[운영체제] 6. Deadlock

키워드

deadlock, mutual exclusion, no preemption, hold and wait, circular wait, resource-allocation graph,
deadlock prevention, deadlock avoidance, deadlock detection and recovery, deadlock ignorance

 

Deadlock(교착상태)

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

 

Resource(자원)

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

 

Deadlock 발생의 4가지 조건

• Mutual exclusion(상호 배제)
  • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
  • 즉, 얻었으면 독점적으로 사용
• No preemption(비선점)
  • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
• Hold and wait(보유대기)
  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓치 않고 계속 가지고 있음
• Circular wait(순환대기)
  
  • 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
  • 프로세스 P0, P1, ..., Pn이 있을 때
    • P0은 P1이 가진 자원을 기다림
    • P1은 P2가 가진 자원을 기다림
    • Pn-1은 Pn이 가진 자원을 기다림
    • Pn은 P0이 가진 자원을 기다림
• Deadlock은 위 조건을 모두 만족해야 한다.

 

Resource-Allocation Graph(자원-할당 그래프)

• P는 프로세스, R은 자원
• 화살표
  • 자원에서 프로세스로 나가는 화살표: 이 자원이 해당 프로세스에 속해있다. 즉, 해당 프로세스가 해당 자원을 가지고 있다. 
  • 프로세스에서 자원으로 나가는 화살표: 이 프로세스가 해당 자원을 요청한 상태(아직 획득하지 못함)
• 사각형 안의 작은 점: 자원의 수. 즉, 인스턴스 
  
  
• 그래프에 cycle이 없으면 deadlock이 아니다.(화살표 따라가보기)
• 그래프에 cycle이 있으면
  • 자원 당 인스턴스가 하나씩 밖에 없다면, deadlock
  • 자원의 인스턴스가 여러 개 있다면 deadlock일수도 있고, 아닐수도 있다. 
    (위 그림상의 제일 오른쪽 예시처럼 여분의 자원을 가지고 있는 경우 사이클이 있지만 deadlock이 아님)
• 테이블을 사용해 쉽게 deadlock을 판별할 수 있다.

 

Deadlock의 처리 방법

• Deadlock Prevention
• Deadlock Avoidance
• Deadlock Detection and recovery
• Deadlock Ignorance
  
  
• 맨 위 두가지(Deadlock Prevention, Deadlock Avoidance): deadlock이 생기지 않게 미연에 방지
• 아래 두가지(Deadlock Detection and recovery, Deadlock Ignorance): deadlock이 생기도록 놔둔 후 처리
• 위로 갈수록 더 강한 deadlock 처리 방법
• deadlock 자체가 빈번하게 발생하는 문제가 아니기 때문에 미연에 방지해서 오버헤드를 들이는게 
  시스템적으로 비효율적이라 판단. 때문에 오늘날 대부분의 OS에서 마지막 Deadlock Ignorance를 채택

Deadlock Prevention

• 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

Deadlock Avoidance

• 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

Deadlock Detection and recovery

• Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover

Deadlock Ignorance

• Deadlock을 시스템에서 책임지지 않음
• UNIX를 포함한 대부분의 OS가 채택
• 사람이 해결

 

Deadlock Prevention

Deadlock을 만족하는 4가지 조건 중 하나를 원천적으로 차단해서 deadlock이 되지 않게 하는 방법

그래서 무엇을 막을건가?

Mutual Exclusion

• 자원을 한번에 여러 프로세스에서 공유해서 쓸 수 있는 자원이라면 애초에 deadlock 이야기가 나오지 않았을 것임.
  때문에 deadlock prevention 방법으로 막을 수 있는 조건이 아니다.

Hold and wait

• 자원을 기다리는 상황에서 자원을 보유하고 있지 않으면 된다.
• 방법 1
  • 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
  • 중간에 필요한 자원이 없음. 모든걸 hold하고 시작해서 wait 할 일이 없다.
  • 하지만 프로세스가 종료될 때 까지 모든 자원을 다 쓰는게 아닌
    매 시점 필요한 자원이 다를 것이기 때문에 자원에 대한 비효율성이 생김
