超硬核，要是當初這麼學進程和執行緒就好了！

來源：Java建設者

作者：cxuan

下面是本文的結構圖

我們平常說的進程和執行緒更多的是基於程式語言的角度來說的，那麼你真的了解什麼是執行緒和進程嗎？那麼我們就從作業系統的角度來了解一下什麼是進程和執行緒。

進程

作業系統中最核心的概念就是 進程，進程是對正在運行中的程式的一個抽象。作業系統的其他所有內容都是圍繞著進程展開的。進程是作業系統提供的最古老也是最重要的概念之一。即使可以使用的 CPU 只有一個，它們也支援（偽）並發操作。它們會將一個單獨的 CPU 抽象為多個虛擬機的 CPU。可以說：沒有進程的抽象，現代作業系統將不復存在。

所有現代的電腦會在同一時刻做很多事情，過去使用電腦的人（單 CPU）可能完全無法理解現在這種變化，舉個例子更能說明這一點：首先考慮一個 Web 伺服器，請求都來自於 Web 網頁。當一個請求到達時，伺服器會檢查當前頁是否在快取中，如果是在快取中，就直接把快取中的內容返回。如果快取中沒有的話，那麼請求就會交給磁碟來處理。但是，從 CPU 的角度來看，磁碟請求需要更長的時間，因為磁碟請求會很慢。當硬碟請求完成時，更多其他請求才會進入。如果有多個磁碟的話，可以在第一個請求完成前就可以連續的對其他磁碟發出部分或全部請求。很顯然，這是一種並發現象，需要有並發控制條件來控制並發現象。

現在考慮只有一個用戶的 PC。當系統啟動時，許多進程也在後台啟動，用戶通常不知道這些進程的啟動，試想一下，當你自己的電腦啟動的時候，你能知道哪些進程是需要啟動的么？這些後台進程可能是一個需要輸入電子郵件的電子郵件進程，或者是一個電腦病毒查殺進程來周期性的更新病毒庫。某個用戶進程可能會在所有用戶上網的時候列印文件以及刻錄 CD-ROM，這些活動都需要管理。於是一個支援多進程的多道程式系統就會顯得很有必要了。

在許多多道程式系統中，CPU 會在進程間快速切換，使每個程式運行幾十或者幾百毫秒。然而，嚴格意義來說，在某一個瞬間，CPU 只能運行一個進程，然而我們如果把時間定位為 1 秒內的話，它可能運行多個進程。這樣就會讓我們產生並行的錯覺。有時候人們說的 偽並行(pseudoparallelism) 就是這種情況，以此來區分多處理器系統(該系統由兩個或多個 CPU 來共享同一個物理記憶體)

再來詳細解釋一下偽並行：偽並行是指單核或多核處理器同時執行多個進程，從而使程式更快。通過以非常有限的時間間隔在程式之間快速切換CPU，因此會產生並行感。缺點是 CPU 時間可能分配給下一個進程，也可能不分配給下一個進程。

因為 CPU 執行速度很快，進程間的換進換出也非常迅速，因此我們很難對多個並行進程進行跟蹤，所以，在經過多年的努力後，作業系統的設計者開發了用於描述並行的一種概念模型（順序進程），使得並行更加容易理解和分析，對該模型的探討，也是本篇文章的主題。下面我們就來探討一下進程模型

進程模型

在進程模型中，所有電腦上運行的軟體，通常也包括作業系統，被組織為若干順序進程(sequential processes)，簡稱為 進程(process) 。一個進程就是一個正在執行的程式的實例，進程也包括程式計數器、暫存器和變數的當前值。從概念上來說，每個進程都有各自的虛擬 CPU，但是實際情況是 CPU 會在各個進程之間進行來回切換。

如上圖所示，這是一個具有 4 個程式的多道處理程式，在進程不斷切換的過程中，程式計數器也在不同的變化。

在上圖中，這 4 道程式被抽象為 4 個擁有各自控制流程（即每個自己的程式計數器）的進程，並且每個程式都獨立的運行。當然，實際上只有一個物理程式計數器，每個程式要運行時，其邏輯程式計數器會裝載到物理程式計數器中。當程式運行結束後，其物理程式計數器就會是真正的程式計數器，然後再把它放回進程的邏輯計數器中。

從下圖我們可以看到，在觀察足夠長的一段時間後，所有的進程都運行了，但在任何一個給定的瞬間僅有一個進程真正運行。

因此，當我們說一個 CPU 只能真正一次運行一個進程的時候，即使有 2 個核（或 CPU），每一個核也只能一次運行一個執行緒。

由於 CPU 會在各個進程之間來回快速切換，所以每個進程在 CPU 中的運行時間是無法確定的。並且當同一個進程再次在 CPU 中運行時，其在 CPU 內部的運行時間往往也是不固定的。進程和程式之間的區別是非常微妙的，但是通過一個例子可以讓你加以區分：想想一位會做飯的電腦科學家正在為他的女兒製作生日蛋糕。他有做生日蛋糕的食譜，廚房裡有所需的原諒：麵粉、雞蛋、糖、香草汁等。在這個比喻中，做蛋糕的食譜就是程式、電腦科學家就是 CPU、而做蛋糕的各種原料都是輸入數據。進程就是科學家閱讀食譜、取來各種原料以及烘焙蛋糕等一系列動作的總和。

現在假設科學家的兒子跑過來告訴他，說他的頭被蜜蜂蜇了一下，那麼此時科學家會記錄出來他做蛋糕這個過程到了哪一步，然後拿出急救手冊，按照上面的步驟給他兒子實施救助。這裡，會涉及到進程之間的切換，科學家（CPU）會從做蛋糕（進程）切換到實施醫療救助（另一個進程）。等待傷口處理完畢後，科學家會回到剛剛記錄做蛋糕的那一步，繼續製作。

這裡的關鍵思想是認識到一個進程所需的條件，進程是某一類特定活動的總和，它有程式、輸入輸出以及狀態。單個處理器可以被若干進程共享，它使用某種調度演算法決定何時停止一個進程的工作，並轉而為另外一個進程提供服務。另外需要注意的是，如果一個進程運行了兩遍，則被認為是兩個進程。那麼我們了解到進程模型後，那麼進程是如何創建的呢？

進程的創建

作業系統需要一些方式來創建進程。下面是一些創建進程的方式

  • 系統初始化（init）
  • 正在運行的程式執行了創建進程的系統調用（比如 fork）
  • 用戶請求創建一個新進程
  • 初始化一個批處理工作

系統初始化

啟動作業系統時，通常會創建若干個進程。其中有些是前台進程(numerous processes)，也就是同用戶進行交互並替他們完成工作的進程。一些運行在後台，並不與特定的用戶進行交互，例如，設計一個進程來接收發來的電子郵件，這個進程大部分的時間都在休眠，但是只要郵件到來後這個進程就會被喚醒。還可以設計一個進程來接收對該電腦上網頁的傳入請求，在請求到達的進程喚醒來處理網頁的傳入請求。進程運行在後台用來處理一些活動像是 e-mail，web 網頁，新聞，列印等等被稱為 守護進程(daemons)。大型系統會有很多守護進程。在 UNIX 中，ps 程式可以列出正在運行的進程， 在 Windows 中，可以使用任務管理器。

系統調用創建

除了在啟動階段創建進程之外，一些新的進程也可以在後面創建。通常，一個正在運行的進程會發出系統調用用來創建一個或多個新進程來幫助其完成工作。例如，如果有大量的數據需要經過網路調取並進行順序處理，那麼創建一個進程讀數據，並把數據放到共享緩衝區中，而讓第二個進程取走並正確處理會比較容易些。在多處理器中，讓每個進程運行在不同的 CPU 上也可以使工作做的更快。

用戶請求創建

在許多互動式系統中，輸入一個命令或者雙擊圖標就可以啟動程式，以上任意一種操作都可以選擇開啟一個新的進程，在基本的 UNIX 系統中運行 X，新進程將接管啟動它的窗口。在 Windows 中啟動進程時，它一般沒有窗口，但是它可以創建一個或多個窗口。每個窗口都可以運行進程。通過滑鼠或者命令就可以切換窗口並與進程進行交互。

互動式系統是以人與電腦之間大量交互為特徵的電腦系統，比如遊戲、web瀏覽器，IDE 等集成開發環境。

批處理創建

最後一種創建進程的情形會在大型機的批處理系統中應用。用戶在這種系統中提交批處理作業。當作業系統決定它有資源來運行另一個任務時，它將創建一個新進程並從其中的輸入隊列中運行下一個作業。

從技術上講，在所有這些情況下，讓現有流程執行流程是通過創建系統調用來創建新流程的。該進程可能是正在運行的用戶進程，是從鍵盤或滑鼠調用的系統進程或批處理程式。這些就是系統調用創建新進程的過程。該系統調用告訴作業系統創建一個新進程，並直接或間接指示在其中運行哪個程式。

在 UNIX 中，僅有一個系統調用來創建一個新的進程，這個系統調用就是 fork。這個調用會創建一個與調用進程相關的副本。在 fork 後，一個父進程和子進程會有相同的記憶體映像，相同的環境字元串和相同的打開文件。通常，子進程會執行 execve 或者一個簡單的系統調用來改變記憶體映像並運行一個新的程式。例如，當一個用戶在 shell 中輸出 sort 命令時，shell 會 fork 一個子進程然後子進程去執行 sort 命令。這兩步過程的原因是允許子進程在 fork 之後但在 execve 之前操作其文件描述符，以完成標準輸入，標準輸出和標準錯誤的重定向。

在 Windows 中，情況正相反，一個簡單的 Win32 功能調用 CreateProcess，會處理流程創建並將正確的程式載入到新的進程中。這個調用會有 10 個參數，包括了需要執行的程式、輸入給程式的命令行參數、各種安全屬性、有關打開的文件是否繼承控制位、優先順序資訊、進程所需要創建的窗口規格以及指向一個結構的指針，在該結構中新創建進程的資訊被返回給調用者。除了 CreateProcess Win 32 中大概有 100 個其他的函數用於處理進程的管理，同步以及相關的事務。下面是 UNIX 作業系統和 Windows 作業系統系統調用的對比

在 UNIX 和 Windows 中，進程創建之後，父進程和子進程有各自不同的地址空間。如果其中某個進程在其地址空間中修改了一個詞，這個修改將對另一個進程不可見。在 UNIX 中，子進程的地址空間是父進程的一個拷貝，但是卻是兩個不同的地址空間；不可寫的記憶體區域是共享的。某些 UNIX 實現是正是在兩者之間共享，因為它不能被修改。或者，子進程共享父進程的所有記憶體，但是這種情況下記憶體通過 寫時複製(copy-on-write) 共享，這意味著一旦兩者之一想要修改部分記憶體，則這塊記憶體首先被明確的複製，以確保修改發生在私有記憶體區域。再次強調，可寫的記憶體是不能被共享的。但是，對於一個新創建的進程來說，確實有可能共享創建者的資源，比如可以共享打開的文件。在 Windows 中，從一開始父進程的地址空間和子進程的地址空間就是不同的。

進程的終止

進程在創建之後，它就開始運行並做完成任務。然而，沒有什麼事兒是永不停歇的，包括進程也一樣。進程早晚會發生終止，但是通常是由於以下情況觸發的

  • 正常退出(自願的)
  • 錯誤退出(自願的)
  • 嚴重錯誤(非自願的)
  • 被其他進程殺死(非自願的)

正常退出

多數進程是由於完成了工作而終止。當編譯器完成了所給定程式的編譯之後，編譯器會執行一個系統調用告訴作業系統它完成了工作。這個調用在 UNIX 中是 exit ，在 Windows 中是 ExitProcess。面向螢幕中的軟體也支援自願終止操作。字處理軟體、Internet 瀏覽器和類似的程式中總有一個供用戶點擊的圖標或菜單項，用來通知進程刪除它所打開的任何臨時文件，然後終止。

錯誤退出

進程發生終止的第二個原因是發現嚴重錯誤，例如，如果用戶執行如下命令

cc foo.c

為了能夠編譯 foo.c 但是該文件不存在，於是編譯器就會發出聲明並退出。在給出了錯誤參數時，面向螢幕的互動式進程通常並不會直接退出，因為這從用戶的角度來說並不合理，用戶需要知道發生了什麼並想要進行重試，所以這時候應用程式通常會彈出一個對話框告知用戶發生了系統錯誤，是需要重試還是退出。

嚴重錯誤

進程終止的第三個原因是由進程引起的錯誤，通常是由於程式中的錯誤所導致的。例如，執行了一條非法指令，引用不存在的記憶體，或者除數是 0 等。在有些系統比如 UNIX 中，進程可以通知作業系統，它希望自行處理某種類型的錯誤，在這類錯誤中，進程會收到訊號（中斷），而不是在這類錯誤出現時直接終止進程。

被其他進程殺死

第四個終止進程的原因是，某個進程執行系統調用告訴作業系統殺死某個進程。在 UNIX 中，這個系統調用是 kill。在 Win32 中對應的函數是 TerminateProcess（注意不是系統調用）。

進程的層次結構

在一些系統中，當一個進程創建了其他進程後，父進程和子進程就會以某種方式進行關聯。子進程它自己就會創建更多進程，從而形成一個進程層次結構。

UNIX 進程體系

在 UNIX 中，進程和它的所有子進程以及子進程的子進程共同組成一個進程組。當用戶從鍵盤中發出一個訊號後，該訊號被發送給當前與鍵盤相關的進程組中的所有成員（它們通常是在當前窗口創建的所有活動進程）。每個進程可以分別捕獲該訊號、忽略該訊號或採取默認的動作，即被訊號 kill 掉。

這裡有另一個例子，可以用來說明層次的作用，考慮 UNIX 在啟動時如何初始化自己。一個稱為 init 的特殊進程出現在啟動映像中 。當 init 進程開始運行時，它會讀取一個文件，文件會告訴它有多少個終端。然後為每個終端創建一個新進程。這些進程等待用戶登錄。如果登錄成功，該登錄進程就執行一個 shell 來等待接收用戶輸入指令，這些命令可能會啟動更多的進程，以此類推。因此，整個作業系統中所有的進程都隸屬於一個單個以 init 為根的進程樹。

Windows 進程體系

相反，Windows 中沒有進程層次的概念，Windows 中所有進程都是平等的，唯一類似於層次結構的是在創建進程的時候，父進程得到一個特別的令牌（稱為句柄），該句柄可以用來控制子進程。然而，這個令牌可能也會移交給別的作業系統，這樣就不存在層次結構了。而在 UNIX 中，進程不能剝奪其子進程的 進程權。（這樣看來，還是 Windows 比較渣）。

進程狀態

儘管每個進程是一個獨立的實體，有其自己的程式計數器和內部狀態，但是，進程之間仍然需要相互幫助。例如，一個進程的結果可以作為另一個進程的輸入，在 shell 命令中

cat chapter1 chapter2 chapter3 | grep tree

第一個進程是 cat，將三個文件級聯並輸出。第二個進程是 grep，它從輸入中選擇具有包含關鍵字 tree 的內容，根據這兩個進程的相對速度（這取決於兩個程式的相對複雜度和各自所分配到的 CPU 時間片），可能會發生下面這種情況，grep 準備就緒開始運行，但是輸入進程還沒有完成，於是必須阻塞 grep 進程，直到輸入完畢。

當一個進程開始運行時，它可能會經歷下面這幾種狀態

圖中會涉及三種狀態

  1. 運行態，運行態指的就是進程實際佔用 CPU 時間片運行時
  2. 就緒態，就緒態指的是可運行，但因為其他進程正在運行而處於就緒狀態
  3. 阻塞態，除非某種外部事件發生，否則進程不能運行

邏輯上來說，運行態和就緒態是很相似的。這兩種情況下都表示進程可運行，但是第二種情況沒有獲得 CPU 時間分片。第三種狀態與前兩種狀態不同的原因是這個進程不能運行，CPU 空閑時也不能運行。

