Disk Management

1. Hard Disks

Hard disks use magnetic media to store disks. The physical hardware addresses are composed of the the cylinder, surface and sector address. Modern disks use logical sector addressing where sectors are numbered to . This makes disk management much easier, and helps work around BIOS limitations.

1.1 HDD Formatting

Before a drive can be used, it must be formatted. A low level format contains:

• Disk sector layout: A split between the preamable, data and error correction code (ECC).
• Accounting for cylinder skew (this is the time it takes for the disk to rotate to the next cylinder).
• Support for interleave (this is the time it takes for the disk to rotate to the next sector).

A high level format contains:

• The boot block.
• A list of free blocks.
• The root directory.
• An empty file system.

1.2 HDD Delays

There are many different delays affecting a HDD:

• Seek time - the time it takes to move the disk head to the correct cylinder. Can vary from -ms.
• Rotation time - the time it takes for the disk to rotate to the correct sector. Is ms.
• Transfer time - the time it takes to read / write data. Is ms.

We can calculate these with the following equations:

• is the seek time.
• is the number of bytes to transfer.
• is the number of bytes per track.
• is the rotation speed in revolutions per second.
• is the time to rotate to the correct sector.
• is the time to transfer the data.
• is the total access time.

1.3 HDD Scheduling

Disk scheduling wants to minimize the seek / latency times, by ordering pending disk requests with respect to head position. There are many different algorithms to do this:

• First Come First Serve (FCFS) - No ordering of requests: random seek patterns. This is fine for light loads, but has poor performance during heavy loads. This is a fair algorithm.
• SCAN Scheduling - choose requests which result in shortest seek time in a preferred direction. Only change direction when reaching the innermost / outermost cylinder. This is the most common scheduling algorithm, but can result in long delays for extreme locations. Sometimes called elevator scheduling.

2. Solid State Drives

SSDs are made up of dies, which are made up of blocks, which are made up of pages. The page size is the smallest unit of data that can be read / written. The block size is the smallest unit of data that can be erased. An SSD has no moving parts and is much faster than a HDD. It has more bandwidth, and smaller latencies. However, it is more expensive and has a limited number of writes. Despite this, SSD is getting cheaper, and is projected to overtake HDDs in the future.

3. RAID

RAID stands for Redudant Array of Inexpensive Disks. CPU performance increases much faster over time compared to disk performance. RAID is a way to increase disk performance by using multiple disks.

• We use an array of physical drives appearing as a single virtual drive.
• We store data distributed over an array of physical disks to allow parallel operation (called striping).
• We use redundant disk capacity to respond to disk failure. The more disks there are, the lower the mean time to failure (MTTF).

A RAID Controller is the hardware that manages the RAID array. It can be a separate card, or integrated into the motherboard. It can be software RAID (managed by the OS) or hardware RAID (managed by a dedicated controller).

3.1 RAID Levels

There are many different RAID levels with different properties relating to performance, redundancy and cost. The most common are:

• RAID 0: Striping - Use multiple disks to increase performance. Disks can seek and transfer concurrently, may also balance load across disks. However, there is no redudancy, which means no fault tolerance.
• RAID 1: Mirroring - We mirror data across disks. Reads can be serviced by either disks (fast), but writes must happen to both disks (slow). Failure recovery is easy, at the cost of a high storage overhead.
• RAID 5: Block Level Distributed XOR - Distributed parity information. Some potential for write concurrency, but good storage efficiency / redundancy tradeoff. Reconstruction of a failed disk can be slow.

RAID levels 2, 3 and 4 are not commonly used since they provide no advantage over RAID 5.

4. Disk Cache

We can use main memory to improve disk access. A buffer is put into main memory for disk sectors. It contains a copy of some sectors from disk, which the OS manages in terms of blocks. Multiple sectors are used for efficiency. Because the buffer has finite space, we need a replacement policy. These include:

• Least Recently Used (LRU) - Replace block that was in cache longest without references. We format the cache as a stack of blocks. Most recently referenced blocks sit on top of the stack. We use pointers instead of moving memory, making a very efficient algorithm. However, it doesn't track block popularity.
• Least Frequently Used (LFU) - Replace block that has experienced the fewest references. A counter is associated with each block, which is incremented on block access. Block with the smallest count used for replacement. However, some blocks maybe accessed many times during a short period, leading to a misleading counter.
• Frequency Based Replacement - Divide the LRU stack into two sections: new and old. We only increment the counter if its not already in new. We replace the block with the lowest count in the old section. However, with this method, blocks age out too quickly.