인강 ) 프로세스 동기화(2)

강의 url www.kocw.net/home/search/kemView.do?kemId=1046323

동기화에 대한 고전적인 문제에 대해 설명할 수 있다.

세마포어의 고전적인 문제에 들어가기 앞서

 앞 포스팅에게 설명되었지만, 세마포어는 동기화를 구현하기 위한 추상적인 개념을 지원하기 위해 사용된다. P(S), V(S) 라는 operation을 통해 세마포어 변수 S에 대해 획득 및 해제를 할 수 있다.  셰마포어는 P 또는 V 연산에 대해 atomic 하다고 가정한다. 세마포어 변수는 Counting Semaphore 또는 Binary Semaphore 형태를 띌 수 있다. 어떠한 형태이든, 세마포어는 P와 V 작업을 통해 Critical Section을 관리하는데에 목적이 있다.

 하지만 세마포어를 사용하면서, Deadlock 및 Starvation문제가 발생할 수 있다. 아래는 발생할 수 있는 예를 보여준다.

위 deadlock 예를 해결하기 위해선, semaphore에 대한 획득 순서를 동일하게 맞추면 해결할 수 있다. 추후 포스팅에서, dead lock에 대한 더 자세한 학습을 해볼 것이다.

Classical Problems of Synchronization

Bounded-Buffer Problem (producer-consumer problem)

공유 자원을 처리할 때, 공유 자원에 접근하는 프로세스를 생산자-소비자 역할로 나누어 사용할 때 생길 수 있는 문제이다. 생산자 프로세스는 Empty Buffer가 있다면 Empty buffer에 임의의 데이터를 넣는다. 임의의 생산자 Process가 Empty buffer A에 접근하여 data를 넣을 때 운영체제에 의해 CPU가 다른 Process에게 선점당하고, 다른 Process가 Empty buffer A를 확인하고 거기에 data를 넣는다하자. 그렇다면 다시 CPU가 원래 임의의 생산자 Process에게 돌아간다면 Empty buffer A(실제론 Empty이지 않은)에 data를 넣는 시점부터 수행하게되어 buffer A에 의도치 않은 값이 입력 될 것이다. 

해당 문제에서, consumer process 입장에서는, 각각의 프로세스가 buffer에 접근 당시 empty buffer가 아니므로 consume하도록 결정하였는데, 2개의 consumer process가 교차하여 같은 empty buffer를 consume하게되고- 부득이 CPU 스케쥴링에 의해, 어느 한 process는 empty buffer를 소비하게 된다.  해결방법은 buffer의 값을 참조할 때 lock을 이용하여 mutual exclusion을 만족하게끔 해야한다. 그리고 이 문제에서 눈여겨 볼 상황은 buffer라는 공유 자원이 유한Bounded 하다는 것이다. producer process 입장에서는 buffer가 모두 사용 중 일때 empty buffer가 생성될 때 까지 대기해야한다. 반면에 consumer process 입장에서는 bueffer가 적어도 하나는 사용중일 때 까지 대기해야한다. 해당 문제는 Counting semaphore를 활용하여 empty-nonempty buffer의 개수를 세고, binary semaphore를 활용하여 buffer에 대한 동시 접근을 막는 방법을 취하여 해결할 수 있다. Shared data는 buffer 자체 및 empty 및 used buffer의 시작 위치를 가르키는 pointer 따위의 buffer 조작 변수로 두 종류로 나뉠 수 있다. 이러한 Shared data는 lock 등을 이용하여 동시 작업을 방지 해야한다. 세마포어 변수로는 lock을 걸기위한 binary semaphore 및 empty-nonempty buffer의 개수를 세기위한 counting semaphore가 필요하다. 

아래는 코드를 활용하여 문제 해결방법을 표현하였다.

위 ppt서 semaphore 변수로는 full, empty, mutex가 주어진다. 생산자 프로세스는 공유 자원인 x에 대해 nonempty buffer를 넣는다. 그러기 위해 공유자원인 buffer에 대해 lock을 걸기위해 P(mutex)-V(mutex)를 수행한다. 그 사이에서, buffer에 아이템을 넣는 작업을 한다. 여기서 mutex 는 binary semaphore임을 확인하라. 이 작업이 다 끝났다면, 내용이 들어있는 buffer가 생겼으므로 V(full)을 통해 full buffer를 추가한다. 이 때 full은 full buffer를 의미한다. consumer process는 P(full)를 통해 full buffer 를 획득하고, lock을 통하여 buffer에 접근하여 item을 consume한다. 그리고 consume하였기 때문에 V(empty)를 통해 empty buffer를 추가한다. 그러므로, 생산자 프로세스는 P(empty)를 통해 empty buffer를 획득한다.

생산자-소비자 문제에서는 두 종의 세마포어를 이용하여 문제를 해결하는데, 1) Buffer 에 대한 접근을 제한하는 binary semaphore 그리고 2) 생산자 입장에서의 빈 자원 소비자 입장에서의 nonempty 자원을 처리하기위해 counting semaphore를 활용한다. 

Readers-Writers Problem

한 process가 DB write중 일 때, 다른 process가 접근하면 안된다. db 접근 전에 lock을 수행하면 완벽히 문제를 해결한다. 하지만 write를 하지 않는 read 작업끼리는 동시에 해도 된다는 특징을 가진다면, 효율성을 위해 read 전에는 lock을 걸지 않을 수 있다. 문제 정의를 위해 공유 자원 및 동기화 변수가 무엇일지 정해보자. 공유 자원은 DB 자체 및 reader의 수 이고, reader 수에 접근하기 위한 binary semaphore(증감을 위해) 및 db에 접근하기 위한 binary semaphore가 필요하다. 

아래는 코드를 활용하여 문제 해결방법을 표현하였다.

Writer는 P(db)를 통해 db 세마포어를 획득한다. Reader는 readcount를 늘리고 P(db)를 통해 db 세마포어를 획득한다. 이 때 readcount가 1이 아닌경우는, 다른 프로세스가 db 세마포어를 획득하였으므로, P(db)를 통해 db 세마포어를 획득하지 않는다. reading 작업은 mutual exclusion을 만족하지 않아도 되므로 따로 세마포어를 획득하지 않는다. 이 코드는 Starvation 유발의 위험이 있다. Reader는 1 카운트 이상에선 항상 db를 획득한 상태임을 인지하고 있어야한다. 도중에 db를 놓거나 하는 코드가 없기 때문이다. 만약 100개의 Reader와 1개의 Writer 작업이 있다고하자. 100 개중 1개의 Reader 작업이 먼저 수행되어, 1개의 Writer 작업이 P(db) 코드에서 block-wait 상태라고하자. 그런데 나머지 99개의 작업은 readcount 관련하여 binary semaphore만 만족하면 되어, P(db)코드를 거치지 않음을 확인하라. 그래서 99개의 작업이 먼저 수행되게 된다. 그런데 또 마지막 1개의 read 작업이 남았을 때, 또다시 1000개의 read 작업이 들어온 상태를 생각해보자. 그러면 또 1개의 Writer는 P(db)를 완료하지 못하고 block 하게 된다. 이게 계속 되면 starvation이 발생하는 것이다.

 이 상황이 자주 발생하는 문제는 아니겠지만, 소스코드상 문제가 있음은 확실하다. starvation 문제를 해결하는 예는 코드로 보여주긴 어렵다. 개념적으로 풀어서 설명하자면, 위의 starvation 발생 예는 마치 신호등이 없는 횡단보도를 건너는 상황과 같다. 신호등이 없을 때 자동차운전자는 앞의 차를 보며 계속 간다. 그러다가, 긴 차 행렬이 끝나고 빈 공간이 생긴 것 처럼 보여 보행자가 횡단보도를 건너려 하는 순간 - 새 자동차 행렬이 앞 선 자동차 행렬과의 빈 공간을 빠른 속도로 채워넣어, 보행자가 건널수 없게 되는 현상과 비슷하다. 만약 신호등이 있다면 보행자는 안전하게 지나갈 수 있을 것이다. 그러한 역할을 하는 코드를 넣어 starvation 문제를 해결할 수 있을 것이다.

Readers-Writers 문제는 Writer는 db에 배타적으로 접근하되, Readers 간은 db에 배타적으로 접근할 필요가 없다는 상황의 문제이다. Writer와 Reader간에는 db 접근에 대한 binary semaphore, Reader간은 reader process를 셀 수 있는 counting semaphore를 활용하여 문제를 해결할 수 있다.

Dining-Philosophers Problem

철학자가 식사를 할 때에 공유자원인 젓가락을 양 쪽에서 짚어야할 때의 문제이다. 젓가락에 대해 binary semaphore를 활용하여 표현할 수 있다. 마치 잘 동작하는 코드같으나 deadlock이 발생할 수 있다는 단점이 있다. 모든 철학자들이 동시에 eat 절차에 들어간다고 해보자. 모두가 왼쪽 젓가락을 먼저 집어올리는데, 어느 누구도 식사를 끝마치기 전까지 오른쪽 젓가락을 놓지 않으므로 deadlock 상황에 처한다.

