Mass -Storage

Structure
C 1 H

A 0 PTER

The file system can be viewed logically as consisting of three parts. In Chapter
11, we examine the user and programmer interface to the file system. In
Chapter 12, we describe the internal data structures and algorithms used by
the operating system to implement this interface. In this chapter, we begin a
discussion of file systems at the lowest level: the structure of secondary storage.
We first describe the physical structure of magnetic disks and magnetic tapes.
We then describe disk-scheduling algorithms, which schedule the order of
disk I/Os to maximize performance. Next, we discuss disk formatting and
management of boot blocks, damaged blocks, and swap space. We conclude
with an examination of the structure of RAID systems.

10.1 Overview of Mass-Storage Structure

In this section, we present a general overview of the physical structure of
secondary and tertiary storage devices.

10.1.1 Magnetic Disks

Magnetic disks provide the bulk of secondary storage for modern computer
systems. Conceptually, disks are relatively simple (Figure 10.1). Each disk
platter has a flat circular shape, like a CD. Common platter diameters range
from 1.8 to 3.5 inches. The two surfaces of a platter are covered with a
magnetic material. We store information by recording it magnetically on the
platters.
467
468 Chapter 10 Mass-Storage Structure

track t spindle

arm assembly
sector s

cylinder c read-write
head

platter
arm

rotation

Figure 10.1 Moving-head disk mechanism.

A read – write head “flies” just above each surface of every platter. The
heads are attached to a disk arm that moves all the heads as a unit. The
surface of a platter is logically divided into circular tracks, which are
subdivided into sectors. The set of tracks that are at one arm position makes
up a cylinder. There may be thousands of concentric cylinders in a disk
drive, and each track may contain hundreds of sectors. The storage capacity
of common disk drives is measured in gigabytes.
When the disk is in use, a drive motor spins it at high speed. Most drives
rotate 60 to 250 times per second, specified in terms of rotations per minute
(RPM). Common drives spin at 5,400, 7,200, 10,000, and 15,000 RPM. Disk
speed
has two parts. The transfer rate is the rate at which data flow between the
drive
and the computer. The positioning time, or random-access time, consists of
two parts: the time necessary to move the disk arm to the desired cylinder,
called the seek time, and the time necessary for the desired sector to rotate to
the disk head, called the rotational latency. Typical disks can transfer several
megabytes of data per second, and they have seek times and rotational
latencies
of several milliseconds.
 10.4 Disk Scheduling 47
3

10.4 Disk Scheduling

One of the responsibilities of the operating system is to use the
hardware efficiently. For the disk drives, meeting this responsibility
entails having fast

access time and large disk bandwidth. For magnetic disks, the access time has two
major components, as mentioned in Section 10.1.1. The seek time is the time for
the disk arm to move the heads to the cylinder containing the desired sector. The
rotational latency is the additional time for the disk to rotate the desired sector to
the disk head. The 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. We can improve both the access time and the bandwidth by managing
the order in which disk I/O requests are serviced.
Whenever a process needs I/O to or from the disk, it issues a system call to
the operating system. The request specifies several pieces of information:

• Whether this operation is input or output

• What the disk address for the transfer is
• What the memory address for the transfer is
• What the number of sectors to be transferred is

If the desired disk drive and controller are available, the request can be
serviced immediately. If the drive or controller is busy, any new requests
for service will be placed in the queue of pending requests for that drive.
For a multiprogramming system with many processes, the disk queue may
often have several pending requests. Thus, when one request is completed,
the operating system chooses which pending request to service next. How
does the operating system make this choice? Any one of several disk-
scheduling algorithms can be used, and we discuss them next.

10.4.1 FCFS Scheduling

The simplest form of disk scheduling is, of course, the first-come, first-served
(FCFS) algorithm. This algorithm is intrinsically fair, but it generally does not
provide the fastest service. Consider, for example, a disk queue with requests
for I/O to blocks on cylinders

98, 183, 37, 122, 14, 124, 65, 67,

 Figure 10.4 FCFS disk scheduling.

in that order. If the disk head is initially at cylinder 53, it will first move from
53 to 98, then to 183, 37, 122, 14, 124, 65, and finally to 67, for a total head
movement of 640 cylinders. This schedule is diagrammed in Figure 10.4.
The wild swing from 122 to 14 and then back to 124 illustrates the problem
with this schedule. If the requests for cylinders 37 and 14 could be serviced
together, before or after the requests for 122 and 124, the total head
movement
could be decreased substantially, and performance could be thereby
improved.

10.4.2 SSTF Scheduling

