리눅스 3.0:futex-lock 교착 상태 버그?

StackOverflow https://stackoverflow.com//questions/9621254

문제 

// SubFetch(x,y) = atomically x-=y and return x (__sync_sub_and_fetch)
// AddFetch(x,y) = atomically x+=y and return x (__sync_add_and_fetch)
// CompareWait(x, y) = futex(&x, FUTEX_WAIT, y) wait on x if x == y
// Wake(x, y) = futex(&x, FUTEX_WAKE, y) wake up y waiters

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

void lock()
{
    while (true)
    {
        if (SubFetch(x, 1) == 0)
            return;

        x = -1;

        CompareWait(x, -1);
    }
}

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

    x = 1;

    Wake(x, 1);
}

private:
    int x;
};

Linux 3.0은 다음과 같은 시스템 호출을 제공합니다. 푸텍스, 최근 pthread_mutex 구현을 포함하여 많은 동시성 유틸리티의 기반이 됩니다.코드를 작성할 때마다 기존 구현을 사용하거나 직접 작성하는 것이 프로젝트에 더 나은 선택인지 항상 고려해야 합니다.

위는 futex와 의미 설명을 기반으로 한 잠금(뮤텍스, 1개의 허가 계산 세마포어)의 구현입니다. 남자 퓨텍스(7)

여기에는 여러 스레드가 잠금 및 잠금 해제를 수천 번 시도한 후 x == -1 상태가 되고 모든 스레드가 CompareWait에 갇히게 되는 교착 상태 버그가 포함된 것으로 보입니다. 그러나 아무도 잠그다.

버그가 어디에 있는지 볼 수 있는 사람이 있나요?

업데이트: futex(7)/semantics가 너무 깨져서 조금 놀랐습니다.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
도움이 되었습니까?

해결책

문제는 명시적으로 -1을 할당한다는 것입니다. x 만약에 SubFetch 잠금을 획득하지 못했습니다.이것은 잠금 해제와 함께 경주합니다.

  1. 스레드 1이 잠금을 획득합니다. x==0.
  2. 스레드 2는 잠금을 획득하려고 시도합니다.그만큼 SubFetch 세트 x -1로 변경한 다음 스레드 2가 일시 중단됩니다.
  3. 스레드 1이 잠금을 해제합니다.그만큼 AddFetch 세트 x 0으로 설정하므로 코드는 명시적으로 설정합니다. x 1로 전화하고 Wake.
  4. 스레드 2가 깨어나 설정됩니다. x -1로 변경한 다음 호출합니다. CompareWait.

스레드 2가 이제 대기 중으로 멈춰 있습니다. x -1로 설정했지만 스레드 1이 이미 잠금을 해제했기 때문에 깨울 사람이 주변에 없습니다.

다른 팁

FUTEX 기반 뮤텍스의 적절한 구현은 ULRICH DREPPER의 종이에 설명되어 있습니다. "FUTEXES는 까다로운"

http://people.redhat.com/drepper/futex.pdf <./ P>

코드뿐만 아니라 왜 올바른지에 대한 매우 자세한 설명도 포함합니다.용지의 코드 : 

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;
};
.

용지의 코드를 코드와 비교하면 차이점을 발견

가 있습니다

(x== 2 || 비교 (x, 1, 2))

FUTEX의 값을 직접 사용하는 반면, DREPPER는 이전 SCIRAMERSSIGN ()에서 반환 값을 사용합니다.그 차이는 성능에만 영향을 미치지 않을 것입니다.

잠금 해제 코드도 다르지만 의미 론적으로 동일한 것으로 보입니다.

어떤 경우에도 Drepper의 코드를 편지에 따라갈 수 있도록 강력히 조언합니다.그 종이는 시간의 테스트를 서서 많은 피어 리뷰를 받았습니다.당신은 당신 자신을 굴릴 수 없게됩니다.

세 개의 스레드 A, B, C가 있는 이 시나리오는 어떻습니까?

이 시나리오의 초기 상태는 다음과 같습니다.

  • 잠금을 유지하는 스레드 A
  • 스레드 B는 아직 잠금을 놓고 경쟁하지 않습니다.
  • 스레드 C CompareWait()
  • x == -1 C가 잠금 획득에 실패했을 때부터
        A                  B                C
    ==============   ================  ===============
     AddFetch()
     (so x == 0)
                       SubFetch()
                       (so x == -1)

     x = 1

                       x = -1

     Wake()

이 시점에서 B 또는 C가 차단 해제되었는지 여부에 관계없이 다음 결과를 얻지 못합니다. 0 그들이 언제 SubFetch().

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top