三種狀態會涉及四種狀態間的切換，在作業系統發現進程不能繼續執行時會發生狀態1的輪轉，在某些系統中進程執行系統調用，例如 pause，來獲取一個阻塞的狀態。在其他系統中包括 UNIX，當進程從管道或特殊文件（例如終端）中讀取沒有可用的輸入時，該進程會被自動終止。

轉換 2 和轉換 3 都是由進程調度程式（作業系統的一部分）引起的，進程本身不知道調度程式的存在。轉換 2 的出現說明進程調度器認定當前進程已經運行了足夠長的時間，是時候讓其他進程運行 CPU 時間片了。當所有其他進程都運行過後，這時候該是讓第一個進程重新獲得 CPU 時間片的時候了，就會發生轉換 3。

程式調度指的是，決定哪個進程優先被運行和運行多久，這是很重要的一點。已經設計出許多演算法來嘗試平衡系統整體效率與各個流程之間的競爭需求。

當進程等待的一個外部事件發生時（如從外部輸入一些數據後），則發生轉換 4。如果此時沒有其他進程在運行，則立刻觸發轉換 3，該進程便開始運行，否則該進程會處於就緒階段，等待 CPU 空閑後再輪到它運行。

從上面的觀點引入了下面的模型

作業系統最底層的就是調度程式，在它上面有許多進程。所有關於中斷處理、啟動進程和停止進程的具體細節都隱藏在調度程式中。事實上，調度程式只是一段非常小的程式。

進程的實現

作業系統為了執行進程間的切換，會維護著一張表格，這張表就是 進程表(process table)。每個進程佔用一個進程表項。該表項包含了進程狀態的重要資訊，包括程式計數器、堆棧指針、記憶體分配狀況、所打開文件的狀態、帳號和調度資訊，以及其他在進程由運行態轉換到就緒態或阻塞態時所必須保存的資訊，從而保證該進程隨後能再次啟動，就像從未被中斷過一樣。

下面展示了一個典型系統中的關鍵欄位

第一列內容與進程管理有關，第二列內容與 存儲管理有關，第三列內容與文件管理有關。

存儲管理的 text segment 、 data segment、stack segment 更多了解見下面這篇文章

程式設計師需要了解的硬核知識之彙編語言(全)

現在我們應該對進程表有個大致的了解了，就可以在對單個 CPU 上如何運行多個順序進程的錯覺做更多的解釋。與每一 I/O 類相關聯的是一個稱作 中斷向量(interrupt vector) 的位置（靠近記憶體底部的固定區域）。它包含中斷服務程式的入口地址。假設當一個磁碟中斷髮生時，用戶進程 3 正在運行，則中斷硬體將程式計數器、程式狀態字、有時還有一個或多個暫存器壓入堆棧，電腦隨即跳轉到中斷向量所指示的地址。這就是硬體所做的事情。然後軟體就隨即接管一切剩餘的工作。

當中斷結束後，作業系統會調用一個 C 程式來處理中斷剩下的工作。在完成剩下的工作後，會使某些進程就緒，接著調用調度程式，決定隨後運行哪個進程。然後將控制權轉移給一段彙編語言程式碼，為當前的進程裝入暫存器值以及記憶體映射並啟動該進程運行，下面顯示了中斷處理和調度的過程。

  1. 硬體壓入堆棧程式計數器等
  2. 硬體從中斷向量裝入新的程式計數器
  3. 彙編語言過程保存暫存器的值
  4. 彙編語言過程設置新的堆棧
  5. C 中斷伺服器運行（典型的讀和快取寫入）
  6. 調度器決定下面哪個程式先運行
  7. C 過程返回至彙編程式碼
  8. 彙編語言過程開始運行新的當前進程

一個進程在執行過程中可能被中斷數千次，但關鍵每次中斷後，被中斷的進程都返回到與中斷髮生前完全相同的狀態。

執行緒

在傳統的作業系統中，每個進程都有一個地址空間和一個控制執行緒。事實上，這是大部分進程的定義。不過，在許多情況下，經常存在同一地址空間中運行多個控制執行緒的情形，這些執行緒就像是分離的進程。下面我們就著重探討一下什麼是執行緒

執行緒的使用

或許這個疑問也是你的疑問，為什麼要在進程的基礎上再創建一個執行緒的概念，準確的說，這其實是進程模型和執行緒模型的討論，回答這個問題，可能需要分三步來回答

  • 多執行緒之間會共享同一塊地址空間和所有可用數據的能力，這是進程所不具備的
  • 執行緒要比進程更輕量級，由於執行緒更輕，所以它比進程更容易創建，也更容易撤銷。在許多系統中，創建一個執行緒要比創建一個進程快 10 - 100 倍。
  • 第三個原因可能是性能方面的探討，如果多個執行緒都是 CPU 密集型的，那麼並不能獲得性能上的增強，但是如果存在著大量的計算和大量的 I/O 處理，擁有多個執行緒能在這些活動中彼此重疊進行，從而會加快應用程式的執行速度

多執行緒解決方案

現在考慮一個執行緒使用的例子：一個萬維網伺服器，對頁面的請求發送給伺服器，而所請求的頁面發送回客戶端。在多數 web 站點上，某些頁面較其他頁面相比有更多的訪問。例如，索尼的主頁比任何一個照相機詳情介紹頁面具有更多的訪問，Web 伺服器可以把獲得大量訪問的頁面集合保存在記憶體中，避免到磁碟去調入這些頁面，從而改善性能。這種頁面的集合稱為 高速快取(cache)，高速快取也應用在許多場合中，比如說 CPU 快取。

上面是一個 web 伺服器的組織方式，一個叫做 調度執行緒(dispatcher thread) 的執行緒從網路中讀入工作請求，在調度執行緒檢查完請求後，它會選擇一個空閑的（阻塞的）工作執行緒來處理請求，通常是將消息的指針寫入到每個執行緒關聯的特殊字中。然後調度執行緒會喚醒正在睡眠中的工作執行緒，把工作執行緒的狀態從阻塞態變為就緒態。

當工作執行緒啟動後，它會檢查請求是否在 web 頁面的高速快取中存在，這個高速快取是所有執行緒都可以訪問的。如果高速快取不存在這個 web 頁面的話，它會調用一個 read 操作從磁碟中獲取頁面並且阻塞執行緒直到磁碟操作完成。當執行緒阻塞在硬碟操作的期間，為了完成更多的工作，調度執行緒可能挑選另一個執行緒運行，也可能把另一個當前就緒的工作執行緒投入運行。

這種模型允許將伺服器編寫為順序執行緒的集合，在分派執行緒的程式中包含一個死循環，該循環用來獲得工作請求並且把請求派給工作執行緒。每個工作執行緒的程式碼包含一個從調度執行緒接收的請求，並且檢查 web 高速快取中是否存在所需頁面，如果有，直接把該頁面返回給客戶，接著工作執行緒阻塞，等待一個新請求的到達。如果沒有，工作執行緒就從磁碟調入該頁面，將該頁面返回給客戶機，然後工作執行緒阻塞，等待一個新請求。

下面是調度執行緒和工作執行緒的程式碼，這裡假設 TRUE 為常數 1 ，buf 和 page 分別是保存工作請求和 Web 頁面的相應結構。

調度執行緒的大致邏輯

while(TRUE){    get_next_request(&buf);    handoff_work(&buf);  }

工作執行緒的大致邏輯

while(TRUE){    wait_for_work(&buf);    look_for_page_in_cache(&buf,&page);    if(page_not_in_cache(&page)){      read_page_from_disk(&buf,&page);    }    return _page(&page);  }

單執行緒解決方案

現在考慮沒有多執行緒的情況下，如何編寫 Web 伺服器。我們很容易的就想像為單個執行緒了，Web 伺服器的主循環獲取請求並檢查請求，並爭取在下一個請求之前完成工作。在等待磁碟操作時，伺服器空轉，並且不處理任何到來的其他請求。結果會導致每秒中只有很少的請求被處理，所以這個例子能夠說明多執行緒提高了程式的並行性並提高了程式的性能。

狀態機解決方案

到現在為止，我們已經有了兩種解決方案，單執行緒解決方案和多執行緒解決方案，其實還有一種解決方案就是 狀態機解決方案，它的流程如下

如果目前只有一個非阻塞版本的 read 系統調用可以使用，那麼當請求到達伺服器時，這個唯一的 read 調用的執行緒會進行檢查，如果能夠從高速快取中得到響應，那麼直接返回，如果不能，則啟動一個非阻塞的磁碟操作

伺服器在表中記錄當前請求的狀態，然後進入並獲取下一個事件，緊接著下一個事件可能就是一個新工作的請求或是磁碟對先前操作的回答。如果是新工作的請求，那麼就開始處理請求。如果是磁碟的響應，就從表中取出對應的狀態資訊進行處理。對於非阻塞式磁碟 I/O 而言，這種響應一般都是訊號中斷響應。

每次伺服器從某個請求工作的狀態切換到另一個狀態時，都必須顯示的保存或者重新裝入相應的計算狀態。這裡，每個計算都有一個被保存的狀態，存在一個會發生且使得相關狀態發生改變的事件集合，我們把這類設計稱為有限狀態機(finite-state machine)，有限狀態機被廣泛的應用在電腦科學中。

這三種解決方案各有各的特性，多執行緒使得順序進程的思想得以保留下來，並且實現了並行性，但是順序進程會阻塞系統調用；單執行緒伺服器保留了阻塞系統的簡易性，但是卻放棄了性能。有限狀態機的處理方法運用了非阻塞調用和中斷，通過並行實現了高性能，但是給編程增加了困難。

模型

特性

單執行緒

無並行性，性能較差，阻塞系統調用

多執行緒

有並行性，阻塞系統調用

有限狀態機

並行性，非阻塞系統調用、中斷

經典的執行緒模型

理解進程的另一個角度是，用某種方法把相關的資源集中在一起。進程有存放程式正文和數據以及其他資源的地址空間。這些資源包括打開的文件、子進程、即將發生的定時器、訊號處理程式、帳號資訊等。把這些資訊放在進程中會比較容易管理。

另一個概念是，進程中擁有一個執行的執行緒，通常簡寫為 執行緒(thread)。執行緒會有程式計數器，用來記錄接著要執行哪一條指令；執行緒還擁有暫存器，用來保存執行緒當前正在使用的變數；執行緒還會有堆棧，用來記錄程式的執行路徑。儘管執行緒必須在某個進程中執行，但是進程和執行緒完完全全是兩個不同的概念，並且他們可以分開處理。進程用於把資源集中在一起，而執行緒則是 CPU 上調度執行的實體。

執行緒給進程模型增加了一項內容，即在同一個進程中，允許彼此之間有較大的獨立性且互不干擾。在一個進程中並行運行多個執行緒類似於在一台電腦上運行多個進程。在多個執行緒中，各個執行緒共享同一地址空間和其他資源。在多個進程中，進程共享物理記憶體、磁碟、印表機和其他資源。因為執行緒會包含有一些進程的屬性，所以執行緒被稱為輕量的進程(lightweight processes)。多執行緒(multithreading)一詞還用於描述在同一進程中多個執行緒的情況。

下圖我們可以看到三個傳統的進程，每個進程有自己的地址空間和單個控制執行緒。每個執行緒都在不同的地址空間中運行

下圖中，我們可以看到有一個進程三個執行緒的情況。每個執行緒都在相同的地址空間中運行。

執行緒不像是進程那樣具備較強的獨立性。同一個進程中的所有執行緒都會有完全一樣的地址空間，這意味著它們也共享同樣的全局變數。由於每個執行緒都可以訪問進程地址空間內每個記憶體地址，因此一個執行緒可以讀取、寫入甚至擦除另一個執行緒的堆棧。執行緒之間除了共享同一記憶體空間外，還具有如下不同的內容

上圖左邊的是同一個進程中每個執行緒共享的內容，上圖右邊是每個執行緒中的內容。也就是說左邊的列表是進程的屬性，右邊的列表是執行緒的屬性。

和進程一樣，執行緒可以處於下面這幾種狀態：運行中、阻塞、就緒和終止（進程圖中沒有畫）。正在運行的執行緒擁有 CPU 時間片並且狀態是運行中。一個被阻塞的執行緒會等待某個釋放它的事件。例如，當一個執行緒執行從鍵盤讀入數據的系統調用時，該執行緒就被阻塞直到有輸入為止。執行緒通常會被阻塞，直到它等待某個外部事件的發生或者有其他執行緒來釋放它。執行緒之間的狀態轉換和進程之間的狀態轉換是一樣的。

每個執行緒都會有自己的堆棧，如下圖所示

執行緒系統調用

進程通常會從當前的某個單執行緒開始，然後這個執行緒通過調用一個庫函數（比如 thread_create）創建新的執行緒。執行緒創建的函數會要求指定新創建執行緒的名稱。創建的執行緒通常都返回一個執行緒標識符，該標識符就是新執行緒的名字。

當一個執行緒完成工作後，可以通過調用一個函數（比如 thread_exit）來退出。緊接著執行緒消失，狀態變為終止，不能再進行調度。在某些執行緒的運行過程中，可以通過調用函數例如 thread_join ，表示一個執行緒可以等待另一個執行緒退出。這個過程阻塞調用執行緒直到等待特定的執行緒退出。在這種情況下，執行緒的創建和終止非常類似於進程的創建和終止。

另一個常見的執行緒是調用 thread_yield，它允許執行緒自動放棄 CPU 從而讓另一個執行緒運行。這樣一個調用還是很重要的，因為不同於進程，執行緒是無法利用時鐘中斷強制讓執行緒讓出 CPU 的。

POSIX 執行緒

為了使編寫可移植執行緒程式成為可能，IEEE 在 IEEE 標準 1003.1c 中定義了執行緒標準。執行緒包被定義為 Pthreads。大部分的 UNIX 系統支援它。這個標準定義了 60 多種功能調用，一一列舉不太現實，下面為你列舉了一些常用的系統調用。

POSIX執行緒（通常稱為pthreads）是一種獨立於語言而存在的執行模型，以及並行執行模型。它允許程式控制時間上重疊的多個不同的工作流程。每個工作流程都稱為一個執行緒，可以通過調用POSIX Threads API來實現對這些流程的創建和控制。可以把它理解為執行緒的標準。 POSIX Threads 的實現在許多類似且符合POSIX的作業系統上可用，例如 FreeBSD、NetBSD、OpenBSD、Linux、macOS、Android、Solaris，它在現有 Windows API 之上實現了pthread。 IEEE 是世界上最大的技術專業組織，致力於為人類的利益而發展技術。

執行緒調用

描述

pthread_create

創建一個新執行緒

pthread_exit

結束調用的執行緒

pthread_join

等待一個特定的執行緒退出

pthread_yield

釋放 CPU 來運行另外一個執行緒

pthread_attr_init

創建並初始化一個執行緒的屬性結構

pthread_attr_destory

刪除一個執行緒的屬性結構

所有的 Pthreads 都有特定的屬性，每一個都含有標識符、一組暫存器（包括程式計數器）和一組存儲在結構中的屬性。這個屬性包括堆棧大小、調度參數以及其他執行緒需要的項目。

新的執行緒會通過 pthread_create 創建，新創建的執行緒的標識符會作為函數值返回。這個調用非常像是 UNIX 中的 fork 系統調用（除了參數之外），其中執行緒標識符起著 PID 的作用，這麼做的目的是為了和其他執行緒進行區分。

當執行緒完成指派給他的工作後，會通過 pthread_exit 來終止。這個調用會停止執行緒並釋放堆棧。

一般一個執行緒在繼續運行前需要等待另一個執行緒完成它的工作並退出。可以通過 pthread_join 執行緒調用來等待別的特定執行緒的終止。而要等待執行緒的執行緒標識符作為一個參數給出。

有時會出現這種情況：一個執行緒邏輯上沒有阻塞，但感覺上它已經運行了足夠長的時間並且希望給另外一個執行緒機會去運行。這時候可以通過 pthread_yield 來完成。

下面兩個執行緒調用是處理屬性的。pthread_attr_init 建立關聯一個執行緒的屬性結構並初始化成默認值，這些值（例如優先順序）可以通過修改屬性結構的值來改變。

