СПОСОБ РАЗРЕШЕНИЯ КОНФЛИКТОВ

Название	СПОСОБ РАЗРЕШЕНИЯ КОНФЛИКТОВ
Разработчик (Авторы)	Гурский Сергей Михайлович
Вид объекта патентного права	Изобретение
Регистрационный номер	2209461
Дата регистрации	27.07.2003
Правообладатель	Гурский Сергей Михайлович
Область применения (класс МПК)	G06F 9/46 (2000.01) G06F 9/50 (2000.01)
Медаль имени А.Нобеля

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

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

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

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

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

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

Целью изобретения является сокращение времени обработки информации за счет учета времени ожидания обслуживания.

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

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

Способ содержит 11 действий: установка 1 признака наличия/отсутствия запроса в положение наличие запроса, суммирование 2 запросов отдельно для каждого вычислительного устройства, формирование кода приоритета 3 отдельно для каждого вычислительного устройства, которое осуществляется путем объединения признака наличия/отсутствия запроса с суммой количества поступивших запросов, суммой циклов ожидания, номером соответствующего вычислительного устройства, хранение кодов приоритетов 4 на время ожидания обслуживания и на время выбора вычислительного устройства, выделение 5 номера вычислительного устройства из числа обратившихся, формирование 6 сигнала о разрешении обслуживания, установка 7 признака наличия/отсутствия запроса в положении отсутствии запроса, объединение 8 сигналов о разрешении обслуживания вычислительных устройств в единый сигнал, подсчет 9 количества циклов ожидания обслуживания всех вычислительных устройств, обнуление 10 кодов циклов ожидания отдельно для каждого вычислительного устройства, причем выделение кода приоритета производится путем пошагового просмотра 11 содержимого кодов приоритетов.

Работа способа заключается в следующем.

Во время работы системы, в которой может использоваться данный способ, от вычислительных устройств независимо друг от друга могут поступать запросы на обслуживание. Например, в мультимикропроцессорных вычислительных системах (ММПВС) микропроцессоры обращаются (МП) к общей памяти (ОП) для считывания или записи информации. При одновременном (в течении цикла работы ОП) обращении двух и более МП к ОП возникает очередь на обслуживание, так как за один цикл работы ОП может быть обслужен только один МП. За счет возникновения очереди снижается производительность систем. В этом случае необходимо принимать решение, какому МП разрешить обратиться к ОП. Существуют различные дисциплины обслуживания. В способе-прототипе используется дисциплина обслуживания "реже обращается - раньше обслужен": преимущество предоставляется тому МП, количество обращений от которого минимально. Для реализации данной дисциплины необходимо вести учет количества обращений отдельно для каждого МП.

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

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

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

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

Коды приоритетов сохраняются 4 на время ожидания обслуживания и на время выделения 5 номера вычислительного устройства. Сохраненные коды приоритетов поступают для выделения номера 5 вычислительного устройства. Выделение номера 5 вычислительного устройства осуществляется с помощью узла выделения кодов приоритетов, состоящего из матрицы блоков опроса, содержащих схемы сравнения, и элементов ИЛИ, путем пошагового просмотра (сравнения) 11 разрядов кодов приоритетов. Матрица блоков опроса состоит из n линеек, в каждой из которых содержится m блоков опроса, где n равно количеству вычислительных устройств, а m равно количеству разрядов кодов приоритетов. На первом шаге просматривается разряд признака наличия/отсутствия запроса кодов приоритетов всех вычислительных устройств. Коды приоритетов, разряд признака наличия/отсутствия запроса которых равны единице (это означает, что от данных вычислительных устройств поступил запрос), передаются для просмотра 11 на следующем шаге. Таким образом, после первого шага сравнения выделяются те вычислительные устройства, от которых поступил запрос на обслуживание. Причем запрос на обслуживание от некоторых вычислительных устройств мог поступить в предыдущих циклах, и они ожидали обслуживания.

На следующих шагах выделения номера вычислительного устройства из числа обратившихся осуществляется просмотр 11 разрядов суммы количества поступивших запросов, поступающих в инверсном коде, например с нулевых выходов триггеров счетчика. Если одноименные разряды всех кодов приоритетов либо равны нулю, либо - единице, то все коды приоритетов передаются без изменения для просмотра 11 в следующем шаге (для сравнения следующих разрядов). Если значения одноименных разрядов кодов разные, то для просмотра 11 в следующем шаге передаются только те коды приоритетов, одноименные разряды которых равны единице.

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

В результате пошагового просмотра 11 (поразрядного сравнения) кодов приоритетов выделяется номер только одного вычислительного устройства.

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

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

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

Например, система состоит из пяти вычислительных устройств. В определенный момент времени первое вычислительное устройство уже обращалось 10 раз, второе - 13 раз, третье - 7 раз, четвертое и пятое - по 12 раз. Суммы циклов ожиданий обслуживания вычислительных устройств соответственно равны: 10, 8, 9, 12 и 14 циклов. В системе ожидают обслуживания второе и четвертое вычислительные устройства и поступил запрос от пятого. Таким образом, коды приоритетов на момент поступления запроса от пятого вычислительного устройства представлены в двоичном коде в табл.1.

В первом шаге просматривается разряд признака наличия/отсутствия запроса кодов приоритетов всех вычислительных устройств, т.е. разряды первой колонки таблицы - 0, 1, 0, 1 и 1.

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

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

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

После пятого шага сравнения коды приоритетов будут иметь следующий вид (табл.3).

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

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

После восьмого шага сравнения коды приоритетов будут иметь следующий вид (табл.4).

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

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

Следовательно, после выдачи номера пятого вычислительного устройства коды приоритетов будут иметь следующий вид (табл.5).

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

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

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

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

Изобретение "СПОСОБ РАЗРЕШЕНИЯ КОНФЛИКТОВ" (Гурский Сергей Михайлович) отмечено юбилейной наградой (25 лет Российской Академии Естествознания)
Медаль Альфреда Нобеля

Оформление наградных документов и заказ каталога