概念
一种经典的内存分配方案。
代码地址： github
https://github.com/fofcn/operation-system/tree/main/%E5%AE%9E%E8%B7%B5/3%20%E5%86%85%E5%AD%98%E7%AE%A1%E7%90%86/buddy
主要思想
- 将内存按照2的幂进行划分，组成若干个空闲块链表；
- 查找该链表找到满足进程需要的最佳匹配块
算法
- 首先将真个可用空间看做一块：2^U
- 假设进程申请的空间大小为s，如果满足 2^u-1 < s <= 2^u则分配整个块；否则将块划分为两个大小相等的伙伴，大小为2^u-1
- 一直划分知道产生大于或等于s的最小块
图例
![Image [2].png](https://ucc.alicdn.com/pic/developer-ecology/738f9d03179f426e82b6a145098dbfca.png)
代码实现
public class BuddySystem {
/**
* 申请释放锁
*/
private Lock lock = new ReentrantLock();
private LinkedList<MemoryBlock> mmBlockList = new LinkedList<>();
/**
* 可用空闲区全部大小
*/
private final int size;
/**
* 空闲区可用大小
*/
private AtomicInteger idleSize = new AtomicInteger(0);
/**
* 内存块数量
*/
private AtomicInteger blockSize = new AtomicInteger(0);
/**
* 是否初始化完成
*/
private volatile boolean isInitialized = false;
public BuddySystem(int size) {
this.size = size;
this.idleSize.set(size);
}
/**
* 初始化伙伴系统内存链表
*/
public void initialize() {
if (isInitialized) {
return;
}
MemoryBlock memoryBlock = new MemoryBlock();
memoryBlock.setSize(size);
memoryBlock.setStart(0);
memoryBlock.setEnd(size - 1);
mmBlockList.add(memoryBlock);
blockSize.incrementAndGet();
isInitialized = true;
}
/**
* 分配内存
* @param expectSize 待分配的内存大小
*/
public MemoryBlock alloc(int expectSize) {
// 参数检查
if (expectSize > size) {
throw new IllegalArgumentException("Sorry, I don't have enough memory.");
}
MemoryBlock best = null;
// 开始查找最适合的块
if (lock.tryLock()) {
try {
// 查看当前空闲块链表，找到小且大于等于申请大小的空闲块
MemoryBlock smallestFit = findSmallestFitBlock(expectSize);
if (smallestFit == null) {
throw new InternalError("not enough memory");
}
// 检查是否满足2^u-1 < expectSize <= 2^u
// 满足则直接分配
// 不满足则拆分为两个大于或等于S的小块，然后检查是否满足2^u-1 < size <= 2^u
if (smallestFit.getSize() != expectSize) {
// 检查并等分内存区
while (expectSize * 2 <= smallestFit.getSize()) {
// 拆分
int smallBlockSize = smallestFit.getSize() / 2;
int start = smallestFit.getStart();
int middle = smallestFit.getStart() + smallBlockSize;
int end = smallestFit.getEnd();
MemoryBlock left = new MemoryBlock(start, middle, smallBlockSize, false);
MemoryBlock right = new MemoryBlock(middle, end, smallBlockSize, false);
// 在删除点添加这两块内存
mmBlockList.replace(smallestFit, left, right);
blockSize.incrementAndGet();
smallestFit = left;
}
}
best = smallestFit;
best.setUsed(true);
idleSize.addAndGet(-best.getSize());
} finally {
lock.unlock();
}
}
return best;
}
private MemoryBlock findSmallestFitBlock(int expectSize) {
MemoryBlock smallestFit = null;
for (MemoryBlock memoryBlock : mmBlockList) {
if (!memoryBlock.isUsed() &&
memoryBlock.getSize() >= expectSize) {
if (smallestFit == null) {
smallestFit = memoryBlock;
} else {
if (smallestFit.getSize() > memoryBlock.getSize()) {
smallestFit = memoryBlock;
}
}
}
}
return smallestFit;
}
public void free(MemoryBlock freeBlock) {
List<LinkedList.Node<MemoryBlock>> mergeNodes = new ArrayList<>(3);
// 释放内存需要检查四种相邻场景
// 如果有相邻，则合并
if (lock.tryLock()) {
try {
freeBlock.setUsed(false);
LinkedList.Node<MemoryBlock> toFreeNode = mmBlockList.findNode(freeBlock);
if (toFreeNode == null) {
throw new IllegalArgumentException("You accessed memory illegally.");
}
// 检查前一个节点
// 检查查找到的块是否大小相等且地址连续
LinkedList.Node<MemoryBlock> prev = toFreeNode.prev;
LinkedList.Node<MemoryBlock> next = toFreeNode.next;
if (prev != null && !prev.item.isUsed()
&& prev.item.getSize() == toFreeNode.item.getSize()
&& prev.item.getEnd() == toFreeNode.item.getStart()) {
mergeNodes.add(prev);
blockSize.incrementAndGet();
}
mergeNodes.add(toFreeNode);
// 检查下一个节点
// 检查查找到的块是否大小相等且地址连续
if (next != null && !next.item.isUsed()
&& next.item.getSize() == toFreeNode.item.getSize()
&& next.item.getStart() == toFreeNode.item.getEnd()) {
mergeNodes.add(next);
}
int start = mergeNodes.get(0).item.getStart();
int end = mergeNodes.get(mergeNodes.size() - 1).item.getEnd();
int itemSize = 0;
for (LinkedList.Node<MemoryBlock> node : mergeNodes) {
itemSize += node.item.getSize();
blockSize.decrementAndGet();
}
// 删除当前节点和下一个节点，然后更新第一个节点大小和连接
mmBlockList.remove(prev);
mmBlockList.remove(next);
toFreeNode.item.setStart(start);
toFreeNode.item.setEnd(end);
toFreeNode.item.setSize(itemSize);
} finally {
lock.unlock();
}
}
}
public void printBlocks() {
int index = 1;
for (MemoryBlock memoryBlock : mmBlockList) {
StdOut.println("index: " + index + " " + memoryBlock);
index++;
}
}
public int getSize() {
return size;
}
public int getIdleSize() {
return idleSize.get();
}
public int getBlockSize() {
return blockSize.get();
}
}
测试用例
public class BuddySystemTest {
private BuddySystem buddySystem;
private static final int MAX_MEM_SIZE = 1024 * 1024 * 1024;
@Before
public void before() {
buddySystem = new BuddySystem(MAX_MEM_SIZE);
}
@Test
public void testInitialize() {
buddySystem.initialize();
Assert.assertEquals(MAX_MEM_SIZE, buddySystem.getSize());
Assert.assertEquals(0, buddySystem.getIdleSize());
}
@Test
public void testAllocAndFree() {
buddySystem.initialize();
// 分配100KB
int size = 100 * 1024 * 1024;
MemoryBlock block = buddySystem.alloc(size);
Assert.assertNotNull(block);
Assert.assertEquals(MAX_MEM_SIZE - block.getSize(), buddySystem.getIdleSize());
Assert.assertEquals(buddySystem.getBlockSize(), 4);
buddySystem.printBlocks();
System.out.println("=================================");
System.out.println("=================================");
// 分配240KB
size = 240 * 1024 * 1024;
MemoryBlock block2 = buddySystem.alloc(size);
Assert.assertNotNull(block2);
Assert.assertEquals(MAX_MEM_SIZE - block.getSize() - block2.getSize(), buddySystem.getIdleSize());
Assert.assertEquals(buddySystem.getBlockSize(), 4);
buddySystem.printBlocks();
System.out.println("=================================");
System.out.println("=================================");
// 分配64KB
size = 64 * 1024 * 1024;
MemoryBlock block3 = buddySystem.alloc(size);
Assert.assertNotNull(block3);
Assert.assertEquals(MAX_MEM_SIZE - block.getSize() - block2.getSize() - block3.getSize(), buddySystem.getIdleSize());
Assert.assertEquals(buddySystem.getBlockSize(), 5);
buddySystem.printBlocks();
System.out.println("=================================");
System.out.println("=================================");
// 分配256KB
size = 256 * 1024 * 1024;
MemoryBlock block4 = buddySystem.alloc(size);
Assert.assertNotNull(block3);
Assert.assertEquals(MAX_MEM_SIZE - block.getSize() - block2.getSize()
- block3.getSize() - block4.getSize(), buddySystem.getIdleSize());
Assert.assertEquals(buddySystem.getBlockSize(), 6);
buddySystem.printBlocks();
System.out.println("=================================");
System.out.println("=================================");
// 释放240KB
buddySystem.free(block2);
Assert.assertEquals(buddySystem.getBlockSize(), 5);
}
}
参考
- 操作系统原理 陈向群