chapter-2-进程的描述与控制解析课件.ppt

1、计算机科学与技术系计算机科学与技术系2022-12-31内容概述内容概述进程管理的主要功能主要功能是把处理机分配给进程,并对处理器运行进行有效地控制和管理,以及协调各个进程之间的相互关系。2.1 2.1 前驱图和程序执行前驱图和程序执行 2.2 2.2 进程的描述进程的描述2.3 2.3 进程控制进程控制2.4 2.4 进程同步进程同步2.5 2.5 经典进程的同步问题经典进程的同步问题2.6 2.6 进程通信进程通信2.7 2.7 线程的基本概念线程的基本概念2.8 2.8 线程的实现线程的实现计算机科学与技术系计算机科学与技术系2022-12-322.1.1 2.1.1 前趋图前趋图2.1

2、.2 2.1.2 程序顺序执行程序顺序执行2.1.3 2.1.3 程序并发执行程序并发执行计算机科学与技术系计算机科学与技术系2022-12-332.1.1 2.1.1 前趋图前趋图前趋图是一个有向前趋图是一个有向无循环无循环图，记为图，记为DAG。用于描述进程之间。用于描述进程之间执行的前后关系。执行的前后关系。图中的每个图中的每个结点结点可用于描述一个程序段或进程，乃至一条语可用于描述一个程序段或进程，乃至一条语句；结点间的句；结点间的有向边有向边则用于表示两个结点之间存在的则用于表示两个结点之间存在的偏序偏序或或前前趋关系趋关系“”。=(Pi,Pj)|Pi must complete b

3、efore Pj may start,如果如果(Pi,Pj),可写成可写成PiPj：称称Pi是是Pj的的直接前趋直接前趋，而称，而称Pj是是Pi的的直接后继直接后继。把没有前趋的结点称为把没有前趋的结点称为初始结点初始结点(Initial Node)，把没有后继，把没有后继的结点称为的结点称为终止结点终止结点(Final Node)。计算机科学与技术系计算机科学与技术系2022-12-34 每个结点还具有一个每个结点还具有一个重量重量(Weight)，用于表示该结点，用于表示该结点所含有的所含有的程序量程序量或结点的或结点的执行时间执行时间。图图2-1 2-1 前趋图前趋图 直接前趋直接前趋直

4、接后继直接后继初始结点初始结点终止结点终止结点计算机科学与技术系计算机科学与技术系2022-12-35对于图对于图 2-1(a)所示的前趋图所示的前趋图,存在下述前趋关系存在下述前趋关系P1P2,P1P3,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)应当注意应当注意,前趋图中必须前趋图中必须不存在不存在循

5、环循环,但在图但在图2-1(b)中却有着下述的前趋关中却有着下述的前趋关系系:S2S3,S3S2 2022-12-362.1.1 2.1.1 前趋图前趋图2.1.2 2.1.2 程序顺序执行程序顺序执行2.1.3 2.1.3 程序并发执行程序并发执行计算机科学与技术系计算机科学与技术系2022-12-37图图2-2 2-2 程序的顺序执行程序的顺序执行 1.程序的顺序执行程序的顺序执行仅当前一操作仅当前一操作(程序段程序段)执行完后，才能执行后继操作。执行完后，才能执行后继操作。例如例如，在进行计算时，总须先输入用户的程序和数据，然后进行在进行计算时，总须先输入用户的程序和数据，然后进行计算，

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

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

8、 2.1.1 前趋图前趋图2.1.2 2.1.2 程序顺序执行程序顺序执行2.1.3 2.1.3 程序并发执行程序并发执行计算机科学与技术系计算机科学与技术系2022-12-3102.1.3 2.1.3 程序并发执行程序并发执行1.1.程序的并发执行程序的并发执行 图图2-3 2-3 并发执行时的前趋图并发执行时的前趋图 并发并发输入程序输入程序I I计算程序计算程序C C输出程序输出程序P P计算机科学与技术系计算机科学与技术系2022-12-311下述四条语句的程序段下述四条语句的程序段:S1:a:=x+2 S2:b:=y+4 S3:c:=a+b S4:d:=c+6 图图2-4 2-4 四

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

