请求分页式存储管理课程设计java

实验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[]，只需往前看要执行的页流，记录下第一个遇到的该页即可。

实验6请求分页存储管理实验6:请求分页存储管理1。

实验的目的是深入理解请求分页存储管理的基本概念和实现方法，重点是地址转换、分页、替换算法等的实现思路。

2.实验属性本实验是综合性和设计性的。

3.实验仪器和设备通用PC386或以上微机4。

这个实验需要两个小时才能完成。

该实验需要以下任务:(1)建立相关数据结构:页表、页表寄存器、存储块表等。

(2)指定分配给进程的物理内存块的数量，并设置进程的页面访问顺序；(3)设计页面替换算法，可以选择OPT、FIFO、LRU等。

并计算相应的缺页率来比较它们的优缺点；(4)编写地址转换函数，通过查找页表完成从逻辑地址到物理地址的转换；如果页面丢失，选择一些替换算法(选择，先进先出，LRU等)。

)来完成页面交换；(5)可视化整个过程。

实验前应复习实验涉及的理论知识和算法，根据实验要求完成基本代码编译和预览报告，在实验中认真调试编译好的代码并进行必要的测试，记录和分析实验结果。

实验结束后，认真编写符合标准格式的实验报告(见附件一)，并要求正式的实验报告纸和封面装订整齐，按时提交。

三、设计过程3.1算法原理分析OPT算法是未来最远的，当当前内存中没有页面即将访问时，替换当前页面在未来访问页面中最远的页面或者永远不出现。

先进先出算法是先进先出。

当当前内存中没有要访问的页面时，将替换最高级的页面。

LRU算法是最近最长的未使用页面。

当当前存储器中没有将要被访问的页面时，当前页面中最近且最长时间未被使用的页面被替换。

3.2数据定义int长度、num_page、计数、种子；//长度记录访问字符串的长度，页数，计算[20] [30]，[30]，[10]中丢失的页数；//result记录结果，order存储访问字符串，a存储当前页中的值int pos1、flag1、flag2、flag3//pos1位置变量、标志1等。

标志变量是字符结果1[30]；//记录缺失的页面数组void opt() //best void fifo() //先进先出bool search(int n) //找出当前内存中是否已经存在页面3.3流程图和操作截图，执行的指令是否启动，指令是否首先存储在内存中，指令是否被删除，是否有任何指令结束以获得命中率图6.1 FIFO()函数流程图；开始在内存中输入分发页的数据时，第一个访问页初始化第一列值并请求访问页？内存中是否已经存在前一列的直接副本？内存中有空闲页面吗？直接插入到替换内存中，输出所有将来不会发生或离当前页面最远的页面更改。

操作系统课程设计题目: 通用请求分页调度算法程序院系：计算机科学与技术系专业班级：09 软件工程学号：学生姓名：指导教师：2011 年12 月 12 日目录1 课程设计目的 (1)2 课程设计内容 (1)3 系统分析与设计 (2)3.1 系统分析： (2)3.2 系统设计： (2)3.3 模块设计： (3)3.4 数据结构说明： (4)3.5 算法流程图： (4)4 模块调试与系统测试 (29)4.1 模块调试： (29)4.2 系统测试： (30)4.3 调试分析： (30)5 用户手册 (31)6 体会与自我评价 (32)7 参考文献 (33)通用请求分页调度算法程序1 课程设计目的操作系统是管理计算机硬件的软件。

它也为应用程序提供一个基础，在计算机用户与计算机硬件之间扮演一个中间者的角色。

在完成操作系统各部分实验的基础上，对操作系统的整体进行一个模拟，通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之间的联系，最后达到对完整系统的理解。

本课程设计的目的综合应用学生所学知识，建立系统和完整的计算机系统概念，理解和巩固操作系统基本理论、原理和方法，掌握多道程序设计基本技能。

研究计算机操作系统的基本原理和算法，掌握操作系统的进程管理、存储管理、文件管理和设备管理的基本原理与主要算法。

目的是使学生掌握常用操作系统的一般管理方法，了解它是如何组织和运作的，对操作系统的核心概念和算法有一个透彻的理解，并对系统运行的机制有一个全面的掌握，从而充分理解系统调用与程序设计之间的关系。

由于本课程设计比较复杂，因此也锻炼了同学们在编程方面的能力和解决实际问题的能力，在软件开发方面，也提高了创新的能力；由于在设计的同时必须查阅大量的资料和书籍，所以也锻炼的调查研究查阅技术文献以及编写软件设计文档的能力。

2 课程设计内容在进程运行过程中，当所要访问的页面不在内存时，则应将它调入内存。

假如在此时内存已无空闲空间，则应选择一页调出。

简述请求分页存储管理方式请求分页存储管理方式是一种非常实用的存储管理方式，它可以将大量数据分成多页存储，从而增加系统的可扩展性和可维护性。

本文将分步骤阐述请求分页存储管理方式的实现过程。

