This chapter is all about disk. Before we start. We won't go deep into the mechanical part of disk operation; rather we will be focusing on general concept related to disk and algorithms to improve disk performance.
The Evaluation Criteria
Here we are introduing the basic components used to evaluate the performance of disk operation.
This is the time to position the head over the track. Maximum can be going from innermost track to outer most track. It usually ranges from 10ms to over 20 ms. However, the average seek time is usually to seek 1/3 of the way across the disk.
Head Swtitch Time
This is time spent to move from one track on one surface to another track on a different surface. The range is similar to seek time.
This is the time spend for the sector to spin underneath the head. It varies depends on how fast the disk rotates.
The time spend to read or write sector as it spins by.
- Transfer time: time to move the bytes from disk to memory
- Surface transfer time: time to transfer one or more sequential sectors to/from surface after head reads/writes first sector
- Host transfer time: time to transfer data between host memory and disk buffer
Disk Head Scheduling (Mainly focusing on HDD)
Now we've looked at the basic performance evaluation critiria for HDD, it's reasonable to discuss how to reduce head movement so that the amount of time spent on moving the head from on track to the other will decrease because the disk I/O request for can be stored in a queue. (Note the seek time takes the most amount of time so it's reasonable to reduce it.)
This technique is easy to understand, the head will move to the corresponding track based the order of the queue of requests. Since the requested data can be read/writen on random tracks, the performance can be heavily affected.
SSTF (Shortest Seek Time first)
The queue of requests is reordered such that the head will only look for the closest track it can move to and thus ignore the global state of locations of all requests. This is a greedy algorithm and thus can be trapped in local optimal value.
Simply move the head to one direction until the request that is closest to that end of the disk is reached, then reverse the direction of the head and find the rest of the requests.
- Optimization: the head is reset when no more requests exist between the current head position and the approaching edge of the disk (LOOK scheduling)
C-SCAN/C-LOOK ("Circular Scan" scheduling)
Move the head in one direction until an edge of the disk is reached and then reset to the opposite edge. optimization: the head is reset when no more requests exist between the current head position and the approaching edge of the disk (called C-LOOK scheduling).
- Note the only difference between SCAN and C-SCAN is that in C-SCAN, after the head reaches one edge, an optimized jump implemented by the hardware is used to directly move the head to the opposite edge instead of reversing the movement direction.)
Disks are partitioned in order to minize the largest seek possible time since each partition is a logically seperate disk. (It's just merely a collection of cylinders.) More information covering partitioning will be covered in file system.
Other Techiniques to Reduce Overhead
To minimize rotational latency and seek time, we can also:
- Make disks smaller (less movement distance)
- Spin disks faster
- Schedule disk operations to minimize head movement(we've just discussed)
- Lay out data on disk so that related data is on nearby tracks(locality and also less movement)
- Place commonly used files on disk
- Block size: (note disk is presented with sector address using logical block address converted by the controller)
- Too small: low transfer rate because we need to perform more seeks for same amount of data.
- Too big: internal fragmentation
The basic advantage of SSD is that it doesn't have moving parts and thus random access is blazingly fast. It's implemented using NAND and is non-volatile.
Basic NAND Flash Units
The fundemental unit is a page which is 4KB. 128 pages are organized together forming a block of size 512KB. Each block is the unit forming a plane. There are 1024 blocks on one plane and the size of the plane is 512MB.
- Read page: fast in terms of nano seconds compared to micro seconds for spinning disk.
- Write page: can only write to empty page, same as above.
- Erace block: (ms) Before a page can be written, all bits in the page need to be set to 1. Note the only way to set bits in a page to 1 is to erase the whole block.
- Read and Write occur in page unit.