Могу ли я определить результат гонки данных, не читая значение?

Я пытаюсь лучше понять программирование без блокировки:

Предположим, у нас есть два потока в гонке данных:

// Thread 1
x = 1

// Thread 2
x = 2

Есть ли безблокировочный способ, которым третий поток может узнать результат гонки, не имея возможности прочитать x?

Предположим, что поток 3 использует незаблокированную очередь, и код выглядит так:

// Thread 1
x = 1
queue.push(1)

// Thread 2
x = 2
queue.push(2)

Тогда операции можно было бы расположить так:

x = 1
x = 2
queue.push(1)
queue.push(2)

or

x = 1
x = 2
queue.push(2)
queue.push(1)

Таким образом, наличия очереди без блокировки недостаточно для того, чтобы поток 3 узнал значение x после гонки.


multithreading lock-free
person Taylor    schedule 23.07.2018    source источник
comment
Вам нужно будет определить, с каким языком и моделью потоков вы работаете. В некоторых случаях результатом будет 2, а гораздо позже — 1. Или поток 3 может увидеть 1, а поток 4 — 2.   -  person Sneftel    schedule 23.07.2018
comment
@Sneftel Предположим, сборка x86 или ARM.   -  person Taylor    schedule 23.07.2018
comment
Эти два метода довольно сильно различаются по своим гарантиям параллелизма. В любом случае, однако, вы должны понимать, что нет четко определенного победителя в гонке данных, не говоря уже о том, кого можно определить, не проверяя, кто выиграл.   -  person Sneftel    schedule 23.07.2018
comment
@Sneftel Поскольку архитектуры значительно различаются, вы можете ответить за обе архитектуры ;-). Когда оба потока завершатся, x будет либо иметь значение 1, либо 2. Это неправильно?   -  person Taylor    schedule 23.07.2018
comment
Да, это (потенциально) неправильно. Я могу предложить это как хорошее введение в параллелизм памяти. модели.   -  person Sneftel    schedule 23.07.2018
comment
@Sneftel: Однако есть долгосрочный победитель. Наблюдатели, вращающиеся на x, увидят, что его значение изменится не более двух раз (на 1, а затем на 2 или наоборот), а не на 1, затем на 2, а затем обратно на 1. И ARM, и x86 запрещают изобретать аппаратные средства записи таким образом. На x86 и ARM я думаю, что очередь без блокировок должна будет использовать по крайней мере выпуск/получение для правильной работы, поэтому, если поток 3 действительно получает загрузки обоих элементов очереди, тогда синхронизация rel/acq означает он увидит окончательное значение x. то есть в качестве побочного эффекта/детали реализации очередь делает все предыдущие сохранения в потоке 1/2 видимыми для потока 3.   -  person Peter Cordes    schedule 23.07.2018
comment
Связано: Предотвращение значений Out of Thin Air с помощью барьера памяти в C++. (У меня есть наполовину законченное редактирование того, что я действительно должен закончить, с более подробной информацией и прочим.) Но в любом случае, это обсуждает проблему создания аппаратных средств записи. Это не настоящая вещь, которая может произойти, кроме как в результате неправильного предположения, то есть это не имеет значения. В любом случае никакое реальное оборудование не может прогнозировать стоимость, хотя некоторые ISA достаточно слабы, чтобы это сделать.   -  person Peter Cordes    schedule 23.07.2018
comment
@Sneftel Согласно статье, на которую вы ссылаетесь (это приятно, спасибо!): Единая основная память гарантирует, что всегда будет «победитель»: последняя запись в каждую переменную. Без этой гарантии после того, как (1) и (2) произошли, (3) может увидеть либо 1, либо 2, что сбивает с толку. Так что мое утверждение выше было правильным.   -  person Taylor    schedule 23.07.2018

Ответы (1)


arrow_upward
5
arrow_downward

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

// Notes:
// x == 0
// x and winner are both atomic
// atomic_swap swaps the content of two variables atomically, 
// meaning, that no other thread can interfere with this operation

//thread-1:
t = 1;
atomic_swap(x, t);
if (t != 0) {
    //x was non zero, when thread-1 called the swap operation
    //--> thread-2 was faster
    winner = 1;
}    

//thread-2
t = 2;
atomic_swap(x, t);
if (t != 0) {
    //x was non zero, when thread-2 called the swap operation
    //--> thread-1 was faster
    winner = 2;
}  

//thread-3
while (winner == 0) {} 
print("Winner is " + winner);
person Domso    schedule 23.07.2018
comment
Что делать, если я не знаю начальное значение x? - person Taylor; 23.07.2018
comment
@Taylor: Тогда этот хитрый трюк не сработает, если только поток 1 и поток 2 не будут обмениваться данными друг с другом, чтобы установить x в какое-то известное значение, прежде чем любой из них поменяется местами. Или если они просто общаются и используют эту синхронизацию для установления порядка. У вас есть какая-то практическая причина, потому что простое чтение x после синхронизации выпуска/приобретения с обоими авторами звучит как более дешевый способ узнать окончательное значение. - person Peter Cordes; 23.07.2018
comment
@Taylor x, вероятно, имеет 64-битную версию, но, возможно, вам просто нужно 32; Таким образом, вы можете использовать оставшиеся 32 бита для хранения дополнительной информации, такой как текущий идентификатор потока, в переменной. Но, как писал PeterCordes, без практической проблемы вы не можете оценить какое-либо решение. - person Domso; 23.07.2018
comment
@PeterCordes Боюсь, я не могу обсуждать приложение. Я полагаю, я мог бы задать новый вопрос об определении значения без какой-либо общей памяти, которую я, вероятно, должен был указать. - person Taylor; 23.07.2018
comment
@Taylor: без какого-то дополнительного канала, такого как отправка сигналов или сообщений через сокеты (что, очевидно, намного медленнее, чем общая память, но не разделяемая память), я не думаю, что есть какое-либо решение, кроме ограничивая порядок выполнения магазинов, т.е. вообще не проводя гонки. например возможно, поток 2 ждет, пока он не сможет извлечь данные из очереди, которые поток 1 отправил, прежде чем делать свое сохранение. Или, может быть, потоки могут выполнить xchg, а затем закодировать результат в то, что они отправляют. Но атомарный RMW намного дороже атомарного магазина. В x86 xchg всегда является полным барьером, неявным префиксом lock. - person Peter Cordes; 23.07.2018