可能是最简单的操作系统书籍

《操作系统导论》，我是通过 starkwang（

这本书的作者非常佛性，将原版书直接开源了，如果英语水平还不错，可以直接看原版，中文的翻译很多地方翻译的都不地道。原版大概是 08 年出版，而国内的翻译已经迟来了 10 年。

本文将从 4 个方面展开。虚拟化，并发，持久性，分布式系统，也对应此书的 4 大部分，我会挑一些重点内容总结。

程序员肯定遇到过面试官问进程和线程的区别。进程是操作系统基本抽象，方便操作系统管理程序。一般进程就是运行中的程序，进程之间相互隔离，通过远程过程调用（Remote Process Call，RPC） 通信。线程属于进程，一个进程下可以创建多个线程，为了最大化利用进程。

首先得理解进程之间为什么需要调度。一个操作系统有多个应用，如果没有调度，一个进程可以恶意占用整个操作系统。如何控制进程之间的调度。首先，操作系统需要有控制权，所以就引入时钟中断（Clock Interrupt），进程每隔一段时间，将控制权还给操作系统，操作系统决定将下次的执行权限赋予哪个进程，这个过程，必须要调度算法协调多方。

进程调度的策略有先进先出，短任务优先，最短完成时间优先，多级反馈，比例份额。

先进先出（FIFO）策略，先进先出，保证每一个进程都有执行时间，完全的公平。但是越是理想情况，越是不符合现实。我们需要一种有优先级的调度策略。

短任务优先（SJF）策略，计算任务的完成时间，越短越优先，这和超市排队一样，如果你只买了口香糖，但是却要排长长的队，效率很低，所以有些商场会有“零散购物”通道，这样就大大增加了效率。

最短完成时间优先（STCF）策略，SJF 有一个问题，比如 A 在运行，A 运行总共要 10s，已经运行了 1s，但是新进了两个任务 B、C 总运行时间只要 1s，这时候 B、C 就要等 A 运行完才能执行，还是阻塞了短任务。所以 STCF 就是用来解决这个，即使 A 在运行，也每隔一段监测是否有短任务需要插入。

多级反馈（MLFQ）策略，将任务分优先级，高优先的先执行，每隔一段，中低级的任务都有机会晋升为高优先级任务，避免高优先级任务一直占用 CPU，低优先任务饿死。

比例份额（proportional-share）策略，这个策略比较有意思。和彩票一样，每个任务都有份额，高优先重要的任务份额多，低优先级的少，每次 CPU 运行权都进行彩票抽奖，这样达到理论上的公平。每个任务还可以将份额再细分给子任务，这样能让任务也有控制权。

• CPU 和内存虚拟化

虚拟化的核心是内存的虚拟化，这是由操作系统实现的。操作系统通过分段和分页技术抽象了地址空间，所以进程里的内存地址是虚拟的。每个进程运行的时候，都拥有一块非常大的虚拟地址空间，像独占了整个进程一样。它实现了进程之间的隔离，也让每个进程最大化利用内存。

• 分段和分页

分段，现代操作系统的内存管理是由分段和分页组成的。一般内存分为 4 个部分，程序代码，堆，栈，空闲地址。因为运行的时候程序代码是固定的，所以放在最上面，堆需要的内容比较大，所以向下增长。而栈所需的内容比较少，放在内存的最后部分，反向增长，如下图。但是这样空闲的部分就很大，分段就是将地址空闲地址，分成不同的段，提供空闲地址的利用率。

分页，将虚拟地址转换成物理地址，分页的地址可以是连续的，物理地址可以不连续，这样将物理地址分割成一个个小页，每次置换的是否只要操作一小部分物理地址。而分页和物理地址之间，引入了页表，专门管理分页到物理地址的映射。分页除了一级分页，也可以设置二级分页，三级分页等，还是利用中间层优化性能，这是计算机一大灵丹妙药，但是复杂度也会增高。分页管理如下图。

网上也有人总结，分段是逻辑地址 -> 线性地址（虚拟地址），而分页是虚拟地址 -> 物理空间，两个分工明确。

如果每一次内存访问，都需要执行一次虚拟地址到真实地址的查找，那 I/O 非常高，所以引入了快速地址转换（Translation Lookaside Buffer，TLB），一个存储虚拟地址到真实地址的数据结构，也是程序中经常说的缓存。缓存是程序的狗皮膏药，好用，但是大范围使用反而适得其反。

有一句话说的好：计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决，而 TLB 就是这个中间层，它很好的解决了性能问题。

• 多处理器、多进程、多线程

多处理器、多进程、多线程其实都是模拟同一时间可以做多件事。想想你 1 分钟能摊一个饼，一个赚 1 块。如果 14 亿个你同时摊，那中国 1 分钟内就产生了一个亿万富翁。

书中也给出了一个例子，下面程序，在多线程情况下输出非理想的结果。

#include <stdio.h>
 #include <pthread.h>
 #include "common.h"
 #include "common_threads.h"

 static volatile int counter = 0;

 // mythread()
 //
 // Simply adds 1 to counter repeatedly, in a loop
 // No, this is not how you would add 10,000,000 to
 // a counter, but it shows the problem nicely.
 //
 void *mythread(void *arg) {
 printf("%s: begin\n", (char *) arg);
 int i;
 for (i = 0; i < 1e7; i++) {
  counter = counter + 1;
 }
 printf("%s: done\n", (char *) arg);
  return NULL;
 }

 // main()
 //
 // Just launches two threads (pthread_create)
 // and then waits for them (pthread_join)
 //
 int main(int argc, char *argv[]) {
  pthread_t p1, p2;
  printf("main: begin (counter = %d)\n", counter);
  Pthread_create(&p1, NULL, mythread, "A");
  Pthread_create(&p2, NULL, mythread, "B");

  // join waits for the threads to finish
  Pthread_join(p1, NULL);
  Pthread_join(p2, NULL);
  printf("main: done with both (counter = %d)\n",
  counter);
  return 0;
 }
