第12章 并發程式設計
chapter1 前言
1.若邏輯控制流在時間上重疊，那麼它們就是并發的。
2.并發(concurrency ) ，出現在計算機系統的許多不同層面上。
3.應用級并發是很有用的:
通路慢速I/O裝置。當一個應用正在等待來自慢速 I/O 裝置(例如磁盤)的資料到達時， 核心會運作其他程序，使 CPU保持繁忙。每個應用都可以按照類似的方式，通過交替執行 I/O 請求和其他有用的工作來使用并發。
與人互動。和計算機互動的人要求計算機有同時執行多個任務的能力。例如，他們在列印一個文檔時，可能想要調整一個視窗的大小。現代視窗系統利用并發來提供這種能力。每次使用者請求某種操作(比如通過單擊滑鼠)時，一個獨立的并發邏輯流被建立來執行這個操作。
通過推遲工作以降低延遲。有時，應用程式能夠通過推遲其他操作和并發地執行它們，利用并發來降低某些操作的延遲。比如，一個動态存儲配置設定器可以通過推遲合并，把它放到一個運作在較低優先級上的并發"合并"流中，在有空閑的 CPU 周期時充分利用這些空閑 周期，進而降低單個 free 操作的延遲。
服務多個網絡用戶端。
在多核機器上進行并行計算。許多現代系統都配備有多核處理器，多核處理器中包含多個 CPU。被劃分成并發流的應用程式通常在多核機器上比在單處理器機器上運作得快，因為這些流會并行執行，而不是交錯執行。 4.使用應用級并發的應用程式稱為并發程式 (concurrent program)。現代作業系統提供了三種基本的構造并發程式的方法：
①程序。每個邏輯控制流都是一個程序，由核心來排程和維護。因為程序 有獨立的虛拟位址空間，想要和其他流通信，控制流必須使用某種顯式的程序間通信 (interprocess communication, IPC) 機制。
②I/O 多路複用。在這種形式的并發程式設計中，應用程式在一個程序的上下文中顯式地排程它們自己的邏輯流。邏輯流被模型化為狀态機，資料到達檔案描述符後，主程式顯式地從一個狀态轉換到另一個狀态。因為程式是一個單獨的程序，是以所有的流都共享同一個位址空間。
③線程。線程是運作在一個單一程序上下文中的邏輯流，由核心進行排程。是其他兩種方式的混合體，像程序流一樣由核心進行排程，而像I/O 多路複用流一樣共享同一個虛拟位址空間。 chapter2 基于程序的并發程式設計
1.構造并發程式最簡單的方法就是用程序。一個構造并發伺服器的自然方法就是，在父程序中接受用戶端連接配接請求，然後建立一個新的子程序來為每個新用戶端提供服務。
2.伺服器正在監昕一個監聽描述符(比如描述符 3)上的連接配接請求。現在假設伺服器接受了用戶端 1 的連接配接請求， 并傳回一個已連接配接描述符(比如描述符4)。
3.在接受連接配接請求之後，伺服器派生一個子程序，這個子程序獲得伺服器描述符表的完整拷貝。子程序關閉它的拷貝端的連接配接請求中的監聽描述符 3，而父程序關閉它的己連接配接描述符 4 的拷貝，因為不再需要這些描述符了。其中子程序正忙于為用戶端提供服務。因為父、子程序中的已連接配接描述符都指向同一個檔案表表項，是以父程序關閉它的已連接配接描述符的拷貝是至關重要的。否則，将永遠不會釋放已連接配接描述符 4 的檔案表條目，而且由此 引起的存儲器洩漏将最終消耗盡可用的存儲器，使系統崩潰。
第一步:伺服器接受用戶端的連接配接請求：
父程序為用戶端 1 建立了子程序之後，它接受一個新的用戶端 2 的連接配接請求， 并傳回一個新的已連接配接描述符(比如描述符5)，然後，父程序又派生另一個子程序，這個子程序用已連接配接描述符 5 為它的用戶端提供服務。
此時，父程序正在等待下一個連接配接請求，而兩個子程序正在并發地為它們各自的用戶端提供服務。
第二步:伺服器派生一個子程序為這個用戶端服務：
第三步：伺服器接受另一個連接配接請求：
1.1 基于程序的并發伺服器
1.通常伺服器會運作很長的時間，是以我們必須要包括一個 SIGCHLD 處理程式，來回收僵死 (zombie) 子程序的資源。因為當 SIGCHLD 處理程式執行時， SIGCHLD 信号是阻塞的，而 Unix 信号是不排隊的，是以 SIGCHLD 處理程式必須準備好回收多個僵死子程序的資源。
2.父子程序必須關閉它們各自的 connfd 拷貝。這對父程序而言尤為重要，它必須關閉它的已連接配接描述 符，以避免存儲器洩漏。
3.因為套接字的檔案表表項中的引用計數，直到父子程序的 connfd 都關閉了，到用戶端的連接配接才會終止。
第四步：伺服器派生另一個子程序為新的用戶端服務
基于程序的并發 echo 伺服器.父程序派生一個子程序來處理每個新的連接配接請求：
1.2 關于程序的優劣
1.在父、子程序間共享狀态資訊，程序有一個非常清晰的模型 ： 共享檔案表，但是不共享使用者位址空間。程序有獨立的位址空間既是優點也是缺點。一個程序不可能不小心覆寫另一個程序的虛拟存儲器，這就消除了許多令人迷惑的錯誤一一這是一個明顯的優點。
2.另一方面，獨立的位址空間使得程序共享狀态資訊變得更加困難。為了共享資訊，它們必須使用顯式的IPC(程序間通信)機制。基于程序的設計的另一個缺點是，它們往往比較慢，因為程序控制和 IPC 的開銷很高。
chapter2 基于 I/O 多路複用的并發程式設計
1.I/O 多路複用(I/O multiplexing) 技術。基本的思路就是使用 select 函數，要求核心挂起程序，隻有在一個或多個I/O事件發生後，才将控制傳回給應用程式
select函數：
2.select 函數處理類型為 fd_set 的集合，也叫做描述符集合。邏輯上，我們将描述符集合看成一個大小為 n 的位向量。
每個位 bk對應于描述符 k。當且僅當 bk= 1， 描述符 k才表明是描述符集合的一個元素。隻允許你對描述符集合做三件事:
1) 配置設定它們
2) 将一個此種類型的變量指派給另一個變量
3) 用 FD_ZERO、 FD_SET、 FD_CLR 和 FD_ISSET 宏指令來修改和檢查它們。 3.select 函數有兩個輸人:一個稱為讀集合的描述符集合(fdset)和該 讀集合的基數 (n) (實際上是任何描述符集合的最大基數). select 函數會一直阻塞，直到讀集合中至少有一個描述符準備好可以讀。當且僅當一個從該描述符讀取一個位元組的請求不會阻塞時，描述符 k就表示準備好可以讀了。作為一個副作用， select 修改了參數 fdset 指向的 fd_set，指明讀集合中一個稱為準備好集合 (ready set) 的子集，這個集合是由讀集合中準備好可以讀了的描述符組成的。函數傳回的值指明了準備好集合的基數。注意，由于這個副作用， 我們必須在每次調用 select 時都更新讀集合。
使用 I/O 多路複用的 echo 伺服器。伺服器使用 select 等待監聽描述符上的連接配接請求和标準輸入上的指令：
<<不是調用 accept 函數來等待一個連接配接請求，而是調用 select 函數，這個函數會一直阻塞，直到監聽描述符或者标準輸入準備好可以讀。
<<一旦 select 傳回，我們就用 FD_ISSET 宏指令來判斷哪個描述符準備好可以讀了。
<<一旦它連接配接到某個用戶端，就會連續回送輸入行，直到用戶端關閉這個連接配接中它的那一端。是以，如果你鍵入一個指令到标準輸入，你将不會得到響應，直到伺服器和用戶端之間結束。一個 更好的方法是更細粒度的多路複用，伺服器每次循環〈至多)回送一個文本行。
2.1 基于 I/O 多路複用的并發事件驅動伺服器
1.I/O 多路複用可以用做并發事件驅動 (event-driven) 程式的基礎，在事件驅動程式中，流是因為某種事件而前進的。
2.将邏輯流模型化為狀态機。不嚴格地說，一個狀态機 (state machine) 就是一組狀态 (state)、輸入事件(input event) 和轉移他(transition)，其中轉移就是将狀态和輸入事件映射到狀态。每個轉移都将一個(輸入狀态，輸入事件)對映射到一個輸出狀 态。自循環(self-loop) 是同一輸入和輸出狀态之間的轉移。節 點表示狀态，有向弧表示轉移，而弧上的标号表示輸入事件。一個狀态機從某種初始狀态開始執行。每個輸入事件都會引發一個從目前狀态到下一狀态的轉移。
3.并發事件驅動 echo 伺服器中邏輯流的狀态機：
4.伺服器使用I/O多路複用，借助 select 函數檢測輸入事件的發生。
5.伺服器調用 select 函數來 檢測兩種不同類型的輸人事件: a) 來自一個新用戶端的連接配接請求到達， b) 一個己存在的客戶 端的己連接配接描述符準備好可以讀了。
6.基于I/O 多路複用的并發 echo 伺服器。每次伺服器疊代都回送來自每個準備好的描述符的文本行：
7.init_pool 函數初始化用戶端池。 clientfd 數組表示已連接配接描述符的集合， 其中整數 -1 表示一個可用的槽位。初始時，已連接配接描述符集合是空的，而且監聽描述符是 select 讀集合中唯一的描述符。
8.init_pool: 初始化活動用戶端池：
9.add_clieht函數添加一個新的用戶端到活動用戶端池中。在 clientfd 數組中找到一個空槽位後，伺服器将這個已連接配接描述符添加到數組中，并初始化相應的RIO讀緩沖區，這樣一來我們就能夠對這個描述符調用rio_readlineb。将這個已連接配接描述符添加到 select 讀集合，并更新該池的一些全局屬性。 maxfd 變量記錄了 select 的最大檔案描述符。 maxi 變量記錄的 是到 clientfd數組的最大索引，這樣 check_clients 函數就無需搜尋整個數組了。
10.check_clients 函數回送來自每個準備好的已連接配接描述符的一個文本行。 如果成功地從描述符讀取了一個文本行，那麼我們就将該文本行回送到用戶端
11.add_client: 向池中添加一個新的用戶端連接配接:
check_clients: 為準備好的用戶端連接配接服務:
12.select 函數檢測到輸入事件，而 add_client 函數建立 一個新的邏輯流(狀态機). check_clients 函數通過回送輸入行來執行狀态轉移，而且當客 戶端完成文本行發送時，它還要删除這個狀态機。
2.2 I/O 多路複用技術的優劣
1.事件驅動設計的一個優點是，它比基于程序的設計給了程式員更多的對程式行為的控制。另一個優點是，一個基于 I/O 多路複用的事件驅動伺服器是運作在單一程序上下文中的，因 此每個邏輯流都能通路該程序的全部位址空間。
2.事件驅動設計的一個明顯的缺點就是編碼複雜。我們的事件驅動的并發 echo 伺服器需要的代碼比基于程序的伺服器多三倍。不幸的是，随着并發粒度的減小，複雜性還會上升。這裡的粒度是指每個邏輯流每個時間片執行的指令數量。
chapter3 基于線程的并發程式設計
1.線程(thread) 就是運作在程序上下文中的邏輯流。
2.每個線程都有它自己的線程上下文 (thread context)，包括一個唯一的整數線程 (Thread ID, TID)、棧、棧指針、程式計數器、通用目的寄存器和條件碼。所有的運作在一個程序裡的線程共享該程序的整個虛拟位址空間。
3.基于線程的邏輯流結合了基于程序和基于 I/O 多路複用的流的特性。同程序一樣，線程由核心自動排程，并且核心通過一個整數 ID 來識别線程。同基于 I/O 多路複用的流一樣，多個線程 運作在單一程序的上下文中，是以共享這個程序虛拟位址空間的整個内容，包括它的代碼、資料、堆、共享庫和打開的檔案。
3.1 線程執行模型
1.每個程序開始生命周期時都是單一線程，這個線程稱為主線程 (main thread)。在某一時刻，主線程建立一個對等線程 (peer thread)，從這個時間點開始，兩個線程就并發地運作。最後，因為主線程執行一個慢速系統調用。或者因為它被系統的間隔計時器中斷，控制就會通過上下文切換傳遞到對等線程。對等線程會執行一段時間，然後控制傳遞回主線程，依次類推。
2.因為一個線程的上下文要比一個程序的上下文小得多，線程的上下文切換要比 程序的上下文切換快得多。另一個不同就是線程不像程序那樣，不是按照嚴格的父子層次來組織的。和一個程序相關的線程組成一個對等(線程)池 (pool)，獨立于其他線程建立的線程。主線程和其他線程的差別僅在于它總是程序中第一個運作的線程。對等 (線程)池概念的主要影響是，一個線程可 以殺死它的任何對等線程，或者等待它的任意對等線程終止。另外，每個對等線程都能讀寫相同的共享資料。
3.并發線程執行：
3.2 Posix 線程
1.Posix 線程 (Pthreads) 是在 C 程式中處理線程的一個标準接口。Pthreads 定義了大約 60 個函數，允許程式建立、殺死和回收線程，與對等線程安全地共享資料，還可以通知對等線程系統狀态的變化。
2.線程的代碼和本地資料被封裝在一個線程例程(thread routine) 中。如果想傳遞多個參數給錢程例程，那麼你應該将參數放 到一個結構中，并傳遞一個指向該結構的指針。想要線程例程傳回多個參數，你可以傳回一個指向一個結構的指針。
3.3 建立線程
1.線程通過調用 pthread create 函數來建立其他線程。
2.pthread_create 函數建立一個新的線程，并帶着一個輸入變量arg，在新線程的上下文中運作線程例程f。能用attr參數來改變新建立線程的預設屬性。
當 pthread_create 傳回時，參數 tid包含新建立線程的ID。新線程可以通過調用 pthread_self 函數來獲得它自己的線程 ID.
3.4 終止線程
1.一個線程是以下列方式之一來終止的 ：
①當頂層的線程例程傳回時，線程會隐式地終止。
②通過調用 pthread_exit 函數，線程會顯式地終止。如果主線程調用 pthread_exit , 它會等待所有其他對等線程終止，然後再終止主線程和整個程序，傳回值為 thread_return。
③某個對等線程調用 Unix 的 exit 函數，該函數終止程序以及所有與該程序相關的線程。
④另一個對等線程通過以目前線程ID作為參數調用 pthread_cancle 函數來終止目前線程。
3.5 回收已終止線程的資源
1.線程通過調用 pthread_join 函數等待其他線程終止。
2.pthread_join 函數會阻塞，直到線程 tid 終止，将線程例程傳回的 (void*) 指針指派 為 thread_return 指向的位置，然後回收己終止線程占用的所有存儲器資源。
3.pthread join 函數隻能等待一個指定的線程終止。
3.6 分離線程
1.在任何一個時間點上，線程是可結合的 (joinable) 或者是分離的 (detached)。一個可結合的線程能夠被其他線程收回其資源和殺死。在被其他線程回收之前，它的存儲器資源(例如棧)是沒有被釋放的。相反，一個分離的線程是不能被其他線程回收或殺死的。它的存儲器資源在它終止時由系統自動釋放。
2.預設情況下，線程被建立成可結合的。為了避免存儲器洩漏，每個可結合線程都應該要麼被其他線程顯式地收回，要麼通過調用 pthread_detach 函數被分離。
3.pthread_detach 函數分離可結合線程 tid. 線程能夠通過以 pthread_self ()為參數 的 pthread_detach 調用來分離它們自己。
3.7 初始化線程
1.pthread_once 函數允許你初始化與線程例程相關的狀态。
2.once_control 變量是一個全局或者靜态變量，總是被初始化為 PTHREAD_ONCE_INIT。 當你第一次用參數 once_control 調用 pthread_once 時， 它調用 init_routine，這是一個沒有輸入參數，也不傳回什麼的函數。
3.動态初始化多個線程共享的全局變量時， pthread_once 函數是很有用的。
3.8 一個基于線程的并發伺服器
1.調用 pthread_ create 時，如何将已連接配接描述符傳遞給對等線程。最明顯的方法就是傳遞一個指向這個描述符的指針。對等線程間接引用這個指針，并将它指派給一個局部變量。
2.這樣可能會出錯，因為它在對等線程的指派語句和主線程的 accept 語句間引入了競争 (race)。如果指派語句在下一個accept之前完成，那麼對等線程中的局部變量 connfd 就得到正确的描述符值。然而，如果指派語句是在 accept 之後才完成的，那麼對等線程中的 局部變量connfd就得到下一次連接配接的描述符值。那麼不幸的結果就是，現在兩個線程在同一個描述符上執行輸入和輸出。為了避免這種潛在的緻命競争，我們必須将每個accept傳回的已連接配接描述符配置設定到它自己的動态配置設定的存儲器塊。
chapter4 多線程程式中的共享變量
4.1 線程存儲器模型
1.一組并發線程運作在一個程序的上下文中。每個線程都有它自己獨立的線程上下文，包括線程 ID、棧、棧指針、程式計數器、條件碼和通用目的寄存器值。每個線程和其他線程一起共享程序上下文的剩餘部分。這包括整個使用者虛拟位址空間，它是由隻讀文本(代碼)、讀/寫資料、堆以及所有的共享庫代碼和資料區域組成的。線程也共享同樣的打開檔案的集合。
2.讓一個線程去讀或寫另一個線程的寄存器值是不可能的。另一方 面，任何線程都可以通路共享虛拟存儲器的任意位置。儲存在虛拟位址空間的棧區域中，并且通常是被相應的線程獨立地通路的。
4.2 将變量映射到存儲器
1.線程化的 C 程式中變量根據它們的存儲類型被映射到虛拟存儲器:
①全局變量。全局變量是定義在函數之外的變量。在運作時，虛拟存儲器的讀/寫區域隻包含每個全局變量的一個執行個體，任何線程都可以引用。
②本地自動變量。本地自動變量就是定義在函數内部但是沒有 static 屬性的變量。在運作時，每個線程的棧都包含它自己的所有本地自動變量的執行個體。即使當多個線程執行同一個線程例程時也是如此。
③本地靜态變量。本地靜态變量是定義在函數内部并有 static 屬性的變量。和全局變量一樣，虛拟存儲器的讀/寫區域隻包含在程式中聲明的每個本地靜态變量的一個執行個體。 4.3 共享變量
一個變量 v 是共亭的，當且僅當它的一個執行個體被一個以上的線程引用。
chapter5 用信号量同步線程
1.将線程 i 的循環代碼分解成五個部分：
Hi：在循環頭部的指令塊
Li：加載共享變量 cnt 到寄存器%eaxi 的指令，這裡%eaxi 表示線程i 中的寄存器%eax的值。
Ui：更新(增加) %eaxi 的指令。
Si：将%eaxi 的更新值存回到共享變量 cnt 的指令。
Ti：循環尾部的指令塊。 2.注意頭和尾隻操作本地棧變量，而Li、Ui和Si操作共享計數器變量的内容。
3.一般而言， 你沒有辦法預測作業系統是否将為你的線程選擇一個正确的順序。
4.進度圖 (progress graph) 的方法來闡明這些正确 的和不正确的指令順序的概念
5.1 進度圖
1.進度圖 (progress graph) 将 n 個并發線程的執行模型化為一條 n 維笛卡兒空間中的軌迹線。每條軸 k對應于線程 k 的進度。每個代表線程 k 已經完成了指令 Ik 這一狀态。圖的原點對應于沒有任何線 程完成一條指令的初始狀态。
2.進度圖将指令執行模型化為從一種狀态到另一種狀态的轉換(transition)。轉換被表示為一條從一點到相鄰點的有向邊。合法的轉換是向右(線程 1 中的一條指令完成〉或者向上(線程 2 中的一條指令完成)的。兩條指令不能在同一時刻完成一一對角線轉換是不允許的。程式決不會反向運作，是以向下或者向左移動的轉換也是不合法的。
3.一個程式的執行曆史被模型化為狀态空間中的一條軌迹線。
4.繞開不安全區的軌迹線叫做安全軌迹線 (safe trajectory)。相反，接觸到任何不安全區的軌迹線就叫做不安全軌迹線 (unsafe trajectory)。
5.2 信号量
1.一種解決同步不同執行線程問題的方法，這種方法是基于一種叫做信号量 (semaphore) 的特殊類型變量的。信号量 s 是具有非負整數值的全 局變量，隻能由兩種特殊的操作來處理，這兩種操作稱為 P 和 V:
①P(s) :如果 s 是非零的，那麼 P 将 s 減1，并且立即傳回。如果 s 為零，那麼就挂起這個線程， 直到 s變為非零，而一個 V操 作會重新開機這個線程。在重新開機之後， P 操作将 s 減1，并将控制 傳回給調用者。
②V(s): V操作将s 加 1。如果有 任何線程阻塞在P 操作等待 s 變成非零，那麼 V操作會重新開機 這些線程中的一個，然後該線程将s 減1，完成它的 P 操作。 2.P中的測試和減1操作是不可分割的，也就是說，一旦預測信号量s 變為非零，就會将s 減 1，不能有中斷。V中的加 1 操作也是不可分割的，也就是加載、加 1 和存儲信号量的過程中沒 有中斷。注意， V的定義中沒有定義等待線程被重新啟動的順序。唯一的要求是V必須隻能重新開機一個正在等待的線程。是以，當有多個線程在等待同一個信号量時，你不能預測V操作要重新開機哪一個線程。
3.P和V的定義確定了一個正在運作的程式絕不可能進入這樣一種狀态，也就是一個正确初始化了的信号量有一個負值。這個屬性稱為信号量不變性 (semaphore invariant)，為控制并發程式的軌迹線提供了強有力的工具
4.信号量的函數：
5.sem_init 函數将信号量 sem 初始化為 value. 每個信号量在使用前必須初始化。針對我 們的目的，中間的參數總是0。程式分别通過調用 sem_wait 和 sem_post 函數來執行P和V操作。
6.P和V的包裝函數：
5.3 使用信号量來實作互斥
1.基本思想是将每個共享變量 (或者一組相關的共享變量)與一個信号量 s (初始為1)聯系起來，然後用 P(s) 和V(s) 操作将 相應的臨界區包圍起來。
2.保護共享變量的信号量叫做二進制信号量 (binary semaphore)，因為它的值總是 0 或者 1 。以提供互斥為目的的二進制信号量常常也稱為互斥鎖 (mutex)。在一個互斥鎖上執行 P 操作稱為對互斥鎖加鎖。類似地，執行 V操作稱為對互斥鎖解鎖。對一個互斥鎖加了鎖但是還沒有解鎖的線程稱為占用這個互斥鎖。一個被用作一組可用資源的計數器的信号量稱為計數信号量。
3.關鍵思想是這種 P 和 V操作的結合建立了一組狀态， 叫做禁止區 (forbidden region)，其中 s<O。因為信号量的不變性，沒有實際可行的軌迹線能夠包含禁止區中的狀态。而且，因為禁止區完全包括了不安全區，是以沒有實際可行的軌迹線能夠接觸不安全區的任何部分。是以，每條實際可行的軌迹線都是安全的，而且不管運作時指令順序是怎樣的，程式都會正确地增加計數器的值。
4.使用信号量來互斥。 s<O 的不可行狀态定義了一個禁止區，禁止區完全包括了不安全 區，阻止了實際可行的軌迹線接觸到不安全區：
5.由P和V操作建立的禁止區使得在任何時間點上，在被包圍的臨界區中，不可能有多個線程在執行指令。換句話說，信号量操作確定了對臨界區的互斥通路。
5.4 利用信号量來排程共享資源
除了提供互斥之外，信号量的另一個重要作用是排程對共享資源的通路。
1. 生産者-消費者問題
生産者産生項目并把它們插入到一個有限的緩沖區中。消費者從緩沖區中取出這些項目，然後消費它們。
<<因為插入和取出項目都涉及更新共享變量，是以我們必須保證對緩沖區的通路是互斥的。但是隻保證互斥通路是不夠的，我們還需要排程對緩沖區的通路。如果緩沖區是滿的(沒有空的槽位)，那麼生産者必須等待直到有一個槽位變為可用。與之相似，如果緩沖區是空的(沒有可取用的項目)，那麼消費者必須等待直到有一個項目變為可用。
<<基于預線程化 (prethreading) 的有趣的并發伺服器。 SBUP 操作類型為 sbuf_t 的有限緩沖區，項目存放在一個動态配置設定的 n 項整數數組 (buf) 中。 front 和 rear 索引值記錄該數組中的第一項和最後一項。三個信号量同步對緩 沖區的通路。 mutex 信号量提供互斥的緩沖區通路。 slots 和 items 信号量分别記錄空槽位和可用項目的數量。
sbuf_t: SBUF 包使用的有限緩沖區：
<<sbuf_init 函數為緩沖區配置設定堆存儲器，設定 front 和 rear 表示一個空的緩沖區，并為三個信号量賦初始值。這個函數在調用其他三個函數中的任何一個之前調用一次。 sbuf_deinit函數是當應用程式使用完緩沖區時，釋放緩沖區存儲的。 sbuf_insert 函數等待一個可用的槽位，對互斥鎖加鎖，添加項目，對互斥鎖解鎖，然後宣布有一個新項目可用。 sbuf_remove 函數是與 sbuf_insert 函數對稱的。在等待一個可用的緩沖區項目之後，對互斥鎖加鎖，從緩沖區的前面取出該項目，對互斥鎖解鎖，然後發信号通知一個新的槽位可供使用。
SBUF: 同步對有限緩沖區并發通路的包：
2. 讀者-寫者問題
有些線程隻讀對象，而其他的線程隻修改對象。修改對象的線程叫做寫者。隻讀對象的線程叫做讀者。寫者必須擁有對對象的獨占的通路，而讀者可以和無限多個其他的讀者共享對象。一般來說，有無限多個并發的讀者和寫者。
第一類讀者-寫者問題，讀者優先，要求不要讓讀者等待，除非已經把使用對象的權限賦予了一個寫者。換句話說，讀者不會因為有一個寫者在等待而等待。第二類讀者一寫者問題，寫者優先，要求一旦一個寫者準備好可以寫，它就會盡可能快地完成它的寫操作。
對這兩種讀者-寫者問題的正确解答可能導緻饑餓 (starvation)，饑餓就是一個線程無限期地阻塞，無法進展。
5.5 綜合： 基于預線程化的并發伺服器
預線程化的并發伺服器的組織結構。一組現有的線程不斷地取出和處理來自有限緩沖區的已連接配接描述符：
chapter6 使用線程提高并行性
1.順序、并發和并行程式集合之間的關系：
2.并行程式常常被寫為每個核上隻運作一個線程。
3.并行程式的加速比 (speedup) 通常定義為：
p 是處理器核的數量，凡是在 k個核上的運作時間。這個公式有時稱為強擴充 (strong scaling)。當 T1 是程式順序執行版本的執行時間時， Sp 稱為絕對加速比.(absolute speedup)。當 T1 是程式并行版本在一個核上的執行時間時， Sp 稱為相對加速比 (relative speedup)。絕對加速 比比相對加速比能更真實地衡量并行的好處。
4.效率 (efficiency ) ，定義為:
通常表示為範圍在 (0， 100] 之間的百分比。效率是對由于并行化造成的開銷的衡量。具有高 效率的程式比效率低的程式在有用的工作上花費更多的時間，在同步和通信上花費更少的時間。
5.加速比還有另外一面，稱為弱擴充 (weak scaling)，在增加處理器數量的同時，增加問題的規模，這樣随着處理器數量的增加，每個處理器執行的工作量保持不變。加速比和效率被表達為機關時間完成的工作總量。
chapter7 其他并發問題
7.1 線程安全
1.當用線程編寫程式時，我們必須小心地編寫那些具有稱為線程安全性(thread safety) 屬性的畫數。一個函數被稱為線程安全的(thread-safe)，當且僅當被多個并發線程反複地調用時，它會一直産生正确的結果。如果一個函數不是線程安全的，我們就說它是線程不安全的(thread-unsafe)。
2.四個(不相交的)線程不安全函數類：
①第 1 類： 不保護共享變量的函數。thread 函數中對一個未受保護的全局計數器變量加 1. 将這類線程不安全函數變成線程安全的， 相對而言比較容易：利用像P和 V操作這樣的同步操作來保護共享的變量。這個方法的優點是在調用程式中不需要做任何修改。缺點是同步操作将減慢程式的執行時間。
②第 2 類：保持跨越多個調用的狀态的函數。一個僞随機數生成器是這類線程不安全函數的簡單例子。僞随機數生成器程式包. rand 函數是線程不安全的，因為目前調用的結果依賴于前次調用的中間結果。當調用 srand 為 rand 設定了一個種子後，我們從一個單線程中反複地調用 rand，能夠預期得到一個可重複的随機數字序列。然而，如果多線程調用 rand 函數，這種假設就不再成立了。使得像 rand這樣的函數線程安全的唯一方式是重寫它，使得它不再使用任何 static 資料，而是依靠調用者在參數中傳遞狀态資訊。這樣做的缺點是，程式員現在還要被迫修改調用程式中的代碼。在一個大的程式中，可能有成百上千個不同的調用位置，做這樣的修改将是非常麻煩的，而且容易出錯。
③第 3 類:傳回指向靜态變量的指針的函數。某些函數，例如 ctime 和 gethostbyname，将計算結果放在一個 static 變量中，然後傳回一個指向這個變量的指針。如果我們從并發線程中調用 這些函數，那麼将可能發生災難，因為正在被一個線程使用的結果會被另一個線程悄悄地覆寫了。有兩種方法來處理這類線程不安全函數。一種選擇是重寫函數，使得調用者傳遞存放結果的變量的位址。這就消除了所有共享資料，但是它要求程式員能夠修改函數的源代碼。
④第 4 類:調用線程不安全函數的函數。如果函數f調用線程不安全函數 g，那麼f就是線程不安全的嗎?不一定。如果 g是第 2 類函數，即依賴于跨越多次調用的狀态，那麼f也是線程不安全的，而且除了重寫 g 以外，沒有什麼辦法。然而，如果 g 是第 1 類或者第 3 類函數，那麼隻 要你用一個互斥鎖保護調用位置和任何得到的共享資料，f仍然可能是線程安全的。
7.2 可重入性
1.可重入函數 (reentrant function)，其特點在于它們具有這 樣一種屬性:當它們被多個線程調用時，不會引用任何共享資料。
可重入函數通常要比不可重人的線程安全的函數高效一些，因為它們不需要同步操作。更進一步來說，将第 2 類線程不安全函數轉化為線 程安全函數的唯一方法就是重寫它，使之變為可重入的。
2.可重入函數、線程安全函數和線程不安全函數之間的集合關系：
3.檢查某個函數的代碼并先驗地斷定它是可重入的。
4.如果所有的函數參數都是傳值傳遞的(即沒有指針)，并且所有的資料引用都是本地的自動棧變量(即沒有引用靜态或全局變量)，那麼函數就是顯式可重入的 (explicitly reentrant)，也就是說，無論它是被如何調用的，我們都可以斷言它是可重入的。
5.我們總是使用術語可重入的 (reenntrant) 既包括顯式可重入函數也包括隐式可重入函數。然而，認識到可重入性有時既是調用者也是被調用者的屬性，并不隻是被調用者單獨的屬性是非常重要的。
7.3 線上程化的程式中使用已存在的庫函數
1.大多數 Unix 函數，包括定義在标準 C 庫中的函數(例如 malloc、 free、 realloc、 printf 和 scanf) 都是線程安全的，隻有一小部分是例外。
2.常見的線程不安全的庫函數：
3.除了 rand 和 strtok 以外，所有這些線程不安全函數都是第 3 類的，它們傳回一個指向靜态變量的指針。如果我們需要在一個線程化的程式中調用這些函數中的某一個，對調用者來說最不惹麻煩的方法是加鎖-拷貝。然而，加鎖-拷貝方法有許多缺點。首先，額外的同步降低了 程式的速度。其次，像 gethostbyname 這樣的函數傳回指向複雜結構的結構的指針，要拷貝整個結構層次，需要深層拷貝 (deep copy) 結構。再次，加鎖-拷貝方法對像 rand 這樣依賴 跨越調用的靜态狀态的第 2 類函數并不有效。 是以，Unix系統提供大多數線程不安全函數的可重人版本。可重入版本的名字總是以"_r" 字尾結尾。
7.4 競争
1.當一個程式的正确性依賴于一個線程要在另一個線程到達y 點之前到達它的控制流中的 x 點時，就會發生競争。
2.發生競争是因為程式員假定線程将按照某種特殊的軌迹線穿過執行狀态空間，而忘記了另一條準則規定:線程化的程式必須對任何可行的軌迹線都正确工作。
7.5 死鎖
1.信号量引人了一種潛在的令人厭惡的運作時錯誤，叫做死鎖(deadlock) ，它指的是一組線程被阻塞了，等待一個永遠也不會為真的條件。
①程式員使用 P 和 V操作順序不當，以至于兩個信号量的禁止區域重疊。如果某個執行軌迹 線碰巧到達了死鎖狀态 d，那麼就不可能有進一步的進展了，因為重疊的禁止區域阻塞了 每個合法方向上的進展。換句話說，程式死鎖是因為每個線程都在等待其他線程執行一個根本不可能發生的V操作。
②重疊的禁止區域引起了一組稱為死所區域(deadlock region )的狀态。如果一個軌迹線碰巧到達了一個死鎖區域中的狀态，那麼死鎖就是不可避免的了。軌迹線可以進人死鎖區域， 但是它們不可能離開。
③死鎖是一個相當困難的問題，因為它不總是可預測的。一些幸運的執行軌迹線将繞開死鎖區域，而其他的将會陷入這個區域。
④程式死鎖有很多原因，要避免死鎖一般而言是很困難的。然而，當使用二進制信号量來實作互斥時，可以應用下面的簡單而有效的規則來避免死鎖:
互斥鎖加鎖順序規則:如果對于程式中每對互斥鎖 (s， t)， 每個同時占用 s 和 t 的線程都按照相同的順序對它們加鎖，那麼這個程式就是無死鎖的。 ⑤有死鎖程式的進度圖:
⑥無死鎖程式的進度圖:
chapter8 遇到的問題及解決方法
這一章講的是程序、多線程、通信等等的問題。和前面幾章的内容都有内部聯系。我覺得最有難度的就是關于信号量的應用那部分。和我們最近在做的項目有重合部分。裡面關于一些函數、資料結構的解說比較難以了解。我覺得這本教材由于是外國人的作品，讀起來還是蠻抽象的，特别是對一些代碼的講解也不是很詳細，一旦功底不紮實就很暈乎。我已經萌生了有時間再讀一遍的想法= =。由于項目的問題，我覺得這個部分這本書講的還是更為詳細一些。比起做項目在網上搜查的資料還是更值得相信。但是其中還是有部分隻是很抽象難以了解。希望後面還能繼續找一些代碼來幫助了解。
chapter9 參考文獻
《深入了解計算機系統》
我的另一篇部落格：http://www.cnblogs.com/paperfish/p/4996435.html