Amity School of Engineering

ASET
&
Technology

CSE-202 OPERATING SYSTEM

Module IV: I/O Systems

 ASET

Operating System

Text Book

• Operating System Concepts : Silberschatz, Abraham and Galvin,

Peter B. and Gagne, Greg , Wiley Publisher

Reference Book
• Operating system: William Stalling , Pearson Education
 ASET

Course Learning Objectives:

• To understand the structure and complexities of an

operating system’s I/O subsystem
• To understand disk scheduling algorithm
• To understand how I/O devices performance can be
enhanced
 Topics Covered ASET

• Overview
• I/O Hardware
• Application I/O Interface
• Kernel I/O Subsystem
• Transforming I/O Requests to Hardware Operations
• STREAMS
• Performance
 Overview
ASET

• I/O management is a major component of operating

system design and operation
– Important aspect of computer operation
– I/O devices vary greatly
– Various methods to control them
– Performance management
– New types of devices frequent
• Ports, busses, device controllers connect to various
devices
• Device drivers encapsulate device details
– Present uniform device-access interface to I/O
subsystem
 I/O Hardware ASET

• Incredible variety of I/O devices

– Storage
– Transmission
– Human-interface

• Common concepts – signals from I/O

devices interface with computer
– Port – connection point for device
– Bus - daisy chain or shared direct access
• PCI bus common in PCs and servers, PCI Express (PCIe)
• expansion bus connects relatively slow devices
– Controller (host adapter) – electronics that operate port, bus, device
• Sometimes integrated
• Sometimes separate circuit board (host adapter)
• Contains processor, microcode, private memory, bus controller, etc
– Some talk to per-device controller with bus controller,
microcode, memory, etc
A Typical PC Bus Structure
ASET
 I/O Hardware (Cont.) ASET

• I/O instructions control devices

• Devices usually have registers where device driver places
commands, addresses, and data to write, or read data from
registers after command execution
– Data-in register, data-out register, status register, control
register
– Typically 1-4 bytes, or FIFO buffer
• Devices have addresses, used by
– Direct I/O instructions
– Memory-mapped I/O
• Device data and command registers mapped to
processor address space
• Especially for large address spaces (graphics)
Device I/O Port Locations on PCs
ASET
 Polling ASET

 For each byte of I/O

1. Read busy bit from status register until 0
2. Host sets read or write bit and if write copies data into data-out
register
3. Host sets command-ready bit
4. Controller sets busy bit, executes transfer
5. Controller clears busy bit, error bit, command-ready bit when
transfer done
 Step 1 is busy-wait cycle to wait for I/O from device
 Reasonable if device is fast
 But inefficient if device slow
 CPU switches to other tasks?
But if miss a cycle data overwritten / lost
 Interrupts ASET

• Polling can happen in 3 instruction cycles

– Read status, logical-and to extract status bit, branch if not
zero
– How to be more efficient if non-zero infrequently?
• CPU Interrupt-request line triggered by I/O device
– Checked by processor after each instruction
• Interrupt handler receives interrupts
– Maskable to ignore or delay some interrupts
• Interrupt vector to dispatch interrupt to correct handler
– Context switch at start and end
– Based on priority
– Some nonmaskable
– Interrupt chaining if more than one device at same interrupt
number
Interrupt-Driven I/O Cycle
ASET
Intel Pentium Processor Event-Vector Table
ASET
 Interrupts (Cont.) ASET

• Interrupt mechanism also used for exceptions

– Terminate process, crash system due to hardware
error
• Page fault executes when memory access error
• System call executes via trap to trigger kernel to
execute request
• Multi-CPU systems can process interrupts concurrently
– If operating system designed to handle it
• Used for time-sensitive processing, frequent, must be
fast
 Direct Memory Access ASET

• Used to avoid programmed I/O (one byte at a time) for large

