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

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

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

Описание изобретения к патенту

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

Известно устройство для приоритетного подключения источников информации к магистрали /Авторское свидетельство СССР №1117638, G06F 9/46/, содержащее триггеры, элементы НЕ, элементы задержки, И-ИЛИ, одновибраторы. Недостатком устройства является большое количество оборудования и отсутствие возможности реализации циклической дисциплины обслуживания запросов.

Известно многоканальное устройство приоритета /Авторское свидетельство СССР №1285475, G06F 9/46/, содержащее генератор импульсов и М каналов, каждый из которых содержит триггер, счетчик, дешифратор, элемент НЕ, формирователь импульсов, переключатель, элемент задержки и элемент ИЛИ. Недостатком устройства является отсутствие возможности реализации циклической дисциплины обслуживания запросов.

Наиболее близким по технической сущности к заявляемому устройству является выбранное в качестве прототипа устройство для приоритетного обслуживания запросов /Авторское свидетельство СССР №1591016, G06F 9/46/, содержащее генератор импульсов, элементы И, счетчики, схему сравнения, регистр, элементы НЕ, элементы ИЛИ, элемент задержки, дешифратор, формирователь импульсов, группу кодовых входов, группу входов запросов, группу выходов разрешения и группу элементов И, причем каждый из выходов разрешения устройства соединен с соответствующим входом первого элемента ИЛИ, выход которого соединен со входом элемента задержки и входом сброса первого счетчика, выход формирователя импульсов соединен с входом первого элемента НЕ, каждый из входов запросов устройства соединен с первым входом соответствующего элемента И группы элементов И и с соответствующим входом второго элемента ИЛИ, выход которого соединен со входом управления генератора импульсов, выход которого соединен с первыми входами первого элемента И и второго элемента И, второй вход которого соединен с выходом элемента задержки, а выход - со счетным входом первого счетчика, группа выходов которого соединена с первой группой входов схемы сравнения, вторая группа входов которой соединена с группой выходов регистра, группа входов которого является группой кодовых входов устройства, выход схемы сравнения соединен с входом формирователя импульсов, вход элемента задержки соединен со входом второго элемента НЕ, выход которого соединен со вторым входом первого элемента И, выход которого соединен со счетным входом второго счетчика, группа выходов которого соединена с группой входов дешифратора, каждый из выходов которого соединен со вторым входом соответствующего элемента И группы элементов И, выход которого является соответствующим выходом разрешения устройства, выход первого элемента НЕ соединен с третьими входами всех элементов И группы элементов И.

Устройство работает следующим образом. В исходном состоянии первый и второй счетчики находятся в нулевом состоянии, на регистре через группу кодовых входов установлен код, соответствующий длительности кванта обслуживания запросов. В случайные моменты времени от абонентов на соответствующие входы запросов поступают запросы на обслуживание в виде единичных сигналов (высоких уровней напряжений), при этом на выходе второго элемента ИЛИ появляется единичный сигнал, запускающий генератор импульсов, первый импульс с выхода которого формируется через время не меньшее, чем время срабатывания элемента И группы элементов И, первого элемента ИЛИ, второго элемента НЕ и первого элемента И, что обеспечивает запрет прохождения этого импульса через первый элемент И на счетный вход второго счетчика в случае, если запрос поступил от нулевого абонента и, т.к. на нулевом выходе дешифратора установлен единичный сигнал и на выходе первого элемента НЕ также установлен единичный сигнал, срабатывает нулевой элемент И группы элементов И, на выходе которого появится единичный сигнал, который через первый элемент ИЛИ и второй элемент НЕ закроет первый элемент И. В этом случае единичный сигнал с выхода нулевого элемента И группы через соответствующий выход разрешения поступает нулевому абоненту, сигнализируя о том, что общий ресурс находится в его распоряжении (и будет принадлежать ему до тех пор, пока не нулевом выходе разрешения имеется единичный сигнал). Этот сигнал через первый элемент ИЛИ своим передним фронтом обнуляет первый счетчик, а через элемент задержки открывает второй элемент И, через который импульсы с выхода генератора импульсов поступают на счетный вход первого счетчика, увеличивая значение кода на его группе выходов и, когда оно станет равным значению кода кванта времени обслуживания, на выходе схемы сравнения появится единичный сигнал, передним фронтом которого будет запущен формирователь импульсов, который выдает единичный импульс, во время действия которого на выходе первого элемента НЕ будет присутствовать нулевой сигнал, что вызовет появление нулевого сигнала на выходе нулевого элемента И группы (т.е. прерывание в обслуживании нулевого абонента). При этом через первый элемент ИЛИ, задержки и второй элемент И закроется счетный вход первого счетчика, а через первый элемент ИЛИ, второй элемент НЕ откроется первый элемент И и очередной импульс с выхода генератора импульсов установит второй счетчик в следующее состояние (причем при достижении этим счетчиком максимального состояния, равного коду на единицу меньшему количества абонентов, очередным счетным импульсом он устанавливается в нулевое состояние), на первом выходе дешифратора появится единичный сигнал и, если от первого абонента на соответствующем входе запроса имеется сигнал запроса, начнется обслуживание аналогично вышеописанному первого абонента (длительность импульса, формируемого формирователем импульсов рассчитывается так, чтобы после появления на первом выходе дешифратора единичного сигнала, импульс с выхода формирователя импульсов закончился и при этом элементы И группы открываются по третьим входам). Если обслуживание данного абонента закончилось, то на соответствующем входе запроса появится нулевой сигнал. Для нормальной работы устройства интервал между импульсами, формируемыми генератором импульсов, должен быть не менее чем суммарное время срабатывания первого элемента И, второго счетчика, дешифратора, элемента И группы, первого элемента ИЛИ, второго элемента НЕ и первого элемента И, т.е. не менее чем 8 Т_Лэ , где Т_Лэ - время срабатывания одного логического элемента типа И или ИЛИ. Этого времени будет достаточно для процесса анализа наличия запроса от очередного абонента и в случае, если запрос имеется, для осуществления блокировки счетного входа второго счетчика, чтобы не перейти к анализу состояния следующего абонента, а начать обслуживание данного абонента.

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

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

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

