當前位置：
首頁 > 最新 > 《深入理解計算機系統》讀書筆記

《深入理解計算機系統》讀書筆記

最新 07-04

程序的機器級表示

程序編碼

編譯

編譯時,提高優化級別,可以提高運行速度,但是編譯時間會更長,對代碼調試會更困難

編譯過程

彙編代碼與目標代碼

彙編代碼接近於機器代碼,目標代碼是二進位格式,彙編代碼的特點是,可讀性很好的文本格式表示

數據格式

Intel用術語"字(word)"表示16位數據類型,因此稱32位為雙字,64位為4字


編寫高效程序

選擇一組最好的演算法和數據結構

編寫出編譯器能夠有效優化以轉換成高效可執行代碼的源代碼

編譯技術

與機器有關:依賴機器的低級細節

與機器無關:不考慮計算機的特性

存儲器別名使用

編譯器必須假設不同的指針可能指向存儲器的同一個位置,阻礙編譯器優化

消除循環的低效率Amdahl定律

當我們加快系統中某一部分的速度時,對系統整體的影響取決於這個部分有多重要和速度提高了多少

編號高速緩存友好的代碼讓最常見的情況運行的更快

核心函數的少量循環

循環內部,緩存不命中數量最小時間局部性

被引用過的一次的存儲器位置在不久的將來被多次引用

空間局部性

如果一個存儲器被引用一次,在不久的將來引用附近的一個存儲器位置

存儲器山

run函數的參數size和stride允許我們控制產生讀序列的局部性程度

size越小,每次讀取的越小,變數引用更快,時間局部性越好;stride越小,寫入越快,空間局部性越好

反覆以不同的size和stride調用run函數,形成讀帶寬的時間和空間局部性的二維函數,稱為存儲器山


第二部分

鏈接

鏈接就是將不同部分的代碼和數據組合成一個單一文件的過程,文件可被載入到存儲器執行

鏈接可以執行於編譯時(源代碼->機器代碼),也可以載入時(程序載入到內存中執行),,甚至在運行時由應用程序執行

早期,鏈接是手動執行,現在系統中,由叫做鏈接器的程序自動執行


可重定位目標文件

包含二進位代碼和數據,可在編譯時與其他可重定位目標文件合併起來,創建一個可執行目標文件

可執行目標文件

包含二進位代碼和數據,可直接拷貝到存儲器並執行

共享目標文件

一種特殊類型的可重定位目標文件,可在載入時或運行時,被動態的載入到存儲器並鏈接


p不是內置的shell命令,所以shell會認為p是一個可執行目標文件,通過調用駐留在存儲器中稱為載入器的操作系統代碼來運行p

任何Unix程序都可以調用execve函數來調用載入器

載入器將可執行目標文件中的代碼和數據從磁碟拷貝到存儲器中,然後跳轉到程序的第1條指令,即入口點(entry point),來運行程序

將程序拷貝到存儲器並運行的過程叫做 載入

載入器實際上是如何工作的?

Unix系統中的每個程序都運行在一個進程上下文中,這個進程上下文有自己的虛擬地址空間

當shell運行一個程序時,父shell進程生成一個子進程,它是父進程的一個複製品

子進程通過execve系統調用啟動載入器,載入器刪除子進程已有的虛擬存儲器段,並創建一組新的代碼、數據、堆和棧段

新的棧和堆段被初始化為零,通過將虛擬地址空間中的頁映射到可執行文件的頁大小組塊,新的代碼和數據段被初始化為可執行文件的內容

載入器跳轉到_start地址,最終會調用應用的main函數

除了一些頭部信息,載入過程中沒有任何從磁碟到存儲器的數據拷貝,直到CPU引用一個被映射的虛擬頁,才會進行拷貝,此時,操作系統利用它的頁面調度機制自動將頁面從磁碟傳送到存儲器


共享庫的目的,就是允許多個正在運行的進程,共享存儲器中相同的庫代碼,節省寶貴的存儲器資源

多個進程如何共享一個程序的一個拷貝呢?

方法1

給每個共享庫實現分配一個專用地址空間塊,然後要求載入器總是在這個地址載入共享庫

不好的:1,即使一個進程不使用這個庫,那部分空間還是會分配

2,難以管理: 我們得保證沒有組塊會重疊,每次當一個庫修改了,就必須確認它的已分配的組塊還是和之前的大小,並且,創建了新的庫,得為它找空間,隨著時間發展,一個系統有數百個庫和各種版本的庫,難免地址空間分裂成大量小的、未使用而又不再能使用的小洞,而且,每個系統,從庫到存儲器的分配都是不同的

方法2

編譯庫代碼

不需要鏈接器修改庫代碼,可以在任何地址載入和執行代碼,這樣的代碼叫位置無關的代碼(PIC代碼)


異常是一種形式的異常控制流,它一部分是由硬體實現的,一部分是由操作系統實現的

具體細節隨系統不同,而有所不同

對於每個系統而言,基本的思想都是相同的

異常就是控制流中的突變,用來響應處理器狀態中的某些變化

異常處理過程

在任何情況下,當處理器檢測到有事件發生時,他就會通過一張叫做異常表(exception table) 的跳轉表,進行一個間接過程調用(異常),到一個專門設計用來處理這類事件的操作系統子程序---異常處理程序(exception handler)

當異常處理程序完成處理後,根據異常類型,會發生以下三種情況中的一種:

將控制返回給當前指令Icurr(異常發生時正在執行的指令)

將控制返回Inext(如果沒有發生異常將會執行的下一條指令)

終止被中斷的程序

8.1.1 異常處理

每種類型的異常都分配了一個唯一的非負整數的異常號(exception number),一些是由處理器的設計者分配,其他由操作系統內核(操作系統常駐存儲器的部分)的設計者分配

處理器設計者分配:被零除、缺頁、存儲器訪問違例、斷點以及算術溢出

操作系統內核分配: 系統調用、來自外部I/O設備的信號

系統啟動時,操作系統分配和初始化一張稱為異常表的跳轉表

異常號是異常表中的索引,異常表的起始地址放在一個叫做異常表基寄存器(exception table base register)的特殊CPU寄存器里

異常類似於過程調用,不同之處:

如果控制從一個用戶程序轉移到內核,所有這些項目item都被壓到內核棧中,而不是壓到用戶棧中

異常處理程序運行在內核模式下,意味著他們對所有的系統資源都有完全的訪問許可權

過程調用時,跳轉之前,處理器將返回地址壓到棧中,然而處理異常時,根據異常類型,返回地址要麼是當前指令,要麼是下一條指令

8.1.3 異常的類型

中斷

硬體中斷不是由任何一條專門的指令造成的,從這個意義上來說是非同步的

I/O設備,例如網路適配器、磁碟控制器和定時器晶元,通過向處理器晶元上的一個管腳發信號,並把異常號放到系統匯流排上,來觸發中斷,這個異常號標識了引發中斷的設備

陷阱

有意的異常,執行一條指令的結果

將控制返回到下一條指令

用途: 在用戶程序和內核之間提供一個像過程一樣的介面, 叫做系統調用

系統調用和普通的函數調用區別: 普通函數運行在用戶模式(user model) ,用戶模式限制了函數可以執行的指令的類型,只能訪問與調用函數相同的棧;

系統調用運行在內核模式(kernel mode)中,內核模式允許系統調用執行指令,並訪問定義在內核中的棧

故障

由錯誤情況引起,可能被故障處理程序修正

能修正,控制返回到故障指令,重新執行

不能修正,處理程序返回到內核中的abort常式,abort常式會終止引起故障的應用程序

終止

終止是不可恢復的致命錯誤造成的結果--典型的是一些硬體錯誤,比如DRAM或者SRAM位被損壞時發生的奇偶錯誤

將控制返回給一個abort常式,該常式會終止這個應用程序


當我們在一個現代系統上運行一個程序時,我們會得到一個假象,就好像我們的程序是系統中當前運行的唯一程序,我們的程序好像是獨佔的使用處理器和存儲器,處理器就好像是無間斷的一條接一條地執行我們程序中的指令,最後,我們程序中的代碼和數據顯得好像是系統存儲器中唯一的對象,這些假象都是通過進程的概念提供給我們的

一個執行中程序的實例

每個程序都運行在某個進程的上下文(context)中

上下文由程序正確運行所需的狀態組成的,包括存放在存儲器中的程序的代碼和數據、棧、通用目的存儲器的內容、程序計數器、環境變數以及打開文件描述符的集合

