8. 데드락 (deadlock)
   8.1. 시스템 모델
   8.2. 멀티스레드 어플리케이션에서의 데드락
   8.3. 데드락의 특징
   8.4. 데드락을 처리하는 방법들
   8.5. 데드락 방지
   8.6. 데드락 회피
   8.7. 데드락 탐지
   8.8. 데드락으로부터의 복구

Chapter 8. Deadlocks

8.1. 시스템 모델

데드락 (deadlock)
어떤 스레드 (또는 프로세스)가 필요로 하는 자원을 다른 대기 스레드에서 점유하고 있고, 대기 스레드 역시 다른 스레드가 작업을 끝내기를 기다리고 있기 때문에 대기 상태가 영원히 끝나지 않는 현상 (서로가 서로를 기다리고 있음)

여러 개의 자원이 있는 시스템에서는 경쟁 스레드 (동기화가 필요한 스레드들)끼리 자원을 공유함.
이러한 자원들은 하나의 타입 (type)으로 묶을 수 있는데, 내부에는 여러 동일 인스턴스 (identical instance)로 이루어져 있음.
ex) CPU는 코어 수에 따라 한 번에 제공할 수 있는 자원의 수가 달라짐. 코어가 4개인 경우 4개의 자원을 한 번에 제공할 수 있고, 그 이상인 경우 한 코어의 작업이 끝날 때까지 대기함.

자원의 타입이 같은 경우 그 자원이 포함하는 인스턴스의 개수는 중요하지 않음. (몇 개의 자원 타입이 있는지 중요하지 않다는 의미)
스레드는 주로 요청 (request) - 사용 (use) - 반납 (release)의 순서로 자원을 사용하는데, '사용' 단계에서 한 번에 여러 자원을 사용할 수 있음.

8.2. 멀티스레드 어플리케이션에서의 데드락

데드락이 발생하는 예시는 6.8에서 잠깐 다룬 적이 있음.

(데드락이 발생하기 쉬운 코드)

pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;

pthread_mutex_init(&first_mutex, NULL);
pthread_mutex_init(&second_mutex, NULL);

void* do_work_one(void* param)
{
	pthread_mutex_lock(&first_mutex);
	pthread_mutex_lock(&second_mutex);

	/* 작업 수행 */

	pthread_mutex_unlock(&second_mutex);
	pthread_mutex_unlock(&first_mutex);

	pthread_exit(0);
}

void* do_work_two(void* param)
{
	pthread_mutex_lock(&second_mutex);
	pthread_mutex_lock(&first_mutex);

	/* 작업 수행 */

	pthread_mutex_unlock(&first_mutex);
	pthread_mutex_unlock(&second_mutex);

	pthread_exit(0);
}

6.8에서 소개한 예시를 코드로 옮긴 것임.

8.3. 데드락의 특징

다음 네 가지 조건을 모두 만족해야만 데드락이 발생함. -> 확률상 데드락은 그렇게 자주 발생하지도 않고, 데드락이 발생하는 예제를 만들기도 까다로움.

• 상호 배제 (mutual exclusion): 적어도 1개 이상의 자원이 공유 불가능해야 함. (여러 스레드 중에 하나라도 자원을 변경하는 스레드가 있으면 경쟁 상태가 발생할 수 있음)
• 점유 대기 (hold and wait): 스레드가 적어도 1개 이상의 리소스를 점유하고 있는 상태로 대기하고 있어야 함. (아무 자원도 점유하지 않고 대기중이면 그 스레드를 필요로 하지 않기 때문에 데드락이 발생하지 않음)
• 비선점 (no preemption): 자원은 선점이 불가능해야 함. (다른 스레드, 혹은 스케쥴러가 자원을 강제로 가져오는 것을 선점이라고 함)
• 순환 대기 (circular wait): 대기 중인 스레드들이 필요로 하는 다른 스레드를 이어보면 순환 구조를 가져야 함.
  

---

데드락을 조금 더 쉽고 명확하게 표현하기 위해 자원 할당 그래프 (resource-allocation graph, RAG)를 그릴 수 있음.
자원 할당 그래프는 방향성을 갖는 방향 그래프 (directed graph, digraph)임.

자원 할당 그래프의 정점 (vertex) 집합은 두 가지로 나뉨.

