Module 4

Memory and IO Peripherals

Prabhu R
School of Electronics Engineering
VIT, Vellore.
PRABHU R 1
 Module 4
Memory Organization,
Memory Hierarchy,
Memory Design,
Cache Memory- Mapping Policies,
Replacement Algorithms,
I/O Fundamentals- programmed I/O and Interrupt driven I/O,
Direct Memory Access,
Shared Memory Architectures.
PRABHU R 2
Memory
• A memory is just like a human brain. It is used to store data and
instructions.
• The human brain has a memory capacity estimated to be around 2.5
petabytes, which is equal to 2.5 million gigabytes or 3 million hours of TV
shows.
• The memory is divided into large number of small parts called cells.
• Each location or cell has a unique address, which varies from zero to
memory size minus one.
• For example, if the computer has 64k words, then this memory unit has
64 * 1024 = 65536 memory locations.
• The address of these locations varies from 0 to 65535.
 Introduction to Memory
• Charles Babbage started Difference
enginein 1821but failed its test in 1833, Why?
– Due to unavailability of Memory
• What is Memory?
• A single separate storage structure that holds information in
the form of bits called Memory.
• The binary information may be instructions and data
• The stored program concept was introduced with the advent

of vacuum tubes by John Von Neumann 1940

• EDVAC (Electronic Discrete Variable Automatic Computer)
Key Characteristics
Location Access methods
CPU Sequential access
Internal(main) Direct access
External (secondary) Random access
Associative access
Capacity Performance
Word size Access time Physical characteristics
Number of words Cycle time Erasable/non erasable
Transfer rate Volatile/non volatile
Unit of Transfer Physical type
Word Semiconductor
Block Magnetic surface
Optical
Word size
Capacity
The capacity of the internal memory is typically
expressed in terms of bytes or words.
Number of words
This capacity also depends on number of word
in memory.
Unit of Transfer
For the internal memory, the unit of transfer is equal to
the number of data lines into and out of the main
memory module (word Length).
Word The common word lengths are 8,16,1nd 32 bits.
Block For external memory, the data often transferred in much longer
units than a word, and these are referred to as Blocks.
Types of Memory
 Primary memory

• Primary memory also known as “main memory” or “internal memory” or

“Physical memory“ which is located in the mother board of system or as we
say which is directly connected to the CPU.
• It is the place where only little bit of data are stored either by manufacturer
or by user.
• This is further divided into two parts :-
• RAM
• ROM
Random Access Memory(RAM)
• RAM also known as “random access memory” it stores the data which
the user currently uses or as we say it stores the data temporary in it.
• RAM needs power or electricity to work when the computer power is
turned off then all the data in it will be erased automatically.
• This is a circuit which have its separate space or slot in motherboard.
• This allows the computer to run the software faster.
• RAM is further classified into two parts
• SRAM
• DRAM
Read Only Memory(ROM)
• ROM also known as “Read Only Memory” as the word refers mainly it
can only read the data which in stored in it.
• This memory is mainly used by our computer when we just turn on
our computer.
• This is non-volatile in nature.
• Mainly there are types of ROM :-
• PROM
• EPROM
• EEPROM
• MPROM
Difference b/w PM & SM
Primary Memory Secondary Memory

It is temporary memory It is permanent memory

It is volatile It is non volatile
Fast access time Low access time
Limited storage Vast storage
Data can be directly accessed by the CPU Data cannot directly accessed by the CPU
It is small in size It is large in size
Primary memory are semiconductor Secondary memories are magnetic
memories memories
Expensive Inexpensive
Computers has two kinds of components:

• Hardware, consisting of its physical

devices (CPU, memory, bus, storage
devices, ...)

• Software, consisting of the programs

