프로세스 동기화

임계구역 문제 ( The Critical-Section Problem )

여러 개의 프로세스가 공유하는 코드 영역, 변수 등의 메모리 공간을 일컬어 임계구역(Critical Section)이라고 한다. 멀티코어 환경에서는 두 개 이상의 프로세스가 임계구역에 동시에 접근할 가능성이 있고, 동시에 접근할 경우 동기화가 이루어지지 않아 예측할 수 없는 문제가 발생하게 된다. 이러한 문제를 해결하기 위해서는 각 프로세스 내에서 임계구역 접근에 관한 규약이 필요하다. 이 규약은 세 가지의 부분으로 나뉘게 되는데,

- Entry Section : 프로세스가 진입허가를 요청하는 부분

- Exit Section : 프로세스가 진입허가를 얻은 후 임계구역에서 코드를 실행하고 임계구역에서 빠져나오는 부분

- Remainder Section : Entry Section, Critical Section, Exit Section을 제외한 프로세스의 코드 나머지 부분

do {
    entry section // 진입 허가 요청
    	critical section // 임계 구역
    exit section // 다른 프로세스에게 임계구역 처리가 끝났음을 알림
    
    remainder section // 나머지 부분
    
} while(TRUE)

또한 이러한 규약을 가지고 임계구역 문제를 해결하기 위해서는 다음의 세 가지 조건이 충족되어야 한다.

- Mutual Exclusion : 만약 하나의 프로세스 P가 임계구역에서 실행되고 있다면, 다른 프로세스는 해당 임계구역에서 실행될 수 없다.

- Progress : Remainder Section에서 실행중이지 않은 프로세스들만 임계구역 진입을 위한 경쟁을 할수 있고, 이 경쟁은 유한한 시간 안에 결론이 나야 한다.(경쟁중인 프로세스들 중 하나가 임계구역에 진입해야 한다.)

- Bounded Waiting : 임계구역의 실행에 있어 어느 프로세스에게든 Starvation을 야기시키면 안 된다.

Peterson's Solution

임계구역 문제를 해결하기 위해서 위의 세 가지 요건을 충족시키는 피터슨 알고리즘에 대해 알아보자.

피터슨 알고리즘은 다음 두 가지의 데이터를 사용한다.

int turn;
bool flag[2];

turn은 당장 임계구역으로 진입할 프로세스를 나타내며, flag는 각 프로세스가 임계구역으로 들어갈 준비가 되었는지의 여부를 나타낸다.

두 개의 프로세스 P0와 P1이 있다고 가정하고, 피터슨 알고리즘을 적용한 각 프로세스의 코드를 살펴보자.

/*
	code for process 0
*/
do {
    ... // remainder section
    
    flag[0] = true;
    turn = 1;
    
    while(flag[1] && turn==1) // entry section
    	;
    ... // critical section
    flag[0] = false; // exit section
    
    ... // remainder section
} while(true);

/*
	code for process 1
*/
do {
    ... // remainder section
    
    flag[1] = true;
    turn = 0;
    
    while(flag[0] && turn==0) // entry section
    	;
    ... // critical section
    flag[1] = false; // exit section
    
    ... // remainder section
} while(true)

위 코드가 세 가지 조건을 어떻게 충족시키는지 알아보자.

- Mutual Exclusion : 만약 P0가 critical section에 진입하기 위해서는 !flag[1] || turn==0를 만족시켜야 하고, P1은 !flag[0] || turn==1를 만족시켜야 한다. 두 프로세스가 entry section에서 경쟁하고 있다면 flag[1]과 flag[0]모두 true이므로 turn값에 따라 경쟁의 승리자가 정해지는데, 이 때 turn값은 동시에 하나의 값만 가질 수 있으므로 상호 배제적인 수행이 보장된다.

- Progress and Bounded Waiting : 각 프로세스는 임계구역이 끝나고 remainder section에 진입하기 전에 자신의 flag를 false로 변경함으로써 자신은 remainder section 실행중에 critical section에 진입하기 위해 경쟁하지 않는것을 나타내고(Progress 보장), 동시에 Entry Section에서 대기중인 상대 프로세스에게 Critical Section의 진입을 허가한다.(Progress 및 Bounded Waiting 보장)

Synchronization Hardware

