本实验要求模拟分页式虚拟存储管理中硬件的地址转换和缺页中断,以及选择页面调度算法处理缺页中断。以此来加深对虚拟存储的理解。

第一题:模拟分页式存储管理中硬件的地址转换和产生缺页中断。

第二题:用先进先出(FIFO)页面调度算法处理缺页中断。

第三题:用最近最少用(LRU)页面调度算法处理缺页中断。

注:网上代码很多,但我借鉴的那篇,它的LRU算法的解题思想与主流不一样,我对其做了修正。

编程语言:C/C++

编译环境:Vs Code


运行结果截图: 

FIFO算法:

 LRU算法:


源代码:

#include "stdio.h"
#include "stdlib.h"
#include <string.h>
#include <iostream>
using namespace std;
#define PROCESSLOGICPAGE 7  // 进程的逻辑页数
#define SIZEOFPAGE 128      // 每个页面的大小
#define PROCESSPAGENUMBER 4 // 给予进程的页框数

struct pageinfo //页表
{
    bool flag;                // 标志位, 1 为已经在主存中 0 为不在主存中
    int block;                // 主存块号
    int disk;                 // 在磁盘上的位置
    bool revise;              // 修改标志, 1 为被修改 0 为未被修改
} pagelist[PROCESSLOGICPAGE]; // 页表

int pageQueuePointer = 0;     // 队列指针,指向调出的页面
int queue[PROCESSPAGENUMBER]; // 主存页号队列

void init() // 初始化页表
{
    queue[0] = 0;
    queue[1] = 1;
    queue[2] = 2;
    queue[3] = 3;
    pagelist[0].flag = 1;
    pagelist[0].block = 5;
    pagelist[0].disk = 011;
    pagelist[1].flag = 1;
    pagelist[1].block = 8;
    pagelist[1].disk = 012;
    pagelist[2].flag = 1;
    pagelist[2].block = 9;
    pagelist[2].disk = 013;
    pagelist[3].flag = 1;
    pagelist[3].block = 1;
    pagelist[3].disk = 021;
    pagelist[4].disk = 022;
    pagelist[5].disk = 023;
    pagelist[6].disk = 121;
}

void showPageListCondition()
{
    printf("\n-------------Information of pagelist-------------\n");
    printf("页号\t标志位\t页框号\t在磁盘上的位置\t修改标志\n");
    for (int i = 0; i < PROCESSLOGICPAGE; i++)
        printf("%d\t%d\t %d\t %d\t\t %d\n", i, pagelist[i].flag, pagelist[i].block, pagelist[i].disk, pagelist[i].revise);
    printf("------------------------------------------This is the dividing line.--------------------------------------------------\n");
}

void pageFault() // 缺页中断
{
    int page, unit;
    string select;
    do
    {
        printf("请输入指令的页号和单元号:\n");
        if (scanf("%d %d", &page, &unit) != 2)
        {
            cin >> select;
            if (select == "exit")
                break;
        }
        if (unit >= SIZEOFPAGE || unit < 0 || page < 0 || page >= PROCESSLOGICPAGE)
        {
            printf("页号或单元号超出范围,请重新输入\n");
            continue;
        }
        else
        {
            if (pagelist[page].flag) // 该页在主存中
            {
                int result = pagelist[page].block * SIZEOFPAGE + unit;
                cout << "绝对地址为:" << pagelist[page].block << "*" << SIZEOFPAGE << "+" << unit << "=" << result << 'B' << endl;
            }
            else // 该页不在主存中
                printf("发生缺页中断:* %d\n", page);
        }
    } while (true);
}

void pageFault_FIFO()
{
    int page, unit;
    string select;
    do
    {
        printf("请输入指令的:\n页号 单元号 是否为存指令(y/n) \n");
        if (scanf("%d %d", &page, &unit) != 2) // 输入页号和单元号
        {
            cin >> select;
            if (select == "exit") // 输入exit退出
                break;
        }
        if (unit >= SIZEOFPAGE || unit < 0 || page < 0 || page >= PROCESSLOGICPAGE)
        {
            printf("页号或单元号超出范围,请重新输入\n");
            cin >> select;
            continue;
        }
        else
        {
            cin >> select;           // 读入是否为存指令
            if (pagelist[page].flag) // 该页在主存中
            {
                int result = pagelist[page].block * SIZEOFPAGE + unit;
                cout << "绝对地址为:" << pagelist[page].block << "*" << SIZEOFPAGE << "+" << unit << "=" << result << 'B' << endl;
                if (select[0] == 'Y' || select[0] == 'y') // 是存指令,修改标志为“1”
                    pagelist[page].revise = 1;
            }
            else // 该页不在主存中,产生缺页中断
            {
                pagelist[page].revise = 0; // 将页块修改标志置为“0”
                pagelist[queue[pageQueuePointer]].flag = 0;  // 从主存中调出该页
                printf("Bring up: %d\t\tWrite back to disk: %s\n", queue[pageQueuePointer], pagelist[queue[pageQueuePointer]].revise ? "True" : "False"); //输出调出的页号
                printf("Call in: %d\n", page);  //输出装入的页号
                pagelist[page].block = pagelist[queue[pageQueuePointer]].block; // 将该页的块号更新为被调出的页面的块号
                pagelist[page].flag = 1;   // 将该页标志置为“1”
                queue[pageQueuePointer] = page; // 将该页号放入队列
                pageQueuePointer = (pageQueuePointer + 1) % PROCESSPAGENUMBER;  // 队列指针后移
            }
        }
    } while (true);
    printf("------------------------------------------This is the dividing line.--------------------------------------------------\n");
    printf("主存页号队列为(第一个队首元素为下一个要被调出的页号):\n");
    for (int i = pageQueuePointer; i < PROCESSPAGENUMBER; i++)
        printf("%d\t", queue[i]);
    for (int i = 0; i < pageQueuePointer; i++)
        printf("%d\t", queue[i]);
    printf("\n");
}

