Module 4: Input output organization

Part A: Input output organization

Introduction

• One of the basic features of a computer is its ability to exchange data with other devices.
o Enables a human operator to use a keyboard and a display screen to process text and graphics.
• Computers are an integral part of home appliances, manufacturing equipment, transportation systems,
banking and point-of-sale terminals.
o Input to a computer may come from a sensor switch, a digital camera, a microphone, or a fire alarm.
o Output may be a sound signal to be sent to a speaker or a digitally coded command to change the
speed of a motor, open a valve, or cause a robot to move in a specified manner.
• In short, a general-purpose computer should have the ability to exchange information with a wide
range of devices in varying environments.

1. With a neat diagram, explain the concept of accessing I/O devices.

Accessing I/O devices

• A simple arrangement to connect I/O devices to a computer is to use a single bus arrangement.
• The bus enables all the devices connected to it to exchange information.
• It consists of three sets of lines used to carry address, data, and control signals.
• Each I/O device is assigned a unique set of addresses.

• To access an I/O device, the processor places the address on the address lines.

• The device recognizes the address, and responds to the control signals.
• The processor requests either a read or a write operation, and the requested data are transferred over
the data lines.

• When I/O devices and the memory share the same address space, the arrangement is called
memory-mapped I/O.
• Any machine instruction that can access memory can be used to transfer data to or from an I/O

Divyashree G Page 1
 Module 4: Input output organization

device.
• Simpler software.
• For example,
o Move DATAIN,R0
o Move R0,DATAOUT

• When I/O devices and the memory have different address spaces, the arrangement is called I/O-
mapped I/O.
• Special In and Out instructions to perform I/O transfers.
• I/O devices may have to deal with fewer address lines.
• I/O address lines need not be physically separate from memory address lines.
• In fact, address lines may be shared between I/O devices and memory, with a control signal to
indicate whether it is a memory address or an I/O address.

• Address decoder enables the device to recognize its address when this address appears on the
address lines.
• 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.
• Data and status registers are connected to the data bus, and have unique addresses.
• I/O interface circuit coordinates I/O transfers.
• Recall that the rate of transfer to and from I/O devices is slower than the speed of the processor.
o This creates the need for mechanisms to synchronize data transfers between them.
• To review the basic concepts, let us consider a simple example of I/O operations involving a

Divyashree G Page 2
 Module 4: Input output organization

keyboard and a display device in a computer system.

• The four registers shown in Figure 4.3 are used in the data transfer operations.
• Register STATUS contains two control flags, SIN and SOUT, which provide status information for
the keyboard and the display unit, respectively.
• The two flags KIRQ and DIRQ in this register are used in conjunction with interrupts.
• The KEN and DEN bits are in register CONTROL.
• Data from the keyboard are made available in the DATAIN register, and data sent to the display are
stored in the DATAOUT register.

• This program reads a line of characters from the keyboard and stores it in a memory buffer starting
at location LINE.
• Then, it calls a subroutine PROCESS to process the input line.
• As each character is read, it is echoed back to the display.
• Register R0 is used as a pointer to the memory buffer area.
• The contents of R0 are updated using the Auto increment addressing mode so that successive
characters are stored in successive memory locations.
• Each character is checked to see if it is the Carriage Return (CR) character, which has the ASCII
code 0D (hex).
o If it is, a Line Feed character (ASCII code 0A) is sent to move the cursor one line down on the
display and subroutine PROCESS is called.

Divyashree G Page 3
 Module 4: Input output organization

o Otherwise, the program loops back to wait for another character from the keyboard.

• Program-controlled I/O
o Processor repeatedly monitors a status flag to achieve the necessary synchronization.
o Processor polls the I/O device.
• Two other mechanisms used for synchronizing data transfers between the processor and memory:
o Interrupts
▪ Synchronization is achieved by having the I/0 device send a special signal over the bus whenever it
is ready for a data transfer operation.
o Direct Memory Access
▪ Used for high-speed I/0 devices.
▪ It involves having the device interface transfer data directly to or from the memory, without
continuous involvement by the processor.
5. What are interrupts? Explain the operation of interrupt with the help of a hardware

Interrupts

• In program-controlled I/O, when the processor continuously monitors the status of the device, it
does not perform any useful tasks.
• An alternate approach would be for the I/O device to alert the processor when it becomes ready.
o Do so by sending a hardware signal called an interrupt to the processor.
o At least one of the bus control lines, called an interrupt-request line is dedicated for this purpose.
• Processor can perform other useful tasks while it is waiting for the device to be ready.

