1.前趋图和程序执行
（1）前趋图
前趋图(Precedence Graph)是一个有向无循环图，可记为DAG，用于描述程序/进程之间执行的先后顺序。
图中每个结点可用来表示一个进程或程序段，结点间的有向边表示两个结点之间存在的偏序或前趋关系。如P1与 P2存在前趋关系，记作P1 -> P2，表示在P2开始执行之前P1必须完成，此时称P1是P2的直接前趋，P2是P1的直接后继。没有前趋的结点称为初始结点，没有后继的结点称为终止结点，每个结点还有一个重量，用于表示该结点所含有的程序量或程序的执行时间。
（2）程序的顺序执行
在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。 一道程序执行完后另一道才能开始。
程序顺序执行的特点
- 顺序性：一个程序开始执行必须要等到前 一个程序已执行完成。
- 封闭性：程序一旦开始执行，其计算结果不受外界因素影响。
- 可再现性：程序的结果与它的执行速度无关（即与时间无关），只要给定相同的输入，一定会得到相同的结果。
（3）程序的并发执行
若干个程序同时在系统中执行，这些程序的执行在时间上是重叠的，一个程序的执行尚未结束，另一个程序的执行已经开始。
只有在不存在前趋关系的程序之间才有可能并发执行，否则无法并发执行。
程序并发执行的特点
- 间断性：在并发执行时由于共享系统资源以及相互合作，可能会导致程序在执行过程中互相制约，造成程序间断性的活动规律。
- 失去程序的封闭性：程序在并发执行时，是多个程序共享系统中的资源，因此这些资源的状态将由多个程序来改变。
- 不可再现性：如循环程序A、B，共享变量N。 程序A执行N:=N+1；程序B执行Print(N)，后将N置0。 两个程序以不同速度运行，可能出现三种情况：
N:=N+1在Print(N)和N=0之前，此时N值分为N+1,N+1, 0
N:=N+1在Print(N)和N=0之后，此时N值分为N, 0, 1
N:=N+1在Print(N)和N=0之间，此时N值分为N, N+1, 0
程序在并发执行时，由于失去了封闭性，其计算结果必将与并发程序的执行速度有关，从而使程序的执行失去了可再现性。程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但等到的结果却各不相同。
2.进程的描述
（1）进程的定义与特征
进程的定义
进程是指进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
进程实体（进程映像、进程）：程序段、相关的数据段、进程控制块PCB。
进程的特征
- 结构特征：由程序段、数据段、进程控制块三部分组成；
- 动态性：进程的实质是程序的执行过程；动态性是进程最基本的特征。进程实体具有一定的生命周期。
- 并发性：多个进程可同存于内存中，能在一段时间内同时运行；引入进程的目的正是为了使进程实体能够并发执行； 程序不能参与并发执行。
- 独立性：进程是独立运行的基本单位，独立获得资源和调度的基本单位；
- 异步性：各进程按各自独立的不可预知的速度向前推进。
进程与程序的区别
程序：指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行过程， 它是一个动态的概念；
- 程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的；
- 进程更能真实地描述并发，而程序不能；
- 进程是由程序和数据、进程控制块三部分组成的；
- 进程具有创建其他进程的功能，而程序没有；
- 同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。同一程序可以对应多个进程。
（2）进程控制块
操作系统中用于管理控制资源的数据结构
在计算机系统中，对每个资源和每个进程都设置了一个数据结构，用来表征其实体，其中包含了他们的标识、描述 、状态等信息以及一批指针。
OS管理的这些数据结构一般分为四类：
内存表、设备表、文件表和进程表。 进程表被称为PCB
进程控制块
为了描述和控制进程运行，系统为每个进程定义了 一个数据结构，称为进程控制块（PCB）。 PCB中记录了OS所需的、用于描述进程当前情况以及控制进程运行的全部信息。
PCB是操作系统中最重要的记录型数据结构。
（3）PCB
PCB的作用
PCB的作用是将一个不能独立运行的程序变成一个可以独立运行的基本单位，一个能与其他进程并发执行的进程。
- OS利用PCB来对并发执行的进程进行控制和管理
- PCB是OS感知进程存在的唯一标志。
- 进程与PCB是一一对应的。 PCB应常驻内存。
- PCB提供进程调度和管理所需要的信息
- PCB实现与其他进程的同步与通信。
PCB的内容
1. 进程标识符(process ID)，用于唯一地标识一个进程
- 外部标识符：进程名，通常基于可执行文件名
- 内部标识符：用户标识符(user ID)；进程组关系
2.处理机状态（处理机上下文）：CPU现场保护信息
- 寄存器值（通用、程序计数器、程序状态字PSW，栈 指针）
- 指向赋予该进程的段/页表的指针
3.进程调度信息
- 进程状态，表明进程当前的状态，它是作为进程调度和对换时的依据
- 进程优先级，描述进程使用处理机的优先级别
- 进程调度所需其他信息，与采用的进程调度算法有关
- 事件，进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因
4.进程控制信息
- 程序和数据的地址，进程实体中的程序和数据的内存或外存地（首）址，便于调度执行
- 进程同步和通信机制，实现进程同步和进程通信时必需的机制，如消息队列指针、信号量
- 资源清单，在该清单中列出进程在运行期间所需的全部资源（除CPU以外），另外还有一张已分配到该进程的资源的清单
- 链接指针，它给出了本进程PCB所在队列中的下一个进程的PCB的首地址
PCB的组织方式
1.线性方式 PCB表
- 系统把所有进程的PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表。
- PCB表的大小决定了系统中最多可同时存在的进程个数， 称为系统的并发度。
2.链接方式
- 相同状态的进程PCB组成一个队列，不同状态对应多个不同的队列。
- 就绪队列、阻塞队列等
3. 索引方式
对具有相同状态的进程，分别设置各自的PCB索引表， 存放这些进程PCB在PCB表中的地址。
（4）进程的状态及转换
进程的三种基本状态
就绪状态：当进程已经获得了除CPU以外的所有资源， 一旦得到CPU，就立即可以运行，则这些进程所处的状态为就绪状态。 就绪队列：所有处于就绪状态的进程所在的队列。
运行状态：正在运行的进程所处的状态为运行状态。
- 单处理机系统一个进程处于运行状态
- 多处理机系统有多个进程处于运行状态
阻塞/等待状态：若一进程正在等待某一事件发 生（如等待输入/输出工作完成），这时即使给它CPU，它也无法运行，称该进程处于等待状态，或阻塞、睡眠、封锁状态。 阻塞队列：系统根据阻塞原因设置多个队列来管理处于阻塞状态的进程。
创建状态和终止状态
创建态：进程由创建而产生。为一个新进程创建必要的管理信息，保证进程的调度必须在创建工作完成以后进行，处于创建状态的进程，当获得了所需要的资源以及对PCB初始化工作完成后，便可以由创建状态进入就绪状态。
终止态：进程由终止而结束。
等待操作系统进行善后，然后，退出主存。进入终止态的进程不再执行，但依然临时保留在系统中等待善后。一旦其他进程完成了对终止态进程的信息抽取之后，系统将删除该进程，将其PCB清零，把PCB空间返回给系统。
挂起操作和进程状态的转换
挂起操作使某个进程处于静止状态
- 如果进程正在执行，挂起操作使他暂停执行
- 如果处于就绪状态，挂起操作使他暂不接受调度
与挂起操作对的就是激活操作
引用挂起状态的原因
- 终端用户的请求
- 父进程请求
- 负荷调节的需要
- 操作系统的需要
- 对换的需要
活动就绪（就绪状态）→静止就绪：对就绪的进程进行挂起操作，则该进程不能再被调度进入静止就绪状态
静止就绪→活动就绪（就绪状态）：用相应的激活原语激活以后，重新进入活动就绪状态，进入就绪队列等待调度
活动阻塞（阻塞状态）→静止阻塞：用挂起原语对阻塞进程实施挂起操作则进入静止阻塞状态，只有在该进程所期待的事件发生以后就会转入静止就绪。
静止阻塞→活动阻塞（阻塞状态）：利用激活原语激活以后进入活动阻塞状态。
七状态进程转换
参考《计算机操作系统》 （汤小丹 第四版）
