[Operating System] Process Synchronization 2

synchronization 문제의 여러 유형들이 존재한다.

• bounded-buffer problem
• readers and writers problem : scheduling
• dining-philosophers problem : deadlock

Bounded-buffer problem

Producer consumer problem

buffer를 shared memory로 사용하면서 발생하는 문제

 

기존 buffer memory를 shared memory로 사용하기 때문에 해당 부분을 동기화시켜줘야 한다.

하지만 이 외에도 producer는 buffer가 꽉 차있으면 더 이상 쓰면 안되고, consumer는 buffer가 비어있으면 더 이상 읽으면 안된다는 특징이 있다.

 

따라서 각 producer와 comsumer는 현재 buffer의 상태를 알 수 있는 변수가 필요

• producer : 현재 buffer가 얼마나 남았는지 : N_empty
• comsumer : 현재 buffer에 데이터가 얼마나 들어있는지 : N_full

• producer는 자신이 buffer에 데이터를 쓰기 전에 N_empty를 확인해 buffer가 비어있으면 N_empty값을 1 감소시킨 뒤, 데이터를 쓰고 N_fulll값을 1 증가시킨다.
• consumer는 자신이 buffer에 데이터를 읽기 전에 N_full값을 확인해 buffer에 값이 들어있으면 N_full값을 1 감소시킨 뒤, 데이터를 읽고 N_empty값을 1 증가시킨다.

solution

즉 N_empty, N_full값은 consumer, producer 모두에서 접근이 가능하기 때문에 해당 값도 synchronization을 해줘야 한다.

이러한 값의 증감과 해당 값의 동기화를 같이 할 수 있는 방법 : counting semaphores

⇒ int variable 자체를 semaphore count 변수로 사용

P,V를 호출하는 주체가 다르다!!

Readers-Writers Problem

DB에 여러 접근자(readers)가 존재하고 writer는 한 명만 존재하는 상황

• bounded-buffer problem과 다르게 memory size에 제약이 없기 때문에 위에서와 같이 N_full,N_empty 등을 관리할 필요가 없다.
• readers 끼리는 서로 동기화할 필요가 없지만 readers와 writer 간의 동기화는 필요하다.

위의 문제를 해결하기 위한 방법은 readers와 writer 간에 어떤 scheduling 방식을 사용할지에 따라 달라진다.

• writer가 접근하기 전까지의 reader만 접근을 허용할지
• writer는 모든 reader가 다 접근을 한 뒤 접근을 할지 ⇒ 선택!

solution

readers 사이에 공유 변수인 readcount를 설정한다.

그 후 가장 먼저 들어오는 reader가 P(S)를 호출, 가장 마지막에 나가는 reader가 V(S)를 호출하는 방식으로 사용

위의 readcount 역시 공유변수이기 때문에 reader들 사이에 동기화가 되어야 한다.

 

• readcount를 증가시키는 부분과 if(readcount) 부분은 같이 동기화되어야 한다.
  ⇒ 만약 readcount를 증감시키는 부분만 동기화가 된다면 if(readcount)를 실행하기 전에 다른 process가 또 들어와 readcount를 증가시키게 되면 문제가 발생하게 된다.
• readcount를 증가시키는 부분과 감소시키는 부분은 동일한 semaphore로 관리되어야 한다.

Dining-Philosophers Problem

circular wait이 발생하게 되는 문제

deadlock이란 여러 process가 서로가 필요한 자원을 상대방이 갖고 있어 무한정을 대기하게 되는 현상을 의미

⇒ starvation과의 차이점은 starvation은 다른 process는 작업을 하고 있는 반면, deadlock은 어떠한 process도 작업을 할 수 없는 상태이다.

solution

위의 문제를 해결할 수 있는 방법은 크게 3가지가 존재

1. 양쪽 젓가락을 동시에 잡도록 함
2. 짝수 philosopher는 자신의 왼쪽을 먼저 집도록, 홀수 philosopher는 자신의 오른쪽을 먼저 집도록 함
3. 좌석 수를 한 자리를 비워 둠

⇒ deadlock이 발생하는 중요한 조건은 circular wait(원형 대기)이므로 이를 안 하도록 하면 된다!

Problems of Semaphore

• semaphore의 단점은 solution을 범용적으로 적용하기 어렵기 각 문제마다 solution code를 구현해야 한다.
• 작성한 solution code가 올바르게 작동하는지를 확인하는 것 또한 어렵다.
• 여러 process 부분에서 같은 semaphore를 사용하는 경우가 많기 때문에 process flow를 조율해야 하는 경우가 많다.
• semaphore의 잘못된 사용이 전체 system에 큰 영향을 미칠 수 있다.

⇒ semaphore가 완벽한 solution은 아니다!

Monitors

monitors : High-level language에서 synchronization을 지원하기 위해 만들어진 construct

monitor construct에서는 하나의 process만 하나의 method에 접근해 실행하도록 보장한다.

⇒ 즉 monitor 내부 methods의 atomicity를 보장

 

추가적으로 특정 process가 methods를 실행 중 작업이 중단되면 busy waiting이 아니라 sleep을 할 수 있도록 하기 위해 condition variable을 지원

condition variable은 다음 두 가지 연산을 지원함으로써 sleep/wakeup을 구현

• x.wait() : 현재 실행 중인 process를 condition variable x에 sleep하도록 한다.
• x.signal() : 현재 x에 sleep 중인 process 중 하나를 깨운다. 이 때 x에 아무 process도 없으면 아무 일도 하지 않는다.

또한 x.wait(c)를 통해 process의 priority를 조절해줄 수 있다.

이러한 monitor를 이용해 위의 dining-philosophers problem을 해결할 수 있다.

여기에서는 위에서 논의한 3가지 해결 방법 중 젓가락을 동시에 들고 동시에 놓는 방식을 택했다.

⇒ 젓가락을 동시에 들고, 놓는 것을 philosopers의 상태로 관리

 

state

• thinking : 생각하고 있는 상태
• eating : 젓가락을 들고 있는 상태
• hungry : 젓가락을 들지 못 하여 기다리고 있는 상태

pickup()

1. 현재 상태를 hungry로 바꾼다.
2. 현재 밥을 먹을 수 있는지를 test()로 확인한다.
3. test()에서 내가 밥을 먹을 수 있는 상태가 안 돼 eating 상태로 넘어가지 못 했다면 condition variable에서 wait한다.

putdown()

1. 현재 상태를 thinking으로 바꾼다.
2. 내 양 옆의 philosoper가 밥을 먹을 수 있는지 test()로 확인한다.

test()

1. 내가 현재 hungry 상태이고 양 옆의 philosopers가 eating 상태가 아니라면 내 상태를 eating으로 바꾼다.
2. test()가 putdown에서 호출된 경우 현재 process는 sleep 상태이었을 것이므로 다시 깨워준다.

위의 코드의 경우 다음 두 가지 조건을 만족하면 항상 올바른 코드로 동작하게 된다.

1. pickup을 호출한 뒤 pickdown을 호출하는 순서를 지켜야 한다.
2. shared variable을 외부에서 직접 접근하는 것을 금지해야 한다.

참고

- Operating System Concepts

- 운영체제, 한양대학교 강수용 교수님