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

 

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

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

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

РЕСПУ БЛИН

„„SU„„1229? 71 А 1

15@ 4 G 06 F 15/20

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

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

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

flo делАЮ изОБРетений и ОтнРытий (21) 3763138/24-24 (22) 29.06.84 (46) 07.05.86. Бюл. Р 17 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова. (72) В.И.Финаев, Г.А.Минаев и М.Ф.Саримахмудов (53) 681.396.6 (088 .8) (56) Авторское свидетельства СССР

Р 1088004, кл. С 06 F 15/20, 1983.

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

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

СИСТЕМ МАССОВОГО ОБСПУЗИВАНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано для моделирования систем,, описываемых аппаратом теории массо- . ваго обслуживания, например вычислительных систем, систем передачи данных, элементов производственных процессов торговых предприятий и т.д.

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

3 12297

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

На фиг. 1 приведена схема предлагаемого устройства; на фиг.2 — структурная схема первого блока формиро- 1 вания состояний; на фиг. 3 — структурная схема дополнительных (М-1) блоков формирования состояний; на фиг. 4 — функциональная схема блока формирования входного потока; на 2р фиг. 5 — функциональная схема блока формирования выходного потока;, на фиг. 6 функциональная схема блока управления; на фиг. 7 и фиг. 8 функциональная схема блока формирова- yg ния времени задержки, на фиг. 9функциональная схема первого узла, задания законов распределения блоков формирования состояний. Устройство моделирования приоритетных систем массового обслуживания {фнг. 1} содержит генератор тактовых импульсов, группу блоков 2 формирования состояний, блок 3 формирования входного потока, блок 4 формирования выходного потока„ первую группу установочных входов 5; вторую группу установочных входов 6, блок

7 управления, группу блоков 8 формирования времени задержки, первый выход 9 устройства, второй выход 10 устройства, группы выходов 11 — 13 устройства.

/ I

Первый блок 2 формирования состояний (фиг. 2) содержит вход 14, коммутатор 15, генератор 16 случайного кода, узел 17 задания законов рас" пределения, выходы 18, узел 19 памяти.

Второй и последующие блоки 2 формирования состояний (фиг. 3) содер- о жат коммутатор 20, генератор 21 случайного кода, дополнительный коммутатор 22, дополнительный узел 23 задания законов распределения, вход

24, узел 25 задания законов распре- И деления, узел 26 памяти.

Блок 3 формирования входного потока (фиг. 4} содержит элемент ИЛИ

71 2

27, М групп элементов И 28, М групп элементов 29 задержки, группу элементов ИЛИ 30.

Блок 4 формирования выходного потока (фиг. 5) содержит элемент ИЦИ

31„ М групп элементов И 32, М групп элементов 33 задержки, группу элементов ИЛИ 34.

Блок 7 управления (фиг. 6) содержит группу элементов И-НЕ 35.

Блок 8 формирования времени задержки (фиг. 7 и 8) содержит вторую группу элементов ИЛИ 36, первый элемент ИЛИ 37, вторую группу элементов И 38, группу триггеров 39, первую группу элементов И 40, входы 41 элементов И 40, дешифратор 42, второй элемент ИЛИ 43, группу формирователей 44 импульсов, третий элемент ИЛИ 45, шифратор 46, выходы 47 шифратора 46, группу регистров 48 памяти с входом 49 разрешения стирания и входом 50 разрешения записи, четвертую группу элементов И 51, первую группу элементов ИЛИ 52,третью группу элементов И 53.

Узел 25 (17) задания законов распределения {фиг. 9) содержит группу регистров 54, группу сумматоров 55, первую группу элементов И 56, группу схем 57 сравнения и вторую группу элементов И 58.

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

17 н 25 задания законов распределения блоков 2 формирования состояний заносятся коды матрицы переходных вероятностей, которые определяют формальную модель (автоматную) системы массового обслуживания: вероятностей

-перехода системы в j-e состояние, при условии, что она в предццущий момент времени находилась в i-и состоянии, По установочным входам 6 в узлы

