Устройство для моделирования процесса обслуживания заявок Советский патент 1992 года по МПК G06F15/20 

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

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

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

Недостатком известных устройств является низкая точность моделирования

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

Поставленная цель достигается тем, что в устройство для моделирования процесса обслуживания заявок, содержащее счетчик импульсов, суммирующий вход которого является входом заявок устройства, три элемента И, триггер, единичный выход которого соединен с инверсным входом первого элемента И, три элемента ИЛИ, блок счетчиков импульсов, дешифратор, два элемента задержки и Две модели обслуживающего прибора, каждая из которых включает триггер, элемент И и генератор импульсов со случайным интервалом следования, выход которого соединен с соответствующим входом блока счетчиков импульсов и единичным входом триггера, прямой выход которого подключен к первому входу элемента И, выход которого соединен с нулевым входом триггера и входом запуска генератора импульсов со случайным интервалом следования, выход первого элемента задержки соединен с прямым входом первого элемента И, выход которого подключен к второму входу элемента И перVJ00 4 Ю Ю СЛ

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

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

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

Устройство содержит счетчик 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.

Поток заявок на обслуживание, поступающих на вход 16, представляет случайную последовательность коротких импульсов. Модели 11, 12 и 24 имитируют один обслуживающий прибор, закон распределения случайных импульсов на выходе генераторов один и тот же, но с разными параметрами. Временной интервал от момента запуска модели до появления импульсов на их выходе случаен и распределен по

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

Времена элементов 7, 18 и 22 задержки выбираются из условия . исключая тем самым появление сдвоенных заявок при переключениях моделей обслуживающего прибора.

Вербальная модель работы устройства сводится к следующему: при поступлении заявки на обслуживающий прибор производится ее обслуживание в первой МОП со

средним временем обслуживания Т1 (т.е. со скоростью vi). При поступлении очередной заявки в момент нахождения предыдущей на обслуживании, она становится в очередь и т.д. Если длина очереди достигает NI зая- вок, то происходит переключение на вторую модель обслуживающего прибора со средним временем обслуживания Т2 (т.е. со скоростью va), а первая МОП заявки на обслуживание не принимает. Если длина очереди достигла максимального допустимого размера N2, а в момент поступления очередной заявки предыдущая находится на обслуживании, то такая заявка к обслу-. живанию не принимается, в очередь не ста- новится, но фиксируется (считается) счетчиками потерянных заявок. Если за вре- мя обслуживания очередной заявки было потеряно системой до № -1 заявок включительно (что определяется первым счетчи- ком), то переключения МОП не происходит и система продолжает обслуживание заявок со скоростью V2. Если же за время обслуживания очередной заявки системой было потеряно N3 заявок и более, то происходит переключение на третью модель обслужи,ва- ющего прибора со средним временем обслуживания Тз (т.е. со скоростью УЗ), а первая и вторая модели заявок не принимают. При уменьшении длины очереди до h заявок,где

h Ni, Ni + 1N2-2,(1)

происходит переключение с третьей модели обслуживающего прибора на вторую, а при уменьшении длины очереди до NI - 1 зая- вок прбисходит переключение со второй модели обслуживающего прибора на первую. Переключение с третьей модели обслуживающего прибора происходит тогда, когда в очереди остается h заявок (при этом обнуляется первый счетчик 21).

Описанная выше логика переключений первой, второй и третьей МОП совместно с неравенством Ti Та Тз позволяет более точно в сравнении с прототипом выбирать скорость обслуживания заявок в зависимости от длины очереди и оценивать вероятностные показатели процесса функционирования обслуживающего прибора. Кроме того, такая модель СМО более адек- ватна реальным иерархическим СМО, у которых обслуживающие приборы верхнего иерархического уровня подключаются в том случае, если обслуживающие приборы нижних уровней не справляются с потоком заявок. Поскольку обслуживающий прибор верхнего иерархического уровня (в данном случае- МОП 24) в обычном режиме занят обслуживанием своих заявок, то в случае привлечения его в данную СМО, мзксимизируе ся его эффективность: то есть, если без него терялось небольшое количество заявок, то он подключается на малое время; если же без него система катастрофически не справлялась с потоком, то обслу- живающий прибор высокого уровня подключается на длительное время. Показателем того на сколько система плохо справляется с потоком .заявок, является состояние счетчика 26.

Устройство работает следующим образом. После включения устройства счетчики 1, 17, 21, 26 устанавливаются в нулевое состояние, а триггеры 3 и 23 в исходное состояние. Заявки поступают на суммирующий вход счетчика 1, разрядные выходы которого соединены с соответствующими входами первого дешифратора 2, число которых n, a число выходов - N2 2П, которые подключены к соответствующим входам элемента ИЛИ 8, чем имитируется процесс организации очереди заявок длиной N2,

