[Operating System] DeadLock(교착상태)

DeadLock?

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

DeadLock의 발생 이유

• 프로세스1과 프로세스2가 자원1, 2를 모두 얻어야 하는 경우
• t1 : 프로세스 1이 자원 1을 얻음 / 프로세스 2가 자원 2를 얻음
• t2 : 프로세스 1은 자원 2를 기다림 / 프로세스 2는 자원 1을 기다림
• 현재 서로 원하는 자원이 상대방에게 할당되어 두 프로세스는 무한히 wait 상태에 빠짐
  • DeadLock 발생
• 주로 발생하는 이유
  • 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황 발생
  • 한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있음
  • 이때 프로세스는 대기 상태에 들어감
  • 대기 상태에 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 교착 상태 발생

DeadLock의 발생 조건

• DeadLock이 발생하기 위한 조건은 4가지가 있다.

1. 상호 배제(Mutual exclusion)
   
   •  
   • 한번에 프로세스 하나만 해당 자원을 사용할 수 있다.
   • 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.
2. 점유 대기(Hold and wait)
   • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
3. 비선점(No preemption)
   • 이미 할당된 자원을 강제로 빼았을 수 없다
4. 순환 대기(Circular wait)
   • 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

DeadLock 해결방법

• DeadLock의 해결법은 4가지로 분류할 수 있다.

1. 데드락이 발생하지 않도록 예방(prevention)하기
2. 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance)하기
3. 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복하기
4. 데드락은 정말 드물게 발생하므로 예방 또는 회피, 탐지를 하며 오버헤드를 발생시키는 것 보다 교착 상태를 발생시키고 필요에 따라 재부팅을 하는 무시(ignore) 방법

교착 상태 예방(Prevention)

• 교착 상태의 발생 조건 4가지 중 하나라도 발생하지 않도록 하는 것이 예방하는 방법
• 각각의 조건을 방지하여 데드락 발생 가능성을 차단
• 조건을 방지해서 데드락을 예방하는 방법은 시스템의 처리량이나 효율성을 떨어트리는 단점이 발생할 수 있음

1. 상호 배제 부정
   • 한 번에 여러 프로세스가 공유 자원을 사용할 수 있도록 한다
   • 추후 동기화 문제가 발생할 수 있음
2. 점유 대기 부정
   • 프로세스 실행에 필요한 모든 자원을 한번에 요구하고 허용할 때까지 작업을 보류
   • 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 함
   • 자원 낭비가 발생할 수 있으며, 기아 상태에 빠질 수 있음
3. 비선점 부정
   • 이미 다른 프로세스에 할당된 자원의 선점권이 없다고 가정할 때 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 함
   • 프로세스가 할당받을 수 없는 자원을 요청한 경우 기존에 가지고 있던 자원을 모두 반납하고 새 자원과 이전 자원을 소유할 수 있도록 대기 (자원 낭비 발생)
4. 순환 대기 부정
   • 자원을 순환 형태로 대기하지 않도록 일정한 한쪽 방향으로만 자원을 요구하도록 한다.

교착 상태 회피(Avoidance)

• 교착 상태가 발생하기 전 교착 상태를 예상하여 안전한 상태(Safe State)에서만 자원 요청을 허용하는 방법
  •  자원을 할당한 후에도 시스템이 항상 Safe state에 있을 수 있도록 할당을 허용하자는 것이 기본 특징
• 자원을 신중하게 할당하면 교착 상태를 회피할 수 있다.
• 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 그것을 안전 순서(safe sequence)라고 부른다.
• 교착 상태 회피를 위한 가정
  1. 프로세스의 수가 고정되어 있어야 함
  2. 자원의 종류와 수가 고정되어 있어야 함
  3. 프로세스가 요구하는 자원 및 최대 자원의 수를 알아야 함
  4. 프로세스는 반드시 자원을 사용 후 반납해야 함
• 교착 상태 회피를 위한 가정들은 현실성이 부족함
• 자원 요청이 있을 때마다 회피 알고리즘을 사용하는 것은 엄청난 오버헤드가 발생함

Safe State

• Safe Sequence가 존재하여 모든 프로세스가 정상적으로 종료할 수 있는 상태
• Safe Sequence는 교착 상태를 발생 시키지 않고 자원을 할당하는 순서를 의미

Unsafe State

• 교착 상태가 될 수 있는 상태
• Unsafe State가 되었다고 반드시 데드락이 되는 것이 아님

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

• 다익스트라가 제안한 기법
• 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래
• 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전 미리 결정된 모든 자원들의 최대 가능성 할당량을 가지고 Safe State에 들 수 있는지 여부를 검사 
• 안정 상태면 자원을 할당하고, 아니면 다른 프로세스의 자원 해지를 대기

자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)

• 자원과 프로세스에 대해 요청 간선과 할당 간선을 적용하여 교착 상태를 회피하는 알고리즘
• 프로세스가 자원 요청 시 요청 간선을 할당 간선으로 변경했을 때 사이클이 형성되는지 확인
• 사이클이 생성된다고 하여 무조건 교착 상태인 것은 아님
  • 자원에 하나의 인스턴스만 존재 시 교착 상태로 판정
  • 자원에 여러 인스턴스가 존재 시 교착 상태 가능성으로 판정
• 사이클이 생성되지 않으면 자원을 할당

교착 상태 탐지(Detection) & 회복(Recovery)

• 예방이나 회피를 사용하지 않을 때, 데드락이 발생할 수 있으니 회복하기 위해 데드락을 탐지하고 회복하는 알고리즘 사용
  • 교착 상태를 허용하고 발생하였다면 회복하는 방법
• 탐지
  • 자원 할당 그래프를 통해 교착 상태를 탐지
  • 자원 요청 시, 탐지 알고리즘을 실행시켜 그에 의한 오버헤드가 발생
  • 현재 시스템의 자원 할당 상태를 가지고 파악
• 회복
  • 교착 상태를 이르킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
  • 프로세스 종료
    1. 교착 상태의 프로세스를 모두 중지
    2. 교착 상태가 제거될 때까지 하나씩 프로세스 중지
  • 자원 선점 방법
    1. 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에 할당 (해당 프로세스는 중단)
    2. 우선 순위가 낮은 프로세스나 실행 횟수가 적은 프로세스 위주로 프로세스 자원 선점

 

 

 

출처

https://github.com/gyoogle/tech-interview-for-developer

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖

https://yoongrammer.tistory.com/67

교착상태(Dead Lock) 해결 방법

https://chanhuiseok.github.io/posts/cs-2/

[운영체제] 데드락(Deadlock, 교착 상태)이란?