Linux 3.0 : futex-lock 교착 상태 버그?

Question

Linux 3.0은 futex이라는 시스템 호출을 제공합니다.이 시스템 호출에는 최근의 pthread_mutex 구현을 포함하여 많은 동시성 유틸리티가 기반을두고 있습니다. 코드를 작성할 때마다 항상 기존 구현을 사용할지 직접 작성 할지를 고려해야합니다.

위는 퓨 텍스에 따라 잠금 (뮤텍스, 1 허가 카운팅 세마포어)의 구현과 여러 스레드가 잠금 및 잠금을 해제하려고하는 이에 후 교착 버그가 포함되어있는 것 같습니다 man futex(7)

의 의미 설명입니다 수천 번 스레드는 x == -1 인 모든 스레드가 CompareWait에 고정 된 상태가 될 수 있지만 아무도 잠금을 보유하지는 않습니다.

누구에게 버그가 있는지 알 수 있습니까?

업데이트 : futex (7)/의미가 너무 깨졌습니다. 나는 Lock을 완전히 다음과 같이 다시 작성했습니다 ... 지금이게 맞습니까?

// CompareAssign(x,y,z) atomically: if (x == y) {x = z; ret true; } else ret false; 

struct Lock 
{ 
Lock() : x(0) {} 

void lock() 
{ 
    while (!CompareAssign(x, 0, 1)) 
     if (x == 2 || CompareAssign(x, 1, 2)) 
      CompareWait(x, 2); 
} 

void unlock() 
{ 
    if (SubFetch(x, 1) == 0) 
     return; 

    x = 0; 

    Wake(x, 1); 
} 

private: 
int x; 
}; 

생각이 여기에

x는 다음과 같은 세 가지 상태를 가지고 있다는 것입니다 :

0: unlocked 
1: locked & no waiters 
2: locked & waiters 

Answer 1

문제는 SubFetch가 잠금을 획득하지 못할 경우 명시 적 -1 x에 할당하는 것입니다. 이 경기는 잠금 해제됩니다.

1. 스레드 1은 잠금을 획득합니다. x==0.
2. 스레드 2가 잠금을 획득하려고 시도합니다. SubFetch은 x을 -1로 설정하고 스레드 2가 일시 중단됩니다.
3. 스레드 1은 잠금을 해제합니다. AddFetch은 x을 0으로 설정하므로 코드에서 x을 명시 적으로 1로 설정하고 Wake을 호출합니다.
4. 스레드 2가 깨어나서 x을 -1로 설정 한 다음 CompareWait을 호출합니다.

스레드 (2) -1 x 세트로, 지금 붙어 대기이지만, 스레드 1이 이미 잠금을 출시했습니다으로 주위를 해제 할 일이 없다.

Answer 2

방법 세 가지 스레드, A, B 및 C와이 시나리오에 대한

이 시나리오의 초기 상태는 있습니다

• 스레드가
• 스레드 B가 경쟁하지 잠금을 보유 잠금 C가 잠금을 획득하는 데 실패 할 때부터 CompareWait()
• x == -1에서 아직
• 스레드 C
B 또는 C가 차단 해제 여부를이 시점에서

 
     A     B    C 
    ============== ================ =============== 
    AddFetch() 
    (so x == 0) 
         SubFetch() 
         (so x == -1) 

    x = 1 

         x = -1 

    Wake() 

, 그들은 0 그들이 SubFetch()의 결과를 얻을 수 없습니다.

Answer 3

퓨 텍스 기반의 뮤텍스의 적절한 구현은 울리히 드레 퍼의 논문 "퓨 텍스가 교묘"에 설명되어 있습니다

http://people.redhat.com/drepper/futex.pdf

그것은 코드뿐만 아니라 그것이 올바른 이유의 아주 자세한 설명뿐만 아니라 포함 . 종이의 코드 :

class mutex 
{ 
public: 
mutex() : val (0) { } 
void lock() { 
    int c; 
    if ((c = cmpxchg (val, 0, 1)) != 0) 
    do { 
     if (c == 2 || cmpxchg (val, 1, 2) != 0) 
     futex_wait (&val, 2); 
    } while ((c = cmpxchg (val, 0, 2)) != 0); 
} 
void unlock() { 
//NOTE: atomic_dec returns the value BEFORE the operation, unlike your SubFetch ! 
    if (atomic_dec (val) != 1) { 
    val = 0; 
    futex_wake (&val, 1); 
    } 
} 
private: 
    int val; 
}; 

코드와 종이의 코드를 비교, 나는 당신이

차이를 발견

경우 (엑스 == 2 || CompareAssign (X, 1 , 2))

Futex의 값을 직접 사용하는 반면 Drepper는 이전 CompareAssign()의 반환 값을 사용합니다. 이 차이는 성능에만 영향을줍니다.

잠금 해제 코드도 다르지만 의미 상 동일합니다.

어쨌든 나는 Drepper의 코드를 편지에 따르는 것이 좋습니다. 그 논문은 시간의 테스트를 견뎌 왔고 많은 동료 리뷰를 받았습니다. 당신은 자신의 것을 굴리지 않고 아무것도 얻지 못합니다.