前言

先來看看一則小故事

我們寫好的一行行代碼，為了讓其工作起來，我們還得把它送進(jìn)城（進(jìn)程）里，那既然進(jìn)了城里，那肯定不能胡作非為了。

城里人有城里人的規(guī)矩，城中有個(gè)專門管轄你們的城管（操作系統(tǒng)），人家讓你休息就休息，讓你工作就工作，畢竟攤位（CPU）就一個(gè)，每個(gè)人都要占這個(gè)攤位來工作，城里要工作的人多著去了。

所以城管為了公平起見，它使用一種策略（調(diào)度）方式，給每個(gè)人一個(gè)固定的工作時(shí)間（時(shí)間片），時(shí)間到了就會(huì)通知你去休息而換另外一個(gè)人上場(chǎng)工作。

另外，在休息時(shí)候你也不能偷懶，要記住工作到哪了，不然下次到你工作了，你忘記工作到哪了，那還怎么繼續(xù)？

有的人，可能還進(jìn)入了縣城（線程）工作，這里相對(duì)輕松一些，在休息的時(shí)候，要記住的東西相對(duì)較少，而且還能共享城里的資源。

“哎喲，難道本文內(nèi)容是進(jìn)程和線程？”

可以，聰明的你猜出來了，也不枉費(fèi)我瞎編亂造的故事了。

進(jìn)程和線程對(duì)于寫代碼的我們，真的天天見、日日見了，但見的多不代表你就熟悉它們，比如簡(jiǎn)單問你一句，你知道它們的工作原理和區(qū)別嗎？

不知道沒關(guān)系，今天就要跟大家討論操作系統(tǒng)的進(jìn)程和線程。

進(jìn)程

我們編寫的代碼只是一個(gè)存儲(chǔ)在硬盤的靜態(tài)文件，通過編譯后就會(huì)生成二進(jìn)制可執(zhí)行文件，當(dāng)我們運(yùn)行這個(gè)可執(zhí)行文件后，它會(huì)被裝載到內(nèi)存中，接著 CPU 會(huì)執(zhí)行程序中的每一條指令，那么這個(gè)運(yùn)行中的程序，就被稱為「進(jìn)程」。

現(xiàn)在我們考慮有一個(gè)會(huì)讀取硬盤文件數(shù)據(jù)的程序被執(zhí)行了，那么當(dāng)運(yùn)行到讀取文件的指令時(shí)，就會(huì)去從硬盤讀取數(shù)據(jù)，但是硬盤的讀寫速度是非常慢的，那么在這個(gè)時(shí)候，如果 CPU 傻傻的等硬盤返回?cái)?shù)據(jù)的話，那 CPU 的利用率是非常低的。

做個(gè)類比，你去煮開水時(shí)，你會(huì)傻傻的等水壺?zé)_嗎？很明顯，小孩也不會(huì)傻等。我們可以在水壺?zé)_之前去做其他事情。當(dāng)水壺?zé)_了，我們自然就會(huì)聽到“嘀嘀嘀”的聲音，于是再把燒開的水倒入到水杯里就好了。

所以，當(dāng)進(jìn)程要從硬盤讀取數(shù)據(jù)時(shí)，CPU 不需要阻塞等待數(shù)據(jù)的返回，而是去執(zhí)行另外的進(jìn)程。當(dāng)硬盤數(shù)據(jù)返回時(shí)，CPU 會(huì)收到個(gè)中斷，于是 CPU 再繼續(xù)運(yùn)行這個(gè)進(jìn)程。

這種多個(gè)程序、交替執(zhí)行的思想，就有 CPU 管理多個(gè)進(jìn)程的初步想法。

對(duì)于一個(gè)支持多進(jìn)程的系統(tǒng)，CPU 會(huì)從一個(gè)進(jìn)程快速切換至另一個(gè)進(jìn)程，其間每個(gè)進(jìn)程各運(yùn)行幾十或幾百個(gè)毫秒。

雖然單核的 CPU 在某一個(gè)瞬間，只能運(yùn)行一個(gè)進(jìn)程。但在 1 秒鐘期間，它可能會(huì)運(yùn)行多個(gè)進(jìn)程，這樣就產(chǎn)生并行的錯(cuò)覺，實(shí)際上這是并發(fā)。

并發(fā)和并行有什么區(qū)別？

一圖勝千言。

進(jìn)程與程序的關(guān)系的類比

到了晚飯時(shí)間，一對(duì)小情侶肚子都咕咕叫了，于是男生見機(jī)行事，就想給女生做晚飯，所以他就在網(wǎng)上找了辣子雞的菜譜，接著買了一些雞肉、辣椒、香料等材料，然后邊看邊學(xué)邊做這道菜。

突然，女生說她想喝可樂，那么男生只好把做菜的事情暫停一下，并在手機(jī)菜譜標(biāo)記做到哪一個(gè)步驟，把狀態(tài)信息記錄了下來。

然后男生聽從女生的指令，跑去下樓買了一瓶冰可樂后，又回到廚房繼續(xù)做菜。

這體現(xiàn)了，CPU 可以從一個(gè)進(jìn)程（做菜）切換到另外一個(gè)進(jìn)程（買可樂），在切換前必須要記錄當(dāng)前進(jìn)程中運(yùn)行的狀態(tài)信息，以備下次切換回來的時(shí)候可以恢復(fù)執(zhí)行。

所以，可以發(fā)現(xiàn)進(jìn)程有著「運(yùn)行 - 暫停 - 運(yùn)行」的活動(dòng)規(guī)律。

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

在上面，我們知道了進(jìn)程有著「運(yùn)行 - 暫停 - 運(yùn)行」的活動(dòng)規(guī)律。一般說來，一個(gè)進(jìn)程并不是自始至終連續(xù)不停地運(yùn)行的，它與并發(fā)執(zhí)行中的其他進(jìn)程的執(zhí)行是相互制約的。

它有時(shí)處于運(yùn)行狀態(tài)，有時(shí)又由于某種原因而暫停運(yùn)行處于等待狀態(tài)，當(dāng)使它暫停的原因消失后，它又進(jìn)入準(zhǔn)備運(yùn)行狀態(tài)。

所以，在一個(gè)進(jìn)程的活動(dòng)期間至少具備三種基本狀態(tài)，即運(yùn)行狀態(tài)、就緒狀態(tài)、阻塞狀態(tài)。

上圖中各個(gè)狀態(tài)的意義：

• 運(yùn)行狀態(tài)（Runing）：該時(shí)刻進(jìn)程占用 CPU；

• 就緒狀態(tài)（Ready）：可運(yùn)行，但因?yàn)槠渌M(jìn)程正在運(yùn)行而暫停停止；

• 阻塞狀態(tài)（Blocked）：該進(jìn)程正在等待某一事件發(fā)生（如等待輸入/輸出操作的完成）而暫時(shí)停止運(yùn)行，這時(shí)，即使給它CPU控制權(quán)，它也無法運(yùn)行；

當(dāng)然，進(jìn)程另外兩個(gè)基本狀態(tài)：

• 創(chuàng)建狀態(tài)（new）：進(jìn)程正在被創(chuàng)建時(shí)的狀態(tài)；

• 結(jié)束狀態(tài)（Exit）：進(jìn)程正在從系統(tǒng)中消失時(shí)的狀態(tài)；

于是，一個(gè)完整的進(jìn)程狀態(tài)的變遷如下圖：

再來詳細(xì)說明一下進(jìn)程的狀態(tài)變遷：

• NULL -> 創(chuàng)建狀態(tài)：一個(gè)新進(jìn)程被創(chuàng)建時(shí)的第一個(gè)狀態(tài)；

• 創(chuàng)建狀態(tài) -> 就緒狀態(tài)：當(dāng)進(jìn)程被創(chuàng)建完成并初始化后，一切就緒準(zhǔn)備運(yùn)行時(shí)，變?yōu)榫途w狀態(tài)，這個(gè)過程是很快的；

