操作系统导论

我对这本书的评价是：通俗易懂而不失准确性，是非常好的一本书。从虚拟化、并发、持久性三个方面揭开了操作系统神秘的面纱，如何让每个程序自己看起来像是独占 CPU、内存？如何提高 CPU 的利用率？数据是如何存储的？

大纲 大纲

介绍 介绍

操作系统实际上做了什么？它取得CPU、内存或磁盘等物理资源（resources），并对它们进行虚拟化（virtualize）。它处理与并发（concurrency）有关的麻烦且棘手的问题。它持久地（persistently）存储文件，从而使它们长期安全。

• 多个程序同时运行：CPU 虚拟化
• 每个进程好像都有独立的内存：内存虚拟化
• 同时处理很多事情时会出现一系列问题：并发
• 内存易失，需要存储数据：持久性

CPU 虚拟化 CPU 虚拟化

操作系统如何启动并运行一个程序？进程创建实际如何进行？操作系统运行程序必须做的第一件事是将代码和所有静态数据（例如初始化变量）加载（load）到内存中，加载到进程的地址空间中。然后在运行此进程之前还需要执行其他一些操作，必须为程序的运行时栈（run-time stack或stack）分配一些内存。操作系统也可能为程序的堆（heap）分配一些内存。操作系统还将执行一些其他初始化任务，特别是与输入/输出（I/O）相关的任务。最后启动程序，在入口处运行，即main()。OS将CPU的控制权转移到新创建的进程中，从而程序开始执行。

• 进程，运行中的程序，PCB 里存了不少东西，是上下文切换必须的，比如寄存器的值、栈指针等，OS 有进程列表
• OS 要跟踪进程的状态（就绪、运行、阻塞、初始、最终）、 OS 提供进程的 API（创建、销毁、等待等）
• CPU 虚拟化有底层机制和上层策略，机制是受限直接执行，策略是各种调度算法。
• 在受限直接执行中，引入了硬件不同的执行模式（用户模式、内核模式），硬件（CPU）原生提供了陷入和从陷阱返回的指令，CPU 出厂就支持中断（时钟、键盘、网卡）、异常（缺页、除零、非法指令）、系统调用门（syscall/int 0x80）这些事件，也提供了 iret/sysret 这种返回指令由操作系统（内核汇编代码）调用。
• 时钟中断可以让 OS 重新获得控制权，然后便能决定是否要切换到其他进程，这是调度器要做的事。
• 进程切换时要进行上下文切换，操作系统、硬件密切合作。
• 调度算法很多，先通过工作负载假设把问题简化，引出了 FIFO、SJF、STCF 算法并计算了平均周转时间，然后是考虑到响应时间提出了 RR 算法。一步步放宽假设，最后介绍了多级反馈队列（五大规则，能利用最近预测未来）、比例（公平）调度（彩票 & 步长，随机近似与确定性）。
• 单处理调度之后，是多处理器调度，他俩的核心区别是缓存的使用和共享数据的方式，多核处理器有底层的缓存一致性机制，但仍避免不了共享数据需要的加锁才能保证预期结果。可以简单用单队列，但存在缓存亲和性和加锁的问题，用多队列就需要考虑负载不均，需要工作窃取。
• Linux 社区对采用哪种调度策略，一直没有共识。

内存虚拟化 内存虚拟化

用户程序生成的每个地址都是虚拟地址（every address generated by a user program is a virtual address）。操作系统只是为每个进程提供一个假象，具体来说，就是它拥有自己的大量私有内存。在一些硬件帮助下，操作系统会将这些假的虚拟地址变成真实的物理地址，从而能够找到想要的信息。

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

• 抽象是地址空间，给进程一个私有的大大的地址空间，怎么把虚拟地址映射到物理地址？
• 整个放进去：如果是整块地址空间放进物理内存，那么硬件有基址寄存器+界限寄存器就可以了，物理地址=虚拟地址+base。但是这有很大的空间浪费，地址空间那么大，栈和堆之间那些空间都没用上。
• 分段：将地址空间分为代码段、栈段、堆段，每个段都有一对基址寄存器+界限寄存器，在虚拟地址中用几个位体现一下用的是哪个段，物理地址=虚拟地址的偏移量+段 base。可是会造成外部碎片。
• 分页：将地址空间、物理内存都分成小的页，一般是 4kB， 虚拟页对应了物理页帧，完全避免了外部碎片。此时需要 OS 帮忙存储页表，物理地址=页表(虚拟地址对应的页号)+虚拟地址的偏移量。可是这会造成两个问题：一是地址转换变慢了，二是页表非常大且大量的页表项都没有用。
• TLB 快速地址转换：硬件上了个缓存，利用时间和空间局部性能在一定程度上避免访问页表，先看 TLB 有没有，TLB 是并行查找，性能大大提升。
• 分段+分页：混合方法，只存有用的部分的页表，分段的那些个寄存器都保留，此时段基址寄存器就要存对应的页表地址了，界限寄存器就是页表的结尾了。可是又带来了外部碎片，分段框定连续空间都做法总有内存浪费。
• 多级页表：这是现代系统用的多的，引入了页目录，就是页表的页表，把页表也按页大小拆分，此时页表就能分散放在内存的任何位置了，并且如果整片页表没用就在页目录项标记无效即可，不用存了，故而非常紧凑。如果页表还是太大，超过物理内存了怎么办？
• 页的换出：交换到硬盘上，硬件触发缺页中断/异常，让操作系统来重新加载页。决定换出哪个页呢？FIFO、随机都没有体现页的重要性，LRU 不错，但是实现起来复杂，每次访存都得记录，故而用时钟算法来近似 LRU。

