北京师范大学珠海分校
1.通过使用位图或空闲表，跟踪内存使用情况，模拟和评价不同的内存分配算法；
2.熟悉内存分配和回收管理过程。
1.要求用你熟悉的程序设计语言编写和调试一个内存分配和回收模拟程序；要求在主函数中测试。
2.实验报告中必须包括：设计思想、数据定义（包括详细说明）、处理流程（详细算法描述和算法流程图）、源代码、运行结果、体会等部分。
3.必须模拟该4种内存分配算法：first fit，next fit，best fit和worst fit中的至少2种。
4.需显示出每次分配和回收后的空闲分区链的情况来以及内存占用情况图。
5.（可选：）计算2个性能参数：碎片数（小于2个单元（units）的空闲区数）、完成一次内存分配的空闲区比较（搜索）次数，也即经过几次比较完成某次请求的内存分配。
假设内存容量为256KB，并且划分成1KB大小的块，也即每个内存单元为1KB。一个进程所需要的内存为3到10个单元。同时假设一个作业在运行过程中所需内存的大小不变。
模拟包括3部分：
1.实现特定的内存分配算法
2.实现内存回收模拟
3.每种内存分配策略对应的碎片数统计（可选）
1）数据项设计
2）存储结构确定
内存空间分配表采用双向链表的数据形式
分配空间块的数据结构为：
前向指针：before 初始值为-1 指向该结点的上一个节点的位置
进程块在内存中的位置： strtLocation 表示该内存块的位置信息
进程块id：标志被占用的内存块
空间大小 ：size 表示占用内存的大小
后向指针： next 初始值为-1 表示该节点的下一个结点位置
空闲块的数据结构：
前向指针：before 初始值为-1 指向该空闲块的上一个空闲块的位置
空闲块在内存中的位置： strtLocation 表示该空闲块的位置信息
空间大小 ：size 表示空闲空间的大小
后向指针： next 初始值为-1 表示该节点的下一个空闲块的位置
1）算法分析
2）算法流程图绘制
3）编码
4）调试
3．编写主函数对所做工作进行测试。
1.首次适应算法FirstFit——空闲链表按地址递增的次序链接，优先分配内存中低址部分的空闲区。可保留高址大空闲区。
2.循环适应算法NextFit——从上次找到的空闲分区的下一个空闲分区开始查找。应设置一起始查询指针。该算法使空闲分区分布得更均匀。
3.最佳适应算法BestFit——空闲链表按分区大小递增的次序链接，优先分配内存中满足条件的最小的空闲区。
4.最坏适应算法WorstFit——空闲链表按分区大小递减的次序链接，优先分配内存中最大的空闲区。
在分配一个作业块时，按照内存中空闲块的位置依次查找，直到找到合适大小的内存块（空闲块的大小大于等于作业块的大小）
在回收内存块时，内存列表会有以下三种情况：
（1）在该回收块的左右两边都有相邻的空闲块；
（2）在该回收块的左边或者右边有相邻的空闲块；
（3）在该回收块的左边和右边都没有相邻的回收块；
第（1）种情况：将三个空闲块合并；
第（2）种情况：将相邻的两个空闲块合并；
第（3）种情况：将空闲块加入到空闲链表中；
ProcessNode类
//初始化作业块和空闲块
package com.it.bnuz.yzy;
public class ProcessNode {
private int id;
private int size;
public ProcessNode(int id, int size) {
this.id = id;
this.size = size;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
}
UseNode类：
//作业块
package com.it.bnuz.yzy;
public class UseNode implements Comparable<UseNode> {
private int before = -1;//初始为-1，-1表示表头
private int startLocation;
private int id;
private int size;
private int next = -1;//初始为-1，-1表示表尾
public UseNode(int id, int size) {
this.id = id;
this.size = size;
}
public int getBefore() {
return this.before;
}
public void setBefore(int before) {
this.before = before;
}
public int getStartLocation() {
return this.startLocation;
}
public void setStartLocation(int startLocation) {
this.startLocation = startLocation;
}
public int getId() {
return this.id;
}
public void setId(int id) {
this.id = id;
}
public int getSize() {
return this.size;
}
public void setSize(int size) {
this.size = size;
}
public int getNext() { return this.next; }
public void setNext(int next) {
this.next = next;
}
public int compareTo(UseNode o) {
return this.startLocation - o.getStartLocation();
}
public String toString() {
String str = "[before:" + this.before + " startLocation:" + this.startLocation + " id:" + this.id + " size:" + this.size + " next:" + this.next + "]";
return str;
}
}
FreeNode类：
//空闲块
package com.it.bnuz.yzy;
public class FreeNode implements Comparable<FreeNode> {
private int before = -1;
private int startLocation;
private int size;
private int next = -1;
public FreeNode(int size) {
this.size = size;
}
public int getBefore() {
return before;
}
public void setBefore(int before) {
this.before = before;
}
public int getStartLocation() {
return startLocation;
}
public void setStartLocation(int startLocation) {
this.startLocation = startLocation;
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
public int getNext() {
return next;
}
public void setNext(int next) {
this.next = next;
}
@Override
public int compareTo(FreeNode o) {
return this.startLocation - o.getStartLocation();
}
@Override
public String toString() {
String str = "[before:"+before+" startLocation:"+startLocation+" size:"+size+" next:"+next+"]";
return str;
}
}
内存Map
private String[] memory_space = new String[256];
初始状态下的内存情况：
//内存空间为16 * 16 的矩形空间，大小为256k，一个单元代表1k
//0代表空闲区
作业链表：
private List<UseNode> useSpaceList = new ArrayList<>();
空闲链表：
private List<FreeNode> freeSpaceList = new ArrayList<>();
FirstFit分配算法：
/*
*FirstFit首次适应算法 分配算法
* */
void FirstFit_distribution(ProcessNode p){
UseNode useNode = new UseNode(p.getId(),p.getSize());
int size = p.getSize();
int count = 0;
for(int i = 0; i < freeSpaceList.size();i++){//循环寻找是否有合适大小的空闲块
count++;
if(size <= freeSpaceList.get(i).getSize()){
//先处理空闲快链表
FreeNode freeNode = freeSpaceList.get(i);
useNode.setStartLocation(freeNode.getStartLocation());//插入进的占用块结点的起始位置为这个空闲块的起始位置
if(size < freeNode.getSize()){//插入块的大小小于该空闲块的大小时，该空闲块的起始位置发生改变,大小发生改变
freeSpaceList.get(i).setStartLocation(freeNode.getStartLocation() + p.getSize());
freeSpaceList.get(i).setSize(freeNode.getSize() - p.getSize());
}
else{//如果插入块的大小和该空闲块的大小相同，从链表中删除这个空闲块
if(i == 0){
freeSpaceList.get(i+1).setBefore(-1);//如果这个空闲块是表头，那么将下一个空闲块的before置为-1；
}
else{
freeSpaceList.get(i-1).setNext(freeSpaceList.get(i).getNext());
freeSpaceList.get(i+1).setBefore(freeSpaceList.get(i).getBefore());
}
}
//在内存中显示分配情况
for(int j = useNode.getStartLocation();j < useNode.getStartLocation() + useNode.getSize();j++){
if(j == useNode.getStartLocation()){
memory_space[j] = ""+useNode.getId()+" ";
}
else{
memory_space[j] = "+ ";
}
}
showMemory();
//对分配列表进行操作
firstFit_add(useNode);
showUseSpaceList();
showFreeSpaceList();
return;
}
else {
continue;
}
}
if(count == freeSpaceList.size()){
System.out.println("没有合适的空闲块，插入失败");
return;
}
}
分配算法中，对作业链表操作的函数：
firstFit_add(UseNode useNode)
再插入作业链表时，该作业列表的位置分为3种情况：
1.表头
2.表中
3.表尾
/*
* firstFit加入分配空间
* */
private void firstFit_add(UseNode useNode){
//操作占用块链表
useSpaceList.add(useNode);
if(useSpaceList.size() > 1){
useSpaceList.sort(UseNode::compareTo);//通过起始地址号进行排序，模拟插入链表
for(int k = 0;k < useSpaceList.size();k++){
if(useNode.getId() == useSpaceList.get(k).getId()){
if(k == 0){
useSpaceList.get(k).setNext(useSpaceList.get(k+1).getStartLocation());//如果该占用块插到表头，将next指向源列表的表头起始地址
useSpaceList.get(k+1).setBefore(0);//将原表头的before指向表头
}
else if(k == useSpaceList.size()-1){
useSpaceList.get(k).setBefore(useSpaceList.get(k-1).getStartLocation());
useSpaceList.get(k-1).setNext(useSpaceList.get(k).getStartLocation());
}
else{
useSpaceList.get(k).setBefore(useSpaceList.get(k-1).getStartLocation());
useSpaceList.get(k).setNext(useSpaceList.get(k+1).getStartLocation());
useSpaceList.get(k-1).setNext(useSpaceList.get(k).getStartLocation());
useSpaceList.get(k+1).setBefore(useSpaceList.get(k).getStartLocation());
}
}
}
}
}
FirstFit回收
/*
* firstFit首次适应算法，内存空间的释放
* 根据分配链表查找到要释放的内存空间地址
* 在空闲内存链表中添加空闲块
* */
public void firstFit_free(int id){
//查找该块的内存块
UseNode free_node = find_useNode(id);
if(free_node != null){
useSpaceList.remove(free_node);
FreeNode freeNode = new FreeNode(free_node.getSize());
freeNode.setStartLocation(free_node.getStartLocation());
freeSpaceList.add(freeNode);
freeSpaceList.sort(FreeNode::compareTo);
for(int i = 0;i < freeSpaceList.size();i++){
if(freeSpaceList.get(i).getStartLocation() == freeNode.getStartLocation()){
if(i == 0){//如果该空闲块为链表的表头
if((freeNode.getStartLocation() + freeNode.getSize()) == freeSpaceList.get(i+1).getStartLocation()){//如果两个空闲块相邻，拓展为一块
freeSpaceList.get(i).setSize(freeNode.getSize() + freeSpaceList.get(i).getSize());//合并两个空闲块
if(freeSpaceList.get(i+1).getNext() == -1){//如果相邻块是最后一个空闲块
freeSpaceList.remove(freeSpaceList.get(i+1));//将相邻空闲块删除
setFreeSpace(freeSpaceList.get(i).getStartLocation(),freeSpaceList.get(i).getSize());
break;
}
else{
freeSpaceList.get(i).setNext(freeSpaceList.get(i+1).getNext());//将空闲块的Next指向相邻块的下一个空闲块
freeSpaceList.get(i+2).setBefore(freeNode.getStartLocation());//将相邻块的下一个空闲块的before指向该空闲块
freeSpaceList.remove(freeSpaceList.get(i+1));
setFreeSpace(freeSpaceList.get(i).getStartLocation(),freeSpaceList.get(i).getSize());
break;
}
}
else{//如果两个空闲块不相邻
freeSpaceList.get(i).setNext(freeSpaceList.get(i+1).getStartLocation());
freeSpaceList.get(i+1).setBefore(freeSpaceList.get(i).getStartLocation());
setFreeSpace(freeSpaceList.get(i).getStartLocation(),freeSpaceList.get(i).getSize());
}
}
else if(i == (freeSpaceList.size() - 1)){//如果该空闲块位于链表表尾
FreeNode beforeNode = freeSpaceList.get(i-1);//空闲快的的前结点
if((beforeNode.getStartLocation() + beforeNode.getSize()) == free_node.getStartLocation()){//如果两个空闲块相邻
freeSpaceList.get(i-1).setSize(beforeNode.getSize() + freeNode.getSize());//合并
freeSpaceList.remove(freeNode);
setFreeSpace(freeNode.getStartLocation(),freeNode.getSize());
break;
}
}
else{//该空闲块在表中
FreeNode beforeNode = freeSpaceList.get(i-1);
FreeNode nextNode = freeSpaceList.get(i+1);
//分三种情况讨论：三个空闲块都相邻；只与左或右节点相邻；都不相邻
//都相邻
if((beforeNode.getStartLocation() + beforeNode.getSize() == freeNode.getStartLocation()) && (freeNode.getStartLocation() + freeNode.getSize() == nextNode.getStartLocation())){
freeSpaceList.get(i-1).setSize(beforeNode.getSize() + freeNode.getSize() + nextNode.getSize());
freeSpaceList.get(i-1).setNext(nextNode.getNext());
freeSpaceList.remove(freeNode);
freeSpaceList.remove(nextNode);
setFreeSpace(freeNode.getStartLocation(),freeNode.getSize());
break;
}
//与左相邻
else if(beforeNode.getStartLocation() + beforeNode.getSize() == freeNode.getStartLocation()){
freeSpaceList.get(i-1).setSize(beforeNode.getSize()+freeNode.getSize());
setFreeSpace(freeNode.getStartLocation(),freeNode.getSize());
break;
}
//与右相邻
else if(freeNode.getStartLocation() + freeNode.getSize() == nextNode.getStartLocation()){
freeSpaceList.get(i).setSize(freeNode.getSize()+nextNode.getSize());
freeSpaceList.get(i).setBefore(nextNode.getBefore());
freeSpaceList.get(i).setNext(nextNode.getNext());
freeSpaceList.remove(nextNode);
setFreeSpace(freeNode.getStartLocation(),freeNode.getSize());
break;
}
//都不相邻
else{
freeSpaceList.get(i).setBefore(beforeNode.getStartLocation());
freeSpaceList.get(i).setNext(nextNode.getStartLocation());
setFreeSpace(freeNode.getStartLocation(),freeNode.getSize());
break;
}
}
}
}
showMemory();
showUseSpaceList();
showFreeSpaceList();
}
}
查询回收块的信息函数，返回一个UseNode对象
/*
* 通过分配链表useSpaceList查询内存块，返回该内存快的信息
* */
private UseNode find_useNode(int id){
for(int i = 0;i < useSpaceList.size();i++){
if(useSpaceList.get(i).getId() == id){
if(useSpaceList.size() > 1){
if(i == useSpaceList.size()-1){
useSpaceList.get(i-1).setNext(-1);
}
else if(i == 0){
useSpaceList.get(i+1).setBefore(-1);
}
else {
useSpaceList.get(i-1).setNext(useSpaceList.get(i).getNext());
useSpaceList.get(i+1).setBefore(useSpaceList.get(i).getBefore());
}
}
return useSpaceList.get(i);
}
}
return null;
}
请输入id:1
请输入占用内存大小:35
请输入id:2
请输入占用内存大小:85
请输入id:3
请输入占用内存大小:9
请输入id:4
请输入占用内存大小:21
请输入id:5
请输入占用内存大小:19
请输入id:6
请输入占用内存大小:23
请输入id:7
请输入占用内存大小:15
请输入id:8
请输入占用内存大小:3
请输入id:9
请输入占用内存大小:6
分配后的内存情况：
分配后的作业块链表：
分配后的空闲快链表：
回收id=5的作业块
作业链表：
空闲块链表：
两边都有空闲块的情况：
作业块链表
空闲快链表
在空闲块列表中加标记。在插入一个作业块时，从上一次标记的空闲块的下一个空闲块开始查找合适的空闲块进行插入。
回收算法的流程与first fit一致，这里就不做重复了。
nextFit算法，这里只给出核心的分配算法，插入作业链表和插入空闲链表的算法与上述一致。
/*
* NextFit算法 循环适应算法
* */
public int nextFit_distribution(ProcessNode p,int flag){
UseNode useNode = new UseNode(p.getId(),p.getSize());
int size = p.getSize();
int count = 0;
for(int i = flag; i < freeSpaceList.size();i++){//从上一次插入的空闲块的下一个空闲块开始循环寻找是否有合适大小的空闲块
count++;
if(size <= freeSpaceList.get(i).getSize()){
//先处理空闲快链表
FreeNode freeNode = freeSpaceList.get(i);
useNode.setStartLocation(freeNode.getStartLocation());//插入进的占用块结点的起始位置为这个空闲块的起始位置
if(size < freeNode.getSize()){//插入块的大小小于该空闲块的大小时，该空闲块的起始位置发生改变,大小发生改变
freeSpaceList.get(i).setStartLocation(freeNode.getStartLocation() + p.getSize());
freeSpaceList.get(i).setSize(freeNode.getSize() - p.getSize());
}
else{//如果插入块的大小和该空闲块的大小相同，从链表中删除这个空闲块
if(i == 0){
freeSpaceList.get(i+1).setBefore(-1);//如果这个空闲块是表头，那么将下一个空闲块的before置为-1；
}
else{
freeSpaceList.get(i-1).setNext(freeSpaceList.get(i).getNext());
freeSpaceList.get(i+1).setBefore(freeSpaceList.get(i).getBefore());
}
}
//在内存中显示分配情况
for(int j = useNode.getStartLocation();j < useNode.getStartLocation() + useNode.getSize();j++){
if(j == useNode.getStartLocation()){
memory_space[j] = ""+useNode.getId()+" ";
}
else{
memory_space[j] = "+ ";
}
}
showMemory();
//对分配列表进行操作
addSpaceList(useNode);
showUseSpaceList();
showFreeSpaceList();
if(i == freeSpaceList.size()-1){//如果该空闲块是最后一个空闲块，将flag置为0
flag = 0;
}
else {//否则将flag指向下一个空闲块
flag = i + 1;
}
return flag;
}
else {
continue;
}
}
if(count == freeSpaceList.size() - flag){
System.out.println("没有合适的空闲块，插入失败");
}
return flag;
}
内存初始情况和链表情况：
插入作业块：
请输入id:2
请输入占用内存大小:15
插入的空闲块的位置是第一个空闲块，那么在下次插入时从第2个开始找
插入第二个作业块：
分配到了上次分配的空闲块的下一个空闲块
插入大小为30的作业块：
请输入id:6
请输入占用内存大小:30
再进行插入，回到第一个空闲块
此时的链表情况
