來源：Java建設(shè)者

作者：cxuan

下面是本文的結(jié)構(gòu)圖

我們平常說的進(jìn)程和線程更多的是基于編程語言的角度來說的，那么你真的了解什么是線程和進(jìn)程嗎？那么我們就從操作系統(tǒng)的角度來了解一下什么是進(jìn)程和線程。

進(jìn)程

操作系統(tǒng)中最核心的概念就是 進(jìn)程，進(jìn)程是對(duì)正在運(yùn)行中的程序的一個(gè)抽象。操作系統(tǒng)的其他所有內(nèi)容都是圍繞著進(jìn)程展開的。進(jìn)程是操作系統(tǒng)提供的最古老也是最重要的概念之一。即使可以使用的 CPU 只有一個(gè)，它們也支持（偽）并發(fā)操作。它們會(huì)將一個(gè)單獨(dú)的 CPU 抽象為多個(gè)虛擬機(jī)的 CPU?？梢哉f：沒有進(jìn)程的抽象，現(xiàn)代操作系統(tǒng)將不復(fù)存在。

所有現(xiàn)代的計(jì)算機(jī)會(huì)在同一時(shí)刻做很多事情，過去使用計(jì)算機(jī)的人（單 CPU）可能完全無法理解現(xiàn)在這種變化，舉個(gè)例子更能說明這一點(diǎn)：首先考慮一個(gè) Web 服務(wù)器，請(qǐng)求都來自于 Web 網(wǎng)頁。當(dāng)一個(gè)請(qǐng)求到達(dá)時(shí)，服務(wù)器會(huì)檢查當(dāng)前頁是否在緩存中，如果是在緩存中，就直接把緩存中的內(nèi)容返回。如果緩存中沒有的話，那么請(qǐng)求就會(huì)交給磁盤來處理。但是，從 CPU 的角度來看，磁盤請(qǐng)求需要更長的時(shí)間，因?yàn)榇疟P請(qǐng)求會(huì)很慢。當(dāng)硬盤請(qǐng)求完成時(shí)，更多其他請(qǐng)求才會(huì)進(jìn)入。如果有多個(gè)磁盤的話，可以在第一個(gè)請(qǐng)求完成前就可以連續(xù)的對(duì)其他磁盤發(fā)出部分或全部請(qǐng)求。很顯然，這是一種并發(fā)現(xiàn)象，需要有并發(fā)控制條件來控制并發(fā)現(xiàn)象。

現(xiàn)在考慮只有一個(gè)用戶的 PC。當(dāng)系統(tǒng)啟動(dòng)時(shí)，許多進(jìn)程也在后臺(tái)啟動(dòng)，用戶通常不知道這些進(jìn)程的啟動(dòng)，試想一下，當(dāng)你自己的計(jì)算機(jī)啟動(dòng)的時(shí)候，你能知道哪些進(jìn)程是需要啟動(dòng)的么？這些后臺(tái)進(jìn)程可能是一個(gè)需要輸入電子郵件的電子郵件進(jìn)程，或者是一個(gè)計(jì)算機(jī)病毒查殺進(jìn)程來周期性的更新病毒庫。某個(gè)用戶進(jìn)程可能會(huì)在所有用戶上網(wǎng)的時(shí)候打印文件以及刻錄 CD-ROM，這些活動(dòng)都需要管理。于是一個(gè)支持多進(jìn)程的多道程序系統(tǒng)就會(huì)顯得很有必要了。

在許多多道程序系統(tǒng)中，CPU 會(huì)在進(jìn)程間快速切換，使每個(gè)程序運(yùn)行幾十或者幾百毫秒。然而，嚴(yán)格意義來說，在某一個(gè)瞬間，CPU 只能運(yùn)行一個(gè)進(jìn)程，然而我們?nèi)绻褧r(shí)間定位為 1 秒內(nèi)的話，它可能運(yùn)行多個(gè)進(jìn)程。這樣就會(huì)讓我們產(chǎn)生并行的錯(cuò)覺。有時(shí)候人們說的 偽并行(pseudoparallelism) 就是這種情況，以此來區(qū)分多處理器系統(tǒng)(該系統(tǒng)由兩個(gè)或多個(gè) CPU 來共享同一個(gè)物理內(nèi)存)

再來詳細(xì)解釋一下偽并行：偽并行是指單核或多核處理器同時(shí)執(zhí)行多個(gè)進(jìn)程，從而使程序更快。通過以非常有限的時(shí)間間隔在程序之間快速切換CPU，因此會(huì)產(chǎn)生并行感。缺點(diǎn)是 CPU 時(shí)間可能分配給下一個(gè)進(jìn)程，也可能不分配給下一個(gè)進(jìn)程。

因?yàn)?CPU 執(zhí)行速度很快，進(jìn)程間的換進(jìn)換出也非常迅速，因此我們很難對(duì)多個(gè)并行進(jìn)程進(jìn)行跟蹤，所以，在經(jīng)過多年的努力后，操作系統(tǒng)的設(shè)計(jì)者開發(fā)了用于描述并行的一種概念模型（順序進(jìn)程），使得并行更加容易理解和分析，對(duì)該模型的探討，也是本篇文章的主題。下面我們就來探討一下進(jìn)程模型

進(jìn)程模型

在進(jìn)程模型中，所有計(jì)算機(jī)上運(yùn)行的軟件，通常也包括操作系統(tǒng)，被組織為若干順序進(jìn)程(sequential processes)，簡稱為 進(jìn)程(process) 。一個(gè)進(jìn)程就是一個(gè)正在執(zhí)行的程序的實(shí)例，進(jìn)程也包括程序計(jì)數(shù)器、寄存器和變量的當(dāng)前值。從概念上來說，每個(gè)進(jìn)程都有各自的虛擬 CPU，但是實(shí)際情況是 CPU 會(huì)在各個(gè)進(jìn)程之間進(jìn)行來回切換。

如上圖所示，這是一個(gè)具有 4 個(gè)程序的多道處理程序，在進(jìn)程不斷切換的過程中，程序計(jì)數(shù)器也在不同的變化。

在上圖中，這 4 道程序被抽象為 4 個(gè)擁有各自控制流程（即每個(gè)自己的程序計(jì)數(shù)器）的進(jìn)程，并且每個(gè)程序都獨(dú)立的運(yùn)行。當(dāng)然，實(shí)際上只有一個(gè)物理程序計(jì)數(shù)器，每個(gè)程序要運(yùn)行時(shí)，其邏輯程序計(jì)數(shù)器會(huì)裝載到物理程序計(jì)數(shù)器中。當(dāng)程序運(yùn)行結(jié)束后，其物理程序計(jì)數(shù)器就會(huì)是真正的程序計(jì)數(shù)器，然后再把它放回進(jìn)程的邏輯計(jì)數(shù)器中。

從下圖我們可以看到，在觀察足夠長的一段時(shí)間后，所有的進(jìn)程都運(yùn)行了，但在任何一個(gè)給定的瞬間僅有一個(gè)進(jìn)程真正運(yùn)行。

因此，當(dāng)我們說一個(gè) CPU 只能真正一次運(yùn)行一個(gè)進(jìn)程的時(shí)候，即使有 2 個(gè)核（或 CPU），每一個(gè)核也只能一次運(yùn)行一個(gè)線程。

由于 CPU 會(huì)在各個(gè)進(jìn)程之間來回快速切換，所以每個(gè)進(jìn)程在 CPU 中的運(yùn)行時(shí)間是無法確定的。并且當(dāng)同一個(gè)進(jìn)程再次在 CPU 中運(yùn)行時(shí)，其在 CPU 內(nèi)部的運(yùn)行時(shí)間往往也是不固定的。進(jìn)程和程序之間的區(qū)別是非常微妙的，但是通過一個(gè)例子可以讓你加以區(qū)分：想想一位會(huì)做飯的計(jì)算機(jī)科學(xué)家正在為他的女兒制作生日蛋糕。他有做生日蛋糕的食譜，廚房里有所需的原諒：面粉、雞蛋、糖、香草汁等。在這個(gè)比喻中，做蛋糕的食譜就是程序、計(jì)算機(jī)科學(xué)家就是 CPU、而做蛋糕的各種原料都是輸入數(shù)據(jù)。進(jìn)程就是科學(xué)家閱讀食譜、取來各種原料以及烘焙蛋糕等一系列動(dòng)作的總和。

現(xiàn)在假設(shè)科學(xué)家的兒子跑過來告訴他，說他的頭被蜜蜂蜇了一下，那么此時(shí)科學(xué)家會(huì)記錄出來他做蛋糕這個(gè)過程到了哪一步，然后拿出急救手冊(cè)，按照上面的步驟給他兒子實(shí)施救助。這里，會(huì)涉及到進(jìn)程之間的切換，科學(xué)家（CPU）會(huì)從做蛋糕（進(jìn)程）切換到實(shí)施醫(yī)療救助（另一個(gè)進(jìn)程）。等待傷口處理完畢后，科學(xué)家會(huì)回到剛剛記錄做蛋糕的那一步，繼續(xù)制作。

這里的關(guān)鍵思想是認(rèn)識(shí)到一個(gè)進(jìn)程所需的條件，進(jìn)程是某一類特定活動(dòng)的總和，它有程序、輸入輸出以及狀態(tài)。單個(gè)處理器可以被若干進(jìn)程共享，它使用某種調(diào)度算法決定何時(shí)停止一個(gè)進(jìn)程的工作，并轉(zhuǎn)而為另外一個(gè)進(jìn)程提供服務(wù)。另外需要注意的是，如果一個(gè)進(jìn)程運(yùn)行了兩遍，則被認(rèn)為是兩個(gè)進(jìn)程。那么我們了解到進(jìn)程模型后，那么進(jìn)程是如何創(chuàng)建的呢？

進(jìn)程的創(chuàng)建

操作系統(tǒng)需要一些方式來創(chuàng)建進(jìn)程。下面是一些創(chuàng)建進(jìn)程的方式

• 系統(tǒng)初始化（init）

• 正在運(yùn)行的程序執(zhí)行了創(chuàng)建進(jìn)程的系統(tǒng)調(diào)用（比如 fork）

• 用戶請(qǐng)求創(chuàng)建一個(gè)新進(jìn)程

• 初始化一個(gè)批處理工作

系統(tǒng)初始化

啟動(dòng)操作系統(tǒng)時(shí)，通常會(huì)創(chuàng)建若干個(gè)進(jìn)程。其中有些是前臺(tái)進(jìn)程(numerous processes)，也就是同用戶進(jìn)行交互并替他們完成工作的進(jìn)程。一些運(yùn)行在后臺(tái)，并不與特定的用戶進(jìn)行交互，例如，設(shè)計(jì)一個(gè)進(jìn)程來接收發(fā)來的電子郵件，這個(gè)進(jìn)程大部分的時(shí)間都在休眠，但是只要郵件到來后這個(gè)進(jìn)程就會(huì)被喚醒。還可以設(shè)計(jì)一個(gè)進(jìn)程來接收對(duì)該計(jì)算機(jī)上網(wǎng)頁的傳入請(qǐng)求，在請(qǐng)求到達(dá)的進(jìn)程喚醒來處理網(wǎng)頁的傳入請(qǐng)求。進(jìn)程運(yùn)行在后臺(tái)用來處理一些活動(dòng)像是 e-mail，web 網(wǎng)頁，新聞，打印等等被稱為 守護(hù)進(jìn)程(daemons)。大型系統(tǒng)會(huì)有很多守護(hù)進(jìn)程。在 UNIX 中，ps 程序可以列出正在運(yùn)行的進(jìn)程， 在 Windows 中，可以使用任務(wù)管理器。

系統(tǒng)調(diào)用創(chuàng)建

除了在啟動(dòng)階段創(chuàng)建進(jìn)程之外，一些新的進(jìn)程也可以在后面創(chuàng)建。通常，一個(gè)正在運(yùn)行的進(jìn)程會(huì)發(fā)出系統(tǒng)調(diào)用用來創(chuàng)建一個(gè)或多個(gè)新進(jìn)程來幫助其完成工作。例如，如果有大量的數(shù)據(jù)需要經(jīng)過網(wǎng)絡(luò)調(diào)取并進(jìn)行順序處理，那么創(chuàng)建一個(gè)進(jìn)程讀數(shù)據(jù)，并把數(shù)據(jù)放到共享緩沖區(qū)中，而讓第二個(gè)進(jìn)程取走并正確處理會(huì)比較容易些。在多處理器中，讓每個(gè)進(jìn)程運(yùn)行在不同的 CPU 上也可以使工作做的更快。

用戶請(qǐng)求創(chuàng)建

在許多交互式系統(tǒng)中，輸入一個(gè)命令或者雙擊圖標(biāo)就可以啟動(dòng)程序，以上任意一種操作都可以選擇開啟一個(gè)新的進(jìn)程，在基本的 UNIX 系統(tǒng)中運(yùn)行 X，新進(jìn)程將接管啟動(dòng)它的窗口。在 Windows 中啟動(dòng)進(jìn)程時(shí)，它一般沒有窗口，但是它可以創(chuàng)建一個(gè)或多個(gè)窗口。每個(gè)窗口都可以運(yùn)行進(jìn)程。通過鼠標(biāo)或者命令就可以切換窗口并與進(jìn)程進(jìn)行交互。

交互式系統(tǒng)是以人與計(jì)算機(jī)之間大量交互為特征的計(jì)算機(jī)系統(tǒng)，比如游戲、web瀏覽器，IDE 等集成開發(fā)環(huán)境。

批處理創(chuàng)建

最后一種創(chuàng)建進(jìn)程的情形會(huì)在大型機(jī)的批處理系統(tǒng)中應(yīng)用。用戶在這種系統(tǒng)中提交批處理作業(yè)。當(dāng)操作系統(tǒng)決定它有資源來運(yùn)行另一個(gè)任務(wù)時(shí)，它將創(chuàng)建一個(gè)新進(jìn)程并從其中的輸入隊(duì)列中運(yùn)行下一個(gè)作業(yè)。

從技術(shù)上講，在所有這些情況下，讓現(xiàn)有流程執(zhí)行流程是通過創(chuàng)建系統(tǒng)調(diào)用來創(chuàng)建新流程的。該進(jìn)程可能是正在運(yùn)行的用戶進(jìn)程，是從鍵盤或鼠標(biāo)調(diào)用的系統(tǒng)進(jìn)程或批處理程序。這些就是系統(tǒng)調(diào)用創(chuàng)建新進(jìn)程的過程。該系統(tǒng)調(diào)用告訴操作系統(tǒng)創(chuàng)建一個(gè)新進(jìn)程，并直接或間接指示在其中運(yùn)行哪個(gè)程序。

在 UNIX 中，僅有一個(gè)系統(tǒng)調(diào)用來創(chuàng)建一個(gè)新的進(jìn)程，這個(gè)系統(tǒng)調(diào)用就是 fork。這個(gè)調(diào)用會(huì)創(chuàng)建一個(gè)與調(diào)用進(jìn)程相關(guān)的副本。在 fork 后，一個(gè)父進(jìn)程和子進(jìn)程會(huì)有相同的內(nèi)存映像，相同的環(huán)境字符串和相同的打開文件。通常，子進(jìn)程會(huì)執(zhí)行 execve 或者一個(gè)簡單的系統(tǒng)調(diào)用來改變內(nèi)存映像并運(yùn)行一個(gè)新的程序。例如，當(dāng)一個(gè)用戶在 shell 中輸出 sort 命令時(shí)，shell 會(huì) fork 一個(gè)子進(jìn)程然后子進(jìn)程去執(zhí)行 sort 命令。這兩步過程的原因是允許子進(jìn)程在 fork 之后但在 execve 之前操作其文件描述符，以完成標(biāo)準(zhǔn)輸入，標(biāo)準(zhǔn)輸出和標(biāo)準(zhǔn)錯(cuò)誤的重定向。

在 Windows 中，情況正相反，一個(gè)簡單的 Win32 功能調(diào)用 CreateProcess，會(huì)處理流程創(chuàng)建并將正確的程序加載到新的進(jìn)程中。這個(gè)調(diào)用會(huì)有 10 個(gè)參數(shù)，包括了需要執(zhí)行的程序、輸入給程序的命令行參數(shù)、各種安全屬性、有關(guān)打開的文件是否繼承控制位、優(yōu)先級(jí)信息、進(jìn)程所需要?jiǎng)?chuàng)建的窗口規(guī)格以及指向一個(gè)結(jié)構(gòu)的指針，在該結(jié)構(gòu)中新創(chuàng)建進(jìn)程的信息被返回給調(diào)用者。除了 CreateProcess Win 32 中大概有 100 個(gè)其他的函數(shù)用于處理進(jìn)程的管理，同步以及相關(guān)的事務(wù)。下面是 UNIX 操作系統(tǒng)和 Windows 操作系統(tǒng)系統(tǒng)調(diào)用的對(duì)比

在 UNIX 和 Windows 中，進(jìn)程創(chuàng)建之后，父進(jìn)程和子進(jìn)程有各自不同的地址空間。如果其中某個(gè)進(jìn)程在其地址空間中修改了一個(gè)詞，這個(gè)修改將對(duì)另一個(gè)進(jìn)程不可見。在 UNIX 中，子進(jìn)程的地址空間是父進(jìn)程的一個(gè)拷貝，但是卻是兩個(gè)不同的地址空間；不可寫的內(nèi)存區(qū)域是共享的。某些 UNIX 實(shí)現(xiàn)是正是在兩者之間共享，因?yàn)樗荒鼙恍薷摹；蛘?，子進(jìn)程共享父進(jìn)程的所有內(nèi)存，但是這種情況下內(nèi)存通過 寫時(shí)復(fù)制(copy-on-write) 共享，這意味著一旦兩者之一想要修改部分內(nèi)存，則這塊內(nèi)存首先被明確的復(fù)制，以確保修改發(fā)生在私有內(nèi)存區(qū)域。再次強(qiáng)調(diào)，可寫的內(nèi)存是不能被共享的。但是，對(duì)于一個(gè)新創(chuàng)建的進(jìn)程來說，確實(shí)有可能共享創(chuàng)建者的資源，比如可以共享打開的文件。在 Windows 中，從一開始父進(jìn)程的地址空間和子進(jìn)程的地址空間就是不同的。

進(jìn)程的終止

進(jìn)程在創(chuàng)建之后，它就開始運(yùn)行并做完成任務(wù)。然而，沒有什么事兒是永不停歇的，包括進(jìn)程也一樣。進(jìn)程早晚會(huì)發(fā)生終止，但是通常是由于以下情況觸發(fā)的

• 正常退出(自愿的)

• 錯(cuò)誤退出(自愿的)

• 嚴(yán)重錯(cuò)誤(非自愿的)

• 被其他進(jìn)程殺死(非自愿的)

正常退出

多數(shù)進(jìn)程是由于完成了工作而終止。當(dāng)編譯器完成了所給定程序的編譯之后，編譯器會(huì)執(zhí)行一個(gè)系統(tǒng)調(diào)用告訴操作系統(tǒng)它完成了工作。這個(gè)調(diào)用在 UNIX 中是 exit ，在 Windows 中是 ExitProcess。面向屏幕中的軟件也支持自愿終止操作。字處理軟件、Internet 瀏覽器和類似的程序中總有一個(gè)供用戶點(diǎn)擊的圖標(biāo)或菜單項(xiàng)，用來通知進(jìn)程刪除它所打開的任何臨時(shí)文件，然后終止。

錯(cuò)誤退出

進(jìn)程發(fā)生終止的第二個(gè)原因是發(fā)現(xiàn)嚴(yán)重錯(cuò)誤，例如，如果用戶執(zhí)行如下命令

為了能夠編譯 foo.c 但是該文件不存在，于是編譯器就會(huì)發(fā)出聲明并退出。在給出了錯(cuò)誤參數(shù)時(shí)，面向屏幕的交互式進(jìn)程通常并不會(huì)直接退出，因?yàn)檫@從用戶的角度來說并不合理，用戶需要知道發(fā)生了什么并想要進(jìn)行重試，所以這時(shí)候應(yīng)用程序通常會(huì)彈出一個(gè)對(duì)話框告知用戶發(fā)生了系統(tǒng)錯(cuò)誤，是需要重試還是退出。

嚴(yán)重錯(cuò)誤

進(jìn)程終止的第三個(gè)原因是由進(jìn)程引起的錯(cuò)誤，通常是由于程序中的錯(cuò)誤所導(dǎo)致的。例如，執(zhí)行了一條非法指令，引用不存在的內(nèi)存，或者除數(shù)是 0 等。在有些系統(tǒng)比如 UNIX 中，進(jìn)程可以通知操作系統(tǒng)，它希望自行處理某種類型的錯(cuò)誤，在這類錯(cuò)誤中，進(jìn)程會(huì)收到信號(hào)（中斷），而不是在這類錯(cuò)誤出現(xiàn)時(shí)直接終止進(jìn)程。

被其他進(jìn)程殺死

第四個(gè)終止進(jìn)程的原因是，某個(gè)進(jìn)程執(zhí)行系統(tǒng)調(diào)用告訴操作系統(tǒng)殺死某個(gè)進(jìn)程。在 UNIX 中，這個(gè)系統(tǒng)調(diào)用是 kill。在 Win32 中對(duì)應(yīng)的函數(shù)是 TerminateProcess（注意不是系統(tǒng)調(diào)用）。

進(jìn)程的層次結(jié)構(gòu)

在一些系統(tǒng)中，當(dāng)一個(gè)進(jìn)程創(chuàng)建了其他進(jìn)程后，父進(jìn)程和子進(jìn)程就會(huì)以某種方式進(jìn)行關(guān)聯(lián)。子進(jìn)程它自己就會(huì)創(chuàng)建更多進(jìn)程，從而形成一個(gè)進(jìn)程層次結(jié)構(gòu)。

UNIX 進(jìn)程體系

在 UNIX 中，進(jìn)程和它的所有子進(jìn)程以及子進(jìn)程的子進(jìn)程共同組成一個(gè)進(jìn)程組。當(dāng)用戶從鍵盤中發(fā)出一個(gè)信號(hào)后，該信號(hào)被發(fā)送給當(dāng)前與鍵盤相關(guān)的進(jìn)程組中的所有成員（它們通常是在當(dāng)前窗口創(chuàng)建的所有活動(dòng)進(jìn)程）。每個(gè)進(jìn)程可以分別捕獲該信號(hào)、忽略該信號(hào)或采取默認(rèn)的動(dòng)作，即被信號(hào) kill 掉。

