06. Deadlock & Starvation

충남대학교 컴퓨터공학과 류재철 교수님의 "운영체제 및 실습" 강의를 필기한 내용입니다.

다소 잘못된 내용과 구어적 표현 이 포함되어 있을 수 있습니다.

Deadlock §

• 일련의 프로세스가 영원히 블락먹는 상태를 의미한다
• 어떤 프로세스의 블락상태가 풀리는것이 다른 프로세스의 실행에 달려있는데 이 다른 프로세스조차 블락을 먹어 둘다 영원히 블락을 먹게 되는 경우 이다
• 예를 들면 이런 상황이다 - 프로세스 P가 D → T의 순서로 리소스를 먹고 Q는 T → D의 순서로 리소스를 먹을때 만약에 P가 D를 먹고 Q로 context change가 일어나 얘가 T를 먹으면 P도 자원을 먹지 못해 블락먹고 Q도 자원을 먹지 못해 블락을 먹으므로 둘 다 블락을 먹게 된다 - 이러한 경우에는 무조건 deadlock을 먹는건 아니므로 deadlock possible이라고 표현한다 - 즉, 무조건 deadlock이 발생하는건 아니지만 아다리가 맞으면 deadlock이 발생하게 되는 경우를 말한다
• 이러한 경우에 첫번째로는 먹는 순서를 일치시킴으로 해결할 수 있다 - Q도 D → T의 순으로 자원을 먹으면 P가 D를 먹고 context change가 일어나도 Q는 D를 먹지 못하므로 T도 먹을 수 없어 Q는 블락을 먹어도 P는 블락을 안먹어 P가 자원을 뱉은 후 Q가 실행될 수 있게 되는 것이다

Consumable 리소스의 deadlock §

Reusable, Consumable §

• reusable : 프로세스 하나가 먹고 뱉으면 다른 프로세스도 사용할 수 있는 자원 - 대표적으로 cpu가 여기에 해당한다
• consumable : 하나의 프로세스가 먹고 나면 뱉어도 없어지기 때문에 다른 프로세스가 이용할 수 없는 자원 - interrupt처럼 처리하고 나면 없어지는 자원을 얘기한다

Deadlock of Consumable resources §

• 메세지 송수신에서의 deadlock

• 보면 서로 메세지를 받아서 자신의 메세지를 보내는 과정을 거치는데 순서가 동일하다면 둘 다 메세지를 받아야 전송을 하므로 둘 다 블락을 먹게 된다 - 송신을 해야 반대편이 블락을 안먹는데 송신을 하려면 수신을 해야되고 그건 상대방도 동일하므로

Deadlock of reusable resources §

• 메모리 공간 할당에서의 deadlock

• 예를들어서 메모리 총 공간이 200일때 프로세스 P는 80 → 60의 순서로 메모리 할당을 요청하고 프로세스 Q는 70 → 80의 순서로 메모리 할당을 요청할때 만약 P가 80을 먹고 context change가 일어나서 Q가 70을 먹으면 남은 공간은 50이므로 둘 다 원하는 메모리를 전부 먹지 못해 블락을 먹게 된다
• 이렇듯 deadlock은 context change가 일어나지 않으면 일어나지 않지만 재수없게 context change가 일어나게 되면 일어나게 되는 경우가 많다
• 프로세스 둘 중 하나의 자원을 뺏던가 아예 kill해버리는 방법으로 자원을 뱉게 하면 해결될 수 있다

그림으로 deadlock 이해하기 - Resource Allocation Graph §

• 동그라미가 프로세스, 네모가 자원, 네모 안의 검은 점이 이용할 수 있는 자원이다
• 그리고 동그라미로부터 뻗어나오는 화살표가 자원 요청이고, 점으로부터 뻗어나오는 화살표는 자원 할당을 나타낸 것 이다
• 왼쪽의 경우를 보면 P1이 Ra의 자원을 요청하나 이미 P2가 먹은 상태이다. 반면에 P2는 Rb의 자원을 요청하나 얘는 이미 P1이 먹은 상태이다. 따라서 계속 waiting하므로 deadlock이 걸리게 되는 것이다 - 이런식으로 리소스를 일부 먹고 기다리는걸 hold & wait라고 한다
• 반면에 오른쪽의 경우 P1은 Ra의 자원을 요청하는데 이용가능한 자원이 있으므로 문제없이 먹을 수 있다. 그리고 P2의 경우에도 Rb의 자원을 요청할때 이용가능한 자원이 있으므로 먹을 수 있다. 따라서 이 경우에는 deadlock이 걸리지 않게 된다