• 就緒態(tài) -> 運(yùn)行狀態(tài)：處于就緒狀態(tài)的進(jìn)程被操作系統(tǒng)的進(jìn)程調(diào)度器選中后，就分配給 CPU 正式運(yùn)行該進(jìn)程；

• 運(yùn)行狀態(tài) -> 結(jié)束狀態(tài)：當(dāng)進(jìn)程已經(jīng)運(yùn)行完成或出錯(cuò)時(shí)，會(huì)被操作系統(tǒng)作結(jié)束狀態(tài)處理；

• 運(yùn)行狀態(tài) -> 就緒狀態(tài)：處于運(yùn)行狀態(tài)的進(jìn)程在運(yùn)行過程中，由于分配給它的運(yùn)行時(shí)間片用完，操作系統(tǒng)會(huì)把該進(jìn)程變?yōu)榫途w態(tài)，接著從就緒態(tài)選中另外一個(gè)進(jìn)程運(yùn)行；

• 運(yùn)行狀態(tài) -> 阻塞狀態(tài)：當(dāng)進(jìn)程請(qǐng)求某個(gè)事件且必須等待時(shí)，例如請(qǐng)求 I/O 事件；

• 阻塞狀態(tài) -> 就緒狀態(tài)：當(dāng)進(jìn)程要等待的事件完成時(shí)，它從阻塞狀態(tài)變到就緒狀態(tài)；

另外，還有一個(gè)狀態(tài)叫掛起狀態(tài)，它表示進(jìn)程沒有占有物理內(nèi)存空間。這跟阻塞狀態(tài)是不一樣，阻塞狀態(tài)是等待某個(gè)事件的返回。

由于虛擬內(nèi)存管理原因，進(jìn)程的所使用的空間可能并沒有映射到物理內(nèi)存，而是在硬盤上，這時(shí)進(jìn)程就會(huì)出現(xiàn)掛起狀態(tài)，另外調(diào)用 sleep 也會(huì)被掛起。

掛起狀態(tài)可以分為兩種：

• 阻塞掛起狀態(tài)：進(jìn)程在外存（硬盤）并等待某個(gè)事件的出現(xiàn)；

• 就緒掛起狀態(tài)：進(jìn)程在外存（硬盤），但只要進(jìn)入內(nèi)存，即刻立刻運(yùn)行；

這兩種掛起狀態(tài)加上前面的五種狀態(tài)，就變成了七種狀態(tài)變遷（留給我的顏色不多了），見如下圖：

進(jìn)程的控制結(jié)構(gòu)

在操作系統(tǒng)中，是用進(jìn)程控制塊（process control block，PCB）數(shù)據(jù)結(jié)構(gòu)來描述進(jìn)程的。

那 PCB 是什么呢？打開知乎搜索你就會(huì)發(fā)現(xiàn)這個(gè)東西并不是那么簡(jiǎn)單。

打住打住，我們是個(gè)正經(jīng)的人，怎么會(huì)去看那些問題呢？是吧，回來回來。

PCB 是進(jìn)程存在的唯一標(biāo)識(shí)，這意味著一個(gè)進(jìn)程的存在，必然會(huì)有一個(gè) PCB，如果進(jìn)程消失了，那么 PCB 也會(huì)隨之消失。

PCB 具體包含什么信息呢？

進(jìn)程描述信息：

• 進(jìn)程標(biāo)識(shí)符：標(biāo)識(shí)各個(gè)進(jìn)程，每個(gè)進(jìn)程都有一個(gè)并且唯一的標(biāo)識(shí)符；

• 用戶標(biāo)識(shí)符：進(jìn)程歸屬的用戶，用戶標(biāo)識(shí)符主要為共享和保護(hù)服務(wù)；

進(jìn)程控制和管理信息：

• 進(jìn)程當(dāng)前狀態(tài)，如 new、ready、running、waiting 或 blocked 等；

• 進(jìn)程優(yōu)先級(jí)：進(jìn)程搶占 CPU 時(shí)的優(yōu)先級(jí)；

資源分配清單：

• 有關(guān)內(nèi)存地址空間或虛擬地址空間的信息，所打開文件的列表和所使用的 I/O 設(shè)備信息。

CPU 相關(guān)信息：

• CPU 中各個(gè)寄存器的值，當(dāng)進(jìn)程被切換時(shí)，CPU 的狀態(tài)信息都會(huì)被保存在相應(yīng)的 PCB 中，以便進(jìn)程重新執(zhí)行時(shí)，能從斷點(diǎn)處繼續(xù)執(zhí)行。

可見，PCB 包含信息還是比較多的。

每個(gè) PCB 是如何組織的呢？

通常是通過鏈表的方式進(jìn)行組織，把具有相同狀態(tài)的進(jìn)程鏈在一起，組成各種隊(duì)列。比如：

• 將所有處于就緒狀態(tài)的進(jìn)程鏈在一起，稱為就緒隊(duì)列；

• 把所有因等待某事件而處于等待狀態(tài)的進(jìn)程鏈在一起就組成各種阻塞隊(duì)列；

• 另外，對(duì)于運(yùn)行隊(duì)列在單核 CPU 系統(tǒng)中則只有一個(gè)運(yùn)行指針了，因?yàn)閱魏?CPU 在某個(gè)時(shí)間，只能運(yùn)行一個(gè)程序。

那么，就緒隊(duì)列和阻塞隊(duì)列鏈表的組織形式如下圖：

除了鏈接的組織方式，還有索引方式，它的工作原理：將同一狀態(tài)的進(jìn)程組織在一個(gè)索引表中，索引表項(xiàng)指向相應(yīng)的 PCB，不同狀態(tài)對(duì)應(yīng)不同的索引表。

一般會(huì)選擇鏈表，因?yàn)榭赡苊媾R進(jìn)程創(chuàng)建，銷毀等調(diào)度導(dǎo)致進(jìn)程狀態(tài)發(fā)生變化，所以鏈表能夠更加靈活的插入和刪除。

進(jìn)程的控制

我們熟知了進(jìn)程的狀態(tài)變遷和進(jìn)程的數(shù)據(jù)結(jié)構(gòu) PCB 后，再來看看進(jìn)程的創(chuàng)建、終止、阻塞、喚醒的過程，這些過程也就是進(jìn)程的控制。

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

操作系統(tǒng)允許一個(gè)進(jìn)程創(chuàng)建另一個(gè)進(jìn)程，而且允許子進(jìn)程繼承父進(jìn)程所擁有的資源，當(dāng)子進(jìn)程被終止時(shí)，其在父進(jìn)程處繼承的資源應(yīng)當(dāng)還給父進(jìn)程。同時(shí)，終止父進(jìn)程時(shí)同時(shí)也會(huì)終止其所有的子進(jìn)程。

創(chuàng)建進(jìn)程的過程如下：

• 為新進(jìn)程分配一個(gè)唯一的進(jìn)程標(biāo)識(shí)號(hào)，并申請(qǐng)一個(gè)空白的 PCB，PCB 是有限的，若申請(qǐng)失敗則創(chuàng)建失??；

• 為進(jìn)程分配資源，此處如果資源不足，進(jìn)程就會(huì)進(jìn)入等待狀態(tài)，以等待資源；

• 初始化 PCB；

• 如果進(jìn)程的調(diào)度隊(duì)列能夠接納新進(jìn)程，那就將進(jìn)程插入到就緒隊(duì)列，等待被調(diào)度運(yùn)行；

02 終止進(jìn)程

進(jìn)程可以有 3 種終止方式：正常結(jié)束、異常結(jié)束以及外界干預(yù)（信號(hào)kill 掉）。

終止進(jìn)程的過程如下：

• 查找需要終止的進(jìn)程的 PCB；

• 如果處于執(zhí)行狀態(tài)，則立即終止該進(jìn)程的執(zhí)行，然后將 CPU 資源分配給其他進(jìn)程；

