操作系统导论

第 1章 关于本书的对话 1 第  2章 操作系统介绍  3 2.1  虚拟化CPU  4 2.2  虚拟化内存  6 2.3  并发  7 2.4  持久性  9 2.5  设计目标  11 2.6  简单历史  12 2.7  小结  15 参考资料  15 第  1部分 虚拟化 第3章  关于虚拟化的对话  18 第4章  抽象：进程  19 4.1  抽象：进程  20 4.2  进程API  20 4.3  进程创建：更多细节  21 4.4  进程状态  22 4.5  数据结构  24 4.6  小结  25 参考资料  25 作业  26 问题  26 第5章  插叙：进程API  28 5.1  fork()系统调用  28 5.2  wait()系统调用  29 5.3  最后是exec()系统调用  30 5.4  为什么这样设计API  32 5.5  其他API  34 5.6  小结  34 参考资料  34 作业（编码）  35 问题  35 第6章  机制：受限直接执行  37 6.1  基本技巧：受限直接执行  37 6.2  问题1：受的操作  38 6.3  问题2：在进程之间切换  40 6.4  担心并发吗  44 6.5  小结  45 参考资料  45 作业（测量）  47 第7章  进程调度：介绍  48 7.1  工作负载假设  48 7.2  调度指标  49 7.3  优选先出（FIFO）  49 7.4  最短任务优先（SJF）  50 7.5  最短完成时间优先（STCF）  51 7.6  新度量指标：响应时间  52 7.7  轮转  52 7.8  结合I/O  54 7.9  无法预知  54 7.10  小结  55 参考资料  55 作业  56 问题  56 第8章  调度：多级反馈队列  57 8.1  MLFQ：基本规则  57 8.2  尝试 #1：如何改变优先级  58 8.3  尝试 #2：提升优先级  60 8.4  尝试 #3：更好的计时方式  61 8.5  MLFQ调优及其他问题  61 8.6  MLFQ：小结  62 参考资料  63 作业  64 问题  64 第9章  调度：比例份额  65 9.1  基本概念：彩票数表示份额  65 9.2  彩票机制  66 9.3  实现  67 9.4  一个例子  68 9.5  如何分配彩票  68 9.6  为什么不是确定的  69 9.7  小结  70 参考资料  70 作业  71 问题  71 第  10章 多处理器调度（高级）  73 10.1  背景：多处理器架构  73 10.2  别忘了同步  75 10.3  最后一个问题：缓存亲和度  76 10.4  单队列调度  76 10.5  多队列调度  77 10.6  Linux 多处理器调度  79 10.7  小结  79 参考资料  79 第  11章 关于CPU虚拟化的总结对话  81 第  12章 关于内存虚拟化的对话  83 第  13章 抽象：地址空间  85 13.1  早期系统  85 13.2  多道程序和时分共享  85 13.3  地址空间  86 13.4  目标  87 13.5  小结  89 参考资料  89 第  14章 插叙：内存操作API  91 14.1  内存类型  91 14.2  malloc()调用  92 14.3  free()调用  93 14.4  常见错误  93 14.5  底层操作系统支持  96 14.6  其他调用  97 14.7  小结  97 参考资料  97 作业（编码）  98 问题  98 第  15章 机制：地址转换  100 15.1  假设  101 15.2  一个例子  101 15.3  动态（基于硬件）重定位  103 15.4  硬件支持：总结  105 15.5  操作系统的问题  105 15.6  小结  108 参考资料  109 作业  110 问题  110 第  16章 分段  111 16.1  分段：泛化的基址/界限  111 16.2  我们引用哪个段  113 16.3  栈怎么办  114 16.4  支持共享  114 16.5  细粒度与粗粒度的分段  115 16.6  操作系统支持  115 16.7  小结  117 参考资料  117 作业  118 问题  119 第  17章 空闲空间管理  120 17.1  假设  120 17.2  底层机制  121 17.3  基本策略  126 17.4  其他方式  128 17.5  小结  130 参考资料  130 作业  131 问题  131 第  18章 分页：介绍  132 18.1  一个简单例子  132 18.2  页表存在哪里  134 18.3  列表中究竟有什么  135 18.4  分页：也很慢  136 18.5  内存追踪  137 18.6  小结  139 参考资料  139 作业  140 问题  140 第  19章 分页：快速地址转换（TLB）  142 19.1  TLB的基本算法  142 19.2  示例：访问数组  143 19.3  谁来处理TLB未命中  145 19.4  TLB的内容  146 19.5  上下文切换时对TLB的处理  147 19.6  TLB替换策略  149 19.7  实际系统的TLB表项  149 19.8  小结  150 参考资料  151 作业（测量）  152 问题  153 第  20章 分页：较小的表  154 20.1  简单的解决方案：更大的页  154 20.2  混合方法：分页和分段  155 20.3  多级页表  157 20.4  反向页表  162 20.5  将页表交换到磁盘  163 20.6  小结  163 参考资料  163 作业  164 问题  164 第  21章 超越物理内存：机制  165 21.1  交换空间  165 21.2  存在位  166 21.3  页错误  167 21.4  内存满了怎么办  168 21.5  页错误处理流程  168 21.6  交换何时真正发生  169 21.7  小结  170 参考资料  171 第  22章 超越物理内存：策略  172 22.1  缓存管理  172 22.2  很优替换策略  173 22.3  简单策略：FIFO  175 22.4  另一简单策略：随机  176 22.5  利用历史数据：LRU  177 22.6  工作负载示例  178 22.7  实现基于历史信息的算法  180 22.8  近似LRU  181 22.9  考虑脏页  182 22.10  其他虚拟内存策略  182 22.11  抖动  183 22.12  小结  183 参考资料  183 作业  185 问题  185 第  23章 VAX/VMS虚拟内存系统  186 23.1  背景  186 23.2  内存管理硬件  186 23.3  一个真实的地址空间  187 23.4  页替换  189 23.5  其他漂亮的虚拟内存技巧  190 23.6  小结  191 参考资料  191 第  24章 内存虚拟化总结对话  193 第  2部分 并发 第  25章 关于并发的对话  196 第  26章 并发：介绍  198 26.1  实例：线程创建  199 26.2  为什么更糟糕：共享数据  201 26.3  核心问题：不可控的调度  203 26.4  原子性愿望  205 26.5  还有一个问题：等待另一个   线程  206 26.6  小结：为什么操作系统课要研究   并发  207 参考资料  207 作业  208 问题  208 第  27章 插叙：线程API  210 27.1  线程创建  210 27.2  线程完成  211 27.3  锁  214 27.4  条件变量  215 27.5  编译和运行  217 27.6  小结  217 参考资料  218 第  28章 锁  219 28.1  锁的基本思想  219 28.2  Pthread锁  220 28.3  实现一个锁  220 28.4  评价锁  220 28.5  控制中断  221 28.6  测试并设置指令（原子交换）  222 28.7  实现可用的自旋锁  223 28.8  评价自旋锁  225 28.9  比较并交换  225 28.10  链接的加载和条件式存储指令  226 28.11  获取并增加  228 28.12  自旋过多：怎么办  229 28.13  简单方法：让出来吧，宝贝  229 28.14  使用队列：休眠替代自旋  230 28.15  不同操作系统，不同实现  232 28.16  两阶段锁  233 28.17  小结  233 参考资料  233 作业  235 问题  235 第  29章 基于锁的并发数据结构  237 29.1  并发计数器  237 29.2  并发链表  241 29.3  并发队列  244 29.4  并发散列表  245 29.5  小结  246 参考资料  247 第30章  条件变量  249 30.1  定义和程序  250 30.2  生产者/消费者（有界缓冲区）   问题  252 30.3  覆盖条件  260 30.4  小结  261 参考资料  261 第31章  信号量  263 31.1  信号量的定义  263 31.2  二值信号量（锁）  264 31.3  信号量用作条件变量  266 31.4  生产者/消费者（有界缓冲区）   问题  268 31.5  读者—写者锁  271 31.6  哲学家就餐问题  273 31.7  如何实现信号量  275 31.8  小结  276 参考资料  276 第32章  常见并发问题  279 32.1  有哪些类型的缺陷  279 32.2  非死锁缺陷  280 32.3  死锁缺陷  282 32.4  小结  288 参考资料  289 第33章  基于事件的并发（进阶）  291 33.1  基本想法：事件循环  291 33.2  重要API：select()（或poll()）  292 33.3  使用select()  293 33.4  为何更简单？无须锁  294 33.5  一个问题：阻塞系统调用  294 33.6  解决方案：异步I/O  294 33.7  另一个问题：状态管理  296 33.8  什么事情仍然很难  297 33.9  小结  298 参考资料  298 第34章  并发的总结对话  300 第3部分  持久性 第35章  关于持久性的对话  302 第36章  I/O设备  303 36.1  系统架构  303 36.2  标准设备  304 36.3  标准协议  304 36.4  利用中断减少CPU开销  305 36.5  利用DMA进行更高效的数据   传送  306 36.6  设备交互的方法  307 36.7  纳入操作系统：设备驱动程序  307 36.8  案例研究：简单的IDE磁盘驱动   程序  309 36.9  历史记录  311 36.10  小结  311 参考资料  312 第37章  磁盘驱动器  314 37.1  接口  314 37.2  基本几何形状  314 37.3  简单的磁盘驱动器  315 37.4  I/O时间：用数学  318 37.5  磁盘调度  320 37.6  小结  323 参考资料  323 作业  324 问题  324 第38章  廉价冗余磁盘阵列（RAID）  326 38.1  接口和RAID内部  327 38.2  故障模型  327 38.3  如何评估RAID  328 38.4  RAID 0级：条带化  328 38.5  RAID 1级：镜像  331 38.6  RAID 4级：通过奇偶校验节省   空间  333 38.7  RAID 5级：旋转奇偶校验  336 38.8  RAID比较：总结  337 38.9  其他有趣的RAID问题  338 38.10  小结  338 参考资料  339 作业  340 问题  340 第39章  插叙：文件和目录  342 39.1  文件和目录  342 39.2  文件系统接口  343 39.3  创建文件  343 39.4  读写文件  344 39.5  读取和写入，但不按顺序  346 39.6  用fsync()立即写入  346 39.7  文件重命名  347 39.8  获取文件信息  348 39.9  删除文件  349 39.10  创建目录  349 39.11  读取目录  350 39.12  删除目录  351 39.13  硬链接  351 39.14  符号链接  353 39.15  创建并挂载文件系统  354 39.16  总结  355 参考资料  355 作业  356 问题  356 第40章  文件系统实现  357 40.1  思考方式  357 40.2  整体组织  358 40.3  文件组织：inode  359 40.4  目录组织  363 40.5  空闲空间管理  364 40.6  访问路径：读取和写入  364 40.7  缓存和缓冲  367 40.8  小结  369 参考资料  369 作业  370 问题  371 第41章  局部性和快速文件系统  372 41.1  问题：性能不佳  372 41.2  FFS：磁盘意识是解决方案  373 41.3  组织结构：柱面组  373 41.4  策略：如何分配文件和目录  374 41.5  测量文件的局部性  375 41.6  大文件例外  376 41.7  关于FFS的其他几件事  377 41.8  小结  378 参考资料  378 第42章  崩溃一致性：FSCK和日志  380 42.1  一个详细的例子  380 42.2  解决方案＃1：文件系统检查   程序  383 42.3  解决方案＃2：日志 （或预写日志）  384 42.4  解决方案＃3：其他方法  392 42.5  小结  393 参考资料  393 第43章  日志结构文件系统  395 43.1  按顺序写入磁盘  396 43.2  顺序而高效地写入  396 43.3  要缓冲多少  397 43.4  问题：查找inode  398 43.5  通过间接解决方案：inode映射  398 43.6  检查点区域  399 43.7  从磁盘读取文件：回顾  400 43.8  目录如何  400 43.9  一个新问题：垃圾收集  401 43.10  确定块的死活  402 43.11  策略问题：要清理哪些块，   何时清理  403 43.12  崩溃恢复和日志  403 43.13  小结  404 参考资料  404 第44章  数据完整性和保护  407 44.1  磁盘故障模式  407 44.2  处理潜在的扇区错误  409 44.3  检测讹误：校验和  409 44.4  使用校验和  412 44.5  一个新问题：错误的写入  412 44.6  最后一个问题：丢失的写入  413 44.7  擦净  413 44.8  校验和的开销  414 44.9  小结  414 参考资料  414 第45章  关于持久的总结对话  417 第46章  关于分布式的对话  418 第47章  分布式系统  419 47.1  通信基础  420 47.2  不可靠的通信层  420 47.3  可靠的通信层  422 47.4  通信抽象  424 47.5  远程过程调用（RPC）  425 47.6  小结  428 参考资料  429 第48章  Sun的网络文件系统（NFS）  430 48.1  基本分布式文件系统  430 48.2  交出NFS  431 48.3  关注点：简单快速的服务器崩溃   恢复  431 48.4  快速崩溃恢复的关键：无状态  432 48.5  NFSv2协议  433 48.6  从协议到分布式文件系统  434 48.7  利用幂等操作处理服务器故障  435 48.8  提高性能：客户端缓存  437 48.9  缓存一致性问题  437 48.10  评估NFS的缓存一致性  439 48.11  服务器端写缓冲的隐含意义  439 48.12  小结  440 参考资料  440 第49章  Andrew文件系统（AFS）  442 49.1  AFS版本1  442 49.2  版本1的问题  443 49.3  改进协议  444 49.4  AFS版本2  444 49.5  缓存一致性  446 49.6  崩溃恢复  447 49.7  AFSv2的扩展性和性能  448 49.8  AFS：其他改进  450 49.9  小结  450 参考资料  451 作业  452 问题  452 第50章  关于分布式的总结对话  453 附录A  关于虚拟机监视器的对话  454 附录B  虚拟机监视器  455 附录C  关于监视器的对话  466 附录D  关于实验室的对话  467 附录E  实验室：指南  468 附录F  实验室：系统项目  478 附录G  实验室：xv6项目  480