 |
Структура алгоритмов распределения времени
|
|
|
|
Алгоритмы распределения времени центрального процессора (ЦП) определяют последовательность выполнения программ и по своей структуре могут быть приоритетными, бесприоритетными и смешанными.
В приоритетном алгоритме каждой программе присваивается приоритет, выражаемый целым числом k. Первой получает доступ к ЦП программа с высшим приоритетом. Программы с одинаковым приоритетом обрабатываются по алгоритму «первый пришел - первый обслужился» (FIFO).
Существуют два класса приоритетов: относительные и абсолютные. При относительных приоритетах, в отличие от абсолютных, появление новой программы, с более высоким приоритетом, не прерывает обрабатываемую программу. Кроме того, приоритеты подразделяются на статические и динамические. Если приоритет не изменяется с течением времени, он называется статическим, в противном случае – динамическим.
В бесприоритетных алгоритмах для каждой новой программы указывается правило постановки ее в очередь и задается предельное время (квант) ее первоначальной обработки (обслуживания). Формулируются также правила постановки в очередь или в несколько очередей недообслуженных программ после каждого нового кванта обслуживания, которые, имеют различную продолжительность. Предполагается, что программа, завершившая обслуживание, сразу же покидает очередь. Простейшим бесприоритетным алгоритмом является FIFO, согласно которому программы обрабатываются в порядке их поступления с бесконечным первоначальным квантом обслуживания. Другим примером является круговой циклический алгоритм (КЦ). Согласно КЦ алгоритму программы обслуживаются фиксированными квантами (например, по 100 нс), и недообслуженная программа ставится в конец очереди.
|
|
|
Поступающие
программы Обслуживание не закончено
Обслу-
живание
закончено
Рисунок 12.1 – Круговой циклический алгоритм
По количеству организуемых очередей из программ, ожидающих дообслуживания после получения определенного числа квантов, бесприоритетные алгоритмы делятся на одноуровневые (RR) и многоуровневые (FB). Простейший многоуровневый алгоритм устроен следующим образом. Организуется N очередей. Вновь поступающая программа занимает конец первой очереди. Первая программа из очереди с номером i >1 поступает на обработку только в том случае, когда очереди с номерами, меньшими i, пусты. При i < N она обрабатывается в течение кванта времени, равного Θi. Незавершенная программа из очереди с номером N-1 попадает в конец очереди с номером N. Программы из очереди с номером N обслуживаются по правилу FIFO, т.е. программы обрабатываются до конца без прерываний. Если программа выполнена, то на обработку сразу поступает следующая программа.
Поступающие
программы Обслуживание не закончено
Обслуживание
Закончено
Рисунок 12.2 – Простейший многоуровневый алгоритм
Смешанные алгоритмы представляют собой сочетание приоритетных и бесприоритетных алгоритмов. Более точно программы с одинаковым приоритетом обслуживаются по одному из бесприоритетных алгоритмов. Новая программа с более высоким приоритетом, чем та, которая в момент ее поступления находиться на обслуживании, получает доступ к ЦП сразу же после завершения обслуживания в течение текущего кванта. Введение приоритетов дает дополнительные возможности для ускорения обслуживания одних программ за счет замедления обслуживания других.
Осн. лит.102[9-16],
Доп. лит.6[6-12].
Контрольные вопросы:
1. В чем заключается сущность приоритетных и бесприоритетных дисциплины диспетчеризации?
|
|
|
2. В чем состоит суть линейных и циклических дисциплины обслуживания?
3. На какую характеристику обслуживания влияет трудоемкость решения задачи?
4. Как влияет квантование времени обслуживания на характеристики решения задачи?
5. Из чего формируется очередь запросов при циклической диспетчеризации?
|
|
|
