OS - 7. Deadlocks 연습문제

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

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

1. 상호배제 - 한 교차점에 한 라인의 차들이 있다. 다른 라인의 차들이 그 공간을 점유하려면 지연되어야 하기 때문에 상호배제 성립

2. 점유하며 대기 - 차가 특정위치(자원)에서 다른 곳으로 이동하려면 그 위치에 있는 차가 빠질 때까지 기다려야 하므로 점유하며 대기가 성립한다.

3. 비선점 -  특정 차가 도로에서 갑자기 사라지는 경우가 없기 때문에 비선점이 성립

4. 순환대기 - 차들이 도로를 계속 도는 경우(사각형 주위를 돌 때) 순환대기가 성립

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

  교차점에서 차들이 정지하지 않을 수 있게 한다.

7.2 동기화 하기 위해 오직 reader-writer 락만을 사용하는 다중스레드 응용을 가정하자. 교착상태가 발생하기 위한 4가지 조건을 적용할 때, 다중 reader-writer 락이 사용되는 경우에도 여전히 교착상태가 발생할 수 있는가?

다중 reader-writer 락은 하나의 락이 점유되면 다른 reader 또는 writer는 락을 선점하거나 접근할 수 없기 때문에 상호 배제와 비선점의 상황이 된다. 또한, reader 또는 writer는 락을 선점하면 버퍼에 읽은 내용이나 쓸 공간이 있을 때까지 대기하기 때문에 락을 점유하며 대기한다. 그러나 다중 reader-writer 락의 경우에는 순환 대기 조건을 만족하지 않기 때문에 교착상태가 발생하지 않는다.

7. 3 > 그림 7.4에서 보인 프로그램이 항상 교착상태로 이끄는 것은 아니다. 이 프로그램에서 CPU 스케줄러의 역할과 교착상태가 발생에 끼친 영향에 대해 설명하시오.

