교착상태 #1 - deadlock, resource types, deadlock model

Deadlock의 개념

Blocked/Asleep state

• 프로세스가 특정 이벤트를 기다리는 상태
• 프로세스가 필요한 자원을 기다리는 상태

Deadlock state

• 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
  • 프로세스가 deadlock 상태에 있음
• 시스템 내에 deadlock에 빠진 프로세스가 있는 경우
  • 시스템이 deadlock 상태에 있음

Deadlock vs Starvation

• asleep 상태 vs ready 상태
• CPU이외의 자원을 기다림 vs CPU 할당을 기다림
• 발생 가능성 X vs 발생 가능성 O

---

자원의 분류

일반적 분류

• Hardware resources vs Software resources

다른 분류 법

• 선점 가능 여부에 따른 분류
• 할당 단위에 따른 분류
• 동시 사용 가능 여부에 따른 분류
• 재사용 가능 여부에 따른 분류

 

선점 가능 여부에 따른 분류

• Preemptible resources
  • 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원
  • Processor(CPU -> context switching( saving, restoring ), memory( swap device ) 등
• Non-preemptible resources
  • 선점 당하면, 이후 진행에 문제가 발생하는 자원
    • Rollback, restart등 특별한 동작이 필요
  • E.g., disk drive 등

 

할당 단위에 따른 분류

• Total allocation resources
  • 자원 전체를 프로세스에게 할당
  • E.g., Processor, disk drive 등
• Partitioned allocation resources
  • 하나의 자원을 여로 조각으로 나누어, 여러 프로세스들에게 할당
  • E.g., Memory 등

 

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

• Exclusive allocation resources
  • 한 순간에 한 프로세스만 사용 가능한 자원
  • E.g., Processor, memory, disk drive 등
• Shared allocation resource
  • 여러 프로세스가 동시에 사용 가능한 자원
  • E.g., Program(sw), shared data 등

 

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

• SR (Serially-reusable Resources)
  • 시스템 내에 항상 존재 하는 자원
  • 사용이 끝나면, 다른 프로세스가 사용 가능
  • E.g., Processor, memory, disk drive, program 등
• CR (Consumable Resources)
  • 한 프로세스가 사용한 후에 사라지는 자원
  • E.g., signal, message 등

---

Deadlock과 자원의 종류

Deadlock을 발생시킬 수 있는 자원의 형태

• Non-preemptible resources
  -> 자원을 할당 받으면 끝까지 수행하기 때문
• Exclusive allocation resources
• Serially reusable resources
• 할당 단위는 영향을 미치지 않음

CR을 대상으로 하는 Deadlock model

• 너무 복잡하므로 제외

---

Deadlock 발생의 예

• 2개의 프로세스 (P1, P2)
• 2개의 자원 (R1, R2)

• P1이 R2 요청, P2가 R1 요청
• P1이 R1 요청, P2가 R2 요청
• 서로가 가지고 있는 자원을 요청하고 있다 -> 발생가능성이 없다.

---

Deadlock Model (표현법)

Graph Model

• Node
  • 프로세스 노드(P1, P2), 자원 노드(R1, R2)
• Edge
  • Rj -> Pi : 자원 Rj 이 프로세스 Pi 에 할당 됨
  • Pi -> Rj : 프로세스 Pi 가 자원 Rj을 요청 (대기 중)

 

State Transition Model

예제

• 2개의 프로세스와 A type의 자원 2개(unit) 존재
• 프로세스는 한번에 자원 하나만 요청/반납 가능

State

• 프로세스가 하나 일 경우의 state 

• 프로세스가 2개 일 경우의 state 

---

Deadlock 발생 필요 조건

자원의 특성

• Exclusive use of resources
• Non-preemptible resources

프로세스의 특성

• Hold and wait (Partial allocation)
  • 자원을 하나 hold하고 다른 자원 요청
• Circular wait

---

강의

www.youtube.com/watch?v=xvoEsy2zJnc&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=19

www.youtube.com/watch?v=czjtYkjhtgo&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=20