Многоканальное устройство приоритета

Многоканальное устройство приоритета

Реферат

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

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

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

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

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

Наиболее близким по технической сущности к заявляемому устройству является выбранное в качестве прототипа многоканальное устройство приоритета /Авторское свидетельство СССР №1809441, G06F 9/46/, содержащее элемент ИЛИ-НЕ, элемент И, элемент ИЛИ, формирователь импульсов, элемент задержки, группу элементов ИЛИ, блок выбора старшего разряда, содержащий элементы И с прямым и инверсными входами, Н каналов, каждый из которых содержит триггер, элемент ИЛИ, вторую и первую группу элементов И, регистр, дешифратор, выход ответа канала, вход сброса канала, группу кодовых входов устройства, вход запроса канала, причем единичный выход триггера каждого канала является выходом ответа канала и соединен с соответствующим входом элемента ИЛИ-НЕ, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом элемента ИЛИ, входы которого являются входами запроса соответствующих каналов, выход элемента И соединен с входом формирователя импульсов, группа кодовых входов устройства соединена с группой входов первой группы элементов И соответствующего канала, выход формирователя импульсов соединен с входом элемента задержки и со вторыми входами первой группы элементов И всех каналов, группа выходов первой группы элементов И каждого канала соединена с группой информационных входов регистра своего канала, группа выходов которого соединена с группой дешифратора канала, К-й (К=1, …, Н) выход которого соединен с первым входом К-го элемента И второй группы элементов И своего канала и с одноименным каналу входом К-го элемента ИЛИ группы элементов ИЛИ, выход К-го элемента И второй группы элементов И соединен с К-м входом элемента ИЛИ своего канала, выход которого соединен с единичным входом триггера своего канала, нулевой вход триггера канала является входом сброса канала и соединен со входом обнуления регистра канала, выход элемента задержки соединен со вторыми входами элементов И вторых групп элементов И всех каналов, выход Н-го элемента ИЛИ группы элементов ИЛИ является Н-м входом и выходом блока выбора старшего разряда (БВСР) и соединен с третьими входами Н-х элементов И вторых групп элементов И всех каналов и с первыми инверсными входами всех элементов И с прямым и инверсными входами БВСР, выход М-го [М=1, …, (Н-1)] элемента И с прямым и инверсными входами БВСР является М-м выходом БВСР и соединен с третьими входами М-х элементов И вторых групп элементов И всех каналов, выход первого элемента ИЛИ группы элементов ИЛИ соединен с прямым входом первого элемента И с прямым и инверсными входами БВСР, выход I-го [I=2, …, (Н-1)] элемента ИЛИ группы соединен с прямым входом I-го элемента И с прямым и инверсными входами БВСР и с соответствующими инверсными входами каждого из элементов И с прямым и инверсными входами БВСР, номера которых меньше чем I.

Устройство работает следующим образом.

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

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

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

Однако известно /1/, что в вычислительных системах реального времени задержка в очереди на обработку более важных запросов приводит к большим потерям эффективности системы, чем задержка менее важных запросов. Для повышения эффективности вычислительной системы необходимо в первую очередь предоставить устройство общего пользования (УОП) для обслуживания запроса, имеющего наивысший приоритет (важность). Такая дисциплина (дисциплина с абсолютными приоритетами) использования УОП (обслуживания запросов) эквивалентна повышению производительности всей системы /1/.

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

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

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

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

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

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

На чертеже изображена структурная схема устройства.

Устройство содержит М каналов 1, в состав которых входят дешифратор 2, группа элементов И 3, первый и второй элементы ИЛИ 4, 5, элемент И 6 с прямым и инверсными входами, элемент задержки 7, группа кодовых входов 8, вход 9 запроса, выход 10 ответа.

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

