[OS] 프로세스 동기화

임계 구역 문제(Critical Section Problem)

n개의 프로세스가 있는 시스템에서 각 프로세스는 임계구역이라 불리는 코드의 일부를 가지고 있다.

한 프로세스가 임계 구역에 들어가면, 다른 프로세스는 아무도 임계구역에 들어갈 수 없다.

각 프로세스는 임계 구역에 들어가기 위해 entry section이라는 코드 부분에서 허가를 받아야 하고, 임계 구역 실행이 끝난 프로세스는 exit section을 지나 다른 프로세스들이 임계구역에 들어갈 수 있게 된다.

임계 구역 문제를 해결하기 위해서는 3가지 조건이 만족해야 한다.

상호 배제(Mutual Exclusion) : 만약 프로세스가 임계 구역에서 실행 중이라면 다른 모든 프로세스는 임계 구역에서 실행할 수 없다.

진행(Progress) : 만약 아무 프로세스도 임계 구역에서 실행되고 있지 않고 임계 구역 내에 진입하려는 프로세스가 있다면, 임계 구역에 들어갈 프로세스를 고르는 것은 무기한 연기될 수 없다.

한정된 대기(Bounded Waiting) : 프로세스가 임계 구역에 진입하려고 하는 요청을 보내면 요청이 받아들여질 때까지 다른 프로세스들이 임계 구역에 진입하도록 허용하는 횟수에 제한이 있어야 한다.

 

피터슨의 해결책(Peterson's Soultion)

임계 구역 문제를 해결하기 위한 방법으로 Peterson's Soultion이 있다.

이 방법은 프로세스가 2개 있을 경우로 한정하고 있고, 두 프로세스는 2가지 공유 변수를 가지고 있다.

int turn; //누가 임계 구역에 들어갈 차례인지
bool flag[2]; //임계 구역에 진입할 준비가 되었는지

2가지 변수를 이용하여 Peterson's Soultion은 다음과 같은 코드 구조를 가지고 있다.

do {
  flag[i] = true;      
  turn = j; 
  while(flag[j] && turn == j); 
  
  // critical section 
  
  flag[i] = false;  
  
  // remainder section
  
} while(1);

 

프로세스 i가 임계 구역에 진입하고 싶어 할 경우, flag[i] = true를 통해 이를 표시한다.

그리고 프로세스 j가 임계 구역에 들어갈 준비가 되었는지 체크하기 위해 turn = j로 한 뒤, while문을 통해 이를 확인한다.

만약 flag[j] = true여서 임계 구역에 프로세스 j가 진입했다면 while문에서 busy waiting을 한다.

프로세스 j가 임계구역에서 나오면 그제야 프로세스 i가 임계구역에 진입하고, 완료된 후에는 flag[i] = false로 바꾸는 방식으로 진행한다.

하지만 Peterson's Solution은 현대 컴퓨터 구조에서 제대로 작동하는 것이 보장되지 않기 때문에 사용되지 않는다.

 

Mutex Lock

Mutex Lock이란 임계 구역 문제를 해결하기 위해  OS 디자이너들이 개발한 소프트웨어 도구이다.

임계 구역에 들어가기 위해 lock을 얻고 임계 구역에서 나올 때 lock을 반환하는 방식이다.

acquire() {
	while (!available);
	available = false;
}
release() {
	available = true;
}

do {
	acquire(); //lock을 획득
	/* critical section */
	release(); //lock을 반환
	/* remainder section */
} while (true);

Mutex Lock을 이용한 방법은 busy waiting을 사용한다. while 문에서 lock을 얻을 때까지 기다리면서 계속 반복문을 호출하게 된다는 단점이 있다.

 

Semaphore

Semaphore는 wait()와 signal()이라는 메서드를 제공한다.

wait()와 signal()은 P()와 V()로도 불린다.

wait(S) { // == P()
	while (S <= 0); // busy wait
	S--;
}

signal(S) { // == V()
	S++;
}

Binary semaphore

• semaphore 변수가 0 또는 1의 binary 값만 갖는 semaphore이다. 
• 공유 변수 제어를 위한 임계 구역 문제를 해결하기 위해 사용된다.
• Mutex Lock과 유사한 기능을 한다.

Counting semaphore

• semaphore 변수가 풀에 있는 자원과 같은 값으로 초기화되는 semaphore이다.
• wait() 연산을 사용하면 semaphore 값이 감소하고, signal()을 사용하면  semaphore 값이 증가한다.
• semaphore 값이 0이 될 때까지  가져올 수 있고, 만약 0이라면 0보다 커질 때까지 block 된다.

 

앞서 구현한 semaphore는 wait()을 할 때 busy waiting을 해야 한다. 이를 해결하기 위한 추가적인 개선방안이 있다.

typedef struct {
int value;
struct process *list;
} semaphore;

wait(semaphore *S) {
	S->value--;
	if (S->value < 0) {
		add this process to S->list;
		block();
	}
}

signal(semaphore *S) {
	S->value++;
	if (S->value <= 0) {
		remove a process P0 from S->list;
		wakeup(P0);
	}
}

wait()을 호출하면 자신의 value를 1 감소시키고 0보다 작다면 프로세스를 waiting queue에 삽입한다.

그리고 block()을 통해 자신을 호출한 프로세스를 중지시킨다.

block 된 프로세스는 다른 프로세스의 signal() 호출에 의해 waiting queue에서 제거된다.

그리고 wakeup()을 통해 block 되었던 프로세스가 다시 실행되게 된다.

 

식사하는 철학자 문제(Dining-Philosophers Problem)

철학자들은 항상 생각하거나 먹는데 시간을 소비한다고 가정한다.

5명의 철학자는 원형테이블에 둘러앉아 있으며 테이블 중앙에는 밥이 있고, 젓가락은 철학자들 사이마다 1개씩 총 5개가 있다.

철학자는 서로 상호작용 하지 않으며, 배고파지면 2개의 젓가락을 한 번에 집는다.

왼쪽과 오른쪽에 젓가락이 하나라도 사용 중이면 젓가락을 집지 못하고, 사용을 다한 젓가락은 내려놓고 다시 생각을 한다.

이 문제는 동기화에 관한 고전적인 문제이다.

이 문제를 semaphore를 통해 해결하려고 시도해 볼 수 있다.

do {
	wait (chopstick[i]);
	wait (chopstick[(i+1) % 5]);
	// eat
	signal (chopstick[i]);
	signal (chopstick[(i+1) % 5]);
	// think
} while (true);

하지만 5명의 철학자가 동시에 왼쪽 젓가락을 집을 경우 deadlock이 발생할 수 있다.

deadlock을 피하기 위해 3가지의 방법이 있다.

• 최대 4명의 철학자만 테이블에 앉게 한다.
• 철학자가 젓가락을 한 번에 2개를 동시에 들게 한다.
• 홀수 번호의 철학자는 왼쪽 젓가락을, 짝수 번호의 철학자는 오른쪽 젓가락을 먼저 들게 한다.