Ch.6 Synchronization

2022. 6. 18. 01:04

임계 구역 문제(Critical-section problem)와 해결책에 대해서 알 수 있습니다.
여러 전통적인 프로세스 동기화(Process Synchronization) 문제에 대해서 알 수 있습니다.
프로세스 동기화(Process Synchronization)를 해결하기 위해 사용되는 여러 도구들을 알 수 있습니다.

6.1. Background

동시에 여러 개의 프로세스가 동일한 data에 접근하여 변경하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 합니다. 이런 상황을 방지하기 위해 한순간에 하나의 프로세스만이 data를 변경하도록 보장해야 하며, 따라서 어떤 형태로든 프로세스들이 동기화 되도록 할 필요가 있습니다. 프로세스는 동시에 실행될 수 있으며, 여러 개의 프로세스가 협력할 때는 프로세스 사이에 데이터가 동기화되지 않는 문제가 발생할 수 있습니다. 만약 두 프로세스가 동시에 어떤 변수의 값을 바꾼다면 프로그래머의 의도와는 다른 결과가 나올 것입니다.

6.2. The Critical-Section Problem

시스템에서 각 프로세스가 코드상에서 경쟁 조건이 발생할 수 있는 특정 부분을 임계구역(critical section)이라고 부르는 코드를 포함하고 있고, 그 안에서는 다른 프로세스와 공유하는 변수를 변경하는 등의 작업을 수행합니다. 이 시스템의 중요한 특징은 "한 프로세스가 자신의 임계 구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계 구역 안에서 실행할 수 없다"라는 점입니다. 임계 구역 문제(Critical-section problem)은 프로세스들이 협력할 때 사용할 수 있는 프로토콜을 설계하는 것이 중요합니다. 각 프로세스는 자신의 임계 구역으로 진입하기 위해 허가를 요청해야 하는데, 이러한 요청을 구현하는 코드 부분을 진입 구역(Entry Section)이라고 하며, 임계 구역 뒤에는 퇴출 구역(Exit Section)이 있을 수 있습니다. 코드의 나머지 부분은 나머지 구역(Remainder Section)이라고 합니다. 프로세스의 일반적인 구조는 다음과 같습니다.

임계 구역 문제에 대한 해결안은 아래 세 가지 요구 조건을 충족시켜야 합니다.

상호 배제(Mutual Exclusion) : 프로세스 P가 자신의 임계 구역(Critical Section)에서 실행된다면, 다른 프로세스들은 그들 자신의 임계 구역(Critical Section)에서 실행될 수 없습니다.
진행(Progress) : 자신의 임계 구역에서 실행되는 프로세스가 없는 상황에서 그들 자신의 임계 구역으로 진입하려는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 해당 임계 구역으로 진입할 수 있는지를 결정하는 데 참여할 수 있으며, 이 선택은 무제한으로 연기될 수 없습니다.
한정된 대기(Bounded Waiting) : 프로세스가 자신의 임계 구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계 구역에 진입하도록 허용되는 횟수에 한계가 있어야 합니다.

임의의 한순간에 많은 Kernel-mode process들이 운영체제 안에서 사용될 수 있으며, 그 결과 운영체제를 구현하는 코드(Kernel Code)는 경쟁 조건이 발생하기 쉽습니다. 예를 들어, 메모리 할당을 관리하는 자료구조, 프로세스 리스트를 관리하는 자료구조 등에서 경쟁 조건이 많이 발생할 수 있습니다.

운영체제 내에서 임계 구역을 다루기 위해 선점형 커널(preemptive kernels)과 비선점형 커널(nonpreemptive kernels)의 두 가지 일반적인 접근법이 사용됩니다. 선점형 커널은 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용합니다. 비선점형 커널는 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고 커널 모드 프로세스는 커널을 빠져나갈 때까지, 봉쇄될 때까지, 자발적으로 CPU의 control을 돌려줄 때까지 계속 수행됩니다. 비선점형 커널에서는 실행되는 프로세스가 하나기 때문에 경쟁 조건에 대해 고려를 하지 않아도 되지만, 선점형 커널에서는 경쟁 조건이 발생하지 않도록 하기 위해 신중한 설계가 필요합니다.

선점형 커널은 real-time process가 현재 kernel을 점유하고 있는 process를 선점할 수 있기 때문에 real-time programming에 더 적합하고, 더 응답이 민첩할 수 있기 때문에 선호되고 있습니다.

6.3. Peterson's Solution

