Билет №31. Алгоритмы планирования, основанные на приоритетах.
Другой важной концепцией, лежащей в основе многих вытесняющих алгоритмов планирования, является приоритетное обслуживание. Приоритетное обслуживание предполагает наличие у потоков некоторой изначально известной характеристики - приоритета, на основании которой определяется порядок их выполнения. Приоритет - это число, характеризующее степень привилегированности потока при использовании ресурсов вычислительной машины, в частности процессорного времени: чем выше приоритет, тем выше привилегии, тем меньше времени будет проводить поток в очередях.
Приоритет может выражаться целым или дробным, положительным или отрицательным значением. В некоторых ОС принято, что приоритет потока тем выше, чем больше (в арифметическом смысле) число, обозначающее приоритет. В других системах, наоборот, чем меньше число, тем выше приоритет.
Во многих ОС предусматривается возможность изменения приоритетов в течение жизни потока. Если ОС сама может изменять приоритеты потоков в зависимости от ситуации, складывающейся в системе, то приоритеты называются динамическими в отличие от неизменяемых, фиксированных, приоритетов.
Существуют две разновидности приоритетного планирования: обслуживание с относительными приоритетами (а) и обслуживание с абсолютными приорите-тами (б).
В обоих случаях выбор потока на выполнение из очереди готовых осуществ-ляется одинаково: выбирается поток, имеющий наивысший приоритет. Однако проблема определения момента смены активного потока решается по-разному. В системах с относительными приоритетами активный поток выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ожидания (или же произойдет ошибка, или поток завершится). В системах с абсолютными приоритетами выполнение активного потока прерывается кроме указанных выше причин, еще при одном условии: если в очереди готовых потоков появился поток, приоритет которого выше приоритета активного потока. В этом случае прерванный поток переходит в состояние готовности.
В системах пакетной обработки (в том числе известной ОС OS/360) относитель-ные приоритеты широко используются. А планирование на основе абсолютных приоритетов является подходящим для систем управления объектами, в которых важна быстрая реакция на событие.
Из учебника Олифера
Другой важной концепцией, лежащей в основе многих вытесняющих алгорит-мов планирования, является приоритетное обслуживание. Приоритетное обслу¬живание предполагает наличие у потоков некоторой изначально известной характеристики — приоритета, на основании которой определяется порядок их выполнения. Приоритет — это число, характеризующее степень привилегиро¬ванности потока при использовании ресурсов вычислительной машины, в част¬ности процессорного времени: чем выше приоритет, тем выше привилегии, тем меньше времени будет проводить поток в очередях.
Приоритет может выражаться целым или дробным, положительным или отрица¬тельным значением. В некоторых ОС принято, что приоритет потока тем выше, чем больше (в арифметическом смысле) число, обозначающее приоритет. В дру¬гих системах, наоборот, чем меньше число, тем выше приоритет.
В большинстве операционных систем, поддерживающих потоки, приоритет по¬тока непосредственно связан с приоритетом процесса, в рамках которого выпол¬няется данный поток. Приоритет процесса назначается операционной системой при его создании. Значение приоритета включается в описатель процесса и используется при назначении приоритета потокам этого процесса. При назначении приоритета вновь созданному процессу ОС учитывает, является этот процесс системным или прикладным, каков статус пользователя, запустившего процесс, было ли явное указание пользователя на присвоение процессу определенного уровня приоритета. Поток может быть инициирован не только по команде поль¬зователя, но и в результате выполнения системного вызова другим потоком. В этом случае при назначении приоритета новому потоку ОС должна принимать во внимание значение параметров системного вызова.
Во многих ОС предусматривается возможность изменения приоритетов в тече¬ние жизни потока. Изменение приоритета могут происходить по инициативе самого потока, когда он обращается с соответствующим вызовом к операцион¬ной системе, или по инициативе пользователя, когда он выполняет соответст¬вующую команду. Кроме того, ОС сама может изменять приоритеты потоков в зависимости от ситуации, складывающейся в системе. В последнем случае при¬оритеты называются динамическими в отличие от неизменяемых, фиксирован¬ных, приоритетов.
От того, какие приоритеты назначены потокам, существенно зависит эффектив¬ность работы всей вычислительной системы. В современных ОС во избежание разбалансировки системы, которая может возникнуть при неправильном назна¬чении приоритетов, возможности пользователей влиять на приоритеты процес¬сов и потоков стараются ограничивать. При этом обычные пользователи, как правило, не имеют права повышать приоритеты своим потокам, это разрешено делать (да и то в определенных пределах) только администраторам. В большин¬стве же случаев ОС присваивает приоритеты потокам по умолчанию.
В качестве примера рассмотрим схему назначения приоритетов потокам, приня¬тую в операционной системе Wihdows NT (рис. 4.9). В системе определено 32 уровня приоритетов и два класса потоков — потоки реального времени и по¬токи с переменными приоритетами. Диапазон от 1 до 15 включительно отведен для потоков с переменными приоритетами, а от 16 до 31 — для более критичных ко времени потоков реального времени (приоритет 0 зарезервирован для систем¬ных целей).
При создании процесса он в зависимости от класса получает по умолчанию ба¬зовый приоритет в верхней или нижней части диапазона. Базовый приоритет процесса в дальнейшем может быть повышен или понижен операционной систе¬мой. Первоначально поток получает значение базового приоритета из диапазона базового приоритета процесса, в котором он был создан. Пусть, например, значе¬ние базового приоритета некоторого процесса равно К. Тогда все потоки данного процесса получат базовые приоритеты из диапазона [К-2, К+2]. Отсюда видно, что, изменяя базовый приоритет процесса, ОС может влиять на базовые приори¬теты его потоков.
В Windows NT с течением времени приоритет потока, относящегося к классу по¬токов с переменными приоритетами, может отклоняться от базового приоритета потока, причем эти изменения могут быть не связаны с изменениями базового приоритета процесса. ОС может повышать приоритет потока (который в этом случае называется динамическим) в тех случаях, когда поток не полностью ис¬пользовал отведенный ему квант, или Яонижать приоритет, если квант был ис¬пользован полностью. ОС наращивает приоритет дифференцированно в зави¬симости от того, какого типа событие не дало потоку полностью использовать квант. В частности, ОС повышает приоритет в большей степени потокам, кото¬рые ожидают ввода с клавиатуры (интерактивным приложениям) и в меньшей степени — потокам, выполняющим дисковые операции. Именно на основе дина¬мических приоритетов осуществляется планирование потоков. Начальной точ-кой отсчета для динамического приоритета является значение базового приори¬тета потока. Значение динамического приоритета потока ограничено снизу его базовым приоритетом, верхней же границей является нижняя граница диапазона приоритетов реального времени.
Существуют две разновидности приоритетного планирования: обслуживание с относительными приоритетами и обслуживание с абсолютными приоритетами.
В обоих случаях выбор потока на выполнение из очереди готовых осуществляет¬ся одинаково: выбирается поток, имеющий наивысший приоритет. Однако про-блема определения момента смены активного потока решается по-разному. В сис¬темах с относительными приоритетами активный поток выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ожидания (или же про-изойдет ошибка, или поток завершится). На рис. 4.10, а показан граф состояний потока в системе с относительными приоритетами.
В системах с абсолютными приоритетами выполнение активного потока преры¬вается кроме указанных выше причин, еще при одном условии: если в очереди готовых потоков появился поток, приоритет которого выше приоритета активно¬го потока. В этом случае прерванный поток переходит в состояние готовности (рис. 4.10, б).
В системах, в которых планирование осуществляется на основе относительных приоритетов, минимизируются затраты на переключения процессора с одной ра-боты на другую. С другой стороны, здесь могут возникать ситуации, когда одна задача занимает процессор долгое время. Ясно, что для систем разделения вре¬мени и реального времени такая дисциплина обслуживания не подходит: интер¬активное приложение может ждать своей очереди часами, пока вычислительной задаче не потребуется ввод-вывод. А вот в системах пакетной обработки (в том числе известной ОС OS/360) относительные приоритеты используются широко.
Рис. 4.10. Графы состояний потоков в системах с относительными и абсолютными приоритетами
В системах с абсолютными приоритетами время ожидания потока в очередях может быть сведено к минимуму, если ему назначить самый высокий приоритет. Такой поток будет вытеснять из процессора все остальные потоки (кроме пото¬ков, имеющих такой же наивысший приоритет). Это делает планирование на ос¬нове абсолютных приоритетов подходящим для систем управления объектами, в которых важна быстрая реакция на событие.
