mutex-condvar-atomic

Синхронизация потоков

Проблема гонки данных

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

Кроме того, операции над типами данных, размер которых превышает размер машинного слова, заведомо являются неатомарными. В первую очередь, такая проблема проявляется для 64-разрядных типов данных (double и int64_t) на 32-разрядных архитектурах.

Если несколько потоков или процессов обращаются к одной области памяти, причем один из потоков (процессов) производит запись, то такая ситуация называется гонкой данных (data race), и приводит к ситуации неопределенного поведения.

Пример:

int64_t balance = 0;

// Thread-1
void* thread_func_one(void *arg) {
    balance += (int64_t) arg;
}

// Thread-2
void* yet_another_thread_func(void *arg) {
    if (balance > 0) {
        // use balance value
    }
    else {
        // fail
    }
}

В данной программе гонка данных возникает по причине того, что поток Thread-2 полагается на неизменность значения переменной balance во время работы функции. В то же время, поток Thread-1 совершенно независимо меняет это значение.

Критические секции

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

Стандартным инструментом для обозначения началала критической секции является захват мьютекса.

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

Мьютекс объявлен в заголовочном файле <pthread.h>, и функции работы с ним требуют линковки с библиотекой -pthread.

• pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr) - инициализация мьютекса для его последующего использования. Если второй параметр NULL, то инициализируется обычный (не рекурсивный) мьютекс. Для создания нового инициализированного мьютекса с параметрами по умолчанию можно использовать макрос PTHREAD_MUTEX_INITIALIZER.
• pthread_mutex_destroy(pthread_mutex_t *mutex) - уничтожить ранее созданный мьютекс.
• pthread_mutex_lock(pthread_mutex_t *mutex) - захватить мьютекс. Если другой поток уже захватил его, то текущий поток приостанавливает свою работу.
• pthread_mutex_trylock(pthread_mutex_t *mutex) - пытается захватить мьютекс. В случае успеха возвращает значение 0, а если мьютекс уже занят, то значение EBUSY.
• pthread_mutex_unlock(pthread_mutex_t *mutex) - освободить ранее захваченный мьютекс. В отличии от семафоров, освободить мьютекс может только тот поток, которые его захватил, в противном случае это приведет к ошибке EPERM.

Условные переменные

Условная переменная - это некоторый примитив синхронизации, используемый для нотификации одним из потоков о наступлении некоторого события, например, готовности данных. Использование условных переменных позволяет отказаться от необходимости применения операций ввода-вывода, и тем самым, исключают необходимость испоьзования системных вызовов.

С условной переменной связан определенный мьютекс, который разблокируется на время ожидания.

• pthread_cond_init(pthread_cond_t *c, const pthread_condattr_t *attr) - инициализации условной переменной. Второй параметр может быть NULL - в этом случае подразумевается использование переменной только в рамках одного процесса. Для инициализации условной переменной с параметрами по умолчанию используется макрос PTHREAD_COND_INITIALIZER.
• pthread_cond_destroy(pthread_cond_t *c) - уничтожить условную переменную.
• pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m) - ожидает нотификации условной переменной переменной c, временно разблокируя мютекс m. Перед вызовом мьютекс должен находиться в заблокированном состоянии, в противном случае - неопределенное поведение. После наступления события нотификации, мьютекс опять блокируется.
• pthread_cond_timedwait(pthread_cond_t *c, pthread_mutex_t *m, const struct timespec *timeout) - то же, что и pthread_cond_wait, но ожидание прекращается по истечению указанного периода времени.
• pthread_cond_signal(pthread_cond_t *c) - уведомляет один поток, для которого выполняется ожидание нотификации. В общем случае, поток выбирается случайным образом, если их несколько.
• pthread_cond_broadcast(pthread_cond_t *c) - уведомляет все потоки, для которых выполняется ожидание нотификации.

В случае, если ни один поток не вызвал pthread_cond_wait, то нотификация условной переменной проходит незамеченной.

Атомарные переменные и неблокирующие структуры данных

Необходимость блокировки мьютекса, защищающего критическую секцию, может приводить к простою потоков, которые не собираются ничего модифицировать. В ситуации, когда потоков много, это существенно сказывается на производительности, и становится более выгодным использование lock-free структур данных, например односвязных списков.

Основная идея lock-free структур заключается в том, что любая модификация данных проводится каким-либо потоком в области памяти, которая не разделяется с другими потоками. В тот момент времени, когда данные подгтовлены и должны стать доступны остальным потокам, указатель на них записывается в достижимую другим потокам переменную, причем это происходит атомарным образом. Атомарность достигается за счёт того, что размер указателя в памяти не превышает размера машинного слова.

Начиная со 2011 года, в языке Си появлилось новое глючевое слово _Atomic - модификатор типа, регламентирующий атомарный тип данных. В отличии от языка C++, где атомарным может быть произвольный объект (не совсем честно, поскольку для составных типов используется мьютекс), множество допустимых атомарных типов данных для языка Си ограничивается только типами, которые умещаются в машинное слово. В противном случае, ключевое слово _Atomic и атомарные операции не имеют никакого значения. Атомарные операции над типами, объявленными как _Atomic, реализуются в Си11 как макросы:

• void atomic_store(T* object, T value),
• void atomic_store_explicit(T* object, T value, memory_order order) - сохранить значение в атомарную переменную.
• T atomic_load(T* object),
• T atomic_load_explicit(T* object, memory_order order) - загрузить значение из переменной.
• T atomic_exchange(T* object, T new_value),
• T atomic_exchange_explicit(T* object, T new_value, memory_order order) - заменить значение и вернуть предыдущее.
• _Bool atomic_compare_exchange_strong(T* object, T* expected, T new_value),
• _Bool atomic_compare_exchange_strong_explicit(T* object, T* expected, T new_value, memory_order success, memory_order failure),
• _Bool atomic_compare_exchange_weak(T* object, T* expected, T new_value),
• _Bool atomic_compare_exchange_weak_explicit(T* object, T* expected, T new_value, memory_order success, memory_order failure) - сравнить два значения, в случае их равенства - заменить на новое, в противном случае - записать в expected значение object.
• T atomic_fetch_MOD(T* object, T operand),
• T atomic_fetch_MOD_explicit(T* object, T operand, memory_order order) - получить значение переменной, после чего - модифицировать её. MOD можеть быть:

• add - инкремент
• sub - декремент
• and - поразрядное "и"
• or - поразрядное "или"
• xor - поразрядное "исключающее или".

В операции compare_exchange вариант weak обычно работает быстрее, но может ложно возвращать значение 0 даже при равенстве значений в object и expected. В некоторых алгоритмах это бывает допустимо, например, если значение проверяется в цикле.

Модели памяти

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

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

Пример:

// Thread-1
y = 0;
x = 0;
...
y = 2;
x = 1;

// Thread-2
if (2 == y) {
    z = x;  // 0 или 1?
}

В данном случае переменная z может иметь значения как 0, так и 1, поскольку компилятор мог переставить местами инструкции y=2 и x=1, считая такую перестановку не влияющей на выполнение кода функции, выполняемой в потоке Thread-1.

Атомарные операции обычно окружены какими-то соседними инструкциями над обычными (не атомарными) переменными.

Модель памяти (memory order) определяет, какие ограничения накладываются на перестановку обычных операций вокруг атомарных.

Ограничения memory_order:

• memory_order_relaxed - отсутствие каких-либо ограничений на оптимизацию.
• memory_order_consume - на существующих современных архитектурах совпадает с memory_order_relaxed.
• memory_order_acquire - запрещает перестановку операций работы с памятью вперед данной операции.
• memory_order_release - запрещает перестановку операций работы с памятью после данной операции.
• memory_order_acq_rel - одновременно memory_order_acquire и memory_order_release.
• memory_order_seq_cst - самые сильные ограничения на перестановку инструкций; все нити видят операции в том порядке, как они были прописаны в коде программы.

По умолчанию (то есть без явного указания модели памяти) подразумевается самая строгая модель seq_cst.