Operating System Concepts Chapter 7. 교착상태 문제풀이

7.1. North Tunbridge 와 South Tunbridge의 두 Vermont 마을의 농부들의 문제를 해결하기 위해, 교착 상태를 예방하는 알고리즘을 세마포어를 사용하여 설계하시오.

void Town_Deadlock{
 
    Semaphore bridge;
 
    wait(bridge);
 
    // go to bridge
 
    signal(bridge);
 
}

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

void Town_Deadlock {
 
    Semaphore bridge;
    int turn;
 
    while(turn == j);
    wait(bridge);
 
    // go to bridge
    
    signal(bridge);
    turn = j;
}

-> turn 변수를 만들어, 나의 차례가 지나고 나서 바로 turn 을 다른 마을로 넘겨주도록 한다.

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

-> 만약, 두 프로세스(P1,P2)가 한개씩 자원을 점유하고 나머지 프로세스(P3)가 2개의 자원을 점유한다고 가정한다. 한개씩 자원을 점유한 프로세스들이 서로의 자원을 방출하기를 기다리고 있는 상황이 생길 수 있다. 사이클이 생길 수 있지만 P3이 점유한 자원을 방출한다는 점을 고려해 보면 교착상태는 발생하지 않는다. 

7.4. 그림 7.9에 보인 교통의 교착상태를 생각해 보자.

a. 이 예에서 교착상태를 위한 네 가지 필요조건이 정말로 성립함을 보이시오.

-> 1) 상호배제

일차선 도로이기 때문에, 길은 항상 한쪽 방향으로 이동할 수 있다는 점에서 상호배제가 지켜진다.

-> 2) 점유하며 대기

각 차선은 저마다 한 방향의 차량행렬이 각각 점령하고 있으며, 앞으로 진입하기 위해 대기중이다.

-> 3) 비선점

현재 꽉 막힌 도로이기 때문에 차량은 뒤로 빠질 수 없는 상태이다. 그래서 자원은 강제적으로 방출될 수 없는 상태이며, 다른 도로를 선점할 수도 없는 상황이다.

-> 4) 순환 대기

현재 각 차량행렬은 앞을 막고있는 행렬이 없어지기를 대기 하고 있는 상태이다.

b. 이 시스템에서 교착 상태를 회피하는 간단한 법칙을 설명하시오.

-> 점유하며 대기 조건을 발생하지 않도록 할 수 있다. 각 차량 행렬은 앞으로 진입하고자 할 때, 도로에 나서지 않은 상태여야만 한다.

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

a. Available을 증가시킨다.(새 자원이 시스템에 추가된다.)

b. Available을 감소시킨다. (기존 자원이 시스템에서 아주 제거된다.)

c. 한 프로세스의 max 를 증가시킨다.( 프로세스가 허락받은 것보다 더 많은 자원을 필요로한다. 그래서 더 많은 자원을 원할 수 있다.)

d. 한 프로세스의 max 를 감소시킨다. (프로세스가 그렇게 많은 자원을 필요로 하지 않는다고 결정한다)

e. 프로세스의 수를 증가시킨다.

f. 프로세스의 수를 감소시킨다.

-> a : 자원이 시스템에 추가되는 것은, 자원의 부족으로 인해 불안전한 상태를 만들지 않으므로 (오히려 안전하게 만들 수도 있음), 상관없다.

-> d : 프로세스의 최대 요청 자원개수를 낮추기 때문에 가용한 자원수가 더 많아질 수 있다.

-> f : 프로세스의 수가 감소되면, 그만큼 자원을 요청하는 프로세스가 줄어들어서 바로 자원을 이용할 가능성이 많아진다.

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

-> 한 자원은 자원 요청 알고리즘으로부터 할당 가능하다고 판단된 반면, 한 자원은 그렇지 않은 경우, 시스템 상태가 안전하다는 것을 보장할 수 없다. 

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

a. 실행 시간 오버헤드

