第二讲 进程管理

1、1 第第2章章 进程管理进程管理 2.12.1 进程的基本概念进程的基本概念 2.22.2 进程控制进程控制 2.32.3 进程同步进程同步 2.42.4 经典进程同步问题经典进程同步问题 2.52.5 管程机制管程机制 实现互斥的软件机制和硬件机制实现互斥的软件机制和硬件机制( (补充补充) ) 2.62.6 进程通信进程通信 2.72.7 线程线程 第一次课内上机实验第一次课内上机实验 2 2.12.1 进程的基本概念进程的基本概念 n 程序的顺序执行及其特征程序的顺序执行及其特征 n 程序的并发执行及其特征程序的并发执行及其特征 n 进程的特征与状态进程的特征与状态 n 进程控制块进程控

2、制块 3 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征 n程序的顺序执行程序的顺序执行 仅当前一操作仅当前一操作( (程序段程序段) )执行完后，才能执行后继操作。执行完后，才能执行后继操作。 例如，在进行计算时，总须先输入用户的程序和数例如，在进行计算时，总须先输入用户的程序和数 据，然后进行计算，最后才能打印计算结果。据，然后进行计算，最后才能打印计算结果。 S1: a=x+yS1: a=x+y; ; S2: b=a-5;S2: b=a-5; S3: c=b+1;S3: c=b+1; (a) 程序的顺序执行(b) 三条语句的顺序执行 I1C1P1I2C2P2S1S2S3 4 2

3、.1.1 程序的顺序执行及其特征程序的顺序执行及其特征 顺序执行包含两层含义：顺序执行包含两层含义： l 对于多个用户程序来说，所有程序是依次执对于多个用户程序来说，所有程序是依次执 行的。（外部顺序性）行的。（外部顺序性） l 对于一个程序来说，它的所有指令是按序执对于一个程序来说，它的所有指令是按序执 行的。（内部顺序性）行的。（内部顺序性） 5 n程序顺序执行的特征程序顺序执行的特征 （1）顺序性：）顺序性： 处理机的操作严格按照程序所规定的顺序执行，处理机的操作严格按照程序所规定的顺序执行， 即每一操作必须在下一操作开始之前结束（或者即每一操作必须在下一操作开始之前结束（或者 说下一操

4、作必须在当前操作结束后才能开始）。说下一操作必须在当前操作结束后才能开始）。 （2）封闭性：）封闭性： 程序是在封闭的环境下执行的。即程序是在封闭的环境下执行的。即 程序运行时独占全机资源，资源的状态（除初始程序运行时独占全机资源，资源的状态（除初始 态外）只有本程序才能改变它。态外）只有本程序才能改变它。 程序一旦开始执行，其执行结果不受外界影响。程序一旦开始执行，其执行结果不受外界影响。 （3）可再现性：）可再现性： 只要程序执行时的环境和初始条件相同，当程只要程序执行时的环境和初始条件相同，当程 序重复执行时，都将获得相同的结果。序重复执行时，都将获得相同的结果。 6 程序的并发执行程序

5、的并发执行包括两层含义：包括两层含义： l 对于一个程序来说，它的所有指令是对于一个程序来说，它的所有指令是 按序执行的。（内部顺序性）按序执行的。（内部顺序性） l 对于多个程序（进程）来说，所有进对于多个程序（进程）来说，所有进 程是交叉执行的。（外部并发性）程是交叉执行的。（外部并发性） 2.1.3 程序的并发执行及其特征程序的并发执行及其特征 7 n前趋图前趋图 前趋图前趋图(Precedence Graph)是一个有向无循环图，记为是一个有向无循环图，记为 DAG(Directed Acyclic Graph)，用于描述进程之间执行的前，用于描述进程之间执行的前 后关系。图中的每个结

