교착상태(deadlock)와 그 해결방안을 알아보자. OS2016. 9. 14. 03:54
심심하니 학창시절 배웠던 전공에 대해 살짝 리뷰.
되도록 쉽게... 초딩...은 좀 무리고, 중딩 수준에서 이해할 수 있도록 설명해 보는 것이 이 글의 목표!
배경 : 다중프로그래밍 환경의 등장!
데드락을 제대로 이해하려면 시스템의 발전 역사를 살짝 봐야 한다.
초기 컴퓨터는 한번에 하나만의 작업을 할 수 있었다.
그런데 컴퓨터가 발전하면서 한번에 여러 작업을 하고 싶어졌다. 예를 들면 웹서핑을 하면서 음악을 듣는 것을 동시에 하고 싶은 거다.
근데 "CPU가 하나인데 어떻게 동시에 처리하지?"라는 문제가 있었고,
똑똑한 공학자들은 컴퓨터는 무지 빠르니까 두가지 일을 이거했다 저거했다를 엄청 빨리 반복하면 사람의 지각능력으론 동시에 하는 것처럼 보이지 않을까?라는 아이디어를 냈다.
그래서 나온 것이 멀티프로세싱과 멀티쓰레딩이다.
데드락은 바로 이런 다중프로그래밍 환경에서 여러 프로세스(혹은 쓰레드)가 간섭하면서 생기는 문제를 말한다.
그럼 DeadLock(교착상태)가 뭐냐?
아주 쉽게 얘기하면 "두개 이상의 프로세스(혹은 쓰레드)가 서로 끝나기를 기다리는 상태"다. 왜 기다려야 하냐면 자원(쉽게 말하면 변수 같은 것들)을 공유해서 쓰기 때문이다.
데드락을 이해하기 쉽게 예를 들어 보자. 선생님이 철수랑 영희한테 청소를 시켰다. 철수는 청소도구함에서 빗자루를 챙기고, 영희는 쓰레받기를 챙겼다. 이제 청소를 시작하자. 철수가 빗자루질을 하고 그걸 담으려고 하는데 쓰레받기가 없다. 영희가 다 쓰길 기다려야겠네?라고 생각하며 기다린다. 영희는 영희대로 철수가 빗자루질을 다 해야 내가 청소를 마칠 수 있겠구나?라고 철수가 빗자루를 다 쓰길 기다린다. 쓰레받기를 손에 꼭 쥔 채 말이다. 문제의 본질이 보이는가? 얘네들 이제 집에 못가게 생겼다...라는걸 이해했으면 데드락을 제대로 이해한 거다. |
그럼 이런 문제를 해결하려면 내가 알아야 할 것은 대체 뭔가?
1. 데드락의 발생 조건을 정확히 알아야 한다.
2. 데드락을 예방(prevention)
3. 데드락을 회피(avoidance)
이제 이것들을 보자.
데드락의 발생 조건
똑똑한 교수님이 데드락 발생조건을 명확하게 정리했다.
아래 4가지 조건을 동시에 충족하면 데드락이 발생한다는 얘기다.
1. Mutual Exclusion(뮤텍스 - 자원에 대한 동시접근 불가)
한번에 여러 프로세스(혹은 쓰레드)가 한 자원에 접근하지 못하도록 막음.
내가 쓰고있는 동안은 때 남이 못쓴다는 얘기다.
(만약 동시에 자원 접근이 가능하다면 애초에 다른프로세스가 다 쓰길 기다릴 필요가 없겠지?라고 이해하면 된다)
2. Hold and Wait(점유하고 기다리기)
자원을 가지고 있는 상태에서 다른 프로세스가 쓰는 자원(변수 같은 것)을 반납하길 기다리는 상태다.
(위 예제로 보면 영희가 쓰레받기를 손에 꼭 쥐고(Hold) 철수가 다 쓰기를 기다리는(Wait) 것이라고 이해하면 된다)
3. No Preemption(자원 뺏어오지 못함)
이거 "선점불가"라고 번역한 사람......... 대체 누구냐? 찾아가서 꿀밤 한대 때려주고 싶다.
요상한 번역 때문에 이거 배울때 대체 뭔소리?라고 생각한 적이 있다.
이건 쉽게 말하면 "다른 프로세스가 이미 점유한 자원을 강제로 뺏어오지 못함"을 말한다.
번역에서 나온 "선점"이란 말은 시간상의 선점이 아니라 우선권이 우선한다는 뜻의 "선점"임을 잊지 말자.
4. Circular Wait(순환 형태로 대기함)
프로세스가 뭔가를 하려고 다른 프로세스를 기다리고 있고... 그 프로세스는 또 다른걸 기다리고... 이렇게 쭉 추적하다보니 마지막에 가선 결국 내가 나오는 상황.
결국 내가 일을 하려고 보니까 내가 일을 끝마쳐야만 수행이 가능하다는 모순적인 상황!
그럼 이 데드락을 해결하려면?
데드락의 예방(Prevention)
위 4가지 조건은 동시에 충족돼야 데드락이 발생한다. 그러므로 그 중 하나라도 발생하지 않도록 시스템 차원에서 막아버리면 해결된다.
근데 이 방법은 대부분 자원이 낭비되는 경향이 있다. 그리고 애초에 발생 가능성을 원천봉쇄하려면 성능이 나빠지거나 또 다른 문제를 발생시킬 수 있다.
데드락의 회피(Avoidance)
교착상태의 원칙적인 발생 가능성(조건)은 그냥 냅두고, 발생을 막는 알고리즘을 적용해서 해결하는 방법.
은행원 알고리즘(프로세스가 자원을 요구하는 시점에 자원을 할당해도 안전한지를 검사하여 데드락을 막는 방법)
자원할당 그래프 알고리즘(아직 이건 모름. 추후 찾아볼 예정)
데드락의 탐지(Detection)와 회복(Recovery)
교착상태가 발생하는 것을 아예 막지조차 않음. 발생하면 그때서야 해결하겠다는 방법.
데드락 무시
거의 무시해도 좋을 확률로 데드락이 발생한다고 판단되면 그냥 무시한다.
왜냐면 데드락 문제는 해결하려면 성능상 손해를 봐야 하기 때문.
안정성과 성능을 고려해서 데드락 문제를 해결할지 말지를 정하자.
참고 문서
https://ko.wikipedia.org/wiki/%EA%B5%90%EC%B0%A9_%EC%83%81%ED%83%9C
http://barunmo.blogspot.kr/2013/06/deadlock.html
http://wingsofgod.tistory.com/entry/%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C