最後，pthread_attr_destroy 刪除一個執行緒的結構，釋放它佔用的記憶體。它不會影響調用它的執行緒，這些執行緒會一直存在。

為了更好的理解 pthread 是如何工作的，考慮下面這個例子

#include <pthread.h>  #include <stdio.h>  #include <stdlib.h>    #define NUMBER_OF_THREADS 10    void *print_hello_world(vvoid *tid){    /* 輸出執行緒的標識符，然後退出 */    printf("Hello World. Greetings from thread %dn",tid);    pthread_exit(NULL);  }    int main(int argc,char *argv[]){    /* 主程式創建 10 個執行緒，然後退出 */    pthread_t threads[NUMBER_OF_THREADS];    int status,i;      for(int i = 0;i < NUMBER_OF_THREADS;i++){      printf("Main here. Creating thread %dn",i);      status = pthread_create(&threads[i], NULL, print_hello_world, (void *)i);        if(status != 0){        printf("Oops. pthread_create returned error code %dn",status);        exit(-1);      }    }    exit(NULL);  }

主執行緒在宣布它的指責之後，循環 NUMBER_OF_THREADS 次，每次創建一個新的執行緒。如果執行緒創建失敗，會列印出一條資訊後退出。在創建完成所有的工作後，主程式退出。

執行緒實現

主要有三種實現方式

  • 在用戶空間中實現執行緒；
  • 在內核空間中實現執行緒；
  • 在用戶和內核空間中混合實現執行緒。

下面我們分開討論一下

在用戶空間中實現執行緒

第一種方法是把整個執行緒包放在用戶空間中，內核對執行緒一無所知，它不知道執行緒的存在。所有的這類實現都有同樣的通用結構

執行緒在運行時系統之上運行，運行時系統是管理執行緒過程的集合，包括前面提到的四個過程：pthread_create, pthread_exit, pthread_join 和 pthread_yield。

運行時系統(Runtime System) 也叫做運行時環境，該運行時系統提供了程式在其中運行的環境。此環境可能會解決許多問題，包括應用程式記憶體的布局，程式如何訪問變數，在過程之間傳遞參數的機制，與作業系統的介面等等。編譯器根據特定的運行時系統進行假設以生成正確的程式碼。通常，運行時系統將負責設置和管理堆棧，並且會包含諸如垃圾收集，執行緒或語言內置的其他動態的功能。

在用戶空間管理執行緒時，每個進程需要有其專用的執行緒表(thread table)，用來跟蹤該進程中的執行緒。這些表和內核中的進程表類似，不過它僅僅記錄各個執行緒的屬性，如每個執行緒的程式計數器、堆棧指針、暫存器和狀態。該執行緒表由運行時系統統一管理。當一個執行緒轉換到就緒狀態或阻塞狀態時，在該執行緒表中存放重新啟動該執行緒的所有資訊，與內核在進程表中存放的資訊完全一樣。

在用戶空間實現執行緒的優勢

在用戶空間中實現執行緒要比在內核空間中實現執行緒具有這些方面的優勢：考慮如果在執行緒完成時或者是在調用 pthread_yield 時，必要時會進程執行緒切換，然後執行緒的資訊會被保存在運行時環境所提供的執行緒表中，然後，執行緒調度程式來選擇另外一個需要運行的執行緒。保存執行緒的狀態和調度程式都是本地過程，所以啟動他們比進行內核調用效率更高。因而不需要切換到內核，也就不需要上下文切換，也不需要對記憶體高速快取進行刷新，因為執行緒調度非常便捷，因此效率比較高。

在用戶空間實現執行緒還有一個優勢就是它允許每個進程有自己訂製的調度演算法。例如在某些應用程式中，那些具有垃圾收集執行緒的應用程式（知道是誰了吧）就不用擔心自己執行緒會不會在不合適的時候停止，這是一個優勢。用戶執行緒還具有較好的可擴展性，因為內核空間中的內核執行緒需要一些表空間和堆棧空間，如果內核執行緒數量比較大，容易造成問題。

在用戶空間實現執行緒的劣勢

儘管在用戶空間實現執行緒會具有一定的性能優勢，但是劣勢還是很明顯的，你如何實現阻塞系統調用呢？假設在還沒有任何鍵盤輸入之前，一個執行緒讀取鍵盤，讓執行緒進行系統調用是不可能的，因為這會停止所有的執行緒。所以，使用執行緒的一個目標是能夠讓執行緒進行阻塞調用，並且要避免被阻塞的執行緒影響其他執行緒。

與阻塞調用類似的問題是缺頁中斷問題，實際上，電腦並不會把所有的程式都一次性的放入記憶體中，如果某個程式發生函數調用或者跳轉指令到了一條不在記憶體的指令上，就會發生頁面故障，而作業系統將到磁碟上取回這個丟失的指令，這就稱為缺頁故障。而在對所需的指令進行讀入和執行時，相關的進程就會被阻塞。如果只有一個執行緒引起頁面故障，內核由於甚至不知道有執行緒存在，通常會把整個進程阻塞直到磁碟 I/O 完成為止，儘管其他的執行緒是可以運行的。

另外一個問題是，如果一個執行緒開始運行，該執行緒所在進程中的其他執行緒都不能運行，除非第一個執行緒自願的放棄 CPU，在一個單進程內部，沒有時鐘中斷，所以不可能使用輪轉調度的方式調度執行緒。除非其他執行緒能夠以自己的意願進入運行時環境，否則調度程式沒有可以調度執行緒的機會。

在內核中實現執行緒

現在我們考慮使用內核來實現執行緒的情況，此時不再需要運行時環境了。另外，每個進程中也沒有執行緒表。相反，在內核中會有用來記錄系統中所有執行緒的執行緒表。當某個執行緒希望創建一個新執行緒或撤銷一個已有執行緒時，它會進行一個系統調用，這個系統調用通過對執行緒表的更新來完成執行緒創建或銷毀工作。

內核中的執行緒表持有每個執行緒的暫存器、狀態和其他資訊。這些資訊和用戶空間中的執行緒資訊相同，但是位置卻被放在了內核中而不是用戶空間中。另外，內核還維護了一張進程表用來跟蹤系統狀態。

所有能夠阻塞的調用都會通過系統調用的方式來實現，當一個執行緒阻塞時，內核可以進行選擇，是運行在同一個進程中的另一個執行緒（如果有就緒執行緒的話）還是運行一個另一個進程中的執行緒。但是在用戶實現中，運行時系統始終運行自己的執行緒，直到內核剝奪它的 CPU 時間片（或者沒有可運行的執行緒存在了）為止。

由於在內核中創建或者銷毀執行緒的開銷比較大，所以某些系統會採用可循環利用的方式來回收執行緒。當某個執行緒被銷毀時，就把它標誌為不可運行的狀態，但是其內部結構沒有受到影響。稍後，在必須創建一個新執行緒時，就會重新啟用舊執行緒，把它標誌為可用狀態。

如果某個進程中的執行緒造成缺頁故障後，內核很容易的就能檢查出來是否有其他可運行的執行緒，如果有的話，在等待所需要的頁面從磁碟讀入時，就選擇一個可運行的執行緒運行。這樣做的缺點是系統調用的代價比較大，所以如果執行緒的操作（創建、終止）比較多，就會帶來很大的開銷。

混合實現

結合用戶空間和內核空間的優點，設計人員採用了一種內核級執行緒的方式，然後將用戶級執行緒與某些或者全部內核執行緒多路復用起來

在這種模型中，編程人員可以自由控制用戶執行緒和內核執行緒的數量，具有很大的靈活度。採用這種方法，內核只識別內核級執行緒，並對其進行調度。其中一些內核級執行緒會被多個用戶級執行緒多路復用。

進程間通訊

進程是需要頻繁的和其他進程進行交流的。例如，在一個 shell 管道中，第一個進程的輸出必須傳遞給第二個進程，這樣沿著管道進行下去。因此，進程之間如果需要通訊的話，必須要使用一種良好的數據結構以至於不能被中斷。下面我們會一起討論有關 進程間通訊(Inter Process Communication, IPC) 的問題。

關於進程間的通訊，這裡有三個問題

  • 上面提到了第一個問題，那就是一個進程如何傳遞消息給其他進程。
  • 第二個問題是如何確保兩個或多個執行緒之間不會相互干擾。例如，兩個航空公司都試圖為不同的顧客搶購飛機上的最後一個座位。
  • 第三個問題是數據的先後順序的問題，如果進程 A 產生數據並且進程 B 列印數據。則進程 B 列印數據之前需要先等 A 產生數據後才能夠進行列印。

需要注意的是，這三個問題中的後面兩個問題同樣也適用於執行緒

第一個問題在執行緒間比較好解決，因為它們共享一個地址空間，它們具有相同的運行時環境，可以想像你在用高級語言編寫多執行緒程式碼的過程中，執行緒通訊問題是不是比較容易解決？

另外兩個問題也同樣適用於執行緒，同樣的問題可用同樣的方法來解決。我們後面會慢慢討論這三個問題，你現在腦子中大致有個印象即可。

競態條件

在一些作業系統中，協作的進程可能共享一些彼此都能讀寫的公共資源。公共資源可能在記憶體中也可能在一個共享文件。為了講清楚進程間是如何通訊的，這裡我們舉一個例子：一個後台列印程式。當一個進程需要列印某個文件時，它會將文件名放在一個特殊的後台目錄(spooler directory)中。另一個進程 列印後台進程(printer daemon) 會定期的檢查是否需要文件被列印，如果有的話，就列印並將該文件名從目錄下刪除。

假設我們的後台目錄有非常多的 槽位(slot)，編號依次為 0，1，2，…，每個槽位存放一個文件名。同時假設有兩個共享變數：out，指向下一個需要列印的文件；in，指向目錄中下個空閑的槽位。可以把這兩個文件保存在一個所有進程都能訪問的文件中，該文件的長度為兩個字。在某一時刻，0 至 3 號槽位空，4 號至 6 號槽位被佔用。在同一時刻，進程 A 和 進程 B 都決定將一個文件排隊列印，情況如下

墨菲法則(Murphy) 中說過，任何可能出錯的地方終將出錯，這句話生效時，可能發生如下情況。

進程 A 讀到 in 的值為 7，將 7 存在一個局部變數 next_free_slot 中。此時發生一次時鐘中斷，CPU 認為進程 A 已經運行了足夠長的時間，決定切換到進程 B 。進程 B 也讀取 in 的值，發現是 7，然後進程 B 將 7 寫入到自己的局部變數 next_free_slot 中，在這一時刻兩個進程都認為下一個可用槽位是 7 。

進程 B 現在繼續運行，它會將列印文件名寫入到 slot 7 中，然後把 in 的指針更改為 8 ，然後進程 B 離開去做其他的事情

現在進程 A 開始恢復運行，由於進程 A 通過檢查 next_free_slot也發現 slot 7 的槽位是空的，於是將列印文件名存入 slot 7 中，然後把 in 的值更新為 8 ，由於 slot 7 這個槽位中已經有進程 B 寫入的值，所以進程 A 的列印文件名會把進程 B 的文件覆蓋，由於印表機內部是無法發現是哪個進程更新的，它的功能比較局限，所以這時候進程 B 永遠無法列印輸出，類似這種情況，即兩個或多個執行緒同時對一共享數據進行修改，從而影響程式運行的正確性時，這種就被稱為競態條件(race condition)。調試競態條件是一種非常困難的工作，因為絕大多數情況下程式運行良好，但在極少數的情況下會發生一些無法解釋的奇怪現象。

臨界區

不僅共享資源會造成競態條件，事實上共享文件、共享記憶體也會造成競態條件、那麼該如何避免呢？或許一句話可以概括說明：禁止一個或多個進程在同一時刻對共享資源（包括共享記憶體、共享文件等）進行讀寫。換句話說，我們需要一種 互斥(mutual exclusion) 條件，這也就是說，如果一個進程在某種方式下使用共享變數和文件的話，除該進程之外的其他進程就禁止做這種事（訪問統一資源）。上面問題的糾結點在於，在進程 A 對共享變數的使用未結束之前進程 B 就使用它。在任何作業系統中，為了實現互斥操作而選用適當的原語是一個主要的設計問題，接下來我們會著重探討一下。

避免競爭問題的條件可以用一種抽象的方式去描述。大部分時間，進程都會忙於內部計算和其他不會導致競爭條件的計算。然而，有時候進程會訪問共享記憶體或文件，或者做一些能夠導致競態條件的操作。我們把對共享記憶體進行訪問的程式片段稱作 臨界區域(critical region) 或 臨界區(critical section)。如果我們能夠正確的操作，使兩個不同進程不可能同時處於臨界區，就能避免競爭條件，這也是從作業系統設計角度來進行的。

儘管上面這種設計避免了競爭條件，但是不能確保並發執行緒同時訪問共享數據的正確性和高效性。一個好的解決方案，應該包含下面四種條件

  1. 任何時候兩個進程不能同時處於臨界區
  2. 不應對 CPU 的速度和數量做任何假設
  3. 位於臨界區外的進程不得阻塞其他進程
  4. 不能使任何進程無限等待進入臨界區

從抽象的角度來看，我們通常希望進程的行為如上圖所示，在 t1 時刻，進程 A 進入臨界區，在 t2 的時刻，進程 B 嘗試進入臨界區，因為此時進程 A 正在處於臨界區中，所以進程 B 會阻塞直到 t3 時刻進程 A 離開臨界區，此時進程 B 能夠允許進入臨界區。最後，在 t4 時刻，進程 B 離開臨界區，系統恢復到沒有進程的原始狀態。

忙等互斥

下面我們會繼續探討實現互斥的各種設計，在這些方案中，當一個進程正忙於更新其關鍵區域的共享記憶體時，沒有其他進程會進入其關鍵區域，也不會造成影響。

屏蔽中斷

在單處理器系統上，最簡單的解決方案是讓每個進程在進入臨界區後立即屏蔽所有中斷，並在離開臨界區之前重新啟用它們。屏蔽中斷後，時鐘中斷也會被屏蔽。CPU 只有發生時鐘中斷或其他中斷時才會進行進程切換。這樣，在屏蔽中斷後 CPU 不會切換到其他進程。所以，一旦某個進程屏蔽中斷之後，它就可以檢查和修改共享記憶體，而不用擔心其他進程介入訪問共享數據。

這個方案可行嗎？進程進入臨界區域是由誰決定的呢？不是用戶進程嗎？當進程進入臨界區域後，用戶進程關閉中斷，如果經過一段較長時間後進程沒有離開，那麼中斷不就一直啟用不了，結果會如何？可能會造成整個系統的終止。而且如果是多處理器的話，屏蔽中斷僅僅對執行 disable 指令的 CPU 有效。其他 CPU 仍將繼續運行，並可以訪問共享記憶體。

另一方面，對內核來說，當它在執行更新變數或列表的幾條指令期間將中斷屏蔽是很方便的。例如，如果多個進程處理就緒列表中的時候發生中斷，則可能會發生競態條件的出現。所以，屏蔽中斷對於作業系統本身來說是一項很有用的技術，但是對於用戶執行緒來說，屏蔽中斷卻不是一項通用的互斥機制。

鎖變數

作為第二種嘗試，可以尋找一種軟體層面解決方案。考慮有單個共享的（鎖）變數，初始為值為 0 。當一個執行緒想要進入關鍵區域時，它首先會查看鎖的值是否為 0 ，如果鎖的值是 0 ，進程會把它設置為 1 並讓進程進入關鍵區域。如果鎖的狀態是 1，進程會等待直到鎖變數的值變為 0 。因此，鎖變數的值是 0 則意味著沒有執行緒進入關鍵區域。如果是 1 則意味著有進程在關鍵區域內。我們對上圖修改後，如下所示

這種設計方式是否正確呢？是否存在紕漏呢？假設一個進程讀出鎖變數的值並發現它為 0 ，而恰好在它將其設置為 1 之前，另一個進程調度運行，讀出鎖的變數為0 ，並將鎖的變數設置為 1 。然後第一個執行緒運行，把鎖變數的值再次設置為 1，此時，臨界區域就會有兩個進程在同時運行。