這里有另一個(gè)例子，可以用來說明層次的作用，考慮 UNIX 在啟動(dòng)時(shí)如何初始化自己。一個(gè)稱為 init 的特殊進(jìn)程出現(xiàn)在啟動(dòng)映像中 。當(dāng) init 進(jìn)程開始運(yùn)行時(shí)，它會(huì)讀取一個(gè)文件，文件會(huì)告訴它有多少個(gè)終端。然后為每個(gè)終端創(chuàng)建一個(gè)新進(jìn)程。這些進(jìn)程等待用戶登錄。如果登錄成功，該登錄進(jìn)程就執(zhí)行一個(gè) shell 來等待接收用戶輸入指令，這些命令可能會(huì)啟動(dòng)更多的進(jìn)程，以此類推。因此，整個(gè)操作系統(tǒng)中所有的進(jìn)程都隸屬于一個(gè)單個(gè)以 init 為根的進(jìn)程樹。

Windows 進(jìn)程體系

相反，Windows 中沒有進(jìn)程層次的概念，Windows 中所有進(jìn)程都是平等的，唯一類似于層次結(jié)構(gòu)的是在創(chuàng)建進(jìn)程的時(shí)候，父進(jìn)程得到一個(gè)特別的令牌（稱為句柄），該句柄可以用來控制子進(jìn)程。然而，這個(gè)令牌可能也會(huì)移交給別的操作系統(tǒng)，這樣就不存在層次結(jié)構(gòu)了。而在 UNIX 中，進(jìn)程不能剝奪其子進(jìn)程的 進(jìn)程權(quán)。（這樣看來，還是 Windows 比較渣）。

進(jìn)程狀態(tài)

盡管每個(gè)進(jìn)程是一個(gè)獨(dú)立的實(shí)體，有其自己的程序計(jì)數(shù)器和內(nèi)部狀態(tài)，但是，進(jìn)程之間仍然需要相互幫助。例如，一個(gè)進(jìn)程的結(jié)果可以作為另一個(gè)進(jìn)程的輸入，在 shell 命令中

cat chapter1 chapter2 chapter3 | grep tree

第一個(gè)進(jìn)程是 cat，將三個(gè)文件級(jí)聯(lián)并輸出。第二個(gè)進(jìn)程是 grep，它從輸入中選擇具有包含關(guān)鍵字 tree 的內(nèi)容，根據(jù)這兩個(gè)進(jìn)程的相對(duì)速度（這取決于兩個(gè)程序的相對(duì)復(fù)雜度和各自所分配到的 CPU 時(shí)間片），可能會(huì)發(fā)生下面這種情況，grep 準(zhǔn)備就緒開始運(yùn)行，但是輸入進(jìn)程還沒有完成，于是必須阻塞 grep 進(jìn)程，直到輸入完畢。

當(dāng)一個(gè)進(jìn)程開始運(yùn)行時(shí)，它可能會(huì)經(jīng)歷下面這幾種狀態(tài)

圖中會(huì)涉及三種狀態(tài)

1. 運(yùn)行態(tài)，運(yùn)行態(tài)指的就是進(jìn)程實(shí)際占用 CPU 時(shí)間片運(yùn)行時(shí)

2. 就緒態(tài)，就緒態(tài)指的是可運(yùn)行，但因?yàn)槠渌M(jìn)程正在運(yùn)行而處于就緒狀態(tài)

3. 阻塞態(tài)，除非某種外部事件發(fā)生，否則進(jìn)程不能運(yùn)行

邏輯上來說，運(yùn)行態(tài)和就緒態(tài)是很相似的。這兩種情況下都表示進(jìn)程可運(yùn)行，但是第二種情況沒有獲得 CPU 時(shí)間分片。第三種狀態(tài)與前兩種狀態(tài)不同的原因是這個(gè)進(jìn)程不能運(yùn)行，CPU 空閑時(shí)也不能運(yùn)行。

三種狀態(tài)會(huì)涉及四種狀態(tài)間的切換，在操作系統(tǒng)發(fā)現(xiàn)進(jìn)程不能繼續(xù)執(zhí)行時(shí)會(huì)發(fā)生狀態(tài)1的輪轉(zhuǎn)，在某些系統(tǒng)中進(jìn)程執(zhí)行系統(tǒng)調(diào)用，例如 pause，來獲取一個(gè)阻塞的狀態(tài)。在其他系統(tǒng)中包括 UNIX，當(dāng)進(jìn)程從管道或特殊文件（例如終端）中讀取沒有可用的輸入時(shí)，該進(jìn)程會(huì)被自動(dòng)終止。

轉(zhuǎn)換 2 和轉(zhuǎn)換 3 都是由進(jìn)程調(diào)度程序（操作系統(tǒng)的一部分）引起的，進(jìn)程本身不知道調(diào)度程序的存在。轉(zhuǎn)換 2 的出現(xiàn)說明進(jìn)程調(diào)度器認(rèn)定當(dāng)前進(jìn)程已經(jīng)運(yùn)行了足夠長的時(shí)間，是時(shí)候讓其他進(jìn)程運(yùn)行 CPU 時(shí)間片了。當(dāng)所有其他進(jìn)程都運(yùn)行過后，這時(shí)候該是讓第一個(gè)進(jìn)程重新獲得 CPU 時(shí)間片的時(shí)候了，就會(huì)發(fā)生轉(zhuǎn)換 3。

程序調(diào)度指的是，決定哪個(gè)進(jìn)程優(yōu)先被運(yùn)行和運(yùn)行多久，這是很重要的一點(diǎn)。已經(jīng)設(shè)計(jì)出許多算法來嘗試平衡系統(tǒng)整體效率與各個(gè)流程之間的競(jìng)爭(zhēng)需求。

當(dāng)進(jìn)程等待的一個(gè)外部事件發(fā)生時(shí)（如從外部輸入一些數(shù)據(jù)后），則發(fā)生轉(zhuǎn)換 4。如果此時(shí)沒有其他進(jìn)程在運(yùn)行，則立刻觸發(fā)轉(zhuǎn)換 3，該進(jìn)程便開始運(yùn)行，否則該進(jìn)程會(huì)處于就緒階段，等待 CPU 空閑后再輪到它運(yùn)行。

從上面的觀點(diǎn)引入了下面的模型

操作系統(tǒng)最底層的就是調(diào)度程序，在它上面有許多進(jìn)程。所有關(guān)于中斷處理、啟動(dòng)進(jìn)程和停止進(jìn)程的具體細(xì)節(jié)都隱藏在調(diào)度程序中。事實(shí)上，調(diào)度程序只是一段非常小的程序。

進(jìn)程的實(shí)現(xiàn)

操作系統(tǒng)為了執(zhí)行進(jìn)程間的切換，會(huì)維護(hù)著一張表格，這張表就是 進(jìn)程表(process table)。每個(gè)進(jìn)程占用一個(gè)進(jìn)程表項(xiàng)。該表項(xiàng)包含了進(jìn)程狀態(tài)的重要信息，包括程序計(jì)數(shù)器、堆棧指針、內(nèi)存分配狀況、所打開文件的狀態(tài)、賬號(hào)和調(diào)度信息，以及其他在進(jìn)程由運(yùn)行態(tài)轉(zhuǎn)換到就緒態(tài)或阻塞態(tài)時(shí)所必須保存的信息，從而保證該進(jìn)程隨后能再次啟動(dòng)，就像從未被中斷過一樣。

下面展示了一個(gè)典型系統(tǒng)中的關(guān)鍵字段

第一列內(nèi)容與進(jìn)程管理有關(guān)，第二列內(nèi)容與 存儲(chǔ)管理有關(guān)，第三列內(nèi)容與文件管理有關(guān)。

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

程序員需要了解的硬核知識(shí)之匯編語言(全)

現(xiàn)在我們應(yīng)該對(duì)進(jìn)程表有個(gè)大致的了解了，就可以在對(duì)單個(gè) CPU 上如何運(yùn)行多個(gè)順序進(jìn)程的錯(cuò)覺做更多的解釋。與每一 I/O 類相關(guān)聯(lián)的是一個(gè)稱作 中斷向量(interrupt vector) 的位置（靠近內(nèi)存底部的固定區(qū)域）。它包含中斷服務(wù)程序的入口地址。假設(shè)當(dāng)一個(gè)磁盤中斷發(fā)生時(shí)，用戶進(jìn)程 3 正在運(yùn)行，則中斷硬件將程序計(jì)數(shù)器、程序狀態(tài)字、有時(shí)還有一個(gè)或多個(gè)寄存器壓入堆棧，計(jì)算機(jī)隨即跳轉(zhuǎn)到中斷向量所指示的地址。這就是硬件所做的事情。然后軟件就隨即接管一切剩余的工作。

當(dāng)中斷結(jié)束后，操作系統(tǒng)會(huì)調(diào)用一個(gè) C 程序來處理中斷剩下的工作。在完成剩下的工作后，會(huì)使某些進(jìn)程就緒，接著調(diào)用調(diào)度程序，決定隨后運(yùn)行哪個(gè)進(jìn)程。然后將控制權(quán)轉(zhuǎn)移給一段匯編語言代碼，為當(dāng)前的進(jìn)程裝入寄存器值以及內(nèi)存映射并啟動(dòng)該進(jìn)程運(yùn)行，下面顯示了中斷處理和調(diào)度的過程。

1. 硬件壓入堆棧程序計(jì)數(shù)器等

2. 硬件從中斷向量裝入新的程序計(jì)數(shù)器

3. 匯編語言過程保存寄存器的值

4. 匯編語言過程設(shè)置新的堆棧

5. C 中斷服務(wù)器運(yùn)行（典型的讀和緩存寫入）

6. 調(diào)度器決定下面哪個(gè)程序先運(yùn)行

7. C 過程返回至匯編代碼

8. 匯編語言過程開始運(yùn)行新的當(dāng)前進(jìn)程

一個(gè)進(jìn)程在執(zhí)行過程中可能被中斷數(shù)千次，但關(guān)鍵每次中斷后，被中斷的進(jìn)程都返回到與中斷發(fā)生前完全相同的狀態(tài)。

線程

在傳統(tǒng)的操作系統(tǒng)中，每個(gè)進(jìn)程都有一個(gè)地址空間和一個(gè)控制線程。事實(shí)上，這是大部分進(jìn)程的定義。不過，在許多情況下，經(jīng)常存在同一地址空間中運(yùn)行多個(gè)控制線程的情形，這些線程就像是分離的進(jìn)程。下面我們就著重探討一下什么是線程

線程的使用

或許這個(gè)疑問也是你的疑問，為什么要在進(jìn)程的基礎(chǔ)上再創(chuàng)建一個(gè)線程的概念，準(zhǔn)確的說，這其實(shí)是進(jìn)程模型和線程模型的討論，回答這個(gè)問題，可能需要分三步來回答

• 多線程之間會(huì)共享同一塊地址空間和所有可用數(shù)據(jù)的能力，這是進(jìn)程所不具備的

• 線程要比進(jìn)程更輕量級(jí)，由于線程更輕，所以它比進(jìn)程更容易創(chuàng)建，也更容易撤銷。在許多系統(tǒng)中，創(chuàng)建一個(gè)線程要比創(chuàng)建一個(gè)進(jìn)程快 10 - 100 倍。

• 第三個(gè)原因可能是性能方面的探討，如果多個(gè)線程都是 CPU 密集型的，那么并不能獲得性能上的增強(qiáng)，但是如果存在著大量的計(jì)算和大量的 I/O 處理，擁有多個(gè)線程能在這些活動(dòng)中彼此重疊進(jìn)行，從而會(huì)加快應(yīng)用程序的執(zhí)行速度

多線程解決方案

現(xiàn)在考慮一個(gè)線程使用的例子：一個(gè)萬維網(wǎng)服務(wù)器，對(duì)頁面的請(qǐng)求發(fā)送給服務(wù)器，而所請(qǐng)求的頁面發(fā)送回客戶端。在多數(shù) web 站點(diǎn)上，某些頁面較其他頁面相比有更多的訪問。例如，索尼的主頁比任何一個(gè)照相機(jī)詳情介紹頁面具有更多的訪問，Web 服務(wù)器可以把獲得大量訪問的頁面集合保存在內(nèi)存中，避免到磁盤去調(diào)入這些頁面，從而改善性能。這種頁面的集合稱為 高速緩存(cache)，高速緩存也應(yīng)用在許多場(chǎng)合中，比如說 CPU 緩存。

上面是一個(gè) web 服務(wù)器的組織方式，一個(gè)叫做 調(diào)度線程(dispatcher thread) 的線程從網(wǎng)絡(luò)中讀入工作請(qǐng)求，在調(diào)度線程檢查完請(qǐng)求后，它會(huì)選擇一個(gè)空閑的（阻塞的）工作線程來處理請(qǐng)求，通常是將消息的指針寫入到每個(gè)線程關(guān)聯(lián)的特殊字中。然后調(diào)度線程會(huì)喚醒正在睡眠中的工作線程，把工作線程的狀態(tài)從阻塞態(tài)變?yōu)榫途w態(tài)。

當(dāng)工作線程啟動(dòng)后，它會(huì)檢查請(qǐng)求是否在 web 頁面的高速緩存中存在，這個(gè)高速緩存是所有線程都可以訪問的。如果高速緩存不存在這個(gè) web 頁面的話，它會(huì)調(diào)用一個(gè) read 操作從磁盤中獲取頁面并且阻塞線程直到磁盤操作完成。當(dāng)線程阻塞在硬盤操作的期間，為了完成更多的工作，調(diào)度線程可能挑選另一個(gè)線程運(yùn)行，也可能把另一個(gè)當(dāng)前就緒的工作線程投入運(yùn)行。

這種模型允許將服務(wù)器編寫為順序線程的集合，在分派線程的程序中包含一個(gè)死循環(huán)，該循環(huán)用來獲得工作請(qǐng)求并且把請(qǐng)求派給工作線程。每個(gè)工作線程的代碼包含一個(gè)從調(diào)度線程接收的請(qǐng)求，并且檢查 web 高速緩存中是否存在所需頁面，如果有，直接把該頁面返回給客戶，接著工作線程阻塞，等待一個(gè)新請(qǐng)求的到達(dá)。如果沒有，工作線程就從磁盤調(diào)入該頁面，將該頁面返回給客戶機(jī)，然后工作線程阻塞，等待一個(gè)新請(qǐng)求。

下面是調(diào)度線程和工作線程的代碼，這里假設(shè) TRUE 為常數(shù) 1 ，buf 和 page 分別是保存工作請(qǐng)求和 Web 頁面的相應(yīng)結(jié)構(gòu)。

調(diào)度線程的大致邏輯

工作線程的大致邏輯

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);
}

單線程解決方案

現(xiàn)在考慮沒有多線程的情況下，如何編寫 Web 服務(wù)器。我們很容易的就想象為單個(gè)線程了，Web 服務(wù)器的主循環(huán)獲取請(qǐng)求并檢查請(qǐng)求，并爭(zhēng)取在下一個(gè)請(qǐng)求之前完成工作。在等待磁盤操作時(shí)，服務(wù)器空轉(zhuǎn)，并且不處理任何到來的其他請(qǐng)求。結(jié)果會(huì)導(dǎo)致每秒中只有很少的請(qǐng)求被處理，所以這個(gè)例子能夠說明多線程提高了程序的并行性并提高了程序的性能。

狀態(tài)機(jī)解決方案

到現(xiàn)在為止，我們已經(jīng)有了兩種解決方案，單線程解決方案和多線程解決方案，其實(shí)還有一種解決方案就是 狀態(tài)機(jī)解決方案，它的流程如下

如果目前只有一個(gè)非阻塞版本的 read 系統(tǒng)調(diào)用可以使用，那么當(dāng)請(qǐng)求到達(dá)服務(wù)器時(shí)，這個(gè)唯一的 read 調(diào)用的線程會(huì)進(jìn)行檢查，如果能夠從高速緩存中得到響應(yīng)，那么直接返回，如果不能，則啟動(dòng)一個(gè)非阻塞的磁盤操作

服務(wù)器在表中記錄當(dāng)前請(qǐng)求的狀態(tài)，然后進(jìn)入并獲取下一個(gè)事件，緊接著下一個(gè)事件可能就是一個(gè)新工作的請(qǐng)求或是磁盤對(duì)先前操作的回答。如果是新工作的請(qǐng)求，那么就開始處理請(qǐng)求。如果是磁盤的響應(yīng)，就從表中取出對(duì)應(yīng)的狀態(tài)信息進(jìn)行處理。對(duì)于非阻塞式磁盤 I/O 而言，這種響應(yīng)一般都是信號(hào)中斷響應(yīng)。

每次服務(wù)器從某個(gè)請(qǐng)求工作的狀態(tài)切換到另一個(gè)狀態(tài)時(shí)，都必須顯示的保存或者重新裝入相應(yīng)的計(jì)算狀態(tài)。這里，每個(gè)計(jì)算都有一個(gè)被保存的狀態(tài)，存在一個(gè)會(huì)發(fā)生且使得相關(guān)狀態(tài)發(fā)生改變的事件集合，我們把這類設(shè)計(jì)稱為有限狀態(tài)機(jī)(finite-state machine)，有限狀態(tài)機(jī)被廣泛的應(yīng)用在計(jì)算機(jī)科學(xué)中。

這三種解決方案各有各的特性，多線程使得順序進(jìn)程的思想得以保留下來，并且實(shí)現(xiàn)了并行性，但是順序進(jìn)程會(huì)阻塞系統(tǒng)調(diào)用；單線程服務(wù)器保留了阻塞系統(tǒng)的簡易性，但是卻放棄了性能。有限狀態(tài)機(jī)的處理方法運(yùn)用了非阻塞調(diào)用和中斷，通過并行實(shí)現(xiàn)了高性能，但是給編程增加了困難。

經(jīng)典的線程模型

理解進(jìn)程的另一個(gè)角度是，用某種方法把相關(guān)的資源集中在一起。進(jìn)程有存放程序正文和數(shù)據(jù)以及其他資源的地址空間。這些資源包括打開的文件、子進(jìn)程、即將發(fā)生的定時(shí)器、信號(hào)處理程序、賬號(hào)信息等。把這些信息放在進(jìn)程中會(huì)比較容易管理。

另一個(gè)概念是，進(jìn)程中擁有一個(gè)執(zhí)行的線程，通常簡寫為 線程(thread)。線程會(huì)有程序計(jì)數(shù)器，用來記錄接著要執(zhí)行哪一條指令；線程還擁有寄存器，用來保存線程當(dāng)前正在使用的變量；線程還會(huì)有堆棧，用來記錄程序的執(zhí)行路徑。盡管線程必須在某個(gè)進(jìn)程中執(zhí)行，但是進(jìn)程和線程完完全全是兩個(gè)不同的概念，并且他們可以分開處理。進(jìn)程用于把資源集中在一起，而線程則是 CPU 上調(diào)度執(zhí)行的實(shí)體。

線程給進(jìn)程模型增加了一項(xiàng)內(nèi)容，即在同一個(gè)進(jìn)程中，允許彼此之間有較大的獨(dú)立性且互不干擾。在一個(gè)進(jìn)程中并行運(yùn)行多個(gè)線程類似于在一臺(tái)計(jì)算機(jī)上運(yùn)行多個(gè)進(jìn)程。在多個(gè)線程中，各個(gè)線程共享同一地址空間和其他資源。在多個(gè)進(jìn)程中，進(jìn)程共享物理內(nèi)存、磁盤、打印機(jī)和其他資源。因?yàn)榫€程會(huì)包含有一些進(jìn)程的屬性，所以線程被稱為輕量的進(jìn)程(lightweight processes)。多線程(multithreading)一詞還用于描述在同一進(jìn)程中多個(gè)線程的情況。

下圖我們可以看到三個(gè)傳統(tǒng)的進(jìn)程，每個(gè)進(jìn)程有自己的地址空間和單個(gè)控制線程。每個(gè)線程都在不同的地址空間中運(yùn)行

下圖中，我們可以看到有一個(gè)進(jìn)程三個(gè)線程的情況。每個(gè)線程都在相同的地址空間中運(yùn)行。

線程不像是進(jìn)程那樣具備較強(qiáng)的獨(dú)立性。同一個(gè)進(jìn)程中的所有線程都會(huì)有完全一樣的地址空間，這意味著它們也共享同樣的全局變量。由于每個(gè)線程都可以訪問進(jìn)程地址空間內(nèi)每個(gè)內(nèi)存地址，因此一個(gè)線程可以讀取、寫入甚至擦除另一個(gè)線程的堆棧。線程之間除了共享同一內(nèi)存空間外，還具有如下不同的內(nèi)容

上圖左邊的是同一個(gè)進(jìn)程中每個(gè)線程共享的內(nèi)容，上圖右邊是每個(gè)線程中的內(nèi)容。也就是說左邊的列表是進(jìn)程的屬性，右邊的列表是線程的屬性。

和進(jìn)程一樣，線程可以處于下面這幾種狀態(tài)：運(yùn)行中、阻塞、就緒和終止（進(jìn)程圖中沒有畫）。正在運(yùn)行的線程擁有 CPU 時(shí)間片并且狀態(tài)是運(yùn)行中。一個(gè)被阻塞的線程會(huì)等待某個(gè)釋放它的事件。例如，當(dāng)一個(gè)線程執(zhí)行從鍵盤讀入數(shù)據(jù)的系統(tǒng)調(diào)用時(shí)，該線程就被阻塞直到有輸入為止。線程通常會(huì)被阻塞，直到它等待某個(gè)外部事件的發(fā)生或者有其他線程來釋放它。線程之間的狀態(tài)轉(zhuǎn)換和進(jìn)程之間的狀態(tài)轉(zhuǎn)換是一樣的。

每個(gè)線程都會(huì)有自己的堆棧，如下圖所示

線程系統(tǒng)調(diào)用

