[Operating System] 교착상태(Dead Lock)

교착상태(Dead Lock)

두 개 이상의 프로세스(또는 스레드)가 하나의 자원을 공유하여 사용하고 있을 때 서로가 사용중인 자원을 요구하지만, 요구를 영원히 들어줄 수 없는 상태

 

필요조건

조건 중 하나를 성립하지 않을 경우 교착상태는 발생하지 않음

아래 조건들이 성립해도 교착상태가 발생하지 않을 수 있다.

 

상호배제(Mutual Exclusion)

하나의 프로세스가 공유 자원을 점유하고 있을 때 다른 프로세스는 기다려야함(서로 다른 프로세스가 하나의 공유자원을 동시에 점유할 수 없음)

 

점유와 대기(Hold and Wait)

특정 프로세스가 공유 자우너을 점유한 상태에서 다른 공유 자원을 사용하기 위해 대기하고 있는 상황이 있어야 함 

 

비선점(No preemption)

선점 가능한 자원은 프로세스가 다른 프로세스가 점유한 자원을 강제로 빼앗을 수 있음. 즉 공유 자원에 대해 비선점하다는 것은 다른 프로세스가 점유한 자원을 강제로 빼앗을 수 없음을 의미

 

환형 대기(Circular wait)

각 프로세스가 서로가 서로 필요한 공유 자원을 점유하고 대기하는 형태가 원형을 이루어야 함

 

회피

자원이 어떻게 요청될지에 대한 정보를 제공하도록 요구하는 것으로 시스템에 환경 대기가 발생하지 않도록 자원 할당 상태를 검사한다.

 

두가지 알고리즘이 존재 

1. 자원 할당 그래프 알고리즘: 프로세스 노드와 자원 노드로 이뤄진 방향 그래프에서 요청/할당 간선을 추가로 가정해 보면서 사이클이 생기면 해당 요청을 보류하고 사이클이 없으면 허용한다. 단일 인스턴스 자원에 특히 직관적이다.
2. 은행원 알고리즘: 각 프로세스의 자원별 최대 요구량을 사전에 가정하고 매 요청 시 가용, 할당, 필요를 기반으로 안전성 검사를 수행한다. 안전 순서가 존재하면 승인, 없으면 보류한다.

안전성 검사

요청을 임시로 승인했다고 가정한 뒤, 가용 자원으로 완료 가능한 프로세스를 하나씩 '완료 처리'하며 모든 프로세스를 끝낼 수 있는 안전 순서가 있는지 확인