23 задания законов распределения блоков 2 формирования состояний заносятся коды вероятности % -вероятности

I поступления требования за заданный отрезок времени для потока i-го приоритета.

Устройство моделирует функционирование одноканальной приоритетной системы массового обслуживания с ожиданием. Причем; вводится ограничение на максимально допустимую длину очереди, которая не более величины п-1, 29771 4

3 12

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

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

5 !

l5

ll ов> о

1О

1 у ° ° ° у Оу О

О, 0

Оу ° ° ° у л-

Г

1 о, о,..., г,„„„ 1 1

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

Информация о входном и выходном потоках требований снимается с выхо,цов 9 и 10. Информация о входных и выходных потоках требований по каждому приоритету снимается соответственно с выходов 11 и 12„ С выходов

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

Рассмотрим поблочно работу устройства.

Импульс генератора 1 подается на тактовые входы 14 блоков 2 формирования состояний блоков формирования входного 3 и выходного 4 потоков. Так как в регистрах 54 узлов

17 и 25 задания законов распределения блоков 2 формирования состояний хранятся кодыП;„, 1! 1, ;Q. П;„ то на выходах регистров 54 и сумматоров 55 формируются коды для К-ro блока 2:

IT. Tl4+ TI Tll + II!1 +ЧЬ ° ° ° 11Ы

+ ... +Д.

Предположим, что в системе нет требований, а генератор 16 в блоке

2„ выработал случайный код А, численная величина которого меньше величины кода Tl„ . Код А подается на входы узла 17 (на входы схем 57 сравнения). Так как код А меньше по величине#, то на выходах схем 57 оо сравнения будут йЬтенциалы, и потенциал с выхода схемы 57 сравнения закроет элементы И 58 и сигнал будет только на первом выходе узла 17.

Этим моделируется событие перехода состояния обслуживания за время

g t нулевого числа требований 1-го приоритета в такое же состояние.

Сигнал с выхода узла 17 поступает на вход коммутатора 15 и проходит на выход коммутатора 15 и на вход узла 19 памяти блока 2, Так как в системе нет требований, то имеются потенциалы на всех выхо т1 дах 18, — 18, блока 2, С выхода

18, блока 2, снимается потенциал, который подается на второй информаI ционный вход 18 узла 17, а также на

1 входы блока 7 управления, блоков формирования входного потока 3 и выход ного потока 4. В блоке 3 формирования входного потока (фиг. 4) потен-! циал с входа 18„через элемент 29 задержки времени поступает на элемент И 28, но так как потенциал на входе 18 отсутствует, то не будет потенциала и на выходах элементов

ИЛИ 30, и ИЛИ 27, что говорит о том, что эа прошедшее время в систему не поступило требований.- Импульсы на выходах 9 и 11 устройства отсутствуют. В блоке 4 формирования выходного потока такыре отсутствуют импульсы на выходах 10 и 12.

В блоке 7 управления (фиг. 6) потенциал по входу 18, закроет все элементы И-НЕ 35. На выходах 24 блока 7 будут нулевые потенциалы, которые подаются на управляющие входы

24 блоков 2 формирования состояний. 1.

В этом случае блоки 2 работают анало» гично блоку 2„ . Тогда через коммутатор 22 вырабатываемый генератором 2t случайный код поступает в узел 25 задания законов распределений, а узел

23 задания законов распределения не

I hl работает. Так. как на выходах t8 -1Ц блоков 2 потенциалы отсутствуют, то блоки 8 формирования времени задержки не работают. В системе отсутствует очередь.

Предположим, что в систему поступило требование старшего приоритета за очередной отрезок времени. Тогда с приходом импульса от генератора генератор 16 случайного кода блока

2, вырабатывает код, величина которого меньше числа 3„ +%„1, но больше числами . В этом случае в узле !

7 задания законов распределения

122,9771 блока 2 срабатывают соответствую1 щие схемы 57„сравнения. Сигнал с выхода схемы 57; сравнения закроет

1г элементы И 58, а на втором выходе узла 17 будет потенциал, который пройдет через коммутатор 15 на вход узла 19 памяти, и на втором выходе блока 2 формирования состояний по1 явится потенциал. Состояние выходов других блоков 2 не изменится;

