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

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

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

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

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

·      переключение контекстов «старого» и «нового» процессов. Первые две задачи решаются программными средствами, а по-

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

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

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

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

·      произошла ошибка,

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

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

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

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

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

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

Существует две разновидности приоритетных алгоритмов: алгорит- мы, использующие относительные приоритеты, и алгоритмы, исполь- зующие абсолютные приоритеты.

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

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

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