欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

操作系统 页面置换算法实现

程序员文章站 2024-03-18 12:04:40
...

操作系统 页面置换算法实现

import java.util.Scanner;

public class page_change {
    final  int M=3;
    final int N=20;

    class block
    {
        int iPageNum;      //物理块里存储的页面号
        int iBlockFlag;		//在三种算法中用到的标记。例如在FIFO中为在内存中的时间

        public block(int iPageNum, int iBlockFlag) {
            this.iPageNum = iPageNum;
            this.iBlockFlag = iBlockFlag;
        }

        public int getiPageNum() {
            return iPageNum;
        }

        public void setiPageNum(int iPageNum) {
            this.iPageNum = iPageNum;
        }

        public int getiBlockFlag() {
            return iBlockFlag;
        }

        public void setiBlockFlag(int iBlockFlag) {
            this.iBlockFlag = iBlockFlag;
        }
    };
//算法模拟移位寄存器原理

    public void pageChange()
    {
        Scanner in=new Scanner(System.in);
        block []myBlock=new block[M];
        int []iPageString={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
        //页面引用串

        int []iTempPage =new int[N]; //临时页面引用串
        int []flag=new int[N];      //缺页标记;1为缺页,0为不缺页,在统计缺页次数时用

        int i;

        boolean bExitFlag=true;   //退出标记
        char ch;		  //接收选择算法时传进来的值

        while(bExitFlag)
        {
            System.out.println("请选择页面置换算法:");
            System.out.println("f:FIFO置换算法  \to:OPT置换算法  \tl:LRU置换算法  \tx:退出置换算法程序.");
            ch=(in.next()).charAt(0);
            //初始化数据
            if((ch=='f')||(ch=='o')||(ch=='l'))
            {
                for(i=0;i<N;i++)
                {
                    iTempPage[i]=iPageString[i];  //初始化临时页面引用串
                    flag[i]=0;                    //初始化缺页标记为0,即不缺页
                }
            }

            switch(ch)
            {
                case 'f':
                    System.out.println("FIFO置换算法的结果是:");
                    FIFO(iTempPage,flag,myBlock);
                    //用PageNum(flag)统计缺页次数
                    System.out.println("\n缺页次数为"+PageNum(flag));
                    break;
                case 'o':
                    System.out.println("OPT置换算法的结果是:");
                    Optimal(iTempPage,flag,myBlock);
                    System.out.println("\n缺页次数为"+PageNum(flag));
                    break;
                case 'l':
                    System.out.println("LRU置换算法的结果是:");
                    LRU(iTempPage,flag,myBlock);
                    System.out.println("\n缺页次数为"+PageNum(flag));
                    break;
                case 'x':
                    System.out.println("退出置换算法。");
                    bExitFlag=false;
                    break;
                default:
                    System.out.println("输入有误,请重新选择置换算法:");
            }
        }

    }

    //对数组中的数累加
    int PageNum(int array[])
    {
        int num=0;
        for(int j=0;j<N;j++)
            num=num+array[j];
        return num;
    }

    //定位函数,在最佳算法中用于定位;
//定位物理块中的某一个页面在引用串中还未访问串中页面的位置
    int allocate(int iPage,int iLoc,int []iTempPage)
    {
        int i;
        for(i=iLoc;i<N;i++)
        {
            if (iPage==iTempPage[i])
                return i;
        }
        //永远不再访问的页面位置假定为N
        return N;
    }
    //在LRU置换算法的时候使用
    int reverse_allocate(int iPage,int iLoc,int []iTempPage)
    {
        int i;
        for(i=iLoc;i>=0;i--)
        {
            if (iPage==iTempPage[i])
                return i;
        }
        //永远不再访问的页面位置假定为0
        return 0;
    }
    //找数组中最大值所在的下标,返回最大值在数组中的位置(下标)
    int max_sign(block []array)
    {
        int j,loc;
        int temp=array[0].iBlockFlag;
        loc=0;

        for(j=1;j<M;j++)
        {
            if (temp<array[j].iBlockFlag)
            {
                temp=array[j].iBlockFlag;
                loc=j;
            }
        }
        return loc;
    }
    int little_sign(block []array)
    {
        int j,loc;
        int temp=array[0].iBlockFlag;
        loc=0;

        for(j=1;j<M;j++)
        {
            if (temp>array[j].iBlockFlag)
            {
                temp=array[j].iBlockFlag;
                loc=j;
            }
        }
        return loc;
    }

    //输出剩余的数据
//loc为页面引用串中
    void output(int iPage,int flag,block []myBlock,int blockNum)
    {
        int j;
        //如果缺页则输出缺页标志,否则不输出
        if (flag==1)
            System.out.print("\n  "+flag);
        else
            System.out.println("");
        System.out.print("\t  "+iPage);
        for(j=0;j<blockNum;j++)
            System.out.print("\t     "+myBlock[j].iPageNum);
    }

    //初始化物理块的内容,因任一种算法在物理块内容为空时,结果都一样的
//同时将目前物理块中的内容输出
    void InitialBlock(int []iTempPage,int []flag,block []myBlock)
    {
        int i;
        for(i=0;i<M;i++)
        {
            //初始化物理块的内容,因任一种算法在物理块内容为空时,结果都一样的
            myBlock[i]=new block(iTempPage[i],(M-1)-i);
            //myBlock[i].iBlockFlag的值:0为最后进来的,数越大表示进来的越早
            //在最佳置换算法中则初始化此值没有意义
            flag[i]=1;   //此时为缺页
        }
        //输出
        System.out.println("\n缺页\t引用串\t物理块1\t物理块2\t物理块3");
        for(i=0;i<M;i++)
            output(iTempPage[i],flag[i],myBlock,i+1);
    }

    //FIFO置换算法
    void FIFO(int []iTempPage,int []flag,block []myBlock)
    {
        int i,j,k,loc;
        boolean ExistFlag=false;

        //初始化物理块的内容,因任一种算法在物理块内容为空时,结果都一样的
        //同时将目前物理块中的内容输出
        InitialBlock(iTempPage,flag,myBlock);

        //从引用串中的第4个页面开始
        for(i=3;i<N;i++)
        {
            ExistFlag=false;
            for(j=0;j<M;j++)
            {
                //物理块中存在
                if (myBlock[j].iPageNum==iTempPage[i])
                {
                    //模拟移位寄存器
                    for(k=0;k<M;k++)
                        myBlock[k].iBlockFlag++;

                    ExistFlag=true;
                    flag[i]=0;
                    break;
                }
            }
            //物理块中不存在
            if (!ExistFlag)
            {
                //查找最先进来的页面,也就是block中iBlockFlag最大的物理块
                loc=max_sign(myBlock);
                myBlock[loc].iPageNum=iTempPage[i];

                //置缺页标志
                flag[i]=1;

                //模拟移位寄存器
                for(k=0;k<M;k++)
                    if (k!=loc)
                        myBlock[k].iBlockFlag++;
                    else
                        myBlock[k].iBlockFlag=0;
            }

            //输出
            output(iTempPage[i],flag[i],myBlock,M);
        }
        System.out.println("");
    }

    //Optimal置换算法
    void Optimal(int []iTempPage,int []flag,block []myBlock)
    {
        boolean ExistFlag=false;
        //初始化
        InitialBlock(iTempPage,flag,myBlock);
        for(int i=3;i<N;i++)
        {
            ExistFlag=false;
            for(int j=0;j<M;j++)
            {
                if(iTempPage[i]==myBlock[j].iPageNum)
                {
                    ExistFlag=true;
                    flag[i]=0;
                    break;
                }
            }
            if(!ExistFlag)              //如果不存在的话
            {
                for(int j=0;j<M;j++)
                {
                    myBlock[j].iBlockFlag=allocate(myBlock[j].iPageNum,i,iTempPage);  //更新每个块的下标
                }
                int item=max_sign(myBlock);
                myBlock[item].iPageNum=iTempPage[i];         //将得到的页面换入
                flag[i]=1;
            }
            //输出
            output(iTempPage[i],flag[i],myBlock,M);
        }
    }

    //LRU置换算法
    void LRU(int []iTempPage,int []flag,block []myBlock)
    {
        boolean ExistFlag=false;
        //初始化
        InitialBlock(iTempPage,flag,myBlock);
        for(int i=3;i<N;i++)
        {
            ExistFlag=false;
            for(int j=0;j<M;j++)
            {
                if(iTempPage[i]==myBlock[j].iPageNum)
                {
                    ExistFlag=true;
                    flag[i]=0;
                    break;
                }
            }
            if(!ExistFlag)              //如果不存在的话
            {
                for(int j=0;j<M;j++)
                {
                    myBlock[j].iBlockFlag=reverse_allocate(myBlock[j].iPageNum,i,iTempPage);  //更新每个块的下标
                }
                int item=little_sign(myBlock);
                myBlock[item].iPageNum=iTempPage[i];         //将得到的页面换入
                flag[i]=1;
            }
            //输出
            output(iTempPage[i],flag[i],myBlock,M);
        }
    }



    public static void main(String[] args) {
        new page_change().pageChange();

    }
}

上一篇: 条件编译

下一篇: 栈实现队列