Лекция: Примеры построения диаграмм выполнения процессов

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

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

Пример 1. В качестве примера планирования периодических заданий с предельным временем завершения рассмотрим систему, которая собирает и обрабатывает данные от двух датчиков — А и В /13/. Сроки сбора данных от датчика А – каждые 20 ms, датчика В – 50 ms. Процесс снятия данных, включая накладные расходы ОС, занимает для датчика А – 10 ms, а для датчика В – 25 ms. В табл.2.1 приведен профиль выполнения этих двух заданий, а на рис.2.2, а – времена поступления, выполнения и предельные времена для заданий А и В.

Таблица 2.1.

Профиль выполнения заданий А и В для примера 1

Вычислительная система может принимать решение о планировании каждые 10 ms.

Предположим, что при этих условиях используется схема планирования с приоритетами. Результат показан на двух временных диаграммах на рис.2.2, б и 2.2, в. Если задание А имеет более высокий приоритет, задание В1 получит только 20 ms процессорного времени в двух смежных интервалах по 10 ms; после этого будет достигнуто предельное время его выполнения, и задание В1 выполнено не будет. Если более высокий приоритет получит задание В, то выполниться в срок не сможет задание А1. Временная диаграмма на рис.2.2, г показывает применение в данной ситуации планирования с наиболее ранним предельным сроком. В момент времени 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.

Далее в задании требуется принять меры для ликвидации опозданий процессов А и В в случаях планирования с фиксированными приоритетами. Одним из вариантов решения этой задачи является уменьшение времени СА и СВ выполнения процессов А и В, т.е. увеличения производительности процессора. Например, для случая, когда приоритет процесса А выше приоритета процесса В (рис.2.2, б), увеличение производительности процессора можно оценить величиной отношения ΔСВ/СВ, где ΔСВ – доля времени, какой не хватило процессу В для завершения работы без опоздания. После корректировки величин СА и СВ необходимо заново построить диаграмму и убедиться, что опоздания процесса В не будет. Также необходимо произвести корректировку выполнения процессов на рис.2.2, в.

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

Таблица 2.2.

Профиль выполнения заданий для примера 2

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

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

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

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

задание P1: C1 = 20; Т1 = 100;

задание P2: С2 = 40; T2 = 150;

задание Р3: С3 = 100; T3= 350.

Предпо­ложим, что у нас имеется n заданий, каждое из которых имеет свое фиксированное время выполнения и период. Известно, что для n процессов необходимое условие выполнения процессами предельных сроков задается следующим неравенством /13/:

.

В табл. 2.3 приведены некоторые значения верхней границы загруженности процессора для метода RMS для разных значений n. При возрастании количества заданий верхняя граница стремится к значе­ниюIn 2 =0,693.

Таблица 2.3.

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

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

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

.

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

Пример 4.Рассмотрим особенности алгоритмов планирования Windows XP/7 /5/.

В Windows XP/7 реализован вытесняющий планировщик, использующий как концепцию абсолютных приоритетов, так и концепцию квантования. На каждом из уровней класса приоритетов реального времени применяется циклическое (карусельное) RR планирование.

В классе переменных приоритетов также используется карусельное планирование, дополненное возможностью динамического изменения приоритета на основе текущей активности потоков /11-12/.

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

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

Код современных версий ОС Windows, отвечающий за планирование, реализован в ядре ОС. Совокупность процедур, выполняющих эти обязанности, называется диспетчером ядра (kernel`s dispatcher). Диспетчеризация потоков осуществляется при прерываниях уровня «DPC/dispatch» и инициируется событиями:

поток готов к выполнению (например создан или вышел из состояния ожидания);

поток выходит из состояния выполнения (например, квант истек, поток завершается или переходит в состояние ожидания);

приоритет потока изменяется в результате вызова системного сервиса или самой ОС Windows;

изменяется привязка к процессорам выполняемого потока (в случае мультипроцессорных SMP-систем).

После выбора нового потока ОС Windows переключает контекст. Эта операция заключается в сохранении параметров состояния вычислительной системы, связанных с выполняемым потоком, и загрузке аналогичных параметров для другого потока, после чего начинается выполнение нового потока.