PE Notes · CA/OS
교착상태
서로 가진 자원을 기다리며 멈추는 교착의 네 조건과 예방·회피·탐지·복구를 가르고, 은행가 알고리즘의 안전 상태를 정리합니다.
두 프로세스가 각자 한 자원을 쥔 채 상대 것을 기다리면 둘 다 끝나지 않습니다. 입니다. 세마포어로 잠금을 엇갈리게 잡아도, IPC로 메시지를 서로 기다려도 같은 그림이 됩니다. 네 조건이 동시에 서야 발생합니다.
네 조건, 네 대응
상호 배제는 한 자원을 한 번에 하나만 씁니다. 점유 대기는 가진 것을 놓고 다른 것을 더 청합니다. 비선점은 자발 반납만 허용합니다. 는 대기 화살표가 고리를 만듭니다. 하나라도 깨면 교착은 성립하지 않습니다.
| 대응 | 하는 일 | 수단 |
|---|---|---|
| 예방 | 조건 하나를 제거 | 일괄 요청, 선점 허용, 전역 순서 |
| 회피 | 만 허용 | |
| 탐지 | 생긴 뒤 고리를 찾음 | |
| 복구 | 고리를 끊음 | 프로세스 종료, 자원 선점 |
예방은 구현이 단순하나 이용률이 떨어집니다. 전역 순서로 잠그면 순환은 사라집니다. 탐지는 그래프에서 프로세스→자원 요청과 자원→프로세스 할당을 그립니다. 단일 인스턴스에서 사이클이면 교착이 확정이고, 다중 인스턴스는 가능성만 말합니다.
은행가가 빌려 주는 법
은행가는 최대 요구, 현재 할당, 남은 필요, 가용을 표로 둡니다. 어떤 프로세스의 필요가 가용 이하이면 그를 끝낸다고 가정하고 자원을 회수합니다. 모두를 끝내는 순서가 있으면 안전하고, 없으면 그 요청을 거절합니다. 불안전이 곧 교착은 아니나, 교착으로 가는 문을 연 상태입니다.
가용이 (3, 2)이고 P1의 필요가 (1, 2)면 P1을 먼저 끝낼 수 있습니다. 회수한 뒤 다음을 고르는 식이 안전 순서입니다. 그 순서 없이 큰 요청을 승인하면 남는 조각이 누구의 필요도 못 채웁니다.
절차는 가용 확인 → 필요 ≤ 가용인 프로세스 선택 → 할당분 반납 → 반복입니다. 스케줄러가 준비 큐를 고르는 일과 달리, 여기는 “지금 빌려 줘도 모두가 끝날 수 있는가”를 먼저 묻습니다. 답안은 네 조건, 네 대응, 안전 순서, 그래프 사이클을 한 장에 닫습니다.