운영 체제 (Operating System) - 동기화 (2)

저번 시간에는 어떻게 동기화를 어떻게 얻을 수 있는지에 대해서 알아보았다. 이번 시간에는 동기화에 어떤 문제들이 있고, 어떻게 해결했는지에 대해서 알아보자. 이번에 알아볼 동기화 고전 문제는 1)Bounded-buffer problem(Consumer produce problem), 2)Readers and writers problem, 3)Dining philosophers problem이다.

 

1. Bounded-buffer problem(Consumer produce problem)

말그대로 Bounded-buffer(유한 크기의 버퍼)에서 발생할 수 있는 동기화 문제이다. 그 Bounded buffer에 여러 생산자와 여러 소비자가 동시에 접근하게 되면서 생기는 동기화 문제를 다룬다. 문제 설명에 앞서 각 주체에 대해서 먼저 살펴보자. 

우선 생산자는 하나의 Item을 생산하여 Buffer에 저장하는 역할을 한다. 만약 Buffer에 저장할 공간이 없다면 대기한다고 가정하자. 데이터를 쓸 때 다른 생산자가 동시에 데이터를 쓰면서 Race condition이 발생할 수 있다. race condition이란 두 개 이상의 프로세스가 공유 데이터를 동시에 읽거나 쓰는 동작을 할 때, 실행 결과가 획일되지 않고 실행 순서에 따라 결과가 달라지는 상황을 말한다.  생산자는 Buffer에서 하나의 Item을 가져오는 역할을 한다. 이때 Buffer가 비어있다면 대기한다고 가정하자.

어떻게 하면 여러 생산자와 소비자 중 자신이 Critical section에 접근하여 효율적으로 생산 소비를 할 수 있겠는가에 대한 문제이다. 가장 쉽게 떠올릴 수 있는 방법은 생산자와 소비자의 모든 행동에 대해 하나의 semaphore를 두고 그 semaphore를 차지한 주체만이 액션을 취할 수 있도록 하는 방식일 것이다. 하지만 이전에 생산자와 소비자를 소개할 때 행동을 취할 수 없을 때 그 행동을 할 수 있을때 까지 대기한다고 가정하였다. 그렇기 때문에 생산자의 행동 가능 여부를 위한 하나의 semaphore(Full)와 소비자의 행동 가능 여부를 위한 또 다른 하나의 semaphore(Empty)를 설정하여 이를 구현할 수 있다. 그리고 맨 처음에 데이터 접근에 대해 설정하였던 semaphore는 Buffer에 대한 접근을 관리하는 semaphore(Mutex)로 설정하여 어떠한 종류의 프로세서이든 하나의 실행 흐름만이 Buffer에 접근할 수 있도록 한다. 이를 구현하면 다음과 같다.

눈여겨 볼만한 것은 생산자와 소비자가 액션을 취할 수 있는지를 먼저 판단하고, Buffer의 접근 가능 여부를 체크하는 것이다.

 

 

2. Readers-Writers Problem

이번엔 데이터를 읽기만 하는 Readers와 데이터를 쓰기만 하는 Writers에 대한 동기화 문제이다. 이번에는 알고리즘의 효율을 높이고자, Race condition을 유발하는 Write 행동을 포함하지 않는 행동들에 대해서 즉, 여러 프로세스가 데이터를 동시에 읽기만 하는 행동에 대해서 Critical section의 Concurrent한 실행을 주자는 것이다. 다만 이때 write연산이 시행된다면 모든 read와 write는 행해질 수 없을것이다. (Race condition때문에)

이제 이것을 어떻게 구현할지에 대해서 생각해보자. 우선 이전 Bounded-buffer problem과 다르게 하나의 Read를 위한 semaphore는 존재하지 않을 것이다. 대신 read중에 write이 되면 안되므로 read중에는 write semaphore를 미리 뺏어놔야 할 것이다. 그리고 아무 프로세스도 읽고 있지 않음이 확인된다면 그 write semahpore를 반환함으로써 write연산이 실행될 수 있게 한다. 여기서 가장 중요한 것은 read 연산 시 read process를 카운팅 하는 변수와 write semaphore의 값을 바꾸므로 다른 read프로세스에 의해 race condition이 발생할 수 있다는 것이다. 그리서 읽는 행동을 제외하고, readcount와 write semaphore을 조작하는 부분에 하나의 semaphore로 감싸줘야 한다.

