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

Аксенова Елена Алексеевна

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И ОПТИМАЛЬНЫЕ МЕТОДЫ РЕАЛИЗАЦИИ ДИНАМИЧЕСКИХ СТРУКТУР ДАННЫХ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

□□31Т312Э

Петрозаводск - 2007

003173129

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

Научный руководитель: доктор физико-математических наук,

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

Официальные оппоненты: доктор физико-математических наук,

профессор Граничил Олег Николаевич,

кандидат физико-математических наук, доцент Фомин Анатолий Сергеевич.

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

Защита состоится 2007 г. в . час. на заседании

диссертационного совета Д 212.190.03 при Петрозаводском государственном университете по адресу 185910, Петрозаводск, пр. Ленина, д 33

С диссертацией можно ознакомиться в Научной библиотеке Петрозаводского государственного университета.

Автореферат разослан "..^7." 2007г.

Ученый секретарь диссертационного совета

В.В. Поляков

Общая характеристика работы

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

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

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

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

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

Положения, выносимые на защиту:

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

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

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

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

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

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

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

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

Связь работы с научными программами, темами. Основные результаты диссертации были получены в рамках исследований, выполнявшихся в ходе работы па госбюджетными темами Института прикладных математических исследований Карельского научного центра РАН. Некоторые результаты диссертационной работы вошли в Основные результаты в области естествешхых, технических, гуманитарных и общественных наук РАН за 2004 год. Работа поддержана грантами РФФИ №01-01-0113, №0301-06415 (МАС), №06-01-00303.

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

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

Публикация работ. По теме диссертации опубликованы 9 статей, в том числе 3 статьи в журналах, входящих в список изданий, рекомендованных ВАК, и 8 тезисов докладов

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

Содержание диссертации

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

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

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

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

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

В начальный момент времени вершила стека с некоторыми вероятностями может перейти вправо или влево, затем вероятности переходов изменяются Если стек перешел в состояние хо — 1, то вероятность возврата в состояние хо равна р\, а вероятность перехода в состояние хо — 2 равна qi —1—pi. Если стек перешел в состояние хо + 1, то вероятность возврата в состояние х0 равна ¡>2, а вероятность перехода в состояние хп + 2 равна «2 = 1 ~ Р2-

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

Известны временные характеристики памяти: время доступа к вершине стека в быстрой памяти ¿о, время перемещения одного элемента в быстрой памяти ti, время доступа к памяти второго уровня t2, время обмена одним элементом между уровнями памяти Предполагается, что потери времени при перемещении элементов пропорциональны числу перемещаемых элементов. Определены функции затрат времени.

• f(x) = t0- затраты времени на доступ к вершине стека,

• /(—1) — to ¡-¿з(жо- М) + <о - затраты времени на доступ и перемещение элементов между уровнями памяти при опустошении,

• /(га+1) = í2 + (w+l—xo)f3+íi(^o — l)+ío - затраты времени на доступ и перемещение элементов между уровнями памяти при переполнении.

Для стековой памяти средний коэффициент потерь равен 1 /Т(х0), где Т(хо) - это математическое ожидание числа шагов до перераспределения, если процесс начался в состоянии х0. Среднее время доступа F(xo) вычисляется по формуле:

EV \ 1 \ , ТЫ -1, + , С(хо) - ¿0

FW - ТЫ СЫ + ~ты~ “ 0 + ты ■

где Рх0,-1 — это вероятность попадания из х0 в —1, pXlt,m\ i - это вероятность попадания из х0 в то + 1, С(х0) = pXo-if(-l) + pXo,m+1f(m + 1) -

б

средние затраты времени на перераспределение памяти при переполнении и он}СТОШС1ШИ, Т(ао) - среднее время работы до перераспределения.

Рассмотрена матрица II вероятностей переходов из невозвратных состояний в поглощающие Доказана теорема о структуре матрицы Я.

Среднее время работы до перераспределения памяти Т(хо) вычисляется с помощью фундаментальной матрицы N = (/ - где I - единичная

матрица, <5 - матрица вероятностей переходов из невозвратных состояний в невозвратные. Элемент имеет смысл кол-ва единиц времени, которое процесс находился в состояшш J если блуждашю началось из состояния 1 Вероятности Рх0,-1 и Рх0,т+1 вычисляются с помощью матрицы В = (I — <2)-1 В, — N II Элемент В [г, ]] равен вероятности поглощения в состоянии ], если начальным было состояние г. Для определения оптимального состояния ¿о необходимо перебрать все возможные начальные состоя-пия, вычислить для каждого среднее время доступа и выбрать состояние, которому соответствует мштмалыюе время.

Для реализации алгоритма решения задачи разработана программа для ЭВМ, которая для задашгых вероятностных характеристик и размера памяти генерирует матрицу <5, вычисляет матрицы N и В, вычисляет среднее время доступа -Р(хо) и определяет оптимальное состояние х{). В диссерта-щш приведены результаты численных экспериментов.

При р\ — (>2 — 1/2 в качестве математической модели рассмотрено классическое случайное блуждание. Тогда Рх0,-г = 1 - Рх0,т+1 =

Т(х0) = (.т0 + 1)(гп - т0 + 1). Требуется найти х0, которое мшшмизирует функцию

т.ч„ ^ * , Рхо-Ль + *з(а-о + 1) + ¿о) ,

Ь (х0) — <о Н--------7Г7--------—гг-----V

(хо + 1 )(гп - х0 + 1)

I Рх0,т+1(^2 + ^(т — Хр + 1) + tl(xo — 1) + ¿о) — ¿0

(х0 + 1 )(тп - Хо + 1)