-> 은행원 알고리즘은, 시스템의 안전성 여부를 확인하기 위해 m * n^2 개의 연산과, 자원요청 알고리즘으로 자원을 안전하게 들어줄 수 있는지를 검사한다. 실행하는 데 드는 시간이 많다. 반면, 순환 대기 기법은, 프로세스가 자원을 요청할 때 마다 큰 것을 요청하게 만들던지, 요청하는 자원보다 큰 자원을 방출하게 만들던지 두 가지의 방법을 쓰기만 하면 된다. 따라서 오버헤드가 적다.

b. 시스템 처리율

-> 순환 대기 같은 경우, 무조건 오름차순으로 자원 요청이 이루어져야 한다. 따라서 그 순서를 정하는 것 때문에 처리율이 낮아진다. 반면, 은행원 알고리즘은 가능한 순서만 먼저 찾는다면 일정한 순서에 의해 모든 프로세스의 요청을 다 들어줄 수 있기 때문에 처리율이 좋다.

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

a. Need 행렬의 내용은 어떻게 되는가?

-> Need 행렬

P0	0 0 0 0
P1	0 7 5 0
P2	1 0 0 2
P3	0 0 2 0
P4	0 6 4 2

b. 시스템은 현재 안전 상태에 있는가?

-> 안전 상태에 있다. <p2, p1, p4, p5, p3> 순서가 그 예다.

c.  p1이 (0,4,2,0) 을 요청하게 되면 그 요청을 즉시 들어줄 수 있는가?

-> available 상태에 있는 자원이 요청을 들어주기에 충분하기 때문에, 요청을 즉시 들어줄 수 있다.

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

a. 각 프로세스의 최대 수요는 1 과 m개 사이의 자원이다.

b. 모든 최대 수요의 합은 m+n 개 보다 작다.

-> 먼저, 자원들은 자원의 개수인 m보다 적은 수만큼 수요 요청을 할 수 있다. 그러므로 한 자원이 모든 자원을 점유할 일이 없어진다. 

7.14. 교착상태 탐지 알고리즘은 어떤 낙관적인 가정을 하고 있는가? 이 가정은 어떤 경우에 위배될 수 있는가?

7.15. 젓가락이 테이블의 중앙에 있고, 철학자에 의해 그 중 2개가 사용될 수 있는 식사하는 철학자 문제를 고려하자. 젓가락에 대한 요청은 한 번에 하나씩 이루어진다고 가정하자. 현재 젓가락이 할당된 상태에서 특정 요청이 교착상태를 유발하지 않고 만족될 수 있는 지를 판단하는 간단한 규칙을 설명하시오.

-> 

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

-> 

7.18. 7.4.4 절에서 모든 락이 일정 순서에 의해 획득되도록 보장함으로써 교착상태를 예방하는 상황을 설명하였다. 그러나 만일 두 스레드가 동시에  transaction() 함수를 호출하는 상황에서는 교착상태가 발생할 가능성이 있다는 것을 지적하였다. 교착상태를 예방할 수 있도록 transaction() 함수를 수정하시오.

void transaction(Account from, Account to, double amount){
    
    Semaphore lock1, lock2;
    bool assign = false;
 
    assign = true;
    while(!assign);
    assign = false;
    
    lock1 = getLock(from);
    lock2 = getLock(to);
    
 
    wait(lock1);
    wait(lock2);
 
    withdraw(from, amount);
    deposit(to, amount);
 
    signal(lock2);
    signal(lock1);
 
    assign = true;
}

-> 정답을 잘 모르겠지만, 스레드가 공유하는 assign 이라는 변수를 두었다. assign 값이 false 일 때, 스레드는 대기를 하게 된다. 처음 수행되는 프로세스는 while문을 빠져나와 assign 을 false로 만들고, 다른 프로세스들은 기다려야 한다. 수행이 다 끝나고, 락을 다 방출한 후 assign 을 true 로 만들어줘 대기하던 프로세스가 진입할 수 있도록 한다. 결국, 두번째 스레드가 락을 요청하기 전에 lock1, lock2 는 모두 다른 스레드에 의해 획득되고 방출되는 것을 보장한다.