也許有的讀者可以這麼認為，在進入前檢查一次，在要離開的關鍵區域再檢查一次不就解決了嗎？實際上這種情況也是於事無補，因為在第二次檢查期間其他執行緒仍有可能修改鎖變數的值，換句話說，這種 set-before-check 不是一種 原子性 操作，所以同樣還會發生競爭條件。

嚴格輪詢法

第三種互斥的方式先拋出來一段程式碼，這裡的程式是用 C 語言編寫，之所以採用 C 是因為作業系統普遍是用 C 來編寫的（偶爾會用 C++），而基本不會使用 Java 、Modula3 或 Pascal 這樣的語言，Java 中的 native 關鍵字底層也是 C 或 C++ 編寫的源碼。對於編寫作業系統而言，需要使用 C 語言這種強大、高效、可預知和有特性的語言，而對於 Java ，它是不可預知的，因為它在關鍵時刻會用完存儲器，而在不合適的時候會調用垃圾回收機制回收記憶體。在 C 語言中，這種情況不會發生，C 語言中不會主動調用垃圾回收回收記憶體。有關 C 、C++ 、Java 和其他四種語言的比較可以參考 鏈接

進程 0 的程式碼

while(TRUE){    while(turn != 0){      /* 進入關鍵區域 */      critical_region();      turn = 1;      /* 離開關鍵區域 */      noncritical_region();    }  }

進程 1 的程式碼

while(TRUE){    while(turn != 1){      critical_region();      turn = 0;      noncritical_region();    }  }

在上面程式碼中，變數 turn，初始值為 0 ，用於記錄輪到那個進程進入臨界區，並檢查或更新共享記憶體。開始時，進程 0 檢查 turn，發現其值為 0 ，於是進入臨界區。進程 1 也發現其值為 0 ，所以在一個等待循環中不停的測試 turn，看其值何時變為 1。連續檢查一個變數直到某個值出現為止，這種方法稱為 忙等待(busywaiting)。由於這種方式浪費 CPU 時間，所以這種方式通常應該要避免。只有在有理由認為等待時間是非常短的情況下，才能夠使用忙等待。用於忙等待的鎖，稱為 自旋鎖(spinlock)。

進程 0 離開臨界區時，它將 turn 的值設置為 1，以便允許進程 1 進入其臨界區。假設進程 1 很快便離開了臨界區，則此時兩個進程都處於臨界區之外，turn 的值又被設置為 0 。現在進程 0 很快就執行完了整個循環，它退出臨界區，並將 turn 的值設置為 1。此時，turn 的值為 1，兩個進程都在其臨界區外執行。

突然，進程 0 結束了非臨界區的操作並返回到循環的開始。但是，這時它不能進入臨界區，因為 turn 的當前值為 1，此時進程 1 還忙於非臨界區的操作，進程 0 只能繼續 while 循環，直到進程 1 把 turn 的值改為 0 。這說明，在一個進程比另一個進程執行速度慢了很多的情況下，輪流進入臨界區並不是一個好的方法。

這種情況違反了前面的敘述 3 ，即 位於臨界區外的進程不得阻塞其他進程，進程 0 被一個臨界區外的進程阻塞。由於違反了第三條，所以也不能作為一個好的方案。

Peterson 解法

荷蘭數學家 T.Dekker 通過將鎖變數與警告變數相結合，最早提出了一個不需要嚴格輪換的軟體互斥演算法，關於 Dekker 的演算法，參考 鏈接

後來， G.L.Peterson 發現了一種簡單很多的互斥演算法，它的演算法如下

#define FALSE 0  #define TRUE  1  /* 進程數量 */  #define N     2    /* 現在輪到誰 */  int turn;    /* 所有值初始化為 0 (FALSE) */  int interested[N];    /* 進程是 0 或 1 */  void enter_region(int process){      /* 另一個進程號 */    int other;      /* 另一個進程 */    other = 1 - process;      /* 表示願意進入臨界區 */    interested[process] = TRUE;    turn = process;      /* 空循環 */    while(turn == process          && interested[other] == true){}    }    void leave_region(int process){      /* 表示離開臨界區 */    interested[process] == FALSE;  }

在使用共享變數時（即進入其臨界區）之前，各個進程使用各自的進程號 0 或 1 作為參數來調用 enter_region，這個函數調用在需要時將使進程等待，直到能夠安全的臨界區。在完成對共享變數的操作之後，進程將調用 leave_region 表示操作完成，並且允許其他進程進入。

現在來看看這個辦法是如何工作的。一開始，沒有任何進程處於臨界區中，現在進程 0 調用 enter_region。它通過設置數組元素和將 turn 置為 0 來表示它希望進入臨界區。由於進程 1 並不想進入臨界區，所以 enter_region 很快便返回。如果進程現在調用 enter_region，進程 1 將在此處掛起直到 interested[0] 變為 FALSE，這種情況只有在進程 0 調用 leave_region 退出臨界區時才會發生。

那麼上面討論的是順序進入的情況，現在來考慮一種兩個進程同時調用 enter_region 的情況。它們都將自己的進程存入 turn，但只有最後保存進去的進程號才有效，前一個進程的進程號因為重寫而丟失。假如進程 1 是最後存入的，則 turn 為 1 。當兩個進程都運行到 while 的時候，進程 0 將不會循環並進入臨界區，而進程 1 將會無限循環且不會進入臨界區，直到進程 0 退出位置。

TSL 指令

現在來看一種需要硬體幫助的方案。一些電腦，特別是那些設計為多處理器的電腦，都會有下面這條指令

TSL RX,LOCK

稱為 測試並加鎖(test and set lock)，它將一個記憶體字 lock 讀到暫存器 RX 中，然後在該記憶體地址上存儲一個非零值。讀寫指令能保證是一體的，不可分割的，一同執行的。在這個指令結束之前其他處理器均不允許訪問記憶體。執行 TSL 指令的 CPU 將會鎖住記憶體匯流排，用來禁止其他 CPU 在這個指令結束之前訪問記憶體。

很重要的一點是鎖住記憶體匯流排和禁用中斷不一樣。禁用中斷並不能保證一個處理器在讀寫操作之間另一個處理器對記憶體的讀寫。也就是說，在處理器 1 上屏蔽中斷對處理器 2 沒有影響。讓處理器 2 遠離記憶體直到處理器 1 完成讀寫的最好的方式就是鎖住匯流排。這需要一個特殊的硬體（基本上，一根匯流排就可以確保匯流排由鎖住它的處理器使用，而其他的處理器不能使用）

為了使用 TSL 指令，要使用一個共享變數 lock 來協調對共享記憶體的訪問。當 lock 為 0 時，任何進程都可以使用 TSL 指令將其設置為 1，並讀寫共享記憶體。當操作結束時，進程使用 move 指令將 lock 的值重新設置為 0 。

這條指令如何防止兩個進程同時進入臨界區呢？下面是解決方案

enter_region:              | 複製鎖到暫存器並將鎖設為1              TSL REGISTER,LOCK              | 鎖是 0 嗎？            CMP REGISTER,#0            | 若不是零，說明鎖已被設置，所以循環            JNE enter_region            | 返回調用者，進入臨界區            RET    leave_region:                | 在鎖中存入 0              MOVE LOCK,#0        | 返回調用者            RET

我們可以看到這個解決方案的思想和 Peterson 的思想很相似。假設存在如下共 4 指令的彙編語言程式。第一條指令將 lock 原來的值複製到暫存器中並將 lock 設置為 1 ，隨後這個原來的值和 0 做對比。如果它不是零，說明之前已經被加過鎖，則程式返回到開始並再次測試。經過一段時間後（可長可短），該值變為 0 （當前處於臨界區中的進程退出臨界區時），於是過程返回，此時已加鎖。要清除這個鎖也比較簡單，程式只需要將 0 存入 lock 即可，不需要特殊的同步指令。

現在有了一種很明確的做法，那就是進程在進入臨界區之前會先調用 enter_region，判斷是否進行循環，如果lock 的值是 1 ，進行無限循環，如果 lock 是 0，不進入循環並進入臨界區。在進程從臨界區返回時它調用 leave_region，這會把 lock 設置為 0 。與基於臨界區問題的所有解法一樣，進程必須在正確的時間調用 enter_region 和 leave_region ，解法才能奏效。

還有一個可以替換 TSL 的指令是 XCHG，它原子性的交換了兩個位置的內容，例如，一個暫存器與一個記憶體字，程式碼如下

enter_region:          | 把 1 放在記憶體器中          MOVE REGISTER,#1      | 交換暫存器和鎖變數的內容          XCHG REGISTER,LOCK      | 鎖是 0 嗎？          CMP REGISTER,#0      | 若不是 0 ，鎖已被設置，進行循環          JNE enter_region      | 返回調用者，進入臨界區          RET    leave_region:          | 在鎖中存入 0          MOVE LOCK,#0      | 返回調用者          RET

XCHG 的本質上與 TSL 的解決辦法一樣。所有的 Intel x86 CPU 在底層同步中使用 XCHG 指令。

睡眠與喚醒

上面解法中的 Peterson 、TSL 和 XCHG 解法都是正確的，但是它們都有忙等待的缺點。這些解法的本質上都是一樣的，先檢查是否能夠進入臨界區，若不允許，則該進程將原地等待，直到允許為止。

這種方式不但浪費了 CPU 時間，而且還可能引起意想不到的結果。考慮一台電腦上有兩個進程，這兩個進程具有不同的優先順序，H 是屬於優先順序比較高的進程，L 是屬於優先順序比較低的進程。進程調度的規則是不論何時只要 H 進程處於就緒態 H 就開始運行。在某一時刻，L 處於臨界區中，此時 H 變為就緒態，準備運行（例如，一條 I/O 操作結束）。現在 H 要開始忙等，但由於當 H 就緒時 L 就不會被調度，L 從來不會有機會離開關鍵區域，所以 H 會變成死循環，有時將這種情況稱為優先順序反轉問題(priority inversion problem)。

現在讓我們看一下進程間的通訊原語，這些原語在不允許它們進入關鍵區域之前會阻塞而不是浪費 CPU 時間，最簡單的是 sleep 和 wakeup。Sleep 是一個能夠造成調用者阻塞的系統調用，也就是說，這個系統調用會暫停直到其他進程喚醒它。wakeup 調用有一個參數，即要喚醒的進程。還有一種方式是 wakeup 和 sleep 都有一個參數，即 sleep 和 wakeup 需要匹配的記憶體地址。

生產者-消費者問題

作為這些私有原語的例子，讓我們考慮生產者-消費者(producer-consumer) 問題，也稱作 有界緩衝區(bounded-buffer) 問題。兩個進程共享一個公共的固定大小的緩衝區。其中一個是生產者(producer)，將資訊放入緩衝區， 另一個是消費者(consumer)，會從緩衝區中取出。也可以把這個問題一般化為 m 個生產者和 n 個消費者的問題，但是我們這裡只討論一個生產者和一個消費者的情況，這樣可以簡化實現方案。

如果緩衝隊列已滿，那麼當生產者仍想要將數據寫入緩衝區的時候，會出現問題。它的解決辦法是讓生產者睡眠，也就是阻塞生產者。等到消費者從緩衝區中取出一個或多個數據項時再喚醒它。同樣的，當消費者試圖從緩衝區中取數據，但是發現緩衝區為空時，消費者也會睡眠，阻塞。直到生產者向其中放入一個新的數據。

這個邏輯聽起來比較簡單，而且這種方式也需要一種稱作 監聽 的變數，這個變數用於監視緩衝區的數據，我們暫定為 count，如果緩衝區最多存放 N 個數據項，生產者會每次判斷 count 是否達到 N，否則生產者向緩衝區放入一個數據項並增量 count 的值。消費者的邏輯也很相似：首先測試 count 的值是否為 0 ，如果為 0 則消費者睡眠、阻塞，否則會從緩衝區取出數據並使 count 數量遞減。每個進程也會檢查檢查是否其他執行緒是否應該被喚醒，如果應該被喚醒，那麼就喚醒該執行緒。下面是生產者消費者的程式碼

/* 緩衝區 slot 槽的數量 */  #define N 100  /* 緩衝區數據的數量 */  int count = 0    // 生產者  void producer(void){    int item;      /* 無限循環 */    while(TRUE){      /* 生成下一項數據 */      item = produce_item()      /* 如果快取區是滿的，就會阻塞 */      if(count == N){        sleep();      }        /* 把當前數據放在緩衝區中 */      insert_item(item);      /* 增加緩衝區 count 的數量 */      count = count + 1;      if(count == 1){        /* 緩衝區是否為空？ */        wakeup(consumer);      }    }  }    // 消費者  void consumer(void){      int item;      /* 無限循環 */    while(TRUE){      /* 如果緩衝區是空的，就會進行阻塞 */        if(count == 0){        sleep();      }      /* 從緩衝區中取出一個數據 */         item = remove_item();      /* 將緩衝區的 count 數量減一 */      count = count - 1      /* 緩衝區滿嘛？ */      if(count == N - 1){        wakeup(producer);      }      /* 列印數據項 */      consumer_item(item);    }    }

為了在 C 語言中描述像是 sleep 和 wakeup 的系統調用，我們將以庫函數調用的形式來表示。它們不是 C 標準庫的一部分，但可以在實際具有這些系統調用的任何系統上使用。程式碼中未實現的 insert_item 和 remove_item 用來記錄將數據項放入緩衝區和從緩衝區取出數據等。

現在讓我們回到生產者-消費者問題上來，上面程式碼中會產生競爭條件，因為 count 這個變數是暴露在大眾視野下的。有可能出現下面這種情況：緩衝區為空，此時消費者剛好讀取 count 的值發現它為 0 。此時調度程式決定暫停消費者並啟動運行生產者。生產者生產了一條數據並把它放在緩衝區中，然後增加 count 的值，並注意到它的值是 1 。由於 count 為 0，消費者必須處於睡眠狀態，因此生產者調用 wakeup 來喚醒消費者。但是，消費者此時在邏輯上並沒有睡眠，所以 wakeup 訊號會丟失。當消費者下次啟動後，它會查看之前讀取的 count 值，發現它的值是 0 ，然後在此進行睡眠。不久之後生產者會填滿整個緩衝區，在這之後會阻塞，這樣一來兩個進程將永遠睡眠下去。

引起上面問題的本質是 喚醒尚未進行睡眠狀態的進程會導致喚醒丟失。如果它沒有丟失，則一切都很正常。一種快速解決上面問題的方式是增加一個喚醒等待位(wakeup waiting bit)。當一個 wakeup 訊號發送給仍在清醒的進程後，該位置為 1 。之後，當進程嘗試睡眠的時候，如果喚醒等待位為 1 ，則該位清除，而進程仍然保持清醒。

然而，當進程數量有許多的時候，這時你可以說通過增加喚醒等待位的數量來喚醒等待位，於是就有了 2、4、6、8 個喚醒等待位，但是並沒有從根本上解決問題。

訊號量

訊號量是 E.W.Dijkstra 在 1965 年提出的一種方法，它使用一個整形變數來累計喚醒次數，以供之後使用。在他的觀點中，有一個新的變數類型稱作 訊號量(semaphore)。一個訊號量的取值可以是 0 ，或任意正數。0 表示的是不需要任何喚醒，任意的正數表示的就是喚醒次數。

Dijkstra 提出了訊號量有兩個操作，現在通常使用 down 和 up（分別可以用 sleep 和 wakeup 來表示）。down 這個指令的操作會檢查值是否大於 0 。如果大於 0 ，則將其值減 1 ；若該值為 0 ，則進程將睡眠，而且此時 down 操作將會繼續執行。檢查數值、修改變數值以及可能發生的睡眠操作均為一個單一的、不可分割的 原子操作(atomic action) 完成。這會保證一旦訊號量操作開始，沒有其他的進程能夠訪問訊號量，直到操作完成或者阻塞。這種原子性對於解決同步問題和避免競爭絕對必不可少。

原子性操作指的是在電腦科學的許多其他領域中，一組相關操作全部執行而沒有中斷或根本不執行。

