操作系统实验四 请求分页式存储管理

题目描述：
一、实验目的
通过编写分页式存储管理的模拟程序，加深对页式存储管理方式的理解，熟悉逻辑地址到物理地址的转换过程，掌握虚拟存储管理中的页面调度算法，认识分页式虚拟存储系统中缺页中断的处理过程。
二、实验内容
1、设计一个分页式虚拟存储系统，用程序模拟实现，假设页面大小为1K，每个进程分配三个块。
2、页面调度分别采用FIFO调度算法和LRU算法(堆栈法)。（选中页面直接交换。）
3、假设当前作业的页表如下：

4、假设逻辑指令格式为：
操作符 页号1 页内地址1 页号2 页内地址2
例如 表示将页面1内地址为011单元的内容和页面2中地址为051的单元的内容相加，
如：（1011H）＋（1200H）。
现有指令序列如下：

5、编写模拟程序，执行上述指令，若当前页面不在内存，则使用页面调度算法，交换相应页。
6、要求每执行上述指令流中的一条逻辑指令，输出相应的物理指令，若页表有修改，则显示修改后的页表。
FIFO结果
队列内容

LRU结果
栈内部内容：第三个为栈顶第一个为栈低

三、实验思路
（1）初始化：
①初始化页表：自定义页表项数据结构，所有页表项构成一个数组。页表项数据结构中包含所提供的页表信息。从文件中读取页表信息并写入该数组。
②初始化指令表：自定义指令数据结构，所有指令构成一个数组，该数组表示指令表。
指令数据结构中包含所提供的单条指令信息。从文件中读取指令表信息并写入该数组。
（2）FIFO算法：
该算法总是换出最先进入内存的页面，就是要选择当前在内存中驻留时间最久的页面换出。因此可以设置一个队列来保存当前进入内存的页面页号，表示当前内存分配情况。并给它们设置驻留时间。
根据题目给的页表信息，可以看出该进程所分配到的内存块已经存满了，存的是0，1，2号页。可以初始化当前内存分配情况队列，我这里按照这些页在页表中的逻辑地址将它们保存到队列中，即初始化队列为：0，1，2。并将它们的驻留时间设置为0。又因为每个进程分配到的内存块为3，所以用一个三行二列的二维数组来表示该队列，每一行的第一个元素保存页号，第二个元素保存对应的驻留时间。
我这里设置的FIFO函数只有一个参数，传入的是待查找的页码。因此该算法要完成以下功能：
①判断该页是否在内存中，由serach_page()实现
②找出在内存中驻留时间最长的页面，由search_max()实现
③如果该页没有在内存中，在页表中查找该页的逻辑地址，在页表中找出驻留时间最长页面的逻辑地址交换两个页面的标志，磁盘地址，内存块号。并在队列中换出的页面位置上写入换入页面的信息，驻留时间设为0，其他的驻留时间+1。输出更新后的页表信息。
④将此时的队列信息写入队列信息总表以便程序运行完之后查看。
（这个总表队对应于上述示例图片的FIFO队列，表总共8行，对应4条指令的8个操作页面。所以说是每找一个页面就要写入一条队列信息。）
代码：

void FIFO(int pnum)
{
	if (!serach_page(pnum))
	{
		int a, b, c;
		int max = serach_max();
		for (int i = 0;i < 3;i++)
		{
			if (in_s[i][1] == max)
			{
				c = in_s[i][0];
				break;
			}
		}
		for (int i = 0;i < 6;i++)
		{
			if (p[i].pnum == c)
			{
				a = i;break;
			}
		}
		for (int i = 0;i < 6;i++)
		{
			if (p[i].pnum == pnum)
			{
				b = i;break;
			}
		}
		p[a].flag = 0;
		p[b].flag = 1;
		p[a].add = p[b].add;
		p[b].add = -1;
		p[b].cnum = p[a].cnum;
		p[a].cnum = -1;
		int e;
		for (int i = 0;i < 3;i++)
		{
			if (in_s[i][0] == c)
			{
				e = i;
				break;
			}
		}
		in_s[e][0] = pnum;
		in_s[e][1] = 0;
		cout << "发生第" << ++cnumber << "次缺页，更新后的页表为：" << endl;
		display_p();
	}
	int p = 0;
	for (int i = 0;i < 3;i++)
		in_FIFO[f][p++] = in_s[i][0];
	f++;
}

