Page replacement algorithms

In systems that use virtual memory, processes often require more memory than is available in physical RAM. To manage this, the operating system swaps pages between RAM and disk storage (such as a hard drive or SSD). When the system runs out of RAM and needs to load a new page, it has to decide which of the currently loaded pages to swap out to disk. This decision is made by the page replacement algorithm.

1. FIFO (First-In, First-Out): The oldest page in RAM (the first one loaded) is the first one to be replaced. Example:

  • Page Slots in RAM: 3 slots
  • Page Sequence: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

  • Load page 1 → [1, -, -]
  • Load page 2 → [1, 2, -]
  • Load page 3 → [1, 2, 3]
  • Load page 4 (remove 1) → [4, 2, 3]
  • Load page 1 (remove 2) → [4, 1, 3]
  • Load page 2 (remove 3) → [4, 1, 2]
  • Load page 5 (remove 4) → [5, 1, 2]
  • Load page 1 (already in RAM) → [5, 1, 2]
  • Load page 2 (already in RAM) → [5, 1, 2]
  • Load page 3 (remove 1) → [5, 3, 2]
  • Load page 4 (remove 2) → [5, 3, 4]
  • Load page 5 (already in RAM) → [5, 3, 4]

Result: High page fault rate because old pages are removed without considering if they are still in use.

Belady's Anomaly: In general, you would expect that giving more memory (more page frames) to a process would reduce the number of page faults because there would be more space to keep the necessary pages in memory. However, Belady's Anomaly shows that this is not always the case. Belady's Anomaly typically occurs with certain page replacement algorithms, particularly the FIFO (First-In, First-Out) algorithm. In FIFO, the oldest page in memory is replaced, regardless of how frequently or recently it has been accessed. Let's say you have a process with a sequence of page accesses and you’re using the FIFO page replacement algorithm. You might observe that:

  • With 3 frames, you get 9 page faults.
  • When you increase the number of frames to 4, you suddenly get 10 page faults instead of fewer.

This counterintuitive result is Belady's Anomaly. It happens because of the way FIFO works—it can end up replacing pages that will be needed soon, and the extra frame does not necessarily hold the most useful pages.

2. The Optimal Page Replacement Algorithm: It is a theoretical page replacement strategy that aims to minimize the number of page faults. It works by replacing the page that will not be used for the longest period in the future. Since it requires knowledge of future page references, it is mainly used as a benchmark for comparing other page replacement algorithms. Example

  • Let's consider a memory with 3 frames and a reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.
  • Load page 7 → [7, -, -] (Page 7 is loaded into the first frame)
  • Load page 0 → [7, 0, -] (Page 0 is loaded into the second frame)
  • Load page 1 → [7, 0, 1] (Page 1 is loaded into the third frame)
  • Load page 2 (replace 7) → [2, 0, 1] (Page 2 is loaded; Page 7 is replaced as it will not be used for the longest period)
  • Load page 0 → [2, 0, 1] (Page 0 is already in memory, no change)
  • Load page 3 (replace 1) → [2, 0, 3] (Page 3 is loaded; Page 1 is replaced because it is not needed soon)
  • Load page 0 → [2, 0, 3] (Page 0 is already in memory, no change)
  • Load page 4 (replace 2) → [4, 0, 3] (Page 4 is loaded; Page 2 is replaced because it will not be used soon)
  • Load page 2 (replace 3) → [4, 0, 2] (Page 2 is loaded; Page 3 is replaced)
  • Load page 3 (replace 4) → [3, 0, 2] (Page 3 is loaded; Page 4 is replaced)
  • Load page 0 → [3, 0, 2] (Page 0 is already in memory, no change)
  • Load page 3 → [3, 0, 2] (Page 3 is already in memory, no change)
  • Load page 2 → [3, 0, 2] (Page 2 is already in memory, no change)
Drawbacks of the Optimal Page Replacement Algorithm: The optimal algorithm requires knowledge of future page references, which is usually not possible in real-world scenarios. This makes it impractical for actual implementation and is used only as a theoretical benchmark.

3. Least Recently Used (LRU): is a page replacement algorithm that keeps track of page usage over time and replaces the page that has not been used for the longest period of time.


Implementation of LRU (for further details click on this link - 14:13 to 14:21)

Comments

Post a Comment

Popular posts from this blog

Indexed allocation

Image
  Indexed allocation is a file allocation method used by operating systems to manage how files are stored on disk. The core idea is simple but powerful: instead of storing a file in contiguous blocks or linking blocks one-by-one, the system uses a special index block that contains a list of all the disk block addresses where the file’s data is stored. This removes many limitations of earlier methods like contiguous and linked allocation. In indexed allocation, each file has its own index block . This index block acts like a table of contents. Every entry inside it points to a data block that belongs to that file. When a file is created, the OS allocates an index block and then fills it with pointers to the actual data blocks as the file grows. These data blocks can be located anywhere on the disk , so the file does not need contiguous space. This makes storage much more flexible and avoids external fragmentation. When the system needs to access a particular part of a file, it fir...
Read more

Thrashing

Image
Thrashing occurs in a computer system when the operating system spends a significant amount of time swapping pages in and out of memory, rather than executing actual processes. This typically happens when the system's memory is overcommitted, meaning there are too many processes competing for too little physical memory, leading to frequent page faults. How Memory is Used 1. Initial State: App1 is running, and its two pages are loaded into memory: Frame 1: App1, Page 1 Frame 2: App1, Page 2 Frame 3 and 4 are free. App3's pages are present in swap memory. 2. Switch to App2: Now, you switch to App2, which also requires 2 pages: Frame 3: App2, Page 1 Frame 4: App2, Page 2 Memory is now full with both App1 and App2’s pages. App3's pages are present in swap memory. 3. Switch to App3: You decide to switch to App3, which needs 2 pages as well. Since the memory is full, the system needs to make room: App1’s pages are moved to swap memory: Swap Memory: [App1, Page 1] [App1, Page 2] F...
Read more

Basics of paging

Image
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory and thus helps in handling fragmentation. It involves breaking down memory into fixed-size blocks called pages and frames. The OS typically decides the page size when the system is configured or during the OS design phase. This page size is constant for the entire system and is determined based on considerations such as hardware architecture, efficiency, and the type of applications running. Common page sizes are 4 KB, 8 KB, or 16 KB. Here's a simple explanation with an example: Basic Concepts Page: A fixed-size block of logical memory (virtual memory) used by a process. Frame: A fixed-size block of physical memory (RAM) where a page is mapped. Page Table: A data structure used by the operating system to keep track of the mapping between pages and frames. The Page Table Base Register (PTBR) is a special register in the CPU that holds the starting address of the page table for ...
Read more