2016年軟件設計師教程重難點精講(一)

1、2016年軟件設計師教程重難點精講(一)2016下半年軟考軟件設計師報名即將開始，下面是希賽軟考學院整理的軟件設計師教程重點難點精講，希望對大家有所幫助。死鎖(Deadlock)是指多個進程在運行的過程中因爭奪資源而造成的一種僵局。當進程處于這種僵持狀態(tài)時，若無外力作用，它們都將無法再向前推進。在軟件設計師的考試當中，這個知識點的考查是以選擇題的形式出現(xiàn)的，考點主要有：死鎖的必要條件、解決死鎖的方法，最難高難度會考到“銀行家算法”。本文將介紹死鎖的相關知識，但不會具體講解“銀行家算法”，該算法將在本系列的下一篇文章中詳細說明。1、死鎖發(fā)生的必要條件死鎖的發(fā)生必須具備四個必要條件，這四個條件相互

2、聯(lián)系、缺一不可?；コ鈼l件：指進程對所分配到的資源進行排他性使用，即在一段時間內某資源只由一個進程占用。如果此時還有其他進程請求該資源，則請求者只能等待，直至占有該資源的進程用完并釋放。請求和保持條件：指進程已經(jīng)保持了至少一個資源，但又提出了新的資源請求，而該資源又已被其他進程占有，此時請求進程阻塞，但又對自己已獲得的其他資源保持不放。(1) 不剝奪條件：指進程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時由自己釋放。環(huán)路等待條件：指在發(fā)生死鎖時，必然存在一個進程-資源的環(huán)形鏈，即進程集合(P0,P1,P2Pn中的P0正在等待一個P1占用的資源，P1正在等待P2占用的資源，Pn正在等待

3、已被P0占用的資源。2、判斷系統(tǒng)是否可能進入死鎖狀態(tài)從上面的死鎖解決方案來看，無論哪一種方式都不可避免的要增加系統(tǒng)的負擔。而同時一個系統(tǒng)是否有可進入死鎖狀態(tài)受系統(tǒng)資源數(shù)量，需要使用該資源的進程數(shù)量等因素影響。若系統(tǒng)本不可能引起死鎖，而我們采用了死鎖解決方案，是很不合理的。所以，考試中?？嫉竭@樣的題型：給出系統(tǒng)的資源數(shù)，以及需要使用該資源的進程數(shù)量等參數(shù)，讓考生判斷系統(tǒng)有無可能產(chǎn)生死鎖。下面我們以例題的方式來說明如何解決這類問題。例題1:系統(tǒng)有3個進程：A、B、C。這3個進程都需要5個系統(tǒng)資源。如果系統(tǒng)有多少個資源，則不可能發(fā)生死鎖。解答：在分析這個問題時，我們可以取一些簡單的數(shù)據(jù)代入試題進行驗

4、證、分析，以得到相應的規(guī)律。如：(1)當系統(tǒng)資源數(shù)量為9時，若給A與B分別分配了4個資源，C分配了1個資源，則系統(tǒng)中的每個進程都存在資源不足的情況，而都不放手自己擁有的資源。不能正常運行完畢，發(fā)生死鎖。(2) 當系統(tǒng)資源數(shù)量為12時，若給A、B、C各分配4個資源，則死鎖。當系統(tǒng)資源數(shù)量為13時，無論如何分配，總有至少1個進程能得到5個資源，得到5個資源的進程可以正常運行完畢，而后將自己占用的資源分配給其它進程，所以這樣能使所有進程運行完畢。從上面的嘗試，我們可以總結出一個規(guī)律：先給所有進程分配他們所需要的資源數(shù)減1個資源，然后系統(tǒng)如果能再剩余1個資源，則系統(tǒng)不會發(fā)生死鎖。這樣解答本題變得非常容

5、易。(5-1)*3+1=13。例題2:一臺計算機有10臺磁帶機被m個進程競爭，每個進程最多需要三臺磁帶機，那么m至多為時，系統(tǒng)沒有死鎖的危險。A.3B.4C.5D.6解答：首先從m=6開始考察，首先每個進程分配1臺，剩下的4臺只能分配給4個進程，還有2個進程沒有分配，如果已經(jīng)分配了2臺的4個進程需要3臺的話，則系統(tǒng)就會死鎖。同樣，如果m=5，也會發(fā)生這種情況。當m=4時，每個進程可以分得2臺，還有2個進程可分得3臺，則可正常運行，運行完畢后可釋放資源，從而不會死鎖。在解這道題時有些學員提出“如果按照答案m=4，則這4個進程都是需要3臺磁帶機的話，共需要12臺磁帶機，這樣還不會死鎖？”。這種想法

6、是錯誤的，因為并不是同時把所有進程都分配給足夠的資源才能完成這些進程，可以是一個進程先執(zhí)行完，釋放完資源再執(zhí)行另一個進程。例如：4個進程中，每個進程分配2臺磁帶機，用去了8臺。剩下2臺，仍然可以滿足兩個進程，直到他們完成，釋放他們暫用的磁帶機。流水線流水線這個知識點在軟件設計師考試中是個重點也是個難點，考查的頻率比較高。之所以說流水線是個難點，有兩方面的原因：一方面是需要理解流水線的理論，了解其工作原理，計算方式；另一方面是在軟考當中，對于流水線的相關計算，標準并不是完全統(tǒng)一的，這一點在后面我們將詳細介紹。流水線是指在程序執(zhí)行時多條指令重疊進行操作的一種準并行處理實現(xiàn)技術。各種部件同時處理是針

7、對不同指令而言的，它們可同時為多條指令的不同部分進行工作，以提高各部件的利用率和指令的平均執(zhí)行速度。指令流水線是將指令執(zhí)行分成幾個子過程，每一個子過程對應一個工位，我們稱為流水級或流水節(jié)拍，這個工位在計算機里就是可以重疊工作的功能部件，稱為流水部件。如圖1所示，IF,ID,EX,WD分別是流水線的流水部件。SIS2S3S4S1幾個部洋貌威的流水舞|流水線要求所有的流水級部件必須在相同的時間內完成各自的子過程。在流水線中，指令流動一步便是一個機器周期，機器周期的長度必須由最慢的流水級部件處理子過程所需的時間來決定。那么我們?yōu)槭裁匆岢隽魉€這個概念，以及流水線是如何提高系統(tǒng)吞吐量的呢？下面我們來

