DeadLock(데드락)

데드락

자원이 한정되어 있어서 상대방이 자원을 다 쓰고 돌려줘야 하는 상황에서 서로 기다려서 무한히 기다림에 빠져버리는 현상이다.

프로세스1과 2가 자원 1,2를 모두 얻어야 한다고 가정한다.
Process1 : 프로세스 1이 자원 1을 얻음 / 프로세스2가 자원2를 얻음
Process2 : 프로세스 1은 자원2를 기다림 / 프로세스2는 자원1을 기다림

운영체제에서 대부분은 데드락 상태는 임계구역에 코드를 작성하기 위해 세마포어를 차지하려는 경쟁에서 발생한다. 이에 멀티쓰레드환경에서 개발할 때, 항상 데드락의 가능성을 항상 염두해두고 개발해야한다.

데드락 발생 조건

데드락의 4가지 필요 조건

여기서 필요조건이란 4가지 조건을 동시에 만족할 때, 데드락에 빠질 수 있다는 것을 의미한다. 주의할 점은 4자기 조건이 다 만족했다고 하여 꼭 데드락 상태로 빠지는 것이 아니다. 즉, 데드락에 빠졌다면 필요조건 4가지는 꼭 만족한 상태라는 것이다.

1. Mutual Exclusion(상호 배제)
프로세서들이 자원을 배타적 점유한 상태이고, 다르 프로세서들이 자원을 사용 불가한 상태이며 한번에 한 프로세스만 자원이 사용 가능하다. 다른 프로세스가 사용하려면 요청한 자원이 해제 될 때 까지 기다려야 한다.
-> 쉽게 말하면 상호 배제한다는 것은 자원을 남에게 공유하지 않고 자신만 쓰는 상황을 말한다.
2. Hold and Wait(점유 대기)
부분할당, 다른 종류의 자원을 부가적으로 요구하면서, 이미 어떤 자원을 점유하고 있음
-> 내가 어떤 공유된 자원(Shared data)를 가진 상태(hold)에서 또 다른 것을 요구(wait)할 때 발생된다.
3. No Preemption(비선점)
자원들은 그들이 점유하고 있는 프로세스로부터 도중에 해제 되지 않음, 이미 할당된 자원을 강제로 빼앗을 수 없다.
-> shared data를 가졌는데 더 이상 진행이 안될 때, 그 shared data를 내려놓으면 preemption이고, 내려 놓지 않으면 no preemption이다.
4. Circular Wait(환형 대기)
대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

위 교통 체증 예에서 필요조건을 확인해보면 4가지 모두 만족하고 있다.
1. Mutual Exclusion - 하나의 차량은 그 순간에 하나의 구간만 차지 한다.
2. Hold and Wait - 각 차량들이 도로에서 하나의 구간을 차지하면서 나아가기만을 기다리고 있다.
3. No preemption - 하나의 구간이 양보될 수 없는 상황(선점할 수 없는 상황)이다.
4. Circular wait - 원형으로 기다리고 있는 상태

데드락 처리방법

데드락을 Handling 하는 방법은 4가지가 있다.

• Prevention(교착상태 예방) : 교착상태의 필요조건을 부정함으로써 교착상태가 발생하지 않도록 미리 예방하는 방법(ex 환형대기, 비선점, 점유와대기, 상호배제 4가지 부정)

• Avoidance(교착상태 회피)
  교착상태 가능성을 배제하지 않고 적절하게 피해나가는 방법(ex Banker's algorithm)

• Detection(교착상태 탐지)
  교착상태 발생을 허용하고 발생 시 원인을 규명하여 해결하는 방법

• Recovery(교착상태 복구)
  교착상태 발견 후 환형대기를 배제하거나 자원을 중단하는 메모리 할당 기법
  (ex 선점, 프로세스 중지(희생자 선택))

---

1. Deadlock Prevention

   데드락이 발생될 가능성을 아예 예방하자는 방법이다. 데드락 발생 필요조건 4가지를 충족시키지 않도록 미리 설계하여 예방한다.

   • 자원의 상호 배제 조건 방지 : 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다. 그러나 추후에 동기화 관련해서 문제가 발생할 수 있다.
   • 점유 대기 조건 방지 : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때 까지 작업을 보류해서, 나중에 또 다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 한다.
   • 비선점 조건 방지 : 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.
   • 순환 대기 조건 방지 : 자원을 순환 형태로 대기하지 않도록 일정한 한쪽 방향으로만 자원을 요구할 수 있도록 한다.

   이러한 조건들을 방지해서 데드락을 예방하는 방법은 시스템의 처리량이나 효율성을 떨어트리는 단점이 발생 할 수 있다. 데드락 회피법은 조금 덜 제한적인 방법으로 예방법의 단점을 일부 해결할 수 있다.

2. Deadlock Avoidance

   시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례대로 모두에게 할당 해 줄 수 있다면 안정 상태(safe state)에 있다고 말한다.

   그리고 이처럼 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 그것을 안전 순서(safe sequence) 라고 부른다.

   반면 불안정 상태는 안정 상태가 아닌 상황을 말한다. 즉, 데드락 발생 가능성이 있는 상황이며, 교착 상태(데드락)는 불안정 상태일 때 발생할 수 있다. 데드락은 불안정 상태의 부분 집합인 상태이다.

   회피 알고리즘은 자원을 할당한 후에도 시스템이 항상 Safe state에 있을 수 있도록 할당을 허용하자는 것이 기본 특징이고 이 특징을 살린 알고리즘으로 유명한 것이 은행원 알고리즘이다.

3. Deadlock Detection

   Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색한다. 즉, 은행원 알고리즘에서 했던 방식과 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악한다. 이 외에도 자원 할당 그래프를 통해 탐지하는 방법도 있다.

4. Deadlock Recovery

   데드락을 탐지 기법을 통해 발견했다면, 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용한다.

   1. 단순히 프로세스를 1개 이상 중단시키기
      • 교착 상태에 빠진 모든 프로세스를 중단시키는 방법 : 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기가 될 수 있는 부작용이 발생할 수 있다.
      • 프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있다.
   2. 자원 선점하기
      • 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해주는 법