• 如果其還有子進(jìn)程，則應(yīng)將其所有子進(jìn)程終止；

• 將該進(jìn)程所擁有的全部資源都?xì)w還給父進(jìn)程或操作系統(tǒng)；

• 將其從 PCB 所在隊(duì)列中刪除；

03 阻塞進(jìn)程

當(dāng)進(jìn)程需要等待某一事件完成時(shí)，它可以調(diào)用阻塞語句把自己阻塞等待。而一旦被阻塞等待，它只能由另一個(gè)進(jìn)程喚醒。

阻塞進(jìn)程的過程如下：

• 找到將要被阻塞進(jìn)程標(biāo)識(shí)號(hào)對(duì)應(yīng)的 PCB；

• 如果該進(jìn)程為運(yùn)行狀態(tài)，則保護(hù)其現(xiàn)場(chǎng)，將其狀態(tài)轉(zhuǎn)為阻塞狀態(tài)，停止運(yùn)行；

• 將該 PCB 插入的阻塞隊(duì)列中去；

04 喚醒進(jìn)程

進(jìn)程由「運(yùn)行」轉(zhuǎn)變?yōu)椤缸枞範(fàn)顟B(tài)是由于進(jìn)程必須等待某一事件的完成，所以處于阻塞狀態(tài)的進(jìn)程是絕對(duì)不可能叫醒自己的。

如果某進(jìn)程正在等待 I/O 事件，需由別的進(jìn)程發(fā)消息給它，則只有當(dāng)該進(jìn)程所期待的事件出現(xiàn)時(shí)，才由發(fā)現(xiàn)者進(jìn)程用喚醒語句叫醒它。

喚醒進(jìn)程的過程如下：

• 在該事件的阻塞隊(duì)列中找到相應(yīng)進(jìn)程的 PCB；

• 將其從阻塞隊(duì)列中移出，并置其狀態(tài)為就緒狀態(tài)；

• 把該 PCB 插入到就緒隊(duì)列中，等待調(diào)度程序調(diào)度；

進(jìn)程的阻塞和喚醒是一對(duì)功能相反的語句，如果某個(gè)進(jìn)程調(diào)用了阻塞語句，則必有一個(gè)與之對(duì)應(yīng)的喚醒語句。

進(jìn)程的上下文切換

各個(gè)進(jìn)程之間是共享 CPU 資源的，在不同的時(shí)候進(jìn)程之間需要切換，讓不同的進(jìn)程可以在 CPU 執(zhí)行，那么這個(gè)一個(gè)進(jìn)程切換到另一個(gè)進(jìn)程運(yùn)行，稱為進(jìn)程的上下文切換。

在詳細(xì)說進(jìn)程上下文切換前，我們先來看看 CPU 上下文切換

大多數(shù)操作系統(tǒng)都是多任務(wù)，通常支持大于 CPU 數(shù)量的任務(wù)同時(shí)運(yùn)行。實(shí)際上，這些任務(wù)并不是同時(shí)運(yùn)行的，只是因?yàn)橄到y(tǒng)在很短的時(shí)間內(nèi)，讓各個(gè)任務(wù)分別在 CPU 運(yùn)行，于是就造成同時(shí)運(yùn)行的錯(cuò)覺。

任務(wù)是交給 CPU 運(yùn)行的，那么在每個(gè)任務(wù)運(yùn)行前，CPU 需要知道任務(wù)從哪里加載，又從哪里開始運(yùn)行。

所以，操作系統(tǒng)需要事先幫 CPU 設(shè)置好 CPU 寄存器和程序計(jì)數(shù)器。

CPU 寄存器是 CPU 內(nèi)部一個(gè)容量小，但是速度極快的內(nèi)存（緩存）。我舉個(gè)例子，寄存器像是你的口袋，內(nèi)存像你的書包，硬盤則是你家里的柜子，如果你的東西存放到口袋，那肯定是比你從書包或家里柜子取出來要快的多。

再來，程序計(jì)數(shù)器則是用來存儲(chǔ) CPU 正在執(zhí)行的指令位置、或者即將執(zhí)行的下一條指令位置。

所以說，CPU 寄存器和程序計(jì)數(shù)是 CPU 在運(yùn)行任何任務(wù)前，所必須依賴的環(huán)境，這些環(huán)境就叫做 CPU 上下文。

既然知道了什么是 CPU 上下文，那理解 CPU 上下文切換就不難了。

CPU 上下文切換就是先把前一個(gè)任務(wù)的 CPU 上下文（CPU 寄存器和程序計(jì)數(shù)器）保存起來，然后加載新任務(wù)的上下文到這些寄存器和程序計(jì)數(shù)器，最后再跳轉(zhuǎn)到程序計(jì)數(shù)器所指的新位置，運(yùn)行新任務(wù)。

系統(tǒng)內(nèi)核會(huì)存儲(chǔ)保持下來的上下文信息，當(dāng)此任務(wù)再次被分配給 CPU 運(yùn)行時(shí)，CPU 會(huì)重新加載這些上下文，這樣就能保證任務(wù)原來的狀態(tài)不受影響，讓任務(wù)看起來還是連續(xù)運(yùn)行。

上面說到所謂的「任務(wù)」，主要包含進(jìn)程、線程和中斷。所以，可以根據(jù)任務(wù)的不同，把 CPU 上下文切換分成：進(jìn)程上下文切換、線程上下文切換和中斷上下文切換。

進(jìn)程的上下文切換到底是切換什么呢？

進(jìn)程是由內(nèi)核管理和調(diào)度的，所以進(jìn)程的切換只能發(fā)生在內(nèi)核態(tài)。

所以，進(jìn)程的上下文切換不僅包含了虛擬內(nèi)存、棧、全局變量等用戶空間的資源，還包括了內(nèi)核堆棧、寄存器等內(nèi)核空間的資源。

通常，會(huì)把交換的信息保存在進(jìn)程的 PCB，當(dāng)要運(yùn)行另外一個(gè)進(jìn)程的時(shí)候，我們需要從這個(gè)進(jìn)程的 PCB 取出上下文，然后恢復(fù)到 CPU 中，這使得這個(gè)進(jìn)程可以繼續(xù)執(zhí)行，如下圖所示：

大家需要注意，進(jìn)程的上下文開銷是很關(guān)鍵的，我們希望它的開銷越小越好，這樣可以使得進(jìn)程可以把更多時(shí)間花費(fèi)在執(zhí)行程序上，而不是耗費(fèi)在上下文切換。

發(fā)生進(jìn)程上下文切換有哪些場(chǎng)景？

• 為了保證所有進(jìn)程可以得到公平調(diào)度，CPU 時(shí)間被劃分為一段段的時(shí)間片，這些時(shí)間片再被輪流分配給各個(gè)進(jìn)程。這樣，當(dāng)某個(gè)進(jìn)程的時(shí)間片耗盡了，就會(huì)被系統(tǒng)掛起，切換到其它正在等待 CPU 的進(jìn)程運(yùn)行；

• 進(jìn)程在系統(tǒng)資源不足（比如內(nèi)存不足）時(shí)，要等到資源滿足后才可以運(yùn)行，這個(gè)時(shí)候進(jìn)程也會(huì)被掛起，并由系統(tǒng)調(diào)度其他進(jìn)程運(yùn)行；

• 當(dāng)進(jìn)程通過睡眠函數(shù) sleep 這樣的方法將自己主動(dòng)掛起時(shí)，自然也會(huì)重新調(diào)度；

• 當(dāng)有優(yōu)先級(jí)更高的進(jìn)程運(yùn)行時(shí)，為了保證高優(yōu)先級(jí)進(jìn)程的運(yùn)行，當(dāng)前進(jìn)程會(huì)被掛起，由高優(yōu)先級(jí)進(jìn)程來運(yùn)行；