Peterson’s solution으로 임계 영역 문제를 해결할 수 있습니다. 현대 컴퓨터 구조가 load, store 같은 기본적인 기계어를 수행하는 방식 때문에 Peterson's solution이 항상 올바르게 작동한다고 보장할 수는 없습니다. 임계 영역에서 프로세스가 작업중인지 저장하는 변수flag와 critical section에 진입하고자하는 프로세스를 가리키는 변수 turn 을 만들어 어떤 프로세스가 임계 영역에 진입하면 flag를 lock하고, 나오면 unlock하는 방식으로 임계 영역 문제를 해결합니다.

이를 풀어서 설명하면, Peterson's Solution은 임계 구역과 나머지 구역을 번갈아 가며 실행하는 두 개의 프로세스로 한정됩니다. ( P(0)와 P(1)으로 한정하여 설명) Perterson's solution은 두 프로세스가 아래 두 개의 데이터 항목을 공유하도록 하여 임계 구역 문제를 해결합니다.

int turn;
boolean flag[2];

변수 turn은 임계 구역으로 진입할 순번을 나타낸다. (turn == i)이면, 프로세스 P(i)가 임계 구역에서 실행될 수 있음을 나타냅니다.

flag 배열은 프로세스가 임계 구역으로 진입할 준비가 되었다는 것을 의미합니다. flag[i]가 참이라면, P(i)가 임계 구역으로 진입할 준비가 되었다는 것을 나타냅니다. 임계 구역으로 진입하기 위해서는 P(i)는 먼저, flag[i]를 True로 만들고 turn을 j로 지정합니다. 이렇게 함으로써, 프로세스 j가 임계 구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장합니다. turn의 값이 궁극적으로 어떤 프로세스가 먼저 임계 구역으로 진입할 것인가를 결정합니다. Peterson's solution에서 P(i)의 구조는 아래와 같습니다.

do {
  flag[i] = TRUE;
  turn = j;

  while(flag[j] && turn == j);

  [CRITICAL SECTION]

  flag[i] = FALSE;

  [REMAINDER SECTION]

} while (TRUE);

Peterson's solution이 임계 구역 문제를 해결한다는 것을 보장하기 위해 3가지 조건을 만족해야 합니다.

상호 배제(Mutual Exclusion)이 제대로 지켜진다는 조건
- 이 조건을 만족하기 위해서는, 각 P(i)가 임계 구역(Critical Section)에 들어가기 위해서는 반드시 flag[i] == false이든지 아니면 turn == i이어야 합니다.
- 만약 flag[0]과 flag[1]의 값이 모두 true라고 하더라도, turn의 값에 따라 임계 구역에 한 프로세스만 진입 가능하므로, 위 코드의 while 문을 두 프로세스가 모두 통과할 수 없습니다.
- 정해진 process가 임계 구역에 있을 동안 flag와 turn 값이 변경되지 않으므로, 상호 배제 조건은 지켜집니다.
진행(Progress)에 대한 요구 조건을 만족한다는 조건
대기 시간이 한없이 길어지지 않는다는 조건 (Bounded Waiting)
- 2와 3을 증명하기 위해 Peterson's solution에서 임계 구역을 보호하는 방법은 while 문을 이용하는 것이라는 점에 주목해야 합니다.
- P(j)가 임계 구역에 들어갈 준비가 안 되어 있을 때 flag[j] == false인 상태이고, P(i)는 임계 구역에 진입할 수 있습니다.
- P(j)의 flag[j] == true 일 때는, turn 값에 따라 P(i) 혹은 P(j)가 자신의 임계 구역에 진입하게 될 것입니다.
- 위의 코드에서 P(i)(혹은 P(j))는 while 문을 수행하는 동안 turn 값을 바꾸지 않기 때문에, P(i)는 P(j)가지난번에 진입했다면, 이번에는 자신도 한 번은 (Bounded Waiting) 들어갈 수 있게 보장됩니다.

6.4 Synchronization Hardware

Peterson's Solution와 같은 Software 기반 해결책은 현대의 컴퓨터 구조에서 올바르게 작동한다는 것을 보장하지 못합니다. 이에 프로그래머가 사용할 수 있는 Hardware에서부터 Software 기반 API를 아우르는 기법을 사용한 임계 구역 문제(Critical Section Problem)의 해결책들에 대해서 알아보겠습니다. 이 모든 해결책들은 임계 구역을 보호하기 위해 Lock을 사용한다는 점에 기반을 둡니다.

