第3章 进程管理

1、第3章进程管理 山东交通学院 沈祥玖 中国水利水电出版社 第3章进程管理（1） 3.1 进程的概念和进程的概念和PCB 3.3 进程控制进程控制 3.3 线线 程程 第二章第二章 进程管理进程管理 3.1 进程的基本概念进程的基本概念 3.1.1程序的顺序执行及特征 1. 1. 基本概念基本概念 程序：一个在时间上按严格次序、顺序执 行的操作序列。 程序的顺序执行：一个具有独立功能的程 序独占处理机，直至得到最终结果的过程 。 操作：数据处理的一种规则，一经启动就 需要在有限时间内完成 。 计算：若干操作严格顺序执行的集合 。 3.程序的顺序执行 通常一个程序可分成若干个程 序段，它们必须按照

2、某种先后次序执行， 仅当前一操作执行后，才能执行后继操作。 例如：进行计算。I:输入操作C: 计算操作P:打印操作。在进行计算时， 总是先输入用户的程序和数据，然后进行 计算，最后将结果打印出来。 3.语句的顺序执行 S1：a:=x+y S3：b:=a-5 S3：c:=b+1 如下图，语句S3必须在a被 赋值后才能执行；S3也只能在b 被赋值后才能执行。 4.程序的顺序执行的特征 顺序性：一个程序的各个部分的执行，严 格地按照某种先后次序执行； 封闭性：程序在封闭的环境下运行，即程 序运行时独占全部系统资源； 可再现性：只要程序执行时的环境和初始 条件相同，当程序重复执行时，不论它是 从头到尾

3、不停顿地执行，还是“停停走走” 地执行，都将获得相同的结果。 程序顺序执行的特性，为程序员检测和校 正程序的错误带来很大方便。 3.1.3.前趋图 为了描述一个程序的各部分(程序段 或语句)间的依赖关系，或者是一个 大的计算的各个子任务间的因果关 系，我们常常采用前趋图方式。 图3-1 九个结点的前趋图 前趋图（续） P1为初始结点，P9为终止结点每个结点 还具有一个重量。 该前趋图，存在下面的前趋关系： P1P2，P1P3，P1P4，P3P5， P3P5，P4P6，P4P7，P5P8， P6P8，P7P9，P8P9；或表示为： =P1,P2,P3,P4,P5,P6,P7,P8,P9 =(P1

4、,P2),(P1,P3),(P1,P4), (P2,P5),(P3,P5),(P4,P6), (P4,P7),(P5,P8),(P6,P8), (P7,P9),(P8,P9) 前趋图（续） 前趋图中的每个结点可以表示一条语句、 一个程序段或进程，结点间的有向边表示 两个结点之间存在的偏序(Partial_Order) 或前趋关系(Precedence_Relation)“” (Pi,Pj)|在Pj开始前Pi必须完成如果 (Pi,Pj)，可写成PiPj，Pi是Pj的 直接前趋，Pj是Pi的直接后继。前趋图中 必须不存在循环，如下图不是前趋图。 3.1.3 程序并发执行及特征 1.1.并发环境：并

5、发环境： 在一定时间内物理机器上有 两个或两个以上的程序同处于开 始运行但尚未结束的状态，并且 次序不是事先确定的 3. 程序的并发执行 在对一批程序进行处理时，可以并发执行。 例如，输入、计算、打印三个程序对一批 作业进行处理时，存在以下的前趋关系： IiCi，IiIi+1，CiPi，CiCi+1， PiPi+1 图3-3并发执行时的前趋图 在上例中存在下述前趋关系： IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1 在Pi-1和Ci以及Ii+1之间，可以并发执行。 对于具有下述四条语句的程序段： S1:a =x+3 S3:b =y+4 S3:c =a+b S4:d =c+b 图

