[OS] Process Synchronization

오늘로 운영체제 독학이 마무리되었다. 마무리된 김에, 이해하기 어려웠던 개념인 Process Synchronization에 대해 알아보려 한다.

 

프로세스 간 메시지를 전송하거나, 공유 메모리를 통해 특정 데이터를 공유하게 되는 경우 문제가 발생할 수 있다.

CPU를 할당받은 프로세스가 공유 메모리에 대한 작업을 수행하는 상황에, 중간에 다른 프로세스에서 해당 메모리 내 같은 데이터에 대한 작업이 수행되는 경우를 말한다. 이를 Race Condition이라고 한다.

 

Race Condition은 작업 도중 OS가 개입하는 경우 때문에 발생한다.

 

1. CPU의 kernel 수행 중 Interrupt 발생 시

2. 프로세스가 System Call을 요청하여 kernel 모드로 수행중인데 Context Switch 발생

3. Multiprocessor에서 shared memory 내 kernel data에 동시 접근 시

 

다음과 같은 경우에서 OS가 개입한다.

Race Condition이 발생했을 때, 해당 공유 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다.

 

이 문제는 Race Condition이 발생하지 않았다면 저장되어야 했을 데이터의 값이 일치하지 않아, 다음 Ready Queue에 있던 프로세스가 CPU에서 수행되었을 때 예상과 전혀 다른 값이 나오거나 오류를 발생할 수 있다.

 

그러면 이를 어떻게 해결해야 할까? 이 문제를 Critical Section Problem이라고도 하는데,

Pseudo Code로 해결책을 표현하면 다음과 같다.

# Critical Section Problem

do{
	entry section
    critical section
    exit section
    remainder section
} while(1);

위 코드를 해석하자면, 공유 데이터에 접근한 프로세스가 있다면 해당 부분을 critical section으로 규정하여 다른 프로세스들이 접근하지 못하게끔 하고, 작업이 다 끝난 후에 프로세스는 exit 표시를 하여 나머지 프로세스들도 접근이 가능하게 한다는 것이다. 이 해결법을 구현하는 알고리즘의 완성 조건은 3가지다.

 

1. 상호 배제 : 한 프로세스가 critical section 부분을 수행 중이면 다른 프로세스는 그들의 critical section에 들어가면 안된다. 

2. 진행 : 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스 존재 시 critical section에 들어가게 해주어야 한다.

3. 유한대기 : 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 들어가는 횟수에 한계가 있어야 한다.

 

이제 구현한 알고리즘에 대해 차례차례 알아보자.

 

Algorithm 1 - Synchronization variable

int turn;
initially turn = 0;
"P_i can enter its critical section" if (turn == 1)

do {
	while (turn != 0); /* My turn? */
    critical section
    turn = 1; /* Now is your turn */
    remainder section
   } while(1);

동기화 변수 turn을 선언하여, turn = 0 이면 자신의 차례에서 critical section에 접근하고, 작업이 끝나면 turn =  1로 바꾸어 다른 프로세스가 접근할 수 있도록 해주는 알고리즘이다. 이 코드는 앞서 본 완성조건에서 상호 배제 조건을 만족시킨다. 그러나 특정 프로세스가 다른 프로세스들에 비해 더 빈번히 critical section에 들어가야 한다면 문제가 발생한다.

위 알고리즘은 본인이 critical section에 진입하고 싶어도 다른 프로세스가 본인이 가진 값으로 바꾸어야만 critical section에 진입할 수 있는 과잉 양보의 문제가 있기 때문에, 진행 조건을 만족시키지 못한다.

 

Algorithm  2 - Boolean Flag

boolean flag[2];
initally flag[all] = false; /* No one is in CS */
"P_i ready to enter its critical section" if (flag[i] == true)

do {
	flag[i] = true;
    while (flag[i]);
    critical section
    flag[i] = false;
    remainder section
} while(1);

flag라는 불리언 변수를 선언하여 앞선 Algorithm 1과는 다르게 true /false 로 진입 여부를 판단하고, 또한 flag[i] = true로 critical section에 진입 의사를 표시하는 것이 특징이다. 작업을 끝마치면 flag[i] = false로 지정하여 다른 프로세스가 작업이 가능하게끔 바꾼다. 이 알고리즘은 상호 배제 조건을 만족하지만, 진행 조건을 만족시키지 못한다. 왜냐하면 flag[i] = true이나 아직 critical section에 들어가기전  timer interrupt나 system call 등의 영향으로 CPU를 빼앗기는 상황을 고려해보자. 이 경우 또한 과잉 양보의 문제를 발생시킨다.

 

Algorithm 3 - Peterson's Algorithm

// combined synchronization variables Algorithm 1 and 2
do {
	flag[i] = true; /* My intention is to enter ... */
    turn = j; /* Set to his turn */
    while (flag[j] && turn == j); /* wait only if ... */
    critical section
    flag[i] = false;
    remainder section
} while(1);

위 방법은 Algorithm 1과 2를 합친 방법이다. 먼저 critical section에 들어가겠다는 의사표현을 한 뒤에, turn을 상대방, 다음에 작업을 할 상대를 지정하고, 오직 flag[j] == true와 turn = j 일 때만 critical section에 진입할 수 있도록 하고 작업이 끝나면 다시 flag[i] = false로 지정하여 다른 프로세스가 작업이 가능하게끔 바꾼다. 이 알고리즘은 앞선 3개의 조건을 모두 만족시킨다. 그러나 CPU와 Memory를 계속 쓰면서 wait를 하는 방법이기에, 비효율적이라는 문제가 발생한다