Таким образом, при поступлении импульса на суммирующий вход счетчика 1, имитирующего поступление заявки на обслуживание, на первом входе счетчика 1 появляется потенциал, который через первый вход - первый выход дешифратора 2 поступает на второй вход элемента ИЛИ 9, а с его выхода через элемент задержки 7 - на прямой вход элемента И 4, инверсный вход которого соединен с прямым выходом триггера 3, на котором в исходном состоянии напряжение отсутствует, т.е. элемент И 4 открыт, а элемент И 6 закрыт, поскольку в исходном состоянии на выходе триггера 23 установлен О. С выхода элемента И 4 импульс поступает на второй вход открытого элемента И 13 МОП 11, а с его выхода - на нулевой вход триггера 14, переводя его в нулевое состояние, закрывая тем самым вход элемента И 13, и также поступает на вход запуска генератора 15, имитируя начало обслуживания заявки. Через случайный интервал времени, соответствующий продолжительности обслуживания заявки, вырабатывается импульс, который поступает на единичный вход триггера 14, перебрасывая его в исходное состояние и открывая тем самым элемент И 13.

С выхода генератора 15 модели 11 импульс имитирует обслуженную заявку и поступает на соответствующий вход блока счетчиков 17 и элемента ИЛИ 10, а с выхода элемента ИЛИ 10-на второй вход элемента И 5, обеспечивая этим прохождение следующей заявки на обслуживание через первый вход элемента И 5, подключенного к выходу элемента ИЛИ 8, С выхода элемента ИЛИ 10 импульс также поступает на вычитающий вход счетчика 1, в котором записанное ранее число уменьшается на единицу. С выхода элемента И 5 в случае, если в счетчике 1 еще имеется хотя бы один заполнен- ный разряд, импульс через первый вход-выход элемента ИЛИ 9 поступает через элемент 7 задержки на прямой вход элемента И 4, далее устройство работает по описанной схеме. Аналогично работает устройство при нахождении в очереди заявок до NI - 1 включительно. При достижении в очереди заявок NI, импульс с Ni-ro выхода дешифратора 2 поступает на единичный вход триггера 3, переводя его в состояние 1, при котором элемент И 4 закрывается, а элемент И 6 открывается по второму входу (третий вход открыт), а на первый вход элемента И 6 поступает импульс с выхода элемента И 5 через элемент задержки, имитирующий поступление из очереди следующей заявки на обслуживание. Этот импульс с выхода элемента И 6 проходив элемент И 13 модели 12 и переводит триггер 14 в нулевое состояние, закрывая элемент И 13, и запускает генератор 15 модели 12, имитируя начало обслуживания заявки Через случайный интервал времени, соответствующий продолжительности обслуживания заявки, вырабатывается импульс, который поступает на единичный вход триггера 14, переводящего в исходное положение, открывая элемент И 13 модели 12 Далее устройство работает при наличии, в очереди заявок от NI до (№ -1) аналогично описанному, при наличии в очереди N2 заявки (свободных мест в очереди нет), вновь поступающие заявки получают отказ, однако их количество фиксируется (подсчитывается) счетчиком 26 через открывшийся элемент И 19.

Если Число потеря иных за явок за время обслуживания очередной заявки (фиксируемое счетчиком 21) достигает величины N3, то триггер 23 переключается в состояние Т на прямом выходе, что вызывает по третьему входу элемента И 6 и готовит к включению элемент И 20 После обслуживания заявки, импульс с выхода второй МОП 12 через элемент ИЛИ 10 поступает на вычитающий вход счетчика 1 и на элемент И 5 При этом число заявок в счетчике 1 уменьшается до N2 - 1, и очередная заявка поступает на обслуживание в третью МОП 24, а счетчики 21 и 26 продолжают подсчет потерянных заявок. Если среднее время ТЗ обслуживания заявок в МОП 24 меньше, чем средний интервал времени между заявками, поступающими на вход 16, то через некоторое время число заявок в очереди уменьшится до величины N2-2 и так далее-до величины

h (см. (1)). При этом (по достижении величины h) счетчик 21 обнуляется, что вызовет переключение в О триггера 23 и, соответственно, отпирание по третьему входу элемента И 6, т е. произойдет переключение с МОП 24 на МОП 12.

При дальнейшем уменьшении очереди по мере обслуживания заявок, при достижении длины очереди величины NI -1 заявок,

происходит обратное переключение моделей, т.е. импульс с (Ni - t)-ro выхода дешифратора 2 переводит триггер 3 в состояние, при котором открывается элемент И 4 и закрывается элемент И 6. Если в момент переключения с модели 12 на модель 11 закончится обслуживание заявки в модели 12, то чтобы не было размножения заявок, используются элементы 18 и 7 задержки, аналогично используются элементы задержки 18 и 22 для предотвращения размножения заявок при переключении модели 12 на модель 24. При этом должны выполняться

УСЛОВИЯ И .

Мультиплексор (коммутатор) 27 выполнен таким образом, что при нулевом адресе на выходе счетчика 26 он коммутирует на выход (N2 - 2)-й выход дешифратора 2, а при максимальном значении счетчика 26 он коммутирует на выход NI-Й выход дешифратора

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

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

Учит интенсивности потока потерянных заявок позволяет с учетом большего числа

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

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

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

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