[운영체제] Deadlock

🧩 Deadlock

Deadlock: 두개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태

🧩 Deadlock이 발생하기 위한 4가지 조건

1. 상호배제, Mutual Exclusion: 자원은 한번에 한 프로세스만 사용가능함

• 레이스 컨디션의 문제를 해결하기 위해 두 개 이상의 프로세스 혹은 스레드가 동시에 한 공유 자원에 접근할 수 없도록하여 한 자원에 한 스레드만 접근할 수 있게 하는 것
• 자원에 대한 배타적 통제권 > 해당 자원을 오직 나만 쓰겠다는 상황
• 어느 스레드가 자원을 독점적으로 사용 > 다른 스레드가 자원에 접근하려고 락을 획득하기 위해 무한 대기 상황 발생 가능

2. 점유상태로 대기, Hold and wait: 어떤 프로세스가 최소 하나의 자원을 점유하고 다른 프로세스가 사용하는 자원을 할당받기 위해 대기

• 공유 자원에 락을 획득하여 점유하고 있는 상태 & 다른 자원의 락을 획득하기 위해 대기하고 있는 상황
• 발생할 수 있는 상황이 여러개의 자원을 동시에 써야하는 경우, 락을 획득한 자원에 대한 처리는 끝났는데 남은 자원의 락을 다른 스레드가 가지고 해제하지 않아서 무한정 대기
• 자신이 점유하고 있는 락도 해제해줘야 그 락을 획득하기 위해 기다리고 있는 다른 스레드들이 자원에 접근하여 처리를 할 수 있을텐데 락을 획득할 수 없으니 무한정 대기할 수 밖에 없는 상황

3. 선점 불가, No preemption: 다른 프로세스가 사용중인 자원을 강제로 뺏을 수 없음

• 다른 프로세스/스레드가 자원을 선점하고 있어서 자원을 뺏어올 방법이 없는 것
• 만일 어느 스레드가 공유 자원의 락을 획득하여 선점하고 있다면 그 공유 자원에 접근해야 하는 다른 스레드들은 아무리 잠깐 처리하면 끝나는 상황이라도 락을 빼앗을 방법이 없기 때문에 무한정 대기

4. 순환성 대기, Circular wait: 프로세스A가 프로세스B가 사용중인 자원을 할당받기 위해 대기하고 프로세스B는 프로세스A의 자원을 할당받으려 대기중

• 프로세스가 어느 자원을 점유하고 있고 다른 자원을 요청하여 대기하고 있는데 순환적으로 이러한 구조를 갖고 있는 것
• 즉, 점유 상태로 대기가 순환적으로 발생한 상황으로 볼 수 있는데 락을 해제하고 락을 획득하는게 순차적으로 잘 돌아가면 좋겠지만 어느 순간 모든 프로세스가 락을 획득하려고 대기하여 모든 프로세스가 무한대기에 놓인 상황이 발생할 수 있음

🧩 4가지 중 3가지만 충족하면 Deadlock이 발생하지 않는가?

발생하지 않음.

4가지 중 한가지라도 제외하는 것은 Deadlock 예방 방법임

🧩 Deadlock 예방 방법

1. 교착 상태 예방: 교착상태 발생조건 중 하나 이상을 제거

각각의 조건을 방지(부정)하여 데드락 발생 가능성 차단

종류

• 자원의 상호 배제 조건 방지: 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 함
  • 어떤 자원들은 근본적으로 공유가 불가능함
  • 추후 동기화 관련 문제가 발생할 수 있음
• 점유 대기 조건 방지: 자원을 요청할 때 다른 자원들을 점유하지 않고 있다는 것을 반드시 보장해야 함
  • 프로세스가 실행되기 전 필요한 모든 자원을 할당
  • 프로세스가 자원을 점유하지 않은 상태에서만 자원을 요청할 수 있도록 함
  • 단점:
    • 많은 자원이 할당 후 오랫동안 사용되지 않음 > 자원 이용률 감소
    • 기아 상태 가능성
• 비선점 조건 방지: 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정
  • 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 요청한 자원을 사용 가능한지 검사
    • 사용 가능하다면 점유하고 있는 자원 반납
    • 요구한 자원을 사용하기 위해 기다리게 함
• 순환 대기 조건 방지: 자원을 순환형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 함
  • 자원에 고유번호 할당 > 번호 순서대로 자원 요구하도록 함
  • 각 프로세스는 현재 점유 중인 자원의 고유 번호를 기준으로 앞/뒤 중 한 방향으로만 자원 요구

단점:

• 시스템의 처리량이나 효율성을 떨어트림
• 제한적인 방법: 자원 효율성 떨어짐
• 비용이 많이 듬

2. 교착상태 회피: 교착상태가 발생하기 전 교착상태를 예측하고 회피하는 방법

• Safe sequence, safe state (안정 상태): 시스템의 프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해줄 수 있는 상태
• 불안정 상태: 안정상태가 아닌 상황
  • 데드락 발생 가능성이 있는 상황
  • 교착 상태가 불안정 상태의 부분집합
