您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 咨询培训 > 软件设计师考试重点难点
软件设计师考试重点难点:死锁、流水线、关键路径、系统可靠性计算、多媒体、操作系统、数据库。软件设计师重点难点——死锁死锁(Deadlock)是指多个进程在运行的过程中因争夺资源而造成的一种僵局。当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。在软件设计师的考试当中,这个知识点的考查是以选择题的形式出现的,考点主要有:死锁的必要条件、解决死锁的方法,最难高难度会考到“银行家算法”。本文将介绍死锁的相关知识,但不会具体讲解“银行家算法”,该算法将在本系列的下一篇文章中详细说明。1、死锁发生的必要条件死锁的发生必须具备四个必要条件,这四个条件相互联系、缺一不可。(1)互斥条件:指进程对所分配到的资源进行排他性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其他进程请求该资源,则请求者只能等待,直至占有该资源的进程用完并释放。(2)请求和保持条件:指进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源又已被其他进程占有,此时请求进程阻塞,但又对自己已获得的其他资源保持不放。(3)不剥夺条件:指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。(4)环路等待条件:指在发生死锁时,必然存在一个进程--资源的环形链,即进程集合{P0,P1,P2…Pn}中的P0正在等待一个P1占用的资源,P1正在等待P2占用的资源,……Pn正在等待已被P0占用的资源。2、解决死锁的策略解决死锁的策略通常有三种:死锁预防、死锁避免以及死锁解除。前两种方法是“事前措施”,而死锁解除是“事后解决方案”。(1)死锁预防:“解铃还需系铃人”,随便破坏导致死锁这任意一个必要条件就可以预防死锁。例如,要求用户申请资源时一起申请所需要的全部资源,这就破坏了保持和等待条件;将资源分层,得到上一层资源后,才能够申请下一层资源,它破坏了环路等待条件。预防通常会降低系统的效率。(2)死锁避免:避免是指进程在每次申请资源时判断这些操作是否安全,典型算法是“银行家算法”(本系列文章的下一篇将详细讲解该问题)。但这种算法会增加系统的开销。(3)死锁解除:该方法的思路很简单,通过死锁检测判断系统是否处于死锁状态,若死锁,则由系统强制剥夺部分进程的资源,将资源强行分配给别的进程。3、判断系统是否可能进入死锁状态从上面的死锁解决方案来看,无论哪一种方式都不可避免的要增加系统的负担。而同时一个系统是否有可进入死锁状态受系统资源数量,需要使用该资源的进程数量等因素影响。若系统本不可能引起死锁,而我们采用了死锁解决方案,是很不合理的。所以,考试中常考到这样的题型:给出系统的资源数,以及需要使用该资源的进程数量等参数,让考生判断系统有无可能产生死锁。下面我们以例题的方式来说明如何解决这类问题。例题1:系统有3个进程:A、B、C。这3个进程都需要5个系统资源。如果系统有多少个资源,则不可能发生死锁。解答:在分析这个问题时,我们可以取一些简单的数据代入试题进行验证、分析,以得到相应的规律。如:(1)当系统资源数量为9时,若给A与B分别分配了4个资源,C分配了1个资源,则系统中的每个进程都存在资源不足的情况,而都不放手自己拥有的资源。不能正常运行完毕,发生死锁。(2)当系统资源数量为12时,若给A、B、C各分配4个资源,则死锁。(3)当系统资源数量为13时,无论如何分配,总有至少1个进程能得到5个资源,得到5个资源的进程可以正常运行完毕,而后将自己占用的资源分配给其它进程,所以这样能使所有进程运行完毕。从上面的尝试,我们可以总结出一个规律:先给所有进程分配他们所需要的资源数减1个资源,然后系统如果能再剩余1个资源,则系统不会发生死锁。这样解答本题变得非常容易。(5-1)*3+1=13。例题2:一台计算机有10台磁带机被m个进程竞争,每个进程最多需要三台磁带机,那么m至多为时,系统没有死锁的危险。A.3B.4C.5D.6解答首先从m=6开始考察,首先每个进程分配1台,剩下的4台只能分配给4个进程,还有2个进程没有分配,如果已经分配了2台的4个进程需要3台的话,则系统就会死锁。同样,如果m=5,也会发生这种情况。当m=4时,每个进程可以分得2台,还有2个进程可分得3台,则可正常运行,运行完毕后可释放资源,从而不会死锁。在解这道题时有些学员提出“如果按照答案m=4,则这4个进程都是需要3台磁带机的话,共需要12台磁带机,这样还不会死锁?”。这种想法是错误的,因为并不是同时把所有进程都分配给足够的资源才能完成这些进程,可以是一个进程先执行完,释放完资源再执行另一个进程。例如:4个进程中,每个进程分配2台磁带机,用去了8台。剩下2台,仍然可以满足两个进程,直到他们完成,释放他们暂用的磁带机。软件设计师重点难点——流水线流水线这个知识点在软件设计师考试中是个重点也是个难点,考查的频率比较高。之所以说流水线是个难点,有两方面的原因:一方面是需要理解流水线的理论,了解其工作原理,计算方式;另一方面是在软考当中,对于流水线的相关计算,标准并不是完全统一的,这一点在后面我们将详细介绍。流水线是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术。各种部件同时处理是针对不同指令而言的,它们可同时为多条指令的不同部分进行工作,以提高各部件的利用率和指令的平均执行速度。指令流水线是将指令执行分成几个子过程,每一个子过程对应一个工位,我们称为流水级或流水节拍,这个工位在计算机里就是可以重叠工作的功能部件,称为流水部件。如图1所示,IF,ID,EX,WD分别是流水线的流水部件。流水线要求所有的流水级部件必须在相同的时间内完成各自的子过程。在流水线中,指令流动一步便是一个机器周期,机器周期的长度必须由最慢的流水级部件处理子过程所需的时间来决定。那么我们为什么要提出流水线这个概念,以及流水线是如何提高系统吞吐量的呢?下面我们来看几个图,概念自然就清楚了。图2是一个非流水线结构系统执行指令时空图。我们从图2中可以看到,任意一个系统时间都有大量的设备处于空闲状态,如第一个时间段有ID,EX,WB空闲,则第二个时间段有IF,EX,WB空闲。我们再来看采用了流水线结构的时空图3。显然,采用流水线可以大大提升系统资源的利用率,以及整个系统的吞吐量。流水线的操作周期取决于基本操作中最慢的那个。例如:一个3段流水线,各段的执行时间分别为t,2t,t。则最慢的一段为2t,所以流水线操作周期为2t。流水线的执行时间公式为:第1条指令的执行时间+(指令条数-1)*流水线操作周期例题1若每一条指令都可以分解为取指、分析和执行三步。己知取指时间t取指=4△t,分析时间t分析=3△t,执行时间t执行=5△t。如果按串行方式执行完100条指令需要(1)△t。如果按照流水方式执行,执行完100条指令需要(2)△t。供选择的答案(1)A.1190B.1195C.1200D.1205(2)A.504B.507C.508D.510试题分析本题考查的是计算机系统指令流水线方面的基础知识。根据题意可以看到,在此流水线中按串行方式执行完100条指令要用1200△t。采用流水方式执行,执行的总时间的关键取决于最长的执行时间,所以执行完100条的时间为:4Δt+3Δt+5Δt+(100-1)*5Δt=507Δt。试题答案CB例题2现采用4级流水线结构分别完成一条指令的取指、指令译码和取数、运算,以及送回运算结果4个基本操作,每步操作时间依次为60ns,100ns,50ns和70ns。该流水线的操作周期应为Ans。若有一小段程序需要用20条基本指令完成(这些指令完全适合于流水线上执行),则得到第一条指令结果需Bns,完成该段程序需Cns。在流水线结构的计算机中,频繁执行D指令时会严重影响机器的效率。当有中断请求发生时,采用不精确断点法,则将E。供选择的答案A:①50②70③100④280B:①100②200③280④400C:①1400②2000③2300④2600D:①条件转移②无条件转移③算术运算④访问存储器E:①仅影响中断反应时间,不影响程序的正确执行②不仅影响中断反应时间,还影响程序的正确执行③不影响中断反应时间,但影响程序的正确执行④不影响中断反应时间,也不影响程序的正确执行试题分析本题主要考查对流水线技术的掌握。对于CPU来说,流水线技术实际上是一种以增加硬件换取性能的方式:把一条指令分解成多条更小的指令,由不同的处理单元来处理,在理想的满负荷运行状态下,执行一条指令的时间虽然没有减少,但是由于多个处理单元同时工作,在同一时间上可以执行不同指令的不同部分,从而使得总体的执行时间大大减少。流水线的操作周期取决于基本操作中最慢的那个。这里最慢的是100ns,所以操作周期是100ns。在流水线中,其实每一条指令的执行时间并没有减少,而第一条指令的执行并没有体现流水线的优势,它在4个操作周期后才能执行完成,这以后每个操作周期都能完成一条指令的执行。影响流水线效率的重要因素有条件转移指令和中断,因为它们打断了流水线,使得流水线不得不重新装载。不精确断点法实现简单,但是要等到流水线内的指令完成之后再响应中断。试题答案A.③B.④C.③D.①E.②希赛IT教育专家提示:上面的两个例题,都是软考当中出现过的真题。我们可以看出,两个题在计算流水线时间方面,标准并不是统一的。在例题1中:4Δt+3Δt+5Δt+(100-1)*5Δt=507Δt。而在例题2中:100ns+100ns+100ns+100ns+(20-1)*100ns=2300ns这两种计算方法,都是在套用公式:“第1条指令的执行时间+(指令条数-1)*流水线操作周期”,而对于“第1条指令的执行时间”的理解并不相同。在例题1中,第1条指令的执行时间是将指令执行时的几个阶段所需时间相加得到,而在例题2中,认为每一个阶段所需时间都是流水线的周期时间。其中前者是流水线的理论计算方法,而后者是我们在设计硬件流水线时,常用的方式。两种计算方法,从理论上来讲,都是正确的,但考试时,只有一个是正确答案。那么我们应该怎么做呢?由于每次考试中,无论认可的是哪种计算方式,都只会把这种计算方式的正确答案放入选项中,而不会将两个正确答案都放入,所以我们在用一种方式不能得到正确选项时,应采用另一种方式进行计算,来得到正确答案。软件设计师重点难点——关键路径关键路径这个知识点在软件设计师考试中,是一个难点。说到关键路径这个概念,大家应该多少有些印象,可能都知道它是“最长路径”而不是“最短路径”,但说到它为什么是最长路径,提出这个概念的用意何在,它有什么应用,在计算机中关键路径是如何求的等问题却没有几个人能真正搞清楚,甚至书上给出了完整的例子,都有很多人看不懂。下面我先会简单的说明基本概念,然后以一个例子,结合平时希赛教育学员的疑问,对这个知识点进行详细的分析。在AOV网络中,如果边上的权表示完成该活动所需的时间,则称这样的AOV为AOE网络。例如,图1表示一个具有10个活动的某个工程的AOE网络。图中有7个顶点,分别表示事件1~7,其中1表示工程开始状态,7表示工程结束状态,边上的权表示完成该活动所需的时间。下面我们来理解一下关键路径的思想,图1虽节点不多,但是为了让问题变得更为简单、直观,我们画另一个AOE网络,如图2所示。从图2中我们可以看出,关键路路径实际上是从源点到目的地的最长路径。为什么是最长路径呢?因为图中的某些事件是可以并发执行的。如图2所示,当到达V1后,可以同时往V2,V3,V4三个方向走,而V2,V3,V4都有到Vk的路径,且长度都为1,并且Vk是终点,则关键路径是V1-V2-Vk。因为这条路径最长,只要这条路径到目的地Vk时其他的都已经到达Vk。而在这条关键路径上的活动a2,a5称为关键活动。为了找出给定的AOE网络的关键活动,从而找出关键路径,先定义几个重要的量:Ve(j)、Vl(j):顶点j事件最早、最迟发生时间。e(i)、l(i):活动i最早、最迟开始时间。从源点V1到某顶点Vj的最长路径长度称为事件Vj的最早发生时间,记为Ve(j)。Ve(j)也是以
本文标题:软件设计师考试重点难点
链接地址:https://www.777doc.com/doc-5044107 .html