（3）LRU算法：
用一个特殊的栈来保存当前内存分配情况。当需要某一页且该页在内存中，就将该页从栈中取出，并压入栈顶。如果此时栈满，且需要的页面不在内存中，应该移出栈底页，将要换入的页面压入栈顶。因为这里涉及到不同于栈的操作，且调用的页要成为栈顶，所以可以用双向链表实现该栈，以便经常行的存取。
初始化栈，根据题意应该是0，1，2，其中0为栈底，2为栈顶。
同样，我这里设置的LRU函数也是只有一个参数，用来传入待查找的页码。因此该算法要完成以下功能：
①判断该页是否在内存中，由serach_page2实现。（与FIFO中不同的是这里从栈中查找）
②如果当前栈满，且发生缺页，将栈底元素移出栈，该元素即为换出页面的页码，并在页表中找到该换出和换入页面的逻辑位置，交换两页面的部分信息。输出更新后的页表信息。
③如果没有发生缺页，将该页从栈中移出，并压入栈顶。
④将此时的栈信息写入总栈内容表。
代码：

void LRU(int pnum)
{
	if (search_page2(pnum))//页面在主存中
	{
		LRU_stack* q = p_stack->next;
		while (q)//找到该页所对应的链栈的位置
		{
			if (q->pnum == pnum)
				break;
			q = q->next;
		}
		if (q->next == NULL)
		{
			q = p_stack->next;
			int k = 0;
			while (q)
			{
				in_LRU[f][k++] = q->pnum;
				q = q->next;
			}
			f++;
		}
		else
		{
			LRU_stack* d = p_stack->next;
			while (d->next)//找到栈顶指针
				d = d->next;
			//在链栈中交换两个页面的位置，并不改变页表。
			q->prew->next = q->next;
			q->next->prew = q->prew;
			q->prew = d;
			d->next = q;
			q->next = NULL;
			//将当前链栈信息写入LRU
			q = p_stack->next;
			int k = 0;
			while (q)
			{
				in_LRU[f][k++] = q->pnum;
				q = q->next;
			}
			f++;
		}
	}
	else//页面不在主存中
	{
		int onum;
		int a, b;//分别保存 换出的页 和 换入的页 在页表中的相对位置
		for (int i = 0;i < 6;i++)//找出换入页相对位置
		{
			if (p[i].pnum == pnum)
			{
				b = i;
				break;
			}
		}
		onum = p_stack->next->pnum;
		for (int i = 0;i < 6;i++)//找出换出页相对位置
		{
			if (p[i].pnum == onum)
			{
				a = i;
				break;
			}
		}
		//修改页表
		p[a].flag = 0;
		p[b].flag = 1;
		p[a].add = p[b].add;
		p[b].add = -1;
		p[b].cnum = p[a].cnum;
		p[a].cnum = -1;
		cout << "发生第" << ++cnumber << "次缺页，更新后的页表为：" << endl;
		display_p();
		LRU_stack* q = p_stack->next;
		LRU_stack* d = p_stack->next;
		while (d->next)//找到栈顶指针
			d = d->next;
		q->prew->next = q->next;
		q->next->prew = q->prew;
		q->prew = d;
		d->next = q;
		q->next = NULL;
		q->pnum = pnum;
		q = p_stack->next;
		int k = 0;
		while (q)
		{
			in_LRU[f][k++] = q->pnum;
			q = q->next;
		}
		f++;
	}
}

实验结果：

1. 实验要求

• 内存总容量4MB，页面大小4KB。
• 用户自定义创建进程（进程名和所需存储空间），随机生成该进程的页面访问序列。
• 实现页面序列的访问过程，记录页面状态、访问次数和加载入内存的时间。
• 内存空间满时，可通过LRU、FIFO和OPT中的任意调度算法实现页面的置换，要求只能置换当前页面所在进程的的其他页面。
• 页面序列加载完毕后，输出当前进程的页面内容
• 实现查看内存分配状况的功能

2. 语言技巧总结（待完善）

①vector容器

②iterator迭代器

③结构体变量的初始化

④rand和srand生成随机数

⑤休眠函数Sleep()

⑥计时函数clock()

⑦取整函数floor()和ceil()

3. 源代码

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <ctime>
#include <cmath>
#include <iterator>
#include <cstdlib>
#include <windows.h>
using namespace std;

//页表项
typedef struct Page_item
{
    bool status;            //页面所在位置，true为内存，false为外存
    int block_num;          //内存块号
    int visit_num;          //访问次数
    bool change;            //内容是否更改
    double into_time;       //首次访问时间
    double last_visit_time; //最后访问时间
} Page_item;

//页表
typedef vector<Page_item> Page;

//进程控制块
typedef struct P
{
    string name; //进程名
    int size;    //页数
    Page page;   //页表
} P;

vector<P> all;               //所有进程信息表
bool M[1000];                //总内存4M，内存块大小4k
int occupy;                  //当前内存块占用状态
int list[100];               //访问序列
clock_t startTime, tempTime; //时间记录
int note[1000];//用OPT置换时记录页面的预访问次数

