[IT 기술면접 준비자료] 상호배제(Mutual Exclusion)와 상호배제 알고리즘

 상호배제(Mutual Exclusion)란, 특정 프로세스가 공유 자원을 사용 중일 때 다른 프로세스가 이 자원에 접근하지 못하도록 막는 것을 의미한다. 그러니까, 공유를 하면 안되는 자원(Resource)의 동시 사용을 피하는 방법 중 하나이다.

 

 스레드의 경우, 프로세스와 달리 메모리의 Stack 영역을 제외한 부분을 다른 스레드와 공유하는데, 이 부분에서 스레드간 동시 사용을 피하고 싶을 때 주로 사용한다. (※참고: [IT 기술면접 준비자료] 교착상태와 식사하는 철학자들) 동시 접근을 막기 위해 프로그래머에 의해 구현된 코드 영역을 임계 구역(Critical Section)이라고 한다. 

  

 

▶상호배제를 재미있게 설명한 삽화. Mutex가 지켜주는 덕에, 화장실은 딱 1명만 쓸 수 있다.

   

 

더 쉬운 이해를 위해서, 상호배제를 소프트웨어 적으로 해결하는 알고리즘에 대해 설명하려고 한다. 상호배제 알고리즘은 대표적으로 3가지가 있다.

1. 데커(Dekker) 알고리즘

2. 피터슨(Peterson) 알고리즘

3. 제과점(Bakery) 알고리즘

  

데커 알고리즘은 flag와 turn이라는 변수로 임계영역에 들어갈 프로세스(혹은 스레드)를 결정하는 방식이다. flag값은 프로세스 중 누가 임계영역에 진입할 것인지 나타내는 변수이고, turn 변수는 누가 임계영역에 들어갈 차례인지 나타내는 변수이다. 구현 예는 아래와 같다.

1. While(1) {
2.   flag[i] = true;     // 프로세스 i가 임계영역 진입을 시도한다.
3.   while(flag[j]) {    // 프로세스 j가 현재 임계영역에 있는지 확인한다.
4.     if(turn == j) {     // 프로세스 j가 임계영역을 사용 중이라면
5.       flag[i] = false;    // 프로세스 i의 진입을 취소하고,  
6.       while (turn == j);  // turn이 j에서 바뀔 때 까지 기다린다...
7.       flag[i] = true;     // j의 turn이 아니면, 즉 임계영역에서 j가 나오면 재진입을 시도한다.
8.     }
9.   }
10. }
11. /*이 부분은 임계영역이다*/
12. ...
13. turn = j;           // 임계영역의 사용이 끝나면, turn을 넘긴다
14. flag[i] = false;    // 진입 flag값을 false로 바꾸어 임계영역 사용 완료를 알린다.
15. ...
16. }

 

 

피터슨 알고리즘은 데커 알고리즘과 상당히 유사하다. 하지만 상대방(다른 프로세스 혹은 스레드)에게 진입기회를 양보한다는 차이가 있다. 구현 예는 아래와 같다.

 

 

1. while(1) {
2.   flag[i] = true;            // 프로세스i가 임계영역에 진입을 시도
3.   turn = j;                  // 다른 프로세스에 진입 기회를 양보
4.   while(flag[i] && turn==j); // 다른 프로세스가 진입을 시도하면 대기 아니면 진입
5. /* 이곳은 임계영역이다. */
6. ...
7. flag[i] = false;           // 임계영역 사용 완료
8. ...
9. }

 

제과점 알고리즘은 위의 2개와 달리, 여러개의 프로세스(혹은 스레드)에 대한 처리가 가능하다. 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계영역에 진입한다.

 

 

1. while(1) {
2. ...
3.   isReady[i] = true;                 // 번호표를 받을 준비
4.   number[i] = max(number[0~n-1]) +1  // 현재 실행 중인 프로세스 중 가장 큰 번호로 배정
5.   isReady[i] = false;                // 번호표 수령 완료
6.  
7.   for( j =0; j < n; j++ ) {          // 모든 프로세스에 대해 번호표를 비교한다.
8.     while( isReady[j] );               // 비교할 프로세스가 번호표를 받을 때까지 대기
9.     while(number[j] && number[j] < number[i] && j<i);
10. // 프로세스 j가 번호표를 가지고 있고,
11. // 프로세스 j의 번호표가 프로세스i의 번호표보다 작거나 같을 경우
12. // j가 i보다 작다면(프로세스 j가 i보다 먼저 온 프로세스이면)
13. // 프로세스 j의 종료(number[j]=0)까지 대기
14. }
15. /* 이곳은 임계영역이다. */
16. ...
17. number[i] = 0;                     // 임계영역 사용 완료
18. ...
19. }

번호표의 숫자가 같은 값이면, 먼저 기다리고 있던 프로세스가 진입하는 것을 확인할 수 있다. (8번째 줄)

 

 

상호배제는 세마포어(Semaphore)와 자주 비교된다. 결론부터 이야기하면, 상호배제는 값이 1인 세마포어라고 할 수 있는데, 상호배제와 세마포어의 비교는 이 글의 범위를 벗어나서 생략한다. (귀찮아...)

 

 

 

함께보면 좋은 자료

 싱글턴(Singleton)패턴에 대해 자세히 알아보자

 

-끝-

 

 

 

그림출처

그림1: http://www.rudyhuyn.com/blog/2015/12/31/synchroniser-ses-agents-avec-lapplication/mutex/