[OS] 교착상태(Deadlock)

교착상태(deadlock)란?

둘 이상의 프로세스들이 다른 스로세스가 차지하고 있는 자원을 서로 무한정 기다리고 있어 프로세스의 진행이 중단된 상태를 의미합니다. 

교착상태 예시

교착상태의 필수 조건

1. 상호 배제(Mutual Exclusion) : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구하는 것으로, 한 프로세스가 사용 중이면 다른 프로세스는 반드시 기다려야 하는 경우. -> 동시 사용 불가(ex: 프린터)
2. 점유와 대기(Hold and Wait) : 프로세스가 적어도 하나 이상의 자원을 할당받은 채로 다른 프로세스의 자원이 해제되기를 기다리는 경우.
3. 비선점(Non-preemption) : 프로세스가 점유한 자원은 사용이 끝날 때까지 해제할 수 없는 경우.
4. 환형 대기(Circular Wait) : 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 각 프로세스는 다음에 있는 프로세스가 요구하는 자원을 갖고 있는 경우.

교착상태의 해결책

1) 교착상태 예방(Prevention) 

필요조건 4가지 중 한가지 이상을 제거

1. 상호배제 제거 : 모든 자원 공유 허용, (현실적으로 불가능)
2. 점유돠 대기 제거 : 필요 자원 한 번에 모두 할당 -> 자원 낭비 발생, 무한 대기 발생 가능
3. 비선점 제거 : 모든 자원에 대해 선점 허용(현실적으로 불가능), (유사한 방법) 프로세스가 할당받을 수 없는 자원을 요청한 경우, 기존에 가지고 있던 자원을 모두 반납하고 작업 취소.(심각한 자원 낭비발생, 비현실적)
4. 환형대기 제거 : 자원들에 순서를 부여, 프로세스는 순서의 증가 방향으로만 자원 요청 가능

교착상태 예방은 교착상태가 절대 발생하지 않지만 심각한 자원 낭비가 발생하며, 비현실적입니다. 그렇기에 회피, 발견, 회복을 주로 이용합니다. 

 

2) 교착상태 회피(Avoidance)

시스템의 상태를 계속 감시하고 교착상태가 될 가능성이 있는 자원 할당은 요청을 보류합니다. 

시스템을 안전상태(교착상태를 일으키지 ㅇ낳으면서 각 프로세스에 필요한 자원을 할당할 수 있는 상태)로 유지합니다.

은행원 알고리즘

• 교착상태 회피를 위한 이론적 기법
• 한 종류의 자원이 여러 개라는 가정하에 시스템을 항상 안전 상태로 유지

예시문제) 프로세스 0,1,2,3,4에 대한 자원 A,B,C의 현재 할당량과 수행에 필요한 최대 요구량은 다음과 같다. 이와 같은 상황에서 자원의 잔여량이 각각 1일 때 모든 작업이 완료될 수 있는 안전 순서를 쓰시오.

할당량과 요구량 표

---

자원의 잔여량

잔여량이 1씩 이므로 P0만 최대 요구량 만큼의 자원을 할당받을 수 있다. P0의 작업이 끝나면 P0의 최대 요구량 만큼의 반환이 된다. 이 반환값으로 다른 프로세스들에게 할당하고 반환받고를 반복한다. 

답 : P0 -> P1 -> P3 -> P2 -> P4

---

3) 교착상태 탐지(Detection) 

• 교착상태 방지를 위한 사전 작업을 하지 않음.(교착상태 발생 가능)
• 주기적으로 교착상태 발생 확인
• 반드시 회복 과적이 필요

4) 교착상태 회복(Recovery)

• 교착상태를 검출한 후 해결하는 과정
• 프로세스 종료 : 교착상태에 있는 프로세스를 종료시킴. 종료된 프로세스는 이후 재시작 됨.
• 자원 선점 : 교착상태 해결을 위해 선점할 자원 선택, 선정된 자원을 가지고 있는 프로세스에서 자원을 가져옴.
• 복귀 : 프로세스 강제 종료 후, 가장 최근의 체크포인트에서 재시작