作業系統-初見？見了好多次，次次都要學！

目錄

作業系統

不是很難哦，好吧其實很難，結合Linux 學習。

學校的課程 ，大家聽聽就好，那一本書，是真的不夠，也不好用，多找找資料，多看幾遍。

一、硬體結構

複習，兄弟們看看就好。

歷史是怎麼發展

最開始是圖靈機，大概長這個樣子。

很原始的 0 1 操作，接下來看看 馮諾依曼模型

今天的電腦基本上還是大體是這個結構，是不是很棒。

記憶體，我們的程式和數據都是存儲在記憶體，存儲的區域是線性的。

中央處理器，也就是我們常說的 CPU，32 位和 64 位 CPU 最主要區別在於⼀次能計算多少位元組數據。

常⻅的暫存器種類：

通⽤暫存器，⽤來存放需要進⾏運算的數據，⽐如需要進⾏加和運算的兩個數據。

程式計數器，⽤來存儲 CPU 要執⾏下⼀條指令「所在的記憶體地址」，注意不是存儲了下⼀條要執⾏的指令，此時指令還在記憶體中，程式計數器只是存儲了下⼀條指令的地址。

指令暫存器，⽤來存放程式計數器指向的指令，也就是指令本身，指令被執⾏完成之前，指令都存儲在這⾥。

匯流排是⽤於 CPU 和記憶體以及其他設備之間的通訊，匯流排可分為 3 種：

地址匯流排，⽤於指定 CPU 將要操作的記憶體地址；

數據匯流排，⽤於讀寫記憶體的數據；

控制匯流排，⽤於發送和接收訊號，⽐如中斷、設備複位等訊號，CPU 收到訊號後⾃然進⾏響應，這時也需要控制匯流排；

程式是怎麼執行

底層會涉及到彙編語言以及各種機器的指令


現代⼤多數 CPU 都使⽤來流⽔線的⽅式來執⾏指令，

所謂的流⽔線就是把⼀個任務拆分成多個⼩任務，於是⼀條指令通常分為 4 個階段，稱為 4 級流⽔線，

四個階段的具體含義：

  1. CPU 通過程式計數器讀取對應記憶體地址的指令，這個部分稱為 Fetch（取得指令）；
  2. CPU 對指令進⾏解碼，這個部分稱為 Decode（指令解碼）；
  3. CPU 執⾏指令，這個部分稱為 Execution（執⾏指令）；
  4. CPU 將計算結果存回暫存器或者將暫存器的值存⼊記憶體，這個部分稱為 Store（數據回寫）；
    上⾯這 4 個階段，我們稱為指令周期（Instrution Cycle），CPU 的⼯作就是⼀個周期接著⼀個周期，周
    ⽽復始。

來一些小問題：

64 位相⽐ 32 位 CPU 的優勢在哪嗎？64 位 CPU 的計算性能⼀定⽐ 32 位 CPU ⾼很多嗎？

64 位相⽐ 32 位 CPU 的優勢主要體現在兩個⽅⾯：

64 位 CPU 可以⼀次計算超過 32 位的數字，⽽ 32 位 CPU 如果要計算超過 32 位的數字，要分多步驟進⾏計算，效率就沒那麼⾼，

但是⼤部分應⽤程式很少會計算那麼⼤的數字，所以只有運算⼤數字的時候，64 位 CPU 的優勢才能體現出來，否則和 32 位 CPU 的計算性能相差不⼤。

64 位 CPU 可以定址更⼤的記憶體空間，32 位 CPU 最⼤的定址地址是 4G，即使你加了 8G ⼤⼩的記憶體，也還是只能定址到 4G，⽽ 64 位 CPU 最⼤定址地址是 2^64 ，遠超於 32 位 CPU 最⼤定址地址的 2^32 。

你知道軟體的 32 位和 64 位之間的區別嗎？再來 32 位的作業系統可以運⾏在 64 位的電腦上嗎？64 位的操
作系統可以運⾏在 32 位的電腦上嗎？如果不⾏，原因是什麼？

64 位和 32 位軟體，實際上代表指令是 64 位還是 32 位的：

如果 32 位指令在 64 位機器上執⾏，需要⼀套兼容機制，就可以做到兼容運⾏了。

但是如果 64 位指令在 32 位機器上執⾏，就⽐較困難了，因為 32 位的暫存器存不下 64 位的指令；

作業系統其實也是⼀種程式，我們也會看到作業系統會分成 32 位作業系統、64 位作業系統，

其代表意義就是作業系統中程式的指令是多少位，⽐如 64 位作業系統，指令也就是 64 位，因此不能裝在32 位機器上。

總之，硬體的 64 位和 32 位指的是 CPU 的位寬，軟體的 64 位和 32 位指的是指令的位寬。

存儲器

CPU Cache

CPU Cache ⽤的是⼀種叫 SRAM（Static Random-Access Memory，靜態隨機存儲器） 的芯⽚。

SRAM 之所以叫「靜態」存儲器，是因為只要有電，數據就可以保持存在，⽽⼀旦斷電，數據就會丟失
了。

在 SRAM ⾥⾯，⼀個 bit 的數據，通常需要 6 個電晶體，所以 SRAM 的存儲密度不⾼，同樣的物理空間
下，能存儲的數據是有限的，不過也因為 SRAM 的電路簡單，所以訪問速度⾮常快。

CPU 的⾼速快取，通常可以分為 L1、L2、L3 這樣的三層⾼速快取，也稱為⼀級快取、⼆次快取、三次緩
存。

CPU Cache 通常會分為 L1、L2、L3 三層，
其中 L1 Cache 通常分成「數據快取」和「指令快取」，
L1是距離 CPU 最近的，因此它⽐ L2、L3 的讀寫速度都快、存儲空間都⼩。我們⼤腦中短期記憶，就好⽐
L1 Cache，⽽⻓期記憶就好⽐ L2/L3 Cache。

暫存器和 CPU Cache 都是在 CPU 內部，跟 CPU 挨著很近，因此它們的讀寫速度都相當的快，但是能存儲的數據很少，畢竟 CPU 就這麼丁點⼤。

再實際的開發中，我們的設計思想也是和電腦有著異曲同工之妙

一個記憶體地址怎麼取到實際的記憶體值呢？

如何寫出讓 CPU 跑得更快的程式碼？

我們知道 CPU 訪問記憶體的速度，⽐訪問 CPU Cache 的速度慢了 100 多倍，

所以如果 CPU 所要操作的數據在 CPU Cache 中的話，這樣將會帶來很⼤的性能提升。訪問的數據在 CPU Cache 中的話，

意味著快取命中，快取命中率越⾼的話，程式碼的性能就會越好，CPU 也就跑的越快。

於是，「如何寫出讓 CPU 跑得更快的程式碼？」這個問題，可以改成「如何寫出 CPU 快取命中率⾼的程式碼？」。

如何提升數據快取的命中率？

看一個有趣的例子：

// 二維數組
array[N][N] = 0;
//形式
for(i=0;i<N;i+=1){
	for(j=0;j<N;j+=1){
		array[i][j] = 0;
	}
}
//形式二:
for(i=0;i<N;i+=1){
	for(j=0;j<N;j+=1){
		array[j][i] = 0;
	}
}
//就是  i  j  的位置互換了

結論：經過測試，形式⼀ array[i][j] 執⾏時間⽐形式⼆ array[j][i] 快好⼏倍。

為什麼：第一種形式是和cpu的訪問的順序是一致的，訪問第一個的時候會順序將後面的加入到快取，

但是後一種是跳躍的，如果數值比較大，就沒有辦法加入進去。

這跟 CPU Cache Line 有關，它表示 CPU Cache ⼀次性能載入數據的⼤⼩，可以在Linux ⾥通過 coherency_line_size 配置查看 它的⼤⼩，通常是 64 個位元組。

因此，遇到這種遍曆數組的情況時，按照記憶體布局順序訪問，將可以有效的利⽤ CPU Cache 帶來的好處，這樣我們程式碼的性能就會得到很⼤的提升，

如果提升多核 CPU 的快取命中率？

在單核 CPU，雖然只能執⾏⼀個進程，

但是作業系統給每個進程分配了⼀個時間⽚，時間⽚⽤完了，就調度下⼀個進程，於是各個進程就按時間⽚交替地佔⽤ CPU，從宏觀上看起來各個進程同時在執⾏。

⽽現代 CPU 都是多核⼼的，進程可能在不同 CPU 核⼼來回切換執⾏，這對 CPU Cache 不是有利的，

雖然 L3 Cache 是多核⼼之間共享的，但是 L1 和 L2 Cache 都是每個核⼼獨有的，

如果⼀個進程在不同核⼼來回切換，各個核⼼的快取命中率就會受到影響，相反如果進程都在同⼀個核⼼上執⾏，

那麼其數據的 L1和 L2 Cache 的快取命中率可以得到有效提⾼，快取命中率⾼就意味著 CPU 可以減少訪問 記憶體的頻率。

當有多個同時執⾏「計算密集型」的執行緒，為了防⽌因為切換到不同的核⼼，⽽導致快取命中率下降的問題，

我們可以把執行緒綁定在某⼀個 CPU 核⼼上，這樣性能可以得到⾮常可觀的提升。

在 Linux 上提供了 sched_setaffinity ⽅法，來實現將執行緒綁定到某個 CPU 核⼼這⼀功能。

CPU 快取⼀致性

CPU Cache 的結構，CPU Cache 是由很多個 Cache Line 組成的，CPU Line 是 CPU

從記憶體讀取數據的基本單位，⽽ CPU Line 是由各種標誌（Tag）+ 數據塊（Data Block）組成。

我們當然期望 CPU 讀取數據的時候，都是儘可能地從 CPU Cache 中讀取，⽽不是每⼀次都要從記憶體中獲
取數據。

所以，身為程式設計師，我們要儘可能寫出快取命中率⾼的程式碼，這樣就有效提⾼程式的性能。

什麼時機才把 Cache 中的數據寫回到記憶體呢？

  • 寫直達（Write Through）
  • 寫回（Write Back）

寫直達

保持記憶體與 Cache ⼀致性最簡單的⽅式是，把數據同時寫⼊記憶體和 Cache 中，這種⽅法稱為寫直達（Write Through）。

寫直達法很直觀，也很簡單，但是問題明顯，⽆論數據在不在 Cache ⾥⾯，每次寫操作都會寫回到記憶體，這樣寫操作將會花費⼤量的時間，⽆疑性能會受到很⼤的影響。

寫回

既然寫直達由於每次寫操作都會把數據寫回到記憶體，⽽導致影響性能，於是為了要減少數據寫回記憶體的頻率，就出現了寫回（Write Back）的⽅法。

在寫回機制中，當發⽣寫操作時，新的數據僅僅被寫⼊ Cache Block ⾥，只有當修改過的 Cache Block「被替換」時才需要寫到記憶體中，減少了數據寫回記憶體的頻率，這樣便可以提⾼系統的性能。