6、点可用于描述一个程序段或进程，乃后关系。图中的每个结点可用于描述一个程序段或进程，乃 至一条语句；结点间的有向边则用于表示两个结点之间存在至一条语句；结点间的有向边则用于表示两个结点之间存在 的偏序的偏序(Partial Order)或前趋关系或前趋关系(Precedence Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果如果(Pi, Pj),可写成可写成PiPj，称，称Pi是是Pj的直接前趋，而称的直接前趋，而称Pj是是Pi的直的直 接后继。在前趋图中，把没有前趋的结点称为初始结点接后继。在前趋图中，把没有前趋的

7、结点称为初始结点 (Initial Node)，把没，把没有后继的结点称为终止结点有后继的结点称为终止结点(Final Node)。 8 n前趋图前趋图 每个结点还具有一个重量每个结点还具有一个重量(Weight)，用于表示该结点用于表示该结点 所含有的程序量或结点的执行时间。所含有的程序量或结点的执行时间。 IiCiPi和和S1S2S3 P1P3P8P9 P4 P2 P5 P6 P7 S1 S2 S3 (a) 具有九个结点的前趋图(b) 具有循环的前趋图 9 n前趋图前趋图 对于图对于图 2-2(a)所示的前趋图，所示的前趋图， 存在下述前趋关系：存在下述前趋关系： P1P2, P1P3,

8、P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9 或表示为：或表示为： P=P1, P2, P3, P4, P5, P6, P7, P8, P9 = (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9) 应当注意，前趋图中必须不存在循环，但在图应当注意，前趋图中必须不存在循环，但在图2-2(b)中却有着中却有着 下述的前趋关系：下述的前趋关系：S2S3, S3S2 10 n前趋

9、图前趋图 前趋图前趋图(Precedence Graph)是一个有向无循环图，记为是一个有向无循环图，记为 DAG(Directed Acyclic Graph)，用于描述进程之间执行的前，用于描述进程之间执行的前 后关系。图中的每个结点可用于描述一个程序段或进程，乃后关系。图中的每个结点可用于描述一个程序段或进程，乃 至一条语句；结点间的有向边则用于表示两个结点之间存在至一条语句；结点间的有向边则用于表示两个结点之间存在 的偏序的偏序(Partial Order)或前趋关系或前趋关系(Precedence Relation)“”。 =(Pi, Pj)|Pi must complete bef

10、ore Pj may start, 如果如果(Pi, Pj),可写成可写成PiPj，称，称Pi是是Pj的直接前趋，而称的直接前趋，而称Pj是是Pi的直的直 接后继。在前趋图中，把没有前趋的结点称为初始结点接后继。在前趋图中，把没有前趋的结点称为初始结点 (Initial Node)，把没，把没有后继的结点称为终止结点有后继的结点称为终止结点(Final Node)。 11 2.1.3 程序的并发执行及其特征程序的并发执行及其特征 P1P2P3P4 I1I2I3I4 C 1 C 2 C 3 C 4 图图 2-3 并发执行时的前趋图并发执行时的前趋图 12 2.1.3 程序的并发执行及其特征程序的

11、并发执行及其特征 在该例中存在下述前趋关系：在该例中存在下述前趋关系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1 而而Ii+1和和Ci及及Pi-1是重迭的，亦即在是重迭的，亦即在Pi-1和和Ci以及以及Ii+1之间，可之间，可 以并发执行。以并发执行。 对于具有下述四条语句的程序段：对于具有下述四条语句的程序段： S1: a =x+2 S2: b =y+4 S3: c =a+b S4: d =c+b 13 1）间断性）间断性: : 程序在并发执行时，由于它们共享系统资程序在并发执行时，由于它们共享系统资 源，以及为完成同一任务而相互合作，致源，以及为完成同一任务而相互合

12、作，致 使这些并发执行的程序之间形成了相互制使这些并发执行的程序之间形成了相互制 约的关系。（互斥关系、同步关系）约的关系。（互斥关系、同步关系） 相互制约导致并发执行的程序具有相互制约导致并发执行的程序具有“执行执行 暂停暂停执行执行”这种间断性活动规律。这种间断性活动规律。 2）失去封闭性：）失去封闭性： 程序在并发执行时，由于多个程序在并发执行时，由于多个 程序共享系统资源，因而这些程序共享系统资源，因而这些 资源的状态将由多个程序来改资源的状态将由多个程序来改 变，致使程序的运行已失去了变，致使程序的运行已失去了 封闭性。封闭性。 某程序的执行时，某程序的执行时， 会受到其他程序的会受

13、到其他程序的 影响。影响。 14 3）不可再现性）不可再现性与时间有关的错误与时间有关的错误 程序在并发执行时，由于失去了封闭性，也将导致程序在并发执行时，由于失去了封闭性，也将导致 其失去可再现性。其失去可再现性。 例如例如：有两个循环程序：有两个循环程序A A和和B B，它们共享一个变量，它们共享一个变量N N L1：N = N+1； goto L1； L2：print (N)； N = 0； goto L2； 程程 序序 A 程程 序序 B 程序程序A和和B并发执行时，可能出现下述三种情况并发执行时，可能出现下述三种情况(设设N的值为的值为10)： (1) N=N+1在在print(N)

14、和和N=0之前，此时得到的之前，此时得到的N值分别为值分别为11,11,0。 (2) N=N+1在在print(N)和和N=0之后，此时得到的之后，此时得到的N值分别为值分别为10,0,1。 (3) N=N+1在在print(N)和和N=0之间，此时得到的之间，此时得到的N值分别为值分别为10,11,0。 上述三种情况中，上述三种情况中，(1)(1)、(2)(2)结果正确，结果正确，(3)(3)结果出错。可见计算结果已与并结果出错。可见计算结果已与并 发程序的执行速度发程序的执行速度( (推进速度推进速度) )有关，从而使程序执行失去了可再现性。有关，从而使程序执行失去了可再现性。 15 2.

15、1.4 进程的特征与状态进程的特征与状态 1进程的定义和特征进程的定义和特征 进程是程序在一个数据集上的运行过程，是系进程是程序在一个数据集上的运行过程，是系 统进行资源分配和调度的一个独立单位。统进行资源分配和调度的一个独立单位。 (传传 统统OS的定义的定义) 定定 义义 (1) (1) 进程是程序的一次执行。进程是程序的一次执行。 (2) (2) 进程是一个程序及其数据在处理机上顺序进程是一个程序及其数据在处理机上顺序 执行时所发生的活动。执行时所发生的活动。 (3)(3)进程进程是进程实体的运行过程，是系统进行资是进程实体的运行过程，是系统进行资 源分配和调度的一个独立单位源分配和调度

16、的一个独立单位”。 其其 他他 16 为了描述和控制进程的运行，系统为每个进程定义了为了描述和控制进程的运行，系统为每个进程定义了 一个数据结构一个数据结构进程控制块。进程控制块。 进程控制块是进程实体的一部分，是操作系统中最重进程控制块是进程实体的一部分，是操作系统中最重 要的记录型数据结构。要的记录型数据结构。 1. PCB作用：作用： 使一个在多道程序环境下不能独立运行的程序使一个在多道程序环境下不能独立运行的程序( (含数据含数据) )， 成为一个能独立运行的基本单位，一个能与其它进程并发成为一个能独立运行的基本单位，一个能与其它进程并发 执行的进程。或者说，执行的进程。或者说，OS是

17、根据是根据PCB来对并发进程进行控来对并发进程进行控 制和管理的。制和管理的。 例如：进程调度；现场保护和恢复；进程同步和例如：进程调度；现场保护和恢复；进程同步和 通信。通信。 PCB是进程存在的唯一标志是进程存在的唯一标志 2.1.5 进程控制块（进程控制块（PCB） 17 2进程控制块中的信息进程控制块中的信息 PCB中记录了操作系统所需的、用于描述进程当前中记录了操作系统所需的、用于描述进程当前 情况以及控制进程运行的全部信息。具体包括下述情况以及控制进程运行的全部信息。具体包括下述 四方面的信息：四方面的信息： 1）进程标识符：）进程标识符： 内部标识符内部标识符( (进程号进程号)

18、 )；外部标识符外部标识符( (名名) )； 父进程标识及子进程标识；用户标识父进程标识及子进程标识；用户标识 2）处理机状态：）处理机状态： 处理机状态信息主要由处理机的各种寄存处理机状态信息主要由处理机的各种寄存 器中的内容组成的。寄存器包括：通用寄器中的内容组成的。寄存器包括：通用寄 存器、指令计数器、程序状态字（存器、指令计数器、程序状态字（PSWPSW） 寄存器、用户栈指针。寄存器、用户栈指针。( (保护、恢复现场保护、恢复现场) ) 当处理机被中断时，这些信息都必须保存到当处理机被中断时，这些信息都必须保存到PCB中，以便中，以便 该进程重新执行时，能从断点继续执行。该进程重新执行

19、时，能从断点继续执行。 18 3）进程调度信息）进程调度信息： 在在PCB中还存放一些与中还存放一些与进程调度进程调度和进程对换有关的信息。包括：和进程对换有关的信息。包括： 进程状态进程状态作为调度和对换时的依据。作为调度和对换时的依据。 进程优先级进程优先级由于描述进程使用处理机的优先由于描述进程使用处理机的优先 级别的一个整数，优先级高的进程优先获得处理级别的一个整数，优先级高的进程优先获得处理 机。机。 进程调度所需的其它信息进程调度所需的其它信息它们与所采用的进它们与所采用的进 程调度算法有关。程调度算法有关。 事件事件即阻塞原因。即阻塞原因。 19 4）进程控制信息：）进程控制信息

20、： l 程序和数据的地址程序和数据的地址指程序和数据所在的内存指程序和数据所在的内存 或外存首地址；或外存首地址； l 进程同步和通信机制进程同步和通信机制如信号量、消息队列指如信号量、消息队列指 针等，它们可能全部或部分地存放在针等，它们可能全部或部分地存放在PCB中；中； l 资源清单资源清单是一张列出了除是一张列出了除CPU外的、进程外的、进程 所需的全部资源及已经分配到该进程的资源的清所需的全部资源及已经分配到该进程的资源的清 单；单； l 链接指针链接指针它给出本进程（它给出本进程（PCB）所在队列中）所在队列中 下一个进程的下一个进程的PCB的首址。的首址。 20 3进程控制块的组

21、织方式进程控制块的组织方式 常用的组织方式有两种：常用的组织方式有两种：链接方式链接方式和和索引方式索引方式。 1）链接方式）链接方式 把具有同一状态的把具有同一状态的 PCB，用其中的链，用其中的链 接字链接成一个队接字链接成一个队 列。形成：列。形成：就绪队就绪队 列列、阻塞队列阻塞队列、空空 白队列白队列等等 21 2）索引方式）索引方式: : 系统根据所有进程系统根据所有进程 的状态建立几张索的状态建立几张索 引表。如，引表。如， 就绪索引表就绪索引表 阻塞索引表等阻塞索引表等 索引表的首址记录在索引表的首址记录在 专用单元中；专用单元中； 每个索引表的表目中，每个索引表的表目中， 记

22、录具有相应状态的某记录具有相应状态的某 个个PCBPCB的首址。的首址。 22 2.1.4 进程的特征与状态进程的特征与状态 1进程的特征进程的特征 1）结构特征：）结构特征： 程序段、相关的数据段、程序段、相关的数据段、PCB三三 部分构成了部分构成了进程实体进程实体。 2）动态性：）动态性：进程的实质是进程实体的一次执行过进程的实质是进程实体的一次执行过 程，故程，故动态性是进程的最基本特征动态性是进程的最基本特征。 23 4）独立性）独立性 ： 在传统的在传统的OS中，独立性是指进程实中，独立性是指进程实 体是一个能独立运行、独立分配资体是一个能独立运行、独立分配资 源和独立接受调度的基

23、本单位。源和独立接受调度的基本单位。 5）异步性）异步性 ： 是指进程按各自独立的、不可预知的是指进程按各自独立的、不可预知的 速度向前推进，或说进程实体按异步速度向前推进，或说进程实体按异步 方式运行。方式运行。 3）并发性：）并发性： 这是指多个进程实体同存于内存这是指多个进程实体同存于内存 中，且能在一段时间内同时运行。中，且能在一段时间内同时运行。 24 进程的三种基本状态：进程的三种基本状态： 1）就绪（）就绪（Ready）状态：）状态： 当进程已分配到除当进程已分配到除CPU以外的所有资源后，只要再获以外的所有资源后，只要再获 得得CPU，便可立即执行，进程这时的状态称为就绪状，便

24、可立即执行，进程这时的状态称为就绪状 态。态。 2）执行（）执行（Running）状态）状态: : 进程已获得进程已获得CPU，其程序正在执行，其程序正在执行。 3）阻塞（）阻塞（Blocked）状态）状态: : 正在执行的进程由于发生某事件而暂时无法继续执行正在执行的进程由于发生某事件而暂时无法继续执行 时，便放弃处理机而处于暂停状态，亦即进程的执行时，便放弃处理机而处于暂停状态，亦即进程的执行 受到阻塞，把这种暂停状态称为阻塞状态（或等待状受到阻塞，把这种暂停状态称为阻塞状态（或等待状 态）态）。 25 进程的三种基本状态的转换：进程的三种基本状态的转换： 进程调度进程调度：就绪态：就绪态

25、执行态执行态 时间片完时间片完：执行态：执行态就绪态就绪态 请求请求I/O：执行态：执行态阻塞态阻塞态 I/O完成完成：阻塞态：阻塞态就绪态就绪态 引起进程状态转换的典型事件：引起进程状态转换的典型事件： 26 挂起状态挂起状态： 有些系统除了进程的三种基有些系统除了进程的三种基 本状态外，还有挂起状态本状态外，还有挂起状态。 1）引入挂起状态的原因引入挂起状态的原因： （1）终端用户的请求：）终端用户的请求： （2）父进程请求：）父进程请求： （3）负荷调节的需要）负荷调节的需要 ： （4）操作系统的需要）操作系统的需要 ： 当当终端用户在自己的程序运行期间发终端用户在自己的程序运行期间发

26、现有可疑问题时，希望暂停执行。现有可疑问题时，希望暂停执行。 希望考察和修改子进程，或协调各希望考察和修改子进程，或协调各 子进程间的活动时子进程间的活动时 实时系统中工作负荷较重时，系统实时系统中工作负荷较重时，系统 可把一些不重要的进程挂起。可把一些不重要的进程挂起。 操作系统有时希望挂起某些进程，操作系统有时希望挂起某些进程， 以便检查运行中的资源使用情况或以便检查运行中的资源使用情况或 进行记账。进行记账。 27 2 2）具有）具有挂起状态系统的挂起状态系统的进程状态的转换进程状态的转换 活动就绪活动就绪静止就绪静止就绪 活动阻塞活动阻塞静止阻塞静止阻塞 静止就绪静止就绪活动就绪活动就

27、绪 静止阻塞静止阻塞活动阻塞活动阻塞 挂起原语挂起原语Suspend 激活原语激活原语Active 28 创建状态创建状态 创建一个进程一般包括两个步骤：创建一个进程一般包括两个步骤： 1)1)为一个新进程创建为一个新进程创建PCB,PCB,并填写必要的管理信息。并填写必要的管理信息。 2 2）把该进程转入就绪状态并插入到就绪队列中。）把该进程转入就绪状态并插入到就绪队列中。 当一个新进程被创建时，系统已经为其分配了当一个新进程被创建时，系统已经为其分配了PCB,PCB, 填写了进程标识等信息，但是由于该进程所必须的资填写了进程标识等信息，但是由于该进程所必须的资 源或其他信息如主存资源等尚未

