3. Алгоритм минимальной неопределенности

Этот алгоритм также ориентирован на однопроцессорные системы.

Он использует те же самые (1) – (5) предположения.

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

d – c = l

назначается высочайший динамический приоритет.

Т.о. существуют алгоритмы планирования, которые дают высочайший приоритет задаче, у которой минимален определенный параметр:

1. d – предельный срок завершения (EDF - earliest deadline);

2. l – неопределенность (LL - least laxity) (минимальной неопределенности);

3. c – длительность (SJF – shortest job) (кратчайшее задание - первым);

4. d – t – срок, оставшийся до завершения (t- текущее время) (SRT – shortest remaining time) (задача с кратчайшим сроком завершения – первая)

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

При этом, существуют системы как со статическими приоритетами (алгоритм монотонной скорости), так и с динамическими приоритетами (все остальные).

Системы со статическими и динамическими приоритетами характеризуются следующими особенностями:

1. Системы со статическими приоритетами легче организовать, но они хуже реагируют на изменения окружающей ситуации;

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

Вот пример планирования с динамическими приоритетами, вычисляемыми по формуле:

Время ожидания + Время выполнения

Приоритет = ───────────────────────────────────

Время выполнения

Уменьшает недостатки варианта планирования SJF.

Т.к. время выполнения есть в знаменателе, то приоритет более короткой задачи выше, чем приоритет более длинной задачи.

Т.к. время ожидания есть в числителе, то приоритет задачи растет, если она более длительная и долгое время ждет.

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

4.7.3.2. Планирование зависимых задач

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

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

Таким образом, наличие ограничений предшествования и взаимного исключения скорее являются нормой, чем исключением.

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

Чрезвычайно дорого искать оптимальный план для множества зависимых задач.

Ресурсы, требуемые для решения проблемы динамического планирования, соразмерны с ресурсами, необходимыми для выполнения самих прикладных задач.

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

Существуют следующие пути выхода из этого трудного положения:

1. Использование мощных вычислительных ресурсов (например, многопроцессорность).

2. Деление проблемы планирования на две части. Одна часть может быть решена неоперативно (до выполнения), а вторая часть должна решаться во время выполнения.

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

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

Основной путь создания алгоритмов планирования зависимых задач – это модифицирование алгоритма монотонной скорости.

Протокол наследования приоритета и протокол предельного приоритета

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

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

Известно явление, называемое инверсией приоритета.

На примере его можно иллюстрировать следующим образом.

Есть 3 задачи Т1, Т2 и Т3 (Т1 имеет высший приоритет, а Т3 имеет низший приоритет), которые планируются алгоритмом монотонной скорости.

Т1 и Т3 требуют исключительного доступа к общему ресурсу, защищенному семафором С.

Пусть в какой-то момент времени низкоприоритетная задача Т3 владеет критическим ресурсом.

Пусть в этот момент высокоприоритетная задача Т1 запрашивает сервис.

Т1 должна ждать, пока Т3 не пройдет свой критический участок и не освободит семафор С.

Если в течение этого времени сервис запрашивает задача Т2, то он будет ей отдан, поскольку Т2 имеет более высокий приоритет, чем Т3.

Таким образом задача Т2 со средним приоритетом задерживает задачу Т3 и, следовательно, задачу Т1, задачу с высоким приоритетом.

Такое явление и называется инверсией приоритета.

Было предложено поднять приоритет низкоприоритетной задачи Т3, пока она находится в критической секции, до высокого приоритета блокированной задачи Т1, и, следовательно, устранить возможность того, что среднеприоритетная задача Т2 вмешается в течение критической секции низкоприоритетной задачи.

Это основная идея протокола наследования приоритета. Однако, анализ показал, что этот протокол может вести к цепным блокированиям и тупикам.

Чтобы решить эти проблемы и был разработан протокол предельного приоритета.

Вводится понятие предельного приоритета семафора, который определяется как приоритет самой приоритетной задачи, которая может захватить этот семафор.

Задаче Т позволено войти в критическую секцию, если только ее (задачи) назначенный приоритет выше, чем предельные приоритеты всех семафоров, захваченных в данный момент другими задачами.

Задача Т выполняется со своим назначенным приоритетом пока она в критической секции и не блокирует более приоритетные задачи.

Если она блокирует задачи, то она наследует приоритет самой высокоприоритетной задачи, которую она блокирует.

Когда она выходит из критической секции, она восстанавливает приоритет, который она имела в момент входа в критическую секцию.