Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
для различных алгоритмов планирования
Приведем примеры построения диаграмм выполнения процессов для различных планировщиков мультипрограммных вычислительных систем.Эти примеры иллюстрируют выполнение задания №1 курсовой работы.
Пример 1. В качестве примера планирования периодических заданий с предельным временем завершения рассмотрим систему, которая собирает и обрабатывает данные от двух датчиков - А и В /13/. Сроки сбора данных от датчика А – каждые 20 ms, датчика В – 50 ms. Процесс снятия данных, включая накладные расходы ОС, занимает для датчика А – 10 ms, а для датчика В – 25 ms. В табл.2.1 приведен профиль выполнения этих двух заданий, а на рис.2.2, а – времена поступления, выполнения и предельные времена для заданий А и В.
Таблица 2.1.
Профиль выполнения заданий А и В для примера 1
Процесс | Время поступления | Время выполнения | Предельное время окончания |
А(1) А(2) А(3) А(4) А(5) . . В(1) В(2) . | . . . | . . . | . . . |
Вычислительная система может принимать решение о планировании каждые 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
Процесс | Время поступления | Время выполнения | Предельное время начала работы |
A B C D E |
При использовании такого подхода, несмотря на то, что задание 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
n | |
1.000 | |
0.828 | |
0.779 | |
0.756 | |
0.743 | |
0.734 | |
* | * |
* | * |
Загруженность процессора каждым из заданий составляет соответственно: 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 переключает контекст. Эта операция заключается в сохранении параметров состояния вычислительной системы, связанных с выполняемым потоком, и загрузке аналогичных параметров для другого потока, после чего начинается выполнение нового потока.
Дата публикования: 2015-04-10; Прочитано: 672 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!