第二章进程管理

1、2022-4-62022-4-61 12022-4-62022-4-62 2内容概述内容概述2.1 2.1 进程的基本概念进程的基本概念 2.2 2.2 进程控制进程控制 2.3 2.3 进程同步进程同步 2.4 2.4 经典进程的同步问题经典进程的同步问题 2.5 2.5 进程通信进程通信 2.6 2.6 线程线程 进程管理的进程管理的主要功能主要功能是把处理机分配给进程是把处理机分配给进程,并对处理器运并对处理器运行进行有效地控制和管理行进行有效地控制和管理,以及协调各个进程之间的相互关系。以及协调各个进程之间的相互关系。2022-4-62022-4-63 32.1.1 2.1.1 程序的

2、顺序执行及其特征程序的顺序执行及其特征2.1.2 2.1.2 前趋图前趋图2.1.3 2.1.3 程序的并发执行及其特征程序的并发执行及其特征2.1.4 2.1.4 进程的特征与状态进程的特征与状态2.1.5 2.1.5 进程控制块进程控制块2022-4-62022-4-64 4图图2-1 2-1 程序的顺序执行程序的顺序执行 1.程序的顺序执行程序的顺序执行仅当前一操作仅当前一操作(程序段程序段)执行完后，才能执行后继操作。执行完后，才能执行后继操作。例如例如，在进行计算时，总须先输入用户的程序和数据，然后进行在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。计算

3、，最后才能打印计算结果。 S1: a:=x+y; S2: b:=a-5; S3: c:=b+1;2.1.1 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征2022-4-62022-4-65 52.2.程序顺序执行时的特征程序顺序执行时的特征(1)(1)顺序性顺序性: :处理机的操作严格按照程序所规定的顺序执行处理机的操作严格按照程序所规定的顺序执行, ,只有当上一个操作完成后只有当上一个操作完成后, ,下一个操作才能执行。下一个操作才能执行。(2)(2)封闭性封闭性: :程序运行在一个封闭的环境中程序运行在一个封闭的环境中, ,即程序运行时独即程序运行时独占系统的全部资源占系统的全部

4、资源, ,这些资源的状态只能因程序的执行而改这些资源的状态只能因程序的执行而改变变, ,不受任何外界因素的影响。不受任何外界因素的影响。(3)(3)可再现性可再现性: :由于程序顺序执行的封闭性由于程序顺序执行的封闭性, ,只要程序顺序执只要程序顺序执行的行的初始条件和环境相同初始条件和环境相同, ,则不论何时执行则不论何时执行, ,也不论程序执也不论程序执行期间是否存在停顿行期间是否存在停顿, ,程序所得的程序所得的结果结果也也相同相同。结论结论: :正由于程序顺序执行的特点正由于程序顺序执行的特点, ,程序员可以检测和重现程序员可以检测和重现程序的错误程序的错误, ,可以调试和校正程序。可

5、以调试和校正程序。2022-4-62022-4-66 62.1.1 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征2.1.2 2.1.2 前趋图前趋图2.1.3 2.1.3 程序的并发执行及其特征程序的并发执行及其特征2.1.4 2.1.4 进程的特征与状态进程的特征与状态2.1.5 2.1.5 进程控制块进程控制块2022-4-62022-4-67 72.1.2 2.1.2 前趋图前趋图(Precedence Graph)(Precedence Graph) 前趋图是一个有向前趋图是一个有向无循环无循环图，记为图，记为DAG。用于描述进程之。用于描述进程之间执行的前后关系。间执行的

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

7、结点终止结点(Final Node)。2022-4-62022-4-68 8 每个结点还具有一个每个结点还具有一个重量重量(Weight)，用于表示该结点，用于表示该结点所含有的所含有的程序量程序量或结点的或结点的执行时间执行时间。 图图2-2 2-2 前趋图前趋图 直接前趋直接前趋直接后继直接后继初始结点初始结点终止结点终止结点2022-4-62022-4-69 9对于图对于图 2-2(a)所示的前趋图所示的前趋图,存在下述前趋关系存在下述前趋关系P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9或表示为或表示为:

8、 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 2022-4-62022-4-610102.1.1 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征2.1.2 2.1.2 前趋图前趋图2.1.3 2.1.3

9、程序的并发执行及其特征程序的并发执行及其特征2.1.4 2.1.4 进程的特征与状态进程的特征与状态2.1.5 2.1.5 进程控制块进程控制块2022-4-62022-4-611112.1.3 2.1.3 程序的并发执行及其特征程序的并发执行及其特征 1.1.程序的并发执行程序的并发执行 图图2-3 2-3 并发执行时的前趋图并发执行时的前趋图 并发并发输入程序输入程序I I计算程序计算程序C C输出程序输出程序P P2022-4-62022-4-61212下述四条语句的程序段下述四条语句的程序段: S1: a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+6 图图

