第2章进程管理.pptx

《第2章进程管理.pptx》由会员分享，可在线阅读，更多相关《第2章进程管理.pptx（162页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、2023/3/271前趋图已知一个求值公式（A2+5B）/(B+2A),若A,B已赋值，试画出该公式求值过程的前趋图。试画出下面四条语句的前趋图：S1:a=x+2;S2:b=a+4;S3:c=a+5S4:d=c+b信号量应用中用PV操作实现前趋图所表示的前趋关系第1页/共162页2023/3/272进程定义进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。第2页/共162页2023/3/273进程的特征（五个基本特征）结构特征：进程是由程序段、数据段、进程控制块三部分组成第3页/共162页2023/3/274进程的特征（五个基本特征）动态性：（最基本特征）进程是程序的一次执行过

2、程。“进程”是一个动态的概念。程序是一组有序指令的集合，在多道程序设计环境下，它不涉及“执行”，因此是一个静态的概念。可以这么来理解，一套电影拷贝相当于一个程序，它可以长期保存；该拷贝在电影院的一次放映，就相当于一个进程。进程有生命周期。进程既然是程序的执行，或者说是“一次运行活动”。因此当系统要完成某一项工作时，它就“创建”一个进程，以便能去执行事先编写好的、完成该工作的那段程序。程序执行完毕，完成了预定的任务后，系统就“撤消”这个进程，收回它所占用的资源。一个进程创建后，系统就感知到它的存在；一个进程撤消后，系统就无法再感知到它。于是，从创建到撤消，这个时间段就是一个进程的“生命期”。进程

3、的存在是暂时的。而程序的存在是永久的。第4页/共162页2023/3/275进程的特征（五个基本特征）并发性：多个进程可同存于内存中，能在一段时间内同时运行（重要特征，也是os重要特征）。这正是引入进程的目的，而程序（在没有为它创建进程时）的并发执行具有不可再现性，因此程序不能正确的并发执行。第5页/共162页2023/3/276进程的特征（五个基本特征）独立性：独立运行的基本单位，独立获得资源和调度的基本单位。（目前有些变化）。而因程序（在没有为它创建进程时）不具有PCB，所以它是不可能在多道程序环境下独立运行的。第6页/共162页2023/3/277进程的特征（五个基本特征）异步性：各进程

4、按各自独立的不可预知的速度向前推进第7页/共162页2023/3/278进程与程序的区别进程是程序在处理机上的一次执行过程，是一个动态的概念；而程序是代码的有序集合，其本身没有任何运行的含义，是静态的概念。进程是一个状态变化的过程，是有生命周期的（因创建而产生，因调度而执行，因得不到资源而暂停等，因撤消而消亡）；而程序是永久的，可以长久保存。进程与程序的组成不同。进程是由程序、数据和进程控制块组成的；程序仅是代码的有序集合。进程与程序之间不是一一对应的。通过多次运行，同一个程序可以对应多个进程；通过调用关系，一个进程可以包含多个程序。第8页/共162页2023/3/2792.2.进程的三种基本

5、状态就绪状态（Ready）：存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行。这些进程所处的状态为就绪状态。执行状态（Running）：正在运行的进程所处的状态为执行状态。阻塞状态（Blocked）：正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃CPU而处于暂停状态，称该进程处于等待状态、阻塞状态。典型事件：请求I/O，申请缓冲空间等。第9页/共162页2023/3/2710一个进程的状态，可以随着自身的推进和外界环境的变化而变化，从而使其从一种状态变迁到另一种状态。下图是进程状态变迁图，箭头表示的是状态变迁的方向，旁边标识的文字是引起这种状态变迁的

6、原因。第10页/共162页2023/3/2711具有挂起状态的进程状态图调度时间片用完I/O完成I/O完成n挂起状态,当用户在自己的程序运行期间发现有可疑问题时,希望暂时使自己的程序静止下来,这种静止状态称为挂起状态.第11页/共162页2023/3/2712进程的创建状态创建状态：创建一个进程一般要通过两个步骤:为一个新进程创建PCB，并填写必要的管理信息；把该进程转入就绪状态并插入就绪状态之中。引入创建状态,是为了保证进程的调度必须在创建工作完成后进行,以确保对进程控制块操作的完整性。第12页/共162页2023/3/2713进程的终止状态终止状态：终止一个进程一般要通过两个步骤:等待操作

