[OS] 07. Deadlocks

교착상태(deadlock)

출처: Vectors Market

The Deadlock Problem

• Deadlock
  • 일련의 프로세스들이 서로 가진 자원을 기다리며 block 된 상태
• Resource(자원) 예) I/O device, CPU cycle, memory space, semaphore 등
  • 하드웨어, 소프트웨어 등을 포함하는 개념
  • 프로세스가 자원을 사용하는 절차
    • Request(요청), Allocate(획득), Use(사용), Release(반납)
• Deadlock Example 1
  • 시스템에 2개의 tape drive가 있다.
  • 프로세스 P1과 P2 각각이 하나의 take drive를 보유한 채 다른 하나를 기다리고 있다.
• Deadlock Example 2
  • Binary semaphore A and B
  

Deadlock 발생의 4가지 조건

Mutual exclusion (상호 배제)

• 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

No preemption (비선점)

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

Hold and wait (보유 대기)

• 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

Circular wait (순환 대기)

• 자원을 기다리는 프로세스 간에 사이클이 형성되어야 함
• 프로세스 P0, P1, …, Pn이 있을 때
  • P0은 P1이 가진 자원을 기다림
  • P1은 P2가 가진 자원을 기다림
  • Pn-1은 Pn이 가진 자원을 기다림
  • Pn은 P0이 가진 자원을 기다림

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

• Vertex
  • Process P (프로세스) = {P1, P2, …, Pn}
  • Resource R (자원) = {R1, R2, …, Rm}
• Edge
  • request edge Pi → Rj
  • assignment edge Rj → Pi

• 그래프에 cycle이 있으면 deadlock이 아님
• 그래프에 cycle이 있으면
  • 만약 자원 당 인스턴스가 하나밖에 없으면 cycle은 deadlock을 의미
  • 만약 인스턴스가 여러 개 있으면 deadlock 일 수도 있고 아닐 수도 있음
    (진행이 불가능하면 deadlock)

Deadlock의 처리 방법

현대 운영체제들은 Deadlock Ignorance를 채택하고 사람이 해결하도록 함
자주 발생하지 않기 때문에 미연 방지하는 것에 더 오버헤드가 걸림

Deadlock Prevention (미연 방지)

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

Mutual Exclusion

• 공유해서는 안되는 자원의 경우 반드시 성립해야함
  → 만족되지 않도록 하는 것이 불가능

Hold and Wait

• 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다. (자진해서 반납)
• 방법 1: 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
  (모든 것을 Hold → 자원 비효율성 생김)
• 방법 2: 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청

No Preemption

• 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
• 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작됨
• State를 쉽게 save하고 restore 할 수 있는 자원에서 주로 사용 (CPU, memory)

Circular Wait

• 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
• 예를 들어 순서가 3인 자원RiR_iRi​을 보유 중인 프로세스가 순서가 1인 자원RjR_jRj​을 할당 받기 위해서 우선RiR_iRi​을 release 해야 한다.

→ Utilization(이용률) 저하, throughput(성능) 감소, stavation 문제

즉, 생기지도 않을 Deadlock을 방지하기 위해 많은 제약 조건을 사용해서 위 문제가 생김

Deadlock Avoidance (미연 방지)

자원 요청에 대한 부가적인 정보를 이용해서 데드락의 가능성이 없는 경우에만 자원 할당 하며,
시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

• 프로세스가 평생 쓸 자원을 미리 알고 있는 경우, 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당
  • safe state → no deadlock
  • unsafe state → possibility of deadlock
    (이를 원천적으로 차단하는 것이 Deadlock Avoidance)
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별로 최대 사용량을 미리 선언하도록 하는 방법임
• safe state
  • 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
• safe sequence
  • 프로세스 sequence <P1P_1P1​,P2P_2P2​, …,PnP_nPn​>이 safe하려면Pi(1≤i≤n)P_i(1 \leq i \leq n)Pi​(1≤i≤n)의 자원 요청이 “가용 자원 + 모든 Pj(j<i)P_j(j<i)Pj​(j<i)의 보유자원”에 의해 충족 되어야 함
    • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
      • PiP_iPi​의 자원 요청이 즉시 충족될 수 없으면 모든Pj(j<i)Pj(j<i)Pj(j<i)가 종료될 때까지 기다린다.
      • Pi−1P_{i-1}Pi−1​이 종료되면PiP_iPi​의 자원 요청을 만족시켜 수행한다

