데드락.md

데드락 (DeadLock, 교착 상태)

• 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
• 무한히 다음 자원을 기다리게 되는 상태
  • 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태
• 한정된 자원을 여러 곳에서 사용하려고 할 때 발생

주로 발생하는 경우

• 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황
  • A 프로세스가 자원A 요청 → 동시에 자원A 사용 불가 한 상태 → A프로세스가 대기 상태로 들어감
  • 이때 대기상태로 들어간 프로세스들이 실행상태로 변경될 수 없을 때 교착 상태 발생

데드락 발생 조건

4가지 모두 성립해야 발생 (하나라도 성립하지 않을 경우 데드락 해결 가능)

✔️ 상호 배제 (Mutual exclusion)

: 자원은 한번에 한 프로세스만 사용 가능

✔️ 점유 대기 (Hold and wait)

: 최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스 존재

✔️ 비선점(No preemption)

: 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 뺏을 수 없음

✔️ 순환 대기(Circular wait)

: 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

데드락 처리

✔️ 예방(prevention)

교착 상태 발생 조건 중 하나를 제거하면서 해결

방법

• 상호배제 부정 : 여러 프로세스가 공유 자원 사용

  • 현실적으로 불가능

• 점유대기 부정 : 프로세스 실행전 모든 자원을 할당

  • 자원 낭비 발생
    • 필요하지 않은 순간에도 가지고 있음
  • 무한대기 현상 발생 가능

• 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납

  • 현실적으로 불가능

• 순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구

  • 자원들에게 순서 부여
  • 프로세스는 순서의 증가 방향으로만 자원 요청 가능
  • 자원 낭비 발생

특징

• 4개의 데드락 발생 필요 조건 중 하나를 제거한다면, 절대 발생하지 않음
• 심각한 자원 낭비 발생
• 비현실적

✔️ 회피(avoidance)

개념

• 시스템의 상태를 계속 감시
• 시스템이 데드락 상태가 될 가능성이 있는 자원 할당 요청 보류
• 시스템을 항상 Safe state로 유지
  • Safe state : 모든 프로세스가 정상적으로 종료 가능한 상태

방법

