[CS] 데드락(DeadLock/교착상태)과 해결 방법

bagt13·어제
0

CS

목록 보기
12/12
post-thumbnail

🔴 데드락(교착상태)이란?

두 개 이상의 프로세스가 자원을 점유한 상태에서 서로가 점유한 자원을 서로에게 요구하고 있어서 그 프로세스들이 무한정으로 기다리고 있는 상태

이에 대한 해결 방법은 예방, 회피, 탐지 및 회복이 있다.


📚 데드락 발생의 4가지 필요 조건

아래의 4가지 조건이 모두 만족되는 경우 데드락이 발생할 가능성이 있다.
하나라도 만족하지 않으면 발생하지 않는다.

1. 상호 배제 (Mutual exclusion)

  • 한 리소스는 한 번에 한 프로세스만이 사용할 수 있다.
  • 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.

2. 점유와 대기(Hold and wait)

  • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.

3. 비선점 (No preemption)

  • 이미 할당된 자원을 강제로 빼앗을 수 없다.
  • 프로세스가 task를 마친 후 리소스를 자발적으로 반환할 때까지 기다려야 한다.

4. 환형 대기 (Circular wait)

  • 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
  • Hold and wait 관계의 프로세스들이 서로를 기다림


🟢 데드락(Deadlock)의 해결법

데드락의 해결법은 크게 3가지로 분류할 수 있다.

  1. 데드락이 발생하지 않도록 예방(prevention) 하기

  2. 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance) 하기

  3. 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복하기


1. 예방 (Prevention)

데드락의 발생조건 4가지 중 하나라도 발생하지 않게 하는 것

즉, 각각의 조건을 방지하여 데드락 발생 가능성을 차단한다.
하지만 이 방법은 자원의 낭비가 가장 심한 방법이다.

  1. 자원의 상호 배제 조건 방지
    • 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.
    • (그러나 추후 동기화 관련 문제가 발생할 수 있다)
  2. 점유 대기 조건 방지
    • 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 한다.
  3. 비선점 조건 방지
    • 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.
  4. 순환 대기 조건 방지
    • 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 한다.

2. 회피 (Avoidance)

교착상태가 발생할 가능성을 배제하지 않고 교착상태를 적절히 피해나가는 방법

  • 리소스 할당의 측면에서, 교착상태가 발생할 가능성이 있는 자원을 할당하지 않는다.
  • 자원을 할당한 후에도 시스템이 항상 Safe state(데드락이 발생하지 않는 안정 상태)에 있을 수 있도록 할당을 허용하자는 것이 기본 특징이다.
  • 주로 은행원 알고리즘(Banker's Algorithm)이 사용된다.

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

다익스트라가 제안한 기법으로, 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션 해서 Safe state에 들 수 있는지 여부를 검사한다.

즉, 대기중인 다른 프로세스들의 활동에 대한 교착 상태 가능성을 미리 조사하는 것이다.

  • 자원 할당량을 사전에 파악하고 데드락을 회피할 수 있도록 한다.
  • 그러나 은행원 알고리즘의 경우 미리 최대 자원 요구량을 알아야 하고, 할당할 수 있는 자원 수가 일정해야 하는 등 사용에 있어 제약 조건이 많고, 그에 따른 자원 이용도 하락 등 단점도 존재한다.

3. 탐지 및 회복 (Detection and Recovery)

교착상태가 발생 할 경우 탐지하여 회복한다

탐지

  • 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견한다.
  • 교착상태 발견 알고리즘자원 할당 그래프 등을 사용한다.
  • 자원 할당 그래프의 단점 : 자원을 요청할 때마다 탐지 알고리즘을 실행하면, 오버헤드가 발생한다.

회복

  • 교착상태를 발견했다면 회복을 진행한다.
  • 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복한다.
  1. 프로세스 종료 방법
    • 교착 상태의 프로세스 모두 중지
    • 교착 상태가 제거될 때까지 한 프로세스씩 중지
  2. 자원 선점 방법
    • 자원을 빼앗긴 프로세스는 강제 종류 이후 재시작
    • 교착 상태에 빠진 프로세스가 필요로 하는 자원을 강제로 가져옴
profile
주니어 백엔드 개발자입니다😄
post-custom-banner

0개의 댓글