CHAPTER 11
MASS STORAGE STRUCTURE
Source:
1. Chapter 11 from “Avi Silberschatz, Peter Baer Galvin, and Greg Gagne, “Operating System Concepts”, 10th Edition, John Wiley &
Sons, 2018.”
2. Greg Ganger 2010, “Disk Array Data Organizations and RAID”, [Link]
[Link]
Contents
1. Overview of Mass-Storage Structure
2. HDD Scheduling
3. NVM Scheduling
4. Error Detection and Correction
5. Storage Device Management
6. Swap-Space Management
7. Storage Attachment
8. RAID Structure
(Silberschatz, et al. 2018) 2
Objectives
1. Describe the physical structures of various
secondary storage devices and the effect of a
device’s structure on its uses.
2. Explain the performance characteristics of
mass-storage devices.
3. Evaluate I/O scheduling algorithms.
4. Discuss operating-system services provided for
mass storage, including RAID.
(Silberschatz, et al. 2018) 3
11.2 HDD Scheduling
(Silberschatz, et al. 2018) 13
HDD Scheduling
● The OS is responsible for using hardware efficiently — for the disc drives, this
means having a fast access time* and disc bandwidth*
○ Recall: access time = seek time + rotational latency
(Silberschatz, et al. 2018) 14
● Minimize seek time
○ Recall: seek time → time to move disc arm to desired cylinder
○ Seek time ≈ seek distance**
● Disc 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.
(Silberschatz, et al. 2018) 15
● There are many sources of disc I/O request:
○ OS
○ System processes
○ Users processes
● I/O request includes input or output mode, disc address, memory address,
number of sectors to transfer
(Silberschatz, et al. 2018) 16
● OS maintains queue of requests, per disc or device
● Idle disc can immediately work on I/O request; a busy disc means work must
queue
○ Optimization algorithms only make sense when a queue exists
(Silberschatz, et al. 2018) 17
● Note that drive controllers have small buffers and can manage a queue of I/O
requests (of varying “depth”)
● Several algorithms exist to schedule the servicing of disc I/O requests
● The analysis is true for one or many platters
(Silberschatz, et al. 2018) 18
Example:
We illustrate disc scheduling algorithms:
● a disc queue with requests for I/O to blocks on cylinders (0-199):
98, 183, 37, 122, 14, 124, 65, 67
assume the disc head is initially at cylinder 53.
(Silberschatz, et al. 2018) 19
FCFS / FIFO
Scheduling
● Illustration shows total
head movement of 640
cylinders.
(Silberschatz, et al. 2018)
20
SCAN Scheduling
● The disc arm starts at one end of the disc, and moves toward the other end,
servicing requests until it gets to the other end of the disc, where the head
movement is reversed and servicing continues.*
○ Must know head’s current position and direction of head movement
● SCAN algorithm → sometimes called the elevator algorithm
(Silberschatz, et al. 2018) 21
(Silberschatz, et al. 2018)
22
● Figure 11.7 shows total head movement of 238 cylinders compared to 640 FCFS
● If we assume 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 is
at the other end of the disc. These requests have also waited the longest, so why
not go there first?
(Silberschatz, et al. 2018) 23
C-SCAN Scheduling
● Provides a more uniform wait time than SCAN*
● The head moves from one end of the disc to the other, servicing requests as it
goes. When it reaches the other end, however, it immediately returns to the
beginning of the disc, without servicing any requests on the return trip.
● Treats the cylinders as a circular list that wraps around from the last cylinder
to the first one.
(Silberschatz, et al. 2018) 24
(Silberschatz, et al. 2018)
25
Selecting a Disc-Scheduling Algorithm
● SCAN and C-SCAN perform better for systems that place a heavy load on the disc -
i.e. less starvation
● Performance depends on the number and types of requests*
● The disc-scheduling algorithm should be written as a separate module of the OS,
allowing it to be replaced with a different algorithm if necessary.
(Silberschatz, et al. 2018) 26
● Linux created the deadline scheduler.
○ This scheduler maintains separate read and write queues, and gives reads
priority because processes are more likely to block on read than write.
○ Deadline keeps four queues:
■ two read and two write:
● one sorted by Logical Block Addressing (LBA) - essentially C-SCAN
and
● the other by FCFS
○ The Linux NOOP scheduler uses FCFS policy but modifies it to
merge adjacent requests.
(Silberschatz, et al. 2018) 27