置换算法讲解

‘壹’ 请简述什么是置换算法和替代算法，并分别给出置换算法和替代算法的实例

LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的。
LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是着名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。这就是LRU算法的全部内容。
这是一个相当好的算法，它是理想算法很好的近似。

‘贰’ 页面置换算法

  上文说到，请求分页管理方式中，当需要调入页面到内存中，但此时内存已满，就需要从内存中按照一定的置换算法决定将哪个页面取出将内存给调入的页面。本文将介绍几种页面置换算方法。
   本文内容

  算法思想：每次选择 淘汰的页面 将是 以后永不使用 ，或者 在最长时间内不再被访问的页面 ，这样可以保证最低的缺页率。
  举例说明，假设系统为进程分配了三个内存块，并考虑到有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

  ....按照此算法依次执行，最后的结果如下

  结果图

  注：缺页时未必发生页面置换，若还有可用的空闲内存空间就不用进行页面置换。
  最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此， 最佳置换算法是无法实现的 。

  算法思想：每次选择 淘汰的页面是最早进入内存的页面。
  该算法很简单，每次淘汰最在内存中待时间最久的各个，下面分别给出系统为进程分为配三个内存块和四个内存块的执行情况图。访问序列为3,2,1,0,3,2,4,3,2,1,0,4
  分配三个内存块的情况：

  分配四个内存块的情况：

  当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为 贝莱迪（Belay）异常 。
   只有FIFO算法会产生Belay异常。 另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此， 算法性能差。

  算法思想： 每次淘汰的页面是最近最久未使用的页面。
  实现方法：赋予每个页面对应的页表项中，用 访问字段记录该页面纯亏自上次被访问以来所经历的时间t。 当需要淘汰一个页面时，选择现有页面中t最大的页面，即最近最久未使用。

  举例说明，加入某系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
  这里先直接给出答案

  结果图

  最佳置换算法那性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。 时钟置换算法 是一种 性能和开销均春裤配平衡 的算法。又称 CLOCK算法 ，或 最近未用算法 （ NRU ，Not Recently Used）
   简单CLOCK算法 算法思想：为每个页面设置一个 访问位 ，再将内存中的页面都通过 链接指针链接成一个循环队列 。当某个页被访问时，其访问位置1.当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，暂不换出，将访问位改为0，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个扒指淘汰页面最多会经过 两轮扫描 ）。

  这个算法指针在扫描的过程就像时钟一样转圈，才被称为时钟置换算法。

  简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。 只有淘汰的页面被修改过时，才需要写回外存。
  因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。
  改进型时钟置换算法的 算法思想 ： 在其他在条件相同时，应该优先淘汰没有被修改过的页面， 从而来避免I/O操作。
  为了方便讨论，用（访问位，修改位）的形式表示各页面的状态。如（1,1）表示一个页面近期被访问过，且被修改过。
   算法规则 ：将所有可能被置换的页面排成一个循环队列

  由于第二轮已将所有的页的访问位都设为0，因此第三轮、第四轮扫描一定会选中一个页，因此 改进型CLOCK置换算法最多会进行四轮扫描。

  假设系统为进程分配了5个内存块，某时刻，各个页的状态如下图

  如果此时有新的页要进入内存，开始第一轮扫描就找到了要替换的页，即最下面的状态为（0,0）的页。

  某一时刻页面状态如下

  如果此时有新的页要进入内存，开始第一轮扫描就发现没有状态为（0，0）的页，第一轮扫描后不修改任何标志位。所以各个页状态和上图一样。
  然后开始第二轮扫描，尝试找到状态为（0,1）的页，并将扫描过后的页的访问位设为0，第二轮扫描找到了要替换的页。

  某一时刻页面状态如下

  第一轮扫描没有找到状态为（0,0）的页，且第一轮扫描不修改任何标志位，所以第一轮扫描后状态和上图一致。
  然后开始第二轮扫描，尝试找状态为（0,1）的页，也没有找到，第二轮扫描需要将访问位设为1，第二轮扫描后，状态为下图

  某一时刻页面状态如下

  具体的扫描过程和上面相同，这里只给出最后的结果，如下图

  所以，改进型的CLOCK置换算法最多需要四轮扫描确定要置换的页。从上面的分析可以看出，改进型的CLOCK置换算法
  (1) 第一优先级淘汰的是 最近没有访问且没有修改 的页面。
  (2) 第二优先级淘汰的是 最近没有访问但修改 的页面。
  (3) 第三优先级淘汰的是 最近访问但没有修改 的页面。
  (4) 第四优先级淘汰的是 最近访问且修改 的页面。

‘叁’ OPT页面置换算法最优性证明。

1常见的置换算法

