двухвходовое устройство приоритета

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

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

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

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

Известно двухвходовое устройство приоритета (Авторское свидетельство СССР № 1269132, G06F 9/46), содержащее элементы ИЛИ-НЕ, элементы И, элементы задержки, элемент НЕ и пороговый элемент.

Недостатком устройства является малое количество запросов, обслуживаемых за время работы.

Известно двухвходовое устройство приоритета (Авторское свидетельство СССР № 1495798, G06F 9/46), содержащее элементы ИЛИ-НЕ, элементы И, триггер, элемент задержки, элемент НЕ, элемент И-НЕ и пороговый элемент.

Недостатком устройства является малое количество запросов, обслуживаемых за время работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

На фиг.1 приведена функциональная схема устройства.

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

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

Запрос присутствует на соответствующем входе до окончания его полного обслуживания. Рассмотрим работу устройства при наиболее сложной ситуации, когда одновременно поступили запросы на вход 13 и вход 14. Допустим, что триггер 8 в момент поступления запросов находился в единичном состоянии. В этом случае на обслуживание будет принят запрос, поступивший на вход 13, т.к. элемент И 2 окажется открытым по третьему входу единичным сигналом с выхода элемента

И-НЕ 12 (т.к. на его третьем входе имеется нулевой сигнал с выхода элемента ИЛИ 26), а по второму входу единичным сигналом с единичного выхода триггера 8. Таким образом, на выходе 16 устройства установится единичный сигнал с выхода элемента И 2. Этот же сигнал, поступив на вход установки в единичное состояние триггера 8, обеспечит удержание в единичном состоянии триггера 8, а через элементы ИЛИ 9 и НЕ 11 закроет элемент И 4 по второму входу, прекратив этим подачу импульсов с генератора 1 на счетный вход триггера 8.

С момента появления единичного сигнала на выходе 16 начинается обслуживание общим ресурсом запроса, поступившего на вход 13, а время его непрерывного обслуживания будет учитываться на счетчике 10, т.к. единичный сигнал с выхода элемента ИЛИ 9 откроет по второму входу элемент И 5, через первый вход которого на счетный вход счетчика 10 начнут поступать счетные импульсы с генератора 1. После того как на группе выходов счетчика 10 появится код, равный коду, записанному в регистре 7, с выхода схемы сравнения 6 единичный сигнал (длительность которого будет указана ниже), пройдя через элемент ИЛИ 26, сбросит счетчик 10 и поступит на третий вход элемента И-НЕ 12, и т.к. на двух других его входах уже имеются единичные сигналы, на выходе этого элемента появится нулевой сигнал, который закроет по третьим входам элементы И 2 и И 3, обеспечив поступление нулевых сигналов с их выходов на установочные входы триггера 8 и закрывание через элемент ИЛИ 9 по второму входу элемента И 5, чтобы счетные импульсы не поступали на счетчик 10, а единичным сигналом с выхода элемента НЕ 11 откроется элемент И 4, и очередным импульсом с генератора 1 триггер 8 переключится в нулевое состояние. К этому моменту единичный сигнал с выхода схемы сравнения закончится (его длительность рассчитывается как сумма времен срабатывания элементов 26, 12, 2, 9, 11, 4 и периода следования импульсов генератора 1) и на выходе элемента И-НЕ 12 появится единичный сигнал, что приведет к срабатыванию элемента И 3, т.к. триггер теперь находится в нулевом состоянии. Далее работа устройства осуществляется аналогично вышеописанному и, таким образом, обеспечивается выделение кванта времени обслуживания запросу, поступившему по входу 14. Если в течение очередного кванта обслуживание одного из запросов полностью закончилось, т.е. на соответствующем входе 13 или 14 появится нулевой сигнал, то устройство перейдет к обслуживанию другого запроса. Если в очереди на обслуживание стоит только один запрос (только на одном из входов имеется единичный сигнал), то прерывание обслуживания этого запроса не наступает и ему выделяется еще квант времени, который будет прерван при поступлении запроса на другой вход, чем обеспечивается наибольшая вероятность выявления "короткого" запроса и, следовательно, максимизируется количество обслуженных запросов в единицу времени, т.е. в полной мере используются возможности циклической дисциплины обслуживания запросов.

Рассмотрим эту ситуацию более подробно. Допустим, на обслуживании находится запрос, поступивший по входу 13, а на входе 14 запроса нет. После того как закончился квант (а обслуживание запроса еще не закончилось), со схемы сравнения 6 выдается единичный сигнал, который вызывает срабатывание элемента И 18, т.к. на его инверсном входе присутствует нулевой сигнал со входа 14, а на первом прямом входе - единичный сигнал со входа 13. Единичный сигнал с выхода элемента И 18 устанавливает триггер 20 в единичное состояние, фиксируя факт того, что первый запрос получил дополнительный квант без прерывания обслуживания, поскольку отсутствует запрос по другому входу. Если же во время этого дополнительного кванта появится запрос по входу 14, то на выходе элемента И 22 появится единичный сигнал, по переднему фронту которого формирователь импульсов 24 сформирует импульс (такой же длительности, как и импульс с выхода схемы сравнения 6), который сбросит триггер 20, а через элемент ИЛИ 26 обеспечит переключение на обслуживание (вышеуказанным образом) запроса, поступившего по входу 14, выдавая ему квант для обслуживания, забрав его у "старого" запроса, поступившего по входу 13, поскольку он не успел обслужиться за предыдущий квант, т.е. свою возможность уже использовал. Элементы 19, 21, 23 и 25 выполняют функции, аналогичные элементам соответственно 18, 20, 22 и 24 по отношению к другому каналу.

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

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

Проанализируем количество обслуженных запросов в вычислительной системе, содержащей два абонента и общий ресурс, например процессор за интервал времени работы, равный 4,5 условным единицам (фиг.2а), считая, что квант обслуживания равен одной единице времени (фиг.2б), а затратами на прерывание ОР от обслуживания одного абонента на обслуживание другого абонента можно пренебречь.

Пусть к началу анализируемого интервала поступил один запрос от первого абонента, требующий 4 единицы времени обслуживания (фиг.2в), а через 1,5 единицы времени поступил первый запрос от второго абонента, требующий 1 единицы времени обслуживания, и за ним через 1 единицу времени - второй запрос от второго абонента, требующий также 1 единицы времени обслуживания (фиг.2г).

При использовании базового устройства в вычислительной системе за анализируемый интервал времени запрос от первого абонента будет обслужен частично (фиг.2д), а полностью будет обслужен один запрос - первый запрос от второго абонента (фиг.2е). При использовании предлагаемого устройства за анализируемый интервал времени запрос от первого абонента будет обслужен также частично (фиг.2ж), а от второго абонента оба запроса будут обслужены полностью (фиг.2з).

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

100(2-1)/2=50%.

Источники информации

1. Таташев А.Г. Одна дисциплина обслуживания с разделением процессора. - Автоматика и вычислительная техника, 1993, № 6, с.27.