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

выставляют запросы, эти запросы транслируются на вход центрального арбитра. Получив сигнал ЗЩ арбитр анализирует состояние линии занятия шины, и если шина свободна, формирует сигнал ПШ Сигнал предоставления шины последовательно переходит по цепочке от одного ведущего к другому. Если устройство, на которое поступил сигнал ПШ, не запрашивало шину, оно просто пропускает сигнал дальше по цепочке. Когда ПШ достигнет самого левого из запросивших ведущих, последний блокирует дальнейшее распространение сигнала ПШ по цепочке и берет на себя управление шиной.

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

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

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

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

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

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

Рис. 4.13. Схема децентрализованного параллельного арбитража

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

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

Под децентрализованный арбитраж может быть модифицирована также схема, приведенная на рис. 4.12. Подобный вариант, называемый кольцевой схемой, показан на рис. 4.14.

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

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

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

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

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

Идея подобного арбитража была предложена М. Таубом (Matthew Taub) в 1975 году. В алгоритме Тауба под арбитраж выделяются две группы сигнальных линий, доступные всем устройствам на шине. Устройства подключаются к этим линиям по схеме «монтажного ИЛИ». Первая группа служит для передачи сигналов синхронизации и управления. Вторую группу линий условно назовем шиной приоритета и обозначим В. В зависимости от принятого числа уровней приоритета эта группа может содержать от 4 до 7 линий. Каждому потенциальному ведущему назначается уникальный уровень приоритета. Приоритет Р представлен ^-разрядным двоичным кодом. Каждому разряду кода приоритета соответствует линия в шине В. Ведущие, претендующие на управление шиной, выдают на шину В свои коды приоритета Р. Дальнейшее поведение ведущих определяется следующим правилом: если i-й разряд кода приоритета равен О (Pj = 0), а на i-й линии шины В в данный момент присутствует единица (Bj = 1), то ведущий обнуляет в выставляемом коде все младшие разряды, от 0-го до /-го. В результате такой процедуры на шине В остается код наивысшего из выставленных приоритетов. Устройство, распознавшее на шине свой код приоритета, считается выигравшим арбитраж. После завершения своей транзакции выигравшее устройство снимает с шины В свой код приоритета, при этом ситуация на линиях В меняется. Ведущие, претендовавшие на шину, восстанавливают ранее обнуленные разряды, и начинается новый цикл арбитража.

Поясним алгоритм примером. Пусть в некоторый момент времени запрос на шину выставили три ведущих с номерами 10,8 и 5. Положим, что уровни приоритета ведущих совпадают с их номерами, то есть на четырехразрядную шину В будут выданы соответственно коды 1010₂ (10₁₀), 1000₂ (8₁₀) и 0101₂ (5₁₀). Так как над одноименными разрядами кодов выполняется операция логического сложения (устройства подключены к линиям по схеме «монтажного ИЛИ»), на шине В установится код 1111₂. Согласно рассмотренному выше правилу первое и второе устройства обязаны обнулить разряды с 2-го по 0-й (0-й разряд — младший), а третье — все разряды. В итоге на шине В установится новый код 1000₂, и первое устройство сможет немедленно восстановить ранее обнуленные разряды. Таким образом, на шине В будет код 1010₂, то есть код приоритета устройства с номером 10. Схема арбитража этого устройства опознает на шине свой уровень приоритета и захватит шину. После завершения транзакции устройство с номером 10 снимет свой код приоритета, а остальные два устройства восстановят свои. Далее начнется новая процедура арбитража.

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

Чтобы исключить постоянное блокирование ведущих, обладающих низким приоритетом, Тауб впоследствии модернизировал свою схему, дополнив ее модулем равнодоступности (fairness module). Модуль запрещает выигравшему ведущему выдавать новые запросы до завершения обслуживания всех ожидающих запро-

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

сов. Следует отметить, что это не гарантирует, а только помогает каждому ведущему получить право на управление шиной.

Вариации рассмотренной схемы широко используются в таких шинах, как Futurebus, NuBus, MultiBus II, Fastbus.

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

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

Ограничение времени управления шиной

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

Опросные схемы арбитража

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

Данный механизм использует специальные линии опроса между контроллером (контроллерами) шины и ведущими — по одной линии для каждого ведущего. С целью уменьшения числа таких линий может формироваться номер запрашивающего ведущего, для чего вместо 2" достаточно п линий. Кроме того, используются также линии запроса шины и линия сигнала занятия шины.

Централизованный опрос

Централизованный опрос Иллюстрирует рис. 4.15.

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

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

Организация децентрализованного опроса показана на рис. 4.16.

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

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

