OS ) 교착 상태 DeadLocks

교착 상태

대기 중인 스레드들이 대기 상태에서 변경이 어려울 때

• 그들이 요청한 자원이 다른 스레드들에 의해 점유되어 있고, 그들도 다 대기 상태에 있기 때문에
• 예) 두 기차가 교차로에서 서로 접근할 때는, 둘 다 완전히 정지해야 하고 상대방이 없어지지 않는 한 누구도 다시 출발할 수 없음..

시스템 모델

Mutex 락과 세마포도 자원이며, 가장 일반적인 교착상태의 발원지 이다.

• 락은 일반적으로 특정 자료구조와 연관되어 있다. (Queue And LinkedList)
  • 큐에 대한 엑세스를 보호하고 연결 리스트에 대한 엑세스를 보호한다.
  • 그래서 고유한 자원이 할당 됨.

스레드와 락

• 스레드는 자원을 사용하기 전에 반드시 요청해야 하고, 사용 후에는 반드시 방출해야 한다.
• 요청된 자원의 수가 시스템에서 사용 가능한 전체 자원의 수를 초과해서는 안 된다.
  • 예) 시스템이 한 개의 네트워크 인터페이스밖에 없는데 두 개를 요청할 순 없음.

프로세스 자원 사용 순서

1. 요청
   • 즉시 허용되지 않으면 자원을 얻을 때까지 대기
2. 사용
   • 자원에 대한 자원을 수행.
   • 자원이 mutex Lock 이라면 자기 임계 구역에 접근하기.
3. 방출
   • 스레드가 사용한 자원을 방출.

자원 요청과 방출은 시스템 콜이다.

• 그래서 운영체제는 매번 스레드가 자원을 요청했는지, 할당받았는지 확인한다.
• 어느 스레드에 할당되었는지도 기록한다.
• 어떤 스레드가 다른 스레드에 할당된 자원을 요청하면, 대기 큐에 입력한다.

교착 상태

한 스레드 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해서만 발생될 수 있는 이벤트를 기다린다면, 그 스레드 집합은 교착 상태에 있다.

• 자원의 획득과 방출이 중요.

💡 물론 락 뿐만 아니라 다른 유형의 교착 상태도 있다.
하지만 개발자는 락이 획득되고 방출되는 방식에 주의를 기울여야한다.(락에 관한 교착 상태를 신경쓰면 된다는 뜻.)

다중 스레드 앱에서의 교착 상태

void *do_work_one(void *param)
{
	**pthread_mutex_lock(&first_mutex);  // 이 둘이 겹쳐서
	pthread_mutex_lock(&second_mutext);// 교착 상태 발생 가능**
	/**
	* Do some work
	*/
	pthread_mutex_unlock(&second_mutex);
	pthread_mutex_unlock(&first_mutex);
	
	pthread_exit(0);
}

void *do_work_two(void *param)
{
	**pthread_mutex_lock(&second_mutext); // 이 둘이 겹쳐서
	pthread_mutex_lock(&first_mutex);   // 교착 상태 발생 가능**
	/**
	* Do some work
	*/
	pthread_mutex_unlock(&first_mutex);
	pthread_mutex_unlock(&second_mutext);
	
	pthread_exit(0);
}

• 저 명령어 둘이 거의 동시에 실행되고 명령어 순서가 겹친다면, 교착 상태 발생 가능.
  • 꼭 발생하는 건 아니지만, 멀티스레드에서 동시에 락을 획득한다면..
  • 특정 스케줄링 상황에서만 발생할 수 있음. ← 이걸 식별하고 검사하는 건 어려움. ㅠㅠ

라이브락

교착 상태와 유사하게 스레드가 진행되는 것을 방해하지만, 진행할 수 없는 이유가 서로 다르다.
→ 스레드가 실패한 행동을 계속해서 시도할 때 발생.

• 서로 락을 해제하고 봉쇄하는 시도를 무한으로 하는 것…
  • 예) thread1은 lock1 을 획득한 후 lock2 를 시도하고
  • thread2는 lock2 를 획득한 후 lock1 을 시도하려고 한다.
  • 서로의 락을 양보하려는 과정에서 반복적으로 실패하고, 계속 다시 시도하면서 무한 루프.
