精华内容
下载资源
问答
  • fifo页面置换算法
    千次阅读
    2019-11-22 23:42:17

    先进先出(FIFO)页面置换算法: 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面,按先后次序存入一个时间数组,并将其中时间值最大的页面进行淘汰,并替换入新的页面就可以实现。

    这里取了个巧,用到了循环单链表结构
    在替换时,确保指针old指向的总是将要被替换的;
    因为要FIFO替换的总是先进来的,而且后续就算命中也不会因此改变置换顺序
    所以一开始old就是指向第一个结点即最先装载的页面,只有当没有命中时才替换当前页面,并且old = old->next;一直循环,直到所有待访问页面执行完;
    check用来遍历查找是否命中,命中无操作,否则替换,并且old=old->next;

    #include <stdio.h>
    #include <stdlib.h>
    #define maxpagenum 100
    typedef struct page
    {
        int pagenum;
        struct page *next;
    }Page;
    int FIFO(Page *block,int pages[maxpagenum],int pagenum,int blocknum)
    {
        int i = 0,j = 0;
        int time = 0;
        Page *old = block,*check = NULL;
        while(i<pagenum){
            check = block;
            j = 0;
            while(j < blocknum){
                if(pages[i]==check->pagenum)// 命中
                    break;
                check = check->next;
                j++;
            }
            if(j == blocknum){//没有命中,替换
                old->pagenum = pages[i];
                old = old->next;
                time += 1; //缺页次数+1
            }
            i++;
        }
        return time;
    }
    Page* creatblock(int blocknum)
    {
        int i;
        Page *head = NULL,*cur = NULL,*tail = NULL;
        for(i = 0;i < blocknum;i++){
            if(!head){
                cur = (Page*)malloc(sizeof(Page));
                cur->pagenum = -1;
                cur->next = NULL;
                head = tail = cur;
            }
            else{
                cur = (Page*)malloc(sizeof(Page));
                cur->pagenum = -1;
                tail->next = cur;
                tail = cur;
            }
        }
        tail->next = head;
        return head;
    }
    int main()
    {
        int time;
        int pages[maxpagenum];
        int i,blocknum,pagenum;
        Page *head=NULL;
        printf("请输入块号:\n");
        scanf("%d",&blocknum);
        head = creatblock(blocknum);
        printf("请输入待访问的页面数量:\n");
        scanf("%d",&pagenum);
        printf("请输入待访问的页面号:\n");
        for(i=0;i<pagenum;i++){
            scanf("%d",&pages[i]);
        }
        time = FIFO(head,pages,pagenum,blocknum);
        printf("缺页次数:%d,中断率:%.2f%%\n",time,time*1.0/pagenum*100);
        return 0;
    }
    
    更多相关内容
  • FIFO页面置换算法宣贯.pdf
  • 课外实践报告 项 目 名 称 所 在 班 级 姓名 小 组 成 员 页面置换算法 学号 组长 指 导 教 师 成 绩 评 定 支丽平 页面置换算法中的先进先出算法 一 实验目的 了解最佳页面置换算法与先进先出 FIFO 页面置换算法并...
  • 这是一个自己完成软件工程的操作系统课程课程设计题目:此程序用于模拟虚拟磁盘页面置换算法,实现了FIFO页面置换算法和LRU页面置换算法,获得课程设计优秀的好成绩
  • FIFO页面置换算法

    2011-02-19 20:51:21
    FIFO页面置换算法的实现源代码,附有可执行程序。
  • FIFO页面置换算法简单实现

    万次阅读 多人点赞 2019-06-09 19:04:43
    FIFO页面置换算法简单实现 先进先出置换算法 (页面置换) 最简单的页面置换算法是先入先出(FIFO)法。这种算法的实质是,总是选择在主存中停留时间最长(即最老)的一页置换,即先进入内存的页,先退出内存。理由是:最...

    FIFO页面置换算法简单实现
    先进先出置换算法
    (页面置换)
    最简单的页面置换算法是先入先出(FIFO)法。这种算法的实质是,总是选择在主存中停留时间最长(即最老)的一页置换,即先进入内存的页,先退出内存。理由是:最早调入内存的页,其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列,收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时,就把它插在队尾上。

    这种算法只是在按线性顺序访问地址空间 时才是理想的,否则效率不高。因为那些常被访问的页,往往在主存中也停留得最久,结果它们因变"老"而不得不被置换出去。

    FIFO的另一个缺点是,它有一种异常现象,即在增加存储块的情况下,反而使缺页中断率增加了。当然,导致这种异常现象的页面走向实际上是很少见的。
    在这里插入图片描述
    在这里插入图片描述

    #include<iostream>
    #define N 10
    using namespace std;
    
    int main()
    {
       // int ym[]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
        // int sum=20;
        int ym[]={4,3,2,1,4,3,5,4,3,2,1,5};
    int sum=12;
    //前两行演示FIFO算法,若注释这验证belady现象。
        int allchangetimes=0;
        int fifo[N]={0};
        int n;
        int dq=0;
    
        cout<<"输入页框大小:";
        cin>>n;
        for(int i=n-1;i>=0;i--)
        {
            fifo[i]=ym[dq++];
        }
    
                for(int i=0;i<n ;i++)
            {
                cout<<fifo[i]<<"   ";
            }
            cout<<endl;
    
    
        for(int j=n;j<sum;j++)
        {    int flag=0;
            for(int i=0;i<n;i++)
            {
                if(fifo[i]==ym[j])
                {  flag=1;
    
                    break;
                }
            }
    
            if(flag==0)
            {
                allchangetimes++;
                for(int i=n-1;i>=1;i--)
                {
                    fifo[i]=fifo[i-1];
                }
                    fifo[0]=ym[j];
            }
    
    
            for(int i=0;i<n;i++)
            {
                cout<<fifo[i]<<"   ";
            }
            cout<<endl;
        }
    
        cout<<"缺页"<<allchangetimes+n<<"次,"<<"置换"<<allchangetimes<<endl;
    }
    
    

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 用一种计算机高级语言来实现请求分页存储管理方式先进先出(FIFO置换算法,设计要求如下: ⑴ 能够输入给作业分配的内存块数; ⑵ 能够输入给定的页面,并计算发生缺页的次数以及缺页率; ⑶ 缺页时,如果发生...
  • fifo页面置换算法.doc

    2022-05-29 13:08:11
    fifo页面置换算法.doc
  • FIFO页面置换算法.pdf

    2021-10-04 01:43:07
    FIFO页面置换算法.pdf
  • LRU/最佳/FIFO页面置换算法

    千次阅读 2020-05-04 15:35:22
    一.先了解一下几种算法的定义: ...2. 先进先出(FIFO)页面置换算法FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。 3. LRU(Leas...

    一.先了解一下几种算法的定义:

    1. 最佳(Optimal)置换算法: 
    最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。
    2. 先进先出(FIFO)页面置换算法:
    FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
    3. LRU(Least Recently Used)置换算法:
    最近最久未使用(LRU)的页面置换算法是根据页面调入内存后的使用情况做出决策的。

    二.根据例题进一步了解几种算法:

    1、题目:
    在一个请求分页系统中,采用LRU/最佳/FIFO页面置换算法时,假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理块数M分别为3和4时,试计算在访问过程中所发生的缺页次数和缺页率,并比较所得结果
    2、计算过程:
    在这里插入图片描述
    LRU:
    M=3时缺页次数10,缺页率5/6;
    M=4时缺页次数8,缺页率2/3;

    *注:个人理解的LRU置换算法最早调入的数并且最近没有被使用,最先换出去。可能这么理解不是很准确。

    在这里插入图片描述
    最佳:
    M=3时缺页次数7,缺页率7/12;
    M=4时缺页次数6,缺页率1/2;

    *注:个人理解的最佳置换算法:最先替换掉,在未来一段时间内不会被用到的数。可能这么理解不是很准确。

    在这里插入图片描述
    FIFO:
    M=3时缺页次数9,缺页率3/4;
    M=4时缺页次数10,缺页率5/6;

    *注:个人理解的最佳置换算法:最先进来的最早被替换掉,先进先出。可能这么理解不是很准确。

    注:如果写的有什么不对的还请指正出来。
    定义以及题目(稍微有点改动,多添加了两种算法)来自操作系统课本。

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

    2015-12-03 20:17:10
    用C语言编写的FIFO页面置换算法,较为简易,多多指教
  • a:最佳置换算法(OPT):将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。 b: 先进先出算法(FIFO):淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。 c:最近最久未使用算法(LRU)...
  • 实验四 模拟FIFO页面置换算法 一、实验目的:用c/c++/java模拟FIFO页面置换算法 二、实验内容:随机一访问串和驻留集的大小,通过模拟程序显示淘汰的页号并统计命中率。示例: 输入访问串:7 0 1 2 0 3 0 4 2 3 0...

                                                                        实验四 模拟FIFO页面置换算法

    一、实验目的:用c/c++/java模拟FIFO页面置换算法

    二、实验内容:随机一访问串和驻留集的大小,通过模拟程序显示淘汰的页号并统计命中率。示例:

    输入访问串:7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 

    驻留集大小:3

    算法的实现:FIFO淘汰算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面进行淘汰。该算法实现只需把一个进程已调入内存的页面,按访问的时间先后顺序链接成一个队列,并设置一个指针,该指针始终指向“最老“的页面。

    7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1 

    7  7  7  2  2  2  2  4  4  4  0  0  0  0  0  0  0

       0  0  0  0  3  3  3  2  2  2  2  2  1  1  1  1

          1  1  1  1  0  0  0  3  3  3  3  3  2  2  2

    ×  ×  ×  ×      ×  ×  ×  ×  ×  ×          ×  ×

                7      0  1  2  3  0  4           2  3

    红色表示:指针指向调入内存的页面中“最老“的页面

    通过模拟程序输出淘汰的页号分别为:7 0 1 2 3 0 4 2 3

                       命中率为:5/13

     

    • 运行结果:

     

       

     

     

    背景: 这是我们操作系统课程的一道实验题

    这道题本来是一道非常简单的题,但是自己没仔细看题,加上对算法理解不够深刻,导致自己认为是最近最久未使用(LRU)算法,所以多花了半个小时测试,最后再仔细看了一下题,去掉一段代码,瞬间出来了

     

    解题思路:

    首先这里我是用Java写的,然后定义三个集合,一个是获取输入顺序,一个是内存集合,一个是淘汰页面的集合

    其次依次遍历输入顺序集合,每一次遍历都要表示时间加1,这里要默认内存中是没有当前遍历到的页面,

    然后在内存集合中找是否有这个页面,找到的话就直接将内存中的页面的驻留时间加1

    如果没有找到那么就看内存中的页面数是否大于内存最大容量,如果小于就直接加入页面,如果等于就进行置换

    置换是看哪个页面的驻留时间最长,置换掉驻留时间最长的页面然后再将内存中的页面的时间加1就可以了

     

    参考代码如下:

     

    package com.eternally.practice;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    class Page {
        int value;
        int time;
    
        public Page(int value, int time) {
    	this.value = value;
    	this.time = time;
        }
    }
    
    public class Test2 {
    
        public static void main(String[] args) {
    	Scanner in = new Scanner(System.in);
    	int n;
    	int base;//
    	int target = 0;// 命中
    	n = in.nextInt();
    	List<Page> list = new ArrayList<>();
    	for (int a = 0; a < n; a++) {
    	    int x = in.nextInt();
    	    Page page = new Page(x, 0);// 初始化
    	    list.add(page);// 加入集合中
    	}
    	base = in.nextInt();
    	List<Page> targetlist = new ArrayList<>();// 定义淘汰的集合
    
    	List<Page> list_base1 = new ArrayList<>();// 定义容器集合
    
    	for (int a = 0; a < list.size(); a++) {
    	    int flag = 0;// 默认不存在
    	    // 判断新进来的进程的页面再内存中是否存在
    	    for (int b = 0; b < list_base1.size(); b++) {
    		if (list_base1.get(b).value == list.get(a).value) {
    		    target++;
    		    flag = 1;
    		    break;
    		}
    	    }
    	    
    	    //如果内存中没有
    	    if (flag == 0) {
    		
    		if (list_base1.size()<base) {
    		    list_base1.add(list.get(a));// 将新的加入
    		} else {
    		    int maxtime = -1;
    			int locat = 0;
    			// 在内存中找出存在时间最久的
    			for (int b = 0; b < list_base1.size(); b++) {
    			    if (maxtime < list_base1.get(b).time) {
    				maxtime = list_base1.get(b).time;
    				locat = b;
    			    }
    			}
    		    targetlist.add(list_base1.get(locat));// 加入淘汰的
    		    list_base1.set(locat, list.get(a));// 删除时间最久的并加入最新的;
    		}
    
    	    }
    	    //时间增加
    	    for (int b = 0; b < list_base1.size(); b++) {
    		list_base1.get(b).time=list_base1.get(b).time+1;
    	    }
    	}
    	System.out.println("淘汰页号:");
    
    	for (int a = 0; a < targetlist.size(); a++) {
    	    System.out.print(targetlist.get(a).value + " ");
    	}
    	System.out.println("命中率:" + target + "/" + n);
        }
    
    }
    

     

     

    展开全文
  • 算法的实现:FIFO淘汰算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面进行淘汰。该算法实现只需把一个进程已调入内存的页面,按访问的时间先后顺序链接成一个队列,并设置一个指针,该指针始终...
  • 编程实现页面置换算法,最少实现两种算法,比较算法的优劣,并将调试结果显示在计算机屏幕上,检测机算和笔算的一致性。 (1)采用页式分配存储方案,通过分别计算不同算法的命中率来比较算法的优劣,同时也考虑页面...
  • 【操作系统实验】FIFO页面置换算法

    千次阅读 2021-11-21 16:21:50
    一、实验描述 二.实验程序 #include<stdio.h>...//页面调度的顺序 int b[3][13],c[13],p=0; b[0][0]=0;//C语言定义数组,初始值不确定 b[1][0]=0; b[2][0]=0; printf(" "); for(i=0;i
  • 该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法,包括先进先出(FIFO)、最佳置换算法(OPT)、最久最近未使用算法(LRU)。 具体实现功能有: 1、建立相应的数据结构 2、在屏幕上显示页面...
  • 页面置换算法: 资源包含三个算法:OPT---最佳置换算法、//FIFO---先进先出、//LRU---最近最久未使用 操作:用户输入物理块数、页面待要访问的个数、每个页面编号,计算出缺页数、置换数、缺页率 语言:C++ 运行环境...
  • 该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法,包括先进先出(FIFO)、最佳置换算法(OPT)、最久最近未使用算法(LRU)。 具体实现功能有: 1、建立相应的数据结构 2、在屏幕上显示页面的...
  • 操 作 系 统 实 验 报 告 页面置换算法模拟 OFTFIFO 和 LRU 算法 班级2013 级软件工程 1 班 学号X X X 姓名萧氏一郎 开始载入序列 开始 载入序列号从第 0 个得到页号 将页号放入物理地址中编号 s 根据选择的置换算法...
  • csdn小透明对大佬的代码做了一些小改进 仅作学习交流,侵权删除 ...以下是改进后的代码 class page: def __init__(self,num,time... # 记录页面号 self.num = num # 记录调入内存时间 self.time = time class main:
  • 页面置换如何运用先进先出FIFO算法进行置换,即最先来的最先置换出去
  • 页面置换算法FIFO算法

    千次阅读 2020-12-05 19:23:26
    最简单的页面置换算法,淘汰最先调入的。 实现:队列 依据: 先进入的可能已经使用完毕。 基本思想: 当需要淘汰一个页面时,总是选择驻留主存时间最长的页面进行淘汰,即先进入主存的页面先淘汰。 理由: 最早调入...
  • 算法实现使用了queue数据结构,实现简单,仅作纪念。 #include<iostream> #include<queue> #include<cstdio> using namespace std; int a[99],m,n; bool paichong(queue<int> q1,int ...
  • 连续输入页面的逻辑地址,以“-1”作为结束标志,采用FIFO页面置换算法、固定分配局部置换分配策略。输出该页面的页号和页内位移,若该页不在内存,并且还有剩余的物理块,将该页调入内存,输出“该页不在内存中,...
  • 页面置换算法FIFO&LRU)

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,138
精华内容 3,255
关键字:

fifo页面置换算法