single-processor 환경에서는 공유 변수가 변경되는 동안 interrupt 발생을 허용하지 않음으로써 임계 구역 문제(Critical Section Problem)을 간단히 해결할 수 있습니다. 명령어들이 순차적으로 수행되기 때문에, 공유 변수에 예기치 못한 변화가 생기지 않기 때문이다. 비선점형 커널(Nonpreemptive kernel)이 이 방법을 사용합니다.

Multi-processor 환경에서는 위의 해결책을 사용하면, 시스템 효율이 떨어지기 때문에 사용하지 않습니다. 많은 modern computer들은 인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어를 제공합니다. 예를 들어, test_and_set()과 compare_and_swap()이 있으며 코드는 아래와 같습니다. test_and_set 명령어는 원자적(atomically)으로 실행된다는 점이 특징입니다.

boolean test_and_set(boolean *target){
  boolean rv = *target;
  *target = true;
  return rv;
}

만일 기계가 test_and_set() 명령을 지원한다면, false로 초기화되는 Boolean type의 lock 변수를 선언하여 아래 코드와 같이 상호 배제(Mutual Exclusion)을 구현할 수 있습니다.

do {
   while (test_and_set(&lock))
        ;   // do nothing
        // critical section

    lock = FALSE;
 
        // remainder section
} while (TRUE);

compare_and_swap() 명령어는 세 개의 피연산자를 parameter로 전달받습니다. 피연산자 value는 오직 (*value == expected) 수식이 참일 때에만, new_value로 지정됩니다. compare_and_swap() 명령어는 언제나 원래의 value 값을 return 합니다.

int compare_and_swap(int *value, int expected, int new_value){
   int temp = *value;

   if(*value == expected)
      *value = new_value;

   return temp;
}

위의 알고리즘들은 상호 배제(Mutual Exclusion) 조건은 만족하지만, 한정된 대기(Bounded Waiting)을 만족하지 못합니다. 이에 임계 구역 요구 조건을 모두 만족시키기 위해 아래와 같이 코드를 작성할 수 있습니다. 맨 처음에, waiting 배열과 lock 변수는 false로 초기화되어 있습니다.

boolean waiting[n] = {0};
boolean lock = FALSE;

do {
  waiting[i] = true;
  key = true;
  
  while(waiting[i] && key)
    key = test_and_set(&lock);

  waiting[i] = false;

  // critical section

  j = (i+1) % n;
  while((j != i) && !waiting[j])
    j = (j+1) % n;

  if(j == i)
    lock = false;
  else
    waiting[j] = false;

  // remainder section
} while (true);

위의 코드는 임계 구역 조건 3가지를 모두 만족합니다.

Mutual Exclusion : P(i)가 임계 구역에 진입하는 경우는 waiting[i] = FALSE이거나 key= FALSE인 경우입니다. 처음으로 임계 구역에 진입하는 프로세스는 key 값을 TRUE로 바꾼 뒤 진입하게 됩니다. 임계 구역을 실행한 뒤에, 단 한 개의 wating[i] 값을 false로 지정하므로 상호 배제(Mutual Exclusion)이 지켜집니다.
Progress : 임계 구역을 떠나는 프로세스는 lock을 false로 하거나, waiting[j]를 false로 합니다. 이에 어느 쪽이든 둘 다 임계 구역으로 들어가고자 하는 프로세스를 진입하게 만들어줍니다.
Bounded waiting : 프로세스가 임계 구역을 떠날 때, waiting 배열을 순환하면서 검사하게 됩니다. 자신의 순서 이후부터 차례대로 보기 때문에, 임계 구역에 들어가고자 하는 프로세스는 최대 (n-1) 번만 기다리면 됩니다.

6.5 Mutex Locks

6.4에서 설명했던 임계 구역에 대해 하드웨어 기반 해결책은 복잡한 형태를 가지고 있습니다. 이에 간단한 소프트웨어 도구들을 개발했으며, 대표적으로 Mutex Lock이 있습니다. mutex locks은 여러 스레드가 공통 리소스에 접근하는 것을 제어하는 기법으로, lock이 하나만 존재할 수 있는 locking 매커니즘을 따릅니다. (참고로 'mutex’는 'MUTual EXclusion’을 줄인 말이다.) 이미 하나의 스레드가 critical section에서 작업중인 lock 상태에서 다른 스레드들은 critical section에 진입할 수 없도록 합니다. acquire()를 통해 lock을 획득하고, relase()를 통해 lock을 반환합니다. mutex lock에서는 available이라는 변수를 통해 lock의 가용 여부를 표시합니다.

