close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Планирование процессов
Типовой граф управления процессами:
0
Ожидание
начала
обработки
БВП
1
Обработка
ЦП
2
Ожидания
операции в/в
6 Завершение
5
4
БОП
Очередь
3 на выполнение
свопинг Диск
Планирование процессов
Характеристики, используемые для оценки эффективности:
• степень загрузки ЦП (CPU utilization);
• пропускная способность (throughput) – количество процессов,
завершающихся в единицу времени;
• полное время выполнения (turnaround time) – суммарное время
пребывания процесса в системе;
• время ожидания (waiting time) – суммарное время, которое
процесс провел в очереди готовых процессов
• время отклика (response time) – время, между поступлением
запроса от пользователя и началом его обработки процессами
Приоритет процесса – числовая характеристика,
соответствующая степени доступности процесса к тем или иным
ресурсам ВС по сравнению с другими процессами.
Priority = f({ресурсы ВС},User,…)
Планирование буфера ввода
процессов
l БВП
- предельное количество процессов, размещенных на БВП.
l БВП 0 , max
P1 {t lim 1 , { ресурсыВС }1 , User 1 , Рriо 1 ...}
P2 {t lim 2 , { ресурсыВС } 2 , User 2 , Рriо 2 ...}
.....
PN {t lim N , { ресурсыВС } N , User N , Рriо
N
...}
Смесь процессов -{ Pi } Если i < j, то процесс Pi сформирован
раньше P j
Будем считать, что все ресурсы, запрашиваемые каждым
Процессом доступны (в противном случае схема несколько
сложнее).
FIFO очередь
....
PN
PN
PN
Очередь с приоритетами процессов
P
N
....
P
2
P 1
для i > j : Рriо i Рriо
j
Многоуровневая очередь
1:
....
2:
....
...
М:
....
Множество процессов, составляющих { Pi } - разделено на М
непересекающихся подмножеств { P 1 } { P 2 } ...{ P M }
Многоуровневая очередь
• объем заказанных ресурсов ВС (например, предельное
время ЦП);
• критерий пользователя, сформировавшего процесс;
•...
{ Pi }
- очередь процессов организованная как:
- FIFO
- очередь процессов с приоритетами
Каждая из очередей может иметь свой приоритет
Перевод процесса из БВП в буфер
готовых к исполнению (БОП)
1. Поддержание заданного уровня многопроцессности.
При завершении выполнения очередного процесса,
запрашивается очередной из БВП. В случае представления
БВП как М очередей, используются приоритеты очередей.
2. Поддержание заданных квот на количество
обрабатываемых процессов, поступивших из тех или иных
входных очередей.
Планирование очереди (буфера) готовых
к исполнению процессов, планирование
использования ЦП
Квант времени работы ЦП.
Цикл счета: непрерывный промежуток времени,
Использованный процессом с момента выделения ЦП до его
освобождения.
Задачи планирования:
- определение стратегии квантования;
- стратегия обслуживания готовых к
исполнению процессов;
Невытесняющее планирование времени ЦП (планирование без
переключений, неприоритетное планирование) – процесс
выполняется либо до завершения, либо до возникновения
блокировки.
Планирование очереди (буфера) готовых
к исполнению процессов, планирование
использования ЦП
Вытесняющее планирование (планирование с переключениями,
приоритетное планирование) – процесс начинает выполнятся и
выполняется до исчерпания выделенного кванта времени, либо
до завершения, либо до возникновения блокировки.
Моменты принятия решений планировщиком:
- завершение выполнения процесса;
- исчерпание выделенного процессу кванта времени;
- блокировка процесса (обмен, синхронизация,...);
- прерывание от внешних устройств.
Планирование в системах пакетной
обработки
FCFS (first-come, first-served) – первым пришел, первым обслужен.
Процесс Цикл счета (время счета) Время ожидания
P1
P2
P3
30
6
6
Среднее время ожидания
0
30
36
22
Процесс Цикл счета (время счета) Время ожидания
P3
P2
P1
6
6
30
Среднее время ожидания
0
6
12
9
Планирование в системах пакетной
обработки
Эффект сопровождения
1. Один «вычислительный» процесс и «много» процессов,
занимающихся обменом.
2. Вычислительный процесс на «длительное» время занимает ЦП, у
остальных процессов завершаются обмены – ждут выделения
процесса.
3. Вычислительный процесс блокируется по обмену. Остальные
«быстро» используют свои «короткие» промежутки времени
использования ЦП и вновь блокируются по обмену.
.
.
Процессы, занимающиеся обменом в ожидании завершения
вычислительного процесса.
FCFS – алгоритм может быть вытесняющим или невытесняющим.
Планирование в системах пакетной
обработки
SPF (shortest-process-first) – кратчайший процесс – первым
Выбирается процесс с минимальным следующим циклом счета.
Цикл счета Время ожидания SPF
FCFS
6
P
8
P3
7
P
3
Среднее время
ожидания
P1
2
4
3
16
9
0
7
0
6
14
21
10.25
Оптимален по минимизации среднего времени ожидания.
Планирование в системах пакетной
обработки
Невозможность точного определения размеров циклов счета.
«Предсказание» следующего цикла счеты.
Использование экспоненциального среднего:
P1
T n 1 t n (1 )T n
, где
- реальная длина n-ого цикла.
T n - n-ое приближение длины n-ого цикла
[ 0 ,1] -весовой коэффициент последнего прогнозирования
tn
0 T n 1 t n - последняя информация игнорируется
1 T n 1 t n - прогнозирование игнорируется
T n 1 t n (1 ) t n 1 (1 ) t n k ... (1 )
k
1
1 1
n 1
T0
Значимость начального приближения со временем
уменьшается
Планирование в системах пакетной
обработки
Вытесняющий алгоритм SDF.
Текущий процесс исполняется, а новый процесс с более
коротким циклом счета чем остаток у текущего попадает в
очередь.
Прерывание текущего процесса.
Время поступления Цикл счета
P1
0
8
P2
1
4
P3
2
9
P4
3
5
P1
0
P2
1
P1
P4
5
10
P3
17
26
SPF без
Вытеснения – 7.5
Среднее время ожидания ((10-1)+(1-1)+(17-2)+(5-3))/4 = 6.5
Планирование в системах пакетной
обработки
SRT (Shortest remaining time) – наименьшее остающееся время
Выбор процесса с минимальным ожидаемым временем до
завершения процесса.
min
i
t lim i
t j0
n
i
j
, где
t lim i лимит времени ЦП для i-ого процесса;
tn j-й использованный i-ым процессом цикл счета.
i
Вариант с вытеснением и вариант без вытеснения.
Документ
Категория
Презентации
Просмотров
92
Размер файла
331 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа