1、第二章 进 程 管 理 1第二章第二章 进程管理进程管理n重点：重点：n进程的定义、进程控制的基本概念。进程的定义、进程控制的基本概念。n进程进程PCB的基本结构，作用及的基本结构，作用及进程的状态转换。进程的状态转换。n进程同步与互斥的基本概念和解决方法进程同步与互斥的基本概念和解决方法。n几个经典的进程同步与互斥问题及算法几个经典的进程同步与互斥问题及算法。n线程的基本概念及状态。线程的基本概念及状态。n难点难点：n进程的同步与互斥进程的同步与互斥第二章 进 程 管 理 2第二章第二章 进程管理进程管理主要内容：主要内容：2.1 进程的基本概念进程的基本概念2.2 进程控制进程控制2.3
2、进程同步进程同步2.4 经典进程的同步问题经典进程的同步问题 2.5 管程机制管程机制2.6 进程通信进程通信2.7 线程线程第二章 进 程 管 理 32.1.进程的基本概念进程的基本概念2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征2.1.2 前趋图前趋图2.1.3 程序的并发执行及其特征程序的并发执行及其特征2.1.4 进程的特征与状态进程的特征与状态2.1.5 进程控制块进程控制块第二章 进 程 管 理 42.1.12.1.1 程序的顺序执行及特征程序的顺序执行及特征1、程序的顺序执行、程序的顺序执行 例例1：数据计算时要经过：数据计算时要经过 I:输入操作输入操作 C:计算操
3、作计算操作 P:打打印操作印操作:例例2：如下三条语句的执行：如下三条语句的执行 S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;2、特征、特征n顺序性、封闭性、可再现性顺序性、封闭性、可再现性I1C1P1I2C2P2第二章 进 程 管 理 52.1.22.1.2 前趋图前趋图1、前趋图、前趋图(Precedence Graph)n一个有向无循环图一个有向无循环图n描述进程之间执行的前后关系描述进程之间执行的前后关系2、前趋关系、前趋关系“”n=(Pi,Pj)|Pi must complete before Pj may startn如果：如果：(Pi,Pj)，也可以写成：，也可以
4、写成：PiPjn则称：则称：Pi是是Pj的直接前趋的直接前趋,Pj是是Pi的直接后继的直接后继n初始结点：没有前趋初始结点：没有前趋n终止结点：没有后继终止结点：没有后继n每个结点还具有一个每个结点还具有一个权权或或重量重量(Weight)，表示该，表示该结点的程序量或执行时间。结点的程序量或执行时间。P1P2P3P1P2P3第二章 进 程 管 理 6 其前趋关系表示为：其前趋关系表示为：P=PP=P1 1，P P2 2，P P3 3，P P4 4，P P5 5，P P6 6，P P7 7=（P P1 1,P,P2 2）,（P P1 1,P,P3 3）,（P P1 1,P,P4 4）,（P P
5、2 2,P,P5 5）,（P P3 3,P,P5 5）,（P P4 4,P,P6 6）,（P P5 5,P,P7 7）,（P P6 6,P,P7 7）P1P4P3P2P6P5P7具有具有7个结点的前驱图个结点的前驱图第二章 进 程 管 理 72.1.32.1.3 程序的并发执行及其特征程序的并发执行及其特征I1C1P1I2C2P2I3C3P3I4C4P4输入程序输入程序计算程序计算程序打印程序打印程序1、在对一批程序进行处理时，可以并发执行。、在对一批程序进行处理时，可以并发执行。例例1：输入、计算、打印三个程序对一批作业进行处理时存：输入、计算、打印三个程序对一批作业进行处理时存在前趋关系：
6、在前趋关系：前驱关系：前驱关系：IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1第二章 进 程 管 理 82.1.3 程序的并发执行及其特征程序的并发执行及其特征例例2：对于下述四条语句的程序段：对于下述四条语句的程序段：S1：a:=x+2;S2：b:=y+4;S3：c:=a+b;S4：d:=c+b;S2S1S3S4前驱关系前驱关系第二章 进 程 管 理 9n又如：三个程序的执行顺序如图：又如：三个程序的执行顺序如图：P1：a:=1 P2：x:=a+1 P3：y:=a+1 2.1.3 程序的并发执行及其特征程序的并发执行及其特征P1P2P3前驱关系前驱关系第二章 进 程 管 理 1
7、0程序并发执行条件（程序并发执行条件（Bernstein条件）条件）将任一语句划分为两个变量的集合将任一语句划分为两个变量的集合R(Si)和和W(Si):读读集集R(Si)=a1，a2，am写集写集W(Si)=b1，b2，bn如对语句如对语句S1和和S2有：有：R(S1)W(S2)=W(S1)R(S2)=W(S1)W(S2)=成立，则语句成立，则语句S1和和S2可并发执行。可并发执行。第二章 进 程 管 理 11程序并发执行条件（程序并发执行条件（Bernstein条件）条件）例例1 语句语句 c=a b 和和 w=c+1R（c=a b）=a,b W（c=a b）=c R（w=c+1）=c W
8、（w=c+1）=w R（w=c+1）W（c=a b）=c 语句语句 c=a b 和和 w=c+1 不能并发执行。不能并发执行。第二章 进 程 管 理 122、程序并发执行时的特征、程序并发执行时的特征n间断间断(异步异步)性性：“执行执行暂停暂停执行执行”，一个程序可能，一个程序可能走到中途停下来，失去原有的时序关系。走到中途停下来，失去原有的时序关系。n失去封闭性失去封闭性：共享资源，受其他程序的控制逻辑的影：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。程序修改，失去原有的不变特征
9、。n不可再现性不可再现性：失去封闭性：失去封闭性 失去可再现性；外界环失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重境在程序的两次执行期间发生变化，失去原有的可重复特征。复特征。第二章 进 程 管 理 13程序并发执行时的不可再现性程序并发执行时的不可再现性 例如例如:有两个循环程序有两个循环程序A和和B，共享一个变量，共享一个变量N。程序。程序A每执行一次时，都要做每执行一次时，都要做N:=N+1;程序程序B每执行一次时，都每执行一次时，都要执行要执行print(N),然后将然后将N置成置成0。程序。程序A和和B以不同的速度以不同的速度运行。运行。可能出现的情况如下可能出
10、现的情况如下(某时刻变量某时刻变量N的值为的值为n)：1、N:=N+1在在print(N)和和N:=0之前，之前，2、N:=N+1在在print(N)和和N:=0之后，之后，3、N:=N+1在在print(N)和和N:=0之间，之间，得到的得到的N值为值为n+1,n+1,0得到的得到的N值为值为n,0,1得到的得到的N值为值为n,n+1,0第二章 进 程 管 理 142.1.4 进程的特征与状态进程的特征与状态1.进程的特征与定义进程的特征与定义2.进程的三种基本状态进程的三种基本状态3.挂起状态挂起状态4.创建状态和终止状态创建状态和终止状态第二章 进 程 管 理 15进程特征进程特征n结构
11、特性结构特性(PCB-Process Control Block)n进程实体程序段相关的数据段进程实体程序段相关的数据段PCBn动态性动态性n由创建而产生，由调度而执行，由撤销而消亡由创建而产生，由调度而执行，由撤销而消亡n并发性并发性n独立性独立性n独立运行、独立分配资源、独立接受调度独立运行、独立分配资源、独立接受调度n异步性异步性第二章 进 程 管 理 16进程定义进程定义n进程的典型定义：进程的典型定义：（1 1）进程是程序的一次执行）进程是程序的一次执行（2 2）进程是一个程序及其数据在处理机上顺序执行）进程是一个程序及其数据在处理机上顺序执行时所发生的活动时所发生的活动（3 3）进
12、程是程序在一个数据集合上运行的过程，它）进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。是系统进行资源分配和调度的一个独立单位。n传统传统OSOS中进程定义：进程是进程实体的运行过程，中进程定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。是系统进行资源分配和调度的一个独立单位。第二章 进 程 管 理 17进程与程序的区别：（如同进程与程序的区别：（如同“演出演出”与与“剧剧本本”）进程是动态的，程序是静态的：进程是动态的，程序是静态的：程序是有序代码的集合；程序是有序代码的集合；进程是程序的执行。进程更能真实地描述并发执行，可以进程是程序
13、的执行。进程更能真实地描述并发执行，可以揭示揭示OS的内部特征，而程序不能的内部特征，而程序不能。进程是暂时的，程序是永久的：进程是暂时的，程序是永久的：进程是一个状态变化的过进程是一个状态变化的过程，程序可长久保存。程，程序可长久保存。进程与程序的组成不同：进程与程序的组成不同：进程的组成包括程序、数据和进进程的组成包括程序、数据和进程控制块（即进程状态信息）；程序仅是代码的有序集合。程控制块（即进程状态信息）；程序仅是代码的有序集合。进程与程序的对应关系：进程与程序的对应关系：通过多次执行，一个程序可对应通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可涉及到多个程序的多个进程
14、；通过调用关系，一个进程可涉及到多个程序的执行。执行。进程具有创建其他进程的功能进程具有创建其他进程的功能，父进程创建子进程而形成，父进程创建子进程而形成进程树，而程序不能。进程树，而程序不能。第二章 进 程 管 理 18进程的基本状态进程的基本状态n三种基本状态：三种基本状态：n就绪状态就绪状态n执行状态执行状态n阻塞状态阻塞状态进程状态转换进程状态转换 阻塞阻塞状态状态就绪就绪状态状态 执行执行状态状态调度调度I/O请求请求进程进程唤醒唤醒时间时间片到片到第二章 进 程 管 理 19第二章 进 程 管 理 20挂起状态挂起状态n引入挂起状态的原因：引入挂起状态的原因：n终端用户请求终端用户
15、请求n父进程请求父进程请求:考查、修改或协调各子进程时；考查、修改或协调各子进程时；n负荷调节的需要：缓和内存紧张的情况；负荷调节的需要：缓和内存紧张的情况；n操作系统的需要：改善系统运行性能，调节负荷；操作系统的需要：改善系统运行性能，调节负荷；n增加的状态：增加的状态：n挂起状态（静止状态）挂起状态（静止状态）n非挂起状态（活动状态）非挂起状态（活动状态）第二章 进 程 管 理 21具有挂起状态的进程状态图具有挂起状态的进程状态图活动活动阻塞阻塞执行执行状态状态活动活动就绪就绪静止静止就绪就绪静止静止阻塞阻塞调度调度唤醒唤醒I/O请求请求激活激活激活激活挂起挂起挂起挂起挂起挂起唤醒唤醒第二
16、章 进 程 管 理 22创建状态和终止状态创建状态和终止状态n创建状态创建状态n创建一个进程过程：创建一个进程过程：1.为一个新进程创建为一个新进程创建PCB，并填写必要的管理信息，并填写必要的管理信息2.把该进程转入就绪状态并插入就绪队列之中把该进程转入就绪状态并插入就绪队列之中n引入创建状态，为了保证进程的调度必须在创引入创建状态，为了保证进程的调度必须在创建工作完成后进行，以确保对进程控制块操作的建工作完成后进行，以确保对进程控制块操作的完整性。完整性。第二章 进 程 管 理 23创建状态和终止状态创建状态和终止状态n终止状态终止状态n进程终止过程进程终止过程n首先，等待操作系统进行善后
17、处理首先，等待操作系统进行善后处理n然后，将其然后，将其PCB清零，并将清零，并将PCB空间返还系统空间返还系统n当一个进程到达了自然结束点，或是出现了无当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是法克服的错误，或是被操作系统所终结，或是被其它有终止权的进程所终结，它将进入终止被其它有终止权的进程所终结，它将进入终止状态。状态。第二章 进 程 管 理 24创建状态和终止状态创建状态和终止状态时间片完时间片完 许可许可 释放释放进程调度进程调度I/O完成完成 I/O请求请求 创建创建终止终止就绪就绪执行执行阻塞阻塞进程的五种基本状态及转换进程的五种基本状态及转
18、换第二章 进 程 管 理 25创建状态和终止状态（续）创建状态和终止状态（续）激活激活 许可许可 挂起挂起 调度调度 挂起挂起释放释放 释放释放I/O请求请求 激活激活挂起挂起静止静止就绪就绪静止静止阻塞阻塞活动活动就绪就绪执行执行活动活动阻塞阻塞创建创建终止终止许可许可具有创建、终止和挂起状态的进程状态图具有创建、终止和挂起状态的进程状态图第二章 进 程 管 理 262.1.5 2.1.5 进程控制块（进程控制块（PCBPCB）1.PCB的作用的作用2.PCB中的信息中的信息3.PCB的组织方式的组织方式第二章 进 程 管 理 271.PCB1.PCB的作用的作用nPCBPCB中记录了操作系
19、统所需的、用于描述进程的当前情况以中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。是及控制进程运行的全部信息。是进程存在的唯一标志进程存在的唯一标志。n作用：作用：使一个在多道程序环境下不能独立运行的程序，成使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，一个能与其他进程并发执为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。行的进程。nPCBPCB常驻内存常驻内存，系统将所有的，系统将所有的PCBPCB组成若干链表或队列，存组成若干链表或队列，存放在放在OSOS中专门开辟的中专门开辟的PCBPCB区内区内第二章 进 程 管 理 28
20、 2.PCB2.PCB中的信息中的信息l进程标识符进程标识符：唯一的标识一个进程：唯一的标识一个进程 内部标识（方便系统使用）内部标识（方便系统使用）外部标识（由创建者提供，由字母数字组成）外部标识（由创建者提供，由字母数字组成）l处理机状态处理机状态：由：由CPU的各种寄存器中的内容组成的各种寄存器中的内容组成 通用寄存器通用寄存器；指令计数器指令计数器；程序状态字程序状态字PSW ；用户栈指针用户栈指针进程控制信息进程控制信息pidstatusschedualcontrol处理机状态信息处理机状态信息进程标识符进程标识符进程调度信息进程调度信息第二章 进 程 管 理 29n进程调度信息：进
21、程调度信息：进程状态；进程状态；进程优先级进程优先级；其它信息；其它信息；等待事件（阻塞原因）等待事件（阻塞原因）n进程控制信息：进程控制信息：程序和数据的地址；同步和通信机制；程序和数据的地址；同步和通信机制；资源清单资源清单；链接指针；链接指针；进程控制信息进程控制信息pidstatusschedualcontrol处理机状态信息处理机状态信息进程标识符进程标识符进程调度信息进程调度信息2.PCB2.PCB中的信息中的信息第二章 进 程 管 理 303.PCB3.PCB的组织方式的组织方式nPCB数目数目n一个系统中的一个系统中的PCB数目可为数十个、数百个甚至数千个数目可为数十个、数百个
22、甚至数千个n链接方式链接方式n把具有同一状态的把具有同一状态的PCB，用其链接字链接成一个队列，用其链接字链接成一个队列n就绪队列、若干个阻塞队列、空队列就绪队列、若干个阻塞队列、空队列n索引方式索引方式n系统根据所有进程的状态建立相应的索引表系统根据所有进程的状态建立相应的索引表n就绪索引表、阻塞索引表等，索引表在内存的首地址记录在就绪索引表、阻塞索引表等，索引表在内存的首地址记录在内存的一些专用单元中。内存的一些专用单元中。第二章 进 程 管 理 313 3、PCBPCB的组织方式（续）的组织方式（续）执行指针执行指针 就绪队列指针就绪队列指针阻塞队列指针阻塞队列指针 空闲队列指针空闲队列
23、指针 执行指针执行指针 就绪队列指针就绪队列指针 阻塞队列指针阻塞队列指针 3572496PCB链接队列示意图链接队列示意图按索引方式组织按索引方式组织PCB就绪索引表就绪索引表阻塞索引表阻塞索引表第二章 进 程 管 理 32思考题思考题1 1如果系统中有如果系统中有N N个进程，运行的进程最多几个，最少个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？个，最少几个？解答解答：在单处理机系统中，处于运行状态的：在单处理机系统中，处于运行状态的进程最多为进程最多为1个，最少为个，最少为0个；处于就绪进程个；处
24、于就绪进程最多为最多为N-1个，最少为个，最少为0个；处于等待的进程个；处于等待的进程最多为最多为N个，最少为个，最少为0个。个。第二章 进 程 管 理 33思考题思考题2.2.有没有这样的状态转换，为什么？有没有这样的状态转换，为什么？等待等待运行；运行；就绪就绪等待等待第二章 进 程 管 理 342.2 进程控制进程控制主要内容：主要内容：1.进程创建进程创建2.进程撤消进程撤消3.进程阻塞进程阻塞4.进程唤醒进程唤醒5.进程挂起与激活进程挂起与激活第二章 进 程 管 理 352.2 进程控制进程控制n进程控制是对系统中所有进程从产生、存在到消亡的全进程控制是对系统中所有进程从产生、存在到
25、消亡的全过程实行有效的管理和控制。过程实行有效的管理和控制。n进程控制一般是由操作系统的内核来实现，内核在执行进程控制一般是由操作系统的内核来实现，内核在执行操作时，往往是通过执行各种原语操作来实现的。操作时，往往是通过执行各种原语操作来实现的。无无 有有 消亡消亡 运运 行行 等等 待待 就就 绪绪 等等 待待等待等待唤醒唤醒创建创建撤消撤消状态转换状态转换第二章 进 程 管 理 36n内核内核：加在硬件上的第一层软件，通过执行各种：加在硬件上的第一层软件，通过执行各种原语原语操作来操作来实现各种控制和管理功能，具有创建进程、撤消进程、进程实现各种控制和管理功能，具有创建进程、撤消进程、进程
26、通信、资源管理的功能。通信、资源管理的功能。n原语原语(primitive)：由若干条指令构成的由若干条指令构成的“原子操作原子操作(atomic operation)”过程，作为一个整体而不可分割，要么全都完成，过程，作为一个整体而不可分割，要么全都完成，要么全都不做。原子操作在管态下执行，常驻内存。要么全都不做。原子操作在管态下执行，常驻内存。n原语的作用原语的作用：实现进程的通信和控制，系统对进程的控制如：实现进程的通信和控制，系统对进程的控制如不使用原语，就会造成其状态的不确定性，从而达不到进程不使用原语，就会造成其状态的不确定性，从而达不到进程控制的目的。控制的目的。第二章 进 程
27、管 理 37处理机运行时的两种状态处理机运行时的两种状态n用户态（目态）用户态（目态）时不可直接访问受保护的时不可直接访问受保护的OS代码。代码。n核心态（管态）核心态（管态）时执行时执行OS代码，可以访问全部进程空间。代码，可以访问全部进程空间。请求请求应答应答核心态核心态用户态用户态第二章 进 程 管 理 38进程树进程树 PDPBPEPCPFPAPIPHPGPJPKPLPMPN2.2.1 进程的创建进程的创建1、进程图、进程图是用于描述一个进程的家族关系的有向树。是用于描述一个进程的家族关系的有向树。n结点结点代表进程代表进程n有向边有向边代表父子关系代表父子关系n进程之间的关系进程之间
28、的关系：n父、子进程与祖先进程：父、子进程与祖先进程：PCB中设置家族关系表项中设置家族关系表项n继承归还资源：继承归还资源：“父父”创建创建“子子”、“父父”撤消撤消“子子”第二章 进 程 管 理 392、引起创建（、引起创建（create）进程的事件）进程的事件l用户登录用户登录（分时系统）（分时系统）l作业调度作业调度（批处理系统）（批处理系统）l提供服务提供服务（操作系统提供服务）（操作系统提供服务）l应用请求应用请求（由现有进程派生）（由现有进程派生）第二章 进 程 管 理 403 3、进程的创建、进程的创建(Creat()(Creat()原语原语)过程：过程：申请空白申请空白PCB
29、PCB、为新进程分配资源、初始化为新进程分配资源、初始化PCBPCB、插入就绪进程队列、插入就绪进程队列HD就绪队列指针就绪队列指针PCB1 5PCB2 PCB3PCB4PCB5 13PCB6 0PCB7PCB8 9PCB9 12PCB10PCB11PCB12 25PCB13 6空空PCB队列指针队列指针RAM程序程序+数据数据PCB8 0PCB6 8第二章 进 程 管 理 412.2.2 进程的终止进程的终止1、引起进程终止事件、引起进程终止事件n正常结束（正常结束（Holt指令，指令，Logs off）n异常结束异常结束n越界错误、保护错、非法指令、特权指令错、运越界错误、保护错、非法指令
30、、特权指令错、运行超时、等待超时、算术运算错、行超时、等待超时、算术运算错、I/O故障故障n外界干预外界干预n操作员或操作系统干预操作员或操作系统干预n父进程请求父进程请求n父进程终止父进程终止第二章 进 程 管 理 422、进程的终止过程、进程的终止过程n根据被终止的进程的标识符，检索出该进程的根据被终止的进程的标识符，检索出该进程的PCB，读出该进程的状态。读出该进程的状态。n若该进程处于执行状态，立即终止其执行，置调度方若该进程处于执行状态，立即终止其执行，置调度方式为真，指示该进程终止后应重新进行调度。式为真，指示该进程终止后应重新进行调度。n若该进程有子孙进程，终止其所有子孙进程。若
31、该进程有子孙进程，终止其所有子孙进程。n将被终止进程所拥有的全部资源，或者归还给其父进将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。程，或者归还给系统。n将被终止进程的将被终止进程的PCB从所在队列中删除。从所在队列中删除。第二章 进 程 管 理 432.2.3进程的阻塞与唤醒进程的阻塞与唤醒1、引起进程阻塞和唤醒的事件、引起进程阻塞和唤醒的事件n请求系统服务请求系统服务n启动某种操作启动某种操作n新数据尚未到达新数据尚未到达n无新工作可做无新工作可做第二章 进 程 管 理 442、进程阻塞的过程、进程阻塞的过程n进程调用阻塞原语进程调用阻塞原语block()把自己阻塞，阻
32、塞是进程自把自己阻塞，阻塞是进程自身的一种主动性为。身的一种主动性为。n先停止进程的执行，将先停止进程的执行，将PCB中的现行状态由执行改中的现行状态由执行改为阻塞。为阻塞。n并将其并将其PCB插入具有相同事件的阻塞队列。插入具有相同事件的阻塞队列。n转调度程序进行重新调度，将处理机分配给另一就转调度程序进行重新调度，将处理机分配给另一就绪进程，保留被阻塞进程的处理机状态。绪进程，保留被阻塞进程的处理机状态。第二章 进 程 管 理 453、进程唤醒的过程、进程唤醒的过程n期待事件出现，相关进程调用唤醒原语期待事件出现，相关进程调用唤醒原语wakeup()n把被阻塞的进程从等待该事件的阻塞队列中
33、移出。把被阻塞的进程从等待该事件的阻塞队列中移出。n将其将其PCB中的现行状态由阻塞改为就绪。中的现行状态由阻塞改为就绪。n将该将该PCB插入就绪队列。插入就绪队列。n阻塞与唤醒要匹配使用，以免造成阻塞与唤醒要匹配使用，以免造成“永久阻塞永久阻塞”nblock()和和wakeup()要成对出现要成对出现第二章 进 程 管 理 462.2.4 进程的挂起与激活进程的挂起与激活n调用挂起原语调用挂起原语suspend()n检查被挂起进程的状态，处于活动就绪，便改为检查被挂起进程的状态，处于活动就绪，便改为静止就绪；处于活动阻塞，便改为静止阻塞；若静止就绪；处于活动阻塞，便改为静止阻塞；若进程正在执
34、行，则转向调度程序。进程正在执行，则转向调度程序。n调用激活原语调用激活原语active()n若进程在外存则将其调入内存，检查进程的状态，若进程在外存则将其调入内存，检查进程的状态，处于静止就绪，便改为活动就绪；处于静止阻塞，处于静止就绪，便改为活动就绪；处于静止阻塞，便改为活动阻塞。便改为活动阻塞。第二章 进 程 管 理 472.3 进程同步进程同步n进程同步的主要任务进程同步的主要任务：对多个相关进程在执行次序上：对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能有效地共享资进行协调，使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。源和相互合作，从
35、而使程序的执行具有可再现性。主要内容：主要内容：2.3.1 进程同步的基本概念进程同步的基本概念2.3.2 信号量机制信号量机制2.3.3 信号量的应用信号量的应用第二章 进 程 管 理 482.3.1 进程同步的基本概念进程同步的基本概念1、两种形式的制约关系：、两种形式的制约关系：n间接相互制约关系间接相互制约关系n进程互斥：进程互斥：一个进程正在访问临界资源，另一个要一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。访问该资源的进程必须等待。n直接相互制约关系直接相互制约关系n进程同步：进程同步：合作完成同一个任务的多个进程，在执合作完成同一个任务的多个进程，在执行速度或某些时
36、序点上必须相互协调的合作关系。行速度或某些时序点上必须相互协调的合作关系。前进前进示例示例第二章 进 程 管 理 49民航售票系统民航售票系统主机主机A窗口窗口B窗口窗口C窗口窗口D窗口窗口每个进程执行的操作：每个进程执行的操作：设设x表示某航班的票数。表示某航班的票数。if x0 then x:=x-1;在某时刻在某时刻x=1，有，有a、b两两人分别去人分别去A、B窗口买票，窗口买票，分析售票情况：分析售票情况：时间时间片到片到ab第二章 进 程 管 理 50进程同步举例：进程同步举例：司机售票员司机售票员司机：司机：P1 while(true)启动车辆；启动车辆；正常运行；正常运行；到站停
37、车；到站停车；售票员：售票员：P2 while(true)关门；关门；售票；售票；开门；开门；正确运行过程正确运行过程While(true)（司机）启动车辆；（司机）启动车辆；（售票员）关门；（售票员）关门；（司机）正常运行；（司机）正常运行；（售票员）售票；（售票员）售票；（司机）到站停车；（司机）到站停车；（售票员）开门；（售票员）开门；第二章 进 程 管 理 512、临界资源、临界资源n临界资源临界资源：一次仅允许一个进程访问的资源称为临界资源：一次仅允许一个进程访问的资源称为临界资源（互斥资源或共享变量）。（互斥资源或共享变量）。n物理设备：打印机，扫描仪物理设备：打印机，扫描仪n例例
38、1：两个进程：两个进程A、B共享一台打印机，若不加以控制，共享一台打印机，若不加以控制，两个进程的输出结果可能交织在一起，很难区分。两个进程的输出结果可能交织在一起，很难区分。n软件资源：全局变量，队列等软件资源：全局变量，队列等n例例2：飞机订票问题：飞机订票问题n设：设：x代表某航班机座号，代表某航班机座号，p1和和p2两个售票进程，售票两个售票进程，售票工作是对全局变量工作是对全局变量x加加1。第二章 进 程 管 理 52 两个进程共享一个变量两个进程共享一个变量x时，时，两种可能的执行次序：两种可能的执行次序：A：p1：r1:=x；r1:=r1+1；x:=r1；p2：r2:=x；r2:
39、=r2+1；x:=r2；B：P1：r1:=x;r1:=r1+1；x:=r1；p2：r2:=x;r2:=r2+1;x:=r2；设设x的初值为的初值为10，两种情况下的执行结果：，两种情况下的执行结果：情况情况A：x=10+2 情况情况B：x=10+1第二章 进 程 管 理 53例例3：生产者：生产者-消费者问题消费者问题产品产品outin01n-1缓冲池缓冲池in:=(in+1)mod nout:=(out+1)mod n第二章 进 程 管 理 54例例3：生产者：生产者-消费者问题消费者问题n缓冲池满缓冲池满：(in+1)mod n=outn缓冲池空：缓冲池空：in=outn引入整型变量：引入
40、整型变量：countern初值：初值：0n生产：生产：counter+1；n消费：消费：counter-1。第二章 进 程 管 理 55例例3：生产者：生产者-消费者问题消费者问题生产者消费者进程共享下面的变量：生产者消费者进程共享下面的变量：var n:integer;type item=;var buffer:array0,1,n-1 of item;in,out:0,1,n-1;counter:0,1,n;第二章 进 程 管 理 56例例3：生产者：生产者-消费者程序：消费者程序：producer:repeat produce an item in nextp;while counter
41、=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;第二章 进 程 管 理 57例例3：生产者：生产者-消费者程序机器语言实现：消费者程序机器语言实现：生产者：生产者：register1:=counter;register1:=reg
42、ister1+1;counter:=register1;假设假设counter的当前值为的当前值为5；并发执行时按如下顺序执行：并发执行时按如下顺序执行：register1:=counter;register1:=register1+1;register2:=counter;register2:=register2-1;counter:=register1;counter:=register2;消费者：消费者：register2:=counter;register2:=register2-1;counter:=register2;(register1=5)(register1=6)(regis
43、ter2=5)(register2=4)(counter=6)(counter=4)程序的执行失去了再现性！程序的执行失去了再现性！第二章 进 程 管 理 58repeatuntil false临界区临界区剩余区剩余区剩余区剩余区3、临界区（、临界区（critical section）n临界区临界区：进程中访问临界资源的一段进程中访问临界资源的一段代码。代码。n进入区进入区：在进入临界区之前，检查可在进入临界区之前，检查可否进入临界区的一段代码。如果可以否进入临界区的一段代码。如果可以进入临界区，设置相应进入临界区，设置相应“正在访问临正在访问临界区界区”标志。标志。n退出区退出区：用于将用于
44、将“正在访问临界区正在访问临界区”标志清除。标志清除。n剩余区剩余区：代码中的其余部分。代码中的其余部分。进入区进入区退出区退出区循环进程循环进程第二章 进 程 管 理 593、临界区（续）、临界区（续）P1：a:=a+1 print(a)互斥互斥P2：a:=a-1print(a)互斥互斥P3：if a0 thena:=a+1elsea:=a-1互斥互斥程序中的临界区程序中的临界区第二章 进 程 管 理 604、同步机制应遵循的规则、同步机制应遵循的规则n为实现进程互斥地进入临界区，可用软件或专门的同为实现进程互斥地进入临界区，可用软件或专门的同步机构实来现同步机制。步机构实来现同步机制。n所
45、有同步机制都应遵循四条准则：所有同步机制都应遵循四条准则：n空闲让进空闲让进：无进程处于临界区。：无进程处于临界区。n忙则等待忙则等待：已有进程处于其临界区。：已有进程处于其临界区。n有限等待有限等待：等待进入临界区的进程不能：等待进入临界区的进程不能“死死等等”。n让权等待让权等待：不能进入临界区的进程，应释放：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）。（如转换到阻塞状态）。第二章 进 程 管 理 612.3.2 信号量机制信号量机制n1965年，荷兰人年，荷兰人Dijkstra首先提出信号量机制首先提出信号量机制n信号量信号量（Semaphores）n仅能被两个原语操作仅能被
46、两个原语操作wait(S)-signal(S)修改的修改的整型整型变量，变量，表示一类资源的物理实体。表示一类资源的物理实体。n信号量的值表示资源数量，只能由信号量的值表示资源数量，只能由wait(S)和和signal(S)原子操作改变。原子操作改变。第二章 进 程 管 理 622.3.2 信号量机制信号量机制n信号量分类：信号量分类：n互斥的信号量：它的互斥的信号量：它的wait(S)-signal(S)在同一个在同一个进程中进程中 n同步的信号量：它的同步的信号量：它的wait(S)-signal(S)在不同的在不同的进程中进程中n信号量机制包括：信号量机制包括：n整型、记录型整型、记录型
47、、AND型、信号量集机制。型、信号量集机制。第二章 进 程 管 理 631.整型信号量整型信号量nS S是一个整型量，除初始化外仅能通过是一个整型量，除初始化外仅能通过2 2个原子个原子操作操作wait(S)wait(S)和和signal(S)signal(S)来访问。来访问。nwait(S)wait(S)和和signal(S)signal(S)长时间以来被称为长时间以来被称为 P P、V V 操作操作-荷兰语的荷兰语的proberen(test)proberen(test)和和verhogen verhogen(increment)(increment)第二章 进 程 管 理 641.整型信
48、号量（续）整型信号量（续）nP，V操作描述如下：操作描述如下：Var S:int;procedure P(S)while S=0 do no-op；S-;procedure V(S)S+;n缺点：若缺点：若S=0,S=0,则则P P操作会不断测试，不满足操作会不断测试，不满足“让权等让权等待待”,即即“忙等忙等”。P 操作，意味着请操作，意味着请求分配一个单位资求分配一个单位资源源Semaphore定义定义V 操作，意味着释操作，意味着释放一个单位资源放一个单位资源第二章 进 程 管 理 652.记录型信号量记录型信号量n遵循遵循“让权等待让权等待”准则。信号量包括一个代表资源数准则。信号量包
49、括一个代表资源数目的目的整型变量整型变量和一个和一个进程链表。进程链表。n记录型可描述如下：记录型可描述如下：type semaphore=record value:integer;L:list of process;end资源数目资源数目进程链表指针，链进程链表指针，链接所有等待进程接所有等待进程第二章 进 程 管 理 662.记录型信号量（续）记录型信号量（续）P，V操作描述如下：操作描述如下：procedure P(S)var S:semaphore;begin S.value:=S.value-1;if S.value0 then block(S.L)endprocedure V(S)
50、var S:semaphore;begin S.value:=S.value+1;if S.value0：S.value表示可用资源的个数表示可用资源的个数 nS.value=0：表示无资源可用：表示无资源可用 nS.value=1 and S2=1 and and Sn=1)then for i:=1 to n do Si:=Si-1;endfor else 将该进程放入第一个将该进程放入第一个Si=ti，表示资源数量低于表示资源数量低于ti时，便不予分配），时，便不予分配），需求值需求值为为di（用于信号量的增减，即用于信号量的增减，即Si=Si di或或Si=Si+di）。）。第二章 进
