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

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

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

На фиг. 1 приведена схема предлагаемого устройства; на фиг.2 - структурная схема первого блока формирования состояний; на фиг. 3 - структурная схема дополнительных (М-1) блоков формирования состояний; на фиг. 4 - функциональная схема блока формирования входного потока; на фиг. 5 - функциональная схема блока форьшрования выходного потока;/ на фиг. 6 - функциональная схема блока управления; на фиг. 7 и фиг. 8 27, М групп элементов И 28, М групп элементов 29 задержки, группу элементов ИЛИ 30.

Блок 4 формирования выходного по- 5 тока (фиг. 5) содержит элемент ИДИ 31,, М групп элементов И 32, М групп элементов 33 задержки, группу элементов ИЛИ 34.

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

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

функциональная схема блока формирова- 33 первую группу элементов ИЛИ 52,третью

ния времени задержки; на фиг. 9 - функциональная схема первого узла. задания законов распределения блоков формирования состояний.

Устройство моделирования приоритетных систем массового обслуживания (фиг. 1) содержит генератор t тактовых импульсов, группу блоков 2 формирования ссх:тояний, блок 3 формирования входного потока, блок 4 формирования выкодного потока,, первую группу установочных входов 5,- вторую группу установочных входов 6, блок 7 управления, группу блоков 8 формирования времени задержки, первый выход 9 устройства, второй выход 10 устройств,, группы выходов 11-13 устройства.

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

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

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

группу элементов И 53.

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

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

По установочным входам 5 в узлы 17 и 25 задания законов распределения блоков 2 формирования состояний заносятся коды матрицы переходных вероятностей, которые определяют фор-

35

40

45

мальную модель (автоматную) системы массового обслуживания: вероятностей Tfjj -перехода системы в j-e состояние, при условии, что она в предыдущий момент времени находилась в i-м состоянии .

По установочным входам 6 в узлы 23 задания законов распределения блоков 2 формирования состояний заносятся коды вероятности ТТ -вероятности

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

Устройство моделирует функционирование одноканальной приоритетной

5S системы массового обслуживания с ожиданием. Причем, вводится ограничение на максимально допустимую длину очереди,- которая не более величины п-1,

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

Блок 4 формирования выходного по- тока (фиг. 5) содержит элемент ИДИ 31,, М групп элементов И 32, М групп элементов 33 задержки, группу элементов ИЛИ 34.

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

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

группу элементов И 53.

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

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

По установочным входам 5 в узлы 17 и 25 задания законов распределения блоков 2 формирования состояний заносятся коды матрицы переходных вероятностей, которые определяют фор-

мальную модель (автоматную) системы массового обслуживания: вероятностей Tfjj -перехода системы в j-e состояние, при условии, что она в предыдущий момент времени находилась в i-м состоянии .

По установочным входам 6 в узлы 23 задания законов распределения блоков 2 формирования состояний заносятся коды вероятности ТТ -вероятности

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

Устройство моделирует функционирование одноканальной приоритетной

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

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

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

Р

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

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

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

Импульс генератора 1 подается на тактовые входы 14 блоков 2 формирования состояний блоков формирования входного 3 и выходного 4 потоков. Так как в регистрах 54 узлов 17 и 25 задания законов распределения блоков 2 формирования состояний хранятся коды1Т)о ,4 ,,, , то на выходах регистров 54 и сумматоров 55 формируются коды для К-го блока 2:

15

20

,0 . Л-,о

+

ia

+ ;.

Предположим, что в системе нет требований, а генератор 16 в блоке 2 выработал случайный код А, численная величина которого меньше величины кода Идо Код А подается на

циал с выхода схемы 57 сравнения закроет элементы И 58 и сигнал будет- только на первом выходе узла 17.

Этим моделируется событие перехо- 5 да состояния обслуживания за время 4t нулевого числа требований 1-го приоритета в такое же состояние.

Сигнал с выхода узла 17 поступает на вход коммутатора 15 и проходит )0 на выход коммутатора 15 и на вход узла 19 памяти блока 2 .

Так как в системе нет требований, то имеются потенциалы на всех выходах 18, - 18 блока 2, .. -С выхода 18 блока 2, снимается потенциал, который подается на второй информационный вход узла 17, а также на входы блока 7 управления, блоков формирования входного потока 3 и выход ного потока 4. В блоке 3 формирования входного потока (фиг. 4) потенциал с входа через элемент 29 задержки времени поступает на элемент И 28, но так как потенциал на 25 входе 18 отсутствует, то не будет потенциала и на выходах элементов ИЛИ 30, и ШШ 27, что говорит о том, что за прошедшее время в систему не поступило требований. Импульсы на выходах 9 и 11 устройства отсутствуют. В блоке 4 формирования выходного потока также отсутствуют импульсы на выходах 10 и 12.

В блоке 7 управления (фиг. 6) потенциал по входу 18 закроет все 35 элементы И-НЕ 35. На выходах 24 блока 7 будут нулевые потенциалы, которые подаются на управляющие входы 24 блоков 2 формирования состояний. 1 В этом случае блоки 2 раб отают анало гично блоку 2 . Тогда через коммутатор 22 вьфабатываемый генератором 2t случайный код поступает в узел 25 задания законов распределений, а узел 23 задания законов распределения не 5 работает. Так как на выходах

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

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

30

40

входы узла 17 (на входы схем 57 срав- 552, вырабатывает код, величина кото- нения). Так как код А меньше по ве-рого меньше числа Идо но боль- личине Тг , то на выходах схем 57ше числаТ, . В этом случае в узле cpaвнeн я будут ЛЬтенциалы, и потен-17 задания законов распределения

15

25

20

25

25

30

35 5

40

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

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

будет открыт элемент И 28 . Тогда

1

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

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

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

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

С приходом очередного .импульса от генератора 1 тактовых импульсов ге- нератор 16 блока 2, вырабатьгоает код величина которого больше + F , но меньше Ж + 11.. + На выходе узла 17 задания законов распределени будет потенциал, который пройдет че- рез коммутатор 15 на вход узла 19 памяти.

Потенциал с выхода 18j блока 2, подается на вход блока 3 формирова- ния входного потока, открывает элемент И 28, и на выходах 9 и 11 устройства появятся импульсы, что гово

, O

5

Q

5 0

0

0

рит о том, что в систему поступило еще одно требование 1-го п;::йоритета.

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

Так как второе требование первого приоритета будет задержано на время, оставшееся до конца обслуживания требования, поступившего ранее, то включается в работу блок 8 формирования времени задержки, определяющий время задержки требований первого приоритета. Функционирует он следующим образом. Потенциал с информационного входа ISj проходит через элемент ИЛИ 37. С появаением импульса йа входе 1 1 через элемент И 38 триггер 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.J и 13 устройства говорит о том, что в сие7

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

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

Пусть на следующем такте закончилось обслуживание требования, поступившего первым в систему. Это соответствует выработке генератором 16 блока 2 случайного кода, величина которого меньше величины кода Ti j,j Тогда состояния блоков 3 и 7 не изменятся, а в блоке формирования выходного потока откроется элемент И 32, так как присутствуют потенциалы на входах 14, 18,, и выходе элемента 33 задержки. Таким образом, появятся импульсы на выходах 10, 12, устройства, что говорит о том, что.требование 1-го приоритета покинуло систему.

По импульсу с входа 12, в блоке 8 откроется элемент И 40 , который импульсом со своего выхода перебросит триггер 39-t в нулевое состояние. С выхода 13, блока 8, исчезнет потенциал, что говорит о том, что время ожидания первого сообщения (требования) в очереди истекло и оно принято к обслуживанию. По заднему фронту импульса с выхода 13 сработает элемент ИЛИ 43 и будет обнулен регистр 48j, так как на его управляющем входе был потенциал от элемента И 53 . Теперь в очереди первым стоит требование, код номера которого записан в регистре 48,, .

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

297718

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

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

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

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

50

91

потока и блок фopмv poвaння вьгхоцног о потока, причем К-й блок формирования состояний (К 2,.,.,М) содержит дополнительный коммутатор и дополнительный узел задания законов распре- деления, информационные входы дополнительного коммутатора подключены соответственно к выходам генератора случайного кода, первая группа выходов дополнительного коммутатора соединена с информационными входами узла задания законов распределения, а вторая группа - с информационными входами первой группы дополнительного узла задания законов распределения, управляющий вход дополнительного коммутатора и вход разрешения считывания дополнительного узла задания законов распределения К-го блока формирования состояний объединены и подключены к выходу (К-1)-го элемента И-НЕ блока управления, группа информационных входов дополнительных узлов задания законов распределения блоков формирования состояний является второй группой информационных входов устройства, блок формирования входного потока содержит М групп элементов задержки, М групп элементов И, группу элементов ИЛИ и элемент ИЛИ, входы которого подключены соответственно к выходам элементов ИЛИ группы, входы которых соединены с выходами элементов И соответствующей группы, первые входы элементов И групп подключены к выходам элементов задержки соответствующих групп, вторые входы элементов И всех групп объединены и подключены к выходу генератора тактовых импульсов, третий вход Р-го элемента И каждой группы (Р 1, п - 2) соединен с выходом (Р + 1)-го элемента задержки соответствующей группы, выход элемента ИЛИ блока формирования входного потока является первым выходом устройства, блок формирования выходного потока содержит М групп элементов задержки, М групп элементов И, группу элементов ИЛИ и элемент ИЛИ, выход которого является вторым выходом устройства, а входы подключены соответственно к выходам элементов ИЛИ группы первые входы элементов И групп подключены к выходам элементов задержки соответствующих групп, вторые входы элементов И всех групп объединены и соединены с выходом генератора тактовых импульсов, третий вход Т-го эле

