[ OS 기초 ] 07. Deadlock

1. 데드락이란?
2. Starvation vs Deadlock
3. 자원의 개념
4. 자원과 데드락
5. 데드락 모델
6. 데드락 발생의 필요조건
7. 데드락 처리 : 예방(prevention), 무시(Avoidance), 감지 및 회복(Detection and Recovery)

 

00 개요

앞서 프로세스와 스레드, 스케줄링의 개념에 대해 알아보았는데 이처럼 다양한 방법과 기법을 활용하더라도 문제가 발생할 수 있다. 데드락도 이러한 문제 중 하나로 프로세스가 계속 작업을 이어나갈 수 없는 상태인데 언제 데드락이 발생하고 이 상황에서 어떤 방법으로 데드락을 해결해 나갈 것인지에 대해 살펴보았다.

 

01 데드락이란? 

데드락은 쉽게 말해 발생 가능성이 없는 이벤트를 기다리고 있는 상태를 의미한다. 프로세스의 상태 관점에서 보면,

• Blocked / Asleep 상태 : 프로세스가 특정 이벤트를 필요로 할 때 running에서 blocked/asleep 상태로 변함
• Deadlock 상태 : 마찬가지로 특정 이벤트를 필요로 해서 프로세스가 멈췄는데, 문제는 이 이벤트의 발생 가능성이 없다는 점

이런 데드락 상태에 빠지면 프로세스가 데드락 상태에 빠졌다고 하며, 시스템 내부에 데드락에 빠진 프로세스가 있을 때 해당 시스템이 데드락 상태에 빠졌다고 표현한다.

 

02 Starvation과의 비교

데드락을 공부하다보면 데드락은 '프로세스가 멈춰있는 상태'라는 점에서 앞서 스케줄링에서 배웠던 Starvation과 비슷한 것으로 착각할 수 있지만 둘은 프로세스 상태에서의 위치가 다르다.

• Deadlock : 프로세스가 작업을 하던 중(Running)에 Blocked State / Asleep 상태가 되는 것. 
• Starvation : 프로세서(cpu)할당을 기다리는 상태로 Ready State에 위치. 

 

프로세스 상태 뿐 아니라 starvation과 deadlock이 기다리고 있는 대상의 발생 가능성도 다르다. 데드락은 발생할 수 없는 이벤트나 할당받을 수 없는 자원을 기다리고 있는 상태라면 Starvation은 단순히 운이 없어서 할당을 못 받고 있을 뿐 충분히 발생할 수 있는 이벤트를 기다리고 있는 상태다.

 

03 자원의 개념

앞서 데드락이 발생 가능성이 없는 이벤트를 기다리고 있는 상태라고 했는데, 보통 이 이벤트는 자원의 할당과 큰 관련이 있다. 데드락에 대해 이해하기 위해서는 먼저 자원에 대한 개념을 이해해야, 프로세스가 자원을 어떻게 요청하고 할당받는지, 그 과정에서 데드락이 어떻게 발생하는 지를 이해할 수 있다.

자원에 대해서는 앞에서도 잠시 살펴보았었는데 그때는 간단히 하드웨어 자원, 소프트웨어 자원으로 구분했었다. 이외에도 자원은 기준에 따라 다양하게 구분할 수 있다.

• 선점 가능 여부에 따른 분류
  • 선점 자원(Preemptible resource) : 빼앗을 수도 빼앗길 수도 있는 자원
    • 프로세서 : Context switching이 발생할 때 context saving, context restoring을 통해 이전 작업 상태를 기억하고 이어나갈 수 있음
    • 메모리 : 뺏길 수 있지만 다시 돌아와서 swap device를 통해 이전 메모리 상태로 복구
  • 비선점 자원(Non-preemptible resource) : 선점될 경우 문제가 생길수 있는 자원
    • 문제를 해결하기 위해 rollback, restart 등의 작업이 추가적으로 필요함
    • disk drive, usb 처럼 뭔가 작업을 하던 도중에 컴퓨터에서 제거해버리면 내용이 날아갈 수 있음
