Assume that each process must go through exactly three CPU burst cycles before it is done and terminates, and that each CPU burst is of exactly the same length (as shown above). Assume also, that following each of its first two CPU bursts, each process must perform an I/O operation, and that each of those I/O operations takes 5 time units to complete. Processes will be added back to the ready queue when their I/O operations complete. E.g., if only process 1 existed, it would be scheduled as:

11xxxxx11xxxxx11 <- x means CPU idle (process 1 waiting for I/O)

12345678901234567890

1 2

To help figure out what decision is to be made at each decision point, you may want to do something like the following (e.g., start of FCFS):

1 2 3 4

queue 1234567890123456789012345678901234567890

[1234] 11wwwww

[234] 2wwwww

[34] 3333wwwww

[41] 444wwwww

...

1123333444...

12345678901234567890

1 2

13. For the FCFS scheduling algorithm, draw the Gantt chart that illustrates the execution of these processes (until all have completed their three CPU bursts). Assume processes initially arrive in order 1, 2, etc., but they will then be added back to the ready queue when their I/O operations complete.

14. For the SJF scheduling algorithm, draw the Gantt chart that illustrates the execution of these processes (until all have completed their three CPU bursts). Assume the scheduler has accurate burst time estimates for the processes.

15. For the nonpreemptive priority scheduling algorithm, draw the Gantt chart that illustrates the execution of these processes (until all have completed their three CPU bursts). Assume larger priority number means higher piority.

16. For the preemptive priority scheduling algorithm, draw the Gantt chart that illustrates the execution of these processes (until all have completed their three CPU bursts). Assume larger priority number means higher piority. Being preemptive means that if a higher priority task is added to the ready queue and a lower priority process is executing, the lower priority task will be preempted (removed from the CPU and returned to the ready queue).

17. The Linux CFS scheduling algorithm basically keeps track of total CPU time that each process has used, and schedules the process with the least total runtime next (with limited preemption). The exact algorithm is a bit complex, however, since what is actually used for making scheduling decisions is virtual runtime, which is actual runtime adjusted to take into account priorities and the time processes spend waiting for I/O.

Since the true algorithm is too complex to reasonably carry out by hand, here is a simplified version of CFS you should use to select the process to run at each time unit:

(ri is the accumulated runtime for process pi)

running process pi wants to continue:

if process pj just added to ready queue, and rj < ri , switch to running pj

else if pi has just run 2 time units and there exists a process pk in ready queue with rk < ri , switch to running pk (break ties by priority)

else leave pi running

there is no continuing process:

select lowest runtime process in ready queue to run next (break ties by priority)

Using the simplified Linux CFS scheduling algorithm above, draw the Gantt chart that illustrates the execution of the given four processes (until all have completed their three CPU bursts, just as was done with problems 1316).

Note: assume all four processes arrive at same time (prior to time 1) so get ordered in queue initially (none run yet) based on priority.

18. Compute and compare the turnaround time for the processes going through three CPU bursts (problems 1317). Which scheduling algorithm turned out best here? Justify your answer.

19. Compute and compare the wait time for the processes going through three CPU bursts (problems 1317). Which scheduling algorithm turned out best here? Justify your answer.

20. Consider the other scheduling criteria from Section 6.2 of the textbook. Are there any besides the above two, where the different scheduling algorithms (in problems 1317) perform quite differently? Justify your answer.