Description:
Page Replacement Algorithms
In an operating system, page replacement algorithms help manage how pages are
loaded into memory when there are limited frames available. When a page fault
occurs (i.e., a required page is not in memory), the system must decide which page
to remove to make space for the new one. This project implements four major
page replacement algorithms: FIFO, LRU, Optimal, and Clock, each with its own
method of handling page replacement.
1. First-In-First-Out (FIFO) Algorithm
The FIFO algorithm follows a simple rule: the page that was added to memory
first is the one that gets removed first when a new page needs space. It works like
a queue where the oldest page is evicted first.
Example:
• Given 3 memory frames and the reference string [1, 2, 3, 4, 2, 1, 5, 6, 2, 4, 3]
• The system fills up the memory with [1, 2, 3] first.
• When 4 arrives, 1 (the first inserted) is removed.
• This process continues, always removing the oldest page.
Limitation:
• FIFO does not consider how frequently or recently a page is used, which may
lead to unnecessary page faults.
2. Least Recently Used (LRU) Algorithm
The LRU algorithm replaces the page that has been least recently used. Instead
of following a fixed order like FIFO, it keeps track of the usage history and
removes the page that has not been used for the longest time.
Example:
• Given 3 memory frames and the reference string [1, 2, 3, 1, 4, 5, 2, 1, 6]
• The system first loads [1, 2, 3].
• When 4 arrives, 3 is removed because it was least recently used.
• When 5 comes, 2 is removed (since 1 and 4 were used more recently).
Advantage:
• LRU provides better performance than FIFO because it takes usage history
into account.
Limitation:
• It requires extra memory to track usage timestamps, making it slightly
complex.
3. Optimal Page Replacement Algorithm
The Optimal algorithm replaces the page that will not be needed for the longest
time in the future. This requires knowing the future reference pattern, which
makes it ideal but impractical in real systems.
Example:
• Given 3 memory frames and the reference string [1, 2, 3, 1, 4, 5, 2, 1, 6]
• Initially, [1, 2, 3] are loaded.
• When 4 arrives, 3 is removed since it is used later than 1 and 2.
• When 5 comes, the page that is used farthest in the future is removed.
Advantage:
• It provides the least number of page faults compared to other algorithms.
Limitation:
• It is impossible to implement in real-time because the system cannot predict
future requests.
4. Clock (Second Chance) Algorithm
The Clock algorithm is an improved version of FIFO that gives each page a
second chance before replacing it. It maintains a circular queue of pages and
uses a reference bit to determine if a page should be replaced.
Example:
• Given 3 memory frames and the reference string [1, 2, 3, 4, 2, 1, 5, 6, 2, 4, 3]
• If a page is referenced again, its reference bit is set to 1 (giving it a second
chance).
• If a page is not used for a while, its reference bit becomes 0, and it gets
replaced.
• This avoids immediately replacing frequently used pages.
Advantage:
• Performs better than FIFO because it avoids unnecessary page replacements.
Limitation:
• It still does not guarantee the best performance like LRU or Optimal.
