Chapter 6. 교착 상태(Deadlock)

교착 상태(Deadlock)

: 두 개 이상의 프로세스가 각자 먼저 확보한 자원을 가진 채 상대방의 자원을 필요로 할 경우, 외부로부터의 조치가 없는 한 아무 일도 못하고 계속해서 기다려야 하는 상태

 

<목차> 

- 교착상태와 관련된 자원의 개념 설명

- 교착 상태 일으킬 수 있는 네 가지 조건

- 다양한 교착 상태의 해결책들

 

교착 상태가 발생되는 근본 원인?

→ 시스템이 가지고 있는 한정적인 자원보다 사용하고자 하는 프로세스들의 요청이 더 많은 경우

(자원이 넉넉하면 문제가 없으나, 최소의 비용으로 최대의 효과를 노리는 경제적 논리에 따라,

거의 사용되지 못할 것임에도 필요 이상의 비용을 들여 많은 자원을 구비할 필요 X)

 

교착상태의 문제점

1. 해당 프로세스들이 더 이상 실행되지 못하여 사용자들에게 응답해 주지 못한다.

2. 보유된 자원들이 교착 상태에서 벗어나기 전까지는 전혀 활용되지 못한다.

→ 시스템 성능 저하로 이어진다.

 

교착상태 VS 무한대기?

- 무한 대기(Indefinite Postponement): 운영체제가 많은 프로세스들의 다양한 요청을 처리하는 과정에서 몇몇 프로세스가 오랜 시간 동안 서비스를 받지 못하게 되는 경우

=> 무한대기는 (교착상태와 달리) 오랜 시간 후에라도 외부적 조치 없이 무한 대기로부터 벗어나 서비스를 받을 수 있다.

 

 

자원(Resource)이란?

자원의 분류

- 하드웨어: 눈으로 보고 만질 수 있는 모든 자원

예) 하드디스크, 테이프 드라이브, 메모리 등

- 소프트웨어 자원

예) 데이터, 메시지

 

▶ 선점 가능성에 따라 (* 선점 가능 = 운영체제에 의해 사용 도중 뺏길 수 있다)

- 선점 가능(Preemptible) 자원: 한 프로세스에 의해 사용 도중 선점(Preemption)이 되어 다른 프로세스에게 할당(Allocation)해 주었다가 이후 다시 원래의 프로세스에게 돌려주어도 되는 자원

예) CPU, 메모리

이유? : 다중 프로그래밍의 성공을 위해

- 선점 불가능(Nonpreemptible) 자원: 선점이 될 경우 자원을 뺏긴 프로세스는 정상적인 진행을 포기해야 하는 불이익을 받게 되는(선점 불가능한) 자원

-> 시스템은 선점 불가능한 자원이 사용 도중 뺏길 수 없도록 한다.

에) 프린터, 테이프 드라이브

이유? : 시스템의 정상적인 진행을 위해

 

▶ 자원이 사용되어지는 방식에 따라

- 공유 가능(Sharble) 자원: 한 프로세스에게 할당된 자원을 동시에 다른 프로세스가 할당받아 같이 사용할 수 있는 자원

예) 공유 가능 프로그램(시스템 프로그램, 유틸리티 프로그램 등), 공유 데이터

- 배타적 사용(Exclusion Use) 자원:  한 프로세스에게 할당된 자원을 동시에 다른 프로세스가 할당받아 같이 사용할 수 없는 자원 

예) CPU, 메모리, 테이프, 버퍼(Buffer), 키보드, 모니터

 

▶ 자원의 속성에 따라

- 순차적 재사용 가능(Serially Reusable) 자원: 할당된 자원이 사용 후 반납(Release)되었을 때 자원 자체는 계속 존재하여 또 다른 프로세스에게 할당이 가능한 자원. 시스템에서 프로세스들이 아무리 사용해도 없어지지 않고 영구히 존재함.

예) CPU, 메모리, 테이프, 하드디스크, 버퍼, 프로그램 등

- 소모성(Comsumable) 자원: 사용 후 사라지는 자원

예) 시그널(Signal), 메시지 등

 

앞으로 설명될 내용에서는 배타적 사용 및 순차적 재사용 가능 자원을 대상으로 교착 상태의 발생과 해결책에 대해 다룰 것이다.

 

프로세스는?

- 교착 상태는 결국 자원과 이들에 대한 프로세스의 행동에 따라 결정된다.

 

< 실행 중인 프로세스가 자원에 대해 취할 수 있는 행동 (2가지) >

1. 필요한 자원에 대한 요청(Request)

▶ 요청된 자원의 상태에 따라

