[OS] Deadlock (교착상태)와 Deadlock 처리

Deadlock

프로세스는 실행을 위해 여러 hw자원(resources)을 필요로한다. 그리고 이 자원을 사용하는 application들이 있다. OS는 그 자원을 잘 나누어주어야한다.

예를들어 아래와같은 상황이 발생하면서도 공교롭게도 가끔, 아차! 싶으면, 교착상태가 발생한다.

• P1이 자원의 일부는 가졌으나 일부자원A는 가지지 못했을 떄, waiting해야한다.
• 다른 프로세스P2가 자원A을 가지려고 waiting하고있었을 때 둘다 기다리는 상태이므로 교착상태(Deadlock)의 가능성이 존재한다.

이 4가지가 모두 만족될 때, 교착상태가 일어날 수도있다.

• Mutual exclusion : 상호 배타. 한사람이 쓰고있으면 다른사람이 쓰지못하는 경우
• Hold and wait : 어떤 자원을 가지고있으면서 대기하고있을 때
• no Preemption : 비선점. 갖고있는걸 강제로 뺏을 경우. 하지만 보통 동기화의 경우 강제로 뺏는 경우란 존재하지 않는다. 그래서 생기는 문제임.
• Circular wait : 사이클이 하나의 원을 이루기 때문에 (모두 왼쪽을 대기중.. 이런거)

실제 컴퓨터에서 deadlock이 발생하면, pc의 경우에는 pc가 전원은 켜져있지만 아무런 작동을 하지 못하는 것이다. 그래서 전원을 껐다 켜야하는 경우가 발생함. 그저 개인용 PC이라면 매우 심각한 문제는 아니겠지만 서버컴퓨터라던가, 임베디드의 수많은 기계들에서, 은행/증권에서도 굉장히 심각한 문제를 발생시킨다.

그래서 OS에서는 deadlock이 생기지 않도록 조치를 미리 취해줘야한다.

교착상태가 실제로 자주 일어나는일은 아니지만

---

Resources

결국 Deadlock이 발생하는 이유는, 자원전쟁! 때문에 일어나는 것이다.

자원의 사용

자원의 사용은 request -> use -> release의 순서로 이루어진다.

• 자원을 사용하려고 한다면, OS에게 CPU 가 요청한다. 이 자원을 쓰겠다 !! 하고
• 자원을 다 사용한 후에 OS에게 잘썼슴! 하면서 해당 자원을 반납.
• 그 자원 사용하려는 대기하고있는 다른 프로세스가 요청 ...

이렇게 자원을 할당받아 사용한다.

동일 자원

하지만, 동일한 자원(type...)이 2개이상 있는 경우도 있다. 예를들어 print를 두개 연결했다거나.. 램 두개 똑같은거 꼈을때나.. 같은 경우를 말한다. 이때 동일한 자원 각각을 instance라는 용어를 사용한다.

자원 할당도(Resource Allocation Graph)

이 시스템 내에 어떤 자원이 있고 그 자원이 어떤 프로세스에게 할당되었나!? 누가 또 그 자원을 할당받으려고 기다리고있나 !? 를 표현할수있는 그림.

자원: ㅁ, 프로세스: ㅇ, 할당: -> 로 표현한다.

위 그림을 보면

• Resource4는 아무런 프로세스에 의해 사용되지 않고있음
• R3는 두개의 동일 리소스를 가지고있으면서 P1, P2에게 할당중
• P2는 R1을 사용하고있고 P1은 R1을 사용하려고 기다리고있음

이렇게 자원할당도를 그렸을 때, deadlock이 발생하기 위한 필요조건은!! 자원 할당도 상에 원이!! 만들어져야한다. (circulate로 보여질 때 )

위 그림에서는 deadlock이 일어날 일이 없음! (화살표)

 

 

---

 

 

그렇다면 이렇게 발생한 교착상태를 처리하는 방법으로는 어떤것을이 있을까! 알아봅시당.

교착상태의 처리

컴퓨터가 교착상태를 handling하는 방식에는 4가지가 있겠다.

교착상태 4가지 필요조건(mutual)

• deadlock Prevention : 교착상태를 방지한다
• deadlock avoidance : 교착상태를 회피
• deadlock Detection & recovery : 교착상태 검출해서 복구
• Don't care : 무시(잘 안일어나니까)

 

1. 교착상태 방지(deadlock Prevention)

교착상태가 일어나는 것을 방지하는 것이다. 그러면!교착상태 4가지 중 하나라도 깨도록 하자 !!! 4개 다 이루어져야 교착상태가 일어날 수 있는 거니까.

1. 상호 배타(mutual exclusion)을 깨보자 - 상호배타를 깨보자는 말은 자원을 공유 가능하게 하자는 건데,, 현실적으로 불가능. 어느 한순간에 자원을 동시에 같이 쓰는 것은 사실상 불가능한일!!
2. hold & wait(보유 및 대기)을 깨보자 - 일부 가능(mutual exclusion보다는 가능) - 자원을 가지고 있으면서 다른 자원을 가지려 기다릴일을 없앤다. (ex. 식사하는 철학자 문제에서는, 젓가락 하나하나 잡는게 아니라 한꺼번에 2개 잡거나 안잡거나. - 놓아주거나-로 해결) - 단점 : 자원의 활용률이 매우 저하될 수도 있음(젓가락을 놓는경우), starvation발생가능
3. non-preemption (비선점)을 깨보자 - 자원을 선점 가능하게 (강제로 뺏을 수 있도록하자) - 현실적으로 불가능. cpu는 강제로 context switching해서 가능할수있지만, 프린터들이나.. 다른거 일반적으로 다 불가능!
4. circular wait(환형대기)을 깨보자 - 자원에 번호를 부여해서, 오름차순으로 자원을 요청하게 한다 (ex. 철학자문제에서 왼쪽-오른쪽. 이렇게 순서를 정해둔다. p1~p4는 왼쪽 -> 오른쪽이었는데 마지막p5의 경우 오른쪽 먼저->왼쪽 : 항상 같은 경우가 아니라서, circulation이 생기지 않음! ) - 단점 : 일반적으로는 컴퓨터 자원 활용률이 저하됨

