UNIT-3

1
 Computer Memory
Memory in a computer is
like a storage unit for
programs and data needed
for processing.

The problem: Limited space

in memory (RAM).

Key Issue: Not enough space

in the main memory to hold
all the data and programs a
modern computer uses.

23/09/2025 MS. HAFSA IHTESHAMUDDIN AHMED, [Link] (CSE), STLW(A) 2

Auxiliary Memory (Bottom Level)
These are slower devices with larger storage capacity, like
magnetic disks or tapes. They store data not immediately
needed by the CPU.
Main Memory (Middle Level)
This is the RAM. It’s fast but has limited space and is directly
accessible by the CPU. It stores active programs and data.
Cache Memory (Top Level)
This is the fastest, but also the smallest, memory in the
hierarchy. It’s located between the CPU and RAM and helps
to speed up access to the most frequently used data.

23/09/2025 3
Why Memory
Hierarchy?

▪ Speed
▪ Cost
▪ Performance
Optimization

23/09/2025 4
 Cache Memory
COMPUTER ORGANIZATION & MICROPROCESSOR

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 5

What is Cache Memory
Cache memory is a small, high-speed memory located
between the CPU and the main memory (RAM). It stores
frequently accessed instructions and data to speed up
processing by reducing the time it takes for the CPU to
access data.

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 6

How Cache Memory Works
▪ Fetching Data
Cache Hit: If the data is found in the cache
Cache Miss: If the data is not in the cache
▪ Block Transfers
▪ Improving Performance with High Hit Ratio
Hit Ratio is the percentage of times the CPU accesses
the cache successfully.

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 7

Example of Access Times:
◦ Cache access time: 100 ns
◦ Main memory access time: 1000 ns
◦ If the hit ratio is 0.9 (90%), the average access time
would be:
=(0.9×100 ns)+(0.1×1000 ns)
=90 ns+100 ns
=200 ns

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 8

Mapping Cache Memory
The data from main memory must be mapped into the cache. There
are three main types of mapping techniques used to organize this
data:
Associative Mapping:
Any word from main memory can be placed in any line in the cache.
Direct Mapping:
Each block of memory is mapped to a specific cache line. For
example, block 0 from main memory might always go into line 0 of
the cache.
Set-Associative Mapping:
A compromise between associative and direct mapping. Cache lines
are grouped into sets, and each memory block maps to a specific set
but can go into any line within that set.

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 9

Technique Description Pros Cons
Any word can go Flexible,
Associative Complex,
into any cache efficient for
Mapping slower search.
line. specific cases.

Each memory
Simple, fast Cache conflicts
Direct block maps to a
implementation with frequent
Mapping specific cache
. blocks.
line.

Combines both
Set-Associ More complex
methods: blocks More efficient,
ative than direct
map to sets, not fewer conflicts.
Mapping mapping.
lines.

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 10

Associative Mapping in
Cache Memory
Definition:
◦ Any block of data from main memory can be stored
in any location in the cache, providing flexibility
compared to other mapping techniques.
Key Benefit:
◦ Efficient and flexible cache organization improves
memory access speeds.

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 11

How Does Associative
Mapping Work?
Address Breakdown:
◦ Tag: Identifies the data block being accessed.
◦ Block/Word: The actual data being fetched.

Cache Search:
◦ CPU sends a memory address to the cache.
◦ Cache searches all slots for a matching tag.

Cache Hit/Miss:
◦ Hit: Data is retrieved from the cache.
◦ Miss: Data is fetched from main memory and placed
in the cache.

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 12

Associative
Mapping in
Cache
(All numbers
is Octal)

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 13

