카운팅 세마포의 사용 사례

Question

명확해야 함 : 대부분 임베디드 작업을 수행합니다. 즉, 마이크로 컨트롤러에서 C 및 일종의 실시간 커널입니다. 실제로이 질문은 플랫폼 독립적이어야합니다.

저는 Michael Barr : Mutexes and Semaphores Demystified의 멋진 기사와이 related answer on StackOverflow을 읽었습니다. 바이너리 세마포어가 무엇인지, 뮤텍스가 무엇인지 명확히 이해하고 있습니다. 훌륭합니다.

솔직히 말하면 나는 소위 카운팅 세마포어 (semaphore) (즉, 최대 카운트가 1보다 큰 세마포어)가 무엇인지를 결코 알지 못하고 여전히 이해할 수 없습니다. 어떤 경우에 사용해야합니까?

필자는 전에 Michael Barr의 기사를 읽기 전에 "과 같은 말을했습니다. 특정 침대 수의 호텔 방이있을 때 사용할 수 있습니다. 침대 수 그 방의 키 숫자와 마찬가지로 세마포어의 최대 값입니다. "".

아마도 멋지게 들리 겠지만 프로그래밍 실습에서는 이러한 상황을 결코 경험할 수 없었습니다. (그리고 상상할 수도없는) Michael Barr는 이러한 접근 방식이 잘못되었다고 생각합니다.

그런 다음 필자가이 기사를 읽은 후, 일종의 FIFO 버퍼가있을 때 아마도 사용했을 것으로 생각됩니다. 버퍼의 용량이 10 개의 요소라고 가정하고 우리는 A (생산자)와 B (소비자)의 두 가지 작업을 수행합니다. 그 다음 :

• 세마포어의 최대 개수는 10으로 설정해야합니다.
• A가 버퍼에 데이터를 넣으려는 경우, signal은 세마포어입니다.
• B가 버퍼에서 데이터를 가져 오려면, wait은 세마포어입니다.

음,하지만 작동하지 않습니다

• 무엇 A는 FIFO에 새 데이터를 넣어하려고하지만 여지가없는 경우? 장소를 기다리는 방법 : 새 데이터를 입력하기 전에 signal을 호출해야합니까? (signal은 최대 카운트 < 최대 카운트까지 기다릴 수 있어야합니다)? 그렇다면, 데이터가 실제로 FIFO에 저장되기 전에 세마포어가 신호를받습니다. 이것은 잘못된 것입니다.
• 세마포어는 적절한 동기화에 충분하지 않습니다. FIFO 자체도 동기화되어야합니다. 그런 다음 고전적인 TOCTTOU 문제를 생성합니다. 세마포어가 이미 신호를 받거나 대기하는 동안 시간이 있지만 FIFO가 아직 수정되지 않았습니다.

그럼, 그 짐승을 사용해야 할 때, 카운팅 세마포어를 사용해야합니까?

Answer 1

'클래식'예제는 실제로 생산자 - 대기열입니다.

무제한 대기열에는 하나의 세마포, (대기열 항목을 계산하기 위해) 하나의 mutex 보호 스레드 안전 대기열 (또는 동등한 잠금없는 스레드 안전 대기열)이 필요합니다. 세마포어는 0으로 초기화됩니다. 제작자는 뮤텍스를 잠그고 큐에 개체를 푸시하며 뮤텍스를 잠금 해제하고 세마포 신호를 보냅니다. 소비자는 세마포어에서 기다리고, 뮤텍스를 잠그고, 객체를 팝하고 뮤텍스를 해제합니다.

