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

(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯСИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ(57) Изобретение относится к автоматике и вычислительной технике и предназначено для моделирования работысистем массового обслуживания. Цельизобретения - расширение функциональ. ных возможностей устройства за счет моделирования повторного возвращения заявок на обслуживание с заданной ве- роятностью. Цель достигается тем, что устройство в каждом канале обслуживания заявок содержит вероятностный коммутатор, а блок анализа ситуации дополнительно содержит блок элементов ИЛИ, регистр памяти, схему сравнения, блок элементов И, элемент запрета, узел поиска и узел очередей. Узел поиска состоит из группы триггеров, элемента И-НЕ и первой и второй групп элементов И. Устройство позволит получить число обслуженных заявок в первом и втором каналах и тем самым вычислить вероятностные харак-Е теристики данной системы обслуживанияс:Тираж 704 ВНИИПИ Государствен по делам изобрет 035, Москва, Ж, 43 Подписноого комитета СССР Зака нии и открытииаушская наб., дИзобретение относится к автоматике и вычислительной технике и пред-назначено для моделирования работысистем массового обслуживания.Целью изобретения является расширение Функциональных возможностейустройства за счет моделирования пов-:торного возвращения заявок на обспу"живание с заданной вероятностью. цНа фиг,1 приведена схема устрой"ства, на Фиг.2 - структурная схемакоммутатора" на фиг.З - схема вероятностного коммутатора, на Фиг,4 - схе=ма блока обслуживания," на Фиг.5 - схе-;5ма блока анализа ситуации; на Фиг,бсхема узла поиска; на Фиг.7 " схемаузла очередей.Устройство ддя моделирования систем массового обслуживания (Фиг,1)содержит два канала обслуживания заявок, в состав каждого из которых вхо."дит коммутатор 1, реверсивный счетчик 2, элемент ИХИ 3, первый эле-мент И 4, вероятностный коммутатор 5, 2-,второй элемент И 6, блок 7 обслуживания, блок 8 анализа ситуации, блок9 регистоации (каналы 10, и 10 обслуживания заявок).На Фиг.1 обозначены: вход 11 устройства, входы 12-14 коммутатора,выходы 15 и 16 коммутатора, выход 17элемента ИЛИ 3, выходы 18 и 19 вероятностного коммутатора, выходы 20 и21 блока обслуживания, выход 22 бло-.ка анализа ситуации, вход 23 устройства и выходы 24 реверсивного счет-.чика. В исходном состоянии реверсивные счетчики 2 обнулены,Коммутатор 1 (фиг.2) содержит элемент ИЛИ 25, элементы И 26-29, элеПмент ИЛИ 30, элементы 31-33 задерж.ки, элемент ИЛИ 34, элемент 35 запрета, выход 36 элемента ИПИ 25 ивыход 37 элемента ИЛИ ЗО.Вероятностный коммутатор 5 (фиг,З)содержит два генератора 38 и 39 импульсов, триггер 40 и два. элементаИ 41 и 42. Вероятностный коммутатор5 предназначен для обеспечения воз 0можностей заявке после обслуживанияс вероятностью р в дальнейшем не рассматриваться и с вероятностью (1-р)подвергнуться дальнейшему анализу ьразличных ситуациях.Блок 7 обслуживания (фиг. 4) содержит генератор 43 импульсов, регистр 44 сдвига, первый элемент 45задержки, генератор 46 случайных импульсов, группу элементов И 47, второй элемент 48 задержки, элемент ИЛИ49 и элемент И 50,Блок 8 анализа ситуации (Фиг. 5)содержит первый элемент ИЛИ 51, первый элемент И 52, узел 53 поиска,датчик 54 случайных кодов, регистр55 памяти, схему 56 сравнения, элемент 57 запрета, блок элементов И 58,бпок элементов 59 задержки, блок элементов ИЛИ 60 вход 61 схемы 56,узел62 очередей, связи 63-70 между элементами блока, В исходном состояниина регистре 55 записан код, соответствуюиий допустимому времени хранениязаявки в блоке решения.Узел 53 поиска содержит (Фиг. 6)элемент И-НЕ 71 группу триггеров 72,первую 73 и вторую 74 группы элементов И. В исходном состоянии все триггеры находятся в нулевом состоянии,а на выходе элемента И-НЕ 71 присутствует единичный потенциал,Узел 53 поиска. выполняет следующие функц 4 иеПрн наличии свободных мест в очереди (ячеек) узел 53 выдает сигнал,открывающий элемент И 52, состояниемест ожидания моделируется триггерами 72 узла 53, которые последовательно устанавливаются в состояние "1"сигналами с выхода элемента ИЛИ 51 ив состояние "О" сигналами с выходаузла 62 очередей.По сигналу с выхода элемента ИЛИ51 узел 53 выдает на две информационные шины узла 62 очередей сигнал озанятии одного из свободных мест вочереди, при этом в одной из этих шинсигнал подается с задержкой. При занятии заявками места ожидания в очереди на соответствующий вход узла 62 очередей подается единич, ный потенциал.Узел 62 очередей содержит (Фиг.7) генератор 75 тактов импульсов, первую группу элементов И 76, группу блоков 77 элементов И, группу вычитающих счетчиков 78, группу элементов 79 задержки, вторую 80 и третью 81 группы элементов И, первый 82 и второй 83 элементы 1 ПИ, четвертую группу эле" ментов И 84, группу триггеров 85 и группу выходов 86 узла, Узел 62 очередей предназначен для определения момента времени окончания анализа заявки и коьачутации ее в зависимостиот ситуации в первый или второй канал.Устройство работает следующим образом. 5Рассмотрим работу, например, первого канала обслуживания. На вход 11 поступают импульсы, имитирующие поток заявок. В случае отсутствия очереди, определенной в канале, сигнал о пос туплении заявки с выхода 15 коммутатора 1 поступает на суммирующий вход реверсивного счетчика 2 и на вход блока 7 обслуживания, где он по данному входу используется как вспомо гательный сигнал . При наличии очереди заявки поступают с выхода 16 коммутатора 1 на вход элемента И 6.Поступающие на входы коммутатора 1 (фиг.2) заявки (вход 11 - входной 20 поток, вход 12 - с второго канала обслуживания, вход 13 - с выхода блока 8) вначале попадают на элемент ИЛИ 25. В блоке предусмотрено устройство, не позволяющее потерять за явки, если они приходят одновременно по двум или трем входам. Если заявки,приходят одновременно по двум из трех входов, то наряду с сигналом, зафиксированным через элемент ИЛИ 25,30 происходит также фиксация сигнала одним из элементов И 26-28, и через элемент ИЛИ 30 и элемент 33 задержки второй сигнал поступает на один из выходов. Таким образом, в ревер-:. сивном счетчике 2 фиксируется поступление двух заявок. Если же заявки поступают по трем входам 11-13, то фиксируется поступление трех заявок: первой - через элемент ИЛИ 25, второй - через один из элементов И 26- 28, элемент ИЛИ 30 и элемент 33 задержки, третьей - через элемент И 29 и элементы 31 и 32 задержки.Заявки уходят из коммутатора 1 или через элемент 35 запрета при отсутствии очереди допустимой длины, или непосредственно с выхода элемента ИЛИ 34 при наличии очереди допустимой длины, В последнем случае на ,управляющий вход элемента 35 запрета подается сигнал с выхода задатчика ограничения очереди (элемента И 4), который фиксирует определенную длину очереди на реверсивном счетчике 2, При срабатывании элемента И 4 сигнал с его выхода поступает на. вход элемента 35 запрета для переключения выходов коммутатора 1 и одновременно подается на вход элемента И 6, подготавливая его к открытию. В этом случае заявки с выхода 1 Ь коммутатора 1 поступают на вход элемента И 6 и далее с его выхода на первый вход второго канала обслуживанияВо втором канале обслуживания, построенном аналогично первому, заявки проходят обслуживание, Необслуженная по каким-либо причинам во втором канале заявка возвращается в первый канал по входу 12 коммутатора 1.Если очередь, зафиксированная в реверсивном счетчике 2, меньше установленной предельной величины, элемент И 6 закрыт, а элемент 35 запрета открыт, и заявки поступают на выход 15. Наличие очереди фиксируется элементом ИЛИ 3. Если в очереди имеется хотя бы одна заявка, то сигнал об этом с выхода элемента ИЛИ 3 подается в блок 7 обслуживания, где происходит (фиг.4) включение генератора 46,имитирующего случайное время обслуживания заявки, Пока на выходе элемента ИЛИ 3 есть сигнал, генератор 46 включен. Время между случайными импульсами с генератора 46 принимается за время обслуживания очередной заявки.Кроме генератора 46, имитирующего время обслуживания заявки, основными элементами блока 7 обслуживания являются также генератор 43 тактовых импульсов, регистр 44 сдвига и элемент ИЛИ 49. Они служат для запоминания на допустимое времязаявки, поступившей в блок 7 обслуживания. Это время устанавливается путем продвижения вспомогательного сигнала по регистру импульсами сдвига от генератора 43, поступающими на вход регистра 44, Вспомогательный сигнал в блок 7 поступает с выхода 15 коммутатора 1, Если за допустимое время с генератора 46 поступает сигнал о завершении обслуживания очередйой заявки, то она считается обслуженной, и сигнал об этом проходит на выход 2 1 блок 7 обслуживания. Время определяется разрядностью регистра 44 и частотой тактовых импульсов.Для обеспечения прохождения сигнала об обслуживании заявки на выход 21 блока 7 с выхода генератора 46 в регистр сдвига поступает импульс, который используется для селективного гашения вспомогательного сигнала, поступившего с выхода 15 коммутатора и. продвигаемого по регистру. Гашение вспомогательного сигнала происходит следующим образом.Если в единичном состоянии находится и-й разряд регистра 44, то на первом входе соответствующего элемента И 47 группы присутствует разрешаю" щий потенциал с выхода этого разряда. Тогда при появлении импульса сгенератора 46 на втором входе этогоэлемента И он проходит на нулевой,вход и-го разряда регистра 44 и че,рез элемент ИЛИ 49 на вход элементаИ 50. На другой вход элемента И 50поступает тот же импульс с генератора 46 через элемент 48 задержки. Если к моменту появления сигнала с ге.нератора 46 и-й разряд регистра 44находится в нулевом состоянии то разрешающий сигнал имеется на инверсном выходе этого разряда и импульс с генератора 46 проходит на соответствующие два элемента И 47 группы (и)-го разряда. Если (и"-1)-й разряд регистра 44 был в единичном состоянии, то он обнуляется, В против.ном случае сигнал с генератора 46 передается на следующий (и)-й разряд, т.е. поиск ближайшего разряда регистра 44 с единичным состоянием продолжается.С выхода 21 блока обслуживания сигнал о конце обслуживания заявки за время, меньшее или равное максимально допустимому, подается на входкоммутатора 5, Если за допустимоевремя в регистр 44 не поступает импульс с генератора 46, то заявка считается необслуженной. В этом случаесигнал об отказе в обслуживании поступает с выхода последнего разрядарегистра 44 через соответствующийэлемент И 47 на выход 20 блока 7 идалее на вход блока 8. Обслуженная в блоке 7 заявка в вероятностном ком мутаторе (фиг.3) подвергается анализу, в результате которого она можетс некоторой вероятностью (1-р) уйтив блок 8 анализа ситуации на повтор"ное обслуживание - на выход 18 ком" мутатора 5. Вторая возможность заклю" чается в том, что заявка .с вероятностью р уходит с обслуживания - навыход 19 коммутатора 5. С выхода 19сигнал о конце обслуживания заявки подается на вычитающий вход реверсивного счетчика 2 для снятия заявки с учета из системы обслуживания и на суммирующий вход реверсивного счетчика блока 9 регистрации.Необслуженная в блоке 7 или распределенная на повторное обслуживание коммутатором 5 заявка в блоке 8проходит анализ ситуации (фиг. 5).В результате анализа заявка может снекоторой вероятностью о после некоторого времени уйти во второй каналобслуживания - выход 22 блока 8. Вторая воэможность заявки состоит в том,что она с вероятностью (1-с 1) послеанализа возвращается в прежний каналобслуживания через .коммутатор 1 повходу 13. В обоих случаях заявка,покидая блок 8, снимается с учетаданного канала через вычитающие входы реверсивного счетчика 2. Когда заявка покидает данный канал обслуживания, уходя в другой канал, то сигнал об этом выдается на вычитающийвход реверсивного счетчика блока 9,фиксируя тем самым уход данной заявки из системы обслуживания,Блок 8 (фиг.5) работает следующимобразом,Поступающая по входам 18 и 20 заявка подается на вход узла 53, имитируя поиск свободных мест (ячеек) вочереди на обслуживание, и проходитчерез элемент И 52 на вход выдачирегистра 55 и вход датчика 54 случайных кодов. В узле 53 поиска производится поиск свободной ячейки(места) (состояния ячеек "Занято",Свободно" моделируются триггерами),занимается один из триггеров 72, т.е,один из этих триггеров из состояния"0" переводится в состояние "1".Каждая ячейка состоит из триггера 72 идвух элементов И 73 и 74. При этомузел 53 выдает сигнал занятости наодин из информационных входов второйи третьей групп входов узла 62 очередей.Узел 53 поиска (фиг. 6) работаетследукпцим образом.Триггеры 72 имитируют состояниемест ожидания моделируемой системымассового обслуживания. Поступлениеочередной заявки на обслуживание соответствует занятию свободной ячейки,Этот процесс имитируется появлениемсигнала на входе 64, который последовательно опрашивает элементы И 74 ипроходит через один из них на триггер 72, при этом триггер 72 перебра"сывается в единичное состояние, чем7 14325 имитируется занятие места ожидания в очереди. Единичный потенциал соответствующего занятой К-й ячейке выхода 69 узла поиска подается на К-й вход первой группы входов .узла 62 очередей. При завершении времени пребывания заявки поступает высокий потенциал на одну из шин входов 86, устанавливая соответствующий триггер 72 в нулевое состояние, имитируя освобождение ячейки (места) в очереди.В случае, когда все места в очереди заняты, сигнал с выхода элемента ИЛИ 51 после опроса всех элементов15 И 73 поступает на выход 22 блока 8,. При этом на выходе элемента И-НЕ 1 сигнал отсутствует, закрывая элемент И 52.С приходом сигнала ка вход блока 8 датчик 54 случайных кодов генери 20 рует код числа, который поступает на вход элемента 5 запрета и на группу входов схемы 56 сравнения, на другую группу входов которых по этому же сигналу поступает код,числа с выхода регистра 55. Кроме того, с выхода регистра 55 код числа поступает на вход элемента И 58. Если число на выходе датчика 54 30 случайных кодов больше числа, записанного в регистре 55, то на выходе схемы 56 сравнения формируется признак, который .запирает элемент 57 запрета и открывает элемент И 58, В результате этого код числа из ре-гистра 55 записывается через элемен- ты И 58 и ИЛИ 60 в один из счетчиков 78 узла 62 очередей, В противном случае в один из счетчиков 78 узла 62 40 очередей через элементы запрета 57 и ИЛИ 60 записывается число с датчика 54 случайных кодов.В узле 62 очередей производятся хранение заявки случайное время, оп ределяемое числом, записанным в соответствующий счетчик 78, и частотой генератора 75 импульсов, и пересылка заявки после истечения укаэанного времени во второй или данный канал обслуживания.Очередные заявки в виде случайных двоичных чисел, значение которых соответствует времени ожидания заявки, поступают по входной шине 70 на все элементы И 77 второй группы. Один из элементов И 77 группы открывается .сигналом, поступающим из узла 53 поила по одному из входов 67, и число 51 8записывается в счетчик 78, Вычитающие входы счетчиков 78 через элементы И 76 первой группы соединены с выходом генератора 75 импульсов, Элементы И 7 б,управляются сигналами,поступающими из узла 53 поиска по входамЪ69. Эти сигнапы присутствуют до тех пор, пока заявка находится на этапе ожидания. Счетчики 78 содержат текущее значение оставшегося времени обслуживания.Когда время ожидания одной из заявок заве 1 шается, соответствующий счетчик 78 переходит в нулевое состояние, При этом на его выходе появляется импульс, который по одному из выходов 86 поступает в узел 53 поиска и устанавливает соответствующий триггер 72 в нулевое состояние; поступает через элемент 79 задержки на вход элемента И 80 группы и далее через элемент ИЛИ 82 на выход 13 блока, поступает через элемент 79 задержки на вход элемента И 81 четвертой группы и далее через элемент ИЛИ 83 на выход 22Коммутация этого импульса на тот или другой выходы узла 62 очередей обеспечивается соответствующим триггером 85 и элементом И 84.Заявки, поступившие в блок 62 очередей в виде двоичных кодов, значение которых соответствует допустимому времени пребывания, хранятся в вычитающих счетчиках блока. Величина этого времени определяется либо числом на выходе датчика 54 случайных кодов, либо числом, установленным на регистре 55.Со схемы 56 сравнения в узел 62 очередей по входу 65 поступает сигнал яа все входы элементов И 84, характеризующий тот факт, что число, поступившее на схему 56 сравнения, большечисла, поступившего из регистра 55. Через один из этих элементов И 84 проходит сигнал, поступивший через элемент 59 задержки из узла 53 поиска по одному из входов 68, и переводит соответствующий триггер 85 в единичное состояние, имитируя процесс ухода заявки во второй канал обслуживания. При этом по окончании анализа происходит возвращение соответствующего триггера 85 в нулевое состояние импульсом, проходящим через элемент И 80. Этот же сигнал поступает также на вычитающий вход реверсивного счетчика блока 9, где регистрируется как определенные потери для данного канала обслуживания, 1432551Если сигнал с выхода схемы 56 сравнения не поступает в узел б 2 очередей, то считается что заявка проходит через элементы И 81 и ИЛИ 83 на вход 13 коммутатора 1. В этом слуЧае заявка остается в прежнем канале обслуживания.Аналогично работает второй канал .Второй канал обслуживания выпал Йен так же, как и первый. Для придания ему свойств с другими характеристиками достаточно изменить количестно элементов в группах блоков поиска И блока очередей, частоту генератора 15 Импульсов или разрядность регистра одвига. Формула из обретения20Устройство для моделирования систем массового обслуживания, содержаЩее два канала обслуживания заявок, каждый из которых содержит коммутатор, реверсивный счетчик заявок, раз рядные выходы которого подключены соответственна к входам элемента ИЛИ и входам первого элемента И, второй элемент И, блок регистрации, блок обслуживания и блок анализа ситуации, 30 содержащий блок элементов задержки, первый элемент И, датчик случайных кодов и элемент ИЛИ, первый выход коммутатора в каждом канале обслуживания заявок соединен с вхоцом разре- З 5 шения обслуживания блока обслуживанИя и суммирующим входом реверсивного счетчика заявок, выход первого элемента И подключен к первому входу второго элемента И и первому информационному входу коммутатора, второй информационный вход которого является входом поступления заявок устройства, второй выход коммутатора соединен с вторым входом второго элемента И, выход второго элемента И и первого канала обслуживания заявок подключен к второму информационному входу коммутатора второго канала обслуживания заявок, выход элемента ИЛИ соединен с входом разрешения работы блока обслуживания, о т л и ч а ю щ е е с я тем,что, с целью расширения функциональных возможностей,за счет моделирования повторного возвращения зая 55 вок на обслуживание с заданной вероятностью, оно дополнительно содержит в каждом канале обслуживания за. явок вер.1 ятностный коммутатор, а блок анализа ситуации дополнительносодержит блок элементов ИЛИ, регистрпамяти, схему сравнения, блок элементов И, элемент запрета, узел поиска и узел очередей, узел поискасостоит из группы триггеров, элемента И-Н 1. и первой и второй групп элементов И, прямые выходы триггеровгруппы соединены соответственно спервыми входами элементов И первойгруппы, а инверсные выходы триггеровгруппы подключены соответственно кпервым входам элементов И второй группы, выход первого элемента ИЛИ блокаанализа ситуации подключен к первомувходу первого элемента И блока анализа ситуации и вторым входам первыхэлементов И первой и второй группузла поиска, в каждом узле поиска вытход К-го элемента И первой группы(К=1, 11-1, где М - число очередей)соединен с вторым входом (К+1)-гоэлемента И первой группы и вторымвходом (К+1)-го элемента И второйгруппы, выходы элементов И второйгруппы подключены соответственно кединичным входам триггеров группы узла поиска, узел очередей содержит генератор тактовых импульсов, первую,вторую, третью и четвертую группыэлементов И, группу элементов задержки, группу вычитающих счетчиков, группу триггеров, группу блоков элементов И, первый и второй элементы ИЛИ,в узле очередей выход генератора тактовых импульсов подключен к первымвходам элементов И первой группы,выходы которых подключены соответственно к вычитающим входам вычитающих счетчиков, разрядные входы которых подключены соОтветственно к выходам блоков элементов И группы, выхо"ды обнуления вычитающих счетчиковсоединены через соответствующие элементы задержки группы с первыми входами элементов И второй и третьейгрупп, выходы элементов И второй группы соединены соответственно с входамипервого элемента ИЛИ, а выходы эле"ментов И третьей группы подключенысоответственно к входам второго элемента ИЛИ, выходы элементов И четвертой группы соединены соответственно с единичными входами триггеровгруппы, нулевые входы которых подключены соответственно к выходам элементов И второй группы, прямые выходытриггеров группы соединены соответст"11 14 венно с вторыми входами элементов И третьей группы, а инверсные выходы триггеров группы подключены соответственно к вторым входам элементов И второй группы, прямые выходы триггеров группы узла поиска соединены соответственно с вторыми входами элементов И первой группы узла очередей и входами элемента И-НЕ узла поиска, выход которого объединен с выходом второго элемента ИЛИ узла очередей и подключен к первому вычитающему входу реверсивного счетчика своего канала обслуживания заявок, а выход первого элемента ИЛИ узла очередей подключен к второму вычитающему входу реверсивного счетчика заявок своего канала обслуживания заявок и третьему информационному входу коммутатора своего канала обслуживания заявок, в каждом канале обслуживания заявок выход необслуженных заявок блока обслуживания подключен к первому входу первого элемента ИЛИ блока анализа ситуации, второй вход первого элемента ИЛИ которого подключен к первому выходу вероятностного коммутатора своего канала обслуживания заявок, второй выход которого соединен с первым информационным входом блока регистрации своего канала обслуживания заявок и третьим вычитающим входом реверсивного счетчика заявок своего канала обслуживания заявок, выход обслуженных заявок блока обслуживанияв каждом канале обслуживания заявок подключен к информационному входу вероятностного коммутатора, а выходы обнуления реверсивных счетчиков группы узла очередей подключены соответственно к нулевым входам триггеров группы узла поиска, выходы элементов И второй группы которого соединены соответственно с входами блока элементов задержки блока анализа ситуации и управляю 32551 12щими входами блоков элементов И группы узла очередей, информационные входы блоков элементов И которого подключены соответственно к выходам блока элементов ИЛИ блока анализа ситуации, первая и вторая группы входовкоторого соединены соответственно свыходами элемента запрета и блока 10 элементов И блока анализа ситуации,выходы блока элементов задержки блока анализа ситуации подключены соответственно к первым входам элементовИ четвертой группы узла очередей, авыход первого элемента И блока анализа ситуации подключен к входу запуска датчика случайных чисел и входу считывания регистра памяти, разрядные выходы датчика случайных чисел соединены соответственно с информационными входами элемента запретаи информационными входами первойгруппы схемы сравнения, информационные входы второй группы которой под ключены соответственно к разряднымвыходам регистра памяти и информационным входам блока элементов И, выход "Больше" схемы сравнения подключен к управляющему входу элементазапрета и управляющему входу блокаэлементов И, а разрядные входы регистра памяти являются установочнымивходами устройства, выход второгоэлемента ИЛИ узла очередей первогоканала обслуживания заявок соединенс вторым информационным входом блокарегистрации своего канала обслуживания заявок и четвертым информационнымвходом коммутатора второго канала обслуживания заявок, выход второго элемента ИЛИ узла очередей которого подключен к четвертому информационномувходу коммутатора первого канала обслуживания заявок, а выход "Больше"схемы сравнения блока анализа ситуации подключен к вторым входам элементов И четвертой группы узла очередей.