Hierarchical Storage Management (HSM)

Hierarchical Storage Management (HSM) is a data storage technique which automatically moves data between high-cost and low-cost storage media. HSM systems exist because high-speed storage devices, such as hard disk drive arrays, are more expensive (per byte stored) than slower devices, such as optical discs and magnetic tape drives. While it would be ideal to have all data available on high-speed devices all the time, this is prohibitively expensive for many organizations.

Instead, HSM systems store the bulk of the enterprise's data on slower devices, and then copy data to faster disk drives when needed. In effect, HSM turns the fast disk drives into caches for the slower mass storage devices. The HSM system monitors the way data is used and makes best guesses as to which data can safely be moved to slower devices and which data should stay on the fast devices.

A hierarchical storage system extends the storage hierarchy beyond primary memory and secondary storage to incorporate tertiary storage — usually implemented as a
jukebox of tapes or removable disks.
It usually incorporates tertiary storage by extending the file system.
* Small and frequently used files remain on disk.
* Large, old, inactive files are archived to the jukebox.
HSM is usually found in supercomputing centers and other large installations that have enormous volumes of data.

Performance Issues of Tertiary storage

There are three aspects of tertiary-storage performance :
- Speed : There are two aspects of speed in tertiary storage are bandwidth and
latency.
Bandwidth is measured in bytes per second.
* Sustained bandwidth – average data rate during a large transfer; # of bytes/transfer time.Data rate when the data stream is actually flowing.
* Effective bandwidth – average over the entire I/O time, including seek or locate, and cartridge switching. It drive’s overall data rate.

Access latency is the amount of time needed to locate data.
* Access time for a disk – It moves the arm to the selected cylinder and wait for the rotational latency; < 35 milliseconds.
* Access on tape requires winding the tape reels until the selected block reaches the tape head; tens or hundreds of seconds.
* Generally say that random access within a tape cartridge is about a thousand times slower than random access on disk.
The low cost of tertiary storage is a result of having many cheap cartridges share a few expensive drives. A removable library is best devoted to the storage of infrequently used data, because the library can only satisfy a relatively small number of I/O requests per hour.

- Reliability : A fixed disk drive is likely to be more reliable than a removable
disk or tape drive. An optical cartridge is likely to be more reliable than a
magnetic disk or tape. A head crash in a fixed hard disk generally destroys the data, whereas the failure of a tape drive or optical disk drive often leaves the data cartridge unharmed.

- Cost : The main memory is much more expensive than disk storage. The cost per megabyte of hard disk storage is competitive with magnetic tape if only one tape is used per drive. The cheapest tape drives and the cheapest disk drives have
had about the same storage capacity over the years. Tertiary storage gives a cost savings only when the number of cartridges is considerably larger than the number of drives.

Difference between Location independence and Static location transparency

There are few aspects that differentiates location independence and static location transparency :
- In location independence, divorcing data from location provides better abstraction fro files. Location independent files can be viewed as logical data containers that are not attached to specific storage location.
In static location transparency, the file name still denotes a specific, although hidden, set of physical disk blocks.

- In static location transparency, users can share remote files by simple naming the files in a location transparent manner, as though the files are local but nevertheless, logical names are still attached to physical storage devices.
Location independence promotes sharing the storage space as well as the data objects.
A possible benefit of such a view is the ability to balance the utilization of disks across the system.

- Location independence separates the naming hierarchy from the storage devices hierarchy and from the inter-computer structure.
In static location transparency, the correspondence between component units machines can be easily exposed.

Once the separation of name and location has been completed, files residing on remote server systems may be accessed by different clients. In fact, these clients may be diskless and rely on servers to provide all files, including the operating system kernel.

How to improve disk reliability ?

Disk used to be the least reliable component of the system. They still have relatively high failures and it causes loss of data and significant downtime. It takes hours to recover from a disk crash. Improving the reliability of disk systems is very important and several improvements in disk-use techniques have been proposed.
To improve speed, disk stripping uses a group of disks as one storage unit. Each data block is broken into several sub blocks, with one sub block stored on each disk. The time required to transfer a block into memory improves because all the disks transfer their sub blocks in parallel. If the disks have their rotation synchronized, the performance improves because all the disks become ready to transfer their sub blocks at the same time rather than waiting for the slowest rotational latency. This organization is usually called a redundant array of independent disks (RAID).

The simplest RAID organization, called mirroring or shadowing, just keeps a duplicate copy of each disk. This solution is costly but it is about twice as fast when reading, because half of the read requests can be sent to each disk.
Block Interleaved Parity, another RAID organization uses much less redundancy. A small fraction of disk space is used to hold parity blocks. Each bit position in the parity block would contain the parity for the corresponding bit positions in each of the 8 data blocks. If one disk block becomes bad, all its data bits are essentially erased but can be recomputed from other data blocks plus parity block.

A parity RAID system has the combined speed of multiple disks and controllers. But the performance is an issue during writing, because updating any single data sub block forces the corresponding parity sub block to be recomputed and rewritten.

Where is swap space located ?

Virtual memory uses disk space as an extension of main memory. Since disk access is much slower than memory access, using swap space has a large effect on system performance.

Swap space can reside at two places :
- It can be carved out of the normal file system : In this case, normal file system routines can be used to create it, name it, and to allocate its space. This approach is easy to implement but inefficient because navigating the directory structure and data structures takes time, and extra disk access. In addition to this, external fragmentation greatly increases swapping times. Performance can be improved by caching the block location information in physical memory but the cost of traversing the file system data structures still remains.

- It can be on a separate disk partition : There is no directory structure or file system placed on this space, a separate swap-space storage manager is used to allocate and deallocate the blocks. This manager uses algorithms that are optimized for speed, rather than for storage efficiency. Internal fragmentation may increase but this is acceptable as data in swap space resides for much shorter period. This approach creates a fixed amount of swap space during disk partitioning, adding more space can only be done via repartitioning of the disk.

How to use swap - space ?

Swap space is an area on a high-speed storage device (almost always a disk drive), reserved for use by the virtual memory system for deactivation and paging processes. At least one swap device (primary swap) must be present on the system. Virtual memory uses disk space as an extension of main memory and since memory access is faster than disk access, using swap space has a large effect on system performance.

It is perfectly normal for the swap file or page file to grow in size, sometimes growing several hundred megs in size. Below is a listing of common Microsoft operating system swap file information; however, it is important to realize that this information may vary. Finally, by default the swap files are hidden.

Operating system Swap file name Location

Windows 3.x 386PART.PAR C:\WINDOWS
Windows 95 / 98 / ME WIN386.SWP C:\
Windows NT / 2000 / XP PAGEFILE.SYS C:\

Swap space is used in various ways by different operating systems :
- Systems implementing swapping may use swap space to hold entire process image, including the code and data segments.
- The pages that are moved out of main memory can be stored by paging systems.
- Some operating systems like UNIX allow use of multiple swap spaces. These swap spaces are generally put on separate disks, so the load placed on the I/O system by paging and swapping can be spread over the system's I/O devices.

The amount of swap space needed on a system can vary depending on the amount of physical memory, the amount of virtual memory it is backing, and the way in which the virtual memory is used.

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.

Disk Scheduling Algorithm - FCFS Scheduling

Scheduling is a key concept in computer multitasking, multiprocessing operating system and real-time operating system designs. The scheduler is concerned mainly with :
* CPU utilization - to keep the CPU as busy as possible.
* Throughput - number of process that complete their execution per time unit.
* Turnaround - total time between submission of a process and its completion.
* Waiting time - amount of time a process has been waiting in the ready queue.
* Response time - amount of time it takes from when a request was submitted until the first response is produced.
* Fairness - Equal CPU time to each thread.

Scheduling Algorithms :
CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated the CPU. There are many different CPU scheduling algorithms.

- First Come First Served (FCFS): The disk controller processes the I/O requests in the order in which they arrive, thus moving backwards and forwards across the surface of the disk to get to the next requested location each time. Since no reordering of request takes place the head may move almost randomly across the surface of the disk. This policy aims to minimize response time with little regard for throughput.
Illustration shows total head movement of 640 cylinders.
queue = 98, 183, 37, 122, 14, 124, 65, 67
Head starts at 53.



The problem with this schedule is illustrated by the wide swing from 122 to 14 and then back to 124. If the requests for cylinders 37 and 14 could be serviced together, before or after the requests at 122 and 124, the total head movement could be decreased substantially, and performance could be improved.

Secondary Storage Structure - Disk Structure

Secondary storage structure helps to :
- Describe the physical structure of secondary and tertiary storage devices and the resulting effects on the uses of the devices.
- Explain the performance characteristics of mass-storage devices.
- Discuss operating-system services provided for mass storage, including RAID and HSM.

Disk provide the bulk of secondary storage for modern computer systems. Disk drives are addressed as large 1-dimensional arrays of logical blocks, where the logical block is the smallest unit of transfer. The 1-dimensional array of logical blocks is mapped onto the sectors of the disk sequentially.
- Sector 0 is the first sector of the first track on the outermost cylinder.
- Mapping proceeds in order through that track, then the rest of the tracks in that cylinder, and then through the rest of the cylinders from outermost to innermost.
- The operating system is responsible for using hardware efficiently — for the disk drives, this means having a fast access time and disk bandwidth.
- Access time has two major components.
* Seek time is the time for the disk arm to move the heads to the cylinder containing the desired sector.
* Rotational latency is the additional time waiting for the disk to rotate the desired sector to the disk head.
- Minimize seek time.
- Seek time seek distance.
- Disk bandwidth is the total number of bytes transferred, divided by the total time between the first request for service and the completion of the last transfer.
- Several algorithms exist to schedule the servicing of disk I/O requests.