atomics & futex를 사용하여 코드 잠금시 경쟁 조건을 찾는 데 문제가 발생했습니다.

Question

내 Linux-futex & atomic-ops 기반 잠금 프리미티브에서 경쟁 조건 유발 데드락을 디버깅하는 데 끔찍한 시간이 있습니다.

int readers, writer, waiting; 

void wrlock() 
{ 
    int cur; 
    while (atomic_swap(&writer, 1)) spin(); 
    while ((cur=readers)) futex_wait(&readers, cur); 
} 

void wrunlock() 
{ 
    atomic_store(&writer, 0); 
    if (waiting) futex_wake(&writer, ALL); 
} 

void rdlock() 
{ 
    atomic_inc(&waiting); 
    for (;;) { 
     atomic_inc(&readers); 
     if (!writer) return; 
     atomic_dec(&readers); 
     futex_wait(&writer, 1); 
    } 
} 

void rdunlock() 
{ 
    atomic_dec(&waiting); 
    atomic_dec(&readers); 
    if (writer) futex_wake(&readers, ALL); 
} 

atomic_* 및 spin 기능은 매우 명백하다 : 여기에 내가 함께 일하고 있어요 코드 (실제 코드와 동일한 논리는 문제와 관련이없는 데이터 구조에 대한 종속성을 꺼내,)입니다 . Linux futex 운영체제는 futex_wait(int *mem, int val) 및 futex_wake(int *mem, int how_many_to_wake)입니다.

내가 겪고있는 교착 상태 조건은 readers==0, writer==1, waiting==2 및 대기중인 모든 스레드가 futex_wait 인 3 개의 스레드입니다. 어떻게 이런 일이 일어날 지 모르겠다.

그리고 pthread 프리미티브를 사용하지 않기를 바라는 모든 사람은 다른 질문을 위해 저장하십시오. 이것은 glibc/libpthread에 의존하지 않고 동작하는 저수준 코드입니다. 어쨌든이 질문은 아마도 저수준 동시성 검정 마술에 대해 배우기 위해 다른 사람들에게 유용 할 것 같고, 아니면 다른 사람들이 이런 식으로 코드를 작성하는 것을 두려워하지 않을까 ... ;-)

한편, 하드웨어는 x86이기 때문에 코드에 메모리 주문 문제가 있어도 버그라고 생각하지는 않습니다. 필자는 실종 된 퓨 텍스의 미묘한 오용을 추측하고 있습니다. 특히 모든 대기가 회전으로 뒤덮 일 때 코드가 올바르게 작동하므로 빠졌습니다.

wrlock에 대해 생성 된 asm은 다음과 같습니다 (기본적으로 버전 1과 동일 함). 단, 첫 번째 스핀 록에는 별도의 함수 lock이 필요합니다. 처음에 추가 조건부 반환은 "여러 스레드를 실행하지 않으면 손을 벗어납니다"입니다. 0x338 및 0x33c은 readers 및 writer에 해당합니다. call 1af은 실제로 외부 인 futex_wait을 호출하기위한 재배치입니다.

00000184 <wrlock>: 
184: a1 18 00 00 00   mov 0x18,%eax 
189: 55      push %ebp 
18a: 85 c0     test %eax,%eax 
18c: 89 e5     mov %esp,%ebp 
18e: 75 02     jne 192 <wrlock+0xe> 
190: c9      leave 
191: c3      ret 
192: 68 3c 03 00 00   push $0x33c 
197: e8 7e fe ff ff   call 1a <lock> 
19c: 58      pop %eax 
19d: a1 38 03 00 00   mov 0x338,%eax 
1a2: 85 c0     test %eax,%eax 
1a4: 74 ea     je  190 <wrlock+0xc> 
1a6: 6a 01     push $0x1 
1a8: 50      push %eax 
1a9: 68 38 03 00 00   push $0x338 
1ae: e8 fc ff ff ff   call 1af <wrlock+0x2b> 
1b3: a1 38 03 00 00   mov 0x338,%eax 
1b8: 83 c4 0c    add $0xc,%esp 
1bb: 85 c0     test %eax,%eax 
1bd: 75 e7     jne 1a6 <wrlock+0x22> 
1bf: eb cf     jmp 190 <wrlock+0xc> 

Answer 1

이것은 잠재적 인 교착 상태를 보여줍니다. 다음 순서로 3 개의 스레드를 실행하는 단일 프로세서를 가정하십시오.

// to start, 
// readers == 0, writer == 0, waiting == 0 

Reader1 
=================================== 

// in rdlock() 
    atomic_inc(&waiting); 
    for (;;) { 
     atomic_inc(&readers); 

    // if (!writer) has not been executed yet 

    // readers == 1, writer == 0, waiting == 1 

writer 
=================================== 
// in wrlock() 
while (atomic_swap(&writer, 1)) spin(); 
    while ((cur=readers)) futex_wait(&readers, cur) 

    // writer thread is waiting 

    // readers == 1, writer == 1, waiting == 1 
    // cur == 1 



Reader1 
=================================== 

// back to where it was in rdlock() 
     if (!writer) return; 
     atomic_dec(&readers); 
     futex_wait(&writer, 1); 

    // Reader1 is waiting 
    // readers == 0, writer == 1, waiting == 1 

Reader2 
=================================== 

// in rdlock() 
    atomic_inc(&waiting); 
    for (;;) { 
     atomic_inc(&readers); 
     if (!writer) return; 
     atomic_dec(&readers); 
     futex_wait(&writer, 1); 

    // Reader2 is waiting 
    // readers == 0, writer == 1, waiting == 2 

이제 교착 상태에 빠졌습니다.

물론 futex API가 작동하는 방식을 이해하지 못했을 수도 있습니다. 블록 futex_wait() (예상 값이 맞았 기 때문)은 그 주소에 대해 futex_wake() 호출이있을 때까지 차단 해제되지 않는다고 가정합니다.

atomic_xxx() 작업이 futex_wait()의 차단을 해제 할 수없는 경우이 분석은 올바르지 않습니다.

마지막으로, 이것이 여러분에게 일어난 일이라면 가능한 해결책에 대해 생각할 기회가 없었습니다 ...

Answer 2

내 생각 엔 메모리 주문 문제입니다. x86 메모리 모델에 대해서는 잘 모르겠지만, futex_* 호출에 대해 메모리 울타리가 필요하다고 강하게 의심됩니다. x86이 한 코어가 다른 코어의 메모리 내용을 메모리 셀과 같은 순서로 업데이트한다는 것을 x86이 보증한다는 것을 이해합니다. 그러나 한 코어의 쓰기가 다른 코어에 즉시 표시 될 수 있다는 강한 가정에 의존하고있는 것처럼 보입니다. . 예를 들어 코어 A가 rdlock이고 rdunlock을 실행했다고 가정 해 보겠습니다. 이제 waiting과 readers이 모두 지워지지만이 정보는 코어 B가 wrlock을 시도 할 때까지는 코어 B가되지 못했습니다. 코어 B는 writer을 성공적으로 획득했지만 현재 readers이 있음을 확인합니다. writer에 대한 업데이트는 rdunlock이 futex_wake(&readers)이 필요한지 확인한 시점까지 코어 A에 게시하지 않았으므로 업데이트되지 않았습니다. 이것은 증상을 나타낼 수 있으며, futex_* 콜이 단순한 스핀으로 대체되면 복구 할 수있는 속성을 갖게됩니다. 너에게 이해가 되니?

흠, while ((cur=readers)) futex_wait(&readers, cur);은 ((cur==readers))...?이어야합니다.