Chapter 14 Notes

En homage to Jody and those on the Math field trip (it's raining here in Naperdale today, so I hope you're dry), please enjoy the encapsulation of my Chapter 14 lecture notes, given May 16, 2002.

Overview

Chapter 14 is titled "Mass Storage Structure". Most of the chapter deals with hard disks used as secondary storage in a computer system and their interaction with the operating system. There is also a final section on tertiary storage: backup devices like CD-ROMs, tapes, floppy drives, etc.

As the chapter relates to the operation of disk drives, you can page back to section 2.3 of our text to refresh your memory on these devices. The picture on page 37 of a disk drive is helpful.

Disk Structure

Conceptually the disk is a 1-D array of blocks...

• Each block is typically 512 bytes
• Sector 0 is the 1st sector on the disk, stored on the 1st track of the first (outermost) cylinder

2 fundamental disk types:

1. Constant Linear Velocity (CLV) - where the density of bits/track on the disk is constant across all the cylinders. Given this, outer cylinders on the disk will store more tracks, than the inner cylinders. Therefore, the rotation speed is increased as the head moves toward the center, to maintain a constant rate of data transfer.
2. Constant Angular Velocity (CAV) - where the density of the disk changes, so that the rotation speed is constant to maintain the same rate of data transfer.

Disk Scheduling

Revisit old definitions for disk drives:

• seek time - the time a disk requires to move the arm to the appropriate cylinder
• rotational latency - the time a disk needs to rotate to the appropriate sector

Our scheduling algorithms will consider only seek time. The goal of our disk scheduling algorithms will be to minimize the seek time for a sequence of disk operations.

So, the input data for these scheduling algorithms will be a sequence of disk operations listed by the cylinder number at which the operation must be performed. For example, the sequence:

52, 131, 82

means that a block of data is needed on cylinders 52, 131, and 82. Selecting the order of these accesses will be the job of our disk scheduling algorithms.

Scheduling algorithms:

1. First Come First Serve (FCFS) scheduling - similar to FJFS in CPU scheduling, just schedule the disk access in the order they appear... does not typically give the best results
2. Shortest Seek Time First (SSTF) scheduling - similar to SJF in CPU scheduling, schedule the next "closest" (in terms of cylinder number) to the current position of the disk head... better results, but not optimal
3. SCAN scheduling - the "elevator algorithm", service requests in order until the end of the disk, then reverse direction and mop up... in this case the disk head continuously "scans" from one end of the disk to the other
4. CSCAN scheduling - stands for "circular" SCAN, like SCAN except you don't process disk requests on the way back to the other end, return the disk head to the end (cylinder 0, for example) and then start processing requests... the advantage over SCAN is that SCAN unfairly favors the middle cylinders in its algorithm, CSCAN is fair to all cylinders
5. LOOK and CLOOK scheduling - just like SCAN/CSCAN but don't go to the end cylinder of the disk, stop at the last request.

We did an example in class using each algorithm. There is a nice example given in the text.

Disk Management

Low-level formatting - disks are formatted into 512 byte sectors, right at the factory

These sectors may have accounting information located in the head or tail of the sector. The accounting information, used by the disk, can include support for Error Correcting Code (ECC) so that minor 1-2 bit errors can be detected and fixed automatically.

For the OS to actually use the disk it needs to:

• Partition the disk (if requested)
• Do logical formatting and create structures needed to support the file system, these vary from OS to OS as we saw in Chapter 11/12.

A boot disk will contain a boot block that can be loaded at system startup by the boot ROM and initialize your operating system. Not all disks contain a boot block.

Handling disk errors, or "bad blocks" is important. "Bad blocks" are bound to happen, but we don't want problems in a tiny fraction of the disk to make the disk unusable:

• In MS-DOS, the File Allocation Table (FAT) marks bad blocks on the disk so that they are not used
• In Unix, a SCSI disk can maintain a list of bad blocks
• A more exotic solution is for the disk to perform sector sparing/forwarding where the disk saves a number of sectors on the disk for repair. Then, any reference to a bad block is caught by the disk and forwarded to its repair sector. This can create havoc with our disk scheduling algorithm though because repair sectors can be on a different cylinder than the actual request... so, some disks keep spare sectors on each cylinder.
• Sector slipping is a technique where the disk renumbers sectors and just skips the bad ones in its numbering.

If a block on the disk goes bad after data has been stored on it, then manual intervention is required (because your data is probably lost).

Swap space (used for virtual memory) on a disk is a special case and frequently is not setup with the normal file structures. This is called a raw partition. Swap space doesn't require the functionality of a normal file system, and therefore can be sped up by removing the file system overhead. The Solaris2 OS provides you with the option to choose.

RAID Structure

RAID = Redundant Array of Independent (or Inexpensive) Disks

Use redundant storage of data on multiple disks to reduce the probability of losing data.

Mirroring - copy each piece of data on two or more disks

Example: If the mean time to failure of a single disk is 100,000 hours (roughly 4,000 days, 10+ years), that's great. However, if our total system includes 100 of these disks, then the mean time to failure of any disk on the system is now 4,000 days / 100, or 40 days. We can significantly reduce this time by storing data on multiple disks, in which case, data is lost only when 2 or more independent disks fail (nearly) simultaneously.

The notion of truly "independent" disks is a bit unrealistic. Disks within some proximity of each other may be subject to the same power failures or act of nature.

Bit striping is a special kind of RAID application used to increase parallelism and, therefore, performance. Bit striping stores each bit of a byte or word on a separate disk. For example, you could use 8 disks and 1 bit of each byte would be stored on each disk. This improved the speed of disk access roughly 8x.

NOTE: We skipped sections 14.5.3 and 14.5.4 that deal with "RAID Levels", and you will not be responsible for this material.

Disk Attachment

Disks can be connected to a computer system via:

• host-attached - where the connection is via some local port, like IDE or USB on a PC
• network-attached - where the connection is over some network and uses a protocol like IP, sockets for access

Tertiary Storage

Used for backup of secondary storage

Must be cheap and removable

Examples: CD-ROM, tapes, floppy drive

Removable disk are also possible. The trick is that the disk head not be close to the disk so that disk head crashes happen when the disk is moved. Some solutions include:

• magneto-optic disk - uses laser for reading magnetic changes on the disk
• optical disk - laser used, but to read changes in the reflective nature of the surface of the disk
• WORM - Write Once, Read Many media
• Read-only - media like CD-ROM, DVD-ROM

The application and user interface to tertiary storage is either setup to mimic the file system or in a special format that will require special software for inspection and use.

Finally, in class, Prof Bill used the historical price charts on pages 524 and 525 to reminisce. The class sighed and rolled their collective eyes as Bill blathered about PC's in 1982 ("back in the day") that had only 16 KB or RAM and 10 MB of disk space ("and we were happy to have that"). So, we calculated that using the same rate of growth over the next 20 years, in 2022, Ahmad will purchase a computer at www.dell.com that has nearly 200 TB (trillion bytes) of disk space... all affordable on a student's allowance, of course.

Thanks... yow, bill