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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК g G 06 F 15/20

3ИЫВжц

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСНОМ,Ф СВИДЕТЕЛЬСТВУ

Ь

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОЛХРЫТИЯМ

ПРИ ГКНТ СССР (21) 4317661/24-24 (22) 15.09.87 (46) 07.04.89. Бюл. 9 13 (72) Ю.А. Капиносов, И.А. Ветров и Д.В. Остапенко (53) 681.3(088.8) (56) Авторское свидетельство СССР

Ф 1419730, кл. G 06 F 15/20, 1987.

Авторское свидетельство СССР

Ф 1406600, кл. G 06 F 15/20, 1986..(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ (57) Изобретение относится к вычислительной технике и предназначено для статистического моделирования приоритетных систем массового обслуживания. Цель изобретения — расширение функциональных возможностей устройства за счет моделирования динамических абсолютных приоритетов.

Устройство позволяет моделировать

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

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

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

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

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

Триггеры каналов имитируют ограниченную очередь. 1 ил.

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

И 16, элемент HE 17, элемент 18 задержки, третий элемент И 19, генера1471199 тор 20 импульсов, элемент ИЛИ 21, реверсивный счетчик 22 и первый элемент И 23.

Устройство предназначено для мо5 делирования СМО с абсолютными динамическими приоритетами, т.е. таких

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

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

h;(t) = f; (t-с;), 25 где t — текущий момент времени, — момент поступления заявки в канал, — частота импульсов в канале на выходе делителя 5.

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

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

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

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

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

В качестве выходного сигнала делителя 5 частоты используется сигнал переполнения, который жестко привязан по времени к входному сигналу делителя 5 частоты, повторяет его по длительности, но выдается в

M раз реже. Для обеспечения соотсЧ ношения собственных частот каналов

f 4) f ) f )Ä, > fh модули счета делителей 5 частоты выбираются так, что с M (, (M

"1

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

Элементом, определяющим равенство нулю разностной функции приоритетности R1 канала, является элемент

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

4 раходится в нулевом состоянии. Таким образом, чтобы на выходе элемента ИЛИ 12 появился нулевой потенциал, характерный для лидера, необходимо, чтобы на входы элемента ИЛИ 12 подавался нулевой код с параллельных выводов реверсивного счетчика 11 канала, а на последний вход подавался

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

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

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

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

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

На момент конца поиска на реверсивных счетчиках 11 всех каналов находятся Разности между функцией приоритета нового лидера и функцией приоритета данного канала, а на реверсивном счетчике 22 — сама функция приоритета нового лидера. Импуль сы поисковой частоты не должны накладываться по времени на импульсы собственной частоты каналов, так как и те и другие приходят на вычитающие входы реверсивных счетчиков 11.

Это достигается тем, что генератор

20 импульсов вырабатывает прямоугольные импульсны со скважнас пью больше

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

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

I4 (N «N

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

В исходном состоянии триггеры

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

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

Допустим, что на выходе генератора 15

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

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

k-r o канала, если это не первый канал, появляется единичный потенциал, так как на всех его входах в этом случае присутствуют единичные потенциалы.. Таким образом, на вход блока

15 случайной временной задержки поступает единичный сигнал, который свидетельствует о том, что заявка

k-го типа поступила на обслуживание, т.е. k-й канал стал лидером.

Кроме того, нулевой потенциал с инверсного выхода триггера 3 k-го канала закрывает элемент И 2 этого канала, имитируя заполнение очереди.

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

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

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

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

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

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

1471199

io функция (k-1) — ro канала. Так как собственная частота (k-1)-го канала выше собственной частоты k-ro канала, то по истечении некоторого вре5 мени значение разностной функции (k-i)-го канала становится равным нулю, происходит смена лидера, т.е. прерывание обслуживания заявки

k-го типа, и начинается обслуживание заявки (k-1)-ro типа. Это осуществляется таким образом, что нулевой потенциал с выхода элемента ИЛИ 12 (k-1)-ro канала, поступая на соотI ветствующий вход элемента И 14 15

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

k-го канала закрывается, а элемент

И 14 (k-1)-ro канала открывается, то на суммирующий вход реверсивного счетчика 22 поступают импульсы с собственной частотой (k-1)-го канала, т ° е. нового лидера. Дальнейшая работа устройства аналогична рассмот- 35 ренному.

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

Так как на выходах элементов

ИЛИ 12 всех каналов обслуживания заявок присутствуют единичные потенциалы, то срабатывает элемент И 23 и в свою очередь открывает элемент

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

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

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

I живания заявок (k = 2, M) содержит третий элемент И, причем в каждом канале обслуживания заявок выход генератора случайного потока заявок соединен с первым входом первого элемента И, выход которого подключен к единичному входу триггера, прямой выход которого соединен с первым входом второго элемента И, а инверсный выход — с вторым входом первого элемента И, нулевой вход триггера подключен к выходу блока случайной временной задержки, вход которого в

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

Вход которого соединен с выходом первого элемента запрета, вычитающий вход — с выходом второго элемента

9 запрета а разрядные входы — с входа40 ми блока элементов И, управляющий вход которого подключен к выходу блока случайной временной задержки, выход второго элемента И соединен с информационным входом делителя часто45 ты, выход которого подключен к первому входу четвертого элемента И и первому входу второго элемента ИЛИ, выход которого соединен с информаци. онным входом второго элемента запрета и управляющим входом первого элемента запрета, выход первого элемента ИЛИ подключен к входу элемента HE и к соответствующему входу первого элемента И устройства, за исключением последнего канала обслу- 55 жив ания заявок выход пе рво го элемента ИЛИ (k-1) -го канала обслуживания т заявок соединен с (k-1)-ми входами третьих элементов И всех каналов обслуживания заявок, имеющих номер, больший чем k-1, выход элемента HE k-го канала обслуживания заявок группы соединен с k-м входом третьего элемента И своего канала обслуживания заявок, выход которого подключен к второму входу четвертого элемента И своего канала обслуживания заявок, выход элемента HE первого канала обслуживания заявок соединен с вторым входом четвертого элемента И и входом блока случайной временной задержки первого канала обслуживания заявок, выходы четвертых элементов И всех каналов обслуживания заявок подключены соответственно к входам элемента ИЛИ устройства, выход которого соединен с, информационными входами первых элементов запрета и управляющими входами вторых элементов запрета всех каналов обслуживания заявок и с суммирующим входом реверсивного счетчика устройства, разрядные выходы которого подключены соответственно к информационным входам блоков элементов И всех каналов обслуживания заявок, инверсные выходы триггеров всех каналов обслуживания заявок группы соединены с соответствующими входами второго элемента И устройства, выход которого подключен к входу элемента

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

1471199

Составитель В.Фукалов

Техред Л.Олийнык Корректор И.Муска

Редактор А.Мотыль

Заказ t609/50 Тираж 667 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина,101