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

 

Изобретение относится к вычислительной технике и может быть использовано для статистического моделирования систем массового обслуживания. Цель изобретения - повышение точности моделирования нелинейного динамического приоритета в обслуживании заявок. Устройство содержит блок элементов задержки, триггер управления, два генератора импульсов, два элемента ИЛИ, два элемента И, формирователь импульсов и группу каналов обслуживания заявок, а в каждом канале генератор случайного потока заявок, два триггера, три элемента И, два счетчика, дешифратор, P регистров, P блоков элементов И, блок элементов ИЛИ и блок случайной временной задержки. Устройство предназначено для моделирования СМО с динамическими приоритетами, т.е. таких СМО, в которых приоритет обслуживания заявок зависит от длительности ожидания заявок в очереди. Выбор заявок на обслуживание осуществляется с учетом текущего значения функции приоритетности, зависящей для заявки каждого типа от времени ожидания и имеющей в общем случае нелинейный вид. Обслуживание заявок осуществляется в порядке относительного приоритета таким образом, что на обслуживание поступает заявка, обладающая в данный момент времени максимальным значением функции приоритетности из числа заявок, находящихся в очереди. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)л 6 06 F 15/20

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4629509/24-24 (22) 02,01.89 (46) 07.12.90, Бюл. N. 45 (72) Ю.А,Капиносов. А.Н.Башкиров, И.А,Ветров и О.Н.Иваненюк (53) 681.3 (088.8) (56) Авторское свидетельство СССР

М 983715, кл. G 06 F 15/20, 1981.

Авторское свидетельство СССР

М 1406600, кл. G 06 F 15/20, 1986. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано для статистического моделирования систем массового обслуживания. Цель изобретения — повышение точности моделирования нелинейного динамического приоритета в обслуживании заявок. Устройство содержит блок элементов задержки, триггер управления, два генератора импульсов, два элемента

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

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

На чертеже приведена структурная схема устройства, Устройство содержит каналы 1 обслуживания заявок, каждый из которых состоит из генератора 2 случайного потока заявок, первого элемента И 3, первого триггера 4, второго элемента И 5, первого счетчика 6, дешифратора 7, регистров 8, блоков элемен„„Я,2„„1612311 А1 пульсов и группу каналов обслуживания заявок, а в каждом канале генератор случайного потока заявок, два триггера, три элемента И, два счетчика, дешифратор, Р .регистров, P блоков элементов И, блок элементов ИЛИ и блок случайной временной заде ржки. Устройство и редназначено для моделирования СМО с динамическими приоритетами, т,е таких СМО, в которых приоритет обслуживания заявок зависит от длительности ожидания заявок в очереди.

В ыбор заявок на обслуживание осуществляете с учетам текущего значения функции приоритетности, зависящей для заявки каждого типа от времени ожидания и имеющей в общем случае нелинейный вид. Обслуживание заявок осуществляется в порядке относительного приоритета таким образом, что на обслуживание поступает заявка, обладающая а данный момент времени максимальным значением функции приоритетности из числа заявок, находящихся в очереди. 1 ил. тов И 9, блока элементов ИЛИ 10, второго счетчика 11, второго триггера 12, третьего элемента И 13 и блока 14 случайной временной задержки, В состав устройства входят также второй элемент ИЛИ 15, элемент 16 запрета, второй генератор 17 импульсов, блок 18 элементов задержки, формирователь 19, импульсов, элемент И 20, первый генератор 21 импульсов, г.ервый элемент И 22, триггер

23, первый элемент ИЛИ 24, На схеме также обозначены входы 25 счетчика 11 записи. разрядные 26, счетный 27 и сброса 28, первый 29, второй 30, третий 31 и четвертый 32 выходь; блока 18 элементов задержки.

1612311

15

25

40

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

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

Значения известной функции приори-! тетности в дискретные значения времени заранее заносятся на группу регистров 8 и считываются последовательно с частотой квантования, задаваемой генератором 17 импульсов.

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

Блок 14 случайной временной задержки имитирует обслуживающий прибор с произвольным временем обслуживания, Элементами, определяющими приоритет заявки какого-либо канала в любое время от момента поступления до момента приема на обслуживание, являются счетчик

6, дешифратор 7, регистры 8, блоки 9 элементов И и блок 10 элементов ИЛИ каждого канала. На выходе блока 10 элементов ИЛИ будет код, определяющий значение функции приоритетности заявки на данный момент времени.

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

