автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математические модели и алгоритмы оптимального управления динамическими структурами данных

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ

ОПТИМАЛЬНОГО УПРАВЛЕНИЯ ДИНАМИЧЕСКИМИ СТРУКТУРАМИ ДАННЫХ

05.13.18 — Математическое моделирование, численные методы и комплексы программ 05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Соколов Андрей Владимирович

Санкт-Петербург 2006

Работа выполнена в Институте прикладных математических исследований Карельского научного центра РАН.

Официальные оппоненты:

доктор физ.-мат. наук, профессор Баранов Сергей Николаевич доктор физ.-мат. наук, профессор Граничин Олег Николаевич доктор физ.-мат. наук, профессор Серебряков Владимир Алексеевич

Ведущая организация: Московский государственный университет им. М.В. Ломоносова.

Защита состоится " 2006 г. в часов на засе-

дании диссертационного совета Д 212.232.51 по защите диссертаций на соискание ученой степени доктора наук при СПбГУ по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., д. 28.

С диссертацией можно ознакомиться в научной библиотеке им. A.M. Горького СПБГУ по адресу: Санкт-Петербург, Университетская набережная., д. 7/9.

Автореферат разослан

Ученый секретарь диссертационного совета Д 212.232.51 д.ф.-м.н., профессор

Б. К. Мартыненко.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Актуальность темы определяется потребностями индустрии программного и аппаратного обеспечения, особенно для мобильных устройств, встроенных систем, различных сетевых устройств, например, маршрутизаторов, и т. п. Такие устройства имеют жесткие ограничения на ресурсы памяти. Разработка программных систем для них требует особого внимания к алгоритмам управления памятью. В настоящее время достаточно хорошо развита теория страничной виртуальной памяти. Различные модели и алгоритмы оптимального замещения страниц исследовались в работах Ахо А., Деннинга Р, Ульмана Дж., Михновского С.Д., Шора Н.З., Авена О.И., Когана Я.А., Стояна Ю.А., Кутепова В.П., Пьянкова В.П. и многих других.

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

Этот вывод подтвердила и практика разработки, например, стековых компьютеров и RISC процессоров, где для управления стеками в двухуровневой памяти (регистры — оперативная память) использовались специальные алгоритмы, а не универсальные алгоритмы кэш-памяти. Еще один пример - алгоритмы работы с очередями, необходимые при разработке встроенных операционных систем, управляющих потоками пакетов в сетевых маршрутизаторах, таких, например, как Cisco IOS, где требования на время обработки пакетов маршрутизатором очень жесткие. Механизм страничной виртуальной памяти здесь не используется и вся работа происходит в нескольких пулах оперативной памяти.

Кроме того на практике достаточно широко используются системы с нестраничной организацией памяти. Теория нестраничной организации памяти развита недостаточно. Выводы большинства работ [Кнут Д., Грисс Д., Танненбаум Э., Цикритзис Д., Бернстайн Ф., Bays С.А., Fenton I.S, Paim P.W., Campbell I.A., Shore J. и др.] основаны на имитационном моделировании и часто противоречивы.

В связи с этим актуальной является задача разработки математического аппарата для анализа методов представления в памяти динами-

ческих структур данных.

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

Объекты исследования. Исследуются базовые линейные структуры — стеки, очереди, динамические таблицы, а также список свободных блоков переменной длины. В данной работе в задачах оптимального управления последовательными стеками в двухуровневой памяти мы будем иметь в виду чистые стеки, в которых разрешен доступ только к последнему включенному в стек элементу, а в задачах оптимального управления стеками в одноуровневой памяти доступ внутрь стека разрешен. Это замечание справедливо и по отношению к последовательным очередям.

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

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

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

Анализ ситуации переполнения стека также может быть полезен в связи с проблемой информационной безопасности компьютерных сетей, так как по некоторым данным, проблема переполнения стека (обычно, когда буфер переменной длины затирает адрес возврата, находящийся в вершине стека) оказывается источником ошибок, например, в программах под Unix и Windows примерно в 2/3 случаев.

Задачи управления стеками возникают при разработке RISC-процессоров. В этом случае для работы со скалярными аргументами и локальными переменными процедур организуются перекрывающиеся окна ре-

гистров, которые связаны в кольцо. По существу, в этом случае мы имеем один обычный стек с элементами типа "окно" в главной памяти, несколько верхних элементов которого образуют циклический стек на регистрах. Если вершина регистрового стека совпала с указателем начала с той или другой стороны, т. е. произошло переполнение (или опустошение) вершины стека, то необходимо какое-то число окон переписать в главную память из регистров или наоборот.

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

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

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

Научная новизна. Все предложенные модели и алгоритмы являются новыми.

Результаты диссертации, выносимые на защиту. На защиту выносятся:

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

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

3. Математические модели и алгоритмы оптимального управления тремя последовательными стеками в памяти одного уровня, в случае, если два стека растут навстречу друг другу, а третий расположен отдельно, в случае, если два стека растут навстречу друг

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

4. Математическая модель и алгоритм оптимального управления тремя стеками в двухуровневой памяти, в случае, если два стека растут навстречу друг другу, а третий расположен отдельно.

5. Математическая модель и алгоритм оптимального управления одной Р1РО-очередью в двухуровневой памяти.

6. Математические модели и алгоритмы оптимального управления двумя последовательными циклическими Р1РО-очередями в памяти одного уровня, когда в качестве критерия оптимальности выбрано среднее время до переполнения памяти, а также если целью оптимизации является минимизация доли потеряннных эле-ментов(пакетов) на бесконечном времени.

7. Математические модели, предназначенные для анализа связанного и страничного методов управления двумя РШО-очередями в памяти одного уровня.

8. Новый метод управления несколькими последовательными ПРО-очередями, когда очереди двигаются по кругу друг за другом. Анализ данного метода с помощью разработанной имитационной программы.

9. Оценка минимального размера памяти, необходимого для динамического распределения сегментов разных длин.

10. Математические модели и алгоритмы, предназначенные для оценки эффективности стратегий обслуживания списка свободных блоков произвольной длины.

Связь работы с научными программами, темами. Часть результатов диссертации была получена в рамках исследований, выполнявшихся в ходе работы над госбюджетными темами Института прикладных математических исследований Карельского научного центра РАН. Некоторые результаты данной работы вошли в Основные результаты

в области естественных, технических, гуманитарных и общественных наук РАН за 2004 год.

Работа над данной темой была поддержана инициативными грантами РФФИ(№95-01-00800,№01-01-00113, №06-01-00303), грантом РФФИ на издание монографии "Математические модели и алгоритмы оптимального управления динамическими структурами данных" (№01-0114013).

Апробация результатов диссертации. Результаты диссертации докладывались на семинарах кафедры "Автоматизации сложных систем" и научных конференциях факультета прикладной математики-процессов управления Ленинградского университета (Ленинград, 1974), на семинарах кафедры информатики и математического обеспечения Петрозаводского университета, на ученом совете Института прикладных математических исследований Карельского Научного Центра РАН, на научном семинаре по автоматизации программирования на факультете ВМК МГУ под руководством М.Р. Шура-Бура, на Всесоюзном симпозиуме "Проблемы системотехники" (Ленинград, 1977 г.), на конференции "Автоматизация производства и проектирования РЭА" (Харьков, 1979 г.), на Международной конференции "Развитие и применение открытых систем" (Петрозаводск, 1995 г.), на Семинаре "Неделя Финской Информатики" (Петрозаводск,1999 г.), на III Московской Международной Конференции по Исследованию Операций (Москва, 2001 г.). на I, II Всесоюзной и IV,V,VI Международной Петрозаводской научной конференции "Вероятностные методы в дискретной математике", на Пятом Всемирном Конгрессе по математическому моделированию (Дубна,

2002 г.), на III Всероссийском симпозиуме по прикладной и промышленной математике (Сочи, 2002 г.), на XIII Международной конференции "Проблемы теоретической кибернетики" (Казань, 2002 г.), на V международной конференции "Дискретные модели в теории управляющих систем" (Ратмино, 2003 г.), на Первой Всероссийской научной конференции "Методы и средства обработки информации" (Москва,

2003 г.), на IV Всероссийском симпозиуме по прикладной и промышленной математике (Летняя сессия. Петрозаводск, 2003 г.), (Осенняя сессия. Сочи, 2003 г.), на Восьмом международном семинаре "Дискретная математика и ее приложения" (Москва, 2004 г.), на Второй Всероссийской научной конференции "Методы и средства обработки

информации" (Москва, 2005 г.), а также были приняты к публикации на 13th International Symposium Fundamental of Computation Theory (Riga, FCT 2001, August 22-24), на Second Workshop on Intermediate Reprezentation Engineering for Virtual Machins and Inaugural Conference on the Principles and Practice of Progrmming in Java (Dublin, PPPJ 2002/IRE 2002, June 13-14), на XIV Международной конференции "Проблемы теоретической кибернетики" (Пенза 29 мая- 3 июня 2005 г.).

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, приложения и списка литературы. Общий объем диссертации составляет 301 страницу. Список литературы содержит 118 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении приводится обоснование актуальности темы диссертации, формулировка цели работы, основные научные положения, выносимые на защиту, и описание структуры диссертации.

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

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

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

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

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

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

В качестве математической модели процесса рассмотрим случайное

блуждание на состояниях —1, 0, 1,..., х..... т — 1, т, т + 1, где х —

число верхних элементов стека в быстрой памяти. Будем считать, что вероятность перехода из состояния х в х +1 (увеличение длины стека на единицу в результате включения нового элемента) равна р, а из ж в х — 1 (уменьшение длины стека на единицу в результате исключения одного элемента) равна </ = 1 — р. Блуждание начинается в состоянии хо, а перераспределение происходит в состояниях —1 и т + 1.

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

Показано, что формула для оптимального значения вершины стека в этом случае имеет следующий вид:

Приведены некоторые результаты экспериментов с построенной моделью.