Стштая, что Г(хо) - функция непрерывного аргумента, показано, что оптимальное значечше параметра вычисляется по формуле-

-¿2(т + 2) - t\rn + (тп + 2)%/t2(t2 + tim)

хо =----------------------т-----------------------

tim

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

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

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

Пусть вершина первого стека х\, вершина второго стека х2. В качестве математической модели процесса работы со стеками рассмотрено случайное блуждание по целочисленной решетке в области х\ > 0, х2 > 0, х\ +х2 < т, гдех! = —1,2:2 = — 1. xi +Х2 = m+l,xi+x2 = т+2-поглощающие экраны

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

Для решения задачи необходимо вычислить фундаментальную матрицу N = (/ — Q)-1 Для вычисления среднего времени работы со стеками необходимо найти суммы элементов строк матрицы N. Для того чтобы найти оптимальное состояние so = необходимо из полученных сумм

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

Для реализации алгоритма решения задачи разработана программа для ЭВМ, которая для заданных вероятностных характеристик и размера памяти генерирует матрицу Q, вычисляет матрицу N и определяет оптимальное состояние ¿о -- В диссертации приведены результаты численных

экспериментов.

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

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

Пусть текущие длины очередей Ж] и х2. В связанном способе оргапиза-щш очередь представлена в виде связанного списка, каждый элемент которого состоит из двух единиц памяти, одна из которых используется для хранения шгформации, вторая содержит указатель (связь) на следующий элемент в списке. Предполагается, что то кратно 2 При таком представле-шш очередей всего будет -у элементов. Для хранения указателей используется тг единиц памяти, для хранения информации используется Щ- едишщ памяти В качестве математической модели процесса работы с очередями рассмотрено случайное блуждашто по целочисленной решетке в треугольной области XI > 0, х2 > О, X] + х2 < Щ- + 1, где хг + х2 = тг + 1 - поглощающий экран, попадашю па который характеризуется как переполнение выделенного объема памяти, х\ = — 1 и х2 = — 1— отражающие экраны, попадашю па которые характеризуется как исключите элемента из пустой очереди. Блуждание начинается в тотгкс х\ = х2 = 0 Необходимо найти среднее время блуждания до попадания на поглощающий экран.

Рассмотрен случай, когда в очереди хранятся данные, длина информаций! той части которых равна Ь > 1 едишщ памяти Длина каждого элемента очереди будет Ь + 1, где одна едишща памяти содержит указатель на следующий элемент Предполагается, что то кратно Ь + 1. Количество элементов в этом случае будет т^ру- Для хранения указателей используется едишщ памяти. В качестве математической модели рассмотрено случайное блуждание по целочисленной решетке в треугольной области х\ > О, ж2 > 0, ж-| + х-2 < ттру + 1, где х1 + х2 = 4- 1 — поглощающий экран,

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

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

т — ^ единиц памяти, для хранения информации у каждой страницы используется х — 1 единиц памяти При х — 2 получаем связашюе представление очередей В качестве математической модели процесса работы с очередями рассмотрено случайное блуждание по целочислешюй решетке в треугольной области х\ > О, х2 > 0, х\ +х2 < т — ^ +1, где хг+х2 = т— ^- +1

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

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

В случае страничной организации очередей рассмотрена функция F(x) = т — ^ - 3 ^~-,т > 0, х > 2 - среднее количество единиц памяти, которые заняты для хранения информации при переполнении какой-либо из очередей. Определен оптимальный размер страницы х* = т В качестве оптимального размера страницы рассмотрены целочисленные значения [ж*] и [ж*].

Для решения задачи необходимо вычислить фундаментальную матрицу Ы = (I — С})''1. Для вьгшеления среднего времени работы с очередями необходимо просуммировать элементы матрицы N в строке, которая соответствует процессу блуждания, выходящему из состояния х\ — х2 = 0.

Для страии'шого способа организации вычисляется оценка сверху и оценка снизу для реального среднего времени работы Для оценки сверху рассмотрено блуждашгс в области х\+х2 < т — ^ +1, а для оценки снизу -блуждание в области х\-\-х2 < т — ^ — 3(а; — 2)4-1, где слагаемое 3(ж —2)

- это три страшщы, у которых при переполнении какой-либо из очередей заполнено по одной ячейке

Сравнивая области блуждания для связанного и страничного способов организации, определено, что для размера памяти то е (24, оо) область блуждания в случае связашюго представления всегда меньше, чем область блуждания для оценки снизу в случае страшгшого представления при х = ^. Поэтому для т > 24 в случае связанного представления среднее время работы меньше, чем минимальная оценка среднего времени работы в случае страшгшого представления при х = Также определено, что область блуждания в случае связашюго представления всегда меньше, чем область блуждания для оценки снизу в случае страничного представления

при 2 < х < ^ Поэтому в случае связанного представления среднее время работы меньше, чем минимальная оценка среднего времеш! работы в случае страничного представления при 2 < х <

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

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

В задаче исследуется очередь с двумя приоритетами, расположенная в области памяти размера гп единиц. Такая приоритетная очередь представлена в виде двух ИРО-очсредеи Первой очереди присвоен приоритет 1, второй очереди — приоритет 2 Наивысший приоритет 2 Исключение элемента из очереди происходит по наивысшему приоритету Это означает, что пока вторая ИГО-очередь не пуста, исключение элементов происходит из этой очереди. Как только вторая ИГО-очередь станет пустой, исключите элементов будет происходить из первой ПГО-очереди. При исключении элемента из пустой очереди не происходит завершение работы Заданы вероятностные характеристики очередей. Рассматриваются последовательный, связанный и страничный способы организации ИГО-очередей. Необходимо определить, как распределить память между7 ИГО-очередями в последовательном способе, и какой из способов организации очередей является оптимальным. В качестве критерия оптимальности рассматривается максимальное среднее время работы с приоритетной очередью до перепол-неиия выделенного объема памяти.

