Циклическая очередь
Cтраница 2
Драйвер терминала направляет неграфические данные в циклическую очередь, откуда они либо выдаются на телетайп, либо выводятся на экран эмулятором алфавитно-цифрового дисплея. Каждый блок графических данных состоит из двух списков, разделенных дополнительной литерой SOM. Первый список является таблицей сообщений, содержащей команды языка L4, которые необходимо проинтерпретировать. Второй список представляет собой список данных, содержащий блоки данных переменной длины, связанные с каждой из команд L4 в таблице сообщений ( разд. [16]
Потоки реального времени, обслуживаемые по алгоритму FIFO, имеют наивысшие приоритеты и не могут прерываться другими потоками, за исключением такого же потока реального времени FIFO, перешедшего в состояние готовности. Потоки реального времени, обслуживаемые в порядке циклической очереди, представляют собой то же самое, что и потоки реального времени FIFO, но с тем отличием, что они могут прерываться таймером. Находящиеся в состоянии готовности потоки реального времени, обслуживаемые в порядке циклической очереди, выполняются в течение определенного кванта времени, после чего поток помещается в конец своей очереди. Ни один из этих классов на самом деле не является классом реального времени. [17]
 |
Очередь на основе связанного списка. [18] |
Недостатком данного способа является то, что требуется дополнительная память для указателей связанного списка NextCell и PrevCell. Это делает очереди на основе связанных списков менее эффективными, чем циклические очереди. [19]
МСВ, адрес которого указан в примитиве. Некоторый активный процесс может выполнить примитив PI ITMSG, чтобы записать адрес сообщения, ожидаемого другими процессами, в циклическую очередь, связанную с тем же блоком МСВ. Планировщик, обнаружив приход сообщения, исключает адрес сообщения из циклической очереди и передает его самому приоритетному процессу, находящемуся в очереди, связанной с рассматриваемым блоком МСВ. Затем планировщик определяет интервал времени Т, оставшийся до окончания тайм-аута, исключает процесс из очереди к блоку МСВ и включает в очередь к микропроцессору. Если ожидаемое сообщение не пришло в течение заданного тайм-аута, то планировщик возвращает ждущему процессу нулевой адрес сообщения и затем поступает с этим процессом так же, как в предыдущем случае. [20]
В рамках APG выполнением заданий управляет SRM, причем разным приоритетам соответствуют разные стратегии управления. Процессам с приоритетами 70 и 71 процессорное время выделяется стандартными порциями на основе простейшего принципа квантования, процессы с приоритетами 72 - 76 обслуживаются по способу циклической очереди с упорядочением по среднему времени непрерывной работы, а к процессам с приоритетом 7В применяется стратегия вращения. Остальные же процессы образуют обычную очередь, из которой для запуска всякий раз выбирается процесс с наибольшим приоритетом. [21]
 |
Удаление элемента из циклической очереди.| Пустая и полная циклические очереди. [22] |
Иногда сложно бывает отличить полную циклическую очередь от пустой. В обоих случаях начало и конец очереди совпадают. На рис. 3.5 показаны две циклические очереди, одна пустая, а другая полная. [23]
МСВ, адрес которого указан в примитиве. Некоторый активный процесс может выполнить примитив PI ITMSG, чтобы записать адрес сообщения, ожидаемого другими процессами, в циклическую очередь, связанную с тем же блоком МСВ. Планировщик, обнаружив приход сообщения, исключает адрес сообщения из циклической очереди и передает его самому приоритетному процессу, находящемуся в очереди, связанной с рассматриваемым блоком МСВ. Затем планировщик определяет интервал времени Т, оставшийся до окончания тайм-аута, исключает процесс из очереди к блоку МСВ и включает в очередь к микропроцессору. Если ожидаемое сообщение не пришло в течение заданного тайм-аута, то планировщик возвращает ждущему процессу нулевой адрес сообщения и затем поступает с этим процессом так же, как в предыдущем случае. [24]
Потоки реального времени, обслуживаемые по алгоритму FIFO, имеют наивысшие приоритеты и не могут прерываться другими потоками, за исключением такого же потока реального времени FIFO, перешедшего в состояние готовности. Потоки реального времени, обслуживаемые в порядке циклической очереди, представляют собой то же самое, что и потоки реального времени FIFO, но с тем отличием, что они могут прерываться таймером. Находящиеся в состоянии готовности потоки реального времени, обслуживаемые в порядке циклической очереди, выполняются в течение определенного кванта времени, после чего поток помещается в конец своей очереди. Ни один из этих классов на самом деле не является классом реального времени. [25]
Потоки реального времени, обслуживаемые по алгоритму FIFO, имеют наивысшие приоритеты и не могут прерываться другими потоками, за исключением такого же потока реального времени FIFO, перешедшего в состояние готовности. Потоки реального времени, обслуживаемые в порядке циклической очереди, представляют собой то же самое, что и потоки реального времени FIFO, но с тем отличием, что они могут прерываться таймером. Находящиеся в состоянии готовности потоки реального времени, обслуживаемые в порядке циклической очереди, выполняются в течение определенного кванта времени, после чего поток помещается в конец своей очереди. Ни один из этих классов на самом деле не является классом реального времени. [26]
Циклические очереди с обратной связью состоят из п подоче-редей. Существует правило, по которому можно определить конкретную подочередь, соответствующую данной программе. Кроме того, между программами, относящимися к различным подочере-дям, возникают особые отношения. Принципиальная структура циклической очереди с обратной связью изображена на рис. 10.4. Стрелки означают, что по завершении некоторого фиксированного интервала обслуживания программа может либо остаться в своей подочереди, либо переместиться в другую. Правила перемещения программ в подочередях иногда окончательно устанавливаются при создании системы, а иногда допускают параметризацию в процессе ее установки. [27]
 |
Планировщик системы UNIX основан на структуре многоуровневой очереди. [28] |
Когда запускается ( низкоуровневый) планировщик, он ищет очередь, начиная с самого высокого приоритета ( то есть с наименьшего отрицательного значения), пока не находит очередь, в которой есть хотя бы один процесс. После этого в этой очереди выбирается и запускает первый процесс. Ему разрешается работать в течение некоего максимального кванта времени, как правило, 100 мс, или пока он не заблокируется. Если процесс использует весь свой квант времени, он помещается обратно, в конец очереди, а алгоритм планирования запускается снова. Таким образом, процессы, входящие в одну группу приоритетов, совместно используют центральный процессор в порядке циклической очереди. [29]
Страницы: 1 2