实验二-虚拟存储器

实验二虚拟存储器一、实验内容模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断。二、实验目的在计算机系统中，为了提高主存利用率，往往把辅助存储器〔如磁盘〕作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。通过这次实习理解在分页式存储管理中怎样实现虚拟存储器。深入了解分页式存储管理如何实现地址转换,进一步认识分页式虚拟存储管理中如何处理缺页中断。三、实验题目题目一：模拟分页式存储管理中硬件的地址转换和产生缺页中断1.概要设计分页式存储管理中地址转换过程很简单，假定主存块的大小为2n字节，主存大小为2m'字节和逻辑地址m位，那么进行地址转换时，首先从逻辑地址中的高m-n位中取得页号，然后根据页号查页表，得到块号，并将块号放入物理地址的高m'-n位，最后从逻辑地址中取得低n位放入物理地址的低n位就得到了物理地址，过程如图1所示。页页号页内地址块号块内地址页号…块号………物理地址逻辑地址m'nn-10mnn-10图1页式存储管理系统地址转换示意图地址转换是由硬件完成的，实验中使用软件程序模拟地址转换过程，模拟地址转换的流程图如图2.7所示〔实验中假定主存64KB，每个主存块1024字节，即n=10,m'=16，物理地址中块号6位、块内地址10位；作业最大64KB，即m=16，逻辑地址中页号6位、页内地址10位〕。在分页式虚拟存储管理方式中，作业信息作为副本放在磁盘上，作业执行时仅把作业信息的局部页面装入主存储器，作业执行时假设访问的页面在主存中，那么按上述方式进行地址转换，假设访问的页面不在主存中，那么产生一个“缺页中断〞，由操作系统把当前所需的页面装入主存储器后，再次执行时才可以按上述方法进行地址转换。页式虚拟存储管理方式中页表除页号和该页对应的主存块号外，至少还要包括存在标志〔该页是否在主存〕，磁盘位置〔该页的副本在磁盘上的位置〕和修改标志〔该页是否修改正〕。缺页处理过程简单阐述如下：①根据当前执行指令中逻辑地址中的页号查页表，判断该页是否在主存储器中，假设该页标志为“0〞，形成缺页中断。中断装置通过交换PSW让操作系统的中断处理程序占用处理器；②操作系统处理缺页中断的方法就是查主存分配表，找一个空闲主存块；假设无空闲块，查页表，选择一个已在主存的页面，把它暂时调出主存。假设在执行过程中该页被修改正，那么需将该页信息写回磁盘，否那么不必写回；③找出该页的磁盘位置，启动磁盘读出该页信息，把磁盘上读出的信息装入第2步找到的主存块，修改页表中该页的标志为“1〞；④由于产生缺页中断的那条指令没有执行完，所以页面装入后应重新执行被中断的指令。当重新执行该指令时，由于要访问的页面已在主存中，所以可正常执行。关于第②步的查找装入新页面的主存块的处理方式，不同系统采用的策略可能有所不同，这里采用局部置换算法，就是每个作业分得一定的主存块，只能在分得的主存块内查找空闲块，假设无空闲主存块，那么从该作业中选择一个页面淘汰出主存。2、主要数据结构设计⑴、structinfo//页表{boolflag;标志//用来表示对应页是否已经装入主存，标志位＝1，那么表示页已经在主存，标志位＝0，那么表示该页尚未装入主存。longblock;主存块号//用来表示已经装入主存的页所站的块号longdisk;磁盘位置即磁盘块号//用来指出作业副本的每一页被存放在磁盘上的位置}pagelist[SizeOfPage];//定义结构体用来存储页表信息〔2〕.作业执行时，指令中的逻辑地址指出了参加运算的操作数存放的页号和单元号，硬件的地址转换机构按页号查页表，假设该页对应标志为“1〞，那么表示该页已在主存，根据关系式：绝对地址＝块号×块长＋单元号计算出欲访问的主存单元地址。假设访问的页对应标志为“0〞，那么表示该页不在主存，这时硬件发“缺页中断〞信号，由操作系统按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。〔3〕.设计一个“地址转换〞函数work_ex()来模拟硬件的地址转换工作。当访问的页在主存时，那么形成绝对地址。当访问的页不在主存时，那么输出“*该页页号〞，表示产生了一次缺页中断。〔4〕.假定主存的每块长度为128字节；现有一个共七页的作业，在函数init_ex()中对页表初始化，将第0页到第3页中的内容装入主存中，其余三页未装入主存；该作业的页表如表2：表2主存中页表格式015011118012219013311021400225002360121如果作业依次为执行的指令序列，作业执行指令序列表，如表3:表3作业执行指令序列表操作页号单元号操作页号单元号＋0070移位4053＋1050＋5023×2015存1037存3021取2078取0056+4001－6040存6084〔5〕.在主函数intmain()中调用函数work_ex()和函数init_ex()，实现地址的转换和产生缺页中断。3、流程图否是结束取下一条指令有后继指令？是输出绝对地址形成绝对地址否输出“*〞页号表示发生缺页中断该页标志＝1？查页表取指令中访问的页号取一条指令开始否是结束取下一条指令有后继指令？是输出绝对地址形成绝对地址否输出“*〞页号表示发生缺页中断该页标志＝1？查页表取指令中访问的页号取一条指令开始4.源程序#include<iostream>usingnamespacestd;#definedata128structleaftable//页表{longleafnumber;//叶号boolflag;//标志longblock;//块号longdisk;//在磁盘上的位置}pagelist[7];voidwork(longa,longb){for(inti=0;i<7;i++) {if(a==pagelist[i].leafnumber&&pagelist[i].flag) { cout<<"块号为："<<pagelist[i].block<<",单元号为："<<b; cout<<"绝对地址为："<<pagelist[i].block*data+b<<endl; }elseif(a==pagelist[i].leafnumber&&!pagelist[i].flag)cout<<"*"<<"在磁盘上的位置为："<<pagelist[i].disk<<endl; }}voidinit_ex()//把页表初始化{pagelist[0].leafnumber=0;pagelist[0].flag=1;pagelist[0].block=5;pagelist[0].disk=011;pagelist[1].leafnumber=1;pagelist[1].flag=1;pagelist[1].block=8;pagelist[1].disk=012;pagelist[2].leafnumber=2;pagelist[2].flag=1;pagelist[2].block=9;pagelist[2].disk=013;pagelist[3].leafnumber=3;pagelist[3].flag=1;pagelist[3].block=1;pagelist[3].disk=021;pagelist[4].leafnumber=4;pagelist[4].flag=0;pagelist[4].disk=022;pagelist[5].leafnumber=5;pagelist[5].flag=0;pagelist[5].disk=023;pagelist[6].leafnumber=6;pagelist[6].flag=0;pagelist[6].disk=121;}voidmain(){longleaf,d; init_ex();inti=1;while(i) { cout<<"请输入要执行指令的页号和单元号："<<endl; cin>>leaf>>d; work(leaf,d);cout<<"是否执行下一条指令，是:输入，不是：输入"<<endl;cin>>i; }}5.实验结果：题目二：用先进先出页面置换算法〔FIFO〕处理缺页中断1、程序用到的数据结构typedefstructpage{intyemian;//页面号intbiaoji;//被访问标记}page;/*页面逻辑结构，结构为方便算法实现设计*/2、算法流程图：3、源程序#include<iostream>usingnamespacestd;#include<stdlib.h>constintNsize=10;constintPsize=12;typedefstructpage{intyemian;//页面号intbiaoji;//被访问标记}page;/*页面逻辑结构，结构为方便算法实现设计*/pageblock[Nsize];//物理块pagepage[Psize];//页面号串voidInit(intQString[],intNsize){//初始化内存单元、缓冲区for(inti=0;i<Nsize;i++) { block[i].yemian=-1;//找到空闲内存block[i].biaoji=0; }for(inti=0;i<Psize;i++) {page[i].yemian=QString[i];page[i].biaoji=0; }}intfindSpace(intNsize){//查找是否有空闲内存for(inti=0;i<Nsize;i++) {if(block[i].yemian==-1) {returni;//找到空闲内存，返回BLOCK中位置 } }return-1;}intfindExist(intcurpage,intNsize){//查找内存中是否有该页面for(inti=0;i<Nsize;i++) {if(block[i].yemian==page[curpage].yemian) {returni;//找到内存中有该页面，返回BLOCK中位置 } }return-1;}intfindReplace(intNsize){//查找应予置换的页面inta=0;for(inti=0;i<Nsize;i++) {if(block[i].biaoji>=block[a].biaoji) { a=i;//找到应予置换页面，返回BLOCK中位置 } }returna;}voiddisplay(intNsize){//显示for(inti=0;i<Nsize;i++) {if(block[i].yemian!=-1)//非空闲内存 {cout<<block[i].yemian<<""; } }cout<<endl;}/*FIFO核心局部*/voidFIFO(intNsize){//先进先出页面置换算法intexist,space,aition;floatscore=0;for(inti=0;i<Psize;i++) {exist=findExist(i,Nsize);if(exist!=-1)//内存中有该页面 {cout<<"不缺页"<<endl; score+=1;//统计不缺页次数 }else {space=findSpace(Nsize);if(space!=-1)//找到空闲内存 {block[space]=page[i];display(Nsize); }else {aition=findReplace(Nsize);//找到应予置换页面block[aition]=page[i];display(Nsize); } }for(intj=0;j<Nsize;j++) { block[j].biaoji++;//BLOCK中所有页面biaoji++ } }cout<<"缺页次数为："<<20-score<<endl;cout<<"缺页率为："<<(20-score)*100/20<<"%"<<endl;}voidBlockClear(intNsize){//块去除for(inti=0;i<Nsize;i++){block[i].yemian=-1;block[i].biaoji=0;}}voidmain(void){inti,Nsize,QString[Psize]={0};cout<<"请输入12个数：\n";for(i=0;i<12;i++) {cin>>QString[i]; }cout<<"页面号引用串:";for(i=0;i<12;i++){cout<<QString[i]<<"";}cout<<endl;cout<<"请输入分配的物理块数的大小:";cin>>Nsize;if(Nsize>0&&Nsize<=10) {Init(QString,Nsize);cout<<"页面号引用串:";for(i=0;i<Psize;i++) {cout<<QSt