Стохастическая модель многоканальной системы массового обслуживания

 

А:;н и е

ТЕЙИЯ

369571

Союз Советских

Со ивпистимс кмх

Респубвии

К АВТОРСКОМУ СВИДЕТЕЛЬСТВ .

Зависимое от авт. свидетельства №

Заявлено 05, I I.1971 (M 1621479/18-24) с присоединением заявки №

Приоритет

Опубликовано 08.II.1973. Бь ллетень ¹ 10

Дата опубликования описания 4 311.1973

М. Кл. G 061 15/36

Гасударственный квинтет

Савета Министров СССР еа делам изобретений и аткрмтий

Ъ ДЬ, 681.332.519.2 (088.8) Авторы изобретения

В. Н. Четвериков, Э. А. Баканович, A. В. Меньков, Л. А. Соломонов и А. Е. Осьминин

Заявитель

Московское ордена Ленина и ордена Трудового Красного Знамени высшее техническое училище им. Н. Э. Баумана

СТОХАСТИЧЕСКАЯ МОДЕЛЬ МНОГОКАНАЛЬНОЙ СИСТЕМЫ

МАССОВОГО ОБСЛУЖИВАНИЯ

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

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

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

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

На фиг. 1 изображена схема унифицированного блок". моделей обслуживающих Ilðèборов; на фиг. 2 — схема генератора потоков случайных c,I5ûòèé, распределенных в про

10 странстве; на фиг. 3 — стохастнческая модель четырехканальной системы массового обслуживания.

В состав у:сифицированного блока моделей обслуживающих приборов входят вентили 1 и

15 2, импульсные входы которых объединены; статический триггер 3, осуществляющий управление вентилями; вентили 4 и 5, потенциальные входы которых объединены; схема

«ИЛИ» б, служащая для объединения выхо20 дов вентилей 4 и 5; схемы «ИЛИ» 7 и 8, предназначенные для попадания заявки в свободный канал; вентили 9 и 10, запрещающие поступление заявки в занятый канал; модели обслуживающих приборов 11, дающие воз25 можность моделировать процесс обслуживания заявок; схема «ИЛИ» 12, входы которой соединены с моделями обслуживающих приборов ll; схема 18 совпадения, входы которой также соединены с моделями обслуживающих

3о приборов 11; схема 14 отрицания, инверти369571

65 рующая выходной сигнал схемы 13; схема 15 совпадения, которая вместе с логической схемой 13, схемой «ИЛИ» 12 и схемой 14 осуществляет анализ занятости каналов.

Триггер 8, вентили. 1, 2, 4, 5, 9 и 10 и логические схемы «ИЛИ» 6, 7, 8 (см. фиг. 1) образуют логический блок распределения 16.

Логические схемы «ИЛИ» 12 и схемы 18—

15 образуют блок анализа занятости 17, Модели обслуживающих приборов 11, логический блок распределения 16 и блок анализа. занятости 17 (см. фиг. 1) образуют унифицированный блок моделей обслуживающих приборов 18.

В состав генератора потоков случайных событий, распределенных в пространстве, входят датчик потока случайных импульсов 19, н епрерывно генерирующий случайную импульсную последовательность, в которой случайные временные интервалы между соседними сигналами распределены по известному (экспоненциальному) закону; набор генераторов импульсов 20 — генераторов регулярн ых импульсных последовательностей с регулируемыми частотами; группа вентилей 21, импульсные входы которых связаны соответственно с генераторами. импульсов 20; вентиль 22, выделяющий первый после поступившей заявки импульс в случайном потоке, вырабатываемом датчиком потока случайных импульсов 19; статический триггер 28, осуществляющий управление вентилями 21 и вентилем 22, и линия задержки 24, связанная с триггером 23.

Датчик потока случайных импульсов 19, набор генераторов импульсов 20, группа вентилей 21, вентиль 22 и триггер 23 в соединении с линией задержки 24 образуют генератор потоков событий, распределенных в пространстве 25.

