内存虚拟化

简单谈一谈对内存虚拟化的理解？

计算机当中的内存条成为物理内存，虚拟化内存即为对物理内存进行抽象，抽象成为地址空间的一个概念。在其中划分了程序代码，栈、堆三个空间，栈用于保存函数的调用信息，分配空间给局部变量，用于传递参数的函数返回值，堆用于管理动态分配的内存。

每个进程使用的内存为成为地址空间的虚拟内存，而不是直接使用物理内存， 首先可以保证易用性，每个进程对地址的使用可以从0KB开始，之后操作系统再将地址空间映射到物理内存的某个位置上。同时可以保证安全性和隔离性。每个进程的地址空间都会被映射到不同的物理内存范围上，除非使用特殊的手段，一个进程在运行期间无法访问到其他进程在物理内存上的映射。

说一说分段内存管理

对于地址空间，如果不进行分段，则需要通过一个基址寄存器和一个范围寄存器将整个地址空间映射到物理内存的某个位置上，存在的问题是不灵活并且容易产生碎片，影响之后内存的分配。

而分段的形式，则可以将整个地址空间分为多个段，可以是代码 + 栈 + 堆，也可以采用更加细致的分法，对于每一段，单独进行映射，从而减少内存碎片的问题。

分段在技术上如何实现

原本地址空间作为整体进行映射只需要一对基址寄存器 + 范围寄存器，分段时可以采用多对寄存器，来对不同的段进行映射。

在寻址时，首先根据地址的前几位找到对应的段，对于后面的几位，需要首先与该段的虚拟内存的段首进行计算，得出一个偏移量，之后再与基址寄存器当中的地址进行偏运算，得到真实的物理地址。

此外，对于栈这种反向增长的段，需要通过一个标志位来表明其增长方向，和基址寄存器偏移运算时偏移量为负

分段形式如何进行空闲内存管理

在分段内存管理下，可以将物理内存视为一个连续的大型的数组，每次分配就会从该数组当中分配走一部分连续的，大小不固定的一部分内存。而空闲空间是通过空闲链表(free_list_)进行管理的。最初链表当中只有一个元素，即完整的数组，如果从物理内存的开头进行分配，则最后空闲链表当中为一个大小变小了的元素，而如果在物理内存的中间进行分配，则会导致物理地址的空闲部分被分割成两份，空闲链表当中即存在两个元素，这样带来的问题，新的较大的内存无法得到分配，如原本30的内存地址在中间分配10的内存，空闲地址被分割成了10 10两个部分，对于15的分配需求则无法满足。

对于上例当中中间的部分进行释放，则会得到10 10 10三段内存空间，此时则需要进行合并，将其合并成一个完整的空闲内存空间。

如果因为当中存在大量的碎片而导致无法进行分配时，可以暂停所有进程的执行，进行一次重新的映射，将内存碎片进行合并。只不过暂停所有进程的执行的代价相当大。

如何对已经分配出去内存进行回收

在通过malloc进行分配内存时，在寻找到一块空闲的物理内存之后，可以创建一个header，在其中保存一些相关的信息，其中至少包含分配的内存空间的大小，也有可能有一些额外的信息来帮助内存空间的释放。之后返回的指针指向header之后的地址。

在通过free进行释放时，可以通过指针运算找到header的位置，之后将header和分配的内存一并释放

段式内存分配的基本策略

  1. 固定分配（Fixed Allocation）：固定分配是最简单的内存分配策略，将内存按照固定大小的段进行划分。每个进程被分配一个或多个固定大小的段，这些段在进程的整个生命周期中保持不变。固定分配适用于不需要动态内存管理的环境。

  2. 等分分配（Equal Allocation）：等分分配将可用内存均匀地划分为若干等大小的段，每个进程被分配一个等大小的段。这种分配策略适用于进程数目固定且相对均匀的场景。

  3. 动态分配（Dynamic Allocation）：动态分配是一种灵活的分配策略，根据进程的需求动态分配内存段。动态分配可以采用以下几种策略：

    • 首次适应（First Fit）：在空闲分区列表中找到第一个大小足够的空闲分区。
    • 最佳适应（Best Fit）：在空闲分区列表中找到最小的足够大小的空闲分区。
    • 最差适应（Worst Fit）：在空闲分区列表中找到最大的足够大小的空闲分区。
    • 下次适应：多维护一个指针，指向上一次查找结束的位置
    • 快速适应（Quick Fit）：将内存划分为几个不同大小的分区，每个分区维护一个空闲链表。根据进程的大小选择相应的空闲链表进行分配。

  4. 伙伴分配（Buddy Allocation）：伙伴分配将可用内存划分为大小为2的幂次方的块，每个块的大小是上一个块大小的两倍。进程申请内存时，分配器会查找大小合适的空闲块，如果找到了比所需大小稍大的块，则会进行分割。如果没有合适的块，将进行内存合并以创建更大的块。

说一下分页内存管理

相比于分段动态的确定分配内存的大小，分页采取的方式是先将物理内存和虚拟内存划分为多个基本单位，一个单位成为一个页(Page)。以页为单位进行虚拟内存和物理内存之间的映射，在地址空间当中，每个Page都有一个id，成为VPN(vitural page number)，而在物理空间当中，存在一个PFN(Physical Frame Number)，对于地址空间当中的一个Page，通过地址转换即可通过VPN得到PFN，从而找到物理内存的地址。

寻址时，地址的前几位作为VPN，经过地址转换得到PFN，后几位作为偏移量找到对应的地址

而VPN到PFN的映射的集合称为页表，由于每个进程的地址空间均为从0开始，因此每个进程都拥有一个独立的页表。

页表的数据结构和存储？

页表本身存储在内存当中，其本质即为一个数组，数组的下标即为VPN，数组的每个元素为一个Entry，称为PTE(Page Table Entry)其中除了存储物理页号PPN之外，还有一些标志位，如有效位，表明该映射是否有效，保护位，存在位，参考位等

如何加速内存的访问过程？

一次完整的内存访问过程需要：

  1. 对地址右移运算得到前几位，求出VPN
  2. 计算出对应PTE在内存当中的位置
  3. 读取出对应的PTE，判断是否有效，如果有效则在其中获取出PPN
  4. 根据PPN + 偏移量计算出真实的物理地址，读取内容

整个过程中涉及到多次内存访问和计算，速度较慢，因此引入缓存机制，称为TLB(Transaction-loolaside-buffer) 对频繁发生虚拟内存到物理地址转换的硬件缓存。

其采取全相联的方式，即只有一个组，一条地址映射可能存在TLB中的任意位置，而一条TLB的结构可以简单的表示为：VPN | PFN | 其他位​，其他位用于表示其是否为一个有效的转换以及读写等保护位

在引入了TLB之后，整个内存访问的过程为：

  1. 检查TLB当中是否存在一个相关映射
  2. 如果存在相关映射并且有效，那么直接获取到对应的PFN，去物理内存当中读取
  3. 如果不存在，则称为TLB未命中，按照之前的方法进行地址转换，并且将获取到的PFN生成一个Entry，添加到TLB当中，而当TLB已满时，可以采用随机或者LRU的方式从中淘汰掉某些Entry，继续添加

谁来处理TLB未命中？

在之前的操作系统当中，通常通过硬件来处理TLB未命中，发生未命中时，硬件遍历页表找到正确的PTE，取出想要的地址映射，用其更新TLB

更加现代的体系结构当中，通常通过软件来处理TLB未命中，发生TLB未命中时，硬件系统跑出一个异常，暂停当前的指令流，并且将特权级别提升至内核模式，跳转到对应的陷阱处理程序，该陷阱处理程序由操作系统提供，在其中通过特权指令更新TLB，从陷阱中返回，之后硬件重试指令则会TLB命中

上下文切换时TLB的处理

由于每个进程均有一个页表，如果TLB也为当前进程所独占的话，每次上下文切换后，其中的映射则全部失效，又需要重新开始建立缓存，因此对应的解决方案为添加一个额外的标志位，称为地址空间标识符(ASID)，可以视为进程标识符(PID)，之后即可多个进程共享TLB。

‍

如何解决页表过大的问题？

由于单级页表采用的管理方式为类似数组的形式，即一开始就确定好VPN和PFN的映射关系，如果存在了改映射，再单独使用有效位进行标识。再加上每个进程均会拥有一个页表，对于32位的地址空间，Page为4KB大小，假设一个Page Table Entry的大小为4个字节，则一个页表的大小为4M，假设当前有100个进程，页表则会占用400MB大小的内存。

  • 最简单的方式即为用更大的Page，Page的大小扩大N倍，即可使Page Table Entry的数量减少到1/N，占用空间缩减为原本的1/N
  • 分段分页混合：分段是将进程的地址空间划分为多个段，每个段具有不同的大小和属性，如代码段、数据段、堆段和栈段等。每个段都有一个段表，用于映射段的逻辑地址到物理地址。由于段的大小可以根据需求进行调整，因此可以避免对整个进程地址空间的映射，节省了内存空间
  • 多级页表：将Page Table分为Page大小的单元，如果该单元内存在有效的映射，则分配该页的Page Table，否则不分配，可以避免为无效的映射额外分配内存进行存储