prompt> ./main
main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 19345221)

作者用两个线程，分别对一个数字各加10,000,000次，理论上最终的结果是20,000,000，但是结果每次都不相同。现在只是用多线程已经出现了不可预期的结果，如果在多处理下不知道会出现更匪夷所思的结果。

• 锁，自旋锁，条件锁，信号锁

有并发就必有锁，这两个是相生相伴的。最典型的是写入冲突，并发带来了性能提升，同时带来了不确定性。而锁就是让这个过程变得更确定，这也就是为什么函数式编程能成为一大编程范式，对于某些场景，确定性比什么都重要。

一般锁的实现有自旋锁，条件锁，信号锁，无论怎么实现，核心都是将调用指令过程原子化，直白的说将可能发生冲突的地方上锁，只允许一个线程或者进程操作。

• 事件的并发，事件循环，select，poll

事件循环是并发的另一个解决方式，代替多线程。NodeJs，Nginx 都利用事件循环解决并发问题。考虑一个场景，假设服务器 1s 内能处理 100 个请求，但是客户端发起 200 个请求，服务端将所有请求加入到队列中（不考虑队列满的情况，也不考虑优先队列），再利用事件循环机制（一般是主线程有一个 for 循环），每次去队列里拿数据，保证服务端不会被流量击垮。

select 和 poll 都是重要的 API，用来接收事件，它们之间很相似，而 Linux 里在 2.6 内核中提出的 epoll，是 select 和 poll 的增强版，在这里就不展开了。

用 select 接收事件

int select(int nfds,
  fd_set *restrict readfds,
  fd_set *restrict writefds,
  fd_set *restrict errorfds,
  struct timeval *restrict timeout);

这一部分说的是硬件相关的知识，操作系统离不开硬件。

• 磁盘持久化

互联网上所有的资源，图片，音频，视频，文字这些最终都是数据，那这些数据存储到哪？答案是磁盘。磁盘提供了数据持久化的功能，当然磁盘销毁了，数据也就没了，这也就是为什么 github 前不久需要将代码存入交卷，存储到冰川之下，保存年限也不过千年。银行也将同一份数据，分别存储到不同的机器上，防止硬件问题导致数据丢失。所以磁盘持久化，不仅需要解决软件问题，也要解决硬件问题。

• 磁盘调度，磁盘驱动器

磁盘驱动器里有磁道、磁盘臂、磁头。通过找到磁头，转动磁盘臂，读取和写入磁盘数据。磁道可能有多层，所以会有一个寻道的过程。

• RAID，廉价冗余阵列磁盘

Redundant Array of Inexpensive Disks,这是利用多个磁盘一起构建更快、更大、更可靠的磁盘系统。它有 5 个等级，分别是 RAID0、RAID1、RAID2、RAID3、RAID4、RAID5。

RAID0 通过条带化提高了多个磁盘的读取速度，而 RAID1-5 都是通过不同的技术，提高条带化的速度和正确性，RAID1 用到了镜像技术，RAID4 用到了奇偶校验技术，RAID5 用到了旋转奇偶校验技术。

文件系统是操作系统中非常重要的一环。它分为目录和文件，通过树形结构组织，用 inode 数据结构记录文件的元数据。

历史遗留原因，所以的文件系统都必须实现 4 个接口，open，read，write，close。

• 文件崩溃一致性

文件崩溃一致性指当发生一些特殊情况，比如断电，写入的文件并不是断电之前的文件。通过日志记录文件的写入内容，当文件写入完成之后，核对写入文件内容是否一致，一般通过和相加判断内容是否一致，如果中途发生断电，从日志中还原文件的信息，重新写入。

分布式系统

远程过程调用（Remote Process Call，RPC），是进程之间通信的协议，虽然是远程服务器之间的调用，但是 RPC 提供了像本地函数调用的方式，在用户层面无感知。将复杂程度交给自己，提供最简单的使用方式，这是计算机的一种艺术。而下面远程文件系统之间的通信都是通过 RPC 完成的。

• NFS 和 AFS

这是两个分布式文件系统管理，前者是 Sun 公司的网络文件系统（Network File System，NFS），后者是 Andrew 文件管理（Andrew File System，AFS）。对于分布式管理系统，主要考虑文件的读写速度，以及可靠性。

NFS 读取远程文件之后，将资源存在本地，当再次访问资源即可从本地读取。但是远程文件可能会更新，所以每次读取本地文件资源时，去远程服务器获取的最后更新时间，与本地文件的最后更新时间对比，决定是否发起文件的访问。这也会带来一些问题，每次都要获取服务端文件的最后更新时间，增加了服务端带宽压力，并且很多是无效请求，远程文件没更新的请求。所以 NFS 设置了本地资源的缓存时间，比如 3s 内不去访问远程服务器，虽然获取到的文件可能不一致，但是缓解了服务端压力。

AFS 在 NFS 基础上优化了很多内容，增加了文件一致性，也提高了读写效率。第一次请求服务端，服务端记录需要更新的客户端地址。第二次请求文件资源，不再是客户端向服务端发起请求查询文件是否更新，而是当文件变更的时候，服务端主动推送消息告知客户端文件更新了，这样大大增加了效率。它还有许多优化，比如减少文件路径的查找等。不过因为 NFS 是开源协议，所以现在 NFS 吸取了 AFS 的精华之后，更为流行。

我本来以为只是简简单单的写一个观后感，没想到最后还是把重要的内容都罗列出来了，但是本文只是介绍了每个重要名词的意思，如果感兴趣，可以去深入研究。