進(jìn)程通常會(huì)從當(dāng)前的某個(gè)單線程開始，然后這個(gè)線程通過調(diào)用一個(gè)庫函數(shù)（比如 thread_create）創(chuàng)建新的線程。線程創(chuàng)建的函數(shù)會(huì)要求指定新創(chuàng)建線程的名稱。創(chuàng)建的線程通常都返回一個(gè)線程標(biāo)識(shí)符，該標(biāo)識(shí)符就是新線程的名字。

當(dāng)一個(gè)線程完成工作后，可以通過調(diào)用一個(gè)函數(shù)（比如 thread_exit）來退出。緊接著線程消失，狀態(tài)變?yōu)榻K止，不能再進(jìn)行調(diào)度。在某些線程的運(yùn)行過程中，可以通過調(diào)用函數(shù)例如 thread_join ，表示一個(gè)線程可以等待另一個(gè)線程退出。這個(gè)過程阻塞調(diào)用線程直到等待特定的線程退出。在這種情況下，線程的創(chuàng)建和終止非常類似于進(jìn)程的創(chuàng)建和終止。

另一個(gè)常見的線程是調(diào)用 thread_yield，它允許線程自動(dòng)放棄 CPU 從而讓另一個(gè)線程運(yùn)行。這樣一個(gè)調(diào)用還是很重要的，因?yàn)椴煌谶M(jìn)程，線程是無法利用時(shí)鐘中斷強(qiáng)制讓線程讓出 CPU 的。

POSIX 線程

為了使編寫可移植線程程序成為可能，IEEE 在 IEEE 標(biāo)準(zhǔn) 1003.1c 中定義了線程標(biāo)準(zhǔn)。線程包被定義為 Pthreads。大部分的 UNIX 系統(tǒng)支持它。這個(gè)標(biāo)準(zhǔn)定義了 60 多種功能調(diào)用，一一列舉不太現(xiàn)實(shí)，下面為你列舉了一些常用的系統(tǒng)調(diào)用。

POSIX線程（通常稱為pthreads）是一種獨(dú)立于語言而存在的執(zhí)行模型，以及并行執(zhí)行模型。它允許程序控制時(shí)間上重疊的多個(gè)不同的工作流程。每個(gè)工作流程都稱為一個(gè)線程，可以通過調(diào)用POSIX Threads API來實(shí)現(xiàn)對(duì)這些流程的創(chuàng)建和控制?？梢园阉斫鉃榫€程的標(biāo)準(zhǔn)。

POSIX Threads 的實(shí)現(xiàn)在許多類似且符合POSIX的操作系統(tǒng)上可用，例如 FreeBSD、NetBSD、OpenBSD、Linux、macOS、Android、Solaris，它在現(xiàn)有 Windows API 之上實(shí)現(xiàn)了pthread。

IEEE 是世界上最大的技術(shù)專業(yè)組織，致力于為人類的利益而發(fā)展技術(shù)。

所有的 Pthreads 都有特定的屬性，每一個(gè)都含有標(biāo)識(shí)符、一組寄存器（包括程序計(jì)數(shù)器）和一組存儲(chǔ)在結(jié)構(gòu)中的屬性。這個(gè)屬性包括堆棧大小、調(diào)度參數(shù)以及其他線程需要的項(xiàng)目。

新的線程會(huì)通過 pthread_create 創(chuàng)建，新創(chuàng)建的線程的標(biāo)識(shí)符會(huì)作為函數(shù)值返回。這個(gè)調(diào)用非常像是 UNIX 中的 fork 系統(tǒng)調(diào)用（除了參數(shù)之外），其中線程標(biāo)識(shí)符起著 PID 的作用，這么做的目的是為了和其他線程進(jìn)行區(qū)分。

當(dāng)線程完成指派給他的工作后，會(huì)通過 pthread_exit 來終止。這個(gè)調(diào)用會(huì)停止線程并釋放堆棧。

一般一個(gè)線程在繼續(xù)運(yùn)行前需要等待另一個(gè)線程完成它的工作并退出?？梢酝ㄟ^ pthread_join 線程調(diào)用來等待別的特定線程的終止。而要等待線程的線程標(biāo)識(shí)符作為一個(gè)參數(shù)給出。

有時(shí)會(huì)出現(xiàn)這種情況：一個(gè)線程邏輯上沒有阻塞，但感覺上它已經(jīng)運(yùn)行了足夠長的時(shí)間并且希望給另外一個(gè)線程機(jī)會(huì)去運(yùn)行。這時(shí)候可以通過 pthread_yield 來完成。

下面兩個(gè)線程調(diào)用是處理屬性的。pthread_attr_init 建立關(guān)聯(lián)一個(gè)線程的屬性結(jié)構(gòu)并初始化成默認(rèn)值，這些值（例如優(yōu)先級(jí)）可以通過修改屬性結(jié)構(gòu)的值來改變。

最后，pthread_attr_destroy 刪除一個(gè)線程的結(jié)構(gòu)，釋放它占用的內(nèi)存。它不會(huì)影響調(diào)用它的線程，這些線程會(huì)一直存在。

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

主線程在宣布它的指責(zé)之后，循環(huán) NUMBER_OF_THREADS 次，每次創(chuàng)建一個(gè)新的線程。如果線程創(chuàng)建失敗，會(huì)打印出一條信息后退出。在創(chuàng)建完成所有的工作后，主程序退出。

線程實(shí)現(xiàn)

主要有三種實(shí)現(xiàn)方式

• 在用戶空間中實(shí)現(xiàn)線程；

• 在內(nèi)核空間中實(shí)現(xiàn)線程；

• 在用戶和內(nèi)核空間中混合實(shí)現(xiàn)線程。

下面我們分開討論一下

在用戶空間中實(shí)現(xiàn)線程

第一種方法是把整個(gè)線程包放在用戶空間中，內(nèi)核對(duì)線程一無所知，它不知道線程的存在。所有的這類實(shí)現(xiàn)都有同樣的通用結(jié)構(gòu)

線程在運(yùn)行時(shí)系統(tǒng)之上運(yùn)行，運(yùn)行時(shí)系統(tǒng)是管理線程過程的集合，包括前面提到的四個(gè)過程：pthread_create, pthread_exit, pthread_join 和 pthread_yield。

運(yùn)行時(shí)系統(tǒng)(Runtime System) 也叫做運(yùn)行時(shí)環(huán)境，該運(yùn)行時(shí)系統(tǒng)提供了程序在其中運(yùn)行的環(huán)境。此環(huán)境可能會(huì)解決許多問題，包括應(yīng)用程序內(nèi)存的布局，程序如何訪問變量，在過程之間傳遞參數(shù)的機(jī)制，與操作系統(tǒng)的接口等等。編譯器根據(jù)特定的運(yùn)行時(shí)系統(tǒng)進(jìn)行假設(shè)以生成正確的代碼。通常，運(yùn)行時(shí)系統(tǒng)將負(fù)責(zé)設(shè)置和管理堆棧，并且會(huì)包含諸如垃圾收集，線程或語言內(nèi)置的其他動(dòng)態(tài)的功能。

在用戶空間管理線程時(shí)，每個(gè)進(jìn)程需要有其專用的線程表(thread table)，用來跟蹤該進(jìn)程中的線程。這些表和內(nèi)核中的進(jìn)程表類似，不過它僅僅記錄各個(gè)線程的屬性，如每個(gè)線程的程序計(jì)數(shù)器、堆棧指針、寄存器和狀態(tài)。該線程表由運(yùn)行時(shí)系統(tǒng)統(tǒng)一管理。當(dāng)一個(gè)線程轉(zhuǎn)換到就緒狀態(tài)或阻塞狀態(tài)時(shí)，在該線程表中存放重新啟動(dòng)該線程的所有信息，與內(nèi)核在進(jìn)程表中存放的信息完全一樣。

在用戶空間實(shí)現(xiàn)線程的優(yōu)勢(shì)

在用戶空間中實(shí)現(xiàn)線程要比在內(nèi)核空間中實(shí)現(xiàn)線程具有這些方面的優(yōu)勢(shì)：考慮如果在線程完成時(shí)或者是在調(diào)用 pthread_yield 時(shí)，必要時(shí)會(huì)進(jìn)程線程切換，然后線程的信息會(huì)被保存在運(yùn)行時(shí)環(huán)境所提供的線程表中，然后，線程調(diào)度程序來選擇另外一個(gè)需要運(yùn)行的線程。保存線程的狀態(tài)和調(diào)度程序都是本地過程，所以啟動(dòng)他們比進(jìn)行內(nèi)核調(diào)用效率更高。因而不需要切換到內(nèi)核，也就不需要上下文切換，也不需要對(duì)內(nèi)存高速緩存進(jìn)行刷新，因?yàn)榫€程調(diào)度非常便捷，因此效率比較高。

在用戶空間實(shí)現(xiàn)線程還有一個(gè)優(yōu)勢(shì)就是它允許每個(gè)進(jìn)程有自己定制的調(diào)度算法。例如在某些應(yīng)用程序中，那些具有垃圾收集線程的應(yīng)用程序（知道是誰了吧）就不用擔(dān)心自己線程會(huì)不會(huì)在不合適的時(shí)候停止，這是一個(gè)優(yōu)勢(shì)。用戶線程還具有較好的可擴(kuò)展性，因?yàn)閮?nèi)核空間中的內(nèi)核線程需要一些表空間和堆棧空間，如果內(nèi)核線程數(shù)量比較大，容易造成問題。

在用戶空間實(shí)現(xiàn)線程的劣勢(shì)

盡管在用戶空間實(shí)現(xiàn)線程會(huì)具有一定的性能優(yōu)勢(shì)，但是劣勢(shì)還是很明顯的，你如何實(shí)現(xiàn)阻塞系統(tǒng)調(diào)用呢？假設(shè)在還沒有任何鍵盤輸入之前，一個(gè)線程讀取鍵盤，讓線程進(jìn)行系統(tǒng)調(diào)用是不可能的，因?yàn)檫@會(huì)停止所有的線程。所以，使用線程的一個(gè)目標(biāo)是能夠讓線程進(jìn)行阻塞調(diào)用，并且要避免被阻塞的線程影響其他線程。

與阻塞調(diào)用類似的問題是缺頁中斷問題，實(shí)際上，計(jì)算機(jī)并不會(huì)把所有的程序都一次性的放入內(nèi)存中，如果某個(gè)程序發(fā)生函數(shù)調(diào)用或者跳轉(zhuǎn)指令到了一條不在內(nèi)存的指令上，就會(huì)發(fā)生頁面故障，而操作系統(tǒng)將到磁盤上取回這個(gè)丟失的指令，這就稱為缺頁故障。而在對(duì)所需的指令進(jìn)行讀入和執(zhí)行時(shí)，相關(guān)的進(jìn)程就會(huì)被阻塞。如果只有一個(gè)線程引起頁面故障，內(nèi)核由于甚至不知道有線程存在，通常會(huì)把整個(gè)進(jìn)程阻塞直到磁盤 I/O 完成為止，盡管其他的線程是可以運(yùn)行的。

另外一個(gè)問題是，如果一個(gè)線程開始運(yùn)行，該線程所在進(jìn)程中的其他線程都不能運(yùn)行，除非第一個(gè)線程自愿的放棄 CPU，在一個(gè)單進(jìn)程內(nèi)部，沒有時(shí)鐘中斷，所以不可能使用輪轉(zhuǎn)調(diào)度的方式調(diào)度線程。除非其他線程能夠以自己的意愿進(jìn)入運(yùn)行時(shí)環(huán)境，否則調(diào)度程序沒有可以調(diào)度線程的機(jī)會(huì)。

在內(nèi)核中實(shí)現(xiàn)線程

現(xiàn)在我們考慮使用內(nèi)核來實(shí)現(xiàn)線程的情況，此時(shí)不再需要運(yùn)行時(shí)環(huán)境了。另外，每個(gè)進(jìn)程中也沒有線程表。相反，在內(nèi)核中會(huì)有用來記錄系統(tǒng)中所有線程的線程表。當(dāng)某個(gè)線程希望創(chuàng)建一個(gè)新線程或撤銷一個(gè)已有線程時(shí)，它會(huì)進(jìn)行一個(gè)系統(tǒng)調(diào)用，這個(gè)系統(tǒng)調(diào)用通過對(duì)線程表的更新來完成線程創(chuàng)建或銷毀工作。

內(nèi)核中的線程表持有每個(gè)線程的寄存器、狀態(tài)和其他信息。這些信息和用戶空間中的線程信息相同，但是位置卻被放在了內(nèi)核中而不是用戶空間中。另外，內(nèi)核還維護(hù)了一張進(jìn)程表用來跟蹤系統(tǒng)狀態(tài)。

所有能夠阻塞的調(diào)用都會(huì)通過系統(tǒng)調(diào)用的方式來實(shí)現(xiàn)，當(dāng)一個(gè)線程阻塞時(shí)，內(nèi)核可以進(jìn)行選擇，是運(yùn)行在同一個(gè)進(jìn)程中的另一個(gè)線程（如果有就緒線程的話）還是運(yùn)行一個(gè)另一個(gè)進(jìn)程中的線程。但是在用戶實(shí)現(xiàn)中，運(yùn)行時(shí)系統(tǒng)始終運(yùn)行自己的線程，直到內(nèi)核剝奪它的 CPU 時(shí)間片（或者沒有可運(yùn)行的線程存在了）為止。

由于在內(nèi)核中創(chuàng)建或者銷毀線程的開銷比較大，所以某些系統(tǒng)會(huì)采用可循環(huán)利用的方式來回收線程。當(dāng)某個(gè)線程被銷毀時(shí)，就把它標(biāo)志為不可運(yùn)行的狀態(tài)，但是其內(nèi)部結(jié)構(gòu)沒有受到影響。稍后，在必須創(chuàng)建一個(gè)新線程時(shí)，就會(huì)重新啟用舊線程，把它標(biāo)志為可用狀態(tài)。

如果某個(gè)進(jìn)程中的線程造成缺頁故障后，內(nèi)核很容易的就能檢查出來是否有其他可運(yùn)行的線程，如果有的話，在等待所需要的頁面從磁盤讀入時(shí)，就選擇一個(gè)可運(yùn)行的線程運(yùn)行。這樣做的缺點(diǎn)是系統(tǒng)調(diào)用的代價(jià)比較大，所以如果線程的操作（創(chuàng)建、終止）比較多，就會(huì)帶來很大的開銷。

混合實(shí)現(xiàn)

結(jié)合用戶空間和內(nèi)核空間的優(yōu)點(diǎn)，設(shè)計(jì)人員采用了一種內(nèi)核級(jí)線程的方式，然后將用戶級(jí)線程與某些或者全部內(nèi)核線程多路復(fù)用起來

在這種模型中，編程人員可以自由控制用戶線程和內(nèi)核線程的數(shù)量，具有很大的靈活度。采用這種方法，內(nèi)核只識(shí)別內(nèi)核級(jí)線程，并對(duì)其進(jìn)行調(diào)度。其中一些內(nèi)核級(jí)線程會(huì)被多個(gè)用戶級(jí)線程多路復(fù)用。

進(jìn)程間通信

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

關(guān)于進(jìn)程間的通信，這里有三個(gè)問題

• 上面提到了第一個(gè)問題，那就是一個(gè)進(jìn)程如何傳遞消息給其他進(jìn)程。

• 第二個(gè)問題是如何確保兩個(gè)或多個(gè)線程之間不會(huì)相互干擾。例如，兩個(gè)航空公司都試圖為不同的顧客搶購飛機(jī)上的最后一個(gè)座位。

• 第三個(gè)問題是數(shù)據(jù)的先后順序的問題，如果進(jìn)程 A 產(chǎn)生數(shù)據(jù)并且進(jìn)程 B 打印數(shù)據(jù)。則進(jìn)程 B 打印數(shù)據(jù)之前需要先等 A 產(chǎn)生數(shù)據(jù)后才能夠進(jìn)行打印。

需要注意的是，這三個(gè)問題中的后面兩個(gè)問題同樣也適用于線程

第一個(gè)問題在線程間比較好解決，因?yàn)樗鼈児蚕硪粋€(gè)地址空間，它們具有相同的運(yùn)行時(shí)環(huán)境，可以想象你在用高級(jí)語言編寫多線程代碼的過程中，線程通信問題是不是比較容易解決？

另外兩個(gè)問題也同樣適用于線程，同樣的問題可用同樣的方法來解決。我們后面會(huì)慢慢討論這三個(gè)問題，你現(xiàn)在腦子中大致有個(gè)印象即可。

競(jìng)態(tài)條件

在一些操作系統(tǒng)中，協(xié)作的進(jìn)程可能共享一些彼此都能讀寫的公共資源。公共資源可能在內(nèi)存中也可能在一個(gè)共享文件。為了講清楚進(jìn)程間是如何通信的，這里我們舉一個(gè)例子：一個(gè)后臺(tái)打印程序。當(dāng)一個(gè)進(jìn)程需要打印某個(gè)文件時(shí)，它會(huì)將文件名放在一個(gè)特殊的后臺(tái)目錄(spooler directory)中。另一個(gè)進(jìn)程 打印后臺(tái)進(jìn)程(printer daemon) 會(huì)定期的檢查是否需要文件被打印，如果有的話，就打印并將該文件名從目錄下刪除。

假設(shè)我們的后臺(tái)目錄有非常多的 槽位(slot)，編號(hào)依次為 0，1，2，…，每個(gè)槽位存放一個(gè)文件名。同時(shí)假設(shè)有兩個(gè)共享變量：out，指向下一個(gè)需要打印的文件；in，指向目錄中下個(gè)空閑的槽位。可以把這兩個(gè)文件保存在一個(gè)所有進(jìn)程都能訪問的文件中，該文件的長度為兩個(gè)字。在某一時(shí)刻，0 至 3 號(hào)槽位空，4 號(hào)至 6 號(hào)槽位被占用。在同一時(shí)刻，進(jìn)程 A 和 進(jìn)程 B 都決定將一個(gè)文件排隊(duì)打印，情況如下

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

進(jìn)程 A 讀到 in 的值為 7，將 7 存在一個(gè)局部變量 next_free_slot 中。此時(shí)發(fā)生一次時(shí)鐘中斷，CPU 認(rèn)為進(jìn)程 A 已經(jīng)運(yùn)行了足夠長的時(shí)間，決定切換到進(jìn)程 B 。進(jìn)程 B 也讀取 in 的值，發(fā)現(xiàn)是 7，然后進(jìn)程 B 將 7 寫入到自己的局部變量 next_free_slot 中，在這一時(shí)刻兩個(gè)進(jìn)程都認(rèn)為下一個(gè)可用槽位是 7 。

進(jìn)程 B 現(xiàn)在繼續(xù)運(yùn)行，它會(huì)將打印文件名寫入到 slot 7 中，然后把 in 的指針更改為 8 ，然后進(jìn)程 B 離開去做其他的事情

現(xiàn)在進(jìn)程 A 開始恢復(fù)運(yùn)行，由于進(jìn)程 A 通過檢查 next_free_slot也發(fā)現(xiàn) slot 7 的槽位是空的，于是將打印文件名存入 slot 7 中，然后把 in 的值更新為 8 ，由于 slot 7 這個(gè)槽位中已經(jīng)有進(jìn)程 B 寫入的值，所以進(jìn)程 A 的打印文件名會(huì)把進(jìn)程 B 的文件覆蓋，由于打印機(jī)內(nèi)部是無法發(fā)現(xiàn)是哪個(gè)進(jìn)程更新的，它的功能比較局限，所以這時(shí)候進(jìn)程 B 永遠(yuǎn)無法打印輸出，類似這種情況，即兩個(gè)或多個(gè)線程同時(shí)對(duì)一共享數(shù)據(jù)進(jìn)行修改，從而影響程序運(yùn)行的正確性時(shí)，這種就被稱為競(jìng)態(tài)條件(race condition)。調(diào)試競(jìng)態(tài)條件是一種非常困難的工作，因?yàn)榻^大多數(shù)情況下程序運(yùn)行良好，但在極少數(shù)的情況下會(huì)發(fā)生一些無法解釋的奇怪現(xiàn)象。

臨界區(qū)

不僅共享資源會(huì)造成競(jìng)態(tài)條件，事實(shí)上共享文件、共享內(nèi)存也會(huì)造成競(jìng)態(tài)條件、那么該如何避免呢？或許一句話可以概括說明：禁止一個(gè)或多個(gè)進(jìn)程在同一時(shí)刻對(duì)共享資源（包括共享內(nèi)存、共享文件等）進(jìn)行讀寫。換句話說，我們需要一種 互斥(mutual exclusion) 條件，這也就是說，如果一個(gè)進(jìn)程在某種方式下使用共享變量和文件的話，除該進(jìn)程之外的其他進(jìn)程就禁止做這種事（訪問統(tǒng)一資源）。上面問題的糾結(jié)點(diǎn)在于，在進(jìn)程 A 對(duì)共享變量的使用未結(jié)束之前進(jìn)程 B 就使用它。在任何操作系統(tǒng)中，為了實(shí)現(xiàn)互斥操作而選用適當(dāng)?shù)脑Z是一個(gè)主要的設(shè)計(jì)問題，接下來我們會(huì)著重探討一下。

避免競(jìng)爭(zhēng)問題的條件可以用一種抽象的方式去描述。大部分時(shí)間，進(jìn)程都會(huì)忙于內(nèi)部計(jì)算和其他不會(huì)導(dǎo)致競(jìng)爭(zhēng)條件的計(jì)算。然而，有時(shí)候進(jìn)程會(huì)訪問共享內(nèi)存或文件，或者做一些能夠?qū)е赂?jìng)態(tài)條件的操作。我們把對(duì)共享內(nèi)存進(jìn)行訪問的程序片段稱作 臨界區(qū)域(critical region) 或 臨界區(qū)(critical section)。如果我們能夠正確的操作，使兩個(gè)不同進(jìn)程不可能同時(shí)處于臨界區(qū)，就能避免競(jìng)爭(zhēng)條件，這也是從操作系統(tǒng)設(shè)計(jì)角度來進(jìn)行的。

盡管上面這種設(shè)計(jì)避免了競(jìng)爭(zhēng)條件，但是不能確保并發(fā)線程同時(shí)訪問共享數(shù)據(jù)的正確性和高效性。一個(gè)好的解決方案，應(yīng)該包含下面四種條件

1. 任何時(shí)候兩個(gè)進(jìn)程不能同時(shí)處于臨界區(qū)

