교착 상태 해결 방법
본 설명은 책 “그림으로 배우는 구조와 원리 운영체제 개정 3판”를 읽으며 제 나름대로 해석하고 정리해 보았습니다.😉
교착 상태 문제를 해결하는 방법은 크게 네가지이다.
- 예방 (Prevention) : 교착 상태가 생길 조건을 없애는 것 (4가지 조건 중 하나를 부정)
- 회피 (Avoidance) : 교착 상태의 발생 가능 성을 배제하지 않고 적절히 회피한다.
- 탐지 (detaction) : 교착 상태를 허용하지만 상태를 탐지하고 다시 회복하는 방법
- 무시: 그냥 무시하고 오히려 교착상태를 해결하는 것 보다 부딪히는게 비용이 덜 들때 사용.
여기서, 우리는 예방, 회피, 탐지 세가지 방법에 대해서 알아볼것이다.
1. 교착 상태 예방
교착 상태 예방은 교착 상태가 발생할 수 있는 네가지 조건 중 하나라도 발생하지 않도록 하여 이를 예방하는 것이다. 따라서 교착 상태는 다음 네가지 방법으로 예방할 수 있다.
- 자원의 상호배제 조건 방지
- 점유와 대기 조건 방지
- 비선점 조건 방지
- 순환(환형) 대기 조건 방지
그럼 지금부터 차례 차례 하나씩 이 조건을 살펴보자.
1.1 자원의 상호배제 조건 방지
상호배제를 다시 떠올리자면, 상호배제는 비공유가 전제되어야 한다. 예를들어 여러 프로세스는 프린터를 동시에 공유할 수 없는 것과 같다. 그런데 이 조건을 부정하자면 공유 자원이라는 것인데 즉, 여러프로세스가 동시에 이 자원을 공유할 수 있다는 것이다. 그런데 사실, 상호배제 조건을 방지를 한다는 것은 거의 불가능하다 볼 수 있다. 왜냐하면 애초에 자원들은 근본적으로 공유가 불가하기 때문이다. 그래서 사실 상호배제 조건을 방지한다는것으로는 교착 상태를 예방하기에는 어렵다고 할 수 있다.
1.2 점유와 대기 조건 방지
점유와 대기 조건을 부정하기 위해서는, 프로세스가 작업을 수행하기 전에 필요한 자원들을 모두 요청하고 획득해야한다.
그래서 한 방법은 자원을 할당할 때 시스템 호출된 프로세스 하나를 실행하는 데 필요한 모든 자원을 먼저 다 할당해버리고 실행한 뒤, 끝나면 다른 시스템 호출에 자원을 할당하는 것이다.
또 다른 방법은, 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원 요청을 허용해 주는 것이다. 그래서 어떤 프로세스가 추가적인 자원을 필요로 한다면 자기 자원을 모두 해제해서 빈상태에서 다시 요청을 해야하는 것이다. 그런데..! 이 방법은 딱봐도 자원의 효율성이 너무너무 떨어지고 (많은 자원이 사용되지 않으면서 계속 할당되어있기 때문에) , 뒤에서 배울 기아상태(프로세스가 무한정 기다림) 가 발생이 가능하다는 점이다.
1.3 비선점 조건 방지
먼저, 비선점 조건의 전제는 이미 할당된 자원에 선점권이 없어야 한다는 것이다. 이 조건을 무효화 시키는 방법은 어떤 자원을 가진 상태에서 또 다른 자원이 필요하다면 내 자원 모두를 해제한다. 그리고 프로세스가 작업을 시작할 때는 요청한 새로운 자원과 해제한 자원을 확보하는 것이다. 하지만 이 방법이 위험한 것은 이미 실행한 작업의 상태를 잃을 수도 있다는 것이다. 따라서 작업의 상태를 저장, 복구할 수 있을 때 좋은 방법이다.
1.4 순환 대기 조건 방지
모든 자원에 일련의 순서를 부여하고 각 프로세스가 오름차순으로만 자원을 요청할 수 있게 한다. 즉, 자원에 고유 할당번호를 붙이는 것이다. 예를들어 어떤 프로세스가 R2의 자원을 요청했다고 치면 그 다음에는 R3의 자원만 요청할 수 있는 것이다.
2. 교착 상태 회피
교착상태 예방 같은 경우에는 효율성과 시스템 처리량을 떨어뜨린다. 따라서, 교착 회피 방법은 덜 엄격한 조건을 요구하여 자원을 더 효율적으로 사용하는 것이 목적이다. 교착 상태 회피 방법은 위험 구역을 파악하여 자원을 할당하는 방법이다. 여기서 위험 구역이란, 아직 교착상태는 아니지만 자원 할당 시 교착 상태가 일어날 수 있는 구역을 말한다.
교착 상태 회피 방법에는 프로세스의 시작 중단과 자원 할당 거부로 두가지가 있다.
2.1 프로세스의 시작 중단
프로세스의 요구가 교착 상태를 발생시킬 수 있다면 프로세스 시작을 중단하는 것이다. 더 구체적으로 말하자면, 각 프로세스마다 요청과 해제에서 정확한 순서를 파악하고, 요청에 따른 프로세스 대기 여부를 결정하는 것이다.
2.2 자원 할당 거부
자원 할당과 교착 상태를 회피하는 또 다른 방법은 다익스트라의 은행가 알고리즘을 이용하는 것이다. 은행가 알고리즘은 자원의 할당 허용 여부를 결정하기 전에 미리 결정된 모든 자원의 최대 가능한 할당량을 시물레이션하여 안전 여부를 검사한다. 그런 다음 대기 중인 다른 모든 활동의 교착 상태 가능성을 조사하여 ‘안전상태’ 여부를 검사 확인한다. 은행가 알고리즘에 대해 자세히 알아보고 싶은 사람은 은행가알고리즘 을 참고하자.
3. 교착 상태 회복
교착 상태를 회복하기 위해서는
- 시스템 상태를 검사하는 교착 상태 알고리즘
- 교착 상태에서 회복시키는 알고리즘
이 필요하다. 교착 상태 탐지 알고리즘을 자주 실행하면 시스템의 성능은 떨어지지만, 교착 상태에 빠진 프로세스를 빨리 발견하여 자원의 유휴 상태를 방지할 수 있다.
탐지알고리즘 통해서 현재 상태가 교착상태인지 아닌지 판별한 후, 교착상태라면 이를 회복해야한다. 한 가지 방법은 교착 상태가 발생한 것을 운영자에게 통지해서 직접 처리하게 하는 것이고, 다른 방법은 시스템이 자동으로 교착 상태로부터 회복하게 하는 것이다. 이 것은 두가지 방법이 있고 하나는 순환 대기를 깨뜨리기 위해 단순히 한 개 이상의 스레드를 중지 시키는 것이다. 두번째 방법은 교착 상태에 있는 하나 이상의 스레들로부터 자원을 선점 하는 것이다.
3.1 프로세스와 스레드의 종료
프로세스 또는 스레드를 중지시켜 교착상태를 제거하기 위해 두가지의 방법이 존재한다. (이 중 하나를 사용)
- 교착 상태 프로세스를 모두 중지: 이 방식은 확실하게 교착 상태를 제거하지만, 비용이 크다. 왜냐하면 프로세스가 오랫동안 연산을 했을 가능성이 있으며, 이들 부분 계산의 결과들은 결국 버려지고 다시 계산해야 하기 때문이다.
- 교착 상태가 제거될 때까지 한 프로세스씩 중지: 이 방법은 각 프로세스가 중지될 때 마다 교착 상태 탐지 알고리즘을 호출해 프로세스들이 아직도 교착 상태에 있는지 확인해야 하므로 상당한 오버헤드를 유발한다.
3.2 자원 선점
자원 선점을 이용해 교착상태를 제거하기 위해서는 교착상태가 깨질때까지 프로세스로부터 자원을 계속해서 선점하고 이 선점한 자원들을 다른 프로세스에게 주어야한다. 이러한 방법으로 해결하기 위해서는 세가지의 사항을 고려해야한다.
- 희생자 선택 : 어느 자원과 어느 프로세스들이 먼저 선점될 것인가?
- 후퇴: 프로세스로부터 자원을 선점하려면 그 프로세스를 어떻게 해야하는가?
- 기아상태: 기아 상태가 발생하지 않는 것을 어떻게 보장할 것인가?
그럼 이 3가지를 어떠한 방식으로 진행해야 하는지 면밀히 따져보자.
- 희생자 선택 : 비용을 최소화 하기 위해서는 각 프로세스가 점유하고 있는 자원의 수 그리고 프로세스가 지금까지 실행하는데 소요한 시간과 같은 매개변수들을 고려해서 선택한다.
- 후퇴 : 사실 확실한 방법은 완전히 후퇴시켜버리는 것이다. 안전 상태가 어떤 것인지 결정하기 어렵기 때문에 그냥 프로세스를 중지시키고 재시작하는 것이다. 물론 교착상태를 깨뜨릴 정도로 후퇴를 시키는 것이 더 효과적이지만 모든 프로세스의 상태에 대해 많은 정보가 필요하다.
- 기아상태: 희생자를 선택할때 주로 비용에 근거하기 때문에 동일한 프로세스가 항상 희생자로 선택될 수 있다. 그 결과 이 프로세스는 자신의 일을 수행하지 못하고 굶어버리는 기아상태가 되기 쉽기 때문에 이를 고려해야한다. 따라서 희생자를 선택할때는 한정된 시간 동안에만 희생될 것을 보장해야한다.