并发程序开发技术-计算机软件技术基础教程.ppt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 并发 程序 开发 技术 计算机软件 基础教程
- 资源描述:
-
,第7章 并发程序开发技术,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,7.1 并发程序的引入,7.2 进 程 和 线 程,7.3 线程的状态与调度,7.4 基本同步机制,7.5 死 锁,第7章 并发程序开发技术,返回主目录,第7章 并发程序开发技术,7.1 并发程序的引入,7.1.1 程序的顺序执行,自从计算机问世以来,就产生了“计算机程序”这一概念。在多道程序设计出现以前,计算机运行程序的最大特征是“顺序性”。,一个程序通常可以分成若干个程序段,它们必须按照某种先后次序执行,仅当前一操作执行完成后,才能执行后继操作。对于一组程序来说,只有一个程序执行结束后,才能执行下一个程序。例如,在进行计算时,总是先输入用户的程序和数据,然后再进行计算,最后将结果输出。,这里,我们用结点代表各程序段的操作,其中I代表输入操作,C代表计算操作,P代表输出操作,并用箭头指示操作的先后次序。那么,上述各程序段的执行顺序可用图7.1来表示。,对于多个程序来说,执行完前一个程序后才能执行下一个程序。对于多条语句而言,只有前一条语句执行完后,才能继续执行后继语句。,程序的顺序执行具有如下特征:,图7.1 程序的顺序执行,1)顺序性。处理机的操作严格按照程序所规定的操作顺序执行,即每一操作必须在下一操作开始之前结束。一个程序的执行也必须在前一程序执行完成之后才能开始。,(2)独占性。一个程序一旦在机器上运行,它就独占机器的所有资源,直到该程序运行结束。,(3)封闭性。程序的运行结果只取决于程序本身,除了人为地改变机器状态或机器发生故障外,不受其他外界因素的影响。,(4)可再现性。程序重复执行时,只要输入保持不变,必将获得相同的结果。,7.1.2 程序的并发执行,我们知道,一个程序在运行时,并不需要占用所有资源。例如,在一个慢速的网络上读取一数据流也许需要一分钟,但需要CPU参与传输数据的时间却非常短。在此期间,CPU大部分都处于空闲状态,而运行一个计算量很大的程序则需占用大量的CPU时间,有时需要几分钟,甚至几小时,但输入、输出设备的使用时间却往往很少。因此,程序的顺序执行,通常会大幅度降低机器资源的利用率。,另外,对于某些应用,要求机器能同时处理多个任务,例如,现在有两个任务,一个是从网络上接收数据并在屏幕上显示出来;另一个则是从键盘读入数据,通过网络发送出去。若这两个任务分别用两个程序来实现,并采用顺序执行方式,则无论先执行哪一个程序,都会产生问题。,如图7.2所示,若先执行数据接收程序,则数据发送程序要一直等待数据接收程序结束,才能运行;反之亦然。,为了增强计算机系统的处理能力和提高各种资源的利用率,现代计算机系统中普遍采用了多道程序设计技术,其主要特征体现在以下方面:,1并发性,这时的程序不再以单纯的串行方式顺序执行。换句话说,在任一时刻,系统中不再只有一个计算,而是存在着许多并行的计算。从硬件方面看,处理机、各种外设、存储部件常常并行地进行工作;从程序活动方面看,则可能有若干个程序同时地或者相互穿插地在机器上运行。这就是说,有很多程序段是可以并发(concurrent)执行的。,图7.2 两个程序执行时相互等待示意图,所谓并发执行,是指两个以上程序的执行过程在时间上是重叠的,即使这种重叠只有很小的一部分,我们也称这两个程序是并发执行的。程序的并发执行已成为现代操作系统的一个基本特征。,在如图7.1所示的例子中,对于任何一个作业i,其输入操作Ii、计算操作Ci、打印操作Pi三者必须顺序执行,但对n个作业来说,则有可能并发执行。例如,输入程序输入完第一个作业程序后,在对该作业进行计算的同时,再启动输入程序,输入第二个作业程序,这就使得第二个作业的输入和第一个作业的计算能并发执行。图7.3给出了输入、计算、打印程序对一批作业进行处理的执行顺序,从该图可以看出某些操作之间是重叠的。,图7.3 程序段的并发执行,对于图7.2的例子,图7.4给出了数据接收程序和数据发送程序交替运行的示意图。,2共享性,机器上的硬件资源和软件资源已不再为单个用户程序所独占,而是由多个用户程序共同使用。,3独立性,并发执行的每一个程序都具有一定的独立性,它们分别实现一种用户所需要的功能。例如,数据接收和数据发送,它们之间相互独立。又如,操作系统中对处理机的调度和对各种外部设备的控制活动,两者之间基本上也是独立的,各自提供一种系统功能。这就是说,系统中各个并发程序活动具有独立性的一面。,4相互制约性,虽然系统中的各个并发活动具有一定的独立性,但在两个并发程序活动之间也会以直接或间接方式发生相互依赖和相互制约的关系。直接制约关系通常是在彼此之间有逻辑关系的两个并发执行的程序之间发生的。例如,一个正在执行的程序段需要另一程序段的结果,只有当另一程序段送来结果时,正在执行的程序段才能继续执行下去,否则它就一直等待,无法继续执行。两个程序段以间接方式发生制约关系通常是由竞争使用同一资源引起的。得到资源的程序段可以继续执行,得不到资源的程序段就只能等待,直到有资源可以使用。,由于程序活动之间的制约关系,各个程序活动之间的工作状态就与它所处的环境有密切关系。它随着外界的变化而不停地变化,并且它不像单道系统中连续顺序执行那样,而是走走停停,具有执行暂停执行的活动规律。,7.2 进程和线程,7.2.1 进程,程序的并发执行虽然卓有成效地增加了系统的处理能力并提高了系统资源的利用率,但它产生了一些新问题,也就是产生了与顺序程序不同的新特性,即破坏了顺序程序所具有的特征:顺序性、封闭性和可再现性,使得程序和程序的执行不再一一对应,而各个程序的运行可能会相互影响,相互制约。因而,程序这个静态概念已不能如实反映程序的活动,于是便产生了“进程”(Process)这一概念。,进程是操作系统中的一个重要概念,它与程序的区别在于,程序是一个静态指令序列,而进程是一个程序在给定的条件下对一组数据的一次动态执行过程。操作系统为每个进程分配一部分计算机资源,并确保每个进程的程序按一定的策略被调度执行。,概括地讲,进程具有以下基本特征:,(1)动态性。进程的实质就是程序的一次执行过程,它由“创建”而产生,由“调度”而执行,因得不到资源而暂停,最后由“撤消”而消失。,(2)并发性。没有为之建立进程的程序是不能并发执行的,仅当为之建立一个进程后才能参与并发执行。引入进程的目的正是为了使其程序能和其他程序并发执行。,(3)独立性。进程是一个能独立运行的基本单位,同时也是系统资源调度的独立单位。,(4)异步性。由于进程间的相互制约,使进程具有执行的间断性,即进程按各自独立的、不可预知的速度向前推进。为此,系统必须提供某些设施,来保证程序之间能协调操作和共享资源。,(5)结构性。为了描述进程的动态变化过程,并使之能独立运行,应为每个进程设置一个进程控制块(PCB)。从结构上看,每个进程都是由程序段、数据段、堆栈和一个PCB等四部分组成的。,随着UNIX、Windows NT、Windows 95等支持多任务的操作系统的广泛应用,进程的概念对大多数程序员而言已不再陌生。这一概念的引入实现了并行性和资源共享。在这些系统中,可以同时执行多个程序,每个执行的程序就可以称为一个进程,进程还可以再执行自己或其他的进程,称为派生进程,派生进程同父进程基本上是毫不相干的。,将一个复杂的任务分解成多个进程,能有效简化问题难度,但进程过多会产生以下问题:,(1)进程之间的交换非常复杂;,(2)进程与进程之间的切换涉及到多种资源,管理开销大,耗时长;,(3)每个进程甚至是相同的进程,都要占用资源,造成包括内存在内的资源的浪费;,(4)进程不利于数据和代码的共享,而数据和代码的共享能大大简化编程。,例如在UNIX系统中,当一个进程创建(或派生)另一个进程时,系统必须将第一个进程地址空间内的所有内容拷贝到新进程的地址空间中。对于一个大地址空间,这种操作是很费时的。更何况两个进程之间还必须建立一种共享数据的方式。,为了降低系统开销,线程(thread)的概念也就应运而生。,wrt.,2 产生死锁的必要条件,线程过多,会消耗大量的CPU时间跟踪线程;,在一个具体的操作系统实现中,操作系统通过硬件时钟中断来将一个虚拟CPU映射到物理CPU上。,this.,如果真的出现这种情况,那么最好还是少用几个线程,其实并不是说线程越多,程序执行就越快。,而在没有读者的情况下,在某一个时刻,只能够有一个作者线程执行。,rerturn next;,其含义是:当一个线程正在执行一个对象上的一个synchronized方法时,其他线程调用这个对象的任何一个synchronized方法将被阻塞。,(3)封闭性。,作者必须互斥地访问共享对象。,线程(thread)有很多定义。,void read(),当然,具有较低优先级的线程无论如何也是要运行的,只是机会少点而已。,value=value+1;,而线程在这一点上也十分相似,在它的生命期内,也总是处于某状态之中。,但是,现代的操作系统(例如,Windows 95/NT,OS/2,Solaris)都支持多线程。,7.2.2 线程,线程和进程是既相似又有区别的两个概念。其相似之处是它们均为实现并行(或并发)操作的基本调度单位,其区别则在于前者的粒度通常比后者小,一个进程可包含若干个线程,且同一进程的多个线程之间,共享数据空间,它们之间的切换仅仅是执行代码的切换。这样在使用线程的场合,大量地用于切换数据空间以及完成数据交换的系统资源被节省下来,从而提高了整个计算机系统的性能。也正是因为如此,通常也将线程称为轻量级进程(light-weight process)。,线程(thread)有很多定义。一个比较常用的定义是:线程是程序中的一个控制的执行流程。在特定的一个时刻,控制流处于程序中的某一点上,这个点被称为执行点。这个点随时间变动,形成一个流程,这个流程所经过的语句被执行。所以,控制流也被称为控制线索或线程(Thread of Control)。,每个线程使用一个CPU,所以,对于单CPU的计算机,只能有一个线程。但是,现代的操作系统(例如,Windows 95/NT,OS/2,Solaris)都支持多线程。操作系统通过虚拟机抽象,使系统表现出有多个虚拟CPU,每个线程拥有一个虚拟CPU。在一个具体的操作系统实现中,操作系统通过硬件时钟中断来将一个虚拟CPU映射到物理CPU上。如果物理CPU的个数比虚拟CPU的个数多,则每个线程在一个物理CPU上运行;如果物理CPU的个数比虚拟CPU的个数少,那么,在特定的一个时刻,只有部分线程在运行,其他线程处于等待状态。为使系统表现得像多CPU机器,操作系统通过硬件时钟中断和调度机制使每个线程轮流在物理CPU上运行一段很短的时间(例如20 ms)。虽然多个线程并不是都在真正同时运行,但由于线程等待使用物理CPU的时间很短,计算机用户不会感觉到某个线程正在等待,所以,从用户角度来说,这些线程在并发地执行。,线程有以下几个特点:,(1)线程共享父线程的所有资源;,(2)线程一般通过系统调度或者同步变量传递消息;,(3)线程切换基本只涉及寄存器和线程局部变量,开销很小;,(4)线程要仔细处理同步问题,防止死锁。,由此可见,线程具有并行执行的特点,但比进程的开销要小。多线程编程也比多进程编程相对简单一些,因为程序中的线程行为就像函数,可以通过全局变量交换信息,也可以共享文件内存等资源,与常规编程方法类似。,7.2.3 使用多线程的原因,使用多线程的主要原因是通过线程的并发执行来加快程序运行,提高CPU的利用率。因为在实际应用中,程序常常会遇到这样的情况:两段代码并没有相互制约的关系,但是因为程序是顺序执行的,而不得不一先一后地执行。如果先执行的代码又是那种无法利用CPU时间的程序,例如等待用户输入的程序,那么就会降低CPU的使用效率。而利用多线程就可以有效地解决程序并发执行的问题。我们把程序中没有顺序关系的代码段抽取出来,用线程实现它们,系统就会根据它们的优先级合理地为线程分配时间。当一个线程暂停时,系统会自动为其他线程分配时间,从而提高了CPU的使用效率。,7.2.4 并发程序设计的注意事项,没有任何事情是完美的,并发程序的设计也不例外。虽然使用多线程能加快程序的运行速度,提高系统的效率,但我们在使用多线程时应注意以下几点:,(1)由于多线程实际上是多个程序段同时存在并运行于内存中,所以一定要理清它们的关系,不要让它们把自己的头脑搅得像一团乱麻。如果真的出现这种情况,那么最好还是少用几个线程,其实并不是说线程越多,程序执行就越快。,(2)弄清线程优先级的设置和运行环境对不同优先级的线程的调度规则。,(3)正确处理多线程的同步控制。,(4)因为同一个任务的所有线程都共享相同的地址空间,并共享任务的全局变量,所以程序也必须在考虑全局变量的同时访问问题。,(5)对多线程程序本身来说,它对系统会产生以下影响:线程需要占用内存;线程过多,会消耗大量的CPU时间跟踪线程;程序必须考虑多线程对共享资源同时访问的问题。如果没有协调好,就会产生令人意想不到的问题,例如可怕的死锁和资源竞争等。,7.3 线程的状态与调度,7.3.1 线程的基本状态,我们知道,进程在生命期中,总是处于某种状态之中,诸如就绪态、运行态、阻塞态等。而线程在这一点上也十分相似,在它的生命期内,也总是处于某状态之中。每一种状态,都体现了线程在该状态时正在进行的活动以及在这段时间内所能完成的任务。,在许多情况下,程序中所存在的线程个数会远远大于物理CPU的个数。此时,一些线程由于不能立即得到物理CPU的使用权而处于等待状态,这些线程被放在一个就绪队列中,等待使用物理CPU。在就绪队列中的线程也被称为就绪线程。,就绪线程不能占有CPU而实际运行,它既不等待程序中的某个事件发生,也不等待其他被竞争的资源,所以,在高层的程序抽象中,我们仍将这些线程看做是处于运行状态。,当一个线程占有物理CPU的时间超过操作系统赋给它的时间时,或这个线程必须等待获得其他资源(例如,从文件输入的数据)之后才能继续执行时,操作系统则将这个线程从物理CPU上移下来。对于前者情况,操作系统将它们放到就绪队列中,对于后者,操作系统将它们放到等待队列中,然后,操作系统从就绪队列中选择另一个线程,使该线程获得CPU的使用权。这样周而复始,使所有线程都有机会占有CPU。在等待队列中的线程被称为阻塞线程。,对于等待队列中的线程,当线程运行所必需的条件具备之后(例如资源可用),这个线程又被操作系统移入到就绪队列中。,我们希望一些重要的线程能有更多的机会占有CPU,例如,与用户相互作用的线程由于等待用户的输入响应,被放在了等待队列中。当用户在用户界面进行了输入操作之后,我们希望这个线程能立即占用物理CPU而实际运行。为做到这点,程序中运行的线程被赋予了不同的优先级。高优先级的线程将优先被运行,所有处于这种优先级的线程都有机会获得一些时间段占用物理CPU。只有在高优先级的线程被阻塞之后,具有较低优先级的线程才被保证能够运行。当然,具有较低优先级的线程无论如何也是要运行的,只是机会少点而已。,当一个线程由于需要获得某种资源的使用权而被强制等待,或系统通过某种方法强制线程睡眠时,这个线程就被阻塞。当一个线程被阻塞之后,它被放到等待队列中,操作系统选择使就绪队列中的某一个就绪线程开始运行。,图7.5给出了线程可能具有的基本状态及状态变换的示意图。图中连线上的标注表示了影响状态变化的事件或消息等。图中只标注了与程序中的事件相关的状态变换,没有考虑线程等待物理CPU可用的情况。关于等待物理CPU可用这个方面是与操作系统有关的低级细节,在程序设计中,这个方面被优先级间接地控制着。所以,图中的运行态既包含线程正占用物理CPU而实际运行,也包含线程在就绪队列中等待使用物理CPU。,需要说明的是,不同的系统所提供的对多线程机制的支持,在其具体的实现上有所不同。,图7.5 线程的状态变化,7.3.2 线程的调度,在许多情况下,程序中所存在的线程个数会远远大于物理CPU的个数,那么,系统怎样知道应该运行哪一个线程呢?,目前,Java是通过线程调度器来监控进入就绪状态的所有线程,并按线程的优先级决定应调度哪些线程。具有高优先级的线程会在具有较低优先级的线程之前得到执行。同时,线程的调度是抢先式的,如果在当前线程的执行过程中,一个具有更高优先级的线程进入就绪状态,则这个高优先级的线程立即被调度执行。在抢先式的调度策略下,又分为时间片方式和非时间片方式(独占式)。在时间片方式下,当前活动线程执行完当前时间片后,如果有其他处于就绪状态的具有相同优先级的线程,系统会将执行权交给其他就绪态的同优先级线程,当前活动线程转入等待执行队列,等待下一个时间片的调度。,,一般情况下,这些线程将加入到等待队列的队尾。在独占方式下,当前活动线程一旦获得执行权,将一直执行下去,直到执行完毕或由于某种原因主动放弃CPU,或是有一高优先级的线程处于就绪状态。采用时间片机制的系统有Windows 95/NT、Unix等,而采用独占式的系统有DOS、Windows 3.1等。,在下面几种情况下,当前线程会放弃CPU:,(1)线程调用了yield()或sleep()方法。,(2)由于当前线程进行I/O访问、外存读写、等待用户输入等操作,导致线程阻塞。,(3)抢先式系统下,有高优先级的线程参与调度;时间片方式下,当前时间片用完,有同优先级的线程参与调度。,Java语言线程优先级的范围为整数110,缺省值为5,这可由类Thread的三个静态变量MIN_PRIORITY、MAX_PRIORITY、NORM_PRIORITY查出。,一个线程可以创建另一个线程。在线程被创建时,它的优先级与创建它的线程的优先级一样。Java中的Thread类中声明的下面两个方法可用于管理线程的优先级:,public final void setPriority(int newPriority);,public final int getPriority();,getPriority()方法获得一个线程的当前优先级。,SetPriority()方法将一个线程的优先级改变为参数所指定的级别。可以在任何需要的时候来改变一个线程的优先级,参数newPriority的值越大,线程的优先级也就越高。,每个线程归属于一个线程组,setPriority()将newPriority的值和这个线程所在的线程组的优先级进行比较,使用它们中的最小值来设置这个线程的优先级。这样,一个线程的优先级不会大于它所在的线程组的优先级。,如果所设置的新的优先级比线程当前所具有的优先级低,则由于这个线程可能不再具有最高的优先级,所以,这个线程可能会失去继续占用物理CPU运行的机会而被操作系统放到就绪队列中,而使就绪队列中另一个高优先级的线程有机会占用物理CPU而实际运行。,需要说明的是,一些线程虽然具有较高的优先级,但由于需要经常等待一些事件发生(例如,用户的响应,网络连接等),或等待对资源的拥有,反而比低优先级的线程有更少的运行时间。对于这样的线程,应考虑使用较高的优先级,而对于从事长时间计算的线程,可考虑使用较低的优先级。这样,一旦事件发生,等待这些事件的线程就会有机会立即运行,在处理完事件之后,又进入等待状态。,7.4 基本同步机制,7.4.1 同步和互斥,1线程间的同步,一般来说,一个线程相对于另一个线程的运行速度是不确定的。也就是说,线程之间是在异步环境下运行的,每个线程都以各自独立的、不可预知的速度向运行的终点推进。但是相互合作的几个线程需要在某些点上协调它们的工作。一个线程到达了这些点后,除非另一线程已完成了某些操作,否则就不得不停下来等待这些操作的结束,这就是线程间的同步。比如说,大型的数学矩阵运算常常分解成多个线程,每个线程完成的时间并不相同,而任务需要矩阵的所有结果,故矩阵运算的多个线程之间需要相互协调。,又如,一用户程序,其形式是:,Z=func1(x)*func2(y),其中func1(x),func2(y)均是一个复杂函数,为了加快本题的计算速度,可用两个线程P1,P2各计算一个函数。线程P1计算func1(x),计算完func1(x)之后,与线程P2的计算结果相乘,以获得最终结果Z。线程P1在计算完func1(x)之后,检测线程P2的结果是否已算完,如线程P2没有算完,则进入阻塞状态;若线程P2已经算完,则线程P1取用计算结果,然后进行乘法运算,最后得到Z。线程P2在计算出func2(y)后,应向线程P1发送消息,将线程P1唤醒。,2线程间的互斥,在各协同工作的线程之间存在着同步关系,但线程之间还存在着另一种关系,即互斥关系。这是由于线程在运行过程中因争夺资源而引起的。,系统中存在着许多线程,它们共享各种资源,然而有很多资源一次只能供一个线程使用。我们将一次仅允许一个线程使用的资源称为临界资源。很多物理设备都属于临界资源,如输入机、打印机等。除了物理设备以外,还有很多变量、数据、表格、队列等也都由若干线程所共享,通常它们也不允许两个线程同时使用,所以也属于临界资源,只能是一个线程用完了,另一线程才能使用,这种现象称为互斥,故临界资源也称为互斥资源。请看以下例子:,一个myArray对象有两个域需保持一致,一个是数组,一个是记录数据元素个数的计数器。,Class myArray extends Thread,int count=0;,int atom =new int 50;,void addatom(int i),atom count=i;,count+;,如果是单一线程,上面的例子没有错误,因为addatom()是顺序执行的。如果有两个线程,情况就不一样了。设想有两个线程thread1和thread2,它们执行的操作均为增加元素:,thread1.addatom(i);,thread2.addatom(i);,因为方法addatom()有两条语句,而线程随时切换,我们看看下面两种情况:,thread1.atomcount=i;,thread1.count+;,thread2.atomcount=i;,thread2.count+;,thread1.atomcount=i;,thread2.atomcount=i;,thread1.count+;,thread2.count+;,第一种情况没有问题。,第二种情况下,线程thread1赋值后计数器count还没有加1,线程thread2重新赋值,结果是atomcount 为线程thread2赋的值,atomcount+1值为空,而计数器指向了count+2,这与期望的情况根本不一致。,出现这种情况的根本原因在于两条语句atomcount=i与count+被分开执行,如果方法addatom()在运行时不被打断,就不会出现这种情况。,即为多个线程所共享的变量、数据等也应作为临界资源来处理。在一个线程中,共享临界资源的代码段被称为临界区。当一个线程在临界区内执行时,必须确保对一些特定的信息或共享资源的互斥访问。,由此可见,对系统中任何一个线程来说,其工作正确与否不 仅取决于它自身的正确性,而且与它在执行中能否与其他相关线程正确地实施同步或互斥有关,所以,解决线程间的同步和互斥是非常重要的问题。,3实现线程互斥的基本模型,保证互斥的一个基本模型是,一个线程在使用一个资源之前必须首先发出对这个资源的使用请求(也被称为加锁),而在使用完之后释放这个资源(被称为解锁)。这样,一个线程只能依据下列的顺序使用一个资源:,(1)请求。如果请求不能被立即满足(例如,这种资源正在被其他线程使用),那么,提出请求的线程必须等待,直到它的请求被满足为止。,(2)使用。线程可以对资源进行处理(例如,向文件中写数据)。,(3)释放。线程将它所请求得到的资源释放掉。,7.4.2 同步机制,支持多线程的操作系统提供信号灯这种原始机制来控制一个线程进入临界区,以达到对共享资源的互斥访问。信号灯只有两种状态,有信号和无信号,这相当于交叉路口的红绿灯,有信号对应于绿灯亮,无信号对应于红灯亮,没有黄灯这一状态。信号灯有两个基本操作,被称为P操作和V操作。P操作检查信号灯的状态,如果信号灯是有信号状态,则线程可以进入临界区;如果是无信号状态,则线程必须在临界区外等待,直到信号灯从无信号状态变为有信号状态时为止。这些等待的线程被称为处于阻塞状态。当有多个线程要进入临界区时,在信号灯前(或在临界区之外)要形成一个等待队列。V操作将信号灯变为有信号状态。某个线程通过执行V操作唤醒在信号灯前等待的线程,使这些线程继续执行。P操作和V操作被分别置于临界区的开始和结束处。,下面给出信号灯的一个示意性描述:,class Semaphore,private int value;,private Queue waitingQueue=new Queue();,Semaphore(),value=1;,void P(),value=value-1;,if(value0),将当前线程放入等待队列WaitingQueue中,当前线程进入等待状态。,void V(),value=value+1;,if(valuesize),wait();,catch(InterruptedException e),poolin=value;,in=(in+1)%size;,count=count+1;,notify();,public synchronized int consume(),try,while(countsize),wait();,它使生产者等待,直到数组中有空的位置时为止。,消费者的实现与生产者类似。,7.5 死 锁,7.5.1 死锁的概念,在一个多线程环境中,几个线程可能竞争有限个数的资源。一个线程请求一些资源,如果这些资源此时不能分配,则这个线程进入等待状态。这时,可能会出现这样的情况,各个线程都忙于抢占系统资源,但每个线程都不能满足所有的要求,因而所有的线程都停步不前。这种情况被称为死锁,死锁将对系统资源造成极大的浪费。,图7.6给出了死锁的示意说明。在图中,一个方框表示一个线程,一个圆圈表示一个对象。,图7.6 死锁,图7.6给出了死锁的示意说明。在图中,一个方框表示一个线程,一个圆圈表示一个对象。当箭头从一个对象指向一个线程时,表示这个对象已拥有了这个对象上的锁。当箭头从一个线程指向一个对象时,表示这个线程为获得这个对象的锁而等待。该图给出了某个时刻线程和对象之间的关系。我们可以看出,此时由于两个线程在互相等待对方释放对象上的锁,因此,这两个线程处于死锁状态。图7.6也表明,如果在某个时刻在线程和对象之间形成一个环路,则必会出现死锁。,死锁问题通过程序调试是很难查出来的。图7.6的情况可以这样产生:,(1)thread1调用了对象obj1的一个同步方法。这时,thread1拥有obj1上的锁。,(2)thread2调用了对象obj2的一个同步方法。这时,thread2拥有obj2上的锁。,(3)然后,thread1在obj1的同步方法中执行时,又调用了obj2的一个同步方法。,(4)同样,thread2在obj2的同步方法中执行时,又调用了obj1的一个同步方法。,对于上述的情况,如果在thread1开始执行上面的第(3)步时,thread2还没有执行到第(2)步,则就不会发生死锁问题。因此,常常出现这种情况,程序在调试时一切都正常,可是当交付使用后,说不定什么时间就出现了死锁。因为死锁与时间因素有关,所以,死锁有时很难被发现,改正程序的死锁错误也就无从下手。死锁只能通过对程序进行分析才能检查出来。,7.5.2 产生死锁的必要条件,一般来说,造成死锁的情况虽然比较复杂,但归纳起来死锁的产生有以下四种必要条件:,(1)互斥条件:至少一个资源被以非共享(互斥)的方式所拥有,即在一个时刻,只能有一个线程使用这个资源。如果另一个线程请求这个资源,正进行请求的线程必须等待,直到资源被释放。,(2)请求和保持条件:必须存在一个线程,这个线程至少拥有一个资源,同时正在请求获得当前正被另一个线程所拥有的其他资源。,(3)不剥夺条件:线程已获得的资源,在未使用完以前,不能被剥夺,只能在使用完后由自己释放。,(4)循环等待条件:必须存在一组正等待的线程p,0,p,1,p,2,p,n,,p,0,正等待p,1,所拥有的资源,p,1,正等待p,2,所拥有的资源,p,n-1,正等待p,n,所拥有的资源,p,n,正等待p,0,所拥有的资源。,如果程序中出现死锁现象,程序将不得不被终止。因此,应付死锁的可行办法是使用某些协议,以确保程序不会进入到死锁状态中。,7.5.3 死锁的预防,从上面所提到的关于死锁的必要条件可以看出,只要保证至少其中的某个条件不成立,就能够避免出现死锁现象。,互斥条件对非共享的资源必须保证,而对能够在多线程之间共享的资源则不需要互斥访问。但是,一般而言,否定互斥条件并不能阻止死锁的发生。,为保证请求和保持条件不成立,系统要求所有线程一次性地申请其所需的全部资源。若系统有足够的资源分配一线程时,便一次把其所需的资源分配给该线程。这样,该线程在整个运行期间,便不会再提出任何资源请求,从而使请求条件不成立。,但在分配时,只要有一种资源要求不能满足,则已有的其他资源也全部不分配给该线程,该线程只能等待。由于等待期间的线程不占有任何资源,因此,也就破坏了保持条件。这种方法简单,易于实现,且很安全,但缺点也极其明显,即资源严重浪费,线程延迟运行。,为使不剥夺条件不成立,可规定:一个已保持了某些资源的线程,若新的资源要求不能立即得到满足,它必须释放已保持的所有资源,以后需要时再重新申请。这种策略实现起来比较复杂,而且要付出很大代价。,为保证循环等待条件不成立,我们可以对所有的资源进行线性排序,每个线程只能以增序或降序的形式请求资源。,上面的方法虽然可以预防死锁,但总的来说,都施加了较强的限制条件,从而在不同程度上损害了系统的性能。,展开阅读全文

咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。
咨信网小贴示:
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】


并发程序开发技术-计算机软件技术基础教程.ppt
















自信AI助手![《小数的初步认识》PPT[精编文档].ppt](/Images/s.gif)














微信客服
客服QQ
发送邮件
意见反馈



链接地址:https://www.zixin.com.cn/doc/14505516.html