data movement
• Requires DMA controller
• Bypasses CPU to transfer data directly between I/O device and
memory
• OS writes DMA command block into memory
– Source and destination addresses
– Read or write mode
– Count of bytes
– Writes location of command block to DMA controller
– Bus mastering of DMA controller – grabs bus from CPU
• Cycle stealing from CPU but still much more efficient
– When done, interrupts to signal completion
• Version that is aware of virtual addresses can be even more
efficient - DVMA
Six Step Process to Perform DMA Transfer
ASET
 Application I/O Interface ASET

• I/O system calls encapsulate device behaviors in generic

classes
• Device-driver layer hides differences among I/O controllers from
kernel
• New devices talking already-implemented protocols need no
extra work
• Each OS has its own I/O subsystem structures and device
driver frameworks
• Devices vary in many dimensions
– Character-stream or block
– Sequential or random-access
– Synchronous or asynchronous (or both)
– Sharable or dedicated
– Speed of operation
– read-write, read only, or write only
Characteristics of I/O Devices
ASET
 Characteristics of I/O Devices ASET
(Cont.)
• Subtleties of devices handled by device drivers
• Broadly I/O devices can be grouped by the OS into
– Block I/O
– Character I/O (Stream)
– Memory-mapped file access
– Network sockets
• For direct manipulation of I/O device specific
characteristics, usually an escape / back door
– Unix ioctl() call to send arbitrary bits to a device
control register and data to device data register
 Block and Character Devices ASET

• Block devices include disk drives

– Commands include read, write, seek
– Raw I/O, direct I/O, or file-system access
– Memory-mapped file access possible
• File mapped to virtual memory and clusters
brought via demand paging
– DMA
• Character devices include keyboards, mice, serial
ports
– Commands include get(), put()
– Libraries layered on top allow line editing
 Network Devices ASET

• Varying enough from block and

character to have own interface
• Linux, Unix, Windows and many others
include socket interface
– Separates network protocol from network
operation
– Includes select() functionality
• Approaches vary widely (pipes, FIFOs,
streams, queues, mailboxes)
 Clocks and Timers ASET

• Provide current time, elapsed time, timer

• Normal resolution about 1/60 second
• Some systems provide higher-resolution
timers
• Programmable interval timer used for
timings, periodic interrupts
• ioctl() (on UNIX) covers odd aspects
of I/O such as clocks and timers
 Nonblocking and Asynchronous I/O ASET

• Blocking - process suspended until I/O completed

– Easy to use and understand
– Insufficient for some needs
• Nonblocking - I/O call returns as much as available
– User interface, data copy (buffered I/O)
– Implemented via multi-threading
– Returns quickly with count of bytes read or written
– select() to find if data ready then read() or
write() to transfer
• Asynchronous - process runs while I/O executes
– Difficult to use
– I/O subsystem signals process when I/O completed
Two I/O Methods ASET

Synchronous Asynchronous
 Vectored I/O ASET

• Vectored I/O allows one system call to perform

multiple I/O operations
• For example, Unix readve() accepts a vector of
multiple buffers to read into or write from
• This scatter-gather method better than multiple
individual I/O calls
– Decreases context switching and system call
overhead
– Some versions provide atomicity
• Avoid for example worry about multiple threads
changing data as reads / writes occurring
 Kernel I/O Subsystem ASET

• Scheduling
– Some I/O request ordering via per-device queue
– Some OSs try fairness
– Some implement Quality Of Service (i.e. IPQOS)
• Buffering - store data in memory while transferring between devices
– To cope with device speed mismatch
– To cope with device transfer size mismatch
– To maintain “copy semantics”
– Double buffering – two copies of the data
• Kernel and user
• Varying sizes
• Full / being processed and not-full / being used
• Copy-on-write can be used for efficiency in some cases
Device-status Table ASET
 Kernel I/O Subsystem ASET

• Caching - faster device holding copy of data

– Always just a copy
– Key to performance
– Sometimes combined with buffering
• Spooling - hold output for a device
– If device can serve only one request at a time
– i.e., Printing
• Device reservation - provides exclusive access to
a device
– System calls for allocation and de-allocation
– Watch out for deadlock
 Error Handling ASET

