[OS] 교착 상태의 해결 방법

이 포스팅에서는 교착 상태 문제를 해결하는 세가지 방법에 대해 알아볼 것이다.

• 시스템이 교착상태가 발생하지 않도록 예방(prevention) 하는 방법
• 교착 상태의 발생 가능성을 배제하지 않고 이를 적절히 회피(avoidance)하는 방법
• 교착 상태를 허용하되 교착 상태를 탐지(detection)하여 다시 회복하는 방법
  • 탐지 및 회복은 사용하기 어렵고 오버헤드가 증가하므로 간단하게 살펴볼 것이다.

 

 

1. 교착 상태 예방 기법

---

• 4 가지의 교착 상태 발생 조건 중 하나라도 발생하지 않도록 하여 교착 상태를 예방하는 것
  (상호배제 문제는 고려해야 함)
  • 전용 자원에서는 교착 상태가 발생하지 않으므로 프로세스가 원하는 자원을 배타적으로 사용하려는 것을 제외시켜야 함.

 

하벤더(Havender, 1968년)가 상호배제를 제외한 세 가지 기본 방법을 제안

1. 각 프로세스는 필요한 자원을 한 번에 모두 요청해야 하며, 요청한 자원을 모두 제공받기 전까지는 작업을 진행할 수 없다.
2. 어떤 자원을 점유하고 있는 프로세스의 요청을 더 이상 허용하지 않으면 점유한 자원을 모두 반납하고, 필요할 때 다시 자원을 요청해야 한다.
3. 모든 프로세스에 자원을 순서대로 할당해야 한다. 모든 프로세스에 각 자원 유형별로 할당 순서를 부여한 순서에 따라 자원을 요청하게 한다.

 

자원의 상호배제 조건 방지

상호 배제는 자원의 비공유가 전제되어야 한다.

• 예를 들어, 여러 프로세스는 프린터를 동시에 공유할 수 없다. 공유 자원은 배타적인 접근이 필요 없으므로 교착 상태가 발생하지 않는다.
• 읽기 전용 파일은 여러 프로세스가 동시에 읽기 전용 파일을 열려고 할 때에도 파일 접근이 가능하므로 프로세스가 공유 자원을 기다릴 필요가 없다.

그러나 일반적으로 상호배제 조건을 만족하지 않으면 교착상태를 예방을 할 수 없다.

이 말은 즉, 공유 자원에 대해 모든 프로세스들이 접근할 수 있으면 교착 상태가 발생할 수 있다는 말이다.

• 어떤 자원은 공유 자체가 불가능한 것도 있다.
• 파일 쓰기는 배타적인 접근만 허용해야한다.
• 하나 이상의 프로세스에 쓰기 권한이 동시에 있으면 교착 상태가 발생할 수 있기 때문이다.
• 즉, 현실적으로 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있다. 

※ 참고

"상호배제 조건을 만족하지 않으면 교착상태를 예방할 수 없다" 라는 말이 애매해서 chat gpt한테 물어본 대답.

"상호배제 조건을 만족하지 않으면 교착상태를 예방할 수 없다" 는 문장은 교착상태(Deadlock)를 막기 위해 상호배제 조건을 지켜야 함을 의미합니다.

교착상태란, 여러 개의 프로세스나 스레드가 각각 자원을 점유하고 다른 프로세스나 스레드의 자원 해제를 기다리는 상황에서, 모든 프로세스나 스레드가 움직이지 못하고 무한정 대기하는 상태를 말합니다. 이러한 상황에서는 시스템의 작동이 멈추게 되어 정상적인 작업을 수행할 수 없게 됩니다.

상호배제 조건은 교착상태를 방지하기 위한 조건 중 하나로, 한 번에 한 프로세스만이 공유 자원을 사용할 수 있도록 하는 것을 의미합니다. 즉, 다른 프로세스가 점유한 자원을 사용하려면 먼저 해당 자원을 해제해야 합니다.

따라서, "상호배제 조건을 만족하지 않으면 교착상태를 예방할 수 없다"라는 문장은 상호배제 조건을 위반하면 교착상태가 발생할 수 있다는 것을 말하고, 상호배제 조건을 지키지 않으면 교착상태를 예방할 수 없다는 의미입니다. 따라서 시스템 설계나 프로그래밍에서는 상호배제 조건을 지키는 것이 중요하며, 이를 통해 교착상태를 예방할 수 있습니다.

 

 

점유와 대기 조건 방지

최대 자원 할당

• 프로세스가 작업을 수행하기 전에 필요한 자원을 모두 요청하고 획득해야 한다.
• 프로세스가 실행에 필요한 자원들을 한꺼번에 요구하고 허용할 때까지 작업을 보류하여 대기 조건이 성립하지 않도록 하는 것이다.
• 보류 상태에서는 프로세스가 자원을 점유할 수 없으므로 대기 조건이 성립하지 않는다.

 

점유와 대기 조건을 방지하는 두 가지 방법

모든 프로세스는 자원을 요청하고 사용할 수 있다. 또한 프로세스가 자원을 더 요청하려면, 먼저 자신에게 할당된 자원을 해제해야 한다.

1. 자원을 할당할 때 시스템 호출된 프로세스 하나를 실행하는데 필요한 모든 자원을 먼저 할당하여 실행한 후 다른 시스템 호출에 자원을 할당하는 것이다.
2. 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용하는 것이다.

 

예시 

프로세스 설정

1. DVD 드라이브에서 디스크 파일로 데이터를 복사
2. 복사한 데이터를 정렬
3. 정렬 결과를 프린터로 인쇄
4. 테이프 드라이브에 복사

 

첫번째 방법

• 프로세스를 시작할 때 필요한 자원(DVD 드라이브, 디스크 파일, 프린터, 테이프 드라이브) 을 모두 요청한다. 따라서 마지막 단계에 필요한 테이프 드라이브를 전체 실행 시간동안 점유한다.

 

두번째 방법

1. 처음에는 DVD 드라이브와 디스크 파일만 요청하도록 허용
2. DVD 드라이브에서 디스크 파일로 복사한 후 DVD 드라이브와 디스크 파일을 해제
3. 다시 디스크 파일과 프린터를 요청
4. 디스크 파일에서 프린터로 복사한 후 두 자원을 해제
5. 디스크 파일과 테이프 드라이브 요청
6. 디스크 파일에서 테이프 드라이브로 복사한 후 두 자원을 해제
7. 프로세스 종료

 

단점

• 자원의 효율성이 너무 낮다. 많은 자원이 사용되지 않으면서 오랫동안 할당되어 있기 때문이다.
  
  • 앞서 예처럼 , 데이터가 디스크에 그대로 남아 있다고 확신할 수 있으면 DVD 드라이브와 디스크를 해제하고 디스크와 프린터를 요청할 수 있다. 그러나 이를 확신할 수 없다면 일을 시작할 때 모든 자원을 요청해야 한다.
• 기아 상태가 발생할 수 있다.
  • 자주 사용하는 자원이 다른 프로세스에 할당되어 있는 프로세스는 무한정 기다려야 하는 경우가 발생한다.
  • 또 적은 수의 자원을 요청한 프로세스의 우선순위가 더 높아 많은 수의 자원을 요청한 프로세스의 대기 시간이 길어질 수 있다.

 

 

비선점 조건 방지

이미 할당된 자원에 선점권( 차지하여 가질 수 있는 권한 )이 없어야 한다는 전제 조건을 가진다. 

• 어떤 자원을 가진 프로세스가 다른 자원을 요청할 때 요청한 자원을 즉시 할당받을 수 없어 기다려야 한다면, 프로세스는 현재 가진 자원을 모두 해제한 후 대기 한다.
• 프로세스가 작업을 시작할 때는 요청한 새로운 자원과 해제한 자원을 확보해야 한다.
• 이미 실행한 작업의 상태를 잃을 수도 있으므로, 작업 상태를 쉽게 저장 및 복구 가능할 때 또는 빈번하게 발생하지 않을 때만 좋은 수단으로 이용 가능하다.

 

두 가지 대안 제시

1. 프로세스가 어떤 자원을 요청할 때, 요청한 자원이 사용 가능한지 검사

• 사용 가능하다면 자원 할당, 사용 불가능 한 경우 대기 프로세스가 요청한 자원을 점유하고 있는지 검사
• 요청한 자원을 대기 프로세스가 선점하고 있다면, 자원을 해제하고 요청 프로세스에 할당.
• 요청한 자원을 사용할 수 없거나, 실행 중인 프로세스가 점유하고 있으면 요청 프로세스는 대기
• 프로세스가 대기하는 동안 다른 프로세스가 점유하고 있던 자원을 요청하면 해제할 수 있음.

 

2. 두 프로세스에 우선 순위를 부여하여, 높은 우선순위의 프로세스가 그보다 낮은 순위의 프로세스가 점유한 자원을 선점하여 해결

