7장 Deadlock

 

• 1 deadlock, resource의 정의
• deadlock
• Resource

• 2 Deadlock 발생 조건
• 2-1. Mutual exclusion (상호 배제)
• 2-2. No preemption (비선점)
• 2-3. Hold and wait (보유 대기)
• 2-4. Circular wait (순환 대기)

• 3 Resource Allocation Graph
• 3-1. 자원 할당 그래프
• 3-2. deadlock 상태 판단

• 4 Deadlock의 처리 방법
• 4-1. Deadlock Prevention
• 4-2. Deadlock Avoidance
• 4-3. Deadlock Detection and Recovery
• 4-4. Deadlock Ignorance

reference: kocw의 반효경 교수님 강의와 권진욱 교수님 강의(대학 정규 수업)
수업을 듣고나서 강의 교재를 타이핑하고 필기한 부분을 추가적으로 정리하였습니다.
웹뷰에서 toc를 제공합니다.
github의 md 파일로 보는 게 편하시다면, 여기로 이동해주시면 됩니다.

---

1 deadlock, resource의 정의

deadlock

• 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
• 어느 누구도 양보를 하지 않으면 더이상 진행되지 않는 상태

Resource

• 하드웨어, 소프트웨어 등을 포함한 개념
  • 예: I/O device, CPU cycle, memory space, semaphore 등
• 프로세스가 자원을 사용하는 절차는 다음과 같이 이루어진다.
  1. 요청 (Request)
  2. 획득 (Allocate)
  3. 사용 (Use)
  4. 반납 (Release)
• 예시
  • deadlock example 1 (하드웨어 리소스)
    • 시스템에 2개의 tape drive가 있는데, 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다
  • deadlock example 2 (소프트웨어 리소스)
    • binary semaphores A and B
    •   

      

2 Deadlock 발생 조건

2-1. Mutual exclusion (상호 배제)

• 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
• 어떤 자원을 가지고 있는 동안에 그 자원을 독점적으로 쓴다.

2-2. No preemption (비선점)

• 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다.
• 자원을 강제로 빼앗을 수 없다.

2-3. Hold and wait (보유 대기)

• 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원(자신의 자원)을 놓지 않고 계속 가지고 있는다.

2-4. Circular wait (순환 대기)

• 자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다.

3 Resource Allocation Graph

3-1. 자원 할당 그래프

자원 할당 그래프를 통해 deadlock 상태인지 아닌지를 판가름할 수 있다.

• 동그란 건 프로세스
• 네모는 리소스
• 점 개수는 리소스의 개수-instance의 개수
  • Resource는 하나의 Block에 여러개가 있을 수 있다.
• Process에서 나가는 화살표는 Resource를 요청하고 있는 상태를 나타낸다.
• Resource에서 나가는 화살표는 해당 Resource를 Process가 보유하고 있음을 나타낸다.

3-2. deadlock 상태 판단

• 그래프에 cycle이 없다면 모든 경우에 deadlock이 아니다.
• 그래프에 cycle이 있고 모든 Resouce Block에 자원이 하나씩만 있다면 반드시 deadlock 상태이다.
• 그래프에 cycle이 있지만 모든 Resoucr Block의 자원이 하나씩만 있는 것이 아니라면 (여러개가 있는 Block이 존재한다면) deadlock일 수도 있고 아닐수도 있다. (추가적 검증 필요)

• 왼쪽 그림은 deadlock 상태이다.
• 오른쪽 그림은 cycle이 형성되어있지만 deadlock 상태가 아니다.
• P2가 언젠가 끝나게 되어 instance 1개가 free 되면 P1은 R1을 점유할 수 있고 P3는 R1의 두번째 resource를 가져다 쓰는 것은 deadlock이 아니다.

4 Deadlock의 처리 방법

• Deadlock Prevention
  • 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
• Deadlock Avoidance
  • 자원 요청에 대한 부가적인 정보를 이용하여 deadlock의 가능성이 없는 경우 (즉, 시스템 state가 원래 state 돌아올 수 있는 경우)에만 자원 할당
• Deadlock Detection and Recovery
  • deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recovery
• Deadlock Ignorance
  • Deadlock을 시스템이 책임지지 않는다. UNIX를 포함한 대부분의 OS가 채택하고 있는 방식이다.

4-1. Deadlock Prevention

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

1) Mutual exclusion

• 배제 불가하다. 공유해서는 안되는 자원의 반드시 성립하게 되어 있다.

2) Hold and Wait

• 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
• hold를 하지 않도록 해서 deadlock이 발생하지 않도록 한다.
• 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
  • 단점: 프로세스가 매 시점 필요한 자원이 다르기에 자원의 비효율성이 높아지므로 잘 사용하지 않는다
• 방법 2. (자원을 내놓지 않고 요청할 경우 deadlock 발생하기에) 자원이 필요한 경우 보유자원을 모두 반환 뒤 다시 요청
  
  • 자원 비효율성이 높지 않다.

3) No Preemption

• process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨(강제로 빼앗길 수 있음)
• 모든 필요한 자원을 얻을 수 있을 때 프로세스 다시 시작
• State를 쉽게 save저장, restore복구할 수 있는(=context switch) 자원에서 주로 사용 (CPU, memory)

