[운영체제] 교착 상태 (Dead Lock)

교착 상태 (Dead Lock)

교착 상태란 2개 이상의 프로세스들이 서로의 자원을 얻지 못해서 진행할 수 없는 상황을 말한다.

프로세스에게 한정된 자원이 할당되었을 때 프로세스들의 자원 부족으로 더 이상 실행할 수도 없으며, 종료 후에 다른 작업을 시작하는 것도 불가능한 상태를 말한다.

 

block된 프로세스들은 각각의 자원을 가지고 다른 프로세스가 점유한 자원을 얻기를 기다리고 있는 상태이다.

두 프로세스는 무한정 wait 상태에 빠지게 된다.

 

자원은 한 번에 하나의 프로세스에 의해서만 사용될 수 있고 non preemtable resource로 선점 불가능 하기 때문에 일반적으로 데드락이 발생한다.

데드락 발생 조건

하나라도 만족하지 않으면 데드락은 해결된다.

상호 배제 Mutal exclusion

자원은 한번에 하나의 프로세스만 사용할 수 있다.

하나의 자원을 두 개 이상의 스레드가 점유할 수 없다.

비선점 No preemption

어떤 자원은 그 자원을 점유한 프로세스가 task을 완료 했을 때, 그 프로세스에 의해 자발적으로만 방출된다. 중간에 다른 프로세스가 강제로 뺏을 수 없다.

점유 대기 Hold and wait

어떤 프로세스는 적어도 하나의 자원을 점유한 상태에서 다른 프로세스에 의해 점유된 다른 자원을 추가적으로 얻기를 기다리고 있어야 한다.

순환 대기 Circular wait

스레드와 자원이 순환적으로 꼬리를 물고 기다리는 구조이다.

식사하는 철학자 문제

5명의 철학자와 5개의포크가 있고 식사를위해서는 한사람당 두 개의 포크가 필요한 상황이다.

• 한 개의 포크를 두 명 의 철학자가 동시에 사용할 수 없고 (mutual exclusion)
• 한 철학자는 각각 왼쪽 포크를 가진 상태로 오른쪽 포크를 기다린다. (Hold and wait)
• 또 철학자는 이미 다른 철학자가 가지고 있는 포크를 빼앗을 수 없다 (No preemption)
• 원형 테이블이므로 순환 구조를 가진다 (Circular wait)

따라서 Deadlock의 조건을 만족하므로 Deadlock이 발생한다.

데드락 해결 방법

예방 기법 Deadlock Prevention

데드락의 4가지 조건인 상호 배제, 점유 대기, 비선점, 순환 구조 중 하나라도 만족하지 않도록 하여 데드락을 해결하는 것을 데드락 예방이라고 한다.

• 상호배제 부정: 여러 프로세스가 공유 자원을 사용하도록 한다.
• 점유 대기 부정: 프로세스가 실행되기 전에 필요한 모든 자원을 할당한다.
• 비선점 부정: 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원을 반납하도록 한다.
• 순환구조 부정: 자원에 번호를 붙여 놓고 프로세스에게 무조건 순서대로 요청하도록 요구한다.

자원 낭비가 심하다.

회피 기법 Deadlock aviodance

시스템이 request했을 때 데드락이 발생할 수 있는 상태인지 확인하고 발생하지 않을 경우만 승인하여 데드락을 해결하는 것을 데드락 회피라고 한다. 은행원 알고리즘이 사용된다.

 

은행원 알고리즘

• 은행의 모든 고객의 요구가 충족하도록 현금을 할당하는데서 유래
• 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아 있게 되는지 사전에 검사하여 교착 상태를 회피한다. 안정 상태일 경우만 자원을 할당하고 아니면 다른 프로세스들이 자원을 해지할 때까지 대기한다.

탐지 & 회복 기법Deadlock detection and recovery

데드락을 주기적으로 체크한 후 데드락된 프로세스를 죽이고 리소스를 방출하는 것으로 회복하여 데드락을 해결한다.

 

탐지

자원 할당 그래프를 통해 교착 상태를 탐진한다. 자원 요청시, 탐지 알고리즘을 실행시키기 때문에 그에 대한 오버헤드가 발생한다.

 

회복

교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복한다.

• 프로세스 종료: 교착 상태의 프로세스를 모두 중지 혹은 교착 상태가 제거될 때까지 하나씩 프로세스 중지
• 자원 선점 방법: 교착 상태의 프로세스가 점유하고 잇는 자원을 선점에 다른 프로세스에게 할당한다. 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원을 선점한다.