第二章 进程管理

1、2 2.1 前趋图和程序执行前趋图和程序执行 2.2 进程描述进程描述 2.3 进程控制进程控制 2.4 进程同步进程同步 2.5 经典的进程同步问题经典的进程同步问题 2.6 进程通信进程通信 2.7 线程线程(Threads)的基本概念的基本概念 2.8 线程的实现线程的实现32.1 前趋图和程序执行前趋图和程序执行1.前趋图前趋图2.程序的顺序执行程序的顺序执行3.程序的并发执行程序的并发执行42.1.1 前趋图前趋图前趋图是一个前趋图是一个有向无循环图有向无循环图，记为，记为DAG（Directed Acyclic Graph），用于描述进程之），用于描述进程之间执行的前后关系。间执行

2、的前后关系。图中的每个结点可用于描述一个程序段或进程，图中的每个结点可用于描述一个程序段或进程，乃至一个语句；结点间的有向边乃至一个语句；结点间的有向边则用于则用于表示两个结点之间存在的偏序或前趋关系。表示两个结点之间存在的偏序或前趋关系。52.1.1 前趋图前趋图前趋关系的形式化定义：前趋关系的形式化定义：=（Pi，Pj）Pi must complete before Pj may start,如果（如果（ Pi，Pj ） ，可写成，可写成 Pi Pj，称为，称为Pi是是Pj的直接前趋，而称的直接前趋，而称Pj是是Pi的直的直接后继。接后继。 定义理解：定义理解：n（ Pi，Pj ），一对结

3、点），一对结点nPi must complete before Pj may start，结点的约束，结点的约束n用一个符合约束条件的结点对集合来定义一个关系用一个符合约束条件的结点对集合来定义一个关系6前趋图的表示方法前趋图的表示方法符号方式符号方式1. 使用关系符号使用关系符号2. 使用集合符号使用集合符号 , ( )图形方式图形方式n如右图所示的有向图如右图所示的有向图7例题：假设某个程序段包含如下例题：假设某个程序段包含如下 语句语句 ，画出它前趋图。，画出它前趋图。 int a,b,c,d,e,f; int t1,t2,t3,t4,t5; s1: t1=a+b; s2: t2=c+d

4、; s3: t3=e/f; s4: t4=t1*t2; s5: t5=t4-t3;s1s2s3s4s5练习练习8程序的两种执行方式程序的两种执行方式程序的两种执行方式程序的两种执行方式n顺序执行顺序执行w未配置未配置OS的系统，程序必须顺序执行的系统，程序必须顺序执行w即，一个程序执行完后，另一个程序才能执行即，一个程序执行完后，另一个程序才能执行n并发执行并发执行w多道程序环境下，允许程序并发执行多道程序环境下，允许程序并发执行w程序并发执行时的特征，导致了进程概念的引入程序并发执行时的特征，导致了进程概念的引入92.1.1 程序的顺序执行程序的顺序执行首先在程序段层次讨论：一个程序可以被分

5、成若干段，各程序段必须按照某种先后次序执行，前一操作(程序段)完成后，后继操作才能开始。这种方式就是程序的顺序执行。10例：讨论例：讨论单道单道系统的工作情况系统的工作情况单道批处理系统中，用户作业的处理，通常分单道批处理系统中，用户作业的处理，通常分为如下三段：为如下三段：首先首先输入输入用户的程序和数据用户的程序和数据然后进行然后进行计算计算最后最后打印打印计算结果计算结果那么各个作业中各程序段的执行顺序可表示为：那么各个作业中各程序段的执行顺序可表示为：I-输入输入 C-计算计算 P-打印打印11语句级的顺序执行语句级的顺序执行S1S2S3S1: a :=x+y;S2: b :=a-5;

6、S3: c :=b+1;一个包含一个包含3条语句的程序段：条语句的程序段：由变量由变量a, b引起的依赖关系，使得：引起的依赖关系，使得：S1必须先于必须先于S2执行，执行，S2必须先于必须先于S3执行。执行。前趋图：前趋图：12程序顺序执行时的特征程序顺序执行时的特征1.顺序性顺序性n处理机严格按照程序规定的顺序执行，即每个操作必须在下处理机严格按照程序规定的顺序执行，即每个操作必须在下一个操作开始之前结束。一个操作开始之前结束。2.封闭性封闭性n程序一旦开始执行，其计算结果不受外界的影响，当程序的程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身

7、确定，即只初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。有本程序才能改变它。3.可再现性可再现性n程序执行的结果与初始条件有关，而与执行时间（执行速度）程序执行的结果与初始条件有关，而与执行时间（执行速度）无关。即只要程序的初始条件相同，它的执行结果是相同的，无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。不论它在什么时间执行，也不管计算机的运行速度。优缺点优缺点：方便程序员检测和校正程序的错误，但计算：方便程序员检测和校正程序的错误，但计算机系统效率不高。机系统效率不高。132.1.3 程序的并发执行程序的并发执行

8、例：讨论在多道批处理系统中，对大量作业的处理在系统中有n个作业，每个作业都有三个处理步骤，输入、计算、输出，即Ii, Ci, Pi (i=1,2,3,.,n)。对作业1、作业2、，作业n的处理： 作业1： I1 C1 P1 作业2： I2 C2 P2 作业n： In Cn Pn14批量作业的执行次序批量作业的执行次序 152.1.3 程序的并发执行程序的并发执行当系统中存在多道作业，有些些程序段必须顺当系统中存在多道作业，有些些程序段必须顺序执行，有些程序段可以并发执行。序执行，有些程序段可以并发执行。例如，例如，I1、C1、P1的执行必须严格按照的执行必须严格按照I1，C1，P1的顺序，的顺

