[OS]운영체제론 연습문제 7장 - 문제 및 해설

[OS]운영체제론 연습문제 7장 - 문제 및 해설

01 교착 상태가 무엇인지 정의하라.

교착 상태란 둘 이상의 프로세스가 각자가 가지고 있던 자원을 보유한 채로 외부적 조치가 없는 한 영원히 그 상태에서 기다리고 있는 상황을 말한다.

교수님 답

교착상태(데드락, deadlock)는 하나 이상의 프로세스들이 결코 일어날 수 없는 이벤트 를 기다리는 상황을 의미한다. 즉, 교착상태는 프로세스 A가 사용하고 있는 자원을 기다리는 다른 프로세스 B에 의해 사용되는 자원을 기다리는 프로세스 A 상황에서 발생한다.

04 무기한 연기는 무엇인가? 교착 상태와 어떻게 다른가? 무기한 연기와 교착 상태의 유사점은 무엇인가?

무기한 연기란 운영체제가 많은 프로세스들의 다양한 요청을 처리해 주다가 몇몇 프로세스가 매우 오랜 시간 동안 서비스를 받지 못하는 경우가 발생하는 상황을 말한다.

무기한 연기 상태인 사용자는 오랜 기간 서비스를 할당 받지 못한다. 이들의 사용자들은 마치 자신들이 교착 상태에 빠진 것과 유사한 기분을 느끼게 될 것이다. 그러나 실제로 교착 상태와는 달리 오랜 시간 후에라도 무한 대기로부터 벗어나 서비스를 받을 수 있다.

교수님 답

무기한 연기 : 이벤트의 어떤 특정 시간과 순서가 프로세스(혹은 스레드)의 수행을 하지 못 하게 만드는 경우 발생하는 상태이다. 무기한 연기의 주된 이유는 선입선출 방식보다 우선 순위대로 요구들을 서비스하는데 있다. 우선 순위 구조는 보다 높은 우선 순위의 프로세스 혹은 스레드가 보다 낮은 프로세스(혹은 스레드)를 반복적으로 중지시키게 됨으로써 낮은 프로세스(혹은 스레드)에서는 무기한 연기가 생기게 된다.

교착상태와의 차이점 : 무기한 연기되고 있는 프로세스는 결국 수행을 하게 되지만 프로세스들이 교착상태가 되면 해당 프로세스들은 결코 수행을 재개할 수 없다.(최소한 시스템 내의 한 부분을 희생하지 않고서는 수행 재개 불가능함)

교착상태와 유사점 : 수행을 더 이상 하지 않는다는 것이 유사함. 지연 시간이 길어질수록 사용자, 오퍼레이터 등은 프로세스가 교착상태 혹은 무기한 연기 상태에 있는지를 구분하지 못한다.

08 프로세스 n개가 있는 시스템에서 이 프로세스들의 부분 집합인 m이 현재 무기한 연기 상태에 빠져있다. 시스템에서 어떤 프로세스가 무기한 연기되고 있는지 파악할 수 있는가?

프로세스들은 무기한 연기 상태일 수도 있지만 아닐 수도 있다. 프로세스들은 곧 발생할 이벤트를 대기하고 있을 수도 있고, 무한 루프에 빠진 것일 수도 있고, 곧 끝날 복잡한 계산을 하고 있을 수도 있다. 그저 ‘기능이 멈춘’ 것처럼 보일 수도 있다는 것이다. 따라서 시스템에서는 어떤 프로세스가 무기한 연기되고 있는지 장담할 수 없다.

교수님 답

일반적인 경우에 있어서는 파악할 수 없다. 이는 프로그램의 수행 경로를 예측할 수 없 기 때문이다. 즉 어떤 프로세스들의 경우에는 무기한 연기를 방금 시작하여 성능적인 측 면에서는 아직 프로그램에서 지연을 시키는지 시스템에서 무기한 연기를 시키는지를 판단 할 수 없기 때문이다.

09 철학자들의 만찬 문제 : 모니터를 사용해 철학자들의 행동을 시뮬레이션하는 병행 프로그램을 작성하라. 프로그램은 교착 상태나 무기한 연기의 위험이 없어야 한다. 상호 배제를 보장해야 한다.