• $T = \{T_1, T_2, \cdots T_n\}$ -> 활성화된 모든 스레드의 집합
• $R = \{R_1, R_2, \cdots R_n\}$ -> 모든 자원들의 집합

각 정점들을 잇는 간선 (edge)은 다음과 같음.

• $T_i \rightarrow R_j$ (request edge): $T_i$ 스레드가 $R_j$ 자원을 요청하였음.
• $R_j \rightarrow T_i$ (assignment edge): $R_j$ 자원이 $T_i$ 스레드에 할당되었음.

first_mutex 자원은 thread_one 스레드에, second_mutex 자원은 thread_two 스레드에 할당되어있는 상황.
이때 thread_one이 second_mutex를, thread_two가 first_mutex를 요청하게 되면 전체 그래프에 순환 (cycle)이 생김. 이러한 상황이 데드락 상황임.
이렇듯 자원 할당 그래프를 그려보면 데드락 상황을 쉽게 파악할 수 있음.

---

자원 할당 그래프 예시
1)

자원을 나타내는 정점 내부에 있는 점의 개수는 그 자원의 인스턴스 개수를 나타냄.
순환 구조가 발견되지 않으므로 데드락이 발생하지 않음.

2)

2개의 순환 구조가 존재하여 데드락이 발생하였음.

3)

1개의 순환 구조가 존재함.
but $T_1$ 스레드가 요청한 $R_1$ 자원의 인스턴스가 2개이고 한 인스턴스가 순환 구조에 걸려 있지 않은 $T_2$ 스레드에 할당되어있기 때문에 $T_2$가 작업을 끝내고 $R_1$ 자원을 반납한다면 $T_1$은 자원을 받아 작업을 수행할 수 있음. 따라서 순환 구조는 존재하지만 데드락이 발생하지 않음.

결론
자원 할당 그래프에 순환 구조가 있으면 데드락이 절대 발생하지 않지만, 순환 구조가 있는 경우 발생할 수도, 발생하지 않을 수도 있음.

8.4. 데드락을 처리하는 방법들

데드락을 처리하는 방법은 대략 세 가지 정도가 있음.

• 문제 자체를 무시하는 것
  - 기도메타 (적어도 내가 이 회사 다닐때만큼은 데드락 안생기기를..)
• 적절한 프로토콜을 사용하여 데드락을 아예 방지하거나 피하는 것
  - 데드락 상황이 자주 일어나지 않는다는 전제로,
  - 아예 데드락이 일어나지 않도록 방지 (prevent)하는 방법이 있음. (8.5에서 자세히 다룸) -> 매우 어렵고 복잡한 방법. 인공위성과 같이 오차가 발생하면 안되는 예민한 시스템에 사용함.
  - 그렇지 않고 은행원 알고리즘 (banker's algorithm)을 사용하여 데드락을 회피 (avoid)할 수도 있음. (8.6에서 자세히 다룸)
• 일단은 아무런 조치도 취하지 않다가 데드락이 발생한 경우 이를 탐지 (detect)하여 복구 (recover)하는 방법 (실제로 많이 쓰는 방식)
  - 시스템을 모니터링하다가 데드락을 발견하고 상황을 복구함.
  - 데드락 탐지는 8.7, 복구는 8.8에서 자세히 다룸.

8.5. 데드락 방지

데드락은 앞서 설명한 4가지 조건 (상호 배제, 점유 대기, 비선점, 순환 대기)을 모두 만족해야 발생하는 상황이었음. 1가지 조건이라도 만족하지 않으면 데드락은 발생하지 않을 것임.
데드락 방지는 4가지 중 최소 1개의 조건이 절대 만족하지 않도록 막는 방법임.

---

1) 상호 배제
최소 1개 이상의 자원이 공유가 불가능해야 한다는 조건이었는데, 모든 자원이 공유 가능하면 이 조건은 만족하지 않음. -> 근데 이거 현실적으로 가능한 얘기임?
몇몇 자원 중에는 본질적으로 공유가 불가능한 자원도 존재함.
ex) 뮤텍스 락을 스레드끼리 공유한다? 말이 되지 않음. 다른 스레드가 접근하지 못하도록 하기 위해 만든 것이 뮤텍스 락인데, 이걸 공유하게 되면 뮤텍스 락을 사용하는 이유가 없어짐.

