Study with me =)

병행 프로세스와 상호 배제
(1) 데커와 피터슨의 알고리즘
(2) 세마포어와 모니터

1. 경쟁조건 (race condition)

경쟁조건이란 2개 혹은 그 이상의 프로세스들이 전체가 공유하는 메모리에 읽기/쓰기를 할 때, 어떤 프로세스가 먼저 실행되는지에 따라 결과가 달라질 수 있는 상황이다. race condition이 있는 코드를 예측하는 것은 불가능에 가깝기 때문에 그 코드에서는 원하는 결과가 나오지 않을 가능성이 높다. 

A 프로세스와 B 프로세스가 있다고 생각해보자. 두 프로세스 모두 공유 메모리에 저장된 3을 읽어와서 1을 더하고 다시 저장해야 한다. 우리의 예측으로는 두 프로세스가 한 번씩 더하고 다시 저장하니 모든 프로세스가 실행된 후에는 5가 나와야 한다. 실제로는 이렇게 동작하여 5가 아닌 4가 결괏값이 될 수도 있다.

• A 프로세스가 3을 읽어갔다.
• A 프로세스가 3에 1을 더했다.
• A 프로세스가 4를 공유 메모리에 다시 저장하기 전에 B 프로세스가 3이라는 값을 읽어갔다.
• A 프로세스가 4를 공유 메모리에 저장했다.
• B 프로세스가 3에 1을 더했다.
• B 프로세스가 이미 4인 공유 메모리에 다시 4를 저장했다.

내가 원하는 대로 코드를 동작시키려면 최대한 경쟁조건을 피해야 한다. 즉 동시에 공유 메모리, 공유 파일, 기타 공유와 관련된 문제를 피할 수 있도록 조치해야 한다.

2. 상호 배제와 임계 영역 (mutual exclusion and critical section)

상호 배제(mutual exclusion)는 한 프로세스가 공유 자원을 사용하고 있을 때 다른 프로세스들이 사용하지 못하게 배제시키는 제어 기법을 말한다. 만약 위에서 A 프로세스의 모든 동작이 끝난 다음 B 프로세스가 공유 메모리에 접근할 수 있었으면 4를 만드는 오류는 발생하지 않았을 것이다. 운영체제의 전반적인 설계에 있어서 이러한 상호 배제를 구현하는 것은 매우 중요하다.

공유 메모리가 동시에 참조되지 않게 하기 위해 공유 메모리가 참조되는 부분을 임계 영역(critical section)이라 한다. 프로그램의 수행 조건을 잘 조절해서 2개 이상의 프로세스가 임계 영역에 들어가지 않도록 한다면 경쟁 조건을 피할 수 있을 것이다.

다만 임계 영역만으로 경쟁 조건이 만들어지지 않을 때가 있다. 공유 메모리를 사용하는 병렬 프로세스가 올바르고 효율적으로 수행되려면 다음과 같은 추가 조건이 필요하다.

• Mutual exclusion
  
  • 두 개 이상의 프로세스들이 동시에 임계 영역에 있어서는 안 된다.
• Progress
  
  • 임계 구역 바깥에 있는 프로세스가 다른 프로세스의 임계 구역 진입을 막아서는 안 된다.
• Bounded Waiting
  • 어떤 프로세스도 임계 구역으로 들어가는 것이 무한정 연기되어서는 안된다.
• 프로세스들의 상대적인 속도에 대해서 어떤 가정도 해서는 안된다.
  • CPU의 성능과 속도에 영향을 받지 않아야 한다.

3. 2개 프로세스의 상호 배제

2개 프로세스가 있다고 할 때 상호 배제를 구현하는 방법들을 각자의 단점과 발전과정을 중심으로 알아볼 것이다. 

이해가 쉽도록 flag 값을 A, B라고 적었지만 실제로는 0과 1이다.

3.1. Strict Alternation

//A 프로세스의 구조

while(1){

    while(turn != A);
    
    V++; //critical section
    
    turn = B;
    
}

Strict Alternation은 turn 변수를 이용해 A 프로세스와 B 프로세스 중 하나에 순서를 준다. 위 코드는 turn이 A일 때에 임계 영역에 들어가지 않고 while문으로 대기하다가 임계 영역에서 동작을 마치면 turn을 B로 준다. 따라서 상호 배제를 만족한다.