• 방법 2
  • 위 방법과 다르게 자원이 필요할 때 마다 할당 받는데, 뭔가 hold 하고 있는데 다른 자원을 기다려야 되는 경우
    이미 hold한 자원도 다 뱉어낸 후 기다림
  • 지금 당장 필요한 걸 다 얻거나 다 뱉어내기 때문에 deadlock이 발생하지 않음
  • 자진해서 반납함으로서 문제 해결

No preemption

• 자원을 preemption 할 수 있게 한다면 deadlock이 발생하지 않음
• CPU에 타이머 인터럽트를 거는 자원의 경우에는 deadlock이 발생하지 않음
• 위 문제는 자원을 내놓지 않는 경우 발생함. 고로, 자원을 강제로 빼앗아 오면 해결
• State를 쉽게 save하고 restore 할 수 있는 자원에서 주로 사용된다. (CPU, Memory)
• but, 중간에 빼앗아오면 하던 일이 엉망이 되는 자원들에서는 사용하기 어려움

Circular wait

• 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
• 앞의 순서 자원을 얻지 못하면 뒷 순서의 자원을 얻지 못하게 함으로 deadlock 방지

정리

• Deadlock prevention 방법은 deadlock을 원천적으로 막을 수 있지만
  생기지도 않을 deadlock을 미리 생각해 제약 조건을 달아놓기 때문에 아래 문제들이 발생할 수 있다. 
  • 자원에 대한 이용률이 낮아짐
  • 전체 시스템의 성능이 나빠짐
  • starvation 문제 발생

 

Deadlock Avoidance

• 프로세스가 시작될 때 해당 프로세스가 평생 쓸 자원의 최대량을 알고 있다고 가정하고 deadlock을 피해가는 방법
• 어떤 프로세스가 자원 요청을 할 때 자원을 할당해주면 deadlock이 발생할 가능성이 있다면 자원의 여분이 있음에도 주지 않는다. 
• 항상 safe한 상태 유지
  -> 가용 자원만 가지고도 safe sequance가 있어서 모든 프로세스가 다 끝까지 수행되는게 만족되는 상황 유지
• 2가지 경우의 avoidance 알고리즘
  • 자원의 인스턴스가 하나씩 밖에 없을 때
    -> Resource-Allocation Graph(자원-할당 그래프) 알고리즘을 통해 avoidance 진행
  • 자원의 인스턴스가 여러 개 있을 때
    -> Banker's 알고리즘을 사용해 deadlock을 효율적으로 피해감

Resource-Allocation Graph Algorithm

• Deadlock avoidance에서 자원의 인스턴스가 하나씩 밖에 없을 때 사용하는 알고리즘
• 위에서 설명한 자원, 프로세스, 실선 화살표 외에 점선이 추가됐는데 
  점선은 해당 프로세스가 평생에 적어도 한번은 그 자원을 사용할 일이 있다는 의미
• 실제로 요청하게 되면 점선은 실선으로 바뀜
• 그림의 세번째 상황은 P1에서 R2의 자원에 대해 요청하고 있지만 당장 요청하는게 아닌 
  평생에 한번 요청할거란 의미이므로 deadlock이 발생하는 상황은 아니다. 
• 만약 3번째 상황에서 점선에 대해 요청을 실제로 하게 되면 사이클이 만들어지고 deadlock이 됨
  
  
• Deadlock avoidance 방법은 최악의 상황을 가정하기 때문에 
  두 번째 상황에서 세 번째 상황으로 넘어가게 만들지 않는다. 
  때문에 P2에서 R2 자원을 요청했지만 R2 자원을 아무도 가지고 있지 않음에도 주지 않음
  (가능성을 아예 배제)
