Устройство для моделирования приоритетных систем массового обслуживания

 

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ПРИСНЧ1ТЕТНЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ, содержащее канал обслуживании заявок высокого приоритета и канал обслуживания заявок низкого приоритета, каждый канал обслужийаиия включает первый и второй злементы ИЛИ, счетчик обслуженных заявок, блок формирования заявок, . состоя1Ц11н из генератора заявок, счетчика заявок. счегш1са отказав, злемента запрета, элемента И злемента 11ЛИ к реверсивного , причем выход генератора заявок соеД1ше с входом счепика заявок, первым входом эпе««ента И и информационным входом элемента запрета, выход которого соединен с суммирующим входом реверсивного счетчи ка, разрядные выходы которого подключены к входам элемента ИЛИ соответственно, выход переполнения реверсивного счетчика соединен с управляюишм входом злемеита запрета и вторым входом злемеита И, выход которого подключен к входу счетчика отказов, и блок обслуживания заявок, состоящий из последовательно соединенных злемента И, генератора импульсов, злемента случайной задержки и триггера, нулевой выход которого соединен с первым входом элемента И, другой вход триггера подключен к выхо генератора импульсов, канал обслуживания заявок низкого приоритета допол1штелыю содержит элемент запрета, отличающееся тем, что, с целью расширения ; функциональных возможностей устройства за счет воспроизведения режима параллельного обслуживания заявок, каждый канал обслуживания допоанительно содержит группу блоков обслуживания заявок и коммутатор, содержащий три группы элементов .И, причем выход К-х элементов И первой и второй групп (К - 1,М) соединены соответственно с первым и вторым входами К-го элемента И третьей группы, в каждом канале обслуживания выход К-го элемента И третьей группы коммутатора соединен с вторым входом элемента И К-го блока обслуживания заявок, выход генератора импульсов К-го блока обслуживания заявок соединен с К-.ым входом первого элемента ИЛИ, выход которого соединен с вычитающим входом реверсивного счетчика блока формирования заявок, выход элемента ИЛИ блока формирования заявок канала обслуживания заявок высокого приоритета соединен с управляющим входом элемента запрета канала обслуживания заявок низкого приоритета и третьими входами элементов И третьей группы KOMMjrraTopa своего канала оСйслзокивания, выход элемента ИЛИ блока формирования заявок канала обсгуживания заявок низкого приоритета подключен к информационному входу злемента запрета, выход которого соединен с третьими входами элементов И третьей группы коммутатора своего канала обслуживания, выход ьторого элемента ИЛИ в каждом канале обслуживания соеданен с входом счетчика обс 1ужениых заявок . К-и элемент И первой и второй групп коммутатора имеет К входов, причем К-й из них инверсный, единичный выход триггера К-го блока обслуживания заявок канала обслуживания заявок высокого приоритета соединен с К-м входом второго элемента ИЛИ

(19) (11) СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИК

А ф150 G 06 F 15/20// 6 06 F 9/46

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

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ 1

r0CYAAPCT8EHHblA HOMHTET OCCP

ПО ДЕЛАМ ИЗОТ ЕТЕНИй И ОтНЕЫТИ (21) 3659913/24-24

° (22) 05.11.83 (46) 28.02.85. Бюл. М 8 (72) В. А. Герцев, Э. Г. Лазаревич, В; А. Мищенко, Л. Б. Авгуль и В. М. Неффа (53) 681.333 (088.8) (56) 1. Авторское свидетельство СССР

Р 450178, кл. 6 06 Р 15/20, 1973.

2. Авторское свидетельство СССР й" 98371ч. кл. 6 06 F 15/20, 1981 (прототип) (54) (57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВА.ННН ЛРИОРИТЕТНЫХ СИСТЕМ МАССОВОГО

