1. 操作系统概述

操作系统目标： 让系统更易于使用并提供高性能，核心技术虚拟化、保护隔离

通过虚拟化操作系统实现主要功能如下：

1. 让许多程序可以同时运行(从而共享CPU)，表现实体：进程线程
2. 可以同时访问自己的指令和数据（从而共享内存），表现实体：地址空间
3. 让许多程序访问设备（从而共享磁盘），表现实体：文件系统
4. 处理并发

系统调用与过程调用的区别：

1. 系统调用将控制权转给操作系统,同时提高硬件特权级别到内核模式，拥有访问硬件的全部权限
2. 过程调用用户程序以用户模式运行，硬件限制了应用程序的部分功能，不能直接操作硬件，需要通过操作系统调用才可以控制硬件

2.进程(CPU)

进程：操作系统提供的最基本的抽象，**其非正式定义：**进程就是运行中的程序

通过少量物理cpu,操作系统使用虚拟化CPU(时分共享)来提供几乎有无数个CPU的假象

2.1 时分共享CPU机制

通过让一个进程只运行一个时间片，然后切换到其它进程，操作系统提供了存在多个CPU的假象

潜在损失： 性能损失，因为共享CPU，每个进程的运行会慢一点

机制与策略：

1. 机制： 一些低级方法或者协议，实现了所需要的功能，如时分共享机制、空分共享机制

   时分共享机制： OS共享资源基本技术之一，将资源在时间上进行划分，允许资源由每个实体使用一小段时间，然后轮转，如此资源（CPU,网络链接等）可被多人共享

   空分共享机制： 与时分共享对应，将资源在空间上进行划分给使用者，如磁盘空间是一个空分共享，一但将块分配给文件，在用户删除文件之前，不可能将其分配给其它文件

2. 策略： 在机制之上，在操作系统内部做出某种决定的算法

   如给定一组程序要在CPU上运行，OS因该运行那个程序，OS中的调度策略会做出这样的决定，可能利用历史信息、工作负载、以及性能指标来做出决定

2.2 进程定义

进程：操作系统为正在运行的程序提供的抽象就是所谓的进程

进程的机器状态（组成部分）： 程序在运行时可以读取或更新的内容（必要内容）

1. 地址空间（进程可以访问的内存空间，因指令存在内存中，正在运行的程序读取和写入的数据也在内存中）
2. 寄存器（许多指令明确读取或更新寄存器，如程序计数器、栈指针、帧指针等告诉程序即将执行的指令，函数参数栈、局部变量与返回地址）
3. IO信息（程序经常访问持久存储设备，如包含当前打开的文件列表）

进程API： 操作系统必须包含的基本API，所有现代操作系统都以某种形式来提供这些API

1. 创建：创建新进程的方法
2. 销毁：销毁进程的方法，可以停止失控的进程
3. 等待：等待进程停止，
4. 其它控制：如暂停与恢复进程
5. 状态：可以获取有关进程的状态信息，如运行了多长时间，处于什么状态

2.3 进程细节

程序如何转换为进程，进程如何实际创建，详细如下

2.3.1 进程创建

进程创建步骤：

