Многоуровневые аналитические очереди

 

Для более гибкой диспетчеризации процессов в операционных системах организуются многоуровневые аналитические очереди (multi-level feedback queues),в которых обслуживаются процессы нескольких классов, причем каждый из классов имеет различные кванты времени. Самый быстрый (приоритетный) класс процессов получает минимальный квант. Если процесс не завершается за этот квант времени, ОС перемещает его в очередь процессов другого класса с большей величиной кванта, и т.д. Если процесс не завершается и за самый большой из выделяемых системой квантов времени, ОС перемещает его в класс пакетных процессов, обслуживаемых по стратегии FCFS.

На рис. 11.12 приведен пример организации многоуровневой аналитической очереди с квантами времени 8 (очередь Q0) и 16 (очередь Q1) и пакетными процессами по стратегии FCFS (очередь Q2). Первоначально процесс помещается в очередь Q0; если он не завершается за 8 единиц времени, то он перемещается в очередь Q1; если не завершается и за 16 единиц времени – то перемещается в очередь Q2.

 

Рис. 11.12. Многоуровневая аналитическая очередь.

Планирование загрузки многопроцессорных систем

 

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

Планирование загрузки процессоров в системах реального времени

 

Как уже отмечалось, системы реального времени делятся на два класса – hard real-time и soft real-time. В первом случае решение основной (критической) задачи требуется за фиксированный интервал времени (response time), что и учитывается при планировании. Во втором случае требование более слабое: критические процессы, решающие основную задачу системы, должны иметь более высокий приоритет, чем остальные процессы. На рис. 11.13 иллюстрируются особенности диспетчеризации и латентность диспетчера для систем реального времени. Интервал ответа, который не может быть превышен, складывается из времени обработки прерывания, периода латентности диспетчера при переключении контекста (времени разрешения конфликтов и собственно времени диспетчеризации) и времени исполнения критического процесса реального времени.

Рис. 11.13. Латентность диспетчера в системах реального времени.

Планирование в Solaris

 

На рис. 11.14 иллюстрируются принципы планирования в ОС Solaris. Система обслуживает несколько классов процессов, в порядке убывания приоритетов: реального времени, системные, интерактивные и с разделением времени. Более высокоприоритетные процессы планируются и диспетчеризуются первыми. Для каждого класса процессов имеется свой планировщик.

Рис. 11.14. Планирование в Solaris.

Планирование в Windows 2000

 

В таблице 1 изображены классы процессов и принципы распределения их приоритетов в Windows 2000. Классы процессов представлены столбцами таблицы, их приоритеты – строками. Рекомендуем обратить внимание, что даже простаивающий процесс реального времени имеет гораздо больший приоритет, чем простаивающие процессы других классов.

 

Таблица 1.
	реального времени	высокий	выше нормального	нормальный	ниже нормального	приоритет простаивающего процесса
критический
наивысший
выше нормального
нормальный
ниже нормального
низший
простаивающий

Ключевые термины

Возраст (aging) процесса – повышение операционной системой приоритета длительное время находящегося в системе процесса.

Время обработки процесса (turnaround time) – время, необходимое для исполнения какого-либо процесса.

Время ожидания (waiting time) – время, которое процесс ждет в очереди процессов, готовых к выполнению.

Время ответа (response time) – время, требуемое от момента запроса (команды) пользователя до первого ответа системы.

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

Диаграмма Ганта (Gantt chart) – схема в виде "временной линейки", изображающая имена процессов и временные диапазоны их выполнения, выраженные в некоторых единицах времени.

Диспетчеризация (процессора) – распределение времени процессора между процессами в системе путем поочередного выделения планировщиком операционной системы процессам квантов процессорного времени.

Диспетчеризация без прерывания процессов (non-preemptive) – стратегии диспетчеризации, не использующие прерывания работы процессов при поступлении в систему более коротких или более приоритетных.

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

Использование процессора (CPU utilization) – поддержание его в режиме занятости максимально возможный период времени.