В состав стохастической модели четырехканальной системы массового обслуживания (см. фиг. 3) входят логический блок распределения 16, осуществляющий. вероятное распределение заявок между свободными каналами: блок анализа занятости 17, анализирующий состояние каналов; унифицированные блоки моделей обслуживающих приборов 18, позволяющие получить многоканальную структуру модели; генератор потоков событий, распределенных в пространстве 25, осуществляющий вероятностную установку триггеров 3, входящих во все логические блоки распределения 16, в соответствии с переключательной матрицей; генератор входного потока заявок 26, иммитирующий поток заявок с заданными характеристиками; схемы «ИЛИ»

27, служащие для получения многоканальной структуры системы; группа вентилей 28, импульсные входы которых соединены с генератором потоков событий, распределенных в пространстве 25; схемы «ИЛИ» 29, выходы которых соединены с потенциальными входами вентилей 28; схемы «ИЛИ» 30, служащие для объединения выходов вентилей 28; де5

40 шифратор 81, предназначенный для автоматического изменения вероятностей распределения заявок между свободными каналами в зависимости от порядковых номеров свободных каналов.

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

В модели возможны 16 состояний. Для полного представления работы схемы достаточно рассмотреть четыре состояния: свободны все каналы; свободны первый, второй и третий каналы; свободны первый и второй каналы; все каналы заняты.

Под первым каналом понимается модель обслуживающего прибора 11, входящая в состав первого унифицированного блока моделей обслуживающих приборов 18 и соединенная с выходом вентиля 9. Под вторым каналом понимается вторая модель обслуживающего прибора 11, входящая в состав первого унифицированного блока моделей обслуживающих приборов 18. Модель обслуживающего прибора 11, соединенная с вентилем 9 и входящая во второй унифицированный блок моделей обслуживающих приборов 18, называется третьим каналом, а оставшуюся модель обслуживающего прибора 11 — четвертым каналом.

В первом состоянии вентили 9 и 10 унифицированных блоков моделей обслуживающих приборов 18 и логического блока распределения 16 открыты потенциалами, поступающими соответственно с моделей обслуживающих приборов 11 и со схем «ИЛИ» 27, и вентили 4 и 5 тех же блоков закрыты потенциалами, приходящими соответственно с блоков анализа занято-ти 17 (см. фиг. 1) и с блока анализа занятости 17 (см. фиг. 3).

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

«ИЛИ» 27.

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

С нулевого выхода триггера 28 на всю группу вентилей 21 и на вентиль 22 поступает запрещающий потенциал.

B каждой группе вентилей 28, соединенных с одной схемой «ИЛИ» 30, открыт только один вентиль 28, на потенциальный вход которого через схему «ИЛИ» 29 поступает разрешающий потенциал с дешифратора 31.

Поступающий с генератора входного потока заявок 26 импульс, представляющий собой

369571

15

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

При этом вентили 1 открыты, а вентили 2 закрыты.

Тот же импульс с генератора входного потока заявок 2б переводит триггер 23 в нулевое состояние. В результате чего на всю группу вентилей 21 и вентиль 22 поступает разрешающий сигнал. Триггер 23 находится в нулевом состоянии до тех пор, пока на его единичный вход не поступит очередной импульс с датчика потока случайных импульсов 19.

Таким образом, триггер 23 находится в нулевом состоянии случайный отрезок времени

Л1 с момента прихода заявки до момента появления первого после заявки импульса в случайном потоке, поступающем на триггер 23 с датчика потока случайных импульсов 19.

3а этот случайный отрезок времени At, в течение которого все вентили 21 открыты, на импульсный вход каждого вентиля 21 с соответствующего генератора импульсов 20 с вероятностью где i= 1, 2,...

Т, — период регулярного импульсного потока;

Х вЂ” интенсивность пуассоновского потока (датчик потока случайных импульсов 19) может вырабатывать импульсный поток, в котором временные интервалы между соседними импульсами распределены по любому закону.

В предлагаемой модели используется датчик потока случайных импульсов, вырабатывающий импульсный поток, временные интервалы которого распределены по экспоненциальному закону, если поступит хотя бы один импульс регулярной частоты, Эти импульсы регулярных частот пройдут через открытые вентили 21 и поступят на импульсные входы вентилей 28, которые разбиты на три группы.

Так как в каждой группе вентилей 28, объединенных одной схемой «ИЛИ» 30, OTKpbIT всего лишь один, вентиль, то из всего множества импульсов регулярной частоты, поступивших на импульсные входы вентилей 28, каждой группой вентилей 28 будет выделено по одному импульсу регулярнои частоты, Эти три импульса пройдут через схему

