进程与线程
进程
进程
进程是对正在运行程序的一个抽象。一个进程就是一个正在执行程序的实例，包括程序计数器，寄存器和变量的当前值。
关键思想：一个进程是某种类型的一个活动，它有程序、输入、输出以及状态。
实际上真正的CPU在各个进程之间来回切换，这种快速的切换称作多道程序设计。
进程的创建
- 系统初始化：系统启动时，会创建若干进程。其中前台进程同用户交互；后台进程停留在后台进行邮件处理，打印之类的活动，这类进程称为守护进程。
- 正在运行的程序执行了创建进程的系统调用。
- 用户请求创建一个新进程。如点开某个app。
- 一个批处理作业的初始化。
进程的终止
- 正常退出（自愿的）：工作已经正常完成时退出
- 出错退出（自愿的）
- 严重错误（非自愿的）
- 被其他进程杀死（非自愿的）：调用kill杀死进程
进程的层次结构
UNIX系中，进程与它的所有子进程以及后羿共同组成一个进程组。父子结构。
Windows中没有进程层次的概念，所有进程地位相同。
进程的状态
- 运行态（该时刻进程实际占用CPU）
- 就绪态（可运行，但因为其他进程正在运行而暂时停止）
- 阻塞态（除非某种外部事件发生，否则进程不能运行）
当操作系统发现进程不能继续运行时，由运行态转变为阻塞态。
当进程等待的一个外部事件发生时，由阻塞态转变为就绪态。
运行态和就绪态的转变是由进程调用程序引起的。
进程的实现
操作系统维护着一张表格（一个结构数组），即进程表。每个进程占用一个进程表项，该表项包含了进程状态的重要信息。
- 进程管理：进程状态、进程ID、父进程、优先级、调度参数等等
- 存储管理：代码段指针、数据段指针、堆栈段指针。
- 文件管理：根目录、工作目录。文件描述符、用户ID、组ID
线程
为什么需要线程？
- 并行实体拥有共享同一个地址空间和所有可用数据的能力。
- 线程比进程更轻量级，所以它们比进程更容易创建，也更容易撤销。
- 如果存在着大量的I/O处理，拥有多个线程允许这些活动彼此重叠运行。
进程间通信（IPC）
竞争条件
多个进程读写某些共享数据时，最后取决于进程运行的准确时序，称为竞争条件。多核增长带来的并行使得竞争条件越来越普遍。
临界区
对共享内存进行访问的程序片段称为临界区。为了避免竞争条件，需要满足几点：
- 任何两个进程不能同时处于临界区。
- 不应对CPU的速度和数量做任何假设。
- 临界区外运行的进程不得阻塞其他进程。
- 不得使进程无限期等待进入临界区。
忙等待的互斥
- 屏蔽中断：当进程进入临界区立即屏蔽所有中断，并在离开之前打开中断。
- 锁变量：进入时设置锁变量，防止下一个进程进入。但是可能存在恰好在设置锁变量的时候，另一个进程也趁机进入了的情况。
- 严格轮换法：连续测试一个变量直到某个值出现为止，称为忙等待。
- Peterson解法：使用共享变量。
- TSL指令：测试并加锁。将内存字lock读到寄存器中，并在该地址存一个非零值，指令结束之前不允许访问该内存字。
睡眠与唤醒
生产者-消费者。两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者，将信息放入缓存区。另外一个是消费者，从缓存区中取出信息。
如果缓存区满了，那么生产者睡眠，待消费者从缓存取中取走数据时唤醒它。同样缓存区为空时类似。
由于生产者和消费者的操作可能需要任意长的时间，在消费者读取缓存区为0的时候，准备要睡眠了，但是此时生产者加了1，本意是要通知消费者醒来，但此时消费者在逻辑上并没有睡眠。这样会导致缓存区迟早会满，最后两个进程全都睡眠了。
信号量
保证一旦一个信号量操作开始，则在该操作完成或阻塞之前，其他进程均不可访问该信号量。信号量的操作仅需几毫秒。
互斥量
信号量的简化版本，仅仅适用于管理共享资源或一小段代码。它是一个可以处于两态之一的变量：解锁和加锁。
管程
一个管程是一个由过程、变量及数据结构等组成的一个集合，他们组成一个特殊的模块或软件包，进程可在任何需要的时候调用过程中的过程。但它们不能再管程之外声明的该过程中直接访问管程内的数据结构。
管程一个重要的特性：任一时刻管程中只有一个活跃进程。
消息传递
调度
计算密集型：花费了绝大多数时间在计算上。
I/O密集型：花费了绝大多数时间在等待I/O上。
何时调度
- 创建一个新进程后，决定是运行父进程还是子进程。
- 一个进程退出后，需要决定接下来运行哪一个进程。
- 当一个进程阻塞时，选择哪一个进程进行运行。
- 在I/0中断发生时，需要作出调度决策。
批处理
- 先来先服务。
- 最短作业优先。总的时间最少。
- 最短剩余时间优先。最短的作业时间永远最先运行。如果新的进程比当前进程需要的时间更少，那么当前进程会被挂起，而运行新的进程。
交互式
- 轮转调度：给每个进程分配一个时间段，进行进程切换运行。
- 优先级调度：优先级高的可运行进程优先运行。
- 多级队列
- 最短进程优先：根据进程过去的行为进行推测，并执行估计运行时间最短的一个。
- 保证调度
- 彩票调度：随机
- 公平分享调度