一般來說，一個系統會同時處理多個請求，但是其資源是優先的，調度就是用來協調每個請求對資源的使用的方法。調度中存在：優先級，時間片，截止時間等概念。

任務調度（task scheduling 也稱 CPU 調度）負責調度可執行的任務對 CPU 的使用；I/O 調度負責對應該以何種順序想存儲設備發起 I/O 請求進行調度；內存管理也是一種調度，內存管理將虛擬內存映射到物理內存，物理內存是有限的資源，當需要使用的虛擬內存超過物理內存容量時，換頁機制就是在對哪部分物理內頁的內容可以留在內存中進行調度，並將剩餘物理頁上到的內容寫回磁盤，進而復用那些剩餘的物理頁。

一般調度器會通過維護運行隊列（run queue）的方式來管理任務，Linux 調度器會用紅黑樹來實現運行隊列，任務在執行時若觸發一定條件，則會停止執行，這些條件可以是：

• 該任務執行瞭指定的時間片後，應讓其他任務在當前 CPU 核心上執行
• 該任務發起瞭 I/O 請求，在 I/O 返回前，它不會繼續執行
• 該任務主動停止執行或進入睡眠
• 該任務被系統中斷打斷，系統優先處理中斷而暫緩該任務的執行

調度器主要作用是做出調度決策，整個系統通過該決策進而決定如何調度，這些調度決策包括：

• 從運行隊列中選擇下一個運行任務
• 決定執行該任務的 CPU 核心
• 決定該任務被允許執行的時間，即時間片

調度器的設計問題主要可以歸納為兩類：

• 調度器應該做出什麼樣的調度決策（what）？
• 調度器應該如何做出符合預期的調度決策（how）？

常用的調度指標包括：

• 性能
• 吞吐量、周轉時間、響應時間、調度開銷

• 非性能
• 公平性、資源利用率

• 特殊
• 實時性、能耗

調度器面臨的挑戰：

• 調度指標多樣性
• 調度可參考的信息有限
• 任務間的復雜交互
• 許多方便存在權衡

調度器權衡包括但不限於一下幾點：

• 調度開銷與調度效果
• 優先級與公平性
• 性能與能耗

在任務調度中，長期、中期和短期調度相互協作，分別以不同的目標對進程進行調度。長期任務的觸發間隔較長，它粗粒度的決定是否應該將一個新的進程納入調度管理，負責增加系統中可被調度的進程的數量；中期調度的觸發相對頻繁，它輔助換頁機制，負責限制系統中可被調度的進程的數量；短期調度的觸發最為頻發，它負責細粒度的調度進程的執行，做出相應的調度決策。

調度流程：

在傳統操作系統中，批處理任務被發起後，其信息會被存入磁盤中的批處理隊列，等待被長期調度允許進入系統；

長期調度負責從批處理隊列中選取下一個可被調度的批處理任務，為其創建對應的進程，將進程設為預備狀態並放入運行隊列；

由於交互任務和實時任務一般都有比較高的時延要求，需要在一定時間內返回結果。所以這兩類任務一般不會被長期調度管理。系統會直接為他們創建對應的進程，將進程設為預備狀態並放入運行隊列；

通過短期調度的決策，運行隊列中的進程會被調度到 CPU 上執行，此時進程為運行狀態；

當進程運行完一個時間片後，短期調度會將其重新置為預備狀態，並放回運行隊列；

當運行中的進程發起 I/O 請求，等待用戶輸入或進入睡眠，因而需要被阻塞時，會被放入阻塞隊列，短期調度會選擇其他進程進行調度；

當進程等待的事件被觸發後，操作系統直接將對應的進程移出阻塞隊列，並將其置為預備狀態，重新放入運行隊列；

如果系統中的內存使用量偏大，就會觸發換頁機制，中期調度會掛起處於預備狀態、阻塞狀態的進程，將其置為掛起預備狀態/掛起阻塞狀態並放入掛起運行隊列/掛起阻塞隊列中；