展开说说多级页表

先以简单的二级多级页表为例，首先将Page Table按照Page的大小进行划分为一个个单元，之后确定一个二级索引，称为Page Directory，其中的每一个条目称为Page Directory Entry（PDE），PDE当中存储有效位和Page Table当中的某一个单元所在的物理内存的位置的PFN。

当Page Table当中某一个单元其中存在有效的映射时，为其建立二级索引，即在Page Directory当中添加一个Entry，包含该单元的物理Page Frame Number，通过这样的形式，对于一个单元中全为无效映射的单元，不为其建立索引，也不为其在物理内存上分配空间，从而简约了内存。

同时，页表也不需要连续存储，可以以Page大小为单位存储在内存的任意位置，之后通过二级索引即可找到。

在进行寻址时，将虚拟地址划分为三段，第一段作为Page Directory索引找到对应的PDE，之后根据PDE当中的PFN去物理内存中读取到对应的Page Table单元，之后第二段作为Page Table的索引，找到对应的PTE，在其中获取到最终的PFN，在使用最后一段作为偏移量，和PFN一起确定最终的物理地址。

而当页表过多时，即Page Directory也无法放入到一个Page当中，可以建立三级索引，此时将虚拟地址划分为4段，按照同样的方式进行索引寻找

同时，多级页表也可以和TLB进行结合，TLB当中为单级形式，记录VPN和最终的PFN的映射，多级索引搜索过程中Page Table单元的PFN不存储于TLB当中，如果TLB未命中，再按照多级索引的方式进行搜索。

介绍一下Swap

之前所假设的都为所有Page全部存储于内存当中，而当内存满了的时候，则需要将一部分没有使用到的内存交换到磁盘上进行存储，此时即可给进程提供一个假象，即当前的计算机上有无穷无尽的内存可供使用，永远不会因为内存不足而导致失败。

在原本的基础上首先在磁盘上开辟一块空间，作为交换空间(Swap Space)，之后对于原本的原本的查找过程，此时则会存在当前的Page不存在于内存当中，已经被交换到了硬盘上，此时需要在Page Table Entry当中添加一位存在位，如果存在，则直接使用PTE当中的PFN在物理内存当中进行读取，如果不存在，此时则触发了一个Page Fault，需要首先将Page从硬盘当中交换到内存当中，之后在进行读取。

说一说Page Fault

Page Fault即为当前读取的Page被交换到了磁盘上，可以通过PTE当中的存在位进行判断，并且在PTE当中存储硬盘地址，用于进行读取，当磁盘完成IO之后，操作系统更新Page Table，将该页标记为存在，更新PTE的PFN字段，用于之后直接从物理内存当中进行读取，并且此时还会更新TLB进行缓存。

当触发了Page Fault之后，操作系统通过某些算法淘汰一个Page，之后从磁盘当中进行读取，之后设置PFN和存在位。

介绍一下内存缓冲淘汰策略

首先缓冲淘汰策略的衡量指标为缓存命中与未命中的处理时间求期望。

提出的最理想的淘汰策略为：当缓存满时，淘汰未来最远的将来才会访问的Page，但是由于对于未来的情况无法估计，因此其只作为最优的情况用于性能评估，看其他的算法在性能上与其性能上的差距。

真实可以实现的有FIFO与Random，以及LRU。其中LRU基于局部性原理（时间局部性与空间局部性）可以取得较好的性能。

在LRU的基础上还有用于解决缓存污染问题的LRU-K和用于减少计算开销的近似LRU

近似LRU：

  1. 时钟算法：时钟算法使用一个环形缓冲区，每个页面有一个访问位，表示是否被访问过。算法维护一个指针，指向当前位置。当页面被访问时，访问位设置为1。当需要淘汰页面时，算法从当前位置开始查找，如果访问位为0，则选择淘汰该页面，并将指针移到下一个位置；如果访问位为1，则将访问位设为0，并将指针移到下一个位置，继续查找。这样，较长时间未被访问的页面会被淘汰，近似实现了LRU算法的效果。
  2. 二次机会算法：二次机会算法是对时钟算法的改进，它在每个页面的基础上添加了一个修改位，表示页面是否被修改过。算法维护一个指针，指向当前位置。当页面被访问时，访问位设置为1，修改位保持不变。当需要淘汰页面时，算法从当前位置开始查找，如果访问位和修改位都为0，则选择淘汰该页面，并将指针移到下一个位置；如果访问位为1，则将访问位设为0，并将指针移到下一个位置，继续查找。如果访问位为0而修改位为1，则将访问位设为1，并将指针移到下一个位置。这样，较长时间未被访问且未被修改的页面会被优先淘汰