티켓 잠금은 대기 시간 제한이 있습니까? (특정 가정 하에서)

Question

다음과 같이 보일 수있는 티켓 잠금 장치에 대해 이야기하고 있습니다 (의사 C 구문).

 unsigned int ticket_counter = 0, lock_counter = 0; 

void lock() { 
    unsigned int my_ticket = fetch_and_increment(ticket_counter); 

    while (my_ticket != lock_counter) {} 
} 

void unlock() { 
    atomic_increment(lock_counter); 
} 

이러한 티켓 잠금이 대기 섹션 S에 대한 액세스를 동기화한다고 가정 해 봅시다. 임계 섹션은 정확히 C 사이클/명령어를 취합니다. 시스템에있는 대부분의 P 스레드가 있다고 가정 할 때 대기 잠금 바운드 티켓 잠금을 사용하는 S의 동기화가 있습니까?

제 생각에는 티켓 잠금 장치가 공평하고 기다리기위한 상한선이 O (p * c)이기 때문입니다.

실수를합니까? 나는 조금 혼란 스럽다. 나는 다음과 같은 이유 때문에 잠금이 제한적이지 않은 것을 의미한다고 항상 생각했다. "대기열, 스택, 우선 순위 대기열, 집합 또는 목록의 대기없는 구현을 원자 단위로 구성하는 것은 불가능하다. 레지스터." (Multiprocessor Programming, Herlihy and Shavit의 기술에 대한 결론 5.4.1)

그러나 티켓 잠금 장치 (그리고 다른 공정한 잠금 메커니즘)가 위에서 언급 한 가정 하에서 대기 상태에 묶여 있다면, 대기열, 스택 등의 바운드 된 대기없는 구현의 구현 (사실 내가 직면 한 문제입니다.)

---

"다중 프로세서 프로그래밍의 예술"에서 제한된 대기 시간의 정의를 상기 해보십시오. p.59 Herlihy와 Shavit :

"모든 호출이 유한 단계의 수의 실행을 끝내도록 보장하면 메서드는 wait-free입니다. 메서드 호출이 걸릴 수있는 단계. "

Answer 1

글쎄, 난 당신이 몇 가지주의로, 올바른 생각합니다.

을 즉, 경계 대기 무료 속성은 임계 섹션 S가 비 선점 형인 경우에만 유지됩니다. 이는 (임계 구역에서 인터럽트를 비활성화하여) 커널 공간 코드에만 사용할 수 있다고 가정합니다. 그렇지 않으면 OS가 다른 스레드로 전환하려고 결정할 수 있습니다. 그리고 나서, 대기 시간은 제한이 없다. no

또한, 커널 코드의 경우, p는 소프트웨어 스레드의 수가 아니라 하드웨어 스레드의 수 (또는 코어, CPU의 코어 수)라고 가정한다. CPU 코어 당 여러 스레드를 지원하지 않음). 대부분의 소프트웨어 스레드는 한 번에 실행 가능하므로 S가 비 선점 적이기 때문에 잠금 대기중인 대기 스레드가 없습니다.