精华内容
下载资源
问答
  • 先进先出页面置换算法
    千次阅读
    2018-11-14 16:17:39

    先进先出页面置换算法模拟

    时间限制: 1 Sec  内存限制: 128 MB
     

    题目描述

    一、实验目的
    1、加深理解先进先出页面置换算法及相关概念。
    2、掌握描述页面置换算法的置换图(教材p175图5-3)。
    3、会计算缺页率。

    二、实验原理
    1、进程的页面数目往往远大于操作系统分配给该进程的页框(物理块)数目,因此,往往只有部分页面能够装入页框中。 
    2、当进程调用 1 个页面时,有可能出现该页面不在页框中,这就需要一种算法决定淘汰哪一个页框中的页面,以加载新调用的页面到该页框中。 
    3、先进先出页面置换算法淘汰在主存中居留最长时间的页面,理由是:最早加载到页框中的页,其不再被访问的可能性最大。 

    三、实验要求
    1、用C++语言编写程序,模拟先进先出页面置换算法。
    2、main 函数及部分代码已编写如下,只需由你编写 fifo 函数并提交(只提交 fifo 函数实现代码)。

    #include <iostream>
    #include <iomanip>
    #include <vector>
    using namespace std;


    // fifo 函数声明
    // 输入参数描述:
    //   pageframeNum:操作系统分配给某进程的页框数目;
    //   pageCallSequence:页面调用序列,序列中的每一项是被调用页面的页面号。

    void fifo(int pageframeNum, vector<int> &pageCallSequence);

    int main()
    {
        int i, pageframeNum, n;

        cin>>pageframeNum; // 输入分配给某进程的页框数目(教材上称“页框”为:物理块)
        cin>>n; // 输入该进程的页面调用序列的长度
        vector<int> pageCallSequence(n); // 定义页面调用序列,序列中的每一项是被调用页面的页面号
        for(i = 0; i < n; i++) // 输入 n 个页面号,构建页面调用序列
        {
            cin>>pageCallSequence[i];
        }

        fifo(pageframeNum, pageCallSequence); // 模拟先进先出页面置换算法

        return 0;


    3、在 fifo 函数中,实现:每次访问页面时,依页框编号的次序输出页框中的页面编号;计算并输出缺页率。 
    4、输入输出格式见样例输入和样例输出。在样例输出中:除最后一行之外,每一行是依页框编号的次序输出页框中的页面编号,如果尚未加载页面到页框,则输出-1;最后一行是缺页率,保留三位有效数字。 
     

     

    输入

    3 12
    4 3 2 1 4 3 5 4 3 2 1 5

     

    输出

    4,-1,-1
    4,3,-1
    4,3,2
    1,3,2
    1,4,2
    1,4,3
    5,4,3
    5,4,3
    5,4,3
    5,2,3
    5,2,1
    5,2,1
    0.750

     

    样例输入

    5 20
    7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
    

     

    样例输出

    7,-1,-1,-1,-1
    7,0,-1,-1,-1
    7,0,1,-1,-1
    7,0,1,2,-1
    7,0,1,2,-1
    7,0,1,2,3
    7,0,1,2,3
    4,0,1,2,3
    4,0,1,2,3
    4,0,1,2,3
    4,0,1,2,3
    4,0,1,2,3
    4,0,1,2,3
    4,0,1,2,3
    4,0,1,2,3
    4,0,1,2,3
    4,0,1,2,3
    4,7,1,2,3
    4,7,0,2,3
    4,7,0,1,3
    0.450
    
    就是是纯模拟,没什么难度

    代码如下

    #include<iostream>
    #include<vector>
    using namespace std;

    void fifo(int pageframeNum, vector<int> &pageCallSequence)
    {
        int i, j, k;
        const int M = pageCallSequence.size();
        const int N = pageframeNum;
        bool T = 0;        //标记位
        int *a =new int[N];  //动态数组
        float s;
        for (i = 0; i<N; i++)
        {
            a[i] = -1;
        }
        k =0;
        for (j = 0; j<M; j++)
        {
            T = 0;                                //调入新页面之前默认该页面不在内存中
            for (i = 0; i<N; i++)
                if (pageCallSequence[j] == a[i])//如果调用的页面已存在内存中  标记位 置1,否则置0
                {
                    T = 1;
                    break;
                }
            if (T == 1)                    //如果页面已经存在于内存中 则输出 当下内存中的页面号
            {
                for (i = 0; i < N; i++)
                {
                    if (i==N-1)
                        printf("%d", a[i]);
                    else
                        printf("%d,", a[i]);
                }        
            }
            else                      //如果该页面不在内存中,则替换掉进入内存时间最长的页面
            {
                a[k%N] = pageCallSequence[j];    //实现先进先出的的代码
                k++;                    //记录页面置换次数
                for (i = 0; i<N; i++)
                { 
                    if (i ==N - 1)
                        printf("%d", a[i]);
                    else
                        printf("%d,", a[i]);
                }
            }
            printf("\n");
        }
        s =1.0*k/M;
        printf("%0.3f\n", s);
        delete a;
    }

    int main()
    {
        int i, pageframeNum, n;

        cin >> pageframeNum; // 输入分配给某进程的页框数目(教材上称“页框”为:物理块)
        cin >> n; // 输入该进程的页面调用序列的长度
        vector<int> pageCallSequence(n); // 定义页面调用序列,序列中的每一项是被调用页面的页面号
        for (i = 0; i < n; i++) // 输入 n 个页面号,构建页面调用序列
        {
            cin >> pageCallSequence[i];
        }
        fifo(pageframeNum, pageCallSequence); // 模拟先进先出页面置换算法
        //system("pause");
        return 0;
    }


     

    更多相关内容
  • 用C语言简单编写的代码,简单地实现了先进先出页面置换算法
  • 这是一个用c语言模拟先进先出页面置换算法的代码,可以任意输入页面数,物理块数与页面序列,然后进行置换后的排序。
  • 页面置换算法 最佳置换算法(OPT):选择永不使用或是在最长时间内不再被访问(即距现在最长时间才会被访问)的页面淘汰内存。用于算法评价参照。 随机置换算法 (S):产生一个取值范围在0和N-1之间的随机数,该...
  • 先进先出页面置换算法详解

    千次阅读 2021-05-12 00:25:38
    *先进先出(First In first Out,FIFO) 页面置换算法的基本思想: **每次置换最先调入内存的页面,即将内存中等待时间最长的页面进行置换。此算法的适用范围是顺序结构程序。 基本原理 FIFO页面置换算法, 也就是先进...

    *先进先出(First In first Out,FIFO) 页面置换算法的基本思想:

    **每次置换最先调入内存的页面,即将内存中等待时间最长的页面进行置换。此算法的适用范围是顺序结构程序。

    基本原理

    FIFO页面置换算法, 也就是先进先出的意思。这和我们现实生活中的排队方式很相似, 先进队伍的人会先买到票, 然后先从队伍中离开。如果使用FIFO算法作为页面置换算法, 缓存空间大小是三个页面时, 一次进入Page1, Page2, Page3。当Page4要进入缓存时, 操作系统将会把Page1清除出缓存, 将Page4加入至缓存中。如果再有Page5要进入缓存时, 操作系统会将Page2清除出缓存空间, 以此类推。

    实现过程

    比如有下述页面走向:1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6。当内存块数量分别为3时, 我们算一算使有此方法时产生的缺页次情况。 (注意, 所有内存块最初都是空的, 凡第一次用到的页面都产生一次缺页。)
    当内存块数量分别为3时, FIFO算法的执行过程如下图所示。
    打叉的表示发生了缺页, 共缺页16次。
    在这里插入图片描述

    优点

    先进先出页面置换算法的优点是其实现起来比较简单,可以不需要硬件的支持, 因而不需要增加系统的成本。

    缺点

    先进先出页面置换算法没有考虑到缓存页面被使用的情况。如果一个页面被频繁访问, 我们应该将它保留在缓存中, 这样就能够提高程序的性能。但是使用FIFO算法, 很可能将一个被频繁访问的页面清除出缓存, 所以FIFO算法在实际的应用中是很少被使用到的, 但是这种思想是计算机系统中常常被采用的。
    在大数情况下,先进先出页面置换算法缺页率比较低或会产生Belady异常现象。

    展开全文
  • FIFO 先进先出页面置换算法 根据作业序列判断置换,先进先置换的原则。 实现过程: 用vector简单模拟这个过程,不用直接queue模拟,是因为,当判断是否需要置换的时候,queue不好判断在队列中是否存在这个数。...

    FIFO 先进先出页面置换算法

    根据作业序列判断置换,先进先置换的原则。

    image-20220505151943627

    实现过程:

    用vector简单模拟这个过程,不用直接queue模拟,是因为,当判断是否需要置换的时候,queue不好判断在队列中是否存在这个数。vector就方便很多。用一个二维数组存下过程的产生的置换图,换面好输出。

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    
    
    
    int main(){
        int n,m;    
    
        vector<int> num;//存储序列页号
        cout<<"请输入作业序列(输入-1停止输入)"<<endl;
        int x;
        while(cin>>x){
            if(x==-1) break;
            num.push_back(x);
        }
        n=num.size();
        cout<<"请输入物理块数: ";
        cin>>m;
        cout<<endl;
        cout<<"页面总数 "<<n<<"物理块数 "<<m<<endl<<endl;
    
        vector<int> q;//用vector模拟队列,先进先出
    
        int count=0;//记录置换的次数
    
        vector<bool>vis(n,0);
        vector<vector<int> > ans(n,vector<int> (m,-1));
    
        for(int i=0;i<n;i++){
            int ok=false;
            if(q.size()<m){
                q.push_back(num[i]);
                count++;
                vis[i]=1;
            }
            else{
                //从队列中查找是否有当前这个页号,没有就需要置换
                
                for(int j=0;j<q.size();j++){
                    if(q[j]==num[i]) {
                        ok=true;
                        break;
                    }
                }
                if(!ok){
                    q.erase(q.begin());//置换队列头部的数
                    q.push_back(num[i]);
                    vis[i]=1;
                    count++;
                }
            }
    
            for(int j=0;j<q.size();j++){
                ans[i][j]=q[j];
            }
            
        }
        //把作业情况输出
    
        cout<<"FIFO: "<<endl;
        cout<<"作业序列  ";
        for(int i=0;i<n;i++) cout<<num[i]<<" ";
        cout<<endl<<endl;
    
        for(int i=0;i<m;i++){
            if(i==0){
                cout<<"最开始的  ";
            }else if(i==m-1){
                cout<<"最末尾的  ";
            }
            else cout<<"          ";
            for(int j=0;j<n;j++){
                if(ans[j][i]==-1) cout<<"  ";
                else cout<<ans[j][i]<<" ";
            }
            cout<<endl<<endl;
        }
        cout<<"是否置换  ";
        for(int i=0;i<n;i++){
            if(vis[i]) cout<<"X ";
            else cout<<"  ";
        }
        cout<<endl<<endl;
        cout<<"置换率为  "<< count*1.0/n<<endl;
    }
    
    /*
    7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
    */
    
    展开全文
  • FIFO算法核心是对内存分配给进程的页块的处理 import java.util.Scanner; public class FIFO { public static void main(String[] args){ Scanner scan=new Scanner(System.in); int mempag=scan.nextInt(); ...

     FIFO算法核心是对内存分配给进程的页块的处理

    import java.util.Scanner;

    public class FIFO {
        public static void main(String[] args){
            Scanner scan=new Scanner(System.in);
            int mempag=scan.nextInt();
            int top=0,head=0,count=0,cols=0;
            int[] seq={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1},stack=new int[mempag];

            while(head<seq.length){  //保持最新的页数在stack[mempag],最旧的页数在stack[0];
                int j=1<<seq[head];
                if((cols & j)==0){
                    if(head<mempag){
                        stack[top++]=seq[head];
                    }else{
                        cols=cols-(1<<stack[0]);
                        stack[0]=seq[head];
                        int index=0;
                        for(int i=0;i<mempag;i++){
                            if(stack[i]!=seq[head]){
                                int a=stack[index];
                                stack[index]=stack[i];
                                stack[i]=a;
                                index++;//当前值不等于head指向的值,index与i同步
                            }
                        }
                    }
                    cols=cols | j;
                    count++;
                    System.out.print(stack[0]+""+stack[1]+""+stack[2]+" ");
                }else{
                    int index=0;
                    for(int i=0;i<mempag;i++){
                        if(stack[i]!=seq[head]){
                            int a=stack[index];
                            stack[index]=stack[i];
                            stack[i]=a;
                            index++;//当前值不等于head指向的值,index与i同步
                        }
                    }
                }
                head++;
            }
            System.out.print(count+"次");
        }
    }

    运算结果:

     

    展开全文
  • 操作系统课程设计-先进先出页面置换算法.doc
  • FIFO先进先出页面置换算法实现

    千次阅读 2018-11-26 00:27:50
    FIFO先进先出页面置换算法,是最早出现的页面置换算法,该算法总是淘汰最先进入内存的页面。以下是代码: #include &lt;iostream&gt; #include &lt;iomanip&gt; #include &lt;vector&gt; ...
  • 【一】先进先出页面置换算法

    千次阅读 2018-12-28 18:03:06
    地址映射过程中,若在...最简单的页面置换算法是先入先出(FIFO)法。    优先淘汰最早进入内存的页面,亦即在内存中驻留时间最久的页面。该算法实现简单,只需把调入内存的页面根据先后次序链接成队列,设置一...
  • 先进先出页面置换算法(FIFO)

    千次阅读 2018-12-01 15:34:52
    算法规则: 顾名思义,最早进来的元素,若发生缺页要最先出去。   code: #include &lt;iostream&gt; #include &lt;cstdlib&gt; #include &lt;vector&gt; #include &lt;cstdio&...
  • /*先进先出页面置换算法*/

    千次阅读 2017-05-07 16:35:17
    /*先进先出页面置换算法*/ #include #include #define N 100 int Butter[N]={-1}; int count=0; int l=0; bool CheckFull(int a[],int n){ int num=0; while(a[num++]!=-1){ } if(num==n+1){ return ...
  • 甘肃政法学院 本科生实验报告 六 姓名 : 马晓娟 学院 : 公安技术学院 专业 : 信息安全 班级 :...第一学期 甘肃政法学院实验管理中心印制 实验题目 小 组 合 否 虚拟内存页面置换算法 作 姓名 马晓娟 班级 2013 级 信 学
  • 1.动态输入进入内存的页面总数,系统分配的物理块数,依次进入内存的页面号。...当内存中存在新页面号时不作任何调动,一直进行直至用户输入的页面号全部执行完毕,最后输出置换的次数,以及置换率。
  • 操作系统 课外实践报告 项 目 名 称 所 在 班 级 姓名 小 组 成 员 页面置换算法 学号 组长 指 导 教 师 成 绩 评 定 支丽平 页面置换算法中的先进先出算法 一 实验目的 了解最佳页面置换算法先进先出 FIFO 页面...
  • 要求计算以下两种置换算法的缺页数 1先进先出算法FIFOFirst In First Out 2最近最久未使用算法LRULeast Recently Used 二实验实训方法过程步骤 1新建一个文件命名为fifo.c并打开该文件编写C程序 2在fifo.c程序中实现...
  • 广东工业大学 操作系统实验 实验内容 假设每个页面中可存放...如果4个内存块均已装入该作业,则需进行页面置换,最后显示其物理地址,并转下一条指令。在所有320指令执行完毕后,请计算并显示作业运行过程中发生的缺页
  • 首先明确,我们要将页上的信息对应装入到物理块中那么我们装入物理块中时,就首先要判断,物理块是否满,如果不满,写入,如果满,按照先进先出的原则,将物理块中的页替换出去贴代码#include&lt;iostream&...
  • 页面置换算法--先进先出页面置换

    千次阅读 2020-12-09 18:18:20
    //等待时间,LRU算法会用到这个属性 }Pro; int pageNum; //系统分配给作业的主存中的页面数 int memoryNum; //可用内存页面数 void print(Pro *page1); //打印当前主存中的页面 int Search(int num1, Pro *...
  • 页面置换算法C语言实现(先进先出FIFO、最近最久未使用LRU C语言实现)
  • LRU页面置换算法模拟 - 最近最久未使用置换算法 - 课程设计 LRU 页面置换算法模拟 - 最近最久未使用置换算法 | 课程设计 | 计算机数据库课程设计 一设计目的 1用 C 语言实现最近最久未使用 LRU置换算法 2了解内存...
  • 页面置换如何运用先进先出FIFO算法进行置换,即最先来的最先置换出去
  • 先进先出(FIFO)页面置换算法 【注】本代码数据及思路方法参考自《计算机操作系统(第四版)》汤小丹等 编著的教材。 #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...
  • 操作系统中编程描述页面置换算法——先进先出算法。 一、目的和要求 给出页面访问的顺序与分配给作业的主存块数,使用队列作为数据结构编写算法,实现统计缺页次数与页面置换操作,用C语言编程并用文档形式给出...

空空如也

空空如也

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

先进先出页面置换算法

友情链接: giu_wi60.zip