Алгоритмы планирования спорадических и апериодических задач

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

1. а) Планирование спорадической задачи, как фоновой задачи.

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

Рис.8.

Создание отдельной задачи не является обязательным.

б) Спорадическая задача как фоновая (без создания дополнительного процесса).

В а) – выделяют фиксированное время, а не любое свободное.

В б) – задача будет иметь приоритет общий с другими фоновыми задачами и ставится в очередь фоновых задач.

2. «Политика выбора».

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

Рис.9.

Данная задача должна запускаться в строго установленное время запуска (T_з).

Недостатки: несовместимость циклического характера алгоритма и случайного характера спорадических задач.

Достоинства: позволяет четко спланировать время исполнения всех задач (самый определяющий алгоритм).

3. Обмен приоритетом.

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

Динамическое назначение приоритета позволяет изменять его в процессе функционирования системы.

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

Рис.10.

Зсз – задача спорадических задач

з1…з4 – задачи

р – приоритет

М1 – метка (Q1)

(1 цикл)

(2 цикл)

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

4. Деферабельный сервер.

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

Зсз (p:max(p)+1)

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

Рис.11.

tсз =

Пока t₀>0 производится запуск спорадической задачи, иначе спорадическая задача не запускается. В процессе функционирования системы данная задача может прерывать периодические задачи несколько раз в зависимости от получения спорадических запросов.

5. Спорадический сервер.

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

Рис.12.

Сама задача времени исполнения должна иметь наивысший приоритет. Данный сервер включает лишь одну задачу – изменение очереди задач.

Каждый алгоритм можно оценить с точки зрения производительности. Для оценки производительности используются 3 параметра:

1. Нагрузка системы на отказ (в обслуживании).

Breakdown Utilization (BU).

2. Нормализованное среднее время ответа (NMRT).

3. Гарантируемая скорость обработки задач (GR).

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

Нормализованное среднее время ответа (NMRT) - это отношение между интервалами времени от готовности задачи к выполнению до ее окончания к фактическому времени процессора. Используется для выполнения задач.

Чем больше NMRT, тем больше время простоя задач.

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

Если число больше 1, то система расписабельная, иначе – нерасписабельная. Чем больше это число, тем больше запас времени для выполнения задач.

Планировщик заданий

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

Планировщики бывают разных видов:

1. Глобальный (общий) планировщик – во-первых, распределяет задачи между несколькими вычислительными узлами в распределённой вычислительной системе. Обычно реализуется на узле типа server, либо на одном из узлов системы при децентрализованном управлении. Во-вторых, создаёт алгоритмы формирования образа узлов.

2. Местный планировщик – распределяет задачи на одном вычислительном узле за заданный цикл функционирования. Работа планировщиков на различных узлах является независимой.

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

Планировщик заданий определяет:

1. Последовательность выполнения задач.

Каждый цикл функционирования узла планировщик может определять новую последовательность задач.

2. Распределение ресурсов между задачами.

Служит для борьбы с гонками.

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

3. Распределение времени между задачами.

Выделение заданного количества тиков для задачи, исполняющейся на узле.

Время – наиболее актуальный параметр.

Тик – минимальная измеряемая единица времени.

Количество тиков зависит от разных параметров:

1. частота процессора;

2. время одного цикла.

Дата добавления: 2014-01-04