7. 데드락(Deadlocks)

Deadlock

일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

데드락이 생기는 이유?

자원을 가지고 있으면서 내가 못가진 자원을 서로 요구할때 데드락이 발생한다

Resource(자원)

• 하드웨어, 소프트웨어 등을 포함하는 개념
• (예) I/O device, CPU cycle, memory space, semaphore 등
• 프로세스가 자원을 사용하는 절차
  • Request, Allocate, Use, Release

데드락 발생의 4가지 조건

• Mutual exclusion (상호 배제)
  매 순간 하나의 프로세스만이 자원을 사용할 수 있음
• No preemption (비선점)
  프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
• Hold and wait (보유대기)
  자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
• Circular wait (순환대기)
  자원을 기다리는 프로세스간에 사이클이 형성되어야 함

데드락의 처리 방법

Deadlock Prevention

• 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
• Mutual exclusion
  • 공유해서는 안되는 자원의 경우 반드시 성립해야함
• Hold and wait
  • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다
  • 방법 1. 프로세스시작 시 모든 필요한 자원을 할당받게 하는 방법
  • 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
• No preemption
  • process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
  • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다
  • state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)
• Circular wait
  • 모든 자원 유형에 할당 순서를 정해진 순서대로만 자원 할당
  • 예를 들어 순서가 3인 자원 Ri를 보유중인 프로세스 순서가 1인 자원 Rj을 할당 받기 위해서는 우선 Ri를 release해야 한다

→ Utilization 저하, throughput 감소, starvation 문제

Deadlock Avoidance

• 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당. 다시 말해 데드락으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임
• safe state
  • 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
• safe sequence
  • 프로세스의 sequence <P₁,P₂, … ,P𝑛>이 safe하려면 Pᵢ(1≤i≤n)의 자원 요청이 “가용 자원 + 모든 P𝘫(j<i)의 보유자원”에 의해 충족되어야 함
  • 조건을 만족하면 다음의 방법으로 모든 프로세스의 수행을 보장
    • Pᵢ의 자원 요청이 즉시 충족될 수 없으면 모든 P𝘫(j<i)가 종료될 때까지 기다린다
    • Pᵢ₋₁이 종료되면 Pᵢ의 자원요청을 만족시켜 수행한다
• 시스템이 safe state에 있으면
  ⇒ no deadlock
• 시스템이 unsafe state에 있으면
  ⇒ possibility of deadlock
• Deadlock Avoidance
  • 시스템이 unsafe state에 들어가지 않는 것을 보장
  • 2가지 경우의 avoidance 알고리즘
    • Single instance per resource types
      • Resource Allocation Graph algorithm 사용
    • Multiple instances per resource types
      • Banker’s Algorithm 사용

Banker’s Algorithm(은행원 알고리즘)

은행원 알고리즘 : 은행이 대출해주는 상식적인 방법의 알고리즘

은행에 돈이 1000만원 있을때 사업가 1이 500을 빌리고 사업가 2는 400을 빌려준다. 그럼 은행에는 100만원이 남아있다. 시간이 지나서 은행은 사업자 1에게 돈을 갚으라하는데 사업가 1이 200만 더 빌려주면 갚는다 한다. 은행은 100만원밖에 없기때문에 2에게 돈을 받아서 1에게 빌려주려한다. 근데 2도 갚을 수 없고 200만 더 빌려주면 벌어서 갚는다고한다. 은행은 누구에게도 돈을 빌려주지도 못하고 돌려받지도 못하는 교착상태에 빠진다.

은행은 이런 상황을 피하기 위해 사업가들에게 돈을 빌려 줄 때 은행의 여윳돈과 사업가들에게 빌려준 돈들을 보고 대출 가능한 상황(안전상태)인지 확인하고 빌려주는데 이것을 은행원 알고리즘이라고 한다

운영체제에서 은행원 알고리즘을 구현하는 방법

운영체제는 프로세스들에게 자원을 할당하기 전에 자기가 가지고 있는 전체 자원의 수를 알고 있어야 한다. 이를 시스템의 총 자원이라 부르겠다. 그리고 프로세스들은 각자 자기가 필요한 자원의 최대 숫자를 운영체제에게 알려줘야한다. 이걸 최대 요구 자원이라고 부르겠다.

안정상태를 살펴보면 운영체제가 가지고 있는 자원의 수, 즉 시스템의 총 자원은 14개다. 그리고 프로세스인 P1의 최대 요구자원은 9개이고 현재 5개가 할당된 상태라 가정한다. P2의 최대 요구자원은 6개이고 현재 4개가 할당됐다. P3의 최대 요구자원은 4개이고 현재 3개가 할당됐다. 모두 합치면 12이고 시스템의 총 자원은 2개가 남는다. (사용 가능한 자원). 여기서 은행원 알고리즘은 각 프로세스가 현재 요구할 수 있는 요청이 예상되는 자원을 구한다. P1의 최대 요구 자원은 9개이고 요청이 예상되는 자원은 4, P2 =2, P3=1. 여기서 p2에게 2개를 빌려주고 p2가 작업이 끝나면 자원 6개를 돌려받는다. 그럼 p1과 p3가 요청한 자원을 전부 할당할 수 있다.

불안정 상태를 살펴보면 운영체제가 사용 가능한 자원이 1개이고 요청이 예상되는 자원인 2개씩을 충족할 수 없다.

비용이 비싸고 비효율적인 은행원 알고리즘

Deadlock Detection and recovery

• Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 Deadlock 발견 시 recover
• Deadlock Detection
  • Resource type당 single instance인 경우
    • 자원 할당 그래프에서의 cycle이 곧 deadlock을 의미
  • Resource type당 multiple instance인 경우
    • Banker’s algorithm과 유사한 방법 활용
• Wait-for graph 알고리즘
  • Resource type 당 single instance인 경우
  • Wait-for graph
    • 자원할당 그래프의 변형
    • 프로세스만으로 node rntjd
    • P𝑗가 가지고있는 자원을 P𝘬가 기다리는 경우 P𝘬→P𝑗
  • Algorithm
    • Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
    • O(n²)

Deadlock Ignorance

• Deadlock을 시스템이 책임지지 않음
• 데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
  • Deadlock이 매우 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드 일 수 있음
  • 만약 시스템에 데드락이 발생한 경우 비정삭적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처
• UNIX를 포함한 대부분의 OS가 채택