chapter 8 (Deadlocks)

Deadlock

• kill , rollback 기법을 사용하지 않는 이상 절대 프로그램이 수행되지 않음

• 위 그림에서 A 와 B 는 평생 멈춰있음
• os 는 기본적으로 deadlock 에 대한 handling 을 하지 않음

해결 방법

Resource allocation graph 에 대한 개념을 알아야 함

• DeadLock prevention
• DeadLock avoidance
  • 도망가버리는 것 ex) 오에스 학점 F 안맞고 싶으면 그냥 듣지않음
• DeadLock detection
• DeadLock recovery

필요 조건 (Necessary Condition)

• Mutual exclusion (무조건 갖춰야 함)
• Hold and wait (확정할 수 없음)
• No preemption (무조건 갖춰야 함)
• Circular wait
  • resource allocation graph 에 cycle 이 존재 할 경우

Resource allocation graph

• 위와 같은 그래프를 Resource allocation graph 라 함
• 프로세스에서 리소스를 요청하는 선을 Resource edge 라고함
• 이때 리소스에서 프로세스에 할당을 해주는데 이 선을 assignment edge 라고함
• R 이 이미 다른 프로세스에 의해 사용되고 있는 데 또 다른 프로세스가 요청을 하면 리소스를 얻지 못함
• P 는 원 R 는 사각형으로 표기함

데드락 발생

• cycle이 없을 경우 데드락 발생안함
• cycle이 있을 경우
  • 모든 리소스 타입이 single instance 일 경우는 데드락 발생 (필요충분)
  • multiple instance 일 경우 에는 데드락이 발생할 수도 있고 안할 수 도 있음

Hold & wait (DeadLock) 의 필요조건

• 특정 리소스를 사용하고 있는 프로세스가 다른 리소스를 요청 할 경우
  • 특정 리소스를 사용하고 있음 (Hold)
  • 다른 리소스를 요청함 (Request)
  • 요청 한 다른 리소스가 마침 다른 프로세스에 의해 점유가 되고 있음 (Wait)

Solution of Deadlock

Deadlock Prevention

• 데드락의 발생을 미리 방지
• Side effect 가 발생할 수 있음

Mutual exclusive

• 이거는 prevention 할 수 가 없음

Hold and Wait

• 각각의 resource 가 모두 사용가능할 때 만 요청해서 예방할 수 있음

단점

• utilization 이 떨어짐
• 다른 프로세스가 자원을 계속 점유하고 있을
  • starvation 발생 가능성 있음

No Preemption (infeasible)

• 불가능한 조건
• preemption이 지원이 되면 dead lock 이 발생 할 수 없음

Circular Wait

• ordering 개념으로 circular wait을 막을 수 있음

Deadlock Avoidance

• Deadlock 이 절대 발생하지않는 Safe 한 state 에서 기다림
• request 의 개수 ≤ available 한 resources 의 개수인 경우에 절대 데드락이 발생하지 않음
  

• safe 하지 않을 경우 걍 프로세스 잠시 멈춰 버림
  

• 프로세스 수행순서(sequence)
• 위 조건을 만족하도록 safe sequence 를 만드는것이 핵심
  
• single instance 일때의 해결방법 (Resource allocation graph) 를 해결
• multi instance 일때 bankers 알고리즘을 사용함

Deadlock Detection

• Deadlock 이 일어난 후에 감지하여 해결하는 방법

Deadlock detection algorithm

• Banker`s algorithm 과 크게 다르지 않음

Single instance

• Wait-for-Graph
  • 단순히 프로세스가 다른 프로세스가 끝나고 자원을 반납하는 것을 기다리는 상황을 표현
  • 사이클이 존재하면 Deadlock 에 빠졌다는 것을 의미함
  • 자원을 할당해주고 Deadlock에 빠졋는지를 판단함

Multiple instance

• Banker`s Algorithm 과 매우 흡사한 방법사용
• Need 대신 Request를 사용
  • Request 는 당장 현재 상태에서 특정 자원을 요청한 상황
  • Allocation ≠ 0 then finished[i] = false else finished[i] = true
    • allocation가 0 이 아니면 현재 자원을 소유하고 있다는 뜻이고 데드락이 발생할 가능성이 있기때문에 2단계에서 검사를 진행함
  • finished[i] 가 false 고 request[i] ≤ work 인 i 를 찾음 i 가 존재하지 않으면 4단계로 감
  • 만약 finshed[i] 가 false인 process가 하나라도 존재한다면 deadlock 상태인것을 알 수 있음

Deadlock Recovery

Kill

프로세스 걍 죽여버림 (terminate)

Rollback

특정 시점의 state로 돌려버림

Banker`s algorithm (Deadlock avoidance)

• 안전상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때 가지 계속 거절함
• 최소한 고객 한명에게 대출해줄 금액은 항상 은행이 보유하고 있어야 한다!

조건

• Available: 은행이 보유한 돈이 얼마인지, 빌려줄 수 있는 돈이 얼마인지

• Allocated: 고객들이 현재 빌린 돈이 얼마인지

• Max: 각 고객들이 얼마나 맥시멈으로 돈을 요구할지

• 불안전 상태에 들어가지 않도록 하는게 은행 알고리즘의 핵심임