《計算機系統基礎》30’

一、處理器的時序電路

1、CPU中的時序電路

答：

CPU中的時序電路：通過RS觸發器控制CPU的時序。

2、單周期處理器的設計

答：

CPU在處理指令時，一般需要經過以下幾個步驟：

1）取指令（IF）

根據程序計數器PC中的指令地址，從存儲器中取出一條指令，同時，根據指令字長度自動遞增產生下一條指令所需要的指令地址，但遇到“地址轉移”指令時，則控制器把“轉移地址”送入PC，當然得到的“地址”需要做些變換才送入PC。

2）指令譯碼（ID）

對取指令操作中得到的指令進行分析并譯碼，確定這條指令需要完成的操作，從而產生相應的操作控制信號，用于驅動執行狀態中的各種操作。

3）指令執行（EXE）

根據指令譯碼得到的操作控制信號，具體執行指令動作，然后轉移到結果寫回狀態。

4）存儲器訪問（MEM）

所有需要訪問存儲器的操作都將在這個步驟中執行，該步驟給出的存儲器的數據地址，把數據寫入到存儲器中數據地址所指定的存儲單元或者從存儲器中得到數據地址單元中的數據。

5）結果寫回（WB）

指令執行的結果或者訪問存儲器中得到的數據寫回相應的目的寄存器中。

單周期CPU，是在一個時鐘周期內完成這五個階段的處理。

3、流水線處理器的基本原理

答：

流水線（Pipeline）技術是指程序在執行時候多條指令重疊進行操作的一種準并行處理實現技術。通俗的講將一個時序過程，分解成若干個子過程，每個過程都能有效的與其他子過程同時執行。旨在提高處理器處理效率，爭取在一個時鐘周期中完成一條指令。

將處理組織成階段：取指、譯碼、執行、訪存、寫回。通常一條指令包含很多操作，可以將它們組織成一定的階段序列，從而便于放入一個通用框架來進行流水線處理。

參考：

流水線處理器的基本原理：https://blog.csdn.net/pankul/article/details/8769979

4、Data Hazard的處理

答：

流水線給處理器帶來了效率，當然也有問題。這些問題稱之為流水線冒險（HaZard）。

1)結構冒險

由于處理器資源沖突，而無法實現某些指令或階段的組合實現，就稱之為處理器有結構冒險。

比如，早起的處理器中，程序和數據是存儲在一起的，那么容易出現下面的情況：在第一個Cycle中，IF和MEM同時訪問存儲器導致有一個操作要等待，此時hazard就出現了。現在的處理器已經解決了該問題：指令存儲在L1P cache中，數據存儲在L1D cache中，單獨訪問，不會影響相互操作。

2）數據冒險

如果流水線中原來有先后順序的指令同一時刻處理時，可能會導致出現訪問了錯誤的數據的情況。

在匯編語句中，add R1,R2,R3將寄存器R2和R3的和賦予R1，改變R1的值；而緊接著下面的語句：add R4,R1,R5則會使用R1的值，可是R1必須在一條語句中的第5個cycle才能更新到寄存器中，語句二是在第4個cycle就要訪問R1，也就是說第二條指令此時在使用錯誤的R1的值，這是數據hazard出現了。

解決方案：在兩條指令中添加一條空指令：nop。但是會影響處理器的指令的執行效率。在現代處理器技術中，已經用forwarding的方式解決了。如下圖（沒圖。。先放著吧？？？）如果處理器在檢測到當前的源操作數正好在流水線的EX或者MEM階段，直接將EX和MEM寄存器的值傳遞給ALU的輸入，而不是再從寄存器堆中獲取數據了。因此此時寄存器堆中的數據可能是沒有被及時更新的。

3）控制冒險

**在流水線中的執行指令時，由于并行處理的關系，后面很多指令其實都在流水線中開始處理了，包括預取值和譯碼。那么，如果此時程序中出現一條跳轉語句會怎么辦呢？**因為程序已經跑到其他地址處執行，流水線中之前已經做好的預取值和譯碼動作都不能使用了。這些會被處理器的專有部件flush掉，重新開始新的流水線。此時我們可以稱之為出現了控制冒險。這種情況對于程序和效率來水是存在很大的損失的。

解決方案：也就是在jump指令后面（不會被真正使用，但是會進入流水線）添加nop。在MIPS程序中，經常在jump指令后面添加nop語句。

在x86架構中，是通過硬件來實現flush，將無效的流水線排空，以保證正確運行流水線。這里會涉及到分支預測技術的使用。

在其他一些處理器中，用軟件的方式來處理，添加nop。同時在編譯器中通過亂序的思想用有效指令代替nop。這樣也可以避免跳轉帶來的性能損失。

5、流水線設計中的其他問題

答：

1）每個階段所用的硬件實際并不是互相獨立的；增加的寄存器也會導致延遲增大；每階段的周期劃分也很難做到一致。

2）理想的流水線系統，每個階段的時間都是相等的。實際上，各個階段的時間是不等的。運行時鐘是由最慢的階段決定的。

3）另外流水線過深，寄存器的增加會造成延遲增大。當延遲增大到時鐘周期的一定比例后，也會成為流水線吞吐量的一個制約因素。

二、優化程序性能

1、優化程序性能

答：

1）程序優化的第一步就是消除不必要的內容，讓代碼盡可能有效地執行它期望的工作。這包括消除不必要的函數調用、條件測試和存儲器引用。這些優化不依賴于目標機器的任何具體屬性。

2）程序優化的第二步，利用處理器提供的指令級并行能力，同時執行多條指令。

3）最后對大型程序的優化，使用代碼剖析程序，代碼剖析程序是測量程序各個部分性能的工具，這種分析能夠幫助找到代碼中低效率的地方，并且確定程序中應該著重優化的部分。

4）Amdahl定律，它量化了對系統某個部分進行優化所帶來的整體效果。

2、優化編譯器的能力和局限性以及表示程序性能

答：csapp chapter5 p325

優化編譯器的能力：

現代編譯器運用復雜精密的算法來去定一個程序中計算的是什么值，以及它們是被如何使用的。然后它們會利用一些機會來簡化表達式，在幾個不同的地方使用同一個計算，以及降低一個給定的計算必須被執行的次數。

優化編譯器的局限性：

編譯器必須很小心地對程序只是用安全的優化，也就是對于程序可能遇到的所有可能的情況，在C語言標準提供的保證之下，優化后得到的程序和未優化的版本有一樣的行為，限制編譯器只進行安全的優化，消除了一些造成不希望的運行時行為的可能原因，但是這也意味著程序員必須花費更大的力氣寫出程序使編譯器能夠將之轉換成有效機器代碼，兩個指針可能指向同一個存儲器位置的情況稱為存儲器別名使用（memory aliasing）。這造成了一個主要的妨礙優化的因素，這也是可能嚴重限制編譯器產生優化代碼機會的程序的一個方面：如果編譯器不能確定兩個指針是否執行同一個位置，就必須假設什么情況都有可能，限制了可能的優化策略。

表示程序性能：

引入度量標準每元素的周期數（Cycles Per Element CPE），作為一種表示程序性能并指導我們改進代碼的方法是用最小二乘擬合，得到一條形如y=mx+b的線，線性因子的系數m叫做每個元素的周期數CPE的有效數

3、特定體系結果或應用特性的性能優化

答：

1）簡單地使用命令行選項，如‘-O1’就會進行一些基本的優化

2）消除循環的低效率：稱作"代碼移動"，這類優化包括識別要執行多次（例如在循環里）但是計算結果不會改變的計算，因而將計算移動到代碼前面不會比多次求值的部分

3）減少過程調用：修改代碼減少函數的調用，不過會危害一些程序的模塊性

4）循環展開：通過增加每次迭代計算的元素的數量，減少循環的迭代次數。從而來個方面改程序的性能，首先它減少了不直接有助于程序結果的操作的數量，例如循環索引計算和條件分支。其次，它提供了一些方法，可以進一步變化代碼，減少整個計算中關鍵路徑上的操作數量

5）提高并行性：多個累計變量；重新結合變換

4、限制因素

1）寄存器溢出

循環并行性的好處收到描述計算的匯編代碼的能力限制。特別地，IA32指令集只有很少量的寄存器來存放積累的值（IA32只有4個，x86-64可以12個）。如果我們的并行度p超過了可用的寄存器數量，那么編譯器會訴諸溢出（spilling），將某些臨時值存放到棧中。一旦出現這種情況，性能會急劇下降。

2）分支預測和預測錯誤觸發

當分支預測邏輯不能正確預測一個分支是否要跳轉的時候，條件分支可能會招致嚴重的預測錯誤處罰。

3）對于這個問題沒有簡單的答案，有一些通用原則

（1）不要過分關系可預測分支

（2）書寫適合用條件傳送實現的代碼

5、確認和消除性能瓶頸

答：

處理大程序時連指導該優化什么地方都很困難

1）程序剖析

程序剖析包括運行程序的一個版本，其中插入了工具代碼，以確定程序的各個部分需要多少時間，這對于確認需要集中注意力優化的部分很有用，剖析一個有力指出在于可以在現實的基準數據上運行實際程序的同時，進行剖析（Unix系統提供了一個剖析程序GPROF）。通常，假設在有代表性的數據上運行程序，剖析能幫助我們對典型的情況進行優化，但是我們還應該確保對所有可能的情況，程序都有相當的性能。這主要包括避免得到糟糕的漸進性能的算法（例如插入算法）和壞的編程實例。

2）Amdahl定律(阿姆達爾定律)

其主要思想是當我們加快系統一部分的速度時，對系統整體性能的影響依賴于這個部分有多重要和速度提高了多少。

阿姆達爾曾致力于并行處理系統的研究。對于固定負載情況下描述并行處理效果的加速比s，阿姆達爾經過深入研究給出了如下公式：
S=1/(1-a+a/n)
其中，a為并行計算部分所占比例，n為并行處理結點個數。這樣，當1-a=0時，(即沒有串行，只有并行)最大加速比s=n；當a=0時（即只有串行，沒有并行），最小加速比s=1；當n→∞時，極限加速比s→ 1/（1-a），這也就是加速比的上限。例如，若串行代碼占整個代碼的25%，則并行處理的總體性能不可能超過4。這一公式已被學術界所接受，并被稱做“阿姆達爾定律”，也稱為“安達爾定理”(Amdahl law)。

三、存儲器結構及虛擬存儲器

1、局部性

答：

一個編寫良好的計算機程序通常具有良好的局部性。

引用臨近于其他最近引用的數據項的數據項，或者最近引用過的數據項本身。這種傾向性，被稱為局部性原理。

局部性兩種形式：

時間局部性：被引用過一次的內存位置很有可能在不遠的將來再被多次引用（通常在循環里）。

空間局部性：一個內存位置被引用了一次，那么將來他附近的位置也會被引用。

局部性和性能的關系

1）有良好局部性的程序比局部性差的程序運行得更快。

2）局部性原理允許計算機設計者通過引入稱為高速緩存存儲器來保存最近被引用的指令和數據項，從而提高對主存的訪問速度。

3）重復引用相同變量的程序有良好的時間局部性

4）對于具有步長為k的引用模式的程序，步長越小，空間局部性越好。

5）具有步長為I的引用模式的程序具有很好的空間局部性。

6）在內存中以大步長跳來跳去的程序空間局部性會很差。

7）對于取指令來說，循環有好的時間和空間局部性。

8）循環體越小，循環迭代次數越多，局部性越好。

2、存儲器層次結構

答：

現在隨著處理器和存儲器在性能發展上的差異越來越大，存儲器在容量尤其是訪問延遲方面的性能增長越來越跟不上處理器性能發展的需要。為了縮小存儲器和處理器兩者之間在性能方面的差距，通常在計算機內部采用層次化的存儲器體系結構。

可以看出，速度越快則容量越小、越靠近CPU。CPU可以直接訪問內部存儲器，而外部存儲器的信息則要先取主存，然后才能被CPU訪問。CPU執行指令時，需要的操作數大部分都來自寄存器；當需要從（向）存儲器中取（存）數據時，先訪問cache,如果不在cache中，則訪問主存，如果不在主存中，則訪問硬盤，此時，操作數從硬盤中讀出送到主存，然后從主存送到cache，數據使用時一般只在相鄰兩層之間復制傳送，而且總是從慢速存儲器復制到快速存儲器。傳送的單位事一個定長塊，因此需要確定定長塊的大小，并在相鄰兩層間建立塊之間的映射關系。

3、計算機高速緩存器原理

答：

加快CPU訪問速度的主要方式之一是在CPU和主存之間增加高速緩沖存儲器（簡稱高速緩存或者cache）。

cache是一種小容量高速緩沖存儲器，由快速的SRAM組成，直接制作在CPU芯片里，速度較快，幾乎與CPU處于同一個量級。

在CPU和主存之間設置cache，總師把主存中被頻繁訪問的活躍程序塊和數據塊復制到cache中。由于程序訪問的局部性，大多數情況下，CPU能直接從cache中取得指令和數據，而不必訪問慢速的主存。

為便于cache和主存間交換信息，cache和主存空間都被劃分為相等的區域。

例如，將主存按照每512字節劃分成一個區域，同時把cache也劃分成同樣大小的區域，這樣主存中的信息就可以按照512字節為單位送到cache中。

我們把主存中的區域稱為塊，也稱為主存塊，它是cache和主存之間的信息交換單位；cache中存放一個主存塊的區域稱為行或槽，也稱為cache行。

4、高速緩存對性能的影響

答：

影響cache性能的因素決定系統訪問性能的重要因素之一是cache命中率，它與許多因素有關。

1）命中率與關聯度有關

關聯度越高，命中率越高。關聯度反映一個主存塊對應的cache行的個數，顯然，直接映射的關聯度為1；2路組相聯映射的關聯度為2,4路組相聯映射的關聯度為4，全相聯映射的關聯度為cache行數。

2）命中率與cache容量有關

cache容量越大，命中率就越高。

3)命中率與主存塊的大小有關

采用大的交換單位能很好地利用空間局部性，但是較大的主存塊需要花費較多的時間來存取，因此，缺失損失會變大。由此可見，主存塊的大小必須適中，不能太大，也不能大小。

此外，設計cache時還要考慮一下因素：

采用單級還是多級cache、數據cache和指令cache是分開還是合在一起、主存-總線-cache–CPI之間采用什么架構等甚至主存DRAM芯片的內部結構、存儲器總線的總線事務類型等，也都與cache設計有關，都會影響系統總體性能。

下面對這些問題進行簡單分析說明：

目前cache基本上都在CPU芯片內，且使用L1和L2cache，甚至L3cache,CPU的訪問順序為L1cache、L2cache和L3cache。

通常L1cache采用分離cache，即數據cache和指令cache分開設置，分別存放數據和指令。指令cache有時稱為代碼cache(code cache)。L2cache和L3cache為聯合cache，即數據和指令放在一個cache中。

由于多級cache中各級cache所處的位置中，使得對它們的設計目標有所不同。例如假定是兩級cache。那么，對于L1cache，通常更關注速度而不要求有很高的命中率，因為，即使不命中，還可以到L2cache，L2cache的速度比主存速度快的多；而對于L2cache，則要求盡量提高其命中率，因為若不命中，則必須到慢速的主存中訪問，其缺失損失會很大而影響總體性能。

5、地址空間

答：

每個高級語言源程序經編譯、匯編、鏈接等處理生成可執行的二進制目標代碼時，都被映射到同樣的虛擬地址空間，因此，所有進程的虛擬地址空間是一致的，這簡化了鏈接器的設計和實現，也簡化了程序的加載過程。

虛擬存儲機制為程序提供了一個極大的虛擬地址空間（也稱為邏輯地址空間），它是主存和磁盤存儲器的抽象。虛存機制帶來了一個假象，使得每個進程都好像都獨占使用主存，并且主存空間極大。

這有三個好處：

1）每個進程具有一致的虛擬地址空間，從而可以簡化存儲管理

2）它把主存看成是磁盤存儲器的一個緩存，在主存中僅保存當前活動的程序段和數據區，并根據需要在磁盤和主存之間進行信息交換，使有限的主存空間得到了有效利用

3）每個進程的虛擬地址空間是私有的，因此，可以保護各自進程不被其他進程破壞。

6、虛擬存儲器

答：

一個系統中的進程是與其他進程共享CPU和主存資源的，然而，共享主存會形成一些特殊的情況，如果太多的進程需要太多的存儲器，那么他們中的一些就根本無法運行。當一個程序沒有空間可用的時候，那就是他運氣不好。存儲器還容易被迫害，如果一個進程不小心寫了另外一個進程使用的存儲器，它就可能失去原先的邏輯。為了更有效的管理存儲器，現在系統引入了一種對主存的抽象概念，叫做虛擬存儲器。

目前，在服務器、臺式機和筆記本等各類通用計算機系統中都采用虛擬存儲技術。在采用虛擬存儲技術的計算機中，指令執行時，通過存儲器管理部件（Memory Management Unit,簡稱MMU）將指令中的邏輯地址（也稱虛擬地址或虛地址，簡寫為VA）轉化為主存的物理地址（也稱主存地址或實地址，簡寫為PA）。在地址轉換過程中由硬件檢查是否發生了訪問信息不在主存或地址越界或訪問越權，則由操作系統進行相應的異常處理。由此可以看出，虛擬存儲技術既解決了編程空間受限的問題，又解決了多道程序共享主存帶來的安全問題。

下圖是具有虛擬存儲機制的CPU與主存的連接示意圖，從圖中可知，CPU執行指令時所給出的是指令或操作數的虛擬地址，需要通過MMU將虛擬地址轉換為主存的物理地址才能訪問主存，MMU包含在CPU芯片中。圖中顯示MMU將一個虛擬地址轉換為物理地址4，從而將第4、5、6、7這4個單元的數據組成4字節數據送到CPU。下圖僅是一個簡單的示意圖，其中沒有考慮cache等情況。

7、虛擬內存的管理

答：

1）請求分頁存儲管理

每次訪問僅將當前需要的頁面調入主存，而進程中其他不活躍的頁面放在磁盤上。當訪問某個信息所在頁不在主存時發生缺頁異常，此時，硬件將調出OS內核中的缺頁處理程序，將缺失頁面從磁盤調入主存。

與主存塊大小相比，虛擬頁的大小要大得多。因為DRAM比SRAM大約慢10~100倍，而磁盤比DRAM大約慢100000多倍，所以進行缺頁處理所花的代價要比cache缺失大得多。

而且，根據磁盤的特性，磁盤扇區定位所用的時間要比磁盤讀寫一個數據的時間長大約100000倍，也即對扇區第一個數據的讀寫比隨后數據的讀寫要慢100000倍。考慮到缺頁代價的巨大和磁盤訪問第一個數據的開銷，通常將主存和磁盤之間交換的頁的大小設定得比較大，典型的有4KB和8KB等，而且有越來越大的趨勢。

因為缺頁處理代價較大，所以提高命中率是關鍵，因此，在主存頁框和虛擬頁之間采用全相聯映射方式。此外，當進行寫操作時，由于磁盤訪問速度很慢，所以，不能每次寫操作都同時寫DRAM和磁盤，因而，在處理一致性問題時，采用回寫方式，而不用全寫方式。

2）請求分段存儲管理

根據程序的模塊化性質，可按程序的邏輯結構劃分成多個相對獨立的部分，例如，過程、數據表、數據陣列等。這些相對獨立的部分被稱為端，它們作為獨立的邏輯單位可以被其他程序段調用，形成段間連接，從而產生規模較大的程序。段通常有段名、段起點、段長等。段名可用用戶名、數據結構名或段號標識，以便于程序的編寫、編譯器的優化和操作系統的調度管理等。

可以把段作為基本信息單位在主存-輔存之間傳送和定位。分段方式下，將主存控件ain按實際程序中的段來劃分，每個段在主存中的位置記錄在段表中，段的長度可變，所以段表中需有長度指示，即段長。每個進程有一個段表，每個段在段表中有一個段表項，用來指明對應段在主存中的位置、段長、訪問權限、使用和裝入情況等。段表本身也是一個可再定位段，可以存在外存中，需要時調入主存，但一般駐留在主存中。

在分段式虛擬存儲器中，虛擬地址由段號和段內地址組成。通過段表把虛擬地址轉換成主存物理地址，分段式管理系統的優點是段的分界與程序的自然分界相對應；段的邏輯獨立性使它易于編譯、管理、修改和保護，也便于多道程序共享；某些類型的段（如堆、棧、隊列等）具有動態可變長度，允許自由調度以便有效利用主存空間。但是，由于段的長度各不相同，段的起點和終點不定，給主存空間分配帶來麻煩，而且容易在主存中留下許多空白的零碎空間，造成浪費。

分段式和分頁式存儲管理各有優缺點，因此可以采用兩者結合的段頁式存儲管理方式。

3）請求段頁式存儲管理

在段頁式虛擬存儲器中，程序按模塊分段，段內再分頁，用段表和頁表（每段一個頁表）進行兩級定位管理。段表中每個表項對應一個段，每個段表項中包含一個指向該段頁表起始位置的指針，以及該段其他的控制和存儲保護信息，由頁表指明該段各頁在主存中的位置以及是否裝入、修改等狀態信息。

程序的調入調出按頁進行，但它又可以按段實現共享和保護。因此，它兼有分頁式和分段式存儲管理的優點。它的缺點是在地址映射過程需要多次查表。

8、翻譯和映射

答：

9、后備轉換緩沖器TLB

答：

地址轉換過程中，訪存時首先要到主存查頁表，然后才能根據轉換得到的物理地址再訪問主存以存儲指令或數據。如果缺頁，則還要進行頁面替換、頁面修改等，訪問主存的次數就更多。因此，采用虛擬存儲機制后，使得訪存次數增加了。為了減少訪存次數，往往把頁表中最活躍的幾個頁表項復制到高速緩存中，這種在告訴緩存中的頁表項組成的頁表稱為后備轉換緩沖器（Translation Lookaside Buffer,TLB）,通常稱為快表，相應地稱主存中的頁表為慢表。

10、動態存儲器分配和垃圾收集

答：

我們可以通過mmap和munmap來創建和刪除虛擬存儲器區域，但對開發來說使用起來并不方便，況且沒有很好的移植性，所以提出了是使用動態存儲分配器來管理進程空間中的堆區域。動態存儲分配器維護著一個進程的虛擬存儲器區域，稱為堆。堆事從低位地址向高位向上增長的，對于每個進程，內核維護著一個brk，它指向堆的頂部。

分配器將堆視為一組不同大小的塊的集合來維護。每個塊就是一個連續的虛擬存儲器片，要么是已分配的，要么是空閑的。已分配的顯式地保留為供應應用程序使用。空閑塊可用來分配。一個已分配的塊保持已分配狀態，直到它被釋放，這種釋放要么是應用程序顯式執行的，要么是存儲器隱式執行的，它們都是顯式的來分配存儲塊的，不同之處在于由哪個實體來負責釋放已分配的塊。

• 顯式分配器

要求顯式的釋放已分配的塊。如C標準庫中的malloc和free，C++中的new和delete操作符。

• 隱式分配器

要求分配器檢測一個已分配的塊何時不再被程序使用，那么就釋放這個塊。隱式分配器也叫做垃圾收集器（Garbage collector），如java語言就依賴類似分配器。

下面我們看下malloc和free的實現是如何管理一個C程序的16字的小堆的。每個方框代表一個4字節的字。粗線標出的矩形對應于已分配塊（有陰影）和空閑塊（無陰影），初始時，堆都是一個大小為16個字的、雙字對齊的、空閑塊組成的。

• a)程序請求一個4字的塊，malloc的響應是：從空閑塊的前部切出一個4字的塊，并返回一個指向這個塊的第一個字的指針p1
• b)程序請求一個5字的塊，malloc的響應是：從空閑塊的前部分分配一個6字的塊，返回指針p2，填充的一個額外字是為了保持空閑塊是雙字邊界對齊的。
• c)程序請求一個6字的塊，而malloc就從空閑塊的前部切出一個6字的塊。返回指針p3
• d)程序釋放在b中分配的那6字的塊。需要注意的是，在調用free返回之后，指針p2仍然指向被釋放的塊，在它被一個新的malloc調用重新初始化之前不能在程序中再使用p2
• e)程序請求一個2字的塊。在這種情況下，malloc分配在前一步中釋放了的塊的一部分，并返回指向新塊的指針p4

**垃圾收集器是一種動態存儲器分配器，它自動釋放程序不再需要的已分配塊。這些塊稱為垃圾。自動回收堆存儲的過程叫做垃圾收集。**在java虛擬機中就使用了類似的機制，應用顯式分配堆塊，但是從不顯式地釋放他們。垃圾收集器定時識別垃圾塊，并相應地調用free，將這些塊放回到空閑鏈表中。

垃圾收集器將存儲器視為一張有向可達圖，改圖的節點被分成一組根節點和一組堆節點。每個堆節點對應于堆中一個已分配塊。有向邊p->q意味著塊中的某個位置指向塊q中的某個位置。根節點對應于這樣一種不再堆中的位置，他們中包含指向堆中指針。這些位置可以是寄存器、堆里的變量，或者是虛擬存儲器中讀取數據區域內的全部變量。

當存在一條從任意根節點出發并到達p的有向路徑時，我們說節點p是可達的。在任何時刻，不可達節點對應于垃圾，是不能被應用再次使用的。垃圾收集器的角色就是維護可達圖的某種表示，并通過釋放不可達節點將它們返回給空閑鏈表，來定期回收它們。

四、鏈接、進程及并發編程

1、靜態鏈接

答：

1）將可重定位的文件和命令行完全鏈接的、可加載、可運行的目標文件；

2）可重定位目標文件由各代碼和數據節組成；

完成靜態鏈接，鏈接器要完成以下兩個工作：

1）符號解析，將每一個符號引用正好和一個符號定義關聯起來；

2）重定位：可重定位的目標文件地址都是從零開始的，連接器通過把每個符號定義與一個內存位置關聯起來，從而重定位這些節，然后修改所有對這些符號的引用，使得他們指向這個內存位置。

2、目標文件

答：

分類：可重定位目標文件；可執行目標文件；共享目標文件；

可重定位目標文件：

包含二進制代碼和數據，其形式可以在編譯時與其他可重定位目標文件合并起來，創建一個可執行目標文件。

可執行目標文件：

包含二進制代碼和數據，其形式可以被直接復制到內存并執行。

共享目標文件：

一個特殊類型的可重定位目標文件，可以在加載或者運行時被動態的加載進內存并鏈接。

3、符號和符號表

答：

定義：符號表記錄了目標模塊定義的符號和引用的符號信息。

三種符號類型：

1）由模塊m定義并能被其他模塊引用的全局符號，非靜態的C函數和全部變量；

2）由其他模塊定義并被模塊m引用的全局變量；

3）由目標模塊定義和引用的局部符號，表現為靜態全局變量和函數；

符號解析：鏈接符號引用與符號定義

1)全局符號的多種定義問題

強符號：已被初始化的全部變量和函數

弱符號：未被初始化的全部變量

2）規則

（1）不允許有多個同名的強符號

（2）如果有一個強符號和多個弱符號同名，選強符號

（3）如果有多個弱符號同名，從其中任意選一個

3）符號的地址由鏈接器確定，但符號的大小以及其類型在編譯器就已經確定了，鏈接只負責解析和重定位符號確認符號的地址，同名符號有且僅有一個地址

4）靜態鏈接可選方式

（1）一組可重定位目標文件

（2）所有相關的目標模塊打包成一個單獨文件-靜態庫（存檔文件）

5）使用靜態庫來解析符號

過程：

符號解析時，鏈接器從左到右按照他們在編譯器驅動程序命令行上出現的順序來掃描可重定位目標文件和存檔文件（如.c .o）。

鏈接器維護三個集合：所有目標模塊集合E；未定義的集合U；定義的集合D；

掃描開始，鏈接器來判斷輸入f是什么，若是目標文件，f添加到E，修改U/D來反應f中的符號定義和引用；若f是存檔文件，鏈接器就嘗試匹配U中未解析的符號和由存檔文件成員定義的符號，若存檔文件成員m中有已定義的符號，m放E，修改U/D；如果鏈接器完成掃描后，U非空，則鏈接器輸出錯誤并終止，否則他會合并和重定位E中的目標文件

4、重定位和加載

答：

1）重定位（可結合靜態鏈接的兩個步驟作答）

需要的術語：

（1）重定位節和符號定義：聚合所有目標文件的相同節，鏈接器開始將運行時內存地址賦給每一個節和每一個符號☆☆☆

（2）重定位節中的符號引用，鏈接器修改代碼節和數據節中的每個符號引用，使得他們執行正確的運行時地址。

2）過程：

（1）一個概念，當匯編器遇到未知的符號引用，就會生成一個重定位條目，代碼的重定位條目存放在.rel.text中，已初始化數據的重定位條目放在.rel.data中

重定位結構的數據結構：

typedef struct{? long offset;? long type:32; //符號相對節的偏移? symbol:32;? long addend;}EIf64_Rela

（2）符號引用的重定位

只講兩種基本的重定位類型：相對引用；絕對引用。

3）加載☆☆☆

（1）背景：elf可執行文件的格式跟可重定位的格式是和相似的

（2）可執行目標文件的加載

加載器將目標文件的代碼和數據復制到內存中，然后跳轉到入口點來運行即_start函數的地址；

5、動態鏈接庫

答：

1）出現的原因：

為了解決靜態庫維護還是相對麻煩以及很多共用庫在內存中有很多隨便造成的內存浪費。

2）動態鏈接：

共享庫在加載或運行時加載在任意內存位置，并和在內存中的程序鏈接起來，由動態鏈接器完成。

3）相關細節：

動態鏈接不會復制共享庫的代碼和數據段，僅會復制一些重定位信息和符號表；

信息和符號表

共享庫中會有一個.interp節，這個節包含動態鏈接器的路徑名，動態鏈接器本身就是一個共享目標如（Id-linux.so）。

當運行一個可執行文件時，加載器會通過.interp節的信息找到動態鏈接器來運行，而動態鏈接器重定位相關的.so來完成鏈接任務：

位置無關代碼PIC(position independent code)：共享庫若想要被進程共享就要求使用位置無關代碼，位置無關代碼是可以加載到內存的任意位置，而無需鏈接器修改即可以加載和重定位；

6、異常和進程

答：

異常就是控制流突變，用來響應處理器狀態中的某個變化，一部分由硬件實現，一部分由操作系統來實現，每個異常都會被分配一個異常號，一些由硬件設計者來分配，常見的有：內存缺頁、算法溢出、內存訪問違規、除零，一些由內核設計者分配，常用的有系統調用和外部I/O設備的信號，異常有如下分類：中斷、故障、陷阱、終止。其中中斷是異步發生的，中斷函數處理結束后返回下條指令，陷阱是同步的總是返回下條指令，故障是同步的，由潛在可恢復的錯誤造成（缺頁），返回當前的指令，終止是同步的，不可恢復，不會返回。

1）異常處理與過程調用的一些不同之處

（1）返回地址不一樣，異常返回地址需要根據異常類型來確定

（2）異常處理時，處理器將一些額外的處理狀態壓入棧中

（3）若是由用戶態進入內核態，則異常處理使用內核棧

（4）異常處理運行在內核態

2）四種不同的類型

中斷：不是由一條專門的指令造成的，他是處理器在每次執行一條指令后檢測是否有中斷產生；

陷阱和系統調用：陷阱是有意義的異常，像中斷處理程序一樣，陷阱處理程序將返回下一條指令。陷阱最重要的作用是在用戶程序和內核之間提供一個像過程一樣的接口，叫做系統調用。系統調用都有一個服務號，指令“syscall n”來請求服務n;

中斷與系統調用的區別：系統調用采用陷阱門，中斷進入中斷服務cpu自動關閉中斷IF清0，防止嵌套；陷阱門進入服務程序時IF不變，是開中斷下進行的，所有系統調用可被中斷；

系統調用與一般程序區別：調用的棧不同，一個運行在內核模式一個運行在用戶模式；

故障：若故障能夠被恢復，則返回到引起故障的指令，否則終止；

終止：不可恢復的錯誤。

進程：

1）定義：

一個執行中的程序的實例。

進程與程序的區別：程序是一堆代碼可以作為目標文件存在于磁盤上，或者作為段存在于地址空間中，進程是執行程序的一個具體實例，程序總是運行在某個進程的上下文中。

2）進程提供應用程序的關鍵抽象：

一個獨立的邏輯控制流，它提供一個假象，好像我們的程序獨占地使用處理器。

一個私有的地址空間，它提供一個假象，好像我們的程序獨占地使用內存系統。

3）邏輯控制流

PC值的序列-邏輯流

4）用戶模式下訪問內核

唯一的模式就是通過異常（中斷、故障、陷阱）

處理器通常是用某個控制寄存器中的一個模式位，該寄存器描述了當前進程享有的特權。當設置了模式位時，進程就運行。在內核模式中（也叫超級用戶模式）一個運行在內核模式的進程可以執行指令集中的任何指令，并可以訪問系統中的任何內存位置。沒有設置，就是普通模式，不允許執行特權指令，比如停止處理器等。

5）上下文切換過程

每個進程維持一個上下文，上下文是內核重新啟動一個被搶占的進程所需的狀態。

過程：

（1）保存當前進程的上下文

（2）恢復某個先前被搶占的進程被保存的上下文

（3）將控制傳遞給這個新恢復的進程

7、進程控制和信號

答：

1）進程控制

（1）獲取進程號（進程唯一的進程號 正數 ID/PID） getpid;

（2）創建進程和終止進程

程序員角度分三種（？TODO）

運行：進程在cpu運行或等待運行且最終被內核調度

停止：進程的執行被掛起，且無觸發條件不會被調度

終止：永遠停止了，如收到一個信號終止了進程，或調用exit

創建：fork、vfork（fork：調用一次返回兩次，和父進程用相同的地址空間，與父進程并發執行，與父進程共享文件，pid不一樣；）

（3）回收子進程

一個終止的進程若沒有被父進程回收，會變成僵尸進程，仍然會占用內存空間，直到被回收。若其父進程先終止，則另init進程收養、回收。init進程pid為1，是所有進程的祖先。

（4）進程的休眠：sleep pause;

2）信號

（1）一次軟件形式的異常，一個信號就是一條消息，它通知進程系統發生了一個某種類型的事件。

底層的硬件異常是由內核異常處理程序來處理，一般情況下對用戶而言是不可見的，但信號提供了一種機制告訴用戶進程系統發生了什么樣的異常。

（2）發生信號的原理：內核改變目的進程的上下文中某個狀態來傳遞一個信號給目的的進程；

（收發信號可簡單理解為：上下文中存與取）

接收信號后常見的信號處理行為有以下幾種：

• 進程終止：SIGKELL
• 進程終止并轉儲內存
• 進程停止（掛起）知道被SIGXONT信號重啟
• 進程忽略該信號

（3）進程組的概念：每個進程都屬于一個進程組，且父子進程同屬于一個進程組。

（4）阻塞和解除阻塞

隱式阻塞：阻塞任何與當前正在處理的信號類型的待處理的信號，只是等不用條件觸發。

顯示阻塞：明確的阻塞和解除阻塞選定的信號。

（5）非本地跳轉

一種用戶級異常控制流，他可以將控制直接從一個函數轉移到另外一個當前正在執行的函數而不用通過函數棧機制。

8、進程間的通信

答：

1）管道及有名管道

管道用于有親緣關系進程間的通信，有名管道克服了管道沒有名字的限制，因此，有名管道可用于無親緣關系進程間通信。

2）信號

用于通知接受進程有某種事件發生，除了用于進程間通信外，進程還可以發信號給進程本身。

3）消息隊列

是消息的鏈表，存放在內核中，并由消息隊列標識符標示。客服了信號傳輸信息少，管道只能承載無格式字節及緩存區大小受限等問題；

4）信號量

信號量是一個計數器，可以用來控制多個進程對共享資源的訪問；

5）共享內存

多個進程可以訪問同一塊內存，是最快的IPC形式，一般結合信號量使用；

6）套接字

更一般的進程間通信機制，可以完成本機或跨機器的進程通信；

9、進程間信號量的控制

答：

信號量是一個計數器，是一個具有非負值的全局變量，能做到如下兩個操作：

P（s）：如果s為非零，那么P將s減1，并且立即返回。如果s為零，那么就掛起這個線程，直到s變為非零，而一個V操作會重啟這個線程。重啟后P操作將s減1，并將控制返回給調用者。

V（s）：V操作將s加1，如果有任何現場阻塞在P操作等待s變成非零，那么V操作會重啟這些線程中的一個，然后該線程將s減1，完成它的P操作。

10、信號量

信號量是一個特殊的變量，程序對其訪問都是原子操作，且只允許對它進行P和V操作，最簡單的信號量是只能取0和1的變量，這也是信號量最常用的一種形式，叫做二進制信號量，而可以取多個常量的信號量被稱為通用信號量。

11、各種并發編程模式

答：

概念：

如果邏輯控制流在時間上有重疊，那它們就是并發的；

場景：

• 訪問慢速I/O設備
• 與人交互
• 推遲工作以降低延遲
• 服務多個網絡客戶端
• 在多核機器上并行計算

三種并發編程模式：

1）基于進程的并發編程

每個邏輯控制流都是一個進程，由內核來調度和維護

優缺點，

優點：共享文件表，不共享用戶空間，更加的安全；

缺點：開銷大，共享信息困難，要使用顯式的IPC

2）基于I/O多路復用的并發編程

基本的思想是select函數，要求掛起進程，只有在一個或多個I/O事件發生后，才將控制返回給應用程序；I/O多路復用可以用做并發事件驅動程序的基礎。

優缺點：

優點：程序員能更好的控制程序，共享數據簡單；

缺點：編碼復雜，并且程度越小，復雜度越高；

3）基于線程并發模型

概念：

線程就是運行在進程上下文中的邏輯流，線程也由內核調度，每個線程都有自己的線程上下文，包括線程ID、棧、棧指針、程序計數器、條件碼和通用目的寄存器。

線程的切換比進程快很多，線程是對等的，任何線程都可以訪問共享虛擬內存的任何位置。

分離線程：

線程要么是可結合的，要么是可分離的，區別：

（1）可結合線程：可以被其他線程回收和殺死，被回收之前，它所占用的資源不會釋放；

（2）可分離進程：不可以回收不可以殺死，它的內存資源在其終止時自動釋放，默認創建的都是可結合線程；

12、共享變量和線程同步

答：

1）線程內存模型

每個線程都有自己獨立的線程上下文，包括線程ID、棧、棧指針、程序計數器、條形碼和通用目的寄存器。線程與其他線程共享進程上下文的剩余部分。包括整個用戶虛擬地址空間。

2）將變量映射到內存

全局變量：定義在函數之外的變量，運行時，全局變量只有一個實例，任何線程都可以引用。

本地自動變量：定義在函數內，但沒有static屬性的變量，運行時每個線程的棧都包含它自己的所有本地自動變量實例。

本地靜態變量：函數內部用static屬性的變量，運行時只有一個實例。

3）共享變量

我們說一個變量v是共享的，當且僅當它的一個實例被一個以上的線程引用。如果只有一個線程引用就不是共享。共享變量是簡單的，但這種共享方式會引來同步錯誤，因為線程之間的運行是競爭關系，沒辦法確認進程運行的順序，為了解決這種錯誤，可以使用信號量來對共享資源加鎖，使其確定線程對該變量的互斥訪問。

4）線程同步

確保每個線程在執行它的臨界區中的指令時，擁有對共享變量的互斥訪問。通過對二元信號量（也叫互斥鎖）的使用，對共享資源進行加鎖，使得每次只會有一個線程能夠訪問，直到訪問完成，其他線程才能訪問，這樣就能對資源的互斥訪問，達到線程同步。

13、其他并行問題

答:

1）線程安全

如果一個函數被稱為線程安全的，那當且僅當被多個并發線程反復地調用時，它會一直產生正確的結果。

四種線程不安全函數：

• 不保護共享變量的函數
• 保持跨越多個調用狀態的函數
• 返回指向靜態變量的指針函數
• 調用線程不安全函數的函數

2）可重入性

有一類重要的線程安全函數，叫做可重入函數，當它們被多個線程調用時，不會引用任何共享數據，盡快線程安全和可重入性不等價，可重入函數屬于線程安全函數；

顯式可重入函數：不依賴調用者，所有的數據引用都是本地自動棧變量，且參數是傳值傳遞的（不是指針）；

隱式可重入函數：形參可以使指針，小心的傳遞指向非共享數據的指針；

3）linux提供不安全的可重入版本（安全）函數名多以_r結尾；

4）競爭：當程序的結果依賴一個線程要在另一個線程達到y點前到達它的控制中的x點時，就會產生競爭；

5）死鎖：一個線程阻塞了，等待一個永遠不為真的條件。

五、系統級I/O和網絡編程

《CSAPP》

1、I/O相關概念

為了更加有效地管理存儲器并且少出錯，現代系統提供了一種對主存的抽象概念，輸入/輸出（I/O）是在主存（main memory）和外部設備（例如磁盤驅動器、終端和網絡）之間拷貝數據的過程。輸入操作是從I/O設備拷貝數據到內存，輸出操作是從主存拷貝數據到I/O設備。

所有的運行時系統都提供I/O的較高級別的工具，例如ANSI C提供標準的I/O庫，包含像printf和scanf這樣執行帶緩沖的I/O函數。C++用它的重載操作符<<(輸入)和>>(輸出)提供了類似的功能。在Unix系統中，是通過使用內核提供的系統級Unix I/O函數來實現這些較高級別的I/O函數的。

2、文件及文件操作

答：

一個Unix文件就是一個m字節的序列B0,B1,…,Bk,…,B(m-1)

所有的I/O設備，例如網絡、磁盤和中斷，都被模型化為文件，而所有的輸入和輸出都被當做相應的文件讀和寫來執行。這種將設備優雅地映射為文件的方式，運行Uninx內核以一種統一的且一致的方式來執行：

• 打開文件
• 改變當前的文件位置
• 讀寫文件
• 關閉文件

共享文件

無共享

同一個進程的不同表項，通過文件表指向了同一個位置

Unix共享文件的內核用三種相關的數據結構來表示打開的文件：

• 描述符表（descriptor table）：每個文件都有它獨立的描述符表，它的表項是由進程打開的文件描述符來索引的。每個打開的描述符表項指向文件表的一個表項。
• 文件表（file table）：打開文件的集合是由一張文件表表示的，所有的進程共享這張表。
• v-node表（v-node table）：同文件表一樣，所有的進程共享v-node表。

多個描述符也可以通過不同的文件表項來引用同一個文件。關鍵思想是每個描述符都有它自己的文件位置，所以對不同描述符的讀操作可以從文件的不同位置獲取數據。

3、文件、網絡編程

網絡應用集成了我們已經學到的很多概念：進程、信號、字節順序、存儲器映射、動態分配等，同時客戶端-服務端模型是一個新的知識，我們將所有的這些結合起來，創建一個微小的web服務器，提供瀏覽器靜態和動態訪問。

就是我們平常TCP和UDP兩種編程：

• TCP需要三次握手，才能成功連接
• UDP直接丟包，例如視頻軟件就使用UDP

4、客戶端-服務器模型（C/S Model）

每個網絡應用都是基于客戶端-服務器模型的。

客戶端-服務器模型中的基本操作是事務的。一個客戶端-服務器由以下四步組成：

1）當一個客戶端需要服務時，它向服務器發送一個請求，發起一個事務

2）服務器收到請求后，解釋它，并以適當的方式操作它的資源

3）服務器給客戶端發送一個響應，并等待下一個請求

4）客戶端收到響應并處理它

TIPS:客戶端和服務器是進程，而不是機器或主機，因為一臺主機可以同時運行不同的客戶端和服務器。

5、套接字接口socket

答：

一個套接字是連接的一個端點。每個套接字都有相應的套接字地址，由一個因特網地址和一個16位的整數端口組成，用“地址：端口”表示。

1）套接字接口是一組函數，它們和Unix I/O函數結合起來，用以創建網絡應用

從Linux內核看，一個套接字就是通信的一個端點，從Linux程序看，套接字就是一個有相應描述符的打開文件。

2）客戶端和服務器使用socket函數來創建一個套接字描述符

例子：對于ipv4創建socket，其中使用tcp協議

sock = socket(AF_INET, SOCK_STREAM, 0);

3）客戶端通過調用connect函數建立和服務器的連接

4）bind函數告訴內核將addr中的服務器套接字地址和套接字描述符sockfd聯系起來

5）listen函數將sockfd從一個主動套接字轉化為一個監聽套接字

6）TCP服務器端依次調用socket()、bind()、listen()之后，就會監聽指定的socket地址了。TCP客戶端依次調用socket()、connect()之后就向TCP服務器發送了一個鏈接請求。TCP服務器端監聽到這個請求后，就會調用accept()函數去接收請求，這樣連接就建立好了。之后就可以開始網絡I/O操作了，即類似于普通文件的讀寫I/O操作。

7）getaddrinfo函數將主機名、主機地址、服務名和端口號的字符串表示轉化成套接字地址結構，這個函數可重入的，適用于任何協議。

8）將一個套接字地址結構轉換成相應的主機和服務名字符串。

TODO CODE_DEMO

6、HTTP請求

答：

一個HTTP請求：一個請求行（request line）后面跟隨0個或多個請求報頭（request header），再跟隨一個空的文本行來終止報頭。

請求行：<method><url><version>

HTTP支持許多方法，包括GET,POST,PUT,DELETE,OPTIONS,HEAD,TRACE。

URI是相應URL的后綴，包括文件名和可選參數

version字段表示該請求所遵循的HTTP版本

請求報頭：<header name>:<header data>為服務器提供了額外的信息，例如瀏覽器的版本類型HTTP1.1中，一個IP地址的服務器可以是多宿主主機，例如www.test1.com www.test2.com都可以存在于同一個服務器上。HTTP1.1中必須有host請求報頭，如host:www.google.com:80。如果沒有這個host請求報頭，每個主機名都只有唯一IP，IP地址很快將會用盡。

7、Web服務器

答：

web服務器以兩種不同的方式向客戶端提供內容：

1）靜態內容：取一個磁盤文件，并將它的內容返回給客戶端

務器套接字地址和套接字描述符sockfd聯系起來

5）listen函數將sockfd從一個主動套接字轉化為一個監聽套接字

6）TCP服務器端依次調用socket()、bind()、listen()之后，就會監聽指定的socket地址了。TCP客戶端依次調用socket()、connect()之后就向TCP服務器發送了一個鏈接請求。TCP服務器端監聽到這個請求后，就會調用accept()函數去接收請求，這樣連接就建立好了。之后就可以開始網絡I/O操作了，即類似于普通文件的讀寫I/O操作。

7）getaddrinfo函數將主機名、主機地址、服務名和端口號的字符串表示轉化成套接字地址結構，這個函數可重入的，適用于任何協議。

8）將一個套接字地址結構轉換成相應的主機和服務名字符串。

TODO CODE_DEMO

6、HTTP請求

答：

一個HTTP請求：一個請求行（request line）后面跟隨0個或多個請求報頭（request header），再跟隨一個空的文本行來終止報頭。

請求行：<method><url><version>

HTTP支持許多方法，包括GET,POST,PUT,DELETE,OPTIONS,HEAD,TRACE。

URI是相應URL的后綴，包括文件名和可選參數

version字段表示該請求所遵循的HTTP版本

請求報頭：<header name>:<header data>為服務器提供了額外的信息，例如瀏覽器的版本類型HTTP1.1中，一個IP地址的服務器可以是多宿主主機，例如www.test1.com www.test2.com都可以存在于同一個服務器上。HTTP1.1中必須有host請求報頭，如host:www.google.com:80。如果沒有這個host請求報頭，每個主機名都只有唯一IP，IP地址很快將會用盡。

7、Web服務器

答：

web服務器以兩種不同的方式向客戶端提供內容：

1）靜態內容：取一個磁盤文件，并將它的內容返回給客戶端

2）動態內容：執行一個可執行文件，并將它輸出返回給客戶端

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的【❌❌深入浅出，九浅一深⭕⭕】《深入理解计算机系统》CSAPP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。