os操作系统02.ppt

单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击以编辑,母版标题样式,第二章 进程管理,2.1,进程的基本概念,2.2,进程控制,2.3,进程同步,2.4,经典进程的同步问题,2.5,管程机制,2.6,进程通信,2.7,线程,1,2.1,进程的基本概念,2.1.1,程序的顺序执行及其特征,2.1.2,前趋图,2.1.3,程序的并发执行及其特征,2.1.4,进程的特征与状态,2.1.5,进程控制块,2,1.,程序的顺序执行,仅当前一操作,(,程序段,),执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。,S,1,:,ax+y;,S,2,:,b=,a-5;,S,3,:,c=,b+1;,2.1.1,程序的顺序执行及其特征,图,2-1,程序的顺序执行,3,2.,程序顺序执行时的特征,顺序性：,(2),封闭性：,(3),可再现性：,4,前趋图,(,Precedence Graph),是一个有向无循环图，记为,DAG(Directed,Acyclic,Graph),，,用于描述进程之间执行的前后关系。,结点：一个程序段、进程、一条语句；,结点间的有向边：两个结点之间存在的偏序,(,Partial Order),或前趋关系,(,Precedence Relation)“”,。,P,i,P,j,，称,P,i,是,P,j,的直接前趋，而称,P,j,是,P,i,的直接后继。,初始结点,(,Initial Node,),：没有前趋的结点,终止结点,(,Final Node,),：,没,有后继的结点,。,2.1.2,前趋图,5,每个结点还具有一个重量,(,Weight),，,用于表示该结点所含有的程序量或结点的执行时间。,I,i,C,i,P,i,和,S,1,S,2,S,3,图,2-2,前趋图,6,对于图,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,7,1.,程序的并发执行,图,2-3,并发执行时的前趋图,2.1.3,程序的并发执行及其特征,前趋关系：,IiCi,，,IiIi+1,CiPi,CiCi+1,，,PiPi+1,而,I,i+1,和,Ci,及,P,i-1,是重迭的，亦即在,Pi,-1,和,Ci,以及,Ii,+1,之间，可以并发执行。,8,对于具有下述四条语句的程序段：,S,1,:a=x+2,S,2,:b=y+4,S,3,:c=a+b,S,4,:d=c+b,图,2-4,四条语句的前趋关系,9,2.,程序并发执行时的特征,间断性 执行暂停执行,2),失去封闭性 资源共享,3),不可再现性 多次执行结果不同,例如，有两个循环程序,A,和,B,，,它们共享一个变量,N,。,程序,A,每执行一次时，都要做,N=N+1,操作；程序,B,每执行一次时，都要执行,PrintN),操作，然后再将,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,。,10,1.,进程的特征和定义,结构特征 程序段、数据段、,PCB,动态性 进程最基本特征，生命期,并发性 多进程,独立性 进程独立运行、分配资源、调度,异步性 运行速度不可知,2.1.4,进程的特征与状态11,较典型的进程定义有：,(1),进程是程序的一次执行。,(2),进程是一个程序及其数据在处理机上顺序执行时所发生的活动。,(3),进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。,在引入了进程实体的概念后，我们可以把传统,OS,中的进程定义为：“进程是进程实体的运,行过程，是系统进行资源分配和调度的一个独立单位”。,12,2.,进程的三种基本状态,就绪,(,Ready),状态：等待,CPU,，就绪队列,执行状态,阻塞状态：暂停，阻塞队列,图,2-5,进程的三种基本状态及其转换,13,3.,挂起状态,引入挂起状态的原因,终端用户的请求调试。,(2),父进程请求修改、协调子进程。,(3),负荷调节的需要。,(4),操作系统的需要检查资源、记帐。,14,2),进程状态的转换,活动就绪静止就绪。,(2),活动阻塞静止阻塞。,(3),静止就绪活动就绪。,(4),静止阻塞活动阻塞。,挂起原语,suspend,激活原语,active,图,2-6,具有挂起状态的进程状态图,15,1.,进程控制块的作用,进程控制块的作用是使一个在多道程序环境下不能独立运行的程序,(,含数据,),，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，,OS,是根据,PCB,来对并发执行的进程进行控制和管理的。,2.1.5,进程控制块,16,2.,进程控制块中的信息,1),进程标识符,进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：,(1),内部标识符。在所有的操作系统中，都为每一个进 程赋予一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。,(2),外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户,(,进程,),在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此,外，还可设置用户标识，以指示拥有该进程的用户。,17,2),处理机状态,处理机状态信息主要是由处理机的各种寄存器中的内容组成的。通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有,832,个通用寄存器，在,RISC,结构的计算机中可超过,100,个；指令计数器，其中存放了要访问的下一条指令的地址；程序状态字,PSW,，,其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；用户栈指针，指每个用户进程都有一个或若干个与之相关的系,统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。,18,3),进程调度信息,在,PCB,中还存放一些与进程调度和进程对换有关的信息，包括：进程状态，指明进程的当前状态，作为进程调度和对换时的依据；进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待,CPU,的时间总和、进程已执行的时间总和等；事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即,阻塞原因。,19,4),进程控制信息,进程控制信息包括：程序和数据的地址，是指进程的程序和数据所在的内存或外存地,(,首,),址，以便再调度到该进程执行时，能从,PCB,中找到其程序和数据；进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在,PCB,中；资源清单，是一张列出了除,CPU,以外的、进程所需的全部资源及已经分配到该进程的资源的清单；链接指针，它给出了本进程,(,PCB),所在队列中,的下一个进程的,PCB,的首地址。,20,3.,进程控制块的组织方式,1),链接方式,图,2-7,PCB,链接队列示意图,21,2),索引方式,图,2-8,按索引方式组织,PCB,22,2.2.1,进程的创建,进程图,(,Process Graph,),子进程可以继承父进程的资源（如打开的文件、权限等）,图,2-9,进程树,2.2,进 程 控 制,23,2.,引起创建进程的事件,用户登录。,(2),作业调度。,(3),提供服务。,(4),应用请求。,24,3.,进程的创建,(,Creation of Progress),(1),申请空白,PCB,。,(2),为新进程分配资源。,(3)初始化进程控制块。,(4),将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队,列。,25,1.,引起进程终止,(,Termination of Process),的事件,1),正常结束,在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。例如，在批处理系统中，通常在程序的最后安排一条,Halt,指令或终止的系统调用。当程序运行到,Halt,指令时，将产生一个中断，去通知,OS,本进程已经完成。在分时系统中，用户可利用,Logs off,去表示进程运行完毕，此时同样可产生一个中断，去通知,OS,进程已运行完毕。,2.2.2,进程的终止,26,2),异常结束,越界错误。这是指程序所访问的存储区，已越出该进程的区域；,保护错。进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只读文件；,非法指令。程序试图去执行一条不存在的指令。出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了指令；,特权指令错。用户进程试图去执行一条只允许,OS,执行的指令；,运行超时。进程的执行时间超过了指定的最大值；,等待超时。进程等待某事件的时间，超过了规定的最大值；,算术运算错。进程试图去执行一个被禁止的运算，例如，被,0,除；,I/O,故障。这是指在,I/O,过程中发生了错误等。,27,3),外界干预,外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。,操作员或操作系统干预。由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程；,父进程请求。由于父进程具有终止自己的任何子孙进程的权利，因而当父进程提出请求时，系统将终止该进程；,父进程终止。当父进程终止,时，,OS,也将他的所有子孙进程终止，也可以继续存在。,28,2.,进程的终止过程,(1),根据被终止进程的标识符，从,PCB,集合中检索出该进程的,PCB,，,从中读出该进程的状态。,(2),若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。,(3),若该进程还有子孙进程，且要终止，则应将其所有子孙进程予以终止，以防他们成为不可控的进程。,(4),将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。,(5),将被终止进程,(,它的,PCB),从所在队列,(,或链表,),中移出，等待其他程序来搜集信息。,29,1.,引起进程阻塞和唤醒的事件,请求系统服务 如打印服务,启动某种操作,I/O,设备,新数据尚未到达 进程同步,无新工作可做 等待新任务,2.2.3,进程的阻塞与唤醒,30,2.,进程阻塞过程,正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用,阻塞原语,block,把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入,block,过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将,PCB,插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞,(,等待,),队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进,程的处理机状态,(,在,PCB,中,),，再按新进程的,PCB,中的处理机状态设置,CPU,的环境。,31,3.,进程唤醒过程,当被阻塞进程所期待的事件出现时，如,I/O,完成或其所期待的数据已经到达，则由有关进程,(,比如，用完并释放了该,I/O设备的进程,),调用,唤醒原语,wakeup,(),，,将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，,将其,PCB,中的现行状态由阻塞改为就绪，然后再将该,PCB,插入到就绪队列中。,32,1.,进程的挂起,当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起，系统将利用,挂起原语,suspend,(),将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。为了方便用户或父进程考查该进程的运行情况而把该进程的,PCB,复制到某指定的内存区域。最后，若被挂,起的进程正在执行，则转向调度程序重新调度。,2.2.4,进程的挂起与激活,33,2.,进程的激活过程,当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用,激活原语,active,(),将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把,处理机分配给刚被激活的进程。,34,2.3.1,进程同步的基本概念,1.,两种形式的制约关系,间接相互制约关系。资源共享,(2),直接相互制约关系。进程合作,2.3,进 程 同 步,35,2.,临界资源,(,Critical,Resouce,),生产者,-,消费者,(,producer-consumer),问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有,n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且,尚未被取走的缓冲区中投放产品。,36,数组,(0,，,1,，,，,n-1,),：缓冲区的循环缓冲池。,输入指针,in,：下一个可投放产品的缓冲区，当生产者进程生产并投放一个产品后，输入指针加,1,，,in=(in+1)mod n,输出指针,out,：下一个可从中获取产品的缓冲区，当消费者进程取走一个产品后，输出指针加,1,，,out=out+1)mod n,。,当,(,in+1)mod n=out,时表示缓冲池满；而,in=out,则表示缓冲池空。,整型变量,counter,其初始值为,0,。每当生产者进程向缓冲池中投放一个产品后，使,counter,加,1,；反之，每当消费者进程从中取走一个产品时，使,counter,减,1,。,37,生产者和消费者两进程共享下面的变,量：,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,。在生产者和消费者进程的描述中，,no-op,是一条空操作指令，,while condition do no-op,语句表示重复的测试条件,(condication,),，,重复测试应进行到该条件变为,false(,假,),，即到该条件不成立时为止。在生产者进程中使用一局部变量,nextp,，,用于暂时存放每次刚生产出来的产品；而在消费者进程中，则使用一个局部变,量,nextc,用于存放每次要消费的产品。,38,producer:repeat,produce an item in,nextp,;,while counter=n do no-op;,buffer,in,=,nextp,;,in =in+1 mod n;,counter =counter+1;,until false;,consumer:repeat,while counter=0 do no-op;,nextc,=buffer,out,;,out =(out+1)mod n;,counter =counter-1;,consumer the item in,nextc,;,until false;,39,虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量,counter,。,生产者对它做加,1,操作，消费者对它做减,1,操作，这两个操作在用机器语言实现时，常可用下面的形式描述：,register 1=counter;,register1 =register 1+1;,counter =register 1;,register 2 =counter;,register 2=register 2-1;,counter=register 2;,40,假设：,counter,的当前值是,5,。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句，则最后共享变量,counter,的值仍为,5,；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，,counter,值也还是,5,，但是如果按下述顺序执行：,register 1 =counter;(register 1=5),register 1 =register 1+1;(register 1=6),register 2 =counter;(register 2=5),register 2 =register 2-1;(register 2=4),counter =register 1;(counter=6),counter =register 2;(counter=4),41,3.,临界区,(,critical section),可把一个访问临界资源的循环进程描述如下：,repeat,critical sectionremainder section;,until false;,entry section,exit section,42,4.,同步机制应遵循的规则,空闲让进。,(2),忙则等待。,(3),有限等待。,(4),让权等待。,CPU,释放,43,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.3.2,信号量机制,44,2.,记录型信号量,在整型信号量机制中的,wait,操作，只要是信号量,S0,，,就会不断地测试，“忙等”的状态。因此，该机制并未遵循“让权等待”的准则。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量,value,外，,还应增加一个进程链表,L,，,用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数,据项可描述为：,type semaphore=record,value:integer;,L:list of process;,end,45,wait,(S),操作可描述为：,procedure wait(S),var,S:semaphore;,begin,S.,value,=S.value-1;,if S.value,0 then block(S,L),end,wait,操作：进程请求一个单位的该类资源，,S.value =S.value-1,；,当,S.value,0,时，表示该类资源已分配完毕，因此进程应调用,block,原语，进行自我阻塞，放弃处理机，并插入到信号量链表,S.L,中。可见，该机制遵循了“让权等待”准则。此时,S.value,的绝对值表示在该信号量链表中已阻塞进程的数目。,46,signal(S),操作可描述为：,procedure signal(S),var S:semaphore;,begin,S.value =S.value+1;,if S.value0 then wakeup(S,L);,end,signal,操作：执行进程释放一个单位资源，,S.value =S.value+1,。若加,1,后仍是,S.value0,，,则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用,wakeup,原语，将,S.L,链表中的第一个等待进程唤醒。,在记录型信号量机制中，,S.value,的初值表示系统中某类资源的数目，因而又称为,资源信号量,。,如果,S.value,的初值为,1,，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信,号量。,47,3.,AND,型信号量,在两个进程中都要包含两个对,Dmutex,和,Emutex,的操作（初值均为,1,），即,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,阻塞,48,AND,同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在,wait,操作中，增加了一个“,AND”,条件，故称为,AND,同步，,或称为同时,wait,操作。,49,定义如下,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,;,50,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,signal(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,;,51,一般“信号量集”的几种特殊情况：,(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,后，将阻止任何进程进入特定区。换言之，它相当于一个,可控开关,。,52,1.,利用信号量实现进程互斥,Var mutex,:semaphore =1;,begin,parbegin,process 1:begin,repeat,wait(,mutex,);,critical section,signal(,mutex,);,remainder,seetion,until false,;end,parend,2.3.3,信号量的应用,process 2:begin,repeat,wait(,mutex,);,critical section,signal(,mutex,);,remainder section until false;,end,53,2.,利用信号量实现前趋关系,图,2-10,前趋图举例,54,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,55,2.4.1,生产者,消费者问题,前面我们已经对生产者,消费者问题,(,The,proceducer,-consumer problem),做了一些描述，但未考虑进程的互斥与同步问题，因而造成了数据,Counter,的不定性。由于生产者,消费者问题是相互合作的进程关系的一种抽象，例如，在输入时，输入进程是生产者，计算进程是消费者；而在输出时，则计算进程是生产者，而打印进程是消费者，因此，,该问题有很大的代表性及实用价值。,2.4,经典进程的同步问题,56,1.,利用记录型信号量解决生产者,消费者问题,假定在生产者和消费者之间的公用缓冲池中，具有,n,个缓冲区，这时可利用互斥信号量,mutex,实现诸进程对缓冲池的互斥使用；利用信号量,empty和,full,分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产,者,消费者问题可描述如下：,57,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,parend,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,58,在生产者,消费者问题中应注意：首先，在每个程序中用于实现互斥的,wait(,mutex,),和,signal(,mutex,),必须成对地出现；其次，对资源信号量,empty,和,full,的,wait,和,signal,操作，同样需要成对地出现，但它们分别处于不同的程序中。例如，,wait(empty),在计算进程中，而,signal(empty),则在打印进程中，计算进程若因执行,wait(empty),而阻塞，则以后将由打印进程将它唤醒；最后，在每个程序中的多个,wait,操作顺序不能颠倒。应先执行对资源信号量的,wait,操作，然后再执行对互斥信号量的,wait,操作，否则可能引起进程死锁。,59,2.,利用,AND,信号量解决生产者,消费者问题,var 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,60,2.4.2,哲学家进餐问题,1.,利用记录型信号量解决哲学家进餐问题,5,哲学家，,5,个碗，,5,只筷子。经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：,Var,chopstick:array,0,4,of semaphore;,61,所有信号量均被初始化为,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;,62,同时拿左边筷子时死锁，可采取以下几种解决方法：,(1),至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。,(2),仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。,(3),规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是,1,、,2,号哲学家竞争,1,号筷子；,3,、,4,号哲学家竞争,3,号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能,获得两只筷子而进餐。,63,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;,64,2.4.3,读者,-,写者问题,1.,利用记录型信号量解决读者,-,写者问题,为实现,Reader,与,Writer,进程间在读或写时的互斥而设置了一个互斥信号量,Wmutex,。,另外，再设置一个整型变量,Readcount,表示正在读的进程数目。由于只要有一个,Reader,进程在读，便不允许,Writer,进程去写。因此，仅当,Readcount,0,表示尚无,Reader,进程在读时，,Reader,进程才需要执行,Wait(,Wmutex,),操作。若,wait(,Wmutex,),操作成功，,Reader,进程便可去读，相应地，做,Readcount,+1,操作。同理，仅当,Reader,进程在执行了,Readcount,减,1,操作后其值为,0,时，才须执行,signal(,Wmutex,),操作，以便让,Writer,进程写。又因为,Readcount,是一,个可被多个,Reader,进程访问的临界资源，因此，应该为它设置一个互斥信号量,rmutex,。,65,读者,-,写者问题可描述如下：,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,66,2.,利用信号量集机制解决读者,-,写者问题,Var,RN integer;,L,mx,:semaphore =RN,1;,begin,parbegin,reader:begin,repeat,Swait,(L,1,1);,Swait,(,mx,1,0);,perform,read operation;,Ssignal(L,1);,until f