Лекция: Уровни приоритетов потоков в Windows 2000
В Windows 2000 предусмотрено 32 уровня приоритета, которые организованы в виде двух групп или классов — реального времени и переменные (динамические) /7,8,11,13/. Каждая из этих групп состоит из 16 уровней приоритета, как показано на рис.5.1.
Приоритеты из разных классов обрабатываются несколько по-разному. В классе приоритетов реального времени все потоки имеют фиксированный приоритет, который никогда не изменяется, и все активные потоки с определенным уровнем приоритета располагаются в круговой очереди данного уровня (рис.5.1).
В классе переменных (динамических) приоритетов поток начинает работу с некоторым изначально присвоенным ему приоритетом, который затем может изменяться – как в большую, так и в меньшую сторону. Таким образом, на каждом уровне приоритета имеется своя очередь, но процессы могут переходить из одной очереди в другую в пределах одного класса переменных приоритетов. Нулевой уровень приоритета используется потоком обнуления страниц и Win32 недоступен. Поток с приоритетом 15 не может получить приоритет 16, как и какой-либо другой приоритет из класса реального времени.
Преимущества планирования с динамическими приоритетами уже были продемонстрированы в предыдущем разделе на примерах систем реального времени. Хотя Windows 2000 относится к ОС свободного времени, преимущества планирования с динамическими приоритетами в этой ОС в значительной мере также реализованы.
Win32 API упорядочивает процессы по уровням приоритета, назначенным при их создании следующим образом: Real time (реального времени), High (высокий), Above Normal (выше обычного), Normal (обычный), Below Normal (ниже обычного) и Idle (простаивающий) /11/. Каждой из указанных шести групп уровней приоритетов соответствует определенный диапазон приоритетов, и значения приоритетов из середин диапазонов называются базовыми приоритетами процессов. Обычно базовые приоритеты групп процессов по умолчанию равны соответственно 24, 13, 10, 8, 6, 4.
После активизации потока из класса переменных приоритетов его действительный приоритет (именуемый динамическим приоритетом потока) может колебаться в определенных пределах – он не может уменьшиться ниже наименьшего относительного приоритета потока или подняться выше максимально возможного значения приоритета данного класса, т.е. 15.
На рис.5.2. приведен пример процесса с базовым приоритетом, равным 4. Каждый поток, связанный с данным процессом, должен иметь начальный приоритет от 2 до 6, и в процессе работы значения динамических приоритетов потоков могут колебаться в диапазоне от 2 до 15.
Если поток прерывается в связи с тем, что он полностью использовал отпущенный ему квант времени, исполнительная система Windows 2000 снижает его приоритет; если же поток прерван в связи с ожиданием завершения операции ввода-вывода, его приоритет повышается. Таким образом, имеется тенденция повышения приоритетов потоков, ориентированных на ввод-вывод, и снижения приоритетов (до уровня базового приоритета), ориентированных на вычисления. В потоках, ориентированных на ввод-вывод, приоритет потоков, ожидающих завершения интерактивной операции (например, вывод на экран или ввод с клавиатуры) повышается больше, чем для других операций ввода-вывода (например, дисковых). Следовательно, в пределах класса переменных приоритетов интерактивные потоки стремятся к получению наивысшего приоритета.
В Windows 2000 никогда динамически не изменяются приоритеты потоков в классе приоритетов реального времени (16 – 31), поэтому у таких потоков базовый приоритет идентичен текущему.
Использование динамических приоритетов является одним из основных методов обеспечения гарантии обслуживания. Действительно, если приоритеты фиксированы, возникает дискриминация низкоприоритетных задач, в результате чего они вследствие высокой загрузки процессора длительное время могут не получать процессорное время и поэтому не выполняться.
Особенности алгоритма планирования в Windows 2000
ОС Windows 2000 (W2K) разработана таким образом, чтобы быть по возможности максимально чувствительной либо к запросам отдельного пользователя в интерактивной среде (Windows 2000 Professional), либо запросам группы пользователей сети при использовании ОС серверной версии (Windows 2000 или Server Advanced Server).
Следует заметить, что алгоритмы планирования Windows 2000 для одно- и многопроцессорных систем отличаются. Ниже будет рассмотрен алгоритм планирования для однопроцессорных ВС.
В Windows 2000 реализован вытесняющий планировщик, использующий как концепцию абсолютных приоритетов, так и концепцию квантования. На каждом из уровней класса приоритетов реального времени применяется циклическое (карусельное) RR планирование. В классе переменных приоритетов также используется карусельное планирование, дополненное возможностью динамического изменения приоритета на основе текущей активности потоков (рис.5.1) /11/.
Выбранный для выполнения поток работает в течение определенного кванта времени. После завершения кванта времени планировщик решет, какой другой ожидающий поток поставить на выполнение. Потокам выделяются разные кванты, их длительность в, частности, зависит от версии ОС — Windows 2000 Professional или Windows 2000 или Server Advanced Server. Однако поток может не полностью использовать свой квант. Это происходит, если в очереди готовых к выполнению потоков появляется поток с более высоким приоритетом. Тогда текущий выполняемый поток вытесняется, даже если его квант еще не истек. Фактически поток может быть выбран следующим для выполнения и вытеснен, не успев воспользоваться своим квантом.
Код Windows 2000, отвечающий за планирование, реализован в ядре ОС. Совокупность процедур, выполняющих эти обязанности, называется диспетчером ядра (kernel`s dispatcher). Диспетчеризация потоков осуществляется при прерываниях уровня «DPC/dispatch» и инициируется событиями:
поток готов к выполнению (например, создан или вышел из состояния ожидания);
поток выходит из состояния выполнения (например, квант истек, поток завершается или переходит в состояние ожидания);
приоритет потока изменяется в результате вызова системного сервиса или самой Windows 2000;
изменяется привязка к процессорам выполняемого потока (в случае мультипроцессорных SMP-систем).
После выбора нового потока, Windows 2000 переключает контекст. Эта операция заключается в сохранении параметров состояния ВС, связанных с выполняемым потоком, и загрузке аналогичных параметров для другого потока, после чего начинается выполнение нового потока.
В типичном случае переключение контекста требует сохранения и восстановления следующих данных:
программного счетчика (program counter);
регистра состояния процессора;
содержимого остальных регистров процессора (РОН и других);
указателя на стек ядра и пользовательский стек;
указателя на адресное пространство, в котором выполняется поток (каталог таблиц страниц процесса).
Ядро сохраняет эту информацию, записывая ее текущий стек ядра, обновляя указатель стека и сохраняя его в блоке KTHREAD потока. Далее указатель стека ядра устанавливается на стек ядра нового потока и производится загрузка контекста нового потока.
Следует обратить внимание на то, что планирование в Windows 2000 осуществляется на уровне потоков, т.е. система не обращает внимание на то, какому процессу принадлежит тот или иной поток.
Рассмотрим на примерах отдельных сценариев планирования как практически работает приведенный выше алгоритм /11/.
1.Самостоятельное переключение. Поток может самостоятельно освободить процессор, перейдя в состояние ожидания на каком-либо объекте (например, событии, мьютексе, семафоре, порте ввода-вывода, процессе, потоке и др.) путем вызова одной из функций ожидания Win32 API (например, WaitForSingleObject или WaitForMultipleObject). Если поток переходит в состояние ожидания, не израсходовав выделенный ему квант времени полностью, то его квант не сбрасывается. В этом случае после успешного завершения ожидания квант потока уменьшается на одну квантовую единицу, что эквивалентно одной трети интервала таймера. Исключение составляют потоки, приоритет которых от 14 и выше, у которых после ожидания квант сбрасывается.
2.Вытеснение. Поток с более низким приоритетом вытесняется готовым к выполнению потоком с более высоким приоритетом. Такая ситуация может явиться следствием двух обстоятельств:
завершилось ожидание потока с более высоким приоритетом (т.е. произошло событие, которого он ждал);
приоритет потока увеличился или уменьшился.
Когда поток вытесняется, он помещается в начало очереди готовых потоков соответствующего уровня приоритета. При возобновлении потока с приоритетом из класса реального времени его квант сбрасывается до исходного значения. Потоки с приоритетом из класса переменных в той же ситуации используют оставшийся квант. После завершения вытеснившего потока вытесненный сможет отработать остаток своего кванта.
3.Завершение кванта. Когда поток полностью израсходует свой квант процессорного времени, Windows 2000 решает, следует ли понизить его приоритет и подключить к процессору другой поток. Снизив приоритет потока, Windows 2000 ищет более подходящий для выполнения поток, например, любой готовый для выполнения поток с приоритетом выше нового приоритета текущего потока. Если приоритет не изменялся, и в очереди готовых потоков есть другие потоки с тем же приоритетом, ОС выбирает следующий поток с тем же приоритетом, а выполнявшийся до этого помещает в хвост очереди. Если ни один поток с тем же приоритетом не готов к выполнению, текущему потоку выделяется еще один квант процессорного времени.
4.Завершение потока. Завершаясь, (например, после вызова функции ExitThread или TerminateThread) поток переходит в состояние Terminated. Если в этот момент ни один описатель его объекта «поток» не открыт, он удаляется из списка потоков процесса, а соответствующие структуры данных освобождаются.
5.Поток простоя. Если нет ни одного потока, готового к выполнению на процессоре, Windows 2000 подключает к данному процессору поток простоя (процесса Idle). Для каждого процессора создается свой поток простоя, работающий вне приоритетов, так как он работает лишь в отсутствии других потоков. Этот поток выполняет следующие действия:
включает и выключает прерывания, давая возможность выполнить отложенные прерывания;
проверяет, есть ли у процессора отложенные программные прерывания DPC и организует их выполнение;
проверяет, выбран ли какой-нибудь поток для выполнения на данном процессоре, и, если да, то организует его диспетчеризацию;
вызывает процедуру обработки процессора в простое (если нужно выполнить какие-либо функции управления электропитанием).
Для принятия решений при планировании потоков ядро поддерживает набор структур данных, в совокупности известных как база данных диспетчера ядра (dispatcher database). Эта база данных позволяет отслеживать потоки, ждущие выполнения, и принадлежность потоков процессам. Самой важной структурой в базе данных диспетчера ядра является очередь готовых потоков (ready queue), находящаяся в KiDispatcherReadyListHead – списке заголовков для 32 очередей готовых потоков (по одной для каждого приоритета).
Для ускорения выбора потока, подлежащего выполнению или вытеснению, Windows 2000 поддерживает 32-битовую маску, называемую сводкой готовности (ready summary) (KiReadySummary). Каждый установленный в ней бит указывает на присутствие одного или более потоков в очереди готовых потоков для данного уровня приоритета (бит 0 соответствует приоритету 0, бит 1 – приоритету 1 и т.д.). Кроме того, Windows 2000 поддерживает сводку простоя (idle summary) (KidleSummary), в которой каждый установленный бит представляет простаивающий процессор.