[운영체제] Ch07 : 교착상태 (Deadlock)

kkado·2022년 6월 13일

운영체제

목록 보기

2/3

1. 교착상태(Deadlock)의 개념

위의 그림과 같이 교차로에서 많은 차들이 서로 비켜주기만을 기다리고 있어 움직이지 못하는 상황이 전형적인 교착 상태라고 할 수 있다.

또는 사다리의 양쪽 끝에서 한 사람은 내려가기 위해 기다리고 있고, 한 사람은 올라가기 위해 기다리고 있으면 어느 한 사람이 먼저 내려오거나 올라가야 하는데 서로에 의해 막혀 있기 때문에 결국 둘 중 누구도 작업을 완료할 수 없다.

이와 같은 상황을 교착 상태(Deadlock, 이하 데드락) 이라고 한다.

두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다. (위키피디아)

2. Deadlock Condition

데드락이 발생하기 위한 필요조건은 다음 4가지이다.

2-1. Mutual Exclusion (상호 배제)

프로세스들이 자원을 상호 배타적으로 점유, 즉 한 프로세스가 자원을 소유하고 있으면 다른 프로세스들은 그 자원에 접근할 수 없다.

2-2. Hold and Wait (점유 & 대기)

한 프로세스가 어떤 자원을 점유하고 있는 상태로 다른 자원을 필요로 한다.

2-3. No preemption (비선점)

자원을 선점할 수 없다. 즉 자원을 빼앗을 수 없다. 어떤 자원을 가지고 있는 프로세스가 자발적으로 그 자원을 반납하여야 다른 프로세스가 사용할 수 있다.

2-4. Circular wait (환형 대기)

프로세스들이 서로 환형(원형)을 이룬 채 서로의 자원을 필요로 하고 있다.
예를 들어 P0이 P1의 자원을, P1이 P2의 자원을, 다시 P2가 P0의 자원을 요구하여 서로 맞물려 있다.

이 4가지 조건들이 모두 충족되어야 데드락이 발생할 수 있다.
4가지의 조건이 충족된다고 무조건 데드락이 발생하는건 아니다. 그러나 4가지 조건 중 한 가지라도 충족되지 않으면 데드락은 발생하지 않는다.

3. Resource Allocation Graph

어떤 프로세스가 어떤 자원을 소유하고 있고, 또 어떤 자원을 요청하고 있는지 하나의 그림으로 표현 가능하다.

위 그림에서 파란색 원은 프로세스, 주황색 사각형은 자원이고 사각형 안의 점들은 각각의 자원을 동시에 가질 수 있는 프로세스 수이다.

즉 P1은 R2를 점유하고 있으면서 동시에 R1을 요청하고 있고, P2는 R1, R2를 모두 점유하고 있으면서 R3를 요청하고 있다. P3는 요청하고 있는 자원은 없고 R3만 점유하고 있다.

위와 같은 그림을 Resource allocation graph라고 하며, 이를 통해 데드락 발생 가능성을 알아볼 수 있다.

Cycle의 유무와 Deadlock

만약 위의 그림처럼 P3가 R2를 요청하고 있다면?

그러면 P1, P2, P3이 각각 요청 및 점유하고 있는 자원이 서로 맞물려 사이클을 형성한다.
P1이 필요한 자원은 P2가, P2가 필요한 자원은 P3가, P3가 필요한 자원은 P1, P2가 점유하고 있으니 말이다.

즉 위와 같은 그림에서는 데드락이 발생할 수 있다.

데드락이 무조건 발생한다 는 것이 아니다. 데드락이 발생할 수 있다 는 것이다.

한편, 다음 그림을 보자.

분명 P1과 P3가 서로 R1, R2를 점유 및 요청하고 있으므로 사이클이 발생했다.
그러나 위의 그림에서는 데드락이 발생하지 않는다.

그 이유는 P2, P4가 다른 별도의 자원을 요청하지 않고 있기 때문이다.

P2, P4가 별도의 자원을 요청하지 않는다는 말은 곧, P2, P4 각각의 프로세스 종료 및 자원 반납에 애로사항이 없다는 뜻이다.

즉 P1, P4 모두가 R2를 소유하고 있고 P3이 R2를 요청하고 있다 하더라도, P4는 언제든지 프로세스를 종료 및 자원을 반납해서 P3에게 전달해 줄 수 있기 때문에 위와 같은 그림에서는 데드락이 발생하지 않는 것이 보장되어(guranteed) 있다.

4. Deadlock Handling