7、系统进行善后处理；将PCB清零，并将PCB空间返还系统。增加的状态NULL-创建创建-活动就绪创建-静止就绪执行-终止第13页/共162页2023/3/2714创建状态连接就绪状态终止状态连接执行状态创建终止许可释放第14页/共162页2023/3/2715调度时间片用完I/O完成I/O完成创建许可终止释放第15页/共162页2023/3/2716练习u下列进程状态转换中，绝对不可能发生的状态转换是（），一般不会发生的状态转换是（）A 就绪执行，B 执行就绪 C 就绪阻塞D 阻塞就绪 E 阻塞执行 F 执行阻塞第16页/共162页2023/3/2717练习某系统的进程状态变迁图如下图所示，引起

8、各种状态变迁的典型事件有哪些？系统中常常由于某一进程的状态变迁引起另一进程也产生状态变迁，试判断在下述情况下，如果有的话，将会发生什么因果变迁：3121324134（3）在什么情况下，如果有的话，下述变迁中哪些将不立即引起其他变迁？1234（4）引起进程状态发生变迁的原因是什么？执行就绪阻塞 2314第17页/共162页2023/3/27183.进程控制为了管理和控制进程，系统在创建每一个进程时，都为其开辟一个专用的存储区，用以随时记录它在系统中的动态特性。而当一个进程被撤消时，系统就收回分配给它的存储区。通常，把这一存储区称为该进程的“进程 控 制 块”PCB（ProcessControlB

9、lock）。第18页/共162页2023/3/2719 进程控制块（Process Control BlockProcess Control Block）为了描述和控制进程的运行，系统为每个进程定义了一个数据结构-进程控制块，它是进程实体的一部分，是操作系统中最重要的记录型数据结构。第19页/共162页2023/3/2720 进程控制块的作用进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯

10、一标志进程与PCB是一一对应的第20页/共162页2023/3/2721随操作系统的不同，PCB的格式、大小以及内容也不尽相同。一般地，在PCB中大致应包含4方面的信息。进程描述信息CPU状态信息进程调度信息进程控制信息PCBPCB中的信息第21页/共162页2023/3/2722进程控制进程控制就是对系统中的所有进程实施管理，进程控制一般用原语来实现。所谓原语是一种特殊的系统功能调用，它可以完成一个特定的功能，其特点是原语执行时不可被中断，既具有“原子性”。第22页/共162页2023/3/2723常用的进程控制原语创建原语终止原语阻塞原语、唤醒原语挂起原语、激活原语第23页/共162页20

11、23/3/2724进程的创建 引起进程创建的事件用户登录作业调度提供服务应用请求进程创建的过程为新进程分配唯一的进程标识符，并从PCB队列中申请一个空闲PCB。为新进程的程序和数据，以及用户栈分配相应的主存空间及其它必要分配资源。初始化PCB中的相应信息，如标识信息、处理器信息、进程控制信息等。如果就绪队列可以接纳新进程，便将新进程加入到就绪队列中。第24页/共162页2023/3/2725进程的终止引起进程终止的事件正常结束异常结束外界干预进程终止的过程根据被终止进程的标识符，从PCB集合中检索该进程的PCB，读出进程状态。若该进程处于执行状态，则立即终止该进程的执行。若该进程有子孙进程，还

12、要将其子孙进程终止，并准备重新分配CPU。将该进程所占用的资源回收，归还给其父进程或操作系统。将被终止进程的PCB从所在队列中移出，并撤消该进程的PCB。第25页/共162页2023/3/2726进程的阻塞与唤醒阻塞：当一个进程所期待的某一事件尚未出现时，该进程调用阻塞原语将自己阻塞。进程阻塞是进程的自身的一种主动行为。唤醒：处于阻塞状态的进程是绝不可能叫醒它自己的，它必须由它的合作进程用唤醒原语唤醒它。第26页/共162页2023/3/2727进程的阻塞引起进程阻塞的事件请求系统服务启动某种操作新数据尚未到达无新工作可做进程阻塞的过程立即停止执行该进程。修改PCB中的相关信息。把进程控制块中

