計(jì)算機(jī)硬件相關(guān)基礎(chǔ)知識(shí)--校驗(yàn)碼

指令系統(tǒng)

計(jì)算機(jī)指令的組成：一條指令由操作碼和操作數(shù)兩部分組成，操作碼決定要完成的操作，操作數(shù)是指參與運(yùn)算的數(shù)據(jù)及其所在的單元地址。

在計(jì)算機(jī)中，操作要求(操作碼)和操作數(shù)地址(操作數(shù))都由二進(jìn)制數(shù)碼表示，分別稱(chēng)作操作碼和地址碼，整條指令以二進(jìn)制編碼的形式存放在存儲(chǔ)器中

計(jì)算機(jī)指令執(zhí)行過(guò)程：取指令--分析指令--執(zhí)行指令三個(gè)步驟.

1. 首先將程序計(jì)數(shù)器PC中的指令地址取出，送入地址總線，CPU依據(jù)指令地址去內(nèi)存中取出指令內(nèi)容存入指令寄存器IR；
2. 然后由指令譯碼器進(jìn)行分析，分析指令操作碼；
3. 最后執(zhí)行指令，取出指令執(zhí)行所需的源操作數(shù)。

計(jì)算機(jī)指令執(zhí)行過(guò)程

如果是涉及到運(yùn)算，可能還要包含運(yùn)算器的介入，最簡(jiǎn)單的取指令→分析指令→執(zhí)行指令流程即如上圖所示。

指令尋址方式

指令尋址是指通過(guò)指令地址找到實(shí)際指令內(nèi)容的過(guò)程

順序?qū)ぶ贩绞?/span>：當(dāng)執(zhí)行一段程序時(shí)，是一條指令接著一條指令順序執(zhí)行

跳躍尋址方式：指下一條指令的地址碼不是由程序計(jì)數(shù)器給出，而是由本條指令直接給出。

注意：程序跳躍后，按新的指令地址開(kāi)始順序執(zhí)行。因此程序計(jì)數(shù)器的內(nèi)容也必須相應(yīng)改變，以便及時(shí)追蹤新的指令地址。

指令操作數(shù)的尋址方式

指令操作數(shù)的尋址方式是指通過(guò)指令操作數(shù)地址找到實(shí)際操作數(shù)的過(guò)程

立即尋址方式：指令的地址碼字段指出的不是地址，而是操作數(shù)本身。

直接尋址方式：在指令的地址字段中直接指出操作數(shù)在主存中的地址。

間接尋址方式：指令地址碼字段所指向的存儲(chǔ)單元中存儲(chǔ)的操作數(shù)的地址，需要再根據(jù)主存中操作數(shù)地址找到對(duì)應(yīng)的操作數(shù)。

寄存器尋址方式：指令中的地址碼是寄存器的編號(hào)。

基址尋址方式：將基址寄存器的內(nèi)容加上指令中的形式地址而形成的操作數(shù)的有效地址，其優(yōu)點(diǎn)是可以擴(kuò)大尋址能力。

變址尋址方式：變址尋址方式計(jì)算有效地址的方式與基址尋址方式相似，它是將變址寄存器的內(nèi)容加上指令中的形式地址而形成操作數(shù)的有效地址。

指令系統(tǒng)的分類(lèi)

經(jīng)典處理器的指令系統(tǒng)分為兩類(lèi)：CISC(Complex Instruction Set Computers)和RISC(Reduced Instruction Set Computers)

CISC是復(fù)雜指令系統(tǒng)，兼容性強(qiáng)、指令繁多、長(zhǎng)度可變，由微程序?qū)崿F(xiàn)；

RISC是簡(jiǎn)單指令系統(tǒng)，指令少，使用頻率接近，主要依靠硬件實(shí)現(xiàn)(通用寄存器、硬布線邏輯控制)。

兩者的區(qū)別如下表：

CISC以Intel、AMD的x86 CPU為代表；RISC以ARM和Power為代表。其中國(guó)產(chǎn)處理器目前有龍芯、飛騰、申威等品牌常用的都是RISC-V、MIPS、ARM等精簡(jiǎn)指令集架構(gòu)

Flynn分類(lèi)法 (重點(diǎn))