하지만 이 코드는 임계 영역의 실행 순서를 두 프로세스가 교대로 가져야만 한다. 예를 들어 turn이 A가 되어 임계 구역 내부 코드를 실행한 후 turn이 B가 되었는데 B 프로세스가 실행될 필요가 없다면, A 프로세스는 두 번 연속해서 임계 영역에 들어갈 수 없다. 따라서 Bounded waiting과 Progress를 만족하지 못한다.

3.2. Using array

//A 프로세스의 구조

while(1){

    flag[A] = true;

    while(flag[B] == true);

    V++; //critical section
    
    flag[A] = false;

}

1번 방법에서는 turn이라는 공유 변수 1개 만을 사용해서 문제가 생겼다. 이번에는 turn을 flag 배열로 대치한다. 이 알고리즘에서 flag 배열은 처음에 false로 초기화되어 있고 A 프로세스에 진입할 때 flag [A]를 true로 만들어서 진입 의사를 밝힌다. 그 다음에 B 프로세스가 진입할 의사가 있는지 확인하고, B가 임계 영역에서의 일을 끝낼 때까지 while문에서 기다린다. 마지막으로 임계 영역에서의 볼일이 끝났다는 것을 flag[A]를 false로 바꿈으로써 표시한다.

그러나 이 코드는 Progress를 충족하지 못할 때가 있다. 만약 2개의 프로세스가 거의 같은 시간에 진입하려고 하면 turn [A]와 turn [B]가 모두 true가 되고 두 프로세스 모두 while문에서 영원히 돌게 된다. 이렇게 두 프로세스 모두 상대의 flag가 false가 되기를 기다리는 상태를 교착상태라고 한다.

교착상태는 임계 영역 진입을 위해서 일어날 수 없는 사건을 기다리는 상태를 뜻하는 말이다.

3.3. Dekker's Algorithm

//A 프로세스의 구조

while(1){

    flag[A] = true;
    
    while(flag[B]){
    
    	if(turn == B){
        
            flag[A] = false;
            
            while(turn == B);
            
            flag[A] = true;
            
        }
        
    }
    
        V++; //critical section
        
        flag[A] = false;
        
        turn = B;
}

데커의 알고리즘은 2개의 프로세스를 위한 최초의 정확한 상호 배제 해결법으로 알려져 있다. 구성요소는 다음과 같다.

• flag : 초기값은 flag [0] = flag [1] = false이고 임계 영역에 들어가겠다는 표시는 true로 한다.
• turn : 0 또는 1의 값을 갖는다. 0인 경우엔 A의 순서, 1인 경우엔 B의 순서이나 위 코드에는 이해를 위해 A, B로 표시한다.

두 프로세스는 동시에 진행하면서 자신의 flag를 true로 하고 상대방 flag를 검사한 다음 turn값에 따라서 if 이하 절을 수행하거나 수행하지 않을 수 있고, 결국 turn값이 A이면 A 프로세스가 진입하고 turn값이 B이면 B 프로세스가 진입하게 된다. 따라서 한 프로세스는 두 번 연속해서 임계 영역에 진입할 수 있다.

3.4. Peterson's Algorithm

//A 프로세스의 구조

while(1){

    flag[A] = true;
    
    turn = B;
    
    while(flag[B] && turn == B);
    
    V++; //critical section
    
    flag[i] = false;
}

피터슨의 알고리즘은 모든 상호 배제를 위한 추가 조건을 만족하고 데커의 알고리즘보다 단순하다. 구성요소는 데커의 알고리즘과 같다. 동작을 살펴보자.

• A 프로세스를 동작시키고 싶다면 임계 영역에 들어가고 싶다는 표시로 flag [A]를 true로 만든다.
• turn 변수를 B로 설정하고 내부 while문을 수행한다.
• 이때 B 프로세스가 들어갈 의사표시를 하지 않았다면, 즉 flag [B]가 false라면 A 프로세스는 임계 영역에 바로 들어갈 수 있다.
• 그러나 만약 두 프로세스가 동시에 동작하려고 하면 turn 변수가 늦게 수행된 프로세스가 내부 while문에서 기다리며 순서를 양보한다.
• 먼저 임계 영역에 들어갔던 프로세스는 나오면서 자신의 flag를 false로 만들고 다른 프로세스가 임계 영역에 들어가는 것을 허용한다.
• 따라서 두 프로세스가 동시에 수행될 때 내부 while문의 turn값에 따라서 어떤 프로세스가 임계 영역에 들어갈지가 결정된다. turn이 A이면 B 프로세스가 수행되고 turn이 B이면 A 프로세스가 먼저 수행된다.

출처 : Operating System, 최현섭 고형대 임철수 오상엽 저 (이한출판사)