11/15/2017

UNIT 4

Input Output Management

1
 INTRODUCTION
 Humans interact with machines by providing

11/15/2017
information through IO devices.

 Many on-line services are availed through use of

specialized devices like printers, keyboards etc.

 Management of these devices can affect the throughput

of a system.

2
 ISSUES IN I/O MANAGEMENT
 Communication with an IO device is required at the

11/15/2017
following levels:-

- The need for a human to input information and

output from a computer.

- The need for a device to input information and

receive output from a computer.

- The need for computers to communicate over network.

3
 DEVICE SPEEDS
 Character oriented input devices operate with

11/15/2017
speeds of tens of bytes per second.

 Block oriented devices are much faster than

character oriented devices. Also note that they
operate over a much wider range.

Devices communicate bit or byte streams with a

machine using a data bus and a device controller.

4
 A computer system may have to synchronize with

11/15/2017
some other process to communicate.

 So, one process may actually wait at the point of

meet place for the other process to arrive for
communication using synchronization signals.

 The process advances further following the

synchronizing event.

5
 Processes may use signals to communicate events.

11/15/2017
 Processes may wait for asynchronous events to occur.

 Every OS provides a set of mechanisms which may be

like polling, or a programmed data transfer, or an
interrupt mechanism, or even use DMA with cycle
stealing.

6
 IO ORGANIZATION
 Computers employ the four basic modes of IO
operation:-

11/15/2017
 These are:
1. Polling
2. Programmed mode
3. Interrupt mode
4. DMA mode

7
 Polling: Computer interrogates each device in turn to

11/15/2017
determine if it is ready to communicate.

 Polling as a strategy is also used by systems to

interrogate ports on a computer communication network.

8
 11/15/2017
9
POLLING
 11/15/2017
10
POLLING
 PROGRAMMED DATA MODE
Programmed mode :

11/15/2017
 An IO instruction is issued to a device.

 Now the program busy-waits (idles) till the device IO is

completed.

 In other words execution of I/O instruction is in

sequence with other program instructions.

11
PROGRAMMED DATA MODE

11/15/2017
12
 INTERRUPT MODE
 An IO instruction is issued.

11/15/2017
 The program advances without suspension till the device is
actually ready to establish an IO, when the process is
suspended.

 In this mode, an IO instruction is issued and the program

advances without suspension.

 Program suspension happens when the device is actually

ready to establish an IO.

 An Interrupt Service Routine is executed to achieve

13
device IO.
 INTERRUPT MODE
 Process context is stored to help resume computation later

11/15/2017
(from the point of suspension).

 Program resumes execution from where it

was suspended.

14
 INTERRUPT TYPES
 Interrupt processing may require the following contexts :

11/15/2017
Internal Interrupt :
 Source of interrupt is a memory resident process or an
event within a processor (due to divide by zero or attempt
to execute an illegal instruction).

 Some times malfunctions caused by events

like divide by zero are called traps.

 Timer interrupts may also occur as in Real Time

Operating System.
15
 INTERRUPT TYPES
External Interrupts :

11/15/2017
 Source of interrupt is not internal i.e. other than a process
or processor related event.

 Can be caused by a device seeking attention of a

processor.

 IO device interrupting a program that had sought IO

(mentioned earlier) is an external interrupt.

16
 INTERRUPT TYPES
Software Interrupt :

11/15/2017
 Most OSs offer two modes of operation – user mode and
system mode.

 A system call made by a user program will require a

transition from user mode to system mode – this
generates a software interrupt.

17
 INTERRUPT SERVICING
Let us see how an interrupt is serviced :-

11/15/2017
 Suppose program P is executing an instruction i when an
interrupt is raised.

 Assume also an interrupt service routine ISR to be

initiated to service the interrupt.

18
 INTERRUPT SERVICING
 The following steps describe how the interrupt service may
happen :

11/15/2017
1. Suspend the current program P after executing
instruction i.

2. Store address of instruction i+1 in P as return address for

