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

Од

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

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

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

Устройство содержит каналы J об- служиван1Гя заявок, каждый из которых состоит из первого элемента И 2, пер вого триггера 3, второго элемента И 4, элемента ИЛИ-НЕ 5, генератора 6 импульсов, счетчика 7 импульсов, бло ка 8 элементов И, второго триггера 9 третьего элемента И 10, блока случай ной временной задержки, содержащего элементы П задержки, и генератора 12 случайного потока заявок.

В состав устройства входят также первый 13 и второй 14 элементы ИЛИ, блок 15 элементов задержки, блок 16 сравнения кодов, триггер 17 управления, второй элемент И 18, третий эле мент ИЛИ 19, первый элемент И 20.

Устройство предназначено для моде лирования СМО с динамическими приори тетами, т.е. таких СМО, в которых приоритет обслуживания поступающих заявок зависит от длительности ожида ния заявок.в очереди. Выбор заявок на обслуживание осуществляется с ytie том текущего значения функции приорИ тетности /}j(t), зависящей для заявки каждого типа от времени ожидания. Обслуживание заявок ocJrщecтвляeтcя в порядке относительного приоритета таким образом, что на обслуживание поступает заявка, обладающая в данный момент времени максимальным значением функции приоритетности ;(t), из числа заявок, находящихся в очере ди.

функция приоритетности заявок име ет вид

