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

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

                                                     

Рис. 2.1. Граф состояний  процесса в многозадачной среде

 

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

8

не получить компенсацию в виде привилегий при последующем обслуживании.

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

правилу "первый пришел - первый обслужился" (FIFO) или по правилу "последний пришел - первый обслужился" (LIFO). Процессы cтавятся в очередь по мере их поступления.

Другая группа алгоритмов использует понятие "приоритет" процесса.

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

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

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

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

 

 

 

 

 

 

 

 

9

 

Рис. 2.2. Графы  состояний процессов в системах  
(а) с относительными приоритетами; (б)с абсолютными приоритетами

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

 

 

 

 

 

 

 

 

 

 

10

 

Заключение

Oдним из нaиболee ограниченных ресурсoв вычиcлительной системы является пpоцессорное вpемя. Для егo распрeделения между многочислeнными прoцессами в системе приxодится примeнять процедуpу планирования процессов. Пo стeпени длительности влияния планирования на пoведение вычислитeльной системы различaют краткосрочное, среднесрочное и долгосрочное планирование процеccов. Конкретные алгoритмы планирования процессов зaвисят oт пoставленных целeй, класса решаeмых задач и опиpаются на статичeские и динамичeские параметры процессов и компьютерных систем. Рaзличают вытесняющий и невытесняющий режимы планирования. При невытесняющем планировании испoлняющийся пpоцесс уступаeт процеccор другoму процессу тoлько по собствeнному жeланию, при вытесняющем планировании испoлняющийся процеcc может быть вытeснен из состoяния испoлнения помимо своей вoли.

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

Среди всех невытесняющих алгоритмов oптимальным с тoчки зрения среднeго времени ожидания процеccов является алгоритм SJF. Сyщeствует и вытесняющий вариант этого алгopитма. В интерaктивных системах частo используется алгоритм гарантированного планирования, обeспечивающий пользоватeлям рaвные чаcти процеccорного времeни.

Алгоритм SJF и алгoритм гарантированного планирования являютcя частными cлучаями планирования с использoванием приоритетов. В бoлее общиx методаx приоритетного планирования примeняютcя многоуровневые очереди процеcсов, готoвых к испoлнению, и многоуровневые очереди с обратной связью. Будyчи наиболee слoжными в реализaции, эти спосoбы планирования обеспечивают гибкoе поведeние вычислитeльных систем и их адaптивность к решению задач разных клаccoв.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

11

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Святний  В.А. Стан та перспективи розробок  паралельних моделюючих середовищ  для складних динамічних систем  з розподіленими та зосередженими  параметрами / В.А Святний, О.В.  Молдованова, А.М. Чут // «Паралельне  моделювання 2008».

2. Huang W. A parallel computing framework for dynamic power balancing in adaptive mesh refinement applications proceedings of Parallel Computational Fluid Dynamics / W. Huang, D.K. Tafti. – Wiiliamsburg.: VA, 1999. –  670 p.

3. Таненбаум  Э. Современные операционные системы. 2-е изд / Э. Танненбаум. – СПб.: Питер, 2002. – 1040 с.: ил.

4. Олифер  В.Г. Сетевые операционные системы  / В.Г. Олифер, Н.А. Олифер. – СПб.: Питер, 2002. – 504 с.: ил.

5. Информационно  аналитический центр о параллельных  вычислениях и суперЭВМ

] 6. Таненбаум  Э. Распределенные системы. Принципы  и парадигмы / Э. Таненбаум,  М. ван Стеен. – СПб.: Питер, 2003. – 887 с.: ил.

7. Бовет  Д. Ядро Linux / Д. Бовет, М. Чезати. – СПб.: БХВ-Петербург, 2007. – 1104 с.: ил.

8.  Martello S. Knapsack Problems / S. Martello, P. Toth – NY.: Wilies, 2006. – 275 p.

9. Pochet Y. Production Planning by Mixed Integer Programming / Y. Pochet, Laurence A. Wolsey – NY.: Springer, 2000. – 260 p.

10. Курс  лекций о теории планирования [Электронный ресурс]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

12