do {
     acquire lock
         [CRITICAL SECTION]
     release lock
         [REMAINDER SECTION]
} while(true);

acquire(){
  while (!available)
    ; /* busy waiting */
  available = false;
}

release() {
  available = true;
}

지금까지 설명한 방식들의 단점은 바쁜 대기(Busy Waiting)을 해야 한다는 점입니다. 즉, 한 프로세스가 임계 구역에 있는 동안에 다른 프로세스들은 계속해서 반복문을 호출해야 합니다. 위의 유형의 mutex lock은 lock이 가용되기를 기다리며 계속 회전하므로 spinlock이라고도 부릅니다. 이는 다중프로그래밍(Multiprogramming system)에서 CPU 사이클을 낭비하게 만듭니다.

그러나, lock을 기다리는 동안 시간을 소모하는 Context switch를 전혀 필요로 하지 않는다는 장점이 있습니다. 따라서, 프로세스들이 짧은 시간 동안만 lock을 소유할 것이라고 예상되면, spinlock이 좋을 수 있습니다. spinlock은 multi-processor 시스템에서 많이 사용됩니다. (한 processor는 임계 구역, 다른 processor들은 반복)

6.6 세마포(Semaphores)

세마포어(Semaphore)는 여러 개의 프로세스나 스레드가 critical section에 진입할 수 있는 locking 매커니즘입니다. 세마포어는 카운터를 이용해 동시에 리소스에 접근할 수 있는 프로세스를 제한합니다. 물론 한 프로세스가 값을 변경할 때 다른 프로세스가 동시에 값을 변경하지는 못합니다. 세마포어는 P와 V라는 명령으로 접근할 수 있습니다. (P, V는 try와 increment를 뜻하는 네덜란드어 Proberen과 Verhogen의 머릿글자다.) Semaphore S는 정수 변수로서, wait()와 signal()로 접근이 가능합니다.

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

signal(S) {
   S++;
}

세마포 사용법(Semaphore Usage)

세마포어의 카운터가 한 개인 경우 바이너리 세마포어(Binary semaphore), 두 개 이상인 경우 카운팅 세마포어(Counting semaphore)라고 합니다. 바이너리 세마포어는 사실상 mutex와 같습니다. Binary Semaphore는 종종 상호 배제(Mutual Exclusion)을 보장하기 위해 사용됩니다. Counting Semaphore는 유한한 개수를 가진 resource에 대한 접근을 제어하는 데 사용되며, semaphore는 가용한 자원의 개수로 초기화됩니다. wait() 연산을 수행하면 sempahore 값이 감소되며, signal() 연산을 수행하면 semaphore 값은 증가합니다. semaphore 값이 0이 되면, 모든 자원이 사용 중임을 나타냅니다. 이후 자원을 사용하려는 프로세스는 semaphore 값이 0보다 커질 때까지 blocking 됩니다.

구현 (Semaphore Implementation)

간단한 Semaphore에서는 wait() 연산시에 반복문을 통해 Busy Waiting을 해야 합니다. 효율적인 연산을 수행하기 위해, wait()와 signal()을 다음과 같이 변경할 수 있습니다.

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

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

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

wait() 연산에서 busy waiting 대신 자신을 blocking 시킵니다. block() 함수에서 프로세스를 semaphore에 연관된 waiting queue에 넣고, 프로세스의 상태를 waiting으로 전환합니다. 그 후, control이 스케줄러에게 넘어가고 스케줄러는 다른 프로세스를 실행하기 위해 선택한다. block() 함수는 자신을 호출한 프로세스를 중지시킵니다.

blocking된 process는 다른 프로세스가 signal() 연산을 실행하면 재시작되어야 합니다. 프로세스는 wakeup() 연산에 의하여 재시작되고, 프로세스의 상태를 waiting에서 ready 상태로 변경합니다. 프로세스는 ready queue에 넣어지게 됩니다. wakeup(P)는 blocking 된 process P의 실행을 재개시킵니다. busy waiting을 하는 semaphore에서 semaphore는 음수의 값을 가질 수 없지만, 위와 같이 구현한 semaphore에서는 semaphore가 음수의 값을 가질 수 있으며, 해당 값은 semaphore를 대기하고 있는 프로세스들의 수를 나타냅니다.