up 操作會使訊號量的值 + 1。如果一個或者多個進程在訊號量上睡眠，無法完成一個先前的 down 操作，則由系統選擇其中一個並允許該程完成 down 操作。因此，對一個進程在其上睡眠的訊號量執行一次 up 操作之後，該訊號量的值仍然是 0 ，但在其上睡眠的進程卻少了一個。訊號量的值增 1 和喚醒一個進程同樣也是不可分割的。不會有某個進程因執行 up 而阻塞，正如在前面的模型中不會有進程因執行 wakeup 而阻塞是一樣的道理。

用訊號量解決生產者 - 消費者問題

用訊號量解決丟失的 wakeup 問題，程式碼如下

/* 定義緩衝區槽的數量 */  #define N 100  /* 訊號量是一種特殊的 int */  typedef int semaphore;  /* 控制關鍵區域的訪問 */  semaphore mutex = 1;  /* 統計 buffer 空槽的數量 */  semaphore empty = N;  /* 統計 buffer 滿槽的數量 */  semaphore full = 0;    void producer(void){      int item;      /* TRUE 的常量是 1 */    while(TRUE){      /* 產生放在緩衝區的一些數據 */      item = producer_item();      /* 將空槽數量減 1  */      down(&empty);      /* 進入關鍵區域  */      down(&mutex);      /* 把數據放入緩衝區中 */      insert_item(item);      /* 離開臨界區 */      up(&mutex);      /* 將 buffer 滿槽數量 + 1 */      up(&full);    }  }    void consumer(void){      int item;      /* 無限循環 */    while(TRUE){      /* 快取區滿槽數量 - 1 */      down(&full);      /* 進入緩衝區 */      down(&mutex);      /* 從緩衝區取出數據 */      item = remove_item();      /* 離開臨界區 */      up(&mutex);      /* 將空槽數目 + 1 */      up(&empty);      /* 處理數據 */      consume_item(item);    }    }

為了確保訊號量能正確工作，最重要的是要採用一種不可分割的方式來實現它。通常是將 up 和 down 作為系統調用來實現。而且作業系統只需在執行以下操作時暫時屏蔽全部中斷：檢查訊號量、更新、必要時使進程睡眠。由於這些操作僅需要非常少的指令，因此中斷不會造成影響。如果使用多個 CPU，那麼訊號量應該被鎖進行保護。使用 TSL 或者 XCHG 指令用來確保同一時刻只有一個 CPU 對訊號量進行操作。

使用 TSL 或者 XCHG 來防止幾個 CPU 同時訪問一個訊號量，與生產者或消費者使用忙等待來等待其他騰出或填充緩衝區是完全不一樣的。前者的操作僅需要幾個毫秒，而生產者或消費者可能需要任意長的時間。

上面這個解決方案使用了三種訊號量：一個稱為 full，用來記錄充滿的緩衝槽數目；一個稱為 empty，記錄空的緩衝槽數目；一個稱為 mutex，用來確保生產者和消費者不會同時進入緩衝區。Full 被初始化為 0 ，empty 初始化為緩衝區中插槽數，mutex 初始化為 1。訊號量初始化為 1 並且由兩個或多個進程使用，以確保它們中同時只有一個可以進入關鍵區域的訊號被稱為 二進位訊號量(binary semaphores)。如果每個進程都在進入關鍵區域之前執行 down 操作，而在離開關鍵區域之後執行 up 操作，則可以確保相互互斥。

現在我們有了一個好的進程間原語的保證。然後我們再來看一下中斷的順序保證

  1. 硬體壓入堆棧程式計數器等
  2. 硬體從中斷向量裝入新的程式計數器
  3. 彙編語言過程保存暫存器的值
  4. 彙編語言過程設置新的堆棧
  5. C 中斷伺服器運行（典型的讀和快取寫入）
  6. 調度器決定下面哪個程式先運行
  7. C 過程返回至彙編程式碼
  8. 彙編語言過程開始運行新的當前進程

在使用訊號量的系統中，隱藏中斷的自然方法是讓每個 I/O 設備都配備一個訊號量，該訊號量最初設置為0。在 I/O 設備啟動後，中斷處理程式立刻對相關聯的訊號執行一個 down 操作，於是進程立即被阻塞。當中斷進入時，中斷處理程式隨後對相關的訊號量執行一個 up操作，能夠使已經阻止的進程恢復運行。在上面的中斷處理步驟中，其中的第 5 步 C 中斷伺服器運行 就是中斷處理程式在訊號量上執行的一個 up 操作，所以在第 6 步中，作業系統能夠執行設備驅動程式。當然，如果有幾個進程已經處於就緒狀態，調度程式可能會選擇接下來運行一個更重要的進程，我們會在後面討論調度的演算法。

上面的程式碼實際上是通過兩種不同的方式來使用訊號量的，而這兩種訊號量之間的區別也是很重要的。mutex 訊號量用於互斥。它用於確保任意時刻只有一個進程能夠對緩衝區和相關變數進行讀寫。互斥是用於避免進程混亂所必須的一種操作。

另外一個訊號量是關於同步(synchronization)的。full 和 empty 訊號量用於確保事件的發生或者不發生。在這個事例中，它們確保了緩衝區滿時生產者停止運行；緩衝區為空時消費者停止運行。這兩個訊號量的使用與 mutex 不同。

互斥量

如果不需要訊號量的計數能力時，可以使用訊號量的一個簡單版本，稱為 mutex(互斥量)。互斥量的優勢就在於在一些共享資源和一段程式碼中保持互斥。由於互斥的實現既簡單又有效，這使得互斥量在實現用戶空間執行緒包時非常有用。

互斥量是一個處於兩種狀態之一的共享變數：解鎖(unlocked) 和 加鎖(locked)。這樣，只需要一個二進位位來表示它，不過一般情況下，通常會用一個 整形(integer) 來表示。0 表示解鎖，其他所有的值表示加鎖，比 1 大的值表示加鎖的次數。

mutex 使用兩個過程，當一個執行緒（或者進程）需要訪問關鍵區域時，會調用 mutex_lock 進行加鎖。如果互斥鎖當前處於解鎖狀態（表示關鍵區域可用），則調用成功，並且調用執行緒可以自由進入關鍵區域。

另一方面，如果 mutex 互斥量已經鎖定的話，調用執行緒會阻塞直到關鍵區域內的執行緒執行完畢並且調用了 mutex_unlock 。如果多個執行緒在 mutex 互斥量上阻塞，將隨機選擇一個執行緒並允許它獲得鎖。

由於 mutex 互斥量非常簡單，所以只要有 TSL 或者是 XCHG 指令，就可以很容易地在用戶空間實現它們。用於用戶級執行緒包的 mutex_lock 和 mutex_unlock 程式碼如下，XCHG 的本質也一樣。

mutex_lock:              | 將互斥訊號量複製到暫存器，並將互斥訊號量置為1              TSL REGISTER,MUTEX        | 互斥訊號量是 0 嗎？              CMP REGISTER,#0        | 如果互斥訊號量為0，它被解鎖，所以返回              JZE ok        | 互斥訊號正在使用；調度其他執行緒              CALL thread_yield        | 再試一次              JMP mutex_lock        | 返回調用者，進入臨界區  ok:     RET    mutex_unlcok:              | 將 mutex 置為 0              MOVE MUTEX,#0        | 返回調用者              RET

mutex_lock 的程式碼和上面 enter_region 的程式碼很相似，我們可以對比著看一下

上面程式碼最大的區別你看出來了嗎？

  • 根據上面我們對 TSL 的分析，我們知道，如果 TSL 判斷沒有進入臨界區的進程會進行無限循環獲取鎖，而在 TSL 的處理中，如果 mutex 正在使用，那麼就調度其他執行緒進行處理。所以上面最大的區別其實就是在判斷 mutex/TSL 之後的處理。
  • 在（用戶）執行緒中，情況有所不同，因為沒有時鐘來停止運行時間過長的執行緒。結果是通過忙等待的方式來試圖獲得鎖的執行緒將永遠循環下去，決不會得到鎖，因為這個運行的執行緒不會讓其他執行緒運行從而釋放鎖，其他執行緒根本沒有獲得鎖的機會。在後者獲取鎖失敗時，它會調用 thread_yield 將 CPU 放棄給另外一個執行緒。結果就不會進行忙等待。在該執行緒下次運行時，它再一次對鎖進行測試。

上面就是 enter_region 和 mutex_lock 的差別所在。由於 thread_yield 僅僅是一個用戶空間的執行緒調度，所以它的運行非常快捷。這樣，mutex_lock 和 mutex_unlock 都不需要任何內核調用。通過使用這些過程，用戶執行緒完全可以實現在用戶空間中的同步，這個過程僅僅需要少量的同步。

我們上面描述的互斥量其實是一套調用框架中的指令。從軟體角度來說，總是需要更多的特性和同步原語。例如，有時執行緒包提供一個調用 mutex_trylock，這個調用嘗試獲取鎖或者返回錯誤碼，但是不會進行加鎖操作。這就給了調用執行緒一個靈活性，以決定下一步做什麼，是使用替代方法還是等候下去。

Futexes

隨著並行的增加，有效的同步(synchronization)和鎖定(locking) 對於性能來說是非常重要的。如果進程等待時間很短，那麼自旋鎖(Spin lock) 是非常有效；但是如果等待時間比較長，那麼這會浪費 CPU 周期。如果進程很多，那麼阻塞此進程，並僅當鎖被釋放的時候讓內核解除阻塞是更有效的方式。不幸的是，這種方式也會導致另外的問題：它可以在進程競爭頻繁的時候運行良好，但是在競爭不是很激烈的情況下內核切換的消耗會非常大，而且更困難的是，預測鎖的競爭數量更不容易。

有一種有趣的解決方案是把兩者的優點結合起來，提出一種新的思想，稱為 futex，或者是 快速用戶空間互斥(fast user space mutex)，是不是聽起來很有意思？

futex 是 Linux 中的特性實現了基本的鎖定（很像是互斥鎖）而且避免了陷入內核中，因為內核的切換的開銷非常大，這樣做可以大大提高性能。futex 由兩部分組成：內核服務和用戶庫。內核服務提供了了一個 等待隊列(wait queue) 允許多個進程在鎖上排隊等待。除非內核明確的對他們解除阻塞，否則它們不會運行。

對於一個進程來說，把它放到等待隊列需要昂貴的系統調用，這種方式應該被避免。在沒有競爭的情況下，futex 可以直接在用戶空間中工作。這些進程共享一個 32 位整數(integer) 作為公共鎖變數。假設鎖的初始化為 1，我們認為這時鎖已經被釋放了。執行緒通過執行原子性的操作減少並測試(decrement and test) 來搶佔鎖。decrement and set 是 Linux 中的原子功能，由包裹在 C 函數中的內聯彙編組成，並在頭文件中進行定義。下一步，執行緒會檢查結果來查看鎖是否已經被釋放。如果鎖現在不是鎖定狀態，那麼剛好我們的執行緒可以成功搶佔該鎖。然而，如果鎖被其他執行緒持有，搶佔鎖的執行緒不得不等待。在這種情況下，futex 庫不會自旋，但是會使用一個系統調用來把執行緒放在內核中的等待隊列中。這樣一來，切換到內核的開銷已經是合情合理的了，因為執行緒可以在任何時候阻塞。當執行緒完成了鎖的工作時，它會使用原子性的 增加並測試(increment and test) 釋放鎖，並檢查結果以查看內核等待隊列上是否仍阻止任何進程。如果有的話，它會通知內核可以對等待隊列中的一個或多個進程解除阻塞。如果沒有鎖競爭，內核則不需要參與競爭。

Pthreads 中的互斥量

Pthreads 提供了一些功能用來同步執行緒。最基本的機制是使用互斥量變數，可以鎖定和解鎖，用來保護每個關鍵區域。希望進入關鍵區域的執行緒首先要嘗試獲取 mutex。如果 mutex 沒有加鎖，執行緒能夠馬上進入並且互斥量能夠自動鎖定，從而阻止其他執行緒進入。如果 mutex 已經加鎖，調用執行緒會阻塞，直到 mutex 解鎖。如果多個執行緒在相同的互斥量上等待，當互斥量解鎖時，只有一個執行緒能夠進入並且重新加鎖。這些鎖並不是必須的，程式設計師需要正確使用它們。

下面是與互斥量有關的函數調用

像我們想像中的一樣，mutex 能夠被創建和銷毀，扮演這兩個角色的分別是 Phread_mutex_init 和 Pthread_mutex_destroy。mutex 也可以通過 Pthread_mutex_lock 來進行加鎖，如果互斥量已經加鎖，則會阻塞調用者。還有一個調用Pthread_mutex_trylock 用來嘗試對執行緒加鎖，當 mutex 已經被加鎖時，會返回一個錯誤程式碼而不是阻塞調用者。這個調用允許執行緒有效的進行忙等。最後，Pthread_mutex_unlock 會對 mutex 解鎖並且釋放一個正在等待的執行緒。

除了互斥量以外，Pthreads 還提供了第二種同步機制： 條件變數(condition variables) 。mutex 可以很好的允許或阻止對關鍵區域的訪問。條件變數允許執行緒由於未滿足某些條件而阻塞。絕大多數情況下這兩種方法是一起使用的。下面我們進一步來研究執行緒、互斥量、條件變數之間的關聯。

下面再來重新認識一下生產者和消費者問題：一個執行緒將東西放在一個緩衝區內，由另一個執行緒將它們取出。如果生產者發現緩衝區沒有空槽可以使用了，生產者執行緒會阻塞起來直到有一個執行緒可以使用。生產者使用 mutex 來進行原子性檢查從而不受其他執行緒干擾。但是當發現緩衝區已經滿了以後，生產者需要一種方法來阻塞自己並在以後被喚醒。這便是條件變數做的工作。

下面是一些與條件變數有關的最重要的 pthread 調用

上表中給出了一些調用用來創建和銷毀條件變數。條件變數上的主要屬性是 Pthread_cond_wait 和 Pthread_cond_signal。前者阻塞調用執行緒，直到其他執行緒發出訊號為止（使用後者調用）。阻塞的執行緒通常需要等待喚醒的訊號以此來釋放資源或者執行某些其他活動。只有這樣阻塞的執行緒才能繼續工作。條件變數允許等待與阻塞原子性的進程。Pthread_cond_broadcast 用來喚醒多個阻塞的、需要等待訊號喚醒的執行緒。

需要注意的是，條件變數（不像是訊號量）不會存在於記憶體中。如果將一個訊號量傳遞給一個沒有執行緒等待的條件變數，那麼這個訊號就會丟失，這個需要注意

下面是一個使用互斥量和條件變數的例子

#include <stdio.h>  #include <pthread.h>    /* 需要生產的數量 */  #define MAX 1000000000  pthread_mutex_t the_mutex;  /* 使用訊號量 */  pthread_cond_t condc,condp;  int buffer = 0;    /* 生產數據 */  void *producer(void *ptr){      int i;      for(int i = 0;i <= MAX;i++){      /* 緩衝區獨佔訪問，也就是使用 mutex 獲取鎖 */      pthread_mutex_lock(&the_mutex);      while(buffer != 0){        pthread_cond_wait(&condp,&the_mutex);      }      /* 把他們放在緩衝區中 */      buffer = i;      /* 喚醒消費者 */      pthread_cond_signal(&condc);      /* 釋放緩衝區 */      pthread_mutex_unlock(&the_mutex);    }    pthread_exit(0);    }    /* 消費數據 */  void *consumer(void *ptr){      int i;      for(int i = 0;i <= MAX;i++){      /* 緩衝區獨佔訪問，也就是使用 mutex 獲取鎖 */      pthread_mutex_lock(&the_mutex);      while(buffer == 0){        pthread_cond_wait(&condc,&the_mutex);      }      /* 把他們從緩衝區中取出 */      buffer = 0;      /* 喚醒生產者 */      pthread_cond_signal(&condp);      /* 釋放緩衝區 */      pthread_mutex_unlock(&the_mutex);    }    pthread_exit(0);    }

管程

