操作系统期中复习 吴峻峰.pdf

第二章 进程的描述与控制 1、前驱图 前驱图是指一个有向无循环图，可记为DAG，它用于描述进程之间执行的先后顺序。图 中的每个结点可用来表示一个进程或程序段乃至一条语句结点间的有向边则表示两个节点 之间存在的偏序或前趋关系”-” 2、程序的执行顺序 2.1、顺序执行 通常一个应用程序由若干个程序段组成，每一个程序段完成特定的功能，他们在执行时， 都需要按照某种先后次序顺序执行，仅当前一程序段执行完成后，才运行后一程序段 顺序执行时具有这样三个特征:①顺序性：指处理机严格地按照程序所规定的顺序执行， 即每一操作必须在下一操作开始之前结束；②封闭性：指程序在封闭的环境下运行，即程序 运行时独占全机资源，资源的状态（除初始状态外）只有本程序才能改变它，程序一旦开始 执行，其执行结果不受外界因素的影响；③可再现性：指只要程序执行时的环境和初始条件 相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是”停停走走”地执行，都可 获得相同的结果。程序顺序执行时的这种特性为程序员检测和校正程序的错误带来了很大的 方便。 2.2、并发执行 例子：输入程序I1 在输入第一次数据后，由计算程序C1 对该数据进行计算的同时，输 入程序 I2 并发执行。事实上正是由于C1 和 I2 之间并不存在前趋关系，因此他们之间可以 并发执行。如图 对于具有下述四条语句的程序段： S1: a = x + 2 S2: b = y + 4 S3: c = a + b S4: d = c + b 可画出前趋关系。可以看出S3 必须在a 和b 被赋值后方能执行；S4 必须在S3 之后执 行；但S1 和S2 则可以并发执行，因为它们彼此互不依赖。 并发执行的特征。①间断性:程序在并发执行时，由于它们共享系统资源，以及为完成同 一项任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。②失去封闭 性：当系统中存在着多个可以并发执行的程序时，系统中的各种资源将为它们所共享，而这 些资源的状态也由这些程序来改变，致使其中任一程序在运行时，其环境都必然会收到其他 程序的影响。③不可再现性：程序在并发执行时，由于失去了封闭性，也将导致其又失去可 再现性。 3、进程的基本状态及转换 3.1、进程的三种基本状态 (1)、就绪状态（ready） 这是指进程已处于准备好运行的状态，即进程已分配到除CPU 以外的所有必要资源后， 只要再获得CPU，便可立即执行。如果系统中有许多处于就绪状态的进程，通常将它们按一 定的策略（如优先级策略）排成一个队列，称该队列为就绪队列。 (2)、执行状态（running） 这是指进程已获得CPU，其程序正在执行的状态。对任何一个时刻而言，在单处理机系 统中，只有一个进程处于执行状态，而在多处理机系统中，则有多个进程处于执行状态。 (3)、阻塞状态（Block） 这是指正在执行的进程由于发生某事件（如I/O 请求、申请缓冲区失败等）暂时无法继 续执行时的状态，亦即进程的执行受到阻塞。此时引起进程调度，OS 把处理机分配给另一 个就绪进程，而让受阻进程处于暂停状态，一般将这种暂停状态称为阻塞状态，有时也称为 等待状态或封锁状态。通常系统将处于阻塞状态的进程也排成一个队列，称该队列为阻塞队 列。实际上，在较大的系统中，为了减少队列操作的开销，提高系统效率，根据阻塞原因的 不同，会设置多个阻塞队列。 3.2、三种基本状态的转换 3.3、创建状态和终止状态 (1)、创建状态 创建一个进程首先由进程申请一个空白的PCB，并向PCB 中填写用于控制和管理进程的 信息；然后为该进程分配运行时所必须的资源；最后，把该进程转入就绪状态并插入就绪队 列之中。但如果进程所需的资源尚不能得到满足，比如系统尚无足够的内存使进程无法装入 其中，此时创建工作尚未完成，进程不能被调度运行，于是把此时进程所处的状态称为创建 状态。 引入创建状态是为了保证进程的调度必须在创建工作完成后进行，以确保对进程控制块 操作的完整性。同时，创建状态的引入也增加了管理的灵活性。OS 可以根据系统性能或主 存容量的限制推迟新进程的提交（创建状态）。对于处于创建状态的进程，当其获得了所需 的资源以及对其PCB 的初始化工作完成后，便可由创建状态转入就绪状态。 (2)、终止状态 进程的终止也要通过两个步骤：首先，是等待操作系统进行善后处理，最后将其PCB 清 零，并将PCB 空间返还系统。当一个进程到达