운영체제 10주차 - Deadlock

---

 

교착상태(Deadlock)란?

• 여러 프로세스들이 각자 자원(CPU, 메모리, IO장치, 파일, 세마포어 등)을 점유하고 있으면서 다른 프로세스가 점유하고 있는 자원을 요청하면서 무한히 대기하는 상태
  • e.g. 1: 시스템에 두 개의 테이프 드라이브가 있을 때, 프로세스 P1과 P2가 하나씩 테이프 드라이브를 사용하면서 상대방 프로세스의 테이프 드라이브를 필요로 함.
  • e.g. 2: 두 개의 세마포어 A와 BP0 P1wait(B) wait(A)
  • wait(A) wait(B)
  • 각 자원은 여러 개의 사례(Instance)를 가질 수 있다(e.g. 시스템에 두 개의 CPU가 있다면 CPU 자원 유형은 두 개의 instance를 가짐)
  • 프로스세가 자원을 사용하려면 다음 순서로 수행한다.
    1. 요청(request): 요청이 즉시 허용되지 않는 경우, 자원을 얻을 때까지 대기
    2. 사용(use)
    3. 해제(release) or 반환(return)

 

교착상태(Deadlock)는 다음 네 가지 조건이 동시에 만족될 때 발생한다.

1. 상호배제(Mutual Exclusion): 한 번에 오직 한 프로세스만이 자원을 사용할 수 있다.

2. 점유와 대기(Hold and Wait): 프로세스가 적어도 하나의 자원을 점유하고 있으면서 다른 프로세스가 점유하고 있는 자원을 추가로 얻기 위해 대기한다.

3. 비선점(No Pressmption): 점유된 자원은 강제로 반환될 수 없고, 점유하고 있는 프로세스가 작업을 마치고 자원을 자발적으로 반환한다.

4. 순환 대기(Circular Wait): 대기하고 있는 프로세스 집합(P0, P1 ... Pn)에서 P0은 P1이 점유한 자원을 대기하고, P1은 P2가 점유한 자원을 대기하고, Pn-1은 계속해 Pn을 대기하며, Pn은 P0이 점유한 자원을 대기한다.

 

 

 

 

 

1. Mutual Exclusion: R1은 P1 혼자 사용, R3 자원은 P3 혼자 점유, R2 자원은 인스턴스가 2개를 각자 P1와 P2가 혼자 점유하고 있다.

2. Hold and Wait: p1, p2, p3 프로세스 3개 한 자원을 점유하면서 대기하고 있다, P1은 R2를 점유하면서 R1을 대기, P2는 R1를 점유하고 R3를 대기, P3는 R3를 점유 R2를 대기

3. No Preemption: 3개의 프로세스가 점유하고 있는 자원을 반환하지 않고 요청한 자원을 대기하고 있다.

4. Circular Wait: P1은 P2가 점유한 자원 R1을 대기하고, P2는 P3가 점유하고 있는 R3를 대기하고 P3는 P1과 P2가 각각 점유하고 있는 R2를 대기하고 있다.

 

P2와 P4는 현재 요청한 자원은 없고 점유한 자원만 있기 때문에 P2와 P4가 작업을 마치면 자원을 반납하므로 교착상태가 아니다!!

 

---

교착상태(Deadlock) 해결방법

1. 교착상태가 발생하지 않도록 예방(Prevention)

2. 교착상태가 가능한 회피(Avoidance)

3. 교착상태를 허용하고, 발생을 탐지한 후, 복구(Detection & Recovery)

※ 대부분의 운영체제는 문제를 무시하고 교착상태를 발생하지 않는다고 가정한다. 그 이유는 대부분의 시스템에서 교착상태가 잘 발생하지 않을뿐더러 위에서 제시한 교착상태 예방, 회피, 탐지 및 복구 방법은 사용하는 데 비용이 많이 든다.

 

교착상태 예방(Prevention)

교착상태 발생 네 가지 조건 중에서 하나라도 성립되지 않으면 됨

• Mutual Exclusion
  • 공유 가능한 자원들은 동시 접근을 허용(e.g. 읽기 전용 파일)

• Hold and Wait
  • 프로세스가 실행되기 전에 사용할 모든 자원을 함께 요청
  • 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청
  • 단점
    • 자원의 낮은 사용률: 자원을 실제로 사용하지 않는 동안에도 자원을 점유하고 있어야 함.
    • 기아 상태 가능성

• No Preemption 예방 방법
  • 어떤 자원을 가진 프로세스가 추가 자원을 요청하여 대기하게 되면, 가지고 있던 자원을 반환하고 대기함.
  • 이후, 대기 중인 프로세스는 이전의 자원들과 새 자원을 모두 갖게 되면 다시 시작함.