• 각 스레드가 실패한 행동을 재시도하는 시간을 무작위로 정하면 회피할 수 있음.
  • 예) 네트워크 충돌 발생 직후에 패킷을 재전송하는 게 아니라, 임의의 시간동안 기다린 후 다시 패킷을 전송한다.

교착 상태 특성

필요 조건

교착 상태는 다음 네 가지 조건이 동시에 성립될 때 발생할 수 있다.

1. 상호 배제 (mutual exclusion)
   • 임계 구역에 진입하면 자원을 요청해도 방출될 때까지 지연 된다.
     • 비공유 모드로 점유 된다.
2. 점유하며 대기 (hold-and-wait)
   • 최소한 하나의 자원을 점유한 채, 다른 스레드에 점유된 자원을 추가로 얻기 위해 반드시 대기해야 할 때.
   • 자원을 점유하고 있으면서 + 다른 자원도 점유하고 싶어서 대기.
3. 비선점 (no preemption)
   • 자원이 강제적으로 방출될 수 없고 자발적으로만 방출될 수 있음.
4. 순환 대기(circular wait)
   • 서로의 자원을 순환 대기하는 것.
   • 개발자가 할 수 있는 건 순환 대기를 막는 것이 제일 현실적^^.

자원 할당 그래프

• 활성 스레드 집합과 자원 유형의 집합으로 구별.
• 스레드 → 자원은 요청 간선.
• 자원 → 스레드는 할당 간선.

요약

• 그래프가 cycle 이 아니면 교착상태가 아니다.
• 그래프가 cycle 이고, 각 자원 유형이 하나의 인스턴스만 갖는다면 교착 상태가 발생한 것이다.
  • 자원 유형이 여러 개의 인스턴스를 가지면 사이클이더라도 반드시 교착 상태는 아닐 수 있다.

교착 상태 처리 방법

• 문제를 무시하고 교착 상태가 시스템에서 절대 발생하지 않는 척하기. → 운영체제.
  • 비용이 제일 적게 든다.
    • 무시해도 뭐 운영체제에서는 드물게 발생하니 굳이 비용을 쓸 필요 없음.
• 교착 상태가 되지 않도록 보장하기 위해 교착 상태를 예방하거나 회피하는 프로토콜 사용. → 개발자의 역랑ㅠ
  • 교착상태 예방 : 필요 조건 중 적어도 하나가 성립하지 않도록 보장
  • 교착 상태 회피 : 스레드가 평생 요구하고 사용할 자원에 대해 정보를 미리 요청하여 운영체제가 스케쥴링.
• 교착 상태가 되도록 허용한 다음 복구 → DB
  • 시스템 상태를 조사하는 알고리즘
  • 교착 상태로부터 복구하기 위한 알고리즘

💡 운영체제가 제어하지 않는 실시간 스레드는 교착 상태가 아닌 상황을 위해 수작업 복구 방법을 가지고 있어야 하며, 동일한 방법을 교착 상태 회복을 위해 사용할 수도 있음.

 

교착 상태 예방

네 가지 필요 조건이 전부 성립해야 하지만, 현실적으로 앱 개발자가 할 수 있는 건 → 순환 대기 막기

• 상호 배제 (mutual exclusion)
  • 적어도 하나의 자원은 공유가 불가능한 자원이어야 한다.
  • 공유 가능한 자원들은 교착 상태에 관련될 수 없다. (읽기 전용 파일)
  • mutex 락 같은 어떤 자원들은 근본적으로 공유가 불가능하니 현실적으로 이걸로 예방은 불가능..
• 점유하며 대기 (hold and wait)
  • 스레드가 자원을 요청할 때 다른 자원을 보유하지 않도록 보장.
  • 현실적으로 응용 프로그램에는 실용적이지 않음…^^
  • 단점
    • 자원이 할당되어도 장기간 사용하지 않으면 자원 이용률 낮음.
    • 인기 있는 여러 개의 자원이 필요한 스레드는 필요한 자원 중 적어도 하나는 다른 스레드에 할당 됨 → 무한정 대기…
• 비선점 (no preemption)
  • 이미 할당된 자원이 선점되지 않아야 함.
  • 어떤 자원을 점유하고 있는 스레드가 즉시 할당할 수 없는 다른 자원을 요청하면(스레드가 반드시 대기해야 하면) 현재 점유하고 있는 모든 자원이 묵시적으로 방출된다.
  • CPU 레지스터나 DB 트랜잭션처럼 상태가 쉽게 저장되고 복원될 수 있는 자원에 종종 적용.
    • mutex, 세마포같은 락에는 사용 불가….
• 순환 대기 (circular wait)
  • 모든 자원 유형에 순서를 부여해서 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요구.
  • 물론 순서나 계층 구조를 정하는 것 자체만으로는 교착 상태를 예방할 수 없음.
    • 개발자가 해야되는데, 수백 수천 개의 락이 있다면…?
    • Java 에서는 System.identityHashCode() 메소드로 락 획득 순서 지정
  • 락이 동적으로 획득될 수 있다면 순서를 부여한다고 해서 교착 상태 예방을 보장할 순 없음.

  transaction(checking_account, savings_account, 25.0)
  transaction(savings_account, checking_account, 50.0)
  
  이런 트랜잭션이 동시에 발생하면
  교착 상태 발생 가능성이 있음..^^
  

교착 상태 회피

요약 : 최대 자원 요구량을 알아 놓고, 특정 스레드에게 자원을 할당할지 결정한다.

• 교착 상태 예방 알고리즘은 장치 이용률이 저하되고 시스템 총처리율이 감소한다는 문제가 있다.
• 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 하는 것은 어떨까?
  • 스레드의 요청과 방출에 대한 완전한 순서를 파악하고 있다면 → 각 요청에 대해 가능한 미래 교착 상태를 피하고자 스레드가 대기해야 하는지 여부를 결정할 수 있다.

💡 락이 올바른 순서로 획득되었는지 검증하는 데에 특정 SW 가 사용될 수 있다. Linux 의 경우 커널 내의 “락킹 순서를 검증”하는 도구인 lockdep 을 제공한다.
lockdep : 락 획득 및 해제 규칙을 기준으로 락 획득 및 해제의 사용 패턴을 감시.

회피 유형

가장 단순한 건.. → 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구해보자 !

• 회피 알고리즘은 시스템 상태가 항상 안전 상태를 떠나지 않도록 고수한다.
• 스레드들이 자원을 요청할 때, 시스템은 결정한다.
  • 즉시 자원을 할당할 수 있는지?
  • 아님 스레드가 대기해야 하는지?
• 요청한 자원을 즉시 승낙해주는 경우는 시스템 상태가 안전 → 안전 상태로 옮길 때 뿐.

안전 상태

시스템이 안전하다 == 시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원을(최대 요구 수를 요구해도) 교착 상태를 야기시키지 않고 차례로 모두 할당해줄 수 있음.

• 시스템이 이런 “안전 순서” 를 찾을 수 있으면 시스템은 안전하다고 이야기 한다.

예시

Ti 가 요청하는 자원을 시스템이 당장 만족시켜줄 수 없지만, 이전 스레드가 끝나고 자원을 반납한 후에는 자원을 만족시켜줄 수 있다.

• Ti 가 모든 Tj 들이 마친 후까지 기다린다.
• Ti 는 모든 Tj 들이 반납한 자원들을 가지고 수행한다.
• Ti 가 끝났을 때 Ti+1 은 필요한 모든 자원을 얻게 되고 이와 같은 상황 반복.

→ 모든 스레드를 무사히 마칠 수 없는 시퀀스를 찾을 수 없으면 불안전(unsafe) 하다고 함.

시스템이 불안전하다면

• 시스템이 안전하다면 교착 상태가 아니다.
• 교착 상태에 있는 시스템은 불안전한 상태다.
• 하지만, 시스템 상태가 불안전하다고 해서 반드시 교착 상태로 간다는 건 아니다.
  • 앞으로 교착 상태로 가게 될 수도 있다는 뜻… 꼭 교착상태로 간다는 건 아님.

예시

	최대 소요량	현재 사용량
T0	10	5
T1	4	2
T2	9	2

• 시스템 자원 총 갯수가 10개일 경우, T1이 자원을 마치고 반납해도 시스템 자원은 6개일 뿐이다.
• T2가 최대 자원 갯수인 9개를 요구하여 7개를 더 채워야 할 경우, T0 이 끝나더라도 자원을 다 확보할 수 없다.
  • 만약 다른 스레드가 끝날 때까지 기다렸다가 자원을 줬다면 교착 상태를 피할 수도 있었을 텐데..
