Semaphores
공유 자원을 여러 프로세스가 접근하는 것을 막기 위한 추상 자료형. 정수값(자원의 갯수)을 가질 수 있다. P 연산(공유 자원을 획득하는 작업)과 V 연산(사용 후 자원을 반납하는 작업)이 정의되어 있다.
lock을 걸고, lock을 푸는 과정(세마포 갯수가 1인 경우) / 공유 자원을 획득하고 반납하는 일을 세마포가 처리해준다.
semaphore mutex; - 초기 값 1
do {
P(mutex);
critical section
V(mutex);
remainder section
} while(1);busy wait 방식 -> 세마포 자원이 남아있지 않은 경우 계속 while문을 돌기 때문(spin lock)
block & wakeup 방식 -> 자원이 없는 경우 sleep 시켜놓는다.(sleep lock)
block & wakeup
typedef struct {
int value; - 세마포 변수 값
struct process *L; - 세마포 때문에 sleep 되어 있는 프로세스들을 연결하기 위한 큐
} semaphore;세마포를 획득할 수 없다면 block 시킨다.
어떤 프로세스가 자원 반납을 하면 block 된 프로세스 중 하나를 wakeup 시킨다.
p연산 구현(자원 획득)
: 자원에 여분이 있다면 바로 획득, 자원에 여분이 없다면 block 된다.
S.value--;
if(S.value < 0) {
// 해당 프로세스를 S.L에 더해준다.
block();
}v연산 구현(자원 반납)
: 자원 반납 후 기다리면서 잠들어있는 프로세스가 있다면 해당 프로세스를 깨워준다.
S.value++;
if(S.value <= 0) {
// S.L에서 잠들어 있는 프로세스 하나를 깨워준다.
wakeup(P);
}**S.value를 0이하로 비교하는 이유는 P연산시 무조건 --연산을 진행하기 때문에 0이하인 경우가 누군가가 기다리면서 잠들어있다는 뜻이기 때문)
세마포의 2가지 타입
- Counting semaphore
자원의 수가 0이상인 경우
- Binary semaphore(mutex)
0또는 1의 값만 가질 수 있다.
lock/unlock에 주로 사용한다.
문제점
-
deadlock: 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태. 무한정 기다리는 상태. 한정된 자원을 여러 곳에서 사용하려고 할 때 발생
-
starvation