ОБСЛУЖИВАНИЯ, содержащее канал обслуживания заявок высокого приоритета и канал обслуживания заявок низкого приоритета, каждый канал обслуживания включает первый и второй элементы ИЛИ, счетчик обслужен: иых заявок, блок формирования заявок, . состоящий из генератора заявок, счетчика заявок,, счетчика отказов, элемента запрета, элемента И элемента ИЛИ и. реверсивного счетчика, причем выход генератора заявок соединен с входом счетчика заявок, первым входоз» элемента И и информационным входом элемента запрета, выход коюрого соединен с суммируиидим входом реверсивного счетчи ка, разрядные. выходы которого подключены к входам элемента ИЛИ соответственно, выход переполнения реверсивного счетчика соединен с управляющим входом элемента запрета и вторым входом элемента И, выход которого подключен к входу счетчика отказов, и блок обслуживания заявок, состоящий из последовательно соединенных элемента И, генератора импульсов, элемента случайной задержки и триггера, нулевой выход которого соединен с первым входом элемента И, другой вход триггера подключен к выходу тенератора импульсов, канал обслуживания заявок низкого приоритета дополнительно содержит элемент запрета, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет воспроизведения режима параллельного обслуживания заявок, каждый канал об-. служивания дополнительно содержит группу блоков обслуживания заявок и коммутатор, содержащий три группы элементов .И, причем выход К-х элементов И первой и второй групп (К = 1,M) соединены соответственно с первым и вторым входами К-го элемента И третьей группы, в каждом канале обслуживания выход К-го элемента И третьей группы коммутатора соединен с вторым входом элемента И K-го блока обслуживания заявок, выход генератора импульсов К-ro блока обслуживания заявок соединен с К;ым входом первого элемента ИЛИ, выход которого соедичен с вычитающим входом реверсивного счетчика блока формирования заявок, выход элемента ИЛИ блока формирования заявок канала обслуживания заявок высокого приоритета соединен с управляющим входом элемента занрета канала обслуживания заявок низкого приоритета и третьими входами элементов И третьей группы коммутатора своего канала обслуживания, выход элемента ИЛИ блока формирования заявок канала обслуживания заявок низкого приоритета подключен к информационному входу элемента запрета, выход которого соединен с третьими входами элементов И третьей группы коммутатора своего канала обслуживания, выход второго элемента ИЛИ в каждом канале обслуживания соединен с входом счетчика обс1уженных заявок, К-й элемент И первой и второй групп коммутатора имеет К входов, причем К-й иэ них инверсный, единичный выход триггера

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

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

Процесс функционирования многонроцессорного вычислительного комплекса (МВК) с уче-. том работы операционной системы (ОС) можно представить в виде системы массового обслуживания (CM0), на вход которой поступает f6 два потока заявок:первый поток — это поток заявок ОС; второй поток — поток заявок . функциональных программ. Заявки СС обладают более высоким относительным приоритетом.

Каждый поток заявок имеет свое среднее время д обслуживания. Обслуживание производится М обслуживающими приборами.

Известно устройство для моделирования.

СМО, содержащее генератор импульсов, первый второй и третий счетчики, схему ЗАПРЕТ, схему ИЛИ, схему И., первый и второй генераторы случайного потока импульсов, peaepcwный счетчик, блок сравнения fl).

Однако устройство не позволяет моделировать СМО с приоритетами и ограниченной оче,адью.

Наиболее близким к предлагаемому является устройство для моделирования СМО, содержащее группу измерительных каналов (приоритетных уровней), каждый из которых содержит генератор случайного потока импульсов, три счетчика, две схемы И, четыре схемы ИЛИ., реверсивкый счетчик, схему сравнения, четыре схемы ЗАПРЕТ, триггер, блок случайного speмени задержки; кроме того, устройство содержит генератор случайного потока импульсов

s каждом канале, выход генератора случайного потока импульсов соединен с входом первого. счетчика, входом элемента запрета, первым вхо. дом первого элемента И, выход которого подклю чен к входу второго счетчика, а второй вход — к 40 управляющему входу элемента запрета и выходу первого элемента ИЛИ, выход элемента запрета подключен к суммирующему входу реверсивного счетчика, выход переполнения которого через схему сравнения соединен с первым входом 45 первого элемента ИЛИ, разрядные выходы реверсивного счетчика через четвертый элемент запрета соединены с первым входом второго элемента

И, второй вход которого.соединен с первым выходом триггера, выход второго элемента И соединен с входом генератора импульсов, выход которого подключен к первому входу триггера и через блок случайной временной задержки к первому входу второго элемента ИЛИ, выход которого подключен к второму входу триггера, второй выход которого подключен к вычитаннцему входу реверсивного счетчика (2) .

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

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

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

