공룡책으로 정리하는 운영체제 - CHAPTER 5. 프로세스 동기화(Process Synchronization)

CHAPTER 5 - 프로세스 동기화(Process Synchronization)

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

---

5.1 배경(Background)

- 동시에 여러 개의 프로세스가 동일한 data에 접근하여 변경하고, 그 실행 결과가 접근이 발생한
  특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 한다.

​- 이런 상황을 방지하기 위해 한순간에 하나의 프로세스만이 data를 변경하도록 보장해야 하며, 
  따라서 어떤 형태로든 프로세스들이 동기화 되도록 할 필요가 있다.

---

5.2 임계 구역 문제(The Critical-Section Problem)

- n 개의 프로세스 {P(0), P(1), ... , P(n-1)}가 있는 시스템에서 각 프로세스는 임계 구역 (Critical Section)이라고 
  부르는 코드를 포함하고 있고, 그 안에서는 다른 프로세스와 공유하는 변수를 변경하는 등의 작업을 수행한다.

​- 이 시스템의 중요한 특징은 "한 프로세스가 자신의 임계 구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계 구역 안에서 실행할 수 없다"라는 점이다.

- 임계 구역 문제(Critical-section problem)은 프로세스들이 협력할 때 사용할 수 있는 프로토콜을 설계하는 것.

- 각 프로세스는 자신의 임계 구역으로 진입하기 위해 허가를 요청해야 하는데, 이러한 요청을 구현하는 코드 부분을
  진입 구역(Entry Section)이라고 하며, 임계 구역 뒤에는 퇴출 구역(Exit Section)이 있을 수 있다.

- 코드의 나머지 부분은 나머지 구역(Remainder Section)이라고 한다.

 

Process P의 일반적인 구조

 

- Critical Section Problem에 대한 해결안은 아래 세 가지 요구 조건을 충족시켜야 한다.

1. 상호 배제(Mutual Exclusion) : 프로세스 P가 자신의 임계 구역(Critical Section)에서 실행된다면,  다른 프로세스들은 그들 자신의 임계 구역(Critical Section)에서 실행될 수 없다.

2. 진행(Progress) : 자신의 임계 구역(Critical Section)에서 실행되는 프로세스가 없는 상황에서 그들 자신의 임계 구역으로 진입하려는 프로세스들이 있다면, 나머지 구역(Remainder section)에서 실행 중이지 않은 프로세스들만 다음에 누가 해당 임계 구역(Critical Section)으로 진입할 수 있는지를 결정하는 데 참여할 수 있으며, 이 선택은 무제한으로 연기될 수 없다.

3. 한정된 대기(Bounded Waiting) : 프로세스가 자신의 임계 구역(Critical Section)에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그 들 자신의 임계 구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.

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

​
- 운영체제 내에서 임계 구역을 다루기 위해 선점형 커널(preemptive kernels)과 비선점형 커널(non-preemptive kernels)의 두 가지 일반적인 접근법이 사용된다.

- 선점형 커널(preemptive kernels)는 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용한다.
- 비선점형 커널(nonpreemptive kernels)는 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고

- 커널 모드 프로세스는 커널을 빠져나갈 때까지, 봉쇄될 때까지, 자발적으로 CPU의 control을 돌려줄 때까지 계속 수행된다.
- 비선점형 커널에서는 경쟁 조건에 대해 고려를 하지 않아도 되지만, 선점형 커널에서는 경쟁 조건이 발생하지 않도록 하기 위해 신중한 설계가 필요하다.
- 선점형 커널은 real-time process가 현재 kernel을 점유하고 있는 process를 선점할 수 있기 때문에 real-time programming에 더 적합하다.

 

---

5.3 피터슨의 해결안(Peterson's Solution)

- 임계 구역 문제를 해결하는 고전적인 소프트웨어 기반 해결책으로 Peterson's Solution이 있다.
- 현대 컴퓨터 구조가 load, store 같은 기본적인 기계어를 수행하는 방식 때문에 Peterson's solution이
  항상 올바르게 작동한다고 보장할 수는 없다.

​- Peterson's Solution은 임계 구역(Critical Section)과 나머지 구역(Remainder Section)을 번갈아 가며 실행하는
  두 개의 프로세스로 한정된다. ( 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가지 조건을 만족해야 한다.

​1. 상호 배제(Mutual Exclusion)이 제대로 지켜진다는 조건
(1) 이 조건을 만족하기 위해서는, 각 P(i)가 임계 구역(Critical Section)에 들어가기 위해서는
     반드시 flag[i] == false거나 turn == i이어야 한다.

(2) 만약 flag[0]과 flag[1]의 값이 모두 true라고 하더라도, turn의 값에 따라 임계 구역에 한 프로세스만
    진입 가능하므로, 위 코드의 while 문을 두 프로세스가 모두 통과할 수 없다.

(3) 정해진 process가 임계 구역에 있을 동안 flag와 turn 값이 변경되지 않으므로, 상호 배제 조건은 지켜진다.

 

2. 진행(Progress)에 대한 요구 조건을 만족한다는 조건

 

3. 대기 시간이 한없이 길어지지 않는다는 조건 (Bounded Waiting)
(1) 2와 3을 증명하기 위해 Peterson's solution에서 임계 구역을 보호하는 방법은 while 문을 이용하는 것이라는 점에 주목해야 한다.

(2) P(j)가 임계 구역에 들어갈 준비가 안 되어 있을 때 flag[j] == false인 상태이고, P(i)는 임계 구역에 진입할 수 있다.

(3) P(j)의 flag[j] == true 일 때는, turn 값에 따라 P(i) 혹은 P(j)가 자신의 임계 구역에 진입하게 될 것이다.

(4) 위의 코드에서 P(i)(혹은 P(j))는 while 문을 수행하는 동안 turn 값을 바꾸지 않기 때문에, P(i)는 P(j)가
    지난번에 진입했다면, 이번에는 자신도 한 번은 (Bounded Waiting) 들어갈 수 있게 보장된다. (Progress)

 

---

5.4 동기화 하드웨어(Synchronization Hardware)

- Peterson's Solution와 같은 Software 기반 해결책은 현대의 컴퓨터 구조에서 올바르게 작동한다는 것을 보장하지 못한다.
- 이에 5.4에서는 프로그래머가 사용할 수 있는 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가지를 모두 만족한다.

​1. Mutual Exclusion : P(i)가 임계 구역에 진입하는 경우는 waiting[i] = FALSE이거나 key= FALSE인 경우이다.
처음으로 임계 구역에 진입하는 프로세스는 key 값을 TRUE로 바꾼 뒤 진입하게 된다. 임계 구역을 실행한 뒤에,
단 한 개의 wating[i] 값을 false로 지정하므로 상호 배제(Mutual Exclusion)이 지켜진다.

2. Progress : 임계 구역을 떠나는 프로세스는 lock을 false로 하거나, waiting[j]를 false로 한다.
이에 어느 쪽이든 둘 다 임계 구역으로 들어가고자 하는 프로세스를 진입하게 만들어준다.

3. Bounded waiting : 프로세스가 임계 구역을 떠날 때, waiting 배열을 순환하면서 검사하게 된다.
자신의 순서 이후부터 차례대로 보기 때문에, 임계 구역에 들어가고자 하는 프로세스는 최대 (n-1) 번만 기다리면 된다.

 

---

5.5 Mutex Locks

- 5.4에서 설명했던 임계 구역에 대해 하드웨어 기반 해결책은 복잡한 형태를 가지고 있다.
- 이에 간단한 소프트웨어 도구들을 개발했으며, 대표적으로 Mutex Lock이 있다.
- 임계 구역에 들어가기 전에 lock을 획득해야 하고, 임계 구역을 빠져나올 때 lock을 반환해야 한다.
- 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들은 반복)

 

---

5.6 세마포(Semaphores)

- Semaphore S는 정수 변수로서, wait()와 signal()로 접근이 가능하다.

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

signal(S) {
   S++;
}

 

* 세마포 사용법(Semaphore Usage)

- Counting Semaphore와 Binary Semaphore(Mutex Lock과 유사하게 동작)로 사용할 수 있다.
- Coutning Semaphore는 제한 없는 domain을 가지며, binary Semaphore는 0과 1의 값만 가능하다.

​- 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)

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