• 이 방법은 프로세서 레지스터나 기억장치 레지스터와 같이 쉽게 저장되고 이후에 다시 복원하기 쉬운 자원에 사용한다.
• 그러나 프린터, 카드 판독기, 테이프 드라이브 같은 자원에는 적용되지 않는다.

 

 

순환 대기 조건 방지

계층적 요구 기법

• 모든 자원에 일련의 순서를 부여하고 각 프로세스가 오름차순으로만 자원을 요청할 수 있게 한다.
• 순환 대기(circular wait)의 가능성을 제거하여 교착 상태를 예방.
• 그러나 예상된 순서와 다르게 자원을 요청하는 작업은 실제로 자원을 사용하기 훨씬 전부터 오랫동안 자원을 할당받은 상태로 있어야 하므로, 상단한 자원 낭비를 초래한다.

자원 집합을 R = {R1, R2, ... Rn}이라고 가정하자. 각 자원 형태에 고유 숫자를 부여하여 어느 자원의 순서가 빠른지 알 수 있게 한다. 이것은 1 : 1 함수 "F: R -> N" 으로 정의할 수 있으며, N 은 자연수의 집합을 의미한다.

• 자원 형태 R의 집합이 CD 드라이브, 디스크 드라이브, 프린터를 포함한다면 함수 F는 다음과 같이 정의할 수 있다.

F(CD 드라이브) = 2,
F(디스크 드라이브) = 4,
F(프린터) = 7

교착 상태를 예방하려면, 다음 규칙을 고려하자.

1. 프로세스는 임의의 자원 Ri 을 요청할 수 있지만 그 다음부터는 "F(Rj) > F(Ri)" 인 경우에만 자원 형태 Rj를 요청할 수 있음.
   • 각 프로세스는 오름차순로만 자원들을 요청할 수 있으며, 데이터 형태 자원이 여러 개 필요하다면, 우선 요청할 형태 자원을 하나 정해야 한다.
   • CD 드라이브와 프린터를 동시에 사용해야 하는 프로세스는 CD 드라이브를 먼저 요청한 후 프린터를 요청
2. 프로세스가 자원 형태 Rj 을 요청할 때마다 "F(Ri) >= F(Rj)" 가 되도록 Ri 의 모든 자원을 해제

 

계층적 요구의 단점

• 순환대기 조건 가능성을 제거하여 교착 상태를 예방하지만, 반드시 그 자원이 가진 번호 순서로 요구해야 한다는 부담(자원 요구순서 예측) 이 있다.
• 번호를 부여할 때 실제로 자원을 사용하는 순서를 반영해야 한다는 어려움도 있다.

 

OS의 중요한 목적 중 하나는 사용자가 이용하기 편리한 작업 환경을 제공하는 것이다.

• 사용자가 HW나 SW의 제약에 영향을 받지 않고 응용 프로그램을 사용하거나 개발할 수 있도록 해야 한다.

그런데 하벤더의 순서 배정법은 순환대기의 가능성을 제거하지만, 사용자가 응용 프로그램을 손쉽게 사용하거나 개발하는 데 지장을 줄 수 있다.

순환 대기 조건 방지는 프로세스 속도를 떨어뜨리고 자원 접근을 불필요하게 거부하기 때문에 비효율적이다.

 

 

그렇다면 3가지만 충족하면 왜 Deadlock 이 발생하지 않을까?

Deadlock 발생에 필요한 조건이 4가지 중 하나인 "순환 대기(Circular Wait)" 조건이 포함되어 있기 때문이다. 순환 대기 예를 들어,

• 상호 배제 조건이 없으면 두 개 이상의 프로세스가 동시에 자원을 사용할 수 있으므로, 대기할 필요가 없어짐
• 점유 및 대기 조건이 없으면 자원을 요청한 프로세스는 해당 자원을 할당받지 못하고 바로 실패하게 되므로 대기X
• 비선점 조건이 없으면 다른 프로세스가 자원을 강제로 해제할 수 있으므로, 프로세스들이 서로 계속해서 자원을 해제하고 점유할 수 있게 됨

따라서, 세 가지 조건만 충족된다면 순환 대기 조건이 없어서 Deadlock이 발생하지 않으며, 순환 대기 조건이 포함된 경우 4가지 조건이 모두 충족되어야 Deadlock이 발생한다.

 

 

정리

교착 상태 예방 기법은 교착 상태의 발생 조건 중 최소한 하나라도 성립하지 않도록 자원 요청을 제한하는 것이다.