Flynn根據(jù)系統(tǒng)內(nèi)同時(shí)執(zhí)行的指令流和處理的數(shù)據(jù)流為標(biāo)準(zhǔn)，對(duì)計(jì)算機(jī)系統(tǒng)進(jìn)行了分類(lèi)，共分為4類(lèi)：

1. 單指令流單數(shù)據(jù)流計(jì)算機(jī)(SISD)：屬于傳統(tǒng)的順序處理計(jì)算機(jī)，其指令部件一次僅對(duì)一條指令進(jìn)行譯碼，并且僅對(duì)一個(gè)操作部件分配數(shù)據(jù)
2. 單指令流多數(shù)據(jù)流計(jì)算機(jī)(SIMD)：這種計(jì)算機(jī)系統(tǒng)包含多個(gè)重復(fù)的運(yùn)算處理單元，但僅存在唯一的指令部件；運(yùn)行過(guò)程中由該指令部件從存儲(chǔ)器中取出指令，然后譯碼并發(fā)往運(yùn)算處理單元，各運(yùn)算處理單元按照統(tǒng)一指令流要求處理各自不同的數(shù)據(jù)
3. 多指令流單數(shù)據(jù)流計(jì)算機(jī)(MISD)：這種計(jì)算機(jī)系統(tǒng)究竟代表哪種計(jì)算機(jī)類(lèi)型，存在著不同的看法，有的文獻(xiàn)上將指令流水線看成是多指令部件，故將流水線體系結(jié)構(gòu)歸并到了這類(lèi)計(jì)算機(jī)中，有的文獻(xiàn)也將容錯(cuò)系統(tǒng)歸并到這一類(lèi)。
4. 多指令流多數(shù)據(jù)流計(jì)算機(jī)(MIMD)：是指實(shí)現(xiàn)作業(yè)、任務(wù)、指令、數(shù)據(jù)各個(gè)級(jí)別全面并行執(zhí)行的計(jì)算機(jī)系統(tǒng)。這樣的系統(tǒng)擁有多個(gè)處理器，每個(gè)處理器具有獨(dú)立的程序，每個(gè)程序?yàn)橄鄳?yīng)的處理器生成一個(gè)指令流，并處理各自不同的數(shù)據(jù)，顯然分布式計(jì)算機(jī)系統(tǒng)基本都屬于多指令流多數(shù)據(jù)流系統(tǒng)

指令流水線

串行技術(shù)是CISC中的指令執(zhí)行技術(shù)

流水線技術(shù)是RISC中的指令執(zhí)行技術(shù)

串行技術(shù)：即一個(gè)指令執(zhí)行過(guò)程(取值→分析→執(zhí)行)完成之后才能執(zhí)行下一個(gè)指令

流水線技術(shù)：即一個(gè)指令執(zhí)行完某一階段A后，開(kāi)始下一階段B時(shí)，另一個(gè)指令可以開(kāi)始階段A的執(zhí)行

RISC中流水線技術(shù)分類(lèi)：

• 超流水線技術(shù)(Super Pipe Line) ：通過(guò)細(xì)化流水、增加級(jí)數(shù)和提高主頻，使得在每個(gè)機(jī)器周期內(nèi)完成一個(gè)甚至兩個(gè)浮點(diǎn)操作(典型的以時(shí)間換空間)
• 超標(biāo)量技術(shù)(Super Scalar) ：通過(guò)內(nèi)裝多條流水線來(lái)同時(shí)執(zhí)行多個(gè)處理，其時(shí)鐘頻率雖然與一般流水接近，卻有更小的CPI(以空間換取時(shí)間)
• 超長(zhǎng)指令字技術(shù)(Very Long Instruction Word,VLIW) ：VLIW和超標(biāo)量都是同時(shí)執(zhí)行多條指令，其不同在于超標(biāo)量依靠硬件來(lái)實(shí)現(xiàn)并行處理的調(diào)度，VLIW則充分發(fā)揮軟件的作用，使硬件簡(jiǎn)化，性能提高。(也是屬于以空間換取時(shí)間)

流水線的時(shí)間計(jì)算(重點(diǎn))

流水線周期：指令分成不同執(zhí)行階段，其中執(zhí)行時(shí)間最長(zhǎng)的段為流水線周期