快取⼀致性問題

現在 CPU 都是多核的，由於 L1/L2 Cache 是多個核⼼各⾃獨有的，那麼會帶來多核⼼的快取⼀致性（Cache Coherence） 的問題，如果不能保證快取⼀致性的問題，就可能造成結果錯誤。

  • 第⼀點，某個 CPU 核⼼⾥的 Cache 數據更新時，必須要傳播到其他核⼼的 Cache，這個稱為寫傳播（Wreite Propagation）；
  • 第⼆點，某個 CPU 核⼼⾥對數據的操作順序，必須在其他核⼼看起來順序是⼀樣的，這個稱為事務的串形化（Transaction Serialization）

匯流排嗅探

寫傳播的原則就是當某個 CPU 核⼼更新了 Cache 中的數據，要把該事件⼴播通知到其他核⼼。

最常⻅實現的⽅式是匯流排嗅探（Bus Snooping）。

我還是以前⾯的 i 變數例⼦來說明匯流排嗅探的⼯作機制，當 A 號 CPU 核⼼修改了 L1 Cache 中 i 變數的值，

通過匯流排把這個事件⼴播通知給其他所有的核⼼，然後每個 CPU 核⼼都會監聽匯流排上的⼴播事件，

並檢查是否有相同的數據在⾃⼰的 L1 Cache ⾥⾯，如果 B 號 CPU 核⼼的 L1 Cache 中有該數據，

那麼也需要把該數據更新到⾃⼰的 L1 Cache。

可以發現，匯流排嗅探⽅法很簡單， CPU 需要每時每刻監聽匯流排上的⼀切活動，但是不管別的核⼼的Cache 是否快取相同的數據，都需要發出⼀個⼴播事件，這⽆疑會加重匯流排的負載。

另外，匯流排嗅探只是保證了某個 CPU 核⼼的 Cache 更新數據這個事件能被其他 CPU 核⼼知道，但是並不能保證事務串形化。

於是，有⼀個協議基於匯流排嗅探機制實現了事務串形化，也⽤狀態機機制降低了匯流排頻寬壓⼒，這個協議就是 MESI 協議，這個協議就做到了 CPU 快取⼀致性。

MESI 協議

MESI 協議其實是 4 個狀態單詞的開頭字⺟縮寫，分別是：

Modified，已修改

Exclusive，獨佔

Shared，共享

Invalidated，已失效

這四個狀態來標記 Cache Line 四個不同的狀態。

狀態 描述
M（Modified） 代表該快取行中的內容被修改了，並且該快取行只被快取在該CPU中。這個狀態的快取行中的數據和記憶體中的不一樣，在未來的某個時刻它會被寫入到記憶體中（當其他CPU要讀取該快取行的內容時。或者其他CPU要修改該快取對應的記憶體中的內容時
E（Exclusive） 代表該快取行對應記憶體中的內容只被該CPU快取，其他CPU沒有快取該快取對應記憶體行中的內容。這個狀態的快取行中的內容和記憶體中的內容一致。該快取可以在任何其他CPU讀取該快取對應記憶體中的內容時變成S狀態。或者本地處理器寫該快取就會變成M狀態
S（Shared） 該狀態意味著數據不止存在本地CPU快取中，還存在別的CPU的快取中。這個狀態的數據和記憶體中的數據是一致的。當其他CPU修改該快取行對應的記憶體的內容時會使該快取行變成 I 狀態
I（Invalid） 代表該快取行中的內容是無效的

CPU 是如何執⾏任務的？

CPU 從記憶體中讀取數據到 Cache 的時候，並不是⼀個位元組⼀個位元組讀取，⽽是⼀塊⼀塊的⽅式來讀取數據的，

這⼀塊⼀塊的數據被稱為 CPU Line（快取⾏），所以 CPU Line 是 CPU 從記憶體讀取數據到 Cache的單位。

Cache 偽共享是什麼？⼜如何避免這個問題？

可以發現如果 1 號和 2 號 CPU 核⼼這樣持續交替的分別修改變數 A 和 B，就會重複 」變為失效狀態「 和 」變為修改狀態「 這兩個步驟，

Cache 並沒有起到快取的效果，雖然變數 A 和 B 之間其實並沒有任何的關係，但是因為同時歸屬於⼀個 Cache Line ，

這個 Cache Line 中的任意數據被修改後，都會相互影響，從⽽出現 這兩個步驟。

因此，這種因為多個執行緒同時讀寫同⼀個 Cache Line 的不同變數時，⽽導致 CPU Cache 失效的現象稱為偽共享（False Sharing）。

避免偽共享的⽅法

在 Linux 內核中存在 __cacheline_aligned_in_smp 宏定義，是⽤於解決偽共享的問題。

  • 如果在多核（MP）系統⾥，該宏定義是 __cacheline_aligned ，也就是 Cache Line 的⼤⼩；
  • ⽽如果在單核系統⾥，該宏定義是空的；

為了防⽌前⾯提到的 Cache 偽共享問題，我們可以使⽤上⾯介紹的宏定義，將 b 的地址設置為Cache Line 對⻬地址。

所以，避免 Cache 偽共享實際上是⽤空間換時間的思想，浪費⼀部分 Cache 空間，從⽽換來性能的提升。

我們再來看⼀個應⽤層⾯的規避⽅案，

有⼀個 Java 並發框架 Disruptor 使⽤「位元組填充 + 繼承」的⽅式，來避免偽共享的問題。

Disruptor 中有⼀個 RingBuffer 類會經常被多個執行緒使⽤，程式碼如下：

CPU Cache 從記憶體讀取數據的單位是 CPU Line，⼀般 64 位 CPU 的 CPU Line 的⼤⼩是 64個位元組，

⼀個 long 類型的數據是 8 個位元組，所以 CPU ⼀下會載入 8 個 long 類型的數據。

根據 JVM 對象繼承關係中⽗類成員和⼦類成員，記憶體地址是連續排列布局的，

因此 RingBufferPad 中的 7個 long 類型數據作為 Cache Line 前置填充，⽽ RingBuffer 中的 7 個 long 類型數據則作為 Cache Line 後置填充，

這 14 個 long 變數沒有任何實際⽤途，更不會對它們進⾏讀寫操作。

另外，RingBufferFelds ⾥⾯定義的這些變數都是 final 修飾的，意味著第⼀次載入之後不會再修改， ⼜由於「前後」各填充了 7 個不會被讀寫的 long 類型變數，所以⽆論怎麼載入 Cache Line，

這整個 CacheLine ⾥都沒有會發⽣更新操作的數據，於是只要數據被頻繁地讀取訪問，就⾃然沒有數據被換出 Cache的可能，也因此不會產⽣偽共享的問題。

CPU 如何選擇執行緒的？

⼀般來說，沒有創建執行緒的進程，是只有單個執⾏流，它被稱為是主執行緒。

如果想讓進程處理更多的事情，可以創建多個執行緒分別去處理，但不管怎麼樣，它們對應到內核⾥都是 tark_struct 。

所以，Linux 內核⾥的調度器，調度的對象就是 tark_struct ，接下來我們就把這個數據結構統稱為任務。

在 Linux 系統中，根據任務的優先順序以及響應要求，主要分為兩種，其中優先順序的數值越⼩，優先順序越⾼：

  • 實時任務，對系統的響應時間要求很⾼，也就是要儘可能快的執⾏實時任務，優先順序在 0~99 範圍內的就算實時任務；
  • 普通任務，響應時間沒有很⾼的要求，優先順序在 100~139 範圍內都是普通任務級別；

調度類

由於任務有優先順序之分，Linux 系統為了保障⾼優先順序的任務能夠儘可能早的被執⾏，於是分為了這⼏種調度類。

Deadline 和 Realtime 這兩個調度類，都是應⽤於實時任務的，這兩個調度類的調度策略合起來共有這三種，它們的作⽤如下：

  • SCHED_DEADLINE：是按照 deadline 進⾏調度的，距離當前時間點最近的 deadline 的任務會被優先調度；
  • SCHED_FIFO：對於相同優先順序的任務，按先來先服務的原則，但是優先順序更⾼的任務，可以搶佔低優先順序的任務，也就是優先順序⾼的可以「插隊」；
  • SCHED_RR：對於相同優先順序的任務，輪流著運⾏，每個任務都有⼀定的時間⽚，當⽤完時間⽚的任務會被放到隊列尾部，以保證相同優先順序任務的公平性，但是⾼優先順序的任務依然可以搶佔低優先順序的任務；

⽽ Fair 調度類是應⽤於普通任務，都是由 CFS 調度器管理的，分為兩種調度策略：

  • SCHED_NORMAL：普通任務使⽤的調度策略；
  • SCHED_BATCH：後台任務的調度策略，不和終端進⾏交互，因此在不影響其他需要交互的任務，可以適當降低它的優先順序。

完全公平調度

我們平⽇⾥遇到的基本都是普通任務，對於普通任務來說，公平性最重要，在 Linux ⾥⾯，實現了⼀個基於 CFS 的調度演算法，也就是完全公平調度（Completely Fair Scheduling）。

這個演算法的理念是想讓分配給每個任務的 CPU 時間是⼀樣，於是它為每個任務安排⼀個虛擬運⾏時間vruntime，

如果⼀個任務在運⾏，其運⾏的越久，該任務的 vruntime ⾃然就會越⼤，⽽沒有被運⾏的任務，vruntime 是不會變化的。

那麼，在 CFS 演算法調度的時候，會優先選擇 vruntime 少的任務，以保證每個任務的公平性。

虛擬運行時間 vruntime += 實際運行時間 delta_ exec * NICE_ 0_ LOAD / 權重

CPU 運⾏隊列

⼀個系統通常都會運⾏著很多任務，多任務的數量基本都是遠超 CPU 核⼼數量，因此這時候就需要排隊。

事實上，每個 CPU 都有⾃⼰的運⾏隊列（Run Queue, rq），⽤於描述在此 CPU 上所運⾏的所有進程，

其隊列包含三個運⾏隊列，Deadline 運⾏隊列 dl_rq、實時任務運⾏隊列 rt_rq 和 CFS 運⾏隊列 csf_rq，

其中 csf_rq 是⽤紅⿊樹來描述的，按 vruntime ⼤⼩來排序的，最左側的葉⼦節點，就是下次會被調度的任務。

這⼏種調度類是有優先順序的，優先順序如下：Deadline > Realtime > Fair。

因此，實時任務總是會⽐普通任務優先被執⾏。

調整優先順序

可以調整任務的 nice 值，從⽽讓優先順序⾼⼀些的任務執⾏

更多時間。nice 的值能設置的範圍是 -20～19 ， 值越低，表明優先順序越⾼，因此 -20 是最⾼優先順序，19則是最低優先順序，默認優先順序是 0。

軟中斷