9、序， I2、C2、P2的执行也必须严格按照的执行也必须严格按照I2，C2，P2的顺序，的顺序，而而C1与与I2， P1与与C2 、I3是是可以同时执行的。可以同时执行的。16程序并发执行（定义）程序并发执行（定义）程序并发执行：若干个程序段同时在系统中运行，这些程序的执行在时间上是重叠的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重叠是很小的，也称这几个程序段是并发执行的。17一道考研题一道考研题兄弟俩共用一个账户，每次限存或取兄弟俩共用一个账户，每次限存或取10元，存元，存钱与取钱的进程如下所示，由于兄弟俩可能同钱与取钱的进程如下所示，由于兄弟俩可能同时存钱和取钱，因此两

10、个进程是并发的。若哥时存钱和取钱，因此两个进程是并发的。若哥哥先存了两次钱，但在哥哥第三次存钱时，弟哥先存了两次钱，但在哥哥第三次存钱时，弟弟在取钱，请问最后的帐号上弟在取钱，请问最后的帐号上amount可能有多可能有多少钱？少钱？18答案：amount=20,30,10s1s2s3s4s5s619 程序的并发执行的特征程序的并发执行的特征1.1.间断性间断性程序在并发执行时，由于共享资源，或者需要相互合作，致使相程序在并发执行时，由于共享资源，或者需要相互合作，致使相互间产生了制约关系，呈互间产生了制约关系，呈“走走停停走走停停”的间断执行特征。的间断执行特征。2.2.失去封闭性失去封闭性程

11、序并发执行时的系统环境（主要指各程序所共享的系统资源的程序并发执行时的系统环境（主要指各程序所共享的系统资源的状态）是由多个程序来改变的，因而失去了封闭性。状态）是由多个程序来改变的，因而失去了封闭性。3.3.不可再现性不可再现性程序在并发执行时的结果与其执行速度等有关，从而不可再现。程序在并发执行时的结果与其执行速度等有关，从而不可再现。u优缺点：优缺点：充分发挥硬件的并行性，消除处理器和充分发挥硬件的并行性，消除处理器和I/O 设备的互等设备的互等现象，提高了系统吞吐量。同时，也使程序的运行环境变得复杂，现象，提高了系统吞吐量。同时，也使程序的运行环境变得复杂，调试与维护难度增加。调试与维

12、护难度增加。202.2.1 进程的描述进程的描述1.进程的定义和特征2.进程的基本状态及转换3.挂起操作和进程状态的转换4.进程管理中的数据结构212.2.1 进程的定义进程的定义进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。其他经典定义：n进程是程序的一次执行。n进程是一个程序及其数据在处理机上顺序执行时所发生的活动。n进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。22进程的相关概念进程的相关概念进程控制块(PCB: Process Control Block)n一个数据结构，用来描述进程的基本情况和活动过程，为操作系统管理和控制进程所必

13、需。进程实体n由程序段、数据段、PCB三部分构成n通常所说的进程实际上是指进程实体创建进程，实质上是创建进程实体中的PCB撤销进程，实质上是撤销进程的PCB23进程的特征进程的特征动态性n进程的实质：进程实体的一次执行过程n由创建而产生，由调度而执行，由撤销而消亡并发性n多个进程实体同存于内存中n能在同一段时间内同时运行独立性n能够独立运行、独立分配资源和独立接受调度的基本单位异步性n进程以各自独立的、不可预知的速度向前推进。24进程与程序的关系程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上

14、的一次执行过程，它是一个动态的概念。念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念。程序可以作为一种软件资料长期保存在某种介质上，而进程是有一定生程序可以作为一种软件资料长期保存在某种介质上，而进程是有一定生命期的，进程被创建后存在于内存中，进程消亡后生命期结束，不再存命期的，进程被创建后存在于内存中，进程消亡后生命期结束，不再存在。在。程序的每次运行都将创建新的进程，而进程一旦消亡，就无法再被执行。程序的每次运行都将创建新的进程，而进程一旦消亡，就无法再被执行。进程更能真实地描述并发，而程序不能进程更能真实地描述并发，而程序不能( (没有没有PCB)PCB)。进程能够独立运行、

15、独立分配资源和独立接受调度的基本单位，程序进程能够独立运行、独立分配资源和独立接受调度的基本单位，程序（没有（没有PCBPCB）不能作为独立的单位运行。）不能作为独立的单位运行。252.2.2 进程的基本状态进程的基本状态就绪就绪(Ready)状态状态执行执行(Running)状态状态阻塞阻塞(Blocked)状态状态26就绪就绪(Ready)就绪状态就绪状态n是指进程已处于准备好运行的状态，已经获得是指进程已处于准备好运行的状态，已经获得除除CPU以外以外的的所有必要资源所有必要资源，因其，因其CPU正被其他进程正被其他进程占用而无法执行，一旦获得占用而无法执行，一旦获得CPU, 可以立即执

