10.7. Рекомендуемая литература

В [WEND89] представлено интересное обсуждение различных подходов к многопроцессорному планированию. В работах [KRIS94, STAN93, LEE93, TILB91] содержится важный материал, посвященный операционным системам и планированию реального времени. В [ZEAD97] выполнен анализ производитель­ности планировщика реального времени SVR4.

KRIS94 Krishna С., Lee Y., eds. Special Issue on Real-Time Systems. — Proceedings of IEEE, January 1994.

LEE93 Lee Y., Krishna C., eds. Readings in Real-Time Systems. — Los Alamitos CA: IEEE Computer Society Press, 1993.

STAN93 Stankovic J., Ramamritham K., eds. Advances in Real-Time Systems— Los Alamitos, CA: IEEE Computer Society Press, 1993.

TILB91 Tilborg A., Koob G,, eds. Foundations of Real-Time Computing: Scheduling and Resource Management. -- Boston: Kluwer Academic Publishers, 1991.

WEND89 Wendorf J., Wendorf R., Tokuda, H. Scheduling Operating System Processing on Small-Scale Microprocessors. "- Proceedings, 22nd Annual Hawaii International Conference on System Science, January 1989.

ZEAD97 Zeadally S. An Evaluation of the Real-Time Performance of SVR4.0-and SVR4.2. — Operating Systems Review, January 1,977.

10.8. Задачи

1. Рассмотрим множество из трех периодических заданий, профили выполнения которых приведены в табл. 10.5. Разработайте для этого множества диаграмму планирования, аналогичную диаграмме, приведенной на рис. 10.5.

Таблица 10.5. Профили выполнения процессов из задачи 10.1

Процесс	Время поступления	Время выполнения	Предельный срок завершения
А(1)	0	10	20
А(2)	20	10	40
•	•	•	•
•	•	•	•
•	•	•	•
В(1)	0	10	50
В(2)	50	10	100
•	•	•	•
•	•	• •	•
С(1)	0	15	50
С(2)	50	15	100
•	•	•	•
•	•	•	•
•	•	•	•

Таблица 10.6. Профили выполнения процессов из задачи 10.2

Процесс	Время поступления	Время выполнения	Предельный срок завершения
А	10	20	100
В	20	20	30
С	40	20	60
D	50	20	80
Е	60	20	70

10.2. Рассмотрим множество из пяти непериодических заданий, профили выполнения которых приведены в табл. 10.6. Разработайте для этого множества диаграмму планирования, аналогичную той, которая приведена на рис. 10.6.

10.3. Эта задача демонстрирует, что формула (10.2) является достаточным, но не необходимым условием — т.е. иногда успешное планирование возможно в ситуации, когда условие (10.2) не выполняется.

а. Рассмотрим множество следующих непериодических заданий:

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

• задание Р₂: C₂ == 30; Т₂ •= 145.

Могут ли эти задания быть успешно выполнены с использованием частотно-монотонного планирования?

б. Добавим к рассматриваемому множеству еще одно задание:

• задание Р₃: C₃ == 68; Т₃ •= 150.

Удовлетворяется ли при этом условие (10.2)?

в. Предположим, что первые задания рассмотренных трех типов поступают в систему в момент t = 0, а первые предельные сроки заданий D₁ = 100;

D₂ = 145; D₃ = 150. Будут ли выполнены все три ограничения при использовании частотно-монотонного планирования? Что можно сказать о предельных сроках последующих повторений заданий?

10.4. К многопроцессорной системе с 8 процессорами подключены 20 лентопротяжных устройств. В систему поступает большое количество заданий, причем для завершения каждого из них требуется максимум 4 лентопротяжных устройства. Предположим, что каждое задание начинает выполняться с требова­нием лишь трех устройств; четвертое ему потребуется только через довольно большой срок, причем будет использоваться очень недолго. Предположим также, что источник заданий бесконечен.

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

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