Rundown protection

Объект, реализованный в ядре ОС Windows, начиная с Windows XP.

Краткое описание

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

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

Такой объект тривиально делается из спинлока, целочисленного счетчика и события (KEVENT), но тривиальная реализация использует спинлок, который может стать узким местом. Реализация же, включенная в ядро Windows, является lock-free и не использует спинлок (только Interlocked операции).

Операции

Для объекта существуют операции:

• Acquire. Увеличивает счетчик на единицу, может отказать.
• AcquireEx. Увеличивает счетчик на заданное число, может отказать.
• Release. Уменьшает счетчик на единицу и, возможно, пробуждает ожидание.
• ReleaseEx. Уменьшает счетчик на заданное число, возможно, пробуждает ожидание.
• Wait. Останавливает поток, пока счетчик не упадет до нуля. Перед этим ожиданием объект переводится в состояние, когда все последующие Acquire возвращают отказ.

Требования к вызывающему коду

• вызывающий код не должен пытаться уменьшить значение счетчика ниже нуля
• вызывающий код должен принять меры для недопущения гонки двух Wait, а также повторного вызова Wait на объекте, где он звался ранее. После входа в Wait объект переходит в состояние, когда все Acquire отказывают, но тем не менее гонки между Wait и Acquire, равно как и Acquire после возврата из Wait, разрешены. Чтобы сбросить это состояние и вернуться к тому состоянию, которое было установлено в момент инициализации объекта, нужно вызвать Reinitialize, после этого вызова Acquire начинают работать и разрешено звать Wait. Допускается гонка между Reinitialize и Acquire.

Интересные факты

В ОС Windows Server 2008 R2 вызов Wait разрешен даже на DISPATCH LEVEL, и, так как использование диспетчера на таком уровне запрещено, Wait представляет собой busy loop опроса объекта.

В этом busy loop есть вызовы, используемые в случае, когда ОС бежит на гостевой виртуальной машине, и извещающие гипервизор виртуальных машин о том, что гость вошел в busy loop.

Наличие документации от производителя ОС

Объект не документирован, хотя вызовы для работы с ним (ExXxxRundownProtection) и присутствуют в wdm.h - главном файле-заголовке ядра Windows.

Версия, оптимизированная по использованию кэша

Начиная с Windows Server 2003 SP1, в ядре Windows есть также еще более быстрая версия этого же объекта - cache-aware rundown protection. Эта версия имеет точно такую же семантику, но иную реализацию, для работы с ней нужно использовать вызовы, в имена которых входит "CacheAware".

Cache-aware rundown protection сильно снижает загрязнение кэша в случае нормальных часто выполняемых операций, т.е. Acquire и Release (считается, что Wait случается крайне редко). Внутри себя объект представляет собой массив обычных rundown protection, по одной на процессор, и логика работы такова, что Acquire использует только подобъект для текущего процессора, который уже загружен в его кэш.

Данный объект защищен патентом 7133977 в США (все три изобретателя - сотрудники Microsoft):

http://www.freepatentsonline.com/7133977.html

Восстановленный исходный код

Восстановленный исходный код этих объектов (только "старая", не cache-aware, версия) есть в проекте ReactOS

http://doxygen.reactos.org/d7/d55/rundown_8c_source.html