Планирование процессов (1)

1. Лекция 8 Планирование процессов

1

2.

1 Алгоритмы планирования
Планирование процессов включает в себя
решение следующих задач:
• определение момента времени для смены
выполняемого процесса;
• выбор процесса на выполнение из очереди
готовых процессов;
• переключение
контекстов
"старого"
и
"нового" процессов.
2

3.

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

4.

1.1 Квантование
Алгоритмы планирования
В соответствии с алгоритмами, основанными
на квантовании, смена активного процесса
происходит, если:
1. процесс завершился и покинул систему,
2. произошла ошибка,
3. процесс перешел в состояние ОЖИДАНИЕ,
4. исчерпан
квант
процессорного
времени,
отведенный данному процессу.
4

5.

Процесс,
переводится
который
в
исчерпал
состояние
свой
квант,
ГОТОВНОСТЬ
и
ожидает, когда ему будет предоставлен новый
квант процессорного времени, а на выполнение
в
соответствии
с
определенным
правилом
выбирается новый процесс из очереди готовых.
Таким образом, ни один процесс не занимает
процессор
надолго,
поэтому
квантование
широко используется в системах разделения
времени.
5

6.

6

7.

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

8.

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

9.

В таком случае преимущество получают
короткие
задачи,
которые
успевают
выполняться в течение первого кванта, а
длительные вычисления будут проводиться в
фоновом режиме. Можно представить себе
алгоритм планирования, в котором каждый
следующий квант, выделяемый определенному
потоку, больше предыдущего. Такой подход
позволяет уменьшить накладные расходы на
переключение задач в том случае, когда сразу
несколько
задач
выполняют
длительные
вычисления.
9

10.

Потоки получают для выполнения квант
времени, но некоторые из них используют его не
полностью,
например
из-за
необходимости
выполнить ввод или вывод данных. В результате
возникает
ситуация,
когда
потоки
с
интенсивными обращениями к вводу-выводу
используют
только
выделенного
им
небольшую
процессорного
часть
времени.
Алгоритм планирования может исправить эту
«несправедливость».
10

11.

В качестве компенсации за неиспользованные
полностью
кванты
потоки
получают
привилегии при последующем обслуживании.
Для этого планировщик создает две очереди
готовых потоков. Очередь 1 образована
потоками, которые пришли в состояние
готовности в результате исчерпания кванта
времени, а очередь 2 — потоками, у которых
завершилась операция ввода-вывода. При
выборе потока для выполнения прежде всего
просматривается вторая очередь, и только если
она пуста, квант выделяется потоку из первой
очереди.
11

12.

12

13.

Многозадачные
количество
ОС
теряют
процессорного
некоторое
времени
для
выполнения вспомогательных работ во время
переключения
контекстов
задач.
При
этом
запоминаются и восстанавливаются регистры,
флаги и указатели стека, а также проверяется
статус задач для передачи управления. Затраты
на эти вспомогательные действия не зависят от
величины кванта времени, поэтому чем больше
квант,
тем
меньше
суммарные
накладные
расходы, связанные с переключением потоков.
13

14.

1.2 Приоритеты
Алгоритмы планирования
Другая
группа
алгоритмов
использует
понятие приоритет процесса. Приоритет - это
число,
характеризующее
привилегированности
использовании
ресурсов
степень
процесса
при
вычислительной
машины, в частности, процессорного времени:
чем выше приоритет, тем выше привилегии.
14

15.

Приоритет может выражаться целыми или
дробными, положительным или отрицательным
значением. Чем выше привилегии процесса, тем
меньше времени он будет проводить в очередях.
Приоритет может назначаться директивно
администратором системы в зависимости от
важности работы или внесенной платы, либо
вычисляться самой ОС по определенным
правилам, он может оставаться фиксированным
на протяжении всей жизни процесса либо
изменяться во времени в соответствии с
некоторым законом. В последнем случае
приоритеты называются динамическими.
15

16.

В
большинстве
операционных
систем,
поддерживающих
потоки,
приоритет потока
непосредственно
связан
с
процесса,
в
рамках
приоритетом
которого
выполняется
данный поток. Приоритет процесса назначается
операционной
системой
при
его
создании.
Значение приоритета включается в описатель
процесса
и
используется
при
назначении
приоритета потокам этого процесса.
16

17.

При
назначении
приоритета
вновь
созданному процессу ОС учитывает, является
этот процесс системным или прикладным, каков
статус пользователя, запустившего процесс,
было ли явное указание пользователя на
присвоение процессу определенного уровня
приоритета. Поток может быть инициирован не
только по команде пользователя, но и в
результате выполнения системного вызова
другим потоком. В этом случае при назначении
приоритета новому потоку ОС должна
принимать во внимание значение параметров
системного вызова.
17

18.

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

19.

От
того,
какие
приоритеты
назначены
потокам, существенно зависит эффективность
работы
всей
вычислительной
системы.
В
современных ОС во избежание разбалансировки
системы,
которая
может
возникнуть
неправильном
назначении
возможности
пользователей
при
приоритетов,
влиять
на
приоритеты процессов и потоков стараются
ограничивать.
19

20.

При
этом
обычные
пользователи,
как
правило, не имеют права повышать приоритеты
своим потокам, это разрешено делать (да и то в
определенных
пределах)
только
администраторам. В большинстве же случаев
ОС
присваивает
приоритеты
потокам
по
умолчанию.
20