write입장에서 보면 write critical section은 write semaphore로 감싸져 있을것이다. 그리고, write중일 때 read가 시행되서는 안되므로 이를 처리해주어야 한다. 하지만 이는 이전에 read 중 write방지를 위해 write semaphore를 뺏는것에 의해 처리될 것이다. 다음은 이에 대한 실제 구현이다.

하지만 이 알고리즘에도 문제가 존재한다. 바로 read가 지나치게 유리하다는 점이다. 만약 read중인 프로세스가 계속 하나라도 존재한다면 어떠한 write도 되지 못할것이다. 그렇기 때문에 writer의 starvation이 일어난다.

이를 극복하기 위해 write 신호가 오면 read를 멈추는 방식이 존재한다. 그 방식에 대해서 추가로 알아보자

 

2-1. Readers-Writers Problem without Writer Starvation

기존 Readers-Writers Problem solution

Readers-Writers Problem without Writer Starvation

Writers의 starvation에 대한 해결 방법은 하나의 Writer와 Read의 시작을 감싸는 세마포어를 추가하는 것이다. 이렇게 Write 시 Read의 초기 부분 (Count를 증가시키는 부분)을 막음으로써 Writer가 in semaphore를 획득하자마자 write를 할 순 없겠지만, 새로 실행되는 readers의 read_count의 증가를 막을 수 있을 것이고, 기존의 모든 reader들은 읽기를 정상적으로 종료할 것이다. 이렇게 됨으로써 writer는 write semaphore를 다시 획득할 수 있을 것이고, write 연산을 시행할 수 있을 것이다.

중요한 점은 reader의 count 증가 부분만을 감쌌다는 것이다. 이 모든 것을 감싸면 물론 starvation은 해결할 수 있겠지만, Bounded-buffer problem과 같은 비요율성을 보여줄 것이다. 이 알고리즘은 read count만을 감쌈으로서 어차피 mutex가 행했던 count에 대한 접근 제어의 로직을 바꾸지 않으면서 단순히 확장하고(한번 세마포어 비교 -> 두번 세마포어 비교), 다수의 process가 여전히 read를 할 수 있게 한다.

 

 

3. Dining-Philosophers Problem

위 그림을 살펴보자. 각 의자에는 철학자들이 앉아있고, 각 철학자들은 자신의 바로 양 옆에 놓인 젓가락 두 개를 모두 집으면 식사를 할 수 있다. 이를 코드로 살펴보자

3-1. Dining-Philosophers Problem : Wrong Solution

단순히 젓가락에 대한 semaphore를 만들고, 양 옆의 semaphore를 잡을 때 critical section에 들어가게 하는 방식으로 간단히 문제를 해결하고자 하였다. 하지만 만약 모든 철학자가 동시에 오른쪽 젓가락을 든다면 어떻게 될까? 어떠한 철학자도 왼쪽 젓가락을 집지 못하여 Deadlock상태에 빠지게 될 것이다. 이러한 Deadlock을 어떻게 방지할 수 있을까?

 

3-2. Dining-Philosophers Problem : Possible Solutions

-1. 한 번에 최대 4명의 철학자만 식탁에 앉게 한다.

-2. 양 옆의 젓가락의 상태를 미리 검사하여 양 쪽 모두 사용 가능할 때 젓가락을 집는다. 이때 젓가락의 상태를 검사하는 것 까지 critical section으로 생각해야 한다. 만약 체크 할 때 다른 철학자가 젓가락을 들고 있다면 그 당시에는 들 수 있는것오르 판단하겠지만, 실제로 들려고 할 때는 들 수 없게 되므로, Deadlock에 빠질 위험이 존재한다. 따라서 상태 체크까지 critical section으로 바라봐야한다.

