CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: FCFS total (20 minutes)

The head is at cylinder 60 and the queue is 20, 150, 45, 100, 10, 180. Find the FCFS total movement.

Done when: 590 cylinders (40 + 130 + 105 + 55 + 90 + 170).

Hint

add the absolute differences, one leg at a time, starting at 60.

Easy 2: SSTF order (20 minutes)

Use the same queue and head. Give the SSTF order and the total.

Done when: the order 45, 20, 10, 100, 150, 180 and a total of 220.

Hint

from 60 the nearest is 45. Then 20, 10, 100, 150, 180.

Easy 3: Name it (20 minutes)

A scheduler sweeps in one direction only and returns to the start without serving. Name it, and say how it differs from SCAN.

Done when: C-SCAN, and one sentence: SCAN serves in both directions, C-SCAN in one.

Hint

the word "circular" is the clue.

Medium

Medium 1: LOOK down first (45 minutes)

The head is at 100, the queue is 40, 120, 15, 170, and the arm moves down first. Find the LOOK total, and the FCFS and SSTF totals.

Done when: LOOK 240 (85 down, 155 up), FCFS 400, SSTF 225 with the order 120, 170, 40, 15.

Hint

moving down first, LOOK goes to the lowest request, then up to the highest.

Medium 2: All six on one queue (45 minutes)

Use the queue of Easy 1 with the head at 60 on a disk of 200 cylinders. Give SCAN up first, LOOK up first, C-SCAN and C-LOOK.

Done when: SCAN 328, LOOK 290, C-SCAN 383 (with the return counted) and C-LOOK 325.

Hint

SCAN up goes to 199 and back to the lowest request. C-SCAN counts 199 for the return.

Medium 3: Run the simulator (45 minutes)

Compile the program of section 2, change the queue to that of Easy 1 and the head to 60, and confirm the totals. Then add a ninth request at 130 and report which totals changed by how much.

Done when: the six totals of Easy 1, Easy 2 and Medium 2 appear, plus the new totals with the changes listed.

Hint

add 130 to the array and set N to 7 (or 9 for the original queue plus one).

Hard

Hard 1: Show the starvation (90 minutes)

Write a simulation of SSTF in which, after each served request, one new request arrives at a cylinder that is within 3 of the head. Start with a request at 190 and the head at 100. Run 1,000 steps and report the wait of the request at 190. Run the same arrivals under LOOK.

Done when: under SSTF the request at 190 is still waiting after 1,000 steps, and under LOOK it is served within one sweep.

Hint

keep an array of waiting requests. In SSTF, choose the nearest. Count steps until 190 is chosen.

Hard 2: Cost model (90 minutes)

Replace the model of 0.05 ms per cylinder with a square-root model, in which a move of d cylinders takes 1 ms plus 0.3 ms times the square root of d. Recompute the six totals of section 4 and the order of the algorithms.

Done when: a table of six times, and a sentence that says whether the order of the algorithms changed and why a fixed start-up cost favours fewer, longer moves.

Hint

apply the cost to each single move, not to the total.

Hard 3: Choose for a workload (90 minutes)

A database server has a hard disk with 20 threads that all issue random reads, and a second server has an NVMe flash disk with the same workload. For each, choose a scheduler from none, mq-deadline, kyber and bfq, and justify it with the rules of this page. Then read the real setting on your own machine and say if it fits.

Done when: two choices with reasons that name seek cost for the disk and per-request overhead for flash, and the output of your own scheduler file.

Hint

think of how much a seek costs on each device and how much work the scheduler itself adds.