it has (Operating system, applications,
utilities, ...)
Memory Hierarchy
• Memory Hierarchy is one of the most required things in Computer
Memory as it helps in optimizing the memory available in the
computer.
• There are multiple levels present in the memory, each one having a
different size, different cost, etc.
• Some types of memory like cache, and main memory are faster as
compared to other types of memory but they are having a little less
size and are also costly whereas some memory has a little higher
storage value, but they are a little slower.
What next
So now data is in the
RAM this means that we
A computer
are usingwill
[Link]
Therefore
have this
a small amount of the
also means that
cache butisthe more it
There is anotherCPU going
type of to want to
has, the quicker the CPU
memory called [Link] it.
can process data and the
This is often built into
quicker your computer
the CPU.
will run
Data stored on the cache
The CPU could get the
is very quick for the CPU
data from the RAM each
to access. Therefore data
time it needs to
that the CPU is going to
complete a process but
process is taken from the
even this would still take
RAM and put onto the
too long
cache
Types of Memory Hierarchy
• This Memory Hierarchy Design is divided into 2 main types:
• External Memory or Secondary Memory: Comprising of Magnetic
Disk, Optical Disk, and Magnetic Tape i.e. peripheral storage devices
which are accessible by the processor via an I/O Module. (Cheap,
Slow, Used for Storage)
• Internal Memory or Primary Memory: Comprising of Main Memory,
Cache Memory, Physical Memory & CPU registers. This is directly
accessible by the processor. (FAST, Used for Operation)
Memory Hierarchy
Registers
Registers are small, high-speed memory units located in the CPU. They are used to store the most
frequently used data and instructions. Registers have the fastest access time and the smallest
storage capacity, typically ranging from 16 to 64 bits.
Cache Memory
Cache memory is a small, fast memory unit located close to the CPU. It stores frequently used data
and instructions that have been recently accessed from the main memory.
Main Memory
Main memory, also known as RAM (Random Access Memory), is the primary memory of a
computer system. It has a larger storage capacity than cache memory, but it is slower. Main
memory is used to store data and instructions that are currently in use by the CPU.
Static RAM:
Static RAM stores the binary information in flip flops and information remains valid until power is
supplied.
Dynamic RAM:
It stores the binary information as a charge on the capacitor.
Secondary Storage
Secondary storage, such as hard disk drives (HDD) and solid-state drives (SSD), is a non-volatile
memory unit that has a larger storage capacity than main memory.
Magnetic Disks
Magnetic Disks are simply circular plates that are fabricated with either
a metal or a plastic or a magnetized material.
The Magnetic disks work at a high speed inside the computer and these
are frequently used.
Magnetic Tape
Magnetic Tape is simply a magnetic recording device that is covered
with a plastic film.
It is generally used for the backup of data.
In the case of a magnetic tape, the access time for a computer is a little
slower and therefore, it requires some amount of time for accessing
the strip.
Characteristics of Memory Hierarchy
Capacity:
It is the global volume of information the memory can store. As we move from top
to bottom in the Hierarchy, the capacity increases.
Access Time:
It is the time interval between the read/write request and the availability of the
data. As we move from top to bottom in the Hierarchy, the access time increases.
Performance:
Earlier when the computer system was designed without a Memory Hierarchy
design, the speed gap increased between the CPU registers and Main Memory due
to a large difference in access time.
Cost Per Bit:
As we move from bottom to top in the Hierarchy, the cost per bit increases i.e.
Internal Memory is costlier than External Memory.
Memory Organization
Memory Organization
• Memory organization is an important aspect of computer architecture, also
known as the organization of computer systems (COA).
• It refers to the way that the computer’s memory is arranged and managed.
• The memory of system can be thought of as a large number of addressable
storage locations.
• Each location can store a fixed amount of data, typically measured in bits
or bytes.
• Memory organization involves the use of different types of memory,
including RAM, ROM, cache memory, virtual memory, flash memory, and
magnetic disks.
• Each type of memory is used for a specific purpose and has its own
advantages and disadvantages.
Memory Organization:
• Program Load: When a program is executed, it is loaded from secondary
storage (HDD/SSD) into main memory (RAM). It may also be loaded
partially into cache memory to speed up execution.
• Accessing Data: The CPU accesses data through registers and cache for
quick computations. If the data is not in the cache, it will fetch it from
RAM. If it’s not in RAM either, it will fetch it from secondary storage.
• Swapping and Virtual Memory: If the system runs out of physical RAM,
parts of the program (pages) may be swapped out to secondary storage.
This process, known as paging, is managed by the operating system’s
memory manager.
 Internal Memory Organization

• A memory consists of cells in the form of an array.

• Each cell is capable of storing one bit of information.

• Each row of the cells constitutes a memory words and all cells of a row
are connected to a common line referred to as a word line.

• A w x b memory has w words, each word having b number of bits. The

bellow Fig 1 shows the 16x8 memory.
Memory Design
• All memory cells must provide these four functions: Select, Data In,
Data Out, and R/W.
An 8-bit register as a 1D RAM array
Conceptual View of Memory Design
2-4 Decoder Circuit
Memory - Block Diagram
RAM Chip
ROM Chips
•Information stored in ROM is
permanent.
•Information and programs are
stored on ROM in binary format (0s
and 1s).
•It is used in the start-up process of
• No R/W signal – Default Read only. the computer.
• Data Bus - unidirectional
Organization of bit cells in a memory chip.
• Each row of the cell is a memory word.
• The memory words are connected to a common line termed as word line.
• The word line is activated based on the address it receives from the address bus.
• An address decoder is used to activate a word line.
• The cells in the memory are connected by two bit lines (column wise).
• These are connected to data input and data output lines through sense/ write
circuitry.
• Read Operation: During read operation the sense/ write circuit reads the
information by selecting the cell through word line and bit lines. The data from
this cell is transferred through the output data line.
• Write Operation: During write operation, the sense/ write circuitry gets the data
and writes into the selected cell. The data input and output line of sense / write
circuit is connected to a bidirectional data line.
• Two control lines, R/W and CS, are provided.
• The R/W(Read/Write) input specifies the required operation, and the CS (Chip
Select) input selects a given chip in a multichip memory system.
128 x 8 memory chips & 1024 x 1 memory chips
 Cache Memory
• Cache memory is a special type of internal memory that can be
accessed much faster than the main RAM.
• It is used by the CPU to enhance its performance.
• The cache contains a copy of portions of main memory.
• When the processor attempts to read a word of memory, a check is
made to determine if the word is in the cache.
 No

Yes
Types of Cache
• Primary Cache:
• very fast and its access time is similar to the processor registers
• it is built onto the processor chip
• its size is quite small
• also known as a level 1 cache and is build using static RAM (SRAM)
• Secondary Cache:
• The secondary cache or external cache is cache memory that is external
to the primary cache
• It is located between the primary cache and the main memory
• It is also known as a level 2 cache
 How Cache Memory Works
CPU Request:
• When the CPU needs a piece of data or an instruction, it first
checks the cache memory.
Cache Hit:
• If the data is found in the cache (a cache hit), it can be
retrieved very quickly.
Cache Miss:
• If the data is not in the cache (a cache miss), it must be
fetched from the slower main memory (RAM).
Data Transfer:
• Once the data is retrieved from RAM, it is also copied into the
cache, making it available for future, faster access.
Benefits of Cache Memory
• Faster access
• Reducing memory latency
• Lowering bus traffic
• Increasing effective CPU utilization
• Enhancing system scalability
• In order to understand the working of cache we must understand few
points
• Cache memory is faster, they can be accessed very fast.
• Cache memory is smaller, a large amount of data cannot be stored.
Difference Between RAM & Cache
 Mapping Techniques
