[OS] 프로세스 동기화 3

Deadlock(교착상태)

프로세스는 실행을 위해 CPU, 메모리, 파일 등 여러 하드웨어 자원이 필요하다. 이를 운영체제에서 적절히 분배한다. 그러나 다음과 같은 예를 들어보자. 한 프로세스가 A 자원을 점유한 상태에서 B 자원을 요청한다. 그런데 또 다른 프로세스가 B 자원을 요구하고 있다면 자원의 분배 순서가 잘못되고 교착상태에 빠지게 된다.

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

교착상태가 일어나기 위한 필요 조건이 네가지가 존재한다. 이는 필요 조건이므로 반드시 교착상태가 일어나는 것이 아니라 일어날 확률이 생기는 것이다.

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

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

2. 자원(Resources)

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

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

자원 할당도(Resource Allocation Graph)

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

• 자원 : 사각형
• 인스턴스 : 점
• 프로세스 : 원
• 할당 : 화살표

위 그림을 보면 R1은 P1에 할당되어 있고 P2는 R1을 요청하고 있다.

 

 

자원 할당도를 사용하는 이유는 교착상태의 필요조건을 한 눈에 볼 수 있기 때문이다. 자원 할당도를 분석할 때 Mutual Exclusion 과 non Preemption은 기본으로 적용된다.

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

Circular wait은 화살표 방향이 원형을 이루고 있는 상황이다.

위 그림은 배고픈 철학자 문제를 자원 할당도로 표현한 것이다. 그림을 보면 한눈에 선형대기가 있는 것을 확인할 수 있고 모든 철학자가 한 자원을 점유하면서 다른 한 자원을 할당받기 위해 대기하고 있으므로 점유 및 대기 또한 확인할 수 있다.

그렇다면 위에서 살펴본 문제를 해결하기 위해 선형 대기를 없애보자. 선형 대기를 없애기 위해 짝수 번호는 왼쪽, 오른쪽 순서로 홀수 번호는 반대 순서로 잡는다고 해보자.

 

위는 선형대기를 없앤 자원할당도이다. 화살표가 원형을 이루지 않는 것을 볼 수 있다.

 

