🛶 교착 상태 회피 (Deadlock Avoidance)

교착 상태를 회피하는 다른 대안은 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구

• 가장 단순하고 제일 유용한 모델은 각 프로세스가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구
• 교착 상태 회피 알고리즘은 시스템에 순환 대기 상황이 발생하지 않도록 자원 할당 상태를 검사
• 자원 할당 상태는 가용 자원의 수, 할당된 자원의 수 그리고 프로세들의 최대 요구 수에 의해 정의

안전 상태 (Safe State)

시스템이 모든 프로세스들의 안전 순서(safe sequence)를 찾을 수 있다면 시스템은 안전(safe)

• Pi가 요청하는 자원을 시스템에 현재 남아 있는 자원과 앞에서 수행을 마칠 모든 프로세스 Pj들이(j/i) 반납하는 자원들로 만족된다면 프로세스 순서가 안전

안전, 불안전, 교착 상태

• 시스템이 안전 상태 : 교착 상태 아님
• 시스템이 불안전 상태 : 교착 상태 가능성
• 교착 상태 회피 : 시스템이 불안전 상태로 진입하지 않도록 보장

처리 알고리즘

교착 상태 회피 알고리즘

시스템이 불안전 상태로 진입하지 않도록 보장하는 알고리즘

• 단일 인스턴스의 자원 유형 → 자원 할당 그래프 알고리즘 적용
• 다수의 인스턴스를 갖는 자원 유형 → 은행원 알고리즘 적용

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

교착 상태 회피를 위해 자원 할당 그래프를 변형

• 요청 간선(request edge)과 할당 간선(assignment edge)에 추가하여 예약 간선(claim edge)을 도입
  • 예약 간선 P→R는 P가 미래에 자원 Rj를 요청할 것이라는 의미
  • 점선(dashed line)으로 표시
  • 프로세스 P가 자원 R를 요청하면, 예약 간선 P→R는 요청 간선으로 변환
  • P가 자원 R을 방출할 때, 할당 간선 R→P는 예약 간선 P→R로 다시 변환
• 시스템에서 자원이 반드시 미리 예약되어야 함
  • 프로세스 P가 실행되기 전에 프로세스의 모든 예약 간선들이 자원 할당 그래프에 표시 되어야 함

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

은행원 알고리즘은 자원 종류(유형) 당 여러 개의 인스턴스를 갖는 경우에도 적용

• 각 프로세스는 필요한 자원의 최대 개수를 자원 종류마다 미리 신고
• 프로세스가 자원들을 요청 시 요청을 수락하면 시스템이 계속 안전 상태에 머무르게 되는지 여부를 판단
  • 계속 안전하게 된다면 그 요청 수락
  • 안전하지 않으면 프로세스의 요청은 수락되 않고 다른 프로세스가 끝나기를 기다림
• 은행원 알고리즘의 자료 구조 (n : 프로세스 수, m : 자원 종류의 수)
  • Available : 각 종류의 자원이 현재 몇 개가 사용 가능하지를 나타내는 벡터로 크기가 m
  • Max : 각 프로세스가 최대로 필요로 하는 자원의 개수를 나타내는 행렬로 크기
  • Allocation : 각프로세스에 현재 할당된 자원의 개수를 나타내는 행렬로 크기가 n*m
  • Need : 각 프로세스가 향후 요청할 수 있는 자원의 개수를 나타내는 행렬로 크기가 n*m

안전성 알고리즘 (Safety Algorithm)

1. Work = Available로 초기화, i =0,1,..n-1에 대해서 Finish[i] =false로 초기화
2. 아래 두 조건을 만족시키는 i 값을 탐색 : 위 조건을 만족하는 i 값을 찾을 수 없다면 step 4로 이동
   1. Finish[i] == false
   2. Need ≤ Work
3. Work = Work + Allocation, Finish
4. 모든 i 값에 대해 Finish[i] == true이면 이 시스템은 안전 상태에 있음

자원 요청 알고리즘 (Resource-Request Algorithm)

Request는 프로세스 P의 요청 벡터

1. 만일 Request ≤ Need이면 step 2로 이동하고, 아니면 시스템에 있는 개수보다 더 많이 요청했으므로 오류로 처리

2. 만일 Request ≤ Available이면 step3으로 간다. 아니면 요청한 자원이 당장은 없으므로 P는 기다림

3. 마치 시스템이 P에게 자원을 할당해준 것처럼 시스템 상태 정보를 아래처럼 변경 조사

   1. Available = Available - Request;
   2. Allocation = Allocation + Request;
   3. Need = Need - Request;

   만일 이렇게 바뀐 상태가 안전하다면 P에게 자원을 할당

   새로운 상태가 불안전 하다면, 위의 자원 할당 상태는 원상태로 복원되고 P는 Request가 만족되기까지 기다림

🪂 교착 상태 탐지

