Recents in Beach

Page Replacement Algorithms in Operating Systems




⏪Previous                                                           Next⏩



 · Each process is allocated frames (memory) which hold the process’s pages (data)
· Frames are filled with pages as needed – this is called demand paging
·  Over-allocation of memory is prevented by modifying the page-fault service routine to replace pages
· The job of the page replacement algorithm is to decide which page gets victimized to make room for a new page
· Page replacement completes separation of logical and physical memory

In an operating system that uses paging for memory management, a page replacement algorithm is needed to decide which page needs to be replaced when new page comes in.


Page Fault – A page fault happens when a running program accesses a memory page that is mapped into the virtual address space, but not loaded in physical memory.
Since actual physical memory is much smaller than virtual memory, page faults happen. In case of page fault, Operating System might have to replace one of the existing pages with the newly needed page. Different page replacement algorithms suggest different ways to decide which page to replace. The target for all algorithms is to reduce the number of page faults.

Page Replacement Algorithms in Operating Systems

  1. FIFO Page Replacement Algorithm
  2. LRU Page Replacement Algorithm
  3. Optimal Page Replacement Algorithm
  4. Random Page Replacement Algorithm



FIFO Page Replacement Algorithm-


  • As the name suggests, this algorithm works on the principle of “First in First out“.
  • It replaces the oldest page that has been present in the main memory for the longest time.
  • It is implemented by keeping track of all the pages in a queue.
·  Example using 4 frames:


Reference #
1
2
3
4
5
6
7
8
9
10
11
12
Page referenced
1
2
3
4
1
2
5
1
2
3
4
5
Frames
_ = faulting page
1
1
1
1
1
1
5
5
5
5
4
4

2
2
2
2
2
2
1
1
1
1
5


3
3
3
3
3
3
2
2
2
2



4
4
4
4
4
4
3
3
3

·   Analysis: 12 page references, 10 page faults, 6 page replacements. Page faults per number of frames = 10/4 = 2.5

Belady’s anomaly – Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm.  For example, if we consider reference string 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4 and 3 slots, we get 9 total page faults, but if we increase slots to 4, we get 10 page faults.

LRU Page Replacement Algorithm-


  • As the name suggests, this algorithm works on the principle of “Least Recently Used“.
  • It replaces the page that has not been referred by the CPU for the longest time.
  • Example using 4 frames:
  

Page referenced
1
2
3
4
1
2
5
1
2
3
4
5
Frames
_ = faulting page
1
1
1
1
1
1
1
1
1
1
1
5

2
2
2
2
2
2
2
2
2
2
2


3
3
3
3
5
5
5
5
4
4



4
4
4
4
4
4
3
3
3
  



·  Analysis: 12 page references, 8 page faults, 4 page replacements. Page faults per number of frames = 8/4 = 2

Optimal Page Replacement Algorithm-


  • This algorithm replaces the page that will not be referred by the CPU in future for the longest time.
  • It is practically impossible to implement this algorithm.
  • This is because the pages that will not be used in future for the longest time can not be predicted.
  • However, it is the best known algorithm and gives the least number of page faults.
  • Hence, it is used as a performance measure criterion for other algorithms.
·  Example using 4 frames:

Reference #
1
2
3
4
5
6
7
8
9
10
11
12
Page referenced
1
2
3
4
1
2
5
1
2
3
4
5
Frames
_  = faulting page
1
1
1
1
1
1
1
1
1
1
4
4

2
2
2
2
2
2
2
2
2
2
2


3
3
3
3
3
3
3
3
3
3



4
4
4
5
5
5
5
5
5
·   Analysis: 12 page references, 6 page faults, 2 page replacements. Page faults per number of frames = 6/4 = 1.5


Random Page Replacement Algorithm-


  • As the name suggests, this algorithm randomly replaces any page.
  • So, this algorithm may behave like any other algorithm like FIFO, LIFO, LRU, Optimal etc.


⏪Previous                                                           Next⏩

  1. What is an Operating System ?
  2. Discuss the structure off OS ?
  3. Explain type of OS?
  4. Explain Function of OS?
  5. Explain OS Services ?
  6. What do mean by system call ?List different type ofsystem call available ?

  1. what is process ? and Characteristics ?
  2. What is different process state? explain the same in details?
  3. write short note on user level and kernal level threads?
  4. explain what is thread and its type ?
  5. explain scheduler ? (short term,medium term,and long term)
  6. state and explain scheduling criteria ?
  7. Explain scheduling algorithm ? [ FCFS,SJF,PRIORITY,ROUND ROBINE.]    

  1. What is process synchronization ? explain critical section problem and race condition ?
  2. what is Race Condition ?
  3. what is critical section problem?
  4. explain classical problem of synchronization?
  5. explain bounded - buffer problem?
  6. explain reader - writer problem ?
  7. explain Dining Philosophers Problem ?
  8. explain semaphores ? its type ?

  1.  What is deadlock ?
  2. What are the 4 condition to produce deadlock ?
  3. explain methods of handling deadlock ?
  4. explain in detail deadlock prevention ?
  5. write short note on deadlock avoidance ?
  6. explain deadlock detection ? 
  7. explain Banker algorithm with example ? 

Post a Comment

0 Comments