Page Replacement Algo

Write a program to simulate Page
replacement algorithm: FIFO, LRU, Optimal.
A computer system has a limited amount of memory. Adding more

memory physically is very costly. Therefore most modern
computers use a combination of both hardware and software to
allow the computer to address more memory than the amount
physically present on the system. This extra memory is actually
called Virtual Memory.
Virtual Memory is a storage allocation scheme used by the Memory

Management Unit(MMU) to compensate for the shortage of
physical memory by transferring data from RAM to disk storage. It
addresses secondary memory as though it is a part of the main
memory. Virtual Memory makes the memory appear larger than
actually present which helps in the execution of programs that are
larger than the physical memory.
Virtual Memory can be implemented using two methods :
 Paging
 Segmentation
Paging
Paging is a process of reading data from, and writing data to, the
secondary storage. It is a memory management scheme that is
used to retrieve processes from the secondary memory in the form
of pages and store them in the primary memory. The main
objective of paging is to divide each process in the form of pages of
fixed size.
Page Replacement Algorithm
Page Replacement Algorithm decides which page to remove, also

called swap out when a new page needs to be loaded into the main
memory. Page Replacement happens when a requested page is not
present in the main memory and the available space is not
sufficient for allocation to the requested page.
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 algorithms. 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 faults the better is the algorithm for that situation.
Some Page Replacement Algorithms :
 First In First Out (FIFO)

 Least Recently Used (LRU)
 Optimal Page Replacement
First In First Out (FIFO)
This is the simplest page replacement algorithm. In this algorithm,

the OS maintains a queue that keeps track of all the pages in
memory, with the oldest page at the front and the most recent page
at the back.
When there is a need for page replacement, the FIFO algorithm,

swaps out the page at the front of the queue, that is the page which
has been in the memory for the longest time.
Advantages
 Simple and easy to implement.

 Low overhead.
Disadvantages
 Poor performance.
 Doesn’t consider the frequency of use or last used time,
simply replaces the oldest page.
 Suffers from Belady’s Anomaly(i.e. more page faults when we
increase the number of page frames).
Least Recently Used (LRU)
Least Recently Used page replacement algorithm keeps track of

page usage over a short period of time. It works on the idea that
the pages that have been most heavily used in the past are most
likely to be used heavily in the future too.
In LRU, whenever page replacement happens, the page which has

not been used for the longest amount of time is replaced.
Advantages
 Efficient.
 Doesn't suffer from Belady’s Anomaly.
Disadvantages
 Complex Implementation.
 Expensive.
 Requires hardware support.
Optimal Page Replacement
Optimal Page Replacement algorithm is the best page replacement

algorithm as it gives the least number of page faults. It is also
known as OPT, clairvoyant replacement algorithm, or Belady’s
optimal page replacement policy.
In this algorithm, pages are replaced which would not be used for
the longest duration of time in the future, i.e., the pages in the
memory which are going to be referred farthest in the future are
replaced.
This algorithm was introduced long back and is difficult to

implement because it requires future knowledge of the program
behaviour. However, it is possible to implement optimal page
replacement on the second run by using the page reference
information collected on the first run.
Advantages
 Easy to Implement.
 Simple data structures are used.
 Highly efficient.
Disadvantages
 Requires future knowledge of the program.

 Time-consuming.

Page Replacement Algo

Uploaded by

Copyright:

Available Formats

Page Replacement Algo

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Page Replacement Algo

Uploaded by

Copyright:

Available Formats

Write a program to simulate Page

replacement algorithm: FIFO, LRU, Optimal.

A computer system has a limited amount of memory. Adding more

Virtual Memory is a storage allocation scheme used by the Memory

Virtual Memory can be implemented using two methods :

Page Replacement Algorithm

Page Replacement Algorithm decides which page to remove, also

A page replacement algorithm tries to select which pages should be

Some Page Replacement Algorithms :

 First In First Out (FIFO)

First In First Out (FIFO)

This is the simplest page replacement algorithm. In this algorithm,

When there is a need for page replacement, the FIFO algorithm,

 Simple and easy to implement.

Least Recently Used (LRU)

Least Recently Used page replacement algorithm keeps track of

In LRU, whenever page replacement happens, the page which has

Optimal Page Replacement

Optimal Page Replacement algorithm is the best page replacement

This algorithm was introduced long back and is difficult to

 Requires future knowledge of the program.

You might also like