Scribd
Upload
12 views13 pages

Page Replacement Algorithms Explained

The document discusses frame allocation and page replacement algorithms in virtual memory management, highlighting the need to allocate frames to processes and select which pages to replace during page faults. It describes various algorithms including FIFO, Optimal, LRU, and MRU, along with the phenomenon of thrashing and its causes. The document emphasizes the challenges of implementing optimal algorithms and suggests using local replacement strategies to mitigate thrashing effects.

Uploaded by

Marium naeem
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
12 views13 pages

Page Replacement Algorithms Explained

The document discusses frame allocation and page replacement algorithms in virtual memory management, highlighting the need to allocate frames to processes and select which pages to replace during page faults. It describes various algorithms including FIFO, Optimal, LRU, and MRU, along with the phenomenon of thrashing and its causes. The document emphasizes the challenges of implementing optimal algorithms and suggests using local replacement strategies to mitigate thrashing effects.

Uploaded by

Marium naeem
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Frame Allocation

and page
Replacement
Algorithm
Virtual memory management
Cont...

• if we have multiple processes in memory, we must


decide how many frames to allocate to each process;
and when page replacement is required, we must
select the frames that are to be replaced.

• We evaluate an algorithm by running it on a particular


string of memory references and computing the
number of page faults. The string of memory
references is called a reference string.
Page Replacement Algorithm

FIFO

Optimal Page Replacement

LRU (Least Recently Used )

MRU (Most Recently Used)


• The simplest page-replacement algorithm is a first-in, first-out (FIFO)
algorithm.
• When a page must be replaced, the oldest page is chosen.

FIFO Algorithm.
FIFO

• A bad replacement choice may increase the page-fault rate and slow
process execution.
• Consider the following string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
• Notice that the number of faults for four frames (ten) is greater than the
number of faults for three frames (nine)! This most unexpected result is
known as Belady’s anomaly.
Optimal page Replacement

• Replace the page that will not be used for the


longest period of time.
• the optimal page-replacement algorithm is
difficult to implement, because it requires future
knowledge of the reference string.
Optimal Page
Replacement
LRU Page Replacement
• If we use the recent past as an approximation of the near
future, then we can replace the page that has not been used for
the longest period of time. This approach is the least recently
used (LRU) algorithm.

• we can think of this strategy as the optimal page-replacement


algorithm looking backward in time, rather than forward.
LRU Page
Replacem
ent
Algorith
m
MRU (Most Recently Used)
Thrashing
• High paging activity is called thrashing. A
process is thrashing if it is spending more time
paging than executing.
Cause of Thrashing
• Problem: If CPU utilization is too low, we
increase the degree of multiprogramming by
introducing a new process to the system.
• Solution :
• we can limit the effects of thrashing by using a
local replacement algorithm (or priority
replacement algorithm).
Thank You

You might also like