[OS] 08. 교착상태 (Deadlock)

(1) 개요

컴퓨터 시스템은 한정된 수의 자원(resource)으로 구성된다.

✔ 교착상태 정의

• 어떤 프로세스가 수행하려고 특정한 자원을 위하여 무한정 기다려도 도저히 해결할 수 없는 상태이다.
• 하나 또는 그 이상의 프로세스가 발생되지 않는 어떤 특정한 사건(event)을 기다리고 있는 상태이다.
• 교착상태는 컴퓨터 시스템의 효율을 급격히 감소시키는 문제점이 있다.

 

✔ 교착상태 모델

교착상태 예시

서로 강의 반대방향으로 향하는 두 사람이 징검다리를 건너면서 같은 돌을 디디려 할 때 발생하는 문제가 발생하는데 이를 교착상태라고 한다.

 

해결방법 : 프로토콜(규약)을 이용하여 해결해야 한다.

• 반대편에서 강을 건너는 사람의 유무를 확인해야 한다.
• 두 사람이 동시에 출발해도 교착상태가 발생하고, 두 사람이 모두 기다려도 교착상태가 발생한다.
• 한 쪽에 우선권을 주면 하나 이상의 프로세스가 강을 건너기 위해 무작정 기다리는 경우가 발생해 starvation이 일어날 수 있다.

 

정상적인 프로세스의 시스템 자원(CPU사이클, 메모리 공간, 파일, 입출력 장치 etc.) 이용 순서

1. Request(요청) : 다른 프로세스에 의하여 자원이 사용중일 때, 요청한 자원을 얻을 수 있을 때까지 기다려야 한다.
2. Use(사용) : 프로세스가 자기가 요청하여 얻은 자원을 작동할 수 있다.
3. Release(해제) : 프로세스는 해당 자원이 미리 요구되어 있거나 할당되어 있으면, 그 자원을 사용한 후에 돌려주어야 한다.

 

시스템 자원에 대하여 교착상태 발생 가능성을 확인한다.

환형 대기(Circular wait)가 존재하면 교착상태가 발생할 가능성이 있다.

 

➤  Indefinite postponement (무기한 연기)

• 교착상태와 유사하나 교착상태는 아니다.
• 한 프로세스가 시스템에 의해 처리되는 동안 다른 프로세스의 스케줄링이 끝없이 연기될 가능성을 말한다.
• 우선순위가 낮은 프로세스가 무한정 기다리는 현상을 말한다.
• Aging기법으로 해결한다. (교착상태는 Aging기법으로 절대 해결이 되지 않는다)

 

 

➤ 교착상태 조건

4가지 조건을 동시에 필요 충분조건으로 만족해야 교착상태가 발생한다. 최소 한 가지 조건을 제거하면 교착상태 발생을 예방할 수 있다.

 

1. Mutual Exclusion(상호 배제) 조건 : 프로세스들이 자원을 배타적으로 사용하고 있음
2. Hold and Wait(점유와 대기) 조건 : 프로세스가 적어도 하나의 자원을 점유하면서, 다른 프로세스에 의해 점유된 다른 자원을 요구하고 할당 받기를 요구
3. No preemption(비선점) 조건 : 프로세스가 자신의 작업 수행이 끝날 때까지 해당 자원을 반환하지 않음
4. Circular Wait(환형 대기) 조건 : 프로세스들 간의 환형 대기가 존재

 

➤ 자원 할당 그래프

 

예제 1

• 프로세스 P1은 자원 형태 R2 한 개를 점유하고, 자원 형태 R1 한 개를 기다리며 대기함
• 프로세스 P2 는 R1과 R2를 각각 한 개씩 점유하고, 자원형태 R3 한 개를 대기함
• 프로세스 P3는 R3 한 개를 점유함
• 그래프에 순환(cycle)이 존재하지 않으면, 시스템 내 어느 프로세스도 교착상태가 아닌 반면, - 그래프에 순환이 존재하면 교착상태가 될 가능성이 있음

 

