操作系统常用页面置换算法课程设计
摘要
在lｉnｕｘ中,为了提高内存利用率,提供了内外存进程对换机制,内存空间的分配和回收均以页为单位进行，一个进程只需要将其一部分调入内存便可运行；当操作系统发生缺页中断时，必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。因而引入一种用来选择淘汰哪一页的算法——页面置换算法。页面置换算法是操作系统中虚拟存储管理的一个重要部分。页面置换算法在具有层次结构存储器的计算机中,为用户提供一个比主存储器容量大得多的可随机访问的地。常见的页面置换算法有先来先服务算法(FIFO)，最近最久未使用算法(LＲＵ)和最佳适应算法(OＰT）。
关键字:操作系统；FIFＯ；LＲＵ；OPT；Linux
目录
1 绪论?１
1．1设计任务 (1)
１.2设计思想?1
1.3设计特点?1
1．４基础知识 (2)
１．4.1 先进先出置换算法(FIFO)?2
1.4.2最近最久未使用算法（LRU) (3)
１.4.３最佳置换算法(OPT) (3)
2 各模块伪代码算法?4
2.1伪代码概念?4
2.２伪代码算法 (4)
2.2.１主函数伪代码算法.............................................. 错误!未定义书签。
２.２.2延迟时间函数伪代码算法?6
2.2．3 FＩFO算法的伪代码?７
２.2.4LRU算法的伪代码 (7)
10
2．2.5 OPＴ算法的伪代码?
3 函数调用关系图................................................................................................... １2
3．1函数声明?１2
3.1.１主要算法函数...................................................... 错误!未定义书签。
3.1．2辅助函数....................................................................................... 1２
3.2程序函数调用关系图 (13)
14
4 测试结果?
14
４.１数据初始化?
4．2页面调度算法............................................................... 错误!未定义书签。
4.2.１先进先出算法................................................................................. 1５
4.2.2最近最久未使用LRU?
15
４.2．3最佳置换算法OPＴ (17)
18
5 源程序?
6 设计总结?３0
参考文献 (31)
致谢?3２
１绪论
１.1 设计任务
１、了解UNIＸ的命令及使用格式,熟悉UNIX/LＩNＵX的常用基本命令,练习并掌握UＮIX提供的vｉ编辑器来编译C程序，学会利用gｃｃ、gｄb编译、调试Ｃ程序。
2、设计一个虚拟存储区和内存工作区，并使用最佳淘汰算法(OPＴ）、先进先出算法(FＩFO)、最近最久未使用算法（LＲU）计算访问命中率。(命中率＝１-页面失效次数／页地址流长度=1-缺页率）
１．2设计思想
在进程运行过程中,若期所有要访问的页面不在内存,而需把它们调入内存，但内存已无空闲空间时,为了保证进程正常进行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。置换算法的好坏将直接影响到系统的性能。
不适当的算法可能会导致进程发生“抖动”,即刚被换出的页很快又要被访问,需要将它重新调入，此时又需要再选一页调出；而此刚被调出的页很快又被访问，有需将它调入,如此频繁地更换页面,以致一个进程在运行中把大部分的时间都花费在页面置换工作上。
通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。改进页面置换算法,可以降低页面失败率,从而有效地提高系统性能。从理论上讲，应将那些以后不再会访问的页面置换出来，或把那些在较长时间内不会再访问的页面调出。目前已有多种置换算法,它们都试图更接近于理论上的目标。
1.3设计特点
本设计作品主要用Ｃ语言编写而成,结构简单,语言易懂,条理清晰。本作品兼容性也非常的高，可以在各种可以编译C语言的编译软件上运行,并能够在cyg ｗin中运行,经多次调试,暂时未发现有何不足。本程序的另一个优点是,程序可以计算大数量数据。如，本程序可以计算的最大物理块个数达到了10000个,用户输入的页面引用串个数也能达到10000个以上。但是,实际生活中系统的物理块个数一般不会达到10000个。因此，我们在提示用户输入页面引用串个数是,只提示最大输入1０0个。但是代码不足在于使用到了较多的ｓtatｉc全局变量使得整个代码质量不是很好,而且也只是简单的根据算法设计来模拟实现整个过程。我通过先查找该页面是否在页帧中存在,若不存在则需要页面置换,通过刷新每个页帧的ｔime值来得到每次的最小值来进行页面的置换，最小值即代表着最近最少使用的页面。
经过测试,这个系统已经达到了题目中的全部要求。这个程序有很多优点有一个是界面简明,简洁明了的程序菜单;一个是智能化的模块设计,减少了许多人工操作,如功能模块操作结束后,均会返回主菜单进行下一模板的运行,并提示是否再进行类似的操作，这样给用户带来了操作的方便，大大提高了学生选课的效率还有就是提示语言既简洁又明确,层次分明等等;当然也有缺点如程序仍然存在不合理的地方，例如程序某些部分输入错误不能立刻返回改正;信息表达方式不丰富,比较单一，缺少图片、音乐等元化表达方式。
FIFO算法总是选择在内存驻留时间最长的一页将其淘汰。这种算法基于CPＵ按线性顺序访问地址空间的这个假设上,许多时候,CＰU不是按吸纳型顺序访问地址空间的。所以，那些在内存中停留时间最长的页往往被访问到。这就造成ＦＩFＯ算法的缺页率不太理想。并且,FIFO还有一个缺点就是Belady奇异现象。实现FＩＦO算法无需硬件提供新的帮助,只采用循环数组管理驻留集即可。OＰT算法被誉为“最佳算法”,因为他淘汰下次访问距当前最远的那些页中序号最小的一页。所以，OＰＴ算法得出的缺页率是最小的。但是，ＯPT算法在使用前必须先得知整个访问串,这很难实现。因此，OPT算法知识一种概念中的算法。LRU算法的实现耗费较高,并且需要硬件的支持，但是效果较好。就缺
页率而言，OPT算法最佳,FＩFO算法最差。
１.４基础知识
1.４.１先进先出置换算法(FＩＦO)
FIFO算法是最早出现的算法。该算法总是淘汰最先进入内存的页面,即选择在内存驻留时间最久的页面予以淘汰。该算法实现简单，只需要把一个进程已调入内存的页面按先来后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。但是该算法与进程实际运行的规律不相符合,因为在进程中,有些页面经常被访问。
１.４.2 最近最久未使用算法（LＲＵ)
选择最近一段时间最长时间没有被访问过的页面予以淘汰。LＲU算法是根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况,采取“最近的过去”作为“最近的将来”的近似。选择最近最久未使用的页面予以淘汰。实现:赋予每个页面一个方位字段，用来记录一个页面自上次被访问以来所经历的时间T,当要淘汰一个页面的,选择现有页面中其T值最大的,即最近最久未使用的页面予以淘汰。
1．4.３最佳置换算法(OPT)
最佳置换算法所选择的被淘汰掉的页面,将是以后永久不再使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置算法,通常可保证获得最低的缺页率。本模拟算法中，最佳页面置换算法实现所采用的思想是：循环读入每个页表项,若该页表在内存中，则读取下一个页表项。若页表不存在内存中：一种情况是内存不满，则将页表放入内存中；若内存块已满，刚分别计算内存中各个页表再次被使用的时间，并将最久不被访问的调出，放入当前读入页表项。
2 各模块伪代码算法
根据程序提示,用户先将需要计算的页面号引用串，物理块数量和引用串个数输入到文件流中。待程序加载数据完成后,用户继续选择页面置换算法的类型，程序根据用户输入的信息来判断采用哪一种算法进行计算。结构如图2.1所示。
图2．1 总体结构图
2.1伪代码概念
伪代码（英语：pseudｏｃoｄe),又称为虚拟代码，是高层次描述算法的一种方法。使用伪代码的目的是让被描述的算法可以容易地以任何一种编程语言(Pascaｌ，C,Java,etc)实现。因此，伪代码必须结构清晰、代码简单、可读性好,介于自然语言与编程语言之间。以编程语言的书写形式指明算法职能。使用伪代码,不用拘泥于具体实现。它是半角式化、不标准的语言。可以把整个算法运行过程的结构用接近自然语言的形式(可以使用任何一种你熟悉的文字,关键是把程序的意思表达出来）描述出来。
2.2伪代码算法
2．2.1主函数伪代码算法
该程序是按自上而下，自顶向下的设计思想进行设计的。程序各个功能的实现之间的联系采用函数调用与函数嵌套。main()函数是整个程序的入口,程序
的开始就是从这里开始的，然后通过maｉｎ()函数调用其他函数来实现各个功能。具体流程如图2.2所示。
图２.２主函数流程图
Ｂegin ／＊算法开始＊/
调用desigｎＢy()→显示出设计者信息
?Scanf ｍSIZE,pSIZE,page[1０0] /*mＳＩＺE表示物理块,pSIZE表示页面号引用串个数，page［10０]表示一个引用串的页面号*/
?do {
??Printf paｇe[ｉ］
?Ｓcanｆcodｅ/*ｃｏde是一个标记，用来判断用户输入是
否符合要求*/
??Ｓwiｔch(cｏde){
ｃase1: ＦIFO() /*先进先出算法*／
cａse ２: LRU(）／*最近最久未使用算法*/??ｃase ３:ＯPＴ（) /*最佳置换算法*／
?case 4:exｉt(０)/*退出程序＊／
deｆauｌt:重新输入
?}
?}whｉｌｅ(ｃodｅ!=4)
??Geｔch(用户输入)
Ｅnd
2．2．2延迟时间函数伪代码算法
?begin
??变量定义
whｉle ｄｅlay>０
{ｗｈilｅi<1２4
?退格
???}
?end
图２.3 延迟时间函数流程图
延迟时间函数主要由两个fｏr循环构成。延迟时间函数在程序中主要起延迟时间的作用，相当于一个定时器,给程序数据加载，数据处理等提供时间保证。使程序能够正常的进行。其具体流程如图２.3所示。
2.2.3 ＦIFO算法的伪代码
?bｅgin
?定义变量
? ｗhｉｌｅi ???pagｅ［i]0→ｍeｍeｒy[ｉ］，i→tｉme[i] ?ｗｈile ｊ ??mｅｍeｒy[j]→ｔｅmp[i］[j] ?while i<ｐSIZE ?whiｌe j＜mＳIZE ???if新页面号不在物理块中 ???ｋ+＋ if k＝=ｍSＩZE ?则,计算换出页,记录该页进入物理块的时间 ?否则,ｔemp[ｉ］[ｊ］=memerｙ[j］ ??} ?priｎt 置换次数 Ｅｎd ＦIＦO算法是操作系统中最简单最容易实现的一种页面置换算法，它的实现主要运用了两个循环结构。第一个循环的功能是将页面串中的前mSIZＥ页面直接放入物理块中；第二个循环主要判断当前页面是否在物理块中，若在物理块中，则继续读取下一个页面。否则，将最先进入物理块的页面写入到物理块中。其主要执行流程如图2.4所示。 2.2．４LRU算法的伪代码 ＬRU算法是将最近进入物理块且未使用的页面首先换出物理块。ＬR Ｕ函数主要也运用了两个循环来实现其算法,首先将前mSIZE个页面置换到物理块中，然后再按具体算法进行置换页面。其执行流程如图2.５所示。 图2．4 FIFO流程图? beｇｉｎ ?定义变量 ?whilｅi ?pａｇe［ｉ］→mｅmery[i], ｉ→timｅ[i]?whｉleｊ ?ｍemeｒｙ［j］→ｔemp[i］［ｊ] ?whiｌｅi ??前mSIＺE个数直接放入 ??ｗhile i ??while ｊ ?iｆ新页面号不在物理块中 ???k++ ??判断新页面号是否在物理块中 iｆｋ=＝mSIZE 则，计算换出页,记录该页进入物理块的时间否则, max=flag［0] ??mｅｍery［j]→ｔｅmｐ[i][j］ ??｝ ??调用pｒint(置换次数) ?End 图2.5 LRU流程图 2.2.5 ＯPT算法的伪代码 begin 定义变量 whilｅi {pａgｅ[i]→memery［i], i→ｔｉmｅ[i]?ｗhile j ??memerｙ[j]→ｔemｐ[ｉ][j］ ? 前mSＩZE个数直接放入 ?ｗhｉｌe i ?{while j ??ｉｆｍemeｒy[j]!=pａge[i] ??判断新页面号是否在物理块中 ??k+＋ ｉf k＝mSIＺE ?则,计算换出页，记录该页进入物理块的时间 否则,max＝fｌag[０] ???temp[i]［j]=memerｙ［ｊ］ ??得到物理块中各页下一次访问时间 ?ｉf meｍｅrｙ[m］＝=page[1] ????退出循环 neｘｔ[m]=1 ??｝ 调用priｎｔ(置换次数) ?End OＰＴ算法是将内存中最长时间内不会用的页面置换出去,这种算法的优点是系统利用率，内存利用率都非常的高。但是这种算法目前无法实现,因为实际中,系统根本无法预知哪一个页面最先执行，哪一个页面最后执行，各个页面的执行顺序都无法确定根本就不能确定页面换出的次序。ＯPT算法主要用于对 其他算法效率的评估。OPＴ函数的执行情况如图2.６所示。 图2.6 ＯＰＴ流程图 3 函数调用关系图 3．１函数声明 3．1.1主要算法函数 主要算法函数包括FIFO（)、LRU(）和OPT()三种,它们都是无返回值类型,不带任何参数。各个函数的具体声明情况如下: vｏid FIFO(); /*先来先服务调度算法函数＊／ 返回值类型:无返回值 形参:无 vｏid LRU（); /*最近最久未使用算法函数*／ 返回值类型:无返回值 形参:无 vｏid OＰT(); ／＊最佳调度算法函数*/ 返回值类型：无返回值 形参：无 3．1.２辅助函数 辅助函数是为了实现某些功能而特意设置的一些辅助函数。本程序主要有显示引用串函数、显示设计者信息函数、数据加载函数和延迟时间函数,它们有的有形式参数，有的没有，但是它们都是无返回值类型的函数。各个函数的具体声明情况如下: void prｉｎt(unｓigned int t); ／*显示引用串函数＊／ 返回值类型:无返回值 形参:无符号整型 ｖoid ｄｅsiｇnBy()；/*显示设计者信息*／ 返回值类型：无返回值 形参:无 vｏid ｄownｌoad(）;/*数据加载*/ 返回值类型：无返回值 形参：无 vｏｉd mDｅlａy(unsｉgnedｉnｔDelａy)；/*延迟时间＊／返回值类型:无返回值 形参:无符号整型 3.２程序函数调用关系图 程序以mａin( )函数为入口,通过主函数maiｎ（)进行调用其他函数,以此实现函数的各个功能。在本程序中,maｉn( ）函数调用了dｅsignBy( )函数,用以显示设计者信息；maｉn( )函数还分别调用了FIFＯ()、LRU( )和ＯPT( )三种算法函数，实现三种算法。ＦIFO(）、LRU（)和OPT( )又分别调用了prｉnt()和cｏmpute()函数,priｎt( )显示了用户输入的页面引用串,compute()则主要计算了用户选择的算法的结果。在计算过程中，为了保证逻辑上合理,我们在coｍpｕte( )函数中调用了mＤelaｙ( )时间延迟函数；ｍain （）函数也调用了downlｏａｄ( )数据加载函数，主要功能是加载用户输入的数据以供各种算法使用。在调用download()过程中，也调用了时间延迟函数ｍDｅlay()。具体函数调用关系如图3．１所示。 图3．1 函数调用关系 ４测试结果 ４.1数据初始化 用户根据程序提示,按照要求输入相应的数据。例如，本次测试中我们设置物理块个数为4,页面引用串个数为2０,一个页面号引用串中各个页面号之间用空格(“ ”)隔开。值得注意的是,物理块个数可以是几个，几十个,甚至几百个，但是考虑到系统的效率,一般取物理块个数在１0个以内；页面号引用串个数也和物理块个数一样，页面引用串个数取100个以内。用户输入情况如图4.1所示。 图 4.1 界面初始化 ４．2页面调度算法 选择一个合适的页面置换算法对提高内存的利用率会有很大的帮助。当用户将数据初始化结束后，就要进行页面调度算法的选择了。下面本书将逐一说明先进先出算法FIＦO、最近最久未使用ＬRＵ和最佳置换算法的具体调试情况。 课程设计报告 2015～2016学年第一学期 操作系统综合实践课程设计 实习类别课程设计 学生姓名李旋 专业软件工程 学号130521105 指导教师崔广才、祝勇 学院计算机科学技术学院 二〇一六年一月 - 1 - - 2 - 一、概述 一个目录文件是由目录项组成的。每个目录项包含16B，一个辅存磁盘块(512B)包含32个目录项。在目录项中，第1、2字节为相应文件的外存i节点号，是该文件的内部标识；后14B为文件名，是该文件的外部标识。所以，文件目录项记录了文件内、外部标识的对照关系。根据文件名可以找到辅存i节点号，由此便得到该文件的所有者、存取权、文件数据的地址健在等信息。UNIX 的存储介质以512B为单位划分为块，从0开始直到最大容量并顺序加以编号就成了一个文件卷，也叫文件系统。UNIX中的文件系统磁盘存储区分配图如下： 本次课程设计是要实现一个简单的模拟Linux文件系统。我们在内存中开辟一个虚拟磁盘空间(20MB)作为文件存储器，并将该虚拟文件系统保存到磁盘上(以一个文件的形式)，以便下次可以再将它恢复到内存的虚拟磁盘空间中。文件存储空间的管理可采用位示图方法。 二、设计的基本概念和原理 2.1 设计任务 多用户、多级目录结构文件系统的设计与实现。可以实现下列几条命令login 用户登录 logout 退出当前用户 dir 列文件目录 creat 创建文件 delete 删除文件 open 打开文件 close 关闭文件 - 3 - read 读文件 write 写文件 mkdir 创建目录 ch 改变文件目录 rd 删除目录树 format 格式化文件系统 Exit 退出文件系统 2.2设计要求 1) 多用户：usr1,usr2,usr3,……,usr8 (1-8个用户) 2) 多级目录：可有多级子目录； 3) 具有login (用户登录)4) 系统初始化（建文件卷、提供登录模块） 5) 文件的创建：create (用命令行来实现)6) 文件的打开：open 7) 文件的读：read8) 文件的写：write 9) 文件关闭：close10) 删除文件：delete 11) 创建目录（建立子目录）：mkdir12) 改变当前目录：cd 13) 列出文件目录：dir14) 退出：logout 新增加的功能： 15) 删除目录树：rd 16) 格式化文件系统：format 2.3算法的总体思想 - 4 - 目录 1．问题的提出 (2) 1.1关于页面置换算法模拟程序问题的产生 (2) 1.2任务分析 (2) 2．需求分析 (2) 3．方案设计 (3) 4．总体设计 (4) 4.1程序N-S图 (4) 4.2主要的函数 (4) 4.3主要流程图及代码 (5) 4.3.1 FIFO（先进先出） (5) 4.3.2 LRU（最近最久未使用） (6) 4.3.3 OPT（最佳置换算法） (8) 4.4实现结果 (11) 5．程序测试 (14) 5.1设计测试数据 (14) 5.2测试结果及分析 (15) 摘要 随着计算机的普及人们的物质生活得到了极大的满足，人们在精神生活方面同样也需要 提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果. 本课程设计是学生学习完《操作系统教程》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。 关键词：编制页面置换算法模拟程序、打印页面、FIFO页面算法、LRU页面置换算法、OPT页面置换算法。 操作系统课程设计-页面置换算法C语言 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三、设计要求 1、编写算法，实现页面置换算法FIFO、LRU； 2、针对内存地址引用串，运行页面置换算法进行页面置换； 3、算法所需的各种参数由输入产生（手工输入或者随机数产生）； 4、输出内存驻留的页面集合，页错误次数以及页错误率； 四．相关知识： 1．虚拟存储器的引入： 局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。 2．虚拟存储器的定义： 虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 3．虚拟存储器的实现方式： 分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。 请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。 4．页面分配： 平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。 考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。 5．页面置换算法： 常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 五、设计说明 1、采用数组页面的页号 2、FIFO算法，选择在内存中驻留时间最久的页 面予以淘汰； 分配n个物理块给进程，运行时先把前n个不同页面一起装入内存，然后再从后面逐一比较，输出页面及页错误数和页错误率。3、LRU算法，根据页面调入内存后的使用情况 进行决策； 同样分配n个物理块给进程，前n个不同页面一起装入内存，后面步骤与前一算法类似。 选择置换算法，先输入所有页面号，为系统分 淮海工学院计算机工程学院实验报告书 课程名：《操作系统原理A 》 题目：虚拟存储器管理 页面置换算法模拟实验 班级：软件*** 学号：20**1228** 姓名：**** 一、实验目的与要求 1.目的： 请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。 2.要求： 本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。 二、实验说明 1．设计中虚页和实页的表示 本设计利用C语言的结构体来描述虚页和实页的结构。 在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。 在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。 2．关于缺页次数的统计 为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内， 此虚页被命中，count加1。最终命中率=count/20*100%。 3．LRU算法中“最近最久未用”页面的确定 为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问 一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前 一、实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 二、实验内容 基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。 1、最佳淘汰算法（OPT） 2、先进先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、简单时钟(钟表)算法（CLOCK） 命中率＝１－页面失效次数／页地址流(序列)长度 三、实验原理 UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。 当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。为实现请求调页，核心配置了四种数据结构：页表、页帧（框）号、访问位、修改位、有效位、保护位等。 当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。 四、算法描述 本实验的程序设计基本上按照实验内容进行。即使用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。 （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在[0，319]的指令地址之间随机选取一起点m B：顺序执行一条指令，即执行地址为m+1的指令 C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’ D：顺序执行一条指令，其地址为m’+1 专业计算机科学与技术 目录 1.设计目的 (2) 2.课设要求 (2) 3.系统分析 (3) 4.系统设计 (3) 4.1问题分析 (3) 4.2程序整体框图 (5) 4.3 FIFO算法 (5) 4.4 LRU算法 (6) 4.5 OPT算法 (7) 5.功能与测试 (8) 5.1开始界面 (8) 5.2 FIFO算法 (9) 5.3 LRU算法 (10) 5.4 OPT算法 (10) 6.结论 (11) 7.附录 (12) 1.设计目的 1、存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本次设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。 2、提高自己的程序设计能力、提高算法设计质量与程序设计素质； 2.课设要求 设计一个请求页式存储管理方案。并编写模拟程序实现之。要求包含： 1．过随机数产生一个指令序列，共320条指令。其地址按下述原则生成： ①50%的指令是顺序执行的； ②25%的指令是均匀分布在前地址部分； ③25%的指令是均匀分布在后地址部分； 具体的实施方法是： 在[0，319]的指令地址之间随机选区一起点M; 顺序执行一条指令，即执行地址为M+1的指令； 在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’; 顺序执行一条指令，其地址为M’+1； 在后地址[M’+2，319]中随机选取一条指令并执行； 重复A—E，直到执行320次指令。 2．指令序列变换成页地址流 设：（1）页面大小为1K； 用户内存容量为4页到32页； 用户虚存容量为32K。 在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为： 上海电力学院 计算机操作系统原理 课程设计报告 题目名称：编写程序模拟虚拟存储器管理 姓名：杜志豪.学号： 班级： 2012053班 . 同组姓名：孙嘉轶 课程设计时间：—— 评语： 成绩： 目录 一、设计内容及要求 (4) 1. 1 设计题目 (4) 1．2 使用算法分析： (4) 1． FIFO算法（先进先出淘汰算法） (4) 1． LRU算法（最久未使用淘汰算法） (5) 1. OPT算法（最佳淘汰算法） (5) 分工情况 (5) 二、详细设计 (6) 原理概述 (6) 主要数据结构(主要代码) (6) 算法流程图 (9) 主流程图 (9) Optimal算法流程图 (10) FIFO算法流程图 (10) LRU算法流程图 (11) ．1源程序文件名 (11) . 2执行文件名 (11) 三、实验结果与分析 (11) Optimal页面置换算法结果与分析 (11) FIFO页面置换算法结果与分析 (16) LRU页面置换算法结果与分析 (20) 四、设计创新点 (24) 五、设计与总结 (27) 六、代码附录 (27) 课程设计题目 一、设计内容及要求 编写程序模拟虚拟存储器管理。假设以M页的进程分配了N 块内存（N 实验四页面置换算法模拟（2）一．题目要求： 设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程，并计算访问命中率： 要求设计主界面以灵活选择某算法，且以下算法都要实现 1) 最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再 被访问的页面换出。 2) 先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留 时间最久的页面予以淘汰。 3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。 4) 最不经常使用算法(LFU) 二．实验目的： 1、用C语言编写OPT、FIFO、LRU，LFU四种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三．相关知识： 1．虚拟存储器的引入： 局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。 2．虚拟存储器的定义： 虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 3．虚拟存储器的实现方式： 分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。 请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。 4．页面分配： 平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。 考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。 5．页面置换算法： 常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 实验编号４ 名称页面置换算法模拟 实验目的 通过请求页式存储管理中页面置换算法模拟设计，以便： 1、了解虚拟存储技术的特点 2、掌握请求页式存储管理中页面置换算法 实验容与步骤 设计一个虚拟存储区和存工作区，并使用FIFO和LRU算法计算访问命中率。 <程序设计> 先用srand()函数和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算相应的命中率。 <程序1> #include int pn, pfn; struct pfc_struct *next; }pfc_type; pfc_type pfc[32]; pfc_type *freepf_head,*busypf_head,*busypf_tail;//空闲页头指针，忙页头指针，忙页尾指针 int NoPageCount; //缺页次数 int a[total_instruction];//指令流数组 int page[total_instruction], offset[total_instruction];//每条指令的页和页偏移 void initialize( int ); void FIFO( int );//先进先出 void LRU( int );//最近最久未使用 void NRU( int );//最近最不经常使用 /**************************************************************************** main() *****************************************************************************/ void main(){ int i,s; //srand(10*getpid());//用进程号作为初始化随机数队列的种子//Linux版 srand(10*GetCurrentProcessId());//用进程号作为初始化随机数的种子//Windows版 s=rand()%320;//在[0，319]的指令地址之间随机选取一起点m for(i=0;i 实验原理： 在内存运行过程中，若其所要访问的页面不在内存而需要把他们调入内存，但内存已经没有空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将那个页面调出，需根据一定的算法来确定。通常，把选择换出页面的算法成为页面置换算法。置换算法的好坏，将直接影响到系统的性能。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面置换出，或者把那些在较长时间内不会在访问的页面调出。目前存在着许多种置换算法（如FIFO，OPT，LRU），他们都试图更接近理论上的目标。 实验目的： 1．熟悉FIFO，OPT和LRU算法 2．比较三种算法的性能优劣 实验内容： 写出FIFO，OPT和LRU算法的程序代码，并比较它们的算法性能。 实验步骤： 代码如下： #include int queue1[20],queue2[20],queue3[20]; //记录置换的页int K=0,S=0,T=0; //置换页数组的标识 int pos=0;//记录存在最长时间项 //初始化内存页表项及存储内存情况的空间 void INIT(){ int i; for(i=0;i 操作系统课程设计报告题目：页面置换算法模拟程序 学院名称: 专业班级： 学生姓名： 指导教师： 成绩： 目录 一、设计目的 (3) 二、设计题目 (3) 2.1设计内容 (3) 2.2设计要求 (3) 三、设计过程 (4) 3.1 FIFO（先进先出） (4) 3.2 LRU（最近最久未使用） (5) 3.3 OPT（最佳置换算法） (6) 3.4 随机数发生器 (7) 四、完整代码 (7) 五、运行结果演示 (13) 六、设计心得 (16) 七、参考文献 (16) 操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果。 本课程设计是学生学习完《计算机操作系统》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。 二、设计题目：页面置换算法模拟程序 2.1设计内容 编制页面置换算法的模拟程序。 2.2设计要求 1).用随机数方法产生页面走向，页面走向长度为L(15<=L<=20),L由控制台输入。 2).根据页面走向，分别采用Optinal、FIFO、LRU算法进行页面置换，统计缺页率。 3).假定可用内存块为m(3<=m<=5)，m由控制台输入，初始时，作业页面都不在内存。 4).要求写出一份详细的设计报告。课程设计报告内容包括：设计目的、设计内容、设计原理、算法实现、流程图、源程序、运行示例及结果分析、心得体会、参考资料等。 操作系统课程实验报告 断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。最简单的页面置换算法是先入先出（FIFO）法。 2、算法流程图 3、步骤说明 （1）初始化 void init(){//初始化 int i; for (i = 0; i < page_frame_number; i++){ page_table[i].page_id = -1; page_table[i].load_time = -1; page_table[i].last_visit_time = -1; } } （2）选择算法，输入插入页面号。进入判断函数 int judge(){//判断页框是否满，或者页框里面是否已存在页面 int i; for (i = 0; i < page_frame_number; i++){ if (page_table[i].page_id == -1 || page_table[i].page_id == page_id) return i; } return -2; } 之后根据返回数的不同决定了不同类型 返回-2则说明页框满且页框里面没有存在要插入的页面。 返回-1则说明页框未满 返回其它数则说明页框里存在相同的页面 （3）//当没有空页框，并且页面本身也没有存在，则执行一下代码 qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp);//按照装入时间从小到大排序 page_table[0].page_id = page_id; page_table[0].load_time = counter; page_table[0].last_visit_time = counter; page_interrupt_number++; 将页框号为0的页面置换成最新插入的页面。 int cmp(const void *p, const void *q){//按照装入时间从小到大排序 int c = (*(struct Page_table*)p).load_time - (*(struct Page_table*)q).load_time; if (c > 0) return 1; else return -1; } 排序函数，将页面按装入时间从小到大排序 （4）//如果页面未满，则将页面替换在空页框里 if (page_table[j].page_id == -1){ page_table[j].page_id = page_id; page_table[j].load_time = counter; page_table[j].last_visit_time = counter; page_interrupt_number++; 则将页面替换在页框号最小的空页框里 （5）//如果页面本身存在页框中，则执行一下代码 page_table[j].last_visit_time = counter; 则更新页面的最近访问时间 （6）qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp3);//按照装入时间从小到大排序 print(2); 打印出页表详细信息 printf("页表信息：\n页号页框号装入时间最近访问时间\n"); for (j = 0; j < page_frame_number; j++){ printf("%4d%8d%7d%7d\n", page_table[j].page_id, j, page_table[j].load_time, 课程设计报告 课程名称操作系统 课题名称页面置换算法模拟设计 专业通信工程 班级 学号 姓名 指导教师 2014年6 月29 日 湖南工程学院 课程设计任务书 课程名称操作系统 课题页面置换算法模拟设计 专业班级 学生姓名 学号 指导老师 审批 任务书下达日期2014 年 6 月23 日 任务完成日期2014 年 6 月29 日 目录 1课题概述 (4) 1.1设计要求 (4) 1.2 理论分析 (4) 2系统分析 (6) 3程序实现 (8) 4程序测试 (13) 5心得体会 (15) 6附录 (16) 7 评分表 (30) 课题：页面置换算法模拟设计 1课题概述 1.1设计要求 计算并输出下述各种算法在不同内存容量下的命中率。 A. FIFO先进先出的算法 B. LRR最近最少使用算法 C. OPT最佳淘汰算法（先淘汰最不常用的页地址） D. LFR最少访问页面算法 E. NUR最近最不经常使用算法 设计技术参数： （1）命中率=1-页面失效次数/页地址流长度 （2）本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。 （3）随机数产生方法，采用系统提供函数SRAND()和RAND ()来产生 1.2 理论分析 在进程运行过程中，若其所要访问的页面不在内存所需把他们调入内存，但内存已无空闲时，为了保证进程能够正常运行，系统必须从内存中调入一页程序或数据送磁盘的对换区中。但应将那个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。置换算法的好坏，将直接影响到系统的性能。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上将讲，应将那些以后不再访问的页面换出，或把那些较长时间内不再访问的页面调出。目前存在着不同的算法，他们都试图更接近与理论上的目标。 南通大学计算机科学与技术学院操作系统课程设计报告 专业： 学生姓名： 学号： 时间： 操作系统模拟算法课程设计报告 设计要求 将本学期三次的实验集成实现： A.处理机管理； B.存储器管理； C.虚拟存储器的缺页调度。 设计流程图 主流程图 开始的图形界面 处理机管理存储器管理缺页调度 先来先服务时 间 片 轮 转 首 次 适 应 法 最 佳 适 应 法 先 进 先 出 L R U 算 法 A.处理机调度 1)先来先服务FCFS N Y 先来先服务算法流程 开始 初始化进程控制块，让进程控制块按进程到达先后顺序让进程排队 调度数组中首个进程，并让数组中的下一位移到首位 计算并打印进程的完成时刻、周转时间、带权周转时间 其中：周转时间 = 完成时间 - 到达时间 带权周转时间=周转时间/服务时间 更改计时器的当前时间,即下一刻进程的开始时间 当前时间=前一进程的完成时间+其服务时间 数组为空 结束 2)时间片轮转法 开始 输入进程总数 指针所指的进程是 否结束 输入各进程信息 输出为就绪状态的进程的信息 更改正在运行的进程的已运行时间 跳过已结束的程序 结束 N 指向下一个进程 Y 如果存在下一个进程的话 Y N 输出此时为就绪状态的进程的信息 时间片轮转算法流程图 B.存储器管理(可变式分区管理） 1)首次适应法 分配流程图 申请xkb内存 由链头找到第一个空闲区 分区大小≥xkb？ 大于 分区大小=分区大小-xkb，修改下一个空闲区的后向指针内容为（后向指针）+xkb;修改上一个空闲区的前向指针为（前向指针）+xkb 将该空闲区从链中摘除：修改下一个空闲区的后向地址=该空闲区后向地址，修改上一个空闲区的前向指针为该空闲区的前向指针 等于 小于延链查找下 一个空闲区 到链尾 了？ 作业等待 返回是 否 登记已分配表 返回分配给进程的内存首地址 开始 淮海工学院计算机科学系实验报告书 课程名：《操作系统原理A 》 题目：虚拟存储器管理 页面置换算法模拟实验 班级： 学号： 姓名： 一、实验目的与要求 1.目的： 请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。 2.要求： 本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。 二、实验说明 1．设计中虚页和实页的表示 本设计利用C语言的结构体来描述虚页和实页的结构。 在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。 在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。 2．关于缺页次数的统计 为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内， 此虚页被命中，count加1。最终命中率=count/20*100%。 3．LRU算法中“最近最久未用”页面的确定 为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问 一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前 摘要 在lｉnｕｘ中,为了提高内存利用率,提供了内外存进程对换机制,内存空间的分配和回收均以页为单位进行，一个进程只需要将其一部分调入内存便可运行；当操作系统发生缺页中断时，必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。因而引入一种用来选择淘汰哪一页的算法——页面置换算法。页面置换算法是操作系统中虚拟存储管理的一个重要部分。页面置换算法在具有层次结构存储器的计算机中,为用户提供一个比主存储器容量大得多的可随机访问的地。常见的页面置换算法有先来先服务算法(FIFO)，最近最久未使用算法(LＲＵ)和最佳适应算法(OＰT）。 关键字:操作系统；FIFＯ；LＲＵ；OPT；Linux 目录 1 绪论?１ 1．1设计任务 (1) １.2设计思想?1 1.3设计特点?1 1．４基础知识 (2) １．4.1 先进先出置换算法(FIFO)?2 1.4.2最近最久未使用算法（LRU) (3) １.4.３最佳置换算法(OPT) (3) 2 各模块伪代码算法?4 2.1伪代码概念?4 2.２伪代码算法 (4) 2.2.１主函数伪代码算法.............................................. 错误!未定义书签。 ２.２.2延迟时间函数伪代码算法?6 2.2．3 FＩFO算法的伪代码?７ ２.2.4LRU算法的伪代码 (7) 10 2．2.5 OPＴ算法的伪代码? 3 函数调用关系图................................................................................................... １2 3．1函数声明?１2 3.1.１主要算法函数...................................................... 错误!未定义书签。 计算机操作系统课程设计 班级：计091-1 姓名： 学号： 使用语言：C++ 指导老师： 学院： 一、系统要求 1、实验目的 通过一个简单多用户文件系统的设计，加深理解文件系统的内部功能及内部实现。 2、实验内容 为linux系统设计一个简单的二级文件系统。要求做到以下几点： （1）可以实现下列几条命令（至少4条）； login 用户登陆 dir 列文件目录 create 创建文件 delete 删除文件 open 打开文件 close 关闭文件 read 读文件 write 写文件 （2）列目录时要列出文件名、物理地址、保护码和文件长度； （3）源文件可以进行读写保护。 二、系统分析 1、设计思想 本文件为二级文件系统，即要实现对文件的增删改查，同时又具备登陆系统、注册用户的功能，各个用户之间的文件系统互不干扰。 本文件系统采用两级目录，其中第一级对应于用户账号，第二级对应于用户帐号下的文件。另外，为了简便文件系统未考虑文件共享，文件系统安全以及管道文件与设备文件等特殊内容。 系统采用结构体来存储用户、文件目录、文件数据内容： 0 48*5 48*5+44*50 48*5+44*50+264*200 每个分区都是由结构体组成，每个个去的结构体的个数由格式化系统是决定。 整个系统的编码构成主要分为： Allstruct.h 定义了每个分区的结构体； Mysys.h 声明了对系统操作的各种方法；Myuserfile.h 声明了对文件操作的各种方法； Mymain.cpp 整个系统的主函数，操作入口； Mysys.cpp 包含了mysys.h，实现了操作系统的各种方法；Myuserfile.cpp 包含了myuserfile.h，实现了操作文件的各种方法； 2、主要数据结构 Allstruct.h文件的内容： struct s_user //用户区结构体 { long isuse; //是否使用 char name[20]; //用户名 char psd[20]; //密码 long address; //目录地址 }; 实验二存储管理 一、实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 二、实验内容 基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。 1、最佳淘汰算法（OPT） 2、先进先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、简单时钟(钟表)算法（CLOCK） 命中率＝１－页面失效次数／页地址流(序列)长度 三、实验原理简述 UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。 当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。为实现请求调页，核心配置了四种数据结构：页表、页帧（框）号、访问位、修改位、有效位、保护位等。 当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。 四、算法描述 本实验的程序设计基本上按照实验内容进行。即使用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。 （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在[0，319]的指令地址之间随机选取一起点m B：顺序执行一条指令，即执行地址为m+1的指令 页面置换算法的演示 一．题目要求： 设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程，并计算访问命中率： 要求设计主界面以灵活选择某算法，且以下算法都要实现 1) 最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再 被访问的页面换出。 2) 先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留 时间最久的页面予以淘汰。 3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。 4) 最不经常使用算法(LFU) 二．实验目的： 1、用C语言编写OPT、FIFO、LRU，LFU四种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三．相关知识： 1．虚拟存储器的引入： 局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。 2．虚拟存储器的定义： 虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 3．虚拟存储器的实现方式： 分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。 请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。 4．页面分配： 平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。 考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。 5．页面置换算法： 常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 四．设计思想： 选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：OPT基本思想： 是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组next[mSIZE]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。 【特别声明】 若物理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。 FIFO基本思想： 是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。 LRU基本思想： 是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。 五．流程图： 如下页所示操作系统课程设计
页面置换算法模拟程序-附代码
操作系统课程设计-页面置换算法C语言
虚拟存储器管理 页面置换算法模拟实验
页面置换算法实验报告
页面置换算法课程设计
操作系统课程设计报告
实验四页面置换算法代码
页面置换算法模拟实验报告
页面置换算法代码实现(完整版)
(流程图)页面置换算法课程设计
第7次 常用页面置换算法模拟实验
页面置换算法模拟设计
操作系统(一个小型操作系统的设计与实现)课程设计
操作系统页面置换算法模拟实验
操作系统常用页面置换算法课程设计
计算机操作系统课程设计
页面置换算法实验(内含完整代码)
(完整版)页面置换算法C语言
- 页面置换算法模拟程序-附代码
- 页面置换算法实验报告
- 常用页面置换算法模拟实验
- 请求页式存储管理中常用页面置换算法
- 页面置换算法的模拟实现及命中率对比实验报告
- 操作系统页面置换算法模拟实验
- 请求页式存储管理中常用页面置换算法模拟(优.选)
- 页面置换算法作业
- 页面置换算法模拟实验报告
- 《操作系统》实验五页面置换算法模拟
- 页面置换算法代码实现完整版
- 实验七请求页式存储管理中常用页面置换算法模拟
- 页面置换算法实验报告
- 页面置换算法课程设计
- 页面置换算法
- 操作系统页面置换算法例题
- 页面置换算法模拟 实验报告
- 页面置换算法的实验报告
- 操作系统 七次实验报告 常用页面置换算法模拟实验..
- 页面置换算法实验报告