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

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

Очередь — абстрактный тип данных с дисциплиной доступа к элементам «первый пришел — первый вышел» (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 как показано ниже:

S1.push(x)

если S2 пуст:

    если S1 пуст:

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

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

        S2.push(S1.pop())

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

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