DeadLock

교착 상태는 어떠한 자원을 갖고 있는 상황에서 문제가 발생한다. 자동차 교차로를 생각해보자. A자동차도 신호를 받았고, B 자동차도 신호를 받았다. 그래서 두 자동차가 움직이는 것에 논리적 오류가 없지만, 두 자동차가 갈 수 없는 상황이 발생한다. 바로 출근 시간 길 막힘이다. 길이 막혀 아무런 동작도 수행할 수 없다. 이런 상황을 교착상태라 한다.

프로세스는 실행을 위해 CPU, 메모리, 파일 등 여러 하드웨어 자원이 필요하다. 이를 운영체제에서 프로세스가 요구하는 자원을 적절히 분배해준다. 예를 들어, 한 프로세스가 A 자원을 가지고 있는 상태에서 B 자원을 요구하고 있다. 하지만 B 자원은 다른 프로세스 역시 요구하고 있는 자원인데, 이러한 상황에서 자원을 분배하는 순서가 잘못되면 교착상태에 빠지게 된다.

1. 교착상태 필요 조건(Necessary Conditions)

교착상태가 일어나기 위한 필요 조건이 네 가지가 존재한다. 이는 필요 조건이므로, 네 가지가 모두 해당된다고 해서 반드시 교착상태가 일어나는 것은 아니다. 단지 일어날 가능성이 발생한다.

하지만 네가지 조건 중 하나라도 해당되지 않으면 교착 상태는 일어나지 않는다. 즉, 4가지 조건에 모두 해당되면 Deadlock의 가능성이 있으나, 그렇지 않다면 Deadlock은 일어나지 않는다.

1. Mutual exclusion (상호배타)
   • 한 프로세스가 자원을 사용하고 있다면, 다른 프로세스는 이 자원을 사용할 수 없다.
     • 젓가락은 한 철학자가 사용하고 있으면 이 젓가락은 사용할 수 없으므로 상호배타적이다.
2. No Preemption (비선점)
   • 한 프로세스가 자원을 수행하는 중에는 다른 프로세스가 중간에 끼어들 수 없다.
     • 한 철학자가 젓가락을 집은 상태에서 다른 철학자가 이 젓가락을 뺏을 수 없다.
3. Hold and wait (보유 및 대기)
   • 한 프로세스가 자원을 가지고 있는 상태에서 대기한다.
     • 철학자는 왼쪽 젓가락을 가지고 있는 상태에서 오른쪽 젓가락을 집기 위해 대기한다.
4. Circular wait (환형대기)
   • 프로세스가 요구하는 자원의 방향이 원형을 이룬다.
     • 모든 철학자는 왼쪽 젓가락부터 집을 수 있다.

교착상태는 위 네 가지 조건을 모두 만족하더라도 매우 드물게 일어나는 현상이지만, 한 번 교착상태에 빠지면 프로세스가 무한 루프에 빠져 수행하지 못하고 해당 프로세스가 가지고 있는 자원은 아무도 사용하지 못한다. 이는 전체 컴퓨터 환경에 매우 치명적이다. 그리고 교착상태에 의한 오류를 해결하기는 매우 힘들다.

2. 자원(Resources)

교착 상태가 발생하는 가장 큰 원인은 결국 자원의 문제이다. 따라서 이 자원을 어떻게 이용하고 있는 지 파악하는 것이 중요하다.

하드웨어 자원은 여러 개가 존재하고 동일한 **형식(type)**의 자원이 존재할 수 있다. 예를 들어, 같은 CPU가 2개있는 환경이 있다. 이러한 자원 하나하나를 instance라고 한다.

자원은 프로세스가 직접적으로 사용할 수 없고, 운영체제에 **요청(request)**하면 운영체제가 제공해준다. 그 후 프로세스는 이 자원을 **사용(use)**하고 모든 사용이 끝나면 이를 **반납(release)**한다.

요청(request) -> 사용(use) -> 반납(release)

2.1 자원 할당도(Resource Allocation Graph)

자원 할당도는 어떤 자원이 어떤 프로세스에 할당되었는지 또는 어느 프로세스가 어느 자원을 할당 받으려고 기다리는지를 그림으로 나타낸 것이다.

|용어|모양| |::----|::----| |Resource(자원)|사각형| |Instance(인스턴스)|점| |Process(프로세스)|원| |할당|화살표|

R1은 P1에 할당되어 있는 상태이고, P2는 R1을 요청하고 있는 상태이다.

