Файл: 1-337.pdf

Арбитраж шин  1 7 1

Рис. 4.10. Мультиплексирование адреса и данных

гом конце. Мультиплексоры и демультиплексоры играют роль коммутирующих

устройств.

Мультиплексирование позволяет сократить общее число линий, но требует ус-

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

Примером применения мультиплексируемой шины адреса/данных может слу-

жить шина Futurebus+.

Арбитраж шин

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

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

Схемы приоритетов

Каждому потенциальному ведущему присваивается определенный уровень прио-

ритета, который может оставаться неизменным

 (статический

 или

 фиксированный

приоритет)

 либо изменяться по какому-либо алгоритму

 (динамический приори-

тет).

172 Глава 4. Организация шин

Основной недостаток статических приоритетов в том, что устройства, имею-

щие высокий приоритет, в состоянии полностью блокировать доступ к шине уст-

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

Наибольшее распространение получили следующие алгоритмы динамического

изменения приоритетов:

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

В алгоритме

 простой циклической смены приоритетов

 после каждого цикла

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

В схеме

 циклической смены приоритетов с учетом последнего запроса

 все воз-

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

В обеих схемах циклической смены приоритетов каждому ведущему обеспечи-

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

При

 смене приоритетов по случайному закону

 после очередного цикла арбитра-

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

В

 схеме равных приоритетов

 при поступлении к арбитру нескольких запросов

каждый из них имеет равные шансы на обслуживание. Возможный конфликт раз-
решается арбитром. Такая схема принята в асинхронных системах.

В

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

 (LRU, Least Recently Used) после

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

Помимо рассмотренных существует несколько алгоритмов смены приоритетов,

которые не являются чисто динамическими, поскольку смена приоритетов проис-

ходит не после каждого цикла арбитража. К таким алгоритмам относятся:

• алгоритм очереди (первым пришел — первым обслужен);
• алгоритм фиксированного кванта времени.

В

 алгоритме очереди

 запросы обслуживаются в порядке очереди, образовав-

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

редко.

Арбитраж шин 173

В

 алгоритме фиксированного кванта времени

 каждому ведущему для захвата

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

Схемы арбитража

Арбитраж запросов на управление шиной может быть организован по централизо-
ванной или децентрализованной схеме. Выбор конкретной схемы зависит от тре-

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

Централизованный арбитраж

При

 централизованном арбитраже

 в системе имеется специальное устройство —

центральный арбитр, —

 ответственное за предоставление доступа к шине только

одному из запросивших ведущих. Это устройство, называемое иногда

 централь-

ным контроллером шины,

 может быть самостоятельным модулем или частью ЦП.

Наличие на шине только одного арбитра означает, что в централизованной схеме

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

лизованного арбитража можно подразделить на параллельные и последователь-

ные.

В параллельном варианте центральный арбитр связан с каждым потенциаль-

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

арбитража называют

 централизованным параллельным арбитражем

 или

 центра-

лизованным арбитражем независимых запросов.

Идею централизованного параллельного арбитража на примере восьми веду-

щих устройств иллюстрирует рис. 4.11,

 а.

Здесь и далее под «текущим ведущим» будем понимать ведущее устройство,

управляющее шиной в момент поступления нового запроса. Устройство, выста-

вившее запрос на управление шиной, будем называть «запросившим ведущим».
Сигналы запроса шины (ЗШ) поступают на вход центрального арбитра по индиви-

дуальным линиям. Ведущему с номером

 i,

 который был выбран арбитром, также

по индивидуальной линии возвращается сигнал предоставления шины (ПШ,). Ре-
ально же занять шину новый ведущий сможет лишь после того, как текущий веду-
щий (пусть он имеет номер j) снимет сигнал занятия шины (ШЗ). Текущий веду-
щий должен сохранять сигналы ШЗ и 3Шj активными в течение всего времени, пока

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

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

174 Глава 4. Организация шин

Рис. 4.11. Централизованный параллельный арбитраж: а — общая схема;

б —

 возможная реализация

Логика выбора одного из запрашивающих ведущих обычно реализуется аппа-

ратными средствами. В качестве примера рассмотрим реализацию системы цент-
рализованного параллельного арбитража для статических приоритетов (рис. 4.11, б).
Пусть имеется восемь потенциальных ведущих 7-0, восемь сигналов запроса шины
ЗШ

7

-ЗШ

0

 и восемь соответствующих им сигналов предоставления шины ПШ

7

-ПШ

0

.

Положим, что приоритеты ведущих последовательно убывают с уменьшением их

номера. Если текущим является ведущий 3, то шину у него могут перехватить ве-

дущие с номерами от 4 до 7, а ведущие 0-2 этого сделать не могут. Ведущий 0
вправе использовать шину лишь тогда, когда она свободна, и должен освободить
ее по запросу любого другого ведущего. Схема статических приоритетов может
быть относительно просто реализована на основе логических выражений, которые
применительно к рассматриваемому примеру имеют вид:

Устройства арбитража, реализующие систему статических приоритетов, обыч-

но выполняются в виде отдельных микросхем (например, SN74278 фирмы Texas

Арбитраж шин 175

Instruments), которые, с целью увеличения числа входов и выходов, могут объеди-
няться по каскадной схеме, что, однако, ведет к увеличению времени арбитража.

При наличии большого числа источников запроса центральный арбитр может

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

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

Схема централизованного параллельного арбитража очень гибка — вместо ста-

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

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

Второй вид централизованного арбитража известен как

 централизованный по-

следовательный арбитраж.

 В последовательных схемах для выделения запроса

с наивысшим приоритетом используется один из сигналов, поочередно проходя-
щий через цепочку ведущих, чем и объясняется другое название —

 цепочечный

 или

гирляндный арбитраж.

 В дальнейшем будем полагать, что уровни приоритета ве-

дущих устройств в цепочке понижаются слева направо.

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

различают три основных типа схем цепочечного арбитража: с цепочкой для сигна-

ла предоставления шины, с цепочкой для сигнала запроса шины (ЗШ) и с цепочкой
для дополнительного сигнала разрешения (РШ). Наиболее распространена схема

цепочки для сигнала

 ПШ (рис. 4.12).

Рис. 4.12. Централизованный последовательный арбитраж с цепочкой для сигнала

предоставления шины

Запросы от ведущих объединяются на линии запроса шины по схеме «монтаж-

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