[OS] 7. 교착 상태 (Deadlock) 개념, 자원의 분류, 모델, 발생조건

각 방향의 자동차들은 서로 다른 곳으로 이동하고 싶지만 꽉 막혀 있기에 이동하지 못한다. 

프로세스도 마찬가지로 자신들이 원하는 자원을 가져가고싶은데 그러지 못하는 상태가 된다.

이를 Deadlock (교착상태)이(가) 된다. 

Deadlock의 개념

• Blocked state
  • 프로세스가 특정 이벤트를 기다리는 상태
• Asleep state
  • 프로세스가 필요한 자원을 기다리는 상태
• Deadlock state
  
  • 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우 => 프로세스가 deadlock 상태에 있음
  • (원하는 자원을 받지 못하는데 계속 기다리기 때문)
  • 시스템 내에 deadlock 에 빠진 프로세스가 있는 경우 => 시스템이 deadlock 상태에 있음

앞서 프로세스 스케줄링 알고리즘(5단원)에서 배웠듯이 deadlock는 starvation과 유사하게 보인다. 

이 둘의 차이점은 무엇인가?

• deadlock은 asleep상태에 존재한다.
• deadlock은 asleep에서 자원과 이벤트를 기다리는데 일어날 가능성이 적은 것을 의미한다.
• starvation은 프로세스를 기다린다 (CPU를 기다림)
• starvation은 발생할 수 있는 이벤트인데 운이 없어서 또는 우선순위에 밀려서 계속 기다림

즉, 발생 가능성과 기다리는 자원도 차이가 있으며 어느곳에 존재하는지도 구분된다. 

---

자원의 분류

deadlock은 자원과 밀접한 관계를 가지고 있다. 

일반적 분류

Hardware resources vs Software resources

다른 분류 법

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

 

선점 가능 여부에 따른 분류

Preemptible resources

• 다른 누군가가 내가 쓰고 있는 CPU를 뺐어 갈 수 있음.
• 선점 당한 후 , 돌아와도 문제가 발생하지 않는 자원
• Processor, memory 등
• Process: CPU(contexted switch), 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 등
• word, 한글 등을 여러 창을 띄울 수 있음 => 프로그램은 하나인데 창을 여러개 띄우는 것은 프로그램을 여러 프로세서가 동시에 쓸 수 있다는 뜻.

 

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

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 => 너무 복잡함. SR만 가지고 deadlock을 고려해보자

 

Deadlock 발생의 예

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

이 상황을 순서대로 표현하면

1. P1이 R2(자원 2번)을 요청
2. P2이 R1을 요청 (자원은 없음)
3. 이 상태에서 P1이 R1을 요청 (이 상태에서 DeadLock이라고 말하기 어려움: P2가 R1을 반납 하면 됨)
4. P2이 R2를 요청함 (이 때 발생하지 않는 이벤트 생성.. => deadlock이라고 한다)

 

Deadlock Model (표현법)

Graph Model

Node

• 프로세스 노드 (P1, P2), 자원 노드 (R1,

Edge

• R j -> P i : 자원 R j 이 프로세스 P i 에 할당 됨
• P i -> R j : 프로세스 P i 가 자원 R j 을 요청 대기 중

서로가 자원을 요청하는 상태 (cycle이 생성됨..)

 

State Transition Model

예제

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

State

of R units allocated : 현재 자원 수

프로세스가 한개라면 위와 같이 5개 state로 분류되지만 두개라면 5x5 = 25개 state를 가지게 된다.

한번에 자원 1개를 요청 또는 1개를 반납하게 되어 위의 그래프로 나타낼 수 있음

 

S01 (프로세서1번 state, 프로세서 2번 state)

화살표 위의 숫자는 해당 프로세스에 의해 상태가 변화하는 것을 나타냄

deadlock은 S33에서 발견됨. 

 

Deadlock 발생 필요 조건

자원의 특성

• Exclusive use of resources (자원의 배타적 사용)
• Non preemptible resources (비선점 자원)

프로세스의 특성

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

위의 4가지 조건이 전부 만족하면 Deadlock이 발생하게 됨.

 

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---