-приоритета доцолннтельно содержит элемент запрета в каждый канал обслуживания введены группа блоков обслуживания заявок и комму843

Э 142 татор, содержащий трн группы элементов И, причем выходы К-х элементов И первой н второй групп (К вЂ” 1,М) соединены соответственно с первым и вторым входами К-го элемента И третьей группы, в каждом канале обслуживания выход К-го элемента И третьей группы коммутатора соединен с вторым входом элемента И К-го блока обслуживания заявок, выход генератора импульсов К-го блока обслуживания заявок соединен в К-м входом 10 первого элемента ИЛИ, выход которого соединен с вычитающим входом . реверсивного счетчика блока формирования заявок, выход элемента ИЛИ блока формирования заявок канала обслуживания заявок высокого приоритета 15 соединен с управляющим входом здемента запрета канала обслуживания заявок низкого приоритета и третьим» входами элементов И третьей группы коммутатора csoего канала обслуживания, выход элемента ИЛИ блока формирования заявок канала обслуживания заявок низкого приоритета подключен к информаци-. онному входу элемента запрета, выход которого соединен с третьими входамн элементов И третьей .группы коммугатора своего канала об- д служивания, выход второго элемента ИЛИ в .. каждом канале обслуживания соединен.с входом счетчика обслуженных заявок, К-й элемент И первой и второй групп коммутатора имеет К входов, причем К-й из ннх инверсный, единичный выход триггера К-ro блока обслуживания

30 заявок канала обслуживания заявок высокого приоритета соединен с К-м входом второго элемента ИЛИ своего канала обслуживания и с К-ми входами всех элементов И перво» группы коммутаторов обоих каналов обслуживания, 45 а единичный выход триггера блока обслужива ния заявок канала обслуживания заявок низкого приоритета соединен с К-м входом второго элемента ИЛИ своего канала н с К-ми входами всех элементов И второй группы 40 коммутаторов обоих каналов обслуживания.

На фиг. 1 изображена фнукциональная схема устройства; на фнг, 2, 3 N 4 — схемы блока формирования заявок, блока обслуживания заявок и коммутатора соответственно. 45

Устройство содержит два канала l и 1< обслуживания, каждый из которых содержит блок 2 формирования заявок, коммутатор 3, М блоков 4 обслуживания заявок, причем коммутатор 3 обеспечивает поступление заявки на 50 первый свободный блок 4, второй элемент ИЛИ

5, счетчик 6 обслужепных заявок, первый элемент ИЛИ 7.

Второй канал содержит также элемент 8 . запрета.

Блок 2 формирования заявок содержит генератор 9 заявок, счетчик 10 заявок, счетчик

11 отказов, элемент И !2, реверсивный счетчик

13, элемент 14 запрета и элемент ИЛИ 15:

Блок 4 обслуживания заявок содержит элемент И !6, генератор !7 импульсов, элемент !

8 случайной задержки, триггер 19.

Коммутатор 3 содержит третью группу элементов И 20, первую группу элемментов И 21, вторую. группу элементов И 22. На схеме также обозначены выходы 23 блока обслуживания заявок.

К-й элемент И 21 первой группы и К-й элемент И 22 второй группы реализуют функции соответственно, где Х; — сигнал состояния с выхода i-го блока 4 j-го измерительного канала.

Первый канал 11 имитирует обработку заявок операционной системы, а второй канал в обработку заявок функциональных алгоритмов. В каждом измерительном канале блок 2 имитирует формирование заявок н их очередь, причем интенсивность поступления заявок в первом и втором измерительных каналах соответственно равна интенсивности поступления заявок операционной системы н заявок функциональных алгоритмов. Коммутатор 3 передает поступающие заявки на первый свободный блок 4, причем одноименные блоки 4 обслуживания первого и второго каналов имеют один » тот же закон обслуживания, так как они.имитируют один и тот же прибор, обслуживающий приоритетную или обычную заявку.

Счетчик 6 подсчитывает число обслуженных заявок. Элемент 8 запрета во втором канале служит для реализации относительного приоритета заявок первого канала.

В каждом канале генсратор 9 имитирует входной поток заявок со случайным периодом повторения. Счетчик 10 подсчитывает общее число поступивших заявок. Счетчик 11 через элемент И 12 подсчитывает число заявок, получивших отказ нз-за занятости очереди.

