Chapter 7. Classic Problems & POSIX API

# Liveness

: Synchronization에서 핵심적인 변수는 Semaphore이다.

=> Wait 함수 호출시, 두번째 오는 프로세스가 block되는데, 이를 잘못 사용하면 프로세스가 둘다 아예 실행되지

않는 문제점이 발생하여 Progress property를 위반하게 된다. : DEADLOCK이 발생하게 된다.

 

- Liveness는 Deadlock과 반대 개념으로, 어떤 경우에도 프로세스가 make progress할 수 있도록 보장한다.

: 만약 어떤 프로세스가 무한정으로 block된다면, Liveness와 반대되는 개념인 Deadlock상태가 된다.

 

 

+) Ji-Dum님 포스팅 참고.

http://www.jidum.com/jidums/view.do?jidumId=447

지식덤프

 

 

#Deadlock & Starvation

 

 

1. Deadlock이란, 두가지 또는 그 이상의 프로세스들이 계속 waiting 상태에 빠져서 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 어떤 프로세스도 실행하지 못하게 된다. 다른 프로세스에서 발생하는 이벤트를 기다림으로써 수행이 안되게 된다. S semaphore와 Q semaphore가 둘 다 0이 되면 앞으로 progress가 불가능하게 된다.

 

2. Starvation이란, indefinite blocking을 의미하는데, 한 프로세스가 semaphore값이 signal로  무한정 증가하면서 영원히 Semaphore queue에서 빠져나오지 못해서 특정 프로세스가 절대 수행이 되지 않음을 의미한다.

< 또는 우선순위가 높은 프로세스만 계속 실행되고, 우선순위 낮은 프로세스는 절대 시행이 되지 않을 때도 쓴다.>

 

 

 

 

 

---

# Classic Problems of Synchronization

 

https://blog.naver.com/PostView.nhn?blogId=and_lamyland&logNo=221192481544

[대딩의 운영체제, OS 14] 동기화 문제(Bounded Buffer, Readers Writers, Dining Philosophers Problem)와 모니터 Moni

 

 

 

 

=> Consumer- Producer problem을 동기화적인 측면에서 살펴보도록 하기 위해, 다음과 같은 Struct를 만들 수 있다.

 

 int n;

 

semaphore mutex=1;

 

semaphore empty=n;

 

semaphore full=0;

 

: Mutual exclusion을 보장하기 위해 만들어진 Binary semaphore인 Mutex는 보통 1로 초기화되고,

 

Counting sempahore는 full 변수 (Shared memory에서 버퍼가 차있는 개수)는 0으로 초기화되고, empty 변수는 (Buffer가 비어있는 개수) N(integer)로 초기화된다.

=> 이때, buffer가 꽉 차면, Spin lock을 걸게 된다.

 

 

 

 

 

=> 먼저, Producer 프로세스에서 item을 생성한다. 만들어진 아이템은 Critical section의 buffer로 진입하게 된다.

 따라서 Critical section에 진입하기 위해서 Wait(empty)와 Wait(mutex)를 호출하게 되는데,

따라서 버퍼에 새로운 아이템을 집어넣기 위해서 생성하였으니 emtpy값은 n-1이 되고, Mutual exclusion을 만족하기 위해서 Mutex를 1 감소시키고 Critical section으로 진입하게 된다.

: 따라서 Mutex 값은 0이기 때문에 Consumer process는 대기 상태에 빠지게 된다.

 

=> 그 후, 버퍼에 아이템을 채우는 행위가 끝나게 되면, 다시 Mutex의 signal 함수를 호출해 mutex값을 1로 만들어서 Consumer process도 c.s에 진입할 수 있도록 하고, Signal(full)을 호출해서 full의 초깃값인 0에 1을 더해준다.

: 따라서 Buffer에 아이템을 하나 채웠음을 알 수 있게 된다.

 

: 만약 계속 프로듀서가 아이템을 생성해서 버퍼에 채워가다가 n+1번 실행되면, Wait(empty)의 조건에 걸려서

 해당 Producer process는 블락된다. empty 변수가 -1이 되기 때문이다.

 

 

 

 

 

=> 이때 Producer가 생성한 Item을 Consumer가 소비하는 형태이기 때문에, 이때, 버퍼에 차있는 item이 소비되기 때문에 Full이 먼저 wait, 그 다음 빈 버퍼가 늘어나기 때문에 empty 변수가 Signal 함수의 변수로 들어가게 된다.

 

: 만약 buffer에 item이 하나도 안들어갔다면, 0으로 초기화된 full 변수가 -1이되면서 block에 걸리게 된다.

=> 따라서, consumer는 무조건 프로듀서가 먼저 실행된적이 있어야 하며, producer 프로세스의 실행 횟수가

