Disk Structure
9 Disk Structure NOTES
The Chapter Covers :
n Introduction to Disks
n Disk Scheduling
n Disk Management
n Disk Reliability
n Swap Space Management
n Stable Storage Implementation
9.1 INTRODUCTION
Magnetic disk or simply disk is a random access secondary storage device. Ran-
dom access means any location may be selected at random, access to the informa-
tion stored is direct and approximately equal access time is required for each
location. Physically a magnetic disk is a thin, circular metal plate coated on both
sides with a magnetic material. As a storage device disk plate is not used a disk
pack is used. A disk pack consists of a number of these disks. These disks are
mounted about half an inch apart from each other on a central spindle. In a disk
pack, information is stored on both the surfaces of each disk plate. The upper
surface of the top plate and the lower surface of the bottom plate are not used. 175
Operating Systems Magnetic disks are the most popular medium for secondary storage. There are three
main concepts of disk pack :
(1) Track - Each disk is divided into a number of concentric circles logically and
NOTES each of such circle in called track (Figure 9.1). In most system each track
contains the same number of characters, which means that inner track are more
densely packed with data.
Figure 9.1, 100 tracks on the disk plate Figure 9.2, Sectors of a track
(2) Sector – All the tracks on a plate are subdivided into sectors.
(3) Cylinder – A set of corresponding tracks in all the surfaces is called a cylinder
(Figure 9.3).
From the disk pack, the smallest unit of data transfer is the logical block. The size
of a logical block may be 512 bytes, 1024 bytes etc. The one-dimensional array
of logical blocks is mapped onto the sectors of the disk sequentially. Sector 0is the
first sector of the first track on the outermost cylinder. The mapping proceeds in
order through that track, then through the rest of the tracks in that cylinder and then
through the rest of the cylinders from outermost to innermost. The total number of
bytes that can be stored in a disk pack is :
Number of cylinders × tracks per cylinder × sectors per track × Bytes per sector.
9.2 DISK SCHEDULING
Disk is most widely used on a secondary storage medium in most computer sys-
tems. But the speed of disk is less than the CPU. So it is necessary to use disk by
the operating system more efficiently.
The two main component that affect the speed of disk are :
(i) Access time (ii) Disk bandwidth
The access time has two major components: seek time and rotational latency. The
time required to position the head over the proper track is called the seek time. The
rotational latency is defined, as the time spent to rotate the desired sector to the
176 head of disk. The bandwidth of disk is the ratio of total number of bytes transferred
and total time for this transfer.
Disk Structure
NOTES
Figure 9.3, Cylinder of a disk pack
The objective of disk scheduling is to reduce access time and increase bandwidth.
After receiving a request for I/O to or from the disk, if the disk drive is free, the
request can be handled immediately. If the drive is busy, any new request for service
will be placed on the queue of pending requests for that drive. In a multiprogram-
ming system, many processes may be generating request for reading and writing
disk records. So the disk queue may have several pending requests. Thus when one
request is serviced, the operating system schedules the next request to service from
the queue of pending requests.
Following are some of the disk scheduling algorithms :
9.2.1 FCFS (First Come First Served) Scheduling
Check Your Progress
This is the simplest disk scheduling algorithm. As its name suggests the request that
comes first is serviced first. For example, the requests for I/O to blocks are on 1. Write down the names
cylinders in the following order 90, 180, 40, 125, 15, 130, 61, 64. of two main compo-
nents that affect the
If the disk head is initially at cylinders 60, it will first move from 60 to 90 then to speed of disk.
180, 40, 125, 15, 130, 61 and 64.
2. Define Scan Sched-
Total Head movement are :- uling.
(90 - 60) + (180 - 90) + (180 - 40) + (125 - 40)
+ (125 - 15) + (130 - 15) + (130 - 61) – (64 - 61)
= 30 + 90 + 140 + 85 + 110 + 115 + 69 + 3
= 642 cylinders
The schedule is shown in figure 9.4
177
Operating Systems
NOTES
Figure 9.4 : An example schedule of FCFS
One drawback with this approach as seen in fig. 9.4 is that there is a wild swing
from 125 to 15 and then back to 130. If 40 and 15 both requests are served
together one after another then total head movement can be decreased and perfor-
mance can be improved.
9.2.2 SSTF Scheduling
In shortest seek time first scheduling, priority is given to those processes which
require the shortest seek time from the current head position, Since seek time
increases with the number of cylinders traversed by the head. SSTF chooses all
request nearer to the current head position to serviced together.
Consider the previous example of request queue of 90, 180, 40, 125, 15, 130, 61
and 64 cylinders. The closest request to the initial head position 60 is at cylinders
61. Then request to cylinder 64 is serviced, the next closest request is at cylinder
40 from here the request at cylinder 15 is serviced then 90, 125, 130 are serviced
and finally request at cylinder 180 is serviced. This scheduling method has total head
movement of only (61 - 60) + (64 - 61) + (64 - 40) + (40 - 15) + (90 - 15) +
(125 - 90) + (130 - 125) + (180 - 130) = 217 cylinders. This is little more than
one third of the distance needed for FCFS scheduling. This is substantial improve-
ment in performance.
The problem with this scheduling is that it may cause starvation on some request.
Figure 9.5 : An example SSTF Schedule
9.2.3 SCAN Scheduling
In the SCAN algorithm, the arm is moved in one direction only, satisfying all
outstanding requests in route, until it reaches the last cylinder in that direction. At the
178
other end, the service direction is reversed and servicing continues. This process
continues.
Let us consider our example of request queue of 90, 180, 40, 125, 18, 130, 61 Disk Structure
and 64 cylinders. The current head position is at cylinder 60 and we suppose that
the head is moving toward cylinder 0. Then the request for 40 is serviced first then
15 is serviced. At cylinder 0, the arm will be reversed. Then the requests at 61, 64,
90, 125, 130 and 180 are serviced in this order. This is shown in figure 9.6. NOTES
Total Head movement are :
(60 - 40) + (40 - 15) + (15 - 0) + (61 - 0) + (64 – 61)
+ (90 - 64) + (125 - 90) + (130 – 125) + (180 - 130)
= 20 + 25 + 15 + 61 + 3 + 26 + 35 + 5 + 50
= 240 Cylinders
Figure 9.6 : An example SCAN Schedule
9.2.4 C-SCAN Scheduling
The circular scan (C-SCAN) is a form of SCAN scheduling. It works like SCAN
scheduling, except that scanning is done in one direction only. Thus when the last
track has been visited in one direction the arm is returned to the opposite end of
the disk and the scan begins again. This is shown in figure 9.7 with schedule of our
previous example.
Figure 9.7 : An example Schedule of C-SCAN
9.2.5 Look and C-Look Scheduling
Look and C-Look are similar to SCAN and C-SCAN respectively except that in
these two head moves in a direction until there are no more requests in that direc-
tion. These two are shown is figure 9.8 and figure 9.9 respectively. 179
Operating Systems
NOTES
Figure 9.8 : An example of Look Schedule
Figure 9.9 : An example schedule of C-Look
9.3 DISK MANAGEMENT
Disk management is also the responsibility of operating system. Here we discuss
some of disk management tasks.
9.3.1 Disk Formatting
For data to be stored on a disk, it must be formatted. This procedure places
electronic marks on the disk's surface so files can be saved and opened in an
orderly fashion. On a magnetic disk, formatting divides the surface into circular
tracks and pie-shaped sectors. Since tracks can store a large amount of data, the
computer divides them into sectors which make it easier to find a location on the
disk. In the process of formatting, a special data structure is maintained for each
sector. This data structure is made up of a header, a data area and a trailer. Disk
controller was the header and trailer information. Sector number and an error
correcting codes are written in header and trailer information. When data is written
on the sector, the ECC is calculated for all the bytes in the data area. On reading
the sector, the ECC is recalculated and it is compared with the stored value. If both
values are different it means that the data area of the sector has become corrupted
and that the disk sector may be bad. Using the ECC, the disk controller corrects
the error. The ECC processing is done automatically by the controller whenever a
sector is read or written.
The operating system records its own data structure on the disk for making the disk
usable for storing files. For the purpose the disk is partitioned into one or more
groups of cylinders. These partitions are treated as separate disks. After creating the
partitions the file system is created onto the disk. After these two steps disk can be
used for storing files.
9.3.2 Bad block management
In the disks there are moving parts hence they can fail. More frequently, one or
180 more blocks become defective. Data that stored on these blocks are lost. The
blocks are called bad blocks. There are number of ways to handle bad blocks. Bad Disk Structure
block management schemes are dependent on the type of disk. For example these
schemes for simple disks such as disks with IDE controllers are different than the
SCSI (Small Computer System Interface) disk.
For simple disks during the process of formatting, bad blocks are marked in the NOTES
FAT (File allocation table). For this a special value is written in the corresponding
FAT entry. Because of this special value allocation routines do not use these blocks.
If blocks go bad during normal operation, a special program (such as scandisk) is
used for marking the bad blocks in FAT.
For disks such as SCSI disks, some schemes are described below
(1) Sectors sparing or forwarding – During the formatting, some spare sectors
are maintained. These spare sectors are not visible to operating system. At any
time, when any bad sectors is recognized this bad sector is replaced logically
with one of the spare sectors.
(2) Sectors slipping – Bad sectors are also replaced by sector slipping. For
example if sector 25 is bad and first available spare sector is 195 then sector
slipping remap 195 into the spare, then sector 194 to 195 and then 193 to 194
and so on. Lastly sectors 25 is mapped to 26.
9.4 DISK RELIABILITY
Disk reliability is a major issue in computer world. Because disks have high failure
rates and their failure causes a loss of data and data is valuable for each organization
using computer. Several improvements have been done in disk technology. RAID
(Redundant Array of Independent Disk) is one of them. RAID system is used for
disk reliability. It also improves disk performance. In RAID we use an array of small
and inexpensive disks that is treated just like a Single disk. In this system all disk
drives are controlled by a single controller means there is no need to particular
controller for each disk drives. To be treated like a single disk to the software, all
RAIDs have the property to distribute the data over the drives to allow parallel
operation. There are different organizations possible for doing this work. These
schemes are known as RAID level through RAID level 5.
The basic ideas behind a RAID is to install a box full of disks, typically a large
server replaces the disk controller card with a RAID controller, copy the data into
the RAID and then continue the normal operation. In other words, a RAID should
look like a Single Disk to the operating system.
Figure 9.10 shows all levels of RAID. In RAID level 0 the disks are divided into
strips of k sectors each and sectors 0 to k-1 is strip 0, sector k to 2k-1 as strip
1 and so on. The distribution of data over multiple drives like this is called stripping.
The RAID level 1 duplicates all the disks, so there are four primary disks with four
back-up disks. On a write every strip is written twice in both the disks while on a
read, any one of the either copy can be used. The write performance is not better
but the read is so better. Basic advantage of it is that if a drive crashes the copy
is simply used.
The RAID level 2 works on words instead of strips of sectors and works on
possibly byte basis. It splits each byte of the single virtual disk into a pair of 4-bit
then adding a Hamming code(An Error Correcting Code) to each one, forms a
seven bit word. The bits 1,2 and 4 are parity bits of 7 bit word. These seven drives
were synchronized in terms of arm position and rotational position. Then it is pos- 181
Operating Systems sible to write seven bit hamming coded word over the seven drives, one bit per
drive.
The RAID level 3 is improved version of RAID level 2. In this level single parity
bit is computed for each data and written into a parity drive. As level 2, the drives
NOTES of this level must be exactly synchronized.
The RAID levels 4 and 5 work with strip again, not any individual word with parity.
These levels do not require synchronized drives. The level 4 works same as level
0 with a strip for strip parity written on to as extra drive or parity drive. If any drive
crashes, the lost bytes can be recomputed from the parity drive.
In level 4 there is a single parity drive, the heavy load may cause a bottleneck. This
is eliminated in RAID level 5 by distributing the parity bits uniformly over all the
drives.
9.5 SWAP SPACE MANAGEMENT
Sometime a process is required to bring into main memory but the main memory
does not have the sufficient memory to accommodate that process. In such a case,
a process that is currently in memory and least active is removed from the memory
and stored in the backing store and the process that is to be executed is brought
into the memory for execution. This backing storage is called swap space and the
steps of “removing a process from memory, storing it into backing space and
loading other process into that memory area is called swapping”.
In other words we can say that swapping is needed when the available main
memory to load processes, reaches a critically low point. But in general, none of
the operating systems uses swapping in this manner. Instead, operating systems use
swapping together with virtual memory techniques. They do not swap entire pro-
cess, rather a process is divided into pages and operating system swaps pages
when needed. Swapping of the pages is also called paging.
Since access to the disk memory is slow compared to the access to main memory,
performance of the memory management techniques depend upon how efficiently
swap space is managed. Hence, swap-space management is implemented as low
level functions of the operating system.
Different operating systems utilize swap space in different way, depending on the
memory management algorithm in use. Systems that implement simple swapping
may use swap space to store an entire process image, while paging systems can use
swap space to store pages only, and virtual memory uses swap space in some
different manner. A swap space can range from a few megabytes to gigabytes.
Amount of swap space needed must be carefully decided because if a system runs
out of swap space either the process is aborted or the entire system may crash and
if more memory is allotted than needed, it results in the wastage of disk space. But
wastage of disk space is acceptable instead of system crash. Some systems rec-
ommend that what amount of disk space to be reserved for swap space. For
example, Linux suggests that the swap space should be two times of the physical
memory. Even more in Linux we can create multiple swap space. These swap
spaces are part of the separate disks.
A swap space can reside in one of two places:
1. As a part of the normal file system,
2. It can be in a separate disk partition.
If the swap space is implemented as a large file within the file system, we can use
182
normal file system routines to create and name it, and to allocate space to it. Though
Disk Structure
NOTES
(a) RAID level 0
(b) RAIDlevel 1
(c) RAID level 2
(d) RAID level 3
(e) RAID level 4
(f) RAID level 5
Figure 9.10 RAID level 0 through 5
183
Operating Systems this implementation method is easy, but it is inefficient in many respects.
Moving on the directory and disk takes extra time.
Data structure require to manage disk allocation that takes extra space.
NOTES
Requires multiple seeks in the swapping process because of the external frag-
mentation.
We can overcome from the problem by caching the block location information in
physical memory and by using special tools to allocate physically contiguous blocks
for the swap file. But wastage of time in traversing the file-system data structures
still remains.
In the second approach, swap space is created as a separate raw partition during
disk partitioning. No file system or directory structure is placed in this space.
Operating system has a separate swap space storage manager module to allocate
and deallocate the blocks from the raw partition. This storage manager is coded to
optimize the access speed rather than for efficiently using the swap space. The
reason behind this is that swap space is accessed much more frequently than file
system. Since, more emphasis is on speeding up the access, swap space suffers
from the problem of internal fragmentation. But this problem of internal fragmenta-
tion is acceptable because the life of data in the swap space is generally much
shorter than that of files in the file system. Also every time system boots swap space
is reinitialized, so, this swap space suffers with internal fragmentation problem for
very short time. To add more swap space, repartitioning the disk is done or addi-
tional swap space is added elsewhere. Some operating systems support both the
implementation and leave the decision on the system administrator. For example,
Linux allows the machine’s administrator to decide which type of swapping to use.
Swap Space Management in Solaris
In Solaris, when process executes, text segment pages containing code are brought
in from the file system, accessed in main memory and thrown away if selected for
page out. It is more efficient to read a page from the file system than to write it to
swap space and then read it from there. In Solaris swap space is used only as a
backing store for pages of any type of memory. It includes memory allocated for
the stack, heap and uninitialized data of a process.
Later this mechanism is changed. The biggest changes done in the Solaris is that,
it now allocates swap space only when a page is forcibly removed from physical
memory rather than when the virtual memory page is first created. This scheme gives
better performance on modern computers, which have more physical memory than
older systems and number of paging is less.
9.6 STABLE STORAGE IMPLEMENTATION
Stable storage means a storage unit in which once the data is stored is never lost.
184
To implement such storage, information is stored in two copies and each copy has
independent failure mode. A information store operation can be successful, partial Disk Structure
failure and total failure. In any type of failure, the system should detect it and invokes
a recovery procedure to restore both copies in a consistent state. To do that the
system must maintain two physical blocks for each logical block. During recovery
NOTES
from a failure, each pair of physical blocks is examined. If both are same, no error
is present. If one block contains error then its content is replaced by second block.
This recovery procedure ensures that once the data is stored in stable storage, it is
safe unless a failure destroys all the copies.
SOLVED PROBLEMS
Problem 1. :
Suppose that head of moving hard disk has 200 tracks numbered 0 to 199 is
currently serving a request at 50 track and has just finished a request at track 85.
If the queue of requests is kept in FIFO order.
100, 199, 56, 150, 25, 155, 70, 85
A seek takes 6 msec. per cylinder moved. How much seek time is needed for the
following ?
(i) FCFS (ii) SSTF (iii) SCAN
(i) FCFS - If the disk head is initially at 50, it will first move 50 to 100, then to
199, 56, 150, 25, 155, 70 and finally to 85. This schedule is illustrated in fig.
9.9.
queue = 100, 199, 56, 150, 25, 155, 70, 85
Check Your Progress
3. Define E-scan Sched-
uling?
Fig. 9.11 FCFS Scheduling
4. Name the two places
Total head movement where a swap spare
can reside
= (100-50) + (199-100) + (199-56) + (150-56)
+ (150-25) + (155-25) + (155-70) + (85-70) = 741 Cylinders
A seek takes 6 msec per cylinder moved.
185
Now seek time for 741 cylinder
Operating Systems = 6 ms x 741
= 4.4 sec.
(ii) SSTF Scheduling - In this, the request with the minimum seek time from the
NOTES
current head position is selected first. Since the seek time increases with the
number of cylinders traversed by the head. SSTF chooses the pending request
closest to the current head position. Thus, head first move from 50 to 56, and
then 70, 85, 100, 150, 155, 199 and finally 25.
Queue - 100, 199, 56, 150, 25, 155, 70, 85
Fig. 9.12 SSTF Scheduling
Total head movement = 6 + 14 + 15 + 15 + 50 + 5 + 44 + 174 = 323
This schedule is shown in fig. 9.12. There are total 323 head movement, and
seek time is
6 ms x 323 = 1.938 sec.
(iii) SCAN Scheduling - SCAN operates like SSTF except that it chooses the
request that results in the shortest seek distance in a preferred direction.
queue - 100, 199, 56, 150, 25, 155, 70, 85
head starts at 50
186
Fig. 9.13 SCAN Scheduling
Total head movement = 25 + 25 + 56 + 14 + 15 + 15 + 50 + 5 + 44 = 249 Disk Structure
There are total 249 cylinder moves required to complete the request queue. Scan
schedule is shown in fig. 9.13
Total seek time = 6 ms x 249 NOTES
= 1.494 sec.
ANSWER TO CHECK YOUR PROGRESS
1) The two main component that affect the speed of disk are :
(i) Access time
(ii) Disk bandwidth
2) SCAN Scheduling
In the SCAN algorithm, the arm is moved in one direction only, satisfying all
outstanding requests in route, until it reaches the last cylinder in that direction.
At the other end, the service direction is reversed and servicing continues. This
process continues.
3) C-SCAN Scheduling
The circular scan (C-SCAN) is a form of SCAN scheduling. It works like
SCAN scheduling, except that scanning is done in one direction only. Thus
when the last track has been visited in one direction the arm is returned to the
opposite end of the disk and the scan begins again.
4) A swap space can reside in one of two places:
1. As a part of the normal file system,
2. It can be in a separate disk partition.
EXERCISE
1. Give the Difference between sequential access and direct access.
2. Explain directory implementation methods.
3. Explain stable storage implementation.
4. Explain Linked list and bitmap method for disc space management.
5. Explain disk structure.
6. Explain Swap space management.
7. Give the importance of disk scheduling. Explain CSCAN method.
187
Operating Systems 8. What do you understand by followings
(i) Disk structure
(ii) Disk management
NOTES
(iii) Disk scheduling
(iv) Disk reliability
(v) Stable storage implementation
9. Write short notes on :
(i) FCFS Scheduling
(ii) SSTF Scheduling
188