Race Condition과 프로세스 동기화(Process Synchronization)

Race Condition이란?

Race condition이란 여러 프로세스들이 동시에 공유 데이터에 접근하는 상황을 말한다. 데이터 최종 연산 결과가 마지막에 어떤 프로세스가 데이터를 다루냐에 따라 달라지기 때문에 문제가 된다. 이를 막기 위해서 동시에 실행되는 프로세스들은 동기화되어야 한다.

 

 

 

OS에서 Race condition이 발생하는 경우

OS에서 race condition이 발생하는 경우는 크게 3가지가 있다.

 

 

1. 커널 수행 중 인터럽트가 발생한 경우

 

커널모드가 running하고 있을 때 interrupt가 발생하여 인터럽트 처리 루틴이 수행되면 둘다 커널 코드이므로 커널 주소 공간을 공유하게 되어 race condition이 발생한다.

 

 

2. 프로세스가 시스템콜을 하여 커널 모드로 수행 중인데 문맥 교환이 일어나는 경우

 

시스템콜을 하는 동안에는 커널 주소 공간의 data를 접근하게 되는데 이때 선점을 당하면 커널 주소 공간 메모리를 공유하게 되어 race condition이 발생한다. 커널 모드에서 수행 중일 때는 CPU를 선점당하지 않도록 하면 문제를 일부 해결할 수 있다.

 

 

3. 멀티프로세서에서 공유 메모리 내의 커널 데이터

 

여러 CPU가 메모리에 동시에 접근하여 각기 다른 일을 수행하는 경우 어떤 CPU가 마지막으로 데이터를 저장했는가에 따라 데이터값이 달라진다. 한 번에 하나의 CPU만 커널에 들어갈 수 있게 하거나 커널 내부에 있는 공유 데이터에 접근할 때마다 그 데이터에 대한 접근을 lock/unlock하는 방법을 써서 해결할 수 있다.

 

 

 

 

Race condition 해결책의 충족 조건

1. Mutual Exclusion

 

특정 프로세스가 *critical section 부분을 수행 중이면 다른 모든 프로세스들은 자기들의 critical section에 들어가면 안 된다.

 

*critical section

critical section이란 각 프로세스의 code 부분에서 다른 프로세스와 공유하는 데이터에 접근하는 코드를 의미한다.

 

 

2. Progress

 

아무도 critical section에 있지 않을 때 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어갈 수 있게 해주어야 한다.

 

 

3. Bounded Waiting

 

프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. 즉, 어떤 프로세스가 critical section에 들어가기 위해 대기하는 시간이 영원해서는 안 된다.

 

 

 

 

프로세스 동기화 구현 알고리즘

1. Peterson's Algorithm

//process i의 경우

do {
    flag [i] = true; /*critical section에 들어가겠다고 표시*/
    turn = j; /*들어가고자 하는 다른 프로세스가 있는지 확인하기 위해서 우선 턴을 넘김.*/
    while (flag[j] && turn == j); /*지금 critical section에 들어간 프로세스가 있다면 대기*/
    //critical section//
    flag[i] = false;
    //remainder section//
} while (1);

 

flag[i]로는 process i가 critical section에 들어가고 싶어한다는 것을 표시하는 데에 사용하고, turn 변수로는 critical section에 들어가고자 하는 다른 프로세스가 있는지 확인하는 것에 사용한다. 

 

이렇게 하지 않고 flag만 이용하거나 turn만 이용하는 코드는 세 가지 조건을 모두 만족시키지는 못한다.

 

우선 flag만 이용하는 경우에는 두 프로세스가 동시에 flag를 true로 설정했을 때에는 둘다 critical section에 진입을 못 하고 끊임없이 양보하는 상황이 발생하게 되어 progress와 bound waiting 기준을 충족하지 못하게 된다. 또한, turn만 이용하는 경우에는 두 프로세스가 반드시 한 번씩 교대로 들어가야 하게 되기 때문에 특정 프로세스가 더 빈번히 critical section에 들어가야 하는 경우나 한 프로세스의 remainder section의 코드가 긴 경우 다른 프로세스가 계속 기다리게 되어서 progress 조건을 충족하지 못한다. 

 

