[프로세스 동기화] Peterson's Solution

프로세스의 동기화 이슈는 프로그래밍을 하면서 만나는 중요한 이슈다.

운영체제가 사용하는 프로세스 번호를 관리하는 전역변수 next_available_pid가 있다.
프로그램 실행 도중 프로세스A와 프로세스B가 생성되었다.
두 프로세스는 우연히 비슷한 시기에 프로세스를 생성하였다.
우연히 두개의 프로세스가 동시에 next_available_pid에 접근해서 동일한 pid가 생겨버렸다.

위와같은 경우 운영체제는 동일한 두개의 pid의 프로세스를 관리하게 되는 상황에 빠진다.

일반적으로 프로세스를 생성 후 다음 생성될 프로세스를 위해서 next_available_pid를 하나 올려줄 것이다. 프로세스A와 프로세스B 모두 아래와 같은 과정을 거친다.

1. next_available_pid를 읽어온다
2. 프로세스에 pid를 부여한다
3. next_available_pid를 1 증가시킨다

프로세스 하나를 생성할때마다 위와같은 3단계의 과정을 거치지만 만약 프로세스A가 2를 실행하고나서 3을 실행하지 않고 타임쉐어링에 의해서 컨텍스트 스위치가 일어나서 프로세스B가 생성되는 과정으로 바뀌었다면 둘의 프로세스 번호는 같아진다.

여기서 next_available_pid 를 임계구역이라고 하고, 임계구역에 대한 접근을 프로세스간 경합 없이 처리해야한다.

이런 공유자원에 대한 프로세스간 경합상황은 프로그래밍을 하다보면 흔하게 만나는 문제이고, 이 문제를 해결해보자.

문제 정의

static int s_num = 0;

void* test1(void* p) 
{
    int i;
    for (i = 0; i < 10000; ++i) { // [1]
        ++s_num;
    }
    printf("test1 : %d\n", s_num);
    
    return NULL;
}

int main(void)
{
    pthread_t thread1; // [2]
    pthread_t thread2; // [3]
    pthread_t thread3; // [4]

    pthread_create(&thread1, NULL, test1, NULL);
    pthread_create(&thread2, NULL, test1, NULL);
    pthread_create(&thread3, NULL, test1, NULL);

    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);
    pthread_join(thread3, NULL);

    printf("result : %d\n", s_num);

    return 0;
}

단순히 공유되는 값 0을 1씩더하는 스레드를 3개 돌려서 30000까지 증가시키는 코드이다. thread1과 thread2는 s_num변수에 대해서 경합(race)하게 되고, 실행결과는 30000이 나와야 정상이지만 다음과같이 언제나 다른 값이 나온다

스레드 하나당 loop 횟수가 100회와 같이 충분히 작으면 값이 똑바로 나오겠지만 loop의 횟수가 늘어나면 스레드 하나당 실행시간이 늘어나기 때문에 (선점형 커널이라고 가정) 임계구역에 있는 값을 연산하는 도중에 컨텍스트 스위칭이 발생해서 연산의 원자성을 해친다.
물론 싱글코어 기준이지만 멀티코어라면 두개의 스레드가 각각 다른 코어에 의해서 실행될 수 있기 때문에 loop의 횟수가 충분히 작어도 이런 문제가 발생할 수 있다.

결국 이 코드의 작성자는 s_num의 값이 30000이 되기를 기대했겠지만 값은 실행할 때 마다 다르게 나온다.

Peterson's Solution

위의 문제점은 임계구역에 대한 각 스레드의 연산이 끝나기도 전에 컨텍스트 스위칭이 발생해서 나타났다.
그렇다면 하나의 스레드가 임계구역에 연산을 하고 있다면 다른 스레드는 임계구역에 접근하지 못하게 하면 될일이다.

예제

피터슨의 해결책에서 제시된 예시를 그대로 활용하지는 않았지만 코드를 통해서 확인해보자.

#define TRUE (1)
#define FALSE (0)

static int lock = FALSE;
static int s_num = 0;

void* test1(void* p) 
{
    int i;
    while (lock == TRUE); // [1]
    lock = TRUE; [2]
    for (i = 0; i < 100000; ++i) {
        ++s_num;
        
    }
    lock = FALSE; [3]
    
    return NULL;
}



int main(void)
{
    pthread_t thread1;
    pthread_t thread2;
    pthread_t thread3;
    
    pthread_create(&thread1, NULL, test1, NULL);
    pthread_create(&thread2, NULL, test1, NULL);
    pthread_create(&thread3, NULL, test1, NULL);

    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);
    pthread_join(thread3, NULL);

    printf("result : %d\n", s_num);

    return 0;
}

이제 lock변수를 통해서 실행중인 스레드만 임계구역에서 연산을 할수있도록 한다.

1. thread1은 임계구역에 대한 연산을 수행하고 thread2는 [1]에서 처럼 lock이 false가 될 때 까지 계속 반복문을 돌리고 있는 busy wait(spin lock)상태에 빠진다.
2. thread1의 임계구역에 대한 연산이 끝나면 lock이 false로 바뀐다. thread2가 [1]을 빠져나와서 다시 lock을 true로 바꾸고 임계영역 연산을 시작한다

이제 결과는 예상했던 값 30000이 나왔다.

이런 처리를 통해서 임계구역에 하나의 스레드만 접근해서 연산할 수 있도록 해서 문제를 해결한 것 같지만 문제가 있다. 반복 횟수를 1천만번으로 올리면 다시 의도하지 않은 경합상황이 발생한다.

이유는 [1]을 실행하는 연산이 c코드에서 보기에는 원자성이 보장되는 것 같지만 컴퓨터가 이해하는 영역으로 넘어가면 원자성이 보장이 안된다. 다음 어셈블리어를 확인해보자

LBB0_1:                                 
	cmpl	$1, _lock(%rip) // [A]
	jne	LBB0_3      		// [B]
## %bb.2:                               
	jmp	LBB0_1				// [C]
LBB0_3:						// [D]
	movl	$1, _lock(%rip)
	movl	$0, -12(%rbp)

[A]에 해당하는 부분이 [1]에서 lock이 true인지 비교하는 부분이다. 하지만 [1]에서는 한줄로 끝났지만 어셈블리어로 바꾸니깐 두번의 기계적 연산이 이루어진다. 만약 [A]를 실행하다가 스케줄러에 의해서 dispatch가 발생하면 원하는 하나씩 증가하는 연산이 이루어지지 않을것이다.

구조적 한계

프로세스 동기화 문제에서는 세가지 상황이 고려되어야 한다.

1. 상호배제(mutual exclusion) : 임계구역이 이미 스레드에 의해 점유중이라면 다른 스레드는 들어올 수 없다.
2. 진행(progress) : 데드락에 걸리면 안된다
3. 한정된 대기(bounded waiting) : 모든 스레드가 실행될 기회를 가져야 한다. 모든 스레드에 대해 기아(starvation)상태가 없어야 한다.

피터슨의 해결안은 적어도 두개의 스레드에 관해서는 위 3가지 상황이 해결된 이론적 모델이라고 할 수 있다. 하지만 하드웨어 구현상의 문제(어셈블리어로 확인했음) 때문에 임계영역에 대한 접근을 처리할때 경합상황이 발생한다.

다음에는 이런 문제의 해결을 위해서 기계자체에서 구현된 "원자성을 보장하는 임계구역에 대한 접근" 기능 중 하나인 뮤텍스(mutex)에 대해서 알아보자