Tutorial Week 12

Questions and Answers

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)

Here is the order of request servicing
FIFO: 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130
SSTF: 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774
SCAN: 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86
C-SCAN: 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130
Total distance travel by the head is left up to the reader to calculate.

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?

Time for a rotation is 4ms; average rotational delay 2ms. Time to read sector 8 us.

• Average access = 5ms + 2ms + 8us
• Average 500 contiguous = 5ms + 2ms + 4ms = 11ms
• 500 scattered sectors = 500 * (5ms + 2ms + 8us) = 2.604 s

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

See lecture slides.

Skew is used to provide enough time for the disk head to seek from the last block in a track to the first block the in the next adjacent track.

Interleaving is used to provide enough time for applications that perform contiguous reads from disk to request the next block after the previous block was supplied.

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

The time to completion of a CPU-bound process is largely determined by the amount of CPU time it receives.

The time to completion of a I/O-bound process is largely determined by the time taken to service its I/O requests. CPU time plays little part in the completion time of I/O-bound processes.

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

Cooperative the thread specifically release the CPU, pre-emptive the thread has no choice.

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?

I/O bound processes typically have many short CPU bursts. If such a process is scheduled, it will typically not use up it's time slice. Priorities are recomputed taking into account the consumed CPU, and hence an I/O-bound process will end up having a higher priority than a process that started at the same priority level and which used more CPU cycles.

Even a process with low priority will be scheduled eventually, since the priority of processes that are continually scheduled eventually also receive a low or lower priority.

Also note that the recorded amount of CPU consumed (that is used to calculate priority) is aged (reduced) over time, and hence CPU-bound processes also increase in priority is they are not scheduled.

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?

Context switch is faster. Better locality. If done too often (always) it starves other tasks.

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

CPU is consumed when switching from one task to another. This switching does not contribute to application progress. If done very frequently (a very short time slice), a significant portion of available CPU will be wasted on scheduler overhead.

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

You will notice that C always misses its deadline with rate monotonic. With earliest deadline all make their deadlines.

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

Take the a file system buffer cache as an example. File system writes are produced by application requests. The OS must select an available entry in the buffer cache (or re-use an existing one), or block until a free slot is available in the bounded-size buffer cache.

The interrupt handler can be considered a consumer as after the write to disk completes, it marks the buffer cache entry as clean (consumed), freeing it up for further writes.

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?

Global queue is simple and provides automatic load balancing, but it can suffer from contention on the global scheduling queue in the presence of many scheduling events or many CPUs or both. Another disadvantage is that all CPUs are treated equally, so it does not take advantage of hot caches present on the CPU the process was last scheduled on. Per-CPU queues provide CPU affinity, avoid contention on the scheduling queue, however they require more complex schemes to implement load balancing.

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?

Spinning makes sense when the average spin time spent spinning is less than the time spent blocking the lock requester, switching to another process, switching back, and unblocking the lock requester.

Page last modified: 4:50pm on Monday, 1st of June, 2009

Print Version