為了能夠編寫更加準確無誤的程式，Brinch Hansen 和 Hoare 提出了一個更高級的同步原語叫做 管程(monitor)。他們兩個人的提案略有不同，通過下面的描述你就可以知道。管程是程式、變數和數據結構等組成的一個集合，它們組成一個特殊的模組或者包。進程可以在任何需要的時候調用管程中的程式，但是它們不能從管程外部訪問數據結構和程式。下面展示了一種抽象的，類似 Pascal 語言展示的簡潔的管程。不能用 C 語言進行描述，因為管程是語言概念而 C 語言並不支援管程。

monitor example      integer i;      condition c;        procedure producer();    ...      end;        procedure consumer();      .      end;  end monitor;

管程有一個很重要的特性，即在任何時候管程中只能有一個活躍的進程，這一特性使管程能夠很方便的實現互斥操作。管程是程式語言的特性，所以編譯器知道它們的特殊性，因此可以採用與其他過程調用不同的方法來處理對管程的調用。通常情況下，當進程調用管程中的程式時，該程式的前幾條指令會檢查管程中是否有其他活躍的進程。如果有的話，調用進程將被掛起，直到另一個進程離開管程才將其喚醒。如果沒有活躍進程在使用管程，那麼該調用進程才可以進入。

進入管程中的互斥由編譯器負責，但是一種通用做法是使用 互斥量(mutex) 和 二進位訊號量(binary semaphore)。由於編譯器而不是程式設計師在操作，因此出錯的幾率會大大降低。在任何時候，編寫管程的程式設計師都無需關心編譯器是如何處理的。他只需要知道將所有的臨界區轉換成為管程過程即可。絕不會有兩個進程同時執行臨界區中的程式碼。

即使管程提供了一種簡單的方式來實現互斥，但在我們看來，這還不夠。因為我們還需要一種在進程無法執行被阻塞。在生產者-消費者問題中，很容易將針對緩衝區滿和緩衝區空的測試放在管程程式中，但是生產者在發現緩衝區滿的時候該如何阻塞呢？

解決的辦法是引入條件變數(condition variables) 以及相關的兩個操作 wait 和 signal。當一個管程程式發現它不能運行時（例如，生產者發現緩衝區已滿），它會在某個條件變數（如 full）上執行 wait 操作。這個操作造成調用進程阻塞，並且還將另一個以前等在管程之外的進程調入管程。在前面的 pthread 中我們已經探討過條件變數的實現細節了。另一個進程，比如消費者可以通過執行 signal 來喚醒阻塞的調用進程。

Brinch Hansen 和 Hoare 在對進程喚醒上有所不同，Hoare 建議讓新喚醒的進程繼續運行；而掛起另外的進程。而 Brinch Hansen 建議讓執行 signal 的進程必須退出管程，這裡我們採用 Brinch Hansen 的建議，因為它在概念上更簡單，並且更容易實現。

如果在一個條件變數上有若干進程都在等待，則在對該條件執行 signal 操作後，系統調度程式只能選擇其中一個進程恢復運行。

順便提一下，這裡還有上面兩位教授沒有提出的第三種方式，它的理論是讓執行 signal 的進程繼續運行，等待這個進程退出管程時，其他進程才能進入管程。

條件變數不是計數器。條件變數也不能像訊號量那樣積累訊號以便以後使用。所以，如果向一個條件變數發送訊號，但是該條件變數上沒有等待進程，那麼訊號將會丟失。也就是說，wait 操作必須在 signal 之前執行。

下面是一個使用 Pascal 語言通過管程實現的生產者-消費者問題的解法

monitor ProducerConsumer          condition full,empty;          integer count;            procedure insert(item:integer);          begin                  if count = N then wait(full);                  insert_item(item);                  count := count + 1;                  if count = 1 then signal(empty);          end;            function remove:integer;          begin                  if count = 0 then wait(empty);                  remove = remove_item;                  count := count - 1;                  if count = N - 1 then signal(full);          end;            count := 0;  end monitor;    procedure producer;  begin              while true do        begin                    item = produce_item;                    ProducerConsumer.insert(item);        end  end;    procedure consumer;  begin              while true do              begin                          item = ProducerConsumer.remove;                          consume_item(item);              end  end;

讀者可能覺得 wait 和 signal 操作看起來像是前面提到的 sleep 和 wakeup ，而且後者存在嚴重的競爭條件。它們確實很像，但是有個關鍵的區別：sleep 和 wakeup 之所以會失敗是因為當一個進程想睡眠時，另一個進程試圖去喚醒它。使用管程則不會發生這種情況。管程程式的自動互斥保證了這一點，如果管程過程中的生產者發現緩衝區已滿，它將能夠完成 wait 操作而不用擔心調度程式可能會在 wait 完成之前切換到消費者。甚至，在 wait 執行完成並且把生產者標誌為不可運行之前，是不會允許消費者進入管程的。

儘管類 Pascal 是一種想像的語言，但還是有一些真正的程式語言支援，比如 Java （終於輪到大 Java 出場了），Java 是能夠支援管程的，它是一種 面向對象的語言，支援用戶級執行緒，還允許將方法劃分為類。只要將關鍵字 synchronized 關鍵字加到方法中即可。Java 能夠保證一旦某個執行緒執行該方法，就不允許其他執行緒執行該對象中的任何 synchronized 方法。沒有關鍵字 synchronized ，就不能保證沒有交叉執行。

下面是 Java 使用管程解決的生產者-消費者問題

public class ProducerConsumer {    // 定義緩衝區大小的長度    static final int N = 100;    // 初始化一個新的生產者執行緒    static Producer p = new Producer();    // 初始化一個新的消費者執行緒    static Consumer c = new Consumer();    // 初始化一個管程    static Our_monitor mon = new Our_monitor();      // run 包含了執行緒程式碼    static class Producer extends Thread{      public void run(){        int item;        // 生產者循環        while(true){          item = produce_item();          mon.insert(item);        }      }      // 生產程式碼      private int produce_item(){...}    }      // run 包含了執行緒程式碼    static class consumer extends Thread {      public void run( ) {             int item;        while(true){          item = mon.remove();                  consume_item(item);        }      }      // 消費程式碼      private int produce_item(){...}    }      // 這是管程    static class Our_monitor {      private int buffer[] = new int[N];      // 計數器和索引      private int count = 0,lo = 0,hi = 0;        private synchronized void insert(int val){        if(count == N){          // 如果緩衝區是滿的，則進入休眠          go_to_sleep();        }        // 向緩衝區插入內容              buffer[hi] = val;        // 找到下一個槽的為止        hi = (hi + 1) % N;        // 緩衝區中的數目自增 1        count = count + 1;        if(count == 1){          // 如果消費者睡眠，則喚醒          notify();        }      }        private synchronized void remove(int val){        int val;        if(count == 0){          // 緩衝區是空的，進入休眠          go_to_sleep();        }        // 從緩衝區取出數據        val = buffer[lo];        // 設置待取出數據項的槽        lo = (lo + 1) % N;        // 緩衝區中的數據項數目減 1        count = count - 1;        if(count = N - 1){          // 如果生產者睡眠，喚醒它          notify();        }        return val;      }        private void go_to_sleep() {        try{          wait( );        }catch(Interr uptedExceptionexc) {};      }    }    }

上面的程式碼中主要設計四個類，外部類(outer class) ProducerConsumer 創建並啟動兩個執行緒，p 和 c。第二個類和第三個類 Producer 和 Consumer 分別包含生產者和消費者程式碼。最後，Our_monitor 是管程，它有兩個同步執行緒，用於在共享緩衝區中插入和取出數據。

在前面的所有例子中，生產者和消費者執行緒在功能上與它們是相同的。生產者有一個無限循環，該無限循環產生數據並將數據放入公共緩衝區中；消費者也有一個等價的無限循環，該無限循環用於從緩衝區取出數據並完成一系列工作。

程式中比較耐人尋味的就是 Our_monitor 了，它包含緩衝區、管理變數以及兩個同步方法。當生產者在 insert 內活動時，它保證消費者不能在 remove 方法中運行，從而保證更新變數以及緩衝區的安全性，並且不用擔心競爭條件。變數 count 記錄在緩衝區中數據的數量。變數 lo 是緩衝區槽的序號，指出將要取出的下一個數據項。類似地，hi 是緩衝區中下一個要放入的數據項序號。允許 lo = hi，含義是在緩衝區中有 0 個或 N 個數據。

Java 中的同步方法與其他經典管程有本質差別：Java 沒有內嵌的條件變數。然而，Java 提供了 wait 和 notify 分別與 sleep 和 wakeup 等價。

通過臨界區自動的互斥，管程比訊號量更容易保證並行編程的正確性。但是管程也有缺點，我們前面說到過管程是一個程式語言的概念，編譯器必須要識別管程並用某種方式對其互斥作出保證。C、Pascal 以及大多數其他程式語言都沒有管程，所以不能依靠編譯器來遵守互斥規則。

與管程和訊號量有關的另一個問題是，這些機制都是設計用來解決訪問共享記憶體的一個或多個 CPU 上的互斥問題的。通過將訊號量放在共享記憶體中並用 TSL 或 XCHG 指令來保護它們，可以避免競爭。但是如果是在分散式系統中，可能同時具有多個 CPU 的情況，並且每個 CPU 都有自己的私有記憶體呢，它們通過網路相連，那麼這些原語將會失效。因為訊號量太低級了，而管程在少數幾種程式語言之外無法使用，所以還需要其他方法。

消息傳遞

上面提到的其他方法就是 消息傳遞(messaage passing)。這種進程間通訊的方法使用兩個原語 send 和 receive ，它們像訊號量而不像管程，是系統調用而不是語言級別。示例如下

send(destination, &message);    receive(source, &message);

send 方法用於向一個給定的目標發送一條消息，receive 從一個給定的源接受一條消息。如果沒有消息，接受者可能被阻塞，直到接受一條消息或者帶著錯誤碼返回。

消息傳遞系統的設計要點

消息傳遞系統現在面臨著許多訊號量和管程所未涉及的問題和設計難點，尤其對那些在網路中不同機器上的通訊狀況。例如，消息有可能被網路丟失。為了防止消息丟失，發送方和接收方可以達成一致：一旦接受到消息後，接收方馬上回送一條特殊的 確認(acknowledgement) 消息。如果發送方在一段時間間隔內未收到確認，則重發消息。

現在考慮消息本身被正確接收，而返回給發送著的確認消息丟失的情況。發送者將重發消息，這樣接受者將收到兩次相同的消息。

對於接收者來說，如何區分新的消息和一條重發的老消息是非常重要的。通常採用在每條原始消息中嵌入一個連續的序號來解決此問題。如果接受者收到一條消息，它具有與前面某一條消息一樣的序號，就知道這條消息是重複的，可以忽略。

消息系統還必須處理如何命名進程的問題，以便在發送或接收調用中清晰的指明進程。身份驗證(authentication) 也是一個問題，比如客戶端怎麼知道它是在與一個真正的文件伺服器通訊，從發送方到接收方的資訊有可能被中間人所篡改。

用消息傳遞解決生產者-消費者問題

現在我們考慮如何使用消息傳遞來解決生產者-消費者問題，而不是共享快取。下面是一種解決方式

/* buffer 中槽的數量 */  #define N 100    void producer(void){      int item;    /* buffer 中槽的數量 */    message m;      while(TRUE){      /* 生成放入緩衝區的數據 */      item = produce_item();      /* 等待消費者發送空緩衝區 */      receive(consumer,&m);      /* 建立一個待發送的消息 */      build_message(&m,item);      /* 發送給消費者 */      send(consumer,&m);    }    }    void consumer(void){      int item,i;    message m;      /* 循環N次 */    for(int i = 0;i < N;i++){      /* 發送N個緩衝區 */      send(producer,&m);    }    while(TRUE){      /* 接受包含數據的消息 */      receive(producer,&m);      /* 將數據從消息中提取出來 */        item = extract_item(&m);      /* 將空緩衝區發送回生產者 */      send(producer,&m);      /* 處理數據 */      consume_item(item);    }    }

假設所有的消息都有相同的大小，並且在尚未接受到發出的消息時，由作業系統自動進行緩衝。在該解決方案中共使用 N 條消息，這就類似於一塊共享記憶體緩衝區的 N 個槽。消費者首先將 N 條空消息發送給生產者。當生產者向消費者傳遞一個數據項時，它取走一條空消息並返回一條填充了內容的消息。通過這種方式，系統中總的消息數量保持不變，所以消息都可以存放在事先確定數量的記憶體中。

如果生產者的速度要比消費者快，則所有的消息最終都將被填滿，等待消費者，生產者將被阻塞，等待返回一條空消息。如果消費者速度快，那麼情況將正相反：所有的消息均為空，等待生產者來填充，消費者將被阻塞，以等待一條填充過的消息。

消息傳遞的方式有許多變體，下面先介紹如何對消息進行 編址。

