운영체제 - 반효경 #7 Deadlock

# 7-1 Deadlock 1

교착상태

• 데드락 = 교착상태 = 더 이상 방법이 없는 상황

 

The Deadlock Problem

• Request = 자원 요청
• Allocate = 자원 획득
• Use = 자원 사용
• Release = 자원 반납

 

Deadlock 발생의 4가지 조건

• 4가지 조건 모두 만족해야 함

• Mutual exclusion = 상호 배제 = 독점
• No preemptive = 비선점 = 빼앗기지 않음
• Hold and wait = 보유대기 = 자발적으로 가지고 있음
• Circular wait

 

Resource-Allocation Graph

• P = process
• R = resource
• 자원 ➡️ 프로세스 화살표 = 이 자원이 이 프로세스에 속해있다, 이 프로세스가 이 자원을 가지고 있다
• 프로세스 ➡️ 자원 화살표 = 이 프로세스가 이 자원을 요청한 상태(아직 획득 못한)
• 사각형 안의 점 = 자원의 인스턴스, 이 중 어느 것을 사용해도 상관 없음

데드락이냐 아니냐 판별법

• 우선 화살표를 따라가보자
• 사이클이 있으면(화살표가 반대로 되돌아갈 수도 있으면) 데드락

첫 번째 그래프

• 자원이 2개가 있더라도, 사이클이 2개 만들어지면서,
• 마지막 p3 이 자원을 요청할 때, 사용할 수 있는 자원이 없는 상황이 되어버리니 데드락

두 번째 그래프

• 데드락 아님
• 자원 2개가 할당되어 있더라도 각 프로세스에 잘 분배되고 있음

 

Deadlock의 처리 방법

• 위로 갈수록 강한 처리 방법

• 데드락은 빈번히 발생하는 이벤트가 아님
• 그렇기에 미연에 방지하기 위해 많은 오버헤드를 들이는 것은 현재 시스템에서 비효율적이기에 일단 내버려두기도 함

 

Deadlock Prevention

• 데드락 4가지 조건 중 어느 하나를 원천적으로 차단
• 생기지 않을 문제를 미리 막는 것이기에 단점도 있음

Mutual exclusion

• 한 번에 하나만 쓸 수 있는 조건이라면 우리가 배제할 수 있는 조건은 아님

Hold and wait

• 자원을 모두 가지고 있거나
• 자원이 필요할 때 가지고 있던 자원들 모두 자진 반납하거나

No preemption

• 자원을 빼앗을 수 있으면 데드락 발생하지 않음

Circular wait

• 꼬리에 꼬리를 무는
• 자원에 순서를 매기자
• 낮은 번호를 순차적으로 획득해야 높은 자원을 획득할 수 있는 그런 방식

 

Deadlock Avoidance

• 데드락 발생 가능성이 있으면 여분의 자원이 있어도 할당해주지 않음

• 프로세스가 시작될 때 본인이 평생 사용할 자원들을 미리 declare 하고, 이를 통해 데드락을 피해감
• Safe 상태에서 가용 자원만으로 충족되지 않는 상태임에도 자원을 줬다고 해서(unsafe 상태) 데드락인 건 아님
• 모든 프로세스가 최대 자원을 요청하고 내가 가진 자원을 반납하지 않아, 가용 자원이 없는 상태일 때 데드락

 

Resource Allocation Graph Algorithm

• 자원 당 인스턴스가 하나뿐일 때 데드락 피하는 방법

첫 번째 그림

• 자원 ➡️ 프로세스 실선 화살표 = 자원이 이 프로세스에 할당된 상태
• 프로세스 ➡️ 자원 실선 화살표 = 프로세스가 해당 자원을 요청했는데 아직 할당 못 받은 상태
• 프로세스 ➡️ 자원 점선 화살표 = 해당 프로세스가 평생에 적어도 한 번은 해당 자원을 사용할 일이 있다

두 번째 그림

• P2 도 자원을 가지고 있다고 가정
• 여기서는 p1 에게 r2 줘도 사이클 생성 안 됨

세 번째 그림

• 최악의 상황을 가정
• 데드락 아님

 

Example of Banker's Algorithm

Banker’s algorithm