- 예를 들어, 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을 사용한다.

 

---

5.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개를 집게 되면 식사를 할 수 있다.
- 식사를 마치면, 두 개의 젓가락을 놓은 뒤, 다시 생각하기 시작한다.

dining-philsophers problem

- 식사하는 철학자(Dining philsophers) 문제는 고전적인 동기화 문제이다.
- 한 가지 해결책은 갓 젓가락을 하나의 semaphore로 표현하는 것이다.
- 철학자는 각 semaphore(젓가락)에 wait() 연산을 수행하여 젓가락을 집으려고 시도한다.
- 철학자는 각 semaphore(젓가락)에 signal() 연산을 수행하여 자신이 집었던 젓가락을 놓는다.

​- 위의 해결책은 deadlock 상태를 유발할 수 있다.
- 이에 deadlock 문제를 해결하기 위해 아래 해결책을 사용할 수 있다.
   (1) 최대 4명의 철학자들만이 테이블에 동시에 앉을 수 있게 한다.
   (2) 한 철학자가 젓가락 두 개를 모두 집을 수 있을 때만 젓가락을 집도록 허용한다.
   (3) 홀수 번호의 철학자들은 먼저 왼쪽 젓가락을 집게하고, 짝수 번호는 오른쪽 젓가락을 먼저 집게 한다.

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

 

---

5.8 모니터(Monitor)

- 아래의 경우, 임계 구역에 많은 프로세스들이 실행될 수 있어 mutual exclusion이 지켜지지 않는다.

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

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

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

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

 

---

5.9 동기화 사례(Synchronization Examples)

* Windows의 동기화

- kernel 외부에서 thread를 동기화하기 위하여 dispatcher 객체를 제공한다.
- dispatcher 객체는 signaled 상태에 있을 수도 있고, nonsignaled 상태에 있을 수도 있다.
   (1) signaled 상태 : 객체가 사용 가능하고, 그 객체를 얻을 때 그 스레드가 봉쇄되지 않음.
   (2) nonsignaled 상태 : 객체가 사용 가능하지 않고, 그 객체를 얻으려고 시도하면 그 스레드가 봉쇄됨.
- critical-section 객체는 커널의 개입 없이 획득하거나 방출할 수 있는 사용자 모드 mutex이다.

​* Linux의 동기화

- version 2.6 이전에 Linux은 비선점형 kernel이었으며, 그 이후부터는 선점형 kenel이다.
- Linux에서는 kernel 안의 임계 구역(Critical Section)을 보호하기 위해 mutex lock이 제공된다.

​

* Solaris의 동기화

- 임계 구역(Critical Section)을 제어하기 위해, adaptive mutex locks, condition variables,
  semaphores, 그리고 reader-writer lock, tunrstiles를 제공한다.

​

* Pthreads 동기화

- Pthreads API는 사용자 수준에서 프로그래머가 사용할 수 있으며, 어떤 특정한 kernel의 일부분이 아니다.
- 이 API는 thread synchronization을 위하여 mutex lock, condition variable과 reader-writer lock을 제공한다.

 

---

5.10 대체 방안들

* 트랜잭션 메모리(Transactional Memory)

- 트랜잭션 메모리의 개념은 데이터베이스 분야에서 출발한 아이디어지만, 프로세스 동기화에 사용될 수 있다.
- 트랜잭션 메모리는 소프트웨어와 하드웨어로 구현될 수 있다.
​- 이 밖에도, OpenMP, 함수형 프로그래밍 언어 등이 있다.

---

-Reference-
Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』