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

 

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

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4816515/24 (22) 19.04.90 (46) 30.01.92. Бюл. М 4 (71) Московский институт инженеров гражданской авиации (72) С. Ж. Кишенский, Н. С. Вдовиченко, B. Б.

Панова и О. Ю. Христенко (53) 681.3(088.8) (56) Авторское свидетельство СССР

М 1236494, кл. G 06 F 15/20, 1984.

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

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

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

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

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

Устройство содержит триггер, элементы

ИЛИ, группу элементов ИЛИ, две группы элементов И, два коммутатора, элемент НЕ, два блока памяти, дешифратор, группу генераторов случайных импульсов, счетчики импульсов, блок вычитания, схемы сравнения, элементы задержки, В устройстве моделируется дисциплина обслуживания типа

"первый пришел — первый обслужен" с памятью времени поступления заявки на обслуживание. 1 ил.

Недостатками данного устройства являются сложность конструкции и узкие функционал ь н ые возможности.

Наиболее близким по технической сущности к предлагаемому является устройство для моделирования систем массового обслуживания, содержащее группу элементов

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

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

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

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

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

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

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

Устройство содержит триггер 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 элементов ИЛИ, третий 26, четвертый 27, пер1709336 вый 28 и второй 29 элементы И, информационные 30 входы, выходы 31 обслуженных и необслуженных 32 заявок, вход 33 задания времени ожидания.

В исходном состоянии триггер 1 в единичном состоянии (на прямом выходе — единичный потенциал), счетчики 16 и 17 — в нулевом состоянии, все ячейки блоков памяти 12 и 13 обнулены, таймер также в нулевом состоянии. При отсутствии (например, в исходном состоянии) управляющих единичных сигналов на управляющих входах коммутаторов 10 и 11 они соответственно коммутируют на свои выходы сигналы с входа 30 и счетчика 16.

Вербальная модель работы устройства.

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

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

Если ее нет (буфер, моделируемый блоком памяти первым — пуст), триггер устанавливается в единичное состояние, фиксируя освобождение обслуживающего прибора.

Если ожидающая заявка есть, она поступает на обслуживание. Буфер устанавливается

55 таким образом, что на выходе блока 12 памяти за счет сигнала счетчика 16 присутствует всегда,(если она есть) очередная заявка, поступившая в буфер ранее остальных (самая "старая"), а на выходе блока 13 памяти — абсолютное время ее поступления.

Это время вычитается из текущего времени, формируемого таймером, и разность — длительность ожидания самой "старой" заявки сравнивается с максимально возможным временем ожидания. При превышении максимального времени ожидания моделируется отказ в обслуживании данной заявки: с соответствующего выхода 32 пользователю выдается сигнал об отказе и номере потока, и соответствующая заявка стирается из блоков памяти, после чего на выходе их устанавливается следующая (по времени ожидания) заявка. Таким образом, моделируется процесс обслуживания заявок от нескольких (произвольного числа) потоков с независимыми временами обслуживания и с ограниченным временем ожидания.

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

Рассмотрим перечисленные случаи и работу устройства при возникновении соответствующих событий.

В первом состоянии (оно совпадает с исходным) открыты элементы И 7 и закрыт нулевым сигналом с инверсного выхода триггера 1 элемент И 28, так что сигналы поступающей заявки с выхода элемента

ИЛИ 4 не проходят через элемент И 28.

Сигнал заявки с соответствующего входа 30 через соответствующий элемент И 7, через соответствующий элемент ИЛИ 25 поступает на вход запуска соответствующего генератора 15, а также через элемент ИЛИ 2 устанавливает триггер 1 в нулевое состояние. Как до, так и после поступления заявки содержимое блоков памяти; блока 12 (сигналы на его выходах) — нулевое; блока 13— произвольное. Содержимое счетчиков 16 и

17 — одинаковое.

Во втором случае (отличающееся от первого тем, что в момент поступления заявки триггер 1 в нулевом состоянии) элементы И