• 發(fā)生硬件中斷時(shí)，CPU 上的進(jìn)程會(huì)被中斷掛起，轉(zhuǎn)而執(zhí)行內(nèi)核中的中斷服務(wù)程序；

以上，就是發(fā)生進(jìn)程上下文切換的常見場(chǎng)景了。

線程

在早期的操作系統(tǒng)中都是以進(jìn)程作為獨(dú)立運(yùn)行的基本單位，直到后面，計(jì)算機(jī)科學(xué)家們又提出了更小的能獨(dú)立運(yùn)行的基本單位，也就是線程。

為什么使用線程？

我們舉個(gè)例子，假設(shè)你要編寫一個(gè)視頻播放器軟件，那么該軟件功能的核心模塊有三個(gè)：

• 從視頻文件當(dāng)中讀取數(shù)據(jù)；

• 對(duì)讀取的數(shù)據(jù)進(jìn)行解壓縮；

• 把解壓縮后的視頻數(shù)據(jù)播放出來；

對(duì)于單進(jìn)程的實(shí)現(xiàn)方式，我想大家都會(huì)是以下這個(gè)方式：

對(duì)于單進(jìn)程的這種方式，存在以下問題：

• 播放出來的畫面和聲音會(huì)不連貫，因?yàn)楫?dāng) CPU 能力不夠強(qiáng)的時(shí)候，Read  的時(shí)候可能進(jìn)程就等在這了，這樣就會(huì)導(dǎo)致等半天才進(jìn)行數(shù)據(jù)解壓和播放；

• 各個(gè)函數(shù)之間不是并發(fā)執(zhí)行，影響資源的使用效率；

那改進(jìn)成多進(jìn)程的方式：

對(duì)于多進(jìn)程的這種方式，依然會(huì)存在問題：

• 進(jìn)程之間如何通信，共享數(shù)據(jù)？

• 維護(hù)進(jìn)程的系統(tǒng)開銷較大，如創(chuàng)建進(jìn)程時(shí)，分配資源、建立 PCB；終止進(jìn)程時(shí)，回收資源、撤銷 PCB；進(jìn)程切換時(shí)，保存當(dāng)前進(jìn)程的狀態(tài)信息；

那到底如何解決呢？需要有一種新的實(shí)體，滿足以下特性：

• 實(shí)體之間可以并發(fā)運(yùn)行；

• 實(shí)體之間共享相同的地址空間；

這個(gè)新的實(shí)體，就是線程( Thread )，線程之間可以并發(fā)運(yùn)行且共享相同的地址空間。

什么是線程？

線程是進(jìn)程當(dāng)中的一條執(zhí)行流程。

同一個(gè)進(jìn)程內(nèi)多個(gè)線程之間可以共享代碼段、數(shù)據(jù)段、打開的文件等資源，但每個(gè)線程都有獨(dú)立一套的寄存器和棧，這樣可以確保線程的控制流是相對(duì)獨(dú)立的。

線程的優(yōu)缺點(diǎn)？

線程的優(yōu)點(diǎn)：

• 一個(gè)進(jìn)程中可以同時(shí)存在多個(gè)線程；

• 各個(gè)線程之間可以并發(fā)執(zhí)行；

• 各個(gè)線程之間可以共享地址空間和文件等資源；

線程的缺點(diǎn)：

• 當(dāng)進(jìn)程中的一個(gè)線程奔潰時(shí)，會(huì)導(dǎo)致其所屬進(jìn)程的所有線程奔潰。

舉個(gè)例子，對(duì)于游戲的用戶設(shè)計(jì)，則不應(yīng)該使用多線程的方式，否則一個(gè)用戶掛了，會(huì)影響其他同個(gè)進(jìn)程的線程。

線程與進(jìn)程的比較

線程與進(jìn)程的比較如下：

• 進(jìn)程是資源（包括內(nèi)存、打開的文件等）分配的單位，線程是 CPU 調(diào)度的單位；

• 進(jìn)程擁有一個(gè)完整的資源平臺(tái)，而線程只獨(dú)享必不可少的資源，如寄存器和棧；

• 線程同樣具有就緒、阻塞、執(zhí)行三種基本狀態(tài)，同樣具有狀態(tài)之間的轉(zhuǎn)換關(guān)系；

• 線程能減少并發(fā)執(zhí)行的時(shí)間和空間開銷；

對(duì)于，線程相比進(jìn)程能減少開銷，體現(xiàn)在：

• 線程的創(chuàng)建時(shí)間比進(jìn)程快，因?yàn)檫M(jìn)程在創(chuàng)建的過程中，還需要資源管理信息，比如內(nèi)存管理信息、文件管理信息，而線程在創(chuàng)建的過程中，不會(huì)涉及這些資源管理信息，而是共享它們；

• 線程的終止時(shí)間比進(jìn)程快，因?yàn)榫€程釋放的資源相比進(jìn)程少很多；

• 同一個(gè)進(jìn)程內(nèi)的線程切換比進(jìn)程切換快，因?yàn)榫€程具有相同的地址空間（虛擬內(nèi)存共享），這意味著同一個(gè)進(jìn)程的線程都具有同一個(gè)頁(yè)表，那么在切換的時(shí)候不需要切換頁(yè)表。而對(duì)于進(jìn)程之間的切換，切換的時(shí)候要把頁(yè)表給切換掉，而頁(yè)表的切換過程開銷是比較大的；

• 由于同一進(jìn)程的各線程間共享內(nèi)存和文件資源，那么在線程之間數(shù)據(jù)傳遞的時(shí)候，就不需要經(jīng)過內(nèi)核了，這就使得線程之間的數(shù)據(jù)交互效率更高了；

所以，線程比進(jìn)程不管是時(shí)間效率，還是空間效率都要高。

線程的上下文切換

在前面我們知道了，線程與進(jìn)程最大的區(qū)別在于：線程是調(diào)度的基本單位，而進(jìn)程則是資源擁有的基本單位。

所以，所謂操作系統(tǒng)的任務(wù)調(diào)度，實(shí)際上的調(diào)度對(duì)象是線程，而進(jìn)程只是給線程提供了虛擬內(nèi)存、全局變量等資源。

對(duì)于線程和進(jìn)程，我們可以這么理解：

• 當(dāng)進(jìn)程只有一個(gè)線程時(shí)，可以認(rèn)為進(jìn)程就等于線程；

• 當(dāng)進(jìn)程擁有多個(gè)線程時(shí)，這些線程會(huì)共享相同的虛擬內(nèi)存和全局變量等資源，這些資源在上下文切換時(shí)是不需要修改的；

另外，線程也有自己的私有數(shù)據(jù)，比如棧和寄存器等，這些在上下文切換時(shí)也是需要保存的。

線程上下文切換的是什么？

這還得看線程是不是屬于同一個(gè)進(jìn)程：

• 當(dāng)兩個(gè)線程不是屬于同一個(gè)進(jìn)程，則切換的過程就跟進(jìn)程上下文切換一樣；

• 當(dāng)兩個(gè)線程是屬于同一個(gè)進(jìn)程，因?yàn)樘摂M內(nèi)存是共享的，所以在切換時(shí)，虛擬內(nèi)存這些資源就保持不動(dòng)，只需要切換線程的私有數(shù)據(jù)、寄存器等不共享的數(shù)據(jù)；

所以，線程的上下文切換相比進(jìn)程，開銷要小很多。

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

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

• 用戶線程（User Thread）：在用戶空間實(shí)現(xiàn)的線程，不是由內(nèi)核管理的線程，是由用戶態(tài)的線程庫(kù)來完成線程的管理；

• 內(nèi)核線程（Kernel Thread）：在內(nèi)核中實(shí)現(xiàn)的線程，是由內(nèi)核管理的線程；

• 輕量級(jí)進(jìn)程（LightWeight Process）：在內(nèi)核中來支持用戶線程；

