Материал: Сущность и обзор методов и стратегий диспетчеризации процессов

Стратегия Shortest-Remaining-Time-First (SRTF, обслуживание процесса с минимальным оставшимся временем выполнения) - стратегия диспетчеризации процессора, при которой процессор предоставляется в первую очередь процессу с минимальным оставшимся временем выполнения.

Многозадачность может быть либо кооперативной (cooperative multitasking), либо вытесняющей (preemptive multitasking).

В кооперативных системах за передачу управления другим задачам отвечает исполняющаяся в данный момент программа. Это управление может передаваться явным или косвенным образом. Для явной (explicitly) передачи управления используются специально предназначенные для этой цели программные вызовы операционной системы. Косвенная (implicitly) передача управления происходит при вызове определенных функций операционной системы, которые подразумевают переход к выполнению других задач на время осуществления операций, соответствующих этим функциям (например, при выполнении обмена с дисками). Примеры ОС: Windows 3.x (однако при работе в расширенном режиме для всех DOS-приложений, запущенных в этой системе, применяется вытесняющая многозадачность) и Novell NetWare.

В системах с вытесняющей многозадачностью ОС может самостоятельно передать управление процессором от одной активной задачи к другой, готовой к выполнению задаче. Следовательно, работающие в режиме вытесняющей мультизадачности приложения могут не беспокоиться о том, что они могут “захватить” все время процессора, так как ОС сама распределяет время процессора между всеми существующими в системе задачами. Примеры ОС: OS/2, Unix, Windows 95 и Windows NT.

Планирование выделения времени центрального процессора в таких системах выполняется в соответствии с приоритетами.

Планировщики, выполняющие диспетчеризацию процессов и предсказание длины следующего периода активности

Планировщики, выполняющие диспетчеризацию процессов

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

Долговременный планировщик (планировщик заданий) определяет, какие процессы должны быть перемещены в очередь готовых процессов.

Кратковременный планировщик (планировщик процессора) - определяет, какие процессы должны быть выполнены следующими и каким процессам должен быть предоставлен процессор.

Для реализации режима разделения времени в систему может быть добавлен также планировщик откачки и подкачки процессов, определяющий, какие пользовательские процессы должны быть подкачаны в память или откачаны на диск. Схема работы системы, включающей такой планировщик, изображена на рис. 8.6.

Особенности планировщиков и процессов.Каждый планировщик имеет свои особенности поведения, как и каждый процесс.

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

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

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

Сами процессы также могут вести себя по-разному, с точки зрения их диспетчеризации. Процессы могут быть:

ЃE Ориентированными на ввод-вывод (I/O-bound) - процессы, которые тратят больше времени на ввод-вывод, чем на вычисления. Такие процессы обычно расходуют много коротких квантов процессорного времени.

ЃE Ориентированные на использование процессора (CPU-bound) - процессы, которые тратят основное время на вычисления. Такие процессы расходуют небольшое число долговременных квантов процессорного времени.

Переключение контекста

Когда процессор переключается на другой процесс, система должна сохранить состояние старого процесса и загрузить сохраненное состояние для нового процесса. Такое действие системы называется переключением контекста (context switch).

Переключение контекста относится к накладным расходам (overhead), так как система не выполняет никаких полезных действий при переключении с одного процесса на другой.

Время переключения контекста зависит от аппаратной поддержки. Выше мы рассматривали необходимые действия системы в таких случаях - сохранение состояния приостанавливаемого процесса в его PCB и восстановление состояния возобновляемого процесса из его PCB.

Например, в системе "Эльбрус" контекстное переключение выполнялось всего одной аппаратной командой - СМСТЕК (сменить стек, т.е. переключиться с одного облегченного процесса на другой). Однако следует отметить, что такая аппаратная оптимизация была возможна, так как понятие процесса в "Эльбрусе" было фактически сведено к понятию облегченного процесса (lightweight process).

