Конкурирующие атомарные операции могут исчерпать ресурсы друг друга?
Вообразите программу с двумя потоками. Они выполняют следующий код (CAS относится, чтобы Сравнить и Подкачать):
// Visible to both threads
static int test;
// Run by thread A
void foo()
{
// Check if value is 'test' and swap in 0xdeadbeef
while(!CAS(&test, test, 0xdeadbeef)) {}
}
// Run by thread B
void bar()
{
while(1) {
// Perpetually atomically write rand() into the test variable
atomic_write(&test, rand());
}
}
Для потока B действительно ли возможно постоянно вызвать, распараллеливают CAS A для сбоя таким образом, что 0xdeadbeef никогда не пишется, чтобы 'протестировать'? Или естественное планирование дрожит среднее, что на практике этого никогда не происходит? Что, если некоторая работа была сделана в, распараллеливает цикл с условием продолжения A?
2 ответа
Теоретически да. Если бы вы могли каким-то образом заставить два потока работать синхронно, как это
time thread A thread B
---- -------- --------
|| CAS
|| atomic_write
|| CAS
\/ atomic_write
, то CAS никогда бы не вернул истину.
На практике этого никогда не произойдет, когда потоки совместно используют ЦП / Ядро, и маловероятно, если потоки работают на разных ЦП или Ядрах. На практике это невероятно маловероятно для более чем нескольких циклов и астрономически маловероятно для более чем кванта планировщика.
И это если этот код
void foo()
{
// Check if value is 'test' and swap in 0xdeadbeef
while(!CAS(&test, test, 0xdeadbeef)) {}
}
выполняет то, что кажется, а именно извлекает текущее значение test и сравнивает его с test , чтобы увидеть, есть ли у него измененный. В реальном мире итерации CAS будут разделены кодом, который действительно работает. Ключевое слово volatile потребуется, чтобы гарантировать, что компилятор выбрал тест перед вызовом CAS, а не предполагал, что копия, которая может все еще находиться в регистре, все еще будет действительной.
Или значение, с которым вы будете тестировать, будет не текущим значением теста, а скорее каким-то последним известным значением.
Другими словами, этот пример кода является проверкой теории, но вы не стали бы использовать CAS, как это, на практике, поэтому, даже если вы можете заставить это выйти из строя, это не обязательно говорит вам, как это могло произойти. при использовании в реальных алгоритмах.
В таких случаях наверняка может случиться голод. Цитируя страницу википедии ,
Также было показано, что широко доступные атомарные условные примитивы, CAS и LL / SC, не могут обеспечивают безостановочную реализацию многих общих структур данных без затрат памяти , линейно возрастающих по количеству потоков. Поэтому алгоритмы без ожидания редки как в исследованиях, так и на практике.
(См. Ссылку на соответствующей странице для математического доказательства).