프로세스 동기화

Data Consistency, Race Condition, Critical Section

동시에 다수의 프로세스가 하나의 자원으로 접근할 때, 공유자원에 대한 무절제한 접근은 개별 프로세스의 단위에서 공유자원에 대한 신뢰성을 해한다. 공유하는 **자원의 일관성(Data consistency)**을 유지하기 위해선 각 프로세스가 순서를 가져야 한다. 프로세스 동기화는 이러한 자원의 일관성을 지키기 위해 다수의 프로세스를 관리하는 메커니즘이다.

동기화 되지 않은 다수의 프로세스가 동시에 자원에 접근하여 자원의 일관성을 깨트릴 수 있는 상황을 **경쟁 상태(Race condition)**라 부른다. 이러한 상태에 접근하는것을 방지하기 위해 코드 상에서의 공유자원 접근을 관리하는데, 공유 자원에 접근하는 코드의 영역을 **임계 영역(Critcal Section)**이라 부른다. 이러한 임계영역은 각 프로세스들이 임계영역의 코드를 연산하기 전, 몇몇 규칙을 만족하는지 확인함을 통해 경쟁 상태에 도달하는것을 방지할 수 있다.

Critical Section 보장 방법

다음과 같은 3가지 규칙을 지킴으로써 임계 영역으로의 무분별한 접근에 의한 경쟁 상태를 방지할 수 있다.

Mutual Exclusion

한 시점에 한 프로세스만 임계영역에서 실행 가능하다.

Process

임계 영역에서 작업 중인 프로세스가 없다면, 임계 영역에 진입하고자 하는 프로세스는 진입할 수 있어야 한다.

Bounded Waiting

한 프로세스가 임계영역에 진입을 요청하면, 요청을 허용하기 전까지 다른 프로세스들이 임계영역에 진입하는 횟수가 제한되어야 한다.

이러한 3가지의 규칙을 지키기 위해 몇가지 알고리즘을 구상해볼 수 있다. SW적으로 제공되는 도구(구현체)는 Mutex, Semaphore가 존재한다.

Mutex

Mutex는 lock을 이용해 프로세스가 자원에 접근할 수 없도록 하는 도구(구현체)이며, 하나의 프로세스가 임계 영역에서 작업 중이면 다른 프로세스들은 임계 영역에 들어갈 수 없도록 한다.

// lock : boolean형 변수로, 자원의 가용 여부를 저장

acquire() { // 임계구역 진입 전 수행
	while(lock); // 자원이 가용할 때 까지 대기 (busy wait)
	lock = true; // 자신이 자원을 사용하고, 자원을 비가용 상태로 전환
}

release() { // 임계구역 탈출 때 수행
 lock = false; // 자원을 가용 상태로 전환
}

자원의 가용 여부를 매 클럭 연산하는 작업을 Busy waiting이라 하는데, 임계 영역에 프로세스가 존재할 때, 다른 프로세스들은 임계 영역에 계속해서 진입하려고 시도하기 때문에 CPU를 낭비하게 된다. lock이 반환될 때까지 계속 확인하면서 프로세스가 기다리는 것을 Spin Lock이라고 한다.

Semaphore

Semaphore는 사용 가능한 자원의 개수를 반환함으로써 동시에 자원에 접근할 수 있는 프로세스의 개수를 제한하는 역할을 하는 도구이다.

// S : Semaphore - 정수형 변수로, 가용한 자원의 개수를 저장

// wait(S) : 임계구역 진입 전 수행 (진입여부를 자원 갯수S를 통해 결정)
P(S) {
  while (S<=0) { } // 가용 자원이 생길 때 까지 대기
  S -= 1  // 가용한 자원이 생기면 접근함과 동시에, 값을 하나 감소
}

// signal(S) : 임계구역 탈출 때 수행 (자원 반납 시그널)
V(S) {
  S += 1  // 자원 반납
}

Semaphore는 자원의 수를 세는 유형에 따라 분류할 수 있는데, 자원의 개수를 0 이상의 정수로 나타내는 Counter Semaphore, 자원의 유무를 0과 1의 정수로 나타내는 Binary Semaphore의 두가지 종류로 분류할 수 있다.

이러한 Mutex와 Semaphore의 구현 방식은 Busy Waiting에 의해 자원의 낭비가 일어날 수 있는데, 이를 방지하기 위해 프로세스의 진행과 대기를 관리하는 Block & Wakeup 방식을 사용한다.

struct Semaphore {
	int value;
	struct process waitQueue;
}

//커널은 block을 호출한 프로세스를 suspend 시키고 해당 프로세스를 wait queue에 넣어준다. 
void wait(Semaphore S) {
	S.value--;
	if(S.value < 0) {
		add this process to S.waitQueue;
		block();
	}
}

