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

В настоящее время вычислительная техника развивается весьма стремительными темпами. Однако, ее базовые понятия, сформированные на заре развития, актуальны до сих пор. К ним относятся, так называемые, структуры данных. Основными из них являются стеки, очереди и деки [14], [10], [31]:

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

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

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

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

В большинстве современных процессорах общего назначения, так или иначе, организована работа со стеком для выполнения операций, для передачи параметров процедурам и обращения к ним (Intel 8080 [9]- Intel 8085 [28]- Zilog Z80 [28]- Motorola 6800 [28]- Motorola 6809 [28]- Zilog Z8000 [25], [28]- Zilog Z8001 [25]- Zilog Z8003 [25]- Motorola 68 000 [28]- Intel 432 [28]- HP 64 000 [29]- VAX-11 [34]- Intel 80 386 [35]- Intel 80 286 [25]- Intel 8086 [16], [11], [28], [25]- Intel Pentium [16]- Intel Itanium [53], Эльбрус 1 и 2 [16], транспьютер фирмы INMOS Т 805 [16]).

Для работы со скалярными аргументами и локальными переменными процедур в первых RISC-процессорах [39], [38] организовывались перекрывающиеся окна регистров, связанные в кольцо. Для передачи параметров не требовалось перемещать данные, так как они находились в зоне пересечения окон регистров. По существу, в этом случае имеем один обычный стек с элементами типа покно" в главной памяти, несколько верхних элементов которого образуют циклический стек на регистрах. В архитектуре Intel Itanium [53] у каждой процедуры есть регистровый стек переменного размера для хранения параметров. Выходные параметры одной процедуры, являющиеся входными параметрами другой, перекрываются.

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

Например, в системе VAX-11, процессорах Intel, Motorola и др., стек наращивается в сторону уменьшающихся значений адресов памяти. Это означает, что указателю позиции вершины того или иного стека первоначально присваивается значение самого старшего адреса области памяти, предоставляемой для организации данного [34], [28], [29].

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

Не существует общепринятого подхода к реализации стека при разработке аппаратного обеспечения. Эта проблема наряду с задачей управления стеками исследуется довольно давно. Так в [12] рассматривались два варианта реализации стека: либо как часть основной оперативной памяти со своим особым механизмом формирования адресов, либо как отдельная сверхоперативная память с такой же организацией формирования адресов. Показаны недостатки каждой из реализации: в первом случае глубина стека может быть практически не ограничена, но такой способ приводит к недопустимо большому числу обращений к главной памятиво втором случае возможности машины в части сложности арифметических выражений, которые могут быть вычислены с ее помощью, тем больше, чем больше глубина стека, однако тем большее время будет занимать при прерываниях программ переписывание данных стека. Компромиссное решение: можно несколько верхних ячеек стека располагать в сверхоперативной памяти. Однако, если количество регистров велико, то возникает сложность передачи данных при прерываниях. Если же таких регистров мало, то количество обращений к оперативной памяти при работе со стеком по-прежнему велико.

То есть в то время не предполагалось как-то управлять процессом переполнения или опустошения верхушки стека.

В стековых компьютерах в случае переполнения и опустошения верхушки стека возможны разные методы управления [43]:

1. Large Stack. Можно сделать стек большим и предполагать, что переполнения не будет, а если переполнение произойдет, то совершить аварийное завершение работы. Так сделано, например, в процессорах WISC CPU/16 с размером стека 256 элементов. Ясно, что, так как одно из основных приложений стековых компьютеров — это управление в реальном времени, такое решение чаще всего неприемлемо.

2. Demand fed single element stack manager. В этой стратегии верхушка стека реализована аппаратно, как циклический буфер, а продолжение стека находится в памяти. На каждый стек требуется три указателя — на верх и низ аппаратного стека и на верх продолжения стека в памяти. При переполнении и опустошении аппаратного стека всегда перемещается один элемент в память из буфера или наоборот. Метод реализован в FRISK 3.

3. Paging stack manager. В этом методе верхушка реализована программно как часть специальной памяти. При опустошении верхушки стека из памяти копируется половина буфера, а при переполнении нижняя половина буфера перемещается в память, а верхняя половина перемещается в начало буфера. Метод реализован в RTX200 и RTX32P.

4. An associative cache. Кэш-память для стековых машин не дает преимуществ по сравнению с рассмотренными методами, так как сложнее для аппаратной реализации и в то же время не учитывает специфики стека как структуры «LIFO». Хотя, если в стек нужно помещать структуры данных переменного размера, такие, как строки и структуры, использование кэшпамяти, как утверждается в работе, может быть целесообразно.

В [52] предполагается реализация стека, когда при переполнении и при опустошении быстрой вершины переносится к элементов стека. Вершина стека является продолжением стека, находящегося в памяти второго уровня.

В работах [23], [52] в качестве теоретической модели описывающей управление вершиной стека в двухуровневой памяти было предложено одномерное случайное блуждание [36]. В [33] в качестве модели рассматривалось блуждание, в котором вероятность включения элемента в стек р (х) это функция от длины стека х.