자원 할당도를 사용하는 이유는 교착상태의 필요조건을 한 눈에 볼 수 있기 때문이다. 자원 할당도를 분석할 때 mutual exclusion(한번에 하나)과 no-preemption(강제로 못 뺏는다.)은 기본으로 적용된다.

Hold and wait는 화살표를 통해 한 프로세스가 인스턴스를 할당받았고 다른 자원을 가리키고 있다면, 이 상황은 Hold and wait인 상태이다.

Circular wait 역시 화살표 방향이 원형을 이루고 있다면 이는 환형대기인 상태이다.

이런 그림을 보면 Circular wait 조건을 가지고 있어 교착 상태의 가능성을 가지고 있다.

위 그림은 식사하는 철학자 문제를 자원 할당도로 표현한 것이다. 그림을 보면 한 눈에 Circular wait 조건을 만족한 것을 알 수 있다. 그리고 모든 철학자(프로세스)는 한 젓가락(자원)을 할당(파란색 화살표)받고, 다른 젓가락을 요청(검은색 화살표)하고 있으므로 Hold and wait 조건 역시 만족한다.

4. 교착상태 처리

4.1 교착상태 방지 (Deadlock Prevention)

교착상태 방지는 교착상태 필요조건 네 가지 중 최소 한 가지를 만족시키지 않도록 만드는 것이다.

• 상호배타(Mutual exclusion)
  • 상호배타를 없애기 위해서는 자원을 공유 가능하게 만들어야 한다. 하지만 현실적으로 이러한 방법이 불가능한 경우가 많다.
• 비선점(No preemption)
  • 비선점을 없애러면 반대로 선점이 가능하도록 만들어야 한다. 이 역시 대부분의 자원에게는 불가능한 방법이다. CPU는 강제로 스위칭하는 것이 가능한 경우가 있지만, 대부분의 경우에는 불가능하다. 가령 프린터를 수행하는 중간에 다른 프로세스가 이를 선점하는 것은 불가능하다고 볼 수 있다.
• 보유 및 대기(Hold & Wait)
  • 이 조건을 없애려면 자원을 가지고 있는 상태에서 다른 자원을 기다리지 않도록 만든다. 만약 여러 개의 자원이 필요하다면 필요한 모든 자원을 얻을 수 있는 경우에만 해당 자원을 요청한다. 또는 필요한 자원 중 일부만 가지는 경우 할당받은 자원을 모두 운영체제에 반납한다. 하지만 이와 같은 방법은 자원의 활용률을 저하시키고, starvation 현상이 발생하는 단점이 있다.
  • 왼쪽 젓가락을 가진 상태에서 오른쪽 젓가락을 요청했는데, 이미 할당되어 있다면, 왼쪽 젓가락도 할당해제 한다.
• 환형대기(Circular wait)
  • 이 조건을 없애는 것은 위 세 가지 조건보다는 할 수 있는 확률이 높다. 대표적인 예는 모든 자원에 번호를 부여하여 이 번호에 대한 오름차순으로 자원을 요청하는 것이다. 이 역시 자원의 활용률을 저하시키는 단점이 있다.

네 가지 방법을 살펴본 결과 가장 현실적인 방법은 hold & wait나 circular wait 조건을 없애는 것이다. 하지만 둘 다 자원을 비효율적으로 사용하게 되는 단점을 가지고 있다. 그래서 이와 같이 교착상태 방지 방법은 군사, 우주, 의료와 같은 크리티컬한 곳에서 사용하는 것이 좋다.

철학자 문제에 적용

위 그림은 식사하는 철학자 문제를 자원 할당도로 표현한 것이다. 그림을 보면 한 눈에 Circular wait 조건을 만족한 것을 알 수 있다. 그리고 모든 철학자(프로세스)는 한 젓가락(자원)을 할당(파란색 화살표)받고, 다른 젓가락을 요청(검은색 화살표)하고 있으므로 Hold and wait 조건 역시 만족한다.

Circular wait 조건을 없애기 위해 짝수 번호 철학자는 왼쪽 젓가락, 오른쪽 젓가락 순서로, 홀수 번호 철학자는 반대 순서인 오른쪽 젓가락, 왼쪽 젓가락 순서로 집는다고 하자.

위 그림은 circular wait 조건을 없앤 식사하는 철학자 문제의 자원 할당도이다. 화살표가 원형을 만들지 않는 것을 볼 수 있다.

// Philosopher Thread run function
public void run() {
    try {
        while (true) {
            if (id % 2 == 0) {
                lstick.acquire();
                rstick.acquire();
            }
            else {
                rstick.acquire();
                lstick.acquire();
            }
            eating();
            lstick.release();
            rstick.release();
            thinking();
        }
    }catch (InterruptedException e) { }
}

이전 글에서 있던 철학자가 젓가락을 집는 코드를 수정했다. 위와 같이 코드를 변경하고 실제로 수행하면 무한 반복문이 끝나지않고 정상적으로 계속되는 것을 확인할 수 있다.

4.2 교착상태 회피 (Deadlock Avoidance)

교착상태 회피와 방지의 차이점은 교착상태를 다르게 접근하는 것이다. 교착상태 회피에서는 교착상태를 자원 요청에 대한 잘못된 승인으로 판단한다. OS단에서 요청에 대해 잘 관리를 해주었다면 해결할 수 있다고 생각하는 것이다.

이러한 접근은 은행과 비슷하다. 은행이 투자를 할 때, 안전한 곳과 안전하지 않은 곳을 잘 분리하여 투자해야, 위기 상황에서 부도가 나지 않을 것이다. 마찬가지로, OS에서 deadlock이 나지 않는 방법으로 할당해주는 방법이 교착 상태 회피이다.

따라서, 교착상태 회피에서는 안전한 할당(Safe allocation)과 불안정한 할당(Unsafe allocation) 두 가지로 나뉜다.

안전한 할당

현재 운영체제에는 magnetic tape 자원이 총 12개가 있고, 이를 요청하는 3개의 프로세스가 있다.

process	Max needs	Current needs
P0	10	5
P1	4	2
P2	9	2

• Current needs
  • 한 프로세스가 한 번 요청을 할 때 요구하는 개수
• Max needs
  • 프로세스를 정상적으로 끝내기 위해 필요한 총 개수

운영체제 입장에서 3개의 프로세스가 모두 수행될 때까지 자원을 분배해보자.

• order : 순서
• process : 프로세스 이름
• needs : 프로세스가 필요로 하는 tape의 개수
• possible : 할당이 가능한지 판단하는 변수
• state : 해당 프로세스의 진행 상태
• dealloc : 할당 해제 되었는지 확인하는 변수
• tapeSize : 현재까지 할당되어 사용할 수 있는 tape의 개수
• wait : 할당 받지 못해 대기하는 지 유무

order	process	needs	possible	state	dealloc	tapeSize	wait
1	P0	5	O	5/10	X	12→7	X
2	P1	2	O	2/4	X	7→5	X
3	P2	2	O	2/9	X	5→3	X
4	P0	5	X	5/10	X	3	O
5	P1	2	O	4/4	O	3→1→5	X
6	P0	5	O	10/10	O	5→0→10	X
7	P2	2	O	4/9	O	10→8→12	X
8	P2	2	O	6/9	O	12→10→12	X
9	P2	2	O	8/9	O	12→10→12	X
10	P2	2	O	9/9	O	12→11→12	X

1. P0에게 5개를 할당한다.(5/10) ⇒ 현재 magnetic tape 개수: 7
2. P1에게 2개를 할당한다.(2/4) ⇒ 현재 magnetic tape 개수: 5
3. P2에게 2개를 할당한다.(2/9) ⇒ 현재 magnetic tape 개수: 3
4. 다시 P0가 5개를 요구하지만 현재 magnetic tape 개수는 3개이므로 할당해줄 수 없다.
5. P1에게 2개를 할당한다.(4/4) ⇒ 현재 magnetic tape 개수: 1
   • P1은 필요한 4개의 magnetic tape을 받았으므로, 정상적으로 프로세스를 종료하고 사용한 자원을 반납한다. ⇒ 현재 magnetic tape 개수: 5
6. 대기하고 있던 P0에게 5개를 할당한다.(10/10) ⇒ 현재 magnetic tape 개수: 0
   • P0 역시 필요한 자원을 모두 할당받았으므로, 종료 후 자원을 반납한다. ⇒ 현재 magnetic tape 개수: 10
7. P2는 현재 필요한 magnetic tape 개수가 7개이고, 현재 남아있는 magnetic tape 개수 10개이므로 정상적으로 수행가능하다. (7~10)

이 예제에서는 3개의 프로세스가 모두 정상적으로 자원을 할당받고 종료할 수 있었다. 이를 안전한 할당이라 한다. 다음 예제를 보자.

불안전한 할당

process	Max needs	Current needs
P0	10	5
P1	4	2
P2	9	3

이 예제 역시 운영체제가 보유하고 있는 총 magnetic tape 개수는 12개이고, 3개의 프로세스가 존재한다. 자원을 분배해보자.

