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?

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.)

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.

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.

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?

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.