Курс лекций Операционным системам и среды (стр. 12 из 21)

Планирование с использованием приоритетов может быть как вытесняющим, так и невытесняющим.

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

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

Пример. Пусть в очередь процессов, находящихся в состоянии готовность, поступают те же процессы, что и в примере для вытесняющего алгоритма «Кратчайшее задание - первое», только им дополнительно еще присвоены приоритеты (см. табл. 4). В вычислительных системах не существует определенного соглашения, какое значение приоритета – 1 или 4 считать более приоритетным. Во избежание путаницы, во всех наших примерах мы будем предполагать, что большее значение соответствует меньшему приоритету, т. е. наиболее приоритетным в нашем примере является процесс p4, а наименее приоритетным – процесс p1.

Таблица 4

Процесс	Время появления	Время выполнения	Приоритет
P1	0	6	4
P2	2	2	3
P3	6	7	2
P4	0	5	1

Как будут вести себя процессы при использовании невытесняющего приоритетного планирования?

Первым для выполнения в момент времени t = 0 выбирается процесс p4, как обладающий наивысшим приоритетом. После его завершения в момент времени t = 5 в очереди процессов, готовых к исполнению, окажутся два процесса p1 и p2. Больший приоритет из них у процесса p2, он и начнет выполняться. Затем в момент времени t = 7 для исполнения будет избран процесс p3, и лишь потом – процесс p1.

Рис. 15. Диаграмма процессов при невытесняющем приоритетном планировании

Иным будет предоставление процессора процессам в случае вытесняющего приоритетного планирования. Первым, как и в предыдущем случае, начнет исполняться процесс p4, а по его окончании – процесс p2. Однако в момент времени t = 6 он будет вытеснен процессом p3 и продолжит свое выполнение только в момент времени t = 13. Последним, как и раньше, будет исполняться процесс p1 (рис. 16).

Рис. 16. Диаграмма процессов при вытесняющем приоритетном планировании

Планирование в системах реального времени

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

и на его обработку уходит секунд работы процессора, все потоки могут быть своевременно обработаны только при выполнении условия: (k – количество доступных процессоров). Система реального времени, удовлетворяющая этому условию, называется поддающейся планированию или планируемой.

Соотношение

является просто частью процессорного времени, используемого процессом i, а сама сумма – это коэффициент использования (или коэффициент загруженности) процессора, который, естественно, не может быть больше 1.

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

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

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

Пример: Алгоритмы планирования будем рассматривать на примере 3 периодических процессов A, B, C. Предположим, что процесс A запускается с периодом 30 мс и временем обработки 10 мс. Процесс B имеет период 40 мс и время обработки 15 мс. Процесс C запускается каждые 50 мс и обрабатывается за 5 мс. Суммарно эти процессы потребляют 0,808 процессорного времени, что меньше единицы. Соответственно, система в данном примере поддается планированию.

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

Рис. 16. Три периодических процесса с разным периодом и временем обработки

Классическим примером статического алгоритма планирования реального времени для прерываемых периодических процессов является алгоритм RMS (Rate Monotonic Scheduling – планирование с приоритетом, пропорциональным частоте). Этот алгоритм может использоваться для процессов, удовлетворяющих следующим условиям:

1) Каждый периодический процесс должен быть завершен за время его периода

2) Ни один процесс не должен зависеть от любого другого процесса

3) Каждому процессу требуется одинаковое процессорное время на каждом интервале

4) У непериодических процессов нет жестких сроков

5) Прерывание процесса происходит мгновенно, без накладных расходов.

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

Алгоритм RMS работает, назначая каждому процессу фиксированный приоритет, обратно пропорциональный периоду и, соответственно, прямо пропорциональный частоте возникновения событий процесса. Например, в примере рис. 16 процесс A запускается каждые 30 мс (33 раза в секунду) и получает приоритет 33. Процесс B запускается каждые 40 мс (25 раз в секунду) и получает приоритет 25. Процесс C запускается каждые 50 мс (20 раз в секунду) и получает приоритет 20. Отметим, что реализация алгоритма требует, чтобы у всех процессов были разные приоритеты.

Во время работы планировщик всегда запускает готовый к работе процесс с наивысшим приоритетом, прерывая при необходимости работающий процесс с меньшим приоритетом. Таким образом, в нашем примере процесс A может прервать процессы B и C, процесс B может прервать C. Процесс C всегда вынужден ждать, пока процессор не освободится.

На рис. 17 показана работа алгоритма планирования для процессов A, B, C.

· Изначально все три процесса готовы к работе.

· Выбирается процесс с максимальным приоритетом – A. Ему разрешается работать в течение 10 мс, требующихся процессу до завершения.

· Когда процесс A освобождает процессор, начинает работать процесс B, а затем процесс C.

· Вместе эти процессы потребляют 30 мс, поэтому, когда процесс C заканчивает работу, снова запускается процесс A.

· Этот цикл повторяется до тех пор, пока в момент времени 70 мс у системы начинается период простоя.

· В момент времени 80 мс процесс B переходит в состояние готовности и запускается.

· Однако в момент времени 90 мс процесс A, обладающий более высоким приоритетом, также переходит в состояние готовности. Поэтому он прерывает выполнение процесса B и работает до момента времени 100 мс, пока не закончит свою работу.

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

Рис. 17. Пример алгоритмов планирования RMS и EDF

Алгоритм RMS может быть использован только при не слишком высокой загруженности процессора. Предположим, что процесс A имеет продолжительность работы не 10 мс, а 15 мс. Коэффициент использования процессора в таком случае равен 0,975. Теоретически для данного случая должен иметься метод планирования. Работа алгоритма показана на рис. 18.

· На этот раз процесс B завершает обработку к моменту времени 30 мс.

· В этот же момент процесс A снова приходит в состояние готовности. К тому времени, когда он заканчивает работу, снова готов процесс B и поскольку у него приоритет больше, чем у C, то запускается процесс B.

· Процесс C пропускает свой критический срок, алгоритм RMS терпит неудачу.

Рис. 18. Пример, в котором алгоритм RMS не может быть использован