大家好，我是冰河~~

最近發(fā)現(xiàn)很多小伙伴工作很久了，大部分工作都是在重復的進行CRUD，對于一些基礎性的知識，比如：計算機基礎知識，操作系統(tǒng)，數(shù)據(jù)結構和算法等，卻了解的少之又少。

其實，很多時候，這些基礎性的知識往往是造成程序員職業(yè)生涯瓶頸的一個重要的因素。所以，冰河強烈建議這些基礎知識越早知道越好，越早掌握越好！最好是在大學時期就充分掌握這些計算機基礎知識。

好了，接下來，冰河為大家總結了一篇萬字長文系統(tǒng)介紹計算機中有關數(shù)據(jù)方面的基礎知識。

數(shù)據(jù)的表示形式

在計算機中，所有的數(shù)據(jù)都是以二進制的形式進行表示的，也就是說，在計算機中使用0和1來表示所有的數(shù)據(jù)。而我們日常生活中的數(shù)字都是10進制的，那我們平時使用的數(shù)字如果在計算機中表示時就需要進行進制的轉換。

進制轉換

R進制轉10進制

R進制轉10進制可以使用按權展開的方法，具體的操作就是：將R進制數(shù)的每一位數(shù)值使用R^k^表示，底數(shù)是R，指數(shù)是k。

其中，k與該位和小數(shù)點之間的位置有關。當這個位置位于小數(shù)據(jù)左邊時，k的值是從小數(shù)點向左依次數(shù)的個數(shù)，需要注意的是：緊鄰小數(shù)點的數(shù)字位置為0，接下來是1,2...依次類推。同樣的，如果這個位置在小數(shù)點的右邊，則緊鄰小數(shù)據(jù)點位置的數(shù)字從-1開始，依次向右數(shù)為-2，-3等等，依此類推。

例如，我們給出一個二進制數(shù)字，11010101.01，轉換為10進制數(shù)字為：1 x 2^7^ + 1 x 2^6^ + 0 x 2^5^ + 1 x 2^4^ + 0 x 2^3^ + 1 x 2^2^ + 0 x 2^1^ + 1 x 2^0^ + 0 x 2^-1^ + 1 x 2^-2^。

圖片

再比如，我們給出一個八進制數(shù)，76128.01，轉換為10進制數(shù)字為：7 x 8^4^ +6 x 8^3^ + 1 x 8^2^ + 2 x 8^1^ + 8 x 8^0^ + 0 x 8^-1^ + 1 x 8^-2^

圖片

十進制轉R進制

十進制轉R進制就比較簡單了，這里我們可以使用短除法。

例如，將十進制數(shù)字69轉換為二進制的過程如下所示。

圖片

得出短除的結果后，我們需要將余數(shù)倒過來排列即為十進制69轉換為二進制的結果，所以結果數(shù)據(jù)為：1000101。

二進制與八進制互轉

二進制轉八進制時，每三位二進制數(shù)表示一個八進制數(shù)。因為在八進制中，總共有8個基數(shù)，分別是0~7，逢8進1。而如果要使用二進制來表示時，0的二進制為000，7的二進制為111，所以，每三位二進制數(shù)對應一位八進制數(shù)。反過來，每一位八進制數(shù)對應三位二進制數(shù)。

具體的劃分策略是，從二進制的低位開始，從低到高，也就是從右向左，每三位二進制數(shù)對應一個八進制數(shù)，不足三位的前面補0，例如，我們將二進制數(shù)：10001110轉化為八進制數(shù)的過程，具體如下所示。

圖片

所以，二進制數(shù)10001110轉化為八進制數(shù)的結果為216。

同理，八進制轉二進制與二進制轉八進制正好相反，八進制的每一位對應三位的二進制數(shù)。也就是說，將八進制數(shù)的每一位轉化成三位的二進制數(shù)即可。

二進制與十六進制互轉

在十六進制表示的數(shù)字中，總共有15個基數(shù)，為0~15，逢16進1。如果要將二進制數(shù)轉化為十六進制數(shù)時，首先要弄清楚每位十六進制數(shù)需要多少為二進制數(shù)表示。

在十六進制中，最大的基數(shù)為15,15的二進制表示為：1111，最小的基數(shù)為0,0的二進制數(shù)為0000，也就是說，十六進制的基礎使用二進制表示為 0000~1111，所以，每位十六進制數(shù)需要四位二進制數(shù)表示。

從二進制數(shù)的低位開始，也就是從右側開始，每四位二進制數(shù)對應一位十六進制數(shù)。

例如，我們需要將二進制數(shù)10001110轉換為十六進制數(shù)，如下所示。

圖片

注意：在十六進制中，分別使用A,B,C,D,E,F代表10,11,12,13,14,15。