• 자원을 달라고 했을 때 그걸 바로 준다면 교착 상태가 될 가능성이 있다.

단점

• 스레드가 요청한 자원보다 많은 양을 시스템이 보유하더라도, 프로세스를 기다리게 할 수 있다. (교착 상태 발생 가능성 때문에..)
  • 결국 자원 이용률은 회피를 안 쓸 때에 비해서 낮아질 수밖에 없음..ㅎㅎ!

자원 할당 그래프 알고리즘

 

예약 간선(claim edge)이라는 새로운 간선을 도입한다.

• 예약 간선
  • 미래에 이런 자원을 요청할 것이다 예약해두는 것.
  • Ti → Rj 는 Pi(Ti)가 미래에 자원 Rj 를 요청할 것이라는 의미.
• 시스템에서 자원이 반드시 예약되어야 한다.
  • 스레드 Ti 가 실행되기 전, 스레드의 모든 예약 간선이 자원 할당 그래프에 표시가 되어야 한다.
  • 요청 간선을 할당 간선으로 변환해도 사이클을 허용하지 않을 때만 요청을 허용한다.
• 사이클 탐지 알고리즘을 이용해 안전성을 검사한다.
  • 만약 사이클이 없다면 자원을 할당해도 시스템은 안전 상태가 된다.

→ 단, 종류마다 자원이 여러 개씩 있으면 사용할 수 없다. 한 개만 있을 때 사용 가능.

은행원 알고리즘

자원 할당 그래프 알고리즘보다 효율성이 다소 떨어지지만, 종류마다 자원이 여러 개 있을 때 사용한다.

• 스레드가 시작할 때 스레드가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 미리 신고한다.
• 스레드가 자원들을 요청할 때, 시스템은 그걸 들어줬을 때 시스템이 계속 안전 상태인지 판단한다.
  • 계속 안전하면 요청을 들어주고
  • 안전하지 않다면 요청이 허락X → 다른 스레드가 끝날 때까지 기다려서 할당 받는다.

은행원 알고리즘의 자료구조

• Available
  • 각 종류별로 가용한 자원의 개수
• Max
  • 각 스레드가 최대로 필요로 하는 자원의 개수
• Allocation
  • 각 스레드에 현재 할당된 자원의 개수
• Need
  • 각 스레드가 향후 요청할 수 있는 자원의 개수

안전성 알고리즘

시스템이 안전한지 아닌지 알아낼 수 있는 알고리즘

1. Work 와 Finish 는 크기가 m 과 n 인 벡터 (m 자원 수, n 스레드 수)
   • Work = Avaliable(가용 자원의 개수) 로 초기 값 설정
   • Finish[i] = false 로 초기 값 설정
2. 아래 두 조건을 만족시키는 i 값을 찾는다.
   • Finish[i] == false
   • Needi ≤ Work (향후 요청할 자원 개수 ≤ 가용 자원 개수)
   • 이 값을 찾을 수 없다면 4번으로 간다.
3. 아래 두 조건이 맞다면 2번으로 간다.
   • Work = Work + Allocation (Work = 가용한 자원 개수 + 할당된 자원 개수)
   • Finish[i] = true
4. 모든 i 값에 대하여 Finish[i] == true 이면 이 시스템은 안전 상태에 있다.

자원 요청 알고리즘

자원 요청이 안전하게 들어줄 수 있는지 검사.

1. 만일 Request ≤ Need 이면 2번으로 간다.
   • 아니면 시스템에 있는 개수보다 더 많이 요청했으니 오류 처리.
2. 만일 Request ≤ Avaliable 이면 3번으로 간다.
   • 아니면 요청 자원이 당장은 없으니 기다려야 한다.
3. 마치 시스템이 Ti 에게 자원을 할당해준 것처럼 시스템 상태 정보를 바꾼다.
   • 만일 이렇게 바뀐 상태가 안전하면, Ti 에 여기에 반영된 정보대로 자원을 할당.
   • 불안전하다면, 자원 할당 상태는 원상태로 복원되고 Ti 은 Request 가 만족하기까지 기다림.
4. Avaliable = Avalible - Request(i) Allocation(i) = Allocation(i) + Request(i) Need(i) = Need(i) - Request(i) // 가용 자원 개수 = 가용 자원 - 요청 자원 // 스레드에 현재 할당된 개수 = 현재 할당된 자원 + 요청 자원 // 스레드가 향후 요청할 수 있는 자원 개수 = 요청할 수 있는 자원 - 요청 자원