(a)  

pickUpLeftFork();             //모든 철학자가 동시에 왼쪽 포크를 집어들면 다음 줄로 넘어갈 수 없기 때문에 이 줄에서 교착상태가 일어나게 된다.

pickUpRightFork();    

eat();

putDownLeftFork();

putDownRightFork();

(b)  

pickUpBothForksAtOnce();   //특정 철학자만 계속하여 포크를 집을 기회를 획득하여, 기회를 획득하지 못하는 철학자가 발생할 수 있다.

eat();

pickDownBothForksAtOnce();

(c)  

while(notHoldingBothForks)

{

        pickUpLeftFork();

        if(rightForkNotAvailable)     putDownLeftFork();   //모든 철학자가 동시에 왼쪽 포크를 들고 다시 내려놓기만을 반복하는 livelock상태가 발생할 수 있다.

        else pickUpRightFork();

}

eat();

putDownLeftFork();

putDownRightFork();

(d)  

if(philosopherID%2==0){     //짝수 번째 철학자들은 왼쪽 포크부터 집어든다.

        pickUpLeftFork();     

pickUpRightFork();    

eat();

putDownLeftFork();

putDownRightFork();

} else {               //홀수 번째 철학자들은 오른쪽 포크부터 집어든다.

pickUpRightFork();    

pickUpLeftFork();      

eat();

putDownRightFork();

putDownLeftFork();

        }

이와 같은 경우, 먼저 포크를 집은 사람이 식사를 하고 있을 때, 그 양 옆의 사람 중 한 명은 포크 하나를 든 상태로 대기하다가 식사를 하던 옆 사람이 포크를 내려놓으면 바로 그 포크를 집어들 수 있다. 따라서 비슷한 횟수로 식사에 성공하게 되므로 위의 문제들을 모두 해결한 알고리즘이라고 할 수 있다.

교수님 답

 (철학자의 만찬)

a. 이 내용은 철학자들이 알맞게 먹는 것을 허용하지만 교착상태에 들어간다. 예로써, 모든 철학자들이 그들의 왼쪽 포크들을 먼저 집는다고 가정하자. 철학자들이 그들의 오른쪽 포크를 집고자 할 때 사용가능한 오른쪽 포크는 없게 된다. 즉 교착상태이다.

b. 이 내용은 “줄다리기” 해결책의 하나이다.  2명의 철학자가 그들의 포크를 집고 먹고 내려놓고 하는 동작을 무한정 반복한다. 이 방법은 다른 철학자들을 굶게 한다. 즉, 다른 철학자들 관점에서 보면 무기한 연기를 하게 만든다.

c. 이 내용은 혹 가다가 동작하지만 너무 자주 무기한 연기(즉, 철학자들을 굶게 만드는 원인임)를 발생한다. 5명의 철학자들이 동기화되어 왼쪽 포크를 집어 들고 오른쪽 포크가 없다는 것을 보면 그들의 왼쪽 포크를 내려놓는다고 가정한다. 이러한 순서는 무한정 갈 수 있다.

d. 이 내용은 순환 대기가 결코 발생하지 않기 때문에 교착상태를 방지할 수 있다. 철학자들이 원탁에 앉아 있기 때문에 순환대기는 모든 철학자가 교착상태에 들어가면 발생한다. 그러나 짝수 번호의 철학자들이 왼쪽 포크를 먼저 집어 들고 홀수 번호의 철학자들은 오른 쪽 포크를 먼저 집어들기 때문에 먼저 같은 포크를 집어 들고자 하는 한 쌍의 철학자들만 있다. 이러한 철학자들 중 어떠한 사람도 다른 사람을 기다리는 동안 포크를 가지고 있는 사람이 없기 때문에 이러한 좌석 구성에서는 순환대기는 결코 발생하지 않고 그래서 교착 상태는 발생하지 않는다. 그러나 특정 철학자가 포크를 항상 가지고 있다면 무한 연기가 발생할 가능성도 있다.