• 교착 상태 발생이 가능한 시스템에서는 다음들을 지원
  • 교착 상태가 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘 (detection algorithm)
  • 교착 상태로부터 회복하는 방식 (recovery scheme)
• 2가지 유형 논의
  • 각 자원 유형마다 하나의 인스터스를 갖는 시스템
  • 자원 유형마다 다수의 인스턴스를 갖는 시스템

각 자원 유형이 한 개씩 있는 경우 (Single Instance of Each Resource Type)

• 대기 그래프(wait-for graph) 사용
  • 자원 할당 그래프로부터 자원 유형의 노드를 제거
  • Pi→Pj : 프로세스 Pj가 가지고 있는 자원을 프로세스 Pi가 요청하여 기다림
• 주기적으로 그래프에서 사이클을 조사하여 교착상태 탐지
• 그래프에서 사이클을 탐지하는 알고리즘은 O(n^2)의 연산을 요구
  • n : 그래프에 있는 정점들(vertices)의 수

각 유형의 자원을 여러 개 가진 경우 (Serveral Instances of a Resource Type)

은행원 알고리즘과 같이 시시각각 그 내용이 달라지는 자료 구조를 사용. O(m * n^2)

• 가용(Available) : 각 종류의 자원이 현재 몇 개가 가용한지를 나타내는 벡터로 크기가 m
• 할당(Allocation) : 각 프로세스에게 현재 할당되어 있는 자원의 개수를 나타내는 행렬로 크기가 n * m
• 요청(Request) : 각 프로세스가 현재 요청 중인 자원의 개수를 나타내는 행렬로 크기가 n*m
  • Request[i, j] == k라면 현재 Pi가 Rj를 k개 요청중임을 의미

탐지 알고리즘(Detection Algorithm)

1. Work = Available로 초기화, i =0, 1, …, n-1에 대해서 Allocation ≠ 0이면 Finish[i] = false, 아니면 Finish[i] = true (Work와 Finish 크기가 m과 n인 벡터)
2. 아래 두 조건을 만족시키는 i값을 탐색 (위 조건을 만족하는 i값을 찾을 수 없다면 step 4)
   1. Finish[i] == false
   2. Request ≤ Work
3. Work = Work + Allocation, Finish[i] = true, step 2로 이동
4. 어떠한 i 값에 대해 (0<i<n) Finish[i] == false이면 Pi가 교착 상태 (즉, 시스템이 교착 상태)

탐지 알고리즘 사용 (Detection-Algorithm Usage)

• 탐지 알고리즘의 수행 빈도는 다음을 고려
  • 교착 상태가 얼마나 자주 일어나는가?
  • 교착 상태가 일어나면 통상 몇 개의 프로세스가 거기에 연루되는가?
• 프로세스의 요청이 즉시 만족되 않을 때마다 탐지 알고리즘을 수행하면 교착 상태에 연루된 프로세스들 뿐 아니라 교착 상태를 야기한 장본인 프로세스도 탐지
• 탐지 알고리즘을 가끔씩만 돌리면 한꺼번에 여러 개의 사이클이 탐지가 되어 어느 프로세스가 최종적으로 교착 상태를 야기한 장본인인지 알아내기 어려움

교착 상태로부터 회복

• 프로세스 종료 : 프로세스를 모두 중지시키거나 제거될 때까지 하나씩 중지하여 교착상태 제거
  • 부분 종료 방식의 경우 다음을 고려하여 중지될 프로세스 선택
    • 프로세스의 우선 순위, 지금까지 프로세스가 수행된 시간과 지정된 일을 종료하는 데 더 필요한 시간
    • 프로세스가 사용한 자원 유형과 수
    • 프로세스가 종료하기 위해 더 필요한 자원의 수
    • 얼마나 많은 수의 프로세스가 종료되어야 하는지
    • 프로세스가 대화형(interactive)인지 일괄 처리(batch)인지 여부
• 자원 선점 : 자원 선점을 이용해 교착 상태를 제거하려면 다음을 고려
  • 희생자 선택 (selecting a victim)
    • 어느 자원과 어느 포르세스들이 선점될 것인가를 결정
    • 비용을 최소화하기 위해 선점의 순서를 결정
  • 후퇴 (rollback)
    • 중지될 프로세스를 안전한 상태로 후퇴시키고, 그 상태로부터 다시 시작
    • 안전 상태가 어떤 것인지를 결정하기 어렵기 때문에, 가장 단순한 해결안은 프로세스를 중시고 재시작
  • 기아 상태 (Starvation)
    • 동일한 프로세스가 항상 희생자로 선택되어 자신의 태스크를 결코 완료하지 못하는 기아 사애로 발생하는 것을 방지
    • 일반적인 해결 방법은 비용 요소에 후퇴의 횟수를 포함

🦴참고

Operating System Concepts, 10th Ed.