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

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

задач:

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

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

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

Существует  множество  различных  алгоритмов  планирования

процессов, 

по-разному  решающих  вышеперечисленные  задачи, 

преследующих  различные  цели  и  обеспечивающих  различное 

качество 

мультипрограммирования. 

Среди 

множества 

алгоритмов  рассмотрим  подробнее  две  группы  наиболее  часто 

встречающихся  алгоритмов:  алгоритмы,  основанные  на  квантовании 

(рисунок 8 а), и алгоритмы, основанные на приоритетах (рисунок 8 б).

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

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

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

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

- процесс перешел в состояние «ожидание»;

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

процессу.

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

«готовность»  и  ожидает,  когда  ему  будет  предоставлен  новый  квант 

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

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

готовых.  Таким  образом,  ни  один  процесс  не  занимает  процессор 

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

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

организована:  циклически,  по  правилу  «первый  пришел  -  первый 

обслужился»  (FIFO)  или  по  правилу  «последний  пришел  -  первый 

обслужился» (LIFO).

Другая  группа  алгоритмов  использует  понятие  «приоритет» 

процесса. 

Приоритет  -   это  число,  характеризующее  степень 

привилегированности 

процесса 

при 

ресурсов 

вычислительной  машины.  Чем  выше  привилегии  процесса  (выше 

приоритет),  тем  меньше  времени  он  будет  проводить  в  очередях. 

Приоритет  может  назначаться  директивно  администратором  системы

28

в  зависимости  от  важности  работы,  либо  вычисляться  самой  ОС  по 

определенным  правилам,  он  может  оставаться  фиксированным  на 

протяжении  всей  жизни  процесса  либо  изменяться  во  времени  в 

соответствии  с  некоторым  законом.  Существует  две  разновидности 

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

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

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

осуществляется 

одинаково: 

выбирается 

процесс, 

имеющий 

наивысший  приоритет.  По-разному  решается  проблема  определения 

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

приоритетами активный процесс  выполняется  до тех  пор,  пока он сам 

не  покинет процессор,  перейдя  в состояние  «ожидание».  В  системах с 

абсолютными  приоритетами  выполнение  активного  процесса  может 

быть  прервано,  если  в  очереди  готовых  процессов  появился  процесс, 

приоритет  которого  выше  приоритета  активного  процесса.  В  этом 

случае прерванный процесс переходит в состояние готовности.

(а)  -   с  относительными  приоритетами;  (б)  -   с  абсолютными 

приоритетами

Рисунок 8 -  Граф состояний процесса в многозадачной среде

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

построены  с  использованием,  как  квантования,  так  и  приоритетов. 

Например,  в  основе  планирования  лежит  квантование,  но  величина 

кванта  и/или  порядок  выбора  процесса  из  очереди  готовых 

определяется приоритетами процессов.

жүктеу/скачать 3,3 Mb.

Достарыңызбен бөлісу: