[系统运维]《操作系统导论》吐血万字整理 - 附下载地址及思维导图

前言

我看的是这本，豆瓣9.4，很经典的教材书，在文章末尾我附上了网盘链接
这篇博客算是一个完整的读书笔记，我大概读了20天看完的，电子版做笔记很方便，推荐一波，很多课上没有讲到的知识在这本书里都详细阐释了

全书的思维导图

操作系统介绍

一个正在运行的程序会做：取址执行。从内存中获取指令，对其解码，执行。

操作系统主要利用一种通用的技术，我们称之为虚拟化(virtualization)。 也就是说，操作系统将物理(physical)资源(如处理器、内存或磁盘)转换为更通用、更强大且更易于使用的虚拟形式。

操作系统取得CPU，内存和磁盘等物理资源，并对它们进行虚拟化；处理与并发相关的麻烦事；持久化地存储文件，使文件长期安全。

虚拟化

4.抽象 进程

进程可以被简单地视为正在运行的程序。

进程的创建首先将代码和静态数据加载到内存中，创建和初始化栈，执行I/O设置相关的其他工作，操作系统就为程序的执行搭建好了舞台，最后需要启动程序。

一般来说进程可以在三个状态：运行，就绪，阻塞。

存储关于进程的信息的个体结构称为进程控制块(Process Control Block，PCB)，这是谈论包含每个进程信息的 C 结构的一种方式。

5.插叙：进程API

进程描述符(process identifier，PID)

1. fork（） 系统调用fork（）用于创建新进程
2. wait（） 调用wait（）延迟自己的进程进行
3. exec（） 给定可执行程序的名称(如 wc)及 需要的参数(如 p3.c)后，exec()会从可执行程序中加载代码和静态数据，并用它覆写自己的代码段(以及静态数据)，堆、栈及其他内存空间也会被重新初始化。这个命令并没有创建新进程，而是直接将当前的程序替换为不同的运行程序

6.机制：受限直接执行

关键问题：操作系统如何高效可控地虚拟化CPU

通过受限的直接执行可以让程序运行地尽可能快，直接在CPU上运行程序即可。当 OS 希望启动程序运行时，它会在进程列表中为其创建一个进程条目，为其分配一些内存，将程序代码(从磁盘)加载到内存中，找到入口点(main()函数或类似的)，跳转到那里，并开始运行用户的代码。

为了安全高效地进行上述的步骤，我们需要解决

1. 如果我们只运行一个程序，操作系统怎么能确保程序不做任何我们不希望它做的事，同时仍然高效地运行它?
2. 当我们运行一个进程时，操作系统如何让它停下来并切换到另一个进程，从而实现虚拟化 CPU 所需的时分共享?

第一个问题：

我们引入用户模式和内核模式，可以实现权限的管理，为了让有些用户模式可以访问内核，引入trap指令，该指令同时跳入内核并将特权级别提升到内核模式。

为了在操作系统发出从陷阱返回指令时能够正确返回，必须确保存储足够的调用者寄存器。

内核在启动时会设置陷阱表，来实现一些前置的“规定”，例如在出错时调用什么代码？根据需要配置的是哪个硬件，哪个硬件可以访问哪个不能随意访问？

第二个问题：

在进程中切换：一个进程在CPU中运行时，操作系统就没有运行，那么操作系统如何重新获得CPU控制权来实现进程间切换？两种方式：协作方式，非协作方式。

1. 协作方式：有些文件会进行yield系统调用
2. 非协作方式：使用时钟中断来让操作系统运行中断处理程序，操作系统会重新获得CPU控制权。在启动过程中，系统必须先开启启动时钟。

为了保存切换时的前后两个程序的内容，操作系统会执行一些底层汇编代码，来保存通用寄存器、程序计数器，以及当前正在运行的进程的内核栈指针，然后恢复寄存器、程序计数器，并切换内核栈，供即将运行的进程使用。

在这个例子中，进程A正在运行，然后被中断时钟中断。硬件保存它的寄存器(在内核栈中)，并进入内核(切换到内核模式)。在时钟中断处理程序中，操作系统决定从正在运行的进程 A 切换到进程 B。此时，它调用 switch()例程，该例程仔细保存当前寄存器的值(保存到 A 的进程结构)，恢复寄存器进程 B(从它的进程结构)，然后切换上下文(switch context)，具体来说是通过改变栈指针来使用 B 的内核栈(而不是 A 的)。最后，操作系统从陷阱返回，恢复 B 的寄存器并开始运行它。

7.进程调度：介绍

我们使用公平，响应时间和周转时间来比较不同的调度策略。响应时间是指任务首次运行的时间-任务到达的时间。周转时间指进程的完成时间-进程的到达时间。

基本的调度方法：

先进先出（FIFO，FCFS）可能遇到先到的任务运行很久，平均周转时间过长

最短任务优先（SJF，shortest job first）因为它是非抢占形式的，可能在运行一个很长时间的任务的时候到达运行时间短的任务，导致平均周转时间降低

最短完成时间优先（STCF，shortest time-to-completion first）在SJF中引入抢占机制，更短运行时间的可以抢占资源

轮转调度（RR，Round-Robin）在一个时间片内运行一个工作，然后在下一个时间片切换到队列中的下一个任务，反复执行，知道所有任务完成。响应时间很低，但是周转时间很高。

8.调度：多级反馈队列

多级反馈队列（MLFQ，multi-level feedback queue）：关注进程的一贯表现，然后区别对待。

• 规则 1:如果 A 的优先级 > B 的优先级，运行 A(不运行 B)。
• 规则 2:如果A的优先级 = B的优先级，轮转运行A和B。
• 规则 3:工作进入系统时，放在最高优先级(最上层队列)。
• 规则 4:一旦工作用完了其在某一层中的时间配额(无论中间主动放弃了多少次 CPU)，就降低其优先级(移入低一级队列)。
• 规则 5:经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。

