操作系统模拟主存储器空间的分配和回收实操

一、实验内容：

主存储器空间的分配和回收。

二、实验目的：

一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实习帮助学生理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。

• 实验题目：

模拟在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。

[提示]：

(1) 分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未分配的空闲块，可用一张位示图来指出。位示图可由若干存储单元来构成，其中每一位与一个物理块对应，用0/1表示对应块为空闲/已占用。

(2) 假设某系统的主存被分成大小相等的64块，则位示图可用8个字节来构成，另用一单元记录当前空闲块数。如果已有第0，1，4，5，6，9，11，13，24，31，共10个主存块被占用了，那么位示图情况如下：

(3) 当要装入一个作业时，根据作业对主存的需要量，先查当前空闲块数是否能满足作业要求，若不能满足则输出分配不成功。若能满足，则查位示图，找出为“0”的一些位，置上占用标志“1”，从“当前空闲块数”中减去本次占用块数。

按找到的计算出对应的块号，其计算公式为：

      块号= j´8+i

其中，j表示找到的是第n个字节，I表示对应的是第n位。

根据分配给作业的块号，为作业建立一张页表，页表格式：

(4) 当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志清成“0”，表示对应的块已成为空闲块。归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：

字节号 j=[块号/8]    （[  ]表示取整）

位数   i={块号/8}   （{  }表示取余）

(5) 设计实现主存分配和回收的程序。假定位示图的初始状态如（2）所述，现有一信息量为5页的作业要装入，运行你所设计的分配程序，为作业分配主存且建立页表（格式如（3）所述）。然后假定有另一作业执行结束，它占用的块号为第4，5，6和31块，运行你所设计的回收程序，收回作业归还的主存块。

要求能显示和打印分配或回收前后的位示图和当前空闲块数，对完成一次分配后还要显示或打印为作业建立的页表。

• 核心代码及注释：

定义一个Work实体类，创建页表与块号的属性，定义运行时间和封装方法

public class Work {
   private int pageNumber = 0;//页号
   private int getNumber = 0;//取出时的页号起始位
   private Integer[] pageList = null;//块号列表
   private Map<Integer,Integer> map = new HashMap<Integer,Integer>();//页表
   //此作业的运行时间
   private int runTime;
   private Random random = new Random();

   public int getRunTime() {
      return runTime;
   }

   public void setRunTime(int runTime) {
      this.runTime = runTime;
   }

   public Work(Integer[] pageBlock) {
      super();
      this.pageList = pageBlock;
      for(int i = 0;i<pageList.length;i++) {
         map.put(pageNumber, pageList[i]);
         pageNumber++;
      }
      runTime = random.nextInt(9)+1;//随机生成此作业的总运行时间
   }

   public Integer[] pop(){//将块号全部还给内存
      return pageList;
   }
   public int remain(){
      runTime--;
      return  runTime;
   }

   @Override
   public String toString() {
      return "此作业的页表为:"+map+"\n"+"此作业的剩余运行时间为:"+runTime;
   }
}

创建存储管理类，用来随机生成作业，随机运行时间，将其位示图不断占用与释放

public class StoreManager {
    public static void main(String[] args) {
        Random random = new Random();//用来随机生成作业需要的内存数量
        List<Work> list = new ArrayList();
        int ranSum =  random.nextInt(9)+1;//用来随机生成作业需要的内存数量
        Integer[][] storePic = new Integer[8][8];//内存图
        for (int i = 0; i < storePic.length; i++) {//图的每一行
            for (int j = 0; j < storePic[i].length; j++) {//图的每一列
                storePic[i][j] = 0;
            }
        }
        int sumM = storePic.length * storePic[0].length;//现在的空闲块数
        Integer[] occupy = {0,1,4,5,6,9,11,13,24,31};//初始占用的内存块
        sumM = changePic(storePic, occupy,sumM);
        System.out.println("已有10个主存块被占用，则当前的空闲块数:"+sumM+"\n");
        showPic(storePic);

        for (int j = 0; j < 1000; j++) {
            if (sumM >= ranSum ){//用来生成作业,否则此作业不生成
                Integer[] pageBlock = new Integer[ranSum];//如果内存还有大于作业需要的空闲块,则开始分配内存
                for (int i = 0; i < ranSum; i++) {
                    pageBlock[i] = returnLeisure(storePic);//将查找到的空闲块号返回
                }
                sumM -= ranSum;
                Work work = new Work(pageBlock);
                list.add(work);
                System.out.println("随机生成了一个新作业:\n"+work+"当前的空闲块数:"+sumM);
                showPic(storePic);
            }
            for (int i = 0; i < list.size(); i++) {//用来返回内存块
                if ((list.get(i).getRunTime()-1) == 0){//当一个进程运行时间用完，应该立即返回所占用的内存块
                    list.get(i).setRunTime(list.get(i).getRunTime()-1);
                    occupy = list.get(i).pop();
                    returnBlock(storePic, occupy);
                    sumM += occupy.length;
                    System.out.println("移除了一个已经结束的作业:\n"+list.get(i)+"\n当前的空闲块数:"+sumM);
                    list.remove(i);
                    showPic(storePic);
                }else{
                    list.get(i).setRunTime(list.get(i).getRunTime()-1);
                }
            }
        }

    }

    /**
     * 用于将作业占用的内存块置为空闲
     * @param storePic  //内存表
     * @param occupy    //占用的所有内存块号
     */
    private static void returnBlock(Integer[][] storePic, Integer[] occupy) {
        for (int j = 0; j < occupy.length; j++) {
            storePic[occupy[j]/8][occupy[j]%8] = 0;
        }
    }

    /**
     *
     * @param storePic 用来返回内存中空闲块
     * @return 空闲内存块号
     */
    private static int returnLeisure(Integer[][] storePic) {
        for (int i = 0; i < storePic.length; i++) {//图的每一行
            for (int j = 0; j < storePic[i].length; j++) {//图的每一列
                if (storePic[i][j] == 0){
                    storePic[i][j] = 1;
                    return i * storePic.length + j;
                }
            }
        }
        return -1;
    }


    /**
     *
     * @param storePic 内存表
     * @param occupy   作业的占用
     * @param sumM  现在的空闲块数
     * @return  剩余的空闲数
     */
    private static int changePic(Integer[][] storePic, Integer[] occupy, int sumM) {
        for (int i = 0; i < occupy.length; i++) {
            storePic[occupy[i]/8][occupy[i]%8] = 1;
        }
        return sumM - occupy.length;
    }

    private static void showPic(Integer[][] storePic) {
        System.out.print("0"+"\t"+"1"+"\t"+"2"+"\t"+"3"+"\t"+"4"+"\t"+"5"+"\t"+"6"+"\t"+"7"+"\t"+"\n");
        System.out.print("<--------------------------------->\n");
        for (int i = 0; i < storePic.length; i++) {//图的每一行
            for (int j = 0; j < storePic[i].length; j++) {//图的每一列
                System.out.print(storePic[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.print("<--------------------------------->\n");
    }

}

• 打印效果图：

初始化位示图，已有10块被占用

随机生成一个新作业，有运行时间和页表，并显示剩余内存块

当旧作业结束后，移除它并释放内存，显示剩余的内存块数

六、实验总结：

1）我使用了一个二维数组作为位示图的数据结构，这样简单明了。而进程页表使用一个二维数组和map集合，用数组下标即可表示页号，节省了存储空间。

（2）在程序中充分考虑到逻辑关系。在用户申请内存时，若要求的空间大小大于空闲空间大小，则不会生成这个作业；在回收内存空间和显示进程页表时，运行时间结束的时候，释放内存，打印新的位示图。这样提高了程序的健壮性。

（3）通过本实验，我进一步加深了对使用位示图方式表示和实现主存分配回收的理解，同时也得到了将系统理论实践的机会，熟练了编程能力。

好了，关于此次操作系统的主存储器空间的分配和回收就说到这里了，如有不足之处，欢迎指正！

感恩能与大家在华为云遇见！希望能与大家一起在华为云社区共同成长。