CPU虚拟化

抽象：进程

  • 定义：运行中的程序。
  • CPU虚拟化：进程数远大于CPU个数，但每个进程都需要CPU，因此需要对其虚拟化。
    • 时分复用：一个进程只运行一个时间片，然后切换到其他进程，通常使用上下文切换机制与调度策略来实现。（机制回答如何做，策略回答选哪个。）
  • 进程的机器状态：程序在运行时可以读取或更新的内容，包括地址空间（内存）、寄存器、持久存储设备等。
  • 进程API：
    • 创建(create)：运行指定的程序。
      1. 操作系统从磁盘上读取程序的代码和静态数据，加载到进程的地址空间中。
        • 惰性加载：借助分页和交换机制，在程序执行期间需要某些代码或数据片段时它们才会被加载。
      2. 为程序的运行时栈分配内存。
        • C程序使用栈存放局部变量、函数参数和返回地址。
      3. 可能为程序的堆分配一些内存。
        • C程序使用堆存放显式请求的动态分配数据。程序通过调用malloc()来请求这样的空间，并通过调用free()来明确地释放它。
      4. 执行其他初始化任务（尤其是I/O相关的）。
        • 在UNIX系统中，默认情况下每个进程都有3个打开的文件描述符，用于标准输入、输出和错误。
      5. 启动程序，在入口处运行，即main()。通过跳转到main()例程，操作系统将CPU的控制权转移到新创建的进程中，从而程序开始执行。
    • 销毁(destroy)：终止指定的进程。
    • 等待(wait)：等待进程停止运行。
    • 其他控制(control)：暂停(停止运行一段时间)、恢复(继续运行)等。
    • 状态(statu)：获取进程的相关信息。
  • 进程状态：
    1. 运行(running)：进程正在CPU上运行，它正在执行指令。
    2. 就绪(ready)：进程已准备好运行，但由于某种原因，操作系统选择不在此时运行。
    3. 阻塞(blocked)：一个进程执行了某种操作，直到发生其他事件时才会准备运行。
    4. 僵尸状态：初始(initial)是进程在创建时处于的状态，最终(final)进程处于已退出但尚未清理的状态
  • 进程列表：存储进程控制块（PCB），用于跟踪系统中正在运行的所有程序。

机制：受限直接执行

  • 目的：在保持对系统的控制的情况下尽快运行。
  • 直接执行：当OS希望启动程序时，直接在CPU上运行程序。

控制

  • 受限：硬件提供不同的执行模式给操作系统。
    • 用户模式：应用程序不能完全访问硬件资源。用户模式可以陷入(trap)到内核模式从而执行系统调用。
    • 内核模式：操作系统可以访问机器的全部资源。完成系统调用后内核模式可以从陷阱返回(return-from-trap)到用户模式。
    • 操作系统会通过某种特权(Privileged)指令告诉硬件陷阱表(trap table)在内存中的位置，陷阱表在内核启动时就预先规定好，发生哪种异常时执行哪些那代码。
    • 在x86上，CPU会将程序计数器(PC)、标志(flag)和其他一些寄存器推送到每个进程的内核栈（kernel stack）上。return-from-trap时将从栈弹出这些值，并恢复执行用户模式程序。

切换

  • 如何把CPU控制权还给操作系统：
    • 协作方式：早期有些系统使用过，其思想是操作系统相信系统的进程会合理运行。运行时间过长的进程被假定会定期主动放弃CPU，或者当它进行非法操作时被强制终止而放弃CPU。
    • 非协作方式：利用时钟中断，每隔几毫秒产生一次中断。产生中断时，当前正在运行的进程停止，操作系统中预先配置的中断处理程序（interrupthandler）会运行。此时，操作系统重新获得CPU的控制权，因此可以停止当前进程，并启动另一个进程。
      • 操作系统必须通知硬件哪些代码在发生时钟中断时运行；操作系统必须启动时钟（也使用特权操作）；硬件在中断发生时要为正在运行的程序保存足够的状态以便随后从陷阱返回指令能够正确恢复正在运行的程序。
  • 如何选择接下来要执行的进程（继续当前进程还是切换到另一个进程）：使用调度策略。
    • 决定切换到另一个进程：执行上下文切换(context switch)。为当前正在执行的进程保存一些寄存器的值到它的内核栈，并为即将执行的进程从它的内核栈恢复一些寄存器的值并切换内核栈。
      • 通过切换内核栈，内核在进入切换代码调用时，是一个进程（被中断的进程）的上下文，在返回时，是另一进程（即将执行的进程）的上下文。

进程调度

  • 护航效应(convoy effect)：一些耗时较少的潜在资源消费者被排在重量级的资源消费者之后。这会导致平均等待时间变长。
  • 先进先出(FIFO)：先来先服务。
  • 最短任务优先(SJF)：服务最短的任务。
  • 最短完成时间优先(STCF)：向SJF添加抢占，服务当前任务列表最短的任务。
  • 轮转(Round-Robin, RR)：在一个时间片内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束，它反复执行，直到所有任务完成。系统设计者需要权衡时间片的长度，使其足够长，以便摊销上下文切换成本，而又不会使系统不及时响应。
    • 摊销：通过减少成本的频度（即执行较少次的操作），系统的总成本就会降低。
  • 结合I/O：调度程序需要在I/O开始时和I/O完成时做出决定，使任务重叠（进程被I/O阻塞时，切换到其他进程以使CPU被充分利用）

调度程序：多级反馈队列(MLFQ)

  • 问题：需要优化周转时间，但操作系统通常不知道任务要运行多久；需要优化响应时间，又不能降低周转时间。
  • 思想：MLFQ中有许多独立的队列，每个队列有不同的优先级，任何时刻一个工作只能存在于一个队列中，MLFQ总是优先执行在较高优先级队列中的工作，对同样优先级的工作采用轮转调度。
  • 如何设置优先级：如果不知道工作是短工作还是长工作，那么就在开始的时候假设其是短工作。并赋予最高优先级。如果确实是短工作，则很快会执行完毕，否则将被慢慢移入低优先级队列，而这时该工作也被认为是长工作了。此外，还需避免I/O工作过多导致长工作饥饿（提升长时间未处理的低优先级任务，或降低总是在处理的高优先级任务）；高优先级有更短的时间片，低优先级有更长的时间片。
  • 规则总结：
    • 规则1：如果A的优先级 > B的优先级，运行A（不运行B）。
    • 规则2：如果A的优先级 = B的优先级，轮转运行A和B。
    • 规则3：工作进入系统时，放在最高优先级（最上层队列）。
    • 规则 4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。
    • 规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。