13、的运行状态由“执行”状态改为“阻塞”状态，并填入等待的原因，以及进程的各种状态信息。把PCB插入到阻塞队列。根据阻塞队列的组织方式，把阻塞进程的进程控制块插入到阻塞队列中。转调度程序重新调度，运行就绪队列中的其他进程。第27页/共162页2023/3/2728进程的唤醒引起进程唤醒的事件请求系统服务得到满足启动某种操作完成新数据已经到达有新工作可做进程唤醒的过程从阻塞队列中找到该进程。修改该PCB的相关内容。把阻塞状态改为就绪状态，删除等待原因等等。把进程控制块插入到就绪队列。按照就绪队列的组织方式，把被唤醒的进程的PCB插入到就绪队列中。第28页/共162页2023/3/2729进程的唤醒B

14、lock原语和wakeup原语是一对作用刚好相反的原语，因此，如果在进程中调用了阻塞原语，则必须在与之相合作的另一进程中或其他相关进程中安排唤醒原语，以能唤醒阻塞进程。第29页/共162页2023/3/2730进程的挂起与激活引起进程挂起的事件（suspend）用户进程请求将自己挂起父进程请求挂起子进程进程挂起的过程检查进程状态：有活动就绪转为静止就绪有活动阻塞转为静止阻塞把该进程的PCB复制到某指定的内存区域若进程正在执行，则转调度程序重新调度，运行就绪队列中的其他进程。第30页/共162页2023/3/2731进程的激活(active)引起进程激活的事件父进程或用户进程请求将挂起进程激活进

15、程激活的过程将进程调入内存检查进程状态：有静止就绪转为活动就绪有静止阻塞转为活动阻塞在抢占策略中，有可能转调度程序重新调度。第31页/共162页2023/3/2732在多道程序设计环境里，同时会创建多个进程。当计算机系统只有一个CPU时，每次只能让一个进程运行，其他的进程或处于就绪状态，或处于阻塞状态。为了对这些进程进行管理，操作系统要做两件事。（1）把处于相同状态的进程的PCB，通过各自的队列指针链接在一起，形成一个个队列。（2）为每一个队列设立一个队列头指针，它总是指向排在队列之首的进程的PCB。4.进程组织第32页/共162页2023/3/2733在单CPU系统，任何时刻系统中都只有一个

16、进程处于执行状态，因此执行队列中只能有一个PCB；系统中所有处于就绪状态的进程的PCB排成一队，称其为“就绪队列”。一般地，就绪队列中会有多个进程的PCB排在里面，它们形成处理机分配的候选对象。如果就绪队列里没有PCB存在，则称该队列为空；所有处于阻塞状态进程的PCB，应该根据阻塞的原因进行排队，每一个都称为一个“阻塞队列”。比如等待磁盘输入/输出进程的PCB排成一个队列，等待打印机输出进程的PCB排成一个队列等。所以，系统中可以有多个阻塞队列，每个阻塞队列中可以有多个进程的PCB，也可以为空。下图是进程各队列的示意图。第33页/共162页2023/3/2734第34页/共162页2023/3

17、/2735PCB表：系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表 常用的组织方式有链接方式和索引方式两种。PCB组织方式总结第35页/共162页2023/3/2736链接结构相同状态的进程PCB组成一个链表，不同状态对应多个不同的链表 第36页/共162页2023/3/2737索引结构对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址第37页/共162页2023/3/2738练习如果系统中有5个进程，执行的进程最多几个，最少几个；就绪进程最多几个，最少几个；等待进程最多几个，最少几个？第38页/共162页2023/3/2739练习为使进程

18、由活动就绪转变为静止就绪，应用（）原语；为使进程由执行状态转变为阻塞状态，应利用（）原语；为使进程由静止就绪变为活动就绪，应利用（）原语；为使进程从阻塞状态变为就绪状态，应利用（）原语。第39页/共162页2023/3/2740 进程同步1 进程同步的基本概念2 实现临界区互斥的基本方法3 信号量4 管程5 经典同步问题第40页/共162页2023/3/27411 1基本概念进程同步的主要任务:是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性第41页/共162页2023/3/2742 多道程序间有两种制约关系：间接制约：多个操作不能同时执行，如：操作和操作不能在