상호배제, 점유와 대기, 비선점 조건이 발생하지 않게 하여 간접적으로 순환 대기 조건을 방지해서 교착 상태를 예방했다. 그러나 이 방법은 장치의 효율성과 시스템 처리량을 떨어뜨리는 결과를 초래했다.

 

 

 

2. 교착 상태 회피 기법

---

• 교착 상태의 예방보다 덜 엄격한 조건을 요구함으로써 자원을 좀 더 효율적으로 이용하는 것을 목적으로 한다.
• 교착 상태 회피는 교착 상태의 모든 발생 가능성을 미리 제거하는 것이 아니다.
• 교착 상태가 발생할 가능성을 인정하고(세 가지 필요조건 허용), 교착 상태가 발생하려고 할 때 적절히 회피하는 것이다. 따라서 예방보다는 회피가 더 병행성을 허용한다.

 

회피 기법은 크게 두 가지 방법이 제시된다.

 

프로세스의 시작 중단

• 프로세스의 요구가 교착 상태를 일으킬 수 있다면 프로세스 시작을 중단한다.
  • ex. 현재 수행 중인 모든 프로세스의 최대 자원 요구량과 새로운 프로세스의 최대 요구량을 합한 자원 요구량을 수용할 수 있으면 새로운 프로세스를 수용한다.
• 그러나 프로세스에 최대 요청량이 필요하다는 최악의 상황이므로 바람직하지 않다.

 

자원 할당 거부