0

5

0

5

97

0

5

0

5

O

5

7110 .

ме}1та И каждой группы (Т 2, п - 1) соединен с выходом (Т-1)-го .элемента задержки соответствующей группы, выходы элементов И каждой группы подключены к входам соответствующего элемента ИЛИ группы, каждый блок формирования времени задержки содержит четыре группы элементов И, группу триггеров, три элемента ИЖ, две группы элементов ИЛИ, группу регистров памяти, группу формирователей импульсов, шифратор и дешифратор, выходы элементов И первой группы соединены соответственно с первыми входами триггеров группы, вторые входы которых соединены с выходами соответствующих элементов И второй грул- пы, первые входы элементов И второй группы объединены и подключены к выходу первого элемента ИЖ, вторые входы элементов И второй группы объединены и подключены к выходу соответствующего элемента ИЛИ группы блока формирования входного потока,первые выходы триггеров группы блока формирования временной задержки соединены с входами второго элемента ИЛИ и входом соответствующего формирова- теля импульсов группы, первый выход Р-го триггера группы соединен с соответствующими входами элементов И второй группы, имеющих номер, больший Р, второй выход В-го триггера группы (В 1, п - 1) подключен к соответствующему входу В-го элемента И второй группы, выходы формирователей импульсов группы соединены с соответствующими входами шифратора и третьего элемента ИЛИ, выходы второго и третьего элементов ИЛИ подключены соответственно к входам разрешения записи и входам сброса регистров памяти группы, выходы шифратора подключены соответственно к разрядным входам первого регистра памяти группы, разрядные выходы Р-го регистра памяти группы соединены соответственно с разрядными входами (Р 1)-го регистра памяти группы, разрядные выходы каждого регистра памяти группы соединены с входами соответствующего элемента ИЛИ первой группы и первыми входами соответствующих элементов И четвертой группы, выход Т-го элемента ИЛИ первой группы подключен к прямому входу Т-го элемента И третьей группы и к соответствующим инверсным входам всех элементов И третьей группы с номером, меньшим Т, выход каждого элемента И третьей группы соединен с установочным входом соответствующего регистра памяти группы и вторыми входами соответствующих элементов И четвертой группы,, выходы подключены к входам соответствующего элемента ИЛИ второй группы, выходы которых соединены соответственно с входами дешифратора, выходы которого подключены к первым входам соответствующих элементов И первой группы, вторы входы которых объединены и соединены с выходом соответствующего элемента ИЛИ группы блока формирования выходного потока, первый вход- (К-1)-го узла памяти, каждо1 о блока формирования состояний соединен с соответствующими входами всех элементов И-НЕ .с номером, не меньшим К, блока управления, В-й выход узла памяти каждого блока формирования состояний подключен к входу В-го элемента задержки соответствующей группы блока формирования входного потока, п-й выход узла памяти каждого блока фор

10

2977112

мирования состояний соединен с третьим входом (n-l)-ro элемента И соответствующей группы блока формирования входного потока, первые входы элементов И каждой группы блока формирования выходного потока соединены с первыми выходами узла памяти соответствующего блока формирования состояний, остальные выходы узла памяти К-го блока формирования состояний подключены соответственно к входам элементов задержки К-й группы блока формирования выходного потока, а входы первого элемента ИЛИ блока формирования времени задержки подключены к выходам узла памяти соответствующего блока формирования состояний, первой, второй и третьей группами выходов устройства являются соответственно выходы -«лементов ИЛИ группы блока формирования входного потока, выходы элементов ИЛИ группы блока формирования выходного потока и первые выходы триггеров 25 группы блоков формирования времени задержки.

f5

20

al 1B № , ,,/У; fSr ffS 191,18

4S SO 47,4 47„

4r,

9otl

Опвл9(гУ

55

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

«te/

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

Редактор Р.Цицика Техред Г. Гербер Корректор А. Тяско

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

ВИНИЛИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. А/5

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