УСТРОЙСТВО ОБСЛУЖИВАНИЯ РАЗНОПРИОРИТЕТНЫХ ЗАПРОСОВ АБОНЕНТОВ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ Российский патент 2002 года по МПК G06F9/46 

Заявленное техническое решение относится к области вычислительной техники и может быть применено в системах обмена данными.

Известны устройства обслуживания запросов. Обслуживание - совокупность действий вычислительной системы, включающая выборку запроса из очереди, выделение ему ресурса, а также проведение завершающих операций. Запрос - посылка сигнала, инициирующего ответ. Входное сообщение, содержащее требование к системе на выделение ресурса. - см. , например, авт.св. СССР 1441398 "Многоканальное устройство динамического приоритета" МПК G 06 F 9/46, опубликованное 30.11.88, Бюл. 44; авт. св. СССР 1562912 "Многоканальное устройство с динамическим изменением приоритета" МПК G 06 F 9/46, опубликованное 07.05.90, Бюл. 17, авт.св. СССР 1522206 "Устройство динамического приоритета", G 06 F 9/46, опубликованное 15.11.89, Бюл. 42.

Известные аналоги содержат блоки анализа приоритетов. Приоритет - число, предписанное задаче, процессу или операции, определяющее очередность их выполнения или обслуживания. Чем меньше число, тем выше уровень приоритета, и блоки наращивания приоритета. Общим недостатком аналогов является невысокая вероятность своевременного обслуживания запросов низшего приоритета.

Из известных наиболее близким аналогом (прототипом) по своей технической сущности заявленному устройству является устройство (первый вариант) см. авт. св. РФ 2140666 "Способ обслуживания запросов пользователей вычислительной системы и устройство его реализующее" МПК G 06 F 9/46, опубликованное 27.10.99, Бюл. 30.

