Operating System Concepts Chapter 5. CPU 스케쥴링 문제풀이

chapter 5. 연습문제 풀기 숙제

5.1. 스케쥴러가 입출력 중심 프로그램과 CPU 중심 프로그램을 구분하는 것의 중요성?

-> 중요하다. 입출력 중심의 프로그램은 대개 짧은 CPU버스트를 가지고, CPU 중심 프로그램은 다수의 긴 CPU 버스트를 가진다. 그렇기 때문에, 이 둘을 구분하는 것은 입출력 중심의 프로그램에 조금 더 많은 우선순위를 두게 함으로써 컴퓨터 자원의 효율적인 사용을 도울 수 있다. 이러한 프로그램의 구분은 스케쥴러가 어떠한 스케쥴링 알고리즘을 선택할 것인지를 결정할 수 있게 하기도 한다.

5.3. 10개의 입출력 중심 태스크와 1개의  CPU 중심 태스크를 실행하는 시스템이다. 입출력 중심 태스크는 CPU에서 1 밀리 초 실행한 후 한 번씩 입출력 요구, 각 입출력 작업은 완료될 때까지 10밀리초가 걸린다고 가정함. 문맥 교환 오버헤드는 0.1 밀리초이다. 모든 프로세스들은 장기간 실행되는 프로세스들이라고 가정하자. 다음과 같은 시간 할당량을 가질 때 라운드 로빈 스케쥴의 CPU 이용률은 얼마인가?

a. 시간 할당량 1 밀리초

-> 10 / 10 + 0.1 = 약 90.9

b. 시간 할당량 10 밀리초

-> 20 / (10 + 0.1*10) + 10 + 0.1 = 94.7

5.5. 다단계 큐 스케쥴링을 구현한 시스템 상, 자신의 프로세스에게 할당된 CPU 시간을 최대로 하기 위해서 어떤 전략을 세워야 되나?

-> 큐 마다 CPU 시간의 일정량을 받아 자기 큐에 맞는 다른 알고리즘으로 스케쥴링 한다.

5.6. 시분할 스레드를 위한 Solaris 운영체제의 스케쥴링 알고리즘 상에서,

a. 우선순위 10의 스레드의 시간 할당량은 밀리초 단위로 얼마인가? 55의 스레드는?

-> 160,40

b. 우선순위 35의 스레드가 봉쇄없이 시간 할당량을 소진했다고 가정하자. 스케쥴러는 이 스레드에게 어떤 우선순위를 배정하겠는가?

-> 25

c. 우선순위 35의 스레드가 시간 할당량이 만료되기 전에 입출력을 위해 봉쇄되었다고 가정하자. 스케쥴러는 이 스레드에게 어떤 우선순위를 배정하겠는가?

-> 54

5.7. 다음의 알고리즘이 짧은 프로세스를 우대하는 정도의 차이

a. FCFS

-> 짧은 프로세스들의 이점은 거의 없다고 보면 된다. 먼저 cpu를 요청하는 프로세스가 먼저 cpu를 할당받는 구조이기 때문에, 몇몇 짧은 프로세스가 긴 프로세스의 뒤에 오면 대기해야 한다.

b. RR

-> 짧은 프로세스와 긴 프로세스는 똑같은 시간동안 처리되고 교체된다. 짧을 수록 빨리 끝나기 때문에 더 유리하다.

c. 다단계 피드백 큐

-> CPU버스트의 성격에 따라 프로세스가 큐 사이를 이동할 수 있기 때문에, 높은 우선순위의 큐에는 입출력 중심의 프로세스, 대화형 프로세스들을 배정한다. 따라서, 짧은 프로세스들이 긴 프로세스들보다 상대적으로 높은 우선순위를 가지기 때문에 유리하다.

5.8. 다음 CPU 버스트를 예측하기 위해 사용된 지수 평균 공식을 고려하자. 매개변수들을 다음과 같이 지정하면 어떤 의미를 나타내는가?

a. 알파 = 0, T0 = 100밀리초

-> 다음 버스트는 100밀리초가 될 것이다. T1 = T0 = 100밀리초 이므로, 최근의 CPU버스트는 영향을 미치지 않는다.

b. 알파 = 0.99, T0 = 10밀리초

-> 다음 버스트는 현재 버스트와 비슷한 값이 될 것이다. 과거의 버스트 추이는 별로 영향을 끼치지 않는다.

5.9. 기아 현상을 일으킬 수 있는 알고리즘은?

a. 선입 선처리

b. 최소 작업 우선

c. 라운드 로빈

d. 우선순위

-> d. 우선순위 알고리즘이다. 낮은 우선순위의 프로세스들이 CPU를 무기한 대기하는 기아 현상이 일어날 수 있다.

5.11. Windows XP 스케쥴링 알고리즘을 사용한다고 할 때, 다음 시나리오에서 스레드의 우선순위 값은?

a. REALTIME_PRIORITY_CLASS 에 속하고, 상대적인 우선순위가 HIGHEST 인 스레드 -> 26

b. NORMAL_PRIORITY_CLASS 에 속하고, 상대적인 우선순위가 NORMAL 인 스레드 -> 8

c. HIGH_PRIORITY_CLASS 에 속하고, 상대적인 우선순위가 ABOVE_NORMAL 인 스레드 -> 14

