串講1 硬件知識和數(shù)據(jù)結(jié)構(gòu)串講(已打)

專題串講一計算機系統(tǒng)知識和數(shù)據(jù)結(jié)構(gòu)一、計算機系統(tǒng)知識計算機體系結(jié)構(gòu)和主要部件的基本工作原理?CPU和存儲器的組成、性能、基本工作原理CPU主要由運算器和控制器組成。大家要明白運算器和控制器的作用以及工作原理。運算器負責對數(shù)據(jù)的算術(shù)運算和邏輯運算的加工處理?；窘Y(jié)構(gòu)由算術(shù)/邏輯運算單元(ALU)、累加器ACC、寄存器組、多路轉(zhuǎn)換器和數(shù)據(jù)總線等邏輯部件組成?？刂破鞴δ苁菑膬?nèi)存中取出指令，并指出下一條指令在內(nèi)存中的位置。將指令經(jīng)指令寄存器送往指令譯碼器，經(jīng)過對指令的分析發(fā)出相應的控制和定時信息，控制協(xié)調(diào)計算機的各個部件的工作，以完成指令所規(guī)定的操作?？刂破鲌?zhí)行指令的過程：1、取指令：從內(nèi)存中取出一條指令2、 指令譯碼：將指令的操作碼部分送入指令譯碼器進行分析，然后根據(jù)指令的功能向有關(guān)部分發(fā)出控制命令。3、 按指令操作碼執(zhí)行：實現(xiàn)指令的具體功能。4、形成下一條指令地址CPU功能程序控制(重要職能)：CPU通過執(zhí)行指令來控制程序的執(zhí)行順序。操作控制：產(chǎn)生每條指令的操作信號并將操作信號送往不同的部件，控制相應的部件按指令的功能要求進行操作。時間控制：對各種操作進行時間上的控制。數(shù)據(jù)處理(根本任務)：對數(shù)據(jù)進行算術(shù)運算及邏輯運算等方式進行加工處理，處理結(jié)果由人們直接利用。?I/O接口的功能、類型和特點I/O系統(tǒng)在CPU、存儲器和各種外部設(shè)備之間負責協(xié)調(diào)和控制數(shù)據(jù)的輸入/輸出。I/O系統(tǒng)控制器基本結(jié)構(gòu)有：數(shù)據(jù)寄存器、狀態(tài)寄存器、控制寄存器、控制電路。I/O系統(tǒng)的工作方式有以下幾種：微型計算機中最常用的內(nèi)存與接口編址方式(該知識點要求掌握兩種編址方式的原理及其優(yōu)缺點)內(nèi)存與接口地址獨立的編址方法.內(nèi)存地址和接口地址是完全獨立的兩個地址空間，內(nèi)存用于存放程序和數(shù)據(jù)，而接口就用于尋址外設(shè)。它們是完全獨立的并且是相互隔離的。該方式由于二者使用的指令完全不同，因此易于編程，但指令少，功能弱內(nèi)存與接口地址同一的編制方法內(nèi)存地址和接口地址統(tǒng)一在一個公共的地址空間里，內(nèi)存空間里每一個地址都可以分配給接口也可以分配給內(nèi)存使用。但是，分配給內(nèi)存的只能用于內(nèi)存，接口絕不允許使用。同樣，分配給接口的地址內(nèi)存也決不能再用。大大增強了對接口的操作功能，但不易于編程。(2)直接程序控制該知識點的關(guān)鍵在于整個輸入輸出過程在CPU執(zhí)行程序的控制下完成，以及兩種控制方式的比較：?無條件傳送：外設(shè)無條件的隨時接收CPU發(fā)來的輸出數(shù)據(jù)，也無條件的隨時向CPU提供需要輸入的數(shù)據(jù)。程序查詢方式：由CPU通過執(zhí)行程序查詢外設(shè)的狀態(tài)，判斷外設(shè)是否準備好接收數(shù)據(jù)或準備好了向CPU輸入的數(shù)據(jù)。其優(yōu)點在于容易實現(xiàn)，但降低了CPU的效率，對外部的突發(fā)事件無法作出實時響應。（3）中斷方式（明白中斷控制機制，以及5種中斷處理方法原理）中斷控制機制：計算機系統(tǒng)通常提供了中斷機制，允許某一事件中止CPU正在執(zhí)行的程序，轉(zhuǎn)去對該事件進行處理，然后再返回原程序被中止處繼續(xù)執(zhí)行。其作用是提高CPU的處理效率，使CPU與I/O設(shè)備并行工作，還可以實現(xiàn)分時操作過程。中斷處理方法：多中斷信號線法：每個中斷源都有屬于自己的一根中斷請求信號線向CPU提出中斷請求。中斷軟件查詢法：當CPU檢測到一個中斷請求信號以后，即輪詢每個中斷源以確定是誰發(fā)出中斷請求信號。雛菊鏈法：所有I/O模塊共享一根共同的中斷請求線。當CPU檢測到中斷請求信號，則發(fā)出中斷確認信號。中斷確認信號依次在I/O模塊間傳遞，直到發(fā)出請求的模塊，該模塊則把它的ID送往數(shù)據(jù)線由CPU讀取?？偩€仲裁法：一個I/O設(shè)備在發(fā)出中斷請求之前，必須先獲得總線控制權(quán)。所以可由總線仲裁機制來裁定誰可以發(fā)出中斷請求信號。中斷向量表法：中斷向量表用來保存各個中斷源的中斷服務程序的入口地址。當外設(shè)發(fā)出中斷請求信號后，由中斷控制器確定其中斷號，并根據(jù)中斷號查找中斷向量表來取得其中斷服務程序的入口地址。中斷優(yōu)先級控制：當不同優(yōu)先級的多個中斷源同時提出中斷請求時，CPU應優(yōu)先響應優(yōu)先級最高的中斷源。當CPU正在對某一個中斷源服務時，當比它優(yōu)先級更高的中斷源提出中斷請求時，CPU應暫時中斷當前的服務，去對優(yōu)先級更高的中斷源服務，服務結(jié)束后再回到原先被中斷的優(yōu)先級較低的中斷服務程序繼續(xù)執(zhí)行。這種情況稱為中斷嵌套。（4） 直接存儲器存取方式（重點）直接存儲器存?。―MA）是指數(shù)據(jù)在內(nèi)存與I/O設(shè)備間直接成塊傳送，不需要CPU的干預。該知識點的關(guān)鍵在于DMA的工作方式。（5）輸入輸出處理機重點在于它也不需要CPU的干預，且不影響計算機的整體性能。輸入輸出處理機適合有較多外設(shè)的大型計算機。輸入輸出處理機是一個專用處理機，主機的輸入輸出操作都由它來完成。?CISC/RISC,流水線操作，多處理機，并行處理重點：CISC和RISC的比較、流水線技術(shù)、多處理的原理、并行處理和并行處理機的原理CISC和RISC的比較:

