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

* 교착상태 처리 방법 분류

• 교착상태가 절대 생기지 않도록 보장
  • 교착상태 예방 (Deadlock prevention)
  • 교착상태 회피 (Deadlock avoidance)
• 교착상태가 되도록 허용, 다음에 복구
  • 교착상태 탐지 (Deadlock Detection)
  • 교착상태 회복 (Deadlock Recovery)
• 교착상태 무시

 

1. 교착상태 예방 (Deadlock prevention)

• 교착 상태를 발생하는 하는 4가지 조건 중에 적어도 하나가 일어나지 않게 보장함으로써 교착상태를 예방

(1) 상호 배제 (Mutual Exclusion)

• 공유 가능한 자원들의 배타적인 접근을 요구하지 않는다.
• 예를 들어, 읽기 전용 파일 (read-only file)에 대해서는 배타적 접근이 필요하지 않는다.
• 반면에, 프린터 등의 비공유 자원의 경우는 배타적 접근이 보장되어야 한다.

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

• 프로세스가 자원을 요청할 때마다 다른 자원을 점유하지 않았음을 보장한다.
• 방법 1) 프로세스가 실행 시작 전에 필요한 모든 자원을 요청하여 모두 할당받는다.
  • 낮은 자원 이용률을 야기한다.
• 방법 2) 프로세스가 아무 자원도 점유하고 있지 않을 때만 자원을 요청한다.
  • 순차적 자원 할당이 이뤄진다. 기아(starvation) 발생할 수 있다.

(3) 비선점 (No Preemption)

•  한 개 이상의 자원을 점유한 프로세스가 즉시 할당받을 수 없는 추가의 자원을 요청한다면, 현재 잡고 있는 모든 자원을 내려놓는다.
• 선점된 자원은 기다리고 있는 프로세스를 위한 자원 목록에 추가된다.
• 프로세스는 요청했던 새로운 자원뿐만 아니라 이전에 소유했던 자원까지 모두 다시 얻었을 때, 다시 시작된다.
• CPU 레지스터, 메모리 등 그 상태가 저장/복원 가능한 경우에 사용되나, 프린터처럼 자원을 얻고 푸는 행위는 비용이 크기 때문에 적합하지 않다.

(4) 순환 대기 (Circular Wait)

• 모든 자원 타입들에 대해 전체적으로 순서(order)를 부여한다.
• 각 프로세스는 오름차순으로만 지원을 요청할 수 있다.
• 사이클이 발생하지 않으므로 교착상태가 발생하지 않으나, 오름차순 요청은 자원을 활용하는데 큰 제약 조건이 된다.

* 교착상태 예방(Deadlock Prevention)의 단점

• 교착상태 예방에서 발생하는 부작용(side effects)이 크다. 
• 낮은 장치 사용률
• 감소된 시스템 처리량

 

2. 교착상태 회피 (Deadlock avoidance)

• 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것
• 각 스레드가 요청할 각 유형의 자원의 최대 수 정보를 미리 파악할 수 있다면, 시스템이 교착 상태에 들어가지 않을 것을 보장한다.

(1) 안전 상태 (Safe State)

• 시스템 상태가 안전하다는 말은 시스템이 어떤 순서로든 스레들이 요청하는 모든 자원을 교착 상태를 야기시키지 않고 차례로 모두 할당해 줄 수 있다는 것을 뜻한다.
• 시스템의 상태가 안전하다면 교착 상태가 아니다.
• 시스템 상태가 불안전하다면 교착 상태가 발생할 가능성이 있다.
• 교착상태 회피는 시스템이 불안전 상태로 되는 것은 막아준다.

(2) 자원 할당 그래프(Resource-Allocation Graph)

• 자원 유형마다 하나의 인스턴스를 가지는 경우 (Single Instance of a resource type)
• 예약 간선(claim edge) 도입
•  

• R2는 현재 가용 상태이나 이를 P2에 할당할 수 없다.
  • 할당할 경우 사이클 발생

• R2가 P2에 할당되었다 가정
• 사이클을 형성하므로 Deadlock 발생가능하다. (unsafe) => 회피한다.

 