10、2-4 2-4 四条语句的前趋关系四条语句的前趋关系S1S2S3S4什么样的程序可以并发执行？什么样的程序可以并发执行？2022-4-62022-4-613132.2.程序并发执行时的特征程序并发执行时的特征 (1)(1)间断性间断性 相互制约导致并发程序具有相互制约导致并发程序具有“执行执行- -暂停暂停- -执行执行”的间断性活动规律。的间断性活动规律。(2)(2)失去封闭性失去封闭性 系统中多道程序系统中多道程序共享共享资源，资源的状态由多个程资源，资源的状态由多个程序来改变，必然失去了程序的封闭性。序来改变，必然失去了程序的封闭性。(3)(3)不可再现性不可再现性 失去封闭性失去封闭性

11、 失去可再现性，外界环境在程序的失去可再现性，外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。两次执行期间发生变化，失去原有的可重复特征。2022-4-62022-4-61414例如例如, ,有两个程序有两个程序A A和和B,B,它们共享一个变量它们共享一个变量N(N(初始值为初始值为x)x)。 A:A:N:=N+1N:=N+1 B: B:Print(N);Print(N);N:=0; N:=0; 程序程序A A和和B B并发执行，可出现以下并发执行，可出现以下三种三种情况情况: : (1)N:=N+1 (1)N:=N+1在在Print(N)Print(N)和和N:=0N:=0之之

12、前前, ,此时得到的此时得到的N N值分别为值分别为x+1, x+1, 0 x+1, x+1, 0。 (2)N:=N+1(2)N:=N+1在在Print(N)Print(N)和和N:=0N:=0之之后后, ,此时得到的此时得到的N N值分别为值分别为x, 0, 1x, 0, 1。 (3)N:=N+1(3)N:=N+1在在Print(N)Print(N)和和N:=0N:=0之之间间, ,此时得到的此时得到的N N值分别为值分别为x, x+1, 0 x, x+1, 0。 2022-4-62022-4-615152.1.1 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征2.1.2 2.1.

13、2 前趋图前趋图2.1.3 2.1.3 程序的并发执行及其特征程序的并发执行及其特征2.1.4 2.1.4 进程的特征与状态进程的特征与状态2.1.5 2.1.5 进程控制块进程控制块2022-4-62022-4-616161 1、进程实体的构成、进程实体的构成(1)(1)程序程序( (段段) )：进程要进行的操作。：进程要进行的操作。(2)(2)数据段数据段：包括操作的数据和程序自己的变量。：包括操作的数据和程序自己的变量。(3)(3)进程控制块进程控制块PCB(Process Control Block)PCB(Process Control Block)：存放进程：存放进程标识符、进程运

14、行的当前状态、程序和数据的地址、程标识符、进程运行的当前状态、程序和数据的地址、程序运行时的序运行时的CPUCPU环境等。环境等。2022-4-62022-4-617172.1.4 2.1.4 进程的特征与状态进程的特征与状态 2.2.进程的特征进程的特征 结构特征结构特征：进程的创建与撤消就是：进程的创建与撤消就是PCB的创建与撤消。的创建与撤消。 动态性动态性：进程是一个动态的概念，实质上是程序的一次：进程是一个动态的概念，实质上是程序的一次执行过程。进程具有生命期：它因执行过程。进程具有生命期：它因“创建创建”而产生，因而产生，因“调度调度”而执行，执行时还走走停停，因而执行，执行时还走

15、走停停，因“撤消撤消”而灭而灭亡。亡。 并发性并发性：多个进程实体同存于内存中：多个进程实体同存于内存中, ,且能在一段时间且能在一段时间内同时运行内同时运行, ,共享系统资源共享系统资源; ;引入进程实体的目的就是并引入进程实体的目的就是并发执行。发执行。2022-4-62022-4-618182.进程的特征进程的特征独立性独立性：进程是一个能：进程是一个能独立运行独立运行的基本单位，也是系统的基本单位，也是系统进行资源分配和调度的基本单位。进行资源分配和调度的基本单位。异步性异步性：各进程按各自独立的、不可预知的速度向前推：各进程按各自独立的、不可预知的速度向前推进。进。3.3.进程的定义

16、进程的定义进程是进程实体的运行过程进程是进程实体的运行过程, ,是系统进行资源分配和调度是系统进行资源分配和调度的一个独立单位。的一个独立单位。2022-4-62022-4-61919 进程是动态的，程序是静态的进程是动态的，程序是静态的：程序是有序代码的集合，：程序是有序代码的集合，它可以复制；进程是程序在数据集上的一次执行。它可以复制；进程是程序在数据集上的一次执行。 进程是暂时的进程是暂时的, ,程序是永久的程序是永久的：进程是一个状态变化的过程，：进程是一个状态变化的过程，有它的撤销，程序可长久保存。有它的撤销，程序可长久保存。 进程具有结构特征进程具有结构特征：由程序段、数据段和进程