Replacement Policy &
Example
Replacement Policy:
◦ FIFO (First-In, First-Out
◦ Least Recently Used (LRU)
◦ Random Replacement
Example:
◦ CPU Address (15 bits)
◦ Data in Main Memory
◦ Process:
◦ CPU sends address to cache.
◦ Cache searches for a matching tag.
◦ If no match, data is fetched from memory and placed
in cache.

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 14

Example of Cache
Organization
In the case of a cache with
512 words and main memory
with 32K words:
CPU Address: The CPU sends
a 15-bit address.
Tag
Cache Lookup

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 15

Example of Cache
Organization

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 16

Direct Mapping in Cache
Memory
Each block of main memory maps to exactly one cache
location
Simple and cost-effective but can lead to performance
issues when multiple memory blocks map to the same
cache line.
How It Works:
Memory address split into Tag (identifies the data) and
Index (specifies the cache line).
Cache Access: CPU uses index bits to access [Link] tags
match, it's a cache hit; otherwise, it's a cache miss and
data is fetched from memory

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 17

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 18
 Example of Direct Mapping
CPU Request for Address 00000:The
CPU sends memory address [Link]
index part of the address is 000 (this will
be used to check which cache line to
access).
The tag is 00 (this will be used to
compare with the tag stored in the
cache).
The cache looks at Index 000:
Index 000 in the cache has Tag 00 and
data 1220.
Since the tag matches, this is a cache
hit, and the data (1220) is fetched from
the cache.

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 19

 Example of Direct Mapping
CPU Request for Address 02777:
The CPU now requests memory address
02777.
The index part of the address is 777 (this
will be used to check cache line 777).
The tag is 02 (this will be compared with
the tag stored in cache).
The cache looks at Index 777:
Index 777 in the cache has Tag 02 and
data 6710.
Since the tag matches, this is another
cache hit, and the data (6710) is fetched
from the cache.

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 20

 Example of Direct Mapping
Step 3: Cache Miss and
Replacement
if the CPU requests memory
address 01000:
◦ The index part is 000 (this will
point to Index 000 in the
cache).
◦ The tag part is 01 (this does not
match the tag stored in Index
000, which is 00).
◦ This results in a cache miss.
◦ The cache line at Index 000 will
be replaced with the new data
from main memory (3450 for
address 01000).

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 21

 Direct Mapping Cache with
Block Size of 8 Words
Memory Address Breakdown (15-bit
address):
Tag (6 bits): Identifies the memory block.
Index (6 bits): Points to the specific cache
line (64 lines).
Word Offset (3 bits): Selects one of 8 words
within the cache block.
Word Offset determines which word in the
block to retrieve.
Cache Access: Index selects the cache line.
Tag verifies if the data in the cache matches
the required block.

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 22

Set-Associative Mapping
A two-way set-associative cache is a compromise between:
◦ Direct-mapped cache (each block maps to only one location)
◦ associative cache (a block can be stored anywhere).
In two-way set-associative mapping:
Cache is divided into sets.
Each set has 2 lines (or “ways”).
A memory block can go into either of the 2 lines of its set.
Replacement policy (LRU, FIFO, etc.) decides which line to replace if
the set is full.

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 23

2-way
Set-Associat
ive
Mapping
Looking at Index = 000:
Way 1:
◦ Tag = 01
◦ Data = 3450
Way 2:
◦ Tag = 02
◦ Data = 5670
Two different memory
blocks (with tags 01 and
02) are stored in the
same cache set (index
000).

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 24

Write Policies and Cache
Initialization
Write Policies:
◦ Write-Through: Updates both cache and main
memory simultaneously.
◦ Write-Back: Updates only the cache and later writes
the data to main memory when the block is evicted.
Cache Initialization:
◦ Valid Bit: Each cache word has a valid bit to track if
the data is valid.
◦ Cache Initialization: On startup, the cache is cleared
and invalid data is replaced as it is filled with valid
data.

23/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 25

 Virtual Memory
COMPUTER ORGANIZATION & MICROPROCESSOR

26/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 26

Introduction
▪ In a computer system with a memory hierarchy,
programs and data are initially stored in auxiliary
memory (such as a hard disk).
▪ Portions of the program or data are brought into main
memory (RAM) only when the CPU needs them.
▪ Virtual memory is a concept used in large computer
systems that allows users to run programs as if a large
memory space is available, equal to the total auxiliary
memory.

26/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 27

What is
Virtual
Memory

26/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 28

▪ Every address referenced by the CPU is translated from a
virtual address to a physical address in main memory
using a process called address mapping.
▪ This provides an illusion of a very large memory even
when the actual main memory is relatively small.
▪ The translation happens dynamically during program
execution and is managed automatically by hardware
using a mapping table.

Question:
Why can’t the CPU just access auxiliary memory
directly for every operation?

26/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 29

Address Space and Memory
Space
▪ The address used by a programmer or CPU is called a
virtual address, and the collection of all virtual addresses
is called the address space.
▪ An address in the main memory is called a physical
address or location, and the collection of all physical
addresses is called the memory space.

26/09/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 30

Address Mapping Using
Pages
The address mapping process is easier when the address
space and memory space are divided into equal -sized
partitions.
Memory space is divided into equal-sized groups called
blocks.
Address space is divided into groups of the same size
called pages.
Programs are divided into pages too, which are moved
from auxiliary memory to main memory as whole pages.

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 31

Example
▪ Consider a computer with main memory of 32K words.
To specify any physical address in this memory, 15 bits
are needed since 32K = 2^15.
Auxiliary memory may be able to store 1024K words
(2^20 words), which is equivalent to 32 times the main
memory capacity.
Let N = address space = 1024K (2^20)
Let M = memory space = 32K (2^15)
▪ In this system, the address space (N) is much larger than
the physical memory space (M).

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 32

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 33
Question:
If the physical memory is smaller than
the address space, how can the
system run programs larger than
Main memory /RAM?

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 34

 Pages & Blocks
Example
Consider a computer with
an address space of 8K
words and a memory space
of 4K words.
Divide both into groups of
1K words:
Address space → 8 pages
Memory space → 4 blocks

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 35

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 36
06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 37
Question
What is the difference between a page
and a block?

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 38

Memory-Page Table
Organization
▪ The memory-page table holds one word for each page.
▪ The table index is the page number, and the table entry
contains the block number where the page is stored in
physical memory.
▪ A presence bit indicates whether the page is in main
memory (1) or still in auxiliary memory (0).

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 39

Virtual Address Translation
Process
The CPU sends a 13-bit virtual address.
The high 3 bits index the page table; the entry gives the block number.
If the presence bit is 1, the block number is combined with the line
number (low 10 bits) to form the physical address.
If the presence bit is 0, a page fault occurs: the operating system must
fetch the required page from auxiliary memory before continuing.

Question:
What happens when the presence bit in the page
table is 0?

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 40

Problem with Traditional
Memory Page Tables
1. Memory Page Table Overview:
Memory is divided into pages (virtual memory) and blocks (physical
memory).
A page table maps virtual pages to physical memory blocks.
2. Inefficiency in Regular Page Tables:
Many empty entries in the page table because physical memory has
fewer blocks than the number of pages.
Example:
◦ 1024 pages, 32 blocks.
◦ 1024 entries needed for the page table, but only 32 blocks are used,
leaving 992 empty entries.
Wastes memory and storage space.

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 41

Associative Memory Page
Table
▪ A more efficient way to organize the page table would be
to construct it with a number of words equal to the
number of blocks in main memory.
▪ In this way the size of the memory is reduced and each
location is fully utilized.

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 42

 Example
The page field in each
word is compared with the
page number in the virtual
address.
If a match occurs, the
word is read from memory
and its corresponding
block number is extracted.

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 43

Page Fault
▪ If page not available in main memory, page fault occurs.
▪ The system fetches page from auxiliary memory and
stores in main memory for execution.
▪ What happens if main memory is completely full?

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 44

Page Replacement
Virtual memory systems combine hardware and software to
manage memory efficiently.
The memory management software decides:
▪ Which page to remove when memory is full.
▪ When to bring in a new page.
▪ Where to place the new page in memory.
When a program references a page not in main memory
(page fault), execution is suspended, and the OS loads the
needed page, possibly removing another page first.

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 45

Replacement Algorithms
First-In, First-Out (FIFO)
Removes the page that has been in memory the longest.
Uses a queue (FIFO stack) to track page order.
Easy to implement but may remove pages still frequently used, causing
frequent page faults.
Least Recently Used (LRU)
Removes the page that has not been used for the longest time.
More complex to implement but generally more efficient.
Uses counters or timestamps to track usage; counters increase with
time, reset to zero when page is used.

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 46

 Question:
Which page replacement algorithm is simpler to
implement?

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 47

Summary
Term Meaning
Illusion of large memory by using main +
Virtual Memory
auxiliary memory
Virtual Address Address generated by programmer/CPU
Address Space Set of all virtual addresses
Physical Address Actual address in main memory
Memory Space Set of all physical addresses
Address Dynamic translation of virtual address to
Mapping physical address
The term page refers to groups of address
Page
space of the same size.
Block/Page The physical memory is broken down into
Frame groups of equal size called blocks

06/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 48

Memory Management
Hardware
▪ In a multiprogramming environment where many
programs reside in memory it becomes necessary to
move programs and data around the memory.
▪ A memory management system is a collection of
hardware and software procedures for managing the
various programs residing in memory.
▪ The memory management software is part of an overall
operating system available in many computers. Here we
are concerned with the hardware unit associated with
the memory management system.

07/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 49

Components of MMU
1. A facility for dynamic storage relocation that maps logical
memory references into physical memory addresses
2. A provision for sharing common programs stored in
memory by different users
3. Protection of information against unauthorized access
between users and preventing users from changing operating
system functions

07/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 50

Segments
▪ It is more convenient to divide programs and data into
logical parts called segments.
▪ A segment is a set of logically related instructions or data
elements associated with a given name.
▪ Segments may be generated by the programmer or by
the operating system.
▪ Examples of segments are a subroutine, an array of data,
a table of symbols, or a user’s program.

07/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 51

Logical Address
▪ The address generated by a segmented program is called a logical
address.
▪ This is similar to a virtual address except that logical address space is
associated with variable-length segments rather than fixed-length
pages.
▪ The logical address may be larger than the physical memory address
as in virtual memory, but it may also be equal, and sometimes even
smaller than the length of the physical memory address.
▪ The function of the memory management unit is to map logical
addresses into physical addresses similar to the virtual memory
mapping concept.

07/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 52

Segmented Page Mapping
• The segment field
specifies a
segment number.

• The page field

specifies the page
within the
segment

• The word field

gives the specific
word within the
page.
07/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 53
07/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 54
 Translation Lookaside Buffer
(TLB)
To reduce delay, use Translation
Lookaside Buffer (TLB)
◦ Fast associative memory
◦ Stores recently referenced
segment & page entries

Associative search with segment

and page numbers
On match (TLB hit): fast access
On miss:
◦ Use table mapping , Store
result in TLB for future
references

07/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 55

 Regular Mapping (Without
TLB)
CPU generates a logical address (Segment, Page, Word)
To translate to physical address:
▪ Access Segment Table → get Page Table Base
▪ Access Page Table → get Physical Frame Number
▪ Access Main Memory → get actual data

Downsides:
Requires 3 memory accesses for each instruction/data access.
▪ This triples memory latency
▪ Increases CPU wait time
▪ Inefficient, especially for high-frequency memory operations

07/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 56

TLB-Based Mapping (With
Translation Lookaside Buffer)
TLB is a fast, small associative memory inside the CPU
Stores recently used segment-page → frame mappings
CPU checks TLB first before going to segment/page tables
If TLB Hit (mapping is found):
▪ Translation is instant (1 memory access)
If TLB Miss:
▪ Falls back to regular mapping
▪ After that, the mapping is loaded into TLB for future use

07/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 57

Memory Protection
Memory protection can be assigned to the physical address
or the logical address.
Physical Address Level:
▪ Protection bits are added to memory blocks
▪ Not ideal-must be updated whenever memory is moved

Logical Address Level (Preferred):

▪ Protection info is stored in segment descriptors.
▪ Easier to manage and more secure

07/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 58

▪ The base address field gives the base of the page table
address in a segmented-page [Link] is the
address used in mapping from a logical to the physical
address.
▪ The length field gives the segment size by specifying the
maximum number of pages assigned to the segment.

07/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 59

The protection field in a segment descriptor specifies the
access rights available to the particular segment.

•Full Read/Write – For program’s own data/code

•Read Only – Shared system utilities, not editable
•Execute Only – Program can run but not be read or
copied
•System Only – Access restricted to operating system

07/10/2025 Ms. Hafsa Ihteshamuddin Ahmed, Assistant Professor (CSE), STLW(A) 60