(,(t) b.(t

- J, ).

де h . i О

1

t коэффициент, определяющий скорость изменения приоритетности заявки i-ro типа при ее пребывании в очереди; момент поступления заявки i-ro типа; текущий момент времени.

10

15

20

25

30

35

40

45

50

55

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

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

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

Элементами, определяющими приоритет заявки i-ro канала в любое время от момента поступления до момента приема на обслуживание, являются генератор 6 импульсов и счетчик 7 каждого канала, подсчитывающий импульс с генератора 6. Скорость увеличения значения кода на группе кодовых выходов счетчика 7 зависит от частоты повторения импульсов генератора 6, которая является аналогом скорости нарастания b приоритета поступившей заявки. Если приоритетность классов заявок уменьшается с возрастанием номера канала устройства, то частоты повторения импульсов генераторов 6 каналов должны быть такими, чтобы

- h Ui о сравнения кодов осуществляет сравнение кодов приоритетов заявок на момент освобождения обслуживающего прибора и обеспечивает выбор ЗЯБКИ на обслуживание, имеющей в данньй момент максимальный приоритет.

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

В исходном состоянии все триггеры 3,9,17 находятся в нулевом состоянии, а в счетчиках 7 каналов записаны нули. Единичные потенциалы с нулевых выходов триггеров 3 присутствзпот на вторых входах элементов И 2. На вторых входах элементов И 4 единичные потенциалы присутствуют с выходов элементов ИЛИ-НЕ 5. Кроме того, единичные потенциалы с нулевых выходов триггеров 9 приложены к вторым входам соответствуюнщх элементов И 10 и соответствующим входам элемента И 18 устройства. ,

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

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

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

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

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

а

При появлении сигнала, порядок формирования которого рассматривается ниже, на выходе элемента 11 задержки одного иэ каналов, имитирующего сигнал конца обслуживания заявки, начинается подготовка отдельных узлов устройства моделирования к выбору очередной заявки на обслуживание. С этой целью данный сигнал, проходя через элемент ИЛИ 19, устанавливает в нулевое состояние управляющий триггер 17 и триггеры 9 каналов, в исходное состояние - блок 16 сравнения кодов. Кроме того, этот сигнал поступает через открытый элемент И 20 и элемент ИЛИ 14 на вход блока 15 элементов задержки. Сигнал с первого выхода блока 15 элементов задержки, задержанный на время, необходимое для -установки в исходное состояние блока 16 сравнения кодов и триггеров 9,17, имитирует сигнал готовности к обслуживанию обслуживающего прибора и поступает на вторые входы элементов ИЛИ-НЕ 5 всех канапой. Через элементы ИЛИ-НЕ 5 сигнал закрывает элементы И 4 каналов, останавливая тем самым работу генераторов 6 импульсов Таким образом, на счетчиках 7 каналов будут зафиксированы значения функций приоритетности заявок различных классов на момент прихода сигнала СГО. После этого сигнал с второго выхода блока 15 элементов задержки, задержанный на время, необходимое для прекращения работы генераторов, открывает элементы И 8 каналов. В результате этого значение кодов с выходов счетчиков 7 переписывается в блок 16 сравнения кодов. 6 период отсутствия сигнала готовности элементы И 8 каналов закрываются, элементы И 4 открываются и генераторы 6 импульсов возобновляют свою работу.

По истечении времени, необходимого для записи кодов со счетчиков 7 каналов в блок 16 ср авнения кодов,

15

30

20товности к обслуживанию содержали не максимальные коды, появляются единичные сигналы. Эти сигналы устанавливают в единично е состояние соответствующие триггеры 9 каналов. Следовательно, в нулевом состоянии остается триггер 9 того канала, счетчик 7 которого содержал в момент прихода сигнала максимальный код, т.е. заявка данного канала (класса) имеет в данный момент наивысший приоритет. На втором входе элемента И 10 этого канала (назовем его приоритетным) по- прежнему присутствует единичный по25 тенциал, в то время как на вторых входах элементов И 10 остальных каналов с нулевых выходов триггеров 9 соответствующих каналов появляются нулевые потенциалы.

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

4Q который принадлежит приоритетному каналу. В результате на выходе элемента И 10 приоритетного канала и, следовательно, на соответствующем входе элемента I1 задержки этого канала появляется сигнал, имитирующий

35

45

50

55

сигнал начала обслуживания (СНО) заявки. Этот же сигнал через элемент ИПИ-НЕ 5 останавливает работу генератора в приоритетном канале.

По истечении времени, равного времени обслуживания заявки данного класса, на выходе элемента ,11 задержки приоритетного канала появляется сигнал, который устанавливает в нулевое состояние счетчик 7 и триггер 3 этого канала, а через элемент ИЛИ 19 устанавливает в исходное состояние узлы выбора заявки (канала) на обслу

живание. Дальнейшая работа устройства аналогична рассмотренной выше.

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

При отсутствии заявок в устройстве (т.е. все триггеры 3 находятся в нулевом состоянии) последним сигналом конца обслуживания установятся в исходное состояние блок 16 сравнения кодов и-триггеры 9,17, а сигнал готовности к обслз иванию вырабатываться не.будет, так как элемент И 20 закрыт нулевым потенциалом с единичных выходов триггеров 3 через элемент ИЛИ 13 к входу элемента И 20. Такое состояние характерно для устройства и при первоначальном включении его в работу.

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

Так как в рассматриваемом случае все триггеры 9 находятся в нулевом состоянии и единичные потенциалы с нулевых выходов этих триггеров 9 приложены к соответствующим входам элемента И 18 устройства, то единичный сигнал с единичного выхода триггера 3 того канала, в котором выработан импульс-заявка, через элемент ИЛИ 13 открывает элемент И 18 устройства. В результате этого единичный сигнал с выхода элемента И 18 через элемент ИЛИ Г4 поступает в блок 15 элементов задержки и обеспечивает вьфаботку ск нала готовности к обслуживанию. В ходе дальнейшей работы устройства, которая рассматривалась вьш1е, поступившая заявка выдается на обслужива

ние, так как в счетчиках 7 остальных каналов записаны нули.

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

Формул

изобретения

0

5

0

0

5

0

Устройство для моделирования систем массового обслуживания, содержащее группу каналов обслуживания заявок, каждый из которых состоит из генератора случайного потока заявок, первого триггера, трех элементов И 5 и блока случайной временной задержки, выход генератора случайного потока заявок соединен с первым входом первого элемента И, выход которого подключен к единичному входу первого триггера, прямой выход которого соединен с первым входом второго элемента И, инверсный выход первого триггера подключен к второму входу первого элемента И, выход блока случайной временной задержки соединен с кулевым входом первого триггера, о т л и- чающееся тем, что, с целью расширения функциональных возможностей за счет воспроизведения динамического приоритета в обслуживании заявок, оно дополнительно содержит блок сравнения кодов, первый и второй элементы И, первый, второй и третий элементы ИЛИ, блок элементов задержки и триггер управления, а каждый канал обслуживания заявок группы дополнительно содержит элемент ИЛИ- НЕ, генератор импульсов, счетчик импульсов, блок элементов И и второй триггер, причем в каждом канале обслуживания заявок группы выход элемента Ш1И-НЕ соединен с вторым входом второго элемента И, выход которого соединен с входом генератора импульсов, выход которого подключен к счетному входу счетчика импульсов, разрядные выходы которого соединены соответственно с информационными входами блока элементов И, выход третьего элемента И подключен к первому входу элемента ЯЛИ-НЕ и входу запуска блока случайной временной задержки, выход которого соединен с установочным входом счетчика импульсов, прямые выходы первых триггеров всех каналов обслуживания заявок группы подключены соответственно к входам первого элемента ШШ устройства, выход которого соединен с первыми вхо5

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

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