Протокол шины

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



	178 Глава 4. Организация шин ший на арбитражных линиях свой номер. Подобная схема известна также какрас-пределенный арбитраж с самостоятельным выбором, поскольку ведущий сам определяет, стал ли он победителем в арбитраже, то есть выбирает себя самостоятельно. Идея подобного арбитража была предложена М. Таубом (Matthew Taub) в 1975 году. В алгоритме Тауба под арбитраж выделяются две группы сигнальных линий, доступные всем устройствам на шине. Устройства подключаются к этим линиям по схеме «монтажного ИЛИ». Первая группа служит для передачи сигналов синхронизации и управления. Вторую группу линий условно назовем шиной приоритета и обозначим В. В зависимости от принятого числа уровней приоритета эта группа может содержать от 4 до 7 линий. Каждому потенциальному ведущему назначается уникальный уровень приоритета. Приоритет Р представлен ^-разрядным двоичным кодом. Каждому разряду кода приоритета соответствует линия в шине В. Ведущие, претендующие на управление шиной, выдают на шину В свои коды приоритета Р. Дальнейшее поведение ведущих определяется следующим правилом: если i-й разряд кода приоритета равен О (Pj = 0), а на i-й линии шины В в данный момент присутствует единица (Bj = 1), то ведущий обнуляет в выставляемом коде все младшие разряды, от 0-го до /-го. В результате такой процедуры на шине В остается код наивысшего из выставленных приоритетов. Устройство, распознавшее на шине свой код приоритета, считается выигравшим арбитраж. После завершения своей транзакции выигравшее устройство снимает с шины В свой код приоритета, при этом ситуация на линиях В меняется. Ведущие, претендовавшие на шину, восстанавливают ранее обнуленные разряды, и начинается новый цикл арбитража. Поясним алгоритм примером. Пусть в некоторый момент времени запрос на шину выставили три ведущих с номерами 10,8 и 5. Положим, что уровни приоритета ведущих совпадают с их номерами, то есть на четырехразрядную шину В будут выданы соответственно коды 1010₂ (10₁₀), 1000₂ (8₁₀) и 0101₂ (5₁₀). Так как над одноименными разрядами кодов выполняется операция логического сложения (устройства подключены к линиям по схеме «монтажного ИЛИ»), на шине В установится код 1111₂. Согласно рассмотренному выше правилу первое и второе устройства обязаны обнулить разряды с 2-го по 0-й (0-й разряд — младший), а третье — все разряды. В итоге на шине В установится новый код 1000₂, и первое устройство сможет немедленно восстановить ранее обнуленные разряды. Таким образом, на шине В будет код 1010₂, то есть код приоритета устройства с номером 10. Схема арбитража этого устройства опознает на шине свой уровень приоритета и захватит шину. После завершения транзакции устройство с номером 10 снимет свой код приоритета, а остальные два устройства восстановят свои. Далее начнется новая процедура арбитража. Описанная процедура связана с определенными затратами времени на стабилизацию на арбитражных линиях номера устройства-победителя. Это время должно быть учтено в протоколе шины. Чтобы исключить постоянное блокирование ведущих, обладающих низким приоритетом, Тауб впоследствии модернизировал свою схему, дополнив ее модулем равнодоступности (fairness module). Модуль запрещает выигравшему ведущему выдавать новые запросы до завершения обслуживания всех ожидающих запро-



	Арбитраж шин 179 сов. Следует отметить, что это не гарантирует, а только помогает каждому ведущему получить право на управление шиной. Вариации рассмотренной схемы широко используются в таких шинах, как Futurebus, NuBus, MultiBus II, Fastbus. В целом схемы децентрализованного арбитража потенциально более надежны, поскольку отказ контроллера шины в одном из ведущих не нарушает работу с шиной на общем уровне. Тем не менее должны быть предусмотрены средства для обнаружения неисправных контроллеров, например на основе тайм-аута. Основной недостаток децентрализованных схем — в относительной сложности логики арбитража, которая должна быть реализована в аппаратуре каждого ведущего. В некоторых ВМ применяют комбинированные последовательно-параллельные схемы арбитража, в какой-то мере сочетающие достоинства обоих методов. Здесь все ведущие разбиваются на группы. Арбитраж внутри группы ведется по последовательной схеме, а между группами — по параллельной. Ограничение времени управления шиной Вне зависимости от принятой модели арбитража должна быть также продумана .стратегия ограничения времени контроля над шиной. Одним из вариантов может быть разрешение ведущему занимать шину в течение одного цикла шины, с предоставлением ему возможности конкуренции за шину в последующих циклах. Другим вариантом является принудительный захват контроля над шиной устройством с более высоким уровнем приоритета, при сохранении восприимчивости текущего ведущего к запросам на освобождение шины от устройств с меньшим уровнем приоритета. Опросные схемы арбитража В опросных методах запросы только фиксируются, и контроллер шины способен узнать о них, лишь опросив ведущих. Опрос может быть как централизованным — с одним контроллером, производящим опрос, так и децентрализованным — с несколькими контроллерами шины. Данный механизм использует специальные линии опроса между контроллером (контроллерами) шины и ведущими — по одной линии для каждого ведущего. С целью уменьшения числа таких линий может формироваться номер запрашивающего ведущего, для чего вместо 2" достаточно п линий. Кроме того, используются также линии запроса шины и линия сигнала занятия шины. Централизованный опрос Централизованный опрос Иллюстрирует рис. 4.15. Контроллер шины последовательно опрашивает каждое ведущее устройство на предмет, находится ли оно в ожидании предоставления шины. Для этого контроллер выставляет на линии опроса адрес соответствующего ведущего. Если в момент выставления адреса ведущий ожидает разрешения на управление шиной, то он, •распознав свой адрес, сигнализирует об этом, делая активной шину (ЗШ). Обнаружив сигнал, контроллер разрешает ведущему использовать шину. Последовательность опроса ведущих может быть организована в порядке убывания адресов, либо меняться в соответствии с алгоритмом динамического приоритета.





	Децентрализованный опрос Организация децентрализованного опроса показана на рис. 4.16. Каждый ведущий содержит контроллер шины, состоящий из дешифратора адреса и генератора адреса. В начале опросной последовательности формируется адрес, который распознается контроллером. Если соответствующий ведущий ожидает доступа к шине, он вправе теперь ее занять. По завершении работы с шиной контроллер текущего ведущего генерирует адрес следующего ведущего, и процесс повторяется. При такой схеме обычно требуется применять систему с квитированием, использующую сигнал ЗЩ формируемый генератором адреса, и сигнал ПЩ генерируемый дешифратором адреса.



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

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