Semaphores (추상자료형)

Semaphore S // 정수값, 자원의 개수

typedef struct{
	int value; // Semaphore
    struct process *L; // 프로세스 wait queue
}semaphore

1) P(S): lock을 건다.

while(S<=0) do no-op;
s--;

공유데이터를 획득하는 과정(줄어듬)

2) V(S): lock을 푼다.

s++;

공유데이터를 반납하는 과정

프로그래머가 Semaphores를 이용할 수 있다.

semaphore mutex;
do{
	p(mutex);
    critical section
    v(mutex);
    remainder section
}while(1);

busy-wait는 효율적이지 못하다. 이를 Block & Wakeup 방식으로 해결가능하다(=sleep lock)

Block/Wake up

1) Block

Semaphore를 획득할 수 없으면 그 프로세스를 Block 시킴

2) Wakeup(P)

누군가가 Semaphore를 쓰고 반납하면 Block된 프로세스 중 하나를 깨워서 Wakeup시킴

P(), V()의 구현

S.value와 프로세스의 관계

세마포어 S의 값인 S.value는 사용 가능한 자원의 개수를 나타냅니다. 이를 통해 자원을 관리하고, 프로세스들이 자원에 접근할 수 있는지 여부를 제어한다.

1) S.value > 0:

사용 가능한 자원이 S.value만큼 있다는 의미입니다. 즉, 여러 프로세스가 자원에 접근하려고 할 때 S.value가 1보다 크다면 자원이 충분히 있어서 기다릴 필요 없이 자원을 사용할 수 있다는 뜻이다.

2) S.value == 0:

모든 자원이 사용 중이라는 의미이다. 즉, 현재 자원을 사용할 수 있는 프로세스는 없으며, 새로운 프로세스는 자원이 해제될 때까지 기다려야 한다.

3) S.value < 0:

자원이 부족하여 대기 중인 프로세스가 있다는 의미이다. S.value가 -1이면 한 개의 프로세스가 자원을 기다리고 있고, -2이면 두 개의 프로세스가 기다리고 있다는 뜻이다.

1) P(S)

s.value--; // 자원요청하는 경우니 1개 감소
if(s.value<0){ // 이미 누가 가지고 가서 자원의 여분 없음
	add this process to S.L; // 리스트에다가 이 프로세스를 연결시킴
    block(); // block시킨다.
}

2) V(S)

s.value++; // 자원을 반환하는 경우니 1개 증가
if(s.value<=0){ // 만약 자원을 반환한 후에도 S.value가 0 이하라면, 여전히 대기 중인 프로세스가 있다는 의미

	remove a process P from S.L;
    wakeup(P); // 잠들어 있는 프로세스 하나를 Semaphore 리스트에서 하나 빼서 깨워줌 (대기 큐에서 빼버린다)
}

즉 <=0이라는 것은 대기상태에 놓인 프로세스가 있다는 뜻이기 때문에 한개를 깨워서 또 자원을 준다. (어차피 반납해서 최소 자원 1개는 있는 상태임)

Busy wait vs Block/Wake up

보통은 Block/Wake up이 효율적이다.
CPU를 쓰면서 기다릴 필요 없이 자원을 누군가 가지고 있다고 하면 CPU반납하고 Blocked 된 상태로 돌아가는게 의미있게 이용가능하다.

그러나 overhead가 발생한다. 따라서 critical section의 길이가 짧은 경우에는 Busy/Wait를 하는 것이 나을 수도 있다.

Semaphore의 2종류

1) Counting Semaphore

도메인이 0이상인 임의의 정수값으로 주로 resource counting에 사용
ex> 5, 10(즉 자원의 개수가 여러개 있어서 여분이 있으면 가져다 쓸 수 있다)

2) Binary Semaphore(=mutex)

0또는 1값만 가질 수 있는 semaphore
주로 mutual exclusion(lock/unlock)에 사용
0: 사용중
1: 사용가능함

Deadlock and Starvation

1) Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

P1의 P(S)를 하려고 보니 기다려야한다. P0의 P(Q)도 마찬가지이다.
서로의 것을 요구하다 보니 둘다 같이 대기 상태에 빠진다.

해결방법: 자원을 획득하는 순서를 똑같이 맞춰준다.

결국 P1은대기 P0는 제대로 수행될것이다.

2) Starvation

자원을 자기들끼리 공유하면서 다른 프로세스는 영원히 자기 차례가 오지 못하게 함
= 어떤 특정 친구가 영원히 자원을 얻지 못하고 무한히 기다려야 하는 상황
(어떻게 보면 데드락도 기아의 일종?)