Потенциал с блока 2„ поступит на вход блока 3 формирования входного потока. Так как в этот момент времени присутствует потенциал на выходе

1 элемента 29„, задержки времени, то

1 будет открыт элемент И 28„ . Тогда на выходах 9 и 11„ блока формирования входиого потока появится потенциал, что свидетельствует о поступлении в систему требования 1-го приоритета за отрезок времени.

Так как потенциал на входе 18„ блока 4 формирования выходного потока исчезнет раньше чем появится на 25 выходе элемента 33 задержки, то

1 состояние выходов блока 4 не изменится. Не участвуют в работе также и блоки 8 формирования времени задержки. 30

Так как на входе 18, блока 7 управления не будет потенциала, то на его выходах 24 появятся потенциалы, которые поступят на соответствующие входы 24 блоков 2 < — 2,„ формирования состояний. Коммутатор 22 подключает в работу узлы 23 задания законов распределений блоков 2 — 2,„.

Пусть в очередной такт времени в систему поступит еще одно требование старшего приоритета. Предыдущее требование еще не было обслужено. В системе возникает очередь. Рассмотрим данный процесс.

С приходом очередного, импульса от

4 ) генератора 1 тактовых импульсов генератор 16 блока 2, вырабатывает код, величина которого больше М + и

10 11 но меньше 7„ + Г + Г „ . На выходе

1О 11 узла 17 задания законов распределения будет потенциал, который пройдет через коммутатор 15 на вход узла 19 памяти.

Потенциал с выхода 18 блока 2< подается на вход блока 3 формирования входного потока, открывает элемент И 289 и на выходах 9 и 11 уст-! ройства появятся импульсы, что говорит о том, что в систему поступило еще одно требование 1-го и;.иоритета.

Блок 4 формирования выходного потока и блок 7 управления не изменяют своего состояния.

Так как второе требование первого приоритета будет задержано на время, оставшееся до конца обслуживания требования, поступившего ранее, то включается в работу блок 8 формирования времени задержки, определяющий время задержки требований первого приоритета. Функционирует он следующим образом. Потенциал с информа1 ционного входа 18 проходит через элемент ИЛИ 37. С появлением импульса на входе 11 через элемент И 38

1 1 триггер 39„ будет переброшен в единичное состояние. На выходе 13„ блока 8„ и устройства появится потенциал, причем длительность его будет равна времени нахождения требования в очереди ° Потенциал с единичного выхода триггера 39, подается также и на. элемент ИЛИ 43, срабатывающий по заднему фронту, и на формирователь 44», который выделяет передний фронт импульса и подает сигнал на элемент ИЛИ 45 и шифратор 46., Он формирует код номера очередного требова.ния в очереди. По импульсу с выхода. 50 элемента ИЛИ 45 код номера требования в очереди запоминается в регистре 48, . С выходов регистра 48, потенциалы поступят на элемент ИЛИ

52, и соответствующие элементы И 51.

Код номера требования, стоящего первого в очереди "на обслуживание, с выходов элементов И 51 поступит через элементы ИЛИ 36 на входы дешифратора 42 и на его выходе 41, будет потенциал.Допустим, на следующем такте в систему поступило еще одно требование и также 1-го приоритета. Данное требование должно стать вторым в очереди. Данное событие определится появлением потенциала на выходе 18 блока 2 и импульсов на выходах 9 и 11 устройства.

Потенциал с входа 18„ блока 8„: через элемент ИЛИ 37 поступит на элементы И 38, но будет открыт только элемент И 38г, тогда импульс с его выхода перебросит триггер 39. в единичное состояние, ° Наличие потенциалов одновременно на выходах 13„ и 13 устройства говорит о том, что в сис7 12 теме два требования в очереди. Потенциал с выхода триггера 39 через формирователь 44 вызовет срабатыва2 ние шифратора 46,. который присвоит адрес требованию, ставшему в очередь.