💡 교착상태 예방, 방지 알고리즘을 사용하지 않으면 교착 상태가 발생할 수 있고, 다음 알고리즘을 반드시 지원해야 한다.

• 교착상태 탐지 알고리즘
• 교착상태 회복 알고리즘

단, 탐지와 회복 알고리즘은 필요한 정보 유지하며 탐지 알고리즘을 실행시키는 시간 + 교착 상태로부터 회복할 때까지 시간 까지도 포함하여 오버헤드가 발생한다고 봐야 한다.

 

교착 상태 탐지

각 자원 유형이 한 개씩 있는 경우 → 대기 그래프 알고리즘

대기 그래프(wait-for graph) 라고 하는 자원 할당 그래프의 변형을 사용해 교착 상태 탐지 알고리즘 정의.

• 대기 그래프가 사이클을 포함하는 경우에만 시스템 교착 상태가 존재한다.
  • 교착상태 탐지를 위해 대기 그래프를 유지
  • 주기적으로 그래프에서 사이클을 탐지하는 알고리즘 호출

각 유형의 자원을 여러 개 가진 경우

은행원 알고리즘과 마찬가지로 시시각각 내용이 달라지는 자료 구조를 이용한다.

• Available : 각 종류 자원이 현재 몇 개가 가용한지
• Allocation : 각 스레드에 현재 할당된 자원 개수
• Request : 각 스레드 현재 요청 중인 자원의 개수

→ 가능한 모든 할당 순서를 조사해보는 방식으로 이루어진다.

예시

• n = 3개의 프로세스 (P1, P2, P3)
• m = 3개의 자원유형 (A,B,C)

상태

프로세스	Allocation	Request	Available
P1	(0, 1, 0)	(1, 0, 2)	(3, 3, 2)
P2	(2, 0, 0)	(2, 0, 2)
P3	(3, 0, 3)	(0, 0, 0)

 

1. Work 와 Finish 초기화

• Work = Available = (3, 3, 2)
• Finish[i] 값 설정
  • Allocation ≠ 0 → Finish[i] = false

→ P1, P2, P3 모두 할당 자원이 0이니 false

Work = (3, 3, 2)
Finish = [false, false, false]

 

2. 조건 만족하는 i 찾기

반복문을 돌면서 다음 조건을 만족하는 프로세스 찾기

• Finish[i] = false
• Request[i] ≤ Work

P1 검사

• Request[1] = (1, 0, 2)
• Work = (3, 3, 2)

→ Request[1] ≤ Work 만족 → P1 선택

 

3. 자원 할당 및 Work 업데이트

P1 이 실행 가능하므로, 해당 프로세스의 할당된 자원을 Work 에 추가하고 Finish[i] 를 true 로 설정.

Work = Work + Allocation[1] = (3, 3, 2) + (0, 1, 0) = (3, 4, 2)
Finish[1] = true

 

4. 다음 프로세스 찾기

남은 프로세스 중, 조건을 만족하는 프로세스 찾기.

P2 검사

• Request[2] = (2, 0, 2)
• Work = (3, 4, 2)

→ Request[2] ≤ Work 만족 → P2 선택

Work = Work + Allocation[2] = (3, 4, 2) + (2, 0, 0) = (5, 4, 2)
Finish[2] = true

 

 

5. 다음 프로세스 찾기

마지막 P3 를 검사해보자~!

P3 검사

• Request[3] = (0, 0, 0)
• Work = (5, 4, 2)

→ Request[3] ≤ Work 만족 → P3 선택

Work = Work + Allocation[3] = (5, 4, 2) + (3, 0, 3) = (8, 4, 5)
Finish[3] = true

 

6. 교착 상태 판별

모든 Finish[i] == true 면 교착 상태가 발생하지 않음.

Finish = [true, true, true]

• 고로 시스템은 안전 상태에 있음!

탐지 알고리즘 사용

탐지 알고리즘은 언제 돌릴까? 두 가지 관점이 있다.

1. 교착 상태가 얼마나 자주 일어나는가?
2. 교착 상태가 일어나면 통상 몇 개의 스레드가 거기에 연루되는가?

