操作系统导论-持久化
36.1系统架构
从下到上性能越来越高，成本越来越高，支持连接的设备数量越来越少。
36.2标准设备
一个标准设备包含两部分：
硬件接口：供系统软件控制它的操作，所有设备都有自己的特定接口以及典型交互协议。
内部结构：设备相关功能的特定实现，负责具体实现设备展示给系统的抽象接口。
状态寄存器：读取设备当前状态；命令寄存器：通知设备执行具体任务；数据寄存器：将数据传给设备/从设备接收数据。
协议：操作系统如何与设备进行交互
36.4利用中断减少CPU开销
如果设备非常快->轮询;如果设备比较慢->中断。
设备的速度未知使用混合（hybrid）策略，先尝试轮询一小段时间，如果设备没有完成操作，此时再使用中断。这种两阶段（two-phased）的办法可以实现两种方法的好处。
36.5利用DMA进行更高效的数据传送
使用 PIO的方式，CPU的时间会浪费在向设备传输数据或从设备传出数据的过程中。
DMA工作过程如下。OS通过编程告诉DMA引擎数据在内存的位置，要拷贝的大小以及要拷贝到那个设备。此后操作系统可以处理其它请求。当DMA的任务完成后，DMA控制器抛出一个中断来告诉OS已经完成数据传输。
36.6设备交互的方法
硬件如何与设备通信?
特权指令：采用明确的I/O指令，这些指令规定了操作系统将数据送到特定设备寄存器的方法。
内存映射I/O：硬件将设备寄存器作为内存地址提供。当需要访问设备寄存器时，操作系统装载(读取)或者存入(写入)到该内存地址；如何硬件会将装载/存入转移到设备上，而不是物理内存。
特权指令中的特权指OS是唯一可以直接与设备交互的实体。
内存映射I/O的好处是不需要引入新指令来实现设备交互。
36.7纳入OS：设备驱动程序
每个设备都有非常具体的接口，如何将它们纳入操作系统，我们希望操作系统尽可能通用。
关键问题：如何实现一个设备无关的操作系统 ？
如何保持操作系统的大部分与设备无关，从而对操作系统的主要子系统隐藏设备交互的细节？ 通过抽象进行解决。
在最底层，操作系统的一部分软件清楚地知道设备如何工作，我们将这部分软件称为设备驱动程序（device driver），所有设备交互的细节都封装在其中。
文件系统（当然也包括在其之上的应用程序）完全不清楚它使用的是什么类型的磁盘。它只需要简单地向通用块设备层发送读写请求即可，块设备层会将这些请求路由给对应的设备驱动，然后设备驱动来完成真正的底层操作。
这种封装也有不足的地方。例如，如果有一个设备可以提供很多特殊的功能，但为了兼容大多数操作系统它不得不提供一个通用的接口，这样就使得自身的特殊功能无法使用。
第37章I/O设备
关键问题：现代磁盘驱动器如何存储数据？接口是什么？数据是如何安排和访问的？磁盘调度如何提高性能？
37.1接口
驱动器由大量山区(512字节块)组测，磁盘可以视为一组扇区。
许多文件系统一次读取或写入4KB(或更多)，驱动器制造商唯一保证的是单个512字节的写入是原子的。
37.2基本几何形状
37.3简单的磁盘驱动器
磁盘完整的I/O时间图：寻道；盘片旋转；数据传输；
许多驱动器采用某种形式的磁道偏斜（track skew)，以确保即使在跨越磁道边界时，顺序读取也可以方便地服务。
扇区往往会偏移因为从一个磁道切换到另一个磁道时，磁盘需要时间来重新定位磁头（即便移到相邻磁道）。如果没有这种偏斜，磁头将移动到下一个磁道，但所需的下一个块已经旋转到磁头下，因此驱动器将不得不等待整个旋转延迟，才能访问下一个块。
后写：写入磁盘缓存后，回报写入完成。
直写：实际写入磁盘后，回报写入完成。
后写缓存有时会使驱动器看起来"更快"，但可能有危险。
37.4I/O时间
第38章廉价冗余磁盘阵列RAID
关键问题：我们如何构建一个大型、快速和可靠的存储系统？关键技术是什么？不同方法之间的折中是什么？
RAID使用多个磁盘一起构建更快、更大、更可靠的磁盘系统。
从外部看，RAID看起来像一个磁盘：一组可以读取或写入的块。
在内部，RAID由多个磁盘、内存（包括易失性和非易失性）以及一个或多个处理器来管理系统。
RAID的优点：
性能：并行使用多个磁盘可以大大加快 I/O时间。
容量：大型数据集需要大型磁盘。
可靠性：通过某种形式的冗余（redundancy），RAID可以容许损失一个磁盘并保持运行，就像没有错误一样。
透明性：RAID对于主机系统看起来就像一个大磁盘。
38.1接口和RAID内部
当文件系统向 RAID发出逻辑 I/O请求时，RAID内部必须计算要访问的磁盘（或多个磁盘）以完成请求，然后发出一个或多个物理 I/O来执行此操作。
在很高的层面上来看，RAID是一个非常专业的计算机系统：它有一个处理器，内存和磁盘。然而，它不是运行应用程序，而是运行专门用于操作 RAID的软件。
38.2故障模型
RAID旨在检测并从某些类型的磁盘故障中恢复。
38.3如何评估RAID
性能；可靠性；容量；
我们现在考虑 3个重要的 RAID设计：RAID 0级（条带化），RAID 1级（镜像）和 RAID 4/5级（基于奇偶校验的冗余）
38.4RAID0级：条带化
没有冗余，但可作为性能和容量的上限。
RAID阵列的大块大小(chunk size)为4KB
RAID阵列的大块大小(chunk size)为8KB
RAID映射问题
给定一个逻辑块来读或写，RAID如何确切地知道要访问哪个物理磁盘和偏移量？
对于块大小为8KB的情况：磁盘= A % 磁盘数 ；偏移量 = A / 磁盘数 ；
大块大小的tradeoff
chunk size较小的情况：文件将跨多个磁盘进行条带化，从而增加了对单个文件的读取和写入的并行性。但是，跨多个磁盘访问块的定位时间会增加，因为整个请求的定位时间由所有驱动器上请求的最大定位时间决定。
chunk size较大的情况：较大的大块大小减少了这种文件内的并行性，因此依靠多个并发请求来实现高吞吐量。但是，较大的大块大小减少了定位时间。
大多数RAID采用64KB大小的chunk
评估RAID的性能：考虑两种性能指标
单请求延迟：它可以揭示单个逻辑 I/O操作期间可以存在多少并行性。
RAID稳态吞吐量：即许多并发请求的总带宽。
单块请求的延迟与单个磁盘的延迟几乎相同；
稳态吞吐量对于顺序IO=N(磁盘数量)×S(单个磁盘的顺序带宽)；随机IO=N×R(单个磁盘的随机带宽)
38.5RAID1级：镜像
RAID1(镜像):需生成系统中每个块的多个副本。每个副本应该放在一个单独的磁盘上。这样，我们可以容许磁盘故障。
假设对于每个逻辑块，RAID保留两个物理副本。
读取可以选择一个进行读取，写入可以并行进行。
RAID-1分析
容量在镜像级别=2时，容量=N/2；从可靠性角度，表现良好。
性能：
单请求延迟：读取与单个磁盘上的延迟相同。写入时间大致等于单次写入时间，平均而言比写入单个磁盘略高。
稳态吞吐量：顺序写入N/2×S；顺序读N/2×S；随机读N×R；随机写N/2×R；
38.6RAID4级：通过奇偶校验节省空间
向磁盘阵列添加冗余(奇偶校验)，基于奇偶校验的方法试图使用较少的容量，从而克服由镜像系统付出的巨大空间损失。不过，这样做的代价是——性能。
奇偶校验=异或函数，如果有奇数个1，则返回1，否则返回0；
利用奇偶校验从故障中恢复：将数据位和奇偶校验位异或。
对于block，将block上的每一位按位执行XOR操作，将结果放入奇偶校验块的相应位置中。
RAID-4分析
容量：RAID-4使用 1个磁盘作为它所保护的每组磁盘的奇偶校验信息。因此，RAID组的有用容量是（N−1）。
可靠性：RAID-4容许 1个磁盘故障，不容许更多。如果丢失多个磁盘， 则无法重建丢失的数据。
性能：连续读取性能可以利用除奇偶校验磁盘以外的所有磁盘，因此可提供（N−1）×S（简单情况）的峰值有效带宽。
将大块数据写入磁盘时，RAID-4可以执行一种简单优化，称为全条带写入（full-stripe write）。在这种情况下，RAID可以简单地计算 P0的新值（通过在块 0、12和 3上执行 XOR），然后将所有块（包括奇偶块）并行写入上面的 5个磁盘。因此，全条带写入是 RAID-4写入磁盘的最有效方式。
顺序写入的性能：有效带宽(N-1)×S；随机读性能：(N-1)×R；
随机写入：随机写的复写，会导致奇偶校验块 P0将不再准确地反映条带的正确奇偶校验值。P0也必须更新。
加法奇偶校验：并行读取条带中所有其他数据块并与新块进行异或。生成新的校验块。接下来将新数据和新奇偶校验并行写入其各自的磁盘。(需要读取其它磁盘来计算奇偶校验)。
减法奇偶校验：
使用减法奇偶校验，每次随机写入RAID必须执行4次物理I/O(两次读和两次写入)。
现几乎同时向 RAID-4提交 2个小的请求，这些数据位于磁盘 0和 1上，因此对数据的读写操作可以并行进行，出现的问题是奇偶校验磁盘。这两个请求都必须读取 4和 13的奇偶校验块，即奇偶校验块1和 3。
在这种类型的工作负载下，奇偶校验磁盘是瓶颈。我们有时将它称为基于奇偶校验的 RAID的小写入问题（small-write problem）。 因此，即使可以并行访问数据磁盘，奇偶校验磁盘也不会实现任何并行。
奇偶校验磁盘必须为每个逻辑 I/O执行两次 I/O（一次读取，一次写入），其性能固定为R/2，添加磁盘也无法改善。
单请求延迟：单次写入的延迟需要两次读取，然后两次写入。读操作可以并行进行，写操作也是如此，因此总延迟大约是单个磁盘的两倍。
38.7 RAID5级：旋转奇偶校验
为解决小写入问题(部分解决)，
顺序读写性能(N-1)×S;随机读N×R；小写入总带宽N×R/4；
38.8RAID比较：总结
第39章文件和目录
39.3创建文件
通过open系统调用完成，调用open()并传入O_CREAT标志，程序可以创建一个新文件。O_TRUNC,将其截断为零字节大小，删除所有现有内容。
open()的一个重要方面是它的返回值：文件描述符（file descriptor）。
一个文件描述符就是一种权限/指向文件类型对象的指针
39.4读写文件
open();read(文件描述符,缓冲区,缓冲区大小);write(文件描述符,缓冲区,写入大小);
39.5读取和写入，但不按顺序
off_t lseek(int fildes, off_t offset, int whence); 第一个参数是熟悉的（一个文件描述符）。第二个参数是偏移量，它将文件偏移量定位到文件中的特定位置。
偏移量决定在文件中读取或写入时，下一次读取或写入开始的位置
第一种是当发生 N个字节的读或写时，N被添加到当前偏移。因此，每次读取或写入都会隐式更新偏移量。第二种是明确的lseek，它改变了上面指定的偏移量。
39.6用fsync()立即写入
当程序调用 write()时，它只是告诉文件系统：请在将来的某个时刻，将此数据写入持久存储。出于性能的原因，文件系统会将这些写入在内存中缓冲（buffer）一 段时间（例如 5s或 30s）。在稍后的时间点，写入将实际发送到存储设备。从调用应用程序的角度来看，写入似乎很快完成，并且只有在极少数情况下（例如，在 write()调用之后但写入磁盘之前，机器崩溃）数据会丢失。
提供给应用程序的接口被称为 fsync(int fd)。当进程针对特定文件描述符调fsync()时，文件系统通过强制将所有脏（dirty）数据（即尚未写入的）写入磁盘来响应，针对指定文件描述符引用的文件。一旦所有这些写入完成，fsync()例程就会返回。
39.7文件重命名
mv使用了系统调用 rename(char * old, char * new)，它只需要两个参数：文件的原来名称（old）和新名称（new）。
rename()调用是一个原子调用
39.8获取文件信息
文件系统会保存关于它存储的每个文件的metadata，可以使用stat();fstat()系统调用。通常保存在inode结构中。
39.9删除文件
使用unlink()系统调用，而不是remove/delete。
39.10创建目录
永远不能直接写入目录。因为目录的格式被视为文件系统元数据，所以只能间接更新目录，例如，通过在其中创建文件、目录或其他对象类型。
39.11读取目录
opendir(),readdir(),closedir()；
目录只有少量的信息（基本上，只是将名称映射到 inode号
39.12删除目录
删除目录可能会导致删除大量的数据，因此rmdir()要求该目录在删除之前是空的。
39.13硬链接
39.14符号链接
第41章局部性和快速文件系统
41.1问题：性能不佳
UNIX文件系统性能很糟糕，主要问题是老 UNIX文件系统将磁盘当成随机存取内存。数据遍布各处，而不考虑保存数据的介质是磁盘的事实，因此具有实实在在的、昂贵的定位成本。例如，文件的数据块通常离其 inode非常远，因此每当第一次读取 inode然后读取文件的数据块。
文件系统会变得非常碎片化，因为空闲空间没有得到精心管理。空闲列表最终会指向遍布磁盘的一堆块。
需要磁盘碎片化整理工具，将重新组织磁盘数据以连续放置文件，并为让空闲空间成为一个或几个连续的区域，移动数据，然后重写 inode等以反映变化。
41.2FFS：磁盘意识文件系统
思路是让文件系统的结构和分配策略具有“磁盘意识”，从而提高性能。
所有现代文件系统都遵循现有的接口（从而保持与应用程序的兼容性），同时为了性能、可靠性或其他原因，改变其内部实现。
41.3组织结构：柱面组
FFS将磁盘划分为一些分组，称为柱面组。
这些分组是 FFS用于改善性能的核心机制。通过在同一组中放置两个文件，FFS可以确保先后访问两个文件不会导致穿越磁盘的长时间寻道。
FFS需要能够在每个组中分配文件和目录。每个组看起来像这样
41.4策略：如何分配文件和目录
相关的东西放一起（无关的东西分开放）
目录的放置：找到分配数量少的柱面组（因为我们希望跨组平衡目录）和大量的自由 inode（因为我们希望随后能够分配一堆文件），并将目录数据和 inode放在该分组中。当然，这里可以使用其他推断方法（例如，考虑空闲数据块的数量）。
文件的放置：首先将文件的数据块分配到与其inode相同的组中，从而防止 inode和数据之间的长时间寻道。其次，它将位于同一目录中的所有文件，放在它们所在目录的柱面组中。
41.5测量文件的局部性
路径差异值：为了找到两个文件的共同祖先，必须在目录树上走多远。它们在树上越靠近，度量值越低。
可以看到大约 7%的文件访问是先前打开的文件，并且近 40%的文件访问是相同的文件或同一目录中的文件（即 0或 1的差异值）。因此，FFS的局部性假设似乎有意义（至少对于这些跟踪）。
41.6大文件例外
如果没有不同的规则，大文件将填满它首先放入的块组（也可能填满其他组）。以这种方式填充块组是不符合需要的，因为它妨碍了随后的“相关”文件放置在该块组内，因此可能破坏文件访问的局部性。
对于大文件，FFS执行以下操作。在将一定数量的块分配到第一个块组之后，FFS将文件的下一个“大”块（即第一个间接块指向的那些部分）放在另一个块组中（可能因为它的利用率低而选择）。
FFS采用了一种简单的方法，基于 inode本身的结构。前 12个直接块与 inode放在同一组中。每个后续的间接块，以及它指向的所有块都放在不同的组中。如果块大小为 4KB，磁盘地址是 32位，则此策略意味着文件的每 1024个块（4MB）放在单独的组中，唯一的例外是直接指针所指向的文件的前 48KB。
为了摊销成本，必须在寻道之间传输更多数据。
41.7关于FFS的其它几件事
容纳小文件可能会导致磁盘浪费，当时许多文件大小为2KB左右，块大小4KB。
为此引入了子块，子块大小为512Byte，文件系统可以将子块分配给文件。直到其达到完整的4KB数据。此时FFS找到应该4KB块，将其复制到其中，并释放子块以备将来使用。
这个过程效率低下，FFS通过修改libc库来避免这种异常行为，将缓冲写入，然后以4KB块的形式将它们发送到文件系统。
第二个巧妙方法是针对性能进行优化的磁盘布局。
FFS首先发出一个请求，读取块 0。当读取完成时，FFS向块 1发出读取，为时已晚：块 1已在磁头下方旋转，现在对块 1的读取将导致完全旋转。
在下一块经过磁头之前，FFS有足够的时间发出请求。实际上，FFS足够聪明，能够确定特定磁盘在布局时应跳过多少块，以避免额外的旋转。这种技术称为参数化。
现代磁盘在内部读取整个磁道并将其缓冲在内部磁盘缓存中。
FFS是允许长文件名的第一个文件系统之一，符号链接，原子rename()操作。
第42章崩溃一致性：FSCK和日志
系统可能在任何两次写入之间崩溃或断电，因此磁盘上状态可能仅部分地更新。崩溃后，系统启动并希望再次挂载文件系统（以便访问文件等）。鉴于崩溃可能发生在任意时间点，如何确保文件系统将磁盘上的映像保持在合理的状态？
FSCK，文件系统检查程序；预写日志journaling;
42.2FSCK文件系统检查程序
让不一致的事情发生，然后重启时查找这些不一致并修复它们。
这种方法无法解决所有问题，文件系统看起来是一致的，但是inode指向垃圾数据。
FSCK的基本总结。
超级块：fsck首先检查超级块是否合理，主要是进行健全性检查，例如确保文件系统大小大于分配的块数。通常，这些健全性检查的目的是找到一个可疑的（冲突的）超级块。在这种情况下，系统（或管理员）可以决定使用超级块的备用副本。
空闲块：fsck扫描 inode、间接块、双重间接块等，以了解当前在文件系统中分配的块。它利用这些知识生成正确版本的分配位图。因此，如果位图和inode之间存在任何不一致，则通过信任 inode内的信息来解决它。对所有 inode执行相同类型的检查，确保所有看起来像在用的 inode，都在 inode位图中有标记。
inode状态：检查每个 inode是否存在损坏或其他问题。例如，fsck确保每个分配的 inode具有有效的类型字段（即常规文件、目录、符号链接等）。如果 inode字段存在问题，不易修复，则 inode被认为是可疑的，并被 fsck清除，inode位图相应地更新。
inode链接：fsck还会验证每个已分配的 inode的链接数。你可能还记得，链接计数表示包含此特定文件的引用（即链接）的不同目录的数量。为了验证链接计数，fsck从根目录开始扫描整个目录树，并为文件系统中的每个文件和目录构建自己的链接计数。如果新计算的计数与 inode中找到的计数不匹配，则必须采取纠正措施，通常是修复 inode中的计数。如果发现已分配的 inode但没有目录引用它，则会将其移动到 lost + found目录。
重复：fsck还检查重复指针，即两个不同的 inode引用同一个块的情况。如果一个 inode明显不好，可能会被清除。或者，可以复制指向的块，从而根据需要为每个 inode提供其自己的副本。
坏块：在扫描所有指针列表时，还会检查坏块指针。如果指针显然指向超出其有 效范围的某个指针，则该指针被认为是“坏的”，例如，它的地址指向大于分区大小的块。在这种情况下，fsck不能做任何太聪明的事情。它只是从 inode或间接块中删除（清除）该指针。
目录检查：fsck不了解用户文件的内容。但是，目录包含由文件系统本身创建的特定格式的信息。因此，fsck对每个目录的内容执行额外的完整性检查，确保“.”和“..”是前面的条目，目录条目中引用的每个 inode都已分配，并确保整个层次结构中没有目录的引用超过一次。
根本问题：太慢了。
42.3日志(预写日志)
将更新的内容，先写入磁盘的一个指定区域(日志).
带有日志的ext3文件系统如下
数据日志
中间的 3个块只包含块本身的确切内容，这被称为物理日志（physical logging）。
在日志中放置更紧凑的更新逻辑，逻辑日志，
一旦这个事务安全地存在于磁盘上，我们就可以覆写文件系统中的旧结构了。这个过程称为加检查点（checkpointing）。如果写入成功完成，说明成功的加上了检查点。
在写入日志期间发生崩溃，当一次发出5个块的写入。
简单的方法是一次发出一个，等待每个完成再发出下一个。
通过写入屏障(wirte barrier)，当它完成时，能确保在屏障之前发出的写入，先于在屏障之后发出的写入到达磁盘。
可能会将垃圾快？？的内容复制导DB应该存在的位置上。
写入日志，必须先写出事务开始块和内容，这些写入完成后，文件系统才能将事务结束块发送到磁盘。磁盘会产生额外的旋转，对性能影响很明显。
为了避免一次发出5个块写入的问题，文件系统分两步发出事务写入。
日志写入；日志提交；加检查点；
恢复：如果崩溃发送在事务被安全地写入日志前，只需简单地跳过待执行的更新。
如果事务已提交到日志之后但在加检查点完成之前发生崩溃，文件系统恢复过程将扫描日志，并查找已提交到磁盘的事务。然后，这些事务被重放（replayed，按顺序），文件系统再次尝试将事务中的块写入它们最终的磁盘位置。
批处理日志
基本协议可能会增加大量额外的磁盘流量。
在同一目录中连续创建两个文件，称为 file1和 file2。要创建一个文件，必须更新许多磁盘上的结构，它们需要一遍又一遍的写入相同的块。
一些文件系统不会一次一个地向磁盘提交每个更新（例如，Linux ext3）。通过将所有更新缓冲到全局事务中。
文件系统只将内存中的 inode位图、文件的 inode、目录数据和目录 inode标记为脏，并将它们添加到块列表中，形成当前的事务。当最后应该将这些块写入磁盘时（例如，在超时 5s之后），会提交包含上述所有更新的单个全局事务。因此，通过缓冲更新，文件系统在许多情况下可以避免对磁盘的过多的写入流量。
使日志有限
日志满会导致两个问题：日志越大恢复时间越长，日志已满时不能向磁盘提交进一步的事务。采用循环数据结构。
元数据日志
对于每次写入磁盘，我们现在也要先写入日志，从而使写入流量加倍。
有序日志/元数据日志，用户数据不需写入日志，直接写入文件系统。
在将相关元数据写入磁盘日志前，先将数据块写入磁盘。
通过强制先写入数据，文件系统可以保证指针永远不会指向垃圾。这个“先写入被指对象，再写入指针对象”的规则是崩溃一致性的核心，
发出写入日志之前强制数据写入完成不是正确性所必需的。真正的要求是发出日志提交快之前完成数据写入和日志元数据写入。
42.4其它方法
软更新：软更新[GP94]的方法。这种方法仔细地对文件系统的所有写入排序，以确保磁盘上的结构永远不会处于不一致的状态。例如，通过先写入指向的数据块，再写入指向它的inode，可以确保 inode永远不会指向垃圾。
写时复制：这种技术永远不会覆写文件或目录。相反，它会对磁盘上以前未使用 的位置进行新的更新。在完成许多更新后，COW文件系统会翻转文件系统的根结构，以包含指向刚更新结构的指针。这样做可以使文件系统保持一致。
减少日志协议等待磁盘写入完成的次数的技术。这种新方法名为乐观崩溃一致性（optimistic crash consistency）
尽可能多地向磁盘发出写入，并利用事务校验和（transaction checksum）的一般形式，以及其他一些技术来检测不一致，如果出现不一致的话。
第43章日志结构文件系统
——To Be Continue