• 할당 단위에 다른 분류
  • Total allocation resource (자원 할당 시 필요 자원 전체를 할당)
    • 코어가 하나인 cpu, disk drive 등 한 번에 하나의 자원 전체가 할당됨
  • Partitioned allocation resource (필요한 자원을 적당히 나누어 할당)
    • 메모리처럼 하나의 자원이 자신의 일부를 각 프로세스에게 할당해줄 수 있는 자원
• 동시 사용 가능 여부에 따른 분류
  • Exclusive allocation resource (한 번에 한 프로세스만 사용 가능한 자원)
    • 한 번에 한 프로세스만 해당 자원을 사용할 수 있는 경우
    • 프로세서, disk drive, memory 등
  • Shared allocation resource (여러 프로세스가 동시에 사용 가능한 자원)
    • 동시에 사용 가능한 자원으로 워드 프로그램이나 한글 문서 등이 해당(한 번에 여러 파일을 동시에 켤 수 있음)
    • 프로그램, exe 파일, shared data 등
• 재사용 가능 여부에 따른 분류
  • Serially-reusable resource (재사용 가능한 자원) : 시스템에 항상 존재하는 자원
    • 프로세서, 메모리, 디스크 드라이브, 프로그램 등
  • Consumable resource (사용 후 소멸되는 자원) : 신호(signal), 메시지(message) 등

 

04 자원과 데드락

위 자원들 중 데드락 발생과 밀접한 관련이 있는 자원은 다음 세 가지다. (사실 Consumable Resource도 관련이 있지만, CR까지 고려하면 너무 복잡해지기 때문에 다음 세 가지만 고려한다)

• Non-Preemptible Resource (비선점 자원)
• Exclusive Allocation Resource (혼자 사용하는 자원)
• Serially Reusable Resource (재사용 가능한 자원)

(생각해보면 당연하다. 선점이 가능한 자원이라면, 언제든 자원을 빼앗을 수 있기 때문에 데드락이 생기지 않고 공유 가능한 자원도 마찬가지로 자원 요청이 오면 바로 공유하면 되기 때문에 데드락이 생기지 않는다)

 

05 데드락 모델

데드락 모델은 데드락이 어떻게 발생하는지 간단히 표현하는 방법으로 그래프 모델과 스테이트 트랜지션 모델이 있다.

05-1 Graph Model
- 노드와 엣지로 구성
- 노드는 프로세스 노드, 자원 노드로 구성
- 엣지는 프로세스 -> 자원 (자원 요청 엣지), 자원 -> 프로세스 (자원 할당 엣지)로 구성
- 만약 할당해줄 수 없는 자원에 대해 요청을 보낼 경우 사이클이 형성되며 이때 데드락이 생김

05-2 State Transition Model
- 두 개의 프로세스, 하나의 자원(인데 그 자원을 2개 보유하고 있는 상황)을 가정
- 프로세스는 한 번에 하나의 자원을 요청할 수 있고, 하나의 자원을 반납한다는 전제
- 5 가지 State 가 존재

• 0 : 자원이 없는데 요청도 하지 않는 상태
• 1 : 자원이 없고, 요청을 보낸 상태
• 2 : 자원이 있는데, 요청을 하지 않는 상태
• 3 : 자원이 있는데, 또 요청을 보낸 상태
• 4 : 자원을 모두 보유하고 있는 상태

- 두 개의 프로세스가 위 다섯가지의 상태로 바뀌면서 나타날 수 있는 데드락의 상황을 찾는 모델로 어떤 상황에서 데드락이 발생할 수 있는지 찾을 수 있음

 

06 데드락 발생의 필요 조건

데드락이 발생하기 위한 필요조건은 자원 관점에서 2가지, 프로세스 관점에서 두 가지가 있고 이 조건들을 컨트롤 해서 데드락을 방지한다는 아이디어를 생각해볼 수 있다(데드락 예방)

• 자원 관점 : Non-preemptible Resource(비선점 자원), Exclusive Allocation Resource(혼자만 쓰는 자원)
• 프로세스 관점 : Hold and Wait(이미 자원이 있는 상태에서 추가적으로 자원을 요청), Circular Wait(관계 사이클)

 

