Memory Management: Basic bare machine, Resident monitor, Multiprogramming with fixed

partitions, Multiprogramming with variable partitions, Protection schemes, Paging,

Segmentation, Paged segmentation, Virtual memory concepts, Demand paging,
Performance of demand paging, Page replacement algorithms, Thrashing, Cache memory
organization, Locality of reference.

Memory Management is a core function of operating systems (OS) that handles or

manages primary memory. The goal is to allocate memory to processes efficiently and
ensure the system runs smoothly and reliably.

Memory management is the process of controlling and coordinating computer memory,

assigning portions called blocks to various running programs to optimize overall system
performance.

Functions of Memory Management

Allocation and Deallocation: Assigns memory to processes and reclaims it after use.
Tracking: Keeps track of each byte in a computer’s memory.
Protection: Prevents one process from accessing another's memory.
Swapping: Moves data between RAM and disk to free memory.

Bare Machine
A Bare Machine is the most primitive form of a computing system. It refers to a computer
system without any operating system (OS) or supporting software — just the hardware
and a minimal set of instructions.

Definition: A bare machine is a computer system with no operating system, no user

interface, and no protection mechanisms. Programs must be loaded manually and interact
directly with hardware.

Key Characteristics
Feature Description

No Operating System Programs run directly on hardware without OS services.

Manual Operation Input/output must be managed manually (e.g., through switches

or punch cards).

Low-level Programming Typically uses assembly or machine language.

No Protection All programs have full access to all hardware resources

(memory, I/O).
 Simple or No I/O Often limited or no input/output facilities.

Example Usage
Early computers like ENIAC, IBM 701.
Embedded systems in microcontrollers where software runs close to the hardware.
Bootloaders and early stages of system boot-up (e.g., BIOS in PCs).

Advantages
Simple and transparent.
Faster for small tasks (no OS overhead).
Useful for understanding hardware and low-level programming.

Disadvantages
No multitasking.
High risk of errors or crashes.
Poor resource management.
Manual effort for loading and managing programs.

Resident Monitor
A Resident Monitor is an early form of operating system software that resides
permanently in memory and controls the execution of programs. It was one of the first
steps toward automating program execution and managing resources in early computing
systems.

Definition: A Resident Monitor is a small program permanently loaded into memory that:

Controls job execution

Manages input/output (I/O)
Loads and transfers control to user programs
Returns control to itself once the program finishes

It was “resident” because it stayed in memory at all times.

Functions of Resident Monitor

Function Description

Job Sequencing Automatically loads and runs user jobs one after another

I/O Management Handles basic input/output operations

Memory Cleanup Clears memory and prepares the system for the next job

Control Transfer Transfers control to a user program and regains it after execution
 Error Handling Reports simple errors (e.g., invalid instructions)

How It Works
Monitor loads a program from punch cards, tape, or disk.
Transfers control to the user program.
Program executes and ends with a special instruction (e.g., HALT).
Control returns to the monitor.
Monitor clears memory and loads the next job.

Structure
Resident portion: Stays in memory, handles control and I/O.
Transient portion: Space for user programs that change job-to-job.

Advantages
Automates execution of multiple jobs (vs manual loading).
Introduces basic job control language (JCL).
Enables batch processing.

Disadvantages
No true multitasking or process isolation.
Inefficient memory usage (part of memory always occupied by monitor).
Limited user protection.

Example IBM 1401 used a resident monitor to load and execute programs from punched
cards in batch mode.

NOTE : Memory Allocation Techniques

● Contiguous Allocation:
Fixed-size or variable-size partitions.
Pros: Simple, fast access.
Cons: Fragmentation (internal/external).

● Non-Contiguous Allocation:
Paging and segmentation.
Solves fragmentation problems.

Multiprogramming with fixed partitions, Multiprogramming with variable

partitions
In multiprogramming, the most important methods of memory management include Fixed
and Variable Partitioning. Under Fixed Partitioning memory is divided into partitions which
are fixed whereas under Variable Partitioning memory partition is varied based on process
size. Each has its advantages and disadvantages as to flexibility, efficiency, and the ease of
using the system and is therefore appropriate for a given system.

What is Fixed Partitioning?

Fixed Partitioning is a contiguous memory management technique in which the main
memory is divided into fixed sized partitions which can be of equal or unequal size.
Whenever we have to allocate a process memory then a free partition that is big enough to
hold the process is found. Then the memory is allocated to the process.If there is no free
space available then the process waits in the queue to be allocated memory. It is one of the
oldest memory management techniques which is easy to implement.

