Disk Management

Disk Structure

Disks come in many sizes and speeds, and information may be stored optically or magnetically; however, all disks share a number of important features. For example, floppy disks, hard disks, CD-ROMs and DVDs. Disk surface is divided into a number of logical blocks called sectors and tracks. The term cylinder refers to all the tracks at a particular head position in the hard disk.

Disk Operations

Latency Time

It is the time taken to rotate from its current position to a position adjacent to the R/W head.

Seek

The processes of moving the arm assembly to new cylinder.

To access a particular record, first, the arm assembly must be moved to the appropriate cylinder, and then rotate the disk until it is immediately under the read-write head. The time taken to access the whole record is called transmission time.

Disk Scheduling

OS is responsible for utilizing the hardware effectively – for the disk drive, this implies fast seek, latency and transmission time. For most disks, the seek time commands the other two times, so lessening the mean seek time can enhance system performance significantly.

Disk Scheduling Algorithms

First-Come-First-Serve (FCFS)

• All incoming requests are placed at the end of the queue.
• Whatever number that is next in the queue will be the next number served.
• Using this algorithm doesn't provide the best results.
• To determine the number of head movements you would simply find the number of tracks it took to move from one request to the next.

For example, given the following queue -- 95, 180, 34, 119, 11, 123, 62, 64 with the Read-write head initially at the track 50 and the tail track being at 199. Then the FCFS algorithm gives the following:

For this case, it went from 50 to 95 to 180 and so on. From 50 to 95 it moved 45 tracks. If you tally up the total number of tracks you will find how many tracks it had to go through before finishing the entire request. In this example, it had a total head movement of 640 tracks. The disadvantage of this algorithm is noted by the oscillation from track 50 to track 180 and then back to track 11 to 123 then to 64. As you will soon see, this is the worse algorithm that one can use. (Disk Scheduling Algorithms, n.d.)

Shortest-Seek-Time-First (SSTF)

• In this case, the request is serviced according to next shortest distance.
• There is a great chance that starvation would take place. The reason for this is if there were a lot of requests close to each other the other requests will never be handled since the distance will always be greater.

For example, given the following queue -- 95, 180, 34, 119, 11, 123, 62, 64 with the Read-write head initially at the track 50 and the tail track being at 199. Then the SSTF algorithm gives the following:

Starting at 50, the next shortest distance would be 62 instead of 34 since it is only 12 tracks away from 62 and 16 tracks away from 34. The process would continue until all the processes are taken care of (Disk Scheduling Algorithms, n.d.).

SCAN

• This approach works like an elevator does.
• It scans down towards the nearest end and then when it hits the bottom it scans up servicing the requests that it didn't get going down.
• If a request comes in after it has been scanned it will not be serviced until the process comes back down or moves back up (Disk Scheduling Algorithms, n.d.).
• It decreases variance in seeking and improves response time.
• If there are repeated requests in current track, it may cause starvation.

For example, given the following queue -- 95, 180, 34, 119, 11, 123, 62, 64 with the Read-write head initially at the track 50 and the tail track being at 199. Then the SCAN algorithm gives the following:

C-Scan

• Circular scanning works simply like the elevator to some degree.
• It starts its scan toward the closest end and works it way to the end of the system.
• Once it arrives at the bottom or top, it jumps to the next end and moves in the same direction.
• A huge jump isn't considered a head movement.

For example, given the following queue -- 95, 180, 34, 119, 11, 123, 62, 64 with the Read-write head initially at the track 50 and the tail track being at 199. Then the C-SCAN algorithm gives the following:

C-LOOK

• This is only an upgraded variant of C-SCAN.
• In this, the scanning doesn't go past the last request in the direction that it is moving.
• It too jumps to the next end however not all the way to the end, just to the farthest request.

For example, given the following queue -- 95, 180, 34, 119, 11, 123, 62, 64 with the Read-write head initially at the track 50 and the tail track being at 199. Then the C-SCAN algorithm gives the following:

Error Handling

Most frequently, one or more sectors become defective or most disk even come from a factory with bad blocks. There are two general approaches to bad blocks; deal with them in the controller or deal with them in the operating system. In the former approach, before the disk is shipped from the factory, it is tested and a list of bad sectors is written onto the disk. For each bad sector, one of the spares is substituted for it. Errors can likewise develop amid ordinary operation after the drive has been installed. The primary line of defence after getting an error that the ECC can't deal with is to simply attempt the read once more. Some read mistakes are transient, that is, are brought on by bits of dust under the head and will go away on a second attempt, if the controller sees that it is getting repeated errors on a specific sector, it can switch to an extra before the segment has passed on totally. Thus, no data are lost and the OS and the user don't see the problem.

Disk Formatting

A hard disk consists of a stack of aluminium, alloy, or glass platters 5.25 inch or 3.5 inches in diameter (or even smaller on notebook computers). On each platter is deposited a thin magnetisable metal oxide. Before the disk can be used, each platter must receive a low-level format done by software. The format consists of a series of concentric tracks, each containing some number of sectors, with short gaps between the sectors (Tanenbaum, 2013). Before a disk can store data, it must be divided into sectors that the disk controller can read and write, called low-level formatting. The sector typically consists of a preamble data and ECC. The preamble contains the cylinder and sector number and the ECC contains redundant information that can be used to recover from read error. The size depends on upon the manufacturer, depending on reliability. If the disk I/O operations are constrained to exchanging a single sector at once, it reads the primary sector from the disk and doing the ECC computation, and transfers to main memory, amid this time the next sector will fly by the head. At the point when transferring finishes, the controller will need to sit tight right around a whole rotation for the second sector to come around once more. This issue can be solved by numbering the sectors in an interleaved style while formatting the disk. As indicated by the replicating rate, interleaving might be of single or double.

RAID

RAID (redundant array of independent disks; originally redundant array of inexpensive disks) provides a way of storing the same data in different places thus,on multiple hard disks(though not all RAID levels provide redundancy). By placing data on multiple disks, I/O operations can overlap in a balanced way, improving performance. Since multiple disks increase the mean time between failures (MBEF), storing data redundantly also increases fault tolerance(Rouse, n.d.). RAID allows more than one disk to be used for a given operation and allows continued operation and even automatic recovery in the face of disk failure. Implemented in hardware or in OS.

RAID Level 0

• Creates one large virtual disk from a number of smaller disks.
• Storage is grouped into logical units called strips with the size of a strip being some multiple of sector size.
• The virtual storage is a sequence of strips interleaved among the disks in the array.
• Can create a large disk.
• Performance benefit can be achieved.
• Reliability decreases.

RAID Level 1

• Stores duplicate copy of each strip, with each copy on a different disk.
• Excellent reliability
• If drive crashes, the copy is used.
• Read performance can be achieved.
• Write Performance is no better than in single drive.

RAID Level 2

• An error-correcting code is used for corresponding bits on each data disks.
• Error-correcting scheme store two or more extra bits, and can reconstruct the data if a single bit get damaged.
• Total parallelism.
• Requires a substantial number of drives.

RAID Level 3

• A simplified version of Level 2.
• A single parity bit is used instead of error-correcting code, hence required just one extra disk.
• If any disk in the array fails, its data can be determined from the data on the remaining disks.
• It is as good as Level 2 but is less expensive in the number of extra disks.

RAID Level 4

• It uses block-level striping, as in Level 0, and in addition keeps a parity block on a separate disk for corresponding blocks from other disks.
• If one of the disks fails, the parity block can be used with the corresponding blocks from other disks to restore the blocks of the fail disks.
• The transfer rate for large read as well as large write is high since reads and writes in parallel but small read and write cannot be in parallel.

RAID Level 5

• Similar to level 4 but parity information is distributed on all disks.
• For each block one of the disk stores parity and other stores data.

Stable Storage

For some applications, it is essential that data never be lost or corrupted, even in the face of disk and CPU errors. Ideally, a disk should simply work all the time with no errors. Unfortunately, that is not achievable. What is achievable is a disk subsystem that has the following property: when a write is issued to it, the disk either correctly writes the data or it does nothing, leaving the existing data intact. Such as system is called stable storage and is implemented in software (Lampson & Sturgis, 1979).

Stable storage uses a pair of identical disks with the corresponding blocks working together to form one error-free block. In the absence of errors, the corresponding blocks on both drives are the same. Either one can be read to get the same result. To achieve this goal, the following three operations are defined:

Stable writes

A stable write comprises of first composition the block on drive 1, then reading it back to check that it was written accurately. If it was not written accurately, the write and reread are done again up to n times until they work. After n back to back failures, the block is remapped onto a spare and the operation repeated until it succeeds, regardless of what number of spares must be attempted. After the write to drive 1 has succeeded, the corresponding block on drive 2 is written and reread, over and again if need be, until it, as well, finally succeeds. Without CPU crashes, when a stable write finishes, the block has effectively been written onto both drives and confirmed on both of them.

Stable reads

A stable read first reads the block from drive 1. In the event that this yields a wrong ECC, the read is attempted once more, up to n times. If these give terrible ECCs, the corresponding block is read from drive 2. Given the fact that an effective stable write leaves two great duplicates of the block behind, and our assumption that the likelihood of the same block spontaneously turning bad on both drives in a sensible time interval is negligible, a stable read always succeeds.

Crash recovery

After a crash, a recovery program checks both disks looking at corresponding blocks. If a couple of blocks are both good and the same, nothing is done. If one of them has an ECC error, the bad block is overwritten with the corresponding good block. If a couple of blocks are both good however distinctive, the block from drive 1 is written onto drive 2. (Tanenbaum, 2013)

References

Disk Scheduling Algorithms. (n.d.). Retrieved from Illinois Institute of Technology: http://www.cs.iit.edu/~cs561/cs450/disksched/disksched.html

Lampson, B., & Sturgis, H. E. (1979). Crash Recovery in a Distributed Data Storage System.

Rouse, M. (n.d.). What is RAID? Retrieved from TechTarget: http://searchstorage.techtarget.com/definition/RAID

Tanenbaum, A. S. (2013). Modern Operating Systems. Delhi: PHI Learning Private Limited.