Профиль выполнения двух периодических заданий

Процесс	Время поступления	Время выполнения	Предельное время окончания
А(1) А(2) А(3) А(4) А(5) . . В(1) В(2) .	. . .	. . .	. . .

Компьютер может принимать решение о планировании каждые 10 ms.

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

Если задание А имеет более высокий приоритет, задание В1 получит только 20 ms процессорного времени в двух смежных интервалах по 10 ms; после этого будет достигнуто предельное время его выполнения, и задание В1 выполнено не будет. Если более высокий приоритет получит задание В, то выполниться в срок не сможет задание А1.

Временная диаграмма на рис.4.1,г показывает применение в данной ситуации планирования с наиболее ранним предельным сроком. В момент времени t=0 поступают задания А1 и В1. Поскольку предельный срок А1 наступает раньше предельного срока В1, сперва выполняется задание А1. После его завершения начинается выполнение В1. В момент времени t=20 в систему поступает задание А2, предельный срок которого наступает раньше предельного срока В1. Соответственно, задание В1 прерывается, и начинается выполнение задания А2. Выполнение В1 продолжается, начиная с момента t=30. В момент t=40 в систему поступает задание А3, предельный срок которого, однако, более поздний, чем предельный срок задания В1, так что задание В1 продолжает выполнение до завершения в момент времени t=45. В этот момент начинается
выполнение задания А3, завершающееся к моменту t=55 и т.д.

В этом примере, где в каждой точке вытеснения планировщик дает высший приоритет тому заданию, предельный срок которого наступает раньше, удовлетворяются все требования к системе реального времени, т.е. задания А и выполняются без опоздания. Здесь использовано статическое планирование на основе таблиц, поскольку задания периодичны и предсказуемы. Анализ расписания выполнения заданий необходимо провести на временном интервале, равном наименьшему общему кратному (НОК) периодов поступления заданий (процессов). В рассмотренном примере период анализа расписания равен НОК(20,50)=100 ms.

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

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

Таблица 4.2.

Профиль выполнения пяти непериодических заданий

Процесс	Время поступления	Время выполнения	Предельное время начала работы
A B C D E

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

Если предельное время заданий известно до того, как задания становятся готовыми к выполнению, можно усовершенствовать эту систему планирования. Усовершенствованная система, именуемая планированием с наиболее ранним предельным сроком начала со свободным временем простоя, работает следующим образом. Планировщик всегда запускает подходящее задание с наиболее ранним предельным сроком начала, которое выполняется до полного завершения. Подходящее задание может оказаться не готовым, и это может привести к тому, что несмотря на наличие готовых к выполнению заданий процессор простаивает. В рассматриваемом примере система воздерживается от выполнения задания А, несмотря на то что это единственное готовое к выполнению задание. В результате, хотя процессор и не используется с максимальной эффективностью, все требования к предельным срокам начала выполнения заданий в примере при таком планировании удовлетворены. И, наконец, для сравнения на нижней части рис.4.2 приведен результат использования стратегии FCFS «первым поступил – первым обслужен». Как видно, в этом случае отклоненными оказываются два задания – В и Е.

4.3.Частотно-монотонное планирование

Одним из эффективных методов планирования для периодических задач является частотно-монотонное плани­рование (rate monotonic scheduling — RMS). Система RMS назначает приоритеты заданиям на основе их периодов.

На рис. 4.3 представлены параметры периодических заданий. Пери­од задания Т представляет собой интервал времени между поступлениями двух последовательных заданий одного типа. Частота заданий, измеряемая в Гц, представляет собой величину, обратную периоду (в секундах). Например, зада­ние с периодом 50 ms имеет частоту 20 Гц. Обычно окончание периода задания является жестким предельным сроком завершения задания, хотя некоторые за­дания могут иметь и более ранние предельные сроки. Время выполнения (вычисления) С представляет собой количество процессорного времени, требую­щегося для каждого задания определенного типа. Очевидно, что в однопроцес­сорной системе время выполнения не должно превышать период заданий (т.е. должно выполняться ). Если периодическое задание всегда выполняется до полного завершения, т.е. если не имеется отклоненных из – за нехватки вычисли­тельного ресурса заданий, то загруженность процессора этим заданием равна U = С/Т. Например, если задание имеет период 80 ms и время выполнения 55 ms, то загруженность им процессора составляет 55/80 = 0.6875.

В частотно-монотонном планировании заданием с наивысшим приоритетом является задание с наименьшим периодом; вторым по приоритетности является задание со вторым по величине пе­риодом и т.д. Соответственно, в случае готовности для выполнения нескольких зада­ний первым обслуживается задание с наименьшим периодом. Если изобразить приоритеты заданий как функцию их частоты, то получается монотонно возрастающая функция (рис. 4.4), откуда и происходит название метода.

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

(4.1)

Сумма загруженности процессора разными заданиями не может превышать единицу, что соответствует полной загрузке процессора. Неравенство (4.1) определяет верхнюю границу количества заданий, которые может успешно обслуживать идеальный алгоритм планирования. Для конкретного реального алгоритма гра­ница может оказаться ниже из-за затрат ресурсов процессора на планирование и диспетчеризацию. В /13/ показано, что для алгоритма RMS справедливо следующее неравенство:

(4.2)

В табл. 4.3 приведены некоторые значения верхней границы загруженности процессора для метода RMS для разных значений n в (4.2). При возрастании количества заданий верхняя граница стремится к значе­нию In 2 =0.693.

Таблица 4.2.

Значения верхней границы загруженности процессора для метода RMS

n
	1.000
	0.828
	0.779
	0.756
	0.743
	0.734
*	*
*	*

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

задание P₁: C₁ = 20; Т₁ = 100;

задание P₂: С₂ = 40; T₂ = 150;

задание Р₃: С₃ = 100; T₃= 350;

Загруженность процессора каждым из заданий составляет соответственно: U₁= 0,2; U₂= 0,267; U₃= 0,286. Тогда общая загруженность процессора тремя заданиями составляет U_o=0,2+0,267+0,286=0,753.

Верхняя граница загруженности этих трех задач при использовании метода RMS составляет:

.

Поскольку общая загруженность процессора по обработке приведенных за­даний ниже верхней границы для метода RMS (0,753<0,779), можно сделать вывод, что при RMS-планировании будут успешно выполнены все задания.

В /13/ указывается, что определяемая выражением (4.2) верхняя граница справедлива и для метода наиболее раннего предельного срока. Хотя при применении планирования с наиболее ранним предельным сроком можно достичь более высокой загрузки про­цессора и, соответственно, обработать большее количество заданий, ме­тод RMS широко распространен и используется во многих промышленных приложе­ниях.

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

Упражнение 4.2. Для группы непериодических задач с заданным профилем построить временные диаграммы их выполнения для следующих алгоритмов планирования: с заданными предельными сроками начала работы; предельными сроками начала и свободным временем простоя.

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

ПЛАНИРОВАНИЕ В WINDOWS 2000