Storage Management
HDD
Address of sector
Track, Head, Sector
HDD Mechanism
Seek time
Disk arm / Head on correct cylinder.
Rotational latency
The disk is spinning.
Disk arm / Head on start of correct sector.
Head (only one) is active for read / write.
Total Time
Total Time = Seek Time + Rotational Latency + Transfer Time
Normally
Seek Time > Rotational Time > Transfer Time
Minimize seek time
Seek time seek distance
Disk Performance Examples
Assume:
Avg Seek Time = 5 ms
7200 RPM Disk
Time for one rotation: 60000 ms / 7200 ~= 8 ms
Transfer Rate = 4 MByte/s
Sector Size = 1 KByte
Read sector from random place on disk:
Seek (5ms) + Rot. Delay (4ms) + Transfer (0.25ms)
Approx 10ms to fetch/put data: 100 KByte/sec
Read sector from random place in same cylinder:
Rot. Delay (4ms) + Transfer (0.25ms)
Approx 5ms to fetch/put data: 200 KByte/sec
Read next sector on same track:
Transfer (0.25ms): 4 MByte/sec
Key to using disk effectively (especially for file systems) is to minimize seek
and rotational delays
Disk Scheduling
Many sources of disk I/O request
OS, System processes and Users processes
I/O request includes
input or output mode
disk address
memory address
number of sectors to transfer
OS maintains queue of requests, per disk or device
Idle disk can immediately work on I/O request, busy disk means
work must queue
Optimization algorithms only make sense when a queue exists
Disk Scheduling (Cont.)
Disk can do only one request at a time
Request denoted by (Track / Cylinder)
2
5
7
3
2
2
User Head
Requests
Several algorithms exist to schedule the servicing of disk I/O
requests
First In First Out (FIFO)
Shortest Seek Time First
SCAN
C-SCAN
We illustrate scheduling algorithms with a request queue (0-199)
98, 183, 37, 122, 14, 124, 65, 67
Head pointer 53
FCFS
total head movement of 640 cylinders
FCFS
Pros:
Fair among requesters
Cons: Order of arrival may be to random spots on the disk.
Very long seeks
SSTF (Shortest Seek Time First)
“Selects the disk I/O request that require minimum head
movement from the current head position”
total head movement of 236 cylinders
SSTF
Pros:
Reduce seeks
Cons:
May cause starvation of some requests
Solution: SSTF with aging
SCAN (Cont.)
total head movement of 208 cylinders
SCAN
“The disk arm starts at one end of the disk, and moves toward the
other end, servicing requests until it gets to the other end of the
disk, where the head movement is reversed and servicing
continues.”
Also called the “Elevator Algorithm”
Pros:
no starvation
low seek
Cons:
favor middle tracks
may spend time on sparse tracks while dense requests
elsewhere
C-SCAN (Cont.)
total head movement of 183 cylinders + Constant Time
C-SCAN
Provides a more uniform wait time than SCAN
The head moves from one end of the disk to the other, servicing
requests as it goes
When it reaches the other end, however, it immediately
returns to the beginning of the disk, without servicing any
requests on the return trip.
Pros:
fair than SCAN
accumulate work in remote region then go get it.
Cons:
longer seeks on the way back.
C-LOOK (Cont.)
total head movement of 153 cylinders + Constant Time
C-LOOK
LOOK a version of SCAN, C-LOOK a version of C-SCAN
“Arm only goes as far as the last request in each direction,
then reverses direction immediately, without first going all
the way to the end of the disk.”