Chapter 06. Synchronization Tools

배경)

이전장에서 프로세스가 병렬로 실행되는 경우를 살펴봤다.

프로세스가 병렬 실행될 때 여러 프로세스에 공유하는 데이터의 무결성 문제에 대해서 알아본다.

동시에 여러 프로스세스가 동일한 데이터에 접근해서 조작하고 실행 결과가 순서에 의존하는 경우를 

Race Condition 이라고 부른다.

따라서 한순간에 하나의 프로세스만이 데이터를 조작하도록 보장해야 한다.

따라서 이러한 이유로 동기화가 필요한 것이다.

Race Condition의 예

위 그림을 보면 a, b, c와 1,2,3의 문맥 교환 순서에 따라서 최종 값이 달라짐을 알 수 있다.

컴퓨터를 통해 동일한 연산을 실행하면 항상 같은 값을 출력해줘야 하기 때문에 동기화가 필수적이다.

 

Critical Section)

n개의 프로세스가 존재할 때 각 프로세스는 critical section이라고 부르는 코드를 포함하고 있다.

해당 코드는 적어도 하나 이상의 다른 프로세스와 공유하는 데이터를 접근하고 갱신할 수 있다.

특징은 프로세스들이 병렬로 실행될 때 하나의 프로세스에서 critical section에 해당하는 코드가 실행되고 있다면

다른 프로세스는 자신의 critical section에 해당하는 코드를 실행할 수 없다는 것이다.

이는 데이터를 협력적으로 공유하기 위한 일종의 약속(Protocol)이다.

각 프로세스는 entry section에서 진입 허가를 요청하고 exit section을 통해서 탈출한다.

Critical Section Problem의 해결안은 3가지 요구 조건을 충족해야 한다.

 

1. Mutal Exclusion(상호 배제): 하나의 프로세스에서 임계 구역에 해당하는 코드가 실행되고 있다면 다른 프로세스 에서는 임계구역에 해당하는 코드를 실행 할 수 없다.

 

2. Progress(진행): 임계 구역에 진입하려고 하는 프로세스들이 있다면 나머지 구역에서 실행중이지 않은 프로세스들만이 다음 임계구역으로 누가 진입할것인가 결정하는데 참여 할 수 있고 이 선택은 무한정 연기될 수 없다. 즉 누군가는 반드시 critical section에 들어가야 한다는 것이다.

 

3. Bounded Waiting(한정된 대기): 임계구역 진입에 허용된 횟수에 한계가 있어야 한다.

 

OS의 임계 구역을 다루기 위해서는 Preemtive Kernel(선점형 커널)과 Non-Preemtive Kernel(비선점형 커널) 두 가지가 있다.

 

선점형 커널 - 프로세스의 커널 모드 수행 시 선점되는 것을 허용한다. 반응이 더 빠르지만 경쟁 조건을 신중하게 고려해야 한다.

 

비선점형 커널 - 커널 모드 수행 시에도 프로세스 선점을 허용하지 않고 프로세스가 커널을 빠져나갈 때까지 또는 block 될 때 까지 혹은 자발적으로 cpu제어를 양보할 때 까지 계속 수행된다.

 

 

Peaterson's Solution)

두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다.

p0와 p1이 critical section에 들어가기 전까지의 상황을 보면

p0에서 flag [0] = True, turn = 1

p1에서 flag [1] = True, turn = 0 이 된다.

p1의 while문의 경우 조건을 만족하기에 계속 반복된다. 그러나 p0의 while문은 turn이 0으로 조건을 만족하지 않고

탈출해서 critical section에 진입한다. 그리고 flag [0] = false가 된다.

p0는 critical section에서 탈출하게 되고 p1의 while문 안의 조건이 만족하지 않기에 이번에는 p1이 critical section에 진입한다.

 

1. critical section에서 하나의 연산만 수행되므로 Mutal Exclusion이 보장된다.

 

2. 각 프로세스의 Critical Section이 실행되는 동안 while 문에 의해 프로세스가 유한하게 대기하도록 하기 때문에 Progress를 만족한다.

 

3. Critical Section에 진입 요청 후 다른 프로세스에서 critical section을 시행하는 동안 유한하게 대기하기 때문에 bounded waiting도 지켜진다.

 

Hardware Instructions)

test_and_set : lock이라는 공유 변수가 한 프로세스에서 false 일 경우 lock을 trye로 만들고 critical section을 실행한다.

