CS/OS

[OS][Deadlock] Characterization, Prevention, Avoidance, Detection, Recovery

은 딩 2023. 6. 2. 21:54

 

[목차]

Deadlock

Deadlock Characterization

Methods for Handling Deadlocks

    Prevention

    Avoidance

          single - ResouceAllocation Algorithm

          multi - Banker's Algorithm

    Detection

          single - Wait for graph

          multi 

    Recovery

          Kill

          Rollback

 

 

Deadlock(교착 상태)

  • process가 resource를 얻지 못해 진행이 안되는 상태
  • 두 개 이상의 작업이 중지되고 각각 사용할 수 있는 자원을 기다리는 경우
    • 서로 원하는 resource가 상대방에게 할당되어 있기 때문에 두 process는 무한정 기다림
  • ex) 외나무 다리 양쪽에서 자동차(Process)가 만난 상황, 서로 양보할 수 없음
    • Recovery 방법 1) Kill the process
    • Recovery 방법 2) Roll back => 자동차를 뒤로 후진시킴
    • Prevention ) 원천적인 원인 제거(애초에 이런 상황을 만들지 X) 

 

Deadlock Characterization

: Deadlock이 발생하려면 이 4가지 특성이 동시에 만족해야 함(필요조건)

1) Mutual Exclusion (상호 배제)

  • resource은 한 번에 한 process만 사용할 수 있어야 함.
  • 다른 process가 그 자원을 요청하면 해당 process는 그 resource가 해제될 때까지 기다려야 함.
    (이렇게 무한정 기다리다가 데드락...)

2) Hold and Wait (점유 대기)

  • 최소한 하나의 resource를 점유하고 있으면서, 현재 다른 process에 할당된 resource을 추가로 점유하기 위해 대기하는 process가 있어야 한다.

3) No preemtion (비선점)

  • 자원을 선점할 수 없으며, 해당 자원을 Hold(점유)하고 있는 프로세스가 종료되어야 그 자원이 해제될 수 있다.
  • 즉, 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 기다려야 함.(강제로 뺏을 수 없음!!)

4) Circular wait (순환 대기)

  • 핵심 조건
  • 자원할당 그래프에서 cycle이 존재해야 함.
  • 프로세스의 집합 {P0, P1, ,…Pn}에서 P0은 P1 holding resource를 대기하고 P1은 P2 holding resource를 대기하고  … Pn-1은 Pn holding resource를 대기하며 Pn은 P0의 holding resource를 요구해야 한다.

                             => P1은 R1을 hold하고 있으면서 R2를 대기하고,  P2는 R2를 hold하고 있으면서 R1을 대기함

 

    Left: No Deadlock                                                                                                              Right: Deadlock

 

만약 자원 할당 그래프에 cycle이 없다?  => No Deadlock

 

만약 자원 할당 그래프에 cycle이 있다?

=> 만약 resource type의 instace가 1개 존재하면 Deadlock

=> 만약 resource type의 instace가 여러 개 존재하면 Deadlock 가능성이 있다

 

 

QUIZ) CPU 자원은 Deadlock이 발생할까?

정답) No!! CPU 자원은 preemtion 할 수 있다

 

Methods for Handling Deadlocks (데드락 처리 방법)

  • Deadlock이 일어나지 않도록 Prevention or Avoidance   (Overhead 크다)
  • Deadlock이 발생하는 것을 막진 않지만 Detection and Recovery  ( Deadlock 허용  >  복구 )
  • Deadlock이 발생한든 말든 신경 쓰지 X

 

Deadlock Prevention

: 위에서 말한 Deadlock 4가지 특성을 동시에 만족하지 않도록! 즉, 하나라도 성립하지 않도록

 

1) Mutual Exclusion (상호 배제) 부정

  • 원래는, 자원으로 서로 동시에 사용하지 못하도록 하는 것
  • 그러므로 상호 배제를 허용하지 않으면 자원을 공유할 수 있다.
  • (( 만약 공유 불가능한 자원 자체가 존재하는 경우 공유 가능하도록 만들어 주는 것이 불가능 즉, 실행불가 ))
  • 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.

2) Hold and Wait (점유 대기) 부정

  • 프로세스가 실행되기 전 필요한 모든 자원을 할당한다.

3) No preemtion (비선점) 부정

  • 원래는, 점유하고 있는 자원을 프로세스가 스스로 반납하기 전까지 회수 X
  • 프로세스가 필요한 자원을 가진 프로세스로부터 그 자원을 선점할 수 있도록 한다.
  • But, 뺏긴 프로세스의 실행이 지연될 수 있음 (Starvation)
  • 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 이전에 사용하던 자원들과 할당을 요청한 자원을 모두 할당받았을 때만 다시 프로세스 수행 가능

