[운영체제] 세마포어와 뮤텍스 알고리즘

Critical Section Problem

n개의 프로세스가 공유데이터를 동시에 사용하기를 원하는 경우 발생하는 문제 각 프로세스의에서 공유 데이터를 접근하는 코드를 critical section 이라고 한다. 하나의 프로세스가 critical section 에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

Critical Section Problem을 해결하기 위한 조건

1. Mutual exclusion (상호 배타) : 한 프로세스가 critical section 부분을 수행하고 있다면, 다른 프로세스들은 그들의 criitical section 에 들어가지 않는다. 즉, critical section에 꼭 하나의 프로세스만이 진입할 수 있다는 조건이다.
2. Progress (진행): 아무도 critical section에 있지 않은 상태에서 ciritical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
3. Bounded waiting (유한 대기): 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 제한이 있어야 한다. 특정 프로세스 입장에서 지나치게 오래 기다리는 starvation 발생하지 말아야 한다.

뮤텍스 (Mutex)

Critical Section을 가진 thread들의 실행시간이 겹치지 않고 각각 실행될 수 있도록 상호배제를 시키는 기법이다. 뮤텍스는 Mutual Exclusion (상호배제)의 약자이다.
한 process에 의해 소유될 수 있는 key를 기반으로 한 상호배제 기법이며, key에 해당하는 객체가 있으며, 이 객체를 통해 공유자원에 접근할 수 있다.
공유 데이터에 대한 접근을 조율하기 위해 lock을 사용한다. 한 프로세스는 critical section에 진입하기 이전에 반드시 lock을 얻어야하며, critical section을 나갈 때 lock을 해제한다.

general 한 해결 방식은 다음과 같다.

do {
    entry section // lock 을 얻는다
    critical section // 임계구역
    exit section // lock을 해제한다

    remainder section
} while(1);

공유 데이터에 접근하는 코드 (critical section)가 실행되기 이전에 entry section에서 lock을 걸어서 다른 프로세스가 접근하지 못하도록 방지해야 한다. 그리고 exit section에서 lock을 푼다. 다른 process가 critical section에 들어갈 수 있도록 한다.

Mutex Algorithm 1

Process Pi 은 turn == i 일때 critical section에 들어갈 수 있다고 하자 turn 은 critical section에 들어가는 것이 누구 차례인지 나타내는 변수이다. 그리고 나갈때는 다음 상대방의 차례를 만들어 주고 나간다.

do {
    while (turn != i); // 자기 차례가 아니면 while문을 계속 돈다 
    critical section
    turn = j; // exit section -> Now it's your turn ! 
    remainder section
} while(1);

ex ) Process P0의 입장에서 본 알고리즘

do {
    while (turn!=0); // entry section -> My turn ! 
    critical section
    turn = 1; // exit section -> Now it's your turn ! 
    remainder section
} while(1);

이 알고리즘은 Mutual Exclusion을 만족한다. 하지만 Progress를 만족하지 못하는 문제가 발생한다. 아무도 critical section에 없는 상황이어도 바로 진입할 수 없기 때문이다.

Mutex Algorithm 2

flag는 2개가 있고 초기에는 flag 값들이 모두 false 이다. -> boolean flag[2];
flag 는 본인이 critical section에 들어가겠다는 의사를 표현하는 변수이다.
Pi가 critical section에 들어갈 준비가 되었으면 flag[i] = true로 바꾼다.

do {
    flag[i] = true; // I am IN
		while(flag[j]); // Is he also in ? then wait (상대빙이 CS에 있는지 확인함)
		critical section 
		flag[i] = false; //I'm OUT(본인의 flag를 false로 만들어서 상대방이 들어갈 수 있게 함)
		remainder section 
} while(1);

Mutual Exclusion은 만족하지만 progress를 만족하지 못한다.

두개의 프로세스 모두 2번째 줄에서 끊임없이 양보하는 상황이 발생할 수 있기 때문이다.

Peterson’s Algorithm

위의 Mutex Algorithm 1번과 2번에 등장하는 turn 과 flag 변수들을 합쳐서 사용하고 있다.

1. process i가 Critical Section 에 들어가고자 할 때 자신의 flag를 true로 만든다.
2. turn 을 상대방(=j) 차례로 만들어 놓는다.
3. 상대방이 깃발을 들고 있어도 turn 이 상대방 차례가 아니면 Critical Section에 i가 진입 할 수 있다.

do {
    flag[i] = true; // My intention is to ENTER
		turn = j; // Set to his turn 
		while(flag[j] && turn == j); // wait only if... 
		critical section 
		flag[i] = false; //I'm out
		remainder section 
} while(1);

Mutual Exclusion, Progress, Bounded Waiting을 모두 만족한다. 그러나 Busy Waiting(= spin lock) 문제가 있을 수 있다.

ex) 어떤 프로세스가 이미 임계구역에 들어가 있는 상태에서 한 프로세스가 CPU를 잡으면 while문을 돌면서 기다리다가 CPU를 다 써버리고 임계구역에 진입하지 못하고 끝날 수도 있다.

세마포어 (Semaphore)

세마포어는 critical section problem 을 해결하기 위한 도구이다. 세마포어는 critical section에 하나의 process만 접근할 수 있도록 한다. 세마포어는 추상자료형으로 P,V연산을 정의하고 있다.

S는 interger variable을 의미한다. 자원의 개수라고 생각할 수 있다.

P: Critical section에 진입하기 이전에 수행된다. 공유 자원을 획득하는 과정이다.

V: Critical section에서 나올 때 수행한다. 공유 자원을 반납하는 과정이다.

P연산과 V연산은 atomic하게 연산한다고 가정한다.

// 공유데이터를 획득하는 과정인 P 
// S는 자원의 개수이다. S가 5일때, P연산이 자원을 하나씩 가져가면 4, 3, 2... 줄어든다. 
// 책에서는 P를 wait(), V를 signal()이라고 표현하고 있다. 

P(S) {
	while (S <= 0) 
		; // P가 양수가 아니면 자원이 없다는 것이므로 busy-wait 상태가 될 것이다. 
	S--;
}

--- Critical Section ---

V(S) {
	S++;
}