10、再现性，外界环境在程序的失去可再现性，外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。两次执行期间发生变化，失去原有的可重复特征。例如例如,有两个程序有两个程序A和和B,它们共享一个变量它们共享一个变量N(初始值为初始值为x)。A:N:=N+1 B:Print(N);N:=0;程序A和B并发执行，可出现以下三种情况:(1)N:=N+1在Print(N)和N:=0之前,此时得到的N值分别为x+1,x+1,0。(2)N:=N+1在Print(N)和N:=0之后,此时得到的N值分别为x,0,1。(3)N:=N+1在Print(N)和N:=0之间,此时得到的N值分别为x,x+1,0。202

11、2-12-3132022-12-3142.2.1 2.2.1 进程的定义和特征进程的定义和特征2.2.2 2.2.2 进程的基本状态及转换进程的基本状态及转换2.2.3 2.2.3 挂起状态和进程状态的转换挂起状态和进程状态的转换2.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构计算机科学与技术系计算机科学与技术系2022-12-3151.1.进程的定义进程的定义进程是进程实体的运行过程进程是进程实体的运行过程,是系统进行资源分配和调度是系统进行资源分配和调度的一个独立单位。的一个独立单位。2.2.进程实体的构成进程实体的构成(1)(1)程序程序(段段)：进程要进行的操作。进程要

12、进行的操作。(2)(2)数据段数据段：包括操作的数据和程序自己的变量。：包括操作的数据和程序自己的变量。(3)(3)进程控制块进程控制块PCB(Process Control Block)PCB(Process Control Block)：存放进程：存放进程标识符、进程运行的当前状态、程序和数据的地址、程序标识符、进程运行的当前状态、程序和数据的地址、程序运行时的运行时的CPUCPU环境等。环境等。2.2.1 2.2.1 进程的定义和特征进程的定义和特征 计算机科学与技术系计算机科学与技术系2022-12-3162.2.1 2.2.1 进程的定义和特征进程的定义和特征 2.2.进程的特征进程

13、的特征 动态性动态性：进程是一个动态的概念，实质上是程序的一次执行过程。进程是一个动态的概念，实质上是程序的一次执行过程。进程具有生命期：它因进程具有生命期：它因“创建创建”而产生，因而产生，因“调度调度”而执行，执行而执行，执行时还走走停停，因时还走走停停，因“撤消撤消”而灭亡。而灭亡。并发性并发性：多个进程实体同存于内存中：多个进程实体同存于内存中,且能在一段时间内同时运行且能在一段时间内同时运行,共享系统资源共享系统资源;引入进程实体的目的就是并发执行。引入进程实体的目的就是并发执行。独立性独立性：进程是一个能：进程是一个能独立运行独立运行的基本单位，也是系统进行资源分的基本单位，也是系

14、统进行资源分配和调度的基本单位。配和调度的基本单位。异步性异步性：各进程按各自独立的、不可预知的速度向前推进。：各进程按各自独立的、不可预知的速度向前推进。3.进程与程序的区别进程与程序的区别 进程是动态的，程序是静态的进程是动态的，程序是静态的：程序是有序代码的集合，它可以复制；进程是程序在数据集上的一次执行。进程是暂时的进程是暂时的,程序是永久的程序是永久的：进程是一个状态变化的过程，有它的撤销，程序可长久保存。进程具有结构特征进程具有结构特征：由程序段、数据段和进程控制块三者组成，而程序仅是指令的有序集合,是进程的组成部分之一。进程与程序的对应关系进程与程序的对应关系：通过多次执行，一个

