기존 Mutual Exclusion 기법의 Busy waiting을 방지하기 위한 기법이다. (다익스트라가 제안)
정의
-
정수형 변수
-
Protected variable로 P(), V()에 의해서만 접근가능하다. (Encapsulation)
-
각 세마포어는 Sleep Queue 가지고 있다. => busy waiting 방지
Semaphore Operations
- P(S) => wait
- S가 0이하이면 Sleep Queue에 넣어 대기한다.
if(S>0)
then S = S-1;
else
wait in the queue; => sleep- V(S) => signal
- sleep queue에 대기 중인 프로세스가 있다면 깨운다.
- 없다면 S를 증가시킨다.
if (wating processes on Q)
then wakeup one of them
else S = S+1;
Semaphore 종류
1. Binary Semaphore (이진 세마포어)
-
0 또는 1의 값을 가지는 세마포어
-
Mutual Exclusion이나 Process Synchronization에 사용
2. Counting Semaphore (계수 세마포어)
-
양수인 정수형 값을 가지는 세마포어
-
producer-consumer 문제를 해결할 때 사용
Semaphore 활용
1. Mutual Exclusion
-
active가 1일 때는 Critical Section에 프로세스가 없음.
-
active가 0일 때는 Critical Section에 프로세스 존재.
2. Producer-Consumer Problem
-
생산자는 계속해서 메세지를 생산하고 소비자는 이를 계속해서 가져간다.
-
생산자는 동시에 메세지를 생산하면 안되고 마찬가지로 소비자는 한 메세지를 동시에 가져가면 안된다. (싱글 버퍼일 경우)
➡️ 따라서 상호 배제가 필요하다.
➡️ consumed, produced라는 세마포어 변수를 가진다.
3. Reader-writer problem
-
Reader는 동시에 메세지를 읽을 수 있다.
-
writer는 동시에 메세지를 쓸 수 없다.
-
Read와 Write는 동시에 이뤄질 수 없다.
-
앞 쪽의 nreaders==0의 뜻은 첫 번째 reader가 읽으러 가는 중이라는 뜻이다. 즉 write를 하지 못하게 막아야한다.
-
뒤 쪽의 nreaders==0은 모든 reader들이 다 읽었다는 뜻이다.
Spinlock
- Busy Waiting을 하는 세마포어라고 생각하면 된다.
P(S) {
while (S <= 0);
S--;
}
V(S) {
S++;
}
-
특징
- 멀티 프로세서 시스템이나 멀티 코어 시스템에 사용된다.
- Busy Waiting을 한다.
- 짧은 시간에 lock이 걸릴 경우엔 유용하다.
세마포어 같은 경우는 Busy Waiting이 없지만 Sleep을 하기 때문에 커널이 개입되는 Context Switching이 발생한다. (overhead)