It seems reasonable to service all the requests close to the current head
position before moving the head far away to service other requests. This
assumption is the basis for the shortest-seek-time-first (SSTF) algorithm. The
SSTF algorithm selects the request with the least seek time from the current
head position. In other words, SSTF chooses the pending request closest to
the current head position.
For our example request queue, the closest request to the initial head
position (53) is at cylinder 65. Once we are at cylinder 65, the next closest
request is at cylinder 67. From there, the request at cylinder 37 is closer than
the one at 98, so 37 is served next. Continuing, we service the request at
cylinder 14, then 98, 122, 124, and finally 183 (Figure 10.5). This scheduling
method results in a total head movement of only 236 cylinders — little more
than one-third of the distance needed for FCFS scheduling of this request
queue. Clearly, this algorithm gives a substantial improvement in
performance.
SSTF scheduling is essentially a form of shortest-job-first (SJF) scheduling;
and like SJF scheduling, it may cause starvation of some requests. Remember
that requests may arrive at any time. Suppose that we have two requests in
the queue, for cylinders 14 and 186, and while the request from 14 is being
serviced, a new request near 14 arrives. This new request will be serviced
next, making the request at 186 wait. While this request is being serviced,
another request close to 14 could arrive. In theory, a continual stream of
requests near one another could cause the request for cylinder 186 to wait
indefinitely.
 queue = 98, 183, 37, 122, 14, 124, 65, 67
head starts at 53
0 14 37 53 65 67 98 122124 183199

Figure 10.5 SSTF disk scheduling.

This scenario becomes increasingly likely as the pending-request queue

grows longer.
Although the SSTF algorithm is a substantial improvement over the FCFS
algorithm, it is not optimal. In the example, we can do better by moving the
head from 53 to 37, even though the latter is not closest, and then to 14, before
turning around to service 65, 67, 98, 122, 124, and 183. This strategy reduces
the total head movement to 208 cylinders.

10.4.3 SCAN Scheduling

In the SCAN algorithm, the disk arm starts at one end of the disk and moves
toward the other end, servicing requests as it reaches each cylinder, until it
gets to the other end of the disk. At the other end, the direction of head
movement is reversed, and servicing continues. The head continuously scans
back and forth across the disk. The SCAN algorithm is sometimes called the
elevator algorithm, since the disk arm behaves just like an elevator in a
building, first servicing all the requests going up and then reversing to
service requests the other way.
Let’s return to our example to illustrate. Before applying SCAN to
schedule the requests on cylinders 98, 183, 37, 122, 14, 124, 65, and 67, we
need to know
the direction of head movement in addition to the head’s current position.
Assuming that the disk arm is moving toward 0 and that the initial head
position is again 53, the head will next service 37 and then 14. At cylinder 0,
the arm will reverse and will move toward the other end of the disk,
servicing the requests at 65, 67, 98, 122, 124, and 183 (Figure 10.6). If a request
arrives in the queue just in front of the head, it will be serviced almost
immediately; a request arriving just behind the head will have to wait until
the arm moves to the end of the disk, reverses direction, and comes back.
Assuming a uniform distribution of requests for cylinders, consider the
density of requests when the head reaches one end and reverses direction. At
this point, relatively few requests are immediately in front of the head, since
these cylinders have recently been serviced. The heaviest density of requests
 Figure 10.6 SCAN disk scheduling.

is at the other end of the disk. These requests have also waited the longest, so
why not go there first? That is the idea of the next algorithm.

10.4.4 C-SCAN Scheduling

Circular SCAN (C-SCAN) scheduling is a variant of SCAN 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 (Figure 10.7). The
C-SCAN scheduling algorithm essentially treats the cylinders as a circular list
that wraps around from the final cylinder to the first one.

queue = 98, 183, 37, 122, 14, 124, 65, 67

head starts at 53
0 14 37 53 65 67 98 122 124 183 199

Figure 10.7 C-SCAN disk scheduling.

 10.5 Disk Management 47
7

10.4.5 LOOK Scheduling

As we described them, both SCAN and C-SCAN move the disk arm across the full
width of the disk. In practice, neither algorithm is often implemented this way. More
commonly, the arm goes only as far as the final request in each direction. Then, it
reverses direction immediately, without going all the way to the end of the disk.
Versions of SCAN and C-SCAN that follow this pattern are called LOOK and C-LOOK
scheduling, because they look for a request before continuing to move in a given
direction (Figure 10.8).

queue = 98, 183, 37, 122, 14, 124, 65, 67 head

starts at 53
0 14 37 53 65 67 98 122 124 183 199

Figure 10.8 C-LOOK disk scheduling.