页面置换算法模拟实验
【实验目的】
1 ）进一步掌握虚拟存储器的工作原理。
2）通过实验理解和掌握FIFO, LRU，OPT三种页面置换算法。
3）比较各种页面置换算法的优缺点。
【实验要求】
1）认真阅读和掌握预备知识。
2）上机操作。
【预备知识】
在采用请求分页机制的操作系统中，当运行一个进程的时侯，若所要访问的页面不在内
存中而需要把它们调入内存，但此时内存已无空闲空间，为了保证该进程能正常运行，需选择内存中暂时不用的一个页面调出到磁盘交换区。选择调出哪个页面，由页面置换算法决定。
页面置换算法的好坏，直接影响着系统的性能。一个好的页面置换算法，应尽可能选择调出较长时间内不会再访问的页面，以保证较低的缺页率。常见的页面置换算法有OPT （最佳置换算法），FIFO （先进先出算法）及LRU （最近最久未使用算法）。
一、OPT算法
1. 原理简述
1）在分配内存页面数（B）小于进程页面数（P）时，最先用到的B个页面依次放入内存；
2）这时若需要处理新的页面，而当前分配的内存页面全部不空闲时，选择换出以后永
远不再使用的页。如没有这样的页面存在，则应选择下次访问距离现在最久的页换出，以空出内存来放置新调入的页面；
3）以后如果有新页面需要调入，按“2）”之规则进行。
该算法能保证有最低的缺页率，所以称为最佳置换算法。但是该算法仅仅是一种理想状况下的算法，因为在进程实际运行过程中，将来会执行到哪个页是不可预知的，所以无法选择该置换哪个页出去。因此，本算法在实际中无法使用，只能作为一种标准来衡量其他算法的性能。
2. 图表描述
假设某个进程在交换区被分为5个页面（P=5 ），分别以1，2，3，4，5表示。在该进程运行过程中，处理机调用它们的顺序即页地址流为：
而系统分配给该进程的内存空间只有 3 （B= 3 ）个页面，那么在使用OPT算法时，这
3个页面的内存使用情况应该是：
为了便于比较学习，例子和前面的一样。在使用
FIFO 算法时，这3个页面的内存使用
5
2
3
3
5
5 4
2
(f)
、FIFO 算法
1. 原理简述
1） 在分配内存页面数（B ）小于进程页面数（P ）时，最先用到的 B 个页面依次放入内 存； 2） 这时若需要处理新的页面，则从当前内存中的 B 个页面中选择调出最先进入的那个
页（所以称为FIFO ）,然后放入新页面；
3） 以后如果有新页面需要调入，按“ 2）”之规则进行。 该算法将所使用的内存页面构成一个循环队列，
每次置换时将队列中的队首换出， 队首
指针后移一位即可， 算法容易实现。但是最先进入内存的页未必将来就不再用到， 甚至可能
很快就会用到，所以不能保证有较低的缺页率，算法性能较差。 2. 图表描述
本例共缺页6次，缺页率为6/12
()()
5
情况应该是:
标
记
本例共缺页9次，缺页率为9/12
三、LRU算法
1. 原理简述
1）在分配内存页面数（B）小于进程页面数（P）时，最先用到的B个页面依次放入内存；
2）这时若需要处理新的页面，而当前分配的内存页面全部不空闲时，选择调出其中最
长时间没有用到的那个页面，用空出的内存来放置新调入的页面，所以称为LRU （最近最久未使用）算法；
3）以后如果有新页面需要调入，按“2）”之规则进行。
该算法根据局部性原理，认为最近一段时间内，最长时间没有用到的那个页将来用到的
可能性也很小，所以替换这样的页出去，也能保证比较低的缺页率，其性能接近OPT算法。但是需要有专门的存储单元来记录每个页面有多久未被使用，并且要随时更新该记录，所以算法的开销比较大。
2. 图表描述：
【实验内容】
1）编译opt.c，实现OPT置换算法。（源程序已给）多次执行，查看OPT置换算法的详细置换过程及结果。
2）编辑lru.c，实现LRU置换算法。（源程序已给）
多次执行exam16b ，查看LRU置换算法的详细置换过程及结果。
为了便于比较学习，例子和前面的一
样。
在使用FIFO算法时，这3 个页面的内存使用
5
7次，缺页率为7/12 。
3）代码参照前两个算法自行编写，实现FIFO置换算法。（自行设计，需在报告中给出）
编译并多次执行“ fifo.c ”，查看FIFO置换算法的详细置换过程及结果。
4）在一个程序中同时实现OPT, LRU和FIFO三种置换算法。（自行设计，需在报告中给出）
编译并多次执行，比较三种置换算法在同一组数据下的运行结果并分析其原因。
目录 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页面置换算法。
一、实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 二、实验内容 基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。 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
淮海工学院计算机工程学院实验报告书 课程名：《操作系统原理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项值设置为增值后的当前
实验4 页面置换算法（2学时） 一、实验目的 通过实验加强对虚拟存储管理中页面置换算法的理解和掌握。 二、实验内容 编写程序实现虚拟存储管理中OPT,FIFO,LRU页面置换算法。 三、实验要求 1、任意给出一组页面访问顺序（如页面走向是1、 2、5、7、5、7、1、4、 3、5、6、 4、3、2、1、 5、2）。 2、分配给该作业一定的物理块（如3块、4块等）。 3、利用OPT,FIFO,LRU页面置换算法模拟页面置换过程并计算其缺页率。 4、每访问一个页面均需给出内存中的内容（内存中的页面号），若有淘汰还需给出淘汰的页面号。 5、通过给出特殊的页面访问顺序，分配不同的物理块，利用FIFO 算法计算其缺页率，进一步理解Belady现象。 6、（附加）实现CLOCK置换算法，修改位可在确定页面号时直接任意给出。 代码部分： #include
int v; int i; int a; srand(time(NULL)); for(i=0; i 实验四页面置换算法模拟（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等。 实验五. 请求页式存储管理的模拟 [实验内容]: 熟悉虚拟存储管理的各种页面置换算法，并编写模拟程序实现请求页式存储管理的页面置换算法----最近最久未使用算法（LRU），要求在每次产生置换时显示页面分配状态和缺页率。 [实验要求]： 1、运行给出的实验程序，查看执行情况，进而分析算法的执行过程，在理解FIFO页面置换算法和最近最久未使 用算法（LRU）置换算法后，给出最佳置换算法的模拟程序实现，并集成到参考程序中。 2、执行2个页面置换模拟程序，分析缺页率的情况。最好页框数和访问序列长度可调节，在使用同一组访问序 列数据的情况下，改变页框数并执行2个页面置换模拟程序，查看缺页率的变化。 3、在每次产生置换时要求显示分配状态和缺页率。程序的地址访问序列通过随机数产生，要求具有足够的长度。 最好页框数和访问序列长度可调节。 实验的执行结果如下图所示（左下图为FIFO执行结果，右下图为LRU执行结果）： 程序源代码： #include 实验5 页面置换算法 一、实验题目：页面置换算法（请求分页） 二、实验目的： 进一步理解父子进程之间的关系。 1）理解内存页面调度的机理。 2）掌握页面置换算法的实现方法。 3）通过实验比较不同调度算法的优劣。 4）培养综合运用所学知识的能力。 页面置换算法是虚拟存储管理实现的关键，通过本次试验理解内存页面调度的机制，在模拟实现FIFO、LRU等经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。将不同的置换算法放在不同的子进程中加以模拟，培养综合运用所学知识的能力。 三、实验内容及要求 这是一个综合型实验，要求在掌握父子进程并发执行机制和内存页面置换算法的基础上，能综合运用这两方面的知识，自行编制程序。 程序涉及一个父进程和两个子进程。父进程使用rand()函数随机产生若干随机数，经过处理后，存于一数组Acess_Series[]中，作为内存页面访问的序列。两个子进程根据这个访问序列，分别采用FIFO和LRU两种不同的页面置换算法对内存页面进行调度。要求： 1）每个子进程应能反映出页面置换的过程，并统计页面置换算法的命中或缺页情况。 设缺页的次数为diseffect。总的页面访问次数为total_instruction。 缺页率= disaffect/total_instruction 命中率= 1- disaffect/total_instruction 2）将为进程分配的内存页面数mframe 作为程序的参数，通过多次运行程序，说明FIFO算法存在的Belady现象。 四、程序流程图 开始 创建子进程1 创建子进程2 结束 操作系统课程实验报告 断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。最简单的页面置换算法是先入先出（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, 页面置换算法实验报告 一、实验目的： 设计和实现最佳置换算法、随机置换算法、先进先出置换算法、最近最久未使用置换算法、简单Clock置换算法及改进型Clock置换算法；通过支持页面访问序列随机发生实现有关算法的测试及性能比较。 二、实验内容： ●虚拟内存页面总数为N，页号从0到N-1 ●物理内存由M个物理块组成 ●页面访问序列串是一个整数序列，整数的取值范围为0到N - 1。页面访问序 列串中的每个元素p表示对页面p的一次访问 ●页表用整数数组或结构数组来表示 ?符合局部访问特性的随机生成算法 1.确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页 数e，工作集移动率m（每处理m个页面访问则将起始位置p +1）， 以及一个范围在0和1之间的值t； 2.生成m个取值范围在p和p + e间的随机数，并记录到页面访问序 列串中； 3.生成一个随机数r，0 ≤r ≤1； 4.如果r < t，则为p生成一个新值，否则p = (p + 1) mod N； 5.如果想继续加大页面访问序列串的长度，请返回第2步，否则结束。 三、实验环境： 操作系统：Windows 7 软件：VC++6.0 四、实验设计： 本实验包含六种算法，基本内容相差不太，在实现方面并没有用统一的数据结构实现，而是根据不同算法的特点用不同的数据结构来实现： 1、最佳置换和随机置换所需操作不多，用整数数组模拟内存实现； 2、先进先出置换和最近最久未使用置换具有队列的特性，故用队列模拟内 存来实现； 3、CLOCK置换和改进的CLOCK置换具有循环队列的特性，故用循环队 列模拟内存实现； 4、所有算法都是采用整数数组来模拟页面访问序列。 淮海工学院计算机科学系实验报告书 课程名：《操作系统原理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项值设置为增值后的当前 实验二存储管理 一、实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 二、实验内容 基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。 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的指令 操作系统课程设计报告课程名称：操作系统课程设计 课程设计题目：页面置换算法 学院：计算机科学与技术学院 专业：科技 小组成员: 庞思慧E01114081 王蒙E01114161 姚慧乔E01114349 朱潮潮E01114408 指导老师：邱剑锋 目录 1 实验目的 (3) 2 实验要求 (3) 3 实验内容与步骤 (3) 4 算法思想 (4) 5 模块设计 (4) 6 程序设计 (5) 7 测试结果 (7) 8 结果分析 (9) 9 程序代码 (9) 10 课程设计小结 (24) 页面置换算法模拟设计 1.实验目的 （1）通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。 （2）掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。 （3）通过对几种置换算法命中率的比较，来对比他们的优缺点。 2.实验要求 计算并输出下述各种算法在不同内存容量下的命中率。 A 先进先出的算法（FIFO） B 最近最少使用算法（LRU） C最佳淘汰算法（OPT） 3.实验内容与步骤 (1)通过随机数产生一个指令序列，共320条指令，具体的实施方法是： A．[0，319]的指令地址之间随机选取一起点M; B．顺序执行一条指令，即执行地址为M+1的指令； C．在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’; D．顺序执行一条指令，其地址为M’+1； E．在后地址[M’+2，319]中随机选取一条指令并执行； F．重复A—E，直到执行320次指令。 (2)指令序列变换成页地址流 A.页面大小为1K； B.用户内存容量为4页到32页； 大理大学课程教案 （实验教学） 课程名称：操作系统 课程类型：（ 1 ）1、必修；2、选修；3、其它 授课对象：计算机科学与技术专业（本）2013级1、2班授课时间： 2015 至 2016 学年 2 学期 计划学时： 48 学时（其中：理论 32 ，实验： 16 ） 任课教师：曾新 所属学院：数学与计算机学院 课程管理部门（教研室）：硬件教研室 大理大学教务处制 大理大学课程教案（教学要求） 课程名称：操作系统 教材：计算机操作系统教程（第3版）、清华大学出版社 授课人：曾新专业技术职务：助教 学历：研究生学位：硕士 实验题目：存储管理常用页面置换算法模拟实验计划学时：6 实验类型：（2）1、演示性2、验证性3、综合性4、设计性 每组实验的学生人数：2人 教学目的和要求： 1、通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟 存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程。 2、做图分析并比较各种算法的效率 实验方法（包括实验中需要注意的问题等）： 1、给出操作内容要求学生自己动手完成 2、注意程序的输入并分析运行结果 实验重点（主要解决的问题和达到的目的）： 1、存储管理常用页面置换算法模拟实验的实现过程 2、各种算法的效率分析与比较 实验难点（预计实验过程中会遇到的问题和解决方案）： 1、存储管理常用页面置换算法模拟实验的实现过程 2、实验结果的分析 教学方法（实验前的教学和实验过程中的指导方法）： 以学生自己查阅资料为主，教师辅导为辅。 实验仪器和材料： 计算机并安装有Red Hat Linux9.0操作系统。 实验报告要求和思考题： 认真填写实验报告并根据讲义完成思考题 参考资料： 《计算机操作系统教程（第3版）习题解答与实验指导》、清华大学出版社 软件学院 上机实验报告 课程名称：操作系统原理 实验项目：虚拟内存页面置换算法实验室：地狱018 姓名：死神学号： 专业班级：实验时间：2015/12/13 一、实验目的及要求 通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。结合Linux的内层的分析方法查看内存的分配过程及linux kernel的内存管理机制 二、实验性质 设计性 三、实验学时 4学时 四、实验环境 实验环境1.实验环境：C与C++程序设计学习与实验系统 2.知识准备： （1）使用Linux的基本命令； （2）了解Linux vmstat、free、top等命令查看linux系统的内存分配 情况； （3）掌握虚拟内存页面置换算法FIFO等基本算法理论。 五、实验内容及步骤 假设有n个进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。分别采用先来先服务FCFS和短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。 步骤 通过已知最小物理块数、页面个数、页面访问序列、及采用置换方式可以得出页面置换的缺页次数和缺页率，及每次缺页时物理块中存储。 1．输入的形式 int PageOrder[MaxNumber];//页面序列 int PageNum,LackNum=0,BlockNum;//页面个数，缺页次数，最小物理块数 2. 输出的形式 double LackPageRate//缺页率 缺页个数 每次缺页时物理块中存储 程序所能达到的功能 模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。 程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。 int PageOrder[MaxNumber];//页面序列 int PageCount[MaxNumber]={0};//计算内存内数据离下一次出现的距离 int PageNum,LackNum=0,BlockNum;//页面个数，缺页次数，最小物理块数 double LackPageRate=0; bool found=false; 操作系统实验报告6-页面置换算法模拟 实验报告 （ 2013 / 2014学年第1学期） 课程名称操作系统原理 实验名称实验6：页面置换算法模拟 实验时间2013 年12 月 10 日 指导单位软件工程系 指导教师杨健 学生姓名班级学号 学院(系) 软件工程系专业计算机软件与服务外包 //本?程ì序ò中D全?局?变?量?名?均ù由?两?个?单蹋?词洙?组哩?成é，?且ò开a头?字?母?大洙?写′int BlockSize = 5;//物?理え?块é大洙?小? int PageCount = 200;//页?面?总哩?数簓 int PageSize = 1024;//页?面?大洙?小? int AddrRange = 8*1024;//访?问ê地?址·范?围§ int get_num(int down,int up)//得?到?一?个?down~up之?间?的?整?数簓 { int num; char str[111]; while(1){ fgets(str,111*sizeof(int),stdin); num=atoi(str);//把?字?符?串?中D的?数簓字?转羇换?为a整?数簓 if(num>=down&& num<=up) break; printf("输?入?范?围§有瓺误ó,请?重?新?输?入?:"); }//while return num; } void init_block()//构1造ì一?个?空?的?物?理え?块é队ó列 { Block.rear=Block.front=(BlockNode*)malloc(sizeof(BlockNode)); if(!Block.front){ printf("内ú存?分?配?失骸?败悒?\n"); exit(0); } Block.length=0; Block.miss_count=0; 信息工程学院实验报告 课程名称：操作系统Array实验项目名称：请求页式存储管理中常用页面置换算法模拟实验时间： 班级姓名：学号： 一、实验目的: 1.了解内存分页管理策略 2.掌握调页策略 3.掌握一般常用的调度算法 4.学会各种存储分配算法的实现方法。 5.了解页面大小和内存实际容量对命中率的影响。 二、实验环境: PC机、windows2000 操作系统、VC++ 三、实验要求： 本实验要求4学时完成。 1.采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大 小及内存实际容量对命中率的影响； 2.实现OPT 算法 (最优置换算法) 、LRU 算法 (Least Recently) 、 FIFO 算法 (First IN First Out)的模拟； 3.会使用某种编程语言。 实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告，按时上交。 四、实验内容和步骤： 1.编写程序，实现请求页式存储管理中常用页面置换算法LRU算法的模拟。要求屏幕显示LRU算法 的性能分析表、缺页中断次数以及缺页率。 2.在上机环境中输入程序，调试，编译。 3.设计输入数据，写出程序的执行结果。 4.根据具体实验要求，填写好实验报告。 五、实验结果及分析： 实验结果截图如下： 利用一个特殊的栈来保存当前使用的各个页面的页面号。当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，栈底是最近最久未被使用的页面号。当访问第5个数据“5”时发生了缺页，此时1是最近最久未被访问的页，应将它置换出去。同理可得，调入队列为：1 2 3 4 5 6 7 1 3 2 0 5，缺页次数为12次，缺页率为80%。 六、实验心得： 本次实验实现了对请求页式存储管理中常用页面置换算法LRU算法的模拟。通过实验，我对内存分页管理策略有了更多的了解。 最近最久未使用（LRU）置换算法的替换规则：是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。 最佳置换算法的替换规则：其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。 先进先出(FIFO)页面置换算法的替换规则：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 三种替换算法的命中率由高到底排列OPT>LRU>FIFO。 本次的程序是在网上查找的相关代码然后自己进行修改，先自己仔细地研读了这段代码，在这过程中我对C++代码编写有了更深的了解。总之，本次实验使我明白要学会把课堂上的理论应用到实际操作中。我需要在今后熟练掌握课堂上的理论基础，只有坚实的基础，才能在实际操作中更得心应手。 附录： #include "" #include <> const int DataMax=100; const int BlockNum = 10; 存储管理 常用页面置换算法模拟实验 实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 实验内容 设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 1、最佳淘汰算法（OPT） 2、先进先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、最不经常使用算法（LFU） 5、最近未使用算法（NUR） 命中率＝１－页面失效次数／页地址流长度 实验准备 本实验的程序设计基本上按照实验内容进行。即首先用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 E：在后地址[m’+2，319]中随机选取一条指令并执行 F：重复步骤A-E，直到320次指令 （2）将指令序列变换为页地址流 设：页面大小为1K； 用户内存容量4页到32页； 用户虚存容量为32K。 在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第 0 条-第 9 条指令为第0页（对应虚存地址为[0，9]） 第10条-第19条指令为第1页（对应虚存地址为[10，19]） ……………………………… 第310条-第319条指令为第31页（对应虚存地址为[310，319]） 按以上方式，用户指令可组成32页。 实验指导 一、虚拟存储系统 UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。 当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU 操作系统实验报告 班级:计科0801班姓名：韩伟伟学号：08407106 时间：2018-5-25 实验五请求页式存储管理的页面置换算法 一．实验目的 通过请求页式存储管理中页面置换算法模拟程序，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。 二．实验属性 设计 三．实验内容 1.通过随机数产生一个指令序列，共320条指令，指令的地址按下述原则生产： 50％的指令是顺序执行的； 25％的指令是均匀分布在前地址部分； 25％的指令是均匀分布在后地址部分。 2.将指令序列变换成为页地址流 设页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。 在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条至第9条指令为第0页；第10条至19条指令为第1页；…第310条至319条指令为第31页。 3.计算并输出下述各种算法在不同内存容量下的命中率。 (1>先进先出算法 实验五虚拟内存页面置换算法 一、需求分析 (1) 1.输入的形式和输入值的范围 (2) 2.输出的形式 (2) 3.程序所能达到的功能 (3) 4.测试数据 (4) 二、概要设计 (5) 1.抽象数据类型的定义 (5) 2.主程序的流程 (6) 3.程序各模块之间的层次(调用)关系 (7) 三、详细设计 (7) 1.void FIFO() (7) 2.void OPI() (8) 3.void LRU() (10) 四、调试分析 (11) 1.发现的问题 (11) 2.算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复杂度的分析)及其改 进设想； (11) 3.解决方法 (11) 4.经验和体会 (12) 五、用户使用说明 (12) 六、测试结果 (12) 七．附录 (14) 一、需求分析 ●需求 在进程运行过程中，若其所访问的页面不在内存而需把它们调入内存，但内存已无 空闲空间时，为了保证该进程能正常运行，系统必须从内存调出一页程序或数据送 磁盘的对换区中。但应将哪个页面调出，需根据一定的算法来确定。通常，把选择 换出页面的算法称为页面置换算法。置换算法的好坏，将直接影响到系统的性能。 一个好的页面置换算法，应具有较低的更好频率。从理论上讲，应将那些以后不再 访问的页面换出，或把那些在较长时间内不再访问的页面调出。 ●实验目的 通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。 ●实验内容 设计程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次 数和缺页率。 程序要求 1）利用先进先出FIFO、最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。 2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。 3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,Pn，算法选择1-FIFO，2-OPI，3-LRU。 4）输出：每种算法的缺页次数和缺页率。 1.输入的形式和输入值的范围 从dos控制台界面按照输入提示输入数据（红色的数字即为输入的内容）： 物理块(LackNum)：3 页号数（PageNum）：20 页面序列(PageOrder)：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 进程的最大页号数为100，物理块、页面序列的值为int类型的范围。 2.输出的形式 输入数据后，按ENTER键就可在dos控制台界面得到结果。按照实验要求分别实验四页面置换算法代码
《操作系统》实验五页面置换算法模拟
实验5 页面置换算法
第7次 常用页面置换算法模拟实验
页面置换算法实验报告
操作系统页面置换算法模拟实验
页面置换算法实验(内含完整代码)
页面置换算法实验报告
实验五存储管理常用页面置换算法模拟实验
虚拟内存页面置换算法实验报告
操作系统实验报告6-页面置换算法模拟
请求页式存储管理中常用页面置换算法模拟
常用页面置换算法模拟实验
实验请求页式存储管理页面置换算法
实验五 虚拟内存页面置换算法
相关主题
文本预览