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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛ ИСТИЧЕСНИХ

РЕСПУБЛИК (51) 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ

101

r0<

®т

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4080345/24-24 (22) 20.06.86 (46) 15.11.87. Бюл. 9 42 (71) Таганрогский радиотехнический институт им.В.Д.Калмыкова (72) В.И.Финаев, О.М.Фабрикант и В.Н.Шаховой (53) 681.3(088.8) (56) Авторское свидетельство СССР

У 1108455, кл. G 06 F 15/20, 1982.

Авторское свидетельство СССР

У 1200297, кл. С 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

РАСПРЕДЕЛЕНИЯ ПРИОРИТЕТОВ (57) Изобретение относится к вычислительной технике и может быть исполь„„SU„„1352499 А1 зовано при моделировании сложных стохастических систем, описываемых в виде систем массового обслуживания с динамическим распределением приоритетов. Цель изобретения — расширение функциональных возможностей за счет моделирования динамического распределения приоритетов. Устройство содержит информационные входы 1, блок 2 регистров памяти, коммутатор 3, блок

4 определения состояний, генератор 5 случайного кода, блок 6 памяти, блок

7 формирования времени состояний, генератор 8 тактовых импульсов, генератор 9 потока заявок, входы 10 задания начального состояния, выходы 11.

8 ил. Ф

1352499

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

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

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

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

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

Коммутатор. 3 содержит элементы

И 14 с входами 15 и 16, элементы ИЛИ

17 с выходами 18.

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

Блок б памяти содержит элементы

ИЛИ .29, триггеры 30, элементы ИЛИ 31.

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

34, группу счетчиков 35.

Генератор 8 потока заявок содержит генератор 36 пауссоновского потока импульсов, элемент И 37, кольцевой регистр 38 сдвига„ элементы И 39, одновибраторы 40, элемент ИЛИ 41, формирователь 42 импульсов, элемент

И 43.

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

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

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

Р,„Р

21 2L 2n

° ° °

30 где Р; — вероятность перехода системы в момент времени + 0 (где- t1, — момент времени поступления на обслуживание к-й заявки) из -го состояния 35 n j-e состояние. Причем i-e состояние характеризуется тем, что поток заявок 1-го приоритета образуют источники заявок с номера один по номер i а поток заявок 2-го приоритета

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