• 자원을 할당한 후에도 시스템이 항상 safe state에 있을 수 있도록 할당을 허용
  • 사전검사를 통해 자원 할당 후에도 안정상태면 자원 할당
  • 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기
• Banker's algorithm: 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션해서 safe state에 들 수 있는지 여부 검사
  • 대기중이 다른 다른 프로세스의 활동에 대한 교착상태 가능성을 미리 조사
• 자원 할당 그래프 알고리즘, Resource Allocation Graph Algorithm
  • 자원이 하나일 때 사용
  • 자원 할당 그래프의 사이클이 존재하는지 확인
  • 사이클이 존재하면:
    • 자원 유형에 하나의 사례만 있으면 교착상태
    • 자원 유형에 여러 사례가 있으면 교착상태 가능성

3. 교착상태 탐지, 복구

• 탐지: allocation, request, available 등으로 시스템에 데드락이 발생했는지 여부 탐색
  • 현재 시스템의 자원 할당 상태를 가지고 파악
  • 자원 할당 그래프를 통해 탐지 > 사이클이 없을 때만 자원 할당
• 회복: 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복하는 것
  • 프로세스 종료
    • 교착 상태에 빠진 모든 프로세스를 중단시키는 방법: 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있음
    • 교착 상태가 제거될때까지 한 프로세스씩 중지
      • 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있음
  • 자원 선점하기
    • 교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스는 일시정지
    • 우선순위가 낮은 프로세스, 수행된 횟수가 적은 프로세스 등을 위주로 프로세스의 자원을 선점
      • 희생자 선택: 어느 자원/프로세스들이 먼저 선점될 것인가?
        • 비용 최소화를 위해 각 프로세스가 점유하고 있는 자원의 수 & 프로세스가 지금까지 실행하는데 소요한 시간과 같은 매개변수를 고려하여 선택
      • 후퇴: 프로세스로부터 자원을 선점하려면 그 프로세스를 어떻게 해야하는가?
        • 안전 상태 결정이 어렵기 때문에 프로세스를 중지시키고 재시작
      • 기아상태: 기아상태를 발생하지 않게 어떻게 보장할 것인가?
        • 희생자를 선택할 때 주로 비용에 근거하기 때문에 동일한 프로세스가 항상 희생자로 선택될 수 있음
        • 이 프로세스는 일을 수행하지 못하고 기아상태가 되기 쉬움
        • 희생자를 선택할 때 한정된 시간동안에만 희생될 것을 보장해야 함

단점:

• 어느 시점에서 교착 상태를 탐지해야 하는지 알 수 없음 > 주기적으로 알고리즘을 실행해야 함
  • 비용이 큼 > 실용적이지 않음

4. 교착상태 무시: 교착상태를 무시하고 특별한 조치를 취하지 않는 방법

• 교착상태의 발생확률이 낮으면 효율적
• 교착상태 발생시 프로세스 종료 또는 자원 선점으로 회복
• UNIX, Windows 등 대부분의 운영체제가 사용하는 방법

🧩 현대 OS에서 Deadlock을 처리하지 않는 이유

• 다른 처리방법과 비교해 비용이 적게듬
• 많은 시스템에서 교착 상태는 드뭄 > 처리에 대한 부가적인 비용은 그만한 가치가 없음

🧩 Wait Free와 Lock Free

Wait free

• per-thread progress
• guarantees that every call finishes its execution in a finite number of step
• Lock free + 다른 스레드와 충돌해도 모두 딜레없이 완료되어야 함
• 각 스레드/프로세스가 다른 스레드/프로세스의 진행과 독립적으로 진행되도록 보장
  • 다른 스레드/프로세스가 완료될 때까지 기다리지 않고 동작을 완료할 수 있음
  • 다른 스레드/프로세스의 진행률과 독립적
• 다른 스레드의 방해가 없음
• 대기 없는 알고리즘
• 주로 응답 시간을 예측/보장해야 하는 고성능 실시간 시스템에 사용
• 유한한 루프를 돌아 루프를 종료해야 함

Lock free

• system-wide progress
• guarantees that infinitely often some method call finishes in a finite number of steps
• lock을 사용하지 않는다
• 멀티스레드에서 동시 호출해도 정확한 결과 보증
• 호출이 다른 스레드와 충돌하면 적어도 하나의 승자가 존재. 그 승자는 딜레없이 완료
• 다른 스레드에 의해 방해 받아 기아 상태 발생 가능
• wait free 알고리즘보다 진행에 대한 보장이 약함
• 모든 스레드/프로세스가 다른 스레드/프로세스와 독립적으로 진행된다는 보장은 없음
  • 일부 스레드/프로세스가 일시적으로 차단될 가능성 존재
• 주로 응답 시간의 예측 가능성보다 시스템의 성능이 더 중요한 상황에서 사용

---

참고:

• 데드락(Deadlock)이란? 데드락의 발생조건과 해결방안
• [운영체제] 교착상태, 데드락 : Deadlock
• [OS] 교착상태 해결 방법 예방, 회피, 탐지