1.1從Hello World說起

目的：從最基本的編譯，靜態鏈接到操作系統如何轉載程序，動態鏈接及運行庫和標準庫的實現，和一些操作系統的機制。了解計算機上程序運行的一個基本脈絡。

1.2變不離其宗

計算機最關鍵的三個部分：CPU,內存,I/O控制芯片。

• 早期的計算機：沒有復雜的圖形功能，CPU和內存頻率一樣，都連接在同一個總線上。
• CPU頻率提升：內存跟不上CPU，產生了和內存頻率一致的系統總線，CPU使用倍頻的方式和總線通信。
• 圖形界面的出現：圖形芯片需要和內存和CPU大量交換數據，慢速的I/O總線無法滿足圖形設備的巨大需求。為了高效處理數據，設計了一個高速的北橋芯片。后來有設計處理低速處理設備南橋芯片，磁盤，USB，鍵盤都是連接在南橋上。在由南橋將它們匯總到北橋上。

北橋

• 北橋左邊CPU和cache：CPU負責所有控制和運算。
• 北橋下面PCI總線
• 北橋右邊memory

SMP和多核

現在CPU已經達到物理極限，被4GHz所限制，于是，開始通過增加CPU數量來提高計算機速度。
對稱多處理器（SMP）：最常見的一種形式。每個CPU在系統中所處的地位和所發揮的功能是一樣，是相互對稱的。但在處理程序時，我們并不能把他們分成若干個不相干的子問題，所以，使得多處理器速度實際提高得并沒有理論上那么高。當對于相互獨立的問題，多處理器就能最大效能的發揮威力了（比如：大型數據庫,網絡服務等）。
對處理器由于造價比較高昂，主要用在商用電腦上，對于個人電腦，主要是多核處理器。
多核處理器：其實際上是(SMP)的簡化版，思想是將多個處理器合并在一起打包出售，它們之間共享比較昂貴的緩存部件，只保留了多個核心。在邏輯上看，它們和SMP完全相同。

1.3站得高,看得遠

系統軟件：一般用于管理計算機本地的軟件。

主要分為兩塊：

• 平臺性的：操作系統內核，驅動程序，運行庫。
• 程序開發：編譯器，匯編器，鏈接器。

計算機系統軟件體系結構采用一種層的結構。
每個層次之間都需要相互通信，那么它們之間就有通信協議，我們將它稱為接口，接口下層是提供者，定義接口。上層是使用者，使用接口實現所需功能。
除了硬件和應用程序，其他的都是中間層，每個中間層都是對它下面的那層的包裝和擴展。它們使得應用程序和硬件之間保持相對獨立。
從整個層次結構來看，開發工具與應用程序屬于同一個層次，因為它們都使用同一個接口—操作系統應用程序編程接口。應用程序接口提供者是運行庫，什么樣的運行庫提供什么樣的接口。winsows的運行庫提供Windows API，Linux下的Gliba庫提供POSIX的API。
運行庫使用操作系統提供的系統調用接口。
系統調用接口在實現中往往以軟件中斷的方式提供。
操作系統內核層對于硬件層來說是硬件接口的使用者，而硬件是接口的定義者。這種接口叫做硬件規格。

1.4操作系統做了什么

操作系統的一個功能是提供抽象的接口，另外一個主要功能是管理硬件資源。
一個計算機中的資源主要分CPU,存儲器（包括內存和磁盤）和I/O設備。下面從這3個方面來看如何挖機它們。

1.4.1不要讓CPU打盹

多道程序：編譯一個監控程序，當程序不需要使用CPU時，將其他在等待CPU的程序啟動。但它的弊端是不分輕重緩急，有時候一個交互操作可能要等待數十分鐘。
改進后
分時系統：每個CPU運行一段時間后，就主動讓出給其他CPU使用。完整的操作系統雛形在此時開始出現。但當一個程序死機的時候，無法主動讓出CPU，那么，整個系統都無法響應。
目前操作系統采用的方式
多任務系統：操作系統接管了所有的硬件資源，并且本身運行在一個受硬件保護的級別。所有的應用都以進程的方式運行在比操作系統更低的級別，每個進程都有自己獨立的地址空間，使得進程之間的地址空間相互隔離。CPU由操作系統進行同一分配，每個進程根據進程優先級的高低都有機會獲得CPU，但如果運行超過一定的時間，CPU會將資源分配給其他進程，這種CPU分配方式是搶占式。如果操作系統分配每個進程的時間很短，就會造成很多進程都在同時運行的假象，即所謂的宏觀并行，微觀串行。

