상호 배제 (Mutual Exclusion)

상호 배제는 동시에 실행되는 프로세스들이 임계 영역(Critical Section)에 동시에 들어가지 않도록 하는 것이다.

 

임계 영역(Critical Section)은 공유 자원에 접근하는 프로세스의 영역이다. 즉, 프로그램 코드 중에서 공유 자원에 접근하는 부분의 코드를 의미한다.

 

예를 들면, 어떤 프로그램이 파일의 이름을 변경하는 기능이 있을 때, 파일의 이름을 변경하는 코드가 있는 곳이 임계 영역이다. 파일은 여러 프로그램이 사용할 수 있는 공유 자원이다. 2개의 프로그램이 동시에 한 파일의 이름을 변경하려고 하면 예측할 수 없는 결과가 생길 수 있다. 2개의 프로그램이 동시에 파일의 이름을 변경하는 임계 영역에 들어가지 못하도록 하는 기법이 상호 배제이다.

 

 

상호 배제는 MS Windows, Unix, Linux 등의 멀티 태스킹 운영체계에서 기본적으로 지원한다. 윈도우에서 열려 있는 파일을 삭제하려고 하면 다음과 같은 메세지가 뜬다.

 

 

상호 배제의 필요성과 해결법은 1965년 Edsger W. Dijkstra에 의해 처음으로 제안 되었다.

 

상호 배제는 다음과 같은 방법들이 있다.

  - Lock

  - Semaphore (세마포어)

  - Monitor

  - Message Passing

  - Tuple Space

 

상호 배제는 하드웨어로 구현될 수도 있고 소프트웨어로 구현될 수도 있다. 하드웨어에 의한 방법은 주로 CPU 명령어에서 지원한다.

 

상호 배제를 순수하게 소프트웨어만으로 구현하기 위해서는 조금 복잡한 알고리즘이 필요하다. 소프트웨어로 구현할 수 있는 상호 배제 알고리즘은 다음과 같다.

  - Dekker 알고리즘

  - Peterson 알고리즘

  - Lamport's bakery 알고리즘

  - Szymanski 알고리즘

  - Taubenfeld's black-white bakery 알고리즘

 

상호 배제가 제대로 동작하지 않을 때 다음과 같은 문제가 생길 수 있다. 

  - Deadlock : 2개의 프로세스가 동시에 공유 자원을 얻기 위해 2개의 프로세스가 모두 대기하는 상태

  - Starvation : 프로세스가 공유 자원을 절대 얻을 수 없는 상태

  - Priority Inversion : 우선 순위가 높은 프로세스가 공유 자원을 얻는데 우선 순위가 낮아지는 것

 

C#에서는 상호 배제를 위해 Mutex, lock, Monitors 등의 명령어를 지원한다.