//LRU页面置换
void LRU(Page &page, Page_item &page_item)
{
    vector<Page_item>::iterator it = page.begin();  //遍历迭代器
    vector<Page_item>::iterator earliest_it = page.begin(); //上次最早访问迭代器
    for (; it != page.end(); it++)
        if (it->status && it->last_visit_time < earliest_it->last_visit_time)
            earliest_it = it;
    //新页面换入
    page_item.status = true;
    page_item.block_num = earliest_it->block_num;
    tempTime = clock();
    page_item.into_time = page_item.last_visit_time = (double)tempTime / CLOCKS_PER_SEC;
    page_item.visit_num = 1;
    //旧页面换出
    earliest_it->status = false;
}

//FIFO置换策略，与LRU相似，找出最早加载到内存的页面来置换
void FIFO(Page &page, Page_item &page_item)
{
    vector<Page_item>::iterator it = page.begin();
    vector<Page_item>::iterator earliest_it = page.begin();
    for (; it != page.end(); it++)
        if (it->status && it->into_time < earliest_it->last_visit_time)
            earliest_it = it;
    page_item.status = true;
    page_item.block_num = earliest_it->block_num;
    tempTime = clock();
    page_item.into_time = page_item.last_visit_time = (double)tempTime / CLOCKS_PER_SEC;
    page_item.visit_num = 1;
    earliest_it->status = false;
}

//OPT置换策略
void OPT(Page &page, Page_item &page_item, int temp_pos, int list_length, int p_size)
{
    //记录数组初始化
    for (int i = 0; i < p_size; i++)
        note[i] = -1;
    //当前已处于内存中的进程页面记录初始化
    vector<Page_item>::iterator it = page.begin();
    for (int i = 0; it != page.end(); it++, i++)
        if (it->status)
            note[i] = 0;
    //遍历待访问序列，记录到note中
    for (int i = temp_pos; i < list_length; i++)
        if (note[i] != -1)
            note[list[i]]++;
    //置换出将来最少用到的页面
    int will_least;
    int minVal = 99999;
    for (int i = 0; i < p_size; i++)
        if (note[i] != -1 && note[i] < minVal)
        {
            minVal = note[i];
            will_least = i;
        }
    //新页面换入
    page_item.status = true;
    page_item.block_num = page[will_least].block_num;
    tempTime = clock();
    page_item.into_time = page_item.last_visit_time = (double)tempTime / CLOCKS_PER_SEC;
    page_item.visit_num = 1;
    //旧页面换出
    page[will_least].status = false;
}

//创建并加载进程到内存
void createProcess()
{
    //创建进程
    string temp_name;
    int temp_size, count;
    cout << "请依次输入进程的名称和大小(k)：" << endl;
    cin >> temp_name >> temp_size;
    P process = {
        .name = temp_name,
        .size = ceil(temp_size / 4.0)};
    cout << "进程" + process.name + "已经创建成功，共" << process.size << "页" << endl;

    //生成访问序列
    srand((unsigned)time(NULL)); //每次生成随机数前，更换随机数种子为当前时间
    count = rand() % 20 + 5;    //访问序列长度为5——25，可根据需要更改
    for (int i = 0; i < count; i++)
        list[i] = rand() % process.size;
    cout << "随机产生的页面访问序列为：";
    for (int i = 0; i < count; i++)
        cout << list[i] << ' ';
    cout << endl;

    //初始化页表
    Page page;
    for (int i = 0; i < process.size; i++)
    {
        Page_item temp = {
            .status = false};
        page.push_back(temp);
    }
    process.page = page;

    //遍历访问序列
    for (int i = 0; i < count; i++)
    {
        tempTime = clock();
        if (!process.page[list[i]].status) //页面未加载
        {
            if (occupy == 1000) //内存已满
            {
                cout << "内存已满!" << endl;
                if (i == 0)
                {
                    cout << "当前进程无可调出页面，只能调出其他进程的页面，本程序暂不支持此操作！" << endl;
                    break;
                }
                cout << "请选择页面置换的调度方式：" << endl
                     << "1.LRU（优先调出最久未使用的页面）" << endl
                     << "2.FIFO（优先调出最早进入内存的页面）" << endl
                     << "3.OPT（优先调出以后最不经常使用的页面）" << endl;
                char choice;
                cin >> choice;
                switch (choice)
                {
                case '1':
                    LRU(process.page, process.page[list[i]]);
                    cout << "置换成功！" << endl;
                    break;
                case '2':
                    FIFO(process.page, process.page[list[i]]);
                    cout << "置换成功！" << endl;
                    break;
                case '3':
                    OPT(process.page, process.page[list[i]], i, count, process.size);
                    cout << "置换成功！" << endl;
                    break;
                default:
                    cout << "输入有误，本页面调入失败" << endl;
                    break;
                }
            }
            else
            {
                int pos = rand() % 1000;
                int next_pos;
                for (int j = 0; j < 1000; j++)
                {
                    next_pos = (pos + j) % 1000;
                    if (M[next_pos])
                    {
                        M[next_pos] = false;
                        occupy++;
                        process.page[list[i]].status = true;
                        process.page[list[i]].visit_num = 1;
                        process.page[list[i]].block_num = next_pos;
                        process.page[list[i]].into_time = process.page[list[i]].last_visit_time = (double)tempTime / CLOCKS_PER_SEC;
                        break;
                    }
                }
            }
        }
        else    //页面已加载
        {
            process.page[list[i]].visit_num++;
            process.page[list[i]].last_visit_time = (double)tempTime / CLOCKS_PER_SEC;
        }
        Sleep(100); //每次加载页面休眠100ms
    }

    //输出当前进程的页表
    vector<Page_item>::iterator it = process.page.begin();
    cout << endl;
    cout << "进程" << process.name << "的页表如下" << endl;
    for (int i = 0; it != process.page.end(); it++, i++)
    {
        cout << "页号：" << i << "  ";
        if (it->status)
            cout << "主存块号：" << it->block_num << "  "
                 << "访问次数：" << it->visit_num << "  "
                 << "首次访问时间：" << it->into_time << "ms"
                 << "  "
                 << "最后访问时间：" << it->last_visit_time << "ms"
                 << "  "
                 << endl;
        else
            cout << "未调入主存" << endl;
    }
    cout << endl;
    all.push_back(process);
}

