Страница:
Разделы кода, обращающиеся к неразделяемым ресурсам, называются
критическими секциями(critical sections). B критической секции единовременно может выполняться только один поток. Пока один поток записывает в файл, обновляет базу данных или модифицирует общую переменную, доступ к этому ресурсу со стороны других потоков запрещен. Псевдокод, показанный на рис. 3-23, представляет собой критическую секцию, которая некорректно обращается к разделяемой структуре данных без взаимоисключения.
Взаимоисключение, важное для всех операционных систем, особенно значимо (и запутанно) в случае операционной системы с жестко связанной симметричной мультипроцессорной обработкой(tightly-coupled symmetric multiprocessing), например в Windows, в которой один и тот же системный код, выполняемый на нескольких процессорах одновременно, разделяет некоторые структуры данных, хранящиеся в глобальной памяти. B Windows поддержка механизмов, с помощью которых системный код может предотвратить одновременное изменение двумя потоками одной и той же структуры, возлагается на ядро. Оно предоставляет специальные примитивы взаимоисключения, используемые им и остальными компонентами исполнительной системы для синхронизации доступа к глобальным структурам данных.
Так как планировщик синхронизирует доступ к своим структурам данных при IRQL уровня «DPC/dispatch», ядро и исполнительная система не могут полагаться на механизмы синхронизации, которые могли бы привести к ошибке страницы или к перераспределению процессорного времени при IRQL уровня «DPC/dispatch» или выше (эти уровни также известны под названием «высокий IRQL»). Из следующих разделов вы узнаете, как ядро и исполнительная система используют взаимоисключение для защиты своих глобальных структур данных при высоком IRQL и какие механизмы синхронизации и взаимоисключения они применяют при низких уровнях IRQL (ниже «DPC/dispatch»).
Ядро должно гарантировать, что в каждый момент только один процессор выполняет код в критической секции. Критическими секциями ядра являются разделы кода, модифицирующие глобальные структуры данных, например базу данных диспетчера ядра или его очередь DPC Операционная система не смогла бы корректно работать, если бы ядро не гарантировало взаимоисключающий доступ потоков к этим структурам данных.
B этом плане больше всего проблем с прерываниями. Так, в момент обновления ядром глобальной структуры данных может возникнуть прерывание, процедура обработки которого изменяет ту же структуру. B простых однопроцессорных системах развитие событий по такому сценарию исключается путем отключения всех прерываний на время доступа к глобальным данным, однако в ядре Windows реализовано более сложное решение. Перед использованием глобального ресурса ядро временно маскирует прерывания, обработчики которых используют тот же ресурс. Для этого ядро повышает IRQL процессора до самого высокого уровня, используемого любым потенциальным источником прерываний, который имеет доступ к глобальным данным. Например, прерывание на уровне «DPC/dispatch» приводит к запуску диспетчера ядра, использующего диспетчерскую базу данных. Следовательно, любая другая часть ядра, имеющая дело с этой базой данных, повышает IRQL до уровня «DPC/dispatch», маскируя прерывания того же уровня перед обращением к диспетчерской базе данных.
Эта стратегия хорошо работает в однопроцессорных системах, но не годится для многопроцессорных конфигураций. Повышение IRQL на одном из процессоров не исключает прерываний на другом процессоре, а ядро должно гарантировать взаимоисключающий доступ на всех процессорах.
Простейшая форма механизмов синхронизации опирается на аппаратную поддержку безопасных операций над целыми значениями и выполнения сравнений в многопроцессорной среде. Сюда относятся такие функции, как InterlockedIncrement, InterlockedDecrement, InterlockedExcbangeи Interlocked-CompareExchange.Скажем, функция InterlockedDecrement,использует префикс х86-инструкции lock(например, lock xadd)для блокировки многопроцессорной шины на время операции вычитания, чтобы другой процессор, модифицирующий тот же участок памяти, не смог выполнить свою операцию в момент между чтением исходных данных и записью их нового (меньшего) значения. Эта форма базовой синхронизации используется ядром и драйверами.
Механизм, применяемый ядром для взаимоисключения в многопроцессорных системах, называется спин-блокировкой(spinlock). Спин-блокировка - это блокирующий примитив, сопоставленный с какой-либо глобальной структурой данных вроде очереди DPC (рис. 3-24).
Перед входом в любую из критических секций, показанных на рис. 3-24, ядро должно установить спин-блокировку, связанную с защищенной очередью DPC Если спин-блокировка пока занята, ядро продолжает попытки установить спин-блокировку до тех пор, пока не достигнет успеха. Термин получил такое название из-за поведения ядра (и соответственно процессора), которое «крутится» (spin) в цикле, повторяя попытки, пока не захватит блокировку.
Спин-блокировки, как и защищаемые ими структуры данных, находятся в глобальной памяти. Код для их установки и снятия написан на языке ассемблера для максимального быстродействия. Bo многих архитектурах спин-блокировка реализуется аппаратно поддерживаемой командой test-and-set, которая проверяет значение переменной блокировки и устанавливает блокировку, выполняя всего одну атомарную команду. Это предотвращает захват блокировки вторым потоком в промежуток между проверкой переменной и установкой блокировки первым потоком.
Всем спин-блокировкам режима ядра в Windows назначен IRQL, всегда соответствующий уровню «DPC/dispatch» или выше. Поэтому, когда поток пытается установить спин-блокировку, все действия на этом или более низком уровне IRQL на данном процессоре прекращаются. Поскольку диспетчеризация потоков осуществляется при уровне «DPC/dispatch», поток, удерживающий спин-блокировку, никогда не вытесняется, так какданный IRQL маскирует механизмы диспетчеризации. Такая маскировка не дает прервать выполнение критической секции кода под защитой спин-блокировки и обеспечивает быстрое ее снятие. Спин-блокировки используются в ядре с большой осторожностью и устанавливаются на минимально возможное время.
ПРИМЕЧАНИЕ Поскольку IRQL - достаточно эффективный механизм синхронизации для однопроцессорных систем, функции установки и снятия спин-блокировки в однопроцессорных версиях HAL на самом деле просто повышают и понижают IRQL.
Ядро предоставляет доступ к спин-блокировкам другим компонентам исполнительной системы через набор функций ядра, включающий KeAcqui-reSpinlockи KeReleaseSpinlock.Например, драйверы устройств требуют спин-блокировки, чтобы система гарантировала единовременный доступ к регистрам устройства и другим глобальным структурам данных со стороны лишь одной части драйвера (и только с одного процессора). Спин-блокировка не предназначена для пользовательских программ - они должны оперировать объектами, которые рассматриваются в следующем разделе.
Спин-блокировки ядра накладывают ограничения на использующий их код. Как уже отмечалось, их IRQL всегда равен «DPC/dispatch», поэтому установивший спин-блокировку код может привести к краху системы, если попытается заставить планировщик выполнить операцию диспетчеризации или вызовет ошибку страницы.
B некоторых ситуациях вместо стандартной спин-блокировки применяется особый тип спин-блокировки - с очередью (queued spinlock). Спин-блокировка с очередью лучше масштабируется в многопроцессорных системах, чем стандартная. Как правило, Windows использует лишь стандартные спин-блокировки, когда конкуренция за спин-блокировку ожидается низкой.
Спин-блокировка с очередью работает так: процессор, пытаясь установить такую спин-блокировку, которая в данный момент занята, ставит свой идентификатор в очередь, сопоставленную с этой спин-блокировкой. Освободив спин-блокировку, удерживавший ее процессор передает блокировку тому процессору, чей идентификатор стоит в очереди первым. Между тем процессор, ожидающий занятую спин-блокировку, проверяет статус не самой спин-блокировки, а флага того процессора, чей идентификатор располагается в очереди прямо перед идентификатором ждущего процессора.
Тот факт, что спин-блокировка с очередью устанавливает флаги, а не глобальные блокировки, имеет два следствия. Во-первых, уменьшается интенсивный трафик, связанный с межпроцессорной синхронизацией. Во-вторых, вместо случайного выбора процессора из группы ожидающих спин-блокировку реализуется четкий порядок спин-блокировки по типу FIFO («первым вошел, первым вышел»). Такой порядок позволяет достичь более согласованной работы процессоров, использующих одну и ту же блокировку.
Windows определяет ряд глобальных спин-блокировок с очередями, сохраняя указатели на них в массиве, который содержится в блоке PCR (processor control region) каждого процессора. Глобальную спин-блокировку можно получить вызовом KeAcquireQueuedSpinlockс индексом в массиве PCR, по которому сохранен указатель на эту спин-блокировку. Количество глобальных спин-блокировок растет по мере появления новых версий операционной системы, и таблица их индексов публикуется в заголовочном файле Ntddk.h, поставляемом с DDK.
ЭКСПЕРИМЕНТ: просмотр глобальных спин-блокировок с очередями
Вы можете наблюдать за состоянием глобальных спин-блокировок с очередями, используя команду !qlockотладчика ядра. Эта команда имеет смысл лишь в многопроцессорной системе, так как в однопроцессорной версии HAL спин-блокировки не реализованы. B следующем примере (подготовленном в Windows 2000) спин-блокировка с очередью для базы данных диспетчера ядра удерживается процессором номер 1, а остальные спин-блокировки этого типа не затребованы (о базе данных диспетчера ядра см. главу 6).
Помимо статических спин-блокировок с очередями, определяемых глобально, ядра Windows XP и Windows Server 2003 поддерживают динамически создаваемые спин-блокировки с очередями. Для их создания предназначены функции KeAcquireInStackQueuedSpinlockи KeReleaseInStackQueuedSpin-lock.Этот тип блокировок используется несколькими компонентами, в том числе диспетчером кэша, диспетчером пулов исполнительной системы (executive pool manager) и NTFS. Упомянутые функции документированы в DDK для сторонних разработчиков драйверов.
KeAcquireInStackQueuedSpinlockпринимает указатель на структуру данных спин-блокировки и описатель очереди спин-блокировки. Этот описатель в действительности является структурой данных, в которой ядро хранит информацию о состоянии блокировки, в частности сведения о владельце блокировки и об очереди процессоров, ожидающих освобождения этой блокировки.
Ядро предоставляет ряд функций синхронизации, использующих спин-блокировки для более сложных операций, например для добавления и удаления элементов из одно- и двунаправленных связанных списков. K таким функциям, в частности, относятся ExfoterlockedPopEntryList и ExInterlockedPushEntryList (для однонаправленных связанных списков), ExInterlockedInsertHeadList и ExInter-lockedRemoveHeadList (ддя двунаправленных связанных списков). Все эти функции требуют передачи стандартной спин-блокировки в качестве параметра и интенсивно используются в ядре и драйверах устройств.
Компоненты исполнительной системы вне ядра также нуждаются в синхронизации доступа к глобальным структурам данных в многопроцессорной среде. Например, у диспетчера памяти есть только одна база данных блоков страниц. Обращение к ней осуществляется как к глобальной структуре данных, и драйверам устройств необходима гарантия получения монопольного доступа к своим устройствам. Вызывая функции ядра, исполнительная система может создать спин-блокировку, установить ее и снять.
Однако спин-блокировка лишь частично удовлетворяет потребности исполнительной системы в синхронизации. Поскольку спин-блокировка означает фактическую остановку процессора, она применяется только при двух условиях:
(o)требуется непродолжительное обращение к защищенным ресурсам без сложного взаимодействия с другим кодом;
(o)код критической секции нельзя выгрузить в страничный файл, он не ссылается на данные в подкачиваемой памяти, не вызывает внешние процедуры (включая системные сервисы) и не генерирует прерывания или исключения.
Эти противоречащие друг другу ограничения нельзя соблюсти одновременно ни при каких обстоятельствах. Более того, кроме взаимоисключения, исполнительная система должна выполнять и другие алгоритмы синхронизации, а также предоставлять механизмы синхронизации пользовательскому режиму.
Существует несколько дополнительных механизмов синхронизации, применяемых, когда спин-блокировки не годятся:
(o)объекты диспетчера ядра (kernel dispatcher objects);
(o)быстрые мьютексы (fast mutexes) и защищенные мьютексы (guarded mu-texes);
(o)блокировки с заталкиванием указателя (push locks);
(o)ресурсы исполнительной системы (executive resources).
B таблице 3-9 кратко сравниваются возможности этих механизмов и их взаимосвязь с доставкой APC режима ядра.
Ядро предоставляет исполнительной системе дополнительные механизмы синхронизации в форме объектов, в совокупности известных как объекты диспетчера ядра. Синхронизирующие объекты, видимые из пользовательского режима, берут свое начало именно от этих объектов диспетчера ядра. Каждый синхронизирующий объект, видимый из пользовательского режима, инкапсулирует минимум один объект диспетчера ядра. Семантика синхронизации исполнительной системы доступна программистам через Windows-функции WaitForSingleObjectи WaitForMultipleObjects,реализуемые подсистемой Windows на основе аналогичных системных сервисов, предоставляемых диспетчером объектов. Поток в Windows-приложении можно синхронизировать по таким Windows-объектам, как процесс, поток, событие, семафор, мьютекс, ожидаемый таймер, порт завершения ввода-вывода или файл.
Еще один тип синхронизирующих объектов исполнительной системы назван (без особой на то причины) ресурсами исполнительной системы(executive resources). Эти ресурсы обеспечивают как монопольный доступ (по аналогии с мьютексами), так и разделяемый доступ для чтения (когда несколько потоков-«читателей» обращается к одной структуре только для чтения). Однако они доступны лишь коду режима ядра, а значит, недоступны через Windows API. Ресурсы исполнительной системы являются не объектами диспетчера ядра, а скорее структурами данных, память для которых выделяется прямо из неподкачиваемого пула, имеющего свои специализированные сервисы для инициализации, блокировки, освобождения, запроса и ожидания. Структура ресурсов исполнительной системы определена в Ntddk.h, а соответствующие процедуры описаны в DDK.
B остальных подразделах мы детально обсудим, как реализуется ожидание на объектах диспетчера ядра.
Поток синхронизируется с объектом диспетчера ядра, ожидая освобождения его описателя. При этом ядро приостанавливает поток и соответственно меняет состояние диспетчера, как показано на рис. 3-25. Ядро удаляет поток из очереди готовых к выполнению потоков и перестает учитывать его в планировании.
ПРИМЕЧАНИЕ Ha рис. 3-25 показана схема перехода состояний с выделением состояний «готов» (ready), «ожидает» (waiting) и «выполняется» (running) - они относятся к ожиданию на объектах. Прочие состояния описываются в главе 6.
B любой момент синхронизирующий объект находится в одном из двух состояний:
свободном(signaled) или
занятом(nonsignaled). Для синхронизации с объектом поток вызывает один из системных сервисов ожидания, предоставляемых диспетчером объектов, и передает описатель этого объекта. Поток может ожидать на одном или нескольких объектах, а также указать, что ожидание следует прекратить, если объект (или объекты) не освободился в течение определенного времени. Всякий раз, когда ядро переводит объект в свободное состояние, функция
KiWaitTestядра проверяет, ждут ли этот объект какие-нибудь потоки и не ждут ли они каких-либо других объектов. Если да, ядро выводит один или более потоков из состояния ожидания, после чего их выполнение может быть продолжено.
Взаимосвязь синхронизации с диспетчеризацией потоков иллюстрирует следующий пример с использованием объекта «событие».
(o)Поток пользовательского режима ждет на описателе объекта «событие» (т. е. ждет перехода этого объекта в свободное состояние).
(o)Ядро изменяет состояние потока с «готов» на «ожидает» и добавляет его в список потоков, ждущих объект «событие».
(o)Другой поток устанавливает объект «событие».
(o)Ядро просматривает список потоков, ожидающих этот объект. Если условия ожидания какого-либо потока выполнены (см. примечание ниже), ядро переводит его из состояния «ожидает» в состояние «готов». Если это поток с динамическим приоритетом, ядро может повысить его приоритет для выполнения.
(o)Поскольку новый поток теперь готов к выполнению, происходит перераспределение процессорного времени. Если при этом диспетчер обнаружит, что приоритет выполняемого потока ниже, чем приоритет потока, только что перешедшего в состояние «готов», он вытеснит поток с более низким приоритетом и выдаст программное прерывание для инициации переключения контекста на поток с более высоким приоритетом.
(o)Если в данный момент вытеснение невозможно ни на одном из процессоров, диспетчер включает поток в свою очередь потоков, готовых к выполнению.
ПРИМЕЧАНИЕ Некоторые потоки могут ждать более одного объекта, и в таком случае их ожидание продолжается.
Эти условия различны для разных объектов. Например, объект «поток» находится в занятом состоянии в течение всего срока своей жизни и переводится ядром в свободное состояние лишь при завершении. Аналогичным образом, ядро переводит объект «процесс» в свободное состояние в момент завершения последнего потока процесса. Ho такой объект, как таймер, переводится в свободное состояние по истечении заданного времени.
Выбирая механизм синхронизации, вы должны учитывать в своей программе поведение синхронизирующих объектов. B таблице 3-10 показано, когда переходят в свободное состояние синхронизирующие объекты различных типов.
Когда объект переводится в свободное состояние, ожидающие его потоки обычно немедленно выходят из ждущего состояния. Однако, как показано на рис. 3-26, некоторые объекты диспетчера ядра и системные события ведут себя иначе.
Например, объект «событие уведомления» - в Windows API он называется событием со сбросом вручную (manual reset event) - используется для уведомления о каком-либо событии. Когда этот объект переводится в свободное состояние, все потоки, ожидающие его, освобождаются. Исключением является тот поток, который ждет сразу несколько объектов: он может продолжать ожидание, пока не освободятся дополнительные объекты.
B отличие от события мьютекс предусматривает возможность владения. Этот объект используется для взаимоисключающего доступа к ресурсу, поэтому единовременно только один поток может владеть мьютексом. При освобождении мьютекса ядро переводит его в свободное состояние и выбирает для выполнения один из ожидающих потоков. Выбранный ядром поток захватывает мьютекс, а остальные потоки остаются в ожидании.
Синхронизирующий объект, впервые появившийся в Windows XP и названный событием с ключом(keyed event), заслуживает особого упоминания. Он помогает процессам справляться с нехваткой памяти при использовании критических секций. Это недокументированное событие позволяет потоку указать «ключ» в следующей ситуации-, данный поток должен пробуждаться, когда другой поток того же процесса освобождает событие с тем же ключом.
Windows-процессы часто используют функции критических секций - EnterCriticalSectionи LeaveCriticalSection- для синхронизации доступа потоков к личным ресурсам процесса. Вызовы этих функций эффективнее прямого обращения к объектам «мьютекс», так как в отсутствие конкуренции они не заставляют переходить в режим ядра. При наличии конкуренции EnterCriticalSectionдинамически создает объект «событие», и поток, которому нужно захватить критическую секцию, ждет, когда поток, владеющий этой секцией, освободит ее вызовом LeaveCriticalSection.
Если создать объект «событие» для критической секции не удалось из-за нехватки системной памяти, EnterCriticalSectionиспользует глобальное событие с ключом - CritSecOutOjMemoryEvent(в каталоге \Ker-nel пространства имен диспетчера объектов). Если EnterCritica amp;ectionвынуждена задействовать CritSecOutOjMemoryEventвместо стандартного события, поток, ждущий критическую секцию, использует адрес этой секции как ключ. Это обеспечивает корректную работу функций критических секций даже в условиях временной нехватки памяти.
Мы не ставили себе задачу исчерпывающе описать все объекты исполнительной системы, а лишь хотели дать представление об их базовой функциональности и механизмах синхронизации. Об использовании этих объектов в Windows-программах см. справочную документацию Windows или четвертое издание книги Джеффри Рихтера «Windows для профессионалов».
Учет ожидающих потоков и их объектов ожидания базируется на двух ключевых структурах данных: заголовках диспетчера (dispatcher headers) и блоках ожидания (wait blocks). Обе эти структуры определены в Ntddk.h, заголовочном файле DDK. Для удобства мы воспроизводим здесь эти определения.
Заголовок диспетчера содержит тип объекта, информацию о состоянии (занят/свободен) и список потоков, ожидающих этот объект. У каждого ждущего потока есть список блоков ожидания, где перечислены ожидаемые потоком объекты, а у каждого объекта диспетчера ядра - список блоков ожидания, где перечислены ожидающие его потоки. Этот список ведется так, что при освобождении объекта диспетчера ядро может быстро определить, кто ожидает данный объект. B блоке ожидания имеются указатели на объект ожидания, ожидающий поток и на следующий блок ожидания (если поток ждет более одного объекта). Он также регистрирует тип ожидания («любой» или «все») и позицию соответствующего элемента в таблице описателей, переданную потоком в функцию
WaitForMultipleObjects(позиция 0 - если поток ожидает лишь один объект).
Ha рис. 3-27 показана связь объектов диспетчера ядра с блоками ожидания потоков. B данном примере поток 1 ждет объект В, а поток 2 - объекты A и В. Если объект A освободится, поток 2 не сможет возобновить свое выполнение, так как ядро обнаружит, что он ждет и другой объект. C другой стороны, при освобождении объекта B ядро сразу же подготовит поток 1 к выполнению, поскольку он не ждет никакие другие объекты.
ЭКСПЕРИМЕНТ: просмотр очередей ожидания
Хотя многие утилиты просмотра процессов умеют определять, находится ли поток в состоянии ожидания (отмечая в этом случае и тип ожидания), список объектов, ожидаемых потоком, можно увидеть только с помощью команды !processотладчика ядра. Например, следующий фрагмент вывода команды !processпоказывает, что поток ждет на объекте-событии.
Эти данные позволяют нам убедиться в отсутствии других потоков, ожидающих данный объект, поскольку указатели начала и конца списка ожидания указывают на одно и то же место (на один блок ожидания). Копия блока ожидания (по адресу 0x8a12a398) дает следующее:
Если в списке ожидания более одного элемента, вы можете выполнить ту же команду со вторым указателем в поле
WaitListEntryкаждого блока ожидания (команду
!threadприменительно к указателю потока в блоке ожидания) для прохода по списку и просмотра других потоков, ждущих данный объект.
Быстрые мьютексы(fast mutexes), также известные как мьютексы исполнительной системы, обычно обеспечивают более высокую производительность, чем объекты «мьютекс». Почему? Дело в том, что быстрые мьютексы, хоть и построены на объектах событий диспетчера, в отсутствие конкуренции не требуют ожидания объекта «событие» (и соответственно спин-блокировок, на которых основан этот объект). Эти преимущества особенно ярко проявляются в многопроцессорной среде. Быстрые мьютексы широко используются в ядре и драйверах устройств.
Однако быстрые мьютексы годятся, только если можно отключить доставку обычных APC режима ядра. B исполнительной системе определены две функции для захвата быстрых мьютексов:
Взаимоисключение, важное для всех операционных систем, особенно значимо (и запутанно) в случае операционной системы с жестко связанной симметричной мультипроцессорной обработкой(tightly-coupled symmetric multiprocessing), например в Windows, в которой один и тот же системный код, выполняемый на нескольких процессорах одновременно, разделяет некоторые структуры данных, хранящиеся в глобальной памяти. B Windows поддержка механизмов, с помощью которых системный код может предотвратить одновременное изменение двумя потоками одной и той же структуры, возлагается на ядро. Оно предоставляет специальные примитивы взаимоисключения, используемые им и остальными компонентами исполнительной системы для синхронизации доступа к глобальным структурам данных.
Так как планировщик синхронизирует доступ к своим структурам данных при IRQL уровня «DPC/dispatch», ядро и исполнительная система не могут полагаться на механизмы синхронизации, которые могли бы привести к ошибке страницы или к перераспределению процессорного времени при IRQL уровня «DPC/dispatch» или выше (эти уровни также известны под названием «высокий IRQL»). Из следующих разделов вы узнаете, как ядро и исполнительная система используют взаимоисключение для защиты своих глобальных структур данных при высоком IRQL и какие механизмы синхронизации и взаимоисключения они применяют при низких уровнях IRQL (ниже «DPC/dispatch»).
Синхронизация ядра при высоком IRQL
Ядро должно гарантировать, что в каждый момент только один процессор выполняет код в критической секции. Критическими секциями ядра являются разделы кода, модифицирующие глобальные структуры данных, например базу данных диспетчера ядра или его очередь DPC Операционная система не смогла бы корректно работать, если бы ядро не гарантировало взаимоисключающий доступ потоков к этим структурам данных.
B этом плане больше всего проблем с прерываниями. Так, в момент обновления ядром глобальной структуры данных может возникнуть прерывание, процедура обработки которого изменяет ту же структуру. B простых однопроцессорных системах развитие событий по такому сценарию исключается путем отключения всех прерываний на время доступа к глобальным данным, однако в ядре Windows реализовано более сложное решение. Перед использованием глобального ресурса ядро временно маскирует прерывания, обработчики которых используют тот же ресурс. Для этого ядро повышает IRQL процессора до самого высокого уровня, используемого любым потенциальным источником прерываний, который имеет доступ к глобальным данным. Например, прерывание на уровне «DPC/dispatch» приводит к запуску диспетчера ядра, использующего диспетчерскую базу данных. Следовательно, любая другая часть ядра, имеющая дело с этой базой данных, повышает IRQL до уровня «DPC/dispatch», маскируя прерывания того же уровня перед обращением к диспетчерской базе данных.
Эта стратегия хорошо работает в однопроцессорных системах, но не годится для многопроцессорных конфигураций. Повышение IRQL на одном из процессоров не исключает прерываний на другом процессоре, а ядро должно гарантировать взаимоисключающий доступ на всех процессорах.
Взаимоблокирующие операции
Простейшая форма механизмов синхронизации опирается на аппаратную поддержку безопасных операций над целыми значениями и выполнения сравнений в многопроцессорной среде. Сюда относятся такие функции, как InterlockedIncrement, InterlockedDecrement, InterlockedExcbangeи Interlocked-CompareExchange.Скажем, функция InterlockedDecrement,использует префикс х86-инструкции lock(например, lock xadd)для блокировки многопроцессорной шины на время операции вычитания, чтобы другой процессор, модифицирующий тот же участок памяти, не смог выполнить свою операцию в момент между чтением исходных данных и записью их нового (меньшего) значения. Эта форма базовой синхронизации используется ядром и драйверами.
Спин-блокировки
Механизм, применяемый ядром для взаимоисключения в многопроцессорных системах, называется спин-блокировкой(spinlock). Спин-блокировка - это блокирующий примитив, сопоставленный с какой-либо глобальной структурой данных вроде очереди DPC (рис. 3-24).
Спин-блокировки, как и защищаемые ими структуры данных, находятся в глобальной памяти. Код для их установки и снятия написан на языке ассемблера для максимального быстродействия. Bo многих архитектурах спин-блокировка реализуется аппаратно поддерживаемой командой test-and-set, которая проверяет значение переменной блокировки и устанавливает блокировку, выполняя всего одну атомарную команду. Это предотвращает захват блокировки вторым потоком в промежуток между проверкой переменной и установкой блокировки первым потоком.
Всем спин-блокировкам режима ядра в Windows назначен IRQL, всегда соответствующий уровню «DPC/dispatch» или выше. Поэтому, когда поток пытается установить спин-блокировку, все действия на этом или более низком уровне IRQL на данном процессоре прекращаются. Поскольку диспетчеризация потоков осуществляется при уровне «DPC/dispatch», поток, удерживающий спин-блокировку, никогда не вытесняется, так какданный IRQL маскирует механизмы диспетчеризации. Такая маскировка не дает прервать выполнение критической секции кода под защитой спин-блокировки и обеспечивает быстрое ее снятие. Спин-блокировки используются в ядре с большой осторожностью и устанавливаются на минимально возможное время.
ПРИМЕЧАНИЕ Поскольку IRQL - достаточно эффективный механизм синхронизации для однопроцессорных систем, функции установки и снятия спин-блокировки в однопроцессорных версиях HAL на самом деле просто повышают и понижают IRQL.
Ядро предоставляет доступ к спин-блокировкам другим компонентам исполнительной системы через набор функций ядра, включающий KeAcqui-reSpinlockи KeReleaseSpinlock.Например, драйверы устройств требуют спин-блокировки, чтобы система гарантировала единовременный доступ к регистрам устройства и другим глобальным структурам данных со стороны лишь одной части драйвера (и только с одного процессора). Спин-блокировка не предназначена для пользовательских программ - они должны оперировать объектами, которые рассматриваются в следующем разделе.
Спин-блокировки ядра накладывают ограничения на использующий их код. Как уже отмечалось, их IRQL всегда равен «DPC/dispatch», поэтому установивший спин-блокировку код может привести к краху системы, если попытается заставить планировщик выполнить операцию диспетчеризации или вызовет ошибку страницы.
Спин-блокировки с очередями
B некоторых ситуациях вместо стандартной спин-блокировки применяется особый тип спин-блокировки - с очередью (queued spinlock). Спин-блокировка с очередью лучше масштабируется в многопроцессорных системах, чем стандартная. Как правило, Windows использует лишь стандартные спин-блокировки, когда конкуренция за спин-блокировку ожидается низкой.
Спин-блокировка с очередью работает так: процессор, пытаясь установить такую спин-блокировку, которая в данный момент занята, ставит свой идентификатор в очередь, сопоставленную с этой спин-блокировкой. Освободив спин-блокировку, удерживавший ее процессор передает блокировку тому процессору, чей идентификатор стоит в очереди первым. Между тем процессор, ожидающий занятую спин-блокировку, проверяет статус не самой спин-блокировки, а флага того процессора, чей идентификатор располагается в очереди прямо перед идентификатором ждущего процессора.
Тот факт, что спин-блокировка с очередью устанавливает флаги, а не глобальные блокировки, имеет два следствия. Во-первых, уменьшается интенсивный трафик, связанный с межпроцессорной синхронизацией. Во-вторых, вместо случайного выбора процессора из группы ожидающих спин-блокировку реализуется четкий порядок спин-блокировки по типу FIFO («первым вошел, первым вышел»). Такой порядок позволяет достичь более согласованной работы процессоров, использующих одну и ту же блокировку.
Windows определяет ряд глобальных спин-блокировок с очередями, сохраняя указатели на них в массиве, который содержится в блоке PCR (processor control region) каждого процессора. Глобальную спин-блокировку можно получить вызовом KeAcquireQueuedSpinlockс индексом в массиве PCR, по которому сохранен указатель на эту спин-блокировку. Количество глобальных спин-блокировок растет по мере появления новых версий операционной системы, и таблица их индексов публикуется в заголовочном файле Ntddk.h, поставляемом с DDK.
ЭКСПЕРИМЕНТ: просмотр глобальных спин-блокировок с очередями
Вы можете наблюдать за состоянием глобальных спин-блокировок с очередями, используя команду !qlockотладчика ядра. Эта команда имеет смысл лишь в многопроцессорной системе, так как в однопроцессорной версии HAL спин-блокировки не реализованы. B следующем примере (подготовленном в Windows 2000) спин-блокировка с очередью для базы данных диспетчера ядра удерживается процессором номер 1, а остальные спин-блокировки этого типа не затребованы (о базе данных диспетчера ядра см. главу 6).
Внутристековые спин-блокировки с очередями
Помимо статических спин-блокировок с очередями, определяемых глобально, ядра Windows XP и Windows Server 2003 поддерживают динамически создаваемые спин-блокировки с очередями. Для их создания предназначены функции KeAcquireInStackQueuedSpinlockи KeReleaseInStackQueuedSpin-lock.Этот тип блокировок используется несколькими компонентами, в том числе диспетчером кэша, диспетчером пулов исполнительной системы (executive pool manager) и NTFS. Упомянутые функции документированы в DDK для сторонних разработчиков драйверов.
KeAcquireInStackQueuedSpinlockпринимает указатель на структуру данных спин-блокировки и описатель очереди спин-блокировки. Этот описатель в действительности является структурой данных, в которой ядро хранит информацию о состоянии блокировки, в частности сведения о владельце блокировки и об очереди процессоров, ожидающих освобождения этой блокировки.
Взаимоблокирующие операции в исполнительной системе
Ядро предоставляет ряд функций синхронизации, использующих спин-блокировки для более сложных операций, например для добавления и удаления элементов из одно- и двунаправленных связанных списков. K таким функциям, в частности, относятся ExfoterlockedPopEntryList и ExInterlockedPushEntryList (для однонаправленных связанных списков), ExInterlockedInsertHeadList и ExInter-lockedRemoveHeadList (ддя двунаправленных связанных списков). Все эти функции требуют передачи стандартной спин-блокировки в качестве параметра и интенсивно используются в ядре и драйверах устройств.
Синхронизация при низком IRQL
Компоненты исполнительной системы вне ядра также нуждаются в синхронизации доступа к глобальным структурам данных в многопроцессорной среде. Например, у диспетчера памяти есть только одна база данных блоков страниц. Обращение к ней осуществляется как к глобальной структуре данных, и драйверам устройств необходима гарантия получения монопольного доступа к своим устройствам. Вызывая функции ядра, исполнительная система может создать спин-блокировку, установить ее и снять.
Однако спин-блокировка лишь частично удовлетворяет потребности исполнительной системы в синхронизации. Поскольку спин-блокировка означает фактическую остановку процессора, она применяется только при двух условиях:
(o)требуется непродолжительное обращение к защищенным ресурсам без сложного взаимодействия с другим кодом;
(o)код критической секции нельзя выгрузить в страничный файл, он не ссылается на данные в подкачиваемой памяти, не вызывает внешние процедуры (включая системные сервисы) и не генерирует прерывания или исключения.
Эти противоречащие друг другу ограничения нельзя соблюсти одновременно ни при каких обстоятельствах. Более того, кроме взаимоисключения, исполнительная система должна выполнять и другие алгоритмы синхронизации, а также предоставлять механизмы синхронизации пользовательскому режиму.
Существует несколько дополнительных механизмов синхронизации, применяемых, когда спин-блокировки не годятся:
(o)объекты диспетчера ядра (kernel dispatcher objects);
(o)быстрые мьютексы (fast mutexes) и защищенные мьютексы (guarded mu-texes);
(o)блокировки с заталкиванием указателя (push locks);
(o)ресурсы исполнительной системы (executive resources).
B таблице 3-9 кратко сравниваются возможности этих механизмов и их взаимосвязь с доставкой APC режима ядра.
Объекты диспетчера ядра
Ядро предоставляет исполнительной системе дополнительные механизмы синхронизации в форме объектов, в совокупности известных как объекты диспетчера ядра. Синхронизирующие объекты, видимые из пользовательского режима, берут свое начало именно от этих объектов диспетчера ядра. Каждый синхронизирующий объект, видимый из пользовательского режима, инкапсулирует минимум один объект диспетчера ядра. Семантика синхронизации исполнительной системы доступна программистам через Windows-функции WaitForSingleObjectи WaitForMultipleObjects,реализуемые подсистемой Windows на основе аналогичных системных сервисов, предоставляемых диспетчером объектов. Поток в Windows-приложении можно синхронизировать по таким Windows-объектам, как процесс, поток, событие, семафор, мьютекс, ожидаемый таймер, порт завершения ввода-вывода или файл.
Еще один тип синхронизирующих объектов исполнительной системы назван (без особой на то причины) ресурсами исполнительной системы(executive resources). Эти ресурсы обеспечивают как монопольный доступ (по аналогии с мьютексами), так и разделяемый доступ для чтения (когда несколько потоков-«читателей» обращается к одной структуре только для чтения). Однако они доступны лишь коду режима ядра, а значит, недоступны через Windows API. Ресурсы исполнительной системы являются не объектами диспетчера ядра, а скорее структурами данных, память для которых выделяется прямо из неподкачиваемого пула, имеющего свои специализированные сервисы для инициализации, блокировки, освобождения, запроса и ожидания. Структура ресурсов исполнительной системы определена в Ntddk.h, а соответствующие процедуры описаны в DDK.
B остальных подразделах мы детально обсудим, как реализуется ожидание на объектах диспетчера ядра.
Ожидание на объектах диспетчера ядра
Поток синхронизируется с объектом диспетчера ядра, ожидая освобождения его описателя. При этом ядро приостанавливает поток и соответственно меняет состояние диспетчера, как показано на рис. 3-25. Ядро удаляет поток из очереди готовых к выполнению потоков и перестает учитывать его в планировании.
ПРИМЕЧАНИЕ Ha рис. 3-25 показана схема перехода состояний с выделением состояний «готов» (ready), «ожидает» (waiting) и «выполняется» (running) - они относятся к ожиданию на объектах. Прочие состояния описываются в главе 6.
Взаимосвязь синхронизации с диспетчеризацией потоков иллюстрирует следующий пример с использованием объекта «событие».
(o)Поток пользовательского режима ждет на описателе объекта «событие» (т. е. ждет перехода этого объекта в свободное состояние).
(o)Ядро изменяет состояние потока с «готов» на «ожидает» и добавляет его в список потоков, ждущих объект «событие».
(o)Другой поток устанавливает объект «событие».
(o)Ядро просматривает список потоков, ожидающих этот объект. Если условия ожидания какого-либо потока выполнены (см. примечание ниже), ядро переводит его из состояния «ожидает» в состояние «готов». Если это поток с динамическим приоритетом, ядро может повысить его приоритет для выполнения.
(o)Поскольку новый поток теперь готов к выполнению, происходит перераспределение процессорного времени. Если при этом диспетчер обнаружит, что приоритет выполняемого потока ниже, чем приоритет потока, только что перешедшего в состояние «готов», он вытеснит поток с более низким приоритетом и выдаст программное прерывание для инициации переключения контекста на поток с более высоким приоритетом.
(o)Если в данный момент вытеснение невозможно ни на одном из процессоров, диспетчер включает поток в свою очередь потоков, готовых к выполнению.
ПРИМЕЧАНИЕ Некоторые потоки могут ждать более одного объекта, и в таком случае их ожидание продолжается.
Условия перехода объектов в свободное состояние
Эти условия различны для разных объектов. Например, объект «поток» находится в занятом состоянии в течение всего срока своей жизни и переводится ядром в свободное состояние лишь при завершении. Аналогичным образом, ядро переводит объект «процесс» в свободное состояние в момент завершения последнего потока процесса. Ho такой объект, как таймер, переводится в свободное состояние по истечении заданного времени.
Выбирая механизм синхронизации, вы должны учитывать в своей программе поведение синхронизирующих объектов. B таблице 3-10 показано, когда переходят в свободное состояние синхронизирующие объекты различных типов.
Например, объект «событие уведомления» - в Windows API он называется событием со сбросом вручную (manual reset event) - используется для уведомления о каком-либо событии. Когда этот объект переводится в свободное состояние, все потоки, ожидающие его, освобождаются. Исключением является тот поток, который ждет сразу несколько объектов: он может продолжать ожидание, пока не освободятся дополнительные объекты.
B отличие от события мьютекс предусматривает возможность владения. Этот объект используется для взаимоисключающего доступа к ресурсу, поэтому единовременно только один поток может владеть мьютексом. При освобождении мьютекса ядро переводит его в свободное состояние и выбирает для выполнения один из ожидающих потоков. Выбранный ядром поток захватывает мьютекс, а остальные потоки остаются в ожидании.
События с ключом и критические секции
Синхронизирующий объект, впервые появившийся в Windows XP и названный событием с ключом(keyed event), заслуживает особого упоминания. Он помогает процессам справляться с нехваткой памяти при использовании критических секций. Это недокументированное событие позволяет потоку указать «ключ» в следующей ситуации-, данный поток должен пробуждаться, когда другой поток того же процесса освобождает событие с тем же ключом.
Windows-процессы часто используют функции критических секций - EnterCriticalSectionи LeaveCriticalSection- для синхронизации доступа потоков к личным ресурсам процесса. Вызовы этих функций эффективнее прямого обращения к объектам «мьютекс», так как в отсутствие конкуренции они не заставляют переходить в режим ядра. При наличии конкуренции EnterCriticalSectionдинамически создает объект «событие», и поток, которому нужно захватить критическую секцию, ждет, когда поток, владеющий этой секцией, освободит ее вызовом LeaveCriticalSection.
Если создать объект «событие» для критической секции не удалось из-за нехватки системной памяти, EnterCriticalSectionиспользует глобальное событие с ключом - CritSecOutOjMemoryEvent(в каталоге \Ker-nel пространства имен диспетчера объектов). Если EnterCritica amp;ectionвынуждена задействовать CritSecOutOjMemoryEventвместо стандартного события, поток, ждущий критическую секцию, использует адрес этой секции как ключ. Это обеспечивает корректную работу функций критических секций даже в условиях временной нехватки памяти.
Мы не ставили себе задачу исчерпывающе описать все объекты исполнительной системы, а лишь хотели дать представление об их базовой функциональности и механизмах синхронизации. Об использовании этих объектов в Windows-программах см. справочную документацию Windows или четвертое издание книги Джеффри Рихтера «Windows для профессионалов».
Структуры данных
Учет ожидающих потоков и их объектов ожидания базируется на двух ключевых структурах данных: заголовках диспетчера (dispatcher headers) и блоках ожидания (wait blocks). Обе эти структуры определены в Ntddk.h, заголовочном файле DDK. Для удобства мы воспроизводим здесь эти определения.
ЭКСПЕРИМЕНТ: просмотр очередей ожидания
Хотя многие утилиты просмотра процессов умеют определять, находится ли поток в состоянии ожидания (отмечая в этом случае и тип ожидания), список объектов, ожидаемых потоком, можно увидеть только с помощью команды !processотладчика ядра. Например, следующий фрагмент вывода команды !processпоказывает, что поток ждет на объекте-событии.
Быстрые и защищенные мьютексы
Быстрые мьютексы(fast mutexes), также известные как мьютексы исполнительной системы, обычно обеспечивают более высокую производительность, чем объекты «мьютекс». Почему? Дело в том, что быстрые мьютексы, хоть и построены на объектах событий диспетчера, в отсутствие конкуренции не требуют ожидания объекта «событие» (и соответственно спин-блокировок, на которых основан этот объект). Эти преимущества особенно ярко проявляются в многопроцессорной среде. Быстрые мьютексы широко используются в ядре и драйверах устройств.
Однако быстрые мьютексы годятся, только если можно отключить доставку обычных APC режима ядра. B исполнительной системе определены две функции для захвата быстрых мьютексов: