Week 7 – CST– 334 Operating System

Module 7- Persistence

This week we covered persistence. We first learned about I/O devices and how the operating system interacts with these devices. In a typical system, the CPU is attached to the main memory via a memory bus. Devices like the PCI or graphics card are then connected to the system via a general I/O bus. Lastly, the peripheral buses like SCSI, SATA, or USB connect slow devices to the system like disks, mice, and keyboards. Modern systems have an I/O chip that connects directly to the CPU and to the peripherals devices. The DMA or Direct Memory Access engine can transfer data back and forth between devices without CPU intervention. Device drivers are software that the OS uses to know how a device works. An interesting fact is that the Linux kernel OS has 70% of its code in device drivers.

We also studied Hard Disk Drives. These drives have been the main form of persistent data storage for many years and the file system is based on their behavior. The drive is made up of sectors numbered from 0 to n-1 on a disk with n sectors. This also happens to dictate the address space of the drive which is 0 to n-1. A disk drive is made up of platter bound by a spindle. The sectors are on the surface of the platter in concentric circles called tracks. A disk head is attached to a disk arm. The disk head is used for reading and writing. Disk scheduling is implemented to optimize the time the process of reading or writing to disk. Some of the scheduling algorithms include Shortest Job First, Shortest Seek Time First, or Nearest Block First. Another algorithm that can be implemented to avoid starvation is the Elevator or SCAN. This technique moves back and forth across the tracks servicing requests. A variant to the SCAN is the Circular SCAN which only scans from outer to inner and resets to the outer track.

Next, we covered Redundant Arrays of Inexpensive Disks or RAIDs. These are techniques that use multiple disks in concert to build faster, bigger, and more reliable disk systems. We learned about four different RAID levels.

RAID Level 0: Striping. Striping simply arranges the blocks across disks for example block 0 will be allocated in Disk 0, block 1 in Disk 1, block 2 in Disk 2 and so on. This design allows for the most parallelism for requests that are made for contiguous chunks.

RAID Level 1: Mirroring. This level makes a copy of each block in the system and places it on a different disk. This design allows for at least 1 disk failure and potentially 2 disks can fail depending on which two disks fail. This level also is expensive capacity wise because it can only use half of its peak capacity.

RAID Level 4: Parity. This level uses XOR to compute parity which is stored on one of the disks. These parity blocks contain redundant information about the blocks on their stripe. The parity block stores a 0 if the number of 1s in that row are even and 1 if the number of 1s in that row are odd. This allows the parity block to reconstruct the value of any given disk that fails. If the remaining 1s are even but the parity block is odd, then the disk that failed must be a 1 to make the parity block odd. This level creates a bottle neck when accessing the blocks because the parity disk prevents parallelism.

RAID Level 5: Rotating Parity. This level is similar to level 4 but the parity blocks are rotated across the disks to remove the parity-disk bottle neck. This method prevents the bottle neck from level 4 because it allows for utilization of all disks.