Введение
Авторы: Сергей Желтов и Станислав БратановЛюбой, кто разрабатывает многопоточные приложения, согласится: проблема эффективной синхронизации - одна из самых сложных задач параллельного программирования. Современные операционные системы обеспечивают множество объектов синхронизации, которые определяют разнообразие методов и схем синхронизации.
В этой статье обсуждается ряд проблем параллельной синхронизации программ и предпринимается попытка прояснить, по крайней мере, некоторые из них.
Далее рассматриваются несколько схем синхронизации; описывается поведение объекта синхронизации, а также объясняется внутренняя системная реализация видимых для пользователей объектов синхронизации или функций, где это применимо. Выявляются скрытые синхронизации и задержки; схема исполнения потока показана в динамике, выявляются также неочевидные временные сдвиги потока.
Читатели найдут здесь также образцы кода, иллюстрирующие важные моменты проблемы синхронизации.
Все обсуждаемые объекты синхронизации и алгоритмы, представленные в этой статье, относятся к реализациям таких объектов и алгоритмов в Microsoft Windows*.
Определения
Несколько аббревиатур, использованных в этой статье, обозначают следующие термины:
IPI означает (Inter-Processor Interrupt - межпроцессорное прерывание), сигнал прерывания, отправленный одним процессором другому.
APC, (Asynchronous Procedure Call - асинхронный вызов процедуры), являющийся схемой уведомления Microsoft Windows*, разрешающей исполнение указанной процедуры в контексте указанного потока.
Внутренняя реализация
Эта статья посвящена схемам активации и подачи сигналов, которые используются для непосредственного контроля за исполнением потоков. Схемы взаимного исключения, которые применяются, главным образом, для синхронизации использования ресурсов (обеспечивая доступ к ресурсу только для одного потока), выходят за рамки этой статьи.Также в этой статье предполагается, что все необходимые ресурсы уже были разделены между потоками; задача заключается в активации потока и загрузке в каждый из них соответствующего объема работы.
Поскольку различные структуры взаимного исключения выходят за рамки данной статьи, рассматриваются только две разновидности объектов синхронизации, которые обычно используются для подачи сигналов: события и семафоры.
Алгоритмы активизации потоков
Полезные согласования по времени
Давайте подтвердим или опровергнем высказанные выше соображения о методах синхронизации и их пригодности для использования с помощью реальной информации о согласованиях по времени. Для исследования были взяты образец приложения OpenMP, построенного с помощью разных компиляторов (для того чтобы воспроизвести по крайней мере две разные модели синхронизации), и пример управления потоками вручную. Результаты показаны далее.
Рисунок 1. Разбивка параллельной программы
Теперь продолжим обсуждение расчетов по времени.
Задержка вызова APC
На рис. 2 показан пример управления потоком на базе APC. Основной поток вставляет в очереди каждого контролируемого потока три объекта APC. На рисунке начало вставки APC и запуск последнего потока помечены пунктирными линиями. Отмеченный интервал соответствует 47 микросекундам (как написано в нижнем правом углу рисунка), что является задержкой вызова APC.
Рисунок 2. Расчеты APC по времени
Задержка запуска события
На рис. 3 представлены аналогичные сведения для метода синхронизации на основе событий. Регион выполнения, начиная с запуска первого события и заканчивая активацией последнего потока, охватывает 33 микросекунды, это меньше, чем время исполнения в версии с применением APC.
Рис. 3. Расчеты по времени для события
Задержка снятия семафора
Рис. 4. Расчеты по времени для семафора
Приведенные выше данные расчета по времени доказывают наше предположение, что в синхронизацию вовлечены внутренние алгоритмы. Как и было предсказано, методы на основе событий и семафора показывают почти одинаковую производительность, а двухэтапное помещение APC в очередь приводит к дополнительным издержкам по сравнению с событиями и семафорами.
Параллельное исполнение потоков
Рассмотрим рис. 5. Мы отметили желтым регионы кода, где выполняются реальные вычисления. Можно заметить, что ни одна часть вычислительного кода не выполняется параллельно. Эти результаты слегка разочаровывают, потому что нет гарантии того, что приложение, правильно разделенное на потоки, работает производительнее, чем его последовательный аналог.
Рис. 5. Регионы параллельного выполнения
После анализа всех моментов, гарантирующих, что хотя бы одна часть приложения выполняется параллельно, должно выполняться следующее условие: время Sequential Time приложения, разделенное на количество процессоров Number of Processors, должно быть больше 50 микросекунд в самом худшем случае (см. рис. 2).
Теперь нужно ответить на вопрос: существует ли способ запуска нескольких потоков одновременно?
Более пристальный взгляд на рис. 4 позволяет обнаружить различие между ожидаемым поведением потоков (как предполагается для типа объекта синхронизации пользовательского уровня) и их фактической работой. Действительно, если три потока ожидают один и тот же объект синхронизации, предполагается, что они активизируются синхронно как объект, который переходит в состояние оповещения. Однако на рисунке все выглядит так, как будто каждый поток был запущен по отдельности.
Это лишний раз подтверждает правильность упомянутых выше предполагаемых алгоритмов синхронизации ядра операционной системы. Как можно убедиться, при открытии семафора операционная система берет новый поток из списка ожидания (связанный с семафором), выбирает незанятый процессор, а затем подает сигнал процессору (с помощью межпроцессорного прерывания) о необходимости начать исполнение нового потока. Эта процедура повторяется до тех пор, пока список ожидания не опустеет или не будет достигнут предел светофора. Поскольку список ожидания проанализирован для одного процессора, а другие процессоры вызываются последовательно, задержка между потоками становится больше или равна времени обработки списка ожидания, к которому прибавляется время отправки и получения IPI.
В настоящий момент, хотя средства для включения запуска синхронного потока отсутствуют (по крайней мере, в операционной системе, рассмотренной в данной статье), это может быть легко исправлено:
Выводы
Существует большое разнообразие объектов и схем синхронизации, которое берет начало в основной поддержке ядра операционной системы. Действительная эффективность различных схем синхронизации на уровне пользователя может выглядеть как совершенно одинаковая, поскольку такие схемы могут служить как обычные синонимы одной общей конструкции режима ядра.И наоборот, некоторые схемы синхронизации могут поддерживать только конкретные случаи, в то время как их производительность в других случаях синхронизации может быть низкой.
Вот почему при написании хорошо сбалансированного многопоточного приложения может оказаться полезным иметь в виду перечисленные выше взаимоотношения между пользовательскими объектами и объектами уровня ядра и применять только те схемы синхронизации, которые специально предназначены для конкретной цели, преследуемой пользователем.
В статье приведены примеры обоих способов нестандартного использования схемы синхронизации, а также использование различных схем, имеющих похожую производительность, благодаря одному и тому же алгоритму ядра системы, лежащему в их основе.
Также приведены неочевидные расчеты по времени вызовов синхронизации и временные сдвиги между потоками. Такие сведения о расчете по времени очень важны для планирования правильно разбитого на потоки приложения, поскольку не считывание издержек переключения между потоками и порядка распределения потоков может заметно повлиять на масштабируемость приложения и даже уменьшить его производительность по сравнению с последовательной версией.
Была выявлена точка, в которой ощущается недостаток поддержки со стороны операционной системы: относительно большие временные сдвиги между потоками, которые были запущены общим семафором. Было предложено решение на основе широковещательных IPI.
Заключение
- Используйте объекты и схемы синхронизации, специально созданные производителями операционной системы для выполнения данных задач (скорее всего такие схемы уже оптимизированы для решения данного конкретного типа проблем синхронизации),
- избегайте избыточных вызовов API (в цикле синхронизации),
- уделяйте внимание объему работы, которым вы собираетесь нагрузить потоки (это может оказаться нерациональным с учетом издержек),
- попробуйте компенсировать временные сдвиги с помощью делегирования меньшего количества работы медленным потокам (в особенности коротким).
Ссылки
- http://msdn.microsoft.com/library/*
- http://www.orgon.com/w2k_internals/*
- http://www.sysinternals.com/*
- Комплект для разработки драйверов Microsoft Windows 2003 Driver Development Kit
- Свен Шрайбер (Sven Schreiber). Undocumented Windows 2000 Secrets: A Programmer’s Cookbook (Недокументированные секреты Windows 2000: рецепты программиста)
- Уолтер Оней (Walter Oney). Programming the Microsoft Windows Driver Model (Программирование модели драйвера Microsoft Windows) (2-ое издание)
Об авторах
Сергей ЖелтовСергей Желтов - руководитель проекта по исследованию микропроцессоров, подразделение Intel Labs. В сферу его интересов входит обработка и сжатие носителей, программная и платформенная архитектура, обработка сигналов, спектры старшего разряда. Он имеет диплом инженера-радиофизика и степень магистра в области теоретической и математической физики Нижегородского государственного университета.
Станислав БратановСтанислав Братанов - программист отдела микропроцессорных исследований, подразделение Intel Labs. В сферу его интересов входят многопроцессорные программные платформы, операционные среды и кодирование данных платформенно-зависимых носителей. Закончил Нижегородский государственный университет (Россия).