28、分配，此时的源或其他信息如主存资源等尚未分配，此时的进程已进程已 经拥有了自己的经拥有了自己的PCB,PCB,但进程自身还未进入主存，即进但进程自身还未进入主存，即进 程创建工作尚未完成，进程不能被调度执行，其所处程创建工作尚未完成，进程不能被调度执行，其所处 的状态就是创建状态的状态就是创建状态。 29 终止状态终止状态 终止一个进程一般包括两个步骤：终止一个进程一般包括两个步骤： 当一个进程到达了自然结束点，或是出现了无法克当一个进程到达了自然结束点，或是出现了无法克 服的错误，或是被操作系统所终结，或是被其他有终止服的错误，或是被操作系统所终结，或是被其他有终止 权的进程所终结，它将进入

29、终止状态。权的进程所终结，它将进入终止状态。 进入终止状态的进程以后不能执行，但在操作系统中进入终止状态的进程以后不能执行，但在操作系统中 依然保留一个记录，其中保存状态码和一些计时统计数依然保留一个记录，其中保存状态码和一些计时统计数 据，供其他进程收集。一旦其他进程完成了对终止状态据，供其他进程收集。一旦其他进程完成了对终止状态 进程的信息提取之后，操作系统将删除该进程。进程的信息提取之后，操作系统将删除该进程。 1) 1) 回收资源回收资源 2 2）删除）删除PCBPCB 30 终止状态终止状态 图2-2 具有创建、终止和挂起状态的进程状态图 31 2.22.2 进程控制进程控制 v进程

