데드락(Deadlock)을 방지하는 방법에 관하여

데드락의 처리방법

데드락은 상호배제, 비선점, 보유 대기 및 순환대기 조건이 모두 충족되어야 발생할 수 있습니다.

 

즉 해당 조건이 충족되지 않게 한다면, 데드락 발생을 예방할 수 있다는 말이 됩니다.

 

데드락의 처리 방법에는 다음과 같은 크게 4가지 방법이 존재합니다.

 

 

 

 

Deadlock prevention

가장 강력한 방지법으로 데드락이 발생할 수 있는 원천적인 요소, 발생조건을 차단하는 것을 말합니다.

 

상호 배제의 경우 공유하는 자원의 경우 반드시 성립해야 하기 때문에 다른 발생조건을 방지하는 방법으로 진행합니다.

 

 

점유 대기 방지

해당 조건을 방지하기 위해서는 자원을 요청하는 상황에서는 어떠한 자원을 보유하지 못하게 진행합니다.

 

방법은 대표적으로 두가지가 존재합니다.

 

첫 번째는 프로세스가 시작될 때 필요한 모든 자원을 할당받도록 하고, 종료될 때 모두 반납되도록 합니다.

 

따라서 처음부터 모든 자원을 받았기 때문에 자원을 기다릴 일이 없게 됩니다.

 

두 번째는 또 다른 방법으로는 자원이 필요할 경우 보유 자원을 모두 놓고 요청하도록 합니다.

 

 

비선점 -> 선점

프로세스가 어떤 자원을 기다려야 하는 경우에는 이미 보유한 자원이 선점되도록합니다.

 

그리고 필요한 자원을 얻을 수 있을 때 해당 프로세스는 다시 시작됩니다.

 

상태를 쉽게 저장하고 복구할 수 있는 CPU, memory 자원에서 사용할 수 있습니다.

 

해당 방법은 자원을 선점당하면 문제가 생기는 상황에서는 당연히 사용하기 어렵습니다.

 

 

순환 대기

자원 유형에 대해 할당 순서를 정하여서 순서대로만 할당할 수 있게 진행합니다.

 

자원의 우선순위가 두어서 순환 대기를 방지하는 것입니다.

 

Deadlock starvation 방법은 강력하게 데드락을 방지할 수는 있지만, 처리량 감소, Starvation 문제등 문제가 많습니다.

 

또한 데드락 방지에는 오버헤드가 수반됩니다.

 

 

 

 

Deadlock Avoidance

자원 요청에 대한 부가정보를 이용해서 자원할당이 데드락으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당하는,

 

보수적 자원 할당 기법입니다.

 

 

Banker's Algorithm

뱅커스 알고리즘은 프로세스가 요청할 최대 자원 수를 계산하고, 가지고 있다가

 

프로세스가 일정량의 자원을 요청했을 때, 현재 가용자원만으로 해당 프로세스의 최대 요청 수를 만족시킬 수 있다면, 자원을 할당해주고,

 

그렇지 않다면 자원할당을 거부하는 알고리즘입니다.

 

가용자원이 0이 된다고 해서 반드시 데드락이 발생하는 것은 아니지만 (추가 요청 없이 종료될 프로세스가 존재할 확률이 높기 때문에)

 

뱅커스 알고리즘은 프로세스들이 최대 요청을 할 것을 가정하고 보수적으로 움직이게 됩니다.

 

뱅커스 알고리즘의 장점은 당연히 데드락에 있어 안전하다는 것이고, 단점은 데드락이 발생할 확률이 낮은데 자원을 보수적으로 할당해주다

 

보니 비효율적이라는 것입니다.

 

 

 

Deadlock Detection and recovery

해당 기법은 데드락이 발생했을 경우 복구작업을 진행한다는 내용입니다.

 

Resource type마다 자원이 여러개 존재할 때, 뱅커스 알고리즘과 비슷한 방식으로 동작합니다.

 

다만 뱅커스 알고리즘과는 다르게 자원을 요청하면 그냥 자원을 무조건 주게 됩니다.

 

그리고 데드락인지 판단하는 방법은 낙관적인 접근을 하면 됩니다.

 

자원을 추가로 요청하지 않은 프로세스들에게 존재하는 자원은 반납 가능성이 존재한다고 가정하고,

 

반납된 내용을 통해 추가적인 요청을 처리할 수 있다고 판단합니다.

 

다만 이러한 경우에는 데드락이라고 할 수 있습니다

Process	Allocation A B C	Request A B C	Available A B C
P0	0 1 0	0 0 0	0 2 0
P1	2 0 2	1 0 0
P2	1 0 1	0 0 1

해당 경우에서는 추가적인 자원 요청이 없는 프로세스 P0가 이후 자원을 반납하더라도,

 

자원을 요청한 P1, P3 프로세스는 서로 상대방이 가진 자원을 기다리면서 사이클을 돌게 될 것입니다.

 

두 프로세스는 끝나지 않게 될 것이고 따라서 해당 경우는 데드락입니다.

 

 

Deadlock Recovery

그렇다면 데드락이 발생했을때 복구작업은 어떻게 이루어지는지 알아보겠습니다.

• 프로세스 종료 방법
  • 데드락에 연루된 모든 프로세스를 모두 죽이는 방법이 존재합니다.
  • 또 다른 방법으로는 연루된 프로세스를 하나씩 죽여보는 방법으로 데드락이 풀릴 때까지 진행합니다.
• 자원 선점 방법
  • 프로세스로 부터 자원을 선점할 수 있도록 하여 해결합니다.
  • Starvation을 방지하기 위해 자원을 많이 빼앗긴 프로세스를 생각해야 하며, 데드락 제거 이후 같은 패턴으로 데드락이 발생하는 것을 막기 위해 자원을 빼앗는 방식을 다양한 방식으로 진행하여야 합니다.

 

 

Deadlock Ignorance

해당 방법은 데드락을 무시한다는 것입니다.

 

방법이라 하기에는 좀 그렇지만 대부분의 운영체제는 사실 데드락을 무시한다고 합니다.

 

 데드락의 발생은 매우 드물게 발생하는데, 그 데드락의 조치를 및 예방을 취하는 것 자체가 오버헤드를 발생시키기 때문입니다.

 

따라서 Deadlock Ignorance 방법은 사용자에게 데드락 처리를 맡깁니다.

 

데드락이 발생하여 컴퓨터가 이상해졌다면, 이상해진 컴퓨터를 사용자가 감지하고

 

작업관리자 -> 프로세스 강제종료와 같이 사용자가 알아서 프로세스를 죽이는 것으로 대처한다는 것입니다.

 

 

 

출처

KOWS 운영체제 - 반효경 교수님 - Deadlock 2

http://www.kocw.net/home/search/kemView.do?kemId=1046323