[운영체제] Deadlocks

프로그램 코드에 필요한 모든 제반 조건들 - 리소스

리소스가 확보되어야 프로세스가 일을 할 수 있음

 

데드락 발생 조건

1. Mutual exclusion: 상호 배제 조건, 어떤 프로세스가 자원을 쓰고 있으면 다른 프로세스는 그 자원을 쓸 수 없다는 것
2. No preemption: 어떤 프로세스가 자원을 잡고 있으면 자발적으로 놓기 전까진 다른 프로세스가 사용할 수 없음, 강제로 뺏지 않음
3. Hold and wait: 모든 프로세스는 확보한 자원은 손에 꼭 쥐고 있고 나머지 자원을 확보하기 위해 기다린다는 것
4. Circular wait: P1이 P2의 자원을 기다리고, Pn-1이 Pn의 자원을 기다리고, Pn이 P0의 자원을 기다리는 것처럼 원형 대기 방식이 된다는 것

Resoure-Allocation Graph, 자원 할당 그래프

정점 V

P = {P1, P2, ..., Pn} 프로세스

R = {R1, R2, ..., Rn} 자원

 

간선 E

request edge P1 -> Rj // 프로세스가 자원이 필요하다고 요청한 거

assignment edge Rj -> Pi // 자원이 프로세스에 할당된 거

 

표시방법

 

 

예시

 

기본 사실

• 그래프에 사이클이 없으면 데드락 x
• 사이클이 있는 경우
  • 인스턴스가 하나면 데드락
  • 인스턴스 여러 개면 데드락일 수도 아닐 수도 있음

그래프 예시

• 데드락인 경우 그래프

=> P1은 R1을 잡아야 하는데 P2가 쓰고 있고, 

      P2는 R3를 잡아야 하는데 P3가 쓰고 있고,

      P3는 R2를 잡아야 하는데 P1, P2가 쓰고 있음

• 데드락이 아닌 경우

 

=> P2 일 끝나면 R1 반납해서 P1이 일할 수 있음

      P4 일 끝나면 R2 반납해서 P3이 일할 수 있음

 

데드락에 대처하는 OS의 자세

1. 절대로 데드락이 되지 않도록 하는 것
   • prevent, avoid
2. 데드락 허용, 발생 시 조치 
   • detection: 감지 시스템
3. 데드락 무시 전략, 대부분의 os가 사용 중
   • 데드락이 일어날 확률은 상당히 작기 때문
   • 요즘 컴퓨터에서 웬만하면 자원이 부족할 일이 발생하지 않음; CPU가 굉장히 빠르고 ,,,

 

Deadlock Prevention

• 데드락이 일어나는 4가지 조건 중 하나를 충족하지 못하게 만들어서 발생할 수가 없게 해버리는 것
  
  • Mutual Exclusion - 자원에 대한 공유를 할 수 있게 만들어서 데드락을 없앨 수 없으니까 운영체제가 어떻게 할 수 없음 
  • Hold and Wait - 내가 확보한 자원은 손에 꼭 쥐고 있으면서 추가적으로 자원을 기다리는 상태
    • all or nothing; 필요한 자원은 동시에 확보하든지 하나라도 확보를 못한다면 기다리든지
    • 단점: low resource utilization; starvation 가능성
      • 진도가 안 나갈 수 없음, 필요한 자원들이 순차적으로 사용되면 난 계속 기다려야 되니까
  • No Preemption - 자원은 강제로 뺏을 수 없다
    • 뺏어볼까? 모두 확보할 수 없다면 잡았던 자원은 뻇어
    • 결과적으론 hold and wait과 같아짐
  • Circular Wait
    • 자원의 종류마다 번호를 매겨서 낮은 번호부터 확보하도록 함
    • 3, 5, 7이 필요할 때 3, 5는 사용 중이고 7번만 확보 가능해도 7번을 먼저 잡지 못하도록 함
    • 모든 프로세스는 필요한 자원을 가진 다음 프로세스를 기다릴 때 내가 가진 자원보다 큰 번호를 기다리게 돼서 가장 끝의 프로세스는 가장 처음 프로세스의 자원을 기다리지 않게 됨
• 하지만 저 방법들은 자원 활용의 효율성을 떨어트려 시스템 전체의 throughput을 떨어트림, 별로 좋지 않음

Deadlock Avoidance

• 회피, prevention은 아예 싹을 자르는 거고 이건 싹을 자르진 않음
• 동작 과정에서 데드락이 발생하지 않도록 제어
• 데드락이 발생하지 않을, 안전한 길만 선택해서 가겠다
• 미래에 데드락이 일어날 가능성을 판단할 수 있어야 함
• 미리 정보 수집, 그걸 기반으로 안정성 평가
• Safe State
• 안전한 상태는 모든 프로세스가 다 끝마칠 수 있는 프로세스의 종료 시퀀스가 존재하는 경우
• 기본 사실
  • 시스템이 safe state => deadlock X
  • 시스템이 unsafe state => deadlock 발생 가능성 (단정 X)
    
    • 모든 프로세스가 자원의 최대치를 요청할 때만 데드락 
    • 자원을 최대치로 사용하지 않고 순차적으로 사용한다면 데드락 발생 X
  • Avoidance: 그래도 일말의 가능성이 있으므로 safe state로 동작하겠다 약간 소심