2. 不應(yīng)對(duì) CPU 的速度和數(shù)量做任何假設(shè)

3. 位于臨界區(qū)外的進(jìn)程不得阻塞其他進(jìn)程

4. 不能使任何進(jìn)程無限等待進(jìn)入臨界區(qū)

從抽象的角度來看，我們通常希望進(jìn)程的行為如上圖所示，在 t1 時(shí)刻，進(jìn)程 A 進(jìn)入臨界區(qū)，在 t2 的時(shí)刻，進(jìn)程 B 嘗試進(jìn)入臨界區(qū)，因?yàn)榇藭r(shí)進(jìn)程 A 正在處于臨界區(qū)中，所以進(jìn)程 B 會(huì)阻塞直到 t3 時(shí)刻進(jìn)程 A 離開臨界區(qū)，此時(shí)進(jìn)程 B 能夠允許進(jìn)入臨界區(qū)。最后，在 t4 時(shí)刻，進(jìn)程 B 離開臨界區(qū)，系統(tǒng)恢復(fù)到?jīng)]有進(jìn)程的原始狀態(tài)。

忙等互斥

下面我們會(huì)繼續(xù)探討實(shí)現(xiàn)互斥的各種設(shè)計(jì)，在這些方案中，當(dāng)一個(gè)進(jìn)程正忙于更新其關(guān)鍵區(qū)域的共享內(nèi)存時(shí)，沒有其他進(jìn)程會(huì)進(jìn)入其關(guān)鍵區(qū)域，也不會(huì)造成影響。

屏蔽中斷

在單處理器系統(tǒng)上，最簡單的解決方案是讓每個(gè)進(jìn)程在進(jìn)入臨界區(qū)后立即屏蔽所有中斷，并在離開臨界區(qū)之前重新啟用它們。屏蔽中斷后，時(shí)鐘中斷也會(huì)被屏蔽。CPU 只有發(fā)生時(shí)鐘中斷或其他中斷時(shí)才會(huì)進(jìn)行進(jìn)程切換。這樣，在屏蔽中斷后 CPU 不會(huì)切換到其他進(jìn)程。所以，一旦某個(gè)進(jìn)程屏蔽中斷之后，它就可以檢查和修改共享內(nèi)存，而不用擔(dān)心其他進(jìn)程介入訪問共享數(shù)據(jù)。

這個(gè)方案可行嗎？進(jìn)程進(jìn)入臨界區(qū)域是由誰決定的呢？不是用戶進(jìn)程嗎？當(dāng)進(jìn)程進(jìn)入臨界區(qū)域后，用戶進(jìn)程關(guān)閉中斷，如果經(jīng)過一段較長時(shí)間后進(jìn)程沒有離開，那么中斷不就一直啟用不了，結(jié)果會(huì)如何？可能會(huì)造成整個(gè)系統(tǒng)的終止。而且如果是多處理器的話，屏蔽中斷僅僅對(duì)執(zhí)行 disable 指令的 CPU 有效。其他 CPU 仍將繼續(xù)運(yùn)行，并可以訪問共享內(nèi)存。

另一方面，對(duì)內(nèi)核來說，當(dāng)它在執(zhí)行更新變量或列表的幾條指令期間將中斷屏蔽是很方便的。例如，如果多個(gè)進(jìn)程處理就緒列表中的時(shí)候發(fā)生中斷，則可能會(huì)發(fā)生競(jìng)態(tài)條件的出現(xiàn)。所以，屏蔽中斷對(duì)于操作系統(tǒng)本身來說是一項(xiàng)很有用的技術(shù)，但是對(duì)于用戶線程來說，屏蔽中斷卻不是一項(xiàng)通用的互斥機(jī)制。

鎖變量

作為第二種嘗試，可以尋找一種軟件層面解決方案?？紤]有單個(gè)共享的（鎖）變量，初始為值為 0 。當(dāng)一個(gè)線程想要進(jìn)入關(guān)鍵區(qū)域時(shí)，它首先會(huì)查看鎖的值是否為 0 ，如果鎖的值是 0 ，進(jìn)程會(huì)把它設(shè)置為 1 并讓進(jìn)程進(jìn)入關(guān)鍵區(qū)域。如果鎖的狀態(tài)是 1，進(jìn)程會(huì)等待直到鎖變量的值變?yōu)?0 。因此，鎖變量的值是 0 則意味著沒有線程進(jìn)入關(guān)鍵區(qū)域。如果是 1 則意味著有進(jìn)程在關(guān)鍵區(qū)域內(nèi)。我們對(duì)上圖修改后，如下所示

這種設(shè)計(jì)方式是否正確呢？是否存在紕漏呢？假設(shè)一個(gè)進(jìn)程讀出鎖變量的值并發(fā)現(xiàn)它為 0 ，而恰好在它將其設(shè)置為 1 之前，另一個(gè)進(jìn)程調(diào)度運(yùn)行，讀出鎖的變量為0 ，并將鎖的變量設(shè)置為 1 。然后第一個(gè)線程運(yùn)行，把鎖變量的值再次設(shè)置為 1，此時(shí)，臨界區(qū)域就會(huì)有兩個(gè)進(jìn)程在同時(shí)運(yùn)行。

也許有的讀者可以這么認(rèn)為，在進(jìn)入前檢查一次，在要離開的關(guān)鍵區(qū)域再檢查一次不就解決了嗎？實(shí)際上這種情況也是于事無補(bǔ)，因?yàn)樵诘诙螜z查期間其他線程仍有可能修改鎖變量的值，換句話說，這種 set-before-check 不是一種 原子性 操作，所以同樣還會(huì)發(fā)生競(jìng)爭(zhēng)條件。

嚴(yán)格輪詢法

第三種互斥的方式先拋出來一段代碼，這里的程序是用 C 語言編寫，之所以采用 C 是因?yàn)椴僮飨到y(tǒng)普遍是用 C 來編寫的（偶爾會(huì)用 C++），而基本不會(huì)使用 Java 、Modula3 或 Pascal 這樣的語言，Java 中的 native 關(guān)鍵字底層也是 C 或 C++ 編寫的源碼。對(duì)于編寫操作系統(tǒng)而言，需要使用 C 語言這種強(qiáng)大、高效、可預(yù)知和有特性的語言，而對(duì)于 Java ，它是不可預(yù)知的，因?yàn)樗陉P(guān)鍵時(shí)刻會(huì)用完存儲(chǔ)器，而在不合適的時(shí)候會(huì)調(diào)用垃圾回收機(jī)制回收內(nèi)存。在 C 語言中，這種情況不會(huì)發(fā)生，C 語言中不會(huì)主動(dòng)調(diào)用垃圾回收回收內(nèi)存。有關(guān) C 、C++ 、Java 和其他四種語言的比較可以參考 鏈接

進(jìn)程 0 的代碼

while(TRUE){
  while(turn != 0){
    /* 進(jìn)入關(guān)鍵區(qū)域 */
    critical_region();
    turn = 1;
    /* 離開關(guān)鍵區(qū)域 */
    noncritical_region();
  }
}

進(jìn)程 1 的代碼

在上面代碼中，變量 turn，初始值為 0 ，用于記錄輪到那個(gè)進(jìn)程進(jìn)入臨界區(qū)，并檢查或更新共享內(nèi)存。開始時(shí)，進(jìn)程 0 檢查 turn，發(fā)現(xiàn)其值為 0 ，于是進(jìn)入臨界區(qū)。進(jìn)程 1 也發(fā)現(xiàn)其值為 0 ，所以在一個(gè)等待循環(huán)中不停的測(cè)試 turn，看其值何時(shí)變?yōu)?1。連續(xù)檢查一個(gè)變量直到某個(gè)值出現(xiàn)為止，這種方法稱為 忙等待(busywaiting)。由于這種方式浪費(fèi) CPU 時(shí)間，所以這種方式通常應(yīng)該要避免。只有在有理由認(rèn)為等待時(shí)間是非常短的情況下，才能夠使用忙等待。用于忙等待的鎖，稱為 自旋鎖(spinlock)。

進(jìn)程 0 離開臨界區(qū)時(shí)，它將 turn 的值設(shè)置為 1，以便允許進(jìn)程 1 進(jìn)入其臨界區(qū)。假設(shè)進(jìn)程 1 很快便離開了臨界區(qū)，則此時(shí)兩個(gè)進(jìn)程都處于臨界區(qū)之外，turn 的值又被設(shè)置為 0 ?，F(xiàn)在進(jìn)程 0 很快就執(zhí)行完了整個(gè)循環(huán)，它退出臨界區(qū)，并將 turn 的值設(shè)置為 1。此時(shí)，turn 的值為 1，兩個(gè)進(jìn)程都在其臨界區(qū)外執(zhí)行。

突然，進(jìn)程 0 結(jié)束了非臨界區(qū)的操作并返回到循環(huán)的開始。但是，這時(shí)它不能進(jìn)入臨界區(qū)，因?yàn)?turn 的當(dāng)前值為 1，此時(shí)進(jìn)程 1 還忙于非臨界區(qū)的操作，進(jìn)程 0 只能繼續(xù) while 循環(huán)，直到進(jìn)程 1 把 turn 的值改為 0 。這說明，在一個(gè)進(jìn)程比另一個(gè)進(jìn)程執(zhí)行速度慢了很多的情況下，輪流進(jìn)入臨界區(qū)并不是一個(gè)好的方法。

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

Peterson 解法

荷蘭數(shù)學(xué)家 T.Dekker 通過將鎖變量與警告變量相結(jié)合，最早提出了一個(gè)不需要嚴(yán)格輪換的軟件互斥算法，關(guān)于 Dekker 的算法，參考 鏈接

后來， G.L.Peterson 發(fā)現(xiàn)了一種簡單很多的互斥算法，它的算法如下

#define FALSE 0
#define TRUE  1
/* 進(jìn)程數(shù)量 */
#define N     2                                                    

/* 現(xiàn)在輪到誰 */
int turn;                    

/* 所有值初始化為 0 (FALSE) */
int interested[N];                                            

/* 進(jìn)程是 0 或 1 */
void enter_region(int process){                    

  /* 另一個(gè)進(jìn)程號(hào) */
  int other;                                                        

  /* 另一個(gè)進(jìn)程 */
  other = 1 - process;                

  /* 表示愿意進(jìn)入臨界區(qū) */
  interested[process] = TRUE;                        
  turn = process;

  /* 空循環(huán) */
  while(turn == process 
        && interested[other] == true){} 

}

void leave_region(int process){

  /* 表示離開臨界區(qū) */
  interested[process] == FALSE;                 
}

在使用共享變量時(shí)（即進(jìn)入其臨界區(qū)）之前，各個(gè)進(jìn)程使用各自的進(jìn)程號(hào) 0 或 1 作為參數(shù)來調(diào)用 enter_region，這個(gè)函數(shù)調(diào)用在需要時(shí)將使進(jìn)程等待，直到能夠安全的臨界區(qū)。在完成對(duì)共享變量的操作之后，進(jìn)程將調(diào)用 leave_region 表示操作完成，并且允許其他進(jìn)程進(jìn)入。

現(xiàn)在來看看這個(gè)辦法是如何工作的。一開始，沒有任何進(jìn)程處于臨界區(qū)中，現(xiàn)在進(jìn)程 0 調(diào)用 enter_region。它通過設(shè)置數(shù)組元素和將 turn 置為 0 來表示它希望進(jìn)入臨界區(qū)。由于進(jìn)程 1 并不想進(jìn)入臨界區(qū)，所以 enter_region 很快便返回。如果進(jìn)程現(xiàn)在調(diào)用 enter_region，進(jìn)程 1 將在此處掛起直到 interested[0] 變?yōu)?FALSE，這種情況只有在進(jìn)程 0 調(diào)用 leave_region 退出臨界區(qū)時(shí)才會(huì)發(fā)生。

那么上面討論的是順序進(jìn)入的情況，現(xiàn)在來考慮一種兩個(gè)進(jìn)程同時(shí)調(diào)用 enter_region 的情況。它們都將自己的進(jìn)程存入 turn，但只有最后保存進(jìn)去的進(jìn)程號(hào)才有效，前一個(gè)進(jìn)程的進(jìn)程號(hào)因?yàn)橹貙懚鴣G失。假如進(jìn)程 1 是最后存入的，則 turn 為 1 。當(dāng)兩個(gè)進(jìn)程都運(yùn)行到 while 的時(shí)候，進(jìn)程 0 將不會(huì)循環(huán)并進(jìn)入臨界區(qū)，而進(jìn)程 1 將會(huì)無限循環(huán)且不會(huì)進(jìn)入臨界區(qū)，直到進(jìn)程 0 退出位置。

TSL 指令

現(xiàn)在來看一種需要硬件幫助的方案。一些計(jì)算機(jī)，特別是那些設(shè)計(jì)為多處理器的計(jì)算機(jī)，都會(huì)有下面這條指令

稱為 測(cè)試并加鎖(test and set lock)，它將一個(gè)內(nèi)存字 lock 讀到寄存器 RX 中，然后在該內(nèi)存地址上存儲(chǔ)一個(gè)非零值。讀寫指令能保證是一體的，不可分割的，一同執(zhí)行的。在這個(gè)指令結(jié)束之前其他處理器均不允許訪問內(nèi)存。執(zhí)行 TSL 指令的 CPU 將會(huì)鎖住內(nèi)存總線，用來禁止其他 CPU 在這個(gè)指令結(jié)束之前訪問內(nèi)存。

很重要的一點(diǎn)是鎖住內(nèi)存總線和禁用中斷不一樣。禁用中斷并不能保證一個(gè)處理器在讀寫操作之間另一個(gè)處理器對(duì)內(nèi)存的讀寫。也就是說，在處理器 1 上屏蔽中斷對(duì)處理器 2 沒有影響。讓處理器 2 遠(yuǎn)離內(nèi)存直到處理器 1 完成讀寫的最好的方式就是鎖住總線。這需要一個(gè)特殊的硬件（基本上，一根總線就可以確保總線由鎖住它的處理器使用，而其他的處理器不能使用）

為了使用 TSL 指令，要使用一個(gè)共享變量 lock 來協(xié)調(diào)對(duì)共享內(nèi)存的訪問。當(dāng) lock 為 0 時(shí)，任何進(jìn)程都可以使用 TSL 指令將其設(shè)置為 1，并讀寫共享內(nèi)存。當(dāng)操作結(jié)束時(shí)，進(jìn)程使用 move 指令將 lock 的值重新設(shè)置為 0 。

這條指令如何防止兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)呢？下面是解決方案

enter_region:
            | 復(fù)制鎖到寄存器并將鎖設(shè)為1
            TSL REGISTER,LOCK              
            | 鎖是 0 嗎？
          CMP REGISTER,#0                             
          | 若不是零，說明鎖已被設(shè)置，所以循環(huán)
          JNE enter_region                            
          | 返回調(diào)用者，進(jìn)入臨界區(qū)
          RET                                              

leave_region:

            | 在鎖中存入 0
            MOVE LOCK,#0                  
      | 返回調(diào)用者
          RET                                              

我們可以看到這個(gè)解決方案的思想和 Peterson 的思想很相似。假設(shè)存在如下共 4 指令的匯編語言程序。第一條指令將 lock 原來的值復(fù)制到寄存器中并將 lock 設(shè)置為 1 ，隨后這個(gè)原來的值和 0 做對(duì)比。如果它不是零，說明之前已經(jīng)被加過鎖，則程序返回到開始并再次測(cè)試。經(jīng)過一段時(shí)間后（可長可短），該值變?yōu)?0 （當(dāng)前處于臨界區(qū)中的進(jìn)程退出臨界區(qū)時(shí)），于是過程返回，此時(shí)已加鎖。要清除這個(gè)鎖也比較簡單，程序只需要將 0 存入 lock 即可，不需要特殊的同步指令。

現(xiàn)在有了一種很明確的做法，那就是進(jìn)程在進(jìn)入臨界區(qū)之前會(huì)先調(diào)用 enter_region，判斷是否進(jìn)行循環(huán)，如果lock 的值是 1 ，進(jìn)行無限循環(huán)，如果 lock 是 0，不進(jìn)入循環(huán)并進(jìn)入臨界區(qū)。在進(jìn)程從臨界區(qū)返回時(shí)它調(diào)用 leave_region，這會(huì)把 lock 設(shè)置為 0 。與基于臨界區(qū)問題的所有解法一樣，進(jìn)程必須在正確的時(shí)間調(diào)用 enter_region 和 leave_region ，解法才能奏效。

還有一個(gè)可以替換 TSL 的指令是 XCHG，它原子性的交換了兩個(gè)位置的內(nèi)容，例如，一個(gè)寄存器與一個(gè)內(nèi)存字，代碼如下

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

睡眠與喚醒

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

這種方式不但浪費(fèi)了 CPU 時(shí)間，而且還可能引起意想不到的結(jié)果?？紤]一臺(tái)計(jì)算機(jī)上有兩個(gè)進(jìn)程，這兩個(gè)進(jìn)程具有不同的優(yōu)先級(jí)，H 是屬于優(yōu)先級(jí)比較高的進(jìn)程，L 是屬于優(yōu)先級(jí)比較低的進(jìn)程。進(jìn)程調(diào)度的規(guī)則是不論何時(shí)只要 H 進(jìn)程處于就緒態(tài) H 就開始運(yùn)行。在某一時(shí)刻，L 處于臨界區(qū)中，此時(shí) H 變?yōu)榫途w態(tài)，準(zhǔn)備運(yùn)行（例如，一條 I/O 操作結(jié)束）?，F(xiàn)在 H 要開始忙等，但由于當(dāng) H 就緒時(shí) L 就不會(huì)被調(diào)度，L 從來不會(huì)有機(jī)會(huì)離開關(guān)鍵區(qū)域，所以 H 會(huì)變成死循環(huán)，有時(shí)將這種情況稱為優(yōu)先級(jí)反轉(zhuǎn)問題(priority inversion problem)。

現(xiàn)在讓我們看一下進(jìn)程間的通信原語，這些原語在不允許它們進(jìn)入關(guān)鍵區(qū)域之前會(huì)阻塞而不是浪費(fèi) CPU 時(shí)間，最簡單的是 sleep 和 wakeup。Sleep 是一個(gè)能夠造成調(diào)用者阻塞的系統(tǒng)調(diào)用，也就是說，這個(gè)系統(tǒng)調(diào)用會(huì)暫停直到其他進(jìn)程喚醒它。wakeup 調(diào)用有一個(gè)參數(shù)，即要喚醒的進(jìn)程。還有一種方式是 wakeup 和 sleep 都有一個(gè)參數(shù)，即 sleep 和 wakeup 需要匹配的內(nèi)存地址。

生產(chǎn)者-消費(fèi)者問題

作為這些私有原語的例子，讓我們考慮生產(chǎn)者-消費(fèi)者(producer-consumer) 問題，也稱作 有界緩沖區(qū)(bounded-buffer) 問題。兩個(gè)進(jìn)程共享一個(gè)公共的固定大小的緩沖區(qū)。其中一個(gè)是生產(chǎn)者(producer)，將信息放入緩沖區(qū)， 另一個(gè)是消費(fèi)者(consumer)，會(huì)從緩沖區(qū)中取出。也可以把這個(gè)問題一般化為 m 個(gè)生產(chǎn)者和 n 個(gè)消費(fèi)者的問題，但是我們這里只討論一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者的情況，這樣可以簡化實(shí)現(xiàn)方案。

如果緩沖隊(duì)列已滿，那么當(dāng)生產(chǎn)者仍想要將數(shù)據(jù)寫入緩沖區(qū)的時(shí)候，會(huì)出現(xiàn)問題。它的解決辦法是讓生產(chǎn)者睡眠，也就是阻塞生產(chǎn)者。等到消費(fèi)者從緩沖區(qū)中取出一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)時(shí)再喚醒它。同樣的，當(dāng)消費(fèi)者試圖從緩沖區(qū)中取數(shù)據(jù)，但是發(fā)現(xiàn)緩沖區(qū)為空時(shí)，消費(fèi)者也會(huì)睡眠，阻塞。直到生產(chǎn)者向其中放入一個(gè)新的數(shù)據(jù)。

這個(gè)邏輯聽起來比較簡單，而且這種方式也需要一種稱作 監(jiān)聽 的變量，這個(gè)變量用于監(jiān)視緩沖區(qū)的數(shù)據(jù)，我們暫定為 count，如果緩沖區(qū)最多存放 N 個(gè)數(shù)據(jù)項(xiàng)，生產(chǎn)者會(huì)每次判斷 count 是否達(dá)到 N，否則生產(chǎn)者向緩沖區(qū)放入一個(gè)數(shù)據(jù)項(xiàng)并增量 count 的值。消費(fèi)者的邏輯也很相似：首先測(cè)試 count 的值是否為 0 ，如果為 0 則消費(fèi)者睡眠、阻塞，否則會(huì)從緩沖區(qū)取出數(shù)據(jù)并使 count 數(shù)量遞減。每個(gè)進(jìn)程也會(huì)檢查檢查是否其他線程是否應(yīng)該被喚醒，如果應(yīng)該被喚醒，那么就喚醒該線程。下面是生產(chǎn)者消費(fèi)者的代碼

/* 緩沖區(qū) slot 槽的數(shù)量 */
#define N 100                        
/* 緩沖區(qū)數(shù)據(jù)的數(shù)量 */
int count = 0                                        

// 生產(chǎn)者
void producer(void){
  int item;

  /* 無限循環(huán) */
  while(TRUE){                
    /* 生成下一項(xiàng)數(shù)據(jù) */
    item = produce_item()                
    /* 如果緩存區(qū)是滿的，就會(huì)阻塞 */
    if(count == N){
      sleep();                                    
    }

    /* 把當(dāng)前數(shù)據(jù)放在緩沖區(qū)中 */
    insert_item(item);
    /* 增加緩沖區(qū) count 的數(shù)量 */
    count = count + 1;                    
    if(count == 1){
      /* 緩沖區(qū)是否為空？ */
      wakeup(consumer);                    
    }
  }
}

// 消費(fèi)者
void consumer(void){

  int item;

  /* 無限循環(huán) */
  while(TRUE){
    /* 如果緩沖區(qū)是空的，就會(huì)進(jìn)行阻塞 */
      if(count == 0){                         
      sleep();
    }
    /* 從緩沖區(qū)中取出一個(gè)數(shù)據(jù) */
       item = remove_item();           
    /* 將緩沖區(qū)的 count 數(shù)量減一 */
    count = count - 1
    /* 緩沖區(qū)滿嘛？ */
    if(count == N - 1){                    
      wakeup(producer);        
    }
    /* 打印數(shù)據(jù)項(xiàng) */
    consumer_item(item);                
  }

}

為了在 C 語言中描述像是 sleep 和 wakeup 的系統(tǒng)調(diào)用，我們將以庫函數(shù)調(diào)用的形式來表示。它們不是 C 標(biāo)準(zhǔn)庫的一部分，但可以在實(shí)際具有這些系統(tǒng)調(diào)用的任何系統(tǒng)上使用。代碼中未實(shí)現(xiàn)的 insert_item 和 remove_item 用來記錄將數(shù)據(jù)項(xiàng)放入緩沖區(qū)和從緩沖區(qū)取出數(shù)據(jù)等。

現(xiàn)在讓我們回到生產(chǎn)者-消費(fèi)者問題上來，上面代碼中會(huì)產(chǎn)生競(jìng)爭(zhēng)條件，因?yàn)?count 這個(gè)變量是暴露在大眾視野下的。有可能出現(xiàn)下面這種情況：緩沖區(qū)為空，此時(shí)消費(fèi)者剛好讀取 count 的值發(fā)現(xiàn)它為 0 。此時(shí)調(diào)度程序決定暫停消費(fèi)者并啟動(dòng)運(yùn)行生產(chǎn)者。生產(chǎn)者生產(chǎn)了一條數(shù)據(jù)并把它放在緩沖區(qū)中，然后增加 count 的值，并注意到它的值是 1 。由于 count 為 0，消費(fèi)者必須處于睡眠狀態(tài)，因此生產(chǎn)者調(diào)用 wakeup 來喚醒消費(fèi)者。但是，消費(fèi)者此時(shí)在邏輯上并沒有睡眠，所以 wakeup 信號(hào)會(huì)丟失。當(dāng)消費(fèi)者下次啟動(dòng)后，它會(huì)查看之前讀取的 count 值，發(fā)現(xiàn)它的值是 0 ，然后在此進(jìn)行睡眠。不久之后生產(chǎn)者會(huì)填滿整個(gè)緩沖區(qū)，在這之后會(huì)阻塞，這樣一來兩個(gè)進(jìn)程將永遠(yuǎn)睡眠下去。

引起上面問題的本質(zhì)是 喚醒尚未進(jìn)行睡眠狀態(tài)的進(jìn)程會(huì)導(dǎo)致喚醒丟失。如果它沒有丟失，則一切都很正常。一種快速解決上面問題的方式是增加一個(gè)喚醒等待位(wakeup waiting bit)。當(dāng)一個(gè) wakeup 信號(hào)發(fā)送給仍在清醒的進(jìn)程后，該位置為 1 。之后，當(dāng)進(jìn)程嘗試睡眠的時(shí)候，如果喚醒等待位為 1 ，則該位清除，而進(jìn)程仍然保持清醒。

然而，當(dāng)進(jìn)程數(shù)量有許多的時(shí)候，這時(shí)你可以說通過增加喚醒等待位的數(shù)量來喚醒等待位，于是就有了 2、4、6、8 個(gè)喚醒等待位，但是并沒有從根本上解決問題。

信號(hào)量

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

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

原子性操作指的是在計(jì)算機(jī)科學(xué)的許多其他領(lǐng)域中，一組相關(guān)操作全部執(zhí)行而沒有中斷或根本不執(zhí)行。

up 操作會(huì)使信號(hào)量的值 + 1。如果一個(gè)或者多個(gè)進(jìn)程在信號(hào)量上睡眠，無法完成一個(gè)先前的 down 操作，則由系統(tǒng)選擇其中一個(gè)并允許該程完成 down 操作。因此，對(duì)一個(gè)進(jìn)程在其上睡眠的信號(hào)量執(zhí)行一次 up 操作之后，該信號(hào)量的值仍然是 0 ，但在其上睡眠的進(jìn)程卻少了一個(gè)。信號(hào)量的值增 1 和喚醒一個(gè)進(jìn)程同樣也是不可分割的。不會(huì)有某個(gè)進(jìn)程因執(zhí)行 up 而阻塞，正如在前面的模型中不會(huì)有進(jìn)程因執(zhí)行 wakeup 而阻塞是一樣的道理。

用信號(hào)量解決生產(chǎn)者 - 消費(fèi)者問題

用信號(hào)量解決丟失的 wakeup 問題，代碼如下

為了確保信號(hào)量能正確工作，最重要的是要采用一種不可分割的方式來實(shí)現(xiàn)它。通常是將 up 和 down 作為系統(tǒng)調(diào)用來實(shí)現(xiàn)。而且操作系統(tǒng)只需在執(zhí)行以下操作時(shí)暫時(shí)屏蔽全部中斷：檢查信號(hào)量、更新、必要時(shí)使進(jìn)程睡眠。由于這些操作僅需要非常少的指令，因此中斷不會(huì)造成影響。如果使用多個(gè) CPU，那么信號(hào)量應(yīng)該被鎖進(jìn)行保護(hù)。使用 TSL 或者 XCHG 指令用來確保同一時(shí)刻只有一個(gè) CPU 對(duì)信號(hào)量進(jìn)行操作。

使用 TSL 或者 XCHG 來防止幾個(gè) CPU 同時(shí)訪問一個(gè)信號(hào)量，與生產(chǎn)者或消費(fèi)者使用忙等待來等待其他騰出或填充緩沖區(qū)是完全不一樣的。前者的操作僅需要幾個(gè)毫秒，而生產(chǎn)者或消費(fèi)者可能需要任意長的時(shí)間。

上面這個(gè)解決方案使用了三種信號(hào)量：一個(gè)稱為 full，用來記錄充滿的緩沖槽數(shù)目；一個(gè)稱為 empty，記錄空的緩沖槽數(shù)目；一個(gè)稱為 mutex，用來確保生產(chǎn)者和消費(fèi)者不會(huì)同時(shí)進(jìn)入緩沖區(qū)。Full 被初始化為 0 ，empty 初始化為緩沖區(qū)中插槽數(shù)，mutex 初始化為 1。信號(hào)量初始化為 1 并且由兩個(gè)或多個(gè)進(jìn)程使用，以確保它們中同時(shí)只有一個(gè)可以進(jìn)入關(guān)鍵區(qū)域的信號(hào)被稱為 二進(jìn)制信號(hào)量(binary semaphores)。如果每個(gè)進(jìn)程都在進(jìn)入關(guān)鍵區(qū)域之前執(zhí)行 down 操作，而在離開關(guān)鍵區(qū)域之后執(zhí)行 up 操作，則可以確保相互互斥。

現(xiàn)在我們有了一個(gè)好的進(jìn)程間原語的保證。然后我們?cè)賮砜匆幌轮袛嗟捻樞虮ＷC

1. 硬件壓入堆棧程序計(jì)數(shù)器等

2. 硬件從中斷向量裝入新的程序計(jì)數(shù)器

3. 匯編語言過程保存寄存器的值

4. 匯編語言過程設(shè)置新的堆棧

5. C 中斷服務(wù)器運(yùn)行（典型的讀和緩存寫入）

6. 調(diào)度器決定下面哪個(gè)程序先運(yùn)行

7. C 過程返回至匯編代碼

8. 匯編語言過程開始運(yùn)行新的當(dāng)前進(jìn)程

在使用信號(hào)量的系統(tǒng)中，隱藏中斷的自然方法是讓每個(gè) I/O 設(shè)備都配備一個(gè)信號(hào)量，該信號(hào)量最初設(shè)置為0。在 I/O 設(shè)備啟動(dòng)后，中斷處理程序立刻對(duì)相關(guān)聯(lián)的信號(hào)執(zhí)行一個(gè) down 操作，于是進(jìn)程立即被阻塞。當(dāng)中斷進(jìn)入時(shí)，中斷處理程序隨后對(duì)相關(guān)的信號(hào)量執(zhí)行一個(gè) up操作，能夠使已經(jīng)阻止的進(jìn)程恢復(fù)運(yùn)行。在上面的中斷處理步驟中，其中的第 5 步 C 中斷服務(wù)器運(yùn)行 就是中斷處理程序在信號(hào)量上執(zhí)行的一個(gè) up 操作，所以在第 6 步中，操作系統(tǒng)能夠執(zhí)行設(shè)備驅(qū)動(dòng)程序。當(dāng)然，如果有幾個(gè)進(jìn)程已經(jīng)處于就緒狀態(tài)，調(diào)度程序可能會(huì)選擇接下來運(yùn)行一個(gè)更重要的進(jìn)程，我們會(huì)在后面討論調(diào)度的算法。

上面的代碼實(shí)際上是通過兩種不同的方式來使用信號(hào)量的，而這兩種信號(hào)量之間的區(qū)別也是很重要的。mutex 信號(hào)量用于互斥。它用于確保任意時(shí)刻只有一個(gè)進(jìn)程能夠?qū)彌_區(qū)和相關(guān)變量進(jìn)行讀寫?；コ馐怯糜诒苊膺M(jìn)程混亂所必須的一種操作。

另外一個(gè)信號(hào)量是關(guān)于同步(synchronization)的。full 和 empty 信號(hào)量用于確保事件的發(fā)生或者不發(fā)生。在這個(gè)事例中，它們確保了緩沖區(qū)滿時(shí)生產(chǎn)者停止運(yùn)行；緩沖區(qū)為空時(shí)消費(fèi)者停止運(yùn)行。這兩個(gè)信號(hào)量的使用與 mutex 不同。

互斥量

如果不需要信號(hào)量的計(jì)數(shù)能力時(shí)，可以使用信號(hào)量的一個(gè)簡單版本，稱為 mutex(互斥量)。互斥量的優(yōu)勢(shì)就在于在一些共享資源和一段代碼中保持互斥。由于互斥的實(shí)現(xiàn)既簡單又有效，這使得互斥量在實(shí)現(xiàn)用戶空間線程包時(shí)非常有用。

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

mutex 使用兩個(gè)過程，當(dāng)一個(gè)線程（或者進(jìn)程）需要訪問關(guān)鍵區(qū)域時(shí)，會(huì)調(diào)用 mutex_lock 進(jìn)行加鎖。如果互斥鎖當(dāng)前處于解鎖狀態(tài)（表示關(guān)鍵區(qū)域可用），則調(diào)用成功，并且調(diào)用線程可以自由進(jìn)入關(guān)鍵區(qū)域。

另一方面，如果 mutex 互斥量已經(jīng)鎖定的話，調(diào)用線程會(huì)阻塞直到關(guān)鍵區(qū)域內(nèi)的線程執(zhí)行完畢并且調(diào)用了 mutex_unlock 。如果多個(gè)線程在 mutex 互斥量上阻塞，將隨機(jī)選擇一個(gè)線程并允許它獲得鎖。

由于 mutex 互斥量非常簡單，所以只要有 TSL 或者是 XCHG 指令，就可以很容易地在用戶空間實(shí)現(xiàn)它們。用于用戶級(jí)線程包的 mutex_lock 和 mutex_unlock 代碼如下，XCHG 的本質(zhì)也一樣。

mutex_lock:
            | 將互斥信號(hào)量復(fù)制到寄存器，并將互斥信號(hào)量置為1
            TSL REGISTER,MUTEX
      | 互斥信號(hào)量是 0 嗎？
            CMP REGISTER,#0 
      | 如果互斥信號(hào)量為0，它被解鎖，所以返回
            JZE ok  
      | 互斥信號(hào)正在使用；調(diào)度其他線程
            CALL thread_yield   
      | 再試一次
            JMP mutex_lock  
      | 返回調(diào)用者，進(jìn)入臨界區(qū)
ok:     RET                                                     

mutex_unlcok:
            | 將 mutex 置為 0 
            MOVE MUTEX,#0   
      | 返回調(diào)用者
            RET                                                     

mutex_lock 的代碼和上面 enter_region 的代碼很相似，我們可以對(duì)比著看一下

上面代碼最大的區(qū)別你看出來了嗎？

• 根據(jù)上面我們對(duì) TSL 的分析，我們知道，如果 TSL 判斷沒有進(jìn)入臨界區(qū)的進(jìn)程會(huì)進(jìn)行無限循環(huán)獲取鎖，而在 TSL 的處理中，如果 mutex 正在使用，那么就調(diào)度其他線程進(jìn)行處理。所以上面最大的區(qū)別其實(shí)就是在判斷 mutex/TSL 之后的處理。

• 在（用戶）線程中，情況有所不同，因?yàn)闆]有時(shí)鐘來停止運(yùn)行時(shí)間過長的線程。結(jié)果是通過忙等待的方式來試圖獲得鎖的線程將永遠(yuǎn)循環(huán)下去，決不會(huì)得到鎖，因?yàn)檫@個(gè)運(yùn)行的線程不會(huì)讓其他線程運(yùn)行從而釋放鎖，其他線程根本沒有獲得鎖的機(jī)會(huì)。在后者獲取鎖失敗時(shí)，它會(huì)調(diào)用 thread_yield 將 CPU 放棄給另外一個(gè)線程。結(jié)果就不會(huì)進(jìn)行忙等待。在該線程下次運(yùn)行時(shí)，它再一次對(duì)鎖進(jìn)行測(cè)試。

上面就是 enter_region 和 mutex_lock 的差別所在。由于 thread_yield 僅僅是一個(gè)用戶空間的線程調(diào)度，所以它的運(yùn)行非?？旖荨＿@樣，mutex_lock 和 mutex_unlock 都不需要任何內(nèi)核調(diào)用。通過使用這些過程，用戶線程完全可以實(shí)現(xiàn)在用戶空間中的同步，這個(gè)過程僅僅需要少量的同步。

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

Futexes

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

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

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

對(duì)于一個(gè)進(jìn)程來說，把它放到等待隊(duì)列需要昂貴的系統(tǒng)調(diào)用，這種方式應(yīng)該被避免。在沒有競(jìng)爭(zhēng)的情況下，futex 可以直接在用戶空間中工作。這些進(jìn)程共享一個(gè) 32 位整數(shù)(integer) 作為公共鎖變量。假設(shè)鎖的初始化為 1，我們認(rèn)為這時(shí)鎖已經(jīng)被釋放了。線程通過執(zhí)行原子性的操作減少并測(cè)試(decrement and test) 來搶占鎖。decrement and set 是 Linux 中的原子功能，由包裹在 C 函數(shù)中的內(nèi)聯(lián)匯編組成，并在頭文件中進(jìn)行定義。下一步，線程會(huì)檢查結(jié)果來查看鎖是否已經(jīng)被釋放。如果鎖現(xiàn)在不是鎖定狀態(tài)，那么剛好我們的線程可以成功搶占該鎖。然而，如果鎖被其他線程持有，搶占鎖的線程不得不等待。在這種情況下，futex 庫不會(huì)自旋，但是會(huì)使用一個(gè)系統(tǒng)調(diào)用來把線程放在內(nèi)核中的等待隊(duì)列中。這樣一來，切換到內(nèi)核的開銷已經(jīng)是合情合理的了，因?yàn)榫€程可以在任何時(shí)候阻塞。當(dāng)線程完成了鎖的工作時(shí)，它會(huì)使用原子性的 增加并測(cè)試(increment and test) 釋放鎖，并檢查結(jié)果以查看內(nèi)核等待隊(duì)列上是否仍阻止任何進(jìn)程。如果有的話，它會(huì)通知內(nèi)核可以對(duì)等待隊(duì)列中的一個(gè)或多個(gè)進(jìn)程解除阻塞。如果沒有鎖競(jìng)爭(zhēng)，內(nèi)核則不需要參與競(jìng)爭(zhēng)。

Pthreads 中的互斥量

Pthreads 提供了一些功能用來同步線程。最基本的機(jī)制是使用互斥量變量，可以鎖定和解鎖，用來保護(hù)每個(gè)關(guān)鍵區(qū)域。希望進(jìn)入關(guān)鍵區(qū)域的線程首先要嘗試獲取 mutex。如果 mutex 沒有加鎖，線程能夠馬上進(jìn)入并且互斥量能夠自動(dòng)鎖定，從而阻止其他線程進(jìn)入。如果 mutex 已經(jīng)加鎖，調(diào)用線程會(huì)阻塞，直到 mutex 解鎖。如果多個(gè)線程在相同的互斥量上等待，當(dāng)互斥量解鎖時(shí)，只有一個(gè)線程能夠進(jìn)入并且重新加鎖。這些鎖并不是必須的，程序員需要正確使用它們。

下面是與互斥量有關(guān)的函數(shù)調(diào)用

像我們想象中的一樣，mutex 能夠被創(chuàng)建和銷毀，扮演這兩個(gè)角色的分別是 Phread_mutex_init 和 Pthread_mutex_destroy。mutex 也可以通過 Pthread_mutex_lock 來進(jìn)行加鎖，如果互斥量已經(jīng)加鎖，則會(huì)阻塞調(diào)用者。還有一個(gè)調(diào)用Pthread_mutex_trylock 用來嘗試對(duì)線程加鎖，當(dāng) mutex 已經(jīng)被加鎖時(shí)，會(huì)返回一個(gè)錯(cuò)誤代碼而不是阻塞調(diào)用者。這個(gè)調(diào)用允許線程有效的進(jìn)行忙等。最后，Pthread_mutex_unlock 會(huì)對(duì) mutex 解鎖并且釋放一個(gè)正在等待的線程。

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

下面再來重新認(rèn)識(shí)一下生產(chǎn)者和消費(fèi)者問題：一個(gè)線程將東西放在一個(gè)緩沖區(qū)內(nèi)，由另一個(gè)線程將它們?nèi)〕觥Ｈ绻a(chǎn)者發(fā)現(xiàn)緩沖區(qū)沒有空槽可以使用了，生產(chǎn)者線程會(huì)阻塞起來直到有一個(gè)線程可以使用。生產(chǎn)者使用 mutex 來進(jìn)行原子性檢查從而不受其他線程干擾。但是當(dāng)發(fā)現(xiàn)緩沖區(qū)已經(jīng)滿了以后，生產(chǎn)者需要一種方法來阻塞自己并在以后被喚醒。這便是條件變量做的工作。

下面是一些與條件變量有關(guān)的最重要的 pthread 調(diào)用

上表中給出了一些調(diào)用用來創(chuàng)建和銷毀條件變量。條件變量上的主要屬性是 Pthread_cond_wait 和 Pthread_cond_signal。前者阻塞調(diào)用線程，直到其他線程發(fā)出信號(hào)為止（使用后者調(diào)用）。阻塞的線程通常需要等待喚醒的信號(hào)以此來釋放資源或者執(zhí)行某些其他活動(dòng)。只有這樣阻塞的線程才能繼續(xù)工作。條件變量允許等待與阻塞原子性的進(jìn)程。Pthread_cond_broadcast 用來喚醒多個(gè)阻塞的、需要等待信號(hào)喚醒的線程。

需要注意的是，條件變量（不像是信號(hào)量）不會(huì)存在于內(nèi)存中。如果將一個(gè)信號(hào)量傳遞給一個(gè)沒有線程等待的條件變量，那么這個(gè)信號(hào)就會(huì)丟失，這個(gè)需要注意

下面是一個(gè)使用互斥量和條件變量的例子

管程

為了能夠編寫更加準(zhǔn)確無誤的程序，Brinch Hansen 和 Hoare 提出了一個(gè)更高級(jí)的同步原語叫做 管程(monitor)。他們兩個(gè)人的提案略有不同，通過下面的描述你就可以知道。管程是程序、變量和數(shù)據(jù)結(jié)構(gòu)等組成的一個(gè)集合，它們組成一個(gè)特殊的模塊或者包。進(jìn)程可以在任何需要的時(shí)候調(diào)用管程中的程序，但是它們不能從管程外部訪問數(shù)據(jù)結(jié)構(gòu)和程序。下面展示了一種抽象的，類似 Pascal 語言展示的簡潔的管程。不能用 C 語言進(jìn)行描述，因?yàn)楣艹淌钦Z言概念而 C 語言并不支持管程。

monitor example
    integer i;
    condition c;

    procedure producer();
  ...
    end;    

    procedure consumer();
    .
    end;
end monitor;

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

進(jìn)入管程中的互斥由編譯器負(fù)責(zé)，但是一種通用做法是使用 互斥量(mutex) 和 二進(jìn)制信號(hào)量(binary semaphore)。由于編譯器而不是程序員在操作，因此出錯(cuò)的幾率會(huì)大大降低。在任何時(shí)候，編寫管程的程序員都無需關(guān)心編譯器是如何處理的。他只需要知道將所有的臨界區(qū)轉(zhuǎn)換成為管程過程即可。絕不會(huì)有兩個(gè)進(jìn)程同時(shí)執(zhí)行臨界區(qū)中的代碼。

即使管程提供了一種簡單的方式來實(shí)現(xiàn)互斥，但在我們看來，這還不夠。因?yàn)槲覀冞€需要一種在進(jìn)程無法執(zhí)行被阻塞。在生產(chǎn)者-消費(fèi)者問題中，很容易將針對(duì)緩沖區(qū)滿和緩沖區(qū)空的測(cè)試放在管程程序中，但是生產(chǎn)者在發(fā)現(xiàn)緩沖區(qū)滿的時(shí)候該如何阻塞呢？

解決的辦法是引入條件變量(condition variables) 以及相關(guān)的兩個(gè)操作 wait 和 signal。當(dāng)一個(gè)管程程序發(fā)現(xiàn)它不能運(yùn)行時(shí)（例如，生產(chǎn)者發(fā)現(xiàn)緩沖區(qū)已滿），它會(huì)在某個(gè)條件變量（如 full）上執(zhí)行 wait 操作。這個(gè)操作造成調(diào)用進(jìn)程阻塞，并且還將另一個(gè)以前等在管程之外的進(jìn)程調(diào)入管程。在前面的 pthread 中我們已經(jīng)探討過條件變量的實(shí)現(xiàn)細(xì)節(jié)了。另一個(gè)進(jìn)程，比如消費(fèi)者可以通過執(zhí)行 signal 來喚醒阻塞的調(diào)用進(jìn)程。