  • 一種方法是為每個進程分配一個唯一的地址，讓消息按進程的地址編址。
  • 另一種方式是引入一個新的數據結構，稱為 信箱(mailbox)，信箱是一個用來對一定的數據進行緩衝的數據結構，信箱中消息的設置方法也有多種，典型的方法是在信箱創建時確定消息的數量。在使用信箱時，在 send 和 receive 調用的地址參數就是信箱的地址，而不是進程的地址。當一個進程試圖向一個滿的信箱發送消息時，它將被掛起，直到信箱中有消息被取走，從而為新的消息騰出地址空間。

屏障

最後一個同步機制是準備用於進程組而不是進程間的生產者-消費者情況的。在某些應用中劃分了若干階段，並且規定，除非所有的進程都就緒準備著手下一個階段，否則任何進程都不能進入下一個階段，可以通過在每個階段的結尾安裝一個 屏障(barrier) 來實現這種行為。當一個進程到達屏障時，它會被屏障所攔截，直到所有的屏障都到達為止。屏障可用於一組進程同步，如下圖所示

在上圖中我們可以看到，有四個進程接近屏障，這意味著每個進程都在進行運算，但是還沒有到達每個階段的結尾。過了一段時間後，A、B、D 三個進程都到達了屏障，各自的進程被掛起，但此時還不能進入下一個階段呢，因為進程 B 還沒有執行完畢。結果，當最後一個 C 到達屏障後，這個進程組才能夠進入下一個階段。

避免鎖：讀-複製-更新

最快的鎖是根本沒有鎖。問題在於沒有鎖的情況下，我們是否允許對共享數據結構的並發讀寫進行訪問。答案當然是不可以。假設進程 A 正在對一個數字數組進行排序，而進程 B 正在計算其平均值，而此時你進行 A 的移動，會導致 B 會多次讀到重複值，而某些值根本沒有遇到過。

然而，在某些情況下，我們可以允許寫操作來更新數據結構，即便還有其他的進程正在使用。竅門在於確保每個讀操作要麼讀取舊的版本，要麼讀取新的版本，例如下面的樹

上面的樹中，讀操作從根部到葉子遍歷整個樹。加入一個新節點 X 後，為了實現這一操作，我們要讓這個節點在樹中可見之前使它"恰好正確"：我們對節點 X 中的所有值進行初始化，包括它的子節點指針。然後通過原子寫操作，使 X 稱為 A 的子節點。所有的讀操作都不會讀到前後不一致的版本

在上面的圖中，我們接著移除 B 和 D。首先，將 A 的左子節點指針指向 C 。所有原本在 A 中的讀操作將會後續讀到節點 C ，而永遠不會讀到 B 和 D。也就是說，它們將只會讀取到新版數據。同樣，所有當前在 B 和 D 中的讀操作將繼續按照原始的數據結構指針並且讀取舊版數據。所有操作均能正確運行，我們不需要鎖住任何東西。而不需要鎖住數據就能夠移除 B 和 D 的主要原因就是 讀-複製-更新(Ready-Copy-Update,RCU)，將更新過程中的移除和再分配過程分離開。

調度

當一個電腦是多道程式設計系統時，會頻繁的有很多進程或者執行緒來同時競爭 CPU 時間片。當兩個或兩個以上的進程/執行緒處於就緒狀態時，就會發生這種情況。如果只有一個 CPU 可用，那麼必須選擇接下來哪個進程/執行緒可以運行。作業系統中有一個叫做 調度程式(scheduler) 的角色存在，它就是做這件事兒的，該程式使用的演算法叫做 調度演算法(scheduling algorithm) 。

儘管有一些不同，但許多適用於進程調度的處理方法同樣也適用於執行緒調度。當內核管理執行緒的時候，調度通常會以執行緒級別發生，很少或者根本不會考慮執行緒屬於哪個進程。下面我們會首先專註於進程和執行緒的調度問題，然後會明確的介紹執行緒調度以及它產生的問題。

調度介紹

讓我們回到早期以磁帶上的卡片作為輸入的批處理系統的時代，那時候的調度演算法非常簡單：依次運行磁帶上的每一個作業。對於多道程式設計系統，會複雜一些，因為通常會有多個用戶在等待服務。一些大型機仍然將 批處理和 分時服務結合使用，需要調度程式決定下一個運行的是一個批處理作業還是終端上的用戶。由於在這些機器中 CPU 是稀缺資源，所以好的調度程式可以在提高性能和用戶的滿意度方面取得很大的成果。

進程行為

幾乎所有的進程（磁碟或網路）I/O 請求和計算都是交替運行的

如上圖所示，CPU 不停頓的運行一段時間，然後發出一個系統調用等待 I/O 讀寫文件。完成系統調用後，CPU 又開始計算，直到它需要讀更多的數據或者寫入更多的數據為止。當一個進程等待外部設備完成工作而被阻塞時，才是 I/O 活動。

上面 a 是 CPU 密集型進程；b 是 I/O 密集型進程進程，a 因為在計算的時間上花費時間更長，因此稱為計算密集型(compute-bound) 或者 CPU 密集型(CPU-bound)，b 因為I/O 發生頻率比較快因此稱為 I/O 密集型(I/O-bound)。計算密集型進程有較長的 CPU 集中使用和較小頻度的 I/O 等待。I/O 密集型進程有較短的 CPU 使用時間和較頻繁的 I/O 等待。注意到上面兩種進程的區分關鍵在於 CPU 的時間佔用而不是 I/O 的時間佔用。I/O 密集型的原因是因為它們沒有在 I/O 之間花費更多的計算、而不是 I/O 請求時間特別長。無論數據到達後需要花費多少時間，它們都需要花費相同的時間來發出讀取磁碟塊的硬體請求。

值得注意的是，隨著 CPU 的速度越來越快，更多的進程傾向於 I/O 密集型。這種情況出現的原因是 CPU 速度的提升要遠遠高於硬碟。這種情況導致的結果是，未來對 I/O 密集型進程的調度處理似乎更為重要。這裡的基本思想是，如果需要運行 I/O 密集型進程，那麼就應該讓它儘快得到機會，以便發出磁碟請求並保持磁碟始終忙碌。

何時調度

第一個和調度有關的問題是何時進行調度決策。存在著需要調度處理的各種情形。首先，在創建一個新進程後，需要決定是運行父進程還是子進程。因為二者的進程都處於就緒態下，這是正常的調度決策，可以任意選擇，也就是說，調度程式可以任意的選擇子進程或父進程開始運行。

第二，在進程退出時需要作出調度決定。因為此進程不再運行（因為它將不再存在），因此必須從就緒進程中選擇其他進程運行。如果沒有進程處於就緒態，系統提供的空閑進程通常會運行

什麼是空閑進程

空閑進程(system-supplied idle process) 是 Microsoft 公司 windows 作業系統帶有的系統進程，該進程是在各個處理器上運行的單個執行緒，它唯一的任務是在系統沒有處理其他執行緒時佔用處理器時間。System Idle Process 並不是一個真正的進程，它是核心虛擬出來的，多任務作業系統都存在。在沒有可用的進程時，系統處於空運行狀態，此時就是System Idle Process 在正在運行。你可以簡單的理解成，它代表的是 CPU 的空閑狀態，數值越大代表處理器越空閑，可以通過 Windows 任務管理器查看 Windows 中的 CPU 利用率

第三種情況是，當進程阻塞在 I/O 、訊號量或其他原因時，必須選擇另外一個進程來運行。有時，阻塞的原因會成為選擇進程運行的關鍵因素。例如，如果 A 是一個重要進程，並且它正在等待 B 退出關鍵區域，讓 B 退出關鍵區域從而使 A 得以運行。但是調度程式一般不會對這種情況進行考量。

第四點，當 I/O 中斷髮生時，可以做出調度決策。如果中斷來自 I/O 設備，而 I/O 設備已經完成了其工作，那麼那些等待 I/O 的進程現在可以繼續運行。由調度程式來決定是否準備運行新的進程還是重新運行已經中斷的進程。

如果硬體時鐘以 50 或 60 Hz 或其他頻率提供周期性中斷，可以在每個時鐘中斷或第 k 個時鐘中斷處做出調度決策。根據如何處理時鐘中斷可以把調度演算法可以分為兩類。非搶佔式(nonpreemptive) 調度演算法挑選一個進程，讓該進程運行直到被阻塞（阻塞在 I/O 上或等待另一個進程），或者直到該進程自動釋放 CPU。即使該進程運行了若干個小時後，它也不會被強制掛起。這樣會在時鐘中斷髮生時不會進行調度。在處理完時鐘中斷後，如果沒有更高優先順序的進程等待，則被中斷的進程會繼續執行。

另外一種情況是 搶佔式 調度演算法，它會選擇一個進程，並使其在最大固定時間內運行。如果在時間間隔結束後仍在運行，這個進程會被掛起，調度程式會選擇其他進程來運行（前提是存在就緒進程）。進行搶佔式調度需要在時間間隔結束時發生時鐘中斷，以將 CPU 的控制權交還給調度程式。如果沒有可用的時鐘，那麼非搶佔式就是唯一的選擇。

調度演算法的分類

毫無疑問，不同的環境下需要不同的調度演算法。之所以出現這種情況，是因為不同的應用程式和不同的作業系統有不同的目標。也就是說，在不同的系統中，調度程式的優化也是不同的。這裡有必要劃分出三種環境