45 (с 1б1 где a — интенсивность потока заявок

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

По входам 10 подается входное воздействие, определяющее начальное состояние системы. Например, в начальный момент времени подан .сигнал в виде

55 импульса по входу 10>. ДО этОГО мо мента времени триггеры 30 блока 6 памяти находились в нулевых состояниях. При подаче единичного потенциала на установочный вход 10> блока 6

1352499 через элемент ИЛИ 292 триггер 302 перебросится в единичное состояние и с его выхода единичный потенциал поступает на выход 162 блока 6, а затем

5 на вход 162 группы входов блока 7 формирования времени состояний О.

В блоке 7 импульс поступает на первый вход элемента И 33 и потенциалом с выходов элементов ИЛЙ 32 обнуляется содержимое счетчиков 35 °

Входы установки в ноль счетчиков

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

Триггер 302 блока 6 установлен в единичное состояние в потенциал с выхода 162блока 6 также открывает элемент; И 14 второй группы коммутатора 3. Этим самым будет разрешена 20 подача кодов второй строки матрицы

Р : Р2„ Рг ° Рг„, которые хранятся в регистрах 122, -122„ в блок 4 определения состояний при приходе импульса по входу 15 коммутатора 3.

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

Л 2 53 6 4 ° -. Ы и+1

В момент времени начинает работать генератор 8.тактовых импульсов.

По первому импульсу генератора 8 в генераторе 9 потока заявок происходит следующее. До момента времени t все одновибраторы 40 на своих выходах имеют нулевые потенциалы. Следовательно элемент И 43 открыт. Генератор 36 пуассоновского потока импуль- 4р сов совместно с элементом И 37 и циклическим регистром 38 сдвига образуют равновероятностный (1-ш) полюсник.

Действительно частота импульсов генератора 36 превышает значительную час- 45 тоту импульсов опроса по входу 34.

Тогда между моментами опроса по входу

34, записанная в одном из разрядов регистра 38, единица успевает многократно "обойти" ячейки регистра 38, а в момент опроса потенциал с вероятностью 1/В1 фиксируется на одном из выходов регистра 38. Генератор 9 потока заявок моделирует приход заявок суммарного пото2 а первого и второго приоритетов, т.е. поток с интенсивностью a(= с, и функцией распре2 деления интервалов времени между соседними заявками F(1:).

Исходя из точности моделирования отрезок $013 на оси ординат разбивается на m равных частей. Каждой вероятности д р,, где (i = 1, m) устанавливается соответствующее время й! по оси абцисс, на которое настраивается соответствующий одновибратор

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

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

По истечении 20-ти импульсов генератора 8 исчезает импульс на выходе одновибратора 401 генератора 9, формирователь 42 сигнала выделит задний фронт импульса и подаст импульс на управляющие входы коммутатора 3 и генератора 5 случайного кода.

В коммутаторе 3 коды вероятностей

Р „, Р, ..., Р г„будут поданы через открытые соответствующие элементы

И в блок 4.

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

21 22 2< 22

2л

Генератор случайного кода с прихо; дом потенциала по управляющему входу

15 вырабаытвает код "А" числа равновероятно распределенного в интервале (0,1) . Код "А" -числа с выходов 21 блока 5 подается на вторую группу входов 21 блока 4 определения состояний.

5 1352499В блоке 4 код "А" числа в каждой схеме 20 сравнения сравнивается с кодом Р „ + Р12 + ° ° ° y + Р е Если код числа А ь + P„ +, ° . ° ° +P<,, то на выходе узла 20; сравнения будет 5 потенциал. Пусть А ñ г +Pãã тогда потенциалы будут на выходах узлов

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

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

2 4 г" 1

Л,=о(„ ь >

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

3 чике 35> будет накапливаться информация о времени пребывания системы массового обслуживания в третьем состоянии.

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

i-ом состоянии, которая позволяет оценить эффективность использования системы массового обслуживания.

Устройство для моделирования распределения приоритетов, содержащее блок регистров памяти, генератор импульсов, коммутатор, генератор случайного кода, блок памяти и блок оп.ределения состояния, содержащий группу схем сравнения, группу элементов

И и группу сумматоров, разрядные выходы i-го сумматора группы (i 1 и-1) соединены соответственно с информационными входами первой группы (i+1)-й схемы сравнения группы, одноименные информационные входы второй группы всех схем сравнения группы объединены и подключены соответственно к выходам генератора случайного кода, выход первой схемы сравнения группы соединен с первым инверсным входом всех элементов И группы, а выход k-й схемы сравнения группы Ос=

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

M-ro сумматора группы (M=1, и-2) подключены соответственно к информационным входам первой группы (М+1)-ro сумматора группы, разрядные входы регистров блока регистров памяти являются соответствующими информацион- ными входами устройства, а первая втором состоянии, т.е. выполнено условие

4ВП доп эад 1< „и „„ (Тз ду

ЗиА1

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

Пусть числа А Рг1+Рл+Ргз потенциалы будут на выходах. узлов

20„. сравнения (i = З,n) блока 4.

В блоке 4 будет потенциал на выходе 23, так как потенциалом с узла 40

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

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

Ьмд Зад1 ЗюА 2 ЗаА2

Следовательно изменяется состояние системы (система переходит в третье состояние) и интенсивности потоков

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

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

1352499

1 Н

ln лк

° ° °

1 2 Ф( т >nr

1 2

%1 21

Ф

75р rr

° ° ° г

1zn 7zn

1 2

7 п 7,л

1 2

)rn 1ю

)zn

° Ъ °

gn группа информационных входов блока памяти является группой установочных входов устройства, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных воэможностей за счет моделирования динамического распре.деления приоритетов, оно дополнительно содержит генератор потока заявок и блок формирования времени состояния, содержащий группу элементов ИЛИ, 10 группу элементов И и группу счетчиков, разрядные выходы которых являются группой информационных выходов устройства, выходы элементов ИЛИ группы соединены соответственно с установочными выходами счетчиков группы, счетные входы которых подключены соответственно к выходам элементов И группы, первые входы которых объединены и соединены с выходом 2о генератора тактовых импульсов и входом запуска генератора потока заявок, выход которого подключен к входу запуска генератора случайного кода и входу опроса коммутатора, информа- 25 ционные входы которого подключены соответственно к выходам блока ре- " гистров памяти, а управляющие входы коммутатора соединены соответственно, с выходами блока памяти, первая груп" па выходов коммутатора подключена соответственно к первой группе информационных входов первой схемы: сравнения группы и первой группе информационных входов первого сумматора группы блока определения состояния, а k-я группа выходов коммутатора подключена соответственно к информационным входам второй группы (k-1)-го сумматора группы блока определения состояния, выход первой схемы сравнения и выходы элементов И группы которого соединены соответственно с информационными входыми второй группы блока памяти, j-й выход которого (j=1,n) подключен к второму входу

j-ro элемента И группы блока формирования времени состояния и )-му входу всех, кроме j-ro, элементов

HJIH группы блока формирования времени состояния.

1352499

1352499

1л

У

Составитель В. Фукалов

Редактор Ю. Середа Техред М.Коданич Корректор Г. Решетник

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

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