//打印当前内存使用情况
void showStorage()
{
    vector<P>::iterator it = all.begin();
    cout << "内存占用情况如下：" << endl;
    cout << "进程名"
         << "  "
         << "占据内存块数" << endl;
    for (; it != all.end(); it++)
        cout << it->name << "      " << it->size << endl;
}

int main()
{
    memset(M, 1, sizeof(M));
    occupy = 0;
    char choice;
    bool flag = true;
    startTime = clock();
    while (flag)
    {
        cout << "请输入要进行的操作：" << endl
             << "1.查看当前内存中进程占用情况" << endl
             << "2.创建新进程" << endl
             << "3.退出" << endl;
        cin >> choice;
        switch (choice)
        {
        case '1':
            showStorage();
            break;
        case '2':
            createProcess();
            break;
        case '3':
            flag = false;
            break;
        default:
            cout << "输入有误" << endl;
            break;
        }
    }
    return 0;
}

操作系统 请求分页式存储管理

实验要求
通过编写分页式存储管理的模拟程序，加深对页式存储管理方式的理解，熟悉逻辑地址到物理地址的转换过程，掌握虚拟存储管理中的页面调度算法，认识分页式虚拟存储系统中缺页中断的处理过程。

实验内容

1. 设计一个分页式虚拟存储系统，用程序模拟实现，假设页面大小为1K，每个进程分配三个块。
2. 页面调度分别采用FIFO调度算法和LRU算法(堆栈法)。（选中页面直接交换。）
3. 假设当前作业的页表如下：
   
4. 假设逻辑指令格式为：
   操作符 页号1 页内地址1 页号2 页内地址2
   例如： 表示将页面1内地址为011单元的内容和页面2中地址为051的单元的内容相加，
   如：（1011H）＋（1200H）。
   现有指令序列如下：
   
5. 编写模拟程序，执行上述指令，若当前页面不在内存，则使用页面调度算法，交换相应页。
6. 要求每执行上述指令流中的一条逻辑指令，输出相应的物理指令，若页表有修改，则显示修改后的页表。

FIFO
内存块按照分配顺序依次放入队列中，每次需要置换时，都将队列第一个内存块取出，分配给一个页表项，原本的数据写入磁盘，然后将该内存块放回队列末尾。

LRU
为每个内存块设置一个上次使用时间，初始为1，每次访问一个内存块时，被访问的内存块的上次使用时间重置为1，其他内存块加1，当需要置换时，选择上次使用时间最大的内存块分配给新的数据，原来的数据写入磁盘，然后该内存块的上次使用时间重置，其他内存块的上次使用时间加1。

//LogicInstruction.h
#pragma once
#include <iostream>

using namespace std;

class LogicInstruction
{
	char op;//运算符
	int pageNo1;//左操作数页号
	string addr1;//左操作数逻辑地址
	int pageNo2;//右操作数页号
	string addr2;//右操作数逻辑地址
public:
	LogicInstruction(char op, int pageNo1, string addr1, int pageNo2, string addr2);
	char getOp()const;
	int getPageNo1()const;
	string getAddr1()const;
	int getPageNo2()const;
	string getAddr2()const;
};

//LogicInstruction.cpp
#include "LogicInstruction.h"

LogicInstruction::LogicInstruction(char op, int pageNo1, string addr1, int pageNo2, string addr2)
{
	this->op = op;
	this->pageNo1 = pageNo1;
	this->addr1 = addr1;
	this->pageNo2 = pageNo2;
	this->addr2 = addr2;
}

char LogicInstruction::getOp()const
{
	return this->op;
}

int LogicInstruction::getPageNo1()const
{
	return this->pageNo1;
}

string LogicInstruction::getAddr1()const
{
	return this->addr1;
}

