운영체제 - 교착 상태(Deadlocks)

7. 교착 상태(Deadlocks)

▶ 교착 상태: 대기중인 프로세스가 요청한 자원들이 다른 대기중인 프로세스에 의해서 점유되어 있기 때문에 결코 프로세스 상태를 변경시킬 수 없는 상태

▶ 대부분의 현재 운영체제들은 교착 상태 방지 기능을 제공하지 않고 있음 → 추가될 것임

7.1 시스템 모델(System Model)

▶ 시스템은 자원을 확보하려고 경쟁하는 여러 프로세스에 분배해야 할 한정된 자원으로 구성됨

ex) 중앙처리장치 주기, 기억 장치 공간, 파일, 입출력 장치 등

▶ 프로세스의 자원 이용 순서

① 요청(request): 요청한 자원이 사용중일 경우에는 해제될 때까지 대기해야 함

② 사용(use): 자원 상에서 동작함

③ 해제(release): 사용 후 자원을 해제함

▶ 자원의 요청과 해제: 시스템 호출에 의해 행해짐

- 장치(device)의 요청(request)/해제(release)

- 파일(file)의 개방(open)/폐쇄(close)

- 기억장치(memory)의 할당(allocate)/해제(free)

▶ 운영체제는 각 자원의 상태를 관리하기 위해 시스템 테이블을 사용함

- 자원의 할당 및 해제, 그리고 사용중인 프로세스 등을 기록

- 할당된 자원을 요청한 프로세스는 그 자원의 대기 큐에 입력됨

▶ 교착 상태: 임의의 프로세스 집합에 있는 각 프로세스가 다른 프로세스에 의해 발생될 사건(event)을 기다리고 있는 상태                                                          “자원의 해제”

(ex1) 프로세스  P1             P2             P3

           점유↑   ↘요청    ↑     ↘      ↑      ↘

        테이프 구동기1  테이프 구동기2  테이프 구동기3  (테이프 구동기 1)

(ex2) 프로세스  Pi             Pj

           점유↑   ↘요청↙   ↑점유

         테이프 구동기      프린터

7.2 교착 상태의 특징(Deadlock Characterization)

7.2.1 필요 조건(Necessary Conditions)

▶ 교착 상태는 다음의 네 가지 조건이 동시에 만족될 때 발생함: “필요충분조건”

1) 상호 배제(mutual exclusion): 한번에 한 프로세스만이 그 자원을 사용할 수 있고, 다른 프로세스는 그 자원이 해제될 때까지 기다려야 함

2) 점유와 대기(hold and wait): 적어도 하나의 자원을 점유하고, 다른 프로세스에 의해 점유되어 있는 자원을 기다리고 있어야 함

3) 비선점(no preemption): 자원을 선점하지 못함. 즉, 자원을 강제로 빼앗지 못하고 해제될 때까지 기다려야 함

4) 순환 대기(circular wait): 대기 프로세스의 집합 에서, 각 가 이 보유하고 있는 자원을 기다리고 있어야 함(단, 은 임)

7.2.2 자원 할당 그래프(Resource-Allocation Graph)

▶ 시스템 자원 할당 그래프: 교착 상태를 관리하기 위한 유향 그래프

- : 정점(vertex)의 집합

① 프로세스 집합 : ○

② 자원 형태 집합 : □ → 각 자원은 점으로 표시

- : 에지(edge)의 집합, , 

(요청 에지)  

(할당 에지)  

① 요청: 요청 에지를 생성

② 사용: 요청 에지를 할당 에지로 변환

③ 해제: 할당 에지를 삭제

[그림 7.1] 자원 할당 그래프 → p.226-227의 내용

▶ 자원 할당 그래프에 의한 교착 상태 판별

- 자원 할당 그래프가 사이클을 가지고 있지 않으면, 교착 상태가 아님

- 자원 할당 그래프가 사이클을 가지고 있으면, 교착 상태일 수도 아닐 수도 있음

1) 각 자원 유형의 수가 하나인 경우: 필요 충분 조건