-3. 철학자들에게 번호를 부여하여 짝수는 왼쪽을, 홀수는 오른쪽을 먼저 집게 한다.

 

하지만 이 solution은 starvation을 해결해주지 못한다. 한명의 철학자 양옆이 번갈아 가면서 식사를 한다면 그 중간에 낀 철학자는 starvation에 빠지게 되기 때문이다.  이 문제는 우선순위를 추가하여 해결할 수 있긴 하다. 이제 1,3번 솔루션은 확장이 어렵기 때문에 무시하고 2번 솔루션에 대해서 자세히 알아보자. 

 

3-3. Dining-Philosophers Problem : Best Solution 

양 옆의 젓가락의 상태를 미리 검사하여 양 쪽 모두 사용 가능할 때 젓가락을 집는 솔루션이다.

한 명의 철학자의 상태를 기록하고 이용함으로써 젓가락 문제를 양 옆의 철학자의 상태문제로 치환할 수 있다. 그 상태를 Thinking(Ready), Hungry(Waiting), Eating(Run)이라고 설정하자. 그리고, 철학자의 젓가락 잡기를 기다리는 세마포어인 Self[k]이 설정되어야 한다. 이것이 필요한 이유는 철학자의 상태가 Hungry여도 다른 젓가락을 사용할 수 없다면 Waiting되어야 하기 때문이다.

마지막으로 양 옆의 철학자의 상태를 체크할 때 그리고 철학자의 상태를 변경할 때 다른 프로세스가 함께 변경하면 안되므로 이를 위한 mutex를 설정한다. 이에 대한 구현을 먼저 보자

 

우선 큰 그림부터 디테일까지 파고가보자.

우선 take_chopstric이 실행되면 P(self[i])가 실행되어 self[i]를 소유하게 된다. 이 과정에서 두 개의 젓가락을 모두 사용할 수 있을 때 까지 기다린다. 사용이 가능하다면, P(self)에 의한 wait을 멈추고 돌아와서 Eat이 실행될 것이다.  그리고 put_chopstic이 실행되면 자신의 상태를 Thinking으로 바꾸고, 양 옆의 철학자가 두 개의 젓가락을 가질 수 있는지 체크한다.

가장 햇갈린 것이 self에 대한 것이다. self의 목적은 단순히 자신이 두 젓가락을 집을 수 있을 때 까지 기다리게 하기 위한 semaphore이다. 이 값의 초기값은 0이고, test에 의해서만 V가 일어나며(즉, release) take_chopstic에 의해서만 P(즉, wait)가 일어난다. 케이스를 나누어 생각해보자. 만약 take_chopstic을 호출하자마자 양 옆의 젓가락을 사용할 수 있다면 함수 내의 test로 self가 V되어 1이 될 것이고, 이후 실행될 P에서 0이 되며 바로 take_chopstic을 나갈것이다.  만약 take_chopstic을 호출할 때 양 옆의 젓가락을 사용할 수 없다고 가정해보자. 그렇다면 그 함수 내의 test에서는 V가 일어나지 않아 take_chopstic 끝 부분의 P(self)에서 waiting 상태가 될 것이다. 이때 얘를 wake up 해주는 것이 양 옆의 철학자이다. 결국 한명의 철학자가 waiting 상태라는 것은 두 개의 젓가락이 모두 완성되기를 기다리는 것이고 이는 양 옆의 철학자가 put_chopstic하기 기다리는 것과 같다. 따라서 put_chopstic에 양 옆의 철학자가 이제 젓가락을 들 수 있는지 없는지를 test해주는 것이다.

"철학자 i가 식사중인동안 LL 혹은 RR 철학자의 상태가 EATING으로 바뀐다 하더라도, test(LEFT)와 test(RIGHT)를 통해 signal을 수행하므로 동기화에 문제가 없다." 이 부분이 이해가 안간다.

 

 

4. Concurrency 유지, Race condition 방지, Process간의 협업을 위한 체크 요소

Data consistency가 확보되는가?

Deadlock이 발생하는가?

Starvation 가능성이 있는가?

Concurrency를 얼마나 제공하는가?