[운영체제] 8. Deadlocks (교착 상태)

아래 도서 기반 정리

운영체제 | Abraham Silberschatz - 교보문고

 

목차

• Deadlocks
• 시스템 모델
• 멀티 스레드 응용에서의 교착 상태
• 교착 상태 특성
• 교착 상태 처리 방법
• 교착 상태 예방
• 교착 상태 회피
• 교착 상태 탐지
• 교착 상태로부터 회복

 

Deadlocks (교착 상태)

 

---

두 개 이상의 프로세스들이, 오로지 대기중인 프로세스들 중 하나에 의해서만 야기될 수 있는 이벤트를
무한정 기다리는 상황이 발생했을 때 이 프로세스들이 교착상태라고 한다.

• 프로세스가 리소스를 점유하고 놓아주지 않는 상태
• 어떠한 프로세스도 리소스를 점유하지 못하는 상태

ex) 식사하는 철학자 문제

2가지 전제

1. 컴퓨터 시스템에 여러개의 병렬 스레드와 프로세스가 존재해야 한다.
2. 컴퓨터 시스템을 구성하는 자원은 유한하다.

 

시스템 모델 (System Model)

---

시스템은 경쟁하는 스레드들 사이에 분배돼야 할 유한한 수의 자원들로 구성된다.
자원은 다수의 유형으로 분할되고, 각각은 동등한 다수의 인스턴스들로 구성된다.

한 스레드가 한 인스턴스를 요청하면, 동일 유형 자원의 임의의 인스턴스를 할당함으로써 요청이 충족된다.

 

프로세스 자원 사용 순서

1. 요청 (Request)
   • 스레드가 자원을 요청한다.
   • 요청이 즉시 허용되지 않으면, 요청 스레드는 자원을 얻을때까지 대기한다.
2. 사용 (Use)
   • 스레드는 자원에 대해 작업을 수행할 수 있다.
3. 방출 (Release)
   • 스레드가 자원을 방출한다.

 

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

ex)

• 세마포 획득과 방출 : wait(), signal()
• mutex lock 획득과 방출 : acquire(), release()

 

멀티 스레드 응용에서의 교착 상태

---

라이브락 (Livelock)

라이브니스 장애로, 교착 상태와 유사하다.
스레드가 실패한 행동을 계속해서 시도할 때 발생한다.

• 두 사람이 복도를 지나갈 때 서로 같은 방향으로 피하는 일이 발생하는 현상과 유사하다.
  무한 대기가 아닌 서로 동일한 작업을 해 부딪히는 것이다.
• 일반적으로 각 스레드가 실패한 행동을 재시도하는 시간을 무작위로 정하면 회피할 수 있다.

 

교착 상태 특성 (Deadlock Characterization)

---

교착상태 필요 조건들 (mecessary Conditions)

데드락은 다음 상황을 모두 만족해야 발생한다.

1. 상호 배제 (mutual exclusion)

• 최소한 하나의 자원이 비공유 모드로 점유되어야 한다.
• 비공유 모드에서는 한 번에 한 스레드만이 그 자원을 사용할 수 있다.
• 다른 스레드가 그 자원을 요청하면, 요청 스레드는 자원이 방출될 때까지 반드시 지연돼야 한다.

2. 점유하며 대기 (hold-and-wait)

• 스레드는 최소한 하나의 자원을 점유한 채, 현재 다른 스레드에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.

3. 비선점 (no preemption)

• 자원들을 선점할 수 없어야 한다.
• 자원이 강제적으로 방출 불가하고, 점유하고 있는 스레드가 태스크를 종료한 후 그 스레드에 의해 자발적으로만 방출 가능하다.

4. 순환 대기 (circle wait)

• 프로세스가 순환적으로 서로 점유한 자원을 대기하는 것이다.
  ex) T0 -> T1 -> T2 -> ... -> T0

 

+++
순환 대기 조건은 비선점과 점유하며 대기 조건이 만족되어야 성립된다.
따라서 네 조건이 완전히 독립적이지 않다.

 

교착 상태 처리 방법 (Methods for Handling Deadlocks)

---

1. 문제를 무시하고, 교착 상태가 시스템에서 발생하지 않는 척한다.

• 다른 처리방법보다 비용이 적게 든다.
• 대부분의 시스템은 교착 상태가 잘 발생하지 않기 때문에 Linux, Window 등 대부분의 운영체제가 사용하는 방법이다.
• 교착 상태를 처리하는 프로그램 작성은 응용 개발자의 몫이다.

2. 시스템이 결코 교착상태가 되지 않도록 예방하거나 회피하는 프로토콜을 사용한다.

• 교착 상태 예방 (prevention)
• 교착 상태 회피 (avoidence)

3. 시스템이 교착 상태가 되도록 허용한 다음 복구시킨다.

• 교착상태가 발생했는지 시스템 상태를 조사하는 알고리즘과
  교착상태로부터 복구하기 위한 알고리즘을 제공할 수 있다.

 

교착 상태 예방

---

교착 상태가 발생하기 위한 네가지 필요 조건들 중 최소한 하나가 성립하지 않도록 하는 방법이다.
자원이 어떻게 요청될 수 있는지를 제한해 교착 상태를 예방한다.

상호 배제 (Mutual exclusion)

• 적어도 하나의 자원은 공유가 불가능한 자원이어야 상호 배제 조건이 성립한다.
• 어떤 자원들은 근본적으로 공유가 불가능하기 때문에, 일반적으로 상호 배제 조건을 거부함으로써 교착 상태를 예방하는 것은 불가능하다.

점유하며 대기(Hold-and-Wait)