30、控制是进程管理中最基本的功能。进程控制是进程管理中最基本的功能。 v进程控制包括：进程控制包括： 创建进程创建进程 终止进程终止进程 进程状态转换进程状态转换 v进程控制是由进程控制是由OS的内核完成的。的内核完成的。 32 2.2.1 进程的创建进程的创建 1引起创建进程的事件引起创建进程的事件 用户登录用户登录 作业调度作业调度 提供服务提供服务 当用户进程提出某种请求当用户进程提出某种请求 后，系统将专门创建一个后，系统将专门创建一个 进程来提供用户所需的服进程来提供用户所需的服 务。如，文件打印。务。如，文件打印。 上述三种情况，都是由系统内核上述三种情况，都是由系统内核 为它创建一个

31、新进程。为它创建一个新进程。 应用请求：应用请求： 是基于应用进程的需求，由应用进是基于应用进程的需求，由应用进 程自己创建一个新进程，以便新进程自己创建一个新进程，以便新进 程以并发运行方式完成特定任务。程以并发运行方式完成特定任务。 33 2.2.1 进程的创建进程的创建 DEFGH BC IJKLM A 图 2-4 进程树 34 2进程的创建进程的创建 调用进程创建原语调用进程创建原语Create（），按下述步骤创建一个进程：（），按下述步骤创建一个进程： （1）申请空白）申请空白PCB； （2）为新进程分配资源。主要是内存空间。）为新进程分配资源。主要是内存空间。 （3）初始化）初始化

32、PCB。包括：。包括： 初始化标识信息初始化标识信息 初始化处理机状态信息：初始化处理机状态信息： 程序计数器，堆栈指针等程序计数器，堆栈指针等 进程状态进程状态就绪或静止就绪或静止 就绪、优先级等。就绪、优先级等。 初始化处理机控制信息：初始化处理机控制信息： （4）将新进程插入就绪队列）将新进程插入就绪队列。 35 1引起进程终止的事件引起进程终止的事件 正常结束正常结束 外界干预外界干预 l越界错误越界错误 l保护错保护错试图访问不允许访问的资试图访问不允许访问的资 源或文件，或者以不适当方式访问源或文件，或者以不适当方式访问 l非法指令非法指令 l特权指令错特权指令错用户程序试图执行只

33、用户程序试图执行只 允许允许OS执行的指令执行的指令 l运行超时运行超时 l等待超时等待超时 l算术运算错算术运算错被被0除除 lI/O故障故障 操作员或操作系统干操作员或操作系统干 预（如发生死锁）预（如发生死锁） 父进程请求父进程请求 父进程终止父进程终止 2.2.2 进程的终止进程的终止 异常结束异常结束 常见的异常常见的异常 结束事件结束事件 36 2进程的终止过程进程的终止过程 OSOS调用终止原语，按下述过程终止进程：调用终止原语，按下述过程终止进程： (1)根据被终止进程的标识，从根据被终止进程的标识，从PCB集合中找除该进程的集合中找除该进程的 PCB，读出该进程状态。，读出该

34、进程状态。 (2)若被终止进程正处于执行状态，应立即终止其执行，并若被终止进程正处于执行状态，应立即终止其执行，并 置调度标志为真，用于指示该进程被终止后应重新进行置调度标志为真，用于指示该进程被终止后应重新进行 调度。若该进程还有子孙进程，应将其所有子孙进程终调度。若该进程还有子孙进程，应将其所有子孙进程终 止，以防止它们成为不可控进程。止，以防止它们成为不可控进程。 (3)将被终止进程的所有资源，或者归还给其父进程，或者将被终止进程的所有资源，或者归还给其父进程，或者 归还给系统。归还给系统。 (4)将被终止进程（它的将被终止进程（它的PCB）从所在队列中移出，等待其）从所在队列中移出，等

35、待其 他进程来搜索信息。他进程来搜索信息。 37 2.2.2 进程的阻塞和唤醒进程的阻塞和唤醒 1引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 请求系统服务请求系统服务 无新工作可做无新工作可做 当执行进程请求当执行进程请求OS服务时，由于服务时，由于 某种原因，某种原因，OS并不立即满足该进程并不立即满足该进程 的请求时，该进程只能转变为阻塞状的请求时，该进程只能转变为阻塞状 态来等待。态来等待。 如，进程请求打印机，如，进程请求打印机， 系统往往设置一些具有特定功能的系统系统往往设置一些具有特定功能的系统 进程，每当这种进程完成任务后，便把进程，每当这种进程完成任务后，便把 自己阻塞起

36、来以等待新任务到来。自己阻塞起来以等待新任务到来。 如，系统中发送数据的进程，如，系统中发送数据的进程， 启动某种操作启动某种操作 当进程启动某种操作后，如果该进程当进程启动某种操作后，如果该进程 必须在该操作完成后才能继续执行，必须在该操作完成后才能继续执行， 则必须先使该进程阻塞，以等待操作则必须先使该进程阻塞，以等待操作 完成。完成。 如，启动了某如，启动了某I/O设备，设备， 新数据尚未到达新数据尚未到达 对于相互合作的进程，如果其中对于相互合作的进程，如果其中 一个进程需要获得另一个（合作）一个进程需要获得另一个（合作） 进程提供的数据才能运行以对数进程提供的数据才能运行以对数 据进

