Linux实验——页面置换算法模拟

页面置换算法模拟

【实验目的】

（1）理解虚拟内存管理的原理和技术。

（2）掌握请求分页存储管理的思想。

（3）理解常用页面置换算法的思想。

【实验原理/实验基础知识】

存储器是计算机系统的重要资源之一。任何程序、数据以及用于实现控制的数据结构都必须占用一定的存储空间，因此存储管理直接影响系统性能。

• 虚拟内存

在计算机存储体系结构中，内存空间有限，能装入内存并发执行的进程数目受到限制，同时，对于一些较大的进程来说，如果其需求的内存空间容量超过系统实际能够提供的内存容量时，进程将无法执行。

存在该问题的原因是常规存储器管理过程中存在一次性及驻留性这样的特征。常规存储管理在作业执行前，要求一次性全部装入内存，且在作业装入内存后，整个作业一直驻留在内存中，直至作业运行结束。实际上，在一个作业执行过程中，其大部分程序和数据并不经常被访问，这些不经常被访问的程序、数据占据了大量存储空间，需要运行的作业又无法装入内存。

系统借助虚拟存储技术解决了上述问题。虚拟存储技术的基本思想是，作业在运行前无需一次性全部装入内存，仅将当前要运行的页面或段装入，其余部分暂存在外存上。程序运行过程中，如果其要访问的页面或段不在内存，则向系统发出缺页中断请求，将该页面或段调入内存后继续执行。调入时若内存全满，则通过页面置换将内存中暂时不用的页面或段调至外存，然后执行待访问页面的调入操作。

操作系统采用虚拟技术，在不改变物理内存实际大小的情况下提供的逻辑上被扩充了的内存。这种物理上不具备而逻辑上具备的内存就是虚拟内存。

• 请求分页存储管理

分页存储管理通过一个页面分配一个内存块，内存块在物理位置上可连续，也可不连续，这样能够提高存储空间的利用效率。但是，作业需要一次性全部装入内存空间。在分页存储管理的基础上结合虚拟存储技术进行空间分配，可进一步提升存储空间使用效率。

请求分页存储管理的基本思想是，进程开始执行前，只需部分装入即将运行的页面，然后根据需要载入其他页面，分配空间可连续，也可不连续。

• 页面置换算法

1. 置换时机

当要将辅存中的一页面并送入到全满的内存中时，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法，也称为淘汰算法。

1. 常用置换算法
   1. 先进先出算法FIFO：淘汰先调入内存的页。
   2. 最久未使用淘汰算法LRU：淘汰未被访问的页中时间最长的页。
   3. 最近未使用淘汰算法NUR：淘汰第1个最近未被访问的页（淘汰页表中第一个访问位为0的页）。
   4. 最少使用页面淘汰算法LFU：页表中增加一个访问记数器，淘汰那些到当前时间为止访问次数最少的页。
2. 页面淘汰算法优劣的衡量标准

页面淘汰算法通过缺页率衡量置换算法的优劣，缺页率越小，说明算法适合该访问序列，系统效率高。

缺页率f’＝f／a （a是总的页面访问次数，f是缺页次数）

【实验环境】VMware Workstation、RedHat

【实验步骤】

设计一个虚拟存储区和一个内存工作区，并使用下述常用页面置换算法计算缺页率。

先进先出（first in first out，FIFO）算法

要求如下：

1. 由用户输入作业页面个数、总的页面访问次数及待访问页面序列。

1. 由用户输入两个可选驻留集数值，需检查驻留集数值是否小于作业页面个数，不满足要求则重新输入。
2. 提供选择页面置换算法的界面。
3. 计算并输出不同页面置换算法在不同驻留集情况下的缺页率。

• 页面置换算法代码

#include <stdio.h>
#include <stdlib.h>
// FIFO页面置换算法
double FIFO(int jobSize, int accessSize, int *accessSequence, int residentSetSize) {
    int pageFaults = 0;
    int *memoryQueue = (int *)malloc(residentSetSize * sizeof(int));
    int *isInMemory = (int *)calloc(jobSize, sizeof(int));
    for (int i = 0; i < accessSize; i++) {
        int page = accessSequence[i];
        if (!isInMemory[page]) {
            pageFaults++;
            if (i >= residentSetSize) {
                int oldestPage = memoryQueue[0];
                for (int j = 0; j < residentSetSize-1; j++) {
                    memoryQueue[j] = memoryQueue[j+1];
                }
                isInMemory[oldestPage] = 0;
            }
            memoryQueue[i % residentSetSize] = page;
            isInMemory[page] = 1;
        }
    }
    free(memoryQueue);
    free(isInMemory);
    return (double)pageFaults / accessSize * 100;
}
int main() {
    int jobSize, accessSize;
    printf("Enter the number of job pages: ");
    scanf("%d", &jobSize);
    printf("Enter the total number of page accesses: ");
    scanf("%d", &accessSize);
    int *accessSequence = (int *)malloc(accessSize * sizeof(int));
    printf("Enter the page access sequence: ");
    for (int i = 0; i < accessSize; i++) {
        scanf("%d", &accessSequence[i]);
    }
    int residentSetA, residentSetB;
    do {
        printf("Enter resident set A size: ");
        scanf("%d", &residentSetA);
        printf("Enter resident set B size: ");
        scanf("%d", &residentSetB);  
        if (residentSetA >= jobSize || residentSetB >= jobSize) {
            printf("Resident set sizes should be less than the number of job pages.\n");
        }
    } while (residentSetA >= jobSize || residentSetB >= jobSize);
    printf("FIFO page replacement algorithm:\n");
    printf("Resident set A: %.2lf%%\n", FIFO(jobSize, accessSize, accessSequence, residentSetA));
    printf("Resident set B: %.2lf%%\n", FIFO(jobSize, accessSize, accessSequence, residentSetB));
    free(accessSequence);
    return 0;
}

【实验报告】 ?

填写《上机实验报告》。

【思考题】

1. 缺页率和驻留集之间的关系是什么？

答：缺页率与驻留集之间的关系是相互影响的。

驻留集是进程在运行过程中所需的物理页面数目，而缺页率是指进程在执行过程中，发生缺页中断的次数与总页面访问次数的比值。

如果驻留集太小，也就是进程所需物理页面数目过少，可能会导致频繁的缺页中断。这是因为当进程需要访问的页面不在内存中时，就会发生缺页中断，导致系统需要花费额外的时间来处理缺页，从而降低了系统的效率。这种情况下，缺页率会很高。

反之，如果驻留集太大，也就是进程所需物理页面数目过多，可能会导致多道程序并发度下降，资源利用率降低。这是因为当内存中驻留的页面数目过多时，可能会导致内存资源的浪费，同时也会增加系统管理的开销，从而降低了系统的效率。这种情况下，缺页率可能不会明显下降，因为即使增加物理页面数目，也可能会因为其他因素（如页面置换算法）导致缺页中断仍然频繁发生。

1. 为什么驻留集数值需要小于页面个数？

答：驻留集数值要小于页面个数，主要是因为在实际的计算机系统中，内存是有限的。当一个进程在运行时，它需要访问的页面可能很多，如果全部放入内存，可能会占用过多的内存资源，导致其他进程无法获得足够的内存资源，从而影响系统的整体性能。

此外，如果驻留集大小等于页面个数，那么一旦发生缺页中断，就需要从硬盘中读取相应的页面来替换内存中的页面，这样会导致IO操作频繁发生，也会影响系统的性能。

因此，将驻留集大小设置小于页面个数，可以避免过度占用内存资源，同时也可以减少IO操作次数，提高系统的整体性能。