请求分页存储管理.docx
- 文档编号:12819619
- 上传时间:2023-06-08
- 格式:DOCX
- 页数:22
- 大小:19.90KB
请求分页存储管理.docx
《请求分页存储管理.docx》由会员分享,可在线阅读,更多相关《请求分页存储管理.docx(22页珍藏版)》请在冰点文库上搜索。
请求分页存储管理
实验3请求分页存储管理
实验目的
(1)熟悉主存的分配与回收;
(2)了解虚拟存储技术的特点;
(3)掌握请求页式存储管理的页面置换算法;
实验内容与步骤
1、实验准备知识
(1)通过随机数产生一个指令序列
(2)将指令序列变换成为页地址流设:
(3)计算并输出下述各种算法在不同内存容量下的命中率
a)先进先出的算法(FIFO);
b)最近最少使用算法(LRU);
c)最佳淘汰算法(OPT);
(4)所涉及的算法
1)FIFO算法
定义变量ptr。
一开始先预调页填满内存。
在这一部分,ptr指向下一个要存放的位置。
之后继续执行剩下的指令。
此时,ptr表示队列最前面的位置,即最先进来的位置,也就是下一个要被替换的位置。
ptr用循环加,即模拟循环队列。
2)LRU算法
定义数组ltu[],即last_time_use来记录该页最近被使用的时间。
定义变量ti模拟时间的变化,每执行一次加一。
这个算法,我没有预调页,而是直接执行所有指令。
若当前需要的页没在内存里,就寻找最近最少使用的页,也就是ltu[]最小的页,即最近一次使用时间离现在最久的页,然后替换掉它。
或者在内存还未满时,直接写入,这个我以初始化内存里所有页为-1来实现。
若已经在内存里了,则只遍历内存内的页,把当前页的最近使用时间改一下即可。
3)OPT算法
定义数组ntu[],即next_time_use来记录下一次被使用的时间,即将来最快使用时间。
初始化为-1.
开始时预调页填满内存里的页。
同样利用变量ptr来表示下一个要存放的位置从而控制预调页的过程。
接着初始化ntu数组为-1。
然后求出每一页下一次被使用的指令号,以此代替使用时间。
如果所有剩下的序列都没有用该页时,则还是-1.这种值为-1的页显然是最佳替换对象。
然后执行所有剩下的指令。
当该页不在内存里时,遍历ntu数组,遇到-1的直接使用该页,没有则用ntu[]值最大的,也就是最晚使用的。
无论该页在不在内存里,因为这一次已经被使用了,所以都应该更新这个页的ntu[],只需往前看要执行的页流,记录下第一个遇到的该页即可。
如果没有找到同样添-1即可。
2、实验步骤
(1)首先,初始化数据
(2)测试地址转换机构
参考代码如下:
privatevoidAddressTransform(stringfunctionName)
{
//该数组用来存储调用页面号的序列
int[]numbers=_pageNumbers;
//调用页面列表的副本,用于循环调用列表时的操作
List
//初始化调用页表和快表
for(inti=0;i { varentry=newPageTableEntry{PageNumber=numbers[i],BlockNumber=numbers[i]+1}; //形成页面部分在快表的情况,规定: 页面号为偶数的在快表中有记录 if(i%2==0) { entry.IsInMemory=true; fastTable.Add(newFastTable{PageNumber=entry.PageNumber,BlockNumber=entry.BlockNumber}); } else { entry.IsInMemory=false; } entry.VisitTimes=0; entry.IsModified=false; entry.DiskPosition=_minBlockNumber; invokePage.Add(entry); copyInvokeTable.Add(entry); } //输出TextBox SwitchTxtToShow(functionName,"当前内存最小物理块数为: "+_minBlockNumber.ToString()+",可用物理块数为: "+_minBlockNumber.ToString()+"\r\n开始进行页面调度: "); //进行地址变换流程,从调用列表第一个页面开始调度,循环的是copyInvokeTable,每循环一次对invokePage原本进行移除操作 foreach(varitemincopyInvokeTable) { //判断functionName对应的算法是否执行过了,如果有执行过,则mark>0,跳出循环结束页面调度 if(_mark>0) { break; } SwitchTxtToShow(functionName,"\r\n当前调度的页面号为: "+item.PageNumber.ToString()); //页号>页表长度? if(item.PageNumber>_pageTable.Length) { SwitchTxtToShow(functionName,"越界中断"); } else { //查询快表 for(inti=0;i { //页表项在快表中? if(fastTable[i].PageNumber==item.PageNumber&&fastTable[i].BlockNumber==item.BlockNumber) { SwitchTxtToShow(functionName,"\r\n当前页面存在快表中,修改访问位和修改位"); //修改访问位和修改位 item.IsModified=false; item.VisitTimes+=1; //形成物理地址,在本程序中无太大作用,故不作编写 //判断内存是否满 if(_isMemoryFull>=_memoryPages.Length) { SwitchTxtToShow(functionName,"\r\n内存已满,选择"+functionName+"算法进行页面调度和置换"); //选择一页换出,置换算法 switch(functionName) { case"Optimal": Optimal(invokePage); break; case"FIFO": FIFO(invokePage); break; case"LRU": List LRU(invokePage,pn); break; } } else { SwitchTxtToShow(functionName,"\r\n内存未满,将该页调入内存"); for(intm=0;m<_memoryPages.Length;m++) { if(_memoryPages[m]==null) { _isMemoryFull++; _memoryPages[m]=newPageTableEntry{PageNumber=item.PageNumber,BlockNumber=item.BlockNumber}; break; } } //将该页调入内存后,调用的页表减一 if(invokePage! =null) { //操作invokePage-1,因为在foreach中如果循环的是invokePage本体,则在这里修改了invokePage的值之后,下一次循环无法调用,会出现异常,所以定义了一个copyInvokePage副本专门用来循环 invokePage.Remove(item); SwitchTxtToShow(functionName,"\r\n当前内存页面为: "); ShowMemory(functionName); } break; } } else { SwitchTxtToShow(functionName,"\r\n该调度页面不在快表中,查询页表"); //访问页表 for(intp=0;p<_pageTable.Length;p++) { if(item.PageNumber==_pageTable[p].PageNumber) { //页在内存? if(_pageTable[p].IsInMemory) { SwitchTxtToShow(functionName,"\r\n修改快表"); //修改块表 fastTable.RemoveAt(fastTable.Count-1); fastTable.Add(newFastTable { PageNumber=_pageTable[p].PageNumber, BlockNumber=_pageTable[p].BlockNumber }); //修改访问位和修改位 item.IsModified=false; item.VisitTimes+=1; //判断内存是否满 if(_isMemoryFull>=_memoryPages.Length) { SwitchTxtToShow(functionName,"\r\n内存已满,选择"+functionName+"算法进行页面调度和置换"); //选择一页换出,置换算法 switch(functionName) { case"Optimal": Optimal(invokePage); break; case"FIFO": FIFO(invokePage); break; case"LRU": List LRU(invokePage,pn); break; } } else { SwitchTxtToShow(functionName,"\r\n内存未满,将该页调入内存"); for(intm=0;m<_memoryPages.Length;m++) { if(_memoryPages[m]==null) { _isMemoryFull++; _memoryPages[m]=newPageTableEntry{PageNumber=item.PageNumber,BlockNumber=item.BlockNumber}; break; } } //调用的页表减一 if(invokePage! =null) { invokePage.Remove(item); SwitchTxtToShow(functionName,"\r\n当前内存页为: "); ShowMemory(functionName); } } } //页不在内存中,产生缺页中断,请求调页 else { SwitchTxtToShow(functionName,"\r\n该页不在内存中,产生缺页中断,请求调页"); //在外存中找到缺页 PageTableEntryp1=_pageTable[p]; //内存满否? if(_isMemoryFull>=_memoryPages.Length) { SwitchTxtToShow(functionName,"\r\n内存已满,选择"+functionName+"算法进行页面调度和置换"); //选择一页换出,置换算法 switch(functionName) { case"Optimal": Optimal(invokePage); break; case"FIFO": FIFO(invokePage); break; case"LRU": List LRU(invokePage,pn); break; } } else { //换入内存,修改页表 p1.IsInMemory=true; _pageTable[p]=p1; if(_isMemoryFull>=_memoryPages.Length) { SwitchTxtToShow(functionName,"\r\n内存已满,选择"+functionName+"算法进行页面调度和置换"); //选择一页换出,置换算法 switch(functionName) { case"Optimal": Optimal(invokePage); break; case"FIFO": FIFO(invokePage); break; case"LRU": List LRU(invokePage,pn); break; } } else { SwitchTxtToShow(functionName,"\r\n内存未满,调入该页,当前内存页面为: "); for(intm=0;m<_memoryPages.Length;m++) { if(_memoryPages[m]==null) { _isMemoryFull++; _memoryPages[m]=p1; break; } } //调用的页表减一 if(invokePage! =null) { invokePage.Remove(item); ShowMemory(functionName); } } } } break; } } break; } } } } } (3)测试先进先出算法FIFO,并计算缺页率,参考代码如下: privatevoidFIFO(List { //标志位,只要这个算法有被执行,mark自增一次 _mark++; //内存页面的下标,从0开始,从第一个开始替换 intmemoryNumber=0; //统计当前调用页面和内存中各个页面的不相等数 intunEquar=0; //开始循环调用页面列表 for(inti=0;i { txtFIFOShow.Text+="\r\n调入页面"+invokePageFifo[i].PageNumber.ToString(); //循环判断内存总的页面和该调用页面是否相等 foreach(varitemin_memoryPages) { if(item.PageNumber! =invokePageFifo[i].PageNumber) { unEquar++; } } //只要内存中有一个页面和该调用页面不相等 if(unEquar>=_minBlockNumber) { //进行页面置换 invokePageFifo[i].IsInMemory=true; _memoryPages[memoryNumber]=invokePageFifo[i]; //内存下标自增,表示下一次将要置换的页面的下标 memoryNumber++; if(memoryNumber>=_minBlockNumber) { memoryNumber=0; } //统计的变量自增 _replaceTimes++; _lacePageNumber++; //显示当前内存信息 txtFIFOShow.Text+="\r\n当前内存页面为: "; ShowMemory("FIFO"); } else { txtFIFOShow.Text+="\r\n当前内存页面为: "; ShowMemory("FIFO"); } unEquar=0; } txtFIFOShow.Text+="\r\n调度结束"; //将一些数据恢复默认 _lacePageChance=_lacePageNumber/20.00; _isMemoryFull=0; _pageNumbers=newint[20]{7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}; ShowResult("FIFO"); } (4)测试最佳置换算法Optimal,参考代码如下: privatevoidOptimal(List { _mark++; intunEquar=0; //记录内存中页面在页号数组中出现的最大的下标,也就是该下标就是调用页表中最晚才会被用到的页面,是要替换出去的页面 //该集合中存储的是未被调用的页面号,已经被调用的页面号不作存储 varnumbers=newList //初始化页号数组 for(inti=0;i { numbers.Add(invokePageOptimal[i].PageNumber); } //循环置换页面 for(inti=0;i { intlocation=0; //记录某个内存页面和页号数组对比时的不相等数 intisFullError=0; //当某个内存页面不存在页号数组中时,记录该内存页面的下标 intfullErrorLocation=0; txtOptimalShow.Text+="\r\n调入页面"+invokePageOptimal[i].PageNumber.ToString(); foreach(varitemin_memoryPages) { if(item.PageNumber! =invokePageOptimal[i].PageNumber) { unEquar++; } } //如果内存中的页面和调用的页面号都不相等,则进行页面置换 if(unEquar>=_minBlockNumber) { //循环页号数组,判断内存中的页面号是否和页号数组中的页号是否相等 for(inta=0;a<_memoryPages.Length;a++) { //循环内存中的页面,页号数组和内存页面的页面号作对比 for(intn=0;n { //如果内存中页面号等于页号数组则记录下该页号的下标,并与上一个页号下标作比较,将比较大的值存入location if(_memoryPages[a].PageNumber==numbers[n]) { if(n>=location) { location=n; } break; } //如果内存中的该页面在页号数组中没有找到,isFullError自增 else { isFullError++; } //当isFullError大于或者等于页号数组的数量时,说明该内存页面在页号数组中不存在,记录该内存页面的下标,准备将其置换出 if(isFullError>=numbers.Count) { fullErrorLocation=a; break; } } if(isFullError>=numbers.Count) { break; } else { isFullError=0; } } //location表示内存页面中,谁在调用页表中最靠后的位置的下标 //拿到内存中要置换出去的页面号 if(isFullError>=numbers.Count) { _memoryPages[fullErrorLocation]=invokePageOptimal[i]; _replaceTimes++; _lacePageNumber++; txtOptimalShow.Text+="\r\n当前内存页面为: "; ShowMemory("Optimal"); } else { intpageNum=numbers[location]; //将该内存页面换出 txtOptimalShow.Text+="\r\n当前内存页面为: "; for(intp=0;p<_memoryPages.Length;p++) { if(_memoryPages[p].PageNumber==pageNum) { _memoryPages[p]=invokePageOptimal[i]; _replaceTimes++; _lacePageNumber++; break; } } ShowMemory("Optimal"); } //将已经调用完的页面号从页号数组中移除 numbers.RemoveAt(0); } //跳出本循环,将页号列表的第一个数移除 else { txtOptimalShow.Text+="\r\n当前内存页面为: "; ShowMemory("Optimal"); numbers.RemoveAt(0); } unEquar=0; } txtOptimalShow.Text+="\r\n调度结束"; _lacePageChance=_lacePageNumber/20.00; _isMemoryFull=0; _pageNumbers=newint[20]{7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}; ShowResult("Optimal"); } (5)测试最近最久未使用算法LRU,参考代码如下: priv
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 请求 分页 存储 管理