15、程序可对应多个进程。2022-12-3172.2.1 2.2.1 进程的定义和特征进程的定义和特征 2022-12-3182.2.1 2.2.1 进程的定义和特征进程的定义和特征2.2.2 2.2.2 进程的基本状态及转换进程的基本状态及转换2.2.3 2.2.3 挂起状态和进程状态的转换（略）挂起状态和进程状态的转换（略）2.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构计算机科学与技术系计算机科学与技术系2022-12-3191.进程的三种基本状态进程的三种基本状态 就绪就绪(Ready)(Ready)状态：进程已获得除处理机外的所需资源，等待分配处状态：进程已获得除处理机外

16、的所需资源，等待分配处理机资源；只要分配理机资源；只要分配CPUCPU就可执行。就可执行。执行执行(Running)(Running)状态：处于就绪状态的进程一旦获得了处理机，进程状态：处于就绪状态的进程一旦获得了处理机，进程状态就处于执行状态。状态就处于执行状态。阻塞阻塞(Blocked)(Blocked)状态状态(“等待等待”或或“睡眠睡眠”)：由于进程等待某种事件：由于进程等待某种事件(如如I/OI/O操作或进程同步操作或进程同步)，在事件发生之前无法继续执行。该事件发，在事件发生之前无法继续执行。该事件发生前即使把处理机分配给该进程生前即使把处理机分配给该进程,也无法运行。如也无法运行

17、。如:请求请求I/OI/O操作，申操作，申请缓冲空间等。请缓冲空间等。2.2.2 2.2.2 进程的基本状态及转换进程的基本状态及转换 计算机科学与技术系计算机科学与技术系2022-12-320图图2-5 2-5 进程的三种基本状态及其转换进程的三种基本状态及其转换 1.1.时间片用完时间片用完2.2.有优先级高的进程到来有优先级高的进程到来终止终止2.进程的三种基本状态的转换进程的三种基本状态的转换3.创建状态和终止状态创建状态和终止状态 创建状态创建状态：当一个新进程刚刚建立,还未将其放入就绪队列时的状态，称为新状态。终止状态终止状态：当一个进程已经正常结束或异常结束，操作系统已将其从系统

18、队列中移出，但尚未撤消，这时称为终止状态。2022-12-321计算机科学与技术系计算机科学与技术系2022-12-322图图2-6 2-6 进程的五种基本状态及其转换进程的五种基本状态及其转换 释放释放2022-12-3232.2.1 2.2.1 进程的定义和特征进程的定义和特征2.2.2 2.2.2 进程的基本状态及转换进程的基本状态及转换2.2.3 2.2.3 挂起状态和进程状态的转换挂起状态和进程状态的转换2.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构计算机科学与技术系计算机科学与技术系2022-12-324 挂起操作的引入挂起操作的引入v终端用户的请求终端用户的请求

19、v父进程请求父进程请求v负荷调节的需要负荷调节的需要v操作系统的需要操作系统的需要2.2.3 2.2.3 挂起操作和进程状态的转换挂起操作和进程状态的转换图图2-7 2-7 具有挂起状态的进程状态图具有挂起状态的进程状态图 2022-12-3252.2.1 2.2.1 进程的定义和特征进程的定义和特征2.2.2 2.2.2 进程的基本状态及转换进程的基本状态及转换2.2.3 2.2.3 挂起状态和进程状态的转换挂起状态和进程状态的转换2.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构计算机科学与技术系计算机科学与技术系2022-12-3262.2.4 2.2.4 进程管理中的数据

20、结构进程管理中的数据结构 1.1.操作系统中用于管理控制的数据结构操作系统中用于管理控制的数据结构 对于每个资源和每个进程都设置了一个数据结构。对于每个资源和每个进程都设置了一个数据结构。资源信息表、进程信息表（称为资源信息表、进程信息表（称为PCBPCB）计算机科学与技术系计算机科学与技术系2022-12-3272.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构 2.2.进程控制块的作用进程控制块的作用 进程控制块的作用是使一个在多道程序环境下不能进程控制块的作用是使一个在多道程序环境下不能独立运行的程序独立运行的程序(含数据含数据)，成为一个能独立运行的基本，成为一个能独立运

