1实验目的
（1）了解动态分区分配方式中使用的数据结构和分配算法
（2）加深对动态分区存储管理方式及其实现过程的理解。
2实验内容
（1）分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。
（2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：
•作业1申请130KB。
•作业2申请60KB。
•作业3申请100KB。
•作业2释放60KB。
•作业4申请200KB。
•作业3释放100KB。
•作业1释放130KB。
•作业5申请140KB。
•作业6申请60KB。
•作业7申请50KB。
•作业6释放60KB。
分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。
3实验结果（给出编写的程序源代码和运行结果的截图）
这是操作系统实验老师出的一个题目，要求模拟动态分区的内存分配，上面是题目的要求。对于这道题，我自己并没有独立实现，在网上找了源码，终于弄懂了，然后自己写了最佳适应算法，这里我就说一下怎么来解这道题。
1.首先，需要声明占用内存的进程的各个属性。你需要name来表示该进程的名字、startAddress表示进程所占内存的起始地址、length表示进程所占大小、flag表示用于标记该内存是否释放。
2.然后需要分配算法和回收的算法。对于分配，因为存储的方式是链式存储的，对于一个将要分配进来的进程，系统会将第一个适合该进程的内存分出足够的大小分配给该进程，这就是首次适应算法。而我写的最佳适应算法的思路是这样的：每次分配前，就对内存中的所有片空间进行排序，这样每次分配进来的内存都会是最适合的内存空间。
3.有分配就会有回收，回收分为几种情况，需要注意的就是在回收过程中，当相邻的有空闲分区时，需要进行合并
下面是源代码：
进程类Date.class
packagememory;publicclassDate {
String name;//进程名称intstartAddress;//起始地址intlength;//占用大小长度intflag;//是否已使用publicDate(String name,intstartAddress,intlength,intflag) {super();this.name =name;this.startAddress =startAddress;this.length =length;this.flag =flag;
}publicDate() {super();
}
@OverridepublicString toString() {return"Date [name=" + name + ", startAddress=" +startAddress+ ", length=" + length + ", flag=" + flag + "]";
}
}
Main.class
packagememory;importjava.util.ArrayList;importjava.util.Collection;importjava.util.Scanner;publicclassMain {staticArrayList list =newArrayList();//建立一个链表，来表示内存的使用情况staticScanner sc =newScanner(System.in);//首次适应算法staticvoidfenPei(){
Date date=newDate();
System.out.PRintln("输入请求分配进程的名称：");
date.name=sc.next();
System.out.println("输入分配的内存大小：");
date.length=sc.nextInt();inti;for( i = 0; i < list.size(); i++) {if(date.length <= ((Date)list.get(i)).length && ((Date)list.get(i)).flag == 0) {//当有适合的内存，且未被使用
break;
}
}if(i ==list.size()) {
System.out.println("没有足够的内存进行分配");
}if(((Date)list.get(i)).length - date.length <= 4 && i != list.size() - 1 ) {//当内存比进程所占的内存在4kB以内的话，就不进行分片((Date)list.get(i)).name =date.name;
((Date)list.get(i)).flag= 1;
}else{//分片分配内存date.flag = 1;
((Date)list.get(i)).length-=date.length;
date.startAddress=((Date)list.get(i)).startAddress;
((Date)list.get(i)).startAddress+=date.length;
list.add(i, date);
}
}//最佳适应算法staticvoidfenPei1(){
Date date=newDate();
System.out.println("输入请求分配进程的名称：");
date.name=sc.next();
System.out.println("输入分配的内存大小：");
date.length=sc.nextInt();intm, j;
Date target=newDate();for(m = 1; m < list.size()-1; m++){
j=m;
target.name=((Date)list.get(m)).name;
target.flag=((Date)list.get(m)).flag;
target.length=((Date)list.get(m)).length;
target.startAddress=((Date)list.get(m)).startAddress;while(j>0 && ((Date)list.get(j-1)).length>target.length){
((Date)list.get(j)).name= ((Date)list.get(j-1)).name;
((Date)list.get(j)).flag= ((Date)list.get(j-1)).flag;
((Date)list.get(j)).length= ((Date)list.get(j-1)).length;
((Date)list.get(j)).startAddress= ((Date)list.get(j-1)).startAddress +((Date)list.get(j)).length;
j--;
}
((Date)list.get(j)).name=target.name;
((Date)list.get(j)).length=target.length;
((Date)list.get(j)).flag=target.flag;
((Date)list.get(j)).startAddress= target.startAddress-((Date)list.get(j+1)).length;
}inti;for( i = 0; i < list.size(); i++) {if(date.length <= ((Date)list.get(i)).length && ((Date)list.get(i)).flag == 0) {//当有适合的内存，且未被使用
break;
}
}if(i ==list.size()) {
System.out.println("没有足够的内存进行分配");
}if(((Date)list.get(i)).length - date.length <= 4 && i != list.size() - 1) {
((Date)list.get(i)).name=date.name;
((Date)list.get(i)).flag= 1;
}else{//分片分配内存date.flag = 1;
((Date)list.get(i)).length-=date.length;
date.startAddress=((Date)list.get(i)).startAddress;
((Date)list.get(i)).startAddress+=date.length;
list.add(i, date);
}
}//回收部分staticvoidhuiShou(){
System.out.println("请输入要回收的进程：");
String name=sc.next();inti;for( i = 0; i < list.size(); i++) {if(name.equals(((Date)list.get(i)).name)) {
break;
}
}if(i ==list.size()) {
System.out.println("没有找到该进程。");return;
}
System.out.println("找到的是====>"+i);inthui =((Date)list.get(i)).length;if(i == 0 && ((Date)list.get(i+1)).flag == 0) {//回收第一个进程，且第二个内存位置空闲，合并这两者((Date)list.get(i)).flag = 0;
((Date)list.get(i)).length+= ((Date)list.get(i+1)).length;
((Date)list.get(i)).name= "";
list.remove(1);
}elseif(i == 0 && ((Date)list.get(i+1)).flag == 1) {//回收第一个进程，但第二个内存位置被占用((Date)list.get(i)).name = "";
((Date)list.get(i)).flag= 0;
}elseif(((Date)list.get(i-1)).flag == 0 && ((Date)list.get(i+1)).flag == 0) {//回收位置的进程左右两边的内存空间都空闲((Date)list.get(i)).name = "";
((Date)list.get(i)).flag= 0;
((Date)list.get(i-1)).length += ((Date)list.get(i)).length + ((Date)list.get(i+1)).length;
list.remove(i);
list.remove(i+1);
}elseif(((Date)list.get(i-1)).flag == 0 && ((Date)list.get(i+1)).flag == 1) {//回收位置左边的内存空闲，而右边的内存被占用((Date)list.get(i)).name = "";
((Date)list.get(i)).flag= 0;
((Date)list.get(i-1)).length +=((Date)list.get(i)).length;
list.remove(i);
}elseif(((Date)list.get(i-1)).flag == 1 && ((Date)list.get(i+1)).flag == 0) {//回收位置右边的内存空闲，而左边的内存被占用((Date)list.get(i)).name = "";
((Date)list.get(i)).flag= 0;
((Date)list.get(i)).length+= ((Date)list.get(i+1)).length;
list.remove(i+1);
}else{//左右两边的内存都被占用((Date)list.get(i)).name = "";
((Date)list.get(i)).flag= 0;
}
System.out.println("成功回收进程"+i+"的"+hui+"kb的空间");
}staticvoiddisPlay(){
System.out.println("=============================================");for(inti = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
System.out.println("=============================================");
}publicstaticvoidmain(String[] args){
Date date=newDate("", 0, 640, 0);
list.add(date);intchoice0;intchoice1;while(true){
System.out.println("请选择：内存分配方式");
System.out.println("1.首次适应算法");
System.out.println("2.最佳适应算法");
System.out.println("3.退出");
choice0=sc.nextInt();switch(choice0) {case1:while(true){
System.out.println("请选择：");
System.out.println("1.分配内存");
System.out.println("2.回收内存");
System.out.println("3.查看内存");
System.out.println("4.退出");
choice1=sc.nextInt();switch(choice1) {case1:
fenPei();
break;case2:
huiShou();
break;case3:
disPlay();
break;case4:
System.exit(0);
break;default:
System.out.println("请正确输入");
break;
}
}case2:while(true){
System.out.println("请选择：");
System.out.println("1.分配内存");
System.out.println("2.回收内存");
System.out.println("3.查看内存");
System.out.println("4.退出");
choice1=sc.nextInt();switch(choice1) {case1:
fenPei1();
break;case2:
huiShou();
break;case3:
disPlay();
break;case4:
System.exit(0);
break;default:
System.out.println("请正确输入");
break;
}
}case3:
System.exit(0);
break;default:
System.out.println("请正确输入：");
}
}
}
}