//Wakeup을 수행하면 block 된 프로세스 P를 깨운 다음, Ready Queue로 이동시킨다. 
void signal(Semaphore S) {
	S.value++;
	if(S.value <= 0) {
		remove a process P from S.waitQueue;
		wakeup(P);
	}
}

대기 큐를 이용한 Block & Wakeup의 구현 방식은 Binary Semaphore와 Mutex가 서로 큰 차이점을 가지게 해주는데, 이 차이점은 대기 큐의 존재가 프로세스의 우선순위를 정해준다는 점에서 발생한다.

• Mutex, Binary Semaphore의 차이 https://blog.naver.com/myca11/222626631093
  • Mutex→ Mutex 획득한 스레드만 잠금해제 가능하므로, Binary Semaphore보다 느림
  • → 상호배제만 가능
  • → Mutex를 획득한 스레드만 뮤텍스 해제 가능
  • Binary Semaphore→ 다른 스레드/프로세스가 잠금 해제가 가능해서, Mutex보다 빠름
  • → 상호배제도 가능하고, 작업순서 동기화도 가능
  • → 현재 스레드보다 우선순위 높은 스레드가 Semaphore를 가질 수 있음
• 그럼에도 Mutex가 사용되는 이유
• Spin Lock은 Critical Section에 진입을 위한 대기 시간이 짧을 때, 즉 Context Switching 하는 비용보다 기다리는 게 더 효율적인 특수한 상황을 위해 고안된 것이다. 단일 CPU 시스템에서는 어차피 Lock을 갖고 있는 스레드를 풀어주기 위해서 Context Switching이 일어나야 하기 때문에 유용하지 않고, 멀티 프로세서 시스템에서 종종 사용된다.

Classical Problem Solving with Mutex and Semaphore

Mutex와 Semaphore를 이용해 기존의 Race condition 문제 상황에서 다수의 프로세스가 동기화되어 자원을 안정적으로 공유할 수 있도록 만들 수 있게 되었다.

Dining-Philosophers Problem

다섯 명의 철학자가 원탁에 앉아 있다. 각자의 앞에는 스파게티가 있고 양옆에 포크가 하나씩 있다. 각각의 철학자는 다른 철학자에게 말을 할 수 없다. 철학자가 스파게티를 먹기 위해서는 양 옆의 포크를 동시에 들어야 한다.

각각의 철학자가 왼쪽의 포크를 들고 그 다음 오른쪽의 포크를 들어서 스파게티를 먹는 알고리즘을 가지고 있다면

다섯 철학자는 동시에 왼쪽의 포크를 들 수 있으나 오른쪽의 포크는 이미 가져가진 상태이기 때문에 다섯 명 모두가 무한정 서로를 기다리다 굶어 죽는 교착 상태에 빠지게 될 수 있다.

다수의 프로세스들이 서로의 자원 반환을 기다리게 되어 더 이상 아무런 작업도 수행할 수 없는 교착 상태를 Deadlock이라 부른다.

Deadlock은 4가지 조건을 만족할 경우에 발생하게 되는데, 자원은 한번에 한 프로세스만 사용 가능한 상호배제(Mutual Exclusion), 자원을 가진 상태에서 다른 프로세스의 자원을 요구하며 대기하는 점유 대기(Hold And Wait), 다른 프로세스의 자원 선점이 불가한 비선점(Non Preemption), 각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 가진 상태인 순환 대기(Circular Wait) 상태를 만족할 때 발생한다.

4가지 조건 중 하나를 부정함으로써 Deadlock 상태를 방지할 수 있는데, 각 철학자가 양쪽 젓가락을 다 들 수 있을 때, 즉 모든 자원이 사용 가능할 때 작업을 수행하도록 하는 점유 대기 부정을 예로 들 수 있다. 이를 코드로 구현한다면 다음과 같다.

enum{thinking, hungry, eating} state [5];
Semaphore self[5] = 0
mutex = 1;

//i 번째 philosopher에 대해
do {
	pickup(i);
	eat();
	putdown(i);
} while(1);

// 젓가락 사용
void pickup(int i) {
	P(mutex);
	state[i] = hungry;
	test(i);
	V(mutex);
	P(self[i]);
}

void putdown(int i) {
	P(mutex);
	state[i] = thinking;
	test((i+4)%5);
	test((i+1)%5);
	V(mutex);
}

// V(self[i]) : 양쪽 젓가락을 들 수 있는 권한을 얻는 부분
// 만약 얻지 못하면 P(self[i])에서 기다리게 된다
// 양쪽 철학자가 밥을 다 먹은 경우에 기다림이 끝난다.
void test(int i) {
	if(state[(i+4)%5] != eating && state[i] != hungry && state[(i+1)%5] != eating]) {
		state[i] = eating;
		V(self[i]);
	}
}

P(S) {
  while (S<=0);
  S -= 1;
}

V(S) {
  S += 1;
}