Устройство для моделирования систем массового обслуживания Советский патент 1990 года по МПК G06N7/08 

(21)4629509/24-24

(22)02.01.89

(46)07.12.90. Бюл.М 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 ил

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

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

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

На чертеже приведена структурная схема устройства.

Устройство содержит каналы 1 обслуживания заявок, каждый из которых состоит из генератора 2 случайного потока заявок первого элемента И 3, первого триггера 4, второго элемента И 5, первого счетчика 6 дешифратора 7, регистров 8, блоков элементов И 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 элементов задержки.

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

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

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

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

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

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

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

В исходном состоянии триггеры 4, 12 и 23 находятся в нулевом состоянии, а в счетчиках 6 и 11 каналов записаны нули. Единич- ные потенциалы с инверсных выходов

триггеров 4 присутствуют на входах триггеров И 3. Кроме того, единичные потенциалы с инверсных выходов триггеров 12 приложены к соответствующим входам элемента И 5 22 и к соответствующим входам элементов И 13. В регистры 8 каналов занесены значения функций приоритетности заявок различных типов в дискретные моменты времени.

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

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

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

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

35 функций приоритетности с соответствующих регистров 8 поступают на группы входов блоков 10 элементов ИЛИ. Таким образом, на группах входов начальной установки 26 счетчиков 11 ф-1ксируются зна0 чения функций приоритетности заявок в зависимости от момента поступления заявки.

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

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

задержки.

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

10

- 1 г-г- - -- iJ- j f t4j

счетчиков 11 всех каналов. Формирователь 19 преобразует постоянный высокий потенциал в короткий импульс с длительностью обеспечивающей запись кодов в счетчики 11 каналов. В результате этого значения кодов с выходов соответствующих регистров соответствующих регистров 8 через соответствующие открытые блоки 9 элементов И и блоки 10 элементов ИЛИ будут записавыходов триггеров 12 соответствующих ка налов по-прежнему будут нулевые потенци алы. Кроме того, нулевой потенциал инверсного выхода триггера 12 приоритет ного канала будет приложен к соответству ющим входам элементов И 13 каналов

имеющих номер больше, чем у приоритетно го канала.

После завершения переходных процессов, обусловленных этапом выделения приоритетного канала, сигналом с выхода 29 блока 18 элементов задержки устанавливается в единичное состояние триггер 23, Единичный сигнал с прямого выхода триггера

20

ныв счетчики 11, те в них будут забикги Ч лвнного пассв,в рованы значения ФvнкuиГпn fnl ±Л r l., приоритетного канала п оканалов, отк рывает только тот из них, который принадлежит приоритетному каналу. В результате на выходе элемента И 13 приоритетного канала и, следовательно, на соответствующем блоке 14 этого канала появляется сигнал, имитирующий сигнал начала обслуживания заявки.

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

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

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

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

30

1- - f-- -- -.,.-,-, rvuiic /fa м

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

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

35

и:Г:еГеГ„ :::ГсГГа Г; Г.Г , е Ге ;i rS VC.po.c.e вди„„н„се состояние .р„„ер 2 з™™ ка- 50 Й™ ,„ и;ГпоГд„гГсГ;;оГ«о „ :Го°а

нала.

Низкий потенциал с инверсного выхода данного триггера 12 поступает на соответствующий вход элемента И 22, в результате чего закрываются элементы И 22 и 20, а генератор 21 импульсов прекращает свою работу. На втором входе элемента И 13 приоритетного канала присутствует единичный потенциал, в то время как на вторых входах элементов И 13 остальных каналов с прямых

55

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

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

выходов триггеров 12 соответствующих каналов по-прежнему будут нулевые потенциалы. Кроме того, нулевой потенциал с инверсного выхода триггера 12 приоритетного канала будет приложен к соответствующим входам элементов И 13 каналов,

имеющих номер больше, чем у приоритетного канала.

После завершения переходных процессов, обусловленных этапом выделения приоритетного канала, сигналом с выхода 29 блока 18 элементов задержки устанавливается в единичное состояние триггер 23, Единичный сигнал с прямого выхода триггера

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

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

