2.1 进程
进程是计算机系统资源分配的基本单位。
2.1.1 进程模型
为了屏蔽中断的影响，操作系统提供了一个由并行运行的顺序进程组成的概念模型。
在进程模型中，所有计算机上可运行的软件，通常也包括操作系统，被组织成若干顺序进程（sequential process），简称进程。一个进程就是一个正在执行程序的实例，包括程序计数器、寄存器和变量的当前值。CPU在各进程间快速来回切换叫做多道程序设计（multiprogramming）。
2.1.2 创建进程
有4种事件导致进程的创建：
- 系统初始化；
- 执行了正在运行的进程所调用的进程创建系统调用；
- 用户请求创建一个新进程；
- 一个批处理作业的初始化。
停留在后台处理的进程称为守护进程（daemon）。
2.1.3 进程的终止
引起进程终止的条件：
- 正常退出（自愿的）；
- 出错退出（自愿的）；
- 严重错误（非自愿）；
- 被其他进程杀死（非自愿）。
2.1.4 进程的层次结构
进程只有一个父进程，但是可以有零个、一个、两个或多个子进程。
2.1.5 进程的状态
- 运行态（该时刻进程实际占用CPU）
- 就绪态（可运行，但因为其他进程正在运行而暂时停止）
- 阻塞态（除非某种外部事件发生，否则进程不能运行）
1->3：进程为等待某事件而阻塞
1->2：调度程序选择另一个进程
2->1：调度程序选择这个进程
3->2：原等待的事件结束
2.1.6 进程的实现
为实现进程模型，操作系统维护着一张进程表，每个进程占用一个表项（即进程控制块，Process Control Block，PCB）。PCB包含了进程状态的重要信息，包括程序计数器（保存了下一条指令的内存地址）、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息，以及其他在进程由运行态转换到就绪态或阻塞态时必须保存的信息，从而保证该进程随后能再次启动，就像从未被中段过一样。
中断向量（interrupt vector）是中断服务程序的入口地址。
进程结束时，操作系统等待一个提示符并等待新的命令，一旦接到新的命令，就装入新的程序进内存，覆盖前一个程序。
2.1.7 多道程序设计模型
采用多道程序设计可以提高CPU的利用率。
2.2 线程
线程（thread）是CPU调度的基本单位。
2.2.1 线程的使用
同一进程内的所有线程共享地址空间和数据。
线程比进程更轻量。
2.2.2 经典的线程模型
线程中有一个程序计数器，用来记录接着要执行哪一条指令；线程拥有寄存器，用来保存线程当前的工作变量；线程还拥有一个堆栈，用来记录执行历史，其中每一帧保存了一个已调用的但是还没有从中返回的过程。线程必须在某个进程中执行。
进程中的不同线程不像不同进程之间那样存在很大的独立性，所有的线程都有完全一样的地址空间，这意味着它们也共享同样的全局变量。由于各个线程都可以访问进程地址空间中的每一个内存地址，所以一个线程可以读、写或甚至清除另一个线程的堆栈。
和传统进程一样（即只有一个线程的进程），线程可以处于若干种状态的任何一个：运行、阻塞、就绪或终止。
每个线程有其自己的堆栈很重要。
2.2.3 POSIX线程
IEEE标准1003.1c中定义了线程的标准，线程包叫做Pthread。
2.2.4 在用户空间中实现线程
把整个线程包放在用户空间，内核对线程包一无所知。
每个进程需要有其专用的线程表（thread table），用来跟踪进程中的线程，于线程之作用与内核中进程表于进程之作用类似。
同个进程中，只要有一个线程运行，其他线程也会运行。
2.2.5 在内核中实现线程
线程表保存于内核中。
阻塞线程的调用都以系统调用的形式实现。
创建或撤销线程代价较大。
2.2.6 混合实现
使用内核级线程，然后将用户级线程与某些或者全部内核线程多路复用起来：编程人员可以决定有多少个内核级线程和多少个用户级线程彼此多路复用，有较大灵活度。
2.2.7 调度程序激活机制
调度程序激活（scheduler activation）机制工作的目标是模拟内核线程的功能，但是为线程包提供通常在用户空间才能实现的更好的性能和更大的灵活性。当使用调度程序激活机制时，内核给每个进程安排一定数量的虚拟的处理机，并且让运行时系统将线程分配到处理机上。
该机制工作的基本思路是，当内核了解到一个线程被阻塞后，内核通知该线程的运行时系统，并且在堆栈中以参数形式传递有问题的现成的编号和所发生时间的一个描述，一旦如此激活，运行时系统就重新调度其线程，这个过程通常是这样的：把当前线程标记为阻塞并从就绪表中取出另一线程，设置其寄存器，然后再启动之，稍后，当内核知道原来的线程又可运行时，内核就又一次上下调用运行时系统，通知它这一事件，此时运行时系统按照自己的判断，或者立即重新启动被阻塞的线程或者把它放入就绪表中稍后继续。
2.2.8 弹出式线程
当有新的请求到达时，马上创建一个线程去处理这个请求。
2.2.9 使单线程代码多线程化
单线程代码所运行的系统，在内核里认为上层运行的程序是单线程进程，此时改为多线程进程，是用户级多线程。
全面禁止全局变量或为每一个线程赋予其私有的全局变量（解决全局变量问题）；为每个过程提供一个包装器，为该包装器设置一个二进制位从而标识某个库处于处于使用中，在先前的调用还没有完成之前，任何试图使用该库的其他线程都会被阻塞（解决库过程不可重入问题）；非线程专用问题较复杂；堆栈管理麻烦。
2.3 进程间通信（Inter Process Communication，IPC）
2.3.1 竞争条件
协作的进程可能共享一些彼此都能读写的公共存储区。
两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件（race condition）。
2.3.2 临界区
避免竞争，需要互斥（mutex exclusion），即以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。
对共享内存进行访问的程序片段称为临界区域（critical region）或临界区（critical section）。
避免竞争的条件：
- 任何两个进程不能同时处于其临界区。
- 不应对CPU的速度和数量做任何假设。
- 临界区外运行的进程不得阻塞其他进程。
- 不得使进程无限期等待进去临界区。
2.3.3 忙等待的互斥
忙等待（busy waiting），即反复检查一个条件是否为真。
- 屏蔽中断
使每个进程在刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断。 - 锁变量
设置一个共享（锁）变量，当一个进程想进入临界区时，先测试这把锁。 - 严格轮换法
连续测试一个变量直到某个值出现为止，称为忙等待。用于忙等待的锁，称为自旋锁（spin lock）。
两个协作的并发进程轮流进入临界区。 - Peterson解法
一个不需要严格轮换的软件互斥算法。 - TSL指令
2.3.4 睡眠与唤醒
生产者-消费者（producer-consumer）问题，也称作有界缓冲区（bounded-buffer）问题：两个进程共享一个公共的固定大小的缓冲区，其中的一个是生产者，将信息放入缓冲区，另一个是消费者，从缓冲区中取出信息，生产者向缓冲区内存放信息至满然后唤醒消费者并自我休眠，消费者从缓冲区中取出信息至空然后唤醒生产者并自我休眠。
2.3.5 信号量
使用一个整型变量来累计唤醒次数，供以后使用。引入一个新的变量类型，称作信号量（semaphore）。一个信号量的取值可以为0，也可以为正值。信号量的另一种用途是用于实现同步（synchronization），保证某种事件的顺序发生或不发生。
2.3.6 互斥量
互斥量（mutex）是一个可以处于两态之一的变量：解锁和加锁，仅仅适用于管理共享资源或一小段代码，允许或阻塞进程对临界区的访问。
pthread还提供了称作条件变量（condition variable）的同步机制，允许线程由于一些未达到的条件而阻塞，（不像信号量）不会存在内存中，与互斥量经常一起使用。
2.3.7 管程
一个管程（monitor）是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包，任一时刻管程中只能有一个活跃进程，这一特性使得管程能有效地完成互斥。
2.3.8 消息传递
消息传递（message passing）是一种进程间通信方式，使用send与receive两条原语，send向一个给定的目标发送一条消息，receive从一个给定的源接收一条消息，如果没有消息可用，则接收者可能被阻塞，直到一条消息到达，或者，带着一个错误码立即返回。
2.3.9 屏障
屏障（barrier）是一种同步机制。进程会在屏障处阻塞直到并发的所有进程都在此屏障处阻塞。
2.4 调度
操作系统中选择下一个要运行进程的部分称为调度程序（scheduler），该程序使用的算法是调度算法（scheduling algorithm）。
2.4.1 调度介绍
计算机密集型（compute-bound）进程具有较长时间的CPU集中使用和较小频度的I/O等待。
I/O密集型（I/O-bound）进程具有较短时间的CPU集中使用和频繁的I/O等待，越来越多的进程是这种类型。
何时进行调度决策：
- 在创建一个新进程之后，需要决定的是运行父进程还是运行子进程；
- 在一个进程退出时必须做出调度决策；
- 当一个进程阻塞在I/O和信号量上或由于其他原因阻塞时，必须选择另一个进程运行；
- 在一个I/O中断发生时，必须做出调度决策。
调度程序的环境：
- 批处理系统
- 交互式系统
- 实时系统
调度算法的目标：
- 所有系统：
i. 公平——给每个进程公平的CPU份额
ii. 策略强制进行——看到所宣布的策略执行
iii. 平衡——保持系统的所有部分都忙碌 - 批处理系统：
i. 吞吐量——每小时最大作业数
ii. 周转时间——从提交到终止间的最小时间
iii. CPU利用率——保持CPU始终忙碌 - 交互式系统：
i. 响应时间——快速响应请求
ii. 均衡性——满足用户的期望 - 实时系统：
i. 满足截止时间——避免丢失数据
ii. 可预测性——在多媒体系统中避免品质降低
2.4.2 批处理系统中的调度
调度算法：
- 先来先服务（first-come first-served）算法
非抢占式，先到的先运行，后到的依次入队列等待，等前一个运行结束才能运行。 - 最短作业优先（shortest job first）算法
总需要运行时间从短到长的依次运行。 - 最短剩余时间优先（shortest remaining time next）算法
剩余需要运行时间从短到长的依次运行。
2.4.3 交互式系统中的调度
调度算法：
- 轮转调度（round robin）
每个进程被分配一个时间段，称为时间片（quantum），即允许该进程在该时间段中运行，如果在时间片结束时该进程还在运行，则将剥夺CPU并分配给另一个进程，如果该进程在时间片结束前阻塞或结束，则CPU立即进行切换。
最古老、最简单、最公平且使用最广的调度算法。
进程切换（process switch）有时称为上下文切换（context switch）。 - 优先级调度
使相同优先级进程进行轮转，只有较高优先级进程全部运行完毕，才会转入下一优先级进程的轮转。 - 多级队列
使优先级由高到低的进程进行轮转，高优先级分配的时间片较长，当一个时间片结束，立即转入下一个优先级进行一个时间片的运行。 - 最短进程优先
当前需要运行时间最短的进程优先。 - 保证调度
向用户作出明确的性能保证，并去实现它。如果 n 个进程同时运行，公平的情况下每进程应该获得处理机时间的 1/n。 - 彩票调度（lottery scheduling）
基本思想是为进程发放针对系统各种资源(如CPU时间)的彩票。当调度程序需作出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源。 - 公平分享调度
针对用户而不是进程，使得每用户获得相同的处理机时间。
2.4.4 实时系统中的调度
2.4.5 策略和机制
将调度机制（scheduling mechanism）与调度策略（scheduling policy）分离，也就是将调度算法以某种形式参数化，而参数可以由用户进程填写。
2.4.6 线程调度
当若干进程都有多个线程时，就存在两个层次的并行：进程和线程。在这样的系统中调度处理有本质差别，这取决于所支持的是用户级线程（或两者都支持）。
用户级线程和内核级线程之间的差别在于性能。
2.5 经典的IPC问题
2.5.1 哲学家就餐问题
问题描述：五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五把叉子，他们的生活方式是交替的进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的叉子，只有在他拿到两把筷子时才能进餐。进餐完毕，放下筷子继续思考。
解决思路：给正在被使用的叉子加锁，引入信号量机制，规定每位哲学家要么不用叉子要么两把左右叉子一起用。
2.5.2 读者-写者问题
问题描述：如果有一个写者正在写，那么就不允许有其他写者在写或任何读者在读；允许多个读者同时在读。
解决思路：读时先加锁，若是有其他读者，便解锁；写时正常加解锁。
2.6 有关进程和线程的研究
2.7 小结
进程可以动态地创建和终止。每个进程都有自己的地址空间。
每个线程有自己的堆栈，但是在一个进程中所有线程共享一个公共地址空间。线程可以在用户空间或内核中实现。
进程间通过进程间通信原语彼此通信。
将调度策略和调度机制清晰地分离，可以使用户对调度算法进行控制。
博文补充（转）：
《Linux内核设计与实现》读书笔记（三）- Linux的进程
《Linux内核设计与实现》读书笔记（四）- 进程的调度
《Linux内核设计与实现》读书笔记（五）- 系统调用
京公网安备 11010502036488号