进程

进程的概念

进程是执行中的程序，它不止是程序代码（文本段），进程还包括当前活动（通过程序计数器的值和处理器寄存器的内容来表示）；另外进程还包括进程堆栈段（包括临时数据，如函数参数、返回地址和局部变量）和数据段（包括全局变量）；进程还可能包括堆（进程运行过程中动态分配的内存）；内存中的进程结构图如下图所示：

注意：程序本身并不是进程；程序只是被动实体，如可执行文件，而进程是活动实体，它通过程序计数器来表示下一个要执行的命令和相关资源集合；当一个可执行文件被装入内存时一个程序才能成为进程；

进程的状态

进程可以有以下五种状态：新建，运行，等待，就绪，终止；在一个处理器上一次只可以运行一个进程，但是多个进程可以处于就绪或等待状态；进程的状态转换图如下所示：

进程控制块

每个进程在操作系统内用进程控制块（PCB，也叫任务控制块）来表示，一个PCB的结构如图所示：

• 进程状态：进程的五个状态之一
• 程序计数器：计数器表示进程要执行的下个指令的地址
• CPU寄存器：在CPU中至少要有六类寄存器：指令寄存器（IR）、程序计数器（PC）、地址寄存器（AR）、数据寄存器（DR）、累加寄存器（AC）、程序状态字寄存器（PSW）。这些寄存器用来暂存一个计算机字，其数目可以根据需要进行扩充
• CPU调度信息：包括进程优先级，调度队列指针和其他调度参数
• 内存管理信息：包括基址和界限寄存器的值、页表或段表
• 记账信息：包括CPU时间，实际使用时间，进程数量等
• I/O状态信息：包括分配给进程的I/O设备列表、打开的文件列表等

一个CPU在进程间的切换实例如图所示：

进程调度

进程进入系统时会被加入到任务队列中，该队列包括系统中的所有进程；就绪的进程保存在就绪队列中；等待特定I/O设备的进程被放至设备队列中，每个设备都有自己的设备队列；
一个进程调度的队列图如下所示：

线程

线程的概念

线程是CPU使用的基本单元，它由线程ID、程序计数器、寄存器集合和栈组成；它与属于同一进程的其他线程共享代码段、数据段和其他操作系统资源；
线程是CPU调度的基本单元，进程是系统资源分配的基本单元，一个进程中可能包含多个线程。

多线程

多线程编程具有响应度高、资源共享、经济和多处理器体系结构的利用四个优点。虽然我们用户进程中可以有很多线程可以执行，但实际上这些用户线程都是映射到内核线程上来执行的。用户线程和内核线程之间的映射关系模型包含有：

1. 多对一
   将许多用户级线程映射到一个内核线程；线程管理是由线程库在用户空间进行的,因而效率比较高，但是如果一个线程执行了阻塞系统调用，那么整 个进程会阻塞。
2. 一对一
   将每个用户线程映射到一个内核线程；该模型在一个线程执行阻塞系统调用时，能允许另一个线程继续执行，所以它提供了比多对一模型更好的井发 功能；它也允许多个线程能并行地运行在多处理器系统上，这种模型的唯一缺点是每创建一个用户线程就需要创建一个相应的内核线程；由于创建内核线程的开销会影响应用程序的性能，所以这种模型的绝大多数实现限制了系统所支持的线程数量。
3. 多对多 多路复用了许多用户线程到同样数量或更小数量的内核线程上；开发人员可创建任意多的用户线程，并且相应内核线程能在多处理器系统上并发执行，而且，当一个线程执行阻塞系统调用时，内核能调度另一个线程来执行。

CPU调度

通常说的CPU调度是讲进程调度，实际上现在支持一个进程包含多线程的操作系统中CPU的调度对象都是针对的内核线程，不过调度算法是一样的；下面以进程调度为例来说明调度算法

调度决策

CPU的调度决策会发生在如下四种情况下：
（1）运行-->等待
（2）运行-->就绪
（3）等待-->就绪
（4）运行-->终止
对于（1）和（4）两种情况都是运行的进程要么是资源条件不足，要么是运行结束了，这个时候需要选择新的就绪队列的进程转入运行状态，因此只有调度，没有选择；对于（2）和（3）两种情况下则是有进程进入就绪状态，这时可以选择。当调度只能发生在（1）和（4）两种情况下时，调度方案称为非抢占调度（新的就绪进程的出现不影响正在运行的进程），否则称为抢占调度（新的就绪进程可能抢占了当前运行进程的CPU资源）

调度准则

为了比较不同的调度算法，产生了许多的调度准则，其中比较标准的有如下几个：

• CPU使用率：需要使CPU尽量忙
• 吞吐量：一个时间单元内所完成进程的数量
• 周转时间：从进程提交到进程完成的时间段；周转时间为所有时间段之和，包括等待进入内存、在就绪队列中等待、在 CPU 上执行和 I/O 执行
• 等待时间：在就绪队列等待所花费时间之和
• 响应时间：从提交请求到产生第一响应的时间；是开始响应所需要的时间，而不是输出响应所需要的时间。

好的调度算法都是使CPU使用率和吞吐量最大化，而使周转时间、等待时间和响应时间最小化

调度算法

先来先服务（FCFS）

最简单的CPU调度算法，根据进程进入就绪队列的先后顺序调度进程执行，但是这种方法的平均等待时间通常较长

最短作业优先调度（SJF）