Divyashree G Page 4
 Module 4: Input output organization

• Processor is executing the instruction located at address i when an interrupt occurs.

• Routine executed in response to an interrupt request is called the interrupt-service routine.
• When an interrupt occurs, control must be transferred to the interrupt service routine.
• But before transferring control, the current contents of the PC (i+1), must be saved in a known
location.
• This will enable the return-from-interrupt instruction to resume execution at i+1.
• Return address, or the contents of the PC are usually stored on the processor stack.
• Example.
• Consider a task that requires some computations to be performed and the results to be printed on a
line printer.
• Let the program consist of two routines, COMPUTE and PRINT.
• Assume that COMPUTE produces a set of n lines of output, to be printed by the PRINT routine.
• First, the COMPUTE routine is executed to produce the first n lines of output.
• Then, the PRINT routine is executed to send the first line of text to the printer.
• At this point, instead of waiting for the line to be printed; the PRINT routine may be temporarily
suspended and execution of the COMPUTE routine continued.
• Whenever the printer becomes ready, it alerts the processor by sending an interrupt-request signal.
• In response, the processor interrupts execution of the COMPUTE routine and transfers control to
the PRINT routine.
• The PRINT routine sends the second line to the printer and is again suspended.
• Then the interrupted COMPUTE routine resumes execution at the point of interruption.

Divyashree G Page 5
 Module 4: Input output organization

• This process continues until all n lines have been printed and the PRINT routine ends.
• The PRINT routine will be restarted whenever the next set of n lines is available for printing.
• If COMPUTE takes longer to generate n lines than the time required to print them, the processor
will be performing useful computations all th

• When a processor receives an interrupt-request, it must branch to the interrupt service routine.
• It must also inform the device that it has recognized the interrupt request.
• This can be accomplished in two ways:
o Some processors have an explicit interrupt- acknowledge signal for this purpose.
o In other cases, the data transfer that takes place between the device and the processor can be used to
inform the device.
o Treatment of an interrupt-service routine is very similar to that of a subroutine.
• However there are significant differences:
o A subroutine performs a task that is required by the calling program.
o Interrupt-service routine may not have anything in common with the program it interrupts.
o Interrupt-service routine and the program that it interrupts may belong to different users.
o As a result, before branching to the interrupt-service routine, not only the PC, but other information
such as condition code flags, and processor registers used by both the interrupted program and the
interrupt service routine must be stored.
▪ This will enable the interrupted program to resume execution upon return from interrupt service
routine.
▪ Saving and restoring information can be done automatically by the processor or explicitly by
program instructions.
• Saving and restoring registers involves memory transfers:
o Increases the total execution time.

Divyashree G Page 6
 Module 4: Input output organization

o 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 order to reduce the interrupt latency, most processors save only the minimal amount of
information:
o This minimal amount of information includes Program Counter and processor status registers.
o Any additional information that must be saved, must be saved explicitly by the program
instructions at the beginning of the interrupt service routine.
o An interrupt is more than a simple mechanism for coordinating I/O transfers.
• The concept of interrupts is used in operating systems and in many control applications where
processing of certain routines must be accurately timed relative to external events.
o Real-time processing.
5. What are interrupts? Explain the operation of interrupt with the help of a hardware
Interrupt Hardware

• 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 INTR1 to

Divyashree G Page 7
 Module 4: Input output organization

• INTRn are inactive, that is, if all switches are open, the voltage on the interrupt-request line will be
equal to 𝑉𝑑𝑑.
o 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 INTR
is the logical OR of the requests from individual devices, that is,

• INTR = INTR1 + INTR2 + ⋯ + INTRn

• 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.
• In the electronic implementation of the circuit in Figure 4.6, special gates known as open-collector
(for bipolar circuits) or open-drain (for MOS circuits) are used to drive the INTR line.
• The output of an open-collector or an open-drain gate is equivalent to a switch to ground that is
open when the gate's input is in the 0 state and closed when it is in the 1 state.
• The voltage level, hence the logic state, at the output of the gate is determined by the data applied to
all the gates connected to the bus.
• 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 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 intended sequence of events
o Sometimes such alterations may be undesirable, and must not be allowed.
o For example, the processor may not want to be interrupted by the same device while executing its
interrupt-service routine.
• 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.
• In another case, it may be necessary to guarantee that a particular sequence of instructions is
executed to the end without interruption.
o The interrupt-service routine may change some of the data used by the instructions in question.

Divyashree G Page 8
 Module 4: Input output organization

• Processors generally provide the ability to enable and disable such interruptions as desired.
• One simple way is to provide machine instructions such as Interrupt-enable and Interrupt-disable
for this purpose.
• Consider 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
acknowledgement.
o This means that the interrupt-request signal will be active during execution of the interrupt-service
routine.
• 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.

• 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.
• First instruction of an interrupt service routine can be Interrupt-disable.
• Last instruction of an interrupt service routine before the Return-from-interrupt instruction can be
Interrupt-enable.
• The processor must guarantee that execution of the Return-from-interrupt instruction is completed
before further interruption can occur.
• The second option is to have the processor automatically disable interrupts before starting the
execution of the interrupt-service routine.
• One bit in the PS (Program Status) register, called Interrupt-enable, indicates whether interrupts are
enabled.
o 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.

• 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.
o 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.
• Let us summarize the sequence of events involved in handling an interrupt request from a single

Divyashree G Page 9
 Module 4: Input output organization

device (Assuming that interrupts are enabled):

• The device raises an interrupt request.
• The processor interrupts the program currently being executed.
• Interrupts are disabled by changing the control bits in the PS (except in the case of edge-triggered
interrupts).
• The device is informed that its request has been recognized, and in response, it deactivates the
interrupt-request signal.
• The action requested by the interrupt is performed by the interrupt-
o service routine.
• Interrupts are enabled and execution of the interrupted program is
o resumed.
4. Explain various methods for handling multiple interrupts requests raised by

multiple devices.
Handling Multiple Devices

▪ Consider the situation where a number of devices capable of initiating interrupts are connected to
the processor.
▪ These devices are operationally independent.
• There is no definite order in which they will generate interrupts.
• Several devices may request interrupts at exactly the same time.
• How can the processor recognize the device requesting an interrupt?
• Given that different devices are likely to require different interrupt- service routines, how can the
processor obtain the starting address of the appropriate routine in each case?
• Should a device be allowed to interrupt the processor while another interrupt is being serviced?
• How should two or more simultaneous interrupt requests be handled?

o 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.
o 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.
o When the interrupt-service 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.
• The status register of each device has an IRQ bit which it set to 1 when it requests an interrupt.
• For example, bits KIRQ and DIRQ in Figure 4.3 are the interrupt request bits for the keyboard and
the display, respectively.

Divyashree G Page 10
 Module 4: Input output organization

• Interrupt service routine can poll the I/O devices connected to the bus.
o The first device with IRQ equal to 1 is the one that is serviced.
• Polling mechanism is easy, but time consuming to query the status bits of all the I/O devices connected
to the bus.
3. Explain the terms with respect to interrupts: Vectored interrupts and Interrupt

nesting.
Vectored Interrupts

o 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.
o The code supplied by the device may represent the starting address of the interrupt-service routine
for that device.
▪ The code length is typically in the range of 4 to 8 bits.
▪ The remainder of the address is supplied by the processor based on the area in its memory where
the addresses for interrupt-service routines are located.
o This arrangement implies that the interrupt-service routine for a given device must always start at
the same location.
o Usually the location pointed to by the interrupting device is used to store the starting address of the
interrupt-service routine.

o The processor reads this address, called the interrupt vector, and loads it into the PC.
o In most computers, I/0 devices send the interrupt-vector code over the data bus.
o The interrupting device must wait to put data on the bus only when the processor is ready to receive
it.
o When the processor is ready to receive the interrupt-vector code, it activates the interrupt-
acknowledge line, INTA.
o The I/0 device responds by sending its interrupt- vector code and turning off the INTR signal.

Interrupt Nesting

o Previously, before the processor started executing the interrupt service routine for a device, it
disabled the interrupts from the device.
o In general, same arrangement is used when multiple devices can send interrupt requests to the
processor.
▪ During the execution of an interrupt service routine of device, the processor does not accept
interrupt requests from any other device.

Divyashree G Page 11
 Module 4: Input output organization

▪ Since the interrupt service routines are usually short, the delay that this causes is generally
acceptable.
o However, for certain devices this delay may not be acceptable.

o I/O devices are organized in a priority structure.

▪ An interrupt request from a high-priority device is accepted while the processor is executing the
interrupt service routine of a low priority device.
o A priority level is assigned to a processor that can be changed under program control.
▪ Priority level of a processor is the priority of the program that is currently being executed.
▪ When the processor starts executing the interrupt service routine of a device, its priority is raised to
that of the device.
▪ If the device sending an interrupt request has a higher priority than the processor, the processor
accepts the interrupt request.
▪ Processor’s priority is encoded in a few bits of the processor status register.
▪ Priority can be changed by instructions that write into the processor status register.
o Usually, these are privileged instructions, or instructions that can be executed only in the supervisor
mode.
▪ Privileged instructions cannot be executed in the user mode.
▪ Prevents a user program from accidentally or intentionally changing the priority of the processor.
▪ If there is an attempt to execute a privileged instruction in the user mode, it causes a special type of
interrupt called as privilege exception.
▪ 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.
o Each of the interrupt-request lines is assigned a different priority level.
o Interrupt requests received over these lines are sent to a priority arbitration circuit in the processor.

o A request is accepted only if it has a higher priority level than that currently assigned to the
processor.

Divyashree G Page 12
 Module 4: Input output organization

Simultaneous Requests

o Consider the problem of simultaneous arrivals of interrupt requests from two or more devices.
o The processor must have some means of deciding which request to service first.
o 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 scheme:
o If the processor uses a polling mechanism to poll the status registers of I/O devices to determine
which device is requesting an interrupt.
o In this case the priority is determined by the order in which the devices are polled.
o The first device with status bit set to 1 is the device whose interrupt request is accepted.

Daisy chain scheme:

o Devices are connected to form a daisy chain.

o The interrupt-request line INTR is common to all devices
o Interrupt-acknowledge line INTA is connected in a daisy-chain fashion.
o When devices raise an interrupt request, the interrupt-request line

Divyashree G Page 13
 Module 4: Input output organization

• INTR is activated.
▪ The processor responds by setting INTA line to 1
o This signal is received by device 1; if device 1 does not need service, it passes the signal to device
2.
o 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.
o Device that is electrically closest to the processor has the highest priority.

o When I/O devices were organized into a priority structure, each device had its own interrupt-request
and interrupt-acknowledge line.
o When I/O devices were organized in a daisy chain fashion, the devices shared an interrupt-request
line, and the interrupt-acknowledge propagated through the devices.
o A combination of priority structure and daisy chain scheme can also used.

o Devices are organized into groups.

o Each group is assigned a different priority level.
o All the devices within a single group share an interrupt- request line, and are connected to form a
daisy chain.

Divyashree G Page 14
 Module 4: Input output organization

•
6. What is Direct Memory Access (DMA)? Explain the registers of DMA in the

interfaceDirect Memory Access

o A special control unit may be provided to transfer a block of data directly between an I/O device and
the main memory, without continuous intervention by the processor.
▪ This approach is called direct memory access, or DMA.
o DMA transfers are performed by DMA controller, which is a control circuit that is a part of the I/O
device interface.
o DMA controller performs functions that would be normally carried out by the processor:
▪ For each word, it provides the memory address and all the control signals.
▪ To transfer a block of data, it increments the memory addresses and keeps track of the number of
transfers.

o DMA controller can transfer a block of data from an external device to the processor, without any
intervention from the processor.
▪ However, the operation of the DMA controller must be under the control of a program executed by
the processor. That is, the processor must initiate the DMA transfer.
o To initiate the DMA transfer, the processor informs the DMA controller of:
▪ Starting address,
▪ Number of words in the block.
▪ Direction of transfer (I/O device to the memory, or memory to the I/O device).
o Once the DMA controller completes the DMA transfer, it informs the processor by raising an
interrupt signal.
o 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

Divyashree G Page 15
 Module 4: Input output organization

transfer.
o For an I/O operation involving DMA, the OS puts the program that requested the transfer in the
Blocked state, 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ഥbitdetermines the direction of the transfer.

o When this bit is set to 1 by a program instruction, the controller
• performs a read operation.
o Otherwise, it performs a write operation.
o 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.
o When this flag is set to 1, it causes the controller to raise an interrupt after it has completed
transferring a block of data.
o Finally, the controller sets the IRQ bit to 1 when it has requested an interrupt.

