 |
Децентрализованный арбитраж
|
|
|
|
ЭВМ и периферийные устройства
Лектор: доц. Осмоналиев А.Б.
Лекция 15. (2 часа)
Тема: Арбитраж шин. Протокол шины
Арбитраж шин
В реальных системах на роль ведущего вправе одновременно претендовать сразу несколько из подключенных к шине устройств, однако управлять шиной в каждый момент времени может только одно из них. Чтобы исключить конфликты, шина должна предусматривать определенные механизмы арбитража запросов и правила предоставления шины одному из запросивших устройств. Решение обычно принимается на основе приоритетов претендентов.
Схемы приоритетов
Каждому потенциальному ведущему присваивается определенный уровень приоритета, который может оставаться неизменным (статический или фиксированный приоритет) либо изменяться по какому-либо алгоритму (динамический приоритет).
Основной недостаток статических приоритетов в том, что устройства, имеющие высокий приоритет, в состоянии полностью блокировать доступ к шине устройств с низким уровнем приоритета. Системы с динамическими приоритетами дают шанс каждому из запросивших устройств рано или поздно получить право на управление шиной, то есть в таких системах реализуется принцип равнодоступности.
Наибольшее распространение получили следующие алгоритмы динамического изменения приоритетов:
• простая циклическая смена приоритетов;
• циклическая смена приоритетов с учетом последнего запроса;
• смена приоритетов по случайному закону;
• схема равных приоритетов;
• алгоритм наиболее давнего использования.
В алгоритме простой циклической смены приоритетов после каждого цикла арбитража все приоритеты понижаются на один уровень, при этом устройство, имевшее ранее низший уровень приоритета, получает наивысший приоритет.
|
|
|
В схеме циклической смены приоритетов с учетом последнего запроса все возможные запросы упорядочиваются в виде циклического списка. После обработки очередного запроса обслуженному ведущему назначается низший уровень приоритета. Следующее в списке устройство получает наивысший приоритет, а остальным устройствам приоритеты назначаются в убывающем порядке, согласно их следованию в циклическом списке.
В обеих схемах циклической смены приоритетов каждому ведущему обеспечивается шанс получить шину в свое распоряжение, однако большее распространение получил второй алгоритм.
При смене приоритетов по случайному закону после очередного цикла арбитража с помощью генератора псевдослучайных чисел каждому ведущему присваивается случайное значение уровня приоритета.
В схеме равных приоритетов при поступлении к арбитру нескольких запросов каждый из них имеет равные шансы на обслуживание. Возможный конфликт разрешается арбитром. Такая схема принята в асинхронных системах.
В алгоритме наиболее давнего использования (LRU, Least Recently Used) после каждого цикла арбитража наивысший приоритет присваивается ведущему, который дольше чем другие не использовал шину.
Помимо рассмотренных существует несколько алгоритмов смены приоритетов, которые не являются чисто динамическими, поскольку смена приоритетов происходит не после каждого цикла арбитража. К таким алгоритмам относятся:
• алгоритм очереди (первым пришел — первым обслужен);
• алгоритм фиксированного кванта времени.
В алгоритме очереди запросы обслуживаются в порядке очереди, образовавшейся к моменту начала цикла арбитража. Сначала обслуживается первый запрос в очереди, то есть запрос, поступивший раньше остальных. Аппаратурная реализация алгоритма связана с определенными сложностями, поэтому используется он редко.
|
|
|
В алгоритме фиксированного кванта времени каждому ведущему для захвата шины в течение цикла арбитража выделяется определенный квант времени. Если ведущий в этот момент не нуждается в шине, выделенный ему квант остается не использованным. Такой метод наиболее подходит для шин с синхронным протоколом.
Схемы арбитража
Арбитраж запросов на управление шиной может быть организован по централизованной или децентрализованной схеме. Выбор конкретной схемы зависит от требований к производительности и стоимостных ограничений.
Централизованный арбитраж
При централизованном арбитраже в системе имеется специальное устройство — центральный арбитр, - ответственное за предоставление доступа к шине только одному из запросивших ведущих. Это устройство, называемое иногда центральным контроллером шины, может быть самостоятельным модулем или частью ЦП.
Наличие на шине только одного арбитра означает, что в централизованной схеме имеется единственная точка отказа. В зависимости от того, каким образом ведущие устройства подключены к центральному арбитрут возможные схемы централизованного арбитража можно подразделить на параллельные и последовательные.
В параллельном варианте центральный арбитр связан с каждым потенциальным ведущим индивидуальными двухпроводными трактами. Поскольку запросы к центральному арбитру могут поступать независимо и параллельно, данный вид арбитража называют централизованным параллельным арбитражем или централизованным арбитражем независимых запросов.
Идею централизованного параллельного арбитража на примере восьми ведущих устройств иллюстрирует рис. 15.1, а.
Здесь и далее под «текущим ведущим» будем понимать ведущее устройство, управляющее шиной в момент поступления нового запроса. Устройство, выставившее запрос на управление шиной, будем называть «запросившим ведущим».
Рис. 15.1. Централизованный параллельный арбитраж: а - общая схема; б — возможная реализация
Сигналы запроса шины (ЗШ) поступают на вход центрального арбитра по индивидуальным линиям. Ведущему с номером i, который был выбран арбитром, также по индивидуальной линии возвращается сигнал предоставления шины (ПШ,). Реально же занять шину новый ведущий сможет лишь после того, как текущий ведущий (пусть он имеет номер j) снимет сигнал занятия шины (ШЗ). Текущий ведущий должен сохранять сигналы ШЗ и 3Шj активными в течение всего времени, пока он использует шину. Получив запрос от ведущего, приоритет которого выше, чем у текущего ведущего, арбитр снимает сигнал ПШj на входе текущего ведущего и выдает сигнал предоставления шины ПШ, запросившему ведущему. В свою очередь, текущий ведущий, обнаружив, что центральный арбитр убрал с его входа сигнал ПШj, снимает свои сигналы ШЗ и 3Шj после чего запросивший ведущий может перенять управление шиной. Если в момент пропадания сигнала ПШ на шине происходит передача информации, текущий ведущий сначала завершает передачу и лишь после этого снимает свои сигналы.
|
|
|
Логика выбора одного из запрашивающих ведущих обычно реализуется аппаратными средствами. В качестве примера рассмотрим реализацию системы централизованного параллельного арбитража для статических приоритетов (рис. 15.1, б).
Пусть имеется восемь потенциальных ведущих 7-0, восемь сигналов запроса шины ЗШ7-ЗШ0 и восемь соответствующих им сигналов предоставления шины ПШ7-ПШ0.
Положим, что приоритеты ведущих последовательно убывают с уменьшением их номера. Если текущим является ведущий 3, то шину у него могут перехватить ведущие с номерами от 4 до 7, а ведущие 0-2 этого сделать не могут. Ведущий 0 вправе использовать шину лишь тогда, когда она свободна, и должен освободить ее по запросу любого другого ведущего. Схема статических приоритетов может быть относительно просто реализована на основе логических выражений, которые применительно к рассматриваемому примеру имеют вид:
Устройства арбитража, реализующие систему статических приоритетов, обычно выполняются в виде отдельных микросхем (например, SN74278 фирмы Texas Instruments), которые, с целью увеличения числа входов и выходов, могут объединяться по каскадной схеме, что, однако, ведет к увеличению времени арбитража.
|
|
|
При наличии большого числа источников запроса центральный арбитр может строиться по схеме двухуровневого параллельного арбитража. Все возможные запросы разбиваются на группы, и каждая группа анализируется своим арбитром первого уровня. Каждый арбитр первого уровня выбирает запрос, имеющий в данной группе наивысший приоритет. Арбитр второго уровня отдает предпочтение среди арбитров первого уровня, обнаруживших запросы на шину, тому, который имеет более высокий приоритет. Если количество возможных запросов очень велико, могут вводиться дополнительные уровни арбитража.
Схема централизованного параллельного арбитража очень гибка — вместо статических приоритетов допускается использовать любые варианты динамической смены приоритетов. Благодаря наличию прямых связей между центральным арбитром и ведущими схема обладает высоким быстродействием, однако именно непосредственные связи становятся причиной повышенной стоимости реализации. В параллельных схемах затруднено подключение дополнительных устройств. Обычно максимальное число ведущих при параллельном арбитраже не превышает восьми. У схемы есть еще один существенный недостаток — сигналы запроса и подтверждения присутствуют только на индивидуальных линиях и не появляются на общих линиях шины, что затрудняет диагностику.
Второй вид централизованного арбитража известен как централизованный последовательный арбитраж. В последовательных схемах для выделения запроса с наивысшим приоритетом используется один из сигналов, поочередно проходящий через цепочку ведущих, чем и объясняется другое название - цепочечный или гирляндный арбитраж. В дальнейшем будем полагать, что уровни приоритета ведущих устройств в цепочке понижаются слева направо.
В зависимости от того, какой из сигналов используется для целей арбитража, различают три основных типа схем цепочечного арбитража: с цепочкой для сигнала предоставления шины, с цепочкой для сигнала запроса шины (ЗШ) и с цепочкой для дополнительного сигнала разрешения (РШ). Наиболее распространена схема цепочки для сигнала ПШ (рис. 15.2).
Рис. 15.2. Централизованный последовательный арбитраж с цепочкой для сигнала предоставления шины
Запросы от ведущих объединяются на линии запроса шины по схеме «монтажного ИЛИ». Аналогично организована и линия, сигнализирующая о том, что шина в данный момент занята одним из ведущих. Когда один или несколько ведущих выставляют запросы, эти запросы транслируются на вход центрального арбитра. Получив сигнал ЗШ, арбитр анализирует состояние линии занятия шины, и если шина свободна, формирует сигнал ПШ Сигнал предоставления шины последовательно переходит по цепочке от одного ведущего к другому. Если устройство, на которое поступил сигнал ПШ, не запрашивало шину, оно просто пропускает сигнал дальше по цепочке. Когда ПШ достигнет самого левого из запросивших ведущих, последний блокирует дальнейшее распространение сигнала ПШ по цепочке и берет на себя управление шиной.
|
|
|
Еще раз отметим, что очередной ведущий не может приступить к управлению шиной до момента ее освобождения. Центральный арбитр не должен формировать сигнал ПШ вплоть до этого момента.
Цепочечная реализация предполагает статическое распределение приоритетов. Наивысший приоритет имеет ближайшее к арбитру ведущее устройство (устройство, на которое арбитр выдает сигнал ПШ). Далее приоритеты ведущих в цепочке последовательно понижаются.
Основное достоинство цепочечного арбитража заключается в простоте реализации и в малом количестве используемых линий. Последовательные схемы арбитража позволяют легко наращивать число устройств, подключаемых к шине.
Схеме тем не менее присущи существенные недостатки. Прежде всего, последовательное прохождение сигнала по цепочке замедляет арбитраж, причем время арбитража растет пропорционально длине цепочки. Статическое распределение приоритетов может привести к полному блокированию устройств с низким уровнем приоритета (расположенных в конце цепочки). Наконец, как и параллельный вариант, централизованный последовательный арбитраж не очень удобен в плане диагностики работы шины.
Децентрализованный арбитраж
При децентрализованном или распределенном арбитраже единый арбитр отсутствует. Вместо этого каждый ведущий содержит блок управления доступом к шине и при совместном использовании шины такие блоки взаимодействуют друг с другом, разделяя между собой ответственность за доступ к шине. По сравнению с централизованной схемой децентрализованный арбитраж менее чувствителен к отказам претендующих на шину устройств.
Рис. 15.3. Схема децентрализованного параллельного арбитража
Одна из возможных схем, которую можно условно назвать схемой децентрализованного параллельного арбитража, показана на рис. 4.13. Каждый ведущий имеет уникальный уровень приоритета и обладает собственным контроллером шины, способным формировать сигналы предоставления и занятия шины. Сигналы запроса от любого ведущего поступают на входы всех остальных ведущих. Логика арбитража реализуется в контроллере шины каждого ведущего.
Под децентрализованный арбитраж может быть модифицирована также схема, приведенная на рис. 15.2. Подобный вариант, называемый кольцевой схемой, показан на рис. 15.4.
Рис. 15.4. Кольцевая схема
Здесь сигнал может возникать в различных точках цепочки, замкнутой в кольцо. Переход к новому ведущему сопровождается циклической сменой приоритетов. В следующем цикле арбитража текущий ведущий будет иметь самый низкий уровень приоритета. Соседний ведущий справа получает наивысший приоритет, а далее каждому устройству в кольце присваивается уровень приоритета на единицу меньше, чем у соседа слева. Иными словами, реализуется циклическая смена приоритетов с учетом последнего запроса.
Текущий ведущий, управляющий шиной, генерирует сигнал ПШ, который проходит через все ведущие устройства, не запросившие шину. Ведущий, сформировавший запрос и имеющий на входе активный сигнал ПШ, запрещает прохождение этого сигнала далее по цепочке, но не может взять на себя управление шиной до момента ее освобождения текущим ведущим. Когда текущий ведущий обнаруживает, что «потерял» сигнал ПШ на своем входе, он обязан при первой возможности освободить шину и снять сигнал занятия шины.
Для большинства шин все-таки более характерна другая организация децентрализованного арбитража. Такие схемы предполагают наличие в составе шины группы арбитражных линий, организованных по схеме «монтажного ИЛИ». Это позволяет любому ведущему видеть сигналы, выставленные остальными устройствами. Каждому ведущему присваивается уникальный номер, совпадающий с кодом уровня приоритета данного ведущего. Запрашивающие шину устройства выдают на арбитражные линии свой номер. Каждый из запросивших ведущих, обнаружив на арбитражных линиях номер устройствах более высоким приоритетом, снимает с этих линий младшие биты своего номера. В конце концов на арбитражных линиях остается только номер устройства, обладающего наиболее высоким приоритетом. Победителем в процедуре арбитража становится ведущий, опознав ший на арбитражных линиях свой номер. Подобная схема известна также как распределенный арбитраж с самостоятельным выбором, поскольку ведущий сам определяет, стал ли он победителем в арбитраже, то есть выбирает себя самостоятельно.
В целом схемы децентрализованного арбитража потенциально более надежны, поскольку отказ контроллера шины в одном из ведущих не нарушает работу с шиной на общем уровне. Тем не менее должны быть предусмотрены средства для обнаружения неисправных контроллеров, например на основе тайм-аута. Основной недостаток децентрализованных схем — в относительной сложности логики арбитража, которая должна'быть реализована в аппаратуре каждого ведущего.
В некоторых ВМ применяют комбинированные последовательно-параллельные схемы арбитража, в какой-то мере сочетающие достоинства обоих методов. Здесь все ведущие разбиваются на группы. Арбитраж внутри группы ведется по последовательной схеме, а между группами - по параллельной.
|
|
|
