Планирование процессов. (Лекция 6)

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

2. Понятия: задание, процесс, планирование процесса

Процесс – это минимальный программный
объект, обладающий собственными системными
ресурсами.
Распределение процессов между
имеющимися ресурсами носит название
планирование процессов.

3. Состояния существования процесса

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

4.

Состояния существования процесса
Типовая диаграмма переходов для состояний процессов.

5. Диспетчеризация процесса

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

6. Способ выбора процесса для диспетчеризации

Наиболее важные дисциплины диспетчеризации.
•FCFS (first come – first served – первым пришёл, первым обслужился ) –
прежде процессор получает та задача, которая раньше перешла в состояние
готовности. Данная дисциплина проста в реализации, равноправна по
отношению как к “длинным ” так и к “коротким” процессам, среднее время
пребывания в очереди готовности весьма значительное.
•SJN (shortest job next – следующий с кратчайшим заданием) – прежде
процессор получает та задача, которая имеет минимальное заказное время
обслуживания. Данная дисциплина требует, чтобы для каждой задачи была
известна оценка потребности в машинном времени, значение которой
задаётся как параметр задачи. Такая дисциплина более сложна в реализации
по сравнению с FCFS, она дискриминационна по отношению к “длинным
процессам”, среднее время пребывания в очереди готовности меньше чем
для FCFS. SJN имеет существенный недостаток. Задачи, которые были
временно заблокированы (например, ожидали завершения ввода/вывода), в
результате попадут в конец очереди готовности, даже если для их
выполнения требуется небольшое процессорное время.

7.

Способ выбора процесса для
диспетчеризации
•SRT (shortest remaining time) – прежде процессор получает
задача, которая имеет меньше всего времени для своего
завершения. Это время определяется как разность между
заказанным временем обслуживания и тем процессорным временем,
которая задача уже получила. SRT свободна от недостатка,
характерного для SJN. SRT сложна в реализации и
дискриминационна по отношению к “длинным” процессам.
Рассмотренные дисциплины диспетчеризации
являются невытесняющими, в отличие от вытесняющих дисциплин,
которые будут описаны далее. Вытесняющей дисциплиной
диспетчеризации будем называть такую дисциплину, которая
предполагает возможное прерывание выполнения текущей задачи с
целью предоставления процессора другой готовой к выполнению
задаче.

8.

Способ выбора процесса для
диспетчеризации
Рассмотрим некоторые основные вытесняющие дисциплины
диспетчеризации:
•RR (round robin) – циклическая (карусельная) дисциплина.
Диспетчер выделяет готовой к выполнению задаче некоторый квант
процессорного времени (интервал мультиплексирования). Если
задача не успевает выполниться в течение этого кванта, диспетчер
переводит её обратно в конец очереди готовности и выделяет
следующий квант процессорного времени для другой готовой задачи.
Данная дисциплина является дискриминационной по отношению к
длинным процессам. Её удобно использовать в
многопользовательских вычислительных системах, где требуется
обслуживать большое число запросов, поступающих с различных
рабочих станций системы.

9.

Способ выбора процесса для
диспетчеризации
•Дисциплины на основе абсолютных приоритетов задач. Каждая
задача имеет приоритет, выраженный конкретным значением, который не
меняется на всём интервале существования задачи. Прежде процессор
будет получать та готовая задача, которая в данный момент имеет
максимальный приоритет по отношению к другим готовым задачам.
Данная дисциплина характерна для систем реального времени, она
дискриминационна по отношению к длинным процессам и не
даёт гарантий обслуживания для таких процессов.
•Дисциплины на основе динамических приоритетов задач. Для каждой
задачи задаётся начальное значение приоритета, которое затем
изменяется во времени. Таким образом, приоритет задачи есть функция
времени. Конкретный вид таких функций может быть разный, но общая их
направленность состоит в том, что, чем дольше задача находится в
очереди готовности, тем выше становится е¨ приоритет. Это позволяет
гарантировать обслуживание как коротких так и длинных процессов.

10.

Способ выбора процесса для
диспетчеризации
•Дисциплины с несколькими очередями. Диспетчер
поддерживает несколько очередей готовых к выполнению задач.
Каждая очередь обслуживается по своей дисциплине. Такой
диспетчер сложен в реализации, так как в его составе должен
быть дополнительный механизм переключения с одной очереди
готовности на другую. Более простой способ реализации
диспетчера (статический) предполагает, что задача попав в
некоторую очередь готовности, там и остаётся до своего полного
выполнения. Более сложным способом реализации
(динамическим) является способ, при котором задача может
переходить из одной очереди готовности в другую на интервале
своего существования.

11. Блок состояния процесса

Время жизни процесса можно теоретически разбить на несколько
состояний, описывающих процесс. Полный набор состояний процесса
содержится в следующем перечне:
1.Процесс выполняется в режиме задачи.
2.Процесс выполняется в режиме ядра.
3.Процесс не выполняется, но готов к запуску под управлением
ядра.
4.Процесс приостановлен и находится в оперативной памяти.
5.Процесс готов к запуску, но программа подкачки (нулевой
процесс) должна еще загрузить процесс в оперативную память,
прежде чем он будет запущен под управлением ядра.
6.Процесс приостановлен и программа подкачки выгрузила его во
внешнюю память, чтобы в оперативной памяти освободить место
для других процессов.

12.