Сопоставительный анализ с прототипом показывает, что заявляемое устройство отличается наличием новых элементов: ИЛИ, ИЛИ-НЕ, И, сумматора по модулю два и связями каждого из них с другими элементами устройства.

Таким образом, заявляемое устройство соответствует критерию изобретения "новизна".

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

На чертеже приведена функциональная схема устройства. Устройство содержит генератор импульсов 1, элементы И 2, 3, счетчики 4, 5, схему сравнения 6, регистр 7, элемент НЕ 8, элементы ИЛИ 9, 10, 11, элемент задержки 12, дешифратор 13, формирователь импульсов 14, группу кодовых входов 15 устройства, элемент ИЛИ-НЕ 16, сумматор по модулю два 17, М каналов 18, каждый из которых содержит элемент И 19, элемент ИЛИ 20, элемент И с прямыми и инверсными входами 21, вход запроса 22 устройства, выход разрешения 23 устройства.

Изображенные на чертеже элементы устройства соединены следующим образом.

Каждый из входов 22 запроса устройства соединен с соответствующим входом второго элемента ИЛИ 10, выход которого соединен со входом генератора импульсов 1, выход которого соединен с первыми входами второго 2 и первого 3 элементов И, выход второго элемента И 2 соединен со счетным входом первого счетчика 4, группа выходов которого соединена с первой группой входов схемы сравнения 6, вторая группа входов которой соединена с группой выходов регистра 7, группа входов которого является группой кодовых входов 15 устройства, выход схемы сравнения 6 соединен со входом формирователя импульсов 14, выход которого соединен со входом элемента НЕ 8, выходы разрешения 23 устройства соединены с соответствующими входами первого элемента ИЛИ 11, выход которого соединен со входом элемента задержки 12 и входом сброса первого счетчика 4, выход элемента задержки 12 соединен со вторым входом второго элемента И 2, выход первого элемента И 3 соединен со счетным входом второго счетчика 5, группа выходов которого соединена с группой входов дешифратора 13, выход элемента ИЛИ-НЕ 16 соединен со вторым входом третьего элемента ИЛИ 9, первый вход которого соединен с выходом сумматора по модулю два 17, а выход - со вторым входом первого элемента И 3, выход элемента НЕ 8 соединен с третьими входами элементов И 19 всех каналов 18, каждый из выходов дешифратора 13 соединен с первым входом элемента ИЛИ 20 соответствующего канала 18, в каждом канале 18 выход элемента ИЛИ 20 соединен со вторым входом элемента И 19, выход которого соединен со вторым входом элемента ИЛИ 20 и с первым прямым входом элемента И с прямыми и инверсными входами 21, выход которого соединен с соответствующим выходом разрешения 23 устройства, выход элемента И 19 каждого канала 18 соединен с соответствующими входами элемента ИЛИ-НЕ 16 и сумматора по модулю два 17, каждый из входов запроса 22 устройства соединен с первым входом элемента И 19 и со вторым входом элемента И с прямыми и инверсными входами 21 соответствующего канала 18, выход элемента И с прямыми и инверсными входами 21 каждого канала 18 соединен с соответствующими инверсными входами элементов И с прямыми и инверсными входами 21 каждого другого канала 18.

