Homework 2

Assigned: Feb. 4
Due: Feb. 11

Problem 1

When a process P makes a non-blocking system call, we assume that control will return to P after the call is complete. When P is interrupted by an interrupt, we assume that the scheduler may decide to run someone else instead, even though usually P will not be blocked. Why the difference?

Problem 2

Not all fields in the process table entry for process P need to be stored when P blocks. Give an example, and explain why not.

Problem 3

Suppose that the following processes enter the system at the specified times with the specified required total CPU times:
Process  Starting Time   Run Time
A           0              10
B           2               3
C           4               8
D           7               6
E          10               1
F          17               4

Trace the progress of these tasks, assuming that the scheduler uses (a) shortest job first (non-preemptive); (b) shortest remaining time next (preemptive); (c) round robin (premptive). Ignore the overhead of context switching. In the case of round robin, also ignore the discreteness of the time quantum; rather assume that all the jobs progress in parallel, at a speed inversely proportional to the number of active jobs. For example, if jobs P and Q are active, and at time 4 P had 4 seconds left to run and Q has 3 seconds, then at time 5, P will have 3.5 seconds left to run and Q will have 2.5 seconds.

Also, what is the average turnaround time for these three scheduling algorithms?