• 이처럼 deadlock avoidance는 available한 자원이 있다고 해서 다 내어주는게 아닌 
  혹시 deadlock의 위험성이 있다고 하면 애초에 자원을 주지 않는 방식이다. 

Banker's Algorithm

• Deadlock avoidance에서 자원의 인스턴스가 여러 개일 경우 사용하는 알고리즘
• Banker's algorithm은 이 프로세스들이 요청 가능한 자원에 대해 요청했을 때
  그 요청을 받아들일 것인지 받아들이지 않을 것인지 결정한다. 
• ex) P0 이 A를 하나 요청하면 A는 3개가 available하기 때문에 받아들일 순 있다. 
  하지만 Banker's algorithm은 주지 않는다.
  줄 순 있지만 최악의 경우에 추가로 나머지 A 6개, B 4개, C 3개를 요청할 수 있기 때문에 
  available 가용 자원을 넘어서기 때문에 문제가 된다. 
• Banker's 알고리즘은 대단히 보수적이기 때문에 절대 deadlock이 발생하지 않도록 하기 위해 
  최대 요청을 할거란 가정 하에 가용 자원이 충족되는가를 보고 요청을 응답한다. 
• but, 자원이 남아돎에도 혹시 모를 상황 때문에 주지 않기 때문에 비효율적

 

Deadlock Detection and Recovery

Detection

• 자원의 인스턴스가 하나밖에 없는 경우
• 자원-할당 그래프의 자원을 빼버리고 wait-for 그래프로 바꿀 수 있다. 
• wait-for graph로 바꾼 후 사이클이 있는지 체크 (사이클이 있다면 deadlock)

• 자원의 인스턴스가 여러 개 있을 경우
• 자원을 요청하면 다 주기 때문에 deadlock avoidance와 달리 자원을 얼마나 요청할지 미리 알 필요는 없다. 
• 위 사진의 상황은 가용 자원(available)이 없는 상황에서 요청(request)를 하는 상황
  • 이 상황이 deadlock인지?
  • deadlock avoidance와 달리 보수적인 접근이 아니라 낙관적 접근을 통해 deadlock 여부 확인
  • 현재 요청한 게 없는 프로세스에 대해 allocation의 자원을 반납할 것이다. 라고 보는 방법
    ex) P0, P2가 각각 요청한게 없으니
    B 1개와 A 3개, C 3개를 반납 할 것이다 라고 보는 거임
    그럼 available의 A, B, C에 대해 3, 1, 3이 됨. 
    -> 이걸 가지고 나머지에 대해 request를 고려 (& 주고 났을 때 반납할 것을 또 고려해서 available이 쌓임 및 반복)
• 만약 P2의 요청이 0, 0, 1이 되면 당장 available한 자원이 P0의 B 1개 뿐이므로 
  어느 request도 충족할 수 없게 되어 deadlock이 된다.
• deadlock이 있는지 찾는 방법
  1. 가용 자원으로 처리 가능한게 있는지 체크
  2. 지금 요청하지 않은 프로세스들의 자원을 가용 자원으로 합침
  3. 합쳐진 가용 자원으로 또 처리 가능한게 있는지 체크 및 반복
• 위 방법들로 deadlock이 발견된다면 recovery를 해야한다.

Recovery

Process Termination

• 프로세스를 죽이는 방법. 아래 두가지 방법 존재
• Deadlock에 연루된 모든 프로세스들을 사살
• Deadlock에 연루된 프로세스들을 하나씩 죽여봄

Resource Preemption

• Deadlock에 연루된 프로세스로부터 자원을 빼앗아 deadlock을 해소하는 방법
• 빼앗았는데 다른 프로세스에서 가져가기 전에 해당 프로세스가 또 가져가버려 
  deadlock을 해소했음에도 똑같은 패턴이 발생할 경우 존재
  • 자원을 뺏을 프로세스를 선정하는 패턴을 바꿔야할 필요성
  • 똑같은 프로세스만 계속 빼앗기는 경우(starvation)도 같이 고려