Пусть текущею длины ИГО-очередей хх и х2 В последовательном способе оргаиизащш каждой ПГО-очереди выделено некоторое количество единиц памяти из данных т единиц. Пусть в - количество едшпщ памяти, выделенных первой ПГО-очереди, тогда (т — з) — количество единиц памяти, выделенных второй ПГО-очереди В качестве математической модели процесса работы с приоритетной очередью рассмотрено случайное блуждание по целочислишой решетке в двухмерном пространстве 0 < х\ < в + 1,

О < Х2 < т — 6 + 1, где х\ — в + 1, Х2 = гп — ь + 1 - поглощающие экраны, попадание на которые характеризуется как переполнение одной из ИГО-очередей, ( — 1,0) и (0,-1) - отражающие точки, тк только в состоянии ■¿'1 — Х2 — 0 возможно исключение из пустой очереди Исключение элементов из первой ПГО-очереди может происходить только при х2 — 0. Блуждание начинается в точке х\ = Х2 — 0. Необходимо определить та-

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

Рассмотрен случай, когда в очереди хранятся данные, длина информационной части которых равна Ь > 1 единиц памяти Предполагается, что та кратно Ь. Количество элементов равно В качестве математической модели рассмотрено случайное блуждание по целочислешюй решетке в двухмерном пространстве 0 < х\ < а + 1, 0 < ж2 < ^ — я +1, где х\ = ,5 + 1, хъ — ^ — з + Х- поглощающие экраны, (-1,0) и (0, -1) - отражающие точки Блуждание начинается в точке Х] = ж2 = 0 Необходимо определить такое значение 0 < .ч < у-, чтобы среднее время блуждания до попадания на поглощающие экраны было максимально.

В связанном способе организации ИРО-очередь представлена в виде связашюго списка элементов. Предполагается, что т кратно 2. Количество элементов равно Щ. В качестве математической модели процесса работы с приоритетной очередью рассмотрено случайное блуждание по цаточисленной решетке в треугольной области х\ > 0, ж2 > 0, жх + ж2 < у + 1, где Х1 + х2 = -у +1 - поглощающий экран, попадание на который характеризуется как переполнение выделенного объема памяти, (—1,0)и(0,— 1) — отражающие ТОЧКИ, Т.К. ТОЛЬКО В СОСТОЯ!ШИ Х\ = Х2 — 0 возможно исключение из пустой очереди Исключение элементов из первой ИРО-очереди может происходить только при ж2 = 0. Блуждадше начинается в точке х\ — ж:2 — 0. Необходимо найти среднее время блуждания до попадания на поглощающий экран.

Рассмотрен случай, когда в очереди хранятся данные, длина информационной части которых равна Ь > 1 единиц памяти. Длина каждого элемента очереди будет Ь + 1, где одна единица памяти содержит указатель на следующий элемент. Предполагается, что та кратно Ь + 1. Количество элементов в этом случае будет Для хранения указателей используется 2^; единиц памяти В качестве математической модели рассмотрено случайное блуждание по целочислешюй решетке в треугольной области х,\ > 0, х2 > 0,Х1+х2 < -££1+1, где Ж1+Х2 — +1 - поглощающий экран, (—1,0)

и (0, —1) - отражающие точки. Блуждадше начинается в точке х\ = :г2 = 0 Необходимо найти среднее время блуждания до попадания на поглощающий экран.

В страничном способе организации ИРО-очередь представлена в виде связанного списка страниц размера х единиц памяти. Предполагается, что т кратно х Для хранения указателей используется ^ единиц памяти, для хранения информации используется то — ^ единиц памяти Количество страниц равно Для хранения информации у каждой страницы используется х — 1 единиц памяти. При ж = 2 получаем связанное пред-

ставлише очередей. В качестве математической модели процесса работы с приоритетной очередью рассмотрено случайное блуждание по целочисленной решетке в треугольной области х\ > 0, х2 > 0, х\ + х2 < т — — + 1, где xi + Х2 = т — ^ + 1 — поглощающий экран, попадание на который характеризуется как переполнение выделенного объема памяти, (—1,0) и (0,-1) — отражающие точки, т.к. только в состоянии — х2 = 0 возможно исключите из пустой очереди. Исключите элементов из первой FIFO-очереди может происходить только при х2 — Q Блуждание начинается в точке х\ = х2 = 0. Необходимо найти среднее время блуждания до попадания на поглощающий экран.

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

Для случая страничного представления рассмотрена функция F(x) = т - ^7 — 3 > 0,х > 2 - среднее количество еди-

шщ памяти, которые заняты для храпения информации при переполнении какой-либо из FIFO-очередей. Определен оптимальный размер страницы х* = В качестве оптимального размера страницы рассмотрены целочисленные значения и [ж*]

Для решения задачи необходимо вычислить фундаментальную матрицу N = {I-Q)-\B случае последовательной организации приоритетной очереди необходимо построить матрицу Q, вычислить матрицу N для всевозможных значений s. Для вычисления среднего времени работы с приоритетной очередью необходимо просуммировать элементы матрицы N в строке, которая соответствует начальному состоянию х\ = х2 = 0, затем сравнить полученное время для разных значений s и выбрать максимальное. Соответствующее максимальному времени значение s будет оптимальным разбиением памяти для последовательного представления. В случае связашюго и страшгшого представления необходимо построить матрицу Q, вычислить матрицу N и просуммировать элементы матрицы N в строке, которая соответствует начальному состоянию xi = х2 = 0

Для страничного способа оргашгзации вычисляется оценка сверху и оценка С1шзу для реального среднего времени работы Для оценки сверху рассмотрено блуждание в области xi + х2 <т — ^ + 1, а для оценки снизу — блуждание в области хг + х2 < т — — 3(ж — 2) + 1, где слагаемое 3(ж — 2)

— это три страшщы, у которых заполнено по одной ячейке.

Сравнивая области блуждания для связашюго и страничного способов

организации, определено, что для размера памяти т е (24, оо) область блуждания в случае связанного представлетшя всегда меньше, чем область блуждания для оценки снизу в случае страничного представления при х = '/'6{. Поэтому для то > 24 в случае связанного представления среднее время работы меньше, чем минимальная оценка среднего времени работы в случае страничного представления при х = тп. Также определено, что область блуждания в случае связашюго представления всегда меньше, чем область блуждашы для оценки снизу в случае страничного представления при 2 < х < 22 Поэтому в случае связанного представлешш среднее время работы меньше, чем минимальная оценка среднего времени работы в случае страничного представления при 2 < х <

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

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

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

Пусть текущие длины очередей х\, х2 и хз В последовательном способе организации каждой очереди выделено некоторое количество единиц памяти из данных гп единиц. Пусть в - количество единиц памяти, выделенных первой очереди, г - количество единиц памяти, выделенных второй очереди, тогда (то — * — г) - количество единиц памяти, выделешгых третьей очереди. В качестве математической модели процесса работы с очередями рассмотрено случайное блуждание по целочисленной решетке в трехмерном пространстве 0 < Ж1 <5+1, 0 < х2 < г + 1, 0 < хз < те — й — г + 1, где х\ — 6 + 1, Х2 = г + 1, хз = т — а — г + 1 - поглощающие экраны, попадание на которые характеризуется как переполнение одной из очередей, ах1 = —1, х2 — — 1, хз — — 1- отражающие экраны, попадашю на которые

характеризуется как исключение элемента из пустой очереди Блуждаиие начинается в точке .г: = х> — х3 =■ 0 Необходимо определить такие значения 0 < .ч < тп и 0 < г < тп — ч, чтобы среднее время блуждания до попадашы на поглощающие экраны было максимально.

Рассмотрен случай, когда в очереди хранятся данные, длина информационной части которых равна Ь > 1 едшшц памяти. В качестве математической модели рассмотрено случайное блуждание по целочисленной решетке в трехмерном пространстве 0 < хг < я + 1, 0 < х2 < г + 1, О < хз < ^ — в — г + 1, где X] = в + 1, х2 = г + 1, х3 = ~ — в — г + 1

- поглощающие экраны, х\ = —1, х2 = —1,хз = — 1 - отражающие экраны.

Блуждашге нашшается в точке хг — х-2 = х-л — 0 Необходимо определить такие значения 0 < в < ^ и 0 < г < ,1Т°бЬ1 среднее время блуждания

до попадания на поглощающие экраны было максимально.

В связашюм способе организации очередь представлена в виде связанного списка элементов В качестве математической модели процесса работы с очередями рассмотрено случайное, блуждание по целочисленной решетке в трехмерном пространстве х\ > 0, х2 > 0, хз > 0, х\ + х2 + х3 < Щ- + 1, где Х \ + а;9 + х,1 = —■ +1 — поглощающий экран, попадание на который характеризуется как переполнение выделенного объема памяти, х\ — — 1, х2 = — 1 н х3 = —1 — отражающие экраны, попадашш па которые характеризуется как исключение элемента из пустой очереди Блуждание начинается в тотгке х^ = х2 = хз = 0 Необходимо найти среднее время блуждания до попадашш на поглощающий экран

Рассмотрен случай, когда в очереди хранятся дадшые, длина информа-циошюй части которых равна Ь > 1 едшшц памяти В качестве .математической модели рассмотрено случайное блуждание по целочисленной решетке в трехмерном пространстве хг > 0, х2 > 0, х3 > 0, х\ +х2+х3 < +1, где

тс\+ х2 + хз = + 1 - поглощающий экран, х\ = — 1, х2 = — 1 и х3 = —1

- отражающие экраны Блуждашю начинается в точке х1=х2 = х3=0 Необходимо найти среднее время блуждания до попадания на поглощающий экран

В страничном способе организации очередь представлена в виде свя-зашюго списка страниц размера х едшшц памяти. При х = 2 получаем связанное представление очередей В качестве математической модели процесса работы с очередями рассмотрено случайное блуждание по цело-’шелешюй решетке в трехмерном пространстве х\ > 0, х2 > 0, хз > О,

+ х2 + х3 < тп - ^ + 1, где XI 4 х2 + х3 = тп - ^ + 1 - поглощающий экран, попадание на который характеризуется как переполнение выделенного объема памяти, а х\ = — 1, х2 = —1 и хз = — 1 — отражающие экраны, попадашге на которые характеризуется как исключение элемента из пустой

очереди. Блуждание начинается в точке х^ = х2 = х3 = 0. Необходимо найти среднее время блуждания до попадания на поглощающий экрал.

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

Для случая страничного представления рассмотрена функция F(x) = т — — 5 т > 0, х > 2 - среднее количество единиц па-

мяти, которые заняты для хранения информации при переполнении какой-либо из очередей. Определен оптимальный размер страницы х* — -1!1 В качестве оптимального размера страницы рассмотрены целочисленные значения |_£*J и [ж*].

