[SW_Jungle] Deadlock

Deadlock state : 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우, 시스템내에 deadlock에 빠진 프로세스가 있는 경우

starvation과 deadlock

starvation은 cpu를 기다리면서 ready상태에 존재하게 되는데 우선순위가 오지 않아 대기하고 있는 상태이고 deadlock은 sleep상태에 존재하며 자원이나 이벤트를 기다리는데 이 가능성이 제로라 일어나지 않는 상황을 가리킨다.

데드락은 자원과 밀접한 관계를 가진다. 자원은 일반적으로는 hardware resource 와 software resourec로 나뉘는데 데드락의 관점에서는 이와 다르게 자원을 분류 할 수 있다.

데드락 관점에서 분류한 자원

• 선점 가능 여부에 따른 분류
  • 선점 당한 후 돌아와도 문제가 발생하지 않는 자원 ex> processor(context switch -> save, restore), memory(swap-device)
  • 선점 당하면 이후 문제가 발생하는 자원, rollback 이나 restart등 특별한 동작이 필요 ex> disk drive
• 할당 단위에 따른 분류
  • total allocation resourece : 자원 전체를 프로세스에게 할당 ex> processor, disk drive
  • partitioned allocation resourece : 하나의 자원을 여러 조각으로 나누어, 여러개의 프로세스들에게 할당 ex> memory
• 동시사용 가능 여부에 따른 분류
  • exclusive allocation resourece : 한순간에 한 프로세스만 사용 가능한 자원 ex> memory
  • shared allocation resoure : 여러 프로세스가 동시에 사용 가능한 지원 ex> program(source code), 실행파일
• 재사용 가능 여부에 따른 분류
  • SR(serially-resuable resoure) : 시스템 내에 항상 존재하는 자원, 사용이 끝나면 다른프로세스가 사용 가능 ex> processor, memory, disk drive, program
  • CR(consumable resource) : 한 프로세스가 사용한 후에 사라지는 자원 ex> siganl, message

Deadlock을 발생시킬 수 있는 자원의 종류

• non-preemptible resource
• exclusive allocation resource
• serially resuable resource
• consumable resource도 데드락을 유발할 수 있으나 너무 복잡해서 고려하지 않음

Deadlock 발생 필요조건(4가지 모두 성립해야 데드락 발생)

• exclusive use of resource (자원의 특성)
• non-preemptible resourece (자원의 특성)
• hold and wait(partial allocation) : 자원을 하나 hold 하고 다른 자원요청 (프로세스의 특성)
• circular wait (프로세스의 특성)

이 4가지 방법 중 하나만 없애주면 데드락이 해결된다.

Deadlock prevention

1. 모든 자원을 공유 허용 (현실적으로 불가능)
2. 모든 자원에 대해 선점 허용 (현실적으로 불가능), 유사한방법으로 구현 가능하나 자원낭비가 매우 심해서 비효율
3. 필요한 자원 한번에 모두 할당 : hold and wait 조건 제거, 무한 대기 발생 가능
4. 자원들에게 순서 부여 : circular wait 조건 제거, 프로세스는 순서의 증가 방향으로만 자원 요청 가능, 자원 낭비 발생

Deadlock solution

• dealock preventation(교착상태 예방)
• deadlock avoidance(교차상태 회피)
• deadlock detection and deadlock recovery(교착상태 탐지 및 복구)

Deadlock avoidance

• 시스템의 상태를 계속 감시
• deadlock 상태가 될 가능성이 있는 자원 할당 요청 보류
• 시스템을 항상 safe state(모든 프로세스가 정상적으로 종료 가능한 상태로 safe sequence가 존재)로 유지

Deadlock detecion

• deadlock 방지를 위한 사전 작업을 하지 않고 주기적으로 deadlock 발생 확인(시스템이 데드락 상태인지, 어떤 프로세스가 데드락 상태인지)
• resource allocation graph(RAG) 사용

ref)
1. https://www.youtube.com/watch?v=xvoEsy2zJnc&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=19