实验二：内存分配

实验之前

• 阅读实验指导二。
• checkout 到仓库中的 lab-2 分支，实验题将以此展开。

实验题

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

   Click to show

   对于一个 ELF 程序文件而言，.bss 字段一般包含全局变量的名称和长度，在执行时由操作系统分配空间并初始化为零。

   不过，在我们执行 rust-objcopy 时，不同的字段会相应地被处理而形成一段连续的二进制数据，这段二进制数据会直接写入到 QEMU 所模拟的机器的 0x80200000 位置。这是因为我们写的操作系统是直接运行在机器上的，而不是一个被操作系统加载的程序。

   我们一般遇到应用程序的动态内存分配（堆）是由其操作系统提供的。例如在 C 语言中的 malloc()，glibc 运行库会维护一个堆空间，而这个空间是通过 brk() 等系统调用向内核索要的。由于我们编写操作系统，自然就无法像这样获取空间。但是此时我们具有随意使用内存空间的权力，因此我们可以在内存中随意划一段空间，然后用相应的算法来实现一个堆。

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

   
   

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

   • 无法编译？

   • 运行时错误？

   • 正常运行？
     

   Click to show

   都不会！程序会陷入一个循环：它需要在堆上分配空间，但是分配器又需要在堆上分配空间……

   
   

3. 实验

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

      Click to show

      时间复杂度是 O(1)，空间复杂度是 O(n)

      
      

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

   
   

4. 挑战实验（选做）

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

      
      

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

      Click to show

      我们以一个朴素的分配器算法为例：将每一次内存分配记录用链表存起来。

      分配器最初必须具有一个节点的静态空间。而每当它仅剩一个节点空间时，都可以用它来为自己分配一块更大的空间。如此，就实现了分配器动态分配自己。

      再考虑到，每次分配 1KB 或 1MB 都需要额外保存一份元信息。如果只用静态分配，就必须按最坏情况（每次都只分配最小单元）来预先留好空间。使用动态分配就可以减少空间浪费。