Архитектура операционных систем

1.

Архитектура
операционных систем
Лекция 1.4

2. Алгоритмы планирования

АЛГОРИТМЫ
SJF (Shortest Job First)
ПЛАНИРОВАНИЯ
приближение
– ВЕЛИЧИНА N-ГО CPU BURST
T(N+1) – ПРЕДСКАЗАНИЕ ДЛЯ N+1-ГО CPU BURST
Α – ПАРАМЕТР ОТ 0 ДО 1
Τ(N)
T(N+1)= Α Τ(N) + (1 – Α)T(N),
T(0) – ПРОИЗВОЛЬНО
ЕСЛИ Α = 0, ТО T(N+1) = T(N) =…= T(0),
НЕТ УЧЕТА ПОСЛЕДНЕГО ПОВЕДЕНИЯ
ЕСЛИ Α = 1, ТО T(N+1) = Τ(N),
НЕТ УЧЕТА ПРЕДЫСТОРИИ
2

3. Алгоритмы планирования

АЛГОРИТМЫ ПЛАНИРОВАНИЯ
Гарантированное планирование
– пользователь обделен
– пользователю благоволят
3

4. Алгоритмы планирования

АЛГОРИТМЫ ПЛАНИРОВАНИЯ
Приоритетное планирование
Каждому процессу процессор выделяется в соответствии с
приписанным к нему числовым значением - приоритетом
Параметры для назначения приоритета бывают:
-внешние
-внутренние
Политика изменения приоритета:
-статический приоритет
-динамический приоритет
4

5. Алгоритмы планирования

АЛГОРИТМЫ ПЛАНИРОВАНИЯ
Приоритетное планирование
невытесняющий
Процессы
P0
P1
P2
P3
Продолжительность CPU burst
6
2
5
5
Момент появления в очереди
0
2
6
0
Приоритет
4
3
2
1
время
1
2
3
4
5
6
7
8
9
10
11
12
P0
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г И И И И И И
Г
Г
Г
И И
P1
Г
P2
P3
13
14
15
16
17
И И И И И
И И И И И
готовность
исполнение
P2013
P0
P1
P2
P3
5
18

6. Алгоритмы планирования

АЛГОРИТМЫ ПЛАНИРОВАНИЯ
Приоритетное планирование
вытесняющий
Процессы
P0
P1
P2
P3
Продолжительность CPU burst
6
2
5
5
Момент появления в очереди
0
2
6
0
Приоритет
4
3
2
1
время
1
2
3
4
5
6
7
8
9
10
11
12
P0
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г И И И И И И
Г
Г
Г
И Г
Г
Г
Г
Г
И
P1
14
15
16
17
И И И И И
P2
P3
13
И И И И И
готовность
исполнение
P2013
P0
P1
P2
P3
6
18

7. Алгоритмы планирования

АЛГОРИТМЫ ПЛАНИРОВАНИЯ
Многоуровневые очереди
(Multilevel Queue)
Системные процессы приоритет 0
RR
Процессы ректората приоритет 1
RR
Процессы преподавателей приоритет 2 RR
Фоновые процессы приоритет 3
FCFS
Процессы студентов приоритет 4
RR
7

8. Алгоритмы планирования

АЛГОРИТМЫ ПЛАНИРОВАНИЯ
Многоуровневые очереди с обратной связью
(Multilevel Feedback Queue)
Клавиатурный
ввод
Очередь 0 – Приоритет 0
RR с квантом времени 8
Очередь 1 – Приоритет 1
RR с квантом времени 16
Очередь 2 – Приоритет 2
RR с квантом времени 32
Дисковый I/O
Очередь 3 – Приоритет 3
FCFS
8

9. Алгоритмы планирования

АЛГОРИТМЫ ПЛАНИРОВАНИЯ
Многоуровневые очереди с обратной связью
(Multilevel Feedback Queue)
Для полного описания необходимо задать
- количество очередей в состоянии готовность
- алгоритм планирования между очередями
- алгоритмы планирования внутри очередей
- куда помещается родившийся процесс
- правила перевода процессов из одной очереди в
другую
9

10. Основные причины для объединения усилий процессов

ОСНОВНЫЕ ПРИЧИНЫ ДЛЯ
ОБЪЕДИНЕНИЯ
УСИЛИЙ ПРОЦЕССОВ
Кооперативные или взаимодействующие процессы
- это процессы, которые влияют на поведение друг
друга путем обмена информацией
10

11. Категории средств обмена информацией

КАТЕГОРИИ СРЕДСТВ ОБМЕНА
ИНФОРМАЦИЕЙ
11

12. Основные аспекты логической организации передачи информации

ОСНОВНЫЕ АСПЕКТЫ ЛОГИЧЕСКОЙ
ОРГАНИЗАЦИИ ПЕРЕДАЧИ ИНФОРМАЦИИ
Как устанавливается связь
12

13. Основные аспекты логической организации передачи информации

ОСНОВНЫЕ АСПЕКТЫ ЛОГИЧЕСКОЙ
ОРГАНИЗАЦИИ ПЕРЕДАЧИ ИНФОРМАЦИИ
Информационная валентность процессов
и средств связи
13

14. Основные аспекты логической организации передачи информации

ОСНОВНЫЕ АСПЕКТЫ ЛОГИЧЕСКОЙ
ОРГАНИЗАЦИИ ПЕРЕДАЧИ ИНФОРМАЦИИ
Особенности канальных средств связи
Буферизация
14

15. Основные аспекты логической организации передачи информации

ОСНОВНЫЕ АСПЕКТЫ ЛОГИЧЕСКОЙ
ОРГАНИЗАЦИИ ПЕРЕДАЧИ ИНФОРМАЦИИ
Особенности канальных средств связи
Модели передачи данных
15

16. Основные аспекты логической организации передачи информации

ОСНОВНЫЕ АСПЕКТЫ ЛОГИЧЕСКОЙ
ОРГАНИЗАЦИИ ПЕРЕДАЧИ ИНФОРМАЦИИ
Особенности канальных средств связи
Потоковая модель - pipe
Потоковая модель - FIFO
P0
5 байт
15
начало
конец
P2
255 байт
10 байт
P1
16

17. Основные аспекты логической организации передачи информации

ОСНОВНЫЕ АСПЕКТЫ ЛОГИЧЕСКОЙ
ОРГАНИЗАЦИИ ПЕРЕДАЧИ ИНФОРМАЦИИ
Особенности канальных средств связи
Модель сообщений
P0
P2
m1
m3
m3 m2
m1
m3
m2
m3
m3
m2
m1
m2
P1
17

18. Основные аспекты логической организации передачи информации

ОСНОВНЫЕ АСПЕКТЫ ЛОГИЧЕСКОЙ
ОРГАНИЗАЦИИ ПЕРЕДАЧИ ИНФОРМАЦИИ
Надежность средств связи
Средство связи считается надежным, если:
18

19. Основные аспекты логической организации передачи информации

ОСНОВНЫЕ АСПЕКТЫ ЛОГИЧЕСКОЙ
ОРГАНИЗАЦИИ ПЕРЕДАЧИ ИНФОРМАЦИИ
Как завершается связь
19