- 사용 가능 시(시스템 보유+현재 아무도 사용하고 있지 않음)

: 자원을 할당 받아 사용 

- 사용 불가 시(다른 프로세스에 의해 사용 중)

: 반납되어질 때까지 대기 상태로 기다림

* 대기 상태: 자력으로 그 상태에서 벗어날 수 없으며, 따라서 자원의 요청이나 반납과 같은 행동은 더 이상 할 수 없다.

2. 사용이 끝난 자원의 반납

 

=> 실행 중인 프로세스가 시스템 서비스를 호출(System Call)함으로써 운영체제에 의해 이루어진다.

+ 반납된 자원으로 그 자원 때문에 대기 중인 프로세스를 깨우는 것도 운영체제이다.

 

 

교착 상태의 원인 (4가지)

아래 4가지 조건을 모두 만족하는 경우에 교착 상태 발생.

ㅡ 한 가지 조건이라도 발생하지 않는다면, 교착 상태는 절대로 발생하지 않는다.

 

■ 자원의 배타적인 사용 (= 상호배제 조건 (Mutual Exclusion Condition))

: 자원이 한정적이더라도 모두 공유가 가능한(여러 프로세스들이 동시에 사용 가능한)

  자원이라면 교착 상태는 발생할 수 없다.

 

■ 자원의 부분 할당 (Partial Allocation) (= 보유와 대기(Hold & Wait) 조건))

: 각각의 프로세스는 자신의 실행 전체 과정에서 필요한 자원을

  필요할 때마다 일부분씩 확보, 실행해 나가다가 어느 시점에

  할당이 불가능한 자원 때문에 이미 확보한 자원들을 소유한 채

  대기 상태가 되어 교착 상태에 빠질 가능성을 높인다.

 

■ 자원의 선점 불가능성 (= 비선점(No Preemption) 조건)

: 선점이 불가능한 자원을 억지로 선점할 경우,

선점의 권한이 주어진 프로세스들은 대기할 필요가 없어 교착 상태를 없앨 수 있으나,

자신의 자원을 선점당한 프로세스들은 정상적인 실행을 포기해야 한다.

=> 결국, 자원의 선점 불가능성을 고수할 경우 교착 상태의 원인이 될 수 있다.

 

■ 자원에 대한 환형 대기 (Circular-Wait) 

: 프로세스들이 자신의 자원은 보유한 채로 서로 상대방의 자원을 요청하고

 결과적으로 대기 상태가 되어버리는 일련의 과정에서 사이클(Cycle)이 생기는 경우,  

 이를 환형 대기라 한다.

 

 

과거에는 교착상태에 대해..?

- 예전에는 시스템 운영 도중 교착 상태가 발생함을 알고 있었지만, 이를 해결하기 위한 구체적 노력을 하지 않았다. 왜냐하면 자주 발생하는 일이 아닌데, 해결 프로그램의 실행에 소요되는 시간과 자원 등의 경비가 많이 들었기 때문이다. 그래서 시스템을 죽이거나(Kill), 시스템을 재부팅(Rebooting)해서 해결하였다. 

- 하지만 요즘은 분산(Distributed) 또는 병렬(Parallel)처리가 일상이 되면서 시스템 내의 프로세스가 아주 많아졌기에, 한정적 자원에 대한 경쟁이 치열해졌고 교착 상태의 발생 가능성이 높아졌다. 그래서 코착 상태에 대해 보다 깊은 관심과 연구가 필요해졌다.

 

 교착 상태의 해결 (4가지 기법)

1. 예방(Prevention) 기법

: 교착 상태가 발생하는 원인 4가지 원인 중 하나를 없앰으로써 교착 상태가 아예 발생하지 않도록 한다.

 

1-1 ) 자원의 배타적 사용 조건을 배제

: 모든 자원을 공유 가능 자원으로 하여 교착 상태의 발생을 차단.

→ but, 프린터나 테이프 장치 등은 공유 불가능 자원(배타적 사용 자원)이므로

   이 조건을 배제하여 교착 상태를 예방하는 것은 불가능하다.

 

1-2) 자원의 부분 할당을 배제 (= all at once (all or none))

: 모두 할당(Total Allocation)하는 것.

- 프로세스들이 각자 자신이 필요한 모든 자원을 미리 할당받아 실행을 시작하도록 함

→ but, 심각한 자원의 낭비 & 무한 대기 가능성

    (모든 자원이 확보되지 못한 프로세스는 대기 상태에 있게 된다.

    또한, 일부 자원만 확보되면 시작할 수 있음에도 불구하고 모든 것을 할당받을 때까지 기다려야 하고,

    할당이 가능했던 일부 자원들은 사용되지 못해 낭비된다.)

 

