프로세스 동기화(Process Synchronization)(1)

프로세스는 병렬로 실행될 수 있으며 데이터를 공유할 수 있다. 만약 여러 개의 프로세스가 같은 자원을 동시에 접근한다면 어떻게 될까? 잘못된 결과가 발생할 것이다.

​예를 들어 counter라는 변수가 있고 현재 5라는 값이 들어있다고 하자. 만약 프로세스 A는 counter++ 연산을, 프로세스 B는 counter-- 연산을 병행하게 실행한다면 counter의 값은 4, 5, 6 중 한 값이 될 것이다.

​이와 같이 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(Race Condition)이라고 한다.

경쟁 상황으로부터 보호하기 위해서는 한순간에 하나의 프로세스만이 자료에 접근 및 조작이 가능하도록 보장해 줘야 한다. 이를 해결하는 것이 바로 프로세스 동기화이다.

​

프로세스 동기화에서 중요한 문제 중 하나는 임계구역(Critical Section) 문제이다. 임계구역이란 여러 개의 프로세스가 수행되는 시스템에서 각 프로세스들이 공유하는 데이터(변수, 테이블, 파일 등)를 작업하는 코드 영역이다.

프로세스의 일반적인 구조는 크게 4가지 부분으로 나뉜다. 첫 번째는 임계구역으로 진입하기 위해 진입 허가를 요청하는 부분을 구현하는 진입 구역(Entry Section)이다. 두 번째는 임계구역 영역이다. 세 번째는 임계구역 뒤에 있는 퇴출 구역(Exit Section)이다. 마지막으로 남은 코드 부분을 나머지 구역(Remainder Section)이라 한다.

do {
   entry section //중요
  
   critical section //임계영역

   exit section //중요

   remainder section
} while (true);

 

진입 구역과 퇴출 구역은 중요한 부분이다. 이 부분에 적절한 알고리즘을 활용하여 임계구역 문제를 해결하기 때문이다.

​

임계구역 문제는 지정되어야 할 코드 영역이 임계 구역으로 지정되지 않았을 때 발생할 수 있는 문제를 의미한다. 임계구역 문제에 대한 해결안은 다음의 세 가지 요구 조건을 충족해야 한다.

• 상호 배제(Mutual Exclusion) : 프로세스 P가 자기의 임계구역에서 실행 중이라면, 다른 프로세스들은 임계구역에 접근할 수 없다.
• 진행(Progress) : 한 임계구역에 진입할 수 있는 프로세스를 결정하는데 참여할 수 있는 프로세스들은 나머지 구역에서 실행 중이지 않은 프로세스여야 하고 결정하는 것은 유한 시간 내에 이루어져야 한다.
• ​한정된 대기(Bounded Waiting) : 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.

​

그렇다면 임계구역 문제를 해결하기 위한 해결책들을 알아보자.

첫 번째는 소프트웨어 기반으로 해결하는 피터슨의 해결안(Peterson's Solution)이다. 피터슨의 해결안은 임계구역과 나머지 구역을 번갈아 가며 실행하는 두 개의 프로세스로 한정된다. 또한 두 개의 변수를 공유하도록 하여 임계구역 문제를 해결한다.

int turn; //임계구역으로 진입할 순번
boolean flag[2]; //flag[i] == true -> i번 프로세스가 임계구역으로 진입할 준비 ok

 

위의 변수를 활용한 프로세스 i의 구조는 다음과 같다.

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);

    --critical section--

    flag[i] = false;

    --remainder section--
} while (true); 

 

코드를 간단하게 살펴보면 프로세스 i가 임계구역으로 진입할 준비가 되어있어도 while 문을 통해 프로세스 j가 아직 임계구역에서 작업 중이라면 진입을 못하도록 하였다. 후에 프로세스 j가 작업을 마치고 flag[j]를 false로 바꾸면 프로세스 i가 임계구역에 진입하도록 한다.

​이 알고리즘은 상호배제, 진행, 한정된 대기 조건을 모두 만족하기 때문에 임계구역 문제를 해결할 수 있다.

​

