Process Synchronization (2)

Monitors

• 이전 글에서 semaphore 를 이용한 synchronization 기법에 대해 살펴봤다.
• 이 기법은 wait(), signal() 이라는 다소 생소한 함수를 사용하고, 코딩이 복잡하다는 단점이 있다.
  semaphore 의 미숙한 사용은 deadlock 으로 이어질 수 있다.
• 이러한 이유로, semaphore 보다 직관적이고, 사용하기 쉬운 API 의 필요성이 부각된다.
  => 이러한 high level abstraction 을 Monitor 라고 한다.
• monitor 의 목적은 user 가 semaphore 사용 없이 mutual exclusion 을 보장할 수 있게 하는 것이다.
  즉, 하나의 process 만이 monitor 내에서 active 하도록 만드는 것이다.
  
• 위 그림은 monitor 의 구조를 나타낸다. 기본적으로 class 의 형태를 띈다.
• monitor 구현 시 필요한 요소는 다음과 같다

1. condition variable 의 정의
   => mutual exclusion 보장을 위해, 실행중인 process 외에는 queue 에 대기하도록 만드는 변수
   => 위 그림의 shared data 에 해당된다.
2. condition variable 에 행해지는 wait(), signal() 두 함수
   => wait() : 호출한 프로세스를 condition variable 의 queue 에 삽입
   => signal() : queue 의 프로세스 중 하나를 dequeue 하고 실행

• 이 두 요소들이 일반적인 class 와 monitor 사이의 차이점이라 할 수 있다.
• monitor 의 구현 방법은 wait() 과 signal() 을 이용해 두 개의 함수를 만드는 것이다. user 는 wait() 과 signal() 대신 새로 구현된 함수를 사용하므로, 더 직관적인 프로그래밍을 할 수 있다.

//monitor
monitor ResourceAllocator{ // class 형태의 monitor
	boolean busy;
    condition x; // condition variable
    
    void acquire (int time) { // wait() 을 이용한 함수
    	if (busy)
        	x.wait(time); // 함수가 condition variable 에 행해진다.
        busy = TRUE; // 다른 process 의 critical session 접근 금지
    }
    
    void release() { // signal() 을 이용한 함수
    	busy = FALSE; // critical session 접근 끝남
        x.signal();
    }
    
    initialization_code() { // class 생성자 역할
    	busy = FALSE;
    }
}

• 위에서 알 수 있듯이, monitor 의 내부 구현에는 condition variable, wait() 과 signal() 이 사용된다.
• busy 변수의 값을 바꾸면서 mutual exclusion 을 보장한다.
• user 는 acquire() 와 release() 만 사용할 뿐, 구현 내용은 몰라도 되므로 직관적이다.

//Application code
ResourceAllocator R; // monitor 인스턴스
R.acquire(t);
// access critical session
R.release();

Liveness

• 프로세스의 liveness 는 프로세스의 코드가 정상적으로 수행 중이라는 뜻이다.
• 반대되는 개념은 Deadlock 이다.
  
• 1로 초기화 된 두 mutex S 와 Q 가 있고, wait(S) 수행 이후 context switch 가 일어났다고 하자.
• S 와 Q 가 모두 0으로 설정되기 때문에, 양쪽 모두 두 번째 wait() 을 벗어날 수 없다.
• 이와 같이 코드 상으로 해결될 수 없는 indefinite blocking 상태를 deadlock 이라고 한다.

Classic Problems of Synchronization

Bounded Buffer Problem

• shared memory 에서 등장했던 producer - consumer problem 과 같은 문제다.
• 해결해야 할 문제는 세 가지다.

1. buffer 가 비어 있으면 consumer 의 동작을 멈춘다.
2. buffer 가 꽉 차있으면 producer 의 동작을 멈춘다.
3. 공유 자원인 buffer 에 대한 mutual exclusion 을 보장한다.

• 이를 위해 세 개의 semaphore 변수를 선언한다.

1. mutual exclusion 보장을 위한 mutex
2. 채워진 slot 갯수 파악을 위한 counting semaphore (full)
3. 빈 slot 갯수 파악을 위한 counting semaphore (empty)
   => full = N 이면 buffer 가 꽉 찬 것, empty = N 이면 buffer 가 빈 것이다.

• 이 변수들을 이용한 구현 내용을 살펴보자

//Producer
while (true) {
	// produce an item
    wait(empty); // empty = 0 이면 buffer 가 꽉 찼으므로 새 item 을 추가하지 않는다.
    wait(mutex); // mutex = 0 이면 buffer 가 access 되는 중이므로 기다린다.
    // add the item to buffer
    signal(mutex); // mutex 를 다시 1로 만든다
    signal(full); // item 을 하나 추가했으므로 full++
}

//Consumer
while (true) {
	wait(full); // full = 0 이면 buffer 가 비었으므로 item 을 소비할 수 없다.
    wait(mutex); 
    // remove an item from buffer
    signal(mutex);
    signal(empty); // item 을 하나 소비했으므로 empty++
}

• producer - consumer problem 의 다른 해결법인 spin lock 보다 직관적이다.

Dining Philoshopher's Problem

• 다섯 명의 철학자가 공용 밥그릇을 두고 밥을 먹는 상황을 가정하자.
• 이 때, 좌우의 젓가락이 모두 사용중이지 않을 때, 두 쌍의 젓사락을 사용해 밥을 먹을 수 있다는 문제다.
• 이 문제에서는 다섯 개의 mutex 를 사용해 다섯 쌍의 젓가락을 표현한다.

while(true){
	wait(chopstick[i]); // 왼쪽 젓가락을 표현, 0이면 젓가락 사용 중이므로 대기
    wait(chopstick[(i + 1) % 5]; // 오른쪽 젓가락을 표현
    //eat
    signal(chopstick[i]);
    signal(chopstick[(i + 1) % 5]);
    //think
}

• 이 방법은 deadlock 을 일으킬 수 있다.
• 다섯 명 모두 첫 wait() 까지 실행 후 context switch 가 되면, 모든 젓가락의 mutex 값이 0으로 설정되어, 두 번째 wait() 이 모두 실행되지 않는다.
• 해결책은 다음과 같다.

1. 두 젓가락이 모두 available 할 때 젓가락을 집을 수 있다.
2. 홀수 번 째, 짝수 번 째 사람의 동작을 나눈다. (asymmertic solution)

POSIX synchronization

• LINUX 에서 사용하는 POSIX compatible 한 synchronization 방법이다.
• mutex 변수와 lock(), unlock() 함수를 이용한다.

#include <pthread.h>
pthread_mutex_t mutex; // declare mutex object
pthread_mutex_init(&mutex, NULL); // define mutex attribute

pthread_mutex_lock(&mutex);
// critical session
pthread_mutex_unlock(&mutex);

pthread_mutex_destroy(pthread_mutex_t* mutex); // destroy mutex object

• semaphore 를 이용하는 방법은 다음과 같다

#include <semaphore.h>
sem_t sem; // delcare semaphore object
sem_init(&sem, 0, 1) // semaphore 초기화
// 첫 인자 = 주소값
// 두 번째 인자 = 0 : process 간 semaphore 공유 금지 option
// 세 번째 인자 = 1 : 초기값

sem_wait(&sem);
//critical session
sem_post(&sem);