Устройство работает следующим образом. В исходном состоянии счетчики 4, 5 находятся в нулевом состоянии, на регистре 7 через группу кодовых входов 15 установлен код, соответствующий длительности кванта обслуживания запросов. В случайные моменты времени от абонентов (абоненты и общий ресурс на чертеже не показаны) на соответствующие входы запросов 22 поступают запросы на обслуживание в виде единичных сигналов (высоких уровней напряжений), при этом на выходе элемента ИЛИ 10 появляется единичный сигнал, запускающий генератор импульсов 1, первый импульс с выхода которого через элемент И 3 (который открыт по второму входу единичным сигналом с выхода элемента ИЛИ-НЕ 16 через элемент ИЛИ 9) поступит на счетчик 5 и увеличит его состояние на единицу. Таким образом, начинается этап поиска следующего запроса. Однако к этому моменту, если, например, запрос поступил от нулевого абонента, то, т.к. на нулевом выходе дешифратора 13, а следовательно, и на втором входе элемента И 19 нулевого канала был установлен единичный сигнал и на выходе элемента НЕ 8 также установлен единичный сигнал, в нулевом канале 18₀ срабатывает элемент И 19, на выходе которого появится единичный сигнал, который через элемент ИЛИ 20 будет поддерживать элемент И 19 по второму входу в открытом состоянии (чтобы не зависеть от состояния дешифратора) и обеспечит срабатывание элемента И с прямыми и инверсными входами 21, т.к. на его прямых входах находятся единичные, а на инверсных - нулевые сигналы. В этом случае единичный сигнал с выхода элемента И 21 нулевого канала через соответствующий выход разрешения 23 поступает абоненту, сигнализируя ему о том, что общий ресурс находится в его распоряжении (и будет принадлежать ему до тех пор, пока на соответствующем выходе разрешения 23 имеется единичный сигнал). Этот сигнал через элемент ИЛИ 11 своим передним фронтом обнуляет счетчик 4, а через элемент задержки 12 открывает элемент И 2, через который импульсы с выхода генератора импульсов 1 поступают на счетный вход счетчика 4, увеличивая значения кода на его группе выходов.

Параллельно с процессом обслуживания нулевого абонента будет продолжаться поиск (если от первого абонента запрос не поступил) другого запроса следующим образом. Поскольку элемент И 3 открыт по второму входу единичным сигналом с выхода сумматора по модулю два 17 (т.к. только на одном его входе имеется единица) через элемент ИЛИ 9, то через него от генератора 1 на счетчик 5 поступит очередной (второй) импульс, который установит счетчик 5 в следующее состояние (причем при достижении этим счетчиком максимального состояния, равного коду на единицу меньшего количества абонентов, очередным счетным импульсом он устанавливается в нулевое состояние), на втором выходе дешифратора 13 появится единичный сигнал, и, если от второго абонента на соответствующем входе 22 имеется сигнал запроса, то во втором канале 18 ₂ сработает элемент И 19, единичный сигнал с выхода которого, во-первых, через элемент ИЛИ 20 будет поддерживать элемент И 19 по второму входу в открытом состоянии, а во- вторых, поступив на вход сумматора по модулю два 17, обеспечит появление на его выходе нулевого сигнала, который через элемент ИЛИ 9 закроет элемент И 3, чем запретит прохождение импульсов с выхода генератора 1 на счетчик 5, т.е. процесс поиска заканчивается как только будет найден один запрос (кроме того, который уже обслуживается). Однако во втором канале 18₂ единичный сигнал с выхода элемента И 19 на выход 23 не пройдет, т.к. в этом канале закрыт элемент И 21 единичным сигналом, поступающим на его инверсный вход с выхода 23₀ нулевого канала.

