精华内容
下载资源
问答
  • 页面置换算法c语言
    2021-05-20 10:51:20

    页面置换算法

    一.题目要求:

    通过实现页面置换算法的FIFO和LRU两种算法,理解进程运行时系统是怎样选择换出页面的,对于两种不同的算法各自的优缺点是哪些。

    要求设计主界面以灵活选择某算法,且以下算法都要实现 1) 最佳置换算法(OPT):将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。

    2) 先进先出算法(FIFO):淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。

    3) 最近最久未使用算法(LRU):淘汰最近最久未被使用的页面。 4) 最不经常使用算法(LFU) 二.实验目的:

    1、用C语言编写OPT、FIFO、LRU,LFU四种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三、设计要求

    1、编写算法,实现页面置换算法FIFO、LRU;

    2、针对内存地址引用串,运行页面置换算法进行页面置换; 3、算法所需的各种参数由输入产生(手工输入或者随机数产生); 4、输出内存驻留的页面集合,页错误次数以及页错误率;

    四.相关知识:

    1.虚拟存储器的引入:

    局部性原理:程序在执行时在一较短时间内仅限于某个部分;相应的,它所访问的存储空间也局限于某个区域,它主要表现在以下两个方面:时间局限性和空间局限性。

    2.虚拟存储器的定义:

    虚拟存储器是只具有请求调入功能和置换功能,能从逻辑上对内存容量进行扩充的一种存储器系统。

    3.虚拟存储器的实现方式:

    分页请求系统,它是在分页系统的基础上,增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。

    请求分段系统,它是在分段系统的基础上,增加了请求调段及分段置换功能后,所形成的段式虚拟存储系统。

    4.页面分配:

    平均分配算法,是将系统中所有可供分配的物理块,平均分配给各个进程。 按比例分配算法,根据进程的大小按比例分配物理块。

    考虑优先的分配算法,把内存中可供分配的所有物理块分成两部分:一部分按比例地分配给各进程;另一部分则根据个进程的优先权,适当的增加其相应份额后,分配给各进程。

    5.页面置换算法:

    更多相关内容
  • 操作系统课程设计-页面置换算法C语言.pdf
  • 页面置换算法C语言实现(先进先出FIFO、最近最久未使用LRU C语言实现)

    1. 实现效果

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

    2. 源代码

    #include<iostream>
    #include<process.h>
    #include<stdlib.h>
    #include<ctime>
    #include<conio.h>
    #include<stdio.h>
    #include<string.h>
    using namespace std;
    
    #define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")/*表格控制*/
    #define bsize 4 //物理块大小
    #define psize 16 //进程大小
     void chushihua();//初始化函数
     void ymzh();
     void yemianzhihuan ();
     void changeaddr(struct Page p[], int logaddr);
     void dizhizhuanhuan();
     void menu();
     int wang();
    
     int yemianliu[32]={0};//全局变量数组,地址流
     int p;
     struct Page  {
         int pno;//页号
         int flag;//标志位
         int cno;//主存号
         int modf;//修改位
         int addr;//外存地址
    }Page;  //全局变量p是一共有多少地址流
    
     typedef struct pagel
     {
         int num; /*记录页面号*/
         int time;  /*记录调入内存时间*/
     }Pagel;  /*页面逻辑结构,方便算法实现*/
    
     Pagel 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;//i表示进程序列号,j表示物理块号*/
     int m =-1,n =-1;//物理块空闲和进程是否相同判断标志*/
     int mmax=-1, maxflag=0;//标记替换物理块进程下标*/
     int count =0; //统计页面缺页次数
    
     void chushihua() //初始化函数
    {
         int t;
         srand(time(0));//随机产生指令序列
             p=12+rand()%32;
         cout<<"地址流序列:";
         cout<<endl;
         for(i=0; i<p; i++)
         {
             t=1+rand()%9;
             yemianliu[i]=t;//将随机产生的指令数存入页面流
        }
        for (i=p-1;i>=0;i--)
        {
            cout<<yemianliu[i]<<" ";
        }
        cout<<endl;
    }
    void ymzh()
    {
        chushihua();
         yemianzhihuan();
    }
    
     void yemianzhihuan()
     {
          int a;
         printf("----------------------------------\n");
         printf("☆☆欢迎使用分页模拟实验系统☆☆\n");
         printf("----------------------------------");
         printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
         printf("☆☆1.进入硬件地址变换算法  ☆☆\n");
         printf("☆☆------------------------☆☆\n");
         printf("☆☆2.进入页面置换算法      ☆☆\n");
         printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
         printf("请输入您的选择:");
     switch(a)
     {
         case 1:
             ymzh();
             break;
         case 2:
             wang();
             break;
         default:
         cout<<"输入有误,请重新输入!"<<endl;
         break;
     }
    }
    
     void changeaddr(struct Page p[], int logaddr){//地址变换
         int j=logaddr/64;//对应的块号
         int k=logaddr%64; //对应的偏移量
         int flag=0;
         int addr;
         for(int i=0;i<8;i++)
         {
            if(p[i].pno==j)//找到对应的页号
            {
                if(p[i].flag==1)//页面标志为1
                {
                 addr=p[i].cno*64+k;
                 cout<<"物理地址为:"<<addr<<endl;
                 cout<<"详细信息:"<<"\t页面号:"<<p[i].pno<<"\t 主存号:"<<p[i].cno<<"\t偏移量:"<<k<<endl;
                 flag=1;
                 break;
                }
            }
        }
    
            if(flag==0)
                cout<<"该页不在主存,产生缺页中断"<<endl;
        }
    
     void dizhizhuanhuan()
     {
         int a;
         int ins;//指令逻辑地址
         struct Page p[8];
        p[0].pno=0;p[0].flag=1;p[0].cno=5;p[0].modf=1;p[0].addr=011;
        p[1].pno=1;p[1].flag=1;p[1].cno=8;p[1].modf=1;p[1].addr=012;
        p[2].pno=2;p[2].flag=1;p[2].cno=9;p[2].modf=0;p[2].addr=013;
        p[3].pno=3;p[3].flag=1;p[3].cno=10;p[3].modf=0;p[3].addr=015;
        p[4].pno=4;p[4].flag=0;p[4].addr=017;
        p[5].pno=5;p[5].flag=0;p[5].addr=025;
        p[6].pno=6;p[6].flag=0;p[6].addr=212;
        p[7].pno=7;p[7].flag=0;p[7].addr=213;
         printf("\t\t\t--------------------------------\n");
         printf("\t\t\t☆☆欢迎使用分页模拟实验系统☆☆\n");
         printf("\t\t\t---------------------------------\n");
         printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
         printf("\t\t\t☆☆1.输入指令              ☆☆\n");
         printf("\t\t\t☆☆------------------------☆☆\n");
         printf("\t\t\t☆☆2.进入页面置换算法      ☆☆\n");
         printf("\t\t\t☆☆------------------------☆☆\n");
         printf("\t\t\t☆☆0.EXIT                  ☆☆\n");
         printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
     while(a!=0)
     {
        cout<<endl<<"请输入您的选择:";
         cin>>a;
    
        cout<<"页号"<<"标记位"<<"外存地址"<<"主存号"<<endl;
         for(int i=0;i<8;i++)
         {
             cout<<p[i].pno<<"\t"<<p[i].flag<<"\t"<<p[i].addr<<"\t";
             if(p[i].flag)
             cout<<p[i].cno;
             cout<<endl;
        }
    
     switch(a)
     {
         case 0:printf("\t\t\t再见!\t\t\t\n"); break;
         case 1:
             cout<<"请输入指令的逻辑地址:";
             cin>>ins;
             changeaddr(p, ins);break;
         case 2: system("CLS"); a=wang();break;
         default:cout<<"输入有误,请重新输入!"<<endl;break;
        }
    }
    }
    
     void menu()
     {
     int a;
         printf("\t\t\t--------------------------------\n");
         printf("\t\t\t☆☆欢迎使用分页模拟实验系统☆☆\n");
         printf("\t\t\t---------------------------------\n");
         printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
         printf("\t\t\t☆☆1.输入指令              ☆☆\n");
         printf("\t\t\t☆☆------------------------☆☆\n");
         printf("\t\t\t☆☆2.进入页面置换算法      ☆☆\n");
         printf("\t\t\t☆☆------------------------☆☆\n");
         printf("\t\t\t☆☆0.EXIT                  ☆☆\n");
         printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
         printf("请选择所要执行的操作:");
         scanf("%d",&a);
         switch(a)
         {
         case 0: printf("\t\t\t-再见!-\t\t\t\n");break;
         case 1: dizhizhuanhuan (); break;
         case 2: wang (); break;
         default:cout<<"输入有误,请重新输入!"<<endl;break;
        }
    }
    int main()
     {
         menu();
    }
    
    //****************随机产生序列号函数
     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++) {
                if(phb[j] == 0){
                    m=j;
                    break;
                }
            }
            //找与进程相同的标号
            for(j=0;j<bsize;j++) {
                if(phb[j] == pro[i]){
                    n=j;
                }
            }
    
     //找flag值最大的
         for(j=0;j<bsize;j++)
        {
             if(flag[j]>maxflag)
             {
                 maxflag = flag[j];
                 mmax = 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[mmax] =pro[i];
                 flag[mmax] =0;
                 for (j=0;j<bsize;j++)
                {
                     flag[j]++;
                }
                 mmax = -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("缺页率 :%16. 6f",(float)count/psize);
         printf("\n");
    }
    /*初始化内存单元、缓冲区*/
     void Init(Pagel *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(Pagel *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, Pagel *b)
     {
         int i;
        for(i=0;i<bsize;i++)
        {
             if(fold==b[i]. num)
                 return i;
        }
         return -1;
    }
    /*LRU核心部分*/
     void Lruu(int fold, Pagel *b)
     {
         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++){
    
    //         URLcount++;
                 if (i!=val)
                     b[i].time++;
            }
        }
    }
    
     void LRU()
     {
         int i,j;
         k=0;
         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;i++)
    //        printf("%3d", queue[i]);
    
        printf("\n缺页次数为:%6d\n   缺页率 :%16. 6f", k+1,(float)(k+1)/psize);
    }
    
    //********主函数
     int wang()
     {
         int sel;
         do{
         printf("\t\t\t--------------------------------\n");
         printf("\t\t\t☆☆欢迎使用分页模拟实验系统☆☆\n");
         printf("\t\t\t---------------------------------\n");
         printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
         printf("\t\t\t☆☆       虚拟内存         ☆☆\n");
         printf("\t\t\t☆☆------------------------☆☆\n");
         printf("\t\t\t☆☆1.产生随机序列          ☆☆\n");
         printf("\t\t\t☆☆------------------------☆☆\n");
         printf("\t\t\t☆☆2.最近最久未使用        ☆☆\n");
         printf("\t\t\t☆☆------------------------☆☆\n");
         printf("\t\t\t☆☆3.先进先出              ☆☆\n");
         printf("\t\t\t☆☆------------------------☆☆\n");
         printf("\t\t\t☆☆0.退出                  ☆☆\n");
         printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
         printf("请选择所要执行的操作:");
         scanf("%d",&sel);
         switch(sel)
        {
             case 0: printf("\t\t\t再见!t\t\t\n"); break;
             case 1: build(); break;
             case 2: printf("最近最久未使用\n"); LRU();empty(); printf("\n");break;
             case 3: printf("先进先出算法\n"); FIFO();empty();printf("\n");break;
             default:printf("请输入正确的选项号!");printf("\n\n");break;
        }
    }while(sel !=0 );
         return sel;
    }
    
    展开全文
  • (完整word版)操作系统课程设计-页面置换算法C语言.pdf(完整word版)操作系统课程设计-页面置换算法C语言.pdf(完整word版)操作系统课程设计-页面置换算法C语言.pdf(完整word版)操作系统课程设计-页面置换算法C语言.pdf...
  • (完整word版)操作系统课程设计-页面置换算法C语言.docx(完整word版)操作系统课程设计-页面置换算法C语言.docx(完整word版)操作系统课程设计-页面置换算法C语言.docx(完整word版)操作系统课程设计-页面置换算法C语言....
  • 操作系统课程设计-页面置换算法C语言.docx操作系统课程设计-页面置换算法C语言.docx操作系统课程设计-页面置换算法C语言.docx操作系统课程设计-页面置换算法C语言.docx操作系统课程设计-页面置换算法C语言.docx操作...
  • 操作系统课程设计-页面置换算法C语言 (2).pdf操作系统课程设计-页面置换算法C语言 (2).pdf操作系统课程设计-页面置换算法C语言 (2).pdf操作系统课程设计-页面置换算法C语言 (2).pdf操作系统课程设计-页面置换算法...
  • 操作系统课程设计-页面置换算法C语言 (2).docx操作系统课程设计-页面置换算法C语言 (2).docx操作系统课程设计-页面置换算法C语言 (2).docx操作系统课程设计-页面置换算法C语言 (2).docx操作系统课程设计-页面置换...
  • 操作系统课程设计_页面置换算法C语言.docx操作系统课程设计_页面置换算法C语言.docx操作系统课程设计_页面置换算法C语言.docx操作系统课程设计_页面置换算法C语言.docx操作系统课程设计_页面置换算法C语言.docx操作...
  • 操作系统课程设计_页面置换算法C语言.pdf操作系统课程设计_页面置换算法C语言.pdf操作系统课程设计_页面置换算法C语言.pdf操作系统课程设计_页面置换算法C语言.pdf操作系统课程设计_页面置换算法C语言.pdf操作系统...
  • 操作系统课程设计页面置换算法C语言.docx操作系统课程设计页面置换算法C语言.docx操作系统课程设计页面置换算法C语言.docx操作系统课程设计页面置换算法C语言.docx操作系统课程设计页面置换算法C语言.docx操作系统...
  • 操作系统课程设计页面置换算法C语言.pdf操作系统课程设计页面置换算法C语言.pdf操作系统课程设计页面置换算法C语言.pdf操作系统课程设计页面置换算法C语言.pdf操作系统课程设计页面置换算法C语言.pdf操作系统课程...
  • opt、FIFO、LRU/LFU、简单clock、改进型clock等算法实现页面置换
  • 网上资源虽多,但是要想把这两个算法的细节理解的透彻,还得是自己写 1.FIFO #include <stdio.h> #include <stdlib.h> #include <time.h> //主要数据结构 #define total_instrucion 15//总的...

    网上资源虽多,但是要想把这两个算法的细节理解的透彻,还得是自己写

    1.FIFO

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    //主要数据结构
    #define total_instrucion 15//总的页面访问次数
    #define max_block_num 10//最大内存分配
    
    int Access_Series[total_instrucion];//内存访问序列
    char Lack[total_instrucion];//记录是否缺页
    struct one_block {//一个物理块
        int page_no;//物理块内的页面号
        int cnt;//计数,用于确定最先进入的页面(FIFO)
    }blocks[max_block_num];
    int table[max_block_num][total_instrucion];//显示矩阵
    void FIFO(int block_num){
        int diseffect;//缺页数
        for (int i = 0; i < total_instrucion; i++)
            Lack[i] = 'N';//初始化不缺页
        //数据结构blocks的初始化
        for (int i = 0; i < block_num; i++) {
            blocks[i].page_no = -1;//初始化页号为-1,当前有空闲页面
            blocks[i].cnt = 0;//初始化计数
        }
        //开始访问页面
        for (int i = 0; i < total_instrucion; i++) {
            char full = 'T';//是否内存满
            char hit = 'F';//是否命中
            for (int j = 0; j < block_num; j++) {
                if (blocks[j].page_no == Access_Series[i]) {//命中的情况
                    hit = 'T';
                    break;
                }else if (blocks[j].page_no == -1) {//未命中,且内存未满的情况
                    blocks[j].page_no = Access_Series[i];
                    blocks[j].cnt = j + 1;
                    Lack[i] = 'Y';//缺页
                    diseffect++;
                    full = 'F';//内存未满
                    break;
                }
            }
            if (full == 'T') {//内存已满
                if (hit == 'F') {//若未命中
                    diseffect++;
                    Lack[i] = 'Y';
                    int target = -1;//选中替换目标
                    for (int j = 0; j < block_num; j++) {
                        blocks[j].cnt--;//发生页面置换
                        if (blocks[j].cnt == 0)
                            target = j;
                    }
                    blocks[target].page_no = Access_Series[i];
                    blocks[target].cnt = block_num;
                }
            }
            for (int j = 0; j < block_num; j++)
                table[j][i] = blocks[j].page_no;
        }
    
        /*输出运行过程及结果*/
        printf("采用FIFO页面置换算法结果如下:");
        printf("\n");
        printf("页号:");
        for (int i = 0; i < total_instrucion; i++)
            printf("%3d", Access_Series[i]);
        printf("\n");
        printf("-----------------------------------------------------\n");
        for (int i = 0; i < block_num; i++) {
            printf("块%2d:", i+1);
            for (int j = 0; j < total_instrucion; j++)
                printf("%3d", table[i][j]);
            printf("\n");
        }
        printf("-----------------------------------------------------\n");
        printf("缺页:");
        for (int i = 0; i < total_instrucion; i++)
            printf("%3c", Lack[i]);
        printf("\n");
        printf("-----------------------------------------------------\n");
        printf("\t缺页次数:%d\t缺页率:%d/%d\n", diseffect, diseffect, total_instrucion);
        printf("-----------------------------------------------------\n");
    }
    int main(){
        //初始化
        //父进程随机产生内存访问页面序列,存于数组Acess_Series[total_instruction]中
        srand((unsigned)time(NULL));
        for (int i = 0; i < total_instrucion; i++)
            Access_Series[i] = rand() % total_instrucion;
        int block_num;
        while(1){
            printf("请输入分配的物理块数(-1退出):");
            scanf("%d",&block_num);
            if(block_num==-1) break;
            FIFO(block_num);
        }
        return 0;
    }
    

    2.LRU

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    //主要数据结构
    #define total_instrucion 15//总的页面访问次数
    #define max_block_num 10//最大内存分配
    
    int Access_Series[total_instrucion];//内存访问序列
    char Lack[total_instrucion];//记录是否缺页
    struct one_block {//一个物理块
        int page_no;//物理块内的页面号
        int tim;//计时,用于确定最近最久未使用的页面(LRU)
    }blocks[max_block_num];
    int table[max_block_num][total_instrucion];//显示矩阵
    void LRU(int block_num){
        int diseffect;//缺页数
        for (int i = 0; i < total_instrucion; i++)
            Lack[i] = 'N';//初始化不缺页
        //数据结构blocks的初始化
        for (int i = 0; i < block_num; i++) {
            blocks[i].page_no = -1;//初始化页号为-1,当前有空闲页面
            blocks[i].tim = 0;//初始化计时
        }
        //开始访问页面
        for (int i = 0; i < total_instrucion; i++) {
            char full = 'T';//是否内存满
            char hit = 'F';//是否命中
            for (int j = 0; j < block_num; j++)
                blocks[j].tim++;//计时器加1
            for (int j = 0; j < block_num; j++) {
                if (blocks[j].page_no == Access_Series[i]) {//命中的情况
                    hit = 'T';
                    blocks[j].tim=0;//刚刚访问,值变为0
                    break;
                }else if (blocks[j].page_no == -1) {//未命中,且内存未满的情况
                    blocks[j].page_no = Access_Series[i];
                    blocks[j].tim=0;//刚刚访问,值变为0
                    Lack[i] = 'Y';//缺页
                    diseffect++;
                    full = 'F';//内存未满
                    break;
                }
            }
            if (full == 'T') {//内存已满
                if (hit == 'F') {//若未命中
                    diseffect++;
                    Lack[i] = 'Y';
                    int target = 0;//选中替换目标
                    for (int j = 1; j < block_num; j++) {
                        if (blocks[j].tim>blocks[target].tim)
                            target = j;
                    }
                    blocks[target].page_no = Access_Series[i];
                    blocks[target].tim=0;//刚刚访问,值变为0
                }
            }
            for (int j = 0; j < block_num; j++)
                table[j][i] = blocks[j].page_no;
        }
    
        /*输出运行过程及结果*/
        printf("采用LRU页面置换算法结果如下:");
        printf("\n");
        printf("页号:");
        for (int i = 0; i < total_instrucion; i++)
            printf("%3d", Access_Series[i]);
        printf("\n");
        printf("-----------------------------------------------------\n");
        for (int i = 0; i < block_num; i++) {
            printf("块%2d:", i+1);
            for (int j = 0; j < total_instrucion; j++)
                printf("%3d", table[i][j]);
            printf("\n");
        }
        printf("-----------------------------------------------------\n");
        printf("缺页:");
        for (int i = 0; i < total_instrucion; i++)
            printf("%3c", Lack[i]);
        printf("\n");
        printf("-----------------------------------------------------\n");
        printf("\t缺页次数:%d\t缺页率:%d/%d\n", diseffect, diseffect, total_instrucion);
        printf("-----------------------------------------------------\n");
    }
    int main(){
        //初始化
        //父进程随机产生内存访问页面序列,存于数组Acess_Series[total_instruction]中
        srand((unsigned)time(NULL));
        for (int i = 0; i < total_instrucion; i++)
            Access_Series[i] = rand() % total_instrucion;
        int block_num;
        while(1){
            printf("请输入分配的物理块数(-1退出):");
            scanf("%d",&block_num);
            if(block_num==-1) break;
            LRU(block_num);
        }
        return 0;
    }
    

    展开全文
  • C语言实现FIFO、OPT、LRU三种页面置换算法
    #include<stdio.h>
    #include<time.h>
    #include<stdlib.h>
    #include<string.h>
    #include<assert.h>
    
    #define NUM_OF_INSTRUSTIONS 320
    
    void generate_instrustions(__u_int* instrustions,__u_int* original_page_address_flow)
    {
      __u_int page_no = 0;
      for(size_t i = 0;i < NUM_OF_INSTRUSTIONS;i += 4) {
        __u_int begin;
        do
        {
          begin = (__u_int)rand() % NUM_OF_INSTRUSTIONS;
        } while (begin == 319);
        instrustions[i] = begin + 1;
        original_page_address_flow[i] = (begin + 1) / 10;
        __u_int before;
        do
        {
          before = (__u_int)rand() % ((begin + 1) + 1) + 0;
        } while (before > 317);
        instrustions[i + 1] = before;
        original_page_address_flow[i + 1] = before / 10;
        instrustions[i + 2] = before + 1;
        original_page_address_flow[i + 2] = (before + 1) / 10;
        __u_int after = (__u_int)rand() % (319 - (before + 2) + 1) + (before + 2);
        instrustions[i + 3] = after;
        original_page_address_flow[i + 3] = after / 10;
      }
    }
    
    __u_int merge(__u_int* original_page_address_flow,__u_int* page_address_flow)
    {
      __u_int num_of_page_address_flow = 0;
      for(size_t i = 0;i < NUM_OF_INSTRUSTIONS;++i) {
        if(i == 0) {
          page_address_flow[num_of_page_address_flow] = original_page_address_flow[i];
          ++num_of_page_address_flow;
        }
        else {
          if(original_page_address_flow[i] != original_page_address_flow[i - 1]) {
            page_address_flow[num_of_page_address_flow] = original_page_address_flow[i];
            ++num_of_page_address_flow;
          }
        }
      }
      return num_of_page_address_flow;
    }
    
    void print_current_state(__u_int* array,__u_int length)
    {
      for(__u_int i = 0;i < length;++i) {
        printf("%d ",array[i]);
      }
      printf("\n");
    }
    
    void fifo_algorithm(__u_int num_of_blocks,__u_int* page_address_flow,__u_int num_of_page_address_flow)
    {
      assert(num_of_blocks);
      __u_int num_of_interrupt = 0;
      __u_int current_index = 0;
      __u_int blocks[num_of_blocks];
      memset((void*)blocks,-1,sizeof(blocks));
      for(__u_int i = 0;i < num_of_page_address_flow;++i) {
        printf("Current page address flow:%d\n",page_address_flow[i]);
        int find = 0;
        for(__u_int j = 0;j < num_of_blocks;++j) {
          if(blocks[j] == page_address_flow[i]) {
            find = 1;
            break;
          }
        } 
        if(!find) {
          ++num_of_interrupt;
          blocks[current_index] = page_address_flow[i];
          current_index = (++current_index) % num_of_blocks;
          print_current_state(blocks,num_of_blocks);
        }
      }
      printf("Number of page missing interrupts:%d\n",num_of_interrupt);
      float page_fault_rate = num_of_interrupt / (float)num_of_page_address_flow;
      printf("Page falut rate:%f\n",page_fault_rate);
    }
    
    void opt_algorithm(__u_int num_of_blocks,__u_int* page_address_flow,__u_int num_of_page_address_flow)
    {
      assert(num_of_blocks);
      __u_int num_of_interrupt = 0;
      __u_int blocks[num_of_blocks];
      memset((void*)blocks,-1,sizeof(blocks));
      for(__u_int i = 0;i < num_of_page_address_flow;++i) { 
        printf("Current page address flow:%d\n",page_address_flow[i]);
        int find = 0;
        for(__u_int j = 0;j < num_of_blocks;++j) {
          if(blocks[j] == page_address_flow[i]) {
            find = 1;
            break;
          }
        }
        if(!find) {
          ++num_of_interrupt;
          __u_int distance[num_of_blocks];
          for(__u_int j = 0;j < num_of_blocks;++j) {
            distance[j] = __UINT16_MAX__;
          }
          for(__u_int j = i + 1;j < num_of_page_address_flow;++j) {
            for(__u_int n = 0;n < num_of_blocks;++n) {
              if(page_address_flow[j] == blocks[n] && distance[n] > j) {
                distance[n] = j;
                break;
              }
            }
          }
          __u_int target_index = 0;
          __u_int max_distance = distance[target_index];
          for(__u_int j = 0;j < num_of_blocks;++j) {
            if(distance[j] == __UINT16_MAX__) {
              target_index = j;
              break;
            }
            if(distance[j] > max_distance) {
              target_index = j;
              max_distance = distance[j];
            }
          }
          blocks[target_index] = page_address_flow[i];
          print_current_state(blocks,num_of_blocks);
        }
      }
      printf("Number of page missing interrupts:%d\n",num_of_interrupt);
      float page_fault_rate = num_of_interrupt / (float)num_of_page_address_flow;
      printf("Page falut rate:%f\n",page_fault_rate);
    }
    
    void lru_algorithm(__u_int num_of_blocks,__u_int* page_address_flow,__u_int num_of_page_address_flow)
    {
      assert(num_of_blocks);
      __u_int num_of_interrupt = 0;
      __u_int blocks[num_of_blocks];
      memset((void*)blocks,-1,sizeof(blocks));
      int interval[num_of_blocks];
      for(__u_int i = 0;i < num_of_blocks;++i)
        interval[i] = __UINT16_MAX__;
      for(__u_int i = 0;i < num_of_page_address_flow;++i) {
        printf("Current page address flow:%d\n",page_address_flow[i]);
        int find = 0;
        for(__u_int j = 0;j < num_of_blocks;++j) {
          if(page_address_flow[i] == blocks[j]) {
            find = 1;
            interval[j] = 0;
            break;
          }
        }
        if(!find) {
          ++num_of_interrupt;
          __u_int target_index = 0;
          __u_int max_interval = interval[target_index];
          for(__u_int j = 0;j < num_of_blocks;++j) {
            if(interval[j] > max_interval) {
              target_index = j;
              max_interval = interval[j];
            }
          }
          blocks[target_index] = page_address_flow[i];
          interval[target_index] = 0;
          print_current_state(blocks,num_of_blocks);
        }
        for(__u_int j = 0;j < num_of_blocks;++j) {
          if(interval[j] != __UINT16_MAX__)
            ++interval[j];
        }
      }
      printf("Number of page missing interrupts:%d\n",num_of_interrupt);
      float page_fault_rate = num_of_interrupt / (float)num_of_page_address_flow;
      printf("Page falut rate:%f\n",page_fault_rate);
    }
    
    int main(void)
    {
      srand((unsigned int)time(NULL));
      __u_int instrustions[NUM_OF_INSTRUSTIONS];
      memset((void*)instrustions,0,sizeof(instrustions));
      __u_int original_page_address_flow[NUM_OF_INSTRUSTIONS];
      memset((void*)original_page_address_flow,0,sizeof(original_page_address_flow));
      generate_instrustions(instrustions,original_page_address_flow);
      __u_int page_address_flow[NUM_OF_INSTRUSTIONS];
      memset((void*)page_address_flow,-1,sizeof(page_address_flow));
      __u_int num_of_page_address_flow = merge(original_page_address_flow,page_address_flow);
      printf("The number of page address flow:%d\n",num_of_page_address_flow);
      __u_int num_of_blocks;
      scanf("%d",&num_of_blocks);
      fifo_algorithm(num_of_blocks,page_address_flow,num_of_page_address_flow);
      opt_algorithm(num_of_blocks,page_address_flow,num_of_page_address_flow);
      lru_algorithm(num_of_blocks,page_address_flow,num_of_page_address_flow);
      return 0;
    }
    
    

    采用如下规则生成指令集:
    A:50%的指令是顺序执行的
    B:25%的指令是均匀分布在前地址部分
    C:25%的指令是均匀分布在后地址部分
    具体的实施方法是:
    A:在[0,319]的指令地址之间随机选取一起点m
    B:顺序执行一条指令,即执行地址为m+1的指令
    C:在前地址[0,m+1]中随机选取一条指令并执行,该指令的地址为m’
    D:顺序执行一条指令,其地址为m’+1
    E:在后地址[m’+2,319]中随机选取一条指令并执行
    F:重复步骤A-E,直到320次指令

    页面大小为1K,用户虚存容量为32K

    (OPT算法应该写得过于冗余了,封装一个struct Page应该会更好

    展开全文
  • 前言最近,我偷偷潜伏...所以,我这边总结了操作系统的三大调度机制,分别是「进程调度/页面置换/磁盘调度算法」,供大家复习,希望大家在秋招能斩获自己心意的 offer。正文进程调度算法 进程调度算法也称 CPU 调度...
  • 页面置换算法C语言代码.txt
  • 操作系统LRU页面置换算法 C语言程序 数组实现 简单,清晰且实用,
  • OPT算法、FIFO算法、LRU算法、LFU算法的具体实现
  • 操作系统课程设计-页面置换算法C语言.doc
  • 广东工业大学 操作系统实验 实验内容 假设每个页面中可存放...如果4个内存块均已装入该作业,则需进行页面置换,最后显示其物理地址,并转下一条指令。在所有320指令执行完毕后,请计算并显示作业运行过程中发生的缺页
  • 设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率: 要求设计主界面以灵活选择某算法,且以下算法都要实现 1)先进先出算法(FIFO) ...3)最佳置换算法(OPT)
  • 操作系统课程设计_页面置换算法C语言.doc
  • LRU页面置换算法C语言实现

    千次阅读 2021-05-10 11:00:08
    LRU 最近最少使用页面置换算法 思路: 代码: #include<stdio.h> #include<string.h> void Change(int P[],int x,int y){//将p数组中x位置的元素挪到y位置 //我们默认传参进来的 x大于 y 也...
  • 页面置换算法C语言.doc
  • 操作系统课程设计页面置换算法C语言.doc
  • 三种页面置换算法的分析及C语言代码-附件资源
  • 操作系统课程设计页面置换算法C语言07010.doc
  • 操作系统课程设计-页面置换算法C语言 精品文档 精品文档 收集于网络如有侵权请联系管理员删除 收集于网络如有侵权请联系管理员删除 精品文档 收集于网络如有侵权请联系管理员删除 页面置换算法 一题目要求 通过实现...

空空如也

空空如也

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

页面置换算法c语言