교착 상태 (Deadlock)

교착 상태 (Deadlock)

프로세스는 실행을 위해 CPU, 메모리, 파일, 프린터 등 여러 가지의 자원을 필요로 한다.

만약 프로세스가 어떤 자원은 갖고 있지만 다른 자원을 갖지 못했다면 (다른 프로세스가 사용 중) 이 자원을 확보할 때 까지 기다려야한다. 다른 프로세스 역시 또 다른 자원이 필요해서 기다리고 있다면 또 이로 인해 다른 프로세스들도 기다려야하는 등의 악순환이 반복되고 이를 교착 상태 (Deadlock)이라고 한다.

필요 조건 (Necessary Conditions)

교착 상태가 발생하려면 다음과 같은 필요 조건이 충족되어야한다.

• 상호 배타 (Mutual Exclusion) : 하나의 프로세스가 자원을 사용하고 있다면, 다른 프로세스는 해당 자원을 사용할 수 없다.
• 보유 및 대기 (Hold and Wait) : 하나의 프로세스가 자원을 갖고 있지만 모종의 이유로 대기하고 있다.
• 비선점 (No Preemption) : 하나의 프로세스가 자원을 사용하는 중에는 다른 프로세스가 해당 자원을 뺏어갈 수 없다.
• 환형대기 (Circular Wait) : 프로세스가 요구하는 자원의 방향이 원형을 이룬다. (식사하는 철학자 문제와 비슷한 케이스)

다만 이는 필요 조건이므로 이 네 가지 조건이 성립하면 무조건 교착 상태가 발생하는 것은 아니다. 교착 상태가 발생할 수 있는 것이다.

반대로 교착 상태가 발생해서 살펴보면 무조건 이 네 가지 조건이 성립된다.

교착 상태는 드물게 발생하는 현상이지만 한 번 발생하면 매우 치명적이고 해결하기도 힘들다. 따라서 사전에 방지하는 것이 매우 중요하다.

자원 (Resources)

동일 자원

동일한 형식 (Type)의 자원이 여러 개가 있을 수 있다. (Instance)
예를 들어 동일한 CPU가 2개 있거나 동일한 프린터가 3개 있거나 등등이 있다.

자원의 사용

프로세스가 자원을 사용하기 위해서는 요청 (Request) -> 사용 (Use) -> 반납 (Release)의 과정을 거쳐야한다.

자원 할당도 (Resource Allocation Graph)

어떤 자원이 어떤 프로세스에게 할당되어있는지를 나타내는 다이어그램이다.
또한 어떤 프로세스가 어떤 자원을 할당 받으려고 기다리고 있는지도 표시할 수 있다.

• 자원 (Resource) : 사각형
• 자원의 인스턴스 (Instance) : 점
• 프로세스 (Process) : 원
• 할당 (Allocation) : 화살표

로 표시한다.

예시

• 모든 프로세스와 자원은 상호 배제 (Mutual Exclusion)와 비선점 (No Preemptiion)이 기본적으로 적용되어있다.
• 프로세스 1은 자원 2를 할당받았고 자원 1을 할당받기 위해 대기중이다. (Hold and Wait)
• 프로세스 2는 자원 1, 2를 할당받았고 자원 3을 할당받기 위해 대기중이다. (Hold and Wait)
• 프로세스 3은 자원 3을 할당받았다.

• 자원 2는 동일한 인스턴스를 2개 갖고 있다.
• 자원 4는 동일한 인스턴스를 3개 갖고 있으며 누구에게도 할당되어있지 않다.

Circular Wait (환형 대기)

환형 대기를 자원 할당도로 나타내면 다음과 같다.

이를 식사하는 철학자 문제에 빗대어 해석해보면 다음과 같다.

• 모든 철학자 (P0 ~ P4)는 왼쪽 젓가락을 하나씩 들고 있다.
• 모든 철학자는 오른쪽 젓가락을 들기 위해 대기하고 있다.

