•
참고 강의
contents
Semaphores
추상 자료형
•
정수값
•
두 가지 atomic 연산에 의해서만 접근 가능 - P(S), V(S)
•
세 개의 특수한 명령들만 접근할 수 있게 허용되는 보호된 변수
공유 자원을 획득하고 반납하는데 세마포어가 처리해준다.초기화 명령(optional)
P(S) : 공유 데이터를 획득하는 과정 - wait, down
V(S) : 공유 데이터를 반납하는 과정 - signal, up
•
busy-wait(= spin lock) 문제는 계속 발생한다.
•
세마포어에 대한 명령들은 각각 분리되지 않고 수행될 수 있도록 구현해야 하며, 같은 세마포어에 대해서 동시에 실행되지 못한다. → P(S) 중이라면 V(S) 불가능
•
세마포어를 활용하면 상호배제뿐만 아니라 프로세스 간의 동기화도 쉽게 구현 가능
Critical Section of n Processes
semaphore mutex; initially 1
do {
P(mutex)
critical section
V(mutex)
remainder section
} while(1);
C
복사
전에 있던 Algorithm과는 다르게 P, V 연산만 해주면 된다.
→ 구연을 어떻게 할 것인지는 시스템의 몫
•
Block & Wakeup 방식(= sleep lock)으로 구현될 수 있다.
◦
lock를 못 얻으면 쓸데없이 CPU를 사용하는 것이 아니고 잠들어 버린다.
Block / Wakeup Implementation
typedef struct {
int value; // 세마포어 변수값
struct process *L; // 잠든 값들 연결하는 Queue
} semaphore;
C
복사
•
Block : 커널은 block을 호출한 프로세스를 suspend 시킴. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
•
Wakeup : block된 프로세스 P를 wakeup시킴. 이 프로세스의 PCB를 ready queue로 옮김
당장 세마포어를 얻을 수 없는 상태라면 해당 프로세스를 Block → 누군가가 쓰고 반납을 하게 되면 Block된 프로세스 중에 하나를 깨워서 Wakeup 시킴
P(S)
S.value--;
if(S.value < 0) {
add this process to S.L;
block();
}
C
복사
•
자원의 여분이 없다면 block 된다.
V(S)
S.value++;
if(S.value <= 0) {
remove a process P from S.L;
wakeup(P);
}
C
복사
•
반납을 하고 끝내는 것이 아니고 이 자원을 기다리면서 잠든 프로세스를 깨우는 작업이 필요
•
자원을 내놓았음에도 음수라는 것은 잠든 프로세스가 있다는 것
여기서의 S.value는 전과 다른 의미를 가진다.(상황을 나타냄)
•
양수 : 자원의 여분이 있음
•
음수 : 기다리는 프로세스들이 잠들어 있음
Busy-wait v.s. Block/wakeup
일반적으로 Block/wakeup이 더 효율적이다.
•
CPU를 더 의미있게 이용하기 때문에
But, Block/wakeup overhead 존재
•
Ready 상태에서 Sleep 상태로 바꾸고, Sleep 상태에서 Ready 상태로 바꾸는 일이 필요
→ Overhead가 발생
•
Section의 길이가 짧은 경우 - busy-wait하는 것이 오버헤드가 덜 듦
•
Section의 길이가 긴 경우 - while문만 돌면서 낭비되는 CPU 시간이 많기 때문에 block/wakeup이 필수
추가
•
Block/wakeup : CPU의 낭비를 막지만 Wake한 P가 바로 CPU를 받아서 Running하지 못한다. 즉각 반응이 늦어진다!
◦
조건이 만족되면 Wake시켜서 Ready Queue로 보낸다. Ready의 프로세스들과 경쟁을 해서 CPU를 받아야 하기 때문.
◦
커널이 개입하기 때문에 Ready로 바꾸는 동안 CPU 시간을 OS가 사용
•
Busy-wait : CPU를 wait용도로 busy시키기에 유용한 곳에 활용하지 못한다는 문제 발생 → CPU 낭비
◦
wait한 상황이 만족되면 while문에서 벗어나서 critical section에 바로 진입 가능하다.
Two Types of Semaphores
1.
Counting semaphore
: 도메인이 0 이상인 임의의 정수값
•
자원의 갯수가 여러개인 경우(여분이 있으면 가져다 쓸 수 있는)
•
주로 resource counting에 사용
2.
Binary semaphore(= mutex)
: 0 또는 1 값만 가질 수 있는 semaphore
•
자원의 갯수가 하나인 경우
•
주로 mutual exclusion(lock/unlock)에 사용
Deadlock and Starvation
Semaphore에서 발생할 수 있는 문제
•
S를 획득하려면 영원히 기다려야 한다 → P0은 Q까지 다 사용하고 나서 S를 내놓을 수 있다.
•
영원히 조건을 충족하지 못하는 상태 → Deadlock !
Deadlock
: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
해결법
자원을 획득하는 순서를 똑같이 맞춰주면 해결 가능하다.
Starvation
: indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
•
특정 프로세스들만 자원을 자기들끼리 공유하면서 다른 프로세스는 영원히 자기 차례가 오지 못하게 하는 것