Выбор примитивов синхронизации для минимизации издержек

Choosing Appropriate Synchronization Primitives to Minimize Overhead [Eng., PDF 237KB]

Аннотация

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

Введение

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

Win32* API синхронизации

Win32 API имеет несколько механизмов, гарантирующих атомарность, три из которых будут рассмотрены в этой главе. Конструкции иллюстрируются на примере оператора инкремента (напр., var++). Если изменяемая переменная разделяется потоками, то инструкции загрузка→изменение→сохранение должны выполняться атомарно (т.е. их последовательность не должна прерываться до завершения операции). В приведенном ниже коде показывается, как использовать функции API:

#include 

CRITICAL_SECTION cs; /* InitializeCriticalSection called in main() */
HANDLE mtx;  /* CreateMutex called in main() */
static LONG counter = 0;

void IncrementCounter ()
{
  // Synchronize with Win32 interlocked function
  InterlockedIncrement (&counter);

  // Synchronize with Win32 critical section
  EnterCriticalSection (&cs);
    counter++;
  LeaveCriticalSection (&cs);

  // Synchronize with Win32 mutex
  WaitForSingleObject (mtx, INFINITE);
    counter++
  ReleaseMutex (mtx);
}

Сравним эти три механизма, чтобы понять, какой из них лучше подходит в тех или иных сценариях синхронизации. Взаимоблокирующие (interlocked) функции Win32 (InterlockedIncrement, InterlockedDecrement, InterlockedExchange, InterlockedExchangeAdd, InterlockedCompareExchange) ограничены выполнением простых операций, но работают быстрее критических секций, к тому же требуют меньшего количества вызовов. Для входа и выхода из критической секции Win32 требуется вызов EnterCriticalSection и LeaveCriticalSection или WaitForSingleObject и ReleaseMutex. Взаимоблокирующие функции не блокируют потоки, а функции EnterCriticalSection и WaitForSingleObject (или WaitForMultipleObjects) в случае недоступности объекта синхронизации блокируют потоки.

Когда возникает необходимость использования критических секций, то синхронизация с помощью Win32 CRITICAL_SECTION создает гораздо меньший объем системных издержек, чем Win32 мьютексы, семафоры и обработчики событий, потому что первая является объектом уровня пользователя, а остальные – объектами уровня ядра. Хотя критические секции Win32 обычно работают быстрее, чем мьютекс, они не такие гибкие. Мьютексы, как и другие объекты ядра, могут использоваться для синхронизации между потоками. Можно также использовать ожидания по таймеру с помощью функций WaitForSingleObject и WaitForMultipleObjects. Вместо того, чтобы неограниченно ожидать мьютекса, после истечения указанного лимита времени потоки продолжают свою работу. Установка времени ожидания в ноль позволяет потокам без установки блокировки проверять, доступен ли мьютекс. (Отметим, что также возможно без блокировки проверять доступность CRITICAL_SECTION с помощью функции TryEnterCriticalSection). Наконец, если поток завершается, не сняв мьютекс, операционная система передает описателю специальный сигнал, чтобы ожидающие потоки не перешли в состояние дедлока. Если поток завершается, не сняв CRITICAL_SECTION, то потоки, ожидающие входа в эту критическую секцию попадают в дедлок.

Поток Win32 сразу освобождает процессор, когда пытается получить доступ в критическую секцию или мьютекс, уже занятый другим потоком. В общем плане это правильно. Поток блокируется и процессор может делать другую полезную работу. Однако блокирование и разблокирование потока дается дорогой ценой. Иногда для потока лучше попытаться еще раз получить блокировку перед тем, как блокироваться (например, в SMP на маленьких критических секциях). Критические секции Win32 имеют настраиваемый счетчик, который контролирует, как долго поток может ожидать перед тем, как освободить процессор. Функции InitializeCriticalSectionAndSpinCount и SetCriticalSectionSpinCount fустанавливают счетчик ожидания для потоков, пытающихся войти в конкретную критическую секцию.

Совет

Для простых операций над переменными (инкримент, декремент, обмен значениями), используйте быстрые взаимоблокирующие функции Win32 с низким уровнем издержек.

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

Контролируйте счетчик цикла критической секции Win32 с помощью функций InitializeCriticalSectionAndSpinCount и SetCriticalSectionSpinCount. Контроль времени, которое поток ожидает до того, как освободить процессор, особенно важен для малых и высококонфликтных критических секций. Циклы ожидания могут серьезно снижать производительность в SMP системах и процессорах с технологией Intel® Hyper-Threading.