• The basic characteristics of cache memory is fast access time.
• Therefore, very little or no time must be wasted when searching for words
in the cache.
• The transformation of data from main memory to cache memory is
referred to as mapping process.
• Cache mapping defines how a block from the main memory is mapped to
the cache memory in case of a cache miss.
• Cache mapping is a technique by which the contents of main memory are
brought into the cache memory.
RAM & ROM Chips
 Memory Design
• The designer of a computer system must calculate the amount of memory required for the particular application and assign it to either
RAM or ROM.
• The interconnection between memory and processor is then established from knowledge of the size of memory needed and the type
of RAM and ROM chips available.
• The addressing of memory can be established by means of a table that specifies the memory address assigned to each chip.
• The table, called a memory address map, is a pictorial representation of assigned address space for each chip in the system.
EXAMPLE:
• To demonstrate with a particular example, assume that a computer system needs 512 bytes of RAM and 512 bytes of ROM.
• The memory address map for this configuration is shown in Table 1.

• RAM1- 000-127 =128

• RAM2- 128-255 =128
• RAM3- 256-383 =128
• RAM4- 384-511 =128
• ROM – 512-1023= 512
 Memory Design - Memory Interface Address Map

Address Calculation
(From – To)
-calculated from 16 bit address Bus line 10 select RAM or ROM
- Hexadecimal format Bus lines 8 and 9 are used to
No. of Address line bits (x) is given by N=2x select one RAM out of 4 RAMs
No. of data bus = No. of columns (Word size)
Assumptions
RAM size: 128 * 8 ----- 7 bit address bits needed, No. of Data Lines --- 8
ROM size: 512 * 8 ------ 9 bit address bits required, No. of Data Lines --- 8
 Memory Design - Memory Interface
Address Map

Address Calculation
(From Address) v v v v
-calculated from 16 bit address
- Hexadecimal formaStubstitute x=0 to get ‘From’ address X=0

If x=0 ‘From’ address is 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

No. of Address line bits (x) is given by N=2x
No. of data bus = No. of columns (Word size)
Convert to hexadecimal value 0 2 0 0
So, from address for ROM 1 is 0200
 Memory Design - Memory Interface Address Map

Address Calculation
(To Address) v v v v
-calculated from 16 bit address
- Hexadecimal formaSt ubstitute x=1 to get ‘To’ address X=1

If x=1  ‘To’ address is 0000 0 0 1 1 1 1 1 1 1 1 1 1

Convert to hexadecimal value 0 3 F F

So, To address for ROM 1 is 03FF

 Memory Design - Memory Interface Address Map

• Hence,
• Available Memory chip Size: N × W
(N – represents ROWS – No. of words) (W – represents COLUMNS – word size)
• Required Memory chip size: N’ × W’
where N’≥ N and W’≥ W
• Required number of chips = p × q
•where p = N’ / N (No. of rows reqd. ) and
Address bits - required to map to the row
q = W’/ W (no. of Cols reqd.) • Decoder used
No. of Address line bits (x) is given by
N=2x
No. of data bus = No. of columns (Word
size)
 Memory design - Memory Interface Address Map

There are 3 types of organizations of N’ × W’ that can be formed using N × W

• N’ > N and W’ = W => increasing the number of words (Rows - N) in the memory

• N’ = N and W’ > W => increasing the word size (Columns – W) of the chip

• N’ > N and W’ > W => increasing both N & W (Rows & Columns) the number of

words and number of bits in each word.

 There are different types of organization of N1 x W 1 –memory using N x W –bit chips

How many 1024x 8 RAM chips are needed to provide a memory capacity of 2048 x 8?

Case 1: If NI > N & W I = W

NI
Increase number of words by the factor of p =
N
How many 1024x 4 RAM chips are needed to provide a memory capacity of 1024 x 8?

Case 2: If NI = N & W I > W

I
Increase the word size of a Memory by a factor of q = W
W

How many 1024x 4 RAM chips are needed to provide a memory capacity of 2048 x 8?

Case 3: If NI > N & W I > W

Increase number of words by the factor of p &
Increase the word size of a Memory by a factor of q
 Problem – 1 (CASE 2) – Increasing the word size (Columns)