• Circular Wait 예방 방법
  • 모든 자원 유형에 일련 번호를 부여하여, 프로세스는 오름차순으로 자원을 요청

 

※ Deadlock 예방법들은 자원의 사용률 을 저하시키는 문제점이 있다.

 

교착상태 회피(Avoidance)

• 각 프로세스는 자원 유형(instance)마다 필요한 최대 개수를 선언하고, 운영체제는 이 정보를 이용해서 다음과 같이 교착상태가 되지 않도록 회피 한다. 하지만 회피를 하기 위해서는 프로세스가 운영체제에게 사용 예정인 자원을 OS에게 알려줘야 하지만 이걸 사전에 알려주기란 거의 제한적이라서 실제로 구현하기는 어렵다.

• 어떤 프로세스가 자원을 요청하면, 이 자원을 할당한 후의 상태가 안정 상태인지 검사.
  • 안정 상태(프로세스가 순차적으로 작업을 마칠 수 있는 상태)이면 자원 할당
  • 불안정 상태이면 자원을 할당하지 않음 → Deadlock 회피

 

 

 

안정 상태 예

 

P0는 현재 5개의 자원을 사용 중인데 5개 자원을 추가적으로 요청하고 싶은데, 남은 자원은 3개이므로 P0는 수행할 수 없다. 다음으로 P1은 현재 2개의 자원을 점유하고 있는 채로, 추가적으로 2개의 자원을 요청하고 있고, 남아 있는 자원이 3개이므로 P1은 수행 가능하다. (P3는 마찬가지 이유로 불가)

1. P1이 시작하고 추가적으로 자원 2개를 요청하면 P1은 4개의 자원을 소유하고 있고, 가용 자원은 1개이다. P1이 종료되면 4개의 자원이 반납돼서 남아있는 자원은 총 5개가 된다.

2. P2는 2개의 자원을 점유 중이고 7개의 자원을 요청하고 싶지만 남아있는 자원이 5개이므로 P0이 수행된다. P0은 5개의 자원을 점유하고, 5개의 자원을 추가적으로 요청하면 10개의 자원을 점유하고, 남아있는 자원은 0개가 된다. P0가 작업을 마치면 남아있는 자원 10개를 반납한다.

3. 마지막으로 P2는 2개의 자원을 점유하고, 7개의 자원을 요청하면, 남아있는 자원이 10개이므로 P2에게 7개의 자원을 제공할 수 있다. 자원을 받은 P2가 작업을 마치고 정상적으로 종료했기 때문에 안정상태이다.

P1, P2, P3가 순서대로 테이프를 할당 받아서 작업을 마칠 수 있으면 안정 상태. → 위 시나리오는 안정상태가 되기 위한 검사이지 실제 수행 순서가 아님!!!

 

 

실제 운영체제가 CPU 스케줄링을 해서 P2가 선택이 됐다고 가정하자. P2가 추가 자기 테이프를 요청하면 위 그림에서 보다시피 P2에게 5개의 테이프를 주고 싶지만, 현재 가용 가능한 테이프는 3개이므로 불가하고, 테이프 3개를 요청한다 하더라도, 할당을 해준 그 다음 상태가 안정인지 불안정인지를 봐야한다.

할당한 후에 그 다음 순서가 있는지 검사해보자. 현재 남은 자원은 0개이다. P0이 추가적으로 필요한 자원은 5개, P1은 2개, P3는 3개를 받은 상태에서 추가적으로 4개가 더 필요한 상황이다. 이 세 개의 프로세스 모두 추가적인 자원이 요청하고 있는 상황인데, 남은 가용 가능한 자원이 0개이므로 그 다음 상태로 나아갈 수가 없으므로 불안정 상태이다. 즉 , P2에게 3개의 자원을 할당해주면 불안정 상태가 되므로 회피(Aviodance)를 해야 한다. 이게 회피 상태이다.

 

불안정 상태라고 해서 반드시 교착 상태는 아니지만, 불안정 상태가 되면 교착 상태가 될 가능성이 있으므로 사전에 회피하는 것이다.

 

