Operati

ng
System
s:
Internal
s and
Design
Principl
es

Chapter 11
I/O Management
and Disk Scheduling
Seventh Edition
By William Stallings

Operating Systems:
Internals and Design Principles
An artifact can be thought of as a meeting point
an interface in todays terms between an
inner environment, the substance and
organization of the artifact itself, and an
outer environment, the surroundings in
which it operates. If the inner environment is
appropriate to the outer environment, or vice
versa, the artifact will serve its intended
purpose.
THE SCIENCES OF THE ARTIFICIAL,
Herbert Simon

External devices that engage in I/O with

computer systems can be grouped into
three categories:

Devices differ in a number of areas:

Three techniques for performing I/O are:

Programmed I/O

Interrupt-driven I/O

the processor issues an I/O command on behalf of a process to an I/O

module; that process then busy waits for the operation to be completed
before proceeding

the processor issues an I/O command on behalf of a process

if non-blocking processor continues to execute instructions from the
process that issued the I/O command
if blocking the next instruction the processor executes is from the
OS, which will put the current process in a blocked state and schedule
another process

Direct Memory Access (DMA)

a DMA module controls the exchange of data between main memory

and an I/O module

Techniques for Performing

I/O

Efficiency

Major effort in I/O design

Important because I/O

operations often form a
bottleneck

Most I/O devices are

extremely slow compared
with main memory and the
processor
The area that has received
the most attention is disk I/O

Generality

Desirable to handle all devices in

a uniform manner

Applies to the way processes view

I/O devices and the way the
operating system manages I/O
devices and operations

Diversity of devices makes it

difficult to achieve true generality

Use a hierarchical, modular

approach to the design of the I/O
function

Functions of the operating system should be separated

according to their complexity, their characteristic time
scale, and their level of abstraction

Leads to an organization of the operating system into a

series of layers

Each layer performs a related subset of the functions

required of the operating system

Layers should be defined so that changes in one layer do

not require changes in other layers

Perform input transfers in advance of requests being made and

perform output transfers some time after the request is made

No
Buffer

Without a buffer, the OS

directly accesses the
device when it needs

Single
Buffer

Operating system
assigns a buffer in
main memory for an
I/O request

Input transfers are made to the system buffer

Reading ahead/anticipated input

is done in the expectation that the block will eventually be

needed

when the transfer is complete, the process moves the block

into user space and immediately requests another block

Generally provides a speedup compared to the lack of

system buffering

Disadvantages:

complicates the logic in the operating system

swapping logic is also affected

Line-at-a-time operation

appropriate for scrollmode terminals (dumb

terminals)
user input is one line at
a time with a carriage
return signaling the end
of a line
output to the terminal is
similarly one line at a
time

Byte-at-a-time operation
used on forms-mode
terminals
when each keystroke is
significant
other peripherals such as
sensors and controllers

Double
Buffer

Use two system buffers

instead of one

A process can transfer data

to or from one buffer while
the operating system
empties or fills the other
buffer

Also known as buffer

swapping

Circular
Buffer

Two or more buffers are

used

Each individual buffer is

one unit in a circular buffer

Used when I/O operation

must keep up with process

Technique that smoothes out peaks in I/O demand

with enough demand eventually all buffers become full and

their advantage is lost

When there is a variety of I/O and process activities to

service, buffering can increase the efficiency of the OS
and the performance of individual processes

Disk
Performan
ce
Parameter
s

The actual details of disk

I/O operation depend on
the:

computer system

operating system

nature of the I/O

channel and disk
controller hardware

When the disk drive is operating, the disk is rotating at constant

speed

To read or write the head must be positioned at the desired

track and at the beginning of the desired sector on that track

Track selection involves moving the head in a movable-head

system or electronically selecting one head on a fixed-head
system

On a movable-head system the time it takes to position the

head at the track is known as seek time

The time it takes for the beginning of the sector to reach the
head is known as rotational delay

The sum of the seek time and the rotational delay equals the
access time

Table 11.2 Comparison of Disk Scheduling Algorithms

First-In, First-Out (FIFO)

Processes in sequential order

Fair to all processes

Approximates random scheduling in

performance if there are many processes
competing for the disk

Table 11.3 Disk Scheduling Algorithms

Control of the scheduling is outside the control of disk

management software

Goal is not to optimize disk utilization but to meet other

objectives

Short batch jobs and interactive jobs are given higher

priority

Provides good interactive response time

Longer jobs may have to wait an excessively long time

A poor policy for database systems

Shortest
Service
Time First
(SSTF)

Select the disk I/O

request that requires the
least movement of the
disk arm from its current
position

Always choose the

minimum seek time

Also known as the elevator algorithm

Arm moves in one direction only

SCAN

satisfies all outstanding requests

until it reaches the last track in that
direction then the direction is
reversed

Favors jobs whose requests are for

tracks nearest to both innermost and
outermost tracks

C-SCAN
(Circular SCAN)

Restricts scanning to one

direction only

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

Segments the disk request queue into subqueues of

length N

Subqueues are processed one at a time, using SCAN

While a queue is being processed new requests must be

added to some other queue

If fewer than N requests are available at the end of a

scan, all of them are processed with the next scan

Uses two subqueues

When a scan begins, all of the requests are in one of the