Design 128 × 16 (N’ × W’)- bit RAM using 128 × 4(N × W) - bit RAM
Solution:
Available-N=128; Required-N’=128; Available-W=4; Required-W’=16
• p = N’/N; 128 / 128 = 1;
• q = W’/W; 16 / 4 = 4
Therefore, No. of chips required is calculated by,
p × q = 1 × 4 =4 (i.e. 4 memory chips of size 128 × 4 are required to construct 128 × 16 bit RAM)
• X – Number of bits required to address lines
128 x 4= 27 x 4 (by N=2x) ; X=7 bit address is required
• Y- Number of bits required for Selecting the specific RAM.
(p = 2y) ; 1= 20 Y=0 (since only one RAM)
• Z – Number of bits to select the RAM or ROM or Interface…
No. of Types (T) = 1; Z=0 ((by T=2Z)
Memory Design - Memory Interface Address Map
Component Hexadecimal address Address Bus
From To 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

RAM 1.1 0000 007F x x x x x x x

RAM 1.2 0000 007F x x x x x x x

RAM 1.3 0000 007F x x x x x x x

RAM 1.4 0000 007F x x x x x x x

Z – Number of bits to select the RAM or ROM or Interface…

Z=0 address line 9 is empty

Y- Number of bits required for Selecting the specific RAM

Y=0 Only one row for the RAM so address lines 7 and 8 are empty
X=7 7 bit address lines(from 0 to 6)
Memory Design - Memory Interface Address Map
Component Hexadecimal address Address Bus
From To 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

RAM 1.1 0000 007F x x x x x x x

RAM 1.2 0000 007F x x x x x x x

RAM 1.3 0000 007F x x x x x x x

RAM 1.4 0000 007F v v xv x x x x v x x

Substitute x=0 to get ‘From’ address X=0

If x=0 ‘From’ address is 0000 0 0 0 0 0 0 0 0 0 0 0 0

Convert to hexadecimal value 0 0 0 0

So, from address of RAM is 0000
Memory Design - Memory Interface Address Map
Component Hexadecimal address Address Bus
From To 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

RAM 1.1 0000 007F x x x x x x x

RAM 1.2 0000 007F x x x x x x x

RAM 1.3 0000 007F x x x x x x x

RAM 1.4 0000 007F v v x vx x x x v x x

Substitute x=1 to get ‘to’ address X=1

If x=1 ‘to’ address is 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1

Convert to hexadecimal value 0 0 7 F

So, to address of RAM is 007F
Memory Design - Memory Interface Address Map
Memory design – Increasing the word size
Design 128 × 16 (N’ × W’)- bit RAM using 128 × 4 (N × W) - bit RAM
Data Bus
16

4 4 4 4
Data (0-3) Data (0-3) Data (0-3) Data (0-3)

Address (0-6) Address (0-6) Address (0-6) Address (0-6)

128 × 4 128 × 4 128 × 4 128 × 4

RAM RAM RAM RAM
1.1 1.2 1.3 1.4
Address CS R/W CS R/W CS R/W CS R/W
Bus
7
Chip Select

Read/write Control

Since W is increased ---- the 4 chips should be arranged horizontally.

Problem – 2 (CASE 1) – Increasing the number of words (Rows)
Design 1024 × 8 - bit RAM using 256 × 8 - bit RAM
Solution:
p = 1024 / 256 = 4; q = 8 / 8 = 1
• p × q = 4 ×1 = 4 - 4 memory chips of size 256 × 8 are required to construct
1024 × 8 bit RAM
• X – Number of bits required to represent the address lines
256 x 8= 28 x 4; x=8 bit address is required
• Y- Number of bits for Selecting the specific RAM.
(p = 2y) (p=422y ) y=2
• Z – Number of 0 (select the RAM or ROM)
[Link] Memory NxW N1 x W1 P q p*q x y z Total
1024 ×
1 RAM 256 × 8 4 1 4 8 2 0 10
8
Memory Design - Memory Interface Address Map

X=8 8 bit address lines(from 0 to 7)

Y=2 address lines 8 and 9 will select one RAM among 4 RAM

Z=0 address line 10 is empty

Memory Design - Memory Interface Address Map

v v

Substitute x=0 to get ‘From’ address X=0

If x=0 ‘From’ address is 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0

Convert to hexadecimal value 0 3 0 0

So, from address of RAM is 0300

Memory Design - Memory Interface Address Map

v v

Substitute x=1 to get ‘To’ address X=1

If x=1 ‘To’ address is 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1

Convert to hexadecimal value 0 3 F F

So, from address of RAM is 03FF

Memory Design - Memory Interface Address Map
 Direct Mapping

Cache Memory Block Placement SetAssociative

FullyAssociative
Management
Techniques Block Identification
Tag

Index

Offset
Cache Memory Management
Techniques
FIFO

Block Replacement LRU, MRU

Optimal

Write Through

Write back
Update Policies
Write around

Write allocate
Cache Mapping
 Types of Mapping

• There are three different cache mapping policies or mapping

functions:

• Direct mapping

• Associative mapping(Full)

• Set Associative mapping

Direct Mapping
• The simplest technique, known as direct mapping, maps each block of
main memory into only one possible cache line. or In Direct mapping,
assign each memory block to a specific line in the cache.
• If a line is previously taken up by a memory block, when a new block
needs to be loaded, the old block is trashed.
• An address space is split into two parts index field and a tag field.
• The Cache Memory consists of cache lines.
These cache lines has same size as memory
blocks. The address in cache memory
consists of:
• Block Offset: This is the same block offset
we use in Main Memory.
• Index: It represent cache line number. This
part of the memory address determines
which cache line (or slot) the data will be
placed in.
• Tag: The Tag is the remaining part of the
address that uniquely identifies which block
is currently occupying the cache line.
• Main memory can store 32K words of 12 bits each
• The cache is capable of storing 512 of these words
• The CPU address of 15 bits(n-bits) is divided into two fields. The nine
least significant bits constitute the index field(k-bits) and remaining
six bits tag field(n-k bits).
• The number of bits in the indexed field is equal to the number of
address bits required to access the cache memory.
• The general case 2^k words in cache memory and 2^n words in main
memory.
• For every word stored in cache there is a duplicate copy in main memory
• The CPU communicate with both memories, it first sends a 15 bit address to
cache
• If there is a hit, the CPU accepts the data from cache
• If there is miss, the CPU reads the word from main memory and the word is
then transferred to cache
• The particular block of main memory can map to only one particular line of
the cache.
• Cache line number = ( MM Block Address ) modulo (Number of CM lines)
• Modulo is nothing Remainder
• Here main memory is total 16 blocks each block have 4 word (16*4=64) and
cache memory total 16 words each block contain 4 word(4*4=16)

• 0 mod 4 = 0
• 1 mod 4 = 1
• 8 mod 4 = 0
• 10 mod 4 = 2

• Memory location 0,4,8,12 all map to cache block 0.

• Address 1,5,9,13 all map with block 1.
• 14 mod 4 = 2
Direct Mapping-Physical Address
Advantages:
1. Simple and easy to put into effect
2. Low hardware overhead
3. Fast hit time
Disadvantages:
1. High pass over fee because of restrained wide variety of cache blocks
2. Increased war misses because of block collisions
3. Limited flexibility in phrases of block placement
 Associative Mapping(Full)
• The Fastest and most flexible cache organization uses an
Associative memory.
• A block of main memory can be mapped to any freely
available cache line, this makes fully associative mapping
more flexible than direct mapping.
• The diagram shows the address value of 15 bits is shown
as a five-digit octal number and its corresponding 12 bit
word is shown in four-digit octal number.
• The CPU address of 15 bits is placed in argument register
and the associative memory searched for matching
address. If the address is found, the corresponding 12 bit
data is read and sent to the CPU.
• If no match occurs, the main memory is accessed for the
word.
• If cache is full then a decision must be taken to which line in cache to
be replaced by the new content(i.e need a replacement algorithm)
• A replacement algorithm is needed to replace a block if the cache is
full
• Replacement Algorithm are:
• Least Recently Used(LRU)
• First In First Out(FIFO)
• Least Frequently used(LFU)
• Optimal
Advantages:
1. Higher hit fee than direct-mapped cache because of more than one
blocks being saved in each set
2. More bendy block placement than direct-mapped cache
3. Lower struggle misses as compared to direct-mapped cache
Disadvantages:
1. Higher hardware overhead than direct-mapped cache.
2. Longer hit time than direct-mapped cache because of looking
multiple blocks
Set Associative
• Set Associative mapping combines direct mapping with associative
mapping by arrangement lines of a cache into sets
• Set associative cache memory has highest hit ratio compared to direct and
associative mapping cache memory, therefore its performance is
considerably better
• It is very expensive because the set size increase the cost increase.
• It includes k lines per set is known as a k way set association cache.
• Cache lines are grouped into sets where each set contains k number of
lines.
• A particular block of main memory can map to only one particular set of
the cache.
• However, within that set the memory block can map to any freely available
cache line.
• A particular block of main memory can map to only one particular set
of the cache
Cache set number=(main memory block address)modulo(number of
sets in cache)
Advantages:
1. Highest hit rate amongst cache businesses
2. Most flexible block placement
3. No struggle misses because of fully-associative mapping
Disadvantages:
1. Highest hardware overhead among cache agencies
2. Longest hit time due to searching all blocks in cache
3. Limited scalability because of constrained physical area and
huge tag storage necessities
 Cache Replacement Algorithms
• When a main memory block needs to be brought into the cache while all the
blocks are occupied, then one of them has to be replaced.
• This selection of the block to be replaced is using cache replacement algorithms.
• The following are the common replacement techniques:
• Least Recently Used (LRU): This replaces the cache line that has been in the cache
the longest with no references to it.
• First-in First-out (FIFO): This replaces the cache line that has been in the cache the
longest.
• Least Frequently Used (LFU): This replaces the cache line that has experienced the
fewest references.
• Optimal: In this method, pages are replaced which would not be used for the
longest duration of time in the future.
FIFO (First-In–First-Out) means:
• The oldest block (the one that entered the cache first) will be replaced
first.
• So, blocks are removed in the same order they were loaded — like a
queue.
• The first block brought in is the first to go out.
• The newest block always goes to the end of the queue.
Given:
Cache type: Fully associative

Replacement policy: FIFO

Cache lines: 4

Block requests (sequence):

2, 3, 4, 7, 6, 3, 4, 7, 5, 4, 7, 8

Step 2: Count Hits and Misses

Total requests = 12

Misses = Steps 1, 2, 3, 4, 5, 9, 12 → 7 Misses

Hits = 12 − 7 = 5 Hits
Step Request Cache (before access) Hit/Miss Explanation Cache (after access)

1 2 [] Miss Empty cache → load 2 [2]

2 3 [2] Miss Load 3 [2, 3]

3 4 [2, 3] Miss Load 4 [2, 3, 4]

4 7 [2, 3, 4] Miss Load 7 (now cache full) [2, 3, 4, 7]

5 6 [2, 3, 4, 7] Miss Cache full → remove oldest (2) [3, 4, 7, 6]

6 3 [3, 4, 7, 6] Hit 3 already present [3, 4, 7, 6]

7 4 [3, 4, 7, 6] Hit 4 present [3, 4, 7, 6]
8 7 [3, 4, 7, 6] Hit 7 present [3, 4, 7, 6]

9 5 [3, 4, 7, 6] Miss Remove oldest (3), insert 5 [4, 7, 6, 5]

10 4 [4, 7, 6, 5] Hit 4 present [4, 7, 6, 5]

11 7 [4, 7, 6, 5] Hit 7 present [4, 7, 6, 5]

12 8 [4, 7, 6, 5] Miss Remove oldest (4), insert 8 [7, 6, 5, 8]

Advantages of FIFO:
• Simple to implement
• Uses a queue; only need to know the insertion order.
• No need to track access frequency
Disadvantages of FIFO
• May remove frequently used blocks
• Even if an old block is still in use, FIFO will remove it if it’s the oldest.
• Not optimal for locality
• Doesn’t consider how recently or how often a block is used.
Optimal Replacement
• Optimal policy replaces the block that will not be used for the longest
period in the future.
• It gives the best possible hit ratio (theoretical maximum), but cannot
be implemented in real systems — it’s used only for analysis and
comparison
Fully associative cache (4 lines)
Replacement policy: Optimal (OPT)
Block request sequence:
0, 1, 2, 3, 4, 2, 3, 1, 5, 6
Hits: 3 (steps 6, 7, 8)
Misses: 7
Total = 10 requests
 0, 1, 2, 3, 4, 2, 3, 1, 5, 6
Cache
Step Request Hit/Miss Action / Reason Cache (after)
(before)
1 0 [] Miss Cache empty → load 0 [0]
2 1 [0] Miss Load 1 [0, 1]
3 2 [0, 1] Miss Load 2 [0, 1, 2]
4 3 [0, 1, 2] Miss Load 3 (cache full now) [0, 1, 2, 3]
Need replacement → look ahead:
future uses: 0(never), 1(8th),
5 4 [0, 1, 2, 3] Miss [4, 1, 2, 3]
2(6th), 3(7th) → 0 not used
again, so replace 0
6 2 [4, 1, 2, 3] Hit 2 present [4, 1, 2, 3]
7 3 [4, 1, 2, 3] Hit 3 present [4, 1, 2, 3]
8 1 [4, 1, 2, 3] Hit 1 present [4, 1, 2, 3]
Look ahead: future uses after step
9:4(never), 1(–), 2(–), 3(–) —
9 5 [4, 1, 2, 3] Miss [5, 1, 2, 3]
only 6 left, 4 not used again →
replace 4
Look ahead: 1(–), 2(–), 3(–),
10 6 [5, 1, 2, 3] Miss [6, 1, 2, 3]
5(never) → replace 5
LRU Cache
• Cache replacement algorithms are efficiently designed to replace the
cache when the space is full.
• The Least Recently Used (LRU) is one of those algorithms.
• As the name suggests when the cache memory is full, LRU picks the
data that is least recently used and removes it in order to make space
for the new data.
Least Recently Used
When the cache is full and a new block needs to be brought in,→
Replace the Least Recently Used block (the one not accessed for the
longest time)
Sequence : 0,1,2,3,4,2,3,1,5,6
 0,1,2,3,4,2,3,1,5,6
Reque
Step Cache (oldest) Hit/Miss Explanation Cache ( newest)
st
1 0 [] Miss Load 0 [0]
2 1 [0] Miss Load 1 [0, 1]
3 2 [0, 1] Miss Load 2 [0, 1, 2]
4 3 [0, 1, 2] Miss Load 3 (cache full) [0, 1, 2, 3]
Replace 0 (least recently
5 4 [0, 1, 2, 3] Miss [1, 2, 3, 4]
used)
2 is in cache → move it to
6 2 [1, 2, 3, 4] Hit [1, 3, 4, 2]
most recent
3 is in cache → move it to
7 3 [1, 3, 4, 2] Hit [1, 4, 2, 3]
most recent
1 is in cache → move to
8 1 [1, 4, 2, 3] Hit [4, 2, 3, 1]
most recent
Replace 4 (least recently
9 5 [4, 2, 3, 1] Miss [2, 3, 1, 5]
used)
Replace 2 (least
10 6 [2, 3, 1, 5] Miss [3, 1, 5, 6]
recently used)
 Problems for Memory Mapping

[Link] the following main memory references: 1, 2, 3, 4, 1, 2, 3, 5, 6, 7

If the number of blocks in the cache memory is 4,find:
[Link] number of cache hits and cache misses using (specify the mapping
technique)
(a) Direct Mapping
(b) Associative Mapping
(c) Set-Associative Mapping
[Link] the step-by-step cache content after each memory reference.
[Link] the hit ratio and miss ratio.
[Link] the following main memory references:7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2
If the number of blocks in the cache memory is 4,answer the following:
[Link] the number of cache hits and cache misses using the following mapping techniques:
(a) Direct Mapping
(b) Fully Associative Mapping
(c) Set-Associative Mapping
[Link] the cache content after each memory reference.
[Link] the hit ratio and miss ratio.

[Link] the following sequence of main memory references:

7, 0, 1, 2, 0, 3, 5, 4, 2, 3, 0
If the number of cache blocks is 4, answer the following:
[Link] the number of cache hits and cache misses using:
(a) Direct Mapping
(b) Fully Associative Mapping
(c) Set Associative Mapping
[Link] the cache contents after each memory reference.
[Link] the hit ratio and miss ratio.
Problem for Replacement Algorithm
1. Consider the following reference string 5 0 1 2 0 3 2 0 3 4 1 0 5 0 4 3 2 1
2 0 1 and find the number page faults for the LRU replacement algorithm
with 3 cache blocks.
2. Consider the following reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3
and find the number page faults for the LRU replacement algorithm with 4
cache blocks.
3. Consider the following reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3,
0, 3, 2, 3 and find the number page faults for the FIFO and LRU
replacement algorithm with 4 cache blocks.
I/O Fundamentals
Introduction to I/O Module
• An input/output (I/O) device is any hardware that enables a human
user or another system to communicate with a computer.
• As the name suggests, these devices can both receive data (input) from
the user or another source and deliver data (output) from the
computer.
• Essentially, an I/O device bridges the computer and external entities,
facilitating seamless data exchange.
• Input devices are the devices that are used to send signals to the
computer for performing tasks. The receiver at the end is the CPU
(Central Processing Unit), which works to send signals to the output
devices.
I/O BUS AND INTERFACE MODULES
• Each peripheral has an interface
module associated with it
• It ensures that data is correctly
transferred between the two,
handling differences in speed, data
format, and control signals.
• Decodes the device address (device
code)
• Decodes the commands (operation)
• Provides signals for the peripheral
controller
• Synchronizes the data flow and
supervises the transfer rate between
peripheral and CPU or Memory
• Input-output interface provides a method for transferring information
between internal storage and external I/0 devices.
• Peripherals(I/O Devices) connected to a computer need special
communication links for interfacing them with the central processing
unit.
• Each peripheral device has associated with it an interface unit.
• Each interface decodes the address and control received from the I/O
bus, interprets them for the peripheral, and provides signals for the
peripheral controller.
• It also synchronizes the data flow and supervises the transfer between
peripheral and processor.
• Each peripheral has its own controller that operates the particular
electromechanical device.
• For example, the printer controller controls the paper motion, the
print timing, and the selection of printing characters. A controller may
be housed separately or may be physically integrated with the
peripheral.
I/O Bus and Memory Bus
• MEMORY BUS is for information transfers between CPU and the Main
Memory
• I/O BUS is for information transfers between CPU and I/O devices
through their I/O interface
• Many computers use a common single bus system for both memory
and I/O interface units
• Use one common bus but separate control lines for each functions
• Use one common bus with common control lines for both function.
• Some computer systems use two separate buses,
• one to communicate with memory and the other with I/O interfaces
• There are four types of commands that an interface may receive. They are
classified as control, status, data output, and data input.
• A control command is issued to activate the peripheral and to inform it what
to do.
• A status command is used to test various status conditions in the interface and
the peripheral. For Example, the computer may wish to check the status of the
peripheral before a transfer is initiated.
• A data output command causes the interface to respond by transferring data
from the bus into one of its registers.
• The data input command is the opposite of the data output. In this case the
interface receives an item of data from the peripheral and places it in its buffer
register.
• There are different types of interfacing techniques are available
i) Isolated I/O
ii) Memory Mapped I/O
Isolated I/O
• Many computers use one common bus to transfer information
between memory or I/0 and the CPU.
• In Isolated I/O, the CPU uses the same buses (wires) to talk to both
memory and I/O devices, but it has separate control signals to tell
whether it’s dealing with memory or an I/O device.
• The distinction between a memory transfer and I/0 transfer is made
through separate read and write lines.
• I/O devices have special addresses called ports.
• When the CPU wants to communicate with an I/O device:
• It puts the port address on the address bus.
• It uses special control lines like I/O Read or I/O Write.
• Then data is sent or received using the data bus.
• As memory and I/O have separate address spaces, it’s called Isolated
I/O. Also, the CPU uses different instructions for memory and I/O
(like IN and OUT for I/O).
The content of the selected register is transfer into the CPU via the data bus when
the I/O read signal is enabled.
The CPU transfer binary information into the selected register via data bus when the
I/O write input is enabled
Advantages of Isolated I/O
• Large I/O Address Space
• Greater Flexibility
• Improved Reliability
Disadvantages of Isolated I/O
• Slower I/O Operations
• More Complex Programming
Memory Mapped I/O
• Memory mapped I/O uses the same address space for both memory
and I/O.
• In a memory-mapped I/O system, there are no special input or output
instructions
• Instead, the CPU uses the same instructions it uses for memory
(like LOAD and STORE) to access I/O devices.
• This design allows I/O and memory to be treated uniformly, simplifying
programming and hardware design.
Advantages of Memory-Mapped I/O
• Faster I/O Operations
• Simplified Programming
• Efficient Use of Memory Space
Disadvantages of Memory-Mapped I/O
• Limited I/O Address Space
• Slower Response Time
 Aspect Isolated I/O Memory-Mapped I/O