4) Circular wait

• 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.
• 이렇게 하면 쌍방향으로의 자원 요구가 이루어질 수 없으므로 Cycle이 생길 우려가 사라진다.
• 예를 들어 순서가 3인 자원 Ri 를 보유 중인 프로세스가 순서 1인 자원 Rj를 할당받기 위해서는 우선 Ri를 release해야 한다.

하지만 위의 방법들은 Utilization 자원 이용률 저하, throughput 처리량 감소, starvation 현상 등이 발생한다.

또한 발생 가능성이 낮은 deadlock 방지를 위한 제약 조건이 많기에 비효율적이다.

4-2. Deadlock Avoidance

*참고로 prevention과 avoidance의 뉘앙스의 차이점은

• prevention: active하게 적극적으로 막는다.
• avoidance: 문제점으로부터 멀리 떨어지도록 해서 deadlock을 막는다.

 

정의

• 자원 요청에 대한 부가적인 정보를 이용해서 deadlock으로부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 자원 할당
  • 시스템이 unsafe state에 들어가지 않는 것을 보장
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.
• 시스템 state가 원래 state 돌아올 수 있는 경우에만 자원 할당

safe state: 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

safe sequence:

• 프로세스의 sequence <P1, P2, ..., Pn>이 safe하려면 Pi의 자원요청이 "가용 자원 + 모든 Pj (i < i)"에 의해 충족되어야 함.
• 조건을 만족한다면 다음 방법으로 모든 프로세스의 수행을 보장
  • Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj (j < i)가 종료될 때까지 기다린다.
  • Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다.

정리하면:

자원 요청에 대한 부가적인 정보를 이용해서 deadlock 가능성이 없는 경우에만 자원을 할당해준다. 프로세스가 시작될 때 그 프로세스가 최대로 사용할 자원을 미리 알려준다. 따라서 자원을 요청 시 deadlock 가능성이 있으면 자원이 충분해도 할당해주지 않는다.

시스템이 safe state에 있으면 → no deadlock

시스템이 unsafe state에 있으면 → possibility of deadlock

 

2가지 경우의 avoidance 알고리즘

1. Single instance per resource types
   • Resource Allocation Graph Algorithm 사용점선 화살표는 claim edge라고 한다. 프로세스가 자원을 미래에 요청할 수 있다는 뜻이다. 요청하면 request edge로 바뀌고 자원이 release 되면 assignment edge는 다시 claim edge로 변한다.
   • 두번째 그림에서 생긴 request edge의 경우 P2가 R2를 요청해도 자원을 할당받지 못한다. 내어주게 된다면(assignment edge 변경 시) 세번째 그림과 같이 cycle이 형성되어 deadlock이 발생할 수 있게 되기 때문이다.

   • 

2. Multiple instances per resource types
   • Banker's Algorithm
     • 각 프로세스의 최대 요청 자원 수를 충족하는 시퀀스가 존재하므로 safe state (절대 deadlock이 생기지 않음)
     • 하지만 자원이 남아 돌아도 최대 요청이 가용 자원 수보다 적으면 주지 않기 때문에 비효율적

4-3. Deadlock Detection and Recovery

deadlock 발생은 그대로 놔두지만 그에 대한 detection routine을 두어 deadlock 발견 시 recovery 한다.

Deadlock Detection

1. resource types 당 Single instance인 경우
   • Resource Allocation Graph에서의 cycle이 곧 deadlock을 의미
   • Wait-for graph
     • 자원 할당 그래프에서 프로세스만으로 node 구성된 그래프를 말함
     • Wait-for graph에 사이클이 존재하는지 주기적으로 조사하는 Algorithm O(n^2) 동작
2. resource types 당 Multiple instances인 경우
   • Banker's Algorithm과 유사한 방법 활용

3. 

Recovery

• Process termination - 프로세스 죽이기
  1. deadlock에 연루된 프로세스들을 모두 죽임
  2. deadlock에 연루된 프로세스들을 하나씩 죽임 (deadlock이 없어질 때까지)
• Resource preemption - 자원 뺏기
  • deadlock에 연루된 프로세스들로부터 자원을 뺏는 방법
  • 비용을 최소화할 victim의 선정
  • victim (희생양 프로세스)를 하나 선정해서 자원을 강제로 뺏음 → safe state로 rollback하여 process를 restart
  • 동일한 프로세스가 계속 victim으로 선정되면 starvation 문제 발생 → cost factor(비용적 측면)에서 rollback 횟수 같이 고려해야 함.

4-4. Deadlock Ignorance

• 현재 대부분의 운영체제에서 채택한 방법으로, deadlock이 발생하지 않는다 생각하고 아무런 조치도 취하지 않는 것이다.
• deadlock은 매우 드물게 발생하기 때문에 조치를 취하는 것이 오히려 더 큰 오버헤드일 수 있기 때문이다.
• 만약 시스템에 deadlock이 발생한 경우 시스템이 느려지거나 프로세스가 멈춘 것을 사용자가 느낄 수 있으므로 일부 프로세스를 직접 죽이는 등의 방법으로 대처한다.
• UNIX를 포함한 대부분의 OS가 채택하고 있다.