前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >虚拟存储管理器的页面调度

虚拟存储管理器的页面调度

作者头像
AI那点小事
发布2020-04-20 16:27:04
4730
发布2020-04-20 16:27:04
举报
文章被收录于专栏:AI那点小事

请求分页式存储管理:每访问一个地址时,首先要计算该地址所在的页的页号,然后查页表,判断该页是否在主存;如果该页不在主存且内存块未满,则调入该页;如果该页不在主存且内存块已满,则按页面淘汰算法淘汰一页后调入所需的页。 设该作业共有320条指令,即它的地址空间为32页,目前它的所有页面都还未调入内存。在模拟过程中,每访问一个地址时,首先要计算该地址所在的页的页号,然后查页表,判断该页是否在主存——如果该页已在主存,则打印内存块情况;如果该页不在主存且内存块未满,则调入一页并打印内存块情况;如果该页不在主存且内存块已满,则按页面淘汰算法淘汰一页后调入所需的页,打印内存块情况; 逐个地址访问,直到所有地址访问完毕。在所有320条指令执行完毕后,请计算并显示作业运行过程中发生的缺页率。 置换算法:请分别考虑FIFO和LRU算法。


首先设计指令类,代码如下:

代码语言:javascript
复制
package 页面调度;

import java.util.Random;

public class Order {
    private int order;                      //指令内容
    private int address;                    //指令地址
    private boolean flag = false;           //状态位,判断是否被访问

    public Order() {
        Random r = new Random();
        this.order = r.nextInt(320);
        this.address = this.order / 10 +1;
    }

    public boolean isFlag() {
        return flag;
    }

    public void setFlag(boolean flag) {
        this.flag = flag;
    }

    public int getOrder() {
        return order;
    }

    public int getAddress() {
        return address;
    }

    public void Print(){
        System.out.println("    "+this.order+"      "+this.address+"        "+this.flag);
    }
}

然后构造页面类,代码如下:

代码语言:javascript
复制
package 页面调度;

import java.util.ArrayList;

public class Page {
    private ArrayList<Order> page = new ArrayList<Order>();                                         //页面 数组
    private int Number;                                                                             //页面个数

    public Page(int number) {
        Number = number;
        int count = 0;
        while( count != number){
            Order myorder = new Order();
            if (this.IsExited(myorder.getAddress()) == false){
                page.add(myorder);
                count++;
            }
        }
    }

    public boolean IsExited(int order){
        boolean flag = false;
        if ( this.getPage().size() == 0){
            flag = false;
        }else{
            for ( int i = 0 ; i < this.getPage().size() ; i++){
                if ( this.getPage().get(i).getOrder() == order){
                    flag = true;
                    break;
                }
            }
        }
        return flag;
    }

    public ArrayList<Order> getPage() {
        return page;
    }

    public int getNumber() {
        return Number;
    }

    public ArrayList<Order> VisitOrderAlgorithm(){                                                  //随机访问页面算法
        ArrayList<Order> myorder = new ArrayList<Order>();                                          //随机获取的页面数组
        int count = 0;
        while( count != 3){
            int i = 0;
            do{
                if ( this.IsALLVisited() == false){
                    if ( this.page.get(i).isFlag() == false){
                        myorder.add(this.page.get(i));
                        this.page.get(i).setFlag(true);
                        break;
                    }else{
                        i++;
                    }
                }else{
                    break;
                }
            }while(true);
            count++;
        }
        return myorder;
    }

    public void Print_Order(ArrayList<Order> a){                                                                //打印指令
        for ( int i = 0 ; i < a.size(); i++){
            System.out.println(i+"  "+a.get(i).getOrder()+" "+a.get(i).getAddress()+"   "+a.get(i).isFlag());
        }
    }

    public void Print(){                                                                            //打印所有指令
        for ( int i = 0 ; i < this.page.size() ; i++){
            this.page.get(i).Print();
        }
    }

    public boolean IsALLVisited(){                                                                  //判断页面是否全部访问
        boolean flag = true;
        for ( int i = 0 ; i < this.page.size() ; i++){
            if ( this.page.get(i).isFlag() == false){
                flag = false;
                break;
            }
        }
        return flag;
    }
}

对于FIFO,LRU算法我们利用接口来实现,代码如下: FIFO接口如下:

代码语言:javascript
复制
package 页面调度;

public interface FIFO {
    public void CarryOutFIFO(Page MyPage);
}

LRU接口如下:

代码语言:javascript
复制
package 页面调度;

public interface LRU {
    public void CarryOutLRU(Page MyPage);
}

最后实现FIFO与LRU算法,代码如下:

代码语言:javascript
复制
package 页面调度;

import java.util.ArrayList;

public class Shdeule implements FIFO,LRU{
    private int MissPage = 0;                                               //缺页数
    private double MissPageRate = 0;                                        //缺页率
    private ArrayList<Order> MemoryBlock = new ArrayList<Order>();          //内存块
    private ArrayList<Order> LongNotUse = new ArrayList<Order>();           //最久未使用页面

