[운영체제] 임계 구역 문제와 피터슨의 해결안(Critical Section Problem and Peterson's Solution)

참고도서: Operating System Concepts (10/E) Abraham Silberschatz, Peter B. Galvin, Greg Gagne

여러 프로세스가 동시에 작업을 수행할 때, 이 프로세스들 사이에 데이터의 공유가 있을 수 있다. 앞선 수업들에서 정리했던 것 처럼, 공유 메모리나 메세지를 전달하는 방식으로 말이다. 그런데 만약 데이터에 두 프로세스나 스레드가 동시에 접근해서 데이터를 수정하려고 하면 어떨까? 이런 상황을 Race Condition(경쟁 상황) 이라고 하는데, 경쟁 상황이 잘 제어되지 못하는 시스템은 심각한 문제를 초래할 것이다. 특히 최근의 컴퓨터 시스템은 기본적으로 SMP나 멀티 스레딩을 지원하므로 이런 동기화 이슈들을 잘 해결하는 것은 매우 중요한 일이다.

아래 코드를 살펴보자.

int consumer (){
    count++;
}

int producer (){
    count--;
}

이전에 살펴보았던 소비자-생산자 이슈를 다시 살펴봤을 때, 만약 두 프로세스나 스레드가 이 함수들을 병렬적으로 처리한다면, 연산의 결과는 상황에 따라 달라지게 된다. count 변수가 증가함과 동시에 감소할 수도 있고, 증가만 할 수도 있고, 감소만 할 수도 있기 때문이다.

Critical-Section Problem

Critical-Section은 임계 구역 이라고도 불리는데, 이 구역은 어떤 코드의 영역에서 다른 프로세스와 데이터를 공유하는 부분을 말한다. 프로세스가 처리하는 코드는 임계구역을 기준으로 다음과 같이 크게 세 구간으로 나누어진다.

• Entry Section(진입 구역): 임계 구역으로 진입하기 위해 진입 허가를 요청하는 구역
• Exit Section(퇴출 구역): 임계 구역이 끝난 직후 따라오는 코드 구역
• Remainder Section(나머지 구역): 진입 구역, 퇴출 구역, 임계 구역을 제외한 나머지 코드 부분

Criteria of Solution

결국 우리가 해결해야할 문제는 이 임계구역에 여러 프로세스들이 접근해서 데이터를 수정하려고 할 때, 어떻게 반응해야할 것인지에 대한 부분이다. 그리고 임계구역 문제를 해결하기 위해서는 다음과 같은 세 요구조건이 충족되어야 한다.

1. Mutual Exclusion(상호 배제): 어떤 프로세스가 자신의 임계 구역에서 작업을 수행하고 있다면 다른 프로세스들은 이 프로세스의 임계구역에 진입할 수 없다.
2. Progress(진행): 임계구역에서 작업 중인 프로세스가 없다면 임계구역으로 진입하려는 프로세스의 진입결정은 유한시간 내에 결정되어야 한다.
3. Bounded Waiting(한정된 대기): 어떤 프로세스가 자신의 임계 구역에 진입하려고 할 때, 다른 프로세스가 임계구역을 사용하고 있다면, 임계 구역을 사용 중인 프로세스는 해당 임계구역 진입 횟수에 한계가 있어야 한다.

쉽게 말하면 임계구역은 한번에 한 프로세스만 진입해야 하고, 진입의 결정을 다른 프로세스에 의해 할 수 있으며, 한 프로세스가 계속해서 임계구역을 점유하고 있을 수는 없다는 것이다.

Solution in Operating System

운영체제는 임계 구역 문제를 해결하기 위해서 두 종류의 접근을 커널을 설계하는 시점에서 계획한다.

1. Preemptive Kernel(선점형 커널): 프로세스가 커널 모드에서 실행 중일 때, 다른 프로세스에 의해 선점되는 것을 허용한다. 이때, 프로세스들 사이에 경쟁 조건이 발생할 수 있고, 커널모드에서의 경쟁조건이 정상적으로 해결되지 못한다면 시스템 전체에 안좋은 영향을 줄 수 있기 때문에, 경쟁 조건에 대한 대처가 정교하게 잘 설계되어 있어야한다.
2. Non-Preemptive Kernel(비선점형 커널): 프로세스가 커널 모드에서 실행 중일 때, 다른 프로세스는 CPU를 점유중인 프로세스가 종료되어 할당이 해제되거나, 인터럽트에 의해 봉쇄될 때까지 다른 프로세스에 의해 선점되는 것을 허용하지 않는다.

비선점형 커널은 어차피 한번에 한 프로세스의 접근만이 허용되기 때문에 경쟁 조건이 발생할 리스크가 없다. 그렇지만 대부분의 운영체제에서는 선점형 커널이 선호되는데, 선점형 커널은 한 프로세스가 지나치게 오랫동안 CPU를 점유하고 있는 것을 방지해 빠른 성능을 보이기 때문이다.

Perterson’s Solution (피터슨의 해결안)

피터슨의 해결안은 임계구역 문제를 해결하기 위한 하나의 알고리즘이고 다음과 같은 구조를 지닌다. 예를 들어 두개의 프로세스 i와 j가 있다고 하자

• 프로세스 i

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

    /* Critical Section  */

    flag[i] = false

    /* Remainder Section */
}

