 | | Опции страницы Сделать закладку  |
 Проголосовать теги сообщества
|
Авторы: Майкл Чайновет (Michael Chynoweth) и Мэри Р. Ли (Mary R Lee)
Краткое содержание В среде ОС Windows* предусмотрено несколько методов атомарной блокировки разделов программного кода и общих данных. В настоящей статье рассматриваются различные методы блокировки, предусмотренные в ОС Windows, а также издержки, связанные с их использованием. Поскольку будущее вычислительных систем – многоядерность, данная информация будет особенно полезна для разработчиков ПО. Введение Использовать все преимущества архитектуры Intel® Core™ можно только при работе с многопоточными приложениями. Из-за специфики многопоточных приложений в них чаще всего выполняются разделы кода, отвечающие за блокировку, поэтому правильный выбор методов блокировки так же важен, как и выбор метода распараллеливания. В этой статье рассматриваются различные методы блокировки, предусмотренные в ОС Windows, а также издержки, связанные с их использованием. Известно, что некоторые блокирующие функции ОС Windows могут передавать управление ядру ОС. Условия, при которых возможна передача управления ядру, также рассматриваются в этой статье.
Чтобы оценить влияние, которое различные методы блокировки оказывают на производительность, авторы статьи разработали два программных кода. Первый из них моделирует блокировку динамически связанного списка и снятие этой блокировки. Подобный метод блокировки мог бы использоваться для организации доступа к списку свободной памяти, используемого диспетчером памяти. Если один из параллельных потоков собирается занять или освободить какой-то раздел памяти, список свободной памяти необходимо заблокировать. Второй программный код имеет иную степень детализации блокировки: в глобальную переменную записывается идентификатор потока, установившего блокировку, затем блокировка снимается. В статье приводятся результаты измерения производительности и масштабируемости этих тестовых программных кодов, которые обрабатывались различным количеством потоков (от 1 до 64). Каждый поток устанавливал блокировку, 10 миллионов раз выполнял какую-то функцию, а затем снимал блокировку. На время тестирования стандартный интервал таймера ОС Windows XP был изменен с 10 до 1 мс.
Функции WaitForSingleObject и EnterCriticalSection Блокировка в многопоточных приложениях, разработанных для ОС Microsoft Windows, чаще всего осуществляется с помощью функций WaitForSingleObject и EnterCriticalSection. Функция WaitForSingleObject применяется для проверки и изменения состояния таких объектов, как события, задачи, мьютексы, процессы, семафоры, потоки и таймеры. К сожалению, она всегда пытается заблокировать ядро и входит в привилегированный режим (с уровнем 0) независимо от того, была установлена блокировка или нет. Функция WaitForSingleObject обратится к ядру, даже если ее аргумент TimeOut равен нулю. Еще одним недостатком этой функции является ограниченное количество потоков (64), для которых она может организовать одновременный запрос блокировки. Преимущество функции WaitForSingleObject – возможность ее глобальной обработки, которая позволяет использовать эту функцию для синхронизации процессов. Кроме того, она сообщает о заблокированном объекте операционной системе, что обеспечивает равный приоритет при распределении общих ресурсов и помогает бороться с инверсией приоритетов.
Еще одним методом синхронизации параллельных потоков являются критические разделы кода, начало которых объявляется функцией EnterCriticalSection. Для выхода из критических разделов используется функция LeaveCriticalSection. В отличие от функции WaitForSingleObject, функция LeaveCriticalSection не будет обращаться к ядру, если конфликты блокировки не обнаружены. В таком случае она просто установит блокировку для объекта в пространстве пользователя и возвратит свое значение без входа в привилегированный режим. При обнаружении конфликтов блокировки функция EnterCriticalSection обратится к ядру (подобно функции WaitForSingleObject). В общем случае, если конфликты блокировки происходят нечасто, то использование функции EnterCriticalSection, которая не будет обращаться к ядру, вызовет меньше издержек по сравнению с функцией WaitForSingleObject.
Минусом функции EnterCriticalSection является невозможность ее глобальной обработки. Следовательно, с помощью этой функции нельзя установить последовательность, в которой потоки будут обращаться к общему ресурсу. По сути, вход в критический раздел кода представляет собой блокирующий вызов функции EnterCriticalSection, которая не возвратит свое значение до тех пор, пока какой-нибудь поток не получит доступ к этому критическому разделу. В ОС Windows предусмотрена и неблокирующая функция – TryEnterCriticalSection, которая немедленно возвращает свое значение независимо от того, произошла блокировка или нет. При инициализации функции EnterCriticalSection можно задать число попыток доступа потока к критическому разделу (если поток так и не получит доступ к критическому разделу, он будет приостановлен) – для этого предназначена функция InitializeCriticalSectionAndSpinCount. Число попыток доступа задается при вызове этой функции или прописывается в реестре, если значение, по умолчанию установленное в ОС, не подходит для имеющегося количества потоков.
Функция EnterCriticalSection, как и WaitForSingleObject, обратится к ядру, если обнаружены конфликты блокировки. В таком случае частые переходы из пользовательского режима в привилегированный могут вызвать существенные вычислительные издержки.
Вызов функций EnterCriticalSection и WaitForSingleObject не отразится на производительности приложения, если блокируемые операции выполняются в течение нескольких тысяч тактов процессора. В этом случае незначительными будут и издержки, связанные с процессами установки и снятия блокировки. Производительность приложения может снизиться лишь в случае с высокой степени детализации блокировки, когда общий ресурс блокируется всего на несколько сотен тактов. В такой ситуации предпочтительнее применить блокировку на уровне пользователя.
Вычислительные издержки при вызовах функций WaitForSingleObject и EnterCriticalSection измерялись авторами при выполнении последовательной и параллельной (с двумя потоками) версий программного кода, моделирующего управление памятью. В процессе данного тестирования конфликты блокировки практически отсутствовали. Тестирование показало, что производительность программного кода, в котором использовалась функция WaitForSingleObject, почти в пять раз ниже производительности аналогичного кода, в котором использовалась функция EnterCriticalSection. Конфликты блокировки свели к минимуму разницу в производительности двухпоточных кодов, в одном из которых использовалась функция EnterCriticalSection, а в другом – функция WaitForSingleObject. Необходимо пояснить, почему в случае с редкими конфликтами блокировки производительность программного кода, в котором задействована функция EnterCriticalSection, была выше производительности аналогичного кода, в котором использовалась функция WaitForSingleObject. Это объясняется тем, что функция EnterCriticalSection обращается к ядру только при обнаружении конфликта блокировки, в отличие от функции WaitForSingleObject, которая обращается к ядру при каждом вызове. Рис. 1. Приложение, выполняющее функции управления памятью. Обработка функций EnterCriticalSection и WaitForSingleObject производилась сначала одним, а затем двумя потоками. Очевиден прирост производительности при однопоточной обработке функции EnterCriticalSection. Это объясняется отсутствием конфликтов блокировки и тем, что функция не обращалась к ядру (то есть не переходила в привилегированный режим), если блокировка проходила успешно.
На рис. 2 представлены результаты измерения издержек, вызванных обработкой функций EnterCriticalSection и WaitForSingleObject, с различным количеством потоков (от 1 до 64) и частыми конфликтами блокировки. При выполнении данного кода блокировался динамически связанный список, осуществлялся ввод или выборка данных, после чего блокировка снималась. То есть приложение моделировало работу со списком свободной памяти, который обычно часто блокируется при распределении или освобождении каких-то ее областей. Поскольку между потоками, которые пытались заблокировать список, происходило переключение контекста, средняя загрузка процессора при запуске обеих версий кода не превысила 22%. Тестирование показало, что частые конфликты блокировки практически уравняли издержки, вызванные обработкой функций EnterCriticalSection и WaitForSingleObject.  Рис. 2. Приложение, выполняющее функции управления памятью. Обработка функций EnterCriticalSection и WaitForSingleObject производилась различным количеством потоков (от 1 до 64). В ситуации с повышенной частотой конфликтов блокировки издержки, вызванные обработкой функций EnterCriticalSection и WaitForSingleObject, были практически равны.
Чтобы определить, сколько конфликтов блокировки происходит при выполнении функций EnterCriticalSection и WaitForSingleObject, можно воспользоваться выборкой на основе событий, производимой анализатором производительности Intel® VTune™. Перед тем, как произвести выборку, не забудьте убедиться в том, что вы загрузили правильные символы ядра (инструкции по загрузке символов ядра вы можете найти в сети Microsoft Developer Network (MSDN)).
Если при выполнении функции EnterCriticalSection будут зарегистрированы обращения к ядру (ntoskrnl.exe или ntkrnlpa.exe), значит, присутствуют конфликты блокировки. При отсутствии конфликтов вызовы функций EnterCriticalSection и LeaveCriticalSection обратятся к библиотеке ntdll.dll (к функциям RtlEnterCriticalSection и RtlLeaveCriticalSection соответственно). NTDLL.DLL – это динамически подключаемая библиотека, обработка которой осуществляется на третьем (непривилегированном) уровне процессора. Эта библиотека основана на стандартной библиотеке исполняемых компонентов, которую использует любое приложение. Поэтому NTDLL.DLL не конфликтует с ядром ОС. При обнаружении конфликтов блокировки функция EnterCriticalSection обратится к ядру, как и функция WaitForSingleObject. Чтобы не углубляться в особенности этих функций, проанализируем функции из состава библиотек hal.dll, ntdll.dll и ntkrnlpa.exe (или ntoskrnl.exe). Таким образом можно выяснить, происходят ли конфликты блокировки при выполнении функции EnterCriticalSection (см. рис. 3).  Рис. 3. Основные функции ядра ОС Windows и библиотек ntdll.dll и hal.dll. При выполнении функций EnterCriticalSection и WaitForSingleObject присутствуют частые конфликты блокировки.
Функция WaitForSingleObject всегда передает управление ядру ОС Windows, однако при анализе вызова этой функции тоже можно определить частые конфликты блокировки, при которых она будет в разной последовательности запрашивать функции из состава ядра и библиотек ntdll.dll и hal.dll. Это объясняется том, что с потоком, который не смог установить блокировку, произойдет переключение контекста. Для определения частых конфликтов блокировки, которые происходят, когда функции WaitForSingleObject и EnterCriticalSection обращаются к ядру, особенно хорошо подходят функции KiDispatchInterrupt, ZwYieldExecution и KiDispatchInterrupt (из состава ядра), а также функции HalRequestlpi и HalClearSoftwareInterrupt (из состава библиотеки hal.dll).  Рис. 4. Основные функции ядра ОС Windows и библиотек ntdll.dll и hal.dll. Вариант с отсутствием конфликтов и частыми конфликтами при вызове функции WaitForSingleObject.
Для блокировки относительно небольших операций или в случае с частыми конфликтами блокировки предпочтительно использовать блокировку на уровне пользователя, поскольку функции EnterCriticalSection и WaitForSingleObject обратятся к ядру, если будут обнаружены конфликты блокировки.
Атомарные блокировки на уровне пользователя Блокировка на уровне пользователя осуществляется с помощью атомарных инструкций процессора, которые обновляют пространство памяти, используя префикс блокировки и операнд, указывающий адрес памяти. Современными процессорами Intel могут атомарно выполняться следующие инструкции с префиксом блокировки: ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD и XCHG. Функция EnterCriticalSection использует атомарные инструкции, чтобы установить блокировку в пространстве пользователя перед тем, как передать управление ядру. Явный префикс блокировки необходим для всех инструкций, кроме xchg и cmpxchg, для которых он обозначается неявно, если этим инструкциям нужен какой-то адрес памяти.
В системах на базе процессоров Intel® серии 486 префикс блокировки использовался для установки блокировки на системную шину, что существенно снижало производительность. Процессоры совершенствовались, и у процессоров с новой архитектурой Intel® Pentium® Pro блокировалась уже не системная шина, а кэш-память. Однако даже в самых современных системах, если понадобится блокировка некэшируемой памяти или сразу нескольких строк кэш-памяти, будет заблокирована именно системная шина. Конечно, такие ситуации маловероятны, поэтому в большинстве случаев префиксы блокировки используются для блокировки именно кэш-памяти, что влияет на производительность незначительно.
На рис. 3 представлен пример кода, использующего атомарные инструкции с префиксом блокировки. Данный код проверяет контрольный регистр перед тем, как попытаться заблокировать общий ресурс. Если в регистре записана единица, значит, общий ресурс уже был заблокирован другим потоком, если нуль – ресурс свободен. Атомарная инструкция xchg используется для изменения содержимого контрольного регистра: если после выполнения инструкции xchg в регистре eax записан нуль, значит, блокировка была установлена текущим потоком, если же в регистре eax записана единица, значит, блокировку установил другой поток.
Note: edx register contains address of lock variable
// move 1 into eax register
mov eax, 1
// xchg 1 with value contained in dereferenced edx
lock xchg
DWORD PTR[edx],eax
// test if zero
test eax,eax
// jump if not zero
jne Target
|
Рис. 5. Пример блокировки, осуществляемой с помощью мьютекса.
Чтобы воспользоваться преимуществами блокировки в пространстве пользователя, необязательно самостоятельно разрабатывать подобные программные коды. В прикладном программном интерфейсе Win32 уже предусмотрено несколько специальных функций: InterlockedExchange, InterlockedIncrement, InterlockedDecrement, InterlockedCompareExchange и InterlockedExchangeAdd. Они входят в состав библиотеки kernel32.dll, которая подгружается приложением на третьем (непривилегированном) уровне процессора. Не стоит путать время обработки библиотеки kernel32.dll со временем обработки ядра – помните, что она подгружается на непривилегированном уровне и работает в качестве шлюза для функций, которые передают управление ядру ОС. Перейти в привилегированный режим и передать управление ядру ОС эти функции не могут.
Чтобы сравнить издержки, связанные с вызовом функции WaitForSingleObject, с издержками, связанными с блокировкой на уровне пользователя, авторы вновь использовали программу, которая моделировала управление памятью. Блокировка осуществлялась с помощью пустых циклов с ожиданием. Оказалось, что такой метод влечет за собой гораздо меньше издержек, как при редких, так и при частых конфликтах блокировки. Таким образом, частую блокировку относительно небольших операций предпочтительно реализовывать на уровне пользователя.  Рис. 6. Системные издержки, которые были измерены при выполнении программы, моделирующей управление памятью. Представлены результаты для встроенных пустых циклов с ожиданием и для вызова функции WaitForSingleObject.
Пустые циклы с ожиданием для атомарной блокировки на уровне пользователя К сожалению, при реализации блокировки на уровне пользователя, пустые циклы с ожиданием нельзя организовать с помощью функций из состава ядра ОС. Это означает, что если приложению не удастся установить блокировку с помощью функций xchg или cmpxchg, ему придется либо выполнять другую функцию, либо отправлять повторный запрос на блокировку. Таким образом, если вы хотите реализовать пустые циклы с ожиданием в пользовательском режиме, примените функцию TryEnterCriticalSection и задайте определенное количество пустых циклов. Еще одним вариантом является использование сторонних библиотек блокирующих функций, например, библиотеки Intel® Threading Building Blocks. В идеальном случае поток, который не смог установить блокировку, должен сразу же начать выполнение другой функции, а не находиться в зацикленном состоянии.
Рассмотрим реализацию пустых циклов с ожиданием на примере тестовых программных кодов. В любом пустом цикле с ожиданием первая попытка установить блокировку осуществлялась с помощью атомарной инструкции (обычно cmpxchg или xchg с префиксом блокировки). Если блокировку установить не удавалось, включался пустой цикл, в котором текущий поток обращался к контрольному регистру, чтобы определить, снял ли другой поток свою блокировку. Такой процесс называется "изменяемым чтением" (volatile read), поскольку в данной структуре кода используется переменная типа "volatile". Для таких переменных существует несколько ограничений, например, их нельзя обновлять непосредственно в регистрах – для этого необходимо использовать адреса памяти. Рассмотрим пример, в котором осуществляется первая попытка установить блокировку. Если попытка блокировки мьютекса была успешной, в результате выполнения инструкции xchg в контрольный регистр записывается нуль.
Если блокировка не устанавливается, поток периодически считывает значению контрольного регистра, и сравнивает его с нулем, чтобы убедиться, что блокировка снята. Если в регистре записан нуль, текущий поток с помощью атомарной инструкции вновь попытается установить блокировку, после чего перейдет к обработке заблокированного кода.
if (GETLOCK(lock) != 0)
{
While (VARIOUS_CRITERIA)
{
_asm pause; // pause instruction in spin-loop
if ((volatile int*)lock) == 0) // spin on dirty read, not on lock
{
if (GETLOCK(lock)) == 0)
{
goto PROTECTED_CODE;
}
}
}
BACK_OFF_LOCK(lock); // back off lock or do other work
}
PROTECTED_CODE:
|
Рис. 7. Эффективная реализация пустых циклов с ожиданием атомарной блокировки. Необходимо отметить, что в случае неудачной попытки установить блокировку поток будет периодически обращаться не к общему ресурсу, а к контрольному регистру. После определенного количества циклов поток либо будет приостановлен, либо начнет выполнять другую функцию. Приостановка запросов на блокировку, осуществляемых через пустые циклы с ожиданием По некоторым причинам использование пустых циклов на уровне пользователя может пагубно повлиять на производительность системы. Судите сами – ОС не знает, что процессор, обрабатывающий пустой цикл, не выполняет полезную работу. Соответственно, поток будет постоянно получать квант процессорного времени. Это повлияет особенно на производительность серверных платформ под управлением Windows, в которых квант процессорного времени увеличен. Итак, процессор может быть перегружен обработкой потоков, выполняющих пустые циклы. Такая ситуация отрицательно повлияет и на производительность приложения (представьте, что поток, который установил блокировку, не сможет получить квант процессорного времени, чтобы снять эту блокировку – процессор-то перегружен!). Вот почему при реализации пустых циклов с ожиданием важно предусмотреть их приостановку, чтобы ограничить количество потоков, которые одновременно будут пытаться заблокировать один и тот же ресурс.
Это можно сделать несколькими способами. Проще всего в программном коде задать количество циклов, в течение которых приложение будет пытаться установить блокировку, а после осуществит переключение контекста. Однако у данной реализации будут проблемы с масштабируемостью, когда в системе изменится количество аппаратных потоков, поскольку квант процессорного времени, выделенный потоку, будет увеличиваться вместе с частотой процессора. Модификацией данного способа является экспоненциальное снижение частоты пустых циклов, при котором поток сначала часто запрашивает блокировку, а затем – все реже и реже. Такой вариант вполне масштабируем и широко используется при организации сетей на основе протоколов Windows [1].
На рис. 8 представлены результаты измерения производительности кодов, в которых запросы на блокировку осуществлялись с помощью пустых циклов с ожиданием. Очевидно, что производительность кода с приостановкой запросов много больше его аналога, в котором запросы осуществлялись постоянно. Низкая производительность объясняется созданием условий, при которых происходило переключение контекста потока, удерживающего блокировку, поскольку ему приходилось ждать следующего кванта процессорного времени, чтобы снять блокировку.  Рис. 8. Измерение производительности тестового приложения, в котором определялся идентификатор потока. Представлены результаты для вариантов с бесконечными запросами на блокировку и с приостановкой запросов после определенного их количества.
Циклическое чтение контрольных регистров или циклические попытки установить блокировку? Основная ошибка разработчиков, реализующих пустые циклы с ожиданием, – циклическое выполнение атомарных инструкций вместо циклического чтения контрольного регистра. Необходимо отметить, для второго варианта требуется значительно меньше системного времени и ресурсов, причем попытка блокировки общего ресурса будет осуществлена только после его освобождения.
На рис. 9 представлены результаты измерения времени выполнения вариантов второго тестового приложения с запросами на блокировку и с запросами на чтение контрольного регистра.  Рис. 9. Измерение времени выполнения тестового приложения, в котором определялся идентификатор потока. Представлены результаты для вариантов с бесконечными запросами на блокировку и с приостановкой запросов после определенного их количества.
Существует ошибочное мнение о том, что издержки при блокировке с использованием инструкции cmpxchg, будут меньше, чем при использовании инструкции xchg. Считается, что cmpxchg не будет устанавливать блокировку в привилегированном режиме, поскольку первой будет выполняться инструкция cmp. Авторы убедились в том, что издержки, вызываемые обработкой инструкций cmpxchg и xchg, одинаковы (см. рис. 10).  Рис. 10. Тестовое приложение, в котором определялся идентификатор потока. Сравнение издержек, вызванных использованием инструкций xchg и cmpxchg.
Заключение Методы блокировки являются важным фактором, влияющим на производительность и масштабируемость приложений, разработанных для среды Windows. Использование функции WaitForSingleObject связано с существенными системными издержками, вызванными обращением к ядру ОС даже при отсутствии конфликтов блокировки, поэтому для частых вызовов блокировки в условиях редких конфликтов предпочтительно использовать другие функции. Кстати, функцию WaitForSingleObject не рекомендуется использовать и для блокировки относительно небольших операций. Функция EnterCriticalSection пытается установить блокировку на уровне пользователя и обращается к ядру только в случае обнаружения конфликтов блокировки. Чтобы разработчикам не приходилось создавать собственные структуры пустых циклов с ожиданием, корпорация Microsoft предусмотрела вызов функции TryEnterCriticalSection, которая несколько раз пытается установить блокировку перед тем, как обратиться к ядру ОС.
Специально для раскрытия понятия пустых циклов с ожиданием на уровне пользователя авторы этой статьи рассмотрели несколько примеров программных кодов и привели результаты измерения их производительности. Чтобы обеспечить производительность приложений, в которых запросы на блокировку реализованы через пустые циклы с ожиданием, необходимо ограничить число этих циклов и предусмотреть циклическое чтение контрольных регистров. Справочные материалы [1] http://www.microsoft.com/technet/itsolutions/network/deploy/depovg/tcpip2k.mspx*
[2] Майкл Чайновет (Michael Chynoweth). Реализация масштабируемых атомарных методов блокировки в приложениях, оптимизированных под архитектуры Intel® с поддержкой технологии Intel® EM64T и под 32-разрядные архитектуры Intel®
We invite you to post a comment (not monitored by customer support) on this page or send a question directly to our support team. |
