本实验要求模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断。以此来加深对虚拟存储的理解。
第一题：模拟分页式存储管理中硬件的地址转换和产生缺页中断。
第二题：用先进先出（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;
}