Для решения задачи необходимо вычислить фундаментальную матриц}' N = (I — Q) '. В случае последовательной организации очередей необходимо построить матрицу Q, вычислить матрицу' N для всевозможных значений 6 и г. Для вычисления среднего времени работы очередей необходимо просуммировать элементы матрицы N в строке, которая соответствует начальному состоянию х\ = х2 = х-л — 0, затем сравнить полученное время для разных значений s и z и выбрать максимальное. Соответствующие максимальному времени значения s я z будут оптимальным разбиением памяти. В случае связанной и страничной организации очередей необходимо построить матрицу Q, вычислить матрицу N и просуммировать элементы матрицы N в строке, которая соответствует начальному состоянию х\ — х2 =жз =0. Согласно введенной нумерации это будет последняя строка матрицы N.

Для страничного способа организации трех очередей вьгшсляется оценка Сверху 'I'm а .г и оценка снизу Ттгп для реального среднего времени работы. Для оценки сверху рассмотрено блуждание в области x\-\-x2+xz < т — ^-Н, а для оцетпш снизу-блуждание в области Ж1+Х2+Х3 < т— ^ — 5(х—2) + 1, где слагаемое 5 (х — 2) - это пять страниц, у которых заполнено по одной ячейке.

Сравнивая области блуждания для связанного и страничного способов организации, определено, что для размера памяти т е. (40, оо) область блуждания в случае связанного представления всегда меньше, чем область блуждания для оценки снизу в случае страничного представления при х = уШлк. Поэтому для т > 40 в случае связанного представления среднее время работы меньше, чем минимальная оценка среднего времени работы в случае страничного представления при х = т. Также определено, что

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

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

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

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

Пусть текущие длины очередей а?!, жг и яз. В последовательном способе организации каждой очереди выделено некоторое количество единиц памяти го данных т единиц. Пусть в - количество единиц памяти, выделенных первой очереди, 2 - количество единиц памяти, выделенных второй очереди, тогда {т — ь — г) - количество единиц памяти, выделенных третьей очереди. В качестве математической модели процесса работы с очередями рассмотрено случайное блуждание по целочисленной решетке в трехмерном пространстве 0 < х\ < в +1, 0 < х2 < г + 1, 0 < хз < та — в — 2+1, где х\ = —1, X) = —1, хз — —1 — отражающие экраны, попадание на которые характеризуется как исключение элемента из пустой очереди. Плоскости х\ = я + 1, а>2 = з + 1, х3 = т — в — г +1 соответствуют ситуациям ’’сброса хвоста”. Попадая на эти плоскости, процесс находится на них до тех пор, по-

ка не произойдет исключение элемента из очереди. Блуждалие начинается в точке х\ — Х2 = хз = 0. Необходимо мтшмизировать долю потерянных элементов при переполнении какой-либо из очередей. Другими словами, необходимо определить такие значения 0 < « < т и 0 < г < т - а-, чтобы доля времени, проведенного в состояниях ’’сброса хвоста”, была минимальной.

Рассмотрен случай, когда в очереди хранятся данные, длина информационной части которых равна Ь > 1 едшшц памяти В качестве математической модели в этом случае рассмотрено случайное блуждание по целочисленной решетке в трехмерном пространстве 0 < яч < .» + 1, 0 < хо <2+1, 0<жз<т;-в-2 + 1, Плоскости х\—э + 1, Х2 — г + 1, хз = 1^—в — г + 1 соответствуют ситуациям ’’сброса хвоста”. Блуждание начинается в точке х\ = Х2 = хз = 0 Необходимо определить такие значения 0 < * < ^ и

0 < г < ^ — д, чтобы доля времени, проведенного в состоящих ’’сброса хвоста”, была минимальной

В связанном способе организации очередь представлена в виде связашю-го списка элементов В качестве математической модели рассмотрено случайное блуждание по целочисленной решетке в трехмерном пространстве х\ > 0, Х2 > 0, хз > 0, х\ +х2 + хз < +1, где х\ = -1, ж2 = -1, ж3 = —1 -

отражающие экраны, попадание на которые характеризуется как исключение элемента из пустой очереди. Плоскость Х1+Х2+Х3 = тг+1 соответствует ситуациям ’’сброса хвоста” Попадая на эту плоскость, процесс находится на ней до тех пор, пока не произойдет исключение элемента из какой-нибудь очереди. Блуждание начинается в точке х\ — х2 = хз — 0. Необходимо найти долю времени, проведенного в состояниях ’’сброса хвоста”.

Рассмотрен случай, когда в очереди хранятся данные, длина информационной части которых равна Ь > 1 единиц памяти. В качестве математической модели рассмотрено случайное блуждание по целочислешюй решетке в трехмерном пространстве х\ > 0, Х2 > 0, хз > 0, х\ + Х2 +хз < +1, где

х\ — —1,Х2 = —1ихз = —1-отражающиеэкраны. ПлоскостьXI+Х2+Х3 = = +1 соответствует ситуациям ’’сброса хвоста”. Блуждание начинается

в точке х\ — Х2 — х'з = 0. Необходимо найти долю времени, проведенного в состояниях ’’сброса хвоста”, и сравнить с долей времени в случае последовательного представления, когда длила информационной части равна Ь.

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

Для вычисления доли времени, проведенного в состояниях ’’сброса хво-

ста”, необходимо решить уравнение а Р = а, где а - предельный вектор для рассматриваемой марковской цепи. По закону больших чисел для регулярной цепи Маркова элемент вектора аг - это доля времени, которое процесс проводит в состояшш г Для вычисления доли времени нужно просуммировать элементы вектора а, соответствующие состояниям "сброса хвоста” В последовательном представлении при введенной нумерации это последшю (s + z + 2)(ш — s — 2 + l) + (s + 1 )(z + 1) элементов вектора а, в связанном представлешш при введешюй нумерации это последние (га+1Н”+2) элементов вектора а В последовательном представлении необходимо вычислить долю времеш! для разных значений s и г, затем выбрать мшшмальную. Соответствующие минимальной доле времени значения s и z будут оптимальным разбиением памяти.

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

