Java模拟操作系统实验二:分区式存储管理_freelink=new linkedlist〈free〉()

1.问题概述

通过这次试验，加深对内存管理的认识，进一步掌握内存的分配、回收算法的思想。

设计程序模拟内存的动态分区法存储管理。内存空闲区使用自由链管理,采用最坏适应算法从自由链中寻找空闲区进行分配

假定系统的内存共640K,初始状态为操作系统本身占用64K。在t1时间之后,有作业A、B、C、D分别请求8K、16K、64K、124K的内存空间:在t2时间之后,作业C完成;在t3时间之后,作业E请求5K的内存空间;在t4时间之后,作业D完成。要求编程序分别输出t1、t2、t3、t4(时刻内存的空闲区的状态。

2.算法简介

最差适应算法（worst-fit）：它从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使链表中的节点大小趋于均匀。

具体参照：https://blog.csdn.net/u011070169/article/details/53177987?fps=1&locationNum=5

3.思路分析

最早出现的固定分区分配方式比较死板，易造成较多的内部碎片，太浪费资源，因此进一步的发展后出现了动态分区分配的方式，这种方式解决了前一种的主要弊端。接下来就是如何实现的问题了，主要是解决如何动态的分配内存以及回收。

本次实验的分配方式采用最坏适应算法。该实验基本思想虽然容易理解，但实现起来依旧是困难重重。首先要做的是确定数据的存储结构，用了两个链表分别存储了已分配的和空闲的内存，然后初始化等等。接下来是实现分配算法，写一个比较器，每次分配完内存后（将链表中第一个空闲块分配出部分空间），都必须将空闲块按从大到小的顺序重新排列。这点并不难，难点在回收内存后如何合并新产生的空闲内存块。这里存在四种情况，新产生的空闲内存块可能与它上面一块空闲块相邻，也可能与它下面一块空闲块相邻，还可能不与任何一块相邻，或者是同时与上下两块相邻。

前三种情况也不是大问题，画个图也就出来了，但是最后一种情况就很让我头疼了。因为链表中所有的空闲块并不是物理意义上的有序排列，而是离散的，任何位置都是有可能的。一开始我的想法是把空闲链表从头到尾扫描一次，通过比较首地址，很容易就能解决前三种情况，但是上下相邻的情况就无从下手了，思路也因此陷入了僵局。后来我想到其实上下相邻的情况必然是先经历了与上相邻和与下相邻两种情况。这样一来，我先用两个值分别记录下前两种情况下的空闲块的位置，如果检测到了前两种情况发生，就接着执行第四种情况。

大方向定下了，接下来是一些细节的问题，比如说不与上下相邻的情况不能放在循环体内，否则一旦执行就会不停添加新的空闲块，造成死循环。还有在Java中，遍历链表用迭代器会比容器内部下标遍历效率高的多，但是用了迭代器就无法用容器自身的方法，这个细节让我程序一直报错，找了很久。

4.代码实现

package AllocationAlg;
 
public class Busy {
	String name;//进程名
	int address;//分区起始地址
	int len;//分区长度
	public Busy(String name, int address, int len) {
		super();
		this.name = name;
		this.address = address;
		this.len = len;
	}
	public Busy() {
		// TODO Auto-generated constructor stub
	}
	
}

package AllocationAlg;
 
public class Free {
	int address;//分区起始地址
	int len;//分区长度
	public Free(int address, int len) {
		super();
		this.address = address;
		this.len = len;
	}
	
}

package AllocationAlg;
 
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
 
public class Partition {
	LinkedList<Free> freeLink;//空闲区队列
	LinkedList<Busy> busyLink;//已分配区队列
	Free free;
	Busy busy;
	
	public Partition() {
		super();
		start();
	}
	void start() {
		freeLink=new LinkedList<Free>();
		busyLink=new LinkedList<Busy>();
		
		Busy os=new Busy("OS",0,64);//系统占用区64K
		busyLink.add(os);//加入已分配队列
		free=new Free(64,300);//初始的内存空闲区就一块，大小300K，首地址64K
		freeLink.add(free);//加入空闲区队列
	}
	void requierMemo(String name,int require) {//模拟内存分配
		if(require<=freeLink.get(0).len) {//可划分内存给所请求分配的大小
			int address=freeLink.get(0).address;//获得该最大空闲区的首地址，从这开始分配require长度内存
			freeLink.get(0).address=address+require;//更新该空闲区的首地址
			freeLink.get(0).len=freeLink.get(0).len-require;//更新该空闲区的长度
			busy=new Busy(name, address, require);//生成分配区间
			busyLink.add(busy);//将该分区分配给请求者,加入已分配队列
			Collections.sort(freeLink, new compatorFree());//因为原来最大的空闲区被划分走一块后可能不是最大了，必须重新排序
			System.out.println("为"+busy.name+"分配内存成功！");
		}
		else
			System.out.println("当前无法找到足够内存分配，请求失败，请等待！");
	}
	void freeMemo(String name) {//模拟内存回收
		Busy recycle=new Busy();//暂时存放要回收的内存的信息
		/*如果该回收区分别与上下两块空闲区邻接（第三种情况），下面算法必会先会依次执行一二两种情况，导致回收区被重复计算，要消除该影响
		就得先记录下这两块已经完成操作的空闲区间位置，再把这两块合并即可（因为两者有重叠区域）*/
		int freeUp=-1;//记录上面相邻接块的位置，-1代表不邻接
		int freeDown=-1;//记录下面相邻接块的位置，-1代表不邻接
		for(int i=0;i<busyLink.size();++i) {
			busy=busyLink.get(i);
			if(busy.name==name) {
				recycle=busy;//先找到要回收的内存,保留信息
				busyLink.remove(recycle);//如果用了迭代器，必须用它的方法增删改查，容器的方法会失效
			}
		}
//		for(ListIterator<Free> iter=freeLink.listIterator();iter.hasNext();){//迭代器效率O(1)远高于随机访问O(N^2)
		for(int i=0;i<freeLink.size();++i) {
			free=freeLink.get(i);//获得链表中指针指向的对象
			/*第一种情况回收区与上面一个空闲区间相邻接*/
			if(recycle.address==(free.address+free.len)) {
				freeUp=freeLink.indexOf(free);//记录下该空闲区间的位置
				free.len=free.len+recycle.len;//更新该空闲区间长度
				freeLink.set(freeUp, free);
			}
			/*第二情况回收区与下面一个空闲区间相邻接*/
			if((recycle.address+recycle.len)==free.address) {
				freeDown=freeLink.indexOf(free);//记录下该空闲区间的位置
				free.address=recycle.address;//更新该空闲区间首地址
				free.len=recycle.len+free.len;//更新该空闲区间长度
				freeLink.set(freeDown, free);
			}
			/*第三情况回收区分别与上下面空闲区间相邻接*/
			if(freeUp!=-1&&freeDown!=-1) {
				Free freeUpObj=freeLink.get(freeUp);
				Free freeDownObj=freeLink.get(freeDown);
				/*不用多此一举，前面已经决定了freeUp的首地址必然小于freeDown的首地址
				if(freeUpObj.address<freeDownObj.address) {//确保低地址在前，高地址在后
					Free temp;
					temp=freeUpObj;freeDownObj=freeUpObj;freeUpObj=temp;
				}*/
				freeUpObj.len=freeUpObj.len+freeDownObj.len-recycle.len;//更新两块合并后的长度
				freeLink.set(freeUp, freeUpObj);//修改链表中三块合一后的最终空闲块
				freeLink.remove(freeDown);//下面这块已经被上面那块合并，把它从链表中删除
			}
		}
		/*第四情况回收区与空闲区间不相邻接(注意：这情况不能放在上面的for循环内，否则会造成队列不断变大，死循环)*/
		if(freeUp==-1&&freeDown==-1) {
			Free addFree=new Free(recycle.address, recycle.len);
			freeLink.addLast(addFree);
		}
		System.out.println("回收"+recycle.name+"的内存成功！");
		Collections.sort(freeLink,new compatorFree());//长度改变需要重排
	}
	
	void printLink() {//输出内存情况
		System.out.println("********************************");
		System.out.println("内存已分配区间情况：");
		for(Iterator<Busy> iter=busyLink.iterator();iter.hasNext();) {
			busy=(Busy)iter.next();
			System.out.print(busy.name+":"+busy.address+"~"+(busy.address+busy.len)+"  ");
		}
		System.out.println('\n'+"内存空闲区间信息，按从大到小排列：");
		for(Iterator<Free> iter=freeLink.iterator();iter.hasNext();){//迭代器效率O(1)远高于随机访问O(N^2)
			free=(Free)iter.next();//获得链表中下一个元素
			System.out.print(free.address+"~"+(free.address+free.len)+"  ");//空闲区间
		}
		System.out.println('\n'+"********************************");
	}
	
}
class compatorFree  implements Comparator<Free>{//按空闲区间从大到小排列
 
	@Override
	public int compare(Free o1, Free o2) {
		return o1.len<o2.len?1:-1;
	}
	
}

5.实验结果

package AllocationAlg;
 
public class TestPartition {
	public static void main(String[] args) {
		Partition pa=new Partition();
		pa.requierMemo("A", 20);pa.requierMemo("B",16);
		pa.requierMemo("C", 64);pa.requierMemo("D", 124);
		pa.printLink();
		pa.freeMemo("C");pa.printLink();
		pa.requierMemo("E", 50);pa.printLink();
		pa.freeMemo("D");pa.printLink();
	}
}