• 은행원 알고리즘 (Banker's algorithm)
  • 다익스트라가 제안한 기법
  • 어떤 자원의 할당의 할당허용 여부를 결정하기 전, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션 진행하여 safe state에 들 수 있는 여부 검사
  • 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래
  • 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
  • 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기

특징

• 데드락의 발생을 막을 수 있음
• 높은 오버헤드
  • 항상 시스템을 감시하고 있어야 함
• Safe state 유지를 위해 사용되지 않는 자원 존재
• 실용적이지 못함
  • 가정이 필요함
    • 프로세스, 자원 수 고정
    • 필요한 최대 자원 수를 알고 있음

✔️ 탐지(detection)

개념

• 데드락 방지를 위한 사전 작업을 하지 않음
  • 데드락 발생 가능
• 주기적으로 데드락 발생 확인
  • 시스템이 데드락 상태인지 확인
  • 어떤 프로세스가 데드락 상태인지 확인
• Resource Allocation Graph (RAG) 사용

Resource Allocation Graph (RAG)

• 데드락 검출을 위해 사용
• 방향성(directed)을 가지고 이분 그래프(bipatite graph) 사용
• Graph Reduction 으로 데드락 판별
  • 주어진 RAG에서 edge를 하나씩 지워감
  • Complete reduced : 모든 edge가 제거 되었다면 데드락 X
  • Irrducible : 지울 수 없는 edge가 존재한다면 데드락 O
• RAG는 높은 오버헤드를 가짐
  • 주기적인 검사 필요로, 검사 주기에 영향을 받음
  • 노드 수가 많은 경우 오버헤드 증가

데드락 회피(avoidance)와 탐지(detection)

• 데드락 회피
  • 최악의 경우를 생각
    • 데드락이 일어날 경우를 고려하여 회피
  • 데드락이 발생하지 않음
• 데드락 탐지
  • 최선의 경우를 생각
    • 현재 상태만 고려해 데드락이 발생하는가를 파악
  • 데드락이 발생할 수 있음
  • 데드락 발생 시 Recovery과정이 필요

✔️ 복구(recovery)

개념

• 데드락을 검출한 후 해결하는 과정

방법

• Process terminate

  • 데드락 상태에 있는 프로세스를 종료시킴

  • 강제 종료된 프로세스는 이후 재시작 됨

  • 종료 방법

    1. 데드락의 원인이 되는 프로세스를 모두 종료
    2. 한번에 하나의 프로세스만 종료시키면서 데드락이 풀리는지 확인 (높은 오버헤드)

  • 종료시킬 프로세스 선택 요인

    1. 프로세스 우선순위
    2. 프로세스 수행 시간, 일을 끝마치기까지 남은 시간
    3. 프로세스가 점유하고있는 자원 타입과 양 (회복하기 쉬운 자원인지)
    4. 프로세스가 종료하기까지 남은 자원의 수
    5. 얼마나 많은 수의 프로세스를 같이 종료시켜야하는지
    6. 프로세스가 interactive인지 bath형태인지

• Resource preemption

  • 데드락 상태 해결을 위해 프로세스의 자원을 선점하는 방법
    1. 희생 프로세스 선정
       • 희생 비용을 최소화하기위해 어느 프로세스의 어떤 자원을 뺏을지 결정
    2. 롤백
       • 어떤 프로세스로부터 자원을 뺏어오면 자원을 뺏긴 프로세스는 나중에 safe state로 롤백하고 다시 재실행 해줘야함
       • 혹은 처음 상태로 되돌림
       • Checkpoint-restart method
         • 프로세스의 수행 중 특정 지점(check point)마다 context 저장
         • 롤백을 위해 사용
           • 프로세스 강제 종료 후, 가장 최근의 check point에서 재시작
    3. 기아현상
       • 선점횟수에 가중치를 부여해 선점이 많이된 프로세스에게 우선권을 줘 기아현상 방지

Wait free 와 Lock free

Wait-free와 Lock-free는 모두 멀티스레딩 환경에서 공유 자원에 대한 동시 접근을 처리하는 기술

Wait-free는 모든 스레드가 동시에 진행될 수 있는 것에 비해, Lock-free는 일부 스레드가 블로킹될 가능성이 있지만, 구현이 더 쉽고 성능이 높은 경우가 많음.

공통점

• 스레드가 락을 획득하거나 해제하는 데 소비되는 시간이 줄어듦
• 락 경쟁으로 인한 병목 현상이 줄어들어 여러 스레드가 효율적으로 동시에 실행될 수 있음
• 무한 대기 상황을 방지함으로써 데드락 문제 해결

Wait free

• 개념
  • 모든 스레드가 동시에 진행
  • 하나의 스레드가 멈춰도 다른 스레드는 계속 진행 가능
• 특징
  • 어떤 스레드도 블로킹되지 않음
• 단점
  • 구현이 복잡하고 어려움
    • 복잡성으로 인해 정확성을 증명하는 것이 어려움
  • Lock-Free에 비해 더 많은 오버헤드 발생 가능
• 장점
  • 모든 스레드가 한정된 시간 내에 진행 가능

Lock free

• 개념
  • 항상 하나 이상의 스레드가 진행할 수 있음을 보장
• 특징
  • 공유 자원에 대한 동시 접근을 락 없이 원자적 연산으로 처리
• 단점
  • 일부 스레드가 블로킹될 가능성 있어 높은 지연시간 발생 가능
• 장점
  • 비교적 쉬운 구현
  • 하나 이상의 스레드가 진행 가능함을 보장
  • 스레드 간 상호작용 없이 안전하게 공유 자원 사용 가능