所以，二進制10001110轉化為十六進制的結果為8E。

十六進制轉二進制與二進制轉十六進制正好相反，將十六進制的每一位轉換為四位二進制數(shù)即可。

數(shù)據(jù)的碼制

在計算機中，帶符號的機器數(shù)可以采用原碼、反碼、補碼和移碼表示，這些編碼稱為碼制。

原碼

在原碼表示中，最高位是符號位，0表示正號，1表示負號，其余的n-1位表示數(shù)值的絕對值，數(shù)值0的原碼有兩種表示形式：原 = 0 0000000，原  = 1 0000000。

反碼

在反碼中，最高位是符號位，0表示正號，1表示負號，正數(shù)的反碼與原碼相同，負數(shù)的反碼是其絕對值按位取反。數(shù)值0的反碼有兩種表示形式：反 = 0 0000000，反  = 1 1111111。

補碼

在補碼中，最高位是符號位，0表示正號，1表示負號，正數(shù)的補碼與原碼和反碼相同，負數(shù)的補碼等于其反碼的末位加1。在補碼的表示中，0有唯一的補碼：補  = 0 0000000，補  = 0 0000000。

移碼

移碼表示法是在數(shù)X上增加一個偏移量來定義的，常用于表示浮點數(shù)中的階碼。如果機器字長為n，規(guī)定偏移量為 2^n-1^。

實際上，在偏移 2^n-1^的情況下，只要將補碼的符號位取反就可以獲得相應的移碼。

碼制總結

我們來看下面的表格，這里，我直接使用八位的二進制數(shù)來表示相應的數(shù)值。

通過表格我們發(fā)現(xiàn)：

• 正數(shù)的原碼、反碼和補碼是相同的。
• 負數(shù)的反碼是原碼除符號位外，其他位分別取反；
• 負數(shù)的補碼是其反碼的末位加1。
• 移碼是在補碼的基礎上符號位取反得到。

在負數(shù)的原碼和補碼的轉換中，我們可以得出如下結論：

• 負數(shù)的原碼轉補碼是在原碼的基礎上除符號位外，其他位取反，然后末位加1。
• 負數(shù)的補碼轉原碼是在補碼的基礎上除符號位外，其他位取反，然后末位加1。

也就是說，負數(shù)的原碼轉補碼和補碼轉原碼的規(guī)則是一樣的。小伙伴們可以根據(jù)表格自行驗證

計算機使用補碼進行加減法運算

我們再來看表格的最后一列 1-1，在計算機中，表示為1+(-1)，其正確的結果應該為0。接下來，我們分別分析下使用原碼、反碼、補碼和移碼進行加減法運算的結果的正確性。

• 表格的第一行中，使用原碼計算的結果為1000 0010，轉換為10進制數(shù)為-2，1-1不等于-2，所以，使用原碼進行加減法運算的結果是錯誤的。
• 在反碼中，計算1-1的結果為1111 1111，顯然結果不為0，所以，使用反碼進行加減法運算的結果是錯誤的。
• 在補碼中，計算1-1的結果為0000 0000，結果為0，所以，使用補碼進行加減法運算的結果是正確的。
• 在移碼中，計算1-1的結果為1000 0000，結果為-0，雖然-0也等于0，但是嚴格意義來講，這個結果是不正確的。

在計算機中，不會使用移碼進行加減法運算，移碼用于浮點數(shù)的階碼。

數(shù)值的表示范圍

在計算機中，碼制所表示的范圍，可以分為定點整數(shù)和定點小數(shù)。在定點數(shù)中，小數(shù)點是固定的。定點整數(shù)就是說小數(shù)點在最低位的后面，也就是在最右面，此時的小數(shù)點可以忽略不寫。定點小數(shù)就是小數(shù)點在最高位的前面，也就是在最左邊。

值得注意的是：在定點整數(shù)和定點小數(shù)中，小數(shù)點都不占位數(shù)。所以，小數(shù)點在定點整數(shù)和定點小數(shù)中不會影響數(shù)值的范圍。

我們可以將定點整數(shù)和定點小數(shù)的取值范圍總結成下表所示。

表格中的n表示機器的字長，也就是用多少位二進制數(shù)表示。

這張表小伙伴們不用死記硬背，說白了，這張表，冰河也記不住，那我們怎么辦呢？不慌，這里，我給大家舉一個例子。

例如，我們這里使用4位機器字長來表示，為了理解方便，這里我用四個方框來表示4位二進制數(shù)。

圖片

默認最高位為符號位，如下所示。

圖片

這里我們先用4位二進制數(shù)表示定點整數(shù)，則最小值為1111，最大值為0111。

最小值1111表示如下。

圖片

其轉換成10進制數(shù)為-7。