指令數(shù)量眾多指令使用頻率相差懸殊指令數(shù)量眾多指令使用頻率相差懸殊支持很多種尋址方式變長的指令格式指令可以對存儲器中數(shù)據(jù)直接進行處理指令數(shù)量少指令的尋址方式少指令長度固定只提供了Load/Store指令訪問存儲器以硬布線邏輯控制為主單周期指令執(zhí)行擁有相當多的寄存器優(yōu)化的編譯器流水線技術(shù)：可能會給出一組指令執(zhí)行過程所需時間，要求計算全部指令完成時間、指令完成周期和流水線處理機的吞吐率和建立時間。多處理的原理：多處理機具有兩個或兩個以上的處理機，共享輸入/輸出子系統(tǒng)，在統(tǒng)一的操作系統(tǒng)控制下，通過共享主存或高速通信網(wǎng)絡(luò)進行通信，協(xié)同求解一個大而復雜的問題。多處理機具有共享存儲器和分布存儲器兩種不同的結(jié)構(gòu)。并行處理機的原理：(絕對重點)并行性(parallelism)就是指在同一時刻或同一時間間隔內(nèi)完成兩種或兩種以上性質(zhì)相同或不同的工作，只要時間上相互重疊，就都蘊含了并行性。并行性有兩重含義：同時性(simultaneity)：兩個或兩個以上事件在同一時刻發(fā)生并發(fā)性(concurrency)：兩個或兩個以上事件在同一時間間隔內(nèi)發(fā)生提高計算機系統(tǒng)并行性的措施主要有3類。?時間重疊在并行性概念中導入時間因素，讓多個處理過程在時間上錯開，輪流重疊的使用同一套硬件設(shè)備的各個部件，以加快硬件周轉(zhuǎn)，提高處理速度。?資源重復在并行性概念中導入空間因素，基于“以數(shù)量取勝”的原則，通過重復設(shè)置硬件資源來提高系統(tǒng)可靠性或性能。?資源共享多個用戶按一定時間順序輪流的使用同一套資源，以提高其利用率，從而相應的提高整個系統(tǒng)的性能。并行處理機(也稱為陣列處理機)使用按地址訪問的RAM,主要用于要求大量高速進行向量或矩陣運算的應用領(lǐng)域。并行處理機的并行性來源于資源重復，它依靠操作級的并行處理來提高系統(tǒng)性能。屬于SIMD計算機存儲系統(tǒng)?虛擬存儲器基本工作原理，多級存儲體系虛擬存儲器：虛擬存儲系統(tǒng)的作用是給程序員一個更大的虛擬的存儲空間，其容量可遠遠超過主存儲器的容量，而與輔助存儲器容量相當。我們提供給用戶的這個存儲器，即在軟件編程上可以使用的存儲器，就稱為虛擬存儲器。它的容量即虛擬存儲空間，簡稱虛擬空間。面向虛擬存儲器的編程地址稱為虛擬地址，或稱為邏輯地址。與主存和輔助存儲器地址相對應。在存儲技術(shù)中，存在以下制約關(guān)系：存儲器讀寫速率越高，每位的成本也較高；存儲器容量越大，每位的成本也越低存儲器容量越大，讀寫速率越低。解決這一難點的方法就是采用多級存儲體系結(jié)構(gòu)。典型的三級存儲體系結(jié)構(gòu)如下圖所示，分為“高速緩沖存儲器（Cache）-主存-外存”三個層次。1） 主存■輔存層次：主存中存放當前執(zhí)行的程序及所需數(shù)據(jù)，可供CPU直接訪問。而外存中存放的是暫時不用的程序及數(shù)據(jù)。當CPU需要執(zhí)行外存中的某一程序時，首先將該程序由外存調(diào)入主存，然后再執(zhí)行。因為CPU不能直接訪問外存。2） 主存-Cache層次：主存存取速度與CPU的速度的差距很大，為了彌補主存速度的不足，使之與CPU速度相匹配，則在CPU和主存之間增設(shè)一個容量不大，速度很高的“高速緩沖存儲器”，簡稱Cache。這樣較好的解決了速度與價格之間的矛盾。輔助存儲器方面的計算：（重點）存儲容量為capacity=n*t*s*b,n為存放數(shù)據(jù)的總盤面數(shù)；t為每面的磁道數(shù)；s為每道的扇區(qū)數(shù)；b為每個扇區(qū)存儲的字節(jié)數(shù)尋道時間為磁頭移動到目標磁道所需的時間。等待時間為待讀寫的扇區(qū)旋轉(zhuǎn)到磁頭下方所用的時間。一般用磁道旋轉(zhuǎn)一周所用的時間的一半作為平均等待時間。4．磁盤存取時間=尋道時間+等待時間。5．位密度：沿磁道方向，單位長度存儲二進制信息的個數(shù)；6．道密度：沿磁盤半徑方向，單位長度內(nèi)磁道的數(shù)目；7.數(shù)據(jù)傳輸速率R=B/T，B為一個磁道上記錄的字節(jié)數(shù)，T為每轉(zhuǎn)一周的時間安全性、可靠性與系統(tǒng)性能評測基礎(chǔ)知識（重點）?診斷與容錯（a） 計算機的故障：可以分為永久性、間歇性及瞬時性3類：（b） 故障診斷方法：包括故障檢測和故障定位兩個方面。（c） 故障診斷主要有下述三種方法：對電路直接進行測試的故障定位測試法“檢查診斷程序”法：利用機器指令的功能來對系統(tǒng)的某些部件進行測試。微診斷法：在微程序控制的計算機中用微指令來對系統(tǒng)進行診斷。（d）計算機容錯技術(shù)：容錯是采用冗余方法來消除故障影響。針對硬件，有時間冗余和元器件冗余兩種方法。（e）容錯系統(tǒng)簡單的雙機備份：將關(guān)鍵的元件或整機設(shè)置兩套，其中一套用作備份。>熱備份（雙重系統(tǒng)）：兩套系統(tǒng)同時同步運行，當聯(lián)機子系統(tǒng)檢測到錯誤時，退出服務進行檢修，而由“熱備份”子系統(tǒng)接替工作。>冷備份（雙工系統(tǒng)）：冷備份子系統(tǒng)平時停機或運行與聯(lián)機系統(tǒng)無關(guān)的運算，當聯(lián)機子系統(tǒng)產(chǎn)生故障時，人工或自動進行切換，使冷備份系統(tǒng)成為聯(lián)機系統(tǒng)。操作系統(tǒng)支持的雙機容錯：在操作系統(tǒng)的層次上，支持聯(lián)機維修，即故障部分退出運行、進行維修并重新投入運行都不影響正在運行的應用程序。?系統(tǒng)可靠性分析評價和計算機系統(tǒng)性能評測方法重點：可靠性與失效率的概念和關(guān)系，平均無故障時間MTBF和平均修復時間MTRF的計算，串聯(lián)系統(tǒng)和并聯(lián)系統(tǒng)的可靠性和失效律計算，N模冗余系統(tǒng)的可靠性計算二、數(shù)據(jù)結(jié)構(gòu)與算法我們在課件中介紹的各種常用數(shù)據(jù)結(jié)構(gòu)和算法都要求掌握。數(shù)據(jù)結(jié)構(gòu)（1） 線性表：重點掌握存儲結(jié)構(gòu)中的鏈表（包括單鏈表、雙向鏈表和循環(huán)鏈表）。（2） 棧：重點掌握棧的后進先出的特點（3） 隊列：重點掌握隊列的先進先出的特點（4） 樹（重點）：關(guān)鍵掌握樹的3種鏈式存儲結(jié)構(gòu)（雙親表示法、孩子表示法、孩子兄弟表示法）、樹的前序、后序和中序遍歷、（5） 二叉樹（絕對重點）：應該是必考的內(nèi)容。重點掌握：二叉樹的特性（有5條）、二叉樹的遍歷（前序、后序和中序）、哈夫曼樹的構(gòu)造（哈夫曼算法）、三種二叉樹的區(qū)分（滿二叉樹、完全二叉樹和非完全二叉樹）、二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)、樹和森林轉(zhuǎn)換為二叉樹（見教程86頁）（6） 圖：關(guān)鍵掌握：圖的性質(zhì)、圖的出處存儲結(jié)構(gòu)（重點是鄰接矩陣和鄰接鏈表）、圖的遍歷（深度優(yōu)先和廣度優(yōu)先）、最小生成樹的兩個算法（Prim算法和Kruskal算法）、最短路徑算法（Dijkstra算法）查找和排序算法：所有涉及到的算法的思想和時間復雜度都要求掌握。其中折半查找中的判定樹和二叉排序樹要會構(gòu)造，平衡二叉樹上的插入操作的4種調(diào)整手段要求掌握。常見算法設(shè)計方法要求一般掌握，即了解它們的思想。例題：