제한된 큐에는 두 개의 세마포가 필요합니다 (항목을 계산할 때 하나의 '카운트', 여유 공간을 계산할 수있는 다른 '사용 가능') 및 뮤텍스로 보호 된 스레드 안전 큐 또는 이와 동등한 잠금없는 스레드 안전 대기열).'count'는 0으로 초기화되고 빈 큐에있는 빈 공간 수에 '사용 가능'합니다. 제작자는 'available'을 기다리고, 뮤텍스를 잠그고, 큐에 객체를 푸시하고, 뮤텍스를 잠금 해제하고 'count'신호를 보냅니다. 소비자는 '카운트'를 기다리고, 뮤텍스를 잠그고, 객체를 팝하고, 뮤텍스를 잠금 해제하고 '사용 가능함'신호를 보냅니다.

이것은 세마포어 용으로 고전적으로 사용되어 왔으며 영원히 계속되었습니다. (물론, Dijkstra 이후로, 어쨌든 :). 수십억 번 시도되었지만 모든 생산자/소비자에게 제대로 작동합니다.

토트 (TOCTTOU) 쟁점이없고, 코너 케이스도, 레이스도 없습니다.

'뮤텍스'기능은 또 다른 세마포어에 의해 제공 될 수 있습니다.이 기능은 '2 개의 세마포어'를 무제한으로 '3 개의 세마포어'로 묶을 수 있습니다.

Answer 2

필자는 일종의 FIFO 버퍼가있을 때 사용했을 것으로 추측됩니다. 버퍼의 용량이 10 개의 요소라고 가정하고 우리는 A (생산자)와 B (소비자)의 두 가지 작업을 수행합니다. 그 다음 :

• 세마포어의 최대 개수는 10으로 설정해야합니다.
• A가 버퍼에 데이터를 넣으려는 경우 A는 세마포 신호를 보냅니다.
• B가 버퍼에서 데이터를 가져 오려는 경우 B는 세마포어를 기다립니다.

이것은 생산자 - 소비자 시나리오에서 사용되는 세마포어가 아닙니다. 표준 솔루션은 빈 슬롯 (사용 가능한 슬롯의 수로 초기화 됨)과 채워진 슬롯 (0으로 초기화 됨)을위한 두 개의 카운팅 세마포어를 사용하는 것입니다.

제작자는 항목을 넣기 위해 빈 슬롯을 할당하려고하므로 빈 슬롯에 할당 된 세마포어로 wait으로 시작합니다. 소비자는 채워진 슬롯을 "할당"(확보)하려고하므로 채워진 슬롯에 할당 된 세마포어로 wait- 시작합니다.

작업을 마친 후에는 슬롯을 빈에서 채우기로, 그리고 채우기에서 빈으로 각각 변환하기 때문에 다른 세마포를 신호로 보냅니다.

표준액 방식 :

semaphore mutex = 1; 
semaphore filled = 0; 
semaphore empty = SIZE; 

producer() { 
    while (true) { 
     item = produceItem(); 
     wait(empty); 

     wait(mutex); 
     putItemIntoBuffer(item); 
     signal(mutex); 

     signal(filled); 
    } 
} 

consumer() { 
    while (true) { 
     wait(filled); 

     wait(mutex); 
     item = removeItemFromBuffer(); 
     signal(mutex); 

     signal(empty); 
     consumeItem(item); 
    } 
} 

나는 카운트 세마포어이 상황에서 잘 될 것 같아요.

---

또 다른

, 어쩌면 간단한 예는 식당 철학자 시나리오에서 교착 상태를 피하기위한 카운팅 세마포어를 사용 할 수있다. 교착 상태는 모든 철학자가 동시에 앉아서 (말하자면) 왼쪽 포크를 선택했을 때만 발생할 수 있기 때문에 동시에 모든 것을 식당에 허용하지 않아 교착 상태를 피할 수 있습니다. 이것은 철학자의 수보다 적은 수로 초기화되는 카운팅 세마포 ( enter)에 의해 달성 될 수 있습니다.

는

한 철학자의 프로토콜은 다음이된다 :

wait(enter) 

wait(left_fork) 
wait(right_fork) 
eat() 
signal(left_fork) 
signal(right_fork) 

signal(enter) 

이 모든 철학자가 동시에 식당에서 할 수 없도록합니다.