進程提供給應用程序的關鍵抽象

一個獨立的邏輯控制流,使我們覺得獨佔使用處理器

一個私有的地址空間,使我們覺得獨佔的使用存儲器系統

8.2.1 邏輯控制流

一般而言,每個邏輯控制流與其它邏輯流想獨立

的那個進程使用進程間通信(IPC)機制,比如管道、套介面、共享存儲器和信號量,顯示地與其它進程交互時,唯一例外就會發生

若干個邏輯流在時間上重疊,被稱為並發進程,這兩個進程被稱為並發運行

進程和其他進程輪換運行的概念叫多任務,一個進程執行它的控制流的一部分的每一時間段叫做時間片

多任務 也叫做時間分片

8.2.2 私有地址空間Linux進程的地址空間的結構

地址空間底部的四分之三是預留給用戶程序的,包括通常的文本、數據、堆和棧段

頂部的四分之一是預留給內核的(比如執行系統調用時,使用的代碼、數據和棧)

8.2.3 用戶模式和內核模式

處理器是用某個控制寄存器中的一個方式位(mode bit)來提供這種功能,描述了進程當前享有的權力

運行在內核模式的進程,可以執行指令集中的任何指令,並且可以訪問系統中任何存儲器位置

用戶模式中的進程不能直接引用地址空間中內核區內的代碼和數據,必須通過系統調用介面間接訪問內核代碼和數據

進程從用戶模式變為內核模式的唯一方法是通過諸如中斷、故障或者陷入系統調用這樣的異常

8.2.4 上下文切換

操作系統內核利用一種稱為上下文切換(context switch)的較高級形式的異常控制流來實現多任務

內核可以決定搶佔當前進程,重新開始一個先前被搶佔的進程,這種決定叫調度(scheduling) ,是由內核中稱為調度器(scheduler) 的代碼處理的

上下文切換過程

保存當前進程的上下文

恢復某個先前被搶佔進程所保存的上下文

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

中斷也可能引發上下文切換,比如,所有的系統都有某種產生周期性定時器中斷的機制,典型的為每1ms或10ms,每次發生定時器中斷時,內核就能判定當前進程已經運行了足夠長的時間了,並切換到一個新的進程

切換過程

磁碟讀取數據需要較長時間(數量級為十幾ms),所以內核執行從進程A到進程B的上下文切換,而不是等待

注意,切換之前,內核正代表進程A在用戶模式下執行指令

在切換的第一步中,內核代表進程A在內核模式下執行指令,然後在某一時刻,內核開始代表B進程執行指令(內核模式),切換完成後,內核代表B在用戶模式下執行指令

B在用戶模式下運行一會兒,直到磁碟發出一個中斷信號,表示數據已經傳到存儲器,內核判定B已經運行足夠長時間,就執行一個從B切換A的上下文切換,將控制返回給A中緊隨在read系統調用之後的那條指令,進程A繼續運行,直到下一次異常發生

高速緩存污染和異常控制流

一般而言,硬體高速緩存存儲器(L1,L2,L3非常小)不能和諸如中斷和上下文切換這樣的異常控制流很好的交互

如果當前進程被中斷,那麼對於中斷處理程序來說,高速緩存是冷的

如果處理程序從主存中訪問了足夠多的表目,那麼被中斷的進程繼續時,高速緩存對它來說也是冷的

當一個進程在上下文切換後繼續執行時,高速緩存對於應用程序而言也是冷的,必須再次熱身


我們把系統調用和它們相關的包裝函數可互換地 稱為系統級函數


8.4.2進程的三種狀態

運行 進程要麼在CPU上執行,要麼等待被執行且最終會被調度

暫停 進程的執行被掛起(suspended) ,且不會被調度 ,當收到SIGSTOP、SIGTSTP、SIDTTIN或者SIGTTOU信號時,進程就暫停,並且保持暫停直到它收到一個SIGCONT信號,這時,進程再次開始運行

終止 進程永遠地被停止了; 三種原因會終止進程: 收到一個信號,該信號的默認行為是終止進程; 從主程序返回; 調用exit 函數.

fork函數

父進程通過調用fork函數創建一個新的運行子進程

新創建的子進程幾乎,但不完全與父進程相同

子進程得到與父進程用戶級虛擬地址控制項相同的一份拷貝,包括文本、數據和bss段、堆以及用戶棧,子進程還獲得與父進程 任何打開文件描述符 相同的拷貝,意味著 當父進程調用fork時,子進程可以讀寫父進程中打開的任何文件

父進程和新創建的子進程之間最大的區別在於它們有不同的PID

fork函數只被調用一次,卻會返回兩次: 一次是在調用進程(父進程)中,一次在子進程中, 父進程中,fork返回子進程的PID,子進程中fork返回0

fork返回值用來分辨程序是在父進程還是在子進程中執行的

8.4.3 回收子進程

當一個進程由於某種原因終止時,內核並不立即從系統中清除,而是被保持在一種終止狀態中,直到被它的父進程回收(reaped)

當父進程回收已終止的子進程時,內核將子進程的退出狀態傳遞給父進程,然後拋棄已終止的進程,從此時開始,該進程就不存在;額

一個終止了但還未被回收的進程稱為僵死進程(zombie)

如果父進程沒有回收它的僵死子進程,就終止了,內核會安排init進程來回收他們

init進程的PID為1,並且在系統初始化時,由內核創建

8.4.4 讓進程休眠


更高層軟體形式的異常,稱為Unix信號,它允許進程中斷其他進程

一個信號就是一條消息,通知進程一個某種類型的事件已經在系統中發生了

每種信號類型都對應某個類型的系統事件

底層的硬體異常是由內核異常處理程序處理的,對用戶進程而言通常是不可見的

信號提供了一種機制向用戶進程通知這些異常的發生

信號的案例

ctrl-c,內核會發送SIGINT信號給前台進程

一個進程可以通過發送一個SIGKILL(號碼9)信號強制終止另外一個進程

當一個子進程終止或者暫停時,內核會發送一個SIGCHLD(號碼17)給父進程

8.5.1 信號術語

一個只發出而沒有被接收的信號叫做待處理信號(pending signal)

在任何時刻,一個類型至多只會有一個待處理信號,接下來發送到這個進程的K類型信號不會排隊等待,只是被簡單地丟棄

一個進程可以選擇性得阻塞接收某種信號,當一個信號被阻塞時,仍可以被發送,但是產生的待處理信號不會被接收,直到進程取消對這種信號的阻塞

8.5.2 發送信號進程組

每個進程都只屬於一個進程組,進程組是由一個正整數進程組ID來標識的

默認的,一個子進程和它的父進程同屬於一個進程組

一個進程可以通過使用setpgid函數來改變自己或者其他進程的進程組

8.5.3 接收信號8.5.4 信號處理問題

系統信號可以被中斷. 像read、write和accept這樣的系統調用潛在的會阻塞進程一段較長的時間,稱之為慢速系統調用

在某些系統中,當處理程序捕捉到一個信號時,被中斷的慢速系統調用在信號處理程序返回時,不再繼續,而是立即返回給用戶一個錯誤條件

8.5.5 可移植的信號處理

Posix標準定義了sigaction函數,顯式的指定他們想要的信號處理語義

Signal包裝函數設置了一個信號處理程序

只有這個處理程序當前正在處理的那種類型的信號被阻塞

和所有信號實現一樣,信號不會排隊等待

只要可能,被中斷的系統調用會自動重啟


C提供了一種形式的用戶級異常控制流,稱為 非本地跳轉(nonlocal jump).它將控制直接從一個函數轉移到另一個當前正在執行的函數,而不需要經過正常的調用-返回序列

非本地跳轉的一個重要應用就是允許從一個深層嵌套的函數調用中立即返回,通常是由檢測到某個錯誤情況引起的

如果在一個深層嵌套的函數調用中發現一個錯誤情況,可以使用非本地跳轉直接返回到一個普通的本地化的錯誤處理程序,而不是費力地解開調用棧

非本地跳轉的另一個重要應用,是使一個信號處理程序分支到一個特殊的代碼位置,而不是返回到被信號到達中斷了的指令的位置


Unix系統提供了大量的監控和操作進程的有用工具:

strace:列印一個程序和它的子進程調用的每個系統調用的軌跡

ps:列出系統中當前的進程(包括僵死進程)

top:列印出關於當前進程資源使用的信息