17、控制块三者：由程序段、数据段和进程控制块三者组成，而程序仅是指令的有序集合组成，而程序仅是指令的有序集合, ,是进程的组成部分之一。是进程的组成部分之一。 进程与程序的对应关系进程与程序的对应关系：通过多次执行，一个程序可对应：通过多次执行，一个程序可对应多个进程。多个进程。2022-4-62022-4-620205.5.进程的状态进程的状态(1)(1)进程的三种基本状态进程的三种基本状态就绪就绪(Ready)(Ready)状态：进程已获得除处理机外的所需资源，状态：进程已获得除处理机外的所需资源，等待分配处理机资源；只要分配等待分配处理机资源；只要分配CPUCPU就可执行。就可执行。执行执行

18、(Running)(Running)状态：处于就绪状态的进程一旦获得了处状态：处于就绪状态的进程一旦获得了处理机，进程状态就处于执行状态。理机，进程状态就处于执行状态。阻塞阻塞(Blocked)(Blocked)状态状态(“(“等待等待”或或“睡眠睡眠”) )：由于进程等：由于进程等待某种事件待某种事件( (如如I/OI/O操作或进程同步操作或进程同步) )，在事件发生之前无，在事件发生之前无法继续执行。该事件发生前即使把处理机分配给该进程法继续执行。该事件发生前即使把处理机分配给该进程, ,也无法运行。如也无法运行。如: :请求请求I/OI/O操作，申请缓冲空间等。操作，申请缓冲空间等。20

19、22-4-62022-4-62121图图2-5 2-5 进程的三种基本状态及其转换进程的三种基本状态及其转换 1.1.时间片用光时间片用光2.2.有优先级高的进程到来有优先级高的进程到来2022-4-62022-4-62222 引入挂起状态的原因引入挂起状态的原因 v终端用户的请求终端用户的请求v父进程请求父进程请求v负荷调节的需要负荷调节的需要v操作系统的需要操作系统的需要 (2)进程的挂起状态进程的挂起状态图图2-6 2-6 具有挂起状态的进程状态图具有挂起状态的进程状态图 2022-4-62022-4-62323 创建状态创建状态：当一个新进程刚刚建立：当一个新进程刚刚建立, ,还未将其

20、放入就绪还未将其放入就绪队列时的状态，称为新状态。队列时的状态，称为新状态。 终止状态终止状态：当一个进程已经正常结束或异常结束，操：当一个进程已经正常结束或异常结束，操作系统已将其从系统队列中移出，但尚未撤消，这时作系统已将其从系统队列中移出，但尚未撤消，这时称为终止状态。称为终止状态。 2022-4-62022-4-62424图图2-7 2-7 进程的五种基本状态及其转换进程的五种基本状态及其转换 2022-4-62022-4-625252.1.1 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征2.1.2 2.1.2 前趋图前趋图2.1.3 2.1.3 程序的并发执行及其特征程序

21、的并发执行及其特征2.1.4 2.1.4 进程的特征与状态进程的特征与状态2.1.5 2.1.5 进程控制块进程控制块2022-4-62022-4-626262.1.5 2.1.5 进程控制块进程控制块 1.1.进程控制块的作用进程控制块的作用 进程控制块的进程控制块的作用作用是使一个在多道程序环境下不能是使一个在多道程序环境下不能独立运行的程序独立运行的程序( (含数据含数据) )，成为一个能独立运行的基本，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，单位，一个能与其它进程并发执行的进程。或者说，OSOS是根据是根据PCBPCB来对并发执行的进程进行控制和管理的。来

22、对并发执行的进程进行控制和管理的。 记录了操作系统所需的记录了操作系统所需的, ,用于描述进程情况及控制进用于描述进程情况及控制进程运行所需的程运行所需的全部信息全部信息。 PCBPCB是进程存在的唯一标志。是进程存在的唯一标志。2022-4-62022-4-627272.2.进程控制块中的信息进程控制块中的信息 进程标识符进程标识符 内部标识符和外部标识符。内部标识符和外部标识符。 处理机状态处理机状态通用寄存器通用寄存器指令计数器指令计数器PC程序状态字程序状态字PSW用户栈指针用户栈指针 进程调度信息进程调度信息进程状态进程状态进程优先级进程优先级进程调度所需的其它信息进程调度所需的其它