Advantages of Fixed Partitioning

● Simplicity: Since partitions are already defined, it is easy to assign memory to a

process especially when it is designed that way.

● Ease of Implementation: This makes the partitioning method very easy to

implement especially since it only requires partitioning of a few segments.

Disadvantages of Fixed Partitioning

● Internal Fragmentation: If a process is not able to fill a partition it uses then

there is space left in that partition which is not utilized.

● Inefficient Memory Utilization: The size of partitions is fixed and therefore large
processes might occupy more space while small processes occupy inadequate
large space.

● Limited Process Size: Quantities greater than the size of the largest partition
cannot be performed; this decreases flexibility.

What is Variable Partitioning?

Variable Partitioning is a contiguous memory management technique in which the main
memory is not divided into partitions and the process is allocated a chunk of free memory
that is big enough for it to fit. The space which is left is considered as the free space which
can be further used by other processes. It also provides the concept of compaction. In
compaction the consecutive spaces that are free and the spaces which are not allocated to
the process are combined and a single large memory space is made.

Advantages of Variable Partitioning

● Efficient Memory Utilization: Memory is allocated dynamically; this means that

it can be used sparingly thus avoiding the use of much space on the available
memory.

● No Process Size Limitation: One advantage of this is an absence of sharp

partitions because memory is allocated as per the processes requirements.

● Higher Degree of Multiprogramming: It also stated that process flexibility for

memory can be suitable for more processes.

Disadvantages of Variable Partitioning

● External Fragmentation: Any time memory space is granted and then recalled
for someone else to free, space of maximum un-utilized portions of memory are
created termed as external fragmentation leading to poor memory utilization.
 ● Complexity: Fixed partitioning and its related concepts are far simpler to handle
and control as compared to variable partitions and external fragmentation.

Difference between Fixed Partitioning and Variable Partitioning

Fixed Partitioning Variable Partitioning

Memory is divided into fixed-sized Memory is allocated dynamically in

partitions. varying sizes.

Only one process can be placed in A process is allocated a chunk of free

each partition. memory as needed.

Inefficient memory utilization due to More efficient memory utilization with less
internal fragmentation. internal fragmentation.

Internal and external fragmentation

Only external fragmentation occurs.
occurs.

Higher degree of multiprogramming due

Limited degree of multiprogramming.
to flexible allocation.

Easier to implement. More complex to implement.

Restricts process size based on

No size limitation on processes.
partition size.

Conclusion

So, Fixed Partitioning and Variable Partitioning both are high memory management
strategies used under multiprogramming. However, compared to Fixed Partitioning, it is
simpler and easier to implement and it can cause inefficiency and has less flexibility at the
same time. However, Variable Partitioning uses even less memory and can manage larger
processes; on the flip side, the procedure is more monumental and may lead to external
fragmentation. The decision whether to use one technique or the other depends with the
requirement of the system in terms of simplicity, memory required, and flexibility required in
the processes

NOTE : Difference between Internal and External fragmentation

What is Internal Fragmentation?

Internal fragmentation happens when the memory is split into mounted-sized blocks.
Whenever a method is requested for the memory, the mounted-sized block is allotted to the
method. In the case where the memory allocated to the method is somewhat larger than the
memory requested, then the difference between allotted and requested memory is called
internal fragmentation. We fixed the sizes of the memory blocks, which has caused this
issue. If we use dynamic partitioning to allot space to the process, this issue can be solved.

The above diagram clearly shows the internal fragmentation because the difference between
memory allocated and required space or memory is called Internal fragmentation.

What is External Fragmentation?

External fragmentation happens when there's a sufficient quantity of area within the memory
to satisfy the memory request of a method. However, the process’s memory request cannot
be fulfilled because the memory offered is in a non-contiguous manner. Whether you apply a
first-fit or best-fit memory allocation strategy it'll cause external fragmentation.

In the above diagram, we can see that there is enough space (55 KB) to run a process-07
(required 50 KB) but the memory (fragment) is not contiguous. Here, we use compaction,
paging, or segmentation to use the free space to run a process.

Protection Schemes in Memory Management

Protection schemes are methods used by operating systems to ensure that each process
accesses only its own memory and does not interfere with the memory or resources of
other processes or the OS itself.

These mechanisms are critical for system stability, security, and multitasking.

Goals of Memory Protection

Prevent a process from accessing memory it does not own.
Isolate each process's memory space.
Protect the operating system and shared resources.
Enable controlled sharing between processes if necessary.

Main Protection Techniques

Paging-Based Protection
Segmentation-Based Protection

Paging
Paging is a memory management scheme that eliminates the need for contiguous allocation
of physical memory. In paging, the physical memory is divided into fixed-size blocks called
frames, and the logical memory (used by processes) is divided into blocks of the same size
called pages. When a process is loaded into memory, its pages can be loaded into any
available memory frames, and a page table keeps track of the mapping between the
process’s pages and the physical frames.

This allows the physical address space to be non-contiguous, which solves the problem of
external fragmentation and makes it easier to allocate memory efficiently. Paging also
simplifies memory management by eliminating the need for complex allocation algorithms.

Page Table Structure

The page table is a data structure used in paging to store the mapping between virtual
addresses and physical addresses. Each entry in a page table corresponds to a page of the
process's logical address space and contains the address of the frame in physical memory
where the page is stored.
Page tables can be implemented in several ways, including single-level, multi-level, and
inverted page tables. A single-level page table is a simple array, but it can become very
large if the address space is large.

Advantages:
● Avoids gaps between allocated memory blocks, ensuring efficient use of available
memory.
● Pages can be placed anywhere in physical memory, simplifying memory allocation.
● Fixed-size pages mean that memory allocation does not require complex algorithms.
● Allows larger programs to run even with limited physical memory.
● Virtual memory allows parts of a program to be stored on disk and brought into
memory as needed.

Disadvantages:
● Each process requires a page table, which can consume a lot of memory for large
address spaces.
● Each memory access requires a lookup in the page table, which can add delay.
● Unused space in the last page of a process can lead to internal fragmentation.

Address Calculation

Logical Add = p,d

Physical Add = F * P + d
p = Logical Add / P
d = Logical Add % P

NOTE, P = page No
P = Page size
F = Frame No

Segmentation:
Segmentation is a memory management technique that divides the process's memory into
variable-sized segments, each of which can be a logical unit such as a function, array, or
data structure. Unlike paging, segments vary in length, reflecting the logical structure of the
process.

Each segment has a segment number and a length, and memory addresses within a
segment are specified by an offset from the segment's base address.

A segment table keeps track of each segment's base address and length. Segmentation
facilitates sharing and protection, as segments can be independently protected and shared
between processes, enhancing modularity and security.

Advantages:
● Improves program readability and manageability.
● Each segment can have its own access rights, enhancing security.
● Reduces wasted space within segments.

Disadvantages:
● Can suffer from external fragmentation.
● Requires more complex algorithms for allocation and deallocation.

Address Calculation
NOTE, If d<limit, then ok
Otherwise not allow due to protection

Paging vs Segmentation

Feature Paging Segmentation

Memory Division Fixed-sized blocks called pages Variable-size blocks called

segments

Physical Memory Divided into frames of the same Divided into segments of varying
size as pages sizes

Address Structure Single-level address with page Two-level address with segment
number and offset number and offset

Fragmentation Eliminates external Can lead to external

fragmentation, may cause fragmentation, but no internal
internal fragmentation within fragmentation
pages

Logical Division Divides memory without Divides memory according to

considering logical structure logical structure (e.g., functions,
arrays)

Ease of Simpler due to fixed-size pages More complex due to variable-

Management size segments

Protection and Easier to manage protection and More intuitive for logical
Sharing sharing at page level groupings but complex

Memory Access Uniform size makes access time Variable sizes can lead to
consistent varying access times

Use Case Commonly used in modern Less common, used for specific
operating systems applications requiring logical
division
Paged Segmentation
Paged Segmentation combines paging and segmentation, taking advantage of both
schemes to provide flexibility, efficiency, and protection in memory management.

● Proces —-----> Segments —----> Pages —----> stored to main memory

Why Combine Paging and Segmentation?

Paging Segmentation

Solves external fragmentation Logical division of memory (code/data/stack)

Difficult to match logical program structure Better reflects program's organization

Internal fragmentation (last page) External fragmentation

Paged Segmentation provides logical structure (from segmentation)

and efficient memory use (from paging).

How Paged Segmentation Works

1. Each process has a segment table.

2. Each segment is divided into pages.

3. A page table is maintained for each segment.

Logical addresses have three components:

Logical Address = [Segment Number | Page Number | Offset]
Address Translation Process:

1. Extract Segment Number (s) from logical address.

2. Look up Segment Table[s] to get:

○ Base address of the segment’s page table.

