Моделирование телефонной станции

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

     СМО характеризуется определенной структурой. Задача формирования структуры разбивается на три подзадачи:

• определение совокупности серверов;
• установление порядка их расположения;
• определение функциональных связей между ними.

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

     Рис. 1. Общая схема  СМО 

     Исходя  из характера входного потока, выделяются следующие два типа СМО: система с отказами и система с ожиданием.

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

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

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

 

     Рис. 2. Схематическое  изображение СМО  с ожиданием

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

     Сеть  массового обслуживания представляет собой множество взаимосвязанных  систем массового обслуживания (рис. 3):

 

     Рис. 3. Пример сети массового  обслуживания 

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

     Потоковые процессы обладают определенным набором  свойств, имеющих специальные обозначения, предложенные Кендаллом. Свойства записываются в виде кода, имеющего форму A|B|m|R, где  А и В – это буквенные  символы, а m – целочисленная константа. С помощью А и В указывается вид закона распределения вероятностей случайных величин – интервала между поступлением двух последовательных заявок и времени обслуживания, соответственно. Константа m показывает, сколько в СМО насчитывается параллельно расположенных идентичных серверов ( ), или, проще говоря, – числу каналов. R – предельное число заявок в очереди или в системе. Если R -> infinity, то четвертую позицию принято опускать. Возможно наличие пятого символа обозначающего порядок отбора (приоритета) требований.

     Ниже  приведены стандартные обозначения, используемые на позициях АВ:

     M – пуассоновский закон распределения  (то есть отрицательная экспоненциальная  функция распределения указанных  выше случайных величин). Такое  обозначение произошло путем выделения первой буквы из термина «memoryless», характеризующего процессы без памяти;

     D – интервалы времени между  последовательными событиями детерминированы («deterministic»). Распределение регулярного потока, когда плотность вероятностей интервалов вырождается в дельта-функцию: 

     

; 

      : 

     

       – гамма-распределение;

       – гиперэкспоненциальное  распределение с k составляющими: 

     

; 

     G – закон распределения неизвестен или может быть любым («general»).

     Те, кто впервые приступил к изучению теории очередей, могут задаться вопросом, почему только пять законов распределения  вероятностей из значительно большего числа всех известных распределений  имеют общепринятое обозначение. Дело в том, что только эти пять законов распределения являются широко распространенными и приносят существенную пользу при практической интерпретации полученных результатов математического и статистического анализа. Поэтому, если в модели используются различные законы распределения помимо указанных выше, то в обозначениях указывают категорию G (general).

     В качестве вывода приведем пример записи одного из видов СМО: M|G|1|infinity. Такая запись означает, что рассматривается одноканальная СМО с простейшим входным потоком, произвольным распределением времени обслуживания и неограниченной очередью. Длина очереди – количество требований, ожидающих сигнал на обслуживание, или число мест. В литературе также встречается обозначение GI, соответствующее рекуррентному распределению, при котором длительности интервалов между последовательными событиями потока статистически независимы и имеют одинаковое распределение.

     Когда заявки порождаются ограниченным числом источников, при этом каждый источник порождает только одну заявку, и  не генерирует новые заявки при условии нахождения заявки в СМО, используется обозначение  A|B|m|R|N. N – количество источников, A – закон, порождающий заявки входного потока СМО, B – распределение времени обслуживания, m – число серверов (приборов) обслуживания, R – допустимая длина очереди. Поток называется рекуррентным, если он может быть задан функциями распределения , и , где , – интервал между двумя последовательными заявками, при этом .

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

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

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

• FIFO или FCFS – «the first-in, first-out» и «first come, first served» соответственно – соответствует ситуации, когда заявки обслуживаются по мере их поступления, и большая приоритетность отводится ранее поступившей заявке;
• LIFO («last in, first out») или LCFS («last come, first served») – указывает на ситуацию, в которой последняя заявка в очереди автоматически переходит в категорию самой приоритетной заявки, и первой поступает на сервер;
• аббревиатура SIRO («service in random order») соответствует ситуации, когда происходит случайный отбор заявок для обслуживания сервером.

 

• RR (Round Robin) – если обслуживание заявки незавершенно к концу заданного временного периода, заявка отзывается и возвращается обратно в очередь. В дальнейшем она поступает в сервер по принципу FIFO. Процедура повторяется до тех, пока заявка не будет окончательно выполнена;
• PS (Processor Sharing) – все требования обслуживаются одновременно,  и, как следствие, период обслуживания увеличивается;
• IS (Infinite Server) – существует достаточное количество серверов, которое исключает возможность образования очереди.

     По  способу отбора для обслуживания заявок из очереди выделяются две  дополнительные дисциплины очереди:

• с ограниченным временем пребывания заявки в очереди;
• с приоритетами – некоторые из находящихся в очереди заявок имеют право первоочередного обслуживания.

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

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

     

2.   СМО. Классификация

 

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

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

     По приоритету заявок:

• СМО с заявками, имеющими разный приоритет (абсолютный, относительный);
• СМО с заявками, имеющими одинаковый приоритет.

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

     1) с неограниченным временем ожидания (с ожиданием),

     2) с отказами;

     3) смешанного типа.

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

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

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

     В целом, многоканальная СМО   работает по сути как одноканальная, когда все n   каналов работают как  один с дисциплиной взаимопомощи, называемой все  как  один, но с более высокой интенсивностью обслуживания. Граф состояний подобной системы  содержит всего два состояния:  s₀ (s₁)- все n каналов свободны (заняты).

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

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