deadlocks

The Deadlock problem

: 자원을 점유하고 있으면서 서로의 자원을 점유하기 위해 무한정 대기하는 문제

 

예를 들면

semaphore A와 B를 기다리는 프로세스 두개를 생각해보자

process 0의 wait(A)가 실행되고 context switch가 발생하여 process 1이 수행된다고 하자.

이 경우 process 1에서 wait(B)를 수행하고 나면 A와 B 모두 품절된 상태이다. (A는 0이, B는 1이 가져감)

그런데 process 1에서는 A를 대기하고 있고, process 0에서는 B를 대기하고 있다.

즉 서로의 자원을 서로가 대기하고 있기 때문에 무한정 대기하는 현상이 발생한다.

이와 같은 상황을 deadlock 이라고 한다.

 

deadlock characterization

: deadlock은 다음 4가지 상황이 동시에 진행될 때 발생 가능하다. 물론 아닐 수도 있다는게 deadlock의 문제이다.

1. mutual exclusion

2. hold and wait

: 점유 대기 상태. 즉 이미 어떤 shared data를 가지고 있는데 다른 process에 할당된 자원을 대기하는 경우

3. no preemption

: 비선점. 점유하고 있는 자원을 끝날때까지 강제로 가져오지 않는 경우. 이 경우 무한정 대기하는 상황이 발생할 수 있기 때문

4. circular wait

: 순환 대기. process와 자원들이 원형을 이루어 각 프로세스는 자신에게 할당된 자원을 가지면서 상대방 프로세스의 자원을 상호 요청하는 경우

 

그렇다면 deadlock은 어떻게 해결할 수 있을까?

Handling deadlocks

1. deadlock prevention

: 발생을 아예 막자.

deadlock이 발생되지 않도록 소프트웨어를 설계하는 것이다. 이는 개발자의 역할이 중요하다.

2. deadlock avoidance

: deadlock의 발생 가능성을 test하여 없을 때만 자원을 할당한다.

이러한 검사를 운영체제가 진행하기 때문에 운영체제는 항상 자원에 대한 상태를 관찰해야한다. 따라서 오버헤드가 큰 방법이다.

3. deadlock detection and recovery

: 주기적으로 검사하여 deadlock이 발생한 경우, deadlock 상태의 process들을 모두 stop하거나 deadlock이 해결될 때 까지 프로세스를 하나씩 kill한다.

하지만 검사 알고리즘 자체가 오버헤드가 크다는 단점이 있다.

4. ignorance

: do nothing!

이 방법을 수업시간에 배웠을 때 나는 교수님께서 농담을 하시는 줄 알았다. 하지만 진짜로 아무것도 하지 않는다는 뜻이었다..

결국 개발자에게 모든 책임을 넘기고 현재의 os는 이 방식이라고 한다.

따라서 deadlock prevention이 중요한다. 이를 위한 코딩 휴리스틱이 있다.

 

deadlock prevention을 위한 코딩 휴리스틱

1. mutual exclusion을 막자

: 혼자만 자원을 쓰는 것을 막자

즉 여러개의 process가 공유자원을 사용할 수 있도록 허용해준다.

하지만 어떤 것은 자원공유가 안되는 경우도 존재하므로 불가능할때도 있다.

 

2. hold and wait

: 어떤 자원을 요구할 때 모든 자원의 요청을 받고 할당 받으면 된다.

프로세스가 필요로 하는 자원을 한번에 다 요구를 하면 한번에 한 프로세스만 그 모든 자원을 가질 수 있으면 가능하다.

하지만 자원이 낭비되고 효율성이 떨어진다. 게다가 특정 프로세스는 계속 수행이 되지 않는 starvation이 발생하게 된다.

 

3. no preemption

: 비선점을 선점으로 바꾸자 (매우 효과적!)

우선순위가 높은 process가 자원을 뺏어오는 것을 가능하게 하면 deadlock 때문에 사용이 되지 않던 자원도 가져올 수 있다.

예를 들어 dining philosopher 문제에서도 철학자들끼리 등급을 매겨 높은 등급의 철학자에게 chopstick을 양보하면 된다.

하지만 자원이 뺏긴 Process는 현재까지 진행했던 작업들이 모두 무효화되어버린다. 따라서 다시 작업을 재개하고자 하면 기존에 가지고 있던 old resource와 new resource를 다 할당받아야 해서 starvation이 발생할 수도 있다.

 

4. circular wait

: 번호를 붙이자

모든 resource에게 번호를 붙여서 process들이 자원을 오름차순으로 요구한다면 우선순위 개념이 생겨서 deadlock이 생기지 않는다.

하지만 복잡하고 새로운 자원이 추가된 경우 Numbering 알고리즘 또한 필요하기 때문에 사용하지 않는다.