调度程序：比例份额

  • 思想：调度程序的最终目标，是确保每个工作获得一定比例的CPU时间，而不是优化周转时间和响应时间。令每个进程都有一些权重（彩票），它被调度运行的概率为占总权重的比例。
  • 机制：
    • 彩票货币：每个用户拥有一些彩票，由用户将这些彩票摊给进程。
    • 彩票转让：一个进程可以临时将自己的彩票交给另一个进程。（在C/S交互场景很有用）
    • 彩票通胀：在进程相互信任的环境中，一个进程可以临时提升或降低自己拥有的彩票数量。
  • 步长调度：一个确定性的公平分配算法。（但和彩票调度比起来，需要全局状态）
    • 系统中的每个工作都有自己的步长，这个值与票数值成反比。每次进程运行后，我们会让它的计数器增加它的步长(记为行程值)，记录它的总体进展。
    • 调度程序使用进程的步长及行程值来确定调度哪个进程。基本思路是：当需要进行调度时，选择目前拥有最小行程值的进程，并且在运行之后将该进程的行程值增加一个步长。

多处理器调度

  • 场景：多个CPU，每个CPU有自己的缓存，但共用一个内存。
  • 缓存基于局部性概念：
    • 时间局部性：指当一个数据被访问后，它很有可能会在不久的将来被再次访问（如循环）
    • 空间局部性：当程序访问地址为x的数据时，很有可能会紧接着访问x周围的数据（如遍历）
  • 缓存一致性问题：通过监控内存访问，硬件可以保证获得正确的数据，并保证共享内存的唯一性。
    • 总线窥探：每个缓存都通过监听连接所有缓存和内存的总线，来发现内存访问。CPU发现对它放在缓存中的数据的更新，会作废（invalidate）本地副本（从缓存中移除），或更新（update）它（修改为新值）。
  • 应用程序/操作系统依然需要关心共享数据的访问。
  • 缓存亲和度：一个进程在某个CPU上运行时，会在该CPU的缓存中维护许多状态。下次该进程在相同CPU上运行时，由于缓存中的数据而执行得更快。相反，在不同的CPU上执行，会由于需要重新加载数据而很慢。因此多处理器调度应该考虑到这种缓存亲和性，并尽可能将进程保持在同一个CPU上。
  • 单队列调度（SQMS）：一共只有一个队列，能够从单CPU调度程序很简单地发展而来，但扩展性不好（有数据共享/同步问题），不能很好保证缓存亲和性。
  • 多队列调度（MQMS）：包含多个调度队列，每个队列可以使用不同的调度规则，扩展性好、缓存亲和度好，但可能会有负载不均问题（通过工作的跨CPU迁移，可以真正实现负载均衡，具体实现可以是工作窃取：工作量较少的（源）队列不定期地“偷看”其他（目标）队列是不是比自己的工作多。如果目标队列比源队列（显著地）更满，就从目标队列“窃取”一个或多个工作，实现负载均衡。）

内存虚拟化

抽象：地址空间

  • 地址空间：是运行的程序看到的系统中的内存，包含运行的程序的所有内存状态。
    • 程序的代码指令。
    • 使用栈保存当前的函数调用信息，分配空间给局部变量、传递参数和函数返回值。
    • 使用堆管理动态分配的、用户管理的内存。
  • 虚拟内存的目标：
    • 透明：程序的行为就好像它拥有自己的私有物理内存。
    • 效率：虚拟内存不会使程序运行得更慢，也不需要太多额外的内存来支持虚拟化。
    • 保护：一个进程不会受另一个进程影响。

机制：地址转换

  • 是受限直接执行的扩展。
  • 利用地址转换，硬件对每次内存访问进行处理（指令获取、数据读取或写入）时，将指令中的虚拟地址转换为数据实际存储的物理地址。
  • 操作系统序要管理内存，记录被占用和空闲的内存位置，保持对内存使用的控制。
  • 拦截(interposition)：在虚拟内存中，硬件可以介入到每次内存访问中，将进程提供的虚拟地址转换为数据实际存储的物理地址。
  • 动态重定位（基于硬件）：每个CPU需要两个硬件寄存器，base寄存器和bound/limit寄存器，两个寄存器确定进程地址空间的范围。转换规则为：physical address = virtual address + base
    • 硬件中负责地址转换的部分统称为内存管理单元（MMU），上述两个寄存器在MMU中。
    • 动态重定位的硬件要求：处在特权模式下，需要一对寄存器支持地址转换和界限检查并通过电路完成功能，有修改两个寄存器、注册异常处理程序的特权指令，如果越界则触发异常。
    • 动态重定位的操作系统要求：需要为新进程分配内存，从终止的进程回收内存，一般通过空闲链表来管理内存。上下文切换时正确设置两个寄存器。当异常发生时执行的处理代码。
      • 空闲列表：记录当前没有使用的物理内存的范围（堆上）。
  • 静态重定位（基于软件）：loader软件接手将要运行的可执行程序，将它的地址重写到物理内存中期望的偏移位置。（在硬件支持重定位前使用，不提供访问保护且难以再次重定位）
  • 动态重定位的优化思路：消除内部碎片，栈区堆区较小时分配的空间内有未使用却不能再分配的空间。

分段

  • 问题：内部碎片。栈和堆之间的空间并没有被进程使用，却依然占用了实际的物理内存。
  • 解决办法：在MMU中引入不止一个基址和界限寄存器对，而是给地址空间内的每个逻辑段（segment）一对。一个段只是地址空间里的一个连续定长的区域，在典型的地址空间里有 3 个逻辑不同的段：代码、栈和堆。分段的机制使得操作系统能够将不同的段放到不同的物理内存区域，从而避免了虚拟地址空间中的未使用部分占用物理内存。
  • 段错误：在支持分段的机器上发生了非法的内存访问。
  • 区分引用了哪个段：
    • 显式方式：用虚拟地址的开头几位来标识不同的段
    • 隐式方式：硬件通过地址产生的方式来确定段，如果地址由程序计数器产生（即它是指令获取），那么地址在代码段。如果基于栈或基址指针，它一定在栈段。其他地址则在堆段。
  • 反向增长：段寄存器用一位区分是否反向增长，栈是其他不是。
  • 共享内存：为每个段增加了几个位，标识程序是否能够读写该段，或执行其中的代码。
  • 问题：外部碎片。已分配的内存是非紧凑的。
    • compact：重新安排原有的段。会占用大量的处理器时间。
    • 空闲列表管理算法：试图保留大的内存块用于分配。包括最优匹配（best-fit，从空闲链表中找最接近需要分配空间的空闲块返回）、最坏匹配（worst-fit）、首次匹配（first-fit）以及伙伴算法（buddy algorithm）等。无论算法多么精妙，都无法完全消除外部碎片，好的算法只是试图减小它。