并发 并发

单个线程的状态与进程状态非常类似。线程有一个程序计数器（PC），记录程序从哪里获取指令。每个线程有自己的一组用于计算的寄存器。所以，如果有两个线程运行在一个处理器上，从运行一个线程（T1）切换到另一个线程（T2）时，必定发生上下文切换（context switch）。线程之间的上下文切换类似于进程间的上下文切换。对于进程，我们将状态保存到进程控制块（Process Control Block，PCB）。现在，我们需要一个或多个线程控制块（Thread Control Block，TCB），保存每个线程的状态。但是，与进程相比，线程之间的上下文切换有一点主要区别： 地址空间保持不变（即不需要切换当前使用的页表） 。

线程和进程之间的另一个主要区别在于栈。在简单的传统进程地址空间模型（我们现在可以称之为单线程（single-threaded）进程）中，只有一个栈，通常位于地址空间的底部。然而，在多线程的进程中，每个线程独立运行，当然可以调用各种例程来完成正在执行的任何工作。不是地址空间中只有一个栈，而是 每个线程都有一个栈 。

锁就是一个变量，因此我们需要声明一个某种类型的锁变量（lock variable，如上面的mutex），才能使用。这个 锁变量（简称锁）保存了锁在某一时刻的状态。它要么是可用的（available，或unlocked，或free），表示没有线程持有锁，要么是被占用的（acquired，或locked，或held），表示有一个线程持有锁，正处于临界区。 我们也可以保存其他的信息，比如持有锁的线程，或请求获取锁的线程队列，但这些信息会隐藏起来，锁的使用者不会发现。锁让程序员获得一些控制权。通过给临界区加锁，可以保证临界区内只有一个线程活跃。锁将原本由操作系统调度的混乱状态变得更为可控。

线程可以使用条件变量（condition variable），来等待一个条件变成真。 条件变量是一个显式队列，当某些执行状态（即条件，condition）不满足时，线程可以把自己加入队列，等待（waiting）该条件。 另外某个线程，当它改变了上述状态时，就可以唤醒一个或者多个等待线程（通过在该条件上发信号），让它们继续执行。Dijkstra最早在“私有信号量”中提出这种思想。Hoare 后来在关于观察者的工作中，将类似的思想称为条件变量。

事实上，Dijkstra及其同事发明了信号量，作为与同步有关的所有工作的单一原语。你会看到，可以使用信号量作为锁和条件变量。信号量是有一个整数值的对象，可以用两个函数来操作它。在POSIX标准中，是 sem_wait()和 sem_post() 。因为信号量的初始值能够决定其行为，所以首先要初始化信号量，才能调用其他函数与之交互。sem_wait() 要么立刻返回（调用 sem_wait() 时，信号量的值大于等于1），要么会让调用线程挂起，直到之后的一个post操作。sem_post() 并没有等待某些条件满足。它直接增加信号量的值，如果有等待线程，唤醒其中一个。当信号量的值为负数时，这个值就是等待线程的个数。

• 新的抽象是线程，一个进程可以有多个线程，这些线程共享一个地址空间。
• 线程是由操作系统调度的，多个线程可以共享变量，当并发更新时会产生让人意想不到的结果，这就是竞态条件。而对应的代码被称为临界区。临界区一定不能让多个线程同时执行。解决这个问题需要硬件支持，提供同步原语。相应的工具有锁、条件变量，以及信号量。
• 锁能提供互斥，也被称为互斥量。锁的实现有三种，控制中断缺点多，硬件比较并交换等的支持却有不必要的自旋，最好的方法是硬件支持+操作系统 yield 调用在自旋时放弃 CPU。有了锁之后，就可以构造出各种基于锁的并发数据结构，比如并发散列表。
• 条件变量在线程检查某个条件满足之后才运行的情况下非常有用，条件变量本身是个队列，当执行状态不满足时，线程可以把自己加入队列，来等待该条件。它有两个操作 wait 和 signal 代表了睡眠和唤醒。调用 wait 时线程释放锁并睡眠，被 signal 唤醒时会进入就绪状态，会从暂停的地方开始继续执行。一个利用两个条件变量 empty 和 full 来解决的经典问题就是生产者和消费者问题，也称有界缓冲区问题。除了 signal唤醒一个线程外，还有 broadcast 可以唤醒所有线程，通常用于不确定要唤醒哪个线程的场景。
• 信号量是一个有数值的对象，当他的值为 1 时是锁，值为 0 时是条件变量。它有 wait 和 post 两个操作，wait 会 -1，要么立即返回要么进入等待队列，post 会 +1，若有等待线程就会唤醒一个。用信号量也能解决有界缓冲区问题，还有哲学家就餐问题、读写锁等。可以用锁和条件变量来实现信号量。
• 并发编程容易出缺陷，主要分为非死锁缺陷和死锁缺陷。死锁的四个必要条件破坏一个就能预防，也可以检查死锁并重启，还可以用银行家算法来进行聪明的调度。非死锁主要指的是原子性、顺序问题。当然了，更好的解决方案是开发新的并发编程模型，比如 map-reduce、事件循环这种无锁的。
• 事件循环的并发编程模型很容易理解，就是一个单线程循环检查，串行处理事件。但也存在一些问题，比如如果有阻塞的系统调用会让整个系统卡死，因而得用异步 IO等。

持久性 持久性

TODO: 待更新

问题研讨 问题研讨