Computer

Architecture-Module 3
Owner Alfia M

Subject Computer Architecture Module 3

Topic: I/O Organization

Accessing I/O devices, Interrupts- Enabling and disabling interrupts, Handling multiple
devices, programmed I/O, interrupt driven I/O; Direct Memory Access (DMA)- Bus
arbitration, distributed arbitration.
Accessing I/O Devices
The bus shown in Figure 7.1 below is a simple structure that implements the
interconnection network . Only one source/destination pair of units can use this bus to
transfer data at any one time. The bus consists of three sets of lines used to carry address,
data, and control signals. I/O device interfaces are connected to these lines, as shown in
Figure 7.2 for an input device. Each I/O device is assigned a unique set of addresses for the
registers in its interface.
When the processor places a particular address on the address lines, it is examined by the
address decoders of all devices on the bus. The device that recognizes this address
responds to the commands issued on the control lines. The processor uses the control lines
to request either a Read or a Write operation, and the requested data are transferred over
the data lines.
Figure 7.2 illustrates the hardware required to connect an I/O device to the bus. The address
decoder enables the device to recognize its address when this address appears on the
address lines. The data register holds the data being transferred to or from the processor.
The status register contains information relevant to the operation of the I/O device. Both
the data and status registers are connected to the data bus and assigned unique
addresses. The address decoder, the data and status registers, and the control circuitry
required to coordinate I/O transfers constitute the device’s interface circuit.

I/O devices operate at speeds that are vastly different from that of the processor.
When a human operator is entering characters at a keyboard, the processor is capable of
executing millions of instructions between successive character entries. An instruction
that reads a character from the keyboard should be executed only when a character is
available in the input buffer of the keyboard interface. Also, we must make sure that an
input character is read only once.

For an input device such as a keyboard, a status flag, SIN, is included in the interface circuit
as part of the status register. This flag is set to 1 when a character is entered at the
keyboard and cleared to 0 once this character is read by the processor. Hence, by checking
the SIN flag, the software can ensure that it is always reading valid data. This is often
accomplished in a program loop that repeatedly reads the status register and checks the
state of SIN. When SIN becomes equal to 1, the program reads the input data register. A
similar procedure can be used to control output operations using an output status flag,
SOUT.
Memory Mapped I/O

In a computer system, Memory-Mapped I/O (MMIO) is a method where I/O devices are
treated as if they are part of the system’s memory. This means that the same address space
is shared by both memory and I/O devices.The CPU uses normal memory instructions
(LOAD, STORE) to access hardware devices. It is used in most computers. With memory-
mapped I/O, any machine instruction that can access memory can be used to transfer data
to or from an I/O device.
For example, if DATAIN is the address of a register in an input device, the instruction
Load R2, DATAIN reads the data from the DATAIN register and loads them into processor
register R2. Similarly, the instruction Store R2, DATAOUT sends the contents of register R2
to location DATAOUT, which is a register in an output device.

Programmed I/O

Programmed I/O is one of the techniques used for data transfer between the CPU and I/O
devices (like keyboard, monitor, printer, etc.).
The CPU issues a command to the I/O device (e.g., "read" or "write").The CPU then
continuously checks the status register of the device to see whether it is ready to send or
receive data.This is called polling.Once the device is ready:If it’s a read operation → data is
transferred from the device to the CPU.If it’s a write operation → data is transferred from the
CPU to the device. The CPU controls the entire transfer process.

Advantages

Easy to design and implement.

Useful for simple, low-speed I/O devices.
No complex hardware required.

Disadvantages

CPU Wastage: CPU spends a lot of time checking device readiness (polling).
Slow performance: Device speed is usually much slower than CPU, so CPU remains idle.
Not efficient for high-speed or large-volume data transfers.
Interrupts

As discussed above , the program enters a wait loop in which it repeatedly tests the device
status. During this period, the processor is not performing any useful computation. There
are many situations where other tasks can be performed while waiting for an I/O device to
become ready. To allow this to happen, we can arrange for the I/O device to alert the
processor when it becomes ready. It can do so by sending a hardware signal called an
interrupt request to the processor. Since the processor is no longer required to
continuously poll the status of I/O devices, it can use the waiting period to perform other
useful tasks. Indeed, by using interrupts, such waiting periods can ideally be eliminated.

Example:
Consider a task that requires continuous extensive computations to be performed and the
results to be displayed on a display device. The displayed results must be updated every
ten seconds.
The task can be implemented with a program that consists of two routines, COMPUTE and
DISPLAY. The processor continuously executes the COMPUTE routine. When it receives an
interrupt request from the timer, it suspends the execution of the COMPUTE routine and
executes the DISPLAY routine which sends the latest results to the display device. Upon
completion of the DISPLAY routine, the processor resumes the execution of the COMPUTE
routine. Since the time needed to send the results to the display device is very small
compared to the ten-second interval, the processor in effect spends almost all of its time
executing the COMPUTE routine.
This example illustrates the concept of interrupts. The routine executed in response to an
interrupt request is called the interrupt-service routine, which is the DISPLAY routine in our
example. Assume that an interrupt request arrives during execution of instruction i in
Figure 3.6. The processor first completes execution of instruction i. Then, it loads the
program counter with the address of the first instruction of the interrupt-service routine.

For the time being, let us assume that this address is hardwired in the processor. After
execution of the interrupt-service routine, the processor returns to instruction i + 1.
Therefore, when an interrupt occurs, the current contents of the PC, which point to
instruction i + 1, must be put in temporary storage in a known location. A Return-from-
interrupt instruction at the end of the interrupt-service routine reloads the PC from that
temporary storage location, causing execution to resume at instruction i + 1. The return
address must be saved either in a designated general-purpose register or on the processor
stack.
We should note that as part of handling interrupts, the processor must inform the device
that its request has been recognized so that it may remove its interrupt-request signal.
This can be accomplished by means of a special control signal, called interrupt
acknowledge, which is sent to the device through the interconnection network.

Before starting execution of the interrupt service routine, status information and contents
of processor registers that may be altered in unanticipated ways during the execution of
that routine must be saved. This saved information must be restored before execution of
the interrupted program is resumed. In this way, the original program can continue
execution without being affected in any way by the interruption, except for the time delay.
The task of saving and restoring information can be done automatically by the processor
or by program instructions. Most modern processors save only the minimum amount of
information needed to maintain the integrity of program execution. This is because the
process of saving and restoring registers involves memory transfers that increase the total
execution time, and hence represent execution overhead. Saving registers also increases
the delay between the time an interrupt request is received and the start of execution of
the interrupt-service routine. This delay is called interrupt latency. In some applications, a
long interrupt latency is unacceptable. For these reasons, the amount of information saved
automatically by the processor when an interrupt request is accepted should be kept to a
minimum.

Interrupt Hardware

We pointed out that an I/O device requests an interrupt by activating a bus line called
interrupt-request. Most computers are likely to have several I/O devices that can request
an interrupt. A single interrupt-request line may be used to serve n devices as depicted in
Figure 4.6. All devices are connected to the line via switches to ground. To request an
interrupt, a device closes its associated switch. Thus, if all interrupt-request signals INTR₁
to INTRₙ are inactive, that is, if all switches are open, the voltage on the interrupt-request
line will be equal to Vdd.
This is the inactive state of the line. When a device requests an interrupt by closing its
switch, the voltage on the line drops to 0, causing the interrupt-request signal, INTR,
received by the processor to go to 1. Since the closing of one or more switches will cause
the line voltage to drop to 0, the value of control line still remains low and the processor will
get a high value.
It is customary to use the complemented form, (INTR)’, to name the interrupt-request signal
on the common line, because this signal is active when in the low-voltage state. Resistor R
is called a pull-up resistor because it pulls the line voltage up to the high-voltage state
when the switches are open.

Enabling and Disabling Interrupts