• 프로세스가 요청한 자원을 할당했을 때 교착 상태가 발생할 수 있다면 요청한 자원을 할당하지 않는다.
• 일반적으로 은행가 알고라즘(Banker's algorithm) 이라고 한다.

 

 

1. 프로세스의 시작 중단

교착 상태를 회피하려면 자원을 언제 요청하는지 추가 정보가 필요하다.

• 각 프로세스마다 요청과 해제에서 정확한 순서를 파악하고 있다면, 요청에 따른 프로세스 대기 여부를 결정할 수 있다.

프로세스의 요청을 수락할지, 기다리게 할지 여부는 현재 사용 가능한 자원, 프로세스에 할당된 자원 등 각 프로세스에 대한 자원의 요청과 해제를 미리 알고 있어야 결정할 수 있다.

• 각 프로세스가 필요한 자원의 최대치(할당 가능한 자원 수) 정보를 미리 파악할 수 있으면 시스템이 교착 상태가 되지 않을 확실한 알고리즘을 만들 수 있다.

 

안정 상태와 불안정 상태

• 교착상태 회피 알고리즘은 시스템이 순환-대기 조건이 발생하지 않도록 자원 할당 상태를 검사한다.
• 자원 할당 상태는 사용 가능한 자원의 수(Available), 할당된 자원의 수(Allocation), 프로세스들의 최대 요구 수(Max에 의해 정의 된다.

안정 상태

• 각 프로세스에 자원을 할당할 수 있고(최대치까지), 교착 상태를 예방할 수 있으면 안정된 상태라고 한다. 그리고 시스템에 안정 순서가 있으면 그 시스템은 안정하다.
• 프로세스의 순서 <P1, P2, ..., Pn> 이 안정 순서란 의미는 모든 Pi 가 요청하는 자원이 현재 사용 가능한 자원과 j > i 인 모든 Pj 가 점유한 자원들이 충족할 수 있다는 의미이다.
• 프로세스 Pi 가 필요한 자원을 즉시 사용할 수 없다면 Pi 는 모든 Pj 가 끝날 때까지 기다렸다가 자원을 확보하고 필요한 모든 자원을 확보하면 지정된 작업을 끝내고 자원을 해제한다.
• Pi 가 종료하면 Pi+1 은 필요한 자원을 확보할 수 있으므로 처리를 계속 진행할 수 있다. 

 

불안정 상태

• 안정 상태처럼 프로세스의 자원 할당 및 해제의 순서가 명확히 존재하지 않는 경우
• 운영체제가 모든 사용자가 일정 기간 내에 작업을 끝나게 해주면 현재 시스템의 상태가 안정하다고 하고, 그러지 않으면 불안정 상태라고 한다.

시스템의 상태는 위 그림처럼 안정 상태와 불안정 상태로 나눌 수 있고, 교착 상태는 불안정 상태에서 발생한다.

• 교착 상태는 불안정 상태이나, 모든 불안정 상태가 교착 상태인 것은 아니다.
• 단지 불안정 상태는 교착 상태가 되기 쉬울뿐(교착 상태는 불안정 상태에서 발생), 상태가 안정하다면 OS는 불안정 상태와 교착 상태를 예발할 수 있다.
• 그러나 불안정 상태의 OS는 교착 상태를 발생시키는 프로세스의 자원 요청을 방지할 수 없다.

 

 

시스템 상태 변화 예시

동일한 자원 10개와 프로세스 P0, P1, P2, P3 을 가진 시스템의 경우를 예를 들어 시스템 상태 변환을 설명해보자.

 

안정 상태

• P0, P1, P2, P3 은 각각 7, 8, 4, 10 개의 자원을 요청한다.
• t0 시간에  프로세스 P0, P1, P2, P3 은 자원 2, 1, 2, 2, 를 점유한다면 사용 가능한 자원은 3개 (= 10-2-1-2-2)이다.
• 시스템은 t0 시간에 안정 상태이다. 이때 <P2, P0, P1, P3 > 순서는 안정 조건을 만족한다.
  1. P2 가 자원 2개를 실행한 후 반납하면, 시스템은 자원 5개를 여분으로 갖는다.
  2. P0 이 사용 가능한 자원 5개를 할당받아 실행한 후 자원 7개를 반납
  3. P1 이 사용 가능한 자원 7개를 할당받고 실행한 후 자원 8개를 반납
  4. P3 도 자원 8개를 할당 받고 실행한 후 10개를 반납할 수 있음
• 이는 즉 시스템이 안정 상태라는 의미.

 

불안정 상태

프로세스 P1 의 요청을 허용한 예

 

• 프로세스 P2 는 사용 가능한 자원 2개를 할당받아 실행 후 자원 4개를 반납, 그러면 시스템에는 여분 자원이 4개 존재
• P0 은 여분 자원이 4개인데 추가로 자원 5개가 필요하므로 대기
• p1 은 추가로 자원 6개, P3 은 추가로 자원 8개가 필요하여 요청하므로 결국 교착 상태 발생

여기서 잘못은 프로세스 P1 의 자원 요청을 허용한 것이다. 다른 프로세스 (P0, P2)이 실행을 마치고 자원을 반납할 때까지 프로세스 P1 을 대기시켰다면, 교착 상태를 회피할 수 있었을 것이다.

 

안정 상태 개념에서 교착 상태 회피 알고리즘을 정의할 수 있다. 이는 시스템이 항상 안정 상태에 머물러 있도록 하는 단순한 방법이다. 초기 시스템은 안정 상태이다. 따라서 프로세스가 현재 사용 가능한 자원을 요청할 때마다 시스템은 자원을 즉시 할당할 수 있는지 또는 프로세스가 대기해야 하는지 결정한다. 자원을 할당한 후에도 시스템이 항상 안정 상태에 있을 때만 할당을 허용하면 된다.

 

 

 

2. 자원 할당 거부(은행가 알로리즘)

추후 포스팅

 

 

3.1 교착 상태 탐지 알고리즘

---

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

그러나 교착 상태 예방은 실제로 구현하기 어렵다. 교착 상태 회피는 구현할 수 있지만 자원을 낭비하는 문제가 있다.

 

따라서 발생한 교착 상태에서 회복하려면 다음 알고리즘이 필요하다

• 시스템 상태를 검사하는 교착 상태 탐지 알고리즘
• 교착 상태에서 회복시키는 알고리즘

교착 상태 해결 방법 중 가장 현실적인 것은 바로 교착 상태 검출이다. 교착 상태 검출은 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방식이다. 만약 교착 상태가 발견되면 이를 해결하기위해 교착 상태 회복 단계를 밟는다.

 

하지만 교착 상태를 파악하려고 교착 상태 탐지 알고리즘을 언제 수행해야 하는지 결정하기란 쉽지 않다. 교착 상태 탐지 알고리즘을 자주 실행하면 시스템의 성능은 떨어지는 단점도 잇다.

 

 

이제 각 데이터 형태마다 자원이 여러 개인 시스템을 살펴보자. 이때 탐지와 회복 방법은 필요한 정보를 유지하고 탐지 알고리즘을 실행시키는 비용뿐만 아니라 교착 상태에서 회복하는 데 필요한 부담까지 요청한다는 점에 유의하자.

 

교착 상태 탐지 알고리즘

교착 상태 탐지 알고리즘의 자료구조

교착 상태 탐지 알고리즘은 쇼사니(Shoshani) 와 코프만(Coffman) 이 제안했다. 은행가 알고리즘에서 사용한 자료구조와 비슷하다.

• Available : 자원마다 사용 가능한 자원 수를 표시하는 길이가 m 인 벡터이다.
• Allocation : 각 프로세스에 현재 할당된 각 형태들의 자원 수를 표시하는 n * m 행렬이다. Allocation[i, j] = k 이면, 프로세스 Pi 는 자원 Rj 를 k 개 할당받고 있다는 의미이다.
• Request : 각 프로세스의 현재 요청을 표시하는 n * m 행렬이다. Request[i, j] 일때 프로세스 Pi 에 필요한 자원 수가 k 개라면, 프로세스 Pi 는 자원 Ri 의 자원을 k 개 더 요청한다.

 

교착 상태 탐지 알고리즘 동작 순서

탐지 알고리즘은 남아 있는 프로세스들의 할당 가능 순서를 모두 찾는다.

2단계 "Request <= Work" 임을 확인하자마자 3단계에서 프로세스 Pi 의 자원을 변환하는 이유는 Pi 가 현재 교착 상태에 있지 않다는 것을 알 수 있기 때문이다. 

Pi 는 자신의 작업을 종료하려고 더 이상 자원을 요청하지 않을 것이라고 가정하자. 그렇지 않으면 이후에 교착 상태가 발생할 수도 있다. 그래서 다음에는 교착 상태 탐지 알고리즘을 호출하여 교착 상태를 탐지할 것이다.

 

 

교착 상태 탐지 알고리즘 문제 예시

• P0~P4 까지 프로세스 5개, A, B, C 자원 3개를 가진 시스템
• 자원 A 는 자원 7개, B는 자원 2개, C는 자원 6개를 갖고 있다.

그리고 t0 시간에 아래 그림처럼 자원 할당 상태가 된다고 하자.

시간 t0 일 때 시스템의 상태

 

Step 1

• Available = (0, 0, 0) 으로 Work = (0, 0, 0) 그리고 Allocation[i] 값 중 0 인 값이 없으므로 Finish = ( false, false, false, false, false ) 로 초기화 한다.

Step 2

• 먼저 P0 프로세스 부터 확인해보자. 먼저 P0 는 Allocation[0] = (0, 1, 0) 으로 P0 에 할당되있는 자원이다. 그리고 Request[0] = (0, 0, 0) 으로 Reqeust[i] <= Work 가 성립하므로 P0 를 실행할 수 있다.

 

Step 3

• 그러면 P0 를 실행한 후 자원 해제가 되면 Work = (0, 0, 0) + (0, 1, 0) = (0, 1, 0) 이고 Finish = ( true, false, false, false, false ) 이다.

Step 4

• 이제 다음 Finish[i] = false, Reqeust <= Work 를 만족하는 i 를 찾아보자. 위의 step 2 에서 같은 방식으로 찾아보면 P2 이고 이 과정을 반복하게 되면 P0 -> P2 -> P3 -> P1 -> P4 의 순서로 실행이 되고 종료된다.
  즉, Finish = ( ture, ture, ture, ture, ture ) 로 현재 교착 상태가 아닌 것을 탐지했다.

 

그런데 이때, P2 가 자원 C 를 1개 더 요청했다고 가정했을 때 위의 표는 아래와 같이 수정된다.

그럼 방금 위에서 P0 가 점유하고 있는 자원을 요청한다면, Work = (0, 0, 0) + (0, 1, 0) = (0, 1, 0) 으로 P1, P2, P3, P4 그 어느 누구도 프로세스들의 요청을 충족할 수 있지 않다. 따라서 이 시스템은 현재 교착 상태이다. 그러므로 < P1, P2, P3, P4 > 로 구성된 교착 상태가 존재한다.

 

 

은행원 알고리즘과 교착 상태 탐지 알고리즘의 차이

은행원 알고리즘을 학습한 사람이라면 이 둘이 왜 다르고 왜 나워서 설명하지? 라는 의문이 들 수 있다.

 

자료구조 차이

은행원 알고리즘의 Need 자료구조와 탐지 알고리즘의 Request 자료구조는 다른 자료구조이다. 처음에 보면 같은 것이라고 착각할 수 있다.

• Need 는 각 프로세스(스레드)가 향후 요청할 수 있는 자원의 수
• Request 는 각 프로세스(스레드) 가 현재 할당된 자원말고도 요청하는 자원의 수 이다.

 

교착 상태 해결 방법의 차이

은행원 알고리즘은 교착상태 해결 방법 중 교착 상태 회피 방벙에 속하는 것으로 말 그래도 프로세스가 자원을 요청할 때 교착 상태를 만나지 않기 위해 최악의 상황까지 고려 하는 기법이다. 그리고 교착 상태 탐지 알고리즘은 교착 상태가 일어났는지 일어나지 않았는지 탐색, 탐지 할 때 사용하는 알고리즘 기법이다. 

 

그래서 탐지를 했을 때 교착 상태이다 하면 이제 회복 알고리즘 을 통해 회복하는 것이다.

 

 

 

교착 상태 탐지 알고리즘의 사용

그러면 교착 상태 탐지 알고리즘을 언제 돌려야할까? 라는 질문에 대한 대답은 아래의 두가지로 답할 수 잇다.

• 교착 상태 발생 빈도수
  • 교착 상태가 얼마나 자주 일어나는가?
• 교착 상태가 발생했을 때 영향을 받는 프로세스 수
  • 교착 상태가 일어나면 통상 몇개의 스레드가 거기에 연루되는가? 

교착 상태가 자주 발생하면 탐지 알고리즘도 더 자주 호출해야 한다. 일단 교착 상태가 발생하면 해결할 때까지 프로세스에 할당된 자원들은 유휴 상태가 되고, 교착 상태의 프로세스 수는 점점 늘어난다. 그리고 어떤 프로세스라도 허용할 수 없는 요청을 하면 즉시 교착 상태가 된다. 

 

물론 요청할 대마다 교착 상태 탐지 알고리즘을 호출하면 교착 상태를 회피할 수 있지만 그만큼 연산 시간이 부담이고 오버헤드가 너무 크게 된다. 따라서 이에 대한 대안으로 경제적인 방법을 통해 호출 빈도를 줄이는 방법이 있다 

예를 들어 1 시간마다 또는 CPU 이용률이 40% 로 떨어질 때마다 호출하는 것이다.

 

그래서 이제 교착 상태 탐지 알고리즘을 돌렸을 때 교착 상태가 존재한다고 결정됏다면 교착 상태 회복 을 진행하는 것이다.

 

 

3.2 교착 상태 회복 기법

---

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

그러나 교착 상태 예방은 실제로 구현하기 어렵다. 교착 상태 회피는 구현할 수 있지만 자원을 낭비하는 문제가 있다.

 

따라서 발생한 교착 상태에서 회복하려면 다음 알고리즘이 필요하다

• 시스템 상태를 검사하는 교착 상태 탐지 알고리즘
• 교착 상태에서 회복시키는 알고리즘

교착 상태 탐지 알고리즘을 자주 실행하면 시스템의 성능은 떨어지지만, 교착 상태에 빠진 프로세스를 빠리 발견하여 자원의 유휴 상태를 방지할 수 있다.

 

탐지 알고리즘은 통해 현재 상태가 교착 상태인지 아닌지 판별한 후, 교착 상태라면 이를 회복해야 한다. 한가지 방법은 교착 상태가 발생한 것을 운영자에게 통제해서 직접 처리하게 하는 것이고, 다른 방법은 시스템이 자동으로 교착 상태로부터 회복하게 하는 것이다.  이것은 두 가지 방법이 있고 하나는 순환-대기를 깨뜨리기 위해 단순히 한 개 이상의 프로세스를 중단하는 방법과 교착 상태의 프로세스들에서 자원을 선점하는 방법이 있다.

 

 

프로세스 중단

프로세스를 중단하여 교착 상태에서 회복하는 방법은 다음 두 가지로 나눌 수 있다. 둘 다 시스템이 정지된 프로세스에 할당되어 있는 모든 자원을 해제를 요청한다.

 

• 교착 상태 프로세스를 모두 중단 : 교착 상태의 순환 대기를 확실히 해결하지만 자원 사용과 시간 면에서 비용이 많이 든다. 오랫동안 연산했을 가능성이 있는 프로세스의 부분 결과를 폐기하여 나중에 다시 연산해야 하기 때문이다.
  
  
• 교착 상태가 제거될 때까지 한 프로세스씩 중단 : 한 프로세스를 중단할 떄마다 교착 상태 탐지 알고리즘을 호출하여 프로세스가 교착 상태에서 있는지 확인한다. 교착 상태 탐지 알고리즘을 호출하는 부담이 상당히 크다는 단점이 있다.

 

물론 프로세스를 중단하는 것이 쉽지 않을 수도 있다. 프로세스가 파일을 업데이트하다가 중단된다면 해당 파일은 부정확한 상태가 된다. 마찬가지로 프로세스가 데이터를 프린터에 인쇄하고 있을 때 중단하면 다음 인쇄를 진행하기 전에 프린터의 상태를 정상 상태로 되돌려야 한다.

 

부분 종료 방법을 이용하여 교착 상태에서 벗어나려면 어떤 프로세스를 중단시킬지 결정해야 한다. 이것은 프로세서 스케줄링과 비슷한 정책 결정 문제이다.

 

또 경제적이 문제도 된다. 즉, 최소 비용으로 프로세스들을 중단하는 방법을 찾는 것이다. 최소 비용이라는 것이 명확한 값은 아니지만 보통 다음 기준으로 프로세스를 선정한다.

• 프로세스의 우선 순위
• 프로세스가 수행된 시간과 앞으로 종료하는데 필요한 시간
• 프로세스가 사용한 자원 형태와 수( 예 : 자원을 선점할 수 있는지 여부)
• 프로세스를 종료하는데 필요한 자원 수
• 프로세스를 종료하는 데 필요한 프로세스 수
• 프로세스가 대화식인지, 일괄식인지 여부

 

자원 선점

자원 선점을 이용하여 교착 상태를 해결하려면 프로세스의 자원을 선점해서 교착 상태를 해결할 때까지 이 선점한 자원들을 다른 프로세스에 할당해야 한다. 선점권을 이용하여 교착 상태를 처리하려면, 다음 세가지 사항을 고려해야 한다.

• 선점 자원 선택 : 어느 자원과 어느 프로세스들이 먼저 선점될 것인가?
• 복귀 : 프로세스로부터 자원을 선점하려면 그 프로세스를 어떻게 해야 하는가?
• 기아 상태 : 기아 상태가 발생하지 않는 것을 어떻게 보장할 것인가?

그럼 이 3 가지를 어떻게 해결하는지 살펴보자

 

• 선점 자원 선택 
  • 프로세스를 종료할 때 비용을 최소화하려면 적절한 선점 순서를 셜정해야 한다. 비용 요인에는 프로세스가 점유한 자원 수, 교착 상태 프로세스가 지금까지 실행하는데 소요한 시간 등 매개변수들을 고려해서 선택한다.
• 복귀 
  • 필요한 장눵르 읽은 프로세스는 정상적으로 실행할 수 없다. 따라서 프로세스를 안정 상태로 복귀시키고 다시 시작해야 한다. 일반적으로 안정 상태를 결정하기가 어렵지만, 완전히 복귀시키고(프로세스 중단) 재시작하는 것이 가장 확실한 방법이다. 프로세스를 교착 상태에서 벗어날 정보로만 복귀키실 수 있다면 더 효과적이다.
    그러나 이 방법은 시스템이 실행하는 모든 프로세스의 상태 정보를 유지해야 하는 부담이 있다.
• 기아 상태 
  • 동일한 프로세스가 자원들을 항상 선점하지 않도록 보장하려고 할 때 비용이 기반인 시스템에서는 동일한 프로세스를 희생자로 선택한다. 그러면 이 프로세스는 작업을 완료하지 못하는 기아 상태가 되어 시스템 조치를 요청한다. 따라서 프로세스가 짧은 시간 동안만 희생자로 지정되도록 보장해야 한다. 
    가장 일반적인 해결 방법은 비용 요소에 복귀 횟수를 포함시키는 것이다.

 

 

 

 

여기까지 교착 상태를 처리하는 기본 방법인 예방, 회피, 탐지, 회복 기법들이였다. 

 

물론 한가지 방법만으로 OS에서 발생하는 모든 자원 할당 문제를 해결하는 것을 불가능하다.

 

교착 상태 탐지 알고리즘의 실행 시간은 객체 수가 증가하면 기하급수적으로 늘어난다. 그러므로 세가지 기본 방법을 결합하여 시스템 자원의 혀애마다 최적의 접근 방법을 채택하는 자원의 계층적 순서를 활용한다.

 

예를 들어, PCB (프로세스 제어 블록) 과 같은 시스템이 사용하는 내부 자원은 자원 순서화 예방 방법을 이용할 수 있다. 메인 메모리 자원은 선점을 이용한 방지 방법, 작업(파일 등) 자원은 회피 방법을 활용할 수 있다.

 

 

 

 

---

참고

• 운영체제:그림으로 배우는 구조와 원리 - 한빛 아카데미