- CPU 스케줄러는 2개의 Thread를 서로 번갈아가면서 할당해 주는데 처음 Thread가 do_work_one() function call을 할 시에 lock(&first_mutex)와 lock(&second_mutex)를 할당하고 CPU 스케줄러가 두 번째 Thread를 할당하면 교착상태가 일어나지 않습니다. 하지만 do_work_one() function call을 할시에 lock(&{first_mutex)가 걸리고 스케줄러가 두 번째 thread를 할당해주고 lock(&second_mutex)를 걸면 두 개의 Thread가 교착상태가 걸리게 되고 이러한 교착상태로 인해서 프로그램이 아무 일도 하지 않고 정지하게 됩니다. 

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

pthread_mutex_t mutx; //전역변수로 쓰레드 선언.

void transaction(Account from, Account to, double amount){

        mutex lock1, lock2;

        lock1 = get_lock(from);

        lock2 = get_lock(to);

        

        pthread_mutex_lock(&mutex); // 이 구역 자체를 임계구역으로 만들자.

acquire(lock1);   acquire(lock2);                withdraw(from,amount);       deposit(to,amount);            release(lock2); release(lock1);

        phtread_mutex_unlock(&mutex); // 잠금 해제.

}

  위 블록 부분도 임계영역으로 보고 해당 임계 영역에 대한 접근 제한하는 mutex를 추가로 두어 Thread A가 임계영역(블록 부분)에 접근 하였을 때, Thread B는 해당 부분에 접근 하지 못하게 된다.

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

a. 실행 시간 오버헤드

 현재 자원할당을 기억하는 비용으로 인해 실행시간 오버헤드를 늘리는 경향이 있다.

b. 시스템 처리율

데드락 형성을 정적으로 방지하는 기법보다 더 많은 자원을 동시에 사용할 수 있다. 따라서 교착상태 회피제도는 시스템 처리율을 높일 수 있다.

7.6 은행원 알고리즘으로 교착상태를 관리하고 있다면 아래 중 어떠한 것이, 그리고 어떠한 조건에서 안전하게 변경될 수 있을까?

a. Available 증가: 은행원 알고리즘의 효용성은 자원 종류의 수에 영향을 받지 않으므로 Available을 증가시키는 것은 안전하게 변경될 수 있다.

b. Available 감소: 만약 어떠한 프로세스가 자원을 할당받은 상태에서 해당 자원의 Available이 감소하면 다른 프로세스는 자원을 할당받은 프로세스가 작업을 종료할 때까지 기다려야하므로 교착상태가 발생할 수 있다.

c. 한 프로세스의 Max 증가: 프로세스가 허락받은 자원보다 더 많은 자원을 이용한다면 다른 프로세스가 작업을 끝내기 위해 필요로하는 자원까지 모두 이용하는 경우가 발생하므로 교착상태를 발생시킬 수 있다.

d. 한 프로세스의 Max 감소: 프로세스가 점유하는 자원의 수가 줄어들기 때문에 오히려 교착상태가 발생할 확률이 감소한다. 따라서, 안전하게 변경될 수 있다.

e, f 프로세스의 수를 증가/감소: 은행원 알고리즘의 효용성과 프로세스의 수는 관계가 없으므로, 안전하게 변경될 수 있다.

따라서, 안전하게 변경될 수 있는 경우는 a, d, e, f이다.

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

- 프로세스 3개를 P1, P2, P3라고 가정하고 4개의 자원을 할당 받아야 하면 두 개의 자원을 필요로 합니다.

	최대 소요량	현재 사용량
P1	2	1
P2	2	1
P3	2	1

위의 표처럼 최대의 상황을 가정해보면 한 개의 자원이 남는데 1개의 자원을 P1,P2,P3에 아무데나 주어도 할당 받은 프로세스는 현재 사용량에서 1개를 더 받고 최대 소요량을 맞추고 자원을 반환하기 때문에 나머지 두 프로세스에게도 최대 소요량만큼 자원을 할당 받을 수 있습니다. 그러므로 교착상태가 발생하지 않습니다.

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

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

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

- 현재 자원의 개수는 m개 이면 각 프로세스가 요청할 자원의 개수는 1~m개의 사이이다. 또한 모든 수요의 합은 m+1보다 작다. 각 자원 종류에 대해 최대 수요가 모든 자원의 수를 넘지 않으면 시스템은 안정적이고 교착 상태가 되지 않는다.

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

  어느 철학자가 첫번째 젓가락을 집기위해 요청을 할 때, 단 하나의 젓가락만 남았고, 두 개의 젓가락을 집고있는 철학자가 없다면 요청은 교착상태를 유발하지 않고 만족될 수 없다.

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

이용이 가능한 모든 젓가락을 가져가도 식사를 하기에 충분한 수의 젓가락을 확보하지 못 할 것으로 예상된다면 요청을 보류한다.

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

	Allocation			Need			Available
	A	B	C	A	B	C	A	B	C
P1	0	2	0	1	0	2	2	1	2
P2	3	0	2	0	4	2
P3	4	3	1	4	1	4
P4	1	2	3	0	2	0

-  위의 표를 banker's algorithm을 이용하여서 풀면 <P1, P4, P2, P3> 상태로 돌게 됩니다.

1) A상태에서 1개의 자원형태로 Banker's Algorithm을 이용 하게 되면 <P1, P2, P3, P4> 상태로 돌게 됩니다.

2) B상태에서 1개의 자원형태로 Banker's Algorithm을 이용 하게 되면 <P1, P3, P4, P2> 상태로 돌게 됩니다.

3) C상태에서 1개의 자원형태로 Banker's Algorithm을 이용 하게 되면 <P1, P2, P3, P4> 상태로 돌게 됩니다.

여기서 A,C의 상태는 같은데 B의 상태가 다르기 때문에 Banker's Algorithm을 이용하지 않을시 불안정한 상태로 들어가기 때문에 사용 해주어야 합니다.

7.12 현재 시스템의 상태가 아래와 같다. 은행원 알고리즘을 사용하여 다음 각 상태가 불안전 상태인지 결정하시오. 만일 상태가 안전이라면 프로세스가 종료할 수 있는 순서를 설명하시오. 그렇지 않다면 상태가 불안전한 이유를 설명하시오

a. Available = (0,3,0,1)

	Allocation	Max	Need	Available
	A B C D	A B C D	A B C D	A B C D
P0	3 0 1 4	5 1 1 7	2 1 0 3
P1	2 2 1 0	3 2 1 1	1 0 0 1
P2	3 1 2 1	3 3 2 1	0 2 0 1	0 3 0 1
P3	0 5 1 0	4 6 1 2	4 1 0 2
P4	4 2 1 2	6 3 2 5	2 1 1 3

P2를 먼저 끝내면 Available은 (3,4,2,2)가 된다. 이 후 P0, P1, P4 중 하나를 끝내면 나머지 프로세스를 모두 처리할 수 있다. 그렇기 때문에 안전 상태이다.