Во втором пункте параграфа рассмотрена задача определения оптимального значения хо с учетом затрат на перераспределение стека. Для р — д = 1/2 получены формулы для оптимального значения х0 для нескольких вариантов стековых архитектур.

= 2 ((,ф)т+2 _

, (m + 2)qln{q/p)'

т

log2

1

P=q= 2' рфц.

(3)

В параграфе 2 рассмотрена задача оптимального управления вершиной стека для немарковской модели поведения стека.

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

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

Для решения задачи перейдем от немарковской модели к цепи Маркова путем удвоения числа состояний. Будем рассматривать в качестве состояний не точки, а переходы из одной точки в другую. Каждому состоянию г поставим в соответствие пару состояний (г,г + 1) и (г + 1,г). Тогда состояния будут нумероваться так:

(0,1) (1,0) (1,2) (2,1) ... (¿,¿+1) (¿+1,1) ... (т-1,т) (т,ш—1). Поглощающие состояния будут (0,-1) и (т, т + 1). Начальное состояние будет обозначаться только номером этого состояния 0 ^ г ^ т.

Сначала рассмотрена задача максимизации среднего времени работы до перераспределения памяти.

Для решения задачи строится матрица переходных вероятностей (матрица С2) из невозвратных состояний в невозвратные для новой цепи Маркова порядка 2т + 1 (так как у нас 2т переходов плюс начальное состояние).

Теорема 1 определяет вид матрицы С}.

Из экономии места вид этой и всех последующих матрий, мы приводить не будем.

Для решения задачи требуется найти фундаментальную матрицу N = (I — С})'1, где I — единичная матрица.

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

Нам будет нужна матрица переходных вероятностей из невозвратных состояний в поглощающие — Я размерности - (2т+ 1,2). Вид матрицы устанавливает Теорема 2.

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

В параграфе 3 приводится частичное решение одной задачи, поставленной Д. Кнутом.

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

Пусть известно, что на каждом шаге с вероятностью р может произойти исключение элемента из одного из стеков и с вероятностью 1 — р может произойти включение информации в один из стеков. Обозначим через М(тп,р) математическое ожидание случайной величины тпах{к\,к2), где кг и к2 — длины стеков при встрече. Д. Кнут поставил задачу разработать математическую модель этого процесса и установить вид функции М(т,р). В (Соколов 1980, Yao 1981, Flajolet 1986, Maier 1991, Louchard 1990, 1994) была построена математическая модель процесса в виде двумерного случайного блуждания в треугольной области с двумя отражающими экранами и одним поглощающим экраном. В ряде работ исследовалось ассимптотическое поведение размеров стеков при переполнении и времени работы до переполнения. В нашей работе предложен алгоритм вычисления Л1(т,р) для конечных значений т.

Обозначим через xi текущую длину первого стека, а через х2 — второго. Тогда в качестве математической модели процесса мы имеем случайное блуждание по целочисленной решетке в области xi ^ 0, х2 > О, xi + х2 < т с вероятностями р/2 сдвинуться влево и вниз, (1 — р)/2 — вправо и вверх. На границах х2 = 0 и xi = 0 с вероятностью р/2, а в точке xi = х2 = 0 с вероятностью р частица остается на месте. Для того чтобы исследовать М(т,р), нужно получить распределение вероятностей поглощения на прямой xi +х2 — т, если частица выходит из точки х\=х2= 0.

Пронумеруем состояния снизу вверх и справа налево, начиная с точки (m,0). Теперь цепь имеет т+1 поглощающее состояние и т(т+1)/2 невозвратных состояний. Для этой цепи справедлива Теорема 3, определяющая вид матрицы переходных вероятностей данной цепи.

Матрица В[1..тп(тп + 1)/2,1 ..тп + 1], определяемая формулой В = = (I—Q)~1R, дает вероятности поглощения блуждания. Отсюда можно вычислить и искомую величину М(гп,р).

Была разработана программа, которая для входных значений рит

генерирует матрицы Я и <Э и вычисляет искомое значение М(тп,р).

В параграфе 4 рассмотрена задача оптимального управления двумя стеками, растущими навстречу друг другу в двухуровневой памяти.

В первом пункте решается задача минимизации среднего числа перераспределений стеков.

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

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

Пусть <71, рх — вероятности исключения и включения в первый стек, 92,Р2 — вероятности исключения и включения во второй стек, где 91 +Р1 + 92 +Р2 = 1.

Обозначим через XI текущую длину первого стека, а через хг — второго. Тогда в качестве математической модели процесса имеем случайное блуждание по целочисленной решетке в области XI > О, Х2 > О,XI +Х2 < тп с вероятностями из точки с координатами (х^хг): <71 — сдвинуться влево, р\ — вправо, — вниз, р2 — вверх. Цель — определить такое состояние 5о = (х^а:^)' ПРИ котором среднее время блуждания до поглощения на прямой XI + = тп + 1 и на прямых х\ = — 1 и х-2 = —1 было максимальным при условии, что процесс начинается в состоянии 5о.

Пронумеруем поглощающие состояния по границе треугольника против часовой стрелки, начиная с точки (т + 1,0), а невозвратные состояния — снизу вверх и справа налево, начиная с точки (ш,0). В этом случае цепь имеет (т + 1)(т + 2)/2 невозвратных состояний и Зш + 4 поглощающих состояний.

Вид матрицы ф устанавливает Теорема 4.

Во втором пункте рассмотрена задача минимизации среднего времени доступа с учетом потерь на перераспределения стеков, если известны затраты на все разрешенные операции.

Наша цель теперь состоит в том, чтобы определить такое состояние 50 = (х5,х§), при котором средние затраты во время блуждания и

перераспределений памяти были бы минимальными при условии, что процесс начинается в состоянии ¿>0.

Для решения задачи потребуется матрица <3, вид которой установлен в предыдущей задаче и матрица Я, вид которой устанавливает Теорема 5.

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

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

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

Геометрически блуждание по целочисленной решетке можно теперь представить как сдвиги вдоль осей координат и по диагоналям. Наша задача состоит в том, чтобы определить такое начальное состояние «о = (я?,^)- чтобы среднее время блуждания до поглощения на прямых XI = —1,Х2 = —1 и ломаной, которая задается уравнениями хх + Х2 = га + 1 и XI + хг = т + 2, было максимально.

Если пронумеровать сначала поглощающие состояния из точки (т,0) (против часовой стрелки), а затем невозвратные (снизу вверх, справа налево), то получим конечную однородную поглощающую цепь Маркова, количество невозвратных состояний в которой будет равно

(т+1)(т+2) 2

Доказана Теорема 6, определяющая структуру необходимой матрицы С}.

Для решения данных задач были разработаны алгоритмы и программы, определяющие оптимальное состояние (х5,х°).

В параграфе 5 рассмотрена задача оптимального расположения п стеков в памяти одного уровня.

Пусть в памяти объема ш единиц требуется расположить тг стеков, вероятностные характеристики которых следующие: р» — вероятность

включения в г-й стек, — вероятность исключения из г-го стека. Процесс начинается, когда стеки пустые. Исключение из пустого стека с вероятностью означает остановку на месте.

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

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

В параграфе 6 рассмотрены задачи оптимального распределения п стеков в памяти одного уровня.

Теперь в силу доказанного ранее мы рассматриваем тг стеков, разбитых на пары растущих навстречу друг другу стеков (нечетный стек, если он есть, предполагается растущим навстречу пустому стеку). Ставится задача определить оптимальное начальное разбиение памяти, где оптимальность понимается как максимизация среднего времени работы со стеками до переполнения.

В данной работе рассмотрен случай п=3.

Пусть в памяти объема ш единиц расположены три стека. Двум стекам, растущим навстречу друг другу, отведено 5 единиц памяти, а третьему стеку тп — з единиц. Обозначим через х1,х2,хз текущие длины стеков. В этом случае в качестве модели имеем трехмерное случайное блуждание в треугольной призме с тремя отражающими экранами XI — —1,Х2 — — 1,хз = —1 и двумя поглощающими экранами

+ х2 — « + 1, хз = тп — в + 1.

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

Сначала рассмотрим задачу оптимального управления тремя стеками, допускающими только включения (<д = 0). Введем новые обозначения X = XI + Х2,У = х3,р =Р1 +Р2,д = РЗ-

В качестве модели мы будем иметь случайное блуждание внутри прямоугольника х ^ О, у О, х < s +1, у <т — s +1 с вероятностями переходов: из точки (ж, у) в точку (х + 1,у) — р\ из точки (ж, у) в точку (х,у + 1) — q = 1 — р. Процесс выходит из начала координат и поглощается на прямых ж = s + 1 и у = m — s + 1. Нашей задачей является нахождение такого значения s и определение того, какое из принять за q (какой стек расположить отдельно), чтобы среднее время блуждания до поглощения было максимальным.

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

m—s я

¡fc=0 fc=о

Теперь нашу задачу можно сформулировать следующим образом: найти 0 ^ s т, и q = pi,p = 1—q, доставляющие максимум функции E(s,q). Аналитическое решение задачи оказалось затруднительно, так как нет явного вида функции E(s,q).

Рассмотрим другой способ решения таких задач — метод разностных уравнений. Обозначим через Т(х,у) среднее время блуждания до поглощения, если начальной точкой блуждания была точка (х, у). Тогда

Т{х,у) = рТ(х + 1,у) + qT(x,y + 1) + 1,

так как в этом случае с вероятностью р мы переходим в состояние х + 1,у, и тогда среднее время будет равно Т(х + 1,у), с вероятностью q переходим в состояние х, у+1, и среднее время будет равно Т(х, у+1). При этом пройдет один шаг до переполнения памяти.

Попав на границы области блуждания, мы уже не двинемся ни на один шаг и, следовательно,

T(s + 1, у) = 0, Т(х, m - s + 1) = 0.

