При прохождении через ОС процесс мигрирует между различными очередями под управлением программы, которая называется планировщик (scheduler).
Одним из методов планирования процессов, ориентированных на эффективную загрузку ресурсов, является метод очередей ресурсов.
Позволяет равномерно загружать ресурсы (ЦП, ОП, ВУ)
Требует специальных механизмов для перемещения программ и защиты памяти.
4. МП уменьшает время обработки коротких заданий, снижает время ожидания ответа при организации работы в интерактивном режиме (разделение времени)
Планирование и диспетчеризация.
Распределение процессов между процессами имеющихся ресурсов носит название планирование процессов.
· Новые процессы находятся во входной очереди, часто называемой очередью заданий (job queue). Входная очередь располагается во внешней памяти, во входной очереди процессы ожидают освобождения ресурса - адресного пространства основной памяти.
· Готовые к выполнению процессы располагаются в основной памяти и связаны очередью готовых процессов или ready queue. Процессы в этой очереди ожидают освобождения ресурса «процессорное время».
· Процесс в состоянии ожидания завершения операции ввода - вывода находится в одной из очередей к оборудованию ввода - вывода, которая носит название devices queue.
Операционная система, обеспечивающая режим мультипрограммирования, обычно включает два планировщика:
· долгосрочный (long term scheduler)
· краткосрочный (short term scheduler/CPU scheduler).
Долгосрочный планировщик решает, какой из процессов, находящихся во входной очереди, должен быть переведен в очередь готовых процессов в случае освобождения ресурсов памяти.
Долгосрочный планировщик выбирает процесс из входной очереди с целью создания неоднородной мультипрограммной смеси. Это означает, что в очереди готовых процессов должны находиться в разной пропорции как процессы, ориентированные на ввод-вывод, так и процессы, ориентированные на преимущественную работу с CPU.
Краткосрочный планировщик решает, какой из процессов, находящихся в очереди готовых процессов, должен быть передан на выполнение в CPU. В некоторых операционных системах долгосрочный планировщик может отсутствовать. Например, в системах разделения времени (time sharing system), каждый новый процесс сразу же помещается в основную память.
Иногда используют термины:
Планировщик верхнего уровня – для программы выделения виртуального процессора.
Планировщик нижнего уровня – для программы выделения фактического процессора.
Основное различие между планированием и диспетчеризацией состоит в том, что планирование выполняется только один раз, а процессор может выделяться процессу многократно.
Планировщик и диспетчер управляют очередями процессов, следовательно, производительность различных алгоритмов управления можно качественно анализировать, использую теорию очередей.
Планирование процессов.
Основной функцией планирования является управление виртуальными процессорами, которое состоит в выделении и изъятии ресурсов, отличных от фактического процессора. Среди необходимых ресурсов могут быть и программные ресурсы.
Блокированные и приостановленные процессы могут быть откачаны во внешнюю память.
Некоторые ОС откачивают готовые активные процессы и тем самым переводят их в блокированное состояние.
Если процесс получил все ресурсы, за исключением фактического процессора, то тем самым ему выделен виртуальный процессор.
Планировщик процессов выполняет функции создания процессов, выделения ресурсов и завершения процессов (выделение виртуального процессора).
Диспетчеризация процессов при мультипрограммировании
Процесс, который может выполняться, как только процессор освободится, находится в состоянии - готовый активный. Такому процессу уже выделена ОП и другие ресурсы. Он ждет только одного ресурса – процессора.
Диспетчером процессов выполняется функция выделения процессора готовому активному процессу (выделение фактического процессора).
Диспетчер передает управление либо по истечении фиксированного интервала времени, либо при возникновении какого-либо внешнего по отношению к выполняющейся программе события (завершение в/в и т.п.). Диспетчер обрабатывает очередь готовых процессов, в которой любой готовой к выполнению программе соответствует элемент определенной структуры.
За разделение процессора приходится «расплачиваться» снижением скорости выполнения работ ВС.
Дисциплины диспетчеризации процессов.
Дисциплины с одной очередью для невытесняющей многозадачности.
1. Первым пришел – первым обслужен (FCFS, first come-first served)
Самой справедливой стратегией является стратегия предоставления всем пользователям одинаковых услуг, которую можно сформулировать следующим образом:
Обеспечить для всех процессов одно и то же среднее время ожидания.
Достигнуть этого можно, обслуживая процессы в порядке их появления и позволяя каждому процессу выполняться до конца (за исключением перехода в заблокированное состояние).
Стоимость реализации низка, так как очередь готовых надо поддерживать в порядке возрастания времен создания процессов, а перераспределения процессора не производится.
Основным недостатком механизма FCFSявляется то, что короткие процессы вынуждены ждать столько же, сколько и длинные («эффект конвоя»).
Два недостатка из теории очередей:
1. Среднее время ожидания может неограниченно расти по мере приближения системы к пределу своей загруженности.
2. С увеличением дисперсии времени выполнения процессов среднее время ожидания увеличивается.
1. Следующий-с кратчайшим заданием (SJN, shortest job-next)
Стратегия, избавленная от недостатков FCFS, состоит в минимизации общегосреднего времени ожидания.
Для достижения этого приоритет, учитываемый при диспетчеризации, основан на времени выполнения процесса, а не на времени его создания.
Перераспределения процессора не происходит.
При этом:
1. Снижается общее среднее время ожидания
2. Среднее время ожидания коротких процессов становится меньше, чем длинных.
3. Растет дисперсия времени ожидания (в результате трудно предсказать, когда процесс будет обслужен)
Циклические дисциплины для вытесняющей многозадачности.
1. Круговой циклический алгоритм (RR, round-robin).
Каждому процессу по очереди выделяется фиксированный квант времени q,в конце которого, если процесс к этому времени не закончился или не был заблокирован, он снимается с процессора, а на процессор ставится следующий готовый процесс. Процесс, снятый с процессора, ставится в конец очереди.
Приоритет процесса возрастает с увеличением времени ожидания с момента получения последнего кванта.
Если существует n готовых процессов, то каждый получит 1/n часть процессорного времени. Такая форма равного обслуживания неявно отдает предпочтение коротким процессам, поскольку они будут заканчиваться быстрее, чем длинные, но без чрезмерного ущемления «интересов» длинных.
Из-за расходов на переключение процессов общее время ожидания может быть больше, чем при FCFS.
Однако если дисперсия времени выполнения процессов велика, то при циклическом механизме общее среднее время ожидания может быть меньше, чем при FCFS.
Существенную роль играет размер кванта. Он может зависеть от размера очереди и параметров процессов.
2. Многоуровневый циклический алгоритм (FB, Feed Back (обратная связь)
n=1 - первая очередь готовых процессов. Из нее заявка поступает на CPU и/или полностью обслуживается или снова поступает в очередь, но с номером на 1 больше.
Заявка в i-ой очереди обслуживается, если пусты все остальные очереди. В очереди N заявки обслуживаются до завершения (в очереди N принцип FIFO +RR).
3. Смешанный алгоритм(RR+FB)
Каждый процесс получает в i-ой очереди несколько квантов процессорного времени и только потом переходит в очередь i+1.
Достоинства смешанного алгоритма:
· сокращаются накладные расходы на перевод процесса из очереди в очередь;
· возможно подобрать параметры алгоритма под т поток процессов (т.е., можно варьировать 
Выводы к бесприоритетным дисциплинам диспетчеризации:
· Линейные дисциплины характеризуются одинаковым средним временем ожидания.
· Циклические дисциплины обслуживают короткие процессы с неявным приоритетом.
· Бесприоритетые дисциплины не требуют предварительной информации о длительности заявок.
· Уменьшение длительности ожидания коротких процессов происходит за счет увеличения tожид. длинных заявок.
Классификация дисциплин диспетчеризации процессов