Многоканальное устройство приоритета для подключения к общей магистрали

 

Изобретение относится к вычислительной технике и может быть использовано в 5 многомашинных и многопроцессорных вычислительных системах. Цель изобретения - расширение области применения устройства за счет обслуживания запросов с дисциплиной как с относительными, так и с абсолютными приоритетами с учетом времени их ожидания в очереди Достижение цели обеспечивается введением в устройство генераторов 14 импульсов, счетчиков 15, элементов И Тб, 17 и элементов И-НЕ 18, 19 Устройство ггозволяет осуществлять подключение источников информации к общей магистрали с учетом приоритетов каналов и переходить от дисциплины с относительными приоритетами к дисциплине с абсолютными приоритетами, если время ожидания запроса на обслуживание превышает пороговое 1 ил /J- Ц Ё VI 4 Ю 00 О О N3

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

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

РЕСПУБЛИК (51)5 G 06 F 9/46

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 1386994 (21) 4862471/24 (22) 27.08,90 (46) 23.07.92. Бюл, ¹ 27 (72) В.В,Туравинин, В,B.Màæíèêoâ, С.Н.Ази и А.П.Орлов (56) Авторское свидетельство СССР

¹ 1386994, кл, G 06 F 9/46, 1988.

Джейсуол Н. Очереди с приоритетами.—

М.: Мир, 1973, с. 193 — 222, Справочник по цифровой вычислительной технике. / Под ред, Б,Н,Малиновского. — Киев: Техника, 1981, с, 145 и 146. (54) МНОГОКАНАЛЬНОЕ УСТРОЙСТВО

ПРИОРИТЕТА ДЛЯ ПОДКЛЮЧЕНИЯ К ОБЩЕЙ МАГИСТРАЛИ (57) Изобретение относится к вычислительной технике и может быть использовано в... Я2,ц, 1749896 А2 многомашинных и многопроцессорных вычислительных системах. Цель изобретения— расширение области применения устройства за счет обслуживания запросов с дисциплиной как с относительными, так и с абсолютными прйоритетами с учетом времени их ожидания в очереди. Достижение цели обеспечивается введением в устройство генераторов 14 импульсов, счетчиков 15, - элементов И 16, 17 и элементов И-НЕ 18, 19, Устройство позволяет Осуществлять подключение источников информации к общей магистрали с учетом приоритетов каналов и переходить от дисциплины с относительными приоритетами к дисциплине с абсолютными приоритетами, если время ожидания запроса на обслуживание превышает пороI 0BOe. 1 Plfl.

1749896

Изобретение относится к вычислитель- (межпроцессорный) обмен осуществляется ной технике, может ыть п им б ть применено в мно- всоответствии с дисциплиной с относительгомэшинных и мног многопроцессорных ными, а на других этапах — с абсолютными вычислительных системах, с емах, использующих приоритетами. При использовании этой для обмена данными общую магистраль, и 5 дисциплины повышается эквивалентная является усовершенствов н шенствованием изобрете- производительность системы йо сравнению ния по авт. св,, N 1386994, с дисциплиной с относительными приоритеИзвестно многоканальное устройство тами, приоритета для подключения к о ключения к общей маги- Известное устройство не обеспечивает страли, содержэще ржащее сигнальные выходы, 10 реализацию смешанной дисциплины обслуканалы, каждыи из к з которых включает за- живания запросов при захвате общей магипросный вход, элементы И, триггеры, эле- страли. мент задержки, фо ми, формирователь импульсов Цель изобретения — расширение облаи информационный выход, причем в каждом сти применения устройства за счет обслуканалезапросныйвходсоединенспервыми 15 живания запросов с дисциплиной как с входами первого и второго элементов И и относительными приоритетами, так и с абвходом формироват ля ф а еля импульсов выход солютными с учетом времени их ожидания которого соединен с входами сброса перво- в очереди.

1 го и второго триггеров, ну ров, нулевой выход пер- В многоканальное устройство приоривого триггера соединен соединен с вторым входом 20 тета для подключения к общей магистрали, первого элемента И, выход которогосоеди- дополнительно введены в первый канал— нен с вторым входом второго элемента И и генератор импульсов, счетчик и элемент И, единичным входом и р ервого триггера еди- в М-й канал — элемент И и два элемента ничный выход которого соединен с третьим И-НЕ, в К-й канал (K = 2 ... М-1) — генератор входом второго л орого элемента И, выход которого 25 импульсов, счетчик, два элемента И и два сбединен с входом элемента задержки, вы- элемента И-НЕ, причем в Н-м канале ( ход которого соединен с первым входом ... M-1) выход генератора импульсов соедитретьего элемента И, выход которого соеди- нен с первым входом четвертого элемента нен с единичным входом второго триггера, И, второй вход которого соединен с запросединичный выходкоторого является инфор- 30 ным входом устройства и входом сброса мационным выходом, н л о ом, нулевой выход второ- счетчика, счетный вход которого соединен с го триггера соединен е инен с вторым входом выходом четвертого элемента И, в П-м канатретьего элемента И и вторым сигнальным ле (П = 2...М) выход первого элемента И-НЕ выходом устроиства, и с ва, первый сигнальный соединен с первым входом второго элеменвыход устройства соединен с нулевыми вы- 35 та И-НЕ, второй вход которого соединен с ходами первых тригг р р ггеров всех каналов, тре- единичным выходом второго триггера, а вытий сигнальный выход устройства соединен ход — с первым входом пятого элемента И, с входами сброса вторых триггеров всех ка- второй вход которого соединен с запросным налов. Устройство обеспечивает приоритет- входом устройства, а выход — с входом форный доступ к общей магистрали (OM) 40 мирователя импульсов, выходсчетчика Н-го источников информации для передачи сооб- канала (Н = 1...М-1) соединен с Н-м входом щений потребителям независимо от дли- первого элемента И-НЕ каждого из последутельности ожидания этих сообщений ющих каналов. (запросов на обслуживание) в очереди на На чертеже изображена структурная