이를 빠져나온 후 다시 lock을 false로 바꾼 후 다른 프로세스가 critical section을 실행하도록 한다.

 

compare_and_swap : 임계 구역에 진입하기 위해서는 waiting [i] == false 이거나 key == 0 이어야 한다.

i를 순차적으로 증가시켜서 자신과 같아질 때까지 무한 루프를 돌게 한다.

critical solution의 3가지 요구조건을 모두 만족한다.

 

Mutex Lock) 

Mutal Exclusion Lock의 축약 형태이다.

Critical Seciton을 보호하고 Racing Condition을 방지하기 위해 사용한다.

프로세스는 Critical Section에 들어가기 전에 반드시 lock을 획득해야 하고 Critical Section을 빠져나올 때 lock을 반환해야 한다.

 

Mutex Lock

acquire() : lock을 획득하는 함수

release(): lock을 반환하는 함수

available(): lock의 가용 여부 판단하는 함수

 

 

단점은 busy waiting이라는 것이다. 프로세스가 임계 구역에 있는 동안 다른 프로세스 들은 임계구역에 들어가기를 원할 때 acquire 함수를 호출하는 반복문을 계속 수행해야 한다.

 

장점은 lock을 사용할 수 있을 때까지 프로세스가 회전한다. 문맥 교환에 상당한 시간이 걸릴 때 이는 문맥 교환을 하지 않는다는 장점이 있다.

이를 spinlock이라고 한다. 일반적으로 lock이 유지되는 시간이 문맥 교환을 두 번(스레드 대기, 스레드 복원) 하는 시간보다 짧은 경우 스핀 락을 사용한다. 최신 멀티 코어 시스템을 지원하는 OS는 해당 기술이 널리 사용된다.

 

Semaphores)

세마포어란 임계 구역 진입이 어려울 때 자발적으로 Block 상태에 들어가는 것이다.

Busy Waiting을 하지 않아도 되는 장점이 있다.(Block - Wakeup 방식)

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

wait(s){
 // 나 자원 쓸래
  s.value--;
 // 근데 없으면
  if(s.value < 0){
    // 큐에 걸어놓고 자고 있어야지
    // add this process to s.queue; 
    block();
  }
}

signal(s){
 // 나 다썼어
  s.value++;
 // 근데 없네 누가 쓰려고 큐에서 기다리나보다
  if(s.value <= 0){
    // remove a process P from s.queue;
    // 깨우기. 너 쓸 차례야
    wakeup(P);
  }
}

//출처: https://velog.io/@klloo/semaphore-mutex

value = 사용 가능한 자원의 수

 

<Block - Wakeup 방식>

1. 자원의 값을 하나 감소시킨다.

2. 자원의 개수가 0보다 작다면 blcok()을 실행시켜 Q에 현재 프로세스를 추가 시킴 즉, block 상태에 진입

3. 다른 프로세스가 작업을 완료해서 signal()을 호출해서 자원의 값을 하나 증가 시킴 이때 자원의 값이 0보다 작거나 같다면 누군가 block 상태에 있단 의미

4. wakeup()을 통해서 Q에 있는 프로세스를 선입선출로 꺼내서 자원을 할당해서 프로세스를 실행한다.

 

s = 자원의 수;

wait(s){
  while(s <= 0) ; //busy waiting s가 1 이상이면 빠져나옴
  s--; // 자원 획득
}

signal(s){
  s++; // 자원 반납
}

do {
   wait(s);
   //ciritical section
   signal(s);
  //remainder section
} while(1);

<Busy - Wait 방식>

1. s가 1 이상 즉, 자원에 여유가 있으면 wait()을 통해서 s-- 를 통해서 자원 획득

2. 다 사용하면 signal()을 통해서 s++로 자원을 반환

3. 다른 프로세스가 critical section에 진입하고자 할 때 현재 자원을 사용 중인 프로세스가

자원을 반납하기 전까지 busy waiting을 해야 한다.

 

Block - Wakeup VS Busy - Wait

Critical Section의 길이가 길다면 Block-Wakeup이 유리하다.

반대로 길이가 짧다면 Block-Wakeup 방식은 잦은 문맥 교환으로 오버헤드가 증가한다.

이 경우에는 Busy-Wait이 유리하다.

 

세마포어는 뮤 텍스가 될 수 있지만 뮤 텍스는 세마포어가 될 수 없다.

뮤텍스는 동기화 대상이 1개일 때 사용하고 세마포어는 동기화 대상이 여러 개 일 때 사용한다.