8、看幾個圖，概念自然就清楚了。圖2是一個非流水線結構系統(tǒng)執(zhí)行指令時空圖?？臻gS11111匚EXI.JnIDIFa12343672非流水線緒柄系統(tǒng)執(zhí)行將令時空圖8T我們從圖2中可以看到，任意一個系統(tǒng)時間都有大量的設備處于空閑狀態(tài)，如第一個時間段有ID,EX,WB空閑，則第二個時間段有IF,EX,WB空閑。我們再來看采用了流水線結構的時空圖3?？臻gSjWBEX】DIFLJN11213JW115iiS3234567$T訝水統(tǒng)緯構指令時空囹顯然，采用流水線可以大大提升系統(tǒng)資源的利用率，以及整個系統(tǒng)的吞吐量。流水線的操作周期取決于基本操作中最慢的那個。例如：一個3段流水線，各段的執(zhí)行時間分別為t,2t,t

9、。則最慢的一段為2t,所以流水線操作周期為2t。流水線的執(zhí)行時間公式為：第1條指令的執(zhí)行時間+（指令條數(shù)-1）*流水線操作周期例題1若每一條指令都可以分解為取指、分析和執(zhí)行三步。己知取指時間t取指=4A,分析時間t分析=3身,執(zhí)行時間t執(zhí)行=5A。如果按串行方式執(zhí)行完100條指令需要（1）有。如果按照流水方式執(zhí)行，執(zhí)行完100條指令需要（2）A。供選擇的答案（1）A.1190B.1195C.1200D.1205A.504B.507C.508D.510試題分析本題考查的是計算機系統(tǒng)指令流水線方面的基礎知識。根據(jù)題意可以看到，在此流水線中按串行方式執(zhí)行完100條指令要用1200身。采用流水方式執(zhí)行

10、，執(zhí)行的總時間的關鍵取決于最長的執(zhí)行時間，所以執(zhí)行完100條的時間為：4At+3At+5At+（100-1）*5At=507to試題答案CB例題2現(xiàn)采用4級流水線結構分別完成一條指令的取指、指令譯碼和取數(shù)、運算，以及送回運算結果4個基本操作，每步操作時間依次為60ns,100ns,50ns和70ns。該流水線的操作周期應為Ans。若有一小段程序需要用20條基本指令完成（這些指令完全適合于流水線上執(zhí)行），則得到第一條指令結果需Bns，完成該段程序需Cns。在流水線結構的計算機中，頻繁執(zhí)行D指令時會嚴重影響機器的效率。當有中斷請求發(fā)生時，采用不精確斷點法，則將E。供選擇的答案A:507010028

11、0B:100200280400C:1400200023002600D:條件轉移無條件轉移算術運算訪問存儲器E:僅影響中斷反應時間，不影響程序的正確執(zhí)行 不僅影響中斷反應時間，還影響程序的正確執(zhí)行 不影響中斷反應時間，但影響程序的正確執(zhí)行 不影響中斷反應時間，也不影響程序的正確執(zhí)行試題分析本題主要考查對流水線技術的掌握。對于CPU來說，流水線技術實際上是一種以增加硬件換取性能的方式：把一條指令分解成多條更小的指令，由不同的處理單元來處理，在理想的滿負荷運行狀態(tài)下，執(zhí)行一條指令的時間雖然沒有減少，但是由于多個處理單元同時工作，在同一時間上可以執(zhí)行不同指令的不同部分，從而使得總體的執(zhí)行時間大大減少。

12、流水線的操作周期取決于基本操作中最慢的那個。這里最慢的是100ns，所以操作周期是100ns。在流水線中，其實每一條指令的執(zhí)行時間并沒有減少，而第一條指令的執(zhí)行并沒有體現(xiàn)流水線的優(yōu)勢，它在4個操作周期后才能執(zhí)行完成，這以后每個操作周期都能完成一條指令的執(zhí)行。影響流水線效率的重要因素有條件轉移指令和中斷，因為它們打斷了流水線，使得流水線不得不重新裝載。不精確斷點法實現(xiàn)簡單，但是要等到流水線內的指令完成之后再響應中斷。試題答案A.B.C.D.E.上面的兩個例題，都是軟考當中出現(xiàn)過的真題。我們可以看出，兩個題在計算流水線時間方面，標準并不是統(tǒng)一的。在例題1中：4At+3At+5At+(100-1)*5At=507Ato而在例題2中：100ns+100ns+100ns+100ns+(20-1)*100ns=2300ns這兩種計算方法，都是在套用公式：“第1條指令的執(zhí)行時間+(指令條數(shù)-1)*流水線操作周期”，而對于“第1條指令的執(zhí)行時間”的理解并不相同。在例題1中，第1條指令的執(zhí)行時間是將指令執(zhí)行時的幾個階段所需時間相加得到，而在例題2中，認為每一個階段所需時間都是流水線的周期時間。其中前者是流水線的理論計算方法，而后者是我們在設計硬件流水線時，常用的