int LogicInstruction::getPageNo2()const
{
	return this->pageNo2;
}

string LogicInstruction::getAddr2()const
{
	return this->addr2;
}

//MemoryBlock.h
#pragma once
#include <iostream>

using namespace std;

class MemoryBlock
{
	int blockNo;//内存块号
	int lastUsed;//上次使用时间
public:
	MemoryBlock(int blockNo, int lastUsed = 1);
	void increase();
	void init();
	int getBlockNo()const;
	int getLastUsed()const;
};

//MemoryBlock.cpp
#include "MemoryBlock.h"

/// <summary>
/// 构造函数
/// </summary>
/// <param name="blockNo">内存块号</param>
/// <param name="lastUsed">上次使用时间，默认为1</param>
MemoryBlock::MemoryBlock(int blockNo, int lastUsed)
{
	this->blockNo = blockNo;
	this->lastUsed = lastUsed;
}

/// <summary>
/// 上次使用时间+1
/// </summary>
void MemoryBlock::increase()
{
	this->lastUsed++;
}

/// <summary>
/// 上次使用时间重置
/// </summary>
void MemoryBlock::init()
{
	this->lastUsed = 1;
}

int MemoryBlock::getBlockNo()const
{
	return this->blockNo;
}

int MemoryBlock::getLastUsed()const
{
	return this->lastUsed;
}

//PageTableEntry.h
#pragma once
#include <iostream>

using namespace std;

class PageTableEntry
{
	int access;//标志位，标志是否在内存中
	int bolckNo;//分配到的内存块号
	int modify;//修改位
	string diskPos;//在磁盘中的地址
public:
	PageTableEntry(int access, int blockNo, int modify, string diskPos);
	int getAccess()const;
	int getBlockNo()const;
	int getModify()const;
	string getDiskPos()const;
	void setAccess(int access);
	void setBlockNo(int blockNo);
	void setModify(int modify);
	void setDiskPos(string diskPos);
};

//PageTableEntry.cpp
#include "PageTableEntry.h"

PageTableEntry::PageTableEntry(int access, int blockNo, int modify, string diskPos)
{
	this->access = access;
	this->bolckNo = blockNo;
	this->modify = modify;
	this->diskPos = diskPos;
}

int PageTableEntry::getAccess()const
{
	return this->access;
}

int PageTableEntry::getBlockNo()const
{
	return this->bolckNo;
}

string PageTableEntry::getDiskPos()const
{
	return this->diskPos;
}

int PageTableEntry::getModify()const
{
	return this->modify;
}

void PageTableEntry::setAccess(int access)
{
	this->access = access;
}

void PageTableEntry::setBlockNo(int blockNo)

{
	this->bolckNo = blockNo;
}

void PageTableEntry::setDiskPos(string diskPos)
{
	this->diskPos = diskPos;
}

void PageTableEntry::setModify(int modify)
{
	this->modify = modify;
}

//RequestPagingStorageManagement.h
#pragma once
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include "PageTableEntry.h"
#include "MemoryBlock.h"
#include "LogicInstruction.h"

using namespace std;

enum class PageReplacementAlgorithm
{
	FIFO, LRU
};

class RequestPagingStorageManagement
{
	static void FIFO(vector<PageTableEntry>& pageTable, queue<MemoryBlock>& blocks, int pageNo);
	static void LRU(vector<PageTableEntry>& pageTable, queue<MemoryBlock>& blocks, int pageNo);
	static MemoryBlock* findBlock(int blockNo, queue<MemoryBlock>& blocks);
	static void increase(queue<MemoryBlock>& blocks);
	static int findPageTableEntryByBlockNo(int blockNo, vector<PageTableEntry>& pageTable);
	static MemoryBlock* findLeastRecentlyUsed(queue<MemoryBlock>& blocks, vector<PageTableEntry>& pageTable);
	static void modifyData(PageTableEntry& cur, PageTableEntry& old);
	static void printPageTable(vector<PageTableEntry> pageTable);
	static string calculatePhysicalAddress(vector<PageTableEntry>& pageTable, int pageNo, string addr, queue<MemoryBlock>& blocks, PageReplacementAlgorithm PRA);
public:
	static void requestPagingStorageManage(vector<PageTableEntry> pageTable, queue<MemoryBlock> blocks, queue<LogicInstruction> ops, PageReplacementAlgorithm PRA);
};

//RequestPagingStorageManagement.cpp
#include "RequestPagingStorageManagement.h"

/// <summary>
/// 打印页表
/// </summary>
/// <param name="pageTable">要打印的页表</param>
void RequestPagingStorageManagement::printPageTable(vector<PageTableEntry> pageTable)
{
	cout << "页号" << "\t标志" << "\t主存块号" << "\t修改标志" << "\t磁盘位置" << endl;
	for (int i = 0; i < pageTable.size(); i++)
	{
		cout << i << "\t" << pageTable[i].getAccess() << "\t" << pageTable[i].getBlockNo() << "\t\t" << pageTable[i].getModify() << "\t\t" << pageTable[i].getDiskPos() << endl;
	}
}