3. Use Page Number (p) to index into the page table and find the Frame Number (f).

4. Combine Frame Number + Offset to get the physical address.

Address Structure:
+-------------------+----------------+--------------+

| Segment Number (s)| Page Number (p)| Offset (d) |

+-------------------+----------------+--------------+

Tables Used:

● Segment Table → Pointer to page table of the segment.

● Page Table (per segment) → Maps pages to frames.

Example Imagine a program with:

● Segment 0: Code

● Segment 1: Data

● Segment 2: Stack

Each is divided into pages and loaded in different frames of physical memory.

So a logical address [1 | 3 | 20] means:

● Segment 1 (Data)

● Page 3 of that segment

● Offset 20 bytes

The OS translates it to a physical address like:

Segment 1 → Page Table Base: 0x3000

Page 3 → Frame 9 → Frame Start: 0x9000

Final Address = 0x9000 + 20 = 0x9014

Advantages of Paged Segmentation

Feature Benefit

Logical structure Easy to separate code, data, stack, etc.

Efficient memory use Paging prevents external fragmentation

Fine-grained protection Per-segment and per-page permissions

Supports virtual memory Easily fits into modern memory models

Disadvantages

Limitation Description

Increased complexity Requires multiple tables (segment + page)

Overhead More address translation steps

Hardware support needed Needs MMU with segment + page translation

Virtual Memory Concepts

Virtual Memory is a memory management technique that gives processes the illusion of
having more memory than physically available by using disk space as an extension of
RAM.

It allows a computer to run large or multiple applications simultaneously even if the

system doesn’t have enough physical memory (RAM) to hold them all at once.

What is Virtual Memory?

● Definition: Virtual memory is a logical abstraction where each process gets its
own large, continuous memory space.

● Backed by: A combination of RAM + disk (usually a swap file or partition).

● Managed by: The Operating System (OS) and Memory Management Unit (MMU).

Key Concepts and Components

Virtual Address Space

● The total memory a process can use.

● Typically much larger than physical memory.

● Divided into pages (just like physical memory).

Page Table

● Maps virtual pages to physical frames.

● Maintains access rights and presence (whether the page is in memory or on disk).

Demand Paging

● Pages are loaded into memory only when accessed.

● If a page is not in RAM, a page fault occurs, and it is loaded from disk.

Swap Space

● A portion of the disk used to store inactive pages.

● Also called a swap file or pagefile.

How Virtual Memory Works

1. Process generates a virtual address.

2. MMU translates it to a physical address using the page table.

3. If the page is in RAM, continue.

4. If page not in RAM → Page Fault:

○ OS pauses the process.

○ Loads the page from disk into RAM.

○ Updates the page table.

○ Resumes process.

Benefits of Virtual Memory

Benefit Explanation

Larger memory space Run programs bigger than physical memory

Process isolation Each process has its own virtual space

Efficient multitasking Processes can be swapped in/out as needed

Simplifies programming Developers don’t worry about physical memory

Memory protection Prevents one process from accessing another’s memory

Overheads and Challenges

Limitation Description

Page faults Cause delays (disk is much slower than RAM)

Thrashing Excessive paging → low performance

Management complexity Requires hardware (MMU) and OS coordination

Example of Address Translation

Logical Address:
Virtual Address = [Page Number | Offset]

● Page Table maps Page Number → Frame Number

● Physical Address = Frame Base + Offset

Virtual vs Physical Memory

Feature Virtual Memory Physical Memory (RAM)

Size Much larger (includes disk) Limited to installed RAM

Isolation Process-specific Shared

Speed Slower (if disk is used) Fast

Management Handled by OS + MMU Managed by hardware directly

Demand Paging
Demand Paging is a virtual memory management technique where pages are loaded into
RAM only when needed (on demand), rather than pre-loading the entire process into
memory.

It is a lazy loading strategy used to save memory and improve efficiency.

How Demand Paging Works

1. A process is started with only some pages loaded into memory.

2. When the process accesses a page that’s not in memory, a page fault occurs.

3. The OS:
 ○ Pauses the process.

○ Loads the required page from disk (swap space).

○ Updates the page table.

○ Resumes execution.

Steps in a Page Fault

[1] Process references page X

[2] Page Table → Page not in memory (invalid bit)

[3] Page Fault trap to OS

[4] OS locates page X on disk

[5] Page X loaded into a free frame

[6] Page Table updated

[7] Process resumes at the faulting instruction

Performance of Demand Paging

Effective Access Time (EAT):