Peterson's Algorithm은 flag와 turn을 모두 쓰기에 세 가지 requirements를 모두 만족시킨다. 두 프로세스가 동시에 flag와 turn을 설정해도 turn 값이 둘 중에 하나로 덮어씌워지기 때문에 결국 둘 중 한 프로세스는 정상적으로 critical section에 진입하게 된다. 또한, 어떤 프로세스 A가 다른 프로세스에게 turn을 주었어도 그 프로세스가 flag를 true로 설정하지 않았다면 (critical section에 들어가 있지 않다면) A가 critical section에 들어갈 수 있게 된다.

 

다만 이 알고리즘은 while문 안에서 자신의 차례를 기다리기 때문에 계속 CPU와 memory를 쓰면서 wait하게 되는 busy waiting 문제가 있다.

 

 

 

2. Synchronization Hardware

 현재 critical section에 들어가 있는 프로세스가 있는지 확인하는 것을 test라고 하고 자신이 critical section에 들어가도록 하는 것을 변수를 통해 명시하는 것을 set이라고 하자. 보통 이 둘은 회로가 별개로 존재하기 때문에 두 명령어 간에 context switch가 벌어진다. 그래서 두 프로세스가 동시에 set을 하고 test를 하는 경우에는, 두 프로세스 모두 critical section에 진입하지 못하게 될 수 있다.

 

Synchronization Hardware란 test와 set을 하나의 회로로 만들어서 하나의 어셈블리 명령어처럼 작동하게, atomic하게 수행할 수 있도록 만들어 context switch가 발생하지 않도록 함으로써 두 프로세스가 모두 진입을 못하고 계속 기다리기만 하는 문제를 방지한 것이다. 이를 이용하는 코드는 다음과 같다. 앞에서 봤던 flag와 turn 값을 set하고 while문 안에서 조건을 test하는 코드를 Test_and_Set이 한 번에 시행한다고 보면 된다.

 

Synchronization variable:
    boolean lock = false;

Process Pi:
    do {
        while(Test_and_Set(lock));
        //critical section//
        lock=false;
        remainder section
    }

 

 

 

3. Semaphore

Semaphore란 소프트웨어적으로 atomic한 연산이 가능하게 운영체제에서 특별하게 만든 api이다. 즉, test와 set이 context switch없이 이뤄지도록 보장하는 api인 것이다. Semaphore S는 integer 변수로, 다음의 두 atomic 연산에 의해서만 접근 가능하다.

//enter
P(S):	while(S<=0) do no-op;
		S--;

//release
V(S):	S++;

 

Semaphore를 이용한 구현코드는 다음과 같다.

semaphore mutex;

Process Pi
do {
    P(mutex);
    //critical section//
    V(mutex);
    //remainder section//
} while(1);

 

그러나 이런 방식의 구현은 P 안에서 while문을 사용해 조건을 확인하기에 여전히 busy-wait하다는 문제가 있다. 그래서 보통은 Block & Wakeup 방식의 구현을 사용한다.

 

 

Block & Wakeup 구현

 

우선 semaphore를 다음과 같이 정의한다.

typedef struct
{
    int  value;
    struct process *L; /*process wait queue*/
} semaphore;

 

새로운 semaphore를 이용한 구현 코드는 다음과 같다.

P(S) : 	S.value--;
        if(S.value < 0)
        {
            add this process to S.L;
            block();
            //block : 커널은 block을 호출한 프로세스를 suspend 시킨다.
            //이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다.
        }

V(S):	S.value++;
        if(S.value <= 0) {
            remove a process P from S.L;
            wakeup(P);
            //wakeup(P) : block된 프로세스 P를 wakeup시킨다.
            //이 프로세스의 PCB를 ready queue로 옮긴다.
        }

 

그렇다면 semaphore를 사용할 때는 항상 Block/wakeup 방식을 쓰는 것이 더 좋을까? 꼭 그런 것만은 아니다.

 

critical section의 길이가 긴 경우에는 block/wakeup이 적당하지만 critical section의 길이가 매우 짧은 경우에는 context switch가 발생할 수 밖에 없는 block/wakeup 방식의 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있다. 물론 일반적으로는 block/wakeup 방식이 더 좋아서 대부분 이 방식을 택한다.

 

 

Semaphore의 종류

 

1. Counting semaphore : 도메인이 0 이상인 임의의 정수값으로 주로 resource 개수를 셀 때 사용한다.

 

2. Binary semaphore : 0,1의 값 위주로 작동하는 semaphore로 critical section에 하나의 프로세스만 들어갈 수 있게 하기 위해(mutual exclusion) 사용한다. mutex와 동일한 역할을 한다. 둘의 구체적인 차이점은 이곳에서 확인할 수 있다.