Нашей задачей является нахождение такого значения s и выбор стека, который будет расположен отдельно, чтобы Т(0,0) было максималь-

ным. Были предложены алгоритмы и программы, решающие данную задачу обоими рассмотренными методами.

Результаты экспериментов показали, что оптимальные значения s не всегда совпадают с интуитивно ожидаемым s = тр. Например, для т = 1000 при pi = Р2 = рз = 1/3, s = 661, а не s = 2/3тп = 667, а для pi = 0.6,Р2 = 0.3,рз = 0.1, s — 889, а не s = 0.9m = 900, причем в оптимальном варианте Т = 983.15, а для s = 900, Т — 963.3. Это значит, что если действовать по интуиции, а не по теории, то в среднем в данной ситуации мы будем производить на 20 операций включения в стеки меньше до переполнения памяти.

Задача оптимального управления четырьмя стеками, допускающими только включения сводится к рассмотренной задаче.

Далее рассмотрен общий случай управления тремя стеками.

Определен алгоритм нумерации невозвратных состояний и доказана Теорема 8, определяющая вид подматрицы Q матрицы переходных вероятностей данной цепи, соответствующая переходам из невозвратных состояний в невозвратные.

Была написана программа, решающая данную задачу.

Проведенные эксперименты позволяют сделать некоторые полезные для практики выводы. Когда один из стеков имеет нулевую вероятность исключения (т.е. является динамической таблицей), а остальные операции равновероятны, то лучше объединить эту таблицу с одним из стеков и выделить этой паре достаточно большой размер памяти. Например, в трансляторах в случае использования двух стеков и кучи надо кучу направить навстречу одному из стеков, а другой стек разместить отдельно,т.к. куча часто реализуется так, что ее верхний край может только возрастать. Если же мы работаем с двумя таблицами и стеком, то стек надо объединить с одной из таблиц и дать данной паре несколько больше половины памяти.

В следующем пункте рассмотрен другой способ работы с тремя (и более) стеками в памяти одного уровня. Здесь два стека мы направляем навстречу друг другу с концов участка памяти, а третий располагаем где-то в середине участка и включаем в него элементы попеременно с разных сторон. Операции push и pop для внутреннего стека здесь будут реализовываться несколько сложнее, так как нужно будет вычислять слева или справа от начала находится указатель на вершину стека.

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

Пусть есть т единиц памяти, представим три стека, как четыре, т.е. память делится на две части к и тп — к элементов. Один из трех стеков начинает расти из точки к: при четном включении на единицу влево, при нечетном включении на единицу вправо. Два других стека растут навстречу этому стеку, из противоположных концов памяти. Задача состоит в том, чтобы определить, какой стек расположить по центру и из какой точки он должен начать движение, чтобы среднее время до переполнения было максимальным.

Можно рассмотреть 4 стека таких, что р\ - вероятность включения в первый стек, Щ- - вероятность включения во второй стек, Щ-- вероятность включения в третий стек, рз - вероятность включения в четвертый стек, 91 - вероятность исключения из первого стека, Ц- вероятность исключения из второго стека, Щ- - вероятность исключения из третьего стека и 53 ■ вероятность исключения из четвертого стека. Обозначим через х1,х2,хз,х4 текущие длины стеков. В качестве математической модели имеем четырехмерное блуждание в области XI + Х2 + Хз + Х4 < ТП, Х\ + Х2 < к, Хз + Х4 < тп — к.