Устройство-прототип включает N абонентских блоков, где N≥2, счетчик, элемент И, генератор тактовых импульсов, делитель, N-входовый элемент ИЛИ-НЕ, мультиплексор, инвертор. При этом счетный вход счетчика соединен с выходом элемента И, а второй вход элемента И подключен к выходу генератора тактовых импульсов и входу делителя. Выход делителя соединен с тактовыми входами N абонентских блоков. Запросные входы и K-разрядные входы, где К≥2 - разрядность кода максимального времени ожидания обслуживания запросов, "Код максимального времени ожидания" N абонентских блоков являются соответствующими запросными входами и K-разрядными входами "Код максимального времени ожидания" устройства, N входов N-входового элемента ИЛИ-НЕ подключены к выходам "Превышение" соответствующих N абонентских блоков, а выход N-входового элемента ИЛИ-НЕ подключен к входам "Запрет" N абонентских блоков. N информационных входов мультиплексора соединены с первыми сигнальными выходами соответствующих N абонентских блоков. J, где J=]log₂N[, выходов "Код абонента" счетчика подключены к соответствующим J адресным входам мультиплексора и одновременно являются соответственно J выходами "Код абонента" устройства. Выход мультиплексора подключен к входу инвертора и одновременно является разрешающим выходом устройства. Выход инвертора соединен с первым входом элемента И, а вход сброса счетчика является опросным входом устройства. Входы "Обнуление" N абонентских блоков являются соответствующими входами "Обнуление" устройства.

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

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

Однако устройство-прототип имеет недостатки: относительно невысокую надежность и относительно низкое быстродействие, которые обусловлены большим количеством составляющих устройство-прототип элементов.

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

Поставленная цель в заявленном устройстве обслуживания разноприоритетных запросов абонентов вычислительной системы достигается тем, что в известном устройстве обслуживания запросов абонентов вычислительной системы, содержащем N абонентских блоков, где N≥2, генератор тактовых импульсов, запросные входы и K-разрядные входы "Код максимального времени ожидания", где К≥1 - разрядность кода максимального времени ожидания обслуживания запроса, N абонентских блоков являются соответствующими запросными входами и K-разрядными входами "Код максимального времени ожидания" устройства, входы "Обнуление" N абонентских блоков являются соответствующими входами "Обнуление" устройства, дополнительно введены первый и второй N-входовые элементы И-НЕ, первый и второй шифраторы приоритетов, элемент ИЛИ, элемент И-НЕ и селектор-мультиплексор. N входов первого и второго N-входовых элементов И-НЕ подключены к соответствующим N инверсным входам соответственно первого и второго шифраторов приоритетов. Выходы первого и второго N-входовых элементов И-НЕ подключены соответственно к второму и первому входам элемента ИЛИ n-ые инверсные входы первого и второго шифраторов приоритетов, где n=l,2,...N, подключены соответственно к первому и второму сигнальным выходам (N+1)-n-го абонентского блока. Выход элемента ИЛИ подключен к второму входу элемента И-НЕ. Первый вход элемента И-НЕ является опросным входом устройства, а выход элемента И-НЕ подключен к инверсному разрешающему входу селектора-мультиплексора и является разрешающим выходом устройства. Управляющий вход селектора-мультиплексора подключен к второму входу элемента ИЛИ. J инверсных выходов первого и второго шифраторов приоритетов, где J=]log₂N[, подключены к соответствующим J входам соответственно второй и первой групп входов селектора-мультиплексора. Выход генератора тактовых импульсов соединен с тактовыми входами всех абонентских блоков, а J выходов селектора-мультиплексора являются соответственно J выходами "Код подлежащего обслуживанию абонента" устройства.

Абонентский блок состоит из счетчика, инвертора, трехвходового элемента И. Инверсный вход разрешения счета счетчика является запросным входом абонентского блока и подключен к второму входу трехвходового элемента И и входу инвертора. К информационных входов счетчика являются K-разрядным входом "Код максимального времени ожидания" абонентского блока, а вход сброса счетчика является входом "Обнуление" абонентского блока. Инверсный выход счетчика подключен к первому входу трехвходового элемента И и является первым сигнальным выходом абонентского блока. Третий вход трехвходового элемента И является тактовым входом абонентского блока, а выход трехвходового элемента И подключен к счетному входу счетчика. Выход инвертора является вторым сигнальным выходом абонентского блока.

Более высокое, по сравнению с устройством-прототипом, быстродействие заявленного устройства достигается за счет того, что время задержки появления результата работы после выставления сигнала на опросном входе устройства определяется только совокупным временем задержки срабатывания элемента И-НЕ и селектора-мультиплексора, коммутирующего на выход заявленного устройства код подлежащего обслуживанию запроса. При этом, в устройстве-прототипе после выставления сигнала на опросном входе инициируются последовательный опрос всех АБ с целью контроля наличия в них сигналов запросов. Далее, в устройстве-прототипе производится определение подлежащего обслуживанию запроса и последующая коммутация на его выход кода подлежащего обслуживанию запроса.

Проведенный заявителем анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностями признаков, тождественных всем признакам заявленного устройства обслуживания разноприоритетных запросов абонентов вычислительной системы, отсутствуют. Следовательно, заявленное изобретение соответствует условию патентоспособности "Новизна".

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

Заявленные объекты изобретения поясняются чертежами, на которых:
на фиг.1 - устройство обслуживания разноприоритетных запросов абонентов вычислительной системы;
на фиг.2 - абонентский блок;
на фиг.3 - структура вычислительной системы;
на фиг.4 - размещение сигналов запросов в очереди второго порядка;
на фиг.5 - порядок переноса запросов из очереди второго порядка в очередь первого порядка.

Устройство (см. фиг.1) состоит из генератора тактовых импульсов 2, первого и второго N-входовых элементов И-НЕ 7, 10, первого и второго шифраторов приоритетов 8, 9, элемента ИЛИ 4, элемента И-НЕ 5, селектора-мультиплексора 6, N абонентских блоков (АБ) 1₁-1_N (схема АБ изображена на фиг.2).

Элементы соединены между собой следующим образом (см. фиг.1). Выход генератора тактовых импульсов 2 подключен к тактовым входам 14 каждого из N абонентских блоков. Запросные входы 11 и K-разрядные входы 12 "Код максимального времени ожидания" N абонентских блоков являются соответствующими запросными входами и K-разрядными входами "Код максимального времени ожидания" устройства. Входы "Обнуление" 13 N абонентских блоков являются соответствующими входами "Обнуление" устройства. N входов первого и второго N-входовых элементов И-НЕ 7, 10 подключены к соответствующим N инверсным входам соответственно первого и второго шифраторов приоритетов 8, 9. Выходы первого и второго N-входовых элементов И-НЕ 7, 10 подключены соответственно к второму и первому входам элемента ИЛИ 4. n-ые инверсные входы первого и второго шифраторов приоритетов 8, 9, где n=1,2,...N, подключены соответственно к первому 15 и второму 16 сигнальным выходам (N+1)-n-гo абонентского блока. Выход элемента ИЛИ 4 подключен к второму входу элемента И-НЕ 5. Первый вход элемента И-НЕ 5 является опросным входом 17 устройства, а выход элемента И-НЕ 5 подключен к инверсному разрешающему входу селектора-мультиплексора 6 и является разрешающим выходом 18 устройства. Управляющий вход селектора-мультиплексора 6 подключен к второму входу элемента ИЛИ 4. J инверсных выходов первого и второго шифраторов приоритетов 8, 9, подключены к соответствующим J входам соответственно второй и первой групп входов селектора-мультиплексора 6, а J выходов селектора-мультиплексора 6 являются соответственно J выходами 19 "Код подлежащего обслуживанию абонента" устройства.

Генератор тактовых импульсов 2 предназначен для выработки синхронизирующей последовательности импульсов и может быть построен по любой известной схеме. См., например, В.Л. Шило "Популярные цифровые микросхемы", М.: "Радио и связь", 1987, с. 50-53.

Шифраторы приоритетов 8 и 9 предназначены для преобразования сигнала низкого уровня на одном из их входов в двоичный код на выходе, причем преобразование осуществляется с учетом приоритетов сигналов, соответствующих номерам входов. Схема реализации шифраторов приоритетов известна. См., например, в книге: В.Л. Шило "Популярные цифровые микросхемы", М.: "Радио и связь", 1987, с. 147-148.

Селектор-мультиплексор 6 предназначен для коммутации одной из двух J-разрядных групп входов на выход. Схемы реализации такого селектора-мультиплексора известны. См., например, в книге: В.Л. Шило "Популярные цифровые микросхемы", М.: "Радио и связь", 1987, с. 139-140.

Абонентские блоки 1₁-1_N предназначены для контроля поступления сигналов запросов, контроля оставшегося времени ожидания, а также выработки управляющих сигналов по истечении установленного времени ожидания для каждого запроса.

Абонентский блок может быть реализован в различных вариантах. В частности, его схема, показанная на фиг.2, содержит счетчик 1.1, инвертор 1.2 и трехвходовый элемент И 1.3.

Инверсный вход разрешения счета счетчика 1.1 является запросным входом 11 абонентского блока и подключен к второму входу трехвходового элемента И 1.3 и входу инвертора 1.2. К информационных входов счетчика 1.1 являются К-разрядным входом "Код максимального времени ожидания" 12 абонентского блока, а вход сброса счетчика 1.1 является входом "Обнуление" 13 абонентского блока. Инверсный выход счетчика 1.1 подключен к первому входу трехвходового элемента И 1.3 и является вторым сигнальным выходом 16 абонентского блока. Третий вход трехвходового элемента И 1.3 является тактовым входом 14 абонентского блока, а выход трехвходового элемента И 1.3 подключен к счетному входу счетчика 1.1. Выход инвертора 1.2 является вторым сигнальным выходом 16 абонентского блока.

Счетчик 1.1 предназначен для счета поступающих на его вход импульсов (счетных импульсов), выработки управляющего сигнала, определяемого кодом начального заполнения по входам D и периодом следования тактовых импульсов, то есть является настраиваемым таймером. Описание работы и схема такого счетчика известны и приведены, например, в книге: П.П. Мальцев, Н.С. Долидзе и др. , "Цифровые интегральные микросхемы: справочник", -М.: "Радио и связь", 1994, с. 64-65.

Устройство работает следующим образом. Перед началом работы устройства по группе K-разрядных входов "Код максимального времени ожидания" 12₁-12_N на информационные входы счетчиков 1.1₁-1.1_N абонентских блоков поступают коды, задающие максимальное время ожидания обслуживания запросов, обеспечивая инициализацию счетчиков. Наименьшему времени ожидания соответствует наибольший код, являющийся дополнением до максимального числа, представимого в K-разрядном коде.

В начальный период, когда запросы на обслуживание отсутствуют, на всех запросных входах 11 абонентских блоков установлены низкие логические уровни. Трехвходовый элемент И 1.3 всех АБ закрыт, тактовые импульсы от генератора тактовых импульсов 2 на счетные входы С счетчиков 1.1 АБ не поступают. Со стороны вычислительного ресурса отсутствует сигнал об освобождении ресурса (на опросном входе 17 установлен низкий логический уровень). На вторых и первых сигнальных выходах АБ 1₁-1_N установлены высокие логические уровни. Соответственно, на выходах первого и второго N-входовых элементов И-НЕ 7, 10 установлены низкие логические уровни. Выходы селектора-мультиплексора 6 разомкнуты, поскольку на инверсном разрешающем входе по цепи элемент ИЛИ 4, элемент И-НЕ 5 установлен высокий логический уровень. Система готова к работе и ожидает сигналы запросов, вырабатываемые абонентами вычислительной системы (см. фиг.3).

При возникновении потребности в вычислительном ресурсе, абонентами вычислительной системы генерируются сигналы запросов, которые поступают на устройство обслуживания запросов и помещаются в очередь второго порядка. Сигналом запроса от абонента считается сигнал высокого уровня, установленный на запросном входе 11 соответствующего АБ. При этом, на вторых сигнальных выходах 16 этих АБ через инверторы 1.2 установятся сигналы низкого уровня. Совокупность сигналов низкого уровня на вторых сигнальных выходах 16 АБ образует очередь второго порядка. Положение сигнала запроса в очереди второго порядка определяется его начальным приоритетом: сигнал запроса, поступивший от абонента с наименьшим номером, обладает наивысшим приоритетом (см. фиг. 4). На счетные входы С счетчиков 1.1 АБ, содержащих сигналы запросов, поступают импульсы от генератора тактовых импульсов 2 по цепи: тактовые входы 14 АБ, открытые трехвходовые элементы И 1.3 АБ. Счетчики 1.1 выполняют функцию таймеров, которые контролируют истечение допустимого времени нахождения запросов в очереди второго порядка путем суммирования поступающих на их счетный вход С тактовых импульсов и формируют сигнал переполнения на выходах через установленный интервал времени, определяемый кодами начального заполнения счетчиков и частотой тактовых импульсов.

Сигналы с вторых сигнальных выходов 16₁-16N АБ 1₁-1_N поступают на инверсные входы второго шифратора приоритетов 9, обеспечивающего преобразование сигналов запросов в J-разрядный код, соответствующий номеру АБ с учетом его приоритета. При этом, сигнал с второго сигнального выхода первого АБ поступает на N-ый инверсный вход второго шифратора приоритетов 9, сигнал с второго сигнального выхода второго АБ поступает на (N-1)-ый инверсный вход второго шифратора приоритетов 9, сигнал с второго сигнального выхода n-го АБ поступает на (N+1)-n-ый инверсный вход второго шифратора приоритетов 9, сигнал с второго сигнального выхода N-го АБ поступает на первый инверсный вход второго шифратора приоритетов 9. Указанный способ подключения вторых сигнальных выходов 16₁-16_N АБ обусловлен тем, что выходы второго шифратора приоритетов 9 инверсные, то есть для получения на его выходе кода, соответствующего АБ с наименьшим номером из числа тех АБ, на вторых сигнальных выходах 16 которых установлены низкие логические уровни (сигналы запросов), следует подключить вторые сигнальные выходы АБ к входам второго шифратора приоритетов 9 в обратном порядке. При наличии в очереди второго порядка хотя бы одного сигнала запроса на выходе второго N-входового элемента И-НЕ 10 установится высокий уровень.

По мере освобождения вычислительного ресурса вырабатывается сигнал высокого уровня, который поступает на опросный вход устройства 17 и, далее на первый вход элемента И-НЕ 5. При наличии хотя бы одного запроса в очереди второго порядка на выходе элемента И-НЕ 5 установится сигнал низкого уровня, который разрешит трансляцию данных селектору-мультиплексору 6. На селективном входе S селектора-мультиплексора 6 установлен низкий уровень (на первых сигнальных выходах всех АБ высокий уровень), следовательно, на выходы "Код подлежащего обслуживанию абонента" 19 селектора-мультиплексора 6 будет скоммутирован код, поступивший на входы A₁-A_J первой группы входов селектора-мультиплексора 6 и соответствующий наименьшему номеру АБ, содержащему сигнал запроса из очереди второго порядка.

После удовлетворения потребности абонента в вычислительном ресурсе абонент снимает сигнал запроса с запросного входа 11 соответствующего АБ, и производит сброс счетчика 1.1 соответствующего АБ по входу "Обнуление" 13. При этом на первом и втором сигнальных выходах 15 и 16 соответствующих АБ будут высокие уровни.

В случае, если один или несколько запросов в результате создавшейся очереди достигли максимального времени ожидания, происходит переполнение счетчиков 1.1 соответствующих АБ, формирование на их инверсных выходах переполнения а следовательно, и на первых сигнальных выходах 15 сигналов низкого уровня, что соответствует переносу запросов в очередь первого порядка на места, соответствующие их приоритетам (см. фиг.5). в целях их дальнейшего внеочередного, по отношению к очереди второго порядка, обслуживания. При этом запираются трехвходовые элементы И 1.3, запрещая поступление тактовых импульсов на счетные входы С счетчика 1.1. Совокупность сигналов низкого уровня на первых сигнальных выходах 15 АБ образует очередь первого порядка. Обслуживание запросов из очереди первого порядка осуществляется с учетом их начальных приоритетов. При этом формирование кода, соответствующего наименьшему номеру АБ, содержащему сигнал запроса из очереди первого порядка, осуществляется первым шифратором приоритетов 8 тем же способом, что и из очереди второго порядка. При наличии запроса в очереди первого порядка их внеочередное, по отношению к запросам из очереди второго порядка, обслуживание обеспечивается сигналом высокого уровня на выходе первого N-входового элемента И-НЕ 7, который, поступая на селективный вход S селектора-мультиплексора 6, коммутирует на выходы "Код подлежащего обслуживанию абонента" 19 сигналы по группе входов B₁-B_J. Сигнал высокого уровня на выходе первого N-входового элемента И-НЕ 7 будет до тех пор, пока в очереди первого порядка есть хотя бы один запрос.

После освобождения ресурса, выделенного в интересах очередного запроса абонента из очереди первого порядка (с истекшим временем ожидания) абонент снимает сигнал запроса с запросного входа 11 соответствующего АБ и производит сброс счетчика 1.1 соответствующего АБ по входу "Обнуление" 13, что установит высокий уровень на выходе счетчика 1.1, устанавливая тем самым на первом и втором сигнальных выходах 15 и 16 этого АБ высокие уровни, что позволит устройству после выполнения всех запросов с истекшим временем ожидания перейти к обслуживанию вновь поступивших, либо ждущих своей очереди запросов в порядке, определенном логикой работы устройства.

Изобретение относится к области вычислительной техники и может быть применено в системах обмена данными. Техническим результатом является быстродействие и надежность работы устройства. Устройство содержит N абонентских блоков, генератор тактовых импульсов, два N-входовых элемента ИЛИ-НЕ, два шифратора приоритетов, элемент ИЛИ, элемент И-НЕ, селектор-мультиплексор. 1 з.п. ф-лы, 5 ил.

1. Устройство обслуживания разноприоритетных запросов абонентов вычислительной системы, содержащее N абонентских блоков, где N≥2, генератор тактовых импульсов, запросные входы и К-разрядные входы "Код максимального времени ожидания", где К≥2 - разрядность кода максимального времени ожидания обслуживания запроса, N абонентских блоков являются соответствующими запросными входами и К-разрядными входами "Код максимального времени ожидания" устройства, входы "Обнуление" N абонентских блоков являются соответствующими входами "Обнуление" устройства, отличающееся тем, что дополнительно введены первый и второй N-входовые элементы И-НЕ, N входов которых подключены к соответствующим N инверсным входам соответственно первого и второго шифраторов приоритетов, а выходы первого и второго N-входовых элементов И-НЕ подключены соответственно к второму и первому входам элемента ИЛИ, n-е инверсные входы первого и второго шифраторов приоритетов, где n= 1,2, . . . , N, подключены соответственно к первому и второму сигнальным выходам (N+1) n-го абонентского блока, выход элемента ИЛИ подключен к второму входу элемента И-НЕ, первый вход которого является опросным входом устройства, выход элемента И-НЕ подключен к инверсному разрешающему входу селектора-мультиплексора и является разрешающим выходом устройства, управляющий вход селектора-мультиплексора подключен к второму входу элемента ИЛИ, J инверсных выходов первого и второго шифраторов приоритетов, где J= ] log₂N[, подключены к соответствующим J входам соответственно второй и первой групп входов селектора-мультиплексора, выход генератора тактовых импульсов соединен с тактовыми входами всех абонентских блоков, J выходов селектора-мультиплексора являются соответствующими J выходами "Код подлежащего обслуживанию абонента" устройства. 2. Устройство по п. 1, отличающееся тем, что абонентский блок состоит из счетчика, инверсный вход разрешения счета которого является запросным входом абонентского блока и подключен к второму входу трехвходового элемента И и входу инвертора, К информационных входов счетчика являются К-разрядным входом "Код максимального времени ожидания" абонентского блока, а вход сброса счетчика является входом "Обнуление" абонентского блока, инверсный выход счетчика подключен к первому входу трехвходового элемента И и является первым сигнальным выходом абонентского блока, третий вход трехвходового элемента И является тактовым входом абонентского блока, а выход трехвходового элемента И подключен к счетному входу счетчика, выход инвертора является вторым сигнальным выходом абонентского блока.