16、行。可以立即执行。就绪进程就绪进程n处于就绪状态的进程称为就绪进程。处于就绪状态的进程称为就绪进程。就绪队列就绪队列n所有的就绪进程排成一个队列，等待获得所有的就绪进程排成一个队列，等待获得CPU。n队列的排序与调度策略有关。队列的排序与调度策略有关。27执行执行(Running)执行状态执行状态n是指当前进程已经是指当前进程已经获得获得CPU，其程序，其程序正在执行正在执行的的状态。状态。当前进程当前进程n正在执行的进程称为当前进程。正在执行的进程称为当前进程。单处理机系统单处理机系统n任一时刻，只有一个进程处于执行状态任一时刻，只有一个进程处于执行状态多处理机系统多处理机系统n可有多个进程

17、同时处于执行状态可有多个进程同时处于执行状态28阻塞阻塞(Blocked)阻塞状态阻塞状态n也叫也叫等待等待状态，是指状态，是指原本正在执行原本正在执行的进程由于的进程由于发生发生某事件某事件（如（如I/O请求，等待其他进程发来的信号）请求，等待其他进程发来的信号）而暂时无法继续执行的状态。而暂时无法继续执行的状态。n也就是说，进程的执行受到也就是说，进程的执行受到阻塞阻塞。阻塞进程阻塞进程n处于阻塞状态的进程称为阻塞进程。处于阻塞状态的进程称为阻塞进程。n阻塞进程尚阻塞进程尚不具备运行条件不具备运行条件，即使，即使CPU空闲它也无空闲它也无法使用。法使用。阻塞队列阻塞队列n进程在阻塞队列中等

18、待进程在阻塞队列中等待n按阻塞原因排成不同队列按阻塞原因排成不同队列(大系统常用大系统常用)29三种基本状态的转换三种基本状态的转换30引起进程状态转换的具体原因引起进程状态转换的具体原因就绪就绪 - 执行执行n调度调度程序选择一个新的进程执行程序选择一个新的进程执行执行执行 - 就绪就绪n当前进程当前进程用完了时间片用完了时间片；n当前进程被中断，被一个当前进程被中断，被一个更高优先级更高优先级的的就绪进程就绪进程抢占抢占CPU执行执行 - 阻塞阻塞(等待等待)n发生某事件，导致等待发生某事件，导致等待：如：如OS尚未完成进程请求的服务；进程尚未完成进程请求的服务；进程向向OS申请缓冲空间；

19、对某资源的访问尚不能进行；初始化申请缓冲空间；对某资源的访问尚不能进行；初始化I/O 且必须等待结果；等待某个进程提供输入且必须等待结果；等待某个进程提供输入, 阻塞阻塞(等待等待) - 就绪就绪n当所等待的事件发生当所等待的事件发生, 欠缺的运行条件被满足欠缺的运行条件被满足：如，得到所请求：如，得到所请求的资源；的资源；I/O操作完成；操作完成；OS完成进程请求的服务；得到申请的完成进程请求的服务；得到申请的缓冲区缓冲区; 等待的数据已经到达等待的数据已经到达; 31J考考你：考考你： 1 1如果某单处理系统中有如果某单处理系统中有N N个进程，运行的进程最多几个，个进程，运行的进程最多几

20、个，最少几个；就绪进程最多几个最少几个；等待进程最多几最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？个，最少几个？ 2. 2. 有没有这样的状态转换，为什么？有没有这样的状态转换，为什么？ （1 1） 等待等待运行；运行； （2 2） 就绪就绪等待等待323 3、在操作系统中引入、在操作系统中引入“进程进程”概念的主要目的是（概念的主要目的是（ ）。）。 A A改善用户编程环境改善用户编程环境 B. B. 描述程序动态执行过程的性质描述程序动态执行过程的性质 C. C. 使程序与计算过程一一对应使程序与计算过程一一对应 D. D. 提高程序的运行速度提高程序的运行速度4 4、

21、某进程在运行过程中需要等待从磁盘上读入数据，此时该进程的状、某进程在运行过程中需要等待从磁盘上读入数据，此时该进程的状态将（态将（ ）。）。 A.从就绪变为运行从就绪变为运行 B.从运行变为就绪从运行变为就绪 .从运行变为阻塞从运行变为阻塞 D.从阻塞变为就绪从阻塞变为就绪 33创建状态与终止状态创建状态与终止状态实际系统中，因管理所需而引入的状态。进程创建步骤：1.创建PCB，填写管理信息2.转入就绪状态，插入就绪队列创建状态n分配了PCB，填写了进程标识n主存及其他资源尚未分配34创建状态与终止状态创建状态与终止状态进程终止步骤：1.OS善后2.清零PCB并返还系统终止状态n进程到达自然结

22、束点/出现严重错误/被OS或其他进程终结，进入终止状态。n不能再执行，但在OS中保留一个记录，供其他进程收集信息用。n其他进程提取完信息后，OS就删除这个进程。35n 进程五态模型及其转换进程五态模型及其转换运行态就绪态阻塞态调度时间片完出现等待事件等待事件结束创建态终止态362.2.3 挂起操作和进程状态的转换挂起操作和进程状态的转换1.挂起操作的引入2.引入挂起操作后的进程状态转换37挂起操作的引入挂起操作的引入终端用户请求n终端用户希望暂停自己的程序以便查看、修改父进程请求n父进程希望挂起子进程(考查、修改、协调)负荷调节的需要n系统负荷重时，挂起不重要的进程OS的需要n检查资源使用情况

