参考：https://labrick.cc/2015/10/12/buddy-system-algorithm/
代码过烂 不宜参考。
output：
[operating.entity.Heap@4554617c, 1048576]
**************begin mallocing memory*****************
heap.myMalloc(16), 分割 16 次
[operating.entity.Heap@4554617c, 1048560]
heap.myMalloc(32), 分割 0 次
[operating.entity.Heap@4554617c, 1048528]
heap.myMalloc(48), 分割 0 次
[operating.entity.Heap@4554617c, 1048464]
heap.myMalloc(64), 分割 1 次
[operating.entity.Heap@4554617c, 1048400]
heap.myMalloc(80), 分割 1 次
[operating.entity.Heap@4554617c, 1048272]
**************begin freeing memory*****************
heap.myFree(32), 合并0次
[operating.entity.Heap@4554617c, 1048304]
heap.myFree(128), 合并1次
[operating.entity.Heap@4554617c, 1048368]
heap.myFree(0), 合并2次
[operating.entity.Heap@4554617c, 1048384]
heap.myFree(64), 合并2次
[operating.entity.Heap@4554617c, 1048448]
heap.myFree(256), 合并13次
[operating.entity.Heap@4554617c, 1048576]
code:
package operating.test;
import operating.entity.Heap;
public class HeapTest {
public static void main(String[] args) {
Heap heap = new Heap();
heap.printList();
System.out.println("**************begin mallocing memory*****************");
int ptr16 = heap.myMalloc(16);
int ptr32 = heap.myMalloc(32);
int ptr48 = heap.myMalloc(48);
int ptr64 = heap.myMalloc(64);
int ptr80 = heap.myMalloc(80);
System.out.println("**************begin freeing memory*****************");
heap.myFree(ptr32);
heap.myFree(ptr64);
heap.myFree(ptr16);
heap.myFree(ptr48);
heap.myFree(ptr80);
}
}
/
package operating.entity; import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList; public class Heap {
/**
* 堆空间heap初始大小
*/
private static final int HEAP_SIZE = 1024*1024;
/**
* 空闲块切割后若剩余不超过RESIDUE，则不进行切割
*/
private static final int RESIDUE = 8;
/**
* 用一个int数组来模拟堆
*/
private int[] memory;
/**
* 用于管理内存的分配状态，采用伙伴系统
*/
private HashMap<Integer, LinkedList<Integer>> blockManager = new HashMap<>(); public Heap() {
memory = new int[HEAP_SIZE];
Arrays.fill(memory, 0); LinkedList<Integer> initBlock = new LinkedList<>(); // 创建可存放最大块 1024*1024 的链表
initBlock.add(0); // 添加一个可用的块，起始地址为 0
blockManager.put(HEAP_SIZE, initBlock); // 将链表添加到映射中 (1024*1024，链表(只含有一个块))
} /**
* 计算块大小 2^i，使得 2^(i-1) < n <= 2^i
* @param requestSize
* @return
*/
private int getBlockSize(int requestSize) {
if (requestSize <= RESIDUE) return RESIDUE; // 如果所请求的块小于最小可分割块则直接返回最小可分割块大小 int i = 4;
while (requestSize > Math.pow(2, i)) {
++i;
}
return (int) Math.pow(2, i);
} /**
* 查找可用的块
* @param blockSize
* @return
*/
private int searchAvailable(int blockSize) {
LinkedList<Integer> blocks = blockManager.get(blockSize);
if (blocks != null) { // 如果恰好有该大小的内存块
for (Integer x : blocks) {
if (memory[x] != 1) { // 并且还没被使用
return x;
}
}
}
return -1;
} /**
* 分割块： 2^i 转变为两个 2^(i-1)
* @param address
* @param size
*/
private void parting(Integer address, int size) {
LinkedList<Integer> bigBlocks = blockManager.get(size); // 取得 size 大小的块
bigBlocks.remove(address);
LinkedList<Integer> smallBlocks = blockManager.get(size/2);
if (smallBlocks == null) {
smallBlocks = new LinkedList<>();
blockManager.put(size/2, smallBlocks);
}
smallBlocks.add(address);
smallBlocks.add(address + size/2);
} /**
* 合并
* @param address
* @param buddyAddress
* @param size
*/
private void merge(Integer address, Integer buddyAddress, int size) {
LinkedList<Integer> smallBlocks = blockManager.get(size);
if (smallBlocks == null) return;
smallBlocks.remove(address);
smallBlocks.remove(buddyAddress);
LinkedList<Integer> bigBlocks = blockManager.get(size*2);
bigBlocks.add(address < buddyAddress ? address : buddyAddress);
} /**
* 通过地址得到相应的块大小
* @param address
* @return
*/
private int getSize(int address) {
for (Integer size : blockManager.keySet()) {
LinkedList<Integer> blocks = blockManager.get(size);
for (Integer x : blocks) {
if (x == address) return size;
}
}
return 0;
} /**
* 分配内存
* @param size 请求的内存大小
* @return 分配内存的起始地址
*/
public int myMalloc(int size) {
int count = 0; // 计算分割次数
// 计算所需要的块的大小
int requestSize = getBlockSize(size);
// 1- 如果恰好有该大小的块，直接分配并返回
int address = searchAvailable(requestSize);
if (address != -1) {
memory[address] = 1;
System.out.println("heap.myMalloc("+ size + ")," + " 分割 " + count + " 次");
this.printList();
return address;
} // 2- 如果没有就分割，逐级向上找可以分割的块
int tempSize = requestSize;
while (address == -1 && tempSize <= HEAP_SIZE) {
// System.out.println("正在搜索 " + tempSize + "大小的块。");
address = searchAvailable(tempSize*=2);
}
// System.out.println("找到了可分割的块。");
if (tempSize > HEAP_SIZE) {
System.out.println("没有足够的空间！");
return -1;
} else { // 分割出需要的块
while (searchAvailable(requestSize) == -1) {
// System.out.println("正在对起始地址为" + address + "大小为" + tempSize + "的块进行分割");
parting(address, tempSize);
++ count;
tempSize = tempSize/2;
}
} // 3- 重复 1
address = searchAvailable(requestSize);
memory[address] = 1;
System.out.println("heap.myMalloc("+ size + ")," + " 分割 " + count + " 次");
this.printList();
return address;
} /**
* 释放起始地址为 address 的内存
* @param address
*/
public void myFree(int address) {
int count = 0; // 计算合并次数
int originAddress = address;
memory[address] = 0;
while (true) {
int size = getSize(address);
// 计算伙伴块的地址
int buddyAddress = -1;
if (size != 0 && address % (size*2) == size) {
buddyAddress = address - size;
} else {
buddyAddress = address + size;
}
if (buddyAddress >=0 && buddyAddress < HEAP_SIZE && memory[buddyAddress] != 1) { // 如果伙伴块没被使用就合并
merge(address, buddyAddress, size);
++count;
} else {
break;
}
if (buddyAddress < address) {
int temp = address;
address = buddyAddress;
buddyAddress = temp;
}
}
System.out.println("heap.myFree("+ originAddress + ")," + " 合并" + count + "次");
this.printList();
} public void printList() {
int rest = HEAP_SIZE;
for (Integer size : blockManager.keySet()) {
LinkedList<Integer> blocks = blockManager.get(size);
for (Integer x : blocks) {
if (memory[x] == 1) {
rest -= size;
}
}
}
// 仅仅是模拟，java 无法真正获取对象内存地址
System.out.println("[" + this + ", " + rest + "]");
}
}