模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。
(1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：
为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：
其中，起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区。
(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。
(3) 采用最先适应算法（顺序分配算法）分配主存空间。
按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。
由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。
(4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。
(5) 请按最先适应算法设计主存分配和回收的程序。假设初始时主存中没有作业，现按下面序列进行内存的申请与释放：
作业1申请300K，作业2申请100K，作业1释放300K，作业3申请150K，
作业4申请30K， 作业5申请40K， 作业6申请60K， 作业4释放30K。
请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。
图一.内存分配流程图
图二.内存回收流程图
package System.Neicun;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Mermory {
int szie=512; //内存空间大小初始值
public List<Node> freeMerroyList=new LinkedList<>(); //内存分配表
public void print(String str){
System.out.println("----------"+str+"---------");
int i;
System.out.println("起址:"+0+" 大小(长度):"+freeMerroyList.get(0).start+" 状态:"+true);
for(i=0;i<freeMerroyList.size()-1;i++){
Node now=freeMerroyList.get(i);
Node next=freeMerroyList.get(i+1);
System.out.println("起址:"+now.start+" 大小(长度):"+now.size+" 状态:"+now.state);
System.out.println("起址:"+now.end+" 大小(长度):"+(next.start-now.end)+" 状态:"+true);
}
Node now=freeMerroyList.get(i);
System.out.println("起址:"+now.start+" 大小(长度):"+now.size+" 状态:"+now.state);
}
public void Allocate(Node jobnode){ //分配函数
int i;
for(i=0;i<freeMerroyList.size();i++){
Node merroyNode=freeMerroyList.get(i);
if(jobnode.size<merroyNode.size&&merroyNode.state==false){ //如果可以分配下，且未分配，则分配此块内存
jobnode.setJobBound(merroyNode.start);
merroyNode.size-=jobnode.size;
merroyNode.start+=jobnode.size;
break;
}
}
if(i==freeMerroyList.size()){ //未找到，分配失败
System.out.println("分配失败");
return;
}
}
public void back(Node jobnode){ //回收函数
int i;
Node merrroyNode=new Node();
if(jobnode.start>freeMerroyList.get(freeMerroyList.size()-1).end){ //如果作业的起始地址在最后一个空闲节点之后，直接插入
Node newfreeNode=new Node(jobnode.start,jobnode.size,false);
freeMerroyList.add(newfreeNode);
return;
}else if(jobnode.start==freeMerroyList.get(freeMerroyList.size()-1).end){ //如果作业的起始地址与最后一个空闲节点的末尾相等，直接合并
freeMerroyList.get(freeMerroyList.size()-1).uPadteMerroyNodeEnd(jobnode.size);
return;
}
for(i=0;i<freeMerroyList.size();i++){ //找寻中间点
merrroyNode=freeMerroyList.get(i);
if(jobnode.start>=merrroyNode.end&&merrroyNode.state==false){
break;
}
}
Node next=freeMerroyList.get(i+1);
if(jobnode.start==merrroyNode.end&&next.start>jobnode.end){ //前面相邻
merrroyNode.uPadteMerroyNodeEnd(jobnode.size);
return;
}else if(jobnode.start>merrroyNode.end&&jobnode.end==next.start){ //后面相邻
merrroyNode.uPadteMerroyNodeStart(jobnode.start);
return;
}else if(jobnode.start==merrroyNode.end&&jobnode.end==next.start){ //前后相邻
merrroyNode.uPadteMerroyNodeEnd(jobnode.size);
freeMerroyList.remove(next);
return;
}
Node newFreeNode=new Node(jobnode.start,jobnode.size,false); //中间插入
freeMerroyList.add(i+1,newFreeNode);
}
public void init(){ //初始化
Node node1=new Node(14,12,false); //初始时，系统的空闲分区表
Node node2=new Node(32,500,false);
freeMerroyList.add(node1);
freeMerroyList.add(node2);
}
public Mermory(){
init();
}
public static void main(String[] args) {
Mermory mermory=new Mermory();
Node jobNode1=new Node(300);
mermory.print("初始空闲表");
mermory.Allocate(jobNode1);
mermory.print("作业一申请300k空间，分配后");
Node jobNode2=new Node(100);
mermory.Allocate(jobNode2);
mermory.print("作业二申请100k空间,分配后");
mermory.back(jobNode1);
mermory.print("作业一回收后");
Node jobNode3=new Node(150);
mermory.Allocate(jobNode3);
mermory.print("作业三申请150k空间,分配后");
Node jobNode4=new Node(30);
mermory.Allocate(jobNode4);
mermory.print("作业四申请30k空间,分配后");
Node jobNode5=new Node(40);
mermory.Allocate(jobNode5);
mermory.print("作业五申请40k空间,分配后");
Node jobNode6=new Node(60);
mermory.Allocate(jobNode6);
mermory.print("作业六申请60k空间,分配后");
mermory.back(jobNode4);
mermory.print("作业四释放后");
}
}
class Node{
int start; //起始
int size; //大小
boolean state; //状态
int end; //结束地址
public Node(){
}
public Node(int size) { //作业申请节点
this.state=true;
this.size = size;
}
public Node(int start, int size, boolean state) { //空闲节点
this.start = start;
this.size = size;
this.state = state;
this.end=start+size;
}
public void setJobBound(int start){
this.start=start;
this.end=start+this.size;
}
public void uPadteMerroyNodeEnd(int size){
this.size+=size;
this.end+=size;
}
public void uPadteMerroyNodeStart(int size){
this.size+=size;
this.start-=size;
}
public void print(String str){
System.out.println(str+" 起始:"+start+" 大小："+size+" 终止:"+end);
}
}