Memory and I/O have separate Memory and I/O share the same
Address Space
address spaces address space
Some address space is used for I/O,
Memory Usage All addresses can be used for memory
reducing memory space

Separate instructions for I/O and Same instructions are used for both I/O
Instruction Set
memory read/write operations and memory

Regular memory addresses are used for

I/O Addressing I/O addresses are called Ports
both memory and I/O
More efficient due to separate control Slightly less efficient due to shared
Efficiency
lines and buses resources
Larger hardware due to additional Smaller hardware as fewer buses are
Hardware Size
buses and logic needed
More complex requires separate logic Simpler design I/O is handled like
Design Complexity
for I/O and memory memory
Modes of transfer
• The transfer of data between two units may be done in parallel or serial.
• In parallel data transmission, each bit of the message has its own path
• In serial data transmission each bit in the message is sent in sequence one
at a time.
• Parallel transmission is faster but requires many wires. It is used for short
distances and where speed is important. Serial transmission is slower but
is less expensive since it requires only one pair of conductors.
• Serial transmission can be synchronous or asynchronous.
• Synchronous Data Transfer: In synchronous transmission, the two
units (Sending Unit and Receiving unit) share a common clock
frequency and bits are transmitted continuously at the rate dictated
by the clock pulses.
• Asynchronous Serial Transfer: A serial asynchronous data transmission
technique used in many interactive terminals employs special bits
that are inserted at both ends of the character code. The first bit,
called the start bit, is always a 0 and is used to indicate the beginning
of a character. The last bit called the stop bit is always a 1.
• 3 different Data Transfer Modes between the central computer (CPU
or Memory) and peripherals;

i) Program-Controlled I/O or programmed I/O

ii) Interrupt-Initiated I/O or Interrupt driven I/O

iii) Direct Memory Access (DMA)

Program Controlled I/O:
• The transfer is initiated by the processor.
• Programmed I/O uses the I/O instructions
written in the computer program.
• The instructions in the program initiate every
data item transfer.
• Usually, the data transfer is from a memory
and CPU register.
• This case requires continuous monitoring by
the peripheral device's CPU.(Polling)
INTERRUPT DRIVEN I/O:
• In interrupt driven I/O, the transfer is not initiated by the processor.
• Instead, an I/O device which wants to perform a data transfer with
the processor, must give an interrupt to the processor.
• The processor is free to carry on its own operations.
• Whenever a device wants to transfer data, it will interrupt the
processor.
• Hence interrupt driven I/O is much better than Polled I/O
(Programmed I/O).
INTERRUPT HANDLING MECHANISM
i) When an interrupt occurs, processor, firstly,
finishes the current instruction.
ii) It then suspends the current program and
executes an ISR.
iii) To do so, it Pushes the value of PC (address
of next instruction), into the stack.
iv) Now it loads the ISR address into PC and
proceeds to execute the ISR.
v) At the end of the ISR, it POPs the return
address from the stack and loads it back
into PC.
vi) This is how the processor return to the very
next instruction in the program.
Interrupt Types
i) Hardware Interrupts: Interrupts present in the hardware pins.
ii) Software Interrupts: These are the instructions used in the program
whenever the required functionality is needed.
iii) Maskable Interrupts: These interrupts can be enabled or disabled
explicitly.
iv) Non-maskable interrupts: These are always in the enabled state. we
cannot disable them.
v) External interrupts: Generated by external devices such as I/O.
vi) Internal interrupts: These devices are generated by the internal
components of the processor such as power failure, error instruction,
temperature sensor, etc.
Drawbacks of Programmed and Interrupt-​Driven I/O
• Interrupt-​driven I/O, though more efficient than simple programmed
I/O, still requires the active intervention of the processor to transfer
data between memory and an I/O module, and any data transfer
must traverse a path through the processor.
• Thus, both these forms of I/O suffer from two inherent drawbacks:
• The I/O transfer rate is limited by the speed with which the processor
can test and service a device.
• The processor is tied up in managing an I/O transfer; a number of
instructions must be executed for each I/O transfer
 Role of CPU in transfer of information
