[OS] Synchronization II (Naive Approach, Peterson's Algorithm, HW Support, TAS, CAS)

Critical Section Problem

임계 영역에 대해서는 아래의 세 가지의 조건을 만족시켜야한다. 

1. Mutual Exclusion(상호 배제) : Critical Section에는 반드시 하나의 Thread/Process만 있어야 한다.
2. Progress(진행): 만약 Critical Section을 사용하는 Thread/Process가 없고, 현재 임계영역의 자원을 사용하려고 누군가 기다려야한다면 적절한 Algorithm을 통해서 해당 Thread/Process를 진행시켜야 한다. 
3. Bounded Waiting(한정 대기): Process/Thread가 임계 영역을 위해 무한정 기다려서는 안된다. 

Naive Approach (Wrong Case)

위 그림을 보자. 이는 우리가 가장 간단하게 생각해볼 수 있는 방법이다. isOccupied라는 flag변수를 두어서 사용중이라면 while을 돌고, 아니라면 CS에 들어가면 되는 간단한 방식이다. 그러나 이 방식은 분명 잘못되었다. 왜냐면 isOccupied라는 flag변수가 공유 자원(Shared Resource)이기 때문이다. Thread는 전역변수를 공유한다. 따라서 만약 왼쪽에서 if 조건문을 확인하자마자 Scheduling에 의해 오른쪽 Thread가 실행이 된다면 이는 CS에 이미 두 개의 Thread가 들어가게 되는 상태이다. 이는 명백한 Mutual Exclusion에 대한 위반이다. 

SW Approach I (Wrong Case)

이 전에는 Shared Resource인 Flag가 하나여서 문제가 생겼다면 이번에는 두 개를 만들어버리면 어떻게 될까? 그래서 Flag라는 Bool Type 배열을 만들어놓고 실행을 시켜보자. 그러나 이 방법 역시 문제가 있다. 만약 flag[0] = true;를 해버리고 Scheduler에 의해 오른쪽으로 넘어간다고 해보자. 그러면 flag[1] = true;까지는 되지만 while(flag[0])에서 걸려 무한루프가 걸려버릴 것이다. 만일 어떻게 Scheduler에 의해 다시 왼쪽으로 넘어간다고 하더라도 이번에 역시 while(flag[1])에 걸려서 여기도 무한루프를 돌 것이다. 양쪽에서 busy waiting이 되고 있는 것이다. 이는 Progress 위반이다. 어떠한 Thread들도 진행되고 있지 못하고 있는 상태이다. 

SW Approach II (Peterson's Algorithm) 

이번에는 Peterson Algorithm을 통해서 Working하는 사례를 살표보자. 이번에는 또 turn이라는 flag를 하나 더 추가하였다. 따라서 이를 통해 어디서 Scheduling이 일어나더라도 Correct하게 동작할 수 있다. 그러나 문제는 쓰레드가 과연 두개만 있을까? 컴퓨터 공학자의 목표는 이러한 결과를 어느 상황에서나 Correct하게 유지시켜주어야 한다. 쓰레드가 두 개일때 지금 코드를 읽어가면서 왔다갔다 하는 것도 복잡한데 더 많은 쓰레드들이 주어진 상황, 혹은 다중 처리기 환경에서 이러한 방식이 과연 Correct할지, 그리고 그 만큼 flag들을 추가를 해줘야 하는 것인지에 대한 의문점이 생긴다. 또한 Compiler에 의해 코드들이 Re-Ordering되어 할당의 순서가 바뀌어버리면 참사가 발생할 것이며 동기화 문제 자체를 SW적으로 접근하고 있기 때문에 매우 느리다. 

Interrupts Disabling

따라서 HW적인 지원이 필요한 단계까지 왔다. 초기에는 Scheduling도 결국 Interrupt 중 하나니까 Interrupt자체를 막아버리자는 Interrupt 금지 기법이 고안되었다. 잘 생각하보면 Race Condition의 원인은 Scheduling이고 Scheduling은 결국 Interrupt(Time Out, I/O Request)에 의해 발생하기에 Interrupt를 막아버리면 Race Condition이 일어나지 않을 것이라는 아이디어에서 나왔다. 물론 창의적이고 구현의 난이도도 쉽다. 그러나 이 방식은 장점보다 단점이 더 많은 방식이다. 이는 너무나 많은 Interrupt의 제한을 두어 Interrupt의 장점을 포기하게 되는 것이다. 결국 시스템의 전체적인 성능이 저하되는 것이다. 또한 Interrupt를 사용하지 않는다면 언제 인간의 Malicious한 코드들이 남용될 수 있고, 이 방식은 Multiprocessor에서 취약하다. 따라서 이 방식은 현대에 와서 단일 처리기에서 아주 짧은 구간 내에서 활용이 되기도 한다. 

HW Support: TAS & CAS

따라서 다른 방식의 HW적 접근이 필요했다. TAS는 Test and Set의 약어로 Test(load) and Set(store)을 Atomic하게 보장해주는 것이다. 따라서 아래의 코드와 같은 방식으로 구현이 될 수 있다. 

int TAS(int *old_ptr, int new) {
    int old = *old_ptr; //load
    *old_ptr = new;     //store
    return old;         //return
}

void lock(lock_t *l) {
    while(TAS(&l->flag, 1) == 1);
    //busy waiting
    ...
}

CAS는 Compare and Swap의 약어로 TAS와는 사뭇 다른 비교를 통해 메모리에 Store시켜줄지 아니면 대기할지 기다리는 방식이다. 이 역시 TAS와 비슷하면서도 다른 부분이 약간 존재한다. 구현은 아래와 같다. 예상이 되는 것과 실제 주소가 일치할 때에만 store가 일어난다. 

int CAS(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected) {
        *ptr = new;
        return actual;
}

void lock(lock_t *l) {
    while(CAS(&l->flag, 0, 1) == 1);
    //spin-wait
}