Список опубликованных работ по теме диссертации

Статьи

1 Аксенова Е А , Волкова О.В., Лазутина А.А, Соколов A.B. Методы оптимального управлешн стеками в двухуровневой памяти.// Труды Института прикладных математических исследовании «Методы математического моделировал шя и информационные технологии», КарНЦ РАН, Петрозаводск, вып.З, 2002, с 127-152 (вклад диссертанта 25 %)

2 Аксенова Е А., Лазутина А.А , Соколов А.В , Тарасюк A.B. Об оптимальном управлешш динамическими структурами данных.// Труды V международной конференции «Дискретные модели в теории управляющих систем» Изд отдел ВМК МГУ им. М.В. Ломоносова, 2003, с. 5-6. (вклад диссертанта 25 %)

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

4 Аксенова Е А., Лазутина A.A., Соколов A.B. Исследование немарковской модели управления стеком в двухуровневой памяти // Программирование, №1, 2004, с 37-46. (вклад диссертанта 33 %)

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

6. Аксенова Е.А. Исследование методов представления трех очередей в памяти одного уровня.// Труды Института прикладных математических исследований «Методы математического моделирования и информационные технологии», КарНЦ РАН, Петрозаводск, вып.6, 2005, с. 163-186.

7 Аксенова Е.А., Соколов A.B., Тарасюк А.В. Об оптимальном управлении двумя FIFO-очередями в конечной области памяти.// Системы управления и информационные технологии, №3, 2006, с 62-68. (вклад диссертанта 33 %)

8. Аксенова Е А. Оптимальное управление FIFO-очередями на бесконечном времени.// Межвуз. сб «Стохастическая оптимизация в шг-форматике». Изд-во С.-Петербургского университета, вып 2,2006, с.71-76

9. Аксенова Е.А., Соколов A.B. Оптимальное управление двумя параллельными стеками в двухуровневой памяти.// Дискретная математика, №1, 2007, с.67-75 (вклад диссертанта 66 %)

Тезисы докладов

1. Sokolov А V., Aksenova Е.А., Lazutina А A., Taiasyuk A.V Mathematical models of dynamic data structure.// V international congress on mathematical modeling. Book of abstract, vol. II, JINR, Dubna 2002, p. 127. (вклад диссертанта 25 %)

2. Аксенова E.A., Лазутина A.A., Соколов A.B. Об оптимальном распределении памяти для стеков.// Обозрение прикладной и промышленной математики, т 10, вып.1, 2003, с.86—87. (вклад диссертанта 33 %)

3. Аксенова Е.А , Лазутина А.А , Соколов А В Об оптимальных методах представления динамических структур данных.// Обозрение прикладной и промышленной математики, т 10, выл 2, 2003, с 375376. (вклад диссертанта 33 %)

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

5 Аксенова Е.А., Соколов А.В Об оптимальном управлении двумя FIFO-очередями // Материалы УШ Международного семинара «Дискретная математика и ее приложения». М.- Изд-во механико-математического факультета МГУ, 2004, с.167-169. (вклад диссертанта 50 %)

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

7. Sokolov А V., Aksenova Е.А Lazutina А.А, Tarasyuk A.V. Probability models and optimal algorithms of dynamic data structure control./'/ Extended abstracts, PTAP, Petrozavodsk, 2006, pp 57-58. (вклад диссертанта 25 %)

8. Аксенова Е.А Некоторые задатш управления динамическими структурами данных.// Материалы IX Международного семинара «Дискретная математика и се приложения» М.: Изд-во механико-матема-тшгсекого факультета МГУ, 2007, с 201-203.

Изд лиц № 00041 от 30 08 99 Формат 60x84 '/|6 Бумага офсетная Гарнитура «Times»

Уч-изд л 1,0 Уел печ л 1,3 Подписано в печать 02 10 07 Тираж 100 экз Изд №51 Заказ № 686

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

Введение

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

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

1.1.1 Постановка задачи.

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

1.1.3 Решение задачи и результаты численных экспериментов

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

1.2.1 Постановка задачи.

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

1.2.3 Решение задачи и результаты численных экспериментов

2 Оптимальное управление двумя FIFO-очередями в памяти одного уровня

2.1 Постановка задачи.

2.2 Связанное представление двух очередей.

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

2.3 Страничное представление двух очередей.

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

2.3.2 Оптимальный размер страницы.

2.4 Решение задачи.

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

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

3.1 Постановка задачи.

3.2 Последовательное представление.

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

3.3 Связанное представление.

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

3.4 Страничное представление

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

3.5 Решение задачи.

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

4 Оптимальное управление тремя FIFO-очередями в памяти одного уровня

4.1 Постановка задачи.

4.2 Последовательное представление трех очередей

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

4.3 Связанное представление трех очередей.

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

4.4 Страничное представление трех очередей.

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

4.4.2 Оптимальный размер страницы.

4.5 Решение задачи.

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

5 Оптимальное управление тремя FIFO-очередями на бесконечном времени

5.1 Постановка задачи.

5.2 Последовательное представление трех очередей

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

5.3 Связанное представление трех очередей.

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

5.4 Решение задачи и результаты численных экспериментов

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

Стеком LIFO (Last In First Out) называется линейный список, в котором все включения и исключения (и обычно всякий доступ) происходят на одном конце, который называется вершиной стека. Другой по отношению к вершине конец стека называется началом стека. Очередью FIFO (First In First Out) называется линейный список, в котором все включения происходят на одном конце (конец очереди), а все исключения (и обычно всякий доступ) происходят на другом конце (начало очереди) [25]. Под линейным списком будем понимать множество узлов, структурные свойства которого ограничиваются лишь их линейным (одномерным) относительным положением.