int findSubpoint(int page)
{
    for (int i = 0; i < PROCESSPAGENUMBER; i++)
        if (queue[i] == page)
            return i;
    return PROCESSPAGENUMBER - 1;
}

void pageFault_LRU()
{
    int page, unit;
    string select;
    do
    {
        printf("请输入指令的:\n页号 单元号 是否为存指令(y/n) \n");
        if (scanf("%d %d", &page, &unit) != 2)
        {
            cin >> select;
            if (select == "exit")
                break;
        }
        if (unit >= SIZEOFPAGE || unit < 0 || page < 0 || page >= PROCESSLOGICPAGE)
        {
            printf("页号或单元号超出范围,请重新输入\n");
            cin >> select;
            continue;
        }
        else
        {
            cin >> select;           // 读入是否为存指令
            if (pagelist[page].flag) // 该页在主存中
            {
                int result = pagelist[page].block * SIZEOFPAGE + unit;
                cout << "绝对地址为:" << pagelist[page].block << "*" << SIZEOFPAGE << "+" << unit << "=" << result << 'B' << endl;
                if (select[0] == 'Y' || select[0] == 'y') // 是存指令,修改标志为“1”
                    pagelist[page].revise = 1;
                for (int i = findSubpoint(page); i > 0; i--)
                    queue[i] = queue[i - 1];
                queue[0] = page;
            }
            else // 该页不在主存中,产生缺页中断
            {
                pagelist[page].revise = 0;   // 将页块修改标志置为“0”
                pagelist[queue[PROCESSPAGENUMBER - 1]].flag = 0;    // 调出队尾元素
                printf("Bring up: %d\t\tWrite back to disk: %s\n", queue[PROCESSPAGENUMBER - 1], pagelist[queue[PROCESSPAGENUMBER - 1]].revise ? "True" : "False"); //输出调出的页号
                printf("Call in: %d\n", page);  //输出装入的页号
                pagelist[page].block = pagelist[queue[PROCESSPAGENUMBER - 1]].block;
                pagelist[page].flag = 1;
                queue[PROCESSPAGENUMBER - 1] = page;
                for (int i = PROCESSPAGENUMBER - 1; i > 0; i--)
                    queue[i] = queue[i - 1];
                queue[0] = page;
            }
        }
    } while (true);
    printf("------------------------------------------This is the dividing line.--------------------------------------------------\n");
    printf("主存页号队列为(第一个队首页号为最近一次访问,最后一个队尾页号为下一次调出页号):\n");
    for (int i = 0; i < PROCESSPAGENUMBER; i++)
        printf("%d\t", queue[i]);
    printf("\n");
}

int main()
{
    int select;
    string s;
    do
    {
        init();
        printf("\n********Page scheduling algorithm simulation********\n");
        printf("1.第一题  2.第二题  3.第三题  exit.退出\n");
        if (scanf("%d", &select) != 1)
        {
            cin >> s;
            if (s == "exit")
                break;
        }
        else
        {
            system("cls");
            if (select == 1)
            {
                printf("******************Basic simulation******************\n");
                showPageListCondition();
                pageFault();
            }
            if (select == 2)
            {
                printf("********FIFO scheduling algorithm simulation********\n");
                showPageListCondition();
                pageFault_FIFO();
            }
            if (select == 3)
            {
                printf("*********LRU scheduling algorithm simulation*********\n");
                showPageListCondition();
                pageFault_LRU();
            }
        }
        for (int i = 0; i < PROCESSLOGICPAGE; i++)
        {
            pagelist[i].flag = 0;
            pagelist[i].block = 0;
            pagelist[i].revise = 0;
        }
    } while (true);
    return 0;
}