那么，這還需要考慮一個(gè)問題，用戶線程和內(nèi)核線程的對(duì)應(yīng)關(guān)系。

首先，第一種關(guān)系是多對(duì)一的關(guān)系，也就是多個(gè)用戶線程對(duì)應(yīng)同一個(gè)內(nèi)核線程：

第二種是一對(duì)一的關(guān)系，也就是一個(gè)用戶線程對(duì)應(yīng)一個(gè)內(nèi)核線程：

第三種是多對(duì)多的關(guān)系，也就是多個(gè)用戶線程對(duì)應(yīng)到多個(gè)內(nèi)核線程：

用戶線程如何理解？存在什么優(yōu)勢(shì)和缺陷？

用戶線程是基于用戶態(tài)的線程管理庫(kù)來實(shí)現(xiàn)的，那么線程控制塊（Thread Control Block, TCB） 也是在庫(kù)里面來實(shí)現(xiàn)的，對(duì)于操作系統(tǒng)而言是看不到這個(gè) TCB 的，它只能看到整個(gè)進(jìn)程的 PCB。

所以，用戶線程的整個(gè)線程管理和調(diào)度，操作系統(tǒng)是不直接參與的，而是由用戶級(jí)線程庫(kù)函數(shù)來完成線程的管理，包括線程的創(chuàng)建、終止、同步和調(diào)度等。

用戶級(jí)線程的模型，也就類似前面提到的多對(duì)一的關(guān)系，即多個(gè)用戶線程對(duì)應(yīng)同一個(gè)內(nèi)核線程，如下圖所示：

用戶線程的優(yōu)點(diǎn)：

• 每個(gè)進(jìn)程都需要有它私有的線程控制塊（TCB）列表，用來跟蹤記錄它各個(gè)線程狀態(tài)信息（PC、棧指針、寄存器），TCB 由用戶級(jí)線程庫(kù)函數(shù)來維護(hù)，可用于不支持線程技術(shù)的操作系統(tǒng)；

• 用戶線程的切換也是由線程庫(kù)函數(shù)來完成的，無需用戶態(tài)與內(nèi)核態(tài)的切換，所以速度特別快；

用戶線程的缺點(diǎn)：

• 由于操作系統(tǒng)不參與線程的調(diào)度，如果一個(gè)線程發(fā)起了系統(tǒng)調(diào)用而阻塞，那進(jìn)程所包含的用戶線程都不能執(zhí)行了。

• 當(dāng)一個(gè)線程開始運(yùn)行后，除非它主動(dòng)地交出 CPU 的使用權(quán)，否則它所在的進(jìn)程當(dāng)中的其他線程無法運(yùn)行，因?yàn)橛脩魬B(tài)的線程沒法打斷當(dāng)前運(yùn)行中的線程，它沒有這個(gè)特權(quán)，只有操作系統(tǒng)才有，但是用戶線程不是由操作系統(tǒng)管理的。

• 由于時(shí)間片分配給進(jìn)程，故與其他進(jìn)程比，在多線程執(zhí)行時(shí)，每個(gè)線程得到的時(shí)間片較少，執(zhí)行會(huì)比較慢；

以上，就是用戶線程的優(yōu)缺點(diǎn)了。

那內(nèi)核線程如何理解？存在什么優(yōu)勢(shì)和缺陷？

內(nèi)核線程是由操作系統(tǒng)管理的，線程對(duì)應(yīng)的 TCB 自然是放在操作系統(tǒng)里的，這樣線程的創(chuàng)建、終止和管理都是由操作系統(tǒng)負(fù)責(zé)。

內(nèi)核線程的模型，也就類似前面提到的一對(duì)一的關(guān)系，即一個(gè)用戶線程對(duì)應(yīng)一個(gè)內(nèi)核線程，如下圖所示：

內(nèi)核線程的優(yōu)點(diǎn)：

• 在一個(gè)進(jìn)程當(dāng)中，如果某個(gè)內(nèi)核線程發(fā)起系統(tǒng)調(diào)用而被阻塞，并不會(huì)影響其他內(nèi)核線程的運(yùn)行；

• 分配給線程，多線程的進(jìn)程獲得更多的 CPU 運(yùn)行時(shí)間；

內(nèi)核線程的缺點(diǎn)：

• 在支持內(nèi)核線程的操作系統(tǒng)中，由內(nèi)核來維護(hù)進(jìn)程和線程的上下問信息，如 PCB 和 TCB；

• 線程的創(chuàng)建、終止和切換都是通過系統(tǒng)調(diào)用的方式來進(jìn)行，因此對(duì)于系統(tǒng)來說，系統(tǒng)開銷比較大；

以上，就是內(nèi)核線的優(yōu)缺點(diǎn)了。

最后的輕量級(jí)進(jìn)程如何理解？

輕量級(jí)進(jìn)程（Light-weight process，LWP）是內(nèi)核支持的用戶線程，一個(gè)進(jìn)程可有一個(gè)或多個(gè) LWP，每個(gè) LWP 是跟內(nèi)核線程一對(duì)一映射的，也就是 LWP 都是由一個(gè)內(nèi)核線程支持。

另外，LWP 只能由內(nèi)核管理并像普通進(jìn)程一樣被調(diào)度，Linux 內(nèi)核是支持 LWP 的典型例子。

在大多數(shù)系統(tǒng)中，LWP與普通進(jìn)程的區(qū)別也在于它只有一個(gè)最小的執(zhí)行上下文和調(diào)度程序所需的統(tǒng)計(jì)信息。一般來說，一個(gè)進(jìn)程代表程序的一個(gè)實(shí)例，而 LWP 代表程序的執(zhí)行線程，因?yàn)橐粋€(gè)執(zhí)行線程不像進(jìn)程那樣需要那么多狀態(tài)信息，所以 LWP 也不帶有這樣的信息。

在 LWP 之上也是可以使用用戶線程的，那么 LWP 與用戶線程的對(duì)應(yīng)關(guān)系就有三種：

• 1 : 1，即一個(gè) LWP 對(duì)應(yīng) 一個(gè)用戶線程；

• N : 1，即一個(gè) LWP 對(duì)應(yīng)多個(gè)用戶線程；

• N : N，即多個(gè) LMP 對(duì)應(yīng)多個(gè)用戶線程；

接下來針對(duì)上面這三種對(duì)應(yīng)關(guān)系說明它們優(yōu)缺點(diǎn)。先下圖的 LWP 模型：

1 : 1 模式

一個(gè)線程對(duì)應(yīng)到一個(gè) LWP 再對(duì)應(yīng)到一個(gè)內(nèi)核線程，如上圖的進(jìn)程 4，屬于此模型。

• 優(yōu)點(diǎn)：實(shí)現(xiàn)并行，當(dāng)一個(gè) LWP 阻塞，不會(huì)影響其他 LWP；

• 缺點(diǎn)：每一個(gè)用戶線程，就產(chǎn)生一個(gè)內(nèi)核線程，創(chuàng)建線程的開銷較大。

N : 1 模式

多個(gè)用戶線程對(duì)應(yīng)一個(gè) LWP 再對(duì)應(yīng)一個(gè)內(nèi)核線程，如上圖的進(jìn)程 2，線程管理是在用戶空間完成的，此模式中用戶的線程對(duì)操作系統(tǒng)不可見。

• 優(yōu)點(diǎn)：用戶線程要開幾個(gè)都沒問題，且上下文切換發(fā)生用戶空間，切換的效率較高；

• 缺點(diǎn)：一個(gè)用戶線程如果阻塞了，則整個(gè)進(jìn)程都將會(huì)阻塞，另外在多核 CPU  中，是沒辦法充分利用 CPU 的。

M : N 模式

根據(jù)前面的兩個(gè)模型混搭一起，就形成 M:N 模型，該模型提供了兩級(jí)控制，首先多個(gè)用戶線程對(duì)應(yīng)到多個(gè) LWP，LWP 再一一對(duì)應(yīng)到內(nèi)核線程，如上圖的進(jìn)程 3。

