본문 바로가기
Operating System

운영체제 (Silberschatz) 1.1~5.5 주요 연습문제 풀이

by kmmguumnn 2018. 4. 23.

운영체제 (Silberschatz 저; 일명 공룡책) 한글판의 주요 연습문제 풀이입니다. 범위는 1장부터 5.5(멀티프로세서 스케줄링)까지이며, 중요하다고 생각되는 주요 문제만 선정해 올립니다. 혹시 틀린 풀이가 포함되어 있다면, 댓글로 남겨 주시면 감사하겠습니다.




1.4 대칭적 다중 처리(SMP)와 비대칭적 다중 처리(AMP)의 차이점을 설명하시오. 다중 처리기 시스템의 세 가지 장점과 한 가지 단점은 무엇인가?


대칭적 다중 처리(SMP)는 각 프로세서가 OS의 모든 task를 수행하고, 모든 프로세서는 대등하다. 비대칭적 다중 처리(AMP)는 하나의 메인 프로세서가 시스템을 제어하고, 다른 프로세서들은 메인 프로세서의 명령을 수행하거나 미리 정의된 태스크를 수행한다.


장점: 증가된 처리량(throughput)

장점: 프로세서가 주변 장치, 저장 장치 등을 공유하므로, 여러 개의 단일 시스템에 비해 비용이 절약됨.

장점: 하나의 프로세서가 고장나도 다른 처리기가 그 일을 대신 할 수 있다.

단점: 싱글 프로세서 방식에 비해 OS가 처리해야 하는 것이 많고 구현이 복잡하다.



1.8 인터럽트의 목적은 무엇인가? 트랩과 인터럽트의 차이점은 무엇인가? 트랩은 사용자 프로그램에 의해 의도적으로 발생할 수 있는가? 만일 그렇다면 그 목적은 무엇인가?


인터럽트는 CPU에게 I/O의 상태를 알리기 위해 필요하다. I/O 등의 외부 이벤트에 의해 발생되며 인터럽트의 타이밍은 복제 불가능하다.

트랩은 소프트웨어, 즉 프로그램에 의해 발생되는 인터럽트이며, 실행되는 프로그램과 동시에 발생하기 때문에 디버깅을 위해 의도적으로 발생시킬 수 있다.



1.9 CPU의 실행 부하가 증가하는 것을 피하기 위하여 직접 메모리 액세스 방식이 고속 입출력 장치에 사용된다.

  1. 전송을 조율하기 위하여 CPU는 어떻게 장치와 인터페이스 하는가?

CPU는 디바이스 컨트롤러 내의 레지스터 셋에 필요한 값을 load하여 DMA 연산을 초기화한다. 이후 디바이스가 CPU에서 명령을 받으면 해당 연산을 시작한다.


   b. CPU는 메모리 연산이 종료되었음을 어떻게 알 수 있는가?


디바이스가 연산을 끝내면, 연산이 끝났음을 인터럽트를 이용해서 디바이스 드라이버에게 통보한다.


   c. DMA가 데이터를 전송하는 동안 CPU는 다른 프로그램을 실행할 수 있다. 이 프로세스는 사용자 프로그램의 실행을 방해하는가? 만일 그렇다면, 어떤 형태의 방해가 발생하는지 설명하시오.


메모리 컨트롤러가 메모리 버스에 대한 공평한 허가를 내줌으로써, 디바이스와 CPU는 메모리에 동시에 접근할 수 있다. CPU와 디바이스가 메모리 버스에 대한 접근을 위해 경쟁하므로, 메모리 연산 속도가 최고치가 아닐 수 있다.



1.10 일부 컴퓨터 시스템은 특권 모드 연산을 하드웨어로 제공하지 않는다. 이러한 컴퓨터에 안전한 운영체제를 구축할 수 있는지를 고려해 보라. 그것의 가능, 불가능 모두에 대한 논거를 제시하시오.


하드웨어로 제공하지 않는 특권 모드 연산을 소프트웨어 인터프리터를 통해 유저 프로그램으로도 수행할 수 있도록 만들 수 있다.











2.2 운영체제에게 매개변수를 전달하는 보편적인 방법 3가지를 설명하시오.


  1. 매개변수를 레지스터에 전달
  2. 메모리 내의 블록 or 테이블에 매개변수를 전달. 레지스터에는 블록 or 테이블의 주소가 전달됨
  3. 스택에 push하여 매개변수 저장, pop하여 매개변수 읽기



2.10 시스템을 설계할 때 마이크로커널 방식을 사용하는 장점은 무엇인가? 마이크로커널 구조에서 사용자 프로그램과 시스템 서비스가 상호작용하는 방식에 대해 설명하시오. 마이크로커널 방식을 사용할 때의 단점은 무엇인가?


