교착 상태 해결 방법

교착 상태 해결

교착상태를 해결하는 방법은 예방, 회피, 검출이며, 추가적으로 교착 상태가 발견된 후에 자원을 회복하는 방법도 있다.

 

교착 상태 예방 prevention

교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식이다. 교착 생태는 상호배제, 비선점, 점유와 대기, 원형 대기라는 네 가지 조건을 동시에 충족해야 발생하기 때문에 이 중 하나라도 막는다면 교착 상태가 발생하지 않는다. 그러나 이 방법은 실효성이 적어 잘 사용되지 않는다.

 

교착 상태 회피 avoidance

자원 할당량을 조절하여 교착 상태를 해결하는 방식이다. 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 것이다. 그러나 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적다.

 

교착상태 검출 detection과 회복 recovery

교착 상채 검출은 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식이다. 만약 교착 상태가 발생하면 교착 상태 회복 단계가 진행된다. 교착 상태를 검출한 후 회복하는 방식은 교착 상태를 해결하는 현실적인 접근 방법이다.

 

예방과 회피는 사용 불가능 방식이고 검출과 회복이 사용 가능한 방식이다.

 

퀴즈

1. 교착상태를 해결하는 방법은 무엇이 있나?

2. 교착상태를 해결하는 방법 중에 실행 불가능한 것은 무엇인가?

3. 교착 상태를 해결하는 방법중에 실행이 가능한 것은 무엇인가?

4. 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식은 무엇인가?

5. 교착 상태 중에서 자원 할당량을 조절하여 교착 상태를 해결하는 방식은 무엇인가?

6. 교착 상태 중에서  자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식은 무엇인가?

교착 상태 예방

 

상호 배제 예방

시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버리는 방법이다. 

현실적으로 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있다. 상호 배제를 없애버리는 것은 식사하는 철학자 문제에서 두 사람에게 하나의 포크를 같이 사용하라고 하는 것과 같다

 

비선점 예방

모든 자원을 빼앗을 수 있도록 만드는 방법이다.

식사하는 철학자 문제에서 옆 사람의 포크를 빼앗을 수 있다면 교착 상태가 발생하지 않는다. 그런데 임계구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없을 뿐만 아니라 상호 배제 예방도 보장할 수 없다. 사실상 시스템의 모든 자원을 빼앗기는 어렵다. 

 

점유와 대기 예방

프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다. 다시 말해 전부 할당하거나 아예 할당하지 않는 all or nothing 방식을 적용하는 것이다. 이를 위해 프로세스는 작업 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나, 그렇지 못할 경우 자원을 모두 반납해야 한다.

 

상호 배제 예방과 비선점 예방은 자원에 대한 제약을 풀어버리는 것이다. 그러나 임계구역으로 보호받는 자원에 대한 제약을 풀기 어렵다. 점유와 대기 예방은 자원이 아닌 프로세스의 자원 사용 방식을 바꿔 교착 상태를 처리한다는 점에서 의미가 있다. 한편 점유와 대기 예방에는 다음과 같은 단점이 있다.

- 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다.

- 자원의 활용성이 떨어진다.

- 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.

- 결국 일괄 작업 방식으로 동작한다.

 

원형 대기 예방

점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법이다. 

자원을 한 방향으로만 사용하도록 설정하여 원형 대기를 예방할 수 있다. 모든 자원에 숫자를 부여하고 숫자가 큰 반향으로만 자원을 할당하는 것이다. 숫자가 작은 자원을 잡은 상태에서 큰 숫자를 잡는 것은 허용하지만, 숫자가 큰 자원을 잡은 상태에서 작은 숫자를 잡는 것은 허용하지 않는다.

원형 대기 예방은 모든 자원을 할당받아야 실행할 수 있는 점유와 대기 예방보다 완화한 방법이다. 그러나 이 또한 다음과 같은 단점이 있다.

- 프로세스 작업 진행에 유연성이 떨어진다.

- 자원에 번호를 어떻게 부여할지가 문제다.

 

퀴즈

7. 독점적으로 사용할 수 있는 자원을 없애버리는 방법은 무엇인가?