Многоуровневая очередь – совокупность системных очередей, содержащих в отдельных очередях процессы различных классов и приоритетов (например, пакетные и интерактивные).

Планировщик (scheduler) – компонента ОС, которая выбирает один из нескольких процессов, загруженных в память и готовых к выполнению, и выделяет процессор для одного из них.

Пропускная способность системы (throughput) – (среднее) число процессов, завершающих свое выполнение за единицу времени.

Скрытая активность (латентность) диспетчера (dispatch latency) – время, требуемое для диспетчера, чтобы остановить один процесс и стартовать другой.

Стратегия First-Come-First-Served (обслуживание в порядке поступления) – стратегия диспетчеризации, при которой ресурсы процессора предоставляются процессам в порядке их поступления в систему, независимо от потребляемых ими ресурсов.

Стратегия Round Robin (RR, круговая система) – стратегия диспетчеризации, при которой всем процессам по очереди предоставляются одинаковые кванты времени.

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

Стратегия Shortest-Remaining-Time-First (SRTF, обслуживание процесса с минимальным оставшимся временем выполнения) -стратегия диспетчеризации процессора, при которой процессор предоставляется в первую очередь процессу с минимальным оставшимся временем выполнения.

Цикл CPU / I-O – чередование периодов использования процессора и ожидания ввода-вывода.

Вопросы

1. Что такое диспетчеризация процессора?

2. В чем основная цель диспетчеризации процессора?

3. Что такое цикл CPU – I/O?

4. Как зависит частота периодов активности процессора от их длительности?

5. Что такое планировщик?

6. Какие разновидности стратегий, с точки зрения прерывания или избежания прерывания процессов, использует планировщик?

7. Что такое стратегия без прерывания процессов?

8. Что такое стратегия с прерыванием процессов?

9. Что такое диспетчер?

10. Что такое латентность диспетчера и каким образом следует оптимизировать данный показатель?

11. Каковы основные критерии диспетчеризации?

12. Что такое использование (утилизация) процессора и как следует оптимизировать данный показатель?

13. Что такое пропускная способность системы и как следует оптимизировать данный показатель?

14. Что такое время обработки и как следует оптимизировать данный показатель?

15. Что такое время ожидания и как следует оптимизировать данный показатель?

16. Что такое время ответа и как следует оптимизировать данный показатель?

17. Что такое диаграмма Ганта?

18. В чем суть стратегии FCFS и каковы ее недостатки?

19. В чем суть стратегии SJF (и SRTF) и оптимальность по какому критерию она обеспечивает?

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

21. В чем суть диспетчеризации по приоритетам?

22. Что такое проблема голодания процессов и каково ее решение в ОС?

23. В чем суть стратегии RR, оптимальность по какому критерию она обеспечивает и по какому критерию она хуже, чем SJF?

24. Как зависит число контекстных переключений от величины кванта времени?

25. Как зависит время оборота от величины кванта времени?

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

27. Каковы особенности планирования загрузки многопроцессорных систем?

28. Каковы особенности планирования в системах реального времени?

Упражнения

1. Реализуйте модель поведения процесса с чередованием периодов активности ЦП и ввода-вывода (времена периодов изменяются по какому-либо случайному закону) и визуализацией их в виде графических схем и гистограмм зависимости частоты периодов активности от их длительности.

2. Реализуйте модель представления процесса в системе и алгоритм диспетчера, выполняющего переключение контекста между процессами.

3. Реализуйте стратегию диспетчеризации FCFS с визуализацией ее результатов в виде диаграмм Ганта.

4. Реализуйте стратегию диспетчеризации SJF с визуализацией ее результатов в виде диаграмм Ганта.

5. Реализуйте стратегию диспетчеризации RR с визуализацией ее результатов в виде диаграмм Ганта.

6. Реализуйте стратегию диспетчеризации по приоритетам с визуализацией ее результатов в виде диаграмм Ганта.

7. Реализуйте вычисление предсказываемой длины следующего периода активности по методу экспоненциального усреднения.

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