當初我要是這麼學習「程序和線程」就好了（附帶思維導圖）

作者 | 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 %d\n",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 %d\n",i);
    status = pthread_create(&threads[i], NULL, print_hello_world, (void *)i);

    if(status != 0){
      printf("Oops. pthread_create returned error code %d\n",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 p)​

​。如果我們能夠正确的操作，使兩個不同程序不可能同時處于臨界區，就能避免競争條件，這也是從作業系統設計角度來進行的。

盡管上面這種設計避免了競争條件，但是不能確定并發線程同時通路共享資料的正确性和高效性。一個好的解決方案，應該包含下面四種條件

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​​

END

​