Устройство для моделирования распределения приоритетов Советский патент 1987 года по МПК G06F9/50 G06N7/08 

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

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

На фиг. 1 приведена блок-схема устройства; на фиг. 2 - функциональная схема блока регистров памяти; на фиг. 3 - функциональная схема коммутатора; на фиг. 4 - функциональная схема блока определения состояний; на фиг. 5 - функциональная схема генератора случайного кода; на фиг. 6- функциональная схема блока памяти; на фиг. 7 - функциональная схема блока формирования времени состояний; на фиг. 8 - функциональная схема генератора потока заявок.

Устройство содержит информационные входы 1, блок 2 регистров памяти, коммутатор 3, блок 4 определения состояния, генератор 5 случайного кода, блок 6 памяти, блок 7 формирования

где Pi; - вероятность перехода систем в момент времени t.+ О (где t - момент времени поступления на обслуживание к-й заявки) из i-ro состояния

времени состояния, генератор 8 тактовых импульсов, генератор 9 потока за- g состояние. Причем i-e состоя- явок, входы 10 задания начального

ние характеризуется тем, что поток заявок 1-го приоритета образуют не-- точники заявок с номера один по номер i, а поток заявок 2-го приоритет 40 образуют источники заявок с номера (1+1) по номер (п+1). Тогда интенсивности потоков заявок 1-го и 2-го приоритетов определяется соответственно

состояния, выходы 11.

Блок 2 регистров памяти содержит регистры 12 памяти с выходами 13,

Коммутатор 3 содержит элементы И 14 с входами 15 и 16, элементы ИЛИ 17с выходами 18.

Блок 4 определения состояния содержит группу сумматоров 19, группу схем 20 сравнения с входами 21, груп- пу элементов И 22 с выходами 23. Генератор 5 случайного кода содержит генератор 24 пуассоновского потока импульсов, элемент И 25, кольцевой регистр 26 сдвига, шифратор 27, элементы И 28.

Блок 6 памяти содержит элементы ИЛИ 29, триггеры 30, элементы ИЛИ 31. Блок 7 формирования времени состояния содержит группу элементов ИЛИ 32, группу элементов И 33, счетный вход 34, группу счетчиков 35.

Генератор 8 потока заявок содержит генератор 36 пауссоновского потока

5

импульсов, элемент И 37, кольцевой регистр 38 сдвига, элементы И 39, одновибраторы 40, элемент ИЛИ 41, формирователь 42 импульсов, элемент И 43.

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

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

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

Р

где Pi; - вероятность перехода системы в момент времени t.+ О (где t - момент времени поступления на обслуживание к-й заявки) из i-ro состояния

g состояние. Причем i-e состоя-

g состояние. Причем i-e состоя-

45

ние характеризуется тем, что поток заявок 1-го приоритета образуют не-- точники заявок с номера один по номер i, а поток заявок 2-го приорите 40 образуют источники заявок с номера (1+1) по номер (п+1). Тогда интенсивности потоков заявок 1-го и 2-го приоритетов определяется соответственно

Л+1

Jrl

f -,

J,4.,

где о/- - интенсивность потока заявок

45

50

j-ro источника.

По входам 10 подается входное воздействие, определяющее начальное состояние системы. Например, в начальный момент времени подан сигнал в виде gg импульса по входу 10. До этого момента времени триггеры 30 блока 6 памяти находились в нулевых состояниях. При подаче единичного потенциала на установочный вход lOj блока 6

через элемент РШИ 29. триггер 30 перебросится в единичное состояние и с его выхода единичный потенциал поступает на выход 16, блока 6, а затем на вход 16 группы входов блока 7 формирования времени состояний 0. В блоке 7 импульс поступает на первый вход элемента И потенциалом с выходов элементов ИЛИ 32 обнуляется содержимое счетчиков 35.

Входы установки в ноль счетчиков 35 динамические, как и все входы триггеров блока 6 и работают на передний фронт импульсов.

Триггер 30J блока 6 установлен в единичное состояние в потенциал с выхода 16jблока 6 также открывает элемент i И 14 второй группы коммутатора 3. Этим самым будет разрешена подача кодов второй строки матрицы

