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

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

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

На фиг.1 приведена схема предлагаемого устройства; на фиг.2 - схема блока синхронизации.

Устройство содержит генератор 1 тактовых импульсов, первый 2 и второй 3 генераторы случайной последо- ватёльности импульсов, второй 4, пер- вьй 5, третий 6, четвертый 7, пятый 8, седьмой 9 элементы И, первь й 10

и второй 11 элементы НЕ, первьш 12 и второй 13 генераторы случайных ин- -тервалов времени, шестой 14 и восьмой 15 элементы И, третий 16 и четвертый 17 элементы НЕ, первый 18 - четвертый 21 элементы ИЛИ, блок 22 синхронизации, реверсивный счетчик 23, первый 24 и второй 25 счетчики обслуженных заявок, дешифратор 26, третий 27, четвертый 28, первый 29 и второй 30 одновибраторы, первьй 31 и второй 32 элементы задержки, первый 33 и второй 34 блоки модели- - рования очередей заявок.

Блоки 33, и 34 моделирования очередей содержат первые 35, 36 и вторые 37,38 элементы ИЛИ, блоки 39 и 40 синхронизации, реверсивные счетчики

сл

(э

х

10

41 и 42, дешифраторы 43 и 44, элементы НЕ 45 и 46.

Блоки 22, 39 и 40 синхронизации предназначены для синхронизации момен с тов поступления импульсор на суммиру- (ощие -и вычитающие входы реверсивных . счетчиков 23, 41 и 42 соответственно, так как типовые реверсивные счетчики не допускают одновременной подачи импульсов на эти входы.

Блок синхронизации (фиг.2) содержит элемент НЕ 47, первый 48 и второй 49 триггеры с динамическими входами, первый 50 и второй 51 эле- .менты И, первый - четвертый одновибра- торы 52-55.

Работа устройства построена на следующей дисциплине. Заявки,пришедшие на обслуживание в двухканаль- ную ШО, присоединяются в результате сравнения длин очередей к более короткой очереди. При равенстве очередей заявка присоединяется к очереди, в которую она поступила. Если при поступлении очередной заявки очередь к соответствукмцему каналу достигла предельной длины, то в зависимости от результата анализа длины очереди смежного канала либо заявка присоединяется к смежной очереди, либо за- - явка отказывается в обслуживании при переполнении и этой очереди. Кроме того, так как возможно изменение соотношения длин очередей в процессе ожидания обслуживания, производится анализ количества заявок, находящих- ся в очередях. Если оказывается, что в очереди к смежному каналу находится меньшее число заявок, причем эта- разница равна (или больше) определенному заранее задаваемому числу, то заявка из длинной очереди переходит в более короткую.

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

: На выходах генераторов 2 и 3 слу-; чайных последовательностей импульсов формируются потоки коротких импульсов, имитирующие входящие в первый и вто- ; рой каналы СМО потоки заявок с заданными законами распределения времени между поступлением заявок. Предполо-

15

В случае равенства очередей на Q четвертом и третьем выходах дешифратора 26 имеется нулевой сигнал, указывающий, что соотношение L, L, и . Lj L неверны. Тогда на вводах элементов И 8 и 9 .нулевой сигнал.

Жим, что на первых входах элементов

И 4 и 5 присутствует единичный сигнал ..5 запрещающей присоединение заявки к

Также пусть первая очередь длиннее, смежной очереди, а на входах элеменчем вторая, на некоторую величину

IL 1 - L,, где L , и L /,, - длины

Первой и второй очередей соответст-

тов И 14 и 15 - единичный сигнал, что делает доступным каналы для заявок, поступивших на их входы. Тогда

0

0

;

венно. Тогда на четвертом выходе дешифратора 28 имеет нулевой сигнал, указывающий, что соотношение L L неверно, а на третьем выходе дешифратора 26 - единичньй сигнал, указывающий, что соотношение L,L2 верно. .В этом случае на первых входах элемен- тов И 9 и 14 имеется нулевой сигнал, а на первых входах элементов И 8 и 15 единичный сигнал, что делает доступным только второй канал. В результате .этого при наличии короткого импульса с выхода генератора 2 единичный 5 сигнал поступает через элементы И 8 и ИЛИ 21 на вход элемента ИЛИ 19, а при наличии короткого импульса с выхода генератора 3 единичный сигнал поступает через элементы И 5, И 15 и ИЛИ 21 также на вход элемента ИЛИ 19. С выхода последнего импульс поступает на второй вход блока 22 синхронизации.

В случае, если вторая очередь длиннее, чем первая, на величину IL т

5

0

., К, то на четвертом выходе дешифратора 26 имеется единичный сигнал указывающий, что соотношение L, L верно, а на третьем выходе дешифратора 26 - нулевой сигнал, указывающий, что соотношение .j неверно. В этом случае на первых входах элементов И 8 и 15 имеется нулевой сигнал, а на первых входах элементов

5 И 9 и 14 - единичный сигнал, что делает доступным только первый канал.

В результате этого при наличии короткого импульса с выхода генерато0 ра 2 единичный сигнал поступает через элементы И 4, И 14 и ИЛИ 20 на вход элемента ИЛИ 18, а при наличии короткого импульса с выхода генератора 3 единичный сигнал поступает че5 рез элементы И 9 и ИЛИ 20 также на вход элемента ИЛИ 18. С выхода элемента ИЛИ 18 импульс поступает на первый вход блока 22 синхронизации.

В случае равенства очередей на Q четвертом и третьем выходах дешифратора 26 имеется нулевой сигнал, указывающий, что соотношение L, L, и . Lj L неверны. Тогда на вводах элементов И 8 и 9 .нулевой сигнал.

смежной очереди, а на входах элементов И 14 и 15 - единичный сигнал, что делает доступным каналы для заявок, поступивших на их входы. Тогда

короткие импульсы с выходов генераторов 2 и 3 через элементы И А и 5, ИЛИ 14и15, 20и21, 18и19 соответственно поступают на первый и- вто рой входы блока 22 синхронизации. Непосредственно с выходов элементов ИЛИ 20 и 21 импульсы попадают на входы блоков 33 и 34 моделирования очередей и, пройдя через элементы ИЛИ 35 и 36, поступают на первые входы блоков 39 и 40 синхронизации.

Блоки синхронизации работают следующим образом.

Импульсы, приходящие на первый

(второй) вход блоков синхронизации по своему переднему фронту переводят триггеры 48(49) в единичное состояние На третий вход блоков синхронизации поступают импульсы высокой частоты от генератора 1 тактовых импульсов. По переднему фронту синхроимпульса на третьем входе блока синхронизации од- новибратор 55 выдает импульс фиксированной длительности. При наличии в этот момент единичного сиглала на выходе триггера 49 срабатывает элемент И 51, который запускает одновибратор 53. Импульс с выхода одновибратора 53 устанавливает по асинхронному вхо- ду триггер 49 в нулевое состояние и поступает на второй выход блока синхронизации. Импульсы на первом выходе блока формируются аналогично при наличии паузы на третьем входе блока.

Одновибраторы выбираются из условия, что сумма длительностей импульсов на выходах одновибраторов 52(53) и 54(55) не превьшает половины пери- ода импульсной последовательности генератора 1.

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

Рассмотрим процесс обслуживания заявок на примере первого канала. При наличии заявок в очереди к первому каналу СМО на.втором выходе дешифратора 43 присутствует логическая

5

JQ

ts

. 20 2530ч

до

дд 50

5

1. При достижении содержимым счетчика 41 значение, при котором«происходит ограничение длины очереди, на первом выходе дешифратора 43 появля.- ется единичный сигнал, который через элемент НЕ 45 поступает на первый выход блока 33 моделирования очереди заявок. Логический О с первого выхода блока 33 блокирует прохождение импульсов от генератора 2 через, элемент И 4, что соответствует отказу вновь поступающим заявкам в приеме на обслуживание из-за достижения очередью предельной длины. Но, если смежная очередь не достигла еще предельной длины, о чем свидетельствует единичный сигнал на первом входе элемента И 8 (т.е. справедливо соотношение L L), то осуществляется переход заявки во вторую очер1едь. Следующая вновь прибывшая заявка может избежать отказа в приеме на обслуживание в случае, если к моменту ее прихода .обьлу- жится хотя бы одна заявка в одном из каналов обслуживания.

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

При наличии заявок в очереди логическая 1 с выхода дешифратора 43 поступает на вход элемента И 6. Предположим, что на его втором входе в этот момент также присутствует 1. В этом случае сигнал с выхода элемента И 6 запускает генератор 12,. который формирует импульс случайной продолжительности. На выходе элемента НЕ 10 формируется пауза соответствующей длительности, которая блокирует прохождение сигнала через элемент И 6. По ее окончании одновибратор 27 выдает короткий импульс, который через элемент.ИЛИ 37 и блок 39 синхронизации поступает на вычитающий вход счетчика 41 и вход счетчика 24. Содержимое счетчика 41 уменьшается на единицу, что соответствует окончанию обслуживания заявки. Счетчик 24 фиксирует количество заявок, обслуженных первым каналом. Обслуживание заявок продолжается до тех пор, пока существует их очередь, т.е. содержимое счетчика 41 отлично от нуля. Обслуживание заявок .во втором канале происходит аналогично.

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

20

В начале процесса моделирования реверсивный счетчик 23 заносятся начальные условия - число К.

Импульсы с выхода элемента ИЛИ г 0 (заявки, принятые в очередь к перому каналу) и с выхода одновибратог - а 28 (заявки, обслуженные вторым каалом через элемент ИЛИ 18 и блок 22 синхронизации поступает на сумми- 10 рующий вход счетчика 23. Импульсы с выхода элемента ИЛИ 21 (заявки, принятые в очередь к второму каналу и с выхода одновибратора 27 заявки, обслуженные первым каналом через эле- 15 мент ИЛИ 19 и блок 22 синхронизации поступают на вычитающий вход. Запи-. санное в счетчике 23 число определят ется по формуле

L m,-m,,+ Р - Р, +К

где m - число заявок, принятых в очередь к первому и второму каналам обслу- 25 жив ания,СМО;

Р и Р - число заявок, обслуженных первым и вторым каналами;К - число, записанное в

счетчик перед началом работы устройства. Величиной К задается то значение разницы в дпинах очередей, которое служит поводом для перехода заявки в более короткую. Величина К может быть равной 2,3,4 и т.д.

Таким образом, в счетчике 23 оказывается число, равное сумме величины К и числа, равного значению, на которое различаются длины очередей к каналам СМО.

Так как число заявок, поступающих на обслуживание, распределяется на входе равномерно между каналами, то изменение соотношения длин очередей возможно только в результате неравномерности обслуживания заявок в различ ных каналах. Предположим, что соотно- шение числа заявок в очередях увели- чиваетсй в пользу первой очереди. При этом содержимое счетчика 23 увеличивается. Как только это содержимое станет равным величине 2К, на втором выходе дешифратора 26 появляется логическая 1 и на выходе одновибратора 30 формируется короткий импульс.

3toT импульс через элемент ИЛИ 37 и блок 39 синхронизации поступает на

30

35

40

45

50

0

0 5

5

0

5

0

5

0

вычитающий вход счетчика 41, через элемент ИЛИ 36 и блок 40 синхронизации он же подается на суммирующий вход счетчика 42,:

Содержимое счетчика 41 уменьшается на единицу, а содержимое счетчика 42 увеличивается на единицу, что соответствует переходу одной заявки из первой очереди во вторую.

Импульс с выхода одновибратора 30 через элемент ИЛИ 19 и блок 22 синхронизации поступйет на вычитаклций вход реверсивного счетчика 23 и через элемент 32 задержки, элемент ИЛИ 19 и блок 22 тоже на вычитающий вход счетчика 23. Время задержки элемента 32 больше длительности импульса, формируемого одновибратором 30. Содержимое счетчика 23, соответствукяцее разнице очередей плюс число К, уменьшается на два, что имитирует переход од- ной заявки из первой очереди во вторую. Первая очередь стала короче на одну заявку, а вторая - длиннее.

В случае, если очередь по второму каналу СМО оказывается длиннее очереди к первому каналу на К заявок, то на первом выходе дешифратора. 26 появляется логическая 1. Одновибра- тор 29 формирует короткий импульс, содержимое счетчика 42 уменьшается на единицу, содержимое счетчика 41 увеличивается на единицу, содержимое счетчика 23 увеличивается на два. Это соответствует переходу заявки из второй очереди в первую.

Регистрация количества заявок в очередях к первому и второму каналам СМО производится по показаниям реверсивных счетчиков 41 и 42 соответственно.:

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

I - ,

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

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

первого генератора случайной последовательности импульсов, выход второ- го одновибратора подключен к перво- .му входу второго элемента ИЛИ, к пер- вому входу исключения из очереди вто- jporo блока моделирования очереди и {первому входу исключения из очереди (первого блока моделирования очереди, ,выход переполнения которого подклю-, чем к первому входу второго элемента И, второй вход которого соединен с выходом второго генератора случайной последовательности импульсов, выходы первого и второго элементов задержки подключен к вторьт входам соответст- венно первого и второго элементов ИЛИ, выход наличия заявок в очереди первого блока моделирования очереди соединен с первым входом третьего элемента И, выход которого подключен к входу запуска первого генератора |Случайных интервалов вр емени, выход которого соединен с входом первого элемента НЕ, выход которого подключен к второму входу третьего :элемента И и входу запуска третьего одновибратора, выход которого соединен со счетным входом первого счетчика обслуженных заявок, третьим входом вто

Q 5 0 5 о

д 0 j

5

0

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

а выходы первого и второго генерато- соответственно пятого и седьмого эле- ра случайной последовательности им- ментов И. пульсов подключены к вторым входам

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

Фие.г

Редактор М, Бланар

Составитель В. Фукалов Техред Л.Олийнык

Корректор в. Кабаций