處於掛起阻塞狀態的進程，如果其等待的時間被處罰，會被置為掛起預備狀態並被放入掛起運行隊列中；

當系統的內存使用不再緊張時，中期調度會激活掛起運行隊列/掛起阻塞隊列中的進程，將其置為預備狀態/阻塞狀態並放回運行隊列/阻塞隊列中；當進程結束後，會進入終止狀態並最終被回收單核調度策略

調度策略

1 經典調度

1.1 先到先得（FCFS），弊端：在長短任務混合的場景下對短任務不友好 ，對 I/O 密集型任務不友好

1.2 最短任務優先（SJF）

弊端：必須預知任務的運行時間，其表現嚴重依賴與任務到達時間點

1.3 最短完成時間任務優先（STCF），SJF 的搶占式版本

弊端：必須預知任務的運行時間，長任務饑餓

1.4 時間片輪轉（RR）：對於 RR 策略，一個關鍵點是它的時間片該如何選取。

弊端：在任務運行時間相似的場景下平均周轉時間高，RR 一定程度上保證瞭每個任務之間的公平性，同時也可獲得良好的響應時間，但是在特定場景下，任務的平均周轉時間可能較差。

2 優先級調度

2.1 多級隊列（MLQ）

每個任務會被分配預先設置好的優先級，每個優先級對應一個隊列，任務會被存儲在對應的優先級隊列中。如果優先級不同的任務同時處於預備狀態，那麼調度器應該傾向於調度優先級較高的任務，因此一個任務必須等到所有優先級比它高的任務調度完成才可以被調度。處於相同優先級隊列的任務，它們內部的調度方式沒有統一標準，可以針對性的為不同隊列采用不同的調度策略，如 FCFS 或 RR。

在設置 MLQ 策略的任務優先級時，需要註意將 I/O 密集型任務的優先級提高，保證 I/O 資源利用率。

弊端：低優先級任務饑餓，如果調度器需要保證一定的公平性，需要引入額外的機制監控任務等待時間，為等待時間過長（如超過一定的閾值）的任務提升優先級，2 優先級反轉，在程序執行時，多個任務可能會對同一份數據產生競爭，因此任務會使用鎖來保護共享數據。假設存在 3 個任務A，B，C，他們的優先級是 ABC，任務 C 在運行時持有一把鎖，然後被高優先級的 A 搶占瞭，A 也想申請任務 C 持有的鎖，但是申請失敗，因此進入阻塞狀態等待 C 釋放鎖，此時 BC 都處於可以運行狀態，B 優先級高，因此 B 先運行，觀察該情況，會發現 B 的優先級好像高於 A，這一問題稱為優先級反轉。一個可行的解決方案是優先級繼承。

2.2 多級反饋隊列（MLFQ）

，在 MLQ 基礎上，增加瞭動態設置任務優先級的策略，MLFQ 策略也會維護多個優先級隊列，處於相同優先級的任務則采用 RR 策略執行，優先級的動態設置策略如下：

• 短任務擁有更高的優先級，好處：1. 可以有更好的平均周轉時間；2. I/O 密集型任務一般在 CPU 中執行的時間很短，給短任務提高優先級也相當於提高 I/O 密集型任務的優先級，提高系統的 I/O 資源利用率；3. 交互式任務一般是短任務，降低響應時間。根據每個任務（多次）執行時間來判斷是短任務還是長任務。當任務進入系統中，假設任務是短任務，MLFQ 會為每個任務隊列設置任務的最大運行時間，如果超過瞭最大時間，就會將該任務的優先級減一。
• 低優先級的任務采用更長的時間片，為瞭減少任務的調度次數，優先級月底的任務，其時間片越長，由於 MLFQ 策略支持搶占式調度，無須擔心低優先級的任務阻塞新進入系統的任務。
• 定時將所有任務的優先級提升至最高，避免出現低優先級任務饑餓。

3 公平共享調度

• “公平”是指任務對資源的使用符合用戶預期

公平共享調度會量化任務對系統資源的占有比例，從而實現對資源的公平調度。用份額（share）來量化每個任務對 CPU 時間的使用。份額支持曾計劃的分配方式，可以將任務分組，以組為單位分配份額，任務組會在組內進一步分攤該組所擁有的份額。

優先級和份額都表示瞭任務在系統中的重要程度，但是目的是不同的。優先級調度是為瞭優化任務的周轉時間、響應時間和資源利用率而設計的。不同任務的優先級隻能用於相互比較，表明任務執行的先後。而基於份額的公平共享調度是為瞭讓每個任務都能使用它應該獲得的系統資源。分隔的值明確對應瞭任務應使用的系統資源比例。

彩票調度，彩票轉讓，彩票貨幣，彩票通脹。弊端：

• 隨機數所帶來的問題，彩票調度通過使用隨機的方式實現瞭一個簡單並且近似於公平共享的調度器，然而，隨機數會導致某一任務占用 CPU 時間的比例，需要在該任務經歷多次調度後，才能趨近於該任務的份額在所有任務總份額的比例。隻有調度次數足夠多，彩票調度效果才接近公平。步幅調度，采用確定性的方式調度任務，核心概念是步幅。引入虛擬時間的概念。為瞭讓虛擬時間短的任務能夠“追趕”虛擬時間長的任務，使用虛擬時間的調度策略一般會選擇調度所有任務中虛擬時間最少的任務。步幅調度通過設置虛擬時間的方式，讓任務在每次調度時增加一定的虛擬時間，即步幅。經歷虛擬時間相同的任務，它們使用的 CPU 時間之比就是步幅的倒數之比，換句話說，任務的份額之比正對應瞭任務的步幅的倒數之比。在真實的系統中，由於任務可能在任意時間進入系統，因此任務經歷的虛擬時間不能為 0，而應該設置為當前所有任務的最小虛擬時間值，放置新進入的任務長時間占有 CPU。

4 實時調度

根據任務超過截止時間所造成的後果分類：

• 硬實時任務，該類任務必須在截止時間前完成
• 軟實時任務，該類任務可以偶爾超過截止時間完成

根據被觸發的時間分類：

• 周期任務，指到達系統時間遵循一定周期的任務
• 偶發任務，指不會周期性的到達系統的任務，且還要滿足連續兩個相同偶發任務到達系統的時間間隔有最小值，即系統不會在同一時刻處理兩個相同的偶發任務。偶發任務通常是硬實時任務。
• 非周期性任務，指到達系統時間隨機的任務，通常是軟實時任務。

5 多核調度策略

在多核上進行調度時，需要回答以下三個問題：

• 當前應該調度哪個/哪些任務？
• 每個調度的任務應該在哪個 CPU 核心上執行？
• 每個調度的任務應該執行多久？

負載分擔

設想多核共享一個全局運行隊列，當一個 CPU 核心需要調度任務時，根據給定的調度策略，決定全局運行隊列中下一個由它執行的任務。給定的調度策略可以是任一一種單核調度策略，這種方法稱為負載分擔，因為系統的負載是被所有的 CPU 核心分擔的。

優點：

• 設計實現簡單，通過使用負載分擔，可以將多核調度問題規約為單核調度問題，使用已有的單核調度策略和單核調度器，就可以實現一個多核的全局調度器
• 每個 CPU 核心都會分擔系統的負載，不會出現 CPU 資源浪費的情況，一個 CPU 核心執行完當前任務後，它會從全局任務隊列中再選取一個任務執行，隻要當前系統還有可以執行的任務，每個 CPU 核心都能獲取到任務執行

問題：

• 多核共享一個全局運行隊列的同步開銷
• 任務在多個 CPU 核心間來回切換的開銷，包括重新載入緩存，TLB 刷新等

協同調度

為瞭滿足對蟻族任務進行調度的需求，協同調度的概念應運而生。協同調度的目的是盡可能讓一組任務並行執行，避免調度器同時調度有依賴關系的兩組任務，同時避免關聯任務執行效率降低的問題。

協同調度的經典策略是群組調度。

兩級調度