19、同时执行。（资源共享关系）直接制约：对于进程操作的时间顺序所加的某种限制，如操作应在之前执行。（相互合作关系）第42页/共162页2023/3/27432 实现临界区互斥的基本方法临界资源(criticalresource)：一次仅允许一个进程访问的资源。临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。并发进程对临界资源的访问必须作某种限制，否则就可能出与时间有关的错误，如：联网售票。诸进程之间用互斥的方式，实现对这种资源的共享第43页/共162页2023/3/2744临界区(criticalsection)：临界段，在每个进程中访问临界资源的那段程序代码。注意：临界区是对某一临界

20、资源而言的，对于不同临界资源的临界区，它们之间不存在互斥。如有程序段A、B是关于变量X的临界区，而C、D是关于变量Y的临界区，那么，A、B之间需要互斥执行，C、D之间也要互斥执行，而A与C、B与D之间不用互斥执行。进入区：临界区前检查临界资源是否被使用的代码段。退出区：临界区后将临界资源恢复未被使用的代码段。剩余区：上述三个区以外的代码区域。第44页/共162页2023/3/2745同步机制应遵循的准则为了禁止两个进程同时进入临界区内,可以采用软件办法或系统提供的同步机构来协调它们的关系。但是，不论用什么办法都要遵循下述准则（评判的标准）:1.空闲让进：无进程处于临界区时应允许一个请求进入临界

21、区的进程立即进入临界区。2.忙则等待：每次至多有一个进程处于临界区3.有限等待:当有若干进程欲进入它的临界区时,应在有限时间内使进程进入临界区。以免限入“死等”状态4.让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程应陷入“忙等”。第45页/共162页2023/3/2746互斥与同步的实现 对于互斥，可以将这些方法统一描述为：临界区入口手段；临界区；临界区出口手段；临界区本身是无须改变的，关键是设计出有效的出入口方案，来实现临界区原则。第46页/共162页2023/3/2747一种卓有成效的进程同步工具信号量机制由“信号量”和“P，V操作”两部分组成。信号量就是一种特殊变量，

22、它用来表示系统中资源的使用情况，它只能由两个标准原语所访问，分别记作P操作原语，V操作原语，P，V操作是由操作系统提供的可供外部调用的两条原语。3 信号量机制第47页/共162页2023/3/27481整型信号量的概念概念整型信号量就是一个整型变量。信号量的操作：（1）wait(S)：称为P操作，描述为：wait（S）:whiles=0dono_op;当S=0时，一直在检测S=S-1；（2）signal(S)：称为V操作，描述为：signal（S）S=S+1；缺点：忙等第48页/共162页2023/3/27492 2记录型信号量：在整型信号量机制中的P操作，只要是信号量S0，就会不断地测试。因

23、此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。第49页/共162页2023/3/27502 2记录型信号量：为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：第50页/共162页2023/3/2751信号量机制：定义如下：typesemaphore=recordvalue:int

24、eger;（资源数目）L:listofprocess;（进程链表）end信号量说明：var S semaphore;第51页/共162页2023/3/2752P P操作P(s)s.value=s.value-1;if(s.value 0)block(s.L)该进程状态置为等待状态 将该进程的PCB插入相应的等待队列末尾;P操作有可能导致两种结果：当S的入口值大于或等于1时，当前进程继续运行；当S的入口值小于1时，当前进程进入等待队列。第52页/共162页2023/3/2753说明对于P操作：uS.Value的初值表示系统中某类资源的数目，对它的每次wait操作，意味着进程请求一个单位的该类资源

