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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 06 Р 15/ САНИЕ ИЗОБРЕТЕН Бло.Р ль ехнике и может я моделировани м массового об тельноизовано приоритл ван ржит аждый ОСУДАРСТВЕННЫЙ КОМИТЕПО ИЗОБРЕТЕНИЯМ И ОТРЫТПРИ ГКНТ СССР Н АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СССУ 1419730, кл. С 06 Р 15/20, 198Авторское свидетельство СССРФ 1406600, кл. С 06 Р 15/20, 198(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ (57) Изобретение относится к вычислительной технике и предназначено для статистического моделированияеприоритетных систем массового обслуживания. Цель изобретения - расширение Функциональных возможностей устройства за счет моделирования динамических абсолютных приоритетов. Устройство позволяет моделировать 1Изобретение относится к вычи алых систе с ужи ияСМО).Цель изобретения - расширениеункциональных возможностей устройтва за счет моделирования абсолютого динамического приоритета вбслуживании заявокНа чертеже приведена структурнахема устройства.Устройство соде каналы обслуживания заявок, к из которых 901471199 системы с произвольным входным потоком заявок, ограниченной очередью,произвольным временем обслуживанияи динамической дисциплиной обслуживания. Устройство содержит генераторимпульсов, элементы И, элемент ИЛИ,элемент НЕ, элемент задержки, реверсивный счетчик и каналы обслуживания заявок, а в каждом канале - элемент НЕ, генератор случайного потоказаявок, делитель частоты, блок случайной временной задержки, триггер,элементы И, элементы ИЛИ, блок элементов И, элементы запрета и ревер.сивный счетчик, Генераторы случайного потока заявок обеспечиваютимитацию входных потоков заявок.ки случайной временной задержки штируют обслуживающий прибор с произвольным временем оослуживания. риггеры каналов имитируют ограненную очередь. 1 ил. 2состоит из генератора 1 случайного потока заявок, первого элемента И 2, триггера 3, второго элемента И 4, делителя 5 частоты, четвертого элемента И 6, второго элемента ИЛИ 7, первого 8 и второго 9 элементов запрета, блока 10 элементов И, реверсивного счетчика 11, первого элемен" та ИЛИ 12, элемента НЕ 13, третьего элемента И 14 и блока 15 случайной временной задержки, В состав устройства входят также второй элемент И 16, элемент НЕ 17, элемент 18 задержки, третий элемент И 19, генера 1471199тор 20 импульсов, элемент ИЛИ 21, реверсивный счетчик 22 и первый элемент И 23.Устройство предназначено для мо 5делирования СМО с абсолютными динамическими приоритетами, т,е. такихСМО, в которых приоритет обслуживания поступающих заявок зависит отдлительности нахождения заявок в системе. Выбор заявок на обслуживаниеосуществляется с учетом текущегозначения функции приоритета, зависящей для заявки каждого типа от времени пребывания в системе, Обслуживание заявок осуществляется в порядкеабсолютного приоритета таким обра.зом, что в каждый момент времени наобслуживании находится заявка, обладающая максимальным мгновенным значением функции приоритетности из числа заявок, находящихся в системе.Функция приоритета заявок х-гоканала обслуживания имеет видь; = й; (-с;),25где Г. - текущий момент времени,- моментпоступления заявкив канал,- частота импульсов в каналена выходе делителя 5.В любой момент времени в устройстве должен быть только один лидер,поэтому в случае, если максимальноемгновенное значение функцииприоритетности имеют одновременно два илиболее каналов, то лидером становится тот из них, номер которого меньше,т.к. канал, имеющий наибольшую частоту.Для каждого канала вводится разностная функция приоритета. ( ) 4(Таким образом, лидером в любоймомент времени должен быть канал сминимальным номером, у которого разностная функция приоритета равнанулю,Элементом, определяющим разностную функцию приоритета кажцого канала . является реверсивный счетчик 11канала, на суммирующий вход которогоподаются импульсы с частотой лидера,а на вычитающий вход - импульсы ссобственной частотой данного канала.Нормальная работа такого реверсивного счетчика нарушается при,одновре.-.менном поступлении импульсов на егосуммирующий и вычитающий входы. Поэтому в каждом канале стоят два элемента 8 и 9 запрета, которые запрещают прохождение сигнала на один из этих входов счетчика в случае наличия сигнала на другом. Для устойчивой работы реверсивного счетчика 11 необходимо, чтобы импульсы на его суммирующий и вычитающий входы проходили или в разное время, не накладываясь друг на друга даже частично, или проходили строго в один и тот же момент, имея одинаковую длительность, а также полностью взаимно уничтожались элементами 8 и 9 запрета каналов.Это достигается введением общего для всех каналов генератора 20 импульсов и делителя 5 частоты .на каждый канал. Делителя 5 частоты построены на базе счетчиков с принудительным насчетом и начальной установкой.В качестве выходного сигнала делителя 5 частоты используется сигнал переполнения, который жестко привязан по времени к входному сигналу делителя 5 частоты, повторяет его по длительности, но выдается в М раз реже. Для обеспечения соот- сЧношения собственных частот каналов Й 4) ЙЕ ),К модули счета делителей 5 частоты выбираются так, чтоМсиМсц (, (МсцТак как выходные импульсы делителя 5 частоты каждого канала жестко. привязаны к своему входному импульсу с генератора 20 импульсов, то для любой пары .каналов импульсы на выходах их делителей 5 частоты будут или полностью совпадать или отстоять друг от друга на время, кратное периоду поступления импульсов с генератора 20 импульсов.Элементом, определяющим равенство нулю разностной функции приоритетности К 1 канала, является элемент ИЛИ 12 канала. Но канал не может быть лидером, если с выхода генератора 1 случайного потока заявок данного канала не поступил импульс- заявка и триггер 3 этого канала 4раходится в нулевом состоянии. Таким образом, чтобы на выходе элемента ИЛИ 12 появился нулевой потенциал, характерный для лидера, необходимо, чтобы на входы элемента ИЛИ 12 подавался нулевой код с параллельных выводов реверсивного счетчика 1.1 канала, а на последний вход подавалсянулевой потенциал с инверсного выхода триггера 3, Элемент НЕ 13 и элементы И 14 каналов обеспечивают единственность лидера в любой момент времени. Лидером будет канал, имеющий нулевой сигнал на выходе элемента ИЛИ 12, а если таких каналов в данный момент несколько, то лидером станет тот из них, у которого меньший порядковый номер и, следовательно, большая частота. Только лидер через слой открытый элемент И 6 подает импульсы со своего делителя 5 частоты на суммирующие входы Реверсивных счетчиков 11 всех каналов обслуживания заявок устройства. И только в канале, являющемся лидером, на входе блока 15 случайной временной задержки, имитирующего обслуживающий прибор, появляется единичный потенциал, свидетельствующий о том, что заявка данного типа поступает на обслуживание.После окончания обслуживания запроса происходит смена лидера, но может возникнуть ситуация, когда разностные функции приоритета всех каналов обслуживания заявок не равны нулю.В таком случае задача выделения канала с максимальной функциеи приоритета сводится к отысканию канала с минимальной разностной функцией. Поиск осуществляется одновременной подачей на вычитающие входы реверсивных счетчиков 11 всех каналов импульсов высокой поисковой частоты до тех пор, пока хотя бы на одном из них не появится нулевой код, те.40 до тех пор, пока разностная функция приоритета хотя бы одного канала станет равной нулю, После этого выделение лицера происходит аналогично рассмотренному.На момент конца поиска на реверсивных счетчиках 11 всех каналов находятся Разности между Функцией приоритета нового лидера и функцией приоритета данного канала, а на реверсивном счетчике 22 - сама функ ция приоритета нового лидера. Импульсы поисковой частоты не должны накладываться по времени на импульсы собственной частоты каналов, так как и те и другие приходят на вычитающие входы реверсивных счетчиков 11. Это достигается тем, что генератор 20 импульсов вырабатывает прямоугольные импульсны со скважнас пью больше2, а импульсы поиска получаются изних сдвигом на половину периода, который осуществляется элементом 18задержки таким образом, что импульсыпоиска не будут накладываться на импульсы генератора 20, а значит и навыходные импульсы делителей 5 частоты каналов. Из этого следуют требования к генератору 20 импульсов: ондолжен вырабатывать прямоугольныеимпульсы со скважностью больше 2,период которых должен быть вдвоебольше того интервала времени, который необходим для завершения переходных процессов в реверсивных счетчиках. Время поиска нового лидерав рассматриваемом случае зависит отпревьппения частоты импульсов поисканад собственной частотой каналов,т.е, величины модулей счета делителей 5 частоты, Приоритентность каждого канала зависит не от абсолютного значения его собственной частоты,а от соотношения этого значения ссобственной частотой других каналов.Поэтому модуль счета делителя 5 частоты первого канала, имеющего максимальную собственную частоту, . выбирается таким, чтобы обеспечитьзначительное превьппение частоты поиска над собственной частотой первогоканала, а модули счета остальныхканалов выбираются с учетом этогозначения в соответствии с нерав=яством Устройство работает следующим образом.В исходном состоянии триггеры 3 всех каналов обслуживания заявок находятся в нулевом состоянии. На выходе элемента И 16 присутствует единичный потенциал, характерный только для исходного состояния. Единичный потенциал с инверсных выходов триггеров 3 каналов подводится на установочные входы реверсивного счетчика 22 и реверсивных счетчиков 11 каналов, что приводит к установлению на разрядных выходах этих счет" чиков нулевых кодов, Кроме того, этот же сигнал подается на входы начальной установки делителей 5 частоты каналов и на последние входы эле-, ментов ИЛИ 12 каналов, Поэтому на изводах элементов ИЛИ 12 всех кана 1471199лов в исходном состоянии присутствуют единичные потенциалы. А это значит, что на выходах элементов НЕ 13 и, следовательно, на выходах элемен- . тов И 14 присутствуют нулевые потен 5 циалы. Прохождение импульсов с генератора 20 импульсов блокируется закрытыми элементами И 4 всех каналов, так как на их первых входах находятся нулевые потенциалы, и закрытым элементом И 19, так как на его вход в исходном состоянии с выхода элемента НЕ 17 подается нулевой потенциал,Допустим, что на выходе генератора 15 1 случайного потока заявок 1-го канала, имитирующего входной поток заявок на обслуживание, Е-го приоритетного класса, появился импульс-заявка, который, пройдя через свой открытый элемент И 2, устанавливает триггер 3 данного канала в единичное состояние. В результате этого на выходе элемента ИЛИ 12 Е-го канала появляется нулевой потенциал, так как на всех его входах присутствуют нулевые потенциалы. Поэтому на выходе элемента НЕ 13 данного канала появляется единичный потенциал, что приводит к ,тому, что на выходе элемента И 14 к-го канала, если это не первый канал, появляется единичный потенциал, так как на всех его входах в этом случае присутствуют единичные потенциалы Таким образом, на вход блока 15 случайной временной задержки по ступает единичный сигнал, который свидетельствует о том, что заявка к-го типа поступила на обслуживание, т,е к-й канал стал лидером.Кроме того, нулевой потенциал с инверсного выхода триггера 3 к-го канала закрывает элемент И 2 этого канала, имитируя заполнение очереди. Так как элемент И 4 1-го канала открывает единичным потенциалом с пря 45 мого выхода триггера 3 данного канала, то импульсы с генератора 20 импульсов поступают на делитель 5 частоты, С выхода делителя 5 частоть, имйульсы с собственной частотой ;,анного канала, т.е. частотой лидера, через открытый элемент И 6 этого канала и через элемент ИЛИ 21 поступают на суммирующий вход реверсивного счетчика 22 устройства, а также 55 на информационные входы элементов 8 запрета и на управляющие входы элементов 9 запрета всех каналов обслуживания заявок. В результате этого во всех, каналах обслуживания зая - вок, за исключением к - го канала, т.е, канала-лидера, с выходов элементов 8 запрета на суммирующие входы реверсивных счетчиков 11 поступают импульсы с частотой канала лидера. В к-м же канале, так как импульсы с собственной частотой этого канала поступают на информационные и управляющие входы элементов 8 и 9 запрета данного канала синхронно, то они взаимно уничтожаются, в результате чего на суммирующем и вычитающем входах реверсивного счетчика 11 канала- лидера присутствуют нулевые потенциалы и содержимое этого счетчика удерживается в нулевом состоянии.По истечении времени обслуживания заявки к-го типа, которое имитируется блоком 15 случайной временной задержки, на его выходе появляется сигнал, который устанавливает триггер 3 этого канала в нулевое состояние, в результате чего данный канал перестает быть лидером и его разностная функция К(С) должна принять то же значение, что и у каналов обслуживания заявок, в которых генераторами 1 случайного потока заявок не ,выработаны импульсы-заявки, Для таких каналов функции приоритета равны нулю. Поэтому их разностные функции приоритета равны Н(г.).Таким образом, на реверсивном счетчике 11 канала-лидера после окончания обслуживания заявки должен быть записан код Н, который вычисляется на реверсином счетчике 22. Запись этого кода осуществляется сигналом с выхода блока 15 случайной временной задержки, который открывает блок элементов И 10 данного канала и содержимое реверсивного счетчика 22 переписывается в реверсивный счетчик 11 этого канала.Во время моделирова:ия процесса обслуживания заявки 1 - го типа в Ь)-й канал обслуживания заявок с генератора 1 случайного потока заявок поступает импульс-заявка, который устанавливает триггер 3 (Е)-гг канала в единичное состояние, Это приводит к тому, что на вычитающий вход реверсивного счетчика 11Ь)-го канала поступают импульсыс собственной частотой (1:-1)-го канала, т,е. вычисляется разностнаяфункция Ь)-го канала, Так каксобственная частота Ь)-го каналавыше собственной частоты -го канала, то по истечении некоторого вре 5мени значение разностной функцииЬ)-го канала становится равнымнулю, происходит смена лидера, т.е.прерывание обслуживания заявкиЕ-го типа, и начинается обслуживаниезаявки Ь)-го типа. Это осуществляется таким образом, что нулевой потенциал с выхода элемента ИЛИ 12Ь)-го канала, поступая на соот 3ветствующий вход элемента И 14 15Е-го канала, закрывает его, а навходе блока 15 случайной временнойзадержки 1-го канала исчезает единичный сигнал. Кроме того, нулевойпотенциал с выхода элемента ИЛИ 12Ь)-го канала поступает на входэлемента НЕ 13 своего канала, в ре. зультате чего на выходе открытогоэлемента И 14 и, следовательно, навходе блока 15 случайной временнойзадержки Ь)-го канала находитсяединичный потенциал, сигнализирующий,что на обслуживании находится заявкаЬ)-го типа, Так как элемент И 14Е-го канала закрывается, а элементИ 14 Ь)-го канала открывается,то на суммирующий вход реверсивногосчетчика 22 поступают импульсы ссобственной частотой -1)-го канала, те. нового лидера. Дальнейшаяработа устройства аналогична рассмотренному,Если после окончания обслуживания очередной заявки в устройственет нового лидера, т.ево всех каналах обслуживания заявок разностнаяфункция не равна нулю, если толькоэто не исходное состояние, то осуществляется поиск канала с минимальным значением разностной функции.Так как на выходах элементовИЛИ 12 всех каналов обслуживаниязаявок присутствуют единичные потенциалы, то срабатывает элемент И 23и в свою очередь открывает элементИ 19. В результате этого импульсыпоиска с генератора 20 импульсовпоступают непосредственно на вычитающий вход реверсивного счетчика 22и через элементы ИЛИ 7 и открытыеэлементы 9 запрета на вычитающие 55входы реверсивных счетчиков 11 всехканалов обслуживания заявок. Этоприводит к тому,.что значения разностных функций всех каналов начинают синхронно уменьшаться с высокой скоростью, определяембй частотой импульсов поиска. В качестве обслуживания заявок, имеющем на момент начала поиска минимальное значение функции, эта функция быстрее, чем у других каналов становится равной нулю. Как только это происходитна выходе элемента ИЛИ 12 данного канала появляется нулевой потенциал, который приводит к исчезновению единичного потенциала с выхода элемента И 23 устройства, что приводит к закрытию элемента И 19 устройства, те, к прекращению выдачи импульсов поиска. Этот же нулевой потенциал одновременно приводит к тому, что на выходах элемента НЕ 13 элемента И 14 данного канала, если это не первый канал, и, следовательно, на входе блока 15 случайной временной задержки появляется единичный потенциал, т.е, данный канал обслуживания заявок становится лидером и на обслуживании находится заявка данного типа. Если при проведении поиска нулевые значения принимают одновременно разностные функции двух и более каналов обслуживания заявок, то лидером становится тот из них, чей номер меньше, так как нулевой потенциал с выхода его элемента.ИЛИ 12 закрывает элемент И 14 остальных каналов.Сигнал с выхода блока 15 используется как сигнал окончания обслуживания заявки для установки соответствующего канала обслуживания заявок группы в исходное состояние. Если во время формирования этого сигнала на входе данного блока исчезает единичный потенциал, а это происходит при прерывании обслуживания заявки заяв-, кой более высокого приоритета, то сигнала окончания обслуживания на выход блока 15 не поступает.Формула изобретенияУстройство для моделирования систем массового обслуживания, содержащее два элемента И, элемент задержки, элемент ИЛИ и М каналов обслуживания заявок, каждый из которых состоит из генератора случайного потока заявок, триггера, блока случайной временной задержки, первого и второго элементов И, -й канал обслу 147 1199живания заявок Ь = 2, М) содержит третий элемент И, причем в каждом канале обслуживания заявок выход генератора случайного потока заявок соединен с первым входом первого элемента И, выход которого подключен к единичному входу триггера, прямой выход которого соединен с первым входом второго элемента И, а инверсный выход - с вторым входом первого элемента И, нулевой вход триггера подключен к выходу блока случайной временной задержки, вход которого в Е-м канале обслуживания заявок соединен с выходом третьего элемента И, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет моделирования абсолютного динамического приоритета в обслуживании заявок, оно дополнительно содержит третий элемент И, элемент НЕ, генератор импульсов и реверсивный счетчик, а каждый канал обслуживания заявок дополнительно 25 содержит четвертый элемент И, два элемента запрета, реверсивный счетчик, два элемента ИЛИ, элемент НЕ и делитель частоты, причем в каждом канале обслуживания заявок инверсный выход триггера соединен с установочным входом делителя частоты и первым входом первого элемента ИЛИ, группа входов которого подключена соответственно к разрядным выходамЪ.Греверсивного счетчика, суммирующий вход которого соединен с выходом первого элемента запрета, вычитающий вход - с выходом второго элемента9запрета а разрядные входы - с входа 40 ми блока элементов И, управляющий вход которого подключен к выходу блока случайной временной задержки, выход второго элемента И соединен с информационным входом делителя часто 45 ты, выход которого подключен к первому входу четвертого элемента И и первому входу второго элемента ИЛИ, выход которого соединен с информаци онным входом второго элемента запрета и управляющим входом первого 50 элемента запрета, выход первого элемента ИЛИ подключен к входу элемента НЕ и к соответствующему входу первого элемента И устройства, за исключением последнего канала обслу жив ания заявок выход пе рво го элемента ИЛИ (1 с)-го канала обслуживаниятзаявок соединен с (1;-1)-ми входами третьих элементов И всех каналов обслуживания заявок, имеющихномер, больший чем 1-1, выход элемента НЕ 1-го канала обслуживания заявок группы соединен с Ъ.-м входомтретьего элемента И своего каналаобслуживания заявок, выход которогоподключен к второму входу четвертого элемента И своего канала обслуживания заявок, выход элемента НЕ первого канала обслуживания заявок соединен с вторым входом четвертогоэлемента И и входом блока случайнойвременной задержки первого каналаобслуживания заявок, выходы четвертых элементов И всех каналов обслуживания заявок подключены соответственно к входам элемента ИЛИ устройства, выход которого соединен с,информационными входами первых элементов запрета и управляющими входамивторых элементов запрета всех каналов обслуживания заявок и с суммирующим входом реверсивного счетчикаустройства, разрядные выходы которого подключены соответственно к информационным входам блоков элементов Ивсех каналов обслуживания заявок,инверсные выходы триггеров всех каналов обслуживания заявок группы соединены с соответствующими входамивторого элемента И устройства, выходкоторого подключен к входу элементаНЕ, устройства, к установочному входуреверсивного счетчика устройства и кустановочным входам реверсивных счетчиков всех каналов обслуживаниязаявок, выход генератора импульсовсоединен с вторыми входами вторыхэлементов И всех каналов обслужива"ния заявок и через элемент задержки - с первым входом третьего элемен"та И устройства, второй вход к .срого подключен к выходу элеме:.".устройства, а третий вход в , :.аду первого элемента И устройства.выход третьего элемента И устройсяаподключен к вычитающему входу ревер-.сивного счетчика устройства и к вторым входам вторых элементов ИЛИ всехканалов обслуживания заявок.1471199 ктор И,Му ть 609/50 Тираж 667 ПодписноеГосударственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5 зводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина,10 РедакторЗаказ 1 Составитель В,ФукалТехред Л.Олийньпс