kill:發送一個信號給進程

/proc:一個虛擬文件系統,以ASCII文本格式輸出大量內核數據結構的內容,用戶程序可以讀取這些內容;比如輸入 "cat /proc/loadavg",觀察在你的Linux系統上當前的平均負載


在宏觀時間尺度上,處理器不停地在許多任務之間切換,一次分配給每個任務大約5~20ms

用戶感覺上任務是在同時進行的,因為人不能夠察覺短於大約100ms的時間段,在這段時間內,處理器可以執行幾百萬條指令

9.1.1 進程調度和計時器中斷

外部事件,例如鍵盤、磁碟操作和網路活動,會產生中斷信號,中斷信號使得操作系統調度程序得以運行,可能還會切換到另一個進程

我們也希望處理器從一個進程切換到另一個,這樣用戶看上去就像處理器在同時執行許多程序

計算機有一個外部計時器,周期性向處理器發送中斷信號,

中斷信號之間的時間稱為間隔時間(interval time)

中斷髮生時,調度程序可以選擇要麼繼續當前正在執行的進程,要麼切換到另一個進程

間隔時間必須足夠短,保證任務間切換足夠頻繁

從一個進程切換到另外一個進程需要幾千個時鐘周期來保存當前進程的狀態,並且為下一個進程準備好狀態,間隔時間太短會導致性能很差

典型的計時器間隔範圍是 1~10ms

操作系統函數,例如處理缺頁、輸入或者輸出(print函數),列印log很耗性能

9.1.2 從應用程序的角度看時間


對獲得程序性能的近似值有用,粒度太粗,不能用於持續時間小於100ms的測量

有系統偏差,過高的估計計算時間,平均大約4%

優點: 它的準確性不是非常依賴於系統負載


運行在時鐘周期級的計時器,是一個特殊的寄存器,每個時鐘周期他都會加1

不是所有的處理器都有這樣的計數器


系統中引入了幾個對性能測量有很大影響的特性

頻率變化的時鐘: 為了降低功耗,未來的系統會改變時鐘頻率,因為功耗直接與時鐘頻率相關


每個系統都是不同的

試驗可以是非常有啟迪性的

在負載很重的系統上獲得準確的計時特別困難

試驗建立必須控制一些造成性能變化的因素 高速緩存能夠極大地影響一個程序的執行時間,傳統的技術是在計時開始之前,清空高速緩存中的所有有用的數據,或是在開始時,把通常會在高速緩存中的所有數據都載入進來


存儲器很容易被破壞,如果某個進程不小心寫了另一個進程使用的存儲器,那麼進程可能以某種完全和程序邏輯無關的令人迷惑的方式失敗

虛擬存儲器是硬體異常、硬體地址翻譯、主存、磁碟文件和內核軟體的完美交互,它為每個進程提供了一個大的、一致的、私有地址空間

虛擬存儲器提供了三個重要的能力:

他將主存看成是一個存儲在磁碟上的地址空間的高速緩存,在主存中只保存活動區域,並根據需要在磁碟和主存之間來回傳送數據,通過這種方式,高效的使用了主存

它為每個進程提供了一致的地址空間,從而簡化了存儲器管理

他保護了每個進程的地址空間不被其他進程破壞


計算機系統的主存被組織成一個由M個連續的位元組大小的單元組成的數組,每個位元組都有一個唯一的物理地址(physical address),第一個位元組的地址為0,接下來的位元組地址為1,再下一個為2,依次類推

CPU訪問存儲器的最自然的方式就是使用物理地址,這種方式稱為物理定址(physical addressing)

為通用計算設計的現代處理器使用的是虛擬定址(virtual addressing)

虛擬定址的過程

CPU通過生成一個虛擬地址來訪問主存,地址翻譯(address translation)將虛擬地址轉換為物理地址

地址翻譯需要CPU硬體和操作系統之間的緊密合作

CPU晶元上叫做MMU(memory management unit,存儲器管理單元)的專用硬體,利用存放在主存中的查詢表來動態翻譯虛擬地址,該表的內容由操作系統管理的


地址空間是一個非負整數地址的有序集合

如果地址空間中的整數是連續的,那麼是一個線性地址空間

在一個帶虛擬存儲器的系統中,CPU從一個有

個地址的地址空間中生成虛擬地址,稱為虛擬地址空間

一個地址空間的大小是由表示最大地址所需要的位數來描述的

現代系統典型地支持32位或64位虛擬地址空間

一個系統還有一個物理地址空間,與系統中物理存儲器的M個位元組(byte)相對應


10.3.1 DRAM高速緩存的組織結構10.3.2 頁表

頁表將虛擬頁映射到物理頁,每次地址翻譯硬體將一個虛擬地址轉換為物理地址時,都會讀取頁表

操作系統負責維護頁表的內容,以及在磁碟與DRAM之間來回傳送頁

10.3.3 頁命中10.3.4 缺頁

DRAM緩存不命中稱為缺頁

在磁碟和存儲器之間傳送頁的活動叫做交換(swapping)或者頁面調度(paging)

當有不命中發生時,才換入頁面的這種策略被稱為按需頁面調度(demand paging)

10.3.5 分配頁面10.3.6 局部性再次搭救

只要我們的程序有好的時間局部性,虛擬存儲器系統就能工作得相當好

如果工作集的大小超出了物理存儲器的大小,那麼程序將產生一種不幸的狀態,叫做顛簸(thrashing),這時頁面將不斷地換進換出


10.4.1 簡化鏈接

獨立的地址空間允許每個進程為它的存儲器映像使用相同的基本格式,而不管代碼和數據實際存放在物理存儲器的何處

10.4.2 簡化共享

某些情況下,需要進程來共享代碼和數據,例如,每個進程必須調用相同的操作系統內核代碼,而每個C程序都會調用標準庫中的程序,比如printf

操作系統通過將不同進程中適當的虛擬頁面映射到相同的物理頁面,從而多個進程共享這部分代碼的一個拷貝,而不是在每個進程中都包括單獨的內核和C標準庫的拷貝

10.4.3 簡化存儲器分配

當進程要求額外的堆空間時,操作系統會分配一個適當數字(例如K)個連續的虛擬存儲器頁面,並且將它們映射到物理存儲器中任意位置的K個任意的物理頁面

由於頁表的工作方式,操作系統沒有必要分配K個連續的物理存儲器頁面,頁面可以隨機的分散在物理存儲器中

10.4.4 簡化載入

映射一個連續虛擬頁面的集合到任意一個文件中的任意一個位置,叫存儲器映射(memory mapping)


SUP位表示進程是否必須運行在內核模式下,才能訪問該頁

如果一條指令違反了這些許可條件,那麼CPU就觸發一個一般保護故障,將控制傳遞給一個內核中的異常處理程序,Unix Shell稱這 為 段錯誤(segmentation fault)


地址翻譯是一個N元素的虛擬地址空間中的元素和一個M元素的物理地址空間中元素之間的映射


10.8.1 再看共享對象

一個對象可以被映射到虛擬存儲器的一個區域,要麼作為共享對象,要麼作為私有對象

一個共享對象映射到的虛擬存儲器區域叫做共享區域,私有對象映射到的虛擬存儲器區域叫做私有區域

一個進程對共享對象的任何寫操作,對於也把這個共享對象映射到它們虛擬存儲器的其它進程而言,是可見的,而且,這些變化會反映在磁碟上的原始對象中

私有對象使用一種叫做寫時拷貝(copy-on-write)的巧妙技術被映射到虛擬存儲器中的

兩個進程將一個私有對象進程映射,共享這個對象同一個物理拷貝,對於每個映射私有對象的進程,相應私有區域的頁表條目都被標記為只讀,並且區域結構被標記為私有的寫時拷貝

只要沒有進程試圖寫它自己的私有區域,它們就可以繼續共享物理存儲器中對象的一個單獨拷貝,然而,只要有一個進程試圖寫私有區域內的某個頁面,這個寫操作就會觸發一個保護故障

寫時拷貝過程

當寫操作觸發保護故障時,故障處理程序就會在物理存儲器中創建這個頁面的一個新拷貝,更新頁表條目指向這個新的拷貝,然後恢復這個頁面的可寫許可權,當故障處理程序返回時,CPU重新執行這個寫操作,在新創建的頁面上,這個寫操作就可以正常執行了

通過延遲私有對象中的拷貝直到最後可能的時刻,寫時拷貝最充分地使用了稀有的物理存儲器