9.调度：比例份额

彩票调度，步长调度；这两种方式都不能很好地适合 I/O;其中最难的票数分配问题并没有确定的解决方式

彩票调度：彩票数(ticket)代表了进程(或用户或其他)占有某个资源的份额。一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。通过不断定时地(比如，每个时间片)抽取彩票，彩票调度从概率上(但不是确定的)获得这种份额比例。

步长调度：步长调度也很简单。系统中的每个工作都有自己的步长，这个值与票数值成反比。在 上面的例子中，A、B、C 这 3 个工作的票数分别是 100、50 和 250，我们通过用一个大数分别除以他们的票数来获得每个进程的步长。每次进程运行后，我们会让它的计数器 [称为行程(pass)值] 增加它的步长，记录它的总体进展。

10.多处理器调度（高级）

13.抽象：地址空间

一个进程的地址空间包含运行的程序的所有内存状态。例如：程序代码；当程序在运行的时候，利用栈(stack)来保存当前的函数调用信息，分配空间给局部变量，传递参数和函数返回值。堆(heap)用于管理动态分配的、用户管理的内存（调用new获得的内存，静态初始化变量）。

虚拟内存系统负责为程序提供一 个巨大的、稀疏的、私有的地址空间的假象，其中保存了程序的所有指令和数据。操作系统在专门硬件的帮助下，通过每一个虚拟内存的索引，将其转换为物理地址，物理内存根据获得的物理地址但获取所需的信息。操作系统会同时对许多进程执行此操作，并且确保程序之间互相不会受到影响，也不会影响操作系统。

14.插叙：内存操作API

内存包括堆和栈两种形式，程序运行需要内存的分配和释放两个步骤，在哪一步出错都可能导致程序的崩溃。

一般来说，系统中实际存在两级内存管理：

第一级是由操作系统执行的内存管理，操作系统在进程运行时将内存交给进程，并在进程退出(或以其他方式结束)时将其回收。

第二级管理在每个进程中，例如在调用 malloc()和 free()时，在堆内管理。 即使你没有调用 free()(并因此泄露了堆中的内存)，操作系统也会在程序结束运行时，收回进程的所有内存(包括用于代码、栈，以及相关堆的内存页)。无论地址空间中堆的状态如何，操作系统都会在进程终止时收回所有这些页面，从而确保即使没有释放内存，也不会丢失内存。

15.机制：地址转换

在实现CPU虚拟化的时候，一般准则为受限直接访问（LDE）。LDE 背后的想法很简单：让程序运行的大部分指令直接访问硬件，只在一些关键点(如进程发起系统调用或发生时钟中断)由操作系统介入来确保“在正确时间， 正确的地点，做正确的事”。

为了实现高效的虚拟化，操作系统应该尽量让程序自己运行， 同时通过在关键点的及时介入(interposing)，来保持对硬件的控制。高效和控制是现代操作系统的两个主要目标。

将虚拟地址转换为物理地址，这正是所谓的地址转换(address translation)技术。

这种地址转换实现的方式是动态重定位，首先，CPU需要两个寄存器：基址寄存器，界限寄存器。

基址寄存器通过记录基址，当程序计数器（例如128）被设置后，硬件获取这个地址后，就加上基址寄存器里的值（例如是32kb：32768），最终得到实际的物理地址32896。

界限寄存器提供访问保护，当进程访问超过边界或者访问负的虚拟地址时，CPU就会触发异常。

基址寄存器配合界限寄存器的硬件结构是芯片中的（每个CPU一对），我们将CPU负责地址转换的部分称为内存管理单元（MMU）

除此之外，操作系统还需要记录哪些空闲内存没有使用，我们使用空闲列表（free list）来实现。

操作系统在内核模式下可以通过特权指令修改这两个寄存器。操作系统和硬件进行配合，实现了简单的虚拟内存。

操作系统介入的过程：

1. 创建进程时，为进程的地址空间找到内存空间（利用空闲列表标记空闲或已经使用）
2. 进程中之时，操作系统回收内存，更新空闲列表
3. 切换进程时，操作系统保存当前两个寄存器的值（保存在进程控制块PCB中）
4. 异常发生时，操作系统提供应急行动

重定位会发生内存资源浪费的情况，因为被界限寄存器保护起来的内存无法被其他进程访问，如果这个进程使用的内存很少，资源就浪费了，所以要引入分段的概念。

16.分段

分段可以更高效的虚拟内存，避免了地址空间中的逻辑段之间的内存浪费，而且算法实现很容易，可以实现代码共享的功能。

用15节里面的例子可能存在栈和堆之间的空间没有被使用却占用了大量内存的问题，将进程分为代码段，栈段，堆段，分别将之放到不同的物理内存上，，这样就避免了虚拟地址空间中未使用部分占用物理内存。

进行分段之后，仍然需要确认当前的地址引用的是哪个段，可以使用显式方式，用虚拟地址的开头几位来表示不同的段，例如前两位00，01，10，11分别对应代码段，栈段，堆段；有时也用一位来判断（堆，栈当作一位）

栈的处理方式特殊些，它的增长方式是反向的，段寄存器中有一个专门的字段记录是否反向增长。除此之外，各个段之间有时为了提高效率还要进行地址空间的共享，所以在段寄存器中又加入了保护信息，来判断代码段的权限。

加入保护信息后，界限寄存器功能需要升级，不仅需要检查虚拟地址是否越界，还需要检查特定访问是否允许。

分段执行之后，在物理内存中会存在很多较小的未分配内容的空间，这样会造成很大的资源浪费，虽然可以使用紧凑物理内存，最接近匹配，最坏匹配，首次匹配等等方法缩小这种资源浪费，但是无法完全解决这个问题，所以要引入分片。

17.空闲空间管理

基本策略：

