Устройство для моделирования марковских потоков сигналов Советский патент 1985 года по МПК G06N7/08 G06F7/58 

Устройство относится к вычислительной технике и может быть исполь зовано для моделирования систем, описываемых аппаратом теории массового обслуживания, например вычислительных систем, систем передачи данных, элементов производственных процессов, торговых предприятий и т.д. По основному авт. св. № 1088004 известно устройство для моделирования марковских потоков сигналов, содержащее генератор случайного кода, генератор тактовых импульсов,блок элементов И,блок элементов ИЛИ, блок памяти и блок задания закона распре деления, состоящий из п. идентичных узлов, каждый из которых содержит группу регистров, группу сумматоров первую и вторую группу элементов И, группу схем сравнения, разрядные .входы регистров всех узлов блока за дания закона распределения являются соответствующими установоч шми входа устройства,а в каждом узле первого регистра группы соединены с первыми входами соответствующих элементов И первой группы, выходы h-го регистра группы fК 2,п) соединены соответственно с входами первой группы (К -1)сумматора группы, вторая группа вхо дов первого сумматора группы соединена соответственно с выходами первого регистра группы, вторая группа входов М-го сумматора группы ( М 2гь1 соединена соответственно с выходами (М-1)-го сумматора группы, выходы всех сумматоров группы подключены к первым входам соответствующих элементов И первой группы, выходы которых соединены с входами первой группы соответствующих схем сравнения группы, выход }(-и схемы сравнен группы соединен с прямым входом ( элемента И второй группы, выход о-и схемы сравнения группы .(р 1,п) подключен к р-м инверсным входш- элементов И второй группы с номером большим р, выход первой схемы сравнения группы и выходы элементов И второй группы являются соответствующими выходами узла блока задания закона распределения, одноименные выходы узлов блока задания закона распределения подключены к соответствующим входам одноименного элемента ИЛИ блока элементов ИЛИ, выходы которых подключены соответственно к первым входам элементов И блока элементов И, вторые входы которых объединены и подключены к выходу генератора тактовых импульсов и входу запуска генератора случайного кода, выходы элементов И блока элементов И соединены с соответствующими входами первого блока памяти, выходы которого подключены к вторым объединенным входам элементов И первой группы соответствующего узла .блока задания закона распределения, входы второй группы схем сравнения которого подключены соответственно к выходам генератора случайного кода, .регистр, первый и второй блоки сравнения и три элемента задержки, входы которых подключены к выходу генератора тактовых импульсов, выходы блока памяти, являющиеся первой группой выходов устройства, соединены соответственно с разрядными входами регистра, с входами первой группы первого и второго блоков сравнения, вторые группы входов которых подключены соответственно к разрядным выходам регистра, выходы первой и второй схен сравнения являются соответственно первым и вторым выходами устройства, выходы первого и второго элементов задержки подключены соответственно к входу разрешения записи и входу сброса регистра, а выход третьего элемента задержки соединен с входами разрещения сравнения первой и второй схем сравнения 1J . Известное устройство моделирует марковский процесс, который описывает системы массового обслуживания. Если задавать интервалы времени достаточно малые, за которые исследовать (моделировать изменение состояний системы массового обслуживания, то легко представить вероятностный автомат, на базе которого построено известное устройство, как модель системы массового обслуживания. Однако известное устройство не позволяет в процессе моделирования системы массового осблуживания определить время задержки требований, поступающих на обслуживание, т.е. не исследуется один из важнейших показателей. Этим определяется недостаток известного ycтpoйctвa, органичивающий его функциональные возможности. Цель изобретения - расширение функциональных возможностей. Цель достигается тем, что в устройство введены второй блок памяти, блок кодирования и блок управления памятью, блок кодирования содержит первую и вторую группы формирователей импульсов, два элемента ИЛИ и шифратор, выходы формирователей импульсов первой группы соединены с входами первого элемента ИЛИ соответственно, выходы формирователей импульсов второй группы подключены к соответствующим входам второго эле мента ИЛИ и шифратора, блок управления памятью содержит параллельный регистр, дешифратор, две группы элементов И и две группы элементов ИЛИ группа выходов параллельного регистра соединена с соответствующими входами элементов ИЛИ первой группы и первыми входами соответствующих элементов И первой группы, выходы которых подключены к входам соответствующих элементов ИЛИ второй группы, выходы которых соединены с соответствующими входами дешифратора, выход первого элемента ИЛИ первой группы соединен с первыми инверсными входами элементов И второй группы, первым входом группы управляющих входов параллельного регистра и вторыми входами соответствующих элементов И первой группы, выход К-го элемента первой группы (к 2,М) соединен с прямым входом К-го элемента второй группы и К-ми инверсными входами элементов И второй группы с номерами большими К , выходы элементов И второй группы подключены к соответ ствующему управляющему входу группы параллельного регистра и вторым входам соответствующих элементов И первой группы, выходы первого и второго блоков сравнения устройства соединены соотвественно с первым и вторым управляющими входами второго блока памяти, группа информационных входов которого подключена соответственно к группе выходов первого блока памяти, а группа адресных входов второго блока памяти соединена соответственно с выходами дешифратора блока управления памятью, группа выходов второго блока памяти является второй группой выходов устройства и подключена соответственно к входам соответствующих формирователей импульсов первой и второй групп блока кодирования, выходы первого и второго элементов ИЛИ которого соединены. соответственно с первым и вторым управляюш;ими входами параллельного регистра блока управления памятью, а группа информационных входов параллельного регистра блока управления памятью подключена соответственно к выходам шифратора блока кодирования. На фиг,1 приведена блок-схема устройства; на фиг.2 - функциональная схема блока задания законов распределений; на фиг.З - функциональная схема блока кодирования/ на фиг,4 - функциональная схема блока управления памятью} на фиг.З - временные диаграммы, характеризующие работу устройства. Устройство для моделирования систем массового обслуживания (фиг.) содержит установочные входы 1, блок 2 задания законов распределения, блок 3 генерации случайного кода, генератор 4 тактовой частоты, первый 5, второй 6 и третий 7 элементы задержки, блок 8 элементов И, блок 9 элементов ШМ, регистр 10, первый блок 11 сравнения, второй блок 12 сравнения, первый блок 13 памяти, первую группу выходов 14 устройства, второй блок 15 памяти, первый 16 и второй 17 выходы устройства, вторую группу выходов 18 устройства, блок 19 кодирования, блок 20 управления памятью. Функциональная схема блока 2 за- Дания закона распределения (фиг.2) содержит первые входы 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) обозначено выход N, - появление сигнала во времени Ha.i-м выходе N-й позиции на/блок-схёме устройства. S Устройство работает следующим о разом. По установочным входам I в регистры 21 блока 2 задания закона распределения заносятся коды матри цы р вероятностей перехода системы массового обслуживания. При этом в регистр 21,) заносится вероятность . перехода системы в j -е состояние при условии, что она в предыдущий момент времени находилась в i -м состоянии. Устройство моделирует одноканальную систему массового обслуживания с ожиданием, причем вводится ограничение на максимально допустимую длину очереди. Наличие сигнала на первом выходе 14| говорит о том, что в системе нет требований и прибор обслужи вания свободен. Наличие сигнала на выходе 14| ( 2,п говорит о то что в системе находится 1-1 требование и одно обслуживается. Сама система массового обслуживания как марковская в этом случае находится в i-м состоянии. Информация о.последовательности входного и выходного потоков требований снимается соответственно с выходов 16 и 17. С выходов 18 снимаются потенциалы, длины которых (во времени) несут информацию о величинах отрезков вр мени зa epжки требований в системе массового обслуживания. Генератор 4 тактовой частоты задает интервалы времени, равные периоду следования его импульсов. Рассмотрим поблочно работу устройства. Начальное состояние устройства предусматривает наличие сигнала на выходе 14, т.е. в системе массового обслуживания нет требований По установочным входам 1 в регистр 21 блока 2 занесены коды и матрицы Р. С приходом импульса генератора 4, который подается на входы первого 5, второго 6 и третьего 7 элементов задержки времени, на вход блока 8 элементов И и вход блока 3 генерации случайного кода, в блоке 3 вырабатывается код числа равномерно распределенного в интер вале от нуля до единицы. Так как на вькоде 14j имеется пот циал, то по входу 14, блока 2 подается потенциал, элементы И 24 открыты и коды регистра 2Ц , а та 776, же сумматоров 25 подаются на вторые; входы схем сравнения 23. Если в регистрах 2 I п хра НЯТСЯ коды 1Грд , HO, , Н 0 , Ио . . , ог) ° входах регистра 21 и сумматоров 25 формируются коды ( Предположим, что блок 3 сгенерировал случайный код А , численная величина которого меньше величины кода lIpQ . Данный код подается на входы 22 блока 2 и на входы схем сравнения .23-, а так как код А меньше по величине TIQQ, то на выходах схем сравнения 23 имеются потенциалы, причем потенциал с выхода схемы сравнения 23,( закрывает элементы И 27 -27. .. и сигнал присутствует только на выходе 26 блока 2. Данный сигнал поступает через блок элементов ИЛИ 9 и блок элементов И 8, при этом с выхода 14 вновь снимается потенциал, т.е. за время .AT в систему массового обслуживания заявки не поступили. По заднему фронту сигнала генератора 4 через первый элемент задержки времени 5 в регистр 10 записывается новое состояние выходов 14. Перед этим по переднему фронту импульса генератора 4 с незначительной задержкой, формируемой третьим элементом задержки времени 7, в блоках сравнения 11 и I2 происходит сравнение чисел регистра 10 и нового состояния выходов 14 в позиционном коде. Так как изменений не произошло, то на выходах первого 11 и второго 12 блоков сравнения потенциалов нет. Поскольку потенциалы отсутствуют на входах второго блока памяти 15, на выходах 18 сигналов тоже нет. Предположим, за второй интервал В систему массового обслуживания поступило требование, как показано на фиг.5. Расмотрим, как это моделируется в системе. В первом такте на выходе 14 присутствует потенциал. С приходом второго импульса от генератора 4 блок 3 генерации случайного кода генерирует код, величина которого меньше числа Q ° больше числа ТГ , В этом случае срабатывают схемы сравнения 23ц2+23., . Сигнал с выхода схемы сравнения 23 закрывает элементы И выхоДё 2645 блока 2 будет потенциал, которой проходит через блок 9 элементов ШЖ блок 8 элементов И на вход блока па мяти 13, на выходе 14 устройства появляется потенциал. Так моделируется случай прихода в систему требования за интервал ut и принятия его на обслуживание. Наличие сигнала на выходе 14 свидетельствует О занятости обслуживанием в системе канала требования и отсутствии очереди в системе. С появлением импульса на выходе третьего элемента 7 задержки времени на третий вход блоков сравнения 11 и 12 подается поетнциал. Так как на выходах регистра 10 снимается код 1000..., подаваемый на входы бл ка 11, а на входы 14 подан код ,0100... ,который меньше кода 1000. .., то на выходе.присутствует потенциал который подается на выход 16 устрой ства для моделирования. Появление потенциала на выходе 16 свидетельст вует о приходе в систему требования об отсчете времени, задаваемый генератором 4, и о занятии обслуживанием канала. Так-как на входы второ го блока памяти 15 не подаются за второй отсчет й.т потенциалы, то бло кодирования 19 не срабатывает. Дейс вительно, требование, поступившее в свободную систему, немедленно при нимается к обслуживанию и задержка не происходит. Поэтому блоки 15, 19 20 не работают. Пусть за четвертый такт на вход тройства поступит следующее требова ние, как показано на фиг.5. Предыдущее требование еще не обслуживало в системе возникает очередь, котора характеризуется числом требований в очереди и временем задержки каждо го требования в очереди. Рассмотрим, как устройство для моделирования позволяет получить эту информацию. С приходом очередного требования на выходе 145 появляется потенциал заметим, что ;подобная1 ситуация в модели соответствует генерации на четвертом такте случайного кода генераторо.м 4, величина которого боль 4o i2 ше II + и но меньше т.е. в блоке 2 единичный потенциал присутствует на выходах схем сравне ния 23 -23-2, и имеется потенциал на выходе 26 блока 2, который прохо дит через блоки 9 и 8 на вход первого блока памяти. Тем самым устанавг линается потенциал на первом выходе 14 устройства и исчезает потенциал на выходе 142 устройства, Аналогичным образом срабатывает первый блок сравнения 11 и на выходе 16 устройства появляется потенциал, что соответствует моделированию поступлени я в систему массового обслуживания очередного второго) требования. Так как второе требование задержано, то BCTynaioT в работу блоки 15, 19 и 20, определяющие время задержки требований. Функционируют они следующим образом. Во втором блоке памяти фиксируется наличие требования, стоящего в очереди. Потенциал с первого входа 14а при появлении импульса йа входе 16 проходит на выход I8j блока 15, причем длительность этого потенциала равна времени нахождения требования в очереди. В блоке 19 кодирования ставшему в очередь требованию присваивается код номера. Происходит это следующим образом. Потенциал с выхода 18 блока 15 подается на вход формирователя сигналов 29 , который вьщеляет его передтшй фронт, и на вход формирователя сигналов 28 , который вьщеляет его задний фронт. С выхода формирователя 29 сигнал поступает на вход первого элемента ИЛИ 30 и на вход шифратора 31. С выходы первого формирователя сигналов 28 сигнал поступает на вход второго элемента ИЛИ 34. Таким образом, на выходах блока кодирования формируются следующие сигналы: на выходе 32 формируется синхроимпульс при поступлении на входы 18 каждого нового сигнала, на выходах 35 формируется код номера очередного требования в очереди, на выходе 33 формируется сигнал сброса регистров сдвига, причем потенциал на выходе 33 будет только в том случае, когда одному из потенциалов на входах 18 будет присвоено значение ноль. В блоке 20 управления памятью (фиг.4 код номера требования в очереди поступает на первые входы 35 и по синхросигналу от второго входа 32 записывается в параллельный регистр 36. Сигналы с выходов параллельного регистра 36 поступают на элементы ИЛИ 37 и элементы И 38, причем в этом случае имеется потенциал на выходе элемент; ИЛИ 37 и на выходах элементов И 38 присутствует код номера требования, стоящего в очереди. Данный код поступает через элементы ИЖ 41 на вхо дешифратора 40 .и на его выходе будет потенциал. За пятый интервал ui в систему поступает еще одно, третье требование, которое также становится в оче редь, причем оно будет вторым в оче реди, а обслуживание самого первого требования еще не окончено, В ус тройстве для моделирования это экви валентно генерации за пятый интервал А блоком 3 кода, величина кото рого больше ° меньше i + . В результате на выходе 144 появляется -потенциал и исчезает потенциал на третьем выходе. Это определяет событие наличия в системе трех требований. Первый блок сравнения 11 выдает на выходе 16 потенциал, что соответ ствует поступлению требования в сис тему, Во втором блоке памяти 15 потенциал в первого входа 14,: поступит на выход IS (фиг,5), Наличие потен циала одновременно на выходах 18 и 18л устройства говорит о том, что в системе два требование в очереди. Потенциал с выхода IBj блока 15 поступает на вход 18 блока 19, на первых выходах которого сформируется код номера второго требования в очереди и на втором выходе блока имеется синхроимпульс, В блоке 20 с приходом синхроимпульса по входу 32 кода по входам 35 в параллельном регистре 36 код первого требования в очереди передвигается в следующий регистр, а в первый регистр записывается код номера второго требования в очереди. Потенциал имеется на выходе элемента И 39, который разрешает прохождение кода номера первого в очереди требования через элементы И 38, эле менты ШШ 41 и дешифратор 40 и на первом выходе по-прежнему есть потенциал. На шестом такте в систему поступает очере;|ное, четвертое требование, а первое еще обслуживается. Потенциал появляется на выходе 14с устройства, С вьгхода 16 снимается потенциал, на выходе 18j также есть потенциал, В блоке кодирования 19 формируется на выходах 35 код номер третьего сообщения в очереди. По си 7 хроимпульсу с входа 32 в блоке 20 управления памятью в параллельном ре- гистре 36 происходит перезапись содержимого регистров. Потенциал имеется на выходе элемента И 39, и-код первого требования в очереди снимается с выходов элементов И 38, На первом выходе по-прежнему есть потенци.ал. На седьмом такте изменений в схеме не происходит,т,е, код блока 3 по величине больше. кода и меньше кода + и и потенциал сохраняется на выходе 14 устройства для моделирования. На восьмом такте (фиг,5 заканчивается обслуживание требования, поступившего в систему первым. Это соответствует генерации блоком 3 случайного кода, величина которого меньше кода т«е, в этом случае на выходе схемы сравнения 23 кл есть потенциал, имеется потенциал на выходе 26 блока 2, Данный потенциал проходит .через блоки 9 и 8, блок памяти 13, На выходе 14j присутст-вует единичный потенциал, и исчезает потенциал на выходе 14 устройства, В этом случае работает второй блок сравнения 12, так как код 000010,,,О меньше кода 000100,,,О, На его выходе 17 есть потенциал, что говорит о том, что требование покинуло систему. Содержимое регистра 10 сбрасывается от сигнала второго элемента 1задержки 6 после сравнения кодов блоками 11 или 12, как это показано на фиг,5, Так как на входе второго блока памяти 15 есть разрешающий потенциал и есть потенциал от блока 20, то на выходе 18/ исчезает потенциал. Это говорит о том, что время -ожидания первого в очереди требования окончено и оно принято к обслуживанию. Длительность потенциала на выходе 18 соответствует его времени ожидания в очереди. По заднему фронту потенциала от входа 18 в блоке 19 срабатываетпервый формирователь 29 и на выходе 33 элемента ИЛИ 34 (блока 19) имеется импульс, который поступает на вход блока 20, В блоке 20 в параллельном регистре 36 обнулен регистр с номером пт-2, так как на его управляющем входе есть потенциал от элемента 39,

J

Теперь первым в очереди будет требование, код номера которого равен 39(т-1.

Как показано на фиг,5, на девятом такте в систему поступает очередное требование. Обслуживание на этом такте второго требования не оканчивается. Сигнал присутствует на выходе 14, Импульс появляется Да выходе 16, и на выходе 18 есть потенциал, В блоке кодирования 19 вновь поступившему требованию присваивается код номера, который записывается в параллельный регистр 36 блока 20,

Таким образом, в процессе моделирования системы массового обслуживания имеется следукяцая информация:

747712 ..

модель входного потока сообщений, по анализу потока импульсов на выходе 16 J

модель выходного потока сообщее НИИ, по анализу потока импульсов на выходе 17J

модель занятости системы обслуживания (период занятости) требований, по анализу потенциалов иа перfO вых выхйдах 14,

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

Технико-экономическая эффективность объекта по отношению к известному заключается в определении характеристик времени задержки требований очередина обслуживание.

г /2 ,

т и /7/7

т п inn

.ш.у Jr X

;;

42

/Д

is

2 3

ij

i,

, Д

Л J in

иг.2

g

Ш

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ МАРКОВСКИХ ПОТОКОВ СИГНАЛОВ ,по авт. св. № 1088004, отличающееся тем, что, с целью расширения функциональных возможностей за счет-моделирования задержки входных сигналов, оно дополнительно содержит второй блок памяти, блок кодирования и блок управления памятью, блок кодирования содержит первую и вторую группы формирователей импульсов, два элемента ИЛИ и шифратор, выходы формирователей им- пульсов первой группы соединены с входами первого элемента ИЛИ соответственно, выходы формирователей импульсов второй группы подключены к соответствующим входам второго элемента ШШ и шифратора, блок управления памятью содержит параллельный регистр, дешифратор, две группы элементов И и две группы элементов ИЛИ, группа выходов параллельного регистра соединена с соответствующими входами элементов ИЛИ первой i pynпы и первыми входами соответствующих элементов И первой группы, выходы которых подключены к входам соотвetcтвyющиx элементов ИЛИ второй группы, выходы которых соединены с соответствующими вводами дешифратора, выход первог.о элемента ШЕИ первой группы соединен с первыми инверсными входами элементов И второй группы, первым входом группы управляющих входов параллельного регистра и вторыми входами соответствующих элементов И первой группы, выход К-го элемента ШШ первой группы (К 2, М) соединен с прямым входом k-го элемента И второй группы и Y-МП инверсными входами элементов И второй группы с номерами большими К, выходы элементов И второй группы подключены к соответствующему управляющему входу группы параллельного регистра и вторым входам соответствующих i элементов И первой группы, .выходы первого и второго блоков сравнения СЛ устройства соединены соответственно с первым и вторым управляющими входами второго блока памяти, группа информационных входов которого подключена соответственно к группе выходов первого блока памяти, а группа адресных входов второго блока пасо | мяти соединена, соответственно-с (выходами дешифратора: блока управле-4 ч ния памятью, группа выходов второго блока памяти является второй группой выходов устройства и 1 одключена соответственно к входам соответствующих формирователей импульсов первой и второй групп блока кодирования, выходы первого и второго элементов ИЛИ которого соединены соответственно с первым и вторым управляющими вхо- дами параллельного perHcfpa блока управлен11я памятью, а группа информационных входов параллельного регистра блока управления памятью подключена соответственно к выходам шифратора блока кодирования.

35i

0

35p

J3

/a.J

35 j 352 P i l

1i

TT

J- I // I

ui.ff