实验三第一个.doc

（三）院 系： 计算机科学学院 专 业： 软件工程 年 级： 08 课程名称： 操作系统 指导教师： 帖军 组 号： 十一组 学 号： 姓 名： 年 月 日年级专 业班级组号实验室日期实验名称实验三 虚拟内存管理实验内容分项内容实验级别1 局部性原理演示（数组清零）（操作系统观察级）2 页面置换算法模拟演示（算法仿真实现级）3 实际系统内存分配演示（Linux，Windows平台）（操作系统观察级）小 组 成 员姓名学号组内分工自我评分教师评分许莹莹08065032局部性原理演示（数组清零）胡飞08065012页面置换算法模拟演示梁必强08065030页面置换算法模拟演示谢劲08065058实际系统内存分配演示夏光佳08065054实际系统内存分配演示小组成绩评定教师签名： 年 月 日实验分项1、局部性原理演示（数组清零）（操作系统观察级）实验目的理解程序的局部性原理并演示实验要求具体题目：数组清零系统平台：linux实验原理步骤（算法流程）1、程序的局部性原理：指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。

相应地，执行所访问的存储空间也局限于某个内存区域局部性原理又表现为：时间局部性和空间局部性时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问空间局部性是指一旦程序访问了某个存储单元，则不久之后其附近的存储单元也将被访问另外，根据程序的局部性理论，Denning提出了工作集理论所谓工作集是指进程运行时被频繁访问的页面集合显然我们知道只要使程序的工作集全部集中在内存中，就可以大大减少进程的缺页次数；否则会使进程在运行过程中频繁出现缺页中断，从而出现频繁的页面调入/调出现象，造成系统性能的下降，甚至出现“抖动” 划分工作集可以按定长时间或定长页面两种方法进行划分当颠簸现象发生时，说明系统的负荷过大，通常采用处理器均衡调度另一种是控制缺页率，当缺页率达到上限时，则增加内存分配量；当缺页率达到下限时，就减少内存的分配量实验原理步骤（算法流程）2、程序对比分析for(i=0;i<1024;i++)for(j=0;j<1024;j++)test[j][i]=0;程序是按列把数组中的元素清“0”的，所以，每执行一次test[j][i]=0就会产生一次缺页中断。

因为开始时第一页已经在主存了，故程序执行时就可以对元素test[1][1]清零，但下一个元素test[2][1]不在该页，就产生缺页中断按程序上述的编制方法，每装入一页只对一个元素清零后就要产生缺页中断于是总共要产生1024*1024-1次缺页中断 for(i=0;i<1024;i++)for(j=0;j<1024;j++)test[i][j]=0;按行清零，每转入一页后就对一行元素全部清零后才产生缺页中断，故总共产生1024-1次缺页中断实验结果及分析实验结果：实验分析：按行清零用时0，而按列清零用时2000，验证了实验原理里面关于局部性原理的分析心得体会通过这次实验体会了程序局部性原理的巨大差别，在以后的编程过程中就会考虑的程序的效率问题对优化程序有很大的帮助实验分项2页面置换算法模拟演示实验目的通过本实验理解内存页面调度的机制，实现FIFO、LRU、NRU、OPT几种经典的页面置换算法的基础上，比较置换算法效率以及优缺点，从而了解虚拟存储实现的过程实验要求具体题目：页面置换算法模拟演示系统平台：linux实验原理步骤（算法流程）㈠ FIFO页面置换算法⑴原理简述①在分配内存页面数(AP)小于进程页面数(PP)时，当然是最先运行的AP个页面放入内存。

②这时有需要处理新的页面，则将原来内存中的AP个页面最先进入的调出(是以称为FIFO)，然后将新页面放入③以后如果再有新页面需要调入，则都按⑵的规则进行算法特点：所使用的内存页面构成一个队列⑵图表描述假设某个进程在硬盘上被划分为5个页面(PP=5)，以1、2、3、4、5分别表示，处理机调用它们的顺序(这取决于进程本身)为：1、4、2、5、3、3、2、4、2、5如果内存可以控制的页面数为3(AP=3)，那么在使用FIFO算法时，这3个页面的内存使用情况应该如下图所示：⑶算法实现提示要得到“命中率”，必然应该有一个常量total_instruction来记录页面总共使用的次数；此外还需要一个变量记录总共换入页面的次数(需要换出页面，总是因为缺页中断而产生)diseffect利用公式 可以得到命中率①初始化设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数，并产生一个的随机数序列main[total_instruction](这个序列由page[]的下标随机构成)表示待处理的进程页面顺序，diseffect置0②看main()中是否有下一个元素，若有，就由main[]中获取该页面下标，并转到③；如果没有就转到⑦。

