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

1

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

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

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

Устройство содержит каналы обслуживания заявок, каждый из которых

состоит из генератора 1 случайного потока заявок, первого элемента И 2, триггера 3, второго элемента И 4, делителя 5 час готы, четвертого элемента И 6, второго элемента ИЛИ 7, первого 8 и второго 9 элементов запрета, блока 10 элементов И, реверсивного счетчика 11, первого элемента ШШ 12, элемента НЕ 13, третьего элемента И 14 и блока 15 случайной временной задержки. В состав устройства входят также второй элемент И 16, элемент НЕ 17, элемент 18 задержки, третий элемент И 19, генера

ю

тор 20 импульсов, элемент ИЛИ 21, реверсивный счетчик 22 и первый элемент И 23.

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

Функция приоритета заявок i-ro канала обслуживания имеет вид

hjCt) fj(t-t-;), где t - текущий момент времени,

ЕГ; - момент поступления заявки в каналу

f; - частота импульсов в канале на выходе делителя 5.

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

Для каждого канала вводится разностная функция приоритета

Ri(t) H(t)-h(t).

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

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

5

0

5

0

мента 8 и 9 запрета, которые запрещают прохождение сигнала на один из этих входов счетчика в случае наличия сигнала на другом. Для устойчивой работы реверсивного счетчика 11 необходимо, чтобы импульсы на его суммирующий и вычитающий входы проходили или в разное время, не накладываясь друг на друга даже частично, или проходили строго в один и тот же момент, имея одинаковую длительность, а также полностью взаимно уничтожались элементами 8 и 9 запрета каналов. Это достигается введением общего для всех каналов генератора 20 импульсов и делителя 5 частоты на каж- дьй канал. Делителя 5 частоты построены на базе счетчиков с принудительным насчетом и начальной установкой. В качестве выходного сигнала делителя 5 частоты используется сигнал переполнения, который жестко привязан по времени к входному сигналу делителя 5 частоты, повторяет его по длительности, но выдается в Mj. раз реже. Для обеспечения соотношения собственных частот каналов f, f 2 f,,, „ модули счета делителей 5 частоты выбираются так, что

Мсч.

М

СЧц

5

0

5

0

5

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

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

5

нулевой потенциал с инверсного выхода триггера 3. Элемент НЕ 13 и элементы И 14 каналов обеспечивают единственность лидера в любой момен времени. Лидером будет канал, имеющий нулевой сигнал на выходе элемента ИЛИ 12, а если таких каналов в данный момент несколько, то лидером станет тот из них, у которого мень- ший порядковый номер и, следовательно, большая частота. Только лидер через слой открытый элемент И 6 подает импульсы со своего делителя 5 частоты на суммирующие входы ревер- сивных счетчиков 11 всех каналов обслуживания-заявок устройства. И только в канале, являющемся лидером, на входе блока 15 случайной временной задержки, имитирующего обслужи- вашщий прибор, появляется единичный потенциал, свидетельствующий о том, что заявка данного типа поступает на обслуживание.

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

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

На момент конца поиска на ревер- сивных счетчиках 11 всех каналов находятся разности между функцией приоритета нового лидера и функцией приоритета данного канала, а на реверсивном счетчике 22 - сама ф унк- дня приоритета нового лидера. Импуль сы поисковой частоты не должны накладываться по времени на импульсы собственной частоты каналов, так как и те и другие приходят на вычитающие входы реверсивных счетчиков 11. Это достигается тем, что генератор 20 ИМПУЛЬСОВ вырабатывает прямоуголь

996

ные импульсны со скважноегью больше 2, а импульсы поиска получаются из них сдвигом на половину периода, который осуществляется элементом 18 задержки таким образом, что импульсы поиска не будут накладываться на импульсы генератора 20, а значит и на выходные импульсы делителей 5 частоты каналов. Из этого следуют требования к генератору 20 импульсов: он должен вырабатывать прямоугольные импульсы со скважностью больше 2, период которых должен быть вдвое больше того интервала времени, который необходим для завершения переходных процессов в реверсивных счетчиках. Время поиска нового лидера в рассматриваемом случае зависит от превьшзения частоты импульсов поиска над собственной частотой каналов, т.е. величины модулей счета делителей 5 частоты Приоритентность каждого канала зависит не от абсолютного значения его собственной частоты, а от соотношения этого значения с собственной частотой других каналов. Поэтому модуль счета делителя 5 частоты первого канала, имеющего максимальную собственную частоту, . выбирается таким, чтобы обеспечить значительное превьш1ение частоты поиска над собственной частотой первого канала, а модули счета остальных каналов выбираются с учетом этого значения в соответствии с неравенством

