Chapter 8. 교착 상태 - 2부

안녕하세요 파피몬입니다! 운영체제 8단원에 대해 공부해 보았습니다. 2부입니다!

Abraham Silberschatz의 Operating System Concepts 10th edition과 학부 수업을 듣고 정리한 내용입니다. 오개념이 있다면 알려주세요~~

 

1부에서 교착 상태의 개념을 알아보고 처리 방법으로 예방, 회피, 탐지, 복구 방법이 있다고 했다. 예방까지 알아보았고 이제 2부에서 회피, 탐지, 복구에 대해서 알아보자!

 

<교착 상태 회피> 

1부에서 살펴본 예방 방식은 장치 이용률(utilization), 시스템 총 처리율(throughput)을 감소시킨다.

이를 개선시켜야 하는데... 생각해보면 각 스레드의 요청과 방출에 대한 완전한 순서를 파악하고 있다면, 스레드가 미래의 교착상태를 일으킬 것을 예상하여 대기시킬 수 있지 않을까? 

 

회피 알고리즘의 기본 원칙은 시스템이 항상 안전 상태 안에 있게 하려 노력한다. 안전 상태는 시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원을 교착 상태 없이 차례로 할당해 줄 수 있는 상황을 뜻한다. 

 

이를 위해 회피 알고리즘은 시스템에 circular wait 상황이 발생하지 않도록 자원의 할당 상태를 검사하게 된다. 

자원의 할당 상태에는 가용 자원의 수, 할당된 자원의 수, 스레드들의 최대 요구 수에 의해 정의되게 된다!

 

본 책에서는 자원의 종류 별로 1개의 인스턴스가 있는 경우 자원 할당 그래프 알고리즘을, 자원의 종류 별로 여러 개의 인스턴스가 있는 경우 은행가 알고리즘을 사용할 것을 권한다. 

 

<자원 할당 그래프 알고리즘>

앞서 1부에서 살펴본 자원 할당 그래프에 예약 간선을 도입한 알고리즘이다. 예약 간선 P->R은 미래에 프로세스 Prk 자원 R을 요청할 것이라는 의미이다. 이는 점선으로 표현한다. 

 

예약 간선은 프로세스가 실제로 자원 요청 한다면, 요청 간선으로 변환이 된다.

요청 간선은 프로세스가 실제로 자원 할당 받으면, 할당 간선으로 변환이 된다. 

자원이 프로세스에 의해 방출 된다면, 할당 간선은 요청 간선으로 변환이 된다. 

 

해당 그래프에서는 요청 간선을 할당 간선으로 변환하는 것이 cycle을 형성하지 않는다면 변환을 진행 할 것이다. 그렇지 않다면 프로세스는 대기를 하게 된다.  

 

<은행가 알고리즘>

이 시스템에서는 스레드가 시작할 때, 스레드가 가져야 할 자원의 최대 개수를 자원 종류별로 미리 알려줘야 한다. 

알고리즘 설명 자체는 너무 포스팅이 길어지니 영상으로 대체하겠다! 

 

 

 

<교착 상태 탐지>

이제 교착 상태 탐지 알고리즘에 대해 알아보자. 예방도 안 하고 회피도 안 했으면 교착 상태가 충분히 일어날 수 있다. 이러한 시스템에서는 교착 상태를 탐지+회복 하는 과정이 필요할 것이다. 

 

탐지 알고리즘은 회피 알고리즘과 상당히 비슷하다. 회피하지 못해 교착 상태가 일어났을 법한 상황을 보고하는 게 탐지라 그런 것 같다. 

 

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

회피 알고리즘에서 자원의 종류 별로 1개가 있다면 자원 할당 그래프를 그렸다.

탐지 알고리즘에서는 이와 같은 경우에 대기 그래프를 그린다. 자원 할당 그래프로부터 자원 노드를 제거하고, 서로 대기를 하게 만드는 프로세스를 가리키게 함으로써 대기 그래프를 작성하게 된다. 

