[공룡책] 교착상태

이전 글에서 동기화에 대한 이야기를 하며 교착상태라는 이야기가 나왔습니다.

Operating System - 동기화

Operating System - 동기화 예제

교착상태는 세마포가 Ready Queue 를 가지고 있고 둘 이상의 프로세스가 Critical Section 진입을 무한정 기다리고 있고 Critical Section 에서 실행되는 프로세스는 진입 대기 중인 프로세스가 실행되야만 빠져나올 수 있는 상황을 말합니다.

이전 글에서 예방에 대한 내용을 보충하기 위해 작성했습니다.

교착상태의 필요조건

1. 상호 배제(mutual exclusion): 최소 하나의 자원이 비공유 모드로 점유되어야 합니다.
2. 점유 대기(hold and wait): 최소 하나의 자원을 점유한 채 다른 점유된 자원을 얻기 위해 대기해야 합니다.
3. 비선점(no preemption): 자원을 선점할 수 없어야 합니다.
4. 순환 대기(circular wait): 다음 스레드가 점유한 자원을 대기하는 것이 순환됩니다.

이 네가지 조건이 모두 성립되면 데드락이 발생합니다.

1, 2, 3번은 병행 프로그래밍을 수행하기 위해 필요한 조건들이고 일반적으로 4번을 예방해서 데드락을 없앱니다.

교착상태 예방

1. 상호 배제

• 자원을 공유해서 처리하는 방법입니다.

mutex 락과 같은 근본적으로 공유가 불가능한 자원이 존재하기 때문에 불가능합니다.

2. 점유 대기

• 자원을 요청할 때마다 다른 자원을 보유하지 않도록 보장해서 처리하는 방법입니다.

각 스레드가 실행하기 전에 모든 자원을 요청하고 할당해야 합니다.

자원 이용률이 낮을 수 있고, starvation이 발생할 수 있다는 문제가 있기 때문에 꺼려집니다.

3. 비선점

• 자원을 선점해서 처리하는 방법입니다.

사용중인 자원이더라도 요청이 생기면 사용 가능한지를 검사하고 할당합니다.

CPU 레지스터나 DB 트랜잭션처럼 상태의 저장과 복원이 쉬운 자원에 종종 적용됩니다.

mutex락과 세마포같은 자원에는 적용될 수 없으며 교착상태를 해결하기에 어렵습니다.

4. 순환 대기

• 필요 조건 중 하나를 무효화해 순환을 없애는 방법입니다.

앞서 제시한 세가지 옵션은 대부분 실용적이지 않습니다.

자원 점유의 우선순위를 부여해 할당시키는 방법으로 순환 대기를 해결하곤 합니다.

무한을 고려하지 않는 이상 스레드를 오름차순으로 정렬하면 끝이 있게 되고, 순환이 끊기게 됩니다.

References

• Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』