10.8.2 再看fork函數

fork函數被當前進程調用時,內核為新進程創建各種數據結構,並分配唯一的PID,對當前進程的mm_struct、區域結構和頁表的原樣拷貝,標記兩個進程中的每個頁面為只讀的,並標記兩個進程中的每個區域結構為私有的寫時拷貝

當fork在新進程中返回時,新進程現在的虛擬存儲器剛好和調用fork時存在的虛擬存儲器相同,當兩個進程中的任一個後來進行寫操作時,寫時拷貝機制就會創建新頁面,因此,也就為每個進程保持了私有地址空間的抽象概念

10.8.3 再看execve函數

execve函數在當前進程中載入並運行包含在可執行目標文件a.out中的程序,用a.out程序有效地替代了當前程序

刪除已存在的用戶區域

映射私有區域

映射共享區域

設置程序計數器

10.8.4 使用mmap函數的用戶級存儲器映射

Unix進程可以使用mmap函數來創建新的虛擬存儲器區域,並將對象映射到這些區域中


雖然可以使用低級的mmap和munmap函數來創建和刪除虛擬存儲器的區域,但是大部分C程序在運行時需要額外虛擬存儲器時,使用一種動態存儲器分配器(dynamic memory allocator)

一個動態存儲器分配器維護著一個進程的虛擬存儲器區域,稱為堆(heap)

在大多數Unix系統中,堆是一個請求二進位零的區域

對於每個進程,內核維護著一個變數brk(break),它指向堆的頂部

分配器將堆視為一組不同大小的塊(block)的集合來維護

每個塊就是一個連續的虛擬存儲器組塊(chunk),要麼是已分配,要麼是空閑的

已分配塊顯示地保留為供應用使用,直到被釋放,這種釋放要麼是應用顯示執行,要麼是存儲器分配器自身隱式執行(垃圾回收)

顯示分配器(explicit allocator)

應用顯示地釋放任何已分配的塊,例如,C標準庫的malloc函數分配塊,free函數來釋放一個塊

隱式分配器(implicit allocator)

要求分配器檢測何時一個已分配塊不再被程序使用,然後釋放這個塊,隱式分配器也叫做垃圾收集器(garbage collector)

自動釋放未使用的已分配的塊的過程叫做 垃圾收集(garbage collection)

10.9.1 malloc和free函數

malloc函數返回一個指針,指向大小為至少size位元組的存儲器塊

調用free後,指針仍然指向被釋放的塊,應用在這個塊被一個新的malloc調用重新初始化之前,不再使用這個指針

10.9.2 為什麼要使用動態存儲器分配

知道程序實際運行時,才知道數據結構的大小

10.9.3 分配器的要求和目標顯式分配器必須在一些約束條件下工作:

處理任意請求序列分配器不可以假設分配和釋放請求的順序

立即響應請求分配器必須立即響應分配請求,不允許分配器為了提高性能重新排列或者緩衝請求

只使用堆為了使分配器是可擴展的,使用的任何非標量數據結構都必須保存在堆里

對齊塊分配器必須對齊塊,使得它們可以保存任何類型的數據對象;在大多數系統中,意味著分配器返回的塊是8位元組(雙字)邊界對齊的(int64,float64等)

不修改已分配的塊分配器只能操作或改變空閑塊;一旦被分配了,就不允許修改或者移動它

目標1:最大化吞吐率吞吐率:在單位時間裡完成的請求數(例如:1秒鐘500個分配請求,500個釋放請求,吞吐率就是沒秒1000次操作)

目標2:最大化存儲器利用率

10.9.4 碎片

當未使用的存儲器但不能用來滿足分配請求時,碎片現象

內部碎片

已分配塊比有效載荷大 比如分配器對已分配塊,最小分配8位元組,滿足對齊約束條件,但是某個有效載荷是2位元組

外部碎片

空閑存儲器合計起來足夠滿足一個分配請求,但是沒有一個單獨的空閑塊足夠大可以來處理這個請求

外部碎片是難以量化和不可預測的,所以分配器典型地採用啟發式策略來試圖維持少量的大空閑塊,而不是維持大量的小空閑塊

10.9.5 實現問題

空閑塊組織: 我們如何記錄空閑塊

放置: 我們如何選擇一個合適的空閑塊來放置一個新分配的塊

分割: 在將一個新分配的塊放置到某個空閑塊之後,如何處理這個空閑塊中的剩餘部分?

合併: 我們如何處理一個剛剛被釋放的塊?

10.9.6 隱式空閑鏈表

塊=一個字的頭部(4位元組,32bit)+有效載荷+填充

頭部編碼了快的大小(包括頭部和所有的填充)

隱式空閑鏈表

優點: 簡單

缺點: 任何操作的開銷,例如放置分配的塊,要求空閑鏈表的搜索與堆中已分配塊和空閑塊的總數呈線性關係

10.9.7 放置分配的塊

當應用請求一個k位元組的塊時,分配器搜索空閑鏈表,查找一個足夠大、可以放置所請求塊的空閑塊,分配器執行這種搜索的方式是由放置策略(placement policy)確定的

常見的策略首次適配(first fit)

從頭開始搜索空閑鏈表,選擇一個合適的空閑塊

優點: 趨向於將大的空閑塊保留在鏈表的後面

缺點: 在靠近鏈表起始處留下小空閑塊的"碎片",增加了對較大塊的搜索時間

下一次適配(next fit)

和首次適配相似,只不過不是從鏈表的起始處開始每次搜索,而是從上一次查詢結束的地方開始

源於這樣的想法: 如果我們上一次在某個空閑塊里已經發現了一個匹配,那麼很可能下一次我們也能在這個剩餘塊中發現匹配

下一次適配比首次適配運行起來更快一些

下一次適配的存儲器利用率比首次適配低得多

最佳適配(best fit)

檢查每個空閑塊,選擇匹配所需請求大小的最小空閑塊

比首次適配和下一次適配的利用率都要高一些

缺點: 再簡單空閑鏈表組織結構中,比如隱式空閑鏈表,使用最佳適配 要求對堆進行徹底的搜索

10.9.8 分割空閑塊

一旦找到一個匹配的空閑塊,就必須決定,分配這個空閑塊中多少空間

用整個空閑塊,這種方式簡單而快捷,缺點是 會造成內部碎片

將這個空閑塊分成兩部分,第一部分變成分配塊,剩下的變成一個新的空閑塊

10.9.9 獲取額外的堆存儲器

如果分配器不能找到合適的空閑塊,將發生什麼?

合併那些在存儲器中物理上相鄰的空閑塊來創建一些更大的空閑塊

如果1還是不能生成一個足夠大的塊,或者空閑塊已經最大程度地合併了,分配器會向內核請求額外的堆存儲器,通過調用mmap,或者sbrk函數

3. 以上任一種情況下,分配器都會將額外的存儲器轉化成一個大的空閑塊,插入到空閑鏈表中,然後將被請求的塊放置在這個新的空閑塊中10.9.10 合併空閑塊

當分配器釋放一個已分配塊,新釋放的空閑塊可能與其它塊相鄰,這些鄰接的空閑塊可能引起一種現象,叫做假碎片(fault fragmentation)

這些假碎片被切割為小的、無法使用的空閑塊,3個字+3個字 無法分配給4個字

為了解決假碎片問題,任何實際的分配器都必須合併相鄰的空閑塊,這個過程稱為合併(coalescing)

何時執行合併立即合併(immediate coalescing)

在每次一個塊被釋放時,就合併所有的相鄰塊 ,可以在常數時間內執行完成

缺點: 在某些請求模式下,塊會反覆的合併,然後馬上分割,產生大量不必要的分割和合併

推遲合併(deferred coalescing)

等到某個稍晚的時候再合併空閑塊

例如,分配器可以推遲合併,直到某個分配請求失敗,然後掃描整個堆,合併所有的空閑塊

10.9.11 帶邊界標記的合併

當前塊的頭部指向下一個塊的頭部,可以檢查這個指針以判斷下一個塊是否是空閑的,如果是,就將它的大小簡單地加到當前塊頭部的大小上,這兩個塊在常數時間內被合併

邊界標記(boundary tag),允許在常數時間內進行對前面塊的合併

在每個塊的結尾處添加一個腳部(footer邊界標記),通過檢查腳部,判斷前面一個塊的起始位置和狀態

邊界標記的概念是簡單優雅的,對不同類型的分配器和空閑鏈表組織都是通用的

