[OS] Synchronization I (Intro with Codes, Race Condition, Critical Resource)

 

위 코드를 우분투 환경에서 돌려보자. 그러면 처음 실행한 환경에서는 아래와 같이 동작한다.

코드를 천천히 뜯어보면 알겠지만 우리가 저 코드에서 목표하는 바는 마지막에 Counter를 0으로 만든느 것이 목표이다. 그러나 코드의 결과는 우리가 예측했던 값과는 동떨어진 값이 나왔다. 우선 x++ 하는 것 부터 살펴보자. 사실 시스템 프로그래밍파트에서 정리를 했지만 변수에 1만 감소시켜주는 Assembly가 존재한다. 그러나 정확한 설명을 위해서 x++을 해주는 것은 먼저 메모리에서 x를 레지스터에 불러오고, 1을 더한 후 다시 메모리에 저장해주는 3가지 lw, add, sw 이렇게 세 가지 명령어가 필요하다고 해보자. 그렇다면 이 명령어 하나하나는 Scheduling의 대상이 되는 하나의 Thread이다. 따라서 x++과 x--가 동시에 있다고 했을 때 lw, add만 수행하다가 Scheduler가 thread_decrement함수를 불러서 lw, sub, sw를 수행하고 다시 thread_increment로 돌아가 sw를 하게 된다면 처음 -- 한거는 무시되고 x에는 1이 저장될 것이다. thread_decrement에서 호출된 x는 0이지만 -1을 저장하고 다시 thread_increment에서 x를 저장을 하게 된다면 x는 결국 1이 저장되기 때문이다. 결국 Scheduling이 함수의 호출 중간의 명령어 사이사이에서 발생했기 때문에 이러한 문제가 생기는 것이다. 그림으로 이 과정을 그려보면 아래와 같다. LW, ++, LW, --, SW, SW순으로 동작하면 X에는 결국 1이 저장될 것이다. 

Synchronization

이것이 바로 Thread, 혹은 Process Synchronization 문제이다. 쓰레드들을 기본적으로 Multi-Threaded 환경에서 협업을 한다. 협업을 한다는 의미는 공유 자원에 같이 Access할 수 있다는 것이다. 문제는 이 공유자원을 동시에, Concurrently하게 접근하게 된다면 위에서 본 것과 같은 Incorrect한 Result를 얻게 되거나 Race Condition이 발생하게 된다. 따라서 동기화의 목표는 Correct한 Operation을 보장해주는 것이다. 

Race Condition

그렇다면 계속해서 언급된 Race Condition은 무엇일까. 공유 자원에 접근하면서 그 결과가 Non-Deterministic할 때 Incorrect한 Result, 다시말해 Bug가 발생한다. 또한 이러한 경우 대부분 Non-Reproducible하다. 이는 결국 Execution의 timing의 영향을 받는다. Multi-Threading은 결국 Scheduling의 Non-Deterministic한 특성때문에 발생하는 것이며 인간이 이를 예측할 수 없기 때문에 Unpredictable하다. Multiprocessor에 와서도 이 문제는 여전히 발생한다. 어떤 쓰레드들이 언제 실행되는지, 누가먼저 실행되는지도 모르고, CPU의 처리율과 Workload를 우리가 예측하는 것은 불가능하다. 따라서 Atomic Operation을 보장하는 것은 쉬운 일이 아니다. 이는 결국 Programming Level과 Instruction Level의 괴리에서 찾아오는 문제이다. 이를 Pipelining, 혹은 Re-ordering 기법으로 해결할 있기도 하다. 

 

Race Condition의 예제를 들어보자. 위의 예시와 매우 비슷한데, Single Core환경에서 2개의 Thread가 있다고 가정해보자. 그리고 두 쓰레드 모두 0으로 초기화 되어있는 result라는 변수를 ++ 시킨다고 가정해보자. 우리가 일반적으로 Thread 두개를 동시에 돌린다면 result는 2일거라고 예상을 한다. 물론 2가 나올 수도 있다. 우리가 위에서 살펴본 것처럼 lw, add(sub), sw의 Instruction들을 수행한다면, 한쪽에서 lw되고 바로 다른쪽에서 lw, add, sw 해버리고, 다시 돌아와 add, sw를 수행한다면 result라는 변수는 2가 아니라 1이 될 것이다. 

 

다음 예제는 Multiprocessor에서도 당연히 발생할 수 있다. 4개의 CPU에서 모두 result라는 변수를 ++하고 싶은데, 모든 CPU가 0인 상태에서 lw, lw, lw, lw를 해버린다면 당연하게도 result에는 4가 아닌 1이 저장이 될 것이다. lw를 하게 되면 모두 result가 0인 상태를 불러와서 Operation을 수행하게 되버린다. 이 역시 우리가 예상하는 것이 아니라 Buggy하다. 

Critical Resource 

우리말로 번역하면 임계 자원이라고 한다. 오직 한 번에 하나의 Process에 의해서 사용될 수 있는 자원을 의미한다. 따라서 Critical Resource를 찾고, Critical Section을 찾아야 한다. Critical Section은 임계 영역으로서 Critical Resource에 접근할 수 있는 코드의 조각들이다. 생각을 해보면 Race Condition이 발생하는 이유는 부분별한 Critical Resource에 대한 사용이다. 그러나 만약 우리가 READ-ONLY Operation만 사용한다고 했을 때 Ciritical Resource를 사용하는 것은 Race Condition이 전혀 발생하지 않는다. 읽기만 하는 것은 전혀 문제가 되지 않지만 Critical Resource에 변화가 일어날 때, 즉 Write Operation이 발생할 때 문제가 발생하는 것이다. 

Mutual Exclusion

따라서 우리는 상호 배제를 시켜주어야 한다. 상호 배제는 오직 하나의 Thread/Process만이 Critical Section에서 실행하도록 진입을 막는 것을 의미한다. 따라서 동기화란 Race Condition 자체를 회피해버리거나, 실행의 Correctness를 보장해주기 위해 Critical Section을 상호배제 시키는 기법이라고 할 수 있겠다. 동기화에 기법에는 Mutual Exclusion, Condition Exclusion 두 가지가 있는데 이를 차례로 살펴볼 것이다.