В windows реализован следующий алгоритм планирования потоков

Ниже представлена не простая расшифровка доклада с семинара CLRium, а переработанная версия для книги .NET Platform Architecture. Той её части, что относится к потокам.

Потоки и планирование потоков

Что такое поток? Давайте дадим краткое определение. По своей сути поток это:

• Средство параллельного относительно других потоков исполнения кода;
• Имеющего общий доступ ко всем ресурсам процесса.

Очень часто часто слышишь такое мнение, что потоки в .NET — они какие-то абсолютно свои. И наши .NET потоки являются чем-то более облегчённым чем есть в Windows. Но на самом деле потоки в .NET являются самыми обычными потоками Windows (хоть Windows thread id и скрыто так, что сложно достать). И если Вас удивляет, почему я буду рассказывать не-.NET вещи в хабе .NET, скажу вам так: если нет понимания этого уровня, можно забыть о хорошем понимании того, как и почему именно так работает код. Почему мы должны ставить volatile, использовать Interlocked и SpinWait. Дальше обычного lock дело не уйдёт. И очень даже зря.

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

Задача процессора — просто исполнять код. Поэтому с точки зрения процессора есть только один поток: последовательное исполнение команд. А задача операционной системы каким-либо образом менять поток т.о. чтобы эмулировать несколько потоков.

Поток в физическом понимании

«Но как же так?», — скажите вы, — «во многих магазинах и на различных сайтах я вижу запись «Intel Xeon 8 ядер 16 потоков». Говоря по-правде это — либо скудность в терминологии либо — чисто маркетинговый ход. На самом деле внутри одного большого процессора есть в данном случае 8 ядер и каждое ядро состоит из двух логических процессоров. Такое доступно при наличии в процессоре технологии Hyper-Threading, когда каждое ядро эмулирует поведение двух процессоров (но не потоков). Делается это для повышения производительности, да. Но по большому счёту если нет понимания, на каких потоках идут расчёты, можно получить очень не приятный сценарий, когда код выполняется со скоростью, ниже чем если бы расчёты шли на одном ядре. Именно поэтому раздача ядер идёт +=2 в случае Hyper-Threading. Т.е. пропуская парные ядра.

Технология эта — достаточно спорная: если вы работаете на двух таких псевдо-ядрах (логических процессорах, которые эмулируются технологией Hyper-Threading), которые при этом находятся на одном физическом ядре и работают с одной и той-же памятью, то вы будете постоянно попадать в ситуацию, когда второй логический процессор так же пытается обратиться к данной памяти, создавая блокировку либо попадая в блокировку, т.к. поток, находящийся на первом ядре работает с той же памятью.

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

Так если процессор ничего не знает о потоках, как же достигается параллельное исполнение потоков на каждом из его ядер? Как было сказано, поток — средство операционной системы выполнять на одном процессоре несколько задач одновременно. Достигается параллелизм очень быстрым переключением между потоками в течение очень короткого промежутка времени. Последовательно запуская на выполнение код каждого из потоков и делая это достаточно часто, операционная система достигает цели: делает их исполнение псевдопараллельным, но параллельным с точки зрения восприятия человека. Второе обоснование существования потоков — это утверждение, что программа не так часто срывается в математические расчёты. Чаще всего она взаимодействует с окружающим её миром: различным оборудованием. Это и работа с жёстким диском и вывод на экран и работа с клавиатурой и мышью. Поэтому чтобы процессор не простаивал, пока оборудование сделает то, чего хочет от него программа, поток можно на это время установить в состояние блокировки: ожидания сигнала от операционной системы, что оборудование сделало то, что от него просили. Простейший пример этого — вызов метода Console.ReadKey().

Если заглянуть в диспетчер задач Windows 10, то можно заметить, что в данный момент в вашей системе существует около 1,5 тысячи потоков. И если учесть, что квант на десктопе равен 20 мс, а ядер, например, 4, то можно сделать вывод, что каждый поток получает 20 мс работы 1 раз в 7,5 сек… Ну конечно же, нет. Просто почти все потоки чего-то ждут. То ввода пользователя, то изменения ключей реестра… В операционной системе существует очень много причин, чтобы что-либо ждать.

Так что пока одни потоки в блокировке, другие — что-то делают.

Создание потоков

Простейшая функция создания потоков в пользовательском режиме операционной системы — CreateThread. Эта функция создаёт поток в текущем процессе. Вариантов параметризации CreateThread очень много и когда мы вызываем new Thread(), то из нашего .NET кода вызывается данная функция операционной системы.

В эту функцию передаются следующие атрибуты:

1) Необязательная структура с атрибутами безопасности:

• Дескриптор безопасности (SECURITY_ATTRIBUTES) + признак наследуемости дескриптора.
  

  В .NET его нет, но можно создать поток через вызов функции операционной системы;

2) Необязательный размер стека:

• Начальный размер стека, в байтах (система округляет это значение до размера страницы памяти)
  

  Т.к. за нас размер стека передаёт .NET, нам это делать не нужно. Это необходимо для вызовов методов и поддержки памяти.

3) Указатель на функцию — точка входа нового потоками
4) Необязательный аргумент для передачи данных функции потока.

Из того, что мы не имеем в .NET явно — это структура безопасности с атрибутами безопасности и размер стэка. Размер стэка нас мало интересует, но атрибуты безопасности нас могут заинтересовать, т.к. сталкиваемся мы с ними впервые. Сейчас мы рассмотривать их не будем. Скажу только, что они влияют на возможность изменения информации о потоке средствами операционной системы.

Если мы создаём любым способом: из .NET или же вручную, средствами ОС, мы как итог имеем и ManageThreadId и экземпляр класса Thread.

Также у этой функции есть необязательный флаг: CREATE_SUSPENDED — поток после создания не стартует. Для .NET это поведение по умолчанию.

Помимо всего прочего существует дополнительный метод CreateRemoteThread, который создаёт поток в чужом процессе. Он часто используется для мониторинга состояния чужого процесса (например программа Snoop). Этот метод создаёт в другом процессе поток и там наш поток начинает исполнение. Приложения .NET так же могут заливать свои потоки в чужие процессы, однако тут могут возникнуть проблемы. Первая и самая главная — это отсутствие в целевом потоке .NET runtime. Это значит, что ни одного метод фреймворка там не будет: только WinAPI и то, что вы написали сами. Однако, если там .NET есть, то возникает вторая проблема (которой не было раньше). Это — версия runtime. Необходимо: понять, что там запущено (для этого необходимо импортировать не-.NET методы runtime, которые написаны на C/C++ и разобраться, с чем мы имеем дело). На основании полученной информации подгрузить необходимые версии наших .NET библиотек и каким-то образом передать им управление.

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

Планирование потоков

Для того чтобы понимать, в каком порядке исполнять код различных потоков, необходима организация планирования тих потоков. Ведь система может иметь как одно ядро, так и несколько. Как иметь эмуляцию двух ядер на одном так и не иметь такой эмуляции. На каждом из ядер: железных или же эмулированных необходимо исполнять как один поток, так и несколько. В конце концов система может работать в режиме виртуализации: в облаке, в виртуальной машине, песочнице в рамках другой операционной системы. Поэтому мы в обязательном порядке рассмотрим планирование потоков Windows. Это — настолько важная часть материала по многопоточке, что без его понимания многопоточка не встанет на своё место в нашей голове никоим образом.

Итак, начнём. Организация планирования в операционной системе Windows является: гибридной. С одной стороны моделируются условия вытесняющей многозадачности, когда операционная система сама решает, когда и на основе каких условия вытеснить потоки. С другой стороны — кооперативной многозадачности, когда потоки сами решают, когда они всё сделали и можно переключаться на следующий (UMS планировщик). Режим вытесняющей многозадачности является приоритетным, т.к. решает, что будет исполняться на основе приоритетов. Почему так? Потому что у каждого потока есть свой приоритет и операционная система планирует к исполнению более приоритетные потоки. А вытесняющей потому, что если возникает более приоритетный поток, он вытесняет тот, который сейчас исполнялся. Однако во многих случаях это бы означало, что часть потоков никогда не доберется до исполнения. Поэтому в операционной системе есть много механик, позволяющих потокам, которым необходимо время на исполнение его получить несмотря на свой более низкий по сравнению с остальными, приоритет.

Уровни приоритета

Windows имеет 32 уровня приоритета (0-31)

• 1 уровень (00 — 00) — это Zero Page Thread;
• 15 уровней (01 — 15) — обычные динамические приоритеты;
• 16 уровней (16 — 31) — реального времени.

Самый низкий приоритет имеет Zero Page Thread. Это — специальный поток операционной системы, который обнуляет страницы оперативной памяти, вычищая тем самым данные, которые там находились, но более не нужны, т.к. страница была освобождена. Необходимо это по одной простой причине: когда приложение освобождает память, оно может ненароком отдать кому-то чувствительные данные. Личные данные, пароли, что-то ещё. Поэтому как операционная система так и runtime языков программирования (а у нас — .NET CLR) обнуляют получаемые участки памяти. Если операционная система понимает, что заняться особо нечем: потоки либо стоят в блокировке в ожидании чего-либо либо нет потоков, которые исполняются, то она запускает самый низко приоритетный поток: поток обнуления памяти. Если она не доберется этим потоком до каких-либо участков, не страшно: их обнулят по требованию. Когда их запросят. Но если есть время, почему бы это не сделать заранее?

Продолжая говорить о том, что к нам не относится, стоит отметить приоритеты реального времени, которые когда-то давным-давно таковыми являлись, но быстро потеряли свой статус приоритетов реального времени и от этого статуса осталось лишь название. Другими словами, Real Time приоритеты на самом деле не являются таковыми. Они являются приоритетами с исключительно высоким значением приоритета. Т.е. если операционная система будет по какой-то причине повышать приоритет потока с приоритетом из динамической группы (об этом — позже, но, например, потому, что потоку освободили блокировку) и при этом значение до повышения было равно 15, то повысить приоритет операционная система не сможет: следующее значение равно 16, а оно — из диапазона реального времени. Туда повышать такими вот «твиками» нельзя.

