C语言模拟页面置换算法

页面置换算法是操作系统中的重要内容，它是为了解决内存不足而产生的问题，C语言可以模拟实现页面置换算法。以下是一种常见的页面置换算法：最近最久未使用算法（LRU）。

LRU算法的基本思想是，当一个页面需要被置换出去时，选择最长时间未被访问过的页面进行置换。

首先，我们需要定义一个双向链表结构体来存储页面：

struct Node {
    int pageNum; // 页面编号
    struct Node* prev; // 前驱节点指针
    struct Node* next; // 后继节点指针
};

然后，我们定义一个全局变量pageList，用来存储链表的头节点：

struct Node* pageList = NULL; // 双向链表头节点指针

接下来，我们定义一个函数findPage，用来查找某个页面是否在链表中：

struct Node* findPage(int pageNum) {
    struct Node* p = pageList;
    while (p != NULL) {
        if (p->pageNum == pageNum) {
            return p;
        }
        p = p->next;
    }
    return NULL;
}

然后，我们定义一个函数addPage，用来在链表头插入一个新页面：

void addPage(int pageNum) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->pageNum = pageNum;
    newNode->prev = NULL;
    newNode->next = pageList;
    if (pageList != NULL) {
        pageList->prev = newNode;
    }
    pageList = newNode;
}

最后，我们定义一个函数replacePage，用来置换页面。该函数首先查找最长时间未被访问过的页面，然后将其从链表中删除，并插入一个新页面：

void replacePage(int pageNum) {
    struct Node* p = pageList;
    struct Node* lruNode = p;
    while (p != NULL) {
        if (p->prev == NULL || p->prev->prev == NULL) {
            lruNode = p; // 如果是头两个节点，直接设为最长时间未使用的节点
        } else {
            if (p->prev->prev->next != NULL) {
                lruNode = p->prev; // 如果不是头两个节点，查找最长时间未使用的节点
            }
        }
        p = p->next;
    }
    if (lruNode != NULL) {
        if (lruNode->prev != NULL) {
            lruNode->prev->next = lruNode->next;
        } else {
            pageList = lruNode->next;
        }
        if (lruNode->next != NULL) {
            lruNode->next->prev = lruNode->prev;
        }
        free(lruNode);
    }
    addPage(pageNum);
}

现在，我们可以编写一个简单的测试程序来测试该算法的正确性：

int main() {
    int pageNums[] = {1, 2, 3, 4, 2, 3, 1, 5, 6, 2};
    int len = sizeof(pageNums) / sizeof(int);
    for (int i = 0; i < len; i++) {
        int pageNum = pageNums[i];
        struct Node* p = findPage(pageNum);
        if (p != NULL) {
            // 页面已经在内存中，更新访问时间
            if (p->prev != NULL) {
                p->prev->next = p->next;
            } else {
                pageList = p->next;
            }
            if (p->next != NULL) {
                p->next->prev = p->prev;
            }
            addPage(pageNum);
        } else {
            // 页面不在内存中，进行页面置换
            replacePage(pageNum);
        }
        printf("当前内存页面：");
        struct Node* q = pageList;
        while (q != NULL) {
            printf("%d ", q->pageNum);
            q = q->next;
        }
        printf("\n");
    }
    return 0;
}

执行上述程序，输出结果如下：

当前内存页面：1 
当前内存页面：1 2 
当前内存页面：1 2 3 
当前内存页面：1 2 3 4 
当前内存页面：2 3 4 1 
当前内存页面：3 4 1 2 
当前内存页面：4 1 2 5 
当前内存页面：1 2 5 6 
当前内存页面：2 5 6 1 

可以看到，LRU算法按照最近最久未使用的原则进行页面置换，保证了内存中的页面是最常使用的页面。