Scribd
Upload
4 views2 pages

Page Replacement Algorithms Explained

The document describes three page replacement algorithms: FIFO, LRU, and Optimal. FIFO replaces the oldest page first, LRU replaces the least recently used page, and Optimal replaces the page that will not be used for the longest time in the future. Each algorithm includes pseudocode for implementation and highlights their advantages and potential drawbacks.

Uploaded by

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

Page Replacement Algorithms Explained

The document describes three page replacement algorithms: FIFO, LRU, and Optimal. FIFO replaces the oldest page first, LRU replaces the least recently used page, and Optimal replaces the page that will not be used for the longest time in the future. Each algorithm includes pseudocode for implementation and highlights their advantages and potential drawbacks.

Uploaded by

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

FIFO Page Replacement Algorithm

Main Points:
• The oldest page in memory is replaced first.
• Think of memory as a queue: pages go in at the back and are removed from the front.
• It’s simple to implement and understand.
• But it can sometimes cause more page faults if the oldest page is still frequently used.

Pseudocode:
Initialize queue for pages
page_faults = 0

For each page in reference string:


If page is in queue:
Continue
Else if queue not full:
Add page to queue
page_faults += 1
Else:
Remove page from front of queue
Add new page to queue
page_faults += 1

Return page_faults

2. LRU (Least Recently Used) Page Replacement


Main Points:
• Replaces the page that hasn’t been used for the longest time.
• Assumes recently used pages will be used again soon.
• Requires tracking page usage history.
Pseudocode:

Initialize list for pages and their last used times


page_faults = 0
time = 0

For each page in reference string:


time += 1
If page is in list:
Update last used time of page
Else if list not full:
Add page with last used time = time
page_faults += 1
Else:
Find page with oldest last used time
Replace it with new page, last used time = time
page_faults += 1

Return page_faults

3. Optimal Page Replacement


Main Points:
• Replaces the page that will not be used for the longest time in the future.
• Requires future knowledge, mostly used for benchmarking.
• Minimizes the number of page faults theoretically.

Pseudocode:
page_faults = 0

For each page at index i in reference string:


If page is in frames:
Continue
Else if frames are not full:
Add page to frames
page_faults += 1
Else:
For each page in frames:
Find next index where page is used after i
If not used again, choose this page for replacement
Replace chosen page with new page
page_faults += 1

Return page_faults

You might also like