(3) 은행원 알고리즘(Banker's Alogrithm) 사용

• 자원 종류마다 자원이 여러 개씩 있는 경우 (Multiple instances of a resource type)
• 자료구조
  • Available : 각 종류별로 가용한 자원의 개수를 나타내는 벡터 (m)
  • Max : 각 프로세스가 최대로 필요로 하는 자원의 개수를 나타내는 행렬 (n * m)
  • Allocation : 각 프로세스에 현재 할당된 자원의 개수를 나타내는 행렬 (n * m)
  • Need : 각 프로세스가 향후 요청할 수 있는 자원의 개수를 나타내는 행렬 (n * m)
• 안정성 알고리즘  (Safety Algorithm)
  • 시스템이 안전하진 아닌지를 판단
  • 알고리즘
    • 1. Work와 Finish는 크기가 m과 n인 벡터. Work = Available로 초기 값. i = 0,1,...,n-1에 대해서 Finish[i]=false
    • 2. 아래 두 조건을 만족시키는 i 값을 찾는다.
      • a. Finish[i] == false
      • b. Need[i] <= Work
      • 이러한 i 값을 찾을 수 없다면 step 4 이동
    • 3. Work = Work + Allocation[i], Finish[i] = true, 2번으로 이동
    • 4. 모든 i 값에 대해 Finish[i] == true이면 이 시스템은 안정 상태에 있다.
• 자원 요청 알고리즘 (Resource-Request Algorithm)
  • 자원 요청이 안전하게 들어줄 수 있는지를 검사
  • 알고리즘
    • 1. Request[i] <= Need[i]이면 2번 이동. 아니면 시스템에 있는 개수보다 더 많이 요청했으므로 오류 처리
    • 2. Request[i] <= Available이면 3번 이동. 아니면 요청한 자원이 당장은 없으므로 P[i]는 기다려야 한다.
    • 3. 시스템 P[i]에게 자원을 할당해준 것처럼 시스템 상태 정보를 아래처럼 바꾸어 본다.
      • Available = Available - Request[i]
      • Allocation[i] = Allocation[i] + Request[i]
      • Need[i] = Need[i] - Request[i]
      • 만약 이렇게 바뀐 상태가 안전하다면 P[i]에 여기에 반영된 정보대로 자원을 할당
      • 그러나 새로운상태가 불안전하다면, 위 자원 할당 상태는 원상태로 복원되고 P[i]는 Request[i]가 만족하기까지 기다려야한다.
• Example
  • 5 processes P[0] through P[4]
  • 3 resource types
    • A (10 instances), B (5 instances), C (7 instances)

• <P1, P3, P4, P0, P2> 순서로 안전성 조건을 만족시킨다.
• 안전성 조건을 만족시키는 순서를 한개라도 찾으면 Safe state이다.

 

* 교착상태가 되도록 허용, 다음에 복구

• 시스템의 성능 저하 방지를 위해 교착상태 예방(prevention)이나 회피(avoidance)를 하지 않는다면 시스템은 교착 상태에 들어갈 수 있으며, 이 환경에서 시스템은 2가지 알고리즘을 지원한다.
• 교착상태 탐지(Deadlock Detection) 알고리즘
• 교착상태로부터 회복(Deadlock Recovery) 알고리즘

 

3. 교착상태 탐지 (Deadlock Detection)

(1) 대기 그래프 (wait-for graph)

• 각 자원 유형이 한 개씩 있는 경우 (Single Instance of a resource type)

(2) 탐지 알고리즘 (Detection Algorithm)

• 각 유형의 자원을 여러 개 가진 경우 (Multiple instances of a resource type)
• 자료구조
  • Available : 각 종류의 자원이 현재 몇 개가 가용하지를 나타내는 벡터 (m)
  • Allocation : 각 프로세스에 현재 할당된 자원의 개수를 나타내는 행렬 (n * m)
  • Request : 각 프로세스가 현재 요청 중인 자원의 개수를 나타내는 행렬 (n * m)
• 알고리즘 
  • 1. Work와 Finish는 크기가 m과 n인 벡터. Work = Available로 초기값. i = 0,1,...,n-1에 대해서 Allocation[i]!=0이면 Finish[i]=false이다. 그렇지 않으면 Finish[i]=true이다.
  • 아래 두 조건을 만족시키는 i 값을 찾는다.
    • a. Finish[i] == false
    • b. Request[i] <= Work
    • 그러한 i 값을 찾을 수 없다면 4번으로 이동
  • Work = Work + Allocation[i], Finish[i] = true, 2번으로 이동
  • 어떠한 i 값에 대해 (0<=i<n) Finish[i] == false이면 이 시스템은 교착 상태이다.
• Example

• <P0, P2, P3, P1, P4> 순서와 같이 작업을 다 끝낼 수 있고 모든 i에 대해서 Finish[i] == true

(3) 탐지 알고리즘의 사용

• 언제, 얼마나 자주 탐지 알고리즘을 호출할 것인가?
• 자원을 요청할 때마다 탐지 알고리즘을 호출
  • 오버헤드가 매우 크다
• 어떤 프로세스가 자원을 요청했는데 그것이 즉시 만족되지 못하는 시점에 호출
  • 교착상태와 관련된 프로세스들을 알 수 있고, 누가 교착상태를 유발했는지 알 수 있다.
• 지정된 시간 간격으로 호출
  • 한 시간에 한 번 CPU 이용률이 40% 이하로 떨어질 때

 

4. 교착상태 회복 (Deadlock Recovery)

(1) 운영자에 의한 해결

• 교착상태 발생을 운영자에게 알리고, 운영자가 교착상태를 수작업으로 처리한다.
• 오늘날의 컴퓨터 시스템에서는 비현실적 방법

(2) 프로세스 종료 (process termination)

• 교착상태 프로세스를 모두 중지
  • 확실하게 교착상태의 사이클을 제거하나, 비용이 많이 들게 된다.
• 교착상태가 제거될 때까지 하나씩 중지
  • 중지되는 프로세스 수는 줄일 수 있으나, 중지 후 문제가 해결되었는지 확인을 위해 교착상태 탐지 알고리즘을 계속 호출해야 하는 오버헤드 발생

(3) 자원 선점 (resource preemption)

• 교착상태가 깨질 때까지 프로세스로부터 자원을 선점해(빼앗아) 다른 프로세스에게 준다.
• 자원 선점의 세 가지 요소
  • 희생자 선택(selection of a victim) 비용 최소화
    • 프로세스가 점유한 자원의 수, 지금까지 소요한 시간 등을 고려한다.
  • Rollback(프로세스를 안전한 상태까지 되돌리고 그 상태에서부터 재시작)
    • 교착상태를 해결할 수 있는 수준까지 rollback 시킨다.
  • 같은 프로세스가 항상 희생자로 선택될 수 있으므로 기아(starvation) 발생 가능
    • 희생자를 선택할 때, rollback 된 횟수를 고려한다.

 

5. 교착상태를 무시

• Linux와 Windows를 포함해 대부분의 운영체제가 사용하는 방법
• 교착 상태를 무시하는 것이 다른 처리 방법과 비교해 비용이 적게 든다.
• 많은 시스템에서 교착 상태는 드물게 발생하기 때문에 교착 상태 처리에 대한 부가적인 비용은 그만한 가치가 없다.
• 교착 상태를 처리하는 프로그램을 작성하는 것은 개발자의 몫