The facilities provided in a computer must give the programmer complete control over the
events that take place during program execution. The arrival of an interrupt request from
an external device causes the processor to suspend the execution of one program and start
the execution of another. Because interrupts can arrive at any time, they may alter the
sequence of events from that envisaged by the programmer. Hence, the interruption of
program execution must be carefully controlled. A fundamental facility found in all
computers is the ability to enable and disable such interruptions as desired.

There are many situations in which the processor should ignore interrupt requests. For
example, in the case of the Compute-Print program of Figure 4.5, an interrupt request from
the printer should be accepted only if there are output lines to be printed. After printing the
last line of a set of n lines, interrupts should be disabled until another set becomes available
for printing.

Let us consider in detail the specific case of a single interrupt request from one
device.When a device activates the interrupt-request signal, it keeps this signal activated
until it learns that the processor has accepted its request. This means that the interrupt
request signal will be active during execution of the interrupt-service routine, perhaps until
an instruction is reached that accesses the device in question.

It is essential to ensure that this active request signal does not lead to successive
interruptions, causing the system to enter an infinite loop from which it cannot recover.
Several mechanisms are available to solve this problem. We will describe three possibilities
here; other schemes that can handle more than one interrupting device will be presented
later.
1st method

The first possibility is to have the processor hardware ignore the interrupt-request line until
the execution of the first instruction of the interrupt-service routine has been completed.
Then, by using an Interrupt-disable instruction as the first instruction in the interrupt-
service routine, the programmer can ensure that no further interruptions will occur until an
Interrupt-enable instruction is executed. Typically, the Interruptenable instruction will be
the last instruction in the interrupt-service routine before the Return-from-interrupt
instruction. The processor must guarantee that execution of the Return-from-interrupt
instruction is completed before further interruption can occur.

2nd method

The second option, which is suitable for a simple processor with only one interrupt- request
line, is to have the processor automatically disable interrupts before starting the execution
of the interrupt-service routine. After saving the contents of the PC and the processor
status register (PS) on the stack, the processor performs the equivalent of executing an
Interrupt-disable instruction. It is often the case that one bit in the PS register, called
Interrupt-enable, indicates whether interrupts are enabled. An interrupt request received
while this bit is equal to 1 will be accepted. After saving the contents of the PS on the stack,
with the Interrupt-enable bit equal to 1, the processor clears the Interrupt-enable bit in its
PS register, thus disabling further interrupts. When a Return-from-interrupt instruction is
executed, the contents of the PS are restored from the stack, setting the Interrupt-enable
bit back to 1. Hence, interrupts are again enabled.

3rd method

In the third option, the processor has a special interrupt-request line for which the
interrupt-handling circuit responds only to the leading edge of the signal. Such a line is said
to be edge-triggered. In this case, the processor will receive only one request, regardless
of how long the line is activated. Hence, there is no danger of multiple interruptions and no
need to explicitly disable interrupt requests from this line.
Handling Multiple Devices
Let us now consider the situation where a number of devices capable of initiating interrupts
are connected to the processor. Because these devices are operationally independent,
there is no definite order in which they will generate interrupts. For example, device X may
request an interrupt while an interrupt caused by device Y is being serviced, or several
devices may request interrupts at exactly the same time.

When a request is received over the common interrupt-request line in Figure 4.6, additional
information is needed to identify the particular device that activated the line. Furthermore,
if two devices have activated the line at the same time, it must be possible to break the tie
and select one of the two requests for service. When the interruptservice routine for the
selected device has been completed, the second request can be serviced.

The information needed to determine whether a device is requesting an interrupt is

available in its status register. When a device raises an interrupt request, it sets to 1 one of
the bits in its status register, which we will call the IRQ bit. The simplest way to identify the
interrupting device is to have the interrupt-service routine poll all the I/O devices
connected to the bus. The first device encountered with its IRQ bit set is the device that
should be serviced. An appropriate subroutine is called to provide the requested service.
The polling scheme is easy to implement. Its main disadvantage is the time spent
interrogating the IRQ bits of all the devices that may not be requesting any service. An
alternative approach is to use vectored interrupts, which we describe next.

Vectored Interrupts

To reduce the time involved in the polling process, a device requesting an interrupt may
identify itself directly to the processor. Then, the processor can immediately start
executing the corresponding interrupt-service routine. The term vectored interrupts refers
to all interrupt-handling schemes based on this approach. A device requesting an interrupt
can identify itself by sending a special code to the processor over the bus. This enables the
processor to identify individual devices even if they share a single interrupt-request line.

In most computers, I/O devices send the interrupt-vector code over the data bus, using the
bus control signals to ensure that devices do not interfere with each other. When a device
sends an interrupt request, the processor may not be ready to receive the interrupt-vector
code immediately. For example, it must first complete the execution of the current
instruction, which may require the use ofthe bus. There may be further delays if interrupts
happen to be disabled at the time the request is raised. The interrupting device must wait
to put data on the bus only when the processor is ready to receive it. When the processor
is ready to receive the interrupt-vector code, it activates the interrupt-acknowledge line,
INTA. The I/O device responds by sending its interruptvector code and turning off the INTR
signal.

Interrupt Nesting

We suggested earlier the interrupts should be disabled during the exесиtion of an interrupt-
service routine, to ensure that a request from one device will not cause more than one
interruption. The same arrangement is often used when several devices are involved, in
which case execution of a given interrupt-service routine, once started, always continues
to completion before the processor accepts an interrupt request from a second device.
Interrupt-service routines are typically short, and the delay they may cause is acceptable
for most simple devices.
For some devices, however, a long delay in responding to an interrupt request may lead to
erroneous operation.other device. This suggests that I/O devices should be organized in a
priority structure. An interrupt request from a high-priority device should be accepted
while the processor is servicing another request from a lower-priority device.

A multiple-level priority organization means that during execution of an interrupt service

routine, interrupt requests will be accepted from some devices but not from others,
depending upon the device's priority. To implement this scheme, we can assign a priority
level to the processor that can be changed under program control. The priority level of the
processor is the priority of the program that is currently being executed. The processor
accepts interrupts only from devices that have priorities higher than its own. At the time
the execution of an interrupt-service routine for some device is started, the priority of the
processor is raised to that of the device. This action disables interrupts from devices at the
same level of priority or lower. However, interrupt requests from higher-priority devices will
continue to be accepted.

A multiple-priority scheme can be implemented easily by using separate interrupt request

and interrupt-acknowledge lines for each device, as shown in Figure 4.7. Each of the
interrupt-request lines is assigned a different priority level. Interrupt requests received
over these lines are sent to a priority arbitration circuit in the processor. A request is
accepted only if it has a higher priority level than that currently assigned to the processor.
Simultaneous Requests

Let us now consider the problem of simultaneous arrivals of interrupt requests from two or
more devices. The processor must have some means of deciding which request to service
first. Using a priority scheme such as that of Figure 4.7, the solution is straightforward. The
processor simply accepts the request having the highest priority. If several devices share
one interrupt-request line, as in Figure 4.6, some other mechanism is needed. Polling the
status registers of the I/O devices is the simplest such mechanism. In this case, priority is
determined by the order in which the devices are polled. When vectored interrupts are used,
we must ensure that only one device is selected to send its interrupt vector code.
A widely used scheme is to connect the devices to form a daisy chain, as shown in Figure
4.8a. The interrupt-request line (INTR)’ is common to all devices. The interrupt-
acknowledge line, INTA, is connected in a daisy-chain fashion, such that the INTA signal
propagates serially through the devices. When several devices raise an interrupt request
and the (INTR)’ line is activated, the processor responds by setting the INTA line to 1. This
signal is received by device 1. Device 1 passes the signal on to device 2 only if it does not
require any service. If device 1 has a pending request for interrupt, it blocks the INTA signal
and proceeds to put its identifying code on the data lines. Therefore, in the daisy-chain
arrangement, the device that is electrically closest to the processor has the highest priority.
The second device along the chain has second highest priority, and so on. The scheme in
Figure 4.8a requires considerably fewer wires than the individual connections in Figure 4.7.
The main advantage of the scheme in Figure 4.7 is that it allows the processor to accept
interrupt requests from some devices but not from others, depending upon their priorities.
The two schemes may be combined to produce the more general structure in Figure 4.8b.
Devices are organized in groups, and each group is connected at a different priority level.
Within a group, devices are connected in a daisy chain. This organization is used in many
computer systems.
Difference Between Programmed I/O and Interrupt Initiated
I/O

