#include <stdio.
h>
// Function to check if a page is already in frames
int isPageInFrames(int frames[], int capacity, int page) {
for (int i = 0; i < capacity; i++) {
if (frames[i] == page) return 1; // Page hit
}
return 0; // Page miss
}
// FIFO Page Replacement Algorithm
int fifoPageReplacement(int pages[], int n, int capacity) {
int frames[capacity]; // Array to store pages in memory
int front = 0; // Points to the oldest page (FIFO queue)
int page_faults = 0;
// Initialize frames with -1 (empty)
for (int i = 0; i < capacity; i++) {
frames[i] = -1;
}
// Simulating page requests
for (int i = 0; i < n; i++) {
if (!isPageInFrames(frames, capacity, pages[i])) { // Page
fault occurs
frames[front] = pages[i]; // Replace oldest page
front = (front + 1) % capacity; // Move pointer in
circular manner
page_faults++;
}
// Printing current frame status
printf("\nStep %d: ", i + 1);
for (int j = 0; j < capacity; j++) {
if (frames[j] != -1)
printf("%d ", frames[j]);
else
printf("- "); // Empty slot
}
}
return page_faults;
}
// Driver Code
int main() {
int pages[] = {1, 3, 0, 3, 5, 6, 3, 5, 1, 3, 6, 3}; // Page
reference string
int n = sizeof(pages) / sizeof(pages[0]);
int capacity = 3; // Number of frames
printf("📌 FIFO Page Replacement Simulation\n");
printf("===================================\
n");
int page_faults = fifoPageReplacement(pages, n, capacity);
printf("\n\nTotal Page Faults: %d\n", page_faults);
return 0;
}
Step 1: 1 - -
Step 2: 1 3 -
Step 3: 1 3 0
Step 4: 1 3 0
Step 5: 5 3 0
Step 6: 5 6 0
Step 7: 5 6 3
Step 8: 5 6 3
Step 9: 1 6 3
Step 10: 1 3 3
Step 11: 1 3 6
Step 12: 1 3 6
Total Page Faults: 8
C Program for LRU Page Replacement
#include <stdio.h>
// Function to check if a page is in the frame
int isPageInFrames(int frames[], int capacity, int page) {
for (int i = 0; i < capacity; i++) {
if (frames[i] == page) return i; // Page found at index i
}
return -1; // Page not found
}
// Function to find the Least Recently Used page
int findLRU(int time[], int capacity) {
int min = time[0], pos = 0;
for (int i = 1; i < capacity; i++) {
if (time[i] < min) {
min = time[i];
pos = i;
}
}
return pos;
}
// LRU Page Replacement Algorithm
int lruPageReplacement(int pages[], int n, int capacity) {
int frames[capacity], time[capacity];
int page_faults = 0, count = 0;
for (int i = 0; i < capacity; i++) {
frames[i] = -1; // Initialize frames as empty
}
for (int i = 0; i < n; i++) {
int pos = isPageInFrames(frames, capacity, pages[i]);
if (pos == -1) { // Page fault occurs
if (count < capacity) {
frames[count] = pages[i]; // Insert page
time[count] = i; // Store time of use
count++;
} else {
int lru_pos = findLRU(time, capacity);
frames[lru_pos] = pages[i]; // Replace LRU page
time[lru_pos] = i;
}
page_faults++;
} else {
time[pos] = i; // Update time for recently used page
}
// Print current frame state
printf("\nStep %d: ", i + 1);
for (int j = 0; j < capacity; j++) {
if (frames[j] != -1)
printf("%d ", frames[j]);
else
printf("- ");
}
}
return page_faults;
}
// Driver Code
int main() {
int pages[] = {1, 3, 0, 3, 5, 6, 3, 5, 1, 3, 6, 3}; // Page
reference string
int n = sizeof(pages) / sizeof(pages[0]);
int capacity = 3; // Number of frames
printf("📌 LRU Page Replacement Simulation\n");
printf("===================================\
n");
int page_faults = lruPageReplacement(pages, n, capacity);
printf("\n\nTotal Page Faults: %d\n", page_faults);
return 0;
}
Step 1: 1 - -
Step 2: 1 3 -
Step 3: 1 3 0
Step 4: 1 3 0
Step 5: 5 3 0
Step 6: 5 6 0
Step 7: 5 6 3
Step 8: 5 6 3
Step 9: 1 6 3
Step 10: 1 3 3
Step 11: 1 3 6
Step 12: 1 3 6
Total Page Faults: 8
C Program for Second-Chance (Clock) Page Replacement
c
CopyEdit
#include <stdio.h>
// Structure to hold page and reference bit
typedef struct {
int page;
int refBit;
} Frame;
// Function to check if a page is in frames
int isPageInFrames(Frame frames[], int capacity, int page) {
for (int i = 0; i < capacity; i++) {
if (frames[i].page == page) {
frames[i].refBit = 1; // Set reference bit if page exists
return 1;
}
}
return 0;
}
// Second-Chance Page Replacement Algorithm
int secondChancePageReplacement(int pages[], int n, int
capacity) {
Frame frames[capacity]; // Array to store pages and
reference bits
int page_faults = 0, pointer = 0; // Pointer for replacement
// Initialize frames
for (int i = 0; i < capacity; i++) {
frames[i].page = -1; // Empty frame
frames[i].refBit = 0; // Reference bit set to 0
}
// Process each page
for (int i = 0; i < n; i++) {
if (!isPageInFrames(frames, capacity, pages[i])) { // Page
fault occurs
while (frames[pointer].refBit == 1) { // Second chance
frames[pointer].refBit = 0; // Reset ref bit
pointer = (pointer + 1) % capacity; // Move pointer
circularly
}
// Replace the selected page
frames[pointer].page = pages[i];
frames[pointer].refBit = 1;
pointer = (pointer + 1) % capacity;
page_faults++;
}
// Print current frame state
printf("\nStep %d: ", i + 1);
for (int j = 0; j < capacity; j++) {
if (frames[j].page != -1)
printf("%d(%d) ", frames[j].page, frames[j].refBit);
else
printf("- ");
}
}
return page_faults;
}
// Driver Code
int main() {
int pages[] = {1, 3, 0, 3, 5, 6, 3, 5, 1, 3, 6, 3}; // Page
reference string
int n = sizeof(pages) / sizeof(pages[0]);
int capacity = 3; // Number of frames
printf("📌 Second-Chance (Clock) Page Replacement
Simulation\n");
printf("=======================================
============\n");
int page_faults = secondChancePageReplacement(pages, n,
capacity);
printf("\n\nTotal Page Faults: %d\n", page_faults);
return 0;
}
📌 Explanation
1. FIFO with a Second Chance:
o Each page has a reference bit (1 if recently used, 0
if not).
o If a page with reference bit 1 is encountered, it
gets a second chance and its bit is reset to 0.
o If a page with reference bit 0 is found, it is
replaced.
2. Page Fault Handling:
o If the page is in memory, set its reference bit to 1.
o If the page is NOT in memory, replace the first
page with refBit = 0.
📌 Sample Output
yaml
CopyEdit
📌 Second-Chance (Clock) Page Replacement Simulation
============================================
=======
Step 1: 1(1) - -
Step 2: 1(1) 3(1) -
Step 3: 1(1) 3(1) 0(1)
Step 4: 1(1) 3(1) 0(1)
Step 5: 5(1) 3(1) 0(0)
Step 6: 5(1) 6(1) 0(0)
Step 7: 5(1) 6(1) 3(1)
Step 8: 5(1) 6(1) 3(1)
Step 9: 1(1) 6(1) 3(0)
Step 10: 1(1) 3(1) 3(0)
Step 11: 1(1) 3(1) 6(1)
Step 12: 1(1) 3(1) 6(1)
Total Page Faults: 8
(Each page is shown with its reference bit in parentheses)
📌 Complexity Analysis
Best case: O(1) (If all pages fit in memory)
Worst case: O(n × capacity) (If every page causes a
fault)
Average case: O(n)