1．最佳置换算法（OPT）（理想置换算法）：所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。2．先进先出置换算法（FIFO）：优先淘汰最早进入的页面，亦即在内存中驻留时间最久的页面。3．最近最久未使用（LRU）算法：选择最近最长时间未访问过的页面予以淘汰。4．Clock置换算法（LRU算法的近似实现）：给每一帧关联一个附加位，称为使用位。5．最少使用（LFU）置换算法6．工作集算法7 . 工作集时钟算法8. 老化算法（非常类似LRU的有效算法）9. NRU(最近未使用）算法10. 第二次机会算法2操作系统页面置换算法代码#include <stdio.h>^[1]#include <stdlib.h>#include <unistd.h> #define TRUE 1#define FALSE 0#define INVALID -1#define NUL 0#define total_instruction 320 /*指令流长*/#define total_vp 32 /*虚页长*/#define clear_period 50 /*清零周期*/typedef struct{ /*页面结构*/int pn,pfn,counter,time;}pl_type;pl_type pl[total_vp]; /*页面结构数组*/struct pfc_struct{ /*页面控制结构*/int pn,pfn;struct pfc_struct *next;};typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;int diseffect,a[total_instruction];int page[total_instruction], offset[total_instruction];void initialize(int);void FIFO(int);void LRU(int);void NUR(int);int main(){int S,i;srand((int)getpid());S=(int)rand()%390;for(i=0;i<total_instruction;i+=1) /*产生指令队列*/{a[i]=S; /*任选一指令访问点*/a[i+1]=a[i]+1; /*顺序执行一条指令*/a[i+2]=(int)rand()%390; /*执行前地址指令m’*/a[i+3]=a[i+2]+1; /*执行后地址指令*/S=(int)rand()%390;}for(i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/{page[i]=a[i]/10;offset[i]=a[i]%10;}for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/{printf("%2d page frames",i);FIFO(i);LRU(i);NUR(i);printf(" ");}return 0;}void FIFO(int total_pf) /*FIFO(First in First out)ALGORITHM*//*用户进程的内存页面数*/{int i;pfc_type *p, *t;initialize(total_pf); /*初始化相关页面控制用数据结构*/busypf_head=busypf_tail=NUL; /*忙页面队列头，对列尾链接*/for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID) /*页面失效*/{diseffect+=1; /*失效次数*/if(freepf_head==NUL) /*无空闲页面*/{p=busypf_head->next;pl[busypf_head->pn].pfn=INVALID; /*释放忙页面队列中的第一个页面*/freepf_head=busypf_head;freepf_head->next=NUL;busypf_head=p;}p=freepf_head->next; /*按方式调新页面入内存页面*/freepf_head->next=NUL;freepf_head->pn=page[i];pl[page[i]].pfn=freepf_head->pfn;if(busypf_tail==NUL)busypf_head=busypf_tail=freepf_head;else{busypf_tail->next=freepf_head;busypf_tail=freepf_head;}freepf_head=p;}}printf("FIFO:%6.4F",1-(float)diseffect/320);}void LRU(int total_pf){int min,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID) /*页面失效*/{diseffect++;if(freepf_head==NUL) /*无空闲页面*/{min=32767;for(j=0;j<total_vp;j++)if(min>pl[j].time&&pl[j].pfn!=INVALID){min=pl[j].time;minj=j;}freepf_head=&pfc[pl[minj].pfn];pl[minj].pfn=INVALID;pl[minj].time=-1;freepf_head->next=NUL;}pl[page[i]].pfn=freepf_head->pfn;pl[page[i]].time=present_time;freepf_head=freepf_head->next;}elsepl[page[i]].time=present_time;present_time++;}printf("LRU:%6.4f",1-(float)diseffect/320);}void NUR(int total_pf){int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID) /*页面失效*/{diseffect++;if(freepf_head==NUL) /*无空闲页面*/{cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)cont_flag=FALSE;else{dp++;if(dp==total_vp)dp=0;if(dp==old_dp)for(j=0;j<total_vp;j++)pl[j].counter=0;}freepf_head=&pfc[pl[dp].pfn];pl[dp].pfn=INVALID;freepf_head->next=NUL;}pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;}elsepl[page[i]].counter=1;if(i%clear_period==0)for(j=0;j<total_vp;j++)pl[j].counter=0;}printf("NUR:%6.4f",1-(float)diseffect/320);}void initialize(int total_pf) /*初始化相关数据结构*//*用户进程的内存页面数*/{int i;diseffect=0;for(i=0;i<total_vp;i++){pl[i].pn=i;pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/pl[i].counter=0;pl[i].time=-1; /*页面控制结构中的访问次数为0，时间为-1*/}for(i=1;i<total_pf;i++){pfc[i-1].next=&pfc[i];pfc[i-1].pfn=i-1;/*建立pfc[i-1]和pfc[i]之间的连接*/}pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1;freepf_head=&pfc[0]; /*页面队列的头指针为pfc[0]*/}/*说明：本程序在Linux的gcc下和c-free下编译运行通过*/【http://wenku..com/link?url=o_】
不知道能不能打开-是复制的 但也辛苦半天 忘采纳~