예제 2

• 그래프에서 최소한 2개의 순환이 시스템 내에 존재하고 있음
  o P1→R1→P2 →R3 →P3 →R2 →P1
  o P2→R3 →P3 →R2 →P2
• 어떻게 해도 순환을 제거할 수 없음
• 결론적으로, 프로세스 P1, P2, P3는 교착 상태에 있음

 

예제 3

• 그래프는 다음과 같은 순환을 가짐
  o P1→R1→P3→R2→P1
• 프로세스 P4가 자원형태 R2를 해제할 수 있음. 즉, R2가 P4에게서 해제된 후, 이 자원이 P3에 - 할당되면, 순환이 없어짐
• 결론적으로, 프로세스 P1, P2, P3, P4는 교착상태가 아님

 

 

➤ 교착상태 해결 방법

• 교착상태 예방 (Deadlock Prevention) : 교착상태가 아예 발생하지 않도록 하는 것
• 교착상태 회피 (Deadlock Avoidance) : 할당하기 전에 교착상태 발생 유무를 체크하는 것
• 교착상태 탐지 (Deadlock Detection) : 자원 할당 후에 주기적으로 검사하는 것
• 교착상태 회복 (Deadlock Recovery) : 탐지 후에 교착상태가 발생했을 때 회복하는 것

 

(2) Deadlock Prevention (교착상태 예방)

• Havender가 제시한 것으로 교착상태 조건 및 교착상태 발생 가능성을 사전에 제거한다.
• 상호 배제 조건은 제외한다. 상호 배제를 없애면 교착 상태가 절대 발생하지 않으나, 임계 구역에서의 프로세들 간의 문제가 발생한다.

 

1. 점유와 대기조건 제거

방법

• 각 프로세스는 필요한 자원들을 모두 한꺼번에 신청한다.
• 요구한 자원을 전부 할당하여 주거나 또는 하나라도 부족하면 전혀 할당하지 않는 방식이다.

 

단점

• 한꺼번에 원하는 자원을 제공할 수 없을 경우에는 무한 연기의 위험이 발생한다.
• 많은 자원이 한꺼번에 할당될 때까지 기다리기 때문에 중간에 자원을 사용할 수 없는 자원 낭비의 위험이 발생한다.

 

2. 비 선점 조건 제거

• 방법 - 추가 자원에 대한 요구가 거절당했다면 그 프로세스는 자원을 전부 반납한다.
• 단점 - 무한 연기가 발생할 가능성이 높다.

 

3. 환형 대기조건 제거

방법

• 모든 자원에게 고유 번호를 부여한다.
• 현재 가지고 있는 자원보다 더 큰 번호를 가진 자원만을 요청하도록 제한하는 방법이다.
  • 프로세스들이 자원을 요청할 때 번호가 증가하는 순으로 요청한다.

단점

• 자원 번호 부여 시에 자원을 사용하는 순서를 반영할 수 있어야 하나, 예상한 순서와 다르게 자원을 요구하는 작업들은 실제로 자원을 사용하기 훨씬 전부터 자원을 요구하고 점유하고 있어야 한다.
• 새로운 자원이 시스템에 추가되면 자원 번호를 다시 작성해야 한다.

 

(3) Deadlock Avoidance (교착상태 회피)

• 자원을 할당할 때 다른 프로세스와 자원할당을 참조하여 교착상태가 발생하는지를 미리 검사하여, 교착상태가 발생할 것 같으면 할당하지 않도록 하는 방법이다.
  • 예시) 교차로에서 꼬리물기 진입을 미리 단속
• *안전상태 체크 알고리즘(자원 요청 알고리즘)인 은행가 알고리즘을 이용한다.
• 은행가 알고리즘의 결과가 불완전상태이면 교착상태 가능성이 있으며, 안전상태면 가능성이 없다.