위의 피터슨 알고리즘처럼 소프트웨어적인 해결방안 이외에 여러 시스템에서 지원하는 하드웨어적인 명령어가 존재한다. 이러한 하드웨어 명령어는 하나의 워드(word)를 참조하고 변경하는 등의 동작이나 두 워드를 서로 swap하는 동작을 독립적으로, 원자적으로(atomic하게) 수행할 수 있다. 두 가지의 하드웨어 명령어를 살펴보겠다.

- test_and_set()

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

test_and_set은 매개변수로 전달받은 target값을 그대로 반환하고 해당 워드의 값을 true로 변경한다. 이는 임계구역 문제에서 다음과 같이 사용될 수 있다.

do {
    while(test_and_set(&lock))
    	; // entry section
    ... // critical section
    lock = false; // exit section
    ... // remainder section
} while(TRUE);

만약 두 프로세스가 test_and_set()을 호출한다면 이 명령어는 하드웨어 명령어 이므로 원자적으로 실행되며 두 개의 test_and_set()은 순차적으로 실행될 것이다. lock은 false로 초기화되어 있다. 이 명령어를 첫번째로 호출한 프로세스는 test_and_set()의 실행결과로 false를 반환받을 것이기 때문에 임계구역에 진입할 것이다. 하지만 명령어를 두 번째로 호출한 프로세스는 test_and_set()의 실행결과로 true를 반환받을 것이기 때문에 임계구역에 진입하지 못하고 지속적으로 test_and_set()을 호출하며 첫 번째 프로세스가 lock을 false로 풀어줄 때까지 기다리게 될것이다.

- compare_and_swap()

int compare_and_swap(int *value, int expected, int new_value) {
    int ret = *value;
    if(*value == expected)
    	*value = new_value;
    return ret;
}

compare_and_swap()명령어는 test_and_set()과 달리 첫 번째 매개변수로 전달받은 변수의 값이 두 번째 매개변수로 전달된 값과 같을 때에만 첫 번째 매개변수로 전달받은 변수를 세 번째 매개변수로 전달받은 값으로 변경하고 원래의 값을 반환한다. 임계구역 문제에 관해서는 다음과 같이 사용될 수 있다.

do {
    while(compare_and_swap(&lock, 0, 1) != 0)
        ; // entry section
    ... // critical section
    lock = 0; // exit section
    ... // remainder section
} while(TRUE);

test_and_set()과 같은 방식으로 사용하면 된다.

위 두 가지 알고리즘은 임계구역을 해결하기 위한 세 가지 조건중 Mutual Exclusion은 만족시키지만 Progress와 Bounded Waiting 조건은 만족시키지 못한다. 각 프로세스가 임계구역 진입준비를 알리는 flag가 존재하지 않기 때문이다. 이는 각 프로세스가 임계구역에 들어갈 준비가 되었음을 표시하는 waiting[] 형태의 flag를 사용하면 해결할 수 있다.

Mutex Lock

위의 하드웨어적인 동기화 명령어는 사용하기 복잡하며 응용프로그래머가 사용할 수 없다. 따라서 운영체제 설계자들이 응용 프로그래머가 사용할 수 있도록 소프트웨서 수준의 동기화 기법을 개발해 놓았는데, 그 중 하나가 Mutex Lock이다. 응용프로그래머는 임계구역 진입요청시 acquire(), 임계구역에서 빠져나올 시 release()를 호출하기만 하면 된다. 구현이 어떻게 이루어져 있는지 살펴보자.

void acquire() {
    while(!available)
        ;
    available = false;
}

void release() {
    available = true;
}

간단하다. 다만 운영체제 설계자들은 위의 두 가지 도구를 원자적으로 수행되게 설계하여야 할 것이다. 단점이라고 할 만한 것은 acquire()를 사용하여 임계구역 진입 요청 시 반복적으로 acquire()를 호출하여야 하는 busy waiting상태에 있게 된다는 것이다. 이는 다른 프로세스에게 의미있는 일을 하도록 할 수 있는 자원을 기다리는 데에 낭비하는 것일 수도 있지만, 한편으로 대기 시간이 짧은 경우 Context Switching에 필요한 비용을 지불하지 않는 것일 수도 있다.

Semaphore

