Bad Block Recovery - Disk Management

Disks have moving parts and some tolerances, they are prone to failure. Most disks even come from the factory with bad blocks. Depending on the disk and controller in use, these blocks are handled in a variety of ways.

- Simple disks such as disks with IDE controllers, bad blocks are handled manually.
The MS-DOS format command does a logical format, scans the disk to find bad blocks. If format finds a bad block, it writes a special value into the corresponding FAT entry to tell the allocation routines not to use that block.

- More sophisticated disks, such as SCSI disks used in high-end PCs and most workstations, are smarter about bad block recovery. The controller has a list of bad blocks on the disk and this list is initialized during low-level format at factory, and is updated over the life of the disk. Low-level formatting also sets aside spare sectors not visible to operating system. The controller can be told to replace each bad sector logically with one of the spare sectors. This scheme is called sector sparing.

A typical bad sector transaction :
- The operating system tries to read logical block 87.
- The controller calculates the ECC and finds that the sector is bad. It reports this finding to the operating system.
- The next time the system is rebooted, a special command is run to tell the SCSI controller to replace the bad sector with a spare.
- After this, whenever the system requests logical block 87, the request is translated into the replacement sector's address by the controller.

An alternative to sector sparing, some controllers can be instructed to replace a bad block by sector slipping.
The replacement of a bad block generally is not a totally automatic process, because the data in the bad block usually are lost. Thus, whatever file was using that block must be repaired, and that requires manual intervention.

Boot Block - Disk Management

A program at some fixed location on a hard disk, floppy disk or other media, which is loaded when the computer is turned on or rebooted and which controls the next phase of loading the actual operating system. The loading and execution of the boot block is usually controlled by firmware in ROM or PROM.
There is an initial program that is run whenever a computer starts running. This initial program initializes all aspects of the system, from CPU registers to device controllers and the contents of the main memory, and then starts the operating system.
Generally, the bootstrap is stored in read-only-memory (ROM) because ROM needs no initialization, and is at a fixed location that the processor can start executing when powered up or reset. The problem is that changing this bootstrap code requires changing ROM hardware chips. For this reason, most systems store a tiny bootstrap loader program in the boot ROM, whose only job is to bring in a full bootstrap program from disk.
The code in the boot ROM instructs the disk controller to read the boot blocks into memory, and then starts executing the code. The full bootstrap program is more sophisticated than the bootstrap loader in the boot ROM, and is able to load the entire operating system from a non-fixed location on disk, and to start the operating system running.

High Level Formatting

The second formatting step is high-level formatting. This is the process of creating the disk's logical structures such as the file allocation table and root directory. The high-level format uses the structures created by the low-level format to prepare the disk to hold files using the chosen file system.

Method of formatting a hard disk drive that initializes portions of the hard disk drive and creates important file system areas on the disk. A good example of a high-level format is using the format command in MS-DOS.

A high-level format is commonly done if a user wishes to erase the hard disk drive and reinstall the operating system back onto the hard disk drive. If errors are present on the hard disk drive, or a high-level format is unable to be completed, a low-level format may need to be done first.

For a hard disk, there is an intermediate task that is performed between the two formatting steps: partitioning. For this reason, combined with the incredible complexity of modern hard disks, they are low-level formatted by the manufacturer, and high-level formatting is done by the DOS FORMAT command (or equivalent). Floppy disks require no intermediate step, and due to their relative simplicity, they are both low-level and high-level formatted at the same time by default when you use the FORMAT command.

Disk Formatting and Low level formatting of floppy disks

Disk formatting is the initial part of the process for preparing a hard disk or other storage medium for its first use. The disk formatting includes setting up an empty file system. A disk formatting may setup multiple file systems by formatting partitions for each file system. Disk formatting is also part of a process involving rebuilding an entire disk from scratch.

There are two steps involved in formatting magnetic media such as floppy disks and hard disks.

Low-level formatting of floppy disks : The first step involves the creation of the actual structures on the surface of the media that are used to hold the data. This means recording the tracks and marking the start of each sector on each track. This is called low-level formatting, and sometimes is called "true formatting" since it is actually recording the format that will be used to store information on the disk. Once the floppy disk has been low-level formatted, the locations of the tracks on the disk are fixed in place. Since floppies use a stepper motor to drive the head actuator, the floppy drive must be aligned properly in order to read the tracks on the disk. Sometimes the heads of a particular drive can become out of alignment relative to where they should be; when this happens you may notice that a disk formatted on the misaligned drive will work in that drive but not in others, and vice-versa.
Since floppy disks tend to be put together cheaply these days and many of them are getting rather old, it is generally preferable to always low-level format a disk in the drive you plan to use to write to it.

C-SCAN Scheduling and LOOK Scheduling

Circular SCAN is a variant of SCAN that is designed to provide a more uniform wait time. Like SCAN, C-SCAN moves the head from one end of the disk to the other, servicing requests along the way. When the head reaches the other end, however, it immediately returns to the beginning of the disk, without servicing any requests on the return trip. The C-SCAN scheduling algorithm essentially treats the cylinders as a circular list that wraps around from the final cylinder to the first one.

Both SCAN and C-SCAN move the disk arm across the full width of the disk. In practice, neither of the algorithm is implemented this way. More commonly, the arm goes only as far as the final request in each direction. Then, it reverses the direction immediately, without first going all the way to the end of the disk. These versions of SCAN and C-SCAN are called LOOK and C-LOOK scheduling.

How to select a Disk Scheduling algorithm ?
With any scheduling algorithm, performance depends heavily on the number and types of requests. Suppose that the queue has just one request, then, all the scheduling algorithms are forced to behave the same, because they have no choice except one. They all behave like FCFS scheduling.
The requests for disk service can be greatly influenced by the file allocation method. The location of directories and index blocks is also important. Since every file must be opened to be used, and opening a file requires searching the directory structure, the directories will be accessed frequently.
The disk scheduling algorithm should be written as a separate module so that it can be replaced with a different algorithm if necessary. Either SSTF or LOOK is a reasonable choice for default algorithm.

Disk Scheduling Algorithm - SCAN Scheduling

In this algorithm the head always constantly moves from the most inner cylinder to the outer cylinder, then it changes its direction back towards the center. As the head moves, if there is a request for the current disk position it is satisfied. The throughput is better than in FIFO. The SCAN algorithm is more fair that SSTF. This algorithm is named after the behavior of a building elevator, where the elevator continues to travel in its current direction (up or down) until empty, stopping only to let individuals off or to pick up new individuals heading in the same direction.



The arm movement is thus always less than twice the number of total cylinders then, for both versions of the elevator algorithm. The variation has the advantage to have a smaller variance in response time. The algorithm is also relatively simple.
However, the elevator algorithm is not always better than Shortest seek first, which is slightly closer to optimal, but can result in high variance in response time and even in starvation when new requests continually get serviced prior to existing requests.
Anti-starvation techniques can be applied to the shortest seek time first algorithm to guarantee an optimum response time.

Disk Scheduling Algorithm - SSTF Scheduling

Shortest seek first (or shortest seek time first) is a secondary storage scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests. This is a direct improvement upon a first-come first-served (FIFO) algorithm. The drive maintains an incoming buffer of requests, and tied with each request is a cylinder number of the request. Lower cylinder numbers indicate that the cylinder is closest to the spindle, and higher numbers indicate the cylinder is further away.

The shortest seek first algorithm determines which request is closest to the current position of the head, and then services that request next. The shortest seek first algorithm has the direct benefit of simplicity and is clearly advantageous in comparison to the FCFS method, in that overall arm movement is reduced, resulting in lower average response time.

However, since the buffer is always getting new requests, these can skew the service time of requests that may be farthest away from the disk head's current location, if the new requests are all close to the current location; in fact, starvation may result, with the faraway requests never being able to make progress.
SSTF scheduling is essentially a form of shortest-job-first (SJF) scheduling, and like SJF scheduling, it may cause starvation of some requests.