Operating System(OSY-315319)
Unit IV
Memory Management
Mrs. Anjali S. Khandagale
1
2
Paging
Paging is a non-contiguous memory allocation technique.
In a paging scheme, a process is divided into several pages.
The pages are then stored in different frames of the main memory.
The basic idea behind paging is that when a process is swapped in,the
pager only loads into memory those pages that it expects the process
to need.
Paging permits a program memory to be non contiguous,thus allowing
a program to be allocated physical memory wherever it is available.
It is possible that not all pages of the program are brought into
[Link] pages are loaded into memory and some pages are
kept on the disk.
3
Page Fault-
When a page referenced by the CPU is not found in the main
memory, it is called as a page fault.
When a page fault occurs, the required page has to be fetched
from the secondary memory into the main memory.
To distinguish between the pages that are in memory and the
pages that are on the disk,a valid-invalid bit is provided.
Pages that are not loaded into memory are marked as invalid
in the page table using the invalid bit.
The bit is set to valid if the associated page is in memory.
4
Page Replacement Algorithms
• When a page fault occurs,the operating system has to
choose a page to remove from memory to make room for
the page that has to be brought [Link] is known as page
replacement.
• The approach of page replacement is ,if no frame is free,we
find one that is not currently being used and free it.
• Page replacement algorithm works on the string of memory
references called as reference string.
• It also needs the available number of page frames.
• Then the number of page faults determined for a particular
reference string.
5
Page Replacement algorithms are
• FIFO – (First in First Out)
• Optimal Page Replacement (OPU)
• Least Recently Used(LRU)
6
FIFO (First In First Out)
• The simplest page replacement algorithm is FIFO.
• A FIFO associates with each page time when that page
was brought into memory
• It replaces the oldest page that has been present in the
main memory for the longest time.
• It is implemented by keeping track of all the pages in a
queue.
7
• Example-1Consider page reference string 1, 3, 0, 3, 5,
6 with 3 page [Link] number of page faults.
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 by 5.
—>1 Page Fault.
6 comes, it is also not available in memory
so it replaces the oldest page slot i.e 3 by 6
—>1 Page Fault.
Finally when 3 come it is not avilable so it
replaces 0 by 3-----> 1 page fault
So total page faults are 6.
8
Belady’s anomaly – Belady’s anomaly proves that it is
possible to have more page faults when increasing the
number of page frames while using the First in First Out
(FIFO) page replacement algorithm.
For example, if we consider reference string 3, 2, 1, 0,
3, 2, 4, 3, 2, 1, 0, 4 and 3 slots, we get 9 total page
faults, but if we increase slots to 4, we get 10 page
faults.
9
FIFO Page Replacement Algorithm
10
Advantages of FIFO page replacement algorithm
[Link] is simple and easy to understand & implement.
Disadvantages of FIFO page replacement algorithm
[Link] process effectiveness is low.
[Link] we increase the number of frames while using
FIFO, we are giving more memory to processes. So,
page fault should decrease, but here the page faults are
increasing. This problem is called as Belady’s Anomaly.
3. Every frame needs to be taken account off. 11
Thank You
12
Thank You