Ч лвнного пассв,в l., приоритетного канала п о0

1- - f-- -- -.,.-,-, rvuiic /fa м

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

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

5

, е Ге ;i rS VC.po.c.e 50 Й™ ,„ и;ГпоГд„гГсГ;;оГ«о „ :Го°а

55

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

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

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

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

Устройство для моделирования систем массового обслуживания, содержащее два элемента ИЛИ. два элемента И. блок элементов задержки, триггер и группу каналов обслуживания заявок, каждый из которых состоит из генератора случайного потока заявок, двух триггеров, трех элементов И, блока элементов И. счетчика и блока случайной временной задержки, причем в каждом канале обслуживания заявок выход генератора случайного потока заявок соединен с первым входом первого элемента И. выход которого подключен к единичному входу первого триггера, прямой выход которого соединен с первым входом второго элемента И. выход третьего элемента И подключен к входу блока случайной временной задержки, выход которого соединен с нулевым входом первого триггера, инверсный выход которого подключен к второмуlewdj y riepeo- го элемента И. выходы блоков случайной временной задержки всех каналов обслуживания заявок группы соединены соответственно с входами первого элемента ИЛИ устройства, выход которого подключен к нулевым входам вторых триггеров всех каналов обслуживания заявок группы и к нулевому входу триггера устройства, прямой выход которого соединен с первыми входами третьих элементов И всех каналов обслуживания заявок группы, прямые выходы первых триггеров всех каналов обслужи- вания заявок группы подключены соответственно к входам второго элемента ИЛИ устройства, выход которого соединен с первым входом первого элемента И устройства, первый выход блока элементов за держки подключен к единичному входу триггеров устройства, инверсный выход второго триггера К-го канала обслуживания заявок группы (К 1, М) соединен с (К + 1)-м входом первого элемента И устройства и с (К + 2)-ми входами третьих элементов И всех

каналов обслуживания заявок группы, имеющих номер, больший чем К, прямой выход второго триггера К-го канала обслуживания заявок группы подключен к (К +1}-му входу 5 третьего элемента И своего канала обслуживания заявок группы, отличающееся тем, что. с целью повышения точности моделирования динамического приоритета в обслуживании заявок, оно дополнительно 10 содержит элемент запрета, два генератора импульсов и формирователь импульсов, а каждый канал обслуживания заявок группы дополнительно содержит дешифратор, второй счетчик, блок элементов ИЛИ, Р регист- 15 ров (где.Р - количество дискретных значений функции приоритетности) и (Р-1) блоков элементов И. причем в каждом канале обслуживания заявок группы выход второго элемента И соединен со счетным 20 входом первого счетчика, разрядные выходы которого подключены соответственно к входам дешифратора, выходы которого соединены с управляющими входами соо твет- ствующих блоков элементов И, разрядные 5 входы регистров подключены к информационным входам соответствующих блоков элементов И, выходы которых соединены соответственно с входами блока элементов ИЛИ. выходы которого соединены соответ- 0 ственно с разрядными второго счетчика, выход переполнения которого подключен к единичному входу второго триггера, инверсный выход первого триггера подключен к входу обнуления первого 5 счетчика, выход первого элемента И устройства соединен с первым входом второго эле- мента И устройства и входом блока элементов задержки, второй выход которого соединен с управляющим входом элемен- 0 та запрета, третий выход - с входом формирователя импульсов, а четвертый выход - с вторым входом второго элемента И устройства, выход которого подключен к входу первого генератора импульсов, выход 5 которого соединен со счетными входами вторых счетчиков всех каналов обслуживания заявок, выход второго элемента ИЛИ устройства подключен к информационному входу элемента запрета, выход которого со- 0 единен с входом второго генератора импульсов, выход коГорого подключен к счетным входам первых счетчиков всех ка- . налов обслуживания заявок группы, выход формирователя импульсов соединен с вхо- 5 дами записи вторых счетчиков всех каналов обслуживания заявок группы, входы установки в нулевое состояние которых объединены и подключены к выходу первого элемента ИЛИ устройства.