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

Дата добавления: 2013-12-23; просмотров: 4854; Нарушение авторских прав

Выполнить самостоятельно расчет среднего времени ожидания и среднего полного времени выполнения для обратного порядка процессов. На производительность алгоритма очень влияет величина кванта времени. Рассмотрим тот же самый пример с порядком процессов p0, p1, p2 для величины кванта времени, равной 1 (см. таблица 3.3). Время ожидания для процесса p0 составит 5 единиц времени, для процесса p1 – тоже 5 единиц, для процесса p2 – 2 единицы. В этом случае среднее время ожидания получается равным (5 + 5 + 2)/3 = 4 единицам времени. Среднее полное время исполнения составит (18 + 9 + 3)/3 = 10 единиц времени. Таблица 3.3. Время p0 В Г Г В Г В Г В Г В В В В В В В В В p1 Г В Г Г В Г В Г В                   p2 Г Г В                               Таким образом, в данном алгоритме очень важно правильно выбирать размер кванта.

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

Приоритет может выражаться целым, дробным, положительным

или отрицательным значением.

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

Приоритет может:

1) назначаться директивно администратором системы в зависимости от важности работы или внесенной платы;

2) вычисляться самой ОС по определенным правилам;

3) оставаться фиксированным на протяжении всей жизни процесса;

4)изменяться во времени в соответствии с некоторым законом.

В последнем случае приоритеты называются динамическими, в отличие от неизменяемых, фиксированных приоритетов.

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

- с относительными приоритетами;

- с абсолютными приоритетами.

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

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

Процесс завершен или ошибка

Выбор по приоритету Ожидание завершения ввода-вывода

Ввод-вывод

завершен

Создание процесса

Граф состояний потока в системе с относительными приоритетами

Здесь минимизируются затраты на переключение процессора с одной работы на другую. Используется в ОС с пакетной обработкой.

Пусть в очередь процессов, находящихся в состоянии Готовность, поступают процессы p₀, p₁, p₂, p₃ только им дополнительно еще присвоены приоритеты (см. таблица 3.8).

В вычислительных системах не существует определенного соглашения, какое значение приоритета – 1 или 4 считать более приоритетным. Во избежание путаницы, во всех наших примерах мы будем предполагать, что большее значение соответствует меньшему приоритету, т. е. наиболее приоритетным в нашем примере является процесс p₃, а наименее приоритетным – процесс p₀.

Первым для выполнения в момент времени t = 0 выбирается процесс p₃, как обладающий наивысшим приоритетом. После его завершения в момент времени t = 5 в очереди процессов, готовых к исполнению, окажутся два процесса p₀ и p₁. Больший приоритет из них у процесса p₁, он и начнет выполняться (см. таблица 3.9). Затем в момент времени t = 8 для исполнения будет избран процесс p₂, и лишь потом – процесс p₀.

Время ожидания: p₀ =14 p_{1 = 3} p_{2 =1} p₃₌₀

Время ожидания = (11+3+1+0)/4

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

состояние Готовность.

Граф состояний потока в системе с абсолютными приоритетами

Процесс завершен или ошибка

Выбор по приоритету Ожидание завершения

В очереди процесс ввода-вывода

с более высоким

приоритетом

Ввод-вывод

завершен

Создание потока

Пусть в очередь процессов, находящихся в состоянии Готовность, поступают процессы p₀, p₁, p₂, p₃ только им дополнительно еще присвоены приоритеты (см. таблица 3.8).

Первым, как и в предыдущем случае, начнет исполняться процесс p₃, а по его окончании – процесс p₁. Однако в момент времени t = 6 он будет вытеснен процессом p₂ и продолжит свое выполнение только в момент времени t = 13. Последним, как и раньше, будет исполняться процесс p₀.

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

С самых общих позиций все множество алгоритмов планирования можно разде­лить на два класса: вытесняющие (preemptive) и невытесняющие (non-preemptive) алгоритмы планирования.

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

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

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

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

Бесприоритетная дисциплина планирования, основанная на выделении равных квантов времени для всех задач, относится к вытесняющим алгоритмам.

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

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

При этом ОС выполняет следующие функции:

- определяет момент снятия с выполнения активной задачи,

- запоминает ее контекст,

- выбирает из очереди готовых задач следующую и

- запускает ее на выполнение, загружая ее контекст.

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

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

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

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

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

Преимуществом невытесянющих систем является более высокая скорость переключения с задачи на задачу.

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

Однако почти во всех современных операционных системах, ориентированных на высокопроизводительное выполнение приложений (UNIX, Windows NT, OS/2, VAX/VMS), реализована вытесняющая многозадачность. В последнее время дошла очередь и до ОС класса настольных систем, например, OS/2 Warp и Windows 95. Возможно в связи с этим вытесняющую многозадачность часто называют истинной многозадачностью.