参考：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 + "]"); } }