package 实验六;
import java.util.*;
//从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给作业,
public class FF {
private static class Node {
int id; // 作业id,为-1代表空闲分区;大于0代表已分配
int start; // 初始地址
int size; // 大小
public String toString() {
return String.format("[%4d, %4d, %4d]", id, start, size);
}
}
// 返回分区链表
private static List init() {
List list = new ArrayList<>();
Node node = new Node();
// 初始化,为整个内存空间分配一个空闲节点
node.id = -1;
node.start = 0;
node.size = 600;//内存空间为640KB,高端40K用来存放操作系统。
list.add(node);
return list;
}
// 为作业id在分区链表list中分配大小为size的内存
//1 语法public E get(int index)2 参数index:要返回的元素的索引。3 返回值返回ArrayList中指定位置的元素
private static boolean add(List list, int id, int size) {
Node p = null;
int i;
// 找到第一个未分配且大于size的内存空间节点p,i为其下标
for (i = 0; i < list.size(); i++) {
p = list.get(i);
if (p.id == -1 && p.size >= size)//找到大小符合的空闲区
break;
}
// 当原来节点的大小大于size时需要创建一个新节点temp保留余下的分区,并插在p的后面
if (p.size - size > 0) {
Node temp = new Node();//后边剩余的空间
temp.id = -1;
temp.start = p.start + size;
temp.size = p.size - size;
list.add(i + 1, temp);// 前边是p, 后边是temp
}
// 将原来节点变成已分配的节点并为其分配大小
p.id = id;
p.size = size;
return true;
}
// 回收作业id的内存,并合并相邻的空闲分区
private static boolean del(List list, int id) {
Node p = null;
int i;
// 找到作业id所在的节点p,i为其下标
for (i = 0; i < list.size(); i++) {
p = list.get(i);
if (p.id == id) break;//退出后获得i的大小
}
p.id = -1; // 回收分区
Node a, b;
if (i != 0) { // 若第i-1个节点和第i个节点相邻,合并两个分区
a = list.get(i - 1);
b = list.get(i);
if (a.id == -1 && b.id == -1 && a.start + a.size == b.start) {
a.size += b.size;
list.remove(i);
i--;
}
// i--是因为可能存在合并后的节点可能与后一个节点相邻
}
if (i != list.size() - 1) { // 若第i个节点和第i+1个节点相邻,合并两个分区
a = list.get(i);
b = list.get(i + 1);
if (a.id == -1 && b.id == -1 && a.start + a.size == b.start) {
a.size += b.size;
list.remove(i + 1);
}
}
return true;
}
private static void show(List list) {
System.out.println("已分配分区:");
int i = 1;
for (Node temp : list) {
if (temp.id != -1) System.out.println("分区号:" + i + " 分配情况:" + temp);
i++;
}
i = 1;
System.out.println("未分配分区:");
for (Node temp : list) {
if (temp.id == -1) System.out.println("分区号:" + i + " 分配情况:" + temp);
i++;
}
// System.out.println(list);
}
public static void main(String[] args) {
List list = init();
System.out.println(" id"+" 起始地址"+" "+" 大小");
// 作业1申请130KB
add(list,1,130);
// 作业2申请60KB
add(list,2,60);
// 作业3申请100KB
add(list,3,100);
// 作业2释放60KB
del(list, 2);
// 作业4申请200KB
add(list,4,200);
// 作业3释放100KB
del(list, 3);
// 作业1释放130KB
del(list, 1);
// 作业5申请140KB
add(list,5,140);
// 作业6申请60KB
add(list,6,60);
// 作业7申请50KB
add(list,7,50);
// 作业6释放60KB
del(list, 6);
show(list);
}
}