1. 교착상태란 무엇인가?
💬 Remind : Blocked(Asleep) 상태
➡️ 프로세스가 Running을 하다가, System Call을 해서 스스로 CPU를 내놓고 Asleep을 하는 상태
프로세스는 특정 이벤트(particular Event)를 기다리고 있다.
특정 이벤트란, 프로세스가 요청한 자원의 할당을 기다리고 있는 것이다!
Ex) 입출력이 끝났다는 시그널을 기다리고 있는 것
Ex) semaphore의 lock이 풀렸다는 시그널을 기다리고 있는 것
📌 Deadlock State
어떠한 프로세스가 "미래에 절대 발생할 발생하지 않을" 특정 이벤트를 기다리고 있는 상태이다.
이 경우, asleep 상태에 있는 프로세스는 그 이벤트는 발생하지 않을 것이므로 깨어나지 못한다.
➡️ 프로세스가 절대 일어나지 않을 이벤트를 기다리고 있다면 그 프로세스는 'deadlock state(교착 상태)'에 있다고 한다.
➡️ 교착 상태에 걸린 프로세스가 시스템에 하나 이상 있다면, 그 시스템은 '교착 상태에 놓였다'고 한다.
(프로세스 200개 중 1개라도 교착상태에 걸렸더라도 그 시스템은 '교착 상태에 놓였다'고 한다. 나머지 199개의 프로세스도 굉장히 빠른 속도로 교착 상태에 놓일 가능성이 높아지기 때문이다!)
📌 Deadlock vs Indefinite Postpone
Indefinite Postpone은 자원을 할당받지 못하고 계속 지연되는 상태를 의미한다. 가능성이 없는 것은 아니지만 리소스를 받는 데 시간이 오래 걸리고 지연되는 것이다.
반면, Deadlock은 자원 할당을 기다리는 asleep 상태인데, 자원 할당의 가능성이 아예 없는 것(transition impossible)이다.
2. 자원의 종류
1) Preemptible 🆚 Non-preemptible
📌 선점형 자원
한 프로세스가 다른 프로세스로부터 자원을 선점당하여도 큰 문제가 없는 자원
CPU(Processor), Memory 등📌 비선점형 자원
선점을 당한 프로세스가 rollback/restart(처음부터 다시 시작해야 하는) 등의 심각한 문제로 인해 지속할 수 없는 경우
Magnetic Tape Drive 등
2) Total 🆚 Partitioned Allocation
📌 Total Allocation
자원을 할당할 때 한꺼번에 다 할당해야 하는 자원
CPU, Magnetic Tape Drive 등
CPU는 물리적으로 한번에 한 프로세스만 사용해야 한다.📌 Partitioned Allocation
자원이 여러개의 덩어리로 나누어서 할당이 가능한 자원
Memory
3) Exclusive 🆚 Shared Allocation
📌 Exclusive Allocation
한번 할당하면 한 프로세스 혼자서만 사용해야 하는 것
CPU, Memory
Memory는 각 공간을 나누어서 사용하지만, 그 공간은 한 프로세스만 사용해야 하며 exclusive하다.📌 Shared Allocation Resources
동시에 여러 프로세스가 이용 가능한 자원
소프트웨어 자원. Shared Allocation Resource의 예시에는 하드웨어 자원은 거의 없고, 대부분 소프트웨어 자원이다.
Text Editor, 컴파일러 등 여러 프로세스가 동시에 사용할 수 있다.
4) SR(Serially Reusable) 🆚 CR(Consumable)
📌 SR(Serially Reusable)
시스템에 영원하게 존재하는 자원.
자원을 사용 후 반납한다.
대부분의 자원이 그러하다.📌CR(Consumable)
사용 후에는 사라져버리는 자원
Signal, Message.
Message 등은 프로세스에 읽고 쓰고 난 이후에는 사라져 버린다. 인터럽트 시그널도 발생 이후 사라져 버린다.
3. 교착상태의 예시
📌 Example
두 개의 프로세스 p1, p2와 두 개의 리소스 r1, r2가 있다고 생각해 보자.
✔️ p1, p2의 Program Code는 각각 다음과 같이 쓰여 있다.
▪️ p1은 r1 요청 => r2 요청 => r2 반납 => r1 반납
▪️ p2는 r2 요청 => r1 요청 => r2 반납 => r1 반납
✔️ p1은 r1을 사용 중이고, p2는 r2 할당 받아 사용중인데
p1은 r2를 요청하여 sleep 상태에 들어가고, p2는 r1을 요청하고 sleep한 상태
= 두 프로세스 모두 깨어날 가능성이 없는 Deadlock 상태
📌 그래프 모델로 나타내기
노드(Node) : 프로세스 노드 P와 자원 노드 R
간선(Edge)
R -> P : 할당된 간선
P -> R : 요청 간선 (요청 후 Sleep 중인 상태)
📌 Example : 2 by 2 system
두개의 프로세스와 두 개의 리소스가 있다면, 각 프로세스의 가능한 상태는 다음과 같다.
State 0 = 한 프로세스가 어떠한 자원도 요청하지 않은 상태
State 1 = 한 프로세스가 어떠한 자원을 요청하고 할당 받지는 못한 상태
State 2 = 한 프로세스가 어떠한 자원을 할당 받고, 요청 상태는 아닌 상태
State 3 = 한 프로세스가 어떠한 자원을 할당 받고, 요청도 있는 상태
State 4 = 한 프로세스가 두 자원을 모두 할당 받고, 요청은 없는 상태
📌 System State Transition Diagram 으로 나타내기
Sij : i = P1의 상태 & j = P2의 상태
S21 : P1은 2번 상태 & P2는 1번 상태
=> S33에서 교착 상태가 발생한다.