/// <summary>
/// 修改新页表项与老页表项的数据
/// </summary>
/// <param name="cur">新页表项</param>
/// <param name="old">老页表项</param>
void RequestPagingStorageManagement::modifyData(PageTableEntry& cur, PageTableEntry& old)
{
	cur.setBlockNo(old.getBlockNo());//老页表项的内存块分给新页表项
	cur.setAccess(1);//设置标志位
	cur.setModify(0);
	old.setAccess(0);
	old.setDiskPos(cur.getDiskPos());//为简便起见，直接交换磁盘空间
	cur.setDiskPos("");
}

/// <summary>
/// FIFO调度策略
/// </summary>
/// <param name="pageTable">页表</param>
/// <param name="blocks">所有内存块</param>
/// <param name="pageNo">页号</param>
void RequestPagingStorageManagement::FIFO(vector<PageTableEntry>& pageTable, queue<MemoryBlock>& blocks, int pageNo)
{
	PageTableEntry& cur = pageTable[pageNo];//当前要使用的页号，即在磁盘中将要换到内存中的页表项
	int index = findPageTableEntryByBlockNo(blocks.front().getBlockNo(), pageTable);//找到要被换到磁盘中的页表项的索引
	PageTableEntry& old = pageTable[index];//要被换到磁盘中的页表项
	cout << pageNo << "号与" << index << "号交换，";
	modifyData(cur, old);//修改页表项数据
	MemoryBlock& t = blocks.front();//第一个内存块换到最后
	blocks.pop();
	blocks.push(t);
}

/// <summary>
/// LRU调度策略
/// </summary>
/// <param name="pageTable">页表</param>
/// <param name="blocks">所有内存块</param>
/// <param name="pageNo">页号</param>
void RequestPagingStorageManagement::LRU(vector<PageTableEntry>& pageTable, queue<MemoryBlock>& blocks, int pageNo)
{
	PageTableEntry& cur = pageTable[pageNo];//当前要使用的页号，即在磁盘中将要换到内存中的页表项
	MemoryBlock* p = findLeastRecentlyUsed(blocks, pageTable);//寻找最近最久未使用的内存块
	int index = findPageTableEntryByBlockNo(p->getBlockNo(), pageTable);//找到内存号对应的页表项的索引
	PageTableEntry& old = pageTable[index];//将被换到磁盘的页表项
	cout << pageNo << "号与" << index << "号交换，";
	modifyData(cur, old);//修改页表项数据
	p->init();
}

/// <summary>
/// 寻找占用该内存块号的页表项的索引
/// </summary>
/// <param name="blockNo">内存块号</param>
/// <param name="pageTable">页表</param>
/// <returns>对应页表项的索引</returns>
int RequestPagingStorageManagement::findPageTableEntryByBlockNo(int blockNo, vector<PageTableEntry>& pageTable)
{
	for (int i = 0; i < pageTable.size(); i++)
	{
		if (pageTable[i].getBlockNo() == blockNo && pageTable[i].getAccess() == 1)
		{//必须是正在内存中的页表项
			return i;
		}
	}
	return -1;
}

/// <summary>
/// 寻找最近最久未使用的页表项占有的内存块
/// </summary>
/// <param name="blocks">内存块</param>
/// <param name="pageTable">页表</param>
/// <returns>对应的内存块的指针</returns>
MemoryBlock* RequestPagingStorageManagement::findLeastRecentlyUsed(queue<MemoryBlock>& blocks, vector<PageTableEntry>& pageTable)
{
	MemoryBlock* max = &blocks.front();
	int size = blocks.size();
	for (int i = 0; i < size; i++)
	{
		MemoryBlock* mb = &blocks.front();
		if (mb->getLastUsed() > max->getLastUsed() && pageTable[findPageTableEntryByBlockNo(mb->getBlockNo(), pageTable)].getAccess() == 1)
		{//寻找lastUsed最大的内存块 并且 当前内存块已经分配
			max = mb;
		}
		blocks.pop();
		blocks.push(*mb);
	}
	//因为pop会直接析构该元素，所以此时的指针只是副本，需要重新寻找真正的在blocks中的地址
	max = findBlock(max->getBlockNo(), blocks);//根据当前找到的最大值的内存块号寻找在blocks中的地址
	return max;
}