이는 젓가락을 드는 순서를 일부 변경하여 다음과 같이 해결할 수 있다.

• 짝수 철학자는 왼쪽 젓가락을 먼저 들고 그 다음 오른쪽 젓가락을 든다.
• 홀수 철학자는 오른쪽 젓가락을 먼저 들고 그 다음 왼쪽 젓가락을 든다.

이렇게 바꾸면 모든 철학자가 돌아가며 젓가락 한 쌍을 사용할 수 있다.

이를 코드로 나타내면 다음과 같다.

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) { }
}

교착상태 처리

잠시 운영체제의 구성요소를 살펴보고 가자.

운영체제는 다음과 같은 여러 부서로 구성되어있다.

이중 가장 중요한 부서는 Process Management 부서이다.

Process Management 부서는 CPU Scheduler, Process Synchronization 등의 세부 부서로 구성되어있다.

교착상태 처리는 이중 Process Synchronization 부서에서 담당한다.

교착상태는 방지, 회피, 검출 및 복구, 무시하는 방법으로 처리할 수 있다.

교착상태 방지 (Deadlock Prevention)

교착상태 방지는 교착상태의 4가지 필요조건 중 하나 이상을 불만족시킴으로써 방지하는 방법이다.

상호배타 (Mutual Exclusion)

자원을 서로 다른 프로세스/쓰레드가 공유할 수 있도록 설정한다. 하지만 이는 경우에 따라 원천적으로 불가능할 수 있다.

보유 및 대기 (Hold and Wait)

프로세스/쓰레드가 자원을 갖고 있으면서 다른 자원을 기다리지 않도록 설정한다.

예를 들어, 모든 자원을 사용할 수 있을 경우에만 자원을 요청하도록 설정하거나, 일부 자원만 사용할 수 있는 상태라면 보유하고 있는 모든 자원을 반납하도록 설정한다.

하지만 이는 자원의 활용률을 저하하고 경우에 따라 기아 (Starvation) 현상이 발생할 수 있다.

비선점 (No Preemption)

자원을 선점 가능하도록 설정한다. 하지만 상호 배타와 마찬가지로 원천적으로 불가능할 수 있다. 자원 중에는 강제로 선점할 수 없는 자원들이 많기 때문이다. 예를 들어 프린터는 들어온 순서대로 출력하는데, 이미 문서를 출력 중인 프린터를 CPU가 강제로 다른 문서를 출력하게 만들 수는 없는 노릇이다.

환형대기 (Circular Wait)

모든 자원에 일련 번호를 부여하고 이를 기준으로 오름 차순으로 자원을 요청하는 등의 방법으로 환형대기를 해결할 수 있다. 하지만 이런 방법 역시 자원의 활용도를 저하시킨다는 문제가 있다.

이 중 보유 및 대기 (Hold and Wait)와 환형대기 (Circular Wait)을 방지하는 방법이 가장 현실적인 방법이다. 물론 자원의 활용도를 저하시킨다는 단점은 있다. 따라서 이렇게 교착상태를 사전에 방지하는 방법은 군사, 우주, 의료와 같은 크리티컬한 분야에서 사용하는 것이 좋다.

교착상태 회피 (Deadlock Avoidance)

교착상태 방지는 교착상태가 일어나지 않도록 사전에 방지하는 방법이고 교착상태 회피는 교착상태가 발생하는 원인을 자원 요쳉에 대한 잘못된 승인이라고 판단해서 접근한다.

따라서 교착상태 회피는 자원의 안전한 할당 (Safe Allocation), 불안전한 할당 (Unsafe Allocation) 2가지 방법으로 접근한다.

12개의 Magnetic Tape과 3개의 Process로 구성되어있는 운영체제가 있다고 가정하고 예시를 들어보자. Max Needs는 프로세스를 끝내기 위해 총 필요한 Magnetic Tape의 개수이다. Current Needs는 프로세스가 한 번 요청할 때 필요한 Magnetic Tape의 개수이다.