1、假設(shè)一個有3個盤片的硬盤，共有4個記錄面，轉(zhuǎn)速為7200轉(zhuǎn)/分，盤面有效記錄區(qū)域的外直徑為30cm,內(nèi)直徑為10cm,記錄位密度為250位/mm，磁道密度為8道/mm，每磁道分16個扇區(qū)，每扇區(qū)512字節(jié)，則該硬盤的非格式化容量和格式化容量約為__(58)__，數(shù)據(jù)傳輸率約為__(58)__若一個文件超出一個磁道容量，剩下的部分__(60)A.120MB和A.120MB和100MBB.30MB和25MBA.2356KB/s B.3534KB/sA.存于同一盤面的其它編號的磁道上C.60MB和50MB D.22.5MB和25MBC.7069KB/s D.1178KB/s存于其它盤面的同一編號的磁道上C.存于其它盤面的其它編號的磁道上C.存于其它盤面的其它編號的磁道上D.存放位置隨機(58)B(59)D(60)B非格式化容量二面數(shù)X(磁道數(shù)/面)X內(nèi)圓周長X最大位密度磁道數(shù)=(內(nèi)外半徑之差)X磁道密度=(30寧2—10寧2)X80=800內(nèi)圓周長=2冗r=2X冗X5最大位密度二2500位/cm非格式化容量=4X800X2X冗X5X2500寧10242寧8=30mb格式化容量=面數(shù)X(磁道數(shù)/面)X(扇區(qū)數(shù)/道)X(字節(jié)數(shù)/扇區(qū))=4X800X16X512寧10242=25mb數(shù)據(jù)傳輸速率=一個磁道上記錄的字節(jié)數(shù)/每轉(zhuǎn)一周的時間=512X16寧(60寧7200)位密度：沿磁道方向，單位長度存儲二進制信息的個數(shù)；道密度：沿磁盤半徑方向，單位長度內(nèi)磁道的數(shù)目；數(shù)據(jù)傳輸速率R=B/T,B為一個磁道上記錄的字節(jié)數(shù)，T為每轉(zhuǎn)一周的時間2、利用并行處理技術(shù)可以縮短計算機的處理時間,所謂并行性是指__(51)__?？梢圆捎枚喾N措施來提高計算機系統(tǒng)的并行性,它們可分成三類,即__(52)__。提供專門用途的一類并行處理機(亦稱陣列處理機)以__(53)__方式工作,它適用于__(54)__。多處理機是目前較高性能計算機的基本結(jié)構(gòu),它的并行任務的派生是__(55)__。:A.多道程序工作:A.多道程序工作C.非單指令流單數(shù)據(jù)流方式工作:A.多處理機,多級存儲器和互連網(wǎng)絡(luò)C.微指令,虛擬存儲和I/0通道:A.SISD B.SIMD:A.事務處理 B.工業(yè)控制D.在同一時間完成兩種或兩種以上工作B.流水結(jié)構(gòu),高速緩存和精簡指令集D.資源重復,資源共享和時間重疊。MISD D.MB4D矩陣運算 D.大量浮點計算:A.需要專門的指令來表示程序中并發(fā)關(guān)系和控制并發(fā)執(zhí)行B.靠指令本身就可以啟動多個處理單元并行工作只執(zhí)行沒有并發(fā)約束關(guān)系的程序先并行執(zhí)行,事后再用專門程序去解決并發(fā)約束(51)D (52)D (53)B (54)C (55)A52：SIMD是單指令流多數(shù)據(jù)流計算機，通過資源重復實現(xiàn)并行性多處理機屬于MIMD計算機3、發(fā)展容錯技術(shù)可提高計算機系統(tǒng)的可靠性。利用元件冗余可保證在局部有故障情況下系統(tǒng)的正常工作。帶有熱備份的系統(tǒng)稱為__(56)__系統(tǒng)。它是__(57)__,因此只要有一個子系統(tǒng)能正常工作,整個系統(tǒng)仍能正常工作。當子系統(tǒng)只能處于正常工作和不工作兩種狀態(tài)時,我們可以采用圖A的并聯(lián)模型,若單個子系統(tǒng)的可靠性都為0.8時,圖示的三個子系統(tǒng)并聯(lián)后的系統(tǒng)可靠性為__(58)__。若子系統(tǒng)能處于正常和不正常狀態(tài)時,我們可以采用圖B所示的表決模型,若圖中有任何二個或三個子系統(tǒng)輸出相同時,則選擇該相同的輸出作為系統(tǒng)輸出,設(shè)單個子系統(tǒng)的可靠性為0.8時,整個系統(tǒng)的可靠性為__(59)__;若單個子系統(tǒng)的可靠性為0.5時,整個系統(tǒng)的可靠性為__(60)__。[圖A] [圖B]子系統(tǒng)1子系統(tǒng)1輸入子系統(tǒng)2——輸出輸入——子系統(tǒng)2輸出子系統(tǒng)3子系統(tǒng)3:A?并發(fā) B.雙工 C.雙重 D.并行。:A.兩子系統(tǒng)同時同步運行,當聯(lián)機子系統(tǒng)出錯時,它退出服務,由備份系統(tǒng)接替?zhèn)浞菹到y(tǒng)處于電源開機狀態(tài),一旦聯(lián)機子系統(tǒng)出錯時,立即切換到備份系統(tǒng)兩子系統(tǒng)交替處于工作和自檢狀態(tài),當發(fā)現(xiàn)一子系統(tǒng)出錯時,它不再交替到工作狀態(tài)兩子系統(tǒng)并行工作,提高機器速度,一旦一個子系統(tǒng)出錯,放棄并行工作。(58):A.0.9B.O.94C.O.992D.O.996(59):A.0.882B.O.896C.O.925D.O.94(60):A.0.5B.O.54 C.O.62D.O.65(56)C(57)A(58)C(59)B(60)A并聯(lián)系統(tǒng)可靠性：R=l-(1-R)(l-R)?(1—R)=l—0.2X0.2X0.2=0.99212nN模冗余系統(tǒng)：N=2n+1?？煽啃詾椋篟 xRi(1-R)n-iN00可靠性： i=n+卜丿 =C2*0.82*0.2+C3*0.83334、直接存儲器訪問(DMA)是一種快速傳遞大量數(shù)據(jù)常用的技術(shù)。工作過程大致如下：向CPU申請DMA傳送；獲CPU允許后，DMA控制器接管_A_的控制權(quán)；在DMA控制器的控制下，在存儲器和_B_之間直接進行數(shù)據(jù)傳送，在傳送過程中不需要_CJ勺參與。開始時需提供要傳送的數(shù)據(jù)的_D_和_E_0傳送結(jié)束后，向CPU返回DMA操作完成信號。供選擇的答案：A：①系統(tǒng)控制臺 ②系統(tǒng)總線 ③I/O控制器 ④中央處理器

B：①外部設(shè)備②運算器③緩存④中央處理器C：①外部設(shè)備②系統(tǒng)時鐘③系統(tǒng)總線④中央處理器D：①結(jié)束地址②起始地址③設(shè)備類型④數(shù)據(jù)速率E：①結(jié)束地址②設(shè)備類型③數(shù)據(jù)長度④數(shù)據(jù)速率214214232 14 2 35、現(xiàn)采用四級流水線結(jié)構(gòu)分別完成一條指令的取指令、指令譯碼和取操作數(shù)、運算以及送回運算結(jié)果四個基本操作，每步操作時間依次為60ns,100ns,50ns和70ns。該流水線的操作周期應為—A_ns。若有一小段程序需要用20條基本指令完成（這些指令完全適合于流水線上執(zhí)行），則得到第一條指令結(jié)果需_B_ns，完成該段程序需_C_ns。供選擇的答案：A：①50②70③100④280B：①100②200③280④400C：①1400②