Мсч,М„.:,., М

сч

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

В исходном состоянии триггеры 3 всех каналов обслуживания заявок находятся в нулевом состоянии. На выходе элемента И 16 присутствует единичный потенциал, характерный только для исходного состояния. Еди- кицный потенциал с инверсных выходов триггеров 3 каналов подводится на установочные входы реверсивного счетчика 22 и реверсивных счетчиков 11 каналов, что приводит к установлению на разрядных выходах этих счетчиков нулевых кодов. Кроме того, этот же сигнал подается на входы-начальной установки делителей 5 частоты каналов и на последние входы эле- , ментов ИЛИ 12 каналов. Поэтому на ходах элементов ИЛИ 12 всех кана

лов в исходном состоянии присутствуют единичные потенциалы. А это значит, что на выходах элементов НЕ 13 и, следовательно, на выходах элемен- тов И 14 присутствуют нулевые потенциалы. Прохо5кдение импульсов . с генератора 20 импульсов блокируется закрытыми элементами И 4 всех каналов, так как на их первых входах находят- ся нулевые потенциалы, и закрытым элементом И 19, так как на его вход в исходном состоянии с выхода элемента НЕ 17 подается нулевой потенциал.

Допустим, что на выходе генератор 1 случайного потока заявок k-го канала, имитирующего входной поток заявок на обслуживание, k-го приоритетного класса, появился импульс-заявка который, пройдя через свой открытый элемент И 2, устанавливает триггер 3 данного канала в единичное состояние, В результате этого на выходе элемента ИЛИ 12 k-ro канала появляется нулевой потенциал, так как на всех его входах присутствуют нулевые потенциалы. Поэтому на выходе элемента НЕ 13 данного канала появляется единичный потенциал, что приводит к .тому, что на выходе элемента И 14 k-ro канала, если это не первый канал, появляется единичный потенциал, так как на всех его входах в этом случае присутствуют единичные потенциалы.. Таким образом, на вход блока 15 случайной временной задержки по- ступает единичный сигнал, который свидетельствует о том, что заявка k-ro типа поступила на обслуживание, т.е. k-й канал стал лидером. ..

Кроме того, нулевой потенциал с инверсного выхода триггера 3 k-ro .канала закрывает элемент. И 2 этого канала, имитируя заполнение очереди Так как элемент И 4 k-ro канала открывает единичным потенциалом с прямого выхода триггера 3 данного канала, то импульсы с генератора 20 импульсов поступают на делитель 5 частоты. С выхода делителя 5 частоть, импульсы с собственной частотой ;,ан- ного канала, т.е. частотой лидера, через открытый элемент И 6 этого канала и через элемент ИЛИ 21 поступают на суммирующий вход реверсивного счетчика 22 устройства, а также на информационные входы элементов 8 запрета и на управляющие входы .элементов 9 запрета,всех каналов об

5

0

Q

5 5

5

0

0

5

0

.служивания заявок. В результате этого во всех, каналах обслуживания заявок, за исключением k-ro канала, т.е. канала-лидера, с выходов элементов 8 запрета на суммирующие входы реверсивных счетчиков 11 поступают импульсы с частотой канала лидера. В k-M же канале, так как импульсы с собственной частотой этого канала поступают на информационные и управляющие входы элементов 8 и 9 запрета данного канала синхронно, то они взаимно уничтожаются, в результате чего на суммирующем и вычитающем входах .реверсивного счетчика 11 канала- лидера присутствуют нулевые потенциалы и содержимое этого счетчика удерживается в нулевом состоянии.