1-3) 자원의 선점 불가능을 배제

: 선점 불가능한 자원을 선점 가능한 자원으로 만드는 것.

= 일부 자원을 가지고 실행하던 프로세스가 현재 할당이 불가능한 자원을 요청할 경우

자신이 보유하고 있떤 자원을 내놓게 함(선점됨)으로써 비선점 조건을 없애는 것

→ but, 실행 도중 보유한 자원을 내어놓게 되는 프로세스는

    비정상적인 종료 & 심할 경우 처음부터 다시 시작해야 하는 불이익.

    (=지금까지 가동되었던 모든 자원들의 사실상 낭비)

    + 무한 대기 겪게 될 가능성有

 

1-4) 자원의 환형 대기 상황을 배제 (=linear ordering) 

: 모든 프로세스는 자신의 실행 동안 필요한 자원들을 실제로 사용할 시기와 상관없이

  시스템에서 정해놓은 순서에 따라 가져가도록 한 것.

= 즉, 자원들의 순서를 정하고 프로세스들은 이 순서를 지켜 요청하도록 함으로써,

모든 화살표가 한 방향으로만 생성되도록 하여 사이클이 발생될 소지를 없애 교착상태를 없앤다.

→ but, 자원의 낭비 & 무한 대기 가능성

    (순서를 지켜야 하기 때문에 당장 필요 없는 자원을 먼저 할당받아야 하고,

    실제로 필요한 자원을 확보하기 위해 지금 당장 필요 없는 순서상의 하위 자원들을

    확보하느라 많은 시간을 보내야 하는 프로세스도 생길 것이다.)

 

=> 결론적으로, 예방 기법들은 교착 상태에 관한 한 확실하고 명쾌한 해결책이나,

자원의 심각한 낭비와 특정 프로세스의 무한 대기 가능성이라는 큰 문제점을 가진다.

 

 

2. 회피(Avoidance) 기법

: 대기 상태가 길어질지언정 교착 상태로 가는 것은 막겠다는 점에서 예방 기법과 다를 바가 없으나,

  예방 기법은 교착 상태의 발생 조건을 배제하는 방식, 회피 기법은 다른 알고리즘의 방식이라는

  차이점이 있다.

- 자원의 낭비는 예방 기법보다는 덜하나 회피 기법에서도 꽤 발생한다.

 

