Что предотвращает состояние гонки на замке?

24

Я понимаю основы того, что такое гонки данных, и как блокировки / мьютексы / семафоры помогают предотвратить их. Но что произойдет, если у вас будет «состояние гонки» на самом замке? Например, два разных потока, возможно, в одном приложении, но работающие на разных процессорах, пытаются получить блокировку в одно и то же время .

Что происходит потом? Что сделано, чтобы предотвратить это? Это невозможно или просто маловероятно? Или это реальное состояние гонки, которое должно произойти?

Гэвин Ховард
источник
Этот вопрос ранее задавался на SO: stackoverflow.com/questions/980521/…
Док Браун
и связанный с этим вопрос здесь на P.SE: programmers.stackexchange.com/questions/228827/…
трещотка урод
Вы приобретаете блокировку, чтобы получить блокировку;) (другими словами, если ваша блокировка имеет состояние гонки, она не реализована правильно - блокировка в значительной степени определяется как конструкция, реализующая взаимное исключение)
Tangrs
Вы упустили важный момент в работе замков. Они сконструированы таким образом, что гонка на замке невозможна, иначе они совершенно бесполезны.
Зейн

Ответы:

36

Это невозможно или просто маловероятно?

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

maaartinus
источник
3
Слава Богу ... все решается аппаратно ... (или, по крайней мере, на уровень ниже, чем мы касаемся.)
corsiKa
2
@ gdhoward Я не могу в это поверить ... этот ответ занял у меня менее 5 минут, и это третье место по количеству проголосовавших из моих четырех сотен ответов (в основном, SO). А также, вероятно, самый короткий.
Maaartinus
1
@maaartinus - Короткие и сладкие иногда делают это.
Бобсон
17

Изучите концепцию атомарных операций «Тест и Набор».

По сути, операция не может быть разделена - невозможно сделать две вещи в одно и то же время. Он проверит значение, установит его, если оно ясно, и вернет значение, которое было при тестировании. В операции блокировки результат всегда будет «lock == TRUE» после проверки и установки, единственная разница в том, была ли она установлена ​​или нет в начале.

На уровне микрокода в одноядерном процессоре это одна неделимая инструкция, и ее легко реализовать. С многоядерными и многоядерными процессорами это становится сложнее, но нам, как программистам, не нужно беспокоиться об этом, так как он предназначен для работы действительно умных парней, которые делают силикон. По сути, они делают то же самое - делают атомарную инструкцию, которая представляет собой причудливую версию test-and-set

mattnz
источник
2
По сути, если оборудование на некотором уровне не является последовательным по своей сути, оно будет иметь механизм, позволяющий разорвать связи, которые могли бы возникнуть в противном случае.
Билл Мичелл
@BillMichell, я должен был подумать об этом. На самом деле, я сделал; Я просто не знал, верно ли мое предположение.
Гэвин Ховард
2

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

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

while(!CompareAndSet(&lock, false, true));//busy loop won't continue until THIS thread has set the lock to true
//critical section
CompareAndSet(&lock, true, false);

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

чокнутый урод
источник
1

Невозможно, чтобы два (или более) потока получили блокировку одновременно. Например, существует несколько типов методов синхронизации:

Активное ожидание - спин блокировка

псевдокод:

1. while ( xchg(lock, 1) == 1); - entry protocole

XCHG является примером атомарной операции (существует в архитектуре x86), которая сначала устанавливает новое значение для переменной «lock», а затем возвращает старое значение. Атомное означает, что оно не может быть прервано - в примере выше между установкой нового значения и возвращением старого. Атомно - детерминированный результат, несмотря ни на что.

2. Your code
3. lock = 0; - exit protocol

Когда блокировка равна 0, другой поток может войти в критическую секцию - пока цикл заканчивается.

Приостановка потока - например, подсчет семафора

Существует две атомарные операции, .Wait()и .Signal()у нас есть целочисленная переменная, позволяющая вызвать ее int currentValue.

Wait():
if (currentValue > 0) currentValue -= 1;
else suspend current thread;

Signal():
If there exists thread suspended by semaphore wake up one of them
Else currentValue += 1;

Теперь решить проблему критического сечения очень просто:

псевдокод:

mySemaphore.Wait();
do some operations - critical section
mySemaphore.Signal();

Обычно ваш программный поток API должен давать вам возможность указывать максимальное количество параллельных потоков в критической секции семафора. Очевидно, что в многопоточных системах существует больше типов синхронизации (мьютекс, мониторы, двоичный семафор и т. Д.), Но они основаны на вышеуказанных идеях. Можно утверждать, что методы, использующие приостановку потоков, следует отдавать предпочтение активному ожиданию (поэтому процессор не теряется) - это не всегда правда. Когда поток приостанавливается - его заменяет дорогая операция, называемая переключением контекста. Однако разумно, когда время ожидания короткое (количество потоков ~ количество ядер).

FEX
источник