주로 현실적인 경우가 hold & wait, circular wait를 깨는 방식으로 deadlock을 방지한다. 자원활용률이 저하된다고 하더라도, deadlock이 일어나면 치명적인 군사 등의 상황에서는 절대 일어나지 않도록 방지하는 것이 중요하다.

 

2. 교착상태 회피(deadlock avoidance)

OS는 application이 요청한 hw 자원들을 효율적으로 분배해주는데, 그래서 Resource manager라고도 한다. 이 방식의 기반에는 자원을 잘 못 나눠줘서 deadlock이 일어났다는 생각이 깔려있다.

예를들어, 은행에서 계속 돈을 빌려줘서 파산을 해버리는!! 그런 경우가 원인이 되었다는 생각이 기반이 되는 것이다.

 

그러면 OS가 자원을 잘못 할당해줘서 deadlock이 일어났다고 하면 안전한 할당을 해주어야 한다는 뜻인데, 좀 더 구체적으로 살펴볼 필요가 있다!

 

예를들어서, 12개의 magnetic tape가 있고, 3개의 process P0, P1, P2가 처리를 요청했다. 그리고 현재 필요한 자원은 Current Needs, process가 처리되기 위해 필요로 하는 max needs는 다음과 같다.

일 때, 우선 OS는 현재 필요로 하는 current needs에 따라 5 2 2를 나누어주게된다.

그러면 남은 자원은 12 --P0(5),P1(2),P2(2)나눠줌-> 3 --P1(2)나눠줌--> 1 --P1끝나고반납(4)--> 5 --P0(5)나눠줌--> 0 --P0끝나고반납(10)--> P2(7)나눠줌--> 3 --P2끝나고반납(9)--> 12 끝.

위 예는 이와같은 프로세스로 교착상태가 일어나지 않는다.

 

하지만! 다음과같은 경우를 따져보자.

똑같이 12개의 magnetic tape, 3개의 process P0, P1, P2가 있고, 아래와 같다.

일 때, 우선 OS는 똑같이 현재 필요로 하는 current needs에 따라 5 2 3 을 나누어준다고 치자.

그러면 남은자원은 12 --p0(5),p1(2),p2(3)나눠줌--> 2 --p1(2)나눠줌--> 0 --p1끝나고반납(4)--> 4 --> ....

P1은 끝났지만 P0, P2 프로세스는 모두 완전하게 처리되지 못한다.

 

왜냐 ? 남은 자원은 4인데, 현재 P0, P2가 처리되기 위해 추가로 필요한 자원은 각각 5, 6이기 때문이다.

이러한 경우, 진작에 P2에게 1개를 덜 나누어주었으면 p0도 p2도 프로세스를 끝내고 종료될수있었을 텐데 말이다.

 

 

다시말해, OS가 자원을 하나 덜 주었으면 되는 문제 == 자원을 잘못 할당 했던 문제.

고로, 운영체제는 자원을 할당할 때 불안전한 할당이 되지 않도록하자는 말이다.

불안전한 할당이 바로 교착상태의 원인이라고 본 것이다.

 

그러한 문제를 해결하기 위한 알고리즘으로 banker's algorithm를 사용하여 unsafe한 할당이 절대 이루어지지 않도록 해서 deadlock을 막는다.

 

3. 교착상태 검출 및 복구

지금까지는 아예 데드락이 일어나지 않도록 하는 것이다. 하지만 지금부터는 데드락이 일어나는 것을 허용은 하되, 검출되면 복구하자!! 라는데서 고안된 방식이다. 현실적으로 가장 와닿고 자주 사용하는 방식이다.

• 프로세스가 필요한대로 자원을 나누어준다
• 어쩌다가 데드락이 일어나면, 동작을 하지 않음!!
• 검출(detection) : OS가 돌면서 데드락이 발생하는지 주기적으로 검사한다 -> 😩 자주할수록 빠른발견은 되겠지만 overhead(계산, 메모리)가 심해짐
• 복구(recovery) : 주기적으로 현재의 상태를 기억해두어야함 -> 이전 상태로 돌아가려면, 자원을 강제로 선점(뺏)하여 일부 프로세스에게 할당하거나 종료시키는 방법이 있을수있다..

그래서 현실적으로 이렇게 사용한다.. 데드락이 실제로 잘 일어나지 않기 때문에 추가 부담은 있지만 ㅎㅎ.. 일어난다면 검출해서 복구하는 방식으로!

 

4. 교착상태 무시

방법이라고 하기엔 좀 ㅎㅎㅎ 그렇지만. 4가지 필요조건을 모두 만족해도 실제로 deadlock은 잘 일어나지 않기 때문에 아예 deadlock이 발생했을 경우 개인용 pc 등은.. 그냥 무시해버리고 ! 재시동! 시킨다.

---

정리

지금까지 OS가 application-HW단의 다양한 management 를 해주는데,

그중에서 특히나 중요한 Process management를 배웠고

그 중에는 cpu scheduling, process 동기화,

그리고 그 동기화 내부로는 Critical Section Problem 해결하기위한 다양한 방식. 등이 있었다!

 

앞으로는 OS가 하는 정말 중요한 memory management , IO management 방식에 대해 배운다.