2) 각 자원 유형이 여러 개인 경우: 필요 조건 ○, 충분 조건 ×

▶ (예)

  ① [그림 7.2] 교착 상태의 자원 할당 그래프

    → 사이클 2개 존재, 교착 상태임

      - 

      - 

  ② [그림 7.3] 사이클이 있으나 교착 상태가 아닌 자원 할당 그래프

    → 사이클 1개 존재, 교착 상태 아님

      - 에 할당된 가 해제되어 에 할당될 수 있기 때문

7.3 교착 상태 처리 방법(Methods for Handling Deadlocks)

▶ 세 가지 방법

1) 시스템이 교착 상태가 되지 않도록 보장하기 위한 프로토콜을 사용하는 방법

- 교착 상태 예방(prevention) 기법: 교착 상태의 필요 조건 중 적어도 하나가 성립하지 않도록 자원 요청에 대해 제한을 두는 방법(7.4절)

- 교착 상태 회피(avoidance) 기법: 시스템은 현재 요청이 만족되는지 혹은 지연해야 하는지를 결정하기 위해 현재 사용 가능한 자원들과 각 프로세스에 할당된 자원들, 그리고 미래에 각 프로세스의 요청과 해제를 고려하는 방법(7.5절)

2) 시스템이 교착 상태가 될 수 있도록 허용하되 회복시키는 방법

- 교착 상태 탐지 알고리즘(7.6절) & 교착 상태로부터의 회복 알고리즘(7.7절)

3) 교착 상태 문제를 무시하고 교착 상태가 발생하지 않는다고 가정하는 방법

- 성능 저하 → 시스템 중단 → 인위적인 재시작

- 교착 상태는 일년에 한번 정도 발생하므로, 이 방법이 비용이 적게 듦

→ UNIX를 비롯한 대부분의 운영체제에서 채택

7.4 교착 상태 예방(Deadlock Prevention)

▶ 앞의 네 가지 필요 조건 중 적어도 하나만 일어나지 않도록 하면 교착 상태가 예방됨

7.4.1 상호 배제(Mutual Exclusion)

▶ 개념: 자원이 공유 가능하면 배타적인 접근을 요구하지 않으므로 교착 상태가 발생하지 않음

- 공유할 수 없는 자원: ex) 프린터

- 공유할 수 있는 자원: ex) 판독 전용 파일(read-only file)

▶ 프로토콜: 불가

→ 근본적으로 공유가 불가능한 자원이 있기 때문에 상호 배제 조건을 부정하여 교착 상태를 예방할 수 없음

7.4.2 점유와 대기(Hold and Wait)

▶ 개념: 프로세스가 자원을 요청할 때는 언제나 다른 어느 자원도 점유하지 않도록 보장하면 교착상태가 발생하지 않음

▶ 프로토콜

① 각 프로세스가 수행 전에 필요한 모든 자원을 요청하여 할당받도록 하는 방법

② 각 프로세스가 자원을 하나도 갖고 있지 않을 때만 자원을 요구하도록 하는 방법

                             (입력)         (출력)

▶ (예) 프로세스: 테이프 구동기 → 디스크 파일 → 프린터

- ①의 경우: 세 가지 자원이 두 프로세스의 시작 시에 요청되고, 종료 시에 해제됨

- ②의 경우: 단계별로 요청 및 해제함

1) 테이프 구동기와 디스크 파일에 대해, 요청 → 수행(복사) → 해제

2) 디스크 파일과 프린터에 대해, 요청 → 수행(인쇄) → 해제

▶ 이러한 프로토콜들이 갖는 단점

- 자원이 할당되어 오랫동안 사용되지 않으므로 자원의 이용도가 낮음: ①의 경우

- 기아 상태의 발생 가능성이 높음: ②의 경우

7.4.3 비선점(No Preemption)

▶ 개념: 선점(preemption)이 허용되면 교착상태가 발생하지 않음

▶ 프로토콜

① 자원을 보유하고 있는 어떤 프로세스가 현재 할당받을 수 없는 자원을 요청하면, 보유하고 있는 모든 자원이 해제되도록 하는 방법

