세마포어의 컨센서스 번호는 무엇입니까?

Question

(나는 그렇게 생각합니다) 합의 번호 뮤텍스는 2입니다.

semaphores (pthread_sem_*와 같은)의 컨센서스 번호는 얼마입니까?

조건 변수에 대한 컨센서스 번호 (Pthread_cond_*와 같은)는 무엇입니까?

Answer 1

뮤텍스의 합의 번호는 1입니다. 단일 스레드의 경우 뮤텍스가 대기하지 않을 것이라는 것이 사소한 분명합니다. 그 정의에서, 뮤텍스가 두 스레드에 대해 더 이상 대기하지 않는다는 것이 분명합니다. 따라서 합의 번호는> = 1 및 <2이므로 1이어야합니다.

마찬가지로, 한 스레드를 다른 스레드를 멈추게하여 작동하는 다른 동기화 메커니즘은 합의 번호 1을 가지므로 2 개의 스레드가 공유하는 대기없는 객체를 구성하는 데 사용할 수 없습니다.

Answer 2

답은 뮤 테스 또는 세마포어의 지원되는 작업에 따라 다릅니다. 차단 잠금 만 지원되는 경우 컨센서스 번호는 1입니다. 스레드가 대기하지 않고 뮤텍스를 잠그려고 할 수 있다면 합의 번호는 2입니다. 두 개의 스레드가 있으면 둘 다 뮤트를 잠그려고 시도 할 수 있습니다. 어느 것이 그것을 얻었는지 동의하므로 합의가 있습니다. Mutex가 추가로 스레드가 잠긴 스레드에 대해 추가로 결정할 수 있다면 합의 번호는 무한합니다. 세마포어의 상황은 비슷하다고 생각합니다. 뮤텍스는 카운터 1이있는 세마포어와 동일합니다. 나는 더 큰 카운터로 합의에 도달 할 수 있다고 생각하지 않습니다. 여전히 동일한 작업으로 이어집니다. pthreads는 비 블로킹 잠금을 지원하지만 쿼리는 아니므로 답은 2가됩니다.

조건 변수를 신호하는 것은 스레드가 대기하지 않으면 아무것도하지 않으므로 합의 번호 1이 있습니다.

Answer 3

무한, 확실히? 그러나 그들은 무료로 기다리지 않습니다.

아마도 나는 오해가 될 것입니다. 당신은 뮤 테스에 합의 번호가 2라고 말합니다. 그 소스는 무엇입니까? 차단의 절충으로 여러 스레드가 리소스를 공유 할 수 있도록 설계되었습니다.

원자 테스트 및 세트 합의 번호는 2이지만 차단하지 않습니다.

---

명확히하기 위해 : 세마포어, 뮤 테스 등은 공유 리소스를 마무리하기 위해 단순히 안전하게 만들 수있는 프리미티브입니다 (올바르게하는 한). 그들은 차단할 수 있지만 귀하의 데이터가 안전하다는 것을 보장합니다.

당신이 인용하는 논문은 데이터를 보호하는 데 필요한 프리미티브에 관한 것입니다. 차단없이, 그것은 딱딱한. 동일한 프리미티브는 자물쇠에도 유용 할 수 있지만 이는 좋은 추가입니다.

Answer 4

이 기사만으로도 세마포어는 합의 번호가 2보다 적거나 동일하다는 결론을 내릴 수 있습니다. 이유는 다음과 같습니다.

기사의 세 번째 페이지에서 "Fetch & Add Operation은 상당히 유연합니다. 세마포어에 사용할 수 있습니다 ..." 우리는 Fetch & Add가 합의 번호가 2와 같은 것을 알고 있기 때문에, 해당 논문의 정리 1은 세마포어가 합의 번호가 2보다 적거나 동일하다는 것을 보여주기 위해 사용될 수 있습니다. 증거는 다음과 같습니다.

증거

Fetch & Add에 의한 세마포르의 대기없이 구현이 존재한다고 가정하십시오. 또한 세마포어는 2보다 큰 컨센서스 수를 가지고 있다고 가정합니다. 우리는 Fetch & Add가 2의 합의 번호가 있다는 것을 알고 있습니다. 정리 1에서 우리는 2 개 이상의 프로세스의 시스템을 페치하고 추가하여 세마포어의 대기없이 구현되지 않는다는 결론을 내릴 수 있습니다. . 이는 Fetch & Add의 구현이 존재한다는 가정과 모순됩니다. 따라서 세마포어는 컨센서스 번호가 2보다 적거나 동일해야합니다.

Qed