25、。u当S.value0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。u此时（S.value0）S.value的绝对值表示在该信号量链表中已阻塞进程的数目。第53页/共162页2023/3/2754V V操作V(s)s.value=s.value+1;if(s.value=ti；即当资源数量低于ti时，便不予分配）需求值为di（表示资源的申请量，即Si=Si-di）对应的操作格式为：Swait(S1,t1,d1;.;Sn,tn,dn);Ssignal(S1,d1;.;Sn,dn);第62页/共162页2023/3/2763Swai

26、t(S1,t1,d1;.;Sn,tn,dn)ifSit1andandSntnthenfori=1tondoSi=Si-di;endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSitiandsetitsprogramcountertothebeginningoftheSwaitOperation.endif第63页/共162页2023/3/2764Ssignal(S1,d1;.;Sn,dn);fori=1tondoSi=Si+di;Removealltheprocesswaitinginthequeueassoc

27、iatedwithSiintothereadyqueueendfor;第64页/共162页2023/3/2765信号量集可以用于各种情况的资源分配和释放，几种特殊情况：Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配Swait(S,1,1),当S1时，表示记录型信号量；当S=1时，表示互斥信号量Swait(S,1,0)可作为一个可控开关（当S1时，允许多个进程进入特定区域；当S=0时，禁止任何进程进入该特定区域）一般信号量集未必成对使用Swait和Ssignal：如：一起申请，但不一起释放第65页/共162页2023/3/2766练习若信号量S的初值为2，当前值为-1，则表

28、示有_等待进程。A、0个B、1个C、2个D、3个n设有4个进程共享一程序段，而每次最多允许2个进程进入该程序段，则信号量的取值范围是_。第66页/共162页2023/3/2767设与某资源相关联的信号量初值为3，当前值为1，若M表示该资源的可用个数，N表示等待该资源的进程数，则M，N分别是（）。（2010年考研全国统考）A、0，1B、1，0C、1，2D、2，0第67页/共162页2023/3/2768利用P、V操作解决互斥概念：互斥信号量是根据临界资源的类型设置的。有几种类型的临界资源就设置几个互斥信号量。它代表该类临界资源的数量，或表示是否可用，其初值一般为“1”。第68页/共162页202

29、3/3/2769图：图：第69页/共162页2023/3/2770信号量及P,V操作讨论 对于两个并发进程，互斥信号量的值仅取1、0和-1三个值若1表示没有进程进入临界区若0表示有一个进程进入临界区若-1表示一个进程进入临界区，另一个进程等待进入。第70页/共162页2023/3/2771用PV操作解决进程的前趋关系若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求，为了描述方便，可以用一个前趋图来表示进程集合的执行次序。第71页/共162页2023/3/2772例如图，试用信号量实现这三个进程的同步。设有两个信号量SB、SC，初值均为

30、VarSB,SC;semaphore=0,0;beginparbegin beginPa;V(SB);V(SC);end;beginP(SB);Pb;end;beginP(SC);Pc;end;parendendPaPbPcSBSC第72页/共162页2023/3/2773【思考题】如图，试用信号量实现这三个进程的同步。如图，试用信号量实现这三个进程的同步。P3P1P2S1S2第73页/共162页2023/3/2774解设有两个信号量S1、S2，初值均为VarS1,S2;semaphore=0,0;beginparbegin beginPa;V(S1);end;beginPb;V(S2);en

31、d;beginP(S1);P(S2);Pc;end;parendend第74页/共162页2023/3/2775利用PV操作实现一般同步用信号量机制实现同步，只要找出进程之间的同步关系，并为每种同步关系设置一信号量，然后再在需要等待某种动作的地方插入P操作，在被等待的动作完成之后插入V操作。第75页/共162页2023/3/2776第76页/共162页2023/3/2777【思考题】司机进程：while(1)启动车辆正常驾驶到站停车售票员进程：while(1)关门售票开门用用P.VP.V操作解决司机与售票员的问题操作解决司机与售票员的问题第77页/共162页2023/3/2778解设有两个信号

32、量S1，S2，初值均为0。司机进程：while(1)P(S1)启动车辆正常驾驶 到站停车 V(S2)售票员进程：while(1)关门 V(S1)售票 P(S2)开门第78页/共162页2023/3/27795、经典同步问题1、生产者消费者问题生产者消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费（使用）或生产（释放）某类资源。这些资源可以是硬件资源，也可以是软件资源。当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。而当某一进程释放某一资源时，它就相当于生产者。第79页/共162页2023/3/2780生产者消费者问题问题1：设某计算进程和打印进程共用一个单缓冲区

33、，进程负责不断地计算数据并送入缓冲区中，进程负责不断地从缓冲区中取出数据去打印。第80页/共162页2023/3/2781分析通过分析可知，、必须遵守以下同步规则：当进程把计算结果送入缓冲区时，IOP进程才能从缓冲区中取出结果去打印;当IOP进程把缓冲区中的数据取出打印后，进程才能把下一个计算结果送入缓冲区第81页/共162页2023/3/2782解为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区中有无数据，Sb表示缓冲区中有无空位置。两个进程的同步可以描述如下：第82页/共162页2023/3/2783生产者消费者问题问题2：一组生产者通过具有N个缓冲区的共享缓冲池向一组消费者提供数据。

34、问问题题2 2只只是是在在问问题题1 1的的基基础础上上增增加加了了对对缓缓冲冲池池的的共共享享关关系系，因因此此需需要要互互斥斥信信号号量量mutexmutex使使诸诸进进程程对对缓缓冲冲池池实实现互斥访问；现互斥访问；同同样样利利用用emptyempty和和fullfull计计数数信信号号量量分分别别表表示示空空缓缓冲冲及及满满缓冲的数量。缓冲的数量。第83页/共162页2023/3/2784问题分析为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用empty表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用full表示，初值为。由于在此问题中有M个生产者

35、和N个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为。第84页/共162页2023/3/2785问题的解消费者：out:=0;repeat P(full);P(mutex);nextc:=buffer(out);/从Bufferout取产品;out=(out+1)mod n;V(mutex);V(empty);消费产品;Until false;生产者：in:=0;repeat生产产品;P(empty);P(mutex);buffer(in):=nextp/往Bufferin放产品;

36、in=(in+1)modn;V(mutex);V(full);Untilfalse;第85页/共162页2023/3/2786注意在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对的出现对资源信号量empty和full的P和V操作，同样需要成对地出现，但它们分别处于不同的程序中。在每个程序中的多个P操作顺序不能颠倒。先同步后互斥第86页/共162页2023/3/2787V操作是否可取消消费者：out:=0;repeat P(full);P(mutex);nextc:=buffer(out);/从Bufferout取产品;out=(out+1)MOD n;V(mutex);/*

37、V(empty)*/消费产品;Until false;生产者：in:=0;repeat生产产品;P(empty);P(mutex);buffer(in):=nextp/往Bufferin放产品;in=(in+1)MODn;V(mutex);/*V(full);*/Untilfalse;如果取消V(full)消费者始终因P(full)语句被送入进程链表进行等待，无法访问缓冲池，造成无限等待。同样如果取消V(empty)操作，我们分析程序可知，消费者消费产品的消息无法通知生产者，到一定时候，就会出现有空间，但生产者却无存放产品的空间，生产者进程被阻塞，造成无限等待。第87页/共162页2023/3

38、/2788P，V操作变换顺序消费者：out:=0;repeat P(mutex);P(full);nextc:=buffer(out);/从Bufferout取产品;out=(out+1)MOD n;V(mutex);V(empty)消费产品;Until false;生产者：in:=0;repeat生产产品;P(empty);P(mutex);buffer(in):=nextp/往Bufferin放产品;in=(in+1)MODn;V(full);V(mutex);Untilfalse;P(full)与P(mutex)互换位置后，因为mutex是全局变量，执行完P(mutex)后，mutex值

39、为0，若full也为0，消费者进程会转入进程链表进行等待，而生产者因为mutex值为0而进行等待，使full始终为0，这样就形成了死锁。V(full)与V(mutex)互换位置不会引起死锁，只是使临界资源的释放略为推迟一些。第88页/共162页2023/3/2789改错题消费者：out:=0;repeat wait(mutex);wait(full);nextc:=buffer(out);/从Bufferout取产品;out=(out+1)MOD n;signal(mutex);消费产品;Until false;生产者：in:=0;repeat生产产品;wait(mutex);wait(ful

40、l);buffer(in):=nextp/往Bufferin放产品;in=(in+1)MODn;signal(mutex);Untilfalse;第89页/共162页2023/3/2790【思考题】用P.V 操作解决下图之同步问题提示：分别考虑对缓冲区S和T的同步，再合并考虑getcopyputst第90页/共162页2023/3/2791解设置四个信号量Sin=1，Sout=0，Tin=1，Tout=0；get：while（1）P(Sin）;将数放入将数放入S;V(Sout);copy：while（1）P(Sout）;P(Tin）;将数从将数从S取出放入取出放入T;V(Tout);V(Sin

41、);put：while（1）P(Tout）;将数从将数从T取走取走;V(Tin);第91页/共162页2023/3/2792【思考题】桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。提示：设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。第92页/共162页2023/3/2793解设置三个信号量S,So,Sa，初值分别为1，0，0。分别表示可否向盘中放水果，可否取桔子，可否取苹果。第93页/共162页2023/3/2794Father()wh

42、ile(1)p(S);将水果放入盘中将水果放入盘中;if(是桔子是桔子)v(So);else v(Sa);Son()while(1)p(So)取桔子取桔子 v(S);吃桔子吃桔子;Daughter()while(1)p(Sa)取苹果取苹果 v(S);吃苹果吃苹果;第94页/共162页2023/3/2795【考研题】三个进程P1，P2，P3互斥使用一个包含N（N0）个单元缓冲区，P1每次用produce()生成一个正整数，并用put（）送入缓冲区某一空单元中，P2每次用getoodd()从该缓冲区中取出一个奇数，并用countodd()统计奇数个数，P3每次用geteven()从该缓冲区中取出一

43、个偶数，并用counteven()统计偶数个数，请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义，要求用伪代码描述。第95页/共162页2023/3/2796【考研题】（1）缓冲区是一互斥资源，因此设互斥信号量mutex。（2）同步问题：P1、P2因为奇数的放置与取用而同步，设同步信号量odd；P1、P3因为偶数的放置与取用而同步，设同步信号量even；P1、P2、P3因为共享缓冲区，设同步信号量empty。第96页/共162页2023/3/2797【考研题】Semaphoremutex=1;Semaphoreodd=0,even=0;Semaphoreempty=N;

44、Main()CobeginProcessP1While(True)Number=produce();P(empty);/检查缓冲区是否为空P(mutex);Put();/是空则放数据V(mutex);Ifnumber%2=0/如果是偶数则唤醒P3，否则P2V(even);elseV(odd);Process P2While(True)P(odd);/检查有没有奇数放入 P(mutex);getodd();/有则取出 V(mutex);V(empty);/使缓冲区为空 Countodd();Process P3While(True)P(even);/检查有没有偶数放入 P(mutex);gete

45、ven();/有则取出 V(mutex);V(empty);/使缓冲区为空 Counteven();coend第97页/共162页2023/3/2798哲学家就餐问题有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子第98页/共162页2023/3/2799设chopstick5为5个信号量，初值为均1Philosopheri：repeatwait(chopsticki);wait(chopstick(i+1)mod5)；进

46、食；signal(chopsticki);signal(chopstick(i+1)mod5)；思考；Untilfalse;解第99页/共162页2023/3/27100以上解法会出现死锁为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（AND信号量）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 分析第100页/共162页2023/3/27101设chopstick5为5个信号量，初值为均1设信号量S，初值为4S用于封锁第5个哲学家无死锁哲学家就餐问题 解1 1第101页/共162页2023/3/2

47、7102Philosopheri：repeat思考；wait(S)wait(chopsticki);wait(chopstick(i+1)mod5)；进食；signal(chopsticki);signal(chopstick(i+1)mod5)；signal(S)Untilfalse;第102页/共162页2023/3/27103利用AND信号量机制解决，要求每个哲学家需获得两个筷子后方能进餐。设chopstick5为5个信号量，初值为均1Philosopheri：repeat思考；Swait(chopsticki，chopstick(i+1)mod5);进食；Ssignal(chopsti

48、cki，(chopstick(i+1)mod5);Untilfalse;无死锁哲学家就餐问题 解2 2第103页/共162页2023/3/27104设chopstick5为5个信号量，初值为均1（奇数号哲学家先拿左边筷子，偶数号哲学家先拿右边筷子）无死锁哲学家就餐问题 解3 3第104页/共162页2023/3/27105Philosopheri：repeat思考；ifimod2=1thenwait(chopsticki);wait(chopstick(i+1)mod5)；进食；signal(chopsticki);signal(chopstick(i+1)mod5)；if i mod 2=0

49、 then wait(chopstick(i+1)mod 5)；wait(chopsticki);进食；signal(chopstick(i+1)mod 5)；signal(chopsticki);Until false;第105页/共162页2023/3/27106读者写者问题 有两组并发进程:读者和写者,共享一组数据区 要求：允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作第106页/共162页2023/3/27107读者优先如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，

50、新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待第107页/共162页2023/3/27108读者写者问题的解法设有两个信号量wmutex=1，rmutex=1另设一个全局变量readcount=0wmutex用于读者和写者、写者和写者之间的互斥readcount表示正在读的读者数目rmutex用于对readcount这个临界资源的互斥访问第108页/共162页2023/3/27109读者：repeatP(rmutex);if(readcount=0)thenP(wmutex);readcount:=readcount+1;V(rmutex);读;P(rmutex);readcou