設備驅動

操作系統作為硬件層的上層，它是對硬件的管理和抽象。
對于操作系統上面的運行庫和應用程序來說，它們只希望看到一個統一的硬件訪問模式。
當成熟的操作系統出現后，硬件逐漸成了抽象的概念。在UNIX中，硬件設備的訪問形式和訪問普通的文件形式一樣。在Windows系統中，圖形硬件被抽象成GDI，聲音和多媒體設備被抽象成DirectX對象，磁盤被抽象成普通文件系統。
這些繁瑣的硬件細節全都交給了操作系統中的硬件驅動。
文件系統管理這磁盤的存儲方式。
磁盤的結構：一個硬盤往往有多個盤片，每個盤片分兩面，每面按照同心圓劃分為若干磁道，每個磁道劃分為若干扇區，每個扇區一般512字節。
LBA：整個硬盤中所有扇區從0開始編號，一直到最后一個扇區，這個扇區編號叫做邏輯扇區號。
文件系統保存了這些文件的存儲結構，負責維護這些數據結構并且保證磁盤中的扇區能有效的組織和利用。

1.5內存不夠怎么辦

在早期計算機中，程序是直接運行在物理內存上的，程序所訪問的都是物理地址。
那么如何將計算機有限的地址分配給多個程序使用。
直接按物理內存分配將產生很多問題：

• 地址空間不隔離：所有的程序都直接訪問物理地址，導致程序使用的物理地址不是相互隔離的，惡意的程序很容易串改其他程序的內存數據。
• 內存使用效率低：由于沒有有效的內存管理機制，通常一個程序執行的時候，監控程序要將整個程序讀入。內存不夠的時候，需要先將內存中的程序讀出，保存在硬盤上，才能將需要運行的程序讀入。這樣會使得整個過程有大量數據換入換出。
• 程序運行地址不確定：每次程序運行都需要內存分配一塊足夠大的內存空間，使得這個地址是不確定的。但在程序編寫的時候，他訪問的數據和指令跳轉的目標地址都是固定的，這就涉及到了程序的重定向問題。

一種解決辦法：
中間層：使用一種間接的地址訪問方法，我們把程序給出的地址看作一種虛擬地址。虛擬地址是物理地址的映射，只要處理好這個過程，就可以起到隔離的作用。

1.5.1關于隔離

普通的程序它只需要一個簡單的執行環境，一個單一的地址空間，有自己的CPU。
地址空間比較抽象，如果把它想象成一個數組，每一個數組是一字節，數組大小就是地址空間的長度，那么32位的地址空間大小就是2^32=4294967296字節，即4G，地址空間有效位是0x00000000~0xFFFFFFFF。
地址空間分為兩種：
物理空間：就是物理內存。32位的機器，地址線就有32條，物理空間4G，但如果值裝有512M的內存，那么實際有效的空間地址就是0x00000000~0x1FFFFFFF，其他部分都是無效的。
虛擬空間：每個進程都有自己獨立的虛擬空間，而且每個進程只能訪問自己的空間地址，這樣就有效的做到了進程隔離。

1.5.2分段

基本思路：把一段與程序所需要的內存空間大小的虛擬空間映射到某個地址空間。虛擬空間的每個字節對應物理空間的每個字節。這個映射過程由軟件來完成。
分段的方式可以解決之前的第一個（地址空間不隔離）和第三個問題（程序運行地址不確定）
第二問題內存使用效率問題依舊沒有解決。

1.5.3分頁

基本方法：把地址空間人為的分成固定大小的頁，每一頁大小有硬件決定或硬件支持多種大小的頁，由操作系統決定頁的大小。
目前幾乎所有的PC上的操作系統都是4KB大小的頁。
我們把進程的虛擬地址空間按頁分割，把常用的數據和代碼頁轉載到內存中，把不常用的代碼和數據保存到磁盤里，當需要的時候從磁盤取出來。
虛擬空間的頁叫做虛擬頁（VP）,物理內存中頁叫做物理頁，把磁盤中的頁叫做磁盤頁。虛擬空間的有的頁被映射到同一個物理頁，這樣就可以實現內存共享。
當進程需要一個頁時，這個頁是磁盤頁時，硬件會捕獲到這個消息，就是所謂的頁錯誤，然后操作系統接管進程，負責從磁盤中讀取內容裝入內存中，然后再將內存和這個頁建立映射關系。
保護也是頁映射的目的之一，每個頁都可以設置權限屬性，只有操作系統可以修改這些屬性，這樣操作系統就可以保護自己保護進程。
虛擬存儲的實現需要依靠硬件支持，所有硬件都采用一個叫做MMU的部件來進行頁映射。
CPU發出虛擬地址經過MMU轉換成物理地址，MMU一般都集成在CPU內部。

1.6眾人拾柴火焰高

1.6.1線程基礎

多線程現在作為實現軟件并發執行的一個重要方法，具有越來越重的地位。

什么是線程

線程有時被稱為輕量級的進程，是程序執行流的最小單位。

構成：

• 線程ID
• 當前指令指針
• 寄存器集合
• 堆棧空間（代碼段，數據段，堆）
• 進程級的資源（打開文件和信號）

線程與進程的關系：

多線程可以互不干擾的并發執行，并共享進程的全局變量和堆的數據。
使用多線程的原因有如下幾點：

• 某個操作可能會陷入長時間等待，等待的線程會進入睡眠狀態，無法繼續執行。
• 某個操作會消耗大量的時間，如果只有一個線程，程序和用戶之間的交互會中斷。
• 程序邏輯本身就要求并發操作。
• 多CPU或多核計算機，本身具備同時執行多個線程的能力。
• 相對于多進程應用，多線程在數據共享方面效率要高很多。

線程的訪問權限

線程的訪問非常自由，它可以訪問進程內存里所有數據，包括其他線程的堆棧（如果知道地址的話，情況很少見）。
線程自己的私用存儲空間：

• 棧（并發完全無法被其他線程訪問）
• 線程局部存儲。某些操作系統為線程提供私用空間，但容量有限。
• 寄存器。執行流的基本數據，為線程私用。

線程調度與優先級

不論在多處理器還是單處理器上，線程都是“并發”的。
線程數量小于處理器數量時，是真正并發的。
單處理器下，并發是模擬的，操作系統會讓這些多線程程序輪流執行，每次都只執行一小段時間，這就稱為線程調度。
線程調度中，線程擁有三種狀態：

• 運行：線程正在執行
• 就緒：線程可以立刻運行，但CPU被占用
• 等待：線程正在等待某一事件發生，無法立即執行。

處于運行中的線程擁有一段可以執行的時間，這稱為時間片，當時間片用盡的時候，進程進入就緒狀態，如果在用盡之前開始等待某事件，那么它就進入等待狀態。每當一個線程離開運行狀態的時候，調度系統就會選擇一個其他的就緒線程繼續執行。

現在的主流調度方法盡管都不一樣，但基本都帶有優先級調度和輪轉法。
輪轉法：各個線程輪流執行一段時間。
優先級調度：按線程的優先級來輪流執行，每個線程都擁有各自的線程優先級。
在win和lin里面，線程優先級不僅可以由用戶手動設置，系統還會根據不同線程表現自動調整優先級。
一般頻繁等待的線程稱之為IO密集型線程，而把很少等待的線程稱為CPU密集型線程。
優先級調度下，存在一種餓死現象。
餓死：線程優先級較低，在它執行之前，總是有較高級的線程要執行，所以，低優先級線程總是無法執行的。
當一個CPU密集型線程獲得較高優先級時，許多低優先級線程就可能被餓死。
為了避免餓死，操作系統常常會逐步提升那些等待時間過長的線程。
線程優先級改變一般有三種方式：

• 用戶指定優先級
• 根據進入等待狀態的頻繁程度提升或降低優先級
• 長時間得不到執行而被提升優先級

可搶占線程和不可搶占線程

搶占：在線程用盡時間片之后被強制剝奪繼續執行的權利，而進入就緒狀態。
在早期的系統中，線程是不可搶占的，線程必須主動進入就緒狀態。
在不可搶占線程中，線程主動放棄主要是2種：

• 當線程試圖等待某個事件（I/O）時
• 線程主動放棄時間片

不可搶占線程有一個好處，就是線程調度只會發生在線程主動放棄執行或線程等待某個事件的時候，這樣就可以避免一些搶占式線程時間不確定而產生的問題。

Linux的多線程

Linux內核中并不存在真正意義上的線程概念。Linux所有執行實體（線程和進程）都稱為任務，每一個任務概念上都類似一個單線程的進程，具有內存空間，執行實體，文件資源等。Linux不同任務之間可以選擇共享內存空間，相當于同一個內存空間的多個任務構成一個進程，這些任務就是進程中的線程。

fork產生新任務速度非常快，因為fork不復制原任務的內存空間，而是和原任務一起共享一個寫時復制的內存空間。

寫時復制：兩個任務可以同時自由讀取內存，當任意一個任務試圖對內存進行修改時，內存就會復制一份單獨提供給修改方使用。
fork只能夠產生本任務的鏡像，因此需要和exec配合才能啟動別的新任務。
而如果要產生新線程，則使用clone。
clone可以產生一個新的任務，從指定位置開始執行，并且共享當前進程的內存空間和文件等，實際效果就是產生一個線程。

1.6.2線程安全

多線程程序處于一個多變的環境中，可訪問的全局變量和堆數據隨時都可能被其他的線程改變。因此多線程程序在并發時數據的一致性變得非常重要。

競爭與原子操作

++i的實現方法：

• 讀取i到某個寄存器X
• X++
• 將X的內容存儲回i
  單條指令的操作稱為原子的，單挑指令的執行不會被打斷。在windows里，有一套API專門進行一些原子操作，這些API稱為Interlocked API。

同步與鎖

為了防止多個線程讀取同一個數據產生不可預料結果，我們將各個線程對一個數據的訪問同步。
同步：在一個線程對一個數據訪問結束的時候，其他線程不能對同一個數據進行訪問。對數據的訪問被原子化。
鎖：鎖是一種非強制機制，每一個線程在訪問數據或者資源之前會先獲取鎖，在訪問結束后會釋放鎖。在鎖被占用時候試圖獲取鎖時，線程會等待，知道鎖可以重新使用。
二元信號量：最簡單的鎖，它適合只能被唯一一個線程獨占訪問的資源，它的兩種狀態：

• 非占用狀態：第一個獲取該二元信號量的線程會獲得該鎖，并將二元信號量置為占用狀態，其他所有訪問該二元信號量線程將會等待。
• 占用狀態

信號量：允許多個線程并發訪問的資源。一個初始值為N的信號量允許N個線程并發訪問。
操作如下：

• 將信號量值鍵1
• 如果信號量值小于0，就進入等待狀態。

訪問完資源后，線程釋放信號量：

• 將信號量加1
• 如果信號量的值小于1，喚醒一個等待中的線程。

互斥量：和二元信號量很類似，但和信號量不同的是：信號量在一個系統中，可以被任意線程獲取或釋放。互斥量要求那個線程獲取互斥量，那么哪個線程就釋放互斥量，其他線程釋放無效。
臨界區：比互斥量更加嚴格的手段。把臨界區的鎖獲取稱為進入臨界區，而把鎖的釋放稱為離開臨界區。臨界區和互斥量，信號量區別在與互斥量，信號量在系統中任意進程都是可見的。臨界區的作用范圍僅限于本線程，其他線程無法獲取。其他性質與互斥量相同。
讀寫鎖：致力于一種更加特定的場合的同步。如果使用之前使用的信號量、互斥量或臨界區中的任何一種進行同步，對于讀取頻繁，而僅僅是偶爾寫入的情況會顯得非常低效。讀寫鎖可以避免這個問題。對于同一個鎖，讀寫鎖有兩種獲取方式：

• 共享的
• 獨占的

讀寫鎖的總結

條件變量：作為同步的手段，作用類似于一個柵欄。對于條件變量，線程有兩個操作：

• 線程可以等待條件變量，一個條件變量可以被多個線程等待
• 線程可以喚醒條件變量，此時某個或所有等待此條件變量的線程都會被喚醒并繼續支持

使用條件變量可以讓許多線程一起等待某個事件的發生，當事件發生時，所有線程可以一起恢復執行。

可重入與線程安全

一個函數被重入，表示這個函數沒有執行完成，由于外部因素或內部調用，又一次進入該函數執行。
一個函數要被重入，只有兩種情況：

• 多個線程同時執行這個函數
• 函數自身（可能經過多層調用之后）調用自身

一個函數被稱為可重入，表示重入之后不會產生任何不良影響

可重入函數：

一個函數要成為可重入，必須具有如下特點：

• 不使用任何（局部）靜態或全局的非const變量
• 不返回任何（局部）靜態或全部的非const變量的指針
• 僅依賴調用方提供的參數
• 不依賴任何單個資源的鎖
• 不調用任何不可重入的函數

可重入是并發安全的強力保障，一個可重入的函數可以在多程序環境下方向使用

過度優化

有時候合理的合理的使用了鎖也不一定能保證線程的安全。

上面X的值應該為2，但如果編譯器為了提高X的訪問速度，把X放到了某個寄存器里面，不同線程的寄存器是各自獨立的，因此，如果Thread1先獲得鎖，則程序的執行可能會呈現如下：
[Thread1]讀取x的值到某個寄存器R [1] (R[1]=0);
[Thread1]R[1]++(由于之后可能要訪問到x,所以Thread1暫時不將R[1]寫回x);
[Thread2]讀取x的值到某個寄存器R[2] (R[2]=0);
[Thread2]R[2]++(R[2]=1);
[Thread2]將R[2]寫回至x(x=1);
[Thread1] (很久以后)將R[1]寫回至x(x=1);
如果這樣，即使加鎖也不能保證線程安全

上面代碼有可能發生r1=r2=0的情況。
CPU動態調度：在執行程序的時候，為了提高效率有可能交換指令的順序。
編譯器在進行優化的時候，也可能為了效率交換兩個毫不相干的相鄰指令的執行順序。
上面代碼執行順序可能是這樣：

使用volatile關鍵字可以阻止過度優化，colatile可以做兩件事情：

• 阻止編譯器為了提高速度將一個變量緩存到寄存器內而不寫回
• 阻止編譯器調整操作volatile變量的指令順序

但volatile無法阻止CPU動態調度換序
C++中，單例模式。

CPU的亂序執行可能會對上面代碼照成影響
C++里的new包含兩個步驟：

• 分配內存
• 調用構造函數

所以pInst=new T包含三個步驟：

• 分配內存
• 在內存的位置上調用構造函數
• 將內存的地址賦值給pInst

這三步中2和3的步驟可以顛倒，可能出現這種情況：pInst中的值不是NULL，但對象還是沒有構造完成。
要阻止CPU換序，可以調用一條指令，這條指令常常被稱為barrier：它會阻止CPU將該指令之前的指令交換到barrier之后。
許多體系的CPU都提供了barrier指令，不過，它們的名稱各不相同。例如POWERPC提供的指令就叫做lwsync。所以我們可以這樣保證線程安全：

1.6.3多線程的內部情況

線程的并發執行是由多處理器或操作系統調度來實現的。windows和linux都在內核中提供線程支持，有多處理器或調度來實現并發。用戶實際使用線程并不是內核線程，而是存在于用戶態的用戶線程。用戶線程并不一定在操作系統內核里對應同等數量的內核線程。對用戶來說，如果有三個線程同時執行，可能在內核中只有一個線程。

一對一模型

對于直接支持線程的系統，一對一模型始終是最為簡單的模型。一個用戶使用的線程就唯一對應一個內核使用的線程，但返回來，一個內核里面的線程在用戶態不一定有對應的線程存在。

對于一對一模型，線程之間的并發是真正的并發，一個線程因為某個原因阻塞，并不會影響到其他線程。一對一模型也可以讓多線程程序在多處理器的系統上有更好的表現。
一般直接使用API或者系統調用創建的線程均為一對一線程。
一對一線程的兩個缺點：

• 由于許多操作系統限制了內核線程數量，因此一對一線程會讓用戶的線程數量受到限制。
• 許多操作系統內核線程調度是，上下文切換的開銷較大，導致用戶線程的執行效率下降。

多對一模型

多對一模型將多個用戶線程映射到一個內核線程上，線程之間的切換由用戶態的代碼來進行，相對于一對一模型，多對一模型的線程切換要快速許多。

多對一模型的問題就是如果一個用戶線程阻塞了，那么所有的線程都將無法執行。在多處理系統上，處理器的增多對多對一模型的線程性能不會有明顯幫助。多對一模型得到的好處是高效的上下文切換和幾乎無限制的線程數量。

多對多模型

多對多模型結合了多對一和一對一的特點，將多個用戶線程映射到少數但不止一個內核線程上。

一個用戶線程阻塞并不會使得所有的用戶線程阻塞。并且對用戶線程數量也沒有什么限制，在多處理器系統上，多對多模型的線程也能得到一定的性能提升，不過提升的幅度沒有一對一模型高。