The performance of demand paging is influenced by how often page faults occur.

Let:

● ma: Memory access time (typically ~100 ns)

● pf: Page fault rate (0 ≤ pf ≤ 1)

● pt: Page fault service time (in ms)

Then:

EAT=(1−pf)×ma+pf×pt

Ideal Case:

If pf=0 (no page faults):

EAT=ma

Worst Case:
If pf is high (e.g., 0.1 or 10%), and pt is large (e.g., 10 ms):

EAT=0.9×100 ns+0.1×10 ms=0.09 μs+1 ms≈1 ms

This is 10,000× slower than memory access

Factors Affecting Performance

Factor Impact

Page Fault Rate Most critical; should be kept very low

Page Size Too small → more faults; too large → waste

RAM

Page Replacement Bad policy increases page faults (e.g., FIFO vs LRU)
Policy

Working Set Size If working set doesn’t fit in RAM → more faults

Disk Speed Slower disk = slower page fault service time

Thrashing
When too many page faults occur, the system spends more time swapping pages than
executing processes → severe performance degradation.

Symptoms of Thrashing:
● High CPU idle time

● Low CPU utilization

● Constant disk activity

Optimizing Demand Paging Performance

1. Minimize page faults:

○ Good page replacement algorithms (e.g., LRU, Clock)

○ Load frequently used pages proactively

2. Use Locality of Reference:

○ Programs tend to access a few pages repeatedly (working set)

3. Increase physical memory:

○ Reduces need for page replacement

 4. Efficient disk I/O:

○ SSDs significantly reduce page fault service time

Summary

Feature Description

Demand Paging Load pages only when needed

Page Fault Triggered on accessing non-resident page

EAT Formula EAT=(1−pf)×ma+pf×pt

Performance Goal Keep page fault rate as low as possible

Thrashing Excessive page faults → system slowdown

Locality of Reference
Locality of Reference is a fundamental principle in computer memory systems, particularly
in caching and virtual memory, which states that computer programs tend to access a
small portion of memory repeatedly over short periods of time.

This principle explains why cache memory and demand paging work effectively.

Types of Locality: There are three main types of locality:

1. Temporal Locality (Time-based)
Definition: If a memory location is referenced now, it is likely to be referenced again
soon.
Example: Loop counters, variables in a loop, recently used functions.
Reason: Programs often use the same data/instructions multiple times during
execution.

2. Spatial Locality (Space-based)

Definition: If a memory location is referenced, nearby memory locations are likely to be
referenced soon.
Example: Iterating through an array or accessing fields of a struct.
Reason: Code and data are typically stored and accessed in contiguous memory
blocks.

3. Sequential Locality
Definition: A special case of spatial locality—memory is accessed in a linear or
sequential order.
Example: Reading a file into memory, fetching instructions from RAM.

Why It Matters

Used In How Locality Helps

 Cache memory Increases hit rate by storing recent data

Paging Reduces page faults by loading nearby pages

Prefetching Predicts future accesses based on patterns

Compiler optimization Reorders code to improve locality

