操作系统导论（OSTEP）读书笔记
作者：yinjie77
虚拟化
cpu虚拟化
第4章（进程）
1进程：就是运行中点程序（非正式定义），程序本身是没有生命周期的，只是存在磁盘上的一些指令，是操作系统让这些字节运行起来
2时分共享cpu技术：进程只运行一个时间片，然后切换到其他程序。
3空分共享：一旦将块分配给文件，在用户删除文件前，不可能将它分配给其他文件
4机器状态：程序在运行时可以读取或更新的内容
（1）内存：指令在内存中，读取和写入的树蕨也在内存中
（2）寄存器：许多指令明确地读取或更新寄存器：
（3）持久性存储设备
5机制：如何解决问题，策略：用哪种方法解决问题
6 进程api
（1）创建（create）：操作系统必须包含一些创建新进程的方法，例如在双击图标时会创建新进程
（2）销毁（destroy）：强制销毁，大多数情况下会自动退出
（3）等待（wait）
（4）其他控制（miscellaneous control）有时还可能有其他控制，例如，大多数操作系统提供某种方法来暂停进程，然后恢复
（5）状态（status）：关于进程的状态信息
7进程创建细节
（在进程列表上创建进程条目）
（1）将代码和所有静态数据从磁盘加载到内存中（早期操作系统在运行前全部加载完成，现代操作系统需要加载的数据才加载）
（2）为栈分配内存：栈存放局部变量，函数参数和返回地址
（3）为堆分配内存：堆用于显示请求的动态分配数据
（程序运行完之后，释放内存，从进程列表中清除）
8进程状态
（1）运行
（2）就绪：进程已准备好，操作系统不选择在此时运行
（3）阻塞：一个进程执行了某种操作，直到发生其他事件时才会准备运行
（4）初始状态：进程在创建时处于的状态
（5）最终状态：已推出但尚未清理
9进程控制块（pcb）：存储关于进程的信息的个体结构
第6章（机制：受限直接执行）
1直接执行（只需直接在cpu上运行程序）
2受限操作：如磁盘发出io请求或获得更多cpu和内存资源
3 用户模式：运行的代码会受到限制，如进程不能发出io请求，这样会导致程序异常而终止
4 内核模式：可以做各种特权操作
5 陷阱（trap）：要执行系统调用（内核模式）就必须执行特殊的陷阱指令，该指令同时跳入内核并将特权级别提升到内核模式，完成后，操作系统调用一个特殊的从陷阱返回指令（将寄存器保存到内核栈以便返回），回到用户模式（确保足够多寄存器以保证能够正确的返回（从内核栈返回到寄存器中））
6陷阱表：根据需要自由配置机器硬件（各种功能，让cpu记住硬件的位置以供调用），以免程序可以跳转到内核的任意位置，谨慎控制在陷阱上执行的代码
7等待系统调用：操作系统相信系统的进程会合理运行，运行时间过长进程会定期放弃cpu，以便操作系统调用（操作系统不能不做事情），如果程序执行了非法操作，也会将控制转移给操作系统
8操作系统进行控制：时钟中断，时钟设备可以编程为每隔几毫秒产生一次中断，产生中断时，当前运行程序停止，中断处理程序运行，此时，操作系统重新获得cpu的控制权。与陷阱表一样，必须通知硬件哪些代码在发生中断时运行，启动时钟是特权操作（也就是说必须在内核模式下完成），在发生中断时，一定要保存程序的状态，以便正常恢复程序（也与内核模式类似）
9上下文切换：操作系统要做的就是为当前正在执行的进程保存一些寄存器的值（到它的内核栈），并为即将执行的进程恢复一些寄存器的值（从内核栈恢复），两个进程不同的栈，特权模式进入中断模式才可进行上下文切换，返回陷阱返回指令时，即将执行的程序变成了当前运行的程序。（上下文切换成本不仅来自保存和恢复寄存器，程序在cpu高速缓存、TLB、等其他硬件中建立了大量状态，一旦更换，全部刷新）
第7章（进程调度：介绍）
周转时间=完成时间-到达时间
1先进先出（FIFO（First In First Out））：可能会出现耗时较少的程序被排在耗时多的程序后面，导致平均周转时间较长
2最短任务优先（SJF（Shortest job First）：可能出现耗时较长的程序先到达，使得目前最短任务就是耗时长的程序，平均周转时间变长（非抢占式）
3非抢占式程序：系统会将每项任务做完，再考虑是否运行新工作
4最短完成时间优先（STCF（Shortest Time to Completion First））：抢占式程序，每当新工作进入系统时，它会就确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作
5响应时间=首次运行-到达时间
6轮转：在一个时间片内运行工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束，时间片长度必须是时钟中断周期的倍数，时间片也不可太短，否则，频繁上下文切换的成本将影响整体性能
第8章（调度：多级反馈队列）
1多级反馈队列（Multi level Feedback Queue）：有许多独立的队列，每个队列有不同的优先级，总是优先执行较高优先级的工作，一个工作只能存在于一个队列中，每个队列可以有多个工作，在具有同样优先级的情况下，采用轮转调度
规则
（1）如果A的优先级>B的优先级，运行A
（2）如果A的优先级=B的优先级，轮转运行A和B
（3）工作进入系统，放在最高优先级
（4）一旦工作用完了其在某一层中的时间配额（消耗的总时间）（无论中间主动放弃了多少次cpu），就降低其优先级
（5）经过一段时间S，就将系统中所有工作重新加入最高优先级队列中
高优先级队列通常只有较短的时间片，因而交互工作可以更快地切换，低优先级队列有较长的时间片，会有更好的工作效果
第9章（调度：比例份额）
1比例份额：确保每个工作获得一定比例的cpu时间，而不是优化周转时间和响应时间
随机调度方法
（1）可以避免奇怪的边角情况
（2）很轻量，不需要记录任何状态
（3）速度很快，只要产生随机数，就能马上调度程序
2彩票机制：允许拥有一组彩票的用户以他们喜欢的某种货币将彩票分给自己不同的工作，之后系统再将这种货币兑换为正确的全局彩票
A和B各有100张彩票，A有A1和A2两个工作，分别赋予500张彩票，B只有一个工作，只给10张彩票，则A1和A2全局彩票数为50张，B全局彩票数为100张
3 彩票调度的实现：一个随机数生成器和一个记录系统中所有进程的列表（每个节点都有对应的彩票数），生成一个数后，开始从列表第一个开始寻找，如果随机数大于第一个节点所有的彩票，则继续往下找，直到随机数比当前节点与之前节点彩票数之和加起来要小。，节点尽量按彩票数递减排序，这样子可以有最小的迭代次数找到节点（所要执行的程序）
4步长调度：步长与自己所有的彩票数成反比，当进行调度时，选择目前拥有最小行程值的进程（如果相同步长就随机选一个），并且在运行之后该进程增加一个步长（最初所有进程的步长都为0，所以一开始都有可能选中）
5彩票调度有步长调度没有的优势，不需要记录全局状态，只需对加入新进程后的全局彩票数进行更新即可，如果是步长调度就不知道如何设置行程值
第10章（多处理器（cpu）调度）
1时间局部性：一个数据被访问之后，它很有可能在不久的将来被再次访问
2空间局部性：当程序访问地址x的数据时，有可能会紧接着访问x周围的数据
3缓存一致性：A程序修改了内存中某个数据，只是将这个数据更新到CPU1缓存中，没有更新到内存中（将数据写回内存比较慢，操作系统会选择稍后再做），此时发生中断，并交给cpu2处理B程序，因为此时没有缓存新数据，所以会从内存中读取旧的数据，而不是正确的新数据
解决方法
（1）总线窥探：缓存监听所有缓存和内存的总线，来发现内存访问。如果cpu发现对它放在缓存中的数据更新，会从缓存中移除或者更新它（修改为新值）
4缓存亲和度：一个进程在某个cpu上运行时，会在该cpu的缓存中维护许多状态，下次再相同cpu上运行时，由于缓存中的数据而执行的更快，相反，在不同的cpu上运行，会由于加载变得很慢
5单队列调度多处理器调度：不需要太多修改，就可以将原有的策略用于CPU
缺点
（1）缺乏可拓展性：为了使得在多个cpu上运行，必须加锁，然而锁可能带来巨大的性能损失
（2）缓存亲和度问题：每个cpu都简单的从队列中选取下一个工作执行，导致工作不断在cpu之间来回切换（解决：尽可能让工作在同一个cpu上运行，有时可能需要牺牲某些工作的亲和度）
6多队列多处理器调度：每个cpu一个队列（每个队列采用不同的调度规则，单队列只有一种调度规则）
（1）拓展性非常好
（2）工作都保持在固定的cpu上，可以很好利用缓存数据（缓存亲和度高）
同时也存在问题：某个cpu上的任务完成了就闲置了，所以必须让别的工作移动到这个cpu上，称为迁移，一般都是不断迁移一个工作或多个工作
（3）迁移的基本方法：工作窃取：工作量较少的队列不定期检查其他（目标）队列是不是比自己的工作多，如果目标队列更满，则从队列中拿一个或多个工作过来，但同时太频繁检查队列，又有搞得开销，检查时间太长，又会导致负载不均
内存虚拟化
第13章（抽象：地址空间）
1地址空间：包括程序的代码，栈、堆
2虚拟内存：程序感觉自己拥有自己的私有物理内存，操作系统在专门的硬件帮助下，通过虚拟内存从你的索引，转换为物理地址。
3操作系统让不同程序复用内存
第15章（机制：地址转换）
1基于硬件的地址转换：简称地址转换：利用地址转换，硬件对没次内存访问进行处理，将指令中的虚拟地址转化为数据实际存储的物理地址，因此每次引用内存时，都会重定位。地址转换操作完全由硬件处理，没有操作系统介入
2动态重定位（基址加界限机制）：每个cpu都需要两个寄存器，基址寄存器和界限寄存器，这组寄存器能够将地址空间放在物理内存的任何位置，同时又能保证进程只访问自己的地址空间。将虚拟地址加上基址寄存器中的内容，得到物理地址，发送给内存系统。界限寄存器确保地址在进程地址空间范围内（两种检查方式（两种方式逻辑等价）1在虚拟地址与基址寄存器求和前它记录地址空间的大小，然后检查界限2转化完之后记录地址空间结束的物理地址，再检查界限）。负责转换地址的部分称为内存管理单元（MMU）
3内存与进程一样，也有列表，称为空闲列表，用于记录当前没有使用的物理内存
4动态重定位硬件要求
（1）特权模式：以防用户模式的进程执行特权操作
（2）基址与界限寄存器：用于地址转换
（3）能够转换虚拟地址并检查是否越界
（4）修改基址与界限寄存器的特权指令：允许操作系统在切换进程时改变他们
（5）注册异常处理程序的特权指令：如果异常发生，操作系统必须告诉硬件应该执行哪些代码
（6）能触发异常
5动态重定位：操作系统职责
（1）内存管理：为新进程分配内存，从终止进程收回内存，通过空闲列表管理内存
（2）基址与界限管理：必须保存和恢复基址与界限寄存器的内容，保存在每个进程都有的结构中，如pcb（可以改变地址空间的物理地址：将地址空间拷贝到新位置，最后更新基址与界限寄存器）
（3）提供异常处理程序，或一些调用的函数
6内部碎片：已经分配的内存单元内部有未使用的空间（碎片），造成浪费
第16章（分段）
1段：地址空间里有三个逻辑不同的段：代码、栈、堆（需要三组基址与界限寄存器）
2段的引用：用虚拟地址开头几位来标识不同的段，比如有三个段，则利用前两位标识，后面的便是偏移量（因为只有三个段却用了两位标识符，所以有些系统会把栈和堆当作同一个段）
3保护位：为每个段增加几个位，标识程序是否能够读写该段或执行其中的代码，同样端内代码可以被多个进程共享（节省内存）
4细粒度分段：允许将地址空间划分为大量较小的段（之前的分段只有几个段，称为粗粒度的）
5外部碎片：物理内存有很多空闲的小空间，很难分配给大的段
6稀疏地址空间（未使用的地址空间）
第17章（空闲空间管理）
1分割与合并：
（1）分割：如果请求的空间大小小于某块空闲块，找到一块可以满足请求的空闲空间，将其分割，第一块给用户，第二块留在空闲列表中
（2）合并：在归还一块空闲内存时，仔细查看要归还的内存块的地址以及附近的空闲看见快，如果归还的地址与原有的空闲块相邻，就合并位一个大的空闲块
2头块：在内存块之前，保存内存块的信息（这也是free（）为什么不用有所释放内存块大小的原因），包含大小与幻数（提供完整性检查），free（）所释放的是头块大小加上分配的内存
3基本策略
（1）最优匹配：遍历整个空闲列表，找到和请求大小一样或更大的空闲块，然后返回这组候选者最小的一块。（遍历查找付出高新能代价）
（2）最差匹配：尝试找最大的空闲块，分割满足用户需求后，将剩余的块加入空闲列表（同样需要遍历整个空闲列表，经过研究表明，导致过量的碎片）
（3）首次匹配：找到第一个足够大的块，将空间返回给用户，剩余的合并（具有速度优势，但有时会让开头有很多小块，分配程序如何管理空闲列表的顺序变得很重要，一种方式是基于地址排序。通过保持空闲块按内存地址有序，使得合并很容易，减少碎片）
（4）下次匹配：多出一个指针，指向上一次查找结束的位置（其写法是将对空闲空间的查找操作扩散到整个列表中，避免对列表开头频繁的分割）
4分离空闲列表：如果某个应用程序经常申请一种或几种大小的内存空间，那就用一个独立的列表，只管理这样大小的对象
（1）厚块分配程序：它为可能频繁请求的内核对象创建一些对象缓存，如锁和文件inode，这些对象缓存，每个分离了特定大小的空闲列表，因此能很快响应内存的请求与释放，当缓存空闲空间快耗尽时，他就向通用内存申请一些厚块，相反快用完时，通用内存收回这些空闲。
5伙伴系统：当有一个内存分配请求时，空闲空间被递归地一分为二，直到刚刚好可以满足请求的大小（再分无法满足请求），因为只能一分为二，所以肯定会有内部碎片，漂亮之处在于块被释放时，被释放的块很好找伙伴（互为伙伴的块只有一位不同）以此方便地进行合并
第18章（分页：介绍）
1分页：将一个进程的地址空间分割成固定大小的单元，一个单元称为一页，物理内存看成是定长槽块的阵列，叫做页帧，一个页帧包含一个虚拟内存页
2页表：为地址空间的每个虚拟页面保存地址转换，让我们知道每个页再物理内存的位置（是每一个进程的数据结构），不同进程要保留不同页表
（1）虚拟页面号（VPN）
（2）页内偏移量
（3）物理帧号（PFN）
（4）页表项（PTE）：
【1】含有有效位：用于指示特定地址转换是否有效，所有未使用的空间都被标记位无效，如果进程尝试访问未使用的空间，则会产生异常，有效位对支持稀疏地址空间至关重要，不需要再为未使用的页面分配物理帧，节省内存
【2】存在位：表示该页是在物理存储器还是磁盘上
【3】脏位：表示页面被带入内存后是否被修改过
【4】参考位：用于追踪页是否被访问，也用于确定哪些页很受欢迎
例如
64个字节（虚拟地址6位），16个字节一个页（4个页）
两位虚拟页号，其他四位偏移量
前两位虚拟页号查找页表项中的物理帧找到页所放在的物理位置，偏移量不变
3页表占用的空间可能很大，同时分页需要我们执行一个额外的内存引用，以便从页表中进行地址转换（分页很慢）
第19章（分页：快速地址转换（TLB））
1地址转换旁路缓冲存储器（TLB）：对每次内存访问，硬件先检查TLB，看看其中是否有期望的映射转换，如果有就很快完成转换，不用访问页表
2TLB算法：首先从虚拟地址中国提取VPN，然后检查TLB是否拥有该VPN的转换映射，如果有，则命中TLB，从TLB取出页帧号（PFN），与原来虚拟地址中的偏移量组合形成期望的物理地址。如果没有命中，需访问页表来寻找映射，并用该映射更新TLB，更新成功后，系统会重新尝试该指令，TLB有了这个映射之后，内存得到很快的处理。我们希望TLB多次命中
3缓存：缓存背后的思想是利用指令和数据引用的局部性
4处理TLB未命中
（1）硬件：未命中时，硬件遍历页表，找到正确的页表项，取出想要的映射转换，用来更新TLB，并重试该指令
（2）软件：未命中时，硬件系统抛出一个异常，会暂停当前的指令流，将特权级提升至内核模式，跳转至陷阱处理程序。这个陷阱处理程序是操作系统的一段用于处理TLB未命中的代码，查找页表中的映射，然后用特权更新TLB。并从陷阱返回（这里陷阱返回不是继续执行之后的语句，而是从导致陷阱的指令的指令继续执行，这次会命中TLB。为避免引起TLB未命中的无限递归，可以将TLB未命中陷阱处理程序直接放在物理内存中，或者在TLB中保留永久有效的地址转换，用以留给处理代码本身）
5TLB内容
（1）TLB的有效位：与页表有效位不同，页表有效位是标记该页是否被使用，而TLB有效位是标识该项是不是有效地址转换映射
（2）保护位：用来标识该页是否有访问限权
6 上下文切换时对TLB的处理
（1）清空TLB：但是如果频繁切换进程，TLB会大量未命中，有开销
（2）增加地址空间标识符（ASID）：有了ASID之后，TLB可以同时缓存不同进程的地址空间映射，没有任何冲突。
7TLB替换策略
（1）替换最近最少使用（LRU）：假设最近没有使用过的项，可能是好的换出候选项
（2）随机
第20章（分页：较小的表）
1更大的页：可以使得页表变得更小，但大内存页会导致页内的浪费，导致内部碎片多
2分页和分段：为每个逻辑分段提供一个页表（代码、栈、堆），仍然利用MMU，使用基址保存段的页表的物理地址，界限寄存器用于指示页表的结尾，每个界限寄存器保存了段中最大有效页的值。（如果有一个大而稀疏的堆，仍然可能导致大量的页表浪费，其次，这种杂合导致外部碎片再出现，尽管大部分内存是以页面大小单位管理的，但页表出现可以是任意大小。）如果TLB未命中，将使用基址和界限对，将基址中的物理地址与VPN结合起来，形成页表项
3多级页表：将页表分成页大小的单元（将页表项放入单元中），如果整页的页表项无效，就完全不分配该页的页表，为了追踪页表的页是否有效，使用了名为页目录的新结构，页目录可以告诉你页表的页在哪里或页表的整个页不包含有效页，页目录由页目录项组成，页目录项包括有效位与页帧号（PFN）
例如
页表有256个项，每个PTE（项）为4个字节，每个页为64个字节
则页表大小1KB（256*4），则一个页表可以分为16个页（1KB/64字节）(页目录有16个项)，每个页包含16个PTE（64/4）
4与线性页表相比：线性页表按VPN搜索PTE（页表项）数组，这样的结构需要连续空闲物理内存，有了多级结构，增加一个间接层，使用页目录指向页表的各个部分。
5多级页表也是有成本的，在TLB未命中时，需要从内存加载两次才能获得正确的地址转换信息（一次用于页目录，另一次用于PTE本身）
第21章（超越物理内存：机制）
1交换空间：在硬盘上开辟一部分空间用于物理页的移入和移出，将内存的的页交换到其中，并在需要的时候交换回去，因此操作系统能够以页大小为单元读取和写入交换空间
2存在位：硬件在PTE中查找时，可能发现页不在物理内存中，硬件判断是否在内存中的方法就是存在位，如果设置为1，则表示该页在内存中。如果设置为0，则页不在内存中，而在硬盘上。访问不在物理内存中的页，这种行为通常被称为页错误
3页错误：都由操作系统负责，可以用PTE中的某些位来存储硬盘地址，这些位通常用来存储PFN这样的数据。
4高水位线与低水位线：当操作系统发现有少于低水位线可用是，后台负责释放内存的线程会开始运行，直到有高水位线个可用的物理页
第22章（超越物理内存：策略）
1最优策略：替换内存中在最远将来才会被访问到的页
2冷启动未命中（强制未命中）：一开始缓存是空的，而这是对项目第一次引用
3容量未命中：缓存空间不足不得不踢出一个项目以将新项目引入缓存
4冲突未命中：缓存对项的位置有限制
5 FIFO：先入的页被提出
6随机
7 LRU：找到绝对最旧的页开销太大了
8近似LRU：时钟算法：在页中增加使用位，当页被使用时设为1，否则设0，时钟一开始指向某个页，直到找到位为0的页，如果所有位都被使用了，则所有位都被设为0.（改进：找到未使用的又干净（未被修改的页）的页踢出，无法找到时，再找脏的未使用的页面）
9预取：操作系统可能会猜测一个页面即将被使用，从而提前载入
10聚集写入：在内存收集一些待完成写入，以更高效的方式写入（执行单次大的写操作，比许多小的写操作更有效）
并发
第26章（并发：介绍）
1线程：一个程序只有一个执行点（一个程序计数器，用来存放要执行的指令），多线程程序会有多个执行点（多个程序计数器，每个都用于取指令和执行）。每个线程由一个程序计数器（记录哪里获取指令），每个线程有自己的一组用于计算寄存器。线程之间的切换类似于进程间的上下文切换，对于进程，将状态保存在PCB中，对于线程，保存在线程控制块（TCB），但是地址空间保持不变。在传统单线程中，只有一个栈，在多线程中，由多个栈
2线程与进程的关系
进程=火车，线程=车厢
• 线程在进程下行进（单纯的车厢无法运行）
• 一个进程可以包含多个线程（一辆火车可以有多个车厢）
• 不同进程间数据很难共享（一辆火车上的乘客很难换到另外一辆火车，比如站点换乘）
• 同一进程下不同线程间数据很易共享（A车厢换到B车厢很容易）
3并发术语
（1）
临界区：访问共享变量的代码片段，一定不能让多个线程同时执行，只能保证一个线程运行
（2）竞争条件：出现多个线程同时进入临界区，都试图更新更新临界区的数据结构
（3）不确定性：程序由一个或多个竞争条件组成，输出因运行而异
4原子方式：会像期望那样执行更新，不能在指令中间中断，但是一般不会由一条指令可以做到这一点，所以必须用一些通用的集合，即同步原语，加上操作系统的帮助，以同步和受控的方式访问临界区（例如包含一些互斥的原语，保证只有一个线程进入临界区）
第28章（锁）
1锁：是一个变量，必须声明是某种类型才可以使用，这个锁变量保存了在某一时刻的状态，要么是可用的，表示没有线程持有锁，要么是被占用的，表示有一个线程持有锁
2锁所要考虑的问题
（1）能否提供互斥
（2）公平性：是否有线程会无法得到锁
（3）使用锁所增加的开销
3控制中断：最早提供的互斥解决方案之一
一般很少使用
缺点
（1）一个程序可能一直独占处理器，操作系统无法获得控制
（2）不支持多处理器，线程可以运行在其他处理器上，能够进入临界区
（3）中断丢失，可能导致严重的系统问题
（4）效率低
4自旋锁：当第一个线程A获取锁的时候，能够成功获取到，不会进入while循环，如果此时线程A没有释放锁，另一个线程B又来获取锁，此时由于不满足条件，所以就会进入while循环，不断判断是否满足条件，直到A线程调用unlock方法释放了该锁。（在单cpu上，需要不断通过时钟中断一个线程，运行其他线程，否则自旋锁在单CPU上无法使用，因为一个自旋的线程永远不会放弃CPU）
（1）能满足一次只允许一个线程进入临界区
（2）自旋锁无法提供公平保证，可能会永远自旋
（3）性能开销大，假设一个线程持有锁，调度器可能会运行其他线程，而其他线程都在竞争锁，都会在放弃cpu之前，自旋一个时间片，浪费cpu周期（但是在多线程上，就不会浪费cpu周期，因为临界区一般很短，因此锁可以很快使用）
5测试并设置（test and set）：返回old-ptr所指向的旧值，同时（ptr）更新为new这个新值
（1）假设一个线程在运行，调用lock，没有其他线程持有锁，则flag=0，调用testandset（flag，1），返回为0，并将flag设置为1，调用unlock（）将flag清理为0
（2）当其他线程占有锁，本线程调用lock，testandset重复返回1，一直自旋，直到其他线程解除锁，本线程再跟第一种情况一样。
6比较并交换：检测ptr所指向的值是否和expect相等，如果是，更新ptr为new这个新值，否则什么也不做
7获取并增加：返回特定地址的旧值，并让该值自增1。如果线程希望获取锁，首先对一个ticket值执行一个原子的获取并相加指令，这个值作为该线程的myturn，当线程的（turn=myturn），则轮到该线程进入临界区，unlock是增加turn，从而下一个等待线程可以进入临界区
8自旋时放弃cpu：在发现锁被占用时，线程主动放弃cpu。虽然比原来其他线程浪费时间片要好，但是上下文切换的成本太高了，浪费很大，而且一个线程可能处于一直让出的循环，其他线程反复进出临界区，造成中这个线程饿死
9使用队列：使用park让调用线程无法调用时睡眠，在锁可用时被唤醒，通过队列控制谁会获得锁，避免饿死。
第29章（基于锁的并发数据结构）
1并发计数器：只是在调用函数操作时获取锁，释放锁，使得并发计数
（1）懒惰计数器：通过多个局部计数器和一个全局计数器实现，每个cpu有一个局部计数器。具体说在4分cpu的机器上，有4个局部计数器于一个全局计数器，每个计数器都有一个锁。如果一个线程想增加计数器，就增加它的局部计数器，不同cpu上的线程不会竞争。局部计数器会定期转移全局计数器，这个定期取决于一个阈值S，，比如阈值是5，则局部计数器到达5时，会把5加到全局计数器中，清空自己的计数器。
2并发链表：也是在函数调用时使用锁，使得并发插入
3并发队列：在队头和队尾都使用锁，使得入队和出队可以并发操作
第30章（条件变量）
1条件变量：是一个显示队列，当某些执行状态（条件）不满足时，线程可以把之间加入队列，等待该条件，等待该条件。当改变了上述状态时，就可以唤醒一个或多个等待线程
2生产者与消费者（有界缓冲器）问题：生产者线程把生成的数据放入缓冲区，消费者从缓冲区取走数据项（生产者只有在缓冲区满了才睡眠，消费者也只有在缓冲区为空的时候睡眠）
第31章（信号量）
1信号量：是有一个整数值的对象（只有信号量大于等于0时线程才可以继续运行）
2二值信号量（锁）：信号量的初值为1
例如：线程0调用wait之后，post之前（调用锁），另一个线程1调用wait试图进入临界区，线程1把信号量减为-1，然后等待（只有>=0时才可以进入临界区），然后0再次运行，它最终调用post，信号量变为0，然后线程1就可以获得锁
3信号量作为条件变量:信号量初值为0（父线程中调用wait，子线程调用post）
（1）父进程创建子进程，但子线程没有运行：父线程调用wait，信号量为-1，父进程睡眠，切换到子进程，子进程调用post，信号量为0，切换到父进程
（2）父进程创建子进程，子线程先于父线程运行：子线程先调用post，使得信号量为1，切换回父进程，父进程调用wait，信号量为0，不用睡眠，继续运行
4读者-写者锁：获取读锁时，首先要获取lock，然后增加reader变量，追踪目前有多少个读者在访问该数据结构。当第一个读者获取该锁时，读者也会获取写锁，其他读者也可以获取这个读锁，但是想要获取写锁的线程，就必须等到所有读者都结束
5哲学家就餐问题解决方案：让前面的哲学家拿左边的叉子，最后一个哲学家拿右边的叉子
第32章（常见并发问题）
1非死锁缺陷
（1）违反原子性：代码段本意是原子的，但在执行中并没有强制实现原子性（加锁就能解决）
（2）违反顺序缺陷：两个内存访问的预期顺序被打破了（即A应该在B之前执行，但是实际运行中却不是这个顺序），条件变量可以解决
2死锁缺陷：
死锁产生的条件
（1）互斥：线程对于需要的资源进行互斥的访问
（2）持有并等待：当线程因请求资源而阻塞（所求锁正被其他线程占有）时，对已获得的资源保持不放。
（3）非抢占：线程获得的资源不能被抢占，资源在使用完之前不会释放
（4）循环等待：线程之间存在一个环路，环路上每个线程都额外持有一个资源，而这个资源又是下一个线程要申请的
解决办法
（1）预防
【1】循环等待：获取锁时提供一个全序（先申请1再申请2）一般系统不会只有两个锁，所有很难实现。偏序：安排锁的获取并避免死锁。
【2】持有并等待：一次性分配所有资源，这样就不会有请求了（需要提前知道要用哪些锁）
【3】非抢占：trylock函数使得线程在尝试获得锁但锁无法使用时，会等待一段时间，如果超时，则放弃之前所有的资源，但是有可能两个线程会一直重复这个序列，同时抢锁失败，称为活锁（可以在循环结束时，先随机等待一个时间，然后再重复整个动作，降低线程之间的重复干扰
【4】互斥：通过数据结构构造出不需要锁的数据结构
（2）
【1】通过调度避免死锁（这个调度指的是使线程运行在不同CPU上）
【2】恢复和检查：允许死锁偶尔发生，检查到死锁再采取行动
第33章（基于事件的并发）
1基于事件的并发：等待某事发生，当它发生时，检查事件类型，然后做少量的相应工作
2使用单个CPU和基于事件的应用程序，并发程序发现的问题不再存在，因为一次只处理一个事件，所以不需要获取和释放锁。（但会带来一个问题，就是如果发出一个阻塞的调用，系统就会处于闲置状态，导致资源浪费）
解决办法：
利用异步io，这些接口使应用程序能发出io请求，并在io完成之前将控制权返回给调用者，这些接口让应用程序能够确定各种io是否完成
3基于事件的方法另一个问题：当事件处理程序发出异步io时，必须打包一些程序状态，以便下一个事件处理程序在io最终完成时使用，而在基于线程的程序中是不需要的，因为程序所要的状态在线程栈中。
4第三个问题：不能很好地与某些类型的活动集成，如分页，事件处理程序发生页错误，它将被阻塞，在页错误完成之前不会有进展
5第四个问题：代码很难管理，因为各种函数的确切语义发生了变化
持久性
第36章（io设备）
1系统架构：cpu和内存连接在内存总线上，图像或其他高性能io（显卡）通过常规的io总线连接到系统上，键盘等最慢的设备连接到系统外围总线上。（越快的总线越短，因此高性能的内存没有足够空间连接太多设备，高新能总线的造价非常高）
2标准设备
（1）硬件接口：向系统其他部分展现的硬件接口，让系统软件来控制它的操作（设备接口包括三个寄存器：一个状态寄存器，可以读取并且查看设备的当前状态；一个命令寄存器，用于通知设备执行某个具体任务；一个数据寄存器，将数据传给设备或从设备接收数据
）
（2）内部结构：包含设备的相关实现，负责具体实现设备展示给系统的抽象接口。
3标准协议：
（1）反复读取状态寄存器，等待设备进入可以接收命令的就绪状态，称之为轮询（问它在做什么）
（2）操作系统下发数据到数据寄存器
（3）将命令写入命令寄存器，这样设备就知道数据准备好了，应该开始执行命令
（4），再次轮询设备，等待并判断设备是否执行完成指令
4（如果设备非常快，最好的办法是轮询（使用太多中断反而导致设备变慢），如果设备比较慢，采用重叠的中断比较好（在中断过程中可以做其他事情），如果设备速度为止，可以考虑使用混合策略，先尝试轮询小段时间，如果设备没有完成，就使用中断）
5最好不用中断的场景是网络，不断处理中断而无法处理用户层的请求（活锁）
6中断优化：合并，抛出中断之前往往会等待一小段时间，在此期间，其他请求可能很快完成，因此多次中断可以合并为一次中断抛出。
7DMA：协调完成内存和设备间的数据传递，不需要cpu介入（在此期间，cpu可以做其他事情）
8设备交互的方法
（1）明确使用io指令，这些指令规定了操作系统将数据发送到特定设备寄存器的方法（利用上面的协议）
（2）内存映射：将外围设备映射到内存空间，便于CPU的访问
9设备驱动程序：所有设备交互的细节都封装在其中
第37章（磁盘驱动器）
1接口：驱动器由大量扇区（512字节）组成，每个扇区都可以读取或写入，磁盘可以视为一组扇区。保证单个512字节 的写入是原子的。
2磁盘组件
（1）盘片：圆形坚硬表面，通过引入磁性变化存储数据，一个磁盘可能由多个盘片
（2）主轴：所有盘片都围绕主轴转，主轴连接到一个电机，以恒定的速度转动
（3）磁道：数据在扇区的同心圆中的每个表面上编码，同心圆称为磁道，一个表面有多个磁道
（4）磁头：采取读写操作
（5）磁盘臂：在表面上移动，将磁头定位在期望的磁道上
3旋转延迟：必须等待期望的扇区旋转到磁头下
4寻道：一个表面有许多磁道，从一个磁道跳转到另一个磁道就是寻道
5传输：数据从表面读取或写入数据
6外圈磁道比内圈磁道有更多扇区（容量更大）
7所有磁盘都有缓存，用于保存从磁盘读取或写入磁盘的数据
8回写：先更新缓存的内容，再等总线不繁忙时更新至磁盘
9直写：同时更新缓存与磁盘的内容
10：最短寻道时间优先（SSTF）：按磁道对io请求队列排序，选择再最近磁道上的请求先完成
11电梯算法：从外圈扫描磁道到内圈，再从内圈访问到外圈
12最短定位时间优先（SPTF）：视情况而定应答磁盘调度
第38章（廉价冗余磁盘阵列（RAID））
1廉价冗余磁盘阵列：多个磁盘一起构建更大、更快、更可靠的磁盘系统。从外部看，raid像一个磁盘，在内部，raid由多个磁盘、内存以及一个或多个处理器来管理系统（如同操作系统一般，专门管理一组磁盘）
2优点：并行使用多个磁盘可以大大加快io时间，容量巨大，提高可靠性（在多个磁盘上传输数据（无raid技术）会使数据很容易受到单个磁盘丢失的影响，通过某种冗余，raid可以容许损失一个磁盘并保持运行）
3故障模型：故障—停止故障模型，在这种模式下，磁盘处于两种状态之一：工作状态或故障状态。工作状态可以读取或写入，故障时，认为永久丢失
4raid0级（条带化）：将块条带化组成大块
评估：容量顶级，给定n个磁盘，提供n个磁盘容量，可靠性，任何磁盘故障都会导致数据丢失，性能好：能并行使用所有磁盘来为用户io请求提供服务
5raid1级（镜像）：只需生成系统中每个块的多个副本，每个副本应该放在一个单独的磁盘上，这样可以容许磁盘故障，读取时可以读取原本与副本容易一个，但是写入必须两个同时更新
评估：容量，只能获得一半的有用容量，可靠性，对于单个故障处理的还是很好的，性能，因为写入时必须等待两个物理写入完成，所以比单个磁盘时间略高
6raid4级（通过奇偶校验节省空间）：对于每一条数据，都添加了一个奇偶校验快，用于存储该条块的冗余信息（可以用异或函数，从第一个块开始对后面不断进行异或，最后保存结果至校验快中）
评估：使用一个磁盘保存校验快，容易为n-1，可靠性，容许一个磁盘故障，不允许更多。如果丢失多个，则无法重建，性能，因为要更新块内容，必须同时更新磁盘内容，使用异或必须读取内容，则需要两次读取与两次写入，所以总延迟大约是单个磁盘的两倍
7raid5级（旋转奇偶校验）：将不同奇偶检验块保存在不同磁盘上（不同于raid4中保存在一个磁盘，导致无法并行）
评估：大部分与4级相同，但是写入性能明显提高，它允许跨请求进行并行处理，但是写入将会是单个磁盘的4倍损失
8
（1）如果严格要求性能而不关心可靠性，条带是最好的
（2）想要随机io与可靠性，镜像是最好的，但是付出的代价是容量下降
（3）如果容量和可靠是主要目标，但付出的是小写入性能。
第40章（文件系统（纯软件）实现）
1简单文件系统（VSFS）：只使用一种块的大小
（1）用户数据
（2）元数据的关键部分：记录文件包含哪些数据块、文件的大小，其所有者和访问限权、访问和修改时间以及其他类似信息，为了存储这些信息，文件系统通常有一个inode
（3）inode表：保存inode数组
（4）位图：用于数据区域，另一种用于inode表。记录数据或inode是空闲还是在使用
（5）超级块：包含特定文件系统信息，例如文件系统中有多少个inode和数据块、inode表开始位置等等
2inode：index node（索引节点）缩写，这些节点最初放在一个数组中，在访问特定inode时会使用该数组的索引，每个inode都由一个数字（inumber）隐式引用，给定这个数字，应该能够计算磁盘上相应节点的位置
3多级索引
（1）间接指针：它不是指向包含用户数据的块，而是指向包含更多指针的块，每个指针指向用户数据（也就是说，块里存储的不是数据信息，而是数据信息的地址，这样inode就可以放下更多的数据信息）
4读取文件：需要根据路径名不断向下读取，当读取到需要文件的信息时，读完之后需要写入信息（最后访问时间）
5写入文件：
（1）读取inode位图（查找空闲inode）
（2）写入inode位图（将其标记为已分配）
（3）读取与写入新的inode（初始化）
（4）写入真正的数据块本身
第41章（局部性和快速文件系统）
1快速文件系统（FFS），让文件系统的结构和分配策略更加合理，使得性能提高
（1）组织结构：柱面组：通过在同一组中放置两个文件，ffs可以确保先后访问两个文件不会导致穿越磁盘的长时间寻道
（2）对于目录：找到分配数量少的柱面组和大量自由inode，并将目录数据和inode放在该分组中。
（3）对于文件：确保将文件的数据块分配到与其inode相同的组中，从而防止inode和数据之间的长时间寻道，同时，将位于同一目录中的所有文件，放在它们所在目录的柱面组中
第42章（崩溃一致性：FSCK和日志）
1崩溃场景
一次写入成功
（1）只将数据块写入磁盘：数据在磁盘上，但是没有指向它的inode，也没有表示块已分配的位图，好像根本没有写入过一样
（2）只有更新inode写入磁盘：将从磁盘读取垃圾数据（文件系统不一致：位图说明数据块未分配，但是inode说它分配了）
（3）只有更新后的位图写入了磁盘：导致空间泄露，永远也不会使用那个被标记的块
两次写入成功
（1）inode和位图写入磁盘：那个块是个垃圾数据
（2）写入inode和数据块：inode和位图存在不一致
（3）写入位图和数据块：文件系统不一致，而且写入数据也不知道放在哪。
2 fsck
（1）超级块：首先检查超级块是否合理，主要是进行健全性检查，目的是找到一个可疑的超级块，在这种情况下，系统可以使用超级块的副本
（2）空闲块：扫描inode、间接块、双重间接块，以了解文件系统分配的块，如果位图和inode不一致，则通过信任inode内的信息来解决
（3）inode状态：检查每个inode是否存在损坏或其他问题。如果inode存在问题，不易修复，则inode被认为是可以的，被清除，位图也相应更新
（4）inode链接：验证每个已分配的inode的链接数（链接计数表示包含此特定文件的引用的不同目录的数量）
（5）重复：检查重复指针，即两个不同的inode引用同一个块的情况，
（6）坏块：检查到坏块指针，则从中删除
（7）目录检查：目录必须是特定的格式
3日志：更新磁盘时，首先写下一点提示，描述你想要做的事情，这个提示写入一个结构，并组织成日志
（1）日志写入：将事务的内容写入日志，等待这些写入完成
（2）日志提交：将事务提交块写入日志，等待写完成（这一步是防止在写入日志过程中断电）
（3）加检查点：将待处理的元数据和数据更新写入文件系统中的最终位置
（4）释放：一段时间后，更新日志超级块，在日志中标记该事务为空闲
4恢复
（1）如果崩溃发生在2之前，跳过待执行的更新
（2）如果崩溃发生在3之前，扫描日志，并查到已提交到磁盘的事务。然后，这些事务被重放
5批处理日志更新：不会一次一个地提交每个更新
6元数据日志：用户数据没有写入日志，先将数据块写入磁盘
（1）数据写入：将数据写入最终位置
（2）日志元数据写入：将开始块和元数据写入日志
（3）日志提交：将事务提交块写入日志
（4）加检查点元数据：将元数据更新的内容写入文件系统中的最终位置
（5）释放：在超级块中将事务标记为空闲
第43章（日志结构文件系统）
1日志结构文件系统（LFS）：写入磁盘时，LFS首先将所有更新缓冲在内存段内，当段满了，它会在一次长时间的顺序传输中写入磁盘，并传输到磁盘的未使用部分，LFS永远不会覆写现有的数据，而是始终将段写入空闲位置
2因为inode分散在磁盘各个位置上，所以引入了imap结构，它将inode号作为输入，并生成最新版本的inode的磁盘地址，imap存储在新信息的旁边，imap数组存储在标记为imap的块中
3检查点区域（CR）：包含指向最新的inode映射片段的指针（即地址），因此磁盘布局的整体结构包含一个检查点区域，每个inode映射块包含inode的地址，inode指向文件
4目录：读取目录数据块，然后提供到所需inode 的映射，再次查询inode映射，即可找到所需文件
5LFS清理过程：清理程序定期读入许多旧的段，确定哪些块在这些段中存在，然后写出一组新的段，只包含其中活着的块，从而释放旧块
6确定块的死活：对于每个数据块，LFS包括其inode及其偏移量，该信息记录在段摘要块中，根据偏移量判断inode是否是旧的版本
7崩溃恢复和日志
（1）确保cr更新以原子方式：LFS保留了两个cr，每个位于磁盘的一端，并交替写入，当更新时，先写出一个头（带有时间），然后写cr的主体，最后写出最后一部分（也有时间），如果系统在cr更新崩溃，可以通过查看时间来检测，LFS始终选择使用具有一致时间更新cr
（2）因为LFS隔30s左右更新cr，所以最后的可能没到30s的数据会失去，基本思想：从最后一个检查点区域开始，找到日志的结尾，使用它读取下一个段，并检查是否有任何有效更新，如果有，就相应更新，从而恢复自上一个检查点以来写入的大部分数据。
第44章（数据完整性和保护）
简单的说扇区是对硬盘而言，块是对文件系统而言。
1潜在扇区错误（LSE）：当磁盘扇区以某种方式讹误时（磁头由于某种原因接触到表面），则可能会出现讹误表面，使得数据位不可读。但是驱动器使用磁盘内纠错码来确定块中的磁盘位是否良好，并且在某些情况下，修复他们，如果无法修复，则在发出请求读取他们时，磁盘会返回错误（很容易处理，当检测到错误时，存储系统应该用它具有的任何冗余机制来返回正确的数据）
2块讹误：磁盘块出现讹误，磁盘本身无法检测（有缺陷的磁盘固件可能会将块写入错误的位置）
（1）解决办法：主要放在检测错误上，主要机制就是校验和，校验和就是一个函数的结果，该函数以一块数据作为输入，并计算这段数据的函数，产生数据内容的小概要，这段概要就是校验和，与数据一起存储，在访问时确认数据当前校验和与原始存储值匹配，从而进行检测
3校验和的分布：因为只能以扇区大小的块和其倍数写入，一些厂商使用520字节扇区格式化硬盘，额外的8个字节用来存储校验和，没有此类功能的磁盘会将校验和打包存储到512字节的扇区中（如n个校验和在一个扇区，后面跟着n个数据块），前者更新时只需一次写入，后者需要两次写入
4错误的写入：正确的将数据写入磁盘，但位置错误
解决办法：在校验和中加入更多的数据，加入磁盘号与扇区偏移量
5丢失的写入：当设备通知上层写入已完成时，但事实上它从未持久，在磁盘上留下的是就内容
6磁盘擦净：通过定期读取系统的每个块，并检查校验和是否有效