Deadlock의 필요조건 §

• Mutual Exclusion : 자원이 상호 배타적으로 접근해야만 정상적으로 작동할 때어떤 자원이 mutual exclusion하지 않으면 그냥 다 먹을 수 있으므로 deadlock이 걸리지 않는다
• Hold & wait : 프로세스가 자원을 하나 먹고 다른 자원을 먹으려고 기다릴 때 - 어떤 프로세스가 먹고 기다리는게 아닌 먹고 다시 뱉으면 다른 프로세스가 와서 사용할 수 있으므로 deadlock이 걸리지 않는다
• Circular wait : 자원의 요청, 할당관계 그래프가 화살표를 따라가봤더니 원형으로 그어질 때 - 원형으로 그어지지 않고 프로세스가 전혀 다른 리소스를 요청하는 그런 경우에는 한 프로세스가 블락을 먹어도 그걸 풀어줄 다른 프로세스가 다른 자원을 이용해 블락을 먹지 않게 되므로 블락먹은 프로세스도 풀리게 된다
• No pre-emption : 프로세스들이 우선순위가 동일해 우선순위에 의한 작동순서를 정할 수 없고 프로세스의 자원을 뺏어오는것도 불가능할때 - 프로세스 두개가 deadlock을 먹었는데 하나의 우선순위가 높아 나머지 하나를 죽여버리면 deadlock이 풀리기 된다
• 이 넷중에 하나만 만족하지 않아도 deadlock이 걸리지 않는다 - 즉, 이중에. 일부만 만족하는 것이 무조건적으로 deadlock을 야기하는건 아니다 - Circular wait의 상태여도 deadlock이 무조건 걸리는건 아니다 이말이야 - 원이 있어도 Mutual exclusion하지 않다던지 하는 연유로 프로세스 종료 시나리오가 완성된다면 deadlock이 아닌 것이다
• 반면에 circular wait이면 반드시 deadlock이 되는 상황이 있다 - 연관되어 있는 모든 자원이 mutual exclusion, 즉, 한번에 한놈만 접근할 수 있을 때에는 circular wait이 일어나면 반드시 deadlock이 걸리게 된다

Deadlock의 해결 §

정보가 있는 경우 §

• 여기서의 정보라는 것은 프로세스가 미래에 어떤 자원을 요청할지에 대한 정보나 자원이 mutual exclusion하다 등의 정보를 말한다. 나중에 프로세스가 어떤 자원을 요청할지를 미리 안다면 지금 내가 누구한테 자원을 줬을때 이것이 결국에는 deadlock을 야기할지 안할지를 알 수 있기 때문
• Avoidance : 자원의 요청과 할당관계에서 위와 같은 정보가 OS에 전달된다면 OS는 이 상황을 피하도록 대비를 할 수 있다 - 미래를 알고 피하는 것 - 그래서 OS는 deadlock posible 한 상황이면 리소스를 아예 할당해주지 않는다

정보가 없는 경우 §

• Prevention : 이러한 정보가 없어도 저 4개의 필요조건중 하나라도 피할 수 있도록 잘 조정하는 것을 의미한다 - 미래는 모르지만 미리미리 방지하는 것
• Detection & Recovery : 프로세스가 deadlock에 걸렸는지 아닌지를 계속 확인하고 걸렸으면 여기에서 빠져나오도록 일부를 kill한다던가 하는 등의 복구작업을 하는 것을 의미한다 - 여기서 deadlock을 탐지하는 방법은 프로세스들을 계속 관찰하면서 이 프로세스가 종료될 수 있는 시나리오가 있느냐를 확인하는 것이다 - 따라서 deadlock인것처럼 보여도 연관된 프로세스가 순차적으로 종료될 수 있는 그런 시나리오가 존재한다면 이것은 deadlock이 아닌 것이다

Prevention strategy §