37、行处理，则只要其所需数据据进行处理，则只要其所需数据 尚未到达，该进程只有阻塞（等尚未到达，该进程只有阻塞（等 待）。待）。如，如， 38 2进程阻塞过程进程阻塞过程 调用阻塞原语调用阻塞原语block把自己阻塞。（主动行为）把自己阻塞。（主动行为） 阻塞（阻塞（blockblock）过程：）过程： u 立即停止执行；立即停止执行； u 把把PCBPCB中进程状态由中进程状态由“执行执行”改为改为“阻塞阻塞”； u 将将PCBPCB插入具有相同事件的阻塞队列；插入具有相同事件的阻塞队列； u 转进程调度程序，将处理机分配给某个就绪转进程调度程序，将处理机分配给某个就绪 进程，并进行进程切换进程

38、，并进行进程切换保留被阻塞进程保留被阻塞进程 的处理机状态（在的处理机状态（在PCBPCB中），再按新进程的中），再按新进程的 PCBPCB中处理机状态设置中处理机状态设置CPUCPU的环境。的环境。 39 3进程唤醒过程进程唤醒过程 调用唤醒原语调用唤醒原语wakeup( )( )，将等待事件的进程唤醒。，将等待事件的进程唤醒。 唤醒原语执行过程唤醒原语执行过程： 将被唤醒进程的将被唤醒进程的PCBPCB从阻塞队列移出；从阻塞队列移出； 将其将其PCBPCB中进程状态由中进程状态由“阻塞阻塞”改为改为“就绪就绪”； 将改将改PCBPCB插入到就绪队列中。插入到就绪队列中。 block（）和（

39、）和wakeup（）是成对的。（）是成对的。 40 1进程的挂起进程的挂起 当出现了引起进程挂起的事件时当出现了引起进程挂起的事件时( (用户进程请求将自己挂起，用户进程请求将自己挂起， 或父进程请求将子进程挂起或父进程请求将子进程挂起) )，系统将用挂起原语，系统将用挂起原语suspend( )suspend( ) 将指定进程或处于阻塞状态的进程挂起。将指定进程或处于阻塞状态的进程挂起。 挂起原语的执行过程：挂起原语的执行过程： 检查被挂起进程的状态：检查被挂起进程的状态： 若处于活动就绪或执行状态，则将其转若处于活动就绪或执行状态，则将其转 为静止就绪；为静止就绪； 若处于活动阻塞若处于活

40、动阻塞, ,则将其转为静止阻塞则将其转为静止阻塞 把该进程的把该进程的PCB复制到某指定内存区域复制到某指定内存区域 为方便用户或父进程考为方便用户或父进程考 查该进程的运行状态。查该进程的运行状态。 若该进程正在执行，则转进程调度程序重新调度。若该进程正在执行，则转进程调度程序重新调度。 2.2.4 进程的挂起和激活进程的挂起和激活 41 2进程的激活进程的激活 当发生激活进程的事件时当发生激活进程的事件时( (如父进程或用户请求激活指定进程，如父进程或用户请求激活指定进程， 而内存中已有足够空间时而内存中已有足够空间时) )，系统利用激活原语，系统利用激活原语active( )active

41、( )将将 指定进程激活。指定进程激活。 激活过程是：激活过程是： 将进程从外存调入内存；将进程从外存调入内存； 若是静止就绪，则改为活动就绪；若是静止就绪，则改为活动就绪； 若是静止阻塞，则改为活动阻塞。若是静止阻塞，则改为活动阻塞。 若采用的是抢占式调度策略，则应检查被激活就绪进程若采用的是抢占式调度策略，则应检查被激活就绪进程 的优先级，若其优先级比先行执行进程高，则应将处理机的优先级，若其优先级比先行执行进程高，则应将处理机 分配给被激活进程。分配给被激活进程。 检查该进程现行状态：检查该进程现行状态： 42 2.32.3 进程同步进程同步 n由于进程的异步性，尤其是它们竞争临界资源时

42、，由于进程的异步性，尤其是它们竞争临界资源时， 可能会给系统造成混乱。可能会给系统造成混乱。 n进程同步的主要任务，是使并发执行的进程之间能进程同步的主要任务，是使并发执行的进程之间能 有效地共享资源和相互合作，从而使程序的执行具有效地共享资源和相互合作，从而使程序的执行具 有可再现性。有可再现性。 2.3.1 进程同步的基本概念进程同步的基本概念 2.3.2 信号量机制信号量机制 2.3.3 信号量的应用信号量的应用 43 2.3.1 进程同步的基本概念进程同步的基本概念 1两种形式的制约关系两种形式的制约关系 （1）间接制约关系）间接制约关系 间接制约关系源于资源共享。间接制约关系源于资源

43、共享。 如，共享打印机。如，共享打印机。 进程互斥进程互斥 （2）直接制约关系）直接制约关系 源于进程间的合作。源于进程间的合作。 如，如， 进程同步进程同步 2临界资源临界资源 在一段时间内只允许一个进程访问的资在一段时间内只允许一个进程访问的资 源，即仅当一个进程访问完并释放该资源，即仅当一个进程访问完并释放该资 源后，才允许另一个进程访问的资源，源后，才允许另一个进程访问的资源， 称为临界资源或独占资源。称为临界资源或独占资源。 如，打印机、磁带机、共享变量、队列、如，打印机、磁带机、共享变量、队列、 44 生产者生产者- -消费者问题消费者问题 【例【例】生产者生产者- -消费者问题消