b. Available = (1,0,0,2)

	Allocation	Max	Need	Available
	A B C D	A B C D	A B C D	A B C D
P0	3 0 1 4	5 1 1 7	2 1 0 3
P1	2 2 1 0	3 2 1 1	1 0 0 1	1 0 0 2
P2	3 1 2 1	3 3 2 1	0 2 0 1
P3	0 5 1 0	4 6 1 2	4 1 0 2
P4	4 2 1 2	6 3 2 5	2 1 1 3

P1를 먼저 끝내면 Available은 (3,2,1,2)가 된다. 이 후 P0, P1, P4 중 하나를 끝내면 나머지 프로세스를 모두 처리할 수 있다. 그렇기 때문에 안전 상태이다.

7.13  현재 시스템의 상태가 아래와 같다.

	Allocation	Max	Available	Need
	A B C D	A B C D	A B C D	A B C D
	2 0 0 1	4 2 1 2	3 3 2 1	2 2 1 1
	3 1 2 1	5 2 5 2		2 1 3 1
	2 1 0 3	2 3 1 6		0 2 1 3
	1 3 1 2	1 4 2 4		0 1 1 2
	1 4 3 2	3 6 6 5		2 2 3 3

은행원 알고리즘을 사용하여 다음 물음에 답하시오.

a. 프로세스가 종료 가능한 순서를 보여서 시스템이 안전한 상태에 있다는      것을 설명하시오

Available(3 3 2 1)로 P0 종료 -> Available(5 3 2 2)로 P3 종료 ->Available(6 6 3 4)로

 P2 종료 -> Available(8 7 3 7)로 P1 종료 -> Available(11 8 5 8)로 P4 종료

b. 프로세스 의 요청이 (1,1,0,0)이라면 이 요청을 즉시 들어줄 수 있는가?

	Allocation	Max	Available	Need
	A B C D	A B C D	A B C D	A B C D
	2 0 0 1	4 2 1 2	2 2 2 1	2 2 1 1
	4 2 2 1	5 2 5 2		1 0 3 1
	2 1 0 3	2 3 1 6		0 2 1 3
	1 3 1 2	1 4 2 4		0 1 1 2
	1 4 3 2	3 6 6 5		2 2 3 3

불가능하다.  --> P1요청 먼저 들어주면 available(1 1 2 1) 이라서 교착상태로 빠짐 

c. 프로세스 의 요청이 (0,0,2,0) 이라면 이 요청을 즉시 들어줄 수 있는가?

Available 의 C가 0 이라서 불가능하다.

	Allocation	Max	Available	Need
	A B C D	A B C D	A B C D	A B C D
	2 0 0 1	4 2 1 2	3 3 0 1	2 2 1 1
	3 1 2 1	5 2 5 2		2 1 3 1
	2 1 0 3	2 3 1 6		0 2 1 3
	1 3 1 2	1 4 2 4		0 1 1 2
	1 4 5 2	3 6 6 5		2 2 3 3

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

“프로세스가 작업을 마치기까지 더 이상의 추가적인 자원을 필요로 하지 않는다”는 가정을 한다. 즉, 프로세스는 종료가 될 시점에 문맥 저장, 파일 입출력 등을 이용하지 않는다는 가정이다. 그러나 이러한 가정은 현재 프로세스의 문맥이 다음 프로세스의 실행에 필요한 경우, 현재 프로세스에 의해 계산되고 있는 데이터를 파일에 저장해야하는 경우 등의 상황에서는 예외가 발생한다.

7. 15> North Tunbridge와 South Tunbridge의 두 Vermont 마을은 1차선의 다리로 연결되어 있다. 두 마을의 농부들은 이웃 마을로 자신들의 생산물을 이동할 때 이 다리를 이용한다. 두 마을의 농부들이 동시에 다리의 중간에 도착하면 교착상태가 발생한다.(Vermont 마을의 농부들은 옹고집들이라 절대 물러설 수 없다.) 교착 상태를 예방하는 알고리즘을 세마포를 사용하여 설계하시오. 처음에는 기아 현상에 대해서는 신경 쓰지 마시오(한쪽 방향의 농부가 반대 방향의 농부들이 다리를 이용하지 못하게 하는 것)

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

 - 전역변수 permit을 두어 permit이 1일 때만 다리를 건너도록 합니다. permit이 0이면 wait함수로 대기를 하고 있고 반대편 농부가 다 건너면 signal을 보내서 wait를 해제시켜줍니다.