Resource Allocation Graph Algorithm (Single instance per resource types)

• Claim edge(PiP_iPi​ →RjR_jRj​)란 프로세스가PiP_iPi​가 자원RjR_jRj​를 미래에 요청할 수 있음을 뜻함 (점선)
• 프로세스가 해당 자원 요청 시 request edge로 바뀜 (실선)
• RjR_jRj​가 release되면 assignment edge는 다시 claim edge로 바뀜

→ request edge의 assignment edge 변경 시 (점선 포함)

cycle이 생기지 않는 경우에만 요청 자원 할당

(cycle 생성 여부 조사 시 프로세스 수가 n일 때O(n2)O(n^2)O(n2) 시간이 걸림)

Banker’s Algorithm (Multiple instance per resource types)

• 5 processesPoP_oPo​,P1P_1P1​,P2P_2P2​,P3P_3P3​,P4P_4P4​
• 3 resource types A(10), B(5), and C(7) 인스턴스
• Snapshot at TImeT0T_0T0​

	Allocation	Max	Available	Need (Max-Allocation)
PoP_oPo​	A B C	A B C	A B C	A B C
PoP_oPo​	0 1 0	7 5 3	3 3 2	7 4 3
P1P_1P1​	2 0 0	3 2 2		1 2 2
P2P_2P2​	3 0 2	9 0 2		6 0 0
P3P_3P3​	2 1 1	2 2 2		0 1 1
P4P_4P4​	0 0 2	4 3 3		4 3 1

→ sequence <PoP_oPo​,P1P_1P1​,P2P_2P2​,P3P_3P3​,P4P_4P4​>가 존재하므로 시스템은 safe state

*즉, 최대 요청이 가용 자원을 넘어버리면 할당하지 않음 (늘 최악의 경우(최대 요청)를 가정하고 배분)
deadlock이 생길 가능성이 낮기 때문에 매우 비효율적
*

Deadlock Detection and recovery (점검 및 회복)

데드락 발생은 허용하되, 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover

• Deadlock 감지
  • Resource type 당 하나의 인스턴스밖에 없는 경우 자원할당 그래프에서 cycle이 곧 deadlock을 의미
  • Resource type 당 여러 인스턴스인 경우 Bankers algorithm과 유사한 방법 활용
  • 낙관적으로 생각하고 deadlock 감지 (자원 요청을 최대로 할 것이라고 가정은 안 함)
• Wait-for graph 알고리즘 (Resource type 당 하나의 인스턴스인 경우)
  • Wait-for graph
    • 자원할당 그래프의 변형
    • 프로세스만으로 node 구성
    • PjP_jPj​가 가지고 있는 자원을PkP_kPk​가 기다리는 경우PkP_kPk​ →PjP_jPj​
  • 알고리즘
    • Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
    • O(n2)O(n^2)O(n2)
  • Recovery
    • Process termination (프로세스를 종료시키는 방법)
      • deadlock에 연루된 모든 프로세스를 모두 사살
      • deadlock에 연루된 프로세스를 deadlock 없어질 때까지 하나씩 사살
    • Resource Preemption (deadlock에 연루된 프로세스로부터 자원을 뺏는 방법)
      • 비용을 최소화할 희생양 선정
      • safe state로 rollback 하여 process를 restart
      • Starvation 문제
        • 동일한 프로세스가 계속해서 희생양으로 선정되는 경우 (똑같은 패턴 발생)
        • cost factor에 rollback 횟수도 같이 고려

Deadlock Ignorance

데드락을 시스템이 책임지지 않고,

**UNIX, Windown를 포함한 대부분의 범용 OS가 채택

**

데드락이 일어나지 않는다고 생각하고 아무런 조치를 취하지 않음

• Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 오버헤드일 수도있음
• 만약 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것ㅇ르 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처

Uploaded by

N2T