WikiGalaxy
Page Replacement Algorithms
Overview:
Page Replacement Algorithms are used in operating systems to manage the contents of a computer's memory. When a system runs out of RAM, the OS must decide which pages to swap out to make room for new data. The efficiency of these algorithms is crucial for optimizing performance and minimizing latency.
- First-In-First-Out (FIFO)
- Optimal Page Replacement
- Least Recently Used (LRU)
- Least Frequently Used (LFU)
- Clock Page Replacement
First-In-First-Out (FIFO)
Concept:
FIFO is one of the simplest page replacement algorithms. It replaces the oldest page in memory, assuming that the oldest page is the least likely to be needed soon.
public class FIFOPageReplacement {
public static void main(String[] args) {
int[] pages = {1, 3, 0, 3, 5, 6};
int capacity = 3;
Queue memory = new LinkedList<>();
int pageFaults = 0;
for (int page : pages) {
if (!memory.contains(page)) {
if (memory.size() == capacity) {
memory.poll();
}
memory.add(page);
pageFaults++;
}
}
System.out.println("Total Page Faults: " + pageFaults);
}
}
Explanation:
The FIFO algorithm maintains a queue of pages currently in memory. When a page fault occurs, the page at the front of the queue is removed, and the new page is added at the back. This process continues until all pages are processed.
Optimal Page Replacement
Concept:
The Optimal Page Replacement algorithm replaces the page that will not be used for the longest period of time in the future. This algorithm is often used as a benchmark for other algorithms.
public class OptimalPageReplacement {
public static void main(String[] args) {
int[] pages = {7, 0, 1, 2, 0, 3, 0, 4, 2};
int capacity = 3;
List memory = new ArrayList<>();
int pageFaults = 0;
for (int i = 0; i < pages.length; i++) {
if (!memory.contains(pages[i])) {
if (memory.size() == capacity) {
int farthest = i + 1;
int indexToReplace = -1;
for (int j = 0; j < memory.size(); j++) {
int futureIndex = findFutureIndex(pages, memory.get(j), i);
if (futureIndex > farthest) {
farthest = futureIndex;
indexToReplace = j;
}
}
memory.remove(indexToReplace);
}
memory.add(pages[i]);
pageFaults++;
}
}
System.out.println("Total Page Faults: " + pageFaults);
}
private static int findFutureIndex(int[] pages, int page, int currentIndex) {
for (int i = currentIndex; i < pages.length; i++) {
if (pages[i] == page) {
return i;
}
}
return Integer.MAX_VALUE;
}
}
Explanation:
The optimal algorithm requires future knowledge of the reference string, which makes it impractical for real-time use but useful for comparison purposes. It calculates the future index for each page in memory and replaces the one with the farthest future use.
Least Recently Used (LRU)
Concept:
LRU replaces the page that has not been used for the longest period of time. This algorithm uses past knowledge to predict future behavior.
public class LRUPageReplacement {
public static void main(String[] args) {
int[] pages = {4, 3, 4, 2, 3, 1, 4, 3, 2};
int capacity = 3;
LinkedHashMap memory = new LinkedHashMap<>(capacity, 0.75f, true);
int pageFaults = 0;
for (int page : pages) {
if (!memory.containsKey(page)) {
if (memory.size() == capacity) {
Integer firstKey = memory.keySet().iterator().next();
memory.remove(firstKey);
}
memory.put(page, page);
pageFaults++;
} else {
memory.get(page); // Refresh order
}
}
System.out.println("Total Page Faults: " + pageFaults);
}
}
Explanation:
LRU uses a data structure that maintains the order of insertion, allowing the least recently used page to be efficiently identified and removed. This approach provides a good approximation of the optimal algorithm.
Least Frequently Used (LFU)
Concept:
LFU replaces the page that has been used least frequently over a period of time. It keeps track of the frequency of access for each page.
public class LFUPageReplacement {
public static void main(String[] args) {
int[] pages = {2, 3, 2, 1, 5, 2, 4, 5};
int capacity = 3;
Map memory = new HashMap<>();
Map frequency = new HashMap<>();
int pageFaults = 0;
for (int page : pages) {
if (!memory.containsKey(page)) {
if (memory.size() == capacity) {
int lfuPage = Collections.min(frequency.entrySet(), Map.Entry.comparingByValue()).getKey();
memory.remove(lfuPage);
frequency.remove(lfuPage);
}
memory.put(page, page);
pageFaults++;
}
frequency.put(page, frequency.getOrDefault(page, 0) + 1);
}
System.out.println("Total Page Faults: " + pageFaults);
}
}
Explanation:
LFU maintains a frequency count for each page in memory. When a page fault occurs, the page with the lowest frequency count is replaced. This algorithm can lead to poor performance if frequently accessed pages are clustered together.
Clock Page Replacement
Concept:
The Clock Page Replacement algorithm is a more efficient version of the FIFO algorithm. It uses a circular buffer and a "use" bit to track page usage.
public class ClockPageReplacement {
public static void main(String[] args) {
int[] pages = {0, 1, 2, 3, 0, 1, 4, 0};
int capacity = 3;
int[] memory = new int[capacity];
boolean[] useBit = new boolean[capacity];
int pointer = 0;
int pageFaults = 0;
Arrays.fill(memory, -1);
for (int page : pages) {
boolean pageFound = false;
for (int i = 0; i < capacity; i++) {
if (memory[i] == page) {
useBit[i] = true;
pageFound = true;
break;
}
}
if (!pageFound) {
while (useBit[pointer]) {
useBit[pointer] = false;
pointer = (pointer + 1) % capacity;
}
memory[pointer] = page;
useBit[pointer] = true;
pointer = (pointer + 1) % capacity;
pageFaults++;
}
}
System.out.println("Total Page Faults: " + pageFaults);
}
}
Explanation:
The Clock algorithm uses a circular buffer to manage pages. Each page has an associated use bit that is set when the page is accessed. When a page fault occurs, the algorithm cycles through the buffer, replacing the first page with a use bit of 0.
