Operating Systems
CS2006
Module 5
I/O management & Disk scheduling
Dr. Abhishek Verma
Computer Science & Engineering
Indian Institute of Information Technology,
Design and Manufacturing
Jabalpur
Credits: A. Silberschatz, P. B. Galvin, and G, Gagne, "Operating System
Concepts", 9th Ed., Wiley, 2018.
Copyright Disclaimer
The slides used in this course are copyrighted by
Silberschatz, Galvin, and Gagne, 2013. As per the copyright
notice, the slides are authorized for personal use and for
use in conjunction with a course for which Operating
System Concepts is the prescribed text. The authors
mentioned that the instructors are free to modify the slides
to their taste as long as the modified slides acknowledge
the source and the fact that they have been modified.
Paper copies of the slides may be sold strictly at the price
of reproduction to students of courses where the book is
the prescribed text. Any use that differs from the above and
any for-profit sale of the slides (in any form) requires the
consent of the copyright owners; contact Avi Silberschatz
(avi@[Link]) to obtain the copyright owners' consent.]
Overview of Mass Storage Structure
Magnetic disks provide bulk of secondary storage of modern
computers
Drives rotate at 60 to 250 times per second
Transfer rate is rate at which data flow between drive and computer
Positioning time (random-access time) is time to move disk arm to
desired cylinder (seek time) and time for desired sector to rotate
under the disk head (rotational latency)
Head crash results from disk head making contact with the disk
surface -- That’s bad
Disks can be removable
Drive attached to computer via I/O bus
Busses vary, including EIDE, ATA, SATA, USB, Fibre Channel,
SCSI, SAS, Firewire
Host controller in computer uses bus to talk to disk controller built
into drive or storage array
Moving-head Disk Mechanism
Disk Scheduling
The operating system is responsible for using hardware
efficiently — for the disk drives, this means having a fast
access time and disk bandwidth
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
Disk Scheduling (Cont.)
There are many sources of disk I/O request
OS
System processes
Users processes
I/O request includes input or output mode, disk address,
memory address, number of sectors to transfer
OS maintains queue of requests, per disk or device
Idle disk can immediately work on I/O request, busy disk
means work must queue
Optimization algorithms only make sense when a queue exists
Disk Scheduling (Cont.)
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 disk
I/O requests
The analysis is true for one or many platters
We illustrate scheduling algorithms with a request queue (0-
199)
98, 183, 37, 122, 14, 124, 65, 67
Head pointer 53
FCFS
Illustration shows total head movement of 640 cylinders
SSTF
Shortest Seek Time First selects the request with the
minimum seek time from the current head position
SSTF scheduling is a form of SJF scheduling; may cause
starvation of some requests
Illustration shows total head movement of 236 cylinders
SCAN
The disk arm starts at one end of the disk, and moves
toward the other end, servicing requests until it gets to the
other end of the disk, where the head movement is
reversed and servicing continues.
SCAN algorithm Sometimes called the elevator
algorithm
Illustration shows total head movement of 236 cylinders
But note that if requests are uniformly dense, largest
density at other end of disk and those wait the longest
SCAN (Cont.)
C-SCAN
Provides a more uniform wait time than SCAN
The head moves from one end of the disk to the other,
servicing requests as it goes
When it reaches the other end, however, it immediately
returns to the beginning of the disk, 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
Total number of cylinders?
C-SCAN (Cont.)
C-LOOK
LOOK a version of SCAN, C-LOOK a version of C-
SCAN
Arm only goes as far as the last request in each
direction, then reverses direction immediately, without
first going all the way to the end of the disk
Total number of cylinders?
C-LOOK (Cont.)