Deadlock, 교착상태란? [운영체제]

 

 

 

꼬리 물기해서 망한 도로의 사진이다. 이제 이 도로는 망했다.

절대 나갈 수 없다.

꼬리물기는 나쁜 것이다

빨간 불 되면 멈춰야 서로 좋다.

 

컴퓨터에서도 이런 현상이 일어난다는데

교착상태, deadlock이다.

알아보자 

 

동기화에 대해 알고 있다는 가정 하에 설명한다.

[컴퓨터(Computer Science)/운영체제(Operation System)] - 프로세스에서의 동기화 (Process Synchronization) [운영체제]

 

---

 

 

 

앞의 동기화에서 이미 알아본 현상이다.

서로의 Event를 기다리며 무한히 대기하는 상태를 말한다.

**Event란 자원의 할당과 해제를 의미한다.

P0는 B자원을 기다리며 A를 점유하고

P1는 A자원을 기다리며 B를 점유하고

누구하나가 자신의 자원을 내놓지 않는 한 무한 대기상태에 빠져버린다.

 

---

 

그렇다면 어떤 상황에 교착상태, deadlock이 발생하느냐?

 

 

위의 조건을 모두 만족할 때 deadlock이 발생한다.

 

우선

매 순간 하나의 프로세스만이 자원을 사용할 때 발생할 수 있다.

A자원이 B자원 점유와 상관없이 자원을 쓸 수 있다면 당연히 무한 대기 상태는 나오지 않을 것이다.

 

다음으로는

비선점(선점되지 않음) -> 자원을 빼앗기지 않는다.

위 상황처럼 내가 점유하고 있으면 다른 프로세스가 그 자원을 빼앗아서 쓸 수 없다.

빼앗을 수 있다면 당연히 deadlock은 나오지 않았다.

 

다음으로는

자원을 점유하며 대기하는 것이다.

내가 바로 수행할 수 없더라도 자원을 점유하는 것은 위의 상황과 같다.

위의 경우에는 한 프로세스만 자원을 반납하더라도 잘 수행될 수 있지만 자 그렇지 않다.

 

마지막으로는

순환 대기다.

p0는 p1을 기다리고 p1은 p0를 기다리게 되면  p0 -> p1 -> p0 의 고리가 만들어진다.

결국 맨 위의 차가 막히는 것과 같은 원리다.

 

---

 

deadlock이 발생할 지는 그래프를 그려서 알아본다.

 

P : process

R : resource (점의 수는 Resource count를 의미)

Edge : request, assignment

**프로세스에서 자원으로 가는 간선은 request

**자원에서 프로세스로 가는 간선은 assignment

 

 

deadlock의 구분은 아래와 같이한다.

 

 

Cycle이 있는지 체크

없으면 deadlock발생 x

있으면 다시 한번 조사

자원에 점이 하나라면, 즉 유일하다면 deadlock이 발생한다.

자원이 여러 개라면 deadlock이 발생하지 않을 수도 있다. (꼭 그런 것은 아니다)

 

다시 말하면 자원의 수에 해당하는 cycle이 만들어지면 자원을 반납할 수 없으므로 deadlock이 발생한다.

 

---

 

그렇다면 어떤 조건이 deadlock이 발생하지 않느냐??

 

 

우선 4가지의 조건이 있고 아래로 갈수록 강도가 덜해진다.

 

마지막을 보면 교착상태를 무시하는 그런 경우가 있다.

대부분 OS 에서는 Deadlock을 가만히 냅두는데.. 사실

deadlock이란 것이 흔히 일어나는 상황이 아니기 때문에

처음부터 방지하려고 하는 것이 오버헤드가 훨씬 크기 때문에 그렇다.

우리가 어떠한 오류가 걸렸을 때 프로세스종료하시겠습니까?

가 우리가 느낄 수 있는 단적인 예라고 보면 되겠다.

 

그렇지만 우리는 공학도로서

무시말고 다른 방법을 알아보도록 하자.

 

---

 

Deadlock Prevention이다.

처음부터 4가지 조건을 충족시키지 못하게 구현하는 것이다.

 

 

위 4가지 조건에서

 

Mutex는 없앨 수 없고

Hold and Wait는 그나마 없앨 수 있다.

No preemption 같은 경우 빼앗겨도 오류가 생기지 않는 자원을 빼앗으면 된다.

Circular는 자원 순서를 정해놓는 것으로 피할 수 있다.

 

하지만 사실 전체 시스템의 성능을 낮춰서 그렇게 쓰이지 않는다.

 

---

 

Deadlock Avoidance에 대해 알아보자

 

 

처음부터 프로세스가 시작할 때 각 자원별 최대 사용량을 미리 선언하여 알고있다.

 