3개의 프로세스가 요구하는 Magnetic Tape이 표로 주어진다.

안전한 할당 (Safe Allocation)

Process	Max needs	Current Needs
P0	10	5
P1	4	2
P2	9	2

할당 과정은 다음과 같다.

할당 받는 프로세스	할당되는 자원의 개수	남은 자원 개수	비고
P0	5	7	-
P1	2	5	-
P2	2	3	-
P0	0	3	개수가 모자라서 줄 수 없다.
P1	2	1	-
	0	5	P1 작업 종료. 갖고 있던 모든 자원 반납
P0	5	0	-
	0	10	P0 작업 종료. 갖고 있던 모든 자원 반납
P2	7	3	P2 작업 종료. 모든 프로세스 작업 종료.

이처럼 3개의 프로세스 모두 정상적으로 자원을 할당받아 안전하게 종료되었다. 이를 안전한 할당 (Safe Allocation)이라고 한다.

불안전한 할당 (Unsafe Allocation)

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

할당 과정은 다음과 같다.

할당 받는 프로세스	할당되는 자원의 개수	남은 자원 개수	비고
P0	5	7	-
P1	2	5	-
P2	3	2	-
P0	0	2	개수가 모자라서 줄 수 없다.
P1	2	0	-
	0	4	P1 작업 종료. 갖고 있던 모든 자원 반납
P0	0	4	개수가 모자라서 줄 수 없다.
P2	3	1	-
P0	0	1	개수가 모자라서 줄 수 없다.
P2	0	1	개수가 모자라서 줄 수 없다.

이처럼 Magnetic Tape의 개수가 부족해서 프로세스를 끝낼 수 없고, 프로세스는 계속해서 자원이 들어오기만을 기다리고 있다. 따라서 교착상태 (Deadlock)이 발생한다.

이를 불안전한 할당 (Unsafe Allocation)이라고 한다.

교착상태의 회피는 마치 대출 전문 은행과 유사하므로 이를 Banker's Algorithm이라고도 한다.

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

교착상태의 방지와 회피는 교착상태를 일어나지 않도록 하는 방법이다. 반면 교착상태 검출 및 복구는 교착상태가 일어나는 것을 허용한다. 대신에 교착상태가 일어나면 이를 감지하고 복구하는 방법이다.

따라서 교착상태가 발생했는지 주기적으로 검사를 진행한다.

검출 (Detection)

운영체제 내부에서 주기적으로 교착상태 발생 여부를 검사한다. 이 과정에서 검사에 따른 추가적인 Overhead가 발생한다.

복구 (Recovery)

메모리의 상태를 주기적으로 메모리에 저장해놓고, 교착상태가 발생하면 그 바로 직전의 상태로 되돌린다. 또는 교착상태가 발생하면 일부 프로세스를 강제로 종료하거나, 자원을 강제로 선점하여 일부 프로세스에게 할당하는 방법도 있다.

교착상태 검출 및 복구는 교착상태 자체가 매우 드문 현상이기 때문에 자유롭게 자원을 할당하다가 교착상태가 발생하면, 정상적이었던 이전 상태로 복구하는 방식이다. 하지만 주기적으로 교착상태를 검사하고 메모리를 저장하는 과정에서 Overhead가 발생한다.

교착상태 무시

교착상태는 4가지 필요조건을 모두 만족해도 반드시 일어나지 않는다는 보장이 없다. 또 교착상태는 실제로 매우 드문 현상이다. 따라서 잘 일어나지도 않는 교착상태를 대비하겠다고 이런 저런 일을 하면 Overhead가 심해지므로 그냥 무시하는 방법이다.

만일 교착상태가 발생하면 전체 시스템을 재시동하면서 해결한다. 따라서 가정용 PC 등에 적합하다.