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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУ БЛИН 801229771 А 1 1511 4 С 06 Р 15/20 ОПИСАНИЕ ИЗОБРЕТЕНИЯ ТОРСНОМУ СВИДЕТЕЛЬСТВУ Р 17 радиотех(54) УСТРОЙСТВО ДЛЯ МО СИСТЕИ МАССОВОГО ОБСЛУ (57) Изобретение относи лительной технике и мож польэовано для моделир описываемых аппаратом ДЕЛИРОВАНИЯ ВАНИЯ с сет быть исвания систем еории массоГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРпо делАм изОБРетений и ОтнРытий(56) Авторское с9 1088004, кл. САвторское свФ, 113747, кл. С вого обслуживания, например вычислительных систем, систем передачи данных, элементов производственных процессов торговых предприятий и т.д.Цель изобретения - расширение функциональных воэможностей устройстваза счет моделирования приоритетныхсистем массового обслуживания. Цельдостигается эа счет введения в устройство блоков формирования состояний, времени задержки, входного по-тока и выходного потока с соответствующими функциональными связями между ними и известными блоками. Устройство моделирует функционирование одноканальной приоритетной системы массового обслуживания с ожиданием ивведением ограничения на максимальнодопустимую длину очереди. 9 ил.Заказ роизводственно-полиграФическое предприятие, г. Ужгород, ул. проектная, 4 2451/49 Тираж 671 ВНИИПИ Государствен по делам изобрете 11 Э 035, Москва, Ж, Подписиого комитета СССРий и открытийРаушская наб., д, 12297Изобретение относится к вычислительной технике и может быть использовано для моделирования систем, описываемых аппаратом теории массовогообслуживания, например вычислительных систем, систем передачи данных,элементов производственных процессовторговых предприятий и т.д,Целью изобретения является расширение функциональных воэможностей за 1 Осчет моделирования приоритетных систем массового обслуживания,.На фиг. 1 приведена схема предла"гаемого устройства; на фиг.2 - структурная схема первого блока формиро- цвания состояний; на фиг. 3 - структурная схема дополнительных (М)блоков формирования состояний; нафиг. 4 - функциональная схема блокаформирования входного потока; на 2 рфиг. 5 - функциональная схема блокаформирования выходного потока;, нафиг. 6 функциональная схема блокауправления; на фиг. 7 и фиг. 8функциональная схема блока формирования времени задержки; на фиг. 9 -функциональная схема первого узла,задания законов распределения блоковформирования состояний.Устройство моделирования приоритетных систем массового обслуживания (фнг. 1) содержит генератортактовых импульсов, группу блоков 2формирования состояний, блок 3 формирования входного потока,блок 4формирования выходного потока первуюгруппу установочных входов 5; вторуюгруппу установочных входов 6, блок7 управления, группу блоков 8 формирования времени задержки, первыйвыход 9 устройства, второй выход 10устройства группы выходов 11 - 13устройства./ 3Первый блок 2 формирования состояний (фиг. 2) содержит вход 14, коммутатор 15, генератор 16 случайногокода, узел 17 задания законов рас"пределения, выходы 18, узел 19 памяти.Второй и последующие блоки 2 формирования состояний (фиг. 3) содер- Ожат коммутатор 20, генератор 21 случайного кода, дополнительный коммутатор 22, дополнительный узел 23задания законов распределения, вход24, узел 25 задания законов распре- Иделения, узел 26 памяти,Блок 3 формирования входного потока (фиг, 4) содержит элемент ИЛИ 71 227, М групп элементов И 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, группусхем 5 сравнения и вторую группуэлементов И 58.Устройство моделирования приоритетных систем массового обслуживанияработает следующим образом,По установочным входам 5 в узлы17 н 25 задания законов распределения блоков 2 формирования состоянийзаносятся коды матрицы переходныхвероятностей, которые определяют формальную модель (автоматную) системымассового обслуживания: вероятностей,и -перехода системы в 3-е состояние,при условии, что она в предццущнймомент времени находилась в д-м состоянии.По установочным входам 6 в узлы23 задания законов распределения блоков 2 формирования состояний заносятся коды вероятности % -вероятности1поступления требования за заданныйотрезок времени для потока -го приоритета.Устройство моделирует функционирование одноканальной приоритетнойсистемы массового обслуживания с ожиданием. Причем; вводится ограничениена максимально допустимую длину очереди,. которая не более величины и29771 4 3 12 Рассмотрим случай простейшего потокаотребований на входе по каждому потоку при экспонеициальном распределении длительности .обслуживания.Для Ординарного входящего потока требований матрицу вероятностей перехода моделируемой системы массового обслуживания возможно представить в следующем виде 5 О 5 20 25 30 35 40 45 50 55 ГовО 1 го фО, 0 О, О Оу Оуу л - 1 пэ ь 11О, О 1,ЪО При моделировании приоритетных систем массового обслуживания важнознать моменты выхода обслуженных требований каждого приоритета из системы, моменты времени поступления сообщений в систему, время задержкитребований каждого приоритета. Всюэту информацию позволяет получитьустройство.Информация о входном и выходномпотоках требований снимается с выхо,цов 9 и 10. Информация о входных ивыходных потоках требований по каждому приоритету снимается соответственно с выходов 11 и 12 С выходов13 снимаются потенциалы, длины которых (во времени) несут информацию овеличинах отрезков времени задержкитребований каждого потока,Рассмотрим поблочно работу устройства.Импульс генератора 1 подаетсяна тактовые входы 14 блоков 2 формирования состояний блоков Формирования входного 3 и выходного 4 потоков. Так как в регистрах 54 узлов17 и 25 задания законов распределения блоков 2 формирования состоянийхранятся кодыП, ,П .;П.то на выходах регистров 54 и сумматоров 55 формируются коды для К-гоблока 2:Ч.,11;, + Ъ Е+ и;, +7 в+а + 0Предположим, что в системе неттребований, а генератор 16 в блоке2 выработал случайный код А, численная величина которого меньше величины кода 7 . Код А подается навходы узла 17 на входы схем 57 сравнения). Так как код А меньше по величине , то на выходах схем 57ООсравнения будут ЛЬтенциалы, и потенциал с выхода схемы 57 сравнения закроет элементы И 58 и сигнал будет только на первом выходе узла 17.Этим моделируется событиеперехода состояния обслуживания за время ,6 С нулевого числа требований 1-го приоритета в такое же состояние.Сигнал с выхода узла 17 поступает на вход коммутатора 15 и проходит на выход коммутатора 15 и на вход узла 19 памяти блока 2, .Так как в системе нет требований, то имеются потенциалы на всех выходдах 18, - 18, блока 2, С выхода 18, блока 2, снимается потенциал, который подается на второй информа 1ционный вход 18 узла 17, а также на1входы блока 7 управления, блоков формирования входного потока 3 и выход ного потока 4. В блоке 3 Формирования входного потока (фиг. 4) потенциал с входа 18 через элемент 29 задержки времени поступает на элемент И 28, но так как потенциал на входе 18 отсутствует, то не будет потенциала и на выходах элементов ИЛИ 30, и ИЛИ 27, что говорит о том, что эа прошедшее время в систему не поступило требований, Импульсы на выходах 9 и 11 устройства отсутствуют. В блоке 4 Формирования выходного потока такыре отсутствуют импульсы на выходах 1 О и 12.В блоке 7 управления (фиг, 6) потенциал по входу 18, закроет все элементы И-НЕ 35. На выходах 24 блока 7 будут нулевые потенциалы, которые подаются на управляющие входы 24 блоков 2 формирования состояний. 1 В этом случае блоки 2 работают анало гично блоку 2 . Тогда через коммутатор 22 вырабатываемый генератором 21 случайный код поступает в узел 25 задания законов распределений, а узел 23 задания законов распределения неЪ работает, Так. как на выходах 18 -1 Ц блоков 2 потенциалы отсутствуют, то блоки 8 Формирования времени задержки не работают. В системе отсутствует очередь.Предположим, что в систему поступило требование старшего приоритета за очередной отрезок времени. Тогда с приходом импульса от генератора генератор 16 случайного кода блока 2, вырабатывает код, величина которого меньше числа 3 +% но больше числами . В этом случае в узле 7 задания законов распределенияблока 2 срабатывают соответствующие схемы 57 сравнения. Сигнал с выхода схемы 57; сравнения закроет1 гэлементы И 58, а на втором выходе узла 17 будет потенциал, который пройдет через коммутатор 15 на вход узла 19 памяти, и на втором выходе блока 2 формирования состояний по 1явится потенциал. Состояние выходов 110 других блоков 2 не изменится;Потенциал с блока 2 поступит на вход блока 3 формирования входного потока. Так как в этот момент времени присутствует потенциал на выходе элемента 29. задержки времени, то1будет открыт элемент И 28 . Тогда на выходах 9 и 11 блока формирования входиого потока появится потенциал, что свидетельствует о поступ ленин в систему требования 1-го приоритета за отрезок времени.Так как потенциал на входе 18 блока 4 формирования выходного потока исчезнет раньше чем появится на 25 выходе элемента 33 задержки, то состояние выходов блока 4 не изменится. Не участвуют в работе также и блоки 8 формирования времени задержки, 30Так как на входе 18, блока 7 управления не будет потенциала, то на его выходах 24 появятся потенциалы, которые поступят на соответствующие входы 24 блоков 2- 2, формирования состояний. Коммутатор 22 подключает в работу узлы 23 задания законов распределений блоков 2 - 2,.Пусть в очередной такт времени в систему поступит еще одно требование старшего приоритета. Предыдущее требование еще не было обслужено. В системе возникает очередь. Рассмотрим данный процесс.С приходом очередного, импульса от генератора 1 тактовых импульсов генератор 16 блока 2, вырабатывает код, величина которого больше 11 + Г1 О М но меньше 7 + Г + Г . На выходе1 О 11узла 17 задания законов распределения будет потенциал, который пройдет через коммутатор 15 на вход узла 19 памяти. Потенциал с выхода 18 блока 2 подается на вход блока 3 Формирования входного потока, открывает элемент И 28 и на выходах 9 и 11 устройства появятся импульсы, что говорит о том, что в систему поступило еще одно требование 1-го и;.иоритета.Блок 4 формирования выходного потока и блок 7 управления не изменяют своего состояния.Так как второе требование первого приоритета будет задержано на время, оставшееся до конца обслуживания требования, поступившего ранее, то включается в работу блок 8 формирования времени задержки, определяющий время задержки требований первого приоритета. Функционирует он следующим образом. Потенциал с информационного входа 18 проходит через элемент ИЛИ 37. С появлением импульса на входе 11 через элемент И 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 и 13 г устройства говорит о том, что в сис 7 12 теме два требования в очереди. Потенциал с выхода триггера 39 через формирователь 44 вызовет срабатывание шифратора 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, исчезнет потенциал, что говорит о том, что времяожидания первого сообщения (требования) в очереди истекло и оно принято к обслуживанию. По заднему фронту1импульса с выхода 13 сработает элемент ИЛИ 43 и будет обнулен регистр 48, так как на его управляющем входе был потенциал от элемента И 53 Теперь в очереди первым стоит требование, код номера которого записан в регистре 48.Если за время занятости системы обслуживанием требований старшего приоритета в систему будут поступать требования младших приоритетов, что моделируется блоками 2 -2 , то они будут аналогично становиться в очередь в блоках 8 -8, до окончания обслуживания требований старшего приоритета. Это обеспечивается наличием управляющего сигнала на входах29771 5 10 15 20 25 30 35 40 45 50 55 24 блоков 2 -2 что моделирует тольгткс приход требований в систему, так как поступление требования 1-го приоритета при условии отсутствия требований 1-(1-1)-х приоритетов переключает блоки формирования состояний 2. - 2 на режим моделирования только поступления требований,В блоке формирования выходного потока изменений не будет, а в блоке формирования входного потока будет зафиксировано поступление требования.Таким образом, в процессе моделирования приоритетных систем массового обслуживания возможно получение следующей информации: модель входного потока для системы в целом по анализу потока импульсов на выходе 9 модель выходного потока для системы в целом по анализу потока импульсов на выходе 1 О устройства; модель входного потока требований -го приоритета по анализу потенциалов на выходах 11 устройства; модель выходного потока требований 1-го приоритета по анализу потенциалов на выходах 12 устройства; модель времени задержки в системе требований 1-х приоритетов по анализу потенциалов на выходах 13 устройства. Формула изобретения Устройство для моделирования систем массового обслуживания, содержащее блок управления, состоящий из группы элементов И-НЕ, первый блок формирования состояний, состоящий из последовательно соединенных гене-ратора случайного кода, узла задания законов распределения, коммутатора и узла памяти, выходы которого соединены соответственно с входами разрешения считывания узла задания законов распределения, информационные входы которого являются первыми информационными входами устройства, вход запуска генератора случайного кода и управляющий вход коммутатора блока формирования состояний подключены к выходу генератора тактовых импульсов устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей эа счет моделирования приоритетных систем массового обслуживания, оно содержит (М) дополнительных блоков формирования состояний, М блоков формирования времени задержки, блок формирования входногопотока и блок формирования выходногопотока, причем К-й блок формированиясостояний (К = 2Г 1) содержит дополнительный коммутатор и дополнительный узел задания законов распределения, информационные входы дополнительного коммутатора подключенысоответственно к выходам генератораслучайного кода, первая группа выходов дополнительного коммутатора соединена с информационными входами узла задания законов распределения, авторая группа - с информационнымивходами первой группы дополнительного узла задания законов распределения, управляющий вход дополнительного коммутатора и вход разрешения считывания дополнительного узла заданиязаконов распределения К-го блока формирования состояний объединены иподключены к выходу (К)-го элемента И-НЕ блока управления, группа информационных входов дополнительныхузлов задания законов распределенияблоков формирования состояний является второй группой информационныхвходов устройства, блок формированиявходного потока содержит М группэлементов задержки, М групп элементов И, группу элементов ИЛИ и элемент ИЛИ, входы которого подключенысоответственно к выходам элементовИЛИ группы, входы которых соединеныс выходами элементов И соОтветствующей группы, первые входы элементов Игрупп подключены к выходам элементовзадержки соответствующих групп, вторые входы элементов И всех группобъединены и подключены к выходу генератора тактовых импульсов, третийвход Р-го элемента И каждой группы(Р + 1) -го элемента задержки соответствующей группы, выход элементаИЛИ блока формирования входного потока является первым выходом устройства, блок формирования выходного потока содержит М групп элементов задержки, М групп элементов И, группу элементов ИЛИ и элемент ИЛИ, выход которого является вторым выходом устройства, а входы подключены соответственно к выходам элементов ИЛИ группы,первые входы элементов И групп подключены к выходам элементов задержкисоответствующих групп, вторые входыэлементов И всех групп объединены исоединены с выходом генератора тактовых импульсов, третий вход Т-го элемента И каждой группы (Т = 2, и - 1) соединен с выходом (Т)-го .элементазадержки соответствующей группы, выходы элементов И каждой группы подключены к входам соответствующегоэлемента ИЛИ группы, каждый блок формирования времени задержки содержитчетыре группы элементов И, группутриггеров, три элемента ИЛИ, две 10 группы элементов ИЛИ, группу регистров памяти, группу формирователейимпульсов, шифратор и дешифратор,выходы элементов И первой группы соединены соответственно с первыми вхо дами триггеров группы, вторые входыкоторых соединены с выходами соответствующих элементов И второй гру"- пы, первые входы элементов И второйгруппы объединены и подключены к вы О ходу первого элемента ИЛИ, вторыевходы элементов И второй группы объединены и подключены к выходу соответствующего элемента ИЛИ группы блока формирования входного потока,пер вые выходы триггеров группы блокаформирования временной задержки соединены с входами второго элемента ИЛИи входом соответствующего формирователя импульсов группы, первый выходР-го триггера группы соединен с соответствующими входами элементов Ивторой группы, имеющих номер, больший Р, второй выход В-го триггерагруппы (В = 1, и - 1) подключен ксоответствующему входу В-го элемента И второй группы, выходы формирователей импульсов группы соединеныс соответствующими входами шифратора и третьего элемента ИЛИ, выходы 40второго и третьего элементов ИЛИподключены соответственно к входамразрешения записи и входам сбросарегистров памяти группы, выходы шифратора подключены соответственно к 45разрядным входам первого регистрапамяти группы, разрядные выходы Р-горегистра памяти группы соединены соответственно с разрядными входами(Р + 1)-го регистра памяти группы,разрядные выходы каждого регистрапамяти группы соединены с входамисоответствующего элемента ИЛИ первойгруппы и первыми входами соответствующих элементов И четвертой группы,выход Т-го элемента ИЛИ первой группы подключен к прямому входу Т-го элемента И третьей группы и к соответствующим инверсным входам всех элементов И третьей группы с номе ром, меньшим Т, выход каждого элемента И третьей группы соединен сустановочным входом соответствующегорегистра памяти группы и вторыми входами соответствующих элементов И четвертой группы выходы подключены квходам соответствующего элемента ИЛИвторой группы, выходы которых соединены соответственно с входами дешифратора, выходы которого подключены к первым входам соответствующих элементов И первой группы, вторыевходы которых объединены и соединеныс выходом соответствующего элементаИЛИ группы блока формирования выходного потока, первый вход (К)-гоуэма памяти. каждого блока формирования состояний соединен с соответствующими входами всех элементов И-НЕ.с номером, не меньшим К, блока управления, В-й выход узла памяти каждого блока формирования состоянийподключен к входу В-го элемента задержки соответствующей группы блокаформирования входного потока, п-йвыход узла памяти каждого блока фор 29771 2мирования состояний соединен с третьим входом (и)-го элемента И соответствующей группы блока формирования входного потока, первые входыэлементов И каждой группы блока формирования выходного потока соединены с первыми выходами узла памятисоответствующего блока формированиясостояний, остальные выходы узла па мяти К-го блока формирования состояний подключены соответственно к входам элементов задержки К-й группыблока формирования выходного потока, а входы первого элемента ИЛИ 15 блока формирования времени задержкиподключены к выходам узла памяти соответствующего блока формированиясостояний, первой, второй и третьейгруппами выходов устройства являются ро соответственно выходы 1 лементов ИЛИгруппы блока формирования входногопотока, выходы элементов ИЛИ группы блока формирования выходногопотока и первые выходы триггеровгруппы блоков формирования временизадержки.