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

делирования входных и выходных потоков системах массового обслуживания,. оно дополнительно содержит регистр, пержнй и второй блоки сравнения и трн элемента задержки, входы которых помитчеяы к выходу геиератора тактоых 1тпульсов, выходы блока памяти, «MXMQiec группой выходов устройства сол влчлпи соответственно с разрядными меодмм регистра, с входами первой груяаы первого и второго (блоков сравнения, вторые группы входов которых подключены соответственно к разрядным выходам регистра, выходы первой и второй схем сравнения являются соответст венно первым и вторым шлходамн ycтpoйct ва,выходы первого и второго элементов задержки подключены соответственно к входу разрешения записи и входу сброса регистра,а шход третьего элемента задержки соединен с входами разрешения сравнения первой и второй схем сравнения

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ МАРКОВСКИХ ПОТОКОВ СИГНАЛОВ, содержащее генератор случайного кода, генератор тактовых импульсов, блок элементов ИЛИ, блок элементов И, блок памяти и блок задания закона распределения, состоящий из п идентичных узлов; каждый из которых содержит группу регистров, группу сумматоров, первую и вторую группы элементов И, группу схем сравнения, разрядные входы регистров всех узлов блока, задагния закона распределения являются соответствующими установочными входами устройства, а в каждом узле выходы первого -регистра группы соедо1иены с первыми входами соответствующих элементов И первой группы, выходы k-ro регистра группы (, п) сое динены соответственно с входами первой группы (It-l)-ro сумматора группы, вторая группа входов первого сумматора группы соединена соответствен о с выходами первого регистра группы, вторая группа входов М-го сумматора группы (, п-1) Соединена соответifrMbrf.-. ла д ствеино с выходайи (M-l)-ro сумматора группы, выходы всех сумматоров группы подключены к первым входам соответствующих элементов И первой группы, выходы которых соединены с входами первой группы соответствующих схем сравнения группы, выход k-ft схемы сравнения группы соединен с прямым входом (k-l)-ro элемента И второй группы, выход р-й сравнения группы (, п-1) подключен к р-м инверсным входам элементов И второй группы с номером, большим р, выход первой схемы сравнения группы и выходы элементов И второй группы являются соот.ветствующими выходами узла блока (Л задания закона распргеделения, одноименные выхода узлов блока задания закона расйределения подключены к соответствующим входам одноименного ; элемента ИЛИ блока элементов ИЛИ-, tвыходы которых подключены соответственно к первым входам элементови блока элементов И, вторые входы кото00 00 рых объединены и подключены к выходу генератора тактовых импульсов и входу запуска генератора случайного кода, выходы элем1ентов И блока элементов И 4 соединены с соответствукяцими входами блока памяти, выходы которого подклю-. чены к вторым объединенным входам элементов И первой группы сортветству- ющего узла блока задания закона распределения, входы второй группы схем сравнения которого подключены соответственно к выходам генератора случайного кода, отличающее с я тем, что, с целью расширения функциональных возможностей путем мо

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

Известио устройство для моделирования систем массового обслуживания, содержащее первый и второй геиераторы случайного потока импульсов, элемент ЗАЭТЕТ, реверсивный счетчик, ьшогоканаяьиый блок случайных временных задержек, первый и второй элементы ИЛИ, бпок сравнения, элемент И, пер вый, второй н третий счетчики,блок элементов И,ге- нератор импульсов, причем выход первого генератора случайного потока импульсов соединен с первым счетчиком и через элемент ЗАПРЕТ с многоканальншм блоком случайных временных задержек и суммирующим входом реверсмвного счетчика, выход которого соединец через блок сравнеиия с первым входом первого элемента Ш1И, выход хоторо го соединен с управляющими входами элемента И и элемента ЗАПРЕТ, сигиапьнмй вход элемента И соединен с входом первого счетчика, а выход 3(яеи«нта И соединен с входом второго счетчика, выход второго генератора случайного потока импульсов соединен с вторьм входом первого элемента ИЛИ л первым входом генератора импульсов, мосод которого соедииеи с входом третьего счетчика и через второй элемент ИЛИ с вычитаюорш входом реверсивного счетчика, {разрядные выходы которого соединены через блок элементов И с вторым входом генератора импул.ьсов, а выход многоканального блока случайных задержек соединен с

другим входом второго элемента ИЖ1 СПНедостаток устройства состоит в ограниченных функциональных возможностях, так как устройство моделирует функционирование только систем с потерями.

Известно устройство для моделирования систем массового обслуживания, содержащее первый и второй генераторы случайных потоков импульсов, генератор импульсов, первый и второй сче-Гчикн, первый и второй реверсивнью счетчики, элемент ЗАПРЕТ, элемент задержки, многоканальный блок случайных временных задержек, первый, второй, третий, четвертый и пятый элементы ШШ, первый, второй и третий элементы И, блок элементов И, блок сиихронизации, сумматор, пороговый элемент, формирователь и переключатель, причем выход первого генератора случайного потока импульсов соединен с входом первого счетчика и с первым входом первого элемента ШШ, выход которого соединен с первым входом элемента ЗАПРЕТ, выход которого соединен с суммирую1цим входом первого ревесивного счетчика и с входом многоканального блока случайных временных задержек, выход которого соединен с первым входом второго элемента ИЛИ, выход которого соединен с вычитающим входом первого реверсивного счетчика, выход которого через пороговый элемент соединен с первым входом третьего элемента ИЛИ, второй вход которого подключен к- шлходу генератора случайного потока импульсов и объединен с первым входом генератора импульсов. второй вход которого через первый элемент И соединен с разрядными выходами первого реверсивного счетчи-: ка, а выход генератора импульсов соединен с вторым входом второго элемен та ИЛИ, выход третьего элемента ИЛИ соединен с вторым входом элемента ЗАПРЕТ и с первым входом второго элемента И, второй вход которого объединен с входом первого счетчика, первый и второй выходы блока синхронизации соединены соответственно с управляняци ми входами блока элементов И и сумматора, входы которого соединены с выходами блока элементов И соответственно, входы которого подсоединены . к разрядным выходам второго реверсив ного счетчика и через четвертый элемент ИЛИ соединены, с первым входом третьего элемента И, второй вход которого подключен к первому выходу переключателя, второй выход которого соединен с входом второго реверсивног счетчика, выход третьего элемента И через элемент задержки соединен с вторым входом первого элемента И и непосредственно с вычитающим входом второго реверсивного счетчика, суммирующий вход которого соединен с выходом пятого элемента ИЛИ, входы которого соединены с выходом второго эле мента И и с третьим выходом .переключателя соответственно, входы которог соединены.соответственно с выходом генератора импульсов и с выходом шестого элемента ИЛИ, входы которого соединены соответственно с первым входом второго элемента ИЛИ и через формирователь серии импульсов - с входом генератора импульсов L2J. При моделировании систем для каждого закона распределения входящего потока сообщений необходим собственный генератор случайного потока. В устройстве не фиксируетсял временное распределение выходного потока требований, что сообенно важно для моделирования, например, многофазных систем (в технике систем связи), а также занятость приборов обслуживания (период занятости). Все это огра ничивает функциональные возможности устройства, которое также отличается сложностью реализации.

Наиболее близким к изобретению по 5Sны с первыми входами соответствующих,

совокупности конструктивных и функци-элементов И первой группы, выходы

ональных признаков является устрой- Кго регистра группы (,п) соединество, содержащее генератор тактовыхны соответственно с входами первой 108 25 4 импульсов, блок генерации случайного кода, блок задания закона распределений, блок элементов И, блок элементов ДЛИ, блок памяти, причем первые установочные входы соединены с первыми входами блока задания законов распределений, вторые входы которых соединены с выходами блока генерации случайного кода, вход которого соединен с выходом генератора Тактовых импулы сов и с первым входом блока элемента И, вторые входы которого соединены с выходами блока элементов ИЛИ, входы которого соединены с выходами блока, задания законов распределений, третьи входы которого соединены с выходами устройства и выходами блока памяти, входы KdToporo соединены с выходами блока элементов И СЗЗ. Известное устройство моделирует марковский процесс, который описывает и системы массового обслуживания. Если задавать достаточно малые интервалы времени, за которые исследовать (моделировать) изменение состояний системы массового обслуживания, то легко представить вероятностный автомат как модель системы массового обслуживания. Однако устройство не позволяет регистрировать моменты входа и выхода требований из системы, а также занятость системы обслуживанием, что ограничивает функциональные возможности известного устройства, Цель изобретения т расширение функциональных возможностей путем моделирования входных и выходных потоков в системах массового обслуживания. Указанная цель достигается тем, что устройство для моделирования марковских потоков сигналов, содержащее генератор случайного кода, генератор тактовых импульсов, блок элементов ИЛИ, блок элементов И, блок памяти и блок задания закона распределения, состоящий из п идентичных узлов, каждый из которых содержит группу регистров, группу сумматоров, первую и вторую группы И, группу схем сравнения, разрядные входы регистров всех узлов блока задания закона распределения являются соответствующими установочными входами устройства, а в каждом узле выходы первого регистра группы соединегруппы ()-го сумматора группы, вторая входов первого суммато ра группы соединена соответственно с выходами первого регистра группы, вторая группа входов М-го сумматора группы , h -J) соединена соответ ственно с выходами (Лл-)-го сумматора группы, выходы всех сумматоров т1цруппы подключены к первым входам соответствующих элементов И первой группы, выходы которых соединены с входами первой группы соответствующих схем сравнения группы,выход7 -й- сравнения группы соединен с прямым входом (k-1 )-го элемента И второй груп пы, выход Р-й схемы сравнения группы (f,h-1) подключен к Р-м инверсным входам элементов И второй труппы с номером, бол.ьшим Р , выход первой схем сравнения группы и выходы элементов И второй группы являются соответствующими выходами узла блока задания закона распределения, одноименные выходы узлов блока задания закона распределения подключены к соответствуюпщм входам одноименного элемента ИЛИ блок элементов ИЛИ, выхода которых подключ ны соответственно к первым входам элементов И блока элементов И, вторые входы которых объединены и подключены к выходу генератора тактовых импульсов и входу запуска генератора случайного кода, тгходы элементов И блока элементов И соединены с соответствующими входами блока памяти, выход которого подключены к вторым объединенным входам элементов И первой груп пы соответствующего узла блока задания закона распределения, входы второй группы схем сравнения которого подключены соответственно к выходам 1генератора случайного кода, дополнительно содержит регистр, первый и . второй блоки сравнения и три элемента задержки, входы которых подключены к выходу генератора тактога х импульсов, выходы блока памяти, являющиеся группой выходов устройства, соединеш соответственна с разрядными входами регистра, с входами первой группы первого и второго блоков сравнения, вторые группы входов которых подклкгчены соответственно к разрядным выходам регистра, выходы первой и в второй схем сравн ия являются соответственно первым и вторым выходами устройства, выходы первого и второго элементов задержки подключены соответственна к входу разрешения записи и входу сброса регистра, а выход третьего элемента задержки соединен с входами разрешения сравнения первой и второй схем сравнения. На фиг, 1 приведена блок-схема устройства; на фиг, 2 - функциональная схема узла блока задания закона распределения; на фиг, 3 - временные /улаграммл работы устройства. Устройство для моделирования систем массового обслуживания (фиг. 1) содержит .группу установочных входов 1, блок 2 задания закона распред влейия, Генератор 3 случайного кода, генератор 4 тактовых импульсов, первый 5, второй 6 и третий 7 элементы задержки, блок 8 элементов И, блок 9 элементов ИЛИ, регистр 10, первый 1) и второй i 2 блоки сравнения, причем второй блок 12 сравнения реализован аналогично первому блоку 11 сравнения, группу выходов 13, блок 14 памяти, первый и второй выходы 15 и 16, Блок 2 задания закона распределения содержит п Однотипных узлов, каждый из узлов блока 2 включает группу регистров 17, вторую группу входов 18, соединенную с соответствунлдими выходами генератора 3, группу схем 19. сравнения, первую группу элементов И 2, выход 13j для каждого узла, соединенный с соответствующим i-м выходом 13 устройства, вторую группу элементов И 21, группу сумматоров 22, группу выходов 23. , Одноименные вьосоды узлов, подключены к входам одного ЗГтого же элемента ШШ блока элементов ИЛИ, Устройство работает следующим образом. По установочным входам I в регистры 17 блока 2 задания закона распределения заносятся коды матрицы вероятностей перехода системы массового обслуживания. При этом в регистр заносится вероятность Р,-:-перехода системы в е состояние, при условии, что она в предыдущий момент вреени находилась в 1-м состоянии. Устройство может моделировать роцесс функционирования систем массового обслуживани как одноканальных, ак и ьшогоканальных с отказами и без отерь. Причем для систем без потерь вводится ограничение на макимально опустимую длину очереди. При этом в каждом случае матрица переходных ероятностей формируется индивидуально .

Рассмотрим формирование матрицы 41ереходных вероятностей для п канальной системы. Bceli каналов абсолютно идентичны, освободившийся канал за нимает первое в очереди требование. Вероятности Ро(г1-с(Сд , Po , а вероятности Р,2, PQ..- Р равны нулю как величины высшего порядка waдрсти по сравнению с POQ и cLинтенсивность входящего пуассоновского потока требований на обслуживание.

Для систем массового обслуживания без потерь с 1 -каналами матрица переходных вероятностей имеет такой же вид,как и для системы сп приборами 5 обслуживания, но в этом случае п- максимально допустимое число заявок в очереди (выбирается из условия максимального отклонения от математического ожидания).40

Предположим, что моделируется си бтема с k приборами и максимально возможным числом требований в системе, равным h.

Тогда наличие сигнала на первом выходе 13- говорит о том, что в системе нет требований и все приборы свободны, наличие сигнала на выходе 132 в системе одно требование и занят один канал, а наличие сигнала на выходе 50 13 - заняты два прибора. Если сигнал на выходе то заняты обслуживанием jBce V приборов. Если сигнал на выходе 13J, то i приборов заняты и в очереди C-tkHl требований.5S

Интервалы времени выбираются значительнолменьше по величине, чем ,е и . Причем чем меньшеД , тем больше

Вероятность P jf/tAt, , а

вероятность Р распределяется из условия поступления в систему очередного требования, т.е. , где L - интенсивность потока обспуживания. Вероятности - ° 0. (i 3, П). Вероятности Р.л Р Р 2 нормируются.

В целом матрица переходных вероятностей имеет вид

oCdi l+oiAt

точность моделирования, однако в этом случае увеличивается время моделированид. . .

Генератор 4 тактовой частоты задает интервалы времениЛ, разные периоду следования его импульсов.

Устройство работает следующим образом.

/

Начальное состояние устройства для моделирования предусматривает наличие сигнала на выходе 13,., т.е. в системе массового обслуживания нет требований. По установочным входам 1 в регистры 17 блока 2 задания закона распределений внесены коды Р- матрицы Р. С приходом импульса генератора А, который подается на входы первого. 5, второго 6 и третьего 7 элементов задержки времени . на первый вход блока элементов И 8 и вход генератора 3 случайного кода. в нем вырабатывается код числа, равномерно распределенного в интервале от нуля до единицы.

Так как на выходе 13 имеется потпнциал, то по входу 13-, блока 2 подается потенциал, элементы И 20 первого узла блока 2 открыты и коды регистра 17 а также сумматоров 22 |-22| ПодаютсЯ на вторые входы схем {9 ;|-1$ сравнени Если в регистрах 17| -Ц хранятся коды РОО РО I PDI г то на выходах регистра 17 и сумматоров сформировываются коды .-ьР... Р.ч-Я,. Р,2,...,Ров Р о J.P Р +Р f 00 Т d « 00 01 .., Р, 11ричем сумма последнего элемейта строки равна единице. Предположим, что генератор 3 сген рировал случайный код А„.численная величина которого меньше величины кода Рд. Данный код подается на входы схем 19|irl9}rv. Так как код А меньш по величине кодов, подаваемых на другую группу входов схем 19 сравнения, то на их выходах появляются потенциалы, причем потенциал с выхода , схемь 19 сравнения закроет все элементы И 21 и сигнаа появится только на выходе 23 блока 2. Данный сигнал поступает через бло 9 элементов ИЛИ. Тогда с выхода 13 вновь снимается потенциал (фиг. 3), т.е. за время dt в систему массового обслуживания заявок Hfe поступает. По заднему фронту сигнала генератора 4 через первый элемент 5 задержки в регистр 10 происходит запись нового состояния выходов 13, Причем перед этим по переднему фронту импульса генератора 4 с незначительной задержкой, формируемой третьим элементом 7 задержки, в блоках 11 и 12 сравнения происходит сравнение чисел регистра - 10 и нового состояния выходов 13 в позиционном коде. Так как изменений происходит, то на выходах первого 11 второго 12 блоков сравнения сигналов нет. После сравнения второй элемент задержки сбрасывает регистр 10 в нулевое состояние, т.е. процесс сравиения с предыдущим кодом выходов 13 происходит перед записью нового состо яния выходов 13 в регистр 10. Предположим, (фиг. 3), что лишь за четвёртый интервал At в систему массо вого обслуживания поступило сообщение Рассмотрим, как это моделируется в системе. С приходом четвертого импульса от генератора 4 тактовых импульсов генератор 3 случайного кода генерирует код, величина которого меньше числа Q+Pjj, но больше числа PQJJ. В этом слу чае срабатывают схемы ,-1 равнения. Сигнал с выхода схемы Р внения закрывает элементы И . и на выходе 137 блока 2 появляется потенциал, который проходит через блок 9 элементов ИЛИ, блок 8 элементов И на второй вход блока 14 памяти и на выходе 13 устройства появляется потенциал. Это моделирует случай приход да в систему требования за интервал Ai и принятия его на обслуживание. В системе занят один канал обслуживанием. Наличие сигнала на выходе 13 свиде1ельствует о занятости обслуживанием в системе одним каналом одного требования и отсутствие очереди в системе. t Появлением импульса на выходе третьего элемента 7 задержки на входы блоков 11 и 12 сравнения подается потенциал. Так как на выходах регистра 10 снимается код 1QOO..., подаваемый на одни входа блока J1, а на другие его входы подается код 01000..., который меньше кода 10000..., то на выходе блока I1 сравнения появляется потенциал, который подается на выход 15. Появление потенциала на выходе 15 свидетельствует о приходе в систему требования в отечет времени, задаваемый генератором 4, и о занятии обслуживанием одного канала. На фиг, 3 показано, что и за шестой интервал At в систему поступает еще одно требование и занят обслуживанием второй канал, так как сигнал появляется на выходе 1Зх устройства и на выходе 13. Если же за какой-либо интервал ;Л будет закончено,обслуживание требования, то в этом случае сигнал появляется на выходе 13 по порядковому номеру индекса, меньшему на единицу, чем I3j. , этом случае срабатывает второй блок сравнения. На третьем выходе 16 устройства появляется потениал, что позволяет.зафиксировать время выхода требования из системы массового обслуживания. Таким образом, в процессе моделирования системы массового обслуживания возможно получить модель входного потока сообщений по анализу потока импулы cob на выходе 15, модель выходного потока сообщений - по анализу потока импульса на выходе 16, модель занятости системы обслуживания.(период занятости) требований - по анализу потенциалов на выходах 13.

)

I i

Ф

J

I t

2%

ль

-5

Й

Фиг.2

2Jt,

1 2Si

(a

фигЗ