상호배제(Mutex : Mutual eXclusion)

1) 임계 구역

• 다중 프로그래밍 기법에서 둘 이상의 프로세스가 운영될 때 서로 공유하게 되는 자원을 말한다.
• 프로세스 간의 통신에 필요한 매개 변수의 역할로 임계구역을 사용할 수도 있다.
• 자원을 공유하는 각 프로세스는 베타적으로, 동시에 사용할 수 없으며 특정 프로세스가 독점하게 해서도 안된다.

2) 상호 배제의 개념

• 하나의 프로세스만 임계구역을 사용할 수 있도록 다른 프로세스의 접근을 차단하는 것이다.
• 상호배제를 위한 4가지의 요구조건이 충족되어야 한다.
  • 두 개 이상의 프로세스들이 동시에 임계구역에 있으면 안 됨
  • 어떤 프로세스도 임계구역에 진입하는 것이 무한정 연기되면 안 됨
  • 임계구역 안에 있는 프로세스가 다른 프로세스의 임계구역 진입을 막을 수 있어야 함
  • 프로세스들의 상대적인 속도(각 프로세스들의 처리 속도, 접근 방법, 상태)에 대해 어떠한 가정을 하면 안 됨

3) 상호배제 알고리즘

(1) 잠금 : 하나의 프로세스가 임계구역을 점유한 후, 다른 프로세스가 접근할 수 없도록 잠그는 것이다.

(2) 인터럽트 봉쇄 : 임계구역이 사용 중일 때 모든 인터럽트가 발생하지 않도록 하여 새로운 프로세스의 생성 및 접근을 막는 것이다.

(3) 엄격한 교대

• 두 개의 프로세스가 하나의 임계구역을 사용할 수 있을 때 서로 교대로 접근할 수 있도록 하는 것이다.
• 하나의 프로세스가 연속으로 접근할 수 없으며, 반드시 상대 프로세스가 사용하고 난 뒤에 접근할 수 있도록 하는 것이다.

(4) 상호배제 알고리즘의 한계

• 현재 사용 중인 프로세스의 실행시간이 길다면 다른 프로세스는 임계구역을 사용하기 위해 계속해서 대기하게 된다(Busy Wait).
• 바쁜 대기 현상이 증가하면 운영체제는 부담을 갖게 되어 컴퓨터 시스템의 전체 성능이 떨어지게 되는데, 이 현상을 제거하기 위해 세마포어 알고리즘을 사용한다.

4) 세마포어(Semaphore)

(1) 세마포어의 개념

• 임계구역을 지키기 위한 기존 상호배제 알고리즘이 바쁜 대기 현상을 야기하는 것을 방지하고자 개발된 알고리즘이다.
• 프로세스가 이러한 바쁜 대기 현상을 방지하기 위해 잠시 재우고(Sleep, Wait, P연산) 나중에 깨워주는 (Wakeup, Signal, V연산) 방식을 사용한다.
• 세마포어 알고리즘에서 사용되는 공유 자원의 수를 나타내는 변수를 세마포어 변수(S)라고 한다.

(2) 세마포어의 특징

• 세마포어에 대한 연산은 소프트웨어 및 하드웨어로 구현되며 연산 처리 중에 인터럽트되어서는 안된다.
• 이진 세마포어는 0과 1의 값을 가지고, 산술 세마포어는 0과 자연수를 가질 수 있다.
• 프로세스 사이의 동기를 유지(동기화)하게 한다.

(3) 모니터(Monitor)

• 세마포어 알고리즘을 구현한 프로그램이다.
• 모니터는 프로세스들이 사용할 수 있는 공유 자원 혹은 공유 자원 그룹을 할당하는 데 사용한다.
• 데이터 및 프로시저를 포함하는 병행성 구조(Concurrent Construct)이다.
• 모니터 외부의 프로세스는 모니터 내부의 데이터를 직접 접근할 수 없다.
• 캡슐화 개념을 사용하며 스위치 개념이 적용되어 한 번에 하나의 프로세스만 모니터에 진입(Entry)할 수 있다.