最大值0111表示如下。

圖片

其轉換為10進制數(shù)為7。

這樣，我們使用4位二進制數(shù)表示的范圍，則可以計算出結果為：-7 ~ 7。也就是 -(2^4-1^ - 1)  ~ +(2^4-1^ -1)，所以，當使用n位二進制數(shù)表示數(shù)值的范圍時，我們可以得出數(shù)據(jù)的表示范圍為：-(2^n-1^ - 1)  ~ +(2^n-1^ -1)

所以，我們根本就不需要記住定點整數(shù)和定點小數(shù)的取值范圍表，只需要簡單的使用一個實際的二進制位進行驗算即可得出正確的結果數(shù)據(jù)。比如，我這里以4位二進制位進行驗算舉例。

還有一點需要注意的是：補碼和移碼比原碼和反碼少一個數(shù)，就是-0。另外，驗證定點小數(shù)和驗證定點整數(shù)的方式相同，小伙伴們可自行驗證定點小數(shù)的值，這里，我就不再贅述。

如果我們使用8位二進制數(shù)表示，則定點整數(shù)的取值范圍為：

1111 1111 ~ 0111 1111 轉換為十進制數(shù)就是：-127 ~ 127，將二進制數(shù)轉換為補碼為：1000 0000 ~ 0111 1111。

其中，-128的補碼為1000 0000是人為規(guī)定的。

如果使用8位二進制數(shù)表示，則定點小數(shù)的取值范圍為：

-0.1111 1111 ~ +0.11111111，補碼的范圍為：-1~ + +0.11111111。

其中，-1的補碼為1000 0000是人為規(guī)定的。

浮點數(shù)的運算

浮點數(shù)的表示

首先，我們先來看下浮點數(shù)的表示形式，浮點數(shù)的表示形式如下，

N = 尾數(shù) * 基數(shù)^指數(shù)^

對于浮點數(shù)來說，我們最常說的就是圓周率 π，數(shù)學上常使用3.14來表示π的值，如果使用科學計算法的話，我們可以使用形如3.14 * 10^3^ 這樣的數(shù)來表示。其中，在3.14 * 10^3^中，3.14表示尾數(shù)，10表示基數(shù)，3表示指數(shù)。

另外，3.14 * 10^3^ 可以寫成多種形式，比如可以寫成 0.314 *  10^4^，也可以寫成0.0314 *  10^5^。

浮點數(shù)的存儲格式

浮點數(shù)在計算機中的表示中，階碼是帶符號的純整數(shù)，尾數(shù)為帶符號的純小數(shù)。浮點數(shù)的表示格式如下所示。

一個數(shù)的浮點數(shù)表示不是唯一的。當小數(shù)點的位置發(fā)生改變時，階碼也會相應的改變。可以使用多個浮點形式表示同一個浮點數(shù)。浮點數(shù)的數(shù)值范圍主要由階碼決定，數(shù)值的精度則是由尾數(shù)決定的。

浮點數(shù)的運算過程

運算的過程要依次經歷對階、尾數(shù)計算和結果格式化三個階段。

例如計算：3.14 * 10^3^ + 1.5 * 10^5^的結果數(shù)據(jù)。

首先，我們需要先進行對階操作，這里有個原則就是小數(shù)向大樹看齊，這里我們需要將3.14 * 10^3^進行對階操作，轉化成0.0314 * 10^5^，然后與1.5 * 10^5^進行相加操作，得出結果數(shù)據(jù)1.5314 * 10^5^。

接下來，我們再來看看浮點數(shù)的特點。

浮點數(shù)的特點

浮點數(shù)的主要特點如下所示。

• 一般尾數(shù)使用補碼表示，階碼使用移碼表示。
• 階碼的位數(shù)決定數(shù)的表示范圍，位數(shù)越多范圍越大。
• 尾數(shù)的位數(shù)決定數(shù)的有效精度，位數(shù)越多精度越高。
• 對階時，小數(shù)向大數(shù)看齊。
• 對階是通過較小數(shù)的尾數(shù)右移實現(xiàn)的。

計算機結構

計算機結構主要由運算器、控制器、存儲器、輸入設備和輸出設備組成。簡化的結構圖如下圖所示。

圖片

接下來，我們再看看看其詳細的結構圖如下所示。

圖片

其中，主存儲器又叫做內存儲器，也就是內存；輔助存儲器又叫做輔存，也就是外存儲器，例如磁盤；CPU的核心部件為運算器和控制器。

CPU由運算器、控制器、寄存器組和內部總線組成。

運算器包含：算術邏輯單元、累加寄存器、數(shù)據(jù)緩沖寄存器、狀態(tài)條件寄存器。