• 자원 당 인스턴스가 여러 개일 때 데드락을 막는 방법
• 최악의 경우를 가정하고, 평생 동안 데드락 가능성이 있는 조건에 걸리면 그 조건은 할당 안 하고 가용자원이 넉넉해질 때까지 대기시킴
• 최대 요청 인스턴스 수가 가용 자원 수로 충족되지 않으면 무조건 막아버리는 것

인스턴스 개수

• A : 10개
• B : 5개
• C : 7개

• Allocation = 지금 할당된 자원
• Max = 최대 요청 가능량
• (전체 자원 인스턴스 – 할당된 자원 인스턴스) = 가용 가능한 인스턴스 수 = available

• Need = 추가로 요청할 수 있는 양
• (Max – allocation)

P1 기준

• 추가할 수 있는 양이 1 / 2 / 2 인데
• 현재 가용 가능한 자원이 3 / 3 / 2 임
• 즉, 가용 가능한 자원만으로 max 를 채울 수 있음

P0 기준

• 추가할 수 있는 양이 7 / 4 / 3
• 현재 가용 가능한 자원이 3 / 3 / 2 임
• = 추가할 수 있는 양이 현재 사용 가능한 자원들만으론 충족 불가한 상태
• 이 친구에게 줄 자원이 있긴 하지만 안 주겠지
• 만약 이 친구가 최대 요청을 해버리면 현재 가용 자원만으론 처리할 수 없으니 기다리게 함
• 다른 프로세스들이 가용 자원으로 처리 다 끝내면 그들이 가지고 있던 자원들을 반납하니, 가용 자원이 늘어남
• 그때 이 친구의 최대 요청 작업이 가능하게 됨
• Ex) p3 이 가지고 있던 자원 반납 시 가용 자원 수가 늘어나고 ➡️ p0 요청 수행 가능

• 근데 이건 되게 비효율적이야
• 자원이 남아돌아도 안 주는 거니까
• 데드락 자체가 사실 잘 발생하지 않아

 

P1 request

• 최대 요청 수 <= 가용 자원 수
• Need <= Available

---

# 7-2 Deadlock 2

Deadlock Detection and Recovery

• 자원 당 인스턴스가 1개만 있는 경우

• 자원 할당 그래프(Resource-allocation graph)
• 사이클이 있으면 데드락

Corresponding wait-for graph

• 왼쪽 그래프의 자원들을 모두 뺀 버전 + p4 에서 p1 로 가는 화살표 추가
• = 지금 p4 는 p1 이 가진 자원을 할당받고자 기다리고 있다는 의미
• 이렇게 자원을 빼고 프로세스끼리 봤을 때 사이클이 이루어지는지 확인하면 됨
• 그럼 이런 사이클을 찾는 오버헤드는 얼마나 될까?
  • 프로세스 n 개 존재
  • 사이클을 알려면 화살표를 따라가면 됨
  • N 개 프로세스에서 최대 화살표 개수는 ( n x n – 1 ) 임 = order of n 제곱의 시간이 걸림(첫 슬라이드 가장 마지막줄)

• 자원 당 여러 개의 인스턴스가 있는 경우

데드락이 있는지 확인하려면 보수적 접근이 아닌, 낙관적 접근 필요

• 가용 자원이 없는 상태이지만 프로세스마다 보유한 자원을 반납할 것이라 가정하자
• ➡️ 그렇게 축적된 자원을 가용할 수 있는 자원이라 판단하고, 각 프로세스가 끝나면 반납될 개수를 파악해 각 프로세스마다의 인스턴스 요청을 허용해주는 것

프로세스의 원칙

• 프로세스는 본인이 가진 자원은 가지고 있으면서 내가 요청한 자원이 충족될 때까지, 내가 가진 자원을 내놓지 않는 것
• 그럼 요청을 받아들일 수 없는 상황이 발생할 수 있고, 이게 데드락임

Process termination

• 데드락에 연루된 모든 프로세스를 한 번에 죽이기
• 프로세스 종료

Resource preemption

• 데드락에 연루된 프로세스를 하나씩 죽이기
• 프로세스 관련 자원 뺏기

• 꼭 비용 최소화에만 집중하지는 말자

 

Deadlock Ignorance