Brinch Hansen 和 Hoare 在對(duì)進(jìn)程喚醒上有所不同，Hoare 建議讓新喚醒的進(jìn)程繼續(xù)運(yùn)行；而掛起另外的進(jìn)程。而 Brinch Hansen 建議讓執(zhí)行 signal 的進(jìn)程必須退出管程，這里我們采用 Brinch Hansen 的建議，因?yàn)樗诟拍钌细唵?，并且更容易?shí)現(xiàn)。

如果在一個(gè)條件變量上有若干進(jìn)程都在等待，則在對(duì)該條件執(zhí)行 signal 操作后，系統(tǒng)調(diào)度程序只能選擇其中一個(gè)進(jìn)程恢復(fù)運(yùn)行。

順便提一下，這里還有上面兩位教授沒有提出的第三種方式，它的理論是讓執(zhí)行 signal 的進(jìn)程繼續(xù)運(yùn)行，等待這個(gè)進(jìn)程退出管程時(shí)，其他進(jìn)程才能進(jìn)入管程。

條件變量不是計(jì)數(shù)器。條件變量也不能像信號(hào)量那樣積累信號(hào)以便以后使用。所以，如果向一個(gè)條件變量發(fā)送信號(hào)，但是該條件變量上沒有等待進(jìn)程，那么信號(hào)將會(huì)丟失。也就是說，wait 操作必須在 signal 之前執(zhí)行。

下面是一個(gè)使用 Pascal 語言通過管程實(shí)現(xiàn)的生產(chǎn)者-消費(fèi)者問題的解法

讀者可能覺得 wait 和 signal 操作看起來像是前面提到的 sleep 和 wakeup ，而且后者存在嚴(yán)重的競(jìng)爭(zhēng)條件。它們確實(shí)很像，但是有個(gè)關(guān)鍵的區(qū)別：sleep 和 wakeup 之所以會(huì)失敗是因?yàn)楫?dāng)一個(gè)進(jìn)程想睡眠時(shí)，另一個(gè)進(jìn)程試圖去喚醒它。使用管程則不會(huì)發(fā)生這種情況。管程程序的自動(dòng)互斥保證了這一點(diǎn)，如果管程過程中的生產(chǎn)者發(fā)現(xiàn)緩沖區(qū)已滿，它將能夠完成 wait 操作而不用擔(dān)心調(diào)度程序可能會(huì)在 wait 完成之前切換到消費(fèi)者。甚至，在 wait 執(zhí)行完成并且把生產(chǎn)者標(biāo)志為不可運(yùn)行之前，是不會(huì)允許消費(fèi)者進(jìn)入管程的。

盡管類 Pascal 是一種想象的語言，但還是有一些真正的編程語言支持，比如 Java （終于輪到大 Java 出場(chǎng)了），Java 是能夠支持管程的，它是一種 面向?qū)ο?/code>的語言，支持用戶級(jí)線程，還允許將方法劃分為類。只要將關(guān)鍵字 synchronized 關(guān)鍵字加到方法中即可。Java 能夠保證一旦某個(gè)線程執(zhí)行該方法，就不允許其他線程執(zhí)行該對(duì)象中的任何 synchronized 方法。沒有關(guān)鍵字 synchronized ，就不能保證沒有交叉執(zhí)行。

下面是 Java 使用管程解決的生產(chǎn)者-消費(fèi)者問題

public class ProducerConsumer {
  // 定義緩沖區(qū)大小的長度
  static final int N = 100;
  // 初始化一個(gè)新的生產(chǎn)者線程
  static Producer p = new Producer();
  // 初始化一個(gè)新的消費(fèi)者線程
  static Consumer c = new Consumer();        
  // 初始化一個(gè)管程
  static Our_monitor mon = new Our_monitor(); 

  // run 包含了線程代碼
  static class Producer extends Thread{
    public void run(){                                                
      int item;
      // 生產(chǎn)者循環(huán)
      while(true){                                                        
        item = produce_item();
        mon.insert(item);
      }
    }
    // 生產(chǎn)代碼
    private int produce_item(){...}                        
  }

  // run 包含了線程代碼
  static class consumer extends Thread {
    public void run( ) {                                            
           int item;
      while(true){
        item = mon.remove();
                consume_item(item);
      }
    }
    // 消費(fèi)代碼
    private int produce_item(){...}                        
  }

  // 這是管程
  static class Our_monitor {                                    
    private int buffer[] = new int[N];
    // 計(jì)數(shù)器和索引
    private int count = 0,lo = 0,hi = 0;            

    private synchronized void insert(int val){
      if(count == N){
        // 如果緩沖區(qū)是滿的，則進(jìn)入休眠
        go_to_sleep();                                                
      }
      // 向緩沖區(qū)插入內(nèi)容
            buffer[hi] = val;                   
      // 找到下一個(gè)槽的為止
      hi = (hi + 1) % N;                 
      // 緩沖區(qū)中的數(shù)目自增 1 
      count = count + 1;                                            
      if(count == 1){
        // 如果消費(fèi)者睡眠，則喚醒
        notify();                                                            
      }
    }

    private synchronized void remove(int val){
      int val;
      if(count == 0){
        // 緩沖區(qū)是空的，進(jìn)入休眠
        go_to_sleep();                                                
      }
      // 從緩沖區(qū)取出數(shù)據(jù)
      val = buffer[lo];                
      // 設(shè)置待取出數(shù)據(jù)項(xiàng)的槽
      lo = (lo + 1) % N;                    
      // 緩沖區(qū)中的數(shù)據(jù)項(xiàng)數(shù)目減 1 
      count = count - 1;                                            
      if(count = N - 1){
        // 如果生產(chǎn)者睡眠，喚醒它
        notify();                                                            
      }
      return val;
    }

    private void go_to_sleep() {
      try{
        wait( );
      }catch(Interr uptedExceptionexc) {};
    }
  }

}

上面的代碼中主要設(shè)計(jì)四個(gè)類，外部類(outer class) ProducerConsumer 創(chuàng)建并啟動(dòng)兩個(gè)線程，p 和 c。第二個(gè)類和第三個(gè)類 Producer 和 Consumer 分別包含生產(chǎn)者和消費(fèi)者代碼。最后，Our_monitor 是管程，它有兩個(gè)同步線程，用于在共享緩沖區(qū)中插入和取出數(shù)據(jù)。

在前面的所有例子中，生產(chǎn)者和消費(fèi)者線程在功能上與它們是相同的。生產(chǎn)者有一個(gè)無限循環(huán)，該無限循環(huán)產(chǎn)生數(shù)據(jù)并將數(shù)據(jù)放入公共緩沖區(qū)中；消費(fèi)者也有一個(gè)等價(jià)的無限循環(huán)，該無限循環(huán)用于從緩沖區(qū)取出數(shù)據(jù)并完成一系列工作。

程序中比較耐人尋味的就是 Our_monitor 了，它包含緩沖區(qū)、管理變量以及兩個(gè)同步方法。當(dāng)生產(chǎn)者在 insert 內(nèi)活動(dòng)時(shí)，它保證消費(fèi)者不能在 remove 方法中運(yùn)行，從而保證更新變量以及緩沖區(qū)的安全性，并且不用擔(dān)心競(jìng)爭(zhēng)條件。變量 count 記錄在緩沖區(qū)中數(shù)據(jù)的數(shù)量。變量 lo 是緩沖區(qū)槽的序號(hào)，指出將要取出的下一個(gè)數(shù)據(jù)項(xiàng)。類似地，hi 是緩沖區(qū)中下一個(gè)要放入的數(shù)據(jù)項(xiàng)序號(hào)。允許 lo = hi，含義是在緩沖區(qū)中有 0 個(gè)或 N 個(gè)數(shù)據(jù)。

Java 中的同步方法與其他經(jīng)典管程有本質(zhì)差別：Java 沒有內(nèi)嵌的條件變量。然而，Java 提供了 wait 和 notify 分別與 sleep 和 wakeup 等價(jià)。

通過臨界區(qū)自動(dòng)的互斥，管程比信號(hào)量更容易保證并行編程的正確性。但是管程也有缺點(diǎn)，我們前面說到過管程是一個(gè)編程語言的概念，編譯器必須要識(shí)別管程并用某種方式對(duì)其互斥作出保證。C、Pascal 以及大多數(shù)其他編程語言都沒有管程，所以不能依靠編譯器來遵守互斥規(guī)則。

與管程和信號(hào)量有關(guān)的另一個(gè)問題是，這些機(jī)制都是設(shè)計(jì)用來解決訪問共享內(nèi)存的一個(gè)或多個(gè) CPU 上的互斥問題的。通過將信號(hào)量放在共享內(nèi)存中并用 TSL 或 XCHG 指令來保護(hù)它們，可以避免競(jìng)爭(zhēng)。但是如果是在分布式系統(tǒng)中，可能同時(shí)具有多個(gè) CPU 的情況，并且每個(gè) CPU 都有自己的私有內(nèi)存呢，它們通過網(wǎng)絡(luò)相連，那么這些原語將會(huì)失效。因?yàn)樾盘?hào)量太低級(jí)了，而管程在少數(shù)幾種編程語言之外無法使用，所以還需要其他方法。

消息傳遞

上面提到的其他方法就是 消息傳遞(messaage passing)。這種進(jìn)程間通信的方法使用兩個(gè)原語 send 和 receive ，它們像信號(hào)量而不像管程，是系統(tǒng)調(diào)用而不是語言級(jí)別。示例如下

send 方法用于向一個(gè)給定的目標(biāo)發(fā)送一條消息，receive 從一個(gè)給定的源接受一條消息。如果沒有消息，接受者可能被阻塞，直到接受一條消息或者帶著錯(cuò)誤碼返回。

消息傳遞系統(tǒng)的設(shè)計(jì)要點(diǎn)

消息傳遞系統(tǒng)現(xiàn)在面臨著許多信號(hào)量和管程所未涉及的問題和設(shè)計(jì)難點(diǎn)，尤其對(duì)那些在網(wǎng)絡(luò)中不同機(jī)器上的通信狀況。例如，消息有可能被網(wǎng)絡(luò)丟失。為了防止消息丟失，發(fā)送方和接收方可以達(dá)成一致：一旦接受到消息后，接收方馬上回送一條特殊的 確認(rèn)(acknowledgement) 消息。如果發(fā)送方在一段時(shí)間間隔內(nèi)未收到確認(rèn)，則重發(fā)消息。

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

對(duì)于接收者來說，如何區(qū)分新的消息和一條重發(fā)的老消息是非常重要的。通常采用在每條原始消息中嵌入一個(gè)連續(xù)的序號(hào)來解決此問題。如果接受者收到一條消息，它具有與前面某一條消息一樣的序號(hào)，就知道這條消息是重復(fù)的，可以忽略。

消息系統(tǒng)還必須處理如何命名進(jìn)程的問題，以便在發(fā)送或接收調(diào)用中清晰的指明進(jìn)程。身份驗(yàn)證(authentication) 也是一個(gè)問題，比如客戶端怎么知道它是在與一個(gè)真正的文件服務(wù)器通信，從發(fā)送方到接收方的信息有可能被中間人所篡改。

用消息傳遞解決生產(chǎn)者-消費(fèi)者問題

現(xiàn)在我們考慮如何使用消息傳遞來解決生產(chǎn)者-消費(fèi)者問題，而不是共享緩存。下面是一種解決方式

/* buffer 中槽的數(shù)量 */
#define N 100                                                    

void producer(void){

  int item;
  /* buffer 中槽的數(shù)量 */
  message m;                                                    

  while(TRUE){
    /* 生成放入緩沖區(qū)的數(shù)據(jù) */
    item = produce_item();                        
    /* 等待消費(fèi)者發(fā)送空緩沖區(qū) */
    receive(consumer,&m);                            
    /* 建立一個(gè)待發(fā)送的消息 */
    build_message(&m,item);                        
    /* 發(fā)送給消費(fèi)者 */
    send(consumer,&m);                                
  }

}

void consumer(void){

  int item,i;
  message m;

  /* 循環(huán)N次 */
  for(int i = 0;i < N;i++){                        
    /* 發(fā)送N個(gè)緩沖區(qū) */
    send(producer,&m);                                
  }
  while(TRUE){
    /* 接受包含數(shù)據(jù)的消息 */
    receive(producer,&m);                            
    /* 將數(shù)據(jù)從消息中提取出來 */
      item = extract_item(&m);                    
    /* 將空緩沖區(qū)發(fā)送回生產(chǎn)者 */
    send(producer,&m);                                
    /* 處理數(shù)據(jù) */
    consume_item(item);                                
  }

}

假設(shè)所有的消息都有相同的大小，并且在尚未接受到發(fā)出的消息時(shí)，由操作系統(tǒng)自動(dòng)進(jìn)行緩沖。在該解決方案中共使用 N 條消息，這就類似于一塊共享內(nèi)存緩沖區(qū)的 N 個(gè)槽。消費(fèi)者首先將 N 條空消息發(fā)送給生產(chǎn)者。當(dāng)生產(chǎn)者向消費(fèi)者傳遞一個(gè)數(shù)據(jù)項(xiàng)時(shí)，它取走一條空消息并返回一條填充了內(nèi)容的消息。通過這種方式，系統(tǒng)中總的消息數(shù)量保持不變，所以消息都可以存放在事先確定數(shù)量的內(nèi)存中。

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

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

• 一種方法是為每個(gè)進(jìn)程分配一個(gè)唯一的地址，讓消息按進(jìn)程的地址編址。

• 另一種方式是引入一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，稱為 信箱(mailbox)，信箱是一個(gè)用來對(duì)一定的數(shù)據(jù)進(jìn)行緩沖的數(shù)據(jù)結(jié)構(gòu)，信箱中消息的設(shè)置方法也有多種，典型的方法是在信箱創(chuàng)建時(shí)確定消息的數(shù)量。在使用信箱時(shí)，在 send 和 receive 調(diào)用的地址參數(shù)就是信箱的地址，而不是進(jìn)程的地址。當(dāng)一個(gè)進(jìn)程試圖向一個(gè)滿的信箱發(fā)送消息時(shí)，它將被掛起，直到信箱中有消息被取走，從而為新的消息騰出地址空間。

屏障

最后一個(gè)同步機(jī)制是準(zhǔn)備用于進(jìn)程組而不是進(jìn)程間的生產(chǎn)者-消費(fèi)者情況的。在某些應(yīng)用中劃分了若干階段，并且規(guī)定，除非所有的進(jìn)程都就緒準(zhǔn)備著手下一個(gè)階段，否則任何進(jìn)程都不能進(jìn)入下一個(gè)階段，可以通過在每個(gè)階段的結(jié)尾安裝一個(gè) 屏障(barrier) 來實(shí)現(xiàn)這種行為。當(dāng)一個(gè)進(jìn)程到達(dá)屏障時(shí)，它會(huì)被屏障所攔截，直到所有的屏障都到達(dá)為止。屏障可用于一組進(jìn)程同步，如下圖所示

在上圖中我們可以看到，有四個(gè)進(jìn)程接近屏障，這意味著每個(gè)進(jìn)程都在進(jìn)行運(yùn)算，但是還沒有到達(dá)每個(gè)階段的結(jié)尾。過了一段時(shí)間后，A、B、D 三個(gè)進(jìn)程都到達(dá)了屏障，各自的進(jìn)程被掛起，但此時(shí)還不能進(jìn)入下一個(gè)階段呢，因?yàn)檫M(jìn)程 B 還沒有執(zhí)行完畢。結(jié)果，當(dāng)最后一個(gè) C 到達(dá)屏障后，這個(gè)進(jìn)程組才能夠進(jìn)入下一個(gè)階段。

避免鎖：讀-復(fù)制-更新

最快的鎖是根本沒有鎖。問題在于沒有鎖的情況下，我們是否允許對(duì)共享數(shù)據(jù)結(jié)構(gòu)的并發(fā)讀寫進(jìn)行訪問。答案當(dāng)然是不可以。假設(shè)進(jìn)程 A 正在對(duì)一個(gè)數(shù)字?jǐn)?shù)組進(jìn)行排序，而進(jìn)程 B 正在計(jì)算其平均值，而此時(shí)你進(jìn)行 A 的移動(dòng)，會(huì)導(dǎo)致 B 會(huì)多次讀到重復(fù)值，而某些值根本沒有遇到過。

然而，在某些情況下，我們可以允許寫操作來更新數(shù)據(jù)結(jié)構(gòu)，即便還有其他的進(jìn)程正在使用。竅門在于確保每個(gè)讀操作要么讀取舊的版本，要么讀取新的版本，例如下面的樹

上面的樹中，讀操作從根部到葉子遍歷整個(gè)樹。加入一個(gè)新節(jié)點(diǎn) X 后，為了實(shí)現(xiàn)這一操作，我們要讓這個(gè)節(jié)點(diǎn)在樹中可見之前使它恰好正確：我們對(duì)節(jié)點(diǎn) X 中的所有值進(jìn)行初始化，包括它的子節(jié)點(diǎn)指針。然后通過原子寫操作，使 X 稱為 A 的子節(jié)點(diǎn)。所有的讀操作都不會(huì)讀到前后不一致的版本

在上面的圖中，我們接著移除 B 和 D。首先，將 A 的左子節(jié)點(diǎn)指針指向 C 。所有原本在 A 中的讀操作將會(huì)后續(xù)讀到節(jié)點(diǎn) C ，而永遠(yuǎn)不會(huì)讀到 B 和 D。也就是說，它們將只會(huì)讀取到新版數(shù)據(jù)。同樣，所有當(dāng)前在 B 和 D 中的讀操作將繼續(xù)按照原始的數(shù)據(jù)結(jié)構(gòu)指針并且讀取舊版數(shù)據(jù)。所有操作均能正確運(yùn)行，我們不需要鎖住任何東西。而不需要鎖住數(shù)據(jù)就能夠移除 B 和 D 的主要原因就是 讀-復(fù)制-更新(Ready-Copy-Update,RCU)，將更新過程中的移除和再分配過程分離開。

調(diào)度

當(dāng)一個(gè)計(jì)算機(jī)是多道程序設(shè)計(jì)系統(tǒng)時(shí)，會(huì)頻繁的有很多進(jìn)程或者線程來同時(shí)競(jìng)爭(zhēng) CPU 時(shí)間片。當(dāng)兩個(gè)或兩個(gè)以上的進(jìn)程/線程處于就緒狀態(tài)時(shí)，就會(huì)發(fā)生這種情況。如果只有一個(gè) CPU 可用，那么必須選擇接下來哪個(gè)進(jìn)程/線程可以運(yùn)行。操作系統(tǒng)中有一個(gè)叫做 調(diào)度程序(scheduler) 的角色存在，它就是做這件事兒的，該程序使用的算法叫做 調(diào)度算法(scheduling algorithm) 。

盡管有一些不同，但許多適用于進(jìn)程調(diào)度的處理方法同樣也適用于線程調(diào)度。當(dāng)內(nèi)核管理線程的時(shí)候，調(diào)度通常會(huì)以線程級(jí)別發(fā)生，很少或者根本不會(huì)考慮線程屬于哪個(gè)進(jìn)程。下面我們會(huì)首先專注于進(jìn)程和線程的調(diào)度問題，然后會(huì)明確的介紹線程調(diào)度以及它產(chǎn)生的問題。

調(diào)度介紹

讓我們回到早期以磁帶上的卡片作為輸入的批處理系統(tǒng)的時(shí)代，那時(shí)候的調(diào)度算法非常簡單：依次運(yùn)行磁帶上的每一個(gè)作業(yè)。對(duì)于多道程序設(shè)計(jì)系統(tǒng)，會(huì)復(fù)雜一些，因?yàn)橥ǔ?huì)有多個(gè)用戶在等待服務(wù)。一些大型機(jī)仍然將 批處理和 分時(shí)服務(wù)結(jié)合使用，需要調(diào)度程序決定下一個(gè)運(yùn)行的是一個(gè)批處理作業(yè)還是終端上的用戶。由于在這些機(jī)器中 CPU 是稀缺資源，所以好的調(diào)度程序可以在提高性能和用戶的滿意度方面取得很大的成果。

進(jìn)程行為

幾乎所有的進(jìn)程（磁盤或網(wǎng)絡(luò)）I/O 請(qǐng)求和計(jì)算都是交替運(yùn)行的

如上圖所示，CPU 不停頓的運(yùn)行一段時(shí)間，然后發(fā)出一個(gè)系統(tǒng)調(diào)用等待 I/O 讀寫文件。完成系統(tǒng)調(diào)用后，CPU 又開始計(jì)算，直到它需要讀更多的數(shù)據(jù)或者寫入更多的數(shù)據(jù)為止。當(dāng)一個(gè)進(jìn)程等待外部設(shè)備完成工作而被阻塞時(shí)，才是 I/O 活動(dòng)。


上面 a 是 CPU 密集型進(jìn)程；b 是 I/O 密集型進(jìn)程進(jìn)程，a 因?yàn)樵谟?jì)算的時(shí)間上花費(fèi)時(shí)間更長，因此稱為計(jì)算密集型(compute-bound) 或者 CPU 密集型(CPU-bound)，b 因?yàn)镮/O 發(fā)生頻率比較快因此稱為 I/O 密集型(I/O-bound)。計(jì)算密集型進(jìn)程有較長的 CPU 集中使用和較小頻度的 I/O 等待。I/O 密集型進(jìn)程有較短的 CPU 使用時(shí)間和較頻繁的 I/O 等待。注意到上面兩種進(jìn)程的區(qū)分關(guān)鍵在于 CPU 的時(shí)間占用而不是 I/O 的時(shí)間占用。I/O 密集型的原因是因?yàn)樗鼈儧]有在 I/O 之間花費(fèi)更多的計(jì)算、而不是 I/O 請(qǐng)求時(shí)間特別長。無論數(shù)據(jù)到達(dá)后需要花費(fèi)多少時(shí)間，它們都需要花費(fèi)相同的時(shí)間來發(fā)出讀取磁盤塊的硬件請(qǐng)求。