07 데드락 처리법

데드락을 어떻게 받아들일 것인지에 따라 다양한 방법으로 처리할 수 있다. 예를 들어 데드락이 아예 발생할 수 없게끔 하자는 차원에서는 예방하는 방법과 무시하는 방법을 사용할 수 있고, 반대로 데드락을 받아들이되 빠르게 복구하는 감지 및 회복 방법을 활용할 수도 있다.

07-1 예방(Prevention)
예방의 핵심은 데드락 발생 필요조건을 절대 만족시키지 못하게끔 함으로써 데드락이 발생할 수 없게 만들자는 것이다. 바로 앞에서 데드락이 발생하기 위한 필요조건 4가지를 살펴봤는데 예방은 이 중 한 가지를 골라 바꿔버린다. 아래에 간단히 정리했는데, 결과적으로 예방 방법은 데드락을 확실히 예방할 수 있다는 장점이 있지만, 현실적으로 불가능하고 불필요한 자원의 낭비가 심하다는 단점이 있다.

• 자원을 선점형 자원으로 : 현실적으로 불가능. 대신 선점형과 유사하게 자원 요청을 거절당했을 경우 아예 프로세스 자체를 취소시키는 방법이 있지만(그렇게 되면 내가 현재 보유한 자원도 모두 반납) 이후 다시 처음부터 작업을 시작해야 해서 자원 낭비
• 자원을 공유 자원으로 : 현실적으로 불가능
• (일부만 할당받지 말고) 전체 할당으로 : 당장 사용하지 않을 자원까지 보유하고 있게 되어 그 자원을 필요로 하는 다른 자원들은 오래 대기해야 하는 starvation 문제 발생 가능
• (원형 대기 말고) 선형 대기 방식으로 : 자원에 순서를 부여해 순서가 증가하는 순으로만 요청할 수 있게 하면 원형 대기는 막을 수 있지만, 마찬가지로 starvation 문제 발생 가능

 

07-2 무시(Avoidance)
데드락 무시 방법의 핵심은 시스템을 계속 감시하고 있다는 데 있다. 데드락을 피해 가려면, 결국 어디서 데드락이 발생할지 바라보고 있어야 한다. 데드락이 발생하게 만들 수도 있는 자원 할당 요청을 보류시킴으로써 시스템을 데드락이 발생하지 않는 safe state 상태로 유지시켜 데드락을 피해 가는데 이 감시 과정에서 오버헤드가 발생할 수 있고, safe state가 아니더라도 데드락이 발생하지 않을 수 있기 때문에 유용한 방법이라 보기엔 어렵다.

• safe state : 모든 프로세스가 정상적으로 종료 가능한 상태. safe sequence가 존재하는 상태. 항상 정상적으로 종료 가능한 상태라기보다는, 모든 프로세스가 정상적으로 종료할 수 있는 상태가 존재한다는 의미로 safe state는 데드락이 되지 않는 상황을 보장함.
• safe sequence : 모든 프로세스가 정상적으로 종료될 수 있는 상황
• 가정 (가정 자체가 사실 유용한 가정은 아님)
  • 프로세스의 수는 고정되어 있다
  • 자원의 종류와 수는 고정되어 있다
  • 프로세스가 요구하는 자원과 최대 수량을 알고 있다
  • 프로세스는 자원을 사용한 뒤 반드시 반납한다
• 다익스트라 알고리즘 - Bankers' algorithm
  • 돈을 빌려달라는 사람들 중 누구에게 돈을 먼저 빌려줄 것인가를 판단하는 은행원의 알고리즘과 비슷
  • 빌려달라는 사람들에게 계속 돈을 빌려줘서 결과적으로 모두가 돈을 빌린 뒤 돌려줄 수 있게끔 만드는 방법을 찾는 것. 만약 어떤 사람에게 먼저 돈을 빌려줬더니, 그다음 돈을 못 빌려주는 상황으로 이어진다면 그 사람에게 게는 먼저 돈을 빌려주지 않도록 하는 것(보류)
  • 핵심 : 자원을 할당해줬다고 가정했을 때 시뮬레이션을 돌려 세이프 시퀀스가 있는지 찾음. 그래서 없다면 그 자원 할당 요청은 보류하는 방법
  • 판단 : 세이프 시퀀스가 존재하는가?
