[운영체제] 데드락 (Deadlock)

atomicity violation : 연속적으로 수행되어야 하는 연산이 연속적으로 수행되지 못 한 경우 → mutex 로 해결

order violation : 어떤 순서를 가정했는데 그 순서로 실행되지 않는 경우

void init() {
    mThread = PR_CreateThread(mMain, ...);
}
mMain() { ... }

 mMain 보다 mThread 초기화가 먼저 이루어질 거라 가정한 코드이다.

 

데드락

 thread 1 은 lock A 을 잡았고 lock B 를 대기중인 상태, thread 2 는 lock B 를 잡았고 lock A 를 대기중인 상태에서 데드락이 발생한다.

 데드락이 발생하려면 다음과 같은 조건을 만족해야 한다.

• mutual exclusion : 공유 자원에 대한 액세스 권한을 한 스레드밖에 못 가질 때
• hold and wait : 여러 자원을 액세스하려고 할 때 자원 하나만 확보한 뒤 다른 자원은 기다리고 있는 상태
• no preemption : 갖고 있는 락을 놓지 않는 상태
• circular wait : wait 상태가 순환 구조

 위 예시는 데드락 조건 네 가지를 모두 만족하기 때문에 데드락이 발생했다. 

데드락을 해결하는 방법에는 세 가지가 있다.

- Deadlock prevention : 데드락이 아예 발생하지 않도록 방지한다.
- Deadlock avoidence : 데드락이 발생할 것 같으면 회피한다.
- Deadlock detection : 데드락이 감지되면 회복한다.

 데드락을 감지하거나 회피하는 것은 오버헤드가 크다. 그래서 보통은 아무 조치도 하지 않고, 문제가 발생하면 관리자가 알아서 해결하거나 리부팅을 한다. 데드락이 자주 발생하지 않기 때문이다. (1년에 몇 번 발생 안 한다고 한다.)

Deadlock Prevention

 데드락이 발생하려면 네 가지 조건을 만족해야 한다. 하나라도 만족하지 못 하게 만들면 데드락은 발생하지 않을 것이다.

- Mutual Exclusion

 상호배제를 없애는 방법은 상당히 어려운 방법이다. read-only, lock free object, 락을 사용하지 않는 자료구조, non preemtive 스케줄링 등을 이용해도 해결할 수 있다.

- Hold and Wait

 요청할 때 반드시 아무 lock 도 없는 상태에서 요청한다. 그리고 요청할 때에는 요청하는 모든 락을 얻을 수 있어야 한다. 쉽게 생각할 수 있는 건 non preemptive 스케줄링이 있지만 이렇게 하면 자원 사용률이 낮아진다. 또한 starvation 문제도 발생한다.

- No Preemption

 락을 잡고 있는 상태에서 다른 락을 요청할 때 락을 얻을 수 없다면 내가 가진 lock 을 포기하나.

- Cirecular Wait

 위 세 가지는 구현하기 어렵기 때문에 보통 이 방법을 많이 쓴다. lock ranking 을만든다. lock 을 사용하는 순서를 정한다. 이렇게 하면 circular wait 가 생기지 않는다. 이 방법은 툴같은 것을 지원하지 않기에 프로그래머가 잘 프로그래밍하는 수밖에 없다. lock ranking 이 항상 결정할 수 있는 건 이다.
 no preemption 조건은 없애므로써 데드락을 방지할 수 있다. trylock() 으로 lock 을 할 수 있으면 lock 을 하고 못 하면 바로 반환한다.

Deadlock Avoidance

 unsafe state 로 들어가지 않도록 하는 방법이다. 두 가지 방법이 있다.

• 자원 할당 그래프
• banker's algorithm

safe state : 프로세스들을 차례로 수행했을 때 (중간에 block 되지 않고)제대로 종료될 수 있는 상태
unsafe state : 데드락이 발생할 가능성이 있는 상태

 프로세스가 자원을 요청할 때 하나씩만 있는 자원이라면 resource allocation graph 를 사용하고 자원이 여러 개라면 banker's algorithm 을 사용할 수 있다.

자원 할당 그래프

 자원에 대한 그래프를 그려본다. 자원을 request 했을 때 cycle 이 형성되면 request 하지 못 하도록 막는다.

Banker's Algorithm

 요청할 최대 인스턴스의 개수를 이미 알고 있다고 가정한다. 프로세스가 요청할 만큼의 자원이 존재하지 않는다면 기다린다.

available : banker 가 빌려줄 수 있는 자원
max : 각 프로세스가 request 할 수 있는 자원의 개수
allocation : 실제 할당된 것
need : max - allocation

 available 은 은행원이 빌려줄 수 있는 자원이다. allocation 은 프로세스에 이미 할당되어 있는 자원이고, need 만큼 필요하다고 했을 때 available >= need 일 때 자원을 빌려줄 수 있다. 자원을 빌려줬을 때 safe 상태라면 빌려주고, unsafe 라면 reject 한다.

Deadlock Detection

 데드락이 발생하도록 허용하고, 데드락이 발생하면 복구하는 알고리즘이다. avoidance 에서 사용했던 방법을 사용하면 되지만 오버헤드가 크다. 데드락이 많이 발생하는 것도 아니라서 detection 주기가 길다. deadlcok detection 에서 어떻게 detect 할 것인가? 어떻게 회복할 것인가?

 아까 사용했던 allocation 그래프를 wait-for 그래프로 바꾸어서 cycle 이 생기는지 확인한다.

 어떻게 회복시킬 것인가? 이 상황을 종료하기 위해 자원을 뺏거나 프로세스를 종료한다. 보통은 프로세스를 종료시키는 방법을 많이 사용한다. 데드락이 발생한 모든 프로세스를 종료하거나, 데드락이 발생한 프로세스를 데드락이 없어질 때까지 하나씩 종료시킨다. 마지막으로 수행시킨 프로세스부터 죽이거나 다 죽이는 게 보통이다. 자원을 뺏는 방법은, 데드락이 발생한 프로세스를 롤백 시킨다. 다시 데드락이 발생할 수 있기 때문에 완벽한 해결 방법은 아니다.