원칙적으로, semaphore는 두 프로세스가 동시에 wait()와 singal() 연산들을 수행할 수 없도록 반드시 보장해야 합니다. Single-Processor 환경에서는 두 연산들이 실행되는 동안 인터럽트를 금지시키면 됩니다. Multi-Processor 환경에서는 모든 processor의 인터럽트를 금지시킴으로써 구현할 수 있으나, 성능을 매우 감소시킬 수 있기 때문에 compare_and_swap()과 같은 locking 기법을 사용해야 합니다.

교착 상태와 기아(Deadlock and Stravation)

두 프로세스가 서로 종료될 때까지 대기하는 프로그램을 실행한다고 생각하면, 프로세스 A는 B가 종료될 때까지, 프로세스 B는 A가 종료될 때까지 작업을 하지 않기 때문에 프로그램은 어떤 동작도 하지 못할 것입니다. 이처럼 두 프로세스가 리소스를 점유하고 놓아주지 않거나, 어떠한 프로세스도 리소스를 점유하지 못하는 상태가 되어 프로그램이 멈추는 현상을 데드락(Deadlock)이라고 합니다. 운영체제도 결국 소프트웨어이기 때문에 데드락에 빠질 수 있습니다.

waiting queue를 통한 semaphore의 구현은 두 개 이상의 프로세스들이 대기 중인 프로세스의 사건을 무한정 기다리는 상황이 발생할 수 있습니다.

예를 들어, P(0)와 P(1)이 모두 wait()를 실행하게 되면, P(0)는 P(1)이 signal()을 실행할 때까지 기다리며, P(1)은 P(0)가 signal()을 실행할 때까지 기다리게 된다. 이에 P(0)와 P(1)은 deadlock 상태가 됩니다.

deadlock과 관련된 다른 문제는 무한 봉쇄(indefinite blocking) 혹은 기아(starvation) 문제입니다. 이는 프로세스들이 semaphore에서 무한정 대기하게 됩니다. (LIFO 순서에서 발생할 수 있음.)

우선순위 역전(Priority Inversion)

높은 우선순위의 프로세스가 낮은 우선순위 프로세스들에 의해 접근되고 있는 kernel data를 읽기/수정해야 할 필요가 있을 때, 스케줄링에 어려움이 있습니다. 보통 kernel data의 경우, lock에 의해 보호되기 때문에 낮은 우선순위 프로세스가 resource 사용을 마칠 때까지 높은 우선순위의 프로세스가 기다리는 상황이 발생합니다. 예를 들어, L<M<H의 우선순위를 가지는 프로세스가 존재한다고 할 때, 프로세스 H가 프로세스 L의 자원을 필요한 상황에서 프로세스 M 이 프로세스 L을 선점하게 되면, 프로세스 M 이 프로세스 H의 실행 시간에 영향을 줍니다. 이런 문제를 우선순위 역전(priority inversion)이라고 이 문제는 셋 이상의 우선순위를 가진 시스템에서만 발생하므로 두 개의 우선순위만을 사용하여 해결할 수 있습니다. 하지만, 범용 운영체제에서는 그것이 힘드므로, priority-inheritance protocol을 사용합니다.

6.7. 고전적인 동기화 문제들 (Classic Problems of Synchronization)

유한 버퍼 문제(The Bounded-Buffer Problem)

int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;

do {
  wait(full);
  wait(mutex);
     ...
  // remove an item from buffer to nextc
     ...
  signal(mutex);
  signal(empty);
     ...
  // consume the item to nextc
     ...
} while (TRUE);

mutex semaphore는 buffer pool을 접근하기 위한 mutual exclusion 기능을 제공합니다. empty와 full semaphore는 각각 비어 있는 buffer의 수와 꽉 찬 buffer의 수를 기록합니다.

Readers-Writers 문제(The Readers-Writers Problem)

프로세스들 중 읽기만을 원하는 프로세스, 쓰기를 원하는 프로세스가 존재할 수 있습니다. 만약 두 reader가 동시에 공유 데이터에 접근하더라도, 문제는 발생하지 않습니다. 하지만, 하나의 writer와 다른 reader(혹은 writer)가 동시에 접근하면 문제가 발생할 수 있습니다. 이에, writer가 쓰기 작업을 공유 데이터에 하는 동안 exclusive 한 access를 가지도록 해야 합니다. 이 동기화 문제를 readers-writers problem라고 합니다.

