先说下什么是页（页面）：就是将用户的程序的的地址空间分成固定大小的区域，称为”页“，或者”页面“
之后将这些页离散的放进内存中，这样解决了内存的碎片问题
记得老师上课说了下这两个概念不能混，现在区分下：
在第4章存储器管理，学习了分页式存储管理方式（是为了解决内存的碎片问题）
在第5章虚拟存储器，学习了请求分页式管理方式（除了解决碎片问题外，又“扩充”了内存的大小（虚拟））
在这里为了使得固定数目的内存来运行较多的进程，增加了调页功能和页面置换功能。
（在这可以看书或者笔记上的例题更好理解）
请求分页式存储管理需要一些硬件设备的支持：
1.请求页表机构
页号，物理块号，状态位（该页是否调入内存），访问字段（用于选择换出页），修改位（换出页是否要重写到外存），外存地址（换入页的地址）
2.缺页中断机构（这个是请求分页式存储管理特有的）
3.地址转换机构
就这些吧。
转载于:https://www.cnblogs.com/ldphoebe/p/4845007.html
操作系统实验四 请求分页式存储管理
题目描述：
一、实验目的
通过编写分页式存储管理的模拟程序，加深对页式存储管理方式的理解，熟悉逻辑地址到物理地址的转换过程，掌握虚拟存储管理中的页面调度算法，认识分页式虚拟存储系统中缺页中断的处理过程。
二、实验内容
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++; } }实验结果：
操作系统 请求分页式存储管理
实验要求
通过编写分页式存储管理的模拟程序，加深对页式存储管理方式的理解，熟悉逻辑地址到物理地址的转换过程，掌握虚拟存储管理中的页面调度算法，认识分页式虚拟存储系统中缺页中断的处理过程。实验内容
- 设计一个分页式虚拟存储系统，用程序模拟实现，假设页面大小为1K，每个进程分配三个块。
- 页面调度分别采用FIFO调度算法和LRU算法(堆栈法)。（选中页面直接交换。）
- 假设当前作业的页表如下：
- 假设逻辑指令格式为：
操作符 页号1 页内地址1 页号2 页内地址2
例如： 表示将页面1内地址为011单元的内容和页面2中地址为051的单元的内容相加，
如：（1011H）＋（1200H）。
现有指令序列如下：
- 编写模拟程序，执行上述指令，若当前页面不在内存，则使用页面调度算法，交换相应页。
- 要求每执行上述指令流中的一条逻辑指令，输出相应的物理指令，若页表有修改，则显示修改后的页表。
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 ------------------------------------------ 请按任意键继续. . .
模拟请求分页式存储管理
1. 实验要求
#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;
}
