Similar presentations:
Архитектура операционных систем
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