1、最近最久未使用置换算法LRU是根据页面调入内存后的使用情况进行决策的，它是利用“最近的过去”作为“最近的将来”的近似，选择最近最久未使用的页面予以淘汰。
2、最佳淘汰算法OPT：也称最佳置换算法。它所选择的被淘汰的页面，将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。
#include"stdio.h" #include"malloc.h" /*或#include"alloc.h"*/ #define N 16 #define num 5 /*进程分配物理块数目*/ int A[N]={1,2,3,4,5,6,7,8,5,2,3,2,7,8,1,4}; /*页面号引用串*/ typedef struct page { int address; /*页面号*/ struct page *next; }page; struct page *head,*run,*rear; void jccreat() /*给进程分配物理块，初始时内存物理块为空，以后运行时调入*/ { int i=1; page *p,*q; head=(page *)malloc(sizeof(page)); p=head; for(i=1;i<=num;i++) {q=(page *)malloc(sizeof(page)); p->next=q; q->address=0; q->next=NULL; p=q; } rear=p;} int search(int n) /*在分配的内存物理块中查找n号页面*/ { page *p; int i=0; p=head; while(p->next) { if(p->next->address==n) { printf("Get it at the page %d\n",i+1); run=p; return 1;} /*找到，返回1*/ p=p->next; i++; } return 0; /*未找到，返回0*/ } void changeOPT(int n,int position) /*OPT页面置换算法*/ { //定义需要的变量； //先查找空闲物理块，若找到，flag=0；否则，flag=1 //若flag=0，直接把要访问的页装入找到的空闲物理块 //若flag=1，计算内存中每个页面要访问的“距离” //选择“距离”最远的，换入。 int i,flag; int total=0; int distance[num]; int MAX; int order=0; page *p,*q; p=head->next; q=head->next; for(i=0;i<num;i++) { distance[i]=100; } i=0; while(p)//判断链表是否填满 { if(p->address==-1) { flag=0; break; } p=p->next; i++; } if(!flag)//链表没有填满 { p->address=n; printf("Change the page %d\n",i+1); } else//链表填满啦 { while(q)//计算距离 { for(i=position+1;i<N;i++) { if(q->address==A[i]) { distance[total]=i-position; break; } } total++; q=q->next; } MAX=distance[0]; for(i=0;i<num;i++) { if(distance[i]>MAX) { MAX=distance[i]; order=i;//记录要替换的页面的位置 } } printf("Change the page %d\n",order+1); i=0; p=head->next; while(p)//页面替换 { if(i==order) { p->address=n; } i++; p=p->next; } } } void changeLRU(int n) /*LRU页面置换算法*/ { //查找空闲物理块，若找到，直接调入； //如果内存没有空闲物理块，选择链表的第一个物理块，进行置换。 int i=0; int flag=1; page *p,*delect; p=head->next; while(p) { if(p->address==0) { flag=0; p->address=n; printf("Change the page %d\n",i+1); break; } p=p->next; i++; } if(flag) { delect=head->next; head->next=delect->next; printf("Delete from the head,and add new to the end.\n"); delect->address=n; rear->next=delect; rear=delect; rear->next=NULL; } } float OPT() /*求OPT页面置换算法的命中率*/ { int i; int lose=0; float losef; float percent; for(i=0;i<N;i++) { if(search(A[i])==0) { lose++; changeOPT(A[i],i); } } losef=lose; percent=1-(losef/N); return percent; } float LRU() /*求LRU页面置换算法的命中率*/ { int i; int lose=0; float losef;/*缺页率*/ float percent;/*命中率*/ page *p; for(i=0;i<N;i++) { if(search(A[i])==0) { lose++; changeLRU(A[i]); } else { p=run->next; run->next=p->next; rear->next=p; rear=p; rear->next=NULL; printf("Move it to end of queue.\n"); } } losef=lose; percent=1-(losef/N); return percent; } void main() /*主函数部分*/ {float percent; int choice; printf("Select the arithmetic:\n(1)OPT\n(2)LRU\nyour choice is:"); scanf("%d",&choice);/*选择页面置换算法*/ jccreat(); /*创建进程物理块链表*/ if(choice==1) /*采用OPT算法置换*/ {percent=OPT(); /*计算OPT时的命中率*/ printf("The percent of OPT is %f\n",percent);} else if(choice==2) /*采用LRU算法置换*/ {percent=LRU(); /*计算LRU时的命中率*/ printf("The percent of LRU is %f\n",percent);} else printf("Your choice is invalid."); //getch(); }