Skip to content

Latest commit

 

History

History
159 lines (106 loc) · 6.46 KB

Deadlocks.md

File metadata and controls

159 lines (106 loc) · 6.46 KB
Raw

Deadlocks (교착상태)

교착상태(Dead Lock)은 상호 배제에 의해 나타나는 문제점으로,

둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미

Deadlock Problem

Deadlock

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

Resource(자원)

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

Example

Deadlock 발생의 4가지 조건

  • **Mutual exclusion **
    • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
  • ** No preemption**
    • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
  • Hold and wait (보유대기)
    • 내가 가진 자원을 놓지 않으면서 다른 자원을 기다림
  • ** Circular wait (순환 대기)**
    • 자원을 기다리는 프로세스간에 사이클이 형성되어 있어야 함

Resource - Allocationn Graph 자원 할당 그래프

  • 작은 점 -> 자원의 instance
  • cycle 이 없음

  • cycle 이 있음
  • 자원의 instance가 여러 개 있으면 deadlock 일 수도 아닐 수도 있다
  • 1 graph : deadlock O
  • 2 graph : deadlock X
    • 4번 프로세스가 다 사용하고 나서 반납하면 dead lock 사라지기 때문

Deadlock의 처리 방법

Deadlock Ignorance

  • deadlock이 자주 발생하지 않기 때문에 현대 컴퓨터 에서는 미연에 방지하지 않음

1. Deadlock Prevention

  • Mutual Exclusion (필수) -> 배제해서는 안되는 조건임
  • Hold and Wait
    • 자진 반납
  • No Preemption
    • 자원을 빼앗을 수 있게 한다. (CPU,memory) (자원 상태 저장)
  • 생기지도 않을 deadlock 문제를 미리 방지하고 있어서 비효율적

2. Deadlock Avoidance

Deadlock 발생 가능성 계속 검사. 발생 가능성이 있다면 회피.

  • Safe state : Deadlock이 발생하지 않는 상태
  • Unsafe state : Deadlock 발생 가능성 있는 상태 (100%는 아님)

Safe state에 있던 프로세스는 언제든지 Unnsafe state로 넘어갈 수 있으며, 이것을 막아야 한다.

Deadlock을 회피하기 위한 알고리즘 2가지

  1. 자원이 하나 종류일 때 -> 자원 할당 그래프
  2. 자원이 여러 종류일 때 -> Banker's Algorithm 사용

일단 할당했다고 가정하고 Deadlock이 발생하는지 확인해 실제로 Deadlock이 발생하는 걸 막는다는 공통점이 있음

Resource Allocation Graph algorithm

자원이 한 종류일 때

  • 점선화살표

    • 프로세스가 새로 자원을 요구하는 것
    • 프로세스가 평생에 적어도 한 번은 이 자원을 요청

  • 3 graph

    • deadlock 이 아님
    • 점선이 실선이 되면(자원 요청하면) deadlock 이 생김

  • deadlock 위험성이 있으면 애초에 자원을 주지 않음

Banker's Algorithm

자원이 여러 종류일 때

  • 자원당 instance 여러 개인 경우 이 알고리즘 통해 dead lock을 막는다

  • Allocation : 현재 할당 중인 자원

  • Max : 프로세스가 작업을 끝내기 위해 필요한 총자원

  • Available : 현재 빌려줄 수 있는 자원의 양

  • Need : 추가로 요청할 수 있는 양

  • 안전상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 계속 거절한다.

  • p0이 b 2개 요청 -> 남아있는 양 있지만 추가요청 (7,4,3) 임 -> 남아있는 것 가지고 충족 x / 혹시 최대 요청을 할까봐

  • 최악의 경우를 고려 (7,4,3)

  • 보수적 알고리즘

  • 가용자원 (0,0,0) 되면 무조건 deadlock은 아님 -> 다른 애가 반납할 수 있음

3. Deadlock Detection and recovery

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

싸이클을 찾는 오버헤드는 얼마인가?

O(n**2) -> n(n-1)

  • Resource 당 multiple instance 인 경우
  • 낙관적 관점으로 본다

p2 가 자원 c 하나를 요청

**deadlock 이 있는지 찾아볼 때 **

  • 가용자원으로 처리할 수 있는지 보기
  • 요청하지 않은 프로세스 (Request) 가용자원으로 합치기 -> P0 같은 경우
  • 거기서 처리할 수 있는지 체크

Deadlock이 발견이 되면 Recovery 해야함

  1. Process termination
    • 데드락에 연루된 프로세스 종료
  2. Resource Preemption - 데드락에 연루된 프로세스로 부터 자원 뺏기

4. Deadlock Ignorance

  • 사용자가 deadlock을 알아서 처리
  • OS는 deadlock에 대해 대처하지 않는다. (현대의 대부분 운영체제)