교착상태(Deadlock)에 대하여

해당 블로그의 내용은 학교에서 배운 내용을 개인적으로 정리한 내용이므로, 잘못된 부분이 있을 수도 있습니다. 

 

 

교착상태 (Deadlock)

두 개 이상의 프로세스가 서로의 작업이 끝나기만을 기다리고 있어 둘 다 영원히 끝나지 않는 상황을 가리킨다.

 

Blocked / Asleep state

• 프로세스가 특정 이벤트를 기다리는 상태
• 프로세스가 필요한 자원을 기다리는 상태

Deadlock state

• 프로세스 발생 가능성이 없는 이벤트를 기다리는 경우
  • 프로세스가 deadlock 상태에 있음
• 시스템 내에 deadlock 에 빠진 프로세스가 있을 경우 
  • 시스템이 deadlock 상태에 있음

 

자원의 종류 (Types of Resources)

• 일반적 분류
  • 하드웨어 리소스(Hardware resources) vs 소프트웨어 리소스(Software resources)
• 다른 분류법
  • 선점 가능 여부에 따른 분류
  • 할당 단위에 따른 분류
  • 동시 사용 가능 여부에 따른 분류
  • 재사용 가능 여부에 따른 분류

선점 가능 여부에 따른 분류

• 선점적 자원 (Preemptible resources)
  • 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원
  • Processor, memory 등 
• 비 선점적 자원 (Non-preemptibel resources)
  • 선점 당하면, 이후 진행에 문제가 발생하는 자원
    • Rollback, restart 등 특별한 동작이 필요
  • Disk Drive 등

할당 단위에 따른 분류

• 전체 할당 자원 (Total allocation resources)
  • 자원 전체를 프로세스에게 할당
  • Processor, disk drive 등
• 부분 할당 자원 (Partitioned allocation resources)
  • 하나의 자원을 여러 조각으로 나누어 여러 프로세스들에게 할당
  • Memory 등

할당 단위에 따른 분류

• 독점 할당 자원 (Exclusive allocation resources)
  • 한 순간에 한 프로세스만 사용 가능한 자원
  • Processor, memory, disk drive 등
• 공유 할당 자원 (Shared allocation resources)
  • 여러 프로세스가 동시에 사용 가능한 자원
  • Program(SW), 공유 데이터 등

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

• 연속적 재사용 자원 (SR, Serially reusable resources)
  • 시스템 내에 항상 존재 하는 자원
  • 사용이 끝나면, 다른 프로세스가 사용 가능
  • Processor, memory, disk drive, program
• 소모적 자원 (CR, Consumable resources)
  • 한 프로세스가 사용한 후에 사라지는 자원
  • signal, message

 

교착 상태(Deadlock)와 자원 종류(Resource type)

• Deadlock을 발생시킬 수 있는 자원의 형태
  • 비 선점적 자원
  • 독점 할당 자원
  • 연속적 재사용 자원
• CR을 대상으로 하는 Deadlock Model
  • 너무 복잡!

Deadlock Model (표현법)

 

Graph Model

Graph Model

• Node
  • 프로세스 노드(P1, P2), 자원 노드(R1, R2)
• Edge
  • R >> P 자원 R이 프로세스 P에 할당됨
  • P >> R 프로세스 P가 자원 R을 요청 (대기 중)

State transition Model

 

Deadlock 발생 필요 조건

• 자원의 특성
  • 독점적 자원
  • 비선점적 자원
• 프로세스의 특성
  • 자원을 하나 Hold하고 다른 자원을 요청하는 경우
  • 순환 대기(Circular wait)

 

Deadlock Solution

• 교착상태 예방
• 교착상태 회피
• 교착상태 탐지 복구 

교착상태 예방 (Prevention)

• 4개의 Deadlock 발생 필요 조건 중 하나를 제거
• Deadlock이 절대 발생하지 않음
• 모든 자원을 공유 허용 (독점적 자원에 대한 예방)
  • 현실적으로 불가능
• 모든 자원에 대해 선점 허용 (비선점적 자원에 대한 예방)
  • 현실적으로 불가능
  • 유사한 방법
    • 프로세스가 할당 받을 수 없는 자원을 요청한 경우
      • 기존에 가지고 있던 자원을 모두 반납하고 작업 취소
      • 이후 처음부터 다시 시작
      • 심각한 자원 낭비 발생
      • 비현실적!
• 필요 자원 한번에 할당 (자원을 가지고 있는 상태에서 요청하는 경우 예방)
  • 자원 낭비 발생
    • 필요하지 않은 순간에도 가지고 있음
  • 무한 대기 현상 발생 가능 
• 순환 대기 예방
  • 자원들에게 순서 부여
  • 프로세스는 순서의 증가 방향으로만 자원 요청 가능
  • 자원 낭비 발생

 

교착상태 회피 (Avoidance)

• 시스템의 상태를 계속 감시
• 시스템이 Deadlock 상태가 될 가능성이 있는 자원 할당 요청 보류
• 시스템을 항상 safe state로 유지
• Safe state
  • 모든 프로세스가 정상적 종료가 가능한 상태
• Unsafe state
  • Deadlock 상태가 될 가능성이 있음
  • 반드시 발생한다는 의미는 아님
• 가정
  • 프로세스의 수가 고정됨
  • 자원의 종류와 수가 고정됨
  • 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
  • 프로세스는 자원을 사용 후 반드시 반납한다. 
  • ** 실용적이진 않음

 

다익스트라 알고리즘 (Dijkstra's Algorithm)

• 은행원(Banker's) 알고리즘
  • 간단한 이론적 기법
  • 가정
    • 한 종류의 자원이 여러 개
  • 시스템을 항상 safe state로 유지
    • 현재 상태에서 안전 순서가 하나 이상 존재하면 안전 상태

Habermann's Algorithm

• 다익스트라 알고리즘의 확장
• 여러 종류의 자원 고려
• 시스템을 항상 safe state로 유지

• Deadock의 발생을 막을 수 있음
• 높은 오버헤드(overhead)
  
  • 항상 시스템을 감시하고 있어야 한다.
• 적은 자원 운용 
  • Safe state 유지를 위해 사용 되지 않는 자원이 존재
• 실용적이지 않음

 

교착상태 탐지 (Detection)

• Deadlock 방지를 위한 사전 작업을 하지 않음
  • Deadlock 발생 가능
    • 발생 시 Recovery 과정이 필요
• 주기적으로 deadlock 상태 확인

RAG, Resource Allocation Graph

• Deadlock 검출을 위해 사용
• Directed graph G = (N, E)
  • N = { Np, Nr }
    • Np 는 프로세스들의 집합
    • Nr 은 자원들의 집합 
  • Edge는 Np 와 Nr 사이에만 존재
    • e = (Pi, Rj) 자원 요청 
    • e = (Rj, Pi) 자원 할당
  • Rk = k type의 자원
  • Tk = Rk 의 단위 자원의 수
  • | (a,b) | = (a, b) edge의 수

• Graph reduction
  • 주어진 RAG에서 edge를 하나씩 지워가는 방법 
  • Completely reduced
    • 모든 edge가 제거 됨
    • Deadlock에 빠진 프로세스가 없음
  • Irreducible
    • 지울 수 없는 edge가 존재
    • 하나 이상의 프로세스가 deadlock 상태
  • Sink(Unblocked process)를 찾고 연결된 모든 edge를 제거 
  • 더 이상 sink가 없을 때까지 반복
  • 최종 그래프에서 edge의 남은 갯수를 보고 교착상태 여부 판별
  • High overhead
    • 검사 주기에 영향을 받음
    • Node의 수가 많은 경우
  • 낮은 오버헤드 교착상태 탐지 방법
    • Case-1) 단일-유닛 자원들 
      • 사이클 탐지
    • Case-2) 단일-유닛 요청 

 

교착상태 복구 (Recovery)

• Deadlock을 검출 한 후 해결하는 과정
• 교착상태 복구 방법
  • 프로세스 종료 (Termination)
    • Deadlock 상태에 있는 프로세스 중 일부를  종료 시킴
    • 강제 종료된 프로세스는 이후 재시작됨
    • 종료 시킬 Deadlock 상태의 프로세스 선택
    • Termination cost
      • 낮은 종료 비용 프로세스 먼저 
    • 최소비용 복구
  • 자원 선점
    • Deadlock 상태 해결 위해 선점할 자원 선택
      • Deadlock 상태가 아닌 프로세스가 종료될 수도 있음
    • 선정된 자원을 가지고 있는 프로세스에서 자원을 빼앗음
      • 자원을 빼앗긴 프로세스는 강제 종료됨

Checkpoint - restart method

• 프로세스의 수행 지점 중 특정 지점(Checkpoint)마다 문맥(context)을 저장
• Rollback을 위해 사용 
  • 프로세스 강제 종료 후, 가장 최근의 checkpoint에서 재시작 

 

 

ㅇ