5강. 연습문제

5.1 Discuss how the following pairs of scheduling criteria conflict in certain settings.

a. CPU Utilization and response time

CPU Utilization을 높히기 위해서는 Overhead가 가장 적게 발생하도록 Context Switching이 최소화가 되고, 그렇게 되면 Response time이 최대화가 된다.

b. Average turnaround time and maximum waiting time

Turnaround time을 최소화 하기 위해서는 SJF 방식을 사용해야 한다. 그렇게 되면 처리기간이 긴 task는 starve하게 되고 이들의 waiting time이 길어진다.

c. I/O device Utilization and CPU Utilization

CPU Utilization은 Context Switching없이 CPU-bounds task만 처리할 때 Maximize된다. I/O Utilization은 I/O Bound task를 빠르게 처리해야 Maximize 되므로 I/O Bounds task를 처리하려면 Context Switching이 발생하여 CPU Utilization이 낮아진다.

5.2 Consider the following set of processes, with the length of the cpu burst given in milliseconds.

 

The Process are assumed to have arrived in the order P1, P2, P3, P4, P5 all at time 0

a. Draw four Gantt Charts that illustrate the execution of these process using the following scheduling algorithms : FCFS, SJF, non preemptive priority ( a smaller priority number implies a higher priority), and RR(quantum = 1)

b. What is the turnaround time of each process for each of the scheduling algoritms in part a?

turnaround time = process가 끝날 때 까지 걸리는 시간

c. What is the waiting time of each process for each of the scheduling algoritm in part a?

waiting time = process가 ready queue에서 기다리는 시간

d. which of the algorithm in part a results in the minimum average waiting time(over all process)?

5.3 Why is it important for the scheduler to distinguish I/O-Bound programs from CPU-Bound programs?

I/O Bounds Program은 CPU사용량이 적다.

CPU Bounds Program은 CPU사용량이 많아 Block이 없다면 CPU를 많이 계속 사용한다.

I/O Bounds Program에 우선순위를 주어 I/O Bounds Program을 CPU가 우선적으로 처리하면 CPU를 더욱 효율적으로 사용할 수 있기 때문에 Scheduler는 두 프로그램을 구분해야한다.

5.4 Which of the following scheduling algorithms could result in starvation?

a. First-Come, First-Served

b. Shortest Job First

c. Round Robin

d. Priority

b, d → Priority에 기반한 알고리즘은 Starvation의 가능성이 있다.

5.5 Consider a system running ten I/O-Bound tasks and one CPU-Bound task. Assume that the I/O-Bound tasks on I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the Context-Switching overhead is 0.1 millisecond and that all process are long-running tasks. which is the CPU Utilization for a Round-Robin scheduler when:

a. The time quantum is 1 millisecond.

1초마다 0.1초의 Overhead가 발생하여 1.1초 동안 1초의 CPU연산이 실행된다.

⇒ (1 / 1.1) * 100 = 91%

b. The time quantum is 10 milliseconds.

(대충 그린 그림.)

I/O작업 10번 ⇒ 10.1초동안 10초의 CPU연산이 실행된다.

⇒ (10 / 10.1)

1초동안 CPU Bound 작업 처리, 1초마다 I/O 작업 발생으로 Context Switching 발생 ⇒ 1.1 * 10초 동안 10초의 CPU 연산 실행 ⇒ (10 / 11)

(10 + 10 / 10.1 + 11) = 20 / 21.1 = 94%

5.6 Consider a system implementing multilevel queue scheduling. what strategy can a computer user employ to maximize the amount of CPU time allocated to the user's process?

할당받은 Time Quantum 값을 전부 사용하지 않는 방식을 통해서 CPU사용을 최대화할 수 있다. 할당받은 Time Quantum의 많은 부분을 사용한 뒤 Quantum이 끝나기 전 CPU를 포기하여 Process의 Priority를 증가시킬 수 있다.

5.7 Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short process:

a. FCFS

Short Process가 Long Process뒤에 오면 Waiting time이 늘어난다. ⇒ Short Process에는 불리하게 차별한다.

b. RR

Process들을 차별하지 않는다. 모든 task를 돌아가면서 수행하여 Short Process는 빨리 처리되어 나간다.

c. Multi level feedback queues

RR과 비슷한 방식으로 동작한다. Short Process에게 유리하게 동작하여 Short Process에 유리하게 차별한다.