[Server] 상호 배제 알고리즘 - Dekker's Algorithm

 

 

병행 프로세스 및 상호 배제

운영체제는 복수의 프로세스들을 관리하는 과정에서 여러 문제를 직면하게 된다.

그중 가장 큰 문제는 Race Condition( 경쟁 조건 )의 극복이다.

이에 대한 자세한 설명 및 여러 동기화 도구들은 아래 포스팅에 나와있다.

[Server] Spin lock & Mutex & Semaphore

운영체제가 여러 프로세스들을 관리할 때도 Race Condition이 발생할 수 있으며,

두 개 이상의 프로세스가 동시에 공유 자원에 접근할 경우 프로세스의 수행 순서에 따라

결괏값이 달라질 수 있고, 이는 시스템에 대한 신뢰도가 낮아진다.

이러한 문제를 해결하기 위해 하나의 프로세스가 공유 자원에 접근하는 동안

다른 프로세스의 접근을 막는 Mutual Exclustion( 상호 배제 )가 달성되어야 하고

해당 포스트에서는 상호 배제 알고리즘 중 하나인 Dekker 알고리즘을 살펴볼 것이다.

 

딘, 병행 프로세스가 올바르게 효율적으로 수행되기 위한 추가적인 조건이 필요하다.

• Mutual Exclusion
  하나의 프로세스/스레드만 진입해서 실행한다는 것
  또는 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘으로,
  두 개 이상의 프로세스들이 동시에 임계 영역을 들어가면 안 된다.
• Progress
  임계 구역 바깥에 있는 프로세스가 다른 프로세스의 임계 구역 진입을 막으면 안 된다.
  즉 임계 영역을 사용할 의향이 없는 프로세스에 의해
  진입을 요구하는 프로세스의 수행이 간섭받는 것은 안 된다.
• Bounded Waiting
  어떠한 프로세스라도 임계 구역으로 들어가는 것이 무한정 연기되어서는 안 된다.

다음과 같이 3개의 조건이 존재하고,

공유 메모리를 사용하는 병렬 프로세스를 제어하기 위해서는 해당 조건을 만족시켜야 한다.

이제 해당 조건을 만족하는 Dekker 알고리즘을 살펴보자.

 

Dekker's Algorithm

Dekker 알고리즘은 2개의 프로세스를 위한 최초의 정확한 상호 배제 해결법으로 알려져 있다. 

두 개의 프로세스는 P0 / P1이라고 명칭 하고, 구성요소 및 알고리즘 코드는 다음과 같다.

boolean flag[2];
int turn;

do {              

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

          while (turn == j); 

          flag[i] = true;     
        }
    }
    [ This is Critical Section ]
    turn = j;            
    flag[i] = false;       
    [ This is Remainder Section ]
    
} while(true)

• flag[2]
  각 인덱스 번호에 해당하는 프로세스가 자신의 임계 영역 사용 의사를 표현
  ( true : 원함 / false : 원하지 않음 )
• turn
  어떤 프로세스에게 임계 영역 진입에 대한 우선권을 줄지 표시
  ( 0 : P0 차례 / 1 : P1 차례 )

두 프로세스는 동시에 진행하면서 자신의 flag를 true로 한다.

상대방 flag를 검사한 다음 turn값에 따라서 if 이하 절을 수행하거나 수행하지 않을 수 있고,

결국 turn값이 P1이면 P1 프로세스가 진입하고 turn값이 P2이면 P2 프로세스가 진입하게 된다.

 

P0 / P1 프로세스 코드

흐름을 이해하기 위해 프로세스 별 코드는 아래 그림과 같다.

그전에 turn에 대한 초기값 할당이 반드시 필요하다.

만약 turn에 대한 초기값 설정이 없으면 P0의 while(flag[1]) P1의 while(flag[0])에 의해

두 프로세스 모두 if문에 진입하지 못하고 while 문만 의미 없이 반복하게 된다.

따라서 turn에 대한 초기값을 0 또는 1로 설정해 줄 필요가 있다.

 

P0 / P1 Process Code

 

 

이제 Dekker 알고리즘의 전체 흐름을 살펴보면 다음과 같다.

turn을 0으로 초기화한 경우

- P0, P1 모두 (1)번 문장에 의해 flag를 true로 만들고,

  (2)번 문장에 의해 while()문 안으로 들어가게 된다.

- 여기서 turn을 0으로 초기화하였으므로, P0은 turn이 1로 값이 변경될 때까지,

  if문을 들어가지 못하고, flag[1]의 값이 변경될 때까지 (2)번 문장의 while문을 계속 반복할 것이다.

- P1은 turn 값이 현재 0이므로 if문 안으로 들어가게 된다. 이때의 흐름을 보면 다음과 같다.

1. P1의 (4)번 문장에 의해 flag[1]의 값이 false로 변경된다.
2. P0는 flag[1]의 값이 false로 변경되면서 (2)번 문장의 while문을 빠져나오고,
   critical section에 진입하게 된다.
3. P1은 turn의 값이 0이므로 (5)번 문장에 의해 while 문에 들어가고 계속 반복하게 된다.
   (이때 turn의 값이 1로 변경될 때까지 계속 반복)