자원을 요청받을 때

자원 할당을 할 때 deadlock이 생길지 조사를 해서 할당을 하는 방법이다.

 

 

자원의 개수에 따라 해결방법이 조금 다르다.

 

자원이 하나일 경우

 

** 점선 edge의 의미는 위에서 말한 미리 자원의 사용량을 선언한 것에서 온 것으로 자원을 요청할 수 있음을 의미한다.

위 상황은 deadlock같아 보이지만 마지막 cycle을 보면 점선으로 되어있다. 

즉, 마지막 cycle에선 p1이 자원을 요청할 경우 deadlock 이 걸릴 수 도 있다.

그래서 r2가 점유되어있지 않고 p2가 r2를 요청했음에도 자원을 주지 않아서 deadlock이 생길 가능성을 없애는 것이다.

하지만 p1이 r2를 요청할 때는 줄 수 있다.

cycle이 생기지 않기 때문이다.

 

 

자원이 여러 개 일 경우 (Banker's Algorithm)

 

위 조건이 있다.

 

 

프로세스가 5개

자원이 3가지 종류가 각각 10,5,7 개

 

Max라고 써있는 부분이 처음 프로세스를 선언할 때 자원의 최대 사용량을 정해놓는 부분이다.

전체에서 Available을 빼면 Allocation이 나오겠고

Max에서 Allocation을 Need가 만들어지고 Need는 추가로 요청할 수 있는 자원 양을 말한다.

 

 

위 상황에서 p1이 A자원 1개 C자원 2개를 요청했다고 해보자

available한 자원이 need를 충당할 수 있다.

 

만약 그렇다면 p0이 B를 2개 요청하면 어떻게 될까??

Available을 보면 B는 2개를 줄 상황이 된다.

하지만 우선 Need를 보면 Available로는 가능하지 않다.

그래서 자원을 할당하지 않고 나머지 프로세스들이 자원을 반환할 때까지 대기한다.

즉, Need <=Available이 되어야만 자원을 할당할 수 있게 하는 것이다.

 

 

 

---

 

다음으로 Deadlock Detection and recovery를 알아보자

 

 

시스템의 성능이 저하되면 deadlock이 발생했는지 의심해서 조사하고

deadlock이 발생했으면 그것을 recovery하는 것이다.

 

역시 dectection은 앞서 말했던 것과 비슷하게

자원이 하나일 때

자원이 여러 개일 때 구분해서

detection이 가능하다.

 

역시나 하나일 때는 그래프로 구분할 수 있고

** 뭐 테이블로 구분할 수 있지만 하나니까 이렇게 하는거다.

 

Cycle이 발생하는 지 관찰하는 것까지 똑같다.

**Cycle을 조사하는 시간 복잡도는 O(N^2)가 된다.

 

 

 

여러 개일 경우에는

테이블을 그려서 구분할 수 있다.

 

역시 프로세스는 5개

자원의 종류는 3개이고 각각 7,2,6개를 가진다.

위와 다르게 여기는 need가 없다.

 

 

만약 P2가 자원 요청을 하게 되면 어떻게 될까?

 

P0가 B를 반납해봤자

다른 프로세스는 자신의 자원의 요청이 받아질 때까지 자원을 점유하고 내놓지 않기 때문에

P1,P2... 다 자원을 점유만하고 요청을 만족하지 못하는 상황이 오고 결국 deadlock이 걸릴 것이다.

 

여기선

요청하지 않는 프로세스의 경우 곧 자원을 반납하겠구나 생각하고

요청하지 않는 프로세스의 자원점유 + 현재 Available을 포함해서 계산한다.

하지만 위의 상황에서는

P0가 반납해봤자 다른 프로세스의 요청이 받아들여지지 않기 때문에 deadlock이 걸리는 것이다.

 

 

 

 

그래서 detection이 되면 어떻게 하느냐?

2가지 방법이 있다.

프로세스 자체를 없애거나 자원을 빼앗거나

 

프로세스를 없애는 방법은

1. 프로세스를 모두 종료시키거나

2. 하나씩 종료시키면서 deadlock이 없어질 때까지 진행하거나

 

자원을 빼앗을 때는

비용을 최소화할 수 있는 프로세스를 선정한다.

하지만 해당 프로세스가 계속 victim으로 선정될 경우(최소 비용)

해당 프로세스는 자원을 점유할 수 없어 starvation이 발생할 수 있으므로 조금씩 다르게 고려해야한다.

 

 

---

 

마지막은 무시하는 것이다.

 

대부분의 OS가 채택하는 이유는 사용자가 프로세스에 대해 제어하는 것이 성능이 저하되는 것 보다 나아서 그렇다.