Если операционная система поддерживает многопоточность, она может распределять процессорное время либо между процессами, либо между потоками. В операционной системе Windows процессор предоставляется потокам, иначе говоря, осуществляется планирование на уровне потоков.
Таким образом, если один процесс имеет пять потоков, а второй – десять, то первый процесс будет занимать процессор в два раза больше времени, чем второй (при условии, конечно, что все потоки имеют равный приоритет и выполняют примерно одинаковую работу).
Существуют разные алгоритмы планирования. Рассмотрим основные виды.
1. Вытесняющие/невытесняющие алгоритмы.
В случае вытесняющего алгоритма операционная система в любой момент времени может прервать выполнение текущего потока и переключить процессор на другой поток. В невытесняющих алгоритмах поток, которому предоставлен процессор, только сам решает, когда передать управление операционной системе.
2. Алгоритмы с квантованием.
Каждому потоку предоставляется квант времени, в течение которого поток может выполняться на процессоре. По истечении кванта операционная система переключает процессор на следующий поток в очереди. Квант обычно равен целому числу интервалов
3. Алгоритмы с приоритетами.
Каждому потоку назначается приоритет (priority) – целое число, обозначающее степень привилегированности потока. Операционная система при наличии нескольких готовых к выполнению потоков выбирает из них поток с наибольшим приоритетом.
В Windows реализован смешанный алгоритм планирования – вытесняющий, на основе квантования и приоритетов.
За время своего существования поток может находиться в нескольких состояниях. Перечислим основные состояния:
Кроме основных существует ещё несколько состояний – Инициализация (Init), Завершение (Terminate), Состояние простоя (Standby), Переходное состояние (Transition), Состояние отложенной готовности (Deferred ready). Подробнее о них можно узнать в [5; 2].
На рис.9.1 показаны основные состояния потока, возможные переходы между состояниями и условия переходов.
(рис 9.1) Состояния потока
В Windows имеется два базовых размера кванта – 2 интервала системного таймера и 12 интервалов. Если квант времени короткий, то потоки будут переключаться быстрее и "отзывчивость" (responsiveness) системы улучшится – это важное свойство для пользователя, поэтому в клиентских системах Windows по умолчанию используются короткие кванты. При этом производительность системы в целом снижается, поскольку потоки не будут успевать выполнять свои задачи в течение выделенного кванта, а частые переключения создадут высокие накладные расходы (служебные операции системы при смене потоков). Вследствие этого в серверных версиях Windows по умолчанию применяются длинные кванты.
Длительность интервала системного таймера (в сотнях наносекунд) хранится в переменной KeMaximumIncrement (для x86 – файл base\ntos\ex\i386\splocks.asm, строка 140; для x64 – файл base\ntos\ex\amd64\hifreqlk.asm, строка 147) и устанавливается функцией KeSetTimeIncrement (файл base\ntos\ke\miscc.c, строка 711 на основе значения, предоставляемого HAL.
Каждый процесс хранит величину кванта в поле QuantumReset структуры KPROCESS (файл base\ntos\inc\ke.h, строка 1029). Значение в этом поле равно количеству интервалов таймера, умноженному на 3. Например, для длинных квантов (12 интервалов) значение QuantumReset будет равно 36. Таким образом, при каждом срабатывании таймера (возникает прерывание) система уменьшает квант выполняющегося потока на 3 единицы.
Умножение на три введено для того чтобы можно было в разной степени уменьшать квант в двух различных ситуациях – срабатывании таймера (квант уменьшается на 3 единицы) и выходе из состояния ожидания (квант уменьшается на единицу). Уменьшение кванта при выходе потока из состояния ожидания применяется чтобы избежать ситуации бесконечно выполняющегося потока: если при каждом срабатывании таймера поток находится в состоянии ожидания, а при выходе из ожидания значение кванта не изменяется, то теоретически поток может выполняться бесконечно. Поэтому при выходе из состояния ожидания текущее значение его кванта уменьшается на единицу.
Значение кванта может быть изменено пользователем. Например, на Windows 7 нужно проделать следующее: Компьютер – Свойства – Дополнительные параметры системы – вкладка "Дополнительно" – раздел "Быстродействие" – Параметры – вкладка "Дополнительно" – раздел "Распределение времени процессора". Можно выбрать короткие кванты ("Оптимизировать работу программ") или длинные ("Оптимизировать работу служб, работающих в фоновом режиме") (рис.9.2).
(рис 9.2) Изменение величины кванта в Windows 7number
За изменение величины кванта отвечает функция KeSetQuantumProcess (файл base\ntos\ke\procobj.c, строка 1393).
Кроме длинных и коротких квантов в Windows реализовано динамическое увеличение размера кванта для потоков активного процесса (т.е. того процесса, окно которого в настоящий момент активно). За повышение кванта (и приоритета) отвечает функция PspComputeQuantumAndPriority (файл base\ntos\ps\psquery.c, строка 4415). Более подробную информацию о динамическом увеличении кванта см. [5, стр. 361].
В операционной системе Windows имеется 32 уровня приоритета – от 0 до 31 (рис.9.3).
(рис 9.3) Приоритеты в Windows
Приоритеты назначаются процессам и потокам. У процесса имеется единственный приоритет, который называется базовым. Значение этого приоритета хранится в поле BasePriority структуры KPROCESS (файл base\ntos\inc\ke.h, строка 1028). В WinAPI для работы с базовым приоритетом процесса используются классы приоритета (например, REALTIME, NORMAL и т. д.); соответствие классов приоритета числовым значениям показано на рис.9.3. Например, при создании процесса можно указать класс приоритета в качестве параметра WinAPI-функции CreateProcess, иначе будет установлен приоритет по умолчанию (см. лекцию 6 "Процессы и потоки", раздел "Создание процесса"). В дальнейшем класс приоритета процесса можно изменить при помощи WinAPI-функции SetPriorityClass.
В WRK структура PROCESS_PRIORITY_CLASS и значения соответствующих констант (заметьте, что эти значения не совпадают с числовыми значениями приоритетов) определены в файле public\sdk\inc\ntpsapi.h (строка 399). Класс приоритета процесса хранится в поле PriorityClass структуры EPROCESS (см. лекцию 7 "Процессы и потоки", раздел "Структуры данных для процессов и потоков"). Таким образом, если, например, процессу назначен класс приоритета High, то в поле PriorityClass запишется число 3 (значение константы PROCESS_PRIORITY_CLASS_HIGH), в поле BasePriority – значение 13 (соответствующее числовое значение приоритета).
Поток имеет два значения приоритета – базовый и текущий. При создании потока базовый приоритет потока принимается равным базовому приоритету процесса-владельца. Можно изменить базовый приоритет потока при помощи WinAPI-функции SetThreadPriority. Параметрами этой функции являются дескриптор потока и относительный приоритет, который определяет смещение базового приоритета (таблица 7.1).
| Относительный приоритет | Смещение для динамических приоритетов | Смещение для приоритетов реального времени |
|---|---|---|
| Time Critical | Базовый приоритет = 15 | Базовый приоритет = 31 |
| Highest | +2 | +2 |
| Above Normal | +1 | +1 |
| Normal | 0 | 0 |
| Below Normal | –1 | –1 |
| Lowest | –2 | –2 |
| Idle | Базовый приоритет = 1 | Базовый приоритет = 16 |
Пример. Имеется процесс с базовым приоритетом Below Normal (6). Поток, принадлежащий этому процессу, имеет такой же базовый приоритет. Вызов функции SetThreadPriority с параметром Highest сделает базовый приоритет потока равным 8, а с параметром Time Critical – равным 15.
Текущий приоритет потока при создании потока равен базовому, но в дальнейшем может динамически повышаться и понижаться операционной системой (эта процедура будет рассмотрена далее). Заметим, что для потоков с базовым приоритетом Real Time текущий приоритет не изменяется и всегда равен базовому.
Базовый приоритет потока хранится в поле BasePriority, а текущий – в поле Priority структуры KTHREAD (файл base\ntos\inc\ke.h, строки 1123 и 1237).
В Windows отсутствует единый модуль, отвечающий за планирование потоков. Алгоритм планирования реализуется несколькими процедурами ядра, совокупность которых называется диспетчером ядра (kernel’s dispatcher).
Для хранения данных, необходимых для планирования, предназначена база данных диспетчера ядра, которая является частью структуры KPRCB (Kernel Processor Control Block), описанной в файле base\ntos\inc\i386.h (строка 1073). Эта структура создается для каждого процессора, присутствующего в системе. Структура KPRCB содержит следующие поля, требуемые для планирования:
CurrentThread – указатель на текущий выполняющийся поток;NextThread – указатель на следующий поток для выполнения;IdleThread – указатель на поток простоя;DispatcherReadyListHead – массив списков, содержащих указатели на потоки, готовые к выполнению. Количество элементов массива совпадает с количеством уровней приоритета в системе (32), т. е. для каждого приоритета поддерживается своя очередь потоков в состоянии готовности;ReadySummary – 32 битное число, каждый из разрядов которого отвечает за один уровень приоритета. Единица в N-ом разряде означает, что очередь готовых к выполнению потоков с приоритетом N не пустая. Это поле используется для ускорения поиска при выборе потока для выполнения.Выбор потока с максимальным приоритетом из массива DispatcherReadyListHead с использованием поля ReadySummary осуществляется функцией KiSelectReadyThread (файл base\ntos\ke\ki.h, строка 3550).
Рассмотрим основные ситуации, возникающие при планировании потоков.
1. Выбор потока на выполнение.
Просматривается очередь готовых к выполнению потоков (сначала поле ReadySummary, затем, когда определена непустая очередь с максимальным приоритетом, поле DispatcherReadyListHead) и выбирается первый поток в очереди с наибольшим приоритетом, которому для выполнения предоставляется квант времени (рис.9.4).
(рис 9.4) Выбор потока для выполнения (квадратами обозначены потоки, числами – их приоритеты)
2. Переход выполняющегося потока в состояние ожидания.
Выполняющийся поток вызывает одну из функций ожидания (см. MSDN – Wait Functions [10]) и освобождает процессор. Его квант времени не истек и сохраняется за потоком, но при выходе из состояния ожидания уменьшается на единицу (см. параграф "Кванты" этой лекции).
Диспетчер ядра выбирает на выполнение первый поток из очереди с наибольшим приоритетом (рис.9.5).
(рис 9.5) Переход потока в состояние ожидания
3. Вытеснение потоком с большим приоритетом.
Во время выполнения поток может быть вытеснен при появлении потока с большим приоритетом. Такая ситуация может возникнуть по следующим причинам:
В любом случае выполняющийся поток вытесняется, помещается в начало очереди готовности с соответствующим приоритетом; при этом неистраченная часть кванта остается за потоком.
(рис 9.6) Вытеснение потока
4. Завершение кванта времени
Когда квант времени, предоставленный потоку, истекает, операционная система проверяет, есть ли в очереди готовности поток с таким же приоритетом или выше. Если есть, то поток помещается в конец соответствующей очереди готовности и новый поток выбирается на выполнение (рис.9.7). Если такие потоки отсутствуют, выполняющемуся потоку может быть предоставлен новый квант времени.
(рис 9.7) Завершение кванта
Если бы операционная система осуществляла планирование потоков только на основе выше рассмотренных ситуаций, большинство потоков с низким приоритетом вообще никогда не выполнялись бы – диспетчер ядра все время выбирал бы потоки с наивысшим приоритетом.
Чтобы дать всем потокам шанс на выполнение операционная система применяет механизм динамического повышения приоритета (Priority Boosts), который работает в следующих случаях:
Замечание. Никогда не повышаются приоритеты потоков реального времени (16–31).
В этой лекции рассмотрены основные алгоритмы планирования потоков, в том числе, вытесняющие и невытесняющие, с квантованием и с приоритетами. Описаны состояния, в которых могут находиться потоки. Приведены особенности реализации квантования и приоритетов в Windows. Рассмотрен алгоритм планирования потоков, используемый в Windows.
В следующей лекции рассказывается, каким образом в Windows реализуется управление виртуальной и физической памятью.
Если операционная система поддерживает многопоточность, она может распределять процессорное время либо между процессами, либо между потоками. В операционной системе Windows процессор предоставляется потокам, иначе говоря, осуществляется планирование на уровне потоков.
Таким образом, если один процесс имеет пять потоков, а второй – десять, то первый процесс будет занимать процессор в два раза больше времени, чем второй (при условии, конечно, что все потоки имеют равный приоритет и выполняют примерно одинаковую работу).
Существуют разные алгоритмы планирования. Рассмотрим основные виды.
1. Вытесняющие/невытесняющие алгоритмы.
В случае вытесняющего алгоритма операционная система в любой момент времени может прервать выполнение текущего потока и переключить процессор на другой поток. В невытесняющих алгоритмах поток, которому предоставлен процессор, только сам решает, когда передать управление операционной системе.
2. Алгоритмы с квантованием.
Каждому потоку предоставляется квант времени, в течение которого поток может выполняться на процессоре. По истечении кванта операционная система переключает процессор на следующий поток в очереди. Квант обычно равен целому числу интервалов
3. Алгоритмы с приоритетами.
Каждому потоку назначается приоритет (priority) – целое число, обозначающее степень привилегированности потока. Операционная система при наличии нескольких готовых к выполнению потоков выбирает из них поток с наибольшим приоритетом.
В Windows реализован смешанный алгоритм планирования – вытесняющий, на основе квантования и приоритетов.
За время своего существования поток может находиться в нескольких состояниях. Перечислим основные состояния:
Кроме основных существует ещё несколько состояний – Инициализация (Init), Завершение (Terminate), Состояние простоя (Standby), Переходное состояние (Transition), Состояние отложенной готовности (Deferred ready). Подробнее о них можно узнать в [5; 2].
На рис.9.1 показаны основные состояния потока, возможные переходы между состояниями и условия переходов.
(рис 9.1) Состояния потока
В Windows имеется два базовых размера кванта – 2 интервала системного таймера и 12 интервалов. Если квант времени короткий, то потоки будут переключаться быстрее и "отзывчивость" (responsiveness) системы улучшится – это важное свойство для пользователя, поэтому в клиентских системах Windows по умолчанию используются короткие кванты. При этом производительность системы в целом снижается, поскольку потоки не будут успевать выполнять свои задачи в течение выделенного кванта, а частые переключения создадут высокие накладные расходы (служебные операции системы при смене потоков). Вследствие этого в серверных версиях Windows по умолчанию применяются длинные кванты.
Длительность интервала системного таймера (в сотнях наносекунд) хранится в переменной KeMaximumIncrement (для x86 – файл base\ntos\ex\i386\splocks.asm, строка 140; для x64 – файл base\ntos\ex\amd64\hifreqlk.asm, строка 147) и устанавливается функцией KeSetTimeIncrement (файл base\ntos\ke\miscc.c, строка 711 на основе значения, предоставляемого HAL.
Каждый процесс хранит величину кванта в поле QuantumReset структуры KPROCESS (файл base\ntos\inc\ke.h, строка 1029). Значение в этом поле равно количеству интервалов таймера, умноженному на 3. Например, для длинных квантов (12 интервалов) значение QuantumReset будет равно 36. Таким образом, при каждом срабатывании таймера (возникает прерывание) система уменьшает квант выполняющегося потока на 3 единицы.
Умножение на три введено для того чтобы можно было в разной степени уменьшать квант в двух различных ситуациях – срабатывании таймера (квант уменьшается на 3 единицы) и выходе из состояния ожидания (квант уменьшается на единицу). Уменьшение кванта при выходе потока из состояния ожидания применяется чтобы избежать ситуации бесконечно выполняющегося потока: если при каждом срабатывании таймера поток находится в состоянии ожидания, а при выходе из ожидания значение кванта не изменяется, то теоретически поток может выполняться бесконечно. Поэтому при выходе из состояния ожидания текущее значение его кванта уменьшается на единицу.
Значение кванта может быть изменено пользователем. Например, на Windows 7 нужно проделать следующее: Компьютер – Свойства – Дополнительные параметры системы – вкладка "Дополнительно" – раздел "Быстродействие" – Параметры – вкладка "Дополнительно" – раздел "Распределение времени процессора". Можно выбрать короткие кванты ("Оптимизировать работу программ") или длинные ("Оптимизировать работу служб, работающих в фоновом режиме") (рис.9.2).
(рис 9.2) Изменение величины кванта в Windows 7number
За изменение величины кванта отвечает функция KeSetQuantumProcess (файл base\ntos\ke\procobj.c, строка 1393).
Кроме длинных и коротких квантов в Windows реализовано динамическое увеличение размера кванта для потоков активного процесса (т.е. того процесса, окно которого в настоящий момент активно). За повышение кванта (и приоритета) отвечает функция PspComputeQuantumAndPriority (файл base\ntos\ps\psquery.c, строка 4415). Более подробную информацию о динамическом увеличении кванта см. [5, стр. 361].
В операционной системе Windows имеется 32 уровня приоритета – от 0 до 31 (рис.9.3).
(рис 9.3) Приоритеты в Windows
Приоритеты назначаются процессам и потокам. У процесса имеется единственный приоритет, который называется базовым. Значение этого приоритета хранится в поле BasePriority структуры KPROCESS (файл base\ntos\inc\ke.h, строка 1028). В WinAPI для работы с базовым приоритетом процесса используются классы приоритета (например, REALTIME, NORMAL и т. д.); соответствие классов приоритета числовым значениям показано на рис.9.3. Например, при создании процесса можно указать класс приоритета в качестве параметра WinAPI-функции CreateProcess, иначе будет установлен приоритет по умолчанию (см. лекцию 6 "Процессы и потоки", раздел "Создание процесса"). В дальнейшем класс приоритета процесса можно изменить при помощи WinAPI-функции SetPriorityClass.
В WRK структура PROCESS_PRIORITY_CLASS и значения соответствующих констант (заметьте, что эти значения не совпадают с числовыми значениями приоритетов) определены в файле public\sdk\inc\ntpsapi.h (строка 399). Класс приоритета процесса хранится в поле PriorityClass структуры EPROCESS (см. лекцию 7 "Процессы и потоки", раздел "Структуры данных для процессов и потоков"). Таким образом, если, например, процессу назначен класс приоритета High, то в поле PriorityClass запишется число 3 (значение константы PROCESS_PRIORITY_CLASS_HIGH), в поле BasePriority – значение 13 (соответствующее числовое значение приоритета).
Поток имеет два значения приоритета – базовый и текущий. При создании потока базовый приоритет потока принимается равным базовому приоритету процесса-владельца. Можно изменить базовый приоритет потока при помощи WinAPI-функции SetThreadPriority. Параметрами этой функции являются дескриптор потока и относительный приоритет, который определяет смещение базового приоритета (таблица 7.1).
| Относительный приоритет | Смещение для динамических приоритетов | Смещение для приоритетов реального времени |
|---|---|---|
| Time Critical | Базовый приоритет = 15 | Базовый приоритет = 31 |
| Highest | +2 | +2 |
| Above Normal | +1 | +1 |
| Normal | 0 | 0 |
| Below Normal | –1 | –1 |
| Lowest | –2 | –2 |
| Idle | Базовый приоритет = 1 | Базовый приоритет = 16 |
Пример. Имеется процесс с базовым приоритетом Below Normal (6). Поток, принадлежащий этому процессу, имеет такой же базовый приоритет. Вызов функции SetThreadPriority с параметром Highest сделает базовый приоритет потока равным 8, а с параметром Time Critical – равным 15.
Текущий приоритет потока при создании потока равен базовому, но в дальнейшем может динамически повышаться и понижаться операционной системой (эта процедура будет рассмотрена далее). Заметим, что для потоков с базовым приоритетом Real Time текущий приоритет не изменяется и всегда равен базовому.
Базовый приоритет потока хранится в поле BasePriority, а текущий – в поле Priority структуры KTHREAD (файл base\ntos\inc\ke.h, строки 1123 и 1237).
В Windows отсутствует единый модуль, отвечающий за планирование потоков. Алгоритм планирования реализуется несколькими процедурами ядра, совокупность которых называется диспетчером ядра (kernel’s dispatcher).
Для хранения данных, необходимых для планирования, предназначена база данных диспетчера ядра, которая является частью структуры KPRCB (Kernel Processor Control Block), описанной в файле base\ntos\inc\i386.h (строка 1073). Эта структура создается для каждого процессора, присутствующего в системе. Структура KPRCB содержит следующие поля, требуемые для планирования:
CurrentThread – указатель на текущий выполняющийся поток;NextThread – указатель на следующий поток для выполнения;IdleThread – указатель на поток простоя;DispatcherReadyListHead – массив списков, содержащих указатели на потоки, готовые к выполнению. Количество элементов массива совпадает с количеством уровней приоритета в системе (32), т. е. для каждого приоритета поддерживается своя очередь потоков в состоянии готовности;ReadySummary – 32 битное число, каждый из разрядов которого отвечает за один уровень приоритета. Единица в N-ом разряде означает, что очередь готовых к выполнению потоков с приоритетом N не пустая. Это поле используется для ускорения поиска при выборе потока для выполнения.Выбор потока с максимальным приоритетом из массива DispatcherReadyListHead с использованием поля ReadySummary осуществляется функцией KiSelectReadyThread (файл base\ntos\ke\ki.h, строка 3550).
Рассмотрим основные ситуации, возникающие при планировании потоков.
1. Выбор потока на выполнение.
Просматривается очередь готовых к выполнению потоков (сначала поле ReadySummary, затем, когда определена непустая очередь с максимальным приоритетом, поле DispatcherReadyListHead) и выбирается первый поток в очереди с наибольшим приоритетом, которому для выполнения предоставляется квант времени (рис.9.4).
(рис 9.4) Выбор потока для выполнения (квадратами обозначены потоки, числами – их приоритеты)
2. Переход выполняющегося потока в состояние ожидания.
Выполняющийся поток вызывает одну из функций ожидания (см. MSDN – Wait Functions [10]) и освобождает процессор. Его квант времени не истек и сохраняется за потоком, но при выходе из состояния ожидания уменьшается на единицу (см. параграф "Кванты" этой лекции).
Диспетчер ядра выбирает на выполнение первый поток из очереди с наибольшим приоритетом (рис.9.5).
(рис 9.5) Переход потока в состояние ожидания
3. Вытеснение потоком с большим приоритетом.
Во время выполнения поток может быть вытеснен при появлении потока с большим приоритетом. Такая ситуация может возникнуть по следующим причинам:
В любом случае выполняющийся поток вытесняется, помещается в начало очереди готовности с соответствующим приоритетом; при этом неистраченная часть кванта остается за потоком.
(рис 9.6) Вытеснение потока
4. Завершение кванта времени
Когда квант времени, предоставленный потоку, истекает, операционная система проверяет, есть ли в очереди готовности поток с таким же приоритетом или выше. Если есть, то поток помещается в конец соответствующей очереди готовности и новый поток выбирается на выполнение (рис.9.7). Если такие потоки отсутствуют, выполняющемуся потоку может быть предоставлен новый квант времени.
(рис 9.7) Завершение кванта
Если бы операционная система осуществляла планирование потоков только на основе выше рассмотренных ситуаций, большинство потоков с низким приоритетом вообще никогда не выполнялись бы – диспетчер ядра все время выбирал бы потоки с наивысшим приоритетом.
Чтобы дать всем потокам шанс на выполнение операционная система применяет механизм динамического повышения приоритета (Priority Boosts), который работает в следующих случаях:
Замечание. Никогда не повышаются приоритеты потоков реального времени (16–31).
В этой лекции рассмотрены основные алгоритмы планирования потоков, в том числе, вытесняющие и невытесняющие, с квантованием и с приоритетами. Описаны состояния, в которых могут находиться потоки. Приведены особенности реализации квантования и приоритетов в Windows. Рассмотрен алгоритм планирования потоков, используемый в Windows.
В следующей лекции рассказывается, каким образом в Windows реализуется управление виртуальной и физической памятью.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.