1. 最优匹配：遍历整个空闲列表，找到最接近的空闲块
2. 最差匹配：遍历后找到最大的空闲块
3. 首次匹配：找到第一个足够大的块
4. 下次匹配：首次匹配的策略下加入指针，指向上次查找结束的位置，为了将空闲空间的查找操作分散在整个地址空间

离奇的策略：

1. 分离空闲列表：将一部分内存拿出来专门满足某种大小的请求，碎片就不会再成为问题了。这种方法省去了列表查找过程，特定大小的内存分配和释放都很快

2. 伙伴系统：将空闲空间递归的一分为二，知道刚好可以满足请求，这种方法优秀在内存释放时，直接向上合并就可以了。
   

18. 分页：介绍

将空间分割成固定长度的分片就是分页，相应地，我们把物理内存看成是定长槽块的阵列，叫作页帧(page frame)。

页表是一种数据结构，用于将虚拟地址映射到物理地址上。VPN为虚拟页号，PFN为物理帧号。

页表项中可能包含很多不同的位：例如有效位（标记当前物理内存是否可用），保护位（标记当前物理内存是否可读可写），存在位（当前页在物理存储器还是在磁盘），脏位，参考位等等。

页表会造成机器访问很慢（很多内存访问用来访问页表），内存浪费（内存大量存储页表）

19. 分页：快速地址转换（TLB）

对每次内存访问，硬件先检查 TLB，看看其中是否有期望的转换映射，如果有，就完成转换(很快)，不用访问页表(其中有全部的转换映射)。

TLB（地址转换旁路缓冲存储器）会将最近转换过的VPN记录在缓存中，由于软件存在两种局限性（时间局限性，空间局限性），所以软件大概率在一段时间内，访问相近的一段内存，所以TLB就可以大展身手了。然而缓存不能设计的太大，只有很小的TLB才可以实现快速的缓存。

正在运行的进程生成虚拟内存引用(用于获取指令 或访问数据)，在这种情况下，硬件将其转换为物理地址，再从内存中获取所需数据。

硬件首先从虚拟地址获得 VPN，检查 TLB 是否匹配(TLB 命中)，如果命中，则获得最终的物理地址并从内存中取回。这希望是常见情形，因为它很快(不需要额外的内存访问)。

如果在 TLB 中找不到 VPN(即 TLB 未命中)，则硬件在内存中查找页表(使用页表基址寄存器)，并使用 VPN 查找该页的页表项(PTE)作为索引。如果页有效且存在于物理内存中，则硬件从 PTE 中获得 PFN，将其插入 TLB，并重试该指令，这次产生 TLB 命中。

在上下文切换的时候，TLB还会遇到两个相同的虚拟地址对应不同的物理地址的情况，这时候不作区分就会乱套，TLB也不知道该怎么映射了。

简单的解决方法是切换进程的时候，将之前TLB的内容清零，但是也会出现很多次未命中的问题。所以一些系统增加了硬件支持，加入ASID地址空间标识符来作区分。

TLB满了之后会需要替换策略，可以使用简单的最近最少使用策略LRU（n+1个页被访问，大小只有n，LRU就乱套了），随机策略。

20. 分页：较小的表

页表总是占据极大的内存，简单的数据结构（基于数组）效率太低了。

多级页表能很好的解决问题，普通的线性表中存在很多无效空间，但是都分配了该页的页表，多级页表仅将两页标记为有效。

线性页表通常很大，线性表是按VPN索引的PTE数组，需要连续驻留在物理空间中；有了多级结构，我们增加了一个间接层 (level of indirection)，使用了页目录，它指向页表的各个部分。这种间接方式，让我们能够将页表页放在物理内存的任何地方。

多级页表的缺点在于，TLB未命中，就需要从内存加载两次，这样会造成时间的浪费（空间换时间的典型）；同时页表查找也会很复杂。

21. 超越物理内存：机制

为了支持更大的地址空间，操作系统需要把当前没有在用的那部分地址空间找个地方存储起来。一般来说，这个地方有一个特点，那就是比内存有更大的容量。增加交换空间让操作系统为多个并发运行的进程都提供巨大地址空间的假象。交换空间位于硬盘驱动器上，它比进入物理内存要慢。

硬件判断页是否在内存中的方法是通过页表的存在位，如果不存在，存在位为0，这时候会出现页错误。页错误通常由操作系统进行处理，操作系统通过PTE中的某些位来找到当前进程所对应的硬盘地址，然后发送请求给硬盘，将页读取到内存中。页表I/O完成后，操作系统会更新页表，这页就标记为存在，I/O运行中，操作系统仍然可以运行其他的进程

内存访问TLB未命中会遇到很多情况：

1. 该页存在且有效，TLB未命中页也可以从PTE中获取PFN，然后重试指令就可以命中了
2. 存在位为0，页错误处理程序运行
3. 访问页为无效页，硬件捕获这个非法访问，操作系统陷阱处理程序运行，可能会杀死程序

22. 超越物理内存：策略

当操作系统中的空闲内存不够时，出于内存压力操作系统必须要换出一些页为常用页留下空间，我们应该踢出哪个页？

问题：内存中只包含系统中所有页的子集，因此可以将其视为系统中虚拟内存页的缓存，我们的目标是在缓存选择替换策略时，让缓存命中更多，如何做？

因为内存访问的速度比磁盘访问速度快很多很多，所以即使是小概率的未命中也会严重影响效率。

最优策略

替换内存中在最远将来才会访问到的页。

虽然不切实际（我们无法预测未来），但是可以作为一个标准来和其他方法进行对比，

FIFO 先入先出 & Random 随机策略

先入先出虽然简单，但是因为根本无法确定页的重要性，即使经常使用的页也会将其踢出，所以命中率会很低

随机策略在内存满了的时候随机选择一个页进行替换，命中率全凭运气

这两种方法都有可能踢出重要的页，而这个页马上就又要被引用

LRU 利用历史数据

局部性原则：程序倾向于频繁地访问某些代码例如（循环）和数据结构（例如循环访问的数组）。