P – PADDRi+1 which is the incremented program counter
value.

This may be stored (RESTORE) in some specific

location or a systems’ data structure or in the code
area of ISR itself. 19
 INTERRUPT SERVICING
3. A branch unconditionally to interrupt service
instructions in ISR happens.

11/15/2017
4. Typically, the last instruction in the service routine ISR
executes a branch indirect from RESTORE. This restores
the program counter a branch indirect instruction from
PADDRi+1

 Thus the suspended program P obtains control of the

processor again.

20
 ISSUES IN HANDLING INTERRUPTS
Detecting an interrupt
 When a processor has an interrupt enable signal up, then

11/15/2017
at the end of an instruction cycle we shall recognize an
interrupt if the interrupt request (IRQ) line is up.
 Once an interrupt is recognized, interrupt service shall be
required.
 Two minor points now arise. One is when is interrupt
enabled. The other is how a device which raises the
interrupt is identified.

21
 ISSUES IN HANDLING INTERRUPTS
When is interrupt enabled
 Sources of interrupt may have assigned priorities.

11/15/2017
 If a higher priority device seeks an interrupt, the lower
priority device may be denied the per-mission to raise an
interrupt.

 Semaphores, cannot be interrupted. Here just processor

may disable interrupt.

22
 IDENTIFICATION OF SOURCE OF INTERRUPTS
We will see how source of interrupt may be identified in the
context of different I/O mechanisms like:

11/15/2017
Polling :
 It interrogates all the devices in sequence

 It is slow if there are many devices.

23
IDENTIFICATION OF SOURCE OF INTERRUPTS

11/15/2017
24
 ISSUES IN HANDLING INTERRUPTS
Interrupt received when a different process is executing.
 Suppose the process Pi initiated an IO. But subsequently it

11/15/2017
relinquishes the processor to process Pj .

 This may well happen because the process Pi may have finished
its time slice or it may have reached a point when it must process
a data expected from the device.

 Now let us suppose that priority of process Pi is higher than that

of Pj. In that case the process Pj shall be suspended and Pi gets
the processor, and the IO is accomplished. Else the process Pj
shall continue and the IO waits till the process.

 Pi is able to get the control of the processor. One other way would
be to let the device interrupt the process Pj but store the IO
information in a temporary buffer (which may be a register) and
proceed. The process Pj continues. 25
 ISSUES IN HANDLING INTERRUPTS
An interrupt during an interrupt service

11/15/2017
 Often devices or processes may have priorities. A lower
priority process or device cannot cause an interrupt while a
higher priority process is being serviced.

 If, however, the process seeking to interrupt is of higher

priority then we need to service the interrupt.

26
 ISSUES IN HANDLING INTERRUPTS
Interrupt Vector (IV)
 Many systems support an interrupt vector (IV).

11/15/2017
 An example with four sources of interrupt. These may be a
trap, a system call, an IO, or an interrupt initiated by a
program. Now we may associate an index value 0 with trap, 1
with system call, 2 with IO device and 3 with the program
interrupt.

 Note that the source of interrupt provides us the index in the

vector. The interrupt service can now be provided as follows:
- Identify the source of interrupt and generate index i.
- Identify the interrupt service routine address by looking
up IVR(i), where IVR stands for the interrupt vector register.
Let this address be ISRi.
- Transfer control to the interrupt service routine by setting
the program counter to
27
 ISRi.
ISSUES IN HANDLING INTERRUPTS

11/15/2017
28
 DMA MODE OF DATA TRANSFER
 This is a mode of data transfer in which IO is performed in large data
blocks.

11/15/2017
 Disks communicate in data blocks of sizes like 512 bytes or 1024
bytes.

 DMA ensures access to main memory without processor intervention

or support. Such independence from processor makes this mode of
transfer extremely efficient.

 When a process initiates a direct memory access (DMA) transfer, its

execution is briefly suspended (using an interrupt) and the starting
address and size of data block are stored in a DMA controller.

 Following the DMA set up, the program resumes from the point of