  • 批處理(Batch)
  • 互動式(Interactive)
  • 實時(Real time)

批處理系統廣泛應用於商業領域，比如用來處理工資單、存貨清單、賬目收入、賬目支出、利息計算、索賠處理和其他周期性作業。在批處理系統中，一般會選擇使用非搶佔式演算法或者周期性比較長的搶佔式演算法。這種方法可以減少執行緒切換因此能夠提升性能。

在互動式用戶環境中，為了避免一個進程霸佔 CPU 拒絕為其他進程服務，所以需要搶佔式演算法。即使沒有進程有意要一直運行下去，但是，由於某個進程出現錯誤也有可能無限期的排斥其他所有進程。為了避免這種情況，搶佔式也是必須的。伺服器也屬於此類別，因為它們通常為多個（遠程）用戶提供服務，而這些用戶都非常著急。電腦用戶總是很忙。

在實時系統中，搶佔有時是不需要的，因為進程知道自己可能運行不了很長時間，通常很快的做完自己的工作並阻塞。實時系統與互動式系統的差別是，實時系統只運行那些用來推進現有應用的程式，而互動式系統是通用的，它可以運行任意的非協作甚至是有惡意的程式。

調度演算法的目標

為了設計調度演算法，有必要考慮一下什麼是好的調度演算法。有一些目標取決於環境（批處理、互動式或者實時）蛋大部分是適用於所有情況的，下面是一些需要考量的因素，我們會在下面一起討論。

所有系統

在所有的情況中，公平是很重要的。對一個進程給予相較於其他等價的進程更多的 CPU 時間片對其他進程來說是不公平的。當然，不同類型的進程可以採用不同的處理方式。

與公平有關的是系統的強制執行，什麼意思呢？如果某公司的薪資發放系統計劃在本月的15號，那麼碰上了疫情大家生活都很拮据，此時老闆說要在14號晚上發放薪資，那麼調度程式必須強制使進程執行 14 號晚上發放薪資的策略。

另一個共同的目標是保持系統的所有部分儘可能的忙碌。如果 CPU 和所有的 I/O 設備能夠一直運行，那麼相對於讓某些部件空轉而言，每秒鐘就可以完成更多的工作。例如，在批處理系統中，調度程式控制哪個作業調入記憶體運行。在記憶體中既有一些 CPU 密集型進程又有一些 I/O 密集型進程是一個比較好的想法，好於先調入和運行所有的 CPU 密集型作業，然後在它們完成之後再調入和運行所有 I/O 密集型作業的做法。使用後者這種方式會在 CPU 密集型進程啟動後，爭奪 CPU ，而磁碟卻在空轉，而當 I/O 密集型進程啟動後，它們又要為磁碟而競爭，CPU 卻又在空轉。。。。。。顯然，通過結合 I/O 密集型和 CPU 密集型，能夠使整個系統運行更流暢，效率更高。

批處理系統

通常有三個指標來衡量系統工作狀態：吞吐量、周轉時間和 CPU 利用率，吞吐量(throughout) 是系統每小時完成的作業數量。綜合考慮，每小時完成 50 個工作要比每小時完成 40 個工作好。周轉時間(Turnaround time) 是一種平均時間，它指的是從一個批處理提交開始直到作業完成時刻為止平均時間。該數據度量了用戶要得到輸出所需的平均等待時間。周轉時間越小越好。

CPU 利用率(CPU utilization) 通常作為批處理系統上的指標。即使如此， CPU 利用率也不是一個好的度量指標，真正有價值的衡量指標是系統每小時可以完成多少作業（吞吐量），以及完成作業需要多長時間（周轉時間）。把 CPU 利用率作為度量指標，就像是引擎每小時轉動了多少次來比較汽車的性能一樣。而且知道 CPU 的利用率什麼時候接近 100% 要比什麼什麼時候要求得到更多的計算能力要有用。

互動式系統

對於互動式系統，則有不同的指標。最重要的是盡量減少響應時間。這個時間說的是從執行指令開始到得到結果的時間。再有後台進程運行（例如，從網路上讀取和保存 E-mail 文件）的個人電腦上，用戶請求啟動一個程式或打開一個文件應該優先於後台的工作。能夠讓所有的互動式請求首先運行的就是一個好的服務。

一個相關的問題是 均衡性(proportionality)，用戶對做一件事情需要多長時間總是有一種固定（不過通常不正確）的看法。當認為一個請求很複雜需要較多時間時，用戶會認為很正常並且可以接受，但是一個很簡單的程式卻花費了很長的運行時間，用戶就會很惱怒。可以拿彩印和複印來舉出一個簡單的例子，彩印可能需要1分鐘的時間，但是用戶覺得複雜並且願意等待一分鐘，相反，複印很簡單只需要 5 秒鐘，但是複印機花費 1 分鐘卻沒有完成複印操作，用戶就會很焦躁。

實時系統

實時系統則有著和互動式系統不同的考量因素，因此也就有不同的調度目標。實時系統的特點是必須滿足最後的截止時間。例如，如果電腦控制著以固定速率產生數據的設備，未能按時運行的話可能會導致數據丟失。因此，實時系統中最重要的需求是滿足所有（或大多數）時間期限。

在一些實事系統中，特別是涉及到多媒體的，可預測性很重要。偶爾不能滿足最後的截止時間不重要，但是如果音頻多媒體運行不穩定，聲音品質會持續惡化。影片也會造成問題，但是耳朵要比眼睛敏感很多。為了避免這些問題，進程調度必須能夠高度可預測的而且是有規律的。

批處理中的調度

現在讓我們把目光從一般性的調度轉換為特定的調度演算法。下面我們會探討在批處理中的調度。

先來先服務

很像是先到先得。。。可能最簡單的非搶佔式調度演算法的設計就是 先來先服務(first-come,first-serverd)。使用此演算法，將按照請求順序為進程分配 CPU。最基本的，會有一個就緒進程的等待隊列。當第一個任務從外部進入系統時，將會立即啟動並允許運行任意長的時間。它不會因為運行時間太長而中斷。當其他作業進入時，它們排到就緒隊列尾部。當正在運行的進程阻塞，處於等待隊列的第一個進程就開始運行。當一個阻塞的進程重新處於就緒態時，它會像一個新到達的任務，會排在隊列的末尾，即排在所有進程最後。

這個演算法的強大之處在於易於理解和編程，在這個演算法中，一個單鏈表記錄了所有就緒進程。要選取一個進程運行，只要從該隊列的頭部移走一個進程即可；要添加一個新的作業或者阻塞一個進程，只要把這個作業或進程附加在隊列的末尾即可。這是很簡單的一種實現。

不過，先來先服務也是有缺點的，那就是沒有優先順序的關係，試想一下，如果有 100 個 I/O 進程正在排隊，第 101 個是一個 CPU 密集型進程，那豈不是需要等 100 個 I/O 進程運行完畢才會等到一個 CPU 密集型進程運行，這在實際情況下根本不可能，所以需要優先順序或者搶佔式進程的出現來優先選擇重要的進程運行。

最短作業優先

批處理中，第二種調度演算法是 最短作業優先(Shortest Job First)，我們假設運行時間已知。例如，一家保險公司，因為每天要做類似的工作，所以人們可以相當精確地預測處理 1000 個索賠的一批作業需要多長時間。當輸入隊列中有若干個同等重要的作業被啟動時，調度程式應使用最短優先作業演算法

如上圖 a 所示，這裡有 4 個作業 A、B、C、D ，運行時間分別為 8、4、4、4 分鐘。若按圖中的次序運行，則 A 的周轉時間為 8 分鐘，B 為 12 分鐘，C 為 16 分鐘，D 為 20 分鐘，平均時間內為 14 分鐘。

現在考慮使用最短作業優先演算法運行 4 個作業，如上圖 b 所示，目前的周轉時間分別為 4、8、12、20，平均為 11 分鐘，可以證明最短作業優先是最優的。考慮有 4 個作業的情況，其運行時間分別為 a、b、c、d。第一個作業在時間 a 結束，第二個在時間 a + b 結束，以此類推。平均周轉時間為 (4a + 3b + 2c + d) / 4 。顯然 a 對平均值的影響最大，所以 a 應該是最短優先作業，其次是 b，然後是 c ，最後是 d 它就只能影響自己的周轉時間了。

需要注意的是，在所有的進程都可以運行的情況下，最短作業優先的演算法才是最優的。

最短剩餘時間優先

最短作業優先的搶佔式版本被稱作為 最短剩餘時間優先(Shortest Remaining Time Next) 演算法。使用這個演算法，調度程式總是選擇剩餘運行時間最短的那個進程運行。當一個新作業到達時，其整個時間同當前進程的剩餘時間做比較。如果新的進程比當前運行進程需要更少的時間，當前進程就被掛起，而運行新的進程。這種方式能夠使短期作業獲得良好的服務。

互動式系統中的調度

互動式系統中在個人電腦、伺服器和其他系統中都是很常用的，所以有必要來探討一下互動式調度

輪詢調度

一種最古老、最簡單、最公平並且最廣泛使用的演算法就是 輪詢演算法(round-robin)。每個進程都會被分配一個時間段，稱為時間片(quantum)，在這個時間片內允許進程運行。如果時間片結束時進程還在運行的話，則搶佔一個 CPU 並將其分配給另一個進程。如果進程在時間片結束前阻塞或結束，則 CPU 立即進行切換。輪詢演算法比較容易實現。調度程式所做的就是維護一個可運行進程的列表，就像下圖中的 a，當一個進程用完時間片後就被移到隊列的末尾，就像下圖的 b。

時間片輪詢調度中唯一有意思的一點就是時間片的長度。從一個進程切換到另一個進程需要一定的時間進行管理處理，包括保存暫存器的值和記憶體映射、更新不同的表格和列表、清除和重新調入記憶體高速快取等。這種切換稱作 進程間切換(process switch) 和 上下文切換(context switch)。如果進程間的切換時間需要 1ms，其中包括記憶體映射、清除和重新調入高速快取等，再假設時間片設為 4 ms，那麼 CPU 在做完 4 ms 有用的工作之後，CPU 將花費 1 ms 來進行進程間的切換。因此，CPU 的時間片會浪費 20% 的時間在管理開銷上。耗費巨大。

為了提高 CPU 的效率，我們把時間片設置為 100 ms。現在時間的浪費只有 1%。但是考慮會發現下面的情況，如果在一個非常短的時間內到達 50 個請求，並且對 CPU 有不同的需求，此時會發生什麼？50 個進程都被放在可運行進程列表中。如果 CP畫U 是空閑的，第一個進程會立即開始執行，第二個直到 100 ms 以後才會啟動，以此類推。不幸的是最後一個進程需要等待 5 秒才能獲得執行機會。大部分用戶都會覺得對於一個簡短的指令運行 5 秒中是很慢的。如果隊列末尾的某些請求只需要幾號秒鐘的運行時間的話，這種設計就非常糟糕了。

另外一個因素是如果時間片設置長度要大於 CPU 使用長度，那麼搶佔就不會經常發生。相反，在時間片用完之前，大多數進程都已經阻塞了，那麼就會引起進程間的切換。消除搶佔可提高性能，因為進程切換僅在邏輯上必要時才發生，即流程阻塞且無法繼續時才發生。

結論可以表述如下：將上下文切換時間設置得太短會導致過多的進程切換並降低 CPU 效率，但設置時間太長會導致一個短請求很長時間得不到響應。最好的切換時間是在 20 - 50 毫秒之間設置。

優先順序調度

輪詢調度假設了所有的進程是同等重要的。但事實情況可能不是這樣。例如，在一所大學中的等級制度，首先是院長，然後是教授、秘書、後勤人員，最後是學生。這種將外部情況考慮在內就實現了優先順序調度(priority scheduling)

它的基本思想很明確，每個進程都被賦予一個優先順序，優先順序高的進程優先運行。

但是也不意味著高優先順序的進程能夠永遠一直運行下去，調度程式會在每個時鐘中斷期間降低當前運行進程的優先順序。如果此操作導致其優先順序降低到下一個最高進程的優先順序以下，則會發生進程切換。或者，可以為每個進程分配允許運行的最大時間間隔。當時間間隔用完後，下一個高優先順序的進程會得到運行的機會。

可以靜態或者動態的為進程分配優先順序。在一台軍用電腦上，可以把將軍所啟動的進程設為優先順序 100，上校為 90 ，少校為 80，上尉為 70，中尉為 60，以此類推。UNIX 中有一條命令為 nice ，它允許用戶為了照顧他人而自願降低自己進程的優先順序，但是一般沒人用。

優先順序也可以由系統動態分配，用於實現某種目的。例如，有些進程為 I/O 密集型，其多數時間用來等待 I/O 結束。當這樣的進程需要 CPU 時，應立即分配 CPU，用來啟動下一個 I/O 請求，這樣就可以在另一個進程進行計算的同時執行 I/O 操作。這類 I/O 密集型進程長時間的等待 CPU 只會造成它長時間佔用記憶體。使 I/O 密集型進程獲得較好的服務的一種簡單演算法是，將其優先順序設為 1/f，f 為該進程在上一時間片中所佔的部分。一個在 50 ms 的時間片中只使用 1 ms 的進程將獲得優先順序 50 ，而在阻塞之前用掉 25 ms 的進程將具有優先順序 2，而使用掉全部時間片的進程將得到優先順序 1。

可以很方便的將一組進程按優先順序分成若干類，並且在各個類之間採用優先順序調度，而在各類進程的內部採用輪轉調度。下面展示了一個四個優先順序類的系統

它的調度演算法主要描述如下：上面存在優先順序為 4 類的可運行進程，首先會按照輪轉法為每個進程運行一個時間片，此時不理會較低優先順序的進程。若第 4 類進程為空，則按照輪詢的方式運行第三類進程。若第 4 類和第 3 類進程都為空，則按照輪轉法運行第 2 類進程。如果不對優先順序進行調整，則低優先順序的進程很容易產生飢餓現象。

多級隊列

最早使用優先順序調度的系統是 CTSS(Compatible TimeSharing System)。CTSS 是一種兼容分時系統，它有一個問題就是進程切換太慢，其原因是 IBM 7094 記憶體只能放進一個進程。

IBM 是哥倫比亞大學電腦中心在 1964 - 1968 年的電腦

CTSS 在每次切換前都需要將當前進程換出到磁碟，並從磁碟上讀入一個新進程。CTSS 的設計者很快就認識到，為 CPU 密集型進程設置較長的時間片比頻繁地分給他們很短的時間要更有效（減少交換次數）。另一方面，如前所述，長時間片的進程又會影響到響應時間，解決辦法是設置優先順序類。屬於最高優先順序的進程運行一個時間片，次高優先順序進程運行 2 個時間片，再下面一級運行 4 個時間片，以此類推。當一個進程用完分配的時間片後，它被移到下一類。

最短進程優先

對於批處理系統而言，由於最短作業優先常常伴隨著最短響應時間，所以如果能夠把它用於互動式進程，那將是非常好的。在某種程度上，的確可以做到這一點。互動式進程通常遵循下列模式：等待命令、執行命令、等待命令、執行命令。。。如果我們把每個命令的執行都看作一個分離的作業，那麼我們可以通過首先運行最短的作業來使響應時間最短。這裡唯一的問題是如何從當前可運行進程中找出最短的那一個進程。

一種方式是根據進程過去的行為進行推測，並執行估計運行時間最短的那一個。假設每個終端上每條命令的預估運行時間為 T0，現在假設測量到其下一次運行時間為 T1，可以用兩個值的加權來改進估計時間，即aT0+ (1- 1)T1。通過選擇 a 的值，可以決定是儘快忘掉老的運行時間，還是在一段長時間內始終記住它們。當 a = 1/2 時，可以得到下面這個序列

可以看到，在三輪過後，T0 在新的估計值中所佔比重下降至 1/8。

有時把這種通過當前測量值和先前估計值進行加權平均從而得到下一個估計值的技術稱作 老化(aging)。這種方法會使用很多預測值基於當前值的情況。

保證調度

一種完全不同的調度方法是對用戶做出明確的性能保證。一種實際而且容易實現的保證是：若用戶工作時有 n 個用戶登錄，則每個用戶將獲得 CPU 處理能力的 1/n。類似地，在一個有 n 個進程運行的單用戶系統中，若所有的進程都等價，則每個進程將獲得 1/n 的 CPU 時間。

彩票調度

對用戶進行承諾並在隨後兌現承諾是一件好事，不過很難實現。但是存在著一種簡單的方式，有一種既可以給出預測結果而又有一種比較簡單的實現方式的演算法，就是 彩票調度(lottery scheduling)演算法。

其基本思想是為進程提供各種系統資源（例如 CPU 時間）的彩票。當做出一個調度決策的時候，就隨機抽出一張彩票，擁有彩票的進程將獲得該資源。在應用到 CPU 調度時，系統可以每秒持有 50 次抽獎，每個中獎者將獲得比如 20 毫秒的 CPU 時間作為獎勵。

George Orwell 關於 所有的進程是平等的，但是某些進程能夠更平等一些。一些重要的進程可以給它們額外的彩票，以便增加他們贏得的機會。如果出售了 100 張彩票，而且有一個進程持有了它們中的 20 張，它就會有 20% 的機會去贏得彩票中獎。在長時間的運行中，它就會獲得 20% 的CPU。相反，對於優先順序調度程式，很難說明擁有優先順序 40 究竟是什麼意思，這裡的規則很清楚，擁有彩票 f 份額的進程大約得到系統資源的 f 份額。

如果希望進程之間協作的話可以交換它們之間的票據。例如，客戶端進程給伺服器進程發送了一條消息後阻塞，客戶端進程可能會把自己所有的票據都交給伺服器，來增加下一次伺服器運行的機會。當服務完成後，它會把彩票還給客戶端讓其有機會再次運行。事實上，如果沒有客戶機，伺服器也根本不需要彩票。

可以把彩票理解為 buff，這個 buff 有 15% 的幾率能讓你產生 速度之靴 的效果。

公平分享調度

到目前為止，我們假設被調度的都是各個進程自身，而不用考慮該進程的擁有者是誰。結果是，如果用戶 1 啟動了 9 個進程，而用戶 2 啟動了一個進程，使用輪轉或相同優先順序調度演算法，那麼用戶 1 將得到 90 % 的 CPU 時間，而用戶 2 將之得到 10 % 的 CPU 時間。

為了阻止這種情況的出現，一些系統在調度前會把進程的擁有者考慮在內。在這種模型下，每個用戶都會分配一些CPU 時間，而調度程式會選擇進程並強制執行。因此如果兩個用戶每個都會有 50% 的 CPU 時間片保證，那麼無論一個用戶有多少個進程，都將獲得相同的 CPU 份額。

實時系統中的調度

實時系統(real-time) 是一個時間扮演了重要作用的系統。典型的，一種或多種外部物理設備發給電腦一個服務請求，而電腦必須在一個確定的時間範圍內恰當的做出反應。例如，在 CD 播放器中的電腦會獲得從驅動器過來的位流，然後必須在非常短的時間內將位流轉換為音樂播放出來。如果計算時間過長，那麼音樂就會聽起來有異常。再比如說醫院特別護理部門的病人監護裝置、飛機中的自動駕駛系統、列車中的煙霧警告裝置等，在這些例子中，正確但是卻緩慢的響應要比沒有響應甚至還糟糕。

實時系統可以分為兩類，硬實時(hard real time) 和 軟實時(soft real time) 系統，前者意味著必須要滿足絕對的截止時間；後者的含義是雖然不希望偶爾錯失截止時間，但是可以容忍。在這兩種情形中，實時都是通過把程式劃分為一組進程而實現的，其中每個進程的行為是可預測和提前可知的。這些進程一般壽命較短，並且極快的運行完成。在檢測到一個外部訊號時，調度程式的任務就是按照滿足所有截止時間的要求調度進程。

實時系統中的事件可以按照響應方式進一步分類為周期性(以規則的時間間隔發生)事件或 非周期性(發生時間不可預知)事件。一個系統可能要響應多個周期性事件流，根據每個事件處理所需的時間，可能甚至無法處理所有事件。例如，如果有 m 個周期事件，事件 i 以周期 Pi 發生，並需要 Ci 秒 CPU 時間處理一個事件，那麼可以處理負載的條件是

只有滿足這個條件的實時系統稱為可調度的，這意味著它實際上能夠被實現。一個不滿足此檢驗標準的進程不能被調度，因為這些進程共同需要的 CPU 時間總和大於 CPU 能提供的時間。

舉一個例子，考慮一個有三個周期性事件的軟實時系統，其周期分別是 100 ms、200 m 和 500 ms。如果這些事件分別需要 50 ms、30 ms 和 100 ms 的 CPU 時間，那麼該系統時可調度的，因為 0.5 + 0.15 + 0.2 < 1。如果此時有第四個事件加入，其周期為 1 秒，那麼此時這個事件如果不超過 150 ms，那麼仍然是可以調度的。忽略上下文切換的時間。

實時系統的調度演算法可以是靜態的或動態的。前者在系統開始運行之前做出調度決策；後者在運行過程中進行調度決策。只有在可以提前掌握所完成的工作以及必須滿足的截止時間等資訊時，靜態調度才能工作，而動態調度不需要這些限制。

調度策略和機制

到目前為止，我們隱含的假設系統中所有進程屬於不同的分組用戶並且進程間存在相互競爭 CPU 的情況。通常情況下確實如此，但有時也會發生一個進程會有很多子進程並在其控制下運行的情況。例如，一個資料庫管理系統進程會有很多子進程。每一個子進程可能處理不同的請求，或者每個子進程實現不同的功能（如請求分析、磁碟訪問等）。主進程完全可能掌握哪一個子進程最重要（或最緊迫），而哪一個最不重要。但是，以上討論的調度演算法中沒有一個演算法從用戶進程接收有關的調度決策資訊，這就導致了調度程式很少能夠做出最優的選擇。

解決問題的辦法是將 調度機制(scheduling mechanism) 和 調度策略(scheduling policy) 分開，這是長期一貫的原則。這也就意味著調度演算法在某種方式下被參數化了，但是參數可以被用戶進程填寫。讓我們首先考慮資料庫的例子。假設內核使用優先順序調度演算法，並提供了一條可供進程設置優先順序的系統調用。這樣，儘管父進程本身並不參與調度，但它可以控制如何調度子進程的細節。調度機制位於內核，而調度策略由用戶進程決定，調度策略和機制分離是一種關鍵性思路。

執行緒調度

當若干進程都有多個執行緒時，就存在兩個層次的並行：進程和執行緒。在這樣的系統中調度處理有本質的差別，這取決於所支援的是用戶級執行緒還是內核級執行緒（或兩者都支援）。

首先考慮用戶級執行緒，由於內核並不知道有執行緒存在，所以內核還是和以前一樣地操作，選取一個進程，假設為 A，並給予 A 以時間片控制。A 中的執行緒調度程式決定哪個執行緒運行。假設為 A1。由於多道執行緒並不存在時鐘中斷，所以這個執行緒可以按其意願任意運行多長時間。如果該執行緒用完了進程的全部時間片，內核就會選擇另一個進程繼續運行。

在進程 A 終於又一次運行時，執行緒 A1 會接著運行。該執行緒會繼續耗費 A 進程的所有時間，直到它完成工作。不過，執行緒運行不會影響到其他進程。其他進程會得到調度程式所分配的合適份額，不會考慮進程 A 內部發生的事情。

現在考慮 A 執行緒每次 CPU 計算的工作比較少的情況，例如：在 50 ms 的時間片中有 5 ms 的計算工作。於是，每個執行緒運行一會兒，然後把 CPU 交回給執行緒調度程式。這樣在內核切換到進程 B 之前，就會有序列 A1,A2,A3,A1,A2,A3,A1,A2,A3,A1 。如下所示

運行時系統使用的調度演算法可以是上面介紹演算法的任意一種。從實用方面考慮，輪轉調度和優先順序調度更為常用。唯一的局限是，缺乏一個時鐘中斷運行過長的執行緒。但由於執行緒之間的合作關係，這通常也不是問題。

現在考慮使用內核執行緒的情況，內核選擇一個特定的執行緒運行。它不用考慮執行緒屬於哪個進程，不過如果有必要的話，也可以這麼做。對被選擇的執行緒賦予一個時間片，而且如果超過了時間片，就會強制掛起該執行緒。一個執行緒在 50 ms 的時間片內，5 ms 之後被阻塞，在 30 ms 的時間片中，執行緒的順序會是 A1,B1,A2,B2,A3,B3。如下圖所示

用戶級執行緒和內核級執行緒之間的主要差別在於性能。用戶級執行緒的切換需要少量的機器指令（想像一下Java程式的執行緒切換），而內核執行緒需要完整的上下文切換，修改記憶體映像，使高速快取失效，這會導致了若干數量級的延遲。另一方面，在使用內核級執行緒時，一旦執行緒阻塞在 I/O 上就不需要在用戶級執行緒中那樣將整個進程掛起。

從進程 A 的一個執行緒切換到進程 B 的一個執行緒，其消耗要遠高於運行進程 A 的兩個執行緒（涉及修改記憶體映像，修改高速快取），內核對這種切換的消耗是了解到，可以通過這些資訊作出決定。

文章參考：

《現代作業系統》

《Modern Operating System》forth edition

https://www.encyclopedia.com/computing/news-wires-white-papers-and-books/interactive-systems

https://j00ru.vexillium.org/syscalls/nt/32/

https://www.bottomupcs.com/process_hierarchy.xhtml

https://en.wikipedia.org/wiki/Runtime_system

https://en.wikipedia.org/wiki/Execution_model

https://zhidao.baidu.com/question/113227654.html

https://baike.baidu.com/item/等待隊列/9223804?fr=aladdin

http://www.columbia.edu/cu/computinghistory/7094.html

https://baike.baidu.com/item/中斷向量/4947039?fr=aladdin

給大家推薦一個Github，我發現裡面有好幾百本CS類地常用電子書，推薦給大家：https://github.com/iamshuaidi/CS-Book（點擊閱讀原文直達，電腦打開更佳）

Tags:

VirMach 便宜 VPS