경쟁하는 원자 적 연산이 서로 굶주 리지 않을 수 있습니까?

Question

두 개의 스레드가있는 프로그램을 상상해보십시오. 스레드 B는 끊임없이 '시험'에을 0xdeadbeef 기록되지 않습니다 그런 실패 스레드 A의 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()); 
    } 
} 

가 가능 : 그들은 다음 코드 (CAS는 Compare and Swap을 말한다)을 실행? 또는 자연스러운 스케줄링 지터는 실제로 이런 일이 발생하지 않는다는 것을 의미합니까? 일부 작업이 스레드 A의 while 루프에서 수행되면 어떻게됩니까?

Answer 1

이론상으로 그렇습니다. 어떻게 든 두 개의 스레드가 이렇게 lockstep에서 실행되도록 관리 할 수 ​​있다면

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

그런 다음 CAS는 절대로 true를 반환하지 않습니다.

실제로 이것은 스레드가 CPU/코어를 공유 할 때 발생하지 않으며 스레드가 다른 CPU 나 코어에서 실행될 때 발생하지 않을 것입니다. 실제로 그것은 입니다. 이는 매우 이상한 사이클로 인해이 발생하지 않을 가능성이 높으며, 스케줄러 퀀텀 이상으로 천문학적으로 발생하기 쉽지 않습니다.

그리고이 코드

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

test의 현재 값을 가져 인 수행하고 변경되었는지 test에 비교 표시되는 내용 않을 경우 그입니다. 실제로 CAS의 반복은 실제 작업을 수행 한 코드로 구분됩니다. volatile 키워드는 컴파일러가 여전히 레지스터에있을 수있는 복사본이 여전히 유효하다고 가정하기보다는 CAS를 호출하기 전에 테스트를 가져 오는 데 필요합니다.

아니면 테스트의 현재 값되지 않을 것에 대해 테스트 될 값이 아니라 마지막으로 알려진 값의 일종.

다른 말로하면이 코드 예제는 이론을 테스트 한 것이지만 실제처럼 CAS를 사용하지 않으므로이 오류가 발생할 수 있다고해도 반드시 그 방법을 말할 필요는 없습니다 실제 알고리즘에서 사용되면 실패합니다.

Answer 2

그런 경우에는 반드시 기아가 발생할 수 있습니다.

그것은 또한 널리 사용할 수 원자 조건 프리미티브, CAS 및 LL/SC는 구조 메모리 비용 증가 을하지 않고 많은 공통 데이터의 기아없는 구현을 제공하지 수 있다는 것을 보여왔다, the wikipedia page 인용 스레드 수는 입니다. 대기 알고리즘은 이므로 희귀합니다. 연구 중에도 실제로는 입니다.

(수학적 증거는 해당 페이지의 링크를 참조하십시오.)