Можно представить это блуждание в виде цепи Маркова, если принять за состояния четверки чисел (х1,х2,хз,х4), где Х{ - длина г-го стека, XI + х2 < к, хз + х4 < т — к. Если есть т единиц памяти и память поделена на две части: к и тп — к, то количество невозвратных состояний данной цепи будет равно ("-*+1)("-*+2>(*+1?(*+2).

Предложен алгоритм нумерации состояний, который позволил построить матрицу <3 переходных вероятностей соответствующей цепи Маркова, вид которой определяет Теорема 9.

Были разработаны алгоритм и программа, решающие задачу.

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

В качестве математической модели имеем случайное блуждание в пирамиде: х\ + + хз ^ § . т.к. половина памяти тратится на связи.

Пронумеруем состояния: начиная с плоскости хз = О, Х1+Х2+Х3 < Щи т.д. наверх, в каждой из этих плоскостей нумерация состояний начинается ВДОЛЬ прямой XI + Х2 = Щ — Хз от ОСИ XI К ОСИ Х2 и т.д.

Теперь можно построить матрицу <3 переходных вероятностей однородной поглощающей цепи Маркова. Для этой матрицы справедлива Теорема 10.

Была написана программа, которая реализует алгоритм построения матриц и вычисления среднего времени работы до переполнения памяти.

Рассматривался также случай, когда информационная часть имеет произвольный размер I, поле связи имеет единичную длину, размер памяти ш кратен I + 1.

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

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

Получена формула для оптимального размера страницы, при котором среднее количество единиц памяти, которое тратится непосредственно под данные будет максимально, и найдены максимальная и минимальная оценки для среднего времени работы до переполения памяти.

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

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

Для практики может быть интересен случай, когда память делится не оптимально, а поровну между стеками, т.е. в случае последователь-

ного представления в м а в случае последовательного представления трех стеков, как четырех, к « Щ-, Так логично поступать, когда вероятностные законы, описывающие поведение стеков неизвестны. В этом случае также оказалось, что среднее время в случае последовательного представления не всегда максимально, а иногда будет лучше способ представления трех стеков, как четырех.

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

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

Пусть два стека расположены навстречу друг другу, и им выделяется память объема ггц условных единиц, третий стек расположен отдельно, ему выделяется тпг — т — т\ условных единиц.

Пусть х\, Х2, хз — текущие длины соответственно первого, второго и третьего стеков в быстрой памяти (в условных единицах), где Х1,Х2,хз > О, XI + Х2 < т 1 и хз < шг-

Будем предполагать, что при работе с тремя стеками в двухуровневой памяти переполнение или опустошение любого из стеков в быстрой памяти приводят к обмену данными между быстрой и внешней памятью, в результате которого в быстрой памяти остаются стеки длиной х°, х%, Хз условных единиц соответственно, где х°,х2,хз > О, х^+х" < тх И Хз < ТО2-

Таким образом, ставится задача определить, в какое состояние следует переходить после обмена данными между двумя уровнями памяти, чтобы среднее время работы со стеками в быстрой памяти до переполнения или опустошения одного из них было максимальным. Иначе говоря, требуется определить тг (тог), х^, х§, х^, при которых среднее время работы со стеками в быстрой памяти до следующего обмена будет максимальным.

При ЭТОМ ПОГЛОЩаЮЩИМИ СОСТОЯНИЯМИ ЯВЛЯЮТСЯ ПЛОСКОСТИ Х1+Х2 = = Ш1 + 1 И ХЗ = Ш2 + 1, И ПЛОСКОСТИ XI = —1, Х2 = —1 и Хз = —1.

Доказана Теорема 11, определяющая вид матрицы <3 при выбранной нумерации состояний. Разработаны алгоритм и программа, решающая данную задачу.

В третьей главе рассмотрены задачи оптимального управления Р1ЕО-очередями.

В параграфе 1 решается задача оптимального управления одной очередью в двухуровневой памяти.

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

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

Обозначим через у текущее число начальных элементов в быстрой памяти, а через х — текущее число новых элементов, вставленных в конец части очереди, находящейся в быстрой памяти. Пусть р обозначает вероятность включения нового элемента в очередь, д — вероятность исключения элемента из очереди, где р + ц = 1, т = п — 1 — максимальное число элементов в очереди, которое на 1 меньше, чем число свободных мест в быстрой памяти.

Тогда в качестве математической модели мы будем иметь двумерное случайное блуждание в области х > 0, у ^ 0, х + у < т. Блуждание начинается в точке у — уо,х = 0. В каждый момент времени находясь в точке (х, у), мы можем попасть в точку (х + 1,у) с вероятностью р и в точку (х, у — 1) с вероятностью д. Блуждание имеет два поглощающих барьера х + у = т + 1иу = —1. Попадание на первый барьер означает переполнение быстрой памяти, а на второй барьер — исчерпание числа начальных элементов в быстрой памяти.

Наша задача формулируется следующим образом: какое значение уо следует выбрать, чтобы среднее время блуждания до поглощения было максимальным?

Для вычисления среднего времени блуждания использовался метод построения и численного решения разностного уравнения.

Вычисления показали, что в случае р = я — 1/2, у0 ^ т/2, как могло показаться на первый взгляд, а уо « 0.7т, хотя вид точной формулы

для произвольного т неясен.

В параграфе 2 рассмотрена задача оптимального управления двумя последовательными циклическими очередями в случае раздельной реализации.

Пусть в памяти размера т мы должны работать с двумя последовательными циклическими очередями. Известны некоторые вероятностные характеристики очередей. Пусть рг,д\ обозначают вероятности включения и исключения элементов в первую очередь, Р2,Я2 ~ во вторую, а г обозначает вероятность операции, не изменяющей длины очередей (например, только чтение), где р\ +91 +Р2 + Я2 + г — Предполагается, что в очередях хранятся данные фиксированного размера. При попытке исключения информации из пустой очереди не происходит завершение работы.

Обозначим через х\ и ж2 текущие длины очередей, через в максимальный размер первой очереди, через п = тп—2 максимальный размер двух очередей. Это значение на две единицы меньше размера памяти, так как в реализации циклической очереди один элемент памяти всегда остается свободным для того, чтобы отличить пустую очередь от переполненной. Иногда для этого предлагается хранить длину очереди, но это эквивалентно потере одной ячейки.

Тогда в качестве модели мы будем иметь двумерное блуждание по целочисленной решетке в области —1 < XI ^ в +1, —1 < х2 < п — в +1 с вероятностями переходов: р\ - вправо, <21 - влево, р2 - вверх, -вниз, г- остаться на месте. Блуждание начинается в точке х\—х2 — О, прямые I] = -1 и 12 = -1 - отражающие экраны (попытка исключения из пустой очереди), а прямые хг = в + 1их2 = п — 5 + 1-поглощающие экраны (переполнение одной из очередей).

Ставится задача выбрать такое в, чтобы математическое ожидание времени блуждания до поглощения было максимальным.

Пронумеруем точки области блуждания сверху вниз и справа налево, нумерацию начнем с 0. Эти точки будут соответствовать невозвратным состояниям однородной цепи Маркова. Всего таких состояний будет (в + 1)(п-в + 1).

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

размера памяти генерируют нужную матрицу и решает данную задачу.

В параграфе 3 предложена математическая модель связанного представления двух очередей.

Для связанного способа организации очередей достаточно иметь од-носвязанные списки элементов, упорядоченные от начала очереди к концу. Каждый элемент состоит из двух единиц памяти одинакового размера, одна из которых содержит хранимую информацию, а вторая содержит указатель (связь) на следующий элемент в списке. При таком представлении очередей Щ- единиц памяти затрачено на связи, т. е. для хранения данных мы можем использовать только т — Щ = Щ единиц памяти.

Обозначим х\ и х2 - текущие длины очередей. В качестве математической модели будем иметь случайное блуждание по целочисленной решетке в треугольной области XI + Х2 < ^ + 1, где х\ + х% — Ч^ + 1 -поглощающий экран, попадание на который означает переполнение одной из очередей, х\ — — 1 и хч = — 1 - отражающие экраны, попадание на которые означает исключение элемента из пустой очереди.

Блуждание начинается в точке х\ = х<г = 0. Необходимо найти среднее время блуждания до поглощения при выходе из начального

СОСТОЯНИЯ Х\ = Х2 = 0.

В параграфе 4 предложена математическая модель страничного представления двух очередей.

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

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

Обозначим ц и 12 - текущие длины очередей. При страничном представлении очередей единиц памяти затрачено на связи, т. к. всего ^ страниц и у каждой страницы берем по ячейке. Для хранения

данных у каждой страницы используется х — 1 единица памяти.

В качестве математической модели будем иметь случайное блуждание по целочисленной решетке в треугольной области

т

XI +х2 < ТП---1-1,

X

где х\ + Х2 = т — ^ + 1 - поглощающий экран, а = — 1 и х2 = — 1 отражающие экраны. Блуждание начинается в точке х\= х2 = 0.

Наша задача состоит в том, чтобы найти среднее время блуждания до поглощения при выходе из начального состояния х\ = х2 = О.

Структура матрицы <3 для связанного представления совпадает со структурой матрицы <3 для страничного представления очередей. Ее определяет Теорема 13.

Был разработан алгоритм и программа, которая вычисляет оценку сверху - Ттах, и оценку снизу Тт*„ для среднего времени блуждания в случае страничного представления, и среднее время для связанного представления очередей.

В параграфе 5 представлены результаты численных экспериментов с разработанными программами.

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

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

Для практики может представлять интерес также анализ последовательного представления очередей, когда память делится не оптимально в зависимости от вероятностных характеристик очередей, а просто пополам. Так логично поступать, если мы не знаем зараннее вероятностных характеристик очередей. В этом случае последовательное представление двух РШО-очередей с делением памяти на две равные доли может быть хуже связанного в том случае, когда алгоритмы или

устройства, которые отвечают за включение и исключение элементов в очереди, работают так, что при переполнении одной очереди вторая очередь с очень большой вероятностью является пустой.

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

Построить математическую модель этого метода управления очередями не удалось и поэтому была разработана имитационная модель для анализа двух методов(нового предложенного нами и проанализированного в параграфе 2 раздельного метода представления) управления двумя Р1РО-очередями в памяти одного уровня.

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

Для каждой из очередей определены операции включения и исключения элементов, а также - "пустая" операция, т.е. операция не изменяющая длин очередей. Предполагались заданными вероятности всех операций, размер памяти тп> О, точка входа второй очереди в и количество итераций модели.

Эксперименты показали, что в случае работы на бесконечном времени раздельный метод хранения очередей лучше, чем наш метод (доля потерянных элементов меньше).

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

В параграфах 7 и 8 приведены постановки задач управления несколькими очередями, когда разрешено одновременное выполнение операций над очередями.

В параграфе 9 рассмотрена задача оптимального управления очередями в общей памяти в случае бесконечного времени блуждания.

Здесь рассмотрен другой способ управления очередями. Если в предыдущих задачах при переполнении одной из очередей работа прекращалась, то теперь процесс завершен не будет, а будет продолжен следующим образом: если очередь занимает всю предоставленную ей память, то все последующие элементы поступающие в нее отбрасываются до тех пор, пока не появится свободная память (т.е. до тех пор, пока не произойдет исключение элемента из очереди). Такая схема работы применяется в работе сетевых маршрутизаторов в том случае, когда по мере увеличения трафика на исходящем интерфейсе маршрутизатора очередь на нем заполняется пакетами. Такое поведение маршрутизатора называется "сбросом хвоста". Понятно, что процесс сброса пакетов приводит к нежелательному результату, поэтому, число таких ситуаций необходимо свести к минимуму.

Теперь перейдем непосредственно к постановке задачи. Сохранив все обозначения параграфа 2, в качестве модели мы будем иметь блуждание по целочисленной решетке в той же области, причем переходные вероятности для области, ограниченной прямыми хг — —1, х2 = —1, XI = я, х2 — п — в останутся прежними.

Блуждание начинается в точке х\ — х2 = 0, прямые х\ = — 1 и х2 = —1 - отражающие экраны (попытка исключения из пустой очереди). Определим теперь поведение процесса на прямых х\ — в + 1 и х2 = п — в + 1, которые и будут соответствовать ситуациям "сброса хвоста". Рассмотрим сначала прямую х\ = в + 1. Пусть процесс находится в состоянии (8 + 1,х2), т.е. первая очередь заняла всю пре-

доставленную ей память и произошла попытка включения еще одного элемента. С вероятностью р\ мы остаемся на месте, т.к. при попытке включения элемента в переполненную очередь он будет потерян и для процесса блуждания ничего не изменится, с вероятностью q■L процесс перейдет в состояние (в —1,Х2), с вероятностью г - в состояние (в, х2), с вероятностью р2 - в ($,х2 + 1) и с вероятностью 92 - в (в, х2 — 1). Аналогичные рассуждения можно применить для определения поведения процесса на прямой хг = п — в + 1, только рассматривая состояние (х1,п —в + 1). Таким образом, прямые х1=5 + 1их2 = 7г — в + 1 также можно рассматривать как отражающие экраны и данная модель описывает блуждание в прямоугольнике на бесконечном времени. Ставится задача выбрать такое в, чтобы доля времени, которое процесс проведет на прямых Х1=в + 1 их2=п — в + 1 была минимальной.

Был разработан алгоритм и программа, которая для заданных значений вероятностей и размера памяти генерирует необходимую матрицу и находит предельное распределение для нашей Марковской цепи. Далее, используя теоремы о законе больших чисел для конечных регулярных цепей Маркова, мы устанавливаем оптимальное разбиение памяти между очередями, так, чтобы время проведенное в состояниях, где теряются пакеты, было минимальным. Указанные теоремы устанавливают тот факт, что доли времени, которые процесс проводит в конкретных состояниях цепи на бесконечном времени, определяются вектором предельных вероятностей. По данному вектору для каждого разбиения памяти мы вычисляем суммарную долю времени, которую процесс проводит в тех состояниях, гле теряются элементы(пакеты), включаемые в очереди, то есть на границах прямоугольной области блуждания х1=в + 1их2=п — в + 1, которые соответствуют ситуациям "сброса хвоста". Разработаны алгоритм и программа для решения рассмотренной задачи.

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

В параграфе 1 получена оценка минимального размера памяти, необходимого для динамического распределения сегментов разных длин.

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

свободной памяти упорядочен по возрастанию адресов и для удовлетворения запросов на память используются стратегии "FIRST-FIT" или "BEST-FIT". Обозначим теперь через N(M,n) такой минимальный размер памяти, который следует предоставить системе для того, чтобы при любой последовательности заявок и освобождений, удовлетворяющей приведенным выше ограничениям, не возникало переполнения памяти. В работе (Robson 1971) рассматривалась задача определения N*(Ai,n), где М и п имеют тот же смысл, a N*(M,n) обозначает минимальный необходимый размер памяти, который следует предоставить системе при условии, что посылает заявки, и удаляет блоки из памяти некий разумный игрок (нападающий), его противник (защитник) размещает заявки в памяти, причем первый желает увеличить размер занимаемой памяти, а второй стремится помешать этому. В вышеупомянутой статье дана формула для N*(M, 2) и приводятся нижняя и верхняя оценки в общем случае. Легко видеть (это следует из определения величин N*(M,n) и N(M,n)), что верхняя оценка и точная формула не могут быть использованы в том случае, когда для обслуживания свободного списка применяются стратегии "FIRST-FIT" или "BEST-FIT", а не стратегия некоего разумного защитника. Например, N*(7,2) = 10, а N(7,2) = 11.

В этом параграфе получена формула для N(M, 2) и верхняя оценка в общем случае. Все следующие рассуждения можно обобщить для получения оценок величины N(M, h, ...,1п), где k — размеры разрешенных сегментов.

Теорема 14.

N(M, 2) = (ЗМ - 1)/2 , если MmodA = 1(М 5);

N(M, 2) = (ЗМ + 1)/2 , если MmodA 2(М ^ 7);

N(M, 2) = ЗМ/2 , если Mmod2 = О(М ^ 4).

, Из этой теоремы следует, что если используются блоки двух размеров, причем один больше другого в два раза, то в наихудшей ситуации суммарная длина свободных блоков примерно в два раза меньше суммарной длины занятых блоков. Этот результат хорошо согласуется с эмпирическим "правилом пятидесяти процентов" Кнута .

В случае произвольного тг получена верхняя оценка для N(M,n).

В параграфе 2 даны оценки эффективности методов динамического

распределения нестраничной памяти.

В пунктах 1 и 2 строятся модели методов "FIRST-FIT" и "BEST-FIT".

В пункте 3 приведена модель метода "OPT-FIT", при которой на каждом шаге помещаем запрос в свободную память так, чтобы максимизировать среднее время до переполнения памяти.

■ Оптимальная стратегия распределения памяти находится здесь методом динамического программирования.

В пункте 4 построена модель метода динамического распределения памяти основной памяти раздела, который использовался в широко известной в 1980-е годы операционной системе ОС ЕС ЭВМ (IBM 360).

Метод заключается в следующем. Организуется список свободных блоков, упорядоченный по убыванию адресов. Все запросы на память супервизор делит на два класса. Запросы первого класса удовлетворяются согласно стратегии "FIRST-FIT", а для удовлетворения запросов второго класса проводится поиск самого последнего подходящего блока в списке свободных блоков. Такой метод заведомо увеличивает время поиска свободного блока по сравнению с методом "FIRST-FIT". Интересно отметить, что время поиска в таком методе распределения памяти можно сократить, если связать свободные блоки в список с двумя связями так, что поиск можно начинать то с одного, то с другого конца списка свободной памяти. С другой стороны, следует выяснить, компенсируются ли затраты на поиск снижением степени фрагментации памяти.

Обозначим через ..., хп вектор длин свободных блоков, упорядоченный по убыванию адресов. Пусть р — вероятность того, что запрос будет размещаться в первом подходящем свободном блоке, а 1 — р - в последнем подходящем свободном блоке. Определена функция Т(хi,...,xn), которая вычисляет среднее время до переполнения памяти, если начальным было состояние памяти xi,...,x„.

В пункте 5 приведены результаты численных экспериментов с разработанными программами. Проведенные эксперименты по сравнению методов "FIRST-FIT" и "BEST-FIT" показали, что, например, для равномерного закона распределения вероятностей стратегия "BEST-FIT" эффективнее.

Для анализа метода динамического распределения памяти ОС ЕС ЭВМ было проведено несколько экспериментов (использовались равно-

мерный, биномиальный и экспоненциальный законы распределения). Для всех серий экспериментов время до переполнения оказывалось больше, если запросы удовлетворяются преимущественно с одного из концов списка свободных блоков. Самое худшее время имеем при р — 0.5, а лучшие времена при р = 1 (метод "FIRST-FIT") и при р = О (метод "последнего подходящего"). Если основываться на этих данных, то приходим к выводу, что метод динамического распределения памяти, принятый в ОС ЕС ЭВМ, увеличивая затраты на поиск свободных блоков, не снижал степени внешней фрагментации памяти. Следовательно, существовал весьма простой способ улучшения принятого в ОС ЕС ЭВМ метода распределения памяти, а именно: нужно был отказаться от деления супервизором всех запросов на классы и все запросы размещать согласно стратегии "FIRST-FIT". Практически это, видимо, свелось бы просто к исключению нескольких команд из супервизора ОС ЕС.

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

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Мазалов В. В., Соколов А. В. Об оптимальном динамическом распределении нестраничной памяти. Управление в динамических системах. Л., 1979,с.206-214. Деп. в ВИНИТИ 24.07.1979.

2. Соколов A.B. Оценка минимального размера памяти, необходимого для динамического распределения сегментов разных длин // Автоматизация эксперимента и обработки данных. Петрозаводск, 1980. С. 59-65.

3. Соколов А. В. О распределении памяти для двух стеков // Автоматизация эксперимента и обработки данных. Петрозаводск,

1980. С. 65-71.

4. Соколов А. В. Оптимальное динамическое распределение нестраничной виртуальной памяти: Дис. канд. физ.-мат. наук. ЛГУ,

1981.

5. Соколов А. В. Математические модели динамического распределения памяти // Тезисы докл. I Всесоюз. науч. конф. "Вероятностные методы в дискретной математике" / КФ АН СССР. Петрозаводск, 1983. С. 28-32.

6. Соколов А. В. Анализ метода динамического распределения памяти в ОС ЕС ЭВМ // Математическое обеспечение ЭВМ и систем управления. Петрозаводск, 1985. С. 28-32.

7. Соколов А. В. Оценка эффективности методов динамического распределения нестраничной памяти // Программирование. 1986. № 5. С. 65-71.

8. Соколов А. В. Об оптимальном управлении стековой памятью //Тезисы докл. I Всесоюз. науч. конф. "Вероятностные методы в дискретной математике" / КФ АН СССР. Петрозаводск, 1988. С. 115.

9. Соколов А. В. Оптимизация динамических структур данных. Учебное пособие. Петрозаводск: Изд-во ПетрГУ, 1993. 58 с.

10. Соколов А. В. Анализ эффективности алгоритмов динамического распределения нестраничной памяти // Труды II Междунар. конф. "Развитие и применение открытых систем". Петрозаводск, 1995. С. 76-77.

11. Sokolov А. V. On the problem of optimal stack control in two levels memory // Probabilistic methods in discrete mathematics: Proceedings of the Fourth International Petrozavodsk Conference. Utrecht, Netherlands: VSP, 1997. P. 349-351.

12. Sokolov A. V. On the problem of stack control // Proceedings' of Finnish Data Processing Week. 1999. Vol. 2. Petrozavodsk: Petrozavodsk University Press. P. 95-106.

13. Соколов А. В. Математические модели и алгоритмы оптимального управления динамическими структурами данных // Обозрение прикладной и промышленной математики. 2000. Т. 7. Вып. 1. С.199-200.

14. Соколов А. В. Об оптимальном управлении очередями в ограниченной памяти // Обозрение прикладной и промышленной математики. 2000. Т. 7. Вып. 2. С. 419-421.

15. Sokolov А. V. Mathematical Models and Optimal Algorithms of Dynamic Data Structure Control I I Fundamental of Computation Theory. 13th International Symposium, FCT 2001, Proceedings, In:Lecture Notes in Computer Science, vol. 2138, Springer-Verlag, p. 416-419.

16. Sokolov A. V., Lemetti A. A. On the problem of optimal stack control // Probabalistic methods in discrete mathematics: Proceedings of the Fifth International Conference. Utrecht, Netherlands: VSP, 2001. P. 351-366.

17. A.V. Sokolov Mathematical Models and Optimal Algorithms of Dynamic Data Structure Control 11 Abstracts. The 3rd Moscow International Conference On Operations Research (ORM2001) (Moscow, April 4-6, 2001) p. 109-110.

18. Соколов А. В. Создание персональной научной коллекции по теме "Математические модели и алгоритмы оптимального управления динамическими структурами данных" // Сборник аннотаций стендовых докладов III Всероссийской конференции по электронным библиотекам. Петрозаводск, 2001. С. 22-23.

19. Соколов А. В., Тарасюк А. В. Об оптимальном управлении циклическими очередями // Труды Института прикладных математических исследований КарНЦ РАН. 2001. Вып. 3. С. 190-195.

20. А.В. Соколов Вероятностные модели динамических структур данных // Труды третьего Всероссийского симпозиума по прикладной и промышленной математике. Сочи, 1-6 октября, 2002, Обозрение прикладной и промышленной математики. Москва 2002, С. 453.

21. Соколов А.В. Математические модели и алгоритмы оптимального управления динамическими структурами данных. Изд. ПГУ. 2002 г. 215 с.

22. Соколов А.В. Математические задачи оптимального управления динамическими структурами данных. Проблемы теоретической кибернетики. // Тезисы докладов XIII Международной конференции. (Казань, 27-31 мая 2002). Москва 2002. Изд. центра прикладных исследований при механико-математическом факультете МГУ. С. 169.

23. Соколов А.В. Математические задачи теории структур данных. Карелия и РФФИ // Тезисы докладов научной конференции, посвященной 10-летию РФФИ. Петрозаводск 2002. С. 96-97.

24. Аксенова Е. А., Волкова О. В., Лазутина А. А., Соколов А. В. Методы оптимального управления стеками в двухуровневой памяти // Труды Института прикладных математических исследований КарНЦ РАН. 2002. Вып. 3. С. 127-152.

25. A.V. Sokolov, Е.А. Aksenova, А.А. Lazutina, A.V. Tarasyuk Mathematical models of dynamic data structure // V international congress on mathematical modelling. Book of abstract, vol. II, JINR, Dubna 2002, P. 127.

26. Sokolov A. V. Optimization strategies of stack control // Proceedings of the Second Workshop on Intermediate Reprezentation Engineering for Virtual Machins and Inaugural Conference on the Principles and Practice of Progrmming in Java. Trinity College Dublin, PPPJ 2002/IRE 2002, June 13-14, 2002. P. 151-156.

27. Sokolov A.V. // Optimization strategies of stack control. Chapter 22. In. Recent Advances in Java Technology. Theory, Application, Implementation. Intermediate Reprezentation Engineering. Computer Science Press, Trinity College Dublin 2002. P. 193-203.

28. E.A. Аксенова, А.А. Лазутина, А.В. Соколов, А.В. Тарасюк Об оптимальном управлении динамическими структурами данных // Труды V международной конференции "Дискретные модели в теории управляющих систем." Ратмино, Изд. отдел ВМК МГУ им. М.В. Ломоносова, 2003. С. 5-6.

29. Е.А. Аксенова, A.A. Лазутина, A.B. Соколов, A.B. Тарасюк Оптимальные методы динамического распределения нестраничной памяти // Труды Первой Всероссийской научной конференции "Методы и средства обработки информации". Изд. отдел ВМК МГУ им. М.В. Ломоносова, 2003. С. 74-79.

30. A.B. Соколов, A.B. Тарасюк. Об оптимальном управлении двумя последовательными очередями // Обозрение прикладной и промышленной матем. 2003 т. 10, в. 1, с. 223-224.

31. Соколов A.B., Ислентьев Д.О., Колосов A.C. Анализ нестандартных методов представления связных списков // Труды ИПМИ КарНЦ РАН. Методы математического моделирования и информационные технологии. Выпуск 4. 2003. С. 188-193.

32. Е.А. Аксенова, A.A. Лазутина, A.B. Соколов Об оптимальном распределении памяти для стеков // Обозрение прикладной и промышленной матем. 2003 т. 10, в. 1, с. 86-87.

33. Е.А. Аксенова, A.A. Лазутина, A.B. Соколов Об оптимальных методах представления динамических структур данных // Обозрение прикладной и промышленной матем. 2003 т. 10, в. 2. С. 375-376.

34. Аксенова Е.А., Лазутина A.A. , Соколов A.B. Исследование немарковской модели управления стеком в двухуровневой памяти // Программирование, 2004, № 1. С. 1-10.

35. Е.А. Аксенова, A.B. Соколов Об оптимальном управлении двумя FIFO очередями. Материалы VIII Международного семинара "Дискретная математика и ее приложения", с. 167-169. М.: Изд-во механико-математического факультета МГУ, 2004, 444 с.

36. Соколов A.B., Соломатов В.А, Анализ методов управления двумя FIFO очередями // Труды ИПМИ КарНЦ РАН. Методы математического моделирования и информационные технологии. Выпуск 5. 2004. С. 121-127.

37. Е.А. Аксенова, A.A. Лазутина, A.B. Соколов. Анализ методов представления динамических структур данных // Обозрение прикладной и промышленной математики. 2004, т.11, в.2. С. 233-234

38. Е. А. Аксёнова, А. В.Соколов Оптимальные методы управления FIFO-очередями в памяти одного уровня. Тезисы докладов XIV Международной конференции "Проблемы теоретической кибернетики"// Изд-во центра прикладных исследований при механико-математическом факультете МГУ, Москва 2005. С. 8.

39. Лазутина А. А. , Соколов A.B. Оптимальное управление тремя стеками в памяти одного уровня. Тезисы докладов XIV Международной конференции "Проблемы теоретической кибернетики"// Изд-во центра прикладных исследований при механико-математическом факультете МГУ, Москва 2005. С.84.

40. Соколов A.B., Тарасюк A.B. Об оптимальном управлении двумя FIFO-очередями на бесконечном времени. Тезисы докладов XIV Международной конференции "Проблемы теоретической кибернетики"// Изд.-во центра прикладных исследований при механико-математическом факультете МГУ, Москва 2005. С. 148.

41. A.B. Соколов, A.B. Тарасюк. Об оптимальном управлении циклическими FIFO-очередями // Системы управления и информационные технологии. 2005, № 3(20). С. 29-33.

42. Е.А. Аксенова, A.B. Соколов, Некоторые задачи оптимального управления FIFO очередями // Труды Второй Всероссийской научной конференции "Методы и средства обработки информации". Изд. отдел ВМК МГУ им. М.В. Ломоносова, 2005. С. 318-322.

Изд. лиц. № 00041 от 30.08.99. Подписано в печать 23.05,06. Формат 60x84 '/i6. Бумага офсетная. Гарнитура «Times». Уч.-изд. л. 1,8. Усл. печ. л. 2,0. Тираж 100 экз. Изд. № 45. Заказ № 588

Карельский научный центр РАН, Редакционно-издательский отдел 185003, Петрозаводск, пр. А. Невского, 50

Введение

1 Динамическое распределение памяти

1.1 Базовые структуры данных.

1.1.1 Линейные списки

1.1.2 Стеки, очереди и деки.

1.1.3 Последовательное представление стека

1.1.4 Последовательное представление очереди

1.1.5 Связанное представление линейных списков

1.1.6 Список свободной памяти.

1.1.7 Последовательное представление нескольких линейных списков.

1.1.8 Бинарные деревья.

1.1.9 Произвольные деревья.

1.1.10 Применение динамических структур в машинной графике.

1.1.11 Другие области применения стеков и очередей

1.1.12 Применение очередей в 1Ш1Х-подобных системах

1.2 Виртуальная память.

1.2.1 Развитие способов адресации

1.2.2 Организация обмена информацией между уровнями памяти.

1.2.3 Фрагментация памяти.

1.2.4 Методы динамического распределения нестраничной памяти.

1.3 Применение стеков в процессорах.

1.3.1 Классификация стековых компьютеров

1.3.2 Методы управления памятью в стековых компьютерах.

1.3 3 Управление регистровыми окнами в Препроцессорах

Оптимальное управление стеками

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

2.1.1 Минимизация среднего числа перераспределений стека.

2.1.2 Минимизация среднего времени доступа с учетом потерь на перераспределения стека

2.2 Немарковская модель поведения стека

2.2.1 Максимизация среднего времени

2.2.2 Минимизация средних затрат времени с учетом перераспределения.

2.3 Решение задачи Д. Кнута о двух стеках, растущих навстречу друг другу

2.4 Оптимальное управление двумя стеками, растущими навстречу друг другу в двухуровневой памяти

2.4.1 Минимизация среднего числа перераспределений стеков

2.4.2 Минимизация среднего времени доступа с учетом потерь на перераспределения стеков

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

2.5 Оптимальное расположение п стеков в памяти

2.6 Оптимальное распределение п стеков в памяти одного уровня

2.6.1 Оптимальное начальное распределение памятиИБ

2.6.2 Случай п=3.

2.6.3 Оптимальное управление тремя стеками, допускающими только включения.

2.6.4 Оптимальное управление четырьмя стеками, допускающими только включения.

2.6.5 Оптимальное управление тремя стеками в общем случае.

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

2.6.7 Оптимальное управление тремя стеками, когда два стека растут навстречу друг другу, а третий растет навстречу им обоим одновременно

2.6.8 Математическая модель связанного метода представления трех стеков

2.6.9 Математическая модель страничного представления трех стеков.

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

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

3 Оптимальное управление очередями

3.1 Оптимальное управление одной очередью в двухуровневой памяти.

3.1.1 Параметризованная реализация циклической очереди в двухуровневой памяти.

3.1.2 Математическая модель.

3.1.3 Результаты вычислений.

3.2 Оптимальное управление двумя циклическими очередями в случае раздельной реализации.

3.2.1 Оптимальное управление двумя циклическими очередями в случае раздельной реализации, когда разрешены только включения в очереди.

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

3.4 Математическая модель страничного представления двух очередей

3.4.1 Выбор оптимального размера страницы

3.4.2 Матрица переходных вероятностей.

3.5 Численные результаты.

3.6 Оптимальное управление двумя очередями в случае, когда очереди двигаются друг за другом по кругу

3.6.1 Результаты экспериментов.

3.7 Оптимальное управление к очередями в памяти одного уровня

3.8 Оптимальное управление очередями в общей памяти в случае, когда очереди принадлежат разным процессам

3.8.1 Случай раздельной последовательной циклической реализации.

3.8.2 Случай, когда очереди двигаются друг за другом по кругу.

3.9 Оптимальное управление очередями в общей памяти в случае бесконечного времени блуждания

4 Оптимальные методы распределения памяти сегментами разных длин

4.1 Оценка минимального размера памяти, необходимого для динамического распределения сегментов разных длин.

4.2 Оценка эффективности методов динамического распределения нестраничной памяти

4.2.1 Модель метода "FIRST-FIT".

4.2.2 Модель метода "BEST-FIT".

4.2.3 Модель метода "OPT-FIT".

4.2.4 Модель метода динамического распределения памяти в ОС ЕС ЭВМ.

4.2.5 Анализ численных результатов.

Настоящий бум сейчас переживает индустрия производства программного и аппаратного обеспечения для различных устройств типа мобильных телефонов, встроенных систем, различных сетевых устройств, например, маршрутизаторов, и т. п. Такие устройства имеют жесткие ограничения на ресурсы памяти. Разработка программных систем для них требует особого внимания к алгоритмам управления памятью. В настоящее время достаточно хорошо развита теория страничной виртуальной памяти. Различные модели и алгоритмы оптимального замещения страниц исследовались в работах Ахо А., Деннинга Р, Ульмана Дж., Михновского С.Д., Шора Н.З., Авена О.И., Когана Я.А., Стояна Ю.А., Кутепова В.П., Пьянкова В.П. и других ученых, которые будут проанализированы в первой главе диссертации.

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

Этот вывод подтвердила и практика разработки, например, стековых компьютеров и RISC процессоров, где для управления стеками в двухуровневой памяти (регистры — оперативная память) использовались специальные алгоритмы, а не универсальные алгоритмы кэш-памяти. Еще один пример - алгоритмы работы с FIFO-очередями, необходимые при разработке встроенных операционных систем, управляющих потоками пакетов в сетевых маршрутизаторах, таких, например, как Cisco IOS, где требования на время обработки пакетов маршрутизатором очень жесткие. Механизм страничной виртуальной памяти здесь не используется и вся работа происходит в нескольких пулах оперативной памяти.

Кроме того на практике достаточно широко используются системы с нестраничной организацией памяти. Теория нестраничной организации памяти развита недостаточно. Выводы большинства работ [Кнут Д., Грисс Д., Танненбаум Э., Цикритзис Д., Берн-стайн Ф., Bays С.A., Fenton LS, Paim P.W., Campbell I.A., Shore J. и др.] основаны на имитационном моделировании и часто противоречивы.

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

Первой задачей математического анализа динамических структур данных, рассмотренной нами, была задача, которая состоит в следующем: пусть в памяти объема m расположены два стека, растущие навстречу друг другу. В этом случае место их встречи можно рассматривать как случайную величину. Пусть известно, что на каждом шаге с вероятностью р может произойти исключение элемента из одного из стеков и с вероятностью 1-р может произойти включение информации в один из стеков. Обозначим через М(т,р) математическое ожидание случайной величины тах(к\,к2), где к\ик2- длины стеков при встрече. Д.Кнут поставил задачу разработать математическую модель этого процесса и установить вид функции М(т,р). В работах [Соколов A.B. 1980, Yao A.C. 1981, P. Flajolet 1986, G.Louchard 1990,1994,R.S.Maier 1991] была построена математическая модель процесса в виде двумерного случайного блуждания в треугольной области с двумя отражающими экранами и одним поглощающим экраном. Эта задача была важна как ступень в разработке новых математических моделей и постановке и решении новых задач оптимального управления динамическими структурами данных. Была, в частности, предложена математическая модель метода динамического распределения памяти в широко известной в 1980-е годы операционной системе ОС ЕС ЭВМ(1ВМ 360) и даны рекомендации по его улучшению, а также высказана гипотеза об улучшении метода управления памятью в МВК Эльбрус-1.

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

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

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

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

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

Анализ ситуации переполнения стека также может быть полезен в связи с проблемой информационной безопасности компьютерных сетей, так как по некоторым данным, проблема переполнения стека (обычно, когда буфер переменной длины затирает адрес возврата, находящийся в вершине стека) оказывается источником ошибок, например, в программах под Unix и Windows NT примерно в 2/3 случаев.

Задачи управления стеками возникают при разработке RISC-процессоров. В этом случае для работы со скалярными аргументами и локальными переменными процедур организуются перекрывающиеся окна регистров, которые связаны в кольцо. По существу, в этом случае мы имеем один обычный стек с элементами типа "окно" в главной памяти, несколько верхних элементов которого образуют циклический стек на регистрах. Если вершина регистрового стека совпала с указателем начала с той или другой стороны, т. е. произошло переполнение (или опустошение) вершины стека, то необходимо какое-то число окон переписать в главную память из регистров или наоборот.

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

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

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

Диссертация состоит из введения, четырех глав, приложения и списка литературы. Общий объем диссертации составляет 301 страницу. Список литературы содержит 118 наименований.

Результаты работы программ показывают, что среднее время в случае представления трех стеков как четырех, когда память разделена интуитивно, для некоторых вероятностей может быть лучше, чем в случае интуитивного последовательного представления стеков, (см. строки Таблицы 22: 3,4,5,8,9). Это происходит тогда, когда все вероятности исключения ^ 0.2 и также тогда, когда среди вероятностей исключения хотя бы одна близка к нулю. В остальных случаях среднее время интуитивного последовательного представления стеков лучше, чем в случае интуитивного представления трех стеков как четырех.

Также, если среди вероятностей исключения хотя бы одна близка к нулю, то среднее время в случае оптимального последовательного представления трех стеков хуже, чем среднее время в случае оптимального представления трех стеков, как четырех, (см. строки Таблицы 22: 4,8,9).

Рассмотрим теперь случай, когда информационная часть имеет произвольный размер поле связи имеет единичную длину, размер памяти т кратен / +1. Тогда в качестве математической модели имеем случайное блуждание по целочисленной решетке, с расстоянием между узлами I + 1, в пирамиде: х\ + х2 + £3 < щ.

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

Рассмотрим последовательное представление трех стеков, в случае разной длины информационного поля узла и поля связи, т.е. когда I > 1. В этом случае, размер памяти т должен быть кратен I, среднее время можно вычислить по алгоритму, приведенному в параграфе 2.6.5.

Результаты сравнения этих двух способов представлены в таблице 23.

1. Абрамов В. Г., Трифонов Н. П., Трифонова Г. Н. Введение в паскаль. М.: Наука, 1988.

2. Авен О. И., Коган Я. А. Управление вычислительным процессом в ЭВМ. М.: "Энергия", 1978.

3. Аксенова Е. А., Волкова О. В., Лазутина А. А., Соколов А. В. Методы оптимального управления стеками в двухуровневой памяти // Труды Института прикладных математических исследований КарНЦ РАН. 2002. Вып. 3. С. 127-152.

4. Аксенова Е.А., Лазутина A.A., Соколов A.B. Об оптимальном распределении памяти для стеков // Обозрение прикладной и промышленной матем. 2003 т. 10, в. 1, с. 86-87.

5. Аксенова Е.А., Лазутина A.A., Соколов A.B. Об оптимальных методах представления динамических структур данных

6. Аксенова Е.А., Лазутина A.A. , Соколов A.B. Исследование немарковской модели управления стеком в двухуровневой памяти // Программирование, 2004, N1, с. 1-10.

7. Аксенова Е.А., Соколов A.B. Об оптимальном управлении двумя FIFO очередями. Материалы VIII Международного семинара "Дискретная математика и ее приложения", с. 167-169. М.: Изд-во механико-математического факультета МГУ, 2004, 444 с.

8. Аксенова Е.А., Лазутина A.A., Соколов A.B. Анализ методов представления динамических структур данных // Обозрение прикладной и промышленной математики. 2004, т.11, в.2, с. 233-234

9. Аксенова Е.А., Соколов A.B. Некоторые задачи оптимального управления FIFO-очередями. Труды Второй Всероссийской научной конференции "Методы и средства обработки информации". Изд. отдел ВМК МГУ им. М.В. Ломоносова, 2005. с. 318-322.

10. Ахо А., Деннинг Р., Ульман Дж. Принципы оптимального замещения страниц // Новая серия. Вып. 9. М.: Мир, 1972. С. 34-102.

11. Боллапрагада В., Мэрфи К., Уайт Р. Структура операционной системы Cisco IOS // Вильяме , 2002.

12. Брайант Р., О'Халларон Д. Компьютерные системы. Архитектура и программирование. БХВ-Петербург, 2005.

13. Брусенцов Н. П. Миникомпьютеры. М.: Наука, 1979.

14. Бурцев В. С. Тенденции развития высокопроизводительных систем и многопроцессорные вычислительные комплексы. Препринт / ИТМ и ВТ АН СССР. М., 1977.

15. Вайнгартен Ф. Трансляция языков программирования. М.: Мир, 1979.

16. Ван-дер-Варден Б. Л. Алгебра. М.: Наука, 1976.

17. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985.

18. Гоисс Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975.

19. Жоголев Е. A., Pay О. И. Принципы оптимального распределения памяти // Вычислительные методы и программирование. М.: Изд-во МГУ, 1971. С. 18-38.

20. Иванов А. П., Шевяков В. С. Управление памятью в МВК ЭЛЬБРУС-1. Препринт № 3 / ИТМ и ВТ АН СССР. М., 1981.

21. Ивченко Г. И. Время ожидания и связанные с ним характеристики в полиномиальной схеме // Дискретная математика. 1993. Вып. 5. № 3. С. 3-34.

22. Ивченко Г. И., Иванов А. В. Разделимые статистики в обратных урновых задачах // Дискретная математика. 1995. Вып. 7. № 2. С. 103-117.

23. Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1970.

24. Кнут Д. Искусство программирования для ЭВМ. Т. 1. М.: Мир, 1976.

25. Кнут Д. Искусство программирования для ЭВМ. Т. 3. М.: Вильяме, 2001.

26. Колчин В. Ф., Севастьянов Б. А., Чистяков В. П. Случайные размещения. М.: Наука, 1976.

27. Колчин В. Ф. Случайные отображения. М.: Наука, 1984.

28. Кормен Е., Лейзерсон Ч., Ривест Р. Алгоритмькпостроение и анализ. М.:МЦНМО, 2000.

29. Королев Л. Н. Структуры ЭВМ и их математическое обеспечение. М.: Наука, 1978.

30. Кохонен Т. Ассоциативные запоминающие устройства. М.: Мир, 1982.

31. Кутепов В. П., Пьянков В. П. Алгоритмы определения множества активных страниц (сегментов) программы, основанные на понятии динамического цикла // Программирование. 1979. № 4. С. 44-52.

32. Лавров С. С., Гончарова Л. И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971.

33. Лазутина А. А. , Соколов A.B. Оптимальное управление тремя стеками в памяти одного уровня // Тезисы докладов XIV Международной конференции "Проблемы теоретической кибернетики". Изд. -во центра прикладных исследований при

34. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

35. Мазалов В. В. Метод динамического распределения нестраничной памяти // Программирование. 1995. № 4. С. 29-32.

36. Мазалов В. В., Соколов А. В. Об оптимальном динамическом распределении нестраничной памяти. Управление в динамических системах. Л., 1979. Деп. в ВИНИТИ 24.07.1979.

37. Медведев Ю. И. Некоторые теоремы об асимптотическом распределении статистики х2 II Доклады АН СССР. 1970. Вып. 192. № 5. С. 987-989.

38. Михновский С. Д., Шор Н. 3. Оценка минимального числа пересылок при динамическом распределении страничной памяти // Кибернетика. 1965. № 5. С. 18-21.

39. Олифер Н. Маршрутизатор как он есть // Журнал сетевых решений LAN. 2001. Т. 7. № 7-8 С. 20-24.

40. Поливанный И. В. Оценка размера буфера для флагового STACK/QUEUE алгоритма заполнения 4-связной области на дискретном растре // Программирование. 1998. № 3. С. 3845.

41. Пратт Т. Языки программирования. М.: Мир, 1979.

42. Ранделл Б. Разбиение памяти и сегментация программ // Экспресс-информация. Вычислительная техника. 1969. №47.

43. RISC: Эффективные архитектуры для СБИС-компьютеров. Электроника СБИС. Проектирование микроструктур

44. Робачевский А. М. Операционная система UNIX. СПб.: BHV-Санкт-Петербург, 1998.

45. Роджерс Д. Алгоритмические основы машинной графики. М.: Мир, 1989.

46. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск. Изд.-во "ДиаСофт", 2001. 688 с.

47. Соколов А. В. Анализ метода динамического распределения памяти в ОС ЕС ЭВМ // Математическое обеспечение ЭВМ и систем управления. Петрозаводск, 1985. С. 28-32.

48. Соколов А. В. Анализ эффективности алгоритмов динамического распределения нестраничной памяти // Труды II Меж-дунар. конф. "Развитие и применение открытых систем". Петрозаводск, 1995. С. 76-77.

49. Соколов А. В. Математические модели динамического распределения памяти // Тезисы докл. I Всесоюз. науч. конф. "Вероятностные методы в дискретной математике" / КФ АН СССР. Петрозаводск, 1983. С. 28-32.

50. Соколов А. В. Математические модели и алгоритмы оптимального управления динамическими структурами данных // Обозрение прикладной и промышленной математики. 2000. Т. 7. Вып. 1. С. 199-200.

51. Соколов А. В. Об оптимальном управлении стековой памятью // Тезисы докл. I Всесоюз. науч. конф. "Вероятностные методы в дискретной математике" / КФ АН СССР. Петрозаводск, 1988. С. 115.

52. Соколов А. В. Оптимальное динамическое распределение нестраничной виртуальной памяти: Дис. . канд. физ.-мат. наук. ЛГУ, 1981.

53. Соколов А. В. Оптимизация динамических структур данных. Учебное пособие. Петрозаводск: Изд-во ПетрГУ, 1993. 58 с.

54. Соколов А. В. О распределении памяти для двух стеков // Автоматизация эксперимента и обработки данных. Петрозаводск, 1980. С. 65-71.

55. Соколов A.B. Оценка минимального размера памяти, необходимого для динамического распределения сегментов разных длин // Автоматизация эксперимента и обработки данных. Петрозаводск, 1980. С. 59-65.

56. Соколов А. В. Оценка эффективности методов динамического распределения нестраничной памяти // Программирование. 1986. № 5. С. 65-71.

57. Соколов А. В., Тарасюк А. В. Об оптимальном управлении циклическими очередями // Труды Института прикладных математических исследований КарНЦ РАН. 2001. Вып. 3. С. 190-195.

58. Соколов A.B. Вероятностные модели динамических структур данных // Труды третьего Всероссийского симпозиума по

59. Соколов A.B. Математические модели и алгоритмы оптимального управления динамическими структурами данных. Из.- во ПГУ. 2002 г. 215 с.

60. Соколов A.B. Математические задачи теории структур данных. Карелия и РФФИ // Тезисы докладов научной конференции, посвященной 10-летию РФФИ. Петрозаводск 2002, С. 96-97.

61. Соколов A.B., Тарасюк A.B. Об оптимальном управлении двумя последовательными очередями // Обозрение прикладной и промышленной матем. 2003 т. 10, в. 1, с. 223-224.

62. Соколов A.B. , Ислентьев Д.О., Колосов A.C. Анализ нестандартных методов представления связных списков // Труды ИПМИ КарНЦ РАН. Методы математического моделирования и информационные технологии. Выпуск 4. 2003, 188-193.

63. Соколов A.B., Соломатов В.А. Анализ методов управления двумя FIFO очередями // Труды ИПМИ КарНЦ РАН. Методы математического моделирования и информационные технологии. Выпуск 5. 2004, 121-127.

64. Соколов A.B., Тарасюк A.B. Об оптимальном управлении двумя FIFO-очередями на бесконечном времени. Тезисы докладов

65. XIV Международной конференции "Проблемы теоретической кибернетики"// Изд.-во центра прикладных исследований при механико-математическом факультете МГУ, Москва 2005, с. 148.

66. Соколов A.B., Тарасюк A.B. Об оптимальном управлении циклическими FIFO-очередями // Системы управления и информационные технологии. 2005, N3(20), с. 29-33.

67. Спицер Ф. Принципы случайного блуждания. М.: Мир, 1969.

68. Стоян Ю. А. Результаты оценки эффективности оптимального алгоритма замещения // Программирование. 1975. № 2. С. 17-23.

69. Супервизор ОС ЕС ЭВМ. М.: Статистика, 1975.

70. Танненбаум Э. Многоуровневая организация ЭВМ. М.: Мир, 1977.

71. Танненбаум Э. Современные операционные системы. 2-издание. Питер, 2002.

72. Феллер В. Введение в теорию вероятностей и ее приложения. М.: Мир, 1964.

73. Футы К., Судзуки Н. Языки программирования и схемотехника СБИС. М.: Мир, 1988.

74. Алгол 68. Методы реализации. Под. ред. Г.С. Цейтина. Издательство Ленинградского университета. Ленинград 1976.

75. Цикритзис Д., Бернстайн Ф. Операционные системы. М.: Мир, 1977.

76. Шилдт Г. Теория и практика С++. СПб.: BHV-Санкт-Петербург, 1996.

77. Юрченко А. С. Методы динамического распределения нестраничной памяти // Управляющие системы и машины. 1978. № 5. С. 68-74.

78. Яковлев Е. И. Машинная имитация. М.: Наука, 1975.

79. Auiezri S. Fraenkel Paired sequential lists in a memory interval // Inform. Process Lett. 1979. № 8. P. 9-10.

80. Batson A., Shy-Ming Jn., Wood D. C. Measurements of segment Size // Second Symposium on operating systems principles. October 20-22. 1969. Princeton: Princeton University, 1969. P. 25-29.

81. Bays C. A. A comparison of Next-fit, First-fit and Best-fit // CACM. 1977. V. 20, № 3. P. 191-192.

82. Campbell /. A. A note an optimal-fit method for dynamic allocation of storage // The Computer Journal. 1971. V. 14, № 1. P. 7-9.

83. Dening P. J. The working set model for program behaviour // CACM. 1968. V. 11, № 8. P. 323-333.

84. Dening P. J. Virtual Memory // Computing Surveys. 1970. V. 2, 3. P. 153-189.

85. Ditzel David R., McLellan H. R. Register Allocation for Free: The С Machine Stack Cache // Proc. Symp. Archit. Support Progr. Lang. Oper. Systems. 1982. P. 48-56.

86. Ertl Anton M. Stack caching for interpreters // SIGPLAN'95 Conf. Program. Lang. Des. and Implem. (PLDI). June 1995. P. 315-327.

87. Flajolet P. The evolution of two stacks in bounded space and random walks in a triangle // Lec. Notes Computer Sci. 1986. Vol. 223. P. 325-340.

88. Harlan D. Mills, Richard C. Linger. Data structured progamming: program design without arrays and pointers // IEEE Trans. Software Eng. 1986. V. 12, № 2. P. 192-197.

89. Hasegava M., Shigei Y. High-speed top-of-stack scheme for VLSI processor: a management algorithm and its analysis // Proceedings of 12th Symposium on Computer Architecture. June. 1985. P. 48-54.

90. Koopman P. Stack Computers. Ellis Horwood, 1989. URL: http://www.cs.cmu.edu/~koopman/stackcomputers/

91. Leung C. H. An improved optimal-fit procedure for dynamic storage allocation // Comp. J. 1982. V. 25, № 2. P. 199-206.

92. Louchard G. Random walks, heat equation and distributed algorithms / G. Louchard, R. Schott, M. Tolley, P. Zimmermann // J. Comput. Appl. Math. 1994. № 53. P. 243-274.

93. Louchard G., Schott R. Probabilistic analysis of some distributed algorithms // Lect. Notes Computer Sci. 1990. № 431. P. 239253.

94. Maier R. S. Colliding Stacks: A Large Deviations Analysis // Random Structures and Algorithms. 1991. № 2. P. 379-421.

95. Patterson D. A., Sequin C. H. Reduced Instruction Set VLSI Computer // Proceedings of 8th Symposium on Computer Architecture. 1980. № 6. P. 72-86.

96. Sokolov A. V. On the problem of optimal stack control in two levels memory // Probabilistic methods in discrete mathematics: Proceedings of the Fourth International Petrozavodsk Conference. Utrecht, Netherlands: VSP, 1997. P. 349-351.

97. Sokolov A. V. On the problem of stack control // Proceedings' of Finnish Data Processing Week. 1999. Vol. 2. Petrozavodsk: Petrozavodsk University Press. P. 95-106.

98. Sokolov A. V., Lemetti A. A, On the problem of optimal stack control // Probabaiistic methods in discrete mathematics: Proceedings of the Fifth International Conference. Utrecht, Netherlands: VSP, 2001. P. 351-366.

99. Sokolov A.V. Mathematical Models and Optimal Algorithms of Dynamic Data Structure Control.// Abstracts. The 3rd Moscow International Conference On Operations Research(ORM2001)(Moscow, April 4-6, 2001) p. 109-110.

100. Sokolov A. V., Aksenova E.A., Lazutina A.A., Tarasyuk A.V. Mathematical models of dynamic data structure. // V international congress on mathematical modelling. Book of abstract, vol. II, JINR, Dubna 2002, P. 127

101. Sokolov A.V. Optimization strategies of stack control // Proceedings of the Second Workshop on Intermediate

102. Reprezentation Engineering for Virtual Machins and Inaugural Conference on the Principles and Practice of Progrmming in Java. Trinity College Dublin, PPPJ 2002/IRE 2002, June 13-14, 2002. P. 151-156.

103. Sokolov A.V. // Optimization strategies of stack control. Chapter 22. In. Recent Advances in Java Technology. Theory, Application, Implementation. Intermediate Reprezentation Engineering. Computer Science Press, Trinity College Dublin 2002. P. 193-203

104. Stanley T., Wedig R. A performance analysis of automatically managed top of stack buffers // Proceeding of 14th Symposuim on Computer Architecture. June. 1987. P. 272-281.

105. Taivalsaari A. Implementing a Java™ Virtual Machine in the Java Programming Language. Sun microsystems 11 Technical Report Series. March. 1998.

106. Tamir Y., Sequin C. Strategies of control register's file // IEEE Trans. Comput. C-32(ll). 1983. P. 977-1037.

107. URL: http://www.hackzone.ru/articles/ntbo.html

108. Yao A. C. An analysis of a memory allocation scheme for implementating stacks // SIAM J. Computing. 1981. № 10. P. 398-403.