Linux 系統為了解決中斷處理程式執⾏過⻓和中斷丟失的問題，將中斷過程分成了兩個階段，分別是「上半部和下半部分」。

  • 上半部⽤來快速處理中斷，⼀般會暫時關閉中斷請求，主要負責處理跟硬體緊密相關或者時間敏感的事情。
    • 上半部直接處理硬體請求，也就是硬中斷，主要是負責耗時短的⼯作，特點是快速執⾏；
  • 下半部⽤來延遲處理上半部未完成的⼯作，⼀般以「內核執行緒」的⽅式運⾏。
    • 下半部是由內核觸發，也就說軟中斷，主要是負責上半部未完成的⼯作，通常都是耗時⽐較⻓的事情，特點是延遲執⾏；

在 Linux 系統⾥，我們可以通過查看 /proc/softirqs 的 內容來知曉「軟中斷」的運⾏情況，以及/proc/interrupts 的 內容來知曉「硬中斷」的運⾏情況。

要想知道當前的系統的軟中斷情況，我們可以使⽤ top 命令查看。

一般對於⽹絡 I/O ⽐較⾼的 Web 伺服器， NET_RX ⽹絡接收中斷的變化速率相⽐其他中斷類型快很多。

如果發現 NET_RX ⽹絡接收中斷次數的變化速率過快，接下⾥就可以使⽤ sar -n DEV 查看⽹卡的⽹絡包接收速率情況，然後分析是哪個⽹卡有⼤量的⽹絡包進來。

接著，在通過 tcpdump 抓包，分析這些包的來源，如果是⾮法的地址，可以考慮加防⽕牆，如果是正常流量，則要考慮硬體升級等。

有意思的問題

為什麼 0.1 + 0.2 不等於 0.3 ？

不是的，0.1 和 0.2 這兩個數字⽤⼆進位表達會是⼀個⼀直循環的⼆進位數，

⽐如 0.1 的⼆進位表示為 0.00011 0011 0011… （0011 ⽆限循環)，對於電腦⽽⾔，0.1 ⽆法精確表達，這是浮點數計算造成精度損失的根源。

因此，IEEE 754 標準定義的浮點數只能根據精度舍⼊，然後⽤「近似值」來表示該⼆進位，那麼意味著電腦存放的⼩數可能不是⼀個真實值。

0.1 + 0.2 並不等於完整的 0.3，

這主要是因為這兩個⼩數⽆法⽤「完整」的⼆進位來表示，只能根據精度舍⼊，

所以電腦⾥只能采⽤近似數的⽅式來保存，那兩個近似數相加，得到的必然也是⼀個近似數。

二、作業系統結構

Linux 內核 vs Windows 內核

Windows 和 Linux 可以說是我們⽐較常⻅的兩款作業系統的。

Windows 基本佔領了電腦時代的市場，商業上取得了很⼤成就，但是它並不開源，所以要想接觸源碼得加⼊ Windows 的開發團隊中。

對於伺服器使⽤的作業系統基本上都是 Linux，⽽且內核源碼也是開源的，任何⼈都可以下載，並增加⾃⼰的改動或功能，Linux 最⼤的魅⼒在於，全世界有⾮常多的技術⼤佬為它貢獻程式碼。

這兩個作業系統各有千秋，不分伯仲。

內核

電腦是由各種外部硬體設備組成的，⽐如記憶體、cpu、硬碟等，如果每個應⽤都要和這些硬體設備對接通訊協議，

那這樣太累了，所以這個中間⼈就由內核來負責，

讓內核作為應⽤連接硬體設備的橋樑，應⽤程式只需關⼼與內核交互，不⽤關⼼硬體的細節。

內核有哪些能⼒呢？

現代作業系統，內核⼀般會提供 4 個基本能⼒：

  • 管理進程、執行緒，決定哪個進程、執行緒使⽤ CPU，也就是進程調度的能⼒；
  • 管理記憶體，決定記憶體的分配和回收，也就是記憶體管理的能⼒；
  • 管理硬體設備，為進程與硬體設備之間提供通訊能⼒，也就是硬體通訊能⼒；
  • 提供系統調⽤，如果應⽤程式要運⾏更⾼許可權運⾏的服務，那麼就需要有系統調⽤，它是⽤戶程式與作業系統之間的接⼝。

內核是怎麼⼯作的？

  • 內核具有很⾼的許可權，可以控制 cpu、記憶體、硬碟等硬體，⽽應⽤程式具有的許可權很⼩，因此⼤多數作業系統，把記憶體分成了兩個區域：
    • 內核空間，這個記憶體空間只有內核程式可以訪問；
    • ⽤戶空間，這個記憶體空間專⻔給應⽤程式使⽤；

Linux 的設計

Linux 的開⼭始祖是來⾃⼀位名叫 Linus Torvalds 的芬蘭⼩伙⼦，他在 1991 年⽤ C 語⾔寫出了第⼀版的Linux 作業系統，那年他 22 歲。

完成第⼀版 Linux 後，Linux Torvalds 就在⽹絡上發布了 Linux 內核的源程式碼，每個⼈都可以免費下載和使⽤。

Linux 內核設計的理念主要有這⼏個點：

  • MutiTask，多任務
  • SMP，對稱多處理
  • ELF，可執⾏⽂件鏈接格式
  • Monolithic Kernel，宏內核
與宏內核相反的是微內核，微內核架構的內核只保留最基本的能⼒，

⽐如進程調度、虛擬機記憶體、中斷等，把⼀些應⽤放到了⽤戶空間，⽐如驅動程式、⽂件系統等。

這樣服務與服務之間是隔離的，單個服務出現故障或者完全攻擊，也不會導致整個作業系統掛掉，提⾼了作業系統的穩定性和可靠性。

微內核內核功能少，可移植性⾼，
相⽐宏內核有⼀點不好的地⽅在於，由於驅動程式不在內核中，⽽且驅動程式⼀般會頻繁調⽤底層能⼒的，於是驅動和硬體設備交互就需要頻繁切換到內核態，這樣會帶來性能損耗。

華為的鴻蒙作業系統的內核架構就是微內核。

還有⼀種內核叫混合類型內核，它的架構有點像微內核，內核⾥⾯會有⼀個最⼩版本的內核，

然後其他模組會在這個基礎上搭建，然後實現的時候會跟宏內核類似，也就是把整個內核做成⼀個完整的程式，

⼤部分服務都在內核中，這就像是宏內核的⽅式包裹著⼀個微內核。

Windows 設計

當今 Windows 7、Windows 10 使⽤的內核叫 Windows NT，NT 全稱叫 New Technology。

下圖是 Windows NT 的結構圖⽚：

Windows 和 Linux ⼀樣，同樣⽀持 MutiTask 和 SMP，

但不同的是，Window 的內核設計是混合型內核，

在上圖你可以看到內核中有⼀個 MicroKernel 模組，這個就是最⼩版本的內核，⽽整個內核實現是⼀個完整的程式，含有⾮常多模組。

三、記憶體管理

作業系統會提供⼀種機制，將不同進程的虛擬地址和不同記憶體的物理地址映射起來。

如果程式要訪問虛擬地址的時候，由作業系統轉換成不同的物理地址，這樣不同的進程運⾏的時候，寫⼊的是不同的物理地址，這樣就不會衝突了。

於是，這⾥就引出了兩種地址的概念：

  • 我們程式所使⽤的記憶體地址叫做虛擬記憶體地址（Virtual Memory Address）、
  • 實際存在硬體⾥⾯的空間地址叫物理記憶體地址（Physical Memory Address）。

主要有兩種⽅式，分別是記憶體分段和記憶體分⻚

記憶體分段

程式是由若⼲個邏輯分段組成的，

如可由程式碼分段、數據分段、棧段、堆段組成。不同的段是有不同的屬性的，所以就⽤分段（Segmentation）的形式把這些段分離出來。

虛擬地址是通過段表與物理地址進⾏映射

分段的辦法很好，解決了程式本身不需要關⼼具體的物理記憶體地址的問題，但它也有⼀些不⾜之處：

  • 第⼀個就是記憶體碎⽚的問題。
  • 第⼆個就是記憶體交換的效率低的問題。
    • 如果記憶體交換的時候，交換的是⼀個占記憶體空間很⼤的程式，這樣整個機器都會顯得卡頓。

為了解決記憶體分段的記憶體碎⽚和記憶體交換效率低的問題，就出現了記憶體分⻚。

記憶體分⻚

分段的好處就是能產⽣連續的記憶體空間，但是會出現記憶體碎⽚和記憶體交換的空間太⼤的問題。

要解決這些問題，那麼就要想出能少出現⼀些記憶體碎⽚的辦法。

另外，當需要進⾏記憶體交換的時候，讓需要交換寫⼊或者從磁碟裝載的數據更少⼀點，這樣就可以解決問題了。這個辦法，也就是記憶體分⻚（Paging）。

分⻚是把整個虛擬和物理記憶體空間切成⼀段段固定尺⼨的⼤⼩。

這樣⼀個連續並且尺⼨固定的記憶體空間，我們叫⻚（Page）。在 Linux 下，每⼀⻚的⼤⼩為 4KB 。

⽽當進程訪問的虛擬地址在⻚表中查不到時，系統會產⽣⼀個缺⻚異常，

進⼊系統內核空間分配物理記憶體、更新進程⻚表，最後再返回⽤戶空間，恢復進程的運⾏。

分⻚是怎麼解決分段的記憶體碎⽚、記憶體交換效率低的問題？

由於記憶體空間都是預先劃分好的，也就不會像分段會產⽣間隙⾮常⼩的記憶體，

這正是分段會產⽣記憶體碎⽚的原因。

⽽采⽤了分⻚，那麼釋放的記憶體都是以⻚為單位釋放的，也就不會產⽣⽆法給進程使⽤的⼩記憶體。

如果記憶體空間不夠，作業系統會把其他正在運⾏的進程中的「最近沒被使⽤」的記憶體⻚⾯給釋放掉，

也就是暫時寫在硬碟上，稱為換出（Swap Out）。

⼀旦需要的時候，再載入進來，稱為換⼊（Swap In）。

所以，⼀次性寫⼊磁碟的也只有少數的⼀個⻚或者⼏個⻚，不會花太多時間，記憶體交換的效率就相對⽐較⾼。

更進⼀步地，分⻚的⽅式使得我們在載入程式的時候，不再需要⼀次性都把程式載入到物理記憶體中。

我們完全可以在進⾏虛擬記憶體和物理記憶體的⻚之間的映射之後，並不真的把⻚載入到物理記憶體⾥，

⽽是只有在程式運⾏中，需要⽤到對應虛擬記憶體⻚⾥⾯的指令和數據時，再載入到物理記憶體⾥⾯去。

分⻚機制下，虛擬地址和物理地址是如何映射的？

在分⻚機制下，虛擬地址分為兩部分，⻚號和⻚內偏移。⻚號作為⻚表的索引，

⻚表包含物理⻚每⻚所在物理記憶體的基地址，這個基地址與⻚內偏移的組合就形成了物理記憶體地址。

總結⼀下，對於⼀個記憶體地址轉換，其實就是這樣三個步驟：

  • 把虛擬記憶體地址，切分成⻚號和偏移量；
  • 根據⻚號，從⻚表⾥⾯，查詢對應的物理⻚號；
  • 直接拿物理⻚號，加上前⾯的偏移量，就得到了物理記憶體地址。

但是，就這樣簡單的分頁是會有不少問題的，所以啊，我們又引入了多級頁表的概念。

多級⻚表

對於 64 位的系統，兩級分⻚肯定不夠了，就變成了四級⽬錄，分別是：

  • 全局⻚⽬錄項 PGD（Page Global Directory）；
  • 上層⻚⽬錄項 PUD（Page Upper Directory）；
  • 中間⻚⽬錄項 PMD（Page Middle Directory）；
  • ⻚表項 PTE（Page Table Entry）；

TLB

多級⻚表雖然解決了空間上的問題，但是虛擬地址到物理地址的轉換就多了⼏道轉換的⼯序，

這顯然就降低了這倆地址轉換的速度，也就是帶來了時間上的開銷。

程式是有局部性的，即在⼀段時間內，整個程式的執⾏僅限於程式中的某⼀部分。

相應地，執⾏所訪問的存儲空間也局限於某個記憶體區域。

我們就可以利⽤這⼀特性，把最常訪問的⼏個⻚表項存儲到訪問速度更快的硬體，

於是電腦科學家們，就在 CPU 芯⽚中，加⼊了⼀個專⻔存放程式最常訪問的⻚表項的 Cache，

這個 Cache 就是 TLB（Translation Lookaside Buffer） ，通常稱為⻚錶快取、轉址旁路快取、快表等。

在 CPU 芯⽚⾥⾯，封裝了記憶體管理單元（Memory Management Unit）芯⽚，它⽤來完成地址轉換和 TLB的訪問與交互。

有了 TLB 後，那麼 CPU 在定址時，會先查 TLB，如果沒找到，才會繼續查常規的⻚表。

TLB 的命中率其實是很⾼的，因為程式最常訪問的⻚就那麼⼏個。

段⻚式記憶體管理

記憶體分段和記憶體分⻚並不是對⽴的，它們是可以組合起來在同⼀個系統中使⽤的，

那麼組合起來後，通常稱為段⻚式記憶體管理。

段⻚式地址變換中要得到物理地址須經過三次記憶體訪問：

  • 第⼀次訪問段表，得到⻚表起始地址；
  • 第⼆次訪問⻚表，得到物理⻚號；
  • 第三次將物理⻚號與⻚內位移組合，得到物理地址。

可⽤軟、硬體相結合的⽅法實現段⻚式地址變換，這樣雖然增加了硬體成本和系統開銷，但提⾼了記憶體的利⽤率。

Linux 記憶體管理

Intel 處理器的發展歷史

早期 Intel 的處理器從 80286 開始使⽤的是段式記憶體管理。

但是很快發現，光有段式記憶體管理⽽沒有⻚式記憶體管理是不夠的，這會使它的 X86 系列會失去市場的競爭⼒。

因此，在不久以後的 80386 中就實現了對⻚式記憶體管理。

也就是說，80386 除了完成並完善從 80286 開始的段式記憶體管理的同時還實現了⻚式記憶體管理。

但是這個 80386 的⻚式記憶體管理設計時，沒有繞開段式記憶體管理，⽽是建⽴在段式記憶體管理的基礎上，

這就意味著，⻚式記憶體管理的作⽤是在由段式記憶體管理所映射⽽成的地址上再加上⼀層地址映射。

由於此時由段式記憶體管理映射⽽成的地址不再是「物理地址」了，

Intel 就稱之為「線性地址」（也稱虛擬地址）。

於是，段式記憶體管理先將邏輯地址映射成線性地址，然後再由⻚式記憶體管理將線性地址映射成物理地址。

這⾥說明下邏輯地址和線性地址：

  • 程式所使⽤的地址，通常是沒被段式記憶體管理映射的地址，稱為邏輯地址；
  • 通過段式記憶體管理映射的地址，稱為線性地址，也叫虛擬地址；

邏輯地址是「段式記憶體管理」轉換前的地址，線性地址則是「⻚式記憶體管理」轉換前的地址。

Linux 記憶體

Linux 記憶體主要采⽤的是⻚式記憶體管理，但同時也不可避免地涉及了段機制。

這主要是上⾯ Intel 處理器發展歷史導致的，因為 Intel X86 CPU ⼀律對程式中使⽤的地址先進⾏段式映射，

然後才能進⾏⻚式映射。

既然 CPU 的硬體結構是這樣，Linux 內核也只好服從 Intel 的選擇。

但是事實上，Linux 內核所採取的辦法是使段式映射的過程實際上不起什麼作⽤。

也就是說，「上有政策，下有對策」，若惹不起就躲著⾛。

Linux 系統中的每個段都是從 0 地址開始的整個 4GB 虛擬空間（32 位環境下），

也就是所有的段的起始地址都是⼀樣的。

這意味著，Linux 系統中的程式碼，包括作業系統本身的程式碼和應⽤程式程式碼，

所⾯對的地址空間都是線性地址空間（虛擬地址），這種做法相當於屏蔽了處理器中的邏輯地址概念，段只被⽤於
訪問控制和記憶體保護。

Linux 作業系統中，虛擬地址空間的內部⼜被分為內核空間和⽤戶空間兩部分，

不同位數的系統，地址空間的範圍也不同。

⽐如最常⻅的 32 位和 64 位系統，如下所示：

雖然每個進程都各⾃有獨⽴的虛擬記憶體，但是每個虛擬記憶體中的內核地址，其實關聯的都是相同的物理記憶體。

這樣，進程切換到內核態後，就可以很⽅便地訪問內核空間記憶體。


通過這張圖你可以看到，⽤戶空間記憶體，從低到⾼分別是 7 種不同的記憶體段：

  • 程式⽂件段，包括⼆進位可執⾏程式碼；

  • 已初始化數據段，包括靜態常量；

  • 未初始化數據段，包括未初始化的靜態變數；

  • 堆段，包括動態分配的記憶體，從低地址開始向上增⻓；

  • ⽂件映射段，包括動態庫、共享記憶體等，從低地址開始向上增⻓（跟硬體和內核版本有關）；

  • 棧段，包括局部變數和函數調⽤的上下⽂等。棧的⼤⼩是固定的，⼀般是 8 MB 。

    當然系統也提供了參數，以便我們⾃定義⼤⼩；

在這 7 個記憶體段中，堆和⽂件映射段的記憶體是動態分配的。

⽐如說，使⽤ C 標準庫的 malloc() 或者mmap() ，就可以分別在堆和⽂件映射段動態分配記憶體。

進程與執行緒

進程

我們編寫的程式碼只是⼀個存儲在硬碟的靜態⽂件，通過編譯後就會⽣成⼆進位可執⾏⽂件，

當我們運⾏這個可執⾏⽂件後，它會被裝載到記憶體中，接著 CPU 會執⾏程式中的每⼀條指令，

那麼這個運⾏中的程式，就被稱為「進程」（Process）。

但是呢，你想，硬碟讀取東西的速度太慢了，

所以，當進程要從硬碟讀取數據時，CPU 不需要阻塞等待數據的返回，⽽是去執⾏另外的進程。

當硬碟數據返回時，CPU 會收到個中斷，於是 CPU 再繼續運⾏這個進程。

這種多個程式、交替執⾏的思想，雖然單核的 CPU 在某⼀個瞬間，只能運⾏⼀個進程。但在 1 秒鐘期間，

它可能會運⾏多個進程，這樣就產⽣並⾏的錯覺，實際上這是並發。


進程的狀態

如果有⼤量處於阻塞狀態的進程，進程可能會佔⽤著物理記憶體空間，物理記憶體空間是有限的，被阻塞狀態的進程占⽤著物理記憶體就⼀種浪費物理記憶體的⾏為。

所以，在虛擬記憶體管理的作業系統中，通常會把阻塞狀態的進程的物理記憶體空間換出到硬碟，等需要再次運⾏的時候，再從硬碟換⼊到物理記憶體。

那麼，就需要⼀個新的狀態，來描述進程沒有占⽤實際的物理記憶體空間的情況，這個狀態就是掛起狀態。

這跟阻塞狀態是不⼀樣，阻塞狀態是等待某個事件的返回。

另外，掛起狀態可以分為兩種：

  • 阻塞掛起狀態：進程在外存（硬碟）並等待某個事件的出現；
  • 就緒掛起狀態：進程在外存（硬碟），但只要進⼊記憶體，即刻⽴刻運⾏；

導致進程掛起的原因不只是因為進程所使⽤的記憶體空間不在物理記憶體，還包括如下情況：

  • 通過 sleep 讓進程間歇性掛起，其⼯作原理是設置⼀個定時器，到期後喚醒進程。
  • ⽤戶希望掛起⼀個程式的執⾏，⽐如在 Linux 中⽤ Ctrl+Z 掛起進程；

進程的控制結構

在作業系統中，是⽤進程式控制制塊（process control block，PCB）數據結構來描述進程的。

PCB 是進程存在的唯⼀標識，這意味著⼀個進程的存在，必然會有⼀個 PCB，如果進程消失了，那麼PCB 也會隨之消失。

PCB 具體包含什麼資訊呢？

進程描述資訊：

  • 進程標識符：標識各個進程，每個進程都有⼀個並且唯⼀的標識符；
  • ⽤戶標識符：進程歸屬的⽤戶，⽤戶標識符主要為共享和保護服務；

進程式控制制和管理資訊：

  • 進程當前狀態，如 new、ready、running、waiting 或 blocked 等；
  • 進程優先順序：進程搶佔 CPU 時的優先順序；

資源分配清單：

  • 有關記憶體地址空間或虛擬地址空間的資訊，所打開⽂件的列表和所使⽤的 I/O 設備資訊。

CPU 相關資訊：

  • CPU 中各個暫存器的值，當進程被切換時，CPU 的狀態資訊都會被保存在相應的 PCB 中，以便進程重新執⾏時，能從斷點處繼續執⾏。

通常是通過鏈表的⽅式進⾏組織，把具有相同狀態的進程鏈在⼀起，組成各種隊列。⽐如：

  • 將所有處於就緒狀態的進程鏈在⼀起，稱為就緒隊列；
  • 把所有因等待某事件⽽處於等待狀態的進程鏈在⼀起就組成各種阻塞隊列；
  • 另外，對於運⾏隊列在單核 CPU 系統中則只有⼀個運⾏指針了，因為單核 CPU 在某個時間，只能運
    ⾏⼀個程式。