Уровень приоритетов процессов с позиции Windows API.

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

Однако, изменение уровня приоритета процесса не меняет относительных приоритетов внутри приложения: их значения сдвигаются, но не меняется внутренняя модель приоритетов: внутри по-прежнему будет поток с пониженным приоритетом и поток — с обычным. Так, как этого хотел разработчик приложения. Как же это работает?

Существует 6 классов приоритетов процессов. Класс приоритетов процессов — это то, относительно чего будут создаваться приоритеты потоков. Все эти классы приоритетов можно увидеть в «Диспетчере задач», при изменении приоритета какого-либо процесса.

Другими словами класс приоритета — это то, относительно чего будут задаваться приоритеты потоков внутри приложения. Чтобы задать точку отсчёта, было введено понятие базового приоритета. Базовый приоритет — это то значение, чем будет являться приоритет потока с типом приоритета Normal:

• Если процесс создаётся с классом Normal и внутри этого процесса создаётся поток с приоритетом Normal, то его реальный приоритет Normal будет равен 8 (строка №4 в таблице);
• Если Вы создаёте процесс и у него класс приоритета Above Normal, то базовый приоритет будет равен 10. Это значит, что потоки внутри этого процесса будут создаваться с более повышенным приоритетом: Normal будет равен 10.

Для чего это необходимо? Вы как программисты знаете модель многопоточности, которая у вас присутствует.
Потоков может быть много и вы решаете, что один поток должен быть фоновым, так как он производит вычисления и вам
не столь важно, когда данные станут доступны: важно чтобы поток завершил вычисления (например поток обхода и анализа дерева). Поэтому, вы устанавливаете пониженный приоритет данного потока. Аналогично может сложится ситуация когда необходимо запустить поток с повышенным приоритетом.

Представим, что ваше приложение запускает пользователь и он решает, что ваше приложение потребляет слишком много процессорных ресурсов. Пользователь считает, что ваше приложение не столь важное в системе, как какие-нибудь другие приложения и понижает приоритет вашего приложения до Below Normal. Это означает, что он задаёт базовый приоритет 6 относительно которого будут рассчитываться приоритеты потоков внутри вашего приложения. Но в системе общий приоритет упадёт. Как при этом меняются приоритеты потоков внутри приложения?

Таблица 3

Normal остаётся на уровне +0 относительно уровня базового приоритета процесса. Below normal — это (-1) относительно уровня базового. Т.е. в нашем примере с понижением уровня приоритета процесса до класса Below Normal приоритет потока ‘Below Normal’ пересчитается и будет не 8 - 1 = 7 (каким он был при классе Normal), а 6 - 1 = 5. Lowest (-2) станет равным 4.

Idle и Time Critical — это уровни насыщения (-15 и +15). Почему Normal — это 0 и относительно него всего два шага: -2, -1, +1 и +2? Легко провести параллель с обучением. Мы ходим в школу, получаем оценки наших знаний (5,4,3,2,1) и нам понятно, что это за оценки: 5 — молодец, 4 — хорошо, 3 — вообще не постарался, 2 — это не делал ни чего, а 1 — это то, что можно исправить потом на 4. Но если у нас вводится 10-ти бальная система оценок (или что вообще ужас — 100-бальная), то возникает неясность: что такое 9 баллов или 7? Как понять, что вам поставили 3 или 4?

Тоже самое и с приоритетами. У нас есть Normal. Дальше, относительно Normal у нас есть чуть повыше
Normal (Normal above), чуть пониже Normal (Normal below). Также есть шаг на два вверх
или на два вниз (Higest и Lowest). Нам, поверьте, нет никакой необходимости в более подробной градации. Единственное, очень редко, может раз в жизни, нам понадобится сказать: выше чем любой приоритет в системе. Тогда мы выставляем уровень Time Critical. Либо наоборот: это надо делать, когда во всей системе делать нечего. Тогда мы выставляем уровень Idle. Это значения — так называемые уровни насыщения.

Как рассчитываются уровни приоритета?

У нас бал класс приоритета процесса Normal (Таблица 3) и приоритет потоков Normal — это 8. Если процесс Above Normal то поток Normal получается равен 9. Если же процесс выставлен в Higest, то поток Normal получается равен 10.

Поскольку для планировщика потоков Windows все потоки процессов равнозначны, то:

• Для процесса класса Normal и потока Above-Normal
• Для процесса класса Higest и потока Normal
  конечные приоритеты будут одинаковыми и равны 10.

Если мы имеем два процесса: один с приоритетом Normal, а второй — с приоритетом Higest, но при этом
первый имел поток Higest а второй Normal, то система их приоритеты будет рассматривать как одинаковые.

Как уже обсуждалось, группа приоритетов Real-Time на самом деле не является таковой, поскольку настоящий Real-Time — это гарантированная доставка сообщения за определённое время либо обработка его получения. Т.е., другими словами, если на конкретном ядре есть такой поток, других там быть не должно. Однако это ведь не так: система может решить, что низко приоритетный поток давно не работал и дать ему время, отключив real-time. Вернее его назвать классом приоритетов который работает над обычными приоритетами и куда обычные приоритеты не могут уйти, попав под ситуации, когда Windows временно повышает им приоритет.

Но так как поток повышенным приоритетом исполняется только один на группе ядер, то получается,
что если у вас даже Real-Time потоки, не факт, что им будет выделено время.

Если перевести в графический вид, то можно заметить, что классы приоритетов пересекаются. Например, существует пересечение Above-Normal Normal Below-Normal (столбик с квадратиками):

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

Поэтому, когда процессу выдаётся более высокий класс приоритета, это повышает приоритет потоков процесса относительно обычных – с классом Normal.

Кстати говоря, мы стартовали продажи на CLRium #7, в котором мы с огромным удовольствием будем говорить про практику работы с многопоточным кодом. Будут и домашние задания и даже возможность работы с личным ментором.

Загляните к нам на сайт: мы сильно постарались, чтобы его было интересно изучить.

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

Введение

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

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

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

Рис.
8.1. 
Упрощенная диаграмма состояний потоков
в ОС Windows

Наиболее
важным вопросом планирования является
выбор момента для принятия решения. В
ОС Windows запуск процедуры планирования
вызывается одним из следующих событий.

Это,
во-первых, события, связанные с
освобождением процессора.

(1)
Завершение потока

(2)
Переход потока в состояние готовности
в связи с тем, что его квант времени
истек

(3)
Переход потока в состояние ожидания

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

(4)
Поток вышел из состояния ожидания

(5)
Поток только что создан

(6)
Деятельность текущего потока может
иметь следствием вывод другого потока
из состояния ожидания.

В
последнем случае выведенный из состояния
ожидания поток может сразу же начать
выполняться, если имеет высокий приоритет.

Наконец,
процедура планирования может быть
запущена, если изменяется приоритет
потока в результате вызова системного
сервиса или самой Windows, а также если
изменяется привязка (affinity) потока к
процессору, из-за чего поток не может
больше выполняться на текущем процессоре.

Заметим,
что переключение из пользовательского
режима в режим ядра (и обратно) не влияет
на планирование потока, так как контекст
в этом случае не меняется.

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

Перевод
потока из состояния ожидания в состояние
готовности (вариант 4) может быть
следствием прерывания, свидетельствующим
об окончании операции ввода-вывода. В
этом случае процедура планирования
может быть отложена (deffered procedure call) до
окончания выполнения высокоприоритетного
системного кода.

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

Алгоритмы
планирования

Приоритеты

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

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

Рис.
8.2. 
Приоритеты потоков

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

• реального
  времени
  (REALTIME_PRIORITY_CLASS),

• высокий
  (HIGH_PRIORITY_CLASS),

• выше
  нормы
  (ABOVE_NORMAL_PRIORITY_CLASS),

• нормальный
  (NORMAL_PRIORITY_CLASS),

• ниже
  нормы
  (BELOW_NORMAL_PRIORITY_CLASS)

• и
  неработающий
  (IDLE_PRIORITY_CLASS).

Относительный
приоритет потока устанавливается
аналогичными параметрами функции
SetThreadPriority:

Совокупность
из шести классов приоритетов процессов
и семи классов приоритетов потоков
образует 42 возможные комбинации и
позволяет сформировать так называемый
базовый приоритет потока
(см. таб.
8.1).

Базовый
приоритет процесса и первичного потока
по умолчанию равен значению из середины
диапазонов приоритетов процессов (24,
13, 10, 8, 6 или 4). Смена приоритета процесса
влечет за собой смену приоритетов всех
его потоков, при этом их относительные
приоритеты остаются без изменений.

Приоритеты
с 16 по 31 в действительности приоритетами
реального времени не являются, поскольку
в рамках поддержки мягкого реального
времени, которая реализована в ОС
Windows, никаких гарантий относительно
сроков выполнения потоков не дается.
Это просто более высокие приоритеты,
которые зарезервированы для системных
потоков и тех потоков, которым такой
приоритет дает пользователь с
административными правами. Тем не менее,
наличие приоритетов реального времени,
а также вытесняемость кода ядра,
локализация страниц памяти и ряд
дополнительных возможностей – все это
позволяет выполнять в среде ОС Windows
приложения мягкого реального времени,
например, мультимедийные. Системный
поток с нулевым приоритетом занимается
обнулением страниц памяти. Обычные
пользовательские потоки могут иметь
приоритеты от 1 до 15.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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

First Come First Serve (FCFS)

Время ожидания каждого процесса выглядит следующим образом —

Среднее время ожидания: (0 + 4 + 6 + 13) / 4 = 5,75

Кратчайшая работа следующая (SJN)

Это не упреждающий, упреждающий алгоритм планирования.

Лучший подход для минимизации времени ожидания.

Легко реализовать в пакетных системах, где необходимое время процессора известно заранее.

Невозможно реализовать в интерактивных системах, где необходимое время ЦП неизвестно.

Процессор должен заранее знать, сколько времени займет процесс.

Это не упреждающий, упреждающий алгоритм планирования.

Лучший подход для минимизации времени ожидания.

