实验二：内存分配

实验题

1.原理：.bss字段是什么含义？为什么我们要将动态分配的内存（堆）空间放在 .bss 字段？

.bss段：未初始化的全局和静态变量，以及所有被初始化为0的全局或静态变量，在目标文件中这个这个节不占据实际的空间，它仅仅是一个占位符。目标文件格式区分已初始化和未初始化变量是为了空间效率：在目标文件中，未初始化变量不需要占据任何实际的磁盘空间。运行时，在内存中分配这些变量，初始化值为0。

.bss段放堆空间，实际并不是必须的——我们完全可以随意指定一段可以访问的内存空间。不过，在代码中用全局变量来表示堆并将其放在.bss段，是一个很简单的实现：这样堆空间就包含在内核的二进制数据之中了，而自KERNEL_END_ADDRESS以后的空间就可以给进程使用。

2.分析：我们在动态内存分配中实现了一个堆，它允许我们在内核代码中使用动态分配的内存，例如 Vec、 Box 等。那么，如果我们在实现这个堆的过程中使用 Vec 而不是 [u8]，会出现什么结果？

  • 无法编译？
  • 运行时错误？
  • 正常运行？

会发生死锁。使用Vec会向堆中申请内存，而Allocator也需要向堆内申请内存（个人感觉Vec的实现需要Allocator，而只有实现了Allocator才能实现堆，这样就会死循环了）。

3.实验：

I. 回答：algorithm/src/allocator 下有一个 Allocator trait，我们之前用它实现了物理页面分配。这个算法的时间和空间复杂度是什么？

allocator模块中的trait定义如下：

1
2
3
4
5
6
7
8
9
/// 分配器：固定容量，每次分配 / 回收一个元素
pub trait Allocator {
    /// 给定容量，创建分配器
    fn new(capacity: usize) -> Self;
    /// 分配一个元素，无法分配则返回 `None`
    fn alloc(&mut self) -> Option<usize>;
    /// 回收一个元素
    fn dealloc(&mut self, index: usize);
}

实现在algorithm/src/allocator/stacked_allocator.rs里，实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
pub struct StackedAllocator {
    list: Vec<(usize, usize)>,
}

impl Allocator for StackedAllocator {
    fn new(capacity: usize) -> Self {
        Self {
            list: vec![(0, capacity)],
        }
    }

    fn alloc(&mut self) -> Option<usize> {
        if let Some((start, end)) = self.list.pop() {
            if end - start > 1 {
                self.list.push((start + 1, end));
            }
            Some(start)
        } else {
            None
        }
    }

    fn dealloc(&mut self, index: usize) {
        self.list.push((index, index + 1));
    }
}

可以看出空间复杂度为O(n)O(n)，时间复杂度为O(1)O(1)。

II. 二选一：实现基于线段树的物理页面分配算法（不需要考虑合并分配）；或尝试修改 FrameAllocator，令其使用未被分配的页面空间（而不是全局变量）来存放页面使用状态。

基于线段树的物理页面算法分配：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// Segment Tree Allocator Implement

use super::Allocator;
use alloc::{vec, vec::Vec};
use bit_field::BitArray;

pub struct SegmentTreeAllocator {
    tree: Vec<u8>,
}

impl Allocator for SegmentTreeAllocator {
    fn new(capacity: usize) -> Self {
        let leaf_count = capacity.next_power_of_two();
        let mut tree = vec![0u8; leaf_count * 2];

        for index in (capacity..leaf_count){
            tree.set_bit(index, true);
        }



        for index in (1..leaf_count).rev() {
            let value = tree.get_bit(2 * index) && tree.get_bit(2 * index + 1) && tree.get_bit(index);
            tree.set_bit(index, value);
        }

        Self{ tree }

    }

    fn alloc(&mut self) -> Option<usize> {
        let mut index = 1;
        if self.tree.get_bit(index) {
            return None;
        }else{
            while index < self.tree.len()/2{
                if(!self.tree.get_bit(index * 2)){
                    index *= 2;
                }else if(!self.tree.get_bit(index * 2 + 1)){
                    index = index * 2 + 1;
                }else {
                    panic!("Damaged Segement Tree!");
                }
            }
        }
        self.uploadNode(index, true);
        return Some(index - self.tree.len()/2);
      }

    fn dealloc(&mut self, index: usize) {
        let node = index + self.tree.len()/2;
        self.uploadNode(node, false);
    }
}

impl SegmentTreeAllocator{

    fn uploadNode(&mut self, mut index: usize, value: bool){
        self.tree.set_bit(index, value);
        while index > 1 {
            index /= 2;
            let v = self.tree.get_bit(2 * index) && self.tree.get_bit(2 * index + 1);
            self.tree.set_bit(index, v);
        }
    }
}

  1. 挑战实验（选做）：

I. 在 memory/heap2.rs 中，提供了一个手动实现堆的方法。它使用 algorithm::VectorAllocator 作为其根本分配算法，而我们目前提供了一个非常简单的 bitmap 算法（而且只开了很小的空间）。请在 algorithm crate 中利用伙伴算法实现 VectorAllocator trait。

II. 前面说到，堆的实现本身不能完全使用动态内存分配。但有没有可能让堆能够利用动态分配的空间，这样做会带来什么好处？