Chapter07. 교착상태 : 문제풀이

7.1 그림7.10에 보인 교착상태를 생각해 보자.

1. 이 예에서 교착상태를 위한 네 가지 필요조건이 정말로 성립함을 보이시오.
2. 이 시스템에서 교착상태를 회피하는 간단한 법칙을 설명하시오.

cf) 교착상태를 위한 필요 조건들

1. 상호 배제 : 최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 비공유 모드에서는 한 번에 한 프로세스만이 그 자원을 사용할 수 있다. 다른 프로세스가 그 자원을 요청하면, 요청 프로세스는 자원이 방출될 때까지 반드시 지연되어야 한다.

2. 점유하며 대기 : 프로세스는 최소한 하나의 자원을 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.

3. 비선점 : 자원들을 선점할 수 없어야 한다. 즉, 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후 그 프로세스에 의해 자발적으로만 방출될 수 있다.

4. 순환 대기 : 대기하고 있는 프로세스의 집합에서 P0은 P1이 점유한 자원을 대기하고, P1은 P2가 점유한 자원을 대기하고, P2,...Pn-1은 Pn이 점유한 자원을 대기하며, Pn은 P0가 점유한 자원을 대기한다.

도로는 자원, 차들은 프로세스라고 볼 수 있다.

a : 도로는 한번에 하나의 차만 지나갈 수 있으므로 상호 배제를 만족한다.

현재 차들은 각자 도로를 점유한 채, 다른 차들이 점유한 도로로 가기 위해 대기하고 있으므로 점유하며 대기 조건을 만족한다.

대기하고 있는 차가 도로를 벗어나야만 도로가 비게되므로 비선점 조건을 만족한다.

차들이 연속적으로 그 다음 도로를 가기 위해 대기하고 있으므로 순환 대기를 만족한다.

b :

7.4 7.4.4절에서 ~. 그러나 만일 두 스레드가 동시에 transaction() 함수를 호출하는 상황에서는 교착상태가 발생할 수 있다는 것을 지적하였다. 교착상태를 예방할 수 있도록 transaction()함수를 수정하시오.

7.5 순환 대기 기법과 다양한 교착상태 회피 기법(은행원 알고리즘 같은)을 다음 측면에서 비교하시오.

1. 실행 시간 오버헤드
2. 시스템 처리율

순환 대기 기법은 처음부터 교착상태를 예방하지만, 회피 기법은 교착상태가 일어난 후 이를 탐지하고 회복하게 된다.

교착상태 예방 알고리즘은 시스템 처리율을 감소시킬 수 있으며, 교착상태 회피 알고리즘에서는 교착상태를 탐지하는 과정에서 오버헤드가 발생할 수 있다.

7.6 실제 시스템에서는 자원의 요구나 시스템 보유 자원 모두가 장기적인 관점에서는 변할 수 있는 것들이다. 어떤 자원들은 항상 고장나고,~`. 우리가 은행원 알고리즘으로 교착상태를 관리하고 있다면 아래 중 어떠한 것이, 그리고 어떠한 조건에서 안전하게 변경될 수 있을까?(즉 교착상태를 유발하지 않는다는 관점에서)

1. Available을 증가시킨다(새 자원이 시스템에 추가된다).
2. Available을 감소시킨다(기존 자원이 시스템에서 아주 제거된다).
3. 한 프로세스의 Max를 증가시킨다(프로세스가 허락받은 것보다 더 많은 자원을 필요로 한다. 그래서 더 많은 자원을 원할 수 있다).
4. 한 프로세스의 Max를 감소시킨다(프로세스가 그렇게 많은 자원을 필요로 하지 않는다고 결정한다).
5. 프로세스의 수를 증가시킨다.
6. 프로세스의 수를 감소시킨다.

7.7 세 개의 프로세스에 의해 공유되는 동일한 유형의 네 개의 자원으로 구성된 시스템을 고려해보자. 이들 각 프로세스는 최대 두 개의 자원을 필요로 한다. 시스템에 교착상태가 발생하지 않음을 보이시오.

7.8 n개의 프로세스들이 공유하는 동일한 타입의 자원 m개로 구성한 시스템을 고려해 보자. 자원들은 단지 한 번에 한 개씩 프로세스들에 의해 청되고 방출될 수 있다. 다음의 두 조건이 성립하면, 시스템이 결코 교착상태가 될 수 없음을 설명하시오.

1. 각 프로세스의 최대 수요는 1과 m개 사이의 자원이다.
2. 모든 최대 수요의 합은 m+n개보다 작다.

7.9 젓가락이 테이블의 중앙에 있고~ 철학자문제를 고려하자. ~~현재 젓가락이 할당된 상태에서 특정 요청이 교착상태를 유발하지 않고 만족될 수 있는지를 판단하는 간단한 규칙을 설명하시오.

7.10 위의 문제와 똑같은 환경. 이제는 각 철학자가 식사하기 위해서는 3개의 젓가락이 필요하고 자원 요청은 한 번에 하나씩 이루어진다고 가정하자. 현재 젓가락이 할당된 상태에서 특정 요청이 교착상태를 유발하지 않고 만족될 수 있는지를 판단하는 간단한 규칙을 설명하시오.

7.11 은행원 알고리즘의 배열들의 차원을 1 줄이면, 한 종류의 자원만을 가진 시스템용 은행원 알고리즘을 만들어낼 수 있다. 각 자원 종류마다 한 자원용 은행원 알고리즘을 개별적으로 적용해서는 여러 자원을 대상으로 하는 원래의 은행원 알고리즘을 구현할 수 없음을 예를 통해서 보이시오.

7.13 현재 시스템의 상태가 아래와 같다. 은행원 알고리즘을 사용하여 다음 물음에 답하시오.

7.14 교착상태 탐지는 어떤 낙관적인 가정을 하고 있는가? 이 가정은 어떻게 어긋날 수 있는가?

교착상태에 빠져있지 않은 프로세스가 작업을 마치기까지 더 이상의 추가적인 자원을 필요로 하지 않는다고 가정한다. 하지만 만약 이 가정이 틀린 것이였다면 이 다음차례에 탐지 알고리즘을 돌릴 때 교착상태가 나타나게 될 것이다.

7.15 North Tunbridge와 South Tunbridge의 두  Vermont마을은 ~~.

7.16 연습문제 7.15의 해결책을 기아 현상이 발생하지 않도록 수정하시오.