exam12 1

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

Реферат к лекции 12. Понятия исполнительного устройства и очереди в системе массового обслуживания

Выполнила: Селукова Вера

Проверила: Воронина Анна

Понятие очереди в теории массового обслуживания

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

Система массового обслуживания (СМО) — система, которая производит обслуживание поступающих в нее требований. Обслуживание требований в СМО осуществляется обслуживающими приборами.

Очередь — абстрактный тип данных с дисциплиной доступа к элементам «первый пришел — первый вышел» (FIFO, англ. first in, first out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

Очередь сообщений (или почтовый ящик) — в информатике — программно-инженерный компонент, используемый для межпроцессного или межпотокового взаимодействия внутри одного процесса. Для обмена сообщениями используется очередь.

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

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

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

Элементы системы массового обслуживания:

1. Входной (входящий) поток требований (заявок) на обслуживание;
2. Приборы (каналы) обслуживания;
3. Очередь заявок, ожидающих обслуживания;
4. Выходной (выходящий) поток обслуженных заявок;
5. Поток не обслуженных заявок;
6. Очередь свободных каналов (для многоканальных СМО).

Виды очередей в объектно-ориентированном программировании

1. Односторонняя очередь – это линейный список, в котором все операции вставки выполняются на одном из концов списка, а все операции удаления (и, как правило, операции доступа к данным) – на другом.
2. Двусторонняя очередь (англ. double-ended queue), или дек (англ. deque) — абстрактный тип данных, в котором элементы можно добавлять и удалять как в начало, так и в конец.
3. Очередь с приоритетом (англ. priority queue) — абстрактный тип данных в программировании, поддерживающий две обязательные операции — добавить элемент и извлечь максимум (минимум).

Способы организации очередей в объектно-ориентированном программировании

Первый способ — очередь в виде массива и двух целочисленных переменных start и end.

Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдет новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив, и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов.

Преимущества: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.

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

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

Преимущества: размер очереди ограничен лишь объемом памяти.

Недостатки: сложнее в разработке; требуется больше памяти; при работе с такой очередью память сильнее фрагментируется; работа с очередью несколько медленнее.

Третий способ — реализация на двух стеках.

Стек — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришел — первым вышел»).

Очередь может быть построена из двух стеков S1 и S2 как показано ниже:

Процедура enqueue(x):

S1.push(x)

Функция dequeue():

если S2 пуст:

    если S1 пуст:

        сообщить об ошибке: очередь пуста

    пока S1 не пуст:

        S2.push(S1.pop())

вернуть S2.pop()

Источники

1. Теория массового обслуживания
2. Система массового обслуживания
3. Очередь
4. Очередь сообщений
5. Элементы системы массового обслуживания
6. Теория игр
7. Понятия теории массового обслуживания
8. Понятие о задачах теории массового обслуживания
9. Динамические структуры данных
10. Двухсторонняя очередь
11. Очередь с приоритетом
12. Стек