45 схема устройства.

О е случаев в вычислительОднако в ряде сл ч Устройство содержит сигнальные выхоных системах реального времени целесооб- ды 1 — 3, М каналов 4, в состав которых входят разно применять такую приоритетную запросные входы 5, элементы И 6 — 8, триггедисциплину, при которой важность запроса ры 9 и 10, элементы 11 задержки, формироскачком возрастает, когда время его ожида- 50 ватели 12 импульсов, информационные ния достигло порогового значения, и проис- выходы 13, генераторы 14, счетчик 15, элеходит прерывание в обслуживании менее менты И 16 и 17, элементы И-HE 18 и 19. приоритетного запроса для того, чтобы об- Устройство работает следующим обраслужить более приоритетный запрос, время зом, ожидания которого достигло порогового 55 В исходном состоянии триггеры 9 и 10 и значения (прерывание более приоритетных счетчики 15 всех каналов находятся в нулезапросов менее приоритетными не проис- вом состоянии, на входы 5 всех каналов 4 от ходит), Такая дисциплина является смешан- соответствующих источников информации ной, поскольку на отдельных этапах работы (например, ЭВМ) поступают сигналы логивычислительной си ной системы Måæмашинной ческого нуля, что обуславливает наличие

1749896 сигналов логической единицы (высоких уровней) на первом и втором сигнальных выходах устройства и сигналов логического нуля на информационных выходах 13 каналов (ЭВМ могут выдавать информацию в ОМ при наличии единичных сигналов на выходах 13 соответствующих каналов) и третьем сигнальном выходе 3 устройства, на выходах счетчиков 15 установлены сигналы логической единицы.

Объединение выходов элементов устройства на первом и втором сигнальных выходах устройства реализует функцию

"Проводное И", а на третьем сигнальном выходе — "Проводное ИЛИ".

В случайные моменты времени ЭВМ заносят в свои ячейки буферной памяти сообщения, предназначенные для передачи через общую магистраль (ОМ). Каждый источник информации подключен через запросный вход 5 и информационный выход

13 к соответствующему каналу 4 (источники информации и OM не показаны). При появлении в ячейке буферной памяти какой-либо

ЭВМ сообщения на входе 5 соответствующего канала 4 устанавливается сигнал логической единицы (этот сигнал исчезает при освобождении соответствующей ячейки памяти).

Далее рассмотрим работу К-ro канала 4 (К = 2 ... М-1), поскольку их большинство в устройстве, а для первого и последнего каналов есть особенности, вызванные тем, что первый канал является самым приоритетным (приоритетность каналов уменьшается с увеличением номера канала), т.е, его работу не может прервать другой канал, поэтому он не содержит элементы 17 — 19, предназначенные в других каналах для организации прерывания канала, а последний канал является наименее приоритетным, т,е. он не может прерывать другие каналы, поэтому он не содержит элементы 14 — 16, предназначенные в других каналах для формирования сигнала на прерывание менее приоритетных каналов, когда время ожидания сообщения для передачи через ОМ достигло порогового значения.

Единичный сигнал с запросного входа 5 в рассматриваемом (например, втором) канале, пройдя через открытый элемент И 6, устанавливает триггер 9 в единичное состояние, что приводит к установлению на первом сигнальном выходе устройства сигнала логического нуля и, следовательно, закрываются элементы И 6 всех каналов 4 (т.е. запросы от ЭВМ на захват ОМ с данного момента времени на триггерах 9 каналов не фиксируют). Этот же сигнал (с запросного входа 5) открывает элемент И 16, через ко10

40 щения, она установит на запросном входе 5 своего канала сигнал логического нуля. По отрицательному перепаду уровня Сигнала

45 сов в данном канале 4 формирует одиночный импульс, который устанавливает

55