Programmed I/O Interrupt Initiated I/O

Data transfer is initiated by the means of The I/O transfer is initiated by the interrupt
instructions stored in the computer command issued to the CPU.
program. Whenever there is a request for
I/O transfer the instructions are executed
from the program.

The CPU stays in the loop to know if the There is no need for the CPU to stay in the
device is ready for transfer and has to loop as the interrupt command interrupts
continuously monitor the peripheral the CPU when the device is ready for data
device. transfer.

This leads to the wastage of CPU cycles The CPU cycles are not wasted as CPU
as CPU remains busy needlessly and thus continues with other work during this time
the efficiency of the system gets and hence this method is more efficient.
reduced.

The CPU cannot do any work until the CPU can do any other work until it is
transfer is complete as it has to stay in the interrupted by the command indicating the
loop to continuously monitor the readiness of device for data transfer
peripheral device.

Its module is treated as a slow module. Its module is faster than programmed I/O
modules.

It is quite easy to program and It can be tricky and complicated to

understand. understand if one uses low level language.

The performance of the system is The performance of the system is

severely degraded. enhanced to some extent.
Direct Memory Access

An instruction to transfer input or output data is executed only after the processor
determines that the 1/O device is ready. To do this, the processor either polls a status flag
in the device interface or waits for the device to send an interrupt request. In either case,
considerable overhead is incurred, because several program instructions must be executed
for each data word transferred. In addition to polling the status register of the device,
instructions are needed for incrementing the memory address and keeping track of the
word count. When interrupts are used, there is the additional overhead associated with
saving and restoring the program counter and other state information.

To transfer large blocks of data at high speed, an alternative approach is used. A special
control unit may be provided to allow transfer of a block of data directly between an
external device and the main memory, without continuous intervention by the processor.
This approach is called direct memory access, or DMА.processor. This approach is called
direct memory access, or DMА. DMA transfers are performed by a control circuit that is part
of the I/O device interface. We refer to this circuit as a DMA controller. The DMA controller
performs the functions that would normally be carried out by the processor when
accessing the main memory.

Although a DMA controller can transfer data without intervention by the processor, its
operation must be under the control of a program executed by the processor. To initiate
the transfer of a block of words, the processor sends the starting address, the number of
words in the block, and the direction of the transfer. On receiving this information, the DMA
controller proceeds to perform the requested operation.When the entire block has been
transferred, the controller informs the processor by raising an interrupt signal. While a DMA
transfer is taking place, the program that requested the transfer cannot continue, and the
processor can be used to execute another program. After the DMA transfer is completed,
the processor can return to the program that requested the transfer.

Thus, for an I/O operation involving DMA, the OS puts the program that requested the
transfer in the Blocked state (see Section 4.2.6), initiates the DMA operation, and starts the
execution of another program. When the transfer is completed, the DMA controller informs
the processor by sending an interrupt request. In response, the OS puts the suspended
program in the Runnable state so that it can be selected by the scheduler to continue
execution.