空闲空间管理

  • 问题：外部碎片。
  • 大多数分配程序都会在头块（header）中保存一点额外的信息。（幻数：完整性。大小：方便free函数）
  • 最优匹配：首先遍历整个空闲列表，找到和请求大小一样或更大的空闲块，然后返回这组候选者中最小的一块。
  • 最差匹配：它尝试找最大的空闲块，分割并满足用户需求后，将剩余的块（很大）加入空闲列表。
  • 首次匹配：找到第一个足够大的块，将请求的空间返回给用户。（不需要遍历所有空闲块）
  • 下次匹配：多维护一个指针，指向上一次查找结束的位置。其想法是将对空闲空间的查找操作扩散到整个列表中去，避免对列表开头频繁的分割。
  • 分离空闲列表：如果某个应用程序经常申请一种（或几种）大小的内存空间，那就用一个独立的列表，只管理这样大小的对象。其他大小的请求都交给更通用的内存分配程序。
    • 在内核启动时，它为可能频繁请求的内核对象创建一些对象缓存（object cache），如锁和文件系统inode等。这些的对象缓存每个分离了特定大小的空闲列表，因此能够很快地响应内存请求和释放。如果某个缓存中的空闲空间快耗尽时，它就向通用内存分配程序申请一些slab（总量是页大小和对象大小的公倍数）。相反，如果给定slab中对象的引用计数变为0，通用的内存分配程序可以从专门的分配程序中回收这些空间，这通常发生在虚拟内存系统需要更多的空间的时候。
  • 伙伴系统：让合并变得简单。
    • 空闲空间首先从概念上被看成大小为2^n的大空间。当有一个内存分配请求时，空闲空间被递归地一分为二，直到刚好可以满足请求的大小（再一分为二就无法满足）。这时，请求的块被返回给用户。
    • 块被释放时。如果将这个块归还给空闲列表，分配程序会检查“伙伴”是否空闲。如果是，就合二为一，变成更大的块。这个递归合并过程继续上溯，直到合并整个内存区域，或者某一个块的伙伴还没有被释放。
    • 伙伴系统运转良好的原因，在于很容易确定某个块的伙伴。每对互为伙伴的块只有一位不同，正是这一位决定了它们在整个伙伴树中的层次。

分页

  • 虚拟内存：页。物理内存：页帧。
  • 避免碎片化的空间管理方法：将空间分割成固定长度的分片。
    • 需要用页来实现虚拟内存。
    • 通过完善的分页方法，操作系统能够高效地提供地址空间的抽象，不管进程如何使用地址空间。
  • 页表：为了记录地址空间的每个虚拟页放在物理内存中的位置，操作系统通常为每个进程保存一个数据结构，称为页表。页表的主要作用是为地址空间的每个虚拟页面保存地址转换（address translation），从而让我们知道每个页在物理内存中的位置（页号->帧号）
    • 虚拟地址划分为虚拟页号和页内偏移量，地址长度取决于虚拟空间大小。
    • 将虚拟页号替换为物理帧号就可以将地址发送给物理内存
  • 页表可以非常大，因此很基本不能全都放到内存中，页表可以存储在操作系统的虚拟内存中。
  • 页表项（PTE）的内容：
    • 有效位（valid bit）通常用于指示特定地址转换是否有效。对于支持稀疏地址空间至关重要。通过简单地将地址空间中所有未使用的页面标记为无效，我们不再需要为这些页面分配物理帧，从而节省大量内存。
    • 保护位（protection bit），表明页是否可以读取、写入或执行
    • 存在位（present bit）表示该页是在物理存储器还是在磁盘上
    • 脏位（dirty bit）表明页面被带入内存后是否被修改过。
    • 参考位（reference bit，也被称为访问位，accessed bit）有时用于追踪页是否被访问，也用于确定哪些页很受欢迎，因此应该保留在内存中。

快速地址转换（TLB）

  • 使用硬件加速虚拟地址转换，尽量避免额外的内存访问（映射信息一般存储在物理内存中）。
  • 对每次内存访问，硬件先检查TLB，看看其中是否有期望的转换映射，如果有，就完成转换（很快），不用访问页表（其中有全部的转换映射）。
  • 算法流程：
    • 首先从虚拟地址中提取页号（VPN），然后检查TLB是否有该VPN的转换映射。
    • 如果有，我们有了TLB命中，接下来我们就可以从相关的TLB项中取出页帧号（PFN），与原来虚拟地址中的偏移量组合形成期望的物理地址（PA），并问内存，假定保护检查没有失败。
    • 如果没有，硬件访问页表来寻找转换映射，并用该转换映射更新TLB，假设该虚拟地址有效，而且我们有相关的访问权限。当TLB更新成功后，系统会重新尝试该指令，这时TLB中有了这个转换映射，内存引用得到很快处理。
  • TLB的成功依赖于空间和时间局部性。
    • 时间局部性是指，最近访问过的指令或数据项可能很快会再次访问。
    • 空间局部性是指，当程序访问内存地址x时，可能很快会访问邻近x的内存。
  • TLB未命中的管理：
    • x86：硬件管理。硬件通过页表基址寄存器知道页表在内存中的确切位置，以及页表的确切格式。发生未命中时，硬件会“遍历”页表，找到正确的页表项，取出想要的转换映射，用它更新TLB，并重试该指令。
    • RISC：操作系统管理。发生TLB未命中时，硬件系统会抛出一个异常，这会暂停当前的指令流，将特权级提升至内核模式，跳转至陷阱处理程序，这个陷阱处理程序是操作系统的一段代码，用于处理TLB未命中。这段代码在运行时，会查找页表中的转换映射，然后用特别的“特权”指令更新TLB，并从陷阱返回（硬件必须从导致陷阱的指令继续执行而不是像函数调用那样继续执行此次调用之后的语句）。
  • 有效位：
    • 如果一个页表项（PTE）被标记为无效，就意味着该页并没有被进程申请使用，正常运行的程序不应该访问该地址。当程序试图访问这样的页时，就会陷入操作系统，操作系统会杀掉该进程。
    • TLB的有效位只是指出TLB项是不是有效的地址映射，在系统上下文切换时系统可以确保将要运行的进程不会错误地使用前一个进程的虚拟到物理地址转换映射。
  • 区分不同进程的映射：地址空间标识符（Address Space Identifier，ASID）使不同进程可以共享TLB
  • 缓存替换策略：随机替换，因为TLB大小很小。

