Micro Project Report On

“Page ReplaceMent Algorithm”

Submitted By:

Aditi Dattatray Yadav

Sanika Anil Jagtap
Snehal Ashok Pilane
Trupti Dipak Yadav

Under the Guidance of

PROF.Khutwad S.S

In the Partial Fulfilment of Fifth Semester of

Diploma in Computer Engineering

Department of Computer Engineering Rajgad Dnyanpeeth

Technical Campus Polytechnic Dhangawadi Tal. Bhor, Dist .Pune
Affiliated to
Maharashtra State Board of Technical Education-41220(MS)
India
Academic Year 2022-2023
 Maharashtra State Board of Technical Education

CERTIFICATE

This is to certify That Ms.Aditi Dattatray Yadav Roll No-03, Ms.Sanika Anil Jagtap Roll no
06,Ms.Snehal Ashok Pilane Roll No-08,Ms. Trupti Dipak Yadav with Roll no-10 , has
successfully completed Microproject in course "Computer Engineering" for the academic
year 2023-2024 as prescribed in the 'Assessment Manual' during his tenure of
completing Fifth Semester of Diploma Program in Computer Engineering from Institute,
Rajgad Dnyanpeeth Technical Campus Polytechnic with Institute code 1532.

Place: Date:

Course Teacher Head of the Department Head of the

Institute
 ACKNOWLEDGMENT

The satisfaction that accompanies that the successful completion of any task would be
incomplete without the mention of people whose ceaseless cooperation made it possible,
whose constant guidance and encouragement crown all efforts with success. We grateful
to our project guide Prof.Khutwad.S.Sfor the guidance inspiration and constructive
suggestions that helpful us in the preparation of this project. We also thank our colleagues
who have helped in successful completion of the Project.

Student name Enrollment No

Aditi Dattatray Yadav 2115320016

Sanika Anil Jagtap 2115320019

Snehal Ashok Pilane 2115320021

Trupti Dipak yadav 2115320024

Abstract
 Page replacement-find some page in memory, but not really in use, swap
it out
 In this case, same page may be brought into memory several times
 The main goal of page replacement algorithms is to provide lowest
page fault rate.
 Deals with which pages need to be swapped out and which are the ones
that need to be swapped in
 The efficiency lies in the least time that is wasted for a
page to be paged in
Introduction:-
In a computer operating system that uses paging for virtual memory management, page
replacement algorithms decide which memory pages to page out, sometimes called swap
out, or write to disk, when a page of memory needs to be allocated. Page
replacement happens when a requested page is not in memory (page fault) and a free page
cannot be used to satisfy the allocation, either because there are none, or because the
number of free pages is lower than some threshold.
When the page that was selected for replacement and paged out is referenced again it has to
be paged in (read in from disk), and this involves waiting for I/O completion. This determines
the quality of the page replacement algorithm: the less time waiting for page-ins, the better
the algorithm. A page replacement algorithm looks at the limited information about accesses
to the pages provided by hardware, and tries to guess which pages should be replaced to
minimize the total number of page misses, while balancing this with the costs (primary
storage and processor time) of the algorithm itself.
The page replacing problem is a typical online problem from the competitive analysis
perspective in the sense that the optimal deterministic algorithm is known.
Aims Of The Microproject:-

Rationale:

Page replacement algorithm are an important part of virtual

memory management and it helps the operating system to decide which memory

page can be moved out, making space for the currently needed page. However, the ultimate
objective of all page replacement algorithm is to reduce the number of page fault. Page
replacement is done when the requested page is not found in the main memory There are
two main aspects of virtual memory, Frame allocation and Page replacement. It is very
important to have optimal frame

allocation and page replacement algorithm.

Aim of the Micro-Project:

Learn different types of page replacement algorithm and how to use

page replacement algorithm in operating system. 3.0 Course Outcomes Achieved:

Know different types of page replacement algorithm.

Know how to use page replacement algorithm in operating system.

Literature Review:

The page replacement algorithm decides which memory page is to be replaced. The process
of replacement is sometimes called swap out or write to disk Page replacement is done when
the requested page is not found in the main memory,

A page replacement algorithm tries to select which pages should be replaced so as to

minimize the total number of page misses. There are many different page replacement. These
algorithms are evaluated by running them on a particular string of memory reference and
computing the number of page faults: The fewer is the page fault the better is the algorithm
for that situation.
Actual Methodology Followed
1. Study the what is paging.

1. Study what is page replacement

2. Study what are different types of page replacement.

3. Study how to use page replacement algorithm.

4. Learn why we use page replacement algorithm 6. Prepare the final report

What is paging?:

 The OS divides virtual memory and the main memory

 into units, called pages.
 Each used page can be either in secondary memory or
 in a page frame in main memory.
 A frame does not have to comprise a single physically contiguous region in secondary
storage.

What is page replacement?:

 When memory located in secondary memory is
 needed, it can be retrieved back to main memory.
 Process of storing data from main memory
 secondary memory->swapping out
 Retrieving data back to main memory->swapping in
What are Page Replacement Algorithms?

 Deals with which page needs to be swapped out and which are the ones that need to
be swapped in
 The efficiency lies in the least time that is wasted for page to be paged in

Types
 Local Page Replacement Strategy
 Global Page Replacement Strategy

Need of Page Replacement Algorithm.

 The main goal of page replacement algorithms is to provide lowest page fault Seol
Page

Algorithms:
1. First In First Out
2. Optimal Page Replacement
3. Least Recently Used
 1. 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 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.

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-2: 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.

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-3: 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.

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 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.

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:

The evolution of replacement algorithms shows the analyses and proof of better performance
has moved from mathematical analysis to testing against real world program traces. This
trend show how difficult it is to mathematically model the memory behavior of programs. An
important is also large amount of easy availability of important programs. The other clear
trend is the realization of the need for workload adaption.