第三章——进程管理
搬运文章：操作系统（第四版）期末复习总结（上）
1. 进程的概述
1.1 程序的顺序执行和并发执行
程序的执行有两种方式：顺序执行和并发执行。
1.1 顺序执行
- 顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统
- 程序：完成所要求的功能时，所应采取的顺序步骤，是执行指令的有序集合。
- 程序的顺序执行：具有独立功能的程序独占CPU直至得到最终结果的过程
- 特征1—顺序性：按照程序结构所指定的次序（可能有分支或循环）
- 特征2—封闭性：独占全部资源，计算机的状态只由该程序的控制逻辑所决定
- 特征3—可再现性：初始条件相同则结果相同
1.2 异步执行
定义：程序的并发执行是指一组在逻辑上互相独立的程序或程序段在执行时间上客观上互相重叠，即一个程序或程序段的执行尚未结束，另一个程序（段）的执行已经开始的执行方式
并发：在一段时间内的同时并行
并行：在同一物理时刻的同时
现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率
- 并发目的1：提高计算机的处理能力
- 并发目的2：提高资源利用率
- 并发形式1：多道程序环境下的多道程序的并发执行
- 并发形式2：在某道程序的几个程序段中，包含可同时执行或可颠倒顺序执行的代码
并发执行特征：
- 间断(异步)性：“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系
- 失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征
- 失去可再现性：失去封闭性 -> 失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征
不加控制的并发执行所带来的影响：
例：利用堆栈管理一块内存区中各数据块的使用情况。
用getaddr(top) 从栈顶取出相应的内存块的地址。
用reladdr(blk)将数据块的地址（以bkl为地址）放入堆栈中。
例子的说明：
- getaddr()和reladdr()的并发执行，产生了错误的结果，不同执行顺序得到不同的结果，程序的执行不再具有封闭性和结果的可再现性。
- 原因：对公共变量（堆栈或堆栈指针）的共享引起的。
- 为了获得结果的可再现性，程序的并发执行是需要条件的。
并发执行的条件：达到封闭性和可再现性
并发执行失去封闭性的原因是共享资源的影响，去掉这种影响即可。
1.2 进程的定义
一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。简言之，进程是程序的一次执行活动。
进程描述了程序的动态执行过程
它对应虚拟处理机、虚拟存储器和虚拟外设等资源的分配和回收
反映系统中程序执行的并发性、随机性和资源共享
引入多进程，提高了对硬件资源的利用率，但又带来额外的空间和时间开销，增加了OS的复杂性
1.2.1 进程的特征
动态性：
进程对应程序的执行
进程是动态产生：创建 -> 运行 -> 消亡
进程在其生命周期内，在三种基本状态之间转换
独立性：各进程的地址空间相互独立，除非采用进程间通信手段
并发性：任何进程都可以同其他进程一起向前推进
异步性：每个进程都以其相对独立的不可预知的速度向前推进
结构化： 进程 = 代码段 + 数据段 + PCB
1.2.2 进程与程序的区别
进程是动态的，程序是静态的：炒菜 <——>菜谱
进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存
进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）
进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序
进程具有并行特征，程序没有。进程具有独立性和异步性
进程是竞争计算机资源的基本单位
举例：
- 正在运行的Web浏览器是一个进程，正在运行的Windows资源管理器是一个进程，正在运行的Visual C++编程环境也是一个进程
- 在计算机中处于运行状态的任何一个程序都是一个进程，一个进程拥有内存、CPU时间等一系列资源
2. 进程的描述
2.1 进程的组成
进程 = 程序 + 数据 + 进程控制块PCB
- 程序是进程的不可缺少的组成部分；如果一个程序段允许被共享，则它应该是可重入的，或纯代码段
- 数据是进程处理的对象
- 进程控制块是进程的控制结构，包含了进程的描述信息、控制信息和资源信息以及现场保护区，是进程的唯一标识，系统通过PCB管理和控制进程。
2.2 进程控制块PCB（Process Control Block）
进程控制块是由OS维护的用来记录进程相关信息和管理进程而设置的一个专门的数据结构
包含了进程的描述信息、控制信息和资源信息以及现场保护区
PCB是进程动态特性的集中反映
系统通过PCB感知进程的存在，通过PCB中所包含的各项变量的变化，掌握进程的状态以达到控制进程活动的目的
2.2.1 进程控制块PCB的特点
PCB结构的全部或部分常驻内存
PCB随进程的创建而填写，随进程的撤消而释放
系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志
进程与PCB是一一对应的
2.2.2 进程控制块PCB的内容
- 进程描述信息：
- 进程标识符(process ID)，唯一，通常是一个整数
- 进程名，通常基于可执行文件名
- 用户标识符 (user ID)—属于哪个用户
- 进程组关系 (process group)–父进程标识和子进程标识
- 进程控制信息：
- 当前状态–就绪、运行、阻塞
- 优先级(priority)
- 代码执行入口地址–进程的程序和数据所在内存中的首地址
- 程序的外存地址–进程的程序和数据所在外存中的首地址
- 运行统计信息–进程等待时间、进程已经获得处理器的总时间和进程占用内存的时间等。（执行时间、页面调度）
- 进程间同步和通信机制–指实现进程同步和通信时所采取的机制，如消息队列指针和信号量等，他们可以全部或部分存在PCB中
- 事件–进程由某一状态转变为另一状态所等待发生的事件
- 资源占用信息：虚拟地址空间的现状、打开文件列表
- CPU现场保护结构：寄存器值（通用、程序计数器PC、状态PSW，地址包括栈指针）
2.3 进程上下文
2.3.1 进程上下文概述
进程上下文是对进程执行活动全过程的静态描述。进程上下文由进程的用户地址空间内容、硬件寄存器内容及与该进程相关的核心数据结构组成（正文段、数据集、堆栈）。
上文： 把已执行的进程指令和数据在相关寄存器与堆栈中的内容。
正文： 把正在执行的进程指令和数据在相关寄存器与堆栈中的内容。
下文： 把待执行的进程指令和数据在相关寄存器与堆栈中的内容。
用户级上下文：进程的用户地址空间（包括用户栈各层次），包括用户正文段、用户数据段和用户栈
寄存器级上下文：程序寄存器、处理机状态寄存器、栈指针、通用寄存器的值
系统级上下文：
- 静态部分（PCB和资源表格）
- 动态部分：核心栈（核心过程的栈结构，不同进程在调用相同核心过程时有不同核心栈）
2.3.2 进程上下文结构
进程的物理实体与支持进程执行的物理环境合称为进程上下文
2.4 PCB的组织方式
2.4.1 PCB表
- 系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表
- PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度。、
2.4.2 组织方式
链表方式
同一状态的进程其PCB成一链表，多个状态对应多个不同的链表
各状态的进程形成不同的链表：就绪链表、阻塞链表
索引表方式
- 同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表
- 各状态的进程形成不同的索引表：就绪索引表、阻塞索引表
2.5 进程状态及转换
2.5.1 进程的执行状态
进程的执行状态可分为用户执行状态和系统执行状态
用户执行状态，又称用户态，进程的用户程序段执行时，该程序处于用户态。用户态时不可直接访问受保护的OS代码
系统执行状态，又称系统态，核心态，进程的系统程序执行时，该进程处于系统态。核心态时可以执行OS代码，可以访问全部进程空间
划分用户态和系统态的原因：
把用户程序和系统程序分开，以利程序的保护和共享
但增加了系统复杂度和系统开销
2.5.2 进程的三种基本状态
就绪态，执行态，等待态
就绪态（Ready）：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行。“万事俱备，只欠东风”。位于 “就绪队列” 中
执行态（Running）：进程占有了包括CPU在内的全部资源，并在CPU上运行
等待态（Blocked）：阻塞态、挂起态、封锁态、冻结态、睡眠态。指进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）。处于等待态的进程位于等待队列中
就绪 -> 运行：调度程序选择一个新的进程运行
运行 -> 就绪：
运行进程用完了时间片
运行进程被中断，因为一个高优先级进程处于就绪状态
运行 -> 等待：当一进程等待某一事件的发生时，如：
请求系统服务
无新工作可做
初始化I/O且必须等待结果
等待某一进程提供输入(IPC)
等待 -> 就绪：当所等待的事件发生时（例如IO读写完成等）
2.5.3 进程的其他状态
创建状态：创建（新new）状态
OS已完成为创建一进程所必要的工作
已构造了进程标识符；
已创建了管理进程所需的表格、PCB
但还没有允许执行该进程 （尚未同意）
因为资源有限，OS所需的关于该进程的信息保存在主存中的进程表中，但进程自身还未进入主存，也没有为与这个程序相关的数据分配空间，程序保留在辅存中
在批处理系统中，提交新作业；为新登录用户创建进程
引入创建状态，保证进程的调度必须在进程创建后进行，确保对PCB操作的完整性；OS可以根据系统性能或主存容量的限制，推迟 创建进程的提交，增加管理的灵活性
- 导致进程创建的原因：
- 批处理环境中，选择一新作业即将进入内存执行
- 交互环境中，新用户登录到系统
- 操作系统因提供一项服务而创建。如：用户请求打印一个文件，OS可创建严格管理打印的进程，使请求进程可继续执行，与完成打印任务的时间无关
- 由现有进程生成，父进程—-子进程
终止状态（Exit）
- 终止后进程移入该状态
- 它不再有执行资格——PCB清空并将PCB返还系统
- 表格和其它信息暂时保留——状态码和统计数据
- 实用程序为了分析性能和利用率，可能要提取程序的历史信息
导致终止进程的原因：
- 含一个HALT指令或用于终止的OS显式服务调用
- 分时系统中，用户的行为可指示终止，如：用户退出系统或关闭自己的终端，该用户的进程将被终止
- PC机环境中，用户结束一应用程序
- 出现某些错误时，如：I/O失败，无效指令等
- 父进程可请求它的某个子进程终止
- 父进程终止，OS自动终止所有后代进程
- 挂起状态：把一个进程从内存转到外存
2.5.3 五状态进程模型
2.5.3.1 单队列结构
时间片超时也会导致进程状态转换
2.5.3.2 多队列结构
2.5.4 挂起进程模型
由于进程优先级的引入，一些低优先级进程可能等待较长时间，从而被对换至外存。目的是：
- 提高处理机效率：就绪进程表为空时，OS将阻塞进程从内存中 “驱逐” 到磁盘的 “挂起队列”，再从该队列选另一进程进入内存，或接受一个新进程的请求。
- 为运行进程提供足够内存：资源紧张时，暂停某些进程，如：CPU繁忙（或实时任务执行），内存紧张
单挂起进程模型
双挂起进程模型
2.5.5 练习题
如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？
答：考虑单CPU的情况，运行的进程最多有1个，最少0个。就绪进程最多N-1个，最少0个。等待进程最多N个，最少0个。
3. 进程控制
3.1 进程控制的功能
- 完成进程状态的转换
- 完成创建和撤消进程，挂起和激活进程、阻塞和唤醒进程
- 原语(primitive)：由若干条指令构成的 “原子操作(atomic operation)” 过程，作为一个整体而不可分割–要么全都完成，要么全都不做。许多系统调用就是原语
- 原语分为：
- 机器指令级：不允许中断
- 功能级原语：允许中断，不允许并发
- 注意：系统调用并不都是原语。进程A调用read()，因无数据而阻塞，在read()里未返回。然后进程B调用read()，此时read()被重入。系统调用不一定一次执行完并返回该进程，有可能在特定的点暂停，而转入到其他进程
原语是操作系统的核心，它不是由进程而是由一组程序模块所组成，是操作系统的一个组成部分，它必须在管态下执行，并且常驻内存
3.2 进程控制的主要原语
进程创建与撤消原语
进程阻塞与唤醒原语
进程挂起与激活原语
