OPT最佳页面置换算法

⑴ 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_】
不知道能不能打开-是复制的 但也辛苦半天 忘采纳~

⑵ 页面置换算法有哪些

页面置换算法包括先进先出（FIFO）、最近最久未使用（LRU）、最不常用（LFU）、时钟（Clock）以及理想（OPT）算法。
1. 先进先出（FIFO）算法
该算法的基本原则是先进入内存的页面先被置换。当内存空间不足时，系统会选择最早进入内存的页面进行置换。FIFO算法的优势在于实现简单，但其缺点在于未能考虑页面的实际使用频率和重要性，可能导致不必要的性能损耗。
2. 最近最久未使用（LRU）算法
LRU算法依据页面的历史访问记录来进行页面置换。它倾向于将最长时间未被访问的页面置换出内存。为了有效地追踪页面访问顺序，LRU算法通常需要使用特殊的数据结构，如链表或栈。尽管LRU算法在理论上较为合理，但其实现复杂度较高，且需要额外的存储空间来维护访问顺序。
3. 最不常用（LFU）算法
LFU算法是基于页面访问频率的置换策略。它认为访问频率低的页面在未来也较少会被访问，因此将这些页面置换出内存。LFU算法需要跟踪每个页面的访问频率，并进行相应的排序。然而，LFU算法可能会导致一些频繁访问的页面被过早置换，影响系统性能。
4. 时钟（Clock）算法
Clock算法是基于FIFO的一种改进。它使用一个时钟指针来遍历页面队列，并根据特定的标记位（如访问位或修改位）来决定置换页面。当新页面需要加载时，时钟指针继续移动，直到找到一个标记位为0的页面进行置换。Clock算法的优势在于其实现相对简单且效率较高。
5. 理想（OPT）算法
理想算法是一个理论上的最优页面置换算法，它能够准确预测未来的页面访问模式，并据此选择最长时间内不会被访问的页面进行置换。然而，由于实际中无法准确预测访问模式，OPT算法在现实中无法完美实现。

⑶ 页面置换算法常见的置换算法

页面置换算法在计算机内存管理中扮演重要角色，用于解决内存与处理器之间的数据交换问题。其中，不同算法各有其特点与适用场景。

最佳置换算法（OPT）旨在选择未来永不访问或最久不访问的页面淘汰，以此降低缺页率，实现内存资源的高效利用。

先进先出置换算法（FIFO）遵循“先入先出”原则，淘汰最早进入内存的页面。该算法简单直观，但可能因预测不准确而产生较多缺页现象。

最近最久未使用（LRU）算法基于页面的访问历史，淘汰最近最久未访问的页面，以确保频繁访问的页面得到优先访问机会。

Clock置换算法（LRU算法的近似实现）通过为每帧关联使用位，动态模拟LRU算法的淘汰策略，实现对最近未使用的页面的高效淘汰。

最少使用（LFU）置换算法关注页面的访问频率，淘汰访问次数最少的页面，旨在平衡页面访问频率与内存使用效率。

工作集算法考虑程序运行时的页面使用情况，通过工作集的大小预测页面需求，实现更合理的页面置换。

工作集时钟算法结合Clock置换算法与工作集概念，优化内存管理策略，提升算法效能。

老化算法（类似LRU的有效算法）通过跟踪页面的访问情况，对页面进行“老化”处理，淘汰访问频率较低的页面，以优化内存使用。

NRU（最近未使用）算法追踪页面的使用情况，优先淘汰长时间未被访问的页面，减少缺页现象。

第二次机会算法在页面置换策略中引入二次淘汰机会，对被淘汰页面进行评估，若发现有较高访问频率，可将其重新加入内存，减少因错误预测带来的缺页成本。

在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法

⑷ 操作系统题：页面置换算法 OPT FIFO LRU

fifo就是先进先出，可以想象成队列
lru是最久未使用，当需要替换页面的时候，向前面看，最久没使用的那个被替换
opt是替换页面的时候，优先替换后面最迟出现的。
不懂再问。。

⑸ 最佳置换算法最后一个怎么办

最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面;如无这样的页面存在,则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。 最佳置换算法可以用来评价其他算法。