23、或记账38带挂起的进程状态转换带挂起的进程状态转换活动就绪（Readya）-静止就绪（Readys）n处于Readys状态的进程不再接受调度n挂起原语：suspend活动阻塞（Blockeda）-静止阻塞(Blockeds)n此时，若进程等待的事件出现，状态变为静止就绪静止就绪-活动就绪n激活原语：active静止阻塞-活动阻塞图2-639具有创建、终止和挂起状态的进程状态转换具有创建、终止和挂起状态的进程状态转换挂起等待事件结束出现等待事件激活挂起时间片完调度运行态活动就绪态等待事件结束终止态新建态静止就绪态激活挂起静止阻塞态活动阻塞态提交提交402.2.4 进程管理中的数据结构进程管理中的

24、数据结构1.操作系统中用于管理控制的数据结构2.进程控制块PCB的作用3.进程控制块中的信息4.进程控制块的组织方式41操作系统中用于管理控制的数据结构操作系统中用于管理控制的数据结构四类数据结构：内存表、设备表、文件表、进程表内存内存设备设备文件文件进程进程内存表内存表设备表设备表文件表文件表进程进程1 1进程进程2 2进程进程n n进程进程1 1进程进程n n进程实体及其进程实体及其所有资源所有资源列表列表42进程表与进程控制块进程表与进程控制块为了管理和控制进程，操作系统维持着一个数据结构-进程表（Process table）。进程表即PCB的集合，一个表项即一个PCB，描述系统中的一个

25、进程的当前情况，以及管理进程运行所需的全部信息，包括：n包括程序计数器，内存分配状况，打开文件状况，调度信息，计费信息 .43进程控制块的作用进程控制块的作用1.作为独立运行基本单位的标志系统通过PCB感知进程的存在PCB是进程存在的唯一标志2.实现间断性运行方式保存被中断进程的CPU运行现场3.提供进程管理所需要的信息程序/数据保存位置资源清单4.提供进程调度所需要的信息5.实现与其他进程的同步和通信44进程控制块中的信息进程控制块中的信息1.进程标识符进程标识符(用于识别进程用于识别进程)n内部标识符：操作系统使用内部标识符：操作系统使用n外部标识符：用户使用外部标识符：用户使用2.处理机

26、状态处理机状态n即处理机上下文，主要包括处理机中各种寄存器即处理机上下文，主要包括处理机中各种寄存器的内容：的内容：w通用寄存器通用寄存器w指令计数器指令计数器(PC)w程序状态字程序状态字(PSW)w用户栈指针用户栈指针n进程切换时，这些信息用来使当前进程被上次中进程切换时，这些信息用来使当前进程被上次中断地方继续执行。断地方继续执行。45进程控制块的组织方式进程控制块的组织方式3.进程调度信息n进程状态n进程优先级n调度所需其他信息n事件(阻塞原因)4.进程控制信息n程序/数据的地址(内/外存首地址)n同步/通信机制(消息队列指针、信号量)n资源清单(需求、占用)n链接指针(队列中下一个P

27、CB)46进程控制块的组织方式进程控制块的组织方式1.线性方式所有进程组织在一张线性表中 实现简单，但查找时需扫描整张表2.链接方式相同状态进程的PCB链接成一个队列就绪队列、阻塞队列、空白队列3.索引方式按进程状态的不同，建立几张索引表索引表的表项：各进程PCB首址线性方式线性方式47链接方式链接方式48索引方式索引方式492.3 进程控制进程控制任务：对任务：对进程生命周期进程生命周期进行控制，即要负责进行控制，即要负责进程的进程的创建创建、撤消撤消以及实现进程的以及实现进程的状态转换状态转换等功能。等功能。1.1.操作系统内核操作系统内核2.2.进程的创建进程的创建3.3.进程的终止进程

28、的终止4.4.阻塞与唤醒阻塞与唤醒5.5.挂起与激活挂起与激活502.3.1 操作系统内核操作系统内核内核的概念内核的概念n现代操作系统多采用现代操作系统多采用分层设计分层设计，一般将，一般将OS中与硬件中与硬件密切相关的模块、常用的设备驱动程序、运行频率密切相关的模块、常用的设备驱动程序、运行频率较高的模块安排在较高的模块安排在紧靠硬件紧靠硬件的软件层次，的软件层次，常驻内存常驻内存，称为，称为OS内核内核。n作用：保护内核中的软件、提高作用：保护内核中的软件、提高OS的运行效率的运行效率处理机的执行状态处理机的执行状态(CPU的工作状态的工作状态)n系统态系统态(管态、核态管态、核态)w能

29、执行所有指令、访问所有存储空间能执行所有指令、访问所有存储空间n用户态用户态(目态目态)w仅能执行部分指令、访问部分存储空间仅能执行部分指令、访问部分存储空间51内核的功能内核的功能支撑功能n中断处理n时钟管理n原语操作资源管理功能n进程管理n存储器管理n设备管理52原语原语(Primitive)原语，是由若干条指令组成，用于完成一定功能的一原语，是由若干条指令组成，用于完成一定功能的一个过程。个过程。与一般过程的区别与一般过程的区别n是是原子操作原子操作(Atomic Operation)：w一个操作中的所有动作要么全做，要么全不做，是一个不可分隔一个操作中的所有动作要么全做，要么全不做，是

30、一个不可分隔带基本单位带基本单位n执行中不允许被中断执行中不允许被中断n在系统态下执行在系统态下执行n常驻内存常驻内存原语的主要特征：原子性，中断屏蔽性。原语的主要特征：原子性，中断屏蔽性。53进程图进程图描述进程的家族关系的有向图描述进程的家族关系的有向图n父进程、子进程、祖先父进程、子进程、祖先箭头表示进程之间创建与被创建的关系箭头表示进程之间创建与被创建的关系n如下图所示：如下图所示：A (父进程父进程)创建了创建了B(子进程子进程), B 创建了创建了E ABCDEF54OS对进程家族关系的管理对进程家族关系的管理资源共享资源共享n子进程可以子进程可以继承继承父进程所拥有的资源父进程所

31、拥有的资源进程撤销时的善后进程撤销时的善后n撤销子进程时，需撤销子进程时，需归还资源归还资源给父进程给父进程n撤销父进程时，需撤销父进程时，需撤销撤销其其所有子进程所有子进程PCB中需设置家族关系表项，记录：中需设置家族关系表项，记录：n父进程父进程n所有子进程所有子进程552.3.2 进程创建进程创建引起创建进程的事件：引起创建进程的事件：1.用户登录用户登录2.作业调度作业调度3.提供服务提供服务4.应用请求应用请求1、2、3类事件引起的，由内核创建进程类事件引起的，由内核创建进程第第4类事件引起的，由应用进程自己创建新进程类事件引起的，由应用进程自己创建新进程56进程创建的主要步骤进程创

32、建的主要步骤调用进程创建原语调用进程创建原语Create()创建进程，创建步创建进程，创建步骤如下：骤如下：1.申请申请空白空白PCB2.为新进程分配为新进程分配资源资源w内存、文件、内存、文件、I/O设备、设备、CPU时间、时间、3.初始化初始化PCB的内容的内容w标识、处理机状态、进程状态、优先级、标识、处理机状态、进程状态、优先级、4.将新进程将新进程插入就绪队列插入就绪队列57 2.3.3 进程的终止进程的终止 引起终止的事件：引起终止的事件：1.1.正常结束正常结束2.2.异常结束异常结束n运行期错误和故障迫使进程终止运行期错误和故障迫使进程终止3.3.外界干预外界干预n操作员、操作

33、员、OSOSn父进程请求终止子孙进程父进程请求终止子孙进程n父进程终止，其所有子孙进程也必须终止父进程终止，其所有子孙进程也必须终止58进程终止过程进程终止过程1.根据被终止进程的标识符，从根据被终止进程的标识符，从PCB集合中检索出该集合中检索出该PCB，读出进程状态；，读出进程状态；2.若进程在执行状态，终止其执行，置重新调度标志；若进程在执行状态，终止其执行，置重新调度标志；3.若该进程有子孙进程，终止其子孙进程，以防成为不若该进程有子孙进程，终止其子孙进程，以防成为不可控进程；可控进程；4.将该进程拥有的资源归还给父进程或操作系统；将该进程拥有的资源归还给父进程或操作系统；5.将被终止

34、进程将被终止进程(PCB)从所在队列从所在队列/链表中移出，等待其链表中移出，等待其他程序收集信息。他程序收集信息。592.3.4 进程的阻塞和唤醒进程的阻塞和唤醒引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件进程阻塞过程进程阻塞过程进程唤醒过程进程唤醒过程60引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件请求系统资源请求系统资源/服务服务等待某种操作完成等待某种操作完成新数据尚未到达新数据尚未到达等待新任务到达等待新任务到达61进程的阻塞进程的阻塞发现阻塞事件，进程就发现阻塞事件，进程就调用阻塞原语把自己调用阻塞原语把自己阻塞。阻塞。阻塞原语：阻塞原语： block( )阻塞过程阻塞过程

35、1.停止停止进程的进程的执行执行, 修改修改PCB的进程状态为的进程状态为“阻塞阻塞”,将其插入到相应的将其插入到相应的阻塞队列阻塞队列；2.转转调度调度程序，将处理机分配给程序，将处理机分配给另一个就绪进程另一个就绪进程。v注意：进程的注意：进程的阻塞是进程阻塞是进程自身自身的一种的一种主动主动行为行为62进程的唤醒进程的唤醒n当阻塞的进程所当阻塞的进程所等待的事件出现等待的事件出现时（如所需数据已到达，时（如所需数据已到达，或者等待的或者等待的I/O操作已经完成），则操作已经完成），则由另外的与阻塞进程由另外的与阻塞进程相关的进程相关的进程（如完成（如完成I/O操作的进程）操作的进程）调用

36、唤醒原语调用唤醒原语，将，将等待该事件的进程唤醒。等待该事件的进程唤醒。n注意：阻塞进程不能唤醒自己。注意：阻塞进程不能唤醒自己。n唤醒原语：唤醒原语： wakeup( )n进程唤醒步骤：进程唤醒步骤：1.从相应的从相应的阻塞队列阻塞队列中中移出移出进程；进程；2.修改进程修改进程PCB的有关信息，如的有关信息，如进程状态改为就绪态进程状态改为就绪态，并，并移入就移入就绪队列绪队列63 2.3.5 进程的挂起与激活进程的挂起与激活 挂起挂起n原语：原语：suspend( )n功能：使处于活动状态的进程变为静止状态。功能：使处于活动状态的进程变为静止状态。w活动就绪活动就绪静止就绪静止就绪w活动