«ИЛИ» 30 и перебросят соответствующие триггеры 3 логического блока распределения

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

Обозначим гпуппы вентилей 28, соединенные через схемы «ИЛИ» 29 с логическим .блоком распределения 1б, первым и вторым уни25

55 б0 б5

6 фици ров а иным и блоками моделей обслуживающих приборов 18, соответственно первой, второй и третьей.

Обозначим через PI, вероятность того, что в течение случайного отрезка времени At, при котором открыты вентили 21, на выходе схемы «ИЛИ» 30 l-ой группы вентилей 28 (l=

=1, 2, 3) появится импульс регулярной частоты, прошедший через открытый вентиль 28 этой группы, соответствующий s-му состоянию (s=1, 2, ..., 16) модели (PI равна одному из значений Р;).

Тогда вероятности того, что за случайный отрезок времени Л! триггеры 3 логического блока распределечия 1б первого и второго унивег сальных олоков моделей обслуживающих приборов 18 перебросятся из единичных состояний в нулевые, при которых вентили 2 будут открыты. а вентили 1 закрыты, соответственно равны P«, P». P».

В случае, когда за случайный отрезок впемени Й на импульсные входы вентилей 21, соединенных с открытыми вентилями 28, с соответствующих генераторов импульсов 20 не придет ни одного импульса регулярной частоты, триггеры 3 логического блока распределения 1б первого и второго унифицированных блоков моделей обслуживающих приборов 18 останутся в единичных состояниях. Вероятности таких событий соответственно равны (1 — P«), (1 — Р») и (1 — P»). При этом вентили 1 останутся открытыми, а ве.ттили 2— закрытыми. Перебросы триггеров 3 в логическом блоке распределения 1б в первом и во втором унифицированных блоках моделей обслуживающих приборов 18 за случайный отрезок времени М являются независимыми событиями.

Первый посде заявки импульс случайного потока, поступающего на триггеп 23 и вентиль 22 с датчика потока случайных импульсов 19, пойдет, с одной стороны, через aIIIIIIIn задержки 24 на переброс триггера 23 из нулевого состояния в единичное, что соответствует снятию разрешающего потенциала с вен.тилей 21 и вентиля 22, и, с другой стороны, через открытый вентиль 22 — на объединенные импульсные входы вентилей 1 и 2 логического блока гаспределения 1б.

Импульс случайного потока, вырабатываемого датчиком потока cëó÷àéIIüë пмпi льcOR

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