8. 모든 자원을 빼앗을 수 있도록 만드는 방법은 무엇인가?

9. 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법은 무엇인가?

10. 전부 할당하거나 아예 할당하지 않는 방식을 무엇이라 하는가?

11. 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵고 자원의 활용성이 떨어지는 단점을 갖고 있는 예방법은 무엇인가?

12. 점유와 대기를 하는 프로새스들이 원형을 이루지 못하도록 막는 방법은 무엇인가?

13. 프로세스 작업 진행에 유연성이 떨어지고 자원에 번호를 어떻게 부여할지가 문제인 예방법은 무엇인가?

 

교착 상태 회피

 

교착 상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법이다. 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킨다.

교착 상태 회피에서는 할당되는 자원의 수를 조절하여 교착 상태를 피한다. 교착 상태 예빵은 프로세스의 작업 방식을 제약하기 때문에 사용할 수 없었는데, 교착 상태 회피는 시스템의 운영 방식에 변경을 가하지 않기 때문에 교착 상태 예방보다 좀 더 유연하다.

 

은행원 알고리즘

교착 상태 회피를 구현하는 방법은 여러 가지인데 그중 하나는 에츠허르 데이크스트라가 제안한 은행원 알고리즘이다.  은행이 대출해 주는 방식, 즉 대출 금액이 가능한 범위 내이면(안정 상태이면) 대출이 허용되지만 그렇지 않으면 거부되는 것과 유사하기 때문에 이러한 명칭이 붙었다.

 

어떤 레스토랑에 가락국수 10인분과 스파게티 20인분을 준비했다고 하자 그럼 수용 가능한 손님의 수는 10명이다.

은행원 알고리즘에서는 최악의 경우를 기준으로 삼음으로써 문제 상황을 철저히 피하여 교착 상태를 막는다.

 

은행원 알고리즘의 변수

Total(전체 자원): 시스템 내 전체 자원의 수

Available(가용 자원): 시스템 내 현재 사용할 수 있는 자원의 수(가용자원=전체 자원-모든 프로세스의 할당 자원)

Max(최대 자원): 각 프로세스가 선언한 최대 자원의 수

Allocation(할당 자원): 각 프로세스의 현재 할당된 자원의 수

Expect(기대 자원): 각 프로세스가 앞으로 사용할 자원의 수(기대 자원= 최대 자원- 할당 자원)

 

안정 상태: 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우다.

 

퀴즈

14. 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법은 무엇이라 하는가?

15. 교착 상태 회피와 교착 상태 예방과 다른 점은?

16. 가능한 범위 내에서만 보장하는 알고리즘은 무엇인가?

17. 시스템 내 전체 자원의 수는 무엇인가?

18. 시스템 내 현재 사용할 수 있는 자원의 수(가용자원=전체 자원-모든 프로세스의 할당 자원)는 무엇인가?

19. 각 프로세스가 선언한 최대 자원의 수는 무엇인가?

20. 각 프로세스의 현재 할당된 자원의 수는 무엇인가?

21. 각 프로세스가 앞으로 사용할 자원의 수(기대 자원= 최대 자원- 할당 자원)는 무엇인가?

교착 상태 회피의 문제점

고착 상태 회피의 원칙은 교착 상태가 발생하지 않을 수준까지만 자원을 나누어주는 것이다.

하지만 여기에는 다음과 같은 문제가 있어서 실제 시스템에서는 교착 상태 회피를 사용하지 않는다.

- 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.

- 시스템의 전체 자원 수가 고정적이어야 한다.

- 자원이 낭비된다.

22. 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 하며, 자원이 낭비되는 것을 무엇이라 하는가?

교착 상태 검출

- 타임아웃

타임아웃을 이용한 교착 상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다. 교착 상태가 자주 발생하지 않을 것이라는 가정하에 사용하는 방법이므로, 특별한 알고리즘 없이 쉽게 구현할 수 있다. 

타임아웃 이용하는 방법을 '가벼운 교착 상태 검출'이라 하고, 자원 할당 그래프를 이용하는 방법을 '무거운 교착 상태 검출'이라 한다. 실제로 유닉스나 윈도우 같은 운영체제에서는 일정 시간 동안 작업이 진행되지 않으면 해당 프로세스를 죽인다. 윈도우에서 '프로그램이 응답이 없어 종료합니다.'라는 메시지를 본 적이 있을 텐데 이것이 타임아웃을 이용하는 방법의 대표적인 예다.