API синхронизация Intel® Threading Building Blocks

Intel ® Threading Building Blocks (Intel® TBB) обеспечивает переносимые оболочки для атомарных операций (класс шаблонов atomic<T>) и механизмы взаимного исключения разных типов, включая оболочку для «родного» мьютекса. Поскольку в предыдущих главах уже обсуждались плюсы и минусы использования атомарных операций и зависящих от системы API-синхронизаций, то в данной главе мы пропускаем операторы tbb::atomic<T> и tbb::mutex, фокусируясь на быстрых классах синхронизации уровня пользователя, таких как spin_mutex, queuing_mutex, spin_rw_mutex и queuing_rw_mutex.

Самым простым мьютексом является spin_mutex. Поток, пытающийся установить блокировку на занятый spin_mutex busy , ожидает до тех пор, пока не получит такую возможность. spin_mutex удобно использовать, когда блокировка устанавливается лишь на несколько инструкций. Например, в следующем коде мьютекс FreeListMutex используется для защиты разделенной переменной FreeList:

Node* FreeList;
typedef spin_mutex FreeListMutexType;
FreeListMutexType FreeListMutex;

Node* AllocateNode()
{
  Node* n;
  {
    FreeListMutexType::scoped_lock lock(FreeListMutex);
    n = FreeList;
    if( n )
    FreeList = n->next;
  }
  if( !n )
    n = new Node();
  return n;
}

Конструктор scoped_lock ожидает, пока не снимутся все другие блокировки на FreeListMutex. Деструктор снимает блокировку. Роль дополнительных фигурных скобок внутри функции AllocateNode состоит в том, чтобы держать время жизни блокировки как можно более коротким, и другие ожидающие потоки могли дождаться своей очереди как можно быстрее.

Еще один мьютекс уровня пользователя с циклом ожидания из пакета Intel TBB - queuing_mutex. Это тоже мьютекс уровня пользователя, но в противоположность spin_mutex, queuing_mutex более «справедлив». Справедливый мьютекс пропускает потоки в том порядке, в котором они прибыли. «Несправедливые» мьютексы могут работать быстрее справедливых, поскольку в первую очередь пропускают работающие потоки, задерживая те, чья очередь подошла, но которые находятся в состоянии сна по причине, например, прерывания. Мьютекс с очередью нужно использовать тогда, когда действительно важны масштабируемость и справедливость мьютекса.

Не всякий доступ к общим данным должен быть взаимоисключающим. В большинстве приложений доступ к общим структурам данных в основном выполняется для чтения и в редких случаях для записи. Для таких структур данных защита одного читающего потока от другого не обязательна, то есть здесь можно избежать последовательного выполнения. Блокировки чтения/записи Intel TBB позволяют входить в критическую секцию сразу нескольким читающим потокам и только одному пишущему. «Несправедливая» версия мьютекса чтения/записи с ожиданием – spin_rw_mutex, и его «справедливый» собрат – queuing_rw_mutex. Мьютексы чтения/записи поддерживают тот же scoped_lock API, что и spin_mutex и queuing_mutex, и в дополнение имеют специальные возможности поднятия уровня блокировки чтения до блокировки записи и понижения блокировки записи до блокировки чтения.

Совет

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

Если критический участок имеет размер всего в несколько инструкций и «справедливый» подход не обязателен, то предпочтительнее использовать spin_mutex. А в ситуациях, когда критическая секция коротка, но важно пропускать потоки в том порядке, в котором они прибывают, используйте queuing_mutex.

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

Рекомендации

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

static LONG N = 0;
LONG localVar;
…
InterlockedIncrement (&N);
InterlockedIncrement (&N);
InterlockedExchange (&localVar, N);

static LONG N = 0;
LONG localVar;
…
EnterCriticalSection (&lock);
 localVar = (N += 2);
LeaveCriticalSection (&lock);

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

Из соображений безопасности критические секции Win32, образованные переменными CRITICAL_SECTION или мьютексом HANDLEs, должны иметь только одну точку входа и одну выхода. Произвольный переход в критическую секцию разрушает синхронизацию. Произвольный выход из критической секции без вызова LeaveCriticalSection или ReleaseMutex вызовет дедлок ожидающих потоков. При этом наличие одной точки входа и одной выхода делает код более понятным.

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

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