• 스레드가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용한다.
• 스레드가 일부 자원을 요청하고 사용할 수도 있다.
• 스레드가 추가의 자원을 요청하려면, 자신에게 할당된 모든 자원을 반드시 먼저 방출해야 한다.
• 단점
  • 자원이 할당된 후 장시간 사용되지 않을 수 있다.
  • 기아가 발생할 수 있다.
• 대부분의 응용프로그램에선 실용적이지 않다.

비선점 (No Preemtion)

• 어떤 자원을 점유하고 있는 스레드가 즉시 할당받지 못 하는 자원을 요청하면,
  현재 점유하고 있는 모든 자원을 방출한다.
• 교착상태가 가장 흔하게 발생하는 mutex lock과 semaphore에선 일반적으로 적용할 수 없다.

순환 대기 (Circular Wait)

• 모든 자원 유형에 전체적인 순서를 부여해, 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구하는 것이다.
• 가장 실용적인 해결책이다.

 

교착 상태 예방의 단점

• 장치 이용률 저하
• 시스템 총처리율 감소

 

교착 상태 회피

---

자원이 어떻게 요청될지에 대한 추가 정보를 제공하는 방법이다.
각 요청에 대해서 가능한 미래의 교착 상태를 피하고자 스레드가 대기해야 하는지 여부를 결정할 수 있다.

교착 상태 회피 알고리즘은 시스템에 순환 대기 상황이 발생하지 않도록 자원 할당 상태를 검사한다.

단점

• 장치 이용률 저하
• 시스템 총처리율(throughput) 감소

 

안전 상태 (Safe State)

시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원을 교착 상태를 야기시키지 않고, 차례로 모두 할당해 줄 수 있다는 것을 뜻한다.

즉, 안전 순서(safe sequence)를 찾을 수 있다면 시스템은 안전하다고 한다.
모든 스레드를 무사히 마칠 수 있는 시퀀스를 못 찾으면 불안전(unsafe) 하다고 한다.

따라서 기본 원칙은 시스템의 상태가 항상 안전 상태를 떠나지 않도록 고수하는 것이다.

단점

• 이러한 방식은 자원을 많이 보유하고 있어도, 프로세스를 기다리게 하는 상황이 벌어질 수 있어 자원 이용률은 회피를 안 쓸때에 비해 낮아질 수밖에 없다.

 

자원 할당 그래프 알고리즘 (Resource-Allocation Graph Algorithm)

교착 상태 회피를 위해 사용한다.
자원 할당 그래프에 사이클을 형성하지 않을 때만 요청을 허용할 수 있다.
사이클이 없다면 자원을 할당해도 안전 상태다.

 

은행원 알고리즘 (Banker's Algorithm)

스레드가 자원을 요청하면, 시스템이 그것을 들어주었을 때 계속 안전상태에 머무르게 되는지 여부를 판단하는 알고리즘

• 스레드가 자원 요청 시, 시스템이 그것을 들어주었을 때 시스템이 계속 안전 상태에 머무르게 되는지 여부를 판단한다.
• 계속 안전하다면, 요청을 들어준다.
• 안전하지 않다면, 이 스레드의 요청은 허락이 안 된 채 다른 스레드가 끝날 때까지 기다리게 된다.

 

교착 상태 탐지 (Deadlock Detection)

---

교착 상태 예방과 교착 상태 방지 알고리즘을 사용하기 위해선 다음 알고리즘을 반드시 지원해야 한다.

• 교착 상태가 발생했는지 결정하기 위해, 시스템 상태를 검사하는 알고리즘
• 교착 상태로부터 회복하는 알고리즘

탐지 알고리즘 사용

탐지 알고리즘을 언제 돌릴지는 두 가지 관점에 달려있다.

• 교착 상태가 얼마나 자주 일어나는가?
  • 교착 상태가 자주 일어난다면, 탐지 알고리즘도 자주 돌려야 한다.
  • 시간이 지날수록, 교착 상태에 연루되는 스레드가 늘어날 수 있기 때문이다.
• 교착 상태 발생 시, 통상 몇 개의 스레드가 거기 연루되는가?
  • 때에 따라 어떤 요청이 여러 스레드의 요청을 연결해 둥그런 고리 모양의 사슬을 완성하는 마지막 요청일 수도 있다.
  • 만일 자원이 여러 종류라면, 한 자원에 대한 단 한개의 요청이 그래프 상에서 여러 사이클을 한 번에 만들게 되는 결과를 초래할 수도 있다.

 

교착 상태로부터 회복

---

교착 상태 처리 방법

• 운영자가 수작업으로 처리
• 시스템이 자동으로 회복

교착 상태 깨트리는 방법

• 순환 대기를 깨뜨리기 위해, 한 개 이상의 스레드를 중지시키기
• 교착 상태에 있는 하나 이상의 스레드들로부터 선점하기

 

프로세스와 스레드의 종료

1. 교착 상태 프로세스를 모두 중지

• 프로세스가 오랫동안 연산했을 가능성이 있고, 부분 계산 결과를 폐기하고 후에 다시 계산해야한다.
  때문에 비용이 크다.

2. 교착 상태가 제거될 때까지 한 프로세스씩 중지

• 각 프로세스가 중지될 때마다 교착 상태 탐지 알고리즘을 호출해야한다.
  따라서 상당한 오버헤드를 유발한다.

 

자원 선점

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

1. 희생자 선택 (selection of a victim)

• 비용을 최소화하기 위해 선점의 순서를 결정해야 한다.

2. 후퇴 (rollback)

• 자원을 선점하기 위해, 프로세스를 안전한 상태로 후퇴시키고, 그 상태부터 다시 시작해야 한다.

3. 기아 상태(starvation)

• 계속 같은 프로세스가 희생자가 될 수 있다.