    public int getMissPage() {
        return MissPage;
    }

    public void AddMissPage() {
        MissPage++;
    }

    public void setMissPage(int missPage) {
        MissPage = missPage;
    }

    public ArrayList<Order> getMemoryBlock() {
        return MemoryBlock;
    }

    public double getMissPageRate() {
        return MissPageRate;
    }

    public void setMissPageRate(double missPageRate) {
        MissPageRate = missPageRate;
    }

    public int SearchAddress(int address ,ArrayList<Order> longNotUse2){                                        //在内存块中寻找页面
        int flag = -1;
        for ( int i = 0 ; i < this.MemoryBlock.size() ; i++){
            if (this.MemoryBlock.get(i).getAddress() == address){
                flag = i;
                break;
            }
        }
        return flag;
    }

    public void Print(){
        System.out.println("缺页数为:"+this.getMissPage());
        System.out.println("缺页率为:"+this.getMissPageRate());
    }

    @Override
    public void CarryOutFIFO(Page MyPage) {                                                             //FIFO调度算法
        // TODO Auto-generated method stub
        ArrayList<Order> myorder;
        boolean flag = false;
        do{                                                                                         //开始执行FIFO
            myorder = MyPage.VisitOrderAlgorithm();
            if ( myorder != null){
                for ( int i = 0 ; i < myorder.size() ; i++){
                    int index = this.SearchAddress(myorder.get(i).getAddress(),this.getMemoryBlock());
                    if ( !this.IsFull()){
                        if ( index == -1){
                            this.AddMissPage();
                            this.MemoryBlock.add(myorder.get(i));
                        }
                    }else{
                        if ( index == -1){
                            this.AddMissPage();
                            this.MemoryBlock.add(myorder.get(i));
                            this.MemoryBlock.remove(0);
                        }
                    }
                }
            }
            flag = MyPage.IsALLVisited();
        }while (flag == false);
        this.setMissPageRate(this.getMissPage() * 1.0 / MyPage.getNumber());
    }

    public boolean IsFull(){
        boolean flag = false;
        if(this.getMemoryBlock().size() == 4){
            flag = true;
        }
        return flag;
    }

    @Override
    public void CarryOutLRU(Page MyPage) {                                                      //LRU调度算法
        // TODO Auto-generated method stub
        ArrayList<Order> myorder;
        boolean flag = false;
        do{
            myorder = MyPage.VisitOrderAlgorithm();
            if ( myorder != null){
                for ( int i = 0 ; i < myorder.size(); i++){
                    int index = this.SearchAddress(myorder.get(i).getAddress(), this.getMemoryBlock());
                    if ( !this.IsFull()){
                        if ( index == -1){
                            this.AddMissPage();
                            this.MemoryBlock.add(myorder.get(i));
                            LongNotUse.add(myorder.get(i));
                        }else{
                            Order tmp = myorder.get(i);
                            int tmp_index = this.SearchAddress(tmp.getAddress(), LongNotUse);
                            if ( tmp_index != -1){
                                LongNotUse.add(tmp);
                            }
                        }
                    }else{
                        Order tmp;
                        if ( index == -1){
                            tmp = this.LongNotUse.get(0);
                            int tmp_index = this.SearchAddress(tmp.getAddress(),this.MemoryBlock);
                            if ( tmp_index != -1){
                                this.getMemoryBlock().remove(tmp_index);
                                this.getMemoryBlock().add(tmp_index,myorder.get(i));
                                this.AddMissPage();
                                LongNotUse.remove(0);
                                LongNotUse.add(myorder.get(i));
                            }
                        }else{
                            tmp = myorder.get(i);
                            int tmp_index = this.SearchAddress(tmp.getAddress(), LongNotUse);
                            LongNotUse.remove(tmp_index);
                            LongNotUse.add(myorder.get(i));
                        }
                    }
                }
                flag = MyPage.IsALLVisited();
            }
        }while(flag == false);
        this.setMissPageRate(this.getMissPage() * 1.0 / MyPage.getNumber());
    }

    public void CarryOut(Page MyPage){
        System.out.println("------------------------------------开始FIFO-------------------------------");
        this.CarryOutFIFO(MyPage);
        this.Print();
        System.out.println("------------------------------------结束FIFO-------------------------------");

        for (int i = 0 ; i < MyPage.getNumber() ; i++){
            MyPage.getPage().get(i).setFlag(false);                             //把所有指令标志位清零
        }
        this.getMemoryBlock().clear();                                          //把内存块清零
        this.setMissPage(0);                                                    //把缺页数清零

        System.out.println("------------------------------------开始LRU--------------------------------");
        this.CarryOutLRU(MyPage);
        this.Print();
        System.out.println("------------------------------------结束LRU--------------------------------");
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Page MyPage = new Page(320);
        Shdeule myshdeule = new Shdeule();
        myshdeule.CarryOut(MyPage);
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档