교착상태 (deadlock)

목차

1. 교착 상태의 개요

2. 교착 상태 필요조건

3. 교착 상태 해결 방법

---

 

 

1. 교착 상태의 개요

1-1. 교착상태의 정의

 

교착상태: 2 개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 

작업을 더 이상 진행하지 못하는 상태

 

 

1-2 교착 상태의 발생

언제 발생하나? 

• 시스템 자원 - 다른 프로세스와 공유할 수 없는 자원을 사용할 때 
• 공유 변수 - 공유 변수를 사용할 때 
• 응용 프로그램(예: 데이터베이스)- 데이터의 일관성을 유지하기 위해 잠금을 사용할 때

 

1-3 자원할당 그래프

프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 

방향성이 있는 그래프로 표현한 것

예) 식사하는 철학자 문제

p1은 R1을 할당받았고, R4를 기다리는 중

이 문제에서 교착 상태가 발생하는 조건

• 철학자들은 서로 포크 공유 x
• 각 철학자는 다른 철학자의 포크 빼앗기 x
• 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크 기다림
• 자원 할당 그래프가 원형

 

---

2. 교착 상태 필요조건

다음 4 가지 조건이 모두 발생해야만 교착상태 발생 

•  상호 배제: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할수 없는
  배타적인 자원이어야 함
• 비선점: 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는
  비선점 자원이어야 함
• 점유와 대기: 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을
  기다리는 상태여야 함
• 원형 대기: 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 함

 

---

3. 교착 상태 해결 방법

3-1

• 교착 상태 예방: 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식
• 교착 상태 회피: 자원 할당량을 조절하여 교착 상태를 회피하는 방식
• 교착 상태 검출과 회복: 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 
  교착 상태가 발생하는지 확인. 만약 교착 상태가 발생하면 교착 상태 회복 단계가 진행

 

3-2 교착 상태 예방

• 상호 배제 예방- 독점적으로 사용할 수 있는 자원을 모두 없애버리는 방법
  -> 사실상 어려움
• 비선점 예방- 자원을 뺏기가 가능해지도록 
  -> 자원을 뺏긴 쪽은 아사 현상이 일어남 
• 점유와 대기 예방- 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하도록
  -> 단점:
  1. 자원의 활용성 떨어짐
  2. 많은 자원을 사용하는 프로세스가 상대적으로 불리
• 원형 대기 예방- 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당
  단점:
  1. 프로세스 작업 진행에 유연성이 떨어짐
  2. 자원의 번호를 어떻게 부여할 것인가? 
  
  

p2는 자원 2를 할당받은 상태이므로 자원1을 기다릴 수 없음.

 

 

3-3 교착 상태 회피

교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고 교착 상태가 발생하는
범위에 있으면 프로세스를 대기시킴

 

시스템이 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당한다.

불안정 상태가 커질수록 교착 상태가 발생할 가능성이 높아짐.

 

 

 

 

<은행원 알고리즘>

교착 상태 회피를 구현하는 대표적인 알고리즘

-> 대출 금액이 대출 가능한 범위 내이면 은행이 대출 허용, 그렇지 않으면 거부

 

가용 자원(시스템 내 현재 사용 가능한 자원) >= 각 프로세스의 기대 자원(앞으로 사용할 자원의 수)

-> 자원을 할당

 

 

 

<교착 상태 회피의 문제점>

• 시스템의 전체 자원 수가 고정적이어야 함
• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 함
• 자원이 낭비됨

 

 

 

3-4 교착 상태 검출

• 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시
• 교착 상태가 발견되면 이를 해결하기 위해 교착 상태 회복 단계를 밟음

 

 

<타임아웃을 이용한 교착 상태 검출>

• 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여
  처리하는 방법
• 타임아웃이 되면 프로세스가 종료됨

타임아웃을 이용한 방법

 

 

<데이터베이스에서 타임아웃의 문제>

 

데이터베이스에서 타임아웃으로 프로세스가 종료되면 일부 데이터의 일관성이 깨질 수 있음

-> 이를 해결 위해 체크포인트와 롤백 사용

• 체크포인트: 문제가 발생하면 저장된 상태로 돌아오기 위한 표시
• 롤백: 과거의 체크포인트로 되돌아가는 것

 

 

<자원 할당 그래프를 이용한 교착 상태 검출>

 

단일 자원을 사용하는 경우

-> 그래프에 사이클이 있으면 교착 상태 발생한 것

 

다중 자원을 사용하는 경우

-> 대기 그래프와 그래프 감소 방법을 이용하여 사이클을 찾음

 

• 대기 그래프: 자원 할당 그래프에서 프로세스와 프로세스 간에 기다리는 관계만 나타낸 그래프
• 그래프 감소: 대기 그래프에서 작업이 끝날 가능성이있는 프로세스의 화살표와 
  관련 프로세스의 화살표를 연속적으로 지워가는 작업

교착 상태 발생x

교착 상태 발생O

 

 

3-5 교착 상태 회복

교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제로 종료

• 교착 상태를 일으킨 모든 프로세스를 동시에 종료
• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
  1. 우선순위가 낮은 프로세스 먼저 종료
  2. 우선순위가 같다면 작업 시간이 짧은 프로세스 먼저
  3. 위의 두 조건이 같다면 자원을 많이 사용하는 프로세스 먼저

---