Deadlock 개념

• 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
  
• 기아상태는 ready상태에 있고 언젠가는 발생
• 데드락은 asleep상태에서 발생 가능성이 없다.

선점 가능 여부에 따른 분류

preemptible resources

• 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원

Non-preemptible resources(데드락)

• 선점 당하면 이후 진행에 문제가 발생하는 자원

할당 단위에 따른 분류

Total allocation resources

• 자원 전체를 프로세스에게 할당
• processor, disk

Partitioned allocation resources

• 하나의 자원을 여러 조각으로 나누어, 여러 프로세스들에게 할당
• memory

동시 사용 가능 여부에 따른 분류

Exclusive allocation resources(데드락)

• 한 순간에 한 프로세스만 사용 가능한 자원
• processor, disk

shared allocation resource

• 여러 프로세스가 동시에 사용 가능한 자원
• sw

재사용 가능 여부에 따른 분류

SR(데드락)

• 시스템 내에 항상 존재하는 자원

CR

• 한 프로세스 사용하고 사라지는 자원

Deadlock 발생의 예

• 프로세스2개와 자원2개가 있다.
• 4번에서 서로 가지고 있는 것을 요청하고 있다.

Deadlock 발생조건

• Exclusive use of resources
  • 한 순간에 한 프로세스만 사용 가능한 자원
• Non-preemptible resources
  • 선점 당하면 이후 진행에 문제가 생기는 자원
• Hold and wait(자원 하나를 hold하고 다른 자원 요청)
• Circular wait
  -> 이중 하나만 예방하면 된다.

Deadlock 해결방법

• Deadlock Prevention (교착상태 예방)
• Deadlock avoidance method (교착상태 회피)
• Deadlock detection and deadlock recovery methods(교착상태 탐지 및 복구)

Deadlcok Prevention

1.모든 자원 공유 허용

• Exclusive use of resources조건 제거
• 불가능하다

2.모든 자원 대해 선점 허용

• 현실적으로 불가능
• 유사한 방법
  • 할당 받을 수 없는 자원을 요청한 경우, 기존 가지고 있던 자원을 모두 반납하고 작업 취소
  • 심각한 자원 낭비 발생

3.필요 자원 한번에 모두 할당

• hold and wait 조건 제거
• 자원 낭비 발생 -> 필요하지 않은 순간에도 가지고 있음
• 끝날 때 동안 반납이 없으므로 무한 대기 발생 가능

4.Circular wait 조건 제거

• totally allocation 일반화한 방법
• 순서를 부여하고 순서의 증가 방향으로만 자원 요청 가능
• 만약 뒤에 순서를 지금당장 할당 받을 수 있는데 순서대로 진행하기에 대기해야한다.
• 자원 낭비 발생

정리

• 4개의 deadlock 조건 하나 제거
• deadlock 발생하지 않음
• 자원낭비가 된다.

Deadlock avoidance

• 시스템의 상태를 계속 감시(4개의 상태 중 하나를 제거를 못하니)
• deadlock의 가능성이 있을 때 피해간다.
• 시스템을 항상 safe state로 유지

Safe state

• 모든 프로세스가 정상적 종료 가능한 상태
• Safe sequence가 존재
  • Deadlock상태가 되지 않을 수 있음을 보장

Unsafe state

• Deadlock 상태가 될 가능성이 있다.

가정

• 프로세스의 수가 고정됨
• 자원의 종류와 수가 고정됨
• 프로세스가 요구하는 자원 및 최대 수량을 알고 있다.
• 프로세스는 자원을 사용 후 반드시 반납한다.

banker's algorithm

• 가정
  • 한 종류의 자원이 여러개
• 시스템을 항상 safe state로 유지

• 10개의 resource와 3개의 processes
• 최대 필요수와 현재 할당수 그리고 필요수가 있다(max - alloc = need)
• 다 믿을 수 있는 관계여서 돈을 빌려주면 바로 갚는다는 가정
  • 현재 가능 수가 2개이고
  • 실행 종료 순서가 P1 -> P3 -> P2(Safe sequence)
    현재 상태에서 안전 순서가 하나 이상 존재하면 안전 상태이다.

• 현재 가능 수가 2개이다. safe sequence가 없으므로

• safe sequence의 여부를 확인하면 된다

Deadlock detection

• Deadlock 방지를 위한 사전 작업을 하지 않음
• 주지적으로 deadlock 발생 확인

Avoidance vs Detection

avoidance

• 최악의 경우를 생각
  • 앞으로 일어날 일을 고려
• Deadlock이 발생 하지 않음

detection

• 최선의 경우를 생각
  • 현재 상태만 고려
• Deadlock 발생 시 Recovery과정 필요

Dealock Recovery

• Deadlock을 검출 한 후 해결 하는 과정

Deadlock Recovery methods

Process termination

• Deadlock 상태에 있는 프로세스를 종료 시킴
• 강제 종료 된 프로세스는 이후 재시작 됨
• Deadlock 상태인 프로세스 중 일부 종료
• 비용이 적은 것 부터 종료
  -> 불필요한 프로세스들이 종료 될 가능성이 높음
• 최고의 선택
  -> 최소 비용으로 dealock상태를 해소 할 수 있는 process선택

Resource Preemption

• Deadlock 상태 해결 위해 선점할 자원 선택
• 선정 된 자원을 가지고 있는 프로세스에서 자원을 빼앗음
  • 자원을 빼앗긴 프로세스는 강제 종료됨
  • Deadlock 상태가 아닌 프로세스가 종료 될 수도 있다.
• checkpoint-restart 특정지점 마다 저장하고 그 부분에서 재시작(롤백)

출처 https://www.youtube.com/watch?v=xvoEsy2zJnc&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=20