[운영체제] - 33강. 교착 상태 해결 방법

이 글은 한빛미디어 '혼자 공부하는 컴퓨터 구조 + 운영체제'를 공부하고, 추가적인 부분을 찾아 정리한 내용입니다.

---

교착상태를 회피, 예방 혹은 검출 후 회복하는 방법은 무엇이 있는가?

---

● 데드락 예방 (Prevention)

- 데드락 발생 원인 4가지 중 하나를 충족하지 못하게 하는 방법. 각각의 조건을 방지하여 데드락 발생 가능성을 차단한다.

 

1) 상호배제 조건 방지 :

- 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.

- 이론적으론 데드락을 차단시키지만, 자원을 상호 배제 시키지 않고 생기는 문제점이 더 크기 때문에 동기화 관련 문제가 발생할 가능성이 높다.

 

2) 점유 대기 조건 방지 : 

- 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류하여 나중에 다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 한다.

- 단 한 프로세스에 필요한 자원을 몰아주는 방식으로 동작하기 때문에 자원의 활용률이 낮아질 우려가 있다.

- 많은 자원을 사용해야하는 프로세스의 경우 적게 사용하는 프로세스보다 자원을 사용할 타이밍을 확보하기가 힘들어지기 때문에 기아현상을 야기할 우려가 있다.

 

3) 비선점 조건 방지 : 

- 높은 우선순위의 프로세스가 자원을 선점 할 수 있도록 한다.

- 일부 자원(예를 들어 CPU)에 대해선 효과적인 대안 방안이나 전 범위에 대해서 사용할 수는 없기 때문에 범용성이 떨어지는 방안이다. (예를 들면 프린터)

 

4) 순환 대기 조건 방지 : 

- 모든 자원에 번호를 붙여 오름차순으로 자원을 할당하여 한 방향으로만 자원을 요구 할 수 있도록 한다.

- 위의 3가지 방지에 비해 현실적이고 실용적이지만, 시스템 내의 수많은 자원에 번호를 붙이는 작업도 복잡하며, 특정 자원에 대해선 활용률이 떨어질 가능성이 있다.

 

---

● 데드락 회피 (Avoidance)

- 운영체제에서 데드락에 빠질 가능성을 검사후, 가능성이 없을 경우만 자원을 할당하는 방식.

- 안전 상태(Safe State) 와 불안전 상태(Unsafe State)로 데드락 여부를 판별한다.

 

- 데드락이 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태를 안전 상태(Safe State)라 하고, 프로세스의 특정 순서로 할당, 실행 및 종료를 했을 때 데드락이 발생하지 않은 안전한 순서를 안전 순서열(Safe Sequence) 라고 한다. 반대로 안전 순서열이 없고, 데드락이 발생할 가능성이 있는 상태를 불안전 상태(Unsafe State)라고 한다.

- 데드락 회피에는 대표적으로 은행원 알고리즘(Banker's Algorithm)이 있다.

 

---

 

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

- 에츠허르 다익스트라가 개발한 자원 할당 및 교착 회피 알고리즘.

- 사전에 설정된 최대 가능량의 자원 할당을 시뮬레이션 하여 안전성을 테스트한 후, 할당이 계속되도록 허용해야 하는지 결정한다.

 

※ 은행원 알고리즘 설명 블로그

https://wookkingkim.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-The-Bankers-Algorithm

[운영체제] The Banker's Algorithm

 

---

● 데드락 탐지 및 회복 (Detection & Recovery)

1) 탐지

- 운영체제가 데드락을 감지하는 별도의 프로그램을 백그라운드로 구동시켜, 데드락에 빠진 스레드 그룹이 있다면 이를 해제 시키는 방법.

- 데드락을 감지하는 백그라운드 작업이 늘 실행되므로 시스템에 많은 부담이 된다.

- 자원 할당 그래프를 통해 교착 상태를 탐지한다.

 

2) 회복

2.1) 자원 강제 선점 (Preemption)

- 데드락에 빠진 스레드 중 하나를 선택하고 이 스레드가 소유한 자원을 강제로 빼앗아 해당 자원을 기다리는 다른 스레드에게 할당하는 방법.

 

2.2) 롤백(Roll Back)

- 운영체제에서 데드락이 발생할 것으로 예측되는 스레드들에 대해 주기적으로 상태를 저장했다가, 데드락이 발생하면 가장 최근 저장해둔 상태로 복구 시키는 방법.

 

2.3) 스레드 강제 종료(Kill Process)

- 데드락에 빠린 스레드 중 하나를 강제 종료 시키는 방법.

 

---

● 데드락 무시(Ignore & Reboot)

- 데드락에 아무런 대비 없이 발생하도록 내버려 두는 방법.

- 타조 알고리즘을 사용하여 데드락을 무시한다.

 

※ 타조 알고리즘 (Ostrich Algorithm) : 데드락에 아무 대비없이 컴퓨터 시스템을 가동하고, 데드락이 발생하면 시스템을 재시작(Reboot)하거나 특정 스레드를 강제 종료하는 방법으로 해결

 

---

※ 참고자료

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

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

 

https://namu.wiki/w/%EB%8D%B0%EB%93%9C%EB%9D%BD

데드락 - 나무위키

 

https://wookkingkim.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-The-Bankers-Algorithm

[운영체제] The Banker's Algorithm

 

https://good-potato.tistory.com/63

[OS] 교착 상태(DeadLock)이란?