UNIX(monolithic; 커널 안에 system call 모두 포함)는 커널이 커지고 관리 어려워짐 

→ 커널에서 중요하지 않은 요소들은 시스템 및 사용자 수준 프로그램으로 빼고, 커널은 작게


장점: 모든 새로운 서비스는 사용자 공간에 추가되며, 따라서 커널의 변경이 필요없으므로 운영체제의 확장이 용이하다. 대부분의 서비스가 커널이 아니라 사용자 프로세스로 수행되므로 보안성과 신뢰성이 높다.


사용자 프로그램과 시스템 서비스는 message passing에 의해 상호작용한다. 사용자 프로그램이 마이크로커널에 메시지를 전달하면, 커널은 해당 인터럽트(이벤트)를 처리하는 다른 프로세스에게 메시지를 넘기고 처리를 요청한다.


단점: 사용자 프로그램 및 시스템 서비스와 커널 간의 통신이 자주 발생하므로 오버헤드가 커진다.



2.11 적재가능 커널 모듈을 사용하는 장점은 무엇인가?


모든 system call들을 커널에 포함시키는 것이 아니라, 필요할 때 모듈을 로드하고 사용되지 않을 때는 해제할 수 있으므로 메모리 낭비를 줄일 수 있다. 모듈에서 임의의 다른 모듈을 호출할 수 있어서 유연하다. 모듈 간에 통신하기 위해 메시지 전달을 할 필요가 없어서 효율적이다.










3.1 단기, 중기, 장기 스케줄링의 차이점을 설명하시오.


단기 스케줄링은 메모리에서 실행 준비된 task(ready queue)를 CPU에 할당하는 것이다. CPU를 위해 자주 새로운 프로세스를 선택해야 하므로, 매우 빠르게 진행되어야 한다.

중기 스케줄링은 시분할 시스템에서 사용되며, 실행을 위해 메모리에서 경쟁 중인 프로세스들 중 일부를 제거하고 차후에 복원한다. 

장기 스케줄링은 디스크에서 메모리로 적재할 프로세스를 선택한다. 실행 빈도수가 훨씬 적다.



3.2 프로세스들 사이에 문맥을 교환할 때 커널이 수행하는 작업을 설명하시오.


현재 실행 중인 프로세스의 PCB에 context를 저장하고, 다음에 실행할 프로세스의 PCB로부터 context를 reload한다. context는 CPU 레지스터의 값, 프로세스 상태, 메모리 관리 정보 등을 포함한다.



3.4 UNIX와 Linux 시스템의 init 프로세스의 역할을 프로세스 종료의 관점에서 설명하시오.


부모 프로세스가 wait()를 호출하는 대신 종료되어 버리는 경우, 고아(orphan) 프로세스의 새로운 부모 프로세스로 init 프로세스를 지정하여 문제를 해결한다.



3.5 다음 프로그램에서 부모 프로세스를 포함하여 총 몇 개의 프로세스가 생성되는가?


#include <stdio.h>

#include <unistd.h>


int main()

{

    int i;

    for (i = 0; i < 4; i++)

        fork();


    return 0;

}


fork()를 4번 실행하므로, 부모 프로세스를 포함해  =16개의 프로세스가 생성된다.










4.7 Amdahl의 법칙을 사용하여 60%의 병렬 수행 부분을 가진 응용을 (a) 두 개의 계산 코어와 (b) 4개의 계산 코어를 가진 컴퓨터에서 실행했을 때의 속도 향상 이득을 계산하시오.


 

S가 0.4이므로  

  1. N: 2

10/7 ≓ 1.43배 속도 향상


  1. N: 4

20/11 ≓ 1.82배 속도 향상










5.1 스케줄러가 입출력 중심 프로그램과 CPU 중심 프로그램을 구분하는 것이 중요한 이유는 무엇인가?


입출력 중심 프로그램은 짧은 CPU 버스트를 많이 가지고, CPU 중심 프로그램은 다수의 긴 CPU 버스트를 갖는다. 다중 프로그래밍(CPU 작업과 입출력 작업을 병행하는 것. CPU가 수행할 작업을 항상 하나 가지도록 작업을 구성하여 CPU 사용률을 늘림. 단일코어라고 가정함) 환경에서 프로세스의 실행은 CPU 실행과 입출력 대기의 사이클로 구성되며, 프로세스들은 이 두 상태 사이를 왔다갔다 한다. 이러한 분포는 적절한 CPU 스케줄링 알고리즘을 선택하는 데 매우 중요할 수 있다.



5.2 다음과 같은 두 스케줄링 기준들은 어떤 상황에서 서로 충돌하는 지 논의하시오.

  1. CPU 이용률과 응답 시간