Однако некоторые специалисты [41] считают, что модель классического случайного блуждания недостаточно точно описывает поведение стеков, а более адекватной была бы модель, в которой вероятность следующей операции со стеком зависит от того, какая операция была предыдущей. Простейшая модель такого рода анализируется в [1], [7].

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

Алгоритм Гаврика перераспределения памяти между стеками в случае переполнения одной из них предложен в [14]. В этом алгоритме при переполнеиии одного из стеков производится перераспределение памяти так, что приблизительно 10% распределяются ровно между стеками, а 90% распределяются пропорционально росту размеров стеков с момента предыдущего перераспределения.

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

В работах [32], [54], [42], [44], [46], [45], [33] была построена математическая модель процесса в виде двумерного случайного блуждания в треугольной области с двумя отражающими экранами и одним поглощающим экраном.

Был предложен алгоритм вычисления М (т, р) для конечных значений т [32]. Для решения задачи использовалась теория поглощающих цепей Маркова.

Решалась задача исследования М (т, р) при т —" со для 0.25 < р < 0.5 [54].

В ряде работ [42], [44], [45] исследовалось асимптотическое поведение стеков при переполнении и времени работы до переполнения памяти для 0 < р > 0.25. Так же задача решалась для случая, когда вероятности включения и исключения информации зависят от размеров стеков[46].

Помимо аппаратного обеспечения понятие стека широко используется в программировании. В операционной системе Unix стек используется в подсистеме управления процессами [24]. Стеки имеют важное значение для исполняющей среды Лауа-программ: текущая Лауа-программа имеет свой собственный Java-стек, который используется для наблюдения за локальными переменными и прочей информацией [40]. Стеки используются в алгоритмах синтаксического разбора [26], для анализа скобочной структуры некоторого текста и вычисления выражений [17], в алгоритмах машинной графики [30], в алгоритмах поиска на графах [14], [15], в алгоритмах сортировки [31]. В современных языках программирования работа со стеком реализуется в виде специальных классов стандартных библиотек, например java.util.Stack в Java2 SDK [40] и stacks в STL (Standard Template Library) в С++ [37]. В языке PostScript реализован внутренний стек [31].

Последовательное представление стеков в программировании используется наряду со связанным представлением, когда стек рассматривается в виде одно-связанного списка: каждый узел содержит поле информации и поле связи, известен указатель на первый элемент [10], [14], [31].

Последовательное и связанное представление сравниваются с точки зрения программирования в [10], [14], [31].

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

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

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

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

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

На защиту выносятся следующие основные результаты:

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

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

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

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

5. Пакет программ, реализующий рассмотренные в работе математические модели. Для заданного размера памяти и заданных наборов вероятностей вычисляется среднее время работы до переполнения или перераспределения, находится оптимальное разбиение памяти для последовательных способов. Пакет разработай на С++ для суперкомпьютера IBM pSeries690(Regatta), установленного на ВМК МГУ им. М. В. Ломоносова.

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

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

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

Апробация работы. Основные материалы диссертации представлялись на Пятом Международном Конгрессе по математическому моделированию (Дубна, 2002 г.) — на V международной конференции «Дискретные модели в теории управляющих систем» (Ратмино, 2003 г.) — на IV Всероссийском симпозиуме по прикладной и промышленной математике (Летняя сессия. Петрозаводск, июнь 2003 г.), (Осенняя сессия. Сочи, октябрь 2003 г.) — на Первой Всероссийской научной конференции «Методы и средства обработки информации» (Москва, 2003 г.) — на Шестой Международной Петрозаводской конференции «Вероятностные методы в дискретной математике» (Петрозаводск, 2004) — на VII Международной конференции «Дискретные модели в теории управляющих систем «(Москва, 2006 г.) — на Российско-Скандинавском симпозиуме «Теория вероятностей и ее приложения «(Петрозаводск, 2006 г.).

Работа поддержана грантами РФФИ № 01−01−0113, № 06−01−303.

Публикация работ. Основные результаты диссертиции опубликованы в 8 статьях [1], [2], [3], [7], [22], [18], [19], [20] и 6 тезисах докладов [49], [4], [5], [6], [21], [50].

Результаты работы программы показывают, что для заданного набора вероятностей среднее время работы в случае связанного представления меньше, чем в случае последовательного представления [33] и чем в случае представления трех стеков, как четырех (См. Таблицы 1.1,1.2).

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

Сравним связанное представление со следующими вариантами последовательного представления (См. Таблицы 1.3, 1.4):

• последовательное в случае оптимального представления стеков (См. раздел 1.1);

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

9 т друг другу отведено ^ единиц памяти, а третьему стеку, расположенному отдельно, отведено у ;

• представление трех стеков, как четырех в оптимальном случае (См. радел 2.2);

• интуитивное представление трех стеков, как четырех, в котором двум парам стеков, растущих навстречу друг другу отведено по j единиц памяти.

Заключение

.

В данной работе получены следующие основные результаты:

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

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

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

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

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