6、3-3四条语句的前趋关系 3.程序的并发执行的特征 不可再现性：不可再现性：由于程序的并发执行，打 破了由另一程序独占系统资源的封闭性， 因而破坏了可再现性。 间断性：间断性：程序并发执行时，由于它们共享 资源或程序之间相互合作完成一项共同任 务，因而使程序之间相互制约。 通信性：通信性：对于相互合作的程序，为了更有 效地协调运行，相互之间进行通信。 独立性：独立性：并发程序在运行过程中，既然是 作为一个独立的运行实体，它也必然具有 作为一个单位去获得资源的独立性。 4.多道程序设计 定义定义：Multiprogramming （引入目的是为了提高系统效率） 与并发不完全是一个概念，但效果相似

7、 考虑因素：考虑因素： 当各用户对资源使用上发生冲突时，如何处理竞争 对CPU只能通过调度来解决竞争问题，而对于其他 资源通过申请分配使用回收的办法进行管理， 当且仅当占有CPU的时候才可以申请，否则要排队 等候 3.1.4 进程的特征与状态 1.进程的概念 进程是具有独立功能的程序关于某个数 据集合上的一次运行活动，是系统进行资 源分配和调度的独立单位 进程是可与其他程序并发执行的程序， 在一个数据集合上的运行过程。它是系统 进行资源分配和调度的一个独立单位。 2. 进程的特征 动态性：动态性：进程的实质是程序的一次执行过程， 进程是动态产生，动态消亡的，进程在其生 命周期内，在三种基本状态

8、之间转换 并发性：并发性：任何进程都可以同其他进程一起向 前推进 独立性：独立性：进程是一个能独立运行的基本单位， 同时也是系统分配资源和调度的独立单位； 异步性：异步性：由于进程间的相互制约，使进程具 有执行的间断性，即进程按各自独立的、不 可预知的速度向前推进 结构特征：结构特征：为了控制和管理进程，系统为每 个进程设立一个进程控制块 PCB。 3. 进程与程序的区别 程序可作为软件资源长期保存，进程只是一次执 行过程，是暂时的； 进程是系统分配调度的独立单位，能与其他进程 并发执行; 4. 进程创建与中止 1）进程何时创建）进程何时创建 提交一个批处理作业 用户登录 由OS创建，用以向一

9、用户提供服务( 如：打 印文件) 由已存在的一进程创建 一个用户程序可创建成多个进程 进程何时中止 批处理作业发出暂停（Halt）指令 用户退出登录 进程执行一中止服务请求 出错及失败因素 5. 进程中止的原因 正常结束 给定时限到 缺少内存 存储器出界 保护性出错：例子: 写只读文件 算术错 超出时间：进程等待超过对某事件的最大值 I/O 失败 无效指令：如试图执行数据 特权指令 操作系统干预：如当死锁发生时 父进程请求中止某一子进程 父进程中止，所以子进程也中止 运行运行 就绪就绪 等待等待 图图3 34 4 进程的状态及其转换进程的状态及其转换 进程状态（续） 当进程已分配到除CPU以外

10、的所有必要资源时， 它便处于就绪状态，一旦获得CPU，便立即执行。 已获得CPU的进程进入执行状态。 正在执行的进程，由于发生某个事件而暂时无法 执行时，便放弃处理机而进入阻塞状态。 由于执行的进程变为阻塞状态后，调度程序立即 把处理机分配给另一个就绪进程；因此，阻塞进 程的事件消失后，进程不会立即恢复到执行状态， 而转变为就绪状态，重新等待处理机。 2）进程状态转换条件 在进程运行过程中，由于自身进展情况 及外界环境的变化，这三种基本状态可以依 据一定的条件相互转换： 就绪 - 运行 调度程序选择一个新的进程运行 运行 - 就绪 运行进程用完了时间片 运行进程被中断，因为一高优先级进程 处于

11、就绪状态 进程状态转换条件（续） 运行 - 等待 当一进程必须等待时 OS尚未完成服务 对一资源的访问尚不能进行 初始化I/O 且必须等待结果 等待某一进程提供输入 (IPC) 等待 - 就绪 当所等待的事件发生时 创建状态 终止状态 挂起状态 （调节负载，对换，父进程， 操作系统，终端用户） 3）其他状态 创建( 新new)状态 OS 已完成为创建一进程所必要 的工作 已构造了进程标识符 已创建了管理进程所需的表格 但还没有允许执行该进程 (尚未 同意) 因为资源有限 终止（退出exit)状态 中止后进程移入该状态 它不再有执行资格 表格和其它信息暂时由辅助程序保留 例子: 为处理用户帐单而

