Tutorial Week 13


Q1: Consider the multilevel feedback queue scheduling algorithm used in traditional Unix systems. It is designed to favour IO bound over CPU bound processes. How is this achieved? How does it make sure that low priority, CPU bound background jobs do not suffer starvation?

Note: Unix uses low values to denote high priority and vice versa, 'high' and 'low' in the above text does not refer to the Unix priority value.

Q2: Why would a hypothetical OS always schedule a thread in the same address space over a thread in a different address space? Is this a good idea?

Q3: What is the problem that fair-share scheduling is tries to solve?

Q4: Why would a round robin scheduler NOT use a very short time slice to provide good responsive application behaviour?

Q5: What are the advantages and disadvantages of using a global scheduling queue over per-CPU queues? Under which circumstances would you use the one or the other? What features of a system would influence this decision?

Q6: When does spinning on a lock (busy waiting, as opposed to blocking on the lock, and being woken up when it's free) make sense in a multiprocessor environment?

Q7: Consider 3 periodic tasks with execution profiles shown below. Draw scheduling diagram for a rate monotonic and a earliest deadline first schedule.

Process Arrival Time Execution Time Deadline
A (1) 0 10 20
A (2) 20 10 40
. . .
B (1) 0 10 50
B (2) 50 10 100
. . .
C (1) 0 15 50
C (2) 50 15 100

Q8: Consider the following set of processes at t = 0. Note: newly released processes are placed at the end of the ready queue

ProcessExecution TimeArrival Time
A 10 2
B 4 3
C 2 4

What is the finish time, response time and turnaround time for each of FCFS, SJF, Round robin (1 second time slices)? What are the average response and turnaround times for each of these algorithms?