교착 상태(dead lock)

교착상태 정의

교착 상태(dead lock)란 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태입니다. ex) 식사하는 철학자

 

교착상태 발생조건 

아래 4가지 조건을 모두 충족할 경우에만 교착상태가 발생할 확률이 있으며, 하나라도 만족하지 않을 경우에는 발생하지 않습니다.

• 상호배제 : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구
• 점유와 대기 : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다림
• 비선점 : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없음
• 원형 대기 : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음

 

교착상태 해결 방법

<예방>

• 상호배제 : 모든 자원을 공유 가능하게 만들기(다만, 현실적으론 불가능)
• 점유와 대기 : 한 프로세스에 수행되기 전에 모든 자원을 할당시키고 나서 점유하지 않을 때에는 다른 프로세스가 자원을 요구
• 비선점 : 선점 가능하도록 만들기
• 원형 대기 : 자원 유형에 따른 순서 정하기

<회피>

• 자원 할당 그래프 알고리즘 : 프로세스가 자원을 요청하고 자원이 프로세스에게 할당 되는 '방향성을 가진 그래프'로써, 데드락 발생 여부를 탐지 할 수 있는 그래프
• 은행원 알고리즘 : 검사하여 *안정상태에 있으면 자원을 할당하고 불안정상태라면 다른 프로세스들이 자원을 해제할 때까지 대기

* 안전상태 : 교착상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태

<회복>

• 선점을 통한 회복 : 한 프로세스씩 자원 몰아주기
• 프로세스 강제 종료를 통한 회복 : 모든 프로세스를 강제 종료 혹은 하나씩 강제종료

 

 

 

---

Reference

혼자공부하는 컴퓨터구조 + 운영체제

https://kukuta.tistory.com/281

https://wannabe-gosu.tistory.com/26

https://ko.wikipedia.org/wiki/%EA%B5%90%EC%B0%A9_%EC%83%81%ED%83%9C