局限性：空间局限性，时间局限性

LRU方法就是找到最近使用最少的页将它踢出，但是这种方法很难实现，因为一台机器会有上百万页，如果遍历寻找，性能代价太大了

在局部性:80%的引用是访问 20%的页(“热门”页)。剩下的 20%是对剩余的 80%的页(“冷门”页)访问时，LRU会有更好的表现

这展示了缓存较小导致的FIFO和LRU在性能方面的瓶颈。

近似LRU

增加一个使用位的概念，当最近使用了这个页，硬件就会将当前页的使用位设置成1。

当必须进行页替换时，操作系统检查当前指向的页 P 的使用位是 1 还是 0。如果是 1，则意味着页面 P 最近被使用， 因此不适合被替换。然后，P 的使用位设置为 0，时钟指针递增到下一页(P + 1)。该算法一直持续到找到一个使用位为 0 的页，使用位为 0 意味着这个页最近没有被使用过(在最坏的情况下，所有的页都已经被使用了，那么就将所有页的使用位都设置为 0，周期性地清除使用位可以防止这个问题出现)。

clock算法不如完美的LRU，但是比无记忆的方法好多了

因为踢出一个已经被更改过的页需要将它重写回磁盘，这很昂贵，我们称这种页为脏页；但是如果没有被修改过，这就是干净的页，脏位就是为了记录这个页修改了么，每次写入页时都会设置此位，因此可以将其合并到页面替换算法中。例如，时钟算法可以被改变， 以扫描既未使用又干净的页先踢出。无法找到这种页时，再查找脏的未使用页面，等等。

当内存被超额请求，操作系统只能不停地换页才能满足需求，一般的解决方式就是杀死其中的内存密集型进程来控制内存请求。

23. VAX/VMS虚拟内存系统

VAX-11为每个进程提供了32位的虚拟地址空间，虚拟地址由23位VPN和9位偏移组成，VPN高两位勇于区分页所在的段。

代码不会访问第0页，这一页被设置为不可访问，以方便空指针的检测（对调试的支持）

并发

26.并发：介绍

多线程程序会有多个执行点（多个程序计数器，每个都用于取指令和执行），每个线程类似于独立的进程，但是线程之间共享地址空间，能够访问相同的数据

两个线程运行在同一个处理器上，进行线程切换时，我们将状态保存在线程控制块（Thread Control Block TCB），进程是保存在PCB中。然而线程之间的切换地址空间保持不变，不用切换当前使用的页表。

除此之外，进程线程另一个区别在栈，每个线程都有一个自己的栈

27. 插叙：线程API

好吧，我其实不咋喜欢看这种章，一堆代码😷，跳过了，以后再看。

28. 锁

锁出现的目的主要是为了解决希望实现并发编程的原子性的问题，在源代码中加锁，放在临界区周围，保证临界区能够像单条原子指令一样执行

锁就是一个变量，它有两种状态，可用与被占用，当线程发现锁是可用的，那么该线程获得锁，进入临界区，这时候其他线程会发现锁的状态是被占用的，所以无法进入临界区。

锁让又操作系统调用的混乱状态变得可控。

锁的评价标准有什么？

1. 能否有效

2. 公平性，线程之间对锁的竞争是否公平？是否有线程会一直竞争失败？

3. 性能，使用锁之后使用锁增加的开销如何？

使用最简单的关闭打开会出现的问题：

1. 有可能存在恶意程序滥用权利一直使用lock占据所有资源
2. 不支持多处理器，线程可以通过其他处理器进入临界区
3. unlock指令如果丢失，操作系统只能永久等待
4. 代码执行效率低

自旋锁（testAndSet实现）

自旋锁运行起来的效果就是，当前线程如果发现flag为0，就直接获得锁；如果发现flag为1，就循环等待，直到flag为0才会获得锁。

首先我们写一个testAndSet函数，函数功能为将目前的flag设置为返回值，将1设置为当前的flag值

在实际运行中会出现两种情况

第一种情况原本的old_ptr（flag值）为0，这时线程的old被设置为0并且返回，但是指针设置为1（告诉别的进程锁已经被占用了）

第二种情况原来的flag为1，程序在lock函数中循环while等待，知道testAndSet函数返回0，才可以获得锁，否则一直循环等待。

完整的代码：

另外，我们可以使用compare-and-swap比较并交换指令实现自旋锁，代码为：

代码表示检测ptr指针当前指向的值是否和expected相等，如果相等则更新指针的值为新值，否则无行动。无论如何都会返回当前的值，以告诉使用者程序在正常运行。

将compare-and-swap替换上问的lock函数，就可以实现自旋锁

自旋锁的评价：满足正确性，不提供任何公平性保证，单CPU情况下性能开销很大，多CPU下性能开销可以接受

使用fetch-and-add可以实现一种类似于排队的策略，每个线程拥有自己的ticket，当全局lock模块的turn等于某个线程的ticket时，这个线程获得lock，ticket锁实现如下：

如果线程希望获取锁，首先对一个 ticket 值执行一个原子的获取并相加指令。这个值作为该线程的“turn”(顺位，即 myturn)。根据全局共享的 lock->turn 变量，当某一个线程的(myturn == turn)时，则轮到这个线程进入临界区。unlock 则是增加 turn，从而下一个等待线程可以进入临界区。

虽然可以使用yield()在线程将要自旋的时候让出CPU进入就绪态，以节省CPU资源（只有两个线程的时候很好用！），但是这种方法仍然会造成资源浪费，因为如果锁一直在别的线程手中，等待线程就会一直运行，yield()让出，运行，yield()让出……

linux使用的是两阶段锁，第一阶段先自旋一段时间（实际中固定自旋的次数），希望可以获取锁，这一阶段如果没有获得锁，这个线程就会进入第二阶段：睡眠，直到锁可用

29.基于锁的并发数据结构

对于特定数据结构，如何加锁才能让该结构功能正确？

拿一个简单的计数器来举例，简单加锁之后的计数器性能相对于不加锁的来说，可扩展性极差，性能下降极大。

使用懒惰计数器可以解决问题，懒惰计数器的原理是利用全局计数器和局部计数器实现的，一个CPU配一个局部计数器，一个机器配一个全局计数器，不同CPU上的线程不会竞争，更新操作的可扩展性会好很多。

具体原理是以S为阈值更新，当某个局部变量到达了阈值就将数据同步给全局计数器，局部计数器清零。阈值越大，花费时间就越少，精确度也越低，所以需要做一个平衡的阈值。

30. 条件变量

多线程程序中，一个线程如何等待某些条件完成再执行？最简单的方法是写一个while自旋等待，但是这种方法效率很低

生产者/消费者方案

pthread_cond_t c;，这里声明c是一个条件变量(注意:还需要适当的初始化)。条件变量有两种相关操作:wait()和 signal()。线程要睡眠的时候，调用 wait()。当线程想唤醒等待在某个条件变量上的睡眠线程时，调用 signal()。

生产者线程等待条件变量 empty，发信号给变量 fill。相应地，消费者线程等待 fill，发信号 empty。这样做，从设计上避免了上述第二个问题:消费者再也不会唤醒消费者，生产者也不会唤醒生产者。

生产者只有在缓冲区满了的时候才会睡眠(p2)，消费者也只有在队列为空的时候睡眠(c2)

31.信号量

?

sem_wait : 将信号量s的值减1；如果信号量s的值为负，则等待

sem_post : 将信号量s的值加1；如果有一个或多个线程在等待，唤醒一个

二值信号量（锁）

就是锁的概念，用sem_post和sem_wait将临界区环绕起来，通过信号量来判断当前进程是等待还是运行

生产者/消费者（有界缓冲区）问题

在上一节中的有效方案中，如果缓冲区MAX的值大于1，那么就会有两个生产者同时调用put的情况，这种情况下，如果有一个生产者刚写入了数据，但是被中断了，还没来得及更新fill，那么新的生产者就会重写刚才的生产者的值，这就会造成数据丢失的问题。

使用二值信号量来加锁（代码中的sem_wait(&mutex)），将put和get操作的临界区保护起来，但是注意不能把锁的作用域放在刚才的有界缓冲区外面，否则会出现死锁的现象

因为只有插入操作才会影响结构，所以我们可以并发的执行多个查找操作，读者-写者锁就使用了这个思想。这个锁有一个缺点就是只有读者释放了锁，写者才可以进行写入，所以读者会多的情况下，写者可能会饿死。另外这种复杂的方法性能会比较差。

哲学家就餐问题

假定有 5 位“哲学家”围着一个圆桌。每两位哲学家 之间有一把餐叉(一共5把)。哲学家有时要思考一会，不需要餐叉;有时又要就餐。而一位哲学家只有同时拿到了左手边和右手边的两把餐叉，才能吃到东西。

如何实现 getforks()和 putforks()函数，保证没有死锁，没有哲学家饿死， 并且并发度更高(尽可能让更多哲学家同时吃东西)。

解决方法是其中四个哲学家都是用下面的方法

而最后一个哲学家使用这种方法

这样就解决了所有哲学家都拿起了左手的叉子形成死锁等待的问题

32. 常见并发问题

这章比较重要，单独画一个思维导图

非死锁缺陷

违反原子性：

举例来说，就是在线程1中通过了if条件，但是在使用if条件中的值时，线程2更改了if条件中的值，导致了空指针的引用。

确保每个proc_info字段都有自己的锁就可以解决问题

违反顺序缺陷：

举例来说，就是代码执行顺序和预期不符，可能存在某个变量没有被初始化就直接被引用了

解决方法就是使用信号量强行决定进程的运行顺序

死锁缺陷

当线程 1 持有锁 L1，正在等待另外一个锁 L2，而线程 2 持有锁 L2，却在等待锁 L1 释放时，死锁就产生了。

死锁的发生是很常见的，在模块化的方式编程情况下，很可能不相关的两个模块会相互影响

死锁产生的条件：

互斥：线程对于需要的资源进行互斥的访问(例如一个线程抢到锁)。

持有并等待：线程持有了资源(例如已将持有的锁)，同时又在等待其他资源(例如，需要获得的锁)。

非抢占：线程获得的资源(例如锁)，不能被抢占。

循环等待：线程之间存在一个环路，环路上每个线程都额外持有一个资源，而这个资源又是下一个线程要申请的。

死锁的预防：

针对循环等待，我们可以设计特定的获取锁的顺序，使用全序和偏序（全序表示所有锁都按规定顺序，偏序表示指定部分锁的顺序）

针对持有并等待，可以设计一个prevention锁，保证原子性地抢锁。这个方案的思路就是保证我们准确知道需要哪些锁，并且都提前抢到，这样才能实现。但是这也就降低了并发，因为拿到锁的时候并不是真正需要的时候

针对非抢占，可以设计一个trylock()函数，trylock函数会尝试去获得锁，或者返回-1，然后打开自己的锁，之后再去获得自己的锁，然后尝试这个过程

然而这样会遇到活锁的问题，如果两个进程共同重复这个过程，两个进程都去拿对方的锁失败，然后重复这个过程，解决方法也很简单，让一个进程等一会再执行就好了。

这种方法存在封装的问题，如果某些资源或者某些内存都已经被占用，但是仍然要返回之前的步骤，这种跳回操作就很难实现。

针对互斥，可能使用无等待数据结构的思想，通过硬件指令，不需要锁来实现。

另外，使用调度的方法也可以实现死锁的避免，例如合理地安排线程的运行，错开他们共同需要某个锁的时间，就可以避免死锁的发生（银行家算法）

最后还可以使用检查和恢复的方法处理死锁，最简单的方法：关机重启

33. 基于事件的并发（进阶）

