Могут ли конкурирующие атомные операции голодать друг с другом? - PullRequest
Новая
       59

Могут ли конкурирующие атомные операции голодать друг с другом?

6 голосов
/ 07 февраля 2010

Представьте себе программу с двумя потоками. Они запускают следующий код (CAS относится к Compare и Swap ): 

// 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 никогда не записывается в 'test'? Или естественное дрожание планирования означает, что на практике этого никогда не происходит? Что, если в цикле while потока A была проделана некоторая работа?

Ответы [ 2 ]

6 голосов
/ 07 февраля 2010

В теоретическом плане да. Если вам удастся как-то заставить два потока работать в режиме блокировки, как это 

    time     thread A     thread B
    ----     --------     --------
     ||       CAS
     ||                   atomic_write
     ||       CAS
     \/                   atomic_write

Тогда CAS никогда не вернет true.

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

А вот если этот код 

void foo()
{
    // Check if value is 'test' and swap in 0xdeadbeef
    while(!CAS(&test, test, 0xdeadbeef)) {}
}

делает то, что, по-видимому, делает, то есть извлекает текущее значение test и сравнивает его с test, чтобы увидеть, изменилось ли оно. В реальном мире итерации CAS будут разделяться кодом, который выполняет реальную работу. Ключевое слово volatile понадобится, чтобы убедиться, что компилятор извлек тест перед вызовом CAS, а не предполагать, что копия, которую он все еще имеет в реестре, все еще будет действительной.

Или значение, с которым вы будете тестировать, будет не текущим значением теста, а скорее чем-то вроде последнего известного значения.

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

2 голосов
/ 07 февраля 2010

Голод, конечно, может случиться в таких случаях. Цитирование страницы википедии ,

Также было показано, что широко доступный атомный условный примитивы, CAS и LL / SC, не могут обеспечить голодом реализации многих общих данных структуры без затрат памяти растет линейно в количестве потоки. Алгоритмы без ожидания поэтому редко, как в исследованиях и на практике.

(См. Ссылку на рассматриваемой странице для математического доказательства).

...