• 아까도 말했지만 4가지 조건들을 회피해 deadlock이 걸리지 않게 하는 것
• 간접(Indirect) 적인 방법 - Circular wait외의 나머지(Mutual exclusion, Hold&Wait, No pre-emption) 이 세가지중 하나라도 발생하지 않도록 조치하는것
• 직접(Direct) 적인 방법 - Circular wait가 일어나지 않게 조치하는 것
  1. Mutual exclusion의 경우에는 리소스를 상호배타적으로 할당하지 않는 것이다
     • 하지만 리소스의 특성상 이놈이 상호배타적으로 할당해야만 하는놈인지 아니면 상호배타적으로 안해도 되는지 를OS가 알기가 힘드므로 쉽지 않다
  2. Hold&wait은 방지가 가능하다 - 프로세스가 시작하면 여기에 필요한 자원들을 중간에 끊지 않고 한번에 다 할당시킨다(serial하게)
     • 하지만 여기에는 몇가지 단점이 있다
     • 프로세스가 시작하면 거기에 필요한 자원들을 모두 할당하므로 이놈이 사용하지 않을 때 에도 먹고 있게 되어 비효율적이 될 수도 있다
     • 또한 어떤 리소스가 필요한지 실행시점에 다 알 수 없는 경우도 있다
     • 따라서 OS는 별로 선호하지 않는 방식이다
  3. No pre-emption : 우선순위가 같은 경우에 OS가 프로세스 하나의 편을 일방적으로 들어서 나머지 프로세스의 리소스를 다 뺏어버리는 방법
     • 하지만 리소스를 뺏어버리면 그 프로세스는 그만큼 딜레이되는 것이므로 형평성의 문제가 있어 OS입장에서는 간편하지만 문제가 생길 수도 있다
  4. Circular wait : 리소스 할당에 원칙을 매기는 것으로 해결할 수 있다
     • 예를들면 오름차순으로 먹고 요청하는 것은 가능하지만 내림차순은 안된다고 했을 때 circular wait가 일어나려면 반드시 한번은 내림차순으로 가야되므로 이놈에게 리소스를 할당해주지 않으면 된다
     • 구체적인 예를 들어보면 프로세스 P가 R1먹고 R2요청하는 것은 오름차순이므로 허용, 다른 프로세스 Q가 R2먹고 R1 요청하는 것은 내림차순이니까 안된다고 했을 때 Circular wait이 성립하지 않으므로 deadlock이 발생하지 않는다
• prevention strategy는 아주 보수적인 해결방법이다 - avoidance와 다르게 미래를 잘 알지 못하는 상황에서 deadlock이 걸릴지 안걸릴지를 판단해야되므로 보수적으로 할 수밖에 없다

Avoidance Strategy §

Deadlock이 걸리지 않는 경우 §

• Claim matrix : 프로세스가 종료되는데 필요한 리소스들의 갯수
• Allocation matrix : 현제 프로세스들에게 할당된 리소스의 갯수
• C - A : 프로세스가 종료되기 위해 더 필요한 리소스의 갯수
• Resource vector : 리소스를 동시에 할당받을 수 있는 프로세스의 통 갯수 - 아까의 allocation graph에서 검은 점의 갯수라고 보면 된다
• Available vector : 현재 프로세스들이 할당받은 다음 더 할당받을 수 있는 프로세스의 갯수 - 잔여분
• Claim matrix와 Resource vector를 아까말한 정보라고 하는 것이다 - 프로세스가 얼마나 자원을 필요로 할 지, 자원을 얼마까지 할당해줄 수가 있는지에 대한 정보가 존재하기 때문에 OS가 Avoidance strategy를 사용할 수 있는 것
• 여기서 보면 P2가 R3를 하나 필요로 하는데 R3도 한개가 남으므로 줄 수 있다. 따라서 얘가 종료되고 남은 리소스를 전부 반환하면 Available vector는 623이 될 것이다. 이제 얘네들을 가지고 P1, P3, P4를 하나씩 끝내보면 모두 종료되는 시나리오가 존재하므로 이 경우에는 deadlock이 걸리지 않을 수 있다

Deadlock이 걸리는 경우 §