该算法将每个进程与其下一个CPU区间段相关联，当CPU为空闲时，他会赋给具有最短CPU区间的进程；如果两个进程具有同样长度，则可以使用FCFS来处理；该算法为最佳算法，但很难知道下一个CPU区间的长度，特别是对于短期CPU调度，由于无法获取下一个CPU区间的长度，一般会对区间长度进行预测，认为下一个CPU区间的长度与以前的相似（指数平均）；
SJF算法可能是抢占的或非抢占的，当一个新进程到达就绪队列而当前进程正在执行 时，就需要进行选择；与当前运行的进程相比，新进程可能有一个更短的 CPU 区间，此时抢占 SJF算法可抢占当前运行的进程，而非抢占 SJF 算法会允许当前运行的进程先完成其 CPU 区间。
抢占 SJF 调度也被称为最短剩余时间优先调度

优先级调度（priority scheduling algorithm）

每个进程都有一个优先级与其关联，具有最高优先级的进程会分配到CPU，具有相同优先级的进程按FCFS的顺序调度；优先级通常为固定区间的数字，如0～7或0～4095，其中优先级与大小的正负相关可以自己定义；
优先级调度可以是抢占的或者非抢占的，当一个新进程到达就绪队列时，其优先级与当前运行进程的优先级相比较，如果新进程优先级高于当前进程，那么抢占优先级调度算法会抢占CPU，而非抢占的只是将新进程加到就绪队列头部
优先级调度的一个主要问题是无穷阻塞或饥饿，即优先级算法会使某个低优先级进程无穷等待CPU；解决该问题的方法之一是老化，通过逐渐增加在系统中等待很长时间的进程的优先级来保证进程被执行；

轮转法调度（round-robin， RR）

定义一个较小时间单元，称为时间片（通常为10～100ms），将就绪队列作为循环队列，CPU调度程序循环就绪队列，为每个进程分配不超过一个时间片的CPU；将就绪队列保存为进程的FIFO队列，新进程增加到就绪队列的尾部，CPU调度程序从就绪队列中选择第一个进程，设置定时器在一个时间片之后中断，再分派该进程；此时可能发生两种情况：如果进程需要的时间小于时间片的CPU区间，那么进程本身会自动释放CPU，调度程序接着处理就绪队列的下一个进程；如果当前进行进程的CPU区间比时间片长，则定时器会中断并产生操作系统中端，然后进行上下文切换，将进程加入到就绪队列的尾部，接着CPU调度程序会选择就绪队列的下一个进程。
RR调度算法的性能很大程度上依赖于时间片的大小；在极端情况下，如果时间片非常大，那么RR算法与 FCFS 算法一样；如果时间片很小（如 1 ms），那么 RR 算法称为处理器共享（n 个进程对于用户都有它自己的处理器,速度为真正处理器速度的 1/n）；

多级队列调度

将就绪队列分为多个独立队列，根据进程的属性（如内存大小，进程优先级，进程类型等）把一个进程永久的分配到一个队列；每个队列都有自己的调度算法；队列之间也存在调度，通常采用固定优先级抢占调度，例如前台队列可以比后台队列具有绝对的优先级；

多级反馈队列调度

多级反馈队列调度算法允许进程在队列之间移动，主要思想是根据不同CPU区间的特点以区分进程，如果进程使用过多CPU时间，那它就会被转移至更低的优先级队列，而在较低优先级队列中等待时间过长的进程会被转移到更高优先级队列以阻止饥饿的发生

进程同步

协作进程之间可以通过消息来共享数据，而对于共享数据的并发访问可能会产生数据的不一致，即多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关，这个称为竞争条件，为了避免竞争条件，需要确保一段时间内只有一个进程能操作某些共同资源，而这就要求进行一定形式的进程同步

临界区问题

每个进程都有一个代码段称为临界区，位于临界区的代码段一般有着改变共同变量，更新一个表，写一个文件等功能，当一个进程进入临界区，其他进程就不允许在临界区内执行；
临界区问题是设计一个方便进程协作的协议，每个进程必须请求允许进入其临界区，实现这一请求的代码段称为进入区，临界区之后可以有退出区，其他代码则为剩余区；一个临界区问题的进程通用结构如下图所示：

临界区问题有以下三个要点：

• 互斥：如果进程Pi在其临界区执行，那么其他进程都不能在其临界区内执行
• 有空让进：如果没有进程在其临界区内执行且有进程希望进入临界区，那么只有那些不在剩余区内执行的进程能参加决策，以选择谁能下一个进入临界区，且这种选择不能无限推迟
• 有限等待：在一个进程做出进入其临界区的请求到该请求被允许期间，其他进程被允许进入期临界区的次数存在一个上限

Peterson算法

Peterson算法是一个经典的基于软件的解决临界区问题的算法，它适用于两个进程在临界区与剩余区间交替执行；以下是Peterson算法的一个进程的结构：

变量turn表示哪个进程可以进入其临界区，级如果turn==i，那么进程Pi允许在其临界区内执行；数组flag表示哪个进程想要进入其临界区，例如若flag[i]为true，则表示进程Pi想要进入其临界区

信号量

信号量允许多进程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大进程数目；本质上，信号量是一个计数器，它用来记录对某个资源的存取状况，为了获得共享资源，进程需要执行下列操作（PV操作）：

1. 测试控制该资源的信号量
2. 若此信号量的值为正，则允许进程使用该资源，进程将信号量减一
3. 若此信号量为0，则该资源目前不可用，进程进入睡眠状态，直至信号量大于0，进程被唤醒，转入步骤一 4.当进程不再使用一个信号量控制的资源时，信号量加一，如果此时有进程正在睡眠等待此信号量，则唤醒此进程

死锁

一组阻塞进程分别占有一定的资源并等待获取另外一些已经被同组其他进程所占有的资源即为死锁，死锁的产生需满足下面四点：互斥，占有并等待，非抢占以及循环等待