*Safety State Check Algorithm : 시스템이 안전 상태인지 체크하기 위한 알고리즘이다.

*Safety State : 모든 프로세스들이 교착 상태를 일으키지 않으면서 수행을 끝낼 수 있는 순서가 최소한 하나 이상 존재할 때의 상태다.

은행가 알고리즘 : 시스템이 안전상태인지를 체크한 후, 자원을 할당하는 알고리즘

 

은행가 알고리즘 단점

• 사용 가능한 자원의 수를 미리 파악하기 어렵다.
• 남아 있는 프로세스의 수가 수시로 변경되는 어려움이 있다.
• 모든 요청에 대하여 주어진 시간 내에 자원을 할당할 수 있도록 더욱 강력한 보장이 필요하다.
• 사전에 각 프로세스가 필요한 자원의 최대량을 제시해야 하나, 현재 OS에서는 각 프로세스의 최대 요구량을 파악하기 어렵다.

 

(4)  Deadlock Detection (교착상태 감지)

• 시스템의 상태를 검사하는 알고리즘으로 주기적으로 교착 상태를 찾아낸다.
• 만일 교착 상태가 탐지되면 시스템은 이 교착 상태로부터 회복과정이 수행되어야 한다.
• 프로세스에 할당된 자원에 관한 정보뿐만 아니라 자원 할당 요청에 대한 정보도 유지되어야 한다.
• 시스템이 교착 상태에 있는지, 아닌지를 알아내기 위해 탐지 알고리즘인 은행가 알고리즘이 필요하다.

 

(5) Deadlock Recovery (교착상태 회복)

• 프로세스들의 자원의 요구와 할당에 대해 순환 상태(환형 대기)가 발생하면 순환 상태가 없어질 때까지 프로세스를 없앤다.
• 특정 알고리즘은 없다.

 

문제점

• 시스템이 교착 상태인지를 파악하기 어렵다.
• 대부분의 시스템은 프로세스를 무기한 정지시키고 일부 프로세스를 제거한 후 다시 진행시키는 기능이 거의 없고, 특히 실시간 프로세스와 같은 무 중단 시스템들은 이러한 기능이 없다.
• 효율적인 중지/재개(suspend/resume) 기능이 있다고 하더라도 상당한 추가 부담이 필요하고 숙련된 operator가 필요하다.
• 교착 상태에 있는 프로세스들은 우선순위가 없으며, operator가 임의로 중단시킬 프로세스를 결정해야 한다.

 

➤ 교착 상태 회복 방법

• 교착 상태에 있는 한 개 또는 그 이상의 프로세스를 희생시켜 보유 자원의 선점을 이용한다.
• Victim 선정, Rollback 시점, Starvation을 고려해야 한다.

 

Victim 선정

• 어느 프로세스를 희생시킬 것인가의 선정한다.
• 선정 기준
  • 프로세스들의 우선순위를 고려해야 한다.
  • 프로세스가 얼마나 오랫동안 연산하였고, 또 일을 완료하기 위해서 앞으로 얼마만큼의 시간이 요구되는가?
  • 프로세스가 어떤 유형의 자원과 몇 개의 자원들을 사용하고 있는가?
  • 몇 개의 프로세스를 희생시킬 것인가?

 

Rollback 문제

• 어느 정도의 시간(범위)를 가지고 복귀시켜야 하는가 하는 기간의 결정 문제를 말한다.
• 복귀 방법
  • 프로세스를 완전히 취소한 후 처음부터 다시 시작하는 방법이 있다.
  • 프로세스를 최소한의 시간 범위 안에서 재귀시키는 방법이 있다.

 

Starvation 문제

• 반복적으로 희생자로 선정될 수 있는 가능성을 없애야 한다.
• 기근 해결 방법
  • 희생자로 선정되는 반복 횟수의 상한선을 정하여 더 이상 희생자가 될 수 없도록 하는 방법이다.