21、行的基本单位，一个能与其它进程并发执行的进程。单位，一个能与其它进程并发执行的进程。或者说，或者说，OSOS是根据是根据PCBPCB来对并发执行的进程进行控制和管理的。来对并发执行的进程进行控制和管理的。记录了操作系统所需的记录了操作系统所需的,用于描述进程情况及控制进用于描述进程情况及控制进程运行所需的程运行所需的全部信息全部信息。PCBPCB是进程存在的唯一标志。是进程存在的唯一标志。计算机科学与技术系计算机科学与技术系2022-12-3282.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构 2.2.进程控制块的作用进程控制块的作用 具体作用：具体作用：作为独立运行基本单位的

22、标志作为独立运行基本单位的标志能实现间断性运行方式能实现间断性运行方式提供进程管理所需的信息提供进程管理所需的信息提供进程调度所需的信息提供进程调度所需的信息实现与其它进程的同步与通信实现与其它进程的同步与通信计算机科学与技术系计算机科学与技术系2022-12-3293.3.进程控制块中的信息进程控制块中的信息 进程标识符进程标识符 内部标识符和外部标识符。内部标识符和外部标识符。处理机状态处理机状态通用寄存器通用寄存器指令计数器指令计数器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-12-330图图2-11

24、PCB2-11 PCB链接队列示意图链接队列示意图 4.4.进程控制块的组织方式进程控制块的组织方式(1)(1)线性方式线性方式(2)(2)链接方式链接方式 (3)(3)索引方式索引方式计算机科学与技术系计算机科学与技术系2022-12-331图图2-12 2-12 按索引方式组织按索引方式组织PCB PCB 4.4.进程控制块的组织方式进程控制块的组织方式(1)(1)线性方式线性方式(2)(2)链接方式链接方式 (3)(3)索引方式索引方式内容概述2022-12-3322.1 2.1 前驱图和程序执行前驱图和程序执行 2.2 2.2 进程的描述进程的描述2.3 2.3 进程控制进程控制2.4

25、 2.4 进程同步进程同步2.5 2.5 经典进程的同步问题经典进程的同步问题2.6 2.6 进程通信进程通信2.7 2.7 线程的基本概念线程的基本概念2.8 2.8 线程的实现线程的实现计算机科学与技术系计算机科学与技术系2.3 进 程 控 制主要内容l 操作系统内核l 进程的创建l 进程的终止l 进程的阻塞与唤醒l 进程的挂起与激活计算机科学与技术系计算机科学与技术系操作系统内核l 问题：现代操作系统中通常将一些与硬件紧密相关的模块，问题：现代操作系统中通常将一些与硬件紧密相关的模块，各种常用的设备的驱动程序以及运行频率较高的模块都安各种常用的设备的驱动程序以及运行频率较高的模块都安排在

26、紧靠硬件的软件层次中，将它们常驻内存，即排在紧靠硬件的软件层次中，将它们常驻内存，即OS内内核核。l 为什么这样做？为什么这样做？l 便于对这些软件进行保护便于对这些软件进行保护l 提高提高OS的运行效率的运行效率计算机科学与技术系计算机科学与技术系操作系统内核1 1.处理机执行状态：系统处理机执行状态：系统态和用户态态和用户态l 处理机的执行状态分系统系统态和用户态两种:l 系统态(管态、核心态)：有较高特权，能执行一切指令，访问所有寄存器和存储区。l 用户态(目态)：有较低特权，能执行规定指令，访问指定寄存器和存储区。l 用户程序运行在用户态，不能执行用户程序运行在用户态，不能执行OS指令

