Алгоритм обслуживания

В понятие алгоритма (организации) обслуживания входят:

1) возможность образования очереди в системе;

2) ограничение на длину очереди (объем накопителя);

3) очередность (дисциплина) обслуживания (т.е. правила, в соответствии с которыми выбирается из очереди требование для обслуживания);

4) правило, в соответствии с которым требования занимают свободные приборы (если их больше одного);

5) некоторые особенности работы обслуживающих приборов (отдыхающие приборы, ненадежные приборы и др.)

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

Системы с ожиданием (или системы с очередью)

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

- обслуживание в прямом порядке FCFS (first - come - first - serve, т.е. первый, поступивший первым, обслуживается);

- обслуживание в обратном порядке LCFS (last - come - first - serve, т.е. последний, поступивший первым, обслуживается);

- обслуживание в случайном порядке RANDOM (с определенной вероятностью выбирается на обслуживание любое из имеющихся в очереди требований);

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

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

Системы с отказами (потерями)

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

Системы с ограниченной очередью

В таких СМО есть и потери требований и ожидание. В такой системе имеется m обслуживающих приборов и n мест для ожидания (буфер, накопитель). Если в момент прихода очередного требования в системе есть хотя бы один свободный прибор или хотя бы одно свободное место для ожидания, то требование либо начинает обслуживаться, либо становится в очередь. В противном случае вновь прибывшее требование покидает систему (получает "отказ"). Из очереди требование выбирается для обслуживания в соответствии с дисциплиной обслуживания. Число n является существенной характеристикой такой системы. Если n = ∞, то получается обычная система с неограниченной очередью. Если n = 0, то получается СМО с отказами.

Открытые и замкнутые системы

Система, в которой входящий поток требований не зависит от процесса ее функционирования, называется открытой (или СМО с бесконечным числом источников). Система называется замкнутой, если входящий поток в неё формируется конечным числом возможных клиентов (источников), например обслуживание К локомотивов в парке депо ремонтной бригадой.

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