[운영체제] 교착상태(DeadLock)

교착 상태

---

교착 상태란 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상, 즉 잘못된 자원관리로 둘 이상의 프로세스 또는 스레드들이 아무것도 하지 않는 상태로 영원히 대기하는 상황. 한정된 자원을 둘 이상의 주체가 서로 동시에 사용하려고 기다리기 때문에 발생

 

교착상태는 식사하는 철학자 문제로 이해할 수 있다

교착 상태를 해결하기 위해서는
1. 교착 상태가 발생했을 때의 상황을 정확히 표현해보기
2. 교착 상태가 일어나는 근본적인 이유 이해하기

자원 할당 그래프

교착 상태 발생 조건 파악 가능
- 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능
- 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현
2. 사용할 수 있는 자원의 개수는 자원 사격형 내에 점으로 표현
3. 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

교착 상태가 일어난 자원 할당 그래프의 특징 -> 자원 할당 그래프가 원의 형태를 띄고 있다.

순환대기

교착 상태가 발생할 조건

1. 상호 배제(Mutual exclusion) - 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
2. 점유와 대기(Hold and Wait) - 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
3. 비선점(No preemption) - 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
4. 원형 대기(Circular wait) - 프로세스들이 원의 형태로 자원을 대기하는 상태

위 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않음
위 네 가지 조건을 모두 만족하면 교착 상태가 발생할 수 있음

교착 상태 해결 방법

교착 상태 해결 - 예방, 회피, 검출 후 회복

교착 상태 예방
- 애초에 교착 상태가 발생하지 않도록 교착 상태 발생 조건(상호배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없애버리기

- 상호배제를 없애면 모든 자원을 공유하게 만든다
- 이론적으로는 가능하지만 현실적으로는 어렵다

- 프린터 등과 같은 입출력 장치나 연산 결과를 저장하는 변수와 같이 동시에 건드리면 위험한 자원들이 존재하기 때문에 상호배제를 없애는 것은 어려운 일이다.

- 점유와 대기를 없애면 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
-> 자원의 활용률을 낮출 수 있는 방식

- 비선점 조건을 없애는 방식은 선점이 가능한 자원 (Ex.CPU)에 한에 효과적이지만, 모든 자원이 선점 가능한 것은 아니다.

- 이를테면 프린터와 같은 자원을 중간에 뺏으면 예상치 못한 결과가 나올 수 있다.

- 원형 대기 조건을 없애는 방식
- 위 방식들보다 현실적이고 효율적
- 모든 자원에 번호를 붙이고 오름차순으로 할당하면 원형 대기는 발생하지 않는다.
- 자원에 번호 붙이는 것은 어려운 작업
- 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다.

교착상태 예방은 교착 상태가 발생하지 않음을 보장할 수는 있지만 부작용이 발생한다.

교착 상태 회피

- 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주
- 교착 상태가 발생하지 않을 만큼 조심히 할당
- 배분할 수 있는 자원의 양을 고려하여 교착상태가 발생하지 않을 만큼만 자원 배분

- 안전 순서열(Safe sequence): 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
- 안전 상태(Safe state): 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태, 안전 순서열이 있는 상태
- 불안전 상태(Unsafe state): 교착 상태가 발생할 수도 있는 상태, 안전 순서열이 없는 상태

- 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식
- 교착 상태 회피는 항상 안전 상태를 유지하게끔 자원을 할당하는 방식이라고 할 수 있음

- 불안전 상태라고 해서 무조건 교착상태가 발생하는 것은 아님
- ex. 은행원 알고리즘

 

P2를 먼저 수행하면 안전 순서열을 만들 수 있다

안전순서열 X

교착 상태 검출 후 회복

- 교착 상태의 발생을 인정하고 사후에 조치하는 방식
- 프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복
- 선점을 통한 회복, 프로세스 강제 종료를 통한 회복

선점을 통한 회복
  - 교착 상태가 회복될 때까지 한 프로세스씩 자원을 몰아주는 방식

프로세스 강제 종료를 통한 회복
  - 교착 상태에 놓인 프로세스 모두 강제 종료 (-> 작업 내역을 잃을 수 있음)
  - 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료 (->오버헤드)

교착 상태 무시

- 타조 알고리즘

- 교착 상태가 발생하지 않을 것이라 가정하고 아무 대책을 취하지 않는 접근법

- 교착상태는 발생하지만 발생 가능성이 극히 낮고, 이를 피하기 위한 비용은 많이 지불해야함

- 교착상태가 발생하면 시스템 재시작 혹은 특정 프로세스/스레드 강제 종료

  - 관련 데이터를 잃을 수는 있으나 전체적으로 큰 손실을 일으키지는 않음

Put your head in the sand