В каждом канале 1 группа кодовых входов 8 соединена с группой входов дешифратора 2, Н-й выход которого (Н=1, …, М) соединен с первым входом Н-го элемента И группы элементов И 3 своего канала 1, I-й вход (I=1, …, М) второго элемента ИЛИ 5 Н-го канала (Н=1, …, М) соединен с Н-м выходом дешифратора 2 I-го канала 1, выход второго элемента ИЛИ 5 К-го канала (К=1, …, М-1) соединен с прямым входом элемента И 6 с прямым и инверсными входами своего канала 1, выходы которых соединены с третьими входами К-х элементов И группы элементов И 3 всех каналов 1, выход второго элемента ИЛИ 5 каждого канала 1, кроме первого, соединен с соответствующим инверсным входом элемента И 6 с прямым и инверсными входами каждого другого канала 1, номер которого меньше данного, выход второго элемента ИЛИ 5 М-го канала 1 соединен с третьими входами М-х элементов И группы элементов И 3 всех каналов 1, в каждом канале 1 выходы элементов И группы элементов И 3 соединены с соответствующими входами первого элемента ИЛИ 4, выход которого является выходом ответа 10 канала 1, в каждом канале вход запроса 9 соединен со входом элемента задержки 7, выход которого соединен со вторыми входами всех элементов И группы элементов И 3 своего канала 1.

Устройство работает следующим образом.

В исходном состоянии на входах 9 запроса каналов 1 и группах кодовых входов 8 присутствуют нулевые сигналы. В случайные моменты времени от абонентов (абоненты на чертеже не показаны) на входы запроса 9 соответствующих каналов 1 поступают сигналы запроса в виде логической единицы. В этот же момент времени от абонентов на соответствующие группы кодовых входов 8 поступают их коды приоритетов (приоритет тем выше, чем старше код). В устройстве применяется двоичный код приоритета, причем одинаковых кодов у абонентов быть не может, но они могут оперативно изменяться при перенастройке вычислительной системы. В дальнейшем при описании работы устройства под появлением запроса от абонента будем понимать одновременные поступления единичного сигнала на вход 9 и кода приоритета на группу кодовых входов 8 соответствующего канала 1. Если от абонента не поступает запрос, то и на соответствующей группе кодовых входов 8 код будет равен нулю, поэтому нулевые выходы дешифраторов 2 в устройстве не используются (используются только выходы с 1-го по М-й, где М - количество каналов).

Рассмотрим ситуацию, когда поступил запрос от первого абонента, т.е. в канал 11, а затем, во время его обслуживания, поступил запрос от второго абонента (т.е. в канал 12), приоритет которого выше, чем у первого абонента (допустим, что код приоритета, поступающий в соответствующий канал, равен номеру канала).

Таким образом, в первом канале 11 на первом выходе дешифратора 2 установится единичный сигнал, который откроет по первому входу первый элемент И 31 группы элементов И и, пройдя через второй элемент ИЛИ 5 и поступив на прямой вход элемента И с прямым и инверсными входами 6, обеспечит появление единичного сигнала на его выходе (т.к. на его инверсных входах в это время присутствуют нулевые сигналы), который откроет по третьему входу первый элемент И 31 группы элементов И. К этому моменту в первом канале 11 на выходе элемента задержки 7 появится единичный сигнал, который, пройдя через первый элемент И 31 группы элементов И и через первый элемент ИЛИ 4, поступит на выход ответа 10. Единичный сигнал с выхода ответа 10 даст разрешение первому абоненту на доступ к устройству общего пользования (если этот сигнал отсутствует, то доступ абонента к устройству общего пользования будет запрещен). С этого момента начинается обслуживание первого абонента устройством общего пользования и, если до окончания его обслуживания поступит сигнал запроса от второго абонента (у которого приоритет выше, чем у первого абонента, т.к. он в рассматриваемой ситуации равен двум, а у первого абонента равен единице), то во втором канале 12 на втором выходе дешифратора 2 установится единичный сигнал, который откроет по первому входу второй элемент И 32 группы элементов И и, пройдя через второй элемент ИЛИ 5, поступит: во - первых, в первый канал 11 на соответствующий инверсный вход элемента И с прямым и инверсными входами 6, устанавливая на его выходе нулевой сигнал, который в первом канале 11, пройдя через элемент И 31 группы элементов И и элемент ИЛИ 4, обеспечит появление на выходе ответа 10 нулевого сигнала, что приведет к прерыванию обслуживания первого абонента, а, во-вторых, во втором канале - на прямой вход элемента И с прямым и инверсными входами 6, вызвав появление на его выходе единичного сигнала (т.к. на его инверсных входах присутствуют нулевые сигналы), который поступит на третий вход второго элемента И 32 группы элементов И, и, поскольку этот элемент к этому времени будет открыт и по второму входу единичным сигналом с выхода элемента задержки 7 (т.к. он задерживает сигнал запроса со входа 9 на время срабатывания дешифратора 2, второго элемента ИЛИ 5 и элемента И с прямым и инверсными выходами 6), то на выходе элемента И 32 группы элементов И появится единичный сигнал, который через элемент ИЛИ 4 поступит на выход ответа 10 и разрешит второму абоненту доступ к устройству общего пользования.

