상호 배제(mutual exclusion)
상호 배제란 둘 이상의 프로세스가 동시에 임계 영역(CS : Critical Section)에 진입하는 것을 방지하기 위해 사용되는 알고리즘입니다.
공유 자원의 동시 사용을 방지하여 race condition과 같은 문제를 피할 수 있습니다.
상호 배제 기본 연산
- enterCS() primitive (primitive: 기본 연산)
- Critical section 진입 전 다른 프로세스가 critical section 안에 있는지 검사를 합니다.
- Critical section에 다른 프로세스가 있다면 비어 있을 때까지 대기를 합니다.
- exitCS() primitive
- Critical section을 벗어날 때의 후처리 과정을 합니다.
- Critical section을 벗어남을 표시하게 됩니다.
상호 배제 기본 연산을 위한 요구사항
상호 배제를 구현하기 위해선 아래 세 가지 조건을 만족해야 합니다.
1. Mutual exclusion (상호 배제)
- CS에 프로세스가 있으면, 다른 프로세스의 진입을 금지하게 합니다.
2. Progress (진행)
- CS안에 프로세스가 없다면 CS에 진입할 수 있어야 합니다.
3. Bounded waiting (유한한 대기)
- 프로세스의 CS 진입은 유한 시간 내에 허용되어야 합니다.
- 계속 기다리는 상황을 만들지 말고 언젠간 들어갈 수 있게 하여 기아상태(starvation)를 방지합니다.
요구사항 위배
상호 배제를 구현할 때 요구사항을 위배하는 경우를 알아보도록 하겠습니다.
1. Progress 위배
위 알고리즘은 turn 값에 따라 CS에 진입할 수 있는 Process가 결정됩니다.
- turn : 0 = ProcessA 만 CS에 진입 가능
- turn : 1 = ProcessB 만 CS에 진입 가능
반드시 A 다음에 B 또는 B 다음에 A 순으로 CS에 진입하도록 설계되어 있습니다.
한 Process가 두번 연속 CS에 진입할 수 없기 때문에 Progress 위배를 하게 됩니다.
2. Mutual exclusion 위배
위 알고리즘은 자신의 flag값을 ture로 변경하여 CS에 진입할 것을 알리고 false로 변경하여 CS에 나왔다는 것을 알림으로써 상호 배제를 구현했습니다.
하지만 다음과 같은 상황에서 동시에 CS에 진입하게 되어 Mutual exclusion에 위배됩니다.
- ProcessA가 while문에서 선점을 당함.
- ProcessB가 CS에 진입함.
- ProcessA가 while문에서 빠져나와 CS에 진입함.
3. Bounded waiting 위배
위 알고리즘은 다음과 같은 상황에서 Bounded waiting을 위배하게 됩니다.
- ProcessA가 while문을 진입하기 전에 선점을 당함.
- ProcessB가 while문을 수행함.
- ProcessA가 while문을 수행함.
위 상황은 두 프로세스가 무한히 CS에 진입하지 못하게 되어 Bounded waiting에 위배 될 뿐만 아니라
CS에 진입한 프로세스가 없음에도 불구하고 진입을 하지 못하기 때문에 Progress에도 위배가 됩니다.
상호 배제 구현시 선점이 발생하는 위치에 따라 요구조건을 위배하는 경우가 발생할 수 있습니다.
이런 상호배제 요구사항을 만족하는 최초의 알고리즘은 데커(Dekker) 알고리즘이며 이밖에 여러 가지 방법들이 있습니다.