여러 해결책이 있는데, 첫번째는 젓가락을 집어올릴 수 있는 상황에 대해서 4개의 counting semaphore를 활용하여 제한한다는 것이다. 두 번째는 젓가락 두 개를 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 해주는 것이다. 세번째로는 짝수 철학자는 왼쪽 젓가락부터 집도록 하는 것이다. 

아래 예는 철학자 식사 문제를 해결하는 코드이다. 아래는 두 번째 방식인 젓가락 두 개를 모두 집을 수 있을 때만으로 해결한 것이다.

먼저 semaphore 변수는 각자 철학자의 상태 변수인 binary semaphore와 젓가락을 모두 짚거나 모두 내려놓는 것에 대한 binary semaphore로 설정한다. pickup 부터 살펴보면, 자신 왼쪽, 자신 우측이 먼저 먹지 않는 상태라면, 본인의 상태를 eating으로 변경하고, 상태에 대한 binary semaphore를 해제한다. 만약 if문을 통과하지 못한 경우 젓가락을 집지 못하는 상태인데, V 작업을 하지 못한다. 우선 V작업을 하였을 때의 경우로 생각해보면, pickup에서 P를 수행하고, 젓가락을 집는 상태로 이동한다. 양 쪽 중 하나라도 젓가락을 쓰고있어 V 작업을 하지 못 한 경우, pickup 에서 P를 수행을 대기하게 된다. 언제 P를 수행할 수 있냐면 인접한 철학자가 put down을 수행할 때, 인접한 철학자에 의해 test가 수행됨을 확인하라. 

세마포어의 문제점

셰마포어를 구현하는 프로그램은 한 번의 실수가 모든 시스템에 치명적인 영향을 미칠 수가 있다. 프로그래머가 동기화 사용을 돕기위해 Monitor 라는 객체를 제공해준다. Monitor를 이용한 동기화 사용은 프로그래머가 V(), P()를 선언할 필요가 없고, Monitor 안의 변수는 오직 모니터 안에 정의된 메서드에서만 접근 가능하고, 그리고 프로세스가 하나만 접근가능하게 하는 Mutual exclusion도 제공해준다.

아래는 Monitor를 도식화 한 것이다. 공유 데이터를 Monitor 안에 정의하고, Mointor 안의 operation만이 variable에 접근할 수 있게 끔 한다. 그리고 프로세스가 공유 데이터에 접근하겠다고 하면, Monitor 안에 정의된 메서드를 호출하여 접근한다. Monitor는 여러 프로세스의 요청이 들어오고, 임의의 프로세스가 해당 메서드를 실행 중일 때, 요청이 들어온 프로세스들을 queue에 대기 시킨다. 이러한 동작을 Monitor 객체가 알아서 해준다.

Monitor에서는 조건 변수에 대해 wait 또는 signal 연산을 사용할 수 있다. 이때 조건 변수는 특정 값을 가지고 있는 변수가 아니며, wait 을 이용하여 해당 메서드의 코드를 수행하는 프로세스가 공유자원에 대한 동시접근을 방지하며 프로세스를 sleep 시키는 역할을 함.

produce 메서드를 수행하는 프로세스 입장에서는 빈 버퍼가 없다면, 빈 버퍼가 빌 때까지 프로세스가 wait하게 된다. 다른 consume 메서드를 수행하는 프로세스가 빈 버퍼를 만든경우 empty.signal을 수행하여 empty.wait에서 대기하고 있는 프로세스를 깨우는 역할을 하게된다. 셰마포어와의 차이점은, 셰마포어에서는 signal역할을 하는 것과 대응 하는 일은, 반드시 어떠한 정수형 변수의 값을 늘리는 역할을 하는 것에 반해, signal은 만약 wait 중인 프로세스가 없다면, 아무런 역할을 하지 않는다. 셰마포어와 모니터는 흐름은 유사한 측면이 있으나, 프로그래머가 체감하는 난이도는 차이가 있다. 셰마포어는 특정 작업을 하다 CPU를 다른 프로세스에게 선점당했을 때라던지의 검사를 하여 P,V 등의 코드 작성을 수행해야하지만, 모니터의 경우 작업 도중 CPU를 다른 프로세스에게 빼앗기는 문제에 대해 고려하지 않아도 된다는 장점이 있다. 모니터의 공유 변수가 다 사용중일 때 접근에 대해 wait, 그리고 signal의 연산만 선언적으로 해주면 된다. 

아래는 철학자 식탁문제를 Monitor로 구현한 것을 풀어쓴것이다.