대기 그래프에서 사이클을 감지하면, 시스템의 교착 상태 가능성을 보고하게 된다. 

 

자원 할당 그래프(왼쪽)을 대기 그래프(오른쪽)으로 변경

 

<각 자원 유형이 여러 개 있는 경우>

이 경우에는 은행원 알고리즘처럼 시시각각 내용이 달라지는 자료구조를 사용한다. 

  - Available: 각 종류의 자원 현재 몇 개 가용한 지

  - Allocation: 각 스레드에 현재 할당된 자원의 개수

  - Request: 각 스레드가 현재 요청 중인 자원의 개수 

 

예시를 통해 살펴보도록 한다. 스텝 하나씩 따져가도록 해보겠다. 

1. 탐지 알고리즘 호출한 현재 (A,B,C) = (0,0,0)

2. P0의 수행을 끝낼 수 있음

3. P0의 수행 끝낸 후 현재 (A,B,C) = (0,1,0)

4. A,B,C 할당해줘도 P1 못 끝냄. PASS

5. P2의 수행을 끝낼 수 있음

6. P2의 수행 끝낸 후 현재 (A,B,C) = (3,1,3)

7. P3의 수행을 A에 1개 할당해 줌으로써 끝낼 수 있음. 할당해 줌

8. P3의 수행 끝낸 후 현재 (A,B,C) = (5,2,4)

  .... 하며 진행

 

 

하지만 만약 P2의 Request가 (A,B,C) = (0,0,1)이었으면 어떻게 되었을까?

할당해 줄 C가 없어 Deadlock 상태에 빠져 버린다. 

 

교착 상태 탐지 알고리즘은 한 번 탐색하는데 대기 그래프는 O(n^2), 여러 자원 유형을 위한 탐지 알고리즘은 O(m*n^2)의 연산이 필요하다.  

 

그래서 적당한 시기에, 적당한 탐지 횟수로 교착상태를 가려내는 것이 중요하다. 예시로 한 시간에 한 번 탐지하거나, CPU의 이용률이 40% 이하로 떨어질 때 호출하는 방법을 책에서는 소개한다. 

 

<교착 상태 회복> 

이제 교착 상태를 탐지했고, 교착 상태에 봉착했다. 교착 상태를 깨뜨려야 한다. 방법은 2가지가 있다. 

  1. 순환 대기 깨뜨리기 위해 한 개 이상의 스레드를 중지(abort)

  2. 교착 상태에 있는 하나 이상의 스레드들의 자원을 선점(preempt)

 

<프로세스와 스레드의 종료>

종료할 프로세스를 선택할 때 고려해야 할 점은 다음과 같다. 

  1. 프로세스의 우선순위는 무엇인가

  2. 지금까지 프로세스가 수행된 시간과 지정된 일을 종료하는데 더 필요한 시간은 얼마인가

  3. 프로세스가 사용한 자원 유형과 수

  4. 프로세스가 종료하기 위해 더 필요한 자원의 수

  5. 얼마나 많은 수의 프로세스가 종료되어야 하는가

 

이를 고려하여 최소 비용이 드는 프로세스를 종료해야 한다!

 

<자원 선점>

자원 선점을 통해 교착 상태로부터 회복하려면, 교착 상태가 깨질 때까지 계속 프로세스로부터 자원을 선점해 다른 프로세스에게 주어야 한다. 다음과 같은 사항을 고려해야 한다. 

  1. Victim Selection: 비용을 최소화하기 위해 선점의 순서 결정하기. (자원의 수, 지금까지 실행 소요 시간 등 고려)

  2. Rollback: 해당 프로세스를 안전한 상태로 후퇴시켜야 한다. 이는 어렵기 때문에, 가장 단순한 방법은 재시작하는 것

  3. Starvation: 같은 프로세스의 자원만 계속하여 선점되면 기아 상태에 놓인다. 이를 방지해야 한다.