《操作系统导论》读书笔记，待更新…
资源
百度网盘资源链接（包含书中代码和本书英文原版 pdf ）提取码：ffhc
官网
GitHub
目录
第 2 章 操作系统介绍
- 将单个 CPU（或其中一小部分）转换为看似无限数量的 CPU，从而让许多程序看似同时运行，这就是所谓的虚拟化 CPU（virtualizing the CPU）。
第 1 部分 虚拟化
第 4 章 抽象：进程
时分共享（和空分共享）
进程状态：运行、就绪、阻塞
第 5 章 插叙：进程 API
本章讲了 UNIX 系统的三个系统调用：fork()、exec() 和 wait()。
第 6 章 机制：受限直接执行
本章讲了用户模式和内核模式、进程切换、保存和恢复上下文。
第 7 章 进程调度：介绍
本章开始对任务有几项假设，然后采用逐渐放宽假设的方式由浅入深讨论各种情况下的调度算法思想。
以周转时间为指标，有下列三种调度算法：
- 先进先出（First In First Out, FIFO）或先到先服务（First Come First Served, FCFS）
- 最短任务优先（Shortest Job First, SJF）
- 最短完成时间优先（Shortest Time-to-Completion First, STCF）或最短完成时间优先（Preemptive Shortest Job First, PSJF）
以响应时间为指标：
- 轮转（Round-Robin, RR）
第 8 章 调度：多级反馈队列
MLFQ（multi-level feedback queue）规则：
- 规则 1：如果 A 的优先级 > B 的优先级，运行 A（不运行 B）。
- 规则 2：如果 A 的优先级 = B 的优先级，轮转运行 A 和 B。
- 规则 3：工作进入系统时，放在最高优先级（最上层队列）。
- 规则 4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次 CPU），就降低其优先级（移入低一级队列）。
- 规则 5：经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。
第 9 章 调度：比例份额
本章讲了彩票调度（lottery scheduling），其实现类似于我的 Blackjack 随机发牌算法实现。
另外一种是步长调度，思想也很简单：按步长增加进度，每次选进度最低的进程运行。
但这两种都没有作为 CPU 调度程序被广泛使用。一是因为它们不适合 I/O ，二是很难确定每个进程的“票数”。
第 10 章 多处理器调度（高级）
- 本章介绍了多处理器调度的不同方法。其中单队列的方式（SQMS）比较容易构建，负载均衡较好，但在扩展性和缓存亲和度方面有着固有的缺陷。多队列的方式（MQMS）有很好的扩展性和缓存亲和度，但实现负载均衡却很困难，也更复杂。
第 13 章 抽象：地址空间
本章大概地介绍了虚拟化内存的相关知识。
第 14 章 插叙：内存操作 API
本章讲了 C 语言的 malloc() 和 free() 函数和相关内存管理知识。
第 15 章 机制：地址转换
- 将虚拟地址转换为物理地址，这正是所谓的地址转换（address translation）技术。
本章讲了基址加界限的动态重定位原理。
第 16 章 分段
- 在典型的地址空间里有 3 个逻辑不同的段：代码、栈、和堆
分段后管理物理的空闲空间，减小内存碎片有两种常见解决方案：
- 紧凑物理内存，重新安排原有的段。
- 空闲列表管理算法。包括最优匹配、最坏匹配、首次匹配、伙伴算法等，这几个具体算法书中本章没细讲。正如书中所讲，方案越多越说明这个问题没有最好的办法。。。
第 17 章 空闲空间管理
本章讲了空闲列表管理算法。包括上章中提到的各种具体的匹配算法。
第 18 章 分页：介绍
分页不会导致外部碎片，因为分页（按设计）将内存划分为固定大小的单元。其次，它非常灵活，支持稀疏虚拟地址空间。
第 19 章 分页：快速地址转换（TLB）
本章讲了 TLB 相关的知识。
第 20 章 分页：较小的表
- 大内存页会导致每页内的浪费，这被称为内部碎片（internal fragmentation）问题（因为浪费在分配单元内部）。
本章讲了多级页表的相关知识。
第 21 章 超越物理内存：机制
本章讲了内存换页的相关知识。
第 22 章 超越物理内存：策略
本章讲了操作系统的换页策略。包括 FIFO、随机、LRU，其中介绍了近似 LRU 的实现，以及各种策略在不同情况下的命中率比较。
第 23 章 VAX/VMS 虚拟内存系统
本章介绍了 VAX/VMS 操作系统的虚拟内存管理器。
第 2 部分 并发
第 26 章 并发：介绍
本章简单介绍了并发中的几个术语，并引出原子性和原语等概念。
第 27 章 插叙：线程 API
本章介绍了 pthread 库，包括线程创建，通过锁创建互斥执行，通过条件变量的信号和等待。
第 28 章 锁
本章介绍了几个原子指令实现和锁的实现。有几个地方比较难还不是很懂。
第 29 章 基于锁的并发数据结构
本章讲了计数器、链表、队列、散列表在并发加锁中的实现。
第 30 章 条件变量
本章讲了条件变量的概念及应用，并介绍了著名的生产者/消费者问题，以及覆盖条件。
第 31 章 信号量
本章讲了信号量相关知识和用法，介绍了哲学家就餐问题。
第 32 章 常见并发问题
本章讨论并发编程中非死锁缺陷和死锁产生的原因以及解决方案。
第 33 章 基于事件的并发（进阶）
本章讲了基于事件的并发相关实现和常见问题。
第 3 部分 持久性
第 36 章 I/O 设备
本章讲了中断和 DMA ，以及访问设备寄存器的两种方式：I/O 指令和内存映射 I/O。另外还介绍了设备驱动程序的概念。
第 37 章 磁盘驱动器
本章讲了磁盘的大致结构，以及介绍了常见的磁盘调度算法。
第 38 章 廉价冗余磁盘阵列（RAID）
本章介绍了多种级别的 RAID 。
第 39 章 插叙：文件和目录
本章介绍了文件和目录在操作系统底层的实现和各种操作。
第 40 章 文件系统实现
本章介绍了构建文件系统所需的基本机制，粗略一看。
第 41 章 局部性和快速文件系统
本章介绍了 FFS（快速文件系统）的相关知识，粗略浏览了一下。
第 42 章 崩溃一致性：FSCK 和日志
本章介绍了崩溃一致性的问题，大致翻了一翻。