• 優(yōu)點(diǎn)：綜合了前兩種優(yōu)點(diǎn)，大部分的線程上下文發(fā)生在用戶空間，且多個(gè)線程又可以充分利用多核 CPU 的資源。

組合模式

如上圖的進(jìn)程 5，此進(jìn)程結(jié)合 1:1 模型和 M:N 模型。開發(fā)人員可以針對(duì)不同的應(yīng)用特點(diǎn)調(diào)節(jié)內(nèi)核線程的數(shù)目來達(dá)到物理并行性和邏輯并行性的最佳方案。

調(diào)度

進(jìn)程都希望自己能夠占用 CPU 進(jìn)行工作，那么這涉及到前面說過的進(jìn)程上下文切換。

一旦操作系統(tǒng)把進(jìn)程切換到運(yùn)行狀態(tài)，也就意味著該進(jìn)程占用著 CPU 在執(zhí)行，但是當(dāng)操作系統(tǒng)把進(jìn)程切換到其他狀態(tài)時(shí)，那就不能在 CPU 中執(zhí)行了，于是操作系統(tǒng)會(huì)選擇下一個(gè)要運(yùn)行的進(jìn)程。

選擇一個(gè)進(jìn)程運(yùn)行這一功能是在操作系統(tǒng)中完成的，通常稱為調(diào)度程序（scheduler）。

那到底什么時(shí)候調(diào)度進(jìn)程，或以什么原則來調(diào)度進(jìn)程呢？

調(diào)度時(shí)機(jī)

在進(jìn)程的生命周期中，當(dāng)進(jìn)程從一個(gè)運(yùn)行狀態(tài)到另外一狀態(tài)變化的時(shí)候，其實(shí)會(huì)觸發(fā)一次調(diào)度。

比如，以下狀態(tài)的變化都會(huì)觸發(fā)操作系統(tǒng)的調(diào)度：

• 從就緒態(tài) -> 運(yùn)行態(tài)：當(dāng)進(jìn)程被創(chuàng)建時(shí)，會(huì)進(jìn)入到就緒隊(duì)列，操作系統(tǒng)會(huì)從就緒隊(duì)列選擇一個(gè)進(jìn)程運(yùn)行；

• 從運(yùn)行態(tài) -> 阻塞態(tài)：當(dāng)進(jìn)程發(fā)生 I/O 事件而阻塞時(shí)，操作系統(tǒng)必須另外一個(gè)進(jìn)程運(yùn)行；

• 從運(yùn)行態(tài) -> 結(jié)束態(tài)：當(dāng)進(jìn)程退出結(jié)束后，操作系統(tǒng)得從就緒隊(duì)列選擇另外一個(gè)進(jìn)程運(yùn)行；

因?yàn)椋@些狀態(tài)變化的時(shí)候，操作系統(tǒng)需要考慮是否要讓新的進(jìn)程給 CPU 運(yùn)行，或者是否讓當(dāng)前進(jìn)程從 CPU 上退出來而換另一個(gè)進(jìn)程運(yùn)行。

另外，如果硬件時(shí)鐘提供某個(gè)頻率的周期性中斷，那么可以根據(jù)如何處理時(shí)鐘中斷
把調(diào)度算法分為兩類：

• 非搶占式調(diào)度算法挑選一個(gè)進(jìn)程，然后讓該進(jìn)程運(yùn)行直到被阻塞，或者直到該進(jìn)程退出，才會(huì)調(diào)用另外一個(gè)進(jìn)程，也就是說不會(huì)理時(shí)鐘中斷這個(gè)事情。

• 搶占式調(diào)度算法挑選一個(gè)進(jìn)程，然后讓該進(jìn)程只運(yùn)行某段時(shí)間，如果在該時(shí)段結(jié)束時(shí)，該進(jìn)程仍然在運(yùn)行時(shí)，則會(huì)把它掛起，接著調(diào)度程序從就緒隊(duì)列挑選另外一個(gè)進(jìn)程。這種搶占式調(diào)度處理，需要在時(shí)間間隔的末端發(fā)生時(shí)鐘中斷，以便把 CPU 控制返回給調(diào)度程序進(jìn)行調(diào)度，也就是常說的時(shí)間片機(jī)制。

調(diào)度原則

原則一：如果運(yùn)行的程序，發(fā)生了 I/O 事件的請(qǐng)求，那 CPU 使用率必然會(huì)很低，因?yàn)榇藭r(shí)進(jìn)程在阻塞等待硬盤的數(shù)據(jù)返回。這樣的過程，勢(shì)必會(huì)造成 CPU 突然的空閑。所以，為了提高 CPU 利用率，在這種發(fā)送 I/O 事件致使 CPU 空閑的情況下，調(diào)度程序需要從就緒隊(duì)列中選擇一個(gè)進(jìn)程來運(yùn)行。

原則二：有的程序執(zhí)行某個(gè)任務(wù)花費(fèi)的時(shí)間會(huì)比較長(zhǎng)，如果這個(gè)程序一直占用著 CPU，會(huì)造成系統(tǒng)吞吐量（CPU 在單位時(shí)間內(nèi)完成的進(jìn)程數(shù)量）的降低。所以，要提高系統(tǒng)的吞吐率，調(diào)度程序要權(quán)衡長(zhǎng)任務(wù)和短任務(wù)進(jìn)程的運(yùn)行完成數(shù)量。

原則三：從進(jìn)程開始到結(jié)束的過程中，實(shí)際上是包含兩個(gè)時(shí)間，分別是進(jìn)程運(yùn)行時(shí)間和進(jìn)程等待時(shí)間，這兩個(gè)時(shí)間總和就稱為周轉(zhuǎn)時(shí)間。進(jìn)程的周轉(zhuǎn)時(shí)間越小越好，如果進(jìn)程的等待時(shí)間很長(zhǎng)而運(yùn)行時(shí)間很短，那周轉(zhuǎn)時(shí)間就很長(zhǎng)，這不是我們所期望的，調(diào)度程序應(yīng)該避免這種情況發(fā)生。

原則四：處于就緒隊(duì)列的進(jìn)程，也不能等太久，當(dāng)然希望這個(gè)等待的時(shí)間越短越好，這樣可以使得進(jìn)程更快的在 CPU 中執(zhí)行。所以，就緒隊(duì)列中進(jìn)程的等待時(shí)間也是調(diào)度程序所需要考慮的原則。

原則五：對(duì)于鼠標(biāo)、鍵盤這種交互式比較強(qiáng)的應(yīng)用，我們當(dāng)然希望它的響應(yīng)時(shí)間越快越好，否則就會(huì)影響用戶體驗(yàn)了。所以，對(duì)于交互式比較強(qiáng)的應(yīng)用，響應(yīng)時(shí)間也是調(diào)度程序需要考慮的原則。

針對(duì)上面的五種調(diào)度原則，總結(jié)成如下：

• CPU 利用率：調(diào)度程序應(yīng)確保 CPU 是始終匆忙的狀態(tài)，這可提高 CPU 的利用率；

• 系統(tǒng)吞吐量：吞吐量表示的是單位時(shí)間內(nèi) CPU 完成進(jìn)程的數(shù)量，長(zhǎng)作業(yè)的進(jìn)程會(huì)占用較長(zhǎng)的 CPU 資源，因此會(huì)降低吞吐量，相反，短作業(yè)的進(jìn)程會(huì)提升系統(tǒng)吞吐量；

• 周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間是進(jìn)程運(yùn)行和阻塞時(shí)間總和，一個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間越小越好；

• 等待時(shí)間：這個(gè)等待時(shí)間不是阻塞狀態(tài)的時(shí)間，而是進(jìn)程處于就緒隊(duì)列的時(shí)間，等待的時(shí)間越長(zhǎng)，用戶越不滿意；