После окончания обслуживания второго абонента на группе кодовых входов 8 и входе запроса 9 второго канала 12 этим абонентом устанавливаются нулевые сигналы, что приведет (после срабатывания в канале 12 элемента задержки 7, элемента И 32 и элемента ИЛИ 4) к появлению на выходе ответа 10 второго канала 12 нулевого сигнала, а на выходе ответа 10 первого канала 11 появится единичный сигнал (после срабатывания во втором канале 12 дешифратора 2 элемента ИЛИ 5 и в первом канале 11 элемента И с прямым и инверсными входами 6, элемента И 31 и элемента ИЛИ 4), и, следовательно, будет продолжено обслуживание первого абонента. Так как элемент задержки 7 задерживает сигнал на время срабатывания дешифратора 2, элемента ИЛИ 5 и элемента И с прямым и инверсными входами 6, то появление нулевого сигнала на выходе 10 второго канала 12 и единичного сигнала на выходе 10 первого канала 12 произойдет одновременно.

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

Поскольку на входы второго элемента ИЛИ 5 последнего канала 1м могут поступать только сигналы, соответствующие самому высокому приоритету абонента (которого другие абоненты прервать не могут), то в этом канале отсутствует элемент И с прямым и инверсными входами 6.

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

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

Базовое устройство реализует дисциплину обслуживания запросов с относительными приоритетами. Предлагаемое устройство позволяет осуществлять дисциплину с абсолютными приоритетами и, за счет этого, получать выигрыши в эквивалентной производительности. Методика оценки эффективности дисциплины с абсолютными приоритетами по сравнению с относительными приоритетами приведена в /1/, где показано, что простых аналитических выражений для определения выигрыша в эквивалентной производительности получить не удалось и для определения значений эффективности дисциплин расчеты приходится проводить последовательно по формулам, позволяющим определить сначала длительность ожидания запросов в очереди, затем полную длительность пребывания в системе и суммарный штраф за это. Результаты оценки эффективности, представленные в /1/ в графическом виде, для двух потоков запросов показывают, что при загрузке устройства, равной 0.9, при отношении времени обработки менее приоритетных запросов ко времени обработки более приоритетных запросов, равном 30, и таком же отношении штрафа за единицу времени ожидания более приоритетных запросов к штрафу за единицу времени ожидания менее приоритетных запросов выигрыш в эквивалентной производительности от применения предлагаемого устройства по сравнению с базовым устройством составляет около 40%.

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

1. Липаев В.В., Яшков С.Ф. Эффективность методов организации вычислительного процесса в АСУ. - М.: Статистика, 1975, с.39, с.127-129.

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