[OS] 4. 프로세스 동기화 (Process Synchronization)

 

4. 프로세스 동기화 (Process Synchronization)

1. 경쟁 상태 (Race Condition)
2. 임계 구역 (Critical Section)
3. 세마포어 (Semaphore)
4. 모니터 (Monitor)

 

1. 경쟁 상태 (Race Condition)

1.1. Race Condition

공유 자원에 대해 여러 프로세스가 동시에 접근을 시도할 때, 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말한다. 동시에 접근할 때 자료의 일관성 을 해치는 결과가 나타날 수 있다.

 

1.2. OS 에서 race condition은 언제 발생할까?

1. 커널 작업을 수행 중에 인터럽트가 발생할 때

2. 프로세스가 system call을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환이 발생할 때

3. 멀티 프로세서에서 공유 메모리 내의 커널 데이터에 접근할 때

 

 

2. 임계 구역 (Critical Section)

OS 에서 여러 프로세스가 데이터를 공유하면서 수행될 때, 각 프로세스에서 공유 데이터를 액세스하는 프로그램 코드 부분을 뜻한다. 공유 자원의 독점을 보장 해주는 역할을 수행한다.

 

2.1. 프로그램적으로 해결하는 방법의 충족 조건

Mutual Exclusion (상호 배제)

• 프로세스1 이 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그 critical section 에 접근할 수 없다

Progress (진행)

• 아무도 critical section 에 있지 않다면, 들어가고자 하는 프로세스를 들어가게 해줘야한다

Bounded Waiting (유한 대기)

• 프로세스가 critical section 에 들어가기 위해 무한정으로 기다리는 현상 (=Starvation) 이 있어서는 안된다

 

2.2. 피터슨 알고리즘 (Peterson's Algorithm)

do {
  flag[i] = true;			// My intention is to enter
  turn = j;				// Set to his turn
  while(flag[j] && turn == j);		// Wait...
  
  // critical section
  
  flag[i] = false;
  // remainder section
} while(1);

 

 

3. 세마포어 (Semaphore)

세마포어(Semaphore) 는 자원의 개수를 뜻한다. 즉, 동시에 자원에 접근 할 수 있는 허용 가능한 counter의 개수 를 뜻한다.

• 동기화 기법 중, 추상적인 방법
• 세마포어는 여러 프로세스들에 의해 공유되는 변수로 정의
• 이 변수는 오직 P() 와 V() 라는 Atomic 한 연산에 의해서만 접근 가능
• 리소스의 상태를 나타내는 카운터 라고 생각하면 된다

 

3.1. Busy - Wait 방식

이 방식은 프로세스 P 가 자원이 모두 사용 중이라면, wait 하는 방식이다. 만약 자원의 여유가 생기면 s−− 를 통해 자원을 획득한다. 그리고 자원을 모두 사용했다면 s++ 를 통해 자원을 반납한다.

P(s){
  while(s <= 0) do wait
  s--;
}

V(s){
  s++;
}

 

3.2. Block - Wakeup 방식

이 방식은 먼저 아래와 같이 세마포어를 정의한다.

type struct{
  int value;			// Semaphore
  struct process *Q;		// Wait Queue
}semaphore;

먼저 자원의 값을 감소시킨다. 만약 자원의 개수가 부족해 사용할 수 없다면 현재 프로세스를 Wait Queue 에 추가시킨 후, block() 을 통해 suspend 시킨다.

만약 다른 프로세스가 작업을 완료해 자원의 값을 증가시키며 반납을 했을 때, 자원의 수가 없다면 이는 현재 자원을 기다리는 프로세스가 존재한다는 뜻이다. 따라서 Wait Queue 에서 프로세스를 꺼내와 wakeup() 을 통해 깨우게 되는 것이다.

P(S){
  S.value--;
  if(S.value < 0){
    // add this precess to S.queue;
    block();
  }
}

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

 

Busy-wait VS Block-wakeup

임계 구역(Critical Section) 의 길이가 긴 경우는 Block-wakeup 방식이 유리하다. 하지만 임계 구역이 짧다면 잦은 문맥 교환으로 인해 오버헤드가 증가하게 된다. 따라서 반대의 경우에는 Busy-wait 방식이 유리하다.

 

3.3. Mutex

뮤텍스(Mutex) 는 상호배제 를 뜻하며, Binary Semaphore 와 같은 의미이다. 즉, 자원에 단 하나의 작업만이 접근할 수 있다는 뜻이다.

Critical Section 을 가진 스레드들의 Running Time 이 서로 겹치지 않게 각각 단독으로 실행되게 하는 기술이다. 다중 프로세스들의 공유 자원에 대한 접근을 조율하기 위해 lock 과 unlock 을 사용한다

세마포어와의 가장 큰 차이점은 동기화 대상의 개수 이다. Mutex 는 동기화 대상이 오직 하나뿐일 때, Semaphore 는 동기화 대상이 하나 이상일 때 사용한다.

 

 

4. 모니터 (Monitor)

동기화 문제를 해결하기 위해서 세마포어라는 방법을 사용했지만, 아래와 같은 문제점을 갖고 있다

• 코딩하기가 어렵다
• 정확성(correctness) 의 입증이 힘들다
• 자발적 협력(voluntary cooperation) 이 필요하다
• 한 번의 실수가 모든 시스템에 치명적 영향을 끼친다

 

모니터(Monitor) 내에서는 한 번에 하나의 프로세스만 활동이 가능하다. 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다. 또한 프로세스가 모니터 안에서 기다릴 수 있도록 Condition Variable 을 사용한다. 이는 wait / signal 연산에 의해서만 접근이 가능하다.

wait() : 다른 프로세스가 signal 을 하기 전까지 suspend 된다

signal() : 정확하게 하나의 suspend 된 프로세스를 깨운다

 

Monitor vs Semaphore

• Monitor 는 자체적으로 하나의 프로세스만 처리
• 반면 Semaphore 는 직접 Lock 을 걸고 해제해야한다

즉, 모니터는 뮤텍스의 상위 호환 버전이면서, 세마포어와는 약간의 차이를 가지고 있다

 

 

 

---

참고 자료

• https://jwprogramming.tistory.com/13