Блок состояния процесса
7.Процесс возвращен из привилегированного режима (режима
ядра) в непривилегированный (режим задачи), ядро резервирует его и
переключает контекст на другой процесс. Об отличии этого состояния
от состояния 3 (готовность к запуску) пойдет речь ниже.
8.Процесс вновь создан и находится в переходном состоянии;
процесс существует, но не готов к выполнению, хотя и не
приостановлен. Это состояние является начальным состоянием всех
процессов, кроме нулевого.
9.Процесс вызывает системную функцию exit и прекращает
существование. Однако, после него осталась запись, содержащая код
выхода, и некоторая хронометрическая статистика, собираемая
родительским процессом. Это состояние является последним
состоянием процесса.

13. Алгоритмы диспетчеризации

Алгоритм разделения времени
Простейший алгоритм диспетчеризации процессов (или
потоков) состоит в поддержании единой очереди готовых
потоков (возможно с различными приоритетами).
Наличие единой очереди, используемой всеми
центральными процессорами, обеспечивает процессорам
режим разделения времени подобно тому, как это
выполняется на однопроцессорной системе.
Кроме того, такая организация позволяет
автоматически балансировать нагрузку, то есть она
исключает ситуацию, при которой один центральный
процессор простаивает, в то время как другие процессоры
перегружены.

14.

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

15.

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

16.

Алгоритмы диспетчеризации
•Совместное использование пространства (процессоров)
Другой подход к планированию мультипроцессоров может быть
использован, если потоки связаны друг с другом каким-либо способом.
Планирование нескольких потоков на нескольких центральных
процессорах называется совместным использованием пространства 
или разделением пространства.
Простейший алгоритм разделения пространства работает
следующим образ· Создается группа связанных потоков.
В момент их создания планировщик проверяет, есть ли свободные
центральные процессоры по количеству создаваемых потоков.
Если свободных процессоров достаточно, каждому потоку
выделяется собственный (то есть работающий в однозадачном
режиме) центральный процессор и все потоки запускаются.
Если процессоров недостаточно, ни один из потоков не
запускается, пока не освободится достаточное количество
центральных процессоров.

17.

Алгоритмы диспетчеризации
•Совместное использование пространства (процессоров)
Каждый поток выполняется на своем процессоре вплоть до завершения,
после чего все центральные процессоры возвращаются в пул свободных
процессоров.
Если поток оказывается заблокированным операцией ввода-вывода, он
продолжает удерживать центральный процессор, который простаивает до тех
пор, пока поток не сможет продолжать свою работу.
Периодически должны приниматься решения о планировании процессов. В
однопроцессорных системах для пакетного планирования применяется хорошо
известный алгоритм «кратчайшее задание первое». Подобный алгоритм для
мультипроцессора представляет собой выбор процесса, для которого требуется
наименьшее количество циклов процессора, то есть процесса, чье
произведение числа центральных процессоров на время работы минимально.
Однако на практике эта информация редко бывает доступна, поэтому
применение такого алгоритма затруднительно. Действительно, исследования
показали, что придумать что-либо лучшее простого обслуживания заданий в
порядке их поступления трудно.

18.

Алгоритмы диспетчеризации
•Совместное использование пространства (процессоров)
В этой простой модели разбиения процессоров на группы процесс просто
запрашивает определенное количество центральных процессоров и либо
сразу получает их, либо ждет, пока они не освободятся. Другой подход состоит
в том, чтобы активно управлять степенью распараллеливания процессов.
Один из способов управления степенью распараллеливания заключается в
наличии центрального сервера, ведущего учет работающих и желающих
работать процессов, а также минимального и максимального количества
требующихся для них центральных процессоров. Периодически каждый
центральный процессор опрашивает центральный сервер, чтобы узнать,
сколько центральных процессоров он может использовать. Затем он
увеличивает или уменьшает количество процессов или потоков, стараясь
добиться соответствия числу доступных процессоров. Такая схема
обеспечивает динамическое изменение размеров групп процессоров, чтобы
добиться лучшего соответствия текущей нагрузке.

19.

Алгоритмы диспетчеризации
•Бригадное планирование
Множество потоков процесса распределяются для одновременного
выполнения на множестве процессоров, по одному потоку на
процессор.
Очевидное преимущество разделения пространства заключается в
устранении многозадачности, что снижает накладные расходы по
переключению контекста. Однако ее недостаток состоит в потерях
времени при блокировке центрального процессора.
Поэтому проводились активные поиски алгоритма,
пытающегося планировать одновременно в пространстве и 
времени, особенно для процессов, создающих большое количество
потоков, которым, как правило, требуется возможность общения друг с
другом.

20.

Алгоритмы диспетчеризации
•Бригадное планирование
Бригадное планирование состоит из трех частей:
1.Группы связанных потоков планируются как одно целое, 
бригада.
2.Все члены бригады запускаются одновременно, на разных 
центральных процессорах с разделением времени.
3.Все члены бригады начинают и завершают свои временные 
интервалы (кванты времени) одновременно.
Бригадное планирование работает благодаря синхронности работы всех
центральных процессоров.
Это значит, что время разделяется на дискретные кванты. В начале
каждого нового кванта все центральные процессоры перепланируются
заново, и на каждом процессоре запускается новый поток. В начале
следующего кванта опять принимается решение о планировании. В середине
кванта планирование не выполняется. Если какой-либо поток блокируется,
его центральный процессор простаивает до конца кванта времени.

21. Понятие события. Блок состояния события

22. Механизм установления соответствия между процессом и событием