Понятие стека широко используется при разработке программного и аппаратного обеспечения. Стеки используются в алгоритмах синтаксического разбора [16, 34, 35], для анализа скобочной структуры текста и вычисления выражений [29], в алгоритмах машинной графики [39], в алгоритмах поиска на графах [25, 30], в алгоритмах сортировки [26, 40], в системе управления процессами [33, 38, 45], при разработке архитектуры [17, 22, 23, 27, 33, 44]. При разработке RISC процессоров для работы со скалярными аргументами и локальными переменными функций организуются перекрывающиеся окна регистров постоянного или переменного размеров [47, 51]. В этом случае получаем один стек с элементами типа "окно" в главной памяти, у которого несколько верхних элементов образуют циклический стек на регистрах. В архитектуре Intel Itanium [60] у каждой процедуры есть регистровый стек с элементами переменного размера для хранения параметров. Выходные параметры одной процедуры являются входными параметрами другой. В процессорах Intel, Motorola и др. стек наращивается в сторону уменьшающихся значений адресов памяти. Это означает, что указателю позиции вершины того или иного стека первоначально присваивается значение самого старшего адреса области памяти, предоставляемой для организации данного стека [36, 37].

При переполнении или опустошении регистровой вершины стека на практике применяют несколько программных и аппаратных методов, которые имеют преимущества по сравнению с универсальными алгоритмами замещения кэш-памяти [51, 59]:

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

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

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

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

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

Во всех этих методах вершина стека является продолжением стека, находящегося в памяти второго уровня.

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

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

Если рассмотреть несколько стеков (процессов) и общий ресурс быстрой памяти, то можно показать, что встречное расположение стеков в виде пар стеков, растущих навстречу друг другу, лучше раздельного, если в качестве критерия оптимальности выбрано среднее время работы стеков до переполнения [42, 58]. Задача построения математической модели такого способа распределения памяти была поставлена Д. Кнутом [25]. Исследовалось поведение двух стеков, расположенных в памяти объема т и растущих навстречу друг другу. В этом случае место встречи стеков можно рассматривать как случайную величину. Известно, что на каждом шаге с вероятностью р может произойти исключение элемента из одного из стеков, с вероятностью 1 — р может произойти включение информации в один из стеков. Пусть М{т,р) математическое ожидание случайной величины max(ki, £2), где ki и длины стеков при встрече. Задача состоит в том, чтобы установить вид функции М(т,р). В [41] предложен алгоритм вычисления М(т,р) для конечных значений т. Для решения задачи использовалась теория поглощающих цепей Маркова [24]. В [61] решалась задача исследования М(т,р) при т —* оо для 0.25 < р < 0.5. В [49, 52, 53] исследовалось асимптотическое поведение размеров стеков при переполнении и времени работы до переполнения памяти для 0 < р < 0.25. В [54] решалась задача для случая, когда вероятности включения и исключения информации зависят от размеров стеков. В [42, 55, 58] предложены марковские модели для решения задач управления несколькими стеками. В [14] исследовалась задача управления двумя параллельными стеками в двухуровневой памяти.

FIFO-очереди используются в компьютерных сетях, операционных системах, графических системах, устройствах промышленной автоматики. Ряд американских фирм выпускает микросхемы, реализующие работу с несколькими FIFO-очередями (IDT Inc. [32], Cypress, AverLogic Technologies). В диссертационной работе рассмотрены некоторые задачи оптимального представления нескольких FIFO-очередей в памяти одного уровня. Оптимальность понимается либо в смысле максимизации среднего времени работы до переполнения какой-либо очереди, либо в смысле минимизации доли потерянных элементов при бесконечном времени работы очередей. Первый критерий разумно применять в программных системах, когда переполнение какой-либо очереди может привести к остановке работы программы. Второй критерий уместен, например, в сетевых маршрутизаторах, когда пакеты, которые помещаются в переполненную очередь, просто теряются ("сброс хвоста") [18]. Потери пакетов приводят к нежелательному результату, поэтому число таких ситуаций необходимо свести к минимуму.

Для организации FIFO-очередей в памяти компьютера применяются два принципиально разных способа представления: последовательный и связанный [25]. Известны указатели на конец и начало очереди. В последовательном способе организации каждой очереди отводится определенная область памяти. При такой организации часто очередь зациклена, т.е. при достижении концом очереди конечной границы выделенной области памяти следующие включения элементов будут происходить с начальной границы, если есть свободная память. В связанном способе организации очередь представлена в виде связанного списка, каждый элемент которого состоит из двух единиц памяти, одна из которых используется для хранения информации, другая для хранения указателя на следующий элемент. В некоторых приложениях, например, в ряде версий операционных систем, для сетевых маршрутизаторов применяется некий промежуточный способ, когда очереди представлены в виде связанного списка буферов (страниц) одинаковой длины. В связанном представлении затраты памяти на хранение связей самые большие, в последовательном представлении таких затрат нет, но есть потери памяти за счет того, что при переполнении одной из очередей другая очередь заполнена не до конца. В страничном представлении есть затраты памяти первого и второго рода.

В работах [12, 43] рассматривались задачи оптимального управления двумя FIFO-очередями.

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