12、累计资源 使用情况的财务程序 当数据不再需要后，进程(和它的表格) 被删除 4）具有挂起操作的进程状态转换图 有的系统有时希望能人为地把进程挂起，使 之处于静止状态，以便研究其执行情况或对它进行 修改。下图示出了具有挂起状态的进程状态演变图。 图35 具有挂起状态的进程状态演变图 五状态进程模型 准备退出：父进程可中止子进程 七状态进程模型 活动活动 挂起挂起 事件事件 发生发生 事件事件 发生发生 等待等待 事件事件 挂起挂起 调度调度 超时超时 释放释放 活动活动 挂起挂起 7. 进程控制块（PCB） 系统为了管理进程设置的一个专 门的数据结构，存放了用于描述 该进程情况和控制进程运行所需

13、 的全部信息。 系统利用PCB来控制和管理进程， 所以PCB是系统感知进程存在的唯 一标志 进程与PCB是一一对应的 1)进程控制块的内容 进程标识符：标识一个进程的编号，也称 为进程的内部名； 现性状态：说明进程的当前状态； 现场保留区：保存进程由执行状态变为其 它状态时的CPU现场信息； 程序与数据地址：该进程的程序和数据所 在位置信息； 互斥与同步机构：实现进程间互斥与同步 时所必须的机构； 进程控制块的内容（续） 进程通信机制：用于实现进程间的通信所 需的数据结构； 优先级：表示进程使用CPU时优先级别的 一个整数； 资源清单：列出进程拥有的资源的记录； 连接字：给出本进程所在队列中的

14、下一个 进程的PCB首址； 家族联系：用于说明本进程与其它家族成 员间的关系。 3)进程映象 (进程要素) 用户程序 用户数据 栈 用于过程调用和参数传递 进程控制块PCB (执行上下文) 控制进程所需的数据(进程属性)， 包括: 进程标识符信息 处理器状态信息 进程控制信息 3）进程控制块的组织方式 为了有效地对进程控制块进行管理， 应该采用适当的方式把它们组织起来。 目前常用的组织方式有以下两种： 按链接方式组织PCB (队列) 不同状态进程分别组成队列 运行队列、就绪队列、等待队列 按索引方式组织PCB (表) 对具有相同状态的进程，分别设置各自 的PCB索引表，表明PCB在PCB表中的

15、地址 （其他方式：线性表或链表） 按索引方式组织PCB 按链接方式组织PCB PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 PCBn . 空空 PCBPCB 运行态运行态 就绪态就绪态 等待等待1 1 等待等待3 3 6 7 5 10 15 3.3 进程控制 1.进程控制的主要任务 进程控制是对系统中所有进程从产 生、存在到消亡的全过程实行有效的管 理和控制。进程控制一般是由操作系统 的内核来实现，内核在执行操作时，往 往是通过执行各种原语操作来实现的。 3.进程图 进程图是一棵有向树(如下图)， 结点代表进程。一棵树表示一个家 族 ， 根 结 点 为 该 家 族 的

16、祖 先 (Ancestor)。 3.进程图和前趋图之间的差异 前趋图描述的是任务(或进程)之间的前趋 关系；只有在前趋进程完成后，其后继进 程才能运行； 在进程图中，创建者和被创建者可以并发 执行，也可以父进程等待其所有的子进程 结束后再执行，这完全取决于创建原语和 创建者的需要。原语：原语：是由若干条机器指 令所构成，用以完成特定功能的一段程序 4.内核与原语 内核：内核：加在硬件上的第一层软件，通过执行各种 原语操作来实现各种控制和管理功能，具有创建、 撤消、进程通信、资源管理的功能。 内核的基本功能 支撑功能：中断处理、时钟管理、原语操作 资源管理功能：进程管理、存贮管理、设备管理 原语

17、：原语：是由若干条机器指令所构成，用以完成特 定功能的一段程序 。 5.进程控制 创建、撤消进程以及完成进 程各状态之间的转换。由具有特 定功能的原语完成。 进程创建原语 进程撤消原语 阻塞原语 唤醒原语 挂起原语 激活原语 1)创建原语 功能功能：创建一个具有指定标识符 进程 入口信息入口信息：进程标识符、优先级、 进程开始地址、初始CPU状态、 资源清单等。 进程创建过程 创建一个PCB 赋予一个统一进程标识符 为进程映象分配空间 初始化进程控制块 许多默认值 (如: 状态为 New，无 I/O设备或文件.) 设置相应的链接 如: 把新进程加到就绪队列的链表中 创建原语的实现过程 3)进程

18、的撤消原语 功能：撤消一个指定的进程 入口信息：被撤消的进程名 实现:收回进程所占有的资源, 撤消该进程的PCB 引起撤消的原因 正常结束 异常结束（越界错、保护错、特权 指令错、非法指令、运行超时、 I/O故障等） 外界干预（操作员干预、父进程请 父进程终止） 撤消原语的实现过程 3) 进程阻塞 处于运行状态的进程，在其运行过 程中期待某一事件发生，如等待键盘输 入、等待磁盘数据传输完成、等待其它 进程发送消息，当被等待的事件未发生 时，由进程自己执行阻塞原语，使自己 由运行态变为阻塞态。 进程的阻塞原语 功能：停止调用进程 的执行，变为等待。 入口信息：可省 阻塞原语的实现过程 4) 进程

19、的唤醒原语 功能：功能：唤醒某一处于等待队列当中的进程。 入口信息：入口信息：被唤醒进程的名字 引起唤醒的原因 系统服务由不满足到满足 I/O完成 新数据到达 进程提出新请求（服务） 唤醒原语的实现过程 5)进程的挂起与激活 挂起原语的功能：自身挂起、挂起 具有指定标识符的进程、将其进程 及其全部或部分“子孙”挂起。 激活原语功能：使处于静止状态的 进程变为活动。 6. 系统核心 1)1)系统核心：系统核心： 向上提供多个无中断的虚拟机器 在核心内不允许中断 3)3)特点：特点： 为进程运行提供一个舞台 核心常驻内存 设计短小精焊 3)核心的组成 中断处理 进程管理: 调度 控制 通讯 互斥

20、同步等 原语管理: 在核心中提供一系列原语，同步, 通信，创建，撤消等 4) 队列管理 队列数据结构:指向队首的表指针 三个队列: 运行，就绪，等待队列 排队方式: 排队首 排队尾 插 队 出队方式: 队首出队/队中出队 队列管理: 中断之后，进程调度之前 5) 现场管理 保存现场;注意顺序,中断之后第一步 恢复现场:恢复时机，进程调度最后一步 时钟管理: 以固定频率 +1 -1 用途:进入绝对时钟 间隔时钟 进行分析比较 6) 虚时钟 每个进程分配给一个虚时钟来记 录CPU时间,这个时钟称为虚时钟。 虚时钟存放在PCB中，属于现场的 一部分，进程运行时，将虚时钟放入 内存开辟的专门单元，离开

21、CPU则放在 PCB中。 核心处理流程流程: 7)内核的执行特点 由中断驱动的: 中断内核退出 内核执行是连续的 内核执行过程中在中断屏蔽状态下 内核使用特权指令 思考题 1如果系统中有N个进程，运行的进程最多 几个，最少几个；就绪进程最多几个,最少 几个；等待进程最多几个，最少几个？ 3. 有没有这样的状态转换，为什么？ 等待运行； 就绪等待 3. 一个状态转换的发生，是否一定导致另一 个转换发生，列出所有的可能 4. 举3个日常生活中类似进程的例子 第第3章章 进程管理进程管理 3.7 线线 程程 3.7 3.7 线线 程程 1.1.进程的两个基本属性：进程的两个基本属性： 资源的拥有者：

