출처 - https://github.com/jmxx219/CS-Study (opens in a new tab)

데드락 (DeadLock, 교착 상태)

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

주로 발생하는 경우

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

데드락 발생 조건

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

✔️ 상호 배제 (Mutual exclusion)

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

✔️ 점유 대기 (Hold and wait)

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

✔️ 비선점(No preemption)

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

✔️ 순환 대기(Circular wait)

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

데드락 처리

✔️ 예방(prevention)

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

방법

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

  • 자원을 한 번에 여러 프로세스가 쓸 수 있었으면 애초에 Deadlock이라는 얘기도 나오지 않았음

• 점유대기 부정 : 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않게 하면 됨

  • 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법 -> 중간에 추가로 필요한 자원이 없기 때문에 Deadlock 발생 X
    • 자원활용이 비효율적임
  • 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청

• 비선점 부정 : 자원을 강제로 뺏을 수 있게 함

  • 자원을 강제로 뺏을 수 있게 하면 Bug가 발생할 가능성이 있음
  • 상태가 save하고 restore되기 어려운 자원에는 적용 불가능함

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

  • 예를 들어서 1, 2, 3, 4, 5번의 자원이 있다고 가정할 때 5번을 획득하려면 1, 2, 3, 4번을 획득해야 획득할 수 있게 하는 방법
  • 자원의 낭비가 심해지고 자원의 이용률이 낮아지고 Starvation이 발생할 수 있음

특징

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

✔️ 회피(avoidance)

개념

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

방법

은행원 알고리즘 (Banker's algorithm)

• 다익스트라가 제안한 기법
• 어떤 자원의 할당의 할당허용 여부를 결정하기 전, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션 진행하여 safe state에 들 수 있는 여부 검사
• 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래
• 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
• 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
• 은행원 알고리즘 구조
  • available[i] : 운영체제가 프로세스에게 자원을 줄 수 있는 양 / i 번째 사용가능한 자원의 양
  • max[i][j] : 프로세스 최대요구량 / 프로세스 i가 자원 j를 최대 요청할 수 있는 양
  • allocation[i][j] : 프로세스 자원할당양 / 프로세스 i에게 자원 j를 할당한 양
  • need[i][j] : 프로세스의 자원 추가 요구량 / 프로세스 i가 자원 j를 추가 요청하는 양
  • finish[i] : i번째 프로세스가 요청하는 양을 운영체제가 만족할 수 있는지를 파악할 수 있는 불리언 배열

은행원 알고리즘 실행순서

1. request[i] <= need[i] 어떤 프로세스가 요청하는 양을 충족을 못시키면 오류발생
2. request[i] <= avaliable[i] 지금 할당할 수 있는 남은 양이 요청양을 커버할 수 있으면 실행, 없으면 대기
   (지금 할당할 수 있는 양이 없는거기 때문에 오류를 발생시키는 것이 아니라 대기만 시킨다.)
3. request[i]의 값이 available[i]에 더해지며 need[i]에 request[i]의 값이 빼지게 된다
4. 이러한 과정을 모든 프로세스에 대해 반복한 뒤 모든 finish[i]가 True라면 안정상태가 된다.

위와 같이 이미 할당된 양(allocation) / max(최대 필요한 양)이 있다고 할 때 프로세스가 완료되기 위해서 필요한 양(need)는 max - allocation이다.

p1 -> p3 -> p4 -> -> p0 -> p2 순으로 실행이 되는데 실행될 때마다 이미 사용 중이었던 allocation이 환원이 된다. 즉, p1이 실행되고 나면 avaliable에 2 0 0 이 더해져서 5 3 2가 되고 p3이 실행되서 available이 5 4 3이 되고.... 하는 식으로 해서 p2까지 실행이 완료되게 되는 것이 은행원 알고리즘이다.

특징

• 데드락의 발생을 막을 수 있음
• 높은 오버헤드
  • 항상 시스템을 감시하고 있어야 함
• 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

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