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

 

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

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

· простая циклическая смена приоритетов;

· циклическая смена приоритетов с учетом последнего запроса;

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

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

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

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

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

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

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

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

В алгоритме наиболее давнего использования (LRU, Least Recently Used) после каждого цикла арбитража наивысший приоритет присваивается ведущему, кото­рый дольше чем другие не использовал шину.

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

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

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

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

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