- 掌握操作系统主要的存储管理方式——页式存储管理
- 掌握常见的几种页面置换算法，并分析其优缺点
- 掌握以vue.js为前端框架的项目开发模式
请求调页是一种动态内存分配技术。它将页面的分配推迟到无法再推迟为止。换言之，一致推迟到进程要访问的页不在物理内存为止，从而引发一个缺页中断。该技术的引入主要是因为进程开始运行时并不访问地址空间的全部地址，甚至有一部分地址进程永远不会使用。其次，程序的局部性原理保证了在程序执行的每个阶段，真正使用的进程页只有一小部分，因此临时不用的物理页面可由其他进程使用。
根据以上背景，建立一个虚拟内存管理环境，实现以下任务：
现有数量为4的内存块即页框分配给某进程。假设每个页面可存放10条指令，该进程（作业）共320条指令，也即其地址空间为32页，初始状态并为有任何页被调入内存。现需要实现页面置换算法，如LRU算法和FIFO算法来模拟该进程执行过程中对应内存块的分配状况。
指令的顺序可由以下几种方法生成：
- 混合执行。50%的指令顺序执行，25%发指令分布在前地址部分，25%的指令分布在后地址部分。
- 顺序执行。指令按照地址依次执行
- 随机执行。不考虑程序的局部性原理，随机执行地址空间的任意指令。
建立该模拟环境模拟使用不同的指令顺序，不同的页面置换算法虚下的内存分配情况和缺页情况。
- vue3.x+Node.js
- vue-cli脚手架+webpack打包
- 在线运行：
https://redifinition.github.io/JoeOSManagement/
（若无法进入可挂梯子重试）
- 本地运行：
本项目依赖于npm和 Vue CLI ，运行前确保环境中已经配置 node.js
请在项目的根目录下打开Powershell窗口输入指令：
npm install可以下载项目依赖的文件包，接下来再通过：
npm run serve可在本地部署内存调页模拟网页。完成后依照命令窗口的提示可在浏览器中打开。默认在计算机localhost:8080端口运行。
出现以下页面，即可成功运行：
该项目为基于vue框架的前端网页。网页的初始页面如下图所示：
实现了以下的核心功能：
-
两种页面置换算法的切换
实现了在网页左侧的 内存调度控制模块 的页面置换算法一栏选择不同的页面置换算法运行。
-
指令执行顺序的切换
实现了在网页左侧的 内存调度控制模块 的指令执行顺序一栏选择不同的指令执行顺序运行。
-
实时展示缺页数、缺页率和每条指令的执行情况
在页面的左下角实时展示了当前的缺页数和缺页率；在"指令序列"板块可查看每条指令的缺页情况，换入页和换出页。
-
页框换页情况，指令执行情况的动态展示
在页面的中心处展示了需要调度的四个内存块，在指令执行时，内存块会动态展示正在调入的页号，正在执行的指令的相对地址。
-
指令执行方式的切换
在页面的右下角的 指令控制模块 可以选择不同的执行方式，包括 单步执行 和 连续执行 两种指令执行方式。并且设置了 重置 按钮，可以重置所有内容，回复至初始状态，方便新的过程模拟。同时，为保证指令执行的完整性，在进行连续执行时，单步执行按钮和重置按钮将被 禁用 。而在进行单步执行时，可随时点击 连续执行按钮进行快速执行。
除此以外，页面的顶栏的“关于”模块展示了有关该项目的其余信息。
页面置换算法发生在分页管理机制进行虚拟内存分配发生了 缺页中断时。发生缺页中断后，需要选择一个页面移出内存，以便为新调入的页面让出空间。用于决定换出哪一页的规则就成为页面置换算法。
本项目实现了两种置换算法。分别是 先进先出FIFO置换算法和 最久未使用 LRU 算法。
先进先出置换算法（FIFO）
该算法为最简单的页面置换算法。其实质是，总是选择在内存中停留时间最长，即最先调入内存的页面进行置换，因为其不再被使用的可能性比刚调入内存的可能性大。对此需要建立一个FIFO队列，每当一个页面被调入内存时，就将其插入队尾。在发生缺页中断时，将位于队头的最先调入内存的页面出队，进行页面置换。
FIFO最特别的地方在于器特有的 belady现象，也称为抖动现象，即当增加该进程分配的存储块的情况下，缺页率反而增加。
在该项目中，我使用了一个 FIFO队列 来存储每次调入页面时对应的内存块号。每次发生缺页中断时，获取队头的内存块号即最早调入页面对应的内存块号，然后换出内存块号对应的页面，进行页面置换。其核心代码如下：
//FIFO算法
FIFOAlgorithm:function()
{
let excIndex = this.FIFOArr[0];
this.FIFOArr.shift();//取出最先换页进入的内存块号
return excIndex;
},取出队列队头的元素，获取对应的内存块号，然后返回给指令执行主程序，进行对应的页面置换。
最近最久未使用LRU算法
该算法的依据是 程序的局部性原理。 通过一个作业在执行过程中过去的页面访问历史来退出未来的行为。该算法认为在过去一段时间不曾被访问过的页面，在最近的将来也不会被理解访问。程序的局部性原理也说明了在程序下一条执行的位置大概率在上一条指令的附近，也就是说下一个指令的执行位置大概率在刚放文过的页面内而不是很久没有访问过的页面。
因此，该算法的核心**是：在发生缺页中断并需要进行页面置换时，总是选择最近一段时间最久为使用的页面予以淘汰。
本项目使用一个LRU数组来记录每个内存块距离上次使用的时刻t，如下：
| 页框号 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| t | 3 | 0 | 4 | 5 |
比如当要发生页面置换时，根据上面的LRU数组，我们需要选择页框号为4所放入的页，将其换出，换入相应的新页面。
该算法的核心js代码如下：
//LRU算法
LRUAlgorithm:function()
{
//首先需要获取t值最大的元素的索引
let index=0;
let maxNum=this.LRUArray[0];//初始化最大值
for(let i=1;i<4;i++)
if(this.LRUArray[i]>maxNum)
index=i;
this.LRUArray[index]=0;
return index;
},除了核心算法外，该项目也提供了如下一些js函数，位于不同的组件位置。
| 函数名 | 位置 | 功能 |
|---|---|---|
| addOneOrder() | App.vue | 单步执行一条指令 |
| addOrder() | App.vue | 连续执行指令直至指令执行完毕 |
| deletePage(pageId) | App.vue | 换出页框号对应的页 |
| open() | App.vue | 显示指令执行完毕的提示信息 |
| reset() | App.vue | 重置所有内存块和页面 |
| createOrderInfo(add,lP,iP,oP) | OrderInfo.vue | 创建一个指令信息对象 |
| openMoreInfo() | Home.vue | 显示项目信息 |
-
混合执行
混合执行的指令生成方式如下：
先在0~319中产生一个随机数i，作为第一条指令的序号，之后顺序执行下一条指令i+1；
之后在0~i-1中产生一个随机数作为指令序号j，即在跳转到前地址部分；
之后在i+2~319中产生一个随机数执行，代表跳转到后地址，再顺序执行下一条指令。
对此首先采用FIFO算法，其运行结果如下
总缺页数为165次，总缺页率为51%。
而采用LRU算法，其运行结果如下：
总缺页数降低至138次，缺页率降低至43%，符合我们的预期，LRU算法比FIFO算法效果更佳。
-
顺序执行
顺序执行的页面置换较为简单直观，其缺页率均为10%，即按照顺序依次换页，这里不再截图演示。
-
随机执行
随机执行不能体现出程序的局部性原理，因此两种算法的换页效果均不理想，缺页率均在 90% 左右。
进入网页后，首先进入初始页面。
在左侧的内存调度控制模块可以点选对应的页面置换算法和指令执行顺序；随后即可选择指令执行方式，如图所示：
在指令控制模块点击执行后，指令开始执行。在左侧可以查看当前实时的缺页数和缺页率，在中心可查看内存块的换页情况；在指令序列模块可划动查看指令的执行信息，如下图所示：
注意在点击连续执行后， 单步执行按钮和重置按钮将被禁用。
当指令执行完毕时，显示如下信息：
查看结果完毕后，点击重置按钮即可重置所有信息，重复上述的步骤。
项目亮点
- 实现了两种页面置换算法，三种指令执行顺序，两种指令执行方式，可多次执行，操作便捷。
- 直观展示了页面置换的过程，每条指令的执行情况，同时动态展示了缺页数和缺页率，界面美观。
- 项目部署成网页，方便展示。
项目不足
- 项目的指令执行顺序的生成存在不合理的地方。其中混合执行方式不能很好的模拟计算机实际执行指令的顺序，模拟情况还不够好。
- 页面置换算法众多，该项目暂时还未实现其他的亚眠置换算法。
- 项目部分参数固定无法改变，降低了项目的灵活性和复用性。
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent