軟考-數(shù)據(jù)庫系統(tǒng)工程師學習筆記

軟考-數(shù)據(jù)庫系統(tǒng)工程師

第1章計算機系統(tǒng)知識

計算機系統(tǒng)基礎知識

硬件及組成

一、計算機的組成

計算機硬件由5大件組成：控制器、運算器、存儲器、輸入設備、輸出設備

（1）運算器（ALU）:

也稱算術邏輯單元，對數(shù)據(jù)進行算術運算和邏輯運算

加法器（累加器）：

專門存放算術或邏輯運算的操作數(shù)和運算結果的寄存器。

程序狀態(tài)寄存器PSW：

用來存放兩類信息：一類是體現(xiàn)當前指令執(zhí)行結果的各種狀態(tài)信息，如有無進位（CY位），有無溢出（0V位），

結果正負（SF位），結果是否為零（ZF位），奇偶標志位（P位）等；另一類是存放控制信息，如允許中斷（IF位），

跟蹤標志（TF位）等

⑵控制器

是分析和執(zhí)行指令的部件

指令寄存器

用于保存當前正在執(zhí)行的指令

指令譯碼器

分析當前指令的操作碼是要做什么

程序計數(shù)器

存放下一條指令的地址

定時與控制電路

堆棧和堆棧指針

數(shù)據(jù)表示

一、數(shù)的進制

十進制：以D表示。如:（123）?；颍?23）io

二進制：以B表示。如：（1011）B或（101表2

八進制：以0（大寫o）表示。如:（301）。或（301）8

十六進制：以H表示。如：(13E)”或(13E)16

二、進制轉換

1.十進制轉非十進制

把被轉換的十進制整數(shù)反復地除以非十進制數(shù)，直到商為0,所得的余數(shù)(從末位讀起)就是這個數(shù)的非十進制表

示。簡稱“除*(*為非十進制數(shù))取余法”

2.非十進制轉十進制

方法：非十進制數(shù)按權展開求和

如：(10110)2=1*2'+0*23+1*22+1*2'+0*2=22

2

(335)8=3*8+3*8'+5*8=221

三、原碼、反碼、補碼、移碼

1.帶符號數(shù)的表示

通常的做法是約定一個數(shù)的最高位為符號位，若該位為0,則表示正數(shù)；若該位為1,則表示負數(shù)

(1)原碼

用最高位表示符號位，數(shù)值部分用二進制絕對值表示。

如：+11的原碼：0000如11,T1的原碼：10001011

(2)反碼

正數(shù)的反碼和其原碼形式相同，負數(shù)的反碼是除符號位，其他各位逐位取反(即0變1,1變0)

如：+11的反碼：00001011,T1的反碼:11110100

(3)補碼

正數(shù)的補碼和其原碼形式相同，負數(shù)的補碼是原碼除符號位以外逐位取反(即0變1,1變0),最后在末尾加1.

如：+11的補碼：0000如11,T1的補碼：11110101

將補碼轉換為真值：［［幻樸］撲=［如底

(4)移碼(增碼)

無論正數(shù)、負數(shù)，在補碼的基礎上對符號位取反，一般用做浮點數(shù)的階碼，引入的目的是為了保證浮點數(shù)的機器零

為全0

如：+11的補碼：0000如11,T1的補碼：11110101

+11的移碼:10001011,-11的移碼：01110101

四、定點數(shù)和浮點數(shù)

計算機中，通常是用定點數(shù)來表示整數(shù)和純小數(shù)，分別稱為定點整數(shù)和定點小數(shù)。對于既有整數(shù)部分又有小數(shù)部

分的數(shù)，一般用浮點數(shù)表示。

1.定點數(shù)

定點整數(shù)：

小數(shù)點的位置固定在最低位的右邊，不占位

定點小數(shù)：

小數(shù)點的位置固定在符號位與最高數(shù)值位之間，表示一個純小數(shù)

2.浮點數(shù)

用類似科學計算機法來表達，即

N=M*R°

M稱為尾數(shù)，R稱為基數(shù)，e為階碼（指數(shù)）

比如：1001.101的規(guī)范浮點數(shù)表達為1.001101+23

浮點數(shù)利用指數(shù)達到了浮動小數(shù)點的效果，從而靈活地表達更大范圍的實數(shù)

校驗碼

一、編碼體系

指一種編碼方式中所有合法碼字的集合

二、編碼效率

合法碼字占所有碼字的比率就是編碼效率。

三、碼距

碼距是衡量一種編碼方式的抗錯誤能力的一個指標

1.碼字的碼距

一個編碼系統(tǒng)中任意兩個合法的編碼之間的不同的二進制位的數(shù)目叫這兩個碼字的碼距

2.編碼系統(tǒng)的碼距

該編碼系統(tǒng)的任意兩個編碼之間的距離的最小值稱為該編碼系統(tǒng)的碼距

四、誤碼

數(shù)字信息在傳輸和存取的過程中，由于各種意外情況的發(fā)生，數(shù)據(jù)可能會發(fā)生錯誤，即所謂誤碼。

五、奇偶校驗

串口通信中使用奇偶校驗作為數(shù)據(jù)校驗的方法

使用一位奇偶校驗的方法能夠檢測出1位錯誤，但無法判斷是哪一位出錯。

當發(fā)生兩位同時出錯的情況時，奇偶校驗也無法檢測出來。所以奇偶校驗常用于對少量數(shù)據(jù)的校驗，如1個字節(jié)。

1.奇校驗：

被傳輸?shù)挠行?shù)據(jù)中“I”的個數(shù)是奇數(shù)個，校驗位填“0”，否則填“I”

2.偶校驗：

被傳輸?shù)挠行?shù)據(jù)中“1”的個數(shù)是偶數(shù)個，校驗位填“0”，否則填“1”。

X0R（異或運算）是一種偶校驗

六、海明碼

海明碼是奇偶校驗的一種擴充。和奇偶校驗的不同之處在于海明碼采用多位校驗碼的方式，在這些多個校驗位中

的每一位都對不同的信息數(shù)據(jù)位進行奇偶校驗，通過合理地安排每個校驗位對原始數(shù)據(jù)進行校驗的位組合，可以達到

發(fā)現(xiàn)錯誤、糾正錯誤的目的（當出現(xiàn)兩位錯誤時，海明碼能夠查錯，但無法糾錯）。

海明碼可以發(fā)現(xiàn)“爛碼距T"位的錯誤；可以糾正“〈碼距/2”位的錯誤，因此，如果要能夠糾正n位錯誤，所需

最小的碼距應該的2n-l

海明碼的原理

在數(shù)據(jù)中間加入幾個校驗碼，碼距均勻拉大，當某一位出錯，會引起幾個校驗位的值發(fā)生變化

海明不等式

校驗碼個數(shù)為k,可以表示2k個信息，1個信息用來表示“沒有錯誤”，其余211個表示數(shù)據(jù)中存在錯誤，如果

滿足2"T>=m+k（m為數(shù)據(jù)長度，m+k為編碼后的數(shù)據(jù)編碼總長度），則在理論上k個校驗碼就可以判斷是哪一位（包

括信息碼和校驗碼）出現(xiàn)了問題

海明碼的編碼規(guī)則

校驗位依次放在第2,（i=0,1,2,3…）位,其余位置為信息位。

B7B6B5B4B3B2Bl

k3k2klr2kOrlrO

7654321

上表4個信息位k0.kl,k2,k3,3個校驗位r0.rl.r2

第i個信息位的位數(shù)為參與校驗它的校驗位的位數(shù)之和。如上例7=4+2+1；6=4+2；5=4+1；3=2+1

從上式可得，k3要參與r2,rl和r0的生成，k2參與r2和rl的生成，kl參與r2和r0的生成，k0參與rl和r0

的生成。則產(chǎn)生下列式子"?”符號為異或運算

r0=k3?kl?k0-?k3?kl?k0?r0=0-?Bl?B3?B5?B7=0

rl=k3?k2?k0^k3?kl?k0?rl=0-?B2?B3?B6?B7=0

r2=k3?k2?kl-^k3十k2十kl十r2=0-B4?B5ffiB6?B7=0

若三個校驗方程都成立，即方程式右邊都等于0,則說明沒有出錯。若不成立，即方程式右邊不等于0.說明有……

從三個方程式右邊的值，可以判斷哪一位出錯。出錯位置為從下向上看相應的二進制數(shù)值，若三個程式右邊的值

為100(如下式)，說明第4位出錯。

B1十B3十B5十B7=0

B2?B3?B6?B7=0

B4十B5十B6十B7=l

七、循環(huán)冗余校驗碼

廣泛地在網(wǎng)絡通信及磁盤存儲時采用

循環(huán)冗余校驗碼的糾錯能力取決于K值(信息碼長度)和R值(校驗碼長度)，在實踐中，K值往往取得非常大,

遠遠大于R的值，提高了編碼效率。在這種情況下，循環(huán)冗余校驗就只能檢錯不能糾錯。

一般來說，R位生成多項式可檢測出所有雙錯、奇數(shù)位錯和突發(fā)錯位小于或等于R的突發(fā)錯誤。

1.多項式

在循環(huán)冗余(CRC)碼中，無一例外地要提到多項式的概念。

一個二進制數(shù)可以以一個多項式來表示。如1011表示為多項式X：'+X'+X",如果把這里的X替換為2,這個多項式的

值就是該數(shù)的值。從這個轉換可以看出多項式最高塞次為n,則轉換為二進制數(shù)有n+1位

2.生成多項式

生成多項式是接受方和發(fā)送方的一個約定，也就是一個二進制數(shù)，在整個傳輸過程中，這個數(shù)始終保持不變。

3.編碼組成

編碼的組成是由K位信息碼，加上R位的校驗碼

4.校驗碼的生成

生成步驟：

(1)將K位數(shù)據(jù)C(x)左移R位，給校驗位留下空間，得到移位后的多項式為C(x)*X)

(2)將這移位后的信息多項式除以生成多項式，得到R位的余數(shù)多項式。

(3)將余數(shù)作為校驗碼嵌入信息位左移后的空間

例：信息位為10100110,約定的生成多項式為1110011即X'+X'+X+l,則：

10100110左移5位一〉1010011000000

用1010011000000和11110011進行模2運算(異或)

余11000

即校驗碼11000,所以CRC碼是1010011011000

計算機體系結構

指令系統(tǒng)

指計算機所能執(zhí)行的全部指令的集合，它描述了計算機內(nèi)全部的控制信息和“邏輯判斷”能力.

一條指令包括：操作碼、地址碼(操作數(shù))

一、指令系統(tǒng)類別

1.根據(jù)地址碼區(qū)分

立即尋址：直接使用地址碼，地址碼就是一個數(shù)

直接尋址：地址碼是一個地址，需去內(nèi)存中取出該數(shù)

間接尋址：地址碼是一個地址，內(nèi)存中仍是一個地址，需再尋址一次

寄存器尋址：地址碼是一個寄存器的地址

寄存器間接尋址：地址碼是一個寄存器的地址的地址

二、復雜指令集計算機(CISC)與精簡指令集計算機(RISC)

1.復雜指令集計算機(CISC)

為提高操作系統(tǒng)的效率，人們最初選擇向指令系統(tǒng)中添加更多、更復雜的指令來實現(xiàn)，導致指令集越來越大。這種

類型的計算機，稱為指令集計算機(CISC)

主要特點

(1)指令數(shù)量多：指令系統(tǒng)擁有大量的指令，有100—250條

(2)指令使用頻率相關懸殊：最常使用的是一些比較簡單的指令，80%的時候使用的是20%的指令

(3)支持很多種尋址方式：通常為5—20種

(4)變長的指令：指令長度不是固定的，變長的指令增加指令譯碼電路的復雜性。

(5)指令可以對存儲器單元中數(shù)據(jù)直接進行處理：典型的CISC處理器通常都有指令能夠直接對內(nèi)存單元中的數(shù)據(jù)

進行處理，其執(zhí)行速度較慢

2.精簡指令集計算機(RISC)

對指令數(shù)目和尋址方式做精簡，指令的指令周期相同，采用流水性技術，指令并行執(zhí)行程度更好，這類是精簡指令

集計算機(RISC)

主要特點

(1)指令數(shù)量少：優(yōu)先選取使用頻率最高的一些簡單指令以及一些常用的指令，避免使用復雜指令

(2)指令的尋址方式少：通常只支持寄存器尋址方式、立即數(shù)尋址方式以及相對尋址方式。

(3)指令長度固定，指令格式種類少：因為RISC指令數(shù)量少，格式相對簡單，其指令長度固定，指令之間各字段的

劃分比較一致，譯碼相對容易。

(4)只提供了Load/Store指令訪問存儲器：只提供了從存儲器讀數(shù)Load和把數(shù)據(jù)定稿存儲器Store兩條指令，其

余所有操作都在CPU的寄存器間進行。

(5)以硬布線邏輯控制為主：為了提高操作的執(zhí)行速度，通常采用硬布線邏輯來構建控制器。

(6)單周期指令執(zhí)行：因為簡化了指令系統(tǒng)，很容易利用流水線技術使得大部分指令在一個機器周期內(nèi)完成。

(7)優(yōu)化的編譯器：RISC精簡指令集使編譯工作簡單化。

3.CISC和RISC的簡單對比

CISCRISC

指令條數(shù)多只選取最常見的指令

指令復雜度高低

指令長度變化固定

指令執(zhí)行周期隨指令變化大大多在一個機器同期完成

指令格式復雜簡單

尋址方式多極少

涉及訪問主存指令多極小，大部分只有兩條存指令

通用寄存器數(shù)量一般大量

譯碼方式微程序控制硬件電路

對編譯系統(tǒng)要求低高

三、流水線技術

在程序執(zhí)行時，多條指令重疊進程操作的一種任務分解技術。把一個任務分解為若干順序執(zhí)行的子任務，不同的

子任務由不同的執(zhí)行機構來負責執(zhí)行，而這些執(zhí)行機構可以同時并行工作。

流水線時間

建立時間、排空時間

1.計算機執(zhí)行時間

假定有某種類型的任務，可分成N個子任務，每個子任務需要時間t,則完成該任務所需的時間為N*t

若以傳統(tǒng)的方式，完成k個任務所需的時間是kNt。

使用流水線技術，花費的時間是Nt?+（k-l）t..

（Nt。為完成任務所需的時間，如果每個子任務所需的時間相同，t0=3如果每個子任務所需的時間不同，其時間3

取決于執(zhí)行順序中最慢的那一個）

2.流水線的吞吐率

在單位時間內(nèi)（一般為1秒）流水線所完成的任務數(shù)量或輸出的結果數(shù)量TP=n/l;（n為任務數(shù)，，是處理完成n

個任務所有的時間）

3.加速比

不采用流水線的執(zhí)行時間/采用流水線的執(zhí)行時間

用來衡量并行系統(tǒng)或程序并行化的性能和效果

4.影響流水線的主要因素

轉移指令：因為前面的轉移指令還沒有完成，流水線無法確定下一條指令的地址，因些也就無法向流水線中添加

這條指令

共享資源訪問的沖突：后一條指令需要使用的數(shù)據(jù)，與前一條指令發(fā)生沖突，或者相令的指令使用了相同的寄存

器

響應中斷：當有中斷請求時，流水線也會停止。對于這種情況有兩沖響應方式

精確斷點法：立即停止，這種方法能夠立即響應中斷

不精確斷點法：流水線中的指令繼續(xù)執(zhí)行，不再新增指令到流水線

存儲系統(tǒng)

存儲器是計算機系統(tǒng)中的記憶設備，用來存放程序和數(shù)據(jù)

一、存儲器分類

寄存器

Cache（高速緩沖存儲器）

主存儲器

輔存儲器

以上四個存儲器從下至上速度越來越快，容量越來越小，成本越來越高

二、存儲器的存取方式

存取方式讀/寫裝置數(shù)據(jù)塊標志訪問特性代表

共享讀/寫

順序存取無特定線性順序磁帶

裝置

共享讀/寫可直接移到特定數(shù)據(jù)

直接存取數(shù)據(jù)分塊，每塊一個唯一標志磁盤

裝置快

每個可尋址

隨時訪問任何一個存主存

隨機存取單元專有讀/寫每個可尋址單元均有一個唯一地址

儲單元儲器

裝置

相聯(lián)存取每個“J址

根據(jù)內(nèi)容需非地址來each

（屬隨機存單元專有讀/寫每個可尋址單元均有一個唯一地址

選擇讀寫點e

?。┭b置

三、存儲器的性能

1.存取時間

對于隨機存取而言，就是完成一次讀/寫所花的時間；對非隨機存取，就是將讀/寫裝置移動到目的位置所花的時

間

2.存儲器帶寬

每秒能訪問的位數(shù)。通常存儲器周期是納秒級（ns）。

計算公式：1/存儲器周期*每周期可訪問的字節(jié)數(shù)。即存儲器頻率*每周期可訪問的字節(jié)數(shù)

3.數(shù)據(jù)傳輸率

每秒輸入/輸出的位數(shù)。

對于隨機存取而言，傳輸率R=1/存儲器周期。即存儲器的頻率

四、主存儲器

主存儲器的種類

RAM：隨機存儲器

可讀/寫，只能暫存數(shù)據(jù)，斷電后數(shù)據(jù)丟失

SRAM：靜態(tài)隨機存儲器，在不斷電時信息能夠一直保持，讀寫速度快，生產(chǎn)成本高，多用于容量較小的高速緩沖存

儲器

DRAM：動態(tài)隨機存儲器，需要定時刷新以維持信息不丟失，讀寫速度較慢，集成度高，生成成本低，多用于容量較

大的主存儲器

ROM：只讀存儲器

出廠前用掩膜技術寫入，常用于存放BIOS和微程序控制

PROM：可編程ROM

只能夠一次寫入，需用特殊電子設備進行寫入

EPROM：可擦除的PROM

用某種方法可擦去信息，可寫入多次

E2PROM：電可擦除EPROM

可以寫入，但速度慢。

閃速存儲器（FlashMemory）

其特性介于EPRO.M與E2PROM之間。但不能進行字節(jié)級別的刪除操作

CAM（相聯(lián)存儲器）

CAM是一種特殊的存儲器，是一種基于數(shù)據(jù)內(nèi)容進行訪問的存儲設備。其速度比基于地址進行讀寫的方式要快

五、輔助存儲器

磁帶

磁帶是一種順序存取的設備。

特點：存儲容量大，價格便宜。適合數(shù)據(jù)的備份存儲。

磁盤

光盤

六、RAID（獨立磁盤冗余陣列）

把多個相對便宜的磁盤組合起來，成為一個磁盤組，配合數(shù)據(jù)分散排列的設計，提升數(shù)據(jù)的安全性和整個磁盤系

統(tǒng)效能。

利用多磁盤數(shù)據(jù)傳輸率

通過數(shù)據(jù)冗余與校驗實現(xiàn)可靠性。

1.RAID應用的主要技術

分塊技術、交叉技術和重聚技術

2.RAID0級（無冗余和無校驗的數(shù)據(jù)分塊）

RAID0原理是把連續(xù)的數(shù)據(jù)分散到多個磁盤上存取，數(shù)據(jù)請求被多個磁盤并行執(zhí)行，每個磁盤執(zhí)行屬于自己的那

部分數(shù)據(jù)請求。這種數(shù)據(jù)上的并行操作充分利用總線帶寬，顯著提高磁盤整體存取性能。

優(yōu)點：具有最高的I/O性能和最高的磁盤空間利用率，易管理。

缺點：不提供數(shù)據(jù)冗余，一旦數(shù)據(jù)損壞，損壞的數(shù)據(jù)將無法得到恢復.

3.RAID1級（磁盤鏡像陣列）

由磁盤對組成，每個工作盤都有其對應的鏡像盤，上面保存著與工作盤完全相同的數(shù)據(jù)拷貝，具有最高的安全性，

但磁盤空間利用率只有50雙RAID1主要用于存放系統(tǒng)軟件、數(shù)據(jù)及其他重要文件

4.RAID2級（采用糾錯海明碼的磁盤陣列）

RAID2采用海明碼糾錯技術，用戶增加校驗盤來提供糾錯和驗借功能，磁盤驅動器組中的第1、2、4……2"個磁盤

馱運器是專門的校驗盤，用于校驗和糾錯，其余的用于存放數(shù)據(jù)。RAID2最少要3臺磁盤驅動器方能運作。

5.RAID3級（采用帶奇偶校驗碼的并行傳送）

RAID3把數(shù)據(jù)分成多個“塊”，按照奇偶校驗算法存放在N+1個硬盤上，實際數(shù)據(jù)占用的有效空間為N個硬盤空

間的總和，第N+1個硬盤上存儲的數(shù)據(jù)是校驗容錯信息。

當N+1硬盤中的一個硬盤出現(xiàn)故障時，從其他N個硬盤中可以恢復原始數(shù)據(jù)。所以RAID3,安全性可以得到保障。

RAID3比較適合大文件類型且安全性要求較高的應用，如視頻編輯、硬盤播放機和大型數(shù)據(jù)庫等。

6.RAID4級（帶奇偶校驗的獨立磁盤結構）

它與RAID3很像，不同的是，它對數(shù)據(jù)的訪問是按數(shù)據(jù)塊進行的（一個數(shù)據(jù)塊是一個完整的數(shù)據(jù)集合，比如一個

文件就是一個典型的數(shù)據(jù)塊。一個數(shù)據(jù)塊存儲在一個磁盤上），也就是按磁盤進行的，每次是一個盤。RAID4使用一

塊磁盤作為奇偶校驗盤，每次寫操作都需要訪問奇偶盤，這時奇偶校驗盤成為寫操作的瓶頸。

7.RAID5級（無獨立校驗盤的奇偶校驗碼磁盤陣列）

RAID5把數(shù)據(jù)和奇偶校驗信息存儲到組成RAID5的各個磁盤上，并且奇偶校驗信息和相對的數(shù)據(jù)分別存儲于不同

的磁盤上。

當RATD5的一個磁盤數(shù)據(jù)損壞后，利用的數(shù)據(jù)和相應的奇偶校驗信息去恢復被損壞的數(shù)據(jù)。

RAID5磁盤空間利用率較高：（N-l）/N

RAID4和RAID5使用了獨立存取技術，陣列中每一個磁盤都相互獨立地操作，所以I/O請求可以并行處理。該技術

非常適合于I/O請求率高的應用，不太適用于要求高數(shù)據(jù)傳輸率的應用。

8.RAID6級（具有獨立的數(shù)據(jù)硬盤與兩個獨立的分布式校驗方案）

RAID6技術是在RAID5的基礎上，為進一步加強數(shù)據(jù)保護而設計的一種RAID方式，是一種擴展RAID5等級。

與RAID5的不同之處：除了每個硬盤上都有同級數(shù)據(jù)X0R（異或）校驗區(qū)外，還有一個針對每個數(shù)據(jù)塊的X0R校驗

區(qū)。當前盤數(shù)據(jù)塊的校驗數(shù)據(jù)不是存在當前盤而是交錯存儲的。每個數(shù)據(jù)塊有了兩個校驗保護，所以RAID6的數(shù)據(jù)冗

余性能相當好。

但是，由于增加了一個校驗，所以寫入的效率較RAID5還差，而且控制系統(tǒng)地更為復雜，第二塊的校驗區(qū)也減少

了有效存儲空間。

9.RAID10級

把RAID0和RAH）1技術結合起來，即RAID1+0是磁盤分段及鏡像的結合，結合了RAID0及RAID1的優(yōu)點。

它采用兩組RAID0的磁盤陣列互為鏡像，也就是它們之間又成為一個RAID1陣列。

七、Cache（高速緩沖存儲器）

高速緩存位于主存與CPU之間的一級存儲器，由靜態(tài)存儲芯片（SRAM）組成，容量比較小，速度比主存高得多，接

近于CPU的速度，單位成本比內(nèi)存高。Cache存儲了頻繁訪問內(nèi)存的數(shù)據(jù)。

l.Cache原理、命中率、失效率

使用Cache改善系統(tǒng)性能的主要依據(jù)是程序的局部性原理

（1）程序局部性原理

時間局部性

當前訪問的指令，不久的將來可能還會訪問

空間局部性

當前訪問了此條指令，有可能馬上會訪問它附近的指令

（2）命中率

訪問的指令能夠在Cache中找到，稱之為命中。單位時間內(nèi)在Cache中命中的數(shù)量與執(zhí)行指令的數(shù)量比稱為命中

率

Cache的訪問命中率為h（通常1-h就是Cache的失效率），Cache的訪問周期時間是tl,主存儲器的訪問周期時

間是t2,則整個系統(tǒng)的平均訪存時間就是：t3=h*tl+（l-h）*t2

2.Cache存儲器的映射機制

分配給Cache的地址存放在一個相聯(lián)存儲器（CAM）中。CPU發(fā)生訪存請求時，會先讓CAM判斷所要訪問的數(shù)據(jù)是

否在Cache中，如果命中就直接使用。這個判斷過程就是Cache地址映射，這個速度應該盡可能快?

常見的映射方法有：

直接映射

是一種多對一的映射關系，但一個主存塊只能夠復制到Cache的一個特定位置上去。

Cache的行號i和主存的塊號j有函數(shù)關系：i=j%m（其中m為Cache總行數(shù)）

例：某Cache容量為16KB（可用14位表示），每行的大小為16B（即可用4位表示）,則說明其可分為1024行

（可用10位表示）。主存地址的低4位為Cache的行內(nèi)地址，中間10位為Cache行號。

如果內(nèi)存地址為1234E8F8IL那么最后4位就是1000（對應十六進制數(shù)的最后一位），而中間10位,則應從E8F（1110

10001111）中獲取,得到101000Hilo內(nèi)存地址為中34E8F8H的單元裝入的Cache地址為10100011111000

全相聯(lián)映射

將主存中任一主存塊能映射到Cache中任意行（主存塊的容量等于Cache行容量）。

根據(jù)主存地址不能直接提取Cache頁號，而是將主存塊標記與Cache各頁的標記逐個，直到找到標記符合的頁（訪

問Cache命中），或者全部比較完后仍無符合的標記（訪問Cache失?。?。

主存塊標記與Cache各頁的標記逐個比較，所以這種映射方式速度很慢，失掉了高速緩存的作用，這是全相聯(lián)映

射方式的最大缺點。如果讓主頁標記與各Cache標記同時比較，則成本太高。

組相聯(lián)映射

是前兩種方式的折中方案。它將Cache中的塊再分成組，各組之間是直接映像，而組內(nèi)各塊之間則是全相聯(lián)映像。

主存地址=區(qū)號+組號+組內(nèi)塊號+塊內(nèi)地址號

例：容量為64塊的Cache采用組相聯(lián)方式映射，字塊大小為128個字，每4塊為一組。若主存容量為4096塊，

且以字編址，那么主存地址應該為多少位？主存區(qū)號為多少位？

首先根據(jù)主存塊與Cache塊的容量必須一致，得出內(nèi)存塊的大小也是128個字，因此共有128*4096個字，即

2|9（27*2日個字，因此需19位主存地址；其中：塊內(nèi)地址號為7位，以表示128個字。一組為4塊，則組內(nèi)塊號用2位

表示。Cache容量為64塊，共分16組，故組號需要4位地址表示。剩余的即為區(qū)號，為6位。

3.Cache淘汰算法

當Cache數(shù)據(jù)已滿，并且出現(xiàn)未命中情況時，就要淘汰一些老的數(shù)據(jù)，更新一些新的數(shù)據(jù)進入Cache。選擇淘汰哪

些數(shù)據(jù)的方法就是淘汰算法。常見的方法有三種：

隨機淘汰算法

先進先出淘汰算法（FIFO）

最近最少使用淘汰算法（LRU）

其中平均命中率最高的是LRU算法

4.Cache存儲器的寫操作（與主存同步的問題）

在使用Cache時，需要保證其數(shù)據(jù)與主存一致，因此在寫Cache時就要考慮與主存間的同步問題，通常使用以下

三種算法：

寫直達：當Cache寫命中時，Cache與主存同時發(fā)生寫修改

寫回：當CPU對Cache寫命中時，只修改Cache的內(nèi)容而不立即寫入內(nèi)存，當此行被換出才寫回主存

標記法：數(shù)據(jù)進入Cache后，有效位置1；當CPU對該數(shù)據(jù)修改時:數(shù)據(jù)只寫入主存并將該有效位置0.當要

從Cache中讀取數(shù)據(jù)時要測試其有效位，若為1則直接從Cache中取數(shù)，否則從主存中取數(shù)。

I/O控制方式

一、程序I/O方式（程序查詢方式，已淘汰，基本不用）

由于早期計算機無中斷機構，處理機對I/O設備的控制采取程序I/O方式，或稱為忙一等待方式，即在處理機向

控制器發(fā)送一條I/O指令啟動輸入設備輸入數(shù)據(jù)時,要同時把狀態(tài)寄存器中的忙/閑標志置為1。然后便不斷測試標志。

當為I時，表示輸入機尚未輸完一個字，處理機應繼續(xù)對該標志測試，直到它為o,表明數(shù)據(jù)已輸入到控制器的數(shù)據(jù)寄

存器中，于是處理機將數(shù)據(jù)取出送入內(nèi)存單元，便完成了一個字的I/O。

在程序I/O方式中，由于CPU高速，I/O設備低速致使CPU極大浪費。

二、中斷驅動I/O方式

當某進程要啟動某個I/O設備時，便由CPU向相應的設備控制器發(fā)出一條I/O命令，然后立即返回繼續(xù)執(zhí)行原來

的任務。設備控制器于是按照命令的要求去控制指定的I/O設備。這時CPU與I/O設備并行操作。

中斷驅動方式在I/O設備輸入數(shù)據(jù)的過程中，無需CPU干預，而是當I/O設備準備就緒時“主動”通知CPU。才需

CPU花費極短的時間去進行中斷處理。從而大大地提高了整個系統(tǒng)的資源利用率及吞吐量，特別是CPU的利用率。但每

次中斷一次僅能傳輸一個字（節(jié)）。

三、直接存儲器訪問DMAI/O控制方式

雖然中斷方式比程序I/O方式更有效，但它仍是以字（節(jié)）為單位進行I/O的，每當完成一個字（節(jié)）的I/O時，

控制器便要請求一次中斷。極其低效的。因此引入了直接存儲器訪問方式。

該方式的特點是：數(shù)據(jù)傳輸?shù)幕締挝皇菙?shù)據(jù)塊；所傳送的數(shù)據(jù)是從設備直接送入內(nèi)存的，或者相反；僅在傳送一

個或多個數(shù)據(jù)塊的開始和結束時，才需CPU干預，整塊數(shù)據(jù)的傳送是在控制器的控制下完成的?？梢奃MA方式又是成

百倍地減少了CPU對I/O的干預，進一步提高了CPU與I/O設備的并行操作程度

四、I/O通道控制方式

I/O通道是一種特殊的處理機。它具有執(zhí)行I/O指令的能力，并通過執(zhí)行通道（I/O）程序來控制I/O操作。但I/O

通道又與一般的處理機不同，一是其指令類型單一，只能執(zhí)行I/O操作有關的指令；二是通道沒有自己的內(nèi)存，與CPU

共享內(nèi)存。

根據(jù)信息交換方式，通道分為三種類型：

字節(jié)多路通道（ByteMultiplexorChannel）

數(shù)組選擇通道（BlockSelectorChannel）

數(shù)組多路通道（BlockMultiplexorChannel）

安全性、可靠性與性能評測

數(shù)據(jù)安全與保密

一、加密體系

1.對稱密碼體制

對稱密碼體制又稱為秘密密鑰體制（私鑰密碼體制），加密和解密采用相同的密鑰（或者可以通過一個推導出另

一個）。優(yōu)點：加密速度快，通常用來加密大批量的數(shù)據(jù)。缺點：需要管理的密碼多。

常見的對稱密鑰技術

DES：是一種迭代的分組密碼，輸入/輸出都是64位，使用一個56位的密鑰和附加的8位奇偶校驗位。攻擊DES

的主要技術是窮舉。由于DES的密鑰長度較短，為了提高安全性，出現(xiàn)了使用112位密鑰對數(shù)據(jù)進行三次加密的算

法，稱為3DES。

IDEA算法：其明文和密文都是64位，密鑰長度為128位

2.非對稱密鑰技術（公鑰算法）

非對稱密鑰技術是指加密密鑰和解密密鑰完全不同，并且不可能從任何一個推導出另一個。

優(yōu)點：適應開放性的使用環(huán)境，可以實現(xiàn)數(shù)字簽名與驗證。

最常見的非對稱密鑰技術是RSA。它的理論基礎是數(shù)論中大素數(shù)分解極其困難。

使用RSA來加密大量的數(shù)據(jù)則速度太慢，因此RSA廣泛用于密鑰的分發(fā)、數(shù)字簽名中。

二、身份認證技術與數(shù)字簽名

數(shù)字簽名就是只有信息的發(fā)送者才能產(chǎn)生的別人無法偽造的一段數(shù)字串，這段數(shù)字串同時也是對信息的發(fā)送者發(fā)

送信息真實性的一個有效證明。數(shù)字簽名使用了公鑰加密領域的技術實現(xiàn)，用于鑒別數(shù)字信息的方法。一套數(shù)字簽

名通常定義兩種運算，一個用于簽名，另一個用于驗證

1.數(shù)字簽名算法：

Hash簽名DSS簽名RSA簽名

2.數(shù)字簽名原理：

(1)發(fā)送者首先將原文用Hash函數(shù)生成128位的消息摘要。

(2)發(fā)送者用自己的私鑰對摘要再加密，形成數(shù)字簽名，把加密后的數(shù)字簽名附加在要發(fā)送的原文后面。

(3)發(fā)送者將原文和數(shù)字簽名同時傳給對方。

(4)接收者對收到的信息用Hash函數(shù)生成新的摘要，同時用發(fā)送者的公開密鑰對消息摘要解密。

(5)將解密后的摘要與新摘要對比，如兩者一致，則說明傳送過程中信息沒有被破壞或篡改。

三、數(shù)字證書

CA是數(shù)字證書的簽發(fā)機構，它是PKI的核心。CA是負責簽發(fā)證書、認證證書、管理已頒發(fā)證書的機關。

CA要制定政策和具體步驟來驗證、識別用戶身份，并對用戶證書進行簽名，以確保證書持有者的身份和公鑰的擁

有權。

CA是可以信任的第三方

數(shù)字證書的內(nèi)容CA《A》=CA{V,SN,Al,CA,UCA,A,UA,Ap,Ta)

V---證書版本號

SN--證書序列號

AI--用于對證書進行簽名的算法標識

CA--簽發(fā)證書的CA機構的名字

UCA--簽發(fā)證書的CA的惟一標識符

A-用戶A的名字

UA--用戶A的惟一標識

Ap--用戶A的公鑰

Ta--證書的有效期

四、電子商務安全

1.SSL(端口號443)

SSL(安全套接層協(xié)議)及其繼任者TLS(傳輸層安全協(xié)議)是一種安全協(xié)議，為網(wǎng)絡通信及數(shù)據(jù)完整性提供安全保障。

SSL和TLS是工作在傳輸層的安全協(xié)議，在傳輸層對網(wǎng)絡連接進行加密。

SSL協(xié)議可分為兩層

SSL記錄協(xié)議(SSLRecordProtocol)

它建立在可靠的傳輸協(xié)議(如TCP)之上，為高層協(xié)議提供數(shù)據(jù)封裝、壓縮、加密等基本功能的支持。

SSL握手協(xié)議（SSLHandshakeProtocol）

它建立在SSL記錄協(xié)議之上，用于在實際的數(shù)據(jù)傳輸開始前，通訊雙方進行身份認證、協(xié)商加密算法、交換加密

密鑰等。

2.SET（SecureElectronicTransaction,安全電子交易）協(xié)議

SET協(xié)議稱為安全電子交易協(xié)議。美國Visa和MasterCard兩大信用卡組織共同制定了應用于Internet上的以

銀行卡為基礎進行在線交易的安全標準一SET。

它采用公鑰密碼體制和X.509數(shù)字證書標準，保障網(wǎng)上購物信息的安全性。

3.HTTPS（安全套接字層上的超文本傳輸協(xié)議）

是以安全為目標的HTTP通道，簡單講是HTTP的安全版。

HTTPS是工作在應用層的協(xié)議。

4.PGP

PGP是一個基于RSA公鑰加密體系的郵件加密軟件。

PGP可用于文件存儲的加密。

PGP承認兩種不同的證書格式：PGP證書和X.509證書。

可靠性評價

一、可靠性計算

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

各個子系統(tǒng)的可靠性分別用RI,R2,…，Rn表

示

系統(tǒng)的可靠性為：R=R1XR2….XRn

系統(tǒng)的失效率為：X=X1+入2+…+An

入=1/MTBF（平均無故障時間）

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

假如一個系統(tǒng)由2個子系統(tǒng)組成，只要有一個子系統(tǒng)能夠正常工作，系統(tǒng)就能正常工作，設系統(tǒng)各個子系統(tǒng)的可

靠性用RLR2，…,Rn表示

系統(tǒng)的可靠性為：R=1-（1-RI）X（1-R2）義…X（1-Rn）

系統(tǒng)的失效率為：〃=―二（公式中n為子系統(tǒng)數(shù)量）—七二------

L1111

—V---------------H?,|---------------

△幺j?出

3.模冗余系統(tǒng)

m模冗余系統(tǒng)由m個（m=2n+l為奇數(shù)）相同的子系統(tǒng)和一個表決器組成，經(jīng)過表決器表決后，m個子系統(tǒng)中占多

數(shù)相同結果的輸出作為系統(tǒng)的輸出。

m模冗余系統(tǒng)的可靠性為：￡c：禺a(chǎn)-凡用一'、

sM--------r*，j—4-**)―

ml

第2章數(shù)據(jù)結構

線性結構

線性表

一、線性表

1、線性表定義

線性表是n個元素的有限序列，通常記為表1,a2,…，an)。

特點：

存在惟一的表頭和表尾。

除了表頭外，表中的每一個元素均只有惟一的直接前驅。

除了表尾外，表中的每一個元素均只有惟一的直接后繼。

2.線性表的存儲結構

(1)順序存儲

是用一組地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素，從而使得邏輯關系相鄰的兩個元素在物理位置上也相鄰。

優(yōu)點：可以隨機存取表中的元素

缺點：插入和刪除操作需要移動大量的元素。

在線性表的順序存儲結構中，第i個元素ai的存儲位置為：LOC(ai)=LOC(al)+(i-l)XL其中LOC(al)是表中第一

個元素的存儲位置，L是表中每個元素所占空間的大小。

(2)鏈式存儲

鏈式存儲是指用結點來存儲數(shù)據(jù)元素，結點的空間可以是連續(xù)的，也可以是不連續(xù)的，因此存儲數(shù)據(jù)元素的同時必須

存儲元素之間的邏輯關系。

結點空間只有在需要的時候才申請，無須事先分配。

優(yōu)點：插入和刪除操作不需要移動元素，操作方便。數(shù)據(jù)域指針域

缺點：增加了存儲空間開銷，不能隨機訪問任一結點。

其他幾種鏈表結構

(1)雙向鏈表：每個結點包含兩個指針，指明直接前驅和直接后繼元素，可在兩個方向上遍歷鏈表。

(2)循環(huán)鏈表：表尾結點的指針指向表中的第一個結點，可在任何位置上開始遍歷整個鏈表。

(3)靜態(tài)鏈表：借助數(shù)組來描述線性表的鏈式存儲結構。

3.線性表的插入和刪除運算

(1)基于順序存儲結構的運算

插入元素前要移動元素以挪出空的存儲單元，然后再插入元素。

刪除元素時同樣需要移動元素，以填充被刪除出來的存儲單元。

(2)基于鏈式存儲結構的運算

在鏈式存儲結構下進行插入和刪除，其實質是對相關指針的修改。

二、棧

棧是只能通過一端來實現(xiàn)數(shù)據(jù)存儲和檢索的一種線性表。

棧進行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。

棧的修改是按先進后出的原則進行的。又稱為先進后出的線性表。

棧的存儲結構

棧的存儲結構有順序存儲和鏈式存儲。

棧的順序存儲

是指用一組地址連續(xù)的存儲單元依次存儲自棧頂?shù)綏５椎臄?shù)據(jù)元素，同時附設指針top指示棧頂元素的位置。

棧的鏈式存儲

用鏈表作為存儲結構的棧也稱為鏈棧。由于棧中元素的插入和刪除僅在棧頂一端進行，因此不必設置頭結點，鏈

表的頭指針就是棧頂指針。

三、隊列

隊列是一種先進先出(FIFO)的線性表，它只允許在表的一端插入元素，而在表的另一端刪除元素。

在隊列中，允許插入元素的一端稱為隊尾(rear),允許刪除元素的一端稱為隊頭(front)。

也..一>2^

A

隊列的存儲結構

隊列的存儲結構有順序存儲和鏈式存儲兩種。

隊列的順序存儲結構

是利用一組地址連續(xù)的存儲單元存放隊列中的元素。由于隊列中元素的插入和刪除限定在隊列的兩端進行，因此

設置隊頭指針和隊尾指針，分別指示當前的隊首元素和隊尾元素。

隊列鏈式存儲

用鏈表表示的隊列簡稱為鏈隊列。

為了便于操作，給鏈隊列添加一個頭結點，并令頭指針指向頭結點.隊列為空的判定條件是：頭指針和尾指針的值

相同，且均指向頭結點。

四、串

串是僅由字符構成的有限序列，是取值范圍受限的線性表。

一般記為$='ala2...an',其中S是串名，ala2…an是串值。

1.串的幾個基本概念

空串

長度為零的串，空串不包含任何字符。

空格串

由一個或多個空格組成的串。

子串

由串中任意長度的連續(xù)字符構成的序列。含有子串的串稱為主串。子串在主串中的位置指子串首次出現(xiàn)時，該子

串的第一個字符在主串中的位置。空串是任意串的子串。

如:主串:abcbcc子串：cb

串相等

指兩個串長度相等且對應位置上的字符也相同.

串比較

兩個串比較大小時以字符的ASCH碼值作為依據(jù)。比較操作從兩個串的第一個字符開始進行，字符的ASCH碼值

大者所在的串為大，若其中一個串先結束，則以串長較大者為大。

幾個關鍵的ASCH碼

a97

A65

0(數(shù)字)48

2.串的存儲結構

每個字符串的最后要增加個串結束標志\0。

(1)串的順序存儲

用一組地址連續(xù)的存儲單元來存儲串值的字符序列。

(2)串的鏈式存儲

當用鏈表存儲串中的字符時，每個結點中可以存儲一個字符，也可以存儲多個字符，要考慮存儲密度問題。

樹和二叉樹

樹

樹是n(n20)個結點的有限集合，n=0時稱為空樹,

在任一非空樹中有且僅有一個稱為根的結點。其余的結點可分為m（m2O）個互不相交的子集Tl,T2…，Tm,其中

每個子集本身又是一棵樹，并稱其為根結點的子樹。

一、樹的基本概念

雙親和孩子

兄弟：

具有相同雙親的結點互為兄弟。

結點的度：

一個結點的子樹的個數(shù)記為該結點的度。

樹的度：

樹中各結點的度的最大值

葉子結點：

也稱為終端結點，指度為零的結點。

內(nèi)部結點：

度不為零的結點稱為分支結點或非終端結點。除根結點之外，分支結點也稱為內(nèi)部結點。

結點的層次：

根為第一層，根的孩子為第二層，依此類推。

樹的高度：

一棵樹的最大層次數(shù)記為樹的高度（或深度）。

有序（無序）樹：

若將樹中的結點的各子樹看成是從左到右具有次序的，即不能交換，則稱該樹為有序樹，否則稱為無序樹。

森林：

是m(m2O)棵互不相交的樹的集合

二、樹的存儲結構

標準存儲結構

結點的數(shù)據(jù)

指向子結點的指針

帶逆存儲結構

結點的數(shù)據(jù)

指向子結點的指針

指向其父結點的指針

三、樹的遍歷

遍歷是指對樹中所有結點信息的訪問，即依次對樹中每個結點訪問一次且僅訪問一次。

如下圖：

前序遍歷ABEFIJCDGII

后序遍歷EIJFBCGHDA

層次遍歷ABCDEFG11IJ

樹是沒有中序遍歷的，中序遍歷使用于二叉樹

二叉樹

二叉樹(BinaryTree)是n(nNo)個結點的有限集合，它或者是空樹(n=0),或者是由一個根結點及兩棵互不相交

的、分別稱為左子樹和右子樹的二叉樹所組成。

二叉樹與樹的區(qū)別：

二叉樹的結點的最大度為2,而樹中不限制結點的度。

二叉樹的結點的子樹要區(qū)分左子樹和右子樹

二叉樹可以為空，即沒有結點，樹至少有一個結點。

一、二叉樹的性質

(1)二叉樹第i層上的結點數(shù)目最多為2iT(i2l)。

(2)深度為k的二叉樹至多有2k-1個結點(kel)。

(3)在任意一棵二叉樹中，若終端結點數(shù)為nO,度為2的結點數(shù)為n2,則n0=n2+l。

(4)具有n個結點的完全二叉樹的深度為Llog2n」+1。(“L」”該符號為取下限整數(shù))

(5)對一棵有n個結點的完全二叉樹的結點按層次自左至右進行編號，小

則對任一結點i有：

若i=l,則結點i是二叉樹的根，無雙親，若i>l,則其雙親為Li/2JojQ

若2i>n,則結點i無左孩子，否則其左孩子為2i。0>5)0Q

若2i+i>n,則結點i無右孩子，否則其右孩子為2i+i。

(6)若深度為k的二叉樹有2k-1個結點，則稱其為滿二叉樹。深度90S)

為k、有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹編號從1至n的結點一一對應時，稱之

為完全二叉樹。

二、二叉樹的存儲結構

1.順序存儲結構

對完全二叉樹既簡單又節(jié)省空間，而對于一般二叉樹則不適用。

2.鏈式存儲結構

由于二叉樹中結點包含有數(shù)據(jù)元素、左子樹根、右子樹根及雙親等信息，因此可以用三叉鏈表或二叉鏈襲來存儲

二叉樹。鏈表的頭指針指向二叉樹的根結點。

3.二叉樹的遍歷

前序遍歷421356(先訪問根、再訪問左子樹、最后右子樹)

中序遍歷123456(先左子樹、再訪問根、最后右子樹)

后序遍歷132654(先左子樹、后右子樹、最后根)

二叉排序樹(二叉查找樹)

定義：或者是一棵空樹，或者是具有下列性質的二叉樹：

(1)若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

(2)若右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值;

(3)左、右子樹也分別為二叉排序樹；

平衡二叉樹(AVL樹)

具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1,并且左右兩個子樹都是一棵平衡

線索樹

n個結點的二叉鏈表中含有n+l(2n-(n-l)=n+l)個空指針域。利用二叉鏈表中的空指針域，存放指向結點在某種

遍歷次序下的前趨和后繼結點的指針(這種附加的指針稱為"線索")。

最優(yōu)二叉樹

給定n個權值作為n的葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹,

也稱為哈夫曼樹(Huffmantree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。

圖

圖的定義

圖G是由兩個集合V和E構成的二元組，記作G=(V,E),其中V是圖中頂點的非空有限集合，E是圖中邊的有限集合。

有向圖：圖G中的每條邊都是有方向的，頂點間的關系用＜vi,vj＞表示:

無向圖：圖G中的每條邊都是無方向的；頂點間的關系用(vi,vj)表示;

完全圖：圖G任意兩個頂點都有一條邊相連接；

有向完全圖：n個頂點的有向圖有n(n-l)條邊。

無向完全圖：n個頂點的無向圖有n(n-l)/2條邊。

有向完全圖

一、度

頂點v的度是與它相關聯(lián)的邊的條數(shù)。記作TD(v)。

入度

是以v為終點的有向邊的條數(shù)，記作ID(v)；

出度

是以v為始點的有向邊的條數(shù)，記作OD(v)0在有向圖中頂點的度等于該頂點的入度與出度之和。

二、帶權圖

即邊上帶權的圖。其中權是指每條邊標上的具有某種含義的數(shù)值(即與邊相關的數(shù))。

三、連通圖

在無向圖中，若從頂點V1到頂點\，2有路徑，則稱頂點V1與V2是連通的。如果圖中任意一對頂點都是連通的,

則稱此圖是連通圖。無向圖G=（V,E）是連通的，那么邊的數(shù)目大于等于頂點的數(shù)目減1

強連通圖

在有向圖中，若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,

則稱此圖是強連通圖

四、生成樹（最小生成樹）

是一個極小連通子圖，它含有圖中全部n個頂點，但只