<Dijkstra의 은행가 알고리즘(Banker's Algorithm)>

- 안전 상태(Safe State)

: 시스템에 있는 모든 프로세스가 유한한 시간 내에 정상적으로 종료될 수 있는 상태 (↔ 불안전(Unsafe) 상태)

= 교착 상태가 발생할 수 없는 상태 

(불안전 상태라고 해서 그것이 곧 교착 상태임을 의미하는 것은 아니지만,

불안전 상태는 교착 상태로 갈 가능성이 있으며 그럴 경우의 방지책이 없다.)

=> 결국 회피 기법은, 시스템의 상태가 안전 상태로만 가도록 지속적으로 제어해나가는 것

 

<그림 6.3> 안전, 불안전, 교착 상태의 관계

 

- 은행가 알고리즘의 정상적 작동을 위해 시스템에 요구되는 몇 가지 가정들

① 시스템 내의 프로세스 수가 고정되어 있어야 한다.

② 자원의 수 역시 고정되어 있어야 한다.

③ 각 프로세스가 요구할 자원의 최대 개수가 알려져야 한다.

④ 각 프로세스는 할당받은 자원을 사용 후 반드시 반납하여야 한다.

* ①, ③의 이유로,  현실적으로 지켜지기 힘듦 -> 이론적인 접근의 방편으로 언급.

* 하지만, 위와 같은 조건이 충족되었을 경우에 회피 기법은

  예방 기법에서는 시작도 못하고 있던 프로세스를 실행시킬 수 있어

  (예방 기법과 비교했을 때)자원 낭비의 감소를 기대할 수 있다.

 

- Dijkstra의 은행가 알고리즘

안정 상태의 판단: "현 상태에서 모든 프로세스가 정상적으로 종료할 수 있는 길이 적어도 하나 이상 있는가?"

º 각 프로세스가 현재 요구량을 유지한 채 앞으로 더 요구할 가능성이 있는 자원의 수

= 최대 요구량 - 현재 보유량

º 시스템이 보유한 전체 자원의 수

= 각 프로세스의 현재 보유량과 여유량을 합친 것

 

<표 6.1> 안정 상태의 예

<표 6.2> 불안정 상태의 예

 

 

3. 탐지(Detection) 기법

: 교착 상태를 찾아내는 것.(= 교착 상태의 발생이 허용됨)

* 탐지는 교착상태가 발생되도록 놓아두었다가 발생 시 또는 발생 후에 교착 상태를 탐지하여 조치하는 방법으로,

이것은 복구 작업을 수반하므로 탐지와 복구는 같이 묶어 하나로 보아도 된다.

- 최소한 "어떤 프로세스가 어떤 자원을 가지고 있는가?"와

  "어떤 프로세스가 어떤 자원에 의해 대기 상태가 되어 있는가?"의 정보는 있어야 한다.

 

잠깐!

운영체제가 하는 일의 대부분은 자원 관리. (= 자원 관리자(Resource Manager)

=> 운영체제가 관리하는 모든 자원들은 그들에 대한 정보가 프로그램이 처리할 수 있는 형태로 저장되어 있고,

(표(Table), 배열(Array), 벡터(Vector), 행렬(Matrix), 리스트(List) 등)

이들에 대한 관리 작업이란 실제로는 저장된 자료에 대한 읽기와 쓰기, 수정 및 추가, 삭제 등의 실행을 하는 것이다.

 

<RAG(=Resource Allocation Graph) 자원 할당 그래프>

: 현 시스템의 상황 (위에서 말한 정보들) 을 표현하는 그래프

 

① RAG는 방향성(Directed) 이분(Bipartite) 그래프이며 노드(Node)와 에지(Edge)들로 이루어져 있다.

- 노드: 프로세스와 자원들

- 에지(화살표): 프로세스와 자원들 간의 할당과 대기상황

(+) 프로세스로부터 자원으로 향하는 에지는 보통 '요청 중'과 '대기 상태가 됨'이라는 2가지 의미를 가진다.

=> 즉, 에지 하나가 경우에 따라 다르게 해석될 수 있다는 의미이고,

이럴 경우 RAG로 교착 상태를 탐지하는 작업이 훨씬 어려워지므로

요청 중이라는 상황이 생기지 않게 시스템이 바로 대처하면

(할당 혹은 대기로 바로 결정 = 즉시 할당 상태(Expendient State)),

에지들의 방향이 나타내는 상황이 할당 아니면 대기와 같이 두 가지로 분명해져 탐지 작업이 용이하다.

② RAG에서 자원 노드는 그 자원의 형(Type)을 나타내고, 그 안의 작은 동그라미가 자원의 개수를 나타낸다.

=> 즉, 한 자원 형에 여러 개의 자원이 있을 수 있음을 나타낸다. 

③ 한 자원 형에는 자원의 개수를 나타내는 정수(ti)가 있으며,

   임의의 노드 a로부터 다른 노드 b로 향하는 에지의 개수는 | (a, b) | 로 표현한다.

 

 => 현 상황에서  "어떤 프로세스가 어떤 자원을 가지고 있는가?"와

 "어떤 프로세스가 어떤 자원에 의해 대기 상태가 되어 있는가?" 뿐만 아니라,

여유량이 있는 자원 및 대기 상태가 아닌 프로세스들에 대한 정보를 알려준다.

 

<그래프 제거(Graph Reduction) 방법>

- 싱크(Sink): 자원으로 향하는 에지가 없는 프로세스. 즉 대기 상태가 아닌 프로세스(unblocked process)

- RAG의 모든 싱크에 대해서 에지를 제거하는 작업을 계속하여 에지가 모두 제거되어 버리면(Completely Reducible) 교착 상태가 없다고 판단하게 되며, 만약 지원지지 않는 에지들이 있다면(Irreducible) 이 에지들에 연결되어 있는 프로세스들이 교착 상태에 빠져 있는 것으로 결론난다.

 

<그래프 탐색(Search) 방법>

: 요청 후 대기 상태로 될 때가 교착 상태를 형성시킬 가능성이 있는데,

이때의 대기 상황을 나타내는 에지로부터 방향을 따라 경로(Path)를 탐색해보면 두 가지 결론 중 하나가 가능하다.

1) 탐색 도중 싱크가 발견되면 교착 상태는 없다고 판단한다. (나머지 경로는 더 탐색할 필요가 없음)

= 애초에 대기 상태를 만든 요청은 단순한 대기일 뿐이며 교착 상태로까지 만들지는 않는 행동이었다는 것.

2) 노드 자신으로 되돌아오는 사이클이 발견되면 교착 상태가 된 것으로 판단할 수 있다.

= 중요한 것은 사이클의 발견이 곧 교착 상태라고 보는 것은 모든 자원 형이 한 개씩의 자원을 가질 경우이며,