2) 점유 대기
스레드가 자원을 점유한 상태로 대기하고 있기 때문에 발생하는 문제였음. 스레드가 자원을 요청할 때 기존에 점유하고 있던 자원을 모두 반납한 뒤 요청하는 것을 강제하면 문제 해결.
but 이는 매우 비효율적인 시스템임.
ex) 1억 개의 파일을 open하고 있는 스레드가 있다고 가정. 그런데 1개의 새로운 파일에 접근하기 위해 1억 개나 되는 파일을 모두 close해야 하고, 또 파일 접근이 끝난 후에는 다시 1억 개의 파일을 open해야 함. 비효율적이고 쓸데없는 과정.

3) 비선점
다른 스레드가 점유하고 있는 자원을 선점하여 주도권을 뺏을 수 있도록 하자는 개념.
그런데 선점당한 스레드가 어떤 작업을 하고 있었는지도 모른 채로 그냥 뺏어버리면 예상치 못한 문제가 생길 수도 있음. 잘 사용하지 않는 해법.

4) 순환 대기
4가지 해법 중 그나마 실용적인 해법임.
각 리소스마다 순서를 배정하여 자원을 요청할 때 기존에 점유하고 있던 자원보다 낮은 순서의 자원은 요청할 수 없도록 하여 순환 구조가 발생하지 않도록 막는 것.
이렇게 하면 데드락이 발생하지 않는다는 것을 증명할 수 있지만, 반대로 기아 상태 (starvation)이 발생할 위험성이 높아짐. (우선순위를 준 것과 마찬가지이기 때문)

심지어 데드락이 발생하지 않는다는 것을 완벽히 보장할 수도 없음.

from에서 to로 돈을 송금하는 상황을 가정.
순환 대기 조건을 막기 위해 순서를 부여하여 무조건 lock1을 획득한 후 lock2를 획득하도록 구현했으나 여기서도 데드락이 발생할 수 있음.
계좌 A, B에 대해 A->B (T1), B->A (T2)로의 송금이 동시에 발생했다면?
T1이 lock1을 획득한 상황에서 T2가 lock2를 획득하려고 하면 T1이 lock1을 반납할 수 없으므로 순환 구조가 생김.

1, 2, 3번 조건은 본질적으로 불가능한 해결법이고, 4번은 실용적이긴 하지만 문제가 많은 해결법임. 따라서 완벽하게 데드락을 방지하는 것은 사실상 불가능함. (멀티스레딩의 장점을 다 없애버림)

8.6. 데드락 회피

스레드의 자원 요청을 받기 전에 발생 가능한 데드락이 있는지 확인할 수 있음. 이를 위해서는 자원이 어떻게 요청되었는지에 대한 정보가 필요함.

ex) $R_1$, $R_2$ 2개의 자원을 갖는 시스템에서 스레드 $P$가 $R_1$을 점유한 상태로 ($R_1 \rightarrow P$) $R_2$를 요청 ($P \rightarrow R_2$)하고, 스레드 $Q$는 $R_2$를 점유한 상태로 ($R_2 \rightarrow Q$) $R_1$을 요청 ($Q \rightarrow R_1$)하는 상황 -> 그대로 놔두면 순환 구조가 발생하여 데드락이 발생할 위험이 있으므로 $P \rightarrow R_2$, $Q \rightarrow R_1$ 요청이 들어왔을 때 이를 거절 (reject)할 수 있음.

몇 가지 사전지식이 있으면 알고리즘을 통해 시스템이 데드락 상태에 절대 빠지지 않도록 할 수 있음.
필요한 자원의 최대 개수를 알고 있고, 사용 가능하며 이미 할당되어있는 자원이나 앞으로 요구할 자원의 수를 알고 있으면 이를 데드락 회피에 활용할 수 있음.

---

안전 상태 (safe state)
자원을 각 스레드에 최대치까지 할당할 수 있으며, 스레드의 실행 순서가 정해져 있어 데드락이 발생하지 않는 상태

스레드에 안전 순서 (safe sequence)가 존재하여 정해진 순서에 따라 모든 자원을 각 스레드에 할당할 수 있음. 이 안전 순서가 데드락 회피의 핵심.