進程的控制

我們熟知了進程的狀態變遷和進程的數據結構 PCB 後，再來看看進程的創建、終⽌、阻塞、喚醒的過程。

01 創建進程

作業系統允許⼀個進程創建另⼀個進程，⽽且允許⼦進程繼承⽗進程所擁有的資源，當⼦進程被終⽌時，

其在⽗進程處繼承的資源應當還給⽗進程。同時，終⽌⽗進程時同時也會終⽌其所有的⼦進程。

注意：Linux 作業系統對於終⽌有⼦進程的⽗進程，會把⼦進程交給 1 號進程接管。

這裡所指出的進程終⽌概念是宏觀作業系統的⼀種觀點，最後怎麼實現當然是看具體的作業系統。

創建進程的過程如下：

  • 為新進程分配⼀個唯⼀的進程標識號，並申請⼀個空⽩的 PCB，PCB 是有限的，若申請失敗則創建
    失敗；
  • 為進程分配資源，此處如果資源不⾜，進程就會進⼊等待狀態，以等待資源；
  • 初始化 PCB；
  • 如果進程的調度隊列能夠接納新進程，那就將進程插⼊到就緒隊列，等待被調度運⾏；

02 終⽌進程

進程可以有 3 種終⽌⽅式：正常結束、異常結束以及外界⼲預（訊號 kill 掉）。

終⽌進程的過程如下：

  • 查找需要終⽌的進程的 PCB；
  • 如果處於執⾏狀態，則⽴即終⽌該進程的執⾏，然後將 CPU 資源分配給其他進程；
  • 如果其還有⼦進程，則應將其所有⼦進程終⽌；
  • 將該進程所擁有的全部資源都歸還給⽗進程或作業系統；
  • 將其從 PCB 所在隊列中刪除；

03 阻塞進程

當進程需要等待某⼀事件完成時，它可以調⽤阻塞語句把⾃⼰阻塞等待。⽽⼀旦被阻塞等待，它只能由另
⼀個進程喚醒。

阻塞進程的過程如下：

  • 找到將要被阻塞進程標識號對應的 PCB；
  • 如果該進程為運⾏狀態，則保護其現場，將其狀態轉為阻塞狀態，停⽌運⾏；
  • 將該 PCB 插⼊到阻塞隊列中去；

04 喚醒進程

進程由「運⾏」轉變為「阻塞」狀態是由於進程必須等待某⼀事件的完成，

所以處於阻塞狀態的進程是絕對不可能叫醒⾃⼰的。

如果某進程正在等待 I/O 事件，需由別的進程發消息給它，則只有當該進程所期待的事件出現時，

才由發現者進程⽤喚醒語句叫醒它。

喚醒進程的過程如下：

  • 在該事件的阻塞隊列中找到相應進程的 PCB；
  • 將其從阻塞隊列中移出，並置其狀態為就緒狀態；
  • 把該 PCB 插⼊到就緒隊列中，等待調度程式調度；

進程的阻塞和喚醒是⼀對功能相反的語句，如果某個進程調⽤了阻塞語句，則必有⼀個與之對應的喚醒語句。

進程的上下⽂切換

各個進程之間是共享 CPU 資源的，在不同的時候進程之間需要切換，

讓不同的進程可以在 CPU 執⾏，那麼這個⼀個進程切換到另⼀個進程運⾏，稱為進程的上下⽂切換。

可以根據進程、執行緒和中斷的不同，

把 CPU 上下⽂切換分成：進程上下⽂切換、執行緒上下⽂切換和中斷上下⽂切換。

進程的上下⽂切換到底是切換什麼呢？

進程的上下⽂切換不僅包含了虛擬記憶體、棧、全局變數等⽤戶空間的資源，還包括了內核堆棧、暫存器等內核空間的資源。

通常，會把交換的資訊保存在進程的 PCB，當要運⾏另外⼀個進程的時候，我們需要從這個進程的 PCB取出上下⽂，然後恢復到 CPU 中，這使得這個進程可以繼續執⾏。

什麼時候會發生上下文的切換？

為了保證所有進程可以得到公平調度，CPU 時間被劃分為⼀段段的時間⽚，
這些時間⽚再被輪流分配給各個進程。
這樣，當某個進程的時間⽚耗盡了，進程就從運⾏狀態變為就緒狀態，系統從就緒隊列選擇另外⼀個進程運⾏；

進程在系統資源不⾜（⽐如記憶體不⾜）時，要等到資源滿⾜後才可以運⾏，
這個時候進程也會被掛起，並由系統調度其他進程運⾏；

當進程通過睡眠函數 sleep 這樣的⽅法將⾃⼰主動掛起時，⾃然也會重新調度；

當有優先順序更⾼的進程運⾏時，為了保證⾼優先順序進程的運⾏，當前進程會被掛起，由⾼優先順序進程來運⾏；

發⽣硬體中斷時，CPU 上的進程會被中斷掛起，轉⽽執⾏內核中的中斷服務程式

執行緒

在早期的作業系統中都是以進程作為獨⽴運⾏的基本單位，直到後⾯，電腦科學家們⼜提出了更⼩的能獨⽴運⾏的基本單位，也就是執行緒。

問題-》解決-》由來

什麼是執行緒？

執行緒是進程當中的⼀條執⾏流程。

同⼀個進程內多個執行緒之間可以共享程式碼段、數據段、打開的⽂件等資源，

但每個執行緒各⾃都有⼀套獨⽴的暫存器和棧，這樣可以確保執行緒的控制流是相對獨⽴的。

執行緒的優缺點？

執行緒的優點：

  • ⼀個進程中可以同時存在多個執行緒；
  • 各個執行緒之間可以並發執⾏；
  • 各個執行緒之間可以共享地址空間和⽂件等資源；

執行緒的缺點：

  • 當進程中的⼀個執行緒崩潰時，會導致其所屬進程的所有執行緒崩潰。

執行緒與進程的⽐較

執行緒與進程的⽐較如下：

  • 進程是資源（包括記憶體、打開的⽂件等）分配的單位，執行緒是 CPU 調度的單位；
  • 進程擁有⼀個完整的資源平台，⽽執行緒只獨享必不可少的資源，如暫存器和棧；
  • 執行緒同樣具有就緒、阻塞、執⾏三種基本狀態，同樣具有狀態之間的轉換關係；
  • 執行緒能減少並發執⾏的時間和空間開銷；

對於，執行緒相⽐進程能減少開銷，體現在：

  • 執行緒的創建時間⽐進程快，

    因為進程在創建的過程中，還需要資源管理資訊，⽐如記憶體管理資訊、⽂件管理資訊，

    ⽽執行緒在創建的過程中，不會涉及這些資源管理資訊，⽽是共享它們；

  • 執行緒的終⽌時間⽐進程快，因為執行緒釋放的資源相⽐進程少很多；

  • 同⼀個進程內的執行緒切換⽐進程切換快，因為執行緒具有相同的地址空間（虛擬記憶體共享），

    這意味著同⼀個進程的執行緒都具有同⼀個⻚表，那麼在切換的時候不需要切換⻚表。

    ⽽對於進程之間的切換，切換的時候要把⻚表給切換掉，⽽⻚表的切換過程開銷是⽐較⼤的；

  • 由於同⼀進程的各執行緒間共享記憶體和⽂件資源，那麼在執行緒之間數據傳遞的時候就不需要經過內核了，

    這就使得執行緒之間的數據交互效率更⾼了；所以，不管是時間效率，還是空間效率執行緒⽐進程都要⾼。

執行緒的上下⽂切換

在前⾯我們知道了，執行緒與進程最⼤的區別在於：

執行緒是調度的基本單位，⽽進程則是資源擁有的基本單位。

所以，所謂作業系統的任務調度，實際上的調度對象是執行緒，

⽽進程只是給執行緒提供了虛擬記憶體、全局變數等資源。

對於執行緒和進程，我們可以這麼理解：

  • 當進程只有⼀個執行緒時，可以認為進程就等於執行緒

  • 當進程擁有多個執行緒時，這些執行緒會共享相同的虛擬記憶體和全局變數等資源，

    這些資源在上下⽂切換時是不需要修改的；

執行緒上下⽂切換的是什麼？

這還得看執行緒是不是屬於同⼀個進程：

  • 當兩個執行緒不是屬於同⼀個進程，則切換的過程就跟進程上下⽂切換⼀樣；

  • 當兩個執行緒是屬於同⼀個進程，因為虛擬記憶體是共享的，

    所以在切換時，虛擬記憶體這些資源就保持不動，只需要切換執行緒的私有數據、暫存器等不共享的數據；

所以，執行緒的上下⽂切換相⽐進程，開銷要⼩很多。

執行緒的實現

主要有三種執行緒的實現⽅式：

  • ⽤戶執行緒（User Thread）：在⽤戶空間實現的執行緒，不是由內核管理的執行緒，是由⽤戶態的執行緒庫
    來完成執行緒的管理；
  • 內核執行緒（Kernel Thread）：在內核中實現的執行緒，是由內核管理的執行緒；
  • 輕量級進程（LightWeight Process）：在內核中來⽀持⽤戶執行緒；

⽤戶執行緒如何理解？存在什麼優勢和缺陷？

⽤戶執行緒是基於⽤戶態的執行緒管理庫來實現的，

那麼執行緒控制塊（Thread Control Block, TCB） 也是在庫⾥⾯來實現的，對於作業系統⽽⾔是看不到這個 TCB 的，它只能看到整個進程的 PCB。

所以，⽤戶執行緒的整個執行緒管理和調度，作業系統是不直接參与的，

⽽是由⽤戶級執行緒庫函數來完成執行緒的管理，包括執行緒的創建、終⽌、同步和調度等。

⽤戶執行緒的優點：

每個進程都需要有它私有的執行緒控制塊（TCB）列表，
⽤來跟蹤記錄它各個執行緒狀態資訊（PC、棧指針、暫存器），
TCB 由⽤戶級執行緒庫函數來維護，可⽤於不⽀持執行緒技術的作業系統；

⽤戶執行緒的切換也是由執行緒庫函數來完成的，⽆需⽤戶態與內核態的切換，所以速度特別快；

⽤戶執行緒的缺點：

由於作業系統不參與執行緒的調度，如果⼀個執行緒發起了系統調⽤⽽阻塞，
那進程所包含的⽤戶執行緒都不能執⾏了。

當⼀個執行緒開始運⾏後，除⾮它主動地交出 CPU 的使⽤權，
否則它所在的進程當中的其他執行緒⽆法運⾏，因為⽤戶態的執行緒沒法打斷當前運⾏中的執行緒，
但是⽤戶執行緒不是由作業系統管理的。

由於時間⽚分配給進程，故與其他進程⽐，在多執行緒執⾏時，每個執行緒得到的時間⽚較少，執⾏會⽐
較慢；