1. 设计数据库表结构首先，我们需要设计出适合分页存储的数据库表结构。

通常，我们需要将数据表按照某种规则分成多个页面，每个页面中包含相同数量的数据。

例如，如果需要将1000条数据分成10页，那么每个页面应该包含100条数据。

2. 编写查询语句在设计好数据库结构之后，我们需要编写查询语句来查询数据并将其分页。

我们可以使用LIMIT关键字来限制查询结果的数量，并使用OFFSET关键字来指定从哪个位置开始查询。

例如，如果需要查询第2页的数据，那么我们可以使用以下SQL语句：SELECT * FROM table_name LIMIT 100 OFFSET 100;这将返回第101到第200条数据。

3. 编写分页控件分页控件是实现分页存储的重要组成部分。

它通常包含一个页面选择器和一个数据显示区域。

我们可以使用JavaScript和CSS来创建翻页效果和样式。

例如，我们可以使用以下代码创建一个简单的页面选择器：```<div class="pagination"><a href="#">1</a><a href="#">2</a><a href="#">3</a><a href="#">4</a><a href="#">5</a></div>```4. 实现异步加载异步加载是将页面动态加载到用户界面中的一种技术。

它可以大大提高页面加载速度和用户体验。

我们可以使用AJAX等技术来实现异步加载。

实验四请求分页存储管理模拟实验一：实验目得通过对页面、页表、地址转换与页面置换过程得模拟,加深对请求分页存储管理系统得原理与实现技术得理解.二：实验内容假设每个页面可以存放１0条指令，分配给进程得存储块数为４。

用C语言或Ｐａscａｌ语言模拟一进程得执行过程。

设该进程共有320条指令，地址空间为32个页面,运行前所有页面均没有调入内存。

模拟运行时,如果所访问得指令已经在内存,则显示其物理地址,并转下一条指令;如果所访问得指令还未装入内存，则发生缺页，此时需要记录缺页产生次数，并将相应页面调入内存，如果４个内存块已满，则需要进行页面置换。

最后显示其物理地址,并转下一条指令。

在所有指令执行完毕后,显示进程运行过程中得缺页次数与缺页率.页面置换算法：分别采用OPT、ＦIFＯ、LRＵ三种算法。

进程中得指令访问次序按如下原则生成：50%得指令就是顺序执行得。

2５%得指令就是均匀分布在低地址部分.25％得指令就是均匀分布在高地址部分.三：实验类别分页存储管理四:实验类型模拟实验五：主要仪器计算机六：结果OＰＴ:ＬRU：FIFO：七：程序＃ i ｎclude 〈stdio 、h 〉＃ ｉncl ｕde 〈ｓtdlib 、h 〉＃ include 〈ｃｏnio 、ｈ＞＃ def ｉne blockn ｕm ４//页面尺寸大小int ｍ; //程序计数器，用来记录按次序执行得指令对应得页号s ｔa ｔi ｃ in ｔ ｎum ［３20]； //用来存储3２0条指令ｔｙpedef s ｔruct BLOCK ／/声明一种新类型—－物理块类型{ﻩint ｐagenum; ／/页号ﻩint ａｃces ｓｅd; ／/访问量，其值表示多久未被访问}BLOCK ；BLOCK bl ｏck ［bl ｏcknum ］； ／/定义一大小为8得物理块数组void init （） /／程序初始化函数，对bl ｏck 初始化｛for （ｉnt i=0;i ＜ｂlo ｃknum;i+＋)bｌｏｃｋ[ｉ]、ｐａgｅnum＝—1；bｌock［ｉ］、accｅsｓed=0；ﻩm=0;｝｝ｉｎt ｐａｇｅＥxist（ｉnt curpagｅ)/／查找物理块中页面就是否存在，寻找该页面curpage就是否在内存块bｌoｃｋ中,若在，返回块号｛ﻩfor（int i=0；i<bｌocknum; i+＋)ﻩ{ﻩﻩｉf(bｌock［i］、ｐagｅnｕm ＝＝ cuｒpaｇe ）ﻩﻩｒeturn i； //在内存块blｏck中,返回块号ﻩ｝ｒetuｒn -1;}ｉnｔ findSpace（）／/查找就是否有空闲物理块，寻找空闲块bｌock，返回其块号｛foｒ(int ｉ=0；ｉ<bｌocknｕm;i＋+)ﻩ｛ｉf（blｏｃｋ[i］、paｇenum=＝－1)ﻩｒeｔuｒn i；／／找到了空闲得ｂlｏcｋ,返回块号｝ﻩrｅｔurｎ -1；｝int findReplａcｅ(）//查找应予置换得页面{ﻩint ｐoｓ = 0;ﻩｆor（int i＝0；i〈ｂlocｋnｕm；ｉ++){if(blｏｃk［ｉ]、ａｃcessed 〉blｏck［pos]、aｃceｓsｅd）ﻩpos = ｉ； //找到应该置换页面，返回BＬOCK中位置ﻩ｝reｔurn pｏs；｝voｉd displaｙ(）//显示物理块中得页面号｛ﻩﻩfor(int i=0; i〈bｌocknｕm; i＋＋）ﻩ｛ﻩif(blocｋ[ｉ］、ｐａｇenum != -1）ﻩ｛ﻩﻩpriｎtf（” ％02d "，block［ｉ]、paｇenum）;ﻩﻩﻩprintf("%p |”，＆blocｋ[ｉ]、pagｅnum）；ﻩﻩ｝ｐrｉｎtf（"\n＂）;｝vｏid rａｎdaｍ（)/／产生320条随机数,显示并存储到ｎｕm[３２0]｛int ｆlａｇ=0;pｒintｆ（”请为一进程输入起始执行指令得序号(0~320）:\n”)；ﻩscanｆ（"%d",＆ｍ）；//用户决定得起始执行指令ｐriｎｔｆ（"*＊＊**＊进程中指令访问次序如下：(由随机数产生)＊*＊*＊＊＊＼n"）;fｏr（int i=0；i〈３2０；ｉ＋+）｛/／进程中得320条指令访问次序得生成ﻩﻩnum[ｉ]＝m;//当前执行得指令数，ﻩﻩｉf（flag％２==0）ﻩm＝++m％３２０；//顺序执行下一条指令ﻩﻩｉf（flag==１）ﻩﻩm＝rａnd（）％（m-1)；//通过随机数,跳转到低地址部分[0，m—1］得一条指令处，设其序号为ｍ1ｉf(flag＝=3）ﻩﻩm=m+1＋(rand()%(３2０－（m+1）)）；//通过随机数,跳转到高地址部分［ｍ1+2，3１９]得一条指令处，设其序号为m2ﻩﻩfｌag＝＋+ｆｌag%４；ﻩprｉntｆ（” %0３d”,num［i］)；／/输出格式:3位数ﻩﻩiｆ（（i+１）%1０==0）／/控制换行，每个页面可以存放１０条指令,共32个页面ﻩprintf（”\n”）；｝｝ｖoid pageｓtrｉng（) //显示调用得页面序列,求出此进程按次序执行得各指令所在得页面号并显示输出｛ｆor（int i＝0;i〈３２0；i++）ﻩ｛printf(”％０２d＂,nuｍ[i］／１0);//输出格式：２位数if((ｉ＋1）%10==0)//控制换行，每个页面可以存放10条指令,共32个页面ﻩﻩｐｒintf("＼n”);}｝void OPＴ() //最佳替换算法{ﻩinｔ n=0；//记录缺页次数inｔ exist，space，posiｔｉon；ﻩinｔｃurpaｇe;//当前指令得页面号ﻩfｏr(int i＝０;i＜３2０；ｉ＋＋）ﻩ｛ﻩm=num［i］;ﻩcurpage=ｍ/10;ﻩﻩeｘiｓt=ｐageExist（cuｒｐage);ﻩif(exist==-1)ﻩﻩ{ ／/当前指令得页面号不在物理块中space＝findＳpace（）；ﻩﻩif(sｐａｃe ！= -１）ﻩﻩ｛//当前存在空闲得物理块ﻩﻩｂloｃk［ｓｐａce]、pagenuｍ＝ cｕｒpaｇe；/／将此页面调入内存ﻩﻩﻩdiｓｐlay（）;／/显示物理块中得页面号ﻩﻩn++;/／缺页次数+1ﻩ｝ﻩﻩelｓeﻩﻩ{ ／/当前不存在空闲得物理块，需要进行页面置换foｒ（inｔk=0；k＜blocknum；k++）ﻩﻩﻩﻩ{ｆor（int j=i；ｊ〈３２０；j＋+）ﻩ{//找到在最长(未来)时间内不再被访问得页面ﻩﻩﻩﻩif(block［k］、pagenum！= ｎｕｍ［j]/1０）ﻩﻩﻩ{ﻩﻩbloｃk［ｋ］、acｃeｓseｄ = 1０00;ﻩﻩﻩ} //将来不会被访问,设置为一个很大数ﻩﻩﻩelseﻩﻩﻩ{ //将来会被访问,访问量设为ｊﻩﻩﻩｂlｏcｋ[ｋ］、ａｃｃessｅd = j；ﻩﻩﻩﻩﻩbｒeak;ﻩﻩﻩﻩ｝ﻩﻩﻩ}ﻩ}ﻩposiｔｉon = ｆiｎdReｐlａｃe（）；//找到被置换得页面，淘汰ﻩblock［ｐosｉtｉon］、pａgenum = ｃurpａｇｅ；// 将新页面调入dispｌay();ﻩﻩn++； //缺页次数+１ﻩ｝｝ﻩ｝ﻩpｒintf(”缺页次数：％ｄ\n＂,n);printｆ(＂缺页率：％f％％＼n"，（n／320、0）＊100）；}void LＲU() //最近最久未使用算法{inｔ n=0；//记录缺页次数ﻩiｎt ｅxｉｓt,ｓｐacｅ，ｐosition ;ﻩｉnｔ curpaｇe；／/当前指令得页面号ﻩｆｏｒ（ｉｎt i=0；i＜320;i++）ﻩ{ﻩm＝num［i]；ﻩﻩcuｒｐagｅ=m／10；ﻩｅxist = pageＥｘiｓt(curpａge);ﻩｉｆ（ｅxist＝=-1）ﻩﻩ｛ //当前指令得页面号不在物理块中ｓｐaｃe = fｉnｄSpace（）;ﻩﻩif（sｐａcｅ！= —１)ﻩ{ //当前存在空闲得物理块ﻩﻩｂｌock［spａce]、pagenum = ｃｕrｐage；//将此页面调入内存ﻩﻩｄisplay（）；//显示物理块中得页面号ﻩn++;／／缺页次数+1ﻩﻩ｝else｛ //当前不存在空闲得物理块，需要进行页面置换ﻩﻩpｏsｉｔioｎ＝ finｄＲeｐlace(）；ﻩbｌocｋ[positｉon]、paｇenum ＝ cｕrｐａge；ﻩﻩdiｓplaｙ(）;ﻩn++；//缺页次数+1ﻩ｝ﻩﻩ}elsｅﻩﻩbｌｏck［exｉsｔ］、acｃesｓed = -１；//恢复存在得并刚访问过得ＢLOCK中页面ａccessｅｄ为-１for(int j=0; j<blockｎum； j＋+)ﻩﻩ｛//其余得accessed++ﻩﻩｂlｏｃk［ｊ］、acｃｅssed+＋;｝ﻩ}prｉntf("缺页次数:%d\n”,n）；ﻩpriｎｔf("缺页率：％f%％\n",（n／３20、0）*10０);｝voｉd FIFO（）{int n=0;//记录缺页次数int eｘist，spacｅ，ｐositｉｏn ;ﻩ iｎｔ cｕrｐaｇe；/／当前指令得页面号iｎt blｏckpｏinter=－１;for（iｎｔ i=０;i<３20；ｉ++）ﻩ｛ﻩ m=num［i］;cｕrpａge=m／１0；ﻩexｉst = pageＥｘist(ｃｕrpａge）；ﻩ iｆ(eｘiｓｔ＝=－１）｛／/当前指令得页面号不在物理块中ﻩ spaｃe = fｉｎdＳpaｃe（);ﻩﻩif（space ！＝-1)ﻩ { ／/当前存在空闲得物理块ﻩﻩ blocｋpoiｎter＋+;ﻩﻩﻩｂlock［spａcｅ]、ｐａｇｅnｕm=curpagｅ; /／将此页面调入内存ﻩ n++;//缺页次数＋1ﻩﻩﻩ diｓｐlay(）;//显示物理块中得页面号ﻩ｝ﻩ elseﻩ { /／没有空闲物理块,进行置换ﻩﻩﻩﻩpｏsitｉon = （++blockpｏintｅr）％4;ﻩ block[positｉon]、ｐaｇｅnum ＝ cuｒｐａge；／/将此页面调入内存ﻩﻩn＋+；ﻩﻩ disｐｌay（）；ﻩ｝ﻩ }｝ｐrｉｎtf(＂缺页次数:％d＼n＂,n）;printf（＂缺页率:%ｆ%%\n",(n/3２0、0)*100）；}void ｍain(）{ﻩint choice;ﻩpriｎtf（"＊＊＊＊*＊＊*＊*＊＊请求分页存储管理模拟系统*＊＊*＊＊＊＊＊＊*＊*\n")；ﻩrandａm（);ｐｒintf(＂＊＊*＊*＊＊*****此进程得页面调用序列如下***＊＊＊＊*＊＊＊**＊\n”）;pageｓtriｎｇ（）;ﻩwｈilｅ（choicｅ！= ４)｛ﻩﻩprinｔf(＂****＊*＊＊1:OPT ２：LRU 3:ＦＩFO 4：退出＊＊*＊＊＊***\n”）;ﻩprintf（"请选择一种页面置换算法:”）;ﻩｓｃａnf("%d＂,＆cｈoｉcｅ）；ﻩiｎit();ﻩswitch（choiｃe)ﻩ｛ﻩcａｓe 1:ﻩﻩﻩｐｒintf(”最佳置换算法OPT：\n")；ﻩpｒintf("页面号物理地址页面号物理地址页面号物理地址页面号物理地址＼n"）;ﻩﻩﻩOPＴ（）；ﻩbreak；ﻩcａse 2：ﻩﻩｐrinｔf("最近最久未使用置换算法LRＵ:\n"）；ﻩｐrｉntf("页面号物理地址页面号物理地址页面号物理地址页面号物理地址＼n＂）;ﻩＬRU()；ﻩﻩﻩｂreaｋ；ﻩﻩcaｓe 3：ﻩprintf("先进先出置换算法FＩＦＯ：\n＂）；ﻩpｒiｎｔf（＂页面号物理地址页面号物理地址页面号物理地址页面号物理地址\ｎ＂);ＦIFO(）；ﻩﻩbreａk;ﻩ｝}}。