27、及区域。指令及区域。l OS内核运行在系统态，进程控制是由内核运行在系统态，进程控制是由OS内核实现的。内核实现的。计算机科学与技术系计算机科学与技术系操作系统内核操作系统内核2.2.支撑功能支撑功能l 中断处理中断处理l 时钟管理时钟管理l 原语操作原语操作 由若干条指令构成的“原子操作”过程，在执行期间不可中断，作为一个整体而不可分割。原子操作：一个操作中的所有动作要么全做，要么全不做。原子操作在管态下执行，常驻内存。原语的作用是为了实现进程的通信和控制。思考：进程控制有哪些原语操作？思考：进程控制有哪些原语操作？1.创建原语创建原语2.撤消原语撤消原语3.阻塞原语阻塞原语4.唤醒原语唤醒

28、原语5.挂起原语挂起原语6.激活原语激活原语计算机科学与技术系计算机科学与技术系操作系统内核操作系统内核3.3.资源管理功能资源管理功能l 进程管理进程管理l 存储器管理存储器管理l 设备管理设备管理计算机科学与技术系计算机科学与技术系2022-12-338进程的创建进程的创建图图2-13 2-13 进程树进程树 1.1.进程的层次结构进程的层次结构l 父进程与子进程父进程与子进程l UNIXUNIX中进程家族中进程家族l WindowsWindows中进程句柄中进程句柄 2.2.进程图进程图(Process Graph)(Process Graph)l 进程图是用于描述一个进程的家族进程图是

29、用于描述一个进程的家族关系的有向树，树中的结点表示进关系的有向树，树中的结点表示进程。程。l 子进程可以继承父进程的资源。子进程可以继承父进程的资源。l 撤消父进程时必须同时撤消子进程撤消父进程时必须同时撤消子进程计算机科学与技术系计算机科学与技术系2022-12-3393.3.引起创建进程的事件引起创建进程的事件l用户登录用户登录l作业调度作业调度l提供服务提供服务l应用请求应用请求 进程的创建进程的创建计算机科学与技术系计算机科学与技术系2022-12-3404.4.进程的创建进程的创建l 申请空白申请空白PCB PCB l 为新进程分配资源为新进程分配资源 l 初始化进程控制块初始化进程

30、控制块 l 将新进程插入就绪队列将新进程插入就绪队列进程的创建进程的创建计算机科学与技术系计算机科学与技术系2022-12-341进程进程的终止的终止 1.1.引起进程终止的事件引起进程终止的事件l 正常结束正常结束l 异常结束异常结束l 外界干预外界干预计算机科学与技术系计算机科学与技术系2022-12-3422.2.进程的终止过程进程的终止过程 (1)(1)从从PCBPCB集合中检索出该进程的集合中检索出该进程的PCB,PCB,读出该进程的状态。读出该进程的状态。(2)(2)若被终止进程正处于执行状态若被终止进程正处于执行状态,应立即终止该进程的执行。应立即终止该进程的执行。(3)(3)若

31、该进程还有子孙进程若该进程还有子孙进程,应将其所有子孙进程予以终止。应将其所有子孙进程予以终止。(4)(4)将被终止进程所拥有的全部资源将被终止进程所拥有的全部资源,归还给其父进程归还给其父进程,或者归还给系或者归还给系统。统。(5)(5)将被终止进程将被终止进程(它的它的PCB)PCB)从所在队列从所在队列(或链表或链表)中移出中移出,等待其他程序等待其他程序来搜集信息。来搜集信息。进程进程的终止的终止 计算机科学与技术系计算机科学与技术系2022-12-343进程进程的阻塞与唤醒的阻塞与唤醒1.1.引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 l 请求系统服务请求系统服务 l 启动某种

32、操作启动某种操作 l 新数据尚未到达新数据尚未到达 l 无新工作可做无新工作可做计算机科学与技术系计算机科学与技术系2022-12-344 2.2.进程阻塞过程进程阻塞过程l 进程调用阻塞原语进程调用阻塞原语block()block()把自己阻塞，立即停止执把自己阻塞，立即停止执行，把进程控制块中的现行状态由行，把进程控制块中的现行状态由“执行执行”改为阻塞，改为阻塞，并将并将PCBPCB插入阻塞队列。插入阻塞队列。l 将本进程插入到具有相同事件的阻塞将本进程插入到具有相同事件的阻塞(等待等待)队列。队列。l 调度程序进行重新调度调度程序进行重新调度,将处理机分配给另一就绪进将处理机分配给另一

33、就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状程，并进行切换，亦即，保留被阻塞进程的处理机状态态(在在PCBPCB中中)，再按新进程的，再按新进程的PCBPCB中的处理机状态设置中的处理机状态设置CPUCPU的环境。的环境。进程的阻塞与唤醒进程的阻塞与唤醒计算机科学与技术系计算机科学与技术系2022-12-345 3.3.进程唤醒过程进程唤醒过程l 调用唤醒原语调用唤醒原语wakeup()wakeup()将等待该事件的进程唤醒。将等待该事件的进程唤醒。l 唤醒原语执行的过程是唤醒原语执行的过程是u 把被阻塞的进程从等待该事件的阻塞队列中移出把被阻塞的进程从等待该事件的阻塞队列中移出u 将

34、其将其PCBPCB中的现行状态由阻塞改为就绪中的现行状态由阻塞改为就绪u 将该将该PCBPCB插入到就绪队列中插入到就绪队列中进程进程的阻塞与唤醒的阻塞与唤醒计算机科学与技术系计算机科学与技术系2022-12-346进程进程的挂起与激活的挂起与激活 1.1.进程的挂起进程的挂起l系统将利用挂起原语系统将利用挂起原语suspend()suspend()将指定进程或处于阻塞状态的将指定进程或处于阻塞状态的进程挂起。进程挂起。lsuspend()suspend()原语的执行过程原语的执行过程u 首先检查被挂起进程的状态，若处于首先检查被挂起进程的状态，若处于活动就绪状态活动就绪状态，便将其，便将其改

35、为改为静止就绪静止就绪；对于；对于活动阻塞状态活动阻塞状态的进程，则将之改为的进程，则将之改为静止静止阻塞阻塞。u 把该进程的把该进程的PCBPCB复制到某指定的内存区域。复制到某指定的内存区域。u 若被挂起的进程正在执行若被挂起的进程正在执行,则转向调度程序重新调度。则转向调度程序重新调度。计算机科学与技术系计算机科学与技术系2022-12-347 2.2.进程的激活过程进程的激活过程l系统将利用激活原语系统将利用激活原语active()active()将指定进程激活。将指定进程激活。lactive()active()原语执行过程原语执行过程u 将进程从外存调入内存，检查该进程的现行状态，若

36、是静止将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，将之改为活动就绪；若为静止阻塞便将之改为活动阻就绪，将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。塞。u 假如采用的是抢占调度策略，则每当有新进程进入就绪队列假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分

37、配给刚被激活的进程。把处理机分配给刚被激活的进程。进程进程的挂起与激活的挂起与激活 计算机科学与技术系计算机科学与技术系2022-12-3481.1.引起进程创建的主要事件？引起进程创建的主要事件？2.2.在创建一个进程时所需要完成的主要工作是什么？在创建一个进程时所需要完成的主要工作是什么？3.3.在撤消一个进程时所要完成的主要工作是什么？在撤消一个进程时所要完成的主要工作是什么？课后思考题课后思考题 内容概述2022-12-3492.1 前驱图和程序执行前驱图和程序执行 2.2 进程的描述进程的描述2.3 进程控制进程控制2.4 进程同步进程同步2.5 经典进程的同步问题经典进程的同步问题

38、2.6 进程通信进程通信2.7 线程的基本概念线程的基本概念2.8 线程的实现线程的实现2.4 2.4 进程同步进程同步 进程同步的主要任务是对多个相关进程在执行次序上进行协调执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源共享资源和相互合作相互合作，从而使程序的执行具有可再现性。2.4.1 2.4.1 进程同步的基本概念进程同步的基本概念2.4.2 2.4.2 硬件同步机制硬件同步机制2.4.3 2.4.3 信号量机制信号量机制2.4.4 2.4.4 信号量的应用信号量的应用2.4.5 2.4.5 管程机制管程机制2022-12-350计算机科学与技术系计算机科学与技术系2022

39、-12-3512.4.1 2.4.1 进程同步的基本概进程同步的基本概念念1.两种形式的制约关系两种形式的制约关系(1)(1)间接相互制约关系间接相互制约关系 源于资源共享源于资源共享。如。如A A、B B共享打印机，若共享打印机，若A A申请打印时，申请打印时，打印机已分配给打印机已分配给B B，则，则A A只能阻塞，等只能阻塞，等B B释放后再改为就绪，释放后再改为就绪，又称为又称为“互斥互斥”。(2)(2)直接相互制约关系直接相互制约关系 源于进程之间的合作关系源于进程之间的合作关系。如进程。如进程A A向向B B提供数据，当提供数据，当输入缓冲空时，输入缓冲空时，B B不能得到数据而阻

40、塞；反之当缓冲满时，不能得到数据而阻塞；反之当缓冲满时，A A无法写入而阻塞，又称为无法写入而阻塞，又称为“同步同步”。2.临界资源临界资源定义定义:在一段时间内只允许一个进程访问的资源。在一段时间内只允许一个进程访问的资源。例如:打印机、磁带机、卡片输入机、变量、表格、数据、指针、数组等。进程之间采取互斥方式实现对这些资源的共享。2022-12-352例子：例子：生产者生产者-消费者消费者(producer-consumer)(producer-consumer)问题问题是一个著名的进是一个著名的进程同步问题。程同步问题。有一群生产者进程在生产产品，提供给消费者进程去消费。有一群生产者进程在

41、生产产品，提供给消费者进程去消费。不能向满缓冲区投放产品，不能从空缓冲区中取产品。不能向满缓冲区投放产品，不能从空缓冲区中取产品。2.4.1 2.4.1 进程同步的基本概念进程同步的基本概念计算机科学与技术系计算机科学与技术系2022-12-353 一个数组缓冲池，有一个数组缓冲池，有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-1 ninout 计算机

42、科学与技术系计算机科学与技术系2022-12-354producer:repeat 生产者进程生产者进程 produce an item in nextp;/生产一个产品生产一个产品 while counter=n do no-op;bufferin =nextp;/将产品放入缓冲区内将产品放入缓冲区内 in =in+1 mod n;counter =counter+1;/缓冲池中产品数加一缓冲池中产品数加一 until false;consumer:repeat 消费者进程消费者进程 while counter=0 do no-op;nextc =bufferout;/从缓冲区中消费产品从缓

43、冲区中消费产品 out =(out+1)mod n;counter =counter-1;/缓冲池中产品数减一缓冲池中产品数减一 consumer the item in nextc;/消费一个产品消费一个产品 until false;计算机科学与技术系计算机科学与技术系2022-12-355 虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言机器语言实现时，常可用下面的形式描述：register1=count

44、er;register2=counter;register1=register1+1;register2=register2-1;counter=register1;counter=register2;计算机科学与技术系计算机科学与技术系2022-12-356 假设：counter的当前值是5。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句，则最后共享变量counter的值仍为5；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，counter值也还是5，但是，如果按下述顺序执行，counter值是4。由于并发执行而失去封闭性。r