② 다른 자원을 요청하여 대기중인 프로세스에 의해 점유중인 자원을 선점할 수 있도록 하는 방법

7.4.4 순환 대기(Circular Wait)

▶ 개념: 모든 자원에 일련의 순서를 부여하여 오름차순으로 자원을 요청하게 하면 교착상태가 발생하지 않음

- 자원 형태의 집합 

- 순서 부여 함수 

  ex)

▶ 프로토콜

① 각 프로세스는 오름차순으로만 자원을 요청할 수 있게 하는 방법: 즉, 프로세스가 를 요청한 후에는 를 만족하는 만을 요청할 수 있음

② 각 프로세스가 자원 형태 를 요청하는 경우, 를 만족하는 모든 자원 를 해제하도록 하는 방법

▶ 순환 대기의 방지에 대한 증명

프로세스 집합 이 위의 조건을 만족하지만 순환 대기가 발생한다고 가정하면, 

     

↑↘ ↑↘     ↑↘

      

을 만족해야 하므로,  즉, 이 된다. 이는 성립하지 않으므로, 위 조건하에서는 환형 대기가 발생하지 않는다.

7.5 교착 상태 회피(Deadlock Avoidance)

▶ 교착 상태 예방 방법의 문제점: 장치 이용률 저하, 시스템 처리율 감소

▶ 교착 상태 회피 방법: 자원이 어떻게 요구되는가에 대한 추가적인 정보 필요

  즉, 각 프로세스의 요구를 만족시킬지 혹은 교착 상태를 회피하기 위해 기다리게 할지를 판단하기 위해서는, 현재 사용 가능한 자원, 각 프로세스에 할당된 자원, 그리고 각 프로세스의 미래의 요구와 해제에 대해 알고 있어야 함

  → 필요한 정보의 양과 종류에 따라 여러 가지 알고리즘 존재함

▶ (예) 각 프로세스가 필요로 하는 각 종류의 자원의 최대 수를 정의하는 방법

→ 순환 대기 조건이 발생하지 않도록 자원 할당 상태를 검사함

  ex) 사용 가능한 자원의 수, 할당된 자원의 수, 프로세스의 최대 요구수

7.5.1 안정 상태(Safe State)

▶ 안정 상태: 시스템이 각 프로세스에 자원을 최대 수까지 어떤 순서로 할당할 수 있어서 교착 상태를 피할 수 있는 상태

→ “안정 순서”가 존재하는 시스템 상태

▶ 안정 순서: 프로세스 순서 이 안정 순서이려면, 각 가 최대로 요청하는 자원이 사용 가능한 자원과 가 점유하고 있는 자원으로 만족될 수 있는 경우가 존재해야 함

▶ [그림 7.4] 안정, 불안정, 교착 상태들의 공간

→ 불안정 상태는 교착 상태는 아니지만 교착 상태가 될 수 있는 상태임

▶ (예) 12개의 자기 테이프 장치와 3개의 프로세스 , , 를 갖는 시스템

최대 수요

현재 수요()

(여분: 3개)

다음 수요()

(여분: 2개)

10

5 점유

5 점유

4

2 점유

2 점유

9

2 점유

2+1=3 점유

(가 1개 더 요구)

- :  → ‘안정 상태’

- :  수행 후 여분 수 = 4, 나 는 최대 수요를 만족시키지 못함 → ‘불안정 상태’

  (만일 의 요청을 허용하지 않고 다른 프로세스가 처리를 종료하고 자원을 반납할 때까지 기다리게 한다면 교착 상태를 피할 수 있음)

→ 결론적으로, 프로세스가 현재 사용 가능한 자원을 요구하더라도 시스템이 안정 상태로 유지될 수 있는 경우에만 받아들이게 함으로써 교착 상태를 회피할 수 있음

7.5.2 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)

▶ 특성: 각 자원 형태마다 자원이 한 개씩인 경우에 적용 가능한 방법

▶ 자원 할당 그래프의 변형

