[운영체제] 교착 상태 (Dead Lock, 데드락)

교착 상태(Dead Lock, 데드락)

• 두 개 이상의 프로세스들이 서로가 가진 자원을 무한정 기다리며 멈추어 있는 상태
• 프로세스 A는 자원 1을 가지고서 자원 2를 요구, 프로세스 B는 자원 2를 가지면서 자원 1을 요구

 

 

교착 상태 발생 조건

• 상호 배제(Mutual Exclusion)
  • 한번에 하나의 프로세스만이 공유 자원을 사용할 수 있어야 함
• 점유와 대기(Hold and Wait)
  • 모든 프로세스는 최소 하나의 자원을 점유하면서 다른 프로세스가 가지고 있는 자원을 기다리고 있어야 함
• 비선점(Non Preemption)
  • 다른 프로세스가 자신에게 할당된 자원을 모두 사용해 반환할 때까지 강제로 뺏어올 수 없어야 함
• 환형 대기(Circular Wait)
  • 공유 자원과 해당 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어야 함
  • 자신에게 할당된 자원을 점유하면서 앞 or 뒤 프로세스의 자원을 요구

 

 

교착 상태 해결 방안

1. 예방(Prevention): 교착 상태가 발생하지 않도록 발생 4가지 조건 중 하나를 제거하는 방법
2. 회피(Avoidance): 교착 상태의 발생 가능성을 인정하면서 적절히 피해가는 방법
3. 탐지(Detection): 교착 상태가 발생했는 지 점검하며 발견해내는 방법
4. 회복(Recovery): 교착 상태가 발생한 프로세스와 자원을 되살려내는 방법

 

1. 예방(Prevention)

• 상호 배제 조건 부정
  • 공유 자원을 여러개의 프로세스가 한번에 사용할 수 있도록 함
• 점유와 대기 조건 부정
  • 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 대기 과정을 없애거나 자원을 점유하지 않은 상태에서만 자원을 요구할 수 있도록 함
  • 자원 낭비 증가
• 비선점 조건 부정
  • 프로세스가 다른 자원을 요구할 때 이미 점유하고 있던 자원은 다른 프로세스가 선점할 수 있도록 함
  • 기아 상태 발생 가능
• 환형대기 조건 부정
  • 자원을 선형 순서로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 함
  • 모든 프로세스에 자원 할당 순서를 부여

 

2. 회피(Avoidance)

• 은행원 알고리즘(Banker's Algorithm)
  • 프로세스의 자원 할당량을 미리 파악해 최소한 하나의 프로세스에게 할당해줄 만큼의 자원은 CPU가 보유하고 있어야 한다는 개념 
  • 각 프로세스에게 자원을 할당했을 때 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전상태, 교착상태가 발생할 수 있는 상태를 불안전 상태라고 함
  • 특정 프로세스가 자원을 요청했을 때 해당 요청으로 시스템이 불안전 상태에 빠진다면 이를 거절하는 방식
  • 계속해서 안전상태를 유지해야하기 때문에 자원 사용률이 낮음
  • 프로세는 최대 자원 요구량을 미리 파악해야하며 자원을 반드시 순환시켜야 하는 부담
  • 자원의 양과 사용자(프로세스) 수가 일정해야 함

 

3. 탐지(Detection)

• 교착 상태 발견 알고리즘
  • Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색
  • 은행원 알고리즘에서 했던 방식과 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악
• 자원 할당 그래프 이용

 

4. 회복(Recovery)

• 프로세스 종료
  • 교착 상태에 있는 프로세스를 강제 종료
  • 모든 프로세스를 중단시키는 방법과, 하나씩 중단시키며 회복되는지 확인하는 방법이 있음
• 자원 선점
  • 교착상태에 있는 프로세스로부터 점유 자원을 선점(회수)하여 다른 프로세스에게 할당