请求页式存储管理方案设计说明书一：实验题目：设计一个请求页式存储管理方案，为简单起见。

页面淘汰算法采用FIFO页面淘汰算法，并且在淘汰一页时，只将该页在页表中修改状态位。

而不再判断它是否被改写过，也不将它写回到辅存。

[基本要求]页面尺寸1K，输入进程大小（例如5300bytes），对页表进行初始化, 页表结构：系统为进程分配3 个物理块（页框），块号分别为0、1、2，页框管理表（空闲块表）：任意输入一个需要访问的指令地址流（例如：3635、3642、1140、0087、1700、5200、4355，输入负数结束），打印页表情况。

每访问一个地址时，首先要计算该地址所在的页的页号，然后查页表，判断该页是否在主存——如果该页已在主存，则打印页表情况；如果该页不在主存且页框未满（查空闲块表，找到空闲块），则调入该页并修改页表，打印页表情况；如果该页不在主存且页框已满，则按FIFO页面淘汰算法淘汰一页后调入所需的页，修改页表，打印页表情况；二：实验题目与要求：1.实验题目：请求页式存储管理方案。

2.要求：实现请求页式的管理，再淘汰一页时，只修改该页在页表中的状态位，不再判断它是否被改写过。

2.功能模块四：模块功能介绍1．页表初始化：根据输入的进程大小初始化页表。

