Как работают мьютексы?

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

Ответы

Ответ 1

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

Рассмотрим следующий эквивалентный псевдокод:

mutex global_mutex;
void InterlockedAdd(int& dest, int value) {
    scoped_lock lock(mutex);
    dest += value;
}
int InterlockedRead(int& src) {
    scoped_lock lock(mutex);
    return src;
}
void InterlockedWrite(int& dest, int value) {
    scoped_lock lock(mutex);
    dest = value;
}

Эти функции реализованы в виде инструкций CPU, и они гарантируют согласованность между потоками в разной степени. Точная семантика зависит от рассматриваемого CPU. x86 обеспечивает последовательную согласованность. Это означает, что операции действуют так, как если бы они были изданы последовательно, в некотором порядке. Это, очевидно, немного блокирует.

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

Ответ 2

Простая реализация, которая использовалась в прошлом, заключается в использовании атомарной "блокировки и обмена" на уровне процессора. Это специальная инструкция, которая атомарно меняет заданное значение со значением в некоторой ячейке памяти.

Нить могла бы получить такой мьютекс, пытаясь поменять значение 1 в ячейке памяти. Если значение возвращается как 0, то поток будет считать, что он имеет мьютекс и будет продолжен. В противном случае, если возвращаемое значение равно 1, поток будет знать, что какой-то другой поток в настоящее время имеет мьютекс. В этом случае он будет ждать, пока не попытается снова.

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

Ответ 3

Вот краткий обзор того, что должен работать мьютекс, это сокращенная форма моей полной статьи Как работает мьютекс?

В памяти есть целое число, которое представляет заблокированное состояние со значением 1 или 0.
Мьютекс нуждается в атомной compare_and_swap функции, которая может атомически попытаться изменить это значение и сообщить, удалось ли это. Это позволяет потоку одновременно проверять и изменять состояние.
ОС должна предоставить функцию ожидания в случае блокировки мьютекса. В Linux низкоуровневая функция futex. Это поместит поток в очередь, а также проверит целое число в памяти.
В число задействованных операций также входят заграждения данных, которые предотвращают видимость изменений в памяти до блокировки и полностью доступны после блокировки.

Ответ 4

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

На практике оба подхода объединены. См. Например, futexs для Linux.