데드락을 handling 하는 방법은 크게 3가지이다.

Use protocol to prevent or avoid deadlock : 앞서 4가지 조건 중 하나만 만족하지 않게끔 하면 데드락이 발생하지 않을 수 있다. 아니면 해당 작업을 받아들였을 때 데드락이 발생할 우려가 있는지 먼저 점검한 후에, 발생할 우려가 있다면 아예 그 작업을 받아들이지 않음으로써 데드락의 발생 가능성을 원천봉쇄 할 수도 있다.
Detect and recover it : 일련의 데드락 회복 과정을 거쳐 데드락에서 빠져나오는 방식이다. 방법론적인 이야기이며 구체적인 방법은 제시하지 않고 있다.
Ignore and hope that it never happens : 오늘날 많은 OS가 채택하고 있는 방법이다. 데드락 처리 매커니즘에는 성능 저하가 수반된다. 하지만 그에 비해 실제로 데드락이 발생하는 경우는 그리 많지 않다. 발생할지도 모를 데드락을 대비하기 위해 시스템의 성능을 저하시키기보단 따로 데드락에 대한 대책을 마련하지 않고 성능에 집중하는 것이다. 데드락이 발생하면 그냥 재부팅하거나 kill 시켜버린다.

5. Safe state

운영체제가 어떤 프로세스에 자원을 할당해주기 전에, 이 프로세스에 자원을 할당해 주었을 때 데드락이 발생할 가능성이 있는지를 점검한다.

이 때 데드락의 발생 가능성이 있다면 자원을 할당해주지 않는다.

위의 예시를 보면 전체 12만큼의 자원을 사용할 수 있고 P0, P1, P2에 각각 5, 2, 2씩 할당해주어 3이 남은 상태이다.

max needs는 이 프로세스가 총 필요로 하는 자원의 양,
current는 현재 할당받은 양,
still needs는 아직 더 할당받아야 하는 양이다. (Max - Current)

여기서 P1에 2를 더 할당해주면 P1은 작업을 끝내고 4만큼의 자원을 반환한다. 즉 이용 가능한 자원이 5가 되었다. 다시 P0에 할당하여 작업을 끝내고 10만큼을 반환받으면 총 자원이 10이 되고 이를 마지막으로 P2에 할당해주어 모든 프로세스를 데드락 없이 종료할 수 있다.

이렇게 데드락이 발생하지 않을 수 있는 상태를 Safe state 라고 한다.
그리고 데드락이 발생하지 않는 자원 할당 순서를 Safe sequence 라고 한다.

다음과 같은 사례를 보자.

남은 자원 2를 P1에 할당해 줌으로써 우선 P1은 잘 종료할 수 있다. 그리고 남은 사용 가능 자원은 4가 된다. 그러나 P0, P2가 필요로 하는 자원은 각각 5, 6이다. 어느 한 프로세스에 자원을 몰아줘도 프로세스를 종료할 수 없다.

이처럼, 데드락이 발생할 수 있는 상황을 Unsafe state 라고 한다.

데드락 회피의 핵심은 항상 safe state가 되게끔 자원을 할당하는 것이다.

항상 safe state에 있도록, safety check를 해 주어 데드락의 발생 위험 구역으로 들어가지 않게끔 한다.

6. Banker's Algorithm

어떤 새로운 프로세스가 들어왔을 때, 이 프로세스에 자원을 할당하는 행위가 시스템을 unsafe state로 만드는지 검사하고, 만약 그렇다면 대기시키고 그렇지 않다면 자원을 할당해 준다.

자원은 A, B, C 세 종류가 있으며 이는 (3, 3, 2)와 같이 하나의 벡터로 표현한다.

Allocation : 각 프로세스에 현재 할당된 자원 양
Max : 이 프로세스가 필요한 자원의 총량
Available : 현재 다른 프로세스들에게 할당해 줄 수 있는 여유 자원 양
Need : 각 프로세스가 할당 받아야 하는 자원 양 (Max - Allocation)

그리고 진행 방식은 다음과 같다.

초기 상태는,work = available, 그리고 모든 프로세스에 대해 Finish[i] = False 로 선언해준다.
그리고 Finish가 False이고, 필요한 need량이 work보다 작거나 같은 프로세스를 찾는다.
그 프로세스에게 모든 사용 가능한 자원들을 할당시키면 그 프로세스는 성공적으로 종료되어 할당되었던 자원들을 반환한다. work에 allocation을 더해준다. 종료되었다는 의미로 finish[i]=True로 바꿔준다.