1. 将代码及静态数据加载到内存（加载到进程的地址空间中）`,使用惰性加载，仅加载程序执行时需要加载的代码和数据
2. 为程序的运行时栈分配内存,栈用于保存局部变量，函数参数和返回地址，也可能会为程序的堆分配内存，用于存储全局变量
3. 初始化与IO设置相关的工作，如输入输出的任务，unix系统默认每个进程会打开3个文件描述符，标准输入，输出和错误
4. 在程序入口处启动程序，跳转到main()例程，OS将cpu控制权转移到新创建的进程中，进程开始运行

2.3.2 进程状态

常见进程状态： 状态之间可以相互转换

1. 运行： 进程正在CPU上运行，意味着正在执行指令
2. 就绪： 进程已经准备好运行，但由于某种原因，操作系统选择不在此时运行
3. 阻塞： 进程执行了某种操作，直到发生其它事件时才会准备运行
4. 初始状态： 进程在创建时所处的状态
5. 最终态（僵死进程）： 已退出，但是还未清理的进程，此时允许其父进程检查它的返回码，用于判断是执行成功还是失败

2.3.3 进程数据结构

进程列表： 存储进程的相关信息，以便跟踪系统中正在运行的所有程序

进程停止时，将保存其寄存器的内容，通过恢复这些寄存器（将它们的值放回实际的物理寄存器中），操作系统可以重新恢复运行该进程，这称为上下文切换

2.4 进程API

unix系统经典进程创建API常用系统调用主要有以下几种，通过组合几种简洁的系统调用，实现更强大的功能

2.4.1 fork()系统调用

用于创建新进程

在程序中进行fork()调用后，创建的新进程与父进程一样，看起来有两个完全一样的程序运行，并且都从fork()系统调用中返回，新创建的进程称为子进程，原来的程序为父进程，子进程不会从入口函数main开始执行，而是直接从fork调用代码处返回，且返回状态码，0成功，其它失败，而主进程获得的返回是子进程的pid号，方便管理，子进程并不是完全拷贝父进程，它拥有自己的地址空间（私有内存），寄存器，程序计数器等

2.4.2 wait()系统调用

用于父进程需要等待子进程执行完毕才执行

父进程调用wait,延迟自己的执行，直到子进程执行完毕，当子进程执行结束时，wait才返回父进程继续执行

2.4.3 exec()系统调用

通过该系统调用，可以让子进程执行与父进程不同的程序

给定可执行程序的名称及需要的参数后，exec会从可执行程序中加载代码和静态数据，并用它复写自己的代码段（以及静态数据），堆，栈及其它的内存空间也会重新初始化，然后操作系统就执行该程序，将参数通过参数传递给该进程，它没有创建新进程，而是直接把当前运行的程序替换为了exec指定的程序，子进程执行结束后直接返回主进程，但是exec调用不返回任何状态

2.4.4 总结

这样设计的api,给了程序在fork调用之后，exec调用之前运行代码的机会，可以使在运行子进程新程序之前改变环境，从而实现程序的连接，unix系统中很多类似的实现，如shell就是其中典型代表

2.4.4.1 shell运行流程：

通过fork,与exec的分离，shell实现了下面的流程，同时使用该流程还可以实现很多功能，如重定向，管道连接等

1. 首先显示一个提示符，然后等待用户输入
2. 当用户输入一个命令和需要的参数后，shell会在文件系统中去找到这个程序，调用fork创建新进程
3. 新进程创建后执行exec调用运行用户输入的这个程序
4. 调用wait等待子进程运行结束
5. 从wait返回主进程，并再次输出一个提示符，等待用户输入

shell实现重定向： wc aa.c > new.txt

shell实现方式与它的执行流程类似，只是在完成fork创建子进程后，在执行exec之前先关闭了标准输出（文件描述符），打开了文件new.txt，这样即将运行的子程序将不会输出到屏幕，而会出到该文件

pipe()系统调用： 管道功能，与重定向类似，使用pipe调用将一个程序的输出连接到内核管道上（队列），另一程序输入也接入该管道上

因此前一个程序的输出可以作为后一个程序的输入，许多命令可以这样串联在一起共同完成某任务

此外还有许多其他系统调用： 如ps, top, kill(向系统发送信号，如终止，睡眠等)

3. 操作系统机制受限直接运行

如何高效可控的虚拟化CPU是操作系统的一大关键，使用时分共享实现了CPU的虚拟化，但是在实现后如何保证在不增加系统开销，同时保证对CPU的控制，有效的运行程序与控制对操作系统尤为重要，操作系统作为资源管理没有控制权，进程就可以无限制的接管机器和访问没有权限的信息，因此提出了受限直接运行机制。

3.1 受限直接运行

受限直接运行

1. 直接运行：只需要直接在cpu上运行即可（提高性能）
2. 受限：程序在运行时只能执行某些受限制的操作，不能完全获得系统的控制权（控制）

直接执行：

当os启动程序时，会在进程列表中为其创建一个进程条目，为其分配一些内存，将程序代码(从磁盘)加载到内存，找到入口点(main函数或类似)，跳转到该处，并开始运行用户代码，执行完毕后从main, return返回，释放进程内存，从进程列表中清除。直接执行优势是速度快，但是完全没有限制，尤其是遇到恶意程序，因此需要进行限制，使用受限制的直接执行

受限制的操作：

采用受保护的控制权转移，可以实现受限操作，硬件通过不同的执行模式来协助操作系统，在用户模式下，应用程序不能完全访问硬件资源，在内核模式下，操作系统可以访问机器的全部资源，此外还提供陷入内核和从陷阱返回到用户模式程序的特别说明，及一些指令，让操作系统告诉硬件陷阱表在内存中的位置

用户模式： 在该模式下进程只能执行有限操作，如不能发起io请求，这样会导致处理器引发异常，操作系统可能会终止进程

内核模式： 在该模式下（操作系统或内核就在该模式下运行），代码运行操作没有限制，可以直接执行所有受限指令，如发起io请求等

系统调用：

当在用户模式下如果程序希望执行某些特权操作，因此出现了系统调用，它允许内核小心的向用户开放某些功能，如访问文件系统，进程创建销毁，与其它进程通信，分配更多内存等

系统调用执行流程：

要执行系统调用，程序必须先执行陷阱指令，该指令会进入内核并将特权级别提升为内核模式，进入内核模式后系统就可以执行任何需要的特权操作，从而为调用进程执行所需要的工作，完成后，操作系统调用特殊的陷阱返回指令，该指令返回到发起调用的用户程序中，并将特权级别降低为用户模式

执行陷阱时，硬件必须确保存储足够的调用者寄存器，以便在操作系统发起陷阱返回指令时能够正确返回

在x86上，处理器会将程序计数器，标志和其它寄存器推送到每个进程的内核栈，从陷阱返回时弹出这些值，并恢复执行用户模式程序

3.2 陷阱表

通过陷阱表，硬件可以知道在操作系统执行陷阱、异常时运行那些相应的处理代码，内核在启动时第一件事就是设置陷阱表，例如发生硬盘中断，键盘中断异常时或者程序进行系统调用时因该运行那些代码，操作系统通过特殊指令(特权指令，内核模式)，通知硬件这些陷阱处理程序的位置，硬件将会记住这些位置，直到重新启动机器，并且当发生异常和系统调用时要做什么(跳转到那段代码)

总结受限直接执行： LED受限直接运行协议主要分为两个阶段

1. 系统引导时： 内核初始化陷阱表，并且CPU记住它的位置以供随后调用（内核通过特权指令来执行该操作）
2. 运行进程时： 在使用陷阱返回指令前，内核设置了一些内容（如在进程列表分配节点，分配内存），这会将CPU切换到用户模式并开始运行程序，当进程发起系统调用时，它会陷入操作系统，通过内核模式执行特权指令，然后在通过陷阱返回指令降低特权模式为用户模式并归还控制器给进程

进程完成后，从main函数入口，return返回,然后操作系统释放进程内存，清理进程列表

3.3 如何在进程之间切换

如果一个进程在cpu上运行，这意味着操作系统没有运行，因此如何在进程间切换，操作系统重获CPU控制权尤为关键

主要方式：

1. 协作方式：等待系统调用（等待）

通过程序运行系统调用和非法操作时陷入操作系统，从而重新获得CPU控制（因为会触发陷阱，执行陷阱会陷入操作系统），缺点，当程序无限循环并且不执行系统调用和违规操作，此时操作系统不能获得控制器，只能重新启动机器。

2. 非协作式：操作系统自己控制(时钟中断)

利用时钟中断，产生中断时，当前运行的进程停止，陷入操作系统中预先配置好的中断处理程序，此时操作系统重新获得CPU控制权

在启动时，操作系统就已经定义好了在发生时钟中断时需要执行那些代码(与陷阱表类似)，并且在启动时就开启时钟硬件（时钟的开启与关闭在特权模式下进行，使用特权指令），在中断时与系统调用一样，硬件也需要为正在运行的程序保存状态，以便陷阱返回时正确返回

3.4 保存和恢复上下文

操作系统重新获得控制权后，需要决定继续运行当前正在运行的进程还是切换到其它进程，这个决定由调度程序作出，根据多种调度策略

如果决定切换，操作系统就会执行一些底层代码，即所谓的上下文切换。

上下文切换： OS为当前正运行进程保存寄存器值(如通用寄存器，程序计数器内核栈指针),将即将执行的进程恢复寄存器值(内核栈)

通过上下文切换，操作系统可以确保从陷阱返回时，不是返回到之前的进程，而是继续执行另一个进程，实现进程的切换

在受限直接执行协议时钟中断时，存在两种类型的寄存器保存恢复

1. 第一种发生在中断时，运行进程的用户寄存器由硬件隐式保存，使用该进程的内核栈
2. 第二种是OS决定从A切换到B，内核栈被OS明确的保存，但保存在该进程的进程结构内存中

4. 进程调度

4.1 调度指标

调度指标，用于评判调度程序的好坏，常见调度指标如下

1. 周转时间（任务CPU运行时间）： T周转时间 = T完成时间 - T到达时间(任务完成时间-任务到达系统的时间)
2. 响应时间（任务到达后首次运行时间）： T响应时间 = T首次运行时间 - T到达时间(从任务到达系统到首次运行的时间)

4.2 常见调度

常见调度分为两种

1. CPU运行时间（周转时间）敏感型
2. 响应时间（首次运行时间）敏感型，（避免执行任务后，由于已存在执行任务，导致需要等待完成后才响应执行，避免交互体验差）

4.2.1 周转时间敏感型调度策略

4.2.1.1 先进先出FIFO（排队）

先进先出策略：也被称为先到先服务

特点： 简单、易于实现

缺点：容易出现护航效应(当最先到达的任务需要运行很长时间时，即使后面到达的任务只需要很少时间运行，也需要一直等待最先到达的任务完成)

4.2.1.2 最短任务优先SJF

谁最短就先运行谁，非抢占，先运行最短的任务，然后是次短的任务，如此循环

其代表一个总体调度原则，可以应用于所有系统，只要平均周转时间很重要都可以应用

优点： 如果所有任务同时到达，该调度算法最优，平均周转时间最少

缺点：如果任务随时到达，也会出现护航效应(当耗时任务到达运行后，其它耗时较短的任务到达后，任然需要等待长任务执行完毕才能执行)

4.2.1.3 最短完成时间优先STCF

抢占式调度，在最短任务优先上添加抢占，就可以实现最短完成时间优先STCF，可以避免护航效应

原理：每当新任务到达就会确认剩余任务和新任务谁的剩余时间最少，然后就调度剩余时间最少的任务

抢占式调度程序： 可以停止一个进程以运行另一个进程，可以实现上下文切换，临时停止一个进程，并恢复另一个进程

优点： 当任务随时到达时，该算法最优，平均周转时间最少，避免了护航效应

4.2.2 响应时间敏感型调度策略

4.2.2.1 轮转调度RR（时间切片）

轮转RR： 每个任务不用等到每次调度后运行完成才运行下一个，而是通过调度每个程序运行一段时间片，直到完成所有任务

优点： 提高了响应时间，交互体验好，响应时间为唯一指标时该调度最优

缺点：周转时间差，考虑周转时间RR是最差的调度策略，同时每个时间片的长度对RR策略影响巨大，需要设置合理的RR时间片长度

注意：RR时间片长度必须是时钟中断周期的倍数，时钟中断每10ms中断一次，则RR时间片可以是10ms、20ms或其它10ms的倍数

RR时间片： 时间片越短，响应时间越好，但是太短突然的上下文切换的成本将会影响整体性能，设置合理值尤为关键

摊销减少成本：当系统某些操作有固定成本时，可以使用摊销技术，通过减少成本的频度(执行较少次的操作)，降低系统的总成本

结合IO调度：通过使用重叠技术可以最大限度提高系统的利用率，如当进程IO阻塞时，调度其它进程运行，减少CPU浪费

在IO完成时，会产生中断，操作系统运行并将发出IO的进程从阻塞状态恢复到就绪状态，然后决定是否马上运行

4.3 多级反馈队列调度

多级反馈队列MLFQ： 利用最近的历史数据进行预测未来，解决OS无法判断即将运行任务的工作长度时如何调度问题

多级反馈队列原理：

MLFQ中拥有许多独立的队列，每个队列拥有不同的优先级，任何时刻，一个工作只处于一个队列，MLFQ总是优先执行较高优先级的工作(即在较高级队列中运行)，每个队列可以用于多个工作，其优先级都相同情况下，使用轮转调度

策略关键：如何设置优先级，MLFQ没有为每个工作指定不变的优先顺序，而是根据观察到的历史数据动态调整优先级

基本规则:

1. 如果A的优先级 > B的优先级，先运行A（不运行B）
2. 如果A的优先级 = B的优先级，轮转运行A和B
3. 工作进入系统时，放在最高优先级（最上层队列，近似SJF性能，不知道工作长短，开始就假设短工作，赋予最高优先级，短工作则很快执行完毕，否则将被慢慢移入低优先级，此时被认为是长工作）
4. 一但工作用完了其在某一层中的时间配额(无论中间主动放弃了多少次CPU)，就降低其优先级（移入低一级队列）
5. 经过一段时间S，就将系统中所有工作重新加入最高优先级队列，然后依次往复循环（解决长工作饿死问题，使长工作在一段时间后有机会再次运行）

优点： 通过观察工作的运行来给出对应的优先级（其它提升计算优先级方式，如数学公式，使用量衰减等），优化周转时间，同时降低响应时间

缺点： 如何配置使调度程序更好非常关键，如配置多少队列、每层队列时间片配置多大、多久提升一次优先级，没有标准参数，只能依据实际的工作负载情况进行这些参数的调整优化。

4.4 比例份额调度（公平份额调度）

目标：确保每个工作获得一定比例的CPU时间片，而不是优化周转时间和响应时间

技术：利用随机性进行按比例分配CPU，优点随机性可以避免部分边角问题，轻量不需保存状态，速度快(产生随机数快，做出决策就快)

基本原理： 彩票数代表了某个进程占有某个资源的份额，一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额

如：假设有进程A,B， A有75张彩票，B有25张彩票，因此我们希望A占用75%的cpu时间，而B占用25%，通过不断定时地抽取彩票，从概率上获得这种份额的比例（因为使用随机性，所以不是确定的，只能趋向于这个期望比例），运行时间越短与期望比例差别越大，越长越倾向于该比例

实现方式一：彩票调度，步长调度

4.4.1 彩票调度

策略调度抽取过程： 调度程序知道总共的彩票数，如上面的100张，调度程序抽取中奖彩票在0-99之间抽数，拥有这个数对应的彩票的进程中奖，开始运行，如上面的抽出为70，A拥有0-75，则开始运行A

彩票调度其它机制： 用于加速某个进程运行，改变运行比例

1. 货币：利用货币允许一组拥有彩票的用户以自己喜欢的某种货币将彩票分给自己的不同工作，之后操作系统再自动的将货币兑换为全局彩票，以此可以来改变程序的运行比例

   如A=100 用于A1、A2工作 B=100 只有一个工作

   A将自己的货币分给自己的A1-500 A2-500，总共1000张

   B将自己的货币100张分给自己，总共100张

   操作系统兑换为全局彩票，全局彩票共200张，A1-50, A2-50, B-100, 然后对全局彩票200张进行抽奖，决定谁运行

2. 彩票转入： 通过转入，一个进程可以临时将自己的彩票交给另一个进程，从而加速另一个进程运行，运行结束后归还转让的彩票

3. 彩票通胀： 适用于进程相互信任的环境，利用通胀进程可以临时提升或者降低自己的彩票数来改变进程的运行比例（竞争环境不适用，一个贪婪的进程可能给自己很多彩票）

调度实现： 彩票调度实现简单，只需一个不错的随机数生成器选择中奖彩票，一个记录系统所有进程的数据结构(一个列表),以及所有的彩票总数：总结就是，随机选取中奖，队列存储，遍历链表谁中奖运行谁(可以进行降序排序后，在遍历提高效率)

优点：不需要全局状态，加入新进程时只需要用新进程的彩票数更新全局的彩票数即可，能够合理处理新加入进程，其次实现简单

缺点： 彩票分配麻烦，调度策略依赖于彩票分配，但随机所以不能确定，尤其在工作时间很短时，容易分配不均，只能长时间后大致正确

4.4.2 步长调度

用于解决彩票调度的随机不确定性而提出的一个确定的公平分配算法，可以在每个调度周期做到完全正确

原理： 系统中每个工作都有自己的步长，这个值与票数值成反比，

1. 每次进程运行后，让进程的计数器(行程值)增加它的步长，并记录它的总长度，
2. 调度时选择目前拥有最小行程值的进程运行
3. 运行后将该进程的行程值增加一个步长，如此往复

总结： 由于比例份额确定比较麻烦，因此使用较少，常用于比例份额确定场景，如虚拟机比例分配共享内存4/1A, 4/3给B

4.5 多处理器调度

多处理器与单处理器的主要区别、对硬件缓存的使用、多处理器之间共享数据的方式，这些区别为调度程序带来新的挑战

在CPU系统中存在多级的硬件缓存，这些缓存提升了CPU的速度，但是缓存是基于局部的

缓存的2种局部性

1. 时间局部性： 当一个数据被访问后，它很有可能在不久的将来再次被访问
2. 空间局部性： 当访问地址为A的数据时，很有可能会接着访问A周围的数据

在多CPU中会存在缓存一致性问题,硬件对这个问题提供了解决方案

1. 监控内存访问： 硬件可以保证获得正确的数据，并保证共享内存的唯一性
2. 总线窥探：在基于总线的系统中，每个缓存都通过监听链接所有缓存和内存的总线，来发现内存访问，如果CPU发现缓存在本地的数据做出了更新操作，会将该本地缓存数据作废从缓存中移除或者更新它，回写缓存

跨CPU访问共享数据时需要使用互斥原语才能保证正确性(加锁)

缓存亲和度：

一个进程在某个CPU上运行，会在该CPU缓存中维持很多状态，下次在该CPU运行时可以使用缓存提升速度，如果下次不是在同CPU运行，因为没有缓存数据，会重新从内存加载数据，速度会有所降低，所以在多CPU调度时需要考虑到这种缓存亲和度特性，尽可能将进程保持在同CPU上运行

4.5.1 单队列调度（SQMS）

单队列调度(SQMS)：将所有需要调度的工作放入一个单独的队列中，选择合适的任务运行，如2CPU，就选2个合适任务运行

优点： 实现简单，不需要太多修改就可以用于多CPU调度

缺点： 可扩展性差、需要加锁保证原子性，CPU越多锁竞争越大影响性能，缓存亲和性差，每次运行都在不同CPU

4.5.2 多队列调度（MQMS）

多队列调度(MQMS)：每个CPU一个队列，每个队列可以使用不同的调度规则，当工作进入系统后，系统依照一定规则将任务随机或者选择较空的队列插入进行调度，这样每个CPU单独调度，避免了单队列的方式由于数据共享及同步带来的问题

优点： 扩展性强，所有工作运行在相同CPU，缓存亲和性好

缺点： 存在负载不均衡问题

解决办法,通过迁移可以实现负载均衡，即将一个CPU的任务迁移到另一个CPU运行

迁移方法：窃取(work stealing)，工作任务较少的队列不定期检查其它队列工作是否比自己多，多则从其它队列窃取一个或者多个工作到自己队列，实现负载均衡。但是这个不定期间隔参数特别重要，太过频繁会导致开销过高，扩展性不好，间隔太久又负载不均，因此需要根据实际情况进行调优

Linux社区常见的多处理器调度程序

1. CFS多队列： 确定的比例调度算法，类似于步长调度
2. BFS单队列： 也基于比例确定算法，但使用了更复杂的虚拟截止时间算法EEVEF
3. **O(1)：**基 于优先级算法，类似MLFQ多级反馈队列

5. 地址空间(内存)

为了方便的使用物理内存，操作系统对内存进行了抽象，这个抽象叫做地址空间，是运行程序所看到的系统中的内存

通过抽象，OS为每个运行在物理内存上的进程(所有进程共享内存)抽象出一个私有且巨大的地址空间，让程序认为被加载到特定的私有地址(例如0)的内存中，且该地址空间巨大可任意使用，程序尝试加载地址0的数据时，操作系统会在硬件的支持下将其正确映射到真正的物理内存地址。

5.1 进程地址空间

一个进程的地址空间包含了该进程运行的所有内存状态：比如，程序的代码、栈保存的当前函数调用信息、局部变量、传递参数、函数返回值，堆保存的用户动态申请管理的内存，全局变量等

程序运行时，地址空间有两个区域可以增长，分别是堆(地址空间顶部)，栈(地址空间底部)(代码在地址空间开头)，在地址空间两端，增长时相互反向增长,这个是操作系统抽象给程序所见的，真正的程序可以是加载在任意的物理内存地址中

隔离是建立可靠系统的关键原则，如果两个实体相互隔离，一个实体的失败就不会影响另一个实体，操作系统通过进程隔离来实现进程间不会相互影响，同时使用隔离也保证运行程序不会影响操作系统本身的底层操作

5.2 虚拟内存(地址空间)的目标

1. 透明性： 对于程序透明，感知不到内存被虚拟化，认为拥有自己的私有物理内存地址，操作系统在幕后完成这个工作，让不同的程序复用内存实现这个假象
2. 效率： 虚拟化操作尽可能高效，如在时间、空间上高效，同时较短的耗时和较少的内存空间占用
3. 保护： 操作系统应确保各个进程相互隔离保护，不受其它进程影响，包括操作系统自己，每个进程都在自己的环境独立运行，不能访问修改除自己内存地址空间以外的任何其它内存的任何内容

在程序中所看到的打印的任何地址都是虚拟地址，不是真正的物理内存地址，只有操作系统和硬件才知道真正的地址

5.3 内存操作API

在unix/c程序中主要会分配栈、堆两种内存类型

1. 栈： 申请释放由编译器隐式管理为自动内存，不需用户管理，常用函数参数，局部变量，函数调用栈，入口，返回等，用完会立即释放
2. 堆： 申请释放都由用户自己管理，常用于全局变量，需要长期使用的数据，用完需要手动释放，避免内存泄露

C中内存申请释放api

1. malloc()调用： 调用它手动申请堆内存
2. free()调用： 调用它手动释放申请的内存
3. calloc()调用： 分配内存并在返回时将其置零
4. realloc()调用： 创建一个新的更大的内存区域，将旧区域复制到其中，并返回新区域的指针

这些api都是库调用，分配的是虚拟地址内存空间，但它们是建立在系统调用之上，系统调用会进入操作系统将内存分配和释放回系统。

系统调用

1. brk系统调用：改变程序分段位置(堆结束的位置)，它需要一个新分段地址来判断是否大于或小于当前分段，来增加或减少堆的大小

2. sbrk系统调用：传入一个增量，目的与brk一样

3. mmap系统调用：分配一个匿名内存区域，这个区域不与任何特定文件相关联，而与交换空间相关联(用于存放进程运行时产生的数据)

常见错误：

1. 忘记分配内存： 调用时会报段错误，空指针异常,常见于定义了变量没分配内存就使用
2. 没有分配足够的内存： 使用时会出现缓冲区溢出，导致数据被截断不正确
3. **忘记初始化分配的内存：**分 配内存后没有初始化值，导致读取到的是内存地址中原有的未知的数据或者直接报错未初始化
4. 忘记释放内存： 申请后没有释放，导致内存泄露(长时间后导致内存不足)程序崩溃
5. 在用完之前释放内存:这种错误被称为悬挂指针、反复释放内存、错误的调用free()

系统中的两级内存管理：

在编写的程序中运行时申请了内存，程序运行并即将完成，在退出前不释放也不会出现内存泄露，因为系统中存在两级内存管理

1. 第一级操作系统执行： 操作系统在进程运行时分配内存给进程，进程结束时回收内存
2. 第二级每个进程中：如malloc/free调用，在堆内存管理没调用释放，在进程终止时操作系统都会收回进程的所有内存(无论地址空间的状态如何)

5.4 地址转换（内存虚拟化）

通过硬件每次对内存访问进行处理(指令获取、数据读取或写入)，将指令中的虚拟地址转换为数据实际存储的物理地址，同时利用操作系统在关键位置介入，设置好硬件，以便正确的完成地址转换(类似虚拟化CPU，使用受限直接访问的方式，利用陷阱表进行各种情况处理),可以完成虚拟地址对内存的虚拟化，实现给进程营造每个进程都拥有自己私有的内存来存放自己代码和数据的假象。实现时操作系统需要管理内存，记录被占用和空闲的内存位置，谨慎的介入保持对内存使用的控制

介入：通过提供介入，程序可以在不改变客户端接口(对客户端透明)方式下，增加或修改功能，如硬件通过介入每次访问实现地址转换，

动态基于硬件的重定位：基址寄存器值 + 虚拟地址 = 物理内存地址,因为重定位在运行时发生所以称为动态

每个CPU需要有基址、界限2个寄存器，cpu负责地址转换的部分也称内存管理单元MMU

基址：负责保存程序的物理起始位置，

界限：提供访问保护，确保地址在进程地址空间范围内,保存进程地址空间的大小(硬件转换前进行判断)，或者记录地址空间结束的物理地址(硬件转换为物理地址后进行判断是否越界)，越界触发异常终止进程,确保进程不会访问除自己外的其它内存地址

1. 程序运行时操作系统从物理地址加载程序，并将它的起始地址保存在基址寄存器中
2. 程序中使用的内存引用都是虚拟地址，引用时硬件将基址寄存器中的地址加上虚拟地址得到程实际内存地址在发给内存
3. 界限寄存器提供保护，确保进程产生的所有地址都在进程的地址解析中

**空闲列表：**操作系统必须记录那些空闲内存没有使用，以便为进程分配内存，空闲列表就是一种最简单的用于记录当前没被使用的物理内存的范围的数据结构，它就是一个列表

动态重定位的硬件支持

硬件要求	解释
特权模式	需要防止用户模式的进程执行特权操作
基址/界限寄存器	每个CPU需要一对寄存器来支持地址转换和界限检查
能转换虚拟地址并检查它是否越界	电路来完成转换和检查界限，实现简单
修改基址/界限寄存器的特权指令	在让用户程序运行前，操作系统必须能够设置这些值
注册异常处理程序的特权指令	操作系统必须能告诉硬件，如果发生异常，因该执行那些代码
能够触发异常	如果进程试图使用特权指令或越界内存地址

动态重定位操作系统职责

操作系统的要求	解释
内存管理	需要为新进程分配内存、从终止的进程回收内存、一般通过空闲列表来管理内存
基址/界限管理	必须在上下文切换时正确设置基址/界限寄存器
异常处理	当异常发生时执行的代码，可能的动作是终止犯错的进程

总结：动态重定位优点：实现简单，功能完善 缺点：效率低下，要求将地址空间放在固定大小的槽中，容易造成浪费出现内部碎片

内部碎片： 已经分配的内存单元内部有未使用的空间(碎片)，造成了浪费

5.5 地址转换优化（分段）

使用基址与界限寄存器的简单地址转换技术，把整个物理内存放入地址空间，存在浪费现象(内部碎片)，这样的内存地址分配太粗糙，粒度不够细分，效率比较低下，因此出现了使用分配粒度更细的分段内存分配方式

分段： 通过分段可以减少浪费，提供大量地址空间(也称稀疏地址空间)，常见分段、代码、栈、堆，将不同的段放入不同的内存地址，避免了虚拟地址空间未使用的部分占用物理内存

分段实现方式：在MMU中引入多个基址、界限寄存器，给每个逻辑段一对，不同的段使用各自对应的基址界限寄存器，实现区分避免全部载入分配，如栈，就只使用栈的段与自己的基址界限进行分配，而不分堆、代码段，避免了浪费，这个寄存器被称为段寄存器

操作系统如何引用段：

1. 显示分配：在虚拟地址开头使用2位进行段标识告诉硬件当前使用那一个段，然后硬件选择相应段的基址界限寄存器，并加上虚拟地址标识位后的地址-映射到物理内存空间，实现转换
2. 隐式分配： 硬件通过地址产生的方式来确认在那个段分配，如由程序计数器生成(地址在代码段中)，如果基于栈或基址指针(在栈段)，其它在堆段

段错误： 支持分段的机器上发生了错误的内存访问

栈的特殊处理： 由于栈反向增长，硬件需要知道段的增长方向，在段寄存器中添加增长方向标识位告知硬件，如0,1分别代表不同方向，然后为了得到正确的反向偏移量，需要使用偏移量减去最大段的地址，然后与基址寄存器相加，就可以得到正确的地址，进行界限检查时，确保反向偏移量的绝对值小于段的大小即可。

例如：地址`11 1100 0000 0000`，前2位11标识属于那个段，后面1100表示10进制3，偏移量为3kb
1. 要访问虚拟地址`15k`
2. 映射到物理地址`27k`,
3. 虚拟地址的偏移量是`3k`
4. 段的最大长度`4k`
5. 基址寄存器为`28k`

反向偏移量=3-4 = -1k, 基址寄存器为28k, 28-1 = 27k得到正确的物理空间地址(栈反向增长，增加地址越来越小，所以基址寄存器进行相减，不是相加)

共享：通过地址空间共享某些段，如代码段，可以实现节省内存

共享实现方式：在段寄存器上增加保护位：标识程序是否能够读写、或者执行该段，标识为只读时可以被多个进程共享，不会破坏隔离

有了保护位，硬件除了检查虚拟地址是否越界外还需要检查特定访问是否允许，触发异常让操作系统处理错误进程

分段带来的问题：

1. 操作系统上下文切换时: 每个进程都有自己独立的虚拟地址空间，操作系统需要保证进程运行前这些寄存器的被正确的赋值
2. 管理物理内存的空闲空间: 处理外部碎片，常见方式，紧凑内存，重新安排原有段、使用空闲列表管理算法(都只能降低，不能避免)

**总结：**分段粒度还是不够细化，还存在优化空间，在一个大段中进行更细分的划分(分页)

5.6 空闲空间管理

内存空间管理： 减少外部碎片与内部碎片

底层基本机制：

1. 分割：按需要的大小，将空闲内存进行切割，返回给程序
2. 合并：空闲内存切割后，空间变得碎片化(出现外部碎片)，需要合并（归还时检查归还块与相邻的快是否空闲，空闲与相邻块合并）
3. 追踪已分配空间的大小：内存分配时，在返回的内存块中添加额外的头块信息，帮助确认分配的内存大小，提高释放时释放速度，头块可以保存内存块大小等，因此申请大小N时，是分配N+头块，释放时同理
4. 嵌入空闲列表:记录内存使用情况
5. 让堆增长：内存不足时，向物理内存申请，返回新的堆末尾地址，将新分配的映射到进程的地址空间

分配策略：

1. 最优匹配： 遍历空闲列表，返回申请块一样大或更大的块进行分配，需要遍历空闲列表找到即可返回（也称最小匹配），减少浪费，遍历耗时（会存在很多外部碎片）
2. 最差匹配： 与最优相反，它找最大的空闲块进行分割返回给程序，然后将剩余的块加入空闲列表，（降低外部碎片，保留大块空闲内存，但是需要遍历所有，效率低下）
3. 首次匹配： 找到第一个足够大的块就立即返回，不需要遍历，速度快，(但头部容易出现很多碎片，可以基于地址排序，保持空闲块按内存地址有序，方便合并减少碎片，利用相邻空闲合并)
4. 下次匹配： 不同于首次每次都从列表开始查找，下次匹配多维护一个指针，指向上次查询结束的位置，将查找扩散到整个空闲列表，性能与首次接近，也避免了查找
5. 分离空闲列表： 某应用经常请求某大小的内存块，就用一个独立的列表，只管理这样大小的内存，其它大小请求交给通用分配程序，典型代表:厚块分配程序
6. 伙伴系统： 在合并时下功夫，让合并更简单，典型代表：二分伙伴分配程序，空闲空间看着是2^n次方大小（必须是2的倍数），当分配内存时，空闲空间被递归地一分为2，直到刚好可以满足用户要求，就返回内存块，（因为必须为2的倍数大小，存在内部碎片），释放内存时，分配程序会检查伙伴释放空闲，空闲就合并，然后检查合并的后块的伙伴是否空闲，空闲合并，如此递归执行，减少碎片：列如：归还8kb，检查伙伴8是否空闲，空闲合并=16，检查伙伴16是否空闲，空闲合并=32，如此递归

总结： 这些都是最本的分配方法，扩展性差，查询空闲列表慢，可以采用更复杂的数据结构提升查找性能，如树结构

5.7 内存分页

分页：将空间分割成固定长度的分片，每个分片称为一页，对应物理内存看成是定长槽块的队列，叫页帧，每个页帧包含一个虚拟内存页

分页优势：通过分页管理虚拟内存，操作系统更高效、灵活的提供地址空间抽象，不会导致外部碎片，支持稀疏地址空间(包含大量未未使用的地址空间)不用假定堆栈的增长方向以及如何使用，空闲空间管理也更简单（如操作系统只需要保存一个记录空闲页的空闲列表，需要分配几个就弹出几个空闲页）

页表： 用于记录地址空间的每个虚拟页存放在物理内存中的位置(虚拟页到物理位置的地址转换)，操作系统通常为每个进程保存一个页表

分页虚拟地址到物理地址转换流程：

1. 将进程运行时的虚拟地址分为、虚拟页面号、页内偏移量两个部分，然后进行读取，举例如下

1. 假设进程虚拟地址空间=64字节：那么虚拟地址总共需要6位(2^6 = 64), //虚地址可表示为 = va5|va4|va3|va2|va1|va0
    
2. va5为最高位,va0为最低位，每页大小16字节，总共64字节，//需要能选择4个页对应4个物理页帧(虚拟页在物理内存的位置)

//虚拟地址可划分为如下两部分
3. 2位表示虚拟地址页号VPN，其余的4位为偏移量，表示该页的那个字节  //因为2比特就可以表示4个数，00|01|10|11

2. 将划分的虚拟地址进行转换，举例如下

1. 虚地址解析
假设虚拟地址=21，转为二进制=010101,  其中：01(VPN页号)|0101(偏移量)
//因此虚地址21，在虚拟页01（或第一页1）的第5个(0101)字节处

2.虚地址转换，查询页表
在页表内查询虚拟页所在的物理位置，假设该虚拟页存放在物理帧号（PFN）是7二进制111，然后使用PFN替换掉VPN就实现了虚拟地址到物理地址的转换，//转换时偏移量不变（因为偏移量只是告诉页面中那个字节是需要的）
此时就是:01(VPN页号)|0101(偏移量)  ==转换== 111(PFN号)|0101(偏移量)=010101虚拟地址----> 1110101物理地址
然后将请求发送给物理内存，整个流程结束

页表一般保存在内存中，有时还可以交换出保存在磁盘上

5.7.1 页表数据结构

页表数据结构有多种，最简单的形式为线性页表，使用数组表示，操作系统通过虚拟页号VPN检索这个数组，并在该索引处查找页表项PTE，以便找到期望的物理帧号PFN

页表项PTE： 一般包含许多位，常见位数如下

1. 有效位：标识特定地址转换是否有效，所有未使用空间会标识为无效位，进程访问会陷入异常，无效位无需分配物理帧，节省内存
2. 保护位：标识页是否可以读取、写入、执行，以这些位不允许的方式访问会陷入异常
3. 存在位：标识该页是在内存，还是磁盘(是否已被换出交换到磁盘，从而支持大于物理内存的空间)
4. 脏位：标识页面被代入内存后是否被修改
5. 参考位：也称为访问位，用于确认页是否被访问，可以确定哪些页收欢迎，可以保留在内存中

普通页表转换，由于页表较大，分页寻找较慢（页表存放内存，每次访问会多一次内存访问），占用太多内存，因此出现了TLB转换

5.8 分页快速地址转换TLB

TLB硬件缓存： 地址转换缓存，用于加快分页地址查询，解决分页内存读取效率问题

TLB基本算法

1. 从虚拟地址中提取页号
2. 检查TLB是否有该VPN转换映射，如果有，且保护位检查可以访问，TLB命中，从TLB中获取页帧号FPN与虚拟地址中的偏移量组成物理地址访问内存
3. 如果TLB未命中，硬件访问页表来寻找转换映射，并用该映射更新TLB（因为访问页表需要额外内存引用开销较大）
4. 更新TLB后系统重新尝试该指令，此时TBL命中

TLB缓存也与其它缓存一样，依赖于时间、空间局部性（时间访问后的数据或指令在次访问的几率较大，空间相邻地址的数据被访问记录较大），且页的大小越大效果更好，缓存的数据更多（每页只有第一次访问不会命中，但太大也会降低速度）

TLB未命中处理： 常见两种处理方法，硬件、软件

1. 硬件： 使用复杂指令集，硬件直接完全实现，硬件知道页表在物理内存的确切位置(页表基址寄存器)，未命中时，硬件遍历页表，找到正确的页表项并进行转换，用它更新TLB，并重试该指令，如x86架构采用固定的多级页表结构
2. 软件： TLB未命中硬件抛出异常，暂停当前指令流，提升特权至内核模式，跳转到陷阱处理程序(操作系统陷阱处理模式)，该方式灵活简单，不需改变硬件

TLB内容： 一般包含 VPN|FPN|其他位

1. 有效位： 标识是否是有效地址映射
2. 保护位： 标识该页是否有访问权限，如，代码标识为可读可执行，堆被标识为可读可写
3. 其他位： 如地址空间标识符、脏位等

TLB有效位与页表有效位区别：

1. 页表有效位：该位无效表示该页没有被进程申请使用，正常运行进程不应该访问，访问触发异常
2. TLB有效位：该位只表示TLB项是不是有效地址映射

TLB上下文切换：TLB中包含的虚拟到物理地址只对当前进程有效，切换进程时需要避免即将运行的进程误读之前进程的地址映射

1. 清空： 发生上下文切换时，将全部有效位置为0，使其失效，实现清空（软件TLB通过特权指令显示清空，硬件TLB修改页表基址寄存器值）,效率较低，频繁切换进程消耗较大
2. 地址空间标识符： 通过在TLB中添加ASID进程标识符，通过ASID区分不同进程的地址映射，实现缓存不同进程地址空间映射(TLB共享)，还可以实现不同进程共享同一地址数据

5.8.1 TLB缓存替换策略

常见策略：

1. LRU:最近最少使用，利用了内存引用的局部性（极端情况访问n+1页，但TLB只能存放n页，则每次都不命中，此时LRU效率低下）
2. 随机：可以避免极端情况

5.9 分页较小的表

**分页较小的表：**解决分页页表太大，消耗内存多问题，利用分段的特性，每次按不同的段进行分页分配，而不是全部分给进程

1. 方法一使用更大的页： 可以减少页表数量，但是会造成内部碎片，出现页浪费，分给进程的页不一定会完全被使用
2. 方法二结合分页分段： 利用分段的特性，每次按不同的逻辑段进行页表分配，而不是将整个页表全部分给进程地址空间，会出现外部碎片，寻找更为复杂
3. 方法三多级页表： 将页表分为页大小的单元，如果整页的页表项无效，则不分配该页的页表(使用了新数据结构：页目录)，页目录记录分页后的页表：每页页表项，是否有效，以及它在内存中的位置，该方式分配方法紧凑，并支持稀疏地址空间，缺点是如果TLB未命中需要引用两次(页目录、页表)，实现更加复杂，页目录至少包含有效位(表示该项指向的分页页表至少有一页页表是有效的)和页帧(每项页表存放的物理位置)，此外如果页目录很大，也可进行划分，通过一级页目录寻找二级页目录寻找页表在到物理地址，依次递推

反向页表： 使用一个页表进行记录，其中的每一项代表每一个物理页，该页表项标识那个进程正在使用此页，以及进程的那个虚拟映射到此物理页，要找正确的页扫描这个页表项即可（可以使用hash,进行快速查找）

将页表交换到磁盘： 如果页表还是过大内存难以放下，可以使用虚拟内存交换到磁盘

5.10 超越物理内存机制（交换空间）

当内存不够时使用磁盘虚拟内存进行交换，使部分页存放在磁盘，这样可以保证运行需要空间比内存大的程序和保证地址空间足够大

交换空间： 硬盘上开辟空间，用于物理页的移入移出，并在需要时交换回内存，操作系统要记住给定页的硬盘地址，交换空间的大小决定了系统在某一时刻使用的最大内存页数，让系统假装内存比实际内存更大

存在位：页表项用于标识该页是否在内存中，用于TLB查找页表时判断该页是否在内存中，存在该位=1，不存在=0，访问不在物理内存中的页被称为页错误，此时硬件会抛出异常，陷入陷阱，操作系统运行页错误处理程序

页错误处理： 由操作系统的页错误处理程序处理(硬件、软件TLB页错误都交由操作系统处理)

1. 使用页表中PTE页表项的某些位存储页在硬盘的地址（一般这些位是用来存储PFN页帧的）
2. 当操作系统收到页错误时，在PTE中查找地址，并将请求发送到硬盘，将页读取到内存
3. 硬盘IO完成后，操作系统更新页表，将此页存在位标识为1(存在)，更新页表项PTE中PFN页帧字段记录获取页的内存地址
4. 将此页更新到TLB中（可省略，可以在重新访问TLB时，加载）
5. 重试指令，在TLB中找到命中

IO运行时，进程会阻塞，因此页错误正常处理时，操作系统会运行其它可执行的进程，交叠执行提高了系统利用率（因IO操作耗时）

5.10.1 内存换出

当内存快满时，需要将部分页交换到磁盘，选择那些页交换的过程被称为页交换策略

当TLB未命中时有三种处理情况

1. 该页存在并且有效，TLB未命中处理程序从PTE中获取FPN地址进行内存访问并更新，然后进行重试(这次TLB会命中)，继续运行
2. 该页不存在，需要运行页处理程序，读取磁盘交换页然后更新
3. 该页无效，非法访问，硬件抛出异常，操作系统陷入陷阱处理程序，可能终止进程

页不存在时，页错误处理流程

1. 操作系统必须为将要换入的页找到一个物理帧，如果内存没有足够物理帧，等待交换算法运行（交换算法先检测是否有空闲页，如果没有则进行释放踢出）从内存中踢出一些页，释放帧以供使用
2. 获得物理帧后处理程序等待IO请求从交换空间读取页
3. 读取完后，操作系统更新并重试指令，重试将导致TLB未命中，然后在一次重试，TLB命中，此时硬件将能够访问所需要的值

交换何时发生： 为了保证有少量空闲内存，操作系统会设置高水位线HW，低水位线LW帮助决定何时从内存中清除页

当系统发现少于低水位线个页可用时，后台负责释放内存的线程（页守护进程）开始运行，直到有高水位线个页可用时该线程进入休眠，唤醒原来的线程，把需要的页交换入内存，继续运行

多个交换同时执行时，可以将要置换的页进行聚集或分组，同时写入到交换区间，从而提高硬盘写入效率，减少开销提高性能

5.10.2 内存换出策略

程序平均内存访问时间*AMAT=（Phit缓存找到数据的概率 * Tm内存访问成本） + (Pmiss缓存找不到数据的概率 Td磁盘访问成本)

Phit + Pmiss = 1

**最优替换策略：**也称为MIN，能够达到总体未命中数量最小,常用来比较内存换出策略的好坏(因为该策略很难实现，是理论上的最优)

基本思路是:踢出在最远将来才会访问的页（缓存中所有的页都比这个页重要），但要确定这个页比较难，未来的访问无法确定

缓存未命中类型

1. 强制未命中：由于缓存最开始为空，因此第一次应用未命中，称为冷启动未命中或者强制未命中
2. 容量未命中：由于缓存空间容量不足不得不踢出一个项目以将新项目引入缓存，称为容量未命中
3. 冲突未命中：出现在硬件，因为硬件缓存中对项的放置有限制，不会出现在操作系统页面缓存中

常用内存换出策略

1. 简单策略：使用简单的机制进行替换

​ 1. 简单策略FIFO： 先进先出，页在进入系统时放入队列，发生替换时先入页被踢出

​ 优点：实现简单 缺点：无法确定页的重要性，机械的先入先出

​ 2. 随机： 在内存满的时候随机选择一个页进行替换，优点：实现简单 缺点：无法确定页的重要性，选页不够智能

2. 利用历史数据： 利用历史数据的访问频率，频率越高则越不会替换以及近期性，越近被访问过的页再次访问的可能性更大，(利用局部性原则，时间空间)

       1. 最近最少访问LRU：最近最少访问进行选择踢出替换的页`（效果较好，一般使用该策略,利用访问时间）`
       2. 最少访问LFU：最不经常使用的页进行选择踢出替换`(利用访问频率)`
   

​ 近似LRU的实现：由于完美的LRU实现比较困难，一般实现的是近似LRU，因为去精确的计算每一页消耗太大，通过在硬件增加一个使用位(或称为引用位)，每当页被使用时，硬件将使用位置为1，但不会清除该位(不会置0，清除由操作系统决定)，操作系统利用使用位进行筛选页的常用算法时钟算法(早期成熟算法)

​ 时钟算法： 系统中所有页都放在一个循环列表中，时钟指针开始时指向某个特定的页，当进行页替换时操作系统检测当前时钟指针指向的页P的使用位是否为1，为1表明最近使用过，不替换将使用位置为0，然后指针加1继续查询下一个，直到查找到使用位为0的，表明最近未使用可以进行踢出替换，最坏的情况下所有页都被使用了，将所有页的使用位置为0，全部遍历一遍

​ 此外，任何周期性的清除使用位，然后区分使用位是1还是0进行替换的算法都可以实现。

​ 脏位： 用于标识内存中的页是否被修改过，如果修改过，则变为脏页，踢出时必须将它写回磁盘(写回磁盘代价昂贵)，没有被修改就是干净的，踢出没有成本，物理帧可以简单的重用于其它目的不需要额外的io,因此一般踢出干净页

​ 通过在硬件添加一个修改位(脏位)，每次写入页时都设置此位，可以将其合并到页面替换算法，每次扫描时扫描干净未使用页面提搞效率，未找到在查找脏页未使用页面

其它虚拟内存策略：

1. 何时将页面载入内存：一般按需载入即可，页被访问时载入内存，或者当可以确定一个页面即将被使用时，可以提前载入称预取

   如P被访问，P+1可能也会，因此提前载入P+1

2. 如何将页面写入磁盘：一般使用在内存中收集多个待完成写入，并以一种高效的方式写入磁盘，称为聚集写入或分组写入，提高效率

抖动：当内存被超额请求时，操作系统将不断低进行换页，这种情况被称为抖动，一般通过准入控制限制运行的进程，如linux系统中，内存超出时，使用守护进程选择一个内存密集型进程并杀死它进行释放内存

按需置零技术： 当页添加到地址空间时，操作系统在页表中加入一个标记页不可访问的页，如果进程读取或写入页，则会触发陷阱，操作系统处理陷阱时通过在页表加入的标记字段发现这是一个按需置零页，操作系统完成寻找物理页的操作并将其置零，并映射到进程的地址空间，如果该进程从不访问该页，这些物理寻找分配都可以避免(先分配虚拟地址，不与物理内存映射，访问时才映射)

写时复制技术： 操作系统将一个页面复制到另外一个页面，不是实际复制，而是通过将其映射到目标空间，并在两个地址空间中将其标识为只读，如果进程都只读取，则可以实现快速复制，当进程尝试写入页面时，触发异常陷入操作系统，操作系统发现该页是一个映射页，则分配一个新页填充数据并将其映射到触发异常的进程地址空间，该进程拥有了自己的私有副本然后继续使用。提供了性能。

6. 并发(线程)

通过为单个进程提供抽象：线程，实现程序的并发，每个线程类似于独立的进程，线程切换时也需要进行上下文的切换，进程上下文切换将进程的状态保存在进程控制块PCB，线程切换保存在线程控制块TCB。

线程与进程的区别：

1. 同一进程的所有线程共享进程的地址空间，上下文切换时地址空间不变(不需要切换当前使用的页表)
2. 多线程的进程中，每个线程拥有自己独立的栈(内容包含栈上的变量、参数、返回值和其它存放在栈上的数据)与程序计数器、寄存器，上下文切换时需要进行保存

线程的运行取决于CPU何时进行调度运行，而不是在代码上谁先调用就执行谁

引入线程并发后在共享数据上会出现不一致问题(共享数据被多个线程同时修改，导致数据不准确)

也就是所谓的竞态问题，多个线程同时执行，这样的代码段称为临界区（访问共享变量的代码段），该区域不能多个线程同时执行，需要进行互斥，保证同时刻只有一个线程进行访问修改，通过加锁或者原子操作可以实现。

关键并发术语：

1. 临界区： 访问共享资源的一段代码，资源通常是一个变量或数据结构
2. 竞态条件： 多个执行线程大致同时进入临界区时，都试图更新共享的数据结构，导致了错误的结果
3. 不确定性： 程序由一个或多个竞态条件组成，程序具体的结果取决于那些线程在何时运行，导致了结果的不确定性
4. 如何避免： 线程使用某种互斥原语，保证只有一个线程进入临界区，避免出现竞态，并产生确定的输出结果(加锁或原子操作)

**线程等待：**一 个线程在继续运行之前等待另一个线程完成某些操作才运行，如进行IO操作时的睡眠唤醒

操作系统本身就是一个并发程序，页表、进程列表、文件系统结构以及每个内核数据结构都需要小心访问，并正确使用同步原语

同步原语： 硬件提供的一组通用集合指令，通过与操作系统结合可以实现同步受控的方式访问临界区，产生正确结果(锁，原子操作)

原子操作： 一组最小不可在分的操作，且操作要么都成功，要么都失败，不存在中间状态，保证操作的一致性

6.1 线程API

unix系统经典线程操作API主要有以下几种

1. 线程创建pthread_create()： 用于创建一个新的线程，新线程拥有自己的调用栈，与程序中的所有线程在相同的地址空间内运行
2. 线程等待pthread_join()： 用于等待线程完成，常用于确保退出或进入下一阶段计算前完成所有工作
3. 锁： 通过加锁解锁保护临界区变量，实现互斥
4. 条件遍历（信号量）： 使用信号量作为条件进行线程的等待或者唤醒，如(通过信号量使一个线程等待另一个线程执行某些操作，信号改变执行相应操作)

线程API使用注意

1. 保持简洁： 线程之间的锁和信号的代码尽量简洁，复杂的线程交互容易出错
2. 让线程交互减到最少： 尽量减少线程之间的交互，每次交互都应想清楚，并用验证过的、正确的方法来实现
3. 初始化锁和条件变量： 未初始化的代码有时工作正常有时失败(防止使用其它线程遗留数据，因为地址空间是共享的)
4. 检查返回值： 所有的操作都有可能出现异常，需要检查返回值
5. 注意传给线程的参数和返回值： 不要引用在栈上分配的变量数据，因为线程结束就释放了
6. 每个线程都有自己的栈： 线程的栈是私有的，栈上的变量不要共享，需要共享使用堆保存
7. 线程之间总是通过条件变量发送信号： 不要用标记变量来同步，使用条件变量

6.2 锁

锁： 为程序员提供了最小程度的调度控制，通过给临界区加锁，可保证临界区内只有一个线程活跃，保证临界区数据的准确性

锁是一个变量，这个变量保存了锁在某一时刻的状态，要么表示可用没有线程持有锁，要么不可用表示有一个线程持有锁，正处于临界区，此时其它线程无法在持有锁，需要等待锁释放后才能获取锁进入临界区。

评价锁的三个指标：

1. 是否有效： 是否能够提供最基本的互斥功能
2. 公平性： 当锁可用时，每个竞争的线程是否有公平的机会抢到锁
3. 性能： 使用锁之后所增加的时间开销(三种情况：没有竞争、单CPU多个线程竞争、多CPU多线程竞争)

6.2.1. 锁的实现方案

1. 控制中断： 早期解决方案，进入临界区时关闭中断，保证临界区代码原子执行不会被其它中断干扰，完成后在开启，适用于单处理器

​ 优点： 实现简单，没有中断干扰，线程可以确信代码会继续执行，没有其它线程干扰

​ 缺点： 该方法需要允许所有线程执行特权操作、不支持多处理器、关闭中断可能导致中断丢失、效率低下

2. 自旋锁，硬件提供测试并设置指令：硬件提供原子交换指令，该指令可以测试值，又可以设置新值，并且是原子性的，通过该指令可以简单的实现自旋锁(通过不停的检测标志值是否改变而执行操作)，一直自旋，利用CPU周期，直到锁可用(标志改变)

   例如：当一个线程持有锁，即flag=1,调用lock()时，执行testAdnSet(flag, 1)指令，此时返回1，只要有一个线程持有锁，会重复返回1，本线程会一直自旋，当flag被改为0时，本线程会调用testAdnSet()指令，返回0并原子的将flag设为1，从而获得锁进入临界区

   在单处理器上，需要使用抢占式调度，即不断通过时钟中断一个线程运行其它线程，否则自旋锁在单CPU上无法使用，因为一个自旋的线程永远不会放弃CPU

   优点： 实现了基本可用的锁，并可以在多CPU运行，且性能还不错

   缺点： 没有公平性，自旋的线程在竞争条件下可能会永远自旋，导致其它线程饿死，在单CPU上性能开销大，放弃锁之前都需要自旋

3. 硬件提供比较并交换指令： 检测指针指向的值A是否与标志B相等，如果相等，更新A指向的值为新值，否则什么也不做，无论哪种情况最后都返回A当前的实际值，让调用者知道执行是否成功，且该指令是原子的，通过它也可以实现一个自旋锁，与测试并设置类似

4. 硬件提供链式加载和条件试存储指令： 从内存中取出值存入寄存器，存储时只有上一次加载的地址在此期间都未更新时才会成功(同时更新刚才链接的加载的地址的值)，成功时条件存储返回1，并将指向的值更新为新值，失败时返回0，并不会更新值，通过它也可以实现一个自旋锁

5. ticket锁/硬件提供获取并增加指令：该指令能原子的返回特定的地址的旧值，并且让该值加一，实现一个ticket锁，该方法使用ticket与turn两个变量来构建锁，如果线程希望获取锁，则首先对一个ticket值执行一个原子的获取并相加指令，这个值作为该线程的turn,然后根据全局共享的turn变量，当某一个线程的turn == 全局turn时，则轮到这个线程进入临界区，释放锁则是增加turn,从而下一个等待线程可以进入临界区

   优点： 与自旋锁相比，该方法可以保证所有的线程都可以获取到锁

6. 操作系统支持使用队列（休眠替代自旋）：操作系统提供park()、unpark()、setpark() 系统调用实现锁

   调用者在获取不到锁时进行休眠，在锁可用时被唤醒

7. park()调用： 能够让调用线程休眠

8. unpark()调用： 可以唤醒休眠的线程

9. setpark()调用： 用于解决唤醒等待竞争,避免一个线程将要park时，假定睡眠到锁可用，此时中断切换到另一个线程(锁持有者)执行了unpark，此时刚开始的线程可能将永久休眠，为了避免，执行setpark，然后在执行park时就会立即返回而不是一直休眠

通过休眠唤醒实现更高效锁的流程： 将测试并设置与等待队列相结合，并使用队列来控制谁会获得锁，避免饿死

		1. 使用测试并设置获取锁
		1. 如果锁已经被持有，将线程加入等待队列并让出cpu，调用`park()`将线程进行休眠
		1. 使用测试并设置释放锁
		1. 如果锁可以被释放，先判断等待队列是否为空，为空直接释放
		1. 等待队列不为空，将锁保持分给等待队列里的一个线程并使用`unpark()`调用将其唤醒

两阶段锁： 结合自旋和休眠等待

1. 一阶段： 会先自旋一段时间，希望可以获得锁
2. 二阶段： 如果一阶段没有获得锁，调用者进行休眠，直到锁可用

6.3 基于锁的并发数据结构

6.3. 1 并发计数器(懒惰计数器)

性能取决于阈值S(局部转移到全局的频率)，是在准确性与性能中取折中的方案

懒惰计数器通过多个局部计数器和一个全局计数器加锁来实现一个逻辑计数器，其中每个CPU核心有一个局部计数器，如在4个cpu的机器上就有4个局部计数器，1个全局计数器，此外每个局部计数器都有一个锁，全局计数器一个锁。

实现原理： 某核心上线程想增加计数器，那就增加自己的局部计数器，通过对应的局部锁控制，因为每个cpu有自己的局部计数器和锁，不同cpu上线程不会竞争，所以计数器并发性好，最后保持全局计数器更新，局部值会定期转移给全局计数器，获取全局锁，让全局计数器加上局部计数器上的值，然后清空局部计数器

局部转移频度取决于一个阈值S，S越大：并发性能越好，但全局与局部计数器的值偏差越大，S越小：并发性能越差趋近于非扩展计数器，所以阈值S很重要，懒惰计数器是在准确性与性能中取折中

6.3.2 并发链表

在链表操作前后加锁

6.3.2 并发队列

使用2个锁，一个负载队头，一个负载队尾，使队头队尾操作可以并发

6.3.3 并发散列表

通过为每个散列桶加锁，而不是全局加一把大锁实现

更多并发不一定快： 如果方案带来了大量开销，那么并发就没有意义，简单但少一点并发，复杂但多一点并发，测试它的表现在做取舍

注意锁和控制流： 注意控制流的变化导致函数返回和退出，或其它错误情况导致函数停止执行，这些附近容易出错，尤其是持有锁时

避免不成熟的优化： 实现并发数据结构先从最简单的开始，发现问题在改进优化，优化到满足即可，局部优化不能提高整体性能就无价值

6.4 条件变量

很多情况下，线程需要检查某一条件满足后才继续运行，如父进程需要检查子进程是否执行完毕，通常这些需要使用条件变量原语实现

通过条件变量进行线程的等待唤醒：

线程可以通过使用条件变量来等待一个条件变成真，条件变量是一个显示队列，当某些条件(执行状态)不满足时，线程可以把自己加入队列，等待该条件，另外某个线程当它改变了上述状态时，就可以唤醒一个或多个等待的线程，通过在该条件上发信号让他们继续运行

条件变量的2种操作：调用时都需要持有锁，防止竞态陷入长久睡眠,多线程在使用条件变量时使用while，不用使用if

1. wait()：用于线程睡眠，使其等待
2. signal()：用于唤醒等待在某个条件变量上的睡眠线程

生产者消费者(有界缓冲区)：

有界缓冲区是共享资源，必须要使用同步机制来访问，避免产生竞态问题，可以使用条件变量来同步，生产时缓存满了就停止，消费时消费完了就停止，生产者等待缓存区为空，消费者等待缓存区为满，然后相互唤醒等待

6.5 信号量

信号量： 一个整数值的对象，可以使用函数操作它，在POSIX标准中，是sem_wait()/sem_post()

信号量的初始值能够决定其行为，使用时需要先初始化信号量，才能调用其它函数与之交换

通过信号量可以实现：锁、条件变量、生产/消费

1. 二值信号量(锁)： 使用信号量做锁，如0,1来表示锁的持有与释放(因为锁只有持有与未持有2种状态)

2. 信号量用在条件变量： 实现一个线程暂停执行，等待某一条件成立在执行(使用信号量实现条件变量的功能，类似go中的wait,done)

3. 信号量实现生产者/消费者（有界缓冲区）： 使用信号量实现生产者消费者，在改变值的临界区加锁

读写锁： 一个读者获取了读锁，其它读者也可以获取这个锁，但是想要获取写锁的线程需要等待所有的读者都结束，才能获取写锁

哲学家进餐问题：并发经典问题

5位哲学家围绕餐桌就餐，每2位哲学家之间有一把餐叉(共5把),每位哲学家只有同时拿到左手边与右手边的餐叉才能进餐，如何保障没有哲学家饿死，并且尽可能让更多哲学家进餐

解决办法：

1. 单纯的依次获取每把餐叉的锁，先左边，然后右边，用餐完毕释放，但是存在(死锁问题)

   当每个哲学家都拿到了左手边的餐叉，他们每个都会阻塞住，并且一直等待另一个餐叉，出现死锁

2. 在1的基础上破除依赖，修改某些哲学家就餐顺序，如第4个哲学家先右边，在左边，此时不会出现每个都拿一个餐叉卡主等待另一个

6.6 并发常见问题

常见并发问题存在两种主要类型:死锁、非死锁

1. 非死锁缺陷：占据并发问题的多数，主要原因如下

2. 违反原子性： 违反了多次内存访问中预期的可串行行为(因该一起执行的指令没有一起执行)，解决办法给需要访问的共享变量加锁

3. 错误顺序： 两个内存访问的预期顺序被打破(两个线程的执行顺序没有强制保证，A在B之前先执行，实际出现B先运行)，解决使用条件变量进行等待

4. 死锁缺陷： 互相持有对方需要的锁，互相等待对方释放锁(如A持有L1,等待L2，B持有L2，等待L1)

5. 出现死锁缺陷的原因：

6. 主要由于大型的代码库里组件之间存在复杂的依赖，需要避免循环依赖

7. 由于代码的封装，让某些看起来不相关的接口调用出现死锁，模块封装内部可能存在调用但隐藏了细节

死锁产生的条件： 如果以下4个条件任何一个没有满足，死锁就不会产生

1. 互斥：线程对于需要的资源进行互斥的访问(如一个线程抢到锁)
2. 持有并等待：线程持有了资源(已经持有了锁)，同时又在等待其它资源(如需要获得的锁)
3. 非抢占：线程获得的资源不能被抢占(如锁)
4. 循环等待：线程之间存在环路，环路上每个线程都持有一个额外的资源，而这个资源又是下一个线程需要申请的

死锁的预防：

1. 有序加锁: 避免循环等待，(全序：若存在2把锁每次先获取L1,在获取L2、偏序：存在多组加锁关系，先获取锁关系1，在获取锁关系2)

   如根据锁的地址大小来保证获取顺序，获取锁时先判断传入锁地址大小，按固定顺序加锁

   // 代码如下,保证了不管怎么调用都按锁地址大小固定顺序加锁
   func doSomeThing(m1, m2 lock) {
       if m1 > m2 {
           lock(m1)
           lock(m2)
       }else{
           lock(m2)
           lock(m1)
       }
   }
   

2. 原子地抢锁： 避免持有并等待,使用全局锁来避免，需要加锁先获取全局的锁，然后在进行加锁(注意：此方案不适于封装，需要精确知道要抢那些锁，并提前抢到这些锁，同时因为需要提前抢到锁而不是真正需要时，降低了并发)

3. 使用尝试： 避免非抢占，获取锁时先尝试获取，要么获取到锁，要么返回一个状态值，表示锁已经被占有(注意：此方案也不适于封装，如果某个锁封装在函数内部，尝试获取锁时很难实现跳回开始处)

4. 硬件原子指令： 避免互斥,通过原子指令避免在临界区使用加锁解锁互斥，避免了锁操作(不会存在死锁，但可能存在活锁)

5. 使用调度避免死锁： 记录不同线程对锁的需求，采取不会出现死锁的调度方式调度，银行家算法就是类似的解决方式(调度方式使用不广泛，会限制并发)

6. 检查恢复： 允许死锁偶尔发生，检查到死锁时在行动，

活锁： 2个线程一直运行重复序列获取锁，但是又同时都抢锁失败，导致系统一直运行该段代码，但又没有任何进展

活锁解决方法： 可以在循环结束的时候先随机等待一段时间，然后在重复该动作，降低线程间的重复互相干扰

6.7 基于事件的并发

基于事件的并发，常用于GUI图形化应用与某些网络服务器，主要解决某些多线程应用中并发处理难度大，无法控制多线程在某一时刻调度的场景

基于事件并发思想: 等待某事件发生，当它发生时检查事件类型，然后执行相应事件的处理工作

基于事件循环的伪代码如下

wwhile true:                // 无限循环
	events = getEvents()    // 获取事件
	for e in events		   // 判断事件类型并处理
		processEvent(e)

事件处理代码称事件处理程序，其处理事件时，是系统中唯一发生的活动，调度就是决定接下来处理那个事件，这种调度显示的控制是事件处理的一大优点

基于事件处理需要面对的问题，服务器如何决定那个事件先发生(事件服务器如何确定是否有它的消息已经到达)

事件API select()/poll()系统调用： 解决事件接收问题，检查是否有任何需要关注的信息进入IO(如网络服务器检查是否有网络数据包到达以便提供服务)

1. select():检测IO描述符集合，返回所有集合中就绪描述符的总数（检查是否准备好读取：是否有新数据到达需要处理、写入：何时可以回复、或有异常待处理）
2. poll():与select系统调用功能类似

阻塞与非阻塞接口：

1. 阻塞接口：也称同步接口，在返回给调用者之前完成所有工作
2. 非阻塞接口：也称异步接口，开始一些工作，但立即返回，从而让所需要完成的工作都在后台完成

不要阻塞基于事件的服务器： 为了保持服务器对调度任务的细粒度控制，不可以有阻止调用者执行的调用(还因为基于事件的服务是单线程的，一次只处理一个事件，不存在并发问题，不需要加锁)，如果阻塞主线程，会造成资源浪费，不允许阻塞调用

异步IO： 解决基于事件的并发不能阻塞调用的问题（向磁盘发出IO操作会阻塞，浪费资源），因此使用异步的方式发出IO请求

异步IO接口使应用程序能够发出IO请求，并在IO完成之前立即将控制权返回给调用者，另外的接口让应用程序能够确定各种IO是否已经完成

总结基于事件的并发

1. 优点： 简单，不需要锁，对程序进行显示调度（单CPU时）
2. 缺点：
3. 需要决定何时进行调度处理事件(使用selec解决)
4. 不能进行阻塞调用（使用异步IO解决）
5. 回调状态管理（回调时需要知道调用时的相关信息才能正确回调）(使用延续解决，调用时记录相关信息，异步完成后查询记录的相关信息进行后续处理)
6. 多核CPU时实现复杂，需要使用加锁保护临界区
7. 不能与某些系统获得集成，如分页，发生页错误时会被阻塞，事件服务器会再次等待
8. 随着时间推移代码很难管理，不同的代码可能会发生改变，调用的事件处理程序也需要调动

7. 持久性(文件系统)

7.1 IO设备

IO输入输出对计算机程序特别重要，没有输入输出，计算机程序就没有运行的必要，因此如何将IO输入输出集成在计算机系统中尤为重要

常见系统架构如下：越快的总线越短越贵，因此使用如下分层

CPU通过内存总线连接内存，高速设备通过常规IO总线连接，最慢设备如磁盘、鼠标、USB设备连接外设IO总线

标准设备： 标准设备一般包含2部分组件

1. 硬件接口： 用于向系统提供操作设备的接口（通过对内部功能封装抽象提供的接口）
2. 内部结构： 设备一般包含内存、寄存器、特定芯片等来实现设备功能，通过固件(硬件设备中的软件)来实现具体功能

标准协议： 一般设备包含3个寄存器，通过他们操作系统可以控制设备的行为

1. 状态寄存器：可以读取查看设备当前的状态
2. 命令寄存器：用于通知设备执行某个具体任务
3. 数据寄存器：将数据传给设备或从设备接收数据

典型交换协议： 优点：实现简单有效，缺点：效率低下，需要不断轮询，浪费CPU

1. 轮询设备： 操作系统通过反复读取寄存器状态，等待设备进入可接收命令的状态
2. 编程IO/PIO: 操作系统下发数据到数据寄存器，
3. 执行命令： 操作系统将命令写入命令寄存器，设备开始执行命令
4. 再次轮询： 操作系统再次轮询，等待判断设备是否执行完成命令(可能返回成功或失败)

7.1.1 中断减少轮询

使用中断减少CPU轮询开销： 中断可以实现计算与IO重叠，提高CPU利用率

通过中断，CPU不在轮询设备，而是向设备发出一个请求，然后就可以让对应进程进入睡眠，CPU切换执行其他任务，当设备完成了自身操作，会抛出一个硬件中断，触发CPU进入中断处理程序，结束当前运行进程，唤醒等待IO的进程继续运行

中断不总是是最佳方案，高速设备不使用中断，因为高速设备很快，通常在CPU第一轮轮询时就返回结果，耗时比中断更少，中断需要进行上下文切换,比较耗时，反而使系统变慢。

一般使用如下：

1. 高速设备：使用轮询
2. 低速设备：使用中断
3. 未知速度设备：可以使用混合，先尝试使用轮询，设备未完成在使用中断
4. 网络场景：不使用中断，网络收发数据包较大，频繁使用中断，容易出现活锁，CPU都执行中断去了，反而降低效率

7.1.2 DMA直接内存访问

使用DMA进行高效数据传输，减少CPU在设备传输数据时的消耗，DMA可以协调内存与设备间的数据传输，不需要CPU接入，

DMA数据拷贝流程

1. 操作系统通过编程告诉DMA存储数据的内存地址，要拷贝的大小，以及要拷贝到那个设备
2. 此后，操作系统就可以处理其它请求了
3. 当DMA任务完成后，DMA控制器抛出一个中断，告诉操作系统已经完成数据传输

设备交换(通信)方法： 主要有2种，2种方法目前都在使用，方法2的好处是不需要引入新指令即可实现

1. 使用明确IO特权指令，指令规定了操作系统将数据发送到特定设备寄存器的方法，执行指令即可实现,只能在内核态操作系统执行
2. 内存IO映射，将设备寄存器作为内存地址通过操作系统直接在该地址读写数据，数据会被保存在硬件设备的寄存器上

7.1.3 设备驱动程序

通过设备驱动程序，操作系统对不同设备接口的抽象，实现通用性，不用在每个设备上都实现一套方法，统一管理驱动程序即可，驱动程序负责设备底层交换

简单的IDE磁盘驱动程序，该程序暴露给OS的接口比较简单，主要有：控制、命令块、状态、错误，其设备交换流程如下，前提设备已初始化

1. 等待驱动就绪：读取状态寄存器，直到驱动就绪而非忙碌
2. 向命令寄存器写入参数：写入扇区数，待访问扇区对应逻辑地址，并将驱动编号写入命令寄存器
3. 开启IO：发送读写命令到寄存器
4. 数据传输(写请求)：当设备驱动状态为就绪与渠道请求数据时，向数据端口写入数据
5. 中断处理：每个扇区数据传送完触发中断，或者全部传送完触发中断
6. 错误处理：每次操作后读取状态寄存器，如果ERROR位被置位，可以读取错误寄存器来获取错误信息

7.2 磁盘驱动器

如何存储和访问磁盘上的数据，接口是什么，数据是如何安排和访问的，磁盘调度如何提供性能,详细信息如下

接口： 驱动器由大量扇区组成(512字节)块组成,每个扇区都可以读取或写入，扇区从0-n-1编号，可以将磁盘视为一组扇区，0-n-1为驱动器的地址空间

驱动器只保证单个512字节的写入是原子完整的，发生不合时宜的掉电时，只能完成较大写入的一部分，此外磁盘顺序读取或写入是最快的，比任何随机访问都快

磁盘组成：

1. 盘片：磁盘可以存在一个或多个盘片，每个盘片的两面称为表面
2. 主轴：所有盘片都围绕主轴连接在一起，主轴连接到一个电机以恒定的速度旋转盘片，常见每分钟转速7500-15000RPM
3. 磁道：数据在扇区的同心圆中的每个表面被编码，称这样的同心圆为磁道
4. 磁头：驱动器的每个表面存在一个磁头，通过磁头读写数据，磁头连接在单个磁盘臂上，磁盘臂在表面上移动，将磁头定位在期望的磁道上

简单磁盘驱动器

1. 单磁道延迟，选择延迟： 盘面只有一个磁道，读取某扇区数据时，必须等待期望的扇区旋转到磁头下(IO服务时间的重要原因之一)

2. 多磁道，寻道时间： 盘面有多个磁道，访问期望的扇区时，需要先找到需要访问扇区所在的磁道，然后移动磁头到该磁道等待旋转，寻道旋转操作耗时

3. 磁道缓存： 驱动器的上的存储器(内存较小)，用于存储从磁盘读取或写入的数据，提升性能

IO时间： Tio时间 = T寻道 + T旋转 + T传输， RioIO速率 = 传输大小/Tio时间

顺序的的使用磁盘，顺序不行，可以大块传输数据，越大越好，这样磁盘性能较高，如果IO是以小而随机方式读取性能低下

7.3 磁盘调度

磁盘调度： 给定一组IO请求，磁盘调度程序检查请求并决定下一个要调度的请求

与任务调度的区别： 对于磁盘调度，我们可以很好的猜测出(磁盘请求)需要多长时间，通过估计请求的查找和扇区的的旋转延迟

因此调度程序可以知道每个请求将花费多长时间，可以贪婪地旋转先服务花费时间最少的请求，调度程序遵循SJF最短任务优先原则

7.3.1 常见调度策略

1. 最短寻道时间SSTF优先： 按磁道对IO请求队列排序，选择在最近磁道上的请求先完成，如中磁道21，最外磁道2，当前在最内磁道，先完成磁道21在完成2

2. 优点：实现简单，操作系统可以以最近块优先，然后用最近块的地址来调度请求

3. 缺点:存在饥饿，最如果磁头当前所在的内圈有稳定的请求，该调度将完全忽略对其它磁道的请求

4. 电梯调度算法(SCAN/C-SACN/F-SCAN)： 简单的已跨越磁道的顺序来服务磁盘请求，将一次跨越磁盘作为一次扫描，因此请求的块所属的磁道在这次扫描中已经服务过了，它就不会立即处理，而是排队等待下一次扫描

   F-SCAN： 在扫描一遍时冻结队列以进行维护，会将扫描一遍时加入的请求放入队列中以便稍后处理，避免远距离请求饥饿，延迟了迟到但更近的请求

   C-SCAN：循环扫描，不是一个方向扫描而是从内到外，在从外到内循环

以上调度算法只考虑了寻道时间，没有考虑旋转时间

7.3.2 SPTF最短定位时间优先

SPTF最短定位时间优先：同时考虑寻道时间和旋转时间，视二者时间长短来进行先调度谁，由驱动器内部实现并调度

1. 如寻道时间远高于旋转时间，使用上面的调度策略即可
2. 如果寻道时间远小于旋转时间，调度寻道时间段的请求，如内道寻道时间10，旋转时间20 外道寻道时间1，旋转时间10，优先调度外道请求

缺点： 该调度实现复杂，操作系统不知道磁道边界以及当前磁道位置，一般由驱动器内部实现执行调度

7.3.3 其他调度问题

1. 操作系统调度程序通常将选择它认为最好的几个请求一起发送给磁盘，磁盘内部利用磁道磁头信息以最佳SPTF顺序服务与这些请求
2. 调度程序会将磁盘IO请求合并，执行的所有请求都是基于合并后的请求，如原请求：33-8-34, 合并后：8-(33,34),合并33-34请求,降低系统开销
3. 发送IO请求后，系统一般需要等待一段时间才会请求驱动器执行，而不是立即请求，可提高效率，减少不必要请求,如修改后又撤销的请求就不用重复发送

7.4 RAID磁盘阵列

通过RAID磁盘阵列技术，可以将多个磁盘组合成一个逻辑上的更大、更快、更可靠的磁盘系统，其对操作系统和软件透明，部署不需要改变任何原有软硬件

常见硬件RAID(硬件raid阵列卡，内部运行raid软件程序类似一个微型计算机系统，拥有自己的处理器，存储器，进行数据的计算校验缓冲等)，软件raid(软件代码模拟实现)，一般硬件raid效率更高

RAID阵列评价主要指标：容量、可靠性、性能

RAID磁盘映射：RAID通过使用 [磁盘=A逻辑块地址 % 磁盘数、 偏移量=A逻辑块地址 / 磁盘数]来计算程序读取的最终物理磁盘和偏移量，都为整数运算

多磁盘RAID一致性问题： 数据写入时一个写入完成，一个由于掉电或其它原因导致写入失败不一致问题

解决此问题一般使用预写日志，在写入之前将相应操作先记录到日志，可以保证出现故障时可以使用该记录重新在raid上执行，保证磁盘数据同步，为了避免每次写入都在磁盘进行日志记录，raid硬件一般会包含少量非易失性RAM用于记录，既保证了一致性又避免了花费高昂代价记录日志到磁盘

7.4.1 常见raid级别性能总结

1. RAID0：条带卷性能最高，磁盘使用率100%，性能最高，但是不可靠没有备份，至少2块磁盘
2. RAID1:镜像卷，磁盘利用率50%，性能折中可靠，但利用率只有2/1，至少2块磁盘
3. RAID5奇偶校验，磁盘利用率75%，性能，备份，利用率折中，至少3块磁盘

RAID容量、可靠性和性能总结表如下

	RAID0 条带卷	RAID1 镜像卷	RAID5 奇偶校验
磁盘数	N>=2	N >= 2	N >=3
容量	N	N/2	N-1
可靠性	0	1(肯定)	1
吞吐量
顺序读	N.S	(N/2).S	(N-1).S
顺序写	N.S	(N/2).S	(N-1).S
随机读	N.R	N.R	N.R
随机写	N.R	(N/2).R	M/4.R
延迟
读	T	T	T
写	T	T	2T

7.5 文件和目录

存储虚拟化的2个核心技术：文件、目录

文件： 一个线性字节数组，每个字节都可以读取或写入，每个文件都拥有某个低级名称inode号与之关联，这个inode号对用户屏蔽，用户不需要知道

目录： 像文件一样也有一个inode号，但它包含的内容为一个文件列表对，文件列表以（用户可读名称，inode号）对方式存放在文件目录，目录中的每个条目都指向文件或目录，通过将目录放入其它目录可以构建目录树，或目录层次结构，在该目录树下存放所有文件和目录，如Linux的根目录/

目录和文件可以拥有相同名称，前提是目录和文件在不同目录(位于文件系统树的不同位置)：如/foo/bar.txt /bar/foo/bar.txt

目录存储内容

如目录存在一个文件名称用户可读名称`foo`,inode号=`10`的文件
目录记录的就是一条("foo", "10")的记录，将用户可读名称映射到低级名称inode号，访问时该记录映射到具体的文件

7.5.1 文件系统接口

文件描述符号： 一个整型数字，是每个进程私有的，类似一个指向具体文件对象的指针，通过它对文件做修改，在linux系统中主要用于访问文件，一但文件被打开，就可以使用文件描述符来读取文件，如果有权限，一个文件描述符也是一种权限一个不透明的句柄，可以让你执行某些操作

**linux中的strace命令:**可以跟踪程序生成的系统调度，查看参数和返回代码，并将结果打印到屏幕，可以很好的理解程序详细的执行过程

strace常见参数：-f 跟踪所有fork的子进程  -t 报告每次调用的时间 -e trace=open,close 只跟踪对这些系统调用的调用，忽略其他调用

文件系统接口: 操作系统提供对文件进行增删改查的必要接口

1 创建文件

创建文件，使用open系统调用完成，调用open()并传入O_CREATE标志，程序可创建一个新文件,返回文件描述符

常见标志： O_CREAT程序创建文件，O_WRONLY只读方式，O_TRUNC如果文件已存在清空当前文件

标志传入时可以传入多个： 例如 int fd = open("foo", O_CREAT | O_WRONLY | O_TRUNC)，创建一个文件，以只读打开，文件已存在则清空

creat()系统调用： 对open调用的封装等同于==open("foo", O_CREAT | O_WRONLY | O_TRUNC)

2 按顺序读写文件

通过linux中的strace 对cat foo的系统调用追踪核心过程进行读写分析如下

[root@cvm31754 ~]# strace cat foo            // 追踪cat foo系统调用核心过程
...
open("foo", O_RDONLY)                   = 3  // 以只读方式打开文件foo, 返回文件描述符3
read(3, "hello\n", 65536)               = 6  // 读取文件描述符3，hello\n内容到缓冲区，缓冲区大大小65535， 返回6,读取到的字节数
write(1, "hello\n", 6)                  = 6  // 将缓冲区内如写入到标准输出1， 内容hello\n, 写入字节6
read(3, "", 65536)                      = 0  // 循环读取，读取内容为空
close(3)                                = 0  // 关闭文件
close(1)                                = 0  // 关闭标准输出
close(2)                                = 0  // 关闭标准错误
...

第一次调用open()返回文件描述符3是因为每个正在运行的进程已经打开了3个文件（0标准输入，1标准输出，2标准错误），因此打开的文件描述符肯定为3

文件打开后，cat使用read系统调重复读取文件中的一些字节，执行的步骤如下

1. read读取文件字节(参数1：文件描述符，参数2：指向一个放置read结果的缓冲区， 参数3：缓冲区的大小， 返回结果读取到的字节大小)
2. write写入数据（参数1：文件描述符1标准输出，参数2：写入的内容， 参数3：写入的字节大小）系统内部调用可能还执行了printf等
3. read循环读取(直到read读取的内容为空，返回读取到的字节=0，停止读取)
4. close关闭文件(关闭文件3， 关闭标准输出1， 关闭标准错误2)执行结束

​ 写入文件流程与上面也一致，打开文件，写入文件(较大文件可能重复多次写入)，关闭文件

3 不按顺序读写文件

通过使用lseek()系统调用，可以指定偏移量，读取文件从指定位置开始的内容,lseek系统调用函数原型如下

off_t lseek(int fildes, off_t offset, int whence)
// 参数1： 文件描述符，需要操作的文件
// 参数2： 文件偏移量
// 参数3： 明确指定搜索执行的方式
对于每个打开的文件，操作系统都会跟踪一个当前的偏移量，其决定在文件下一次读取或写入时的起始位置，因此打开文件的抽象包括当前偏移量
偏移量的更新：
1. 当发生N个字节的读或写时，N被添加到当前偏移量，因此每次读写都会隐式更新偏移量
2. 明确的lseek, 明确指定偏移量改变

lseek系统调用不会执行磁盘寻道，没有直接关系，它只是在OS内存中更改一个变量，该变量跟踪特定进程的下一个读写开始的偏移量，执行IO时，根据磁头位置，磁盘可能会也可能不会实际执行寻道，但调用lseek在文件的随机位置读取写入，确实会导致更多磁盘寻道(发送到磁盘的读取与最后一次读取不在同一磁道就会进行寻道移动磁头)

4 fsync立即写入

一般情况下为了提高操作系统性能，执行write调用时并不会直接写入磁盘，文件系统会将这些数据写入内存缓冲区,一段时间后才会将数据写入实际存储设备，从应用程序来看写入很块完成，但在异常情况下，写入缓冲区后还未同步到存储设备机器崩溃会造成数据丢失，因此操作系统提供了fsync系统调用，调用后数据会被立即写入存储设备

5 rename文件重命名

在需要进行文件重命名时，linux中命令实例为： mv aa bb 进aa重命名为bb,使用strace 系统追踪发现该操作使用了rename系统调用，该系统调用是一个原子调用，保证了文件名称修改要么成功要么失败，不会有中间状态

6 获取文件信息

文件系统保存的文件信息称为文件的元数据，可以使用stat,fstat系统调用获取，系统调用会将提供的路径名参数或文件描述符添加到一个文件中，并且填充一个stat结构，常见信息如下，一般每个文件系统都将这种类型信息保存在一个名为inode的结构中

[root@cvm31754 ~]# stat  install.sh 
  File: ‘install.sh’                             // 文件名称
  Size: 29048     	Blocks: 64         IO Block: 4096   regular file     // 文件大小，块类型信息
Device: 803h/2051d	Inode: 4326403     Links: 1						   // 文件设备，inode号， 链接信息
Access: (0644/-rw-r--r--)  Uid: (    0/    root)   Gid: (    0/    root) // 文件访问权限，uid,gid, 所属组。用户信息
Access: 2023-04-28 10:01:48.177075386 +0800		// 文件访问时间											
Modify: 2022-04-19 10:11:04.000000000 +0800		// 文件修改时间
Change: 2022-04-30 14:38:52.348639229 +0800		// 文件改变时间

7 unlink删除文件

在linux系统中使用rm 可以删除文件，但实际执行的系统调用是unlink系统调用，该调用参数为需要删除的文件名称，调用成功时返回0，只会删除文件对底层inode的映射关系，不会在存储设备彻底删除，因此某些删除的数据可以执行恢复数据，除非该inode的引用计数为0时文件系统才会真正删除

8 mkdir创建目录

除文件外，还可以使用一组与目录相关的系统调用进行目录创建修改，注意不能直接写入目录，目录的格式被视为文件的元数据信息,只能间接更新目录，如在文件目录创建文件，目录，通过该方式文件系统可以确保目录的内容始终符合预期

通过mkdir()系统调用可以创建目录，参数为目录名称，与目录权限，调用成功返回0，如 mkdir("xx", 0777),默认创建的目录为空目录，包含2个条目，一个是自身引用. 一个是引用其父目录的..

9 读取目录

在linux中使用ls可以读取目录，它调用了opendir,readdir,closedir三个调用

10 删除目录

删除目录执行rmdir系统调用，删除时目录需要为空，否则调用失败

11 硬链接

通过link()系统调用，为文件生成一个硬链接，类似一个完全一样的文件，类似复制，参数为：linke(旧文件名称，新文件名称），底层原理是新建一个用户可以识别的名称，将它指向旧文件的inode号，此时inode号的引用加1，因此删除的系统调用为unlink

在linux中使用ln a b 命令实现，此时a,b内容一致，a,b名称映射到同一个底层inode号，不能跨分区因为不同文件系统inode号不一样

12 符号链接

由于硬链接不能创建目录链接(担心在目录树中创建环)同时不能跨分区(因为不同分区的inode号不同，在特定文件系统是唯一的，而不是夸文件系统)，因此出现符号链接(软连接，可以跨分区)，类似win的快捷方式

符号链接与硬链接的区别：

1. 符号链接本身实际上是一个不同类型的文件，是文件系统知道的第三种类型
2. 删除原始文件，会导致符号链接不可用，因为符号链接只是一个指向原文件的快捷方式,指向的原文件不存在就会不可用

13 创建并挂载文件系统

linux中通过mkfs可以给一块分区写入一个空文件系统，创建后使用mount将该文件系统挂载挂载到统一的文件目录树下，然后使用该目录就可以在该系统下进行访问读取了，mount系统调用将所有的文件系统都统一挂载到一棵树中，实现了通用命名统一管理

7.6 文件系统

文件系统：纯软件系统，不需要硬件支持(实现还是需要考虑硬件设备的特性)，灵活度较高

文件系统的两个重要方面：

1. 数据结构： 文件系统在磁盘上使用那些类型的数据结构组织其数据和元数据
2. 访问方法： 如何将进程发出的调用映射到它的结构上，执行特定系统调用期间调用、读取、改写那些结构，这些步骤的执行效率如何

文件系统心智模型应包含的必要答案：

• 磁盘上那些结构存储文件系统的数据和元数据
• 当一个进程打开一个文件时会发生什么
• 在读取或写入期间访问那些磁盘结构

简单文件系统VSFS的实现如下

7.6.1 整体组织

将构建文件系统的磁盘分区分成一些列固定大小的块，在大小为N个4KB的块分区中，块的地址为0-N-1，且按不同功能将这些块进行划分

• 数据区域： 存储用户数据
• inode表： 存储inode结构数据(元数据信息)，每个inode包含文件的元数据信息(文件包含哪些数据块，文件大小，权限，访问修改时间等),inode的数量表示该文件系统中拥有的最大文件数量
• 位图：记录inode或数据块是空闲/已分配，有数据位图，inode位图分别记录(位图是一种简单的数据结构，每个位用于标识相应的对象/块是空闲0，还是使用1，还可使用其它数据结构如空闲列表)
• 超级快： 记录该特定文件系统的信息，如（多少个inode和数据块，inode表的开始位置，和一些幻数标识文件系统类型等)

在挂载文件系统时，操作系统首先读取超级块，初始化各种参数，然后将该卷添加到文件系统树中，访问时操作系统就知道在哪里查找所需的磁盘上的结构

7.6.2 inode文件组织

文件系统最重要的磁盘结构之一是inode,几乎所有的文件系统都有类似结构，用于保存给定文件的元数据信息,每个inode都由一个数字隐式引用，就是前面说的低级名称，在VFS和其它简单文件系统中，通过该inode号，可以直接计算出磁盘上相应的结点位置

设计inode时,最重要决定之一就是它如何引用数据块的位置，简单的方法就是每个inode中包含一个指向磁盘数据块的指针实现映射，但不灵活

在ext2文件系统中inode结构包含的内容如下表

大小（字节）	名称	inode字段用途
2	mode	该文件是否可以读/写/执行
2	uid	谁拥有该文件
4	size	该文件有多少个字节
4	time	该文件最近的访问时间是什么时候
4	ctime	该文件的创建时间是什么时候
4	mtime	该文件最近的修改时间是什么时候
4	dtime	该inode被删除的时间是什么时候
2	gid	该文件属于那个分组
2	links count	该文件有多少硬链接
4	blokcs	为该文件分配了多少块
4	flags	ext2将如何使用该inode
4	osdl	OS相关字段
60	block	一组磁盘指针(共15个)
4	generation	文件版本(用于NFS)
4	file acl	一种新的许可模式，除了model位
4	dir acl	称为访问控制表
4	faddr	未支持字段
12	i osd2	另一个OS相关字段

多级索引：

为了支持更大的文件系统，必须在inode中引入不同的结构

间接指针：

常见思路是引入一个称为间接指针的特殊指针，它指向包含更多指针的块，每个指针指向用户数据，因此inode可以有一些固定数量的直接指针(如12)和一个间接指针，如果文件变得足够大，将会分配一个间接块(磁盘的数据块区域)，并将inode的间接指针指向它，可以存在多层间接指针用以支持更大的文件，如双重间接指针、三层间接指针等

// 例如 假设一个块 = 4kb
// 磁盘地址是4字节，那就增加了1024个指针，文件可以增长到（12+1024）* 4kb = 4144kb

基于范围：

另一种方法是基于范围而不是指针，范围就是一个磁盘指针加一个长度(以块为单位),因此不需要指向文件的每个块的指针，只需要指针和长度来指定文件的磁盘位置，只有一个范围是有局限的，因此通常基于范围的文件系统允许多个范围，从而在分配文件时给于文件系统更多的自由

两种方法的对比：

1. 基于指针的方法是最灵活的，但是每个文件使用大量元数据(尤其是大文件)
2. 基于范围的方法不够灵活，但更紧凑，如果磁盘有足够可用空间且文件可以连续布局，基于范围的方法都可以正常运行

此外还存在一种更简单的基于链接的分配方法，在一个indoe中只需要一个指针，指向文件的第一个块，需要处理大数据，就在该数据块尾部添加另一个指针，同时由于链表的特性，不是将下一个指针与数据块一起存储，需要添加一个链接信息表，该表用来记录数据块的地址，通过对地址进行索引，可以很方便的对数据进行随机文件访问，只需要通过扫描链接信息表(内存中)查找需要的块，然后直接访问磁盘上，(如文件分配表FAT,经典的旧win文件系统)

7.6.3 目录组织

在VSFS中，包括很多文件系统中，目录组织很简单，一个目录基本上只包含一个二元组(条目名称，inode号)列表，对给定目录中的文件或目录，目录的数据块中都只有一个字符串，和一个数字，对于每个字符串可能还要一个长度。

//如：目录dir(inode = 5) 中有3个文件 (foo, bar, foobar), inode分别为(12,13,24),在磁盘的数据可能如下
inum  |  reclen  |  strlen  |  name
 5          4          2         .
 2          4          3         ..
 12         4          4         foo
 13         4          4         bar
 24         8          7         foobar

样列中每个条目都有一个：`indoe号，记录长度(名称的总字节数加上所有的剩余空间)，字符串长度(名称的实际长度)、条目名称`
此外每个目录有2个额外目录：. ..   .目录为当前目录dir ， ..目录为父目录在本列中是根目录

删除文件如unlink调用会在目录条目中间留下空白，因此使用一个保留的inode 0 来标记, 而不用直接删除，用于复用，新条目可能会重复使用旧的更大的条目，通过记录长度来判定大小

文件系统将目录视为特殊类型文件，因此目录有一个inode，位于inode表中的某处(inode表中的inode标记为目录类型字段，而不是常规文件)，该目录具有由inode指向的数据块或间接块，这些数据块存在简单文件系统的数据块区域中，因此不需要改变磁盘结构

此外目录列表还可以使用其它任何数据结构存储，如XFS中以B树形式保存，快于简单列表系统

7.6.4 空闲空间管理

文件系统必须记录那些inode和数据位空闲，那些不是，这样在分配新文件或目录时，就可以为它找到空间，空闲空间管理对于所有的文件系统都很重要，在VSFS中，使用2个简单的位图来进行标记

在VSFS中，创建文件分配indoe时，文件系统通过位图搜索一个空闲的内容，并将其分配给文件，同时将分配的indoe对应的位图标记为1已使用，新文件分配时还可以使用预分配，分配时查找一些列连续的空闲块分给创建的文件，从而保证文件的一部分在磁盘上是连续的提高性能，这种预分配策略是为数据块分配空间时的常用启发方式

管理空闲块的方式有多种，还可以使用空闲列表，B树等数据结构进行管理

7.6.5 访问路径读取与写入

从磁盘读文件：

假设打开文件/foo/bar 读取它，然后关闭它，流程如下

1. 发起Open("/foo/bar", O_RDONLY)系统调用，文件系统首先找到文件bar的inode号，获取关于文件的基本信息(权限、大小等)
2. 寻找inode时，由于当前只有完整的路径名，寻找inode时文件系统需要遍历路径名，从而找到需要的inode号
3. 所有遍历都从文件系统根开始(根目录)，因为根目录没有父目录，因此没有目存储它的inode信息，通常使用默认定义的inode号，一般为2
4. 文件系统读取根inode后，在其中查找指向数据块的指针，数据块包含根目录内容，文件系统使用这些磁盘上的指针来读取目录
5. 在根目录寻找foo目录，找到foo目录的inode号
6. 读取foo目录的inode号，获取目录内容，以此循环递归遍历路径，直到获取到目标文件的indoe号
7. 找到bar inode号，open系统调用将其读入内存，然后文件系统进行最后的权限检查，在进程的打开文件表中，为此进程分配一个文件描述符返回给用户
8. 程序通过文件描述符调用read系统调用进行文件内容读取（第一次读取，偏移量为0，除非lseek已被调用）,将在文件的第一个块中读取，查阅inode,确定该块的位置，它也会用新的最后访问时间更新inode,读取将进一步更新此文件描述符在内存中打开的文件表，更新文件偏移量，以便下一次读取时读取第二个文件块
9. 在某个时候读取关闭，释放文件描述符

整个读取过程，首先需要查询inode号，然后读取块，在使用写入更新inode的最后访问时间字段(查询需要根据全路径多次递归遍历路径的inode号读取数据，直到找到目标indoe号)，open导致的IO与文件路径名的长度成正比，路径越长，进行的读取IO操作次数越多

写入磁盘：

写入文件过程与读入类似，首先需要打开文件，其次应用程序进行write调用更新文件，最后关闭文件，与读取不同的是，写入文件会进行更多的工作和IO

在遍历打开文件后，还需要以下操作

写入新文件时，每次操作不仅要将数据写入磁盘，还必须首先决定将那个块分配给文件，从而相应的更新数据位图和inode，（已存在文件不需要分配）

因此每次写入文件逻辑上还会导致5个IO操作

1. 读取数据位图(然后更新以标记分配的块被使用)
2. 写入位图(将它的新状态存入磁盘)
3. 读取inode号，写inode号，用于更新块的位置
4. 写入真正的数据块本身

创建文件时，文件系统不仅要分配一个inode,还要在包含新文件的目录中分配空间，一个读取inode位图，查找空闲，一个写入inode位图标记已使用，一个写入新的inode初始化它，一个写入目录数据（将文件的高级文件名称链接到indoe号)，以及一个读取目录indoe以便更新它,会进行大量的IO操作

7.6.6 缓存和缓冲

为了减少读写文件进行的IO操作，提升效率，多数文件系统使用系统内存来缓存重要块，然后使用LRU等策略来进行块淘汰保留

早期文件系统使用静态内存划分，在系统启动时进行分配，约占内存的10%,但是这种静态的内存划分可能会导致浪费，文件系统未使用完10%的内存，但是该内存不能重新用于其它用途导致浪费

现代系统使用动态划分，将虚拟内存页面与文件系统页面集成到统一的页面缓存中，实现在虚拟内存与文件系统直接更加灵活的进行内存分配，具体取决于在给定时间那种内存需要更多内存,实现内存的高效利用

通过引入缓存，在读取文件时只有第一次进行大量IO操作，后序访问将会命中缓存，从而提升性能

在写入文件时，缓存不会减少流量，数据写入磁盘才能持久化,因此出现了惰性写入策略，将写入进行缓存延迟一定时间后进行写入来提高效率，常见以下策略

1. 通过延迟写入，文件系统可以将一些更新编成一批batch,放入一组较小的IO中

   如创建文件时inode位图被更新，稍后在创建另一个文件又被更新，则文件系统会在第一次更新后延迟写入，从而节省一次IO

2. 通过将写入缓冲在内存中，系统可以调度后序的IO，从而提高性能

3. 一些写入通过延迟写入来避免

   如应用程序创建并删除文件，则将文件创建延迟写入磁盘可以完全避免写入

现代大多数文件系统将写入在内存中缓冲几秒在写入，但系统更新传递到磁盘前崩溃，数据会丢失，但是延迟写入提高了性能，这是一种折中的方案(耐用性/性能权限)，操作系统也提供fsync()立即写入调用，绕过缓存直接写入磁盘，某些程序(如数据库)会使用立即写入保证数据不丢失,或者直接使用原始磁盘接口完全避免使用文件系统

7.7 局部性和快速文件系统

unix操作系统的第一个文件系统，简称老unix文件系统，其实现非常简单，它的数据结构在磁盘上十分简单，只包含以下部分：

• 超级块(包含整个文件系统的信息，卷的大小，inode数量，指向空闲列表的块的头部指针等)
• inode区域（包含文件系统的所有inode）
• 数据区域（数据块占用）

该文件系统首先简单，提供了实现文件系统基本的抽象(文件和目录层次结构)，但由于将磁盘当随机内存存取,数据遍布各处,数据定位成本较大，性能较差，并且没有对空闲空间进行管理，会出现很多磁盘碎片。

由此引出了如何组织文件系统数据结构以提供高性能，以及在这些数据结构上如何进行分配，需要哪些分配策略，让文件系统拥有磁盘意识等问题

7.7.1 FFS快速文件系统

FFS思路是让文件系统的结构和分配策略具有磁盘意识,从而提高性能，通过保持与文件系统相同的接口，但改变内部实现，从而保持了与应用程序的兼容性(所有现代文件系统都遵循现有接口，实现兼容性，但为了提高性能和可靠性以及其它原因，改变其内部实现，这是一种很好的方法)

组织结构柱面组： 通过将一个大的极简文件系统，划分为多个结构类似的小分组

• FFS将磁盘划分为一些组，称为柱面组,现代文件系统称为块组(如ext2, ext3),这些分组是FFS改善性能的核心机制，通过在同一个组里放置2个文件，从而确保先后访问2个文件不会导致穿越磁盘的长时间寻道，因此FFS在每个组中分配文件和目录
• 出于可靠性要求，每个分组中都有超级块的副本(用于损坏恢复，一个损坏任然可以使用副本实现访问)，此外每个分组还需要记录该组的inode和数据块是否已被使用，因此每组还存在inode位图与数据块位图，用于记录是否被使用

位图是管理文件系统中可用空间的优秀方法，它可以很容易找到大块可用空间并将其分配给文件，尽量避免旧文件系统中空闲列表的碎片问题

策略文件和目录的分配： 如何实现文件和目录的合理分配的策略方法，分配核心相关的东西放一起,因此ffs需要决定什么是相关的并将其放置于同一组

• 目录的放置：FFS分配方法，找到分配数量最少的柱面组(用于跨组平衡目录)，和大量空闲的inode(用于保证随后能够分配一堆文件),并将目录数据和inode放在该分组(也可以使用其它策略如考虑空闲块的数量)
• 文件的位置：在ffs中，首先确保将文件数据分配到与其inode相同的分组，从而防止inode与数据之间的长时间寻道，其次将位于同一目录中的所有文件，放在它们所在目录的柱面组中，例如(/a/1, /a/2, /a/3, /b/4 , 1,2,3放在同一个目录a的柱面组中，4单独放在另一个目录b的柱面组中)

大文件分配策略： 在FFS中大文件分配使用不同的策略，因为大文件可能需要多个分组才能完全填满，这样的填充是不符合需要的，妨碍了随后的相关文件存放

• 大文件分配，FFS将大块文件的一定数量块分配到一个块组，之后将文件的下一个大块放在另一个分组中，然后文件的下一个大块放在另一个分组中依次类推

大块分配导致文件在磁盘上四处分散，破坏了顺序性，从而导致影响性能，但是如果大块足够大，主要时间还是在传输数据，而寻道时间相对较少，每次开销做更多工作，减少开销，实现摊销，(因此需要仔细选择块的大小),FFS基于inode本身的结构，前12个inode直接块与inode放在同一组中，每个后续的间接块以及它指向的所有块都放在不同分组，如块大小4kb,磁盘地址是32位，者意味着文件的1024个块4MB放在单独的组中，，唯一列外的是直接指针所指向的文件前的48KB

FSS其它的创新：

• 引入子块：避免文件碎片和浪费，每个子块512字节，使用子块分配，当大小到4kb时，在进行赋值分配给一个4kb的块，并进行缓冲写入避免复制时的额外IO
• 参数化：找出磁盘的特定性能参数，并根据它们来确定磁盘的交错布局，减少寻道等待
• 允许长文件名以及符号链接概念，并且增加了原子操作rename,用于重命名文件

FFS通过这些改进提高了可用性，让系统可用很重要

7.8 崩溃一致性FSCK和日志

文件系统数据结构必须持久化，数据必须保留在磁盘上，但是由于磁盘一次只能响应一个请求(以及使用缓存缓冲写入)，容易出现崩溃一致性问题，当数据更新到一半时，或者多个操作只完成了其中几次，此时操作系统崩溃或断电，就会导致数据丢失，不一致问题，如何保证崩溃一致性是文件系统需要解决的一个重要问题(保证数据更新的原子性)

7.8.1 常见崩溃时写入场景

会导致文件系数据结构不一致(如inode已分配，数据块未分配，以及其它情况)，数据丢失、读取垃圾数据、空间泄露(数据块被分配，没有指向的inode,该块永远不会被使用)

1. 只有数据块写入：数据在磁盘上，但是没有指向的inode，也没有表示已分配的位图，导致就写入就像未发生
2. 只有inode块写入：inode块指向了数据的地址，但是指向的数据块没有写入，如果此时该数据块地址可以会读取垃圾数据(该数据块的旧数据)
3. 只有更新后的数据块位图写入：数据块位图被分配，没有指向的inode,该块永远不会被使用，空间泄露，文件系统元数据不一致
4. inode位图和数据块位图写入：但没有写入数据，数据块存储的是垃圾数据(改地址的旧数据)，文件系统元数据一致
5. inode位图和数据块写入：但数据位图没写入,inode位图指向正确，数据块位图指向旧数据，文件系统元数据不一致
6. 数据块位图和数据块写入：但是inode位图没写入，inode和数据位图不一致，不知道属于那个文件，没有inode指向该块，文件系统元数据不一致

解决办法：

1. fsck文件系统检查程序(旧文件系统使用，对文件系统进行扫描修复，但当磁盘越来越大时不适用，修复某几个错误需要扫描整个磁盘，效率太低)

2. 日志记录(也叫预写日志，每次写入时进行日志记录，崩溃时可以快速从日志恢复)

7.8.2 fsck文件系统检查

fsck文件检查修复思想，让崩溃发生，系统重启时进行磁盘扫描恢复(文件系统挂载并可用前运行，保证运行时没其它干扰)，详细流程如下

1. 检查超级块，检查超级块结构是否健全，如确保文件系统大小大于分配的块数，用于找出冲突超级块，找到时可以使用超级块副本恢复

2. 检查空闲块,以了解当前文件系统中分配的块，利用这些知识生成正确版本的分配位图，如确保所有像在使用的inode,都在inode位图中标记

3. 检查inode状态,检查每个inode是否存在损坏或其它问题，如确保每个分配的inode具有有效字段(文件/目录/符号链接等)，若存在可疑且不易修复，删除该inode并更新该inode位图

4. 检查inode链接,从根目录扫描整个目录树，并为每个文件和目录生成自己的链接数，如果生成的与原来的不匹配，使用新计算的进行修复，如果发现已分配没有目录引用，将其移动到lost+found目录

5. 检查重复,检查重复指针，2个不同的inode引用同一个块的情况，不好的可以被删除或者复制指向的块，根据需要为每个inode提供自己的副本

6. 检查坏块，扫描所有指针列表时还会检查坏块指针，如指针指向超出其有效范围的指针会被认为是坏块，从inode或间接块中删除该指针

7. 检查目录,对每个目录进行完整性检查，确保存在.,..目录，且目录条目中应用的每个inode都已分配，整个层次结构中没有目录的引用没超过一次

fsck文件系统检查程序一般在旧文件系统使用，对文件系统进行扫描修复，但当磁盘越来越大时不适用，修复某几个错误需要扫描整个磁盘，效率太低

7.8.3 日志(预写日志)

对于一致性更新问题，从数据库管理系统得到启发，这种方式成为预写日志，一般称为日志，常见日志文件系统ext3/ext4/jfs/xfs/ntfs

日志更新的基本思路：

• 更新磁盘时，在覆写结构之前，在某个地方记录下要做的所有操作(这就是预写)，将这些预写部分写入一个结构并进行组织起来就是预写日志
• 在进行磁盘数据更新(覆写)操作发生崩溃时，能够返回查看记录的预写日志，按照日志进行重新尝试，不必扫描整个磁盘，只需要查看预写日志

当前日志方式主要有以下2种：

1. 数据日志： 记录日志时将用户数据也进行记录(记录用户数据性能开销较大，会将用户数据写入2次，一次磁盘，一次日志)，基本协议流程如下
2. 日志写入： 将事务的内(包括TxB和更新内容)写入日志，等待这些写入完成
3. 日志提交： 将事务提交块(包括TxE)写入日志，等待写入完成，事务被认为已提交
4. 加检查点： 将更新内容写入其最终的磁盘位置
5. 释放： 稍后在日志超级块中将事务标记为空闲(避免日志过大，使日志有限，循环使用该数据结构，标记为空闲事务的空间可重新复用)
6. 元数据日志(有序日志)： 记录日志时除不记录用户数据记录，其它与数据日志一致(不记录用户数据提升了性能),基本协议如下
7. 数据写入: 将数据写入最终位置，等待完成(等待选) 通过强制先写入数据，文件系统可以保证指针永远不会执行垃圾
8. 日志元数据写入： 将开始块与元数据写入日志，等待写入完成
9. 日志提交： 将事务提交块(包括TxE)写入日志，等待写入完成，事务被认为已提交(包括数据)
10. 加检查点元数据： 将元数据更新的内容写入文件系统中的最终位置
11. 释放： 稍后在日志超级块中将事务标记为空闲

先写入被指对象(数据)，在写入指针对象，该规则是崩溃一致性的核心，在很多方案中被进一步利用

在元数据日志中，在发出写入日志(步骤2)之前强制数据写入完成(步骤1)，不是必须的，可以发出数据写入并向日志写入开始块与元数据，唯一必须保证的是在发出日志提交前**必须完成步骤1、2、3**

在NTFS/XFS中都使用了无序的元数据日志(可以随时写入数据),ext3提供了多种模式供选择(数据、元数据有序、无序等模式),所有这些模式都保持元数据一致，它们的数据语义各不相同

7.8.4 日志的优化

1. 块的复用(元数据日志存在该问题)： 为了避免文件删除后新文件复用了该块(只更新了元数据),导致崩溃发生恢复时，将旧的数据恢复到该块覆盖了当前的用户数据，常见方法如下

• 永远不再重复使用块，直到所述的块删除加上检查点，从日志中清除
• ext3中使用撤销记录进行标记，删除目录会进行撤销标记并写入日志，崩溃重放日志时先扫描带有撤销记录的日志，这样的日志不会被重放，避免了旧数据覆盖当前数据

2. 批处理更新优化： 为了减少磁盘开销，一般文件系统不会一次一个向磁盘提交每个更新，而是将所有更新缓冲到一个全局事务中，全局事务包含多个单个更新事务，写入磁盘时进行在进行批量更新

3. 日志写入优化： 写入日志时效率比较低下，文件系统必须写出事务开始块和事务内容这些写入完成后，才能将事务结束块发送给磁盘，影响性能造成磁盘额外的旋转，可以将事务写入日志时在开始和结束块中包含日志内容的校验和，这样文件系统可以理解写入整个事务，而不需等待，在恢复期间，文件系统检查计计算的校验和与事务中存储的校验和不匹配可以确定在事务写入过程过程中发生了崩溃，从而丢弃文件系统更新(保证了事务记录的数据也是正确的)，ext4中使用了该方法

磁盘保证每个512字节的写入是完整的，文件系统分2步发出事务写入，为确保TxE是原子的，因该使它成为一个512字节的块(分2步进行事务写入是为了避免一步事务写入时发生崩溃，导致记录的事务不完整问题)

7.8.5 恢复

1. 崩溃发生在事务安全写入日志之前，跳过待执行的更新
2. 崩溃发生在事务日志已安全写入，检查点完成之前(数据写入之前)，文件系统按如下方式恢复

• 系统引导时，文件系扫描日志，查找已提交到磁盘的事务
• 按顺序重放这些事务，文件系统尝试将事务中的块写入它们最终的磁盘位置(也称重做日志)

一些其它的方法：

软更新、写时复制、基于反向指针的一致性、乐观崩溃一致性

最常用的还是有序元数据日志，既可以减少日志流量又可以保证文件系统元数据与用户数据一致性

7.9 日志结构文件系统

LFS日志结构文件系统，通过引入一种新的磁盘更新方法，LFS总是写入磁盘的未使用部分，然后通过清理回收旧空间，而不是在原来的位置覆盖文件，这种方法在数据库系统中称为影子分页，在文件系统中有时称写时复制，可以实现高效写入，因为LFS可以将所有的更新收集到内存段中，然后按顺序一起写入

LFS文件系统磁盘一般结构：检查点区域CR——imap(inode映射块包含indoe地址)——indode指向的文件和目录——数据块，比传统文件系统多了imap查找

LFS核心机制如下，主要提高了磁盘的写入性能(因为随着内存的增大，读取一般在内存缓存读取，但是写还是需要存储到磁盘)

1. 缓冲写入： 通过他实现了顺序高效写入，写入磁盘时，先将所有更新包括元数据缓存在内存段中(固定大小，通常较大),当段满时将该段一次性写入到磁盘的未使用部分，只要段够大写入就很高效(因为可以减少磁盘旋转，寻道的时间，更多用于写入)
2. 空闲写入： LFS永远不覆写现有数据，始终将数据写入磁盘未使用部分，因为按缓冲的内存段写入(通常较大)，磁盘写入性能高，文件系统性能接近其峰值
3. 缓存落盘： 内存段缓存多少次数据更新就写入磁盘，取决于磁盘本身性能(一般以接近磁盘的写入速率峰值为好)
4. inode映射： 使用inode映射解决inode查找问题(因为inode分布整个磁盘，最新的inode并不断更新，因为不会覆盖),引入imap的数据结构，在inode号与inode之间使用了一个间接层，imap存储最新的inode号以及地址，查找时，在imap中输入inode号，返回inode地址，通过inode地址在查找到数据地址，imap也需要持久化到磁盘，LFS将其存放在写入其它信息的旁边，如新数据写入时，LFS将新数据块、inode、inode映射一起写入磁盘，他们相互紧挨着
5. 检查点区域： LFS通过在磁盘上固定一个位置(检查点区域),该区域包含指向最新的inode映射片段指针(地址),因此查找时通过首先读取该区域获得inode映射imap,该区域仅定期更新，性能不会受到影响
6. 目录存储方式与文件一致： 目录也存在imap映射，通过该imap找到目录inode,在通过inode找到目录，通过目录的目录项找到目录存储文件的inode号，然后通过inode号在imap中找到inode地址，最后通过indoe地址查询到文件数据，通过它间接解决了递归更新问题(任何不会原地更新的文件系统都会遇到该问题，它们将更新移动到新位置，如果不小心导致目录也更新，就必须更改目录的父目录一直递归到根)，LFS中imap更新时，目录保持相同的名称到indoe号的映射
7. 垃圾收集： 因每次不覆盖在新的空闲处写入，同一数据会在磁盘上存在多份，而此时的就旧版本数据就是垃圾数据需要清理，LFS中使用定期清理只保存文件最新的版本，清理时按段大小清理，减少了空闲空洞，因为写入是按段大小写入，清理原理是定期读取许多旧的段，确定哪些块在段中存在，开辟一组新的段，将旧段中活的块放入新段，释放旧的段，需要解决块的死活判断，清理多久运行一次2个问题
8. 块死活确定： LFS通过在每个段添加每个数据块和inode号它们属于那个文件以及其偏移量，该信息记录在位于段头部的段摘要块中，通过该方式获取到数据块的地址与通过imap中获取到的地址想对比，如果不一致证明是死块，因为imap存的是最新的活块，此外还可以通过版本号实现判断，当文件被删除截断时增加其版本号，并在imap中记录最新版本号，通过磁盘上段中记录的版本号与imap版本号对比，即可知道是否活块，减少了查询地址步骤提高了效率，LFS就使用了版本号
9. 清理策略： 周期性、空闲时间、磁盘已满时这几个时期都会开始进行清理，最早的方法为优先清理冷段，延迟清理热段(冷段，内容相对稳定可能存在死块，热段，经常覆盖内容的段)
10. 崩溃恢复： 使用时间戳机制保障检查点区域以原子方式更新，更新时，先写时间戳——在写CR检查点区域——最后在写时间戳，在CR更新时崩溃2边的时间戳就会不一致，LFS可以通过检查只使用具有一致时间戳的最新CR，实现CR的一致更新，且由于CR按周期每隔30s更新，崩溃恢复数据会丢失最后的30S数据，LFS使用回滚技术重建段，从最后一个检查点区域开始找到日志结尾，使用它读取下一个段，并查看其中是否存在有效更新，存在LFS会相应的更新文件系统，从而恢复自上一个检查点以来写入的大部分数据和元数据

7.10 数据完整性和保护

鉴于存储设备的不可靠性，文件系统或存储系统如何保证数据的完整性也十分重要

7.10.1 常见的磁盘故障解决办法

• 整个磁盘故障： 磁盘停止服务，该故障比较容易检测可以使用冗余备份的磁盘恢复，如raid技术
• 磁盘扇区错误： 磁盘正常工作存在部分扇区块错误，该故障也比较容易检测，读取该扇区返回错误时，使用冗余备份数据即可，如raid
• 讹误错误： 磁盘扇区块都正常工作，但是返回的数据是错误的(无声错误不容易检测)，使用校验和方法解决(磁盘记录时同时计算数据的校验和一起保存，读取时在计算当前数据校验和与之比较，不匹配说明数据不对，返回错误)
• 错误写入： 磁盘正常工作数据正常写入，但是写入位置不对,使用校验和+物理标识符方法解决(存储数据时包含校验和与磁盘号、扇区偏移量，读取时进行对比)
• 丢失写入： 数据并没有真正的写入到磁盘，1.使用写入后立即读回保证数据写入了(该方法效率较低，磁盘IO开销较大)，2.使用在inode与间接块也包含文件中每个块的校验和(这样即使数据丢失inode中校验和也不会与旧数据匹配，除非数据与inode的写入同时丢失，该可能性很小，ZFS文件系统使用该方案)

7.10.2 常见校验和函数

1. 基于XOR运算的校验和： 计算实现简单，但是每个校验和单元内相同位置的两个位发生变化，则校验和检测不出讹误(一般不使用)
2. 二进制补码加法： 在每个数据块上进行二进制补码加法忽略溢出，优点快速简单，但是如果数据移位则不好(一般不使用)
3. Fletcher校验和： 校验效果与循环冗余校验CRC几乎一致，可以检测所有单、双比特错误，大部分突发错误（原理，涉及2个校验字节的S1,S2的计算，假设块D由字节d1,d2,d3...dn组成， S1 = S1 + dn mod 255在所有dn上计算 S2 = S2 + S1 mod 255同样在所有dn上）
4. 循环冗余校验CRC： 将数据视为一个整块大的二进制数，并将其除以约定的值K得到校验和(使用广泛，计算机技术中多处使用，如计算机网中)

虽然校验和方法很好，但是无论什么校验和方法，都有可能存在碰撞问题(哈希碰撞，不同的数据生成相同的校验和，只能尽量减少无法避免)

7.10.3 校验和布局

校验和在磁盘中的布局常见两种方式

• 紧挨数据： 在每个数据块的旁边存放自己的校验和(不通用需要磁盘驱动器支持，更新时每个扇区一个校验和只需要执行一次写操作)
• 单独存放： 将n个校验和一起存放在一个扇区，后跟n个数据块，接着是后n块的另一个校验和扇区，依次类推(通用所有磁盘都支持，但是效率较低，更新时需要一次读取，2次写入)

磁盘擦净： 定期读取系统的每个块检查校验和是否任然有效，减少某个数据项所有副本都被破坏的可能性，一般系统每晚或每周安排扫描

校验和的开销： 磁盘开销(需要多余的空间存放校验和)，内存开销(查找时临时存放内存)，CPU计算开销(读取，存放都需要计算校验和并比较)，其它IO开销(如不同的校验和磁盘布局，磁盘擦净时间)

7.11 分布式系统

分布式系统关键：如何构建在组件故障时仍能工作的系统(如何处理在故障时仍然持续可用)

通信本身是不可靠的，在分布式系统中必须考虑能够应对数据包丢失的技术

分布式系统的关键要点：

• 通信：如何保证通信的可靠性(校验和，ACK确认，超时重试机制，每个消息只接收一次避免重传消息重复，如TCP可靠通信，网络层的抽象TCP/IP)
• 系统性能：如何实现低延迟，高带宽，系统性能最大化
• 安全：如何保证远程节点是需要连接的结点，如何确保第三方无法监听改变正在进行的通信

7.11.1 远程过程调用RPC

使在远程机器上执行代码的过程像调用本地函数一样简单直接，通常包含存根生成器也叫协议编译器、运行时库两部分

存根生成器协议编译器： 通过自动化，消除将函数参数和结果打包成消息的一些痛苦，对于客户端生成客户端存根，其中包含接口指定的每个函数，希望使用此RPC服务的客户端程序将链接此客户端存根，调用它进行RPC，调用时对于客户端代码是透明的，只是作为函数调用出现(如 func(xx)),但调用后客户端存根RPC在内部会执行以下步骤

客户端

• 创建消息缓冲区：通常只是某种大小的连续字节数组
• 将所需信息打包到缓冲区中：信息包括要调用的函数名称，所需要的参数，有时这步也称为参数的封送处理或消息的者序列化
• 将消息发送到目标RPC服务器：与RPC服务器的通信，使其正常运行的所有细节都由RPC运行时库处理
• 等待回复：因为一般函数调用是同步的，因此调用将等待其完成
• 解包返回代码和其它参数：将调用返回的数据进行解封送处理，也称反序列化
• 返回调用者：从客户端存根返回到客户端代码

服务端：

• 解包消息：收到客户端RPC调用请求后，对消息进行反序列化，提取出函数名称和参数
• 调用实际函数：在服务器上实际运行指定的函数传入指定的参数
• 打包结果：返回函数执行返回数据，进行消息序列化放入缓冲区
• 发送回复：将函数返回结果返回给调用者

运行时库： 处理RPC系统中大部分工作，处理RPC性能和可靠性问题，其需要处理的问题如下

• 如何找到远程服务：常见IP+端口
• RPC的传输级协议：使用TCP(可靠性能较低)还是UDP(不可靠性能高，RPC自己实现可靠性保证如超时/重试和确认等)
• 支持客户端询问：经过一段时间后客户端可以定期询问服务器是否仍在处理，服务器给出回复
• 大参数分组处理：大参数(大于可以放入的单个数据包)的分组发送，如TCP提供的分组发送组装，若没有提供RPC需要自己实现
• 字节序：有的机器存储使用大端序(高位在前低位在后如921)，有的使用小端序(低位在前高位在后如129)，需要处理如何与不同字节序的机器通信，通常在消息中使用明确定义的字节序进行解决
• 端到端的检查：可以保证数据的完整性，一般使用校验和比较
• 异步的支持：一般RPC为同步，可以支持异步提高利用率

7.12 NFS网络文件系统

基本分布式文件系统： 简单的客户端服务器分布式文件系统，包含客户端文件系统与文件服务器端个部分

通过客户端文件系统,实现了客户端用户程序的透明性，客户端文件系统对用户程序提供通用的文件系统调用，就像使用普通本地磁盘一样，通过客户端文件系统将这些系统调用转换成网络访问与文件服务器进行访问,他们的体系结构如下

// 通过网络进行访问文件
客户端应用程序               
客户端文件系统      --->         文件服务器   <---> 磁盘
网络		  	    <--->	         网络	

分布式文件系统需要处理的问题，如何保证在不可靠的服务器上保证可靠，不可靠原因如下

1. 服务器崩溃(停电，bug,内存泄露)
2. 网络问题(客户端服务端都正常运行，但是网络不能通信，看起来就像是远程主机崩溃)

NFS文件系统，此处为NFSV2协议

NFS文件系统是一种开放的文件协议，定义了客户端服务端用于通信的确切消息格式，按这些协议格式可以实现自己的NFS文件系统，该协议的主要目标是简单快速的实现服务器崩溃恢复，该技术的关键是无状态，通过无状态NFS实现了简单快速的恢复

快速恢复关键：无状态每次请求都是一个完整独立的请求，崩溃恢复时服务器只需要再次运行或者客户端进行重试请求即可

NFSV2通过设计无状态协议，服务器不会追踪每个客户端发生的事情，在每个协议请求中提供所有需要的信息以完成该请求

有状态的缺点：

1. 共享状态使服务器崩溃恢复变得困难，如服务器崩溃恢复后没法恢复崩溃前的使用状态(要实现恢复比较困难导致结构复杂)

2. 客户端崩溃的情况，打开文件后客户端崩溃，永远不会执行close,服务器打开文件无法关闭感知不到客户端已经崩溃

文件句柄： 在NFSV2中，文件句柄用于唯一地描述文件或目录，其通过卷标标识符、inode号、世代号三个组件一起构成客户端希望访问文件或目录的唯一标识符，卷标识符用于标识请求指向那个文件系统，inode号标识请求访问分区中的那个文件，世代号用于复用inode号时区分复用文件与旧文件(inode号复用时会递增世代号，确保具有旧文件句柄的客户端不会访问到新分配的文件)

在NFSV2中， 最重要的是首先使用LOOKUP协议消息用于获取文件句柄，然后用于访问文件数据，客户端通过该协议传递目录文件句柄和要查找的文件的名称，服务端返回该文件的局部及其属性(文件元信息，stat调用返回的那些信息)，此后通过文件句柄，客户端对文件发出READ/WRITE协议消息进行文件读写，该协议消息要求客户端发送文件句柄，文件中的偏移量，要读取的字节数等信息,服务器收到后进行读写，根据文件句柄，偏移量等信息进行本地磁盘的读取，并将读取结果返回给客户端，有错误时直接返回错误

从协议到分布式文件系统：

• 客户端文件系统追踪打开的文件：将应用程序的请求转换为相关的协议消息集
• 服务器只响应每个协议消息：每个协议消息都具有完成请求所需要的所有信息

利用幂等性操作处理服务器故障： 利用幂等性操作(操作执行多次与执行一次的效果相同)，请求出错故障时，只要进行重试就可(如网络丢包)，可以提升系统的可靠性，在NFSV2协议中，其利用大多数操作的幂等性，出现故障时都统一使用重试解决，发送请求后，客户端启动计时器设置为指定时间后关闭，在计时器关闭前收到回复则取消计时器一切正常，如果在收到任何回复之前计时器关闭，客户端正任务处理未完成，并进行重试重新发送请求，服务器回复则问题解决

在NFSV2中，LOOKUP、READ、WRITE(因为每次写都包含了偏移量与字节数，同样的操作多次重试结果都一直，因为每次操作都是重新覆写结果内容一致)都是幕等的，但MKDIR协议则不是(因为尝试创建已经存在的目录时，系统会通知创建失败，因此服务器收到mkdir协议并成功执行，但回复丢失，则客户端进行重试就会重复它返回错误，实际上第一次操作成功，只是在重试时失败了，该操作实现不了幂等性)

客户端与服务器进行通信可能出现的消息丢失情况

• 请求丢失：客户端发送请求丢失服务器未收到消息
• 服务器宕机：客户端发送请求服务器宕机不响应
• 服务器返回消息丢失：客户端发送请求服务器正常接收并处理回复，回复在途中丢失，客户端收不到回复

使用客户端缓存，避免所有的请求都通过网络，提高性能，NFS客户端文件系统缓存文件数据和元数据，因此只有第一次访问耗时，后序访问较快可以直接从客户端内存访问，此外缓存还用作写入的临时缓冲区，写入时先存入缓存，立即返回写入结果，稍后在将写入数据写入到远程文件服务器，提高性能(与本地文件系统的写入缓冲类似)

缓存一致性问题： 因为引入了缓存，如何保证缓存与当前数据的一致也要解决

• 更新可见性问题：来自一个客户端的更新，什么时候被其它客户端看见(因为更新缓存在本地还未写入远端，其它客户端看不见就会导致读取到旧数据)
• 陈旧的缓存：某个客户端已经将更新提交到了远端，但此时之前使用该文件的客户端由于该文件的本地缓存，而读取了过时的数据(更新已提交，但其它客户端还是使用的本地缓存旧数据)

NFSV2缓存一致性解决方案：

1. 更新可见性问题：实现关闭时刷新解决，应用程序写入文件并随后关闭时，客户端将所有更新(即缓存中的脏页)立即刷新到服务器，保证其它读取时为新数据
2. 陈旧缓存：客户端使用缓存时先进行文件改变检查，通过GETATTR协议请求获取文件的属性(元数据，包含上次修改文件的信息)，通过修改时间与本地缓存时间进行对比检查缓存是否过时，过时删除缓存后序读取转型服务器，缓存有效继续使用缓存(该方法存在问题，每次都需求发送GETATTR请求，存在大量该请求，NFSV2进行了优化，为每个客户端添加了一个属性缓存，检查时通过属性缓存查询文件属性，该缓存在一定时间后超时，如3s,在3s内，所有文件访问都从该缓存获取文件属性，判断缓存是否过期，并没有与服务器进行通信)

NFS服务器端缓存的处理：服务器的读取与客户端类似也使用内存将磁盘数据进行缓存，提高下次访问相同数据时的性能，但是在写入时没有使用缓存而是在返回写入成功之前使用强制性写入磁盘后才返回，避免数据发生丢失的情况(因为，缓存写入成功磁盘落盘失败，但是此时客户端已收到写入成功的响应，但实际磁盘数据并没有写入，因此要求强制等待写入磁盘成功才返回，但该等待也影响了性能)

7.13 AFS文件系统

AFS文件系统与NFS不同，该项目一开始就考虑可扩展性，其基本原则是在访问文件的客户端计算机的本地磁盘上进行全文件缓存，使读取在本地进行提升性能AFS存在v1、v2两个版本, v2是对v1的优化改进

AFS核心原则：

当open()文件时，将从服务器上获取整个文件(如果文件存在)并存储在本地磁盘中，后序文件read()/write()都使用在本地存储读取，不需要进行网络通信，速度快，在文件close()时文件(如果已被修改)被写回服务器

AFSV1协议：

1. Fetch:获取文件内容(在调用open()时向服务器发送该协议，会将所需文件的整个路径名传递给服务器，然后沿着路径名遍历查找文件并返回给客户端，客户端将文件缓存在本地)
2. Store:将文件存入服务器(客户端完成检查是否修改，如果被修改，使用Store协议将新版本刷写回服务器，将整个文件和路径名发送到服务器持久存储)
3. TestAuth：测试文件是否改变(使用改协议与服务通信验证本地缓存的有效性，再次访问文件时进行查询，修改重新向服务端获取，未修改使用本地缓存)
4. GetFileStat：取得文件的状态信息
5. SetFileStat：设置文件的状态信息
6. ListDir：列出目录的内容

AFSV1存在的问题：

• 路径查找成本过高： 执行Fetch与Store时传递整个路径名称，服务器查询时遍历才能访问具体文件，如/A/B/C, 要先找A,然后在A中找X，最后在B中找到C
• 客户端发出太多TestAuth： 每次访问时都需要发送该协议确认缓存是否可用，太多该消息影响服务器性能
• 服务器之间负载不均衡： 服务器对每个客户端使用一个不同的进程
• 上下文切换问题： 因为服务器使用不同进程对客户端进行响应，进程上下文切换开销大

AFSv2版本： v2版本引入新的方法，解决了v1存在的问题，使文件系统可用性更强

• 引入回调：通过回调服务器对客户端的承诺，当客户端缓存文件被修改时，服务器将通知客户端，减少了客户端与服务器的交互(解决v1中TestAuth问题)，它假定本地缓存有效，直到服务器另说为止
• 引入文件标识符FID：类似NFS文件句柄，用于替代路径名(解决v1中路径查找成本过高问题)查找指定文件，文件标识符包含卷标识符、文件标识符。全局唯一标识符(用于在删除文件时复用卷和文件id),如,访问/A/B/C, 客户端先获取A目录内容将他们放在本地缓存上并在目录A上设置回调，然后客户端获取目录B的内容并将它放在本地缓存上，在目录B上设置回调，最后获取到文件C并缓存在本地且设置回调，然后客户端将文件描述符返回给调用应用程序

AFS缓存一致性问题： 因为使用了回调和全文件缓存，解决比较简单

• 更新可见性：在AFS中，在不同计算机之间，AFS让更新在服务器上可见，并在同一时间是缓存的副本无效，即在更新的文件被关闭时(客户端打开文件修改关闭后，立即刷新到服务器，服务器更新后立即通过回调通知其它客户端原有缓存失效，需要重新从服务器获取该文件最新版本)
• 更新可见性本地进程列外处理：对于更新可见性，在同一机器的不同进程进行了例外处理，在这种情况下，对文件的写入对本地其它进程是立即可见的(不必等到文件关闭时，才能查看最新版本)，只有在不同机器时，需要等到服务器回调通知
• 最后写入者胜出：在不同机器上的进程同时修改某文件时，AFS只会采用最后写入者胜出的方法作为最终更新(多个进程同时修改同一文件，最后写入的作为最终结果更新到服务器)

AFS崩溃恢复：

• 客户端崩溃：客户端重新启动后，将本地所有缓存视为可疑，像服务端发送TestAuth协议验证本地缓存是否有效，无效重新从服务器获取，有效可继续使用
• 服务端崩溃：服务器崩溃恢复后必须要让所有客户端知道自己崩溃过，之前所有的本地缓存都不可信，需要重新验证(常用通知方法，1，服务器重新启动后向所有客户端告知自己崩溃重新启动，之前的本地缓存不可信需要重新验证，2，所有客户端利用心跳定期检查服务器是否存活)

AFS的其它改进： 使系统更易于使用和管理

• 提供了全局命名空间：确保所有文件在所有客户端计算机上以相同的方式命名(不同NFS，允许客户端以任意的名称挂载NFS服务器，除非人为统一规定)
• 提升了安全性：采用了一些机制要验证用户，还可以让一组文件保存私密
• 添加了访问控制功能：用户可以灵活的控制那些文件可以访问，那些不能

8. 虚拟机监视器

VMM虚拟机监视器，在操作系统下透明的虚拟化操作系统下的机器，为操作系统提供硬件的假象，实现操作系统下的机器硬件的复用，通过该虚拟化，在硬件与操作系统间架起中间层，实现在同一台机器上运行不同的操作系统，通过使用VMM虚拟机监视器，可以在同一套硬件上运行不同的操作系统，实现运行不同操作系统上的应用程序，方便测试和调试不同操作系统平台上的应用程序

8.1 虚拟化CPU

为了在虚拟机监视器上运行虚拟机(os及其应用程序)，使用的基本技术是受限直接执行(与操作系统的受限直接执行类似)，如果想在VMM上起动新操作系统，只需要跳转到第一条指令的地址，并让操作系统开始运行

在单个处理器上运行，并且希望在两个虚拟机之间进行多路复用(在两个操作系统和它们各自的应用程序之间进行多路复用)，VMM使用了类似操作系统进程间的切换的方式实现在不同操作系统间切换，切换时也需要保存操作系统的上下文(操作系统运行的整个机器状态，寄存器，特权硬件状态等)，恢复待运行的虚拟机的机器状态，然后跳转到待运行虚拟机的PC，则实现了切换，从而实现了CPU的虚拟化

VMM虚拟机监视器的系统调用机制：由于操作系统的系统调用是直接操作硬件，但是引入虚拟监视器后，操作系统是运行在虚拟监视器之上，因此不能直接操作硬件，而是通过VMM去间接的操作硬件，VMM中通过使用操作系统的陷阱机制从而间接的实现了运行在其之上的操作系统进行系统调用

引入VMM后系统调用机制如下： 此时的操作系统不能运行在内核模式下，它必须以该模式更少的特权模式运行，只能访问自己的数据结构，同时阻止从用户进程访问其数据结构

1. 虚拟机操作系统启动时设置陷阱表，试图安装自己的陷阱处理程序，因此陷入VMM中
2. VMM记录了OS的这些陷阱处理程序在内存中的位置
3. VMM从给定的操作系统上运行的用户进程接收到陷阱时，因为记录了陷阱程序的位置，它会跳转到操作系统陷阱处理程序，并让操作系统按原样处理系统调用
4. 系统调用完毕后，会执行某种特权指令从陷阱返回，然后回到VMM，VMM意识到操作系统正从陷阱返回，从而将控制返回给用户并让机器返回用户模式

经历完这一些列操作，就实现了一次完整的系统调用，中间只是多了VMM的转发，因为引入VMM，可能会减慢系统调用影响性能

8.2 虚拟化内存

VMM就像一个操作系统，安排不同的虚拟机运行，当特权级别发生变化时，交互方式也不一样，比如VMM如何虚拟化内存

每个操作系统通常直接将物理内存进行虚拟化自己和每个用户进程提供私有地址空间的假象，引入VMM中间层后，必须添加另一层虚拟层使物理内存虚拟化，以便多个操作系统可以共享机器的实际物理内存，且必须对操作系统透明(此时操作系统操作的物理内存其实是VMM对真实物理内存的虚拟化，但对操作系统透明，对其就像操作物理内存一样)，每个操作系统通过将其每个进程的页表映射到虚拟物理地址，VMM通过每个OS页面表将生成的虚拟物理地址映射到底层机器地址(真实的内存硬件物理地址)

整个转换流程

            操作系统页表                 VMM页表             
虚拟地址空间--------------> 虚拟物理内存------------->真实机器内存

引入VMM后TLB未命中处理流程：对每个正在运行的OS的物理内存，像OS有每个进程的页表一样，VMM必须跟踪它运行的每个虚拟机的物理内存到机器内存的映射

1. 从内存加载TLB未命中，陷入TLB未命中处理陷阱
2. VMM TLB为命中处理程序调用OS TLB处理程序(减少的特权)
3. OS TLB为未命中处理程序，查找页表更新TLB
4. OS非特权代码尝试更新TLB(特权操作)，陷入VMM，VMM将OS尝试安装VPN-FPN的映射转换为其所需的VPN-MFN机器内存映射，然后返回到OS
5. OS从陷阱返回
6. 陷入VMM(所有非特权代码尝试执行特权时，VMM都会得到通知并陷入VMM)，从陷阱返回
7. 继续执行(导致陷入指令的PC)指令重试，导致TLB命中

引入VMM后的TLB未命中处理程序变得比非虚拟化系统更耗时，因此Disco设计人员开发了一种VMM级别的软件TLB，其原理如下

• VMM记录它看到操作系统尝试安装的每个虚拟到物理的映射
• 在TLB为命中时，VMM首先查询其软件TLB以查看它是否已经看到此虚拟到物理映射，以及VMM所需的虚拟到机器的映射是啥
• 如果VMM在其软件TLB中找到转换，就将虚拟到机器的映射直接装入硬件TLB

信息沟

VMM通常不了解操作系统正在做什么或者想要什么，这种知识缺乏被称为VMM与OS之间的信息沟，可能会导致低效率(一个OS没有可以运行的程序时陷入空旋，另一个在运行用户进程，此时就会降低运行用户进程的OS效率，如果VMM知道的话就可以优化，为运行进程的OS提供更多的CPU时间)

半虚拟化： 运行修改后的操作系统，以便在VMM上运行，这被称为半虚拟化，因为VMM提供的不是完整的虚拟化，而是需要OS更改才能有效运行的部分虚拟化，一个设计合理的半虚拟化系统，只需要正确的OS更改，就可以接近没有VMM时的效率

按需置零： OS将物理帧映射到地址空间之前会将其置零，防止读取到旧数据，引入VMM后，VMM也需要将提供给每个操作系统的页面置零，因此很多时候页面被置零了两次，一次VMM分配给OS， 一次OS分配给其某个进程，Disco通过半虚拟化修改操作系统使OS不对页面置零，因为知道VMM已经置零，实现了减少一次操作

8.3 虚拟化总结

VMM使用的关键方法是扩展受限直接执行的概念，通过设置硬件，让VMM能够介入关键事件(如陷阱)，VMM可以完全控制机器资源的分配方式，同时保留操作系统所需的假象，对操作系统透明