Peripheral Device -> CPU -> Memory (With CPU - Programmed & Interrupted I/O)

• CPU limits the speed of transfer

Peripheral Device -> Memory (Without CPU – DMA)

• Transfer speed increases

• Peripheral device manage the memory bus directly.

• DMA (Direct memory Access)

• CPU is idle
DMA BASED I/O
• DMA means transferring data directly between memory and I/O.
without going through the CPU.
• DMA transfers are very fast as compared to Processor based transfers
due to two reasons.
• Thus, we can allow the peripherals directly communicate with each
other using the memory buses, removing the intervention of the CPU.
• This type of data transfer technique is known as DMA or direct
memory access.
• CPU BUS Signals for DMA Transfer BR(Bus Request) Signal, BG(Bus
Grant) Signal – issued by CPU
• 0 --- DMA communicates with CPU,
• 1 ---- DMA communicates with Memory
• DMA Controller sends Bus Request to CPU
• CPU stops execution of current instruction and places address bus,
data bus, read and write lines into high impedance state.
• CPU activates Bus Grant
• After transfer DMA disables BR
• CPU continues normal operation
 DMA Transfer
DMA Request Bus Request Bus grant

• Peripheral device ------> DMA controller -------> CPU --------> DMA controller
• DMA controller puts the current value of its address register onto address
bus, activates RD or WR signal, and --------------> peripheral device
• RD and WR are bidirectional
• BG = 0 => CPU communicates with the internal DMA registers
• BG = 1 => RD and WR are output lines from DMA controller to the RAM to specify read
or write operation for data
Application
• Fast transfer of information between magnetic disk and memory
• High-speed I/O devices
• Inter-chip communication
• Updating the display in an interactive terminal
Types of Direct Memory Access (DMA)
• There are four popular types of DMA.
• Single-Ended DMA: In this type, the DMA controller is connected only to
one device (usually either the memory or the I/O device), and it directly
controls data transfer.
• Dual-Ended DMA: The DMA controller is connected to both the source and
the destination, typically memory and an I/O device.
• Arbitrated-Ended DMA: In systems with multiple DMA devices or masters,
arbitration is needed to decide which device gets control of the bus. It is
more advanced than Dual-Ended DMA.
• Interleaved DMA: Interleaved DMA are those DMA that read from one
memory address and write from another memory address.
Advantages of DMA Controller

• DMA speeds up memory operations and data transfers by allowing

peripherals to communicate directly with memory, bypassing the CPU.

• During data transfer, the CPU is not involved, which significantly reduces its
workload.

• Operates efficiently, requiring very few clock cycles to complete data

transfers.
Disadvantages of DMA Controller

• It increases the overall cost of the system.

• It increases the complexity of the software.

• Costly operation due to the need for additional hardware and control
logic.
Difference between Interrupt Request and DMA request

• When an interrupt occurs, the processor has to suspend the current

program, execute the ISR and then return to the next instruction of
the main program. Hence it is necessary that the processor completes
the current instruction before servicing an interrupt request.
• When a DMA request occurs, the processor has to simply relinquish
(give away) control of the system bus and enter hold state.
Thank You