Chapter 6-2. Concurrency : Deadlock and Starvation

Deadlock Avoidance Logic

시스템의 상태 설명
(global data structure)

• resource[m] : 원래 이 시스템 안에 자원이 각각 몇개씩 있는지?
• avaiavble[m] : 그 자원들 중, 할당 후 남아있는 자원?
• claim[n][m] : 모든 프로세스가, 나는 이 타입의 자원을 몇개까지(최대 동시 요청 가능) 요청할거다 라는 걸 미리 OS에게 미리 얘기해주는 것
• alloc[n][m] : 실제 각각의 프로세스들이 현재 가지고 있는 자원, 어떤 자원이 몇개인지?

Resource allocation algorithm

safe인지 unsafe인지 판단하기 전, 두 가지 조건이 존재한다.
→ 시스템이 safe인지 unsafe한지 판단할 필요도 없는 그런 상황을 말한다.

1. 첫 번째 if 문

if(alloc[i, *] + request[*] > claim[i, *])
	<error>;

프로세스가 현재 가지고 있는 값 + 프로세스가 자원 요청한 값 > 프로세스가 처음 OS에게 요청할거라고 말한 자원의 최대치
⇒ Error → 시스템 실행 불가, 프로그램 종료

* 은 모든 자원을 의미한다.

ex) 자원이 5개일 때, request[*] = [1 2 3 1 1]

alloc[i, *] +  request[*]  > claim[i, *]
[4 4 4 4 4] + [1 2 3 1 1 ] > [5 5 5 5 5]
⇒ Error

2. 두 번째 else-if 문

else if(request[*] > available[*])
	<suspend process>;

프로세스가 요청한 자원 값 > 현재 할당 가능한 자원의 개수
⇒ Suspend , 오류는 아님. 자원을 줄 수 없는 상태임.

3. 마지막 else 문

safe 인지, unsafe 인지를 결정한다.

먼저, 자원을 줬다고 가정한다.

새로운 상태 정의하기

alloc[i, *] = alloc[i, *] + request[*];  // request 만큼 자원을 할당
available[*] = available[*] - request[*]; // request 만큼 자원을 할당

이제 새로운 상태가 safe 인지, unsafe 인지를 결정한다.

• safe 할 경우
  → 자원 할당
• unsafe 할 경우
  → 원래의 상태로 환원시킨 후 프로세스를 Suspend 한다.

---

Deadlock Avoidance Logic(2)

