본문 바로가기

별걸다하는 IT/운영체제 OS

[운영체제OS]교착상태(deadlock데드락)의 발생조건(necessary condition-필요조건)

[운영체제(OS) 목차 &책 추천]

데드락(deadlock) 발생 조건


저번 포스트에서는 데드락의 개념에 대해서 살펴보았어요

이 데드락이라고 하는 것을 formal하게 정의를 하고 있는데 이를 수학적으로 증명을 해놨습니다

이번 시간에 설명할 것은 Deadlock을 발생시킬 4가지 필요조건이예요



Necessary Conditions


고등학교 수학시간 때 배웠던 충분 조건과 필요조건! 4가지 필요 조건이란 이 4가지 조건이 동시에 다 만족을 하면 교착 상태에 빠질 수 있다는 것입니다. 즉 데드락이 발생하기 위한 필요조건이예요! (4 conditions <- deadlock )

조심해야 할 것은 4가지 조건이 다 맞았다고 해서 꼭 교착상태가 일어나는 것은 아닙니다. 

교착상태가 일어나면 이 4가지 조건이 꼭 만족된다는 것이죠! 4가지 조건이 발생되면 deadlock이 발생할 수 있다는 것




1. Mutual Exclusion = 상호 배제

프로세서들이 자원을 배타적 점유, 다른 프로세서들이 자원 사용 불가, 한 번에 한 프로세스만이 자원 사용 가능


At least one resource must be held in a nonsharable mode; that is, only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released

이게 무슨 뜻이냐! 쉽게 말하면 상호 서로를 배제한다 => 남 안주고 공유하지도 않고 오로지 나만 쓰는 그런 상황입니다.

나 빼고 다 배타적인거죠. 당연히 나만 쓰는 그런 상황이 일어나야지만 데드락이 발생할 수 있겠죠!


2. Hold and wait = 점유와 대기.

부분 할당, 다른 종류의 자원을 부가적으로 요구하면서, 이미 어떤 자원을 점유하고 있음


즉 내가 어떤 공유된 자원(shared data)를 가진 상태에서 또 다른 것을 요구할 때 데드락이 발생되는 거지(욕심쟁이)

밥먹는 철학자 문제에서 예를 들자면, 왼쪽 젓가락을 집은 상태에서 오른쪽 젓가락을 집으려고 봤더니 누가 쓰고 있는 것! 젓가락을 두개나 가지려고 하다니..! 다른거 쓰려면 하나 내려놔!! 내꺼 있는데 다른거 탐내는 것이 hold and wait입니다.


3. No preemption =비선점

자원들은 그들이 점유하고 있는 프로세스로부터 도중에 해체되지 않음.

앞의 데드락 개념 포스트에서 예시로 들어진 교통 체증 문제에서 보면, 몇 차만 후진해서 양보해주면 데드락이 발생하지 않는데, 내 것은 양보하기 싫은거야. 그러니까 오도 갈수 없는 상태에 빠지는거죠

철학자 문제에서도 또한, 자원을 내가 가졌어, shared data를 내가 가졌는데, 더 이상 진행이 안되니까 그 shared data를 내려놓으면 그것이 preemption이고 내려놓지 않는 것이 no preemption!

Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task


4. Circular Wait =환형대기

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


잘 생각해보면 실제로 데드락은 일직선일때는 발생하지 않아요

왜냐! 일직선으로 만약 A B C D가 있으면 D가 C에게 요청하고 C가 B에게 요청하고 B가 A에게 요청하고..

교착 상태는 서로에게 요구해서 서로가 기달려야하는데 일직선이면 서로가 아니기 때문! 발생할 일이 없겠죠?!

서로 맞물리는 형태가 되려면 환형형태가 되어야하기 때문에 교착상태가 발생하면 다 환형형태일 수 밖에 없는 것입니다.

즉 원형으로 이루어져있어야 deadlock problem이 발생합니다.


A set {P0, P1, ... , Pn} of waiting processes must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, ... , Pn-1 is waiting for a resource held by Pn, and Pn is waiting for a resource held by P0


이전 포스트에서 예시로 들었던 교통 체증 또한 데드락이 발생했으니 필요조건들을 만족하고 있어야겠죠?



1. Mutual exclusion - 하나의 차량은 그 순간에 하나의 구간만 차지할 수 있어요. (충족)

2. Hold and wait - 각각의 차량들이 도로에서 하나의 구간을 차지하면서 나아가기를 기다리고만 있습니다. (충족)

3. No preemption - 하나의 구간이 양보될 수 없는 상황(선점할 수 없는 상황), 차량을 뺄 수 없는 상황이죠

4. circular wait - 딱 봐도 서로 맞물리는 원형 형태를 띄고 있죠.


다음 포스트에서는 데드락을 처리하는 4가지 방법에 대해서 진행하겠습니다!


도움이 됐다면 공감 꾹 

공감과 댓글은 지식 공유의 힘이 됩니다 ;)



  • 코동이 2019.06.10 04:35

    너무 잘 보고 있어요. 해드릴 수 있는 게 광고를 클릭하는 것 뿐이네요 ㅜㅜ 감사합니다.^^

  • Maddawgs 2019.10.01 20:38

    아름다운 설명 너무나 감사드립니다. 최고에요 정말.

  • 익명이 2019.11.25 21:31

    필요조건에서 의문점이 있습니다! 저는 1-3까지가 필요조건 4까지 발생하면 필요충분조건으로 알고잇는데 음..
    찾아보니 저는 환형대기가 1-3의 결과에 의해서 발생하고 그 상호작용의 결과로 해결불가능한 환형대기가 발생했다라고 배웠거든요...뭐가 맞는걸가요..