為瞭減少任務在不同 CPU 核心上切換執行的開銷，每個任務應盡可能隻在一個 CPU 核心上進行調度。因此，新的調度策略改為每個 CPU 核心都引入一個本地調度器，並用它管理對應核心上執行的任務。這種調度策略使用全局調度器和本地調度器，構成瞭層級化結構，一般稱為兩級調度。

當一個任務進入系統時，全局調度器根據系統的當前信息，諸如每個 CPU 核心的負載情況，決定該任務應該被哪個 CPU 核心執行，當一個任務被分配給定的核心時，它將一直被該核心的本地調度器管理，不會遷移到其他 CPU 核心上執行。同時，每個本地調度器可以使用任意單核調度策略來調度任務。在避免線程在 CPU 核心間來回切換，提高瞭緩存局部性，較少瞭數據競爭的沖突的同時，這種曾計劃的設計將設計單核調度策略與支持多核調度進行瞭解耦，使得調度器的設計實現更加靈活。以 Linux 為代表的一系列操作系統會為每個 CPU 核心分配一個本地運行隊列，即可理解為每個 CPU 核心有一個本地調度器。

負載追蹤與負載均衡

兩級調度策略避免瞭任務在多核間切換，但是由於在任務開始時就指定瞭它在哪個 CPU 上運行，且沒有任務在 CPU 核心間切換的機制，可能會導致多核間的負載不均衡，為瞭解決這個問題，引入瞭負載均衡的策略，負載均衡的思想是：通過追蹤每個 CPU 核心當前的負載情況，將處於高負載的 CPU 核心管理的任務遷移至低負載的 CPU 核心上，盡可能的保證每個核心的負載大致相同。

負載均衡面臨的挑戰是：如何確定當前任務的負載情況，一個任務的執行負載是動態變化的，因此系統必須動態追蹤當前的負載情況，這會造成一定的性能開銷，如何保持低開銷的同時對負載進行精確追蹤是調度器設計實現的一大挑戰，Linux 目前使用的是調度實體粒度負載追蹤（PELT）。

運行隊列粒度的負載追蹤，在 Linux 3.8 以前，內核以每個 CPU 核心的運行隊列為粒度計算負載，認為運行隊列長的負載就高，導致負載追蹤不夠精確。

調度實體粒度的負載追蹤，在 Linux 3.8 以後，Linux 使用瞭以調度實體（單個任務）為粒度的負載計算方式，做到瞭更細粒度的負載追蹤。PELT通過記錄每個任務的歷史執行狀況來表示任務的當前負載。具體的，調度器會以 1024 微妙作為一個周期，記錄任務處於可運行狀態（包括正在運行的以及等待被運行的）的時間，記為 x 微妙。該任務在第 i 個周期內對當前 CPU 的利用率為 x/1024，而對應的負載 Li 為 scale_cpu_capacity x/1024 ，其中 scale_cpu_capacity 是 CPU 容量，可以理解為對應 CPU 核心的處理能力。在手機到任務每個周期內的負載後，PELT 需要計算一段時間內任務所有周期的累計負載，隨著距離當前時間越遠，數據參考意義越小，采用衰減系數 y 來計算：L = L0 + L0 y + L1 y^2 + L2 y ^3…. 通過計算每個任務的負載 L，PELT 就可以進而統計出每個運行隊列的負載，便於調度器做出有效的遷移決策。

隨著 CPU 核心數量越來越多，系統架構越來越復雜，負載均衡策略應該讓任務盡量在遷移開銷較小的 CPU核心間遷移，以 NUMA 架構為例，當任務從一個 NUMA 節點遷移到另一個 NUMA 節點，會嚴重影響任務的執行效率，又以超線程為例，一個物理核會被邏輯上分為兩個邏輯核，任務在同屬於一個五裡河的兩個邏輯核間切換的開銷，會比在不同五裡河的兩個邏輯核間的開銷小很多。

Linux 為瞭解決上述問題，采用層級化的方法，引入兩個數據結構：調度與是有用相同特性的 CPU 核心的集合，這些核心間可以進行負載均衡。一個調度與保存一個或多個調度組，調度組是一個調度與內進行負載均衡的整體單位。通過自下而上的方式層級式的進行負載均衡，並且為瞭設計簡單，隻允許觸發負載均衡的 CPU 核心拉取其他 CPU 核心的任務到本地。如果當前 CPU 核心觸發負載均衡邏輯，首先在最底層調度域內的調度組間進行均衡，然後依次進入更高一級的調度域，並對其管理的調度組進行負載均衡。由於越高層級的調度域間進行負載均衡的開銷越大，所以 Linux 為不同層級的調度域設置瞭不同的負載均衡觸發頻率與閾值。

對於非實時任務，Linux 使用 CFS 調度器進行調度，CFS 采用瞭累死公平共享調度的策略，因此其主要關心每個任務占用 CPU 時間的份額。sched_nice 為[-20,19] 的 Niceness ，越不友善的任務越傾向於使用更多的資源或搶占其他友善的任務。

Linux 調度器設計

O(n) 調度器

在 Linux 2.4 版本以前，Linux 調度器是一個機遇 RR 策略的運行隊列，沒有考慮很多因素（諸如任務的實時性要求）。從 Linux 2.4 版本開始，采用 O(n) 調度器，O(n) 調度器指定調度決策的時間復雜度是 O(n) ，n 代表的是調度器運行隊列中的任務數量。

O(n) 調度器采用瞭負載分擔的思想，所有任務被存儲於一個全局運行隊列中，被選擇調度的任務會從運行隊列中移除，當該任務執行完並且需要再次被調度時，會被重新放入運行隊列的隊尾。當調度器選擇下一個被調度的任務時，需要遍歷運行隊列中的所有任務，並重新計算他們的動態優先級，然後選取動態優先級最高的任務。

存在問題：

• 調度開銷過大
• 多核擴展性差

O(1) 調度器

由於O(n) 調度器存在上述問題，Linux 在 2.6.0 版本使用心得 O(1) 調度器替換 O(n) 調度器。 O(1) 調度器采用瞭兩級調度的思想，每個 CPU 核心單獨維護一個本地運行隊列，讓任務僅在同一個核心上調度。每個本地運行隊列實際上是由兩個多級隊列：激活隊列和過期隊列組成的，分別用於管理仍有時間片剩餘的任務和時間片耗盡的任務。當一個任務的時間片耗盡後，它會被加入到過期隊列中。如果當前激活隊列中沒沒有可調度的任務， O(1) 調度器會將兩個隊列的角色互換，開始新一輪調度。每個多級隊列都有 140 個優先級，其中高優先級 [0,100) 對應於實時任務，剩下的優先級 [100, 140) 對應於不同 Niceness 的非實時任務。每個多級隊列都維護瞭一個位圖，位圖中的比特位用於判斷對應的優先級隊列是否有任務等待調度，在制定調度決策時， O(1) 調度器會根據位圖找到激活隊列中第一個不為空的隊列，並調度該隊列的第一個任務，其時間復雜度是 O(1) ，與運行隊列中的任務數量無關。

用戶可能不希望交互式任務在時間片用完後就需要等待所有其他任務的時間片用完才能再次執行，因此該類任務在時間片用完後，仍然會被加入激活隊列中。同時，為瞭防止交互式任務過於激進而導致當前過期隊列中的任務無法執行，當過期隊列中的任務等待過長時間後， O(1) 調度器會把交互式任務加入過期多列中。

存在問題：

• 交互式任務的判定算法過於復雜
• 靜態時間片帶來的問題， O(1) 調度器的非實時任務的運行時間片是根據其 Niceness 靜態確定的，問題是，隨著系統中任務數量的上升，任務的調度時延也會上升，對應的，響應時間也會受到影響。

完全公平調度器

為瞭解決 O(1)調度器的問題，Linux 從 2.6.23 版本開始使用完全公平調度器。公平共享調度策略保證每個任務可以根據自己所占的份額共享 CPU 時間，這是 CFS 調度器的基本思想，O(1)調度器需要繁瑣的通過啟發式方法確定交互式任務，再給與交互式任務更多的執行機會。而 CFS 調度器隻關心非實時任務對 CPU 時間的公平共享，避免瞭復雜的調度算法實現與調參。同時通過動態的設定任務時間片，確保瞭任務的調度時延不會過高。

CFS 調度器所使用的調度策略類似於步幅調度，vruntime 代表人物經過的虛擬時間，在調度是 CFS 會調度 vruntime 值最低的任務，Linux 靜態的設置瞭 Niceness 與任務權重的對應關系，Niceness 越低則任務的權重越高，可被分配的 CPU 時間越多。

CFS 調度器的動態時間片，為瞭避免靜態設置任務時間片所帶來的問題，CFS 調度使用瞭調度周期的概念，並保證每經過一個調度周期，運行隊列中所有任務都會被調度一次。因而在最壞的情況下，任務的調度時延即為一個調度周期。同時間片一樣，調度周期會帶來權衡問題。如果調度周期過長，則一系列任務必須在很長時間的運行後才能體現公平性，且任務的調度時延可能過長；如果調度周期過短，則調度開銷會變大。

確定瞭 CFS 的調度周期後，調度器就可以開始計算在當前運行隊列中，第 i 個任務的動態時間片 time_slice_i = sched_period * weight_i / weight_rq ，其中 weight_i 是第 i 個任務的權重，weight_rq 代表當前運行隊列中的任務權重之和。

由於每個任務的動態時間片是不同的，都根據任務權重進行瞭縮放，所以任務每次執行後對 vruntime 的更新也要進行對應的縮放：vruntime_i = vruntime_i + weight_nice0 / weight_i * real_runtime ，其中 weight_nice0 表示一個 Niceness 為 0 的任務的權重，該權重與 weight_i 的比值是一個系數，用於將任務的實際運行時間映射為虛擬時間。通過該系數，CFS 保證瞭不同動態時間片的任務執行完自己的時間片後，他們虛擬時間的增幅是一致的。

同步原語

實際應用程序中有很多需要同步的場景，為瞭正確，搞笑的解決這些同步問題，抽象出瞭一系列同步原語。

互斥鎖

當程序的正確性依賴於特定執行順序的情況時，被稱為競爭冒險。避免競爭冒險最直接的辦法就是：確保同一時刻隻有生產者中的一個能夠對共享緩沖區進行操作。任意時刻隻允許至多一個線程訪問的方式被稱為互斥訪問，而保證互斥訪問共享資源的代碼區域被稱為臨界區。

需要滿足以下條件：

• 互斥訪問：在同一時刻，最多隻能有一個線程可以執行臨界區
• 有限等待：當一個線程申請進入臨界區後，必須在有限的時間內獲得許可並進入臨界區，不能無限等待
• 空閑讓進：當沒有線程在執行臨界區代碼時，必須在申請進入臨界區的線程中選擇一個線程，允許其執行臨界區代碼，保證程序執行的進展。

硬件實現：關閉中斷。

關閉中斷可以防止執行臨界區的線程被搶占，避免多個線程同時執行臨界區，保證瞭互斥訪問。而有限等待依賴於內核的調度器，如果能保證有限時間內調度到該線程，則該線程可以再有限時間內進入臨界區，達成有限等待的要求。最後，每個線程離開臨界區時都開啟瞭中斷，允許調度器調度其他線程執行，達成瞭空閑讓進的要求。但是多核環境中，即使關閉瞭所有核心的中斷，也不能阻塞其他核心上正在運行的線程繼續執行。

軟件實現：皮特森算法https://zh.wikipedia.org/wiki/Peterson%E7%AE%97%E6%B3%95。

軟硬件協同：使用原子操作實現互斥鎖。原子操作指的是不可被打斷的一個或一系列操作。即要麼這一系列指令都執行完成，要麼都沒有執行，最常見的是比較與置換 （CAS）拿取並累加（FAA）。

