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

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

01 운영체제 학습자들에게 병행성에 관한 연구가 적당한 주제인 몇 가지 이유를 기술하라.

병행성에 의해 프로세스나 스레드가 공유자원에 접근하게 된다. 이 주제는 시스템에서 아주 중요한 사항이다.

[교수님 답]

자원관리자로써 OS는 비동기적으로 그리고 병행적으로(동시적으로) 수행하는 여러 스레드들에게 자원들을 사용하게 만든다. 동시적(병행적)으로 수행하는 스레드들에 의해 공유하는 자원들이 동기화되어 사용되어야 할 때를 이해하여야 하고 이러한 동기화를 어떻게 구현하는지를 알아야 하기 때문에 병행성(동시성) 연구는 매우 중요하다.

03 데커의 알고리즘, testAndSet, swap 그리고 세마포어 연산 P, V는 상호 배제를 강제하는 데 사용할 수 있는 다양한 방법이다. 이들을 비교 대조하라. 각각의 장단점을 생각해보라.

데커의 알고리즘은 스레드가 임계 영역에 들어가려는 의도를 알리는 ‘플래그’개념에 ‘선호 스레드’개념을 추가했다. 선호 스레드는 여러 스레드가 동시에 임계 영역에 들어가려고 할 때 먼저 임계 영역에 진입할 수 있다.

timeAndSet은 다른 스레드들이 자신들의 임계 영역에 들어가지 못하게 잠그는 사이에 프로세서를 선점당할 수 있는 가능성을 제거한다. 

Swap은 swap 명령어를 사용하여 상호 배제를 강제한다. swap에는 p1MustWait 혹은 p2MustWait 와 occupied 값이 들어간다. 하드웨어 명렁어인 swap은 단순히 상호 배제 기능만을 제공하는 다른 명령어들보다 훨씬 유용하다.

세마포어 연산은 대기 스레드들을 블록해 바쁜 대기를 피하게 함으로써 커널에서 구현할 수 있다. 세마포어는 보호 변수와 V연산을 대기하는 스레드들을 대기하게 하는 큐를 사용해 구현할 수 있다. 

[교수님 답]

 

알고리즘	장점	단점
데커 알고리즘	HW 지원(예, 인터럽트)없이 수행함	2개의 스레드에 대해서만 상호배제 제공
testAndSet	데커 알고리즘보다 단순하다.	HW가 지원하기 떄문에 이식성이 떨어진다.
SWAP	데커 알고리즘보다 단순하다.	HW가 지원하기 떄문에 이식성이 떨어진다.
세마포어 P, V동작	고수준의 상호배제 기능을 수행한다.	상호배제가 P, V 구현 시 사용된 다른 기능들에 의해 수행된다.

 주) testAndSet 과 swap은 2개의 인수를 사용하는데, 전자는 수행후에 2번째 인수가 항상

‘참’으로 설정되어 있지만, 스왑은 호출이전에 2번째 인수 값이 첫 번째 인수의 값이 되도록

설정한다.

11 상호 배제 프리미티브는 바쁜 대기나 블록킹을 사용해 구현할 수 있다. 각 접근법의 적용 가능성과 상대적인 장점을 논의하라.

바쁜 대기를 사용하면 해당 프로세스는 의미 없는 행위를 하느라 자원을 낭비하게 되므로, 비효율적이다. 어차피 자원을 사용할 수 없으므로, 해당 조건 확인문에서 벗어날 수 없다. 차라리 다른 프로세서에게 CPU권한을 할당시켜주는 것이 효율적이다. 따라서 사용할 자원이 없는 경우 블록킹 상태가 되면 해당 자원을 다른 프로세서가 유용하게 사용하여 더 효율적인 시스템이 될 것이다.

[교수님 답]

이러한 2가지 방법은 장단점이 있기 때문에 응용에 맞게 사용되어야 한다. 바쁜 대기 방법으

로써 스레드가 계속하여 작업을 수행할 수 있을 때까지(즉, 어떤 플래그가 설정될 때까지) 프

로세서는 플래그를 계속 검사한다. 플래그가 설정될 때 만일 해당 프로세스가 실행 상태에 있

다면 계속하여 수행한다. 그렇지 않다면(즉, 준비 상태이 있다면) 쓰레드는 실행상태가 되었을

때 동작을 계속한다. 이 방법의 문제는 해당 스레드가 계속하여 수행되기 전에 많은 시간을

지연된다면 프로세서는 시간을 허비하게 된다는 것이다. 블록 방법에서는 어떠한 프로세서 시

간도 허비하지 않는다는 것이다. 스레드는 플래그를 검사하여 설정이 되어 있지 않았다면 프