• An example of a computer system is given in Figure 4.19, showing how DMA controllers may be

Divyashree G Page 16
 Module 4: Input output organization

used.
• DMA controller connects a high-speed network to the computer bus.
• Disk controller, which controls two disks also has DMA capability.
o It provides two DMA channels.
• It can perform two independent DMA operations, as if each disk has its own DMA controller.
• The registers to store the memory address, word count and status and control information are
duplicated.

• To start a DMA transfer of a block of data from the main memory to one of the disks, a program
writes the address and word count information into the registers of the corresponding channel of
the disk controller.
• It also provides the disk controller with information to identify the data for future retrieval.
• The DMA controller proceeds independently to implement the specified operation.
• When the DMA transfer is completed, this fact is recorded in the status and control register of the
DMA channel by setting the Done bit.
• At the same time, if the IE bit is set, the controller sends an interrupt request to the processor and
sets the IRQ bit.
• The status register can also be used to record other information, such as whether the transfer took
place correctly or errors occurred.
• Processor and DMA controllers have to use the bus in an interwoven fashion to access the memory.

Divyashree G Page 17
 Module 4: Input output organization

o DMA devices are given higher priority than the processor to access the bus.
o Among different DMA devices, high priority is given to high-speed peripherals such as a disk or a
graphics display device.
• Processor originates most memory access cycles on the bus.
o DMA controller can be said to “steal” memory access cycles from the bus.
o This interweaving technique is called “cycle stealing”.
• An alternate approach is the provide a DMA controller an exclusive capability to initiate transfers on
the bus, and hence exclusive access to the main memory.
o This is known as the block or burst mode.

• Most DMA controllers incorporate a data storage buffer.

• In the case of the network interface in Figure 4.19, for example, the DMA controller reads a block
of data from the main memory and stores it into its input buffer.
• This transfer takes place using burst mode at a speed appropriate to the memory and the computer
bus.
• Then, the data in the buffer are transmitted over the network at the speed of the network.
• A conflict may arise if both the processor and a DMA controller or two DMA controllers try to use
the bus at the same time to access the main memory.
• To resolve these conflicts, an arbitration procedure is implemented on the bus to coordinate the
activities of all devices requesting memory transfers.

Part B
BUS ARBITRATION
o Any device which initiates data transfer operation on bus at any instant of 2time is called as
Bus-Master.
o When the bus mastership is transferred from one device to another device, the next device is
ready to obtain the bus mastership.
o The bus-mastership is transferred from one device to another device based on the principle of
priority system.
o There are two types of bus-arbitration technique:
a) Centralized bus arbitration
b) Distributed bus arbitration
a) Centralized bus arbitration:
• In this technique CPU acts as a bus-master or any control unit connected to bus can be acts as
a bus master.

Divyashree G Page 18
 Module 4: Input output organization

Figure: centralized bus arbitration

• The schematic diagram of centralized bus arbitration is as shown in the fig.:

• The following steps are necessary to transfer the bus mastership from CPU to one of the DMA
controller:
• The DMA controller request the processor to obtain the bus mastership by activating BR (Bus
request) signal.
• In response to this signal the CPU transfers the bus mastership to requested devices
DMAcontroller1 in the form of BG (Bus grant).
• When the bus mastership is obtained from CPU the DMA controller1 blocks the propagation
of bus grant signal from one device to another device.
• The BG signal is connected to DMA controller2 from DMA controller1 in as daisy fashion
style is as shown in the figure.
• When the DMA controller1 has not sent BR request, it transfers the bus mastership to
DMAcontroller2 by unblocking bus grant signal.
• When the DMA controller1 receives the bus grant signal, it blocks the signal from passing to
DMA controller2 and enables BBSY signal. When BBSY signal is set to 1 the set of devices
connected to system bus doesn’t have any rights to obtain the bus mastership from the CPU.

c) Distributed bus arbitration:

• In this technique 2 or more devices trying to access system bus at the same time may
participate in bus arbitration process.
• The schematic diagram of distributed bus arbitration is as shown in the figure

Divyashree G Page 19
 Module 4: Input output organization