• 프로세스 j

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

    /* Critical Section  */

    flag[j] = false

    /* Remainder Section */
}

그리고 둘 사이에 Peterson 해결안을 위한 공유 데이터 turn 과 flag 가 있다고 하자.

• 공유 데이터

int turn; // 변수 진입 순번
int flag[2]; // 임계구역 진입 준비 상태, 각 인덱스가 프로세스를 의미

피터슨 해결안의 핵심은 양보에 있다. 각 프로세스는 임계구역에 다다르게 되면 자신이 아닌 다른 프로세스에게 임계 구역 진입 차례(turn)를 양보한다. 두 프로세스 i 와 j의 실행흐름을 따라가며 피터슨 해결안을 정리해보자.

1. 프로세스 i 는 자신이 임계구역에 들어갈 준비가 되면, 자신에 대한 flag 값을 true 로 만든다.
2. 그리고 동시에 turn 은 자신이 아닌 프로세스 j를 가르키게 한다. 프로세스 j의 준비상태가 true 라고 한다면 프로세스 i는 4번 라인의 while 문의 모든 조건이 true가 되므로 무한루프를 돌게된다.
3. 이때 프로세스 j가 임계구역에 들어갈 준비가 되면 자신의 flag 를 true로 만들고 turn은 프로세스 i를 가르키게 한다.
4. 프로세스 j가 turn 을 i로 바꾸었기 때문에 프로세스 i 는 무한루프에서 빠져나올 수 있다. turn == j가 false 가 되었기 때문이다.
5. 무한루프에서 빠져나온 프로세스 i는 임계구역에 진입해서 작업을 수행한다. 이때 flag[i] == true, turn == i 가 모두 참이기 때문에 프로세스 j는 무한루프를 돌며 대기한다.
6. 프로세스 i가 임계구역을 빠져나오면서 flag[i]를 false 로 만든다.
7. 프로세스 j는 이제 flag[i] 가 false 가 되었기 때문에 무한루프를 빠져나와 임계구역으로 진입한다.
8. 위 과정을 반복한다.

Solution Analysis

앞서 정의했던 것에 따르면 임계구역 문제에 대한 해결은 Mutual Exclusion, Progress, Bounded Waiting 의 요구조건을 충족해야 한다.

1. Mutual Exclusion(상호 배제) : 동시에 여러 프로세스가 임계구역에 진입하는 것을 허용하면 안된다. 이 조건은 while(flag[i] && turn == i) 에 의해 만족된다. 두 프로세스가 모두 준비상태에 있어 flag[i]와 flag[j]가 모두 true 를 가진다고 해도 turn 값은 언제나 i 혹은 j의 값을 하나만 가질 수 있다. 따라서 동시에 두 프로세스가 임계구역에 진입하는 것을 제한한다.
2. Progress(진행) : 임계구역이 비어있을 때, 임계구역의 진입여부가 한정된 시간안에 결정되어야 한다. 이 조건은 임계구역을 빠져나오면서 실행되는 flag[i] = false 와 while(flag[i] && turn == i) 에 의해 만족된다. 프로세스 i 는 임계구역을 빠져나온 직후에 flag[i]를 false 로 만드는데, 이 코드 덕분에 무한루프를 돌며 대기중이던 프로세스 j가 임계구역으로 진입하는 것이 가능해진다. 즉, 임계구역이 비게되자마자 곧바로 다른 준비된 프로세스의 임계구역 진입을 허락하는 것이다.
3. Bound Waiting(한정된 대기시간) :flag[i] = false 와 while(flag[i] && turn == i) 는 2번 조건을 만족시킴과 동시에 3번 조건도 만족시킨다. 이 코드를 통해서 두 프로세스는 무한정하게 임계구역 진입을 위해 기다리지 않고, 다른 한 프로세스가 임계구역을 빠져나오게 되면 곧바로 임계구역으로의 진입이 가능해진다.

Could It be a Ulimate Solution?

피터슨의 해결책은 임계구역 문제를 해결하는 요구조건을 설명하기에 가장 간단하면서도 적합한 해결책이다. 하지만 현대의 컴퓨팅 시스템에서는 피터슨 해결책이 임계구역 문제를 항상 해결해주지는 않는다.

그 이유는 시스템의 성능을 향상 시키기 위해서 프로세스나 컴파일러가 서로 종속성이 없는 명령어들의 순서를 바꿔서 실행하기 때문이다. 컴퓨터 구조에서 배웠겠지만, 이렇게 재정렬된 프로그램이 단일한 스레드로 이루어진 응용프로그램에 의해 실행되었다면 결과에 달라지는 부분이 없겠지만, 다중스레딩 환경에서는 데이터의 공유가 일어나기 때문에 결과가 달라지는 문제가 생길 수도 있다.