Chapter05. CPU 스케줄링 : 문제풀이

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

각 프로그램에 맞는 CPU 버스트의 분포가 다르기 때문에, 각각의 CPU 버스트를 파악해야 적절한 CPU 스케줄링 알고리즘을 선택할 수 있다.

(입출력 중심 프로그램은 짧은 CPU 버스트를 많이 가지고 CPU 중심 프로그램은 다수의 긴 CPU 버스트를 가질 수 있다.)

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

1. CPU 이용률과 응답 시간
2. 평균 총처리 시간과 최대 대기 시간
3. 입출력 장치 이용률과 CPU 이용률
   

cf) 스케줄링 기준 :   CPU 이용률 - 40% ~ 90%

     처리량 - 단위 시간당 완료된 프로세스의 갯수

     총처리 시간 - 프로세스의 제출시간과 완료시간의 차

     대기 시간 - 프로세스가 큐에서 대기하며 보낸 시간의 합 (스케줄링 알고리즘에 의해 결정됨)

     응답 시간 - 응답이 시작되는 데까지 걸리는 시간

a : 문맥교환이 자주 일어나면 오버헤드가 발생해 CPU이용률이 그만큼 줄어든다. 문맥교환 오버헤드를 줄이려면 문맥교환의 빈도수를 줄이면 되는데, 이는 응답시간의 저하로 이어질 수 있다.

b :  짧은 프로세스를 먼저 실행하면 평균 총처리 시간이 줄어든다. 하지만 그만큼 긴 프로세스의 기아현상이 발생할 수 있어 최대 대기시간은 늘어난다.

c : CPU이용률은 문맥교환 없이 한 프로세스가 계속 실행될 때 높아지지만, 입출력 장치 이용률은 입출력 장치가 준비되었을 떄 바로 실행되어야 늘어난다. 따라서 입출력 장치 이용률이 늘어나면 문맥교환이 잦아지고 이는 CPU이용률의 저하로 이어진다.

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

1. α = 0 ,  τ。= 100밀리초
   
2. α = 0.99 ,  τ。= 10밀리초

a : α = 0 이므로 최근의 조건들은 다음 CPU 버스트에 영향을 주지 않는다. CPU 버스트들의 길이가 100밀리초로 일정하게 된다.

b : α가 1에 가까우므로 다음 CPU 버스트는 최근의 CPU 버스트에 가장 크게 영향을 받는다. 과거에 대한 기억을 거의 하지 않고, 다음 CPU버스트를 예측하기 위해 바로 전 버스트의 길이를 예측한다.

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

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

a :

FCFS

P1	P2	P3	P4	P5
2	3	11	15	20

SJF

P2	P1	P4	P5	P3
1	3	7	12	20

비선점 우선순위

P3	P5	P1	P4	P2
8	13	15	19	20

RR

P1	P2	P3	P4	P5	P3	P4	P5	P3	P5	P3
2	3	5	7	9	11	13	15	17	18	20

    

b : 각 프로세스에 대한 총처리 시간

	P1	P2	P3	P4	P5	합계
FCFS	2	3	11	15	20	51
SJF	3	1	20	7	12	43
비선점우선순위	15	20	8	19	13	75
RR	2	3	20	13	18	56

c : 각 프로세스에 대한 대기 시간

	P1	P2	P3	P4	P5	합계
FCFS	0	2	3	11	15	31
SJF	1	0	12	3	7	23
비선점우선순위	13	19	0	15	8	55
RR	0	2	12	9	13	36

d : SJF 방식이 최소의 평균 대기시간을 보인다.

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

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

D 우선순위 알고리즘.

기아현상을 해결하기 위해 노화(Aging) 기법을 사용할 수 있다.

5.11 준비완료 큐의 항목이 PCB를 가리키는 포인터인 RR 스케줄링 알고리즘의 변형을 고려하자.

1. 준비 완료 큐의 두 항목이 같은 프로세스를 가리키게 만드는 것은 어떤 효과와 같은가?
2. 이러한 구조를 가지는 스케줄러의 두 가지 장점과 두 가지 단점은 무엇인가?
3. 포인터 복제 없이 동일한 효과를 구현하려면 기본 RR알고리즘을 어떻게 수정할 수 있는가?

a : 그 프로세스는 더 자주 시간을 할당받게 됨으로써 우선순위가 높아진다.

b : 더 중요한 프로세스에 많은 시간을 할당함으로써 우선순위를 높일 수 있다. 하지만 그만큼 덜 중요한 작업은 밀려날 수 있다.

c : 더 높은 우선순위를 가진 프로세스에 더 긴 시간을 할당한다. RR 스케줄에서 2개 이상의 항목을 가지게 한다.

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

1. 시간 할당량 1밀리초
2. 시간 할당량 10밀리초

5.13 다단계 큐 스케줄링을 구현한 시스템을 고려하자. 자신의 프로세스에게 할당된 CPU시간이 최대가 되게 하기 위해서 사용자는 어떤 전략을 세울 수 있는가?

5.14

1. β > α > 0 이면 무슨 알고리즘인가?
   
2. α < β < 0 이면 무슨 알고리즘인가?

a : FCFS

b :

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

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

a : 전혀 우대하지 않는다.

b : 프로세스가 도착한 순서대로 스케줄되지만 짧은 프로세스는 다른 프로세스보다 먼저 끝날 수 있다.

c : 짧은 프로세스에게 최고의 우선순위를 부여한다.

5.16 Windows 스케줄링 알고리즘을 사용할 때, 다음 각 스레드의 우선순위 값은?

a

b

c

5.18 시분할 스레드를 위한 Solaris 운영체제의 스케줄링 알고리즘을 고려하자.

1. 우선순위 15의 스레드의 시간 할당량은 밀리초 단위로 얼마인가? 40의 스레드는?
2. 우선순위 50의 스레드가 봉쇄없이 시간 할당량을 소진했다고 가정하자. 스케줄러는 이 스레드에게 어떤 우선순위를 배정하겠는가?
3. 우선순위 20의 스레드가 시간 할당량이 만료되기 전에 입출력 때문에 봉쇄되었다고 가정하자. 스케줄러는 이 스레드에게 어떤 우선순위를 배정하겠는가?