C语言实现fifo和lru

实现 FIFO 和 LRU 算法的关键在于如何维护队列或链表以及如何在缓存空间满时选择哪个页面进行替换。

FIFO（First In First Out）算法，即先进先出算法，是一种简单的页面置换算法。它的实现方式一般使用队列，将最早进入缓存的页面排在队首，最后进入缓存的页面排在队尾。当缓存空间满时，弹出队首页面，将新页面加入队尾即可。

以下是 C 语言实现 FIFO 算法的示例代码：

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

#define CACHE_SIZE 5

int cache[CACHE_SIZE];
int head = 0;
int tail = 0;

void push(int page) {
    if ((tail + 1) % CACHE_SIZE == head) {
        printf("Cache is full, page %d is replaced by page %d.\n", cache[head], page);
        head = (head + 1) % CACHE_SIZE;
    }
    cache[tail] = page;
    tail = (tail + 1) % CACHE_SIZE;
}

int main() {
    push(1);
    push(2);
    push(3);
    push(4);
    push(5);
    push(6);
    push(7);
    push(8);
    return 0;
}

LRU（Least Recently Used）算法，即最近最少使用算法，是一种比 FIFO 更高效的页面置换算法。它的实现方式一般使用双向链表，将最近访问的页面排在链表尾部，最早访问的页面排在链表头部。当缓存空间满时，弹出链表头部页面，将新页面加入链表尾部即可。

以下是 C 语言实现 LRU 算法的示例代码：

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

#define CACHE_SIZE 5

typedef struct node {
    int page;
    struct node *prev;
    struct node *next;
} Node;

Node *head = NULL;
Node *tail = NULL;

void push(int page) {
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->page = page;
    new_node->prev = NULL;
    new_node->next = NULL;
    if (head == NULL) {
        head = new_node;
        tail = new_node;
    } else {
        tail->next = new_node;
        new_node->prev = tail;
        tail = new_node;
    }
    Node *node = head;
    while (node != NULL && node != tail) {
        if (node->page == page) {
            if (node->prev != NULL) {
                node->prev->next = node->next;
            } else {
                head = node->next;
            }
            node->next->prev = node->prev;
            free(node);
            break;
        }
        node = node->next;
    }
    if (tail->next != NULL) {
        Node *old_head = head;
        head = old_head->next;
        head->prev = NULL;
        free(old_head);
    }
}

int main() {
    push(1);
    push(2);
    push(3);
    push(4);
    push(5);
    push(6);
    push(7);
    push(8);
    return 0;
}