23、信息事件事件 进程控制信息进程控制信息程序和数据的地址程序和数据的地址进程同步和通信机制进程同步和通信机制资源清单资源清单链接指针链接指针struct pcb int id; /进程序号进程序号 int ra; /所需资源所需资源A的数量的数量 int rb; /所需资源所需资源B的数量的数量 int rc; /所需资源所需资源C的数量的数量 int ntime; /所需的时间片个数所需的时间片个数 int rtime; /已经运行的时间片个数已经运行的时间片个数 char state; /进程状态进程状态 struct pcb *next; 2022-4-62022-4-62828图图2-9

24、 PCB2-9 PCB链接队列示意图链接队列示意图 3.3.进程控制块的组织方式进程控制块的组织方式(1)(1)链接方式链接方式 (2)(2)索引方式索引方式2022-4-62022-4-62929图图2-10 2-10 按索引方式组织按索引方式组织PCB PCB 3.3.进程控制块的组织方式进程控制块的组织方式(1)(1)链接方式链接方式 (2)(2)索引方式索引方式2022-4-62022-4-630302.1 2.1 进程的基本概念进程的基本概念 2.2 2.2 进程控制进程控制 2.3 2.3 进程同步进程同步 2.4 2.4 经典进程的同步问题经典进程的同步问题 2.5 2.5 进程

25、通信进程通信2.6 2.6 线程线程2022-4-62022-4-631311.1.系统态和用户态系统态和用户态 处理机的执行状态分处理机的执行状态分系统态系统态和和用户态用户态两种两种: : (1) (1)系统态系统态( (管态、核心态管态、核心态) )：有较高特权，能执行一切：有较高特权，能执行一切指令，访问所有寄存器和存储区。指令，访问所有寄存器和存储区。 (2)(2)用户态用户态( (目态目态) )：有较低特权，能执行规定指令，访：有较低特权，能执行规定指令，访问指定寄存器和存储区。问指定寄存器和存储区。用户程序运行在用户态，不能执行用户程序运行在用户态，不能执行OSOS指令及区域。指

26、令及区域。OSOS内核运行在系统态，进程控制是由内核运行在系统态，进程控制是由OSOS内核实现的。内核实现的。2022-4-62022-4-632322.2.进程控制的功能进程控制的功能 进程控制是进程管理中最基本的功能：进程控制是进程管理中最基本的功能：创建创建新进程新进程终止终止已结束进程已结束进程终止终止由于某事件而无法运行下去的进程由于某事件而无法运行下去的进程负责进程的状态负责进程的状态转换转换 进程控制一般由进程控制一般由OSOS的内核中的原语来实现的。的内核中的原语来实现的。2022-4-62022-4-633333.3.原语原语由若干条指令构成的由若干条指令构成的“原子操作原子

27、操作”过程，在执行期过程，在执行期间间不可中断不可中断，作为一个整体而不可分割。，作为一个整体而不可分割。原子操作：一个操作中的所有动作要么全做，要么原子操作：一个操作中的所有动作要么全做，要么全不做。全不做。原子操作在管态下执行，常驻内存。原子操作在管态下执行，常驻内存。原语的作用是为了实现进程的通信和控制。原语的作用是为了实现进程的通信和控制。1.创建原语创建原语2.撤消原语撤消原语3.阻塞原语阻塞原语4.唤醒原语唤醒原语5.挂起原语挂起原语6.激活原语激活原语2022-4-62022-4-634342.2.1 2.2.1 进程的创建进程的创建2.2.2 2.2.2 进程的终止进程的终止2

28、.2.3 2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒2.2.4 2.2.4 进程的挂起与激活进程的挂起与激活2022-4-62022-4-63535图图2-9 2-9 进程树进程树 1. 1.进程图进程图(Process Graph)(Process Graph)进程图进程图是用于描述一个进程的是用于描述一个进程的家族关系的有向树，树中的结家族关系的有向树，树中的结点表示进程。点表示进程。子进程可以继承父进程的资源。子进程可以继承父进程的资源。撤消父进程时必须同时撤消子撤消父进程时必须同时撤消子进程进程2022-4-62022-4-636362.2.引起创建进程的事件引起创建进程的事件 (1

29、)(1)用户登录用户登录 (2)(2)作业调度作业调度 (3)(3)提供服务提供服务 (4)(4)应用请求应用请求 3.3.进程的创建步骤进程的创建步骤(1)(1)申请空白申请空白PCB PCB (2)(2)为新进程分配资源为新进程分配资源 (3)(3)初始化进程控制块初始化进程控制块 (4)(4)将新进程插入就绪队列将新进程插入就绪队列2022-4-62022-4-637372.2.1 2.2.1 进程的创建进程的创建2.2.2 2.2.2 进程的终止进程的终止2.2.3 2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒2.2.4 2.2.4 进程的挂起与激活进程的挂起与激活2022-4-620

30、22-4-638381.1.引起进程终止的事件引起进程终止的事件 1)1)正常结束正常结束 2)异常结束异常结束 3)外界干预外界干预2022-4-62022-4-639392.2.进程的终止过程进程的终止过程 (1)(1)从从PCBPCB集合中检索出该进程的集合中检索出该进程的PCB, PCB, 读出该进程的状态。读出该进程的状态。 (2)(2)若被终止进程正处于执行状态若被终止进程正处于执行状态, ,应立即终止该进程的执应立即终止该进程的执行。行。 (3)(3)若该进程还有子孙进程若该进程还有子孙进程, ,应将其所有子孙进程予以终止。应将其所有子孙进程予以终止。 (4)(4)将被终止进程所

31、拥有的全部资源将被终止进程所拥有的全部资源, , 归还给其父进程归还给其父进程, , 或者归还给系统。或者归还给系统。 (5)(5)将被终止进程将被终止进程( (它的它的PCB)PCB)从所在队列从所在队列( (或链表或链表) )中移出中移出, ,等待其他程序来搜集信息。等待其他程序来搜集信息。 2022-4-62022-4-640402.2.1 2.2.1 进程的创建进程的创建2.2.2 2.2.2 进程的终止进程的终止2.2.3 2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒2.2.4 2.2.4 进程的挂起与激活进程的挂起与激活2022-4-62022-4-641411.1.引起进程阻塞和

32、唤醒的事件引起进程阻塞和唤醒的事件 (1) (1)请求系统服务请求系统服务 (2)(2)启动某种操作启动某种操作 (3)(3)新数据尚未到达新数据尚未到达 (4)(4)无新工作可做无新工作可做2022-4-62022-4-64242 2. 2.进程阻塞过程进程阻塞过程 进程调用阻塞原语进程调用阻塞原语block()block()把自己阻塞，立即停止执把自己阻塞，立即停止执行，把进程控制块中的现行状态由行，把进程控制块中的现行状态由“执行执行”改为阻塞，改为阻塞，并将并将PCBPCB插入阻塞队列。插入阻塞队列。 将本进程插入到具有相同事件的阻塞将本进程插入到具有相同事件的阻塞( (等待等待) )

33、队列。队列。 调度程序进行重新调度调度程序进行重新调度, ,将处理机分配给另一就绪进将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状程，并进行切换，亦即，保留被阻塞进程的处理机状态态( (在在PCBPCB中中) )，再按新进程的，再按新进程的PCBPCB中的处理机状态设置中的处理机状态设置CPUCPU的环境。的环境。2022-4-62022-4-64343 3. 3.进程唤醒过程进程唤醒过程 调用唤醒原语调用唤醒原语wakeup( )wakeup( )将等待该事件的进程唤醒。将等待该事件的进程唤醒。 唤醒原语执行的过程是唤醒原语执行的过程是 把被阻塞的进程从等待该事件的阻

34、塞队列中移出把被阻塞的进程从等待该事件的阻塞队列中移出 将其将其PCBPCB中的现行状态由阻塞改为就绪中的现行状态由阻塞改为就绪 将该将该PCBPCB插入到就绪队列中插入到就绪队列中2022-4-62022-4-644442.2.1 2.2.1 进程的创建进程的创建2.2.2 2.2.2 进程的终止进程的终止2.2.3 2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒2.2.4 2.2.4 进程的挂起与激活进程的挂起与激活2022-4-62022-4-64545 1. 1.进程的挂起进程的挂起 系统将利用挂起原语系统将利用挂起原语suspend( )suspend( )将指定进程或处于阻将指定进程

35、或处于阻塞状态的进程挂起。塞状态的进程挂起。 suspend()suspend()原语的执行过程原语的执行过程 首先检查被挂起进程的状态，若处于活动就绪状首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。进程，则将之改为静止阻塞。 把该进程的把该进程的PCBPCB复制到某指定的内存区域。复制到某指定的内存区域。 若被挂起的进程正在执行若被挂起的进程正在执行, ,则转向调度程序重新调则转向调度程序重新调度。度。2022-4-62022-4-64646 2. 2.进程的激活过程进程的激活过程 系统

36、将利用激活原语系统将利用激活原语active( )active( )将指定进程激活。将指定进程激活。 active()active()原语执行过程原语执行过程 将进程从外存调入内存，检查该进程的现行状态，将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，将之改为活动就绪；若为静止阻若是静止就绪，将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。塞便将之改为活动阻塞。 假如采用的是抢占调度策略，则每当有新进程进假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级由调度程序将