•
• The external device requests the processor to obtain bus mastership by enabling start arbitration
signal.
• In this technique 4 bit code is assigned to each device to request the CPU in order to obtain
bus mastership.
• Two or more devices request the bus by placing 4 bit code over the system bus.
• The signals on the bus interpret the 4 bit code and produces winner as a result from the CPU.
• When the input to the one driver = 1, and input to the another driver = 0, on the same bus line,
this state is called as “Low level voltage state of bus”.
• Consider 2 devices namely A & B trying to access bus mastership at the same time.
• Let assigned code for devices A & B are 5 (0101) & 6(0110) respectively.
• The device A sends the pattern (0101) and device B sends its pattern (0110) to master.
• The signals on the system bus interpret the 4 bit code for devices A & B produces device B as
a winner.
• The device B can obtain the bus mastership to initiate direct data transfer between external
devices and main memory.

Divyashree G Page 20
 Module 4: Input output organization

The Memory System: Speed, Size and Cost

• The block diagram of memory hierarchy is as shown in the figure below.

• Registers: The fastest access is to data held in registers. Hence registers are part of the memory
hierarchy. More speed, small size and cost per bit is also more.
• At the next level of hierarchy, small amount of memory can be directly implemented on the
processor chip.
• This memory is called as processor cache. It holds the copy of recently accessed data and
instructions.
• There are 2 levels of caches viz level-1 and level-2.
• Level-1 cache is part of the processor and level-2 cache is placed in between level-1 cache and
main memory.
• The level-2 cache is implemented using SRAM chips
• The next level in the memory hierarchy is called as main memory. It is implemented using
dynamic memory components (DRAM). The main memory is larger but slower than cache
memory. The access time for main memory is ten times longer than the cache memory
• The level next in the memory hierarchy is called as secondary memory.

Divyashree G Page 21
 Module 4: Input output organization

• It holds huge amount of data.

• The main-memory is built with DRAM

• SRAMs are used in cache memory, where speed is essential.
• The Cache-memory is of 2 types:
• Primary/Processor Cache (Level1 or L1 cache)
➢ It is always located on the processor-chip.

• Secondary Cache (Level2 or L2 cache)

➢ It is placed between the primary-cache and the rest of the memory.

• The memory is implemented using the dynamic components (SIMM, DIMM).

• The access time for main-memory is about 10 times longer than the access time for L1cache.
2. What is cache memory? Explain any two mapping functions of cache memory.

Cache Memory
• It is the fast access memory located in between processor and main memory.

•
• The cache memory holds the copy of recently accessed data and instructions.
• The processor needs less access time to read the data and instructions from the cache memory
as compared to main memory.
• Hence by incorporating cache memory, in between processor and main memory, it is possible
to enhance the performance of the system.
• The effectiveness of cache mechanism is based on the property of “Locality of Reference”.
Locality of Reference

Divyashree G Page 22
 Module 4: Input output organization

• Many instructions in the localized areas of program are executed repeatedly during
• sometime of execution
• Remainder of the program is accessed relatively infrequently
• There are 2 types of locality reference:
1. Temporal
➢ The recently executed instructions are likely to be executed again and again.

➢ Eg –instruction in loops, nested loops and few function calls.

2. Spatial
➢ Instructions in close proximity to recently executed instruction are likely to be executed soon.
(near by instructions)
• If active segment of program is placed in cache-memory, then total execution time can be reduced.
• Cache Block / cache line refers to the set of contiguous address locations of some size.
o The Cache-memory stores a reasonable number of blocks at a given time.
• This number of blocks is small compared to the total number of blocks available in main-memory.
o Correspondence b/w main-memory-block & cache-memory-block is specified by mapping-
function.
o If the cache memory is full, one of the block should be removed to create space For the new block,
this is decided by cache control hardware.
o The collection of rule for selecting the block to be removed is called the
• Replacement Algorithm.
o The cache control-circuit determines whether the requested-word currently exists in the cache.
o If data is available, for read-operation, the data is read from cache.
o The write-operation (writing to memory) is done in 2 ways:
1. Write-through protocol &
2. Write-back protocol.
1. Write-Through Protocol
➢ Here the cache-location and the main-memory-locations are updated simultaneously.
[Link]-Back Protocol
➢ This technique is to

→ update only the cache-location &

Divyashree G Page 23
 Module 4: Input output organization

→ mark the cache-location with a flag bit called Dirty/Modified Bit.

➢ The word in memory will be updated later, when the marked-block is removed from cache.
3. During Read-operation
a. If the requested-word currently does not exists in the cache, then read-miss will
occur.
b. To overcome the read miss, Load–through/Early restart protocol is used.
4. Load–Through Protocol
➢ The block of words that contains the requested-word is copied from the memory into cache.

