chapter2进程的描述与控制概述课件

计算机科学与技术系计算机科学与技术系2024/5/41内容概述内容概述进程管理的主要功能主要功能是把处理机分配给进程,并对处理器运行进行有效地控制和管理,以及协调各个进程之间的相互关系。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 线程的实现线程的实现计算机科学与技术系计算机科学与技术系2024/5/422.1 2.1 前驱图和程序执行前驱图和程序执行2.1.1 2.1.1 前趋图前趋图2.1.2 2.1.2 程序顺序执行程序顺序执行2.1.3 2.1.3 程序并发执行程序并发执行计算机科学与技术系计算机科学与技术系2024/5/432.1.1 2.1.1 前趋图前趋图前趋图是一个有向前趋图是一个有向无循环无循环图，记为图，记为DAG。用于描述进程之间。用于描述进程之间执行的前后关系。执行的前后关系。图中的每个图中的每个结点结点可用于描述一个程序段或进程，乃至一条语可用于描述一个程序段或进程，乃至一条语句；结点间的句；结点间的有向边有向边则用于表示两个结点之间存在的则用于表示两个结点之间存在的偏序偏序或或前前趋关系趋关系“”。=(Pi,Pj)|Pi must complete before Pj may start,如果如果(Pi,Pj),可写成可写成PiPj：称称Pi是是Pj的的直接前趋直接前趋，而称，而称Pj是是Pi的的直接后继直接后继。把没有前趋的结点称为把没有前趋的结点称为初始结点初始结点(Initial Node)，把没有后继的，把没有后继的结点称为结点称为终止结点终止结点(Final Node)。计算机科学与技术系计算机科学与技术系2024/5/44 每个结点还具有一个每个结点还具有一个重量重量(Weight)，用于表示该结点，用于表示该结点所含有的所含有的程序量程序量或结点的或结点的执行时间执行时间。图图2-1 2-1 前趋图前趋图 直接前趋直接前趋直接后继直接后继初始结点初始结点终止结点终止结点计算机科学与技术系计算机科学与技术系2024/5/45对于图对于图 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)应当注意应当注意,前趋图中必须前趋图中必须不存在不存在循环循环,但在图但在图2-1(b)中却有着下述的前趋关中却有着下述的前趋关系系:S2S3,S3S2 2024/5/462.1 2.1 进程的基本概念进程的基本概念2.1.1 2.1.1 前趋图前趋图2.1.2 2.1.2 程序顺序执行程序顺序执行2.1.3 2.1.3 程序并发执行程序并发执行计算机科学与技术系计算机科学与技术系2024/5/47图图2-2 2-2 程序的顺序执行程序的顺序执行 1.程序的顺序执行程序的顺序执行仅当前一操作仅当前一操作(程序段程序段)执行完后，才能执行后继操作。执行完后，才能执行后继操作。例如例如，在进行计算时，总须先输入用户的程序和数据，然后进行计在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。算，最后才能打印计算结果。S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;2.1.2 2.1.2 程序顺序执行程序顺序执行计算机科学与技术系计算机科学与技术系2024/5/482.2.程序顺序执行时的特征程序顺序执行时的特征(1)(1)顺序性顺序性:处理机的操作严格按照程序所规定的顺序执行处理机的操作严格按照程序所规定的顺序执行,只有当上一个操作完成后只有当上一个操作完成后,下一个操作才能执行。下一个操作才能执行。(2)(2)封闭性封闭性:程序运行在一个封闭的环境中程序运行在一个封闭的环境中,即程序运行时独即程序运行时独占系统的全部资源占系统的全部资源,这些资源的状态只能因程序的执行而改这些资源的状态只能因程序的执行而改变变,不受任何外界因素的影响。不受任何外界因素的影响。(3)(3)可再现性可再现性:由于程序顺序执行的封闭性由于程序顺序执行的封闭性,只要程序顺序执只要程序顺序执行的行的初始条件和环境相同初始条件和环境相同,则不论何时执行则不论何时执行,也不论程序执也不论程序执行期间是否存在停顿行期间是否存在停顿,程序所得的程序所得的结果结果也也相同相同。结论结论:正由于程序顺序执行的特点正由于程序顺序执行的特点,程序员可以检测和重现程序员可以检测和重现程序的错误程序的错误,可以调试和校正程序。可以调试和校正程序。2024/5/492.1 2.1 进程的基本概念进程的基本概念2.1.1 2.1.1 前趋图前趋图2.1.2 2.1.2 程序顺序执行程序顺序执行2.1.3 2.1.3 程序并发执行程序并发执行计算机科学与技术系计算机科学与技术系2024/5/4102.1.3 2.1.3 程序并发执行程序并发执行1.1.程序的并发执行程序的并发执行 图图2-3 2-3 并发执行时的前趋图并发执行时的前趋图 并发并发输入程序输入程序I I计算程序计算程序C C输出程序输出程序P P计算机科学与技术系计算机科学与技术系2024/5/411下述四条语句的程序段下述四条语句的程序段:S1:a:=x+2 S2:b:=y+4 S3:c:=a+b S4:d:=c+6 图图2-4 2-4 四条语句的前趋关系四条语句的前趋关系什么样的程序可以并发执行？什么样的程序可以并发执行？计算机科学与技术系计算机科学与技术系2024/5/4122.2.程序并发执行时的特征程序并发执行时的特征 (1)(1)间断性间断性 相互制约导致并发程序具有相互制约导致并发程序具有“执行执行-暂停暂停-执行执行”的间断性活动规律。的间断性活动规律。(2)(2)失去封闭性失去封闭性 系统中多道程序系统中多道程序共享共享资源，资源的状态由多个程资源，资源的状态由多个程序来改变，必然失去了程序的封闭性。序来改变，必然失去了程序的封闭性。(3)(3)不可再现性不可再现性 失去封闭性失去封闭性 失去可再现性，外界环境在程序的失去可再现性，外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。两次执行期间发生变化，失去原有的可重复特征。例如例如,有两个程序有两个程序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。2024/5/4132024/5/4142.2 2.2 进程的描述进程的描述2.2.1 2.2.1 进程的定义和特征进程的定义和特征2.2.2 2.2.2 进程的基本状态及转换进程的基本状态及转换2.2.3 2.2.3 挂起状态和进程状态的转换挂起状态和进程状态的转换2.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构计算机科学与技术系计算机科学与技术系2024/5/4151.1.进程的定义进程的定义进进程程是是进进程程实实体体的的运运行行过过程程,是是系系统统进进行行资资源源分分配配和和调调度度的一个独立单位。的一个独立单位。2.2.进程实体的构成进程实体的构成(1)(1)程序程序(段段)：进程要进行的操作。进程要进行的操作。(2)(2)数据段数据段：包括操作的数据和程序自己的变量。：包括操作的数据和程序自己的变量。(3)(3)进程控制块进程控制块PCB(Process Control Block)PCB(Process Control Block)：存放进程：存放进程标识符、进程运行的当前状态、程序和数据的地址、程序标识符、进程运行的当前状态、程序和数据的地址、程序运行时的运行时的CPUCPU环境等。环境等。2.2.1 2.2.1 进程的定义和特征进程的定义和特征 计算机科学与技术系计算机科学与技术系2024/5/4162.2.1 2.2.1 进程的定义和特征进程的定义和特征 2.2.进程的特征进程的特征 动态性动态性：进程是一个动态的概念，实质上是程序的一次执行过程。进程是一个动态的概念，实质上是程序的一次执行过程。进程具有生命期：它因进程具有生命期：它因“创建创建”而产生，因而产生，因“调度调度”而执行，执行而执行，执行时还走走停停，因时还走走停停，因“撤消撤消”而灭亡。而灭亡。并发性并发性：多个进程实体同存于内存中：多个进程实体同存于内存中,且能在一段时间内同时运行且能在一段时间内同时运行,共享系统资源共享系统资源;引入进程实体的目的就是并发执行。引入进程实体的目的就是并发执行。独立性独立性：进程是一个能：进程是一个能独立运行独立运行的基本单位，也是系统进行资源分的基本单位，也是系统进行资源分配和调度的基本单位。配和调度的基本单位。异步性异步性：各进程按各自独立的、不可预知的速度向前推进。：各进程按各自独立的、不可预知的速度向前推进。3.进程与程序的区别进程与程序的区别进程是动态的，程序是静态的进程是动态的，程序是静态的：程序是有序代码的集合，它可以复制；进程是程序在数据集上的一次执行。进程是暂时的进程是暂时的,程序是永久的程序是永久的：进程是一个状态变化的过程，有它的撤销，程序可长久保存。进程具有结构特征进程具有结构特征：由程序段、数据段和进程控制块三者组成，而程序仅是指令的有序集合,是进程的组成部分之一。进程与程序的对应关系进程与程序的对应关系：通过多次执行，一个程序可对应多个进程。2024/5/4172.2.1 2.2.1 进程的定义和特征进程的定义和特征 2024/5/4182.2 2.2 进程的描述进程的描述2.2.1 2.2.1 进程的定义和特征进程的定义和特征2.2.2 2.2.2 进程的基本状态及转换进程的基本状态及转换2.2.3 2.2.3 挂起状态和进程状态的转换（略）挂起状态和进程状态的转换（略）2.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构计算机科学与技术系计算机科学与技术系2024/5/4191.进程的三种基本状态进程的三种基本状态就绪就绪(Ready)(Ready)状态：进程已获得除处理机外的所需资源，等待分配处理状态：进程已获得除处理机外的所需资源，等待分配处理机资源；只要分配机资源；只要分配CPUCPU就可执行。就可执行。执行执行(Running)(Running)状态：处于就绪状态的进程一旦获得了处理机，进程状状态：处于就绪状态的进程一旦获得了处理机，进程状态就处于执行状态。态就处于执行状态。阻塞阻塞(Blocked)(Blocked)状态状态(“等待等待”或或“睡眠睡眠”)：由于进程等待某种事件：由于进程等待某种事件(如如I/OI/O操作或进程同步操作或进程同步)，在事件发生之前无法继续执行。该事件发生，在事件发生之前无法继续执行。该事件发生前即使把处理机分配给该进程前即使把处理机分配给该进程,也无法运行。如也无法运行。如:请求请求I/OI/O操作，申请缓操作，申请缓冲空间等。冲空间等。2.2.2 2.2.2 进程的基本状态及转换进程的基本状态及转换 计算机科学与技术系计算机科学与技术系2024/5/420图图2-5 2-5 进程的三种基本状态及其转换进程的三种基本状态及其转换 1.1.时间片用完时间片用完2.2.有优先级高的进程到来有优先级高的进程到来终止终止2.进程的三种基本状态的转换进程的三种基本状态的转换3.创建状态和终止状态创建状态和终止状态 创建状态创建状态：当一个新进程刚刚建立,还未将其放入就绪队列时的状态，称为新状态。终止状态终止状态：当一个进程已经正常结束或异常结束，操作系统已将其从系统队列中移出，但尚未撤消，这时称为终止状态。2024/5/421计算机科学与技术系计算机科学与技术系2024/5/422图图2-6 2-6 进程的五种基本状态及其转换进程的五种基本状态及其转换 释放释放2024/5/4232.2 2.2 进程的描述进程的描述2.2.1 2.2.1 进程的定义和特征进程的定义和特征2.2.2 2.2.2 进程的基本状态及转换进程的基本状态及转换2.2.3 2.2.3 挂起状态和进程状态的转换挂起状态和进程状态的转换2.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构计算机科学与技术系计算机科学与技术系2024/5/424挂起操作的引入挂起操作的引入v终端用户的请求终端用户的请求v父进程请求父进程请求v负荷调节的需要负荷调节的需要v操作系统的需要操作系统的需要2.2.3 2.2.3 挂起操作和进程状态的转换挂起操作和进程状态的转换图图2-7 2-7 具有挂起状态的进程状态图具有挂起状态的进程状态图 2024/5/4252.2 2.2 进程的描述进程的描述2.2.1 2.2.1 进程的定义和特征进程的定义和特征2.2.2 2.2.2 进程的基本状态及转换进程的基本状态及转换2.2.3 2.2.3 挂起状态和进程状态的转换挂起状态和进程状态的转换2.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构计算机科学与技术系计算机科学与技术系2024/5/4262.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构 1.1.操作系统中用于管理控制的数据结构操作系统中用于管理控制的数据结构 对于每个资源和每个进程都设置了一个数据结构。对于每个资源和每个进程都设置了一个数据结构。资源信息表、进程信息表（称为资源信息表、进程信息表（称为PCBPCB）计算机科学与技术系计算机科学与技术系2024/5/4272.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构 2.2.进程控制块的作用进程控制块的作用 进进程程控控制制块块的的作作用用是是使使一一个个在在多多道道程程序序环环境境下下不不能能独独立立运运行行的的程程序序(含含数数据据)，成成为为一一个个能能独独立立运运行行的的基基本本单单位位，一一个个能能与与其其它它进进程程并并发发执执行行的的进进程程。或或者者说说，OSOS是根据是根据PCBPCB来对并发执行的进程进行控制和管理的。来对并发执行的进程进行控制和管理的。记记录录了了操操作作系系统统所所需需的的,用用于于描描述述进进程程情情况况及及控控制制进进程运行所需的程运行所需的全部信息全部信息。PCBPCB是进程存在的唯一标志。是进程存在的唯一标志。计算机科学与技术系计算机科学与技术系2024/5/4282.2.4 2.2.4 进程管理中的数据结构进程管理中的数据结构 2.2.进程控制块的作用进程控制块的作用 具体作用：具体作用：作为独立运行基本单位的标志作为独立运行基本单位的标志能实现间断性运行方式能实现间断性运行方式提供进程管理所需的信息提供进程管理所需的信息提供进程调度所需的信息提供进程调度所需的信息实现与其它进程的同步与通信实现与其它进程的同步与通信计算机科学与技术系计算机科学与技术系2024/5/4293.3.进程控制块中的信息进程控制块中的信息 进程标识符进程标识符 内部标识符和外部标识符。内部标识符和外部标识符。处理机状态处理机状态通用寄存器通用寄存器指令计数器指令计数器PC程序状态字程序状态字PSW用户栈指针用户栈指针 进程调度信息进程调度信息进程状态进程状态进程优先级进程优先级进程调度所需的其它信息进程调度所需的其它信息事件事件进程控制信息进程控制信息程序和数据的地址程序和数据的地址进程同步和通信机制进程同步和通信机制资源清单资源清单链接指针链接指针struct pcb int id;/进程序号进程序号 int ra;/所需资源所需资源A的数量的数量 int rb;/所需资源所需资源B的数量的数量 int rc;/所需资源所需资源C的数量的数量 int ntime;/所需的时间片个数所需的时间片个数 int rtime;/已经运行的时间片个数已经运行的时间片个数 char state;/进程状态进程状态 struct pcb*next;计算机科学与技术系计算机科学与技术系2024/5/430图图2-11 PCB2-11 PCB链接队列示意图链接队列示意图 4.4.进程控制块的组织方式进程控制块的组织方式(1)(1)线性方式线性方式(2)(2)链接方式链接方式 (3)(3)索引方式索引方式计算机科学与技术系计算机科学与技术系2024/5/431图图2-12 2-12 按索引方式组织按索引方式组织PCB PCB 4.4.进程控制块的组织方式进程控制块的组织方式(1)(1)线性方式线性方式(2)(2)链接方式链接方式 (3)(3)索引方式索引方式内容概述2024/5/4322.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 线程的实现线程的实现计算机科学与技术系计算机科学与技术系2.3 进 程 控 制主要内容l操作系统内核l进程的创建l进程的终止l进程的阻塞与唤醒l进程的挂起与激活计算机科学与技术系计算机科学与技术系操作系统内核l问问题题：现现代代操操作作系系统统中中通通常常将将一一些些与与硬硬件件紧紧密密相相关关的的模模块块，各各种种常常用用的的设设备备的的驱驱动动程程序序以以及及运运行行频频率率较较高高的的模模块块都都安安排排在在紧紧靠靠硬硬件件的的软软件件层层次次中中，将将它它们们常常驻驻内内存存，即即OS内内核核。l为什么这样做？为什么这样做？l便于对这些软件进行保护便于对这些软件进行保护l提高提高OS的运行效率的运行效率计算机科学与技术系计算机科学与技术系操作系统内核1 1.处理机执行状态：系统处理机执行状态：系统态和用户态态和用户态l处理机的执行状态分系统系统态和用户态两种:l系统态(管态、核心态)：有较高特权，能执行一切指令，访问所有寄存器和存储区。l用户态(目态)：有较低特权，能执行规定指令，访问指定寄存器和存储区。l用户程序运行在用户态，不能执行用户程序运行在用户态，不能执行OS指令及区域。指令及区域。lOS内核运行在系统态，进程控制是由内核运行在系统态，进程控制是由OS内核实现的。内核实现的。计算机科学与技术系计算机科学与技术系操作系统内核操作系统内核2.2.支撑功能支撑功能l 中断处理中断处理l 时钟管理时钟管理l 原语操作原语操作由若干条指令构成的“原子操作”过程，在执行期间不可中断，作为一个整体而不可分割。原子操作：一个操作中的所有动作要么全做，要么全不做。原子操作在管态下执行，常驻内存。原语的作用是为了实现进程的通信和控制。思考：进程控制有哪些原语操作？思考：进程控制有哪些原语操作？1.创建原语创建原语2.撤消原语撤消原语3.阻塞原语阻塞原语4.唤醒原语唤醒原语5.挂起原语挂起原语6.激活原语激活原语计算机科学与技术系计算机科学与技术系操作系统内核操作系统内核3.3.资源管理功能资源管理功能l进程管理进程管理l存储器管理存储器管理l 设备管理设备管理计算机科学与技术系计算机科学与技术系2024/5/438进程的创建进程的创建图图2-13 2-13 进程树进程树 1.1.进程的层次结构进程的层次结构l父进程与子进程父进程与子进程lUNIXUNIX中进程家族中进程家族lWindowsWindows中进程句柄中进程句柄 2.2.进程图进程图(Process Graph)(Process Graph)l进程图是用于描述一个进程的家族进程图是用于描述一个进程的家族关系的有向树，树中的结点表示进关系的有向树，树中的结点表示进程。程。l子进程可以继承父进程的资源。子进程可以继承父进程的资源。l撤消父进程时必须同时撤消子进程撤消父进程时必须同时撤消子进程计算机科学与技术系计算机科学与技术系2024/5/4393.3.引起创建进程的事件引起创建进程的事件l用户登录用户登录l作业调度作业调度l提供服务提供服务l应用请求应用请求 进程的创建进程的创建计算机科学与技术系计算机科学与技术系2024/5/4404.4.进程的创建进程的创建l申请空白申请空白PCB PCB l为新进程分配资源为新进程分配资源 l初始化进程控制块初始化进程控制块 l将新进程插入就绪队列将新进程插入就绪队列进程的创建进程的创建计算机科学与技术系计算机科学与技术系2024/5/441进程进程的终止的终止 1.1.引起进程终止的事件引起进程终止的事件l正常结束正常结束l异常结束异常结束l外界干预外界干预计算机科学与技术系计算机科学与技术系2024/5/4422.2.进程的终止过程进程的终止过程 (1)(1)从从PCBPCB集合中检索出该进程的集合中检索出该进程的PCB,PCB,读出该进程的状态。读出该进程的状态。(2)(2)若被终止进程正处于执行状态若被终止进程正处于执行状态,应立即终止该进程的执行。应立即终止该进程的执行。(3)(3)若该进程还有子孙进程若该进程还有子孙进程,应将其所有子孙进程予以终止。应将其所有子孙进程予以终止。(4)(4)将将被被终终止止进进程程所所拥拥有有的的全全部部资资源源,归归还还给给其其父父进进程程,或或者者归归还还给给系系统。统。(5)(5)将将被被终终止止进进程程(它它的的PCB)PCB)从从所所在在队队列列(或或链链表表)中中移移出出,等等待待其其他他程程序序来搜集信息。来搜集信息。进程进程的终止的终止 计算机科学与技术系计算机科学与技术系2024/5/443进程进程的阻塞与唤醒的阻塞与唤醒1.1.引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 l请求系统服务请求系统服务 l启动某种操作启动某种操作 l新数据尚未到达新数据尚未到达 l无新工作可做无新工作可做计算机科学与技术系计算机科学与技术系2024/5/444 2.2.进程阻塞过程进程阻塞过程l进程调用阻塞原语进程调用阻塞原语block()block()把自己阻塞，立即停止执把自己阻塞，立即停止执行，把进程控制块中的现行状态由行，把进程控制块中的现行状态由“执行执行”改为阻塞，改为阻塞，并将并将PCBPCB插入阻塞队列。插入阻塞队列。l将本进程插入到具有相同事件的阻塞将本进程插入到具有相同事件的阻塞(等待等待)队列。队列。l调度程序进行重新调度调度程序进行重新调度,将处理机分配给另一就绪进将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状程，并进行切换，亦即，保留被阻塞进程的处理机状态态(在在PCBPCB中中)，再按新进程的，再按新进程的PCBPCB中的处理机状态设置中的处理机状态设置CPUCPU的环境。的环境。进程的阻塞与唤醒进程的阻塞与唤醒计算机科学与技术系计算机科学与技术系2024/5/445 3.3.进程唤醒过程进程唤醒过程l调用唤醒原语调用唤醒原语wakeup()wakeup()将等待该事件的进程唤醒。将等待该事件的进程唤醒。l唤醒原语执行的过程是唤醒原语执行的过程是u把被阻塞的进程从等待该事件的阻塞队列中移出把被阻塞的进程从等待该事件的阻塞队列中移出u将其将其PCBPCB中的现行状态由阻塞改为就绪中的现行状态由阻塞改为就绪u将该将该PCBPCB插入到就绪队列中插入到就绪队列中进程进程的阻塞与唤醒的阻塞与唤醒计算机科学与技术系计算机科学与技术系2024/5/446进程进程的挂起与激活的挂起与激活 1.1.进程的挂起进程的挂起l系系统统将将利利用用挂挂起起原原语语suspend(suspend()将将指指定定进进程程或或处处于于阻阻塞塞状状态态的的进程挂起。进程挂起。lsuspend()suspend()原语的执行过程原语的执行过程u首首先先检检查查被被挂挂起起进进程程的的状状态态，若若处处于于活活动动就就绪绪状状态态，便便将将其其改改为为静静止止就就绪绪；对对于于活活动动阻阻塞塞状状态态的的进进程程，则则将将之之改改为为静静止止阻塞阻塞。u把该进程的把该进程的PCBPCB复制到某指定的内存区域。复制到某指定的内存区域。u若被挂起的进程正在执行若被挂起的进程正在执行,则转向调度程序重新调度。则转向调度程序重新调度。计算机科学与技术系计算机科学与技术系2024/5/447 2.2.进程的激活过程进程的激活过程l系统将利用激活原语系统将利用激活原语active()active()将指定进程激活。将指定进程激活。lactive()active()原语执行过程原语执行过程u将进程从外存调入内存，检查该进程的现行状态，若是静止将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，将之改为活动就绪；若为静止阻塞便将之改为活动阻就绪，将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。塞。u假如采用的是抢占调度策略，则每当有新进程进入就绪队列假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。把处理机分配给刚被激活的进程。进程进程的挂起与激活的挂起与激活 计算机科学与技术系计算机科学与技术系2024/5/4481.1.引起进程创建的主要事件？引起进程创建的主要事件？2.2.在创建一个进程时所需要完成的主要工作是什么？在创建一个进程时所需要完成的主要工作是什么？3.3.在撤消一个进程时所要完成的主要工作是什么？在撤消一个进程时所要完成的主要工作是什么？课后思考题课后思考题 内容概述2024/5/4492.1 前驱图和程序执行前驱图和程序执行 2.2 进程的描述进程的描述2.3 进程控制进程控制2.4 进程同步进程同步2.5 经典进程的同步问题经典进程的同步问题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 管程机制管程机制2024/5/450计算机科学与技术系计算机科学与技术系2024/5/4512.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不能得到数据而阻塞；反之当缓冲满时，不能得到数据而阻塞；反之当缓冲满时，A A无法写入而阻塞，又称为无法写入而阻塞，又称为“同步同步”。2.临界资源临界资源定义定义:在一段时间内只允许一个进程访问的资源。在一段时间内只允许一个进程访问的资源。例如:打印机、磁带机、卡片输入机、变量、表格、数据、指针、数组等。进程之间采取互斥方式实现对这些资源的共享。2024/5/452例子：例子：生生产产者者-消消费费者者(producer-consumer)(producer-consumer)问问题题是是一一个个著著名名的的进进程程同步问题。同步问题。有一群生产者进程在生产产品，提供给消费者进程去消费。有一群生产者进程在生产产品，提供给消费者进程去消费。不能向满缓冲区投放产品，不能从空缓冲区中取产品。不能向满缓冲区投放产品，不能从空缓冲区中取产品。2.4.1 2.4.1 进程同步的基本概念进程同步的基本概念计算机科学与技术系计算机科学与技术系2024/5/453 一个数组缓冲池，有一个数组缓冲池，有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 计算机科学与技术系计算机科学与技术系2024/5/454producer: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;/从从缓冲区中消冲区中消费产品品 out =(out+1)mod n;counter =counter-1;/缓冲池中冲池中产品数减一品数减一 consumer the item in nextc;/消消费一个一个产品品 until false;计算机科学与技术系计算机科学与技术系2024/5/455 虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言机器语言实现时，常可用下面的形式描述：register1=counter;register2=counter;register1=register1+1;register2=register2-1;counter=register1;counter=register2;计算机科学与技术系计算机科学与技术系2024/5/456 假设：counter的当前值是5。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句，则最后共享变量counter的值仍为5；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，counter值也还是5，但是，如果按下述顺序执行，counter值是4。由于并发执行而失去封闭性。register1=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.临界区不论是硬件临界资源硬件临界资源还是软件临界资源软件临界资源，多个进程必须互斥互斥地对它进行访问。在每个进程中访问临界资源的那段代码称为临界区。在每个进程中访问临界资源的那段代码称为临界区。每个进程进入临界区之前应先对欲访问的临界资源进行检查，看是否正在被访问。如果此刻该临界资源未被访问，该进程可进入临界区,并设置它正在被访问的标志，在临界区之前执行的这段代码称为进入进入区区。在临界区后面也要加上一段代码，用于将临界区被访问的资源恢复为未被访问的标志，称为退出区退出区。2024/5/457计算机科学与技术系计算机科学与技术系2024/5/458可把一个可把一个访问临界资源访问临界资源的循环进程描述如下的循环进程描述如下:repeat critical section;临界区临界区 remainder section;剩余区剩余区 until false;entry sectionexit section 进入区进入区 退出区退出区 计算机科学与技术系计算机科学与技术系2024/5/4594.4.同步机制应遵循的规则同步机制应遵循的规则(1)(1)空闲让进：空闲让进：当无进程处于临界区时当无进程处于临界区时,应允许一个进程进应允许一个进程进入临界区入临界区,以有效利用临界资源。以有效利用临界资源。(2)(2)忙则等待忙则等待：当有进程进入临界区时当有进程进入临界区时,其他进程必须等待。其他进程必须等待。(3)(3)有限等待：有限等待：对要求访问临界资源的进程对要求访问临界资源的进程,应保证在有限应保证在有限时间内进入自己的临界区时间内进入自己的临界区,防止防止“死等死等”。(4)(4)让权等待：让权等待：当进程不能进入其临界区时当进程不能进入其临界区时,应立即释放处应立即释放处理机理机,防止防止“忙等忙等”,不能一直用语句判断能不能进不能一直用语句判断能不能进,占占用处理机。用处理机。2.4.2 硬件同步机制硬件同步机制采采用用软软件件方方法法实实现现进进程程互互斥斥使使用用临临界界资资源源是是很很困困难难的的，它它们们通通常常能能实实现现两两个个进进程程的的互互斥斥，很很难难控控制多个进程的互斥。制多个进程的互斥。算算法法设设计计需需要要非非常常小小心心，否否则则可可能能出出现现死死锁锁，或或互斥失败等严重问题。互斥失败等严重问题。软软件件方方法法始始终终不不能能解解决决“忙忙等等”现现象象，降降低低系系统统效率。效率。硬件方法包括硬件方法包括屏蔽中断屏蔽中断和和专用机器指令专用机器指令。2.4.2 硬件同步机制硬件同步机制-屏蔽中断屏蔽中断由由由由于于于于进进进进程程程程切切切切换换换换需需需需要要要要依依依依赖赖赖赖中中中中断断断断来来来来实实实实现现现现，如如如如果果果果屏屏屏屏蔽蔽蔽蔽中中中中断断断断，则不会出现进程切换。则不会出现进程切换。则不会出现进程切换。则不会出现进程切换。因因因因此此此此，为为为为了了了了实实实实现现现现对对对对临临临临界界界界资资资资源源源源的的的的互互互互斥斥斥斥使使使使用用用用，可可可可以以以以在在在在进进进进程程程程进进进进入入入入临临临临界界界界区区区区之之之之前前前前，屏屏屏屏蔽蔽蔽蔽中中中中断断断断,当当当当进进进进程程程程退退退退出出出出临临临临界界界界区区区区时，打开系统中断。时，打开系统中断。时，打开系统中断。时，打开系统中断。中中中中断断断断被被被被屏屏屏屏蔽蔽蔽蔽以以以以后后后后，系系系系统统统统时时时时钟钟钟钟中中中中断断断断也也也也被被被被屏屏屏屏蔽蔽蔽蔽。处处处处理理理理机机机机将不会被切换到其他进程。将不会被切换到其他进程。将不会被切换到其他进程。将不会被切换到其他进程。于于于于是是是是，一一一一旦旦旦旦屏屏屏屏蔽蔽蔽蔽中中中中断断断断，进进进进程程程程就就就就可可可可以以以以检检检检查查查查和和和和修修修修改改改改共共共共享享享享内内内内存存存存区区区区中中中中的的的的数数数数据据据据，而而而而不不不不必必必必担担担担心心心心其其其其他他他他进进进进程程程程介介介介入入入入。其其其其伪伪伪伪代码如下：代码如下：代码如下：代码如下：2.4.2 硬件同步机制硬件同步机制-屏蔽中断屏蔽中断repeat ;forever.2.4.2 硬件同步机制硬件同步机制-屏蔽中断屏蔽中断这种方法约束条件太强，付出的代价太大这种方法约束条件太强，付出的代价太大这种方法约束条件太强，付出的代价太大这种方法约束条件太强，付出的代价太大因因因因为为为为中中中中断断断断被被被被屏屏屏屏蔽蔽蔽蔽以以以以后后后后，系系系系统统统统将将将将无无无无法法法法响响响响应应应应任任任任何何何何外外外外部部部部请请请请求求求求，也也也也不不不不会会会会响响响响应应应应当当当当前前前前执执执执行行行行进进进进程程程程的的的的任任任任何何何何异异异异常常常常及及及及系系系系统故障，严重地降低了处理机性能。统故障，严重地降低了处理机性能。统故障，严重地降低了处理机性能。统故障，严重地降低了处理机性能。这这这这种种种种方方方方法法法法仅仅仅仅对对对对单单单单处处处处理理理理机机机机系系系系统统统统有有有有效效效效，如如如如果果果果系系系系统统统统有有有有两两两两个个个个或或或或多多多多个个个个共共共共享享享享内内内内存存存存的的的的处处处处理理理理机机机机，屏屏屏屏蔽蔽蔽蔽中中中中断断断断仅仅仅仅仅仅仅仅对对对对执执执执行行行行本本本本指指指指令令令令的的的的处处处处理理理理机机机机有有有有效效效效，其其其其它它它它处处处处理理理理机机机机仍仍仍仍将将将将继继继继续续续续运运运运行，并可以访问共享内存空间。行，并可以访问共享内存空间。行，并可以访问共享内存空间。行，并可以访问共享内存空间。2.4.2 硬件同步机制硬件同步机制-专用机器指令专用机器指令利用一些专用机器指令也能实现互斥，机利用一些专用机器指令也能实现互斥，机器指令在一个指令周期内执行，不会受到器指令在一个指令周期内执行，不会受到其它指令的干扰，也不会被中断。其它指令的干扰，也不会被中断。Test and Set指令就是较常用的一种机器指指令就是较常用的一种机器指令，其定义如下：令，其定义如下：2.4.2 硬件同步机制硬件同步机制-专用机器指令专用机器指令TestAndSet指令：这条指令是原子操作，即执行该代码时不允许被中断。其功功能能是是读读出出指指定定标标志志后后把把该该标标志志设设置置为为真真。指令的功能描述为：Boolean TestAndSet(Boolean*lock)Boolean old；old=*lock；*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；在每个进程中再设置一个局部布尔变量key，用于与lock交换信息。在进入临界区之前先利用Swap指令交换lock与key的内容，然后检查key的状态；有进程在临界区时，重复交换和检查过程，直到进程退出。利用Swap指令实现进程互斥的算法描述如下：1.key=true;2.while(key!=false)3.Swap(&lock,&key);4./进程的临界区代码段；5.lock=false;6./进程的其他代码；机器机器指令优点指令优点非常简单，易于证明；非常简单，易于证明；同时适合于单处理机系统和共享内存的多同时适合于单处理机系统和共享内存的多处理机系统中多个进程的互斥；处理机系统中多个进程的互斥；可以分别为临界区设置属于它自己的变量，可以分别为临界区设置属于它自己的变量，以实现对多个临界区的互斥访问。以实现对多个临界区的互斥访问。机器机器指令缺点指令缺点 “忙等忙等忙等忙等”现象仍然存在。进程都需要循环检测，现象仍然存在。进程都需要循环检测，现象仍然存在。进程都需要循环检测，现象仍然存在。进程都需要循环检测，等待时机进入临界区。但是，由于采用了机器指等待时机进入临界区。但是，由于采用了机器指等待时机进入临界区。但是，由于采用了机器指等待时机进入临界区。但是，由于采用了机器指令，这种令，这种令，这种令，这种“忙等忙等忙等忙等”消耗的机器时间比软件方法小，消耗的机器时间比软件方法小，消耗的机器时间比软件方法小，消耗的机器时间比软件方法小，属于属于属于属于“可接受的忙等可接受的忙等可接受的忙等可接受的忙等”。可能出现饥饿现象。当临界区空闲时，执行循环可能出现饥饿现象。当临界区空闲时，执行循环可能出现饥饿现象。当临界区空闲时，执行循环可能出现饥饿现象。当临界区空闲时，执行循环检测的若干等待进程能进入临界区的机率是相等检测的若干等待进程能进入临界区的机率是相等检测的若干等待进程能进入临界区的机率是相等检测的若干等待进程能进入临界区的机率是相等的，有的进程可能的，有的进程可能的，有的进程可能的，有的进程可能“运气运气运气运气”非常不好，很难有机非常不好，很难有机非常不好，很难有机非常不好，很难有机会进入临界区，而饥饿。会进入临界区，而饥饿。会进入临界区，而饥饿。会进入临界区，而饥饿。机器机器指令缺点指令缺点还有可能导致死锁。还有可能导致死锁。还有可能导致死锁。还有可能导致死锁。例如，进程例如，进程例如，进程例如，进程P1P1P1P1的优先级低于的优先级低于的优先级低于的优先级低于P2P2P2P2的优先级，若的优先级，若的优先级，若的优先级，若P1P1P1P1通通通通过执行专用机器指令，进入临界区，且在临界区过执行专用机器指令，进入临界区，且在临界区过执行专用机器指令，进入临界区，且在临界区过执行专用机器指令，进入临界区，且在临界区内被中断，内被中断，内被中断，内被中断，P2P2P2P2被调度执行。若被调度执行。若被调度执行。若被调度执行。若P2P2P2P2也需要进入该临也需要进入该临也需要进入该临也需要进入该临界区，由于临界区被界区，由于临界区被界区，由于临界区被界区，由于临界区被P1P1P1P1占用，占用，占用，占用，P2 P2 P2 P2“忙等忙等忙等忙等”。由于。由于。由于。由于P1P1P1P1的优先级低于的优先级低于的优先级低于的优先级低于P2P2P2P2，调度程序不可能强行剥夺，调度程序不可能强行剥夺，调度程序不可能强行剥夺，调度程序不可能强行剥夺P2P2P2P2的执行而调度的执行而调度的执行而调度的执行而调度P1P1P1P1。这样，。这样，。这样，。这样，P1P1P1P1将一直占用临界区被将一直占用临界区被将一直占用临界区被将一直占用临界区被中断，中断，中断，中断，P2P2P2P2一直一直一直一直“忙等忙等忙等忙等”，如果没有外力的作用，如果没有外力的作用，如果没有外力的作用，如果没有外力的作用，这种这种这种这种“僵持僵持僵持僵持”状态将一直保持下去，即系统出现状态将一直保持下去，即系统出现状态将一直保持下去，即系统出现状态将一直保持下去，即系统出现死锁。死锁。死锁。死锁。1965年,荷兰学者Dijkstra提出的信号量(Semaphores)机制是一种有效的进程同步工具，所以P、V分别是荷兰语的test(proberen)和increment(verhogen)。信号量机制已从整型信号量整型信号量发展为记录型信号量记录型信号量、AND型型信号量信号量，又进一步发展为信号量集信号量集。信号量就是OS提供的管理公有资源的有效手段。信号量代表可用资源实体的数量可用资源实体的数量。物理意义2024/5/4712.4.3 2.4.3 2.4.3 2.4.3 信号量机制信号量机制信号量机制信号量机制 计算机科学与技术系计算机科学与技术系2024/5/4721.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)是是原原子子操操作作，因因此此它它们们在在执执行行时时是是不不可可中中断断的的。另另外外，信信号号量量只只能能通通过过原原语语操操作作来来访访问问，不不能能被被进进程调度所打断。程调度所打断。有有“忙等忙等”现象。现象。计算机科学与技术系计算机科学与技术系2024/5/473可把一个可把一个访问临界资源访问临界资源的循环进程描述如下的循环进程描述如下:repeat critical section;临界区临界区 remainder section;剩余区剩余区 until false;entry sectionexit sectionP(S)或或wait(S);V(S)或或signal(S);进入区进入区 退出区退出区 1.1.整型信号量整型信号量计算机科学与技术系计算机科学与技术系2024/5/4742.2.记录型信号量记录型信号量记录型信号量（也称记录型信号量（也称资源信号量资源信号量）机制，则是一种不存在）机制，则是一种不存在“忙等忙等”现象的进程同步机制，它采用了现象的进程同步机制，它采用了记录型的数据结记录型的数据结构。构。在采取了在采取了“让权等待让权等待”的策略后，又会出现多个进程等待的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于需要一个用于代表资源数目代表资源数目的整型变量的整型变量valuevalue外，还应增加外，还应增加一个进程链表一个进程链表L L，用于，用于链接上述的所有等待进程链接上述的所有等待进程。计算机科学与技术系计算机科学与技术系2024/5/475type 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;if S.value0 then wakeup(S.L);end 请求一个单位的该类资源该类资源数减少一个自我阻塞，放弃处理机释放一个单位资源该类资源增加一个唤醒进程计算机科学与技术系计算机科学与技术系2024/5/4763.AND3.AND3.AND3.AND型信号量型信号量型信号量型信号量 在在有有些些任任务务中中,一一个个进进程程先先要要获获得得多多个个共共享享资资源源后后才才能能执执行行，若若进进程程A A和和B B都都要要申申请请D D和和E E两两种种资资源源，设设信信号号量量DmutexDmutex和和EmutexEmutex的的初初值值均均为为1 1在在两两个个进进程程中中都都要要包包含含两两个个对对DmutexDmutex和和EmutexEmutex的操作，即的操作，即process A:process B:P(Dmutex);P(Emutex);P(Emutex);P(Dmutex);若进