Легко реализовать в пакетных системах, где необходимое время процессора известно заранее.

Невозможно реализовать в интерактивных системах, где необходимое время ЦП неизвестно.

Процессор должен заранее знать, сколько времени займет процесс.

Дано: таблица процессов и время их прибытия, время выполнения

Время ожидания каждого процесса выглядит следующим образом —

Среднее время ожидания: (0 + 4 + 12 + 5) / 4 = 21/4 = 5,25

Источник

Простая модель планировщика ОС

Не так давно пытался найти здесь какую-нибудь информацию о планировщике Windows и к своему удивлению не нашёл ничего конкретного о планировщиках вообще, поэтому решил запостить вот этот пример планировщика, надеюсь кому-то он окажется полезен. Код написан на Turbo Pascal со вставками ассемблера 8086.

Что собственно планирует планировщик?

Алгоритмы планирования

Критические секции

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

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

Взаимная блокировка

Допустим у нас есть неразделяемые ресурсы А и Б и потоки Х, Y, которые хотят задействовать эти ресурсы. Если некий криворукий недостаточно компетентный программист расставит критические скобки вот так:
…
Поток X
Занять Ресурс(А)
Занять Ресурс(Б)
…
Отдать Ресурс(А)
Отдать Ресурс(Б)
Поток Y
Занять Ресурс(Б)
Занять Ресурс(А)
…
Отдать Ресурс(Б)
Отдать Ресурс(А)

через некоторое время возникнет вот такая ситуация:

Сладенькое

Ну и собственно то ради чего это всё писалось. Как уже было сказано код нашего планировщика будет выполнен на языке Turbo Pascal.
Механизм критических секций реализован в процедурах EnterCritical(), LeaveCritical(). Вспомним ещё раз: чтобы войти в критическую секцию — нужно проверить не занята ли она, и по результату — либо занять её и разрешить потоку ей пользоваться, либо поставить поток в очередь и передать управление кому-то другому.

C LeaveCritical() вроде бы и так всё ясно:

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

Сама процедура скомпилирована с директивой interrupt, то есть является обработчиком прерывания. Которое может быть спровоцировано как аппаратно, так и программно вызовом int 08h, вот так:

Так же необходимо описать сами процедуры регистрации, включения и остановки потоков. Если кому-то интересно — можно посмотреть в исходниках процедуры RegistrThread, RunThread, StopThread.
Вот и всё! Наш планировщик готов.
Исходники вместе примером многопоточной программы написаной под этот планировщих и досовским турбиком можно скачать здесь. Можно поиграться и посмотреть как по разному будут выполняться потоки при вытесняющей и невытесняющей многозадачности (процедура ExecuteRegisterThreads(true/false)), смоделировать ситуацию взаимной блокировки и убедиться в том, что она не всегда диагностируема (я однажды минуту ждал пока возникнет дедлок).
Запускать в системах новее Win98 советую из под DOSbox.

Источник

4.1 Основные понятия планирования процессов

Ситуации, когда необходимо планирование:

Когда создается процесс

Когда процесс завершает работу

Когда процесс блокируется на операции ввода/вывода, семафоре, и т.д.

При прерывании ввода/вывода.

Необходимость алгоритма планирования зависит от задач, для которых будет использоваться операционная система.

Основные три системы:

Задачи алгоритмов планирования:

4.2 Планирование в системах пакетной обработки

Процессы ставятся в очередь по мере поступления.

Справедливость (как в очереди покупателей, кто последний пришел, тот оказался в конце очереди)

Процесс, ограниченный возможностями процессора может затормозить более быстрые процессы, ограниченные устройствами ввода/вывода.

Нижняя очередь выстроена с учетом этого алгоритма

Уменьшение оборотного времени

Справедливость (как в очереди покупателей, кто без сдачи проходит в перед)

Длинный процесс занявший процессор, не пустит более новые краткие процессы, которые пришли позже.

4.2.3 Наименьшее оставшееся время выполнение

Аналог предыдущего, но если приходит новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса.

4.3 Планирование в интерактивных системах

4.3.1 Циклическое планирование

Самый простой алгоритм планирования и часто используемый.

Каждому процессу предоставляется квант времени процессора. Когда квант заканчивается процесс переводится планировщиком в конец очереди. При блокировке процессор выпадает из очереди.

Пример циклического планирования

Справедливость (как в очереди покупателей, каждому только по килограмму)

4.3.2 Приоритетное планирование

Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом.

Приоритет может быть динамический и статический.

Динамический приоритет может устанавливаться так:

П=1/Т, где Т- часть использованного в последний раз кванта

Если использовано 1/50 кванта, то приоритет 50.

Если использован весь квант, то приоритет 1.

Т.е. процессы, ограниченные вводом/вывода, будут иметь приоритет над процессами ограниченными процессором.

Часто процессы объединяют по приоритетам в группы, и используют приоритетное планирование среди групп, но внутри группы используют циклическое планирование.

Приоритетное планирование 4-х групп

4.3.3 Методы разделения процессов на группы

Группы с разным квантом времени

Сначала процесс попадает в группу с наибольшим приоритетом и наименьшим квантом времени, если он использует весь квант, то попадает во вторую группу и т.д. Самые длинные процессы оказываются в группе наименьшего приоритета и наибольшего кванта времени.

Процесс либо заканчивает работу, либо переходит в другую группу

Группы с разным назначением процессов

Процесс, отвечающий на запрос, переходит в группу с наивысшим приоритетом.

Такой механизм позволяет повысить приоритет работы с клиентом.

В системе с n-процессами, каждому процессу будет предоставлено 1/n времени процессора.

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

Процессорное время распределяется среди пользователей, а не процессов. Это справедливо если у одного пользователя несколько процессов, а у другого один.

4.4 Планирование в системах реального времени

Системы реального времени делятся на:

Внешние события, на которые система должна реагировать, делятся:

Что бы систему реального времени можно было планировать, нужно чтобы выполнялось условие:

Т.е. перегруженная система реального времени является не планируемой.

4.4.1 Планирование однородных процессов

В качестве однородных процессов можно рассмотреть видео сервер с несколькими видео потоками (несколько пользователей смотрят фильм).

Т.к. все процессы важны, можно использовать циклическое планирование.

Но так как количество пользователей и размеры кадров могут меняться, для реальных систем он не подходит.

4.4.2 Общее планирование реального времени

Используется модель, когда каждый процесс борется за процессор со своим заданием и графиком его выполнения.

Планировщик должен знать:

частоту, с которой должен работать каждый процесс

объем работ, который ему предстоит выполнить

ближайший срок выполнения очередной порции задания

Рассмотрим пример из трех процессов.

Процесс А запускается каждые 30мс, обработка кадра 10мс

Процесс В частота 25 кадров, т.е. каждые 40мс, обработка кадра 15мс

Процесс С частота 20 кадров, т.е. каждые 50мс, обработка кадра 5мс

Три периодических процесса

Проверяем, можно ли планировать эти процессы.

10/30+15/40+5/50=0.808 4.4.3 Статический алгоритм планирования RMS (Rate Monotonic Scheduling)

Процессы должны удовлетворять условиям:

Процесс должен быть завершен за время его периода

Один процесс не должен зависеть от другого

Каждому процессу требуется одинаковое процессорное время на каждом интервале

У непериодических процессов нет жестких сроков

Прерывание процесса происходит мгновенно

Приоритет в этом алгоритме пропорционален частоте.

Процессу А он равен 33 (частота кадров)

Процессу В он равен 25

Процессу С он равен 20

Процессы выполняются по приоритету.

Статический алгоритм планирования RMS (Rate Monotonic Scheduling)

4.4.4 Динамический алгоритм планирования EDF (Earliest Deadline First)

Наибольший приоритет выставляется процессу, у которого осталось наименьшее время выполнения.

При больших загрузках системы EDF имеет преимущества.

Проверяем, можно ли планировать эти процессы.

Источник

Планирование потоков

Если операционная система поддерживает многопоточность, она может распределять процессорное время либо между процессами, либо между потоками. В операционной системе Windows процессор предоставляется потокам, иначе говоря, осуществляется планирование на уровне потоков.

Таким образом, если один процесс имеет пять потоков, а второй – десять, то первый процесс будет занимать процессор в два раза больше времени, чем второй (при условии, конечно, что все потоки имеют равный приоритет и выполняют примерно одинаковую работу).

Алгоритмы планирования

Существуют разные алгоритмы планирования. Рассмотрим основные виды.

1. Вытесняющие/невытесняющие алгоритмы.

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

2. Алгоритмы с квантованием.

3. Алгоритмы с приоритетами.

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

В Windows реализован смешанный алгоритм планирования – вытесняющий, на основе квантования и приоритетов.

Состояния потоков

За время своего существования поток может находиться в нескольких состояниях. Перечислим основные состояния:

Кроме основных существует ещё несколько состояний – Инициализация (Init), Завершение (Terminate), Состояние простоя (Standby), Переходное состояние (Transition), Состояние отложенной готовности (Deferred ready). Подробнее о них можно узнать в [5; 2].

На рис.9.1 показаны основные состояния потока, возможные переходы между состояниями и условия переходов.

Кванты

В Windows имеется два базовых размера кванта – 2 интервала системного таймера и 12 интервалов. Если квант времени короткий, то потоки будут переключаться быстрее и «отзывчивость» (responsiveness) системы улучшится – это важное свойство для пользователя, поэтому в клиентских системах Windows по умолчанию используются короткие кванты. При этом производительность системы в целом снижается, поскольку потоки не будут успевать выполнять свои задачи в течение выделенного кванта, а частые переключения создадут высокие накладные расходы (служебные операции системы при смене потоков). Вследствие этого в серверных версиях Windows по умолчанию применяются длинные кванты.