suspension.

 The device communicates with main memory stealing memory access

29
cycles in competition with other devices and processor.
DMA MODE OF DATA TRANSFER

11/15/2017
30
DMA : Hardware Support
DMA MODE OF DATA TRANSFER

11/15/2017
31

DMA : Direct memory access mode of data transfer.

 IO MODES: SOME OBSERVATIONS
Programmed IO is used for synchronizing information or

11/15/2017

when speed is not critical.

 Interrupt transfer is suited for a small amount of critical

information – no more than tens of bytes.

 DMA is used mostly for block devices.

32
 NETWORK ORIENTED TRAFFIC
 Network oriented traffic can be handled in DMA

11/15/2017
mode.

 Network traffic usually corresponds to getting

information from a disc file at both ends and
network traffic is bursty.

 In
all the above modes, OS makes it look as if
we are doing a read or a write operation on a file.

33
 HARDWARE SOFTWARE INTERFACE
 IO management requires that a proper set-up is created
by an application on computer system with an IO device.

11/15/2017
 An IO operation is a combination of HW and SW
instructions.

 Following the issuance of an IO command, OS kernel

resolves IO commands.

 Then the kernel communicates with individual device

drivers; which in turn communicate with IO devices.

 The application at the top level communicates only with

the kernel. 34
HARDWARE SOFTWARE INTERFACE

11/15/2017
35
 I/O AND THE KERNEL
 Each IO request from an application generates the

11/15/2017
following:-

- Naming or identification of the device to

communicate.

- Providing device independent data to

communicate.

36
 I/O AND THE KERNEL
 Kernel IO subsystem arranges for the following:-

11/15/2017
- Identification of the device driver.
- Allocation of buffers.
- Reporting of errors.
-Tracking the device usage(is the device
free, who is the current user, etc.)

37
 I/O AND THE KERNEL
 Thedevice driver transfers the kernel IO request to set
device controller with the following information:-

11/15/2017
• Identify read/write request.

• Set controller registers for data transfer (Data

count = 0; where to locate data, how much data to
transfer, etc).

• Keep track when the data has been

transferred(when fresh data is to be brought in).
38
 DEVICE DRIVER
 A device driver is a specialized software which is
specifically written to manage communication with an

11/15/2017
identified class of devices.

 The devices of different makes may differ in speed, the sizes

of buffer and the interface characteristics, etc.

 Therefore requires different drivers.

 Device drivers present a uniform interface to the OS.

39
DEVICE DRIVER

11/15/2017
40

Device Driver Interface

 DEVICE DRIVER
 In a general scenario, n applications may communicate
with m devices using a common device driver.

11/15/2017
 In that case the device driver employs a mapping table to
achieve communication with a specific device.

 Drivers may also need to use specific resources (like a

shared bus).

 If more than one resource is required, a device

driver may also use a resource table. Sometimes a device
driver may need to block a certain resource for its exclusive
use by using a semaphore 1. 41
 DEVICE DRIVER
 The device driver methods have device specific functionalities
using standard function calls.

11/15/2017
 Function calls : open(), close(), lseek(), read(), write ()
 These calls may even be transcribed as hd-open(), hd-close(), etc.
to reflect their use in the context of hard-disk operations.

 The user views device communication as if it were a

communication with a file so an arbitrary amount of
data.

 The device driver has to be device specific. It cannot choose an

arbitrary sized data transfer. The driver must manage fixed sizes of
data for each data transfer.

 With n applications communicating with m devices the device

driver methods assume greater levels of complexity in buffer 42
management.
HANDLING INTERRUPT USING DEVICE DRIVER
 Register with listener chain of the driver.

11/15/2017
 Enable the device.

 Interrupt request handling.

 Interrupt acknowledge and interrupt servicing.

 Schedule to complete the communication.

 Generate a wake up signal.

43
 DEVICE DRIVER OPERATION
The figure below shows sequence which the device driver follow to handle interrupt :-

11/15/2017
44
MANAGEMENT BUFFER

11/15/2017
45
 MANAGEMENT OF BUFFERS
 Buffers are usually set up in the main memory or in
caches.

11/15/2017
 Caches are used to obtain enhanced performance.

 Buffers absorb mismatch in the data transfer rates of the

processor or memory on one side and the device on the
other.

46
MANAGEMENT OF BUFFERS

11/15/2017
47
MANAGEMENT OF BUFFERS

11/15/2017
48
MANAGEMENT OF BUFFERS

11/15/2017
49
BUFFERING SCHEMES

11/15/2017
50
 PCI BUS
 Peripheral Controller Interface.

11/15/2017
 System architects recognized the limitations of the internal buses.

 Limitation : bus structure was too closely tied to the system

architecture.

 Microprocessor architecture supports a front end bus (local bus)

and a back end bus ( system bus).

 Front end bus : used for communication with devices like disks,
video & sound cards, network cards & bridge that connect other
buses.

 Back end bus : high speed communication between CPU, main 51

memory & caches.
 11/15/2017
52
PCI BUS
PCI BUS : MODES OF COMMUNICATION
 3 primary modes supported by every PCI bus are :-

11/15/2017
 Burst mode : An address is set up & multiple data sets are
communicated over the bus to the designated address.

 Avoids overheads, by storing the address for

communication.

 Similar to cache bursting for memory transfers.

53
PCI BUS : MODES OF COMMUNICATION
 Bus Master mode : PCI supports direct communication
between two entities connected to the bus.

11/15/2017
 Closest to DMA mode.

 Also referred as 1st party DMA.

 Because here instead of 3rd party sets up communication,

the bus directly offers the connection.

54
PCI BUS : MODES OF COMMUNICATION
 High bandwidth mode : Accelerated with graphics port
(AGP).

11/15/2017
 Useful for streaming IO.

 High bandwidth easily achieved with 64 bit operation.

55
PCI BUS : MODES OF COMMUNICATION
 Point to point mode : PCI express, which operates with

11/15/2017
64 bit data transfers at 66 MHz, may also operate like a
switch for point to point communication.

 Beyond the usual shared bus operations.

 Shared bus operations avoid direct links.

 But point to point mode requires direct links ( not

shared) to be set up between the devices.

56
PCI BUS : MODES OF COMMUNICATION
 Interrupt transfers : PCI bus has internal interrupt control
at 4 levels identified as #A through #D.

11/15/2017
 When used these levels need to be mapped to the IRQ
priorities at four distinct levels.

57
POINTS RELATED TO DEVICE COMMUNICATION
 PCI provisions handshake & acknowledgement signals
for reliable network device communication.

11/15/2017
 ISA continues to be used for serial & parallel port
transfers. Several devices ISA compatibility. Usage of
bus bridge allows PCI to connect to devices.
 Conflicts in communication due to two devices seek to
communicate with same device. But PCI bus has
embedded arbitration logic to resolve conflicts.

58
INFORMATION STORAGE ORGANIZATION ON DISCS

11/15/2017
59
 INFORMATION STORAGE ORGANIZATION ON DISCS

 A disc has several platters each with several rings or

tracks.

11/15/2017
 Rings are divided into sectors where information is
actually stored.

 Sequentially related information is organized into

cylinders.

 Information on different cylinders has to be accessed by

moving the arm – seek latency.
60
 DELAYS IN INFORMATION RETRIEVAL
 Rotational delay is due to the waiting time for a sector in
rotation to come under the read or write head.

11/15/2017
 The motivation for disc scheduling comes from the need
to keep both the delays to a minimum.

 A sector stores a lot of other information in addition to a

block of information.

61
DELAYS IN INFORMATION RETRIEVAL

11/15/2017
62
 SCHEDULING DISK OPERATIONS
 A user communicates with files (program, data, system
utilities etc.) stored on discs. All such communications have

11/15/2017
the following components.

 The IO is to read from, or write into, a disc.

 The starting address for communication in main

memory.

 The amount of information to be communicated.

 The starting address in disc and current status of the transfer.

63
 A SCENARIO FOR INFORMATION RETRIEVAL
 Consider a scenario of one process with one request to access
data; a disc access request leads finally to the cylinder having

11/15/2017
that data.

 When multiple requests are pending on a disc, accessing

information in a certain order becomes essential – disc access
scheduling.
 ‘;

 For example, if there are 200 tracks on each platter, pending

requests may come in the order – 59, 41, 172, 74, 52, 85, 139,
12, 194 and 87.

64
 COMPARISON OF POLICIES
 FCFS Policy : The service is provided strictly in the

11/15/2017
sequence in which the requests arrived.

 The service would be in the sequence :-

59, 41, 172, 74, 52, 85, 139, 12, 194 and 87.

 In order to compare the effect of implementing a certain

policy, we analyze the arm movements – captures the
basic disc activity.

65
COMPARISON OF POLICIES

11/15/2017
66
 COMPARISON OF POLICIES
 Shortest Seek First : Disc access is in the order:

11/15/2017
87, 85, 74, 59, 52, 41, 12, 139, 172, 194.

 Elevator (SCAN) Algorithm : Assume an initial

movement is in a certain direction. Disc access is in the
following order :
139, 172, 194, 87, 85, 74, 59, 41, 12.

67
 COMPARISON OF POLICIES
 Circular Scan : This scan policy is done in one

11/15/2017
direction and wraps around. The disc access will be in
the following order:
139, 172, 174, 12, 41, 52, 59, 74, 85, 87.

 From these graphs we find that FCFS is not a very good

policy; Shortest Seek First and Elevator algorithm seem
to perform well as these have least arm movements.

68
 USB (UNIVERSAL SERIAL BUS) - NEED
 In 1990s, major problem with PCs was difficult in
connections to a variety of devices(mouse, keyboards,

11/15/2017
joysticks for game, modems, printers, scanners, speakers,
mobile phones, web cams, LAN cards etc.

 Each device have its own connectors with a designated

pin configuration to support voltage levels, control
signals & its customized cable etc.

 Also its own IO protocol(for initiating & maintaining

connection) & drivers.

69
 USB (UNIVERSAL SERIAL BUS)
 Offers a common cable & connector configuration (blind
mating) to connect the wide range of devices.

11/15/2017
 Means a slots on PC can be flexibly used.

 The industry reckons a USB interface to be “hot

swappable”- which implies that one can plug-out one
device & plug-in another device in that slot, without
rebooting the PC.

70
 USB : A BRIEF HISTORY
Application’s Speed USB Specifications Some Observations
environment

Interactive i/p as in Low 10- USB 1.1(announced in 95, but Low cost interface for

11/15/2017
games 100 kbps released in 96, popular till human I/F devices like
2000) mouse, keyboards,
joysticks
Bulk transfer for Medium USB 1.1(Intel announced USB Useful when latency is to
data services as 1.5-12 host controller & Philips regularly guaranteed like
required in ISDN, Mbps announced USB audio for in speech & audio.
audio etc isochronous communications
with consumer electronics
devices)

Bulk transfer at high High 50- USB 2.0(announced in Apr Useful for data transfers
speed as required in 480 Mbps 2000) with very low
LANs & video data latency(flash memory
devices, projection
devices)
Bulk transfer at UHS 1-5 USB 3.0 (announced Nov Handles variety of real
71
ultra high speed Gbps 2008) time media data at 500
Mbps or more
USB : CLASSIFICATION OF DEVICES

11/15/2017
72
USB : MODES OF COMMUNICATION

11/15/2017
73
THREE TIER ARCHITECTURE OF USB

11/15/2017
74
THREE TIER ARCHITECTURE OF USB

11/15/2017
75
USB : TIERED STAR NETWORK TOPOLOGY

11/15/2017
76
USB : TIERED STAR NETWORK TOPOLOGY

11/15/2017
77
USB HUB PROVISIONS AS FOLLOWS :

11/15/2017
78