Создание процесса - одна из основных операций над процессами

Процесс-родитель создает дочерние процессы, которые, в свою очередь, создают другие процессы, тем самым формируя дерево процессов.

Возможны различные подходы к созданию процессов, с точки зрения возможности совместного использования (разделения) ресурсов процессом-родителем и дочерним процессом, с точки зрения возможности их параллельного выполнения и с точки зрения адресации и использования памяти.

Разделение ресурсов. Возможны следующие подходы:

ЃE Процесс-родитель и дочерние процессы разделяют все ресурсы;

ЃE Дочерние процессы разделяют подмножество ресурсов процесса-родителя;

ЃE Процесс-родитель и дочерний процесс не имеют общих ресурсов.

Исполнение. Возможны следующие подходы:

ЃE Процесс-родитель и дочерние процессы исполняются совместно;

ЃE Процесс-родитель ожидает завершения дочерних процессов.

Адресация и использование памяти.Возможны следующие подходы:

ЃE Адресное пространство дочернего процесса копирует адресное пространство процесса-родителя; у дочернего процесса имеется программа, загруженная в него;

ЃE Дочерний процесс исполняется в том же пространстве памяти, что и процесс-родитель (облегченный процесс).

В системе UNIX сформулированные вопросы решены следующим образом. fork - системный вызов, создающий новый процесс. Он клонирует память процесса-родителя и создает для дочернего процесса новое виртуальное адресное пространство. После этого выполняется еще один системный вызов - exec (execve)- системный вызов, с целью замены пространства памяти процесса новой программой. Дочерний процесс продолжает выполняться вместо процесса родителя

При запуске системы создается корневой процесс root.Он, в свою очередь, создает три дочерних процесса: init- инициализация системы; pagedaemon - процесс-демон (процесс, постоянно находящийся в системе до ее перезапуска), управляющей страничной организацией памяти; swapper - процесс, управляющий откачкой и подкачкой. Процесс init после инициализации системы запускает пользовательские процессы. Последние, в свою очередь, могут запускать новые и т.д.

Уничтожение процесса

Это также одна из основных операций над процессами. Как правило, процесс уничтожается (завершается), когда он исполняет заключительный оператор и обращается к ОС для своей ликвидации с помощью системного вызова exit. При этом возможна передача данных от дочернего процесса процессу-родителю - например, через файлы, созданные дочерним процессом. Ресурсы процесса освобождаются операционной системой.При своей работе процесс-родитель может уничтожить дочерние процессы системным вызовом abort (UNIX). Это возможно в сле

ЃE Дочерний процесс превысил выделенные ему ресурсы;

ЃE Решения задачи, порученной дочернему процессу, больше не требуется;

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

Предсказание длины следующего периода активности

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

фактическая длина n- го периода активности процесса;

предсказанная длина n- го периода активности процесса.

Будем искать значение для предсказания следующего периода активности процесса как следующую линейную комбинацию tn и :

где - число между 0 и1. Коэффициент характеризует, в какой степени при предсказании учитывается недавняя история вычислений.

Пример предсказания следующего периода активности по приведенной формуле приведен на рис. 11.7.

При т.е. недавняя история не учитывается.

При т.е. учитывается только фактическая длина последнего периода активности.

Если обобщить приведенную формулу, получим:

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

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

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

Данная стратегия, как и предыдущая, имеет варианты с прерыванием и без прерывания.

Более того, стратегию SJF можно рассматривать как диспетчеризацию по приоритетам, в которой приоритетом является очередное время активности.

При диспетчеризации по приоритетам возникает проблема "голодания" (starvation) - ситуации, когда процессы с низким приоритетом могут никогда не исполниться и бесконечно ждать.

Традиционным способом решение данной проблемы в операционных системах является учет возраста процесса (aging): c течением времени приоритет процесса повышается системой.

диспетчеризация вычислительный дескриптор