那內核執行緒如何理解？存在什麼優勢和缺陷？

內核執行緒是由作業系統管理的，執行緒對應的 TCB ⾃然是放在作業系統⾥的，

這樣執行緒的創建、終⽌和管理都是由作業系統負責。

內核執行緒的優點：

在⼀個進程當中，如果某個內核執行緒發起系統調⽤⽽被阻塞，並不會影響其他內核執行緒的運⾏；

分配給執行緒，多執行緒的進程獲得更多的 CPU 運⾏時間；


內核執行緒的缺點：

在⽀持內核執行緒的作業系統中，由內核來維護進程和執行緒的上下⽂資訊，如 PCB 和 TCB；

執行緒的創建、終⽌和切換都是通過系統調⽤的⽅式來進⾏，因此對於系統來說，系統開銷⽐較⼤；

輕量級進程如何理解？

輕量級進程（Light-weight process，LWP）是內核⽀持的⽤戶執行緒，⼀個進程可有⼀個或多個 LWP，

每個 LWP 是跟內核執行緒⼀對⼀映射的，也就是 LWP 都是由⼀個內核執行緒⽀持。

另外，LWP 只能由內核管理並像普通進程⼀樣被調度，Linux 內核是⽀持 LWP 的典型例⼦。

在⼤多數系統中，LWP與普通進程的區別也在於它只有⼀個最⼩的執⾏上下⽂和調度程式所需的統計資訊。

⼀般來說，⼀個進程代表程式的⼀個實例，⽽ LWP 代表程式的執⾏執行緒，

因為⼀個執⾏執行緒不像進程那樣需要那麼多狀態資訊，所以 LWP 也不帶有這樣的資訊。

在 LWP 之上也是可以使⽤⽤戶執行緒的，那麼 LWP 與⽤戶執行緒的對應關係就有三種：

  • 1 : 1 ，即⼀個 LWP 對應 ⼀個⽤戶執行緒；
  • N : 1 ，即⼀個 LWP 對應多個⽤戶執行緒；
  • M : N ，即多個 LMP 對應多個⽤戶執行緒；

調度

進程都希望⾃⼰能夠占⽤ CPU 進⾏⼯作，那麼這涉及到前⾯說過的進程上下⽂切換。

⼀旦作業系統把進程切換到運⾏狀態，也就意味著該進程占⽤著 CPU 在執⾏，

但是當作業系統把進程切換到其他狀態時，那就不能在 CPU 中執⾏了，於是作業系統會選擇下⼀個要運⾏的程。

選擇⼀個進程運⾏這⼀功能是在作業系統中完成的，通常稱為調度程式（scheduler）。

調度演算法

  • 先來先服務調度演算法，聽名字就明白了。
  • 最短作業優先調度演算法，同。
  • ⾼響應⽐優先調度演算法，看吧，看懂中文意思就明白了。
  • 時間⽚輪轉調度演算法
  • 最⾼優先順序調度演算法
  • 多級回饋隊列調度演算法，多級回饋隊列（Multilevel Feedback Queue）調度演算法是「時間⽚輪轉演算法」和「最⾼優先順序演算法」的綜合和發展。

進程與通訊

每個進程的⽤戶地址空間都是獨⽴的，⼀般⽽⾔是不能互相訪問的，但內核空間是每個進程都共享的，所以進程之間要通訊必須通過內核。

管道

管道傳輸數據是單向的，如果想相互通訊，我們需要創建兩個管道才⾏。

管道還有另外⼀個類型是命名管道，也被叫做 FIFO ，因為數據是先進先出的傳輸⽅式。

但是呢，管道這種通訊⽅式效率低，不適合進程間頻繁地交換數據。

當然，它的好處，⾃然就是簡單，同時也我們很容易得知管道⾥的數據已經被另⼀個進程讀取了。

所謂的管道，就是內核⾥⾯的⼀串快取。

從管道的⼀段寫⼊的數據，實際上是快取在內核中的，另⼀端讀取，也就是從內核中讀取這段數據。

另外，管道傳輸的數據是⽆格式的流且⼤⼩受限。

我們可以得知，對於匿名管道，它的通訊範圍是存在⽗⼦關係的進程。

因為管道沒有實體，也就是沒有管道⽂件，只能通過 fork 來複制⽗進程 fd ⽂件描述符，來達到通訊的⽬的。

另外，對於命名管道，它可以在不相關的進程間也能相互通訊。

因為命令管道，提前創建了⼀個類型為管道的設備⽂件，在進程⾥只要使⽤這個設備⽂件，就可以相互通訊。

不管是匿名管道還是命名管道，進程寫⼊的數據都是快取在內核中，

另⼀個進程讀取數據時候⾃然也是從內核中獲取，同時通訊數據都遵循先進先出原則，不⽀持 lseek 之類的⽂件定位操作。

消息隊列

消息隊列是保存在內核中的消息鏈表，

在發送數據時，會分成⼀個⼀個獨⽴的數據單元，也就是消息體（數據塊），消息體是⽤戶⾃定義的數據類型，

消息的發送⽅和接收⽅要約定好消息體的數據類型。

所以每個消息體都是固定⼤⼩的存儲塊，不像管道是⽆格式的位元組流數據。

如果進程從消息隊列中讀取了消息體，內核就會把這個消息體刪除。

消息隊列⽣命周期隨內核，如果沒有釋放消息隊列或者沒有關閉作業系統，消息隊列會⼀直存在，

⽽前⾯提到的匿名管道的⽣命周期，是隨進程的創建⽽建⽴，隨進程的結束⽽銷毀。

消息隊列不適合⽐較⼤數據的傳輸，消息隊列通訊過程中，存在⽤戶態與內核態之間的數據拷⻉開銷

共享記憶體

共享記憶體的機制，就是拿出⼀塊虛擬地址空間來，映射到相同的物理記憶體中。

訊號量

訊號量其實是⼀個整型的計數器，主要⽤於實現進程間的互斥與同步，⽽不是⽤於快取進程間通訊的數據。

PV操作。

訊號

於異常情況下的⼯作模式，就需要⽤「訊號」的⽅式來通知進程。

Socket

跨⽹絡與不同主機上的進程之間通訊，就需要 Socket 通訊了。

int socket(int domain, int type, int protocal)

三個參數分別代表：

  • domain 參數⽤來指定協議族，⽐如 AF_INET ⽤於 IPV4、AF_INET6 ⽤於 IPV6、AF_LOCAL/AF_UNIX ⽤於本機；

  • type 參數⽤來指定通訊特性，⽐如 SOCK_STREAM 表示的是位元組流，

    對應 TCP、SOCK_DGRAM表示的是數據報，對應 UDP、SOCK_RAW 表示的是原始套接字；

  • protocal 參數原本是⽤來指定通訊協議的，但現在基本廢棄。因為協議已經通過前⾯兩個參數指定完
    成，protocol ⽬前⼀般寫成 0 即可；

根據創建 socket 類型的不同，通訊的⽅式也就不同：

  • 實現 TCP 位元組流通訊： socket 類型是 AF_INET 和 SOCK_STREAM；

  • 實現 UDP 數據報通訊：socket 類型是 AF_INET 和 SOCK_DGRAM；

  • 實現本地進程間通訊： 「本地位元組流 socket 」類型是 AF_LOCAL 和 SOCK_STREAM，

    「本地數據報 socket 」類型是 AF_LOCAL 和 SOCK_DGRAM。

    另外，AF_UNIX 和 AF_LOCAL 是等價的，所以AF_UNIX 也屬於本地 socket；

針對 TCP 協議通訊的 socket 編程模型

針對 UDP 協議通訊的 socket 編程模型

多執行緒同步

互斥（mutualexclusion）的，也就說保證⼀個執行緒在臨界區執⾏時，其他執行緒應該被阻⽌進⼊臨界區，說⽩了，就是這段程式碼執⾏過程中，最多只能出現⼀個執行緒。

同步與互斥是兩種不同的概念：

  • 同步就好⽐：「操作 A 應在操作 B 之前執⾏」，「操作 C 必須在操作 A 和操作 B 都完成之後才能執⾏」等；
  • 互斥就好⽐：「操作 A 和操作 B 不能在同⼀時刻執⾏」；

互斥與同步的實現和使⽤

為了實現進程/執行緒間正確的協作，作業系統必須提供實現進程協作的措施和⽅法，主要的⽅法有兩種：

  • 鎖：加鎖、解鎖操作；
  • 訊號量：P、V 操作；

鎖

想詳細了解Java裡面鎖的實現可以看這幾個文章：

從synchronize到CSA和AQS _

執行緒同步-鎖

鎖

任何想進⼊臨界區的執行緒，必須先執⾏加鎖操作。

若加鎖操作順利通過，則執行緒可進⼊臨界區；

在完成對臨界資源的訪問後再執⾏解鎖操作，以釋放該臨界資源。

根據鎖的實現不同，可以分為「忙等待鎖」和「⽆忙等待鎖」。

「忙等待鎖」

⾃旋鎖（spin lock）

⼀直⾃旋，利⽤ CPU 周期，直到鎖可⽤。

在單處理器上，需要搶佔式的調度器（即不斷通過時鐘中斷⼀個執行緒，運⾏其他執行緒）。

否則，⾃旋鎖在單 CPU 上⽆法使⽤，因為⼀個⾃旋的執行緒，永遠不會放棄 CPU。

「⽆忙等待鎖」

⽆等待鎖顧明思議就是獲取不到鎖的時候，不⽤⾃旋。

既然不想⾃旋，那當沒獲取到鎖的時候，就把當前執行緒放⼊到鎖的等待隊列，然後執⾏調度程式，把 CPU讓給其他執行緒執⾏。

訊號量

訊號量實現臨界區的互斥訪問。

⽣產者-消費者問題

⽣產者-消費者問題描述：

  • ⽣產者在⽣成數據後，放在⼀個緩衝區中；
  • 消費者從緩衝區取出數據處理；
  • 任何時刻，只能有⼀個⽣產者或消費者可以訪問緩衝區；

我們對問題分析可以得出：

  • 任何時刻只能有⼀個執行緒操作緩衝區，說明操作緩衝區是臨界程式碼，需要互斥；

  • 緩衝區空時，消費者必須等待⽣產者⽣成數據；緩衝區滿時，⽣產者必須等待消費者取出數據。

    說明⽣產者和消費者需要同步。

那麼我們需要三個訊號量，分別是：

  • 互斥訊號量 mutex ：⽤於互斥訪問緩衝區，初始化值為 1；
  • 資源訊號量 fullBuffers ：⽤於消費者詢問緩衝區是否有數據，有數據則讀取數據，初始化值為 0
    （表明緩衝區⼀開始為空）；
  • 資源訊號量 emptyBuffers ：⽤於⽣產者詢問緩衝區是否有空位，有空位則⽣成數據，初始化值為 n
    （緩衝區⼤⼩）；

經典同步問題