언제 돌립니까?

1. 당연히 자주 일어날 경우 탐지 알고리즘도 자주 돌려야 함.
2. 극단적으로는 스레드 요청이 즉시 만족되지 않을 때마다 탐지 알고리즘을 돌릴 수 있음.
   • 이 경우 교착 상태를 야기한 장본인 스레드도 알아낼 수 있음.
   • 오버헤드를 줄이는 간단한 대안 → 지정된 시간 간격
     • 예) 한 시간에 한 번 또는 CPU 이용률이 40% 이하로 떨어질 때.

교착 상태로부터 회복

1. 단순히 한 개 이상의 스레드를 중지(abort)
2. 교착 상태에 있는 하나 이상의 스레드들로부터 자원을 선점(preempt)

프로세스와 스레드의 종료 abort

1. 교착 상태 프로세스를 모두 중지
   • 비용이 크다. → 오랫동안 연산했을 가능성이 있는 결과물을 반드시 폐기해야 함 ㅠㅠ.
2. 교착 상태가 제거될 때까지 한 프로세스씩 중지
   • 상당한 오버헤드. → 프로세스가 중지될 때마다 교착 상태 탐지 알고리즘을 호출해야 함.

→ 그나마 프로세스들을 중지시켰을 때 유발되는 비용이 최소인 프로세스들을 중지시켜야 함..

어느 프로세스를 종료할지 결정해야 할까?

1. 프로세스 우선순위가 뭔지
2. 지금까지 프로세스가 수행된 시간과 지정된 일을 종료하는 데 더 필요한 시간.
3. 프로세스가 사용한 자원 유형과 수(예를 들어, 자원들을 선점하기 단순한가?)
4. 프로세스가 종료하기 위해 더 필요한 자원의 수
5. 얼마나 많은 수의 프로세스가 종료되어야 하는지?

자원 선점 preempt

교착 상태가 깨질 때까지 프로세스로부터 자원을 계속 선점해 다른 프로세스에 주어야 함.

1. 희생자 선택(selection of a victim)
   • 비용을 최소화하기 위해 선점 순서를 결정.
   • 비용 : 교착 상태 프로세스가 점유하고 있는 자원의 수, 실행하는데 소요한 시간 같은 매개 변수
2. 후퇴(rollback)
   • 안전한 상태로 후퇴시키고 그 상태로부터 다시 시작
   • “안전 상태”를 결정하긴 어려우니 보통 프로세스를 중지시키고 재시작
   • 프로세스를 교착 상태를 깨뜨릴 수 있을 정도로 후퇴시키면 좋으나, 이건 대신 프로세스 상태에 더 많은 정보를 유지해야 한다.
3. 기아 상태(starvation)
   • 프로세스가 작은 한정된 시간 동안만 희생자로 선정된다는 것을 반드시 보장해야 한다. → 언젠가 이 프로세스가 실행되어야 하며, 기아 상태가 되어선 안된다.
   • 일반적으로 비용 요소의 후퇴 횟수를 포함하면 기아 상태를 막을 수 있음.

요약 ! ! ! !!!

• 집합의 모든 프로세스가 같은 집합의 다른 프로세스에서만 발생할 수 있는 이벤트(자원 반환)을 기다리는 경우, 교착 상태가 발생한다.
• 교착 상태에 필요한 네 가지 조건 → 4개 모두 만족해야 교착 상태
  • 상호 배제 : 자원 공유 X
  • 점유하며 대기 : 점유 + 다른 자원 기다림
  • 비선점 : 자원 강제 방출 X
  • 순환 대기 : 서로가 서로를 사이클로 기다리는 상황.
• 교착 상태는 자원 할당 그래프를 사용하여 모델링 가능 → 사이클이 있으면 교착 상태
• 교착 상태에 필요한 4가지 조건 중, **순환 대기를 제거**하는 게 유일하게 현실적인 방법 ^^
• 은행원 알고리즘 : 최대 자원 수를 정의하고, 그걸 통해 자원 점유를 관리
• 교착 상태 감지 알고리즘 : 자원이 충족될 수 있는지 주기적으로 검사.
• 교착상태 발생 시 복구 시도 방법 2가지
  • 순환 대기 중인 프로세스 중 하나를 중단.
  • 교착 상태의 프로세스에 지정된 자원을 선점.