Реверснвный счетчик 13 совместно с элемснтом 14 запрета и элементом ИЛИ !5 имитирует очередь CMO. Генератор 17 импульсов. совместно с элементом 18 случайной задержки, элементом И 16 и триггером 19 имитируют обслуживающий прибор со случайным врсменем обслуживания, причем имитируется М обслуживающих приборов.

В исходном состоянии в реверсивном счетчике !3 записан "О". Пулевой сигнал с, единичного выхода 23 триггера !9 подастся на соответствующие входы коммутаторов 3. Единица с нулевого выхода триггера 19 поддерживает элемент И 16 в открытом состоянии. Генератор 17 импульсов ничего не гелер»руст. так

1142843

Х, Хя Х% Р ЕФ Ез

О О О 1

0 О 1 1 0 0

0 1 0 1

0 1 1 1 0

2S

1 О

0 0

1 0

1 0

О 0

1 0

1 1

1 1 1 0

О 0

Из таблицы видно, что если Х, — Х,= О, 2 т. е. первый канал свободен, то F F = 1 ®

2 . н сигнал с выхода блока 2 через элемент

И 20 поступает на первый выход коммутатора.

Если Х1 = Х, = 1, а Хт = Х = О, Ф . l т.е. первый канал занят, а второй свободен, 4© тоF, F, = Онпз =F, =1н сигнал с выхода блока через элемейт И 20 поступает на второй выход коммутатора.

Коммутирующее устройство работает аналогично н при других соотношениях сигналов состояний.

Импульс от генератора 9, имитирующего входной поток заявок, проходит через откак отсутствует разрептающий потенциал с выходных разрядов реверсивного счетчика 13, прошедший через элемент ИЛИ 15 н коммутар 3.

Работу коммутатора рассмотрим на лрймере

1 2 . дпя М вЂ” 3, тогда функции и и Ра имеют вид

Я ° дпя первого выхода F, Х,, F, Х,, дпя второго выхода F> * Х, Х Р Х, з

Х дпя третьего выхода F X, Х Х,,, F =Х Х Х ! где Х вЂ” сигнал состояния с выхода 23 i-го бло1 ка 4 1-го канала.

Тогда таблица «стчщиости для функций F имеет следувлций вид

15 крытый элемент 14 запрета и поступает иа суммирующий вход реверсивного счетчика 13, который ведет подсчет поступивших заявок, имитируя очередь СМО. Потенциал с выход-. ных разрядов реверсивного счетчика 13 через многовходовый элемент ИЛИ 15, коммутатор

3 поступает на первый свободный блок 4, где сигнал через открытый элемент И 16 запускает генератор 17 . импульсов. Импульс с выхода генератора 17 импульсов поступает на элемент 18, который. задает случайное время обслуживания и одновременно устанавливает триггер 19 в единичное состояние, закрывая тем самым элемент И 16 и запрещая работу генератора 17 импульсов. Кроме того, импульс с выхода генератора 17 поступает на выход и через элемент ИЛИ 7 на вычитающий вход реверсивного счетчика 13 и,тем самым, уменьшает очередь на "1". Задержанный импульс с элемента 18 устанавливает триггер 19 s нулевое состояние, имитируя окончание обслуживания заявки. Сигнал перехода триггера 19 от единичного в нулевое оастояние с выхода 23, пройдя через элемент

ИЛИ S, подсчитывает число обслуженных заявок на счетчике 6.

При заполнении всех мест в очереди сигнал переполнения реверсивного счетчика 13 поступает иа.элемент 14 запрета и элемент И 12.

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

Отличие в работе. второго канала 1 состоит в том, что между выходом блока 2 и входом коммутатора 3 стоит элемент 8 запрета, который управляется снгнаяом с выхода бпока 2 первого канала. Тем самым имитируется относительный приоритет заявок первого канала.

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

6, 10 s 11.

Нредлагаемое устройство позволяет моделировать работу многоканальной СМО.с двумя уровнями приоритета, тогда прототип моделирует работу одноканальной СМО с несколькими жаровнями приоритета.

1142843

4 иг. 2

Рт bn 2(8 и8. Л.Фиг. Ф

ВНИИПИ Заказ 1392 Тиюаж 710 Поднисное

Фипиал ППП "Патент", г. Ужгород, уя. Проектная, 4