11 교착 상태가 발생하기 위한 네 가지 필요 조건을 기술하라. 각 조건이 왜 필요한지 직관적으로 생각나는 이유들에 대해 논하라.

상호 배제 조건 : 두 개 이상의 프로세스가 동시에 임계영역에 접근하는 경우 공유자원의 혼란이 올 수 있기 때문이다.

대기 조건 또는 보유 후 대기 조건 : 프로세스들이 서로 자신의 자원은 내놓지 않고 동시에 서로의 자원을 획득하기 위해 대기하는 경우 어느 프로세스도 결코 원하는 자원을 얻을 수 없기 때문이다.

비선점 조건 : 프로세스는 자원을 무한정 사용하거나 기아상태의 프로세스가 발생할 수 있기 때문이다.

순환 대기 조건 : 순환 고리형이 아니라면 이 프로세스들은 언젠간 자원을 획득하게 될 수도 있다. 고리형이어야 프로세스들이 원하는 자원을 획득할 수 없는 교착 상태가 된다.

교수님 답

4가지 필요 조건 : 상호배제조건, 대기 조건, 비선점 조건, 순환대기 조건    상호배제조건 : 자원은 한 번에 단 하나의 프로세스에 의해 배타적으로 사용된다. 이 때문에 다른 프로세스를 강제적으로 대기시키게 하는 방식이 만들어짐.

대기 조건 : 배타적으로 자원을 획득한 프로세스가 해당자원을 보유한 채 다른 자원을 얻으려고 대기할 수 있다.

비선점 조건 : 일단 프로세스가 자원을 확보하면 해당 프로세스가 자원을 모두 사용할 때까지 시스템이 프로세스의 제어를 빼앗을 수 없다.

순환대기 조건: 2개 이상 프로세스가 순환고리를 형성하고 있는 경우에 해당된다. 즉 프로세스들이 순환고리 안에 있는 다음 프로세스가 점유하고 있는 자원을 대기한다.

19 교착 상태 회피가 교착 상태 방지보다 직관적으로 호소력이 있는 이유는 무엇인가?

교착 상태 방지를 사용하면 자원 활용도가 떨어지는 결과를 초래한다. 그러나 교착 상태 회피는 교착 상태의 가능성이 어느 정도 있을 수 있지만 교착 상태가 발생하려는 조짐이 보일 때마다 조심스럽게 비켜서는 전략을 취한다. 따라서 교착 상태도 피하고 자원 활용도도 높일 수 있는 것이다.

교수님 답

교착상태 회피는 자원 사용을 더 효율적으로 하는 것으로 보인다. 역시 교착상태회피가 더 많은 동시 사용자를 허용한다.

24 자원을 그룹으로 할당하면 은행원 알고리즘이 여전히 제대로 동작할 수 있는가? 답을 상세히 설명하라.

자원을 그룹으로 할당해도 가용 자원 수가 현재 요청 수 보다 많고, 그로 인하여 프로세스가 정상적으로 수행되며, 반납된 자원을 이용하여 다른 프로세스들을 모두 수행할 수 있다면 제대로 동작할 수 있을 것이다.

교수님 답

가능하다. 이것은 시스템의 상태에 의존적이다. 목표가 단순히 모든 시간내내 시스템의 상태를 안전하게 유지하는 것이다. 충분한 자원들이 요구를 들어주고 시스템의 안전상태 를 유지할 만큼 충분하면 은행원 알고리즘은 잘 동작한다.

25 은행원 알고리즘을 사용해 교착 상태 회피 방법을 사용하는 시스템이 다섯 개 프로세스(1, 2, 3, 4, 5 프로세스)와 네 가지 유형(A, B, C, D)의 자원을 포함하고 있다. 각 유형에는 여러 자원이 있다. 표[7-7]과 [표7-8]에 나타낸 이 시스템은 안전 상태인가? 답을 설명하라. 안전 상태면 모든 프로세스가 성공적으로 실행을 마칠 수 있는 방법을 보여라. 불안전 상태면 교착 상태가 어떻게 발생할 수 있는지 보여라.

