实验四 页式虚拟存储管理中地址转换和页式中断 FIFO LRU OPT C++版本教学内容文档格式.docx
《实验四 页式虚拟存储管理中地址转换和页式中断 FIFO LRU OPT C++版本教学内容文档格式.docx》由会员分享，可在线阅读，更多相关《实验四 页式虚拟存储管理中地址转换和页式中断 FIFO LRU OPT C++版本教学内容文档格式.docx（18页珍藏版）》请在冰点文库上搜索。
//该页存放在磁盘上的位置，即磁盘块号
}page[n];
//页表定义
2）地址转换算法的实现
地址转换是由硬件完成的，实验中使用软件程序模拟地址转换过程。
在实验中，每个主存块1024字节，则块内地址占10位；
主存64KB，则主存共64块，即块号占6位；
物理地址共占16位；
作业最大64KB，则作业最大占64块，即页号占6位，逻辑地址共占16位。
（用主存的大小计算物理地址位数，用最大作业大小计算逻辑地址位数）。
在页式虚拟存储管理方式中，作业信息作为副本放在磁盘上，作业执行时仅把作业信息的部分页面装入主存储器，作业执行时若访问的页面在主存中，则进行地址转换，若访问的页面不在主存中，则产生一个“缺页中断”，由操作系统把当前所需要的页面装入主存储器后，再次执行时才可以按上述方法进行地址转换。
模拟地址转换流程度
3）
缺页中断处理算法的实现
缺页处理过程简单阐述如下：
a）根据当前执行指令中逻辑地址的页号查找页表，判断该页是否在主存储器中，若该页标志为“0”，形成缺页中断。
中断装置通过交换PSW让操作系统的中断处理程序占用处理器。
b）操作系统处理缺页中断的方法及时查主存分配表，找一个空闲主存块；
若无空闲块，查页表，选择一个已在主存的页面，把它暂时调出主存。
若在执行过程中该页被修改过，则需将该页信息写回磁盘，否则不比写回；
c）找出该页的位置，启动磁盘读出该页的信息，把磁盘上读出的信息装入第2不找到的主存块，修改页表中该页的标志为“1”；
d）由于产生缺页中断的那条指令还没有执行完，所以页面装入后应该重新执行被中断的指令。
当重新执行该指令时，由于要访问的页面已在主存中，所以可以正常执行。
关于第二步的查找装入新页面的主存块处理方式，不同系统采用的策略可能有所不同，这里采用局部置换算法，就是每个作业分得一定的主存块，只能在分得的主存块内查找空闲块，若无空闲主存块，则从该作业中选择一个页面淘汰出主存。
实验中采用局部置换算法。
使用局部置换算法时，存在这样一个问题：
就是在分配给作业主存空间时，装入哪些页？
有的系统采取不装入任何一页，当执行过程中需要时才将其调入。
有点系统采用页面预置的方法，事先估计可能某些页面会先用到，在分配主存块后将这些页面装入。
在本实验中采用第二种方法，分配主存空间时将前几页调入主存，假定系统中每个作业分得主存块m块，则将第0~m-1页装入主存。
因为是模拟硬件工作，所有在实验中如果访问的页不再主存中时，则输入该页页号，表示硬件产生缺页中断，然后直接转去缺页中断处理；
由于采用页面预置方法，在给定的主存块中一定无空闲块，只能淘汰已在主存的一页；
没有启动磁盘的工作，淘汰的页面需要写回磁盘时，用输入页号表示，调入新的一页时，将该页在页表中的存在标志置为“1”，输出页号表示将该页调入主存。
当主存中无空闲块时，为装入一个页面，必须按照某种算法从已在主存的页中选择一页，将它暂时调出主存，让出主存空间，用来存放装入的页面，这个工作称为“页面调度”。
常用的页面调度算法有：
先进现出、最近最少用算法、和最近最不常用算法。
在本实验中采用先进现出调度算法。
先进现出算法总是选择驻留在主存时间最长的一页调出。
实验中把主存储器的页的页号按照进入主存的先后次序拍成队列，每次总是调出对首的页，当装入一个新页后，把新页的页号排入对尾。
实验中，用一个数组存放页号的队列。
假定分配给作业的主存块数为m，数组可由m个元素组成，p[0],p[1],p[2]……p[m-1];
对首指针head;
采用页面预置的方法，页号队列的长度总是m，tail等于（head+1）%m。
因此可以使用一个指针，只用head即可。
在装入一个新的页时，装入页和淘汰页同时执行，当装入一个新的页时，将其页号存入数组：
淘汰页的页号＝p[head];
p[head]=新装入页的页号；
head=（head+1）%m;
实验执行一条指令时，不模拟指令的执行，只是考虑指令执行是否修改页面，若修改页面，则将该页的页表中的修改标志位置“1”，然后输出转换后的物理地址，并输出物理地址来表示一条指令执行完成；
如果访问的页不在主存时，则产生缺页中断，然后直接转去缺页中断处理，最后模拟中断返回，就是返回冲进进行地址转换。
因为没有实际主存，所有在模拟程序中首先手工输入页表信息，创建该作业的页表；
然后循环执行假定的指令，观察地址转换情况。
五、练习题
采用LRU页面调度算法编程实现上述虚拟页式存储管理的地址转换。
源代码
#include<
iostream.h>
#definen64//页表的最大长度
#definelength4//系统为每个作业分配的主存块数
intm;
intpage_length;
//页表的实际长度
intp[length];
//用向量模拟主存
inthead;
voidpage_interrupt（int）;
//缺页中断处理函数
voidcommand（unsigned,int）;
//命令处理函数
voidmain（）
{
intlnumber,pnumber,write,dnumber;
unsignedladdress;
inti;
cout<
<
"
输入页表的信息，创建页表（页号从0开始，若页号为－1，则结束输入）\n"
;
请输入页号和辅存地址：
cin>
>
lnumber>
dnumber;
cin.ignore（）;
i=0;
while（lnumber!
=-1）
{
page[i].lnumber=lnumber;
page[i].flag=0;
page[i].write=0;
page[i].dnumber=dnumber;
i++;
cout<
请输入页号和辅存地址:
cin>
}
//预先将输入的页调入主存块中
page_length=i;
输入主存块号（输入少于或者等于"
i<
个数据，若块号数为－1，则结束输入）:
pnumber;
m=0;
head=0;
while（m<
length&
&
pnumber!
if（m<
i）
{
page[m].pnumber=pnumber;
page[m].flag=1;
//调入主存后，标志为置1
p[m]=m;
//记录主存中的页号
m++;
}
cin.ignore（）;
}//while
输入指令性质（1－修改，0－不需要，其他－结束程序运行）和逻辑地址\n"
<
逻辑地址最大能支持2的16次方－1＝65535。
\n"
输入指令性质：
write;
输入逻辑地址：
laddress;
while（write==0||write==1）
command（laddress,write）;
//将输入的逻辑地址转换成物理地址
if（write!
=0&
write!
=1）break;
}//main
/*中断处理函数，采用先进先出的页面调度算法*/
voidpage_interrupt（intlnumber）
intj;
发生缺页中断"
lnumber<
endl;
j=p[head];
p[head]=lnumber;
head=（head+1）%m;
if（page[j].write==1）
将页"
j<
写回磁盘第"
page[j].dnumber<
块！
page[j].flag=0;
page[lnumber].pnumber=page[j].pnumber;
page[lnumber].flag=1;
page[lnumber].write=0;
淘汰主存块"
page[j].pnumber<
中的页"
从磁盘第"
page[lnumber].dnumber<
块中调入页"
}
/*地址转换函数，将逻辑地址转换成物理地址，如果要查找的页不在主存当中则产生缺页中断*/
voidcommand（unsignedladdress,intwrite）
unsignedpaddress,ad,pnumber;
kk:
lnumber=laddress>
10;
//取逻辑地址高6位，页号
ad=laddress&
0x3ff;
//页内地址
该逻辑地址的页号为：
页内地址为：
ad<
if（lnumber>
=page_length）
{//页号大于页表的长度，则无效页号
该页不存在！
return;
if（page[lnumber].flag==1）{//页号为lnumber在内存当中
pnumber=page[lnumber].pnumber;
paddress=pnumber<
10|ad;
逻辑地址是：
laddress<
对应物理地址是：
paddress<
if（write==1）//该页被修改过
page[lnumber].write=1;
else
{//页号为lnumber不在内存当中，则产生缺页中断
page_interrupt（lnumber）;
gotokk;
}//command
页式存储管理OPT，LRU实验报告
一、实验目的：
掌握分页式存储管理的基本概念和实现方法。
要求编写一个模拟的分页式管理程序，并能对分页式存储的页面置换算法进行编写和计算各个算法的缺页率。
二、程序设计：
首先创建页面链指针数据结构，并设计页面映像表，采用数组的方法给定页面映像。
申请缓冲区，将一个进程的逻辑地址空间划分成若干个大小相等的部分，每一部分称做页面或页。
每页都有一个编号，叫做页号，页号从0开始依次编排，如0，1，2……。
设置等大小的内存块。
初始状态：
将数据文件的第一个页面装入到该缓冲区的第0块。
设计页面置换算法，这里分别采用最佳页面置换算法OPT和最近最久未使用置换算法LRU,并分别计算它们的缺页率，以比较它们的优劣。
三、算法说明：
执行程序时，当主存没有可用页面时，为了选择淘汰主存中的哪一页面，腾出1个空闲块以便存放新调入的页面。
淘汰哪个页面的首要问题是选择何种置换算法。
该程序采用人工的方法选择，依置换策略选择一个可置换的页，并计算它们的缺页率以便比较。
/*分页式管理实验-源程序*/
stdlib.h>
conio.h>
stdio.h>
string.h>
#defineN16
#definenum5/*进程分配物理块数目*/
intA[N]={1,2,3,4,5,6,7,8,5,2,3,2,7,8,1,4};
/*页表映像*/
typedefstructpage
{
intaddress;
/*页面地址*/
structpage*next;
}page;
structpage*head,*run,*rear;
voidjccreat（）/*进程分配物理块*/
inti=1;
page*p,*q;
head=（page*）malloc（sizeof（page））;
p=head;
for（i=1;
=num;
i++）
q=（page*）malloc（sizeof（page））;
p->
next=q;
q->
address=0;
next=NULL;
p=q;
rear=p;
intsearch（intn）
page*p;
inti=0;
while（p->
next）
if（p->
next->
address==n）
printf（"
Getitatthepage%d\n"
i+1）;
run=p;
return1;
p=p->
next;
return0;
voidchangeOPT（intn,intposition）
inttotal=0;
intflag=1;
intdistance[num];
intMAX;
intorder=0;
p=head->
q=head->
for（i=0;
num;
distance[i]=100;
while（p）
address==0）
flag=0;
break;
if（!
flag）
address=n;
printf（"
Changethepage%d\n"
while（q）
{
for（i=position;
N;
i++）
{
if（q->
address==A[i]）
distance[total]=i-position;
total++;
q=q->
MAX=distance[0];
for（i=0;
if（distance[i]>
MAX）
MAX=distance[i];
order=i;
}
order+1）;
i=0;
while（p）
if（i==order）
p->
i++;
p=p->
}
}
voidchangeLRU（intn）
page*p,*delect;
p->
break;
if（flag）
delect=head->
head->
next=delect->
Delectfromthehead,andaddnewtotheend.\n"
）;
delect->
rear->
next=delect;
rear=delect;
floatOPT（）
intlose=0;
floatlosef;
floatpercent;
if（search（A[i]）==0）
lose++;
changeOPT（A[i],i）;
losef=lose;
percent=1-（losef/N）;
returnpercent;
floatLRU（）
if（search（A[i]）==0）
changeLRU（A[i]）;
else
p=run->
run->
next=p->
rear->
next=p;
rear=p;
Moveittoendofqueue.\n"
}
voidmain（）/*主函数部分*/
intchoice;
printf（"
Selectthearithmetic:
\n
（1）OPT\n
（2）LRU\nyourchoiceis:
scanf（"
%d"
&
choice）;
/*选择页面置换算法*/
jccreat（）;
/*创建进程*/
if（choice==1）/*采用OPT算法置换*/
percent=OPT（）;
/*计算OPT时的缺页率*/
ThepercentofOPTis%f"
percent）;
elseif（choice==2）/*采用LRU算法置换*/
percent=LRU（）;
/*计算LRU时的缺页率*/
elseprintf（"
Yourchoiceisinvalid."
getch（）;
升级会员 