Example
for (int i = 0; i < 1000; i++) {

sum += array[i];

Temporal: sum is accessed repeatedly.

Spatial: array[i] accesses consecutive memory locations.
Sequential: Iterates through array[] linearly.

Page Replacement Algorithms

Page replacement algorithms are techniques used in operating systems to manage memory
efficiently when the physical memory is full. When a new page needs to be loaded into
physical memory, and there is no free space, these algorithms determine which existing
page to replace.
If no page frame is free, the virtual memory manager performs a page replacement
operation to replace one of the pages existing in memory with the page whose reference
caused the page fault. It is performed as follows: The virtual memory manager uses a page
replacement algorithm to select one of the pages currently in memory for replacement,
accesses the page table entry of the selected page to mark it as “not present” in memory,
and initiates a page-out operation for it if the modified bit of its page table entry indicates that
it is a dirty page.
Common Page Replacement Techniques
● First In First Out (FIFO)

● Optimal Page replacement

● Least Recently Used (LRU)

● Most Recently Used (MRU)

First In First Out (FIFO)

This is the simplest page replacement algorithm. In this algorithm, the operating system
keeps track of all pages in the memory in a queue, the oldest page is in the front of the
queue. When a page needs to be replaced, the page in the front of the queue is selected for
removal.
Example 1: Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3-page frames. Find the
number of page faults using FIFO Page Replacement Algorithm.

Initially, all slots are empty, so when 1, 3, 0 come they are allocated to the empty slots ---> 3
Page Faults.
when 3 comes, it is already in memory so ---> 0 Page Faults. Then 5 comes, it is not
available in memory, so it replaces the oldest page slot i.e 1. ---> 1 Page Fault. 6 comes, it
is also not available in memory, so it replaces the oldest page slot i.e 3 ---> 1 Page Fault.
Finally, when 3 comes it is not available, so it replaces 0 1-page fault.

Optimal Page Replacement

In this algorithm, pages are replaced which would not be used for the longest duration of
time in the future.
Example: Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-page
frame. Find number of page faults using Optimal Page Replacement Algorithm.
Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots ---> 4 Page
faults
0 is already there so ---> 0 Page fault. when 3 comes it will take the place of 7 because it is
not used for the longest duration of time in the future---> 1 Page fault. 0 is already there so
---> 0 Page fault. 4 will take place of 1 ---> 1 Page Fault.

Now for the further page reference string ---> 0 Page fault because they are already
available in the memory. Optimal page replacement is perfect, but not possible in practice as
the operating system cannot know future requests. The use of Optimal Page replacement is
to set up a benchmark so that other replacement algorithms can be analyzed against it.
Least Recently Used
In this algorithm, a page will be replaced which is least recently used.
Example: Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-
page frames. Find number of page faults using LRU Page Replacement Algorithm.

Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots ---> 4 Page
faults
0 is already there so ---> 0 Page fault. when 3 came it will take the place of 7 because it is
least recently used ---> 1 Page fault
0 is already in memory so ---> 0 Page fault.
4 will takes place of 1 ---> 1 Page Fault
Now for the further page reference string ---> 0 Page fault because they are already
available in the memory.

Most Recently Used (MRU)

In this algorithm, a page will be replaced which has been used recently. Belady's anomaly
can occur in this algorithm.
Example 4: Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-
page frames. Find number of page faults using MRU Page Replacement Algorithm.
Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots ---> 4 Page
faults
0 is already their so--> 0 page fault
when 3 comes it will take place of 0 because it is most recently used ---> 1 Page fault
when 0 comes it will take place of 3 ---> 1 Page fault
when 4 comes it will take place of 0 ---> 1 Page fault
2 is already in memory so ---> 0 Page fault
when 3 comes it will take place of 2 ---> 1 Page fault
when 0 comes it will take place of 3 ---> 1 Page fault
when 3 comes it will take place of 0 ---> 1 Page fault
when 2 comes it will take place of 3 ---> 1 Page fault
when 3 comes it will take place of 2 ---> 1 Page fault

Conclusion
In summary, page replacement algorithms are essential for managing a computer's memory
efficiently. They help ensure that the system runs smoothly by reducing the number of times
it needs to fetch data from slower storage. Different algorithms, like FIFO and LRU, have
their own pros and cons, and choosing the right one depends on the specific needs of the
system. Understanding these algorithms can help improve system performance and make
our computers faster and more efficient.

Cache Memory Organization

Cache memory is a small, high-speed memory located close to the CPU. It stores
frequently accessed data from main memory to reduce access time.

Why Organize Cache Memory?

Cache must decide:

Where to place data from main memory

How to find it quickly
What to replace when cache is full

This is determined by the cache organization or mapping technique.

Cache Mapping Techniques: There are three major cache mapping techniques:
Direct Mapping
● Each block of main memory maps to one specific cache line

● Uses:
Cache Line=(Block Address)mod (Number of Lines)

Structure:

● Tag: Identifies the memory block

● Line Number: Index in the cache

● Offset: Byte within the block

Pros:

● Simple and fast

● Easy to implement

Cons:

● High conflict misses (multiple blocks map to same line)

Fully Associative Mapping

● Any memory block can be stored in any cache line

● Cache must search all lines for a match

Pros:

● Very flexible

● Minimizes conflict misses

Cons:

● Complex hardware (needs comparators for all lines)

● Slower lookup

Set-Associative Mapping

● Hybrid of direct and fully associative

 ● Cache is divided into sets, each with N lines (N-way set-associative)

● A block maps to one set, but can go in any line of that set

Example:

● 4-way set-associative → each set has 4 slots

Pros:

● Reduces conflict misses

● Balance between speed and flexibility

Cons:

● More complex than direct mapping

Cache Replacement Policies

When a new block needs to be loaded and all lines in the set are full:

Policy Description

LRU Replace Least Recently Used line

FIFO Replace line loaded first

Random Replace a random line in the set