• 윗쪽의 상태를 보면 아직 종료 시나리오가 존재한다 - P2에게 102를 할당해주면 P2가 종료되며 순차적으로 종료될 수 있기 때문 - 이렇게 종료 시나리오가 존재하는 상태를 safe state라고 한다
• 하지만 P1에게 101을 할당해주면 아래와 같이 종료 시나리오가 나오지 않게 된다
• 왜냐면 아래쪽을 보면 모든 프로세스가 R1을 필요로 하는데 R1의 잔고가 하나도 남아있지 않은 상황이다. 따라서 프로세스 종료 시나리오가 나오지 않기 때문에 이 경우 추후에 deadlock이 발생하게 된다
• 하지만 아직은 deadlock이 아니다 : 아직 P1이후로는 아무도 리소스를 요청하지 않았기 때문에 deadlock이라고는 할 수 없는것 - 즉, 아직 할당해줄 수 있는 자원이 남았기 때문에 이 범위 안에서 리소스를 요청하게 되면 그것을 수락할 수 있기 때문이다
• 그래도 worst case를 가정했을 때 - 만약 저 프로세스들 중 어느 누구라도 R1을 요청하는 상황 - deadlock이 걸리게 되고 따라서 종료시나리오가 나오지 않는 것이라고 판단하는 것이다 - 이렇게 deadlock은 아니지만 종료 시나리오가 나오지 않는 그러한 상태를 unsafe state라고 한다
• 따라서 OS는 P1한테 101을 주면 unsafe state이 걸린다는것을 알 수 있으므로 P1이 101을 요청해왔을때 이것을 거절하는 식으로 deadlock을 avoid할 수 있다
• 이렇게 요청이 들어왔을때 unsafe state로 바뀌는지를 계산해 할당여부를 결정하는 식으로 avoid하게 된다
• 이렇게 할당할때 조심스럽게 다 계한하고 위험요소가 없을 때 할당하는 것(worst case를 판단해서 할당여부를 결정하는 것)을 banker’s algorithm이라고 한다
• 하지만 프로세스가 얼마만큼의 리소스를 필요로 하는지 알기 어렵기 때문에 - 저 claim matrix와 resource vector를 알아내는게 쉬운일이 아니기 때문에 avoid를 하는 것은 쉬운일이 아니다
• avoidance는 미래를 알고 대비하는 것 이기 때문에 보수와 방임의 중간정도이다

Detection strategy §

• Detection의 경우에는 저 Claim matrix를 알 수가 없고 단지 Request matrix만 알고있는 상황이라는 점에서 Avoidance와는 좀 다르다 - 여기서 request matrix는 앞으로 더 요청할 수도 있지만 일단 지금은 요정도 요청한다이런 의미의 표이다
• 그래서 Request matrix와 Available vector를 가지고 프로세스 종료 시나리오를 짜봣을때 시나리오가 안나오면 deadlock이라고 판단하게 되는 것 이다 - 시나리오 짜는 방법은 저 request matrix 이후 더 이상 요청을 하지 않고 종료된다는 가정 하에 종료 시나리오를 짜는 방법이다

Recovery strategy §

• 프로세스들을 다 죽일수도 있지만 그럼 처음부터 다다시 해야되므로 효율적이지 않다
• 방법1 : git reset HEAD^마냥 그 주기적으로 detection을 하고 이전 detection했을때의 상태를 저장해놨다가 deadlock이 발생하면 이 지점으로 다시 돌아가는 방법으로 해결할 수도 있다
• 방법2 : deadlock이 풀릴때까지 프로세스를 하나씩 뱉게 하거나 죽여버리는 것이다
• Detection & Recovery는 방임형 해결방법이다 - 걍 냅뒀다가 deadlock이 발생하면 해결하는 것 이므로

밥먹는 철학자 문제 §

• 철학자는 스파게티를 먹는데 2개의 포크가 필요하다
• 포크 하나를 동시에 두명이 들 수 없다
• 이 경우 deadlock이 걸리는 상황은 모든 사람이 왼쪽(혹은 오른쪽)의 포크만 들고 기다리는 상태이다
• 해결법1 - 한번에 4명에게만 포크를 들 수 있는 자격을 준다
• 해결법2 - 한번에 짝수번째/홀수번째에게만 포크를 들 수 있는 자격을 준다
• 해결법3 - 포크를 드는 순서를 다르게 한다 - 기준을 한명 정해서 그사람을 기준으로 짝수번째 위치의 사람은 왼쪽거를 먼저 들고, 홀수번째의 사람은 오른쪽꺼를 먼저들게 하는 식으로 하면