[운영체제] 공룡책 - 데드락 (Deadlock) 요약

데드락

• 어느 프로세스도 자기 일을 할 수 없는 상태
• 다른 프로세스가 종료되기를 기다리며 계속 기다리는 상태
• blocked state: 프로세스가 특정 이벤트를 기다리는 상태
• asleep state: 프로세스가 필요한 자원을 기다리는 상태
• deadlock state
  • 프로세스가 발생가능성이 없는 이벤트를 기다리는 경우

• 대기 상태와 교착 상태 비교
  • 대기상태와 교착 상태가 발생하는 위치와 종류가 다르다
  • 기아 상태의 경우 CPU를 운 나쁘게 계속 할당 못받은 것 (추후에 받을 수도 있음)
  • 교착 상태는 앞으로도 해결될 가능성이 없다

•  

선점 

• 선점 자원: 선점 당한 후 다시 돌아와도 문제 없는 자원: 프로세서, 메모리
• 비선점 자원: 선점 당하면 진행에 문제가 생기는 자원: 디스크 드라이브 (롤백, restart 필요)

Deadlock 발생 조건

• 상호 배제 Mutual Exclusion: 여러 프로세스 중 하나만 임계 구역(자원)에 접근 가능
• 비선점 자원 : 다른 프로세스가 사용 중인 자원을 뺏을 수 없다
• 점유와 대기 (하나의 자원을 hold한 상태로 다른 자원을 요청할 때)
• 순환 대기: 자원을 하나씩 점유한 상태로 서로의 자원을 요청하는 경우

위 조건 중 하나라도 만족하지 않으면 교착 상태는 발생하지 않는다

 

Deadlock Prevention 예방 방법

•  위 발생 조건 중 하나를 제거하는 방법
• 데드락이 절대 발생하지 않도록 한다

• 상호 배제: 상호 배제 조건 제거 (현실적 불가능)
• 비선점 :  선점 허용함 (현실적 불가능, 기존에 가지고 있던 자원을 모두 반납하고 작업 취소한 뒤 처음부터 다시 시작) => 자원 낭비
• 점유 대기: 필요한 자원을 모두 할당 => 필요하지 않은 자원도 가지고 있음 => 자원 낭비, 무한 대기 현상 발생
• 순환 대기: 자원들에게 순서를 부여 => 순서의 증가 방향으로만 자원 요청 가능 => 자원 낭비

• 비현실적임, 심각한 자원 낭비

Deadlock Avoidance 회피 방법

• 시스템 상태 계속 감시
• 데드락 상태가 될가능성이 있는 자원 할당 요청 보류
• 시스템을 항상 safe state(모든 프로세스가 정상적으로 종료 가능한 상태)로 유지
• 프로세스 수, 자원 종류 및 수, 프로세스가 요구하는 자원 및 최대 수량 알고있고 프로세스는 자원을 사용한 후 반드시 반납한다는 가정 하 에서만 사용가능해서 실용적이지 않음
• 다익스트라의 알고리즘: 은행 알고리즘 (자원이 한 가지라고 가정)
• 하버만의 알고리즘 (다익스트라 알고리즘 확장, 여러 종류의 자원 고려)
• 데드락 발생 막을 수 있다. 
• 항상 시스템 감시 => 오버헤드 크다
• safe state 유지 위해 사용되지 않는 자원 존재 => 낮은 자원 활용도
• 실용적이지 않음

Deadlock Detection

• 데드락 방지 위한 사전 작업 하지 않는다
• 일단 발생하면 해결하자 
• Resource Allocation Graph (RAG)를 사용해서 데드락이 발생했는지 확인한다.
  • 데드락 검출하기 위해서 사용한다
  • 프로세스와 자원의 할당 관계를 보고 데드락이 발생했다면 제거할 수 있는지 본다 (Graph Reduction)
  • RAG그래프에서 모든 edge를 제거할 수 있다면 데드락에 빠진 프로세스가 없다
  • 지울 수 없는 edge가 있다면 하나 이상의 프로세스가 deadlock 상태이다
• 오버헤드 높다 => 검사 주기, 노드 개수에 영향을 받는다

Deadlock avoidance vs Deadlock detection

회피

• 최악의 경우 생각
• 데드락이 절대 발생하지 않도록 한다

감지

• 최선의 경우 고려
• 데드락 발생시 recovery 과정 필요

Deadlock Recovery

• 프로세스 종료
  • 데드락 상태의 프로세스를 종료시킨다 (우선순위, 종류, 총 수행시간, 남은 수행시간, 종료비용 고려)
  • 강제 종료된 프로세스는 이후 재시작된다
• 자원 선점
  • 데드락 상태 해결하기 위해서 선점할 자원 선택
  • 해당 자원을 선점한 프로세스에서 자원을 뺏는다
  • 자원 뺏긴 프로세스는 강제 종료된다
• 체크 포인트 restart 방법
  • 롤백을 위해서 사용. 프로세스 강제 종료 후 가장 최근의 checkpoint에서 재시작한다

 

 

 

 

 

•