Оптимальное управление двумя параллельными стеками в двухуровневой памяти

Рассматривается задача управления двумя стеками в двухуровневой памяти. Предполагается, что вершины двух стеков растут навстречу друг другу в быстрой памяти, к которй разрешен доступ нескольких параллельных процессоров, и объем стеков превосходит объем быстрой памяти. В быстрой памяти хранятся только вершины стеков, а остальные части хранятся в памяти второго уровня. Если вершина одного из стеков стала пустой или стеки заполнили всю быструю память, то есть произошло переполнение стеков, то происходит обмен с памятью второго уровня так, что каждый раз устанавливается некоторое определенное состояние памяти, после чего начинается следующий этап работы. Рассматривается задача выбора этого состояния памяти в зависимости от вероятностей включения и исключения элементов стеков с тем, чтобы среднее время работы до следующего перераспределения памяти было максимальным.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 01–01–00113 и 03–01–06415.