[OS/공룡책] Part 3. Process Synchronization

Concurrent access to shared data my result in data inconsistency.

 

동기화 방법

프로세스들은 동시에 실행되거나 서로 다른 코어에서 병렬적으로 실행될 수 있다. 공유 자원에 여러 개의 프로세스가 동시에 접근하는 상황을 경쟁 상태라고 부르는데, 이는 공유 데이터의 무결성을 해칠 수 있다. 따라서 한 번에 하나의 프로세스만 공유 데이터를 조작하도록 접근 순서를 제어해야 한다. (동기화)

⭐ 경쟁 상태
두 개 이상의 프로세스가 공유 자원에 동시에 접근할 때, 공유 자원에 대한 접근 순서에 따라 그 실행 결과가 달라지는 상황

 

The Critical-Section Problem

임계구역은 다른 프로세스와 공유하는 코드의 일부분을 의미하며, 다음 구조를 갖는다.

1. entry-section : 임계구역에 진입하는 코드 (= 허가 획득)
2. critical-section
3. exit-section : 임계구역을 빠져나오는 코드 (= 허가 반납)
4. remainder-section

 ⭐ 임계구역
여러 프로세스가 데이터를 공유할 때, 각 프로세스에서 공유 데이터를 접근하는 코드 부분

 
임계구역 문제는 다음 세 가지 조건을 모두 만족해야 해결할 수 있다.

1. mutual exclusion : `Pi`가 임계구역을 실행하고 있다면, 다른 프로세스는 임계 영역을 실행할 수 없다.
2. progress : 어떤 프로세스도 임계구역을 실행하지 않을 때, 임계구역에 진입하려는 프로세스들이 존재한다면 누군가는 반드시 진입할 수 있어야 하며, 이 선택은 무한히 지연되어서는 안 된다. (= deadlock에 빠지지 않음)
3. bounded waiting : 어떤 프로세스가 임계구역에 진입하려고 요청했을 때, 그 프로세스가 임계구역에 진입하기 전까지 다른 프로세스들의 진입 횟수에 상한이 있어야 한다. (= starvation에 빠지지 않음)

 

Peterson's Solution

피터슨 솔루션은 임계구역 문제를 해결하는 고전적인 소프트웨어 해결책이다. `turn`은 임계구역에 진입하려는 프로세스를 나타낸다. `flag` 배열은 프로세스가 임계구역에 진입할 준비가 되었는지를 나타낸다.

`Pi`는 `Pj`가 임계구역을 실행하고 있지 않을 때 임계구역에 진입할 수 있다. 이처럼 피터슨 솔루션은 mutual exclusion을 만족하지만 멀티 스레드 환경에서 완벽한 동기화를 보장할 수는 없다. 
 

Mutex Locks

boolean 타입의 lock 변수를 활용하여 한 번에 하나의 프로세스만 임계 구역에 접근할 수 있다.

뮤텍스 락은 임계구역을 보호하여 경쟁 상태를 예방한다. 프로세스는 임계구역에 들어가기 위해 lock을 획득 `acquire()` 해야 하고, 임계구역을 빠져나올 때 lock을 반환 `release()` 해야 한다. 뮤텍스 락은 lock의 획득 가능 여부를 나타내는 `available`이라는 boolean 변수를 갖는다.

위 구현 방법은 busy waiting 문제가 발생한다. 한 프로세스가 임계구역에 있을 때, 다른 프로세스가 임계구역에 진입하려면 반복문을 실행하며 대기한다. (= spin lock) 이는 CPU를 낭비하지만, CPU를 계속 점유하기 때문에 문맥 교환이 발생하지 않는다는 장점도 존재한다. 즉, 싱글코어 시스템에서는 비효율적인 방법이지만, 멀티코어 시스템에서는 선호하는 방식일 수 있다.
 

Semaphores

정수형 타입의 lock 변수를 활용하여 여러 개의 프로세스가 임계 영역에 접근하는 것을 허용한다.

세마포어 `S`는 정수형 변수로, `wait()`과 `signal()` 연산을 통해 접근할 수 있다. `wait()`과 `signal()`은 각각 `P()`, `V()`로도 불린다.

void wait(semaphore *S) {
  while(S <= 0) {} // 임계 영역에 접근할 수 있는 자원 개수 초과
  S--;
}

void signal(S) {
  S++;
}

while(true) {
  wait(S); 
  /* critical section */
  signal(S);
  /* remainder section */
}

세마포어에는 카운팅 세마포어, 바이너리 세마포어 두 종류가 있다. 바이너리 세마포어는 0과 1 중 하나의 값을 가지므로 뮤텍스 락과 유사하다. 카운팅 세마포어는 임계구역에 접근할 수 있는 자원의 수를 의미한다.
 
세마포어 역시 busy waiting 문제가 발생하는데, 이는 `wait()`과 `signal()` 로직을 수정하여 극복할 수 있다. 임계구역에 진입할 수 있는 자원의 수를 초과하면 대기 리스트에 현재 프로세스를 추가한 후 sleep하여 (running → waiting) 다른 프로세스가 CPU를 점유하고 실행할 수 있도록 구현하면 된다.

typedef struct {
  int value;
  struct process *list; // CS에 진입 대기 중인 프로세스 (= sleep된 프로세스 = waiting 상태)
} semaphore;

임계구역에서 빠져나왔을 때, 진입 대기 중인 프로세스가 존재한다면, 대기 리스트에서 프로세스를 하나 꺼내고 wakeup하여 (waiting → ready) 레디큐로 넣는다. 해당 프로세스는 CPU를 점유하면 곧바로 임계구역에 진입할 수 있다.

뮤텍스 락	세마포어
lock (= 바이너리 세마포어)	세마포어
`acquire()`	`wait()` (= `P()`)
`release()`	`signal()` (= `V()`)

🚨 뮤텍스 락과 세마포어는 개발자가 직접 lock을 관리하기 때문에 개발자의 실수로 인해 데드락과 같은 동기화 문제가 발생할 가능성이 높다.

⭐ 뮤텍스 락 & 세마포어

• 뮤텍스 락과 세마포어는 동기화 문제를 해결하기 위한 방법이다.
• 뮤텍스 락은 바이너리 세마포어로, 자원에 lock을 걸어 동기화 문제를 해결한다. 즉, lock으로 mutual exclusion을 만족하여 한 번에 하나의 프로세스만 임계구역을 실행하도록 제한한다.
• 세마포어는 임계구역에 진입하기 전에 세마포어를 통해 자원에 접근할 수 있는지 확인하여 동기화 문제를 해결한다.

 

Monitor

one fundamental high-level synchronization construct

모니터는 뮤텍스락과 세마포어의 한계를 극복하기 위해 도입된 개념이다. 모니터 차원에서 lock을 관리하기 때문에 실수로 인한 동기화 문제가 발생할 가능성이 낮다.

📝 모니터

• 캡슐화 : 공유 데이터와 이를 사용하는 연산을 하나의 모듈로 캡슐화한다. 모니터 내부에 정의된 함수만 변수에 접근할 수 있다.
• 추상화 : 코드의 복잡성을 낮추고 높은 가독성을 제공한다.
• 자동 동기화 관리 : 모니터 내에서는 한 번에 하나의 스레드만 활성화된다.

 
모니터는 조건 변수를 통해 특정 조건이 만족될 때까지 스레드를 대기시키는 기능을 제공한다. 임계구역에 접근하려는 프로세스는 직접 `wait()`, `signal()`을 사용하지 않고 모니터에 작업을 요청한다.

monitor shared_count() {
  bool busy = false; // lock
  condition x; // 조건 변수 (동기화 메커니즘 제공)
  int count = 0; // 공유 데이터
  
  void increase(int amount) {
    if(busy) {
      x.wait(); // 다른 프로세스가 x.signal()을 실행하기 전까지 중단
    }
    busy = true;
    count += amount;
    x.signal(); // 중단된 프로세스 중 하나를 재시작
  }
}

 

💡 liveness : 프로그램이 결국에는 동작을 수행한다는 것을 보장하는 것
*liveness의 실패 사례 : deadlock, starvation, priority inversion 등

priority inversion

• 높은 우선순위를 가진 프로세스 `H`가 공유 자원 `S`에 접근하려고 할 때, 낮은 우선순위 `L`의 프로세스가 `S`를 사용하고 있어 실행이 끝나기를 가다리는 상황을 의미한다.
• 낮은 우선순위의 프로세스가 중간 우선순위의 프로세스 `M`에 의해 선점된다면 문제가 더욱 심각해진다.

우선순위 상속으로 극복할 수 있다

• `H`가 필요로 하는 자원에 접근하는 모든 프로세스는 해당 자원의 사용을 마칠 때까지 일시적으로 높은 우선순위를 상속받는다.
• 자원 사용을 마치면 원래의 우선순위로 돌아간다.

---

동시성 문제

이제 앞에서 배운 동기화 방법을 고전적인 동시성 문제들에 적용해보자.

The Bounded-Buffer Problem

bounded buffer는 고정된 크기의 버퍼를 의미한다. 생산자가 버퍼에 데이터를 집어넣으면 소비자가 이를 꺼내서 사용한다. 이때, 버퍼에 저장할 공간이 없는 문제나 버퍼에서 꺼낼 데이터가 없는 문제가 발생할 수 있다. 이는 `empty`와 `full`이라는 추가적인 세마포어를 사용해서 해결할 수 있다.

int n; // 버퍼 크기
semaphore mutex = 1; // 바이너리 세마포어 (for mutual exclusion)
semaphore empty = n; // 카운팅 세마포어
semaphore full = 0; // 카운팅 세마포어

// 생산자 ver.
while(true) {
  ...
  wait(empty); // 1. 버퍼가 빌 때까지 기다림
  wait(mutex); // 2. 차례 기다림 (= 프로세스 동기화)
  /* 3. 버퍼에 데이터 작성 */
  signal(mutex); // 4. lock 반납
  signal(full); // 5. 소비자에게 데이터 가져가라고 알림 
}

// 소비자 ver.
while(true) {
  wait(full); // 1. 버퍼가 찰 때까지 기다림
  wait(mutex); // 2. 차례 기다림 (= 프로세스 동기화)
  /* 3. 버퍼에서 데이터 가져옴 */
  signal(mutex); // 4. lock 반납
  signal(empty); // 5. 생산자에게 데이터 작성하라고 알림 
  ...
}

 

The Readers-Writers Problem

읽기만 하는 프로세스를 reader, 쓰기만 하는 프로세스를 writer라고 한다. 두 개 이상의 reader가 동시에 공유 데이터에 접근하는 상황을 가정해보자. 프로세스 모두 읽기 작업만 수행하기 때문에 부작용이 발생하지 않는다. 따라서 writer가 공유 데이터에 접근하는 상황만 제어해주면 된다.

첫번째 방법은 한 reader가 임계구역에 있을 때, 다른 reader가 임계구역에 곧바로 진입할 수 있도록 허용하는 것이다. writer가 기다린다고 해서 reader도 기다릴 필요가 없지만, reader가 계속 진입할 수 있기 때문에 writer의 starvation이 발생할 수 있다.

semaphore rw_mutex = 1; // 바이너리 세마포어 (for writer의 mutual exclusion)
semaphore mutex = 1; // CS 접근 제어
int read_count = 0; // CS에 진입한 reader의 개수

// writer ver.
while(true) {
  wait(rw_mutex);
  /* write */
  signal(rw_mutex);
}

// reader ver.
while(true) {
  wait(mutex);
  read_count++;
  if(read_count == 1) { // writer 작업 끝날 때까지 기다림
    wait(rw_mutex);
  }
  /* read */
  wait(mutex);
  read_count--;
  if(read_count == 0) { // 지금부터 reader와 writer 모두 진입 가능
    signal(rw_mutex);
  }
  signal(mutex);
}

두번째 방법은 writer가 기다리는 경우, 새로운 reader는 임계구역에 진입할 수 없도록 제어하는 것이다. 이는 writer의 작업을 빠르게 처리해주지만, 반대로 reader의 starvation이 발생하게 된다.

첫번째 방법 (= reader부터 처리)	두번째 방법 (= writer부터 처리)
writer의 starvation	reader의 starvation

 
reader-writer 락은 다음 상황에서 유용하게 사용된다.

• reader, writer 프로세스의 구분이 쉬운 경우
• reader의 수가 writer의 수보다 많은 경우

 

The Dining-Philosophers Problem

다섯 명의 철학자가 원형 탁자에 앉아있고, 철학자 사이에 젓가락이 한 짝씩 놓여있다. 철학자는 배가 고프면 가장 가까이에 있는 젓가락을 하나씩 차지하고, 음식을 먹은 후에 젓가락을 내려놓는다. 젓가락을 동시에 차지하는 경우를 방지하기 위해 젓가락을 잡을 때 mutual exclusion을 적용한다.

// 뮤텍스 락 ver.
while(true) {
  /* acqruie chopsticks */
  wait(chopstick[i]);
  wait(chopstick[(i + 1) % 5]);
  /* eat */
  /* release chopsticks */
  signal(chopstick[i]);
  signal(chopstick[(i + 1) % 5]);
}

다섯 명의 철학자가 동시에 배가 고파져 왼쪽 젓가락을 잡는 상황을 가정해보자. 철학자는 음식을 먹은 후에 젓가락을 내려놓기 때문에 아무도 젓가락을 차지할 수도, 놓을 수도 없는 상황이 발생한다. (= deadlock) 
 
이를 해결하기 위한 세 가지 방법이 존재한다.

1. 한 자리를 항상 비워둠으로써 데드락을 방지한다.
2. 양쪽 젓가락을 다 획득할 수 있는 경우만 젓가락을 잡을 수 있도록 제어한다.
3. 홀수 철학자는 왼쪽-오른쪽 순으로, 짝수 철학자는 오른쪽-왼쪽 순으로 젓가락을 획득할 수 있다.

// 두 번째 방법 + 모니터 ver.
monitor DiningPhilosopher {
  enum {THINKING, HUNGRY, EATING} state[5]; // 철학자의 상태
  condition self[5]; // 조건 변수
  
  void pickUp(int i) {
    state[i] = HUNGRY;
    test(i);
    if(state[i] != EATING) { // 젓가락 집을 수 없는 경우 기다림
      self[i].wait();
    }
  }

  void putDown(int i) {
    state[i] = THINKING;
    test((i + 4) % 5);
    test((i + 1) % 5);
  }

  void test(int i) { // 양쪽 젓가락을 잡을 수 있가
    if(
      (state[i] == HUNGRY) && 
      (state[(i + 4) % 5] != EATING) && // 왼쪽 젓가락 잡을 수 있음
      (state[(i + 1) % 5] != EATING)) { // 오른쪽 젓가락 잡을 수 있음
      state[i] = EATING;
      self[i].signal();
    }
  }

  void initialize() {
    for(int i = 0; i < 5; i++) {
      state[i] = THINKING;
    }
  }
}

하지만 위 세 가지 방법도 starvation 문제를 해결하진 못한다.

---

Deadlock

every process in a set of processes is waiting for an event that can be caused only by another process in the set

멀티코어 시스템에서 여러 개의 프로세스는 다수의 자원을 공유할 수 있다. 프로세스가 자원을 사용하기 위해서는 request, use, release 과정을 따르는데, 자원을 요청한 프로세스가 곧바로 자원을 사용할 수 없는 경우에는 자원을 획득할 수 있을 때까지 기다려야 한다. deadlock은 모든 프로세스가 다른 프로세스가 발생시킬 이벤트를 무한정 기다리는 상황을 의미한다.

⭐ deadlock
원하는 자원이 상대방에게 할당되어 있어 프로세스가 무한정 기다리는 상황

 

필수 조건

다음 네 가지 조건을 모두 만족하면 deallock이 발생한다.

1. mutual exclusion : 한 번에 하나의 스레드만이 자원을 이용할 수 있다.
2. hold and wait : 여러 개의 자원이 필요할 때, 스레드는 하나의 자원을 점유한 상태에서 다른 스레드가 사용하고 있는 자원이 반환되기를 기다린다.
3. no preemption : 스레드에서 자발적으로 자원을 반환하기 전까지 해당 자원을 뺏을 수 없다.
4. circular wait : 스레드는 순환적으로 다음 스레드가 요구하는 자원을 가지고 있다.

⭐ Dining Philosophers Problem의 deadlock 성립 조건

1. mutual exclusion : 젓가락은 한 번에 한 철학자만 사용할 수 있다.
2. hold and wait : 왼쪽 젓가락을 점유한 상태에서 오른쪽 젓가락을 기다린다.
3. no preemption : 다른 철학자가 사용 중인 젓가락을 강제로 뺏을 수 없다.
4. circular wait : 모든 철학자들이 오른쪽에 앉은 철학자가 젓가락을 내려놓기를 기다린다.

 

해결 방법

deadlock은 다음 네 가지 방법으로 해결할 수 있다.

1. ignorance : deadlock이 발생해도 별다른 조치를 취하지 않는다.
2. prevention : deadlock이 발생하지 않도록 네 가지 필수 조건 중 하나를 방지한다.
3. avoidance (by Banker's Algorithm)
4. detection-and-recovery : deadlock의 발생 여부를 확인하여 deadlock 발생 시 이를 복구한다.

prevention과 avoidance는 deadlock이 발생하지 않도록 미연에 방지하는 방법이다.

 
prevention은 deadlock의 필수 조건 중 아무 하나를 충족시키지 않도록 제어하여 deadlock을 방지한다. mutual exclusion의 경우, 공유 자원에 동시에 접근하는 것이 불가능하기 때문에 이를 충족시키지 않는 방법은 존재하지 않는다.
 
hold and wait은 프로세스가 자원을 요청할 때 어떤 자원도 소유하지 않도록 함으로써 예방할 수 있다. 즉, 추가적인 자원을 요청하기 위해서는 현재 할당된 모든 자원을 반환해야만 한다. 하지만 이는 두 가지 단점이 존재한다. 자원을 할당받아도 오랜 기간동안 사용하지 않기 때문에 자원의 효율성이 떨어지고, 자원을 할당받지 못하는 시간이 길어져 starvation이 발생할 수 있다.
 
no preemption은 프로세스가 하나 이상의 자원을 할당받은 상태에서 다른 프로세스가 사용 중인 자원을 요청한 경우, 소유한 모든 자원을 반납하도록 하여 방지할 수 있다. 하지만 이 역시 강제성만 다를 뿐 hold and wait과 동일하므로 같은 단점을 갖는다.
 
사실상 가능한 prevention 방법은 circular wait을 충족시키지 않는 것뿐이다. 모든 자원에 번호를 부여하고, 요청 시 오름차순으로 요청하도록 만든다. 하지만 이 방법 역시 starvation이 발생할 수 있다.

📝 prevention

• mutual exclusion : 공유 자원에 동시에 접근하는 것이 불가능하므로 이를 방지하는 방법은 존재하지 않는다.
• hold and wait & no preemption : 다른 자원을 할당받기 위해서는 본인이 갖고 있는 자원을 모두 내려놓거나, 빼앗기게 된다. 자원 효율성이 떨어지고 starvation이 발생할 수 있다.
• circular wait : 자원 요청 시 오름차순으로 요청해야 한다.

 
avoidance는 자원에 대한 요청을 승인하기 전에 deadlock 가능성을 확인하는 방법이다. 스레드는 safe와 unsafe 상태가 존재한다. safe 상태에서는 deadlock이 발생하지 않지만, unsafe 상태에서는 자원의 요청 순서에 따라 deadlock이 발생할 수 있다.

avoidance는 safe 상태를 유지하여 deadlock을 방지한다. 새로운 스레드가 시스템에 들어오면 스레드는 자신이 사용하는 자원의 수를 알려야 한다. 시스템은 해당 자원의 할당이 safe 상태를 유지하는지 판단한 후, 자원을 할당하거나 기다리도록 만든다. avoidance를 위해서는 다음 정보가 필요하다. 

• 현재 사용할 수 있는 자원 `avaliable`
  • `available[j] == k` : `Rj` 자원 중 `k`개의 자원을 사용할 수 있다.
• 현재 각 스레드에 할당된 자원 `allocation`
  • `allocation[i][j] == k` : `Ti`에서 `Rj`를 `k`개 점유하고 있다. 
• 각 스레드에서 필요로 하는 자원의 수 `max`
  • `max[i][j] == k` : `Ti`에서 `Rj`를 `k`개 필요로 한다. 
• 각 스레드에서 추가적으로 요청해야 하는 자원의 수 `need`
  • `need[i][j] = max[i][j] - allocation[i][j] = k` :  `Ti`에서 `Rj`를 `k`개 더 요청해야 한다.

safe 상태를 유지하면서 자원을 할당하는 과정을 살펴보자. 먼저 `need` 값을 계산하여 각 스레드가 추가적으로 필요로 하는 자원의 수를 파악한다. `need`와 `available`을 비교하여 자원을 할당할 수 있는 스레드를 찾는다. 현재 실행할 수 있는 스레드는 `T1`과 `T3`다.

`T1`을 선택하면, `T1`은 자원을 사용한 후에 반납한다. `T1`의 실행이 끝나면 현재 사용 가능한 자원의 수는 `5 3 2`가 된다. 현재 상황에서 실행할 수 있는 스레드는`T3`와 `T4`가 된다. 

`T3`를 실행하고 나면 `7 3 2`개의 자원이 남는다. 계속해서 위의 과정을 동일하게 반복하면 safe 상태를 유지할 수 있다.

📝 avoidance (Banker's Algorithm)

• 스레드가 자원을 요청했을 때, safe 상태를 만족하는지 확인하여 deadlock을 방지한다.
• 자원을 할당할 수 있어도 unsafe 상태를 피하기 위해 기다리기 때문에 자원의 효율이 떨어진다.
• 자원을 요청할 때마다 상태를 확인하기 때문에 비용이 많이 든다.

 
detection-and-recovery는 시스템 상태를 검사하여 deadlock이 발생했는지 확인하고 이로부터 극복하는 방법이다. 하지만 이 방법 역시 필요한 정보를 유지하고 탐지 알고리즘을 실행하는 오버헤드가 발생하며, deadlock을 회복하는 과정에서 잠재적인 손실이 발생할 수 있다.
 
deadlock은 어떤 스레드가 당장 승인될 수 없는 요청을 보낼 때 발생하므로, 할당 요청이 승인될 수 없을 때마다 탐지 알고리즘을 실행하면 된다. 하지만 매 자원 요청마다 탐지 알고리즘을 실행하는 것은 상당한 오버헤드가 발생한다. 따라서 현재 다음 두 가지 방법을 사용하고 있다.

1. 하나 이상의 스레드를 종료한다. (= process and thread termination)
2. 하나 이상의 스레드로부터 자원을 빼앗는다. (= resource preemption)

📝 detection-and-recovery

• 실질적인 방법이나 필요한 정보를  유지하고, 탐지 알고리즘을 실행하는 오버헤드가 발생하며, deadlock을 회복하는 과정에서 손실이 발생할 수 있다.
• deadlock 상태의 스레드를 종료하거나 자원을 빼앗아서 circular wait 상태를 빠져나온다.