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

Question

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

Answer 1

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

 
    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, так что даже если бы вы могли это терпеть неудачу, это не обязательно скажет вам, как это возможно сбой при использовании в реальных алгоритмах.

Answer 2

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

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

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