Устройство .работает следующим образом.

В исходном состоянии триггеры 4, 12 и

23 находятся в нулевом состоянии, а в счетчикахби11 каналовзаписаны нули, Единичные потенциалы с инверсных выходов триггеров 4 присутствуют на входах триггеров И 3. Кроме того, единичные потенциалы с инверсных выходов триггеров 12 приложены к соответствующим входам элемента И

22 и к соответствующим входам элементов

И 13. В регистры 8 каналов занесены значения функций приоритетности заявок различных типов в дискретные моменты времени.

Импульсы от генераторов 2 случайного потока заявок, имитируя входные потоки заявок на обслуживание различных приоритетных классов, проходят через открытые элементы И 3 соответствующих каналов на единичные входы триггеров 4 этих каналов, устанавливая их в единичное состояние

Единичный потенциал с выходов этих триггеров 4 через элемент ИЛИ 15 и элемент 16 запрета запускает генератор 17 импульсов, с выхода которого импульсы с частотой квантования функций приоритетности заявок каналов поступают на входы элементов

И 5 всех каналов обслуживания заявок, Эти импульсы поступают на счетные входы счетчиков 6 тех каналов, в которых зафиксированы заявки на обслуживание, так как высокие потенциалы с единичных выходов триггеров 4 обеспечивают открывание элементов И 5 данных каналов. В результате этого на выходах дешифратора 7 этих каналов последовательно с частотой квантования появляются высокие потенциалы, открывающие поочередно блоки 9 элементов И, и коды дискретных значений функций приоритетности с соответствующих регистров 8 поступают на группы входов блоков 10 элементов ИЛИ. Таким образом, на группах входов начальной установки 26 счетчиков 11 ф-буксируются значения функций приоритетности заявок в зависимости от момента поступления заявки.

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

При появлении сигнала, порядок формирования которого рассматривается ниже, на выходе элемента 14 задержки одного из каналов, имитирующего сигнал конца обслуживания (СКО), начинается подготовка отдельных узлов устройства моделирования к выбору очередной заявки на обслуживание. С этой целью данный сигнал, проходя через элемент ИЛИ 24, устанавливает в нулевое состояние триггер 23, триггеры 12 и счетчики 11 всех каналов. В результате этого открывается элемент И 22, высокий потенциал с его выхода поступает на вход элемента И 20 и на вход блока 18 элементов задержки, 1612311

Сигнал с второго выхода 30 блока 18 элементов задержки, задержанный на время, необходимое для установки в исходое состояние триггеров 12, 23 и счетчиков 11, имитирует сигнал готовности к обслуживанию (СГО) обслуживающего прибора и поступает на управляющий вход элемента 16 запрета, останавливая тем самым работу генератора 17 импульсов. После этого сигнал с третьего выхода 31 блока 18 элементов задержки, задержанный на время, необходимое для прекращения работы генератора

17 импульсов, поступает на вход формирователя 19, который выдает импульс на управляющие (разрешающие) входы 25 счетчиков 11 всех каналов. Формирователь

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

11 каналов. В результате этого значения кодов с выходов соответствующих регистров соответствующих регистров 8 через соответствующие открытые блоки 9 элементов

И и блоки 10 элементов ИЛИ будут записаны в счетчики 11, т,е. в них будут зафиксированы значения функций приоритетности заявок различных классов на момент прихода сигнала СГО. В период отсутствия сигнала готовности элемент 16 запрета открывается и генератор 17 импульсов возобновляет свою работу.

По истечении времени, необходимого для записи кодов в счетчики 11, сигналом с четвертого выхода 32 блока 18 элементов задержки через открытый элемент И 20 запускается генератор 21 импульсов.

Импульсы с выхода генератора 21 с большой частотой повторения поступают на счетные входы 27 счетчиков 11 всех каналов обслуживания заявок. Счетчики 11 выполняют функцию определения заявки (канала) с максимальным значением функции приоритетности на момент прихода сигнала СГО.

Так как емкость счетчиков 11 одинакова, то при поступлении импульсов на счетный вход 27 счетчиков 11 первым переполнится тот из них, на который записан наибольший код значения функции приоритетности. Сигнал переполнения счетчика 11 установит в единичное состояние триггер 12 этого канала.