Существуют различные способы реализации очередей с приоритетами. Одним из часто используемых способов является представление N - приоритетной очереди в виде N FIFO-очередей. Приложениями очередей по приоритетам являются системы моделирования, в рамках которых ключи могут соответствовать моментам возникновения событий, что обеспечивает возможность их обработки в хронологическом порядке, системы планирования заданий в компьютерных системах, где ключи могут соответствовать приоритетам, указывающим, какой из пользователей должен быть обслужен первым. Метод приоритетной очереди достаточно широко используется, например, как один из аппаратно-независимых методов управления перегрузками в технологии QoS. В операционной системе Cisco IOS реализация приоритетной очереди содержит четыре различные подочереди: high, medium, normal и low priority [18].

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

Основными результатами диссертации являются:

Заключение

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

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

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

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

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

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

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

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

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

7. Аксенова Е.А., Соколов А.В., Тарасюк А.В. Об оптимальном управлении двумя FIFO-очередями в конечной области памяти.// Системы управления и информационные технологии, №3, 2006, с.62-68.

8. Аксенова Е.А. Оптимальное управление FIFO-очередями на бесконечном времени.// Межвуз. сб. «Стохастическая оптимизация в информатике». Изд-во С.-Петербургского университета, вып.2, 2006, с.71-76.

9. Аксенова Е.А., Соколов А.В. Оптимальное управление двумя параллельными стеками в двухуровневой памяти.// Дискретная математика, М, 2007, с.67-75.

10. Аксенова Е.А. Некоторые задачи управления динамическими структурами данных.// Материалы IX Международного семинара «Дискретная математика и ее приложения». М.: Изд-во механико-математического факультета МГУ, 2007, с.201-203.

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

12. Брусенцов Н.П. Микрокомпьютеры. М.: Наука. Гл.ред.физ.-мат.лит., 1985.-208 с.

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

14. Вавилов В.В., Устинов А.В. Многоугольники на решетках. М.:МЦНМО, 2006.-72с.

15. Гантмахер Ф.Р. Теория матриц. М.:Наука, 1967.-576с.

16. Гудрич М. Т., Тамассия Р. Структуры данных и алгоритмы в Java. Пер. с англ. Чернухо A.M. М.:Новое знание, 2003.-671с.

17. Исада X. Программирование для микрокомпьютеров: Пер с яп. М.: Мир, 1988.-224 с.

18. Карцев М.А. Архитектура цифровых вычислительных машин. Главная редакция физико-математической литературы, М.: Наука, 1978.-296 с.

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

20. Кнут Д. Искусство программирования для ЭВМ. Т.1, М.:Изд-во "Вильяме", 2001.-720с.

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

22. Королев ЯЛ. Архитектура электронных вычислительных машин. М.: Научный мир, 2005.-272 с.

23. Кормен Т., Лейзерсои Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.-960С.

24. Кубенский А.А. Создание и обработка структур данных в примерах на Java. СПб. :БХВ-Петербург, 2001.-336с.

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

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

27. Мамаева Т.Ю. Новые семейства памяти FIFO-TeraSync DDR и Multi-queue. URL:http: / / www.efo.ru / doc/IDT/IDT.pl?179

28. Морис Дж. Вах. Архитектура операционной системы Unix. Ныо-Джерси 1986. URL:http://rsusul.rnd.runet.ru/inix/bach/index.html

29. Опалева Э.А., Самойленко В.П. Языки программирования и методы трансляции. СПб.:БХВ-Петербург,2005.-480с.

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

31. Рафикузаман М. Микропроцессоры и машинное проектирование микропроцессорных систем: В 2-х кн. Кн. 1. Пер. с англ.-М.:Мир, 1988-312с.

32. Рафикузаман М. Микропроцессоры и машинное проектирование микропроцессорных систем: В 2-х кн. Кн. 2. Пер. с англ.-М.:Мир, 1988.-288с.

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

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

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

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

37. Соколов А.В. Математические модели и алгоритмы оптимального управления динамическими структурами данных./ПетрГУ. Петрозаводск, 2002.-216с.

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

39. Смит Б.Э., Джонсон М.Т. Архитектура и программирование микропроцессора INTEL 80386. Пер. с англ. Григорьева B.JI. М.'Конкорд, 1992.-334с.

40. Таненбаум Э. Современные операционные системы. Спб.: Питер, 2002,-1040с.

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

42. RISC: Эффективные архитектуры для СБИС-компьютеров. Электроника СБИС. Проектирование микроструктур./ Катеванис М.Г.Х., Се-куин К.Х., Паттерсон Д.А., Шербурн Р.У. М.:Мир, 1989.

43. Ertl Anton М. Stack caching for interpreters. SIGPLAN '95 Conf. Programm. Lang. Des. and Implem.(PLDI), 15 La Jolla,Calif,June 18-21,1995.

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

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

46. Koopman P. Stack Computers. Ellis Horwood, 1989.

47. URL: http://www.cs.cmu.edu/~koopman/stackcomputers/

48. Louchard G., Schott R. Probabilistic analysis of some distributed algorithms. // Lect. Notes Computer Sci. 1990. №431. p.239-253.

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

50. Maier R. S. Colliding Stacks: A Large Deviations Analysis // Random Structures and Algorithms. 1991. M. p.379-421.

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

52. Sokolov A. V., Aksenova E.A., Lazutina A.A., Tarasyuk A. V. Mathematical models of dynamic data structure. V international congress on mathematical modeling. Book of abstract, vol. II, JINR, Dubna 2002, p. 127.

53. Sokolov A.V., Aksenova E.A., Lazutina A.A., Tarasyuk A.V. Probability models and optimal algorithms of dynamic data structure control. Extended abstracts, PTAP, Petrozavodsk, 2006, p.57-58.

54. Sokolov A. V., Lemetti A.A. On the problem of optimal stack control. Probabilistic methods of discrete mathemetics: Proceedings of the Fifth International Conference. Utrecht, Netherlands: VSP, 2001. P.351-366.

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

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