进程管理part2.pptx

第二章 进 程 管 理 Heb Nomal University Department of Computer Science11.程序顺序执行时的特征程序顺序执行时的特征(1)顺序性：(2)封闭性：(3)可再现性：2.程序并发执行时的特征程序并发执行时的特征 1)间断性2)失去封闭性 3)不可再现性 u 简单回顾简单回顾第二章 进 程 管 理 Heb Nomal University Department of Computer Science2程序与进程之间的区别程序与进程之间的区别进程更能真实地描述进程更能真实地描述并发并发，而程序不能，而程序不能进程是由进程是由程序，数据和控制块程序，数据和控制块三部分组成的三部分组成的程序是静态的，进程是程序是静态的，进程是动态动态的的进程有进程有生命周期生命周期，有诞生有消亡，短暂的；而程序是，有诞生有消亡，短暂的；而程序是相对长久的相对长久的一个程序可对应一个程序可对应多个多个进程，反之亦然进程，反之亦然进程具有进程具有创建其他进程创建其他进程的功能，而程序没有的功能，而程序没有第二章 进 程 管 理 Heb Nomal University Department of Computer Science3 较典型的进程定义有：较典型的进程定义有：(1)进程是程序的一次执行。进程是程序的一次执行。(2)进进程程是是一一个个程程序序及及其其数数据据在在处处理理机机上上顺顺序序执执行行时时所所发生的活动。发生的活动。(3)进进程程是是程程序序在在一一个个数数据据集集合合上上运运行行的的过过程程，它它是是系系统进行资源分配和调度的一个独立单位。统进行资源分配和调度的一个独立单位。在在引引入入了了进进程程实实体体的的概概念念后后，我我们们可可以以把把传传统统OS中中的的进进程程定定义义为为：“进进程程是是进进程程实实体体的的运运行行过过程程，是是系系统统进进行行资源分配和调度的一个独立单位资源分配和调度的一个独立单位”。第二章 进 程 管 理 Heb Nomal University Department of Computer Science42.进程的三种基本状态进程的三种基本状态 1)就绪就绪(Ready)状态状态进程占有进程占有进程占有进程占有CPUCPU，并在，并在，并在，并在CPUCPU上运行上运行上运行上运行2)执行状态执行状态一个进程已经具备运行条件，但由于一个进程已经具备运行条件，但由于一个进程已经具备运行条件，但由于一个进程已经具备运行条件，但由于无无无无CPUCPU暂时不能运行的状态（当调暂时不能运行的状态（当调暂时不能运行的状态（当调暂时不能运行的状态（当调度给其度给其度给其度给其CPUCPU时，立即可以运行）时，立即可以运行）时，立即可以运行）时，立即可以运行）3)阻塞状态阻塞状态 又叫等待态、封锁态、睡眠态指进程又叫等待态、封锁态、睡眠态指进程又叫等待态、封锁态、睡眠态指进程又叫等待态、封锁态、睡眠态指进程因等待某种事件的发生而暂时不能运因等待某种事件的发生而暂时不能运因等待某种事件的发生而暂时不能运因等待某种事件的发生而暂时不能运行的状态（即使行的状态（即使行的状态（即使行的状态（即使CPUCPU空闲，该进程空闲，该进程空闲，该进程空闲，该进程也不可运行）也不可运行）也不可运行）也不可运行）图 2-5 进程的三种基本状态及其转换 第二章 进 程 管 理 Heb Nomal University Department of Computer Science5增加增加:创建状态，终止状态创建状态，终止状态三种进程状态三种进程状态-五状态进程模型五状态进程模型创建创建(新新new)new)状态状态OS OS 已完成为创建一进程所必要的工作已完成为创建一进程所必要的工作已构造了进程标识符已构造了进程标识符已创建了管理进程所需的表格已创建了管理进程所需的表格但还没有允许执行该进程但还没有允许执行该进程 (尚未同意尚未同意)因为资源有限因为资源有限终止（退出终止（退出exit)exit)状态状态中止后进程移入该状态中止后进程移入该状态它不再有执行资格它不再有执行资格表格和其它信息暂时由辅助程序保留表格和其它信息暂时由辅助程序保留一旦其他进程完成了对终止态进程的信息一旦其他进程完成了对终止态进程的信息抽取之后，系统将删除该进程。抽取之后，系统将删除该进程。第二章 进 程 管 理 Heb Nomal University Department of Computer Science62)进程状态的转换进程状态的转换(1)活动就绪活动就绪静止就绪。静止就绪。(2)活动阻塞活动阻塞静止阻塞。静止阻塞。(3)静止就绪静止就绪活动就绪。活动就绪。(4)静止阻塞静止阻塞活动阻塞。活动阻塞。图 2-6 具有挂起状态的进程状态图 执行执行静止就绪。静止就绪。挂起挂起 激活激活 就绪状态就绪状态(Ready)：进程在内存且可立即进入运行状态：进程在内存且可立即进入运行状态阻塞状态阻塞状态(Blocked)：进程在内存并等待某事件的出现：进程在内存并等待某事件的出现静止阻塞静止阻塞/阻塞挂起状态（阻塞挂起状态（Blocked,suspend）：进程在外）：进程在外存并等待某事件的出现存并等待某事件的出现静止就绪静止就绪/就绪挂起状态（就绪挂起状态（Ready,suspend）：进程在外存，）：进程在外存，但只要进入内存，即可运行但只要进入内存，即可运行第二章 进 程 管 理 Heb Nomal University Department of Computer Science7进程程序进程程序进程数据进程数据栈栈用于过程调用和参数传递用于过程调用和参数传递进程控制块进程控制块PCB(PCB(进程属性进程属性)处于核心段处于核心段用户进程不能直接访问、修改自己的用户进程不能直接访问、修改自己的PCB*进程要素进程要素第二章 进 程 管 理 Heb Nomal University Department of Computer Science8PCBPCB的内容的内容进程描述信息进程描述信息进程描述信息进程描述信息进程控制信息进程控制信息进程控制信息进程控制信息CPUCPU现场现场现场现场保护保护保护保护信息信息信息信息注意：不同操作系统中对进程的控制和管理机制不一样，注意：不同操作系统中对进程的控制和管理机制不一样，PCBPCB中的信息多少也不一样中的信息多少也不一样第二章 进 程 管 理 Heb Nomal University Department of Computer Science9第二章第二章 进程管理进程管理 2.1 2.1 进程的基本概念进程的基本概念 2.2 2.2 进程控制进程控制 2.3 2.3 进程同步进程同步 2.4 2.4 经典进程的同步问题经典进程的同步问题 2.5 2.5 管程机制管程机制 2.6 2.6 进程通信进程通信 2.7 2.7 线程线程 第二章 进 程 管 理 Heb Nomal University Department of Computer Science102.2 进进 程程 控控 制制 2.2.1 进程的创建进程的创建 1.进程图(Process Graph)图 2-9 进程树 u处理器管理的一个主要工作是对进程的控制，处理器管理的一个主要工作是对进程的控制，u包括：创建进程、阻塞进程、唤醒进程、挂起进程、激活进程、包括：创建进程、阻塞进程、唤醒进程、挂起进程、激活进程、终止进程和撤销进程等终止进程和撤销进程等第二章 进 程 管 理 Heb Nomal University Department of Computer Science112.引起创建进程的事件引起创建进程的事件(1)用户登录。用户登录。(2)作业调度。作业调度。(3)提供服务。提供服务。(4)应用请求。应用请求。在终端上交互式的登录。在终端上交互式的登录。在终端上交互式的登录。在终端上交互式的登录。系统为用户创建一个进程，并插入就绪队列 提交一个批处理作业。提交一个批处理作业。提交一个批处理作业。提交一个批处理作业。操作系统为用户请求创建一个服务进程。操作系统为用户请求创建一个服务进程。操作系统为用户请求创建一个服务进程。操作系统为用户请求创建一个服务进程。存在的进程孵化（存在的进程孵化（存在的进程孵化（存在的进程孵化（spawnspawn）新的进程。用户进程自己）新的进程。用户进程自己）新的进程。用户进程自己）新的进程。用户进程自己创建进程创建进程创建进程创建进程第二章 进 程 管 理 Heb Nomal University Department of Computer Science123.进程的创建进程的创建(Creation of Progress)(1)申请空白申请空白PCB。(2)为新进程分配资源。为新进程分配资源。(3)初始化进程控制块。初始化进程控制块。(4)将新进程插入就绪队列，或直接投入运行。将新进程插入就绪队列，或直接投入运行。第二章 进 程 管 理 Heb Nomal University Department of Computer Science132.2.2 进程的终止进程的终止 1.引起进程终止引起进程终止(Termination of Process)的事件的事件 1)正常结束 在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。例例如如，在在批批处处理理系系统统中中，通通常常在在程程序序的的最最后后安安排排一一条条Holt指指令令或或终终止止的的系系统统调调用用。当当程程序序运运行行到到Holt指指令令时时，将将产产生生一一个个中中断断，去去通通知知OS本本进进程程已已经经完完成成。在在分分时时系系统统中中，用用户户可可利利用用Logs off去去表表示示进进程程运运行行完完毕毕，此此时时同同样样可可产生一个中断，去通知产生一个中断，去通知OS进程已运行完毕。进程已运行完毕。第二章 进 程 管 理 Heb Nomal University Department of Computer Science14 2)异常结束异常结束 在在进进程程运运行行期期间间，由由于于出出现现某某些些错错误误和和故故障障而而迫迫使使进进程程终止。这类异常事件很多，常见的有：终止。这类异常事件很多，常见的有：越界错误。越界错误。这是指程序所访问的存储区，已越出该进程的区域；这是指程序所访问的存储区，已越出该进程的区域；保保护护错错。进进程程试试图图去去访访问问一一个个不不允允许许访访问问的的资资源源或或文文件件，或或者者以以不不适当的方式进行访问，例如，进程试图去写一个只读文件；适当的方式进行访问，例如，进程试图去写一个只读文件；非非法法指指令令。程程序序试试图图去去执执行行一一条条不不存存在在的的指指令令。出出现现该该错错误误的的原原因因，可能是程序错误地转移到数据区，把数据当成了指令；可能是程序错误地转移到数据区，把数据当成了指令；特权指令错。特权指令错。用户进程试图去执行一条只允许用户进程试图去执行一条只允许OS执行的指令；执行的指令；运行超时。运行超时。进程的执行时间超过了指定的最大值；进程的执行时间超过了指定的最大值；等待超时。等待超时。进程等待某事件的时间，进程等待某事件的时间，超过了规定的最大值；超过了规定的最大值；算术运算错。算术运算错。进程试图去执行一个被禁止的运算，例如，被进程试图去执行一个被禁止的运算，例如，被0除；除；I/O故障。故障。这是指在这是指在I/O过程中发生了错误等。过程中发生了错误等。第二章 进 程 管 理 Heb Nomal University Department of Computer Science15 3)外界干预外界干预 外界干预并非指在本本进进程程运运行行中中出出现现了了异异常常事事件件，而是指进程应外界的请求而终止运行。而是指进程应外界的请求而终止运行。这些干预有：操操作作员员或或操操作作系系统统干干预预。由由于于某某种种原原因因，例例如如，发发生生了了死死锁锁，由操作员或操作系统终止该进程；由操作员或操作系统终止该进程；父父进进程程请请求求。由由于于父父进进程程具具有有终终止止自自己己的的任任何何子子孙孙进进程程的的权权利利，因而当父进程提出请求时，系统将终止该进程；因而当父进程提出请求时，系统将终止该进程；父父进进程程终终止止。当当父父进进程程终终止止时时，OS也也将将他他的的所所有有子子孙孙进进程程终终止。止。第二章 进 程 管 理 Heb Nomal University Department of Computer Science16 2.进程的终止过程进程的终止过程 (1)根据被终止进程的标识符，从PCB集合中找出该进程的PCB，从中读出该进程的状态。(2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。(3)若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。(4)将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。(5)将被终止进程(它的PCB)从所在队列(或链表)中移出，将它的将它的PCBPCB归还到归还到PCBPCB池池。第二章 进 程 管 理 Heb Nomal University Department of Computer Science172.2.3 进程的阻塞与唤醒进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 1)请求系统服务 2)启动某种操作 3)新数据尚未到达 4)无新工作可做 第二章 进 程 管 理 Heb Nomal University Department of Computer Science18 2.进程阻塞过程进程阻塞过程 正正在在执执行行的的进进程程，当当发发现现上上述述某某事事件件时时，由由于于无无法法继继续续执执行行，于于是是进进程程便便通通过过调调用用阻阻塞塞原原语语block把把自自己己阻阻塞塞。可可见见，进程的阻塞是进程自身的一种主动行为。进程的阻塞是进程自身的一种主动行为。进进入入block过过程程后后，由由于于此此时时该该进进程程还还处处于于执执行行状状态态，所所以以应应立立即即停停止止执执行行，保保保保存存存存现现现现场场场场信信信信息息息息到到到到PSWPSW；把把进进程程控控制制块块中中的的现现行行状状态态由由“执执行行”改改为为阻阻塞塞，将将PCB插插入入阻阻塞塞队队列列。如如果果系系统统中中设设置置了了因因不不同同事事件件而而阻阻塞塞的的多多个个阻阻塞塞队队列列，则则应应将将本本进进程插入到具有相同事件的阻塞程插入到具有相同事件的阻塞(等待等待)队列。队列。最最后后，转转调调度度程程序序进进行行重重新新调调度度，将将处处理理机机分分配配给给另另一一就就绪绪进进程程，并并进进行行切切换换，亦亦即即，保保留留被被阻阻塞塞进进程程的的处处理理机机状状态态(在在PCB中中)，再再按按新新进进程程的的PCB中中的的处处理理机机状状态态设设置置CPU的的环境。环境。第二章 进 程 管 理 Heb Nomal University Department of Computer Science19 3.进程唤醒过程进程唤醒过程 当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤唤醒醒原原语语wakeup()，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。第二章 进 程 管 理 Heb Nomal University Department of Computer Science202.2.4 进程的挂起与激活进程的挂起与激活 1.进程的挂起进程的挂起 当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起，系统将利用挂挂起起原原语语suspend()将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。第二章 进 程 管 理 Heb Nomal University Department of Computer Science21 2.进程的激活过程进程的激活过程 当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语激活原语active()将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假假如如采采用用的的是是抢抢占占调调度度策策略略，则则每每当当有有新新进进程程进进入入就就绪绪队队列列时时，应应检检查查是是否否要要进进行行重重新新调调度度，即即由由调调度度程程序序将将被被激激活活进进程程与与当当前前进进程程进进行行优优先先级级的的比比较较，如如果果被被激激活活进进程程的的优优先先级级更更低低，就就不不必必重重新新调调度度；否否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。挂起原语既可由进程自己也可由其他进程调用，挂起原语既可由进程自己也可由其他进程调用，挂起原语既可由进程自己也可由其他进程调用，挂起原语既可由进程自己也可由其他进程调用，但激活原语却只能由其他进程调用但激活原语却只能由其他进程调用但激活原语却只能由其他进程调用但激活原语却只能由其他进程调用第二章 进 程 管 理 Heb Nomal University Department of Computer Science222.3 进进 程程 同同 步步 2.3.1 进程同步的基本概念进程同步的基本概念 1.两种形式的制约关系两种形式的制约关系(1)间接相互制约关系。(2)直接相互制约关系。第二章 进 程 管 理 Heb Nomal University Department of Computer Science232.临界资源临界资源(Critical Resouce)生生产产者者-消消费费者者(producer-consumer)问问题题是一个著名的进程同步问题。它描述的是：有有一一群群生生产产者者进进程程在在生生产产产产品品，并将这些产品提供给消费者进程去消费。并将这些产品提供给消费者进程去消费。为为使使生生产产者者进进程程与与消消费费者者进进程程能能并并发发执执行行，在在两两者者之之间间设设置置了了一一个个具具有有n个个缓缓冲冲区区的的缓缓冲冲池池，生生产产者者进进程程将将它它所所生生产产的的产产品品放放入入一一个个缓缓冲冲区区中中；消消费费者者进进程程可可从从一一个个缓缓冲冲区区中中取取走走产产品品去去消消费费。尽尽管管所所有有的的生生产产者者进进程程和和消消费费者者进进程程都都是是以以异异步步方方式式运运行行的的，但但它它们们之之间间必必须须保保持持同同步步，即即不不允允许许消消费费者者进进程程到到一一个个空空缓缓冲冲区区去去取取产产品品；也也不不允允许许生生产产者者进进程程向向一一个个已已装装满满产产品品且且尚尚未未被被取取走走的的缓缓冲冲区中投放产品。区中投放产品。第二章 进 程 管 理 Heb Nomal University Department of Computer Science24Var 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。我们可利用一个数数组组来表示上述的具有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时时表表示示缓缓冲冲池池满满；而而in=out则则表表示示缓缓冲冲池空。池空。此外，还引入了一个整整型型变变量量counter,其初始值为0。每当生产者进程向缓冲池中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时，使counter减1。生产者和消费者两进程共享下面的变量：第二章 进 程 管 理 Heb Nomal University Department of Computer Science25producer:repeat produce an item in 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 =bufferout;out =(out+1)mod n;counter =counter-1;consumer the item in nextc;until false;指针指针in和和out初始化为初始化为1。在生产者和消费者进程的描述中，在生产者和消费者进程的描述中，no-op是一条空操作指令，是一条空操作指令，while condition do no-op语句表示重复的测语句表示重复的测试条件试条件(condication)，重复测试应进，重复测试应进行到该条件变为行到该条件变为false(假假)，即到该条，即到该条件不成立时为止件不成立时为止在生产者进程中使用一局部变在生产者进程中使用一局部变量量nextp，用于暂时存放每次刚，用于暂时存放每次刚生产出来的产品；而在消费者生产出来的产品；而在消费者进程中，则使用一个局部变量进程中，则使用一个局部变量nextc,用于存放每次要消费的用于存放每次要消费的产品产品第二章 进 程 管 理 Heb Nomal University Department of Computer Science26 虽虽然然上上面面的的生生产产者者程程序序和和消消费费者者程程序序，在在分分别别看看时时都都是是正正确确的的，而而且且两两者者在在顺顺序序执执行行时时其其结结果果也也会会是是正正确确的的，但但若若并并发发执执行行时时，就就会会出出现现差差错错，问问题题就就在在于于这这两两个个进进程程共共享享变变量量counter。生生产产者者对对它它做做加加1操操作作，消消费费者者对对它它做做减减1操操作作，这这两两个个操操作作在在用用机机器器语语言言实实现现时时，常常可可用用下下面面的形式描述：的形式描述：register 1=counter;register1 =register 1+1;counter =register 1;register 2 =counter;register 2 =register 2-1;counter =register 2;Memory5counterregister 1register 25665 65第二章 进 程 管 理 Heb Nomal University Department of Computer Science27 假假设设：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)Memory5counterregister 1register 255646 4第二章 进 程 管 理 Heb Nomal University Department of Computer Science283.临界区临界区(critical section)可把一个访问临界资源的循环进程描述如下：repeat critical section;remainder section;until false;entry sectionexit section第二章 进 程 管 理 Heb Nomal University Department of Computer Science294.同步机制应遵循的规则同步机制应遵循的规则(1)空闲让进。空闲让进。(2)忙则等待。忙则等待。(3)有限等待。有限等待。(4)让权等待。让权等待。第二章 进 程 管 理 Heb Nomal University Department of Computer Science302.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;第二章 进 程 管 理 Heb Nomal University Department of Computer Science31 2.记录型信号量记录型信号量 在整型信号量机制中的wait操作，只要是信号量S0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代代表表资资源源数数目目的的整整型型变变量量value外，还应增增加加一一个个进进程程链链表表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记记录录型型的的数数据据结结构构而得名的。它所包含的上述两个数据项可描述为：第二章 进 程 管 理 Heb Nomal University Department of Computer Science32type semaphore=record value:integer;L:list of process;end相应地，相应地，wait(S)和和signal(S)操作可描述为：操作可描述为：procedure 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);end 第二章 进 程 管 理 Heb Nomal University Department of Computer Science33 在记录型信号量机制中，S.value的的初初值值表表示示系系统统中中某某类类资资源源的的数数目目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.value =S.value-1；当当S.value0时时，表表示示该该类类资资源源已已分分配配完完毕毕，因因此此进进程程应应调调用用block原原语语，进进行行自自我我阻阻塞塞，放放弃弃处处理理机机，并并插插入到信号量链表入到信号量链表S.L中中。可可见见，该该机机制制遵遵循循了了“让让权权等等待待”准准则则。此此时时S.value的的绝绝对对值值表表示示在在该该信信号号量量链链表表中中已已阻阻塞塞进进程程的的数数目目。对对信信号号量量的的每每次次signal操操作作，表表示示执执行行进进程程释释放放一一个个单单位位资资源源，故故S.value =S.value+1操操作作表表示示资资源源数数目目加加1。若若加加1后后仍仍是是S.value0，则则表表示示在在该该信信号号量量链链表表中中，仍仍有有等等待待该该资资源源的的进进程程被被阻阻塞塞，故故还还应应调调用用wakeup原原语语，将将S.L链链表表中中的的第第一一个个等等待待进进程程唤唤醒醒。如如果果S.value的的初初值值为为1，表表示示只只允允许许一一个个进进程程访访问问临临界界资资源源，此此时的信号量转化为互斥信号量。时的信号量转化为互斥信号量。第二章 进 程 管 理 Heb Nomal University Department of Computer Science343.AND型信号量型信号量 在两个进程中都要包含两个对Dmutex和Emutex的操作，即process 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阻塞 第二章 进 程 管 理 Heb Nomal University Department of Computer Science35 AND同同步步机机制制的的基基本本思思想想是是：将将进进程程在在整整个个运运行行过过程程中中需需要要的的所所有有资资源源，一一次次性性全全部部地地分分配配给给进进程程，待待进进程程使使用用完完后后再再一一起起释释放放。只只要要尚尚有有一一个个资资源源未未能能分分配配给给进进程程，其其它它所所有有可可能能为为之之分分配配的的资资源源，也也不不分分配配给给他他。亦亦即即，对对若若干干个个临临界界资资源源的的分分配配，采采取取原原子子操操作作方方式式：要要么么全全部部分分配到进程，要么一个也不分配配到进程，要么一个也不分配。由由死死锁锁理理论论可可知知，这这样样就就可可避避免免上上述述死死锁锁情情况况的的发发生生。为为此此，在在wait操操作作中中，增增加加了了一一个个“AND”条条件件，故故称称为为AND同同步步，或或称称为为同同时时wait操操作作，即即Swait(Simultaneous wait)定义如下：定义如下：第二章 进 程 管 理 Heb Nomal University Department of Computer Science36Swait(S1,S2,Sn)if Si1 and and Sn1 then for i=1 to n do Si=Si-1;endfor else place 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;第二章 进 程 管 理 Heb Nomal University Department of Computer Science374.信号量集信号量集 Swait(S1,t1,d1,Sn,tn,dn)if Sit1 and and Sntn then for i=1 to n do Si=Si-di;endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the beginning of the Swait Operation.endif signal(S1,d1,Sn,dn)for i=1 to n do Si =Si+di;Remove all the process waiting in the queue associated with Si into the ready queue endfor;第二章 进 程 管 理 Heb Nomal University Department of Computer Science38 一般一般“信号量集信号量集”的几种特殊情况：的几种特殊情况：(1)Swait(S,d,d)。此此时时在在信信号号量量集集中中只只有有一一个个信信号号量量S，但但允允许许它它每每次次申申请请d个个资资源源，当当现现有有资资源源数数少少于于d时时，不予分配。不予分配。(2)Swait(S,1,1)。此此时时的的信信号号量量集集已已蜕蜕化化为为一一般般的的记记录型信号量录型信号量(S1时时)或互斥信号量或互斥信号量(S=1时时)。(3)Swait(S,1,0)。这这是是一一种种很很特特殊殊且且很很有有用用的的信信号号量量操操作作。当当S1时时，允允许许多多个个进进程程进进入入某某特特定定区区；当当S变变为为0后后，将将阻阻止止任任何何进进程程进进入入特特定定区区。换换言言之之，它它相相当当于于一一个个可可控控开关。开关。第二章 进 程 管 理 Heb Nomal University Department of Computer Science392.3.3 信号量的应用信号量的应用 1.利用信号量实现进程互斥利用信号量实现进程互斥 利用信号量实现进程互斥的进程可描述如下：利用信号量实现进程互斥的进程可描述如下：Var mutex:semaphore =1;begin parbegin process 1:begin repeat wait(mutex);critical section signal(mutex);remainder seetion until false;end第二章 进 程 管 理 Heb Nomal University Department of Computer Science40 process 2:begin repeat wait(mutex);critical section s