缺陷: 要求每個塊都保持一個頭部和一個腳部,在應用程序操作許多個小塊時,會產生顯著的存儲器開銷,例如: 如果一個圖形應用反覆的調用malloc和free,來動態的創建和銷毀圖形節點,並且每個圖形節點都只要求兩個存儲器字,那麼頭部和腳部將佔用每個已分配塊的一半的空間

邊界標記的優化方法

只有在前面的塊是空閑時,才會需要用到它的腳部,如果我們把前面塊的已分配/空閑位存放在當前塊中多出來的低位中,那麼已分配的塊就不需要腳部了,空閑塊仍然需要腳部

10.9.12 綜合: 實現一個簡單的分配器10.9.13 顯示空閑鏈表(雙向空閑鏈表)

堆可以組織成一個雙向空閑鏈表,每個空閑塊中,都包含一個pred(祖先)和succ(後繼)指針

使用雙向鏈表,使首次適配的分配時間從塊總數的線性時間減少到了空閑塊數量的線性時間

空閑鏈表中對塊排序的策略

後進先出(LIFO)

新釋放的塊放置在鏈表的開始處,釋放塊可以在常數時間內完成,如果使用邊界標記,合併也可以在常數時間內完成

按照地址順序來維護鏈表

釋放一個塊需要線性時間的搜索,來定位合適的祖先; 有更高的存儲器利用率,接近最佳適配的利用率

顯式鏈表的缺點

空閑塊必須足夠大,以包含所有需要的指針,以及頭部和可能的腳部

導致更大的最小塊大小,潛在地提高了內部碎片的程度

10.9.14 分離的空閑鏈表(分離存儲)

一種流行的減少分配時間的方法,通常稱為分離存儲(segregated storage),維護多個空閑鏈表,其中每個鏈表中的塊有大致相等的大小

一般的思路是將所有可能的塊大小分成一些等價類,也叫做大小類(size class)

分配器維護著一個空閑鏈表數組,每個大小類就是一個空閑鏈表,按照大小的升序排列,當分配器需要一個大小為n的塊時,它就搜索相應的空閑鏈表,如果它不能找到合適的塊與之匹配,它就搜索下一個鏈表,以此類推

有很多種分離存儲方法,主要區別在於: 如何定義大小類,何時進行合併,何時向操作系統請求額外的堆存儲器,是否允許分割,等等

簡單分離存儲(simple segregated storage)

每個大小類的空閑鏈表包含大小相等的塊,每個塊的大小就是這個大小類中最大元素的大小,例如,如果某個大小類定義為,那麼這個類的空閑鏈表全由大小為32的塊組成

分配時,檢查相應的空閑鏈表,如果鏈表為非空,簡單的分配其中第一個塊的全部,空閑塊是不會分割以滿足分配請求的

如果鏈表為空,分配器就向操作系統請求一個固定大小的額外存儲器組塊,將這個組塊(chunk)分成大小相等的塊,並將這些塊鏈接起來形成新的空閑鏈表

要釋放一個塊,只需要簡單地將這個塊插入到相應的空閑鏈表的前部

理解

將空閑內存按照固定大小分塊,方便管理,比如大小為32的塊組成的鏈表,當系統向分配器請求分配的內存大小在17-32這個範圍內是,就從32的鏈表中取一個空閑塊使用

有效減少空閑鏈表的數量,降低維護難度

有時為了減少內部碎片,需要減小17-32這個範圍

優點

分配和釋放塊都是很快的常數時間操作

每個組塊中都是大小相等的塊,不分割,不合併,這意味著每個塊只有很少的存儲器開銷

沒有合併,所以已分配塊不需要頭部(已分配/空閑標記),也不需要腳部

分配和釋放操作都是在空閑鏈表的起始處操作,所以鏈表只需要是單向的

唯一在任何塊中都需要的欄位是每個空閑塊中的一個字的succ指針(後繼),因此最小的塊大小就是一個字

缺點

因為空閑塊是不會被分割的,所以會造成內部碎片,比如大量17大小的對象,使用32的塊

因為不會合併空閑塊,因此,某些引用模式會引起極多的外部碎片,比如說請求的都是較大對象,大小類比較小的空閑鏈表的利用率就很低,不會合併,被浪費著

合併方式對付外部碎片

分配器記錄操作系統返回的每個存儲器組塊(chunk)中的空閑塊的數量,無論何時,如果有一個組塊(比如32的大小類組塊)完全由空閑塊組成,那麼分配器就從當前大小類中刪除這個組塊,回收內存,供其它大小類使用

分離適配(segregated fit)

每個空閑鏈表是和一個大小類相關聯的,並且被組織成某種類型的顯式或隱式鏈表

每個鏈表包含潛在的大小不同的塊,這些塊的大小是大小類的成員

過程

確定請求的大小類,對適當的空閑鏈表做首次適配,查找一個合適的塊

如果找到一個,那麼分割它,將剩餘的部分插入到適當的空閑鏈表中

如果找不到合適的塊,就搜索下一個更大的大小類的空閑鏈表,如此重複,直到找到一個合適的塊

如果最後未找到合適的塊,就請求額外的堆存儲器,從這個新的堆存儲器中分配一個塊,將剩餘的部分放置到最大的大小類中

要釋放一個塊,我們執行合併,將結果放置到相應的空閑鏈表中

優缺點

是一種常見的選擇,C標準庫中提供的GNU malloc包就是採用這種方法

既快速,對存儲器的使用也很有效率

搜索時間減少了,因為搜索被限制在堆的某個部分,而不是整個堆

有一個有趣的事實: 對分離空閑鏈表的簡單的首次適配搜索相當於對整個堆的最佳適配搜索

夥伴系統

夥伴系統(buddy system)是分離匹配的一種特例,其中每個大小類都是2的冪,基本的思路是假設一個堆的大小為2的m次方個字,我們為每個塊大小為2的k次方維護一個分離空閑鏈表,其中0

請求塊大小向上舍入到最接近的2的冪

最開始時,只有一個大小為2的m次方個字的空閑塊

過程

優點

快速搜索和快速合併

缺點

要求塊大小為2的冪可能導致顯著的內部碎片,因此夥伴系統分配器不適合通用目的的工作負載

對於某些與應用相關的工作負載,其中塊大小預支知道是2的冪,夥伴系統分配器就很有吸引力了


在諸如C malloc包這樣的顯示分配器中,應用通過調用malloc和free來分配和釋放堆塊,應用要負責釋放所有不再需要的已分配塊

垃圾收集器(garbage collector)是一種動態存儲分配器, 它自動釋放程序不再需要的已分配塊,這些塊被稱為垃圾(garbage)

自動回收堆存儲的過程叫做垃圾收集(garbage collection)

在一個支持垃圾收集的系統中,應用顯式分配堆塊,但是從不顯式地釋放它們,垃圾收集器定期識別垃圾塊,並相應地調用free,將這些塊放回到空閑鏈表中

10.10.1 垃圾收集器的基本要素

垃圾收集器將存儲器視為一張有向可達圖(reachability graph)

一組根節點(root node)和一組堆節點(heap node),每個堆節點對應於堆中的一個已分配塊

根節點對應於這樣一種不在堆中的位置,包含指向堆中的指針,可以是寄存器,棧里的變數,或者是虛擬存儲器中讀寫數據區域內的全局變數

當存在一條從任意根節點出發併到達p的有向路徑時,節點p是可達(reachable)

在任何時刻,和垃圾相對應的不可達節點是不能被應用再次使用的

垃圾收集器的角色是 維護可達圖的某種表示,並通過釋放不可達節點並將它們返回給空閑鏈表,來定期地回收它們

像Java這樣的語言的垃圾收集器,對應用如何創建和使用指針有很嚴格的控制,能夠維護可達圖的一種精確的表示,因此能夠回收所有垃圾

諸如C和C++這樣的語言的收集器通常不能維持可達圖的精確表示,這樣的收集器叫做保守的垃圾收集器(conservative garbage collector). 從某種意義上來說它們是保守的,也就是每個可達塊都被正確地標記為可達,而一些不可達節點卻可能被錯誤地標記為可達

10.10.2 Mark&Sweep垃圾收集器

由標記(mark)階段和清除(sweep)階段組成

標記階段標記出根節點的所有可達的和已分配的後繼,而後面的清除階段釋放每個未被標記的已分配塊

塊頭部中空閑的低位中的一位用來表示這個塊是否被標記了

10.10.3 C程序的保守Mark&Sweep


10.11.1 間接引用壞指針10.11.2 讀未初始化的存儲器10.11.3 允許棧緩衝區溢出

如果一個程序不檢查輸入串的大小就寫入棧中的目標緩衝區,程序就會緩衝區溢出錯誤(buffer overflow bug)

10.11.4 假設指針和它們指向的對象是相同大小的10.11.5 造成錯位錯誤

創建一個n個元素的指針數組,但是隨後試圖初始化這個數組的n+1個元素.這個過程中覆蓋了A數組後面的某個存儲器

10.11.6 引用指針,而不是它所指向的對象


輸入/輸出(I/O)是在主存(main memory)和外部設備(例如磁碟驅動器、終端和網路)之間拷貝數據的過程

輸入: 從I/O設備拷貝數據到主存

輸出: 從主存拷貝數據到I/O設備

在Unix系統中,是通過使用由內核提供的系統級Unix I/O函數來實現這些較高級別的I/O函數的

11.1 Unix I/O

所有的I/O設備,例如網路、磁碟和終端,都被模型化為文件,而所有的輸入和輸出都被當做對相應文件的讀和寫來執行

打開文件

改變當前的文件位置

讀寫文件

關閉文件: 無論進程因為何種原因終止,內核都會關閉所有打開的文件並釋放它們的存儲器資源

11.2 打開和關閉文件11.3 讀和寫文件11.5 讀取文件元數據11.6 共享文件11.7 I/O重定向

12.1 客戶端-伺服器編程模型

每個網路應用都是基於客戶端-伺服器模型的

一個應用是由一個伺服器進程和一個或者多個客戶端進程組成

基本操作是事務(transaction)

客戶端-伺服器事務與資料庫事務

它不是資料庫事務,而且也沒有資料庫事務的特性,例如原子性,在這裡,事務僅僅是客戶端和伺服器之間執行的一系列步驟

12.2 網路

物理上而言,網路是一個按照地理遠近組成的層次系統,最低層是LAN(Local Area Network,區域網),範圍在一個建築或者校園內

最流行的區域網技術是乙太網(Ethernet),被證明在3Mb/s~1Gb/s之間都是相當適合的

每個乙太網適配器都有一個全球唯一的48位地址

一個乙太網段包括一些電纜和一個叫做集線器的小盒子,通常服務於一個小的區域,例如一個房間或者一個樓層。集線器不加分辨地將從一個埠上收到的每個位複製到其他所有的埠上,因此,每台主機都能看到每個位

一台主機可以發送一段位,稱為幀(frame),到這個網段內其他任何主機,每個主機適配器都能看到這個幀,但是只有目的主機實際讀取它

幀=頭位(header,標識源和目的地址以及幀的長度)+有效載荷(payload)

網橋比集線器更充分地利用了電纜帶寬,利用一種聰明的分配演算法,它們隨著時間自動學習哪個主機可以通過哪個埠可達.然後有必要時,有選擇地將幀從一個埠拷貝到其它埠

例如,如果主機A發送一個幀到同網段上的主機B,當該幀到達網橋X的輸入埠時,它將丟棄此幀,因而節省了其它網段上的帶寬

如果主機A發送一個幀到一個不同網段上的主機C,那麼網橋X只會把此幀拷貝到和網橋Y相連的埠上,網橋Y會只把此幀拷貝到與主機C的網橋相連的埠

在層次更高級別中,多個不兼容的區域網可以通過叫做路由器(router)的特殊計算機連接起來,組成一個internet(互聯網路)

internet描述一般概念,而用大寫字母的Internet來描述一種特殊的實際應用(全球IP網際網路)

WAN(Wide-Area Network,廣域網),覆蓋的地理範圍比區域網大

internet(互聯網路),它能由採用完全不同和不兼容技術的各種區域網和廣域網組成,

如何使得某台源主機跨過所有這些不兼容的網路發送數據位到另一台目的主機成為可能呢?

一層運行在每台主機和路由器上的協議軟體,它消除了不同網路之間的差異,這個軟體執行一種協議,控制主機和路由器如何協同工作來實現數據傳輸

命名方法不同的區域網技術有不同和不兼容的方式來為主機分配地址,internet協議通過定義一種的一致的主機地址格式,消除差異,這個地址惟一的標識了它

傳送機制在電纜上編碼位和將這些位封裝成幀方面,不同的網路互聯技術有不同的和不兼容的方式,internet協議通過定義一種把數據位捆紮成不連續的組塊(chunk)--也就是包--的統一方式,消除差異

一個包由包頭(header)和有效載荷(payload)組成,其中包頭包括包的大小以及源主機和目的主機的地址,有效載荷包括從源主機發出的數據位

12.3 全球IP網際網路

可以把網際網路看做一個世界範圍的主機集合,有以下特性:

主機集合被映射為一組32位的IP地址

這組IP地址被映射為一組稱為網際網路域名(Internet domain name)的標識

一個網際網路主機上的進程能夠通過一個連接(connection)和任何其他網際網路主機上的進程通信

12.3.1 IP地址

一個IP地址就是一個32位無符號整數

IP地址以點分十進位表示法表示

12.3.2 網際網路域名

網際網路客戶端和伺服器互相通信時使用IP地址

對人們而言,大整數很難記住,所以定義了一組更加人性化的域名(domain name),以及一種將域名映射到IP地址的機制

每台網際網路主機都有本地定義的域名 localhost,總是映射為本地回送地址(loopback address) 127.0.0.1

12.3.3 網際網路連接

客戶端和伺服器通過在連接(connection)上發送和接收位元組流來通信

從連接一對進程的意義上,連接是點對點(point-to-point)的

從數據可以雙向流動的角度,它是全雙工(full-duplex)的

套接字(socket)是連接的端點(end-point),每個套接字都有相應的套接字地址,由一個IP地址和一個16位的整數埠組成,"地址:埠"表示

客戶端發起連接請求時,客戶端socket地址中的埠是由內核自動分配的,稱為臨時埠(ephemeral port)

伺服器socket中的埠通常是某個知名的埠,和服務對應的,例如Web伺服器通常用埠80,電子郵件伺服器使用埠25

一個連接是由兩端的套接字地址唯一確定的,這對套接字地址叫做套接字對(socket pair)

12.4 套接字介面

套接字介面(socket interface)是一組用來結合Unix I/O函數創建網路應用的函數,大多數現代系統上都實現了它

12.4.1 套接字地址結構12.4.2 socket函數

客戶端和伺服器使用socket函數來創建一個套接字描述符(socket descriptor)

12.4.3 connect函數

客戶端通過調用connect函數來建立和伺服器的連接的

12.4.4 open_clientfd函數

將socket和connect函數包裝成一個叫做open_clientfd的輔助函數是很方便的,當connect函數返回時,我們返回套接字描述符給客戶端,客戶端就可以立即開始用Unix I/O和伺服器通信了

12.4.5 bind函數

告訴內核將伺服器套接字地址和套接字描述符聯繫起來

12.4.6 listen函數12.4.7 open_listenfd函數

將socket、bind和listen函數結合成一個叫做 open_listenfd的輔助函數是很有幫助的,伺服器可以用它來創建一個監聽描述符

12.4.8 accept函數

伺服器通過它來等待來自客戶端的連接請求

accept函數等待來自客戶端的請求 到達偵聽描述符listenfd,然後在addr中填寫客戶端的套接字地址,並返回一個已連接描述符(connected descriptor),這個描述符可被用來利用Unix I/O函數與客戶端通信

12.4.9 echo客戶端和伺服器的示例

簡單的echo伺服器一次只能處理一個客戶端,在客戶端間迭代,稱為 迭代伺服器(iterative server)

EOF意味什麼?

並沒有像EOF字元這樣的一個東西

EOF是由內核檢測到的一種條件,應用程序在它接收到一個由read函數返回的零返回碼時,就會發現出EOF條件

對於磁碟文件,當前文件位置超出文件長度時,會發生EOF

對於網路連接,當一個進程關閉連接,在連接的另一端會發生EOF,另一端的進程在試圖讀取流中最後一個位元組之後,會檢測到EOF

12.5 Web伺服器12.5.1 Web基礎

Web客戶端和伺服器之間的交互用的是一個基於文本的應用級協議,叫 HTTP(Hypertext Transfer Protocol,超文本傳輸協議)

FTP,文件檢索服務

HTML(Hypertext Markup Language,超文本標記語言)

12.5.2 Web內容

內容是與一個MIME(Multipurpose Internet Mail Extensions,多用途的網際郵件擴充協議)類型相關的位元組序列

Web伺服器以兩種方式向客戶端提供內容

取一個磁碟文件,返回給客戶端,瓷盤文件稱為靜態內容(static content),返迴文件給客戶端的過程稱為服務靜態內容(serving static content)

運行一個可執行文件,將輸出返回給客戶端, 可執行文件產生的輸出稱為動態內容(dynamic content),運行程序並返回它的輸出到客戶端的過程稱為服務動態內容(serving dynamic content)

12.5.3 HTTP事務

HTTP標準要求每個文本行都由一個回車和換行符對來結束

HTTP請求

HTTP/1.1定義了一些附加的報頭,例如 緩存和安全等高級特性,還支持一種機制,允許客戶端和伺服器在同一條持久連接(persistent connection)上執行多個事務

HTTP/1.0和HTTP/1.1是互相兼容的,HTTP/1.0的客戶端和伺服器會簡單地忽略HTTP/1.1的報頭

請求報頭為伺服器提供額外的信息,例如瀏覽器的商標名,或者MIME類型

HTTP響應

響應行(response line)+響應報頭(response header)+響應主體(response body)

響應報頭提供了關於響應的附加信息,兩個最重要的報頭是Content-Type,它告訴客戶端響應主體中內容的MIME類型；以及Content-Length,用來指示響應主體的位元組大小

12.5.4 服務動態內容

伺服器如何向客戶端提供動態內容? 一個叫做CGI(Common Gateway Interface,通用網關介面)的實際標準解決了這個問題

客戶端如何將程序參數傳遞給伺服器?

GET請求的參數在URI中傳遞,"?"字元分隔了文件名和參數,每個參數用一個"&"分隔開,參數中不允許有空格,必須用字元串""%20"來表示,其它特殊字元,也存在類似的編碼

POST請求中的參數是在請求主體(request body)中

伺服器如何將參數傳遞給子進程

在伺服器接收到如下請求後(GET /cgi-bin/adder?15000&213 HTTP/1.1),調用fork來創建一個子進程,子進程將CGI環境變數QUERY_STRING設置為 "15000&213",adder程序在運行時可以用Unix getenv函數來引用它,並調用execve在子進程的上下文中執行/cgi-bin/adder程序,常常被稱為CGI程序(遵守CGI標準,常用Perl腳本編寫,也常被稱為CGI腳本)

對於POST請求,子進程也需要重定向標準輸入到已連接描述符,CGI程序從標準輸入中讀取請求體中的參數

伺服器如何將其他信息傳遞給子進程?

CGI定義了大量的其他環境變數,CGI程序在運行時,可以設置這些環境變數

子進程將它的輸出發送到哪裡?

在子進程載入並運行CGI程序之前,它使用Unix dup2函數將標準輸出重定向到和客戶端相關聯的已連接描述符

CGI程序將它的動態內容發送到標準輸出

父進程不知道子進程生成的內容的類型和大小,所以子進程要負責生成Content-type和Content-length響應報頭,以及報頭後的空行


如果邏輯控制流在時間上重疊,那麼它們就是並發(concurrent)的,這種現象,稱為並發性(concurrency),出現在計算機系統的許多不同層面中,例如 硬體異常處理程序、進程和 Unix 信號處理程序

使用應用級並發的應用程序稱為並發程序(concurrent program)

應用級並行

在處理器上進行並行計算

在只有一個 CPU 的單處理器上,並發流是交替的,在任何時間點上,都只有一個流在 CPU 上實際執行,然而在有多個 CPU 的機器,稱為多處理器,可以真正地同時執行多個流,被分成並發流的並行應用,在多處理器的機器上運行得快很多

訪問慢速 I/O 設備

當一個應用正在等待來自慢速 I/O 設備(例如磁碟)的數據到達時,內核會運行其他進程,使 CPU 保持繁忙,通過交替執行 I/O 請求和其他有用的工作,來使用並發性

與人交互

與計算機交互的人要求計算機能同時執行多個任務的能力,例如,列印文檔時,可能想要調整一個窗口的大小,每次用戶請求某種操作時,一個獨立的並發邏輯流被創建來執行這個操作

通過推遲工作以減少執行時間

比如,一個動態存儲分配器可以通過推遲與一個運行在較低優先順序上的並發"合併"流的合併,使用空閑時的 CPU 周期,來降低單個 free 操作的延遲

服務多個網路客戶端

創建一個並發伺服器,為每個客戶端創建各自獨立的邏輯流,同時為多個客戶端服務

三種基本的構造並發程序的方法

進程

每個邏輯控制流都是一個進程,由內核來調度和維護。進程有獨立的虛擬地址空間,想要和其他流通信,控制流必須使用某種顯式的進程間通信(interprocess communication,IPC)機制

I/O 多路復用

應用程序在一個進程的上下文中顯式地調度它們自己的邏輯流,邏輯流被模型化為狀態機,作為數據到達文件描述符的結果,主程序顯式的從一個狀態轉換到另一個狀態,程序是一個單獨的進程,所有的流都共享同一個地址空間

線程

線程是運行在一個單一進程上下文中的邏輯流,由內核調度。可以理解成其他兩種方式的混合體,像進程流一樣由內核進行調度,而像I/O多路復用流一樣共享一個虛擬地址空間

13.1 基於進程的並發編程

在父進程中接受客戶端連接請求,然後創建一個新的子進程為每個新客戶端提供服務

在伺服器派生一個子進程,這個子進程獲取伺服器描述符表的完整拷貝,子進程關閉它的監聽描述符,而父進程關閉它的已連接描述符

13.1.1 基於進程的並發伺服器

通常伺服器會運行很長時間,所以需要一個SIGCHLD處理程序,來回收僵死(zombie)子進程的資源,當SIGCHLD處理程序執行時,SIGCHLD信號是阻塞的,而Unix信號是不排隊的,所以SIGCHLD處理程序必須準備好回收多個僵死子進程的資源

父子進程必須關閉它們各自的connfd拷貝(描述符),以避免存儲器泄漏

因為套接字的文件表表項中的引用計數,直到父子進程的connfd都關閉了,到客戶端的連接才會終止

13.1.2 關於進程的優劣

父子進程間共享狀態信息,模型:共享文件表,但是不共享用戶地址空間

獨立的進程地址空間

優點: 一個進程不可能不小心覆蓋另一個進程的虛擬存儲器

缺點: 使得進程共享狀態信息變得更加困難,為了共享信息,它們必須使用顯式的IPC機制(往往比較慢,進程式控制制和IPC的開銷很高)

13.2 基於I/O多路復用的並發編程

伺服器必須響應兩個互相獨立的I/O事件: 網路客戶端發起連接請求;用戶在鍵盤輸入命令行

I/O多路復用(I/O multiplexing)技術, 基本思路是,使用select函數,要求內核掛起進程,只有在一個或多個I/O事件發生後,才將控制返回給應用程序

問題: 一旦連接到某個客戶端,就會連續回送輸入行,直到客戶端關閉連接,此時,輸入一個命令到標準輸入,將不會得到響應,直到伺服器和客戶端之間結束,更好的辦法是更細粒度的多路復用,伺服器每次循環(至多)回送一個文本行

13.2.1 基於I/O多路復用的並發事件驅動伺服器13.2.2 I/O多路復用技術的優劣優點

比基於進程的設計給了程序員更多的對程序行為的控制,例如,可以設想編寫一個事件驅動的並發伺服器,為某些客戶端提供它們需要的服務

運行在單一進程上下文中,每個邏輯流都可以訪問進程的全部地址空間,流之間共享數據很容易,可以利用調試工具(例如GDB)來調試程序,就像對順序程序那樣

事件驅動設計常常比基於進程的設計要明顯高效的多,不要求有進程上下文切換來調度新的流

缺點

編碼複雜,例如,事件驅動的並發伺服器的代碼比基於進程的伺服器多三倍,並且隨著並發性粒度的減小,複雜性還會上升

粒度: 指每個邏輯流每次時間片執行的指令數目

13.3 基於線程的並發編程

基於進程和基於I/O多路復用兩種方法的混合

一個線程是運行在一個進程上下文中的邏輯流,由內核自動調度,每個線程有自己的線程上下文(thread context),包括一個唯一的整數線程ID(Thread ID,TID)、棧、棧指針、程序計數器、通用目的寄存器和條件碼

運行在一個進程里的所有線程共享該進程的整個虛擬地址空間

13.3.1 線程執行模型

每個進程開始生命周期時,都是單一線程,這個線程稱為主線程(main thread)

在某一時刻,主線程創建一個對等線程(peer thread),從這個時間點開始,兩個線程就並發運行

進程和線程不同點

線程上下文比進程上下文小得多,切換快得多

線程不像進程那樣,不是按照嚴格的父子層次來組織的,和一個進程相關的線程組成一個對等(線程)池(a pool of peers),獨立於其它進程創建的線程,一個線程可以殺死它的任何對等線程,或者等待它的任意對等線程終止,每個對等線程都能讀寫相同的共享數據

13.3.2 Posix線程

Posix線程(Pthreads)是在C程序中處理線程的一個標準介面,在大多數Unix系統上都可用

定義了大約60個函數,允許程序創建、殺死和回收線程,與對等線程安全地共享數據,通知對等線程系統狀態的變化

線程的代碼和本地數據被封裝在一個線程常式(thread routine)中,可以理解成Golang中,傳一個func進去

13.3.3 創建線程13.3.4 終止線程

一個線程是以下列方式之一來終止的

當頂層的線程常式返回時,線程會隱式地終止

pthreadexit 函數: 子線程調用pthreadexit 函數,線程會顯式的終止,該函數會返回一個指向返回值 thread_return的指針

主線程調用用pthreadexit 函數,會等待所有其它對等線程終止,然後再終止主線程和整個進程,返回值為threadreturn

Unix的exit函數: 某個對等線程調用Unix的exit函數,終止進程以及所有與該進程相關的線程

pthreadcancle函數: 另一個對等線程,通過調用pthreadcancle函數來終止指定線程ID對應的線程

13.3.5 回收已終止線程的資源

線程通過調用pthread_join函數等待指定線程終止

pthread_join函數會阻塞,直到線程tid終止,然後回收已終止線程佔用的所有存儲器資源

13.3.6 分離線程

在任何一個時間點上,線程是可結合的(joinable)或者分離的(detached)

一個結合的線程能夠被其它線程收回其資源和殺死,在被回收前,它的存儲器資源(棧)是不釋放的

一個分離的線程是不能被其它線程回收或殺死的,它的存儲器資源在它終止時由系統自動釋放

默認下,線程被創建成可結合的

為了避免存儲器泄漏,每個可結合線程都應該要麼被其它線程顯式的收回,要麼調用pthread_detach函數被分離

13.3.7 初始化線程

pthread_once函數允許你初始化與線程常式相關的狀態

13.3.8 一個基於線程的並發伺服器

傳遞已連接描述符的指針給子線程

不顯式的收回線程,必須分離每個線程,資源才能在終止時被系統收回

13.4 多線程中的共享變數13.4.1 線程存儲器模型

一組並發線程運行在一個進程的上下文中,每個線程都有自己獨立的線程上下文(包括線程ID、棧、棧指針、程序計數器、條件代碼和通用目的的寄存器值)

多個線程共享進程上下文,包括整個用戶虛擬地址空間,打開文件的集合

寄存器從不共享,虛擬存儲器總是共享的

13.4.2 將變數映射到存儲器

多線程的C程序中的變數

全局變數定義在函數之外，虛擬存儲器的讀/寫區域只包含一個實例

本地自動變數（局部變數）函數內部定義的沒有static屬性的變數，在運行時，每個線程的棧都包含它自己的所有局部變數的實例，即使多個線程執行同一個函數，局部變數都屬於線程各自獨有

本地靜態變數定義在函數內部並static屬性的變數，和全局變數一樣，虛擬存儲器的讀/寫區域只包含一個實例

13.4.3 共享變數

變數v只有一個運行時實例，並且被兩個以上線程引用

13.5 用信號量同步線程13.5.2 利用信號量訪問共享變數

一種叫做信號量（semaphore）的特殊類型變數，信號量s是具有非負整數值的全局變數，只能由兩個特殊的操作來處理，稱為P和V

P（s）：如果s非零，P將s減1，並且立即返回，如果s為零，就掛起進程，阻塞直到s變為非零，然後被V操作重啟，完成P操作，獲得控制權

V（s）：將s加1，如果有任何進程阻塞在P操作，那麼V操作會重啟這些進程中的一個

二進位信號量

將每個共享變數（或相關共享變數集合）與一個信號量s（初始為1）聯繫起來，然後用P和V操作將相應的臨界區包圍起來，它的值總是0或者1，所以叫做二進位信號量

進度圖

由P和V操作創建的禁止區使得在任何時間點上，在被包圍的臨界區中，不可能有多個線程在執行指令，信號量操作確保了對臨界區的互斥訪問，一般現象稱為互斥（mutual exclusion）

目的是提供互斥的二進位信號量通常叫做互斥鎖（mutex），在互斥鎖上執行一個P操作叫做加鎖，V操作叫做解鎖，一個線程已經對一個互斥鎖加鎖但還沒有解鎖，被稱為佔用互斥鎖

13.5.3 Posix信號量

Posix標準定義了許多操作信號量的函數，三個基本的操作是seminit、semwait（P操作）和sem_post（V操作）

13.5.4 利用信號量來調度共享資源

其它同步機制

Java線程是用一種叫做Java監控器（Java Monitor）的機制來同步的，提供了對信號量互斥和調度能力的更高級別的抽象

13.6 綜合：基於預線程化的並發伺服器

為每一個新客戶端創建一個新線程，缺點是代價較大

13.7 其它並發性問題13.7.1 線程安全

一個函數，當且僅當被多個並發線程反覆地調用時，它會一直產生正確的結果，被稱為線程安全的（thread-safe）

第1類：不保護共享變數的函數

修改一個未受保護的變數

解決： 利用類似P和V操作這樣的同步操作來保護變數，優點是調用程序不需要做任何修改，缺點是同步操作將減慢程序的執行時間

第2類：保護跨越多個調用的狀態的函數

函數共享一個全局變數

解決：調用者在函數參數中傳遞狀態信息，缺點：需要被迫修改調用程序中的代碼

第3類：返回指向靜態變數的指針的函數

共享了一個全局變數

解決：1，重寫函數 2，使用lock-and-copy（加鎖-拷貝）技術，定義一個線程安全的包裝函數（wrapper），執行lock-and-copy，通過調用這個包裝函數來取代所有對線程不安全函數的調用

第4類：調用線程不安全函數的函數13.7.2 可重入性

一類重要的線程安全函數，叫做可重入函數（reentrant function）

特點： 當被多個線程調用時，不會引用任何共享數據

可重入函數通常比不可重入的線程安全的函數高效一些，因為不需要同步操作

如果所有的函數參數都是傳值傳遞（沒有指針），並且所有的數據引用都是本地的自動棧變數（也就是，沒有引用靜態或全局變數），那麼函數就是顯式可重入的（explicitly reentrant），無論它是如何被調用，都可以斷定它是可重入的

加入顯式可重入函數中一些參數可以傳指針，那麼就得到一個隱式可重入函數（implicitly reentrant）函數，即，在調用線程小心地傳遞指向非共享數據的指針時，它是可重入的

13.7.3 在多線程中使用已存在的庫函數

大多數Unix函數和定義在標準c庫中的函數都是線程安全的，只有一小部分是例外

Unix系統提供大多數線程不安全函數的可重入版本，總是以"_r"後綴結尾

13.7.4 競爭

原因: 程序員假設線程將按照某種特殊的軌線穿過執行狀態空間

多線程必須對任何可行的軌線都正確工作

13.7.5 死鎖

死鎖(deadlock),指的是一組線程被阻塞了,等待一個永遠也不會為真的條件

避免死鎖

互斥鎖加鎖順序規則: 如果對於程序中每對互斥鎖(s,t),每個既包含s也包含t的線程都按照相同的順序同時對它們加鎖,那麼這個程序就是無死鎖的

即，兩個線程都是從P（s）->P(t)


喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！

本站內容充實豐富，博大精深，小編精選每日熱門資訊，隨時更新，點擊「搶先收到最新資訊」瀏覽吧！


請您繼續閱讀更多來自 全球大搜羅 的精彩文章:

※運營棋牌你還忙著開發很多遊戲嗎？
※戲精真的是一種可怕的存在！

TAG:全球大搜羅 |