➢ After entire block is loaded into cache, the requested-word is forwarded to processor.
5. During Write-operation
a. If the requested-word does not exists in the cache, then write-miss will occur.
If Write Through Protocol is used, the information is written directly into main-memory.
6. If Write Back Protocol is used,
→ then block containing the addressed word is first brought into the cache&
→ then the desired word in the cache is over-written with the new information.
7. What is cache memory? With relevant diagram, describe Direct Mapping method of

cache memory.
Mapping functions
There are 3 techniques to map main memory blocks into cache memory –
a. Direct mapped cache
b. Associative Mapping
c. Set-Associative Mapping

DIRECT MAPPING
• The simplest way to determine cache locations in which to store memory blocks is the direct
mapping technique as shown in the figure.
• If there are 128 blocks in a cache, the block-j of the main-memory maps onto block-
jmodulo-128 of the cache.
• When the memory-blocks 0, 128, & 256 are loaded into cache, the block is stored in cache-
block 0. Similarly, memory- blocks 1, 129, 257 are stored in cache-block 1.(eg:1mod
128=1,129 mod 128=1).
• The contention may arise Even when the cache is full. But more than one memory-block is
mapped onto a given cache-block position.
• The contention is resolved by allowing the new blocks to overwrite the currently resident-

Divyashree G Page 24
 Module 4: Input output organization

bloc

• Memory-address determines placement of block in the cache.

• The main memory block is loaded into cache block by means of memory address. The main
memory address consists of 3 fields as shown in the figure.
• Each block consists of 16 words. Hence least significant 4 bits are used to select one of the
16 words.
• The 7bits of memory address are used to specify the position of the cache block, location.
The most significant 5 bits of the memory address are stored in the tag bits. The tag bits
are used to map one of 25 = 32 blocks into cache block location (tag bit has value 0-31).
• The higher order 5 bits of memory address are compared with the tag bits associated with

Divyashree G Page 25
 Module 4: Input output organization

cache location. If they match, then the desired word is in that block of the cache.
• If there is no match, then the block containing the required word must first be read from
the main memory and loaded into the cache. It is very easy to implement, but not flexible.

2. Associative Mapping:
• It is also called as associative mapped cache. It is much more flexible.
• In this technique main memory block can be placed into any cache block position.
• In this case, 12 tag bits are required to identify a memory block when it is resident of the
cache memory.
• The Associative Mapping technique is illustrated as shown in the fig.

• In this technique 12 bits of address generated by the processor are compared with the tag
bits of each block of the cache to see if the desired block is present.
• This is called as associative mapping technique.

Divyashree G Page 26
 Module 4: Input output organization

[Link] Associative Mapping:

• It is the combination of direct and associative mapping techniques.
• The blocks of cache are divided into several groups. Such a groups are called as sets.
• Each set consists of number of cache blocks. A memory block is loaded into one of the
cache sets.
• The main memory address consists of three fields, as shown in the figure.
• The lower 4 bits of memory address are used to select a word from a 16 words.
• A cache consists of 64 sets as shown in the figure. Hence 6 bit set field is used to select a
cache set from 64 sets.
• As there are 64 sets, the memory is divided into groups containing 64 blocks, where each
group is given a tag number
• The most significant 6 bits of memory address is compared with the tag fields of each set
to determine whether memory block is available or not.
• The following figure clearly describes the working principle of Set Associative Mapping
technique.
• cache that has “k” blocks per set is called as “k-way set associative cache‟.
• Each block contains a control-bit called a valid-bit.
• The Valid-bit indicates that whether the block contains valid-data (updated data).
• The dirty bit indicates that whether the block has been modified during its cache residency.
• Valid-bit=0 - When power is initially applied to system.
• Valid-bit=1 - When the block is loaded from main-memory at first time.
• If the main-memory-block is updated by a source & if the block in the source is already
exists in the cache, then the valid-bit will be cleared to “0‟.
• If Processor & DMA uses the same copies of data then it is called as Cache Coherence
Problem.

Divyashree G Page 27
 Module 4: Input output organization

Advantages:
1. Contention problem of direct mapping is solved by having few choices for block placement.
2. The hardware cost is decreased by reducing the size of associative search.

Divyashree G Page 28