使用单个 CPU 和基于事件的应用程序，并发程序中发现的问题不再存在。具体来说， 因为一次只处理一个事件，所以不需要获取或释放锁。基于事件的服务器不能被另一个线程中断，因为它确实是单线程的。因此，线程化程序中常见的并发性错误并没有出现在基本的基于事件的方法中。

当事件循环阻塞时，系统处于闲置状态，因此是潜在的巨大资源浪费。因此，我们在基于 事件的系统中必须遵守一条规则:不允许阻塞调用。

持久性

36. I/O设备

输入输出设备如何集成到系统中？

越快的总线造价越高，越快的总线越短，高性能的内存总线没有足够空间连接过多设备。

所以需要高性能的总线的设备会连在离CPU近的地方，低性能的设备离CPU远。

一个标准设备包含两部分：硬件接口，内部结构。

硬件接口包含三个寄存器：状态寄存器，命令寄存器，数据寄存器

在每次等待设备执行完成命令时会浪费大量CPU时间，所以引入中断的概念。中断在某些运行很快的设备中反而效果不好，所以有时使用混合策略，先轮询，再中断。

I/O 支持是必需的。中断、DMA 及相关思想都是在快速 CPU 和慢速设备之间权衡的结果

中断：利用中断并允许重叠，操作系统就可以在等待磁盘操作时运行其他的进程，否则操作系统只能简单自旋，不断轮询设备状态，直到完成I/O操作

DMA：DMA可以协调完成内存和设备间的数据传输，不需要CPU介入。如果不使用DMA，数据的拷贝工作阶段仍然是需要CPU的，这会降低效率。

硬件如何与设备通信？

1. 明确的I/O指令：这些指令规定了操作系统将数据发送到特定寄存器的方法，从而允许构造协议
2. 内存映射I/O：硬件将设备寄存器作为内存地址提供。当需要访问设备寄存器时，操作系统装载(读取)或者存入(写入)到该内存地址；然后硬件会将装载/存入转移到设备上，而不是物理内存。

设备驱动程序：

设备驱动程序完美的知道设备如何工作，和设备交互的细节都封装在设备驱动程序中，驱动程序有时会因为不了解设备的特殊功能而失效，且因为插入系统的设备都需要各自的驱动程序，所以操作系统中的大部分代码其实都是设备驱动程序代码。

37. 磁盘驱动器

简单的磁盘驱动器包含了一个单磁道，一个磁道有12个扇区，每个扇区的大小是512字节，用0-11表示，必须等待需要的扇区转到磁头下面，才可以实现写入读取操作，这需要等待，且往往是I/O服务时间的重要组成部分

正常我们使用的磁盘驱动器都是有百万的磁道，未来进行读取或写入操作，我们需要先寻道，然后等待转动延迟（这期间盘片已经完成了旋转），最后传输。

所以我们有公示

I/O的成本是非常高的，操作系统在磁盘I/O顺序上面发挥作用来提高效率

SSTF：最短寻道时间优先，但是如果有很多内圈的请求，那么外圈的磁道就会饥饿

C-SCAN电梯算法：该算法从内圈扫到外圈，再从外圈扫回内圈，仍然遵守较近的优先

SPTF：最短定位时间优先，现在的机器查找和旋转的速度是相当的，所以SPTF算法经常在驱动器内部执行（因为驱动器比操作系统更懂磁道边界，磁头位置）

现代操作系统较为复杂，而且很精准，可以准确实现SPTF，操作系统会选择它认为的几个最好的请求，并将他们全部发送到磁盘。

除此之外，调度程序执行还会执行I/O合并，相近的扇区共同进行请求，这样可以降低开销；发出I/O之后，操作系统通常会等一段时间，这样整体效率会提高很多。

38. 廉价冗余磁盘阵列（RAID）

RAID由多个磁盘、内存(包括易失性和非易失性)以及一个或多个处理器来管理系统。硬件 RAID 非常像一个计算机系统，专门用于管理一组磁盘。

RAID并行使用多个磁盘可以大大加快I/O时间，且容量较大，通过冗余的方式还可以容许损失磁盘保持运行，除此之外，RAID拥有很好的透明性，很轻松就可以部署，不必担心兼容性问题

评估RAID的方法：容量，可靠性，性能

RAID 0级：条带化

基本思想：以轮转方式将磁盘阵列的块分布在磁盘上。

评估条带化的容量、可靠性和性能。从容量的角度来看，它是顶级的：给 定 N 个磁盘，条件化提供 N 个磁盘的有用容量。从可靠性的角度来看，条带化也是顶级的， 但是最糟糕：任何磁盘故障都会导致数据丢失。最后，性能非常好:通常并行使用所有磁 盘来为用户 I/O 请求提供服务。

磁盘可以在连续工作负载下以 S MB/s 传 输数据，并且在随机工作负载下以 R MB/s 传输数据。

RAID 1级：镜像

保留两个物理副本就是典型的镜像系统

存在一致更新的问题，可能在一个磁盘写入，另一个备份磁盘没有写入，导致不一致，所以需要记录日志来保证同步

容量方面N/2，可靠性来说表现很好，容许任何一个磁盘故障，性能方面顺序读取只有N/2·S的带宽，随机写入是N/2·R，但是随机读取为N·R

RAID 4级：通过奇偶校验节省空间

对于每一条数据，我们都添加了一个奇偶校验(parity)块，用于存储该条块的冗余信息。例如，奇偶校验块 P1 具有从块 4、 5、6 和 7 计算出的冗余信息。

磁盘4可以使用奇偶校验的方法进行异常的监控

有效容量为N-1，可靠性方面，也仅仅允许一个磁盘故障，连续性能为（N-1）·S，相比于上面的级别，4级为了更新磁盘4，写入时的性能会较差

RAID 5级：旋转奇偶校验

随机读写性能比4级稍好一些，增加一些并行性

总之，如果你严格要求性能而不关心可靠性，那么条带显然是最好的。但是，如果你想要随机 I/O 的性能和可靠性，镜像是最好的，你付出的代价是容量下降。如果容量和可靠性是你的主要目标，那么 RAID-5 胜出，你付出的代价是小写入的性能。最后，如果你总是在按顺序执行 I/O 操作并希望最大化容量，那么 RAID-5 也是最有意义的。

40. 文件系统的实现

考虑文件系统时，我们需要考虑两个方面：文件系统的数据结构，访问方法

构建文件系统的磁盘分区如下：

很大面积用于存放用户数据，这些磁盘区域称为数据区域；inodes结构用于存放每个文件的信息（给定文件的元数据的结构：长度，权限，组成块的位置）；i和d分别表示inode位图和数据位图，用于指示对象/块是否空闲；S表示超级块，保存该特定文件系统的信息

41. 局部性和快速文件系统

一个老旧的文件系统如下所示，虽然简单，但是它的问题也很多，例如它会将磁盘随机存储，每次访问内存的定位成本太高，在逻辑上连续的块可能在这个文件系统上分离，性能太差。

FFS（快速文件系统）提供了解决方法：将磁盘划分为一些分组，称为柱面组，如果在同一个组中放置两个文件，FFS可以确保先后访问两个文件不会导致磁盘长时间寻道。

每个组中需要分配文件和目录，每个组中都有超级块的副本以防灾，inode位图和数据位图（ib，db）记录组的inode和数据块的分配

FFS文件创建超级复杂，因为如果更新了一个目录下的一个文件，这个子文件的inode以及data都要更新，那么记录信息的ib，db以及父目录的ib，db也都需要更新！

FFS的原则是相关的东西放在一起：目录的放置方法为寻找分配数量少的柱面组，这是为了跨组平衡目录；文件的放置需要确保文件和它对应的inode分配在相同的组中，以防止长时间寻道，然后再将同一目录中的所有文件都放在它们所在目录的柱面组中。

然而，在遇到大文件的时候，FFS会出现填满当前组的问题，FFS的解决方法是将大文件分布在磁盘上进行存储，分布的内容为inode指针指向的内容，虽然这样可能损害顺序读取的性能，但是在大块足够大的情况下，这种损害是比较小的。

另外FFS在处理小文件上也有所创新：引入子块，一个子块512字节，一个块一般是4kb，小文件攒够8个才变成一个大块，但是这样有些慢，所以使用缓冲写入，凑够4kb再写入文件系统；防止子块转过了，例如读取0完了想读1但是磁盘转多了，只能再转一圈，引入新的布局；

42. 崩溃一致性：FSCK和日志

举例来说，如果我们希望向磁盘中写入信息，需要至少三次：位图写入，inode写入，数据块写入。当这三个写入没有全部完成的时候发生了崩溃，这就是崩溃一致性问题。

为了解决这个问题有以下的几种方式

1.文件系统检查程序

典型的如FSCK，它的思路是让不一致的事情发生，查找不一致的内容然后删除，但是这种方法需要扫描整个磁盘，查找已经分配的块并读取目录树，这是不合理的，仅仅修复三个块的更新引入的问题而扫描整个磁盘

2.日志/预写日志

日志的思路借鉴自数据库管理系统，基本思路是在更新磁盘时，覆写操作之前，先写下一些标注，放入一个结构中，这样就构成了日志。崩溃发生之后只要读一下日志的内容，重试就好了。

写入日志的操作顺序如下：

1. 日志写入：将事务的内容写入日志
2. 日志提交：将事务提交块写入日志
3. 加检查点：将待处理的元数据和数据更新写入文件系统中的最终位置
4. 释放：一段时间后，更新日志超级块，在日志中标记该事务为空闲

在开始和结束块中加入日志内容的校验和，可以提高写入日志的效率

文件系统利用日志进行恢复：崩溃发生在事务写入日志前，跳过等待执行的更新即可；加检查点期间发生崩溃，文件系统需要扫描日志，找到已经提交磁盘的事务，重放这些事务，再次尝试将事务中的块放入自己最终的磁盘位置。

为了提高效率，也可以使用元数据日志的方法，不将Db写入日志，而是将数据在日志写入之前就写入最终位置

3.其他方法

软更新：利用系统保证每次写入都不会导致不一致发生，这种方法需要对文件系统数据结构非常了解，系统会很复杂

乐观崩溃一致性：尽可能多的向磁盘发出写入，利用事务校验和的一般形式或其他方式检测不一致。这样可以大幅提高效率

43. 日志结构文件系统

写入磁盘时，LFS 首先将所有更新(包括元数据!)缓冲在内存段中。当段已满时，它会在一次长时间的顺序传输中写入磁盘，并传输到磁盘的未使用部分。LFS 永远不会覆写现有数据，而是始终将段写入空闲位置。由于段很大，因此可以有效地使用磁盘，并且文件系统的性能接近其峰值。

LFS为了实现大量连续写入，使用写入缓冲的办法，写入磁盘之前，LFS会跟踪内存中的更新，收到足够数量更新后，才会立即将他们写入磁盘，从而确保有效使用磁盘。下图表示LFS将两组更新缓冲到一个段中。

在LFS系统中，查找inode号会比较困难，因为我们将inode分散在整个磁盘上，而且我们不会覆盖，最新版本的inode会不断移动。

通过一个inode映射imap作为一个中间层，imap驻留在写入新信息的位置旁边，更新数据块时，向文件加入imap，inode以及数据块。imap告诉LFS inode位于的位置，inode告诉LFS数据块所在的地址。

LFS在磁盘上有一个检查点区域（checkpoint region），包含了inode映射片段的指针（地址），可以通过检查点区域来找到imap，检查点区域定时更新，不影响整体性能。

LFS会不断的将新版本的文件写入磁盘的新位置，这样磁盘的中间位置就会存在很多垃圾，解决方法是定时清理，将现有的段打包到新段中，然后释放旧的段，这样才能保证LFS的大段写入机制。通过段中的摘要块可以判断当前块的死活，例如版本更新的时候就可以直接更新摘要块，这样就可以省略判断指针目前情况的时间。