流水線執(zhí)行時(shí)間：1條指令總執(zhí)行時(shí)間+(總指令條數(shù)-1)*流水線周期

流水線吞吐量計(jì)算：吞吐率即單位時(shí)間內(nèi)執(zhí)行的指令條數(shù)。公式：指令條數(shù)/流水線執(zhí)行時(shí)間

流水線的加速比計(jì)算：加速比即使用流水線后的效率提升度，即比不使用流水線快了多少倍，越高表明流水線效率越高。公式：不使用流水線執(zhí)行時(shí)間/使用流水線執(zhí)行時(shí)間

例1：對(duì)于一個(gè)k段流水線，假設(shè)其各段的執(zhí)行時(shí)間均相等(設(shè)為t)，輸入到流水線中的任務(wù)是連續(xù)的理想情況下，完成n個(gè)連續(xù)任務(wù)需要的總時(shí)間是多少？

存儲(chǔ)系統(tǒng)

計(jì)算機(jī)采用分級(jí)存儲(chǔ)體系的主要目的是為了解決存儲(chǔ)容量、成本和速度之間的矛盾問(wèn)題

存儲(chǔ)器的定義：存儲(chǔ)器是利用半導(dǎo)體、磁、光等介質(zhì)制成的用于存儲(chǔ)數(shù)據(jù)的電子設(shè)備

根據(jù)存儲(chǔ)器的硬件結(jié)構(gòu)分為：SRAM、DRAm、NVRAM、Flash、EPROM、Disk等

計(jì)算機(jī)系統(tǒng)中的存儲(chǔ)器通常采用分層的體系結(jié)構(gòu)，按照與處理器的物理距離分類(lèi)：

• 片上緩存：在處理器核心中直接集成的緩存，一般為SRAM結(jié)構(gòu)，實(shí)現(xiàn)數(shù)據(jù)的快速讀取。容量較小【16KB~512KB】,按照不同的設(shè)計(jì)可能劃分為一級(jí)或二級(jí)
• 片外緩存：在處理器核心外的緩存，需要經(jīng)過(guò)交換互聯(lián)開(kāi)關(guān)訪問(wèn)，一般也是由SRAM構(gòu)成，容量比片上緩存略大【256KB~4MB】，按照層級(jí)被稱(chēng)為L(zhǎng)2Cache或L3Cache，或稱(chēng)為平臺(tái)Cache
• 主存（內(nèi)存）：通常采用DRAM結(jié)構(gòu)，以獨(dú)立的部件/芯片存在，通過(guò)總線與處理器連接。DRAM依賴(lài)不斷充電維持其中的數(shù)據(jù)，容量在數(shù)百M(fèi)B至數(shù)10GB之間
• 外存：可以是磁帶、磁盤(pán)、光盤(pán)和各類(lèi)Flash等介質(zhì)器件，這類(lèi)設(shè)備訪問(wèn)速度慢，但容量大，并且在掉電后能夠保持其數(shù)據(jù)。
  不同介質(zhì)類(lèi)型容量不同，如Nor Flash容量一般在MB級(jí)別，磁盤(pán)容量則在GB和TB級(jí)別。并非所有介質(zhì)都能夠永久性保存數(shù)據(jù)，每種介質(zhì)都有一定的年限，比如Flash外存的維持?jǐn)?shù)據(jù)年限在10年左右，光盤(pán)年限在數(shù)年至數(shù)十年，磁盤(pán)年限在十年以上，磁帶年限為30年以上。

存儲(chǔ)系統(tǒng)層級(jí)

image.png

兩級(jí)存儲(chǔ)：Cache-主存、主存-輔存(虛擬存儲(chǔ)體系)

Cache是高速緩沖寄存器，CPU和主存的交互速度影響了CPU的計(jì)算效率，因此采用了Cache這個(gè)設(shè)計(jì)，將常用的數(shù)據(jù)暫時(shí)存儲(chǔ)到Cache中

如何確定數(shù)據(jù)是否常用，即如何保證cache中的數(shù)據(jù)在短暫的時(shí)間內(nèi)CPU用得到？，就需要涉及到局部性原理！

局部性原理：在CPU運(yùn)行時(shí)，所訪問(wèn)的數(shù)據(jù)會(huì)趨向一個(gè)較小的局部空間地址內(nèi)，包括以下兩個(gè)方面：

