Планирование процессов на основе приоритетов
При приоритетном выборе работам присваивается приоритет. Существует два вида приоритетного обслуживания:
-с относительными приоритетами (ОП);
-с абсолютными приоритетами (АП).
Обслуживание с относительными приоритетами
При использовании
относительных приоритетов обработка
заявок организуется по схеме?
представленной на рисунке ?. Заявкам
типа
,
...,
присвоены относительные приоритеты 1,
…, М
соответственно.
Заявка
,
поступившая в систему, заносится в
очередь
,
в которой хранятся заявки приоритета
В очереди
заявки упорядочены по времени поступления.
Когда процессор ЦП/ОП
заканчивает
ранее начатое обслуживание, то управление
передается программе ПЛАНИРОВЩИК
(ДИСПЕТЧЕР). Он выбирает на обслуживание
заявку с наибольшим приоритетом –
заявку
,
если очереди
,
...,
не содержат заявок. Выбранная заявка
захватывает процессор на все время
обслуживания. Таким образом, вновь
поступивший запрос с более высоким
приоритетом не прерывает выполнение
текущей заявки. Сравнение приоритетов
производится только по завершении
текущей работы.
Рисунок 2.10 - Модель обработки заявок с относительными приоритетами
Используя коэффициенты вариации длительности обслуживания, можно представить формулу времени ожидания обслуживания работы, имеющей k-ый приоритет в виде:
–
загрузка
процессора заявками, имеющими более
высокий приоритет, чем рассматриваемая
(k-я);
– загрузка процессора заявками, имеющими
более высокий и равный приоритет с
рассматриваемой;
Обслуживание с относительными приоритетами уменьшает время ожидания заявок с высоким приоритетом и увеличивает время ожидания для заявок с низким приоритетом по сравнению с бесприоритетным обслуживанием. В качестве недостатка такого способа обслуживания следует отметить, что низкоприоритетные работы могут захватить процессор на длительный период времени. Этот факт в вычислительных системах реального времени зачастую является недопустимым.
Обслуживание с абсолютными приоритетами
В ряде случаев время ожидания высокоприоритетных заявок нужно уменьшить до минимума, который недостижим при использовании относительных приоритетов. Этого можно достичь, если при поступлении высокоприоритетной заявки обслуживание ранее поступившей заявки с низким приоритетом прерывается, и процессор тут же предоставляется для обслуживания высокоприоритетной заявки. Дисциплина обслуживания, при которой высокоприоритетная заявка прерывает обслуживание заявки с низким приоритетом, называется дисциплиной обслуживания с абсолютными приоритетами.
При использовании
абсолютных приоритетов обслуживание
заявок организуется по схеме, представленной
рисунке , где заштрихованный квадрат
обозначает прерванную заявку. Для
каждого потока заявок
,
...,
организуется очередь
,
...,
,
в которой заявки размещаются в порядке
поступления. Заявкам
,
...,
соответствуют
абсолютные
приоритеты
Если подсистема процессор-память занята
обслуживанием заявки
и на вход поступает заявка типа
,
то при
заявка
заносится в конец очереди
,
а при
обслуживание заявки
прерывается, заявка
заносится в начало очереди
и ПЛАНИРОВЩИК переключает прибор на
обслуживание заявки
.
Рисунок 2.11 - Модель обработки заявок с абсолютными приоритетами.
Обслуживание
прерванных заявок может проводиться
двумя способами: 1) от начала; 2) от момента
прерывания (дообслуживание). Чаще
используется второй способ – дообслуживание
прерванных заявок, хотя он в реализации
сложнее, но обеспечивает более высокую
производительность. В случае, когда
длительность обслуживание распределена
по экспоненциальному закону, среднее
время дообслуживания совпадает со
средним временем обслуживания заявки.
Когда прерывание предполагает
дообслуживание, сохраняется вся
информация о процессе обслуживания,
необходимая для возобновления
(продолжения) обслуживания. Если потоки
заявок – простейшие с интенсивностями
,
математические ожидания и вторые
начальные моменты длительностей
обслуживания равны соответственно
и
,
и
прерванные заявки
дообслуживаются от точки прерывания,
то среднее время ожидания заявки с
абсолютным приоритетом
.
Сопоставление с
полученным временем ожидания для
дисциплины обслуживания с относительными
приоритетами, показывает, что при
обслуживании с абсолютными приоритетами
длительность ожидания заявок
-го
приоритета изменяется на величину
,
где первое слагаемое определяет влияние заявок более высокого приоритета, прерывающих обслуживание заявок данного потока, а второе слагаемое учитывает уменьшение времени ожидания заявок с меньшими приоритетами.
Эффект от использования абсолютных приоритетов иллюстрируется на рисунке __, где ОП – кривая относительного приоритета; АП – кривая абсолютного приоритета.
Рисунок 2.12- Среднее время ожидания заявок с бесприоритетным обслуживанием, с относительными и абсолютными приоритетами
Присваивание заявкам абсолютных приоритетов приводит к уменьшению времени ожидания заявок с высокими приоритетами, но одновременно с этим увеличивается время ожидания низкоприоритетных заявок.
3.