Планирование и диспетчеризация процессора

1.

Планирование и диспетчеризация
процессора
(C) В.О. Сафонов, 2010

2.

Основные понятия
(C) В.О. Сафонов, 2010

3.

Последовательность активных фаз (bursts)
процессора и ввода-вывода
(C) В.О. Сафонов, 2010

4.

Гистограмма периодов активности
процессора
(C) В.О. Сафонов, 2010

5.

Планировщик процессора
(scheduler)
(C) В.О. Сафонов, 2010

6.

Собственно диспетчер
(C) В.О. Сафонов, 2010

7.

Критерии диспетчеризации
(C) В.О. Сафонов, 2010

8.

Критерии оптимизации
(C) В.О. Сафонов, 2010

9.

Стратегия диспетчеризации
First-Come-First-Served (FCFS)
P1
0
P2
24
P3
27
30
nВремя ожидания для P1 = 0; P2 = 24; P3 = 27
nСреднее время ожидания: (0 + 24 + 27)/3 = 17
(C) В.О. Сафонов, 2010

10.

Стратегия FCFS (продолжение)
P2
0
P3
3
P1
6
30
nВремя ожидания: P1 = 6; P2 = 0; P3 = 3
nСреднее время ожидания: (6 + 0 + 3)/3 = 3
nМного лучше, чем в предыдущем случае.
n Эффект сопровождения (convoy effect) - короткий
процесс после долгого процесса
(C) В.О. Сафонов, 2010

11.

Стратегия Shortest-Job-First (SJF)
(C) В.О. Сафонов, 2010

12.

Пример: SJF без опережения
P1
0
3
P3
7
P2
8
(C) В.О. Сафонов, 2010
P4
12
16

13.

Пример: SJF с опережением
P1
0
P2
2
P3
4
P2
5
P4
7
P1
11
(C) В.О. Сафонов, 2010
16

14.

Определение длины следующего
периода активности
1. t n actual length of n th CPU burst
2. n 1 predicted value for the next CPU burst
3. , 0 1
4. Define :
n 1 tn 1 n .
(C) В.О. Сафонов, 2010

15.

Предсказание длины следующего
периода активности
(C) В.О. Сафонов, 2010

16.

Примеры экспоненциального усреднения
(C) В.О. Сафонов, 2010

17.

Диспетчеризация по приоритетам
(C) В.О. Сафонов, 2010

18.

Стратегия Round Robin (RR) –
“круговая система”
(C) В.О. Сафонов, 2010

19.

Пример RR (квант времени = 20)
P1
0
P2
20
37
P3
P4
57
P1
77
P3
97 117
P4
P1
P3
P3
121 134 154 162
(C) В.О. Сафонов, 2010

20.

Квант времени ЦП и время
переключения контекста
(C) В.О. Сафонов, 2010

21.

Изменение времени оборота, в
зависимости от кванта времени
(C) В.О. Сафонов, 2010

22.

Многоуровневая очередь
(C) В.О. Сафонов, 2010

23.

Диспетчеризация по принципу
многоуровневой очереди
(C) В.О. Сафонов, 2010

24.

Многоуровневая аналитическая очередь
(multi-level feedback queue)
(C) В.О. Сафонов, 2010
24

25.

Пример многоуровневой
аналитической очереди
(C) В.О. Сафонов, 2010
25

26.

Многоуровневые аналитические очереди
(C) В.О. Сафонов, 2010
26

27.

Планирование загрузки
многопроцессорных систем
(C) В.О. Сафонов, 2010
27

28.

Планирование загрузки процессоров в
реальном времени
(C) В.О. Сафонов, 2010
28

29.

Латентность диспетчера
(dispatch latency)
(C) В.О. Сафонов, 2010
29

30.

Планирование в Solaris
(C) В.О. Сафонов, 2010
30

31.

Приоритеты в Windows 2000
(C) В.О. Сафонов, 2010
31