初始化的内容包括：计算页表长度，将状态位置零，物理块号置零。

2．地址链表建立：将输入的地址流以链表的形式存储，3．页面调用：从地址链表的头指针开始调页。

调页包括：首先计算所调页面的页号，对于不在内存中的页面使用请求调页策略。

4。

页面置换：对于不在内存中的页面采用先进先出策略进行置换，置换包括：改变页表的状态位，换入请求页面，换出最早调入的页面。

五：主要模块代码：import java.util.*;public class Memory{static int h=0;static int n=0;//主程序public static void main(String[] args){//创建页表int presize=Integer.parseInt(args[0]);//获得进程的大小int j;int lengh=presize/1024+1;//页号int leaf[]=new int[lengh];for(int x=0;x<lengh;x++){leaf[x]=x;}//块号int block[]=new int[lengh];for(int x=0;x<lengh;x++){block[x]=-1;}//标志位int flag[]=new int[lengh];for(int x=0;x<lengh;x++){flag[x]=0;}int a[]=new int[3];for(int x=0;x<3;x++){a[x]=0;}//块信息int d[]=new int[3];for(int x=0;x<3;x++){d[x]=x;}System.out.println("页表长："+lengh);System.out.println("请输入指令地址流：");for(int k=1;k<lengh;k++){int i=Integer.parseInt(args[k]);//获得地址的大小System.out.print("指令地址:"+i);System.out.println("");if(i<0){System.exit(0);}if(i>presize){System.out.println("地址超出范围!");}else{j=i/1024;if(n<3){block[j]=h;flag[j]=1;a[h]=j;h++;System.out.println("页信息：");System.out.println("页号"+"块号"+"标志");for(int m=0;m<lengh;m++){System.out.println(leaf[m]+" "+block[m]+""+flag[m]+" ");}System.out.println("块信息：");System.out.println("块号"+"进程");for(int m=0;m<3;m++){System.out.println(d[m]+" "+a[m]+" ");}}else{n=0;int y=a[n];a[n]=j;block[y]=-1;flag[j]=0;n++;System.out.println("页信息：");System.out.println("页号"+"块号"+"标志");for(int m=0;m<lengh;m++){System.out.println(leaf[m]+" "+block[m]+" "+flag[m]+" ");}System.out.println("块信息：");System.out.println("块号"+"进程");for(int m=0;m<3;m++){System.out.println(d[m]+" "+a[m]+" ");}}}}}。

实验八请求分页存储管理设计一、虚拟存储器的相关知识：1.概述：虚拟存储器(Virtual Memory)：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”。

虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。

作用：虚拟内存的作用内存在计算机中的作用很大，电脑中所有运行的程序都需要经过内存来执行，如果执行的程序很大或很多，就会导致内存消耗殆尽。

为了解决这个问题，Windows中运用了虚拟内存技术，即拿出一部分硬盘空间来充当内存使用，当内存占用完时，电脑就会自动调用硬盘来充当内存，以缓解内存的紧张。

举一个例子来说，如果电脑只有128MB物理内存的话，当读取一个容量为200MB的文件时，就必须要用到比较大的虚拟内存，文件被内存读取之后就会先储存到虚拟内存，等待内存把文件全部储存到虚拟内存之后，跟着就会把虚拟内存里储存的文件释放到原来的安装目录里了。

下面，就让我们一起来看看如何对虚拟内存进行设置吧。

2.请求分页虚拟存储系统是将作业信息的副本存放在磁盘这一类辅助存储器中，当作业被调度投入运行时，并不把作业的程序和数据全部装入主存，而仅仅装入立即使用的那些页面，至少要将作业的第一页信息装入主存，在执行过程中访问到不在主存的页面时，再把它们动态地装入。

用得较多的分页式虚拟存储管理是请求分页（demand paging），当需要执行某条指令或使用某个数据，而发现它们并不在主存时，产生一个缺页中断，系统从辅存中把该指令或数据所在的页面调入内存。

3.替换算法：替换规则用来确定替换主存中哪一部分，以便腾空部分主存，存放来自辅存要调入的那部分内容。

常见的替换算法有4种。

随机算法用软件或硬件随机数产生器确定替换的页面。

先进先出先调入主存的页面先替换。

近期最少使用算法替换最长时间不用的页面。

最优算法替换最长时间以后才使用的页面。

哈尔滨工业大学计算机科学与技术学院课程设计报告（2012 ~2013 学年度秋季学期）课程名称操作系统课程设计项目名称姓名学号专业班级地点教师设计四：1.设计目的请求页式管理是一种常用的虚拟存储管理技术。

本设计通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。

2.设计内容：通过随机数产生一个指令序列，共320条指令。

指令的地址按下述原则生成：① 50% 的指令是顺序执行的；② 25% 的指令是均匀分布在前地址部分；③ 25% 的指令是均匀分布在后地址部分。

具体的实施方法是：①在 [0,319] 的指令地址之间随机选取一起点 m；②顺序执行一条指令；③在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为 m′；④顺序执行一条指令，其地址为 m′+1；⑤在后地址 [m′+2,319] 中随机选取一条指令并执行；⑥重复上述步骤② ~ ⑤，直到执行 320 次指令。

将指令序列变换成为页地址流设：①页面大小为 1K；②用户内存容量为 4 页到 32 页；③用户虚存容量为 32K 。

在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的存放方式为：第 0 条 ~ 第 9 条指令为第 0 页 ( 对应虚存地址为 [0,9])；第 10 条 ~ 第 19 条指令为第 1 页 ( 对应虚存地址为 [10,19] ) ；┇┇第 310 条 ~ 第 319 条指令为第 31 页 ( 对应虚存地址为 [310,319]) 。

按以上方式，用户指令可组成 32 页。

计算并输出下述各种算法在不同内存容量下的命中率。

先进先出的算法 (FIFO)；最近最少使用算法 (LRR)；最少访问页面算法 (LFR)；最近最不经常使用算法 (NUR)。

3．实验环境每个学生一台微机，需要安装windows98或windows2000操作系统，配备VC、VB、java或C编程语言，每个学生上机时间不少于24个小时。

一、目的与要求1、目的近年来，由于大规模集成电路（LSI ）和超大规模集成电路（VLSI ）技术的发展，使存储器的容量不断扩大，价格大幅度下降。

但从使用角度看，存储器的容量和成本总受到一定的限制。

所以，提高存储器的效率始终是操作系统研究的重要课题之一。

虚拟存储技术是用来扩大内存容量的一种重要方法。

学生应独立地用高级语言编写几个常用的存储分配算法，并设计一个存储管理的模拟程序，对各种算法进行分析比较，评测其性能优劣，从而加深对这些算法的了解。

任务三采用最佳淘汰算法(OPT)实现，任务四采用最近最少使用页淘汰算法(LRU)实现。

2、 要求为了比较真实地模拟存储管理，可预先生成一个大致符合实际情况的指令地址流。

然后模拟这样一种指令序列的执行来计算和分析各种算法的访问命中率。

二、示例1、题目 本示例是采用页式分配存储管理方案，并通过分析计算不同页面淘汰算法情况下的访问命中率来比较各种算法的优劣。

另外也考虑到改变页面大小和实际存储器容量对计算结果的影响，从而可为算则好的算法、合适的页面尺寸和实存容量提供依据。

本程序是按下述原则生成指令序列的：（1） 50%的指令是顺序执行的。

（2） 25%的指令均匀散布在前地址部分。

（3） 25%的指令均匀散布在后地址部分。

示例中选用最佳淘汰算法（OPT ）和最近最少使用页面淘汰算法（LRU ）计算页面命中率。

公式为页地址流长度页面失效次数命中率-=1 假定虚存容量为32K ，页面尺寸从1K 至8K ，实存容量从4页至32页。

2、 算法与框图（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 位置变量，flagl 等为标志变量char result1[30]; // 记录缺页数组void opt() //最佳void fifo() //先进先出bool search(i nt n) 〃查找当前内存中是否已存在该页3.3流程图与运行截图图6.1 FIFO ()函数流程图替换内存中将来不岀现或离当前最 图22 OPT 算法流程图 1 5 7 8 4 5 41 2 直1 机& 随B 内5 !£」八-?--- 3 丄度产串- 匸番问数 剽的控访个 馬早随面页6 圣5 邸入入生入示四、小结本次课程设计目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

存储器管理1．实验内容：模拟请求页式存储管理中硬件的地址转换和缺页中断,并用先进先出调度算法〔FIFO处理缺页中断；2．要求：①指令序列的设定可以执行拟定,格式如表3；②在完成了FIFO换页策略后,可以选做LRU的换页策略,并进行比较；③作业允许的页架数m在不同情况下的缺页中断率；④程序运行时显示地址转变和页面调入调出过程。

3.实验控制流图：4．数据结构核心代码：package xiao.zhang.bean;publicclass Instruction {/*** 指令操作符号*/private String op;/*** 页号*/privateint pageId;/*** 页内地址*/privateint pageInAddress;public Instruction<> {}public Instruction<String op, int pageId, int pageInAddress> { this.op = op;this.pageId = pageId;this.pageInAddress = pageInAddress;}public String getOp<> {return op;}publicvoid setOp<String op> {this.op = op;}publicint getPageId<> {return pageId;}publicvoid setPageId<int pageId> {this.pageId = pageId;}publicint getPageInAddress<> {return pageInAddress;}publicvoid setPageInAddress<int pageInAddress> {this.pageInAddress = pageInAddress;}/** <non-Javadoc>** @see ng.Object#toString<>*/@Overridepublic String toString<> {return"Instruction [op=" + this.op + ", pageId=" + this.pageId + ", pageInAddress=" + this.pageInAddress + ", getOp<>="+ this.getOp<> + ", getPageId<>=" +this.getPageId<>+ ", getPageInAddress<>=" +this.getPageInAddress<>+ ", getClass<>=" + this.getClass<> + ", hashCode<>="+ this.hashCode<> + ", toString<>=" +super.toString<> + "]";}}package xiao.zhang.bean;import java.util.LinkedList; publicclass ExecuteFiFo {/*** 指令队列*/public LinkedList<Instruction> is; /*** 页面存储*/public LinkedList<Page> pages;/*** 是否还有存储页架*/privatefinalint isUseablePageFrame; publicstaticint point = 0;/*** 默认设置页架为4个*/public ExecuteFiFo<> {this.isUseablePageFrame = 4;}public ExecuteFiFo<int isUseablePageFrame> {is = new LinkedList<Instruction><>;pages = new LinkedList<Page><>;this.isUseablePageFrame = isUseablePageFrame;}public ExecuteFiFo<LinkedList<Instruction> is, LinkedList<Page> pages,int isUseablePageFrame> {this.is = is;this.pages = pages;this.isUseablePageFrame = isUseablePageFrame;}/*** 一次性调度完成,装载所有的可用的页*/publicvoid initalExecute<> {for <int i = 0; i < isUseablePageFrame; i++> {/*** 从指令队列出一条指令*/Instruction ins = is.poll<>;/*** 访问指定页号的主存*/Page p = pages.get<i>;p.setPageId<ins.getPageId<>>;p.setInMen<true>;p.setModifyFlag<isModify<ins.getOp<>>>;printINInformation<ins>;}}/*** 执行指令*/publicvoid executeInstruction<> {/*** 先判断执行的页是否住存指令序列中将其删除*/while <!is.isEmpty<>> {Instruction ins = is.poll<>;if <isExistMemeroy<ins>> {System.out.println<"[页号为：\t" +ins.getPageId<> + "\t存在]">;Page p = pages.get<ins.getPageId<>>;printOUTInformation<p>;printINInformation<ins>;} else {System.out.println<"[页号为：\t" +ins.getPageId<> + "\t不存在]">;Page p = pages.get<ins.getPageId<>>;p.setInMen<true>;Page outP = pages.get<point % isUseablePageFrame>;p.setPageFrameId<outP.getPageFrameId<>>;p.setModifyFlag<isModify<ins.getOp<>>>;printOUTInformation<outP>;printINInformation<ins>;}point++;}}/*** 判断指定序列是否住存** @return*/publicboolean isExistMemeroy<Instruction ins> {for <int i = 0; i < this.pages.size<>; i++> {if <this.pages.get<i>.getPageId<> == ins.getPageId<>&& this.pages.get<i>.isInMen<>> { returntrue;}}returnfalse;}/*** 打印装载信息** @param ins*/publicvoid printINInformation<Instruction ins> {System.out.println<"[页号：" + ins.getPageId<> + "\tIN\t" + "执行:"+ ins.getOp<> + "操作\t" + "物理地址："+ <1024 * ins.getPageId<> +ins.getPageInAddress<>> + "]">;}/*** 打印调出信息** @param p*/publicvoid printOUTInformation<Page p> {if <p.isModifyFlag<>> {System.out.println<"[页号：" + p.getPageId<> + "\tOUT\t" + "页架号:"+ p.getPageFrameId<> + "\t修改\t" + "写回磁盘："+ p.getLocationInDisk<> + "]">;} else {System.out.println<"[页号：" + p.getPageId<> + "\tOUT\t" + "页架号:"+ p.getPageFrameId<> + "\t未修改\t" + "不用写回磁盘]">;}}/*** 判断指令是否修改主存内容** @param op* @return*/publicboolean isModify<String op> {if <op.equals<"R"> || op.equals<"W">> { returntrue;}returnfalse;}/*** @return the isUseablePageFrame*/publicint getIsUseablePageFrame<> { return isUseablePageFrame;}/*** @return the is*/public LinkedList<Instruction> getIs<> { returnthis.is;}/*** @return the pages*/public LinkedList<Page> getPages<> { returnthis.pages;}/*** @param is* the is to set*/publicvoid setIs<LinkedList<Instruction> is> { this.is = is;}/*** @param pages* the pages to set*/publicvoid setPages<LinkedList<Page> pages> { this.pages = pages;}}package xiao.zhang;import xiao.zhang.bean.ExecuteFiFo;import xiao.zhang.bean.Instruction;import xiao.zhang.bean.Page;publicclass MainExecute { publicstaticvoid main<String[] args> {Instruction[] i = new Instruction[12];i[0] = new Instruction<"+", 0, 70>;i[1] = new Instruction<"-", 1, 50>;i[2] = new Instruction<"*", 2, 15>;i[3] = new Instruction<"R", 3, 21>;i[4] = new Instruction<"W", 0, 56>;i[5] = new Instruction<"-", 6, 40>;i[6] = new Instruction<"RM", 4, 53>;i[7] = new Instruction<"+", 5, 23>;i[8] = new Instruction<"W", 1, 37>;i[9] = new Instruction<"R", 2, 78>;i[10] = new Instruction<"+", 4, 1>;i[11] = new Instruction<"W", 6, 84>;Page[] p = new Page[7];p[0] = new Page<0, true, 5, false, 11>;p[1] = new Page<2, true, 8, false, 12>;p[2] = new Page<3, true, 9, false, 13>;p[3] = new Page<4, true, 1, false, 21>;p[4] = new Page<5, false, 0, false, 22>;p[5] = new Page<6, false, 0, false, 23>;p[6] = new Page<7, false, 0, false, 121>;ExecuteFiFo xf = new ExecuteFiFo<4>; for <int j = 0; j < p.length; j++> {xf.getPages<>.add<p[j]>;}for <int j = 0; j < i.length; j++> {xf.getIs<>.add<i[j]>;}xf.initalExecute<>;xf.executeInstruction<>;}}. 6.程序运行结构截图：14 / 14。

第四讲存储器管理主讲教师：夏辉丽4.7 请求分页存储管理方式4.7.1 请求分页中的硬件支持4.7.2 内存分配策略和分配算法4.7.3 调页策略页号 物理块号 修改位M ：该页在调入内存后是否被修改过 状态位P 访问字段A 修改位M 外存地址 4.7.1 请求分页中的硬件支持1. 页表机制：•基本作用：地址转换•增加页表字段，供程序在换入换出时参考 访问字段A ：记录本页在一段时间内被访问的次数 状态位P ：用于指示该页是否已调入内存外存地址：指示该页在外存上的地址(物理块号)4.7.1 请求分页中的硬件支持2. 缺页中断机构：•缺页中断与其他中断的不同：（1）在指令执行期间产生和处理中断信号（2）一条指令在执行期间可能产生多次缺页中断 页面B ：A ：654321指令copy A TO B3. 4.7.1 请求分页中的硬件支持4.7.2 内存分配策略和分配算法1. 最小物理块数的确定：•保证进程正常运行所需的最小物理块数；•与硬件结构有关，取决于指令的格式、功能和寻址方式。

4.7.2 内存分配策略和分配算法2. 物理块的分配策略：•两种内存分配策略：▪固定分配：为进程分配的物理块数固定不变。

▪可变分配：先为每个进程分配一定数目的物理块，若发生缺页中断，再增加物理块数。

•两种置换策略：▪局部置换：只能将自己的某个内存页换出。

▪全局置换：可将系统中任一进程的内存页换出。

4.7.2 内存分配策略和分配算法2. 物理块的分配策略：•组合出以下三种适用策略：▪（1）固定分配局部置换▪（2）可变分配全局置换▪（3）可变分配局部置换4.7.2 内存分配策略和分配算法3. 物理块分配算法：•（1）平均分配算法•（2）按比例分配算法：根据进程大小按比例分配（m:物理块总数，S:各进程页面总数）•（3）考虑优先权的分配算法：一部分按比例分配；另一部分为优先权高的进程增加分配份额4.7.3 调页策略1. 调入页面的时机：•预调页策略：进程首次调入内存时，由程序员指出应该先调入哪些页。