Figure 4.18 shows an example of the DMA controller registers that are accessed by the
processor to initiate transfer operations. Two registers are used for storing the starting
address and the word count. The third register contains status and control flags. The R/W
bit determines the direction of the transfer. When this bit is set to 1 by a program
instruction, the controller performs a read operation, that is, it transfers data from the
memory to the I/O device. Otherwise, it performs a write operation.When the controller has
completed transferring a block of data and is ready to receive another command, it sets the
Done flag to 1. Bit 30 is the Interrupt-enable flag, IE. When this flag is set to 1, it causes the
controller to raise an interrupt after it has completed transferring a block of data. Finally,
the controller sets the IRQ bit to 1 when it has requested an interrupt.

Bus Arbitration

When multiple devices (CPUs, DMA controllers, I/O devices) share a common system bus,
only one device can use the bus at a time.Bus arbitration is the process of deciding which
device gets control of the bus when more than one device requests it simultaneously.

The device that is allowed to initiate data transfers on the bus at any given time is called
the bus master. When the current master relinquishes control of the bus, another device
can acquire this status. Bus arbitration is the process by which the next device to become
the bus master is selected and bus mastership is transferred to it. The selection of the bus
master must take into account the needs of various devices by establishing a priority
system for gaining access to the bus.

There are two approaches to bus arbitration: centralized and distributed. In centralized
arbitration, a single bus arbiter performs the required arbitration. In distributed arbitration,
all devices participate in the selection of the next bus master.

Centralized Arbitration

Centralized arbitration is a bus control technique in which a single, dedicated arbiter (bus
controller) manages all requests from devices wanting to use the bus. It is the most
common form of bus arbitration because it is simple, fast, and easy to implement.
Figure 4.20 illustrates a basic arrangement in which the processor contains the bus
arbitration circuitry. In this case, the processor is normally the bus master unless it grants
bus mastership to one of the DMA controllers. A DMA controller indicates that it needs to
become the bus master by activating the Bus-Request line, BR. The signal on the Bus-
Request line is the logical OR of the bus requests from all the devices connected to it.

When Bus-Request is activated, the processor activates the Bus-Grant signal, BG1,
indicating to the DMA controllers that they may use the bus when it becomes free. This
signal is connected to all DMA controllers using a daisy-chain arrangement. Thus, if DMA
controller 1 is requesting the bus, it blocks the propagation of the grant signal to other
devices. Otherwise, it passes the grant downstream by asserting BG2. The current bus
master indicates to all devices that it is using the bus by activating another open-collector
line called BusBusy, BBSY. Hence, after receiving the Bus-Grant signal, a DMA controller
waits for Bus-Busy to become inactive, then assumes mastership of the bus. At this time,
it activates Bus-Busy to prevent other devices from using the bus at the same time.

Distributed Arbitration

Distributed arbitration means that all devices waiting to use the bus have equal
responsibility in carrying out the arbitration process, without using a central arbiter. A
simple method for distributed arbitration is illustrated in Figure 4.22. Each device on the
bus is assigned a 4-bit identification number. When one or more devices request the bus,
they assert the Start-Arbitration signal and place their 4-bit ID numbers on four open-
collector lines, ARBO through ARB3. A winner is selected as a result of the interaction
among the signals transmitted over these lines by all contenders. The net outcome is that
the code on the four lines represents the request that has the highest ID number.

Assume that two devices, A and B, having ID numbers 5 and 6, respectively, are requesting
the use of the bus. Device A transmits the pattern 0101, and device B transmits the
pattern0110. The code seen by both devices is0111. Each device compares the pattern on
the arbitration lines to its own ID, starting from the most significant bit. If it detects a
difference at any bit position, it disables its drivers at that bit position and for all lower-
order bits.

It does so by placing a 0 at the input of these drivers. In the case of our example, device A
detects a difference on line (ARB1)’. Hence, it disables its drivers on lines (ARB1)’ and
(ARBO)’. This causes the pattern on the arbitration lines to change to 0110, which means
that B has won the contention. Note that, since the code on the priority lines is 0111 for a
short period, device B may temporarily disable its driver on line (ARBO)’. However, it will
enable this driver again once it sees a 0 on line (ARBI)’ resulting from the action by device
A.