Disk Scheduling and External Sorting
Hard Drive: consists of number of disks, aligned with each other, sit on spindle
Disk head array - series of heads which sit on top of the disks
Disk head reads from one side of one disk at a time
Raid: composed of multiple disk drives, can be read in parallel, depending on RAID type
Data in blocks - possible example, 2048 bytes
To read this block, must move disk head to appropriate track
Seek Time: in region of 2 to 20 milliseconds - time to move to track you want to read
Disk is rotating. Really fast, ~100rps
To read data from hard drive:
1. Move disk head to correct track (concentric circles on the disk)
2. Wait for the block that you're trying to read to rotate to the disk head (called rotational latency or
delay [but latency sounds cooler] - 4-11 milliseconds)
3. Transfer data as it passes underneath disk head (0.1ms)
Reading 1 block from a disk: order of 10ms
Suggests that how you organize things on the disk is very important!
Can also call blocks pages, pages are abstractions of blocks, can refer to pages on disk and pages in
main memory - same size.
Reading one page in RAM is in region of 50ns
ms = 10^-3s
ns = 10^-9s
Accessing a page in a disk is about 200,000 times slower than accessing page in RAM!
Suggests: we would like to minimize the number of times we access hard drives.
Also want to minimize as much as possible seek time and rotational latency
If want to write algorithm that accesses blocks on a disk, using a simple queue for a disk access
algorithm is a bad idea.
Algorithms for DiskAccess:
Fair algorithms are usually bad (ex using a queue)
Elevator algorithm is commonly used for disk access - algorithm that is used by -pause for dramatic
Stops at closest first, regardless of order of buttons pushed. Does not deal with requests in order they
are made. Use this to schedule disk requests. External Sorting:
Problem: we want to sort a large file currently residing on a disk and the file is too large to fit in main
Most concerned with reducing the number of times that the disk is accessed. (read or written)
Not as concerned with the number of main memory operations
This cost is different than what we were looking at before
Goal:An algorithm that