21 17,

, которые хранятся в регистрах 1221-12 0 в блок 4 определения состояний при приходе импульса по входу 15 коммутатора 3.

Таким образом, начальное состояние - второе, т.е.

01, С, С/2

Д2 ,с/.

По истечении 20-ти импульсов генератора 8 исчезает импульс на выходе одновибратора 40) генератора 9, формирователь 42 сигнала выделит

В коммутаторе 3 коды вероятностей Р„„, ..., Р,„ будут поданы чеВ момент времени t начинает работать генератор 8.тактовых импульсов.

По первому импульсу генератора 8 в генераторе 9 потока заявок происхо- 35 задний фронт импульса и подаст им- дит следующее. До момента времени t, пульс на управляющие входы коммутато- все одновибраторы 40 на своих выходах ра 3 и генератора 5 случайного кода, имеют нулевые потенциалы. Следовательно элемент И 43 открыт. Генера- rj, , f j-j 2n тор 36 пуассоновского потока импуль- 40 открытые соответствующие элементы сов совместно с элементом И 37 и цик- И в блок 4. лическим регистром 38 сдвига образуют

равновероятностный (1-т) полюсник, В блоке 4 определения, состояний Действительно час-гота импульсов гене- (фиг. 4) на первые входы схем 20 срав- ратора 36 превьшает значительную час- 45 нения будут подаваться соответствую- тоту импульсов опроса по входу 34. щие коды Тогда между моментами опроса по входу 34, записанная в одном из разрядов регистра 38, единица успевает многократно обойти ячейки регистра 38, а в момент опроса потенциал с вероятностью 1/т фиксируется на одном из выходов регистра 38. Генератор 9 потока заявок моделирует приход заявок суммарного потойа первого и второго приоритетов, т.е. поток с интенсив50

21

+ Р

21

+ Pj2 ; Pji

+ Pj2+,,.., +

2n

Генератор случайного кода с прихог дом потенциала по управляющему входу 15 вырабаытвает код А числа равно- 52 вероятно распределенного в интервале 0,1. Код А -числа с выходов 21

ностью 2 о(. и функцией распределения интервалов времени между соседними заявками F(t).

1352499 . 4

Исходя из точности моделирования отрезок QM на оси ординат разбуша- ется на m равных частей. Каждой вероятности р. ,. где (i 1, m) уста

навливается соответствующее время t по оси абцисс, на которое настраивается соответствующий одновибратор 40..

С приходом импульса по входу 34 элемент И 37 закрьтается, на одном из выходов регистра 38 фиксируется потенциал, который через соответствующий элемент И 39- запускает одновиб- ратор 40:. Потенциал с выхода одно- вибратора 40; через элемент ИЛИ 41 запирает элемент И 43 на время, равное времени длительности импульса на выходе одновибратора 40. Пусть дли

тельность импульса равна 20-ти тактам генератора 8.

В блоке 7 формирования состояний (фиг. 7) через открытый элемент И 33 импульсы генератора 8 от входа 34

поступают в счетчик 35, , в котором их число подсчитывается. Информация снимается с выходов счетчика 35 2. и свидетельствует о том, сколько времени система находится во втором состоянии.

По истечении 20-ти импульсов генератора 8 исчезает импульс на выходе одновибратора 40) генератора 9, формирователь 42 сигнала выделит

задний фронт импульса и подаст им- пульс на управляющие входы коммутато- ра 3 и генератора 5 случайного кода, rj, , f j-j 2n открытые соответствующие элементы И в блок 4.

В коммутаторе 3 коды вероятностей Р„„, ..., Р,„ будут поданы чений фронт импульса и подаст им- ьс на управляющие входы коммутато- 3 и генератора 5 случайного кода, , f j-j 2n открытые соответствующие элементы блок 4.

блоке 4 определения, состояний . 4) на первые входы схем 20 срав- я будут подаваться соответствую- коды

21

21

+ Pj2 ; Pji

+ Pj2+,,.., +

В блоке (фиг. 4) н 45 нения буду щие коды

50

+ Р

2n