readers-writers problem은 여러 가지 변형이 존재합니다. 첫 번째, writer가 공유 object에 대한 허가를 아직 얻지 못했다면 어느 reader도 기다리게 해서는 안 됩니다. 두 번째, writer가 객체를 접근하려고 기다리고 있다면, 새로운 reader들은 읽기를 시작하지 못합니다. 첫 번째 방식은 writer에 대한 starvation, 두 번째 방식은 reader에 대한 starvation을 발생시킬 수 있습니다. 첫 번째 reader-writer problem의 해결책에서, reader 프로세스는 아래와 같은 자료구조를 공유합니다.

semaphore rw_mutex = 1; 
semaphore mutex = 1;
int read_count = 0;

rw_mutex semaphore는 reader와 writer가 모두 공유합니다. mutex semaphore는 read_count를 갱신할 때, mutual exclusion을 보장하기 위해 사용됩니다. read_count는 현재 몇 개의 프로세스들이 객체를 읽고 있는지 알려줍니다. writer process의 구조는 아래와 같습니다.

do {
   wait(rw_mutex);
      ...
   /* writing is performed */
      ...
   signal(rw_mutex);
} while (true)

reader process의 구조는 아래와 같습니다.

do {
   wait(mutex);
   read_count++;
   
   if(read_count == 1)
     wait(rw_mutex);
   signal(mutex);
     ...
   /* reading is performed */
     ...
   wait(mutex);
   read_count--;

   if(read_count == 0)
      signal(rw_mutex);

   signal(mutex);
} while (true)

Readers-writers problem을 해결하기 위해, 몇몇 시스템에서는 reader-writer lock을 제공합니다. 다수의 process들이 reader mode의 reader-writer lock을 획득할 수 있습니다. 하나의 process만이 writer mode의 reader-writer lock을 획득할 수 있습니다.

식사하는 철학자들 문제(The Dining-Philsophers Problem)

데드락에 관한 유명한 비유가 있다. 철학자 5명이 식탁 가운데 음식을 두고 철학자들은 사색과 식사를 반복합니다. 포크는 총 5개, 단 음식을 먹으려면 2개의 포크를 사용해야 합니다. 즉, 동시에 음식을 먹을 수 있는 사람은 두 명뿐이며, 운이 좋으면 5명의 철학자들이 돌아가면서 사색과 식사를 이어갈 수 있다. 하지만 모두가 포크를 하나씩 들고 식사를 하려하면 누구도 식사를 할 수 없는 상태, 다시말해 데드락에 빠져 버립니다. 이것이 바로 철학자들의 만찬 문제(Dining-Philosophers Problem)입니다. 여기서 철학자는 thread, 젓가락은 semaphore에 해당하며 철학자는 젓가락을 wait() 연산을 통해 젓가락을 집고, signal()을 통해 젓가락을 놓는 것을 구현할 수 있습니다.

이는 다음을 통해 해결할 수 있습니다.

최대 4명의 철학자들만이 테이블에 동시에 앉을 수 있게 합니다.
한 철학자가 젓가락 두 개를 모두 집을 수 있을 때만 젓가락을 집도록 허용합니다.
홀수 번호의 철학자들은 먼저 왼쪽 젓가락을 집게하고, 짝수 번호는 오른쪽 젓가락을 먼저 집게 합니다.

deadlock 상태를 제거한다고 해서, 꼭 starvation의 가능성을 제거하는 것은 아닙니다.

6.8. 모니터(Monitor)

식사하는 철학자 문제에서 교착 상태없는 해결법을 통해 모니터 해결법에 대해 알아봅시다. 모니터는 말 그대로 상태를 관찰하면서 접근합니다. 철학자는 젓가락을 둘 다 사용할 수 있을 때만 집을 수 있게 제한하고 코딩을 위해 아래 데이터 구조로 표현합니다. 아래의 경우, 임계 구역에 많은 프로세스들이 실행될 수 있어 mutual exclusion이 지켜지지 않습니다.

signal(mutex);
   ...
   critical section
   ...
wait(mutex);

아래의 경우, deadlock 상태가 발생하게 됩니다.

wait(mutex);
   ...
   critical section
   ...
wait(mutex);

프로그래머들이 semaphore를 잘못 사용하면 다양한 오류가 발생할 수 있다. 이에 monitor를 사용합니다.

'CS > Operation System' 카테고리의 다른 글

Ch.8 Memory-Management Strategies (0)	2022.07.05
Ch.7 Deadlocks (0)	2022.06.18
Ch.5 Process Scheduling (0)	2022.06.18
Ch.4 Multithreaded Programming (0)	2022.06.17
Ch.3 Process (0)	2022.06.17

C++, 그래픽 기술 블로그