/// <summary>
/// 根据内存块号寻找对应内存块
/// </summary>
/// <param name="blockNo">内存块号</param>
/// <param name="blocks">所以内存块</param>
/// <returns>对应内存块的指针，未找到返回NULL</returns>
MemoryBlock* RequestPagingStorageManagement::findBlock(int blockNo, queue<MemoryBlock>& blocks)
{
	int size = blocks.size();
	MemoryBlock* p = NULL;
	bool flag = false;//标志是否找到
	for (int i = 0; i < size; i++)
	{
		flag = false;
		MemoryBlock& mb = blocks.front();
		if (mb.getBlockNo() == blockNo)
		{
			flag = true;
		}
		blocks.pop();//pop之后会调用析构函数，需要在push之后再用指针接收
		blocks.push(mb);
		if (flag)
		{
			p = &blocks.back();
		}
	}
	return p;
}

/// <summary>
/// 将所以内存块的lastUsed+1
/// </summary>
/// <param name="blocks">内存块</param>
void RequestPagingStorageManagement::increase(queue<MemoryBlock>& blocks)
{
	int size = blocks.size();
	MemoryBlock* p = NULL;
	for (int i = 0; i < size; i++)
	{
		p = &blocks.front();
		p->increase();
		blocks.pop();
		blocks.push(*p);
	}
}

/// <summary>
/// 计算物理地址
/// </summary>
/// <param name="pageTable">页表</param>
/// <param name="pageNo">页号</param>
/// <param name="addr">逻辑地址</param>
/// <param name="blocks">所有内存块</param>
/// <param name="PRA">页面置换策略</param>
/// <returns>逻辑地址对应的物理地址</returns>
string RequestPagingStorageManagement::calculatePhysicalAddress(vector<PageTableEntry>& pageTable, int pageNo, string addr, queue<MemoryBlock>& blocks, PageReplacementAlgorithm PRA)
{
	PageTableEntry cur = pageTable[pageNo];
	string phyAddr;
	MemoryBlock* p = NULL;
	if (cur.getAccess() == 1)//当前页表项在内存中
	{
		phyAddr = to_string(cur.getBlockNo()) + addr + "H";//计算物理地址
		MemoryBlock* p = findBlock(cur.getBlockNo(), blocks);
		increase(blocks);//所有内存块上次访问时间+1
		p->init();//当前页表项上次使用时间重置
	}
	else//当前页表项不在内存中
	{
		switch (PRA)
		{
		case PageReplacementAlgorithm::FIFO:
			cout << "使用FIFO策略进行置换，";
			FIFO(pageTable, blocks, pageNo);//使用FIFO策略
			cout << "置换后的页表：" << endl;
			printPageTable(pageTable);
			phyAddr = calculatePhysicalAddress(pageTable, pageNo, addr, blocks, PRA);//计算物理地址
			break;
		case PageReplacementAlgorithm::LRU:
			cout << "使用LRU策略进行置换，";
			LRU(pageTable, blocks, pageNo);//使用LRU策略
			cout << "置换后的页表：" << endl;
			printPageTable(pageTable);
			phyAddr = calculatePhysicalAddress(pageTable, pageNo, addr, blocks, PRA);//计算物理地址
			break;
		default:
			cout << "ERROR" << endl;
			break;
		}
	}
	return phyAddr;
}

/// <summary>
/// 请求分页式存储管理
/// </summary>
/// <param name="pageTable">页表</param>
/// <param name="blocks">所有内存块</param>
/// <param name="ops">所有逻辑指令</param>
/// <param name="PRA">页面置换策略</param>
void RequestPagingStorageManagement::requestPagingStorageManage(vector<PageTableEntry> pageTable, queue<MemoryBlock> blocks, queue<LogicInstruction> ops, PageReplacementAlgorithm PRA)
{
	cout << "初始页表为：" << endl;
	printPageTable(pageTable);
	cout << "------------------------------------------" << endl;
	LogicInstruction cur = ops.front();
	while (!ops.empty())//执行所有指令
	{
		cur = ops.front();
		ops.pop();
		cout << "执行指令 " << cur.getOp() << " " << cur.getPageNo1() << " " << cur.getAddr1() << " " << cur.getPageNo2() << " " << cur.getAddr2() << endl;
		string leftAddr = calculatePhysicalAddress(pageTable, cur.getPageNo1(), cur.getAddr1(), blocks, PRA);//计算左操作数物理地址
		string rightAddr = calculatePhysicalAddress(pageTable, cur.getPageNo2(), cur.getAddr2(), blocks, PRA);//计算右操作数物理地址
		cout << "执行结果(" << leftAddr << ")" << cur.getOp() << "(" << rightAddr << ")" << endl;
		cout << "------------------------------------------" << endl;
	}
	cout << "最终页表为：" << endl;
	printPageTable(pageTable);
	cout << "------------------------------------------" << endl;
}

	vector<PageTableEntry> pageTable;
	pageTable.push_back(PageTableEntry(1, 3, 1, ""));
	pageTable.push_back(PageTableEntry(1, 4, 1, ""));
	pageTable.push_back(PageTableEntry(1, 5, 1, ""));
	pageTable.push_back(PageTableEntry(0, 0, 1, "030"));
	pageTable.push_back(PageTableEntry(0, 0, 1, "025"));
	pageTable.push_back(PageTableEntry(0, 0, 1, "026"));
	queue<MemoryBlock> blocks;
	blocks.push(MemoryBlock(3, 1));
	blocks.push(MemoryBlock(4, 2));
	blocks.push(MemoryBlock(5, 3));
	queue<LogicInstruction> ops;
	ops.push(LogicInstruction('+', 0, "030", 2, "003"));
	ops.push(LogicInstruction('-', 1, "050", 2, "005"));
	ops.push(LogicInstruction('*', 2, "001", 5, "004"));
	ops.push(LogicInstruction('/', 3, "007", 1, "031"));
	PageReplacementAlgorithm PRA1 = PageReplacementAlgorithm::FIFO;
	PageReplacementAlgorithm PRA2 = PageReplacementAlgorithm::LRU;
	cout << "********************FIFO********************" << endl;
	RequestPagingStorageManagement::requestPagingStorageManage(pageTable, blocks, ops, PRA1);
	cout << "********************LRU********************" << endl;
	RequestPagingStorageManagement::requestPagingStorageManage(pageTable, blocks, ops, PRA2);