public void run() {
    try {
        while (true) {
            if (id % 2 == 0) {
                l_stick.acquire();
                r_stick.acquire();
            }
            else {
                r_stick.acquire();
                l_stick.acquire();
            }

            eating();
            l_stick.release();
            r_stick.release();
            thinking();
        }
    } catch (InterruptedException e) {}

 

철학자 스레드의 run() 메소드에서 젓가락을 잡는 코드를 선형대기를 없앤 코드로 변경한 모습이다. 이대로 수행하면 무한반복이 끊이지 않고 정상적으로 계속 실행되는 것을 확인할 수 있다.

3. 교착상태 처리

1. 교착상태 예방(Deadlock Prevention)

교착상태 예방은 위에서 살펴본 교착상태 필요조건 네 가지중 최소 한가지를 만족시키지 않도록 만드는 것이다.

• 상호배제 제거 : 상호 배제를 없애기 위해서는 자원을 공유 가능하도록 해야한다. 하지만 현실적으로 이러한 방법이 불가능한 경우가 많다.
• 점유 및 대기 제거 : 이 조건을 없애기 위해선 자원을 가지고 있는 상태에서 다른 자원을 기다리지 않도록 만들어야 한다. 만약 여러개의 자원이 필요하다면 필요한 모든 자원을 얻을 수 있는 경우에만 해당 자원을 요청하도록 한다. 또는 필요한 자원 중 일부만 가지는 경우 할당받은 자원을 모두 운영체제에 반납한다. 하지만 이와 같은 방법은 자원의 활용률을 저하시키며, 기아 현상이 발생하는 단점이 있다.
• 비선점 제거 : 비선점을 없애려면 반대로 선점이 가능하도록 해야 한다. 이 역시 대부분의 자원에게는 불가능한 방법이다. CPU는 강제로 스위칭하는 것이 가능한 경우가 있지만 대부분은 불가능하다. 가령, 프린터를 수행하는 중간에 다른 프로세스가 이를 선점하는 것은 불가능하다고 볼 수 있다.
• 선형 대기 제거 : 이 조건을 없애는 것이 위 세 조건보다는 가능성이 높다. 대표적으로는 모든 자원에 번호를 부여하여 이 번호에 대한 오름 차순으로 자원을 요청하도록 하는 것이다. 하지만 이 또한 자원의 활용률을 저하시키는 단점이 있다.

네 가지 방법 중 가장 현실적인 방법은 점유 및 대기나 선형대기를 제거하는 것이다. 하지만 둘 다 자원의 활용률이 저하되는 단점이 있다. 그래서 이와 같이 교착상태 예방은 군사, 의료, 우주 분야에서 사용하는 것이 좋다.

2. 교착상태 회피(Deadlock Avoidance)

교착상태 예방 같은 경우에는 효율성과 시스템 처리량을 떨어트린다. 따라서 교착 회피방법은 덜 엄격한 조건을 요구하여 자원을 더 효율적으로 사용하는 것이 목적이다. 교착상태 회피 방법은 위험구역을 파악하여 자원을 할당하는 방법이다. 여기서 위험구역이란 아직 교착상태는 아니지만 자원 할당 시 교착 상태가 일어날 수 있는 구역을 말한다. 교착상태 회피 방법에는 프로세스의 시작 중단과 자원할당 거부로 두가지로 나뉜다.

 

프로세스의 시작중단

프로세스의 요구가 교착상태를 발생시킬 수 있다면 프로세스 시작을 중단하는 것이다. 더 구체적으로 각 프로세스마다 요청과 해제에서 정확한 순서를 파악하고 요청에 따른 프로세스 대기 여부를 결정하는 것이다.

 

자원할당거부

자원할당과 교착상태를 회피하는 다른 방법은 다익스트라의 은행가 알고리즘을 이용하는 것이다. 은행가 알고리즘은 자원의 할당 허용 여부를 결정하기 전에 미리 결정된 모든 자원의 최대 가능 할당량을 시뮬레이션하여 안전여부를 검사한다. 그런 다음 대기 중인 모든 활동의 교착상태 가능성을 조사하여 '안전상태' 여부를 검사 확인한다.

 

또한 교착상태 회피와 예방의 차이점은 교착상태를 다르게 접근하는 것이다. 교착상태 회피에서는 교착상태를 자원 요청에 대한 잘못된 승인으로 판단한다. 따라서 교착상태 회피에서는 안전한 할당(Safe Allocation)과 불안전한 할당(Unsafe Allocation) 두 가지로 나뉜다.

 

안전한 할당

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

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

 

3개의 프로세스가 요청하는 magnetic tape의 양은 위 표와 같다. Current needs는 한 프로세스가 한 번 요청을 할 때 요구하는 개수이고, Max needs는 프로세스를 정상적으로 끝내기 위해 필요한 총 개수이다. 운영체제 입장에서 3개의 프로세스가 모두 수행될 때까지 자원을 분배해보자.

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

3개의 프로세스가 모두 자원을 할당받고 종료할 수 있었다. 이를 안전한 할당이라 한다.

 

불안전한 할당

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

 

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

• P0에게 5개를 할당한다. (5/10) -> 현재 magnetic tape 개수 : 7
• P1에게 2개를 할당한다. (2/4) -> 현재 magnetic tape 개수 : 5
• P2에게 3개를 할당한다. (3/9) -> 현재 magnetic tape 개수 : 2
• 다시 P0이 5개를 요청하지만 할당할 수 없다.
• P1에게 2개를 할당한다. (4/4) -> 현재 magnetic tape 개수 : 0
• P1은 모두 할당받았고 프로세스를 종료하고 자원을 반납한다. -> 현재 magnetic tape 개수 : 4
• 대기하고 있던 P0은 아직 할당받을 수 없다.
• P2 에게 3개를 할당한다 (6/9) -> 현재 magnetic tape 개수 : 1
• 현재 남아있는 개수는 1이고 P0은 5개를, P2는 3개를 요구하므로 두 프로세스 모두 할당 받을 수 없다.

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

 

교착상태 회피는 대출전문은행과 유사하게 동작하므로 해결방법을 Bankers Algorithm이라고 한다.

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

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

 

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

 

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

 

교착상태 검출 및 복구는 교착상태가 매우 드문 현상이므로 자유롭게 자원을 분배하다가 교착상태가 발생하면 이를 정상적인 상태로 복구하는 것이다. 하지만 복구를 제대로 하지 못할 수도 있고, 검출을 위해 추가적인 오버헤드가 발생한다는 단점이 있다.

4. 교착상태 무시

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