[OS] Synchronization IV (Condition Synchronization with Scenarios)

Condition Synchronization

지금까지의 Mutex는 임계영역에 들어갈 때 하나의 Thread 혹은 하나의 Process만 사용할 수 있도록 보장해준다고 배웠다. Mutex를 Guarantee하지 않으면 결국 Non-Deterministic한 동작으로 인해 잘못된 결과가 초래될 수 있다. 그렇다고 해서 Mutex가 동기화를 보장해주는 유일한 방법은 아니다. 조건 동기화(Conditional Synchronization)은 특정 조건(condition, or state)이 만족할 때까지 대기하게 해서 다수의 쓰레드의 흐름을 Re-Ordering하는 것이다. 다시 말해서 조건에 따라 실행 흐름을 대기시키고 재개시킬 수 있다는 것이다. 

 

우리는 앞에서 Mutex는 P와 V Operation이 서로 쌍을 이루어야 한다고 배웠다. Mutex는 단순히 자신의 코드를 걸어잠구고, 풀어준다. 그러나 Conditional Synchronization은 자기 자신이 unlock해주는 것이 아니라 다른 쪽에서 V Operation을 수행해준다. 실행 흐름의 순서화를 하면 아래의 그림과 같다. 

Conditional Variable

일반적으로 thread가 Condition을 충족할 때까지 기다려야하는데, 가장 쉬운 구현 방법으로는 while문이 떠오를 것이다. 그러나 앞서서 다뤄보았지만 while문 같은 Spin Lock 작동 방식은 그다지 효율적이지는 않다. 따라서 정확한 Event에 의해 깨어나는 것이 더욱 효율적이라고 할 수 있겠다. 앞에서 예시로 들었던 semaphore나 pthread를 활용한 코드에서는 pthread_join이라는 API가 있었다. 이것은 인자로 받은 쓰레드가 종료될 때까지 기다리는 것이다. 이 API에는 "종료가 될 때"라는 조건이 달려있다. 이 조건을 만족시켜도록 깨워주는 API는 각각의 increment, decrement Function의 마지막에 있는 pthread_exit 이다. 이것이 V Operation, 즉 Signal처럼 동작을 하게 하는 것이다. 이런게 바로 조건 동기화이다. while문을 통해 기다리는 busy-waiting 방법은 직관적이지만 너무나 비효율적이기 때문에 우리는 Conditional Variable(이하 CV)을 사용해서 조건을 만족시키도록 할 것이다. 

 

CV는 특정 Event가 발생할 때까지 그 쓰레드를 Block시키는 것이다. Programmer의 입장에서 본다면 하나의 Waiting Queue이다. CV를 사용할때는 기본적으로 Mutex를 들고가야 한다. CV역시 Shared Resource이다. 따라서 Mutex로 이 CV를 먼저 잡고 활용한 다음에 Unlock시켜야한다. 이러한 의존관계는 필연적이다. 일반적으로 pthread 계열 API를 사용할때는 wait, signal이라는 이름의 API를 사용한다. pthread_cond_wait(*CV, *m), pthread_cond_signal(*CV); 이렇게 사용한다. 이때의 CV는 waiting queue가 들어가고 m에는 Mutex Variable이 들어가게된다. 또한 앞선 그림에서 보았듯이 Signal은 자신의 thread가 하는 것이 아닌, 다른 thread가 해주는 것이다. 예전에는 broadcast()라는 API를 활용해서 모든 thread들을 깨워주는 API가 있다고 하지만 이 역시 Non-Deterministic하게 동작할 수 있기 때문에 잘 사용되지는 않는다고 한다. pthread_cond_wait()을 조금 더 살펴보자. pthread_join같은 경우 아래과 같이 구현을 할 수 있다. 그런데 조금 이상함을 느꼈으면 센스가 있는 사람일 것이다. 분명하게도 pthread_mutex_lock으로 Mutex m을 잡았는데, pthread_cond_wait에서 m을 argument로 사용하고 있다. 이게 어떻게 가능한 것인지는 pthread_cond_wait의 Atomic Operation에 있다. pthread_cond_wait은 처음에 스스로 lock을 풀고, 자러간 다음 lock을 다시 잡는 내부구현이 되어있다. 따라서 내부적으로 lock release -> sleep -> require lock 이 방식으로 내부구현이 되어있다. pthread_exit()같은 경우도 내부를 아래와 같이 구현할 수 있다. 

