[운영체제] 교착상태(Dead Lock, 데드락)이란? 그 해결 방법은?

💎 데드락(Dead lock, 교착 상태)이란?

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태

 

 

보통 한정된 시스템 자원을 여러 곳에서 동시에 사용하려고 할 때 발생합니다. 쉽게 예를 들면 목수 A와 B가 있는데 A는 망치를 독점한 채 못을 달라고 하고 B는 못을 독점한 채 망치를 달라고 하는 상황에서 두 목수가 양보하지 않는다면 작업이 진행되지 않는데 이러한 상황을 교착 상태라고 합니다.

 

• 시스템 자원
• 공유 변수
• 응용 프로그램

 

위의 3가지를 사용할 때 교착 상태가 발생할 수 있습니다.

 

💎 Dead lock 필요조건

교착 생태가 발생하기 위해서는 아래의 4개의 조건을 충족시켜야 발생합니다.

 

• 상호 배제 : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다. (즉, 동시에 사용할 수 없는 자원을 이용)
• 비선점: 이미 다른 프로세스에게 할당된 자원은 빼앗을 수 없다.
• 점유와 대기 : 프로세스가 어떤 자원을 가진 상태에서 다른 자원을 기다리는 상태여야 한다.
• 원형 대기 : 점유와 대기를 하는 프로세스간의 관계가 원으로 이루어야 한다.

 

💎 Dead lock 해결 방법

교착 상태를 해결하기 위한 방법으로는 예방, 회피, 검출, 회복이 있습니다.

교착 상태 해결 방법

 

💡 교착 상태 예방

교착 상태가 발생하기 위한 필요조건 4개 중 하나를 무력화시키면 됩니다.

• 상호 배제 예방 : 독점적으로 사용할 수 있는 자원을 없애버린다. 즉, 시스템 내의 모든 자원을 공유할 수 있다면 교착 상태는 발생하지 않는다.
• 비선점 예방 : 모든 자원을 빼앗을 수 있도록 만든다.
• 점유와 대기 예방 : 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 한다.
• 원형 대기 예방 : 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는다.

 

💡 교착 상태 회피

프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법입니다. 미리 할당되는 자원의 수를 조절하여 교착 상태를 피하는 것을 의미합니다.

 

교착 상태 예방은 프로세스 작업 방식을 제약하지만 운영 방식에 변경을 가하지 않기에 좀 더 유연합니다. 교착 상태 회피는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태(safe state)와 불안정 상태(unsafe state)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당합니다. 이를 구현하는 방법 중 은행원 알고리즘이 있습니다.

 

하지만 이러한 교착 상태 회피에도 문제점이 있는데 다음과 같습니다.

1. 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
2. 시스템의 전체 자원 수가 고정적이어야 한다.
3. 자원이 낭비된다.

 

💡 교착 상태 검출

교착 상태 예방은 어렵고, 교착 상태 회피는 구현할 수 있지만 자원을 낭비합니다. 그래서 가장 현실적인 방법은 교착 상태 검출하는 방법입니다. 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방식입니다. 교착 상태를 검출하면 교착 상태 회복 단계를 밟습니다.

 

• 타임아웃을 이용한 교착 상태 검출 : 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태 발생한 것으로 간주
• 자원 할당 그래프를 이용한 교착 상태 검출 : 말 그대로 자원 할당 그래프를 이용해 교착 상태 발견

 

💡 교착 상태 회복

교착 상태를 검출하고 회복하는 단계입니다. 이때 교착 상태를 유발한 프로세스를 강제로 종료합니다.

• 교착 상태를 일으킨 모든 프로세스를 동시에 종료
• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

 

이때 강제 종료하는 일뿐만 아니라 강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 해야 합니다. 시스템 복구는 명령어가 실행될 때 체크포인트를 만들어 가장 최근 시점으로 돌아가는데 이 작업량이 상당하여 무분별하게 사용하면 안 되고 선택적으로 사용해야 합니다.