37、阻塞活动阻塞静止阻塞静止阻塞n可挂起自身、挂起具有指定标识符的进程、将其进可挂起自身、挂起具有指定标识符的进程、将其进程及其全部或部分程及其全部或部分“子孙子孙”挂起。挂起。激活激活n原语：原语：active( )n功能：使处于静止状态的进程变为活动状态。功能：使处于静止状态的进程变为活动状态。64思考与练习：思考与练习：1.我们都学习了哪些进程控制原语？我们都学习了哪些进程控制原语？ 2.执行每一个进程控制原语，进程状态将发生什么变化？执行每一个进程控制原语，进程状态将发生什么变化？652.4 进程同步进程同步进程的进程的异步性异步性，和对，和对临界资源临界资源的争用，的争用，会给系统带来混

38、乱。会给系统带来混乱。进程同步的进程同步的主要任务：主要任务：n对多个相关进程在对多个相关进程在执行次序上执行次序上进行进行协协调调，以使并发执行的诸进程之间能，以使并发执行的诸进程之间能有有效效地地共享共享资源和相互资源和相互合作合作，从而使程，从而使程序的执行具有序的执行具有可再现性可再现性。66进程间的两种制约关系进程间的两种制约关系间接间接相互制约相互制约n源于源于资源共享资源共享，即对资源的，即对资源的竞争关系竞争关系，进程进程需要互斥地访问同一资源需要互斥地访问同一资源直接直接相互制约相互制约n源于源于进程合作进程合作，即，即协作关系协作关系，某些进程为完，某些进程为完成同一任务需

39、要分工协作成同一任务需要分工协作67临界资源与临界区临界资源与临界区临界资源临界资源(Critical Resource):只允许进程互斥地只允许进程互斥地访问的资源。访问的资源。n例如，打印机，共享变量，例如，打印机，共享变量，临界区临界区(Critical section)：进程：进程中访问中访问临界资源临界资源的的代码段代码段。若能保证各进程若能保证各进程互斥地进入自己的临界区互斥地进入自己的临界区，就，就可实现各进程可实现各进程对临界资源的互斥访问对临界资源的互斥访问。68访问临界资源的进程的访问临界资源的进程的4个组成部分：个组成部分：a. 进入区进入区：检查可否进入临界区；若可进入

40、，设：检查可否进入临界区；若可进入，设置它正被访问的标志，阻止其他进程。置它正被访问的标志，阻止其他进程。b. 临界区临界区：进程中访问临界资源的一段代码。：进程中访问临界资源的一段代码。 c. 退出区退出区：将访问标志清除。：将访问标志清除。d. 剩余区剩余区：代码中的其余部分。：代码中的其余部分。例，见例，见P50模拟代码模拟代码进入区退出区 临界区 剩余区访问临界资源的进程访问临界资源的进程69 同步机制应遵循的规则同步机制应遵循的规则1.空闲让进空闲让进n没有进程在临界区，表明临界资源空闲，应允许一个请求进没有进程在临界区，表明临界资源空闲，应允许一个请求进入临界区的进程立即进入临界区

41、，以保证资源的入临界区的进程立即进入临界区，以保证资源的有效利用有效利用。2.忙则等待忙则等待n已有进程进入临界区，表明临界资源正在被访问，其他请求已有进程进入临界区，表明临界资源正在被访问，其他请求进入临界区进程必须等待，以保证对临界资源的进入临界区进程必须等待，以保证对临界资源的互斥访问互斥访问。3.有限等待有限等待n一个进程不能无限地等待进入临界区，一个进程不能无限地等待进入临界区，避免避免“死等死等”。4.让权等待让权等待n进程若不能进入自己的临界区，应立即释放处理机，进程若不能进入自己的临界区，应立即释放处理机，避免避免“忙等忙等”。702.4.3 信号量机制信号量机制1.整型信号量

