Содержание к диссертации
Введение
1 Оптимальное управление тремя стеками в памяти одного уровня 14
1.1 Постановка задачи 15
1.2 Последовательное представление 16
1.3 Представление трех стеков, как четырех 17
1.3.1 Математическая модель и матрица вероятностей переходов 18
1.3.2 Результаты численных экспериментов 26
1.4 Связанное представление 28
1.4.1 Математическая модель и матрица вероятностей переходов 28
1.4.2 Результаты численных экспериментов 34
1.4.3 Сравнение связанного и последовательного представлений 35
1.4.4 Случай, когда размер информационной части произвольный 37
1.5 Страничное представление 39
1.5.1 Оптимальный размер страницы 40
1.5.2 Математическая модель 40
1.5.3 Результаты численных экспериментов 42
1.6 Заключение 44
Оптимальное управление четырьмя стеками в памяти одно го уровня 46
2.1 Постановка задачи 46
2.2 Связанное представление четырех стеков в памяти одного уровня 47
2.2.1 Математическая модель и матрица вероятностей переходов 47
2.2.2 Результаты численных экспериментов 56
2.3 Страничное представление 57
2.3.1 Оптимальный размер страницы 58
2.3.2 Математическая модель 58
2.3.3 Результаты численных экспериментов 59
2.4 Последовательное представление четырех стеков в памяти од ного уровня 62
2.4.1 Математическая модель 62
2.4.2 Результаты численных экспериментов 63
2.4.3 Сравнение связанного и последовательного представлений 64
2.4.4 Случай, когда размер информационной части произвольный 66
2.5 Заключение 68
Оптимальное управление тремя стеками в случае парал лельного выполнения операций 70
3.1 Случай, когда возможны параллельные включения или параллельные исключения 70
3.1.1 Последовательное представление 71
3.1.1.1 Три стека, допускающих только включения . 71
3.1.1.2 Общий случай 75
3.1.1.2.1 Математическая модель 75
3.1.1.2.2 Результаты численных экспериментов 84
3.1.2 Связанное представление 90
3.1.2.1 Математическая модель 91
3.1.3 Случай, когда длина информационной части имеет произвольный размер 99
3.1.4 Страничное представление 101
3.1.4.1 Оптимальный размер страницы 102
3.1.4.2 Математическая модель 102
3.1.4.3 Результаты численных экспериментов 103
3.2 Случай, когда возможны не более двух параллельных операций, включение и исключение 106
3.2.1 Последовательное представление 106
3.2.1.1 Математическая модель 107
3.2.2 Связанное представление 115
3.2.2.1 Математическая модель 115
3.2.3 Случай, когда длина информационной части имеет произвольный размер 122
3.2.4 Страничное представление 123
3.2.4.1 Математическая модель 123
3.2.5 Результаты численных экспериментов 124
3.3 Заключение 128
4 Немарковская модель управления одним стеком в двухуров невой памяти 130
4.1 Постановка задачи 130
4.2 Математическая модель 134
4.3 Матрица переходных вероятностей 134
4.4 Результаты численных экспериментов 138
Заключение 140
Литература
- Математическая модель и матрица вероятностей переходов
- Связанное представление четырех стеков в памяти одного уровня
- Последовательное представление
- Случай, когда длина информационной части имеет произвольный размер
Введение к работе
В настоящее время вычислительная техника развивается весьма стремительными темпами. Однако, ее базовые понятия, сформированные на заре развития, актуальны до сих пор, К ним относятся, так называемые, структуры данных. Основными из них являются стеки, очереди и деки [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 68000 [28]; Intel 432 [28]; HP 64000 [29]; VAX-11 [34]; Intel 80386 [35]; Intel 80286 [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]: Large Stack. Можно сделать стек большим и предполагать, что переполнения не будет, а если переполнение произойдет, то совершить аварийное завершение работы. Так сделано, например, в процессорах WISC CPU/16 с размером стека 256 элементов. Ясно, что, так как одно из основных приложений стековых компьютеров — это управление в реальном времени, такое решение чаще всего неприемлемо. Demand fed single element stack manager. В этой стратегии верхушка стека реализована аппаратно, как циклический буфер, а продолжение стека находится в памяти. На каждый стек требуется три указателя — на верх и низ аппаратного стека и на верх продолжения стека в памяти. При переполнении и опустошении аппаратного стека всегда перемещается один элемент в память из буфера или наоборот. Метод реализован в FRISK 3. Paging stack manager. В этом методе верхушка реализована программно как часть специальной памяти. При опустошении верхушки стека из памяти копируется половина буфера, а при переполнении нижняя половина буфера перемещается в память, а верхняя половина перемещается в начало буфера. Метод реализован в RTX200 и RTX32R
4. An associative cache. Кэш-память для стековых машин не дает преимуществ по сравнению с рассмотренными методами, так как сложнее для аппаратной реализации и в то же время не учитывает специфики стека как структуры "LIFO". Хотя, если в стек нужно помещать структуры данных переменного размера, такие, как строки и структуры, использование кэшпамяти, как утверждается в работе, может быть целесообразно.
В [52] предполагается реализация стека, когда при переполнении и при опустошении быстрой вершины переносится к элементов стека. Вершина стека является продолжением стека, находящегося в памяти второго уровня.
В работах [23], [52] в качестве теоретической модели описывающей управление вершиной стека в двухуровневой памяти было предложено одномерное случайное блуждание [36]. В [33] в качестве модели рассматривалось блуждание, в котором вероятность включения элемента в стек р(х) это функция от длины стека х.
Однако некоторые специалисты [41] считают, что модель классического случайного блуждания недостаточно точно описывает поведение стеков, а более адекватной была бы модель, в которой вероятность следующей операции со стеком зависит от того, какая операция была предыдущей. Простейшая модель такого рода анализируется в [1], [7].
Помимо задачи управления вершиной стека, актуальной является задача управления несколькими стеками, а именно их оптимальное распределение в памяти и максимизация времени работы до переполнения или опустошения отведенной им памяти. Пусть в памяти одного уровня распределено несколько стеков. Переполнение — это ситуация, когда один из стеков переполнил отведенное, для него место и это значит, что произошла ошибка и один из вариантов возможного далее события — завершение работы программы. Также возможна обратная ситуация — исключение из пустого стека. Это, как правило, не является ошибкой. Такая ситуация может, например, интерпретироваться как переход на другую ветвь алгоритма программы.
Алгоритм Гаврика перераспределения памяти между стеками в случае переполнения одной из них предложен в [14]. В этом алгоритме при пере- полпенни одного из стеков производится перераспределение памяти так, что приблизительно 10 % распределяются ровно между стеками, а 90 % распределяются пропорционально росту размеров стеков с момента предыдущего перераспределения.
Д. Кнут поставил задачу разработать математическую модель процесса распределения памяти для двух стеков, растущих навстречу друг другу и установить вид функции математического ожидания М{т,р), где т -это размер памяти для двух стеков, р — вероятность исключения из одного из стеков. М(т,р) — математическое ожидание случайной величины тах(к]_, А>г), где / и &2 — длины стеков при встрече. Для безотказной работы в случае раздельного хранения двух стеков потребовалось бы 2max(ki,k2) единиц памяти, в то время как для стеков, направленных навстречу друг другу, нужно т = к\ -f к% единиц памяти.
В работах [32], [54], [42], [44], [46], [45], [33] была построена математическая модель процесса в виде двумерного случайного блуждания в треугольной области с двумя отражающими экранами и одним поглощающим экраном.
Был предложен алгоритм вычисления М(щр) для конечных значений т [32]. Для решения задачи использовалась теория поглощающих цепей Маркова.
Решалась задача исследования М(т,р) при т —> со для 0.25 < р < 0.5 [54].
В ряде работ [42], [44], [45] исследовалось асимптотическое поведение стеков при переполнении и времени работы до переполнения памяти для 0 < р > 0.25. Так же задача решалась для случая, когда вероятности включения и исключения информации зависят от размеров стеков[46].
Помимо аппаратного обеспечения понятие стека широко используется в программировании. В операционной системе Unix стек используется в подсистеме управления процессами [24]. Стеки имеют важное значение для исполняющей среды Java-программ: текущая Java-программа имеет свой собственный Java-стек, который используется для наблюдения за локальными переменными и прочей информацией [40]. Стеки используются в алгоритмах синтаксического разбора [26], для анализа скобочной структуры некоторого текста и вычисления выражений [17], в алгоритмах машинной графики [30], в алгоритмах поиска на графах [14], [15], в алгоритмах сортировки [31]. В современных языках программирования работа со стеком реализуется в виде специальных классов стандартных библиотек, например java.util.Stack в Java2 SDK [40] и stacks в STL (Standard Template Library) в C++ [37]. В языке PostScript реализован внутренний стек [31].
Последовательное представление стеков в программировании используется наряду со связанным представлением, когда стек рассматривается в виде одно-связан но го списка: каждый узел содержит поле информации и поле связи, известен указатель на первый элемент [10], [14], [31].
Последовательное и связанное представление сравниваются с точки зрения программирования в [10], [14], [31].
В данной работе построены математические модели этих двух способов представления стеков и сравнение этих способов с точки зрения среднего времени работы до переполнения.
Существует большое количество устройств с ограниченными ресурсами памяти. Это мобильные устройства, встраевыемые системы, бортовые и промышленные компьютеры, системы реального времени, сетевые устройства и т.д. В своей работе они активно используют стековую архитектуру. Поэтому для подобных устройств актуально не только грамотное управление памятью как таковой, но и управление конкретными структурами данных, в частности, стеками. Это позволит повысить эффективность их работы и снизит затраты на производство.
В последнее время вычислительная техника достигла небывалых высот. Наряду с многопроцессорными системами широкое распространение получили системы, основанные на многоядерных процессорах. Это могут быть мощные вычислительные серверы со множеством процессоров и однопроцессорные персональные компьютеры [16]. В связи с этим особую актуальность приобрела задача исследования поведения стеков при параллельном выпол- нении операций. В работе построена модель поведения трех стеков в памяти одного уровня при наличии двух или трех процессоров.
В связи с вышеизложенным, построение математических моделей поведения одного или нескольких стеков в памяти одного или двух уровней, а также с учетом возможного параллельного выполнения операций, является важной и актуальной задачей.
Цель работы — построение математических моделей и алгоритмов оптимального управления стеками, с точки зрения максимизации среднего времени до переполнения одного из стеков в памяти одного уровня и максимизации среднего времени работы до перераспределения одного стека в памяти двух уровней.
На защиту выносятся следующие основные результаты:
Математические модели, описывающие поведение трех стеков в памяти одного уровня для следующих вариантов представления стеков: последовательное представление трех стеков как четырех, связанное, страничное представление.
Математические модели, описывающие поведение четырех стеков в памяти одного уровня для следующих способов представления стеков: последовательное, связанное, страничное представление.
Математические модели, описывающие поведение трех стеков в памяти одного уровня в случае параллельного выполнения операций для следующих способов представления стеков: последовательное, связанное, страничное представление.
Немарковская модель поведения одного стека в двухуровневой памяти в случае, когда вероятность операции, которая будет произведена со стеком на следующем шаге, зависит от того, какая операция была произведена на текущем шаге, для трех алгоритмов управления верхушкой стека.
Пакет программ, реализующий рассмотренные в работе математические модели. Для заданного размера памяти и заданных наборов ве- роятностей вычисляется среднее время работы ло переполнения или перераспределения, находится оптимальное разбиение памяти для последовательных способов. Пакет разработай на C++ для суперкомпьютера IBM pSeries690(Regatta), установленного на ВМК МГУ им. М.В. Ломоносова.
Научная новизна и практическая ценность. В работе предложены новые математические модели поведения трех и четырех стеков в памяти одного уровня, а также трех стеков в случае параллельного выполнения операций в памяти одного уровня. Получены выводы об эффективности основных способов представления стеков с точки зрения максимизации среднего времени работы, в предположении, что известны вероятностные характеристики стеков. Предложена новая математическая модель, описывающая поведение одного стека в двух уровневой памяти, когда вероятность операции, которая будет произведена со стеком на следующем шаге, зависит от того, какая операция была произведена па текущем шаге.
Разработан пакет программ, реализующий рассмотренные в работе математические модели.
Предложенные в работе алгоритмы могут быть использованы при разработке аппаратного и программного обеспечения ЭВМ со стековой организацией памяти и при реализации алгоритмов работы со стеками на обычных ЭВМ.
Апробация работы. Основные материалы диссертации представлялись на Пятом Международном Конгрессе по математическому моделированию (Дубна, 2002 г.); на V международной конференции "Дискретные модели в теории управляющих систем"(Ратмино, 2003 г.); на IV Всероссийском симпозиуме по прикладной и промышленной математике (Летняя сессия. Петрозаводск, июнь 2003 г.), (Осенняя сессия. Сочи, октябрь 2003 г.); на Первой Всероссийской научной конференции "Методы и средства обработки информации" (Москва, 2003 г.); на Шестой Международной Петрозаводской конференции "Вероятностные методы в дискретной математике" (Петрозаводск, 2004); на VII Международной конференции "Дискретные модели в теории управляющих систем "(Москва, 2006г.); на Российско-Скандинавском симпозиуме "Теория вероятностей и ее приложения"(Петрозаводск, 2006г.).
Работа поддержана грантами РФФИ №01-01-0113, №06-01-00303.
Публикация работ. Основные результаты диссертиции опубликованы в 8 статьях [1], [2], [3], [7], [22], [18], [19], [20] и 6 тезисах докладов [49], [4], [5], [6], [21], [50].
Математическая модель и матрица вероятностей переходов
В данном способе представления память разделена на две части к и т — к элементов. Один из трех стеков начинает расти из точки к: при четном включении на единицу влево, при нечетном включении на единицу вправо; при включении и исключении элементов нужно помнить положение вершины этого стека. Два других стека растут навстречу этому стеку, из противоположных концов памяти (См. Рис. 1.2).
Тогда можно рассмотреть три стека, как четыре со следующими вероятностными характеристиками: fe р\ — вероятность включения в первый стек, Ц — вероятность включения во второй стек, Ц — вероятность включения в третий стек, рз — вероятность включения в четвертый стек, qi — вероятность исключения из первого стека, — вероятность исключения из второго стека, у — вероятность исключения из третьего стека и дз — вероятность исключения из четвертого стека. Обозначим через ХиХ2,х$,Х4 текущие длины стеков.
Задача заключается в том, чтобы разбить память на две части так, чтобы среднее время работы со стеками было бы максимальным, т.е. необходимо определить оптимальное значение к, а также определить начало какого стека должно быть в точке к.
Математическая модель и матрица вероятностей переходов В качестве математической модели рассмотрим четырехмерное блуждание в области: х\ + хч + х3 + х4 т, Х\ + х2 к, х$ + х± т — к.
Обозначим СОСТОЯНИе СТОКОВ В ВИДЄ ЧеТВерКИ ЧИСеЛ ( 1,02) 3) 4)) гДе аг - длина г -го стека. Тогда а\ -\- а,2 к и. а + а т — к. Пронумеруем состояния таким образом: (0,0,0,0), (0,0,0,1),...,(0,0,0, m-A:-1),(0,0,0, m-fc) (0,0,1,0),(0,0,1,1),...,(0,0, l,m-fc-l)
Если есть m единиц памяти, то количество состояний равно (m-ft+l)-(m-fc+2).(fc+l)-(fc+2) Пронумеровав, таким образом состояния, получаем однородную поглощающую цепь Маркова. Можно построить матрицу Q вероятностей переходов из невозвратных состояний в невозвратные однородной поглощающей цепи Маркова [13].
Найдем фундаментальную матрицу однородной поглощающей цепи Мар кова N — (I — Q)-1, где I — единичная матрица [13]. Щ — это количество единиц времени, которое процесс находится в состоянии j, если блуждание началось из состояния г.
Алгоритм решения задачи: построить матрицу Q, вычислить матрицу JV для возможных начальных разбиений памяти к и выбрать оптимальное. Оптимальным будет такое к, которое соответствует максимальному среднему времени. Вычислим оптимальное среднее время для каждого из трех случаев: когда из точки к растет первый стек, второй и третий.
Была написана программа, которая реализует данный алгоритм, результаты вычислений представлены в Таблицах 1.1 и 1.2.
Из результатов, представленных в Таблицах 1.1 и 1.2 видно, что: если вероятности включения и исключения у всех стеков равны, за исключением одного, у которого вероятность включения больше, то среднее время больше в том случае, если этот стек не растет из точки к; если вероятности включения и исключения у всех стеков равны, за исключением одного, у которого вероятность исключения больше, то среднее время больше в том случае, если этот стек не растет из точки к: если у двух стеков вероятности включения равны нулю, а все остальные вероятности равны, то среднее время работы больше в том случае, если один из этих стеков растет из точки к. Например, динамическая память (куча) часто реализуется так, что ее верхняя граница может только возрастать [14]. На практике также часто используются другие виды динамических таблиц, которые могут только возрастать. если одна из вероятностей исключения равна нулю, а все остальные вероятности равны, то в этом случае среднее время блуждания больше в том случае, если этот стек растет из точки к.
Связанное представление четырех стеков в памяти одного уровня
Определим оптимальный размер страницы. Пусть размер страницы х единиц памяти. Тогда, количество страниц . Обозначим через М{х) количество единиц памяти, которое тратиться непосредственно под данные. Будем считать, что М(х) = т — — 2 -. Здесь единиц памяти тратятся на связи. После переполнения одного из стеков, в том случае, когда список свободной памяти уже пуст, работа заканчивается. Предположим, что три другие страницы, с которыми работали три других стека, заполне-ны не полностью данными, например, наполовину, т.е. 2 единиц.
Выбираем такое значение размера страницы х, чтобы М{х) принимало наибольшее значение. Найдем первую производную и приравняем ее к нулю. М {х) = р — , $ — = 0, т.е. оптимальный размер страницы х — Ар.
Если проверить знак второй производной, то можно убедиться, что эта точка максимума. Мы работаем с дискретной моделью, поэтому необходимо проверить два значения - округлить х до целого снизу и сверху.
В качестве математической модели рассмотрим случайное блуждание в области х\ + Х2 + хз + Xi т : т = т — для случая, когда память используется полностью (максимально), т.е. после переполнения из одного из стеков, когда в списке свободной памяти нет свободных страниц, три другие страницы, с которыми работали три других стека, тоже заполнены полностью, т = т— —3-(х—2) для случая, когда память используется не полно стью (минимально), т.е. после переполнения из одного из стеков, когда в списке свободной памяти нет свободных страниц, три другие страни цы, с которыми работали три других стека, заполнены минимально, в них содержится только по одной единице данных. Пронумеруем состояния также, как и в задаче о связанном представлении четырех стеков.
Построим матрицу вероятностей переходов из невозвратных состояний в невозвратные однородной поглощающей цепи Маркова. Матрица Q для случая страничной организации памяти будет иметь такую же структуру, как для случая связанной организации памяти, за исключением размерности, меньшей в х раз. Найдем фундаментальную матрицу N. Вычислим две оценки для среднего времени (максимальную и минимальную), обозначим ИХ max и -l-min Была написана программа, которая реализует данный алгоритм, результаты представлены в Таблицах 2.2 и 2.3. Условные обозначения в Таблицах 2.2, 2.3: Tmin — минимальная оценка для среднего времени в случае страничного представления четырех стеков в памяти одного уровня, т.е. х\ + х2 + хг т- -2 (х-2); Ттах — максимальная оценка для среднего времени в случае страничного представления четырех стеков в памяти одного уровня, т.е. Хі + х2 + яз гп
Из результатов, представленных в Таблицах 2.1, 2.2 и 2.3 видно, что: страничное представление в случае т = 6, х = 2 совпадает со связанным представлением. среднее время в случае связанного представления четырех стеков для т — 12, х — 3 находится между минимальной и максимальной оценками для среднего времени в случае страничного представления. начиная с некоторого номера т минимальная оценка для среднего времени в случае страничного представления будет лучше, чем среднее время в случае связного представления четырех стеков.
Проверим это: m - - 3 (ж - 2) m - у, х = J f = т -3\/б т — 2v/m + 12 0. Решив это неравенство, получаем: т С (—oo,6)U(24,+oo), т.е. начиная с х = уЦ ( ж — 4 ) и больших, минимальная оценка для среднего времени в случае страничного пред
Последовательное представление
Пусть в каждый момент времени могут происходить параллельные включения или параллельные исключения в три стека в памяти одного уровня.
Рассмотрим последовательное, связанное и страничное представление. Выясним в предположении, что известны некоторые вероятностные характеристики стеков, какой из методов эффективнее с точки зрения среднего времени работы до переполнения памяти.
В качестве моделей предложены случайные блуждания по целочисленной решетке в различных областях трехмерного пространства. Пусть в памяти объема т 0 условных единнц расположены три параллельных стека, вероятностные характеристики которых следующие: Pi — вероятность включения в стек с номером і, где і — 1,2,3; Яі — вероятность исключения из стека с номером і, где г = 1,2,3; pij — вероятность одновременного включения в два стеки с номерами inj, где i,j = 1,2,3,1 ф І; щ — вероятность одновременного исключения из двух стеков с номерами і и j, где i, j = 1,2,3, і ф j; Рі23 — вероятность включения в три стека одновременно; 7t23 — вероятность исключения из трех стеков с одновременно. Исключение из пустого стека не вызывает ошибку и означает остановку на месте. Р\ +Р2 +Рг + Ч\ + й + Ь +Pi2 -VP2Z Л- р\г + Яп + фи + діз +і2з + 7ш = 1-Текущие длины стеков обозначим через Xi, #2, 23
Рассмотрим три стека, расположенных последовательно в памяти объемом т единиц. Двум стекам, растущим навстречу друг другу, отведено s единиц памяти, а третьему стеку — т — $ единиц (См. Рис. 3.1).
Для начала рассмотрим более простой случай, когда возможны только включения в стеки. Будем считать, что в каждый момент времени могут произойти следующие события: с вероятностью ро все стеки остаются на месте, с вероятностью pi произойдет включение только в стек с номером і, где 1 = 1,2,3, с вероятностью р\2 произойдет операция параллельного включения в стеки 1 и 2, с вероятностью різ произойдет операция параллельного включения в стеки 1 и 3, с вероятностью Р2з произойдет операция параллельного включения в стеки 2 и 3, с вероятностью рі2з произойдет операция параллельного включения во все три стека.
Задача заключается в том, чтобы разбить память на две части так, чтобы среднее время работы со стеками было бы максимальным, т.е. необходимо определить оптимальное значение s. Также необходимо выяснить, какой из трех стеков следует расположить отдельно в т — s единиц памяти.
Вероятности переходов зависят от того, какой из трех стеков расположен отдельно.
Пусть первый и второй стеки объединены в пару, а третий стек расположен отдельно. Введем обозначения: х = Х\ + х%у = x$,r = po,Pi = Pi +Р2,Р2 = Р-І,РЗ = РіЗ + Р23,Р4 = Pl2,Pb = РШ Тогда в качестве математической модели удобно рассмотреть двумерное случайное блуждание внутри прямоугольника: х — 0, у — 0, х s + 1, у т s + 1. Вероятность перехода из точки (х, у) в точку (х, у) равна г, из точки {х, у) в точку (х + \,у) равна pi, в точку (х, у + 1) равна р2, в точку (х+Х,у + 1) равнарз, в точку (ж+ 2,у) равнар4, в точку {х + 2,у-\-\) равна р5 (См. Рис. 3.2).
Случай, когда длина информационной части имеет произвольный размер
Мы рассмотрели последовательное и связанное представление трех стеков в случае, когда размер информационной части равен единице. Теперь рассмотрим случай, когда информационная часть имеет произвольный раз 122 мер I 1.
В случае последовательного представление трех стеков размер памяти т должен быть кратен /. Для связанного представления размер памяти т должен быть кратен 1 + 1.
Воспользуемся результатами, полученными выше для последовательного и связанного представления, и вычислим среднее время блуждания.
Результаты сравнения среднего времени для этих двух способов представлены в Таблицах 3.39-3.40.
В случае страничного представления память разделена на страницы одинакового размера. На связь тратится один элемент каждой страницы, поэтому потери на связи в случае страничного представления стеков будут меньше, чем в случае связанного представления.
Предполагается, что существует механизм работы со списком свободных страниц, который позволяет при заполнении страницы предоставить стеку новую страницу. При освобождении страницы, она возвращается в список свободных страниц.
Рассмотрим три стека, расположенных связанно в страничной памяти размером т единиц (См. Рис. 3.9).
Пусть размер страницы х единиц памяти. Оптимальный размер страницы х = у/т (См. раздел 3.1.3).
В качестве математической модели рассмотрим случайное блуждание в пирамиде: Х\ + Х2 + х$ пг . т = т — — для случая, когда память используется максимально, т.е. после переполнения из одного из стеков, когда в списке свободной памяти нет свободных страниц, две другие страницы, с которыми работали два других стека, тоже заполнены полностью, m = m — j — 2 (a: - 2) для случая, когда память используется минимально, т.е. после переполнения из одного из стеков, когда в списке свободной памяти нет свободных страниц, две другие страницы, с которыми работали два других стека, заполнены минимально, в них содержится только по одной единице данных (См. Рис. 3.10).
Пронумеруем состояния также, как и в задаче о связанном представлении (по плоскостям пирамиды). Построим матрицу вероятностей переходов из невозвратных состояний в невозвратные однородной поглощающей цепи Маркова. Матрица Q для случая страничной организации памяти будет иметь такую же структуру, как для случая связанной организации памяти, за исключением размерности, которая будет в х раз меньше. Построим фундаментальную матрицу JV. Вычислим две оценки для среднего времени, максимальную и минимальную, обозначим их Ттах и Тт{п.
Была написана программа, которая реализует данный алгоритм, результаты представлены в Таблицах 3.29-3.38.
Условные обозначения в Таблицах 3.29-3.38: W\ — среднее время в случае последовательного представления трех стеков, когда первый и второй стек объединены в пару, а третий стек расположен отдельно; W2 — среднее время в случае последовательного представления трех стеков, когда первый и третий стек объединены в пару, а второй стек расположен отдельно; Wz — среднее время в случае последовательного представления трех стеков, когда второй и третий стек объединены в пару, а первый стек расположен отдельно Wi — среднее время в случае связанного представления трех стеков; W$ — среднее время в случае страничного представления трех стеков.