21.

В
качестве
примера
рассмотрим
схему
назначения приоритетов потокам, принятую в
операционной системе Windows NT. В системе
определено 32 уровня приоритетов и два класса
потоков — потоки реального времени и потоки с
переменными приоритетами. Диапазон от 1 до
15
включительно
отведен
для
потоков
с
переменными приоритетами, а от 16 до 31 — для
более критичных ко времени потоков реального
времени
(приоритет
системных целей).
0
зарезервирован
для
21

22.

22

23.

При создании процесса он в зависимости от
класса получает по умолчанию базовый
приоритет в верхней или нижней части
диапазона. Базовый приоритет процесса в
дальнейшем может быть повышен или понижен
операционной системой. Первоначально Поток
получает значение базового приоритета из
диапазона базового приоритета процесса, в
котором он был создан. Пусть, например,
значение базового приоритета некоторого
процесса равно К. Тогда все потоки данного
процесса получат базовые приоритеты из
диапазона [К-2, К+2]. Отсюда видно, что,
изменяя базовый приоритет процесса, ОС может
влиять на базовые приоритеты его потоков.
23

24.

Во
многих
алгоритмы
операционных
планирования
использованием
как
системах
построены
квантования,
с
так
и
приоритетов. Например, в основе планирования
лежит квантование, но величина кванта и/или
порядок выбора процесса из очереди готовых
определяется приоритетами процессов.
24

25.

2 Алгоритмы с вытеснением и без
Существует два основных типа процедур
планирования
процессов
-
вытесняющие
(preemptive) и невытесняющие (non-preemptive).
Non-preemptive multitasking - невытесняющая
многозадачность - это способ планирования
процессов, при котором активный процесс
выполняется до тех пор, пока он сам, по
собственной инициативе, не отдаст управление
планировщику операционной системы для того,
чтобы тот выбрал из очереди другой, готовый к
выполнению процесс.
25

26.

Preemptive
multitasking
-
вытесняющая
многозадачность - это такой способ, при котором
решение
о
переключении
процессора
с
выполнения одного процесса на выполнение
другого процесса принимается планировщиком
операционной системы, а не самой активной
задачей.
26

27.

Основным различием между preemptive и nonвариантами
preemptive
является
степень
планирования
многозадачности
централизации
задач.
При
механизма
вытесняющей
многозадачности механизм планирования задач
целиком сосредоточен в операционной системе, и
программист
пишет
свое
приложение,
не
заботясь о том, что оно будет выполняться
параллельно с другими задачами.
27

28.

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

29.

Прикладная программа, получив управление
от операционной системы, сама определяет
момент завершения своей очередной итерации и
передает управление ОС с помощью какого-либо
системного вызова, а ОС формирует очереди
задач и выбирает в соответствии с некоторым
алгоритмом (например, с учетом приоритетов)
следующую
задачу
на
выполнение.
механизм
создает
проблемы
как
Такой
для
пользователей, так и для разработчиков.
29

30.

Для
пользователей
это
означает,
что
управление системой теряется на произвольный
период
времени,
приложением
(а
который
не
определяется
пользователем).
Если
приложение тратит слишком много времени на
выполнение какой-либо работы, например, на
форматирование диска, пользователь не может
переключиться с этой задачи на другую задачу,
например, на текстовый редактор, в то время
как
форматирование
фоновом режиме.
продолжалось
бы
30
в

31.

Эта
ситуация
нежелательна,
так
как
пользователи обычно не хотят долго ждать,
когда машина завершит свою задачу.
Поэтому разработчики приложений для nonpreemptive операционной среды, возлагая на
себя функции планировщика, должны создавать
приложения так, чтобы они выполняли свои
задачи
небольшими
частями.
Например,
программа
форматирования
может
отформатировать
одну
дорожку
вернуть управление системе.
дискеты
31
и

32.

После выполнения других задач система
возвратит
управление
программе
форматирования, чтобы та отформатировала
следующую
дорожку.
Подобный
метод
разделения времени между задачами работает,
но он существенно затрудняет разработку
программ
и
предъявляет
повышенные
требования к квалификации программиста.
Программист
должен
обеспечить
"дружественное" отношение своей программы к
другим выполняемым одновременно с ней
программам, достаточно часто отдавая им
управление.
32

33.

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

34.

Однако
распределение
функций
планировщика между системой и приложениями
не всегда является недостатком, а при
определенных
условиях
может
быть
и
преимуществом, потому что дает возможность
разработчику
приложений
самому
проектировать
алгоритм
планирования,
наиболее
подходящий
для
данного
фиксированного набора задач. Так как
разработчик сам определяет в программе
момент времени отдачи управления, то при этом
исключаются нерациональные прерывания
программ в "неудобные" для них моменты
времени.
34

35.

Кроме того, легко разрешаются проблемы
совместного использования данных: задача во
время
каждой
итерации
использует
их
монопольно и уверена, что на протяжении этого
периода никто другой не изменит эти данные.
Существенным преимуществом non-preemptive
систем
является
более
высокая
переключения с задачи на задачу.
скорость
35

36.

Примером
эффективного
невытесняющей
использования
многозадачности
является
файл-сервер NetWare, в котором, в значительной
степени благодаря этому, достигнута высокая
скорость
Менее
выполнения
удачным
невытесняющей
файловых
оказалось
операций.
использование
многозадачности
операционной среде Windows 3.х.
в
36