В блоке 4 определения, состояний (фиг. 4) на первые входы схем 20 срав- 45 нения будут подаваться соответствую- щие коды

Генератор случайного кода с прихог дом потенциала по управляющему входу 15 вырабаытвает код А числа равно- 52 вероятно распределенного в интервале 0,1. Код А -числа с выходов 21

блока 5 подается на вторую группу входов 21 блока 4 определения состояний.

5-13В блоке 4 код А числа в каждой схеме 20 сравнения сравнивается с

+ Р, . Если

Ь л

кодом Pji + Pj2 +

2-i

код числа А РЗ PZZ 21 то на выходе узла 20; сравнения будет потенциал. Пусть А тогда потенциалы будут на выходах узлов

20,- сравнения (i 2,п). Только на выходе 23 блока 5 будет потенциал, так как потенциал с выхода узла 20j сравнения закроет остальные элементы И 22.

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

Лоп 3«A1

И t

з«Аг

t

Лоп з«л г

Импульс с выхода 23 блока 4 подает- 20 ся на вход 23,j блока 6 памяти, так как Триггер 30 находится в единичном состоянии, то в схеме блока 6 изменений не произойдет. На 21-ом импульсе генератора 8 вновь сработа ет генератор 9 потока заявок. Если сработает одновибратор 40 и выдаст

Таким обарзом, в процессе моделирования с выходов 11 снимается информация о времени пребьгеания системы в i-OM состоянии, которая позволяет оценить эффективность использования

системы массового обслуживания.

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

импульс длительностью 5 тактов генератора 8, тогда по истечению пяти так- Устройство для моделирования рас- тов на выходе генератора 9 потока 30 пределения приоритетов, содержащее заявок будет потенциал, который вызо- блок регистров памяти, генератор им- вет срабатывание генератора 5 случай- пульсов, коммутатор, генератор слу- ного кода и подачу кодов второй стро- чайного кода, блок памяти и блок опблок 4 определения

ки матрицы Р в состояний.

Пусть число А Pji +Р22

потенциалы будут на ыходах узлов сравнения (1 3,п) блока 4.

В блоке 4 будет потенциал на выходе 23з, так как потенциалом с узла 20 сравнения будут закрыты все элементы И, начиная с третьего. В - блоке памяти .6 триггер 30 будет переброшен в единичное состояние потенределения состояния, содержап ий груп- 35 пу схем сравнения, группу элементов т.е. И и группу сумматоров, разрядные

выходы i-ro сумматора группы (, п-1) соединены соответственно с информационными .входами первой группы 40 (1+1)-й схемы сравнения группы, одноименные информационные входы второй группы всех схем сравнения группы объединен и подключены соответственно к выходам генератора случайного

циалом с выхода 23 блока 4 определе- 45 кода, выход первой схемы сравнения

ния состояний.

С приходом очередной заявки прогнозируется, что

t

АОП ЗМА1

-ЗЯА 2

АОП зад 2

Следовательно изменяется состояние системы (система переходит в третье состояние) и интенсивности потоков 1-го и 2-го приоритетов. Происходит переключение заявок одного источника из группы заявок 2-го приоритета в группу заявок 1-го приоритета, т.е. ,

после изменений интенсивности потоков определяется

