Сетевые операционные системы

Глава 4. Процессы и потоки

2004-10-19

Продолжение

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

Кванты, выделяемые потокам, могут быть одинаковыми для всех по-токов или различными. Рассмотрим, например, случай, когда всем потокам предоставляются кванты одинаковой длины q (рис. 4.7). Если в системе име-ется n потоков, то время, которое поток проводит в ожидании следующего кванта, можно грубо оценить как q(n-l). Чем больше потоков в системе, тем больше время ожидания, тем меньше возможности вести одновременную ин-терактивную работу нескольким пользователям. Но если величина кванта выбрана очень небольшой, то значение произведения q(n-l) все равно будет достаточно мало для того, чтобы пользователь не ощущал дискомфорта от присутствия в системе других пользователей. Типичное значение кванта в системах разделения времени составляет десятки миллисекунд.

Если квант короткий, то суммарное время, которое проводит поток в ожидании процессора, прямо пропорционально времени, требуемому для его выполнения (то есть времени, которое потребовалось бы для выполнения этого потока при монопольном использовании вычислительной системы). Действительно, поскольку время ожидания между двумя циклами выполне-ния равно q(n-l), а количество циклов B/q, где В - требуемое время выполне-ния, то W=B(n-l). Заметим, что эти соотношения представляют собой весьма грубые оценки, основанные на предположении, что В значительно превыша-ет q. При этом не учитывается, что потоки могут использовать кванты не полностью, что часть времени они могут тратить на ввод-вывод, что количе-ство потоков в системе может динамически меняться и т.д.

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

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

Потоки получают для выполнения квант времени, но некоторые из них используют его не полностью, например из-за необходимости выполнить ввод или вывод данных. В результате возникает ситуация, когда потоки с ин-тенсивными обращениями к вводу-выводу используют только небольшую часть выделенного им процессорного времени. Алгоритм планирования мо-жет исправить эту "несправедливость". В качестве компенсации за неисполь-зованные полностью кванты потоки получают привилегии при последующем обслуживании. Для этого планировщик создает две очереди готовых потоков (рис. 4.8). Очередь 1 образована потоками, которые пришли в состояние готовности в результате исчерпания кванта времени, а очередь 2 - потоками, у которых завершилась операция ввода-вывода. При выборе потока для выполнения прежде всего просматривается вторая очередь, и только если она пус-та, квант выделяется потоку из первой очереди.

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

ПРИМЕЧАНИЕ. В алгоритмах, основанных на квантовании, какую бы цель они не пре-следовали (предпочтение коротких или длинных задач, компенсация недоиспользованно-го кванта или минимизация накладных расходов, связанных с переключениями), не ис-пользуется никакой предварительной информации о задачах. При поступлении задачи на обработку ОС не имеет никаких сведений о том, является ли она короткой или длинной, насколько интенсивными будут ее запросы к устройствам ввода-вывода, насколько важно ее быстрое выполнение и т.д. Дифференциация обслуживания при квантовании базирует-ся на "истории существования" потока в системе.

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

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

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

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

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

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

В качестве примера рассмотрим схему назначения приоритетов пото-кам, принятую в операционной системе Windows NT (рис. 4.9). В системе оп-ределено 32 уровня приоритетов и два класса потоков - потоки реального времени и потоки с переменными приоритетами. Диапазон от 1 до 15 вклю-чительно отведен для потоков с переменными приоритетами, а от 16 до 31 - для более критичных ко времени потоков реального времени (приоритет 0 зарезервирован для системных целей).

При создании процесса он в зависимости от класса получает по умолчанию базовый приоритет в верхней или нижней части диапазона. Базовый приоритет процесса в дальнейшем может быть повышен или понижен операционной системой. Первоначально поток получает значение базового приоритета из диапазона базового приоритета процесса, в котором он был создан. Пусть, например, значение базового приоритета некоторого процесса равно К. Тогда все потоки данного процесса получат базовые приоритеты из диапазона [К-2, К+2]. Отсюда видно, что, изменяя базовый приоритет процесса, ОС может влиять на базовые приоритеты его потоков.

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

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

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

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

В системах, в которых планирование осуществляется на основе отно-сительных приоритетов, минимизируются затраты на переключения процес-сора с одной работы на другую. С другой стороны, здесь могут возникать си-туации, когда одна задача занимает процессор долгое время. Ясно, что для систем разделения времени и реального времени такая дисциплина обслужи-вания не подходит: интерактивное приложение может ждать своей очереди часами, пока вычислительной задаче не потребуется ввод-вывод. А вот в сис-темах пакетной обработки (в том числе известной ОС OS/360) относительные приоритеты используются широко.

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

Смешанные алгоритмы планирования

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

Рассмотрим более подробно алгоритм планирования в операционной системе UNIX System V Release 4. В этой ОС понятие "поток" отсутствует, и планирование осуществляется на уровне процессов. В системе UNIX System V Release 4 реализована вытесняющая многозадачность, основанная на ис-пользовании приоритетов и квантования.

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

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

Процессы разделения времени были до появления UNIX System V Release 4 единственным классом процессов, и по умолчанию UNIX System V Release 4 назначает новому процессу именно этот класс. Состав класса про-цессов разделения времени наиболее неопределенный и часто меняющийся в отличие от системных процессов и процессов реального времени. Для спра-ведливого распределения времени процессора между процессами в этом классе используется стратегия динамических приоритетов. Величина при-оритета, назначаемого процессам разделения времени, вычисляется пропор-ционально значениям двух составляющих: пользовательской части и систем-ной части. Пользовательская часть приоритета может быть изменена админи-стратором и владельцем процесса, но в последнем случае только в сторону его снижения.

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

Другой пример относится к операционной системе OS/2. Планирова-ние здесь основано на использовании квантования и абсолютных динамиче-ских приоритетов. На множестве потоков определены приоритетные классы - критический (time critical), серверный (server), стандартный (regular) и оста-точный (idle), в каждом из которых имеется 32 приоритетных уровня. Потоки критического класса имеют наивысший приоритет. В этот класс могут быть отнесены, например, системные потоки, выполняющие задачи управления сетью. Следующий по приоритетности класс предназначен, как это следует из его названия, для потоков, обслуживающих серверные приложения. К стандартному классу могут быть отнесены потоки обычных приложений. По-токи, входящие в остаточный класс, имеют самый низкий приоритет. К этому классу относится, например, поток, выводящий на экран заставку, когда в системе не выполняется никакой работы.

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

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

ОС динамически устанавливает величину кванта, отводимого потоку для выполнения. Величина кванта зависит от загрузки системы и интенсив-ности подкачки. Параметры настройки системы позволяют явно задать гра-ницы изменения кванта. В любом случае он не может быть меньше 32 мс и больше 65 536 мс. Если поток был прерван до истечения кванта, то следую-щий выделенный ему интервал выполнения будет увеличен на время, равное одному периоду таймера (около 32 мс), и так до тех пор, пока квант не дос-тигнет заранее заданного при настройке ОС предела. Благодаря такому алгоритму планирования в OS/2 ни один поток не будет "забыт" системой и получит достаточно процессорного времени.

Продолжение следует...