LRU Page Replacement
C implementation simulating OS-level page replacement using an LRU caching policy.
Let's start off by defining what pages are. Pages are fixed-size blocks of memory. To manage memory efficiently, operating systems use a technique called paging. This is where both virtual and physical memory are divided into equally sized chunks called pages in virtual memory and frames in physical memory.
When a process requests memory, it operates entirely in virtual addresses. In other words, it doesn't know where the data is stored in RAM (physical addresses). Behind the scenes, the Memory Management Unit (MMU) translates virtual addresses to physical ones using a page table (i.e. maps each virtual page to a physical frame).
This is what operating systems do: they act as illusionists. They provide abstractions of the physical memory space as virtual memory so that each process thinks they own the full address space.
Paging avoids external fragmentation, a problem where free memory is split into unusable gaps. Internal fragmentation can still occur if a process doesn't fully use the memory available in a page.
If a page isn't in RAM (physical memory), the OS triggers a page fault which pauses the process, loads the correct page from secondary storage, then resumes the process (demand paging).
The least recently used (LRU) page replacement algorithm simply swaps out the least recently used page for one loaded from secondary storage into readily accessible RAM.
That was a lot of background information so let's now dive straight into the code. We first have to define our LRUCache. We'll be storing our cache as a doubly linked list where each node represents a page with a hashmap lookup table.
#ifndef _LRU_H_
#define _LRU_H_
typedef struct Node {
int page;
struct Node *prev;
struct Node *next;
} Node;
typedef struct {
// LRU --> MRU
Node *head; // LRU
Node *tail; // MRU
int capacity;
int size;
Node **map;
} LRUCache;
void init_cache(LRUCache *cache, int capacity);
int get(LRUCache *cache, int page);
void put(LRUCache *cache, int page);
void print_cache(LRUCache *cache);
void free_lru(LRUCache *cache);
#endif
Let's go through it. We first initialize a data structure Node and store pointers (variables that hold memory addresses of other variables) to the previous and next node. Note the syntax: we define a struct Node so that we can use it within our definition and then wrap it with a typedef as type Node.
We also define a data structure LRUCache where we track the head and tail of the linked list (our cache), the capacity, size, and a hashmap for O(1) lookup. Again a note on the syntax here on Node **map: map is a pointer to a pointer to a Node. In other words, map is a pointer to the start of an array of pointers to nodes.
Finally we define headers for functions: init_cache, get, put, print_cache, free_lru. Save it as file like lru.h. Let's continue:
#include <stdio.h>
#include <stdlib.h>
#include "lru.h"
void init_cache(LRUCache *cache, int capacity) {
Node *head = malloc(sizeof(Node));
Node *tail = malloc(sizeof(Node));
head->page = -1;
tail->page = -1;
head->next = tail;
tail->prev = head;
head->prev = NULL;
tail->next = NULL;
cache->capacity = capacity;
cache->size = 0;
cache->head = head;
cache->tail = tail;
cache->map = calloc(1000, sizeof(Node *)); // TO-DO: replace with a hashmap implementation
}
First we dynamically allocate (malloc; memory is allocated at runtime) the head and tail dummy nodes. We do this so that when the function returns, the linked list cache structure remains in the heap. We also use calloc for our map since we need to initialize unused pointers to 0 (in this case NULL). Finally, the -> is C's syntactic sugar for dereferencing the pointer to access the value stored at that memory address.
We'll now write some basic inserting and removing to our cache to make our lives easier for the other functions.
void insert_mru(LRUCache *cache, Node *node) {
Node *prev = cache->tail->prev;
Node *next = cache->tail;
prev->next = node;
node->prev = prev;
next->prev = node;
node->next = next;
}
void remove_node(Node *node) {
Node *prev = node->prev;
Node *next = node->next;
prev->next = next;
next->prev = prev;
}
The idea is to insert between the second to last element (the actual most recently used (MRU) node) and our last element (the dummy node: tail), making it the new MRU node. Same idea for deletion, except we want to remove the second node (the LRU node) and reassign the pointers between the next element and the dummy head node.
Now we can easily implement the rest of the functions!
int get(LRUCache *cache, int page) {
if (page < 1000 && cache->map[page] != NULL) {
Node *node = cache->map[page];
remove_node(node);
insert_mru(cache, node);
return page;
}
return -1;
}
In our get method, we simply validate whether our page is valid. Then we find our mapped node using our hashmap and remove it from our cache and reinsert it (since it's been recently accessed making it our MRU page). Let's add our adding a page mechanism:
void put(LRUCache *cache, int page) {
if (page >= 1000 || page < 0) {
return;
}
if (cache->map[page] != NULL) {
remove_node(cache->map[page]);
free(cache->map[page]);
cache->size--;
}
Node *node = malloc(sizeof(Node));
node->page = page;
insert_mru(cache, node);
cache->map[page] = node;
cache->size++;
if (cache->size > cache->capacity) {
Node *lru = cache->head->next;
remove_node(lru);
cache->map[lru->page] = NULL;
free(lru);
cache->size--;
}
}
We first check whether our page is in range. If we already have a page in our cache, we want to remove it (then reinsert it later on—potentially updated). We allocate a node and insert it into our cache. We have to be careful though and this is where the magic of our algorithm comes into play!
If our cache size ever exceeds the capacity, we have to evict our LRU page. We retrieve it by finding the next value of our head dummy node. We then want to remove it, set our mapping to NULL, and free the structure to take care of any memory leaks.
Now we just have to do a little cleanup and printing. Our final code should look something like this:
#include <stdio.h>
#include <stdlib.h>
#include "lru.h"
void init_cache(LRUCache* cache, int capacity) {
Node* head = malloc(sizeof(Node));
Node* tail = malloc(sizeof(Node));
head->page = -1;
tail->page = -1;
head->next = tail;
tail->prev = head;
head->prev = NULL;
tail->next = NULL;
cache->capacity = capacity;
cache->size = 0;
cache->head = head;
cache->tail = tail;
cache->map = calloc(1000, sizeof(Node*));
}
void insert_mru(LRUCache* cache, Node* node) {
Node* prev = cache->tail->prev;
Node* next = cache->tail;
prev->next = node;
next->prev = node;
node->next = next;
node->prev = prev;
}
void remove_node(Node* node) {
Node* prev = node->prev;
Node* next = node->next;
prev->next = next;
next->prev = prev;
}
int get(LRUCache* cache, int page) {
if (page < 1000 && cache->map[page] != NULL) {
Node* node = cache->map[page];
remove_node(node);
insert_mru(cache, node);
return page;
}
return -1;
}
void put(LRUCache* cache, int page) {
if (page >= 1000 || page < 0) {
return;
}
if (cache->map[page] != NULL) {
remove_node(cache->map[page]);
free(cache->map[page]);
cache->size--;
}
Node* node = malloc(sizeof(Node));
node->page = page;
insert_mru(cache, node);
cache->map[page] = node;
cache->size++;
if (cache->size > cache->capacity) {
Node* lru = cache->head->next;
remove_node(lru);
cache->map[lru->page] = NULL;
free(lru);
cache->size--;
}
}
void print_cache(LRUCache* cache) {
Node* curr = cache->head->next;
while (curr != cache->tail) {
printf("Page #%d\n", curr->page);
curr = curr->next;
}
}
void free_lru(LRUCache* cache) {
Node* curr = cache->head;
while (curr != NULL) {
Node* next = curr->next;
free(curr);
curr = next;
}
free(cache->map);
}
int main() {
LRUCache cache;
init_cache(&cache, 3);
printf("LRU --> MRU:\n");
printf("============\n");
put(&cache, 1);
put(&cache, 2);
put(&cache, 3);
print_cache(&cache);
printf("============\n");
get(&cache, 1);
print_cache(&cache);
printf("============\n");
put(&cache, 4);
print_cache(&cache);
printf("============\n");
get(&cache, 3);
print_cache(&cache);
printf("============\n");
put(&cache, 5);
print_cache(&cache);
printf("============\n");
free_lru(&cache);
return 0;
}
Save it as a file like lru.c.
Hope you enjoyed implementing a straightforward system simulation of a LRU page replacement algorithm.
Thanks for reading! Found this useful? Share it or reach out with thoughts.