Tutorial Week 12

Questions

Disk scheduling and CPU scheduling

Q1: Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 125. The queue of pending requests, in FIFO order, is
86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130.
Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk-scheduling algorithms?

  1. FIFO
  2. SSTF
  3. SCAN (Elevator)
  4. C-SCAN (Modified ELevator)

Q2: A disk has an average seek time of 5ms, a rotational speed of 15,000 rpm, and 500 sectors per track. What is the average access time to read a single sector? What is the expected time to read 500 contiguous sectors on the same track? What is the expected time to read 500 sectors scattered over the disk?

Q3: What is disk skew and interleaving? Why would a file system (or disk controller firmware) use these techniques?

Q4: What do the terms I/O bound and CPU bound mean when used to describe a process (or thread)?

Q5: What is the difference between cooperative and pre-emptive multitasking?

Q6: 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.

Q7: 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?

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

Q9: 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

Q10: Describe how I/O buffering can be formulated as a bounded-buffer producer-consumer problem.

Multiprocessor scheduling

Q1: 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?

Q2: 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?