互斥鎖的實現種類多，不同的互斥鎖被用於不同的場景，比如利用原子 CAS 實現的自旋鎖，利用原子 FAA 實現的排號自旋鎖。

自旋鎖：

利用一個變量 lock 表示鎖的狀態，lock 為 1 表示已經有人拿鎖，為 0 表示空閑。在加鎖時，線程會通過 CAS 判斷 lock 是否為空閑，如果空閑則上鎖，否則將一遍一遍重試。放鎖時，直接將 lock 設置為 0 表示其空閑。自旋鎖不能保證有限等待，即不具有公平性。自旋鎖並非按照申請的順序決定下一個獲取鎖的競爭者，而是讓所有的競爭者均同時嘗試完成原子操作。

排號自旋鎖：

排號自旋鎖按照鎖競爭者申請鎖的順序傳遞鎖，鎖的競爭者組成瞭一個 FIFO 的等待隊列。排號鎖的結構體有兩個成員，owner 表示當前鎖持有者序號，next 表示下一個需要分發的序號。獲取排號所需要先通過原子的 FAA 操作拿到最新的序號並同時增加鎖的分發序號，來避免其他競爭者拿到相同的序號。拿到序號後，競爭者通過判斷 owner 的值，等待排到自己的序號，一旦兩者想等，競爭者擁有該鎖並被允許進入臨界區。釋放鎖時，持有者更新 owner 的值將鎖傳遞給下一個競爭者，保證瞭公平性。

條件變量

使用條件變量提供的借口，一個線程可以停止使用 CPU 並將自己掛起，當等待的條件滿足時，其他的線程會喚醒該掛起的線程讓其繼續執行，使用條件變量能夠有效的避免無謂的循環等待。

互斥鎖 vs 條件變量：

互斥鎖與條件變量解決的不是同一個問題，互斥鎖用於解決臨界區的問題，保證互斥訪問共享資源。而條件變量通過提供掛起/喚醒機制來避免循環等待，節省 CPU 資源。條件變量需要和互斥鎖搭配使用。

信號量

信號量在不同的線程之間充當信號燈，根據剩餘資源數量控制不同線程的執行或等待。信號量又被成為 PV 原語，P 為校驗，V 為自增。

互斥鎖 vs 信號量：

互斥鎖與信號量有相似之處。當信號量的初始值為 1，且隻允許其值在 0 和 1 之間變化時，wait 和 signal 操作分別於互斥鎖的 lock 和 unlock 操作類似，稱這種信號量為二院信號量。二元信號量與互斥鎖的差別在於：互斥鎖有擁有者概念，二元信號量沒有。互斥鎖往往由同一個線程加鎖和放鎖，信號量允許不同線程執行 wait 與 signal 操作。互斥鎖與計數信號量（非二元信號量）區別較大，計數信號量允許多個線程通過，其數量等於剩餘可用資源數量；而互斥鎖同一時刻隻允許一個線程獲取。互斥鎖用於保證多個線程對一個共享資源的互斥訪問，而信號量用於協調多個線程對一系列共享資源的有序操作。

條件變量 vs 信號量：

信號量是由條件變量、互斥鎖以及計數器實現的。而這個計數器就是信號量的核心，用於表示當前可用資源的數量。可以理解為：信號量利用條件變量實現瞭更高層級的抽象。

同步帶來的問題

死鎖

死鎖產生的必要條件：

• 互斥訪問
• 持有並等待
• 資源非搶占
• 循環等待

優先級反轉：由於同步導致線程執行順序違反預設優先級的問題。

解決方法：

• 不可搶占臨界區協議，核心時避免線程在臨界區中被搶占，當線程獲取鎖，編不允許任何其他線程搶占。
• 優先級繼承協議，在高優先級線程等待鎖時，會使鎖的持有者繼承其優先級，從而避免該鎖的臨界區被低優先級的任務打斷。
• 優先級置頂協議，將獲取鎖的線程的優先級置為可能競爭該鎖的最高優先級。