25 торый на счетчик 15 начинают поступать импульсы с генератора 14 импульсов, отсчитывая время ожидания сообщения в очереди на передачу через ОМ (в последнем канале этого не происходит, так как он наименее приоритетный), После установления на единичном выходе триггера 9 сигнала логической едини цы и до момента пропадания единичного сигнала на выходе элемента И 6 на выходе элемента И 7 устанавливается сигнал логической единицы, который, пройдя через элемент 11 задержки и открытый элемент И 8, устанавливает триггер 10 в единичное состояние. Задержка нэ элементе 11 задержки в каждом канале, начиная с первого. увеличивается по сравнению с предыдущим каналом на величину интервала времени большую, чем необходимо для прохождения сигнала по элементам 8 и 10 и сигнальному второму выходу . устройства между двумя наиболее удаленными каналами 4, При этом исключается возможность одновременного подключения нескольких каналов к ОМ.

Сигнал с единичного выхода трйггера 10 через информационный выход 13 канала 4 сигнализирует соответствующей ЭВМ о том, что ОМ захвачена и можно передавать информацию. Одновременно сигнал логического нуля с нулевого выхода триггера 10 через сигнальный второй выход устройства закрывает во всех каналах 4 элементы И 8, и если одновременно осуществлялись попытки захватить ОМ другими каналами, у которых приоритет ниже (больше время задержки сигнала на элементе 11), чем у данного канала 4, то они (попытки) блокируются. После того, как 3ВМ, подключенная к данному каналу 4, закончит передачу сообна запросном входе 5 происходит обнуление счетчика 15 и формирователь 12 импультриггеры 9 и 10 этого канала (э через сигнальный выход 3 устройства триггерь. 9 в менее приоритетных каналах, где осуществляется одновременная попытка захвата

ОМ) в нулевое состояние, Если же при поступлении сигнала на запросный вход 5 второго канала 4 ОМ была занята менее приоритетным каналом (кэнал с большим номером, например последним) и к моменту времени Т = Т + Тп (где Т1 — время поступления сообщения в ячейку буферной памяти второй 3ВМ; Тп — порогое время ожидания сообщения в очереди на передачу, после которого должно прерваться обслуживание

1749896

50 любого менее приоритетного сообщения) последний канал не освободил ОМ, то в этот момент на выходе счетчика 15 второго канала появится нулевой сигнал, который поступит в последний канал на второй вход элемента И-НЕ 18, вызывая íà его выходе, т.е. на первом входе элемента И-НЕ 19, сигнал логической единицы, Поскольку на втором входе элемента И-НЕ 19 также установлен сигнал логической единицы (поскольку последний канал захватил ОМ и его триггер 10 находится в единичном состоянии), то на выходе элемента И-НЕ 19 появится нулевой сигнал, который обеспечит на выходе элемента И 17 нулевой сигнал, при появлении которого формирователь 12 импульсов сформирует одиночный импульс, который установит триггеры 9 и 10 в нулевое состояние, и вновь начнется состязание каналов на захват ОМ, в результате которого второй канал захватит ОМ (так как он более приоритетный, чем последний), а ЭВМ, подключенная к последнему каналу, вынуждена прервать выдачу сообщения в ОМ, так как на информационном выходе 13 ее канала появится нулевой сигнал, После того, как вторая ЭВМ закончит передачу сообщения и освободит ОМ (если за это время не появится более приоритетный запрос), последняя ЭВМ захватит QM и продолжит передачу прерванного сообщения. Далее работа устройства повторяется, Поскольку первый канал является самым приоритетным, то его сеансы передачи сообщений не могут быть прерваны другими каналами, Таким образом, предлагаемое.устройство позволяет реализовать смешанную дисциплину обслуживания запросов на захват

OM с учетом приоритетов источников информации и времени ожидания сообщений в очереди на передачу через ОМ.

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

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

1 5 /о

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

Многоканальное устройство приоритета для подключения к общей магистрали по авт. св. N 1386994, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет обслуживания запросов с дисL,èïëèíoé как с относительными приоритетами, так и с абсолютными с учетом времени их ожидания в очереди, в него дополнительно введены в первый канал— генератор импульсов, счетчик и элемент И, в М-й канал — элемент И и два элемента

И-НЕ, в К-й канал (K = 2...М-1) — генератор импульсов, счетчик, два элемента И и два элемента И-НЕ,,причем в Н-м (Н = 1...М-1) канале выход генератора импульсов соединен с первым входом четвертого элемента

И, второй вход которого соединен с запросным входом устройства и входом сброса счетчика, счетный вход которого соединен с выходом четвертого элемента И, в П-м канале (П 2...М) выход первого элемента И-НЕ соединен с первым входом второго элемента И-НЕ, второй вход которого соединен с единичным выходом второго триггера, а выход — с первым входом пятого элемента И, второй вход которого соединен с запросным входом устройства, а выход — с входом формирователя импульсов, выход счетчика Н-ro канала (Н=1...М-1) соединен с Н-м входом первого элемента И-Н Е каждого из последующих каналов,