• OS can recover from disk read, device

unavailable, transient write failures
– Retry a read or write, for example
– Some systems more advanced –
Solaris FMA, AIX
• Track error frequencies, stop using
device with increasing frequency of
retry-able errors
• Most return an error number or code
when I/O request fails
• System error logs hold problem reports
 References ASET

• Silberschatz, Abraham and Galvin,

Peter B. and Gagne, Greg,
Operating system Concepts, 9th
Edition
 ASET

Thank You
 Amity School of Engineering &
Technology

CSE-202 OPERATING SYSTEM

Module IV: Disk Scheduling

 Operating System

Text Book

• Operating System Concepts : Silberschatz, Abraham and Galvin,

Peter B. and Gagne, Greg , Wiley Publisher

Reference Book
• Operating system: William Stalling, Pearson Education
Course Learning Objectives:

• To understand how I/O devices performance can be

enhanced
 Topics Covered

• Disk Scheduling Algorithms

– FCFS Scheduling
– Shortest Seek Time First (SSTF)
– SCAN
– SEEK
– C-SCAN
– C-SEEK
– LOOK
– C-LOOK
 HDD 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.)
• In the past, operating system responsible for queue
management, disk drive head scheduling
– Now, built into the storage devices,
controllers
– Just provide Logical Block Addressing
(LBA), handle sorting of requests
• Some of the algorithms they use described
next
 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

Total head movements incurred while servicing these requests

= (98 – 53) + (183 – 98) + (183 – 37) + (122 – 37) + (122 – 14) + (124 – 14) +
(124 – 65) + (67 – 65)

= 45 + 85 + 146 + 85+ 108 + 110 + 59 + 2 = 640

 SSTF
• 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
 SSTF (Cont.)

= (65 – 53) + (67 – 65) + (67 – 37) + (37– 14) + (98 – 14) + (122 – 98)
+ (124 – 122) + (183 – 124)
= 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59
 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
208 cylinders
 SCAN (Cont.)

= (53– 37) + (37 – 14) + (14– 0) + (65 – 0) + (67

– 65) + (98– 67) + (122 – 98)+(124-122)+(183-
124)
= 16 + 23 + 14 + 65+ 2 + 31 + 24 + 2+59
= 236
 Alternatively
Total head movements incurred
while servicing these requests
= ( 53-0) + (183 – 0)
= 53 + 183
= 236
 C-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
C-SCAN (Cont.)
Total head movements incurred while
servicing these requests
= (199 – 53) + (199 – 0)+(37-0)
= 146 + 199+37
= 382
 LOOK and C-LOOK

• Version of SCAN and 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
 Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 41, 122, 14, 124, 65, 67.
The LOOK scheduling algorithm is used. The head is initially at cylinder number 53 moving towards larger cylinder
numbers on its servicing pass. T
he cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while
servicing these requests is _______.

• Total head movements incurred while servicing these requests

• = (65 – 53) + (67 – 65) + (98 – 67) + (122 – 98) + (124 – 122) + (183 – 124) + (183 – 41) + (41 – 14)
• = 12 + 2 + 31 + 24 + 2 + 59 + 142 + 27
• = 299
C-LOOK (Cont.)
 Selecting a Disk-Scheduling Algorithm

• SSTF is common and has a natural appeal

• SCAN and C-SCAN perform better for systems that
place a heavy load on the disk
• Performance depends on the number and types of
requests
• Requests for disk service can be influenced by the file-
allocation method
• The disk-scheduling algorithm should be written as a
separate module of the operating system, allowing it to
be replaced with a different algorithm if necessary
• Either SSTF or LOOK is a reasonable choice for the
default algorithm
 References

• Silberschatz, Abraham and Galvin,

Peter B. and Gagne, Greg,
Operating system Concepts, 9th
Edition
Thank You