7 закрыты нулевым сигналом с прямого выхода триггера 1; поступающая заявка формирует сигнал на выходе элемента ИЛИ 4, который, проходя через открытый сигналом

1709336

20

30

40

55 с инверсного выхода триггера 1 элемент.И

28, поступает на управляющий вход коммутатора 11, который по этому сигналу подключает на свои выходы счетчика 17, эти сигналы поступают на адресные входы блоков 12 и 13 памяти. Тем же сигналом с выхода элемента И 28 через элемент ИЛИ 6 на блоки памяти 12 и 13 поступают сигналы записи, таким образом, в блок 12 памяти через коммутатор 10 по адресу, формируемому счетчиком 17, записывается вектор, представляющий собой запись в единичном коде номера потока, по которому поступила данная заявка, а в блок 13 памяти записывается время (абсолютное) от таймера. После этого с задержкой, определяемой элементом 19, содержимое счетчика 17 увеличивается на единицу, осуществляя подготовку к возможной записи в блоки памяти по следующему адресу новой заявки, которая может поступить в интервале занятости обслуживающего прибора.

В третьем случае (окончание обслуживания заявки при пустом буфере) окончание обслуживания заявки некоторого потока вызывает появление на соответствующем выходе определенного генератора 15 положительного короткого импульса, который поступает пользователю по выходу 31, фиксируя окончание обслуживания заявки данного потока, и через элемент ИЛИ 3 поступает на вход элемента И 26. Когда буфер пуст, на выходе блока памяти 12 — нулевой код (как будет показано ниже, после обслуживания или после отказа в обслуживании соответствующая ячейка блока 12 обнуляется), поэтому с выхода дешифратора 14, настроенного на нулевую кодовую комбинацию, на вход элемента И 26 поступает разрешающий сигнал, по которому импульс с выхода элемента ИЛИ 3 через элемент И 26 поступает на вход триггера 1 и устанавливает его в единичное состояние, фиксируя факт освобождения обслуживающего прибора.

В четвертом случае (окончание обслуживания при непустом буфере) с выхода дешифратора 14 на элемент И 26 не поступает разрешающего сигнала, поэтому импульс окончания заявки с выхода элемента ИЛИ 3 не проходит через элемент И 26. Однако этот импульс проходит в качестве разрешающего на группу элементов И 8, через которую и далее через группу элементов ИЛ И 25 на входы группы генераторов случайных импульсов 15 поступает вектор с блока 12 памяти, соответствующий самой."старой" из поступивших и ожидающих обслуживания заявок. Этот вектор (a любом случае он содержит лишь одну единицу в своем составе, место которой соответствует номеру потока данной заявки) запускает соответствующий генератор из группы 15, осуществляя тем самым начало обслуживания самой "старой" из заявок, содержащихся в буфере.

Этот же импульс (с выхода элемента ИЛИ 3) через элемент ИЛИ 5 поступает на вход управления коммутатора 10, чем осуществляется переключение выходов коммутатора на его входы, соединенные с нулевой шиной устройста, и через элемент ИЛИ 6 — на вход записи блоков памяти 12 и 13, таким образом осуществляется обнуление соответствующей ячейки памяти в блоке 12 и запись текущего времени от таймера в блок 13 (данное время) в дальнейшем не оказывает влияния на работу устройства, так как соответствующая ему ячейка блока памяти

12 имеет нулевое значение).

Когда содержимое счетчиков 16 и 17 не одинаково(буфер содержит необслуженные заявки) с выхода "Не равно" схемы сравнения 21 поступает на элемент И 27 разрешающий сигнал, по которому с выхода элемента ИЛИ 5 через элемент И 27 импульс поступает с некоторой задержкой (определяемой элементом 18) на счетный вход счетчика 16 и увеличивает его содержимое на единицу, подготавливая к обслуживанию новую заявку из буфера. Если содержимое одинаково, то буфер пуст и сигнал на инкрементирование счетчика 16 не поступает, В общем случае счетчик 16 всегда либо "отстает" по содержимому от счетчика 17, либо равен ему, но никогда не опережает (это означало бы "отрицательное" число заявок в буфере).