• 響應(yīng)時(shí)間：用戶提交請(qǐng)求到系統(tǒng)第一次產(chǎn)生響應(yīng)所花費(fèi)的時(shí)間，在交互式系統(tǒng)中，響應(yīng)時(shí)間是衡量調(diào)度算法好壞的主要標(biāo)準(zhǔn)。

說白了，這么多調(diào)度原則，目的就是要使得進(jìn)程要「快」。

調(diào)度算法

不同的調(diào)度算法適用的場(chǎng)景也是不同的。

接下來，說說在單核 CPU 系統(tǒng)中常見的調(diào)度算法。

01 先來先服務(wù)調(diào)度算法

最簡(jiǎn)單的一個(gè)調(diào)度算法，就是非搶占式的先來先服務(wù)（First Come First Severd, FCFS）算法了。

顧名思義，先來后到，每次從就緒隊(duì)列選擇最先進(jìn)入隊(duì)列的進(jìn)程，然后一直運(yùn)行，直到進(jìn)程退出或被阻塞，才會(huì)繼續(xù)從隊(duì)列中選擇第一個(gè)進(jìn)程接著運(yùn)行。

這似乎很公平，但是當(dāng)一個(gè)長(zhǎng)作業(yè)先運(yùn)行了，那么后面的短作業(yè)等待的時(shí)間就會(huì)很長(zhǎng)，不利于短作業(yè)。

FCFS 對(duì)長(zhǎng)作業(yè)有利，適用于 CPU 繁忙型作業(yè)的系統(tǒng)，而不適用于 I/O 繁忙型作業(yè)的系統(tǒng)。

02 最短作業(yè)優(yōu)先調(diào)度算法

最短作業(yè)優(yōu)先（Shortest Job First, SJF）調(diào)度算法同樣也是顧名思義，它會(huì)優(yōu)先選擇運(yùn)行時(shí)間最短的進(jìn)程來運(yùn)行，這有助于提高系統(tǒng)的吞吐量。

這顯然對(duì)長(zhǎng)作業(yè)不利，很容易造成一種極端現(xiàn)象。

比如，一個(gè)長(zhǎng)作業(yè)在就緒隊(duì)列等待運(yùn)行，而這個(gè)就緒隊(duì)列有非常多的短作業(yè)，那么就會(huì)使得長(zhǎng)作業(yè)不斷的往后推，周轉(zhuǎn)時(shí)間變長(zhǎng)，致使長(zhǎng)作業(yè)長(zhǎng)期不會(huì)被運(yùn)行。

03 高響應(yīng)比優(yōu)先調(diào)度算法

前面的「先來先服務(wù)調(diào)度算法」和「最短作業(yè)優(yōu)先調(diào)度算法」都沒有很好的權(quán)衡短作業(yè)和長(zhǎng)作業(yè)。

那么，高響應(yīng)比優(yōu)先 （Highest Response Ratio Next, HRRN）調(diào)度算法主要是權(quán)衡了短作業(yè)和長(zhǎng)作業(yè)。

每次進(jìn)行進(jìn)程調(diào)度時(shí)，先計(jì)算「響應(yīng)比優(yōu)先級(jí)」，然后把「響應(yīng)比優(yōu)先級(jí)」最高的進(jìn)程投入運(yùn)行，「響應(yīng)比優(yōu)先級(jí)」的計(jì)算公式：

從上面的公式，可以發(fā)現(xiàn)：

• 如果兩個(gè)進(jìn)程的「等待時(shí)間」相同時(shí)，「要求的服務(wù)時(shí)間」越短，「響應(yīng)比」就越高，這樣短作業(yè)的進(jìn)程容易被選中運(yùn)行；

• 如果兩個(gè)進(jìn)程「要求的服務(wù)時(shí)間」相同時(shí)，「等待時(shí)間」越長(zhǎng)，「響應(yīng)比」就越高，這就兼顧到了長(zhǎng)作業(yè)進(jìn)程，因?yàn)檫M(jìn)程的響應(yīng)比可以隨時(shí)間等待的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其響應(yīng)比便可以升到很高，從而獲得運(yùn)行的機(jī)會(huì)；

04 時(shí)間片輪轉(zhuǎn)調(diào)度算法

最古老、最簡(jiǎn)單、最公平且使用最廣的算法就是時(shí)間片輪轉(zhuǎn)（Round Robin, RR）調(diào)度算法。
。

每個(gè)進(jìn)程被分配一個(gè)時(shí)間段，稱為時(shí)間片（Quantum），即允許該進(jìn)程在該時(shí)間段中運(yùn)行。

• 如果時(shí)間片用完，進(jìn)程還在運(yùn)行，那么將會(huì)把此進(jìn)程從 CPU 釋放出來，并把 CPU 分配另外一個(gè)進(jìn)程；

• 如果該進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束，則 CPU 立即進(jìn)行切換；

另外，時(shí)間片的長(zhǎng)度就是一個(gè)很關(guān)鍵的點(diǎn)：

• 如果時(shí)間片設(shè)得太短會(huì)導(dǎo)致過多的進(jìn)程上下文切換，降低了 CPU 效率；

• 如果設(shè)得太長(zhǎng)又可能引起對(duì)短作業(yè)進(jìn)程的響應(yīng)時(shí)間變長(zhǎng)。將

通常時(shí)間片設(shè)為 20ms~50ms 通常是一個(gè)比較合理的折中值。

05 最高優(yōu)先級(jí)調(diào)度算法

前面的「時(shí)間片輪轉(zhuǎn)算法」做了個(gè)假設(shè)，即讓所有的進(jìn)程同等重要，也不偏袒誰，大家的運(yùn)行時(shí)間都一樣。

但是，對(duì)于多用戶計(jì)算機(jī)系統(tǒng)就有不同的看法了，它們希望調(diào)度是有優(yōu)先級(jí)的，即希望調(diào)度程序能從就緒隊(duì)列中選擇最高優(yōu)先級(jí)的進(jìn)程進(jìn)行運(yùn)行，這稱為最高優(yōu)先級(jí)（Highest Priority First，HPF）調(diào)度算法。

進(jìn)程的優(yōu)先級(jí)可以分為，靜態(tài)優(yōu)先級(jí)或動(dòng)態(tài)優(yōu)先級(jí)：

• 靜態(tài)優(yōu)先級(jí)：創(chuàng)建進(jìn)程時(shí)候，就已經(jīng)確定了優(yōu)先級(jí)了，然后整個(gè)運(yùn)行時(shí)間優(yōu)先級(jí)都不會(huì)變化；

• 動(dòng)態(tài)優(yōu)先級(jí)：根據(jù)進(jìn)程的動(dòng)態(tài)變化調(diào)整優(yōu)先級(jí)，比如如果進(jìn)程運(yùn)行時(shí)間增加，則降低其優(yōu)先級(jí)，如果進(jìn)程等待時(shí)間（就緒隊(duì)列的等待時(shí)間）增加，則升高其優(yōu)先級(jí)，也就是隨著時(shí)間的推移增加等待進(jìn)程的優(yōu)先級(jí)。

該算法也有兩種處理優(yōu)先級(jí)高的方法，非搶占式和搶占式：

• 非搶占式：當(dāng)就緒隊(duì)列中出現(xiàn)優(yōu)先級(jí)高的進(jìn)程，運(yùn)行完當(dāng)前進(jìn)程，再選擇優(yōu)先級(jí)高的進(jìn)程。

• 搶占式：當(dāng)就緒隊(duì)列中出現(xiàn)優(yōu)先級(jí)高的進(jìn)程，當(dāng)前進(jìn)程掛起，調(diào)度優(yōu)先級(jí)高的進(jìn)程運(yùn)行。

但是依然有缺點(diǎn)，可能會(huì)導(dǎo)致低優(yōu)先級(jí)的進(jìn)程永遠(yuǎn)不會(huì)運(yùn)行。

06 多級(jí)反饋隊(duì)列調(diào)度算法

多級(jí)反饋隊(duì)列（Multilevel Feedback Queue）調(diào)度算法是「時(shí)間片輪轉(zhuǎn)算法」和「最高優(yōu)先級(jí)算法」的綜合和發(fā)展。

顧名思義：

• 「多級(jí)」表示有多個(gè)隊(duì)列，每個(gè)隊(duì)列優(yōu)先級(jí)從高到低，同時(shí)優(yōu)先級(jí)越高時(shí)間片越短。

• 「反饋」表示如果有新的進(jìn)程加入優(yōu)先級(jí)高的隊(duì)列時(shí)，立刻停止當(dāng)前正在運(yùn)行的進(jìn)程，轉(zhuǎn)而去運(yùn)行優(yōu)先級(jí)高的隊(duì)列；

來看看，它是如何工作的：

• 設(shè)置了多個(gè)隊(duì)列，賦予每個(gè)隊(duì)列不同的優(yōu)先級(jí)，每個(gè)隊(duì)列優(yōu)先級(jí)從高到低，同時(shí)優(yōu)先級(jí)越高時(shí)間片越短；

• 新的進(jìn)程會(huì)被放入到第一級(jí)隊(duì)列的末尾，按先來先服務(wù)的原則排隊(duì)等待被調(diào)度，如果在第一級(jí)隊(duì)列規(guī)定的時(shí)間片沒運(yùn)行完成，則將其轉(zhuǎn)入到第二級(jí)隊(duì)列的末尾，以此類推，直至完成；

• 當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程運(yùn)行。如果進(jìn)程運(yùn)行時(shí)，有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則停止當(dāng)前運(yùn)行的進(jìn)程并將其移入到原隊(duì)列末尾，接著讓較高優(yōu)先級(jí)的進(jìn)程運(yùn)行；

可以發(fā)現(xiàn)，對(duì)于短作業(yè)可能可以在第一級(jí)隊(duì)列很快被處理完。對(duì)于長(zhǎng)作業(yè)，如果在第一級(jí)隊(duì)列處理不完，可以移入下次隊(duì)列等待被執(zhí)行，雖然等待的時(shí)間變長(zhǎng)了，但是運(yùn)行時(shí)間也會(huì)更長(zhǎng)了，所以該算法很好的兼顧了長(zhǎng)短作業(yè)，同時(shí)有較好的響應(yīng)時(shí)間。

看的迷迷糊糊？那我拿去銀行辦業(yè)務(wù)的例子，把上面的調(diào)度算法串起來，你還不懂，你錘我！

辦理業(yè)務(wù)的客戶相當(dāng)于進(jìn)程，銀行窗口工作人員相當(dāng)于 CPU。

現(xiàn)在，假設(shè)這個(gè)銀行只有一個(gè)窗口（單核 CPU ），那么工作人員一次只能處理一個(gè)業(yè)務(wù)。

那么最簡(jiǎn)單的處理方式，就是先來的先處理，后面來的就乖乖排隊(duì)，這就是先來先服務(wù)（FCFS）調(diào)度算法。但是萬一先來的這位老哥是來貸款的，這一談就好幾個(gè)小時(shí)，一直占用著窗口，這樣后面的人只能干等，或許后面的人只是想簡(jiǎn)單的取個(gè)錢，幾分鐘就能搞定，卻因?yàn)榍懊胬细甾k長(zhǎng)業(yè)務(wù)而要等幾個(gè)小時(shí)，你說氣不氣人？

有客戶抱怨了，那我們就要改進(jìn)，我們干脆優(yōu)先給那些幾分鐘就能搞定的人辦理業(yè)務(wù)，這就是短作業(yè)優(yōu)先（SJF）調(diào)度算法。聽起來不錯(cuò)，但是依然還是有個(gè)極端情況，萬一辦理短業(yè)務(wù)的人非常的多，這會(huì)導(dǎo)致長(zhǎng)業(yè)務(wù)的人一直得不到服務(wù)，萬一這個(gè)長(zhǎng)業(yè)務(wù)是個(gè)大客戶，那不就撿了芝麻丟了西瓜

那就公平起見，現(xiàn)在窗口工作人員規(guī)定，每個(gè)人我只處理 10 分鐘。如果 10 分鐘之內(nèi)處理完，就馬上換下一個(gè)人。如果沒處理完，依然換下一個(gè)人，但是客戶自己得記住辦理到哪個(gè)步驟了。這個(gè)也就是時(shí)間片輪轉(zhuǎn)（RR）調(diào)度算法。但是如果時(shí)間片設(shè)置過短，那么就會(huì)造成大量的上下文切換，增大了系統(tǒng)開銷。如果時(shí)間片過長(zhǎng)，相當(dāng)于退化成退化成 FCFS 算法了。

既然公平也可能存在問題，那銀行就對(duì)客戶分等級(jí)，分為普通客戶、VIP 客戶、SVIP 客戶。只要高優(yōu)先級(jí)的客戶一來，就第一時(shí)間處理這個(gè)客戶，這就是最高優(yōu)先級(jí)（HPF）調(diào)度算法。但依然也會(huì)有極端的問題，萬一當(dāng)天來的全是高級(jí)客戶，那普通客戶不是沒有被服務(wù)的機(jī)會(huì)，不把普通客戶當(dāng)人是嗎？那我們把優(yōu)先級(jí)改成動(dòng)態(tài)的，如果客戶辦理業(yè)務(wù)時(shí)間增加，則降低其優(yōu)先級(jí)，如果客戶等待時(shí)間增加，則升高其優(yōu)先級(jí)。

那有沒有兼顧到公平和效率的方式呢？這里介紹一種算法，考慮的還算充分的，多級(jí)反饋隊(duì)列（MFQ）調(diào)度算法，它是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)算法的綜合和發(fā)展。它的工作方式：

• 銀行設(shè)置了多個(gè)排隊(duì)（就緒）隊(duì)列，每個(gè)隊(duì)列都有不同的優(yōu)先級(jí)，各個(gè)隊(duì)列優(yōu)先級(jí)從高到低，同時(shí)每個(gè)隊(duì)列執(zhí)行時(shí)間片的長(zhǎng)度也不同，優(yōu)先級(jí)越高的時(shí)間片越短。

• 新客戶（進(jìn)程）來了，先進(jìn)入第一級(jí)隊(duì)列的末尾，按先來先服務(wù)原則排隊(duì)等待被叫號(hào)（運(yùn)行）。如果時(shí)間片用完客戶的業(yè)務(wù)還沒辦理完成，則讓客戶進(jìn)入到下一級(jí)隊(duì)列的末尾，以此類推，直至客戶業(yè)務(wù)辦理完成。

• 當(dāng)?shù)谝患?jí)隊(duì)列沒人排隊(duì)時(shí)，就會(huì)叫號(hào)二級(jí)隊(duì)列的客戶。如果客戶辦理業(yè)務(wù)過程中，有新的客戶加入到較高優(yōu)先級(jí)的隊(duì)列，那么此時(shí)辦理中的客戶需要停止辦理，回到原隊(duì)列的末尾等待再次叫號(hào)，因?yàn)橐汛翱谧尳o剛進(jìn)入較高優(yōu)先級(jí)隊(duì)列的客戶。

可以發(fā)現(xiàn)，對(duì)于要辦理短業(yè)務(wù)的客戶來說，可以很快的輪到并解決。對(duì)于要辦理長(zhǎng)業(yè)務(wù)的客戶，一下子解決不了，就可以放到下一個(gè)隊(duì)列，雖然等待的時(shí)間稍微變長(zhǎng)了，但是輪到自己的辦理時(shí)間也變長(zhǎng)了，也可以接受，不會(huì)造成極端的現(xiàn)象，可以說是綜合上面幾種算法的優(yōu)點(diǎn)。