目錄

計算機系統(tǒng)漫游

Amdahl定理

信息的表示和處理

信息存儲

進制轉(zhuǎn)化

小端法

大端法

布爾代數(shù)

位級運算

邏輯運算

移位運算

整數(shù)表示

無符號數(shù)編碼

補碼編碼

有符號數(shù)和無符號數(shù)之間的轉(zhuǎn)換

擴展數(shù)的位表示

截斷數(shù)字

整數(shù)運算

無符號加法

無符號數(shù)求反

有符號整數(shù)加法

補碼的非

無符號乘法

補碼乘法

浮點數(shù)

小數(shù)換算

IEEE浮點表示

舍入

浮點數(shù)加法

浮點數(shù)乘法

程序的機器級表示

訪問信息

寄存器訪問

數(shù)據(jù)傳送指令

算數(shù)和邏輯操作

算法和邏輯運算指令

特殊算術(shù)操作

控制

條件碼

跳轉(zhuǎn)指令

實現(xiàn)條件分支if-else

條件傳送指令

do-while循環(huán)

while循環(huán)

for循環(huán)

Switch

過程

存儲器層次結(jié)構(gòu)

存儲技術(shù)

存儲器

磁盤結(jié)構(gòu)

磁盤容量

磁盤訪問?編輯

局部性

局部性原理:

存儲器層次結(jié)構(gòu)?編輯

高速緩存?編輯

緩存不命中

Cache映射

鏈接

編譯器驅(qū)動程序

編譯過程

靜態(tài)鏈接與動態(tài)鏈接

目標文件

可重定位目標文件

符號和符號表

符號解析

靜態(tài)庫鏈接

重定位

加載可執(zhí)行目標文件

動態(tài)鏈接共享庫

《計算機系統(tǒng)（2）》學習筆記

葉茂林 2023.6.24-2023.6.30

計算機系統(tǒng)漫游

Amdahl定理

對系統(tǒng)某部分的加速時，其對系統(tǒng)整體性能的影響程度取決于該部分工作的所占的比重和加速程度。

系統(tǒng)為加速時所需時間為Told，某部分處理所占比例為α，該部分性能提升倍數(shù)為κ。即該部分工作需要α*Told時間，性能提升后需要α*Told/ κ。

那么新的處理時間為：Tnew=（1- α）Told+α*Told/κ=Told[（1-α）+α/κ]

加速比：S = 1/ ((1 ? α) + α/k)

信息的表示和處理

信息存儲

進制轉(zhuǎn)化

十六進制轉(zhuǎn)換為二進制：

通過展開每個十六 進制數(shù)字，將其轉(zhuǎn)換為二進制格式

十六進制數(shù)0x173A4C

二進制轉(zhuǎn)換為十六進制：

首先將二進制數(shù)字分為每4位一組來轉(zhuǎn)換為十六進制。如果位總數(shù)不是4的倍數(shù)，最左邊的一組可以少于4位，前面用0補足。

二進制數(shù)11 1100 1010 1101 1011 0011

十六進制轉(zhuǎn)換為十進制：

用相應的16的冪次方乘以每個十六進制數(shù)字。

十六進制數(shù)0x7AF

十進制轉(zhuǎn)換為十六進制：

除以十六取余。

314156

十六進制數(shù)為：0x4CB2C

字數(shù)據(jù)大小

字長：指明指針數(shù)據(jù)的大小。

對于一個字長為w位的機器而言，虛擬地址的范圍為0~2w -1，程序最多訪問2w個字節(jié)。

小端法

小端序是指機器選擇在內(nèi)存中按照從最低有效字節(jié)到最高有效字節(jié)的順序存儲對象。

以一個位于 0x100 處，類型為 int，十六進制值為 0x01234567 的變量為例。其中 0x01 是最高位有效字節(jié)，0x67 是最低位有效字節(jié)。

小端法：低位數(shù)在低地址，x86機器，Intel兼容機，Google的Android，Apple的iOS。

大端法

大端序是指機器選擇在內(nèi)存中按照從最高有效字節(jié)到最低有效字節(jié)的順序存儲對象。

以一個位于 0x100 處，類型為 int，十六進制值為 0x01234567 的變量為例。其中 0x01 是最高位有效字節(jié)，0x67 是最低位有效字節(jié)。

大端法：低位數(shù)在高地址，IBM機器。

ARM微處理器：雙端法。

布爾代數(shù)

以二元集合{0，1}或{TRUE(真)，F(xiàn)ALSE(假)}基礎(chǔ)上定義的代數(shù)

位級運算

邏輯運算

C語言中提供了一組邏輯運算符||、&&和！，分別對應于OR、AND和NOT 運算。

所有非零的參數(shù)都表示TRUE，參數(shù)零表示FALSE。

返回1來表示結(jié)果為TRUE，返回0來表示結(jié)果為FALSE。

移位運算

左移：在右端補0。

算術(shù)右移：在左端補最高有效位。

邏輯右移：在左端補0。

整數(shù)表示

無符號數(shù)編碼

補碼編碼

Umax、Tmin和TMax

求一個數(shù)的補碼表示

有符號數(shù)和無符號數(shù)之間的轉(zhuǎn)換

當表達式同時含有有符號數(shù)和無符號數(shù)的時候，在同位長的情況下，默認將有符號數(shù)強制轉(zhuǎn)換為無符號數(shù)進行運算。

強制類型轉(zhuǎn)換的結(jié)果保持位值不變，只是改變了解釋位值的方式，即位表示是一樣的，改變的只是解釋方式。

補碼轉(zhuǎn)換為無符號數(shù)

無符號數(shù)轉(zhuǎn)換為補碼

擴展數(shù)的位表示

無符號數(shù)零擴展：位開頭添加0。

有符號數(shù)補碼符號位擴展：位開頭添加最高有效位的值。

運算時，先改變位大小，再完成有符號到無符號的轉(zhuǎn)換。

截斷數(shù)字

截斷無符號數(shù)：直接丟棄高位。

截斷有符號數(shù)：先當成無符號數(shù)截斷，再當成有符號數(shù)。

整數(shù)運算

無符號加法

直接丟棄最高進位如果當前位數(shù)無法表示和。

無符號數(shù)求反

有符號整數(shù)加法

補碼的非

無符號乘法

補碼乘法

浮點數(shù)

小數(shù)換算

整數(shù)部分除二取余，小數(shù)部分乘二取整。

IEEE浮點表示

V=(-1)s×M×2E

符號s：s=1表示負數(shù)，s=0表示正數(shù)。

尾數(shù)（fraction）M：范圍[1,2)或者[0,1)。

階碼（exp）E：對浮點數(shù)加權(quán)，2的E次冪。

舍入

IEEE規(guī)定了四種舍入方式，分別為：向0舍入、向下舍入、向上舍入以及向偶數(shù)舍入。

默認向偶數(shù)舍入。

浮點數(shù)加法

階碼對齊，尾數(shù)右移相加

1.010*22 + 1.110*23= (0.1010 + 1.110)*23

= 10.0110 * 23

= 1.0011 * 24

= 1.010 * 24

浮點數(shù)乘法

程序的機器級表示

訪問信息

寄存器訪問

對寄存器低四位賦值時，高四位自動清零。

三種數(shù)據(jù)尋址方式：

立即數(shù)、寄存器、內(nèi)存引用。

數(shù)據(jù)傳送指令

等大小

不等大小，零擴展

不等大小，符號擴展

彈棧和出棧

算數(shù)和邏輯操作

算法和邏輯運算指令

特殊算術(shù)操作

兩個64位數(shù)的全128運算

指令中只給出一個操作數(shù)，另一操作數(shù)：乘法%rax，除法%rdx:%rax

隱含目的操作數(shù)：乘法 %rdx:%rax，除法商%rax、余數(shù)%rdx

控制

條件碼

條件碼(condition code)寄存器，其值描述最近的算術(shù)或邏輯操作的屬性。

CF (Carry Flag): 進位標志（無符號數(shù)的溢出）

ZF(Zero Flag): 結(jié)果為零標志

SF(Sign Flag): 符號標志，結(jié)果為負時SF=1

OF(Overflow Flag): 溢出標志，正溢出或負溢出

以下指令只改變標志位。

訪問條件碼

跳轉(zhuǎn)指令

實現(xiàn)條件分支if-else

條件傳送指令

當傳送條件滿足時，把S復制到目的R。

do-while循環(huán)

while循環(huán)

第一種方法，先跳轉(zhuǎn)到測試

第二種方法，先測試再開始do-while循環(huán)

for循環(huán)

先初始化，然后變成while循環(huán)

Switch

Switch語句可以通過if-else語句來實現(xiàn)，事實上也是如此，當情況的數(shù)量少于4個時，switch語句將翻譯為if-else語句，當超過4個情況時，并且值的范圍跨度比較小時就會使用跳轉(zhuǎn)表

過程

運行時棧

棧的作用：過程參數(shù)、返回地址、寄存器保存（用于修改后恢復，現(xiàn)場保存）、局部變量。

轉(zhuǎn)移控制

支持調(diào)用和返回的指令

call指令：返回地址入棧，跳轉(zhuǎn)到所指的地址——被調(diào)用過程的起始地址。

返回地址：調(diào)用結(jié)束后的下一條指令的地址。

ret指令：從棧中彈出一個地址，跳轉(zhuǎn)到該地址。

過程數(shù)據(jù)存儲

數(shù)組

指針運算

int E[18]

數(shù)據(jù)對齊

以結(jié)構(gòu)體中最長元素類型為對齊。

在機器級程序中將控制與數(shù)據(jù)結(jié)合起來

理解指針

存儲器層次結(jié)構(gòu)

存儲技術(shù)

存儲器

隨機訪問存儲器

cache是靜態(tài)RAM，不用刷新。

內(nèi)存是動態(tài)RAM，靠電容有無存儲的電荷來表示1和0，電荷會因漏電而消失，因此需要刷新。

磁盤存儲

磁盤結(jié)構(gòu)

• 磁盤由雙面的盤片組成
• 每張盤面上密集地排布著環(huán)形磁道
• 每條磁道上有多個扇區(qū)，每個扇區(qū)由間隙隔開

• 對齊的磁道形成一個柱面

磁盤容量

• 容量: 可存儲的最多比特數(shù)
  • 銷售商以10進制度量存儲大小，即1 GB = 109 Bytes
• 容量參數(shù)
  • 記錄密度(位/英寸):
    • 一英寸磁道可存儲的比特數(shù)
  • 磁道密度 (道/英寸):
    • 一英寸半徑可排布的磁道數(shù)
  • 面密度 (位/平方英寸):
    • 記錄密度與磁道密度的乘積

容量 =(字節(jié)數(shù)/扇區(qū))×(平均扇區(qū)數(shù)/磁道)×(磁道數(shù)/盤面)×(盤面數(shù)/盤片)×(盤片/磁盤)

磁盤訪問

• 訪問某個扇區(qū)的平均時間為 :
  • 訪問時間 ?=? 尋道時間 +? 旋轉(zhuǎn)時間 + 數(shù)據(jù)傳輸時間
• 尋道時間
  • 磁頭由一個柱面移動到另一個柱面的時間
  • 通常尋道時間為： 3—9 ms
• 旋轉(zhuǎn)時間
  • 經(jīng)過磁盤旋轉(zhuǎn)，目標扇區(qū)到達磁頭下的時間
  • 最大旋轉(zhuǎn)延遲 =? 1/RPMs x 60 sec/1 min
  • 平均旋轉(zhuǎn)延遲 = 0.5 x 最大旋轉(zhuǎn)延遲
  • 通常旋轉(zhuǎn)時間 = 7200 RPMs
• 數(shù)據(jù)傳輸時間
  • 傳輸每個扇區(qū)所需時間
  • 數(shù)據(jù)傳輸時間 = 1/RPM x 1/(平均扇區(qū)數(shù)/磁道) x 60 秒/1 分鐘.

磁盤訪問時間示例

• 給定條件:
  • 旋轉(zhuǎn)速度 = 7,200 RPM
  • 平均尋道時間 = 9 ms.
  • 平均扇區(qū)數(shù)/磁道 = 400.
• 計算結(jié)果:
  • 平均旋轉(zhuǎn)時間 = 1/2 x (60 secs/7200 RPM) x 1000 ms/sec ≈ 4 ms.
  • 數(shù)據(jù)傳輸時間 = 60/7200 RPM x 1/400 secs/track x 1000 ms/sec ≈ 0.02 ms
  • 服務總時間? = 9 ms + 4 ms + 0.02 ms = 13.02 ms
• 重點:
  • 訪問時間主要由尋道時間和旋轉(zhuǎn)時間組成.
  • 訪問扇區(qū)的第一個bit比較消耗時間，剩余bit較快.
  • SRAM 訪問時間為 4 ns/雙字, DRAM 為 60 ns/雙字
    • 磁盤比SRAM慢4,0000倍,
    • 磁盤比 DRAM慢2500倍.

局部性

局部性原理:

程序傾向于使用最近一段時間，距離其較近地址的數(shù)據(jù)和指令。

時間局部性:

最近被訪問的數(shù)據(jù)或指令在未來可能還會被訪問。

空間局部性:

當前訪問地址附近的區(qū)域在不久還有可能被訪問。

存儲器層次結(jié)構(gòu)

高速緩存

緩存不命中

• 冷不命中(或強制性不命中)
  • 由于高速緩存開始為空并且這是對塊的第一次引用，所以發(fā)生冷不命中。
• 容量不命中
  • 當一組活動緩存塊（工作集）大于緩存時發(fā)生
• 沖突不命中
  • 大多數(shù)高速緩存將第k+1層的某個塊限制放置在第k層塊的一個小的子集中（有時只是一個塊）
    • 例如，第k+1層的塊i必須放置在第k層的塊（i mod 4）中
  • 當?shù)趉層的緩存足夠大，但多個數(shù)據(jù)對象映射到同一個緩存塊中時發(fā)生沖突不命中
    • 例如，每次引用塊0, 8, 0, 8, 0, 8, ... 都會錯過

Cache的命中率：在一個程序執(zhí)行期間，設Nc表示cache完成存取的總次數(shù)，Nm表示主存完成存取的總次數(shù)，h定義為命中率。

?

平均訪問時間：若tc表示命中時的Cache訪問時間，tm表示未命中時的主存訪問時間，1-h表示未命中率，則Cache/主存系統(tǒng)的平均訪問時間ta為 ta= h tc + (1 - h) tm

• 某計算機系統(tǒng)的內(nèi)存儲器由cache和主存構(gòu)成，cache的存取周期為45ns，主存的存取周期為200ns。已知在一段給定的時間內(nèi)，CPU共訪問內(nèi)存4500次，其中340次訪問主存。問：
  • Cache的命中率是多少？
  • Cpu訪問內(nèi)存的平均時間是多少納秒？
  • Cache-主存系統(tǒng)的效率是多少？

解：

1、cache的命中率

• h=Nc/(Nc+Nm)=（4500-340）/4500=0.92

2、cpu訪存的平均時間

• ta=htc+(1-h)tm=0.92 ×45+(1-0.92) ×200=57.4[ns]

3、cache-主存系統(tǒng)的效率

• e=tc/ ta=45/57.4=0.78=78%

Cache映射

把主存空間劃分成大小相等的主存塊（Block）。

Cache中存放一個主存塊的對應單位稱為槽（Slot）或行（line），有書中也稱之為塊（Block），有書稱之為頁（page）（不妥?。?。

將主存塊和Cache行按照以下三種方式進行映射

直接相聯(lián)(Direct)：每個主存塊映射到Cache的固定行。

全相聯(lián)(Full Associate)：每個主存塊映射到Cache的任一行。?

組相聯(lián)(Set Associate)：每個主存塊映射到Cache固定組中任一行。

鏈接

編譯器驅(qū)動程序

編譯過程

預處理

預處理是在編譯之前的一個階段，它主要負責處理源代碼中的預處理指令。預處理器會根據(jù)預處理指令進行相應的處理，最常見的預處理指令是以"#"開頭的指令，如包含文件指令（#include）、宏定義指令（#define）等。預處理器會根據(jù)這些指令將相應的代碼插入到源代碼中，生成被處理過的新的源代碼文件。

編譯

編譯是將預處理過后的源代碼翻譯成匯編語言的過程。編譯器會對源代碼進行詞法分析、語法分析和語義分析等操作，然后將源代碼轉(zhuǎn)換成中間代碼或者匯編代碼。中間代碼是一種機器無關(guān)的代碼表示形式，而匯編代碼則是與特定的硬件平臺相關(guān)聯(lián)的低級代碼。

匯編

匯編是將匯編代碼轉(zhuǎn)化為機器碼的過程。匯編器將匯編代碼逐行翻譯成與特定處理器相關(guān)的二進制指令，這些指令可以被計算機直接執(zhí)行。每個匯編語句通常對應著一條機器指令，包括操作碼和操作數(shù)等。

鏈接

鏈接是將多個目標文件與庫文件鏈接在一起，形成最終的可執(zhí)行文件。在編寫復雜程序時，往往會將不同的源代碼文件分別編譯成目標文件，然后通過鏈接器將這些目標文件以及所需的庫文件鏈接在一起。鏈接器會解析目標文件之間的引用關(guān)系，將它們合并成一個完整的可執(zhí)行文件。在鏈接過程中，還會進行地址分配、重定位和符號解析等操作。

靜態(tài)鏈接與動態(tài)鏈接

完成兩個任務：符號解析與重定位。

符號解析：

建立符號引用和定義之間的聯(lián)系。

重定位：

為每一個引用確定地址。

鏈接時間：編譯時、加載時、運行時。

目標文件

可重定位目標文件 (.o)

其代碼和數(shù)據(jù)可和其他可重定位文件合并為可執(zhí)行文件，每個.o 文件由對應的.c文件生成，每個.o文件代碼和數(shù)據(jù)地址都從0開始。

可執(zhí)行目標文件 (默認為a.out)

包含的代碼和數(shù)據(jù)可以被直接復制到內(nèi)存并被執(zhí)行，代碼和數(shù)據(jù)地址為虛擬地址空間中的地址。

共享的目標文件 (.so)

特殊的可重定位目標文件，能在裝入或運行時被裝入到內(nèi)存并自動被鏈接，稱為共享庫文件，Windows 中稱其為 Dynamic Link Libraries (DLLs)。

可執(zhí)行可鏈接格式

Executable and linkable format，ELF。

可重定位目標文件

.text：已編譯程序的機器代碼。

.rodata：只讀數(shù)據(jù)。

.data：已初始化的全局和靜態(tài)C變量。

.bss：未初始化的全局和靜態(tài)C變量，以及所有被初始化為0的全局或靜態(tài)變量。

.symtab：符號表，存放函數(shù)和全局變量的信息。

.rel.text：文本部分的重新定位信息，修改指令的地址。

.rel.data：數(shù)據(jù)段的重新定位信息，修改指針數(shù)據(jù)的地址。

符號和符號表

全局符號

由本模塊定義并且能被其他模塊引用的，對應于非靜態(tài)的函數(shù)和全局變量。

外部符號

由其他模塊定義并且能被本模塊引用的，對應于在其他模塊定義的非靜態(tài)函數(shù)和全局變量。

局部符號

只能被本模塊定義和引用的局部符號，對應于靜態(tài)函數(shù)和全局變量。

符號解析

作用

將每個符號引用與它輸入的可重定位目標文件的符號表中的一個確定的符號定義關(guān)聯(lián)起來。

強符號

函數(shù)和已經(jīng)初始化的全局變量。

弱符號

未初始化的全局變量。

規(guī)則

• 不允許存在同名強符號。
• 如果強符號和弱符號同名，選擇強符號。
• 如果弱符號同名，任意選擇一個弱符號。

靜態(tài)庫鏈接

靜態(tài)庫

定義

將相關(guān)可重定位目標模塊打包成一個單獨的文件。

數(shù)據(jù)結(jié)構(gòu)：

維護三個動態(tài)變化的集合E、U和D

E：可重定位目標文件集合，被引用的目標文件將被拷貝到可執(zhí)行文件中；

U：隨著鏈接的展開而發(fā)現(xiàn)的未解析的符號集合，成功鏈接后最終該集合為空；

D：所有輸入文件中已解析的符號集合；

算法要點：

1）初始化E/U/D為空；

2）逐個掃描命令行給出的文件f；

a）f是目標文件: E = E U {f}，D = D U {f中的已定義符號}，

?????? 重定位表項對應的符號與D進行匹配，未匹配的加入到U；

b）f是靜態(tài)庫，將U中的符號與f定義的符號相匹配，存在匹配模塊m上的符號，E = E U {m}，否則丟棄該庫。

3）掃描結(jié)束

U非空：鏈接失敗，將U未能解析的符號輸出給用戶。

U為空，鏈接成功，布局E中模塊拼接成可執(zhí)行文件，完成符號解釋和重定位。

重定位

重定位由兩步組成：重定位節(jié)和符號定義，重定位節(jié)中的符號引用。

重定位節(jié)和符號定義

賦予指令和全局變量唯一的運行時內(nèi)存地址。

重定位節(jié)中的符號引用

修改代碼節(jié)和數(shù)據(jù)節(jié)中符號的引用，使其指向正確的運行地址。

可執(zhí)行目標文件

加載可執(zhí)行目標文件

了解LINUX運行時存儲器映像。

動態(tài)鏈接共享庫

靜態(tài)庫的不足

• 庫函數(shù)被復制到每個運行進程的代碼段，對于并發(fā)運行上百個進程的系統(tǒng)，造成內(nèi)存空間的極大浪費。
• 庫函數(shù)被合并到可執(zhí)行目標文件中，磁盤上存放著數(shù)千個可執(zhí)行文件，造成磁盤空間的極大浪費。
• 程序員需關(guān)注是否有函數(shù)庫的新版本出現(xiàn)，并須定期下載、重新編譯和鏈接，使用不便且編譯耗時。

動態(tài)鏈接共享庫（shared library，又稱共享庫或動態(tài)鏈接庫）文章來源地址http://www.zghlxwxcb.cn/news/detail-510756.html

• 目標文件，包含有代碼和數(shù)據(jù)。
• 從程序中分離出來，磁盤和內(nèi)存中都只有一個備份。
• 可在裝入時或運行時被動態(tài)加載并鏈接。
• Window稱其為動態(tài)鏈接庫（Dynamic Link Libraries，.dll文件）。
• Linux稱其為動態(tài)共享對象（ Dynamic Shared Objects, .so文件）。

到了這里，關(guān)于《計算機系統(tǒng)2》學習筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！