页面置换算法的实现

页面置换算法

实验说明：

通过页面置换算法模拟设计，理解虚拟存储技术的特点，掌握请求页式存储管理方式。

编程实现先进先出（FIFO）页面置换算法、最近最久未使用（LRU）页面置换算法、Clock(NRU)置换算法。

先进先出(FIFO)页面置换算法

​ 先进先出（FIFO）页面置换算法基于队列的思想，认为最先进入内存的页面在后续被置换出去的可能性最大。该算法维护一个页面队列，新页面进入时添加到队列末尾，当需要置换页面时，选择队列头部的页面进行置换，就如同排队时先到的人先离开队伍一样。

算法流程图：

最近最久未使用(LRU)页面置换算法

​ 最近最久未使用（LRU）页面置换算法基于这样一个原理：如果页面在过去很长一段时间内未被访问，那么在将来它被访问的可能性也比较小，所以当发生缺页中断且内存已满时，置换掉最近最久未使用的页面。

算法流程图

最近未使用(NRU)页面置换算法

​ Clock 置换算法（也称为最近未用算法，NRU）是一种改进型的页面置换算法，它结合了先进先出（FIFO）算法和最近最久未使用（LRU）算法的部分思想。

​ 该算法将内存中的页面构成一个环形链表（逻辑上的环形结构，可以通过数组配合指针来模拟实现），并为每个页面设置一个访问位（通常初始化为 0）。当有页面被访问时，将其访问位设置为 1。

​ 在需要进行页面置换时，从当前指针位置开始扫描环形链表，查找访问位为 0 的页面（即最近未被使用的页面），如果找到这样的页面，就将其置换出去；如果扫描一圈都没有找到访问位为 0 的页面，那就将所有页面的访问位重新置为 0，然后再进行下一轮扫描，直到找到可置换的页面为止。这种方式类似于时钟指针的转动来依次查看各个页面的情况，所以被称为 Clock 置换算法。

算法流程图

实现代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define overflow -2
#define codenum 220 // 指令数
#define pagenum 20  // 页数

int n = pagenum, m = 3; // n为页流数, m为物理块数

typedef struct link {
    int data;
    struct link* next;
} qnode, * qlink;

// 函数声明
void menu(int* str);
int* creatstr();
int** initstring();
void printresult(int** a, int* str);
qlink initlink();
void release_link(qlink l); // 释放链表
void fifo(int* str);
void lru(int* str);
void nru(int* str);

// 随机生成页流
int* creatstr() {
    int* str;
    time_t t;
    int count = 0;
    str = (int*)malloc(sizeof(int) * (pagenum + 1));
    if (!str)
        exit(overflow);
    srand((unsigned)time(&t));
    for (count = 1; count <= pagenum; count++) {
        str[count] = rand() % (codenum / 10);
    }
    return str;
}

// 初始化二维数组
int** initstring() {
    int** a = (int**)malloc(sizeof(int*) * (n + 1));
    if (!a)
        exit(overflow);
    for (int i = 0; i <= n; i++) {
        a[i] = (int*)malloc(sizeof(int) * (m + 1));
        if (!a[i])
            exit(overflow);
        for (int j = 1; j <= m; j++)
            a[i][j] = -1;
    }
    return a;
}

// 打印结果
void printresult(int** a, int* str) {
    printf("**************************** Orders of Pages ************************\n");
    for (int i = 1; i <= n; i++)
        printf("%3d", str[i]);
    putchar('\n');
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[j][i] == -1)
                printf("   ");
            else
                printf("%3d", a[j][i]);
        }
        putchar('\n');
    }
    putchar('\n');
}

// 初始化链表
qlink initlink() {
    return NULL;
}

// 释放链表
void release_link(qlink l) {
    while (l) {
        qlink temp = l;
        l = l->next;
        free(temp);
    }
}

// FIFO算法
void fifo(int* str) {
    int count = 0, j = 0, ** a = initstring();
    for (int i = 1; i <= n; i++) {
        int flag = 0;
        for (int k = 1; k <= m; k++) {
            if (a[i][k] == str[i]) {
                flag = 1;
                break;
            }
        }
        if (!flag) {
            count++;
            a[i][j++ % m + 1] = str[i];
        }
        if (i != n) {
            for (int k = 1; k <= m; k++)
                a[i + 1][k] = a[i][k];
        }
    }
    printresult(a, str);
    printf("Page Faults: %d\n", count);
    for (int i = 0; i <= n; i++) free(a[i]);
    free(a);
}

// LRU算法（基于链表实现）
void lru(int* str) {
    int count = 0, ** a = initstring();
    qlink head = initlink();
    for (int i = 1; i <= n; i++) {
        int found = 0;
        qlink prev = NULL, curr = head;

        // 查找当前页是否在链表中
        while (curr) {
            if (curr->data == str[i]) {
                found = 1;
                if (prev) { // 如果不是链表头，则移动到头部
                    prev->next = curr->next;
                    curr->next = head;
                    head = curr;
                }
                break;
            }
            prev = curr;
            curr = curr->next;
        }

        if (!found) { // 缓存未命中
            count++;
            qlink new_node = (qlink)malloc(sizeof(qnode));
            new_node->data = str[i];
            new_node->next = head;
            head = new_node;

            // 如果超过物理块数量，则删除链表尾部
            int node_count = 0;
            qlink temp = head, tail = NULL;
            while (temp) {
                node_count++;
                if (node_count == m)
                    tail = temp;
                temp = temp->next;
            }
            if (node_count > m && tail) {
                temp = tail->next;
                tail->next = NULL;
                free(temp);
            }
        }

        // 记录链表中的状态
        curr = head;
        for (int j = 1; j <= m; j++) {
            a[i][j] = (curr) ? curr->data : -1;
            if (curr) curr = curr->next;
        }
    }
    printresult(a, str);
    printf("Page Faults: %d\n", count);
    for (int i = 0; i <= n; i++) free(a[i]);
    free(a);
    release_link(head);
}

// NRU算法
void nru(int* str) {
    int count = 0, ** a = initstring();
    int* frame = (int*)malloc(sizeof(int) * m);
    int* referenced = (int*)malloc(sizeof(int) * m);
    for (int i = 0; i < m; i++) {
        frame[i] = -1;
        referenced[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        int found = 0;
        for (int j = 0; j < m; j++) {
            if (frame[j] == str[i]) {
                found = 1;
                referenced[j] = 1; // 设置引用位
                break;
            }
        }

        if (!found) {
            count++;
            for (int j = 0; j < m; j++) {
                if (referenced[j] == 0) {
                    frame[j] = str[i];
                    referenced[j] = 1;
                    break;
                }
                referenced[j] = 0; // 重置引用位
            }
        }

        for (int j = 0; j < m; j++) {
            a[i][j + 1] = frame[j];
        }
    }

    printresult(a, str);
    printf("Page Faults: %d\n", count);

    for (int i = 0; i <= n; i++) free(a[i]);
    free(a);
    free(frame);
    free(referenced);
}

// 主菜单
void menu(int* str) {
    int choice;
    printf("1. FIFO\n");
    printf("2. LRU\n");
    printf("3. NRU\n");
    printf("4. Exit\n");
    printf("Choose (1-4): ");
    scanf("%d", &choice);
    switch (choice) {
    case 1: fifo(str); break;
    case 2: lru(str); break;
    case 3: nru(str); break;
    case 4: exit(0);
    default: printf("Invalid choice!\n");
    }
}

// 主函数
int main() {
    int* str = creatstr();
    while (1) {
        menu(str);
    }
    free(str);
    return 0;
}

运行结果

1. FIFO
2. LRU
3. NRU
4. Exit
Choose (1-4): 1
**************************** Orders of Pages ************************
 14  9 20  3  9  1  9 17  2  5 19 17  1  7 12  4  5  8 11 15
 14 14 14  3  3  3  3 17 17 17 19 19 19  7  7  7  5  5  5 15
     9  9  9  9  1  1  1  2  2  2 17 17 17 12 12 12  8  8  8
       20 20 20 20  9  9  9  5  5  5  1  1  1  4  4  4 11 11

Page Faults: 19
1. FIFO
2. LRU
3. NRU
4. Exit
Choose (1-4): 2
**************************** Orders of Pages ************************
 14  9 20  3  9  1  9 17  2  5 19 17  1  7 12  4  5  8 11 15
 14  9 20  3  9  1  9 17  2  5 19 17  1  7 12  4  5  8 11 15
    14  9 20  3  9  1  9 17  2  5 19 17  1  7 12  4  5  8 11
       14  9 20  3  3  1  9 17  2  5 19 17  1  7 12  4  5  8

Page Faults: 18
1. FIFO
2. LRU
3. NRU
4. Exit
Choose (1-4): 3
**************************** Orders of Pages ************************
 14  9 20  3  9  1  9 17  2  5 19 17  1  7 12  4  5  8 11 15
 14 14 20 20 20  1  1  1  2  2 19 19  1  1 12 12  5  5 11 11
     9  9  9  9  9  9  9  9  5  5  5  5  7  7  7  7  8  8  8
           3  3  3  3  3  3  3  3 17 17 17 17 17 17 17 17 15

Page Faults: 18
1. FIFO
2. LRU
3. NRU
4. Exit
Choose (1-4): 4