- 요청 에지(request edge):  실선 

- 할당 에지(assignment edge):  실선 

- 요청 가능 에지(claim edge):  점선 → 향후 가 를 요청할 수 있음을 의미

▶ 개념: 프로세스 가 자원 를 요청할 때, 요청 에지 를 할당 에지 로 변환해도 자원 할당 그래프에 순환을 야기하지 않으면 요청을 허용할 수 있음

→ 순환 검사(cycle detection) 알고리즘 사용

- 有: 불안정 상태 → 기다리게 함

- 無: 안정 상태 → 요청 승인

▶ (예) 

[그림 7.5] 교착 상태 회피를 위한 자원 할당 그래프

[그림 7.6] 자원 할당 그래프에서의 불안정 상태

      

 사이클 없음          사이클 존재(할당 취소:의 요청을 기다리게 함)

7.5.3 은행가 알고리즘(Banker's Algorithm)

▶ 특성: 같은 종류의 자원이 여러 개인 일반적인 경우에도 적용 가능

▶ 은행가 알고리즘: 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래

- 새로운 프로세스의 생성시: 

→ 각 자원 종류에 대해 총 자원 수를 넘지 않는 한도 내에서 최대 수요를 정의

- 기존 프로세스의 추가적인 자원 요구시: 

→ 이 할당으로 시스템의 상태가 안정 상태로 유지되는지를 결정

1) Yes: 할당됨

2) No: 기다림

▶ 자료 구조: 자원 할당 시스템의 상태 묘사

- : 프로세스의 수

- : 자원 종류의 수

① : 사용 가능한 각 자원 종류의 자원 수를 표시하는 길이가 인 벡터

→ : 자원 종류 의 개가 사용 가능하다는 의미

② : 각 프로세스의 최대 요구를 정의하는  행렬

→ : 프로세스 가 자원 종류 를 최대로 개 요청할 수 있음을 의미

③ : 현재 각 프로세스에 할당된 각 자원의 수를 정의하는  행렬

→ : 프로세스 가 현재 자원 종류 를 개 할당받고 있음을 의미

④ : 각 프로세스의 남아 있는 요구를 나타내는  행렬

→ : 프로세스 가 자원 종류 를 개 필요로 할 수 있음을 의미

  

▶ 표기법 정의

- , 가 길이 인 벡터일 때,

1) 모든 에 대해 이면, 이다.

  ex) , 이면, 

2) 이고 이면, 이다.

- 프로세스 를 의미하는 행 벡터:  또는 

7.5.3.1 안정 알고리즘(Safety Algorithm)

▶ 개념: 시스템의 상태가 안정 상태인지 불안정 상태인지를 확인하는 알고리즘

▶ 알고리즘

① 길이가 각각 , 인 벡터 , 의 초기화

② 다음과 같은 를 찾음

→ 존재? 

- Yes: ③으로 감

- No: ④로 감

③ 프로세스 Pi에 할당되었던 자원의 해제

④ 모든 에 대해 ?

- Yes: 안정 상태

- No: 불안정 상태

7.5.3.2 자원 요청 알고리즘(Resource Request Algorithm)

▶ 정의:  - 프로세스 의 요청 벡터(길이 m)

  → : 프로세스 가 자원 종류 를 개 요청함을 의미

▶ 알고리즘

① 이면 ②로 가고, 아니면 오류 발생(최대 자원 수보다 더 많이 요구하므로)

② 이면 ③으로 가고, 아니면 기다림( 자원이 사용가능하지 않으므로)

③ 요청된 자원이 할당된 것으로 가정하고 다음과 같이 상태를 수정한다.

→ 할당 상태 체크: 안정 알고리즘

1) 안정: 할당을 인정

2) 불안정: 이전 상태로 복귀하고 대기

7.5.3.3 예제(An Illustrative Example)

▶ 구성

- 5개의 프로세스 

- 3가지의 자원 형태 

▶ 시간에서의 시스템 상태

Allocation

A  B  C

Max

A  B  C

Need

(Max-Allocation)

