Устройство для моделирования марковских потоков сигналов

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИК 4 51) САНИЕ ИЗОБРЕТЕН ыков ль 20 О ДЛЯ МОД ОКОВ СИГН 004, о т м что с нальных В асши ей э ожнос ия функци чет модел ров ани оно до ж сигнало нительно хо о еГОСУДАРСТВЕННЫЙ НОМИТЕТ СССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) 1, Авторское свидете ство ССР 1088004, кл. С 06 Г 15/ , 1983(54)(57) УСТРОЙСТВ ЕЛИРОВАНИЯ МАРКОВС 1 С 1 Х ПОТ АПОВ,по авт. св. У 1088л ичающеесяте целью содержит второи блок памяти, бкодирования и блок управлениямятью, блок кодирования содержипервую и вторую группы формиролей импульсов, два элемента ШЬ шифратор, выходы формирователеи импульсов первой группы соединены с входами первого элемента й 1 И соответственно, выходы формирователей импульсов второй группы подключены к соответствующим входам второго элемента И 11 И и шифратора, блок управления памятью содержит параллельный регистр, дешифратор, две группы элементов И и две группы элементов ИЛИ, группа выходов параллельного регистра соединена с соответствующими входами элементов ИЛИ первой группы и первыми входами соответствующих элементов И первой группы, выходы которых подключены к входам соответствующих элементов ИЛИ второй группы, выходы которых соединены с соответствующими входами дешифра,ЯО 113747 тора, выход первого элемента ИЛИ пер. вой группы соединен с первыми инверсными входами элементов И второй груп. пы, первым входом группы управляющих входов параллельного регистра и вторыми входами соответствующих элементов И первой группы, выход К -го элемента ИЛИ первой группы (К =2, М) соединен с прямым входом К -го элемента И второй группы и К -ми инверсными входами элементов И второй груп. пы с номерами большуми К, выходы элементов И второй группы подключены к соответствующему управляющему входу группы параллельного регистра и вторым входам соответствующих элементов И первой группы, .выходы первого и второго блоков сравнения устройства соединены соответственно с первым и вторым управля 1 ощими входами второго блока памяти, группа информационных входов которого под- Яключена соответственно к группе выходов первого блока памяти, а группа адресных входов второго блока па- фф мяти соединена соответственно с овы- М ходами дешифратора блока управле ния памятью, группа выходов второго фв блока памяти является второй группой выходов устройства и подключена соответственно к входам соответствующих формирователей импульсов первой и второй групп блока кодирования, выходы первого и второго элементов ИЛИ которого соединены соответственно фЬ с первым и вторым управляющими входами параллельного регистра блока управленйя памятью, а группа информационных входов параллельного регистра блока управления памятью подключена соответственно к выходам шифратора блока кодирования, 11374771137477 чар ное делам Москв Филиал ППП "Патент", г.ужгород, ул. Проектная, 4 едактор М.Циткинааказ 10526/37ВНИИПИ Го оставитель В.фукаловехред Т.фанта, Корректо Тираж 710 Под арственного комитета СССР зобретений и открытий Ж, Раушская наб д.1 11374Устройство относится к вычислительной технике и может быть использовано для моделирования систем, описываемых аппаратом теории массового обслуживания, например вычислительных систем, систем передачи данных, элементов производственных процессов, торговых предприятий и т.д.По основному авт. св, В 1088004 известно устройство для моделирования марковских потоков сигналов, содержащее генератор случайного кода,генератор тактовых импульсов, блок элементов И,блок элементов ИЛИ, блок памяти и блок задания закона распределения, состоящий из Ъ идентичных узлов, каждый из которых содержит группу регистров, группу сумматоров, первую и вторую группу элементов И, группу схем сравнения, разрядные входы регистров всех узлов блока задания закона распределения являются соответствующими установочными входами устройства, а в каждом узле первого регистра группы соединены с первыми входами соответствующих элементов И первой группы, выходы 1 -го регистра группы (К =2,и) соединены соответственно с входами первой группы К - 1-го30 сумматора группы, вторая группа входов первого сумматора группы соединена соответственно с выходами первого регистра группы, вторая группа входов М - го сумматора группы ( М = ь-) соединена соответственно с выходами З 5 (М) -го сумматора группы, выходы всех сумматоров группы подключены к первым входам соответствующих элементов И первой группы, выходы которых соединены с входами первой 40 группы соответствующих схем сравнения группы, выход К -й схемы сравнения группы соединен с прямым входом (К -11 -го элемента И второй группы, выход-й схемы сравнения группы 45 , =1,ь) подключен к р -м инверсным входам элементов И второй группы с номером большим , выход первой схемы сравнения группы и выходы элементов И второй группы являются соответст вующими выходами узла блока задания закона распределения, одноименные выходы узлов блока задания закона распределения подключены к соответствующим входам одноименного эле мента ИЛИ блока элементов ИЛИ, выходы которых подключены соответственно к первым входам элементов И 77 2блока элементов И, вторые входы которых объединены и подключены к выходу генератора тактовых импульсов и входу запуска генератора случайного кода, выходы элементов И блока элементов И соединены с соответствующими входами первого блока памяти, выходы которого подключены к вторым объединенным входам элементов И первой группы соответствующего узла блока задания закона распределения, входы второй группы схем сравнения которого подключены соответственно к выходам генератора случайного кодарегистр, первый и второй блоки сравнения и три элемента задержки, входы которых подключены к выходу генератора тактовых импульсов, выходы блока памяти, являющиеся первой группой выходов устройства, соединены соответственно с разрядными входами регистра, с входами первой группы первого и второго блоков сравнения, вторые группы входов которых подключены соответственно к разрядным выходам регистра, выходы первой и второй схев сравнения являются соответственно первым и вторым выходами устройства, выходы первого и второго элементов задержки подключены соответственно к входу разрешения записи и входу сброса регистра, а выход третьего элемента задержки соединен с входами разрешения сравнения первой и второй схем сравнения 111 .Известное устройство моделирует марковский процесс, который описывает системы массового обслуживания. Если задавать интервалы времени достаточно малые, за которые исследовать (моделировать) изменение состоя ний системы массового обслуживания, то легко представить вероятностный автомат, на базе которого построено известное устройство, как модель системы массового обслуживания, Однако известное устройство не позволяет в процессе моделирования системы массового осблуживания определить1 время задержки требований, поступающих на обслуживание, т.е. не исследуется один из важнейших показателей. Этим определяется недостаток известного устройства, органичиваю" щий его функциоиапьные воэможности. Цель изобретения - расширение функциональных возможностей.25 3 11374Цель достигается тем, что в устройство введены второй блок памяти, блок кодирования и блок управления памятью, блок кодирования содержит первую и вторую группы формировате 5 лей импульсов, два элемента ИЛИ и шифратор, выходы формирователейимпульсов первой группы соединены .с входами первого элемента ИЛИ соответственно, выходы формирователей импульсов второй группы подключены к соответствующим входам второго эле. мента ИЛИ и шифратора, блок управления памятью содержит параллельный Регистр, дешифратор, две Группы эле ментов И и две группы элементов ИЛИ, группа выходов параллельного регистра соедин.на с соответствующими входами элементов ИЛИ первой группы и первыми входами соответствующих20 элементов И первой группы, выходы которых подключены к входам соответствующих элементов ИЛИ второй группы, выходы которых соединены с соответствующими входами дешифратора, выход первого элемента ИЛИ первой группы соединен с первыми инверсными входами элементов И второй группы, первым входом группы управляющих входов параллельного регистра и вто 30 рыми входами соответствующих элементов И первой группы, выход К -го элемента первой группы (М =2,М) соединен с прямым входом 1 -го элементаИ второй группы и 1 -ми инверсными входами элементов 1 второй группы с но- З 5 мерами большими Ц, выходы элементов И второй группы подключены к соответствующему управляющему входу группы параллельного регистра и вторым входам соответствующих элементов И пер вой группы, выходы первого и второго блоков сравнения устройства соединены соотвественно с первым и вторым управляющими входами второго блока памяти, группа информационных вхо дов которого подключена соответственно к группе выходов первого блока памяти, а группа адресных входов второго блока памяти соединена соответственно с выходами дешифратора 50 блока управления памятью, группа выходов второго блока памяти является второй группой выходов устройства и подключена соответственно к входам соответствующих формирователей им 1 пульсоз первой и второй групп блока кодирования, выходы первого и второ-. го элементов ИЛИ которого соединены 77 1соответственно с первым и вторым управляющими входами параллельного регистра блока управления памятью, а группа информационных входов параллельного регистра блока управления памятью подключена соответственно к выходам шифратора блока коди- рования.На фиг.1 приведена блок-схема устройства, на фиг,2 - функциональная схема блока задания законов распределений; на фиг.З - функциональная схема блока кодирования, на фиг.4 - функциональная схема блока управления памятью на фиг.5 - временные диаграммы, характеризующие работу устройства.Устройство для моделирования сис" тем массового обслуживания (фиг.) содержит установочные входы 1, блок 2 задания законов распределения, блок 3 генерации случайного кода, генератор 4 тактовой частоты, первый 5, второй 6 и третий 7 элементы задержки, блок 8 элементов И, блок 9 элементов ИЛИ, регистр 1 О, первый блок 11 сравнения, второй блок 12 сравнения, первый блок 13 памяти, первую группу выходов 14 устройства, второй блок 15 памяти, первый 16 и второй 7 выходы устройства, вторую группу выходов 18 устройства, блок 19 кодирования, блок 20 управления памятью.Функциональная схема блока 2 задания закона распределения (фиг.21 содержит первые входы 1, группу регистров 21, входы 22, группу схем сравнения 23, первую группу элементов И 24, группу сумматоров 25, выходы 26, вторую группу элементов И 27.Блок 19 кодирования (фиг,З) содержит первую группу формирователей 28 импульсов, вторую группу формирователей 29 импульсов, второй элемент ИЛИ 30, шифратор 31, первый выход 32, второй выход 33, первый элемент ИЛИ 34, группу выходов 35.Блок 20 управления памятью (фиг.4) содержит параллельный регистр 36, первую группу элементов ИЛИ 37, первую группу элементов И 38, вторую группу элементов И 39, дешифратор 40, вторую группу элементов ИЛИ 41.На временных диаграммах (фиг.5) обозначено "выход М, " - появление сигнала во времени на.1 -м выходеМ-й позиции на,блок-схеме устройства.Устройство работает следующим образом,По установочным входамв регистры 2 блока 2 задания законараспределения заносятся коды матрицывероятностей перехода системымассового обслуживания. При этомв регистр 21 заносится вероятность ; перехоца системы в-есостояние при условии, что она впредыдущий момент времени находилась в-м состоянии.Устройство моделирует одноканальную систему массового обслуживания с ожиданием, причем вводится ограничение на максимально допустимую длину очереди,Наличие сигнала на первом выходе 141 говорит о том, что в системе нет требований и прибор обслужиУвания свободен. Наличие сигналана выходе 14, (1:2,й) говорит о том,что в системе находится-1 требование и одно обслуживается. Самасистема массового обслуживания какмарковская в этом случае находитсяв-м состоянии. Информация о последовательности входного и выходного потоков требований снимаетсясоответственно с выходов 16 и 17.С выходов 18 снимаются потенциалы,длины которых (во времени) несутинформацию о величинах отрезков времени заДержки требований в системемассового обслуживания.Генератор 4 тактовой частотызадает интервалы времени, равныепериоду следования его импульсов,Рассмотрим поблочно работу устройства.Начальное состояние устройствапредусматривает наличие сигналана выходе 141, т,е, в системе массового обслуживания нет требований,По установочным входам 1 в регистрыл,21 блока 2 занесены кодыматрицы Р. С приходом импульса генератора 4, который подается на входы первого 5, второго 6 и третьего 7 элементов задержки времени,на вход блока 8 элементов И и входблока 3 генерации случайного кода,в блоке 3 вырабатывается код числа,равномерно распределенного в интервале от нуля до единицы.Так как на выходе 14 имеется потек.циал, то по входу 14 блока 2 подается потенциал, элементы И 24открыты и коды регистра 211, а также сумматоров 25 подаются на вторые входы схем сравнения 23.Если в регистрах 211 -21 о храп л л нятся коды Оо ф оо( э оо ю оЗ ъф юона, то на входах регистра 21 и сумматоров 25 формируются коды/л л л -л +гоооо ко Роо оо "02 7оо о(оо0 Предположим, что блок 3 сгенери"ровал случайный код 1, численнаявеличина которого меньше величинылкода 10 о, Данный код подается навходы 22 блока 2 и на входы схемсравнения 23 а так как код Д меньшелпо величине 1 оо, то на выходах схемсравнения 23 имеются потенциалы, причем потенциал с выхода схемы сравнения 23 ц закрывает элементы И 27 -27И -.и сигнал присутствует только навыходе 2611 блока 2.Данный сигнал поступает черезблок элементов ИЛИ 9 и блок элементов И 8, при этом с выхода 41вновь снимается потенциал, т,е.эа время 4 Ф в систему массового обслуживания заявки не поступили. По заднему фронту сигнала генератора 4через первый элемент задержки времени 5 в регистр 1 О записывается новое состояние выходов 14. Перед этимпо переднему фронту импульса генератора 4 с незначительной задержкой,формируемой третьим элементом задерж.ки времени 7, в блоках сравнения 135 и 12 происходит сравнение чисел регистра 1 О и нового состояния выходов 14 в позиционном коде, Так какизменений не произошло, то на выходах первого 11 и второго 12 блоков40сравнения потенциалов нет. Поскольку потенциалы отсутствуют на входахвторого блока памяти 15, на выходах18 сигналов тоже нет.Предположим, за второй интервал45в систему массового обслуживания пос"тупило требование, как показано нафиг,5, Расмотрим, как это моделируется в системе,В первом такте на выходе 14 присутствует потенциал. С приходом второго импульса от генератора 4 блок 3генерации случайного кода генерирует код, величина которого меньшечислао но больше числа оо .В этом случае срабатывают схемы сравнения 23 +23 . Сигнал с выходасхемы сравнения 231 закрывает элементы И 27 о -27 и на выходе 26 д137477 8 7 1блока 2 будет потенциал, которойпроходит через блок 9 элементов ИЛИ,блок 8 элементов И на вход блока па-мяти 13, на выходе 14 устройствапоявляется потенциал,Так моделируется случай приходав систему требования за интервал 6и принятия его на обслуживание, Наличие сигнала на выходе 14 1 свидетельствует о занятости обслуживанием в системе канала требованияи отсутствии очереди в системе.С появлением импульса на выходетретьего элемента 7 задержки времени на третий вход блоков сравнения11 и 12 подается поетнциал. Так какна выходах регистра 10 снимаетсякод 1000, подаваемый на входы бло.ка 11, а на входы 14 подан код,0100,который меньше кода 1000.л,то на выходе. присутствует потенциал,который подается на выход 16 устройства для моделирования, Появлениепотенциала на выходе 16 свидетельствует о приходе в систему требованияоб отсчете времени, задаваемый генератором 4, и о занятии обслуживанием канала. Так как на входы второго блока памяти 15 не подаются завторой отсчет Д потенциалы, то блоккодирования 19 не срабатывает. Действительно, требование, поступившеев свободную систему, немедленно принимается к обслуживанию и задержкане происходит, Поэтому блоки 15, 19,20 не работают.Пусть эа четвертый такт на вход устройства поступит следующее требование, как показано на фиг.5. Предыдущее требование еще не обслуживалосьв системе возникает очередь, котораяхарактеризуется числом требованийв очереди и временем задержки каждого требования в очереди.Рассмотрим, как устройство длямоделирования позволяет получитьэту информацию.С приходом очередного требованияна выходе 14 появляется потенциал( заметим, что:подобная ситуацияв модели соответствует генерации начетвертом такте случайного кода генератором 4, величина которого больл л л лше и 11+ 011, но меньше и, + цн+ ь,т.е, в блоке 2 единичный потенциалприсутствует на выходах схем сравнения 23 д -23 11 и имеется потенциална выходе 26 блока 2, который проходит через блоки 9 и 8 на вход пер 5 10 15 20 25 30 35 40 45 ного блока памяти. Тем самым устанав-. ливается потенциал на первом выходе 14 устройства и исчезает потенциал на выходе 14 2 устройства.Аналогичным образом срабатывает первый блок сравнения 11 и на выходе 16 устройства появляется потенциал, что соответствует моделированию поступления в систему массового обслуживания очередного (второго) требования.Так как второе требование задержано, то вступают в работу блоки 15, 9 и 20, определяющие время задержки требований. Функционируют они следующим образом. Во втором блоке памяти Фиксируется наличие требования, стоящего в очереди, Потенциал с первого входа 14 при появлении импульса на входе 16 проходит на выход 18 блока 15, причем длительность этого потенциала равна времени нахождения требования в очередиВ блоке 19.кодирования ставшему в очередь требованию присваивается код номера. Происходит это следующим образом, Потенциал с выхода 18 блока 15 подается на вход формирователя сигналов 29, который выделяет его передний фронт, и на вход формирователя сигналов 281, который выделяет его задний фронт. С выхода формирувателя 29 сигнал поступает на вход первого элемента ИЛИ 30 и на вход шифратора 3 . С выходы первого формирователя сигналов 28 сигнал поступает на вход второго элемента ИЛИ 34. Таким образом, на выходах блока кодирования формируются следующие сигналы; на выходе 32 Формируется синхроимпульс при поступлении на входы 18 каждо- го нового сигнала, на выходах 35 формируется код номера очередного требования в очереди, на выходе 33 формируется сигнал сброса регистров сдвига, причем потенциал на выходе 33 будет только в том случае, когда одному из потенциалов на входах 18 будет присвоено значение "ноль". В блоке 20 управления памятью(Фиг.4) код номера требования в оче реди поступает на первые входы 35 и по синхросигналу от второго входа 32 записывается в параллельный регистр 36, Сигналы с выходов параллельного регистра 36 поступают наэлементы ИЛИ 37 иэлементы И 38, причем в этом случае имеется потенциал на выходе элементаИЛИ 37 и на выходах элементов И 389 11присутствует код номера требования,стоящего в очереди. Данный код поступает через элементы ИЛИ 41 на входдешифратора 40 и на его выходе будет потенциал.За пятый интервал Й в системупоступает еще одно, третье требование, которое также становится в очередь, причем оно будет вторым в очереди, а обслуживание самого первого требования еще не окончено. В ус-тройстве для моделирования это эквивалентно генерации за пятый интервал 41 блоком 3 кода, величина котоврого больше 1 2 + 1(,2, но меньше и 1+г+ 1 + , . В результате на выходе144 появляется потенциал и исчезаетпотенциал на третьем выходе. Этоопределяет событие наличия в системе трех требований,Первый блок сравнения 11 выдаетна выходе 16 потенциал, что соответствует поступлению требования в систему,Во втором блоке памяти 15 потенциал в первого входа 14 поступитна выход 18 у (фиг.5). Наличие потенциала одновременно на выходах 18 и18 устройства говорит о том, чтов системе два требования в очереди.Потенциал с выхода 182 блока 153.,йоступае т на вход8 2 блока 1 9 ,на первых выходах которого сформируе тся код номера второго тр е бов ания в очереди и н а втором выходеблока имеется синхр оимпуль с .В блоке 2 0 с приходом синхроимпульса по входу 3 2 кода по входам3 5 в параллельном регистре 3 6 кодпервого требования в очереди передвигается в следующий регистр , а впервый регистр записывается код номера второго требования в очереди .Потенциал имеется на выходе элемент а И 3 9 , который разрешает прохождение кода номера первого в очередитребования через элементы И 38 , элементы ИЛИ 4 1 и дешифратор 4 0 и напервом выходе по-прежнему есть потенциал .На шестом такте в систему поступает о чередное , четвертое тр е бов ание , а первое еще обслуживается .Потенциал появляется навыходе4устройства . С выхода 1 6 снимаетсяпотенциал , на выходе 1 8также естьпотенциал . В блоке кодирования 1 9формируется на выходах 35 код номератретьего сообщения в очереди . По син 37477 10 О 20 25 ЗО 35 40 45 50 55 Так как на входе второго блока па. мяти 15 есть разрешающий потенциал и есть потенциал от блока 20, то на выходе 8 исчезает потенциал. Это говорит а том, что время ожидания первого в очереди требования окончено и оно принято к обслуживанию. Длительность потенциала на выходе 18 соответствует его времени ожидания в очереди.По заднему фронту потенциала от входа 18 в блоке 9 срабатывает пер. вый формирователь 29 и на выходе 33 элемента ИЛИ 34 (блока 9) имеется импульс, который поступает на вход блока 20.В блоке 20 в параллельном регистре 36 обнулен регистр с номером и".2, так как на его управляющем входе есть потенциал от элемента 39. хроимпульсу с входа 32 в блоке 20 управления памятью в параллельном ре-гистре 36 происходит перезапись содержимого регистров. Потенциал имеется на выходе элемента И 39, и кодпервого требования в очереди снимает.ся с выходов элементов И 38, На первом выходе по-прежнему есть потенци,ал еНа седьмом такте изменений в схеме не происходит,т.е. код блока 3по величине большекода , ногг л1меньше кода 1 + .и потенциал сох-.раняется на выходе 14 устройства длямоделирования,На восьмом такте (фиг.5) заканчивается обслуживание требования,поступившего в систему первым. Этосоответствует генерации блоком 3случайного кода, величина котороголменьше кода , т.е. в этом случаена выходе схемы сравнения 23 4 естьпотенциал, имеется потенциал йа выходе 26блока 2. Данный потенциалпроходит .через блоки 9 и 8, блокпамяти 13, На выходе 14 присутствует единичный потенциал, и исчезаетпотенциал на выходе 14 устройства.В этом случае работает второй блоксравнения 12, так как код 0000100меньше кода 0001000. На его выходе 17 есть потенциал, что говорито том, что требование покинуло систему. Содержимое регистра 10 сбрасывается от сигнала второго элементазадержки 6 после сравнения кодовблоками 11 или 12, как это показанона фиг.5.11 1Теперь первым в очереди будет требование, код номера которого равен 39 л) .Как показано на фиг,5, на девятом такте в систему поступает очередное требование. Обслуживание на этом такте второго требования не оканчивается. Сигнал присутствует на выходе 14. Импульс появляется йа выходе 16, и на выходе 18 есть потенциал. В блоке кодирования 19 вновь поступившему требованию присваивается код номера, который записывается в параплельный регистр 36 блока 20. Таким образом, в процессе моделирования системы массового обслуживания имеется следующая информация: 37477 12модель входного потока сообщений,по анализу потока импульсов на вы"ходе 1 бфмодель выходного потока сообщений,:по анализу потока импульсовна выходе 17 фмодель занятости системы обслуживания (период занятости) требований, по анапизу потенциапов на первых выходах 14 ф,модель задержки в системе обслуживания требований в очереди время задержки), по анализу потенциаловна выходах 8.1 5Технико-экономическая эффектив"ность объекта по отношению к известному заключается в определении характеристик времени задержки требований очереди на обслуживание, 1137477