교착상태2

교착 상태

교착 상태 회피

교착 상태 성립 조건(4가지 조건)중 한 가지는 성립되지 않도록 하는 방법은 장치의 이용률을 저하시키고 시스템의 총처리율을 감소시킨다.

 

교착 상태를 회피하는 다른 대안

• 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구한다.
  • 가용 자원, 각 스레드에 할당된 자원, 각 스레드가 요청하거나 방출할 자원의 정보 등
• 자원 R1, R2를 가진 시스템에서
  • 스레드 P는 R1을 먼저 요청하고 R2를 요청
  • 스레드 Q는 R2를 먼저 요청하고 R1을 요청
• 각 스레드의 요청과 방출에 대한 완전한 순서를 파악하고 있다면 교착 상태를 피하고자 스레드가 대기해야 하는지 여부를 결정할 수 있다.

안전 상태

안전 상태(Safe State)

• 각 스레드들이 요청하는 모든 자원(최대 요구 수를 요구하더라도) 교착 상태를 발생 시키지 않고 차례로 모두 할당해줄수 있는 상태
• 안전 순서(safe sequence)를 찾을 수 있으면 시스템은 안전하다.
  • Ti스레드가 끝났을 때 Ti+1 스레드가 필요한 모든 자원을 얻고 이와 같은 상황이 계속되면, 모든 스레드는 무사히 마칠 수 있다.
• 순서를 찾을 수 없으면 불안전(unsafe) 하다.

그림에 대한 설명

• 불안전 상태라고 항상 데드락이 발생하지는 앟는다.
  • 하지만 데드락은 불안전 상태에서 발생함
• 안전 상태에서는 데드락 상태를 막을 수 있다.

교착 상태 회피 알고리즘의 기본 원칙은 시스템의 상태가 항상 안전 상태를 떠나지 않도록 고수하는 것이다.

자원 할당 그래프 알고리즘

• 각 자원 유형마다 하나의 인스턴스를 갖는 자원 할당 시스템
• 예약 간선(claim edge)를 도입한다.
  • 점선(--)으로 표시되며 T1 -> R2는 T1이 미래에 R2를 요청할 것임을 나타낸다.
  • 프로세스 T가 자원 R을 요청하면 예약 간선 T -> R은 요청 간선으로 변함
  • 반대로 T가 R을 방출하면 할당간선 R -> T는 예약 간선 T -> R로 변환됨
• 스레드가 자원을 요청할 때 요청 간선을 할당 간선으로 변해도 사이클을 형성하지 않으면 요청된 자원이 할당된다.
• 사이클이 존재하면 요청 자원은 할당되지 않는다.
  • 불안전 상태로 바꾸기 때문이다.

T2에 R2를 할당하면 불안전 상태가 된다. 만약 T1이 R2를 요청하고 T2가 R1을 요청하면 교착 상태가 발생한다.

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

자원 할당 그래프 알고리즘은 종류마다 자원이 여러 개씩 있게 되면 사용할 수 없다.

• 은행원 알고리즘은 자원이 여러 개 있을 때 적용 가능하다.

은행원 알고리즘을 적용하는 시스템에서는 스레드가 시작할 때 스레드가 가지고 있어야 할 자원의 최대 개수를 미리 알려줘야 한다.
자원의 최대 개수는 자원의 총 보유수를 넘어서면 안된다.

 

은행원 알고리즘을 구현하기 위해 필요한 자료구조

• Available : 각 종류별로 가용한 자원의 개수를 나타내는 벡터이다.
• Max : 각 스레드가 최대로 필요로 하는 자원의 개수를 나타낸다.
• Allocation : 각 스레드에 현재 할당된 자원의 개수를 타나낸다.
• Need : 각 스레드가 향후 요청할 수 있는 자윈의 개수를 나타낸다.

안정성 알고리즘

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

1. Work와 Finish는 크기가 m과 n인 벡터이다. Work = Available로 초기값을 준다. i = 0 ... n-1에 대해서 Finish[i] = false를 초기값으로 준다.
2. 아래 조건을 만족시키는 i값을 찾는다.
   1. Finish[i] = false
   2. Needi <= Work
   3. i값을 찾을 수 없다면 4번 과정으로 간다.
3. Work = Allocation + Work, Finish[i] = true후 2번으로 간다.
4. 모든 i값에 대해 Finish[i] = true이면 시스템은 안전 상태에 있다.

예시

다섯 개의 스레드 T0, T1, T2, T3, T4가 존재한다.
리소스 타입 R = {A, B, C}가 존재한다.
A = 10, B = 5, C = 7개 존재한다.(Allocation 합 + Available 합)
위의 사진은 시스템의 현재 상태를 보여준다.

Need 값들은 다음과 같다. (Max - Allocation)

알고리즘 실행 순서

• T0은 Finish[0] = false이지만 Need0 <= Work를 만족시키지 못한다. 따라서 T1을 실행한다.
  • (7, 4, 3) <= (3, 3, 2)기 때문에 만족되지 못함
• T1은 Finish[1] = fasle이고 Need1 <= Work를 만족시킨다.
  • (1, 2, 2) <= (3, 3, 2)를 만족함
  • 자원을 할당하고 T1은 작업 수행을 완료한다.
  • Work = (2, 0, 0) + (3, 3, 2) = (5, 3, 2)가 된다.
  • Finish[1] = true가 된다.
• T2는 Finish[2] = false이고 Need2 <= Work를 만족시키지 못한다.
  • (6, 0, 0) <= (5, 3, 2) 에서 6은 5보다 크므로 만족시키지 못함
• T3는 Finish[3] = false이고 Need3 <= Work를 만족시킨다.
  • (0, 1, 1) <= (5, 3, 2) 는 만족한다.
  • 자원을 할당하고 T3은 작업 수행을 완료함
  • Work = (2, 1, 1) + (5, 3, 2) = (7, 4, 3)이 된다.
• 계속해서 알고리즘을 수행한다.

이와 같은 과정을 수행하면 <T1, T3, T4, T2, T0>의 순서를 알게 되고 시스템은 안전한 상태임을 알 수 있다.

자원 요청 알고리즘

자원 요청이 안전하게 들어줄 수 있는지를 검사하는 알고리즘

1. Requesti <= Needi이면 2번으로 간다.
2. Requesti <= Available이면 3번으로 간다.
3. 시스템에 Ti에게 자원을 할당해준 것처럼 시스템 상태 정보를 아래처럼 바꿔본다.
4. 바뀐 상태가 안전하다면 Ti에게 반영된 정보대로 자원을 할당해준다. 새로운 상태가 불안전하다면 자원 할당 상태는 원상태로 복원되고 Ti는 Requiesti가 만족하기까지 기다려야 한다.

Available = Available - Requesti
Allocationi = Allocationi + Requesti
Needi = Needi - Requesti

 

예시

요청 성공 예시

• T1이 (1, 0, 2)를 요구한다고 가정
• 자원을 할당할지 말아야할지 결정해야 한다.
• Requesti <= Needi를 만족한다.
  • (1, 0, 2) <= (1, 2, 2)
• Requesti <= Available를 만족한다.
  • (1, 0, 2) <= (3, 3, 2)
• T1에 자원을 할당해준것처럼 값들을 변경한다.
  • Available = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)
  • Allocationi = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)
  • Needi = (1, 2, 2) - (1, 0, 2) = (0, 2, 0)

이 상태에서 안전성 알고리즘을 수행하면 안전 상태인 것을 확인할 수 있다.

 

요청 실패 예시

• T4가 (3, 3, 0)을 요청한다고 가정해보자.
• (3, 3, 0) <= (4, 3, 1) (Request3 <= Need3) 이므로 다음 단계를 수행한다.
• (3, 3, 0) <= (2, 3, 0) (Request3 <= Available)은 성립하지 않으므로 요청을 들어줄 수 없다.

교착 상태 탐지

시스템이 교착 상태 예방이나 교착 상태 방지 알고리즘을 사용하지 않는다면 교착 상태가 발생할 수 있다.

 

이러한 환경에서는 다음과 같은 알고리즘을 지원해야 한다.

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

각 자원 유형마다 하나의 인스턴스를 갖는 시스템과 자원 유형마다 여러개의 인스턴스를 갖는 시스템에서 교착 상태를 탐지하는 알고리즘이 존재한다.

각 자원 유형이 한 개씩 있는 경우

대기 그래프(wait-for graph)를 사용해 교착 상태 방지 알고리즘을 정의할 수 있다.

• 자원 할당 그래프로부터 자원 유형의 노드를 제거하고, 간선들을 결합해서 얻을 수 있다.

대기 그래프가 사이클을 포함하는 경우에만 시스템에 교착 상태가 존재한다.

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

은행원 알고리즘과 유사한 형식의 알고리즘을 사용하여 교착 상태를 감지한다.

탐지 알고리즘 사용

탐지 알고리즘을 언제 돌려야 하는지 판단하는 기준

• 교착 상태가 얼마나 자주 일어나는가?
• 교착 상태가 일어나면 통상 몇 개의 스레드가 연루되는가?

교착 상태로부터 회복

교착 상태가 발생하면 운영자(operator)가 수작업으로 교착 상태를 처리하거나, 시스템이 자동으로 교착 상태로부터 회복하게 하는 방법이 있다.

 

교착 상태를 깨트리는 두 가지 방법

• 순환 대기를 깨트리기 위해 한 개 이상의 스레드를 중지(abort)
• 교착 상태에 있는 하나 이상의 스레드로부터 자원을 선점(preempt)

프로세스와 스레드의 종료

프로세스 또는 스레드를 중지하면 종료된 프로세스에게 할당되었던 모든 자원을 시스템이 회수한다.

 

교착 상태를 제거하기 위해 프로세스를 제거하는 방법

• 교착 상태 프로세스를 모두 중지
  • 비용이 크다. 연산이 오래 진행중이던 프로세스를 중지하면 후에 다시 연산을 진행 해야 한다.
• 교착 상태가 제거될 때까지 한 프로세스씩 중지
  • 프로세스가 중지될 때 마다 교착 상태 탐지 알고리즘을 호출해 프로세스가 여전히 교착 상태에 있는지 확인해야 하므로 오버헤드가 크다.

자원 선점

교착 상태가 제어될 때까지 프로세스로부터 자원을 선점해서 다른 프로세스에 준다.

 

선점을 하기위해 고려해야 할 사항

• 희생자 선택
  • 다양한 요인(점유 하는 자원의 수, 실행 시간)등을 고려해서 비용을 가장 최소화 하는 희생자를 선택한다.
• 후퇴(rollback)
  • 프로세스를 안전한 상태로 후퇴시키고 재시작
  • 안전 상태를 모르기 때문에 가장 단순한 방법은 프로세스를 종료시키고 재시작 하는 것이다.
    • 종료, 재시작하지 않고 안전한 상태로 후퇴하려면 많은 정보가 필요하다.
• 기아 상태(starvation)
  • 기아 상태가 발생하지 않는것을 보장해야 한다.
  • 비용 요소의 후퇴 횟수를 포함해서 기아 상태를 방지할 수 있다.