哲學家就餐問題

「哲學家進餐問題」對於互斥訪問有限的競爭問題（如 I/O 設備）⼀類的建模過程⼗分有⽤。

先來看看哲學家就餐的問題描述：
5 個⽼⼤哥哲學家，閑著沒事做，圍繞著⼀張圓桌吃⾯；
巧就巧在，這個桌⼦只有 5 ⽀叉⼦，每兩個哲學家之間放⼀⽀叉⼦；
哲學家圍在⼀起先思考，思考中途餓了就會想進餐；
奇葩的是，這些哲學家要兩⽀叉⼦才願意吃⾯，也就是需要拿到左右兩邊的叉⼦才進餐；
吃完後，會把兩⽀叉⼦放回原處，繼續思考；

⽅案⼀

不過，這種解法存在⼀個極端的問題：

假設五位哲學家同時拿起左邊的叉⼦，桌⾯上就沒有叉⼦了，這樣就沒有⼈能夠拿到他們右邊的叉⼦，

也就說每⼀位哲學家都會在 P(fork[(i + 1) % N ]) 這條語句阻塞了，很明顯這發⽣了死鎖的現象。

⽅案二

只要有⼀個哲學家進⼊了「臨界區」，也就是準備要拿叉⼦時，其他哲學家都不能動，只有這位哲學家⽤完叉⼦了，才能輪到下⼀個哲學家進餐。

⽅案⼆雖然能讓哲學家們按順序吃飯，但是每次進餐只能有⼀位哲學家，

⽽桌⾯上是有 5 把叉⼦，按道理能可以有兩個哲學家同時進餐的，所以從效率⻆度上，這不是最好的解決⽅案。

⽅案三

即讓偶數編號的哲學家「先拿左邊的叉⼦後拿右邊的叉⼦」，奇數編號的哲學家「先拿右邊的叉⼦後拿左邊的叉⼦」。

⽅案四

⽤⼀個數組 state 來記錄每⼀位哲學家在進程、思考還是飢餓狀態（正在試圖拿叉⼦）。

那麼，⼀個哲學家只有在兩個鄰居都沒有進餐時，才可以進⼊進餐狀態。

⽅案四同樣不會出現死鎖，也可以兩⼈同時進餐。

讀者-寫者問題

它為資料庫訪問建⽴了⼀個模型。

讀者-寫者的問題描述：

  • 「讀-讀」允許：同⼀時刻，允許多個讀者同時讀
  • 「讀-寫」互斥：沒有寫者時讀者才能讀，沒有讀者時寫者才能寫
  • 「寫-寫」互斥：沒有其他寫者時，寫者才能寫

⽅案⼀

讀者優先的策略，因為只要有讀者正在讀的狀態，後來的讀者都可以直接進⼊，

如果讀者持續不斷進⼊，則寫者會處於飢餓狀態。

⽅案⼆

那既然有讀者優先策略，⾃然也有寫者優先策略：

  • 只要有寫者準備要寫⼊，寫者應儘快執⾏寫操作，後來的讀者就必須阻塞；
  • 如果有寫者持續不斷寫⼊，則讀者就處於飢餓；

⽅案三

既然讀者優先策略和寫者優先策略都會造成飢餓的現象，那麼我們就來實現⼀下公平策略。

公平策略：

  • 優先順序相同；
  • 寫者、讀者互斥訪問；
  • 只能⼀個寫者訪問臨界區；
  • 可以有多個讀者同時訪問臨街資源；

死鎖

死鎖只有同時滿⾜以下四個條件才會發⽣：

  • 互斥條件；
  • 持有並等待條件；
  • 不可剝奪條件；
  • 環路等待條件；

互斥鎖與⾃旋鎖

最底層的兩種就是會「互斥鎖和⾃旋鎖」，有很多⾼級的鎖都是基於它們實現的，你可以認為它們是各種鎖的地基，所以我們必須清楚它倆之間的區別和應⽤。

加鎖的⽬的就是保證共享資源在任意時間⾥，只有⼀個執行緒訪問，這樣就可以避免多執行緒導致共享數據錯亂的問題。

當已經有⼀個執行緒加鎖後，其他執行緒加鎖則就會失敗，互斥鎖和⾃旋鎖對於加鎖失敗後的處理⽅式是不⼀樣的：

  • 互斥鎖加鎖失敗後，執行緒會釋放 CPU ，給其他執行緒；
  • ⾃旋鎖加鎖失敗後，執行緒會忙等待，直到它拿到鎖；

互斥鎖

互斥鎖是⼀種「獨佔鎖」，對於互斥鎖加鎖失敗⽽阻塞的現象，是由作業系統內核實現的。

當加鎖失敗時，內核會將執行緒置為「睡眠」狀態，等到鎖被釋放後，內核會在合適的時機喚醒執行緒，

當這個執行緒成功獲取到鎖後，於是就可以繼續執⾏。

所以，互斥鎖加鎖失敗時，會從⽤戶態陷⼊到內核態，讓內核幫我們切換執行緒，

雖然簡化了使⽤鎖的難度，但是存在⼀定的性能開銷成本。

那這個開銷成本是什麼呢？會有兩次執行緒上下⽂切換的成本：

  • 當執行緒加鎖失敗時，內核會把執行緒的狀態從「運⾏」狀態設置為「睡眠」狀態，然後把 CPU 切換給其他執行緒運⾏；
  • 接著，當鎖被釋放時，之前「睡眠」狀態的執行緒會變為「就緒」狀態，然後內核會在合適的時間，把CPU 切換給該執行緒運⾏。

執行緒的上下⽂切換的是什麼？

當兩個執行緒是屬於同⼀個進程，因為虛擬記憶體是共享的，所以在切換時，虛擬記憶體這些資源就保持不動，

只需要切換執行緒的私有數據、暫存器等不共享的數據。

上下切換的耗時有⼤佬統計過，⼤概在⼏⼗納秒到⼏微秒之間，如果你鎖住的程式碼執⾏時間⽐較短，

那可能上下⽂切換的時間都⽐你鎖住的程式碼執⾏時間還要⻓。

所以，如果你能確定被鎖住的程式碼執⾏時間很短，就不應該⽤互斥鎖，⽽應該選⽤⾃旋鎖，否則使⽤互斥鎖。

⾃旋鎖

CPU 提供的 CAS 函數（Compare And Swap），在「⽤戶態」完成加鎖和解鎖操作，不會主動產⽣執行緒上下⽂切換，所以相⽐互斥鎖來說，會快⼀些，開銷也⼩⼀些。

⼀般加鎖的過程，包含兩個步驟：

  • 第⼀步，查看鎖的狀態，如果鎖是空閑的，則執⾏第⼆步；
  • 第⼆步，將鎖設置為當前執行緒持有；

CAS 函數就把這兩個步驟合併成⼀條硬體級指令，形成原⼦指令，

這樣就保證了這兩個步驟是不可分割的，要麼⼀次性執⾏完兩個步驟，要麼兩個步驟都不執⾏。

使⽤⾃旋鎖的時候，當發⽣多執行緒競爭鎖的情況，加鎖失敗的執行緒會「忙等待」，直到它拿到鎖。

這⾥的「忙等待」可以⽤ while 循環等待實現，不過最好是使⽤ CPU 提供的 PAUSE 指令來實現「忙等待」，因為可以減少循環等待時的耗電量。

⾃旋鎖是最⽐較簡單的⼀種鎖，⼀直⾃旋，利⽤ CPU 周期，直到鎖可⽤。

需要注意，在單核 CPU 上，需要搶佔式的調度器（即不斷通過時鐘中斷⼀個執行緒，運⾏其他執行緒）。

否則，⾃旋鎖在單 CPU 上⽆法使⽤，因為⼀個⾃旋的執行緒永遠不會放棄 CPU。

⾃旋鎖與互斥鎖使⽤層⾯⽐較相似，但實現層⾯上完全不同：

當加鎖失敗時，互斥鎖⽤「執行緒切換」來應對，⾃旋鎖則⽤「忙等待」來應對。

讀寫鎖

讀寫鎖的⼯作原理是：

  • 當「寫鎖」沒有被執行緒持有時，多個執行緒能夠並發地持有讀鎖，這⼤⼤提⾼了共享資源的訪問效率，

    因為「讀鎖」是⽤於讀取共享資源的場景，所以多個執行緒同時持有讀鎖也不會破壞共享資源的數據。

  • 但是，⼀旦「寫鎖」被執行緒持有後，讀執行緒的獲取讀鎖的操作會被阻塞，

    ⽽且其他寫執行緒的獲取寫鎖的操作也會被阻塞。

所以說，寫鎖是獨佔鎖，因為任何時刻只能有⼀個執行緒持有寫鎖，類似互斥鎖和⾃旋鎖，

⽽讀鎖是共享鎖，因為讀鎖可以被多個執行緒同時持有。

知道了讀寫鎖的⼯作原理後，我們可以發現，讀寫鎖在讀多寫少的場景，能發揮出優勢。

讀寫鎖可以分為「讀優先鎖」和「寫優先鎖」。

公平讀寫鎖⽐較簡單的⼀種⽅式是：

⽤隊列把獲取鎖的執行緒排隊，不管是寫執行緒還是讀執行緒都按照先進先出的原則加鎖即可，這樣讀執行緒仍然可以並發，也不會出現「飢餓」的現象。

互斥鎖和⾃旋鎖都是最基本的鎖，讀寫鎖可以根據場景來選擇這兩種鎖其中的⼀個進⾏實現。

樂觀鎖與悲觀鎖

悲觀鎖做事⽐較悲觀，它認為多執行緒同時修改共享資源的概率⽐較⾼，於是很容易出現衝突，所以訪問共享資源前，先要上鎖。

樂觀鎖做事⽐較樂觀，它假定衝突的概率很低，

它的⼯作⽅式是：先修改完共享資源，再驗證這段時間內有沒有發⽣衝突，

如果沒有其他執行緒在修改資源，那麼操作完成，如果發現有其他執行緒已經修改過這個資源，就放棄本次操作。

樂觀鎖全程並沒有加鎖，所以它也叫⽆鎖編程。

只有在衝突概率⾮常低，且加鎖成本⾮常⾼的場景時，才考慮使⽤樂觀鎖。

調度演算法

具體內容更新中…………

文件系統

⽂件系統的基本組成

Linux 最經典的⼀句話是：「⼀切皆⽂件」，不僅普通的⽂件和⽬錄，就連塊設備、管道、socket 等，也都是統⼀交給⽂件系統管理的。

虛擬⽂件系統

⽂件系統的種類眾多，⽽作業系統希望對⽤戶提供⼀個統⼀的接⼝，

於是在⽤戶層與⽂件系統層引⼊了中間層，這個中間層就稱為虛擬⽂件系統（Virtual File System，VFS）。

⽂件的存儲

連續空間存放

