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

СТРАТЕГИИ И КРИТЕРИИ ДИСПЕТЧЕРИЗАЦИИ ПРОЦЕССОВ

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

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

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

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

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

 

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

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

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

Решения по диспетчеризации могут быть приняты в случаях, если процесс:

1. Переключается из состояния выполнения в состояние ожидания.

2. Переключается из состояния выполнения в состояние готовности к выполнению.

3. Переключается из состояния ожидания в состояние готовности.

4. Завершается.

Диспетчеризация типов 1 и 4 обозначается термином диспетчеризация без прерывания процесса (non-preemptive).

Диспетчеризация типов 2 и 3 обозначается термином диспетчеризация с прерыванием процесса (preemptive).

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

Диспетчер процессора – компонента ОС, предоставляющая процессор тому процессу, который был выбран планировщиком. Диспетчер выполняет последовательность действий:

· Переключает контекст

· Переключает процессор в пользовательский режим

· Выполняет переход по соответствующему адресу в пользовательскую программу для ее рестарта.

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

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

 

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

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

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

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

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

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

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

Стратегия First-Come-First-Served (FCFS)

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

Рассмотрим следующий пример. Пусть процессы P₁, P₂ и P₃ введены в систему в указанном порядке со следующими периодами активности:

 

Процесс	Период активности
P1
P2
P3

 

Тогда при использовании стратегии FCFS для их диспетчеризации первым получит процессор первый процесс, несмотря на то, что он – наиболее долгий.

 

Рис. 11.3. Схема диспетчеризации по стратегии FCFS (пример 1).

 

Таким образом, время ожидания для P₁ = 0; P₂= 24; P₃ = 27.

Среднее время ожидания: (0 + 24 + 27)/3 = 17.

Если порядок процессов иной: P₂, P₃, P₁ (последний введенный в систему процесс – самый долгий), то результат их диспетчеризации будет совершенно иным.

 

Рис. 11.4. Схема диспетчеризации по стратегии FCFS (пример 2).

Время ожидания процессов в данном случае: P₁ = 6; P₂ = 0; P₃ = 3.

Среднее время ожидания: (6 + 0 + 3)/3 = 3

Данный результат много лучше, чем в предыдущем случае.

Эффект, продемонстрированный первым примером, носит название эффекта сопровождения (convoy effect) – увеличение среднего времени ожидания процессов в случаях, если короткий процесс обслуживается после долгого процесса.

Стратегия Shortest Job First (SJF)

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

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

Возможны две схемы применения данной стратегии:

1. Без прерывания процессов – пока процессу предоставляется процессор, он не может быть прерван, пока не истечет его квант времени.

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

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

Рассмотрим пример применения стратегии SJF без прерывания процессов. Пусть набор процессов, времен их появления в системе и времен их активности следующие:

 

Процесс	Время появления	Время активности
P1	0.0
P2	2.0
P3	4.0
P4	5.0

Рис. 11.5. Схема диспетчеризации процессов по стратегии SJF без прерывания.

 

В данном случае среднее время ожидания = (0 + 6 + 3 + 7)/4 = 4.

Теперь применим к тем же процессам стратегию SJF с прерыванием и проанализируем, как изменится среднее время ожидания.

 

Рис. 11.6. Схема диспетчеризации процессов по стратегии SJF с прерываниями.

 

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

· в момент 2 прерывается процесс 1 и начинает исполняться более короткий процесс 2;

· в момент 4 прерывается процесс 2 и начинает исполняться более короткий процесс 3.

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

В данном случае среднее время ожидания = (9 + 1 + 0 +2)/4 = 3, т.е. оно, как и следовало предполагать, оказалось меньше, чем без применения принципа прерывания процессов.

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

 

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

· t_n – фактическая длина n- го периода активности процесса;

· – предсказанная длина n- го периода активности процесса.

Будем искать значение для предсказания следующего периода активности процесса как следующую линейную комбинацию t_n и :

.

где – число между 0 и 1. Коэффициент характеризует, в какой степени при предсказании учитывается недавняя история вычислений.

 

Рис. 11.7. Пример предсказания следующего периода активности.

 

При , т.е. недавняя история не учитывается.

При т.е. учитывается только фактическая длина последнего периода активности.

Если обобщить приведенную формулу, получим:

.

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