[운영체제] 환형대기 조건(사이클)을 차단하여 교착상태를 예방하는 방법

운영체제에서 교착상태(Deadlock)는 여러 프로세스가 서로 자원을 점유한 채, 상대가 가진 자원을 기다리면서 무한 대기에 빠지는 현상이다. 교착상태가 발생하려면 다음 네 가지 조건이 모두 동시에 성립해야 한다.

1. 상호 배제 (Mutual Exclusion) – 자원은 한 번에 하나의 프로세스만 사용할 수 있다.
2. 점유 대기 (Hold and Wait) – 자원을 점유한 상태에서 다른 자원을 요청하며 대기한다.
3. 비선점 (No Preemption) – 점유한 자원을 강제로 빼앗을 수 없다.
4. 환형 대기 (Circular Wait) – 자원을 기다리는 관계가 원형 고리를 이룬다.

교착상태를 막기 위해선 이 중 하나 이상의 조건을 제거하면 된다.

그중 환형 대기 조건을 제거하는 방법에 대해 알아보자. 

 

자원에 일련번호(순서)를 부여하기

환형 대기를 막기 위한 대표적인 방법은 모든 자원에 고유한 일련번호를 부여하고, 프로세스가 자원을 요구할 때 항상 점유한 자원의 번호보다 번호가 더 큰 자원만 요구하도록 제한하는 것이다.

예를 들어 자원 R1, R2, R3이 있다고 가정하면, 각각의 자원을 서로 다른 자연수로 지정하는 함수 f를 통해 다음과 같이 일련번호를 줄 수 있다:

• R1: 1번
• R2: 2번
• R3: 3번

이제 모든 프로세스는 자신이 점유하고 있는 자원보다 번호가 높은 자원만 요구해야 한다. 즉, R1을 점유한 프로세스는 R2나 R3는 요구할 수 있지만, 반대로 R3를 점유한 프로세스는 R1을 요구할 수 없다.

 

환형 대기(사이클)이 사라지는 원리

위 원칙에 따라 프로세스가 자원을 요구할 때 일련번호 기준으로 항상 오름차순이 되도록 요구하거나, 프로세스가 자원을 요구할 때 점유하고 있는 자원 중 그보다 일련번호가 큰 자원은 모두 해제하는 방법으로 자원의 요구가 항상 오름차순이 되도록 한다면 사이클이 형성될 수 없다. 

 

왜냐하면, 모든 자원 요구의 흐름이 한 방향으로만 진행되기 때문이다. 

 

사이클이 없다는 것은 곧 환형 대기가 제거된 것이고, 결과적으로 교착상태도 발생하지 않는다는 것을 의미한다.

 

만약 이러한 규칙이 없다면, 아래와 같이 사이클이 생길 수 있다. 

 

이처럼 교착상태가 생긴다. 하지만 자원의 요구가 오름차순으로만 이루어지도록 한다면, 마지막 P3가 R3을 점유한 상태에서 R1을 요구하는 것이 불가능해지기 때문에 사이클 자체가 차단된다. 

 

이 방법은 자원의 일련번호가 가급적 프로세스가 자원을 요구하는 순서에 맞도록 설정되어야 프로세스 입장에서 큰 무리가 없이 수행 가능하지만, 현실적으로 프로세스마다 자원의 요구 순서가 다를 수 있으므로 자원의 일련번호 설정에 어려움이 있을 수 있다. 

 

또한 프로세스의 자원 요구 순서가 일련번호의 오름차순을 지키지 못하면, 점유 중인 자원 중 일련번호가 큰 자원을 해제해야 하는데, 이것이 적용 불가능한 자원도 있을 수 있다. (ex. 프린터)