2.1.3. Алгоритмы планирования процессов

Планирование процессов включает в себя решение следующих задач:

• определение момента времени для смены выполняемого процесса;

• выбор процесса на выполнение из очереди готовых процессов;

• переключение контекстов «старого» и «нового» процессов.

Первые две задачи решаются программными средствами, а последняя – в значительной степени аппаратно.

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

• алгоритмы, основанные на квантовании;

• алгоритмы, основанные на приоритетах.

Алгоритмы, основанные на квантовании. Каждому процессу предоставляется квант процессорного времени. Кванты могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процесс, который исчерпал свой квант времени, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение выбирается новый процесс из очереди. Очередь готовых процессов может быть организована в соответствии с определенным правилом: циклически, по правилу «первый пришел – первый обслужился» (FIFO) или по правилу «последний пришел – первый обслужился» (LIFO). Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода/вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании.

В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если:

• процесс завершился и покинул систему;

• произошла ошибка;

• процесс перешел в состояние ОЖИДАНИЕ;

• исчерпан квант процессорного времени, отведенный данному процессу.

Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени.

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

Существует две разновидности приоритетных алгоритмов:

• алгоритмы, использующие относительные приоритеты;

• алгоритмы, использующие абсолютные приоритеты.

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

В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится).

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

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

Вытесняющие и невытесняющие алгоритмы планирования. Существует два основных типа планирования процессов: вытесняющие (preemptive) и невытесняющие (non-preemptive).

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

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

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

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