consumer의 실행횟수보다 많아야 한다.

 

: 따라서 Mutex와 Counting semaphore를 통해서 Consumer-Producer 문제는 금방 해결이 가능하다.

 

 

---

#Dining- Philosphers problem

 

 

=> 철학자들 n명이 원탁에 둘러앉아 있다.

: 젓가락의 양쪽 짝이 각 철학자의 왼쪽 과 오른쪽에 놓여 있고, 두 젓가락을 다 집어야 식사를 할 수 있다,

식사를 하고 난 뒤에는 젓가락 두개를 다시 테이블에 놓고 생각에 빠지게 된다.

따라서 젓가락을 이미 옆의 철학자가 집었다면, 다른 철학자가 Chopstick을 내려놓을 때 까지 기다려야 한다.

 

 

: 이 문제를 해결하기 위해 Semaphore chopstick[5]를 도입할 수 있게 된다.

 

 

 

 

=> chopstick semaphore가 1이면 사용가능한 것이고,

=> 만약 0이라면 이미 자기 옆의 철학자가 해당 chopstick을 사용하여 식사중인 것이다

 따라서 Chopstick이 0이면 block되는 것은 불변의 성질이다.

 

만약 밥을 먹으려는 철학자 기준으로 왼쪽과 오른쪽의 젓가락을 집고, 두 젓가락을 모두 집게 되면 밥을 먹을수 있게 된다. 둘중 하나라도 젓가락을 집지 못하게 되면 wait 함수에 걸려서 block될 것이다.

 

=> 밥을 다 먹고난 후에는 signal 함수를 통해서 chopstick[i]와 chopstick[i+1 % 5] 를 둘다 release 해줌으로써 

옆의 철학자가 밥을 먹을수 있도록 해준다.

 

 

 

But, Philosopher's Dining problem에서의 문제는 Deadlock이다.

 

 

1) 먼저 wait(chopstick[i])를 통해서 왼쪽 chopstick이 0보다 큰 값을 가지는지 확인하고,

 

2 ) Wait(chopstick((i+1)%5) 함수를 통해서 오른쪽 chopstick이 available한지 확인 한다.

 

=> 이미 1 번 프로세스들로 각 철학자 5명이 모든 chopstick이 available한지 확인해서 모든 semaphore가 0인 상태.

=> 따라서, 2번째 line을 실행할 때 모든 semaphore가 이미 0이므로, 모든 철학자가 block된다.

 

 

# 그렇다면, 해결책은 무엇인가?

 

 

 

 

 

 

 

1. 다섯개의 semaphore가 존재하면, 최대 4명만 앉을수 있게 허용하면 최소 한명은 식사를 할 수 있게 된다.

 

 

 

2. 젓가락을 집는 instruction을 atomic하게 실행한다. 그럼 최소한 두명은 식사를 할 수 있게 된다.

 

---

#POSIX synchronization

 

 

 

=> 직접 동기화를 위해 POSIX에서 제공하는 mutex API에 대해 알아보자.

 

- Mutex를 쓰는 가장 궁극적 목적은?

 : Critical Section에서 mutual Exclusion을 제공하기 위함이다

 

- pthread_mutex_t mutex : mutex 변수를 선언해준다

- pthread_mutex_init : mutex 변수의 주소값을 넘겨주고, mutex 변수를 어떤 속성으로 생성할 것인지에 대한 속성변수

(Default 값은 주로 NULL로 선언한다.)

 

- lock 함수를 통해서 critical section에 들어갈 수 있는지 검사하고, C.S에서 빠져나왔다면 unlock을 통해 반납.

 

 

 

 

 

1. int pthread_mutex_init( pthread_mutex_t *mutex, pthread_mutexattr_t *attr)

: mutex를 초기화시켜주고, 속성 변수를 대입시킨다. (주로 디폴트값인 NULL로 지정)

 

2. int pthread_mutex_lock(pthread_mutex_t * mutex);

: Critical Section에서 lock할 때 호출한다. Mutex가 0과 같으면 block하고, mutex 값이 양수가 될때까지 기다린다.

 

3. int pthread_mutex_unlock (pthread_mutex_t *mutex)

: Critical section에서 벗어날 때 호출하며, mutex값을 0에서 1로 증가시킨다.

 

4. int pthread_mutex_destroy(pthread_mutex_t *mutex)

: mutex object를 destroy한다

 

 

 

 

#POSIX semaphore

 

 

sem_init 함수를 통해서 semaphore를 초기화시켜준다.

 

sem_wait에서는 0이라면 waiting 상태로 빠지고, 프로세스가 Critical Section에서 빠져나왔다면 sem_post 값을 통해

 semaphore값을 1로 증가시켜준다.