queues, with the other empty

During scan, all new requests are put into the other
queue

Service of new requests is deferred until all of the old

requests have been processed

Redundant Array of
Independent Disks

Consists of seven levels,

zero through six

Table 11.4 RAID Levels

RAID
Level 0

Not a true RAID because it does

not include redundancy to
improve performance or provide
data protection

User and system data are

distributed across all of the disks
in the array

Logical disk is divided into strips

RAID
Level 1

Redundancy is achieved by the

simple expedient of duplicating all
the data

There is no write penalty

When a drive fails the data may

still be accessed from the second
drive

Principal disadvantage is the cost

RAID
Level 2

Makes use of a parallel access

technique

Data striping is used

Typically a Hamming code is

used

Effective choice in an
environment in which many disk
errors occur

RAID
Level 3

Requires only a single redundant disk,

no matter how large the disk array

Employs parallel access, with data

distributed in small strips

Can achieve very high data transfer

rates

RAID
Level 4

Makes use of an independent access

technique

A bit-by-bit parity strip is calculated

across corresponding strips on each data
disk, and the parity bits are stored in the
corresponding strip on the parity disk

Involves a write penalty when an I/O

write request of small size is performed

RAID
Level 5

Similar to RAID-4 but distributes the

parity bits across all disks

Typical allocation is a round-robin

scheme

Has the characteristic that the loss of

any one disk does not result in data
loss

RAID
Level 6

Two different parity calculations are

carried out and stored in separate
blocks on different disks

Provides extremely high data

availability

Incurs a substantial write penalty

because each write affects two parity
blocks

Cache memory is used to apply to a memory that is smaller and

faster than main memory and that is interposed between main
memory and the processor

Reduces average memory access time by exploiting the principle

of locality

Disk cache is a buffer in main memory for disk sectors

Contains a copy of some of the sectors on the disk

Most commonly used algorithm that deals with the

design issue of replacement strategy

The block that has been in the cache the longest with no
reference to it is replaced

A stack of pointers reference the cache

most recently referenced block is on the top of the stack

when a block is referenced or brought into the cache, it is

placed on the top of the stack

The block that has experienced the fewest references is

replaced

A counter is associated with each block

Counter is incremented each time block is accessed

When replacement is required, the block with the

smallest count is selected

Frequency-Based
Replacement

Frequency-Based
Replacement

LRU
Disk Cache
Performance

UNIX SVR4
I/O

Two types of I/O

Buffered

system buffer
caches

character
queues

Unbuffered

Buffer
Cache

Three lists are

maintained:
free list
device list
driver I/O
queue

Is simply DMA between device and process space

Is always the fastest method for a process to perform I/O

Process is locked in main memory and cannot be swapped

out

I/O device is tied up with the process for the

duration of the transfer making it unavailable
for other processes

Device I/O in UNIX

Very similar to other UNIX implementation

Associates a special file with each I/O device driver

Block, character, and network devices are recognized

Default disk scheduler in Linux 2.4 is the Linux Elevator

Deadlin
e
Schedul
er

Uses three
queues:
incoming
requests
read requests
go to the tail of
a FIFO queue
write requests
go to the tail of
a FIFO queue
Each request has
an expiration time

Elevator and deadline scheduling can be counterproductive

if there are numerous synchronous read requests

Is superimposed on the deadline scheduler

When a read request is dispatched, the anticipatory

scheduler causes the scheduling system to delay

there is a good chance that the application that issued the

last read request will issue another read request to the same
region of the disk

that request will be serviced immediately

otherwise the scheduler resumes using the deadline

scheduling algorithm

For Linux 2.4 and later there is a single unified page

cache for all traffic between disk and main memory

Benefits:

dirty pages can be collected and written out efficiently

pages in the page cache are likely to be referenced again due

to temporal locality

Window
s I/O
Manager

Cache Manager

maps regions of files into

kernel virtual memory
and then relies on the
virtual memory manager
to copy pages to and
from the files on disk

File System Drivers

sends I/O requests to

the software drivers
that manage the
hardware device
adapter

Network Drivers

Windows includes
integrated networking
capabilities and support
for remote file systems
the facilities are
implemented as software
drivers

Hardware Device
Drivers
the source code of
Windows device drivers
is portable across
different processor types

Windows provides five different

techniques for signaling I/O
completion:

Windows supports two sorts of RAID

configurations:

Volume Shadow
Copies

efficient way of making

consistent snapshots of
volumes so they can be
backed up

also useful for archiving

files on a per-volume
basis

implemented by a
software driver that
makes copies of data on
the volume before it is
overwritten

Volume
Encryption

Windows uses
BitLocker to encrypt
entire volumes

more secure than

encrypting individual
files

allows multiple
interlocking layers of
security

I/O architecture is the computer systems interface to the outside world

I/O functions are generally broken up into a number of layers

A key aspect of I/O is the use of buffers that are controlled by I/O utilities
rather than by application processes

Buffering smoothes out the differences between the speeds

The use of buffers also decouples the actual I/O transfer from the
address space of the application process

Disk I/O has the greatest impact on overall system performance

Two of the most widely used approaches are disk scheduling and the disk
cache

A disk cache is a buffer, usually kept in main memory, that functions as a

cache of disk block between disk memory and the rest of main memory