4) Circular wait (순환 대기) 부정

  • 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.

Deadlock Prevention은 자원의 활용도가 떨어지고 시스템 성능이 안좋아질 수 있음

 

 

Deadlock Avoidance

: Deadlock 발생하면 피해가는 방법

 

  • Deadlock Avoidance는 사전 정보가 있어야 함
    • 사전 정보: 이용 가능한 자원의 수, 프로세스가 최대로 요구하는 자원의 수, 할당된 자원의 수
  • 이 알고리즘은 Resource-Allocation State를 동적으로 검사하여 Circular wait 상태가 만들어지지 않도록 한다.

Resource-Allocation State

  • Safe 상태 : Deadlock이 발생하지 않을 수 있는 상태, Unsafe로 넘어가지 않도록 해야 함
  • Unsafe 상태 : Deadlock이 발생할 가능성이 있다.

Safe State

  • process가 사용가능한 resource를 요청할때, 즉시 할당이 시스템을 safe 상태로 유지하는지 여부 결정
  • process에 필요한 resource가 즉시 사용 불가할 경우, 모든 프로세스가 끝날 때까지 기다릴 수 있음
  • Safe Sequence가 하나라도 존재하면 Safe State
    • 자원을 필요로 하는 프로세스들에게 자원을 할당해주는 순서

Safe State Example

=> 이 예시에서 Safe Sequence : P1, P0, P2

 

Resource Allocation Graph

Single instance of a resource type. Use a resource-allocation graph
자원의 instance가 하나라면 resource allocation graph로 가능

 

Resource Allocation Graph

- R2 자원을 P1, P2가 차후에 요청할 때 만약 여기서 P2에게 할당을 해주면 오른쪽처럼 cycle이 생겨 Deadlock 상태에 빠질 수 있다.

- R2를 P1에게 먼저 할당을 해주고 P1이 작업을 완료하고 R1과 R2를 반납하면 반납된 자원으로 P2가 작업을 수행하고 완료할 수 있다. 

- 여기서 Safe Sequence는 P1, P2이다.

- 이렇게 자원의 instance가 하나라면 자원 할당 그래프로 Safe Sequece를 찾을 수 있다.

 

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

n Multiple instances of a resource type. Use the banker’s algorithm
자원의 instance가 여러 개라면 Banker's Algorithm 사용

why 은행원 알고리즘?

- 은행은 고객들을 일정한 순서에 의해서 모든 고객들의 요청을 들어준다.

  • 프로세스가 자원을 요청할 때 시스템은 자원을 할당한 후에도 safe state로 남아있게 되는지를 사전에 검사하여 deadlock 회피하는 기법
  • safe state면 자원 할당, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기
  • 사전 정보
    • Available : 사용 가능한 자원의 수
    • Max : 최대로 할당할 수 있는 자원의 수
    • Allocation : 이미 할당된 자원의 수
    • Need : Max - Allocation

Banker's Algorithm

Deadlock Detection

  • Deadlock이 발생한 후 복구하는 방법
  • Instance 하나일 때 사용
    • Wait-for-Graph     cf) Resource Allocation Graph

          => Resource-Allocation Graph에서는 자원을 소유하고 있는 상황도 표현했지만
              Wait-for Graph에서는 단순히 프로세스가 다른 프로세스가 끝나고 자원 반납을 기다리는 상황만 표현

                                                   cycle이 존재한다면 현재 Deadlock 상태

  • Instance 여러 개 일 때 사용
    • Banker's Algorithm과 유사
      • 차이점
        • In deadlock avoidance,
          • Need(Banker's Algorithm) = Max - Allocation
          • 요청은 하지 않아도 궁극적으로 작업을 끝내기 위해 필요한 자원의 양
        • In deadlock detection,
          • Request : 현재 특정 자원을 요청한 상황

Deadlock Recovery

  • detection algorithm이 deadlock 존재한다고 판단했을 때의 대안
    • 1) operator에게 inform하고 수동으로 처리
    • 2) 시스템이 자동으로 복구되도록
      • Kill
      • Rollback  (특정 지점인 check point까지)

Kill

  • 어떤 프로세스를 kill(termination)할지
  • deadlock된 모든 process 중단
    • deadlock cycle이 없어질 때까지
  • deadlock 상태가 제거될 때까지 한 process씩 중단
    • Partial termination을 사용할 경우, 어떤 process를 종료해야하는지 결정
    • procesㄴ 우선순위, resource 필요 정도 등....

Rollback

  • victim 선택 => minimize cost
  • Roll back => safe state로 돌아가서 해당 process restart

 

Reference

Operating System Concepts 10th Edition

저작자표시 비영리 변경금지