안전 상태는 데드락이 발생하지 않는 상태임. 역으로 말하면 안전하지 않은 상태 (unsafe state)는 데드락이 발생할 가능성이 있는 상태를 말함. (발생하지 않을 수도 있음)
따라서 스레드를 최대한 안전 상태에 있게 하는 것이 데드락 회피의 주요 개념.

회피 알고리즘은 시스템이 항상 안전 상태에 있도록 구현되어 데드락을 회피해야 함.
시스템 초기에는 안전 상태에서 시작함. (점유 대기를 수행하기 때문) 이후 자원 요청이 들어올 때마다 상태를 판단하여 자원을 할당할지, 할당하지 않을지 결정함. (시스템이 안전 상태에 있는 경우 자원 할당을 허용하고, 그렇지 않은 경우 요청을 거부함)

---

자원 할당 그래프가 오직 1개의 인스턴스를 갖는 자원으로 구성되어 있다고 가정.
이때 데드락 회피를 위해 요청 가능 간선 (claim edge)을 추가할 수 있음.
$T_i \rightarrow R_j$은 $T_i$ 스레드가 미래에 $R_j$ 자원을 요청할 수도 있음을 의미함.
claim edge를 자원 할당 그래프에 추가하여 순환 구조가 발생하는지 판단하면 시스템이 안전 상태에 있는지 확인할 수 있음.
만약 claim edge를 추가한 자원 할당 그래프에 순환 구조가 없다면 안전 상태에 있다는 뜻으로, 추후 그 요청이 들어왔을 때 허용해줄 수 있음.

claim edge를 추가했을 때 순환 구조가 없는 경우

반대로 순환 구조가 발견된 경우 이를 허용하면 안전하지 않은 상태에 들어갈 수 있으므로 즉시 허용하지 않음. (잠시 대기)

claim edge를 추가했을 때 순환 구조가 있는 경우