③如果该page已在内存中，就转到②；否则就到④，同时未命中的diseffect加1④观察pagecontrol是否占满，如果占满须将使用队列(在第⑥步中建立的)中最先进入的(就是队列第一个单元)pagecontrol单元“清干净”，同时将对应的page[]单元置为“不在内存中”⑤将该page[]与pagecontrol[]建立关系(可以改变pagecontrol[]的标志位，也可以采用指针链接，总之至少要使对应的pagecontrol单元包含两个信息：一是它被使用了，二是哪个page[]单元使用的page[]单元也包含两个信息：对应的pagecontrol单元号和本page[]单元已在内存中)⑥将用到的pagecontrol置入使用队列(这里的队列是一种先进先出的数据结构了，而不是泛指导)，返回②⑦显示计算 的结果，完成㈡ LRU页面置换算法⑴原理算述①当分配内存页面数(AP)小于进程页面数(PP)时，当然是把最先执行的AP个页面放入内存②当需要调页面进入内存，而当前分配的内存页面全部不空闲时，选择将其中最长时间没有用到的那个页面调出，以空出内存来放置新调入的页面(称为LRU)算法特点：每个页面都有属性来表示有多长时间未被CPU使用的信息。

⑵图表描述为了便于比较，采用的例子和前面的一样某进程在硬盘上被划分为5个页面，用1、2、3、4、5表示，处理机处理它们的顺序为：1、4、2、5、3、3、2、4、2、5而内存可以控制的页面数为3(AP=3)，那么在使用LRU算法时，这三个页面的内存使用情况如下图所示：不难看出页面插入次数为7次，diseffect=7 ⑶算法实现提示与前述算法一样，只有先得到diseffect才能获得最终的“命中率”①初始化主要是进程页面page[]和分配的内存页面pagecontrol[]，同时产生随机序列main[]，diseffect置0②看序列main[]是否有下一个元素，如果有，就从main[]获取该page[]的下标，并转到③；如果没有就转到⑥③如果该page[]单元在内存中便改变页面属性，使它保留“最近使用”的信息，转到②；否则转到④，同时diseffect加1④判断是否有空闲的内存页面，如果有，就返回页面指针，转到⑤；否则，在内存页面中找出最长时间没有使用的页面，将其“清干净”，并返回该页面指针⑤在需要处理的page[]与④中得到的pagecontrol[]之间建立联系，同时让对应的page[]单元保存“最新使用”的信息，返回②。

⑥如果序列处理完成，就输出计算 的结果，并结束㈢ NUR页面置换算法⑴原理简述所谓“最近未使用”，首先是要对“近”作一个界定，比如CLEAR_PERIOD=50，便是指在CPU最近的50次进程页面处理工作中，都没有处理到的页面那么可能会有以下几种情况：①如果这样的页面只有一个，就将其换出，放入需要处理的新页面②如果有这样的页面不止一个，就在这些页面中任取一个换出(可以是下标最小的，或者是下标最大的)，放入需要处理的页面③如果没有一个这样的页面，就随意换出一个页面(可以是下标最小的，或者是下标最大的)算法特点：有一个循环周期，每到达这个周期，所有页面存放是否被CPU处理的信息的属性均被置于初始态(没有被访问)⑵图表描述还是用前面的例子，某进程在硬盘上被划分为5个页面，用1、2、3、4、5表示，而处理机处理它们的顺序为：1、4、2、5、3、3、2、4、2、5而内存可以控制的页面数为3(AP=3)，CLEAR_PERIOD取5；在循环周期内，如果所有内存页面均被CPU处理或者有多个页面未被CPU处理，取页码最小的页面换出算法实现过程如下图所示：显示页面交换共6次，diseffect=6⑶算法实现提示①初始化。

设置两个数组page[ap]和pagecontrol[pp]分别表示进程数和内存分配的页面数，并产生一个的随机数序列main[total_instruction](当然这个序列由page[]的下标随机构成)表示待处理的进程页面顺序，diseffect置0，设定循环周期CLEAR_PERIOD②看main[]是否有下一个元素若有，就从main[]中获取一个CPU将处理页面的序号；如果没有就转到⑧③如果待处理的页面在内存之中，就转到②；否则diseffect加1，并转到④④看是否有空闲的内存页面，如果有，返回空闲内存页面指针，并转到⑤；否则，在所有没有被访问且位于内存中的页面中按任意规则(或者取最近的一个页面；或者取下标最小的……)取出一个，返回清空后的内存页面指针⑤在待处理进程页面与内存页面之间建立联系，并标注该页被访问⑥如果CPU已处理了CLEAR_PEROD个页面，就将所有页面均设为“未访问”⑦返回②⑧如果CPU所有处。