操作系统第2章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 进 程 管 理,第二章 进程管理,2.1,进程的基本概念,2.2,进程控制,2.3,进程同步,2.4,经典进程的同步问题,2.5,管程机制,2.6,进程通信,2.7,线程,2.1,进程的基本概念,2.1.1,程序的顺序执行及其特征,1.,程序的顺序执行,仅当前一操作,(,程序段,),执行完后，才能执行后继操作。,例如，在进行计算时，总须先输入用户的程序和数据,(I),，然后进行计算,(C),，最后才能打印计算结果,(P),。,S,1,:a=x+y;,S,2,:b=a-5;,S,3,:c=b+1;,图,2-1,程序的顺序执行,2.,程序顺序执行时的特征,顺序性：,(2),封闭性：,(3),可再现性：,2.1.2,前趋图,前趋图,(Precedence Graph),是一个有向无循环图，记为,DAG(Directed Acyclic Graph),，,用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序,(Partial Order),或前趋关系,(Precedence Relation)“”,。,=(P,i,P,j,)|P,i,must complete before,P,j,may start,如果,(P,i,P,j,),可写成,P,i,P,j,，称,P,i,是,P,j,的直接前趋，而称,P,j,是,P,i,的直接后继。在前趋图中，把没有前趋的结点称为初始结点,(Initial Node),，,把没,有后继的结点称为终止结点,(Final Node),。,每个结点还具有一个重量,(Weight),，,用于表示该结点所含有的程序量或结点的执行时间。,I,i,C,i,P,i,和,S,1,S,2,S,3,图,2-2,前趋图,对于图,2-2(,a,),所示的前趋图，存在下述前趋关系：,P,1,P,2,P,1,P,3,P,1,P,4,P,2,P,5,P,3,P,5,P,4,P,6,P,4,P,7,P,5,P,8,P,6,P,8,P,7,P,9,P,8,P,9,或表示为：,P=P,1,P,2,P,3,P,4,P,5,P,6,P,7,P,8,P,9,=(P,1,P,2,),(P,1,P,3,),(P,1,P,4,),(P,2,P,5,),(P,3,P,5,),(P,4,P,6,),(P,4,P,7,),(P,5,P,8,),(P,6,P,8,),(P,7,P,9,),(P,8,P,9,),应当注意，前趋图中必须不存在循环，但在图,2-2(,b,),中却有着下述的前趋关系：,S,2,S,3,S,3,S,2,2.1.3,程序的并发执行及其特征,1.,程序的并发执行,图,2-3,并发执行时的前趋图,I,1,I,2,I,3,I,4,C,1,C,2,C,3,C,4,P,1,P,2,P,3,P,4,I,2,C,1,I,3,C,2,P,1,I,4,C,3,P,2,C,4,P,3,在该例中存在下述前趋关系：,I,i,C,i,，,I,i,I,i+1,C,i,P,i,C,i,C,i+1,，,P,i,P,i+1,而,I,i+1,和,C,i,及,P,i-1,是重迭的，亦即在,P,i-1,和,C,i,以及,I,i+1,之间，可以并发执行。对于具有下述四条语句的程序段：,S,1,:a=x+2,S,2,:b=y+4,S,3,:c=a+b,S,4,:d=c+b,S,1,和,S,2,可以并发执行，它们彼此互不依赖。,图,2-4,四条语句的前趋关系,2.,程序并发执行时的特征,1),间断性,：相互制约将导致并发程序具有“执行暂停执行”这种间断性的活动规律。,2),失去封闭性,：程序并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。,3),不可再现性,：由于失去了封闭性，也将导致其再失去可再现性。,例如，有两个循环程序,A,和,B,，,它们共享一个变量,N,。,程序,A,每执行一次时，都要做,N:=N+1,操作；程序,B,每执行一次时，都要执行,Print(N),操作，然后再将,N,置成“,0”,。程序,A,和,B,以不同的速度运行。,(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,。,2.1.4,进程的特征与状态,1.,进程的特征和定义,1),结构特征：由程序段、相关的数据段和,PCB,组成,2),动态性,：最基本的特征,3),并发性,4),独立性,5),异步性,较典型的进程定义有：,(1),进程是程序的一次执行。,(2),进程是一个程序及其数据在处理机上顺序执行时所发生的活动。,(3),进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。,在引入了进程实体的概念后，可以把传统,OS,中的进程定义为：“,进程是进程实体的运,行过程，是系统进行资源分配和调度的一个独立单位,”,。,进程与程序的区别：,(1),程序是指令的有序集合，其本身没有任何运行的含义，是一个,静态,的概念。而进程是程序在处理机上的一次执行过程，它是一个,动态,的概念。,(2),程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是,永久,的，进程是,暂时,的。,(3),进程更能真实地描述并发，而程序不能,(4),进程是由程序和数据两部分组成的,(5),进程具有创建其他进程的功能，而程序没有,(6),同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说,同一程序可以对应多个进程,思考？,为什么引入进程的概念？,2.,进程的三种基本状态,1),就绪,(Ready),状态,（可能有多个进程处于就绪状态）,2),执行状态,（单处理机中，只有一个进程处于执行状态；,多处理机系统中，则有多个进程处于执行状态）,3),阻塞状态,（可能有多个进程处于阻塞状态）,图,2-5,进程的三种基本状态及其转换,就绪,阻塞,执行,进程调度,时间片完,I,/,O,请求,I,/,O,完成,3.,挂起状态,引入挂起状态的原因,终端用户的请求。,(2),父进程请求。,(3),负荷调节的需要。,(4),操作系统的需要。,2),进程状态的转换,活动就绪静止就绪。,(2),活动阻塞静止阻塞。,(3),静止就绪活动就绪。,(4),静止阻塞活动阻塞。,活动,阻塞,静止,阻塞,活动,就绪,静止,就绪,执行,激活,激活,挂起,挂起,释放,释放,挂起,调度,I/O,请求,图,2-6,具有挂起状态的进程状态图,4,创建状态和终止状态,1),创建状态,首先，为一个新进程创建,PCB,，并填写必要的管理信息；,其次，把该进程转入就绪状态并插入就绪队列之中。,当一个新进程被创建时，系统已为其分配了,PCB,，填写了进程标识等信息，但由于该进程所必需的资源或其它信息，如主存资源尚未分配等，对于处于创建状态的进程，获得了其所必需的资源，以及对其,PCB,初始化工作完成后，进程状态便可由创建状态转入就绪状态。,2),终止状态,首先等待操作系统进行善后处理，然后将其,PCB,清零，并将,PCB,空间返还系统。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。进入终止态的进程以后不能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据，供其它进程收集。一旦其它进程完成了对终止状态进程的信息提取之后，操作系统将删除该进程。,创建,就绪,阻塞,执行,终止,许可,释放,I,/,O,请求,I,/,O,完成,进程调度,时间片完,图,2-7,进程的五种基本状态及转换,图,2-8,具有创建、终止和挂起状态的进程状态图,活动,阻塞,静止,阻塞,活动,就绪,静止,就绪,执行,激活,激活,挂起,挂起,释放,释放,挂起,调度,I/O,请求,创建,终止,许可,许可,释放,思考？,1,如果系统中有,N,个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？,2.,有没有这样的状态转换，为什么？,阻塞,运行；就绪,阻塞,对于单处理机，运行进程最多一个，最少,0,个，就绪进程最多,n-1,个，最少,0,个，等待进程最多,n,个，最少,0,个（可能全部等待）。,2.1.5,进程控制块,1.,进程控制块的作用,进程控制块的作用是使一个在多道程序环境下不能独立运行的程序,(,含数据,),，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，,OS,是根据,PCB,来对并发执行的进程进行控制和管理的。,系统利用,PCB,来控制和管理进程，所以,PCB,是系统,感知进程存在的唯一标志,进程与,PCB,是一一对应的,2.,进程控制块中的信息,1),进程标识符,进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：,(1),内部标识符。在所有的操作系统中，都为每一个进 程赋予一个惟一的数字标识符，它通常是一个进程的序号。,(2),外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户,(,进程,),在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此,外，还可设置用户标识，以指示拥有该进程的用户。,2),处理机状态,处理机状态信息主要是由处理机的各种寄存器中的内容组成的。,通用寄存器,指令计数器,程序状态字,PSW,用户栈指针,3),进程调度信息,进程状态,进程优先级,进程调度所需的其它信息,事件,4),进程控制信息,程序和数据的地址,进程同步和通信机制,资源清单,链接指针,3.,进程控制块的组织方式,1),链接方式,图,2-9 PCB,链接队列示意图,2),索引方式,图,2-10,按索引方式组织,PCB,2.2,进 程 控 制,进程控制就是对系统中的所有进程实施管理，进程控制一般有,原语,来实现。,所谓原语是一种特殊的系统功能调用，它可以完成一个特定的功能，其特点是原语执行时不可被中断,。,原语的作用是为了进程的通信和控制，保证进程状态的确定性。,常用原语：,创建原语、终止原语、阻塞原语、唤醒原语,2.2.1,进程的创建,1.,进程图,(Process Graph),图,2-11,进程树,2.,引起创建进程的事件,用户登录。,(2),作业调度。,(3),提供服务。,(4),应用请求。,3.,进程的创建,(Creation of Progress),通过调用创建原语,Create,创建一个新进程,(1),申请空白,PCB,。,(2),为新进程分配资源。,(3),初始化进程控制块。,(4),将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队,列。,2.2.2,进程的终止,1.,引起进程终止,(Termination of Process),的事件,1),正常结束,2),异常结束：,越界错误。保护错。非法指令。权指令错。运行超时。等待超时。算术运算错。,I/O,故障。,3),外界干预：操作员或操作系统干预。父进程请求。父进程终止。,2.,进程的终止过程,调用进程终止原语,(1),根据被终止进程的标识符，从,PCB,集合中检索出该进程的,PCB,，,从中读出该进程的状态。,(2),若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。,(3),若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。,(4),将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。,(5),将被终止进程,(,它的,PCB),从所在队列,(,或链表,),中移出，等待其他程序来搜集信息。,2.2.3,进程的阻塞与唤醒,1.,引起进程阻塞和唤醒的事件,1),请求系统服务不能立即满足,2),启动某种操作必须在完成另一操作之后才能执行,3),新数据尚未到达,4),无新工作可做,2.,进程阻塞过程,通过调用阻塞原语,block,把自己阻塞,先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将,PCB,插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞,(,等待,),队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进,程的处理机状态,(,在,PCB,中,),，再按新进程的,PCB,中的处理机状态设置,CPU,的环境。,3.,进程唤醒过程,通过调用唤醒原语,wakeup,将阻塞进程唤醒,首先把被阻塞的进程从等待该事件的阻塞队列中移出，,将其,PCB,中的现行状态由阻塞改为就绪，然后再将该,PCB,插入到就绪队列中。,2.2.4,进程的挂起与激活,1.,进程的挂起,利用挂起原语,suspend(),将指定进程或处于阻塞状态的进程挂起,首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。为了方便用户或父进程考查该进程的运行情况而把该进程的,PCB,复制到某指定的内存区域。最后，若被挂,起的进程正在执行，则转向调度程序重新调度。,2.,进程的激活过程,利用激活原语,active(),将指定进程激活,激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把,处理机分配给刚被激活的进程。,思考？,为什么创建进程要用原语来实现？,请设想一下进程在什么情况下会变为阻塞状态？,阻塞进程在什么情况下会被唤醒？谁来唤醒它？,2.3,进 程 同 步,2.3.1,进程同步的基本概念,1.,两种形式的制约关系,间接相互制约关系。,(2),直接相互制约关系。,同步,同步是进程间共同完成一项任务时直接发相互作用的关系,同步进程间具有合作关系,在执行时间上必须按一定的顺序协调进行,互斥,互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系,互斥进程彼此在逻辑上是完全无关的,它们的运行不具有时间次序的特征,2.,临界资源,(Critical,Resouce,),生产者,-,消费者,(producer-consumer),问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有,n,个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且,尚未被取走的缓冲区中投放产品。,利用数组表示具有,n,个,(0,，,1,，,，,n-1),缓冲区的缓冲池。,in,：指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加,1,；,out,：指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加,1,。,当,(in+1)mod n=out,时，满；而,in=out,，空。,整型变量,counter,其初始值为,0,。每当生产者进程向缓冲池中投放一个产品后，使,counter,加,1,；反之，每当消费者进程从中取走一个产品时，使,counter,减,1,。,Var,n,integer;,type item=;,var,buffer:array,0,1,n-1,of item;,in,out:0,1,n-1;,counter:0,1,n;,指针,in,和,out,初始化为,1,。,producer:repeat,produce an item in,nextp;/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,:,每次取出的产品数,nextc,:=,bufferout,;,out:=(out+1)mod n;,counter:=counter-1;,consumer the item in,nextc,;,until false;,虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量,counter,。,生产者对它做加,1,操作，消费者对它做减,1,操作，这两个操作在用机器语言实现时，常可用下面的形式描述：,register1:=counter;register2:=counter;,register1:=register1+1;register2:=register2-1;,counter:=register1;counter:=register2;,假设：,counter,的当前值是,5,。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句，则最后共享变量,counter,的值仍为,5,；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，,counter,值也还是,5,，但是，如果按下述顺序执行：,register1:=counter;(register1=5),register1:=register1+1;(register 1=6),register2:=counter;(register 2=5),register2:=register2-1;(register 2=4),counter:=register1;(counter=6),counter:=register2;(counter=4),3.,临界区,(critical section),可把一个访问临界资源的循环进程描述如下：,repeat,critical section;,remainder section;,until false;,entry section,exit section,4.,同步机制应遵循的规则,空闲让进。,(2),忙则等待。,(3),有限等待。,(4),让权等待。,2.3.2,信号量机制,1.,整型信号量,最初由,Dijkstra,把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作,(Atomic Operation)wait(S),和,signal(S),来访问。这两个操作一直被分别称为,P,、,V,操作。,wait,和,signal,操作可描述为：,wait(S):while S0 do no-op,/,申请一个单位资源,S:=S-1;,signal(S):S:=S+1;,/,释放一个单位资源,2.,记录型信号量,procedure wait(S),var,S:semaphore;,begin,S.value,:=S.value-1;,if S.value,0 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,S.value,的初值表示系统中某类资源的数目,wait,操作，意味着进程请求一个单位的该类资源，,S.value,:=S.value-1,；当,S.value,0,时，表示该类资源已分配完毕，入等待队列,S.L,，当,S.value0,时，继续,。,signal,操作，表示执行进程释放一个单位资源，,S.value,:=S.value+1,；若加,1,后仍是,S.value0,，,则表示在该信号量链表中，仍有等待该资源的进程被阻塞，将,S.L,链表中的第一个等待进程唤醒。当,S.value,0,时，继续。,如果,S.value,的初值为,1,，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信,号量。,3.AND,型信号量,在两个进程中都要包含两个对,Dmutex,和,Emutex,的操作，即,process A:process B:,wait(Dmutex,);,wait(Emutex,);,wait(Emutex,);,wait(Dmutex,);,若进程,A,和,B,按下述次序交替执行,wait,操作：,process A:,wait(Dmutex,);,于是,Dmutex,=0,process B:,wait(Emutex,);,于是,Emutex,=0,process A:,wait(Emutex,);,于是,Emutex,=-1 A,阻塞,process B:,wait(Dmutex,);,于是,Dmutex,=-1 B,阻塞,AND,同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在,wait,操作中，增加了一个“,AND”,条件，故称为,AND,同步，,或称为同时,wait,操作，即,Swait(Simultaneous,wait),定义如下：,Swait(S,1,S,2,S,n,),if S,i,1 and and S,n,1 then,for i=1 to n do,S,i,=S,i,-1;,endfor,else,place the process in the waiting queue associated with the first,S,i,found with,S,i,1,and set the program count of this process to the beginning of,Swait,operation,endif,Ssignal(S1,S2,Sn,),for i =1 to n do,S,i,=S,i,+1;,Remove all the process waiting in the queue associated with,S,i,into the ready queue.,endfor,;,4.,信号量集,Swait(S,1,t,1,d,1,S,n,t,n,d,n,),if S,i,t,1,and and,S,n,t,n,then,for i=1 to n do,S,i,=,S,i,-d,i,;,endfor,else,Place the executing process in the waiting queue of the first,S,i,with,S,i,t,i,and set its program counter to the beginning of the,Swait,Operation.,endif,Ssignal(S,1,d,1,S,n,d,n,),for i=1 to n do,S,i,=,S,i,+d,i,;,Remove all the process waiting in the queue associated with,S,i,into the ready queue,endfor,;,一般“信号量集”的几种特殊情况：,(1),Swait(S,d,d),。,此时在信号量集中只有一个信号量,S,，,但允许它每次申请,d,个资源，当现有资源数少于,d,时，不予分配。,(2),Swait(S,1,1),。,此时的信号量集已蜕化为一般的记录型信号量,(S,1,时,),或互斥信号量,(S=1,时,),。,(3),Swait(S,1,0),。,这是一种很特殊且很有用的信号量操作。当,S1,时，允许多个进程进入某特定区；当,S,变为,0,后，将阻止任何进程进入特定区。换言之，它相当于一个可,控开关。,2.3.3,信号量的应用,1.,利用信号量实现进程互斥,利用信号量实现进程互斥的进程可描述如下：,Var,mutex:semaphore,:=1;,begin,parbegin,process 1:begin,repeat,wait(mutex,);,critical section,signal(mutex,);,remainder,seetion,until false;,end,process 2:begin,repeat,wait(mutex,);,critical section,signal(mutex,);,remainder section,until false;,end,parend,2.,利用信号量实现前趋关系,图,2-12,前趋图举例,Var,a,b,c,d,e,f,g;semaphore=0,0,0,0,0,0,0;,begin,parbegin,begin S,1,;signal(a);signal(b);end;,begin wait(a);S,2,;signal(c);signal(d);end;,begin wait(b);S,3,;signal(e);end;,begin wait(c);S,4,;signal(f);end;,begin wait(d);S,5,;signal(g);end;,begin wait(e);wait(f);wait(g);S,6,;end;,parend,end,2.4,经典进程的同步问题,2.4.1,生产者,消费者问题,1.,利用记录型信号量解决生产者,消费者问题,mutex,：实现诸进程对缓冲池的互斥使用；,empty,：表示缓冲池中空缓冲区；,full,：表示满缓冲区的数量。,假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。,Var,mutex,empty,full:semaphore=1,n,0;,buffer:array,0,n-1,of item;,in,out:integer=0,0;,begin,parbegin,proceducer:begin,repeat,producer an item,nextp,;,wait(empty);,wait(mutex,);,buffer(in,):=,nextp,;,in:=(in+1)mod n;,signal(mutex,);,signal(full);,until false;,end,consumer:begin,repeat,wait(full);,wait(mutex,);,nextc,:=buffer(out);,out:=(out+1)mod n;,signal(mutex,);,signal(empty);,consumer the item in,nextc,;,until false;,end,parend,end,2.,利用,AND,信号量解决生产者,消费者问题,ar,mutex,empty,full:semaphore,=1,n,0;,buffer:array,0,n-1,of item;,in,out:integer,:=0,0;,begin,parbegin,producer:begin,repeat,produce an item in,nextp,;,Swait(empty,mutex,);,buffer(in,):=,nextp,;,in:=(in+1)mod n;,Ssignal(mutex,full);,until false;,end,consumer:begin,repeat,Swait(full,mutex,);,nextc,:=,buffer(out,);,out:=(out+1)mod n;,Ssignal(mutex,empty);,consumer the item in,nextc,;,until false;,end,parend,end,生产者与消费者对单缓冲区的同步,信号量,S1,：缓冲区空否（初值为,1,）,S2,：缓冲区满否（初值为,0,）,生产者进程,L1,：,wait,（,S1,）,生产产品,signal,（,S2,）,goto,L1,消费者进程,L2,：,wait,（,S2,）,从缓冲区消费产品,signal,（,S1,）,goto,L2,【,思考题,】,【,思考题,】,如果生产者消费者问题中的缓冲区是无界的，又该如何解呢？,设信号量,S1,mutex,初值分别为,0,，,1,P,：,i=0;while(1),生产产品,;,P(mutex,);,往,Buffer i,放产品,;,i=(i+1)%n;,V(mutex,);V(S1);,;,Q,：,j=0;,while(1),P(S1);,P(mutex,);,从,Bufferj,取产品,;,j=(j+1)%n;,V(mutex,);,消费产品,;,;,2.4.2,哲学家进餐问题,1.,利用记录型信号量解决哲学家进餐问题,有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。,为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：,Var,chopstick:array,0,4,of semaphore;,所有信号量均被初始化为,1,，第,i,位哲学家的活动可描述为：,repeat,wait(chopstick,i,);,wait(chopstick,(i+1)mod 5,);,eat;,signal(chopstick,i,);,signal(chopstick,(i+1)mod 5,);,think;,until false;,可采取以下几种解决方法：,(1),至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。,(2),仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。,(3),规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是,1,、,2,号哲学家竞争,1,号筷子；,3,、,4,号哲学家竞争,3,号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能,获得两只筷子而进餐。,2.,利用,AND,信号量机制解决哲学家进餐问题,在哲学家进餐问题中，要求每个哲学家先获得两个临界资源,(,筷子,),后方能进餐，这在本质上就是前面所介绍的,AND,同步问题，故用,AND,信号量机制可获得最简洁的解法。,Var,chopsiick,array,0,4,of semaphore =(1,1,1,1,1);,processi,repeat,think;,Sswait(chopstick,(i+1)mod 5,chopstick,i,);,eat;,Ssignat(chopstick,(i+1)mod 5,chopstick,i,);,until false;,2.4.3,读者,-,写者问题,1.,利用记录型信号量解决读者,-,写者问题,允许多个进程同时读一个共享对象，但不允许一个,Write,进程和其他的,Reader,进程或,Writer,进程同时访问对象。,为实现,Reader,与,Writer,进程间在读或写时的互斥而设置了一个互斥信号量,Wmutex,。,另外，再设置一个整型变量,Readcount,表示正在读的进程数目。,还应该为,Readcount,设置一个互斥信号量,rmutex,。,读者,-,写者问题可描述如下：,Var,rmutex,wmutex:semaphore,:=1,1;,Readcount:integer,:=0;,begin,parbegin,Reader:begin,repeat,wait(rmutex,);,if,readcount,=0 then,wait(wmutex,);,Readcount,:=Readcount+1;,signal(rmutex,);,perform read operation;,wait(rmutex,);,readcount,:=readcount-1;,if,readcount,=0 then,signal(wmutex,);,signal(rmutex,);,until false;,end,writer:begin,repeat,wait(wmutex,);,perform write operation;,signal(wmutex,);,until false;,end,parend,end,2.,利用信号量集机制解决读者,-,写者问题,Var,RN integer;L,mx:semaphore,=RN,1;,reader:begin,repeat,Swait(L,1,1);,Swait(mx,1,0);,perform read operation;,Ssignal(L,1);,until false;,end,writer:begin,repeat,Swait(mx,1,1;L,RN,0);,perform write operation;,Ssignal(mx,1);,until false;,end,parend,end,思考,对于,N,个并发进程，信号量的取值范围是什么，有什么含义。,信号量及,P,、,V,操作讨论,对于两个并发进程，互斥信号量的值仅取,1,、,0,和,-1,三个值,若,1,表示没有进程进入临界区,若,0,表示有一个进程进入临界区,若,-1,表示一个进程进入临界区，另一个进程等待进入。,信号量及,P,、,V,操作讨论（续,1,）,1),信号量的物理含义：,S0,表示有,S,个资源可用,S=0,表示无资源可用,S0,则,|S|,表示,S,等待队列中的进程个数,wait(S,),：表示申请一个资源,signal(S,),：表示释放一个资源。,信号量的初值应该大于等于,0,信号量及,P,、,V,操作讨论（续,2,）,2)wait,、,signal,操作必须成对出现，有一个,wait,操作就一定有一个,signal,操作,当为互斥操作时，它们同处于同一进程,当为同步操作时，则不在同一进程中出现,如果,wait(S1),和,wait(S2),两个操作在一起，那么,wait,操作的顺序至关重要，而两个,signal,操作无关紧要,一个同步,wait,操作与一个互斥,wait,操作在一起时同步,wait,操作在互斥,Swait,操作前,信号量及,P,、,V,操作讨论（续,3,）,3,）,wait,、,signal,操作的优缺点,优点：,简单，而且表达能力强（用,wait,、,signal,操作可解决任何同步互斥问题）,缺点：,不够安全，,wait,、,signal,操作使用不当会出现死锁；,遇到复杂同步互斥问题时实现复杂,【,思考题,】,如图，试用信号量实现这三个进程的同步。,解：设有两个信号量,S1,、,S2,，初值均为,P1,：,P2,：,P3,：,wait(S1),signa