• 算術邏輯單元（ALU）：數(shù)據(jù)的算術運算和邏輯運算。
• 累加寄存器（AC）：通用寄存器，為ALU提供一個工作區(qū)，用于暫存數(shù)據(jù)。
• 數(shù)據(jù)緩沖寄存器（DR）：寫內存時，暫存指令或數(shù)據(jù)。
• 狀態(tài)條件寄存器（PSW）：存儲狀態(tài)標志和控制標志，有時也可以將狀態(tài)條件寄存器歸為控制器部分。

控制器包含：程序計數(shù)器、指令寄存器、指令譯碼器、時序部件。

圖片

• 程序計數(shù)器（PC）：存儲下一條要執(zhí)行的指令的地址。
• 指令寄存器（IR）：存儲即將執(zhí)行的指令。
• 指令譯碼器（ID）：對指令中的操作碼字段進行分析解釋。
• 時序部件：提供時序控制信號。

計算機體系結構分類

首先，我們先來看一個在計算機領域中，對計算機的體系結構進行分類的一種經典方法，就是Flynn分類法，F(xiàn)lynn分類法將計算機分成單指令流單數(shù)據(jù)流、單指令流多數(shù)據(jù)流、多指令流單數(shù)據(jù)流、多指令流多數(shù)據(jù)流。

圖片

具體信息如下表所示。

指令的基本概念

一條指令就是機器語言的一個語句，它是一組有意義的二進制代碼，指令的格式如下所示。

其中，操作碼部分指出了計算機要執(zhí)行什么性質的操作，例如，加法、減法、取數(shù)、存數(shù)等。地址碼字段需要包含各操作數(shù)的地址及操作結果的存放地址等，從其地址結構的角度可以分為三地址指令、二地址指令、一地址指令和零地址指令。

三地址指令

例如，執(zhí)行a+b=c操作時，就是使用的三地址指令。此時如下所示。

圖片

二地址指令

圖片

例如，執(zhí)行a+=b操作時，執(zhí)行的就是二地址指令，此時如下所示。

圖片

一地址指令

圖片

例如，執(zhí)行a++操作時，執(zhí)行的就是一地址指令，此時如下所示。

零地址指令

例如，宕機就是零地址指令。

尋址方式

總體來說，尋址方式可以分為：立即尋址、直接尋址、間接尋址、寄存器尋址、寄存器間接尋址。

圖片

• 立即尋址：操作數(shù)直接在指令中，速度快，靈活性差。
• 直接尋址：指令中存放的是操作數(shù)的地址。
• 間接尋址：指令中存放了一個地址，這個地址對應的內容是操作數(shù)的地址。
• 寄存器尋址：寄存器存放操作數(shù)。
• 寄存器內存放的是操作數(shù)的地址。

CISC與RISC

CISC和RISC分別表示復雜指令集系統(tǒng)和精簡指令集系統(tǒng)，具體信息如下表所示。

如何比較CISC和RISC，分哪些維度？

指令數(shù)量、指令使用頻率、存執(zhí)方式、寄存器、流水線支持、高級語言支持。

• CISC：復雜、指令數(shù)量多，頻率差別大、多尋址。
• RISC：精簡、指令數(shù)量少。操作寄存器，單周期，少尋址，多通用寄存器，流水線，

流水線概念

流水線是指在程序執(zhí)行時，多條指令重疊進行操作的一種準并行處理的實現(xiàn)技術。各種部件同時處理是針對不同指令而言的，它們同時為多條指令的不同部分進行工作，以提高各部件的利用率和指令的平均執(zhí)行速度。

流水線的相關參數(shù)計算包括：流水線執(zhí)行時間計算、流水線吞吐率、流水線加速比、流水線效率。

圖片

在計算機中，對于指令的操作主要分為三個部分：取指、分析和執(zhí)行。如下所示。

圖片

如果執(zhí)行取值、分析和執(zhí)行各需要1ms的話，則串行執(zhí)行三條指令的時間總共需要9ms。這是因為一條執(zhí)行的操作需要經過取指、分析和執(zhí)行三個步驟，每個步驟需要1ms，執(zhí)行一條指令的時間為3ms，則串行執(zhí)行三條指令的時間為9ms。我們可以用下圖來表示這個過程。

圖片

在上圖的表示中，貌似執(zhí)行三條指令使用9ms是沒啥問題的。但是，如果我們把圖形改造一下，我們就會發(fā)現(xiàn)相應的問題。我們使用下面的圖形來表示執(zhí)行三條指令的情況。

此時，我們發(fā)現(xiàn)，在上圖執(zhí)行指令操作的過程中，有很多空白的格子，而空白的格子表示在執(zhí)行執(zhí)行的過程中有空余的時間片資源沒有利用起來。

很顯然，沒有必要等待指令1完全執(zhí)行完畢后再執(zhí)行指令2，同樣的，沒有必要等待指令2完全執(zhí)行完畢后再執(zhí)行指令3。而且，我們發(fā)現(xiàn)按照上圖執(zhí)行完三條指令需要9ms時間。

此時，如果將空余的時間片利用起來，則可以使用下圖來表示。

圖片

此時，在執(zhí)行三條指令的過程中，取指操作對指令1執(zhí)行完取指后，馬上對指令2進行取指，然后又馬上對指令3進行取指；分析操作同樣是對指令1執(zhí)行完分析后，馬上對指令2進行分析，然后又馬上對指令3進行分析；執(zhí)行操作也是對指令1執(zhí)行完畢后，馬上對指令2進行執(zhí)行操作，然后又馬上對指令3進行執(zhí)行操作。期間，將空余的時間片資源充分的利用起來了。

而且，我們發(fā)現(xiàn)，充分利用空余的時間片后，執(zhí)行三條指令的時間由原來的9ms變?yōu)楝F(xiàn)在的5ms。

從另一個角度，我們發(fā)現(xiàn)執(zhí)行完第一條指令時，需要3ms，執(zhí)行完第二條指令時，只需要在執(zhí)行完第一條指令的基礎上增加1ms。同樣的，執(zhí)行完第三條指令時，只需要在執(zhí)行完第二條指令的基礎上增加1ms。以后每增加一條指令，只需要增加1ms的時間便可以執(zhí)行完此條指令。

這就是計算機中的流水線技術。接下來，我們就說說流水線技術的相關計算問題。

流水線計算

關于流水線計算，我們先來看一個圖。

圖片

在上圖中，我們可以看出，執(zhí)行完第一條指令時，需要3ms時間，執(zhí)行完第二條指令時，只需要在執(zhí)行完第一條指令的基礎上增加1ms；執(zhí)行完第三條指令時，只需要在執(zhí)行完第二條指令的基礎上增加1ms。

以此類推，執(zhí)行完第n條指令時，只需要在執(zhí)行第n-1條指令的基礎上增加1ms。說到這里，不知道小伙伴們有沒有思考這樣一個問題，流水線技術的這種規(guī)律就涉及到一個非常重要的概念，叫作 流水線周期。

流水線周期為執(zhí)行時間最長的一段，上圖中的流水線周期為1ms

流水線的計算公式為：

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

流水線的理論公式如下所示。

(t1 + t2 + ... + tk) + (n-1) * △t

其中t1,t2...tk表示執(zhí)行一條指令的每個步驟分別需要的時間，n為指令的條數(shù)，△t為流水線周期。

流水線的實踐公式如下所示。

k*△t + (n-1) * △t

其中，k為執(zhí)行一條指令的步驟數(shù)，n為指令的條數(shù)，△t為流水線周期。

這里，給小伙伴們舉一個例子。

例如，一條執(zhí)行的執(zhí)行過程可以分解為取指，分析和執(zhí)行三步，在取指時間t取指=3△t，分析時間分析=2△t，執(zhí)行時間t執(zhí)行=4△t的情況下，若按照串行方式執(zhí)行，則10條指令全部執(zhí)行完需要多少△t？若按照流水線方式執(zhí)行，流水線周期為多少△t？使用流水線方式時，執(zhí)行完10條指令需要多少△t？

（1）串行方式比較簡單，就是將每條指令的執(zhí)行時間進行累加。

（3△t + 2△t + 4△t） * 10 = 90△t。

（2）在執(zhí)行一條指令的過程中，取指為3△t，分析為2△t，執(zhí)行為4△t。根據(jù)流水線中對于流水線周期的定義：流水線周期為執(zhí)行時間最長的一段，所以，流水線周期為4△t。

（3）使用流水線方式時，執(zhí)行完10條指令需要的時間可以使用如下方式進行計算。

這里，我們分別計算下理論時間和實踐時間。

• 理論時間

(3△t + 2△t + 4△t) + (10-1) * 4△t = 45△t。

• 實踐時間

3 * 4△t + (10-1) * 4△t = 48△t。

超標量流水線

關于超標量流水線，我們可以使用下圖來表示。

圖片

在超標量流水線中，有一個概念叫作度。度表示在超標量流水線中，由幾條流水線組成。例如上面的圖中，超標量流水線由兩條流水線組成，所以，度為2。此時的超標量流水線可以同時進行2個操作。

也就是說，可以同時執(zhí)行兩個取指操作，可以同時執(zhí)行兩個分析操作，也可以同時執(zhí)行兩個執(zhí)行操作。

如果此時有10條指令需要執(zhí)行，使用以上超標量流水線的話，只需要10 / 2 = 5 條指令的時間。

流水線吞吐率計算

流水線的吞吐率（TP）是指在單位時間內流水線所完成的任務數(shù)量或輸出的結果數(shù)量。計算流水線吞吐流程的最基本的公式如下所示。

圖片

流水線最大吞吐率計算公式如下所示。

圖片

流水線的吞吐率計算問題相對來說還是比較簡單的。

層次化存儲結構

首先，問小伙伴們一個問題：計算機的存儲結構為什么需要進行層次化的劃分呢？

說的直接一點：就是為了減少經濟成本。如果說，CPU的價格非常便宜的話，根本就不需要內存了?？梢园阉械膬却嫒萘咳慷甲龅紺PU里面去，就可以了。

但是，事實上，CPU的內存是很精貴的，至今為止，CPU中基本上還是一級緩存和二級緩存。三級緩存比較少見。而且，CPU中的存儲容量是非常小的，基本都是KB級別的存儲，CPU的內存容量也就幾KB，MB級別的CPU內存也是比較少見的。所以，出于經濟成本的考慮，計算機中的存儲結構是按照層次進行劃分的。

為了能夠讓小伙伴們更加清晰的理解層次化存儲結構，我們先來看一張圖。

圖片

由上圖，可以看出：

（1）層次化的存儲結構可以分為：CPU、Cache（高速緩存）、主存（內存）、外存（輔存）。

（2）從上往下，速度越來越慢，容量越來越大。

局部性原理是層次化存儲結構的支撐。

局部性原理

一個編寫良好的計算機程序常常具有良好的局部性。也就是說。它們傾向于引用臨近于其他最近引用過的數(shù)據(jù)項的數(shù)據(jù)項，或者最近引用過的數(shù)據(jù)項本身。這匯總傾向性，就被稱為局部性原理，這是一個持久的概念，對硬件和軟件系統(tǒng)的設計和性能都有著極大的影響。

之所以有這個規(guī)律，很多人認為原因是：程序的指令大部分時間是順序執(zhí)行的」，而且程序的集合，如數(shù)組等各種數(shù)據(jù)結構是連續(xù)存放的。

局部性原理講的是：在一段時間內，整個程序的執(zhí)行僅限于程序的某一部分，相應地，程序訪問的存儲空間也局限于某個內存區(qū)域。主要分為兩類：

圖片

• 時間局部性：如果程序中的某條指令一旦執(zhí)行，則不久之后該指令可能再次被執(zhí)行；如果某數(shù)據(jù)被訪問，則不久之后該數(shù)據(jù)可能再次被訪問。
• 空間局部性：是指一旦程序訪問了某個存儲單元，則不久之后，其附近的存儲單元也將被訪問。

Cache

針對Cache相關的技術，我們主要來聊聊Cache的概念和映像相關的技術。

Cache-概念

這里的Cache表示的是高速緩沖，在計算機的存儲體系系統(tǒng)中，Cache是除寄存器外訪問速度最快的層次。使用Cache改善系統(tǒng)性能的依據(jù)是程序的局部性原理 。

如果以h代表對Cache的訪問命中率，t1表示Cache的周期時間，t2表示主存儲器的周期時間，以讀操作為例，使用“Cache+主存儲器”的系統(tǒng)的平均周期為t3，則可以得出如下運算公式。

t3 = h * t1 + (1 - h) * t2

其中。(1 - h)又稱為失效率，也就是未命中率。

Cache-映像

Cache的映像分為三種，分別是：直接相聯(lián)映像、全相聯(lián)映像、組相聯(lián)映像。

圖片

• 直接相聯(lián)映像：硬件電路比較簡單，但沖突率最高。
• 全相連映像：電路難于設計和實現(xiàn)，只適用于小容量的Cache，沖突率比較低。
• 組相聯(lián)映像：直接相聯(lián)與全相聯(lián)的折中。

地址映像是將主存與Cache的存儲空間劃分為若干大小相同的頁（或稱為塊）。

例如，一臺計算機的主存容量為1GB，劃分為2048頁，每頁512KB；Cache的容量為8MB，劃分為16頁，每頁512KB。接下來，我們由此來詳細圖解直接相聯(lián)映像、全相聯(lián)映像和組相聯(lián)映像。

直接相聯(lián)映像

我們可以畫一組圖來表示Cache的直接映像。首先，我們先來簡單畫一個主存標記、Cache頁號和頁內地址的示意圖。如下所示。

圖片

如上圖所示，主存標記為7位，Cache頁號為4位，頁內地址為19位。

記錄主存區(qū)號的示意圖如下所示。

圖片

有了上面兩張圖的基礎后，我們再來看直接相聯(lián)映像的示意圖如下所示。

圖片

這里，我們將容量為1GB的主存劃分成2048頁，總共127個區(qū)，每頁的容量為512KB。將容量為8MB的Cache劃分為16頁，每頁容量為512KB。

所謂直接相聯(lián)映像是指Cache中的0頁只能存儲主存中0頁的內容，這里主存中0頁指的是每個區(qū)的0頁，比如上圖中的0區(qū)的0頁，1區(qū)的16頁，127區(qū)的2032頁等。

在直接相聯(lián)映像中，只需要記錄主存標記、Cache頁號和頁內地址就能夠快速的找到主存中的數(shù)據(jù)。

使用直接相聯(lián)映像有個缺點：那就是如果Cache中的0頁，存儲了主存中0區(qū)0頁的內容時，如果此時需要存儲主存1區(qū)中的16頁內容，就只能將主存0區(qū)中0頁的內容從Cache的0頁中清除，然后將主存1區(qū)中16頁的內容存儲到Cache中的0頁內。沖突率比較高。細心的小伙伴會發(fā)現(xiàn)：這其實是違背局部性原理的。

直接相聯(lián)映像訪問速度最快，但沖突率最高。

全相連映像

我們先來看下全相聯(lián)映像的主存頁標記和頁內地址的示意圖，如下所示。

圖片

此時，使用11位來標識主存頁標記，使用19位來標識頁內地址。

使用全相連映像需要記錄主存與Cache的對應關系，如下圖所示。

圖片

接下來，我們來看看全相連映像的示意圖，如下所示。

圖片

從圖中可以看出，Cache中的任何一個也，都可以存儲主存中的任何一個頁。

使用全相連映像訪問速度最慢，沖突率最低。

組相聯(lián)映像

組相聯(lián)映像本質上是直接相聯(lián)映像和全相聯(lián)映像的折中。同樣的，我們先來看組相連映像的存儲示意圖。

圖片

此時，在組相連映像中，Cache組號使用3位表示，組內頁號使用1位表示，頁內地址使用19位表示。其中，3位的Cache組號，1位的組內頁號和前面的7位構成了主存頁標記；3位的Cache組號，1位的組內頁號和19號的頁內地址構成了Cache地址。

接下來，我們再來看看主存與Cache的對應關系，如下圖所示。

圖片

組相連的映像示意圖如下所示。

圖片

由上圖可知，在組相連映像中，主存的組與Cache的組是組相聯(lián)映像關系，而在組內則是通過直接相聯(lián)映像來訪問和存儲數(shù)據(jù)。

主存編址與計算

這里，小伙伴們首先要區(qū)分兩個概念，一個是編址，一個是尋址。

編址： 存儲器是由一個個存儲單元構成的，為了對存儲器進行有效的管理，就需要對各個存儲單元編上號，即給每個單元賦予一個地址碼，這叫編址。經編址后，存儲器在邏輯上便形成一個線性地址空間。

尋址：存取數(shù)據(jù)時，必須先給出地址碼，再由硬件電路譯碼找到數(shù)據(jù)所在地址，這叫尋址。

編址可以分為兩種：按字編址和按字節(jié)編址。

圖片

• 按字編址：存儲體的存儲單元是字存儲單元，即最小尋址單位是一個字。
• 按字節(jié)編址：存儲體的存儲單元是字節(jié)存儲單元，即最小尋址單位是一個字節(jié)。

對于主存編址中最常見的計算形式為：根據(jù)存儲器所要求的容量和選定的存儲芯片的容量，就可以計算出所需要的芯片的數(shù)量。公式如下所示。

總片數(shù) = 總容量 / 每片的容量

這里，給小伙伴們舉一個例子：若內存地址區(qū)間為4000H ~ 43FFH，每個存儲單元可存儲16位二進制數(shù)，該內存區(qū)域使用4片存儲器芯片構成，則構成該內存所用的存儲器芯片的容量是多少？

解題思路也比較簡單，我們一起來看看如何解題：

（1）首先，我們來求解4000H ~ 43FFH地址空間的總容量，使用終止地址-起始地址+1即可得到總容量，也就是43FFH - 4000H + 1 = 43FFH + 1 - 4000H = 4400H - 4000H = 400H。

注意：在計算機中，以H結尾的數(shù)字是十六進制，逢16進1，而F在十六進制中表示15，所以，43FFH + 1 = 4400H。

所以，4000H ~ 43FFH地址空間的總容量為400H。

（2）接下來，我們要把400H轉換成二進制，對于十六進制數(shù)轉換成二進制數(shù)來說，每一位十六進制數(shù)對應著四位的二進制數(shù)，我們可以把400H拆分成4、0、0三部分，4轉換成二進制數(shù)就表示0100，十六進制的0轉換成二進制為0000。所以，400H轉換成二進制的結果為：0100 0000 0000。

0100 0000 0000也就是2的10次方，即為2^10^。

（3）題目中說的每個存儲單元可存儲16位二進制數(shù)，所有總共可以存儲的二進制數(shù)就是：2^10^ * 16。

（4）該區(qū)域使用4片存儲器芯片構成，所以，存儲芯片的容量為：2^10^ * 16 / 4 = 2^10^ * 4 = 2^12^，最終的結果單位為bit。

總線

一條總線同一時刻只允許一個設備發(fā)送數(shù)據(jù)，但允許多個設備接收數(shù)據(jù)。

總線的分類

總線可以分為數(shù)據(jù)總線、地址總線和控制總線。

圖片

• 數(shù)據(jù)總線（Data Bus）：在CPU和RAM之間來回傳送需要處理或是需要存儲的數(shù)據(jù)。
• 地址總線（Address Bus）：用來指定在RAM（Random Access Memory）之中存儲的數(shù)據(jù)的地址。
• 控制總線（Control Bus）：將微處理器控制單元（Control Unit）的信號傳送到周邊設備，一般常見的為USB Bus和1394 Bus。

串聯(lián)系統(tǒng)與并聯(lián)系統(tǒng)

這里，先給小伙伴們簡單介紹下什么是串聯(lián)系統(tǒng)，什么是并聯(lián)系統(tǒng)。

串聯(lián)系統(tǒng)

串聯(lián)系統(tǒng)是組成系統(tǒng)的所有單元中任一單元失效就會導致整個系統(tǒng)失效的系統(tǒng)。把用電器各元件逐個順次連接起來，接入電路就組成了串聯(lián)電路。我們常見的裝飾用的"滿天星"小彩燈，常常就是串聯(lián)的。

串聯(lián)電路有以下一些特點:

⑴電路連接特點:串聯(lián)的整個電路是一個回路，各用電器依次相連，沒有"分支點"。

⑵用電器工作特點:各用電器相互影響，電路中一個用電器不工作，其余的用電器就無法工作。

⑶開關控制特點:串聯(lián)電路中的開關控制整個電路，開關位置變了，對電路的控制作用沒有影響。即串聯(lián)電路中開關的控制作用與其在電路中的位置無關。

注：以上對于串聯(lián)系統(tǒng)的描述來源于網(wǎng)絡。

接下來，我們來看一個關于串聯(lián)系統(tǒng)的圖形表示，這里我們假設串聯(lián)系統(tǒng)中每個部分的可靠度依次為R1，R2，...Rn，如下所示。

圖片

則整個系統(tǒng)的可靠度為：R = R1 * R2 * ... * Rn。

并聯(lián)系統(tǒng)

并聯(lián)系統(tǒng)指的是組成系統(tǒng)的所有單元都失效時才失效的系統(tǒng)。把電路中的元件并列地接到電路中的兩點間，電路中的電流分為幾個分支，分別流經幾個元件的連接方式叫并聯(lián)。

并聯(lián)電路是使在構成并聯(lián)的電路元件間電流有一條以上的相互獨立通路，為電路組成二種基本的方式之一。例如，一個包含兩個電燈泡和一個9 V電池的簡單電路。若兩個電燈泡分別由兩組導線分開地連接到電池，則兩燈泡為并聯(lián)。

即若干二端電路元件共同跨接在一對節(jié)點之間的連接方式。這樣連成的總體稱為并聯(lián)組合。其特點是：

①組合中的元件具有相同的電壓；

②流入組合端點的電流等于流過幾個元件的電流之和；

③線性時不變電阻元件并聯(lián)時，并聯(lián)組合等效于一個電阻元件，其電導等于各并聯(lián)電阻的電導之和，稱為并聯(lián)組合的等效電導，其倒數(shù)稱為等效電阻

注：以上對于并聯(lián)系統(tǒng)的描述來源于網(wǎng)絡。

接下來，我們來看一個關于并聯(lián)系統(tǒng)的圖形表示，這里我們假設并聯(lián)系統(tǒng)中每個部分的可靠度依次為R1，R2，...Rn，如下所示。

圖片

則整個并聯(lián)系統(tǒng)的可靠度R = 1 - (1 - R1)  *  (1 - R2) * ... * (1-Rn)。

混合型系統(tǒng)

混合型系統(tǒng)就是既有串聯(lián)系統(tǒng)，又有并聯(lián)系統(tǒng)的系統(tǒng)，這里，我們也使用一個圖形進行表示，如下所示。

圖片

所以，上圖并聯(lián)系統(tǒng)的可靠度為：R * (1 - (1 - R) ^3^)  * (1 - (1 - R) ^2^)