По истечении времени обслуживания заявки k-ro типа, которое имитируется блоком 15 случайной временной задержки, па его выходе появляется сигнал, который устанавливает триггер 3 этого канала в нулевое состояние, в результате чего данный канал перестает быть лидером и- его разностная функция R{(t) должна принять то же значение, что и у каналов обслуживания заявок, в которых генераторами 1 случайного потока заявок не выработаны импульсы-заявки. Для таких каналов функции приоритета равны нулю. Поэтому их разностные функции приоритета равны H(t).

Таким образом, на реверсивном счетчике 11 канала-лидера после окончания обслуживания заявки должен быть записан код H(t), который вычисляется на реверсином счетчике 22. Запись этого кода осуществляется сигналом с выхода блока 1.5 случайной временной задержки, который открывает блок элементов И 10 данного канала и содержимое реверсивного счетчика 22 переписывается в реверсивный счетчик 11 этого канала.

Во время моделирования процесса обслуживания заявки k-ro типа в (k-1)-и канал обслуживания заявок с генератора 1 случайного потока заявок поступает импульс-заявка, который устанавливает триггер 3 (k-1)-rr канала в единичное состояние. Это приводит к тому, что на вычитающий вход реверсивного счетчика 11 (k-1)-го канала поступ;зют импульсы с собственной частотой (k-1)-го канала, т.е вычисляется разностная

функция (k-l)-ro канала. Так как собственная частота (k-l)-ro канала вьше собственной частоты k-ro канала, то по истечении некоторого вре- ,- мени значение разностной функции (k-1)-ro канала становится равным нулю, происходит смена лидера, т.е. прерывание обслуживания заявки k-ro типа, и начинается обслуживание tO заявки Ck-1)-ro типа. Это осуществляется таким образом, что нулевой потенциал с выхода элемента ИЛИ 12 (k-l)-ro канала,,поступая на соответствующий вход элемента И 14 5 k-ro канала, закрывает его, а на входе блока 15 случайной временной задержки k-ro канала исчезает единичный сигнал. Кроме того, нулевой потенциал с выхода элемента ИЛИ 12 20 (k-T)-ro канала поступает на вход элемента НЕ 13 своего канала, в ре- зультате чего на выходе открытого элемента И 14 и, следовательно, на входе блока 15 случайной временной 25 задержки (k-1)-ro канала находится единичный потенциал, сигнализирующий, что на обслуживании находится заявка (k-l)-ro типа. Так как элемент И 14 k-ro канала закрывается, а элемент ,« И 14 (k-l)-ro канала открьшается, то на суммирующий вход реверсивного счетчика 22 поступают импульсы с собственной частотой (k-1)-ro канала,, т.е. нового лидера. Дальнейшая работа устройства аналогична рассмот- ренному.

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

Так как на выходах элементов ШЖ 12 всех каналов обслуживания заявок присутствуют единичные потенциалы, то срабатьшает элемент И 23 и в свою очередь открьшает элемент 19. В результате этого импульсы 50 поиска с генератора 20 импульсов поступают непосредственно на вычитащий вход реверсивного счетчика 22 через элементы ИЛИ 7 и открытые лементы 9 запрета на вычитающие 55 ходы реверсивных счетчиков 11 всех аналов обслуживания заявок. Это риводит к тому,.что значения разностных функций всех каналов ют синхронно уменьшаться с высокой скоростью, определяемой частотой импульсов поиска. В качестве обслуживания заявок, имеющем на момент начала поиска минимальное значение функции, эта функция быстрее, чем у других каналов становится равной нулю. Как только это происходит на выходе элемента ИЛИ 12 данного канала появляется нулевой потенциал, который приводит к исчезновению единичного потенциала с выхода элемента И 23 устройства, что приводит к закрытию элемента И 19 устройства, т.е. к прекращению выдачи импульсов поиска. Этот же нулевой потенциал одновременно приводит к тому, что на выходах элемента НЕ 13 элемента И 14 данного канала, если это не первый канал, и, следовательно, на входе блока 15 случайной временной задержки появляется единичный потенциал, т.е. данный канал обслуживания заяво становится лидером и на обслуживании находится заявка данного типа. Если при проведении поиска нулевые значения принимают одновременно разностны функции двух и более каналов обслуживания заявок, то лидером становится тот из них, чей номер меньше, так как нулевой потенциал; с выхода его элемета. ИЛИ 12 закрывает элемент И 14 остальных каналов.

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

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