-d,( ;

d,,..

..

Потенциалом с выхода триггера 30 через элемент ИЛИ 31 будет сброшен в нулевое состояние триггер 30. Через элемент ИЛИ 32 блока 7 формирования задержки будет сброшен в нулевое состояние счетчик 35., с которого снимается до этого момента времени информация о времени пребьшания системы во втором состоянии, а также

будет открыт элемент И 33, и в счетчике 355 будет накапливаться информация о времени пребывания системы массового обслуживания в третьем состоянии.

Таким обарзом, в процессе моделирования с выходов 11 снимается информация о времени пребьгеания системы в i-OM состоянии, которая позволяет оценить эффективность использования

системы массового обслуживания.

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

группы соединен с первым инверсным входом всех элементов И группы, а выход k-й схемы сравнения группы (k 2,п) подключен к прямому входу

50 (k-l)-ro элемента И группы и k-му инверсному входу с k-ro по (п-1)-й элемент И группы, а разрядные выходы М-го сумматора группы (, п-2) подключены соответств енно к информаци55 онным входам первой группы (M+D-ro сумматора группы, разрядные входы регистров блока регистров памяти являются соответствующими информацион-| ными входами устройства, а первая

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

и блок формирования времени состоя- .....

ния, содержащий группу элементов ИЛИ, fo ра группы блока определения состо яния, группу элементов И и группу счетчи- а k-я группа выходов коммутатора подков, разрядные выходы которых являются группой информационных выходов устройства, выходы элементов ИЖ группы соединены соответственно с установочными выходами счетчиков группь, счетные входы которых подключены соответственно к выходам элементов И группы, первые входы которых

объединены и соединены с выходом 20 (,п) подключен к второму входу генератора тактовых импульсов и вхо- j-ro элемента И группы блока форми- дом запуска генератора потока заявок, рования времени состояния и j-му выход которого подключен к входу за- входу всех, кроме j-ro, элементов пуска генератора случайного кода и ИЛИ группы блока формирования време- входу опроса коммутатора, информа- 25 ни состояния, ционные вхрды которого подключены

соответственно к выходам блока ре-- гистров памяти, а управляющие входы коммутатора соединены соответственно с выходами блока памяти, первая груп па выходов коммутатора подключена соответственно к первой группе информационных входов первой схемы -. сравнения группы и первой группе информационных входов первого сумматоключена соответственно к информационным входам второй группы (k-l)-ro . сумматора группы блока определения 15 состояния, выход первой схемы сравне ния и йыходы элементов И группы которого соединены соответственно с информационными входыми второй группы блока памяти, j-й выход которого

/ Ijl

/ //

L L

1 1 T

hi jiI21

I i:::I

12г1

II I

JA, ... fЯ

rj/,;jf,/j

Ж

/J /J// r r

.....

ра группы блока определения состо яния, а k-я группа выходов коммутатора подсоответственно к выходам блока ре-- гистров памяти, а управляющие входы коммутатора соединены соответственно с выходами блока памяти, первая группа выходов коммутатора подключена соответственно к первой группе информационных входов первой схемы -. сравнения группы и первой группе информационных входов первого сумматора группы блока определения состо яния, а k-я группа выходов коммутатора под(,п) подключен к второму входу j-ro элемента И группы блока форми- рования времени состояния и j-му входу всех, кроме j-ro, элементов ЛИ группы блока формирования време- ни состояния,

ключена соответственно к информационным входам второй группы (k-l)-ro . сумматора группы блока определения состояния, выход первой схемы сравнения и йыходы элементов И группы которого соединены соответственно с информационными входыми второй группы блока памяти, j-й выход которого

f1 ,гfX

ifii ifti fftt

I1:::I

J2zi

Пт

Изобретение относится к вычислительной технике и может быть исполь, ,г ,/г -Г г ,f П 1„ 1,1 1т Inn Inn II::1II::1 зовано при моделировании сложных стохастических систем, описываемых в виде систем массового обслуживания с динамическим р:аспределением приоритетов. Цель изобретения - расширение функциональных возможностей за счет моделирования динамического распределения приоритетов. Устройство содержит информационные входы 1, блок 2 регистров памяти, коммутатор 3, блок 4 определения состояний, генератор 5 случайного кода, блок 6 памяти, блок 7формирования времени состояний, генератор 8 тактовых импульсов, генератор 9 потока заявок, входы 10 задания начального состояния, выходы 11. 8ил. с Ф (Л

1

I nn

Ni/ si/

I nn

12

/7/7

ГТ 1

,

/J/7/7J SfTfT

фиГ.З

илты

24Ч1ь5

и

и :: : .1;.

Щ Щ---

Т Т

%/ /;--

i

pueS /, ,

а,

з

Ю.0tStlf-

X,

30,

30,

МЗп

tei

№

41 T 41 Th U-..

//

I

(риг. 6

tSz

i .

«,

/

%

и

S-Ч

фигУ

Составитель В. Фукалов Редактор Ю. Середа Техред М.Ходанич Корректор Г. Решетник

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

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

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

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