7. 교착 상태 (1) - Deadlock and Resource types

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

 

 

 

 

Deadlock : 어느 프로세스도 자신이 원하는 자원을 가져갈 수 없는(자신이 원하는 작업을 수행할 수 없는) 상태

 

 

Deadlock의 개념

 

• Blocked / Asleep state
  • 프로세스가 특정 이벤트를 기다리는 상태
  • 프로세스가 필요한 자원(프로세서가 아닌 다른 자원)을 기다리는 상태
• Deadlock state
  • 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
    • 프로세스가 deadlock 상태에 있음
  • 시스템 내에 deadlock에 빠진 프로세스가 있는 경우
    • 시스템이 deadlock 상태에 있음
• Deadlock vs Starvation

 

 

• Deadlock
  • asleep/blocked 상태에서 존재한다.
  • 가능성이 0 인 이벤트를 기다림
  • CPU가 아닌 자원을 기다림

 

• Starvation
  • ready 상태에서 존재한다.
  • 가능성이 0은 아니지만 운이 나빠서 혹은 우선 순위에서 밀려서 계속 기다림
  • CPU 자원을 기다림

 

자원의 분류

Deadlock은 자원과 굉장히 밀접한 관계를 가진다.

 

• 일반적 분류
  • Hardware resources vs Software resources
• 다른 분류법 : Deadlock의 관점에서 자원을 바라봤을 때 다음과 같이 분류할 수 있다.
  • 선점 가능 여부에 따른 분류
  • 할당 단위에 따른 분류
  • 동시 사용 가능 여부에 따른 분류
  • 재사용 가능 여부에 따른 분류

 

 

선점 가능 여부에 따른 분류

 

• Preemptible resources
  • 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원
  • 프로세서(Context Switching 덕분), 메모리(Swap device) 등
• Non-Preemptible resources
  • 선점 당하면, 이후 진행에 문제가 발생하는 자원
    • Rollback, restart 등 특별한 동작이 필요
  • disk drive

 

 

할당 단위에 따른 분류

 

• Total allocation resources
  • 자원 전체를 프로세스에게 할당
  • 프로세서, 디스크 드라이브 등
• Partitioned allocation resources
  • 하나의 자원을 여러 조각으로 나누어, 여러 프로세스들에게 할당
  • 메모리 등

 

 

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

 

• Exclusive allocation resources
  • 한 순간에 한 프로세스만 사용 가능한 자원
  • 프로세서, 메모리(본인에게 할당된 영역), 디스크 드라이브 등
• Shared allocation resources
  • 여러 프로세스가 동시에 사용 가능한 자원
  • 프로그램(sw), shared data 등

 

 

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

 

• SR (Serially-Reusable Resources)
  • 시스템 내에 항상 존재하는 자원
  • 사용이 끝나면, 다른 프로세스가 사용 가능
  • 프로세서, 메모리, 디스크 드라이브, 프로그램 등
• CR (Consumable Resources)
  • 한 프로세스가 사용한 후에 사라지는 자원
  • Signal, message 등

 

 

Deadlock과 자원의 종류

 

• Deadlock 을 발생시킬 수 있는 자원의 형태
  • 선점 가능 여부 : Non-preemptive resources
  • 동시 사용 가능 여부 : Exclusive allocation resources
  • 재사용 가능 여부 : Serially reusable resources
  • 할당 단위는 영향을 미치지 않는다.
• CR을 대상으로 하는 Deadlock 모델
  • 너무 복잡함