Содержание к диссертации
Введение
1 Динамическое распределение памяти 20
1.1 Базовые структуры данных 20
1.1.1 Линейные списки 20
1.1.2 Стеки, очереди и деки 21
1.1.3 Последовательное представление стека . 23
1.1.4 Последовательное представление очереди . 25
1.1.5 Связанное представление линейных списков . 28
1.1.6 Список свободной памяти 32
1.1.7 Последовательное представление нескольких линейных списков 34
1.1.8 Бинарные деревья 36
1.1.9 Произвольные деревья 40
1.1.10 Применение динамических структур в машинной графике 43
1.1.11 Другие области применения стеков и очередей 46
1.1.12 Применение очередей в UNIX-подобных системах 46
1.2 Виртуальная память 48
1.2.1 Развитие способов адресации 48
1.2.2 Организация обмена информацией между уровнями памяти 50
1.2.3 Фрагментация памяти 54
1.2.4 Методы динамического распределения нестра ничной памяти 56
1.3 Применение стеков в процессорах 62
1.3.1 Классификация стековых компьютеров 64
1.3.2 Методы управления памятью в стековых компьютерах 65
1.3 3 Управление регистровыми окнами в RISC-
процессорах 67
2 Оптимальное управление стеками 70
2.1 Оптимальное управление одним стеком в двухуров невой памяти 70
2.1.1 Минимизация среднего числа перераспределений стека 70
2.1.2 Минимизация среднего времени доступа с учетом потерь на перераспределения стека 79
2.2 Немарковская модель поведения стека 86
2.2.1 Максимизация среднего времени 88
2.2.2 Минимизация средних затрат времени с учетом перераспределения 94
2.3 Решение задачи Д. Кнута о двух стеках, растущих навстречу друг другу 100
2.4 Оптимальное управление двумя стеками, растущими навстречу друг другу в двухуровневой памяти 106
2.4.1 Минимизация среднего числа перераспределений стеков 106
2.4.2 Минимизация среднего времени доступа с учетом потерь на перераспределения стеков 112
2.4.3 Оптимальное управление двумя параллельными стеками 130
2.5 Оптимальное расположение п стеков в памяти 140
2.6 Оптимальное распределение п стеков в памяти одного уровня 145
2.6.1 Оптимальное начальное распределение памяти145
2.6.2 Случай п=3 145
2.6.3 Оптимальное управление тремя стеками, допускающими только включения 146
2.6.4 Оптимальное управление четырьмя стеками, допускающими только включения 153
2.6.5 Оптимальное управление тремя стеками в общем случае 153
2.6.6 Оптимальное распределение четырех и более стеков в одноуровневой памяти 162
2.6.7 Оптимальное управление тремя стеками, когда два стека растут навстречу друг другу, а третий растет навстречу им обоим одновременно 164
2.6.8 Математическая модель связанного метода представления трех стеков 172
2.6.9 Математическая модель страничного представления трех стеков 182
2.7 Оптимальное управление тремя стеками в двухуровневой памяти 188
2.8 Оптимальное управление п 4 стеками в двухуровневой памяти 192
3 Оптимальное управление очередями 193
3.1 Оптимальное управление одной очередью в двух уровневой памяти 193
3.1.1 Параметризованная реализация циклической очереди в двухуровневой памяти 195
3.1.2 Математическая модель 200
3.1.3 Результаты вычислений 203
3.2 Оптимальное управление двумя циклическими очередями в случае раздельной реализации 205
3.2.1 Оптимальное управление двумя циклически ми очередями в случае раздельной реализа ции, когда разрешены только включения в очереди 211
3.3 Математическая модель связанного представления двух очередей 212
3.4 Математическая модель страничного представления двух очередей 214
3.4.1 Выбор оптимального размера страницы 217
3.4.2 Матрица переходных вероятностей 218
3.5 Численные результаты 224
3.6 Оптимальное управление двумя очередями в случае, когда очереди двигаются друг за другом по кругу 229 3.6.1 Результаты экспериментов 235
3.7 Оптимальное управление к очередями в памяти одного уровня 237
3.8 Оптимальное управление очередями в общей памяти в случае, когда очереди принадлежат разным процессам 238
3.8.1 Случай раздельной последовательной циклической реализации 238
3.8.2 Случай, когда очереди двигаются друг за другом по кругу 240
3.9 Оптимальное управление очередями в общей памя ти в случае бесконечного времени блуждания 241
Оптимальные методы распределения памяти сегмента ми разных длин 247
4.1 Оценка минимального размера памяти, необходимого для динамического распределения сегментов разных длин 247
4.2 Оценка эффективности методов динамического распределения нестраничной памяти 256
4.2.1 Модель метода "FIRST-FIT" 256
4.2.2 Модель метода "BEST-FIT" 257
4.2.3 Модель метода "ОРТ-FIT" 258
4.2.4 Модель метода динамического распределения памяти в ОС ЕС ЭВМ 259
4.2.5 Анализ численных результатов 262
Приложение. Результаты численных экспериментов 266
Приложение 1. Результаты тестирования программ 266
Приложение 2. Анализ результатов 284
Литература
- Последовательное представление стека
- Минимизация среднего времени доступа с учетом потерь на перераспределения стека
- Оптимальное управление двумя циклическими очередями в случае раздельной реализации
- Оценка эффективности методов динамического распределения нестраничной памяти
Введение к работе
Настоящий бум сейчас переживает индустрия производства программного и аппаратного обеспечения для различных устройств типа мобильных телефонов, встроенных систем, различных сетевых устройств, например, маршрутизаторов, и т. п. Такие устройства имеют жесткие ограничения на ресурсы памяти. Разработка программных систем для них требует особого внимания к алгоритмам управления памятью. В настоящее время достаточно хорошо развита теория страничной виртуальной памяти. Различные модели и алгоритмы оптимального замещения страниц исследовались в работах Ахо А., Деннинга Р, Ульмана Дж., Михновского С.Д., Шора Н.З., Авена О.И., Когана Я.А., Стояна Ю.А., Кутепова В.П., Пьянкова В.П. и других ученых, которые будут проанализированы в первой главе диссертации.
Однако по нашему мнению, разработанные специально под конкретную структуру данных алгоритмы будут работать лучше, чем универсальные алгоритмы замещения страничной виртуальной или кэш-памяти.
Этот вывод подтвердила и практика разработки, например, стековых компьютеров и RISC процессоров, где для управления стеками в двухуровневой памяти (регистры — оперативная память) использовались специальные алгоритмы, а не универсальные ал- горитмы кэш-памяти. Еще один пример - алгоритмы работы с FIFO-очередями, необходимые при разработке встроенных опера- | ционных систем, управляющих потоками пакетов в сетевых марш- рутизаторах, таких, например, как Cisco IOS, где требования на время обработки пакетов маршрутизатором очень жесткие. Механизм страничной виртуальной памяти здесь не используется и вся работа происходит в нескольких пулах оперативной памяти.
Кроме того на практике достаточно широко используются системы с нестраничной организацией памяти. Теория нестраничной организации памяти развита недостаточно. Выводы большинства работ [Кнут Д., Грисс Д., Танненбаум Э., Цикритзис Д., Берн-стайн Ф., Bays С.A., Fenton I.S, Paim P.W., Campbell I.A., Shore J. и др.] основаны на имитационном моделировании и часто противоречивы.
В связи с этим задача разработки математического аппарата для анализа методов представления динамических структур данных в ь памяти является весьма актуальной.
Первой задачей математического анализа динамических структур данных, рассмотренной нами, была задача, которая состоит в следующем: пусть в памяти объема m расположены два стека, растущие навстречу друг другу. В этом случае место их встречи можно рассматривать как случайную величину. Пусть известно, что на каждом шаге с вероятностью р может произойти исключение элемента из одного из стеков и с вероятностью 1-р может произойти включение информации в один из стеков. Обозначим через М{т,р) математическое ожидание случайной величины max(kl,k'2), где к\ и к2 - длины стеков при встрече. Д.Кнут поста- ) вил задачу разработать математическую модель этого процесса и установить вид функции М(т,р). В работах [Соколов А.В. 1980, Yao А.С. 1981, P. Flajolet 1986, G.Louchard 1990,1994,R.S.Maier 1991] была построена математическая модель процесса в виде дву- мерного случайного блуждания в треугольной области с двумя отражающими экранами и одним поглощающим экраном. Эта задача была важна как ступень в разработке новых математических моделей и постановке и решении новых задач оптимального управления динамическими структурами данных. Была, в частности, предложена математическая модель метода динамического распределения памяти в широко известной в 1980-е годы операционной системе ОС ЕС ЭВМ(1ВМ 360) и даны рекомендации по его улучшению, а также высказана гипотеза об улучшении метода управления памятью в МВК Эльбрус-1.
Целью диссертации является разработка и анализ новых математических моделей некоторых базовых структур данных, и разработка на основе этих моделей алгоритмов оптимального управления этими структурами данных.
Исследуются базовые линейные структуры — стеки, очереди, динамические таблицы, а также список свободных блоков переменной длины. В данной работе в задачах оптимального управления последовательными стеками в двухуровневой памяти мы будем иметь в виду чистые стеки, в которых разрешен доступ только к последнему включенному в стек элементу, а в задачах оптимального управления стеками в одноуровневой памяти доступ внутрь стека разрешен. Это замечание справедливо и по отношению к последовательным очередям. Дело в том, что в чистых стеках и очередях в случае ситуации переполнения быстрой памяти возможно часть структуры данных переместить в память второго уровня, а в быстрой памяти хранить только ту часть, где производятся исключения и доступ к элементам. В случае стека в эту же часть производятся и включения элементов, а в случае очереди включения производятся в другой конец списка, который также хранится в быстрой памяти. Если же разрешен доступ внутрь структуры данных, то такая оптимизация невозможна.
В случае связанного представления стеков и очередей в памяти одного уровня мы будем иметь ввиду чистые стеки и очереди, так как в противном случае операция доступа к внутреннему элементу, например, по индексу элемента для связанного представления требует некоторого перебора, а в случае последовательного представления адрес элемента просто вычисляется и в критериях оптимальности логично будет потребовать учитывать разную стоимость операций включения и исключения элементов.
Результаты, выводы и рекомендации диссертации могут быть использованы разработчиками программных и аппаратных систем, в которых используются исследуемые структуры данных.
Стеки наиболее широко используются в задачах синтаксического анализа и трансляции, при организации обращений к подпрограммам. Многостековая иерархическая структура применяется для организации параллельных процессов и мультипрограммирования. Стеки также используются при разработке систем реального времени, алгоритмов комбинаторного анализа, дискретной оптимизации, и вообще везде, где процессы имеют рекурсивный характер.
Анализ ситуации переполнения стека также может быть полезен в связи с проблемой информационной безопасности компьютерных сетей, так как по некоторым данным, проблема переполнения стека (обычно, когда буфер переменной длины затирает адрес возврата, находящийся в вершине стека) оказывается источником ошибок, например, в программах под Unix и Windows NT примерно в 2/3 случаев.
Задачи управления стеками возникают при разработке RISC-процессоров. В этом случае для работы со скалярными аргументами и локальными переменными процедур организуются перекрывающиеся окна регистров, которые связаны в кольцо. По существу, в этом случае мы имеем один обычный стек с элементами типа "окно в главной памяти, несколько верхних элементов которого образуют циклический стек на регистрах. Если вершина регистрового стека совпала с указателем начала с той или другой стороны, т. е. произошло переполнение (или опустошение) вершины стека, то необходимо какое-то число окон переписать в главную память из регистров или наоборот.
Очереди используются в алгоритмах машинной графики, поиска на графах, в качестве буфера ввода/вывода, в операционных системах, компьютерных сетях и других приложениях.
Алгоритмы работы со списком свободных блоков переменной длины используются в трансляторах, операционных системах, в системах моделирования.
Для решения поставленных задач используется аппарат управляемых случайных блужданий, цепей Маркова, динамического программирования, разностных уравнений и комбинаторики, имитационное моделирование, численные эксперименты с разработанными алгоритмами и программами.
Диссертация состоит из введения, четырех глав, приложения и списка литературы. Общий объем диссертации составляет 301 страницу. Список литературы содержит 118 наименований.
В первой главе диссертации представлены в основном известные методы реализации таких структур данных, как стеки, очереди, списки, бинарные деревья, описан ряд алгоритмов из различных предметных областей, в которых используются динамические структуры данных, и предложен ряд новых структур данных, например, списки с 1,5 связями, а также последовательные циклические очереди, которые двигаются по кругу одна за другой. Для изложения алгоритмов используется язык C++ и обозначения книги [29].
Также в этой главе дан обзор известных методов реализации систем с виртуальной памятью и описаны методы управления струк- турами данных в некоторых типах процессоров.
В последующих главах представлен ряд новых математических моделей и алгоритмов оптимального управления динамическими структурами данных.
В главе 2 рассмотрены задачи оптимального управления стеками в памяти одного и двух уровней.
В параграфе 1 главы 2 рассматривается задача оптимального управления вершиной стека в быстрой памяти. Предполагается, что мы работаем со стеком, значительно превосходящем выделенный для него участок быстрой памяти. Нашей задачей является определение оптимального количества элементов вершины стека, которое надо держать в быстрой памяти после опустошения и переполнения стека. В качестве математической модели рассмотрено случайное блуждание, а в качестве критериев оптимальности среднее число перераспределений стека и среднее время доступа с учетом потерь на перераспределения стека. Получены аналитические формулы для вычисления оптимального числа элементов стека в быстрой памяти, которые остаются там после переполнения или опустошения быстрой вершины стека. Эти формулы для разных вариантов организации стековой архитектуры позволяют вычислять оптимальное число элементов быстрой вершины в зависимости от размера быстрой памяти, вероятностных характеристик стека и от временных характеристик уровней памяти.
В параграфе 2 рассмотрена аналогичная задача для немарковской модели поведения стека.
В параграфе 3 приведено частичное решение одной задачи, по-ставленой Д. Кнутом. Построена математическая модель в виде случайного блуждания в треугольнике, описывающая поведение двух стеков, растущих навстречу друг другу. На основе этой модели разработан алгоритм для вычисления математического ожидания некоторой величины, которая характеризует данный метод управления стеками.
В четвертом параграфе решается задача оптимального управления двумя стеками, растущими навстречу друг другу в двухуровневой памяти. В этой задаче предполагается, что мы работаем с двумя стеками, растущими навстречу друг другу в участке быстрой памяти, который заведомо меньше чем размеры стеков. Рассматривается задача нахождения оптимального состояния быстрых вершин стека, в которое мы должны переходить после переполнения памяти, или после опустошения одного из стеков. В качестве критериев оптимальности рассмотрено среднее число перераспределений стеков и среднее время доступа к вершинам стеков с учетом потерь на перераспределения стеков. В случае первого критерия изучается также задача оптимального управления двумя параллельными стеками, растущими навстречу друг другу. В этом случае с некоторыми вероятностями могут производиться операции одновременно с двумя стеками.
В параграфе 5 рассмотрена задача оптимального расположения п стеков в памяти одного уровня. Сравниваются способ управления последовательными стеками, когда стеки расположены один за другим, и когда стеки разбиты на пары стеков, растущих навстречу друг другу. Показано, что, если в качестве критерия оптимальности выбрано среднее время до переполнения памяти, то лучшим методом управления стеками является метод, когда стеки разбиты на пары стеков(и одну тройку, если п нечетное), растущих навстречу друг другу.
В параграфе б решается задача оптимального распределения п стеков в памяти одного уровня.
Рассмотрен вариант задачи для п = 3. В этом случае мы считаем, что два стека растут навстречу друг другу, а третий расположен отдельно. Ставится задача определить какой из стеков надо разместить отдельно и как разделить память между парой стеков и третьим стеком. Эта задача сначала рассмотрена для случая, когда разрешены только включения в стеки(заданы вероятности этих операций), а затем для случая, когда заданы вероятности операций включения и исключения элементов в стеки. Предложены модели и алгоритмы для анализа этого метода работы со стеками. Проведенные эксперименты позволяют сделать некоторые полезные для практики выводы. Например, оказалось, что когда один из стеков имеет нулевую вероятность исключения (т.е. является динамической таблицей), а остальные операции равновероятны, то лучше объединить эту таблицу с одним из стеков и выделить этой паре достаточно большой размер памяти. Например, в трансляторах в случае использования двух стеков и кучи надо кучу направить навстречу одному из стеков, а другой стек разместить отдельно. Если же мы работаем с двумя таблицами и стеком, то стек надо объединить с одной из таблиц и дать данной паре несколько больше половины памяти.
Рассмотрен новый способ управления тремя стеками, когда два стека растут навстречу друг другу с концов памяти, а третий стек растет навстречу им обоим одновременно, начиная с некоторой средней точки. В этом методе решается задача оптимального выбора начальной точки расположения для третьего стека. Разработана математическая модель, с помощью которой вычисляется математическое ожидание времени до переполнения памяти.
Изучается метод связанного представления трех стеков. Построена математическая модель этого метода и разработаны алгоритм и программа для вычисления математического ожидания времени до переполнения памяти.
Последним изученным методом управления памятью для трех стеков является метод страничного управления тремя стеками. В этом методе предполагается, что стеки расположены в некотором связанном списке страниц одной длины. Для управления свободными страницами поддерживается список свободных страниц. Рассмотрена задача выбора оптимального размера страницы и найдены максимальная и минимальная оценки для среднего времени до переполнения памяти.
Разработанные модели и программы позволяют для заданных вероятностных характеристик памяти выбирать лучший метод управления тремя стеками в памяти одного уровня.
В параграфе 7 решается задача оптимального управления тремя стеками в двухуровневой памяти.
В главе 3 решаются задачи оптимального управления FIFO-очередями в памяти одного и двух уровней.
В параграфе 1 главы 3 решается задача оптимального управления одной FIFO-очередью в двухуровневой памяти.
В параграфе 2 рассмотрена задача оптимального управления двумя последовательными циклическими FIFO-очередями в памяти одного уровня, когда в качестве критерия оптимальности выбрано среднее время до переполнения памяти.
В параграфах 3 и 4 предложены модели и алгоритмы, предназначенные для математического анализа связанного и страничного методов управления двумя очередями в памяти одного уровня.
В параграфе 5 приводятся результаты численных экспериментов с разработанными моделями.
В шестом параграфе анализируется новый метод управления FIFO-очередями, когда очереди двигаются по кругу друг за другом. Приведены результаты экспериментов с разработанной имитационной программой.
В параграфе 7 приведены постановки задач оптимального управления несколькими очередями в памяти одного уровня, а в параграфе 8 приведены постановки задач управления двумя очередями, когда разрешено параллельное выполнение операций с очередями.
В параграфе 9 предложены модели и алгоритмы для оптималь- ного управления двумя FIFO-очередями, если целью оптимизации является минимизация доли потеряннных элементов(пакетов) на бесконечном времени.
В главе 4 решаются некоторые задачи динамического распределения памяти сегментами разных длин.
В параграфе 1 поставлена и решена задача оценки минимального размера памяти, необходимого для динамического распределения сегментов разных длин.
В параграфе 2 даны оценки эффективности двух наиболее распространенных стратегий обслуживания списка свободных блоков произвольной длины - методов "OPT-FIT"h "FIRST-FIT", предложен теоретически оптимальный алгоритм размещения сегментов "ОРТ-FIT", а также дана оценка динамического распределения памяти в широко известной в 1980-е годы операционной системе ОС ЕС ЭВМ (IBM 360).
В Приложении приведены некоторые результаты численных экспериментов с моделями, разработанными для оптимального управления тремя стеками в памяти одного и двух уровней.
Таким образом, тема исследования, заявленная в диссертации, находится на стыке теории структур данных, теории операционных систем, а также имеет приложения в области аппаратной реализации структур данных, например, в разработках стековых и RISC процессоров и сетевых маршрутизаторов.
Результаты, полученные в диссертации:
Математические модели и алгоритмы оптимального управления одним стеком в памяти, состоящей из двух уровней.
Математические модели, описывающие поведение двух стеков, растущих навстречу друг другу, в случае последовательной и параллельной организации операций работы со стеками. Алгоритмы оптимального управления двумя стеками, растущими навстречу друг другу, в двухуровневой памяти.
Математические модели и алгоритмы оптимального управления тремя последовательными стеками в памяти одного уровня, в случае, если два стека растут навстречу друг другу, а третий расположен отдельно, в случае, если два стека растут навстречу друг другу с концов памяти, а третий стек растет навстречу им обоим одновременно, начиная с некоторой средней точки, а также в случае связанного и страничного представления трех стеков.
Математическая модель и алгоритм оптимального управления тремя стеками в двухуровневой памяти, в случае, если два стека растут навстречу друг другу, а третий расположен отдельно.
Математическая модель и алгоритм оптимального управления одной FIFO-очередью в двухуровневой памяти.
Математические модели и алгоритмы оптимального управления двумя последовательными циклическими FIFO-очередями в памяти одного уровня, когда в качестве критерия оптимальности выбрано среднее время до переполнения памяти, а также если целью оптимизации является минимизация доли потеряннных элементов(пакетов) на бесконечном времени.
Математические модели, предназначенные для анализа связанного и страничного методов управления двумя FIFO-очередями в памяти одного уровня.
Новый метод управления несколькими последовательными FIFO-очередями, когда очереди двигаются по кругу друг за другом. Анализ данного метода с помощью разработанной имитационной программы.
Оценка минимального размера памяти, необходимого для динамического распределения сегментов разных длин.
10. Математические модели и алгоритмы, предназначенные для оценки эффективности стратегий обслуживания списка свобод ных блоков произвольной длины.
Часть результатов диссертации была получена в рамках исследо- ваний, выполнявшихся в ходе работы над госбюджетными темами Института прикладных математических исследований Карельского научного центра РАН. Некоторые результаты данной работы вошли в Основные результаты в области естественных, технических, гуманитарных и общественных наук РАН за 2004 год.
Работа над данной темой была поддержана инициативными грантами РФФИ(95-01-00800,01-01-00113), грантом РФФИ на издание монографии "Математические модели и алгоритмы оптимального управления динамическими структурами данных"(01-01-14013) и грантом конкурса МАС РФФЩ03-01-06415).
Апробация результатов.
Результаты диссертации докладывались на семинарах кафедры "Автоматизации сложных систем'и научных конференциях факультета прикладной математики-процессов управления Ленинградского университета (Ленинград, 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 тезисов докладов на международных, всероссийских и региональных конференциях, одна монография, раздел в коллективной монографии, одно учебное пособие.
Последовательное представление стека
Здесь мы рассмотрим последовательную реализацию стека, когда элементы стека хранятся в последовательных элементах памяти, размер которых зависит от типа переменных, хранящихся в стеке. Мы представим параметризованную версию алгоритма с использованием шаблонов языка C++ [83], [84] (предполагается, что версия транслятора поддерживает их реализацию), в которой тип элементов стека передается в класс как параметр. В данном примере с помощью параметризованного класса будут созданы стеки, хранящие элементы типа int, double и char Для операций включения и исключения элементов в стек сохранены традиционные названия pushQ и рор(). Для хранения элементов используется массив х (это член класса stack — указатель на тип элемента стека telem), для указания на вершину стека — переменная top. Член класса п — это размер выделяемого для стека массива.
Переменная size — это размер стека, который передается конструктору класса как параметр. #include iostream.h #include stdlib.h template class telem class stack{ telem x; int top; int republic: stack(int size); void push(telem y); telem pop(); int empty(){if(top==0) return 1; else return 0;} }; //Конструктор стека template class telem stack telem ::stack(int size) { x=new telem[size]; if(!x){ cout« "Невозможно создать стекДп"; exit(l); } n=size; top=0; } II Помещаем объект в стек template class telem void stack telem ::push(telem y) { if(top==n){ cout « "Стек заполнен.\n"; return ; } x[top]=y; top++; } II Исключаем объект из стека template class telem telem stack telem ::pop() { if(top==0) { cout « "Стек пуст.\п"; return 0; } top—; return x[top]; } void main(void) { stack int x(10);//Создаем стек с 10 элементами типа int stack double y(10);//Создаем стек с 10 элементами типа double stack char z(10)///Создаем стек с 10 элементами типа char //Используем стеки int, double и char, записывая и удаляя из //каждого по одному элементу. x.push(l); у.push(1.1); z.push{ a ); cout« x.pop()«endl; cout« y.pop()«endl; cout«z. pop () «endl ; }
В этой реализации возможны две ситуации переполнения стека, когда не хватает памяти для выполнения операции New при вызове конструктора, или при выполнении функции pushQ. Эти ситуации в разных системах обрабатываются по-разному. В главе 2 мы будем рассматривать задачи, в рамках которых сделана попытка обрабатывать такие ситуации некоторым оптимальным образом.
Под последовательной реализацией очереди обычно понимают циклическую реализацию, так как в противном случае очередь быстро уходит в бесконечность, если не происходит больших последовательных серий исключений, которые опустошают очередь. Пусть в памяти размера п мы работаем с последовательной циклической очередью [29], [83]. Здесь мы приведем параметризованную реализацию с использованием шаблонов языка C++ и обозначений [29]. Член класса R — это указатель на конец очереди, F — указатель на место, непосредственно перед началом очереди (рис. 1).
Член класса п — это размер выделяемого для очереди массива. Он на 1 больше размера очереди size, который передается как параметр конструктору класса queue, так как в циклической реализации [29], [83] один элемент массива обычно оставляют свободным, чтобы отличить пустую очередь от переполненной. Можно вместо этого хранить длину очереди, но это эквивалентно потере одной ячейки.
Метод класса push() помещает элемент в конец очереди, а рор() исключает элемент из начала очереди. Если F догнал R, то произошло опустошение очереди, а если R догнал F (рис. 2), то происходит аварийное завершение по переполнению. В функции main приведены примеры использования данного класса для нескольких типов данных элементов очереди.
Минимизация среднего времени доступа с учетом потерь на перераспределения стека
Рассмотрим теперь задачу определения оптимального значения 2 с учетом затрат на перераспределение стека. Эта задача является обобщением задачи, рассмотренной в работе [41]. Формулировку критерия оптимизации здесь мы дадим в терминах теории кэш ) памяти [35]. Близкая постановка задачи рассматривалась также в
В этой работе предлагается при переполнении перемещать к нижних элементов быстрой вершины стека в память второго уровня и передвигать оставшиеся верхние элементы в начало быстрой памяти, а при опустошении верхушки стека перемещать к верхних элементов стека из памяти второго уровня в быструю память. К сожалению, при построении математической модели и анализе алгоритма в вышеуказанной работе допущена неточность. В критерии оптимизации участвует величина / — среднее время до переполнения памяти, если процесс начинается из состояния к (число элементов стека в быстрой вершине). Но в это состояние мы попадаем только после опустошения, а после переполнения мы переходим в состояние т - к + 1, и, следовательно, в этом случае в критерии оптимизации должна быть величина Дп_ +Ь а не D . В нашей модели параметром выступает не число перемещаемых элементов, а число элементов в быстрой памяти и учитываются вероятности как переполнения, так и опустошения.
Обозначим через 0 время доступа к вершине стека в быстрой памяти, t\ — время перемещения одного элемента в быстрой памяти, ti — время доступа к памяти второго уровня, Ьъ — время обмена одним элементом между уровнями памяти.
В зависимости от архитектурных решений [99], [48] функции потерь в состояниях перераспределения могут иметь разный вид, и поэтому мы рассмотрим несколько возможных вариантов реализации вершины стека.
1. Например, для метода "paging" функция потерь, заданная на состояниях, имеет следующий вид: f(x) = io,/(-1) = ti + 3(2 + 1)-Ко,/(га+1) = t2+{m+li))tt+ti{xo-\)+U). В этом случае мы считаем, что при опустошении вершины стека мыяо + 1 элементов восстанавливаем в буфер из памяти второго уровня, при перепол нении т + 1 -2 элементов запоминаем в памяти второго уровня,
1 перемещаем в начало буфера. Теперь в буфере после ис ключения или включения нового элемента станет хц элементов, и начинается этап работы до следующего переполнения или опустошения. Мы здесь считаем, что потери при перемещении элементов пропорциональны числу перемещаемых элементов.
2. Можно считать, что при переполнении перемещение элементов в буфере не зависит от числа элементов, а занимает фиксированное время t. Тогда f(m + 1) = t2 + к{т + 1 - ж0) + t + Ц.
3. Для аппаратного циклического стека f(m + 1) = t2 + (m+ +1 - #оКз + (ъ так как в отличие от предыдущего случая при переполнении стека не происходит перемещения верхних элементов стека в начало буфера. В зависимости от аппаратных решений функции потерь могут иметь и другой вид.
4. Можно считать, что перемещение между уровнями памяти реализовано так, что время перемещения не зависит от числа перемещаемых элементов. Тогда /(-1) = f(m + 1) = t2 + U.
5. Возможна также реализация с копированием в фоновом режиме и тогда /(-1) = t2 + h{x + 1) + t(b /(wi + 1) = 0. В этом случае запоминание элементов стека в памяти при переполнении не требуется, но нужна более сложная аппаратура, и значительно увеличится время доступа к вершине стека в быстрой памяти.
Возможны и другие варианты архитектурных решений. Напри мер, в работе [48] предлагалось для RISC процессоров делать окна переменного размера, определяемого во время выполнения проце дуры. Математическую модель здесь можно описать в виде слу чайного блуждания весьма приближенно, так как в этом случае вероятности перехода из состояния х в х - / (возврат из процедуры длины /) зависят от длин процедур, находящихся в стеке, т. е. процесс немарковский.
Рассмотрим теперь более подробно введенное в теории кэш памяти [35] понятие среднего коэффициента потерь, равного про центному отношению обращений к памяти, при которых приходи лось вызывать данные из дополнительной памяти, к общему числу обращений. Например, если коэффициент потерь равен 1% (т. е. 1/100 обращений приходится к памяти второго уровня, а 99/100 — к памяти первого уровня), время доступа к памяти второго уровня (i2), включая передачу данных, в 100 раз больше времени досту па в память первого уровня (t0), то средняя скорость вычислений будет составлять примерно половину той скорости, которая была бы, если бы все данные находились в одноуровневой памяти со временем доступа, соответствующим кэш-памяти. Действительно, если t2 = ЮОіоі то среднее время доступа к памяти равно 1 99 199 100i0 + 777 0 = 077 « 2t(h 100 " 100 и "100 Для стековой памяти, как уже отмечалось, средний коэффициент потерь равен 1/Т(х0), где T(XQ) — это математическое ожидание числа шагов до перераспределения.
Оптимальное управление двумя циклическими очередями в случае раздельной реализации
Предположим, что для размера памяти п выполняется утвержде ние теоремы. Размерность матрицы перехода будет (5 + 1)(П - 5 + 1) X (5 + 1)(П + 1) , к = (п + 1) и она будет иметь вид ( ). 3) Индуктивный переход Проверим, что при размере памяти п + 1 выполняется утверждение теоремы. Мы добавили еще одну единицу памяти. Эта единица памяти будет добавлена к какой-нибудь из двух очередей. Рассмотрим варианты:
Пусть единица свободной памяти досталась первой очереди, т. е. значения пи s увеличилось на 1. Для области блуждания это сдвиг на единицу вправо по оси Ох\, следовательно, мы получим п + 1 новых состояний, которые в силу заданной нумерации ( нумеруются в первую очередь. Очевидно, что в этом случае раз мерность матрицы Q увеличится на п + 1, а размерность всех подматриц останется прежней. Кроме того, сами подматрицы останутся прежними, а их число увеличится на 1 (кроме Л ). Таким образом, для размера памяти п + 1 матрица Q будет иметь следующий вид:
Акхк Вк к о Ckxkо Qnxn где z = (s + l)(n + 1) и z = (s + 2)(n + 1). Матрица Q охраняет свою структуру. (2) Пусть единица свободной памяти досталась второй очереди, т. е. значение п увеличилось на 1, а значение s осталось прежним. Для области блуждания это сдвиг на единицу вверх по оси 0x2, следовательно, мы получим s+1 новых состояний. Очевидно, 209 что в этом случае размерность матрицы Q увеличится на s + 1, размерность всех подматриц увеличится на 1, а их число не из ) менится. Обозначим к = (п + 2) и рассмотрим, как изменится вид подматрицы А. Как сказано выше, размерность подматрицы увеличится на 1, в силу заданной нумерации состояний добавятся первая строка и первый столбец и для размера памяти п + 1 подматрица А будет иметь вид: г 92 0 V2 Акхк k о т. е. структура подматрицы не изменится. Аналогично рассуждая, можно показать, что сохранится структура всех подматриц матрицы Q, а значит и сама матрица перехода сохранит свою структуру. Теорема доказана. Для решения задачи найдем фундаментальную матрицу: JV = (/-Q)-l[28], где I - это единичная матрица. Элемент NtJ имеет смысл количества единиц времени, которое процесс находился в состоянии j, если блуждание началось из состояния і, т. е. элемент матрицы, стоящий на пересечении і-ой строки и j-ro столбца есть среднее количество попаданий в невозвратное состояние j из невозвратного состояния і. Необходимо найти матрицу N для всевозможных значений s, которые могут меняться от 1 до п - 1. Для нахождения среднего времени работы очередей просуммируем элементы матрицы N в строке, которая соответствует процессу блуждания, начинающемуся из состояния х\ = #2 = 0, затем сравним полученное время для разных значений s, и выберем максимальное. Для этого были разработаны алгоритм и программа, которая для заданных значений вероятностей и размера памяти генерирует матрицу Q и решает данную задачу.
Оптимальное управление двумя циклическими очередями в случае раздельной реализации, когда разрешены только включения в очереди В этом разделе мы рассмотрим частный случай задачи, когда q\ = qi = 0.
Обозначив pi = р, р2 = 1 —p-r = q, мы получим задачу аналогичную задаче о трех стеках, когда разрешены только включения в стеки, рассмотренную в параграфе 2.6.3(мы здесь будем использовать обозначения параграфа 2.6.3). Эту задачу можно решить или комбинаторным методом, вычисляя распределение времени работы до поглощения, либо построением и решением разностных уравнений от двух переменных. Мы здесь проведем некоторые рассуждения, которые позволят аналитически получить приближенно оптимальное решение. Будем рассматривать двумерное случайное блуждание как наложение двух одномерных блужданий.
Рассмотрим одномерное блуждание вправо до поглощения на экране х = 5 + 1. Тогда, начиная с точки (0,0), мы можем совершать скачки вправо с вероятнотью р и на месте и вверх(с точки зрения одномерного блуждания на месте)с вероятностью q = 1 — р — г. Обозначим через Е\(х) среднее время до поглощения, если блуждание начинается в точке х.
Построим разностное уравнение Ei{x) =р Ei{x + 1) + (q + г) Ei{x) + 1 с граничным условием E\(s + 1) = 0. Решая это уравнение, получаем Е\(х) = (s + 1 - х)/р. Нас интересует блуждание, начинающееся в точке х = 0. В этом случае время блуждания будет (0) = (5+1)/ .
Рассуждая аналогично можно рассмотреть блуждание в вертикальном направлении с поглощающим экраном у = п +1. Обо 211 значим через Е уу) среднее время блуждания до поглощения на экране у = n-s+1. Е2{у) = {n-s+l-y)/q, а Е2(0) = (n-s+l)/q Логично предположить, что если мы хотим максимизировать среднее время до переполнения памяти, то следует выбрать s так, чтобы ?i(0) = Е2{0). Тогда, решая уравнение (s + l)/p = {n-s + \)/q, получаем 5 = p n+p-q. То есть мы получили, что оптимально делить память между очередями следует пропорционально вероятностям включения элементов в очереди, хотя вычисления параграфа 2.6.3 показали, что это интуитивное предположение здесь не работает. Дело здесь в том, что при построении разностных уравнений мы предполагали, что с некоторой вероятностью q + г(или р + г в случае блуждания вверх)мы всегда остаемся на месте, хотя на самом деле с некоторой ненулевой вероятностью мы можем поглотиться на другом поглощающем экране. То есть реальное среднее время работы до поглощения будет меньше, чем вычисленное с помощью решения разностного уравнения. Таким образом с помощью этих рассуждений можно получить только приближенно оптимальное решение. Вычисления показывают, что оптимальное значение 5 всегда несколько меньше чем вычисленное по формуле этого пункта.
Оценка эффективности методов динамического распределения нестраничной памяти
Теперь рассмотрим совершенно другой способ управления очередями, если в предыдущих задачах при переполнении одной из очередей работа прекращалась, то теперь процесс завершен не будет, а будет продолжен следующим образом: если очередь занимает всю предоставленную ей память, то все последующие элементы поступающие в нее отбрасываются до тех пор, пока не появится свободная память (т.е. до тех пор, пока не произойдет исключение элемента из очереди). Такая схема работы применяется в работе сетевых маршрутизаторов в том случае, когда по мере увеличения трафика на исходящем интерфейсе маршрутизатора очередь на нем заполняется пакетами. Заполнение очереди происходит из-за того, что низкая пропускная способность исходящего канала связи не позволяет ему успешно справляться с возрастающим объемом поступающего трафика. И если объем трафика продолжает нарастать со скоростью, превышающей скорость исходящего канала, то вполне возможна ситуация, когда система очередей будет заполнена полностью. Когда это происходит, маршрутизатор не имеет другой альтернативы, кроме удаления всех новых поступающих пакетов. Такое поведение маршрутизатора называется "сбросом хвоста"[15]. Понятно, что процесс сброса пакетов приводит к нежелательному результату, поэтому, число таких ситуаций необходимо свести к минимуму.
Теперь перейдем непосредственно к постановке задачи. Сохранив все обозначения параграфа 3.2, в качестве модели мы будем иметь блуждание по целочисленной решетке изображенной на рис.51, причем переходные вероятности для области, ограниченной прямыми х\ = -1, Х2 — -1, х\ = s, xi = п — s останутся прежними. Блуждание начинается в точке х\ = Х2 = 0, прямые x\ = -1 и x2 = -1 - отражающие экраны (попытка исключения из пустой очереди). Определим теперь поведение процесса на прямых х\ = s + 1 и Х2 = и - б + 1, которые и будут соответствовать ситуациям "сброса хвоста". Рассмотрим сначала прямую х\ = s + 1. Пусть процесс находится в состоянии (s + 1,3:2). т-е. первая очередь заняла всю предоставленную ей память и произошла попытка включения еще одного элемента. С вероятностью р\ мы остаемся на месте, т.к. при попытке включения элемента в переполненную очередь он будет потерян и для процесса блуждания ничего не изменится, с вероятностью qi процесс перейдет в состояние (s - 1,3:2), с вероятностью г - в состояние (s,x2), с вероятностью р2 - в (s,x2 + 1) и с вероятностью q2 - в (s,x2 - 1). Аналогичные рассуждения можно применить для определения поведения процесса на прямой х2 = п — s + 1, только рассматривая состояние (жі,п -5 + 1). Таким образом, прямые х\ = s + 1 и х2 = п + 1 также можно рассматривать как отражающие экраны и данная модель описывает блуждание в прямоугольнике на бесконечном времени. Ставится задача выбрать такое s, чтобы доля времени, которое процесс проведет на прямых Х\ = 5 + 1 и х2 = п + 1 была минимальной.
Зададим нумерацию состояний данного блуждания. Пронумеруем сначала точки области, ограниченной прямыми х\ = 0, х2 = О, х\ = s, х2 = п- s. Удобно пронумеровать их сверху вниз и справа налево, нумерацию начнем с 0. Затем пронумеруем сверху вниз точки прямой х\ = s+1 и справа налево точки прямой х2 = n-s+l. Точку с координатами (s + 1,n-s + l) пропускаем, т.к. при заданных переходных вероятностях попасть в нее мы не сможем. Всего точек в области блуждания будет (s + 2)-(n-s + 2)-l. Нумерация состояний для данной задачи, при п = 3 и s = 2, изображена на рис. 63.
Случайное блуждание будем рассматривать в виде регулярной конечной однородной цепи Маркова с матрицей переходных вероятностей Р. При размере памяти п и заданном значении s размерность матрицы Р будет ((s + 1)(п + 1) + п + 2) х х ((s + l)(n-s + l) + n + 2). При введенной нумерации регулярная матрица перехода Р для последовательного представления очередей имеет определенную структуру. Для данной задачи ее удобно представить в следующем виде:
Где подматрица Q описывает блуждание в области ограниченной прямыми х\ = О, Х2 — 0, х\ = s, Х2 = п и в точности совпадает с матрицей Q из задачи параграфа 3.2, подматрица Q описывает вероятности перехода на прямые х\ = s + І и х2 = п + 1, т.е. первое включение элементов в переполненные очереди и, наконец, подматрица Q" описывает поведение процесса в случаях, когда переполнены одна или обе очереди.
Как было сказано выше, вид матрицы Q нам известен. Теперь рассмотрим подматрицу Q размерности {{п + 1) (s + 1)) х х (п + 2), которая, как упоминалось ранее, описывает вероятности перехода на прямые х\ = s + 1 и х2 = п — s + I
Похожие диссертации на Математические модели и алгоритмы оптимального управления динамическими структурами данных
