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

Question

Представьте себе программу с двумя потоками.Они выполняют следующий код (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 никогда не записывается в 'test'?Или естественное дрожание при планировании означает, что на практике этого никогда не происходит?Что, если какая-то работа была выполнена внутри цикла while потока A?

Answer 1

Теоретически, да.Если бы вам удалось каким-то образом заставить два потока работать синхронно, вот так

    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 чтобы посмотреть, изменилось ли это.В реальном мире итерации центров сертификации были бы разделены кодом, который выполнял реальную работу.Тот Самый volatile ключевое слово было бы необходимо для гарантии того, что компилятор извлек test перед вызовом CAS, а не для предположения, что копия, которую он все еще может иметь в реестре, все еще будет действительной.

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

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

Answer 2

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

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

(Математическое доказательство смотрите по ссылке с соответствующей страницы).