Квант времени процессора это
Аннотация: Алгоритмы планирования. Состояния потоков. Кванты. Приоритеты. Алгоритм планирования в Windows. Динамическое повышение приоритета.
Если операционная система поддерживает многопоточность, она может распределять процессорное время либо между процессами, либо между потоками. В операционной системе Windows процессор предоставляется потокам, иначе говоря, осуществляется планирование на уровне потоков.
Таким образом, если один процесс имеет пять потоков, а второй – десять, то первый процесс будет занимать процессор в два раза больше времени, чем второй (при условии, конечно, что все потоки имеют равный приоритет и выполняют примерно одинаковую работу).
Алгоритмы планирования
Существуют разные алгоритмы планирования. Рассмотрим основные виды.
1. Вытесняющие/невытесняющие алгоритмы.
В случае вытесняющего алгоритма операционная система в любой момент времени может прервать выполнение текущего потока и переключить процессор на другой поток. В невытесняющих алгоритмах поток, которому предоставлен процессор, только сам решает, когда передать управление операционной системе.
2. Алгоритмы с квантованием.
Каждому потоку предоставляется квант времени, в течение которого поток может выполняться на процессоре. По истечении кванта операционная система переключает процессор на следующий поток в очереди. Квант обычно равен целому числу интервалов системного таймера 1 Системный таймер – электронное устройство на материнской плате или в процессоре, которое вырабатывает сигнал прерывания через строго определенные промежутки времени (интервал системного таймера). .
3. Алгоритмы с приоритетами.
Каждому потоку назначается приоритет (priority) – целое число, обозначающее степень привилегированности потока. Операционная система при наличии нескольких готовых к выполнению потоков выбирает из них поток с наибольшим приоритетом.
В Windows реализован смешанный алгоритм планирования – вытесняющий, на основе квантования и приоритетов.
Состояния потоков
За время своего существования поток может находиться в нескольких состояниях. Перечислим основные состояния:
Кроме основных существует ещё несколько состояний – Инициализация (Init), Завершение (Terminate), Состояние простоя (Standby), Переходное состояние (Transition), Состояние отложенной готовности (Deferred ready). Подробнее о них можно узнать в [5; 2].
На рис.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).
За изменение величины кванта отвечает функция KeSetQuantumProcess (файл base\ntos\ke\procobj.c, строка 1393).
Кроме длинных и коротких квантов в Windows реализовано динамическое увеличение размера кванта для потоков активного процесса (т.е. того процесса, окно которого в настоящий момент активно). За повышение кванта (и приоритета) отвечает функция PspComputeQuantumAndPriority (файл base\ntos\ps\psquery.c, строка 4415). Более подробную информацию о динамическом увеличении кванта см. [5, стр. 361].
Приоритеты
В операционной системе Windows имеется 32 уровня приоритета – от 0 до 31 (рис.9.3).
Приоритеты назначаются процессам и потокам. У процесса имеется единственный приоритет, который называется базовым. Значение этого приоритета хранится в поле 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).
Пример. Имеется процесс с базовым приоритетом Below Normal (6). Поток, принадлежащий этому процессу, имеет такой же базовый приоритет. Вызов функции SetThreadPriority с параметром Highest сделает базовый приоритет потока равным 8, а с параметром Time Critical – равным 15.
Текущий приоритет потока при создании потока равен базовому, но в дальнейшем может динамически повышаться и понижаться операционной системой (эта процедура будет рассмотрена далее). Заметим, что для потоков с базовым приоритетом Real Time текущий приоритет не изменяется и всегда равен базовому.
Базовый приоритет потока хранится в поле BasePriority , а текущий – в поле Priority структуры KTHREAD (файл base\ntos\inc\ke.h, строки 1123 и 1237).
Квант времени (timeslice[20]) — это численное значение, которое характеризует, как долго может выполняться задание до того момента, пока оно не будет вытеснено. Стратегия планирования должна устанавливать значение кванта времени, используемое по умолчанию, что является непростой задачей. Слишком большое значение кванта времени приведет к ухудшению интерактивной производительности системы— больше не будет впечатления, что процессы выполняются параллельно. Слишком малое значение кванта времени приведет к возрастанию накладных расходов на переключение между процессами, так как больший процент системного времени будет уходить на переключение с одного процесса с малым квантом времени на другой процесс с малым квантом времени. Более того, снова возникают противоречивые требования к процессам, ограниченным скоростью ввода-вывода и скоростью процессора. Процессам, ограниченным скоростью ввода-вывода, не требуется продолжительный квант времени, в то время как для процессов, ограниченных скоростью процессора, настоятельно требуется продолжительный квант времени, например, чтобы поддерживать кэши процессора в загруженном состоянии.
На основе этих аргументов можно сделать вывод, что любое большое значение кванта времени приведет к ухудшению интерактивной производительности. При реализации большинства операционных систем такой вывод принимается близко к сердцу и значение кванта времени, используемое по умолчанию, достаточно мало, например равно 20 мс. Однако в операционной системе Linux используется то преимущество, что процесс с самым высоким приоритетом всегда выполняется. Планировщик ядра Linux поднимает значение приоритета для интерактивных задач, что позволяет им выполняться более часто. Поэтому в ОС Linux планировщик использует достаточно большое значение кванта времени (рис 4.1). Более того, планировщик ядра Linux динамически определяет значение кванта времени процессов в зависимости от их приоритетов. Это позволяет процессам с более высоким приоритетом, которые считаются более важными, выполняться более часто и в течение большего периода времени. Использование динамического определения величины кванта времени и приоритетов позволяет обеспечить большую устойчивость и производительность планировщика.
Рис. 4.1. Вычисление кванта времени процесса
Следует заметить, что процесс не обязательно должен использовать весь свой квант времени за один раз. Например, процесс, у которого квант времени равен 100 мс, не обязательно должен беспрерывно выполняться в течение 100 мс, рискуя потерять всю оставшуюся неистраченную часть кванта времени. Процесс может выполняться в течение пяти периодов длительностью по 20 мс каждый.
Таким образом, интерактивные задачи также получают преимущество от использования продолжительного кванта времени, если даже вся продолжительность кванта времени не будет использована сразу, гарантируется, что такие процессы будут готовы к выполнению по возможности долго.
Когда истекает квант времени процесса, считается, что процесс потерял право выполняться. Процесс, у которого нет кванта времени, не имеет права выполняться до того момента, пока все другие процессы не используют свой квант времени. Когда это случится, то у всех процессов будет значение оставшегося кванта времени, равное нулю. В этот момент значения квантов времени для всех процессов пересчитываются. В планировщике ОС Linux используется интересный алгоритм для обработки ситуации, когда все процессы использовали свой квант времени. Этот алгоритм будет рассмотрен далее.
18.1.1. Представление времени
18.1.1. Представление времени В системах Unix и Linux время отслеживается в секундах до или после начала эпохи, которое определяется как полночь 1 января 1970 года по UTC[148]. Положительные значения времени относятся к периоду после начала эпохи; отрицательные — до начала эпохи. Для
12.1. Ограничения по времени
12.1. Ограничения по времени После выбора этой ссылки появится сетка ограничений по времени на каждый день недели. Настройка ограничений производится очень просто: необходимо щелкнуть кнопкой мыши на пересечении дня недели и нужного времени суток, что приведет к
Линейка времени
Линейка времени На линейке времени окна редактора в часах, минутах, секундах и миллисекундах отображается время (рис. 4.11). Когда мы прослушиваем запись, то всегда можем определить, сколько времени прошло с начала воспроизведения. Для этого достаточно посмотреть на
Настройка времени
Настройка времени С помощью этой кнопки можно настроить время, которое на экране будет показываться каждый слайд. То есть такая вот репетиция презентации.При нажатии кнопки Настройка времени начнется полноэкранный показ презентации. В левом верхнем углу вы увидите вот
1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени
1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени "В ранние мини-компьютерные времена Unix" вынесенная в заголовок идея была довольно радикальной (машины тогда работали
1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени
1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени "В ранние мини-компьютерные времена Unix" вынесенная в заголовок идея была довольно радикальной (машины тогда работали
7.10. Контроль даты и времени
7.10. Контроль даты и времени В разделе 7.5 было показано, что стандартные функции не проверяют корректность даты, а «переносят» ее вперед, если необходимо. Например, 31 ноября становится 1 декабря.Иногда такое поведение даже желательно. А если нет, то спешу обрадовать:
7.15 Сравнение моментов времени
Интервал времени
Интервал времени Ошибочно предполагать, что тип TIME может хранить интервал времени. Он не может. Для вычисления интервала времени вычтите более позднюю дату или время из более раннего. Результатом будет число NUMERIC(18,9), выражающее интервал в днях. Поскольку точность
Машина времени
Машина времени Автор: Олег ВолошинЛюбой производитель спит и видит, как бы вырваться вперед, создать что-то такое, что отличит его детище от сонма других. В случае с цифровыми камерами, выпускаемыми в колоссальном избытке, это становится особенно актуально —
Немного времени
Немного времени Игра «О счастливчик»Игрок: Прошу убрать два неверных варианта.Ведущий: Итак, дорогой компьютер, уберите, пожалуйста, два неверных варианта.Надпись на мониторах: «Программа выполнила недопустимую ошибку и будет закрыта».Ведущий: Что ж, по просьбе компании
Знаки времени
Знаки времени Автор: Киви БердНа закате правления госадминистрации Клинтона один из видных деятелей ИТ-индустрии, глава Sun Microsystems Скотт Макнили сделал, помнится, весьма сильное публичное заявление, которым многие были просто шокированы. Речь шла о роли технологий в
Квант времени (timeslice[20]) — это численное значение, которое характеризует, как долго может выполняться задание до того момента, пока оно не будет вытеснено. Стратегия планирования должна устанавливать значение кванта времени, используемое по умолчанию, что является непростой задачей. Слишком большое значение кванта времени приведет к ухудшению интерактивной производительности системы— больше не будет впечатления, что процессы выполняются параллельно. Слишком малое значение кванта времени приведет к возрастанию накладных расходов на переключение между процессами, так как больший процент системного времени будет уходить на переключение с одного процесса с малым квантом времени на другой процесс с малым квантом времени. Более того, снова возникают противоречивые требования к процессам, ограниченным скоростью ввода-вывода и скоростью процессора. Процессам, ограниченным скоростью ввода-вывода, не требуется продолжительный квант времени, в то время как для процессов, ограниченных скоростью процессора, настоятельно требуется продолжительный квант времени, например, чтобы поддерживать кэши процессора в загруженном состоянии.
На основе этих аргументов можно сделать вывод, что любое большое значение кванта времени приведет к ухудшению интерактивной производительности. При реализации большинства операционных систем такой вывод принимается близко к сердцу и значение кванта времени, используемое по умолчанию, достаточно мало, например равно 20 мс. Однако в операционной системе Linux используется то преимущество, что процесс с самым высоким приоритетом всегда выполняется. Планировщик ядра Linux поднимает значение приоритета для интерактивных задач, что позволяет им выполняться более часто. Поэтому в ОС Linux планировщик использует достаточно большое значение кванта времени (рис 4.1). Более того, планировщик ядра Linux динамически определяет значение кванта времени процессов в зависимости от их приоритетов. Это позволяет процессам с более высоким приоритетом, которые считаются более важными, выполняться более часто и в течение большего периода времени. Использование динамического определения величины кванта времени и приоритетов позволяет обеспечить большую устойчивость и производительность планировщика.
Рис. 4.1. Вычисление кванта времени процесса
Следует заметить, что процесс не обязательно должен использовать весь свой квант времени за один раз. Например, процесс, у которого квант времени равен 100 мс, не обязательно должен беспрерывно выполняться в течение 100 мс, рискуя потерять всю оставшуюся неистраченную часть кванта времени. Процесс может выполняться в течение пяти периодов длительностью по 20 мс каждый.
Таким образом, интерактивные задачи также получают преимущество от использования продолжительного кванта времени, если даже вся продолжительность кванта времени не будет использована сразу, гарантируется, что такие процессы будут готовы к выполнению по возможности долго.
Когда истекает квант времени процесса, считается, что процесс потерял право выполняться. Процесс, у которого нет кванта времени, не имеет права выполняться до того момента, пока все другие процессы не используют свой квант времени. Когда это случится, то у всех процессов будет значение оставшегося кванта времени, равное нулю. В этот момент значения квантов времени для всех процессов пересчитываются. В планировщике ОС Linux используется интересный алгоритм для обработки ситуации, когда все процессы использовали свой квант времени. Этот алгоритм будет рассмотрен далее.
18.1.1. Представление времени
18.1.1. Представление времени В системах Unix и Linux время отслеживается в секундах до или после начала эпохи, которое определяется как полночь 1 января 1970 года по UTC[148]. Положительные значения времени относятся к периоду после начала эпохи; отрицательные — до начала эпохи. Для
12.1. Ограничения по времени
12.1. Ограничения по времени После выбора этой ссылки появится сетка ограничений по времени на каждый день недели. Настройка ограничений производится очень просто: необходимо щелкнуть кнопкой мыши на пересечении дня недели и нужного времени суток, что приведет к
Линейка времени
Линейка времени На линейке времени окна редактора в часах, минутах, секундах и миллисекундах отображается время (рис. 4.11). Когда мы прослушиваем запись, то всегда можем определить, сколько времени прошло с начала воспроизведения. Для этого достаточно посмотреть на
Настройка времени
Настройка времени С помощью этой кнопки можно настроить время, которое на экране будет показываться каждый слайд. То есть такая вот репетиция презентации.При нажатии кнопки Настройка времени начнется полноэкранный показ презентации. В левом верхнем углу вы увидите вот
1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени
1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени "В ранние мини-компьютерные времена Unix" вынесенная в заголовок идея была довольно радикальной (машины тогда работали
1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени
1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени "В ранние мини-компьютерные времена Unix" вынесенная в заголовок идея была довольно радикальной (машины тогда работали
7.10. Контроль даты и времени
7.10. Контроль даты и времени В разделе 7.5 было показано, что стандартные функции не проверяют корректность даты, а «переносят» ее вперед, если необходимо. Например, 31 ноября становится 1 декабря.Иногда такое поведение даже желательно. А если нет, то спешу обрадовать:
7.15 Сравнение моментов времени
Интервал времени
Интервал времени Ошибочно предполагать, что тип TIME может хранить интервал времени. Он не может. Для вычисления интервала времени вычтите более позднюю дату или время из более раннего. Результатом будет число NUMERIC(18,9), выражающее интервал в днях. Поскольку точность
Машина времени
Машина времени Автор: Олег ВолошинЛюбой производитель спит и видит, как бы вырваться вперед, создать что-то такое, что отличит его детище от сонма других. В случае с цифровыми камерами, выпускаемыми в колоссальном избытке, это становится особенно актуально —
Немного времени
Немного времени Игра «О счастливчик»Игрок: Прошу убрать два неверных варианта.Ведущий: Итак, дорогой компьютер, уберите, пожалуйста, два неверных варианта.Надпись на мониторах: «Программа выполнила недопустимую ошибку и будет закрыта».Ведущий: Что ж, по просьбе компании
Знаки времени
Знаки времени Автор: Киви БердНа закате правления госадминистрации Клинтона один из видных деятелей ИТ-индустрии, глава Sun Microsystems Скотт Макнили сделал, помнится, весьма сильное публичное заявление, которым многие были просто шокированы. Речь шла о роли технологий в
В начале этой главы было рассмотрено, как приоритет и квант времени используются для того, чтобы влиять на те решения, которые принимает планировщик. Кроме того, были рассмотрены процессы, ограниченные скоростью ввода-вывода и скоростью процессора, а также было описано, почему желательно поднимать приоритет интерактивных задач. Теперь давайте рассмотрим код, который реализует эти соображения.
Процессы имеют начальное значение приоритета, которое называется nice. Это значение может лежать в диапазоне от -20 до 19, по умолчанию используется значение 0. Значение 19 соответствует наиболее низкому приоритету, а значение -20 — наиболее высокому. Значение параметра nice хранится в поле static_prio структуры task_struct процесса. Это значение называется статическим приоритетом, потому что оно не изменяется планировщиком и остается таким, каким его указал пользователь. Планировщик свои решения основывает на динамическом приоритете, которое хранится в поле prio. Динамический приоритет вычисляется как функция статического приоритета и интерактивности задания.
Функция effective_prio() возвращает значение динамического приоритета задачи. Эта функция исходит из значения параметра nice для данной задачи и вычисляет для этого значения надбавку или штраф в диапазоне от -5 до 5, в зависимости от интерактивности задачи. Например, задание с высокой интерактивностью, которое имеет значение параметра nice, равное 10, может иметь динамический приоритет, равный 5. И наоборот, программа со значением параметра nice, равным 10, которая достаточно активно использует процессор, может иметь динамический приоритет, равный 12. Задачи, которые обладают умеренной интерактивностью, не получают ни надбавки, ни штрафа, и их динамический приоритет совпадает со значением параметра nice.
Конечно, планировщик по волшебству не может определить, какой процесс является интерактивным. Для определения необходима некоторая эвристика, которая отражает, является ли процесс ограниченным скоростью ввода-вывода или скоростью процессора. Наиболее выразительный показатель — сколько времени задача находится в приостановленном состоянии (sleep). Если задача проводит большую часть времени в приостановленном состоянии, то она ограничена вводом-выводом. Если задача больше времени находится в состоянии готовности к выполнению, чем в приостановленном состоянии, то эта задача не интерактивна. В экстремальных случаях, если задача большую часть времени находится в приостановленном состоянии, то она полностью ограничена скоростью ввода-вывода; если задача все время готова к выполнению, то она ограничена скоростью процессора.
Для реализации такой эвристики в ядре Linux предусмотрен изменяемый показатель того, как соотносится время, которое процесс проводит в приостановленном состоянии, со временем, которое процесс проводит в состоянии готовности к выполнению. Значение этого показателя хранится в поле sleep_avg структуры task_struct. Диапазон значений этого показателя лежит от нуля до значения MAXSLEEP_AVG, которое по умолчанию равно 10 мс. Когда задача становится готовой к выполнению после приостановленного состояния, значение поля sleep_avg увеличивается на значение времени, которое процесс провел в приостановленном состоянии, пока значение sleep_avg не достигнет MAXSLEEP_AVG. Когда задача выполняется, то в течение каждого импульса таймера (timer tick) значение этой переменной уменьшается, пока оно не достигнет значения 0.
Такой показатель является, на удивление, надежным. Он рассчитывается не только на основании того, как долго задача находится в приостановленном состоянии, но и на основании того, насколько мало задача выполняется. Таким образом, задача, которая проводит много времени в приостановленном состоянии и в то же время постоянно использует свой квант времени, не получит большой прибавки к приоритету: показатель работает не только для поощрения интерактивных задач, но и для наказания задач, ограниченных скоростью процессора. Этот показатель также устойчив по отношению к злоупотреблениям. Задача, которая получает повышенное значение приоритета и большое значение кванта времени, быстро утратит свою надбавку к приоритету, если она постоянно выполняется и сильно загружает процессор. В конце концов, такой показатель обеспечивает малое время реакции. Только что созданный интерактивный процесс быстро достигнет высокого значения поля sleep_avg. Несмотря на все сказанное, надбавка и штраф применяются к значению параметра nice, так что пользователь также может влиять на работу системного планировщика путем изменения значения параметра nice процесса.
Расчет значения кванта времени, наоборот, более прост, так как значение динамического приоритета уже базируется на значении параметра nice и на интерактивности (эти показатели планировщик учитывает как наиболее важные). Поэтому продолжительность кванта времени может быть просто выражена через значение динамического приоритета. Когда создается новый процесс, порожденный и родительский процессы делят пополам оставшуюся часть кванта времени родительского процесса. Такой подход обеспечивает равнодоступность ресурсов и предотвращает возможность получения бесконечного значения кванта времени путем постоянного создания порожденных процессов. Однако после того, как квант времени задачи иссякает, это значение пересчитывается на основании динамического приоритета задачи. Функция task_timeslice() возвращает новое значение кванта времени для данного задания. Расчет просто сводится к масштабированию значения приоритета в диапазон значений квантов времени. Чем больше значение приоритета задачи, тем большей продолжительности квант времени получит задание в текущем цикле выполнения. Максимальное значение кванта времени равно MAX_TIMESLICE, которое по умолчанию равно 200 мс. Даже задания с самым низким приоритетом получают квант времени продолжительностью MIN_TIMESLICE, что соответствует 10 мс. Задачи с приоритетом, используемым по умолчанию (значение параметра nice, равно 0 и отсутствует надбавка и штраф за интерактивность), получают квант времени продолжительностью 100 мс, как показано в табл. 4.1.
Таблица 4.1. Продолжительности квантов времени планировщика
Тип задания Значение параметра nice Продолжительность кванта времени Вновь созданное То же, что и у родительского процесса Половина от родительского процесса Минимальный приоритет +19 5 мс (MIN_TIMESLICE) Приоритет по умолчанию 0 100 мс (DEF_TIMESLICE) Максимальный приоритет -20 800 мс (MAX_TIMESLICE)
Для интерактивных задач планировщик оказывает дополнительную услугу: если задание достаточно интерактивно, то при исчерпании своего кванта времени оно будет помещено не в истекший массив приоритетов, а обратно в активный массив приоритетов. Следует вспомнить, что пересчет значений квантов времени производится путем перестановки активного и истекшего массивов приоритетов: активный массив становится истекшим, а истекший — активным. Такая процедура обеспечивает пересчет значений квантов времени, который масштабируется по времени как O(1). С другой стороны, это может привести к тому, что интерактивное задание станет готовым к выполнению, но не получит возможности выполняться, так как оно "застряло" в истекшем массиве. Помещение интерактивных заданий снова в активный массив позволяет избежать такой проблемы. Следует заметить, что это задание не будет выполняться сразу же, а будет запланировано на выполнение по кругу вместе с другими заданиями, которые имеют такой же приоритет. Данную логику реализует функция scheduler_tick(), которая вызывается обработчиком прерываний таймера (обсуждается в главе 10, "Таймеры и управление временем"), как показано ниже.
struct task_struct *task = current;
struct runqueue *rq = this_rq();
if (!TASK_INTERACTIVE(task) || EXPIRED_STARVING(rq))
Показанный код уменьшает значение кванта времени процесса и проверяет, не стало ли это значение равным нулю. Если стало, то задание является истекшим и его необходимо поместить в один из массивов. Для этого код вначале проверяет интерактивность задания с помощью макроса TASK_INTERACTIVE(). Этот макрос на основании значения параметра nice рассчитывает, является ли задание "достаточно интерактивным". Чем меньше значение nice (чем выше приоритет), тем менее интерактивным должно быть задание. Задание со значением параметра nice, равным 19, никогда не может быть достаточно интерактивным для помещения обратно в активный массив. Наоборот, задание со значением nice, равным -20, должно очень сильно использовать процессор, чтобы его не поместили в активный массив. Задача со значением nice, используемым по умолчанию, т.е. равным нулю, должна быть достаточно интерактивной, чтобы быть помещенной обратно в активный массив, но это также отрабатывается достаточно четко. Следующий макрос, EXPIRED_STARVING(), проверяет, нет ли в истекшем массиве процессов, особенно нуждающихся в выполнении (starving), когда массивы не переключались в течение достаточно долгого времени. Если массивы давно не переключались, то обратное помещение задачи в активный массив еще больше задержит переключение, что приведет к тому, что задачи в истекшем массиве еще больше будут нуждаться в выполнении. Если это не так, то задача может быть помещена обратно в активный массив. В других случаях задача помещается в истекший массив, что встречается наиболее часто.
Массивы приоритетов
Массивы приоритетов Каждая очередь выполнения содержит два массива приоритетов (priority arrays): активный и истекший. Массивы приоритетов определены в файле kernel/sched.c в виде описания struct prio_array. Массивы приоритетов — это структуры данных, которые обеспечивают O(1)-планирование.
Пересчет квантов времени
Пересчет квантов времени Во многих операционных системах (включая и более старые версии ОС Linux) используется прямой метод для пересчета значения кванта времени каждого задания, когда все эти значения достигают нуля.Обычно это реализуется с помощью цикла по всем задачам
Наследование приоритетов
Наследование приоритетов Одним из интересных моментов в операционных системах реального времени является феномен инверсии приоритетов.Инверсия приоритетов наблюдается, например, в случае, когда поток с низким приоритетом потребляет все процессорное время, в то время
Определение протокола защиты от инверсии приоритетов
Определение протокола защиты от инверсии приоритетов int pthread_mutexattr_setprotocol( pthread_mutexattr_t* attr, int protocol);int pthread_mutexattr_getprotocol( pthread_mutexattr_t* attr, int* protocol);Эти функции устанавливают/считывают протокол, который реализуется мьютексом для защиты от инверсии приоритетов. Переменная protocol
Инверсия приоритетов
Инверсия приоритетов Независимо от причины мы всегда находим способы избежать выполнения работы. Мы убеждаем себя, что у вас есть более срочная задача, и занимаемся ей. Это называется инверсией приоритетов: вы искусственно повышаете приоритет задачи, чтобы отложить
Динамическое планирование приоритетов
Динамическое планирование приоритетов В предыдущих разделах мы рассмотрели более понятную, но упрощенную модель диспетчеризации задач в AS/400. Со времен первой System/38 в структуру задач было внесено множество изменений для удовлетворения требований различных приложений и
1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени
1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени "В ранние мини-компьютерные времена Unix" вынесенная в заголовок идея была довольно радикальной (машины тогда работали
1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени
1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени "В ранние мини-компьютерные времена Unix" вынесенная в заголовок идея была довольно радикальной (машины тогда работали
7.7. Вычисление промежутка времени, прошедшего от точки отсчета
7.7. Вычисление промежутка времени, прошедшего от точки отсчета По разным причинам может понадобиться перейти от внутреннего (традиционного) представления времени к стандартному. В системе время хранится как число секунд, прошедших с точки отсчета.Метод класса Time.at
7.17. Вычисление разности между двумя моментами времени
ТЕМА НОМЕРА: Кванты ради квантов
ТЕМА НОМЕРА: Кванты ради квантов Автор: Леонид Левкович-МаслюкОдин из самых захватывающих сюжетов современной физики — попытки нащупать пути построения квантового компьютера (КК). Погоня за довольно призрачной целью сводит воедино трудносовместимые вещи. С одной
8 Расстановка приоритетов
8 Расстановка приоритетов В этой главе описывается процесс расстановки приоритетов «снизу вверх». Вначале я уточню то, чего поверхностно коснулся в главе 5, - расстановка приоритетов в сегодняшнем списке дел. Затем я собираюсь обсудить приоритеты более крупных проектов.
Расстановка приоритетов в списке дел
Расстановка приоритетов в списке дел Итак, вы сидите за рабочим столом, и перед вами список сегодняшних дел. Десятки пунктов. Как вы определите, с чего начать?Этот раздел посвящен расстановке приоритетов в этом списке. В разных ситуациях приходится использовать разные
Дмитрий Плесконос: Развитие Интернета - один из приоритетов
Аннотация: Алгоритмы планирования. Состояния потоков. Кванты. Приоритеты. Алгоритм планирования в Windows. Динамическое повышение приоритета.
Если операционная система поддерживает многопоточность, она может распределять процессорное время либо между процессами, либо между потоками. В операционной системе Windows процессор предоставляется потокам, иначе говоря, осуществляется планирование на уровне потоков.
Таким образом, если один процесс имеет пять потоков, а второй – десять, то первый процесс будет занимать процессор в два раза больше времени, чем второй (при условии, конечно, что все потоки имеют равный приоритет и выполняют примерно одинаковую работу).
Алгоритмы планирования
Существуют разные алгоритмы планирования. Рассмотрим основные виды.
1. Вытесняющие/невытесняющие алгоритмы.
В случае вытесняющего алгоритма операционная система в любой момент времени может прервать выполнение текущего потока и переключить процессор на другой поток. В невытесняющих алгоритмах поток, которому предоставлен процессор, только сам решает, когда передать управление операционной системе.
2. Алгоритмы с квантованием.
Каждому потоку предоставляется квант времени, в течение которого поток может выполняться на процессоре. По истечении кванта операционная система переключает процессор на следующий поток в очереди. Квант обычно равен целому числу интервалов системного таймера 1 Системный таймер – электронное устройство на материнской плате или в процессоре, которое вырабатывает сигнал прерывания через строго определенные промежутки времени (интервал системного таймера). .
3. Алгоритмы с приоритетами.
Каждому потоку назначается приоритет (priority) – целое число, обозначающее степень привилегированности потока. Операционная система при наличии нескольких готовых к выполнению потоков выбирает из них поток с наибольшим приоритетом.
В Windows реализован смешанный алгоритм планирования – вытесняющий, на основе квантования и приоритетов.
Состояния потоков
За время своего существования поток может находиться в нескольких состояниях. Перечислим основные состояния:
Кроме основных существует ещё несколько состояний – Инициализация (Init), Завершение (Terminate), Состояние простоя (Standby), Переходное состояние (Transition), Состояние отложенной готовности (Deferred ready). Подробнее о них можно узнать в [5; 2].
На рис.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).
За изменение величины кванта отвечает функция KeSetQuantumProcess (файл base\ntos\ke\procobj.c, строка 1393).
Кроме длинных и коротких квантов в Windows реализовано динамическое увеличение размера кванта для потоков активного процесса (т.е. того процесса, окно которого в настоящий момент активно). За повышение кванта (и приоритета) отвечает функция PspComputeQuantumAndPriority (файл base\ntos\ps\psquery.c, строка 4415). Более подробную информацию о динамическом увеличении кванта см. [5, стр. 361].
Приоритеты
В операционной системе Windows имеется 32 уровня приоритета – от 0 до 31 (рис.9.3).
Приоритеты назначаются процессам и потокам. У процесса имеется единственный приоритет, который называется базовым. Значение этого приоритета хранится в поле 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).
Пример. Имеется процесс с базовым приоритетом Below Normal (6). Поток, принадлежащий этому процессу, имеет такой же базовый приоритет. Вызов функции SetThreadPriority с параметром Highest сделает базовый приоритет потока равным 8, а с параметром Time Critical – равным 15.
Текущий приоритет потока при создании потока равен базовому, но в дальнейшем может динамически повышаться и понижаться операционной системой (эта процедура будет рассмотрена далее). Заметим, что для потоков с базовым приоритетом Real Time текущий приоритет не изменяется и всегда равен базовому.
Базовый приоритет потока хранится в поле BasePriority , а текущий – в поле Priority структуры KTHREAD (файл base\ntos\inc\ke.h, строки 1123 и 1237).
Читайте также: