7-3강. 동기화 문제(Deadlock) 해결 방안

 Semaphore은 프로그래밍을 조금만 잘못해도 문제가 발생할 수 있다. 예를 들어 Semaphore 변수가 S와 Q로 두 개가 있다고 가정하자. 그리고 어떤 프로세스는 두 Semaphore를 모두 얻어야만 할 수 있는 작업이라고 하자. 예를 들면 A라는 Tape driver에 있는 내용을 B에 저장을 하는 것과 같은 작업이다. 그것들을 각각 P0와 P1이라고 하며 <그림 1>에 나타나 있다. 겉으로 보기엔 문제가 없어 보인다. 그러나 여기에는 심각한 문제가 발생할 수 있다.

 

그림 1 : Deadlock

 

 P0가 S를 얻고 CPU를 뺏겼다고 해보자. 그리고 CPU가 P1로 넘어가고 P1은 Q를 획득했다고 하자. P1이 이제 아랫부분을 실행하려고 해도 S를 P0가 가지고 있기 때문에 실행을 못하고, 반대로 P0가 Q를 얻으려고 해도 P1이 가지고 있기 때문에 실행이 불가능하다. 이렇게 둘 이상의 프로세스가 서로 가지고 있는 자원을 무한히 기다리는 상태를 Deadlock이라고 한다. 이 문제가 발생한 이유는 일이 다 끝난 다음에만 자원을 반납하기 때문이다. 이것도 다르게 이야기하면 Starvation problem이라고 볼 수도 있다. 이것을 해결하는 방법 중에는 <그림 2>처럼 P0과 P1 모두 같은 순서로 자원을 얻게 만드는 것이 있을 것이다. 

 

그림 2 : Deadlock 해결

 

---

동기화와 관련한 전통적인 문제들

 

 동기화와 관련하여 전통적인 세 가지 문제가 있다.

 

1. Bounded-Buffer Problem (i.e. Producer-Consumer Problem)

2. Readers and Writers Problem

3. Dining-Philosophers Problem

 

하나 하나 살펴보자.

---

1. Bounded-Buffer Problem (i.e. Producer-Consumer Problem) (크기가 유한한 공유 버퍼 문제)

 여기서 프로세스는 두 가지 종류가 있다. 하나는 Producer(생산자) 프로세스이고, 또 다른 하나는 Consumer(소비자) 프로세스이다. 이러한 프로세스들끼리 공유하는 버퍼가 존재하는데, 여기서 프로세스들이 하는 일이 무엇이냐? 생산자 프로세스는 데이터를 만들어서 버퍼에다 집어넣어주고, 소비자 프로세스는 여기엥서 데이터를 꺼내가는 역할을 한다. 

 

그림 3 : Bounded-Buffer Problem

 

 자 여기서 무슨 문제가 발생하느냐? 어떤 생산자 프로세스가 버퍼 중에 빈 곳에다가 데이터를 쓰려고 한다고 하자. 그러는 와중에 CPU를 뺏기고 CPU를 얻은 다른 생산자 프로세스도가 해당하는 빈 곳에다가 데이터를 쓴다고 해보자. 그러면 둘 중에 한 프로세스의 데이터는 유실이 될 수 있다는 것이다. 이 문제를 해결하기 위해서는 해당 공유 버퍼에 접근할 때는 Lock을 걸어서 비어있는 위치에다가 데이터를 집어넣고, 그다음 비어있는 위치를 다른 위치로 바꾸는 일을 해 놓은 다음에 Lock을 풀어야 할 것이다.

 

 소비자 프로세스도 마찬가지이다. 어떤 데이터를 하나 꺼내가려고 찜을 해놨는데 CPU를 빼앗겼다고 하자. 그러면 실제로 데이터는 하나인데 두 프로세스가 하나의 데이터를 가져가는 문제가 발생할 수 있다. 그걸 막기 위해 생산자 프로세스 때와 마찬가지로 공유 버퍼에 Lock을 걸고 꺼내가고 난 다음, 내용이 들어있는 버퍼의 위치를 다음 위치로 이동시킨 후 Lock을 풀어주어야 할 것이다.

 

 그렇다면 이것을 우리가 배운 것을 가지고 어떻게 구현하여 해결할 수 있을까? 우리는 지금까지 Semaphore에 대해 배웠다. 이걸 가지고 해결한다면 생산자 프로세스에게는 자원을 Empty buffer의 개수로, 소비자 프로세스에게는 자원을 Full buffer의 개수로 하고 연산을 정의해주면 될 것이다. 또한 이를 위해 Counting Semaphore(resource counting)와 Binary Semaphore(mutex) 중에서는 당연하게도 Counting Semaphore(resouce counting)를 사용해야 할 것이다. 공유 데이터는 무엇일까? buffer 자체 및 buffer 조작 변수(현재 empty 위치를 가리키고 있는 일종의 emtpy pointer와 데이터가 들어있는 위치를 가리키는 일종의 full pointer)이다. 이 데이터에 대해 Lock을 거는 행위에 대해서는 Binary Semaphore(mutex)를 사용하여 해결할 수 있을 것이다. <그림 4>를 보자.

 

그림 4 : Bounded-Buffer Problem Pseudo-Code

 

 생산자 프로세스는 데이터를 만들고 나서 먼저 empty 자원을 얻기 위해 P(empty)를 실행한다. 그리고 empty 자원을 얻게 되면 Lock을 걸기 위해 P(mutex)를 실행하여 소비자의 접근을 막는다. 이 작업들이 완료되면 비로소 버퍼에 데이터를 추가할 수 있다.

 

 반대로 소비자 프로세스는 데이터를 꺼내가기 위해 먼저 full 자원을 얻기 위해 P(full)을 실행한다. 그리고 데이터가 채워져 있는 full 자원이 있다면 Lock을 걸기 위해 P(mutex)를 실행한다. 이 작업들이 완료되어야만 버퍼에서 데이터를 꺼내갈 수 있다.

---

2. Readers - Writers Problem (읽기 쓰기 문제)

 이 문제에서도 공유 데이터가 존재한다. 공유 데이터에 대해 접근하는 프로세스도 두 종류가 있다. 하나는 읽는 프로세스이고, 다른 하나는 쓰는 프로세스이다. 특별히 공유 데이터를 읽고 쓰는 문제는 DB에서 많이 일어나기 때문에 공유 데이터를 DB라고 할 것이다. 그러니까 누군가가 DB를 읽거나 쓰는 도중에는 DB에 대한 접근을 막아야 하는 것이 이 문제의 핵심이다.

 

 쉽게 생각하자면 DB 접근 전에 Lock을 걸고, 끝나고 나면 Lock을 풀면 될 것 아닌가? 근데 조금 더 효율성을 높여보자. 

DB는 읽을 때는 여러 프로세스가 동시에 읽어도 별 문제가 안된다. 따라서 이 Readers-Writers Problem에서는 읽을 때는 동시에 DB에 접근할 수 있도록 해주고, Writer에 대해서는 무조건 배타적으로 혼자만 접근할 수 있도록 해야 할 것이다.

 

 우선 공유 데이터(Shared data)는 무엇일까? 

• DB 자체

• readcount

일 것이다.

 

이 DB에 대한 Lock을 거는 동기화 변수로 db라는 것을 둔다. 그런데 Lock을 걸었더라도 readcount가 양수이면 다른 Reader가 접근하더라도 접근을 허용해 주어야 겠다. 그리고 readcount가 0이면 Lock을 걸고 Read를 해야 할 것이다. 하지만 이 readcount라는 변수도 공유 데이터이며, 이 데이터를 변경시킬 때도 Lock을 걸어야 하기 때문에 mutex라는 동기화 변수, 즉, Binary Semaphore를 둔다. 

그림 5 : Readers-Writers Problem

---

그림 5 : Readers-Writers Problem Pseudo-Code

 Writer 입장에서는 DB에 접근하기 위해 db라는 mutex variable을 통해 Lock을 거는, 아주 간단한 작업으로도 해결이 가능하다.

근데 Reader는 DB를 읽기 위해 db에 대한 Lock을 걸지만, Reader들이 동시에 읽을 수 있도록 해주어야 하기 때문에 readcount라는 공유 변수를 건드려야 한다. readcount를 건드리기 전에 mutex를 통해 readcount Lock을 걸어주고 readcount연산을 하고 Lock을 풀어준다.

 

 그런데 readcount가 1이라는 것은 내가 지금 최초로 들어온 것이기 때문에 'Writer'의 접근을 막기 위해 db Lock을 세팅한다. 만약 readcount가 1보다 크다면 읽고 있는 다른 reader가 있다는 것을 말한다. 그러다가 DB를 다 읽고 나서 내가 마지막에 빠져나가는지 체크하는 것이 if (readcount == 0)이다. 마지막이면 db Lock을 풀어야 할 것이다. 그래야 기다리고 있는 Writer가 접근할 수 있기 때문이다.

 

 하지만 이 코드에서는 Starvation이 발생할 수 있다. 예를 들어 Writer가 DB에 접근하려고 할 때 100개의 Reader가 읽고 있다고 해보자. Writer는 기다려야 할 것이다. 마지막 Reader가 빠져 나가려고 할 때 즈음 갑자기 1000개의 Reader가 들어왔다고 해보자. Reader끼리는 서로 Lock을 걸지 않기 때문에 충분히 가능한 상황이다. 이런 이유로 Writer는 평생 DB에 접근조차 하지 못할 수 있다. 

 

 어떻게 하면 해결할 수 있을까? 이 문제는 마치 신호등이 없는 길을 건너는 문제와 같다. 차가 지나다니고 있는 길에서 나는 차가 모두 지나가고 틈이 생기기를 기다려야 하는데, 계속해서 차가 온다면 영원히 길을 건널 수 없는 처지가 될 수 있다. 마찬가지로 Reader들이 도착하는 족족 읽을 수 있게 하는 것이 아니라 일정 시간까지 도착한 Reader만 읽을 수 있게 하면 될 것이다.

 

---

3. Dining Philosphers Problem (식사하는 철학자 문제)

 문제 이름이 참 재밌지 않은가? 나는 재밌다.  

 

 이 문제는 5명의 철학자가 원탁에 앉아 밥을 먹는 상황과 비슷하다. 철학자가 하는 일은 생각하는 것이다. 그리고 철학자이기 전에 사람이기 때문에 밥을 먹을 것이다. 생각하다가 밥먹다가... 를 반복할 것이다. 그런데 철학자마다 배고파지는 주기가 다르다. 서로 동기화되어있지 못하고 모두 밥 먹는 시간이 다르다. 이때, 하필 젓가락이 '공유 데이터'라고 해보자. 젓가락이 두 짝이 되어야 밥을 먹을 수 있는데 각각 한 가락씩만 있다고 한다면 왼쪽에 있는 철학자가 밥을 먹고 있지 않아야 내가 밥을 먹을 수 있게 된다. 

 

 여기서 해결해야 하는 문제는 첫 번째, 모든 철학자가 동시에 밥을 먹는 것은 불가능하다. 젓가락이 '공유 자원'이기 때문이다. 두 번째로, 철학자들은 굶어 죽으면 안된다. 

 

그림 6 : 식사하는 철학자 문제

 

 철학자들은 우선 자기 앞에 놓인 젓가락(오른쪽)을 집고난집 고난 다음에, 바로 왼쪽에 놓인 젓가락이 있어야만 그 젓가락을 집고 밥을 먹을 수 있다. 그리고 밥을 다 먹기 전까지는 젓가락을 내려놓지 않는다. 어디서 많이 본 문제 아닌가? 그렇다 바로 Deadlock이다. 내 오른쪽 젓가락을 집 고난 다음에, 왼쪽 젓가락을 집으려고 왼쪽을 보았는데 젓가락이 없으면 계속 기다린다. 그런데 내 왼쪽 철학자도 본인 오른쪽 젓가락을 집고 왼쪽 젓가락을 '기다리고'있다면 젓가락을 내려놓지 않을 것이다. Deadlock이 걸린 것이다. 아무런 진행이 불가능하다.

 

 이 문제를 어떻게 해결할까? 우선 앞에 있는 방법으로는 해결이 불가능하다. 

---

1.  먼저, 첫 번째로는 철학자가 생각은 내려가서 하게 하고, 밥을 먹을 때는 4명의 철학자만 밥을 먹을 수 있게 하면 해결될 것이다.
2.  두 번째로는 젓가락을 두 짝 모두 집을 수 있을 때만 젓가락을 잡게하는 것이다.
3.  세 번째로는 짝수 철학자는 왼쪽, 홀수 철학자는 오른쪽 젓가락만 잡게 하면 될 것이다. 서론에서 살펴본 Deadlock의 해결 법과 같다. <그림 2>를 참조하자.

 우리가 살펴볼 방안은 두 번째이다.

 

---

 

 

 * Data & Variable Setting

편의상 다섯 명의 철학자가 갖는 상태에 대해 enum {thinking, hungry, eating} state [5]를 둔다. 

 그리고 Semaphore self[5]는 Binary Semaphore의 배열로 1이면 젓가락을 집을 수 있고, 0이면 집을 수 없는 상태를 나타낸다. 그러면 당연히 1로 시작해야 할 것 같은데 왜 0으로 시작했을까? 일단 양쪽 젓가락이 available 한 지 테스트를 하고 통과가 되면 그때서야 젓가락을 집을 수 있는 권한을 주기 때문에 0으로 초기화하였다. 

 Semaphore mutex는 옆 철학자의 state를 확인했는데 밥을 먹고 있지 않다고 해서 젓가락을 잡으려고 한다. 이때 CPU를 뺏기고 그 철학자가 상태를 바꾼다면 문제가 발생하기 때문에 Lock을 거는 용도로 사용한다.

 

 pickup()에서는 젓가락을 잡으러 왔으니까 hungry로 바꾸고, 젓가락을 잡을 수 있는지 test를 한다. 이때 test()에서는 왼쪽 철학자와 오른쪽 철학자 모두 밥을 먹고 있지 않을 때 그 철학자의 state를 eating으로 바꿔주면, V연산을 통해 self[i]를 V연산을 통해 젓가락을 잡을 수 있는 권한을 준다! 그러고 나서 젓가락을 잡을 수 있는 권한이 '1'로 세팅되어 있다면 권한을 P 연산을 통해 1을 빼앗고 젓가락을 잡게 한다! 만약 test를 통과하지 못했다면 여전히 self [i]는 0이기에 pickup을 하지 못하고 P(self [i])에서 잠들게 된다. 그리고 언제 잠에서 깨는가? 옆에 있는 철학자가 밥을 다 먹고 putdown()을 실행할 때, 혹시 나 때문에 옆에 있는 철학자가 밥을 먹지 못하고 있는지를 판단한다(test((i+4)%5);, test((i+1)%5);). 이때 깨워지게 된다. 

 

 

본 글들은 이화여대 반효경 교수님 2017학년도 1학기 운영체제 강의를 기반으로 작성됩니다.

링크 : http://www.kocw.net/home/search/kemView.do?kemId=1046323