44、费者问题著名的进程同步问题著名的进程同步问题 共享变量：共享变量： 临界资源临界资源 循环缓冲区循环缓冲区 生产者投放一个产品后，输入指针生产者投放一个产品后，输入指针in加加1： in = ( in + 1 ) % n （n是缓冲区个数，整是缓冲区个数，整 型常量），型常量），in初值为初值为0； 消费者每取出一个产品，输出指针消费者每取出一个产品，输出指针out加加1： out = ( out + 1 ) % n，out初值为初值为0； 引入一个引入一个共享共享变量变量counter, ,初值为初值为0。 生产者投放一个产品，生产者投放一个产品，counter加加1， counter =

45、n时不能再投放产品时不能再投放产品 消费者每取一个产品，消费者每取一个产品，counter减减1， counter = 0时不能再取出产品时不能再取出产品 前面交通观察前面交通观察 站例子亦然。站例子亦然。 以下是软件临界资源的例子。以下是软件临界资源的例子。 45 process producer： while （condition） produce an item in nextp； while(counter=n) no-op；/no-op表示空操作表示空操作 bufferin = nextp； in = (in + 1)% n ； counter = counter + 1 ； 生产者

46、进程算法如下：生产者进程算法如下： 46 process consumer： struct item nextc ； while （condition） while （counter = 0）no-op ； nextc = bufferout ； out = （out + 1）% n ； counter = counter 1 ； consume the item in nextc ； 消费者进程算法如下：消费者进程算法如下： 47 上面的生产者程序和消费者程序，在顺序执行时其上面的生产者程序和消费者程序，在顺序执行时其 结果是正确的。但若并发执行时，可能会出现差错，结果是正确的。但若并发执行

47、时，可能会出现差错， 问题在于这两个进程共享变量问题在于这两个进程共享变量counter。生产者做。生产者做 counter=counter+1操作，消费者做操作，消费者做counter= counter-1操作，这两个操作在机器语言实现时，常操作，这两个操作在机器语言实现时，常 可用下面的形式描述：可用下面的形式描述： 生产者执行的操作：生产者执行的操作： register1 = counter ； register1 = register1 + 1; counter = register1； 消费者执行的操作：消费者执行的操作： register2 = counter ； register

48、2 = register2 - 1 ； counter = register2； 48 假设某一时刻假设某一时刻counter的值为的值为5，生产者和消费者同时对，生产者和消费者同时对counter 操作，按下述顺序执行：操作，按下述顺序执行： register1 = counter; (生产者取得生产者取得counter的当前值为的当前值为5) register1 = register1 + 1; (生产者将该值增生产者将该值增1变为变为6) register2 = counter; (消费者取得消费者取得counter的当前值为的当前值为5) register2 = register2 1

49、; (消费者将该值减消费者将该值减1变为变为4) counter = register2; (消费者保存消费者保存counter的新值的新值4) counter = register1; (生产者保存生产者保存counter的新值的新值6) 最终最终counter的值为的值为6，正确的值应是，正确的值应是5，出现了差错。，出现了差错。 学生考虑学生考虑：什么情况会出现什么情况会出现counter最终值为最终值为4的情况。的情况。 解决此问题的关键，是应将变量解决此问题的关键，是应将变量counter作为临界资作为临界资 源处理，亦即让生产者进程和消费者进程互斥地访源处理，亦即让生产者进程和消费

50、者进程互斥地访 问变量问变量counter。 49 2.3.1 进程同步的基本概念进程同步的基本概念 3临界区（临界区（critical section） 每个进程中访问临界资源的那段代码称为临界区。每个进程中访问临界资源的那段代码称为临界区。 不论是硬件临界不论是硬件临界 资源，还是软件资源，还是软件 临界资源，多个临界资源，多个 进程必须互斥地进程必须互斥地 对它们访问。对它们访问。 显然，若能保证诸进程显然，若能保证诸进程互斥互斥地进入自己的临界区，便可实现地进入自己的临界区，便可实现 诸进程对临界区的互斥访问。为此，每个进程在进入临界区诸进程对临界区的互斥访问。为此，每个进程在进入临界

51、区 之前，应先对欲访问的临界资源进行检查，看是否正被访问，之前，应先对欲访问的临界资源进行检查，看是否正被访问， 如果此刻该资源未被访问，便可进入临界区对该临界资源进如果此刻该资源未被访问，便可进入临界区对该临界资源进 行访问，并设置它正被访问的标志；如果此刻它正被访问，行访问，并设置它正被访问的标志；如果此刻它正被访问， 则本进程不能进入临界区。则本进程不能进入临界区。 定义：定义： 进程互斥的定义：进程互斥的定义：进程互斥进程互斥不允许两个或两个以上进不允许两个或两个以上进 程同时访问同一个临界资源。程同时访问同一个临界资源。 进程互斥进程互斥不允许两个或两个以上进不允许两个或两个以上进

52、程同时进入程同时进入相关临界区相关临界区。 50 u 因此必须在临界区前增加一段用于上述检查的代因此必须在临界区前增加一段用于上述检查的代 码，把这段代码称为码，把这段代码称为进入区进入区(entry section) u 相应地，在临界区后面也要加上一段称为相应地，在临界区后面也要加上一段称为退出区退出区 (exit section)的代码，用于将临界区正被访问的的代码，用于将临界区正被访问的 标志恢复为未被访问的标志。标志恢复为未被访问的标志。 repeat 非临界区非临界区 进入区进入区 临界区临界区 退出区退出区 非临界区非临界区 until false 一般结构一般结构 “ 进 入

