《虚拟存储技术中页面置换算法的研究》6700字

虚拟存储技术中页面置换算法的研究目录TOC\o"1-2"\h\u17721摘要： 123358引言 1166771.课题研究的目的与意义 2285431.1课题研究的目的 2318551.2课题研究的意义 294902.相关知识介绍 2139542.1请求分页系统 2130822.2内存和缓存 3291312.3页面置换算法 37043.页面置换算法的分析与设计 4269983.1页面置换算法的分析 498563.2页面置换算法的设计 1087184.页面置换算法的实现 11176144.1主要模块实现 11215044.2部分运行结果 14227904.3页面置换算法的优缺点及优化 1710066总结 171221参考文献 18摘要：随着人工智能和大数据技术的迅猛发展，虚拟存储技术大大提高了操作系统的性能，页面置换算法作为虚拟存储技术的重要组成成分，它的优劣直接影响操作系统的整体性能。本文归纳整理了关于请求分页系统的内容，重点对页面置换原理进行了深入的研究，根据基本原理设计并实现了页面置换算法，并对算法进行比较。在实际应用中，应根据具体的条件和环境，选择适用的页面置换算法，充分考虑算法的适配性。关键词：请求分页系统；页面置换算法；最佳置换算法；先进先出算法；LRU置换算法；Clock置换算法引言缺页中断是进程运行过程中，要查看的页不在内存分配的页框里。当发生缺页中断时，操作系统就会利用合适的页面置换算法将内存中的某一符合条件的页面调出，将要访问的页面调入内存。页面置换算法的作用就是，选择一个不常用、以后也不会用到的页面调出内存，会使操作系统的性能好很多，减少不必要的开销。总而言之，页面置换算法便是将内存中不用的页面给置换成需要访问的或即将要访问的，以节省内存。页面置换算法的优劣直接影响虚拟存储系统的性能，进而影响整个操作系统的性能。课题研究的目的与意义1.1课题研究的目的到目前为止，尽管前辈们已经对页面置换算法有了相当深入的认识与研究，并且成为教科书中的经典章节，但是仍然具有继续深入研究的价值。就本文而言，通过研究几个经典的页面置换算法的思想、具体实现和优缺点，可以更加深刻的了解操作系统中页面置换思想，掌握实现流程，及它的特性。同时，基于对页面置换算法的深入了解对算法可以做一些改进去优化它。1.2课题研究的意义在请求分页系统中页面置换算法具有重要的研究意义。第一，当某一程序在运行时，程序要访问的所有页面不是同一时间全部装入内存的，而是操作系统给进程分配一些物理块，只有一部分页面可以直接调入内存，占用这些物理块，当物理块用完时，要访问的页面不在内存时，就需要用到页面置换算法选出某一合适页面，将需要访问的页面和选出的页面进行页面对换。第二，页面置换算法作为虚拟存储的重要组成部分，对页面置换算法的进一步优化，也是对操作系统性能的提升。第三，对页面置换算法的优化需要建立在经典页面置换算法的基础之上。2.相关知识介绍2.1请求分页系统请求分页系统是建立在基本分页存储系统的基础上的。请求调页功能和页面置换功能是请求分页系统的两大特色功能，无需将所有页面调入内存，只需装入一部分就可以运行，实现了小内存运行大作业；在作业运行之前只装入当前需要的一部分页面，便让作业开始运行。在作业运行过程中，如果出现要访问的页面不在内存中，就由硬件产生缺页中断，然后请求操作系统将所缺页面调入内存[1]。2.2内存和缓存计算机程序都是在内存中运行的，在运行程序的时候，内存需要从磁盘中读取程序[2]。所有的计算工作都需要在CPU中进行，读取内存，然后进行计算。内存的读写速度非常快，磁盘的读写速度很慢。为了达到提高程序运行速度、减少运行时间的目的，这就需要减少对磁盘读写。为了提高计算机性能，所以执行过程中的中间结果会保存在内存中，当CPU需要该结果时，从内存中直接读取，这种机制被称为缓存机制[3]。2.3页面置换算法在请求分页系统中，当所访问的页面不存在内存中产生缺页中断，便需要调入页面到内存中，但如果此时内存已经满了，这需要按照一定的页面置换算法，从内存中调出某一页面，将内存空间让给要调入的页面。页面置换算法的好坏直接影响系统的性能，一个好的页面置换算法会带来较少的缺页中断次数和页面对换次数[4]。从理论上讲，应该将以后不会再访问的页面调出内存，或把那些较长时间里不会再访问的页面调出内存。图SEQ图\*ARABIC1页面置换流程图3.页面置换算法的分析与设计3.1页面置换算法的分析3.1.1最佳置换算法最佳置换算法[5]的基本原理是：将不再访问或最远的将来才会需要的页面调出内存。但由于人们无法预测将来会发生的事情，所以该算法无法实现。但由于最佳页面置换算法可以保证最低的缺页中断次数，现主要用于评价其他的页面置换算法的优劣。例如：配给某进程的内存页框数为3页，页面地址流如下：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1。程序运行过程中，第一次访问到2号页面时，系统分配的三个页框已经被占用，此时发生缺页中断，按照最佳页面置换算法，应将7号页面置换出内存，应为7号页面在之后不会再访问。访问到3号页面时，此时占用页框的是2、0、1号页面，其中1号页面在较长时间不会被访问，因此将1号与3号页面进行对换。具体的内存动态分配过程如下表所示：表SEQ表\*ARABIC1最佳置换算法内存动态分配表70120304230321201777222222222222220000004440000000111333333331111其中，产生了8次缺页中断，5次页面置换，缺页率为47.06%。3.1.2先进先出置换算法FIFO先进先出页面置换算法[6]的基本原理是：每当需要将内存中的页面调出内存时，就将最早调入内存的页面调出，也就是在内存中滞留最久的页面。通俗的理解就是排队的思想，按照来的先后顺序排队，当出现缺页中断，且队满了，队头出队。例如：配给某进程的内存页框数为3页，页面地址流如下：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1。在程序运行过程中，第一次访问到2号页面时，此时系统分配的三个页框均被占用，发生缺页中断，根据先进先出页面置换算法的思想，将队头元素7号页面调出内存，将2号页面调入内存，添加到队尾。具体的内存动态分配过程如下表所示：表2先进先出置换算法内存动态分配表170120304230321201777001230422230000011230423330111122304230001222其中，产生了12次缺页中断，9次页面置换，缺页率为70.59%。当系统分配给该进程的页框数增加至4页时，具体的内存动态分配过程如下表所示：表3先进先出置换算法内存动态分配表27012030423032120177777001112223444000011222333400011122333444011122334440001222其中，产生了9次缺页中断，5次页面置换，缺页率为52.94%。当系统分配页框数为3，页面地址流为：4,3,2,1,4,3,5,4,3,2,1,5时，具体的内存分配过程如下表所示：表4先进先出置换算法内存动态分配表3432143543215444111555555333444442222223333311其中，产生了9次缺页中断，6次页面置换，缺页率为75%。当系统分配给该进程的页框数增加至4页时，具体的内存动态分配过程如下表所示：表5先进先出置换算法内存动态分配表4432143543215444444555511333333444452222223333111111222其中，产生了10缺页中断，6次页面置换，缺页率为83.33%。产生了比莱迪异常，页框数的增加没有解决缺页次数过多的问题。3.1.3最近最久未使用置换算法最近最久未使用页面置换算法[7]的基本原理是：根据当前页框中的页面访问情况来预测以后的使用情况，当出现缺页中断，页框已被占完，需要置换页面时，将最长时间没有被使用的页面占用的页框让给要访问的页面。根据程序的局部性原理[8]，在过去的一段时间里不经常被访问的页面，在将来被访问的可能性也很小。例如：配给某进程的内存页框数为3页，页面地址流如下：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1。在程序运行时，运用栈的思想，这样最近访问的页面在栈顶，最近最久未使用的页面在栈底，这样在发生页面置换时，将栈底元素调出内存，将调入内存的新页面放在栈顶即可。当第一次访问2号页面时，将栈底的7号页面调出内存，将2号页面调入内存，放在栈顶。接着访问到0号页面时，因为0号页面处于栈中，所以将其上元素均下移，0号页面放于栈顶。具体的内存动态分配过程如下表所示：表6最近最久未使用置换算法内存动态分配表170120304230321201701203042303212017012030423032120701223042203312其中，产生了11次缺页中断，8次页面置换，缺页率为64.71%。当系统分配给该进程的页框数增加至4页时，具体的内存动态分配过程如下表所示：表7最近最久未使用页面置换算法内存动态分配表27012030423032120170120304230321201701203042303212070122304220331277112304440033其中，产生了7次缺页中断，3次页面置换，缺页率为41.18%。3.1.4最近最不常用置换算法LFU最近最不常用页面置换算法[9]的基本原理是：在最近一段时间里，经常被访问的页面与不经常被访问的页面相比，更可能在不远的将来被访问，所以将最近一段时间里被访问次数最少的页面调出内存。由于内存的访问速度较高，所以不能直接利用软件计数来记录某页的访问次数。例如：配给某进程的内存页面数为3页，页面地址流如下：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1。在程序运行过程中，需要设置一个很长的计数器，记录在特定时间段里每页的访问次数，每过一个特定时间，就需要将计数器清零。当访问次数相同时，优先淘汰最先调入内存的页面。当第一次访问页面2时，出现缺页中断，当前占用页框的页面7、0、1的访问次数均为1，7号页面为最先调入内存的页面，将7号页面与2号页面进行页面对换。具体的内存动态分配过程如下表所示：表8最近最不常用置换算法内存动态分配表70120304230321201777222244333333310000000000000000111333222221222其中，产生了9次缺页中断，6次页面置换，缺页率为52.94%。3.1.5Clock置换算法Clock页面置换算法[10]的基本原理是：将页框中的页构成一个循环链表，将指针指向最早调入主存的页。产生缺页中断时，先检测指针当前所指的页，如果它的访问位为0，将该页调出主存，将所缺页调入该位置，指针向后移动一个位置；如果它的访问位为1，则将其置为0，指针向后移动，直到找到第一个访问位为0的页面。但由于该页调入主存可能被修改过，调出主存时要相应地修改置换区和相应的文件。如下图所示，当需要进行页面置换时，开始遍历循环链表，将1号页面的访问位置为0，再将5号页面的访问位置为0，由于10号页面的访问位为0，所以将10号页面调出内存，将新的页面放在该位置上，访问位置为1。图SEQ图\*ARABIC2Clock页面置换算法3.1.6改进的时钟算法改进的时钟算法[11]的基本原理是：为了解决按照Clock算法将调入主存后被修改过的页面调出主存，从而增加系统开销的问题，为页表增加了修改位。所有页的访问位和修改位开始时都设置为0。每次将页调入主存时，该页的访问位置为1；如果调入主存同时又被修改，该页的修改位置为1。按照访问位和修改位的值，所有页面可以分为四类：a类：最近未访问过，未修改，该页值为00；b类：最近未访问过，已修改，该页值为01；c类：最近访问过，未修改，该页值为10；d类：最近访问过，已修改，该页值为11。表9页面状态类别访问位修改位描述A类00最近未访问过，未修改B类01最近未访问过，已修改C类10最近访问过，未修改D类11最近访问过，已修改改进的时钟算法与Clock算法一样，将页框内的页面构成一个时钟一样的环，初始时，指针指向调入主存最早的页。当产生缺页中断时，扫描循环链表，检查当前指向的页属于哪一类表，来确定淘汰页。优先淘汰a类页面，其次b类c类、d类。如下图所示，当出现缺页中断，需要页面置换时，将1号页面的访问位置为0，指针遍历到3号页面置，符合A类条件，将3号页面调出内存，将新的页面调入内存，访问位置为1，修改位置为1。图SEQ图\*ARABIC3改进的Clock页面置换算法3.2页面置换算法的设计（1）开发平台页面置换算法实现的平台为：联想笔记本个人电脑；window10操作系统；C++语言；codeblocks等开发工具；（2）设计思想为模拟进程访问页面过程而设计了一个yemianzhihuan()函数，提供五种页面置换算法供用户选择。在这个函数中包含输入页框数n代表系统分配的物理块，页面地址流大小m代表该进程访问所有页面的次数，然后申请一个大小为m的linklist型的结构体数组L[m]，输入m对数据L[i].data（页码号）、L[i].modified（修改位）代表访问页的信息。然后让用户选择要使用的算法，如若选择LRU，则调用LRU()函数，输出使用FIFO的内存动态分配过程；若选择让系统输出缺页率最低的算法，则调用choosebest()函数，输出使用最优缺页率的算法的内存动态分配过程。4.页面置换算法的实现4.1主要模块实现现介绍两种较为有特点的页面置换算法的代码实现。LRU置换算法需要同时考虑进入缓存的时间和被访问的情况，所以它的实现简单来说是将最新访问和最新调入的页面放在队头，当发生缺页中断时，将队列中的最后一个页面调出主存。核心代码如下表所示：表10LRU核心代码LRU核心代码：linklista[n];intnum=0,sum=0;//num为页框占用数sum为缺页次数for(inti=0;i<m;i++){//m为页面地址流大小if(num<n){//页框数没用完intflag=1;//记录该页是否存在内存for(intj=0;j<num;j++){if(a[j].data==L[i].data){//该页存在于内存中flag=0;}}if(flag){//该页不在内存中for(intk=num;k>0;k--)a[k].data=a[k-1].data;//队列元素后移a[0].data=L[i].data;//新页插入队头num++;//占用页框数增加sum++;//缺页次数增加}}else{//页框数已用完intflag=1,t=0;//记录该页是否存在内存for(intj=0;j<n;j++){if(a[j].data==L[i].data){//已存在内存中flag=0;t=j;//记录该页所在位置，它之前的页面要后移}}if(flag){//该页不在内存for(intk=n-1;k>0;k--)a[k].data=a[k-1].data;//队尾元素出队a[0].data=L[i].data;//新页放到队头sum++;//缺页次数增加}else{//已在内存中for(;t>0;t--){a[t].data=a[t-1].data;}a[0].data=L[i].data;//将该页放到队头}}}returnsum;Clock算法的实现需要一个循环链表，使用一个指针指向调入主存最早的页面，出现缺页中断时，开始遍历链表中的页面，将访问位为0的调出主存，将新的页面插入。遍历过程中，访问位为1的，则清除为0。核心代码如下表所示：表SEQ表\*ARABIC2CLOCK核心代码CLOCK核心代码：linklista[n];intnum=0,sum=0,flag=n-1;//num页框数sum缺页次数flag指针位置for(inti=0;i<m;i++){if(num<n){//页框没用完 intflag1=1;//记录访问页的是否在内存中for(intj=0;j<num;j++){if(a[j].data==L[i].data){a[j].used=1;//在内存中，访问位置为1flag1=0;}}if(flag1){//不在内存中 a[num].data=L[i].data;//直接加入队尾，访问位置为1 a[num].used=1; num++;sum++;//已用页框数增加，缺页次数增加 }}else{ intflag1=1; intj=flag;//当前指针位置 intw=0;//记录是否查看一圈 while(flag1&&w<n){//找到该页结束，找完一遍也结束 j=(j+1)%n;//循环指针跳转 if(a[j].data==L[i].data){//已在内存中 a[j].used=1;//访问位置为1 flag1=0; } w++; } flag=j;//当前指针位置 if(flag1){//不在内存中 intk=flag;//指针位置 while(flag1){//找到置换页跳出循环 k=(k+1)%n;//从下一页开始 if(a[k].used==0){//找到第一个访问位为0的置换出内存 a[k].data=L[i].data;//发生页面对换 a[k].used=1; flag1=0; sum++; } else{//遍历到的每一页将访问位置为0 a[k].used=0; } } flag=k;//记录指针当前位置 } }}returnsum;4.2部分运行结果假如系统分配页框数为5，有一进程访问页码的顺序为：11,30,20,51,20,31,20,21,60,80,101,70,10,111,61,90,110,51；用户若选择LRU，则运行结果如下图4所示，若选择改进后的CLOCK，则运行结果如图5所示。图SEQ图\*ARABIC4LRU运行结果图SEQ图\*ARABIC5改进的CLOCK运行结果4.3页面置换算法的优缺点及优化FIFO是最直观的一个算法，实现简单，但是性能最差，实际应用少。LRU考虑到了程序访问的时间局部性，一般具有较好的性能，实际应用多，但会增加硬件成本，需要较多的硬件支持。LFU不能直接利用软件计数，采用寄存器机制也并不能准确反应页面最近一段时间的访问次数。Clock算法只有一个访问位来表示该页是否已被访问，发生置换时仅是将最近未用的页面置换出内存。改进的Clock与Clock相比，增加了修改位，发生缺页中断时需要综合考虑访问位和修改位。在LRU的基础上，发展了一些优化的算法，如工