타임아웃을 이용하는 방식에는 다음과 같은 문제가 있다.

- 엉뚱한 프로세스가 강제 종료될 수 있다.

- 모든 시스템에 적용할 수 없다.

 

데이터베이스의 교착 상태 처리는 운영체제보다 복잡하다. 타임아웃으로 데이터의 일관성이 깨지는 문제를 해결하기 위해 데이터베이스에서는 체크포인트 check point와 롤백 roll back을 사용한다. 체크포인터는 작업을 하다가 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시다. 체크포인트를 설정하면 현재의 시스템 상태가 하드디스크에 저장되며 이러한 데이터를 스냅숏(snap shot)이라고 한다. 롤백은 작업을 하다가 문제가 발생하면 과거의 체크포인트로 되돌아가는 것을 말한다. 

윈도우에서는 '특정 시점으로 복원은' 스냅숏과 롤백을 이용하여 운영체제를 복원시키는 작업이다.

 

퀴즈

23. 교착 상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생하는 것으로 간주하여 처리하는 방법은 무엇인가?

24. 타임아웃을 이용하는 것을 무슨 검출이라 하는가?

25. 자원 할당 그래프를 이용하는 것은 어떤 검출이라 하는가?

26. '프로그램이 응답이 없어 종료합니다'라고 메시지가 뜨는 것은 어떤 방법을 사용한 것인가?

27. 엉뚱한 프로세스가 강제 종료될 수 있고 모든 시스템이 적용할 수 없는 단점을 갖고 있는 것을 어떤 검출이라 하는가?

28. 타임아웃으로 데이터의 일관성이 깨지는 문제를 해결하기 위해 데이터베이스에서는 두 가지 방법을 사용한다. 그 두 가지가 무엇인가?

29. 체크포인트를 설정하면 현재의 시스템 상태가 하드디스크에 저장되며 이러한 데이터를 무엇이라 하는가?

30. 작업을 하다가 문제가 발생하면 과거의 체크포인트로 되돌아가는 것을 무엇이라 하는가?

 

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

교착 생태를 검출하는 또 다른 방법은 자원 할당 그래프를 이용하는 것이다. 자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지 혹은 기다리고 있는지를 알 수 있다.

 

- 교착 상태가 없는 자원 할당 그래프

자원 할당 그래프에는 사이클이 존재하지 않는다. 그러므로 프로세스 P2가 작업을 마치고 자원 R2를 반환하면 나머지 프로세스의 작업이 계속 진행되어 결국 교착 상태가 발생하지 않는다.

 

- 교착 상태가 있는 자원 할당 그래프

운영체제는 자원을 요청하거나 할당할 때마다 자원 할당 그래프를 갱신하는데, 이때 사이클이 발생하면 교착 상태가 검출된 것으로 판단한다.

교착 상태 회복

교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 하는데 이를 교착 상태 회복이라고 한다. 교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제 종료한다. 프로세스 강제로 종료하는 방법에는 다음과 같이 두 가지가 있다.

 

- 교착 상태를 일으킨 모든 프로세스를 동시에 종료한다.

 

- 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료한다.

= 우선순위가 낮은 프로세스를 먼저 종료한다.

= 우선순위가 같으면 작업 시간이 짧은 프로세스를 먼저 종료한다.

= 위의 두 조건이 같으면 자원을 많이 사용하는 프로세스를 먼저 종료한다.

 

퀴즈

31. 교착 상태가 없는 자원 할당 그래프를 무엇이라 하는가?

32. 사이클이 발생하면서 교착 상태가 검출된 것으로 판단하는 것을 무엇이라 하는가?

33. 교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 하는데 이를 무엇이라 하는가?

34. 교착 상태를 일으킨 모든 프로세스를 동시에 종료하는 것을 무엇이라 하는가?

35. 교착 상태를 일으킨 프로세스를 종료할 때 어떤 프로세스부터 종료하는가?