Код адреса импульсом с выхода элемента ИЛИ 45 запишется в регистр 48„, содержимое которого перепишется в регистр 48 . Потенциал будет на выходах элементов ИЛИ 52 и 52,, но только на выходе элемента И 53 будет потенциал, который разрешит прохождение через элементы И 51 и элементы ИЛИ 36 кода номера первого требования в очереди на входы дешифратора 42. Таким образом, по прежнему на выходе 41„ будет потенциал.

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

16 блока 2„ случайного кода, величина которого меньше величины кода пз

Тогда состояния блоков 3 и 7 не изменятся, а в блоке формирования выходного потока откроется элемент И

323, так как присутствуют потенциалы на входах 14, 18з и выходе элемента

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

По импульсу с входа 12, в блоке

8„ откроется элемент И 40„, который импульсом со своего выхода перебросит триггер 39„ в нулевое состояние.

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

I импульса с выхода 13„ сработает элемент ИЛИ 43 и будет обнулен регистр

48, так как на его управляющем входе был потенциал от элемента И 53

Теперь в очереди первым стоит требование, код номера которого записан в регистре 48 ..

Если за время занятости системы обслуживанием требований старшего приоритета в систему будут поступать требования младших приоритетов, что моделируется блоками 2 -2, то они будут аналогично становиться в очередь в блоках 8 -8, до окончания обслуживания требований старшего приоритета. Это обеспечивается наличием управляющего сигнала на входах

29771

24 блоков 2 -2 что моделирует тольгп кс приход требований в систему, так как поступление требования i-го приоритета при условии отсутствия требований 1-(i-1)-х приоритетов переключает блоки формирования состояний

2. — 2 на режим моделирования тольjб) ко поступления требований.

В блоке формирования выходного потока изменений не будет, а в блоке формирования входного потока будет зафиксировано поступление требования.

Таким образом, в процессе моделирования приоритетных систем массового обслуживания возможно получение следующей информации: модель входного потока для системы в целом по анализу потока импульсов на выходе 9 модель выходного потока для системы в целом по анализу потока импульсов на выходе 10 устройства; модель входного потока требований i-ro приоритета по анализу потенциалов на выходах 11 устройства; модель выходного потока требований i-го приоритета по анализу потенциалов на выходах 12 устройства; модель времени задержки в системе требований i-х приоритетов по анализу потенциалов на выходах

13 устройства.

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

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

1229771 потока и блок формирования выходного потока, причем К-й блок формирования состояний (К = 2,...,Г1) содержит дополнительный коммутатор и дополнительный узел задания законов распределения, информационные входы дополнительного коммутатора подключены соответственно к выходам генератора случайного кода, первая группа выходов дополнительного коммутатора соединена с информационными входами узла задания законов распределения, а вторая группа — с информационными входами первой группы дополнительного узла задания законов распределения, управляющий вход дополнительного коммутатора и вход разрешения считывания дополнительного узла задания законов распределения К-го блока формирования состояний объединены и подключены к выходу (К-1)-ro элемента И-НЕ блока управления, группа информационных входов дополнительных узлов задания законов распределения блоков формирования состояний является второй группой информационных входов устройства, блок формирования входного потока содержит M групп элементов задержки, И групп элементов И, группу элементов ИЛИ и элемент ИЛИ, входы которого подключены соответственно к выходам элементов

ИЛИ группы, входы которых соединены с выходами элементов И соответствующей группы, первые входы элементов И групп подключены к выходам элементов задержки соответствующих групп, вторые входы элементов И всех групп объединены и подключены к выходу генератора тактовых импульсов, третий вход P-го элемента И каждой группы (Р = 1, п — 2) соединен с выходом (P + 1) -ro элемента задержки соответствующей группы, выход элемента