37、被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。处理机分配给刚被激活的进程。2022-4-62022-4-647472.1 2.1 进程的基本概念进程的基本概念 2.2 2.2 进程控制进程控制 2.3 2.3 进程同步进程同步 2.4 2.4 经典进程的同步问题经典进程的同步问题 2.5 2.5 进程通信进程通信2.6 2.6 线程线程2022-4-62022-4-64848 进程同步的主要任务是对多个相关进程在执行

38、次序进程同步的主要任务是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地上进行协调，以使并发执行的诸进程之间能有效地共享共享资源资源和和相互合作相互合作，从而使程序的执行具有可再现性。，从而使程序的执行具有可再现性。2.3.1 2.3.1 进程同步的基本概念进程同步的基本概念2.3.2 2.3.2 信号量机制信号量机制2.3.3 2.3.3 信号量的应用信号量的应用2.3.4 2.3.4 管程机制管程机制2022-4-62022-4-649492.3.1 2.3.1 进程同步的基本概进程同步的基本概念念1.两种形式的制约关系两种形式的制约关系(1)(1)间接相互制约关系间接

39、相互制约关系 源于资源共享。如源于资源共享。如A A、B B共享打印机，若共享打印机，若A A申请打印时，申请打印时，打印机已分配给打印机已分配给B B，则，则A A只能阻塞，等只能阻塞，等B B释放后再改为就绪，释放后再改为就绪，又称为又称为“互斥互斥”。(2)(2)直接相互制约关系直接相互制约关系 源于进程之间的合作关系。如进程源于进程之间的合作关系。如进程A A向向B B提供数据，当提供数据，当输入缓冲空时，输入缓冲空时，B B不能得到数据而阻塞；反之当缓冲满时，不能得到数据而阻塞；反之当缓冲满时，A A无法写入而阻塞，又称为无法写入而阻塞，又称为“同步同步”。2022-4-62022-

40、4-650502.2.临界资源临界资源定义定义: :在一段时间内只允许一个进程访问的资源。在一段时间内只允许一个进程访问的资源。例如例如: :打印机、磁带机、卡片输入机、变量、表格、数据、打印机、磁带机、卡片输入机、变量、表格、数据、 指针、数组等。进程之间采取互斥方式实现对这些指针、数组等。进程之间采取互斥方式实现对这些 资源的共享。资源的共享。例子：例子： 生产者生产者- -消费者消费者(producer-consumer)(producer-consumer)问题是一个著名的问题是一个著名的进程同步问题。进程同步问题。有一群生产者进程在生产产品，提供给消费者进程去消费。有一群生产者进程在

41、生产产品，提供给消费者进程去消费。不能向满缓冲区投放产品，不能从空缓冲区中取产品。不能向满缓冲区投放产品，不能从空缓冲区中取产品。2022-4-62022-4-65151 一个数组缓冲池，有一个数组缓冲池，有n个缓冲区。个缓冲区。 buffer:array0, 1, , n-1 of item 输入指针输入指针in in =(in+1)mod n。 输出指针输出指针out out =(out+1) mod n。 counter：初始值为：初始值为0。缓冲池中含有的产品数目。缓冲池中含有的产品数目。0 1 n-1inout 2022-4-62022-4-65252producer: repeat

42、 producer: repeat 生产者进程生产者进程 produce an item in nextp;produce an item in nextp;/生产一个产品生产一个产品 while counter=n do no-op;while counter=n do no-op; bufferbufferinin = =nextp;nextp;/将产品放入缓冲区内将产品放入缓冲区内 in =in =in+1 mod n;in+1 mod n; counter =counter =counter+1;counter+1; /缓冲池中产品数加一缓冲池中产品数加一 until false;un

43、til false;consumer: repeat consumer: repeat 消费者进程消费者进程 while counter=0 do no-op;while counter=0 do no-op; nextc =nextc =bufferbufferoutout; ;/从缓冲区中消费产品从缓冲区中消费产品 out =out =(out+1) mod n;(out+1) mod n; counter = counter-1;counter = counter-1; /缓冲池中产品数减一缓冲池中产品数减一 consumer the item in nextc;/consumer th

44、e item in nextc;/消费一个产品消费一个产品 until false; until false; 2022-4-62022-4-65353 虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时， 常可用下面的形式描述：register1=counter; register2=counter;register1=register1+1; register2=register2-1;counter

45、=register1; counter=register2; 2022-4-62022-4-65454 假设：counter的当前值是5。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句，则最后共享变量counter的值仍为5；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，counter值也还是5，但是，如果按下述顺序执行，counter值是4。由于并发执行而失去封闭性。register1=counter; (register1=5)register1=register1+1; (register1=6)register2=co