Этот импульс пройдет II;III через вентиль 1 логического блока распределения 1б, если за случайный отрезок времени триггер 3 этого блока остался в единичном состоянии (вероятность такого coáûòèÿ равна (1 — Р„), или через вентиль 2 логического блока распределения 1б, если триггер 3 этого блока за случайный отрезок времени перебросится в нулевое состояние (вероятность такого события равна P»).

369571

В том случае, если заявка прошла через вен тиль 1, она через схему «ИЛИ» 7 и открытый вентиль 9 логического блока распределения 16 попадет на первый унифицированный блок моделей обслуживающих приборов 18.

Внутри этого блока заявка может пройти или через вентиль 1, схему «ИЛИ» 7, открытый вентиль 9 и поступить на первую модель обслуживающего прибора 11, если за случайный отрезок времени At триггер 8 остался в единичном состоянии (вероятность такого события равна (1 — P») (1 — Рг ), или через вен тиль 2, схему «ИЛИ» 8, открытый вентиль 10 и может поступить на вторую модель обслуживающего прибора 11, если за случайный отрезок времени At триггер 8 перебросился в нулевое состояние (вероятность такого события равна (1 — Р„).Р„.

В том случае, если заявка прошла через вентиль 2 логического блока распределения 16, она через схему «ИЛИ» 8 и открытый вентиль 10 этого блока попадет на второй унифицированный блок моделей обслуживающих приборов 18.

Внутри этого блока заявка может пройти или через вентиль 1, схему «ИЛИ» 7; открытый вентиль 9 и поступить на третью модель обслуживающего прибора 11, если за случайный отрезок времени At триггер 8 остался в единичном состоянии (вероятность такого события равна Pi> (1 — Рз ), или через вентиль 2, схему «ИЛИ» 8, открытый вентиль 10 и поступить на четвертую модель обслуживающего прибора 11, если за случайный отрезок времени триггер 8 перебросился в нулевое состояние (вероятность такого события равна Pi Рг .

Во втором состоянии вентили 9 и 10 логического блока распределения 16 и первого унифицированного блока моделей обслуживающих приборов 18 открыты потенциаламп, поступающими соответственно со схем «ИЛИ»

27 и с моделей обслуживающих приборов II, а вентили 4 и 6 тех же блоков, закрыты потенциалами, приходящими с блока анализа занятости 17.

Вентиль 9 и вентили 4 и 5 второго унифицированного блока моделей обслуживающих приборов 18 открыты потенциалами, приходящими соответственно с третьей модели обслуживающего прибора Il и блока анализа занятости 17, входящих в состав второго унифицированного блока 18, Вентиль 10 этого блока закрыт потенциалом, поступающим с четвертой модели обслуживающего прибора 11.

В каждой группе вентилей 28 открыпго по одному вентилю, соответствующему второму состоянию. Это обеспечивает дешифратор 81.

Состояние остальных элеме..тов, а также работа схемы на начальном этапе, включая проход заявки или через вентиль 9 логического блока распределения 16 с вероятностью (1 — Рд), или через вентиль 10 того же блока

10

8 с вероятностью Р,г аналогичны случаю, рассмотренному. выше.

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

18, она распределится между первой и второй моделями обслуживающих приборов I l с соответствующими вероятностями (1 — Р,г) . (1 — Ргг) и (1 — Р г) Ргг таким образом, ка" это было показано при первом состоянии модели.

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

15 Внутри этого блока заявка должна попасть только на третью модель обслуживающего прибора 11. Осуществляется это следующим образом.

Если заявка пройдет через вентиль 1, схе20 му «ИЛИ» 7, огкрытый вентиль 9, то она с вероятностью Р г. (1 — P .) попадет на третью модель обслуживающего прибора 11. Одновременно заявка пойдет и по другому пути— через открытый вен тиль 6 схемы «ИЛИ» б и

25 8 и попадет на закрытый вентиль 10, через который заявка не сможет попасть в четвертую модель обслуживающего прибора Il. Если заявка пройдет через вентиль 2, то о. ta, с одной стороны, через схему «ИЛИ» 8 поступит на закрытый вентиль 10, и, с другой стороны, через открытый вентиль 4, схемы

«ИЛИ» 6 и 7 и вентиль 9 с вероятностью

Ры. Р г попадет в третью модель обслуживающего прибора 11.

З5 Таким образом, внутри второго унифицированного блока моделей обслуживающих гриборов 18 заявка в любом случае с вероятностью Рю.Рзг+Рк(1 — Рзг) =Р г попадет л свободную третью модель обслуживающего

40 прибора 11.

В третьем состоянии и логическом блоке распределения 16 открыты вентили 9, 4 и 6 (вентиль 10 закрыт) .

В первом унифицированном блоке моделей

45 обслуживающих приборов 18 открыты венти:IH 9 и 10, вентили 4 и б закрыты.

Во втором унифицированном блоке моделей обслуживающих приборов 18 закрыты вентили 4, б, 9 и 10.

В каждой группе вентилей 28 отк1:ыты по одному вентилю 28, соответствующих третьему состоянию. Это обеспечивает дешифратор 81.

Состояние остальных элементов, а так же работа схемы на начальном этапе, включая проход заявки или через вентиль 1, или через вентиль 2 логического блока распределения

16 аналогичны первому состоянию модели.

При третьем состоянии модели логический

60 блок распределения 16 должен в любом случае (проход заявкой вентиля 1 или вентиля2) направить заявку в первый унифицированный блок модели обслуживающих приборов 18.

Работа логического олока распределения 16

65 в этом случае аналогична работе логического

369577

Стохастическая модель многоканальной системы массового обслуживания, содержащая гечерятор входного потока заявок, соединенный с генератором случайных событий, распределенных в пространстве, связанным с логическим блоком распределения, модели обслуживающих приборов, соединенные через схемы «ИЛИ» с блоком анализа, и подключенные к блоку распределения логические схемы «ИЛИ» и вентили, отлачаюи аяся тем, что, с целью автоматизации изменения вероятностей попадания заявок в свободные каналы в зависимости от Нх по ядковых чомеров, модель содержит дешифратор, входы которого подключены к выходам моделей обслуживающих приборов, а выходы объединены в группы, соединенные входами с шестью схе50

9 блока распределения 16 второго унифицированного блока моделей обслуживающих приборов 18 при втором состоянии модели. Распределение заявок внутри первого унифицированного блока моделей обслуживающих приборов 18 между первой и второй моделями об"луживающих приборов 11 соответствующими вероятностями (1 — Р з) и Р з осуществляется таким же образом, как при первом и втором состояниях моделей.

В четвертом состоянии в логическом блоке распределения 16 вентили 9 и 10 закрыты, поэтому заявка не сможет попасть ни на какую модель обслуживающего прибора 11. Вероятности распределения заявок между моделями обслуживающих приборов 11 при любом состоянии модели задаются переключательной матрицей.

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

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

Два блока на четыре канала, один из которых показан ча фиг. 3, объединяются в блок на восемь каналов с помощью дополнительных элементов: одного логического блока распределения 16; одного блока анализа занятости 17; двух схем «ИЛИ» 27; одной группы вентилей 28 с соответствующими схемами

«ИЛИ» 29 и 30. При этом используется один дешифратор 31 на восемь входов и один генератор потоков событий, распределенных в пространстве 25, число выходов которого увеличено на необходимую величину, определяемую по переключательной матрице.

Объединение двух четырехканальных блоков фиг. 3 с помощью дополнительных элементов осуществляется следующим образом.

Входы логических блоков распределения 16 четырехканальных блоков, которые раньше соединялись с выходом генератора потоков событий, распределенных в пространстве 25, отключаются от этого генератора и подключаются к выходам дополнительного логического блока распределения 16. Отключенный выход генератопа подается на вход этого блока. Другой вход этого блока соединяется с выходом генератора входного потока заявок 26.

Выходы схем «ИЛИ» 27 каждого четырехканального блока фиг. 3 подключаются к дополнительной схеме «ИЛИ» 27, выход котовой, с одной стороны, подается на вход дополнительного логического блока распределения 16 и, с другой стороны, подключенного ко входу дополнительного блока анализа занятости 17. Выход этого блока также соеди5

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

28 соединяются со входом дополнительного логического блока паспределення 16, при этом входы схем «ИЛИ» 28 подключаются к соответствующим выходам дешифратора 31 на восемь входов. Выходы всех восьми моделей обслуживающих приборов 11 подаются на этот дешифратор. Остальные связи внутри каждого четырехканального блока сохраняются.

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

Если необходимо получить многоканальную си"тему с числом каналов, заключенным от

2" — до 2", но не равным этим значениям, то к блоку с числом каналов 2" — надо подключать блоки с числом каналов 2 (i=1. 2, ..., и — 2) или непосредственно модель обслуживающего прибора 11.

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

«ИЛИ» 27, соединенной с этим унифицировачным блоком, а также группы вентилей 28 отпадает. Выход этой модели обслуживающего прибора Il соединяется, с одной стороны, со входом логического блока распределения

16, с другой стороны, — со входом блока анализа занятости 17 и, с третьей стороны, — со входом дешпфратора 31. Необходимость в связи этой мотели обслуживающего ппибора

11 с генератором входного потока заявок 26 отпадает. Остальные связи, показанные на фиг. 3. остаются.

Предмет изобретения

369571

Фиг. 2 мами «ИЛИ», выходы которых соответственно подключены к шести вентилям; вторые входы всех вентилей соединены с выходами генератора случайных событий, распределенных в пространстве; выходы первого и второго вентилей и выходы третьего .и четвертого вентилей подключены соответственно через седьмую и восьмую схемы «ИЛИ» ко входам моделей обслуживающих приборов, а выходы пятого и шестого вентилей через девятую схе5 му «ИЛИ» соединены со входом логического блока распределения, 369571

Составитель В. Жовинский

Техред Л. Богданова

Редактор Е. Семанова корректор О. Тюрина

Типография, пр. Сапунова, 2

Заказ 3525/10 Изд. М 1443 Тираж 647 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, Ж-35, Раушская наб., д. 4/5