精华内容
下载资源
问答
  • 置换算法OPT,FIFO,LRU

    2020-10-28 15:42:24
    随机给出一个页面执行序列,如:1,5,3,4,2,1,3,4,5,7,9,……。要求计算以下几种置换算法的...最佳置换算法OPT(Optimal) 先进先出算法FIFO(First In First Out) 最近最少使用算法LRU(Least Recently Used)
  • 操作系统:页面置换算法OPT算法实验(C语言)

    千次阅读 多人点赞 2020-11-23 11:21:40
    已知页面访问序列,采用OPT页面置换算法,求缺页次数、页面置换次数和缺页率。 实验目的: 通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理中几种基本...

    实验题目:

    OPT算法实验

    实验内容:

    已知页面访问序列,采用OPT页面置换算法,求缺页次数、页面置换次数和缺页率。

    实验目的:

    通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。

    实验原理:问题分析及算法设计(流程图)

    在这里插入图片描述

    实验源代码:

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <math.h>
    #include <limits.h>
    
    int toNextPageLen[50];//当前页面位置下一次被访问的位置,下标为当前页面位置,值为下一次访问位置 
    //OPT算法 
    void OPT(int page_access[],int PBC,int PAC,int result[][50]){
    	int k = 0;
    	int nextPageAccessIndex[50];//存储当前页面的位置,作为该页面上一次被访问的下一次访问位置 ,下标为页面,值为下一次访问位置 
    	memset(nextPageAccessIndex,0,sizeof(nextPageAccessIndex));//初始化为0,代表没再访问过 
    	//1.获取当前位置页面下次访问该页面的位置 
    	for(int i = PAC-1; i>=0; i--){
    		int nextIndex = nextPageAccessIndex[page_access[i]]; 
    		if(nextIndex <= 0){//没在访问过则位置设为无穷 
    			toNextPageLen[i] = INT_MAX;
    		}else{
    			toNextPageLen[i] =  nextIndex;
    		}
    		nextPageAccessIndex[page_access[i]] = i;
    	}
    	
    	//2.计算每一次访问的每个物理块存放的当前页面 
    	int flagBlock[50];//存储页面是否在物理块中,用于去重,下标为页面,值为访问位置 
    	memset(flagBlock,-1,sizeof(flagBlock));//不存在物理块中为-1 
    	for(int i = 0 ; i < PAC; i++){//遍历访问位置 
    		int len = 0;//存储下一次访问该页的最大长度 
    		int block = -1;//要替换的物理块中页面 
    		
    		if(flagBlock[page_access[i]]!=-1){//如果存在物理块中,直接复制前一次数据 
    			for(int j = 0; j < k; j++){
    				result[j][i] = result[j][i-1];
    			}
    			flagBlock[page_access[i]] = i; 
    			continue;
    		}
    		for(int j = 0; j < PBC; j++){//遍历物理块 
    			if(k < PBC){//如果当前使用的物理块数少于总共物理块数,复制上一次访问页面,在剩下的物理块中添加当前页面 
    				if(j == k){//如果为新的物理块,直接存储当前页面 
    					result[k][i] = page_access[i];//存储当前页面 
    					flagBlock[page_access[i]] = i;// 标记为存在物理块中 
    					k++; //使用的物理块数+1
    					result[PBC][i] = 1;  //判断是否缺页,有增加则缺页 
    					break;
    				}else{//复制上一次的页面 
    					result[j][i] = result[j][i-1];
    				}
    			}else{//如果物理块满 
    				result[j][i] = result[j][i-1];//复制上一次页面 
    				int s = toNextPageLen[flagBlock[result[j][i-1]]]-i;
    			
    				if(len < s){//找到下次访问最长页面替换 ,即判断物理块中页面 上次的下标 的下一次访问位置减去当前位置,得到距离长度 
    					block = j;
    					len = s;
    				}
    			}
    		}
    		if(block!=-1){
    			flagBlock[result[block][i]] = -1;
    			flagBlock[page_access[i]] = i;
    			result[block][i] = page_access[i];//替换下次访问最长的页面 
    			result[PBC][i] = 1;
    		}
    	}
    }
    int main(){
    	int PBC;//物理块数 physical block count 
    	int PAC;//页面访问次数 Page access count 
    	int page_access[50];//存储访问的页面,下标代表第几次访问 
    	int result[50][50];//0~PBC-1行0~PAC-1列代表每个物理块存储每次访问的页面,PBC行存储是否缺页,是为1,否为0 
    	memset(result, -1, sizeof(result)); 
    	printf("请输入物理块数:"); 
    	scanf("%d",&PBC);
    	printf("请输入访问次数:"); 
    	scanf("%d",&PAC);
    	for(int i = 0 ; i < PAC; i++){
    		printf("请输入第%d次访问的页面:",i+1);
    		scanf("%d",&page_access[i]); 
    	}
    	
    	//OPT 
    	OPT(page_access, PBC, PAC, result);
    	
    	//输出 
    	printf("\n\n页面访问\t");
    	for(int i = 0 ; i < PAC; i++){
    		printf("%d\t",page_access[i]);
    	}
    	printf("\n");
    	for(int i = 0; i < PBC; i++){
    		printf("物理块%d\t\t",i+1);
    		for(int j = 0; j < PAC; j++){
    			if(result[i][j]!=-1&&result[PBC][j]!=-1){
    				printf("%d\t",result[i][j]);
    			}else{
    				printf("\t");
    			}
    		}
    		printf("\n");
    	}
    	int lack_page_number = 0;//缺页次数 
    	printf("是否缺页\t");
    	for(int i = 0; i < PAC; i++){
    		printf("%c\t",result[PBC][i]==1?'Y':'N');
    		if(result[PBC][i]==1)lack_page_number++;
    	} 
    	printf("\n"); 
    	
    	int exchange_numbber = lack_page_number - PBC;
    	double lack_page_rate = lack_page_number/(double)PAC;
    	printf("缺页次数: %d\n", lack_page_number);
    	printf("置换次数: %d\n",exchange_numbber);
    	printf("缺页率: %0.2lf%%\n",lack_page_rate) ;
    
    }
    /*
    3
    12
    2
    3
    2
    1
    5
    2
    4
    5
    3
    2 
    5 
    2
    
    3
    20
    7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
    */
    

    实验结果:(截图)

    在这里插入图片描述

    实验总结:(心得体会)

    通过此次实验,我熟练掌握了几种页面置换算法,自己独立写出了OPT算法的代码实现,对虚拟存储技术的特点有了更深的了解。

    展开全文
  • 页面置换算法OPT,FIFO,LRU,LFU

    千次阅读 多人点赞 2019-12-13 22:42:55
    1.背景 进程运行时,若其访问的页面不在内存而需将其调入,但内存已无空闲空间时,就需要从内存中调出一页程序或数据,送入磁盘的对换区。 选择调出页面的算法就称为页面置换...最佳(Optimal, OPT)置换算法所选...

    1.背景

    进程运行时,若其访问的页面不在内存而需将其调入,但内存已无空闲空间时,就需要从内存中调出一页程序或数据,送入磁盘的对换区。

    选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率,也就是说,应将以后不会再访问或者以后较长时间内不会再访问的页面先调出。

     

    2.置换策略理论

     

     1. 最佳置换算法(OPT)

    最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的,因而该算法无法实现。

     2. 先进先出(FIFO)页面置换算法

    优先淘汰最早进入内存的页面,亦即在内存中驻留时间最久的页面。该算法实现简单,只需把调入内存的页面根据先后次序链接成队列,设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应,因为在进程中,有的页面经常被访问。

     3. 最近最久未使用(LRU)置换算法

    选择最近最长时间未访问过的页面予以淘汰,它认为过去一段时间内未访问过的页面,在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段,来记录页面自上次被访问以来所经历的时间,淘汰页面时选择现有页面中值最大的予以淘汰。

    3.策论比较

    1. FIFO,Optimal,LRU这三种置换算法的优劣?

    •优点:

        ① FIFO页面置换算法实现简单,要求的硬件支持较少。

        ② Optimal页面置换算法可保证获得最低的缺页率,并且可以用来评价其他算法。

        ③ LRU页面置换算法利用“最近的过去”代替“最近的将来”,以此模拟Optimal算法,是实际应用中缺页率最低的算法。

     

    •缺点:

        ① FIFO算法所依据的条件是各个页面调入内存的时间,而页面调入内存的先后并不能反映页面的使用情况。

        ② Optimal算法是理论上的算法,目前该算法是无法实现的。

        ③LRU算法是根据各页以前的使用情况,来代替各页面将来的使用情况,进而判断要替换出去的页面,而页面过去和将来的         走向之间并无必然的联系;其实际应用时要求较多的硬件支持,因而多采用近似算法。

     

    2. 在什么情况下采用哪种置换算法更有利?

        •FIFO算法在按线性顺序访问地址空间时使用;当硬件水平不足时,FIFO算法也可作为首选。

        •OPT算法可以进行模拟实验分析或理论分析。

        •当系统有寄存器或栈的硬件支持时,利用LRU算法可以获得最低缺页率。

     

    各个csdn太多类似的解释,就我自己百度的来看,关于OPT这个算法的解释模型基本上都是错误的。PS:可能有对的。

    以下是我浅薄的解释:

     

       在弄清楚这些个页面置换算法之前要先弄清楚两个概念:

    1:缺页(也称缺页中断)

    这是百度百科的解释:

    这是我的解释(大家随便看看)

    缺页:就是指按照访问顺序去访问“页面”时,但发现物理内存中并没有(对应的“页面‘号’”),所以发生了缺页中断:需要调入内存之后才可以继续运行。

    2:页面置换:(页面置换算法)

    百度百科:

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

    简单来说就是就是替换页面

     

    好在了解上面之后在来说今天的重点:

    1:OPT:最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率. 

     

     

    自我小结论:空物理块情况下:页面置换=缺页减-物理块数(一开始就要缺页3次)。

    这个是:网络上一个博客跟我的结论是一样的

    https://www.cnblogs.com/ctrltab/p/10013815.html

    最佳置换算法(optimal replacement,OPT)是从内存中选择今后不再访问的页面或者在最长一段时间后才需要访问的页面进行淘汰。如下例子:

    根据页面走向依次处理,得到最终的置换结果如下图表,整个页面缺页次数为7,缺页率为7/12=58%。

     

     

    https://blog.csdn.net/qq_34777600/article/details/79508613

    这个csdn给的列子是错误的(opt)

     

    2:先进先出(FIFO)页面置换算法

    优先淘汰最早进入内存的页面,亦即在内存中驻留时间最久的页面。

     

     

     

     

    结论:1:FIFO的页面置换刚好是OPT的一倍(相同的情况和访问顺序下)

              2::空物理块情况下:页面置换=缺页减-物理块数(一开始就要缺页3次)。

     

     

     3. 最近最久未使用(LRU)置换算法

    选择最近最长时间未访问过的页面予以淘汰,它认为过去一段时间内未访问过的页面,在最近的将来可能也不会被访问

     

     

     

    结论:

    1:原始方法是 加一个t(时间戳)来记录上次访问后到现在所经历的时间,需要淘汰时,选择t最大的那个淘汰。

    2:ava8以后实现了hashmap+双向link链表实现了。、

     

     

    链接如下: http://www.imooc.com/article/details/id/285117

    https://www.cnblogs.com/hongdada/p/10406902.html

     

     

    扩展:

    4:LFU 最少使用置换算法:

                LFU算法的访问图与LRU算法的访问图是一样的

     

    最少使用(LFU)置换算法

    在采用最少使用置换算法时,应为在内存中的每个页面设置一个移位寄存器,用来记录该页面被访问的频率。该置换算法选择在之前时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度,例如100 ns,在1 ms时间内可能对某页面连续访问成千上万次,因此,通常不能直接利用计数器来记录某页被访问的次数,而是采用移位寄存器方式。每次访问某页时,便将该移位寄存器的最高位置1,再每隔一定时间(例如100 ns)右移一次。这样,在最近一段时间使用最少的页面将是∑Ri最小的页。LFU置换算法的页面访问图与LRU置换算法的访问图完全相同;或者说,利用这样一套硬件既可实现LRU算法,又可实现LFU算法。应该指出,LFU算法并不能真正反映出页面的使用情况,因为在每一时间间隔内,只是用寄存器的一位来记录页的使用情况,因此,访问一次和访问10 000次是等效的。 [3]

    1,基本原理

    LFU(Least Frequently Used)算法根据数据的历史访问频率来淘汰数据,其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高”。

    LFU的每个数据块都有一个引用计数,所有数据块按照引用计数排序,具有相同引用计数的数据块则按照时间排序。

     

    具体实现如下:

     

     

     

     

    1. 新加入数据插入到队列尾部(因为引用计数为1);

    2. 队列中的数据被访问后,引用计数增加,队列重新排序;

    3. 当需要淘汰数据时,将已经排序的列表最后的数据块删除。

     

    展开全文
  • 操作系统 页面置换算法 OPT(最佳置换算法) 郑州大学 大作业
  • 最佳置换算法OPT

    千次阅读 2018-12-04 09:41:00
    原文链接:https://www.jianshu.com/p/544ee20e307c 转载于:https://www.cnblogs.com/qy-blogs/p/10062309.html

    原文链接:https://www.jianshu.com/p/544ee20e307c

    转载于:https://www.cnblogs.com/qy-blogs/p/10062309.html

    展开全文
  • 带有界面的算法,视自己需求下载。 主界面选择使用三种算法的一个。在创建中输入页面数,随机生成页面。在指定物理块中实现置换。点击查看将置换的过程显示出来。
  • 页面置换算法OPT+FIFO+LRU+clock

    热门讨论 2012-12-31 12:06:40
    C语言 页面置换算法 OPT FIFO LRU clock
  • 该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法,包括先进先出(FIFO)、最佳置换算法OPT)、最久最近未使用算法(LRU)。 具体实现功能有: 1、建立相应的数据结构 2、在屏幕上显示页面的...
  • OPT最佳页面置换算法

    2013-12-19 10:12:29
    OPT算法的C语言实现,希望对你们有帮助!
  • 最佳置换OPT页面置换算法的源代码,以及可执行程序。
  • 该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法,包括先进先出(FIFO)、最佳置换算法OPT)、最久最近未使用算法(LRU)。 具体实现功能有: 1、建立相应的数据结构 2、在屏幕上显示页面...
  • 最佳置换算法OPT

    2021-05-24 23:07:37
    这是一种理想情况下的页面置换算法,但实际上是不可能实现的。该算法的基本思想是:发生缺页时,有些页面在内存中,其中有一页将很快被访问(也包含紧接着的下一条指令的那页),而其他页面则可能要到10、100或者...

    这是一种理想情况下的页面置换算法,但实际上是不可能实现的。该算法的基本思想是:发生缺页时,有些页面在内存中,其中有一页将很快被访问(也包含紧接着的下一条指令的那页),而其他页面则可能要到10、100或者1000条指令后才会被访问,每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定:标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。当缺页发生时,操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现,但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。

    展开全文
  • 页面置换算法OPT,FIFO,LRU)

    万次阅读 多人点赞 2019-01-05 16:24:39
    页面置换算法 地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面...最佳置换算法OPT) 理想置换算...
  • c语言编写页面置换算法OPT FIFO LRU的模拟程序。 源代码: #include <stdio.h> #define number 20 #define block 3 int opt(int a[]) { int i,j,zero=0,one=0,two=0,q=0; int b[block]; for(i=0;i<block...
  • 包括了操作系统页面置换算法,其中有OPT,FIFO,LRU,CLOCK,改进型的CLOCK算法
  • C语言模拟OS虚拟内存页面置换算法OPT+FIFO+LRU

    千次阅读 多人点赞 2020-05-29 22:41:15
    这就是页面置换算法。 最佳(Optimal)置换算法,选择的淘汰页将是以后永久不使用的,或许是在最长时间内不再访问的页面。这种算法可以保证最低的缺页率,但该算法真实情况下无法实现,可以作为评价其他算法的标准。 ...
  • 1、了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。 2、了解程序设计技术和内存泄露的原因 二、实验内容 1、模拟实现请求页式存储管理的几种...
  • 自己写的 希望有错提出来 期中那个OPT写的不是很好,希望可以多多指教
  • 全面的页面置换算法opt、fifo、lru、clock),很全。
  • 页面置换算法OPT算法

    千次阅读 2020-12-05 18:49:41
    最佳置换算法OPT)(理想置换算法) 最佳置换算法是由 Belady 于1966年提出的一种理论上的算法。其所选择的被淘汰页面,将是以后永不使用的, 或许是在最长(未来)时间内不再被访问的页面。 采用最佳置换算法,通常...
  • 操作系统页面置换算法之最优置换(OPT)算法

    万次阅读 多人点赞 2016-08-03 17:03:43
     最优置换算法OPT)是指,其所选择的被淘汰页面,将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法,通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的...
  • 最佳(OPT)置换算法 #include <iostream> int accessPage[20] = { 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 }; int flagOPT[3] = { -1,-1,-1 }; // 用来在OPT算法中标记三个物理块是否有页面;-1:物理...
  • 文章目录前言知识总览最佳置换算法OPT)先进先出置换算法(FIFO)最近最久未使用置换算法(LRU)时钟置换算法(CLOCK)改进型的时钟置换算法知识回顾与重要考点 前言 此篇文章是我在B站学习时所做的笔记,大部分图片...
  • 自己写的页面置换算法。期中OPT算法写的不好,请有选择参考
  • 1.最佳置换算法OPT)(理想置换算法) 从主存中移出永远不再需要的页面;如无这样的页面存在,则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,...
  • OPT页面置换算法1

    千次阅读 2019-06-09 17:31:47
    OPT页面置换算法1 OPT简单/简陋/算法实现 对于页面置换计数有待改进 当要调入一页而必须淘汰旧页时,应该淘汰以后不再访问的页,或距现在最长时间后要访问的页面。它所产生的缺页数最少,然而,却需要预测程序的页面...
  • 操作系统实验报告 页面置换算法模拟 OFTFIFO 和 LRU算法 班级 2013 级软件工程 1 班 学号 X X X 姓名萧氏一郎 实用标准文案 数据结构说明 Memery[10] 物理块中的页码 Page[100] 页面号引用串 Temp[100][10] 辅助数组...
  • 操作系统之三种页面置换算法(OPT,FIFO,LRU)--Java实现

    千次阅读 多人点赞 2020-12-03 16:25:37
    页面置换算法有三种:分别是最佳置换算法、先进先出置换算法、最近最久未使用置换算法 其中最好的是最佳置换算法,但最佳置换算法只是个理想化模型,缺页率最高的是先进先出置换算法。 最佳置换算法的原理:每次从...
  • 页面置换算法 - OPT - FIFO - LRU

    千次阅读 2017-06-21 16:58:10
    1.最佳置换算法OPT(Optimal Replacement Algorithm)又称理想淘汰算法、最佳页面算法等。其基本思想是:总选择那些以后不再需要的或将来最长时间之后才会用到的页面进行淘汰。例:设系统为某进程分配3个物理块,...
  • 操作系统页面置换算法模拟实现,fifo、lfu、lru、opt,界面由MFC实现

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,931
精华内容 1,972
关键字:

置换算法opt