《第二章 进程管理.ppt》由会员分享，可在线阅读，更多相关《第二章 进程管理.ppt（236页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章 进程管理进程管理 2.1 2.1 进程的基本概念进程的基本概念 2.2 2.2 进程控制进程控制 2.3 2.3 进程同步进程同步 2.4 2.4 经典进程的同步问题经典进程的同步问题 2.5 2.5 进程通信进程通信 2.6 2.6 线程线程 教学目的与要求教学目的与要求n理解进程和线程的概念理解进程和线程的概念n掌握进程的基本状态及状态转换的原因掌握进程的基本状态及状态转换的原因n掌握进程控制的原理及其实现掌握进程控制的原理及其实现n掌握进程同步机制并能使用信号量解决进程掌握进程同步机制并能使用信号量解决进程同步问题同步问题n掌握进程间通信的原理和实现方法掌握进程间通信的原理
2、和实现方法教学重点教学重点：进程控制的原理及其实现，进程同步：进程控制的原理及其实现，进程同步机制，使用信号量解决进程同步问题，进程间通机制，使用信号量解决进程同步问题，进程间通信的原理和实现方法信的原理和实现方法教学难点教学难点：进程同步机制，使用信号量解决进程：进程同步机制，使用信号量解决进程同步问题同步问题2.1 进程的基本概念进程的基本概念 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征 1.程序的顺序执行程序的顺序执行 仅仅当当前前一一操操作作(程程序序段段)执执行行完完后后，才才能能执执行行后后继继操操作作。例例如如，在在进进行行计计算算时时，总总须须先先输输入入用用户户
3、的的程程序和数据，然后进行计算，最后才能打印计算结果。序和数据，然后进行计算，最后才能打印计算结果。S1:a=x+y;S2:b=a-5;S3:c=b+1;图 2-1 程序的顺序执行 2.程序顺序执行时的特征程序顺序执行时的特征(1)顺序性：顺序性：(2)封闭性：封闭性：(3)可再现性：可再现性：2.1.2 前趋图前趋图 前趋图(Precedence Graph)是一个有向无循环有向无循环图图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Part
4、ial Order)或前趋关系(Precedence Relation)“”2.1.2 前趋图前趋图 =(Pi,Pj)|Pi must complete before Pj may start,如果(Pi,Pj),可写成PiPj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。在图2-1(a)和2-1(b)中分别存在着这样的前驱关系：IiCiPi和和S1S2S3 图 2-2 前趋图 对
5、于图 2-2(a)所示的前趋图，存在下述前趋关系：P1P2,P1P3,P1P4,P2P5,P3P5,P4P6,P4P7,P5P8,P6P8,P7P9,P8P9或表示为：P=P1,P2,P3,P4,P5,P6,P7,P8,P9=(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)应当注意，前前趋趋图图中中必必须须不不存存在在循循环环，但在图2-2(b)中却有着下述的前趋关系：S2S3,S3S2 2.1.3 程序的并发执行及其特征程序的并发执行及其特征 1.程序的并发执行程序的
6、并发执行 图 2-3 并发执行时的前趋图 在该例中存在下述前趋关系：在该例中存在下述前趋关系：IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1而而Ii+1和和Ci及及Pi-1是是重重迭迭的的，亦亦即即在在Pi-1和和Ci以以及及Ii+1之之间间，可以并发执行。可以并发执行。图 2-4 四条语句的前趋关系对于具有下述四条语句的程序段：S1:a=x+2 S2:b=y+4 S3:c=a+b S4:d=c+b 2.程序并发执行时的特征程序并发执行时的特征 1)间断性间断性2)失去封闭性失去封闭性 3)不可再现性不可再现性 例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，
7、都要做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)结构特征结构特征2)动态性动态性 3)并发性并发性 4)独立性独立性 5)异步性异步性 较典型的进程定义有：较典型的进程定义有：(1)进程
8、是程序的一次执行。进程是程序的一次执行。(2)进进程程是是一一个个程程序序及及其其数数据据在在处处理理机机上上顺顺序序执行时所发生的活动。执行时所发生的活动。(3)进进程程是是程程序序在在一一个个数数据据集集合合上上运运行行的的过过程程，它是系统进行资源分配和调度的一个它是系统进行资源分配和调度的一个独立独立单位。单位。在在引引入入了了进进程程实实体体的的概概念念后后，我我们们可可以以把把传传统统OS中中的的进进程程定定义义为为：“进进程程是是进进程程实实体体的的运运行行过过程程，是是系系统统进进行行资资源源分分配配和和调调度度的的一一个个独独立立单单位位”。2.进程的三种基本状态进程的三种基
9、本状态 1)就绪就绪(Ready)状态状态 2)执行状态执行状态3)阻塞状态阻塞状态 图 2-5 进程的三种基本状态及其转换 Representation of Process Scheduling3.挂起状态挂起状态1)引入挂起状态的原因引入挂起状态的原因(1)终端用户的请求。终端用户的请求。(2)父进程请求。父进程请求。(3)负荷调节的需要。负荷调节的需要。(4)操作系统的需要。操作系统的需要。(5)内存资源紧张，需要将某些进程挂起，对换内存资源紧张，需要将某些进程挂起，对换到磁盘中到磁盘中2)2)进程状态的转换进程状态的转换进程状态的转换进程状态的转换 (1)活动就绪活动就绪静止就绪。静
10、止就绪。(2)活动阻塞活动阻塞静止阻塞。静止阻塞。(3)静止就绪静止就绪活动就绪。活动就绪。(4)静止阻塞静止阻塞活动阻塞。活动阻塞。图 2-6 具有挂起状态的进程状态图 Addition of Medium Term Scheduling4.进程的创建终止和终止状态进程的创建终止和终止状态nAs a process executes,it changes statennew:The process is being created.nrunning:Instructions are being executed.nwaiting:The process is waiting for some
11、 event to occur.nready:The process is waiting to be assigned to a processor.nterminated:The process has finished execution.Diagram of Process State图图2-7 进程的五种状态及其转换进程的五种状态及其转换4.进程的创建终止和终止状态进程的创建终止和终止状态图2-8 具有创建、终止和挂起状态的进程状态图2.1.5 进程控制块进程控制块 1.进程控制块的作用进程控制块的作用 进进程程控控制制块块的的作作用用是是使使一一个个在在多多道道程程序序环环境境下下
12、不不能能独独立立运运行行的的程程序序(含含数数据据)，成成为为一一个个能能独独立立运运行行的的基基本本单单位位，一一个个能能与与其其它它进进程程并并发发执执行行的的进进程程。或或者者说说，OS是是根根据据PCB来来对对并并发发执执行行的的进程进行控制和管理的进程进行控制和管理的。PCB是进程存在的唯一标志！是进程存在的唯一标志！2.进程控制块中的信息进程控制块中的信息 1)进程标识符 进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：(1)内部标识符。在所有的操作系统中，都为每一个进程赋予一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。2.进程控制
13、块中的信息进程控制块中的信息(2)外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。2)处理机状态处理机状态 处理机状态信息主要是由处理机的各种寄存器中的内容组成的。通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有 832 个通用寄存器，在RISC结构的计算机中可超过 100 个；指令计数器，其中存放了要访问的下一条指令的地址；2)处理机状态处理机状态 程序状态字PSW，其中含有状态信息，如条件码、执行方
14、式、中断屏蔽标志等；用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。3)进程调度信息进程调度信息 在PCB中还存放一些与进程调度和进程对换有关的信息，包括：进程状态，指明进程的当前状态，作为进程调度和对换时的依据；进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；3)进程调度信息进程调度信息 进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。4)进程控制信
15、息进程控制信息 进程控制信息包括：程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；4)进程控制信息进程控制信息 资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。Process Control Block(PCB)Information associated with each process.
16、nProcess statenProgram counternCPU registersnCPU scheduling informationnMemory-management informationnAccounting informationnI/O status information上下文切换（上下文切换（Context Switch）nWhen CPU switches to another process,the system must save the state of the old process and load the saved state for the new p
17、rocess.nContext-switch time is overhead;the system does no useful work while switching.nTime dependent on hardware support.CPU Switch From Process to Process3.进程控制块的组织方式进程控制块的组织方式 1)链接方式 图 2-9 PCB链接队列示意图 Ready Queue And Various I/O Device Queues2)索引方式索引方式 图 2-10 按索引方式组织PCB 2.2 进进 程程 控控 制制 2.2.1 进程的创
18、建进程的创建 1.进程图(Process Graph)图 2-9 进程树 Processes Tree on a UNIX System2.引起创建进程的事件引起创建进程的事件(1)用户登录。(2)作业调度。(3)提供服务。(4)应用请求。3.进程的创建进程的创建(Creation of Progress)(1)申请空白PCB。(2)为新进程分配资源。(3)初始化进程控制块。(4)将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。Process CreationnParent process create children processes,which,in tu
19、rn create other processes,forming a tree of processes.nResource sharingnParent and children share all resources.nChildren share subset of parents resources.nParent and child share no resources.nExecutionnParent and children execute concurrently.nParent waits until children terminate.Process Creation
20、(Cont.)nAddress spacenChild duplicate of parent.nChild has a program loaded into it.nUNIX examplesnfork system call creates new processnexec system call used after a fork to replace the process memory space with a new program.fork-fork-fork-fork-创建进程创建进程创建进程创建进程fork()=0-子进程返回子进程pid-父进程返回1、调用格式2、使用方法
21、 main().while(x=fork()=-1);if(x=0)子进程语句 else 父进程语句 父、子都执行语句；例：main()int x;while(x=fork()=-1);if(x=0)printf(“a”);else printf(“b”);printf(“c”);abcc?bcac?bacc?acbc?cabc?fork例main()int child,i=2;if(child=fork()=-1)printf(fork error.);exit();if(child=0)i=i+3;printf(“i=%dn”,i);i=i+5;printf(“i=%dn”,i);1.fo
22、rk error2.i=5 i=10 i=73.i=7 i=5 i=104.i=5 i=7 i=10插入else呢？父子1子2main()if(fork()=0)子1的代码段 else if(fork()=0)子2的代码段 else 父代码段 父子1子2main()if(fork()=0)子1的代码段;if(fork()=0)子2的代码段 else 子1的代码段 else 父代码段去掉这个去掉这个else谁执行这一段？谁执行这一段？2.2.2 进程的终止进程的终止 1.引起进程终止引起进程终止(Termination of Process)的事件的事件 1)正常结束正常结束 在在任任何何计计算
23、算机机系系统统中中，都都应应有有一一个个用用于于表表示示进进程程已已经经运运行行完完成成的的指指示示。例例如如，在在批批处处理理系系统统中中，通通常常在在程程序序的的最最后后安安排排一一条条Holt指指令令或或终终止止的的系系统统调调用用。当当程程序序运运行行到到Holt指指令令时时，将将产产生生一一个个中中断断，去去通通知知OS本本进进程程已已经经完完成成。在在分分时时系系统统中中，用用户户可可利利用用Logs off去去表表示示进进程程运运行行完完毕毕，此此时时同同样样可可产产生生一一个个中中断断，去去通通知知OS进进程程已已运运行行完毕。完毕。2)异常结束异常结束在进程运行期间，由于出现
24、某些错误和故障而迫使进程终止。这类异常事件很多，常见的有：越界错误。这是指程序所访问的存储区，已越出该进程的区域；保护错。进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只读文件；非法指令。程序试图去执行一条不存在的指令。出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了指令；特权指令错。用户进程试图去执行一条只允许OS执行的指令；2)异常结束异常结束 运行超时。进程的执行时间超过了指定的最大值；等待超时。进程等待某事件的时间，超过了规定的最大值；算术运算错。进程试图去执行一个被禁止的运算，例如，被0除；I/O故障。这是指在I/O过程中发生
25、了错误等。操作员或操作系统干预。父进程请求。父进程终止。3)外界干预外界干预 (1)根根据据被被终终止止进进程程的的标标识识符符，从从PCB集集合合中中检检索索出出该该进程的进程的PCB，从中读出该进程的状态。，从中读出该进程的状态。(2)若若被被终终止止进进程程正正处处于于执执行行状状态态，应应立立即即终终止止该该进进程程的的执执行行，并并置置调调度度标标志志为为真真，用用于于指指示示该该进进程程被被终终止止后后应应重新进行调度。重新进行调度。(3)若若该该进进程程还还有有子子孙孙进进程程，还还应应将将其其所所有有子子孙孙进进程程予予以终止，以防他们成为不可控的进程。以终止，以防他们成为不可
26、控的进程。(4)将将被被终终止止进进程程所所拥拥有有的的全全部部资资源源，或或者者归归还还给给其其父父进程，进程，或者归还给系统。或者归还给系统。(5)将被终止进程将被终止进程(它的它的PCB)从所在队列从所在队列(或链表或链表)中移出，中移出，等待其他程序来搜集信息。等待其他程序来搜集信息。2.进程的终止过程进程的终止过程2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 1)请求系统服务 2)启动某种操作 3)新数据尚未到达 4)无新工作可做 2.进程阻塞过程进程阻塞过程入口入口保存当前的保存当前的CPU现场现场置进程的状态置进程的状态被阻塞进
27、程入等待队列被阻塞进程入等待队列转进程调度转进程调度 3.进程唤醒过程进程唤醒过程入口入口从等待队列中摘下被唤醒的进程从等待队列中摘下被唤醒的进程将被唤醒进程置为就绪态将被唤醒进程置为就绪态将被唤醒进程送入就绪队列将被唤醒进程送入就绪队列转进程调度或返回转进程调度或返回2.2.4 进程的挂起与激活进程的挂起与激活 1.进程的挂起进程的挂起 当当出出现现了了引引起起进进程程挂挂起起的的事事件件时时，系系统统将将利利用用挂挂起起原语原语suspend()将指定进程或处于阻塞状态的进程挂起。将指定进程或处于阻塞状态的进程挂起。挂挂起起原原语语的的执执行行过过程程是是：首首先先检检查查被被挂挂起起进进
28、程程的的状状态态，若若处处于于活活动动就就绪绪状状态态，便便将将其其改改为为静静止止就就绪绪；对对于于活活动动阻阻塞塞状状态态的的进进程程，则则将将之之改改为为静静止止阻阻塞塞。为为了了方方便便用用户户或或父父进进程程考考查查该该进进程程的的运运行行情情况况而而把把该该进进程程的的PCB复复制制到到某某指指定定的的内内存存区区域域。最最后后，若若被被挂挂起起的的进进程程正正在在执行，则转向执行，则转向调度程序重新调度调度程序重新调度。2.进程的激活过程进程的激活过程 当当发发生生激激活活进进程程的的事事件件时时，系系统统将将利利用用激激活活原原语语active()将将指指定定进进程程激激活活。
29、激激活活原原语语先先将将进进程程从从外外存存调调入入内内存存，检检查查该该进进程程的的现现行行状状态态，若若是是静静止止就就绪绪，便便将将之之改改为为活活动动就就绪绪；若为静止阻塞便将之改为活动阻塞。若为静止阻塞便将之改为活动阻塞。假假如如采采用用的的是是抢抢占占调调度度策策略略，则则每每当当有有新新进进程程进进入入就就绪绪队列时，应检查是否要进行重新调度。队列时，应检查是否要进行重新调度。2.3 进进 程程 同同 步步 2.3.1 进程同步的基本概念进程同步的基本概念 1.两种形式的制约关系两种形式的制约关系(1)间接相互制约关系。间接相互制约关系。(2)直接相互制约关系。直接相互制约关系。
30、2.临界资源临界资源(Critical Resouce)生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是：有一一群群生生产产者者进进程程在生产产品，并将这些产品提供给消消费费者者进进程程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个个缓缓冲冲区区的的缓缓冲冲池池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步必须保持同步，即不允不允许消费者进程到一个空缓冲区去取产品；也不允许消费者进程到一个空缓冲区去取产品；
31、也不允许生产者进程向一个已装满产品且尚未被取走的许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。缓冲区中投放产品。我们可利用一个数组来表示上述的具有n个(0，1，n-1)缓冲区的缓冲池。用输输入入指指针针in来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1；用一个输输出出指指针针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1。由于这里的缓冲池是组织成循环缓冲的，故应把输入指针加1表示成 in=(in+1)mod n；输出指针加1表示成out=(out+1)mod n。当(in+1)mod n=out时表示缓冲池满
32、时表示缓冲池满；而in=out则表示缓冲池空则表示缓冲池空。此外，还引入了一个整型变整型变量量counter,其初始值为0。每当生产者进程向缓冲池中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时，使counter减1。生产者和消费者两进程共享下面的变量：Var n,integer;type item=;var buffer:array0,1,n-1 of item;in,out:0,1,n-1;counter:0,1,n;指指针针in和和out初初始始化化为为1。在在生生产产者者和和消消费费者者进进程程的的描描述述中中，no-op是是一一条条空空操操作作指指令令，
33、while condition do no-op语语句句表表示示重重复复的的测测试试条条件件(condication)，重重复复测测试试应应进进行行到到该该条条件件变变为为false(假假)，即即到到该该条条件件不不成成立立时时为为止止。在在生生产产者者进进程程中中使使用用一一局局部部变变量量nextp，用用于于暂暂时时存存放放每每次次刚刚生生产产出出来来的的产产品品；而而在在消消费费者者进进程程中中，则则使使用用一一个个局局部部变变量量nextc,用用于存放每次要消费的产品。于存放每次要消费的产品。producer:repeat produce an item in nextp;while
34、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 =bufferout;out =(out+1)mod n;counter =counter-1;consumer the item in nextc;until false;虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。
35、生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：register 1=counter;register 2 =counter;register1=register1+1;register 2 =register2-1;counter=register 1;counter =register 2;假设：counter的当前值是5。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句，则最后共享变量counter的值仍为5；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，counter值也还
36、是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)正确的值应该为5，但现在是4.还可能出现答案为6的情况。失去可再现性失去可再现性3.临界区临界区(critical section)可把一个访问临界资源
37、的循环进程描述如下：repeat critical section;remainder section;until false;entry sectionexit section4.同步机制应遵循的规则同步机制应遵循的规则(1)空闲让进。(2)忙则等待。(3)有限等待。(4)让权等待。2.3.2 信号量机制信号量机制 1.整型信号量整型信号量 最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原原子子操操作作(Atomic Operation)wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。wait和signal操作可描述为：wai
38、t(S):while S0 do no-op S=S-1;signal(S):S=S+1;2.记录型信号量记录型信号量 在在整整型型信信号号量量机机制制中中的的wait操操作作，只只要要是是信信号号量量S0，就就会会不不断断地地测测试试。因因此此，该该机机制制并并未未遵遵循循“让让权权等待等待”的准则的准则，而是使进程处于而是使进程处于“忙等忙等”的状态。的状态。记记录录型型信信号号量量机机制制，则则是是一一种种不不存存在在“忙忙等等”现现象象的的进进程程同同步步机机制制。但但在在采采取取了了“让让权权等等待待”的的策策略略后后，又又会会出出现现多多个个进进程程等等待待访访问问同同一一临临界界
39、资资源源的的情情况况。为为此此，在在信信号号量量机机制制中中，除除了了需需要要一一个个用用于于代代表表资资源源数数目目的的整整型型变变量量value外外，还还应应增增加加一一个个进进程程链链表表L，用用于于链链接接上上述的所有等待进程。述的所有等待进程。记记录录型型信信号号量量是是由由于于它它采采用用了了记记录录型型的的数数据据结结构构而而得名的。它所包含的上述两个数据项可描述为：得名的。它所包含的上述两个数据项可描述为：type semaphore=record value:integer;L:list of process;end相应地，wait(S)和signal(S)操作可描述为：pr
40、ocedure wait(S)var S:semaphore;begin S.value =S.value-1;if S.value0 then block(S,L)end procedure signal(S)var S:semaphore;begin S.value =S.value+1;if S.value0 then wakeup(S,L);endnS.value的初的初值值表示系表示系统统中某中某类资类资源的数目，源的数目，因而又称因而又称为资为资源信号量源信号量.n每次每次wait操作，意味着操作，意味着进进程程请请求一个求一个单单位的位的该类资该类资源，因此源，因此描述描述为为S
41、.value =S.value-1；n 当当S.value0时时，表示，表示该类资该类资源已分配完源已分配完毕毕，因此，因此进进程程应调应调用用block原原语语，进进行自我阻塞，放弃行自我阻塞，放弃处处理机，并插入到信号量理机，并插入到信号量链链表表S.L中。中。n可可见见，该该机制遵循了机制遵循了“让权让权等待等待”准准则则。此此时时S.value的的绝对绝对值值表示在表示在该该信号量信号量链链表中已阻塞表中已阻塞进进程的数目。程的数目。n 对对信信号号量量的的每每次次signal操操作作，表表示示执执行行进进程程释释放放一一个个单单位位资资源源，故故S.value =S.value+1操
42、操作作表表示示资资源源数目加数目加1。n 若若加加1后后仍仍是是S.value0，则则表表示示在在该该信信号号量量链链表表中中，仍仍有有等等待待该该资资源源的的进进程程被被阻阻塞塞，故故还还应应调调用用wakeup原原语语，将，将S.L链链表中的第一个等待表中的第一个等待进进程程唤唤醒。醒。n如如果果S.value的的初初值值为为1，表表示示只只允允许许一一个个进进程程访访问问临临界界资资源，此源，此时时的信号量的信号量转转化化为为互斥信号量互斥信号量。3.AND型信号量型信号量 在两个进程中都要包含两个对在两个进程中都要包含两个对Dmutex和和Emutex的操作，的操作，即即process
43、 A:process B:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若进程若进程A和和B按下述次序交替执行按下述次序交替执行wait操作：操作：process A:wait(Dmutex);于是于是Dmutex=0process B:wait(Emutex);于是于是Emutex=0process A:wait(Emutex);于是于是Emutex=-1 A阻塞阻塞process B:wait(Dmutex);于是于是Dmutex=-1 B阻塞阻塞 AND同同步步机机制制的的基基本本思思想想是：将进程在整个运行过程中需要的所有资源，
44、一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原原子子操操作方式作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为 AND同 步，或 称 为 同 时 wait操 作，即Swait(Simultaneous wait)定义如下：Swait(S1,S2,Sn)if S11 and and Sn1 then for i =1 to n do Si=Si-1;endfor else place
45、 the process in the waiting queue associated with the first Si found with Si1,and set the program count of this process to the beginning of Swait operation endifSsignal(S1,S2,Sn)for i =1 to n do Si=Si+1;Remove all the process waiting in the queue associated with Si into the ready queue.endfor;2.3.3
46、信号量的应用信号量的应用 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 u
47、ntil false;end parend 2.利用信号量实现前趋关系利用信号量实现前趋关系 图 2-12 前趋图举例 abcdfge Var 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;begin wait(d);S5;signal(g);end;begin wa
48、it(e);wait(f);wait(g);S6;end;parend end 2.3.4 管管 程程 机机 制制 1.管程的定义管程的定义 管程由三部分组成：局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的数据设置初始值的语句。此外，还须为管程赋予一个名字。图 2-13 管程的示意图 管程的语法如下：管程的语法如下：type monitor-name=monitor variable declarations procedure entry P1();begin end;procedure entry P2();begin end;procedure entry Pn
49、();begin end;begin initialization code;end 2.条件变量条件变量 管程中对每个条件变量，都须予以说明，其形式为：Var x,y:condition。该变量应置于wait和signal之前，即可表示为X.wait和X.signal。例如，由于共享数据被占用而使调用进程等待，该条件变量的形式为：nonbusy:condition。此时，wait原 语 应 改 为 nonbusy.wait，相 应 地，signal应 改 为nonbusy.signal。应当指出，X.signal操作的作用，是重新启动一个被阻塞的进程，但如果没有被阻塞的进程，则X.signa
50、l操作不产生任何后果。这与信号量机制中的signal操作不同。因为，后者总是要执行s =s+1操作，因而总会改变信号量的状态。如果有进程Q处于阻塞状态，当进程P执行了X.signal操作后，怎样决定由哪个进行执行，哪个等待，可采用下述两种方式之一进行处理：(1)P等待，直至Q离开管程或等待另一条件。(2)Q等待，直至P离开管程或等待另一条件。采用哪种处理方式，当然是各执一词。但是Hansan却采用了第一种处理方式。华中理工大学1999年试题，哈工大2000年试题司机和售票员之间的同步关系司机和售票员之间的同步关系n司机只有在售票员关车门后，才能启动汽车。n售票员只有在司机到站停车后，才能开车门