缩小页表

  • 时空折中：通常，如果你希望更快地访问特定的数据结构，就必须为该结构付出空间的代价。
  • 缩小页表最直观的做法：增加页大小。但会带来内部碎片问题。
  • 分页和分段：不是为进程的整个地址空间提供单个页表，而是为每个逻辑分段提供一个。每个分段都有界限寄存器，每个界限寄存器保存了段中最大有效页的值。栈和堆之间未分配的页不再占用页表中的空间。但依赖分段，仍可能带来页表浪费。
  • 多级页表：现在常用的方法。首先，将页表分成页大小的单元。然后，如果整页的页表项（PTE）无效，就完全不分配该页的页表。为了追踪页表的页是否有效（以及如果有效，它在内存中的位置），使用了名为页目录（page directory）的新结构。页目录因此可以告诉你页表的页在哪里，或者页表的整个页不包含有效页。
    • 优点：多级页表分配的页表空间，与你正在使用的地址空间内存量成比例。因此它通常很紧凑，并且支持稀疏的地址空间。
    • 缺点：在TLB未命中时，需要从内存加载多次，才能从页表中获取正确的地址转换信息（若干次用于页目录，一次用于PTE本身），而用线性页表只需要一次加载，而且处理也较为复杂。
  • 反向页表：系统中只有一个，页表项告诉我们哪个进程正在使用此页，以及该进程的哪个虚拟页映射到此物理页。
  • 系统将过大的页表放入内核虚拟内存（kernel virtual memory），从而允许系统在内存压力较大时，将这些页表中的一部分交换（swap）到磁盘。

超越物理内存

  • 多道程序（能够“同时”运行多个程序，更好地利用机器资源）和易用性（不用手动处理内存分配）都需要操作系统支持比物理内存更大的地址空间。因此，操作系统需要把当前没有在用的那部分地址空间找个地方存储起来。这个地方空间足够大，但访问也会更慢（磁盘）。
  • 交换空间（swap space）：磁盘上开辟的空间，内存中的页在不需要时交换到其中，并在需要的时候又交换回内存。操作系统需要记住给定页的硬盘地址。
  • 存在位：位于页表项（PTE）中，为1则表示该页存在于物理内存中。访问不在物理内存中的页，这种行为通常被称为页错误（page fault）。
  • 页错误：如果一个页不存在，它已被交换到硬盘，在处理页错误的时候，操作系统需要将该页交换到内存中。操作系统可以用PTE中的某些位来存储硬盘地址，这些位通常用来存储像页的PFN这样的数据。当操作系统接收到页错误时，它会在PTE中查找地址，并将请求发送到硬盘，将页读取到内存中。
    • 当I/O在运行时，进程将处于阻塞（blocked）状态。因此，当页错误正常处理时，操作系统可以自由地运行其他可执行的进程。因为I/O操作是昂贵的，一个进程进行I/O（页错误）时会执行另一个进程，这种交叠（overlap）是多道程序系统充分利用硬件的一种方式。
  • 页交换策略：选择哪些页被交换出或被替换。
    • 最优替换策略：能达到总体未命中数量最少，但很难实现（未来的访问是无法知道）。其思想是，替换内存中在最远将来才会被访问到的页，可以达到缓存未命中率最低。
    • FIFO：页在进入系统时，简单地放入一个队列。当发生替换时，队列尾部的页（“先入”页）被踢出。FIFO最大的优势是实现相当简单。没有栈特性（大小为N + 1的缓存自包括大小为N的缓存的内容）容易出现异常行为。
    • 随机：凭运气。
    • LRU：利用历史数据（局部性原则）最近最少使用。
      • 近似LRU（避免扫描所有页以找到最旧的页，只找到差不多旧的页即可）：在硬件上设置一个引用位（use bit）每当页被引用（即读或写）时，硬件将使用位设置为1，由操作系统将其置为0。
      • 时钟指针：开始时指向某个特定的页（哪个页不重要）。当必须进行页替换时，操作系统检查当前指向的页P的使用位是1还是0。如果是1，则意味着页面P最近被使用，因此不适合被替换。然后，P的使用位设置为0，时钟指针递增到下一页（P + 1）。该算法一直持续到找到一个使用位为0的页，使用位为0意味着这个页最近没有被使用过（在最坏的情况下，所有的页都已经被使用了，那么就将所有页的使用位都设置为0）。
      • 如果页已被修改（modified）并因此变脏（dirty），则踢出它就必须将它写回磁盘，这很昂贵。如果它没有被修改（因此是干净的，clean），踢出就没成本。物理帧可以简单地重用于其他目的而无须额外的I/O。因此，一些虚拟机系统更倾向于踢出干净页，而不是脏页。为了支持这种行为，硬件应该包括一个修改位（modified bit，又名脏位，dirty bit）。每次写入页时都会设置此位。
  • 缓存未命中的类型：
    • 强制性未命中（冷启动未命中）：因为缓存开始是空的，而这是对项目的第一次引用。
    • 容量未命中：由于缓存的空间不足而不得不踢出一个项目以将新项目引入缓存。
    • 冲突未命中：硬件缓存中对项的放置位置有限制。
  • 当程序从内存中读取数据时发生了什么？
    • 硬件控制流首先从虚拟地址中提取页号（VPN），然后检查TLB是否有该VPN的转换映射。TLB未命中时有3种重要情景。第一种情况，该页存在（present）且有效（valid）在这种情况下，TLB未命中处理程序可以简单地从PTE中获取PFN，然后重试指令（这次TLB会命中），并因此继续前面描述的流程。第二种情况页错误处理程序需要运行。虽然这是进程可以访问的合法页，但它并不在物理内存中。第三种情况，访问的是一个无效页，可能由于程序中的错误。在这种情况下，PTE中的其他位都不重要了。硬件捕获这个非法访问，操作系统陷阱处理程序运行，可能会杀死非法进程。
    • 软件控制流首先操作系统必须为将要换入的页找到一个物理帧，如果没有这样的物理帧，我们将不得不等待交换算法运行，并从内存中踢出一些页，释放帧供这里使用。在获得物理帧后，处理程序发出I/O请求从交换空间读取页。最后，当这个慢操作完成时，操作系统更新页表并重试指令。重试将导致TLB未命中，然后再一次重试时，TLB命中，此时硬件将能够访问所需的值。
  • 交换真正发生的时机：操作系统可以主动地预留一小部分空闲内存。大多数操作系统会设置高水位线（High Watermark，HW）和低水位线（Low Watermark，LW），来帮助决定何时从内存中清除页。
    • 当操作系统发现有少于LW个页可用时，后台负责释放内存的线程会开始运行，直到有HW个可用的物理页。这个后台线程有时称为交换守护进程（swap daemon）或页守护进程（page daemon）[1]，它然后会很开心地进入休眠状态，因为它毕竟为操作系统释放了一些内存。因此交换算法需要先简单检查是否有空闲页，而不是直接执行替换。如果没有空闲页，会通知后台分页线程按需要释放页。

并发

抽象：线程

  • 线程有一个程序计数器（PC），记录程序从哪里获取指令。每个线程有自己的一组用于计算的寄存器。一个进程内的多个线程共享地址空间，从而能够访问相同的数据。
    • 上下文切换：进程将状态保存到进程控制块（Process Control Block，PCB）线程将状态保存到线程控制块（Thread Control Block，TCB）但是，与进程相比，线程之间的上下文切换有一点主要区别：地址空间保持不变（即不需要切换当前使用的页表）。
    • 线程和进程之间的另一个主要区别在于栈。单线程进程只有一个位于地址空间底部的栈。多线程进程有多个与线程相关的栈（thread-local）
  • 并发相关术语：
    • 临界区（critical section）是访问共享资源的一段代码，资源通常是一个变量或数据结构。
    • 竞态条件（race condition）出现在多个执行线程大致同时进入临界区时，它们都试图更新共享的数据结构，导致了令人惊讶的（也许是不希望的）结果。
    • 不确定性（indeterminate）程序由一个或多个竞态条件组成，程序的输出因运行而异，具体取决于哪些线程在何时运行。这导致结果不是确定的（deterministic），而我们通常期望计算机系统给出确定的结果。
    • 为了避免这些问题，线程应该使用某种互斥（mutualexclusion）原语。这样做可以保证只有一个线程进入临界区，从而避免出现竞态，并产生确定的程序输出。

锁、条件变量、信号量

  • 作用：通过给临界区加锁，可以保证临界区内只有一个线程活跃。
  • 锁的实现：需要硬件和操作系统的帮助。
    • 硬件指令：
      1. 在临界区关闭中断。优点是简单，缺点包括需要线程执行特权操作；不支持多处理器；中断丢失可能导致严重的系统问题；效率低。
      2. test-and-set指令：x86上为xchg，它返回旧值同时将其更新为新值。可以实现自旋锁。
      3. compare-and-exchange指令：它比较当前值与期待值是否相等，如果是则更新为新值，返回旧值。
      4. load-linked&store-conditional：链接加载从内存中取出值存入一个寄存器，条件存储只有上一次加载的地址在期间都没有更新时，才会成功，（同时更新刚才链接的加载的地址的值）
      5. fetch-and-add：原子地返回特定地址的旧值，并且让该值自增一。这个解决方案使用了ticket和turn变量来构建锁。基本操作也很简单：如果线程希望获取锁，首先对一个ticket值执行一个原子的获取并相加指令。这个值作为该线程的“turn”（顺位，即myturn）。根据全局共享的lock->turn变量，当某一个线程的（myturn == turn）时，则轮到这个线程进入临界区。unlock则是增加turn，从而下一个等待线程可以进入临界区。
    • 操作系统：
      1. yield()：线程可以调用它主动放弃CPU，让其他线程运行。
      2. 调度过程中存在着太多偶然性，因此需要显式地施加控制，决定锁释放时，谁能抢到锁。需要一个队列来保存等待锁的线程。park()能够让调用线程休眠，unpark(threadID)则会唤醒threadID标识的线程。
  • 锁的评价标准：
    • 基本任务：提供互斥。
    • 公平性：当锁可用时，是否每一个竞争线程有公平的机会抢到锁/是否有竞争锁的线程会饿死（starve），一直无法获得锁？
    • 性能：使用锁之后增加的时间开销（扩展性：线程数增加时的性能与单线程时的性能比较）
  • 如何给数据结构加锁：
    • 通用方法：添加一把大锁。
    • 懒惰计数器（sloppy counter）：通过多个局部；计数器和一个全局计数器来实现一个逻辑计数器，其中每个CPU核心有一个局部计数器。每个局部计数器有一个锁，全局计数器有一个。如果一个CPU上的线程想增加计数器，那就增加它的局部计数器，访问这个局部计数器是通过对应的局部锁同步的。因为每个CPU有自己的局部计数器，不同CPU上的线程不会竞争，所以计数器的更新操作可扩展性好。但是，为了保持全局计数器更新（以防某个线程要读取该值），局部值会定期转移给全局计数器，方法是获取全局锁，让全局计数器加上局部计数器的值，然后将局部计数器置零。转移频率S越小，懒惰计数器则越趋近于非扩展的计数器。S越大，扩展性越强，但是全局计数器与实际计数的偏差越大。
    • 过手锁（hand-over-hand locking）：每个节点都有一个锁，替代之前整个链表一个锁。遍历链表的时候，首先抢占下一个节点的锁，然后释放当前节点的锁。这种并发的方案也不一定会比单锁的方案快。
    • 并发队列：有两个锁，一个负责队列头，另一个负责队列尾。这两个锁使得入队列操作和出队列操作可以并发执行，因为入队列只访问tail锁，而出队列只访问head锁。在队列空或者满时，能让线程等待
    • 并发散列表：每个散列桶都有一个锁（可以使用并发链表）
  • 条件变量：
    • 目的：在很多情况下，线程需要检查某一条件满足之后，才会继续运行。
    • 条件变量是一个显式队列，当某些执行状态（即条件，condition）不满足时，线程可以把自己加入队列，等待（waiting）该条件。另外某个线程，当它改变了上述状态时，就可以唤醒一个或者多个等待线程（通过在该条件上发信号），让它们继续执行。
    • 线程要睡眠的时候，调用wait()。当线程想唤醒等待在某个条件变量上的睡眠线程时，调用signal()。wait()调用有一个参数，它是互斥量。它假定在wait()调用时，这个互斥量是已上锁状态。wait()的职责是释放锁，并让调用线程休眠（原子地）。当线程被唤醒时（在另外某个线程发信号给它后），它必须重新获取锁，再返回调用者。而在调用signal()时建议持有锁
  • 多个生产者消费者问题：检查检查条件变量时总是使用while，使用多个条件变量区分不同的唤醒的角色。
  • 覆盖条件：当不知道该唤醒哪个线程时，可以广播信号。（但尽量不这样做，因为唤醒了许多不必被唤醒的线程）
  • 信号量：sem_wait()将信号量的值减1，如果结果小于0，则挂起线程。sem_post()将信号量的值加1，如果结果小于0，就唤醒一个线程。
    • 用作锁（二值信号量）：初始值为1，只有持有/未持有两种状态。
    • 用作条件变量：初始值为0。
    • 解决问题：生产者消费者（有界缓冲区）问题、读者写者锁（写锁保证只有一个写者能获得锁进入临界区，读锁维护有多少个读者在访问该数据结构，当第一个读者获取该锁时，读者也会获取写锁，这样可能饿死写者）、哲学家就餐问题
    • 实现：用一个锁和一个条件变量实现，维护一个计数器

常见并发问题

  • 违反原子性缺陷：代码段本意是原子的，但在执行中并没有强制实现原子性。
    • 解决方案：给共享变量的访问加锁，确保每个线程访问共享变量时，都持有锁。
  • 违反顺序缺陷：A应该在B之前执行，但是实际运行中却不是这个顺序。
    • 解决方案：通过条件变量进行同步。
  • 死锁缺陷：
    • 死锁经常发生，原因是大型系统设计过于复杂，以及封装隐藏了实现细节。
    • 产生死锁的四个条件：
      1. 互斥：线程对于需要的资源进行互斥的访问。
        • 避免互斥：通过强大的硬件指令，避免需要锁的数据结构。
      2. 持有并等待：线程持有了资源，同时又在等待其他资源。
        • 破除持有并等待：通过原子操作抢锁，抢锁前先抢全局锁。
      3. 非抢占：线程获得的资源，不能被抢占。
        • 破除非抢占：trylock()函数会尝试获得锁，或者返回−1，表示锁已经被占有（释放已经持有的锁），可以稍后重试一下。
        • 活锁：几个线程一直进行尝试持有一个锁并获得另下一个锁，但总是尝试失败，可以使等待时间随机化，防止反复干扰。
      4. 循环等待：线程之间存在一个环路，环路上每个线程都额外持有一个资源，而这个资源又是下一个线程要申请的。
        • 破除循环等待：全序，只要每个线程都以相同顺序获取锁就不会死锁；偏序，安排锁的获取并避免死锁。（当一个函数要抢占多个锁时，为了避免设计失误，通常根据锁的地址高低按顺序获得）

基于事件的并发

  • 不用线程，显式控制调度以保证对并发的控制，从而避免多线程应用中出现的问题。
  • 最简单的基于事件的服务器：一次只处理一个事件，不需要获得或释放锁，单线程，但发出阻塞调用会使整个服务器被阻塞。
while(1){
    events = getEvents();
    for(e in events)
        processEvent(e);
}
  • 重要API：select()或poll()
  • 通过异步I/O使服务器支持阻塞调用。发出异步I/O请求后会立即返回使服务器可以继续工作，服务器可以周期性地轮询所述I/O是否已完成，或者使用信号(signal)在完成时发生中断。
  • 状态管理：当事件处理程序发出异步I/O时，它必须打包一些程序状态，以便下一个事件处理程序在I/O最终完成时使用。这个额外的工作在基于线程的程序中是不需要的，因为程序需要的状态在线程栈中
  • 在现代多核系统上，无锁的简单事件处理已不再可能。

持久性

I/O设备

  • 操作系统与I/O设备交互的基础协议：
    1. 操作系统轮询状态寄存器，等待设备进入可以接收命令的就绪状态。
    2. 操作系统下发数据到数据寄存器。
    3. 操作系统将命令写入命令寄存器，这样设备就知道数据已经准备好了，它应该开始执行命令。
    4. 操作系统轮询状态寄存器，等待并判断设备是否执行完成命令（有可能得到一个指示成功或失败的错误码）。
  • 中断与轮询：中断允许计算与I/O重叠以此提高CPU利用率，但如果设备非常快，那么最好的办法反而是轮询（没有中断处理和上下文切换开销）
    • 混合两阶段：如果设备的速度未知，或者时快时慢，先尝试轮询一小段时间，如果设备没有完成操作，此时再使用中断。
    • 网络端不适合使用中断。
    • 合并：设备在抛出中断之前往往会等待一小段时间，在此期间，其他请求可能很快完成，因此多次中断可以合并为一次中断抛出，从而降低处理中断的代价。当然，等待太长会增加请求的延迟，这是系统中常见的折中。
  • DMA（Direct Memory Access）：它可以协调完成内存和设备间的数据传递，不需要CPU介入。为了能够将数据传送给设备，操作系统会通过编程告诉DMA数据在内存的位置，要拷贝的大小以及要拷贝到哪个设备。在此之后，操作系统就可以处理其他请求了。当DMA的任务完成后，DMA控制器会抛出一个中断来告诉操作系统自己已经完成数据传输。
  • 操作系统如何与I/O设备通信：
    1. 使用明确的I/O指令：这些指令规定了操作系统将数据发送到特定设备寄存器的方法。
    2. 内存映射：硬件将设备寄存器作为内存地址提供。当需要访问设备寄存器时，操作系统读取或写入到该内存地址；然后硬件会将装载/存入转移到设备上，而不是物理内存。
  • 设备驱动程序：
    文件系统栈

磁盘驱动器

  • 接口：磁盘驱动器由大量扇区（512字节块）组成，每个扇区都可以读取或写入。在具有n个扇区的磁盘上，扇区从0到n−1编号。因此，我们可以将磁盘视为一组扇区，0到n−1是驱动器的地址空间（address space）。单个扇区的写入是原子的。
  • 单磁道具有旋转延迟，多磁道具有寻道时间。
  • 磁道缓冲区：即它的缓存，是少量的内存（通常大约8MB或16MB），驱动器可以使用这些内存来保存从磁盘读取或写入磁盘的数据。
  • 写入完成：在将数据放入其内存之后回报写入完成（后写write back缓存）或者在将数据实际写入磁盘之后回报写入完成（直写write through）。后写缓存有时会使驱动器看起来“更快”，但可能有危险。如果文件系统或应用程序要求将数据按特定顺序写入磁盘以保证正确性，后写缓存可能会导致问题。
  • 磁盘调度：由操作系统检查请求并决定下一个要调度的请求。磁盘调度程序将尝试在其操作中遵循SJF（最短任务优先）的原则。
    • SSTF最短寻道时间优先：改进为NBF最近块优先，但会有饥饿问题。
    • SCAN电梯：简单地以跨越磁道的顺序来服务磁盘请求。我们将一次跨越磁盘称为扫一遍。因此，如果请求的块所属的磁道在这次扫一遍中已经服务过了，它就不会立即处理，而是排队等待下次扫一遍。变体为C-SCAN，往复扫描而非循环扫描。这种方法忽视了旋转带来的影响。
    • SPTF最短定位时间优先：视情况而定（寻道和旋转哪个更快就做哪个）
  • 在向磁盘发出I/O之前，系统应该等待多久：
    • 工作保全：即使有一个磁盘I/O，也应立即向驱动器发出请求。
    • 非工作保全：等待一段时间。通过等待，新的和“更好”的请求可能会到达磁盘，从而整体效率提高。

文件和目录

  • 目的：管理持久存储设备。
  • 文件：一个线性字节数组，每个字节都可以读取或写入。每个文件都有某种低级名称（low-level name）称为inode号，用户通常不知道这个名字，每个文件都一个与其关联的inode号。内容是一些二进制数据。
  • 目录：每个目录也有一个与其关联的inode号。它的内容包含一个（用户可读名字，低级名字）对的列表
  • 文件系统接口：
    • open()：打开/创建/覆盖文件，返回一个文件描述符。
      • 文件描述符只是一个整数，是每个进程私有的（线程共享），在UNIX系统中用于访问文件。每个正在运行的进程已经打开了3个文件：标准输入（进程可以读取以接收输入），标准输出（进程可以写入以便将信息显示到屏幕），以及标准错误（进程可以写入错误消息）。这些分别由文件描述符0、1和2表示。
    • read()：读取指定文件描述符对应文件的一些字节。
    • write()：写入指定文件描述符对应文件的一些字节。出于性能的原因，这些写入将在内存中缓冲一段时间。
    • lseek()：将文件偏移量定位到特定位置。
    • fsync()：文件系统通过强制将所有脏（dirty）数据（即尚未写入的）写入磁盘来响应，针对指定文件描述符引用的文件。
    • rename()：文件重命名，是一个原子操作。
    • stat()/fstat()：获取文件元信息，填充一个stat结构。每个文件系统通常将这种类型的信息保存在一个名为inode的结构中
    • unlink()：删除文件。在文件系统树中创建条目使用link()，它的参数是一个旧路径名和一个新路径名，在要创建链接的目录中创建了另一个名称，并将其指向原有文件的相同inode号
    • mkdir()：创建目录
    • opendir()：打开目录
    • readdir()：读取目录内容
    • closedir()：关闭目录
    • rmdir()：删除目录
  • 创建文件时，首先，要构建一个结构（inode），它将跟踪几乎所有关于文件的信息，包括其大小、文件块在磁盘上的位置等等。其次，将人类可读的名称链接到该文件，并将该链接放入目录中。
  • 硬链接：ln，多个文件名指向同一文件底层元数据。链接时增加引用计数，解链接时减少引用计数。不能创建目录的硬链接（因为担心会在目录树中创建一个环）。不能硬链接到其他磁盘分区中的文件（因为inode号在特定文件系统中是唯一的，而不是跨文件系统）
  • 符号链接/软连接：ln -s，符号链接是一个不同类型的文件，它将链接指向文件的路径名作为链接文件的数据。它可以用于硬链接不能应用的场景，但删除原始文件会导致符号链接指向不再存在的路径名。
  • 创建并挂载文件系统：从许多底层文件系统创建完整的目录树，先制作文件系统，然后挂载它们，使其内容可以访问。
    • mkfs：为该工具提供一个设备，一种文件系统类型，它就在该磁盘分区上写入一个空文件系统，从根目录开始。
    • mount()：以现有目录作为目标挂载点（mount point），本质上是将新的文件系统粘贴到目录树的这个点上。从而可以在统一的文件系统树中进行访问。

文件系统实现

  • 磁盘空间：划分成块，用于存储超级块（包含关于该特定文件系统的信息）、分配结构（记录inode或数据块空闲或已分配，inode位图和数据位图）、inode（文件元信息）、数据。

inode

  • 文件元信息：
    • 文件类型（例如，常规文件、目录等）
    • 大小
    • 分配给它的块数
    • 保护权限信息（如谁拥有该文件以及谁可以访问它）
    • 一些时间信息（包括文件创建、修改或上次访问的时间）
    • 有关其数据块驻留在磁盘上的位置的信息（如某种类型的指针，硬链接计数等）。
  • inode如何引用数据块的位置：
    • 多级索引：每个inode有一些固定数量的直接指针和间接指针，间接指针指向包含更多指针的块，每个指针指向用户数据。如果想支持更大的文件，就用多重间接指针。（ext）
    • 基于范围的方法：范围就是一个磁盘指针加一个长度（以块为单位），以此指定文件的磁盘位置。
    • 基于链接的方法：inode中只需要一个指向第一个块的指针，每个块指向下一个块。一些系统在内存中保留链接信息表，而不是将下一个指针与数据块本身一起存储。该表用数据块D的地址来索引，一个条目的内容就是D的下一个指针，即D后面的文件中的下一个块的地址。那里也可以是空值（表示文件结束），或用其他标记来表示一个特定的块是空闲的。拥有这样的下一块指针表，使得链接分配机制可以有效地进行随机文件访问，只需首先扫描（在内存中）表来查找所需的块，然后直接访问（在磁盘上）。(FAT)
  • 根目录的inode必须是众所周知的。（UNIX系统中通常为2）

访问路径

  • 打开文件：文件系统从根开始递归遍历路径名，从而找到所需的inode并读入内存，然后进行权限检查，在进程的打开文件表中，为此进程分配一个文件描述符，并将它返回给用户。
  • 读取文件：读取时从偏移量位置开始，查阅inode以查找这个块的位置。用新的最后访问时间更新inode。读取将进一步更新此文件描述符在内存中的打开文件表，更新文件偏移量。
  • 文件创建：先读取inode位图，再向inode位图写入更新，表示分配了新的inode。再读取目录的inode，向所在目录中写入数据，并更新目录inode。
  • 写入磁盘：先读取数据位图，再向数据位图写入更新，表示分配了新的块。再读取inode，用新块的位置对其更新，最后写入数据块。
  • 动态划分缓存：将虚拟内存页面和文件系统页面集成到统一页面缓存中。通过这种方式，可以在虚拟内存和文件系统之间更灵活地分配内存，具体取决于在给定时间哪种内存需要更多的内存。