test for safety algorithm
(banker's algorithm)

current available : 자원이 현재 몇개가 있는지? (임시 변수)

rest : 프로세스 집합

1. 모든 프로세스들을 전부 rest 에 넣는다.
2. 하나씩 뺀다. → deadlock 없이 무사히 종료시킬 수 있는, safe 하게 되는 애들
3. rest 공집합 O → 모든 애들이 safe
4. rest 공집합 X → 어떤 프로세스가 종료 불가, unsafe

코드 분석

current available 에 available 값을 복사해서 집어 넣기.
↓
rest에 모든 프로세스 집어 넣기.
↓
while문 돌기
↓
지금 현재 남아 있는 자원을 가지고(available 에 남은 자원을 가지고), 종료할 수 있는 프로세스가 있는지 살펴본다.
↓
Pk를 먼저 볼건데, 조건은 다음과 같다.
요청할 최대 자원 값 - 내가 현재 가지고 있는 자원 값
즉, 앞으로 더 요청할 값이 현재 할당가능한 자원보다 작거나 같은지?

claim[k, *] - alloc[k, *] <= currentavail;
//요청할 최대 자원 값 - 내가 현재 가지고 있는 자원 값 (앞으로 더 요청할 값) <= 현재 할당가능한 자원

자원이 할당 가능하면, Pk가 종료하게되고 Pk가 갖고 있던 자원을 모두 반납하게 될 것이다.

currentavail = currentavil + alloc [k, *];
// Process k가 갖고 있던 자원을 반납한다.

↓
rest 집합에서 Pk를 제외한다.

↓
while 문이 멈추는 때 는 두가지 경우가 있다.

1. 모든 프로세스가 다 빠져나가서 남아있는 프로세스가 없는 경우
2. 더 이상 종료할 수 있는 프로세스가 없는 경우

↓
while문을 빠져나오면 이제 rest 집합이 비었는지를 확인한다.

• rest 공집합 O → 모든 애들이 safe
• rest 공집합 X → 어떤 프로세스가 종료 불가, unsafe

---

Deadlock Avoidance Restrictions

• Maximum resource requirement must be stated in advance.
• There must be a fixed number of resources to allocate.

Banker's algorithm → Not optimal

1. 프로세스가 필요한 최대 자원 요청이 미리 말해져야 한다. (Compiler가 파악 가능하다.)
   • 이때 요청하는 자원은 동시에 필요한 자원이 아닐 수 있다.
   • 지속적으로 필요한 자원이 아닐 수도 있다.
   • 필요하지 않을 수도 있다.
2. Resource 개수가 정해져야 한다. (일정해야 한다.)
   • 자원의 개수가 늘어나는 것은 상관 없지만, 줄어들어선 안된다.

---

Deadlock Detection

Deadlock prevention strategies are very conservative;

• limit access to resources and impose restrictions on processes.

Deadlock detection strategies do the opposite

• Resource requests are granted whenever possible.
• Regularly check for deadlock

Deadlock prevention 이나 Deadlock avoidence 는 굉장히 많은 비용을 요구하는 방식이다.
⇒ 프로세스를 리스타트 시킨다든가, 자원을 줄 수 있는데도 주지 않는다든가, 시작을 지연 시키든가, ... ← 프로세스의 입장에서 불리하다.

↔ Deadlock detection 은 일단 자원을 달라고 하면 준다. (물론 자원이 있는 경우만!)
프로세스의 자원 요청 → 자원이 있으면(available) 할당
대신, 이렇게 요청하는대로 자원을 다 줘버리면 deadlock 이 발생할 수 밖에 없다.
⇒ 주기적으로 데드락을 감지할 것이다!

 

Deadlock 은 90% 이상 프로세스 두 개 사이에서 발생한다.

처음에는 두 프로세스 사이에서 Deadlock 이 발생했지만, 이 프로세스들이 가지고 있는 자원들을 요청한 다른 무고한 프로세스들이 block 되고, 또 프로세스가 가지고 있는 다른 자원을 요청한 프로세스가 block 되는 등의 시스템 전체가 block 되는 상황이 발생될 수 있다.
⇒ 따라서 처음 두 프로세스가 Deadlock 에 걸렸을 때, 재빨리 Deadlock 을 발견해 내어 시스템 전체가 멈추는 상황을 막는다!

---

A Common Detection Algorithm

필요한 것

Use a Allocation matrix and Available vector as previous

Allocation matrix : 원래 필요하다. 원래 OS가 해야하는 많은 일중에, 제일 중요한 일이 자원을 관리하는 일이다. 당연히, 어떤 자원을 어떤 프로세스에게 몇개 주었는지 잘 기록해놔야 한다. 즉, Allocation matrix 는 원래 필요한 것이다.

Available vector : 원래 필요하다. 자원이 몇개 남아있는지 OS가 모르면 안된다.

request matrix Q

request matrix : 각 프로세스들이 어떤 타입의 자원을 몇개 요청하는지?

요청을 했는데 할당 받지 못한 자원이 몇 개인지를 나타낸다.

아직 할당이 안된 자원만 해당 매트릭스에 씌여진다.
할당이 안된 이유?

• 다른 사람이 그 자원을 사용 중이기 때문에
• 자원이 있긴 있는데 OS가 다른일을 하느라 바빠서 자원을 할당해주지 못했기 때문에

Where Qij indicates that an amount of resource j is
requested by process i

Unmark

First ‘un-mark’ all processes that are not deadlocked

• Initially that is all processes

모든 프로세스들을 unmark 하고 프로세스들을 쫙 줄세우고 하나씩 mark 한다.

이 프로세스는 Deadlock이 아니다라고 확신할 수 있을 때 (0%) mark 한다.

• 모든 Process mark O → Safe
• 모든 Process mark X → Unsafe ⇒ Deadlock

---

Deadlock Detection

Request matrix : 각각의 프로세스들이 각각의 자원들을 몇 개씩 Request 했는데, 할당이 안된 자원의 개수

Allocation matrix : 각각의 프로세스들이 할당 받아 가지고 있는 자원의 수

Resource vector : 이 시스템에 있는 원래 자원의 수

Available vector : 할당 가능한 남은 자원의 수

---

Detection Algorithm

1. Mark each process that has a row in the Allocation matrix of all zeros.
   Allocation matrix 가 00000 인 프로세스를 mark 한다.
   ↳ P4 → Deadlock 이 아니라고 확신할 수 있는 이유?
   ↳ 앞의 Deadlock 이 걸리는 4가지 조건 중 Hold-and-Wait 에서 Hold 한 자원이 없기 때문이다.
2. Initialize a temporary vector W to equal the Available vector.
   W 는 Available Vector 이다. (copy)
3. Find an index i such that process i is currently unmarked and the ith row of Q is less than or equal to W.
   mark 가 안된 프로세스 중에서 request 값이 전부 W 값보다 작은 프로세스를 찾는다.
   • i.e. Qik ≤ Wk for 1 ≤ k ≤ m.
     Request ≤ Available ⇒ 할당 가능 O
   • If no such row is found, terminate

mark 가능 → Deadlock X
↳ 왜 자원을 줄 수 있는 것이 Deadlock이 아닌가?
↳ 앞의 Deadlock 이 걸리는 4가지 조건 중 Hold-and-Wait 에서 Wait 한 자원이 없기 때문이다.
→ 자원을 주면, Hold 는 하지만, Wait 는 하지 않는다.

⇒ Request 나 Allocation 이나 둘 중 하나는 0 이 되어야 mark 가 가능하다.

Avoidance Deadlock 과 같이 프로세스를 mark 하고 나면 mark 한 프로세스가 가지고 있던 자원을 다시 Available Vector에 반환한다.

P1
P2
P3 2✅: 00010 → request <= available ⇒ available + allocation 
									= 00001  + 00010
									= 00011
P4 1✅
P5

더 이상 request 를 만족시킬 수 있는 프로세스가 존재하지 않으면, while문을 빠져 나오게 된다.
이때 만약 모든 프로세스가 mark 되어 있다면, safe 이고, 모든 프로세스가 mark 되지 않는다면 unsafe 상태이다.

1. If such a row is found,
   • mark process i and add the corresponding row of the
     allocation matrix to W.
   • i.e. set Wk = Wk + Aik, for 1 ≤ k ≤ m

• Return to step 3.
• A deadlock exists if and only if there are unmarked
  processes at the end
• Each unmarked process is deadlocked.

Q. Mark 가 안된 프로세스가 한 개만 존재할 수 있는가?

존재할 수 없다.
Deadlock 은 최소 두 개의 프로세스가 있어야 발생할 수 있다.

Q. P1과 P2 가 Deadlock 에 걸렸을 때, 사이클이 포함된 Resource Allocation Graph 그리기

Deadlock이 걸리면, Resource Allocation Graph를 그렸을 때, 사이클이 존재한다.
이때 벡터들이 주어진다면, P1과 P2의 사이클이 포함된 Resource Allocation Graph 를 그릴 수 있어야 한다.

---

Recovery Strategies Once Deadlock Detected

• Abort all deadlocked processes
• Back up each deadlocked process to some previously
  defined checkpoint, and restart all process
• Successively abort deadlocked processes until deadlock no longer exists
• Successively preempt resources until deadlock no longer exists

Deadlock 이 감지 됐다면, Deadlock 이 걸리기 이전으로 되돌릴 수 있는 방법은 존재하지 않는다.

1. 방법은, Deadlock이 걸린 모든 프로세스를 Abort (중단) 하는 것이다.
   → Abort 했다는 뜻은 프로그램을 처음부터 다시 시작한다는 뜻이다. 즉, 지금까지 했던 작업들이 다 사라지는 것이다.
2. Deadlock 이 걸리기 전 가장 최신 지점으로 되돌린다. (save 한 시점)
   그것보다 프로세스를 실행시키면서 중간 중간 프로세스의 상태를 save 해둔다.
   그랬다가 Deadlock이 걸리면, Deadlock이 빠지기 전 상태로 프로세스를 되돌린다. 즉, 처음부터가 아닌 가장 최신 지점으로 되돌리는 것이다.
   → 이 방법은 어렵다, 다시 시작하려고 save 한 지점들 중 데드락이 걸리기 이전의 마지막 지점을 찾아야 한다.
3. 모든 프로세스를 Abort 하지 않고, 일부를 Abort 하고 Deadlock 이 존재하는지 확인한다.

이와 같이 두개의 사이클이 존재한다고 가정하자. (P3-P4 이중 사이클, 전체 사이클)

P3 을 Abort 하면 두개의 사이클이 지워진다.

P1을 Abort 하면 마지막 남은 사이클이 지워져서 더 이상 Deadlock 이 존재하지 않게 된다.

Abort 된 최소 1개 이상의 프로세스는 다시 프로세스를 처음부터 다시 시작해야 한다.

1. 모든 프로세스들은 주기적으로 자기 상태를 save 한다.
   (두번째와 세번째 방법은 섞은 방법이다.)
   → Deadlock 발견
   → 프로세스를 하나씩 하나씩 자원을 할당 받기 전의 상태로 되돌린다.
   → 한사람 되돌려서 Deadlock이 끝나면 거기서부터 시작하는 거고, 문제가 해결되지 않으면 다른 한사람은 자원 할당 받기 이전 상태로 되돌린다.
   → 문제가 해결되지 않으면 자원 할당 받기 전전상태로 되돌린다.
   → 순차적으로 프로세스들을 이전상태로 되돌려서 Deadlock 이 발생하기 전의 상황을 만들어 낸다.

Deadlock Prevent 와 Deadlock Avoidance 는 자원을 할당 받을 때마다 뭔가 action을 해주어야 한다.
즉, 1년 365일 내내 Deadlock Prevent 와 Deadlock Avoidance를 돌리고 있어야 한다는 뜻이다.

반면, Deadlock Detection은 Deadlock이 매일매일 발생하는 것이 아니기 때문에 매일 이 알고리즘을 돌려야하는 것이 아니라, 자원할당에 문제가 있을 때만 이 알고리즘을 돌리면 된다.
→ 프로세스가 자원을 요청했는데, 자원할당 될 때까지 시간이 이상하게 오래걸릴 때 싶을 때만 Deadlock Detection을 하면 된다.
⇒ Deadlock Prevent 와 Deadlock Avoidance에 비해 Deadlock Detection은 실행 빈도가 낮다.

Deadlock Detection 에서 시스템의 실행 상태를 중간 중간 저장하는데, 사실 원래 백업을 목적으로 저장하고 있는 시스템들이 많다. 그렇게 때문에 추가로 필요한 것은 어느 지점이 데드락이 발생하지 않았던 가장 최근 지점인가 이정도의 노력만 해주면 된다.

---

Dining Philosophers Problem
식사하는 철학자 문제

Deadlock 과 관련된 유명한 문제이다.

둥그런 원탁에 다섯명의 철학자가 앉아있다.
철학자들은 생각을 하다가 밥을 먹다가 생각을 하다가 밥을 먹다가를 반복한다.
밥을 먹으려면 포크 두개가 필요하다.
각각의 철학자는 자기 왼편의 포크와 오른편의 포크를 사용해서 면을 덜어서 밥을 먹고 밥을 다 먹고 나면 포크를 놓을 것이다.
포크1을 철학자 P0와 P1이 동시에 사용할 수 없다.
즉, 두 사람 중 한 사람이 포크를 잡으면 나머지 한 사람은 기다려야 하는 상황이다.

---

The Problem

Devise a algorithm that will allow the philosophers to eat.
1. No two philosophers can use the same fork at the same time (mutual exclusion)
2. No philosopher must starve to death (avoid deadlock and starvation)

우리는 이 철학자들이 굶어 죽지 않고(Starvation, Deadlock), 생각하고 밥먹는 행위를 계속하기를 바란다.

---

A frist Solution using Semaphore

Solution이라고 적혀 있지만, 문제를 해결하는 방법이 아니라, 문제가 발생할 가능성이 있는 알고리즘이다. 세마포를 이용한다.

5개의 포크를 세마포 5개라고 생각하면 된다.

세마포는 한 번에 한 프로세스만 접근 가능하므로 1로 초기화 되어 있다.
철학자들은 while 문을 반복하면서 생각(think())을 할 것이다.

생각을 한참하다가 밥을 먹을 생각이 들면, 자신의 왼쪽 포크를 집을 것이다.
왼쪽 포크를 무사히 집으면, 오른쪽 포크를 집을 것이다.

• semWait(fork[i]) → 철학자의 왼쪽 포크는 철학자의 id 와 같다.
• semWait(fork[i+1]) → 철학자의 오른쪽 포크는 철학자의 id+1 과 같다.
• P4와 같은 경우는 자신의 왼쪽 포크가 0번이기 때문에 modular를 한다.

왼쪽과 오른쪽 포크 모두 무사히 집으면 밥을 먹는다.

밥을 다 먹고 나면, 오른편 포크를 놓고, 그 다음 왼편 포크를 놓는다.
그러면 포크의 값이 다시 0에서 1로 바뀌게 된다.

그리고 다시 생각을 한다.

문제가 되는 상황은, 동시에 밥을 먹어야겠다고 생각이 들었을 때다.

본인의 왼쪽 포크를 집은 후 TIMEOUT이 걸린 상황이다.

모두가 fork를 하나씩 잡고 상대편이 fork를 놓기만을 기다리며 굶어죽어가는 상황이다.

---

Avoiding deadlock

위의 문제를 피할 방법.

문제를 해결하기 위하여 room 이라는 세마포를 하나 더 만들었다.
초기값은 4이다.

밥을 먹기 위해서는 room 라는 세마포를 통과해야 한다.

room 에는 최대 4명까지 철학자가 들어가서 식사가 가능하다.
⇒ 즉, 한명은 기다려야 한다.

밥 먹는 곳(최대 4명만 들어갈 수 있는)과 생각하는 곳을 구분해놨다고 생각하면 좋다.

Q. Deadlock 이 없는지 어떻게 확신할 수 있을까?

포크가 5개가 있고, 사람이 4명이 있으므로 적어도 한 사람은 포크를 집고 밥을 먹을 수 있다. 그리고 그 사람이 밥을 다 먹고 포크를 놓고 밖으로 나오면, 밖에 있던 사람이 안으로 들어 올 수 있고, 내려놓은 포크 양쪽에 있던 사람들은 밥을 먹을 수 있게 된다.

결국 순차적으로 밥을 먹을 수 있게 된다.

room 의 값을 3으로 해도 Deadlock 은 발생하지 않는다.
이 경우, 최대 3명의 철학자가 room 으로 들어갈 수 있고, 2명은 포크를 집어 밥을 동시에 먹을 수 있게 된다.

하지만, room 의 값을 5이상 6으로 하면 Deadlock 이 발생하게 된다.

Q. Circular Wait을 Prevent 하는 방식(deadlock prevention)으로 이 해결하라!

deadlock prevention 은 모든 작업에 번호 할당한다.
→ 자원을 할당할 때 번호순으로 할당한다.
↳ 이 작업은 이미 포크에 번호가 붙여 있으므로 따로 작업을 하지 않아도 된다.

모든 포크에 번호가 붙어 있으므로, 자원 할당을 번호순으로 할 수 있는 방법을 답안지에 적으면 된다...

(deadlock은 존재하지 않는다.)

 

---

A solution using a Monitor

condition 변수

monitor 를 사용할 때는 condition 변수가 존재한다.
→ condition 변수는 Queue 이다.
(프로세스들이 기다리는 Queue를 의미한다.)
→ condition 변수를 몇 개를 둘까 생각해야한다.
→ Queue 는 포크의 개수만큼 필요하다.
↳ Queue 를 하나만 두고 철학자들을 하나의 Queue 에서 기다리게 하면, 포크를 잡을 수 있다면 안기다리지만, 포크를 옆 사람이 잡고 있으면 난 기다려야 한다.
하나의 Queue 에서 기다리면, 내가 원하지 않은 포크를 사용한 사람이 나를 데려와서 내가 필요하지 않은 포크를 사용하게 할 수 있다.
⇒ 다섯개의 포크를 각 기다리는 사람들을 다른 곳에서 기다리게 하기 위해서 forkReady 라는 다섯개의 Queue 를 사용한다.

fork 변수

여기서의 fork 는 세마포가 아니라 boolean 변수이다.

fork == true → 아무도 포크를 사용중이지 않다는 뜻이다.
fork == false → 누군가가 포크를 사용중이라는 뜻이다.

get_forks()

포크를 잡는 함수이다.

제일 먼저하는 일은 현재 프로세스의 왼쪽과 오른쪽 포크의 id를 결정하는 것이다.

• 왼쪽 포크 id == 프로세스 id
• 오른쪽 포크 id == (프로세스 id + 1) mod 5

왼쪽과 오른쪽 포크가 사용중인지 확인한다.

• 만약, 왼쪽 포크가 이미 사용중이라면, cwait()를 이용해서 대기 Queue로 들어가게 된다.
  그렇지 않으면, 왼쪽 fork의 값을 false로 바꾼다.
• 오른편 fork 도 같은 방법으로 사용중인지 확인하고 cwait()로 대기하거나, 오른편 포크를 잡아 오른편 fork의 값을 false로 바꾼다.

아래쪽 코드

철학자가 생각하고 밥먹는 건 밖에서 진행한다.

즉, 밥 먹고 싶을때만 monitor 안으로 들어오고, 먹는건 밖에서 먹는다.

왜냐하면, 밥은 동시에 먹을 수 있어야 하는데, monitor 는 한 번에 하나의 프로세스만 진입 가능하기 때문이다.

release_forks()

밥을 다 먹고 포크를 놓을 때 다시 모니터로 들어오게 된다.

왼편 오른편 포크 번호를 결정한다.

• 왼편 포크를 놓을 때, 그냥 놓으면 안되고 포크를 잡으려고 기다리는 사람이 있는지 확인한다.
  • 만약 기다리는 사람이 있다면 → 깨워준다.
  • 만약 기다리는 사람이 없다면 → fork 값을 true로 바꿔준다.
• 오른편 포크를 놓을 때도 포크를 잡으려고 기다리는 사람이 있는지 확인한다.
  • 만약 기다리는 사람이 있다면 → 깨워준다.
  • 만약 기다리는 사람이 없다면 → fork 값을 true로 바꿔준다.

왜 monitor를 이용한 Solution에서는 Deadlock 이 발생하지 않을까? 🌟

아까 Deadlock이 발생했던 코드를 다시 보면,

왼편 포크 잡고 오른편 포크 잡고 밥 먹고, 오른편 포크 놓고 왼편 포크 놓고 했는데 Deadlock 이 발생했었다.

A solution using a Monitor도 똑같이 왼편 포크 잡고 오른편 포크 잡고 밥 먹고, 왼편 포크 놓고 오른편 포크 놨는데, Deadlock 이 발생하지 않는다.

포크 놓는 순서가 달라서 Deadlock이 발생하고 안발생하고 하지는 않는다.
포크를 놓는 순서에 상관 없이, signal 을 주는 순서이기 때문에
여기서는 내 왼편과 오른편 사람 중에서 오른편 사람 먼저 밥을 먹게 하고 왼편을 먹게 하고 아니면 왼편을 먼저 먹게 하고 오른편을 먹게 하고의 차이이다.
→ 밥을 먹기 시작하는 순서가 달라진다고 변하는 것은 없다.

다른 이유로 이 Solution 은 Deadlock 이 없는 Solution 이다.
↳ 이유가 무엇일까?

Monitor 안에서는 TIMTOUT이 걸리지 않아서 → X,

왜냐하면 위의 문제가 발생하는 코드는 왼편 포크를 잡고, 오른편 포크를 잡는 사이에 TIMTOUT이 발생해서 문제가 발생했던 것이었다.

하지만, 모니터 코드에서도 왼편 사람이 포크를 잡은 후 TIMEOUT이 걸릴 수 있다.
⇒ TIMEOUT이 걸리지 않는다고 하는 말은 옳지 않다.

문제가 발생하는 코드에서는 왼편 포크를 잡고 TIMEOUT이 걸려서 CPU를 내 오른편에 있는 사람이 뺏어 갔는데, 그 사람이 내 오른편 포크를 뺏어갔다.

• 왼편 fork → Timeout → 오른편 사람 → CPU → 내 오른쪽 fork 가져감

하지만 모니터를 이용한 solution에서도 TIMEOUT은 걸릴 수 있다.
내가 왼편 포크를 잡고 TIMEOUT 이 걸렸는데, 여기서 중요한 점은, monitor 안에서 TIMEOUT 이 걸렸다는 점이다.
monitor 의 가장 중요한 특성이 monitor 안에는 한 번에 한 프로세스만 들어올 수 있다는 점이다.
⇒ 즉, 내가 monitor 안에서 TIMEOUT 이 걸려서 CPU 를 뺏겨도, 다른 사람은 monitor 안에 들어올 수 없다. (다 monitor 밖에서 대기를 하는 것이다.)

monitor 안에 들어올 수 없다 == 내 오른편 포크를 뺏어갈 수 없다.
⇒ Deadlock 이 발생하지 않는다.

일단 monitor 안으로 들어가면, 왼쪽 포크를 잡고, 오른편 포크를 잡을 때까지 TIMEOUT이 걸려서 얼마나를 Ready Queue에서 기다리든지 전혀 상관 없이, 나는 일단 왼편 포크를 잡으면 오른편 포크도 잡게 된다.

monitor → 한 번에 하나의 프로세스만 들어올 수 있다. → 포크 두 개를 동시에 잡거나 / 아예 안 잡거나 둘 중 하나만 가능

⇒ Deadlock X