先进先出算法(FIFO)和最近最久未使用算法(LRU)c语言设计思路

FIFO算法和LRU算法都是操作系统中常用的页面置换算法。

FIFO算法的设计思路如下：

1. 建立一个队列，用于保存当前已分配的所有页面；
2. 当需要置换页面时，选择队列头部（即最先进入队列的页面）进行置换；
3. 将新分配的页面加入队列尾部。

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

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

#define PAGE_NUM 3 // 总共可分配的页面数
#define PAGE_SIZE 10 // 每个页面的大小

// 页面结构体，用于表示每个页面的信息
typedef struct {
    int id; // 页面编号
    int last_used_time; // 最近一次使用的时间
} Page;

int main() {
    Page pages[PAGE_NUM]; // 存储页面的数组
    int page_fault = 0; // 页面缺页次数
    int time = 0; // 当前时间

    // 初始化页面信息
    for (int i = 0; i < PAGE_NUM; i++) {
        pages[i].id = -1; // 未分配页面的编号为-1
        pages[i].last_used_time = -1; // 最近一次使用时间初始化为-1
    }

    // 模拟访问页面的过程
    int access_sequence[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3};
    int sequence_size = sizeof(access_sequence) / sizeof(access_sequence[0]);
    for (int i = 0; i < sequence_size; i++) {
        int page_id = access_sequence[i];

        // 查找是否已经分配了该页面
        int found = 0;
        for (int j = 0; j < PAGE_NUM; j++) {
            if (pages[j].id == page_id) {
                found = 1;
                pages[j].last_used_time = time;
                break;
            }
        }

        // 如果未分配该页面，则进行页面置换
        if (!found) {
            // 查找最先进入队列的页面
            int oldest_page_index = 0;
            for (int j = 1; j < PAGE_NUM; j++) {
                if (pages[j].last_used_time < pages[oldest_page_index].last_used_time) {
                    oldest_page_index = j;
                }
            }

            // 进行页面置换
            pages[oldest_page_index].id = page_id;
            pages[oldest_page_index].last_used_time = time;
            page_fault++;
        }

        time++;
    }

    printf("FIFO算法的缺页次数为：%d\n", page_fault);

    return 0;
}

LRU算法的设计思路如下：

1. 建立一个队列，用于保存当前已分配的所有页面；
2. 当需要置换页面时，选择队列中最近最久未使用的页面进行置换；
3. 每次访问页面时，将该页面移动到队列尾部。

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

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

#define PAGE_NUM 3 // 总共可分配的页面数
#define PAGE_SIZE 10 // 每个页面的大小

// 页面结构体，用于表示每个页面的信息
typedef struct {
    int id; // 页面编号
    int last_used_time; // 最近一次使用的时间
} Page;

int main() {
    Page pages[PAGE_NUM]; // 存储页面的数组
    int page_fault = 0; // 页面缺页次数
    int time = 0; // 当前时间

    // 初始化页面信息
    for (int i = 0; i < PAGE_NUM; i++) {
        pages[i].id = -1; // 未分配页面的编号为-1
        pages[i].last_used_time = -1; // 最近一次使用时间初始化为-1
    }

    // 模拟访问页面的过程
    int access_sequence[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3};
    int sequence_size = sizeof(access_sequence) / sizeof(access_sequence[0]);
    for (int i = 0; i < sequence_size; i++) {
        int page_id = access_sequence[i];

        // 查找是否已经分配了该页面
        int found = 0;
        for (int j = 0; j < PAGE_NUM; j++) {
            if (pages[j].id == page_id) {
                found = 1;
                pages[j].last_used_time = time;

                // 将该页面移动到队列尾部
                for (int k = j; k < PAGE_NUM - 1; k++) {
                    pages[k] = pages[k + 1];
                }
                pages[PAGE_NUM - 1].id = page_id;
                pages[PAGE_NUM - 1].last_used_time = time;

                break;
            }
        }

        // 如果未分配该页面，则进行页面置换
        if (!found) {
            // 查找最近最久未使用的页面
            int oldest_page_index = 0;
            for (int j = 1; j < PAGE_NUM; j++) {
                if (pages[j].last_used_time < pages[oldest_page_index].last_used_time) {
                    oldest_page_index = j;
                }
            }

            // 进行页面置换
            pages[oldest_page_index].id = page_id;
            pages[oldest_page_index].last_used_time = time;
            page_fault++;
        }

        time++;
    }

    printf("LRU算法的缺页次数为：%d\n", page_fault);

    return 0;
}