Главная страница « Научно-исследовательский семинар « 2003 «

Рассмотрены задачи оптимального распределения последовательных стеков и очередей в памяти одного и двух уровней.

Показано, что оптимальным способом расположения стеков, будет такой, когда стеки разбиты на пары стеков, растущих навстречу друг другу. В предположении, что известны вероятностные характеристики стеков, решается задача оптимального распределения памяти для трех стеков, два из которых растут навстречу друг другу. В случае двух уровней памяти задача оптимального управления стеками сводится к выбору оптимальной начальной точки одномерного блуждания на интервале для одного стека, двумерного блуждания внутри треугольника для двух стеков и трехмерного – внутри призмы для трех.

Предложен новый способ динамического распределения памяти для последовательных циклических очередей, когда очереди двигаются по кругу друг за другом. Рассматриваются различные критерии оптимальности, которые зависят от траекторий блуждания до поглощения на границе соответствующей области. В частности, рассматривается способ работы с очередями, применяемый в сетевых маршрутизаторах.

Для некоторых из рассмотренных задач предложены также модели, которые предполагают параллельное выполнение операций со структурами данных, а также возможность того, что вероятности операций зависят от операции, которая была выполнена на предыдущем шаге.

Рассматриваются также задачи оптимального размещения сегментов разных длин в списке свободных блоков разных длин. Предложен теоретически оптимальный метод, а также даны рекомендации по улучшению метода динамического распределения памяти в некоторых операционных системах.

Приглашаются аспиранты и стажеры программистских кафедр.