值得注意的是，隨著 CPU 的速度越來越快，更多的進(jìn)程傾向于 I/O 密集型。這種情況出現(xiàn)的原因是 CPU 速度的提升要遠(yuǎn)遠(yuǎn)高于硬盤。這種情況導(dǎo)致的結(jié)果是，未來對(duì) I/O 密集型進(jìn)程的調(diào)度處理似乎更為重要。這里的基本思想是，如果需要運(yùn)行 I/O 密集型進(jìn)程，那么就應(yīng)該讓它盡快得到機(jī)會(huì)，以便發(fā)出磁盤請(qǐng)求并保持磁盤始終忙碌。

何時(shí)調(diào)度

第一個(gè)和調(diào)度有關(guān)的問題是何時(shí)進(jìn)行調(diào)度決策。存在著需要調(diào)度處理的各種情形。首先，在創(chuàng)建一個(gè)新進(jìn)程后，需要決定是運(yùn)行父進(jìn)程還是子進(jìn)程。因?yàn)槎叩倪M(jìn)程都處于就緒態(tài)下，這是正常的調(diào)度決策，可以任意選擇，也就是說，調(diào)度程序可以任意的選擇子進(jìn)程或父進(jìn)程開始運(yùn)行。

第二，在進(jìn)程退出時(shí)需要作出調(diào)度決定。因?yàn)榇诉M(jìn)程不再運(yùn)行（因?yàn)樗鼘⒉辉俅嬖冢虼吮仨殢木途w進(jìn)程中選擇其他進(jìn)程運(yùn)行。如果沒有進(jìn)程處于就緒態(tài)，系統(tǒng)提供的空閑進(jìn)程通常會(huì)運(yùn)行

什么是空閑進(jìn)程

空閑進(jìn)程(system-supplied idle process) 是 Microsoft 公司 windows 操作系統(tǒng)帶有的系統(tǒng)進(jìn)程，該進(jìn)程是在各個(gè)處理器上運(yùn)行的單個(gè)線程，它唯一的任務(wù)是在系統(tǒng)沒有處理其他線程時(shí)占用處理器時(shí)間。System Idle Process 并不是一個(gè)真正的進(jìn)程，它是核心虛擬出來的，多任務(wù)操作系統(tǒng)都存在。在沒有可用的進(jìn)程時(shí)，系統(tǒng)處于空運(yùn)行狀態(tài)，此時(shí)就是System Idle Process 在正在運(yùn)行。你可以簡單的理解成，它代表的是 CPU 的空閑狀態(tài)，數(shù)值越大代表處理器越空閑，可以通過 Windows 任務(wù)管理器查看 Windows 中的 CPU 利用率

第三種情況是，當(dāng)進(jìn)程阻塞在 I/O 、信號(hào)量或其他原因時(shí)，必須選擇另外一個(gè)進(jìn)程來運(yùn)行。有時(shí)，阻塞的原因會(huì)成為選擇進(jìn)程運(yùn)行的關(guān)鍵因素。例如，如果 A 是一個(gè)重要進(jìn)程，并且它正在等待 B 退出關(guān)鍵區(qū)域，讓 B 退出關(guān)鍵區(qū)域從而使 A 得以運(yùn)行。但是調(diào)度程序一般不會(huì)對(duì)這種情況進(jìn)行考量。

第四點(diǎn)，當(dāng) I/O 中斷發(fā)生時(shí)，可以做出調(diào)度決策。如果中斷來自 I/O 設(shè)備，而 I/O 設(shè)備已經(jīng)完成了其工作，那么那些等待 I/O 的進(jìn)程現(xiàn)在可以繼續(xù)運(yùn)行。由調(diào)度程序來決定是否準(zhǔn)備運(yùn)行新的進(jìn)程還是重新運(yùn)行已經(jīng)中斷的進(jìn)程。

如果硬件時(shí)鐘以 50 或 60 Hz 或其他頻率提供周期性中斷，可以在每個(gè)時(shí)鐘中斷或第 k 個(gè)時(shí)鐘中斷處做出調(diào)度決策。根據(jù)如何處理時(shí)鐘中斷可以把調(diào)度算法可以分為兩類。非搶占式(nonpreemptive) 調(diào)度算法挑選一個(gè)進(jìn)程，讓該進(jìn)程運(yùn)行直到被阻塞（阻塞在 I/O 上或等待另一個(gè)進(jìn)程），或者直到該進(jìn)程自動(dòng)釋放 CPU。即使該進(jìn)程運(yùn)行了若干個(gè)小時(shí)后，它也不會(huì)被強(qiáng)制掛起。這樣會(huì)在時(shí)鐘中斷發(fā)生時(shí)不會(huì)進(jìn)行調(diào)度。在處理完時(shí)鐘中斷后，如果沒有更高優(yōu)先級(jí)的進(jìn)程等待，則被中斷的進(jìn)程會(huì)繼續(xù)執(zhí)行。

另外一種情況是 搶占式 調(diào)度算法，它會(huì)選擇一個(gè)進(jìn)程，并使其在最大固定時(shí)間內(nèi)運(yùn)行。如果在時(shí)間間隔結(jié)束后仍在運(yùn)行，這個(gè)進(jìn)程會(huì)被掛起，調(diào)度程序會(huì)選擇其他進(jìn)程來運(yùn)行（前提是存在就緒進(jìn)程）。進(jìn)行搶占式調(diào)度需要在時(shí)間間隔結(jié)束時(shí)發(fā)生時(shí)鐘中斷，以將 CPU 的控制權(quán)交還給調(diào)度程序。如果沒有可用的時(shí)鐘，那么非搶占式就是唯一的選擇。

調(diào)度算法的分類

毫無疑問，不同的環(huán)境下需要不同的調(diào)度算法。之所以出現(xiàn)這種情況，是因?yàn)椴煌膽?yīng)用程序和不同的操作系統(tǒng)有不同的目標(biāo)。也就是說，在不同的系統(tǒng)中，調(diào)度程序的優(yōu)化也是不同的。這里有必要?jiǎng)澐殖鋈N環(huán)境

• 批處理(Batch)

• 交互式(Interactive)

• 實(shí)時(shí)(Real time)

批處理系統(tǒng)廣泛應(yīng)用于商業(yè)領(lǐng)域，比如用來處理工資單、存貨清單、賬目收入、賬目支出、利息計(jì)算、索賠處理和其他周期性作業(yè)。在批處理系統(tǒng)中，一般會(huì)選擇使用非搶占式算法或者周期性比較長的搶占式算法。這種方法可以減少線程切換因此能夠提升性能。

在交互式用戶環(huán)境中，為了避免一個(gè)進(jìn)程霸占 CPU 拒絕為其他進(jìn)程服務(wù)，所以需要搶占式算法。即使沒有進(jìn)程有意要一直運(yùn)行下去，但是，由于某個(gè)進(jìn)程出現(xiàn)錯(cuò)誤也有可能無限期的排斥其他所有進(jìn)程。為了避免這種情況，搶占式也是必須的。服務(wù)器也屬于此類別，因?yàn)樗鼈兺ǔ槎鄠€(gè)（遠(yuǎn)程）用戶提供服務(wù)，而這些用戶都非常著急。計(jì)算機(jī)用戶總是很忙。

在實(shí)時(shí)系統(tǒng)中，搶占有時(shí)是不需要的，因?yàn)檫M(jìn)程知道自己可能運(yùn)行不了很長時(shí)間，通常很快的做完自己的工作并阻塞。實(shí)時(shí)系統(tǒng)與交互式系統(tǒng)的差別是，實(shí)時(shí)系統(tǒng)只運(yùn)行那些用來推進(jìn)現(xiàn)有應(yīng)用的程序，而交互式系統(tǒng)是通用的，它可以運(yùn)行任意的非協(xié)作甚至是有惡意的程序。

調(diào)度算法的目標(biāo)

為了設(shè)計(jì)調(diào)度算法，有必要考慮一下什么是好的調(diào)度算法。有一些目標(biāo)取決于環(huán)境（批處理、交互式或者實(shí)時(shí)）蛋大部分是適用于所有情況的，下面是一些需要考量的因素，我們會(huì)在下面一起討論。

所有系統(tǒng)

在所有的情況中，公平是很重要的。對(duì)一個(gè)進(jìn)程給予相較于其他等價(jià)的進(jìn)程更多的 CPU 時(shí)間片對(duì)其他進(jìn)程來說是不公平的。當(dāng)然，不同類型的進(jìn)程可以采用不同的處理方式。

與公平有關(guān)的是系統(tǒng)的強(qiáng)制執(zhí)行，什么意思呢？如果某公司的薪資發(fā)放系統(tǒng)計(jì)劃在本月的15號(hào)，那么碰上了疫情大家生活都很拮據(jù)，此時(shí)老板說要在14號(hào)晚上發(fā)放薪資，那么調(diào)度程序必須強(qiáng)制使進(jìn)程執(zhí)行 14 號(hào)晚上發(fā)放薪資的策略。

另一個(gè)共同的目標(biāo)是保持系統(tǒng)的所有部分盡可能的忙碌。如果 CPU 和所有的 I/O 設(shè)備能夠一直運(yùn)行，那么相對(duì)于讓某些部件空轉(zhuǎn)而言，每秒鐘就可以完成更多的工作。例如，在批處理系統(tǒng)中，調(diào)度程序控制哪個(gè)作業(yè)調(diào)入內(nèi)存運(yùn)行。在內(nèi)存中既有一些 CPU 密集型進(jìn)程又有一些 I/O 密集型進(jìn)程是一個(gè)比較好的想法，好于先調(diào)入和運(yùn)行所有的 CPU 密集型作業(yè)，然后在它們完成之后再調(diào)入和運(yùn)行所有 I/O 密集型作業(yè)的做法。使用后者這種方式會(huì)在 CPU 密集型進(jìn)程啟動(dòng)后，爭(zhēng)奪 CPU ，而磁盤卻在空轉(zhuǎn)，而當(dāng) I/O 密集型進(jìn)程啟動(dòng)后，它們又要為磁盤而競(jìng)爭(zhēng)，CPU 卻又在空轉(zhuǎn)。。。。。。顯然，通過結(jié)合 I/O 密集型和 CPU 密集型，能夠使整個(gè)系統(tǒng)運(yùn)行更流暢，效率更高。

批處理系統(tǒng)

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

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

交互式系統(tǒng)

對(duì)于交互式系統(tǒng)，則有不同的指標(biāo)。最重要的是盡量減少響應(yīng)時(shí)間。這個(gè)時(shí)間說的是從執(zhí)行指令開始到得到結(jié)果的時(shí)間。再有后臺(tái)進(jìn)程運(yùn)行（例如，從網(wǎng)絡(luò)上讀取和保存 E-mail 文件）的個(gè)人計(jì)算機(jī)上，用戶請(qǐng)求啟動(dòng)一個(gè)程序或打開一個(gè)文件應(yīng)該優(yōu)先于后臺(tái)的工作。能夠讓所有的交互式請(qǐng)求首先運(yùn)行的就是一個(gè)好的服務(wù)。

一個(gè)相關(guān)的問題是 均衡性(proportionality)，用戶對(duì)做一件事情需要多長時(shí)間總是有一種固定（不過通常不正確）的看法。當(dāng)認(rèn)為一個(gè)請(qǐng)求很復(fù)雜需要較多時(shí)間時(shí)，用戶會(huì)認(rèn)為很正常并且可以接受，但是一個(gè)很簡單的程序卻花費(fèi)了很長的運(yùn)行時(shí)間，用戶就會(huì)很惱怒。可以拿彩印和復(fù)印來舉出一個(gè)簡單的例子，彩印可能需要1分鐘的時(shí)間，但是用戶覺得復(fù)雜并且愿意等待一分鐘，相反，復(fù)印很簡單只需要 5 秒鐘，但是復(fù)印機(jī)花費(fèi) 1 分鐘卻沒有完成復(fù)印操作，用戶就會(huì)很焦躁。

實(shí)時(shí)系統(tǒng)

實(shí)時(shí)系統(tǒng)則有著和交互式系統(tǒng)不同的考量因素，因此也就有不同的調(diào)度目標(biāo)。實(shí)時(shí)系統(tǒng)的特點(diǎn)是必須滿足最后的截止時(shí)間。例如，如果計(jì)算機(jī)控制著以固定速率產(chǎn)生數(shù)據(jù)的設(shè)備，未能按時(shí)運(yùn)行的話可能會(huì)導(dǎo)致數(shù)據(jù)丟失。因此，實(shí)時(shí)系統(tǒng)中最重要的需求是滿足所有（或大多數(shù)）時(shí)間期限。

在一些實(shí)事系統(tǒng)中，特別是涉及到多媒體的，可預(yù)測(cè)性很重要。偶爾不能滿足最后的截止時(shí)間不重要，但是如果音頻多媒體運(yùn)行不穩(wěn)定，聲音質(zhì)量會(huì)持續(xù)惡化。視頻也會(huì)造成問題，但是耳朵要比眼睛敏感很多。為了避免這些問題，進(jìn)程調(diào)度必須能夠高度可預(yù)測(cè)的而且是有規(guī)律的。

批處理中的調(diào)度

現(xiàn)在讓我們把目光從一般性的調(diào)度轉(zhuǎn)換為特定的調(diào)度算法。下面我們會(huì)探討在批處理中的調(diào)度。

先來先服務(wù)

很像是先到先得。。?？赡茏詈唵蔚姆菗屨际秸{(diào)度算法的設(shè)計(jì)就是 先來先服務(wù)(first-come,first-serverd)。使用此算法，將按照請(qǐng)求順序?yàn)檫M(jìn)程分配 CPU。最基本的，會(huì)有一個(gè)就緒進(jìn)程的等待隊(duì)列。當(dāng)?shù)谝粋€(gè)任務(wù)從外部進(jìn)入系統(tǒng)時(shí)，將會(huì)立即啟動(dòng)并允許運(yùn)行任意長的時(shí)間。它不會(huì)因?yàn)檫\(yùn)行時(shí)間太長而中斷。當(dāng)其他作業(yè)進(jìn)入時(shí)，它們排到就緒隊(duì)列尾部。當(dāng)正在運(yùn)行的進(jìn)程阻塞，處于等待隊(duì)列的第一個(gè)進(jìn)程就開始運(yùn)行。當(dāng)一個(gè)阻塞的進(jìn)程重新處于就緒態(tài)時(shí)，它會(huì)像一個(gè)新到達(dá)的任務(wù)，會(huì)排在隊(duì)列的末尾，即排在所有進(jìn)程最后。

這個(gè)算法的強(qiáng)大之處在于易于理解和編程，在這個(gè)算法中，一個(gè)單鏈表記錄了所有就緒進(jìn)程。要選取一個(gè)進(jìn)程運(yùn)行，只要從該隊(duì)列的頭部移走一個(gè)進(jìn)程即可；要添加一個(gè)新的作業(yè)或者阻塞一個(gè)進(jìn)程，只要把這個(gè)作業(yè)或進(jìn)程附加在隊(duì)列的末尾即可。這是很簡單的一種實(shí)現(xiàn)。

不過，先來先服務(wù)也是有缺點(diǎn)的，那就是沒有優(yōu)先級(jí)的關(guān)系，試想一下，如果有 100 個(gè) I/O 進(jìn)程正在排隊(duì)，第 101 個(gè)是一個(gè) CPU 密集型進(jìn)程，那豈不是需要等 100 個(gè) I/O 進(jìn)程運(yùn)行完畢才會(huì)等到一個(gè) CPU 密集型進(jìn)程運(yùn)行，這在實(shí)際情況下根本不可能，所以需要優(yōu)先級(jí)或者搶占式進(jìn)程的出現(xiàn)來優(yōu)先選擇重要的進(jìn)程運(yùn)行。

最短作業(yè)優(yōu)先

批處理中，第二種調(diào)度算法是 最短作業(yè)優(yōu)先(Shortest Job First)，我們假設(shè)運(yùn)行時(shí)間已知。例如，一家保險(xiǎn)公司，因?yàn)槊刻煲鲱愃频墓ぷ?，所以人們可以相?dāng)精確地預(yù)測(cè)處理 1000 個(gè)索賠的一批作業(yè)需要多長時(shí)間。當(dāng)輸入隊(duì)列中有若干個(gè)同等重要的作業(yè)被啟動(dòng)時(shí)，調(diào)度程序應(yīng)使用最短優(yōu)先作業(yè)算法

如上圖 a 所示，這里有 4 個(gè)作業(yè) A、B、C、D ，運(yùn)行時(shí)間分別為 8、4、4、4 分鐘。若按圖中的次序運(yùn)行，則 A 的周轉(zhuǎn)時(shí)間為 8 分鐘，B 為 12 分鐘，C 為 16 分鐘，D 為 20 分鐘，平均時(shí)間內(nèi)為 14 分鐘。


現(xiàn)在考慮使用最短作業(yè)優(yōu)先算法運(yùn)行 4 個(gè)作業(yè)，如上圖 b 所示，目前的周轉(zhuǎn)時(shí)間分別為 4、8、12、20，平均為 11 分鐘，可以證明最短作業(yè)優(yōu)先是最優(yōu)的?？紤]有 4 個(gè)作業(yè)的情況，其運(yùn)行時(shí)間分別為 a、b、c、d。第一個(gè)作業(yè)在時(shí)間 a 結(jié)束，第二個(gè)在時(shí)間 a + b 結(jié)束，以此類推。平均周轉(zhuǎn)時(shí)間為 (4a + 3b + 2c + d) / 4 。顯然 a 對(duì)平均值的影響最大，所以 a 應(yīng)該是最短優(yōu)先作業(yè)，其次是 b，然后是 c ，最后是 d 它就只能影響自己的周轉(zhuǎn)時(shí)間了。

需要注意的是，在所有的進(jìn)程都可以運(yùn)行的情況下，最短作業(yè)優(yōu)先的算法才是最優(yōu)的。

最短剩余時(shí)間優(yōu)先

最短作業(yè)優(yōu)先的搶占式版本被稱作為 最短剩余時(shí)間優(yōu)先(Shortest Remaining Time Next) 算法。使用這個(gè)算法，調(diào)度程序總是選擇剩余運(yùn)行時(shí)間最短的那個(gè)進(jìn)程運(yùn)行。當(dāng)一個(gè)新作業(yè)到達(dá)時(shí)，其整個(gè)時(shí)間同當(dāng)前進(jìn)程的剩余時(shí)間做比較。如果新的進(jìn)程比當(dāng)前運(yùn)行進(jìn)程需要更少的時(shí)間，當(dāng)前進(jìn)程就被掛起，而運(yùn)行新的進(jìn)程。這種方式能夠使短期作業(yè)獲得良好的服務(wù)。

交互式系統(tǒng)中的調(diào)度

交互式系統(tǒng)中在個(gè)人計(jì)算機(jī)、服務(wù)器和其他系統(tǒng)中都是很常用的，所以有必要來探討一下交互式調(diào)度

輪詢調(diào)度

一種最古老、最簡單、最公平并且最廣泛使用的算法就是 輪詢算法(round-robin)。每個(gè)進(jìn)程都會(huì)被分配一個(gè)時(shí)間段，稱為時(shí)間片(quantum)，在這個(gè)時(shí)間片內(nèi)允許進(jìn)程運(yùn)行。如果時(shí)間片結(jié)束時(shí)進(jìn)程還在運(yùn)行的話，則搶占一個(gè) CPU 并將其分配給另一個(gè)進(jìn)程。如果進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束，則 CPU 立即進(jìn)行切換。輪詢算法比較容易實(shí)現(xiàn)。調(diào)度程序所做的就是維護(hù)一個(gè)可運(yùn)行進(jìn)程的列表，就像下圖中的 a，當(dāng)一個(gè)進(jìn)程用完時(shí)間片后就被移到隊(duì)列的末尾，就像下圖的 b。

時(shí)間片輪詢調(diào)度中唯一有意思的一點(diǎn)就是時(shí)間片的長度。從一個(gè)進(jìn)程切換到另一個(gè)進(jìn)程需要一定的時(shí)間進(jìn)行管理處理，包括保存寄存器的值和內(nèi)存映射、更新不同的表格和列表、清除和重新調(diào)入內(nèi)存高速緩存等。這種切換稱作 進(jìn)程間切換(process switch) 和 上下文切換(context switch)。如果進(jìn)程間的切換時(shí)間需要 1ms，其中包括內(nèi)存映射、清除和重新調(diào)入高速緩存等，再假設(shè)時(shí)間片設(shè)為 4 ms，那么 CPU 在做完 4 ms 有用的工作之后，CPU 將花費(fèi) 1 ms 來進(jìn)行進(jìn)程間的切換。因此，CPU 的時(shí)間片會(huì)浪費(fèi) 20% 的時(shí)間在管理開銷上。耗費(fèi)巨大。

為了提高 CPU 的效率，我們把時(shí)間片設(shè)置為 100 ms?，F(xiàn)在時(shí)間的浪費(fèi)只有 1%。但是考慮會(huì)發(fā)現(xiàn)下面的情況，如果在一個(gè)非常短的時(shí)間內(nèi)到達(dá) 50 個(gè)請(qǐng)求，并且對(duì) CPU 有不同的需求，此時(shí)會(huì)發(fā)生什么？50 個(gè)進(jìn)程都被放在可運(yùn)行進(jìn)程列表中。如果 CP畫U 是空閑的，第一個(gè)進(jìn)程會(huì)立即開始執(zhí)行，第二個(gè)直到 100 ms 以后才會(huì)啟動(dòng)，以此類推。不幸的是最后一個(gè)進(jìn)程需要等待 5 秒才能獲得執(zhí)行機(jī)會(huì)。大部分用戶都會(huì)覺得對(duì)于一個(gè)簡短的指令運(yùn)行 5 秒中是很慢的。如果隊(duì)列末尾的某些請(qǐng)求只需要幾號(hào)秒鐘的運(yùn)行時(shí)間的話，這種設(shè)計(jì)就非常糟糕了。

另外一個(gè)因素是如果時(shí)間片設(shè)置長度要大于 CPU 使用長度，那么搶占就不會(huì)經(jīng)常發(fā)生。相反，在時(shí)間片用完之前，大多數(shù)進(jìn)程都已經(jīng)阻塞了，那么就會(huì)引起進(jìn)程間的切換。消除搶占可提高性能，因?yàn)檫M(jìn)程切換僅在邏輯上必要時(shí)才發(fā)生，即流程阻塞且無法繼續(xù)時(shí)才發(fā)生。

