第一章:計算機系統漫游
這本書是為這樣一些程序員而寫的,他們希望通過了解這些部件如何工作以及如何影響程序的準確性和性能,來提高自身的技能.
系統中所有的信息--包括磁盤文件,存儲器中的程序,存儲器中存放的用戶數據以及網絡上傳送的數據,都是由一串比特表示的.
c語言是貝爾實驗室的Dennis Ritchie于1969-1973年間創建的.美國國家標準化組織在1989年頒布了ANSI C的標準.該標準定義了C語言和一系列函數庫,即所謂的標準C庫.
c和unix操作系統關系密切.c從開始就是作為一種用于unix系統的程序語言開發出來的.unix內核的大部分,以及所有它支持的工具和函數庫都是用c語言編寫的.
c是一個小而簡單的語言,c語言的設計是由一個人完成的,其結果就是這是一個簡潔明了,沒有什么冗贅的設計.
c是為實踐目的設計的.c是設計用來實現unix操作系統的.它是系統編程的首選.同時它非常適用于應用級程序的編寫.
預處理器,編譯器,匯編器和連接器一起構成了編譯系統.
匯編語言是非常有用的,因為它為不同的高級語言的不同編譯器提供了通用的輸出語言.
GNU環境包括EMAC編譯器,GCC編譯器,GDB調試器,匯編器,連接器,處理二進制文件的工具以及其他一些部件.
shell是一種命令行解釋器,它輸出一個提示符,等待你輸入一行命令,然后執行這個命令.如果該命令的第一個單詞不是一個內置的shell命令,那么shell就會假設這是一個可執行文件的名字,要加載和執行該文件.
每個I/O設備都是通過一個控制器或適配器于I/O總線連接起來的.控制器和適配器之間的區別主要在它們的組成方式.控制器是I/O設備本身中或是主板上的芯片組,而適配器則是一塊插在主板插槽上的卡.
主存是臨時存儲設備,在處理器執行程序時,它被用來存放程序和程序處理的數據.物理上來說,主存是由一組DRAM芯片組成的,邏輯上來說,存儲器是由一個線性的字節數組組成的.
中央處理單元簡稱處理器,是解釋存儲在主存中指令的引擎.處理器的核心是一個被稱為程序計數器的字長大小的存儲設備.在任何一個時間點上,PC都指向主存中的某條機器語言指令.
從系統通電開始,直到系統斷電,處理器一直在不假思索的重復執行相同的基本任務:從程序計數器指向的存儲器處讀取指令,解釋指令中的位,執行指令中的簡單操作,然后更新程序計數器指向下一條指令,而這條指令并不一定在存儲器中和剛剛執行的指令相鄰.
利用稱為DMA(直接存儲器存取)的技術,數據可以不通過處理器而直接從磁盤到達主存.
常字符串的顯示過程:存儲器到寄存器文件,再從寄存器文件到顯示設備.
一個典型的寄存器文件只存儲幾百字節的信息,主存里可存放幾百萬字節.然而,處理器從寄存器文件中讀數據比從主存中讀取要快幾乎100倍.
L1和L2高速緩存是用一種叫做靜態隨機訪問存儲器的硬件技術實現的.
我們可以把操作系統看成是應用程序和硬件之間插入的一層軟件.
操作系統有兩個基本功能:防止硬件被失控的應用程序濫用;在控制復雜而又通常廣泛不同的低級硬件設備方面,為應用程序提供簡單一致的方法.
程序在現代系統上運行時,操作系統會提供一種假象,就好像系統上只有這個程序是在運行的.這些假象是通過進程的概念來實現的,進程是計算機科學中最重要和最成功的概念之一.
在現代系統中,一個進程實際上可以由多個稱為線程的執行單元組成.每個線程都運行在進程的上下文中,并共享同樣的代碼和全局數據.
虛擬存儲器是一個抽象概念,它為每個進程提供了一個假象,好像每個進程都在獨占的使用主存.每個進程看到的存儲器都是一致的.
每 個進程看到的虛擬地址空間由大量準確定義的區組成,從最低的地址開始:程序代碼和數據(代碼和數據區是由可執行目標文件直接初始化的);堆(作為調用像 malloc和free這樣的c標準庫函數的結果,堆可以在運行時動態的擴展和收縮);共享庫(共享庫的概念非常強大,但是也是個相當難懂的概念);棧 (位于用戶虛擬地址空間頂部的是用戶棧,編譯器用它來實現函數的調用);內核虛擬存儲器(內核是操作系統總是駐留在存儲器中的部分).
虛擬存儲器的運作需要硬件和操作系統軟件之間的精密復雜的相互合作,包括對處理器生成的每個地址的硬件翻譯.基本思想是把一個進程虛擬存儲器的內容存儲在磁盤上,然后用主存作為磁盤的高速緩存.
Linux逐漸發展成為一個技術和文化現象,通過和GNU項目的力量結合,Linux項目發展成為了一個完整的,符合Posix標準的Unix操作系統的版本,包括內核和所有支撐的基礎設施.
操作系統內核是應用程序和硬件之間的媒介,它提供三個基本的抽象概念:文件是I/O設備的抽象概念:虛擬存儲器是對主存和磁盤的抽象概念:進程是處理器,支撐和I/O設備的抽象概念.//

第二章:信息的表示和處理
2的n次方的二進制表示為1后面加n個0;
指針變量將用到機器的全字長,long int*也是這樣;
可移植性的一個方面就是使程序對不同數據不敏感;
c標準對不同類型的數字范圍設置了下限,但是沒有上限;
存儲數據分大端法和小端法;
反匯編器是一種確定可執行程序文件所表示的指令序列的工具;
不同的機器使用不同的且不兼容的指令和編碼方式;
布爾的and和異或分別相當于模2的乘法和加法;
c標準沒有明確定義使用那種類型的右移;
c和c++中的有符號樹是默認的;
c的標準并沒有要求用二進制補碼來表示有符號數;
c庫中的文件<limits.h>定義了一組常量,來限定運行編譯器的這臺機器的不同整型數據的范圍;
printf沒有使用任何輸出變量類型的信息(how);
無符號和有符號數混合運算,將有符號數轉化為無符號數;
一種有名的用來執行二進制補碼的非的技術是取反并加一;
編譯器用移位和加法運算的組合來代替乘以常數因子的乘法;
單精度浮點的符號,指數和有效數字分別是1,8,23.雙精度為1,11,52.有效數字的第一位總是1,因此我們不需要表示它;
IEEE浮點格式定義了4種不同的舍入方式,默認是找到最接近的匹配.這四種方式為:向偶數舍入,向0舍入,向上舍入,向下舍入;
浮點寄存器使用一種特殊的80位的擴展精度格式;
浮點數取非就是簡單的將其符號位取反;

第三章:程序的機器級表示
匯編程序員可以看到程序計數器,整數,浮點數寄存器和條件碼寄存器;
匯編代碼只是將存儲器看成是一個很大且按字節尋址的數組;
對標量數據類型,匯編代碼也不區分有符號和無符號數,不區分各種類型的指針,甚至不區分指針和整數;
程序存儲器包含程序的目標代碼,操作系統需要的一些信息,用來管理過程調用和返回的運行時棧,以及用戶分配的存儲器塊;
IA32 CPU有8個32位值的寄存器,前6個是通用的,后2個保存棧指針和幀指針;
最頻繁使用的指令是執行數據傳送的指令;
局部變量通常是保存在寄存器中;
除了右移操作,所有的指令都不區分有符號數和無符號數;
IA32程序用程序棧來支持過程的調用,棧用來傳遞過程參數,存儲返回信息,保存寄存器以供以后的恢復之用,以及用于本地存儲;
為單個過程分配的那部分棧稱為棧幀,它的最頂端是以兩個指針定界的;
寄存器%eax可以用來返回值,如果函數要返回整數或指針的話;
IA32中%eax,%edx和%ecx被劃分為調用者保存寄存器,其余三個為被調用者保存寄存器;
IA32也仍然在不斷增加新的指令類,來支持處理多媒體應用的需要;
許多計算機系統要求某種數據類型的對象必須是某個值的k倍,這種對其限制簡化了處理器和存儲器系統之間的接口硬件設計;
&操作符可以應用到任何左值類的c表達式上,包括變量,結構,聯合和數組元素;
用高級語言編寫的程序可在許多不同的機器上編譯執行,而匯編代碼是于特定機器密切相關的;
1997-PentiumII  1999-PentiumIII  2001-Pentium4;
美國商標局不允許用數字作為商標;
Intel現在稱其指令集為IA32;
匯編代碼非常接近于機器代碼;
匯編代碼只是將存儲器看成是一個很大的,按字節尋址的數組;
機器實際執行的程序只是對一系列指令進行編碼的字節序列,機器對產生這些指令的源代碼一無所知;
call過程調用  leave為返回準備棧  ret從過程調用中返回;
指針提供一種統一方式,能夠遠程訪問數據結構;
malloc函數返回一個通用指針;
指針也可以指向函數,這提供了一個很強大的存儲和傳遞代碼引用的功能(how);
數年來,AMD的策略一致是在技術上緊跟Intel后面,生產性能稍低但是價格更便宜的處理器;
浮點數使用一組完全不同的指令和寄存器(相對整數來說);
IA32加了一條限制,傳送指令的兩個操作數不能都指向存儲器的位置,第一個是源操作數,第二個是目標操作數;
局部變量通常是保存在寄存器中的,這樣就能更快的訪問到它;
加載有效地址(load effective address)指令leal實際上是movl指令的變形,但目標操作數必須是一個寄存器;
編譯器產生的代碼中會用一個寄存器存放多個程序值,還會在寄存器之間傳送程序值;
匯編代碼提供了實現非順序控制流的較低層次的機制,這是通過借助條件碼寄存器來完成的;
當執行PC相關的尋址時,程序計數器的值是跳轉指令后面的那條指令的地址,,而不是跳轉指令本身的地址;
switch語句不僅提高了c代碼的可讀性,而且通過使用一種跳轉表的數據結構使得實現更加高效,跳轉表是一個數組,表項i是一個代碼段的地址,這個代碼段實現的是當開關索引值等于i時程序應該采取的動作;
數據傳遞,局部變量的分配了釋放是通過操縱程序棧來實現的;
IA32程序用程序棧來支持過程調用;
當對一個局部變量使用地址操作符&的時候,該變量不能保存在寄存器中;
call指令的效果是將返回地址入棧,并跳轉到被調用過程的起始處.返回地址是緊跟在程序中call后面的那條指令的地址.ret指令從棧中彈出地址并跳轉到那個位置;
在較老的IA32處理器模型中,整數乘法指令要花費30個時鐘周期,所以編譯器要盡可能的避免使用它,而大多數新近的處理器模型中,乘法指令只需要3個時鐘周期,所以不一定會進行這樣的優化;
c和c++都要求程序顯式的用free函數來釋放已經分配的空間,在Java中,釋放是由運行時系統通過一個稱為垃圾回收的進程自動完成的;
寄存器溢出是IA32一個很常見的問題,因為處理器的寄存器數量太少了;
結構的實現類似于數組的實現,因為結構的所有組成部分都存放在存儲器中連續的區域內,而指向結構的指針就是結構的第一個字節的地址;
struct數據類型的構造函數是c提供的于c++和java對象最為接近的東西;
蠕蟲是這樣一種程序,它可以自己運行,并且能夠將一個完全有效的自己傳播到其他的機器上.與此相應的,病毒是這樣一段代碼,它能將自己添加都包括操作系統在內的其他程序中,但是它不能獨立的運行;//
(14 15 16節未看)

第五章:優化程序性能
編寫高效的程序需要兩類活動:第一,我們必須選擇一組最好的算法和數據結構;第二,我們必須編寫出編譯器能夠有效優化以轉成高效可執行代碼的源代碼;
事實上,編譯器只能執行有限的程序轉換,而且妨礙優化的因素還會阻礙這種轉換,妨礙優化的因素就是程序行為中那些嚴重依賴于執行環境的方面;
編譯器優化程序的能力受幾個因素的限制,包括:要求它們絕不能改變正確的程序行為:它們對程序行為,對使用它們的環境了解有限;需要很快的完成編譯工作;
編譯器必須假設不同的指針可能會指向存儲器中同一個位置,這造成了一個主要的妨礙優化的因素,這也是可能嚴重限制編譯器產生優化代碼機會的程序的一個方面;
編譯器會假設最糟的情況,并保持所有的函數調用不變;
代碼移動的優化包括識別出要執行多次但是計算結果不會改變的計算,因而我們可以將計算移動到代碼前面的,不會被多次求值的部分;
c中的字符串是以null結尾的字符序列,strlen必須一步一步的檢查這個序列,直到遇到null字符;
過程的調用會帶來相當大的開銷,而且妨礙大多數形式的程序優化;
消除不必要的存儲器引用,具體是用一些臨時變量,這些變量很可能被存在寄存器中(如果沒有溢出的話);
在匯編代碼級,看上去似乎是一次是執行一條指令,每條指令都包括從寄存器或存儲器取值,執行一個操作,并把結果存回到一個寄存器或存儲器位置.在實際的處理器中,是同時對多條指令求值的.在某些設計中,可以有80或更多條指令在處理中.
P6 微體系結構是自20世紀90年代后期以來許多廠商生產的高端處理器的典型.在工業界稱為超標量,意思是它可以在每個時鐘周期執行多個操作,而且是亂序的, 整個設計有兩個主要部分:ICU(Instruction Control Unit,指令控制單元)和EU(Execution Unit,執行單元).
ICU從指令高速緩存中讀取指令,指令高速緩存是一個特殊的高速緩存存儲器,它包含最近訪問的指令;
指令解碼邏輯接收實際的程序指令,并將它們轉換成一組基本的操作;
加載和存儲單元通過數據高速緩存訪問存儲器,這是一個高速存儲器,包含最近訪問的數據值;
退役單元紀錄正在進行的處理,并確保遵守機器級程序的順序語意.退役單元控制著寄存器的更新;
任何對程序狀態的更新都只會在指令退役時才發生,只有在處理器能夠確信這條指令的所有分支都預測正確了,才能這樣做;
執行時間的范圍從基本整數操作的一個周期,到加載,存儲,整數乘法和更常見的浮點操作的幾個周期,到除法和其他復雜操作的許多個周期;
處理器的幾個功能單元被流水線化了,這意味著在前一個操作完成之前,它們就可以開始一個新的操作;
浮點乘法器要求連續的操作之間至少要一兩個周期,而兩個除法器根本就沒有流水線化;
標記可以與并不會寫道寄存器文件中的中間值相關聯;
循環展開本身只會幫助整數求和情況中代碼的性能,因為我們的其他情況是被功能單元的執行時間限制的;
編譯器可以很容易的執行循環展開,只要優化級別設置得足夠高(例如,優化選項-O2)許多編譯器都能例行公事的做到這一點,在命令行上以'-funroll-loops'調用GCC,它會執行循環展開;
有時候,我們能夠通過使用指針,而不是數組改進一個程序的性能;編譯器對數組代碼應用非常高級的優化,而對指針只應用最小限度的優化,為了可讀性的緣故,通常數組代碼更可取一些;
循環分割:我們可以通過將一組合并操作分割成兩個或更多的部分,并在最后合并結果來提高性能;
對于整數數據類型的情況,總共只有八個整數據傳區可用.其中兩個指向棧中的區域;
八 個整數和八個浮點寄存器的限制是IA32指令集的不幸產物,前面講到國的重命名消除了寄存器名字和寄存器數據實際位置之間的聯系.在現代處理器中,寄存器 名字之簡單的用來標識在功能單元之間傳遞的程序值.IA32只提供了很少量的這樣的標識符,限制了在程序中能表達的并行性的數量;
某個與及其相關的因素將浮點乘法能達到的CPE限制在了1.5,而不是理論極限值的1.0;
程序優化的通用原則對各種不同的機器都適用,即使某種特殊的特性組合導致最優性能依賴于特殊的機器;
到目前,臺式機或服務器中幾乎每個處理器都支持投機執行;
一個存儲器讀的結果依賴于一個非常近的存儲器的寫叫做讀寫相關,它導致了處理速度的下降;
movl %edx,(%ecx)被翻譯成兩個操作:storeaddr指令計算存儲操作的地址,創建一個存儲緩沖區中的條目,并設置該條目的地址字段;storedata指令設置該條目的數據字段;
通常,處理器/存儲器接口是處理器設計中最復雜的部分之一.不查閱詳細的文檔和使用機器分析工具,我們只能給出實際行為的一個假象的描述;
由于存儲器操作占到了程序很大一部分,存儲器子系統優化成以獨立的存儲器操作來提供更大的并行性;
優化程序性能的基本策略:
 1.高級設計,為手邊的問題選擇適當的算法和數據結構;
 2.基本編碼原則,消除函數的連續調用,在可能時,將計算移到循環外.考慮有選擇的妥協程序的模塊性以獲得更大的效率;消除不必要的存儲器引用,引入中間變量來保存中間結果,只有在最后的值計算出來的時候,才將結果存放到數組或全局變量中;
 3.低級優化.嘗試各種于數組代碼相對的指針形式;通過展開循環降低循環開銷;通過諸如迭代分割之類的技術,找到使用流水線化的功能單元的方法;
Unix系統提供了一個剖析程序GPROF.這個程序產生兩種形式的信息.首先,它確定程序中每個函數花費了多少CPU時間.其次,它計算每個函數被調用的次數,以調用函數來分析;
庫函數qsort是際遇快速排序算法進行排序的;
剖析是工具箱中一個很有用的工具,但是它不應該是唯一一個,即使測量不是很準確,特別是對較短的運行時間來說.結果只適用于被測試的那些特殊的數據;
Amdahl定律的主要觀點:要想大幅度提高整個系統的速度,我們必須提高整個系統很大一部分的速度;
Amdahl 定律描述了一個改進任何過程的通用原則.除了適用于提高計算機系統的速度外,它還能指導一個公司試著降低生產剃須刀的成本,或是指導一個學生改進他或她的 平均績點.或許它在計算機世界里最有意義,在計算機世界中,我們通常將性能提高一倍或更多.只有通過優化系統很大一部分才能獲得這么高的提高率;

第六章：存儲器層次結構
RAM分SRAM和DRAM
DDR-SDRAM:雙倍數據速率同步DRAM.通過時鐘的兩個邊沿作為控制信號,從而使DRAM的速度加倍.
ROM是以它們能被重編程的次數和對它們進行重新編程的機制來區分的:PROM,EPROM,EEDROM.閃存是基于EEPROM的;
存儲在ROM設備中的程序通常被稱為固件,當一個計算機系統通電以后,它會運行存儲在ROM中的固件;
總線是一組并行的導線,能攜帶數據,地址和控制信號;
系統總線將CPU連接到I/O橋接器,存儲器總線將I/O橋接器連接到主存,I/O橋接器也將系統總線和存儲器總線連接到I/O總線;
扇區包含相等數量的數據位,扇區之間由一些間隙分隔開,間隙用來存儲標識扇區的格式化位;
多個盤面時,任何時刻,所有讀寫頭都位于同一柱面上;
磁盤是以扇區大小的塊來讀寫數據的;
磁盤中有一個小的硬件/固件設備,稱為磁盤控制器,維護著邏輯塊號和實際磁盤扇區之間的映射關系;
在磁盤可以存儲數據之前,它必須被磁盤控制器格式化,這包括標識扇區的信息填寫扇區之間的間隙,標識出表面有故障的柱面并且不適用它們,以及在每個區中預留出一組柱面作為備用;
在使用存儲器映射I/O的系統中,地址空間中有一塊地址是為與I/O設備通信保留的,每個這樣的地址稱為一個I/O端口;
現代計算機頻繁使用基于SRAM的高速緩存;
有良好局部性的程序比局部性差的程序運行得更快;
代碼區別于程序數據的一個重要屬性是在運行時不能修改;
局部變量的反復引用是好的,步長為1的引用模式是好的;
如果你的程序需要的數據是存儲在CPU寄存器中的,那么在執行期間,在零個周期內就能訪問到它們;如果存儲在高速緩存中,需要1-10個周期;如果存儲在主存中,需要50-100個周期;而如果存儲在磁盤上,需要大約20 000 000個周期;
具有良好局部性的程序傾向于一次又一次的訪問相同的數據項集合,或是傾向于訪問鄰近的數據項集合;
特別的,我們將注意力集中在CPU和主存之間作為緩存區域的高速緩存存儲器上,因為它們對應用程序性能影響最大;
隨機訪問存儲器(random-access memory,RAM)分為兩類--靜態的和動態的.靜態RAM(SRAM)比動態RAM(DRAM)更快,但也貴得多;
SRAM將每個位存儲在一個雙穩態的存儲器單元里;每個單元是用一個六晶體管電路來實現的.這個電路有這樣一個屬性,它可以無限期的保持在兩個不同的電壓配置或狀態之一;
DRAM存儲器可以制造的非常密集--每個單元由一個電容和一個訪問晶體管組成;
只要有電,SRAM就是持續的,與DRAM不同,它不需要刷新.SRAM的存取比DRAM快.SRAM對諸如光和電噪音這樣的干擾不敏感.代價是SRAM單元比DRAM單元使用更多的晶體管,因而沒那么密集,而且更貴,功耗更大;
電路設計者將DRAM組織成二維陣列而不是線性數組的一個原因是降低芯片上地址管腳的數量;
DRAM芯片包裝在存儲器模塊中,它插到主板的擴展槽上;二維陣列組織的缺點是必須分兩步發送地址,這增加了訪問時間;
增 強的DRAM:FPM DRAM(fast page mode DRAM,快頁模式DRAM);EDO DRAM(extended data out DRAM,擴展數據輸出DRAM);SDRAM(synchronous DRAM, 同步DRAM);DDR SDRAM(double data-rate synchronous DRAM,雙倍數據速率同步);Rambus DRAM;
一些系統在固件中提供了少量的輸入和輸出函數--例如,PC的BIOS例程;I/O橋接器將系統總線的電信號翻譯成存儲器總線的電信號;
磁盤是由一個或多個疊放在一起的盤片組成的,它們放在一個密封的包裝里,正個裝置通常別叫做磁盤驅動器,雖然我們通常簡稱位磁盤;
對扇區的訪問時間有三個主要部分:尋道時間,旋轉時間,傳送時間;
從存儲器中讀一個512字節扇區大小的塊的時間對SRAM來說大約是256ns,對DRAM來說大約是4000ns.磁盤訪問時間比SRAM大約大4000倍;比DRAM大約大2500倍;
當 操作系統想要執行一個I/O操作時,例如讀一個磁盤扇區的數據到主存,操作系統會發送一個命令到磁盤控制器,讓它讀某個邏輯塊號.控制器上的固件執行一個 快速表查找,將一個邏輯塊號翻譯成一個(盤面,磁道,扇區)的三元組,這個三元組唯一的標識了對應的物理扇區.控制器上的硬件解釋這個三元組,將I/O頭 移動到適當的柱面,等待扇區移動到I/O頭下,將I/O頭感知到的位放到控制器上的一個小緩沖區中,然后將它們拷貝到主存中;
像圖形卡,監視器,鼠標,鍵盤,這樣的設備都是通過諸如Intel的PCI(peripheral component interconnect外圍設備互聯)總線這樣的I/O總線連接到CPU和主存的;
雖然I/O總線比系統總線和存儲器總線慢,但是它快頁容納種類繁多的第三方I/O設備;
USB控制器是一個將設備連接到USB的電路,USB的吞吐率可以達到12Mbit/s,是為慢速或中速串行設備設計的;
圖形卡包含硬件和軟件邏輯,它們負責代表CPU在顯示器上畫像素;
磁盤控制器包含硬件和軟件邏輯,它們用來代表CPU讀寫磁盤;
當一個設備連接到總線時,它與一個或多個端口相關聯;
邏輯塊的概念不僅能夠提供給操作系統一個更簡單的接口,還能夠提供一層抽象,使得磁盤更加健壯;
磁盤中有一個小的硬件/固件設備,稱為磁盤控制器,維護著邏輯塊號和實際磁盤扇區之間的映射關系;
操作系統用主存來緩存磁盤文件系統中最近被使用的磁盤塊;
對于取指令來說,循環有好的時間和空間局部性,循環體越小,循環次數越多,局部性越好;
一般而言,層次結構中較低層的設備的訪問時間較長,因此為了補償這些較長的訪問時間,傾向于使用較大的塊;
在一個有虛擬存儲器的系統中,DRAM主存作為存儲在磁盤上的數據塊的緩存,是有操作系統軟件和CPU上的地址翻譯硬件共同管理的;
高速緩存確定一個請求是否命中,然后抽取出被請求的字的過程,分為三步:組選擇;行匹配;字抽取;
沖突不命中在真實的程序中很常見,會導致令人困惑的性能問題;
即使程序有良好的空間局部性,而我們的高速緩存中也有足夠的空間來存放兩個數組的塊,每次引用還是會導致沖突不命中,這是因為這些塊被映射到了同一個高速緩存組;
直寫高速緩存通常是非寫分配的,寫回高速緩存通常是寫分配的;
只保存指令的高速緩存稱為i-cache,只保存程序數據的高速緩存稱為d-cache.一個典型的桌面系統CPU芯片本身就包括一個L1 i-cache和一個L1 d-cache;
一方面,較大的高速緩存可能會提高緩存命中率;另一方面,使得大存儲器運行得更快總是要難一些的;
現代系統通常會折中,使高速緩存塊包含4-8個字;
傳統上,努力爭取時鐘頻率的高性能系統會選擇直接映射L1高速緩存,而在較低層上使用比較小的相關度,但是沒有固定的規則;
一般而言,高速緩存越往下層,越可能使用寫回而不是直寫;
因為一行總是存儲一個塊,術語行和塊通常互換使用,例如,系統專家總是說高速緩存的行大小,實際上他們指的是塊大小;
理 解存儲器層次結構本質的程序員能夠利用這些知識,編寫出更有效的程序,無論具體的存儲系統是怎樣的.特別的,我們推薦下列技術:將你的注意力集中在內部循 環上,大部分計算和存儲器訪問都發生在這里;通過按照數據對象存儲在存儲器中的順序來讀數據,從而使得你程序中空間局部性最大;一旦從存儲器中讀入一個數 據對象,就盡可能多的使用它,從而使得你程序中的時間局部性最大;記住,不命中率只是確定你代碼性能的一個因素,存儲器訪問數量也扮演著重要的角色,有時 候要在兩者之間做一下折中;//(6.6未看)

第七章:連接
連接器完成的兩個主要任務:符號解析和重定位.
編譯器和匯編器生成地址0開始的代碼和數據節.
目標文件:可重定位目標文件,可執行目標文件,共享目標文件.
ELF 可重定位目標文件:ELF頭以一個16字節的序列開始,這個序列描述了字的大小和生成該文件的系統的字節順序. .test.:已編譯程序的機器代碼;.rodata.:只讀數據;.data.:已初始化的全局變量;.bss.:為初始化的全局變 量;.symtab.:存放程序中被定義和引用的函數和全局變量的信息.
連接器上下文中有三種符號:塊內定義的全局符號;塊外定義的全局符號和本地符號;
定義為帶c static屬性的本地過程變量不是在棧中管理的,編譯器在.data.和.bss.中為每個定義分配空間;
任何聲明為static屬性的全局變量或函數是模塊私有的;
編譯器來保證本地符號的唯一性;
當編譯器遇到一個不是在當前模塊中定義的變量時,它會假設該符號是在其他某個模塊中定義的,生成一個連接器符號表表目;
運行時的存儲器映像:未使用->只讀段->讀寫段->運行時堆->共享庫的存儲器映射區域->用戶棧->內核虛擬存儲器;
加載運行:可執行文件中段頭表的指導下,加載代碼和數據->程序入口點_start->初始化函數->注冊函數->主函數->返回;
c的啟動代碼對于每個c程序都是相同的,都需要跳到main函數;
鏈接就是將不同部分的代碼和數據收集和組合成為一個單一文件的過程,這個文件可被加載到存儲器并執行.鏈接可以執行于編譯時,也就是在源代碼被翻譯成機器代碼時;也可以執行于加載時,也就是在程序被加載器加載到存儲器并執行時;甚至執行于運行時,由應用程序來執行;
鏈接器在軟件開發中扮演著一個關鍵的角色,因為他們使得分離編譯成為了可能;
理解鏈接器將幫助你構造大型程序;理解鏈接器將幫助你避免一些危險的編程錯誤;理解鏈接器將幫助你理解語言的作用域規則是如何實現的;理解鏈接器將幫助你理解其他重要的系統概念;理解鏈接器使你能夠開發共享庫;
目 標文件純粹是字節塊的集合,這些塊中,有些包含程序代碼,有些則包含程序數據,而其他的則包含指導鏈接器和加載器的數據結構.鏈接器將這些塊連接起來,確 定鏈接塊的運行時位置,并且修改代碼和數據塊中的各種位置.鏈接器對目標機器了解甚少,產生目標文件的編譯器和匯編器已經完成了大部分工作;
目標 文件有三種形式:1.可重定位目標文件 包含二進制代碼和數據,其形式可以在編譯時與其他可重定位目標文件合并起來,創建一個可執行目標文件;2.可執行目標文件 包含二進制代碼和數據,其形式可以被直接拷貝到存儲器并執行;3.共享目標文件 一種特殊類型的可重定位目標文件,可以在加載活著運行時,被動態的加載到存儲器并鏈接;
各個系統之間,目標文件的格式都不相同;
SUN  Solaris使用的是Unix ELF(可執行可鏈接格式).盡管我們的討論集中在ELF上,但是不管是那種格式,基本的概念是相似的;
ELF 頭以一個16字節的序列開始,這個序列描述了字的大小和生成該文件的系統的字節順序.ELF頭剩下的部分包含幫助鏈接器解析和解釋目標文件的信息.其中包 括了ELF頭的大小,目標文件的類型(可重定位,可執行或是共享等),機器類型(IA32等),節頭部表的文件偏移,以及節頭部表中的表目大小和數量.不 同節的位置和大小是有節頭部表描述的,其中目標文件中每個節都有一個固定大小的表目;
每個可重定位目標文件m都有一個符號表,它包含m所定義和引 用的符號的信息.在鏈接器的上下文中,有三種不同的符號:1.由m定義并能被其他模塊引用的全局符號.全局鏈接器符號對應于非靜態的c函數以及被定義為不 帶c的static屬性的全局變量;2.由其他模塊定義的并被模塊m引用的全局符號.這些符號稱為外部符號,對應于定義在其他模塊中的c函數和變量;3. 只被模塊m定義和引用的本地符號.有的本地鏈接器符號對應于代static屬性的c函數和全局變量.這些符號在模塊m中的任何地方都是可見的,但是不能被 其他模塊引用.
.symtab中的符號表不包含對應于本地非靜態程序變量的任何符號.這些符號在運行時在棧中被管理,鏈接器第此類符號不感興趣;
c程序員使用static屬性在模塊內部隱藏變量和函數聲明;
鏈接器解析符號引用的方法是將每個引用與它輸入的可重定位目標文件的符號表中的一個確定的符號定義聯系起來;
編譯器只允許每個模塊中的每個本地符號只有一個定義,編譯器還確保靜態本地變量,他們也也會有本地鏈接器符號,擁有唯一的名字;
當編譯器遇到一個不是在當前模塊中定義的符號(變量或是函數)時,它會假定該符號是在其他模塊中定義的,生成一個鏈接器符號表表目,并把它交給鏈接器處理;
c++和java中能使用重載函數,是因為編譯器將每個唯一的方法和參數列表組合編碼成一個對鏈接器來說是一個唯一的名字.這種編碼過程叫做毀壞,而相反的過程叫做恢復;
函數和已初始化的全局變量是強符號,未初始化的全局變量是弱符號;
根據強弱符號的定義,Unix鏈接器使用下面的規則來處理多處定義的符號:1.不允許有多個強符號;2.如果有一個強符號和多個弱符號,那么選擇強符號;3.如果有多個弱符號,那么從這些弱符號中任意選擇一個;
所有的編譯系統都提供一種機制,將所有相關的目標文件打包為一個單獨的文件,稱為靜態庫,它也可以作為鏈接器的輸入;
在Unix系統中,靜態庫以一種稱為存檔的特殊文件格式存放在磁盤中.存檔文件是一組連接起來的可重定位目標文件的集合,有一個頭部描述每個成員目標的大小和位置;
在符號解析的階段,Unix鏈接器從左到右按照它們在編譯器驅動程序命令行上出現的相同順序來掃描可重定位目標文件和存檔文件;
一 旦鏈接器完成了符號解析這一步,它就把代碼中的每個符號引用和確定的一個符號定義(也就是它的一個輸入目標模塊中的一個符號表表目)聯系起來.在此時,鏈 接器就知道它的輸入目標模塊中的代碼節和數據節的確切大小.現在就可以開始重定位步驟了,在這個步驟中,將合并輸入模塊,并為每個符號分配運行時的地址. 重定位由兩部分組成:重定位節和符號定義(這步完成時,程序中的每個指令和全局變量都有一個唯一的運行時存儲器地址了);重定位節中的符號引用.
當 匯編器生成了一個目標模塊時,它并不知道數據和代碼最終將存放在存儲器的什么位置.它也不知道這個模塊引用的任何外部定義的函數或者全局變量的位置.所 以,無論何何時編譯器遇到對最終位置未知的目標引用,它就會生成一個重定位表目,告訴鏈接器在將目標文件合并成可執行文件時如何修改這個引用,代碼的重定 位表目放在.relo.text中,已初始化數據的重定位表目放在.relo.data中;
可執行文件的.init節定義了一個小函數,叫做_init,程序的初始化代碼會調用它;
ELF可執行文件被設計為一個很容易加載到存儲器,連續的可執行文件組塊被映射到連續的存儲器段.段頭表描述了這種映射關系;
加載器將可執行目標文件中的代碼和數據從磁盤拷到存儲器中,然后通過跳轉到程序的第一條指令,即入口點,來運行該程序.這個將程序拷貝到存儲器并運行的過程叫做加載;
當 加載器運行時,它創建了一個存儲器映像.在可執行文件中段頭表的知道下,加載器將可執行文件的相關內容拷貝到代碼和數據段,接下來,加載器跳轉到程序的入 口點,也就是符號_start的地址._start地址處的啟動代碼是在目標文件ctrl.o中定義的,對所有的c程序都是一樣的.在從.text 和.init節中調用了初始化例程后,啟動代碼調用atexit例程,這個程序附加了一系列在應用調用exit函數時應該調用的程序.exit函數運行 atexit注冊函數,然后通過調用_exit將控制返回給操作系統,接著,啟動代碼調用應用程序的main程序,這就開始執行我們的c代碼了,在應用程 序返回之后,啟動代碼調用_exit程序,它將控制返回給操作系統;
Unix系統中的每個程序都運行在一個進程上下文中,這個進程上下文有自己的 虛擬地址空間,當shell運行一個程序時,父shell進程生成一個子進程,他是父進程的一個復制品.子進程通過execve系統調用啟動加載器.加載 器刪除子進程已有的虛擬存儲器段,并創建一組新的代碼,數據,堆和棧段.新的棧和堆段被初始化為零.通過將虛擬地址空間中的頁映射到可執行文件的頁大小的 組塊,新的代碼和數據段被初始化為可執行文件的內容.最后,加載器跳轉到_start地址,它最終會調用應用的main函數.除了一些頭部信息,在加載過 程中沒有任何從磁盤到存儲器的數據拷貝.直到CPU引用一個被映射的虛擬頁,才會進行拷貝,此時,操作系統利用它的頁面調度機制自動將頁面從磁盤傳送到存 儲器;
共享庫是致力于解決靜態庫缺陷的一個現代創新產物.共享庫是一個目標模塊,在運行時,可以加載到任意的存儲器地址,并在存儲器中和一個程序鏈接起來.這個過程稱為動態鏈接,是由一個叫做動態鏈接器的程序來執行的;
在存儲器中,一個共享庫的.text節只有一個副本可以被不同的正在運行的進程共享;
生成動態鏈接的可執行文件時,鏈接器拷貝了一些重定位和符號表信息,它們使得運行時可以解析對動態庫中代碼和數據的引用;
加 載器將可執行文件的內容映射到存儲器,并運行這個程序.鏈接器還可能生成部分鏈接的可執行程序,這樣的文件中有未解析的到定義在共享庫中的程序和數據的引 用.在加載時,加載器將部分鏈接的可執行文件映射到存儲器,然后調用動態鏈接器,它通過加載共享庫和重定位程序中的引用來完成鏈接;
(7.7 7.11 7.12未理解)

第十章:虛擬存儲器
存儲器很容易被破壞.如果某個進程不小心寫了另一個進程使用的存儲器,那么進程可能以某種完全和程序邏輯無關的令人迷惑的方式失敗;
為 了更加有效地管理存儲器并且少出錯,現代系統提供了一種對主存的抽象概念,叫做虛擬存儲器.虛擬存儲器是硬件異常,硬件地址翻譯,主存,磁盤文件和內核軟 件的完美交互,它為每個進程提供了一個大的,一致的,私有地址空間.通過一個很清晰的機制,虛擬存儲器提供了三個重要的能力:它將主存看成是一個存儲在磁 盤上的地址空間的高速緩存,在主存中只保存活動區域,并根據需要在磁盤和主存之間來回傳送數據,通過這種方式,它高效地使用了主存;它為每個進程提供了一 個一致的地址空間,從而簡化了存儲器管理;它保護了每個進程的地址空間不被其他進程破壞;
虛擬存儲器是危險的.每次應用程序引用一個變量,間接引用一個指針,或者調用一個諸如malloc這樣的動態分配包程序時,它就會和虛擬存儲器發生交互;
本章的前一部分描述虛擬存儲器是如何工作的,后一部分描述的是應用程序如何使用和管理虛擬存儲器;
計算機系統的主存被組織成一個由M個連續的字節大小的單元組成的數組,每個字節都有一個唯一的物理地址;
早起的PC使用物理地址尋址,為通用計算設計的現代處理器使用的是虛擬尋址;
CPU芯片上叫做MMU的專用硬件,利用存放在主存中的查詢表來動態的翻譯虛擬地址,該表的內容由操作系統管理的;
一個地址空間的大小是由表示最大地址所需要的位數來描述的;
這就是虛擬存儲器的思想.主存中的每個字節都有一個選自虛擬地址空間的虛擬地址,和一個選自物理地址空間的物理地址;
概念上而言,虛擬存儲器被組織為一個存放在磁盤上的N個連續的字節大小的單元組成的數組.每字節都有唯一的虛擬地址,這個唯一的虛擬地址是作為到數組的索引的;
VM系統通過將虛擬存儲器分割為稱為虛擬頁的大小固定的塊,來處理這個問題.每個虛擬頁的大小為2的P次方字節.類似的,物理存儲器被分割為物理頁,大小也是2的p次方字節.
在任意時刻,虛擬頁的集合都分為三個不相交的子集:
    未分配的:VM系統還未分配的頁,未分配的塊沒有任何數據和它們相關聯,因此就不占用任何磁盤空間;
    緩存的:當前緩存在物理存儲器中的已分配頁;
    未緩存的:沒有緩存在物理存儲器中的已分配頁;
DRAM比SRAM要慢大約10倍,而磁盤要比DRAM慢大約100000多倍.因此,DRAM緩存中的不命中比起SRAM緩存中的不命中要昂貴的多;
因為大的不命中處罰和訪問第一字節的開銷,虛擬頁趨向于很大,典型的是4-8KB;
比起硬件對SRAM緩存,操作系統對DRAM緩存使用了更復雜精密的替換算法,最后,因為對磁盤的訪問時間很長,DRAM緩存總是使用寫回,而不是直寫;
同 任何緩存一樣,虛擬存儲器系統必須有某種方法來判定一個虛擬頁是否放在DRAM中的某個地方.如果是,系統還必須確定這個虛擬頁存放在哪個物理頁中.如果 不命中,系統必須判斷這個虛擬頁存放在磁盤的哪個位置,在物理存儲器中選擇一個犧牲頁,并將虛擬頁從磁盤拷貝到DRAM中,替換這個犧牲頁;
這些 功能是由許多軟硬件聯合提供的,包括:操作系統軟件,MMU中的地址翻譯硬件,和一個存放在物理存儲器中叫做頁表的數據結構.頁表將虛擬頁映射到物理頁. 每次地址翻譯硬件將一個虛擬地址轉換為物理地址時,都會讀取頁表.操作系統負責維護頁表的內容,以及在磁盤與DRAM之間來回傳送頁;
頁表就是一個PTE的數組.虛擬地址空間中的每個頁在頁表中的一個固定偏移量處都有一個PTE;
因為DRAM緩存是全相關聯的,任意物理頁都可以包含任意虛擬頁;
地址翻譯硬件將虛擬地址作為一個索引;
虛擬存儲器是在20世紀60年代早起發明的,遠在CPU-存儲器之間的差距的加大引發產生SRAM緩存之前;
虛擬存儲器工作的相當好,這主要歸功于我們的老朋友局部性;
操作系統為每個進程提供了一個獨立的頁表,因而也就是一個獨立的虛擬地址空間;
多個虛擬頁面可以映射到同一個共享物理頁面上;
獨立的地址空間允許每個進程為它的存儲器映像使用相同的基本格式,而不管代碼和數據實際存放在物理存儲器的何處;
這樣的一致性極大的簡化了鏈接器的設計和實現,允許鏈接器生成全鏈接的可執行文件,這些可執行文件是獨立于物理存儲器中代碼和數據的最終位置的;
一般而言,每個進程都有自己的私有代碼,數據,堆以及棧區域,是不和其他進程共享的.在這種情況中操作系統創建頁表,將相應的虛擬頁映射到不同的物理頁;
然而,在一些情況中,還是需要進程來共享代碼和數據的.例如,每個進程必須調用相同的操作系統內核代碼,而每個c程序都會調用標準庫中的程序;
當一個運行在用戶進程中的程序要求額外的堆空間時,操作系統分配一個適當的數次和連續的虛擬存儲器頁面,并且將它們映射到物理存儲器中任意位置的k個任意的物理頁面.由于頁表工作的方式,操作系統沒有必要分配k個連續的物理存儲器頁面.頁面可以隨機的分散在物理存儲器中;
有趣的一點是加載器從不真正的從磁盤中拷貝任何數據到存儲器中.當每個頁面第一次被引用時,虛擬存儲器系統將自動并按需的把數據從磁盤上調入到存儲器,頁面引用或者是當CPU取一條指令時,或者是當一條正在執行的指令引用一個存儲器位置時;
任 何現代計算機系統必須為操作系統提供手段來控制對存儲器系統的訪問.不應該允許一個用戶進程修改它的只讀文本段,而且也不應該允許它讀或者修改任何內核中 的代碼和數據結構.不應該允許它讀或者寫其他進程的私有存儲器,并且不允許它修改任何與其他進程共享的虛擬頁面,除非所有的共享者都顯式的允許它這么做;
運行在內核模式中的進程可以訪問的任何頁面,但是運行在用戶模式中的進程只能訪問那些SUP為0的頁面;
CPU中的一個控制寄存器,頁表基址寄存器指向當前的頁表;
MMU利用VPN來選擇適當的PTE.例如vpn0選擇pte0等.將頁表條目中的PPN和虛擬地址中的VPO串聯起來,就得到相應的物理地址,注意,因為物理和虛擬頁面都是P字節的,所以PPO和VPO是相同的;
當出項頁面命中時,CPU硬件執行的步驟:
    處理器生成一個虛擬地址,并把它傳送給MMU;
    MMU生成PTE地址,并從高速緩存/主存請求得到它;
    高速緩存/主存向MMU返回PTE;
    MMU構造物理地址,并把它傳送給高速緩存/主存;
    高速緩存/主存返回所請求的數據字給處理器;
頁面命中完全由硬件來處理的,而處理缺頁要求硬件和操作系統內核協作完成的;
    第一步到第三步同上
    PTE中的有效位是零,所以MMU觸發了一次異常,傳遞CPU中的控制到操作系統內核中的缺頁異常處理程序;
    缺頁處理程序確定出物理存儲器中的犧牲頁面,如果這個頁面已經被修改了,則把它頁面換出到磁盤;
    缺頁處理程序頁面調入新的頁面,并更新存儲器中的PTE;
    缺頁處理程序返回到原來的進程,驅使導致缺頁的指令重新啟動,CPU將引起缺頁的指令重新發送給MMU.因為虛擬頁面現在緩存在物理存儲器中,所以就會命中,在MMU執行了如上的步驟,主存就會將所請求的自返回給處理器;
MMU中包括了一個關于PTE的小的緩存,稱為TLB(翻譯后備緩沖器)
用于組選擇和行匹配的索引和標記字段是從虛擬地址中的虛擬頁號中提取出來的;
用來壓縮頁表的常用方法是使用 層次結構的頁表;
一級頁表轉中的每個PTE負責映射虛擬地址空間中的一個4MB的組塊;
如果組塊i中的每個頁面都未分配,那么一級PTE i就為空,然而,如果在組塊i中至少有一個頁是分配了的,那么一級PTE i就指向一個二級頁表的基址;
二級頁表中的每個PTE都負責映射一個4KB的虛擬存儲器頁面,每個一級和二級頁表都是4KB的;
這 種方法從兩個方面減少了存儲器要求:第一,如果一級頁表中的一個PTE是空的,那么相應的二級頁表就根本不會存在;第二,只有一級頁表需要總是在主存中, 虛擬存儲器系統可以在需要的時候創建并頁面調入或調出二級頁表,這就減少了主存的壓力.只有最經常使用的二級頁表才需要緩存在主存中;
為了方便,我們用索引它的VPN來標識每個PTE,但是要記住這些VPN并不是頁表的一部分,也不在存儲器中;