42、2.记录型信号量3.AND型信号量4.信号量集711.整型信号量整型信号量定义定义S为一个用于为一个用于表示资源数目表示资源数目的的整型量整型量，除初始化外，除初始化外，仅能通过两个标准的仅能通过两个标准的原子操作原子操作wait(S)和和signal(S)来访来访问。这两个操作也被称为问。这两个操作也被称为P、V操作。操作。 wait(S) while (Svalue-;if (S-value list); signal (semaphore *S) S-value+;if (S-value list); 注意：注意：S.value的初值的初值表示系统中表示系统中某类资源的数目某类资源的数目

43、，又称，又称资资源信号量源信号量。如果初值为如果初值为1，表示只允许一个进程访问临界资源，信号量，表示只允许一个进程访问临界资源，信号量即转化为即转化为互斥信号量互斥信号量，用于进程互斥。，用于进程互斥。743. AND型信号量型信号量(1) 问题的引入问题的引入假定有两个进程假定有两个进程A和和B，它们都要求访问共享数据，它们都要求访问共享数据D和和E。当然，共享数据都应作为临界资源。为此，可为这。当然，共享数据都应作为临界资源。为此，可为这两个数据分别设置用于互斥的信号量两个数据分别设置用于互斥的信号量Dmutex和和Emutex，并令它们的初值都是并令它们的初值都是1。相应地，在两个进程

44、中都要包含。相应地，在两个进程中都要包含两个对两个对Dmutex和和Emutex的操作，即的操作，即: process A: wait (Dmutex); wait (Emutex); process B:wait(Emutex);wait(Dmutex);75若进程若进程A和和B按下述次序交替执行按下述次序交替执行wait操作：操作： process A: wait(Dmutex);于是于是Dmutex=0 process B: wait(Emutex);于是于是Emutex=0 process A: wait(Emutex);于是于是Emutex=-1,A阻塞阻塞 process B: w

45、ait(Dmutex);于是于是Dmutex=-1,B阻塞阻塞A、B各自持有对方各自持有对方需要的资源，又等待需要的资源，又等待对方释放自己需要的对方释放自己需要的资源，都无法继续执资源，都无法继续执行，进入死锁状态！行，进入死锁状态！本例出现死锁的原因：主要在于本例出现死锁的原因：主要在于进程运行时需要多个资源进程运行时需要多个资源，在为在为每个进程分配每个进程分配所需的所需的全部资源全部资源时，时，不能保证原子操作不能保证原子操作，从而导致从而导致进程之间相互等待对方释放所占资源进程之间相互等待对方释放所占资源的的死锁死锁状态。状态。为了解决进程为了解决进程同时需要多种资源同时需要多种资源

46、且且每种资源要占用一段时间每种资源要占用一段时间的问题，人们提出了的问题，人们提出了ANDAND型信号量同步机制。型信号量同步机制。763. AND型信号量型信号量(2) AND型信号量的基本思想型信号量的基本思想: 将进程在整个运行过程中需要的所有资源，一次性将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放全部地分配给进程，待进程使用完后再一起释放。只要。只要尚有一个资源未能分配给进程，其他所有可能为之分配尚有一个资源未能分配给进程，其他所有可能为之分配的资源，也不分配给它。亦即，的资源，也不分配给它。亦即，对若干个临界资源的分对若干个临界资源的分配，采

47、取了原子操作方式配，采取了原子操作方式：要么全部分配给进程，要么要么全部分配给进程，要么一个也不分配。一个也不分配。 773. AND型信号量型信号量AND型信号量型信号量wait原语为原语为Swait, 定义如下：定义如下：Swait (S1, S2, , Sn) if (Si =1 & & Sn = 1) /进程所需各项资源都能满足时进程所需各项资源都能满足时 for (i = 1; i = n; +i) Si-; else /某些资源不够时的处理某些资源不够时的处理 把进程放入把进程放入第一个小于第一个小于1的信号量的信号量Sj的的等待队列等待队列Sj.queue，并将程序计数器指向，并

48、将程序计数器指向Swait的开始处；的开始处； 783. AND型信号量型信号量AND型信号量集型信号量集signal原语为原语为Ssignal, 其定义如下：其定义如下：Ssignal (S1, S2, , Sn) for (i = 1; i = n; +i) Si=Si+；/释放占用的资源；释放占用的资源； 把等待把等待Si的所有进程从的所有进程从等待队列等待队列移至移至就绪队列就绪队列； 793. AND型信号量型信号量引入引入AND信号量后，上面的例子就可以简单改写为：信号量后，上面的例子就可以简单改写为：process A: process B:Swait (Dmutex, Emut

49、ex);Swait (Emutex, Dmetux); Ssignal (Dmutex, Emutex); Ssignal (Emutex, Dmutex);这样也就不会出现死锁问题。这样也就不会出现死锁问题。804.信号量集信号量集信号量集机制的适用范围更广，不仅能处理前述信号信号量集机制的适用范围更广，不仅能处理前述信号量机制能处理的问题，还能处理以下情况：量机制能处理的问题，还能处理以下情况：n需要需要一次性分配多个同类资源一次性分配多个同类资源时时n当资源数量当资源数量低于低于某一某一下限下限值时，就值时，就不不予以予以分配分配对对AND型型信号量加以信号量加以扩充扩充，即得到更为一般

50、化的信号，即得到更为一般化的信号量集机制：量集机制：Swait (S1, t1, d1, , Sn, tn, dn);Ssignal (S1, d1, , Sn, dn);/ti：分配下限值，如果：分配下限值，如果Siti, 不予分配不予分配/di：资源需求值，分配时：资源需求值，分配时Si-=di; 释放时释放时Si +=di;812.4.4 信号量的应用信号量的应用应用原理：应用原理： 两个或多个进程可以利用两个或多个进程可以利用彼此间收发的简单的信号彼此间收发的简单的信号来实来实现现“正确的正确的”并发执行，一个进程在并发执行，一个进程在收到一个指定信号收到一个指定信号前前，会，会被迫被

51、迫在一个确定的或者需要的地方在一个确定的或者需要的地方停下来停下来，从而，从而保持保持同步同步或或互斥互斥。822.4.4 信号量的应用信号量的应用1、利用信号量实现进程、利用信号量实现进程互斥互斥为了使进程能互斥地访问某临界资源，只需为该资源设置为了使进程能互斥地访问某临界资源，只需为该资源设置一一互斥信号量互斥信号量mutex，初值设为，初值设为1。值为。值为1表示临界资源未表示临界资源未被占用，且其可用数目为被占用，且其可用数目为1。然后将各进程访问该资源的然后将各进程访问该资源的临界区临界区放在放在一对一对wait(mutex)和和signal(mutex)之间之间，就能，就能保证保证

52、这些进程这些进程互斥互斥地进入各自的地进入各自的临界区。临界区。每个进程访问临界资源之前，必须先每个进程访问临界资源之前，必须先wait,如果资源空闲如果资源空闲(mutex=1)，那么可以进入临界区，并将，那么可以进入临界区，并将mutex-1 (=0)，使其他进程无法进入临界区。使其他进程无法进入临界区。832.4.4 信号量的应用信号量的应用wait(S)signal(S)wait(S)signal(S)wait(S)signal(S)P1P2P3临界区临界区842.4.4 信号量的应用信号量的应用2、利用信号量实现、利用信号量实现前趋关系前趋关系该类问题是指多个该类问题是指多个合作进程

53、合作进程在执行时在执行时有先后次序的要求有先后次序的要求，前后形成前趋后继关系，可以用前趋图描述。前后形成前趋后继关系，可以用前趋图描述。在前趋与后继同步问题中，每个在前趋与后继同步问题中，每个进程是否进程是否能够能够执行执行，取取决于决于它的它的所有前趋是否所有前趋是否执行执行结束结束。每个前趋的结束都是。每个前趋的结束都是它得以执行的必要条件之一，因此，它得以执行的必要条件之一，因此，需要需要针对针对该进程的该进程的每个前趋每个前趋设置设置一个信号量一个信号量，并在该，并在该进程开始处进程开始处执行相应执行相应的的wait操作。操作。同样，如果同样，如果进程有后继进程有后继，则当它，则当它

54、结束时结束时，需要，需要执行其后执行其后继所等待的信号量的继所等待的信号量的signal操作操作，释放其后继所等待的执，释放其后继所等待的执行条件。行条件。852.4.4 信号量的应用信号量的应用对于对于前趋后继前趋后继同步问题的算法可以按下列步骤进行：同步问题的算法可以按下列步骤进行： 分析每个分析每个进程进程j，看它有无前趋，如果有则针对，看它有无前趋，如果有则针对每个前趋每个前趋i设置一个信号量设置一个信号量Sij，初值皆为初值皆为0； 在每个在每个进程进程j开始开始时，针对其每个前趋的信号量时，针对其每个前趋的信号量Sij执行执行wait操作，操作，有几个前趋执行几个有几个前趋执行几个

55、wait操作；操作； 在每个在每个进程进程i执行完毕执行完毕后，针对其每个后继的信号量后，针对其每个后继的信号量Sij执行执行signal操作，有操作，有几个后继执行几个几个后继执行几个signal操作。操作。其中：其中：i表示表示前趋前趋进程号，进程号，j表示后继进程号。表示后继进程号。862.4.4 信号量的应用信号量的应用同步分析：同步分析： 进程进程Pj有无前趋有无前趋请求信号量请求信号量信号量初值信号量初值有无后继有无后继释放信号量释放信号量P1无无无无无无P2、P3S12、S13P2P1结束结束S120P4S24P3P1结束结束S130P4S34P4P2、P3结结束束S24、S34

56、0无无无无872.4.4 信号量的应用信号量的应用例如：设有例如：设有4个进程，其执行的先后流图如下图所示。用个进程，其执行的先后流图如下图所示。用wait、signal操作实现其同步。操作实现其同步。P1P4P3P288算法描述算法描述：main()int s12 = s13 = s24 = s34 = 0;cobeginp1(); p2(); p3(); p4();coendp1() 执行执行P1自己的程序自己的程序;/无前趋，所以无无前趋，所以无P操作操作 signal(s12); /有后继有后继P2，释放条件，释放条件s12 signal(s13);/有后继有后继P3，释放条件，释放条

57、件s13p2() wait(s12);/有前趋有前趋P1，申请条件，申请条件s12 执行执行P2自己的程序自己的程序; signal(s24); /有后继有后继P4，释放条件，释放条件s24p3()wait(s13);/有前趋有前趋P1，申请条件，申请条件s13执行执行P3自己的程序自己的程序;signal(s34);/有后继有后继P4，释放条件，释放条件s34p4()wait(s24);/有前趋有前趋P2，申请条件，申请条件s24wait(s34);/有前趋有前趋P3，申请条件，申请条件s34执行执行P4自己的程序自己的程序; /无后继，所以无无后继，所以无V操作操作 这样，无论哪个进程先来

58、，只要不是p1进程，都会在执行了相应的wait操作后，因为执行条件不成立而被挂到相应信号量的等待队列上，等待其前驱执行该信号量的signal操作后将其唤醒，从而保证这些进程并发执行时其执行的时序遵循给定的同步关系。891.问题的提出问题的提出 采用信号量同步机制来编写并发程序，对于采用信号量同步机制来编写并发程序，对于共享变量及共享变量及信号量变量的操作信号量变量的操作将被将被分散于各个进程分散于各个进程中，具有以下缺点：中，具有以下缺点：n 易读性差易读性差，因为要了解对于一组共享变量及信号量的操作，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序。是否正确，

59、则必须通读整个系统或者并发程序。n 不利于修改和维护不利于修改和维护，因为程序的局部性很差，所以任一组，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响全局。变量或一段代码的修改都可能影响全局。n 正确性难以保证正确性难以保证，因为操作系统或并发程序通常很大，要，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的。保证这样一个复杂的系统没有逻辑错误是很难的。2.4.5 管程机制管程机制902.2.管程的概念管程的概念n一个管程定义了一个数据结构和能为并发进程所执行一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进

60、程（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。和改变管程中的数据。n管程由三部分组成：管程由三部分组成：（1 1）局部于管程的若干）局部于管程的若干公共变量公共变量说明；说明；（2 2）对该数据结构进行操作的）对该数据结构进行操作的一组过程一组过程；（3 3）对局部于管程的数据）对局部于管程的数据设置初值设置初值的语句。此外，还必须的语句。此外，还必须给管程赋予一个名字。给管程赋予一个名字。2.4.5 管程机制管程机制91管程的基本形式管程的基本形式monitor monitor-name ; procedure (); ； procedure (); ； ； 92共享