5.12. 준비완료 큐의 항목이 프로세스 제어 블록에 대한 포인터인 라운드 로빈 스케쥴링의 변형 알고리즘을 고려하자.

a. 준비완료 큐에 동일한 프로세스를 가리키는 두 개의 포인터를 넣는 결과는 무엇인가? 

-> 그만큼 그 프로세스가 CPU를 차지하는 시간이 길어지므로, 더 높은 우선순위를 얻는다고 볼 수 있다. 

b. 이 방식의 주요한 두 개의 장단점은 무엇인가?

-> 더 중요한 프로세스에 많은 시간을 할당함으로써 우선순위를 높일 수 있다. 반면, 그만큼 덜 중요한 작업은 뒤로 밀려난다.

c. 포인터를 복제하지 않고도 동일한 효과를 달성하려면 기본 라운드 로빈 알고리즘을 어떻게 변경해야 하는가?

-> 더 높은 우선순위를 가진 프로세스에게 더 많은 시간을 할당한다. 다시 말하면, 라운드 로빈 알고리즘 상에서 두개 혹은 더 많은 quantum을 가지도록 한다.

5.13 다음 프로세스들의 집합을 생각해보자. CPU버스트 시간 단위는 밀리초.

프로세스	버스트 시간	우선순위
P1	10	3
P2	1	1
P3	2	3
P4	1	4
P5	5	2

프로세스들은 시간 0 에 P1,P2,P3,P4,P5 순서로 도착한다고 가정한다.

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

->선입 선처리

(P1 = 10)

(P2 = 1)

(P3 = 2)

(P4= 1)

(P5 = 5)

0                                                                                               10                  11                                      13                      14                                       19

->SJF

(P2 = 1 )

(P4 = 1 )

( P3 = 2)

(P5 = 5)

(P1 = 10)

0           1                 2                            4                                                        9                                                                                                          19

->비선점 우선순위

(P2 = 1 )

(P5 = 5 )

(P1 = 10)

(P3 = 2)

(P4 = 1)

0          1                                                             6                                                                                                       16                              18           19                  

->RR

P1

P2

P3

P4

P5

P1

P3

P5

P1

P5

P1

P5

P1

P5

P1

P1

P1

P1

P1

0         1           2          3          4          5          6          7          8          9        10         11          12         13        14         15         16         17        18        19

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

->FCFS :

P1	P2	P3	P4	P5
10	11	13	14	19

->SJF : 

P1	P2	P3	P4	P5
19	1	4	2	9

->비선점 우선순위 : 

P1	P2	P3	P4	P5
16	1	18	19	6

->RR : 

P1	P2	P3	P4	P5
19	2	7	4	14

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

->FCFS : 12

P1	P2	P3	P4	P5
0	10	11	13	14

->SJF : 4

P1	P2	P3	P4	P5
9	0	2	1	4

->비선점 우선순위 : 10.xx

P1	P2	P3	P4	P5
6	0	16	18	1

->RR : 5.4

P1	P2	P3	P4	P5
9	1	5	3	9

d. a에서 어느 스케쥴이 최소의 평균 대기 시간을 갖는가?

-> SJF

5.15. 다음과 같은 두 스케쥴링 기준들은 어떤 상황에서 서로 충돌하는가.

a. CPU 이용률과 응답시간

-> CPU이용률은 문맥교환이 많이 일어날 때, 오버헤드가 많이 발생하여 줄어든다. CPU이용률을 높이기 위해서 문맥교환을 줄이게 되면, 프로세스의 응답시간이 그만큼 오래 걸리기 때문에 충돌한다.

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

-> 평균 총처리 시간은, 짧은 task를 갖는 프로세스를 먼저 실행할 때, 최소화 된다. 반면, 그렇게 하면 긴 task를 갖는 프로세스들이 계속해서 대기하게 되므로 대기시간이 길어지는 결과를 초래한다.

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

-> CPU이용률은, 문맥교환없이 긴 task를 가진 프로세스를 실행할 수록, 높아진다. 하지만 입출력 장치를 많이 이용하려면, 바로바로 준비된 다음 입출력 프로세스를 실행해야 하므로 문맥교환이 빈번하게 일어나게 되어 결국 CPU이용률은 떨어지는 결과로 이어질 수 있다.

-> 입출력 장치를 많이 이용하면 할수록 빈번한 문맥교환이 일어나므로 CPU 이용률은 줄어들 수 있다.

5.16 동적으로 변화하는 우선순위에 기반을 둔 다음의 선점형 우선순위 스케쥴링 알고리즘에 대해 생각해보자. 우선순위 값이 클수록 높은 우선순위를 의미한다. 프로세스가 CPU를 기다리는 중일 때(준비완료 큐에 있으나, 실행되지는 않는) 그 프로세스들의 우선순위는 알파 비율로 변화한다. 프로세스가 실행되면 베타의 비율로 변한다. 준비완료 큐에 들어올 때 모든 프로세스들의 위선순위는 0 으로 주어진다. 매개변수 알파와 베타의 값에 따라 여러 가지 다른 스케쥴링 알고리즘이 만들어진다.

a. 베타 > 알파 > 0 이면, 무슨 알고리즘? -> FCFS

b. 알파 < 베타 < 0 이면, 무슨 알고리즘? -> LIFO

**그냥 공부한 내용 정리하려고 쓴 거라서 정답인지 아닌지 모릅니당**