Deadlock 회피 알고리즘 - 은행가 알고리즘(Banker's Algorithm)

 

• 각 프로세스는 실행되기 전에 필요로 하는 모든 자원의 형태들의 최대 개수를 선언한다.

• 프로세스가 자원을 요구할 떄, OS는 자원을 할당한 후에도 안정 상태로 남아 있는지를 검사한다. 즉, 안정 상태에 있으면 자원을 할당하고 그렇지 않으면 다른 프로세스들이 자원을 해제할 때까지 프로세스를 대기시킨다.

• 안정 상태는 프로세스가 프로세스들이 하나 씩 수행을 마칠 수 있는 순서가 있다면 안정 상태
  • P0은 추가적으로 필요한 자원의 개수가 (A, B, C) → (7, 4, 3)인데, 남은 자원은 (3, 3, 2)이기 떄문에 P0은 실행할 수 없다.
  • P1(1, 2, 2) → 가능
  • P2 → 불가능
  • P3 → 가능
  • P4 → 불가능
  • 즉 처음에 실행할 수 있는 프로세스는 여러 개가 될 수 있고, 이렇게 종합한 결과 P1→P3→P4→P2→P0 순서로 프로세스를 실행하면 문제 없이 마칠 수 있기 때문에 이 시스템은 P1→P3→P4→P2→P0 순서일 떄 안정 상태에 있다. 여기서 주의해야 할 점은 P1→P3→P4→P2→P0 이 순서는 말 그대로 시스템이 안정 상태로 끝마치기 위한 순서(검사)이지 실제 실행 순서가 아니다!!

 

1. 위 그림에서 (1, 0, 2) 자원을 할당해주면 (3, 0, 2)가 되는데 이 상태가 안정 상태가 되어야지 (1, 0, 2)를 할당하는 것이다. 현재 가용 가능한 자원은 (A, B, C) = (2, 3, 0)인데, P1과 P3를 선택 가능하다. P1에게 (0, 2, 0)을 할당하면 남은 자원은 (2, 1, 0)이고 P1은 필요한 모든 자원을 점유했으므로 작업을 마칠 수 있다. P1이 작업을 마치면서 반납하는 자원의 (3, 0, 2)이므로 총 남은 자원은 (5, 2, 2) 가 된다.

2. 이제 두 번째 수행할 프로세스를 찾아보자, 현재 가용 가능 자원이 (5, 3, 2)이다, P3과 P4가 선택 가능하다.

 

위 상태는 할당할 수 있는 자원으로 어느 필요도 만족할 수 없으므로 불안정 상태!

---

Deadlock 탐지(Detection)

• 교착 상태가 일어나도록 허용한다.

• 교착 상태가 발생했는지를 탐지하는 알고리즘 수행

• 교착 상태로부터 회복하는 알고리즘 수행

 

탐지 방법1 - 각 자원 유형(instance)이 하나의 자원을 가진 경우

• 탐지 알고리즘은 주기적으로 수행하면서 대기 그래프에 주기가 생기는지 검사(참고) 그래프의 정점이 n개이면 n^2 연산이 필요

• 대기 그래프(wait graph)

 

각 자원 유형(instance)이 여러 자원을 가진 경우

• 교착 상태 회피 알고리즘인 은행가 알고리즘과 비슷한 방법 사용

• 은행가 알고리즘과 차이점
  • 프로세스가 사용할 자원의 최대 개수를 미리 알지 않는다.
  • 자원을 할당한 후의 상태를 검사하는 것이 아니라 현재 상태를 검사하여 교착 상태를 탐지
  • 주기적으로 탐지 알고리즘을 수행.

 

 

• P0, P2만 선택 가능 → P0을 한 번 선택해보자. → P0 프로세스 종료하면 (0, 1, 0) 반납 → 그 다음으로 사용할 수 있는 프로세스가 P2밖에 없으므로 P2에게 자원 주고 P2 종료 → P2 자원 반납 → (3, 1, 3) → P1, P3, P4 가능 → P3 선택 → P3 종료 → (5, 2, 4) → P1 선택 → P1 프로세스 종료 및 반납 → P4 수행 → P4 종료.

• <P0, P2, P3, P1, P4> 가 수행 가능하므로 교착 상태가 아님.

 

P0 다음에는 어떤 프로세스가 올 수 없으므로 P1, P2, P3, P4 프로세스가 교착 상태에 빠져있다(탐지). 운영 체제가 주기적으로 해당 시스템이 교착상태에 빠지는지 검사를 하고, 해당 시스템이 교착 상태에 빠졌다는 것을 알아차리면 어떤 조치를 취해야 할까?

 

교착 상태로부터 회복(Recovery)

• 시스템 관리자가 수동적으로 처리

• OS가 자동적으로 처리

• 프로세스 종료
  • 교착 상태에 있는 모든 프로세스 종료
  • 교착 상태가 해결될 때까지 프로세스를 하나씩 종료

• 자원 선점(자원을 뺐자!): 프로세스로부터 자원을 빼앗아서 이들을 교착 상태가 해결될 떄까지 다른 프로세스에게 준다)