[Ch 6] Synchronization: Critical Section Problem, Mutex Lock, Semaphore

서로 다른 프로세스들은 address space를 공유하거나 shared data를 사용할 수 있다. 이 때 이들이 동시에 실행되면 data inconsistency가 발생할 수 있는데, 이 chapter에서는 data consistency가 유지될 수 있도록 cooperating process들의 순차적 실행을 보장하는 synchronization 방법들을 살펴보도록 한다.

 

6.1 Background

프로세스 간 변수를 공유하는 상황에서 발생할 수 있는 data inconsistency를 구체적으로 살펴보도록 한다. 예를 들어, 두 프로세스 1, 2에서 count라는 변수를 공유해서 사용한다. 변수에 값을 쓰는 것은 assembly instruction level에서는

    1) count 변수를 레지스터로 불러오기

    2) 레지스터에 대해 연산

    3) 레지스터 값을 다시 count 변수에 쓰기

와 같은 3단계로 이루어지는데, 이들이 한 단위로 수행되지 않고 scheduling 시 프로세스 간 interleaving되어 실행될 수 있다. 예를 들어 프로세스 1에서 변수 count의 값을 레지스터 값에만 업데이트를 하고 아직 메모리에 쓰지 않은 상황에서 프로세스 2가 이 변수에 대한 접근을 시도한다면 업데이트 되기 이전의 값을 읽게 되는 것이다.

 

이처럼 여러 프로세스에서 같은 데이터에 대한 접근과 조작을 시도할 때, 그 실행 결과가 접근의 순서에 의존적인 상황을 race condition이라고 한다. Race condition을 방지하기 위해서 공유되는 변수에 대해서 한 번에 하나의 프로세스만 조작이 가능하도록 보장하는 매커니즘이 필요한 것이다.

 

6.2 The Critical-Section Problem

Process synchronization은 critical-section problem에 대한 논의로부터 출발할 수 있다. 각 프로세스 내에는 critical section이 존재하는데, 이 코드 안에서 공유되는 데이터에 대한 접근과 업데이트가 일어난다. 그러면 하나의 프로세스가 critical section 코드를 수행하는 동안 다른 프로세스는 수행되면 안 된다. Critical section problem이란 이러한 동작을 보장하기 위한 프로토콜을 설계하는 것이다.

출처: 교재 Figure 6.1

위 그림에서처럼 우선 critical section이 수행되기 전에 entry section이 있어서 critical section에 진입이 가능한지에 대한 허가를 받는다. Critical section 코드를 수행한 뒤에는 exit section으로 종료된다.

 

Single core 시스템에서 간단한 해결 방법 중 하나는 공유 변수에 대한 수정을 하기 전에 인터럽트를 disable 시키는 것이다.

 

6.4 Hardware Support for Synchronization

여기서는 synchronization tool로 사용될 수 있는 HW level의 primitive에 대해서 알아본다.

6.4.2 Hardware Instructions

많은 computer system은 word 단위에 대해 test와 modify를 동시에 하는 것 또는 두 개의 word를 동시에 swap하는 명령어를 지원한다. 명령어로 지원된다는 것은 곧 interrupt가 불가능한 하나의 atomic operation이 된다는 것이다. test_and_set() 명령어의 abstraction 코드 및 이를 활용한 mutual-exclusion 구현은 다음과 같다.

bool test_and_set(bool *target){
    bool rv = *target;
    *target = true;
    return rv;
}

...
while (test_and_set(&lock)){
}
/*
	critical section here
*/
lock = false;
...

물론 test and set의 실제 구현은 HW이며, 여기서는 그 동작만을 추상화시켜 C 코드로 표현하였다. 처음에는 lock 변수가 0이므로 while 문에서 바로 탈출이 가능하다. 처음 lock 변수에 접근한 프로세스가 critical section 코드를 실행하고, 그 동안 다른 프로세스 입장에서는 lock 변수를 계속 읽어도 1이기 때문에 while 문을 계속 돌게 된다. Critical section이 종료되면서 lock 변수를 0으로 바꿔주면 다른 프로세스가 이후에 test_and_set()에 대해 0을 return 받을 수 있게 된다.

 

6.5 Mutex Locks

test_and_set()과 같은 HW 수준의 명령어를 직접 사용하는 것은 어렵기 때문에, OS level에서 mutex lock이라는 tool을 제공한다. 프로세스가 critical section에 진입하기 전에 acquire lock을 하게 되며, 마친 뒤에는 release lock을 한다. mutex lock은 available이라는 bool 변수를 포함하는데, acquire lock 시 available이 1이 되었을 때까지 기다렸다가 그 값을 0으로 바꾼다. release lock은 available을 1로 바꾼다. 여기서 역시 available에 대한 접근과 업데이트는 atomic하게 이루어져야 하며, 위 6.4에서 설명한 HW의 지원을 받아야 한다. 예를 들어 release_lock을 한 뒤에, 두 개의 프로세스가 동시에 acquire이 1인 것을 확인하여 while loop을 빠져나오면 안 된다.

 

이러한 방식의 단점은 busy waiting인데, critical section을 실행하고 있지 않은 다른 프로세스들은 계속 loop을 돌면서 실행을 하고 있다. Single core 시스템에서는 하나의 프로세스에서 mutex release를 하지 않은 상황에서 다른 프로세스 입장에서 한 번 acquire이 0인 것을 본다면 더 이상 반복문을 계속 도는 것은 CPU cycle을 낭비할 뿐이다.

 

그러나 이러한 방식의 장점으로는 context switch에 의한 overhead는 낮다는 것인데, 만약 critical section을 실행하지 않는 프로세스들을 wait queue에 넣는다면 이로 인한 context switch overhead가 커질 것이다. 따라서 이러한 'spinlock' 방식은 lock이 짧은 시간 걸려있는 경우에 적합하다. 그런 경우 loop에 의한 CPU cycle 낭비가 일부 있더라도 이를 wait queue에 넣는 것보다는 overhead가 작기 때문이다.

 

6.6 Semaphores

위의 mutex lock은 synchronization을 제공하는 가장 간단한 tool인데, 여기서는 보다 robust한 방식으로 동작하는 semaphore에 대해서 살펴본다. 우선, semaphore는 integer 변수인데, wait(), signal()의 두 가지 atomic operation을 통해서만 접근된다. 이들의 동작은 다음과 같다.

wait(S){
    while (S <= 0){
    }
    S--;
}

signal(S){
    S++;
}

wait(S)에서 S의 값을 test하는 것과 이를 modify하는 것은 중간에 interrupt 없이 atomic하게 이루어져야 한다.

 

6.6.1 Semaphore Usage

Semaphore 변수가 가질 수 있는 값의 범위에 따라 counting/binary로 구분할 수 있는데, binary의 경우 mutex lock과 유사하게 동작한다. Counting semaphore는 한정된 수의 자원에 대한 접근 권한을 control할 수 있다. 자원을 사용하고자 할 때 wait(S)을 수행하고, 자원을 다시 반환할 때는 signal(S) operation을 수행한다. 만약 semaphore가 0이 되면, 이 자원에 접근하고자 하는 프로세스는 count 값이 0보다 커질 때까지 기다리게 된다.

 

6.6.2 Semaphore Implementation

Mutex lock에서 critical section을 실행하지 않는 프로세스들이 busy waiting을 하는 것이 문제였는데, semaphore 구현에서는 이를 해결하기 위해 wait(S)에서 semaphore count가 0 이하의 값인 것을 확인했다면 프로세스가 스스로 실행을 중단하고 CPU scheduler로 control을 넘겨준다. 이 때 이 프로세스는 semaphore에 대한 waiting queue에 들어가서 waiting state로 대기하게 된다. 그리고 signal(S)에서 wakeup() operation을 통해 다시 ready queue로 이동시킨다.

wait(semaphore *S){
    S->value--;
    if (S < 0){
        (put process into wait queue)
        sleep();
    }
}

signal(semaphore *S){
    S->value++;
    if (S <= 0) {
        (move process P from wait queue to ready queue)
        wakeup(P);
    }
}

이 때는 semaphore 변수가 음수를 가질 수 있으며, 현재 대기 중인 프로세스의 수가 곧 semaphore 변수의 절댓값과 같다. 여기서도 wait(), signal() operation은 atomic하게 이루어져야 하며, 동시에 두 개의 프로세스에 의해 실행되지 않음을 보장해야 한다. 이것은 interrupt를 disable, reenable하는 방식을 통해 보장할 수 있다.

 

6.7 Monitors

Mutex와 semaphore는 synchronization을 위한 효과적인 방법이나, 프로그래머가 잘못 사용하는 경우 오류가 발생하기 쉽다. 이러한 오류를 방지하고자, synchronization tool을 하나의 high-level language construct로 만들었는데, 이것이 monitor의 개념이다.

 

Reference

A. Silberschatz, Operating System Concepts 10th ed, WILEY (2019) Ch 6