Низкий потенциал с инверсного выхода данного триггера 12 поступает на соответствующий вход элемента И 22, в результате чего закрываются элементы И 22 и 20, а генератор 21 импульсов прекращает свою работу. На втором входе элемента И 13 приоритетного канала присутствует единичный потенциал, в то время как на вторых входах элементов И 13 остальных каналов с прямых выходов триггеров 12 соответствующих каналов по-прежнему будут нулевые потенциалы. Кроме того, нулевой потенциал с инверсного выхода триггера 12 приоритет5 ного канала будет приложен к соответствующим входам элементов И 13 каналов, имеющих номер больше, чем у приоритетного канала, После завершения переходных процес10 сов, обусловленных этапом выделения приоритетного канала, сигналом с выхода 29 блока 18 элементов задержки устанавливается в единичное состояние триггер 23, Единичный сигнал с прямого выхода триггера

15 23, поступая на входы элементов И 13 всех каналов, открывает только тот из них, который принадлежит приоритетному каналу. В результате на выходе элемента И 13 приоритетного канала и, следовательно, на со20 ответствующем блоке 14 этого канала появляется сигнал, имитирующий сигнал начала обслуживания заявки.

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

25 выходе блока 14 приоритетного канала появляются сигналы конца обслуживания, который устанавливает в нулевое состояние триггер 4 этого канала, который, в свою очередь, сигналом с нулевого выхода обнуляет

30 счетчик 6 и открывает элемент И 3 данного кяналэ. Кроме того, через элемент ИЛИ 24 устанавливает в исходное состояние триггерь; 1", 23 и счетчики 11 всех каналов. Дальнейшая работа устройства аналогична

35 рассмотренной выше.

Возможны случаи, когда две или несколько заявок на обслуживание имеют одинаковые приоритеты, т.е. коды счетчиков 1 l этих качалов в момент прихода сигнала го40 товности к обслуживанию окажутся равными. Тогда сигнал появляется на выходе элемента И 13 того канала, в котором имитируются заявки более приоритетного класса, так как нулевой сигнал с инверсного

45 выхода триггера 12 этого канала удерживает в закрытом состоянии элементы И 13 каналов менее приоритетных классов.

При отсутствии заявок в устройстве (т.е. все триггеры 4 находятся в нулевом

50 состоянии) последним сигналом конца об<-..луживания установятся в исходное состояние триггеры 12, 23 и счетчики 11, а сигнал готовности к обслуживанию вырабатываться не будет, так как элемент И 22 закрыт

55 нулевым потенциалом с выхода элемента

ИЛИ 15, Такое состояние характерно для устройства и при первоначальном включении его в работу.

При выдаче одним из генераторов 2 случайного потока заявок осуществляется уста1612311

30

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

Получение характеристик СМО осуществляется известными способами.

Формула изобретения

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

ИЛИ устройства, выход которого соединен с первым входом первого элемента И устройства, первый выход блока элементов задержки подключен к единичному входу триггеров устройства, инверсный выход второго триггера -ro канала обслуживания заявок группы (К = 1, M) соединен с (К+ 1)-м входом первого элемента И устройства и с (К+ 2)-ми входами третьих элементов И всех каналов обслуживания заявок группы, имеющих номер, больший чем К, прямой выход второго триггера К-ro канала обслуживания заявок группы подключен к (К +1)-му входу третьего элемента И своего канала обслуживания заявок группы. о т л и ч а ю щ е е с я тем, что, с целью повышения точности моделирования динамического приоритета в обслуживании заявок, оно дополнительно содержит элемент запрета, два генератора импульсов и формирователь импульсов, а каждый канал обслуживания заявок группы дополнительно содержит дешифратор, второй счетчик, блок элементов ИЛИ, P регистров (где P — количество дискретных значений функции приоритетности) и (P-1) блоков элементов И. причем в каждом канале обслуживания заявок группы выход второго элемента И соединен со счетным входом первого счетчика, разрядные выходы которого подключены соответственно к входам дешифратора, выходы которого соединены с управляющими входами соответствующих блоков элементов И, разрядные входы регистров подключены к информационным входам соответствующих блоков элементов И, выходы которых соединены соответственно с входами блока элементов

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

1612311

Составитель В,Фукалов

Техред M. Морг нтал Корректор Т.Палий

Редактор А.Мотыль

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101

Заказ 3831 Тираж 56Q Подписное

ВНИИПИ Государственного комитета по изобрегениям и открытиям при ГКНТ СССР

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