Disk Introduction

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.

disk-structure

The Evaluation Criteria

Here we are introducing the basic components used to evaluate the performance of disk operation.

Seek Time

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 Switch 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.

Rotation Delay

This is the time spend for the sector to spin underneath the head. It varies depends on how fast the disk rotates.

Transfer Time

The time spend to read or write sector as it spins by.

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.)

FIFO

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/written 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.

SCAN/Elevator/LOOK

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.

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.)

Partitioning

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 Techniques to Reduce Overhead

To minimize rotational latency and seek time, we can also:

SSD

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

structure-of-flash-die

The fundamental 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.

Operations