结果

FIFO
假设初始内存分配顺序为3、4、5，每次按先入先出的顺序置换页面，所以置换时也是一次按照3、4、5的顺序换出相应的数据
LRU
最近最久未使用，假设3、4、5内存块的上次使用的时间为1、2、3，所以5号内存块是最久未使用的，所以第一个换出的应该是5号内存块的数据

********************FIFO********************
初始页表为：
页号    标志    主存块号        修改标志        磁盘位置
0       1       3               1
1       1       4               1
2       1       5               1
3       0       0               1               030
4       0       0               1               025
5       0       0               1               026
------------------------------------------
执行指令 + 0 030 2 003
执行结果(3030H)+(5003H)
------------------------------------------
执行指令 - 1 050 2 005
执行结果(4050H)-(5005H)
------------------------------------------
执行指令 * 2 001 5 004
使用FIFO策略进行置换，5号与0号交换，置换后的页表：
页号    标志    主存块号        修改标志        磁盘位置
0       0       3               1               026
1       1       4               1
2       1       5               1
3       0       0               1               030
4       0       0               1               025
5       1       3               0
执行结果(5001H)*(3004H)
------------------------------------------
执行指令 / 3 007 1 031
使用FIFO策略进行置换，3号与1号交换，置换后的页表：
页号    标志    主存块号        修改标志        磁盘位置
0       0       3               1               026
1       0       4               1               030
2       1       5               1
3       1       4               0
4       0       0               1               025
5       1       3               0
使用FIFO策略进行置换，1号与2号交换，置换后的页表：
页号    标志    主存块号        修改标志        磁盘位置
0       0       3               1               026
1       1       5               0
2       0       5               1               030
3       1       4               0
4       0       0               1               025
5       1       3               0
执行结果(4007H)/(5031H)
------------------------------------------
最终页表为：
页号    标志    主存块号        修改标志        磁盘位置
0       0       3               1               026
1       1       5               0
2       0       5               1               030
3       1       4               0
4       0       0               1               025
5       1       3               0
------------------------------------------
********************LRU********************
初始页表为：
页号    标志    主存块号        修改标志        磁盘位置
0       1       3               1
1       1       4               1
2       1       5               1
3       0       0               1               030
4       0       0               1               025
5       0       0               1               026
------------------------------------------
执行指令 + 0 030 2 003
执行结果(3030H)+(5003H)
------------------------------------------
执行指令 - 1 050 2 005
执行结果(4050H)-(5005H)
------------------------------------------
执行指令 * 2 001 5 004
使用LRU策略进行置换，5号与2号交换，置换后的页表：
页号    标志    主存块号        修改标志        磁盘位置
0       1       3               1
1       1       4               1
2       0       5               1               026
3       0       0               1               030
4       0       0               1               025
5       1       5               0
执行结果(5001H)*(5004H)
------------------------------------------
执行指令 / 3 007 1 031
使用LRU策略进行置换，3号与1号交换，置换后的页表：
页号    标志    主存块号        修改标志        磁盘位置
0       1       3               1
1       0       4               1               030
2       0       5               1               026
3       1       4               0
4       0       0               1               025
5       1       5               0
使用LRU策略进行置换，1号与0号交换，置换后的页表：
页号    标志    主存块号        修改标志        磁盘位置
0       0       3               1               030
1       1       3               0
2       0       5               1               026
3       1       4               0
4       0       0               1               025
5       1       5               0
执行结果(4007H)/(3031H)
------------------------------------------
最终页表为：
页号    标志    主存块号        修改标志        磁盘位置
0       0       3               1               030
1       1       3               0
2       0       5               1               026
3       1       4               0
4       0       0               1               025
5       1       5               0
------------------------------------------
请按任意键继续. . .