Overview
人们对计算机的算力追求是永无止境的，当一块 CPU 上再难以集成更多的晶体管来提升算力时，多道程序设计的思想大大提高了 CPU 的利用率。
CPU 是高速设备，硬盘等是低速设备，提升 CPU 利用率的方法是并发，本质是当碰到一些需要等待低速设备协作才能完成的任务时，CPU 能转去执行其他操作而不是空转等待低速设备完成工作。例如磁盘 I/O 操作，没有 DMA（Directory Memory Access）的时候磁盘 I/O 也要经由 CPU 处理，DMA 的职责就是在磁盘和内存之间进行搬运工作（仍受 CU 的控制），有了 DMA 之后 CPU 才可以在磁盘 I/O 的时候进行其他工作。
进程（Process）： 我们把内存中一个正在运行的程序称作一个进程，进程是操作系统分配资源的基本单位（在没有引入线程的概念前，它也是系统调度的基本单位），进程间隔离性强，比较安全，进程的调度代价比较大。
为什么需要进程？ 因为我们知道 程序=数据结构+算法，语义上“程序”是一个偏向于静态的概念，仅使用“程序”二字无法体现程序是在硬盘中还是正在跑在内存中。提出进程的概念，说明了程序运行时的动态性，进程除了包括程序所包含的静态文本还包括了程序运行到某一时刻的状态信息。同时，提出进程的概念，屏蔽了 CPU 调度、内存管理等底层细节，让程序可以更加专注于实现功能。
线程（Thread）： 线程是进程的组成单元，是 CPU 进行调度的基本单位；线程可以共享所属进程的资源，线程比较轻量，调度开销较小。
有进程为什么需要线程？ 因为随着技术的发展，程序的功能不再单一，很多程序中都包含着多个任务，这些任务（尤其是 CPU 密集型和 I/O 密集型的组合）的并发执行也能够提升程序运行的效率，提升用户的体验，所以将每一个任务映射成为一个线程；同时最主要的也是弥补进程的不足，因为线程可以共享资源，且较进程的调度开销小。
调度
进程的调度
想要在多个进程间来回切换，要保证切换回某个进程时它能够从断点处继续执行，就好像没有被中断过一样。想要实现这样的效果就要记录下进程切换前一时刻的状态，便于切换回来的时候进行复原，这个记录叫做 进程控制块（PCB）。
下图是 PCB 包含的一些内容：
操作系统维护一个 进程表，进程表中的每一项就是一个 PCB，记录着程序计数器、堆栈指针、优先级、内存分配上下界情况等与进程当前状态有关的重要信息。进程切换前，这些信息要被保存到某个地方，切换回来后再取出来恢复原状。
例如响应磁盘 I/O 中断请求的过程，一般磁盘 I/O 中断都有着较高的优先级，因为磁盘是一个慢速设备，得赶紧得到 CPU 的响应然后去干活，才好配合后面程序的运行。当进程 P 正在运行时，CPU 接到磁盘 I/O 的请求，这时与进程 P 相关的信息入栈，通过中断向量找到中断服务程序的入口开始执行中断服务程序，CU 给 DMA 发信号，磁盘 I/O 开始，中断服务程序返回，进程 P 的信息出栈复原，继续执行，就好像什么事都没发生。
线程的调度
了解了进程的切换，其实线程的切换思想也是大同小异。线程也拥有自己的运行时信息，称为 TCB，如程序计数器、堆栈等，在切换前需要被保存，见下图：
进程调度 VS 线程调度
调度的开销主要体现在 对当前信息的更改 和 管态与目态的转换。
进程切换意味着 PCB 的信息要出入栈、CPU 中的缓存不能用了需要刷新、内存管理单元（Memory Management Unit，MMU）的页表信息与高速缓存 TLB 需要更新、要从目态进入到管态、若内存比较小不足以多个进程同时存在，还会引发页面的换入换出……代价极高。
线程切换时，若隶属于同一个进程，则绝大部分信息都不用更改。对于进不进管，用户级线程 切换不需要进管，内核级线程 切换需要进管。用户级线程就是用程序来实现多个线程，从 CPU 的角度看，用户线程是透明的，即 CPU 只看到一个进程，故即便是多核处理器也无法实现用户级线程的并行，但是有个好处是可以实现自定义的调度算法。内核级线程，就是真正意义上的多线程，可以由 CPU 调度。
下面是几个概念：
- MMU
我们写的代码中的数据及指令在编译连接后会被分配以 虚拟地址，MMU 位于处理器和主存的总线之间，用于处理虚拟地址到实际物理地址的映射。这样做有什么好处呢，首先我们程序员不需要关注物理内存的实际分配，其次虚拟空间使我们的可编程地址得以扩大。
- 管态和目态
操作系统=内核+系统调用，内核 是操作系统的核心，也是一种软件，为其他程序提供了对计算机硬件的安全访问，也定义了该系统采用的进程调度方式、页面置换算法、文件管理方式……系统调用 是操作系统向上提供的接口；
为什么要分管态和目态？（也叫内核态与用户态）主要是为了安全考虑。程序=算法+数据结构 也可以说成是 程序=数据+定义在数据上的操作，如果一个程序能够肆无忌惮的访问任何地方的数据和随心所欲的操作数据，那系统将遭受危机。因此，操作系统和要限制程序的权利，包括程序能够访问的地址空间（即限制数据）和程序能够进行的操作。操作系统工作在管态，普通程序工作在目态。
什么是进入管态？如上所说，程序权利被限制，处于目态的程序对一些敏感操作是无权执行的，需要委托给操作系统去执行，这时就要进入管态。通过一条特殊的访管指令，提出进管请求，由操作系统响应，执行完相应的系统调用再返回该程序。
调度策略
主要分为两大类：抢占式调度和非抢占式调度。抢占式调度 指当系统认为某进程运行了足够长的时间片后，直接将它挂起，即便它还没运行完，通常 PC 端、服务器端使用；非抢占式调度 指的是一个进程一直运行直到结束或发生了阻塞，通常移动端使用。
一些判优条件：公平性，吞吐量，平均周转时间……
非抢占式调度
先来先服务（FCFS）
像超市排队收银一样维护一个队列，新来的进程排在队尾。看似公平，可是对 I/O 密集型进程很不友好。
短进程优先
大大减少了平均周转时间，提升了用户的体验，但是准确估算进程运行时间较难，而且多个进程在同一时刻到达才能发挥最大作用。
抢占式调度
下面几个本质都是时间片轮转。
时间片轮转法
最公平且使用最广泛，一视同仁的为所有进程分配相同的时间片，但是时间片的大小不容易控制，太大容易空转，太小调度太频繁。
优先级调度
为进程排上优先级，优先级可以是静态的也可以是动态的。静态优先级容易饿死优闲级低的进程，动态优先级的计算耗费资源。
多队列轮转
有多个优先级队列，低优先级队列分配的时间片多一些，当某一个进程经过一次轮转还没有结束，就降低它的优先级，下一次轮转它会获得较第一次多的时间片，即减少了长进程的调度次数。
同步与互斥
锁思想
设一个共享的锁变量 lock，初值为 0，进程到来时先判断锁的状态，若 lock=0 则表示临界区没有上锁，此时进程对其上锁修改 lock=1，进入临界区进行操作，出临界区时再将锁打开。
存在的一个问题就是这个锁变量本身也应该被看做是一个临界资源，如当进程 P0 发现 lock=0，准备上锁时，发生了进程调度，P1 到来发现 lock=0，于是修改 lock=1 上锁进入了临界区。若 P1 在时间片内还没有出临界区开锁，当再切换回 P0 时就会出现问题；
自旋锁（spin lock）
两个进程 P0、P1，lock 初始值为 0，用于记录允许几号进程进入临界区，过程如下：
// ---进程P0---
while(true){
while(lock!=0);
// 临界区操作;
lock = 1;
// 非临界区操作;
}
// ---进程P1---
while(true){
while(lock!=1);
// 临界区操作;
lock = 0;
// 非临界区操作;
}假设 P0 先到来，检查 lock 发现等于 0，进入临界区操作，出临界区后将 lock 置为 1；这时 P1 到来检查 lock 等于 1，同理。这种连续检查某一个值直到出现为止称为 忙等待，时间片内一直在检查 lock，没有阻塞挂起一说，即浪费了 CPU 时间。
同时还会出现 进程被在临界区外的其他进程阻塞 的情况。假设现在 P1 想进入临界区，而 lock=0 且进程 P0 一直工作在非临界区，没有进入临界区的意思，就不会有出临界区修改 lock 的操作，这时 P1 被处在非临界区的 P0 阻塞。这个叫做 不可重入，即一个进程不能连续两次持有相同的锁。
当然它也有优点。首先线程一直处在活动状态不会被阻塞挂起，减少了线程切换的代价，当然这一点对单核处理器来说毫无意义，因为总得切换到其他进程修改 lock 才可以。
Peterson 解法
解决了上述不可重入的问题，过程如下：
#define FALSE 0
#define TRUE 1
#define N 2 // 进程数量
int turn; // 现在轮到谁
int interested[N]; // 表示谁有意向，初始化为 false
// 进入临界区
void enter_region(int process) {
int other = 1 - process; // 另一个进程号
interested[process] = TRUE; // 置为有意向
turn = process; // 当前轮到谁
while (turn == process && interested[other] == TRUE);
}
// 离开临界区
void leave_region(int process) {
interested[process] = FALSE; // 置为无意向
}
// ---进程P0---
while(true) {
enter_region(0);
// 临界区操作
leave_region(0);
// 非临界区操作
}
// ---进程P1---
while(true) {
enter_region(1);
// 临界区操作
leave_region(1);
// 非临界区操作
}
TSL 指令
考虑进程切换只会发生在响应时钟中断和其他中断发生时，可以在某进程进入临界区后通知 CPU 屏蔽中断，这样在单核处理器中就不用担心其他进程在进入临界区，但是把屏蔽中断的权利交给任意进程对系统是不安全的。
在多核处理器中，哪个核调用屏蔽中断的指令，就只会屏蔽这个核响应中断，对其他核没有影响，于是就有了 测试并加锁（Test and Set Lock，TSL）指令。执行 TSL 指令会锁住数据总线，屏蔽了其他处理器对内存的读写操作。
上面都会出现忙等待问题。
信号量（semaphore）
信号量 S 能够表示能否进入临界区和要唤醒的次数，通过两个 原子操作 实现：
P(S): S:=S-1；
若 S≥0，调用 P(S) 的进程进入临界区；
若 S<0，调用 P(S) 的进程进入阻塞队列；
V(S): S:=S+1；
若 S>0，调用 P(S) 的进程继续运行；
若 S≤0，调用 P(S) 的进程唤醒阻塞队列中的一个进程，然后继续运行；
因为信号量也是一种临界资源（存在内核中或共享内存中），所以对于上述这个两个过程，包括判断、修改、挂起进程的操作必须是不可分割的原子操作。单核 CPU 使用屏蔽中断，多核 CPU 使用 TSL 指令实现来确保同一时刻只有一个 CPU 能操作信号量。
互斥量（mutex）
是信号量的简化版本，即信号量 mutex 只表示加锁和解锁两个状态。
管程（monitor）
管程是一种 语言特性，是一种高级同步原语，是一种互斥的自动化。考虑下面问题：
// 进程P1 // 进程P2
P(扫描仪) P(打印机)
P(打印机) P(扫描仪)
... ...
V(打印机) V(扫描仪)
V(扫描仪) V(打印机)显然上面的两个进程有可能会发生死锁，应该将 P2 对信号量的操作顺序改为和 P1 一致。这说明信号量的使用是一个非常细致的工作，稍有考虑不周全的地方就有可能出现错误，而我们程序员只是想要关心哪些代码、内存能否互斥访问，不想要在信号量上费功夫。所以有些编程语言向我们提供了这一便利，由编译器帮我们实现信号量的 PV 操作，更能保持并发编程的正确性。
如 Java 的 synchronized 关键字，我们用它声明一个方法可以表示互斥访问，信号量就是锁对象，具体信息记录在对象头的 MarkWord 中。