連續空間存放的⽅式雖然讀寫效率⾼，但是有「磁碟空間碎⽚」和「⽂件⻓度不易擴展」的缺陷。

⾮連續空間存放⽅式

⾮連續空間存放⽅式分為「鏈表⽅式」和「索引⽅式」。

鏈表⽅式

鏈表的⽅式存放是離散的，不⽤連續的，於是就可以消除磁碟碎⽚，可⼤⼤提⾼磁碟空間的利⽤率，同時⽂件的⻓度可以動態擴展。

「隱式鏈表」的⽅式存放的話，實現的⽅式是⽂件頭要包含「第⼀塊」和「最後⼀塊」的位置，並且每個數據塊⾥⾯留出⼀個指針空間，⽤來存放下⼀個數據塊的位置。

隱式鏈表的存放⽅式的缺點在於⽆法直接訪問數據塊，

只能通過指針順序訪問⽂件，以及數據塊指針消耗了⼀定的存儲空間。

隱式鏈接分配的穩定性較差，系統在運⾏過程中由於軟體或者硬體錯誤導致鏈表中的指針丟失或損壞，會導致⽂件數據的丟失。

「顯式鏈接」，它指把⽤於鏈接⽂件各數據塊的指針，顯式地存放在記憶體的⼀張鏈接表中，該表在整個磁碟僅設置⼀張，每個表項中存放鏈接指針，指向下⼀個數據塊號。

因⽽不僅顯著地提⾼了檢索速度，⽽且⼤⼤減少了訪問磁碟的次數。

但也正是整個表都存放在記憶體中的關係，它的主要的缺點是不適⽤於⼤磁碟。

索引⽅式

索引的實現是為每個⽂件創建⼀個「索引數據塊」，⾥⾯存放的是指向⽂件數據塊的指針列表，說⽩了就像書的⽬錄⼀樣，要找哪個章節的內容，看⽬錄查就可以。

另外，⽂件頭需要包含指向「索引數據塊」的指針，這樣就可以通過⽂件頭知道索引數據塊的位置，再通過索引數據塊⾥的索引資訊找到對應的數據塊。

索引的⽅式優點在於：

  • ⽂件的創建、增⼤、縮⼩很⽅便；
  • 不會有碎⽚的問題；
  • ⽀持順序讀寫和隨機讀寫；

鏈表 + 索引的組合，這種組合稱為「鏈式索引塊」，它的實現⽅式是在索引數據塊留出⼀個存放下⼀個索引數據塊的指針

索引 + 索引的⽅式，這種組合稱為「多級索引塊」，實現⽅式是通過⼀個索引塊來存放多個索引數據塊，⼀層套⼀層索引，像極了俄羅斯套娃是吧。

Unix ⽂件的實現⽅式

空閑空間管理

⽂件的存儲是針對已經被占⽤的數據塊組織和管理，

接下來的問題是，如果我要保存⼀個數據塊，我應該放在硬碟上的哪個位置呢？難道需要將所有的塊掃描⼀遍，找個空的地⽅隨便放嗎？

那這種⽅式效率就太低了，所以針對磁碟的空閑空間也是要引⼊管理的機制，接下來介紹⼏種常⻅的⽅法：

  • 空閑表法
  • 空閑鏈表法
  • 點陣圖法

空閑表法

空閑鏈表法

點陣圖法

點陣圖是利⽤⼆進位的⼀位來表示磁碟中⼀個盤塊的使⽤情況，磁碟上所有的盤塊都有⼀個⼆進位位與之對應。

當值為 0 時，表示對應的盤塊空閑，值為 1 時，表示對應的盤塊已分配。

在 Linux ⽂件系統就采⽤了點陣圖的⽅式來管理空閑空間，不僅⽤於數據空閑塊的管理，

還⽤於 inode 空閑塊的管理，因為 inode 也是存儲在磁碟的，⾃然也要有對其管理。

⽂件系統的結構

每個塊組⾥有很多重複的資訊，⽐如超級塊和塊組描述符表，這兩個都是全局資訊，⽽且⾮常的重要，這麼做是有兩個原因：

  1. 如果系統崩潰破壞了超級塊或塊組描述符，有關⽂件系統結構和內容的所有資訊都會丟失。

    如果有冗餘的副本，該資訊是可能恢復的。

  2. 通過使⽂件和管理數據儘可能接近，減少了磁頭尋道和旋轉，這可以提⾼⽂件系統的性能。

不過，Ext2 的後續版本采⽤了稀疏技術。

該做法是，超級塊和塊組描述符表不再存儲到⽂件系統的每個塊組中，

⽽是只寫⼊到塊組 0、塊組 1 和其他 ID 可以表示為 3、 5、7 的冪的塊組中。

⽬錄的存儲

如果⼀個⽬錄有超級多的⽂件，

我們要想在這個⽬錄下找⽂件，按照列表⼀項⼀項的找，效率就不⾼了。

於是，保存⽬錄的格式改成哈希表，對⽂件名進⾏哈希計算，把哈希值保存起來，如果我們要查找⼀個⽬錄下⾯的⽂件名，可以通過名稱取哈希。

Linux 系統的 ext ⽂件系統就是采⽤了哈希表，來保存⽬錄的內容，這種⽅法的優點是查找⾮常迅速，插⼊和刪除也較簡單，不過需要⼀些預備措施來避免哈希衝突。

軟鏈接和硬鏈接

硬鏈接（Hard Link） 和軟鏈接（Symbolic Link）

硬鏈接是多個⽬錄項中的「索引節點」指向⼀個⽂件，也就是指向同⼀個 inode，

但是 inode 是不可能跨越⽂件系統的，每個⽂件系統都有各⾃的 inode 數據結構和列表，所以硬鏈接是不可⽤跨⽂件系統的。

由於多個⽬錄項都是指向⼀個 inode，那麼只有刪除⽂件的所有硬鏈接以及源⽂件時，系統才會徹底刪除該⽂件。

軟鏈接相當於重新創建⼀個⽂件，這個⽂件有獨⽴的 inode，

但是這個⽂件的內容是另外⼀個⽂件的路徑，所以訪問軟鏈接的時候，實際上相當於訪問到了另外⼀個⽂件，

所以軟鏈接是可以跨⽂件系統的，甚⾄⽬標⽂件被刪除了，鏈接⽂件還是在的，只不過指向的⽂件找不到了⽽已。

⽂件 I/O

  • 緩衝與⾮緩衝 I/O
  • 直接與⾮直接 I/O
  • 阻塞與⾮阻塞 I/O VS 同步與非同步 I/O

阻塞與⾮阻塞 I/O VS 同步與非同步 I/O

先來看看阻塞 I/O，當⽤戶程式執⾏ read ，執行緒會被阻塞，⼀直等到內核數據準備好，並把數據從內核緩衝區拷⻉到應⽤程式的緩衝區中，當拷⻉過程完成， read 才會返回。

注意，阻塞等待的是「內核數據準備好」和「數據從內核態拷⻉到⽤戶態」這兩個過程。

⾮阻塞 I/O

這⾥最後⼀次 read 調⽤，獲取數據的過程，是⼀個同步的過程，是需要等待的過程。

這⾥的同步指的是內核態的數據拷⻉到⽤戶程式的快取區這個過程。

應⽤程式每次輪詢內核的 I/O 是否準備好，感覺有點傻乎乎，因為輪詢的過程中，應⽤程式啥也做不了，只是在循環。

為了解決這種傻乎乎輪詢⽅式，於是 I/O 多路復⽤技術就出來了，如 select、poll，它是通過 I/O 事件分發，當內核數據準備好時，再以事件通知應⽤程式進⾏操作。

這個做法⼤⼤改善了應⽤進程對 CPU 的利⽤率，在沒有被通知的情況下，應⽤進程可以使⽤ CPU 做其他的事情。

select I/O 多路復⽤

實際上，⽆論是阻塞 I/O、⾮阻塞 I/O，還是基於⾮阻塞 I/O 的多路復⽤都是同步調⽤。

因為它們在 read調⽤時，內核將數據從內核空間拷⻉到應⽤程式空間，過程都是需要等待的，

也就是說這個過程是同步的，如果內核實現的拷⻉效率不⾼，read 調⽤就會在這個同步過程中等待⽐較⻓的間。

⽽真正的非同步 I/O 是「內核數據準備好」和「數據從內核態拷⻉到⽤戶態」這兩個過程都不⽤等待。

非同步的IO

當我們發起 aio_read 之後，就⽴即返回，

內核⾃動將數據從內核空間拷⻉到應⽤程式空間，這個拷⻉過程同樣是非同步的，

內核⾃動完成的，和前⾯的同步操作不⼀樣，應⽤程式並不需要主動發起拷⻉動作。

⽤故事去理解這⼏種 I/O 模型

舉個你去飯堂吃飯的例⼦，你好⽐⽤戶程式，飯堂好⽐作業系統。

阻塞 I/O 好⽐，
你去飯堂吃飯，但是飯堂的菜還沒做好，然後你就⼀直在那⾥等啊等，

等了好⻓⼀段時間終於等到飯堂阿姨把菜端了出來（數據準備的過程），

但是你還得繼續等阿姨把菜（內核空間）打到你的飯盒⾥（⽤戶空間），

經歷完這兩個過程，你才可以離開。



⾮阻塞 I/O 好⽐，
你去了飯堂，問阿姨菜做好了沒有，阿姨告訴你沒，

你就離開了，過⼏⼗分鐘，你⼜來，

飯堂問阿姨，阿姨說做好了，於是阿姨幫你把菜打到你的飯盒⾥，這個過程你是得等待的。




基於⾮阻塞的 I/O 多路復⽤好⽐，
你去飯堂吃飯，發現有⼀排窗⼝，飯堂阿姨告訴你這些窗⼝都還沒做好菜，

等做好了再通知你，於是等啊等（ select 調⽤中），過了⼀會阿姨通知你菜做好了，

但是不知道哪個窗⼝的菜做好了，你⾃⼰看吧。

於是你只能⼀個⼀個窗⼝去確認，後⾯發現 5 號窗⼝菜做好了，

於是你讓 5 號窗⼝的阿姨幫你打菜到飯盒⾥，這個打菜的過程你是要等待的，雖然時間不⻓。

打完菜後，你⾃然就可以離開了。



非同步 I/O 好⽐，
你讓飯堂阿姨將菜做好並把菜打到飯盒⾥後，把飯盒送到你⾯前，整個過程你都不需要任何等待。

設備管理

DMA（Direct Memory Access） 功能，它可以使得設備在CPU 不參與的情況下，能夠⾃⾏完成把設備 I/O 數據放⼊到記憶體。

設備驅動程式

設備驅動程式會提供統⼀的接⼝給作業系統

存儲系統 I/O 軟體分層

網路系統


I/O 多路復⽤：select/poll/epoll

更新中…………

Tags:

VirMach 便宜 VPS

QNews

QNews