結(jié)論可以表述如下：將上下文切換時(shí)間設(shè)置得太短會(huì)導(dǎo)致過多的進(jìn)程切換并降低 CPU 效率，但設(shè)置時(shí)間太長會(huì)導(dǎo)致一個(gè)短請(qǐng)求很長時(shí)間得不到響應(yīng)。最好的切換時(shí)間是在 20 - 50 毫秒之間設(shè)置。

優(yōu)先級(jí)調(diào)度

輪詢調(diào)度假設(shè)了所有的進(jìn)程是同等重要的。但事實(shí)情況可能不是這樣。例如，在一所大學(xué)中的等級(jí)制度，首先是院長，然后是教授、秘書、后勤人員，最后是學(xué)生。這種將外部情況考慮在內(nèi)就實(shí)現(xiàn)了優(yōu)先級(jí)調(diào)度(priority scheduling)

它的基本思想很明確，每個(gè)進(jìn)程都被賦予一個(gè)優(yōu)先級(jí)，優(yōu)先級(jí)高的進(jìn)程優(yōu)先運(yùn)行。

但是也不意味著高優(yōu)先級(jí)的進(jìn)程能夠永遠(yuǎn)一直運(yùn)行下去，調(diào)度程序會(huì)在每個(gè)時(shí)鐘中斷期間降低當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級(jí)。如果此操作導(dǎo)致其優(yōu)先級(jí)降低到下一個(gè)最高進(jìn)程的優(yōu)先級(jí)以下，則會(huì)發(fā)生進(jìn)程切換。或者，可以為每個(gè)進(jìn)程分配允許運(yùn)行的最大時(shí)間間隔。當(dāng)時(shí)間間隔用完后，下一個(gè)高優(yōu)先級(jí)的進(jìn)程會(huì)得到運(yùn)行的機(jī)會(huì)。

可以靜態(tài)或者動(dòng)態(tài)的為進(jìn)程分配優(yōu)先級(jí)。在一臺(tái)軍用計(jì)算機(jī)上，可以把將軍所啟動(dòng)的進(jìn)程設(shè)為優(yōu)先級(jí) 100，上校為 90 ，少校為 80，上尉為 70，中尉為 60，以此類推。UNIX 中有一條命令為 nice ，它允許用戶為了照顧他人而自愿降低自己進(jìn)程的優(yōu)先級(jí)，但是一般沒人用。

優(yōu)先級(jí)也可以由系統(tǒng)動(dòng)態(tài)分配，用于實(shí)現(xiàn)某種目的。例如，有些進(jìn)程為 I/O 密集型，其多數(shù)時(shí)間用來等待 I/O 結(jié)束。當(dāng)這樣的進(jìn)程需要 CPU 時(shí)，應(yīng)立即分配 CPU，用來啟動(dòng)下一個(gè) I/O 請(qǐng)求，這樣就可以在另一個(gè)進(jìn)程進(jìn)行計(jì)算的同時(shí)執(zhí)行 I/O 操作。這類 I/O 密集型進(jìn)程長時(shí)間的等待 CPU 只會(huì)造成它長時(shí)間占用內(nèi)存。使 I/O 密集型進(jìn)程獲得較好的服務(wù)的一種簡單算法是，將其優(yōu)先級(jí)設(shè)為 1/f，f 為該進(jìn)程在上一時(shí)間片中所占的部分。一個(gè)在 50 ms 的時(shí)間片中只使用 1 ms 的進(jìn)程將獲得優(yōu)先級(jí) 50 ，而在阻塞之前用掉 25 ms 的進(jìn)程將具有優(yōu)先級(jí) 2，而使用掉全部時(shí)間片的進(jìn)程將得到優(yōu)先級(jí) 1。

可以很方便的將一組進(jìn)程按優(yōu)先級(jí)分成若干類，并且在各個(gè)類之間采用優(yōu)先級(jí)調(diào)度，而在各類進(jìn)程的內(nèi)部采用輪轉(zhuǎn)調(diào)度。下面展示了一個(gè)四個(gè)優(yōu)先級(jí)類的系統(tǒng)

它的調(diào)度算法主要描述如下：上面存在優(yōu)先級(jí)為 4 類的可運(yùn)行進(jìn)程，首先會(huì)按照輪轉(zhuǎn)法為每個(gè)進(jìn)程運(yùn)行一個(gè)時(shí)間片，此時(shí)不理會(huì)較低優(yōu)先級(jí)的進(jìn)程。若第 4 類進(jìn)程為空，則按照輪詢的方式運(yùn)行第三類進(jìn)程。若第 4 類和第 3 類進(jìn)程都為空，則按照輪轉(zhuǎn)法運(yùn)行第 2 類進(jìn)程。如果不對(duì)優(yōu)先級(jí)進(jìn)行調(diào)整，則低優(yōu)先級(jí)的進(jìn)程很容易產(chǎn)生饑餓現(xiàn)象。

多級(jí)隊(duì)列

最早使用優(yōu)先級(jí)調(diào)度的系統(tǒng)是 CTSS(Compatible TimeSharing System)。CTSS 是一種兼容分時(shí)系統(tǒng)，它有一個(gè)問題就是進(jìn)程切換太慢，其原因是 IBM 7094 內(nèi)存只能放進(jìn)一個(gè)進(jìn)程。

IBM 是哥倫比亞大學(xué)計(jì)算機(jī)中心在 1964 - 1968 年的計(jì)算機(jī)

CTSS 在每次切換前都需要將當(dāng)前進(jìn)程換出到磁盤，并從磁盤上讀入一個(gè)新進(jìn)程。CTSS 的設(shè)計(jì)者很快就認(rèn)識(shí)到，為 CPU 密集型進(jìn)程設(shè)置較長的時(shí)間片比頻繁地分給他們很短的時(shí)間要更有效（減少交換次數(shù)）。另一方面，如前所述，長時(shí)間片的進(jìn)程又會(huì)影響到響應(yīng)時(shí)間，解決辦法是設(shè)置優(yōu)先級(jí)類。屬于最高優(yōu)先級(jí)的進(jìn)程運(yùn)行一個(gè)時(shí)間片，次高優(yōu)先級(jí)進(jìn)程運(yùn)行 2 個(gè)時(shí)間片，再下面一級(jí)運(yùn)行 4 個(gè)時(shí)間片，以此類推。當(dāng)一個(gè)進(jìn)程用完分配的時(shí)間片后，它被移到下一類。

最短進(jìn)程優(yōu)先

對(duì)于批處理系統(tǒng)而言，由于最短作業(yè)優(yōu)先常常伴隨著最短響應(yīng)時(shí)間，所以如果能夠把它用于交互式進(jìn)程，那將是非常好的。在某種程度上，的確可以做到這一點(diǎn)。交互式進(jìn)程通常遵循下列模式：等待命令、執(zhí)行命令、等待命令、執(zhí)行命令。。。如果我們把每個(gè)命令的執(zhí)行都看作一個(gè)分離的作業(yè)，那么我們可以通過首先運(yùn)行最短的作業(yè)來使響應(yīng)時(shí)間最短。這里唯一的問題是如何從當(dāng)前可運(yùn)行進(jìn)程中找出最短的那一個(gè)進(jìn)程。

一種方式是根據(jù)進(jìn)程過去的行為進(jìn)行推測(cè)，并執(zhí)行估計(jì)運(yùn)行時(shí)間最短的那一個(gè)。假設(shè)每個(gè)終端上每條命令的預(yù)估運(yùn)行時(shí)間為 T0，現(xiàn)在假設(shè)測(cè)量到其下一次運(yùn)行時(shí)間為 T1，可以用兩個(gè)值的加權(quán)來改進(jìn)估計(jì)時(shí)間，即aT0+ (1- 1)T1。通過選擇 a 的值，可以決定是盡快忘掉老的運(yùn)行時(shí)間，還是在一段長時(shí)間內(nèi)始終記住它們。當(dāng) a = 1/2 時(shí)，可以得到下面這個(gè)序列

可以看到，在三輪過后，T0 在新的估計(jì)值中所占比重下降至 1/8。


有時(shí)把這種通過當(dāng)前測(cè)量值和先前估計(jì)值進(jìn)行加權(quán)平均從而得到下一個(gè)估計(jì)值的技術(shù)稱作 老化(aging)。這種方法會(huì)使用很多預(yù)測(cè)值基于當(dāng)前值的情況。

保證調(diào)度

一種完全不同的調(diào)度方法是對(duì)用戶做出明確的性能保證。一種實(shí)際而且容易實(shí)現(xiàn)的保證是：若用戶工作時(shí)有 n 個(gè)用戶登錄，則每個(gè)用戶將獲得 CPU 處理能力的 1/n。類似地，在一個(gè)有 n 個(gè)進(jìn)程運(yùn)行的單用戶系統(tǒng)中，若所有的進(jìn)程都等價(jià)，則每個(gè)進(jìn)程將獲得 1/n 的 CPU 時(shí)間。

彩票調(diào)度

對(duì)用戶進(jìn)行承諾并在隨后兌現(xiàn)承諾是一件好事，不過很難實(shí)現(xiàn)。但是存在著一種簡單的方式，有一種既可以給出預(yù)測(cè)結(jié)果而又有一種比較簡單的實(shí)現(xiàn)方式的算法，就是 彩票調(diào)度(lottery scheduling)算法。

其基本思想是為進(jìn)程提供各種系統(tǒng)資源（例如 CPU 時(shí)間）的彩票。當(dāng)做出一個(gè)調(diào)度決策的時(shí)候，就隨機(jī)抽出一張彩票，擁有彩票的進(jìn)程將獲得該資源。在應(yīng)用到 CPU 調(diào)度時(shí)，系統(tǒng)可以每秒持有 50 次抽獎(jiǎng)，每個(gè)中獎(jiǎng)?wù)邔@得比如 20 毫秒的 CPU 時(shí)間作為獎(jiǎng)勵(lì)。

George Orwell 關(guān)于 所有的進(jìn)程是平等的，但是某些進(jìn)程能夠更平等一些。一些重要的進(jìn)程可以給它們額外的彩票，以便增加他們贏得的機(jī)會(huì)。如果出售了 100 張彩票，而且有一個(gè)進(jìn)程持有了它們中的 20 張，它就會(huì)有 20% 的機(jī)會(huì)去贏得彩票中獎(jiǎng)。在長時(shí)間的運(yùn)行中，它就會(huì)獲得 20% 的CPU。相反，對(duì)于優(yōu)先級(jí)調(diào)度程序，很難說明擁有優(yōu)先級(jí) 40 究竟是什么意思，這里的規(guī)則很清楚，擁有彩票 f 份額的進(jìn)程大約得到系統(tǒng)資源的 f 份額。

如果希望進(jìn)程之間協(xié)作的話可以交換它們之間的票據(jù)。例如，客戶端進(jìn)程給服務(wù)器進(jìn)程發(fā)送了一條消息后阻塞，客戶端進(jìn)程可能會(huì)把自己所有的票據(jù)都交給服務(wù)器，來增加下一次服務(wù)器運(yùn)行的機(jī)會(huì)。當(dāng)服務(wù)完成后，它會(huì)把彩票還給客戶端讓其有機(jī)會(huì)再次運(yùn)行。事實(shí)上，如果沒有客戶機(jī)，服務(wù)器也根本不需要彩票。

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

公平分享調(diào)度

到目前為止，我們假設(shè)被調(diào)度的都是各個(gè)進(jìn)程自身，而不用考慮該進(jìn)程的擁有者是誰。結(jié)果是，如果用戶 1 啟動(dòng)了 9 個(gè)進(jìn)程，而用戶 2 啟動(dòng)了一個(gè)進(jìn)程，使用輪轉(zhuǎn)或相同優(yōu)先級(jí)調(diào)度算法，那么用戶 1 將得到 90 % 的 CPU 時(shí)間，而用戶 2 將之得到 10 % 的 CPU 時(shí)間。

為了阻止這種情況的出現(xiàn)，一些系統(tǒng)在調(diào)度前會(huì)把進(jìn)程的擁有者考慮在內(nèi)。在這種模型下，每個(gè)用戶都會(huì)分配一些CPU 時(shí)間，而調(diào)度程序會(huì)選擇進(jìn)程并強(qiáng)制執(zhí)行。因此如果兩個(gè)用戶每個(gè)都會(huì)有 50% 的 CPU 時(shí)間片保證，那么無論一個(gè)用戶有多少個(gè)進(jìn)程，都將獲得相同的 CPU 份額。

實(shí)時(shí)系統(tǒng)中的調(diào)度

實(shí)時(shí)系統(tǒng)(real-time) 是一個(gè)時(shí)間扮演了重要作用的系統(tǒng)。典型的，一種或多種外部物理設(shè)備發(fā)給計(jì)算機(jī)一個(gè)服務(wù)請(qǐng)求，而計(jì)算機(jī)必須在一個(gè)確定的時(shí)間范圍內(nèi)恰當(dāng)?shù)淖龀龇磻?yīng)。例如，在 CD 播放器中的計(jì)算機(jī)會(huì)獲得從驅(qū)動(dòng)器過來的位流，然后必須在非常短的時(shí)間內(nèi)將位流轉(zhuǎn)換為音樂播放出來。如果計(jì)算時(shí)間過長，那么音樂就會(huì)聽起來有異常。再比如說醫(yī)院特別護(hù)理部門的病人監(jiān)護(hù)裝置、飛機(jī)中的自動(dòng)駕駛系統(tǒng)、列車中的煙霧警告裝置等，在這些例子中，正確但是卻緩慢的響應(yīng)要比沒有響應(yīng)甚至還糟糕。

實(shí)時(shí)系統(tǒng)可以分為兩類，硬實(shí)時(shí)(hard real time) 和 軟實(shí)時(shí)(soft real time) 系統(tǒng)，前者意味著必須要滿足絕對(duì)的截止時(shí)間；后者的含義是雖然不希望偶爾錯(cuò)失截止時(shí)間，但是可以容忍。在這兩種情形中，實(shí)時(shí)都是通過把程序劃分為一組進(jìn)程而實(shí)現(xiàn)的，其中每個(gè)進(jìn)程的行為是可預(yù)測(cè)和提前可知的。這些進(jìn)程一般壽命較短，并且極快的運(yùn)行完成。在檢測(cè)到一個(gè)外部信號(hào)時(shí)，調(diào)度程序的任務(wù)就是按照滿足所有截止時(shí)間的要求調(diào)度進(jìn)程。

實(shí)時(shí)系統(tǒng)中的事件可以按照響應(yīng)方式進(jìn)一步分類為周期性(以規(guī)則的時(shí)間間隔發(fā)生)事件或 非周期性(發(fā)生時(shí)間不可預(yù)知)事件。一個(gè)系統(tǒng)可能要響應(yīng)多個(gè)周期性事件流，根據(jù)每個(gè)事件處理所需的時(shí)間，可能甚至無法處理所有事件。例如，如果有 m 個(gè)周期事件，事件 i 以周期 Pi 發(fā)生，并需要 Ci 秒 CPU 時(shí)間處理一個(gè)事件，那么可以處理負(fù)載的條件是

只有滿足這個(gè)條件的實(shí)時(shí)系統(tǒng)稱為可調(diào)度的，這意味著它實(shí)際上能夠被實(shí)現(xiàn)。一個(gè)不滿足此檢驗(yàn)標(biāo)準(zhǔn)的進(jìn)程不能被調(diào)度，因?yàn)檫@些進(jìn)程共同需要的 CPU 時(shí)間總和大于 CPU 能提供的時(shí)間。

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

實(shí)時(shí)系統(tǒng)的調(diào)度算法可以是靜態(tài)的或動(dòng)態(tài)的。前者在系統(tǒng)開始運(yùn)行之前做出調(diào)度決策；后者在運(yùn)行過程中進(jìn)行調(diào)度決策。只有在可以提前掌握所完成的工作以及必須滿足的截止時(shí)間等信息時(shí)，靜態(tài)調(diào)度才能工作，而動(dòng)態(tài)調(diào)度不需要這些限制。

調(diào)度策略和機(jī)制

到目前為止，我們隱含的假設(shè)系統(tǒng)中所有進(jìn)程屬于不同的分組用戶并且進(jìn)程間存在相互競(jìng)爭(zhēng) CPU 的情況。通常情況下確實(shí)如此，但有時(shí)也會(huì)發(fā)生一個(gè)進(jìn)程會(huì)有很多子進(jìn)程并在其控制下運(yùn)行的情況。例如，一個(gè)數(shù)據(jù)庫管理系統(tǒng)進(jìn)程會(huì)有很多子進(jìn)程。每一個(gè)子進(jìn)程可能處理不同的請(qǐng)求，或者每個(gè)子進(jìn)程實(shí)現(xiàn)不同的功能（如請(qǐng)求分析、磁盤訪問等）。主進(jìn)程完全可能掌握哪一個(gè)子進(jìn)程最重要（或最緊迫），而哪一個(gè)最不重要。但是，以上討論的調(diào)度算法中沒有一個(gè)算法從用戶進(jìn)程接收有關(guān)的調(diào)度決策信息，這就導(dǎo)致了調(diào)度程序很少能夠做出最優(yōu)的選擇。

解決問題的辦法是將 調(diào)度機(jī)制(scheduling mechanism) 和 調(diào)度策略(scheduling policy) 分開，這是長期一貫的原則。這也就意味著調(diào)度算法在某種方式下被參數(shù)化了，但是參數(shù)可以被用戶進(jìn)程填寫。讓我們首先考慮數(shù)據(jù)庫的例子。假設(shè)內(nèi)核使用優(yōu)先級(jí)調(diào)度算法，并提供了一條可供進(jìn)程設(shè)置優(yōu)先級(jí)的系統(tǒng)調(diào)用。這樣，盡管父進(jìn)程本身并不參與調(diào)度，但它可以控制如何調(diào)度子進(jìn)程的細(xì)節(jié)。調(diào)度機(jī)制位于內(nèi)核，而調(diào)度策略由用戶進(jìn)程決定，調(diào)度策略和機(jī)制分離是一種關(guān)鍵性思路。

線程調(diào)度

當(dāng)若干進(jìn)程都有多個(gè)線程時(shí)，就存在兩個(gè)層次的并行：進(jìn)程和線程。在這樣的系統(tǒng)中調(diào)度處理有本質(zhì)的差別，這取決于所支持的是用戶級(jí)線程還是內(nèi)核級(jí)線程（或兩者都支持）。

首先考慮用戶級(jí)線程，由于內(nèi)核并不知道有線程存在，所以內(nèi)核還是和以前一樣地操作，選取一個(gè)進(jìn)程，假設(shè)為 A，并給予 A 以時(shí)間片控制。A 中的線程調(diào)度程序決定哪個(gè)線程運(yùn)行。假設(shè)為 A1。由于多道線程并不存在時(shí)鐘中斷，所以這個(gè)線程可以按其意愿任意運(yùn)行多長時(shí)間。如果該線程用完了進(jìn)程的全部時(shí)間片，內(nèi)核就會(huì)選擇另一個(gè)進(jìn)程繼續(xù)運(yùn)行。

在進(jìn)程 A 終于又一次運(yùn)行時(shí)，線程 A1 會(huì)接著運(yùn)行。該線程會(huì)繼續(xù)耗費(fèi) A 進(jìn)程的所有時(shí)間，直到它完成工作。不過，線程運(yùn)行不會(huì)影響到其他進(jìn)程。其他進(jìn)程會(huì)得到調(diào)度程序所分配的合適份額，不會(huì)考慮進(jìn)程 A 內(nèi)部發(fā)生的事情。

現(xiàn)在考慮 A 線程每次 CPU 計(jì)算的工作比較少的情況，例如：在 50 ms 的時(shí)間片中有 5 ms 的計(jì)算工作。于是，每個(gè)線程運(yùn)行一會(huì)兒，然后把 CPU 交回給線程調(diào)度程序。這樣在內(nèi)核切換到進(jìn)程 B 之前，就會(huì)有序列 A1,A2,A3,A1,A2,A3,A1,A2,A3,A1 。如下所示

運(yùn)行時(shí)系統(tǒng)使用的調(diào)度算法可以是上面介紹算法的任意一種。從實(shí)用方面考慮，輪轉(zhuǎn)調(diào)度和優(yōu)先級(jí)調(diào)度更為常用。唯一的局限是，缺乏一個(gè)時(shí)鐘中斷運(yùn)行過長的線程。但由于線程之間的合作關(guān)系，這通常也不是問題。

現(xiàn)在考慮使用內(nèi)核線程的情況，內(nèi)核選擇一個(gè)特定的線程運(yùn)行。它不用考慮線程屬于哪個(gè)進(jìn)程，不過如果有必要的話，也可以這么做。對(duì)被選擇的線程賦予一個(gè)時(shí)間片，而且如果超過了時(shí)間片，就會(huì)強(qiáng)制掛起該線程。一個(gè)線程在 50 ms 的時(shí)間片內(nèi)，5 ms 之后被阻塞，在 30 ms 的時(shí)間片中，線程的順序會(huì)是 A1,B1,A2,B2,A3,B3。如下圖所示

用戶級(jí)線程和內(nèi)核級(jí)線程之間的主要差別在于性能。用戶級(jí)線程的切換需要少量的機(jī)器指令（想象一下Java程序的線程切換），而內(nèi)核線程需要完整的上下文切換，修改內(nèi)存映像，使高速緩存失效，這會(huì)導(dǎo)致了若干數(shù)量級(jí)的延遲。另一方面，在使用內(nèi)核級(jí)線程時(shí)，一旦線程阻塞在 I/O 上就不需要在用戶級(jí)線程中那樣將整個(gè)進(jìn)程掛起。


從進(jìn)程 A 的一個(gè)線程切換到進(jìn)程 B 的一個(gè)線程，其消耗要遠(yuǎn)高于運(yùn)行進(jìn)程 A 的兩個(gè)線程（涉及修改內(nèi)存映像，修改高速緩存），內(nèi)核對(duì)這種切換的消耗是了解到，可以通過這些信息作出決定。

文章參考：

《現(xiàn)代操作系統(tǒng)》

《Modern Operating System》forth edition

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

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

https://www./process_hierarchy.xhtml

https://en./wiki/Runtime_system

https://en./wiki/Execution_model

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

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

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

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