A  B  C

Available

A  B  C

P0

P1

P2

P3

P4

0  1  0

2  0  0

3  0  2

2  1  1

0  0  2

7  5  3

3  2  2

9  0  2

2  2  2

4  3  3

7  4  3

1  2  2

6  0  0

0  1  1

4  3  1

3  3  2

→ 안정 상태: 이 안정 기준을 만족함

  (풀이)  

▶ 다음의 각 요청에 대해, 판별

① 

Allocation

A  B  C

Max

A  B  C

Need

(Max-Allocation)

A  B  C

Available

A  B  C

P0

P1

P2

P3

P4

0  1  0

3  0  2

3  0  2

2  1  1

0  0  2

7  5  3

3  2  2

9  0  2

2  2  2

4  3  3

7  4  3

0  2  0

6  0  0

0  1  1

4  3  1

2  3  0

→ 안정 상태: 이 안정 기준을 만족함

  (풀이)  

② : 자원 부족, ③ : 불안정 상태

7.6 교착 상태 탐지(Deadlock Detection)

▶ 교착 상태 탐지 및 회복: 탐지 알고리즘(7.6절) → 회복 알고리즘(7.7절)

7.6.1 각 자원 형태마다 자원이 한 개씩 있는 경우(Single Instance of Each Resource Type)

▶ 대기 그래프(wait-for graph): 자원 할당 그래프(resource-allocation graph)의 변형

“자원 할당 그래프에서 자원 종류의 노드를 제거하고 프로세스간의 에지로 나타낸 그래프”

 - 가 보유중인 자원을 가 기다린다는 의미

→ 대기 그래프에 사이클이 존재하면 교착 상태임

▶ (예) [그림 7.7] 자원 할당 그래프와 대응하는 대기 그래프

7.6.2 자원 형태마다 여러 개의 자원이 있는 경우(Several Instances of a Resource Type)

▶ 자료구조: 은행가 알고리즘에서 사용한 것과 동일

① :  벡터

② :  행렬

③ :  행렬

▶ 탐지 알고리즘(detection algorithm): Shoshani & Coffman

① 길이가 각각 , 인 벡터와 의 선언 및 초기화

- 

- if  then 

otherwise  (단, ) ← <다름>

② 다음 조건을 만족하는  탐색

1) 

2)  ← <다름>

→ 존재?

  - Yes: go to ③

  - No: go to ④

③ 

 

  go to ②

④ 인 임의의   존재?

- Yes: 교착 상태 ← <다름>

- No: 미교착 상태

▶ (예)

- 5개의 프로세스 , 

- 3개의 자원 유형 

시스템 상태 1

  

    

    

    

P0

P1

P2

P3

P4

0   1   0

2   0   0

3   0   3

2   1   1

0   0   2

0   0   0

2   0   2

0   0   0

1   0   0

0   0   2

0   0   0

  (풀이)

    → 모든 에 대해, 

       ∴ 미교착 상태  - 미교착 순서

시스템 상태 2

  

    

    

    

0   1   0

2   0   0

3   0   3

2   1   1

0   0   2

0   0   0

2   0   2

0   0   1

1   0   0

0   0   2

0   0   0

  (풀이)   

    → 에 대해,  

       ∴ 교착 상태:  - 교착 상태의 프로세스 집합

7.6.3 탐지 알고리즘 사용법(Detection-Algorithm Usage)

▶ 얼마나 자주 탐지 알고리즘을 호출할 것인가?

- 교착 상태의 빈도에 비례

- 교착 상태에 영향받는 프로세스의 수에 비례

→ 교착 상태인 프로세스에 할당된 자원은 교착 상태가 없어질 때까지 사용되지 않게 되고, 더욱이 그래프에서 사이클의 수는 점점 더 늘어날 수 있음

▶ 탐지 알고리즘의 호출 시점 예

- 즉시 받아들일 수 없는 할당 요구가 있을 때마다 수행: 연산 시간 부담이 큼

- 일정 시간(1시간)마다 수행