Устройство для моделирования систем массового обслуживания, содержащее два элемента И, элемент задержки, элемент ИЛИ и М каналов обслуживания заявок, каждый из которых состоит из генератора случайного потока заявок, триггера, блока случайной временной задержки, первого и второго элементов И, k-й канал обслу

живания заявок (k 2, М) содержит третий элемент И, причем в каждом канале обслуживания заявок выход генератора случайного потока заявок соединен с первым входом первого элемента И, выход которого подключен к единичному входу триггера, прямой выход которого соединен с первым входом второго элемента И, а инверс- ный выход - с вторьм входом первого элемента И, нулевой вход триггера подключен к выходу блока случайной временной задержки, вход которого в k-M канале обслуживания заявок сое- динен с выходом третьего элемента И, отличающееся тем, что, с целью расширения функциональных возможностей за счет моделирования абсолютного динамического приоритета в- обслуживании заявок, оно дополнительно содержит третий элемент И, элемент НЕ, генератор импульсов и реверсивный счетчик, а каждый канал обслуживания заявок Дополнительно содержит четвертый элемент И, два элемента запрета, реверсивный счетчик, два элемента ИЛИ, элемент НЕ и делитель частоты, причем в каждом канале обсхгуживания заявок инверс- ный выход триггера соединен с установочным входом делителя частоты и первым входом первого элемента РЩИ, группа входов кот орого подк-лючен а соответственно к разрядным выходам реверсивного счетчика, с пммирующий вход которого соединен с выходом первого элемента запрета, вычитающий вход - с выходом второго элемента запрета, а разрядные входы - с входами блока элементов И, управляющий вход которого подключен к выходу блока случайной временной задержки, выход второго элемента И соединен с информационным входом делителя частоты, выход которого подключен к первому входу четвертого элемента И и первому входу второго элемента ИЖ, выход которого соединен с информаци г онньм входом второго элемента за- прета и управляющим входом первого элемента запрета, выход первого элемента ИЛИ подключен к входу элемента НЕ и к соответствующему входу первого элемента И устройства, за исключением последнего канала обслу-

0

5

«j 5

0

5

0

5

0

живания заявок выход первого элемента ИЛИ (k-l) -ro канала обслуживания заявок соединен с (и-1)-ми входами третьих элементов И всех каналов обслуживания заявок, имеющих номер, больший чем k-1, выход элемен-, та НЕ k-ro канала обслуживания зая- БОК группы соединен с k-м входом третьего элемента И своего канала обслуживания заявок, выход которого подключен к второму входу четвертого элемента И своего канала обслуживания заявок, выход элемента НЕ первого канала обслуживания заявок соединен с вторым входом четвертого элемента И и входом блока случайной временной задержки первого канала обслуживания заявок, выходы четвертых элементов И всех каналов обслуживания заявок подключены соответственно к входам элемента ИЛИ устройства, вьпсод которого соединен с информационными входами первых элементов запрета и управляющими входами вторых элементов запрета всех каналов обслуживания заявок и с суммирующим входом реверсивного счетчика устройства, разрядные выходы которого подключены соответственно к информационным входам блоков элементов И всех каналов обслуживания заявок, инверсные выходы триггеров всех каналов обслуживания заявок группы сое- динены с соответствующими входами второго элемента И устройства, выход которого подключен к входу элемента , НЕ, устройства, к установочному входу реверсивного счетчика устройства и к установочньм входам реверсивных счетчиков всех каналов обслуживания заявок, выход генератора импульсов соединен с вторыми входами вторых элементов И всех каналов обслуживания заявок и через элемент задержки - с первым входом третьего элемента И устройства, второй вход го подключен к выходуэлемег-ч НЕ устройства, а третий вход ;- . s::;iO ду первого элемента И устройства,;. выход третьего элемента И устройс за подключен к вычитающему входу реверсивного счетчика устройства и к вторым входам вторых элементов ИЛИ всех каналов обслуживания заявок.

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