I/O MANAGEMENT

COMP6697001-OPERATING SYSTEMS
SESSION 9

SUBJECT MATTER EXPERT

Dr. Zulfany Erlisa Rasjid [Link].,MMSI
SUB TOPICS

- I/O DEVICES
- DESIGN ISSUES
- DISK MANAGEMENT
- RAID CONFIGURATION
- DISK ARM SCHEDULING
- UNIX I/O
- LINUX I/O
- WINDOWS I/O
ACKNOWLEDGEMENT

THESE SLIDES HAVE BEEN ADAPTED FROM:

STALLINGS, W. (2018). OPERATING SYSTEMS:

INTERNALS AND DESIGN PRINCIPLES. 9TH.
ISBN: 978-1-292-21429-0

CHAPTER 11
Learning Objectives

AT THE END OF THIS LECTURE, STUDENTS ARE ABLE TO:

LO1 : DESCRIBE I/O TECHNIQUES

LO2 : EXPLAIN THE CONCEPT OF I/O MANAGEMENT

LO2: EXPLAIN BUFFERING TECHNIQUES

LO3 : COMPARE DIFFERENT I/O IMPLEMENTATION IN THE OPERATING SYSTEMS

LO3: COMPARE DISK SCHEDULING ALGORITHM

LO3: COMPARE RAID SYSTEMS

CATEGORIES OF I/O DEVICES

External devices that engage in I/O with computer systems

can be grouped into three categories:

Human readable

• Suitable for communicating with the computer user

• Printers, terminals, video display, keyboard, mouse

Machine readable

• Suitable for communicating with electronic

equipment
• Disk drives, USB keys, sensors, controllers

Communication

• Suitable for communicating with remote devices

• Modems, digital line drivers

• © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

DIFFERENCE INI/O DEVICES

• Devices differ in a number of areas:

Data Rate
• differences of magnitude between the data transfer rates

Application
• The use to which a device is put has an influence on the software

Complexity of Control
• The effect on the O/Sis filtered by the complexity of the I/O module

Unit of Transfer

• Data may be transferred as a stream of bytes or characters or in larger blocks

Data Representation
• Different data encoding schemes are used by different devices

Error Conditions
• The nature of errors, the way in which they are reported

• © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

I/O DEVICE DATA RATES

• © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

ORGANIZATION OF THE I/O FUNCTION

• Three techniques for performing I/O are:

• Programmed 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
• Interrupt-driven I/O
– 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
DESIGN OBJECTIVES
• Generality
• Efficiency • Desirable to handle all
devices in a uniform
• Major effort in I/O design manner
• Important because I/O
• Applies to the way
operations often form a
bottleneck processes view I/O
devices and the way
• Most I/O devices are
the operating system
extremely slow compared
with main memory and
manages I/O devices
the processor and operations
• The area that has • Diversity of devices
received the most makes it difficult to
attention is disk I/O achieve true generality
• Use a hierarchical,
modular approach to
the design of the I/O
function
© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
I/O ORGANIZATION MODEL

© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

BUFFERING

• To avoid overheads and inefficiencies, it is sometimes convenient to perform

input transfers in advance of requests being made, and to perform output
transfers some time after the request is made

Block-oriented device Stream-oriented device

• Stores information in • Transfers data in and out
blocks that are usually of as a stream of bytes
fixed size • No block structure
• Transfers are made one • Terminals, printers,
block at a time communications ports,
• Possible to reference mouse and other
data by its block number pointing devices, and
• Disks and USB keys are most other devices that
examples are not secondary
storage are examples

© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

NO BUFFER

• Without a buffer, the OS directly accesses the device when it

needs

© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

SINGLE BUFFER

• The simplest type of support that the operating system can provide
• When a user process issues an I/O request, the OS assigns a buffer in the
system portion of main memory to the operation
DOUBLE BUFFER

• Assigning two system buffers to the operation

• A process now transfers data to or from one buffer while the operating
system empties or fills the other buffer

• Also known as buffer swapping

© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

CIRCULAR BUFFER

• When more than two buffers are used, the collection of

buffers is itself referred to as a circular buffer
• Each individual buffer is one unit in the circular buffer
DISK PERFORMANCE PARAMETER

• 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

• © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

DISK PERFORMANCE PARAMETER

• 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

© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

SEEK TIME

• The time required to move the disk arm to the required

track

• Consists of two key components:

• The initial startup time
• The time taken to traverse the tracks that have to
be crossed once the access arm is up to speed
• Settling time
• Time after positioning the head over the target
track until track identification is confirmed
• Much improvement comes from smaller and lighter disk
components
• A typical average seek time on contemporary hard disks is
under 10ms

© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

DISK PERFORMANCE

• Rotational delay
• The time required for the addressed area of
the disk to rotate into a position where it is
accessible by the read/write head
• Disks rotate at speeds ranging from 3,6000
rpm (for handheld devices such as digital
cameras) up to 15,000 rpm
FIRST0IN 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

• © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

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

• © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

SCAN

• Also known as the elevator algorithm

• Arm moves in one direction only
• 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 and favors the latest-arriving jobs
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
N-STEP SCAN

• 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
F-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

• © 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

RAID

• Redundant Array
of Independent RAID is a set of physical disk
drives viewed by the
Disks operating system as a single
logical drive

• Consists of seven
levels, zero
through six Design
architectures
share three
characteristic
s:

Data are distributed

Redundant disk capacity is used
across the physical
to store parity information, which
drives of an array in a
guarantees data recoverability in
scheme known as
case of a disk failure
striping

© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

RAID

• The term was originally coined in a paper by a group of

researchers at the University of California at Berkeley
• The paper outlined various configurations and applications
and introduced the definitions of the RAID levels
• Strategy employs multiple disk drives and distributes data in
such a way as to enable simultaneous access to data from
multiple drives
• Improves I/O performance and allows easier incremental
increases in capacity
• The unique contribution is to address effectively the need for
redundancy
• Makes use of stored parity information that enables the
recovery of data lost due to a disk failure

• © 2017 Pearson Education, Inc., Hoboken, NJ. All rights

reserved.
RAID LEVEL

© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

UNIX BUFFER CACHE

• Is essentially a disk cache

• I/O operations with disk are handled through the buffer cache
• The data transfer between the buffer cache and the user process space always
occurs using DMA
• Does not use up any processor cycles
• Does consume bus cycles
• Three lists are maintained:
»Free list
– List of all slots in the cache that are available for allocation
»Device list
– List of all buffers currently associated with each disk
»Driver I/O queue
– List of buffers that are actually undergoing or waiting for I/O on a particular device

© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 LINUX I/O

• 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

For Linux 2.6 the Elevator algorithm

has been augmented by two
additional algorithms:

• The deadline I/O scheduler

• The anticipatory I/O scheduler

© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

THE ELEVATOR SCHEDULER

• Maintains a single queue for disk read and write requests and
performs both sorting and merging functions on the queue
• When a new request is added to the queue, four operations are
considered in order:
• If the request is to the same on-disk sector or an immediately
adjacent sector to a pending request in the queue, then the
existing request and the new request are merged into one
request
• If a request in the queue is sufficiently old, the new request is
inserted at the tail of the queue
• If there is a suitable location, the new request is inserted in
sorted order
• If there is no suitable location, the new request is placed at the
tail of the queue

© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

DEADLINE SCHEDULER

• Two problems manifest themselves with the elevator scheme:

• A distant block request can be delayed for a substantial time because the
queue is dynamically updated
• A stream of write requests can block a read request for a considerable time,
and thus block a process
• To overcome these problems, a new deadline I/O scheduler was developed in 2002
• This scheduler makes use of two pairs of queues
• In addition to each incoming request being placed in a sorted elevator queue
as before, the same request is placed at the tail of a read FIFO queue for a
read request or a write FIFO queue for a write request
• When a request is satisfied, it is removed from the head of the sorted queue
and also from the appropriate FIFO queue
»However, when the item at the head of one of the FIFO queues becomes
older than its expiration time, then the scheduler next dispatches from
that FIFO queue, taking the expired request, plus the next few requests
from the queue
»As each request is dispatched, it is also removed from the sorted queue
ANTICIPATORY I/O SCHEDULER

• Elevator and deadline scheduling can be

counterproductive if there are numerous synchronous
read requests
• In Linux, the anticipatory scheduler 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
WINDOWS ASYNCHRONOUS AND SYNCHRONOUS I/O

Windows offers two

modes of I/O
operation

Asynchronous Synchronous

An application initiates
Is used whenever
an I/O operation and The application is
possible to optimize
then can continue blocked until the I/O
application
processing while the I/O operation completes
performance
request is fulfilled
I/O COMPLETION

 Windows provides five different techniques for signaling

I/O completion:

1
• Signaling the file object

2
• Signaling an event object

3
• Asynchronous procedure call

4
• I/O completion ports

5
• Polling
WINDOW RAID CONFIGURATION

• Windows supports two sorts of RAID configurations:

Hardware
Software RAID
RAID
Noncontiguous
Separate physical
disk space
disks combined
combined into one
into one or more
or more logical
logical disks by the
partitions by the
disk controller or
fault-tolerant
disk storage
software disk
cabinet hardware
driver, FTDISK
REFERENCES

• Stallings, W. (2014). Operating Systems: Internals and Design Principles.

8th.
ISBN: 978-0-13-380591-8
• Abraham Silberschatz, Peter B. Galvin, Greg Gagne (2018). Operating
System Concepts 10th ed.
ISBN: 978-1-119-32091-3
• A. Tanenbaum and H. Bos (2015), Modern Operating System, 4th
ISBN: 978-0-13-359162-0