崩溃一致性

  • 问题：如何在出现断电（power loss）或系统崩溃（system crash）的情况下，更新持久数据结构
  • 核心思想：先写入被指对象，再写入指针对象
  • 位图、inode、数据块三者存在有没更新到磁盘上的情况：
    • 只将数据块写入磁盘：没有指向它的inode，也没有表示块已分配的位图，好像什么都没有发生。
    • 只有更新的inode写入磁盘：如果信任其中的指针，将从磁盘中读取垃圾数据。
    • 只有更新后的位图写入磁盘：文件系统不一致，导致空间泄露，有一些块永远无法被使用。
    • inode和位图写入磁盘：将从磁盘中读取垃圾数据。
    • inode和数据块写入磁盘：文件系统不一致
    • 位图和数据块写入磁盘：与只有位图写入的情况相同。
  • 文件系统检查程序fsck：用于查找这些不一致并修复它们，这种方法无法解决所有问题，假定在运行时没有其他文件系统活动正在进行，效率很低。
  • 预写日志：更新磁盘时，在覆写结构之前，首先写下一点小注记（在磁盘上的其他地方，在一个众所周知的位置），描述你将要做的事情。写下这个注记就是“预写”部分，我们把它写入一个结构，并组织成“日志”。因此，就有了预写日志。通过将注释写入磁盘，可以保证在更新（覆写）正在更新的结构期间发生崩溃时，能够返回并查看你所做的注记，然后重试。因此，你会在崩溃后准确知道要修复的内容（以及如何修复它），而不必扫描整个磁盘。因此，通过设计，日志功能在更新期间增加了一些工作量，从而大大减少了恢复期间所需的工作量。
    • 数据日志：事务以TxB开头（包括对文件系统即将进行的更新的相关信息，以及某种事务标识符），中间包含inode、位图、数据块的确切内容，以TxE结束。
    • 逻辑日志：在日志中放置逻辑表示而不是确切内容，可以节省日志空间。
    • 元数据日志：数据块直接写入磁盘中，而不用写入日志中，以避免一个更新要两次磁盘写入。
  • 更新文件系统的协议：
    1. 日志写入：将事务的内容（包括TxB、元数据和数据）写入日志，等待这些写入完成。
    2. 日志提交：将事务提交块（包括TxE）写入日志，等待写完成，事务被认为已提交（committed）
    3. 加检查点：将更新内容（元数据和数据）写入其最终的磁盘位置。
    4. 释放：一段时间后，通过更新日志超级块，在日志中标记该事务为空闲。
    • 一些文件系统不会一次一个地向磁盘提交每个更新（例如，Linux ext3）。与此不同，可以将所有更新缓冲到全局事务中。在上面的示例中，当创建两个文件时，文件系统只将内存中的inode位图、文件的inode、目录数据和目录inode标记为脏，并将它们添加到块列表中，形成当前的事务。当最后应该将这些块写入磁盘时（例如，在超时5s之后），会提交包含上述所有更新的单个全局事务。因此，通过缓冲更新，文件系统在许多情况下可以避免对磁盘的过多的写入流量。
  • 日志文件系统将日志视为循环数据结构，一遍又一遍地重复使用，防止日志文件不断增大或者变满。一旦事务被加检查点，文件系统应释放它在日志中占用的空间，允许重用日志空间。为此只需在日志超级块（journal superblock）中标记日志中最旧和最新的事务，所有其他空间都是空闲的。
  • 元数据日志无法恢复inode和位图写入成功但数据块写入失败的情况。因此，如ext3 NTFS等文件系统，先将数据块写入磁盘，再开始写日志。
    1. 数据写入：将数据写入最终位置，等待完成（等待是可选的）。
    2. 日志元数据写入：将开始块和元数据写入日志，等待写入完成。
    3. 日志提交：将事务提交块（包括TxE）写入日志，等待写完成，现在认为事务（包括数据）已提交（committed）。
    4. 加检查点元数据：将元数据更新的内容写入文件系统中的最终位置。
    5. 释放：稍后，在日志超级块中将事务标记为空闲。
  • 块复用：Linux ext3的做法是将新类型的记录添加到日志中，称为撤销（revoke）记录。删除目录将导致撤销记录被写入日志。在重放日志时，系统首先扫描这样的重新记录。任何此类被撤销的数据都不会被重放，从而避免了上述问题。

日志结构文件系统

  • 动机：
    • 内存大小不断增长。
    • 随机I/O性能与顺序I/O性能之间存在巨大的差距，且不断扩大。
    • 现有文件系统在许多常见工作负载上表现不佳。
    • 文件系统不支持RAID。
    • 理想的文件系统会专注于写入性能，并尝试利用磁盘的顺序带宽。此外，它在常见工作负载上表现良好，这种负载不仅写出数据，还经常更新磁盘上的元数据结构。最后，它可以在RAID和单个磁盘上运行良好。
  • 写入磁盘时，LFS首先将所有更新（包括元数据！）缓冲在内存段中。当段已满时，它会在一次长时间的顺序传输中写入磁盘，并传输到磁盘的未使用部分。LFS永远不会覆写现有数据，而是始终将段写入空闲位置。由于段很大，因此可以有效地使用磁盘，并且文件系统的性能接近其峰值。
    • 写入缓冲：一次大写入才能获得良好的写入性能。LFS会跟踪内存中的更新。收到足够数量的更新时，会立即将它们写入磁盘，从而确保有效使用磁盘。
    • inode映射：这样操作会使inode分散在整个磁盘上，由于不会覆盖，因此最新版本的inode会不断移动。因此使用inode map作为inode号和inode的中间层，它将inode号作为输入，并生成最新版本的inode的磁盘地址。LFS将inode映射的块放在它写入所有其他新信息的位置旁边。
  • 检查点区域：LFS在磁盘上只有一个固定且已知的位置，称为检查点区域（checkpoint region，CR）。检查点区域包含指向最新的inode映射片段的指针（即地址），因此可以通过首先读取CR来找到inode映射片段。检查点区域仅定期更新。
  • 垃圾收集：在后台，LFS必须定期查找文件数据，索引节点和其他结构的旧的死版本，并清理（clean）它们。因此，清理应该使磁盘上的块再次空闲，以便在后续写入中使用。这需要确定该数据块是否是活的。为此，LFS会为描述每个块的每个段添加一些额外信息。具体地说，对于每个数据块D，LFS包括其inode号（它属于哪个文件）及其偏移量（这是该文件的哪一块）。该信息记录在一个数据结构中，位于段头部，称为段摘要块（segment summary block）。

分布式系统

  • 目的：通过聚集一组机器，我们可以构建一个看起来很少失败的系统，尽管它的组件经常出现故障。

通信

  • 不可靠通信：不处理丢包，但考虑包的完整性。
  • 可靠通信：
    • 发送方如何知道接收方实际收到了消息？确认+超时+重试。当发送方发送消息时，发送方现在将计时器设置为在一段时间后关闭。如果在此时间内未收到确认，则发送方断定该消息已丢失。发送方然后就重试（retry）发送，再次发送相同的消息，希望这次它能送达。
    • 避免重复接收消息：顺序计数器。发送方和接收方就每一方将维护的计数器的起始值达成一致（例如1）。无论何时发送消息，计数器的当前值都与消息一起发送。此计数器值（N）作为消息的ID。发送消息后，发送方递增该值（到N + 1）。接收方使用其计数器值，作为发送方传入消息的ID的预期值。如果接收的消息（N）的ID与接收方的计数器匹配（也是N），它将确认该消息，将其传递给上层的应用程序。在这种情况下，接收方断定这是第一次收到此消息。接收方然后递增其计数器（到N + 1），并等待下一条消息。

远程过程调用RPC

  • RPC系统通常有两部分：存根生成器（stub generator，有时称为协议编译器，protocol compiler）和运行时库（run-time library）。
  • 存根生成器：输入是服务器希望导出到客户端的一组调用，在客户端生成客户端存根（client stub），其中包含接口中指定的每个函数。希望使用此RPC服务的客户端程序将链接此客户端存根，调用它以进行RPC。
    • 客户端调用：
      1. 创建消息缓冲区。
      2. 将所需信息打包到消息缓冲区中。
      3. 将消息发送到目标RPC服务器。
      4. 解包返回代码和其他参数。
      5. 从客户端存根返回到客户端代码。
    • 服务器响应：
      1. 解包从客户端收到的消息。
      2. 调用实际函数。
      3. 打包结果。
      4. 向客户端发送回复。
  • 运行时库：找到远程服务，提供路由机制，通常建立在不可靠通信上（优化性能）。