How to use the disk scheduling algorithm simulator
- Enter the cylinder requests in the order they arrive, separated by commas or spaces.
- Enter the cylinder where the head starts and the last cylinder number of the disk.
- Choose which way the first sweep goes, and whether to count the return jump in C-SCAN and C-LOOK.
- Read the total head movement for each algorithm, the one with the least movement, and the order in which each serves the requests.
Formula
FCFS: serve requests in arrival order. Total movement = sum of the distances between successive positions.
SSTF: always serve the request nearest to the head
SCAN: sweep to the end of the disk, then reverse. LOOK: sweep only as far as the last request, then reverse.
C-SCAN and C-LOOK: sweep one way, jump back to the start and sweep the same way again
SCAN and C-SCAN travel to the end of the disk only when requests remain on the other side. Total movement is counted in cylinders.
The textbook queue with the head at 53
The queue is 98, 183, 37, 122, 14, 124, 65, 67 on a disk with cylinders 0 to 199. FCFS moves the head 640 cylinders and SSTF moves it 236. Sweeping toward 0 first, SCAN moves 236, LOOK 208, C-SCAN 386 and C-LOOK 326, so LOOK has the least movement.
Sweeping toward the end first, SCAN moves 331, LOOK 299, C-SCAN 382 and C-LOOK 322. If the return jump is not counted, C-SCAN falls to 183 and C-LOOK to 153. Textbooks differ on whether to count that jump, and the checkbox lets you match yours.
Why the order matters
On a spinning disk, moving the head between cylinders is the slowest part of reading, so the order of service has a big effect on throughput. FCFS is fair but wanders back and forth. SSTF cuts movement but can starve distant requests. The sweeping methods trade a little efficiency for a bounded wait, because every request is reached within one or two sweeps.
These ideas apply to scheduling of other resources too. See the CPU scheduling simulator and the cache replacement policy simulator.
What the model leaves out
The totals count only head movement. They ignore rotation delay, transfer time, requests that arrive while the head is moving and the fact that solid state drives have no head at all. Use the results to compare algorithms on a given queue, as in a course exercise, and not to predict the speed of a real drive.
To count the operations in a sorting algorithm, there is the sorting algorithm operation counter.
Assumptions and limits
- All requests are waiting when the head starts, and no new requests arrive.
- Requests are whole cylinder numbers from 0 to the last cylinder.
- Movement is the distance in cylinders. Seek time is assumed to grow with distance.
- SCAN and C-SCAN go to the end of the disk only when requests remain on the other side.
Frequently asked questions
What is SCAN disk scheduling?
The head moves in one direction serving requests until it reaches the end of the disk, then reverses and serves the rest. It is also called the elevator algorithm.
What is the difference between SCAN and LOOK?
SCAN goes all the way to the end of the disk before it reverses. LOOK turns around at the last request in that direction.
Why does SSTF risk starvation?
A steady stream of requests near the head can keep far requests waiting indefinitely.
Should the return jump count?
Some books count it and some do not. The page lets you choose, and shows the difference.