关于何时清理，一些论文指出可以多清理更新少的死块，少清理更新多的死块，因为更新多的块会有越来越多的块被覆盖，被释放；但是这个问题仍然在被研究中。

检查点区域CR的更新为了保证不产生崩溃影响，在LFS中保留了两个CR，位于磁盘的两端，除此之外，还使用了先写出头，再写出主体，再写出最后一部分的方法来更新CR，每个部分都含有时间戳，这样实现了CR的一致更新；LFS使用前滚技术保证CR的更新，因为CR更新期间可能发生崩溃（每30s一次的那个），我们检查最后一个检查点区域，找到日志的结尾，用它来读取，并检查其中的更新

LFS的这种写入磁盘未使用部分，清理回收旧空间的方法，在数据库中称为影子分页，文件系统中称为写时复制。

44. 数据完整性和保护

单块故障包括潜在扇区错误和块讹误，磁盘扇区或扇区组出现问题导致磁盘内容不正确叫做潜在扇区错误，磁盘固件可能会产生问题，导致写入错误位置，这叫做块讹误。

潜在扇区错误的解决方法相对简单，因为这种错误很容易检测到，然后就可以用RAID的副本，通过奇偶校验来找到出错位置进行重建

块讹误的问题在于检测的困难，因为恢复只需要和以前一样找到副本就可以了。我们使用的校验方法为检验和，校验和就是一个函数的结果，该函数以一块数据(例如 4KB 块)作为输入，并计算这段数据的函数，产生数据内容的小概要(比如 4 字节或 8 字节)。

一个最简单的方法就是异或运算，对二进制字节每四个进行一次异或运算，得到一个十六进制结果，这种方法在有两个二进制数字一起更改的时候会失效；加法也是简单的检测方法。另外还可以使用CRC循环冗余校验，校验和的存储一般是在每个块上，驱动器制造商来将512字节的扇区多加8字节来实现存储，没有这种功能的扇区，只能开辟一个空间来进行校验和的存储

还存在错误写入的问题：在校验和中加入当前块的磁盘和扇区号（物理id）辅助判断就可以进行解决了

如果设备通知上层已经写入完成，事实上却还未持久化，磁盘留下的仍然是旧内容，这种问题如何解决？很多解决方法，例如在文件系统的其他位置加入校验和

文件系统应该按时使用一下校验和来进行检查，以保证数据的可靠性，这叫做磁盘擦净

校验和的空间开销很小，但是时间的开销很大

分布式

如何构建在组件故障时仍然可以正常工作的系统？

47. 分布式系统

通信总是不可靠的，会以很多种不同的方式丢包。

使用校验和技术可以进行数据完整性检验，但是这也不是一定可以检验出来的。

构建可靠的分布式系统最主要的抽象是基于远程过程调用（Remote Procedure Call,RPC），RPC中有两部分：存根生成器，运行时库

存根生成器：自动化将函数参数和结果打包成消息，并优化此类代码

运行时库：运行时库处理RPC系统中的大部分繁重工作，处理大多数性能和可靠性问题

48. Sun的网络文件系统（NFS）

分布式文件系统如下：客户端通过网络访问服务器磁盘上的目录和文件，这样做有很多好处，客户端之间可以轻松的共享数据；集中管理很方便，备份也仅仅通过少数机器就可以实现；安全，服务器一般在上锁的机房中

服务器故障时，我们可以利用幂等性（多次重复操作得到的结果是一样的）来处理故障，所以处理故障时我们一般进行重试就可以了

客户端中引入缓存的概念来增加利用的效率，因为网络传输总是很昂贵的。但是这就会出现一致性的问题，可能当前缓存的内容已经在服务器中被更新了，那么这要怎么办？

首先要在每次客户端关闭时，将缓存更新一遍，以保证其余节点进行访问时看到的是最新的版本。此外，客户端在使用缓存时还会对比服务器的版本以确认当前使用的是最新版本

49. Andrew文件系统（AFS）

AFS和NFS不同的地方在于一开始就考虑合理的，用户可见的行为。

AFS的基本原则是调用open()时，每个客户端的本地磁盘进行全文件缓存，最终close()操作之后，如果文件被修改，则写回服务器。

这样的系统存在两个问题：每次服务器查找路径都要很久，服务多个客户端的时候会浪费大量资源按目录路径找文件；客户端会发出很多test信息来判断是否文件被修改了。这两个问题影响了AFS的可拓展性，每次服务20个客户端就是上限了

AFSv2是AFS的改进版，引入了回调的概念，客户端缓存的文件被修改时，服务器会通知客户端，这样客户端就不用询问这个文件是否有效了；引入了文件标识符的概念，类似于缓存的概念，指定客户端感兴趣的文件，以减少查找的次数

举例来说：在不同的计算机之间，AFS 让更新在服务器上可见，并在同一时间使缓存的副本无效， 即在更新的文件被关闭时。客户端打开一个文件，然后写入(可能重复写入)。当它最终关闭时，新文件被刷新到服务器(因此可见)。然后，服务器中断任何拥有缓存副本的客户端的回调，从而确保客户端不再读取文件的过时副本。在这些客户端上的后续打开，需要从服务器重新获取该文件的新版本。

服务器崩溃的成本非常高，因为可能服务器也不知道哪个客户端的版本是最新的，所以可能需要客户端告诉服务器自己的版本是可用的，这样才可以恢复，所以客户端经常需要知道服务器是否挂了

AFSv2扩展性好很多（50个），且AFS考虑了系统管理，使得系统管理员可以简单的管理服务器

下载链接

链接: https://pan.baidu.com/s/11p5nVg2L1q61LECjlh1ryw 密码: p2hq
如果失效请私信联系我～

关注博主即可阅读全文