[OS] 5. 데드락 (Deadlock)

5. 데드락 (Deadlock)

1. 데드락 (Deadlock)
2. 데드락의 처리

 

1. 데드락 (Deadlock)

1.1. Deadlock (= 교착 상태)

일련의 프로세스들이 서로가 가진 자원을 기다리며 Block 된 상태

 

1.2. Deadlock 발생의 4가지 조건

1. Mutual Exclusion (상호 배제)

   • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

2. No Preemption (비선점)

   • 프로세스는 자원을 스스로 내놓을 뿐 강제로 빼앗기지 않음

3. Hold and Wait (점유 대기)

   • 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유 자원을 놓지 않고 갖고 있음

4. Circular Wait (순환 대기)

   • 자원을 기다리는 프로세스간, 사이클이 형성되어야함

 

 

2. 데드락의 처리

2.1. Deadlock Prevention

자원 할당 시, 데드락의 4가지 조건 중, 어느 하나가 만족되지 않도록 하는 것

상호 배제 (Mutual Exclusion) 부정

• 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다

비선점 (No Preemption) 부정

• Save & Restore 이 가능한 자원에서 선점(Preemption)을 허용한다

점유 대기 (Hold and Wait) 부정

• 프로세스 시작 시, 모든 자원을 할당한다
• 자원이 필요한 경우, 보유 자원을 놓는다

순환 대기 (Circular Wait) 부정

• 할당 순서를 정하여, 정해진 순서대로 자원을 할당한다

 

2.2. Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용하여, 데드락의 가능성이 없는 경우에만 자원 할당

자원 할당 그래프 (Resource Allocation Graph)

• 각 자원의 타입이 한 개 씩 있는 경우 (Single Instance)
• 프로세스와 자원의 요청 및 할당 관계를 표시함
• Circular Wait 조건을 발견하기 위한 목적으로 사용
• 사이클을 형성 (단, 자원이 사이클을 형성하는 프로세스 외의 다른 프로세스들에게도 점유 당하고 있다면 제외) 한다면 데드락이 발생하는 경우

 

은행원 알고리즘 (Banker's Algorithm)

• 각 자원의 타입이 여러개 있는 경우 (Multiple Instance)
• 프로세스가 자원을 요구할 때, 시스템이 자원을 할당한 후 안정 상태로 남아있게 되는지를 사전에 검사하여 교착상태를 회피하는 방법
• 알고리즘을 이용해 안정 상태 인지 확인하고 안정 상태라면 자원을 할당하고 그렇지 않으면 다른 프로세스들이 자원을 해제할 때까지 대기
• 할당할 수 있는 자원의 수와 사용자의 수가 일정해야하고, 항상 불안정 상태를 방지해야 하므로 자원 이용도가 낮다는 단점을 지님

 

2.3. Deadlock Detection & Recovery

데드락 발생은 허용하되, 그에 대한 감지를 하여 데드락 발견시 회복함

Detection

• Single Instance 의 경우 자원할당 그래프

• Multiple Instance 의 경우 Banker's Algorithm

Recovery

1. Process Termination

   • 데드락에 연관된 모든 프로세스를 죽임

2. Resource Preemption

   • 비용을 최소화할 Victim 프로세스를 선정하여 자원을 빼앗음

 

2.4. Deadlock Ignore

데드락을 시스템이 책임지지 않음

• 데드락이 매우 드물게 발생하므로, 데드락에 대한 조치 자체가 더 큰 overhead 일 수 있음
• 만약, 시스템에서 데드락이 발생한 경우, 프로그래머가 직접 process를 죽이는 방법으로 대처
• UNIX, Windows 등 대부분의 OS 가 채택

 

 

 

---

예상 질문

1. 교착상태란 무엇인가를 설명한 후, 교착상태 발생 조건 4가지에 대하여 설명하세요
2. 교착상태 회피 기법인 Banker's Algorithm 에 대하여 설명하세요
3. 기아상태를 설명하는 Dining Philosophers Problem 에 대하여 설명하세요

 

참고자료

• https://m.blog.naver.com/dong5053/220717510273