В третьем режиме с выхода элемента

ИЛИ 3 на элементы И 8 и ИЛИ 5 поступают импульсы в момент окончания обслуживания заявки, но так как содержимое соответствующей ячейки блока 12 нулевое, это не оказывает влияния на работу устройства.

В пятом случае (истечение времени ожидания очередной заявки) текущее время таймера становится. больше времени поступления самой "старой" заявки на величину, которая превышает установленное в схеме 20 сравнения максимальное время ожидания. При этом на выходе "Равно" схемы 20 формируется импульс; Если буфер не пуст (на выходе блока 12 — не нулевой вектор), на выходе дешифратора 14 — нулевой сигнал, а на выходе элемента НЕ 24 — единичный, по которому импульс с выхода схемы 20 сравнения проходит черед элемент И

29 и поступает на вторые входы всех элементов И 9, поэтому импульсу вектор с выхода блока 12 поступает на выход 32, формируя сигнал на том выходе, который

1709336

40 содержит вторую и третью группы элементов И, с третьего по пятый элементы .ИЛИ. 45

55 соответствует потоку, к которому принадлежит заявка, время ожидания которой истекло.

Сигнал с выхода элемента И 29 поступает также на элемент ИЛИ 5, проходя через который осуществляет (аналогично режиму четвертому) обнуление соответствующей ячейки блока 12 и запись текущего времени (не оказывающего влияния на работу устройства) в соответствующую ячейку блока

13, а также — в зависимости от соотношения содержимого счетчиков 16 и 17 — инкрементирование (или нет) счетчика 16.

Когда на входах 33 установлено нулевое сочетание сигналов (нулевая кодовая комбинация), работа данного устройства совпадает с работой устройства-прототипа.

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

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

35 мента задержки, выход которого подключен к счетному входу первого счетчика импульсов, выход четвертого элемента ИЛИ вЂ” к входам записи первого и второго блоков памяти, адресные входы которых соединены с выходами второго коммутатора, выходы таймера подключены к информационным входам второго блока памяти и к информационным входам первой группы блока вычитания, информационные входы второй группы которого подключены соответственно к выходам второго блока памяти, а выходы соединены соответственно с информационными входами первой группы первой схемы сравнения, информационные входы второй группы которой являются входами задания времени ожидания устройства, выход "Равно" первой схемы сравнения и выход элемента НЕ соединены соответственно с первым и вторым входами второго элемента И, выход которого подключен к первому входу пятого элемента ИЛИ и к первым входам элементов И второй группы, выходы которых являются выходами необслуженных заявок устройства, а вторые входы элементов И второй группы соединены соответственно с выходами первого блока памяти, с одноименными первыми входами элементов И третьей группы и с входами дешифратора, выход второго элемента ИЛИ соединен с первым входом третьего элемета И, с вторым входом пятого элемента ИЛЧ и с вторыми объединенными входами элементов И третьей группы, выход третьего элемента И вЂ” с единичным входом триггера,а второй вход третьего элемента И подключен к входу элемента НЕ и к выходу дешифратора, выходы элементов И первой и третьей групп соединены соответственно с первыми и вторыми входами соответствующих элементов ИЛИ группы, выходы которых подключены к входам запуска соответствующих генераторов случайных импульсов группы, разрядные выходы первого и второго счетчиков импульсов соединены соответственно с первыми и вторыми информационными входами второго коммутатора и второй схемы сравнения, выход "Неравно" которой и выход пятого элемента ИЛИ соединены соответственно с первым и вторым входами четвертого элемента И, выход которого через первый элемент задержки соединен со счетным входом второго счетчика импульсов, выход пятого элемента ИЛИ вЂ” с вторым входом четвертого элемента ИЛИ с управляющим входом первого коммутатора, информационные входы второй группы которого подключены к шине нулевого потенциала, а выходы соединены соответственно с информационными входами первого блока памяти.

1709336

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

Техред M.Ìoðãåíòàë Корректор Т. Малец

Редактор Н. Горват

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

Заказ 427 Тираж Подписное

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

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