45、egister1=counter;(register1=5)register1=register1+1;(register1=6)register2=counter;(register2=5)register2=register2-1;(register2=4)counter=register1;(counter=6)counter=register2;(counter=4)共享资源的访问互斥3.临界区 不论是硬件临界资源硬件临界资源还是软件临界资源软件临界资源，多个进程必须互斥互斥地对它进行访问。在每个进程中访问临界资源的那段代码称为临界区。在每个进程中访问临界资源的那段代码称为临界区。每个

46、进程进入临界区之前应先对欲访问的临界资源进行检查，看是否正在被访问。如果此刻该临界资源未被访问，该进程可进入临界区,并设置它正在被访问的标志，在临界区之前执行的这段代码称为进入进入区区。在临界区后面也要加上一段代码，用于将临界区被访问的资源恢复为未被访问的标志，称为退出区退出区。2022-12-357计算机科学与技术系计算机科学与技术系2022-12-358可把一个可把一个访问临界资源访问临界资源的循环进程描述如下的循环进程描述如下:repeat critical section;临界区临界区 remainder section;剩余区剩余区 until false;entry section

47、exit section 进入区进入区 退出区退出区 计算机科学与技术系计算机科学与技术系2022-12-3594.4.同步机制应遵循的规则同步机制应遵循的规则(1)(1)空闲让进：空闲让进：当无进程处于临界区时当无进程处于临界区时,应允许一个进程进应允许一个进程进入临界区入临界区,以有效利用临界资源。以有效利用临界资源。(2)(2)忙则等待忙则等待：当有进程进入临界区时当有进程进入临界区时,其他进程必须等待。其他进程必须等待。(3)(3)有限等待：有限等待：对要求访问临界资源的进程对要求访问临界资源的进程,应保证在有限应保证在有限时间内进入自己的临界区时间内进入自己的临界区,防止防止“死等死

48、等”。(4)(4)让权等待：让权等待：当进程不能进入其临界区时当进程不能进入其临界区时,应立即释放处应立即释放处理机理机,防止防止“忙等忙等”,不能一直用语句判断能不能进不能一直用语句判断能不能进,占占用处理机。用处理机。2.4.2 硬件同步机制硬件同步机制 采用软件方法实现进程互斥使用临界资源是很困采用软件方法实现进程互斥使用临界资源是很困难的，它们通常能实现两个进程的互斥，很难控难的，它们通常能实现两个进程的互斥，很难控制多个进程的互斥。制多个进程的互斥。算法设计需要非常小心，否则可能出现死锁，或算法设计需要非常小心，否则可能出现死锁，或互斥失败等严重问题。互斥失败等严重问题。软件方法始终

49、不能解决软件方法始终不能解决“忙等忙等”现象，降低系统现象，降低系统效率。效率。硬件方法包括硬件方法包括屏蔽中断屏蔽中断和和专用机器指令专用机器指令。2.4.2 硬件同步机制硬件同步机制2.4.2 硬件同步机制硬件同步机制2.4.2 硬件同步机制硬件同步机制2.4.2 硬件同步机制硬件同步机制2.4.2 硬件同步机制硬件同步机制 TestAndSet指令：这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真功能是读出指定标志后把该标志设置为真。指令的功能描述为：Boolean TestAndSet(Boolean*lock)Boolean old；old=*l

50、ock；*lock=true；return old；while TestAndSet(&lock)；进程的临界区代码；进程的临界区代码；lock=false；进程的其他代码；进程的其他代码；2.4.2 硬件同步机制硬件同步机制 Swap指令：该指令的功能是交换两个字节的内容指令：该指令的功能是交换两个字节的内容。其功能描述如下。1.Swap(boolean*a,boolean*b)2.boolean temp;3.Temp=*a;4.*a=*b;5.*b=temp;6.2.4.2 硬件同步机制硬件同步机制应为每个临界资源设置了一个共享布尔变量lock，初值为false；在每个进程中再设置一个局