下载文档原格式
请求页式存储管理中页表的组成
页式存储管理中，页表是管理页面和物理页面之间映射关系的数据结构，用于记录页面的虚拟地址和物理地址之间的对应关系。
页表的组成主要包括以下几个部分：
1. 页表项（Page Table Entry，PTE）：每个页表项记录了虚拟
页面的页号和对应的物理页面的帧号，以及一些控制位和标志位，如有效位（valid bit）用于指示该页是否已经分配。
2. 页表：页表是一个由页表项组成的数组，数组的索引即是虚拟页面的页号，每个页表项对应一个虚拟页面。
3. 页目录（Page Directory）：如果系统的虚拟地址空间较大，页表可能会非常大，而且维护和查找页表项也会比较费时。
为了简化管理和提高效率，可以引入多级页表机制，即使用页目录来管理页表。
页目录是一个由页目录项组成的数组，每个页目录项指向一个页表，实现了虚拟地址到页表的映射关系。
4. 页目录项（Page Directory Entry，PDE）：每个页目录项记
录了一个页表的物理地址和一些控制位和标志位，如有效位用于指示该页表是否已经分配。
以上是页式存储管理中页表的基本组成部分，具体的实现可能因系统架构和算法的不同而有所差异。
请求页式存储管理中页表的组成在计算机系统中，页式存储管理是一种常见的存储管理方式。
它将主存储器划分为固定大小的页框，将程序和数据分割成相同大小的页面，并将页面映射到页框中。
而页表则是页式存储管理中非常重要的组成部分。
页表是一种数据结构，用于记录页面和页框之间的映射关系。
它的主要作用是将逻辑地址转换为物理地址，实现虚拟内存到物理内存的映射。
在请求页式存储管理中，页表通常由两个部分组成：页目录和页表。
页目录是页表的第一级索引，用于将逻辑地址的高位映射到页表。
它的作用是将逻辑地址的高位转换为页表的物理地址，从而找到对应的页表。
页目录中的每个目录项都对应一个页表，每个目录项的大小通常为4字节。
页目录的大小取决于系统的虚拟地址空间大小和页框大小。
页表是页表的第二级索引，用于将逻辑地址的低位映射到页框。
它的作用是将逻辑地址的低位转换为页框的物理地址，从而找到对应的页框。
页表中的每个表项都对应一个页框，每个表项的大小通常为4字节。
页表的大小取决于系统的虚拟地址空间大小和页框大小。
在请求页式存储管理中，页表的组成可以根据系统的需求进行灵活的设计。
一种常见的设计是多级页表。
多级页表将页表分为多个级别，每个级别的页表都有自己的页目录和页表。
这种设计可以有效地减小页表的大小，提高地址转换的速度。
另一种常见的设计是倒排页表。
倒排页表将页表的索引和数据分开存储，通过索引表来查找页表的数据。
这种设计可以减小页表的大小，提高地址转换的速度。
但是倒排页表需要额外的索引表，增加了存储开销。
除了页目录和页表，页表还可以包含其他的信息，如访问权限、脏位、有效位等。
这些信息可以用于实现更加复杂的存储管理策略，如页面置换算法、页面共享等。
总之，请求页式存储管理中的页表是实现虚拟内存到物理内存映射的重要组成部分。
它由页目录和页表组成，可以根据系统的需求进行灵活的设计。
页表的组成和设计对于系统的性能和效率有着重要的影响，需要根据具体的应用场景进行选择和优化。
第十六讲存储器管理之请求分页存储管理方式1 基本概述请求分页管理是建立在基本分页基础上的，为了能支持虚拟存储器而增加了请求调页功能和页面置换功能。
基本原理：地址空间的划分同页式；装入页时，可装入作业的一部分(运行所需)页即可运行。
2 请求分页的硬件支持为实现请求分页，需要一定的硬件支持，包括：页表机制、缺页中断机构、地址变换机构。
2.1 页表机制作用：将用户地址空间的逻辑地址转换为内存空间的物理地址。
因为请求分页的特殊性，即程序的一部分调入内存，一部分仍在外存，因此页表结构有所不同。
如图：说明：（1）状态位P：指示该页是否已调入内存。
（2）访问字段A：记录本页在一段时间内被访问的次数或最近未被访问的时间。
（3）修改位M：表示该页在调入内存后是否被修改过。
若修改过，则换出时需重写至外存。
（4）外存地址：指出该页在外存上的地址。
2.2 缺页中断机构在请求分页系统中，每当所要访问的页面不在内存时，便产生缺页中断，请求OS将所缺的页调入内存。
缺页中断与一般中断的区别：（1）在指令执行期间产生和处理中断信号（2）一条指令在执行期间，可能产生多次缺页中断2.3 地址变换机构请求分页系统的地址变换机构。
是在分页系统地址变换机构的基础上，又增加了一些功能。
例：某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。
假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址0A5C和093C 变换为物理地址。
解：虚拟地址为：页号（2^5=32）5位页内位移（1K =2^10=1024）10位物理地址为物理块号（2^4=16）4位因为页内是10 位，块内位移（1K =2^10=1024）10位虚拟地址OA5C对应的二进制为：00010 1001011100即虚拟地址OA5C的页号为2，页内位移为1001011100，由题意知对应的物理地址为：0100 1001011100即125C同理求093C。
一、判断题并说明理由1、操作系统的基本思想是多道。
X 管理和控制系统资源2、分时系统的主要特点之一是交互性。
V3、高可靠性是实时系统的主要特点之一。
V4、请求页式存储管理是一种静态分区存储技术。
X 虚拟存储5、用户进程中使用的是从0开始编址的逻辑地址。
V1、作业的完成由相应的进程运行来实现。
2、联机控制方式用于终端型作业。
3、作业控制块由用户建立并保存于内存89。
V4、请求页式存储管理是一种交换技术。
X 虚拟存储5、在段页式存储管理中，段的长度由用户确定。
V1、“把某进程的状态变为运行”的指令是系统中的特权指令。
2、所谓“恢复现场”是指将现在信息恢复至CPU各相应的寄存器中。
3、在Windows系统中，使用的存储管理技术为请求页式。
X分区目录和文件目录的形式来存储的4、请求页式存储管理是一种静态分区存储技术。
X5、请求页式存储管理是一种虚拟存储技术。
V二、填空题（10分，每空1分）1. 从管理的角度看，外部设备的种类有输入设备和输出设备。
2. 缓冲区的组织形式主要有单缓冲、多缓冲、缓冲池。
3. 分区存储管理方法可分为单用户连续分区分区和固态分区。
4. 虚拟存储器的容量是由计算机系统的地址和结构确定的。
1. 现代操作系统的主要特征并发、共享、虚拟和异步。
2. 操作系统为用户提供两种类型的使用接口，即命令方式和系统调用和图形用户界面。
3. 用户的作业一般可分为批量型作业和终端型作业。
4. 作业控制方式分为两种，即脱机命令接口和联机命令接口。
5.“作业控制块”的英文缩写是JCB。
1. 外部设备的控制方式主要有4种程序直接控制方式、中断控制方式、DMA方式、通道方式。
其中第一种现在已基本不再采用。
2. 对磁盘上的一个物理块信息的访问时间包括寻道、读取、传输三部分。
3. 在资源分配图中，用圆圈代表一个继承，用方框代表每类资源，而方框中圆点则代表各类资源实例。
1. 产生死锁的四个必要条件是互斥条件和 CA：请求和阻塞条件； B：请求和释放条件；C：请求和保持条件； D：释放和阻塞条件；2. 在 A 中，要求空闲分区按空闲区地址递增顺序链接成空闲分区链；在 C_中是按空闲区大小递增顺序形成空闲分区链；在B 中，是按空闲区大小递减的顺序形成空闲分区链。
昆明理工大学信息工程与自动化学院学生实验报告（2012 —2013 学年第二学期）一、实验目的存储管理的主要功能之一是合理地分配空间。
请求页式管理是一种常用的虚拟存储管理技术。
通过本次实验, 要求学生通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解, 通过请求页式存储管理中页面置换算法模拟设计, 了解虚拟存储技术的特点, 掌握请求页式存储管理的页面置换算法。
二、实验原理及基本技术路线图（方框原理图）用C或C++语言模拟实现请求式分页管理。
要求实现: 页表的数据结构、分页式内存空间的分配及回收（建议采用位图法）、地址重定位、页面置换算法（从FIFO,LRU,NRU中任选一种）。
int subareaSize[num]={8,12,16,32,24,16,64,128,40,64};//分区大小Process *pro=NULL;//保持进程信息int ProcessNum=0;//进程数目int applyProcessNum=0;//每次申请进程数目int maxApplyNum=0;//最大可申请数目int *applyIndex=NULL;//申请进程队列int totalApplyNum=0;//申请总数int *assignPointer=NULL;//已分配内存的进程队列int assignFlag=0;//分配索引, 表示已申请队列已分配的进程数int exeIndex;//执行的进程号Node *subareaNode=new Node[3];//分区回收时, 进程所在分区及其前, 后分区信息LinkList createLinkList(int n );//建立空闲分区链Node firstFit(LinkList &head,Process pro);//首次适应算法Node nestFit(LinkList &head,Process pro,Node flag);//循环适应算法Node bestFit(LinkList &head,Process pro);//最佳适应算法Node worstFit(LinkList &head,Process pro);//最坏适应算法Node assign(LinkList &head,int orderIndex,int index,Node flagNode);//一次分区分配int assignMemory(LinkList &head);//内存分配void insertNode(LinkList &head,Node q,int index);//插入节点Node deleteNode(LinkList &head,int index);//删除节点int display(LinkList &head);//打印分区分配情况int lowAttemper(int *excursionPointer);//低级调度int findSubarea(LinkList &head,int index);//回收内存int creatProcess();//创建进程Process* randomCreatPro(int n);//随机产生进程下面是各种方法简述:(1) 最优替换算法, 即OPT算法。
实验六：请求分页存储管理一．实验目的深入理解请求页式存储管理的基本概念和实现方法，重点认识其中的地址变换、缺页中断、置换算法等实现思想。
二．实验属性该实验为综合性、设计性实验。
三．实验仪器设备及器材普通PC386以上微机四．实验要求本实验要求2学时完成。
本实验要求完成如下任务：（1）建立相关的数据结构：页表、页表寄存器、存储块表等；（2）指定分配给进程的内存物理块数，设定进程的页面访问顺序；（3）设计页面置换算法，可以选择OPT、FIFO、LRU等，并计算相应的缺页率，以比较它们的优劣；（4）编写地址转换函数，实现通过查找页表完成逻辑地址到物理地址的转换；若发生缺页则选择某种置换算法（OPT、FIFO、LRU等）完成页面的交换；（5）将整个过程可视化显示出来。
实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。
实验后认真书写符合规范格式的实验报告（参见附录A），并要求用正规的实验报告纸和封面装订整齐，按时上交。
三、设计过程3.1算法原理分析OPT算法是未来最远出现，当当前内存中没有正要访问的页面时，置换出当前页面中在未来的访问页中最远出现的页面或再也不出现的页面。
FIFO算法是先进先出，当当前内存中没有正要访问的页面时，置换出最先进来的页面。
LRU算法是最近最久未使用，当当前内存中没有正要访问的页面时，置换出在当前页面中最近最久没有使用的页面。
3.2数据定义int length,num_page,count,seed; //length记录访问串的长度，num_page页面数，count记录缺页次数int result[20][30],order[30],a[10]; //result记录结果,order存储访问串,a存储当前页面中的值int pos1,flag1,flag2,flag3; //pos1位置变量，flag1等为标志变量 char result1[30]; //记录缺页数组 void opt() //最佳void fifo() //先进先出bool search(int n) //查找当前内存中是否已存在该页3.3流程图与运行截图图6.1 FIFO （）函数流程图;否是 是否 开始得到执行的指令指令是否在内存中最先存入指令被淘汰下面是否还有指令 结束得出命中率图2.2 OPT算法流程图四、小结本次课程设计目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
实验八请求分页存储管理设计一、虚拟存储器的相关知识：1.概述：虚拟存储器(Virtual Memory)：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”。
虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。
作用：虚拟内存的作用内存在计算机中的作用很大，电脑中所有运行的程序都需要经过内存来执行，如果执行的程序很大或很多，就会导致内存消耗殆尽。
为了解决这个问题，Windows中运用了虚拟内存技术，即拿出一部分硬盘空间来充当内存使用，当内存占用完时，电脑就会自动调用硬盘来充当内存，以缓解内存的紧张。
举一个例子来说，如果电脑只有128MB物理内存的话，当读取一个容量为200MB的文件时，就必须要用到比较大的虚拟内存，文件被内存读取之后就会先储存到虚拟内存，等待内存把文件全部储存到虚拟内存之后，跟着就会把虚拟内存里储存的文件释放到原来的安装目录里了。
下面，就让我们一起来看看如何对虚拟内存进行设置吧。
2.请求分页虚拟存储系统是将作业信息的副本存放在磁盘这一类辅助存储器中，当作业被调度投入运行时，并不把作业的程序和数据全部装入主存，而仅仅装入立即使用的那些页面，至少要将作业的第一页信息装入主存，在执行过程中访问到不在主存的页面时，再把它们动态地装入。
用得较多的分页式虚拟存储管理是请求分页（demand paging），当需要执行某条指令或使用某个数据，而发现它们并不在主存时，产生一个缺页中断，系统从辅存中把该指令或数据所在的页面调入内存。
3.替换算法：替换规则用来确定替换主存中哪一部分，以便腾空部分主存，存放来自辅存要调入的那部分内容。
常见的替换算法有4种。
随机算法用软件或硬件随机数产生器确定替换的页面。
先进先出先调入主存的页面先替换。
近期最少使用算法替换最长时间不用的页面。
最优算法替换最长时间以后才使用的页面。
软件学院操作系统实验报告专业：软件工程班级： RB软工互152学号： 201560160226 学生姓名：王泽华指导教师：韩新超实验四：请求页式存储管理一．实验目的深入理解请求页式存储管理的原理，重点认识其中的地址变换、缺页中断、置换算法等实现思想。
二．实验属性该实验为综合性、设计性实验。
三．实验仪器设备及器材普通PC386以上微机四．实验要求本实验要求4学时完成。
本实验要求完成如下任务：（1）建立相关的数据结构：存储块表、页表等；（2）实现基本分页存储管理，如分配、回收、地址变换；（3）在基本分页的基础上实现请求分页存储管理；（4）给定一批作业/进程，选择一个分配或回收模拟；（5）将整个过程可视化显示出来。
实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。
实验后认真书写符合规范格式的实验报告（参见附录A），并要求用正规的实验报告纸和封面装订整齐，按时上交。
五、实验提示1、本实验虽然不以前面实验为基础，但建议在其界面中继续增加请求页式存储管理功能。
2、数据结构：内存分配表、页表空间（用数组实现），修改PCB结构增加页表指针、页表长度。
3、存储管理：编写内存分配、内存回收算法、页面置换算法。
4、主界面设计：在界面上增加一个请求分页内存分配按钮、请求分页内存回收按钮、装入指定进程的指定页按钮。
触发请求分页内存分配按钮，弹出作业大小输入框，输入后调用内存分配函数，在内存分配表和页表中看到分配的存储块。
触发请求分页内存回收按钮，弹出进程ID输入框，输入后调用内存回收函数，在内存分配表中看到回收后的状态改变。
5、功能测试：从显示出的内存分配表和页表，可查看操作的正确与否。
六、实验步骤（1）任务分析：1.最佳页面置换算法（OPT ）：其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。
采用最佳置换算法，通常可保证获得最低的缺页率。
2.最近最久未使用（LRU ）算法：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。
（2） 程序设计：程序功能模块图如下：（1在：所有线程都具有相同的地址空间（进程的地址空间）。
此外我们应该还要用控制语句，控制线程的同步执行。
2. 这个实验是要求我们采用算法模拟分页存储管理技术的FIFO 和LRU 算法。
所以我们应该先生成地址序列，有了地址序列，我们要找到它所在的虚页，然后通过查找实页，再判断下一步动作。
假如要访问的虚页不在内存中，不命中，我们要替换实页内容。
根据FIFO 算法，直接替换最早进入内存中的那一页就可以了。
所以可以设立一个循环指针，记录那个最早进入内存中的那页。
而对于LRU 算法，我们要替换是到现在为止最长时间没被访问的页，在这里我们可以用一个队列来表示内存。
把最久没使用的页放在队头，然后替换进去的页放在队尾就可以了。
假如要访问的虚页在内存中，明显是命中。
对于FIFO 算法，不处理，而对于LRU 算法，我们还要把他的权值置0。
（2）系统功能流程图：Y YN N（31.先进先出 定义一个队列存放页面，头指针记录最先进入队列的页面的位置，每次替换头指针指向的页面。
2.最近最少使用 定义一个二维数组，一维用来记录页面号，一维用来记录该页面被使用的次数，每次替换最近最少使用的页面（3）程序结果：在运行界面选择某个算法，运行结果，如图1，图2所示：图1新页进入计算过程数组第一 位，其余为一次下移 找到了吗？ 计算命中率 结束 找到了吗？比较现有页面计数项的大小，新页面替换最大项页面计算命中率结束图2（3）调试与测试：1.第一道涉及线程的题编译时总是发生错误，原来编译这类程序在原有的编译语言后要加上-pthread.2.第二个分页算法我们在系统结构课已经做过这个实验，所以有了一定的了解，加上一点修改就能够使用了。
所以没太花功夫。
七、实验总结通过实现请求页式存储管理的几种基本页面置换算法，了解了虚拟存储技术的特点。
通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解，也知道了几种算法的效率，也验证了LRU算法的命中率平均的比FIFO算法要高。
通过本次实验，我收获了很多。
我了解到编写程序不是首要任务，而是一种实现手段。
我们最重要的是如何做好需求分析和理清思路，做出正确、简介的流程设计，这样可以达到事半功倍的效果。
八、附录//# include <windows.h>//# include <iostream>#include"stdio.h"#include<conio.h>#include <malloc.h>#define N 16#define num 5 /*进程分配物理块数目*/int A[N]={1,2,3,4,5,6,7,8,5,2,3,2,7,8,1,4}; /*页表映像*/typedef struct page{ int address; /*页面地址*/struct page *next;}page;struct page *head,*run,*rear;void jccreat() /*进程分配物理块*/{ int i=1;page *p,*q;head=(page *)malloc(sizeof(page)); p=head;for(i=1;i<=num;i++) { q=(page *)malloc(sizeof(page));p->next=q; q->address=0; q->next=NULL; p=q; } rear=p;}int search(int n){page *p;int i=0;p=head;while(p->next){if(p->next->address==n){printf("Get it at the page %d\n",i+1);run=p;return 1;}p=p->next;i++;}return 0;}void changeOPT(int n,int position){int i;int total=0;int flag=1;int distance[num];int MAX;int order=0;page *p,*q;p=head->next;q=head->next;for(i=0;i<num;i++)distance[i]=100;i=0;while(p){if(p->address==0){flag=0;break;}p=p->next;i++;}if(!flag){p->address=n;printf("Change the page %d\n",i+1); }else{while(q)}for(i=position;i<N;i++){if(q->address==A[i])distance[total]=i-position;}total++;q=q->next;}MAX=distance[0];for(i=0;i<num;i++){if(distance[i]>MAX){MAX=distance[i];order=i;}}printf("Change the page %d\n",order+1); i=0;while(p){if(i==order)p->address=n;i++;p=p->next;}}void changeLRU(int n){int i=0;int flag=1;page *p,*delect;p=head->next;while(p){if(p->address==0){flag=0;p->address=n;printf("Change the page %d\n",i+1);break;}p=p->next;i++;}if(flag){delect=head->next;head->next=delect->next;printf("Delect from the head, and add new to the end.\n"); delect->address=n;rear->next=delect;rear=delect;rear->next=NULL;}}float OPT(){int i;int lose=0;float losef;float percent;for(i=0;i<N;i++){if(search(A[i])==0){lose++;changeOPT(A[i],i);}}losef=lose;percent=1-(losef/N);return percent;}float LRU(){int i;int lose=0;float losef;float percent;page *p;for(i=0;i<N;i++){if(search(A[i])==0){lose++;changeLRU(A[i]);}else{p=run->next;run->next=p->next;rear->next=p;rear=p;rear->next=NULL;printf("Move it to end of queue.\n");}}losef=lose;percent=1-(losef/N);return percent;}main() /*主函数部分*/{float percent;int choice;printf("Select the arithmetic:\n(1)OPT\n(2)LRU\nyour choice is:"); scanf("%d",&choice);/*选择页面置换算法*/jccreat(); /*创建进程*/if(choice==1) /*采用OPT算法置换*/{percent=OPT(); /*计算OPT时的缺页率*/printf("The percent of OPT is %f",percent);}else if(choice==2) /*采用LRU算法置换*/下载可编辑{percent=LRU(); /*计算LRU时的缺页率*/ printf("The percent of OPT is %f",percent);else printf("Your choice is invalid.");getch();}.专业.整理.。