53、区进 入 区 ” 和和 “退出区退出区”的的 不同构成方法，不同构成方法， 形成了各种不形成了各种不 同的同的同步机制同步机制。 51 4同步机制应遵循的原则同步机制应遵循的原则 为了实现各进程互斥地进入自己的临界区，一为了实现各进程互斥地进入自己的临界区，一 般是在系统中设置专门的同步机制来协调各进程般是在系统中设置专门的同步机制来协调各进程 间的运行。间的运行。 我们把异步环境下的一组并发进程因直接制我们把异步环境下的一组并发进程因直接制 约而互相发送消息、进行互相合作、互相等待，约而互相发送消息、进行互相合作、互相等待， 使得各进程按一定的速度执行的过程称为进程使得各进程按一定的速度执行

54、的过程称为进程 间的同步。具有同步关系的一组并发进程称为间的同步。具有同步关系的一组并发进程称为 合作进程，合作进程间互相发送的信号称为消合作进程，合作进程间互相发送的信号称为消 息或事件。息或事件。 52 4同步机制应遵循的原则同步机制应遵循的原则 所有同步机制都应遵循如下四条准则：所有同步机制都应遵循如下四条准则： 空闲让进空闲让进 当无进程处于临界区时，表明临界资源处当无进程处于临界区时，表明临界资源处 于空闲状态，应允许一个请求进入临界区于空闲状态，应允许一个请求进入临界区 的进程立即进入自己的临界区，以便有效的进程立即进入自己的临界区，以便有效 地利用临界资源。地利用临界资源。 空闲

55、让进、忙则等待、有限等待、让权等待。空闲让进、忙则等待、有限等待、让权等待。 53 有限等待有限等待 让权等待让权等待 对要求访问临界资源的进程，应保证在有对要求访问临界资源的进程，应保证在有 限的时间内能进入自己的临界区，以免陷限的时间内能进入自己的临界区，以免陷 入入“死锁死锁”状态。状态。不死等不死等。 不互相阻塞不互相阻塞。 当进程不能进入自己的临界区时，应立即当进程不能进入自己的临界区时，应立即 释放处理机，以免进程陷入释放处理机，以免进程陷入“忙等忙等”。 不忙碌等待不忙碌等待。 忙则等待忙则等待 当已有进程进入临界区时，表明临界资源当已有进程进入临界区时，表明临界资源 正在被访问

56、，因而其他试图进入临界区的正在被访问，因而其他试图进入临界区的 进程必须等待，以保证对临界资源的进程必须等待，以保证对临界资源的互斥互斥 访问访问。 54 2.3.2 信号量机制信号量机制 信号量信号量(Semaphores)机制是一种卓有成效的进程同机制是一种卓有成效的进程同 步工具。信号量机制已被广泛应用于单处理机和多步工具。信号量机制已被广泛应用于单处理机和多 处理机系统以及计算机网络中。处理机系统以及计算机网络中。 信号量机制的发展：信号量机制的发展： 整型信号量整型信号量 记录型信号量记录型信号量 AND型信号量型信号量 信号量集信号量集 ( (重点介绍重点介绍) ) 55 1、整型

57、信号量、整型信号量 最初由最初由Dijkstra把整型信号量定义为一个整型量，把整型信号量定义为一个整型量， 除初始化外，仅能通过两个标准的原子操作除初始化外，仅能通过两个标准的原子操作 (Atomic Operation) wait(S)和和signal(S)来访问。来访问。 这两个操作一直被分别称为这两个操作一直被分别称为P、V操作。操作。 wait和和 signal操作可描述为：操作可描述为： wait(S): while S0 do no-op S:=S-1; signal(S): S:=S+1; 56 1、整型信号量、整型信号量 最初由最初由Dijkstra把整型信号量定义为一个整型

58、量，把整型信号量定义为一个整型量， 除初始化外，仅能通过两个标准的原子操作除初始化外，仅能通过两个标准的原子操作 (Atomic Operation) wait(S)和和signal(S)来访问。来访问。 这两个操作一直被分别称为这两个操作一直被分别称为P、V操作。操作。 wait和和 signal操作可描述为：操作可描述为： wait(S): while S0 do no-op S:=S-1; signal(S): S:=S+1; 57 process producer： while （condition） produce an item in nextp； while(counter=n)

59、 no-op；/no-op表示空操作表示空操作 bufferin = nextp； in = (in + 1)% n ； wait(s); counter = counter + 1 ； signal(s); 生产者进程算法如下生产者进程算法如下(加入整型信号量）：加入整型信号量）： 58 process consumer： struct item nextc ； while （condition） while （counter = 0）no-op ； nextc = bufferout ； out = （out + 1）% n ； wait(s); counter = counter 1 ；

60、 signal(s); consume the item in nextc ； 消费者进程算法如下（加入整型信号量）：消费者进程算法如下（加入整型信号量）： 59 1、整型信号量、整型信号量 最初由最初由Dijkstra把整型信号量定义为一个整型量，把整型信号量定义为一个整型量， 除初始化外，仅能通过两个标准的原子操作除初始化外，仅能通过两个标准的原子操作 (Atomic Operation) wait(S)和和signal(S)来访问。来访问。 这两个操作一直被分别称为这两个操作一直被分别称为P、V操作。操作。 wait和和 signal操作可描述为：操作可描述为： wait(S): whi