간단하게 다시 정리해보자면 상호배제 뿐만 아니라 어떤 state가 만족할 때까지 waiting/resume 시키는 방법으로 다수의 쓰레드간의 Order를 Guarantee해주는 방법을 Conditional Synchronization을 통해 구현할 수 있다. 

Scenario

본격적으로 들어가기 앞서서 어떻게 해서 Conditional Synchronization이 Working한지 알아보고, Broken Solution에 대해서 다뤄볼 것이다. 위에 있는 theard_join과 thread_exit을 그대로 사용할 것이다. 먼저 두 개의 Process, T1, T2가 있다고 가정해보자.

 첫 번째로 살펴볼 시나리오는 T1이 join하고 T2가 exit를 수행하는 경우이다. 초기에는 done == 0 인 상태이기 때문에 pthread_cond_wait은 lock을 풀고 sleep하러 간다. 그 다음 T2로 가서 mutex로 lock을 다시 잡는다. 이제 done = 1을 해고, Signal함수를 통해서 T1을 깨워준다. 이때 T1은 Ready State에 있다. 아직 T2에 있는 상태인데, T2에서 마지막으로 unlock을 해주게 되면 T1에서는 pthread_cond_wait이 다시 스스로를 lock한다. 그러고 나서 while문에서 done == 1이기 때문에 벗어나고 unlock을 해주면 된다. 이 상황을 머리속으로 그려봐도 충분히 Working한다는 것을 알 수 있다. 

 두 번째 시나리오는 T2에서 먼저 thread_exit하고 T1에서 join을 하는 Case이다. exit에서 먼저 lock을 잡고 done을 1로 만들어 버린다. Signal을 보내지만 받을 thread가 없으니 그대로 return된다. Signal을 수행했어도 아무런 일이 일어나지 않는 no-effect이다. 그 다음에 단순히 unlock을 해준다. 이제 T1이 선택을 받아서 스스로 Lock을 한다. while문에 진입했지만 조건이 맞지 않아 바로 나온다. 그 후 unlock만 해주면 정상종료가 된다. 

Bad Scenario

만약에 Mutex가 없다면 어떻게 될까? 아래의 코드처럼 나올 것이다. 또한 일부러 문제를 일으키기 위해 while문도 빼버렸다. 사실 while문을 사용하지 않고 if를 쓰면 되겠지?라는 생각을 할 수도 있는데, 이에 대해서는 뒤에서 자세하게 다뤄보고 지금은 잘못된 Case를 다루기 위해 일부러 이렇게 써보았다. 

문제는 if문에서 done == 0을 확인하고 바로 thread_exit으로 interleave될 수 있다는 것이다. 만약 이렇게 되서 done = 1이 되버리고 signal까지 이뤄지게 된다면 깨울 thread가 없기 때문에 아무 일도 일어나지 않는다. 하지만 다시 join의 wait으로 돌아왔을 때는 더 이상 signal을 받을 수 없는 상태가 되어버리고, 이는 아무런 process도 progress하지 못하는 교착상태, 즉 Deadlock이 발생해버린다. 

또 다른 Broken Case를 살펴보자. 이번에는 Condition Variable인 done이 사라졌고, 그에 따른 조건문 또한 없어졌다. 이렇게 되면 만약 join을 먼저 수행하고 exit를 하게되면 아무런 문제가 발생하지 않는다. 그러나 만약 exit를 먼저 해버라고 join을 하게 된다면 이 역시 교착상태가 발생할 수 있다. 

 

다음 포스팅에서는 생산자 소비자 문제를 다뤄보면서 Semaphore의 동기화까지 알아볼 것이다. 

 

Reference

William Stallings. (2018). Operating Systems: Internals and Design Principles (8th Edition): Pearson.