Due: Feb. 11

** Answer: ** If an interrupt occurs, it is frequently the
case that some other process Q unblocks. Therefore, the scheduler
might want to consider running Q in preference to P (which was not
an option before the interrupt.) By contrast, no change in process
state occurs at a non-blocking system call; hence, it is unlikely
that there would now be a reason to prefer a new process (though
not impossible, depending on the scheduling strategy and the
state of the system.)

** Answer: **
Only dynamic fields, which change over the execution of P,
such as registers, need to be stored at a block. Static fields,
such as user id or parent process, are set when P is created
and need not be changed thereafter.

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?

** Answer: **

** Shortest Job First (non-preemptive) **

Time Running Decision at end 0-10 A between B=3, C=8, D=6, E=1 10-11 E between B=3, C=8, D=6. 11-14 B between C=8, D=6 14-20 D between C=8, F=4 20-24 F between C=8 24-32 C

Turnaround times: A-10; B-12; C-28; D-13; E-1; F-7. Average: 71/6=11.8333

** Shortest remaining time first (preemptive) **

Time Running Decision at end 0-2 A between A=8 (remaining) and B=3 2-4 B between A=8, B=1, C=8 4-5 B between A=8, C=8. Choice is arbitrary. 5-7 A between A=6, C=8, D=6. Choice between A and D is arbitrary 7-10 A between A=3, C=8, D=6, E=1. 10-11 E between A=3, C=8, D=6. 11-14 A between C=8, D=6. 14-17 D between C=8, D=3, F=4. 17-20 D between C=8, F=4. 20-24 F between C=8. 24-32 C

Turnaround times: A-14; B-3; C-28; D-13; E-1; F-7. Average 66/6 = 11.0

** Round robin **

Time Running Time used per proc. Time remaining 0-2 A 2/1=2 A-8 2-4 A,B 2/2=1 A-7; B-2 4-7 A,B,C 3/3=1 A-6; B-1; C-7 7-10 A,B,C,D 3/4=0.75 A=5.25; B=0.25; C=6.25; D=5.25 10-11.25 A,B,C,D,E 1.25/5=0.25 A=5; B=0; C=6; D=5, E=0.75. 11.25-14.25 A,C,D,E 3/4=0.75 A=4.25; C=5.25; D=4.25; E=0 14.25-17 A,C,D 2.75/3=0.916 A=3.33; C=4.33; D=3.33; F=4 17-30.33 A,C,D,F 13.33/4=3.33 A=0; C=1; D=0; F=0.67 30.33-31.67 C,F 1.33/2=0.67 C=0.33 31.67-32 C 0.33/1=0.33

Turnaround times: A-30.33; B-9.25; C-28; D-23.33; E-4.25; F-14.67. Average: 109.83/6 = 18.305.