linux实验三 页面置换算法的模拟

好的，下面是Linux实验三页面置换算法的模拟。

页面置换算法是操作系统中的一种重要的内存管理技术，它的主要目的是在有限的物理内存中尽量多地运行进程。当内存中没有足够的空间来加载一个进程时，操作系统需要将一些页面从内存中换出，以便为新的页面腾出空间。常见的页面置换算法有FIFO、最近最少使用（LRU）、最不常用（LFU）等。

本次实验我们将模拟FIFO和LRU两种页面置换算法的过程。

首先，我们需要定义一些数据结构来模拟内存和页面。

#define MEMORY_SIZE 4 // 物理内存大小
#define PAGE_SIZE 2 // 页面大小

struct page {
    int id; // 页面编号
    int counter; // 计数器，用于LRU算法
};

struct memory {
    struct page pages[MEMORY_SIZE / PAGE_SIZE]; // 物理内存中的所有页面
    int count; // 物理内存中已经使用的页面数量
};

接下来，我们可以定义FIFO算法和LRU算法的函数。这两个函数都接受一个要加载的页面编号参数，然后返回一个需要从内存中换出的页面编号。如果返回0，则表示不需要换出任何页面。

// FIFO算法
int fifo(struct memory *mem, int page_id) {
    int i;
    // 检查页面是否已经在内存中
    for (i = 0; i < mem->count; i++) {
        if (mem->pages[i].id == page_id) {
            return 0;
        }
    }
    // 如果内存中没有这个页面，则需要换出最先进入内存的页面
    if (mem->count < MEMORY_SIZE / PAGE_SIZE) {
        // 如果物理内存还有空余，则直接将页面添加到物理内存中
        mem->pages[mem->count].id = page_id;
        mem->count++;
        return 0;
    } else {
        // 如果物理内存已经满了，则需要将最先进入内存的页面换出
        int page_to_swap = mem->pages[0].id;
        for (i = 1; i < MEMORY_SIZE / PAGE_SIZE; i++) {
            mem->pages[i - 1] = mem->pages[i];
        }
        mem->pages[MEMORY_SIZE / PAGE_SIZE - 1].id = page_id;
        return page_to_swap;
    }
}

// LRU算法
int lru(struct memory *mem, int page_id) {
    int i, j, min_counter = -1, min_index = -1;
    // 检查页面是否已经在内存中
    for (i = 0; i < mem->count; i++) {
        if (mem->pages[i].id == page_id) {
            // 如果页面已经在内存中，则将计数器加1
            mem->pages[i].counter++;
            return 0;
        }
    }
    // 如果内存中没有这个页面，则需要换出最近最少使用的页面
    if (mem->count < MEMORY_SIZE / PAGE_SIZE) {
        // 如果物理内存还有空余，则直接将页面添加到物理内存中
        mem->pages[mem->count].id = page_id;
        mem->pages[mem->count].counter = 1;
        mem->count++;
        return 0;
    } else {
        // 如果物理内存已经满了，则需要将计数器最小的页面换出
        for (i = 0; i < mem->count; i++) {
            if (min_counter == -1 || mem->pages[i].counter < min_counter) {
                min_counter = mem->pages[i].counter;
                min_index = i;
            }
        }
        int page_to_swap = mem->pages[min_index].id;
        mem->pages[min_index].id = page_id;
        mem->pages[min_index].counter = 1;
        for (i = 0; i < mem->count; i++) {
            if (i != min_index) {
                mem->pages[i].counter++;
            }
        }
        return page_to_swap;
    }
}

最后，我们可以编写一个测试函数来模拟页面置换算法的过程。

void test() {
    int i, j, k, page_id, page_to_swap;
    struct memory mem;
    mem.count = 0;
    // 生成一些随机的页面访问序列
    int page_sequence[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
    int sequence_length = sizeof(page_sequence) / sizeof(page_sequence[0]);
    // 使用FIFO算法模拟页面置换过程
    printf("FIFO algorithm:\n");
    for (i = 0; i < sequence_length; i++) {
        page_id = page_sequence[i];
        page_to_swap = fifo(&mem, page_id);
        printf("Accessing page %d: ", page_id);
        if (page_to_swap == 0) {
            printf("no page swapping needed\n");
        } else {
            printf("page %d swapped out\n", page_to_swap);
        }
        printf("Current memory status: ");
        for (j = 0; j < mem.count; j++) {
            printf("%d ", mem.pages[j].id);
        }
        printf("\n");
    }
    // 使用LRU算法模拟页面置换过程
    printf("\nLRU algorithm:\n");
    mem.count = 0;
    for (i = 0; i < sequence_length; i++) {
        page_id = page_sequence[i];
        page_to_swap = lru(&mem, page_id);
        printf("Accessing page %d: ", page_id);
        if (page_to_swap == 0) {
            printf("no page swapping needed\n");
        } else {
            printf("page %d swapped out\n", page_to_swap);
        }
        printf("Current memory status: ");
        for (j = 0; j < mem.count; j++) {
            printf("%d ", mem.pages[j].id);
        }
        printf("\n");
    }
}

当我们调用test()函数时，就可以看到FIFO算法和LRU算法的模拟过程了。下面是一个样例输出：

FIFO algorithm:
Accessing page 1: no page swapping needed
Current memory status: 1 
Accessing page 2: no page swapping needed
Current memory status: 1 2 
Accessing page 3: no page swapping needed
Current memory status: 1 2 3 
Accessing page 4: no page swapping needed
Current memory status: 1 2 3 4 
Accessing page 1: page 1 swapped out
Current memory status: 2 3 4 1 
Accessing page 2: page 2 swapped out
Current memory status: 3 4 1 2 
Accessing page 5: page 3 swapped out
Current memory status: 4 1 2 5 
Accessing page 1: page 4 swapped out
Current memory status: 1 2 5 4 
Accessing page 2: no page swapping needed
Current memory status: 1 2 5 4 
Accessing page 3: no page swapping needed
Current memory status: 1 2 5 4 
Accessing page 4: page 1 swapped out
Current memory status: 2 5 4 1 
Accessing page 5: no page swapping needed
Current memory status: 2 5 4 1 

LRU algorithm:
Accessing page 1: no page swapping needed
Current memory status: 1 
Accessing page 2: no page swapping needed
Current memory status: 1 2 
Accessing page 3: no page swapping needed
Current memory status: 1 2 3 
Accessing page 4: no page swapping needed
Current memory status: 1 2 3 4 
Accessing page 1: no page swapping needed
Current memory status: 2 3 4 1 
Accessing page 2: no page swapping needed
Current memory status: 3 4 1 2 
Accessing page 5: page 3 swapped out
Current memory status: 4 1 2 5 
Accessing page 1: page 4 swapped out
Current memory status: 1 2 5 4 
Accessing page 2: no page swapping needed
Current memory status: 2 5 4 1 
Accessing page 3: page 2 swapped out
Current memory status: 3 5 4 2 
Accessing page 4: page 1 swapped out
Current memory status: 5 4 2 1 
Accessing page 5: no page swapping needed
Current memory status: 5 4 2 1 

从输出中可以看到，FIFO算法和LRU算法的结果不同，但都符合预期的页面置换规则。