Период следования импульсов с выхода генератора 1 должен быть не меньше, чем сумма времен срабатывания: элемента И 3, счетчика 5, дешифратора 13, элементов ИЛИ 20, И 19, сумматора по модулю два 17, элемента ИЛИ 9 и элемента И 3. Это обеспечит закрытие элемента И 3 по второму входу (чтобы очередной импульс с генератора 1 не изменил состояния счетчика 5, а следовательно, и дешифратора 13) после того, как обнаружен запрос в (К+1)-м канале, когда идет обслуживание запроса, поступившего в К-й канал (где К=0...М-2) или, например, обслуживается (М-1)-й канал и обнаружен следующий запрос в нулевом канале, т.е. в соседнем. Выполнение этого ограничения позволит сохранить очередность предоставления квантов абонентам, как и в прототипе, - первому запросу, обнаруженному при опросе каналов по "кольцу".

Когда содержимое счетчика 4 станет равным значению кода кванта времени обслуживания, на выходе схемы сравнения 6 появится единичный сигнал, передним фронтом которого будет запущен формирователь импульсов 14, который выдает единичный импульс, во время действия которого на выходе элемента НЕ 8 будет присутствовать нулевой сигнал, что вызовет в нулевом канале появление нулевого сигнала на выходах элементов И 19 и 21 (т.е. прерывание в обслуживании нулевого абонента). При этом через элементы ИЛИ 11, задержки 12 и И 2 закроется счетный вход счетчика 4.

Длительность импульса, формируемого формирователем импульсов 14, рассчитывается так, чтобы после появления на выходе 23₀ нулевого сигнала, импульс с выхода формирователя импульсов 14 закончился и при этом во всех каналах 18 элементы И 19 открываются по третьим входам. При этом в рассматриваемом случае только во втором канале 18₀ на выходе элемента И 19 появится единичный сигнал, т.к. в это время только на втором выходе дешифратора 13 имеется единичный сигнал. Далее будет обслужен второй абонент, т.к. на всех инверсных входах элемента И 21 второго канала 18₀ присутствуют нулевые сигналы и, следовательно, на выходе 23 ₂ появится единичный сигнал. Во время обслуживания этого абонента будет происходить поиск следующего абонента, выставившего запрос. Если обслуживание данного абонента закончилось, то на соответствующем входе 22 появится нулевой сигнал. В дальнейшем работа устройства повторяется.

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

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

Рассмотрим вычислительную систему, состоящую из 10 терминалов (абонентов) и одного сервера (общего ресурса) и допустим, что время обслуживания одного запроса общим ресурсом (ОР) является постоянным и составляет Т_об=100 Т _лэ /1/, где Т_лэ - время срабатывания одного логического элемента типа И или ИЛИ /2/, а величина кванта Т_к=Т_об.

При использовании базового устройства для организации доступа абонентов к ОР, после обслуживания нулевого абонента следующий абонент начнет обслуживаться минимум (если это абонент номер один) через время 8Т_лэ, т.к. период следования импульсов с выхода генератора импульсов (согласно описанию работы базового устройства) должен составлять не менее чем 8Т _лэ, а максимум (если это абонент номер девять) через время 72 Т_лэ, т.е. в среднем через Т _п=40Т_лэ. Таким образом, базовое устройство будет обслуживать один абонент в среднем за время T _б=T_к+T_п=140T _лэ, т.е. за время, равное величине кванта плюс время поиска следующего запроса. При использовании предлагаемого устройства вместо базового поиск следующего запроса будет происходить во время обслуживания предыдущего запроса, т.е. после обслуживания одного абонента не нужно тратить время на поиск следующего запроса. Таким образом, предлагаемое устройство будет обслуживать один абонент за время Т_пр=100Т _лэ.

Поэтому относительный выигрыш в быстродействии, получаемый при использовании предлагаемого устройства по сравнению с базовым, составляет В=100(Т_б-Т _пр)/Т_б, т.е. примерно 28%.

ИСТОЧНИКИ ИНФОРМАЦИИ

1. Бойченко Е.В., Кальфа В., Овчинников В.В. Локальные вычислительные сети. - М.: Радио и связь, 1985, с.118.

2. Мальцева Л.А., Фромберг Э.М., Ямпольский B.C. Основы цифровой техники. - М.: Радио и связь, 1987, с.20, 25, 30.