ИЛИ блока формирования входного потока является первым выходом устройства, блок формирования выходного потока содержит И групп элементов задержки, Г1 групп элементов И, группу элементов ИЛИ и элемент ИЛИ, выход которого является вторым выходом устройства, а входы подключены соответственно к выходам элементов ИЛИ группы, первые входы элементов И групп подключены к выходам элементов задержки соответствующих групп, вторые входы элементов И всех групп объединены и соединены с выходом генератора тактовых импульсов, третий вход Т-го элемента И каждой группы (Т = 2, n — 1) соединен с выходом (Т-1)-го .элемента задержки соответствующей группы, выходы элементов И каждой группы подключены к входам соответствующего элемента ИЛИ группы, каждый блок формирования времени задержки содержит четыре группы элементов И, группу триггеров, три элемента ИЛИ, две

10 группы элементов ИЛИ, группу регистров памяти, группу формирователей импульсов, шифратор и дешифратор, выходы элементов И первой группы соединены соответственно с первыми вхо15 дами триггеров группы, вторые входы которых соединены с выходами соответствующих элементов И второй гру"пы, первые входы элементов И второй группы объединены и подключены к вы2О ходу первого элемента ИЛИ, вторые входы элементов И второй группы объединены и подключены к выходу соответствующего элемента ИЛИ группы блока формирования входного потока,пер25 вые выходы триггеров группы блока формирования временной задержки соединены с входами второго элемента ИЛИ и входом соответствующего формирова- . теля импульсов группы, первый выход

P-го триггера группы соединен с соответствующими входами элементов И второй группы, имеющих номер, больший Р, второй выход В-ro триггера группы (В = 1, n — 1) подключен к соответствующему входу В-го элемен35 та И второй группы, выходы формирователей импульсов группы соединены с соответствующими входами шифратора и третьего элемента ИЛИ, выходы

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

45 разрядным входам первого регистра памяти группы, разрядные выходы P-ro регистра памяти группы соединены соответственно с разрядными входами (P + 1)-ro регистра памяти группы, разрядные выходы каждого регистра памяти группы соединены с входами соответствующего элемента ИЛИ первой группы и первыми входами соответствующих элементов И четвертой группы, выход Т-ro элемента ИЛИ первой группы подключен к прямому входу Т-го элемента И третьей группы и к соответствующим инверсным входам всех элементов И третьей группы с номеf2 ром, меньшим Т, выход каждого элемента И третьей группы соединен с установочным входом соответствующего регистра памяти группы и вторыми входами соответствующих элементов И четвертой группы,, выходы подключены к входам соответствующего элемента ИЛИ второй группы, выходы которых соединены соответственно с входами дешифратора, выходы которого подключены к первым входам соответствующих элементов И первой группы, вторые входы которых объединены и соединены с выходом соответствующего элемента

ИЛИ группы блока формирования выходного потока, первый вход. (К-1)-го уэ™ма памяти каждого блока формирования состояний соединен с соответствующими входами всех элементов И-HE .с номером, не меньшим К, блока управления, В-й выход узла памяти каждого блока формирования состояний подключен к входу В-ro элемента задержки соответствующей группы блока формирования входного потока, п-й выход узла памяти каждого блока фор?9771 !2 мирования состояний соединен с третьим входом (n-t)-го элемента И соответствующей группы блока формирования входного потока, первые входы элементов И каждой группы блока формирования выходного потока соединены с первыми выходами узла памяти соответствующего блока формирования состояний, остальные выходы узла nafp мяти К-ro блока формирования состояний подключены соответственно к входам элементов задержки К-й группы блока формирования выходного потока, а входы первого элемента ИЛИ блока формирования времени задержки подключены к выходам узла памяти соответствующего блока формирования состояний, первой, второй и третьей группами выходов устройства являются

gp соответственно выходы 1лементов ИЛИ группы блока формирования входного потока, выходы элементов ИЛИ группы блока формирования выходного потока и первые выходы триггеров группы блоков формирования времени задержки.

1229771

° ° °

6Ч 5t б л

1229771

pic y al м и у лл

Фиа S

f22977

r gt ЪФ-Ф

/ф

М а/

CF е Иу М3 Юуп

99k 1

1229771

4ф $P 41< 4ф 47с

4Ь|сУ

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

Редактор P.Öèöèêà Техред Г .Гербер Корректор А.Тяско

Заказ 2451/49 Тираж 671 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. проектная, 4