46、unter; (register2=5)register2=register2-1; (register2=4)counter=register1; (counter=6)counter=register2; (counter=4) 共享资源的访问互斥2022-4-62022-4-65555不论是不论是硬件临界资源硬件临界资源还是还是软件临界资源软件临界资源，多个进程必须，多个进程必须互斥互斥地对它进行访问。地对它进行访问。在每个进程中访问临界资源的那段代码称为在每个进程中访问临界资源的那段代码称为临界区。临界区。每个进程进入临界区之前应先对欲访问的临界资源进行每个进程进入临界区之前应先对欲访

47、问的临界资源进行检查，看是否正在被访问。如果此刻该临界资源未被访检查，看是否正在被访问。如果此刻该临界资源未被访问，该进程可进入临界区问，该进程可进入临界区, ,并设置它正在被访问的标志，并设置它正在被访问的标志，在临界区之前执行的这段代码称为在临界区之前执行的这段代码称为进入区。进入区。在临界区后面也要加上一段代码，用于将临界区被访问在临界区后面也要加上一段代码，用于将临界区被访问的资源恢复为未被访问的标志，称为的资源恢复为未被访问的标志，称为退出区。退出区。2022-4-62022-4-65656可把一个可把一个访问临界资源访问临界资源的循环进程描述如下的循环进程描述如下: :repeat

48、 critical section; 临界区临界区 remainder section; 剩余区剩余区 until false; entry sectionexit section 进入区进入区 退出区退出区 2022-4-62022-4-657574.4.同步机制应遵循的规则同步机制应遵循的规则(1)(1)空闲让进：空闲让进：当无进程处于临界区时当无进程处于临界区时, ,应允许一个进程进应允许一个进程进入临界区入临界区, ,以有效利用临界资源。以有效利用临界资源。(2)(2)忙则等待忙则等待：当有进程进入临界区时当有进程进入临界区时, ,其他进程必须等待。其他进程必须等待。(3)(3)有限等

49、待：有限等待：对要求访问临界资源的进程对要求访问临界资源的进程, ,应保证在有限应保证在有限时间内进入自己的临界区时间内进入自己的临界区, ,防止防止“死等死等”。(4)(4)让权等待：让权等待：当进程不能进入其临界区时当进程不能进入其临界区时, ,应立即释放处应立即释放处理机理机, ,防止防止“忙等忙等”, ,不能一直用语句判断能不能进不能一直用语句判断能不能进, ,占占用处理机。用处理机。2022-4-62022-4-658582.3.1 2.3.1 进程同步的基本概念进程同步的基本概念2.3.2 2.3.2 信号量机制信号量机制2.3.3 2.3.3 信号量的应用信号量的应用2022-4

50、-62022-4-65959 19651965年年, ,荷兰学者荷兰学者DijkstraDijkstra提出的信号量提出的信号量(Semaphores)(Semaphores)机制是一种有效的进程同步工具机制是一种有效的进程同步工具, ,所以所以P P、V V分别是荷兰分别是荷兰语的语的test(proberen)test(proberen)和和increment(verhogen)increment(verhogen)。 信号量机制已从信号量机制已从整型信号量整型信号量发展为发展为记录型信号量记录型信号量、ANDAND型信号量型信号量, ,又进一步发展为信号量集。又进一步发展为信号量集。 信

51、号量就是信号量就是OSOS提供的管理公有资源的有效手段。提供的管理公有资源的有效手段。 信号量代表信号量代表可用资源实体的数量可用资源实体的数量。2022-4-62022-4-660601.1.整型信号量整型信号量除除初始化初始化外，仅能通过两个标准的外，仅能通过两个标准的原子操作原子操作wait(S)和和signal(S)来访问。也称为来访问。也称为P、V操作。操作。wait和和signal操作可描述为操作可描述为:uwait(S): while S0 do no-op; S:=S-1;usignal(S): S:=S+1; wait(S)和和signal(S)是原子操作，因此它们在执行时是

52、不可是原子操作，因此它们在执行时是不可中断的。另外，信号量只能通过原语操作来访问，不能被中断的。另外，信号量只能通过原语操作来访问，不能被进程调度所打断。进程调度所打断。 有有“忙等忙等”现象。现象。2022-4-62022-4-66161可把一个可把一个访问临界资源访问临界资源的循环进程描述如下的循环进程描述如下: :repeat critical section; 临界区临界区 remainder section; 剩余区剩余区 until false; entry sectionexit sectionP(S)或或wait(S);V(S)或或signal(S); 进入区进入区 退出区退出

53、区 2022-4-62022-4-662622.2.记录型信号量记录型信号量 记录型信号量（也称资源信号量）机制，则是一种不存记录型信号量（也称资源信号量）机制，则是一种不存在在“忙等忙等”现象的进程同步机制，它采用了现象的进程同步机制，它采用了记录型的数记录型的数据结构。据结构。 在采取了在采取了“让权等待让权等待”的策略后，又会出现多个进程等的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量除了需要一个用于代表资源数目的整型变量valuevalue外，外，还应增加一个进程链表还应