- CPU의 효율이 일정 비율(40%) 이하로 떨어질 때마다 수행

7.7 교착 상태로부터의 회복(Recovery from Deadlock)

▶ 접근 방법

- 수동 처리: 운영원에게 알림

- 자동 처리: 1) 순환 대기를 탈피하기 위해 하나 이상의 프로세스를 중지시키는 방법

2) 교착 상태의 프로세스로부터 자원을 선점하는 방법

7.7.1 프로세스 중지(Process Termination)

▶ 교착 상태의 프로세스를 종료시키고 자원을 회수하는 방법

1) 전체 종료: 교착 상태의 모든 프로세스를 중지시키는 방법

  → 이미 계산된 프로세스의 각종 결과를 재 연산해야 함 - (비용 大)

2) 부분 종료: 교착 상태 사이클이 제거될 때까지 프로세스를 하나씩 중지시키는 방법

  → 프로세스가 중지될 때마다 교착 상태 탐지 알고리즘을 수행해야 함 - (비용 大)

▶ 프로세스를 중지시키는 것이 단순하지 않음

- 파일 수정 중 → 파일의 부정확한 상태를 초래

- 프린터에 자료 출력 중 → 다음 출력 전에 프린터의 상태 조정 필요

▶ 부분 종료의 경우, 중지시킬 프로세스의 선택 방법 필요

→ 최소 비용 원칙: 기본적으로, 원상태로 되돌리는데 드는 비용이 최소인 프로세스를 선택

① 프로세스의 우선 순위

② 프로세스의 현재까지의 수행 시간 및 잔여 수행 시간

③ 프로세스가 사용할 자원의 종류 및 수량

④ 프로세스의 작업 완료를 위해 추가로 소요되는 자원의 양

⑤ 종료하는데 필요한 프로세스의 수

⑥ 프로세스가 대화식인지 일괄식인지 여부

7.7.2 자원 선점(Resource Preemption)

▶ 교착 상태 사이클이 없어질 때까지, 자원을 선점하여 다른 프로세스에게 제공하는 방법

1) 희생자(victim) 선택: 원상태로 되돌리는데 드는 비용을 적게 하도록 프로세스나 자원의 선점 순서를 결정

2) 복귀(rollback): 선점당하는 프로세스가 정상 상태로 복귀하는 방법

① 절대 복귀(total rollback): 프로세스를 중지시키고 다시 수행하도록 하는 방법

  → 비효율적

② 제한적인 복귀: 교착 상태 해결에 필요한 만큼만 복귀

  → 효율적, 그러나 현재 진행중인 모든 프로세스의 상태 정보 유지가 필요

3) 기아 상태(starvation): 동일한 프로세스가 계속 선점당하는 경우

→ 복귀의 횟수를 비용 요소에 포함시킴으로써 해결 가능

7.8 교착 상태 해결을 위한 복합 방식(Combined Approach to Deadlock Handling)

▶ 자원에 계층적인 순서를 부여하고 각 부류에 별도의 교착 상태 해결 방법을 적용하는 방법

                                            (예방, 회피, 탐지 및 회복 등)

(네 가지 부류)

① 내부 자원(internal resources): 시스템에 의해 사용되는 자원 - ex) 프로세스 제어 블록

→ 자원의 순서화에 의한 예방 방법 사용: 계류된 요청의 실행 시간 선택이 불필요하기 때문

② 중앙 기억장치(central memory): 사용자 작업에 의해 사용되는 공간 - ex) RAM

→ 선점을 통한 예방 방법 사용: 작업이 교체 가능해서 기억 장치가 선점될 수 있기 때문

③ 작업 자원(job resources): 할당할 수 있는 장치와 파일 - ex) 테이프 드라이버

→ 회피 방법 사용: 작업 요청 정보를 제어 카드를 통해 미리 예측할 수 있기 때문

④ 교체가능 공간(swappable space): 사용자 작업을 저장할 수 있는 공간

→ 선 할당(preallocation) 방법 사용: 기억 장치의 최대 수요를 미리 알 수 있기 때문