피터슨의 해결안은 임계구역 문제를 해결해주는 좋은 방법이지만 안타깝게도 현대의 컴퓨터 구조에서 올바르게 동작한다는 것을 보장해주지 않는다. 이를 위해 나온 것이 하드웨어에서부터 소프트웨어 기반으로 해결하는 방법인 동기화 하드웨어(Synchronization Hardware)이다.

​임계구역 문제는 단일 처리기 환경에서는 공유 변수가 변경되는 동안 인터럽트 발생을 허용하지 않음으로써 간단히 해결이 가능하다. 하지만 다중 처리기 환경에서는 적용할 수 없다. 다중 처리기 상에서 인터럽트의 사용불가능화는 메시지가 모든 처리기에 전달되게 하기 때문에 상당한 시간을 소비하여 시스템 효율을 떨어뜨리기 때문이다.

​많은 현대 기계들은 한 워드(word)의 내용을 검사하고 변경하거나, 두 워드의 내용을 원자적으로 교환(Swap)할 수 있는, 즉 인터럽트 되지 않은 하나의 단위로서, 특별한 하드웨어 명령어들을 제공한다. 이 명령어들을 사용하여 임계구역 문제를 상대적으로 간단한 방식으로 해결할 수 있다.

​

간단한 명령어를 통해 알아보자.

​먼저 test_and_set() 명령어이다. 이 명령어의 중요한 특징으로 원자적(Atomically)으로 실행된다는 점이다.

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

 

그리고 test_and_set() 명령어를 사용한 상호 배제 구조는 다음과 같다. lock이라는 공유 변수를 통해 상호 배제 문제를 해결하였다.

do {
   while (test_and_set(&lock))
   ; //do nothing

   //critical section
 
   lock = false;
 
   //remainder section
} while (true);

 

다음으로 compare_and_swap() 명령어이다. test_and_set() 명령어와는 대조적으로 세 개의 피연산자를 인자로 전달받는다.

void compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;

    if (*value == expected)
       *value = new_value;
    return temp;
}

 

그리고 compare_and_swap() 명령어를 사용한 상호 배제 구조는 다음과 같다. 마찬가지로 lock이라는 공유 변수를 통해 상호 배제 문제를 해결하였다.

do {
   while (compare_and_swap(&lock, 0, 1) != 0)
   ; //do nothing
  
   //critical section

   lock = 0;

   //remainder section
} while (true);

 

위 두 알고리즘은 lock이라는 공유 변수를 활용하여 임계구역의 사용 유무를 판단하여 프로세스 간의 상호 배제 문제를 해결하였다. 하지만 한정된 대기 조건을 만족시키지 못한다.

​

임계구역 문제의 요구 조건을 모두 만족시키는 test_and_set() 명령어를 이용한 또 다른 알고리즘은 다음과 같다. 한정된 대기 조건을 만족시키기 위해 공유 변수 두 가지를 추가적으로 사용한다.

boolean waiting[n];
boolean lock;

 

test_and_set() 명령어와 두 변수를 사용하여 임계구역 문제를 해결하는 구조는 다음과 같다.

do {
   waiting[i] = true;
   key = true;
   while (waiting[i] && key)
      key = test_and_set(&lock);
   waiting[i] = false;

   //critical section
 
   j = (i+1) % n;
   while ((j != i) && waiting[j])
      j = (j+1) % n;

   if (j == i)
     lock = false;
   else
     waiting[j] = false;

   //remainder section
} while (true);

 

코드를 살펴보면 한 프로세스가 임계구역을 떠났을 경우 임계구역에 들어가고자 하는 프로세스는 waiting 배열을 순환하다가 자신이 while 문의 조건을 성립할 때 임계구역에 진입한다. 최대 n-1 회만 양보하면 자신의 차례가 오기 때문에 한정된 대기 문제를 해결할 수 있다.

​

하지만 이 방법들은 복잡할뿐만 아니라 응용 프로그래머는 사용할 수가 없는 단점이 있다. 이를 위해 운영체제 설계자들은 임계구역 문제를 해결하기 위한 소프트웨어 도구들을 개발하였다. 임계구역 문제를 해결하기 위한 또 다른 방법들은 다음 글에서 알아보도록 하자.