Титул
Введение
Постановка задачи
Пример приложения
Результаты
Используемая литература
Постановка задачи
Пусть мы работаем со стеком, значительно превосходящим выделенный для него участок быстрой памяти размера m. В этом случае в быстрой памяти всегда хранится вершина стека, а остальная часть находится в памяти второго уровня. Предполагается, что во время работы со стеком некоторая часть его почти всегда, за исключением, может быть, начала и конца работы процесса, находится в памяти второго уровня. Ставится задача определить, как производить перераспределение стека между уровнями памяти, чтобы минимизировать средние временные затраты. Под перераспределением будем понимать перепись x0+1 верхних элементов стека с памяти второго уровня в быструю память, если быстрая память стала пустой (теперь, после исключения элемента, в быстрой памяти будет х0 элементов) или выталкивание m – x0 +1 элементов на второй уровень и, возможно, перепись x0 – 1 верхних элементов стека в начало быстрой памяти, если произошло её переполнение (теперь, после включения нового элемента в стек, в быстрой памяти станет x0 элементов). После перераспределения памяти начинается следующий этап работы. Нашей целью является нахождение оптимального значения x0.
Данную задачу можно обобщить на случай нескольких стеков
Петрозаводск - 2006