세마포어도 Mutex Lock과 동일한 동작을 하지만, 자원이 하나가 아니라 여러개인 경우에도 적용할 수 있다는 장점이 있다.

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

void signal(S) {
    S++;
}

wait()은 acquire()에 해당되고 signal()은 release()에 해당된다. 여기서 S는 같은 자원을 동시에 사용할 수 있는 프로세스의 개수로 초기화된다.

Busy Waiting 문제의 해결을 위한 구현방법

busy waiting문제를 해결하기 위한 방법은 운영체제의 스케쥴러를 사용하는 것이다. 즉, 임계구역에 진입하려고 기다리는 프로세스를 ready queue로부터 waiting queue로 이동함과 동시에 세마포어의 리스트에 달아놓고, 임계구역을 빠져나오는 프로세스는 어떤 하나의 프로세스를 waiting queue로부터 ready queue로 이동함과 동시에 세마포어의 리스트에서 뽑아내는 것이다. 이 방법을 사용한 wait()과 signal()의 구현을 살펴보기 전에 세마포어의 구조부터 살펴보자.

typedef struct {
    int value;
    struct process *list;
} semaphore;

위 세마포어 구조체에서 value는 임계구역에서 동시에 작업가능한 프로세스의 개수를 의미하고, list는 해당 세마포어의 획득을 위해 대기중인 프로세스들의 리스트이다.

void wait(semaphore *S) {
    S->value--;
    if(S->value < 0) {
        ... // 현재 프로세스를 S->list에 넣음
        block(); // 현재 프로세스를 wait queue에 넣음
    }
}

void signal(semaphore *S) {
    S->value++;
    if(S->value <= 0) {
        ... // S->list에서 하나의 프로세스 P를 꺼냄
        wakeup(P); // P를 ready queue에 넣음
    }
}

만약 임계구역에서 동시에 실행될 수 있는 프로세스의 개수인 S->value가 2로 초기화 되어있고, 세 개의 프로세스가 거의 동시에 wait()을 호출했다고 가정하자. wait()은 원자적으로 실행되므로 세 개의 wait()은 순차적으로 실행될 것이다. 첫 번째와 두 번째 프로세스에 의해 S->value는 2에서 0이 되고, 세 번째 프로세스에 의해 S->value는 0에서 -1이 되며 이 프로세스는 S->list와 스케쥴러에 의해 wait queue에 들어가게 될 것이다. 첫 번째 프로세스가 임계구역 동작을 끝내고 signal()을 호출하면 value는 -1에서 0이 되며 세 번째 프로세스가 S->list로부터 빠져나오며 ready queue로 들어가게 될 것이다.

Deadlocks and Starvation

Deadlock은 두 개 이상의 프로세스가 현재 기다리고 있는 상태의 프로세스에 의해서만 깨어날 수 있고 이 상태가 무한히 유지되는 교착상태를 의미한다. Starvation은 대기하는 프로세스를 후입선출(LIFO)방식의 리스트에 넣을 경우에 프로세스의 실행이 거의 일어나지 않는 상태를 의미한다.

Priority Inversion

Priority Inversion(우선순위 역전)이 필요한 경우는 Priority 기반 스케쥴링 방식인 경우이다. 우선순위가 각각 1, 2, 3인 세 개의 프로세스 P1, P2, P3가 있다고 가정하자(숫자가 낮을 수록 우선순위가 높다). P1과 P3이 같은 자원 R을 공유하고 P3이 현재 R을 점유하고 있을 때 P1은 P3보다 우선순위가 높지만 P3이 공유자원 R의 처리를 끝마칠때까지 기다려야 한다. 그런데 이 때 P2가 ready queue에 들어오게 된다면 P2가 P3보다 우선순위가 높기 때문에 선점(Preemption)이 일어난다. 이는 P1의 대기시간에 영향을 미칠수 있다는 문제를 야기시킨다.

이러한 문제를 해결하기 위해서 P3의 Priority를 임시적으로 1로 상승시키는 Priority Inversion 기법을 사용하는 것이다. 이렇게 하면 P3은 P2에 의해 선점당하지 않기 때문이다.

참조

ABRAHAM SILBERSCHATZ, PETER BAER GALVIN, GREG GAGNE / 운영체제 / (주)교보문고 / 2018년

devsophia