• 時(shí)間局部性原理：如果一個(gè)數(shù)據(jù)項(xiàng)正在被訪問(wèn)，那么在近期它很可能會(huì)被再次訪問(wèn)，即在相鄰的時(shí)間里會(huì)訪問(wèn)同一個(gè)數(shù)據(jù)項(xiàng)
• 空間局部性原理：在最近的將來(lái)會(huì)用到的數(shù)據(jù)的地址和現(xiàn)在正在訪問(wèn)的數(shù)據(jù)地址很可能是相近的，即相鄰空間地址會(huì)被連續(xù)訪問(wèn)

高速緩存Cache

高速緩存Cache用于存儲(chǔ)當(dāng)前最活躍的程序和數(shù)據(jù)，直接與CPU交互，位于CPU和主存之間，容量小，速度為內(nèi)存的5-10倍，由半導(dǎo)體材料構(gòu)成。其內(nèi)容是主存內(nèi)存的副本拷貝，對(duì)于程序員來(lái)說(shuō)是透明的

Cache由控制部分和存儲(chǔ)器組成，存儲(chǔ)器存儲(chǔ)數(shù)據(jù)，控制部分判斷CPU要訪問(wèn)的數(shù)據(jù)是否在Cache，在則命中，不在則依據(jù)一定的算法從主存中替換(這就涉及到一個(gè)概念：命中率)

地址映射：在CPU工作時(shí)，送出的是主存單元的地址，而應(yīng)從Cache存儲(chǔ)器中讀/寫(xiě)信息，這就需要將主存地址轉(zhuǎn)換為Cache存儲(chǔ)器地址，這種地址的轉(zhuǎn)換稱(chēng)為地址映像，由硬件自動(dòng)完成映射(考點(diǎn))

地址映像的三種方法：

• 直接映像：將Cache存儲(chǔ)器等分成塊，主存也等分成塊，并且對(duì)塊進(jìn)行編號(hào)。主存中的塊與Cache中的塊的對(duì)應(yīng)關(guān)系是固定的，兩者塊號(hào)相同才能命中。特點(diǎn)：地址變化簡(jiǎn)單，不靈活，容易造成資源浪費(fèi)

直接映像.png

• 全相聯(lián)映像：同樣都等分成塊，并且編號(hào)。主存中任意一塊都與Cache中任意一塊對(duì)應(yīng)。特點(diǎn)：可隨意調(diào)入Cache任意位置，但是地址變化復(fù)雜，速度較慢。因?yàn)橹鞔婵梢噪S意調(diào)用任意Cache塊，因此只有當(dāng)Cache塊滿(mǎn)了之后，才會(huì)發(fā)生塊沖突。因此全相聯(lián)映像是最不容易發(fā)生沖突的映像方式。

全相聯(lián)映像.png

• 組組相連映像：組組相連映像是前面兩種方式的結(jié)合，將Cache存儲(chǔ)器先分塊再分組，主存也同樣先分塊再分組，組間采用直接映像，即主存中組號(hào)與Cache中組號(hào)相同的組才能命中，但是組內(nèi)全相聯(lián)映像，也即組號(hào)相同的兩個(gè)組內(nèi)的所有塊可以任意調(diào)換

Cache的替換算法

替換算法的目的：使Cache獲得盡可能高的命中率。常用的算法有如下幾種：

1. 隨機(jī)替換算法：就是使用隨機(jī)數(shù)發(fā)生器產(chǎn)生一個(gè)要替換的塊號(hào)，將該塊替換出去。
2. 先進(jìn)先出算法：就是將最先進(jìn)入Cache中的信息塊替換出去
3. 近期最少使用算法：這種方法是將近期使用最少的Cache中的信息塊替換出去(最常用的算法)
4. 優(yōu)化替換算法：這種方法必須先執(zhí)行一次程序，統(tǒng)計(jì)Cache的替換情況。通過(guò)統(tǒng)計(jì)信息在第二次執(zhí)行程序時(shí)便于用最有效的方式來(lái)替換。

命中率與平均時(shí)間的計(jì)算

Cache命中率：即當(dāng)CPU所訪問(wèn)的數(shù)據(jù)在Cache中時(shí)，命中則直接從Cache中讀取數(shù)據(jù)，未命中則表示不在Cache中，需要從內(nèi)存中讀取。那么CPU在多次讀取數(shù)據(jù)時(shí)，從Cache中讀取數(shù)據(jù)的次數(shù)/總次數(shù)就是命中率。

平均時(shí)間：即CPU多次讀取數(shù)據(jù)時(shí)，命中和未命中時(shí)讀取數(shù)據(jù)的時(shí)間。

例1：設(shè)讀取一次Cache時(shí)間為1ns，讀取一次主存時(shí)間為1000ns，如果在CPU多次讀取數(shù)據(jù)過(guò)程中，有90%命中Cache，10%未命中，則CPU讀取一次的平均時(shí)間為：

磁盤(pán)

磁盤(pán)有正反兩個(gè)盤(pán)面，每個(gè)盤(pán)面有多個(gè)同心圓，每個(gè)同心圓是一個(gè)磁道，每個(gè)同心圓又被劃分為多個(gè)扇區(qū)，數(shù)據(jù)就被存放在一個(gè)個(gè)扇區(qū)中

磁盤(pán)示意圖

磁頭首先要尋找對(duì)應(yīng)的磁道，然后等待磁盤(pán)進(jìn)行周期旋轉(zhuǎn)，旋轉(zhuǎn)到指定的扇區(qū)，才能讀到對(duì)應(yīng)的數(shù)據(jù)，因此，會(huì)產(chǎn)生尋道時(shí)間和等待時(shí)間。公式為：存取時(shí)間=尋道時(shí)間+等待時(shí)間

尋道時(shí)間：指磁頭移動(dòng)到磁道所需的時(shí)間

等待時(shí)間：指等待讀寫(xiě)的扇區(qū)轉(zhuǎn)到磁頭下方所用的時(shí)間

磁盤(pán)調(diào)度算法

尋道時(shí)間耗時(shí)最長(zhǎng)，旋轉(zhuǎn)時(shí)間無(wú)法優(yōu)化

尋道時(shí)間的優(yōu)化算法

• 先來(lái)先服務(wù)FCFS：根據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤(pán)的先后順序進(jìn)行調(diào)度
• 最短尋道時(shí)間優(yōu)先SSTF：請(qǐng)求訪問(wèn)的磁道與當(dāng)前磁道最近的進(jìn)程優(yōu)先調(diào)度，使得每次的尋道時(shí)間最短。這個(gè)算法會(huì)產(chǎn)生饑餓現(xiàn)象，即遠(yuǎn)處進(jìn)程可能永遠(yuǎn)無(wú)法訪問(wèn)
• 掃描算法SCAN：又稱(chēng)電梯算法，磁頭在磁盤(pán)上雙向移動(dòng)，其會(huì)選擇離磁頭當(dāng)前所在磁道最近的請(qǐng)求訪問(wèn)的磁道，并且與磁頭移動(dòng)方向一致，磁頭永遠(yuǎn)都是從里向外或者從外向里一致移動(dòng)完才掉頭。
• 單向掃描調(diào)度算法CSCAN：與SCAN不同的是，CSCAN只做單向移動(dòng)，即只能從里向外或者從外向里。

例1：假設(shè)某磁盤(pán)的每個(gè)磁道劃分成11個(gè)物理塊，每個(gè)塊存放1個(gè)邏輯記錄。邏輯記錄R0，R1，...，R9，R10存放在同一個(gè)磁道上，記錄的存放順序如下表所示：

如果磁盤(pán)的旋轉(zhuǎn)周期為33ms，磁頭當(dāng)前處在R0的開(kāi)始處。若系統(tǒng)使用單緩沖區(qū)順序處理這些記錄，每個(gè)記錄處理時(shí)間為3ms，則處理這11個(gè)記錄的最長(zhǎng)時(shí)間為多少？若對(duì)信息存儲(chǔ)進(jìn)行優(yōu)化分布后，處理11個(gè)記錄的最少時(shí)間是多少？

解：處理這11個(gè)記錄的最長(zhǎng)時(shí)間為多少？

根據(jù)題述：一個(gè)磁道劃分位11個(gè)物理塊，每個(gè)塊存放1個(gè)邏輯記錄，則如下圖所示：

image.png

磁盤(pán)旋轉(zhuǎn)周期為33ms，則每個(gè)邏輯記錄的讀取時(shí)間為33/11=3ms

從R0開(kāi)始，每個(gè)記錄處理時(shí)間為3ms，則R0的讀取時(shí)間+處理時(shí)間，一共是6ms

由于R0讀取時(shí)間為3ms，而處理時(shí)，R1讀取完成后，緩沖區(qū)并沒(méi)有釋放，此時(shí)磁頭已經(jīng)移動(dòng)到R2的開(kāi)始處(即每次讀取時(shí)間+等待時(shí)間就會(huì)跳過(guò)一個(gè)邏輯記錄Rx)，但是按照條件必須按照順序執(zhí)行，即R0執(zhí)行完成后，需要等待一個(gè)周期才能執(zhí)行R1

此時(shí)得出：等待時(shí)間為：

R0的等待時(shí)間 = 3+3 = 6ms

R1的等待時(shí)間 = 33(讀取時(shí)間)+3(處理時(shí)間)=36ms

R2的等待時(shí)間 = 33(讀取時(shí)間)+3(處理時(shí)間)=36ms

......

依此類(lèi)推：11個(gè)記錄的最長(zhǎng)時(shí)間為：36*10+6 = 366ms

解：若對(duì)信息存儲(chǔ)進(jìn)行優(yōu)化分布后，處理11個(gè)記錄的最少時(shí)間是多少？

根據(jù)問(wèn)題，是想表達(dá)，既然每次讀取時(shí)間+處理時(shí)間剛好跳過(guò)那個(gè)順序執(zhí)行的塊，我們需要如何存儲(chǔ)能達(dá)到最優(yōu)效果？

那么我們應(yīng)該跳格存儲(chǔ)，即如下圖所示：

image.png

那么此時(shí)處理R0為6ms，剛好磁頭到達(dá)R1，處理R1為6ms，剛好到達(dá)R2......

依此類(lèi)推，則處理11個(gè)記錄為6*11=66ms

例2：在磁盤(pán)調(diào)度管理中，應(yīng)先進(jìn)行移臂操作，再進(jìn)行旋轉(zhuǎn)調(diào)度。假設(shè)磁盤(pán)移動(dòng)臂位于21號(hào)柱面上，進(jìn)程的請(qǐng)求序列如下表所示。如果采用最短移臂調(diào)度算法，那么系統(tǒng)的響應(yīng)序列應(yīng)為：

image.png

A.②⑧③④⑤①⑦⑥⑨

B.②③⑧④⑥⑨①⑤⑦

C.①②③④⑤⑥⑦⑧⑨

D.②⑧③⑤⑦①④⑥⑨

解：移臂操作=尋道操作、旋轉(zhuǎn)調(diào)度=磁道旋轉(zhuǎn)

此時(shí)采用最短移臂算法，即最短尋道時(shí)間優(yōu)先SSTF

21號(hào)柱面的下一個(gè)響應(yīng)序列應(yīng)該是23號(hào)柱面(離得最近)，表中23號(hào)柱面共有三個(gè)②③⑧【排除選項(xiàng)C】

為什么會(huì)有三個(gè)23號(hào)柱面，按照題述，23號(hào)柱面其實(shí)就是磁道，那么很明顯，這三個(gè)23號(hào)是同一個(gè)磁道，只是扇區(qū)不同

23號(hào)的下一個(gè)響應(yīng)序列則為17號(hào)，表中17號(hào)柱面共有三個(gè)①⑤⑦【排除選項(xiàng)AB】

因?yàn)?38肯定是在同一個(gè)磁道上，需要全部執(zhí)行完后才會(huì)找下一個(gè)磁道，下一個(gè)磁道157也會(huì)全部執(zhí)行完之后才會(huì)找下一個(gè)磁道

17號(hào)的下一個(gè)響應(yīng)序列應(yīng)該是32號(hào)，表中32號(hào)柱面共有兩個(gè)④⑥

32號(hào)的下一個(gè)響應(yīng)序列應(yīng)該是38號(hào)，表中38號(hào)柱面共有一個(gè)⑨

答案：D