面试题：Rust堆内存内存池中的内存分配策略

1. 空闲链表法（Free List）

策略描述：维护一个空闲内存块的链表。当申请内存时，遍历链表寻找合适大小的空闲块分配；释放内存时，将其加入空闲链表。
优点：
- 简单直观：实现相对容易，概念简单，便于理解和维护。
- 碎片合并灵活：释放内存时能较方便地与相邻空闲块合并，减少外部碎片。
缺点：
- 分配效率低：遍历链表寻找合适块的时间复杂度较高，特别是链表较长时。
- 内存开销：每个空闲块需要额外空间存储链表指针。
适用场景：适用于内存分配和释放操作不太频繁，且对内存碎片较为敏感的场景，如一些嵌入式系统中相对稳定的内存管理。

2. 伙伴系统（Buddy System）

策略描述：将内存空间看成一棵二叉树，初始时是一个完整的大块。分配内存时，将大块不断分裂成两个相等的“伙伴”块，直到找到合适大小的块。释放内存时，如果其伙伴也空闲，则合并成更大的块。
优点：
- 快速分配：分配和释放操作效率较高，因为分裂和合并操作有规律可循，时间复杂度相对较低。
- 减少碎片：能有效减少内部碎片和外部碎片，因为合并机制可以将小块内存逐步合并成大块。
缺点：
- 内存浪费：由于只能以2的幂次方大小进行分配，可能导致实际使用内存与分配内存大小差异较大，造成一定内存浪费。
- 复杂实现：实现相对复杂，需要管理树状结构和伙伴关系。
适用场景：适用于对内存分配和释放速度要求较高，且内存块大小以2的幂次方增长较为合适的场景，如一些实时系统或图形渲染中的内存管理。

Rust中实现空闲链表法的代码示例

// 定义空闲链表节点
struct FreeListNode {
    size: usize,
    next: Option<Box<FreeListNode>>,
}

// 内存池结构体
struct MemoryPool {
    head: Option<Box<FreeListNode>>,
    pool: Vec<u8>,
}

impl MemoryPool {
    // 创建新的内存池
    fn new(total_size: usize) -> MemoryPool {
        let mut pool = Vec::with_capacity(total_size);
        pool.resize(total_size, 0);
        let head = Some(Box::new(FreeListNode {
            size: total_size,
            next: None,
        }));
        MemoryPool { head, pool }
    }

    // 分配内存
    fn allocate(&mut self, size: usize) -> Option<usize> {
        let mut prev = None;
        let mut current = self.head.as_mut();
        while let Some(node) = current {
            if node.size >= size {
                let allocated_size = if node.size - size >= std::mem::size_of::<FreeListNode>() {
                    size
                } else {
                    node.size
                };
                let new_size = node.size - allocated_size;
                let allocated_start = &self.pool.len() - node.size;
                if new_size > 0 {
                    let new_node = Box::new(FreeListNode {
                        size: new_size,
                        next: node.next.take(),
                    });
                    node.next = Some(new_node);
                    node.size = allocated_size;
                } else {
                    if let Some(p) = prev {
                        p.as_mut().unwrap().next = node.next.take();
                    } else {
                        self.head = node.next.take();
                    }
                }
                return Some(allocated_start);
            }
            prev = Some(current);
            current = current.as_mut().and_then(|n| n.next.as_mut());
        }
        None
    }

    // 释放内存
    fn deallocate(&mut self, start: usize) {
        let size = self.pool.len() - start;
        let new_node = Box::new(FreeListNode {
            size,
            next: self.head.take(),
        });
        self.head = Some(new_node);
        // 这里简单实现，未进行相邻空闲块合并，实际可添加合并逻辑
    }
}

你可以这样使用这个内存池：

fn main() {
    let mut pool = MemoryPool::new(1024);
    if let Some(ptr) = pool.allocate(128) {
        println!("Allocated at position: {}", ptr);
    }
    pool.deallocate(896); // 假设之前分配在896位置
}

星途面试题库

面试题：Rust堆内存内存池中的内存分配策略

知识考点

面试题答案

1. 空闲链表法（Free List）

2. 伙伴系统（Buddy System）

Rust中实现空闲链表法的代码示例