[운영체제](반효경) 8강. Deadlock

The Deadlock Problem

 

• DeadLock
  • 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
• Resource(자원)
  • 하드웨어, 소프트웨어 등을 포함하는 개념
  • ex) I/O Device, CPU cycle, memory space, semaphore 등
  • 프로세스가 자원을 사용하는 절차(요청, 할당, 사용, 반납)
    • Request, Allocate, Use, Release
• 데드락 예시
  • 시스템에 2개의 테이프 드라이버가 있는데, 프로세스 P1과 P2가 각각 하나의 테이프 드라이버를 보유한 채 다른 하나를 기다리고 있을 때
  • Binary semaphores A and B

 

Deadlock 발생의 4가지 조건

 

• Mutual exclusion(상호 배제)
  • 매 순간 하나의 프로세스 만이 자원을 사용할 수 있음
• No preemption (비선점)
  • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
• Hold and wait(보유 대기)
  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
• Cicular wait(순환 대기)
  • 자원을 기다리는 프로세스 간에 사이클이 형성

 

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

 

좌측은 데드락, 우측은 데드락 아님

• 그래프에 cycle이 없으면 deadlock이 아니다
• 그래프에 cycle이 있으면
  • if only one instance per resource type, then deadlock(그림에서 점의 개수가 instance의 수)
  • if several instances per resource type, possibility of deadlock

 

Deadlock의 처리 방법

 

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

 

1. Deadlock Prevention(데드락의 4가지 조건 중 하나를 원천적으로 차단하는 방법)

 

• Mutual Exclusion
  • 공유해서는 안되는 자원의 경우 반드시 성립해야 함
• Hold and Wait
  • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다. (보유하고 있으면서 요청할때 데드락이 생기므로)
  • 방법 1: 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법(비효율적)
  • 방법 2: 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
• No Preemption(빼앗는 것을 허용한다 → Preemption 허용)
  • process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
  • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다
  • State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용 (CPU나 memory같은 자원이 해당됨)
• Circular Wait
  • 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
  • 예를 들어 순서가 3인 자원 R을 보유 중인 프로세스가 순서 1인 자원 R1을 할당받기 위해서는 우선 R1을 Release 해야 한다.
  • → Uitilization(이용률) 저하, Throughput(성능-처리량) 감소, Starvation 문제

 

2. Deadlock Avoidance(항상 sfae를 유지하는 보수적이고 매우 안전한 방법)

 

• 자원 요청에 대한 부가정보를 이용해서 자원할당이 deadlock으로 부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임
• safe state
  • 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
• safe sequence
  • 프로세스의 sequence < P1, P2, …, Pn >이 safe 하려면 Pi의 자원 요청이 “가용자원 + 모든 Pj의 보유 자원"에 의해 충족되어야 함
  • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
    • Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j<i)가 종료될 때까지 기다린다.
    • Pi-1이 종료되면 Pi의 자원 요청을 만족시켜 수행한다.
• 시스템이 safe state에 있으면 → 데드락이 발생하지 않음
• unsafe state에 있으면 → 데드락 발생 가능성

• Deadlock Avoidance
  • 시스템이 unsafe state에 들어가지 않는 것을 보장
  • 2가지 경우의 avoidance 알고리즘
    1. Single instance per resource types
       • Resource Allocation Graph Algorithm
    2. Multiple Instances per resource types
       • Banker’s Algorithm 사용

 

• Resource Allocation Graph Algorithm(자원당 인스턴스가 하나일 때)
  • Claim edge Pi → Rj
    • 프로세스 Pi가 자원 Rj를 미래에 요청할 수 있음을 뜻함(점선으로 표시)
    • 프로세스가 해당 자원 요청시 request edge로 바뀜(실선)
    • Rj가 release 되면 assignment edge는 다시 claim edge로 바뀐다
  • request edge의 assginment edge 변경 시 (점선을 포함하여) cycle이 생기지 않는 경우에만 요청 자원을 할당한다. → 데드락의 위험성을 조사하여 발생할 가능성이 없을때만 할당
  • Cycle 생성 여부 조사 시 프로세스의 수가 n일 때 O(n^2) 시간이 걸림

3번째 그림 → A cycle is formed(unsafe) 데드락은 아니지만, P1이 R2를 요청하면 데드락 발생할 가능성 있음

 

 

• Bankers Algorithm(자원 당 인스턴스가 여러개일 때)
  • 가정1. 모든 프로세스는 자원의 최대사용량을 미리 명시
  • 가정2. 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다
  • 방법(보수적으로, 절대 deadlock이 발생하지 않는 상황을 상정한다. 밑에 그림에서 P0의 요청에 따라 준다고해서 deadlock이 무조건 발생하는 것은 아니지만, 최악의 상황을 가정한다.)
    • 기본개념: 자원 요청 시 safe 상태를 유지할 경우에만 할당
    • 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택(그런 프로세스가 없으면 unsafe 상태)
    • 그런 프로세스가 있으면 그 프로세스에게 자원을 할당
    • 할당받은 프로세스가 종료되면 모든 자원을 반납
    • 모든 프로세스가 종료될 때까지 이러한 과정 반복

 

3. Deadlock Detection and Recovery

• Deadlock Detection
  • Resource type 당 single instance인 경우
    • 자원 할당 그래프에서의 cycle이 곧 deadlock을 의미
  • Resource type 당 multible instance인 경우
    • Banker’s algorithm과 유사한 방법 활용

 

1. Wait-for graph 알고리즘

• Resource type 당 single instance인 경우
• Wait-for graph
  • 자원 할당 그래프의 변형
  • 프로세스만으로 node 구성
  • Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk → Pj
• Algorithm
  • Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
  • O(n^2) - DFS/BFS

 

2. Multiple instane인 경우(Bankers 알고리즘과는 다르게 낙관적으로 자원의 분배를 예상한다 - 추가요청 가능량이 아니라, 실제 요청 자원량으로 판단)아무것도 요청하지 않은 프로세스의 자원을 반납시켜서 다른곳에 쓸수 있다고 낙관적으로 가정해서 판단한다.

아무것도 요청하지 않은 프로세스의 자원을 반납시켜서 다른곳에 쓸수 있다고 낙관적으로 가정해서 판단한다.

 

• Recovery 방법
  1. Process termination
     • Abort all deadlocked processes(데드락에 연루된 모든 프로세스를 kill)
     • Abort one process at a time until the deadlock cycle is eliminated(하나씩 kill)
  2. Resource Preemption(데드락에 연루된 프로세스의 자원을 뺏는 방법)
     • 비용을 최소화 할 victim의 선정
     • sfae state로 rollback하여 process를 restart
     • Starvation 문제
       • 동일한 프로세스가 계속해서 victim으로 선정되는 경우
       • cost factor에 rollback 횟수도 같이 고려

 

4. Deadlock Ignorance

 

• Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
  • Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
  • 만약, 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처
  • UNIX, Windows 등 대부분의 범용 OS가 채택