lru页面置换算法把命中的往前移怎么实现c语言

LRU页面置换算法的实现通常使用双向链表和哈希表两种数据结构来完成。其中，哈希表用于快速查找某个页面是否在内存中，而双向链表则用于按照访问时间顺序维护内存中页面的顺序。

下面是一个简单的 C 语言实现示例：

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

#define CACHE_SIZE 3   // 缓存大小
#define PAGE_NUM   10  // 页面数

// 双向链表结点类型
typedef struct Node {
    int page;           // 页面编号
    struct Node *prev;  // 前驱结点指针
    struct Node *next;  // 后继结点指针
} Node;

// 哈希表类型
typedef struct HashTable {
    Node **nodes;       // 链表头数组指针
} HashTable;

// 初始化结点
Node *init_node(int page) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->page = page;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 初始化哈希表
HashTable *init_hash_table() {
    HashTable *table = (HashTable*)malloc(sizeof(HashTable));
    table->nodes = (Node**)calloc(PAGE_NUM, sizeof(Node*));
    return table;
}

// 插入结点到链表头
void insert_node_to_head(Node **head, Node *node) {
    node->next = *head;
    if (*head != NULL) {
        (*head)->prev = node;
    }
    *head = node;
}

// 移动结点到链表头
void move_node_to_head(Node **head, Node *node) {
    if (node == *head) {
        return;
    }
    if (node->prev != NULL) {
        node->prev->next = node->next;
    }
    if (node->next != NULL) {
        node->next->prev = node->prev;
    }
    insert_node_to_head(head, node);
}

// 删除链表尾结点并返回其页面编号
int remove_tail_node(Node **tail) {
    int page = (*tail)->page;
    Node *prev = (*tail)->prev;
    if (prev != NULL) {
        prev->next = NULL;
    }
    free(*tail);
    *tail = prev;
    return page;
}

// 执行 LRU 置换算法并返回缺页次数
int lru(int pages[], int n) {
    int i, miss = 0;
    Node *head = NULL, *tail = NULL;
    HashTable *table = init_hash_table();
    for (i = 0; i < n; i++) {
        int page = pages[i];
        Node *node = table->nodes[page];
        if (node != NULL) {
            move_node_to_head(&head, node);
        } else {
            if (head == NULL) {
                head = tail = init_node(page);
            } else if (i < CACHE_SIZE) {
                insert_node_to_head(&head, init_node(page));
            } else {
                table->nodes[remove_tail_node(&tail)] = NULL;
                insert_node_to_head(&head, init_node(page));
            }
            table->nodes[page] = head;
            miss++;
        }
    }
    return miss;
}

int main() {
    int pages[] = {1, 3, 5, 2, 4, 1, 7, 8, 9, 3};
    int n = sizeof(pages) / sizeof(pages[0]);
    int miss = lru(pages, n);
    printf("缺页次数：%d\n", miss);
    return 0;
}

在上面的代码中，我们使用 `HashTable` 结构体表示哈希表，它包含一个长度为 `PAGE_NUM` 的指针数组 `nodes`，每个指针指向一个双向链表的头结点。在每次访问页面时，我们首先通过哈希表快速查找该页面是否在内存中，如果在，则将其移动到链表头；否则，如果缓存未满，则将该页面插入到链表头，否则删除链表尾结点并将该页面插入链表头，同时更新哈希表。最后返回缺页次数。

需要注意的是，上述代码仅为演示 LRU 页面置换算法的实现方式，实际应用中可能需要考虑更多的细节问题。