进程管理课件

2023/9/13太湖学院信机系12.1.1程序的顺序执行及特征一、程序执行有固定的时序。（P34,图2-1）二、特征：顺序性、封闭性、可再现性2.1进程的基本概念I1C1P1I2C2P2程序段的顺序执行2023/8/3太湖学院信机系12.1.1程序的顺序执行2023/9/13太湖学院信机系2程序段中语句的顺序执行S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;S1S2S32023/8/3太湖学院信机系2程序段中语句的顺序执行S1:2023/9/13太湖学院信机系32.1.2前趋图定义有向无循环图表示方式： （1）p1p2（2）={(p1,p2)|p1必须在p2开始前完成}，前趋关系（图2-2P35）节点表示：一条语句，一个程序段，一个进程。P1P2P3P4S1S2S32023/8/3太湖学院信机系32.1.2前趋图定义有向无循2023/9/13太湖学院信机系4试画出下面几条语句的前趋图:S1:a=5-x;S2:b=a*x;S3:c=4*x;S4:d=b+c;S5:e=d+3。2023/8/3太湖学院信机系4试画出下面几条语句的前趋图:2023/9/13太湖学院信机系52.1.3程序的并发执行一、多个程序的并发执行（可行性分析）I1I2I3I4C1C2C3C4P1P2P3P4t思考：①哪些程序段的执行必须是顺序的？为什么？②哪些程序段的执行是可并行的？为什么？2023/8/3太湖学院信机系52.1.3程序的并发执行2023/9/13太湖学院信机系6程序的并发执行(2)二、特征间断性失去封闭性：主要由共享资源引起不可再现性：P37例，设N的初值为n。有2个循环程序A和B，它们共享一个变量N，程序A每执行一次时，都要做N:=N+1;B则每次要执行Print(N),然后再做N:=0.若程序A,B以不同的速度运行有以下三种不同的结果:N:=N+1在print(N)和N:=0之前，则N值分别为n+1,n+1,0.N:=N+1在print(N)和N:=0之后，则N值分别为n,0,1.N:=N+1在print(N)和N:=0之间，则N值分别为n,n+1,0.2023/8/3太湖学院信机系6程序的并发执行(2)二、特征2023/9/13太湖学院信机系72.1.4进程的特征和状态1.进程的特征和定义一、定义：1978年，全国操作系统会议：进程是一个具有一定独立功能的程序（关于某个数据集合的一次运行活动）对某个数据集在处理机上的执行过程和分配资源的基本单位。进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。（P38）系统中能独立运行并作为资源分配和调度的基本单位。(P15)*程序是指一组操作序列*数据集则是指接受程序规定操作的一组存储单元的内容2023/8/3太湖学院信机系72.1.4进程的特征和状态12023/9/13太湖学院信机系82.1.4进程的特征和状态(2)二、特征:1.结构特征进程：由程序段、数据段及进程控制块三部分构成，总称“进程映像”。2.动态性由“创建”而产生，由“调度”而执行；由得不到资源而阻塞（或等待）；由撤消而消亡。（而程序是静态的）。3.并发性只有建立了进程，才能并发执行。4.独立性独立运行，独立获得资源,独立接受调度5.异步性（断断续续向前推进）2023/8/3太湖学院信机系82.1.4进程的特征和状态(2023/9/13太湖学院信机系9进程与程序的区别进程程序动态静态暂时永久并发串行PCB---------多个一个一个多个2023/8/3太湖学院信机系9进程与程序的区别进程程序动态2023/9/13太湖学院信机系10例题：设有2个程序，程序P打印工资报表的程序，程序C是计算1000以内所有素数并显示最后结果的程序。（1）在不支持进程运行环境的操作系统下运行。（2）在支持进程运行的操作系统环境下运行。运行过程如下：①在不支持进程运行的环境下：依次运行程序P、程序C。可以看到先是打印机不停地打印工资报表，打完后，接着运行程序C，不停地计算，最后显示计算结果。②在支持进程运行的环境下：创建进程P和C，由于两个进程分别是I/O量较大和计算量较大的进程，故在系统进程调度的控制下，两个进程并发执行。可以看到打印机不断地打印工资报表，而处理机不停地计算，最后屏幕显示计算的结果。2023/8/3太湖学院信机系10例题：设有2个程序，程序P2023/9/13太湖学院信机系112.1.4进程的特征和状态(3)为了描述和控制进程的运行，系统为每一个进程定义了一个数据结构，即进程控制块PCB（ProcessControlBlock）,系统根据PCB，感知该进程的存在，故称PCB是进程存在的标志。通常在一个实际系统中，PCB的总数时固定的，该数目规定了系统所允许拥有的进程数目，同时将所有的PCB形成一个结构数组（或称PCB表），存放在系统的数据区里。一个进程的PCB机构全部或部分常驻内存。进程的静态描述由三部分组成：PCB，有关程序段，数据集。2023/8/3太湖学院信机系112.1.4进程的特征和状态2023/9/13太湖学院信机系122.1.4进程的特征和状态(3)2.进程的三种基本状态就绪状态、执行状态、阻塞（等待）状态就绪态：等待系统分配处理机以便运行。即获得了处理机以外的所有资源，一旦由调度选中得到处理机可以立即执行的状态。运行态：占有处理机正在执行。在单处理机的情况下，该状态的进程只有一个。等待态：等待某个事件的完成。进程因等待某事件而放弃处理机进入等待该事件的状态。2023/8/3太湖学院信机系122.1.4进程的特征和状态2023/9/13太湖学院信机系13就绪阻塞运行时间片完(剥夺处理机)进程调度发生等待事件等待事件结束图2－5进程的三种基本状态及其转换创建2023/8/3太湖学院信机系13就绪阻塞运行时间片完(剥夺2023/9/13太湖学院信机系142143执行态就绪态等待态1、某系统的进程状态转换图如上图所示，请回答：（1）引起各种状态转换的典型事件有哪些？（2）当我们观察系统中某些进程时，能够看到某一进程产生的一次状态转换能引起另一个进程作一次状态转换。在什么情况下，当一个进程发生转换3时，能立即引起另一进程发生转换1？试说明是否会发生这些因果转换：2→1；3→2；4→1。

2023/8/3太湖学院信机系142143执行态就绪态等待态2023/9/13太湖学院信机系152.1.4进程的特征和状态(4)3.挂起状态（被换出内存的状态，它所要解决的问题就是某些进程不参与资源竞争，挂起就是静止）引入原因：终端用户请求父进程请求（考察、修改、协调子进程）负荷调节需要（符合过重，把暂时不要的进程挂起）操作系统需要（检查资源使用情况）进程状态的转换活动就绪

静止就绪活动阻塞

静止阻塞静止就绪

活动就绪静止阻塞

活动阻塞2023/8/3太湖学院信机系152.1.4进程的特征和状态2023/9/13太湖学院信机系16图2－6具有挂起状态的进程状态图运行活动就绪静止就绪活动阻塞静止阻塞激活挂起激活挂起唤醒唤醒挂起请求I/O2023/8/3太湖学院信机系16图2－6具有挂起状态的进2023/9/13太湖学院信机系172.1.5进程控制块1.进程控制块的作用是进程存在的唯一标志；记录进程的信息PCB(processcontrolblock)常驻内存2.进程控制块中的信息标识（描述信息）、处理机状态（CPU现场保护）、进程调度信息、进程控制信息进程标识符进程状态现场优先级阻塞原因程序地址同步机制资源清单家族关系链接指针2023/8/3太湖学院信机系172.1.5进程控制块1.进2023/9/13太湖学院信机系18⑴描述信息（标识）进程名或进程标识符用户名或用户标识符（指示拥有该进程的用户）家族关系（父进程和子进程的标识符）⑵调度信息进程的当前状态优先级调度所需的其他信息事件（执行-等待）2023/8/3太湖学院信机系18⑴描述信息（标识）2023/9/13太湖学院信机系19⑶控制信息程序和数据的地址进程同步和通信机制资源清单链接指针（同一队列的下一个PCB的首地址）⑷处理机状态（CPU现场保护）通用RPC指令计数器程序状态字PSW用户栈指针2023/8/3太湖学院信机系19⑶控制信息2023/9/13太湖学院信机系20CPU现场保护信息（进程上下文）当处理机被中断时，各种Register的内容都必须保存在被中断进程的PCB中，以便在改进程重新执行时，能从断点继续执行。(1)通用R（用户可视寄存器）8-32个(在RISC结构中，可超过100）(2)PC（next）(3)PSW：含状态信息（条件码的执行方式，中断屏蔽标志）(4)用户栈指针：每个用户进程有一个或若干个与之相关的系统栈，用户存放过程和系统调用参数和调用地址。由于PCB中包含较多的信息（占几百-几千Byte），在有的系统中只含最常用部分（标识、进程状态信息、用于调度的信息）常驻内存，其它部分则存在于外存之中，待该进程将要执行时，与其它数据一起装入内存。2023/8/3太湖学院信机系20CPU现场保护信息（进程上2023/9/13太湖学院信机系21进程上下文进程上下文实际上是进程执行活动全过程的静态描述。进程的上下文是其相应的程序地址空间的内容，硬件R的内容以及与该进程有关的核心数据结构组成的。具体包括：计算机系统中与该进程有关的各种R值，程序段经过编译，连接后形成的机器指令代码段（text）数据段及各种堆栈的值和PCB块。2023/8/3太湖学院信机系21进程上下文进程上下文实际上2023/9/13太湖学院信机系223.PCB的组织方式在一个系统中，通常可拥有数十个、数百个，乃至数千个PCB：为能对它们进行有效的管理，应当用适当的方式将它们组织起来。目前常用的组织方式有两种：链接方式，索引方式。系统中进程队列分类：就绪队列、等待队列、运行队列。就绪队列：整个系统一个。等待队列：每个等待事件一个。运行队列：单机系统中整个系统一个。2023/8/3太湖学院信机系223.PCB的组织方式2023/9/13太湖学院信机系232.1.5进程控制块(2)链接方式把具有相同状态的PCB，用其中的链接字，链接成一个队列。执行指针就绪队列指针阻塞队列指针空闲队列指针PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB911多个2023/8/3太湖学院信机系232.1.5进程控制块(2)2023/9/13太湖学院信机系242.1.5进程控制块(3)索引方式系统根据所有进程的状态，建立几张索引表，例如，就绪索引表，阻塞索引表等，并把各索引表在内存的首地址记录于内存中的一些专用库文件中，在内存索引表的表目中，记录具有相应状态的PCB在PCB表中的地址。2023/8/3太湖学院信机系242.1.5进程控制块(3)2023/9/13太湖学院信机系25PCB1PCB2PCB3PCB4PCB5PCB6PCB7执行指针就绪表指针阻塞表指针就绪索引表阻塞索引表2023/8/3太湖学院信机系25PCB1PCB2PCB3P2023/9/13太湖学院信机系262.2进程控制为了防止操作系统及关键数据如PCB等，受到用户程序有意或无意的破坏，通常将处理机的执行状态分成系统态和用户态两种：（1）系统态，又称核心态。它具有较高的特权，能执行一切指令，访问所有寄存器和存储区。（2）用户态，具有较低特权的执行状态，它只能执行规定的指令，访问指定的寄存器和存储区。OS内核通常是运行在系统态的，而进程控制是由OS内核实现的。OS内核：运行在系统态的，包括对进程操作和控制的最基本的原语和数据结构。2023/8/3太湖学院信机系262.2进程控制为了防止2023/9/13太湖学院信机系27概念进程控制：就是系统使用一些具有特定功能的程序段来创建、撤销进程以及完成各进程状态间的转换，从而达到多进程高效率并发执行和协调，实现资源共享的目的。原语（AtomicOperation）：系统态下执行的某些具有特定功能的程序段称为原语。机器指令级:不可分割，不允许初始化功能级：不允许并发执行（原语本身由若干条指令组成，要么全做，要么全不做）在OS中，大都把进程控制用程序段做成原语。比如：创建原语、撤消原语、阻塞原语、唤醒原语、挂起原语、激活原语2023/8/3太湖学院信机系27概念进程控制：2023/9/13太湖学院信机系282.2.1进程的创建一、进程树(图)：描述了进程的家族关系子进程可继承父进程的资源，撤消时应归还给父进程，父进程在撤消时也应该撤消全部子进程。（递归）ABEKDFGHMLJIC2023/8/3太湖学院信机系282.2.1进程的创建一2023/9/13太湖学院信机系29二、引起创建进程的事件：1.用户登录：为终端用户建立一进程2.作业调度：（不是进程调度）为被调度的作业建立进程3.提供服务：如要打印时建立打印进程4.应用请求：由应用程序建立多个进程2023/8/3太湖学院信机系292023/9/13太湖学院信机系302.2.1进程的创建(2)三、进程的创建：（creat原语）1.申请空白PCB（一个系统的PCB是有限的）2.为新进程分配资源（不同于一般的分配，PCB-LIST在一个特殊区域）3.初始化PCB4.将新进程插入就绪队列。2023/8/3太湖学院信机系302.2.1进程的创建(2023/9/13太湖学院信机系31创建原语Procedurecreate(n,s0,P0,m0,R0,acc)begini:=getinternalname(n);获得内部名i.id:=n;填外部名i.priority:=P0;填优先级表i.CPUstate:=s0;填CPU初始状态i.mainstore:=m0;填写主存区域i.resources:=R0;填写资源清单i.status:=readys;填写进程状态j:=EP;获取调用者内部标识i.parent:=j;填入i进程的父进程jgeny:=φ;i的家族指针为空geny:=i;把i填入其父进程PCB的家族指针处i.state:=RQ;i所在状态队列首指针insert(RQ,i);把i进程插入RQ队尾end2023/8/3太湖学院信机系31创建原语Procedure2023/9/13太湖学院信机系322.2.2进程的撤消（终止）（一）、引起进程撤消（终止）的事件1.正常结束：如Halt、logsoff2.异常结束：如Protecterror、overtime等3.外界干预：a.系统或操作员kill进程；b.父进程终止；c.父进程请求。（二）、进程的终止过程（1）检查进程状态；（2）运行态――>终止，且置调度标志为真。（3）有无子孙需终止。（4）归还资源给其父进程或系统。（5）从PCB队列中移出PCB。2023/8/3太湖学院信机系322.2.2进程的撤消（33撤消原语Proceduredestroy(n)beginsched:=false;i:=n;//获取进程内部名；

kill(i);

如果sched为真，则转调度程序，否则继续；end33撤消原语Proceduredestroy(n)2023/9/13太湖学院信机系34Procedurekill(i)beginifi.status:=“Running”thenbeginstop(i);sched:=trueend;remove(i.state,i);将被撤消进程i从i.state所指示的队列中移去foralls∈genydokill(s);forallr∈(i.mainstore∪i.resources)doifowend(r)theninsert(r.semaphore,r.data);属于父进程资源归还且插入父进程资源清单forallR∈createdresources(i)doremovedescriptor(R);撤消自己的清单资源归还系统removeprocesscontrolblock;end2023/8/3太湖学院信机系34Procedurekil2023/9/13太湖学院信机系352.2.3进程的阻塞与唤醒（一）、引起进程阻塞和唤醒的事件1.请求系统服务而得不到满足时，如问系统请求打印。2.启动某种操作而需同步时：如该操作和请求该操作的进程需同步运行（即非异步操作）。3.新数据尚未到达：如进程A写，进程B读，则A未写完B不能读。4.无新工作可做。（二）、进程阻塞过程：是进程自身的一种主动行为a.调用block原语b.停止执行，修改PCB入阻塞队列（一个或多个），并转调度。2023/8/3太湖学院信机系352.2.3进程的阻塞与2023/9/13太湖学院信机系36Procedureblockbegini:=EP;从执行进程的指针EP获得调用者内部标识符i;stop(i);i.status:=“blocka”;i.state:=WQ(r);填写阻塞队列首指针insert(WQ(r),i);把i插入WQ队尾；scheduler;转调度程序end2023/8/3太湖学院信机系36Procedureblo2023/9/13太湖学院信机系372.2.3进程的阻塞与唤醒(2)（三）、唤醒过程其它相关进程完成。wakeup原语将目标进程移出等待队列，修改PCB，移入就绪队列可见，有block原语，在其它进程中就应有wakeup原语。2023/8/3太湖学院信机系372.2.3进程的阻塞与2023/9/13太湖学院信机系38Procedurewakeup(n)begini:=获取n进程的内部名；remove(WQ(r),i)；把i进程从等待r而受阻塞队列中摘除；i.status:=“就绪”；置i进程为“就绪”状态i.state:=RQ;把i进程插入就绪队列；insert(RQ,i);continue;end2023/8/3太湖学院信机系38Procedurewak2023/9/13太湖学院信机系392.2.4进程的挂起与激活

一、进程的挂起过程由进程自己或其父进程调suspend原语完成，将该进程PCB移到指定区域，注意状态的改变，有可能要重新调度。挂起方式：把挂起原语调用者本身挂起，即自己挂起自己挂起某个标识符的进程将某个指定标识符的进程及其全部或部分子孙挂起用意保存n进程的PCB副本的内存区，以备参考2023/8/3太湖学院信机系392.2.4进程的挂起与2023/9/13太湖学院信机系40Proceduresuspend(n,a)begini:=getinternalname(n);s:=i.status;ifs=“Running”thenstop(i);a:=copyPCB(i);i.status:=ifs=“blocka”then“blocks”else“readys”;ifs=“Running”thenschedulerelsecontinue;end2023/8/3太湖学院信机系40Proceduresu2023/9/13太湖学院信机系41二、进程的激活过程active原语（如在外存，调入内存，改变状态，根据情况看是否调度，如抢先或非抢先）。阻塞、唤醒一般由OS实现，而挂起与激活可由用户干预。激活方式：激活指定标识符的Process激活某Process及其子孙当激活后的Process处于“readys”状态时，将引起新调度，这种情况一般时当系统中无可调度的就绪进程时采用

2023/8/3太湖学院信机系41二、进程的激活过程2023/9/13太湖学院信机系42Procedureactivename(n)begini:=getinternalname(n);ifi.status=“readys”then“readya”else“blocka”;ifi.status=“readya”thenschedulerelsecontinue;end2023/8/3太湖学院信机系42Procedureact2023/9/13太湖学院信机系432.3进程间的相互作用进程的互斥进程的同步信号量及P、V操作。（解决进程同步互斥问题）2023/8/3太湖学院信机系432.3进程间的相互作用2023/9/13太湖学院信机系442.3.1进程间的联系

相交进程：指多个并发进程在逻辑上的某种联系无关进程：在逻辑上无任何联系的进程直接作用和间接作用直接作用：进程间的相互联系是有意识的安排的，进程间密切联系。直接作用只发生在相交进程间间接作用：进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可以发生在无关进程之间。2023/8/3太湖学院信机系442.3.1进程间的联系 相2023/9/13太湖学院信机系45进程间的关系表相互感知的程度交互关系一个进程对其他进程的影响相互不感知（完全不了解其他进程的存在）竞争（competition）一个进程的操作对其他进程的结果无影响间接感知（双方都与第三方交互：如共享资源）通过共享进行协作一个进程的结果依赖于从其他进程获得的信息直接感知（双方直接交互：如通信）通过通信进行协作（大批量的数据传递）一个进程的结果依赖于从其他进程获得的信息2023/8/3太湖学院信机系45进程间的关系表相互感知的程2023/9/13太湖学院信机系46进程同步（直接作用）进程的同步：synchronism指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一次任务，具体说，一个进程执行到某一点时，要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪状态。2023/8/3太湖学院信机系46进程同步（直接作用）进程的2023/9/13太湖学院信机系47司机P1While（true）{启动汽车；正常行驶；到站停车}售票员P2While（true）{关门；售票；开门；}2023/8/3太湖学院信机系47司机P1售票员P22023/9/13太湖学院信机系48进程的互斥（间接作用）进程的互斥：mutualexclusion由于各进程要求共享资源，而有些资源需要互斥使用，因此进程间竞争使用这些资源，进程的这种关系称为进程的互斥。临界资源：criticalresource系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。与时间有关的错误2023/8/3太湖学院信机系48进程的互斥（间接作用）进程2023/9/13太湖学院信机系49临界区（互斥区）：criticalsection一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作。在进程中，涉及到临界资源的程序片段叫临界区，多个进程的临界区称为相关临界区。2023/8/3太湖学院信机系49临界区（互斥区）：crit2023/9/13太湖学院信机系50进程的互斥作用（间接作用）2023/8/3太湖学院信机系50进程的互斥作用（间接作用）2023/9/13太湖学院信机系512023/8/3太湖学院信机系512023/9/13太湖学院信机系52使用临界区的原则：有空让进无空等待多中选一有限等待让权等待2023/8/3太湖学院信机系52使用临界区的原则：2023/9/13太湖学院信机系53前提：任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定进程互斥的解决有两种做法：由竞争各方平等协商引入进程管理者由管理者来协调竞争各方对互斥资源的使用具体的实现方法：硬件（当一个进程进入临界区就屏蔽所有中断，成本高，并行程度会降低）软件（用编程解决，但常常忙等待）2023/8/3太湖学院信机系53前提：任何进程无权停止其它2023/9/13太湖学院信机系54软件方法1free：表示临界区的标志

true：有进程在临界区

false：无进程在临界区（初值）

…while(free);free=true;

临界区

free=false;2023/8/3太湖学院信机系54软件方法1free：表示2023/9/13太湖学院信机系55软件方法2turn:trueP进程进入临界区

falseQ进程进入临界区

…P:while(notturn);

turn=false;Q:while(turn);

turn=true;临界区临界区①交替使用②某进程失败2023/8/3太湖学院信机系55软件方法2turn:t2023/9/13太湖学院信机系56例：进程0…while(flag[1]);flag[0]:=true;flag[0]:=false;进程1…while(flag[0]);flag[1]:=true;flag[1]:=false;临界区临界区存在问题：可能有两个进程同时进入临界区，达不到互斥的效果2023/8/3太湖学院信机系56例：进程02023/9/13太湖学院信机系57改进后：进程0…flag[0]:=true;while(flag[1]);flag[0]:=false;进程1…flag[1]:=true;while(flag[0]);flag[1]:=false;临界区临界区存在问题：造成谦让，两个进程同时处于等待状态2023/8/3太湖学院信机系57改进后：进程02023/9/13太湖学院信机系58继续改进：进程0…flag[0]:=true;while(flag[1])beginflag[0]:=false;

等会；

flag[0]:=true;endflag[0]:=false;进程1…flag[1]:=true;while(flag[0])beginflag[1]:=false;

等会；

flag[1]:=true;endflag[1]:=false;临界区临界区2023/8/3太湖学院信机系58继续改进：进程02023/9/13太湖学院信机系59软件方法3的形成：P进程pturn=true;while(qturn);pturn=false;…Q进程qturn=true;while(pturn);qturn=false;…pturn,qturn:初值为falseP进入临界区的条件：pturn∧notqturnQ进入临界区的条件：notpturn∧qturn临界区临界区存在问题：可能造成死锁2023/8/3太湖学院信机系59软件方法3的形成：P进程2023/9/13太湖学院信机系60软件方法4（Dekker算法）进程P:pturn:=true;while(qturn){if(turn==2) { pturn:=false;while(turn==2); pturn:=true; }}

turn:=2;pturn:=false…进程Q:qturn:=true;while(pturn){if(turn==1) { qturn:=false;while(turn==1); qturn:=true; }}

turn:=1;qturn:=false…在方法3的基础上引入turn枚举类型，初值可以任意设置。在这里：turn==1（P进），turn==2（Q进）临界区临界区2023/8/3太湖学院信机系60软件方法4（Dekker2023/9/13太湖学院信机系61软件算法有其缺点：忙等待（用循环在不停地等待）实现过于复杂，需要较高的编程技巧2023/8/3太湖学院信机系61软件算法有其缺点：忙等待（2023/9/13太湖学院信机系62改进的Dekker算法（Peterson算法）P:pturn:=true;turn:=2;while(qturn&&turn==2);

pturn:=false;Q:qturn:=true;turn:=1;while(pturn&&turn==1);

qturn:=false;临界区临界区2023/8/3太湖学院信机系62改进的Dekker算法2023/9/13太湖学院信机系632.3.2进程的同步机制信号量及P.V操作（解决进程同步）同步机制：信号量及P.V操作、管程；条件临界域；路径表达式等（用于集中式系统中）会合；通信顺序进程；分布进程；远程过程调用等；（适用于分布式系统中）2023/8/3太湖学院信机系632.3.2进程的同步机制信2023/9/13太湖学院信机系64同步机制满足的基本要求：描述能力可以实现效率高使用方便2023/8/3太湖学院信机系64同步机制满足的基本要求：2023/9/13太湖学院信机系65信号量：semaphore是一个数据结构定义如下：structsemaphore{intvalue;pointer_PCBqueue;}信号量说明：semaphores;2023/8/3太湖学院信机系65信号量：semaphore2023/9/13太湖学院信机系66信号量机制的提出者：伟大的计算机科学家Dijkstra，主要贡献：提出“goto有害论”;提出信号量和PV原语;解决了有趣的“哲学家聚餐”问题;最短路径算法(SPF)的创造者;第一个Algol60编译器的设计者和实现者;……与D.E.Knuth并称为我们这个时代最伟大的计算机科学家的人

2023/8/3太湖学院信机系66信号量机制的提出者：伟大的2023/9/13太湖学院信机系672.3.3信号量机制1.整型信号量是一个整型量，通过2个原子操作wait(s)和signal(s)来访问。Wait(s):whiles<=0dono-op；

s:=s-1;Signal(s): s:=s+1;P、V操作（两个原语）2023/8/3太湖学院信机系672.3.3信号量机制12023/9/13太湖学院信机系68关于信号量的问题信号量：互斥：wait与signal在同一个进程中同步：wait与signal在不同的进程中信号量的物理意义：S>0：表示可用资源的个数S=0：表示无资源，无等待进程S<0：∣S∣表示等待队列中进程个数2023/8/3太湖学院信机系68关于信号量的问题信号量：2023/9/13太湖学院信机系692.记录型信号量wait(S){s.value=s.value--;if(s.value<0){该进程状态置为等待状态将该进程的PCB插入相应的等待队列末尾s.value}}2023/8/3太湖学院信机系692.记录型信号量wait2023/9/13太湖学院信机系70signal(S){s.value=s.value++;if(s.value<=0){

唤醒相应等待队列s.value中等待的一个进程改变其状态为就绪态并将其插入就绪队列

}}2023/8/3太湖学院信机系70signal(S)2023/9/13太湖学院信机系71P.V操作为原语操作原语：primitiveoratomicaction是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性；即原语的执行必须是连续的，在执行过程中不允许被中断2023/8/3太湖学院信机系71P.V操作为原语操作原语：2023/9/13太湖学院信机系72信号量的使用必须置一次且只能置一次初值初值不能为负数只能执行P.V操作2023/8/3太湖学院信机系72信号量的使用必须置一次且只2023/9/13太湖学院信机系73用P.V操作解决进程间的互斥问题wait(mutex)signal(mutex)互斥区P1P2P3wait(mutex)signal(mutex)互斥区wait(mutex)signal(mutex)互斥区2023/8/3太湖学院信机系73用P.V操作解决进程间的互2023/9/13太湖学院信机系74互斥问题进程A………Wait（s）打印Signal（s）……【例】设有一台打印机初值s:=1进程B………Wait（s）打印Signal（s）……2023/8/3太湖学院信机系74互斥问题进程A【例】设有一2023/9/13太湖学院信机系75生产者－消费者问题Varn,integer;typeitem=…;varbuffer:array[0,1,…,n-1]ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;2023/8/3太湖学院信机系75生产者－消费者问题Var2023/9/13太湖学院信机系76生产者－消费者问题producer:repeat… produceaniteminnextp;…whilecounter=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;untilfalse;consumer:repeatwhilecounter=0dono-op;nextc:=buffer[out];out:=(out+1)modn;counter:=counter-1;consumertheiteminnextc;untilfalse;2023/8/3太湖学院信机系76生产者－消费者问题prod2023/9/13太湖学院信机系77生产者－消费者问题（2）设counter的初值为5register1:=counter;register2:=counter;register1:=register1+1;register2:=register2-1;counter:=register1;counter:=register2;2023/8/3太湖学院信机系77生产者－消费者问题（2）设2023/9/13太湖学院信机系78register1:=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)解决方法：变量counter应设置成临界资源2023/8/3太湖学院信机系78register1:=co2023/9/13太湖学院信机系79同步问题【例】矩阵运算：A+B考虑问题：资源等待为其他资源着想2023/8/3太湖学院信机系79同步问题【例】矩阵运算：A2023/9/13太湖学院信机系80经典的生产者消费者问题（关于同步的问题）仓库生产者消费者一次只放一个产品同步问题：P进程不能往“满”的缓冲区中放产品，设置信号量为s1，初值为1Q进程不能从“空”的缓冲区中取产品，设置信号量为s2，初值为02023/8/3太湖学院信机系80经典的生产者消费者问题（关2023/9/13太湖学院信机系81P:生产者while(true){生产一个产品；Wait(s1);送产品到仓库；Signal(s2)}Q:消费者while(true){Wait(s2);从仓库中取产品；Signal(s1)；消费产品}仓库只能存放一个产品：2023/8/3太湖学院信机系81P:生产者Q:消费者仓库只2023/9/13太湖学院信机系82扩充：多个缓冲区的生产者消费者问题P：i=0;while(true){生产产品；Wait(s1);往buffer[i]放产品；Signal(s2);i=(i+1)%n;}Q：j=0;while(true){Wait(s2);从buffer[j]取产品；Signal(s1);消费产品j=(j+1)%n;}初值：s1=n，s2=02023/8/3太湖学院信机系82扩充：多个缓冲区的生产者消2023/9/13太湖学院信机系83小结：生产者消费者问题的分类：单一资源：s1=1,s2=0有限资源：s1=n,s2=0无限资源：2023/8/3太湖学院信机系83小结：生产者消费者问题的分2023/9/13太湖学院信机系84∞缓冲区的生产者消费者问题P：i=0;while(true){生产产品；Wait(s1);往buffer[i]放产品；Signal(s2);i=(i+1)%n;}Q：j=0;while(true){Wait(s2);从buffer[j]取产品；Signal(s1);消费产品j=(j+1)%n;}初值：s2=02023/8/3太湖学院信机系84∞缓冲区的生产者消费者问题2023/9/13太湖学院信机系85n个缓冲区，m个生产者和k个消费者（临界资源的使用）P：i=0;while(true){生产产品；Wait(s1);Wait(mutex);往buffer[i]放产品；Signal(mutex);Signal(s2);i=(i+1)%n;}Q：j=0;while(true){Wait(s2);Wait(mutex)从buffer[j]取产品；Signal(mutex);Signal(s1);消费产品j=(j+1)%n;}信号量：s1=ns2=0mutex=12023/8/3太湖学院信机系85n个缓冲区，m个生产者和k2023/9/13太湖学院信机系86若在Q中颠倒wait操作的顺序P：i=0;while(true){生产产品；Wait(s1);Wait(mutex);往buffer[i]放产品；Signal(mutex);Signal(s2);i=(i+1)%n;}Q：j=0;while(true){Wait(mutex)；Wait(s2);从buffer[j]取产品；Signal(mutex);Signal(s1);消费产品j=(j+1)%n;}信号量：S1=nS2=0mutex=12023/8/3太湖学院信机系86若在Q中颠倒wait操作的2023/9/13太湖学院信机系87（扩展）生产者与消费者应针对不同的临界区进行操作P：i=0;while(true){生产产品；Wait(s1);Wait(mutex1);往buffer[i]放产品；Signal(mutex1);Signal(s2);i=(i+1)%n;}Q：j=0;while(true){Wait(s2);Wait(mutex2)从buffer[j]取产品；Signal(mutex2);Signal(s1);消费产品j=(j+1)%n;}信号量：S1=nS2=0Mutex1=1Mutex2=12023/8/3太湖学院信机系87（扩展）生产者与消费者应针2023/9/13太湖学院信机系88对PV操作的讨论1）信号量的物理意义：S>0：表示可用资源的个数S=0：表示无资源，无等待进程S<0：∣S∣表示等待队列中进程个数Wait(s):表示申请一个资源Signal(s):表示释放一个资源信号量的初值应该大于等于02023/8/3太湖学院信机系88对PV操作的讨论1）信号量2023/9/13太湖学院信机系892）p、v操作必须成对出现，有一个p操作就一定有一个v操作 当为互斥操作时，它们处于同一进程 当为同步操作时，则不在同一进程中出现wait(s1)和wait(s2)两个操作在同进程中？

wait操作的顺序至关重要，一个同步wait操作与一个互斥wait操作在一起时，同步wait操作在互斥wait操作之前，而两个signal操作的顺序没有要求。2023/8/3太湖学院信机系892）p、v操作必须成对出现2023/9/13太湖学院信机系903）pv操作的优缺点优点：简单，而且表达能力强（可以解决任何同步互斥问题）缺点：不够安全，pv操作使用不当会出现死锁，遇到复杂的同步互斥问题时实现复杂。2023/8/3太湖学院信机系903）pv操作的优缺点2023/9/13太湖学院信机系91AND型信号量AND型信号量是指同时需要多种资源且每种占用一个的信号量操作AND型信号量的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配AND型信号量P原语为SwaitAND型信号量V原语为Ssignal2023/8/3太湖学院信机系91AND型信号量AND型信号2023/9/13太湖学院信机系92Swait(s1,s2,…,sn){while(true){if(s1>=1&&s2>=1&&…&&sn>=1){//满足资源要求时的处理for(i=1;i<=n;i++)si=si-1；//注：与wait的处理不同这里在确信可满足资源需求时才进行减1操作break;}else{//某些资源不够时的处理调用进程进入第一个小于1信号量的等待队列sj.queue;阻塞调用进程；}}}2023/8/3太湖学院信机系92Swait(s1,s2,…2023/9/13太湖学院信机系93Ssignal(s1,s2,…,sn){For(i=1;i<=n;i++){si=si+1;//释放所有占用的资源For(在si.queue中等待的每一个进程p)//检查每种资源的等待队列的所有进程{从等待队列si.queue中取出进程p；if(判断进程p是否通过Swait中的测试)//这里要进行重新判断{//通过检查（资源够用时）的处理；进程p进入就绪队列}else{//未通过检查（资源不够用时）的处理；进程p进入等待队列；}}}}2023/8/3太湖学院信机系93Ssignal(s1,s22023/9/13太湖学院信机系94信号量集信号量集是指同时需要多种资源，每种占用的数目不同且可分配的资源还存在一个临界值时的信号量处理。信号量集的基本思路：在AND型信号量的基础上进行扩充，在一次原语操作完成所有的资源申请。进程对信号量si的测试值为ti（表示信号量的判断条件，要求si>=ti;即当资源数量低于ti时，便不予分配）占用值为di（表示资源的申请量，即si=si-di）对应的pv原语格式为：Swait(s1,t1,d1;…;sn,tn,dn);Ssignal(s1,d1;…sn,dn);2023/8/3太湖学院信机系94信号量集信号量集是指同时需2023/9/13太湖学院信机系95信号量集可以用于各种情况的资源分配和回收，几种特殊情况：Swait(s,d,d)：表示每次申请d个资源，当少于d个时，便不分配Swait(s,1,1)：s>1表示记录型信号量，s=1表示互斥信号量Swait(s,1,0)：可作为一个可控开关（当s>=1时，允许多个进程进入特殊区域；当s=0时，禁止任何进程进入临界区）不占用资源2023/8/3太湖学院信机系952023/9/13太湖学院信机系96第二类经典问题：读者写者问题有两组并发进程：读者和写者，共享一组数据区要求：允许多个读者同时执行读操作不允许读者、写者同时操作（读写互斥）不允许多个写者同时操作（只能一个写）2023/8/3太湖学院信机系96第二类经典问题：读者写者问2023/9/13太湖学院信机系97分析：第一类情况：读者优先如果读者来：1)无读者写者，新读者可以读2)有写者等，但有其他读者正在读，则新读者也可以读3)有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其他写者，新写者等待2023/8/3太湖学院信机系97分析：2023/9/13太湖学院信机系98第一类读者写者问题的解法读者来：While(true){Wait(mutex);readcount++;if(readcount==1)

Wait(wr);Signal(mutex);读Wait(mutex);readcount--;if(readcount==0)

Signal(wr);signal(mutex);}写者来：While(true){Wait(wr);写Signal(wr);}初值：wr=1;（读-写互斥，写-写互斥）mutex=1;（读者统计数量互斥）readcount=0;2023/8/3太湖学院信机系98第一类读者写者问题的解法读2023/9/13太湖学院信机系99用信号量集解决第一类读者写者问题写者：Swait(wr,1,1);Swait(count,n,0);写Ssignal(wr,1);读者：Swait(count,1,1);Swait(wr,1,0);读Ssignal(count,1);初值：wr:=1count:=n最多只能n个读者同时读(空位)2023/8/3太湖学院信机系99用信号量集解决第一类读者写2023/9/13太湖学院信机系1002.利用信号量来描述前趋关系(1)P1：S1；P2：S2；并发进程：P1和P2，各进程语句如下，要求：S1执行结束才能执行S2。如何设置P1与P2的关系？2023/8/3太湖学院信机系1002.利用信号量来描述前趋2023/9/13太湖学院信机系1012.利用信号量来描述前趋关系(2)S1S2S3S4S5S6abcdegf图2－10前趋图举例2023/8/3太湖学院信机系1012.利用信号量来描述前趋2023/9/13太湖学院信机系102利用信号量来描述前趋关系(2)Vara,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; begin wait(d);S1;signal(g); end; begin wait(e);wait(f);wait(g);S6; end; parendend2023/8/3太湖学院信机系102利用信号量来描述前趋关系2023/9/13太湖学院信机系1032.4.2哲学家进餐问题1.利用记录型信号量解决哲学家进餐问题Varchopstick:array[0,…,4]ofsemaphore;Repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);…eat；

…signal(chopstick[i]);signal(chopstick[(i+1)mod5]);…think;Untilfalse2023/8/3太湖学院信机系1032.4.2哲学家进餐问题2023/9/13太湖学院信机系1042.4.2哲学家进餐问题2.利用AND信号量解决哲学家进餐问题Varchopstick:array[0,…,4]ofsemaphore:=(1,1,1,1,1);processiRepeatthink;Sswait(chopstick[(i+1)mod5],chopstick[i]);eat；

Ssignal(chopstick[(i+1)mod5],chopstick[i]);Untilfalse2023/8/3太湖学院信机系1042.4.2哲学家进餐问题2023/9/13太湖学院信机系1052.5管程机制引入原因：为了避免凡要使用临界资源的进程都自备同步操作wait(s)和signal(s).将同步操作的机制和临界资源结合到一起，形成管程。

2023/8/3太湖学院信机系1052.5管程机制引入原因：2023/9/13太湖学院信机系1061、定义：一个数据结构和能为并发进程所执行的一组操作，该操作能同步进程和改变进程中的数据。(P55)由四部分组成：管程的名称局部于管程的共享变量。