Длительность интервала системного таймера (в сотнях наносекунд) хранится в переменной KeMaximumIncrement (для x86 – файл basentosexi386splocks.asm, строка 140; для x64 – файл basentosexamd64hifreqlk.asm, строка 147) и устанавливается функцией KeSetTimeIncrement (файл basentoskemiscc.c, строка 711 на основе значения, предоставляемого HAL.

Каждый процесс хранит величину кванта в поле QuantumReset структуры KPROCESS (файл basentosincke.h, строка 1029). Значение в этом поле равно количеству интервалов таймера, умноженному на 3. Например, для длинных квантов (12 интервалов) значение QuantumReset будет равно 36. Таким образом, при каждом срабатывании таймера (возникает прерывание) система уменьшает квант выполняющегося потока на 3 единицы.

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

Значение кванта может быть изменено пользователем. Например, на Windows 7 нужно проделать следующее: Компьютер – Свойства – Дополнительные параметры системы – вкладка «Дополнительно» – раздел «Быстродействие» – Параметры – вкладка «Дополнительно» – раздел «Распределение времени процессора». Можно выбрать короткие кванты («Оптимизировать работу программ») или длинные («Оптимизировать работу служб, работающих в фоновом режиме») (рис.9.2).

За изменение величины кванта отвечает функция KeSetQuantumProcess (файл basentoskeprocobj.c, строка 1393).

Кроме длинных и коротких квантов в Windows реализовано динамическое увеличение размера кванта для потоков активного процесса (т.е. того процесса, окно которого в настоящий момент активно). За повышение кванта (и приоритета) отвечает функция PspComputeQuantumAndPriority (файл basentospspsquery.c, строка 4415). Более подробную информацию о динамическом увеличении кванта см. [5, стр. 361].

Приоритеты

В операционной системе Windows имеется 32 уровня приоритета – от 0 до 31 (рис.9.3).

Таблица 9.1. Влияние относительных приоритетов

Пример. Имеется процесс с базовым приоритетом Below Normal (6). Поток, принадлежащий этому процессу, имеет такой же базовый приоритет. Вызов функции SetThreadPriority с параметром Highest сделает базовый приоритет потока равным 8, а с параметром Time Critical – равным 15.

Текущий приоритет потока при создании потока равен базовому, но в дальнейшем может динамически повышаться и понижаться операционной системой (эта процедура будет рассмотрена далее). Заметим, что для потоков с базовым приоритетом Real Time текущий приоритет не изменяется и всегда равен базовому.

Источник

Обзор алгоритмов планирования в windows

Новые потоки выделяются зеленым, а существующие – красным. (Длительность подсветки настраивается в Options.) Это помогает обнаруживать создание лишних потоков в процессе. (Как правило, потоки должны создаваться при запуске процесса, а не при каждой обработке какого-либо запроса внутри процесса.)
Когда вы поочередно выбираете потоки в списке, Process Explorer отображает их идентификаторы, время запуска, состояние, счетчики использования процессорного времени, число переключений контекстов, а также базовый и текущий приоритеты. Кнопка KiIl позволяет принудительно завершать индивидуальные потоки, но пользоваться ею следует с крайней осторожностью.
Разница в числе переключений контекста (context switch delta) отражает, сколько раз потоки начинали работать в течение периода обновления, указанного в Process Explorer. Это еще один способ определения активности потоков. B некоторых отношениях он даже лучше, так как многие потоки выполняются в течение лишь очень короткого времени и поэтому крайне редко попадают в список текущих потоков. Например, если вы добавите столбец с разницей в числе переключений контекстов к тому, что показывается для процесса и отсортируете по этому столбцу, то увидите процессы, в которых потоки выполняются, но используют очень мало процессорного времени или вообще его не используют.
Стартовый адрес потока выводится в виде «modulefunction»,где module –имя EXE или DLL. Имя функции извлекается из файла символов для данного модуля (см. эксперимент «Просмотр детальных сведений о процессах с помощью Process Explorer» в главе 1). Если вы точно не знаете, что это за модуль, нажмите кнопку Module, и появится окно свойств модуля, где содержится данная функция.

ПРИМЕЧАНИЕ Для потоков, созданных Windows-функцией Create-Tbread, Process Explorer показывает функцию, переданную в Create-Tbread, а не истинную стартовую функцию потока. Это связано с тем, что все Windows-потоки запускаются в общей стартовой функции-оболочке для процессов или потоков (BaseProcessStartJin6oBaseThre-adStart в Kernel32.dll). Если бы Process Explorer выводил истинный стартовый адрес, то казалось бы, что большинство потоков в процессе были запущены по одному адресу, а это вряд ли помогло бы понять, какой код выполняется потоком.

Однако одного стартового адреса потока может оказаться недостаточно для того, чтобы выяснить, что именно делает поток и какой компонент внутри процесса отвечает за использование процессорного времени этим потоком. Это особенно верно, если стартовый адрес потока относится к универсальной стартовой функции (например, если имя функции не указывает на
то, что делает данный поток). Тогда может помочь изучение стека потока. Для его просмотра дважды щелкните интересующий вас поток (или выберите этот поток и нажмите кнопку Stack). Process Explorer покажет стек потока (пользовательского режима и режима ядра, если поток был в последнем режиме).

ПРИМЕЧАНИЕ Отладчики пользовательского режима (Windbg, Ntsd и Cdb) тоже позволяют подключаться к процессу и просматривать стек потока, но Process Explorer выводит стек как пользовательского режима, так и режима ядра простым нажатием одной кнопки. Стеки пользовательского режима и режима ядра можно , но эта утилита гораздо сложнее в использовании. Кстати, при работе Windbg в режиме локальной отладки ядра, поддерживаемом только в Windows XP и Windows Server 2003, увидеть содержимое стеков потоков нельзя.

Просмотр стека потока полезен и при поиске причины зависания процесса. Например, на одной системе Microsoft PowerPoint зависал при запуске на минуту. Чтобы понять причину этого зависания, с помощью Process Explorer изучили стек одного из потоков в процессе. Результат приведен на рис. 6-10.

Как видите, PowerPoint (строка 10) вызвал функцию в Mso.dll (основной Microsoft Office DLL), которая обратилась к функции OpenPrinterWBWinspool.drv (DLL, используемой для подключения к принтерам). Затем Winspool.drv пересылает запрос функции OpenPrinterRPC,а та вызывает функцию в DLL исполняющей среды RPC, сообщая, что запрос посылается удаленному принтеру. Вот так, не зная деталей внутреннего устройства PowerPoint, по именам модулей и функций в стеке потока можно понять, что поток ждет соединения с сетевым принтером. B данной системе был сетевой принтер, который не отвечал, что и объясняет задержку в запуске PowerPoint. (Приложения Microsoft Office соединяются со всеми сконфигурированными принтерами при запуске.) Соединение с тем принтером было удалено из пользовательской системы, и проблема исчезла.

Планирование потоков

Здесь описываются стратегии и алгоритмы планирования в Windows. B первом разделе этой части материалов рассматриваются принципы планирования в Windows и даются определения ключевых терминов. Уровни приоритета обсуждаются с точки зрения как Windows API, так и ядра. После обзора сопутствующих Windows-функций и утилит подробно анализируются – сначала в однопроцессорных системах, а затем и в многопроцессорных – алгоритмы и структуры данных, используемые подсистемой планирования Windows.

Обзор планирования в Windows

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

ЭКСПЕРИМЕНТ: просмотр потоков, готовых к выполнению
Список потоков, готовых к выполнению, можно увидеть с помощью команды !readyотладчика ядра. Она выводит поток или список потоков, готовых к выполнению (на каждом уровне приоритета отдельно). B следующем примере к выполнению готовы два потока с приоритетом 10 и шесть потоков – с приоритетом 8. Поскольку эта информация получена в однопроцессорной системе с использованием LiveKd, текущим потоком всегда является отладчик ядра (Kd или WinDbg).

Выбранный для выполнения поток работает в течение некоего периода, называемого квантом.Квант определяет, сколько времени будет выполняться поток, пока не наступит очередь другого потока с тем же приоритетом (или более высоким, что возможно в многопроцессорной системе). Длительность квантов зависит от трех факторов: конфигурационных параметров системы (длинные или короткие кванты), статуса процесса (активный или фоновый) и использования объекта «задание» для изменения длительности квантов. (Подробнее о квантах см. раздел «Квант» далее в этой главе.) Однако поток может не полностью использовать свой квант. Поскольку в Windows реализован вытесняющий планировщик, то происходит вот что. Как только другой поток с более высоким приоритетом готов к выполнению, текущий поток вытесняется, даже если его квант еще не истек. Фактически поток может быть выбран следующим для выполнения и вытеснен, не успев воспользоваться своим квантом!
Код Windows, отвечающий за планирование, реализован в ядре. Поскольку этот код рассредоточен по ядру, единого модуля или процедуры с названием «планировщик» нет. Совокупность процедур, выполняющих эти обязанности, называется диспетчерам ядра(kernel’s dispatcher). Диспетчеризация потоков может быть вызвана любым из следующих событий.

(o)Поток готов к выполнению – например, он только что создан или вышел из состояния ожидания.
(o)Поток выходит из состояния Running (выполняется), так как его квант истек или поток завершается либо переходит в состояние ожидания.
(o)Приоритет потока изменяется в результате вызова системного сервиса или самой Windows.
(o)Изменяется привязка к процессорам, из-за чего поток больше не может работать на процессоре, на котором он выполнялся.

B любом случае Windows должна определить, какой поток выполнять следующим. Выбрав новый поток, Windows переключает контекст.Эта операция заключается в сохранении параметров состояния машины, связанных с выполняемым потоком, и загрузке аналогичных параметров для другого потока, после чего начинается выполнение нового потока.
Как уже говорилось, планирование в Windows осуществляется на уровне потоков. Этот подход станет понятен, если вы вспомните, что сами процессы не выполняются, а лишь предоставляют ресурсы и контекст для выполнения потоков. Поскольку решения, принимаемые в ходе планирования, касаются исключительно потоков, система не обращает внимания на то, какому процессу принадлежит тот или иной поток. Так, если у процесса A есть 10, у процесса B – 2 готовых к выполнению потока, и все 12 имеют одинаковый приоритет, каждый из потоков теоретически получит 1/12 процессорного времени, потому что Windows не станет поровну делить процессорное время между двумя процессами.
Чтобы понять алгоритмы планирования потоков, вы должны сначала разобраться в уровнях приоритета, используемых Windows.

Уровни приоритета

Как показано на рис. 6-11, в Windows предусмотрено 32 уровня приоритета – от 0 до 31. Эти значения группируются так: (o)шестнадцать уровней реального времени (16-31); (o)пятнадцать варьируемых (динамических) уровней (1-15);

(o)один системный уровень (0), зарезервированный для потока обнуления страниц (zero page thread).

Рис. 6-12. Взаимосвязь приоритетов в ядре и Windows API

Начальный базовый приоритет потока наследуется от базового приоритета процесса, а тот наследует его от родительского процесса. Это поведение можно изменить при вызове Windows-функции CreateProcess иликоманды START. Приоритет процесса можно изменить и после его создания, используя функцию SetPriorityClassили различные утилиты, предоставляющие доступ к этой функции через UI, например диспетчер задач и Process Explorer. B частности, вы можете понизить приоритет процесса, интенсивно использующего процессорное время, чтобы он не мешал обычным операциям в системе. Смена приоритета процесса влечет за собой смену приоритетов всех его потоков, но их относительные приоритеты остаются прежними. Ho изменение приоритетов индивидуальных потоков внутри процесса обычно не имеет смысла, потому что вы не знаете, чем именно занимается каждый из них (если только сами не пишете программу или не располагаете исходным кодом); так что изменение относительных приоритетов потоков может привести к неадекватному поведению этого приложения.
Обычно базовый приоритет процесса (а значит, и базовый приоритет первичного потока) по умолчанию равен значению из середины диапазонов приоритетов процессов (24, 13, 10, 8, 6 или 4). Однако базовый приоритет некоторых системных процессов (например, диспетчера сеансов, контроллера сервисов и сервера локальной аутентификации) несколько превышает значение по умолчанию для класса Normal (8). Более высокий базовый приоритет по умолчанию обеспечивает запуск потоков этих процессов с приоритетом выше 8. Чтобы изменить свой начальный базовый приоритет, такие системные процессы используют внутреннюю функцию NtSetInformationProcess.

Функции Windows API, связанные с планированием

Эти функции перечислены в таблице 6-14 (более подробную информацию см. в справочной документации Windows API).

Таблица 6-14. API-функции планирования и их назначение

Сопутствующие утилиты

Единственный способ задать начальный класс приоритета для процесса – использовать команду startв командной строке Windows. Если вы хотите, чтобы некая программа каждый раз запускалась с определенным приоритетом, то можете создать для нее ярлык и указать команду запуска, предварив ее cmd /с.Это приведет к появлению окна командной строки, выполнению команды и последующему закрытию этого окна. Например, чтобы запустить Notepad в процессе с низким приоритетом, в свойствах ярлыка должна быть задана команда cmd /с start /low notepad.exe.

ЭКСПЕРИМЕНТ: исследуем и задаем приоритеты процессов и потоков
Попробуйте провести такой эксперимент.
1. Наберите в командной строке start /realtime notepad.Ha экране появится окно Notepad.
2. Запустите утилиту Process Explorer или Process Viewer (Pviewer.exe) из Support Tools и выберите Notepad.exe из списка процессов, как показано ниже. Заметьте, что динамический приоритет потока Notepad равен 24. Это значение совпадает со значением приоритета реального времени на рис. 6-12.

Диспетчер системных ресурсов Windows

B Windows Server 2003 Enterprise Edition и Windows Server 2003 Data-center Edition включен необязательный компонент, который называется диспетчером системных ресурсов Windows (Windows System Resource Manager, WSRM). Он позволяет администратору настраивать правила политики, указывающие для процессов использование процессорного времени, параметры привязки к процессорам и лимиты на физическую и виртуальную память. Кроме того, WSRM может генерировать отчеты по использованию ресурсов, удобные для учета и проверки уровня обслуживания по договорам с пользователями.
Такие правила могут быть применены к конкретным приложениям, пользователям или группам и действовать в определенные периоды или постоянно.
После того как вы сформировали политику выделения ресурсов для управления определенными процессами, служба WSRM будет вести мониторинг потребления ими процессорного времени и регулировать их базовые приоритеты, если эти процессы будут использовать процессорного времени больше или меньше, чем было установлено вами.
Ограничение физической памяти достигается заданием максимального размера рабочего набора через функцию SetProcessWorkingSetSizeEx,а ограничение виртуальной памяти реализуется самой службой (о лимитах на объемы физической и виртуальной памяти см. главу 7). Если заданный лимит превышен, WSRM – в зависимости от настроек – может уничтожать процессы или создавать соответствующую запись в журнале событий. Последнее позволяет выявить процесс с утечкой памяти до того, как он займет всю переданную виртуальную память в системе. Заметьте, что лимиты на память, установленные в WSRM, не применяются к памяти Address Windowing Extensions (AWE), памяти больших страниц (large page memory) или памяти ядра (пулу подкачиваемых или неподкачиваемых страниц).

Приоритеты реального времени

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

ПРИМЕЧАНИЕ Как показано на следующей иллюстрации, где изображены уровни запросов прерываний (Interrupt Request Levels, IRQL) на платформе x86, в Windows имеется набор приоритетов, называемых приоритетами реального времени, но они не являются таковыми в общепринятом смысле этого термина, так как Windows не относится к операционным системам реального времени. Подробнее на эту тему см. врезку «Windows и обработка данных в реальном времени» в главе 3, а также статью «Real-Time Systems and Microsoft Windows NT» в MSDN Library.

Уровни прерываний и уровни приоритета

Состояния потоков

Вот что представляют собой состояния потока.
(o) Ready (готов)Поток в состоянии готовности ожидает выполнения. Выбирая следующий поток для выполнения, диспетчер принимает во внимание только пул потоков, готовых к выполнению.
(o) Standby (простаивает)Поток в этом состоянии уже выбран следующим для выполнения на конкретном процессоре. B подходящий момент диспетчер переключает контекст на этот поток. B состоянии Standby может находиться только один поток для каждого процессора в системе. Заметьте, что поток может быть вытеснен даже в этом состоянии (если, например, до начала выполнения потока, который пока находится в состоянии Standby, к выполнению будет готов поток с более высоким приоритетом).
(o) Running (выполняется)Поток переходит в это состояние и начинает выполняться сразу после того, как диспетчер переключает на него контекст. Выполнение потока прекращается, как только он завершается, вытесняется потоком с более высоким приоритетом, переключает контекст на другой поток, самостоятельно переходит в состояние ожидания или истекает выделенный ему квант процессорного времени (и другой поток с тем же приоритетом готов к выполнению).
(o) Waiting (ожидает)Поток входит в состояние Waiting несколькими способами. Он может самостоятельно начать ожидание на синхронизирующем объекте или его вынуждает к этому подсистема окружения. По окончании ожидания поток – в зависимости от приоритета – либо немедленно начинает выполняться, либо переходит в состояние Ready.
(o) Transition (переходное состояние)Поток переходит в это состояние, если он готов к выполнению, но его стек ядра выгружен из памяти. Как только этот стек загружается в память, поток переходит в состояние Ready.
(o) Terminated (завершен)Заканчивая выполнение, поток переходит в состояние Terminated. После этого блок потока исполнительной системы (структура данных в пуле неподкачиваемой памяти, описывающая данный поток) может быть удален, а может быть и не удален – это уже определяется диспетчером объектов.
(o) Initialized (инициализирован)B это состояние поток входит в процессе своего создания.

ЭКСПЕРИМЕНТ: изменение состояний потоков при планировании
Вы можете понаблюдать за изменением этих состояний с помощью оснастки Performance. Она может оказаться полезной в отладке многопоточных приложений, если вам нужно проверить состояние потоков, выполняемых в вашем процессе.
1. Запустите стандартную программу Notepad (Блокнот) (Notepad.exe).
2. Запустите оснастку Performance (Производительность), открыв в меню Start (Пуск) подменю Programs (Программы) и Administrative Tools (Администрирование), а затем выбрав команду Performance (Производительность).
3. Выберите режим просмотра диаграмм (если установлен какой-то другой).
4. Щелкните график правой кнопкой мыши и выберите команду Properties (Свойства).
5. Откройте вкладку Graph (График) и установите максимальное значение вертикальной шкалы равным 7. (Состояниям потоков соответствуют числа от O до 7). Щелкните кнопку ОК.
6. Щелкните на панели инструментов кнопку Add (Добавить), чтобы открыть диалоговое окно Add Counters (Добавить счетчики).
7. Выберите в списке объект Thread (Поток), а затем – счетчик Thread State (Состояние потока). Определение его значений вы увидите, щелкнув кнопку Explain (Объяснение), как показано ниже.

База данных диспетчера ядра

Для принятия решений при планировании потоков ядро поддерживает набор структур данных, в совокупности известных как база данных ducnem-чераядра(dispatcher database) (рис. 6-15). Эта база данных позволяет отслеживать потоки, ждущие выполнения, и потоки, выполняемые на тех или иных процессорах.

ПРИМЕЧАНИЕ База данных диспетчера ядра в однопроцессорной системе имеет ту же структуру, что и в многопроцессорных системах Windows 2000 и Windows XP, но отличается от структуры такой базы данных в системах Windows Server 2003. Эти различия, а также иной алгоритм выбора потоков для выполнения в многопроцессорных системах поясняются в разделе «Многопроцессорные системы».

Источник

Рассмотрим, как в системе Windows осуществляется планирование потоков для их выполнения на центральном процессоре. Также посмотрим на приоритеты процессов и потоков.

Планирование потоков в системе

В Windows всегда выполняется хотя бы один поток с самым высоким приоритетом. Если в системе много ядер, то Windows делит все ядра на группы по 64 ядра. Каждому процессу даётся доступ к определённой группе ядер. Следовательно потоки этих процессов могут видеть только свою группу ядер.

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

Поток может не отработать весь свой квант, так как если другой поток готов к выполнению и имеет более высокий приоритет, то он вытеснит первый поток.

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

Так как процессор постоянно обрабатывает разные, несвязанные между собой потоки, то он должен запоминать на каком результате он остановился выполняя определённый поток. Такое запоминание предыдущего потока и переключение на новый называют – переключением контекста.

Планирование осуществляется на уровне потоков, а не процессов. Например, Процесс_А имеет 10 потоков, а Процесс_Б – 2 потока. Тогда процессорное время распределился между этими 12 потоками равномерно.

Приоритеты потоков

Планирование потоков полагается на их приоритеты. Windows использует 32 уровня приоритета для потоков от 0 до 31:

• 16 — 31 — уровни реального времени;
• 1 — 15 — обычные динамические приоритеты;
• 0 — зарезервирован для потока обнуления страниц.

Вначале поток получает свой Базовый приоритет, который наследуется от приоритета процесса:

• реального времени (24),
• высокий (13),
• выше среднего (10),
• обычный (8),
• ниже среднего (6),
• низкий (4).

Дальше назначается относительный приоритет который увеличивает или уменьшает приоритет потока:

• критический по времени (+15),
• наивысший (+2),
• выше среднего(+1),
• обычный (0),
• ниже среднего (-1),
• самый низкий (-2),
• уровень простоя (-15).

После получения базового приоритета и корректировки относительным приоритетом получается динамический приоритет:

Изменить базовый приоритет процесса можно из “Диспетчера задач” на вкладке “Подробности“, или в “Process Explorer“. Однако, это не поменяет относительный приоритет потока.

Приоритеты отдельных потоков можно посмотреть в программе “Process Explorer“. Но изменять их нет смысла, так как только разработчик данной программы понимает как лучше расставить приоритеты потокам.

Получается что относительный приоритет у потока Notepad.exe равен 2, так как динамический приоритет больше базового на 2.

Состояния потоков

Поток может находиться в следующих состояниях:

• Готов (Ready) — поток готов к выполнению и ожидает процессор.
• Готов с отложенным выполнением (Deferred ready) — поток выбран для выполнения на конкретном ядре и ожидает именно это ядро.
• В повышенной готовности (Standby) — поток выбран следующим для выполнения на конкретном ядре. Как только сможет процессор выполнит переключение контекста на этот поток.
• Выполнение (Running) — выполняется на процессоре пока не истечет его квант времени, или пока его не вытеснит поток с большем приоритетом.
• Ожидание (Waiting) — поток ждет каких-то ресурсов.
• Переходное состояние (Transition) — готов к выполнению, но стек ядра выгружен из памяти, как только стек загрузится в память поток перейдет в состояние Готов.
• Завершение (Terminated) — поток выполнил свою работу и завершился сам, или его завершили принудительно.
• Инициализация (Initializated) — состояние при создании потока.

Кванты времени

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

Итак, теперь я вам покажу как переключить систему на работу с длинным или коротким квантом.  Длительность кванта времени настраивается тут: “Свойства системы” / “Дополнительные параметры системы” / “Дополнительно” / “Быстродействие” / “Параметры” / “Дополнительно”:

• Программ – короткий квант времени;
• Служб – длинный квант времени.

На серверной системе можно выбрать “программ” если это сервер терминалов или просто настольный компьютер с установленной серверной системой.

На десктопной системе можно выбрать “служб” если вы запускаете какую-то длительную компиляцию или рендерите видео, а потом вернуть обратно в состояние “программ“.

Изменение приоритета планировщиком

Планировщик Windows периодически меняет текущий приоритет потоков. Делается это например для:

• повышения приоритета, если поток слишком долго ожидает выполнение (предотвращает зависание программы);
• повышения приоритета, если происходит ввод из пользовательского интерфейса (сокращение времени отклика);
• повышения приоритета, после завершения операции ввода/вывода (чтобы потоки ждущие ввод/вывод быстрее выполнялись). При ждать могут:
  • диск, cd-rom, параллельный порт, видео — повышение на 1 пункт;
  • сеть, почтовый слот, именованный канал, последовательный порт — повышение на 2 пункта;
  • клавиатура или мышь — повышение на 6 пунктов;
  • звуковая карта — повышение на 8 пунктов.
• когда поток ожидает ресурс, который занят другим потоком, то система может повысить приоритет потока который занял нужный ресурс, чтобы он быстрее выполнил свою работу и освободил этот ресурс;
• повышается приоритет у потоков которые на первом плане, а свёрнутые приложения работают с низким приоритетом.

Эксперимент

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

1. Запустите программу «Блокнот».
2. Запустите «Системный монитор».
3. Щелкните на кнопке панели инструментов «Добавить» (Add Counter).
4. Выберите объект «Поток» (Thread), а затем выберите счетчик «Текущий приоритет» (Priority Current).
5. В поле со списком введите «Notepad», а затем щелкните на кнопке «Поиск» (Search).
6. Найдите строку «Notepad/0». Выберите ее, щелкните на кнопке «Добавить» (Add), а затем щелкните на кнопке «ОК».
7. Как только вы щелкните мышкой по блокноту, то заметите в Системном мониторе, что приоритет у потока «Блокнот» поднялся до 12, если свернуть блокнот то приоритет вновь упадет до 10.

Поток простоя — idle

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

Групповое планирование

Планирование потоков на базе потоков отлично работает, но не способно решить задачу равномерного распределения процессорного времени между несколькими пользователями на терминальном сервере. Потому в Windows Server 2012 появился механизм группового планирования.

Термины группового планирования:

• поколение — период времени, в течении которого отслеживается использование процессора;
• квота — процессорное время, разрешенное группе на поколение (исчерпание квоты означает, что группа израсходовала весь свой бюджет);
• вес — относительная важность группы от 1 до 9 (по умолчанию 5);
• справедливое долевое планирование — вид планирования, при котором потокам исчерпавшим квоту могут выделяться циклы простоя;
• ранг — приоритет групповой политики, 0 — наивысший, чем больше процессорного времени истратила группа, тем больше будет ранг, и с меньшей вероятностью получит процессорное время (ранг всегда превосходит приоритет) (0 ранг у потоков которые: не входят ни в одну группу, не израсходовали квоту, потоки с приоритетами реального времени).

Где же применяется групповое планирование? Например его использует механизм DFSS для справедливого распределения процессорного времени между сеансами на машине. Этот механизм включается по умолчанию при установке роли служб терминалов.

Помимо DFSS групповое планирование применяется в объектах Jobs (Задания), так мы можем ограничить Задание по % потребления CPU, например задание будет потреблять не больше 20% процессорного времени.

Вернуться к оглавлению

Главная / Операционные системы /
Введение во внутреннее устройство Windows / Тест 9

Что такое процесс?

Что такое поток?

Выберите правильные утверждения относительно потоков:

Выберите правильное утверждение относительно многозадачной операционной системы

Операционные системы Windows NT являются…

Многопоточность – это средство …:

В состав структуры EPROCESS входят следующие поля:

За поток в Windows отвечает структура, которая называется …

Указатель на список потоков процесса хранится в структуре …

В ходе создания процесса выполняются следующие этапы:

Файлы с какими расширениями в Windows могут быть исполняемыми?

При создании процесса основной поток …

Выберите правильные утверждения:

В Windows реализован следующий алгоритм планирования потоков:

Характеристикой какого из перечисленных алгоритмов планирования потоков является следующее утверждение: "Активному потоку позволяется выполняться, пока он сам, по собственной инициативе, не отдаст управление операционной системе"?

Что такое приоритет потока?

В Windows процессорное время распределяется между:

Что такое квант?

В Windows поток может покинуть состояние выполнения по следующим причинам:

Какие по длительности кванты используются в клиентских версиях операционных систем Windows и почему?

Выберите состояния, в которых может находиться поток:

Выберите правильное утверждение относительно процессов

Выберите правильное утверждение относительно потоков

Что происходит при завершении кванта времени выполняющегося потока?

   Новые потоки выделяются зеленым, а существующие – красным. (Длительность подсветки настраивается в Options.) Это помогает обнаруживать создание лишних потоков в процессе. (Как правило, потоки должны создаваться при запуске процесса, а не при каждой обработке какого-либо запроса внутри процесса.)
   Когда вы поочередно выбираете потоки в списке, Process Explorer отображает их идентификаторы, время запуска, состояние, счетчики использования процессорного времени, число переключений контекстов, а также базовый и текущий приоритеты. Кнопка KiIl позволяет принудительно завершать индивидуальные потоки, но пользоваться ею следует с крайней осторожностью.
   Разница в числе переключений контекста (context switch delta) отражает, сколько раз потоки начинали работать в течение периода обновления, указанного в Process Explorer. Это еще один способ определения активности потоков. B некоторых отношениях он даже лучше, так как многие потоки выполняются в течение лишь очень короткого времени и поэтому крайне редко попадают в список текущих потоков. Например, если вы добавите столбец с разницей в числе переключений контекстов к тому, что показывается для процесса и отсортируете по этому столбцу, то увидите процессы, в которых потоки выполняются, но используют очень мало процессорного времени или вообще его не используют.
   Стартовый адрес потока выводится в виде
«modulefunction»,где
module –имя EXE или DLL. Имя функции извлекается из файла символов для данного модуля (см. эксперимент «Просмотр детальных сведений о процессах с помощью Process Explorer» в главе 1). Если вы точно не знаете, что это за модуль, нажмите кнопку Module, и появится окно свойств модуля, где содержится данная функция.

    

ПРИМЕЧАНИЕ

Для потоков, созданных Windows-функцией Create-Tbread, Process Explorer показывает функцию, переданную в Create-Tbread, а не истинную стартовую функцию потока. Это связано с тем, что все Windows-потоки запускаются в общей стартовой функции-оболочке для процессов или потоков (BaseProcessStartJin6oBaseThre-adStart в Kernel32.dll). Если бы Process Explorer выводил истинный стартовый адрес, то казалось бы, что большинство потоков в процессе были запущены по одному адресу, а это вряд ли помогло бы понять, какой код выполняется потоком.

    Однако одного стартового адреса потока может оказаться недостаточно для того, чтобы выяснить, что именно делает поток и какой компонент внутри процесса отвечает за использование процессорного времени этим потоком. Это особенно верно, если стартовый адрес потока относится к универсальной стартовой функции (например, если имя функции не указывает на
   то, что делает данный поток). Тогда может помочь изучение стека потока. Для его просмотра дважды щелкните интересующий вас поток (или выберите этот поток и нажмите кнопку Stack). Process Explorer покажет стек потока (пользовательского режима и режима ядра, если поток был в последнем режиме).

    

ПРИМЕЧАНИЕ

Отладчики пользовательского режима (Windbg, Ntsd и Cdb) тоже позволяют подключаться к процессу и просматривать стек потока, но Process Explorer выводит стек как пользовательского режима, так и режима ядра простым нажатием одной кнопки. Стеки пользовательского режима и режима ядра можно
, но эта утилита гораздо сложнее в использовании. Кстати, при работе Windbg в режиме локальной отладки ядра, поддерживаемом только в Windows XP и Windows Server 2003, увидеть содержимое стеков потоков нельзя.

    Просмотр стека потока полезен и при поиске причины зависания процесса. Например, на одной системе Microsoft PowerPoint зависал при запуске на минуту. Чтобы понять причину этого зависания, с помощью Process Explorer изучили стек одного из потоков в процессе. Результат приведен на рис. 6-10.

   Как видите, PowerPoint (строка 10) вызвал функцию в Mso.dll (основной Microsoft Office DLL), которая обратилась к функции
OpenPrinterWBWinspool.drv (DLL, используемой для подключения к принтерам). Затем Winspool.drv пересылает запрос функции
OpenPrinterRPC,а та вызывает функцию в DLL исполняющей среды RPC, сообщая, что запрос посылается удаленному принтеру. Вот так, не зная деталей внутреннего устройства PowerPoint, по именам модулей и функций в стеке потока можно понять, что поток ждет соединения с сетевым принтером. B данной системе был сетевой принтер, который не отвечал, что и объясняет задержку в запуске PowerPoint. (Приложения Microsoft Office соединяются со всеми сконфигурированными принтерами при запуске.) Соединение с тем принтером было удалено из пользовательской системы, и проблема исчезла.

Планирование потоков

   Здесь описываются стратегии и алгоритмы планирования в Windows. B первом разделе этой части материалов рассматриваются принципы планирования в Windows и даются определения ключевых терминов. Уровни приоритета обсуждаются с точки зрения как Windows API, так и ядра. После обзора сопутствующих Windows-функций и утилит подробно анализируются – сначала в однопроцессорных системах, а затем и в многопроцессорных – алгоритмы и структуры данных, используемые подсистемой планирования Windows.

Обзор планирования в Windows

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

    
ЭКСПЕРИМЕНТ: просмотр потоков, готовых к выполнению

   Список потоков, готовых к выполнению, можно увидеть с помощью команды
!readyотладчика ядра. Она выводит поток или список потоков, готовых к выполнению (на каждом уровне приоритета отдельно). B следующем примере к выполнению готовы два потока с приоритетом 10 и шесть потоков – с приоритетом 8. Поскольку эта информация получена в однопроцессорной системе с использованием LiveKd, текущим потоком всегда является отладчик ядра (Kd или WinDbg).

   Выбранный для выполнения поток работает в течение некоего периода, называемого
квантом.Квант определяет, сколько времени будет выполняться поток, пока не наступит очередь другого потока с тем же приоритетом (или более высоким, что возможно в многопроцессорной системе). Длительность квантов зависит от трех факторов: конфигурационных параметров системы (длинные или короткие кванты), статуса процесса (активный или фоновый) и использования объекта «задание» для изменения длительности квантов. (Подробнее о квантах см. раздел «Квант» далее в этой главе.) Однако поток может не полностью использовать свой квант. Поскольку в Windows реализован вытесняющий планировщик, то происходит вот что. Как только другой поток с более высоким приоритетом готов к выполнению, текущий поток вытесняется, даже если его квант еще не истек. Фактически поток может быть выбран следующим для выполнения и вытеснен, не успев воспользоваться своим квантом!
   Код Windows, отвечающий за планирование, реализован в ядре. Поскольку этот код рассредоточен по ядру, единого модуля или процедуры с названием «планировщик» нет. Совокупность процедур, выполняющих эти обязанности, называется
диспетчерам ядра(kernel’s dispatcher). Диспетчеризация потоков может быть вызвана любым из следующих событий.

    
(o)Поток готов к выполнению – например, он только что создан или вышел из состояния ожидания.
   
(o)Поток выходит из состояния Running (выполняется), так как его квант истек или поток завершается либо переходит в состояние ожидания.
   
(o)Приоритет потока изменяется в результате вызова системного сервиса или самой Windows.
   
(o)Изменяется привязка к процессорам, из-за чего поток больше не может работать на процессоре, на котором он выполнялся.

    B любом случае Windows должна определить, какой поток выполнять следующим. Выбрав новый поток, Windows
переключает контекст.Эта операция заключается в сохранении параметров состояния машины, связанных с выполняемым потоком, и загрузке аналогичных параметров для другого потока, после чего начинается выполнение нового потока.
   Как уже говорилось, планирование в Windows осуществляется на уровне потоков. Этот подход станет понятен, если вы вспомните, что сами процессы не выполняются, а лишь предоставляют ресурсы и контекст для выполнения потоков. Поскольку решения, принимаемые в ходе планирования, касаются исключительно потоков, система не обращает внимания на то, какому процессу принадлежит тот или иной поток. Так, если у процесса A есть 10, у процесса B – 2 готовых к выполнению потока, и все 12 имеют одинаковый приоритет, каждый из потоков теоретически получит 1/12 процессорного времени, потому что Windows не станет поровну делить процессорное время между двумя процессами.
   Чтобы понять алгоритмы планирования потоков, вы должны сначала разобраться в уровнях приоритета, используемых Windows.

Уровни приоритета

   Как показано на рис. 6-11, в Windows предусмотрено 32 уровня приоритета – от 0 до 31. Эти значения группируются так:
(o)шестнадцать уровней реального времени (16-31);
(o)пятнадцать варьируемых (динамических) уровней (1-15);

    
(o)один системный уровень (0), зарезервированный для потока обнуления страниц (zero page thread).

   Уровни приоритета потока назначаются с учетом двух разных точек зрения – Windows API и ядра Windows. Windows API сначала упорядочивает процессы по классам приоритета, назначенным при их создании [Real-time (реального времени), High (высокий), Above Normal (выше обычного), Normal (обычный), Below Normal (ниже обычного) и IdIe (простаивающий)], а затем – по относительному приоритету индивидуальных потоков в рамках этих процессов [Time-critical (критичный по времени), Highest (наивысший), Above-normal (выше обычного), Normal (обычный), Below-normal (ниже обычного), Lowest (наименьший) и IdIe (простаивающий)].
   Базовый приоритет каждого потока в Windows API устанавливается, исходя из класса приоритета его процесса и относительного приоритета самого потока. Связь между приоритетами Windows API и внутренними приоритетами ядра Windows (в числовой форме) показана на рис. 6-12.
   Если у процесса только одно значение приоритета (базовое), то у каждого потока их два: текущее и базовое. Решения, связанные с планированием, принимаются на основе текущего приоритета. Как поясняется в следующем разделе, в определенных обстоятельствах система может на короткое время повышать приоритеты потоков в динамическом диапазоне (1-15). Windows никогда не изменяет приоритеты потоков в диапазоне реального времени
(16-31
),поэтому у таких потоков базовый приоритет идентичен текущему.

Рис. 6-12.
Взаимосвязь приоритетов в ядре и Windows API

    Начальный базовый приоритет потока наследуется от базового приоритета процесса, а тот наследует его от родительского процесса. Это поведение можно изменить при вызове Windows-функции
CreateProcess иликоманды START. Приоритет процесса можно изменить и после его создания, используя функцию
SetPriorityClassили различные утилиты, предоставляющие доступ к этой функции через UI, например диспетчер задач и Process Explorer. B частности, вы можете понизить приоритет процесса, интенсивно использующего процессорное время, чтобы он не мешал обычным операциям в системе. Смена приоритета процесса влечет за собой смену приоритетов всех его потоков, но их относительные приоритеты остаются прежними. Ho изменение приоритетов индивидуальных потоков внутри процесса обычно не имеет смысла, потому что вы не знаете, чем именно занимается каждый из них (если только сами не пишете программу или не располагаете исходным кодом); так что изменение относительных приоритетов потоков может привести к неадекватному поведению этого приложения.
   Обычно базовый приоритет процесса (а значит, и базовый приоритет первичного потока) по умолчанию равен значению из середины диапазонов приоритетов процессов (24, 13, 10, 8, 6 или 4). Однако базовый приоритет некоторых системных процессов (например, диспетчера сеансов, контроллера сервисов и сервера локальной аутентификации) несколько превышает значение по умолчанию для класса Normal (8). Более высокий базовый приоритет по умолчанию обеспечивает запуск потоков этих процессов с приоритетом выше 8. Чтобы изменить свой начальный базовый приоритет, такие системные процессы используют внутреннюю функцию
NtSetInformationProcess.

Функции Windows API, связанные с планированием

   Эти функции перечислены в таблице 6-14 (более подробную информацию см. в справочной документации Windows API).

    
Таблица 6-14.
API-функции планирования и их назначение

Сопутствующие утилиты

   B следующей таблице перечислены утилиты, сообщающие информацию о планировании потоков. Базовый приоритет процесса можно увидеть (и изменить) с помощью диспетчера задач, Process Explorer, Pview или Pviewer. Заметьте, что Process Explorer позволяет уничтожать отдельные потоки в любых процессах. Ho, конечно же, этой возможностью следует пользоваться с крайней осторожностью.
   Приоритеты потоков можно просмотреть в оснастке Performance (Производительность), а также с помощью утилит Process Explorer, Plist, Pview, Pviewer и Pstat. Хотя повышение или понижение приоритета процесса может оказаться весьма полезным, изменение приоритетов индивидуальных потоков внутри процесса, как правило, не имеет смысла, потому что постороннему человеку не известно, что делают эти потоки и почему важны именно такие их относительные приоритеты.

   Единственный способ задать начальный класс приоритета для процесса – использовать команду
startв командной строке Windows. Если вы хотите, чтобы некая программа каждый раз запускалась с определенным приоритетом, то можете создать для нее ярлык и указать команду запуска, предварив ее
cmd /с.Это приведет к появлению окна командной строки, выполнению команды и последующему закрытию этого окна. Например, чтобы запустить Notepad в процессе с низким приоритетом, в свойствах ярлыка должна быть задана команда
cmd /с start /low notepad.exe.

    
ЭКСПЕРИМЕНТ: исследуем и задаем приоритеты процессов и потоков

   Попробуйте провести такой эксперимент.
   1. Наберите в командной строке
start /realtime notepad.Ha экране появится окно Notepad.
   2. Запустите утилиту Process Explorer или Process Viewer (Pviewer.exe) из Support Tools и выберите Notepad.exe из списка процессов, как показано ниже. Заметьте, что динамический приоритет потока Notepad равен 24. Это значение совпадает со значением приоритета реального времени на рис. 6-12.

   3. Аналогичную информацию можно получить в диспетчере задач. Для его запуска нажмите клавиши Ctrl+Shift+Esc и перейдите на вкладку Processes (Процессы). Щелкните правой кнопкой мыши процесс Notepad.exe и выберите команду Set Priority (Приоритет). Вы увидите, что класс приоритета потока относится к Realtime (Реального времени), как показано на следующей иллюстрации.

Диспетчер системных ресурсов Windows

   B Windows Server 2003 Enterprise Edition и Windows Server 2003 Data-center Edition включен необязательный компонент, который называется диспетчером системных ресурсов Windows (Windows System Resource Manager, WSRM). Он позволяет администратору настраивать правила политики, указывающие для процессов использование процессорного времени, параметры привязки к процессорам и лимиты на физическую и виртуальную память. Кроме того, WSRM может генерировать отчеты по использованию ресурсов, удобные для учета и проверки уровня обслуживания по договорам с пользователями.
   Такие правила могут быть применены к конкретным приложениям, пользователям или группам и действовать в определенные периоды или постоянно.
   После того как вы сформировали политику выделения ресурсов для управления определенными процессами, служба WSRM будет вести мониторинг потребления ими процессорного времени и регулировать их базовые приоритеты, если эти процессы будут использовать процессорного времени больше или меньше, чем было установлено вами.
   Ограничение физической памяти достигается заданием максимального размера рабочего набора через функцию
SetProcessWorkingSetSizeEx,а ограничение виртуальной памяти реализуется самой службой (о лимитах на объемы физической и виртуальной памяти см. главу 7). Если заданный лимит превышен, WSRM – в зависимости от настроек – может уничтожать процессы или создавать соответствующую запись в журнале событий. Последнее позволяет выявить процесс с утечкой памяти до того, как он займет всю переданную виртуальную память в системе. Заметьте, что лимиты на память, установленные в WSRM, не применяются к памяти Address Windowing Extensions (AWE), памяти больших страниц (large page memory) или памяти ядра (пулу подкачиваемых или неподкачиваемых страниц).

Приоритеты реального времени

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

    

ПРИМЕЧАНИЕ

Как показано на следующей иллюстрации, где изображены уровни запросов прерываний (Interrupt Request Levels, IRQL) на платформе x86, в Windows имеется набор приоритетов, называемых приоритетами реального времени, но они не являются таковыми в общепринятом смысле этого термина, так как Windows не относится к операционным системам реального времени. Подробнее на эту тему см. врезку «Windows и обработка данных в реальном времени» в главе 3, а также статью «Real-Time Systems and Microsoft Windows NT» в MSDN Library.

Уровни прерываний и уровни приоритета

   Как показано на следующей иллюстрации, потоки обычно выполняются при IRQL, равном 0 или 1. (Описание уровней прерываний в Windows см. в главе 3.) Потоки пользовательского режима всегда выполняются при IRQL, равном 0. Ввиду этого ни один поток пользовательского режима независимо от его приоритета не в состоянии блокировать аппаратные прерывания (хотя потоки с высоким приоритетом из диапазона реального времени способны блокировать важные системные потоки). При IRQL, равном 1, работают только APC режима ядра, поскольку они прерывают выполнение потоков (об APC см. главу 3). Кроме того, потоки, выполняемые в режиме ядра, могут повышать IRQL, например при обработке системного вызова, требующего диспетчеризации потоков.

Состояния потоков

   Прежде чем перейти к алгоритмам планирования потоков, вы должны разобраться, в каких состояниях могут находиться потоки в процессе выполнения в Windows 2000 и Windows XR Соответствующая схема дана на рис. 6-13 [числовые значения отражают показатели счетчика производительности Thread: thread state (Поток-. Состояние потока)].

   Вот что представляют собой состояния потока.
   
(o)
Ready (готов)Поток в состоянии готовности ожидает выполнения. Выбирая следующий поток для выполнения, диспетчер принимает во внимание только пул потоков, готовых к выполнению.
   

(o)

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

(o)

Waiting (ожидает)Поток входит в состояние Waiting несколькими способами. Он может самостоятельно начать ожидание на синхронизирующем объекте или его вынуждает к этому подсистема окружения. По окончании ожидания поток – в зависимости от приоритета – либо немедленно начинает выполняться, либо переходит в состояние Ready.
   
(o)
Transition (переходное состояние)Поток переходит в это состояние, если он готов к выполнению, но его стек ядра выгружен из памяти. Как только этот стек загружается в память, поток переходит в состояние Ready.
   
(o)
Terminated (завершен)Заканчивая выполнение, поток переходит в состояние Terminated. После этого блок потока исполнительной системы (структура данных в пуле неподкачиваемой памяти, описывающая данный поток) может быть удален, а может быть и не удален – это уже определяется диспетчером объектов.
   
(o)
Initialized (инициализирован)B это состояние поток входит в процессе своего создания.

    
ЭКСПЕРИМЕНТ: изменение состояний потоков при планировании

   Вы можете понаблюдать за изменением этих состояний с помощью оснастки Performance. Она может оказаться полезной в отладке многопоточных приложений, если вам нужно проверить состояние потоков, выполняемых в вашем процессе.
   1. Запустите стандартную программу Notepad (Блокнот) (Notepad.exe).
   2. Запустите оснастку Performance (Производительность), открыв в меню Start (Пуск) подменю Programs (Программы) и Administrative Tools (Администрирование), а затем выбрав команду Performance (Производительность).
   3. Выберите режим просмотра диаграмм (если установлен какой-то другой).
   4. Щелкните график правой кнопкой мыши и выберите команду Properties (Свойства).
   5. Откройте вкладку Graph (График) и установите максимальное значение вертикальной шкалы равным 7. (Состояниям потоков соответствуют числа от O до 7). Щелкните кнопку ОК.
   6. Щелкните на панели инструментов кнопку Add (Добавить), чтобы открыть диалоговое окно Add Counters (Добавить счетчики).
   7. Выберите в списке объект Thread (Поток), а затем – счетчик Thread State (Состояние потока). Определение его значений вы увидите, щелкнув кнопку Explain (Объяснение), как показано ниже.

   8. Прокрутите список вхождений до строки notepad/O (это процесс Notepad), выделите его и щелкните кнопку Add (Добавить).
   9. Прокрутите список назад до процесса Mmc (это процесс Microsoft Management Console, в котором выполняется ActiveX-элемент System Monitor), выберите все его потоки (mmc/0, mmc/1 и т.д.) и добавьте их на график, щелкнув кнопку Add. Прежде чем щелкнуть кнопку Add, вы должны увидеть диалоговое окно, аналогичное показанному ниже.

   10. Теперь закройте диалоговое окно Add Counters, щелкнув кнопку Close (Закрыть).
   11. Вы должны увидеть, что поток Notepad (верхняя линия графика) находится в состоянии 5. Как вы уже знаете, значение 5 соответствует состоянию Waiting. (B данном случае поток ждет GUI-ввода.)

   12.3аметьте, что один из потоков процесса Mmc (выполняющий оснастку Performance) находится в состоянии Running (значение 2). Этот поток всегда выполняется, так как постоянно запрашивает состояние других потоков.
   13. Вы никогда не увидите процесс Notepad в состоянии Running (если только не используете многопроцессорную систему), поскольку в этом состоянии всегда находится Mmc, собирая данные о состоянии отслеживаемых потоков.
   Схема состояний потоков в Windows Server 2003 показана на рис. 6-14. Обратите внимание на новое состояние Deferred Ready (готов, отложен). Это состояние используется для потоков, выбранных для выполнения на конкретном процессоре, но пока не запланированных к выполнению. Это новое состояние предназначено для того, чтобы ядро могло свести к минимуму срок применения общесистемной блокировки к базе данных планирования (scheduling database). (Этот процесс подробно описывается в разделе «База данных диспетчера ядра в многопроцессорной системе».)

База данных диспетчера ядра

   Для принятия решений при планировании потоков ядро поддерживает набор структур данных, в совокупности известных как
база данных ducnem-чераядра(dispatcher database) (рис. 6-15). Эта база данных позволяет отслеживать потоки, ждущие выполнения, и потоки, выполняемые на тех или иных процессорах.

    

ПРИМЕЧАНИЕ

База данных диспетчера ядра в однопроцессорной системе имеет ту же структуру, что и в многопроцессорных системах Windows 2000 и Windows XP, но отличается от структуры такой базы данных в системах Windows Server 2003. Эти различия, а также иной алгоритм выбора потоков для выполнения в многопроцессорных системах поясняются в разделе «Многопроцессорные системы».

Очереди готовых потоков(ready queues) диспетчера ядра включают потоки в состоянии Ready, ожидающие выделения им процессорного времени. Для каждого из 32 уровней приоритета существует по одной очереди. Для ускорения выбора потока, подлежащего выполнению или вытеснению, Windows поддерживает 32-битную маску, называемую