Demand paging- Fragmentation &

Compaction
•Demand paging is a memory management technique where pages are loaded into
RAM only when the CPU needs them, not all at once.
•How it works:
• The program starts running with only the necessary pages in memory.
• If the program tries to access a page that is not in memory, a page fault
occurs.
• The operating system then loads that page from disk into memory and
updates the page table.
• The program continues running as if the page was always in memory.
✅ In short: Demand paging loads pages only when needed, saving memory and
making programs run efficiently.
Pure Demand Paging

•Pure demand paging is a type of demand paging where no pages are loaded into
memory at the start—all pages are initially on the disk.
•How it works:
• When a program starts, memory is empty for that process.
• Pages are brought into RAM only when the program actually needs them.
• This happens one page at a time, as the CPU accesses them.
•Advantages:
• Good for very large programs that cannot fit entirely in memory.
• Saves physical memory, which is helpful for computers with limited RAM.
•Disadvantages:
• If a program accesses many pages not in memory, it can cause many page faults,
slowing down performance.
• Operating systems often use caching and smarter page replacement to reduce
this slowdown.
✅ In short: Pure demand paging loads memory only when needed, saving space,
but too many page faults can slow things down.
Working Process of Demand Paging
Let us understand this with the help of an example. Suppose we want to run a process P which have four
pages P0, P1, P2 and P3. Currently, in the page table, we have pages P1 and P3.
Page Replacement Algorithms in Operating Systems

When a computer uses paging, it divides memory into small parts called pages.
Sometimes, when the system needs a new page but no free space is left in
memory, it must remove one of the pages already there.
Here’s what happens step by step:
[Link] system chooses a page to remove (called the victim page) using a page
replacement algorithm.
[Link] marks that page in the page table as “not present”, meaning it’s no longer in
memory.
[Link] that page was changed while in memory (called a dirty page), the system
saves it back to the disk before removing it.
[Link], the new page is loaded into that freed space.
The better the page replacement algorithm, the fewer page faults will occur —
and that means the system runs faster and more smoothly.
 Common Page Replacement Techniques
•First In First Out (FIFO)
•Optimal Page replacement
•Least Recently Used (LRU)
•Most Recently Used (MRU)
1. First In First Out (FIFO)

•The operating system keeps a list (queue) of all the pages

currently in memory.
•The oldest page — the one that entered memory first — is
placed at the front of the queue.
•When a new page needs to be loaded and memory is full, the
system removes the oldest page (the one at the front).
•The new page is then added to the end of the queue.
So, FIFO simply replaces the page that has been in memory
the longest. It’s easy to use but not always the most efficient.
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

came 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 come it is not available, so it

replaces 0 1-page fault.
2. 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 fault 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 came

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 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.
• 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.
3. Least Recently Used
In this algorithm, 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.
4. Most Recently Used (MRU)
In this algorithm, 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 faults0 is already their so--> 0 page fault

•when 3 comes it will take place of 0 because it is most recently

used ---> 1 Page faultwhen 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

Memory allocation algorithms:

• first fit,

• Best fit,

• worst fit.
• Memory management in an operating system is like organizing and
managing space in a cupboard so that everything fits properly and
can be easily found when needed.
• When a program (process) starts running, it needs some space in
the computer’s memory to store its instructions and data.
• The operating system is responsible for giving each process the
memory space it needs and making sure no two processes use the
same space.
• To do this efficiently, the OS uses memory allocation algorithms —
rules that decide where and how much memory to give to each
process.
• This helps the system use memory wisely, avoid wasting space, and
ensure that programs run smoothly without interfering with each
other.
The following are the most used
algorithms:
1. First Fit
2. Best Fit
3. Worst Fit
4. Next Fit
 First-Fit Memory Allocation
• The First Fit method gives a process the first
empty space in memory that is big enough to
hold it.
• When a new program (process) needs
memory, the operating system starts
checking from the beginning of memory.
• As soon as it finds a free block that’s large
enough, it stops searching and puts the
process there.
• It’s called First Fit because it doesn’t look for
the best or smallest space — just the first
one that fits.
• This makes it quick and easy, but over time it
can leave small unused gaps in memory
(called fragmentation).
 2. Best Fit
•The OS searches all available blocks and chooses the smallest block that can hold the
process.
•This helps reduce wasted space inside the block.
✅ Advantage: Minimizes leftover space (internal fragmentation).
❌ Disadvantage: Searching all blocks takes more time and may create many small unusable
gaps.
3. Worst Fit
The OS looks for the largest available block and allocates the process [Link] idea is
to leave behind a large remaining space that can be used later.✅ Advantage: May
reduce very small unusable gaps.❌ Disadvantage: Can waste large memory areas
and isn’t very efficient overall.