프로세스	현재 대여 수	최대 필요 수	현재 요청 수
	A B C D	A B C D	A B C D
1	1 0 2 0	3 2 4 2	2 2 2 2
2	0 3 1 2	3 5 1 2	3 2 0 0
3	2 4 5 1	2 7 7 5	0 3 2 4
4	3 0 0 6	5 5 0 8	2 5 0 2
5	4 2 1 3	6 2 1 4	2 0 0 1

총 자원 수	가용 자원 수
A  B  C  D	A B C D
13 13 9 13	3 4 0 1

자원을 할당할 프로세스 번호	수행 전 가용 자원 수	수행 후 반납된 자원 수	수행 후 총 가용 자원 수	해결된  프로세스 번호
5	3 4 0 1	4 2 1 3	7 6 1 4	5
2	7 6 1 4	0 3 1 2	7 9 2 6	5, 2
1	7 9 2 6	1 0 2 0	8 9 4 6	5, 2, 1
3	8 9 4 6	2 4 5 1	10 13 9 7	5, 2, 1, 3
4	10 13 9 7	3 0 0 6	13 13 9 13	5, 2, 1, 3, 4

위와 같이 모든 프로세스의 실행을 성공적으로 마칠 수 있으므로 해당 알고리즘은 안전 상태이다.

교수님 답

각 자원의 유형에 대한 현 요구가 유용한 유형의 자원의 수보다 적거나 같으면 프로세스의 수행은 마치고 모든 자원을 반납한다. 프로세스 2 혹은 프로세스 5는 현 상태에서 마칠 수 있다. 다음의 이벤트 순서를 생각하자: 프로세스 2가 마치면 유용한 자원의 상태는 (3,7,1,3)이 된다. 프로세스 5가 마치게 되면 유용한 자원의 상태는 (7,9,2,6)이 된다. 이 시점에서 남아 있는 각 프로세스들은 마칠 수 있고 자원들을 반납한다. 결국 모든 프로세스들의 수행은 끝나게 된다. 따라서 상태는 안전 상태이다.

28 교착 상태가 발생할 가능성이 있는 시스템에서 어떤 경우에 교착 상태 탐지 알고리즘을 사용하겠는가?

교착 상태 탐지 : 교착 상태가 발생할 수 있는 시스템에서 사용한다. 교착 상태 탐지의 목적은 교착 상태 발생 여부와 관련 프로세스 및 자원을 밝히는 것이다. 교착 상태 발생을 허용하면서 교착 상태의 위치를 추적하고 제거한다.

교착 상태 탐지 알고리즘은 대체로 교착 상태 성립을 위한 다른 조건들을 충족함을 전제로 할 때 ‘순환 대기 존재 여부’에 초점을 맞춘다. 즉 ‘순환 대기’의 경우에 해당 알고리즘을 사용한다.

교수님 답

교착상태가 의심될 때 사용된다. 즉 어떤 프로세스들이 잠시 동안 동작하는 상태로 들어가지 못하거나 혹은 초기 감지 후 주기적으로 동작하고자 할 때 사용된다.

34 자원이 고장나서 사용이 어려워지면, 일반적으로 교착 상태와 무기한 연기의 위험이 증가하는가, 감소하는가? 답을 설명하라.

교착 상태의 위험성은 증가한다. 자원이 고장나지 않았으면 제대로 수행될 수 있었을 프로세스의 자원요청이 좌절될 수 있기 때문이다. 하지만 무기한 연기의 위험과는 관계가 없다. 자원이 줄어듦으로 인하여 프로세스가 대기하는 시간만 늘어날 뿐, 그 위험성이 증가하지는 않는다.

교수님 답

그러한 상태는 교착상태와 무기한 연기의 가능성을 증가시킬 수 있다. 은행원 알고리즘 의 교착회피 구조에서 이전의 안전 상태를 불안전하게 만드는 효과를 가져올 수 있다. 즉, 프로세스가 수행할 수 있는 유용한 자원이 없어지기 때문에 프로세스의 수행을 끝낼 수 없는 상태가 될 수 있다.