CPU 이용률은 Context Switching에 따른 오버헤드가 최소화 될 때 증가한다. Context Switching 오버헤드는 문맥전환이 빈번히 일어나지 않아야 최소화 된다. 그러나 Context Switching이 빈번히 일어나지 않는다는 것은 프로세스 사이의 CPU 전환이 적으므로 응답시간을 늘리는 결과를 초래한다.


   b. 평균 총처리 시간과 최대 대기 시간


평균 총처리 시간(프로세스의 제출부터 완료까지의 시간)은 짧은 작업을 먼저 수행해야 최소화된다. 그러나 이런 스케줄링 정책은 작업시간이 긴 작업들을 굶주리게(starving) 하고 결론적으로 그들의 대기시간을 증가시키는 결과를 가져오므로 최대 대기 시간도 늘어난다.


   c. 입출력 장치 이용률과 CPU 이용률


입출력 장치와 CPU는 항상 바쁘게 유지 되어야 한다. 단일 프로세서는 둘 다 바쁘게 사용할 수 없고 하나만 사용 가능하다.



5.4 5장에서 다양한 커널 자료구조에서 발생할 수 있는 경쟁조건에 대해 논의하였다. 거의 모든 스케줄링 알고리즘은 실행 큐를 유지하여 스케줄 할 프로세스들을 관리한다. 다중코어 시스템에서는 다음 두 가지 선택이 존재한다. (1) 각 처리기 코어마다 각자의 실행 큐를 유지하거나 (2) 하나의 실행 큐를 모든 처리기 코어가 공유한다. 각 선택의 장단점은 무엇인지 설명하시오.


  1. 각 처리기 코어마다 각자의 실행 큐를 유지: Symmetric MultiProcessing(SMP)

장점: 병목현상이 없다. 여러 개의 프로세서가 동시에 수행될 수 있다. 시스템의 전반적인 정보를 통일적이고 일관성 있게 운영한다.

단점: 각 프로세서가 동등한 입장이기 때문에 공유된 장치를 사용하려고 할 때 대립문제가 발생하므로

적절한 대비책이 필요하다. 프로세서의 수를 늘린다고 해도 시스템 효율은 향상되지 않는다.


  1. 하나의 실행 큐를 모든 처리기 코어가 공유: Asymmetric MultiProcessing(AMP)

장점: 한 프로세서만 시스템 자료구조를 접근하여 자료 공유의 필요성을 배제하므로 간단하다.

단점: 주 프로세서에 이상이 있을 경우 전체 시스템에 문제가 생긴다.



5.7 다음 프로세스들의 집합을 생각해 보자. CPU 버스트 시간 단위는 밀리초이다. 프로세스들은 시간 0에 , , ,  순서로 도착한다고 가정한다.

프로세스

버스트 시간

우선순위

2

2

1

1

8

4

4

2

5

3


  1. FCFS, SJF, 비선점 우선순위(높은 우선순위 값이 높은 우선순위를 의미) 그리고 라운드 로빈(할당량 = 2) 스케줄링을 이용해 프로세스들의 실행을 보이는 Gantt 차트를 그리시오.

<FCFS>

0                 2        3                                                                      11                         15                                20


<SJF>

0      1                    3                             7                                  12                                                                 20




<비선점 우선순위>

0                                                                    8                             13                 15                                 19   20


<Round Robin>

0             2       3               5                7               9               11              13             15             17     18        20


  1. a의 각 스케줄링 알고리즘 별 각 프로세스에 대한 총처리 시간은 얼마인가?


FCFS

2

3

11

15

20

SJF

3

1

20

7

12

비선점 우선순위

15

20

8

19

13

Round Robin

2

3

20

13

18


  1. a의 각 스케줄링 알고리즘 별 각 프로세스에 대한 대기 시간은 얼마인가?


FCFS

0

2

3

11

15

SJF

1

0

12

3

7

비선점 우선순위

13

19

0

15

8

Round Robin

0

2

12

9

13


  1. 위의 알고리즘 중에서 어느 스케줄이 최소의 평균 대기시간을(모든 프로세스들에 대해) 보이는가?

FCFS

SJF

비선점 우선순위

Round Robin

6.2

4.6

11

7.2



5.10 다음 알고리즘 중 기아 현상을 일으킬 수 있는 알고리즘은 무엇인가?

  1. 선입 선처리
  2. 최소 작업 우선(SJF)
  3. 라운드 로빈
  4. 우선순위


b, d



5.15 다음의 알고리즘들이 짧은 프로세스를 우대하는 정도의 차이에 대해 설명하시오.

  1. FCFS
  2. RR
  3. 다단계 피드백 큐


RR < 다단계 피드백 큐 < FCFS 순서로 우대한다. 다단계 피드백 큐는 큐 내부에서는 RR과 동일하지만 큐 간 경쟁이 필요하다.


댓글