1. FIFO Page Replacement Algorithm

The First-In-First-Out (FIFO) algorithm replaces the oldest page in memory. By using a circular linked list to represent page frames, we can efficiently track the arrival order.

#include <stdio.h>
#include <stdlib.h>

typedef struct Frame {
   int id;
   struct Frame *next;
} Frame;

int executeFIFO(Frame *buffer, int *stream, int totalPages, int frameCount) {
   int faults = 0;
   Frame *ptr = buffer;
   for (int i = 0; i < totalPages; i++) {
       Frame *check = buffer;
       int found = 0;
       for (int j = 0; j < frameCount; j++) {
           if (check->id == stream[i]) { found = 1; break; }
           check = check->next;
       }
       if (!found) {
           ptr->id = stream[i];
           ptr = ptr->next;
           faults++;
       }
   }
   return faults;
}
   

2. Least Recently Used (LRU) Strategy

LRU discards the item that has not been accessed for the longest period. This is typically implemented using a combination of a Doubly Linked List and a Hash Map for O(1) lookups and updates.

#include <list>
#include <unordered_map>

class PageCache {
   int capacity;
   std::list<int> sequence;
   std::unordered_map<int, std::list<int>::iterator> lookup;

public:
   PageCache(int cap) : capacity(cap) {}

   void accessPage(int page) {
       if (lookup.count(page)) {
           sequence.erase(lookup[page]);
       } else if (sequence.size() == capacity) {
           lookup.erase(sequence.back());
           sequence.pop_back();
       }
       sequence.push_front(page);
       lookup[page] = sequence.begin();
   }
};
   

3. Second-Chance Page Replacement

The Second-Chance algorithm modifies FIFO by checking a reference bit. If the bit is set, the page is given a "second chance" and its reference bits cleared, essentially moving it to the end of the queue.

typedef struct {
   int pageNum;
   int refBit;
} PageEntry;

void handleFault(PageEntry *memory, int *clockHand, int size, int newPage) {
   while (1) {
       if (memory[*clockHand].refBit == 0) {
           memory[*clockHand].pageNum = newPage;
           memory[*clockHand].refBit = 1;
           *clockHand = (*clockHand + 1) % size;
           break;
       } else {
           memory[*clockHand].refBit = 0;
           *clockHand = (*clockHand + 1) % size;
       }
   }
}
   

4. Bit Vector Manipulation

Bit vectors provide a space-efficient way to track binary states, such as free/allocated disk blocks.

#include <stdint.h>

#define ENABLE_BIT(vec, pos)  ((vec) |= (1U << (pos)))
#define DISABLE_BIT(vec, pos) ((vec) &= ~(1U << (pos)))
#define CHECK_BIT(vec, pos)   ((vec) & (1U << (pos)))

void example() {
   uint32_t diskMap = 0;
   ENABLE_BIT(diskMap, 5);
   if (CHECK_BIT(diskMap, 5)) { /* Block 5 is in use */ }
}