精华内容
下载资源
问答
  • 先进先出页面置换算法
  • 先进先出页面置换算法模拟 时间限制: 1 Sec 内存限制: 128 MB   题目描述 一、实验目的 1、加深理解先进先出页面置换算法及相关概念。 2、掌握描述页面置换算法的置换图(教材p175图5-3)。 3、会计算缺页率...

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

    时间限制: 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;
    }


     

    展开全文
  • FIFO先进先出页面置换算法实现

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

    学校要做的实验,很久没有写代码了orz,所以写的很乱。不过可以直接提交到oj平台上。自己写的代码,欢迎讨论。

    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;最后一行是缺页率,保留三位有效数字。
    
    
    void fifo(int pageframeNum, vector<int> &pageCallSequence)
    {
    	int arr[100] = { -1 };//初始化数组并且赋值为-1,最高上限100
    	for (int i = 0; i < 100; i++)
    	{
    		arr[i] = -1;
    	}
    	int arr1[100];//标志数组,每改变一次数+1
    	for(int i=0;i<pageframeNum;i++)//初始值设为0
    	{
    		arr1[i]= 0;
    	}
    	for (int i = pageframeNum; i < 100; i++)//其他不相关的值设为100
    	{
    		arr1[i] = 100;
    	}
    	int change = pageframeNum;//计算缺页次数,并且作为确认修改哪个数值的指针
    	int size = pageCallSequence.size();//页面调用长度
    	int flag = 0;//标志,插入的数字在页表中存在就设置为1
    	int flag1 = 0;//标志2,判断arr1中最小数字,即最先进入的值
    	int a;//保存缺页次数
    	for (int i = 0; i < size; i++)
    	{
    		int temp = pageCallSequence.at(i);//temp为当前所指向的页面号
    
    			for (int i1 = 0; i1 < pageframeNum; i1++)//遍历操作,判断插入的数字是否已存在
    			{
    				if (arr[i1] == temp)
    					flag = 1;//如果已经存在就不执行后面的操作
    			}
    			if (flag == 0)//不存在时的操作
    			{
    				//判断arr1中最小数字,即最先进入的值,并且替换arr中相应的数据,对插入的地方arr1+1
    				for (int t = 0; t < pageframeNum; t++)
    				{
    					if (arr1[t] < arr1[0])
    					{
    						arr[t] = temp;
    						arr1[t]++;
    						flag1 = 1;
    						break;
    					}
    				}
    				if (flag1 == 0)
    				{
    					arr[0] = temp;
    					arr1[0]++;
    				}
    				change++;//缺页次数+1
    			}
    		for (int i3 = 0; i3 < pageframeNum; i3++) //按照格式输出
    		{
    			if (i3 + 1 == pageframeNum)
    			{
    				cout << arr[i3] << endl;
    			}
    			else
    			{
    				cout << arr[i3] << ",";
    			}
    		}
    		a = change;
    		flag = 0;//重置标志
    		flag1 = 0;//重置标志
    	}
    	float queye = (float)(a-pageframeNum) / (float)size;//计算缺页率
    	//cout << cout.precision(4) <<queye<<endl;
    	printf("%.3f", queye);//输出小数点后三位
    
    }

    设置了两个数组,最大值都是100,所以最多可以设置100个页面。

                                                                                                                                                                                                                2018.11.26

                                                                                                                                                                                                                 小旻

    展开全文
  • 这是一个用c语言模拟先进先出页面置换算法的代码,可以任意输入页面数,物理块数与页面序列,然后进行置换后的排序。
  • *先进先出(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异常现象。

    展开全文
  • /*先进先出页面置换算法*/

    千次阅读 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 ...
    /*先进先出页面置换算法*/
    #include<stdio.h>
    #include<malloc.h>
    #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 true;
    }
    return false;
    }
    bool CheckFind(int a[],int n,int data){
    for(int i=0;i<n;i++){
    if(a[i]==data){
    return true;
    }
    }
    return false;
    }
    void First(int a[],int n){
    for(int i=0;i<n;i++){
    a[i]=-1;
    }
    }
    void Print(int a[],int n){
    printf("当前内存块中的数据:");
    for(int i=0;i<n;i++){
    printf("%d ",a[i]);
    }
    printf("\n");
    }
    int piror=0;
    int main(){
    int n,num,k=0;
    int *fir;
    int temp=0;
    printf("物理块的大小:");
    scanf("%d",&n);
    printf("数据个数:");
    scanf("%d",&num);
    fir=(int *)malloc(sizeof(int)*(n+1));
    First(fir,n+1);
    for(int i=0;i<num;i++){
    printf("数据%d:",i+1);
    scanf("%d",Butter+i);
    }
    Print(Butter,num);
    for(int j=0;j<num;j++){
    if(CheckFull(fir,n)==false){
    if(CheckFind(fir,n,Butter[j])==false){
    *(fir+l)=Butter[j];
    count++;
    l++;
    Print(fir,n);
    }
    }
    else{
    if(CheckFind(fir,n,Butter[j])==false){
    *(fir+k)=Butter[j];
    count++;
    k++;
    Print(fir,n);
    }
    if(k==n){
    k=0;
    }
    }
    }
    printf("缺页次数:%d\n",count);
    printf("页面置换次数:%d\n",count-n);
    printf("命中次数:%d\n",num-count);
    printf("命中率%.2f%\n",(1-(float)(count)/num)*100);
    return 0;
    }
    展开全文
  • 【一】先进先出页面置换算法

    千次阅读 2018-12-28 18:03:06
    地址映射过程中,若在...最简单的页面置换算法是先入先出(FIFO)法。    优先淘汰最早进入内存的页面,亦即在内存中驻留时间最久的页面。该算法实现简单,只需把调入内存的页面根据先后次序链接成队列,设置一...
  • 1.动态输入进入内存的页面总数,系统分配的物理块数,依次进入内存的页面号。...当内存中存在新页面号时不作任何调动,一直进行直至用户输入的页面号全部执行完毕,最后输出置换的次数,以及置换率。
  • 首先明确,我们要将页上的信息对应装入到物理块中那么我们装入物理块中时,就首先要判断,物理块是否满,如果不满,写入,如果满,按照先进先出的原则,将物理块中的页替换出去贴代码#include&lt;iostream&...
  • FIFO(First-In First-Out)先进先出页面置换算法:FIFO淘汰算法总是淘汰最先装入内存的页面,即选择在内存中驻留时间最久的页面进行淘汰。该算法实现只需把一个进程已调入内存的页面,按访问的时间先后顺序链接成一...
  • 先进先出页面置换算法c语言源码

    千次阅读 2017-11-25 21:45:48
    #include   #define M 20   #define N 3   void FIFO(int a[N],int b[M])   { int i,j,k;      int c[M]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};... 
  • 先进先出页面置换算法(FIFO)

    千次阅读 2018-12-01 15:34:52
    算法规则: 顾名思义,最早进来的元素,若发生缺页要最先出去。   code: #include &lt;iostream&gt; #include &lt;cstdlib&gt; #include &lt;vector&gt; #include &lt;cstdio&...
  • 操作系统 课外实践报告 项 目 名 称 所 在 班 级 姓名 小 组 成 员 页面置换算法 学号 组长 指 导 教 师 成 绩 评 定 支丽平 页面置换算法中的先进先出算法 一 实验目的 了解最佳页面置换算法先进先出 FIFO 页面...
  • 主要实现主存空间的分配和回收、存储保护。主要是对用户区的管理。存储管理采用请求分页式存储管理方式。该系统的页面置换算法必须包括先进先出页面置换算法、最近最少使用LRU页面置换算法、最佳置换算法。
  • 2. 掌握请求页式存储管理的页面置换算法,如最佳(Optimal)置换算法、先进先出(Fisrt In First Out)置换算法和最近最久未使用(LeastRecently Used)置换算法。二、 实验内容设计模拟实现OPT、FIFO和LRU页面...
  • //等待时间,LRU算法会用到这个属性 }Pro; int pageNum; //系统分配给作业的主存中的页面数 int memoryNum; //可用内存页面数 void print(Pro *page1); //打印当前主存中的页面 int Search(int num1, Pro *...
  • 1.最佳(Optimal)置换算法 该算法所选择的淘汰页面,将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法,通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干...
  • 先进先出置换算法---FIFO3.最近最久未使用置换算法---LRU4.时钟置换算法---CLOCK5.改造型时钟置换算法 0.思维导图 1.最佳置换算法—OPT 2.先进先出置换算法—FIFO 3.最近最久未使用置换算法—LRU 4.时钟...
  • 使用c++语言编写的模拟实现先进先出页面置换算法,定义了一个FIFO类,FIFO类有一个str数组来存放页面走向;一个base数组表示物理块;一个int型变量来存放最先进入物理块的下标。这是个比较简单的代码,
  • 页面置换如何运用先进先出FIFO算法进行置换,即最先来的最先置换出去
  • 本文实例为大家分享了C语言实现页面置换算法的具体代码,供大家参考,具体内容如下一、设计目的加深对请求页式存储管理实现原理的理解,掌握页面置换算法中的先进先出算法。二、设计内容设计一个程序,有一个虚拟...
  • 地址映射过程中,若在页面中发现所要访问的页面不再内存中...最简单的页面置换算法是先入先出(FIFO)法。 假定系统为某进程分配了三个物理块,并考虑有以下页面号引用串:7, 0, 1, 2, 0, 3, 0,4,2,3, 0, 3, 2, 1,
  • 叙》《张中丞者依马伶《五伶官代史的作传序传后传》次是。下列作品中,进形式通篇寓言的是采用说理。置中心一文梁启论毅力》达的超《所表是。页最》中子是隐《运用无题李商的句传说神话抒情。下列表述的是...
  • 题目阐述如下:设计四:页面置换设计目的:加深对请求页式存储管理实现原理的理解,掌握页面置换算法。设计内容:设计一个程序,有一个虚拟存储区和内存工作区,实现下述三种算法中的任意两种,计算访问命中率(命中率=...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 710
精华内容 284
关键字:

先进先出页面置换算法