Second Chance Page Replacement
In our previous look at page replacement, we saw that FIFO is incredibly fast to implement but performs poorly because it ignores whether a page is actually being used. LRU performs excellently but is very expensive to implement because it requires updating data structures on every single memory access.
The Second Chance Algorithm (often called the Clock Algorithm) is a brilliant compromise. It takes the blazing speed of the FIFO queue but adds a simple check to ensure it doesn't accidentally evict heavily used pages.
What is the Second Chance Algorithm?
The algorithm uses a standard FIFO queue, but it looks at the hardware "Reference Bit" of each page. When a page is first loaded or successfully accessed (a hit), the hardware sets its Reference Bit to 1.
When RAM is full and a page must be evicted, the OS looks at the oldest page in the queue:
1. If the Reference Bit is 0, the page hasn't been used recently. It is evicted immediately.
2. If the Reference Bit is 1, the page has been used recently. Instead of evicting it, the OS gives it a "second chance". It flips the bit to 0, moves the page to the back of the queue (treating it as newly arrived), and moves on to check the next page.
Steps of the Algorithm
- A page fault occurs and physical RAM is completely full.
- The pointer (clock hand) examines the oldest page in the circular queue.
- If the Reference Bit is 0: Evict the page. Put the new page in this frame, set its bit to 1, and advance the pointer.
- If the Reference Bit is 1: Give it a second chance. Flip the bit to 0, leave the page in RAM, and advance the pointer to check the next oldest page.
- Repeat this process until a page with a 0 bit is successfully found and evicted.
A Worked Example
Let's trace a simple string: 1, 2, 3, 1, 4 with 3 physical frames. We will represent frames as Page(Bit).
Step 1: Request 1. Fault. Load 1. Pointer points to frame 1.
Frames: [ 1(1), Empty, Empty ]
Step 2: Request 2. Fault. Load 2.
Frames: [ 1(1), 2(1), Empty ]
Step 3: Request 3. Fault. Load 3.
Frames: [ 1(1), 2(1), 3(1) ]
Step 4: Request 1. Hit! Page 1 is already in memory. Its bit is refreshed to 1 (it already was 1, so no change).
Frames: [ 1(1), 2(1), 3(1) ]
Step 5: Request 4. Fault! RAM is full. The pointer is at Page 1.
- Check Page 1: Bit is 1. Second chance! Flip bit to 0. Advance pointer to Page 2.
- Check Page 2: Bit is 1. Second chance! Flip bit to 0. Advance pointer to Page 3.
- Check Page 3: Bit is 1. Second chance! Flip bit to 0. Advance pointer back to Page 1.
- Check Page 1 again: Bit is now 0!
- EVICT Page 1. Load Page 4. Set bit to 1. Advance pointer to Page 2.
Frames: [ 4(1), 2(0), 3(0) ]Implementation in Code
Here is how you might simulate the Second Chance (Clock) algorithm using arrays to track the frames and their reference bits.
Python Implementation
def second_chance(reference_string, capacity):
frames = [-1] * capacity
ref_bits = [0] * capacity
pointer = 0
page_faults = 0
for page in reference_string:
# Check if page is already in memory (Hit)
if page in frames:
index = frames.index(page)
ref_bits[index] = 1 # Refresh the bit
continue
# Page Fault: We need to load the page
page_faults += 1
# Find a victim using the clock hand (pointer)
while True:
# If bit is 0, we found our victim
if ref_bits[pointer] == 0:
frames[pointer] = page
ref_bits[pointer] = 1 # New page gets bit 1
pointer = (pointer + 1) % capacity # Advance pointer
break
# If bit is 1, give second chance
else:
ref_bits[pointer] = 0 # Flip to 0
pointer = (pointer + 1) % capacity # Advance pointer
return page_faults
# Test the example
pages = [1, 2, 3, 1, 4]
print(f"Page Faults: {second_chance(pages, 3)}")C++ Implementation
#include <iostream>
#include <vector>
using namespace std;
int secondChance(vector<int> pages, int capacity) {
vector<int> frames(capacity, -1);
vector<int> refBits(capacity, 0);
int pointer = 0;
int faults = 0;
for (int page : pages) {
bool found = false;
for (int i = 0; i < capacity; i++) {
if (frames[i] == page) {
refBits[i] = 1; // Hit! Refresh bit
found = true;
break;
}
}
if (!found) {
faults++;
while (true) {
if (refBits[pointer] == 0) {
frames[pointer] = page;
refBits[pointer] = 1;
pointer = (pointer + 1) % capacity;
break;
} else {
refBits[pointer] = 0; // Second chance
pointer = (pointer + 1) % capacity;
}
}
}
}
return faults;
}Java Implementation
public class SecondChance {
public static int run(int[] pages, int capacity) {
int[] frames = new int[capacity];
int[] refBits = new int[capacity];
int pointer = 0, faults = 0;
// Initialize frames to -1
for (int i = 0; i < capacity; i++) frames[i] = -1;
for (int page : pages) {
boolean found = false;
for (int i = 0; i < capacity; i++) {
if (frames[i] == page) {
refBits[i] = 1; // Hit
found = true;
break;
}
}
if (!found) {
faults++;
while (true) {
if (refBits[pointer] == 0) {
frames[pointer] = page;
refBits[pointer] = 1;
pointer = (pointer + 1) % capacity;
break;
} else {
refBits[pointer] = 0; // Give second chance
pointer = (pointer + 1) % capacity;
}
}
}
}
return faults;
}
}Summary
The Second Chance algorithm is a highly practical solution to the page replacement problem. By using a simple hardware bit, it avoids the massive software overhead of LRU linked lists while still successfully identifying and protecting frequently used pages from being evicted by a naive FIFO queue.
Understanding the Second Chance Logic
Question 1 of 1Test your understanding of the core rule of the algorithm.