order	process	needs	possible	state	dealloc	tapeSize	wait
1	P0	5	O	5/10	X	12→7	X
2	P1	2	O	2/4	X	7→5	X
3	P2	3	O	3/9	X	5→2	X
4	P0	5	X	5/10	X	2	O
5	P1	2	O	4/4	O	2→0→4	X
6	P0	5	X	5/10	X	4	O
7	P2	3	O	6/9	X	4→1	X
8	P0	5	X	5/10	X	1	O
9	P2	3	X	6/9	X	1	O
10	P0	5	X	5/10	X	1	O
11	P2	3	X	6/9	X	1	O
$⋮$

1. P0에게 5개를 할당한다.(5/10) ⇒ 현재 magnetic tape 개수: 7
2. P1에게 2개를 할당한다.(2/4) ⇒ 현재 magnetic tape 개수: 5
3. P2에게 3개를 할당한다.(3/9) ⇒ 현재 magnetic tape 개수: 2
4. 다시 P0가 5개를 요구하지만 현재 magnetic tape 개수는 2개이므로 할당해줄 수 없다.
5. P1에게 2개를 할당한다.(4/4) ⇒ 현재 magnetic tape 개수: 0
   • P1은 필요한 자원을 모두 할당받았으므로, 정상적으로 프로세스를 종료하고 사용한 자원을 반납한다. ⇒ 현재 magnetic tape 개수: 4
6. 대기하고 있던 P0는 아직 할당받으르 수 없다.
7. P2에게 3개를 할당한다.(6/9) ⇒ 현재 magnetic tape 개수: 1
8. 현재 남아있는 magnetic tape 개수는 1개이고, P0가 요구하는 개수는 5개, P2는 3개이므로 두 프로세스 모두 할당받을 수 없다. (8~)

이 예제에서 남은 magnetic tape 개수가 요구하는 개수보다 적으므로 자원을 할당해줄 수 없다. 그러므로 P0, P2 프로세스는 자원을 하염없이 기다리게 된다. 이를 불안전한 할당이라 하고, 그 결과 교착상태에 빠지게 된다.

교착상태 회피는 마치 대출전문 은행과 유사하게 동작하므로, 해결 방법을 Banker’s Algorithm이라 한다. 돈이 있어야 값지

4.3 교착상태 검출 및 복구 (Deadlock Detection & Recovery)

교착상태 검출 및 복구는 교착상태 자체가 매우 드문 현상이므로 자유롭게 자원을 분배하다가 교착상태가 발생하면 이를 정상적인 상태로 복구하는 것이다.

1번과 2번 방법은 사전에 교착상태를 일어나지 않도록 하는 방법이지만, 교착상태 검출 및 복구 방법은 교착상태가 일어나는 것을 허용한다. 그 대신, 교착상태가 일어났을 때 이를 인지하고 복구를 해야 한다.

교착상태가 일어나는 것을 감지하기 위해 운영체제 내부에서 주기적으로 교착상태가 발생하였는지 검사해야한다. 그 주기의 길이가 짧으면 그 만큼 오버헤드가 크고, 주기가 길면 오버헤드는 줄일 수 있지만 복구 가능성이 낮아진다.

복구하는 방법은 교착상태가 발생하는지 주기적으로 검사하듯이 메모리의 상태를 주기적으로 메모리에 저장해놓고 만약 교착상태가 발생하면 그 이전 상태로 되돌리는 방법이 있다. 그 외에도 일부 프로세스를 강제로 종료하거나 자원을 강제로 선점하여 프로세스에게 할당해주는 방법 등이 있다.

정상적인 상태로 복구한다는 장점이 있지만, 복구를 제대로 하지 못할 수도 있고, 검출을 위해 추가적인 오버헤드가 발생한다는 단점이 있다.

4.3 교착상태 무시

교착상태의 필요조건 네 가지를 모두 만족하더라도 교착상태가 반드시 일어나는 것이 아니라고 했듯이, 교착상태는 매우 드문 상황이다. 그러므로 이를 위해 오버헤드를 감수하는 것이 비효율적인 환경도 존재한다. 그러한 환경은 교착상태에 대한 아무런 조치를 하지 않는 방법도 있다.

Reference

• KOCW 양희재 교수님 - 운영체제
• 양희재 교수님 블로그(시험 기출 문제)
• codemcd 님의 정리글
• 세마포 사진
• Operating System Concepts, 9th Edition - Abraham Silberschatz