54、增加一个进程链表L L，用于链接上述的所有等待进，用于链接上述的所有等待进程。程。2022-4-62022-4-66363type semaphore=record value:integer;/资源数目资源数目 L:list of process;/进程链表指针进程链表指针 endprocedure wait(S) var S: semaphore; begin S.value:=S.value-1; if S.value0 then block(S.L); end procedure signal(S) var S: semaphore; begin S.value:=S.value+1;

55、 if S.value0 then wakeup(S.L); end 请求一个单位的该类资源该类资源数减少一个自我阻塞，放弃处理机释放一个单位资源该类资源增加一个唤醒进程2022-4-62022-4-66464 在有些任务中在有些任务中, ,一个进程先要获得多个共享资源后才能一个进程先要获得多个共享资源后才能执行，若进程执行，若进程A A和和B B都要申请都要申请D D和和E E两种资源，设信号量两种资源，设信号量DmutexDmutex和和EmutexEmutex的初值均为的初值均为1 1在两个进程中都要包含两个对在两个进程中都要包含两个对DmutexDmutex和和EmutexEmutex

56、的操作，即的操作，即process A: process B: P(Dmutex); P(Emutex); P(Emutex); P(Dmutex);若进程若进程A A和和B B按下述次序交替执行按下述次序交替执行P P操作操作: process A: P(Dmutex); 于是于是Dmutex=0 process B: P(Emutex); 于是于是Emutex=0 process A: P(Emutex); 于是于是Emutex=-1 A阻塞阻塞 process B: P(Dmutex); 于是于是Dmutex=-1 B阻塞阻塞 2022-4-62022-4-66565 AND AND同步

57、机制的同步机制的基本思想基本思想是是: :将进程在整个运行过程中将进程在整个运行过程中需要的所有资源需要的所有资源, ,一次性全部一次性全部地分配给进程地分配给进程, ,待进程使用完待进程使用完后再一起释放。只要尚有一个资源未能分配给进程后再一起释放。只要尚有一个资源未能分配给进程, ,其它所其它所有可能为之分配的资源有可能为之分配的资源, ,也不分配给他。亦即也不分配给他。亦即, ,对若干个临对若干个临界资源的分配界资源的分配, ,采取原子操作方式采取原子操作方式: :要么全部分配到进程要么全部分配到进程, ,要要么一个也不分配。由死锁理论可知么一个也不分配。由死锁理论可知, ,这样就可避免

58、上述死锁这样就可避免上述死锁情况的发生。为此情况的发生。为此, ,在在P P操作中操作中, ,增加了一个增加了一个“AND”AND”条件条件, ,故故称为称为ANDAND同步同步, ,或称为同时或称为同时P P操作操作, , 即即SP(Simultaneous wait)SP(Simultaneous wait)定义如下定义如下: : 2022-4-62022-4-66666SP:Swait(S1, S2, , Sn) if Si1 and and Sn1 then 每个资源都可用每个资源都可用 for i: =1 to n do Si:=Si-1; 分配所有资源分配所有资源 endfor e

59、lse 否则否则,将进程放到等待资源将进程放到等待资源Si的队列中的队列中 “阻塞阻塞”( (去第去第1 1个个S Si11的的“等待等待S Si”的阻塞队列中排队的阻塞队列中排队, ,并置它的程序计数器于并置它的程序计数器于SPSP操作的起始点操作的起始点) ) endifSV:Ssignal(S1, S2, , Sn) for i: =1 to n do Si=Si+1; 释放所有资源释放所有资源 “唤醒唤醒”( (所有所有“等待等待S Si i”的阻塞进程的阻塞进程, ,置为置为“就绪就绪”状状态态, ,移到就绪队列中移到就绪队列中) ) endfor; 2022-4-62022-4-6

60、6767在记录型信号量机制中在记录型信号量机制中,P(S),P(S)和和V(S)V(S)操作仅能对信号量施操作仅能对信号量施以加以加1 1或减或减1 1操作操作, ,意味着每次只能获得或释放一个单位的意味着每次只能获得或释放一个单位的临界资源临界资源, ,效率较低。效率较低。在有些情况下在有些情况下, ,当资源数量低于某下限值时便不予分配。当资源数量低于某下限值时便不予分配。因而因而, ,在每次分配之前在每次分配之前, ,都必须测试该资源的数量都必须测试该资源的数量, ,看其是看其是否大于下限值。否大于下限值。在对在对ANDAND型信号量机制扩充的基础上型信号量机制扩充的基础上, ,形成一般化