CS/OS

[OS] Deadlocks (1) - 교착상태

JWonK 2023. 5. 9. 15:58
728x90
반응형

  • 데드락이 어떻게 발생하는지, 어떻게 방지하고 회피하는 방법

 

 

  • 항상 자원이 부족해서 발생하는 현상
  • P1이나 P2가 작업을 완료하기 위해서는 tape drives 2개 필요
  • 다 만족하기 위해서는 4개가 필요한데 전체 2개가 필요하면 자원이 부족한 경우가 발생할 수 있음
  • 서로 자원을 필요로 하는데 부족한 경우가 발생하면 이는 데드락 상태를 야기
  • 둘다 1로 초기화 되어있음
  • wait(A), wait(B)로 서로 기다리고 있음 처음 값이 1이어서 통과하지만 0으로 줄어듦
  • 그 뒤는 while문에 걸려 무한반복으로 deadlock
  • signal operation을 만나면 값이 증가되어 종료될 수 있지만 그곳까지 가지도 못함

 

 

  • 또 다른 예로 다리 상태
  • 어느 한 쪽은 양보를 해야 해결이 되는데 다른 문제가 발생할 수 있음
  • 후진하면 그 당시 상태는 해결되지만 어느 한쪽만 통과되고 후진한 쪽은 아무 것도 못함 -> starvation

 

 

 

  • Deadlock 특성 4개
  • 모두 만족하면 Deadlock 상태 발생
  1. Mutual exclusion (상호배제) : 어느 한 프로세스만 자원 사용 가능
  2. Hold and wait : 소유하고 있는 상태를 요청하여 기다리고 있는 상태
  3. No preemption : 뺏어올 수 없다는 의미, 다른 프로세스가 가지고 있는 자원을 뺏어올 수 없음
  4. Circular wait

 

 

 

  • resource내 인스턴스들이 모두 같으면 같은 type으로 봄
  • reousrce 유형
    • CPU
    • Memory
    • I/O devices
  • 각각의 process는 자원을 요청하고 받아 쓰고 반납을 해야함

 

 

 

  • 어느 자원이 누구한테 할당되어있는지 보여주는 그래프 - [자원 할당 그래프]
  • P - Process, R - Resources
  • request edge - 요청 (단방향)
  • assignement edge - 단방향

 

 

 

 

  • 프로세스 - 원, 자원 - 사각형
  • 그 안에 작은 원 : instance
  • request edge : Process -> resource
  • assignment edge : instance -> Process

 

 

 

 

  • P1이 R2의 하나 instance를 가지고 있음 동시에 R1 instance request

 

 

 

  • 파란색과 빨간색 cycle 존재
  • 싸이클 상태에 빠지면 deadlock이라고 함
  • 4가지 조건을 보자면
    • 첫 번째(상호배제), 어느 리소스는 한 순간 어느 한 프로세스에만 할당되어야 함
    • 두 번째, p1을 보면 R2 하나 Hold, 동시에 P1이 R1 하나 Wait
    • 세 번째, 뺏어올 수 없는 상태
    • 네 번째, 파란색과 빨간색 모두 cycle 존재

 

 

  • 똑같이 싸이클이 존재하지만 두 번째 조건을 만족하지 않아 Deadlock 상태가 아님 : P(2)와 P(4)가 Wait상태가 아님

 

 

 

  • Case1의 경우 싸이클 존재 x -> No deadlock
  • Case2의 경우 싸이클이 존재하고 한 유형 안에 instance 1개 -> Deadlock
  • Case3의 경우 싸이클이 존재하고 여러 instance 존재 ->  Deadlock이 발생할 수 있는 상태

 

 

  • Deadlock 극복 방안
  • 아예 Deadlock이 되지 않도록 하는 방법
    • Prevention
    • Avoidance
  • Deadlock은 허용하나 회복할 수 있도록 하는 방법
    • Defect
    • Recovery
  • 신경을 아예 안쓰는 방법, 재부팅
    • 모든 PC, Unix System 적용
    • 위 2가지 방법은 많은 Overhead를 발생시키기 때문에 3번 적용

 

 

 

  • Prevention을 만드는 방식의 조건
    • Mutual Exclusion - 보장해주면 됨
    • Hold and Wait - 일부는 갖고 있고 일부는 요청 대기 상태, 아무것도 없을 때 요청하게 하면 됨
      • 처음에 process가 실행되기 직전 필요한 자원들이 확보가 되면 그 때서야 실행단계로 넘어감
      • 확보가 안된 자원들만 있을 때 자원 요청
      • 자원 이용률이 떨어짐,Starvation 발생 가능성

 

 

 

 

  • No Preemption (뺏어오지 못함)
    • 자원들이 바로 할당되지 못하면 이미 갖고 있던 것들도 모두 반환하도록 함
      • ex) 특정 자원 10개가 필요한 프로세스가 6개를 요청, 6개는 받았는데 4개를 받지못함, 그렇다면 모두 반환
  • Circular Wait
    • 모든 자원들한테 숫자 부여
    • 숫자 증가하는 순선대로 자원 요청 가능

 

 

 

 

  • Deadlock Avoidance (회피) : 사전에 어느 한 프로세스가 자원 요청이 최대 몇 개인지 명시하고 체크
    • Resource-allocation state를 이용하여 회피
    • 자원의 여유분, 할당된 자원들, 최대 자원 요청을 명시하여 Circular-wait 상태를 회피

 

 

 

 

  • 프로세스는 일반적으로 실행 중간 자원을 요청하고 할당되어야 함
  • 자원요청이 들어왔을 때 허락 여부를 판단 
    • Safe State - 자원 제공 ok
    • 실행 순서에 따라 결정(Safe Sequence)
    • 여유분, 반납한 자원들에 대해 P(i)가 만족하면 모든 프로세스가 만족하는 실행순서 - Safe Sequence
    • Safe Sequence 상태라면 System Safe State라 함

 

 

 

  • 시스템이 Safe State라면 "Must have a Safe Sequence"이며 No deadlocks!
  • 시스템이 Unsafe State면 항상 deadlock은 아님, Deadlock 발생 가능성이 존재한다는 뜻임

 

 

 

  • Claim Edge를 추가 - 어느 한 프로세스가 특정 자원을 필요로 할 것 같으면 Claim을 걸어둔다. (미리 선점을 하기 위함)
  • 점선으로 표시
  • Claim Edge → Request Edge
  • Reqeust Edge → 방향이 바뀐 Assignment Edge
  • Assignment Edge → Claim Edge

 

 

 

 

  • 점선으로 Claim Edge로 표시

 

  • Claim Edge가 Assignment Edge로 바뀜
  • CYCLE 발생 가능성이 있기 때문에 Unsafe가 될 수 있음
728x90
반응형