精华内容
下载资源
问答
  • 页面置换算法FIFO
    千次阅读
    2020-12-05 19:23:26

    先进先出置换算法(FIFO)

    最简单的页面置换算法,淘汰最先调入的。

    实现:队列

    依据: 先进入的可能已经使用完毕。

    基本思想:

    当需要淘汰一个页面时,总是选择驻留主存时间最长的页面进行淘汰,即先进入主存的页面先淘汰。

    理由:

    最早调入主存的页面不再被使用的可能性最大。 即优先淘汰最早进入内存的页面。(往前看

    说明:

    1. 该算法的出发点是最早调入内存的页面,其不再被访问的可能性会大一些。
    2. 该算法实现比较简单,对具有线性顺序访问的程序比较合适,而对其他情况效率不高。因为经常被访问的页面,往往在内存中停留最久,结果这些常用的页面却因变老而被淘汰。
    3. 先进先出算法存在一种 异常现象,即在某些情况下会出现分配给的进程物理块数增多,缺页次数有时增加,有时减少的奇怪现象,这种现象称为Belady现象
    物理页面232152453252
    物理块1222315243
    物理块233152435
    物理块31524352
    是否缺页

    缺页9次,总访问次数12次
    缺页率:9/12 = 75%

    更多相关内容
  • 这是一个自己完成软件工程的操作系统课程课程设计题目:此程序用于模拟虚拟磁盘页面置换算法,实现了FIFO页面置换算法和LRU页面置换算法,获得课程设计优秀的好成绩
  • 实验报告五 实验名称: 模拟页面置换算法 FIFOLRU 的实现 日期2015-12-9 班级13 级计科 一 实验目的 学号: 姓名 了解页面置换的概念理解页面置换的算法加深对页面置换算法的理解 二 实验内容 Java 编程语言实现 FIFO ...
  • 提供的是页面置换算法中最简单的先进先出策略的java代码实现
  • 该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法,包括先进先出(FIFO)、最佳置换算法(OPT)、最久最近未使用算法(LRU)。 具体实现功能有: 1、建立相应的数据结构 2、在屏幕上显示页面...
  • 操作系统调度方法中的先进先出页面置换算法
  • 操作系统_页面置换算法FIFO,OPT,LRU实现.pdf
  • 操作系统 页面置换算法FIFO,LRU

    FIFO

    FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。

    在这里插入图片描述

    LRU

    最近最久未使用(LRU)的页面置换算法是根据页面调入内存后的使用情况做出决策的,需要记录页面的访问时间。每当进程访问某页面时, 便将该页面的页面号从栈中移出,将它压入栈顶。因此,栈顶始终是最新被访问页面的编号,而栈底则是最近最久未使用页面的页面号。

    在这里插入图片描述

    代码实现

    #include<conio.h> 
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n") //表格控制
    #define bsize 4     //物理块大小
    #define psize 16     //进程大小
    typedef struct page{ 
           int num;  //记录页面号
           int time;  //记录调入内存时间
    }Page;                   //页面逻辑结构,结构为方便算法实现设计
    
    Page b[bsize];            //内存单元数 
    int c[bsize][psize];   //暂保存内存当前的状态:缓冲区
    int queue[100];      //记录调入队列
    int K;              //调入队列计数变量 
    int phb[bsize] = {0};   //物理块标号
    int pro[psize] = {0};     //进程序列号
    int flag[bsize] = {0};  //进程等待次数(存放最久未被使用的进程标志)
    int i = 0, j = 0, k = 0;   //i表示进程序列号,j表示物理块号
    int m = -1, n = -1;       //物理块空闲和进程是否相同判断标志
    int max = -1,maxflag = 0; //标记替换物理块进程下标
    int count = 0;            //统计页面缺页次数
    
    int* build(){
    	//随机产生序列号函数
    	printf("随机产生一个进程序列号为:\n");
    	int i = 0;
        for(i=0; i<psize; i++){
    		pro[i] = 10*rand()/(RAND_MAX+1)+1;
            printf("%d  ",pro[i]);
        }
        printf("\n");
    	return(pro);
    }
    
    int searchpb(){
    	//查找空闲物理块
    	for(j=0; j<bsize; j++){
    		if(phb[j] == 0){
               m = j; 
    		   return m;     
               break;
            }	
    	}
    	return -1;
    }
    
    int searchpro(){
    	//查找相同进程
    	for(j = 0; j < bsize; j++){
           if(phb[j] == pro[i]){
              n = j;
    		  return j;
           }
        }
    	return -1;
    }
     
    void empty(){
    	//初始化内存
    	for(i=0;i<bsize;i++){
    		phb[i]=0;
    	}
        count=0;                //计数器置零
    }
    
    void FIFO(){
       //先进先出页面置换算法
        for(i = 0; i<psize; i++){ 
    	   m=searchpb();
    	   n=searchpro();
            for(j = 0; j < bsize;j++){
            	//找flag值最大的
               if(flag[j]>maxflag){
                    maxflag = flag[j];
                    max = j;
                }
            }   
            if(n == -1){               
    			//不存在相同进程
               if(m != -1){            
               	   	//存在空闲物理块
    			   	phb[m] = pro[i];   //进程号填入该空闲物理块
    			   	count++;
                   	flag[m] = 0;
                   	for(j = 0;j <= m; j++){
                      	flag[j]++;
                   	}
                   	m = -1;
               }
               else{               
                  	//不存在空闲物理块
                	phb[max] = pro[i];
                  	flag[max] = 0;
                  	for(j = 0;j < bsize; j++){
                  		flag[j]++;
                  	}
                  	max = -1;
                  	maxflag = 0;
                  	count++;
               }
           }
           else{                    
    			//存在相同的进程
    		   	phb[n] = pro[i];
               	for(j = 0;j < bsize; j++){
    			   flag[j]++;
               	}
               	n = -1;
           }
           	for(j = 0 ;j < bsize; j++){
    		  	printf("%d  ",phb[j]);
           	}
           printf("\n");
        }
        printf("缺页次数为:%d\n",count);
    	printf("\n");
    }
    
    void Init(Page *b,int c[bsize][psize]){ 
     	//初始化内存单元、缓冲区
        int i,j; 
        for(i=0;i<psize;i++){ 
            b[i].num=-1; 
            b[i].time=psize-i-1; 
        } 
        for(i=0;i<bsize;i++) 
            for(j=0;j<psize;j++) 
                c[i][j]=-1; 
    } 
     
    int GetMax(Page *b){ 
     	//取得在内存中停留最久的页面,默认状态下为最早调入的页面
        int i; 
        int max=-1;
        int tag=0;
        for(i=0;i<bsize;i++){ 
            if(b[i].time>max){ 
                max=b[i].time; 
                tag=i; 
            } 
        } 
        return tag; 
    }
     
    int Equation(int fold,Page *b){ 
    	//判断页面是否已在内存中
        int i; 
        for(i=0;i<bsize;i++){ 
            if (fold==b[i].num) 
                return i; 
        } 
        return -1; 
    } 
    
    void Lruu(int fold,Page *b){ 
    	//LRU核心部分
        int i; 
        int val; 
        val=Equation(fold,b); 
        if (val>=0){ 
            b[val].time=0; 
            for(i=0;i<bsize;i++) 
                if (i!=val) 
                    b[i].time++; 
        } 
        else{
            queue[++K]=fold; //记录调入页面
            val=GetMax(b); 
        	b[val].num=fold; 
            b[val].time=0; 
            for(i=0;i<bsize;i++) 
                if (i!=val) 
                    b[i].time++; 
        } 
    }
     
    void LRU(){
        int i,j; 
        K=-1; 
        Init(b, c); 
        for(i=0;i<psize;i++){ 
            Lruu(pro[i],b); 
            c[0][i]=pro[i]; 
            //记录当前的内存单元中的页面
                for(j=0;j<bsize;j++) 
                    c[j][i]=b[j].num; 
        } 
        //结果输出 
        printf("内存状态为:\n"); 
        Myprintf; 
        for(j=0;j<psize;j++) 
        	printf("|%2d ",pro[j]); 
           	printf("|\n"); 
           	Myprintf; 
           	for(i=0;i<bsize;i++){ 
                for(j=0;j<psize;j++){ 
                  	if(c[i][j]==-1) 
                        printf("|%2c ",32); 
                  	else 
                        printf("|%2d ",c[i][j]); 
                } 
                printf("|\n"); 
           	} 
           	Myprintf; 
           	printf("\n调入队列为:"); 
           	for(i=0;i<K+1;i++) 
    		printf("%3d",queue[i]); 
           	printf("\n缺页次数为:%6d\n缺页率:%16.6f",K+1,(float)(K+1)/psize); 
    }
    
    int main()
    {
    	int sel;	
        do{	
        	printf("0、退出(Exit)\n");
        	printf("1、产生随机序列\n");
        	printf("2、最久未使用(LRU)\n");
        	printf("3、先进先出(FIFO)\n");
        	printf("<请选择所要执行的操作:(0)(1)(2)(3)>\n");
        	scanf("%d",&sel);
        	if(sel == 0){
        		printf("退出 \n");
    		}
    		if(sel == 1){
    			build();
    		}
    		if(sel == 2){
    			printf("LRU\n");
    			LRU();
    			empty();
    			printf("\n");
    		}
    		if(sel == 3){
    			printf("FIFO\n");
    			FIFO();
    			empty();
    			printf("\n");
    		}
    	}while(sel!=0);
    }
    

    效果图

    在这里插入图片描述
    先输入1,产生随机序列,模拟进程序号列
    在这里插入图片描述
    再输入2调用LRU
    在这里插入图片描述
    输入3调用FIFO
    在这里插入图片描述
    输入0退出

    展开全文
  • 页面置换算法FIFO算法

    2018-04-25 10:14:08
    最简单的页面置换算法是先入先出(FIFO)法。这种算法的实质是,总是选择在主存中停留时间最长(即最老)的一页置换,即先进入内存的页,先退出内存。理由是:最早调入内存的页,其不再被使用的可能性比刚调入内存的...
  • 页面置换算法 FIFO NUR LRU LFU.doc
  • 一个页面置换算法性能比较程序,包括了最佳置换,先进先出,LRU,随机置换,简单时钟和改进时钟六个算法。使用了队列,链表,循环链表等数据结构。随机产生请求页号,计算六种算法的缺页率。
  • 页面置换算法(java)

    2021-02-26 14:18:35
    在一个请求分页系统中,分别采用最佳置换算法、先进先出置换算法、最近最久未使用置换算法(LRU)时,假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理块数M分别为3和4时,试计算在...
  • (1)输入一个逻辑页面访问序列和随机产生逻辑页面访问序列,由四个线程同时完成每个算法; (2)能够设定驻留内存页面的个数、内存的存取时间、缺页中断的时间、快表...(7) 给出每种页面置换算法每个页面的存取时间;
  • 页面置换算法 fifo min lru clock second-chance五种算法。
  • 模拟页面置换算法FIFO、LRU的实现.pdf
  • 编程实现页面置换算法,最少实现两种算法,比较算法的优劣,并将调试结果显示在计算机屏幕上,检测机算和笔算的一致性。 (1)采用页式分配存储方案,通过分别计算不同算法的命中率来比较算法的优劣,同时也考虑页面...
  • 关于计算机操作系统页面置换算法FIFO、LRU、OPT的java描述、希望能在结构上提出改进建议。
  • 页面置换算法FIFO&LRU)

    万次阅读 多人点赞 2020-12-27 11:23:43
    编写程序实现:先进先出页面置换算法(FIFO)和最近最久未使用页面置换算法(LRU) 说明:(1)关于页面走向的页地址流可利用随机数产生一个序列,模拟该页地址流, 也可以手工键盘输入的方式或读取文件中的页地址流。(2)...

    页面置换算法

    实验目的

    1.通过模拟实现几种基本页面置换的算法,了解虚拟存储技术的特点。
    2.通过置换算法的模拟和比较,进一步了解它们的优缺点。
    3.锻炼知识的运用能力和实践能力

    实验要求

    编写程序实现:先进先出页面置换算法(FIFO)和最近最久未使用页面置换算法(LRU)
    说明:(1)关于页面走向的页地址流可利用随机数产生一个序列,模拟该页地址流,
    也可以手工键盘输入的方式或读取文件中的页地址流。(2)初始时,假定所有页面均
    不在内存。(3)计算并输出以上两种算法在分配不同内存物理块数时(讨论内存物理
    块数分配为3,4,5)的缺页率。(4)至少验证两组数据,即页地址流。

    实验内容概述

    首先,了解页面算法的功能。页面的算法的功能是当出现缺页异常且调入新页面而内存已满时,置换算法选择被置换的物理页面进行置换。因此对于如何科学地选取被置换的物理页面根据不同的页面置换算法不同而不同。

    其次,页面置换算法的设计目标是为了减少页面的调入调出次数,把未来不再访问或者短期内不访问的页面调出。常见的页面置换调度算法有先进先出页面置换算法(FIFO)、最近最久未使用页面置换算法(LRU)、最佳置换调度算法(OPT)、CLOCK置换算法等。

    本次实验针对FIFO和LRU两种算法进行详细分析和模拟实验,深刻理解页面调度算法原理。

    算法流程图

    总体流程:
    总体流程图FIFO流程:
    FIFO流程LRU流程图:
    LRU流程图

    程序代码

    #include <stdio.h>
    #define phy 100
    #define page 100//页面最大数
    #define phyBlock 100//物理块最大数
    //物理块的数量
    int phyBlockNum;
    //页面数量
    int pageNum;
    //保存页面号引用串
    int pageNumStrList[page];
    //初始化队列
    void initializeList(int list[], int number)
    {
        for (int i = 0; i < number; i++)
        {
            list[i] = -1;
        }
    }
    //展示队列状态
    void showList(int list[], int number)
    {
        for (int i = 0; i < number; i++)
        {
            printf("%2d", list[i]);
        }
        printf("\n");
    }
    
    //展示当前内存状态
    void showMemoryList(int list[], int phyBlockNum)
    {
        for (int i = 0; i < phyBlockNum; i++)
        {
            if (list[i] == -1)
            {
                break;
            }
            printf(" |%d|", list[i]);
        }
        printf("\n");
    }
    
    void informationCount(int missingCount, int replaceCount, int pageNum)
    {
        printf("***********结果展示***********\n");
        printf("缺页次数:%d\n", missingCount);
        printf("缺页率:%d/%d\n", missingCount, pageNum);
        double result = (double)(pageNum - missingCount) / (double)pageNum;
        printf("置换次数:%d\n", replaceCount);
        printf("******************************\n");
    }
    
    //找到该页面下次要访问的位置
    int getNextPosition(int currentPage, int currentPosition, int strList[], int pageNum)
    {
    
        for (int i = currentPosition + 1; i < pageNum; i++)
        {
            if (strList[i] == currentPage)
            {
                return i;
            }
        }
        return 100;
    }
    //先进先出置换算法
    void replacePageByFIFO(int memoryList[], int phyNum, int strList[], int pageNum) {
    
        //置换次数
        int replaceCount = 0;
        //缺页次数
        int missingCount = 0;
    
        //记录当前最早进入内存的下标
        int pointer = 0;
    
        //记录当前页面的访问情况: 0 未访问
        int isVisited = 0;
        for (int i = 0; i < pageNum; i++) {
            isVisited = 0;
    
            //判断是否需要置换->内存已满且需要访问的页面不在内存中
            for (int j = 0; j < phyNum; j++) {
                if (memoryList[j] == strList[i]) {
                    //该页面已经存在内存中
                    //修改访问情况
                    isVisited = 1;
                    //修改访问时间
                    //展示
                    printf("%d\n", strList[i]);
                    break;
                }
                if (memoryList[j] == -1) {
                    //页面不在内存中且内存未满->直接存入
                    memoryList[j] = strList[i];
                    //修改访问情况
                    isVisited = 1;
                    missingCount++;
                    //展示
                    printf("%d\n", strList[i]);
                    showMemoryList(memoryList, phyNum);
                    break;
                }
            }
    
            if (!isVisited) {
                //当前页面还未被访问过->需要进行页面置换
                //直接把这个页面存到所记录的下标中
                memoryList[pointer] = strList[i];
    
                //下标指向下一个
                pointer++;
    
                //如果到了最后一个,将下标归零
                if (pointer > phyNum - 1) {
                    pointer = 0;
                }
    
    
                missingCount++;
                replaceCount++;
    
                //展示
                printf("%d\n", strList[i]);
                showMemoryList(memoryList, phyNum);
            }
        }
        informationCount(missingCount, replaceCount, pageNum);
    }
    
    //最近最久未使用置换算法
    void replacePageByLRU(int memoryList[], int phyNum, int strList[], int pageNum) {
    
        //置换次数
        int replaceCount = 0;
        //缺页次数
        int missingCount = 0;
    
        //记录内存中最近一次访问至今的时间
        int timeRecord[phy];
        //初始化
        initializeList(timeRecord, phyNum);
    
        //记录当前页面的访问情况: 0 未访问
        int isVisited = 0;
    
        //记录已经在内存中的页面数量
        int pageCount = 0;
        for (int i = 0; i < pageNum; i++) {
            isVisited = 0;
    
            //时间加一
            for (int p = 0; p < pageCount; p++) {
                if (memoryList[p] != -1) {
                    timeRecord[p] ++;
                }
            }
    
            //是否需要置换
            for (int j = 0; j < phyNum; j++) {
                if (memoryList[j] != -1) {
                    timeRecord[j] ++;
                }
                if (memoryList[j] == strList[i]) {
                    //该页面已经存在内存中
                    //修改访问情况
                    isVisited = 1;
                    //重置访问时间
                    timeRecord[j] = -1;
                    //展示
                    printf("%d\n", strList[i]);
                    break;
                }
                if (memoryList[j] == -1) {
                    //页面不在内存中且内存未满->直接存入
                    memoryList[j] = strList[i];
                    pageCount++;
                    //修改访问情况
                    isVisited = 1;
                    //修改访问时间
                    timeRecord[j] ++;
    
                    missingCount++;
                    //展示
                    printf("%d\n", strList[i]);
                    showMemoryList(memoryList, phyNum);
                    break;
                }
            }
    
            if (!isVisited) {
                //需要置换
                //1.遍历时间记录表,寻找最久未访问的页面所在的内存下标
                int max = 0;
                for (int k = 0; k < phyNum; k++) {
                    if (timeRecord[max] < timeRecord[k]) {
                        max = k;
                    }
                }
    
                //2.将该位置的页面换出
                memoryList[max] = strList[i];
                timeRecord[max] = -1;
    
                missingCount++;
                replaceCount++;
    
                //展示
                printf("%d\n", strList[i]);
                showMemoryList(memoryList, phyNum);
    
            }
        }
        informationCount(missingCount, replaceCount, pageNum);
    }
    
    int main(int argc, const char* argv[])
    {
        printf("***********************************\n");
        printf("*            页面调度算法         *\n");
        printf("***********************************\n");
    
        printf("请输入物理块数量:\n");
        scanf("%d", &phyBlockNum);
        //生成内存队列
        int memoryList[phyBlock];
        //初始化内存状态
        initializeList(memoryList, phyBlockNum);
        //showMemoryList(memoryList,phyBlockNum);
        printf("请输入要访问的页面总数:\n");
        scanf("%d", &pageNum);
        printf("请输入要访问的页面号:\n");
        for (int i = 0; i < pageNum; i++) {
            scanf("%d", &pageNumStrList[i]);
        }
        printf("*******************************\n");
        showList(pageNumStrList, pageNum);
        printf("*******************************\n");
        int chose;
        while (1)
        {
            printf("请选择所需的置换算法(1.FIFO 2.LRU 3.退出):\n");
            scanf("%d", &chose);
            printf("*******************************\n");
            switch (chose)
            {
            case 1:
                showList(pageNumStrList, pageNum);
                printf("*******************************\n");
                replacePageByFIFO(memoryList, phyBlockNum, pageNumStrList, pageNum);
                //重新初始化内存
                initializeList(memoryList, phyBlockNum);
                break;
            case 2:
                showList(pageNumStrList, pageNum);
                printf("*******************************\n");
                replacePageByLRU(memoryList, phyBlockNum, pageNumStrList, pageNum);
                //重新初始化内存
                initializeList(memoryList, phyBlockNum);
                break;
            default:
                return 0;
                break;
            }
        }
        return 0;
    }
    

    实验结果截图

    • 测试数据1:物理内存块分别为{3,4,5},页面长度为20,页面地址流为{7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}

    数据输入截图:物理内存块为3
    数据输入
    FIFO结果:
    FIFO
    LRU结果:
    LRU后面结果读者就自己去实验啦。

    实验分析

    本次实验通过对两种页面置换算法即先进先出置换算法(FIFO)以及最近最久未使用算法(LRU)进行了实验模拟,为了保证程序能够正常运行,系统必须从内存中调出一页内存放在磁盘上,以便将所需要的页调入内存,该过程称为页面调度,通过对以上两种算法的模拟,从中我深刻理解了两种算法的深层原理。本次实验要求基本达到,实验结果达到预期效果,下面是本次实验的收获以及心得:

    物理内存块数量的增大可能使缺页率不降反增,这与该算法不考虑程序的动态特征有关;

    影响缺页率的因素不是单一的,主存页框数,页面大小,页面替换算法、程序特征均会影响缺页率;

    每种算法各有各的优缺点,例如FIFO算法简单,但通常缺页率较高,而LRU通常缺页率较FIFO低,但算法比较复杂,选择时各有取舍。

    展开全文
  • 页面置换算法,我们最常用的页面置换算法包括FIFO先来先服务,LRU最近最久未被使用,LFU最近最少被使用以及我们的时钟置换算法。 一、FIFO算法——先来先服务 1、简述FIFO算法 FIFO算法是我们比较简单的置换算法...

    页面置换算法,我们最常用的页面置换算法包括FIFO先来先服务,LRU最近最久未被使用,LFU最近最少被使用以及我们的时钟置换算法。

    一、FIFO算法——先来先服务

    1、简述FIFO算法

    FIFO算法是我们比较简单的置换算法,就是先来先服务或者说是先进先出。也就是说在进行页面置换的时候,最先来的那个会被最先置换出去。先进入的指令先完成并引退,跟着才执行第二条指令。

    2FIFO算法的简单实现

    FIFO算法的简单实现:可以通过维护一个链表结构去存储当前调入的页面;将最先进入的页面维护在链表的最前,最后进入的页面维护在链表的最后;这样,当发生缺页中断时,需要进行置换的时候,淘汰表头的页面并将新调入的页面加到链表的尾部;

             当然除了链表以外我们还可以采用数组或者队列等来进行实现。

    3、FIFO算法的特点

    (1)FIFO算法实现简单,易于理解易于编程。FIFO算法实现简单,无须硬件支持,只需要用循环数组管理物理块即可。

    (2)FIFO算法可能会出现Belady现象。也就是在FIFO算法中,如果未分配够一个进程所要求的页面,有时就会出现分配的页面数增多,却也率反而增加Belady现象。

    (3)FIFO算法可能会置换调重要的页面,其效率不高。

    (4)在FIFO算法可能中会导致多次的页面置换。当页面置换的时间大于所要操作的时间的时候,这时候其效率就会很低。当其不停的进行页面置换的时候会出现大量的系统抖动现象。

    二、LRU算法——最近最久未被使用

    1、简述LRU算法

    LRU算法是最近最久未被使用的一种置换算法。也就是说LRU是向前查看。在进行页面置换的时候,查找到当前最近最久未被使用的那个页面,将其剔除在内存中,并将新来的页面加载进来。

    2、LRU算法的实现

    LRU的实现就相对于FIFO的实现复杂一点。我们可以采用哈希映射和链表相结合。

    方法一:数组

    用一个数组来存储数据,给每一个数据项标记一个访问时间戳,每次插入新数据项的时候,先把数组中存在的数据项的时间戳自增,并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候,将被访问的数据项的时间戳置为0。当数组空间已满时,将时间戳最大的数据项淘汰。

    数组:查询比较快,但是对于增删来说是一个不是一个好的选择;

    方法二:链表

    利用一个链表来实现,每次新插入数据的时候将新数据插到链表的头部;每次缓存命中(即数据被访问),则将数据移到链表头部;那么当链表满的时候,就将链表尾部的数据丢弃。

    链表:查询比较慢,但是对于增删来说十分方便O(1)时间复杂度内搞定;

    方法三:hash+链表:保证了查询和增删的时间复杂度O(1)

    因此,我们具体介绍这种实现方法。

    具体过程描述:首先对于链表结构的描述,链表中包含我们的key,valueyu,以及我们的prev和pnext前驱和后继域。Hashmap我们用来作为一个检索表,它的检索时间复杂读最优可到O(1),也就是我们的get过程的时间复杂度可到O(1);那么,通过双向链表进行set的过程时间复杂度也可到O(1)。

    我们可以通过哈希映射快速检索到来的页面是否已经存在,如果已经存在的活,直接映射到我们的链表中,将链表中该节点从当前位置移除直接插入到链表的头部,这样就能保证链表的尾部是我们最近最久未被使用的页面;头部是我们最近刚使用过的页面。

    Get:是获取元素的操作;通过hashmap可以直接映射到链表中,查看是否有命中的元素,如果有,将元素从当前位置删除,并且再将其插入到首位置;如果没有,返回NULL;

    Set:是插入元素的操作;插入前先通过hashmap查看该元素是否存在,如果存在同上操作(先从该位置移除,再将其插入到链表首部);如果不存在即没有命中,将元素插入到链表的首部,同时判断容量是否达到最大,如果达到最大,将链表尾部元素进行删除;hashmap同样也要进行更新删除;

    (注意:每次进行删除和插入操作的时候都需要对hashmap表中的key数据进行调整;而value值保持不变,这样就能正确映射。)

    3、LRU算法的特点

    LRU是一种页面置换算法,在对于内存中但是又不用的数据块,叫做LRU,操作系统会根据那些数据属于LRU而将其移出内存而腾出空间来加载另外的数据;

    如果进程被调度,该进程需要使用的外存页(数据)不存在于数据块中,这个现象就叫做缺页。如果这个数据此时不在,就会将这个数据重新加入到数据块首部。

    数据块插入与剔除:每次有新数据到来时,会将其放入数据块首部,当数据每次被访问时,会将其放入数据块首部,当数据每次被访问时,将这个数据插入数据块的首部;如果数据块满了,每次新进的数据都会将数据块尾部的数据挤出数据块。

    三、LFU算法——最近最少未被使用

    1、LFU算法简述

    LFU是最近最少未被使用。也就是说当页面满时,需要进行页面置换的时候,所采取的措施是在缓存队列中找到最近使用次数最少的页面,将其剔除出去。将新的页面加载到页面缓存队列中。也就是说在LFU中,需要记录每个页面被访问的次数。

    如上图所示,在内存缓冲满的时候,2的访问次数是最少的,所以此时进行页面置换的时候,就将2置换出去,加载新来的页面。

    2、LFU的实现方式

    方法一:hashmap(存储数据项在数组中的对应关系)+数组(存储数据项+对应的引用计数)

    为了能够淘汰最少使用的数据,因此LFU算法最简单的一种设计思路就是:利用一个数组存储数据项,用hashmap存储每个数据项在数组中对应的位置,然后为每个数据项设计一个访问频次,当数据项被命中时,访问频次自增,在淘汰的时候淘汰访问 频次最少的数据。这样一来的话,在插入数据和访问数据的时候都能达到O(1)的时间复杂度,在淘汰数据的时候,通过选择算法得到应该淘汰的数据项在数组中的索引,并将该索引位置的内容替换为新来的数据内容即可,这样的话,淘汰数据的操作时间复杂度为O(n)。

    方法二:hashmap+小顶堆

    小顶堆是利用页面的访问次数进行构建;每次最少的访问次数的页面在小顶堆的堆根;利用hashmap进行映射,插入和删除的操作都是O(logN);

    方法三:二级哈希映射

    往后会继续补充

    展开全文
  • 操作系统第六次上机 在一个请求分页系统中设页面大小占100个单元假如系统分配给一个作业的物理块数为3试求出用FIFOLRUOPT三种算法在程序访问过程中所发生的缺页次数及缺页率每次中断时都需要打印出来或者标示出来...
  • 连续输入页面的逻辑地址,以“-1”作为结束标志,采用FIFO页面置换算法、固定分配局部置换分配策略。输出该页面的页号和页内位移,若该页不在内存,并且还有剩余的物理块,将该页调入内存,输出“该页不在内存中,...
  • 文章目录页面置换算法前言一、最近未使用页面置换算法二、先进先出页面置换算法三、第二次机会页面置换算法四、时钟页面置换算法四、最近最少使用页面置换算法四、最不常用算法总结 前言 当发生缺页中断时,操作...
  • 1.动态输入进入内存的页面总数,系统分配的物理块数,依次进入内存的页面号。...当内存中存在新页面号时不作任何调动,一直进行直至用户输入的页面号全部执行完毕,最后输出置换的次数,以及置换率。
  • 页面置换算法 FIFO,OPT,LRU

    千次阅读 2016-05-25 14:53:45
    ////LRU页面置换算法,将帧内最近不常使用的置换出 #include #include #include #include using namespace std; int returnMaxValueInVec(vectorstr) { int postion = 0; int length = str.size(); if (str.size...
  • 页面置换算法FIFO,LRU,OPT)

    千次阅读 2018-01-19 20:41:48
    1.先进先出置换算法(FIFO):是最简单的页面置换算法。这种算法的基本思想是:当需要淘汰一个页面时,总是选择驻留主存时间最长的页面进行淘汰,即先进入主存的页面先淘汰。其理由是:最早调入主存的页面不再被使用...
  • 通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。
  • 页面置换算法--FIFO(操作系统)

    千次阅读 2020-12-28 13:43:20
    页面置换算法FIFO 先初始化页面大小,和物理块数。连续输入页面的逻辑地址,以“-1”作为结束标志,采用FIFO页面置换算法、固定分配局部置换分配策略。输出该页面的页号和页内位移,若该页不在内存,并且还有剩余...
  • 缓冲池是数据库最终的概念,数据库可以将一部分数据页放在内存中形成缓冲池,当需要一个数据页时,首先检查内存中的缓冲池是否有这个页面,如果有则直接命中返回,没有则从磁盘中读取这一页,然后缓存到内存并返回。...
  • 页面置换算法fifo

    2010-01-12 10:36:34
    用c语言模拟实现操作系统中的页面置换算法——先进先出算法
  • FIFO 先进先出页面置换算法 根据作业序列判断置换,先进先置换的原则。 实现过程: 用vector简单模拟这个过程,不用直接queue模拟,是因为,当判断是否需要置换的时候,queue不好判断在队列中是否存在这个数。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,402
精华内容 2,960
关键字:

页面置换算法FIFO