[OS] Semaphore에 대해

앞선 포스트에서 확인할 수 있듯이, Process Synchronization 문제에서 Critical Section 처리 방식은 상당히 중요하다.

OS가 동기화 문제를 일으키지만, 앞선 포스트에서 봤듯 소프트웨어적인 알고리즘으로는 비효율적인 문제와 과잉 양보 문제가 발생하므로, 하드웨어적 접근이 필요하다.

 

하드웨어 적으로 Test & Modify를 원자적으로 수행할 수 있도록 지원하게 되면, Critical Section 문제는 간단히 해결된다.

Synchronization variable
boolean lock = false;

Process P_i
do {
	while(Test_and_Set(lock));
    critical section
    lock = false;
    remainder section
}

이 pseudo code를 구현하는 방법으로는 두 가지가 있다. 

 

Semaphore

semaphore는 추상 자료형으로, integer variable이며 아래의 두 가지 연산만 접근이 가능하다. 

# 1 공유 데이터 획득
P(S); while(S <= 0) do no-op;
	  S--;
# 2 공유 데이터 반납
V(S);
	  S++;

# 1은 lock을 획득하는 것으로, 획득하고 작업을 수행하는 것을 뜻한다. S는 여분의 자원 개수를 의미하며, 이때 자원은 해당 프로세스가 작업하는 자원의 개수를 의미한다.

 

# 2는 unlock을 실행하는 것이다. 이는 작업을 다 끝마치고 다른 프로세스에게 해당 자원에 대한 접근을 가능하게 만들며, S++ 연산으로 초기화 작업을 거친다.

 

Critical Section of n Processes

semaphore mutex;

do {
	P(mutex);
    critical section
    V(mutex);
    remainder section 
} while(1);

다음과 같은 코드를  busy-wait라고 한다. busy-wait는 앞선 방법과 같이 V(mutex)를 하지 않으면 spin lock 문제가 발생하여 비효율적인 문제가 발생한다. 이를 해결하기 위해 Block & WakeUp 방식의 구현을 해보기로 한다.

 

typedef struct

{	int value; /*Semaphore*/
	struct process *L; /*process wait queue*/
} semaphore;

Semaphore를 다음과 같이 정의한다. 

 

block

kernel은 block을 호출한 프로세스를 suspend시키며, 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다.

 

wakeup(P)

block된 프로세스 p를 wakeup시키며, 이 프로세스의 PCB를 ready queue로 옮긴다.

 

 

P(S);
S.value--; /*prepare to enter*/
if (S.value < 0) /*Oops, negative, I can't enter*/
{ 
	add this process to S.L;
    block();
};


V(S); 
S.value++;
if (S.value <= 0) {
	remove a process P from S.L
    wakeup(P);
}

여기서 S.value가 0보다 작거나 같은 상황일 때라 함은 누군가 Critical Section에 들어가고 싶지만 자원이 없어 잠들어 있는 상황을 의미한다.

 

Semaphore에는 Counting Semaphore와 Binary Semaphore가 있다.

두 개의 차이점은 무엇일까?

 

Counting Semaphore	Binary Semaphore
도메인 0 이상의 임의 정수값	0, 1 값만 가질 수 있는 semaphore
주로 resource counting	주로 mutual exclusion (clock/unlock Algorithm에 사용)

Deadlock

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

 

위 알고리즘은, 다음과 같은 starvation 현상을 초래한다. 

 

Infinite blocking

프로세스가 suspend된 이유에 해당하는 Semaphore Queue에서 빠져나갈 수 없는 현상

 

이 현상을 해결하기 위해서는, semaphore 호출의 순서를 지정해주어야 한다.

이를 구현하기 위해 Bounded-Buffer Problem을 해결한 알고리즘을 도입했다. 

 

Bounded-Buffer Problem

위 그림과 같이 Producer(Write)와 Consumer(Read) 두 객체를 두고, 공유 데이터의 제어권을 각각 두어 공유 데이터를 조작하게 한다. 또한 Synchronization 변수를 상호 배제를 위한 Binary semaphore 한 개와, 자원 count를 위한 Integer semaphore를 둔다. 이를 통해 앞선 pseudo code의 문제를 해결할 수 있을 것이다.

 

Code 예시

Bounded-Buffer Problem을 해결한 pseudo code이다. 이렇게 Producer와 Consumer의 상호 작용을 통해 공유 데이터에 대한 동시 접근을 제어할 수 있다.

다만, 아직 문제가 남아있다.

 

Readers and Writers Problem

 

DB 원칙

1. 프로세스가 DB에 write할 때, 다른 프로세스가 접근하면 안된다.

2. 다만 read는 동시에 수행할 수 있다. 

 

이 문제를 해결하기 위해, 다음과 같은 해법을 적용한다.

- Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다.

- Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.

- 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.

- Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.

 

이를 구현하기 위해 Shared data와 Synchronization variables를 다음과 같이 선언한다.

 

Shared Data

 - DB 자체를 Shared Data로 간주 

- readcount 변수 : 현재 DB에 접근 중인 Reader의 수

 

Synchronization

- mutex : 공유 변수 readcount를 접근하는 코드의 mutual exclusion 보장을 위해 사용한다

- db : Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

 

다음과 같이 구현한다.

 

이 코드는 Starvation 현상이 발생할 수 있다. 

Reader = 100, Writer = 1인 상황을 고려하자. 만약 Reader가 99까지 수행된 상태에서 추가 공급이 된다면, Writer는 추가 공급분이 다 끝날 때까지 추가적으로 대기해야 한다. 이는 곧 Writer의 Starvation 현상이 발생하는 것이다.

이를 해결하기 위해서는 Reader의 무분별한 추가 공급을 막기 위해 timer interrupt와 비슷하게 일정 시간의 term을 부여해 일정 시간 내 도착하는 접근만 추가할 수 있도록 하고, 이외에는 Writer에 권한을 부여함으로써 유한대기 시간을 보장한다.