교착 상태

in CS on OS


Deadlock


[ 교착 상태 ]

  • 자원(Resuorce)와 굉장히 밀접한 관계를 가진다.
  • Blocked/Asleep state
    • 프로세스가 특정 Event를 기다리는 상태
    • 프로세스가 필요한 자원을 기다리는 상태
  • Deadlock stats

    • 프로세스가 발생 가능성이 없는 Event를 기다리는 경우

      Process가 deadlock 상태에 있음

    • 시스템 내에 deadlock에 빠진 process가 있는 경우

      시스템이 deadlock 상태에 있음


[ Deadlock vs Starvation ]

Deadlock은 Asleep/Blocked 상태에 존재하고, 일어날 가능성이 없는 자원과 Event를 기다린다. 

반면, Starvation경우는 ready state에서 CPU를 기다린다. 

즉, 항상 일어날 Event를 기다리는 셈이다.


[자원의 분류 ]

Deadlock을 이해하기 위해선 자원의 분류를 알아야한다.

일반적으로 HW자원, SW자원으로 나뉜다. 여기서는 다른 분류법을 다뤄본다.

1. 선점 가능 여부에 따른 분류

Preemptible Resources

  • 내 자원을 빼앗길 수 있는 경우
  • 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원
  • Processor, Memory 등

Non Preemptible Resources

  • 내 자원은 빼앗기지 않는다.
  • 선점 당하면, 이후 진행에 문제가 발생하는 자원
  • disk drive 등
예를 들어 USB에 자료를 옮기고 있는 도중에는 USB를 제거해서는 안 된다.

만약에 누군가 USB를 뽑으면 데이터가 제대로 저장되지 않을 것이다.

이런 경우 Non Preemptible Resources는 USB를 말한다.


2. 할당 단위에 따른 분류

Total allocation resources

  • 자원 전체를 process에게 할당
  • 한 번에 한 명 만 쓸 수 있다.
  • processor, disk drive

Partitioned allocation resources

  • 하나의 자원을 여러 조각으로 나누어, 여러 process에게 할당.
  • Memory 등


3. 동시 사용 가능 여부에 따른 분류

Exclusive allocation resources

  • 한 순간에 한 process만 사용 가능한 자원
  • Processor, memory, disk drive
여기서 Memory가 있는 이유

앞에서 봤듯이, 메모리는 여러 조각으로 분할이 가능하다.

예를 들어 하나의 메모리를 4등분 했다고 가정하면 A,B,C,D 이렇게 4개의 영역이 나온다. 

그리고 A영역이 P1(1번 프로세스)에 할당 됐다면, A영역은 P1만 사용할 수 있다.

Shared allocation resource

  • 여러 process가 동시에 사용 가능한 자원
  • program(sw), sdata
엑셀.exe를 예로 들면, 우리는 엑셀 창을 동시에 여러개 띄울수 있다.

즉, 각각 다른 process가 엑섹.exe를 동시에 사용 가능하다는 의미이다.


4. 재사용 가능 여부에 따른 분류

SR(Serially-Reusable Resources)

  • 연속적으로 다시 쓸수 있는 자원
  • 시스템 내에 항상 존재하는 자원
  • 사용이 끝나면, 다른 process가 사용 가능
  • Processor, memory, disk drive, program

CR(Consumable Resources)

  • 소비되는 자원
  • 한 process가 사용한 후에 사라지는 자원
  • signal, messages


🔒 Deadlock을 발생 시킬수 있는 자원의 형태

  • Non Preemptible Resources (100%)
  • Exclusive allocation resources (100%)

  • Shared allocation resource

    CR과 SR 모두 Deadlock을 발생 시킬수 있다. 하지만 CR까지 고려하게 되면 Deadlock모델이 너무 복잡해진다. 따라서 CR을 빼고 SR만 고려하는 것이다.

  • 할당 단위는 영향을 미치지 않는다

    전체를 할당 받아도, preemptible이면 Deadlock이 아니기 때문이다.


[ Deadlock Model 표현법 ]

1. Graph Model

deadlock1

  • 자원 노드는 직사각형, 프로세스 노드는 원
  • R1 → P2 : 자원 할당
  • P2 → R2 : 프로세스 P2가 자원을 요청 ( 대기중 )


2. State Transition Model

deadlock2

  • SAB

    S : State A : P1의 상태 B : P2의 상태


[ Deadlock 발생 필요 조건 ]

❗ 아래 조건 네 가지를 모두 만족 시켜야한다.

자원의 특성

  • Exclusive use of resources
  • Non preemptible resources

프로세스의 특징

  • Hold and Wait (Partial allocation)
  • Circular wait


References