22、 给每个进程分配一虚拟地址空间， 保存进程映像，控制一些资源（文 件，I/O设备），有状态、优先级、 调度 调度单位： 进程是一个执行轨迹 以上两个属性构成进程并发执行 的基础 3. 线程的引入 对进程系统必须完成的操作： 创建进程 撤消进程 进程切换 缺点： 时间空间开销大，限制并发 度的提高 线程的引入（续1） 在操作系统中，进程的引入提高了计算机资 源的利用效率。但在进一步提高进程的并发 性时，人们发现进程切换开销占的比重越来 越大，同时进程间通信的效率也受到限制 线程的引入正是为了简化进程间的通信，以 小的开销来提高进程内的并发程度 线程：有时称轻量级进程，进程中的一个 运行实体，是一

23、个CPU调度单位，资源的拥 有者还是进程或称任务 线程的引入（续2） 线程： 有执行状态（状态转换） 不运行时保存上下文 有一个执行栈 有一些局部变量的静态存储 可存取所在进程的内存和其他资源 可以创建、撤消另一个线程 3. 线程的特点 是进程的一个实体，可作为系统独立调 度和分派的基本单位。 不拥有系统资源（只拥有从属进程的全 部资源，资源是分配给进程） 一个进程中的多个线程可并发执行。 （进程可创建线程执行同一程序的不同 部分） 系统开销小、切换快。（进程的多个线 程都在进程的地址空间活动） 单进程、单线程 单进程、多线程 多进程、一个进程一个线程 多进程、一个进程多个线程 4.线程和进程

24、的关系 P C B 用用 户户 栈栈 单线程进程模型单线程进程模型 用户地址空间用户地址空间 核核 心心 栈栈 线程控制块：线程控制块： 包含了寄存器映像，线程优先数和线程状态信息包含了寄存器映像，线程优先数和线程状态信息 P C B 多线程进程模型多线程进程模型 用户用户 地址地址 空间空间 用用 户户 栈栈 核核 心心 栈栈 线程线程 控制块控制块 用用 户户 栈栈 核核 心心 栈栈 线程线程 控制块控制块 用用 户户 栈栈 核核 心心 栈栈 线程线程 控制块控制块 5.引入线程的好处 创建一个新线程花费时间少（结束亦 如此） 两个线程的切换花费时间少 （如果机器设有“存储恢复所有寄 存器

25、”指令，则整个切换过程用几条 指令即可完成） 因为同一进程内的线程共享内存和文 件，因此它们之间相互通信无须调用 内核 适合多处理机系统 例子1： LAN中的一个文件服务器，在一段 时间内需要处理几个文件请求 因此有效的方法是：为每一个请 求创建一个线程 在一个SMP机器上：多个线程可以 同时在不同的处理器上运行 例子3： 一个线程显示菜单，并读入用户输入； 另一个线程执行用户命令 考虑一个应用：由几个独立部分组成， 这几个部分不需要顺序执行，则每个部 分可以以线程方式实现 当一个线程因I/O阻塞时，可以切换到同 一应用的另一个线程 6.线程与进程的比较 调度：线程作为调度的基本单位，同进程

26、中线程切换不引起进程切换，当不同进程 的线程切换才引起进程切换；进程作为拥 有资源的基本单位。 并发性：一个进程间的多个线程可并发。 拥有资源：线程仅拥有隶属进程的资源； 进程是拥有资源的独立单位。 系统开销：进程大；线程小。 7. 线程的实现机制 用户级线程 核心级线程 两者结合方法 1) 用户级线程（ULT） 由应用程序完成所有线程的管理 通过线程库(用户空间) 一组管理线程的过程 核心不知道线程的存在 线程切换不需要核心态特权 调度是应用特定的 对用户级线程的核心活动 核心不知道线程的活动，但仍然管理线 程的进程的活动 当线程调用系统调用时，整个进程阻塞 但对线程库来说，线程仍然是运行状态 即线程状态是与进程状态独立的 用户级线程的优点和缺点 优点： 线程切换不调用核心 调度是应用程序特定的：可以选择最好的算法 ULT可运行在任何操作系统上（只需要线程库） 缺点： 大多数系统调用是阻塞的，因此核心阻塞进程， 故进程中所有线程将被阻塞 核心只将处理器分配给进程，同一进程中的两 个线程不能同时运行于两个处理器上 3) 核心级线程（KLT） 所有线程管理由核心完成 没有线程库，但对核心线程工具提供API 核心维护进程和线程的上下文 线程之间的切换需要核心支持