Avoidance 알고리즘

• 각 리소스가 인스턴스를 하나만 가지는 경우; Resource Allocation Graph algorithm
  • claim edge: 지금 당장 요청하는 건 아니지만 미래에 사용할 거라고 선언
  • request edge: 자원을 실제로 요청
  • assignment edge: 실제 자원 요청이 받아들여져서 자원을 사용하는 경우
  • assignment edge가 자원을 사용하고 반납하면 다시 claim edge로 바뀜 <- 또 사용할 수도 있으니까
  • claim edge들이 그려지고 자원 요청 시 request edge가 그려지고 assign 했을 때 안전하면 assignment edge로 바꿔줌
    • 사이클이 그려지면(=unsafe state) assignment edge로 바꾸지 않음
  • 아래의 경우 P2에게 R2를 할당해주면 P1이 R2를 요청했을 때 사이클이 생기므로 assign해주지 않음

 

• 각 리소스가 여러 개의 인스턴스를 가지는 경우; Banker's algorithm
  • 전제조건 
    1. 모든 프로세스는 시작 전 리소스의 최대 사용량을 미리 선언해야 함
    2. 어떤 프로세스가 리소스를 요청하면 바로 받지 못하고 기다릴 수 있음
    3. 어떤 프로세스가 필요로 하는 리소스를 모두 받았으면 반납해야 함
  • n개의 프로세스, m개의 리소스 타입
  • Vector; Available[j] = k: j라는 리소스 타입이 k개 남아있다, 할당되지 않았다
  • n*m Matrix; Max[i, j] = k: 프로세스 i는 리소스 j를 최대 k개 사용한다
  • n*m Matrix; Allocation[i, j] = k: 프로세스 i는 리소스 j를 k개 할당받은 상태이다
  • n*m Matrix;Need[i, j] = k: 프로세스 i는 리소스 j가 추가적으로 k개 더 필요하다
    • Need[i, j] = Max[i, j] - Allocation[i, j]

Safety Algorithm

• Banker's algorithm 예시
  • 5개의 프로세스 P0~P4
  • 3개의 리소스 타입과 각각 인스턴스 개수 A(10), B(5), C(7)
  • 가능한 종료 시퀀스 <P1, P3, P4, P2, P0>

 

Deadlock Detection

• 데드락 걸리면 조치해주겠다, 미래를 보는 게 아니라 현재만 봄
• 데드락을 감지할 수 있어야 하고, 조치 방법이 있어야 함

Detection algorithm

• 리소스 타입 당 인스턴스가 1개인 경우; wait-for-graph
  • 프로세스 간 대기 관계, Resource allocation graph에서 자원 없앰
  • Pk -> Pj : Pk가 Pj 기다림
  • 사이클 탐지

• 리소스 타입 당 인스턴스가 여러개인 경우
  • safety algorithm과 유사

 

Detection Algorithm 예시

• 시간 복잡도
  • O(m*n^2)
  • m=n이면 O(n^3)
  • => 꽤 큼
  • 감지 방법
    1. 요청할 때마다
    2. 요청을 받아들일 수 없을 때
    3. 주기적으로

Recovery from Deadlock

1. Process Termination: 프로세스 죽이기
   
   • 데드락 걸린 모든 프로세스 죽이기
   • 하나씩 죽여보기
     • 우선순위 낮은 놈부터
     • 얼마나 오랫동안 동작했는지 (시작한지 얼마 안 된 놈을 죽이는 게 낫지 않냐는 생각)
     • 프로세스가 사용해온 자원의 양 (많은 놈을 죽이면 다시 시작했을 때 자원을 많이 필요로 하니까)
     • 앞으로 필요로 하는 자원의 양이 많은 놈을 죽이자
     • 최소한의 프로세스를 죽여서 데드락을 해소할 수 있는 집합을 찾자
     • interactive한 걸 죽이지 말고 batch (백그라운드에서 도는 놈)을 죽이자
2. Resource Preemption: 자원 뺏기
   • victim(자원 뺏을 프로세스) 선정
   • 자원을 뺏어서 이전의 안전한 상태로 돌리고 프로세스 다시 시작
   • Starvation이 생길 수도 있음
     • 자원 뺏기는 놈이 계속 뺏길 수 있기 때문

 

 

 

 

 

한양대학교 강수용 교수님 운영체제 강의 내용 정리