자원의 인스턴스가 여러 개인 경우 RAG에서 순환 구조를 파악하는 것만으로는 데드락을 확인할 수 없음. (순환 구조가 있어도 데드락이 발생하지 않는 경우가 있기 때문) -> 이 경우 은행원 알고리즘 (banker's algorithm)을 사용함. but RAG에 비해 비효율적이고 복잡함.

---

은행원 알고리즘 (banker's algorithm)

$n$을 스레드의 개수, $m$을 자원의 개수라고 가정.

• Available[m]: 사용 가능한 자원을 나타내는 벡터.
  Available[j] == k -> $R_j$ 자원 중 k 개의 인스턴스가 사용 가능함.
• Max[n $\times$ m]: 각 스레드가 최대로 요구할 수 있는 자원에 대한 행렬 (matrix).
  Max[i][j] == k -> $T_i$ 스레드가 최대 k개의 $R_j$ 자원을 요청할 수 있음을 의미함.
• Allocation[n $\times$ m]: 각 스레드에 현재 할당되어있는 자원을 나타내는 행렬.
  Allocation[i][j] == k -> $T_i$ 스레드에 현재 k 개의 $R_j$ 자원이 할당되어있음.
• Need[n $\times$ m]: 현재 할당되어있는 자원을 제외한 남은 자원.
  Need[i][j] == k -> $T_i$ 스레드가 앞으로 k 개의 $R_j$ 자원을 요청할 수 있음.

---

안전 알고리즘 (safety algorithm)

1. Work, Finish는 각각 m, n의 길이를 갖는 벡터. Work = Available, Finish[i] = false $(i=0,1,\cdots,n-1)$로 초기화함.
2. 다음 두 조건을 만족하는 인덱스 i를 탐색함. (i를 찾을 수 없는 경우 4번으로 이동)
   a. Finish[i] == false
   b. Need$_i$ $\le$ Work
3. Work = Work + Allocation$_i$
   Finish[i] = true
   이후 2번으로 이동.
4. 모든 i에 대해 Finish[i] == true이면 시스템은 안전 상태에 들어와 있는 것임.

자원 요청 알고리즘 (resource-request algorithm)

1. Request$_i$ $\le$ Need$_i$이면 2번으로 가고, 그 외의 경우 스레드가 최대 요청 (maximum claim)을 넘어선 것이므로 에러가 발생함.
2. Request$_i$ $\le$ Available인 경우 3번으로 가고, 그 외의 경우 자원이 사용 가능하지 않으므로 T$_i$ 스레드는 기다려야 함.
3. 시스템은 다음과 같이 상태를 수정하여 요청한 자원을 T$_i$ 스레드에 할당한 것처럼 보이게 함.
   Available = Available - Request$_i$
   Allocation$_i$ = Allocation$_i$ + Request$_i$
   Need$_i$ = Need$_i$ - Request$_i$

---

예시
$\{T_0, T_1, T_2, T_3, T_4\}$ 5개의 스레드, $\{A, B, C\}$ 3개의 자원이 있고, 각 자원 A, B, C는 A = 10, B = 5, C = 7개의 인스턴스를 갖는다고 가정.

Allocation은 각 스레드가 현재 할당 중인 자원, Max는 앞으로 필요한 총 자원의 수임. (ex. $T_0$ 스레드는 B 자원을 1개 할당하고 있고, 5개가 필요함)
Available은 각 자원의 인스턴스의 개수에서 현재 할당 중인 자원의 수를 빼주면 됨. -> $A = 10 - 7 = 3, B = 5 - 2 = 3, C = 7 - 5 = 2$
Need[i][j] = Max[i][j] - Allocation[i][j]임. (최대로 요구할 수 있는 양과 현재 할당하고 있는 양의 차이)

여기서부터 안전 알고리즘을 수행함.
1. Work = Available = (3, 3, 2) / Finish = (false, false, false, false, false)
2. i = 0 ~ i = 4까지 Need$_i$ $\le$ Work인 i 값을 찾음. (벡터의 모든 요소를 하나씩 비교함) i를 찾은 경우 Work = Work + Allocation$_i$로 값을 업데이트함. && Finish[i] = true
i = 0 -> (7, 4, 3) $\le$ (3, 3, 2) == false ($T_0$ 스레드의 요청은 현재 받아들일 수 없음.
i = 1 -> (1, 2, 2) $\le$ (3, 3, 2) == true -> Work = Work + Allocation$_1$ = (3, 3, 2) + (2, 0, 0) = (5, 3, 2) && Finish[1] = true
i = 2 -> (6, 0, 0) $\le$ (5, 3, 2) == false
i = 3 -> (0, 1, 1) $\le$ (5, 3, 2) == true -> Work = Work + Allocation$_3$ = (5, 3, 2) + (2, 1, 1) = (7, 4, 3) && Finish[3] = true
i = 4 -> (4, 3, 1) $\le$ (7, 4, 3) == true -> Work = Work + Allocation$_4$ = (7, 4, 3) + (0, 0, 2) = (7, 4, 5) && Finish[4] = true

(모든 Finish가 true가 아니므로 i = 0으로 다시 돌아감)
i = 0 -> (7, 4, 3) $\le$ (7, 4, 5) == true -> Work = Work + Allocation$_0$ = (7, 4, 5) + (0, 1, 0) = (7, 5, 5) && Finish[0] = true
i = 2 -> (6, 0, 0) $\le$ (7, 5, 5) == true -> Work = Work + Allocation$_2$ = (7, 5, 5) + (3, 0, 2) = (10, 5, 7) && Finish[2] = true

최종 결과
Work = (10, 5, 7), Finish = (true, true, true, true, true)
$T_1$ -> $T_3$ -> $T_4$ -> $T_0$ -> $T_2$의 순서로 스레드를 실행하면 안전성이 보장됨.

---

이 상황에서 $T_1$ 스레드가 A 1개, C 2개를 요청한다면 Request$_1$ = (1, 0, 2)임. 이 요청을 받아들일지 말지를 판단하기 위해 자원 요청 알고리즘을 사용함.

1. Request$_i$ $\le$ Need$_i$인지 확인
   Request$_1$ = (1, 0, 2) $\le$ Need$_1$ = (1, 2, 2) == true
2. Request$_i$ $\le$ Available$_i$인지 확인
   Request$_1$ = (1, 0, 2) $\le$ Available$_1$ = (3, 3, 2) == true
3. Available, Allocation, Need의 값을 각각 Request 값에 따라 바꿔줌.
   Available = Available - Request$_1$ = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)
   Allocation$_1$ = Allocation$_1$ + Request$_1$ = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)
   Need$_1$ = Need$_1$ - Request$_1$ = (1, 2, 2) - (1, 0, 2) = (0, 2, 0)
   
   but 이 상태는 요청을 허락한 상태가 아님. -> 다시 안전 알고리즘을 통해 이 요청을 받아들여도 되는지 확인함. -> 동일하게 $T_1$ -> $T_3$ -> $T_4$ -> $T_0$ -> $T_2$ 순서로 요청을 받을 수 있음. 문제가 없는 경우 시스템 상태가 실제로 저 사진처럼 될 것임.
   1, 2번 조건을 만족하지 않는 경우 요청이 거절됨.

안전 알고리즘은 현재 상태가 안전 상태인지 확인하는 알고리즘이고, 자원 요청 알고리즘은 어떤 요청이 들어왔을 때 허용이 가능한지 확인하는 알고리즘임.

8.7. 데드락 탐지

데드락 방지는 문제가 많고, 데드락 회피는 매 요청이 들어올 때마다 수행하기에는 시스템 입장에서 너무 무겁고 부담스러움. 이 때문에 최근에는 일단 데드락 발생을 허용하되, 지속적인 모니터링을 통해 데드락이 발생하면 즉시 시스템을 복구하는 방식을 많이 사용함.

---

인스턴스가 1개인 경우 (single instance)
자원 할당 그래프와 유사한 대기 그래프 (wait-for graph)를 사용함.
주기적으로 알고리즘을 호출하여 대기 그래프 내에 순환 구조가 있는지 확인함.

(a)는 자원 할당 그래프, (b)는 이에 대응하는 대기 그래프임.
자원 할당 그래프에서 자원에 해당하는 node를 제거하고, 각 스레드 사이의 관계만 남겨놓은 것이 대기 그래프.

인스턴스가 여러 개인 경우 (several instances)
자원 할당 그래프에서와 마찬가지로 대기 그래프만으로는 해결하기 어렵기 때문에 은행원 알고리즘과 비슷한 방식으로 진행함.
은행원 알고리즘과 동일하게 진행하되, Need를 Request로 바꿈.
데드락 탐지 알고리즘

1. Work, Finish는 각각 m, n의 길이를 갖는 벡터. Work = Available $(i=0,1,\cdots,n-1)$로 초기화하고, Allocation$_i$ != 0인 경우 Finish[i] = false, 그 외의 경우 true로 초기화함.
2. 다음 두 조건을 만족하는 인덱스 i를 탐색함. (i를 찾을 수 없는 경우 4번으로 이동)
   a. Finish[i] == false
   b. Request$_i$ $\le$ Work
3. Work = Work + Allocation$_i$
   Finish[i] = true
   이후 2번으로 이동.
4. $0 \le i \lt n$인 i에 대해 Finish[i] == false인 i가 존재할 경우 시스템은 데드락이 발생할 수 있는 상태이며, 해당 스레드는 데드락에 걸린 상태임.

8.8. 데드락으로부터의 복구

데드락 탐지 결과 실제로 데드락이 발생했다면, 단순히 "데드락 발생했음"을 알려주기만 할수도 있고, 중요한 시스템인 경우 즉시 복구도 진행할 수 있음.

데드락 복구의 2가지 방법

• 프로세스 및 터미널 종료 (process and thread termination): 데드락이 발생한 스레드, 혹은 프로세스를 강제 종료하는 방식. 문제가 발생한 모든 스레드를 종료할 수도 있지만 그건 너무 부담스러우므로 순환 구조를 이루는 스레드 중에서 한 스레드만 종료시켜줘도 순환 구조가 깨지면서 데드락이 복구될 수 있음. 1개를 죽여서 해결되지 않으면 2개, 3개, ...를 죽이는 방식으로 진행.
• 자원 선점 (resource preemption)
  - 피해자 선정 (selecting a victim): 비용을 최소화하는 방향으로 특정 프로세스의 자원을 선점하여 요청한 스레드에게 넘겨줌.
  - 롤백 (roll-back): 프로세스를 안전 상태로 롤백하고 재시작함.
  - 기아 (starvation): 이렇게 하다보면 계속 피해자로 선택되는 프로세스가 생겨서 기아 문제를 야기할 수 있음. 따라서 피해자로 선택되는 횟수를 제한하여 무한히 자원을 선점당하는 참사를 방지해야 함.