그렇지 않을 경우의 사이클 발견은 단지 교착 상태의 가능성을 높이는 필요조건일 뿐이다.

(+)

모든 자원형이 하나의 자원만을 가지고 있을 경우, cycle 발견 -> deadlock.

한 자원형이라도 다수 개의 자원이 있는 경우, 노트(Knot)라는 자료 구조의 발견 -> deadlock.

(cycle의 발견은 deadlock의 필요조건일 뿐, 필요충분조건이 아니다!)

 

- Reduction은 시간이 꽤 걸리기에 주기적으로 하는 방식

  (직전의 reduction 다음에 바로 발생한 deadlock은 다음 reduction 때 발견 가능)

- Search는 프로세스들이 누구라도 block이 될 때마다 자주하는 방식

  (자기가 갈 수 있는 path만을 쭉 따라감. 다른 건 보지 X)

 

4. 복구(Recovery) 기법

: 교착 상태로부터 벗어나기 위한 방법

*교착 상태의 원인 = "모자란 자원과 이것을 요청하고 대기 상태가 되는 프로세스들"

-> 1) 교착 상태에 포함되어 있는 한 개 이상의 프로세스를 강제로 종료시켜

        이들로부터 반납되는 자원들을 나머지 프로세스들에게 줌으로써 해결하거나,

    2) 교착 상태를 벗어나기 위해 필요한 추가의 자원을 어디거든 갖고 와 할당해 줌으로써 해결.

 

<두 가지 방식의 복구 기법>

■ 프로세스의 종료 (Process Termination) 방식

>> 1-1) 교착 상태에 포함되어 있는 한 개 이상의 프로세스를 강제로 종료시켜

     이들로부터 반납되는 자원들을 나머지 프로세스들에게 줌으로써 해결

문제> 어떤 프로세스들을 종료시킬 것인가?

: 종료 비용(Termination Cost)를 따져 교착 상태로부터 복구될 때까지 종료 비용이 최소인 프로세스부터(Lowest-termination-cost Process First) 종료시켜 나간다.

- 비교적 간단하나 프로세스 하나를 종료시킬 때마다 교착 상태가 제거되었는지 알아보아야 한다.

 

>> 1-2) 교착 상태에 있는 프로세스들의 집합에서 가능한 모든 부분집합을 만들어

     이 집합들에 속하는 프로세스들을 종료시켰을 경우의 비용을 따져

     역시 최소 비용이 드는 부분집합에 속하는 프로세스들을 한꺼번에 종료시키는 방식

- 최소 비용의 프로세스들을 고를 수는 있으나 모든 부분 집합에 대해 비용을 계산하기가 복잡하고 힘들다.

 

=> 결국, 두 가지 방법 모두 종료 비용의 최소화가 관건!

* 종료 비용 ~ by. 프로세스의 우선순위(Priority)나 종류, 실행된 시간의 크기, 남은시간 등.

: 우선순위 낮음 /  실시간 아님 / 실행된 시간 적은 것 / 남은 시간이 큰 것 ㅡ 일수록 종료 비용이 저렴하다.

 

 

 

■ 자원의 선점에 의한 방식 

>> 2) 교착 상태를 벗어나기 위해 필요한 추가의 자원을 어디서든 갖고 와 할당해 줌으로써 해결.

어디서 가져올까?

: 필요한 자원을 가지고 있는 프로세스로부터 강제로 뺏어(선점하여)

  교착 상태에 있는 프로세스들에게 줌으로써 해결할 수밖에 없다.

~ 프로세스 종료 방식과 다를 게 없어 보이지만 이 방식에서 자원을 선점 당하는 프로세스는 교착 상태와는 전혀 상관이 없지만 단지 해당 자원을 가지고 있다는 이유 때문에 선택될 수 있다는 것이다. 물론 이 방식에서도 선점 시의 최소 비용은 따져야 한다.

 

*프로세스의 강제 종료 = 복구 비용을 키우는 주요인 (낭비 요인)

ㄴ<강제 종료 시의 낭비를 줄이기 위한 방법>

■ 검사점 지정(Checkpointing)과 재시작(Restart)

*검사점(Checkpoint): 프로세스들이 실행의 중간 중간에 그 시점까지의 실행 결과를 보존하고 표시해주는 것

- 강제로 종료될 때는 아예 처음으로 돌아가는 것이 아닌, 가장 최근의 검사점부터 차례로 하나씩 되돌린다.

- 따라서 종료된 프로세스는 처음부터가 아니라 최종적으로 되돌려졌던 검사점에서 보존된 내용으로 재시작을 할 수 있어 잃게 되는 일의 양을 최소화할 수 있다.