• 하버만(?) 알고리즘
  • 뱅커스 알고리즘을 프로세스와 자원이 여러 개일 경우로 확장한 개념

 

07-3 감지 및 회복(Detection and Revocery)
앞의 예방, 무시 방법은 데드락 발생 자체를 막으려는 시도였다면 감지 및 회복 방법은 데드락이 생겼을 때 이를 감지하고 회복하는 방법이다. 당연히 이를 감지하기 위해서는 주기적으로 데드락 발생 여부를 파악해야 하는데 이 과정에서 Resource Allocation Graph를 활용한다. 물론 감지 및 회복 방법도 주기적으로 감지 작업을 수행해야 하기 때문에 주기에 따라 오버헤드와 성능에 영향을 줄 수 있고, 노드 수에 따라 오버헤드가 증가할 수도 있다.

• ㅇRAG : 앞의 데드락 그래프 모델의 확장 개념.
• 노드 : 프로세스 노드, 자원 노드들이 존재
• 엣지 : 프로세스노드와 자원노드를 연결하는 엣지 (Bipartite Graph 라서 프로세스간, 자원간에는 연결되지 않음)
• 노드 > 엣지 : 자원 요청
• 엣지 > 노드 : 자원 할당
• |(a, b)| : 절댓값이 아니라 개수로 이해 (a에서 b로 가는 엣지의 개수)

RAG에서 어떻게 데드락을 발견할까? Graph Reduction을 통해서

• graph reduction : RAG에서 엣지들을 하나씩 지워나가는 방식
• 만약 모든 엣지들을 지울 수 있다면? 데드락 X
• 지워지지 않는 엣지들이 있다면? 데드락 O
• 지우는 방법은?
  • unblocked process에 연결된 엣지를 모두 지우면 됨(필요한 자원을 모두 할당받을 수 있는 엣지들)
  • 전체 자원의 개수 - 사용 중인 자원의 개수 >= 현재 요청하는 자원의 개수
  • 엣지들을 지워나가다가 지울 수 없는 엣지가 있다는 건 자원을 할당받을 수 없는 프로세스가 존재함을 의미

 

이렇게 데드락을 감지했다면 이를 회복시켜야 한다.(Recovery) 회복 방법에는 크게 두 가지가 있는데, 핵심은 결국 회복을 위해서 특정 프로세스의 종료가 발생한다는 점이다. 단, 이때 종료된 프로세스가 다시 처음부터 시작해야 하는 낭비를 막기 위해서 checkpoint restart method를 사용해 특정 지점의 문맥을 저장시켜 놓고 종료가 될 경우 rollback 하는 방법으로 context restoring을 한다.

• Process Termination (프로세스 종료시키기)
  • 어떤 프로세스를 종료시킬 것인가? Cost Model에 따라
  • cost model에는 프로세스 우선순위, 종류, 총 수행 시간, 남은 수행 시간 등을 고려할 수 있음
  • Lowest-termination cost process first : 간단한 방법이며 오버헤드도 낮지만, 해당 프로세스 문제가 아니었다면 데드락은 해결되지 않음
  • Minimum cost recovery : 회복 비용이 최소가 되는 경우를 선택하는 경우로 비용을 모두 계산해야 해서 복잡하고 오버헤드가 클 수 있다. (k개의 프로세스라면 2의 k승만큼의 오버헤드가 생김)
• Resource Preemption (자원 선점해 버리기)
  • 필요한 자원을 사용하고 있는 프로세스들(r)로부터 자원을 뺏어오는 방법으로 뺏겨야 하는 프로세스는 억울할 수 있고 데드락이 아닌 프로세스가 종료되어버릴 가능성도 있음
  • 선점 비용을 고려하는 과정에서 O(r)만큼의 오버헤드가 생김

 

 

**  KOREATECH 무료 OS강의(클릭) 학습 후 나름대로 이해한 뒤 정리한 내용입니다. **

[Course] Operating System (CPA310) - 운영체제 강의