로세서 사용을 포기하고 즉시 블록 상태로 들어간다. 스레드가 계속하여 수행될 때(즉, 다른

스레드가 자원을 다 사용하고 반납할 때) 스레드 먼저 블록 상태를 준비 상태로 상태 전이를

하고 준비 큐의 앞에 그 스레드를 삽입하여 바로 바로 수행하게 한다. 실시간 응용에서는 스

레드들이 바로 반응할 필요가 있다. 즉 자원이 반납되는 플래그가 설정되면 바로 즉시 해당

스레드가 동작되어야 한다. 스레드를 블록 상태에서 준비상태로 만들고 준비 큐에 넣는 것은

오버헤드 시간을 요구한다. 이는 실시간 응용에서는 알맞지 않을 수 있기 때문에 바쁜 대기

방법이 좋을 수 있다.

12 운영체제 커널에서 바이너리 세마포어와 바이너리 세마포어 연산을 구현하는 방법을 자세히 설명하라.

바이너리 세마포어는 P연산과 V연산, 그리고 보호 변수를 이용한다. 시스템은 세마포어 occupied를 1로 초기화한다. P연산을 통하여 스레드가 세마포어 S로 보호하는 임계 영역에 들어가려고 할 때 스레드는 세마포어가 존재하면 1을 빼고, 없으면 대기 스레드 큐에 넣는다. V연산을 통하여 S를 대기하는 스레드가 있으면 큐에서 대기하는 다음 스레드를 시작하고, 없으면 세마포어에 1을 더한다. 

[교수님 답]

커널은 세마포어의 값을 표현하도록 한 비트를 할당할 뿐만 아니라 세마포어에 블록된 스레드를 대기하도록 큐를 할당한다. 이러한 큐는 PCB들의 연결 리스트(linked list) 데이터 구조를 사용하여 구현될 수 있다.

스레드가 P 동작을 호출할 때 커널은 인터럽트를 비활성화시킨다. 세마포어 값이 0이면 스레드는 블록 큐의 끝에 추가된다.이 때 사용되는 블록 큐가 연결 리스트(linked list)구조를 사용한다. 그 후 인터럽트가 재활성화된다. 세마포어 값이 1이면 스레드는 새마포어 값을 0 로 설정하고 인터럽트를 재활성화한다. 다시 말하면 세마포어 값이 1이면 자원이 있는 상태이고 0이면 자원이 없는 상태이다.

스레드가 V 동작을 호출할 때 커널은 P 동작과 같이 먼저 인터럽트를 비활성화한다. 그리고 커널은 블록 큐가 비어 있는지를 확인한다. 만일 큐가 비어있다면(즉, 대기하고 있는 스레드가 없다면) 세마포어의 값을 1로 설정하고 인터럽트를 활성화시킨다. 만일 세마포어를 기다리고 있는 스레드가 있다면(즉, 큐에 스레드가 있다면) 커널은 블록 큐로부터 스레드를 꺼내어 (deque 시키고) 그 스레드를 준비 큐에 넣는다. 그리고 인터럽트를 재활성화시킨다.

13 단일 프로세서 시스템에서 상호 배제 프리미티브를 구현할 때, 인터럽트 활성화와 비활성화를 유용하게 사용하는 방법을 설명하라.

인터럽트를 이용하여 상호 배제 프리미티브를 구현하는 것은 올바른 방법이 아니지만 제한적으로 사용할 수는 있다. 짧은 시간이 필요한 신뢰할 만한 코드에 대해 커널이 인터럽트를 비활성화해서 최적화를 이룰 수 있다.

[교수님 답]

실제로 상호배제 기능을 구현하는 것은 매우 직선적이다. 스레드가 enterMutualExclusion()

을 수행할 때 모든 인터럽트는 비활성화된다. 그리고 스레드는 중요 영역을 인터럽트가 안들

어오는 상태에서 수행된다. 쓰레드가 exitMutualExclusion()를 수행라 때 인터럽트는 재활성

화된다. 인터럽트를 비활성화시키지 않은 상태에서 중요 영역에 들어가는 경우, 인터럽트들에

의해 다른 스레드들이 수행되기 때문에 중요 영역을 수행하는 스레드의 수행 시간이 길어지기

때문에 다른 스레드들이 해당 중요 영역을 사용하기를 원할 때 많은 시간이 지연되는 문제가

있다.

23 많은 스레드가 P 연산을 호출하려고 한다면 어떤 스레드를 선택해서 진행하게 해야 하는가? 여기서 주요 쟁점은 무엇인가? 단일 프로세서 시스템에서는 어떤 기준으로 스레드를 결정할 수 있는가? 멀티프로세서 시스템에서는 어떤 기준으로 다음 진행할 스레드를 선택하는가?

단일이나 멀티 프로세서 시스템에서는 큐에서 가장 앞에 있는 스레드를 선택하여 진행하게 해야 한다. 멀티 프로세서 시스템에서는 우선순위나 선호 스레드에 따라 그 순서가 변경될 수도 있다.

[교수님 답]

중요 쟁점은 무한 지연을 피하는 것이다. 무한 지연을 피하는 방법은 선입선출 순으로 요구들

을 서비스하는 것이다. 이 방법은 하나의 프로세서(uniprocessor)에서는 쉽다. 이유는 다음과

같다: 단 하나의 스레드가 한 번에 하나의 P 동작을 시도하여 이러한 요구들의 시간 스탬프가

찍혀서 선입선출로 서비스할 수 있기 때문이다, 다중 프로세스(multiprocessor)에서는 여러

스레드들이 P 동작들을 동시에 시도하기 때문에 시간 축 상의 선입선출 방식이 알맞지 않다.

동작가능한 해결책은 선입선출 방식을 사용하고 동시에 P 동작을 호출하는 경우 스레드 ID(식

별자) 번호 순으로 요들을 서비스함으로써 충돌을 해결할 수 있다.

24 바이너리 세마포어만을 지원하는 시스템이 있다고 하자. 이 시스템에서 바이너리 세마포어를 사용해카운팅 세마포어를 시뮬레이션할 수 있음을 보여라.

바이너리 세마포어가 여러 개 존재하면 카운팅 세마포어를 시뮬레이션할 수 있다. 자원의 개수만큼 바이너리 세마포어를 생성하면 된다. 그렇게 하면 카운팅 세마포어와 같은 기능을 하도록 구현할 수 있다.

[교수님 답]

알고리즘은 상호배제를 제공하지 못한다. T2가 먼저 수행한다고 가정하자. T2는 turn이 2인

지를 확인한다. turn이 현재 1 이면 T2는 안쪽 루프로 들어간다. 그리고 T2는

t1WantsToEnter 값이 ‘참(true)’ 인지를 확인한다. T1이 수행을 시작하지 않았기 때문에

t2WantsToEnter는 ‘거짓(false)’로 현재 설정되어 있다. T2가 turn을 2로 설정하기 바로 전

에 문맥 교환(context switch)이 일어난다. 그러면 T1은 수행을 시작한다. turn이 아직 1 이

기 때문에 T1은 중요 영역으로 바로 들어갈 수 있다. T1이 중요 영역에 머물고 있다면 다른

문맥교환(context switch)이 일어난다.

T2는 수행을 계속하며, turn 값은 2로 설정되어 있다. turn이 더 이상 2값이 아니기 때문에

T2는 루프를 빠져 나와 중요 영역으로 들어간다. 그러나 2개의 스레드는 바로 지금 동시에

중요 영역에 있게 된다.

28 [예제 5-19] 코드가 상호 배제를 지원하는가? 그렇지 않다면 상호 배제가 지켜지지 않는 부분을 지적하라.

지원하지 않는다. 만약 두 스레드가 한 줄씩 나란히 연속적으로 번갈아가며 실행될 경우 t1WantsToEnter와 t2WantsToEnter가 둘 다 true가 되어 바쁜 대기 상태에 들어가서 스레드 둘 다 무기한 연기가 될 수 있다.

[교수님 답]

   없음

29 [예제 5-19]의 알고리즘에서 위반하고 있는 또 다른 상호 배제 제약 조건은 무엇인가?

28번의 답에 의하여 해당 알고리즘은 교착 상태(Deadlock)에 빠질 수도 있다.

시스템 :

      

int turn = 1;

boolean t1WantsToEnter = false;

boolean t2WantsToEnter = false;

 

startThreads();     //두 스레드를 초기화하고 시작함

 

스레드 T1:

      

void main()

{

       while(!done)

       {

             t1WantsToEnter = true;

             while(turn != 1)

             {

                    while(t2WantsToEnter);

                    turn = 1;

             }//while문 끝

             //임계 영역 코드

             t1WantsToEnter = false;

             //임계 영역 외부 코드

       }//바깥쪽 while 문 끝

}//스레드 T1 끝

 

스레드 T2:

      

void main()

{

       while(!done)

       {

             t2WantsToEnter = true;

             while(turn != 2)

             {

                    while(t1WantsToEnter);

                    turn = 2;

             }//while문 끝

             //임계 영역 코드

             t2WantsToEnter = false;

             //임계 영역 외부 코드

       }//바깥쪽 while 문 끝

}//스레드 T2 끝

 

[교수님 답]

알고리즘은 중요 영역 밖에 있는 스레드가 다른 스레드가 그 중요 영역에 들어가는 것을 방해

할 수 없는 제약조건을 위반한다. 이 알고리즘에서는 스레드 T1이 수행되지 않고 turn이 1이면, 스레드 T2는 중요영역 코드를 결코 수행하지 못한다.