4. P0는 critical section의 코드를 모두 완료하면 (8)번 문장을 실행하고 turn=1로 변경하게 된다.
5. 이때 P1은 turn의 값이 1로 변경되었으므로,
   (5)번 문장을 while문을 빠져나올 수 있고, (6)번 문장을 실행하여, flag[1]=true로 변경한다.
   하지만 아직 flag[0]의 값이 변경된 것은 아니기 때문에 (2)번 문장의 while문은 나올 수 없다.
6. P0이 이제 (9)번 문장을 실행하고 flag[0]을 false로 변경하였다고 하자.
   그러면 이제 P1도 (2)번 문장의 while문을 빠져나오고 그 후 critical section에 진입하게 된다.
   이때는 이미 P0에서 critical section을 마치고 나왔기 때문에
   Mutual Exclusion 조건을 만족하게 된다.

이제 다음 진행 상황을 나타내면 다음과 같다.

1. P0은 do 부분의 한 cycle을 마치고 다시 (1)번 문장을 실행하러 간다.
   P1은 이제 critical seciton에 진입하여 해당 코드를 실행한다고 하자.
2. P0은 (1)번 문장 실행 후 flag[1]이 아직 true이므로 (2)번 문장 while문으로 들어가게 된다.
   그 후 turn이 아직 1이므로 (3)번 if문으로 들어가고 (4)번 문장 flag[0]=false로 변경하고
   (5)번 while문으로 들어가게 된다.
3. P1은 critical section을 마치고 (8)번 문장 turn=0으로 변경하게 되고
   이 순간 P0는 (5)번 while문을 빠져나온다.
4. P1이 (9)번 문장 flag[1]=false;를 실행하는 순간
   P0는 (6)번 문장을 통해 flag[0]을 true로 변경하고 (2)번 while문을 빠져나온다.
   이때 다시 P0은 critical section을 들어갈 수 있고,
   P0이 (2)번 while문을 빠져나오기 전에 '(6)번 문장을 통해 flag[0]을 true로 변경’
   문장을 통해 P1이 다시 (1)번 문장을 실행하고 (2)번 while문으로 들어가서
   P0이 critical seciton을 완료하기 전까지 계속 (2)번 while문을 돌게 된다.
5. P0이 critical seciton을 완료하고 (8),(9)를 완료해야만
   다시 (2)번 전체 while문을 나오고 P1이 critical section을 다시 들어가게 된다.

이와 같은 흐름으로 Dekker 알고리즘을 정리할 수 있다.

Dekker 알고리즘의 흐름은 다음과 같은데 이 Dekker 알고리즘이
위의 3가지의 임계 구역 문제 요구사항을 충족하는지 살펴보아야 한다.

 

Dekker's Algorithm의 요구 조건 만족도

Mutual Exclusion

Mutual Exclusion은  while(flag[j])와 while(turn == j) 구문을 통해 해당 문제를 해결할 수 있다.

하나의 프로세스가 임계 영역에 진입한 경우 이 프로세스가 임계 영역을 빠져나와서

turn과 flag 값을 변경하지 않는 한 다른 프로세스는 임계 영역에 접근할 수 없다.

또한 두 프로세스가 모두 임계 영역에 진입하기 전 Race Condition 상태일 때,

1 또는 0의 상태만 가질 수 있는 turn값을 확인함으로써,

둘 중 하나의 프로세스만 임계 영역으로 진입할 수 있다.

 

Progress

Progress는 임계 구역 바깥에 있는 프로세스가

다른 프로세스의 임계 구역 진입을 막으면 안 된다는 조건이다.

while ( flag[j] ) 구문을 통해 상대 프로세스가 임계 영역에 진입할 의사가 없다면 

turn 값에 관계없이 해당 while()문을 빠져나오므로

진입하기 원하는 프로세스는 임계 영역에 진입 가능하다.

 

Bounded Waiting

Bounded Waiting은 어떠한 프로세스라도

임계 구역으로 들어가는 것이 무한정 연기되어서는 안 된다는 조건이다.

Dekker 알고리즘에서는 turn 변수를 이용하여 Bounded Waiting을 충족한다.

구체적으로는 한 프로세스가 임계 구역에 들어가면,

임계 구역을 빠져나올 때 turn을 상대방에게 양보하는 메커니즘이다.

즉, turn = j로 설정하여 다음 차례는 상대 프로세스가 될 수 있도록 만들어 준다.

프로세스 i가 임계 구역에 들어가려고 할 때,

flag[j] == true인 경우에 turn == j 이면 프로세스 j의 차례이므로

i는 자신의 flag[i]를 false로 바꾸고 대기하게 된다.

그러나, turn이 변경될 때까지 무한히 대기하는 것이 아니라,

turn 값이 i로 바뀌면 다시 진입을 시도할 수 있는 것이다.

이 과정을 통해 turn 값은 두 프로세스가 번갈아가며 임계 구역에 진입할 수 있도록 보장해 준다.

즉, 한 프로세스가 계속해서 임계 구역을 독점하는 상황을 방지하고,

다른 프로세스는 유한한 횟수 안에 임계 구역에 진입할 기회를 얻게 된다.