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

Другим популярным алгоритмом планирования является алгоритм EDF (Earliest Deadline First – процесс с ближайшим сроком завершения в первую очередь). Алгоритм EDF представляет собой динамический алгоритм, не требующий от процессов периодичности. Он также не требует и постоянства временных интервалов использования процессора. Каждый раз, когда процессу требуется процессорное время, он объявляет о своем присутствии и о своем сроке выполнения задания. Планировщик хранит список процессов, сортированный по срокам выполнения заданий. Алгоритм запускает первый процесс в списке, то есть тот, у которого самый близкий по времени срок выполнения. Когда новый процесс переходит в состояние готовности, система сравнивает его срок выполнения со сроком выполнения текущего процесса.

Если у нового процесса график более жесткий, он прерывает работу текущего процесса. Пример работы алгоритма EDF показан на рис. 17.

· Вначале все процессы находятся в состоянии готовности. Они запускаются в порядке своих крайних сроков.

· Процесс A должен быть выполнен к моменту времени 30, процесс B должен закончить работу к моменту времени 40, процесс C – 50. Таким образом, процесс A запускается первым. Вплоть до момента времени 90 выбор алгоритма EDF не отличается от RMS.

· В момент времени 90 процесс A переходит в состояние готовности с тем же крайним сроком выполнения 120, что и у процесса B.

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

Рассмотрим рис. 18.

· В момент времени 30 между процессами A и C возникает спор. Поскольку срок выполнения процесса C равен 50 мс, а процесса A – 60 мс, планировщик выбирает процесс C. Этим данный алгоритм отличается от алгоритма RMS, в котором побеждает процесс A, как обладающий большим приоритетом.

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

· Алгоритм EDF работает с любым набором процессов, для которых возможно планирование. Платой за это является использование более сложного алгоритма.

Решение задач

Задача №7. Пользовательский процесс формирует 1 страницу текста для вывода на принтер, затрачивая на это 200 мс. Формирование новой страницы начинается, если начинает печататься предыдущая страница. Объем буфера равен одной странице. Страница содержит 50 строк текста. Принтер способен напечатать 8 строк за 1 секунду. Будет ли приостанавливаться пользовательский процесс и на какое время? Изменится ли ситуация, если объем буфера будет равен 2 страницам?

1. Определим, сколько времени тратится на печать 1 страницы текста.

8 строк печатается за 1 секунду50 строк печатается за t секунд

2. Начинает печататься страница, на это тратится 6250 мс. В это же время начинает формироваться новая строка, на это тратится 200 мс. Прежде, чем приступить к формированию новой строки, процесс должен ждать, пока завершиться печать: 6250-200=6050 мс.

3. Если объем буфера равен 2 страницам, то как только начинает печататься страница, пользовательский процесс формирует 2 строки, на это тратится 400 мс. Затем процесс ждет, пока закончиться печать страницы в течение: 6250-400=5850 мс.

Задача 2. В какой очереди предпочтительней выполнять процессы, если используется алгоритм FIFO: р1, р2, р3, р4 или р4, р2, р1, р3?

Процесс	Длительность
Р1	8
Р2	2
Р3	5
Р4	4

Данные:

Построим диаграммы процессов для каждой очереди и определим числовые характеристики:

р1, р2, р3, р4

Среднее время ожидания:

Среднее время выполнения:

р4, р2, р1, р3

Среднее время ожидания:

Среднее время выполнения:

Предпочтительней 2-я очередь.

Задача 3. Какой алгоритм предпочтительней использовать для планирования процессов р1, р2, р3, р4: циклический алгоритм с величиной кванта 3 или по кратчайшему времени поступления?

Процесс	Длительность
Р1	7
Р2	2
Р3	5
Р4	10

Данные:

Построим диаграммы процессов для каждой очереди:

Среднее время ожидания:

Среднее время выполнения:

Среднее время ожидания:

Среднее время выполнения:

Задача 4. Определить среднее время ожидания и выполнения процесса. Если используется алгоритм «кратчайшее задание - первое» и известно. Что процессы поступают с интервалом в 2 единицы времени.

Процесс	Длительность	Время поступления
Р1	8	0
Р2	2	2
Р3	5	4
Р4	4	6

Данные:

Построим диаграмму процессов:

Среднее время ожидания:

Среднее время выполнения:

Задача 5. Построить диаграммы процессов для невытесняющего и вытесняющего приоритетного планирования.

Процесс	Длительность	Приоритет	Время поступления
Р1	8	4	0
Р2	5	3	2
Р3	5	1	4
Р4	4	2	6

Данные:

Построим диаграмму процессов для невытесняющего алгоритма:

Построим диаграмму процессов для вытесняющего алгоритма:

Задача 6. Определить, поддается ли планированию 3-хпроцессорная система реального времени, если известны периоды и времена выполнения процессов:

Процесс	Период	Время выполнения
Р1	20	10
Р2	30	15
Р3	15	5
Р4	50	20

Проверим условие планируемости:

. Значит, система поддается планированию.

Задача №6. В систему реального времени поступают 4 периодических процесса с периодами 50, 100, 200, и Х мс. На обработку каждого процесса требуется 35, 20, 10, 15 мс времени процессора. Определить предельное значение Х, при котором система поддается планированию?

Составим условие планируемости:

1. Определим, сколько времени тратится на печать 1 страницы текста.

8 строк печатается за 1 секунду50 строк печатается за t секунд

Потоки и процессы

Мультипрограммирование, или многозадачность, - это способ организации вычислительного процесса, при котором на одном процессоре попеременно выполняются сразу несколько задач (программ).