《2016年软件设计师教程重难点精讲(一)》由会员分享，可在线阅读，更多相关《2016年软件设计师教程重难点精讲(一)（8页珍藏版）》请在金锄头文库上搜索。
1、2016年软件设计师教程重难点精讲（一） 2016下半年软考软件设计师报名即将开始，下面是希赛软考学院整理的软件设计师教程重点难点精讲，希望对大家有所帮助。 死锁(Deadlock)是指多个进程在运行的过程中因争夺资源而造成的一种僵局。当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。在软件设计师的考试当中，这个知识点的考查是以选择题的形式出现的，考点主要有：死锁的必要条件、解决死锁的方法，最难高难度会考到“银行家算法”。本文将介绍死锁的相关知识，但不会具体讲解“银行家算法”，该算法将在本系列的下一篇文章中详细说明。 1、死锁发生的必要条件 死锁的发生必须具备四个必要条件，这四个
2、条件相互联系、缺一不可。 (1)互斥条件：指进程对所分配到的资源进行排他性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其他进程请求该资源，则请求者只能等待，直至占有该资源的进程用完并释放。 (2)请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放。 (3)不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。 (4)环路等待条件：指在发生死锁时，必然存在一个进程-资源的环形链，即进程集合P0，P1，P2Pn中的P0正在等待一个P1占用的资源，P1正在等
3、待P2占用的资源，Pn正在等待已被P0占用的资源。 2、判断系统是否可能进入死锁状态 从上面的死锁解决方案来看，无论哪一种方式都不可避免的要增加系统的负担。而同时一个系统是否有可进入死锁状态受系统资源数量，需要使用该资源的进程数量等因素影响。若系统本不可能引起死锁，而我们采用了死锁解决方案，是很不合理的。所以，考试中常考到这样的题型：给出系统的资源数，以及需要使用该资源的进程数量等参数，让考生判断系统有无可能产生死锁。下面我们以例题的方式来说明如何解决这类问题。 例题1： 系统有3个进程：A、B、C。这3个进程都需要5个系统资源。如果系统有多少个资源，则不可能发生死锁。 解答：在分析这个问题时
4、，我们可以取一些简单的数据代入试题进行验证、分析，以得到相应的规律。 如：(1)当系统资源数量为9时，若给A与B分别分配了4个资源，C分配了1个资源，则系统中的每个进程都存在资源不足的情况，而都不放手自己拥有的资源。不能正常运行完毕，发生死锁。 (2)当系统资源数量为12时，若给A、B、C各分配4个资源，则死锁。 (3)当系统资源数量为13时，无论如何分配，总有至少1个进程能得到5个资源，得到5个资源的进程可以正常运行完毕，而后将自己占用的资源分配给其它进程，所以这样能使所有进程运行完毕。 从上面的尝试，我们可以总结出一个规律：先给所有进程分配他们所需要的资源数减1个资源，然后系统如果能再剩余
5、1个资源，则系统不会发生死锁。这样解答本题变得非常容易。 (5-1)*3+1=13。 例题2： 一台计算机有10台磁带机被m个进程竞争，每个进程最多需要三台磁带机，那么m至多为时，系统没有死锁的危险。 A.3 B.4 C.5 D.6 解答：首先从m=6开始考察，首先每个进程分配1台，剩下的4台只能分配给4个进程，还有2个进程没有分配，如果已经分配了2台的4个进程需要3台的话，则系统就会死锁。同样，如果m=5，也会发生这种情况。当m=4时，每个进程可以分得2台，还有2个进程可分得3台，则可正常运行，运行完毕后可释放资源，从而不会死锁。在解这道题时有些学员提出“如果按照答案m=4，则这4个进程都是
6、需要3台磁带机的话，共需要12台磁带机，这样还不会死锁?”。这种想法是错误的，因为并不是同时把所有进程都分配给足够的资源才能完成这些进程，可以是一个进程先执行完，释放完资源再执行另一个进程。 例如：4个进程中，每个进程分配2台磁带机，用去了8台。剩下2台，仍然可以满足两个进程，直到他们完成，释放他们暂用的磁带机。 流水线 流水线这个知识点在软件设计师考试中是个重点也是个难点，考查的频率比较高。之所以说流水线是个难点，有两方面的原因：一方面是需要理解流水线的理论，了解其工作原理，计算方式;另一方面是在软考当中，对于流水线的相关计算，标准并不是完全统一的，这一点在后面我们将详细介绍。 流水线是指在
7、程序执行时多条指令重叠进行操作的一种准并行处理实现技术。各种部件同时处理是针对不同指令而言的，它们可同时为多条指令的不同部分进行工作，以提高各部件的利用率和指令的平均执行速度。 指令流水线是将指令执行分成几个子过程，每一个子过程对应一个工位，我们称为流水级或流水节拍，这个工位在计算机里就是可以重叠工作的功能部件，称为流水部件。 如图1所示，IF，ID，EX，WD分别是流水线的流水部件。 流水线要求所有的流水级部件必须在相同的时间内完成各自的子过程。在流水线中，指令流动一步便是一个机器周期，机器周期的长度必须由最慢的流水级部件处理子过程所需的时间来决定。 那么我们为什么要提出流水线这个概念，以及
8、流水线是如何提高系统吞吐量的呢?下面我们来看几个图，概念自然就清楚了。 图2是一个非流水线结构系统执行指令时空图。 我们从图2中可以看到，任意一个系统时间都有大量的设备处于空闲状态，如第一个时间段有ID，EX，WB空闲，则第二个时间段有IF，EX，WB空闲。 我们再来看采用了流水线结构的时空图3。 显然，采用流水线可以大大提升系统资源的利用率，以及整个系统的吞吐量。 流水线的操作周期取决于基本操作中最慢的那个。例如：一个3段流水线，各段的执行时间分别为t，2t，t。则最慢的一段为2t，所以流水线操作周期为2t。 流水线的执行时间公式为： 第1条指令的执行时间+(指令条数-1)*流水线操作周期
9、例题1 若每一条指令都可以分解为取指、分析和执行三步。己知取指时间t取指=4t，分析时间t分析=3t，执行时间t执行=5t。如果按串行方式执行完100条指令需要(1)t。如果按照流水方式执行，执行完100条指令需要(2)t。 供选择的答案 (1)A.1190 B.1195 C.1200 D.1205 (2)A.504 B.507 C.508 D.510 试题分析 本题考查的是计算机系统指令流水线方面的基础知识。根据题意可以看到，在此流水线中按串行方式执行完100条指令要用1200t。采用流水方式执行，执行的总时间的关键取决于最长的执行时间，所以执行完100条的时间为：4t+3t+5t+(100
10、-1)*5t=507t。 试题答案 C B 例题2 现采用4级流水线结构分别完成一条指令的取指、指令译码和取数、运算，以及送回运算结果4个基本操作，每步操作时间依次为60 ns，100 ns，50 ns和70 ns。该流水线的操作周期应为A ns。若有一小段程序需要用20条基本指令完成(这些指令完全适合于流水线上执行)，则得到第一条指令结果需B ns，完成该段程序需C ns。 在流水线结构的计算机中，频繁执行D指令时会严重影响机器的效率。当有中断请求发生时，采用不精确断点法，则将E。 供选择的答案 A：5070100280 B：100200280400 C：1400200023002600 D
11、：条件转移无条件转移算术运算访问存储器 E：仅影响中断反应时间，不影响程序的正确执行 不仅影响中断反应时间，还影响程序的正确执行 不影响中断反应时间，但影响程序的正确执行 不影响中断反应时间，也不影响程序的正确执行 试题分析 本题主要考查对流水线技术的掌握。 对于CPU来说，流水线技术实际上是一种以增加硬件换取性能的方式：把一条指令分解成多条更小的指令，由不同的处理单元来处理，在理想的满负荷运行状态下，执行一条指令的时间虽然没有减少，但是由于多个处理单元同时工作，在同一时间上可以执行不同指令的不同部分，从而使得总体的执行时间大大减少。流水线的操作周期取决于基本操作中最慢的那个。这里最慢的是10
12、0 ns，所以操作周期是100 ns。在流水线中，其实每一条指令的执行时间并没有减少，而第一条指令的执行并没有体现流水线的优势，它在4个操作周期后才能执行完成，这以后每个操作周期都能完成一条指令的执行。 影响流水线效率的重要因素有条件转移指令和中断，因为它们打断了流水线，使得流水线不得不重新装载。 不精确断点法实现简单，但是要等到流水线内的指令完成之后再响应中断。 试题答案 A.B.C.D.E. 上面的两个例题，都是软考当中出现过的真题。我们可以看出，两个题在计算流水线时间方面，标准并不是统一的。 在例题1中： 4t+3t+5t+(100-1)*5t=507t。 而在例题2中： 100ns+1
13、00ns+100ns+100ns+(20-1)*100ns=2300ns 这两种计算方法，都是在套用公式：“第1条指令的执行时间+(指令条数-1)*流水线操作周期”，而对于“第1条指令的执行时间”的理解并不相同。在例题1中，第1条指令的执行时间是将指令执行时的几个阶段所需时间相加得到，而在例题2中，认为每一个阶段所需时间都是流水线的周期时间。其中前者是流水线的理论计算方法，而后者是我们在设计硬件流水线时，常用的方式。两种计算方法，从理论上来讲，都是正确的，但考试时，只有一个是正确答案。那么我们应该怎么做呢?由于每次考试中，无论认可的是哪种计算方式，都只会把这种计算方式的正确答案放入选项中，而不会将两个正确答案都放入，所以我们在用一种方式不能得到正确选项时，应采用另一种方式进行计算，来得到正确答案。更多软件设计师资讯请到希赛软考学院。文档可能无法思考全面，请浏览后下载，另外祝您生活愉快，工作顺利，万事如意! /
