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

МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА ИНФОРМАТИКИ И МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ

Отчет о выполнении курсовой работы

Анализ методов управления тремя последовательными

циклическими FIFO очередями в общей памяти

Выполнил: студент 2 курса В.Ю.Талбонен

группа 22203

_________________

подпись

Научный руководитель:

к.т.н., доцент А.В.Соколов

Оценка руководителя _________________

_________________

подпись

Представлена «___»____________200__ г.

____________________ подпись принявшего работу

Итоговая оценка _____________________

____________________

подпись

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

2004

Введение.

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

Проделанная работа.

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

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

Случай работы с тремя очередями.

Постановка и математическая модель задачи.

Пусть в памяти размера m единиц мы работаем с тремя циклическими FIFO очередями. Для последовательного представления каждой очереди выделим некоторое количество единиц памяти из данных m единиц (см. рис.1). Известны некоторые вероятностные характеристики очередей. Пусть p1, p2 и p3 – вероятности включения информации в первую, вторую и третью очереди соответственно, q1, q2 и q3 - вероятности исключения информации в первую, вторую и третью очереди соответственно, r – вероятность операции, не изменяющей длины очереди (например, чтение). Предполагается, что в очередях хранятся данные фиксированного размера. При исключении информации из пустой очереди не происходит завершение работы. Возникает задача: сколько единиц памяти в зависимости от вероятностных характеристик выделить каждой очереди, чтобы среднее время работы до переполнения какой-либо было наибольшим.

Рис. 1

Мы работаем с чистыми FIFO очередями, т.е. доступ возможен только к начальному элементу очереди. Обозначим x1, x2, и x3 – текущие длины очередей, s – количество единиц памяти, выделенных первой очереди, z – количество единиц памяти, выделенных второй очереди, тогда m-s-z – количество единиц памяти, выделенных третьей очереди (см. рис. 1).

В качестве математической модели будем иметь случайное блуждание по целочисленной решетке в трехмерном пространстве (прямоугольный параллелепипед), где 0 ≤ x1 ≤ s+1, 0 ≤ x2 ≤ z+1, 0 ≤ x3 ≤ m-s-z+1, где x1 = s+1, x2 = z+1, x3 = m-s-z+1 – поглощающие экраны, попадание на которые характеризуется как переполнение одной из очередей. x1 = -1, x2 = -1, x3 = -1 – отражающие экраны, попадание на которые характеризуется как исключение элемента из пустой очереди (см. рис.2).

Рис. 2

Блуждание начинается в точке x1 = x2 = x3 = 0. Необходимо определить такие значения s и z, чтобы время блуждания по целочисленной решетке до поглощения на границе было максимально.

Если пронумеровать невозвратные состояния так, как показано на рис. 3 (т.е. сначала состояния, находящиеся в плоскости (x1,x2) при x3 = 0, затем – при x3 = 1 и т.д. поднимаемся по оси x3), то получим конечную, однородную цепь Маркова[3].

Рис. 3.

Геометрически блуждание по решетке можно представить так: включение элемента в первую очередь – сдвиг от начальной точки по оси x1, исключение элемента из первой очереди – сдвиг к начальной точке по оси x1, включение элемента во вторую очередь – сдвиг от начальной точки по оси x2, исключение элемента из второй очереди – сдвиг к начальной точке по оси x2, включение элемента в третью очередь – сдвиг от начальной точки по оси x3, исключение элемента из третьей первой очереди – сдвиг к начальной точке по оси x3.

Количество невозвратных состояний в такой цепи будет (s+1)(z+1)(m-s-z+1)

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

Итоги.

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

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

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

Литература

[1] Кнут Д. Э. Искусство программирования: Основные алгоритмы.- 3-е изд.- М.: Вильямс, 2001.- 720с.: ил. – Парал. тит. англ.

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

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

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

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

[6] Седжвик Р. Фундаментальные алгоритмы на С. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./ Роберт Седжвик.- СПб: ООО «ДиаСофтЮП», 2003.- 672 с.