《计算机操作系统---第2章进程管理.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统---第2章进程管理.ppt（182页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2 2章章 进程管理进程管理主要内容2.1 进程的基本概念进程的基本概念2.2 进程控制进程控制2.3 进程同步进程同步2.4 经典进程的同步问题经典进程的同步问题2.5 进程通信进程通信2.6 线程线程11/19/20222本章重点本章重点进程的定义；进程的结构特征；进程控制块的作用；进程同步的概念信号量机制；经典进程的同步问题；进程通信的类型什么是线程及为什么要引入线程进程同步机制及其应用本章难点本章难点11/19/20223本章学习建议：在掌握进程及进程同步的基本概念的基础上，熟记信号量机制的定义；通过信号量机制的应用及对经典进程同步问题的分析，能够解决常见问题的同步本章学时：10学
2、时11/19/202242.1.1 程序的顺序执行及其特征程序的顺序执行及其特征2.1.2 前驱图前驱图2.1.3 程序的并发执行及其特征程序的并发执行及其特征2.1.4 进程的特征与状态进程的特征与状态2.1.5 进程控制块进程控制块2.1 2.1 进程的基本概念进程的基本概念P34P34本节主要内容：返回返回11/19/20225本节学习目标：本节学习目标：2.1 2.1 进程的基本概念进程的基本概念（1）了解程序的顺序执行及其特征）了解程序的顺序执行及其特征（2）会利用前驱图描述进程（或程序）的执行）会利用前驱图描述进程（或程序）的执行（3）掌握程序并发执行的特征）掌握程序并发执行的特征
3、（4）熟练掌握）熟练掌握 进程的定义、特征及基本状态进程的定义、特征及基本状态11/19/20226在多道程序环境下，在多道程序环境下，程序程序不能独立运行。作为资不能独立运行。作为资源分配和独立运行的基本单位是源分配和独立运行的基本单位是进程进程。操作系统。操作系统所有的特征都是基于进程而体现的。所有的特征都是基于进程而体现的。概概 述述11/19/202272.1.1程序顺序执行及其特征1.程序顺序执行I1C1P1I2C2P2一个程序段的多条语句也有一个执行顺序问题：一个程序段的多条语句也有一个执行顺序问题：S1:a:=x+y S2:b:=a-5S3:c:=b+1图图2-1 程序的顺序执行
4、程序的顺序执行S1S2S3图图2-2 语句的顺序执行语句的顺序执行 11/19/202282.程序顺序执行时的特征1)顺序性顺序性2)封闭性封闭性3)可再现性可再现性11/19/20229定义：前驱图是一个定义：前驱图是一个有向无循环图有向无循环图（DAG)。67 注意：前驱图中必须不存在循环不存在循环。12345图中每个结点可用于表示一条语句、一个程序段或进程。结点间的有向边则表示在两结点之间存在的偏序或前驱关系。可用“”表示。2.1.2 前驱图图图2-3 前驱图前驱图11/19/2022102.1.3 程序并发执行及其特征1.程序并发执行I1I2I3I4C1C2C3C4P1P2P3P4上图
5、存在下述前驱关系：(Ii,Ci),(Ii,Ii+1),(Ci,Pi),(Ci,Ci+1),(Pi,Pi+1)图图2-4 程序并发执行的前驱图程序并发执行的前驱图11/19/202211对于下述四条语句的程序段：对于下述四条语句的程序段：S2:b:=y+4S3:c:=a+bS4:d:=c+6图图2-5语句并发执行的前驱图语句并发执行的前驱图S1S2S3S4显然，显然，S1和和S2可以并发执行。可以并发执行。S1:a:=x+2要求：根据给定的描述画出前驱图，并能指出哪些可以要求：根据给定的描述画出前驱图，并能指出哪些可以并发执行，哪些只能顺序执行。并发执行，哪些只能顺序执行。11/19/20221
6、22.程序并发执行时的特征1)间断性间断性 共享资源-相互制约-执行-暂停-执行2)失去封闭失去封闭 性性 一个程序的执行受到其他程序的影响3)不可再现性不可再现性设有两个循环程序A和B共享变量N，A每次执行N+1操作，B每次执行print(N)，N置0。执行情况：（1）N:=N+1 在在print(N)和和N:=0之前，得到的之前，得到的N值分别为值分别为n+1,n+1,0。（2）N:=N+1 在在print(N)和和N:=0之后，得到的之后，得到的N值分别为值分别为n,0,1（3）N:=N+1 在在print(N)和和N:=0之间，得到的之间，得到的N值分别为值分别为n,n+1,0。11/
7、19/202213例如：作业A需要CPU 25,需要DEV1 5,DEV2 10;作业B需要CPU 15,需要DEV1 10,需要DEV2 15。要求：分别求出CPU、DEV1、DEV2的使用率。实例：比较顺序执行和并发执行的性能11/19/202214 CPU利用率=40/80=50%DEV1利用率=15/80=18.75%DEV2利用率=25/80=31.25%t(s)t(s)CPU DEV1 DEV2 CPU CPU A 10 15 20 3040 DEV2 CPU DEV 1 DEV2 CPU B 1020 30 40 25（1 1）在顺序环境下 图图2-6 顺序环境下的程序执行顺序环
8、境下的程序执行11/19/202215（2）在并发环境下图图2-7 并发环境下的程序执行并发环境下的程序执行A AB BCPUCPUDEV1DEV1DEV2DEV2CPUCPUCPUCPU10101515202030304040 t(s)t(s)2525DEV1DEV1CPUCPU35354545DEV2DEV2CPUCPUDEV2DEV2CPU利用率=（2515）/45=89%DEV1利用率=(5+10)/45=33%DEV2利用率=(10+15)/45=56%11/19/2022162.1.4 进程的特征与状态1.进程的特征和定义1)结构特征结构特征从从结构上看，进程实体是由程序段、数据段
9、及进程结构上看，进程实体是由程序段、数据段及进程控制块三部分组成，有人把这三部分统称为控制块三部分组成，有人把这三部分统称为“进程进程映像映像”。11/19/2022172)动态性动态性3)并发性并发性4)独立性独立性5)异步性异步性进程的实质是进程实体的一次执行过程。多个进程在一段时间内同时运行。独立运行、独立分配资源和独立调度按各自独立的、不可预知的速度向前推进。11/19/202218定义：定义：ProcessProcess 进程是程序的一次执行。进程是程序的一次执行。进进程程是是一一个个程程序序及及其其数数据据在在处处理理机机上上顺顺序序执执行时所发生的活动。行时所发生的活动。进进程程
10、是是程程序序在在一一个个数数据据集集合合上上的的运运行行活活动动，是系统进行是系统进行资源分配资源分配和和调度调度的独立单位的独立单位11/19/202219进程模型 物理视角物理视角（进程切换）（进程切换）进程进程A进程进程B进程进程C 逻辑视角逻辑视角（多道并发）（多道并发）进进 程程 A进进 程程 B进进 程程 C 时间视角时间视角（持续推进）（持续推进）进程进程A 进程进程B进程进程C11/19/202220“进程进程”是进程实体的运行过程是进程实体的运行过程,是系统进行是系统进行资源分配和调度的一个独立单位。资源分配和调度的一个独立单位。或者：可并发执行的程序在一个数据集合上或者：可
11、并发执行的程序在一个数据集合上的运行过程。的运行过程。进程的定义：进程的定义：11/19/202221程序与进程之间的区别：程序与进程之间的区别：进程更能真实地描述并发，而程序不能进程更能真实地描述并发，而程序不能进程是由程序和数据及进程是由程序和数据及PCBPCB组成的组成的程序是静态的，进程是动态的程序是静态的，进程是动态的进程有生命周期，有诞生有消亡，短暂进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的的；而程序是相对长久的一个程序可对应多个进程，反之亦然一个程序可对应多个进程，反之亦然进程具有创建其他进程的功能，而程序进程具有创建其他进程的功能，而程序没有没有11/19/202
12、222图图2-8 三个进程三个进程并发执行的图示并发执行的图示11/19/202223图2-9 各进程的轨迹11/19/202224图2-10:3进程并发执行的轨迹11/19/2022252.进程的三种基本状态1)就绪（就绪（Ready）状态状态2)执行状态执行状态3)阻塞（阻塞（Block）状态状态进程分配了除处理机之外的所有资源。进程因发生某事件而暂停执行。11/19/202226执行执行就绪就绪等待等待11/19/202227进程转换就绪-运行调度程序选择一个新的进程运行运行-就绪（产生中断）运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态有一个更短的作业到来11/19
13、/202228运行-等待当一进程必须等待时OSOS尚未完成服务尚未完成服务对一资源的访问尚不能进行对一资源的访问尚不能进行初始化初始化I/O I/O 且必须等待结果且必须等待结果等待某一进程提供输入等待某一进程提供输入 (IPC)(IPC)等待-就绪当所等待的事件发生时进程转换11/19/2022293.进程的挂起状态1)引入挂起状态的原因终端用户的需要父进程的请求操作系统的需要负荷调节的需要由活动到静止，由内存到外存11/19/202230图2-12 具有挂起状态的转换图2）进程状态的转换）进程状态的转换11/19/202231状态转换(中级调度)活动阻塞-静止阻塞静止阻塞-活动阻塞静止就绪
14、-活动就绪当内存中没有就绪进程时活动就绪-静止就绪(较少见)当没有被阻塞的进程，而为了性能上的考虑，必须释放一些内存时11/19/2022324.创建（创建（New）状态和终止状态状态和终止状态2）终止状态）终止状态OS 已完成为创建一进程所必要的工作已构造了进程标识符已构造了进程标识符已创建了管理进程所需的表格已创建了管理进程所需的表格但还没有允许执行该进程(尚未同意)因为资源有限因为资源有限1）创建（创建（New）状态状态 一个进程刚刚建立，还未将它送入就绪队列时的状态。11/19/202233图2-13 五状态进程模型11/19/202234图2-14 七状态进程模型活动活动挂起挂起事件
15、事件发生发生事件事件发生发生等待等待事件事件挂起挂起调度调度超时超时释放释放活动活动挂起挂起11/19/2022352.1.5 进程控制块PCB进程控制块是进程实体的一部分，是操作系统中最重要的记录型数据结构。PCB是进程存在的唯一标志是进程存在的唯一标志。PCB必须常驻内存。必须常驻内存。1.PCB的作用OS中最重要的数据结构,涉及调度、资源分配、中断处理11/19/2022362.PCB中的信息1)进程标识符信息：外部标识符：如计算进程 内部标识符：为方便系统使用而设置的，用整数表示。2)处理机状态信息11/19/2022373)进程调度信息进程状态进程优先级进程调度所需的其它信息 与所采
16、用的调度算法有关事件 即阻塞原因11/19/2022384)进程控制信息程序和数据的地址进程同步和通信机制资源清单链接指针11/19/2022393.PCB的组织方式PCB表：系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表 PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度（注：多道程序中的多道与系统并发度不同）PCB表组织成进程队列：不同状态进程分别组成队列运行队列、就绪队列、等待队列11/19/202240PCB的组织方式1、线性方式；2、索引方式，对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址3、链接方式 11/
17、19/2022411.1.将将所所有有的的PCBPCB部部分分状状态态组组织织在在一一个个连连续续表表（PCBPCB表表）中中。该该方方式式的的优优点点是是简简单单，且且不不需需要要额额外外的的开开销销，适适用用于于数数目目不不是很多的系统。是很多的系统。1.1.线性方式线性方式11/19/202242 如如UNIXUNIX系系统统，但但缺缺点点是是,往往往往需需要要扫扫描描整整个表个表 .如图：如图：PCB1PCB2PCB3PCB4.PCBn11/19/202243 2.2.索引方式索引方式 对对于于具具有有相相同同状状态态的的进进程程，分分别别设设置置各各自自的的PCBPCB索索引引表表，
18、表表目目为为PCBPCB在在PCBPCB表表（线线性性表表）中中的的地地址址，就就构构成成了了就就绪绪索索引引表表和和等待索引表等待索引表.11/19/202244执行指针就绪表指针等待表指针 .PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCBn-1 PCBn就绪索引表就绪索引表等待索引表等待索引表如图：如图：11/19/2022453.3.链接方式链接方式 对对于于具具有有相相同同状状态态的的进进程程的的PCBPCB，通通过过PCBPCB链链接接字字构构成成一一个个队队列列（链链接接字字是是指指出出本本队队列列下下一一PCBPCB在在PCBPCB表表中中的的编编号号或或地地
19、址址）编编号号为为0 0表表示示队队尾尾，队队首首由由内内存存固固定定单单元元中中相相应应的的队队列列指指针针表表示示。如如此此就就形形成了就绪队列和等待队列。成了就绪队列和等待队列。11/19/202246进程控制块（Process Control Block）PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn.空空 PCBPCB运行态运行态就绪态就绪态等待等待1 1等待等待2 26751015返回返回11/19/2022472.2 进程控制P432.2.1 进程的创建 2.2.2 进程的终止2.2.3 进程的阻塞与唤醒2.2.4 进程的挂起与激活本节学习目标本节学习目标：掌握
20、处理机的两种执行状态；熟记原语的定义；了解进程的创建和终止原因；了解进程的阻塞与唤醒过程；了解进程的挂起与激活过程返回返回11/19/202248通常将处理机的执行状态分成系统态系统态和用户态用户态。OS内核通常是运行在系统态的，而进程控制是由内核通常是运行在系统态的，而进程控制是由OS内核内核实现的。实现的。（1）系统态。）系统态。又称为核心态、管态。它具有较高的特权，又称为核心态、管态。它具有较高的特权，能执行一切指令，访问所有寄存器和存储区。能执行一切指令，访问所有寄存器和存储区。（2）用户态。又称目态。具有较低特权的执行状态，它只）用户态。又称目态。具有较低特权的执行状态，它只能执行规
21、定的指令，访问指定的寄存器和存储区。能执行规定的指令，访问指定的寄存器和存储区。概 述11/19/202249 操作系统内核通常将一些与硬件紧密相关的模块诸如中断处理程序中断处理程序，各种常用设备的驱动程序常用设备的驱动程序，以及运行频率较高的模块运行频率较高的模块都安排在紧靠硬件的软件层次中，并使它们常驻内存，以便提高操作系统的运行效率，并对它们加以特殊的保护。通常把这一部分称为OS的内核。内核通常是一些原语原语。原语是通过屏蔽中断屏蔽中断来实现的。11/19/202250原语：是由若干条指令组成的，用于完成一定功能的一个过程。它们是原子操作：一个操作中的所有动作要么全做，要么全不做。11/
22、19/2022512.2.1 进程的创建1.进程图ABCDEFGH进程树11/19/2022522.引起创建进程的事件1)用户登录2)作业调度3)提供服务4)应用请求11/19/2022533.进程的创建由创建原语Creat()完成，具体如下：（1）申请空白PCB（2）为新进程分配资源（3）初始化进程控制块包括：（1）初始化标识符信息（2）初始化处理机状态信息（3）初始化处理机控制信息（4）将新进程插入就绪队列（就绪状态）11/19/2022542.2.2 进程的终止1.引起进程终止的事件1)正常结束（调用Holt指令）2)异常结束3)外界干预包括：（1）操作员或操作系统干预 如发生死锁（2）
23、父进程请求（3）父进程终止11/19/202255异常事件：（1）越界错误。（2）保护错。如试图去写一个只读文件。（3）特权指令错。（4）非法指令错。（5）运行超时。（6）等待超时。（7）算术运算错。（8）I/O故障。11/19/2022562.进程的终止过程（1）根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态；（2）若被终止进程正处于执行状态，应立即终止该进程的执行，并设置调度标志为真，用于指示该进程被终止后应重新进行调度，选择一新进程，把处理机分配给它。（3）若该进程还有子孙进程，还应将其子孙进程予以终止，以防它们成为不可控的。11/19/202257（4
24、）将该进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。（5）将被终止进程从所在队列中移出，等待其它程序来收集信息。2.进程的终止过程（续）11/19/2022582.2.3 进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件1）请求系统服务2）启动某种操作3）新数据尚未到达4）无新工作可做11/19/2022592.进程阻塞过程(block)进程的阻塞是进程自身的一种主动行为。阻塞过程：（1）将PCB中的“执行”改为“阻塞”，插入到阻塞队列；（2）重新调度，将处理机分配给另一就绪进程，并进行切换。11/19/2022603.进程唤醒过程(wakeup)唤醒过程：首先把被阻塞进程从等待该事件
25、的阻塞队列中移出，将其PCB中的现行状态，由阻塞改为就绪，然后再将该进程插入到就绪队列中。11/19/2022612.2.4 进程的挂起与激活1.进程的挂起过程(suspend)过程：首先检查被挂起进程的状态：若正处于活动就绪状态，便将其改为静止就绪；将活动阻塞改为静止阻塞。然后将该进程的PCB复制到指定的内存区域。最后，如被挂起的进程正在执行，则重新调度。11/19/2022622.进程的激活过程(active)过程：首先将进程从外存调入内存，检查该进程的现行状态；假如采用抢占调度策略，则应检查是否重新调度。返回返回11/19/202263本节主要内容：2.3.1 进程同步的基本概念2.3.
26、2 信号量机制2.3.3 信号量的应用2.3.4 管程机制2.3 进程同步P47本节学习目标：熟练掌握进程同步的基本概念；掌握信号量机制；掌握信号量的应用；了解管程机制返回返回11/19/202264进程同步的主要任务是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。概 述11/19/2022651.两种形式的制约关系（1）相关进程与无关进程相关进程：指多个并发进程在逻辑上有某种联系无关进程：在逻辑上无任何联系的进程2.3.1 2.3.1 进程同步的基本概念进程同步的基本概念11/19/202266直接相互制约关系：直接相互
27、制约关系：进程间的相互联系是有意识的安排的，直接作用只发生在相关进程间（相互合相互合作作）间接相互制约关系：间接相互制约关系：进程间要通过某种中介发生联系，是无意识安排的，可发生在相关进程之间，也可发生在无关进程之间（共享资源共享资源）（2）并发进程的制约关系11/19/202267（1）进程的同步（直接相互制约关系）进程的同步：synchronism指系统中多个进程中发生的事件存在某种时序时序关系，需要相互合作，共同完成一项任务。实例：说明：互斥是一种特殊的同步11/19/202268 司机 P1 售票员 P2 while(true)while(true)启动车辆；关门；正常运行；售票；到站
28、停车；开门；一个具体的例子：一个具体的例子：11/19/202269定义：定义：由于各进程要求共享资源，而有些资源需要互斥使用互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥（2 2）进程的互斥（间接相互制约关系）进程的互斥（间接相互制约关系）mutual exclusionmutual exclusion11/19/202270a:=a-1 print(a)a:=a+1 print(a)P1互斥互斥P2互斥互斥If a 0then a:=a+1else a:=a-1P3互斥互斥 进程的互斥进程的互斥一个具体的例子：一个具体的例子：11/19/202271临界资源互斥访问：例
29、如：例如：A,B两个程序共享变量两个程序共享变量n，A对对n执行加执行加1操作，操作，B对对n执行减执行减1操作，用机器语言实现：操作，用机器语言实现：A：register1:=n;（a1）register1:=register1+1;（a2）n:=register1;(a3)临界资源临界资源：critical resource（定义见（定义见P16)描述：描述：系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源临界资源或互斥资源互斥资源2.临界资源11/19/202272设当前n的值为5，由于A，B异步运行，可能会产生下列的序列：a1,a2,b1,b2,a3,b3正确的答案应该是5
30、，但上述的执行结果为4。因此必须互斥地互斥地访问n。B:register2:=n;(b1)register2:=register2-1;(b2)n:=register2;(b3)11/19/202273一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作 或者：把每个进程中访问临界资源的那段代码称为临界区。（CS)3.临界区（互斥区）：critical section11/19/202274一个访问临界资源的循环进程描述如下：repeatEntry sectionCritical section;Exit sectionRemainder section
31、;Until false;进入区 临界区退出区11/19/2022754.同步机制应遵循的原则空闲让进忙则等待有限等待让权等待11/19/2022762.3.2 信号量机制信号量机制是行之有效的进程同步工具学习时注意：1）各种信号量的定义 2）信号量的应用：解决同步问题和互斥问题 11/19/202277整型信号量定义为一个整型量，除初始化外初始化外，仅能通过两个标准的原子操作wait(s)wait(s)和和signal(s)signal(s)来访问，通常称为P、V操作wait(s):while s=0 do no_op s:=s-1;signal(s):s:=s+1;1.整型信号量11/19
32、/2022782）信号量的使用：(1)必须置一次且只能置一次初值,并且初值不能为负数 （2）只能执行P、V操作 整型信号量的缺点缺点：未遵循同步机制的“让权等待让权等待”1）P、V操作为原语操作说明：11/19/2022792.记录型信号量记录型信号量机制的提出是为了解决整型信号量机制不遵循“让权等待让权等待”这一准则。记录型信号量由于采用了记录型的数据结构记录型的数据结构而得名，描述如下：type semaphore=record value:integer;L:list of process;end采用类采用类PASCAL的定的定义形式义形式11/19/202280procedure wa
33、it(S)var S:semaphore;begin S.value:=S.value-1;if S.value0 then block(S.L)endprocedure signal(S)var S:semaphore;begin S.value:=S.value+1;if S.value0表示有S个资源可用S=0表示无资源可用P.V操作讨论P(S):表示申请一个资源 V(S)表示释放一个资源。S.Value的初值表示系统中某类的初值表示系统中某类资源的数目，称为资源的数目，称为资源信号量资源信号量若若S.value初初值为值为1，则称，则称为互斥信号量为互斥信号量S0则|S|表示S等待队列
34、中的进程个数11/19/2022822）P.V操作的优缺点优点：优点：简单，而且表达能力强（用P.V操作可解决任何同步互斥问题）缺点：缺点：不够安全；P.V操作使用不当会出现死锁死锁；遇到复杂同步互斥问题时实现复杂11/19/2022833.AND型信号量设有两个进程设有两个进程A和和B，它们都要求访问共享数据它们都要求访问共享数据D和和E。因此设因此设两个互斥的信号量两个互斥的信号量Dmutex和和Emutex，令初值为令初值为1。则有：。则有：process A:wait(Dmutex);wait(Emutex);process B:wait(Emutex);wait(Dmutex);若进
35、程A和B按下述次序交替执行wait操作：process A:wait(Dmutex);process B:wait(Emutex);process A:wait(Emutex);process B:wait(Dmutex);产生死锁。产生死锁。11/19/202284将进程在整个运行过程中需要的所有资源，一次性全部将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给它。也不分配给它。ANDA
36、ND同步机制的基本思想是：同步机制的基本思想是：11/19/202285place the process in the waiting queue associated with the first Si found with Si=ti；即当资源数量低于ti时，便不予分配）占用值占用值为为d di i（表示资源的申请量，即Si=Si-di）对应的P、V原语格式为：Swait(S1,t1,d1;.;Sn,tn,dn);Ssignal(S1,d1;.;Sn,dn);设置：11/19/202289在信号量集机制中，Swait操作描述如下，其中S为信号量，d为需求量，t为下限值。Swait(S1,
37、t1,d1,Sn,tn,dn)if S1 t1 and and Sn tn then for i:=1 to n do Si:=Si-di;endforelseendifSsignal(S1,d1,Sn,dn)for i:=1 to n do Si:=Si+di;endfor;11/19/202290“信号量集信号量集”的几种特殊情况：的几种特殊情况：（1）Swait(S,d,d)。（2）Swait(S,1,1)。蜕化为一般的记录型信号量（S1)或互斥信号量（S=1）。（3）Swait(S,1,0)。当S 1时，允许多个进程进入某特定区；当S变为0时，将阻止任何进程进入特定区。相当于一个可控开
38、关。11/19/2022911.利用信号量实现互斥2.3.3 信号量的应用用用P P、V V操作解决进程间互斥问题操作解决进程间互斥问题P(mutex)V(mutex)P(mutex)P(mutex)V(mutex)V(mutex)11/19/202292利用记录型信号量实现进程互斥的进程可描述如下：var mutex:semaphore:=1;begin parbegin process1:begin repeat wait(mutex);cs signal(mutex);remainder section until falseend11/19/202293 wait(mutex);cs
39、signal(mutex);remainder section until false endparendprocess 2:begin repeat注：注：wait和和signal必须成对出现必须成对出现11/19/2022942.利用信号量来描述前驱关系设有两个并发执行的进程P1和P2，要求P1中的语句S1先于P2中的S2执行。设一公共信号量s，初值为0。在在进程进程P1中：用中：用S1；signal(s);在在进程进程P2中：用中：用wait(s);S2;S1S2S3S4S5S6abcdefg11/19/202295 begin wait(d);S5;signal(g);end;begi
40、n wait(e);wait(f);wait(g);S6;end;parendendvar a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;begin parbegin begin S1;signal(a);signal(b);end;begin wait(a);S2;signal(c);signal(d);end;begin wait(b);S3;signal(e);end;begin wait(c);S4;signal(f);end;11/19/2022962.3.4 管程机制信号量机制的不足：每个要访问临界资源的进程必须自备同步操作wait(s)和signa
41、l(s)例子：例子：错误1在利用互斥信号量mutex实现进程互斥时，将wait(s)和signal(s)颠倒，即signal(mutex);cs;wait(mutex);这样可能会有几个进程同时进入临界区。这样可能会有几个进程同时进入临界区。11/19/202297错误错误2在实现进程互斥时，将程序中的signal(mutex)误写为wait(mutex),即wait(mutex);cs;wait(mutex);这样可能会发生死锁。这样可能会发生死锁。基于上述情况，提出了管程(Monitors）概念。11/19/2022981.管程的定义系统中的所有硬件资源和软件资源，均可用数据结构加系统中的
42、所有硬件资源和软件资源，均可用数据结构加以抽象地描述，即用以抽象地描述，即用少量信息和对该资源所执行的操作少量信息和对该资源所执行的操作来表征该资源，而忽略了它们的内部结构和实现细节。来表征该资源，而忽略了它们的内部结构和实现细节。如，一个如，一个FIFO队列，可用其队长、队首和队尾以及在该队队列，可用其队长、队首和队尾以及在该队列上所执行的一组操作来描述。列上所执行的一组操作来描述。11/19/202299管程由三部分组成：（1）局部于管程的共享变量说明（2）对该数据结构进行操作的一组过程（3）对局部于管程的数据设置初始值的语句。管程的定义：一个管程定义了一个数据结构和能为并发进程所执行（在
43、该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。管程：一种同步机制管程：一种同步机制11/19/2022100管程的形式管程的形式TYPE monitor_name=MONITOR;共享变量说明PROCEDURE 过程名（形参表）；过程局部变量说明；BEGIN语句序列；END;.11/19/2022101FUNCTION 函数名（形参表）：值类型；函数局部变量说明；BEGIN语句序列；END;.BEGIN共享变量初始化语句序列；END;11/19/2022102共享数据 一组操作进程初始化代码条件（不忙）队列进入队列管程的示意图11/19/2022103说明：局部于管程的数据结
44、构，仅能被局部于管程的过程所访问；反之，局部于管程的过程也仅能访问管程内的数据结构。可以把管程看作是围墙。11/19/2022104 管程的三个主要的特性：（一）模块化，一个管程是一个基本程序单位，可以单独编译（二）抽象数据类型，管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码（三）信息隐藏，管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的11/19/2022105 管程有如下几个要素：（一）管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量（二）为了保证管程
45、共享变量的数据完整性，规定管程互斥进入（三）管程通常是用来管理资源的，因而在管程中应当设有进程等待队以及相应的等待及唤醒操作11/19/2022106管程和进程的异同点：（1）设置进程和管程的目的不同（2）系统管理数据结构 进程：PCB 管程：等待队列（3）管程被进程调用（4）管程是操作系统的固有成分，无创建和撤消11/19/2022107利用管程解决生产者、消费者问题首先定义管程（1）put(item)（2）get(item)11/19/20221082.4 2.4 经典进程的同步问题经典进程的同步问题P58P58包括：包括：生产者消费者问题、读者写者问题、生产者消费者问题、读者写者问题、哲
46、学家进餐问题哲学家进餐问题问题：如何描述进程同步问题？先写出对问题的初步描述（用汉语，流程）问题中存在的关系（互斥、同步，各有几种）问题的初始状态（用于信号量初值的设置）把P、V操作放到合适的位置11/19/2022109本节主要内容：本节主要内容：2.4.1 生产者生产者消费者问题消费者问题2.4.2 哲学家进餐问题哲学家进餐问题2.4.3 读者读者写者问题写者问题本节学习目标：掌握三个经典进程同步问题所本节学习目标：掌握三个经典进程同步问题所解决的同步问题；理解并会分析三个经典进程解决的同步问题；理解并会分析三个经典进程同步问题，重点掌握生产者同步问题，重点掌握生产者消费者问题消费者问题1
47、1/19/20221102.4.1 2.4.1 生产者消费者问题生产者消费者问题描述如下：描述如下：有一些进程生成产品，称为生产者；有一些进程使用产品，称为消费者。生产者和消费者必须同步生产者和消费者必须同步。设置一缓冲池用来暂存产品；设置一缓冲池用来暂存产品；互斥问题：互斥问题：缓冲池属于临界资源，对缓冲池的操作缓冲池属于临界资源，对缓冲池的操作必须互斥进行；必须互斥进行；11/19/2022111同步问题：生产者进程不能往“满”的缓冲区中放产品，设置信号量为empty,消费者进程不能从“空空”的缓冲区中取产品，设置信号量full.empty和full分别表示缓冲池中空缓冲区上数量和满缓冲区
48、的数量。11/19/2022112消费者消费者生产者生产者单缓冲单缓冲1.利用记录型信号量解决生产者消费者问题11/19/2022113P(生产者）：while (true)生产一个产品生产一个产品;P(empty);送产品到缓冲区送产品到缓冲区;V(full);Q（消费者）：while (true)P(full);从缓冲区取产品;V(empty);消费产品;empty初值为1，full初值为011/19/202211411/19/2022115多个缓冲区的生产者-消费者问题(1)P：i=0;while(true)生产产品;P(empty);往Buffer i放产品;V(full);i=(i+
49、1)%n;Q：j=0;while(true)P(full);从Bufferj取产品;V(empty);消费产品;j=(j+1)%n;11/19/2022116【思考题思考题】要不要对缓冲区（临界资源）要不要对缓冲区（临界资源）进行互斥操作？进行互斥操作？存在问题存在问题：1)会造成多个生产者向同一个缓冲区会造成多个生产者向同一个缓冲区放产品；放产品；2)会造成多个消费者从同一个缓冲区会造成多个消费者从同一个缓冲区取产品取产品11/19/2022117Q：j=0;while(true)P(full);P(mutex);从Bufferj取产品;V(mutex);V(empty);消费产品;j=(j
50、+1)%n;P：i=0;while(true)生产产品;P(empty);P(mutex);往Buffer i放产品;V(mutex);V(full);i=(i+1)%n;是否有错误？是否有错误？若颠倒两个若颠倒两个P操作的顺序？操作的顺序？多个缓冲区的生产者-消费者问题(2)11/19/2022118Q：j=0;while(true)P(full);P(mutex);从从Bufferj取产品取产品;j=(j+1)%n;V(mutex);V(empty);消费产品消费产品;P：i=0;while(true)生产产品;P(empty);P(mutex);往Buffer i放产品;i=(i+1)%