Лекция: Стратегии и критерии диспетчеризации процессов В лекции рассмотрены: планирование и диспетчеризация процессора

Лекция: Стратегии и критерии диспетчеризации процессов

 

В лекции рассмотрены: планирование и диспетчеризация процессора; критерии диспетчеризации; стратегии диспетчеризации (FCFS, SJF, RR); многоуровневые очереди, диспетчеризация мультипроцессорных систем и систем реального времени.

 

Содержание

• Введение
• Основные понятия диспетчеризации процессов
• Планировщик процессора
• Собственно диспетчер процессора
• Критерии диспетчеризации
• Стратегия First-Come-First-Served (FCFS)
• Стратегия Shortest Job First (SJF)
• Предсказание длины следующего периода активности
• Диспетчеризация по приоритетам
• Стратегия Round Robin (RR)
• Многоуровневая очередь
• Многоуровневые аналитические очереди
• Планирование загрузки многопроцессорных систем
• Планирование загрузки процессоров в системах реального времени
• Планирование в Solaris
• Планирование в Windows 2000
• Ключевые термины
• Краткие итоги
• Набор для практики
• Вопросы
• Упражнения
• Темы для курсовых работ, рефератов, эссе

Введение

Планирование и диспетчеризация процессора – одна из важнейших функций операционной системы. В лекции рассмотрены следующие вопросы:

• Основные понятия диспетчеризации процессов
• Критерии диспетчеризации
• Алгоритмы диспетчеризации
• Диспетчеризация нескольких процессоров
• Диспетчеризация в реальном времени
• Многоуровневые очереди.

Основные понятия диспетчеризации процессов

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

Исполнение любого процесса можно рассматривать как цикл CPU / I-O– чередование периодов использования процессора и ожидания ввода-вывода.

Распределение периодов активности процессора (bursts) и ввода-вывода изображено на рис. 11.1.

Рис. 11.1. Последовательность активных фаз процессора и фаз ввода-вывода.

На рис. 11.2 изображена примерная гистограмма периодов активности процессора, основанная на анализе реального поведения процессов в операционных системах.

Рис. 11.2. Гистограмма периодов активности процессора.

Из схемы видно, что чем короче период активности, тем выше частота таких периодов, и наоборот, т.е. частота периодов активности обратно пропорциональна их длительности.

Планировщик процессора

Решения по диспетчеризации могут быть приняты в случаях, если процесс: Переключается из состояния выполнения в состояние ожидания. … Диспетчеризация типов 1 и 4 обозначается термином диспетчеризация без… Диспетчеризация типов 2 и 3 обозначается терминомдиспетчеризация с прерыванием процесса (preemptive).

Собственно диспетчер процессора

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

Критерии диспетчеризации

Использование процессора (CPU utilization)– поддержание его в режиме занятости максимально возможный период времени. Критерий оптимизации:… Пропускная способность системы (throughput)– (среднее) число процессов,… Время обработки процесса (turnaround time)– время, необходимое для исполнения какого-либо процесса. Критерий…

Предсказание длины следующего периода активности

Будем искать значение τn+1 для предсказания следующего периода активности процесса как следующую линейную комбинацию tn и τn: τn+1 = tn + (1 – ) τn . где – число между 0 и 1. Коэффициент характеризует, в какой степени при предсказании учитывается недавняя история…

Диспетчеризация по приоритетам

Данная стратегия, как и предыдущая, имеет варианты с прерыванием и без прерывания. Более того, стратегию SJF можно рассматривать как диспетчеризацию по… При диспетчеризации по приоритетам возникает проблема "голодания" (starvation)- ситуации, когда процессы с…

Рис. 11.10.

Многоуровневая очередь

Каждая очередь имеет свой собственный алгоритм диспетчеризации: основная –RR, фоновая – FCFS. При данной смешанной стратегии необходима также диспетчеризация между… На рис. 11.11 приведен реалистичный пример структуры многоуровневой очереди для диспетчеризации процессов. Наивысший…

Рис. 11.11.

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

На рис. 11.12 приведен пример организации многоуровневой аналитической очереди с квантами времени 8 (очередь Q0) и 16 (очередь Q1) и пакетными… Рис. 11.12. Многоуровневая аналитическая очередь.

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

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

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

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

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

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

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

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

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

Время обработки процесса (turnaround time)– время, необходимое для исполнения какого-либо процесса. Время ожидания (waiting time) –время, которое процесс ждет в очереди… Время ответа (response time)– время, требуемое от момента запроса (команды) пользователя до первого ответа системы. …

Краткие итоги

Работа любого процесса в системе представляется как последовательность чередований фаз активности процессора и активности ввода-вывода. Частота… Планировщик – компонента ОС, планирующая выделение квантов времени процессам… Диспетчер – компонента ОС, выполняющая само переключение процессора с одного процесса на другой. Время, которое на это…

Набор для практики

Вопросы

Упражнения

Темы для курсовых работ, рефератов, эссе