1. 基本概念

競爭性: 系統(tǒng)進(jìn)程數(shù)目眾多，而CPU資源只有少量，甚至1個(gè)，所以進(jìn)程之間是具有競爭屬性的。為了高效完成任務(wù)，更合理競爭相關(guān)資源，便具有了優(yōu)先級(jí)

從上一張進(jìn)程優(yōu)先級(jí)我們可以知道，進(jìn)程之間是存在競爭關(guān)系的，并且我們要明白一點(diǎn)就是進(jìn)程在運(yùn)行的時(shí)候，放在CPU中，不是說必須要把代碼跑完后才會(huì)從CPU下來。在現(xiàn)代的操作系統(tǒng)，都是基于時(shí)間片進(jìn)行輪轉(zhuǎn)的。

獨(dú)立性: 多進(jìn)程運(yùn)行，需要獨(dú)享各種資源，多進(jìn)程運(yùn)行期間互不干擾

我們電腦上可以打開微信，也可以打開qq，也可以打開CSDN，這一個(gè)個(gè)都都是進(jìn)程，但是我們?cè)谑褂靡粋€(gè)進(jìn)程的時(shí)候都是不會(huì)影響到其他的進(jìn)程。

并行: 多個(gè)進(jìn)程在多個(gè)CPU下分別，同時(shí)進(jìn)行運(yùn)行，這稱之為并行

一般情況下，我們的電腦都是只有一個(gè)CPU的，一個(gè)CPU維護(hù)一個(gè)運(yùn)行隊(duì)列，如果有多個(gè)CPU的話就會(huì)有多個(gè)運(yùn)行隊(duì)列，所以如有多個(gè)CPU那么同一時(shí)間段就可以實(shí)現(xiàn)每個(gè)CPU都運(yùn)行一個(gè)進(jìn)程。

并發(fā): 多個(gè)進(jìn)程在一個(gè)CPU下采用進(jìn)程切換的方式，在一段時(shí)間之內(nèi)，讓多個(gè)進(jìn)程都得以推進(jìn)，稱之為并發(fā)

為什么我們的電腦只有一個(gè)CPU但是可以同時(shí)運(yùn)行微信，qq，CSCN呢？那是因?yàn)镃PU是通過時(shí)間片進(jìn)行輪詢運(yùn)行在運(yùn)行隊(duì)列的進(jìn)程的，只要速度夠快我們?nèi)耸欠从巢贿^來一個(gè)時(shí)間段只運(yùn)行一個(gè)進(jìn)程的。就好比之前的老電影都是一張一張的圖片進(jìn)行快速的播放來達(dá)到動(dòng)態(tài)的效果是一樣意思。

2. 進(jìn)程切換

我們?cè)谥v解進(jìn)程狀態(tài)的時(shí)候，講過了進(jìn)程在運(yùn)行的時(shí)候其實(shí)本質(zhì)是放在了CPU運(yùn)行隊(duì)列中，基于時(shí)間片輪轉(zhuǎn)發(fā)方式進(jìn)行占用CPU的資源，從而實(shí)現(xiàn)了多個(gè)進(jìn)程同時(shí)運(yùn)行的現(xiàn)象。而基于運(yùn)行隊(duì)列進(jìn)行切換輪詢式的享受CPU資源，這個(gè)輪詢的方式就叫做式進(jìn)程切換的過程。

而CPU中其實(shí)是由大量的寄存器的，其中我們所了解的一個(gè)寄存器eip俗稱pc指針是我們之前有接觸過的，pc指針的作用就是記錄當(dāng)前執(zhí)行代碼的下一個(gè)需要執(zhí)行的代碼的位置。所以當(dāng)一個(gè)進(jìn)程在CPU中運(yùn)行的時(shí)候，會(huì)產(chǎn)生大量的臨時(shí)數(shù)據(jù)，而這些臨時(shí)數(shù)據(jù)是存放在寄存器當(dāng)中的。

那我們就會(huì)有一個(gè)疑問了，既然進(jìn)程是基于運(yùn)行隊(duì)列時(shí)間片輪詢方式進(jìn)行切換的，那么CPU是怎么知道切換后的進(jìn)程再次來到的時(shí)候上一次運(yùn)行到那里了呢？CPU又是怎么接著根據(jù)這個(gè)進(jìn)程上一次運(yùn)行的到的位置接著運(yùn)行呢？所以當(dāng)一個(gè)進(jìn)程運(yùn)行的時(shí)間片到了的時(shí)候，CPU因該將改進(jìn)程運(yùn)行后的信息進(jìn)行記錄起來，等到這個(gè)進(jìn)程下一次再來的時(shí)候接著運(yùn)行，而這些信息就是保存在寄存器里面的。但是這些信息最終不是放在寄存器中的，而是將信息重新放到進(jìn)程的PCB中（這里我們就簡單的理解是放到PCB中的，其實(shí)是更復(fù)雜的），等到下次再到CPU中運(yùn)行的時(shí)候重新將數(shù)據(jù)個(gè)CPU，這個(gè)時(shí)候CPU就知道那些運(yùn)行了，那些沒有運(yùn)行，而這個(gè)信息叫做進(jìn)程的硬件上下文

• 上面的保存硬件上下文的操作叫做保護(hù)上下文。
• 當(dāng)一個(gè)進(jìn)程第一次被運(yùn)行那就正常執(zhí)行，如果不是那么進(jìn)程放到CPU中運(yùn)行就得先將曾經(jīng)保存的硬件上下文數(shù)據(jù)進(jìn)行恢復(fù)

這里我們要明白的是：

1. CPU內(nèi)的寄存器只有一套，但是寄存器內(nèi)保存的數(shù)據(jù)可以有多套。
2. 雖然寄存器數(shù)據(jù)是放在一個(gè)共享的CPU設(shè)備里面呢，但是所有的數(shù)據(jù)其實(shí)都是被進(jìn)程私有的。

也就是說，雖然我們的寄存器只有一套，但是只要進(jìn)程來了，那么此時(shí)CPU中的寄存器存放的就是該進(jìn)程的所數(shù)據(jù)，只要它走了，另一個(gè)進(jìn)程來了，那么保存的就是該進(jìn)程的數(shù)據(jù)。這樣就體現(xiàn)出來進(jìn)程的獨(dú)立性。

3. 進(jìn)程調(diào)度

Linux下實(shí)現(xiàn)進(jìn)程調(diào)度的算法，是需要考慮優(yōu)先級(jí)，饑餓問題，以及效率問題的。

之前我們只是簡單的畫出了進(jìn)程調(diào)度的方式——運(yùn)行隊(duì)列。

現(xiàn)在我們來詳細(xì)的解剖一下，這是一張運(yùn)行隊(duì)列中的詳細(xì)成員：

上面大部分的屬性現(xiàn)階段都是不要太關(guān)系的，我們主要關(guān)系的是上面話紅色框框的屬性字段，和畫藍(lán)色框框的屬性字段。

3.1運(yùn)行隊(duì)列實(shí)現(xiàn)優(yōu)先級(jí)設(shè)計(jì)

在Linux下是通過queue[140]這個(gè)數(shù)組來控制優(yōu)先級(jí)的，這個(gè)數(shù)組的下標(biāo)就對(duì)應(yīng)著優(yōu)先級(jí)。

前面我們學(xué)習(xí)進(jìn)程優(yōu)先級(jí)的時(shí)候，我們說過了進(jìn)程的優(yōu)先級(jí)范圍是[60,99]的一共有40個(gè)有限等級(jí)。那為什么這里控制優(yōu)先級(jí)的數(shù)組是140呢？

首先這里的話我們只關(guān)系100 ~ 139,這部分叫做是普通優(yōu)先級(jí)，100-139剛好對(duì)應(yīng)著我們之前學(xué)習(xí)的進(jìn)程的40個(gè)優(yōu)先級(jí)。所以100對(duì)應(yīng)著就是我們進(jìn)程優(yōu)先級(jí)的60，139就對(duì)應(yīng)著99，剩下的0~99的部分稱之為實(shí)時(shí)優(yōu)先級(jí)

• 分時(shí)操作系統(tǒng)必須以時(shí)間片為周期調(diào)度不同的進(jìn)程，是為了確保公平，避免進(jìn)程饑餓，比如現(xiàn)在的互聯(lián)網(wǎng)，在互聯(lián)網(wǎng)的視角中，所有用戶都是公平的，不能因?yàn)檎l的優(yōu)先級(jí)高就僅服務(wù)誰，所有用戶的優(yōu)先級(jí)都差不太多，不會(huì)出現(xiàn)誰的優(yōu)先級(jí)非常高的情況。
• 還有另外一種為實(shí)時(shí)操作系統(tǒng)則相反，在運(yùn)行某個(gè)進(jìn)程時(shí)，必須跑完，嚴(yán)格按照隊(duì)列先后順序進(jìn)行，如果有更高優(yōu)先級(jí)的進(jìn)程，允許插隊(duì)，即實(shí)時(shí)操作系統(tǒng)必須對(duì)用戶有高響應(yīng)這一特性，比如車載系統(tǒng)，絕對(duì)不能使用基于時(shí)間片輪轉(zhuǎn)的分時(shí)操作系統(tǒng)，而必須采用實(shí)時(shí)操作系統(tǒng)，剎車的指令優(yōu)先級(jí)非常高，在用戶需要?jiǎng)x車時(shí)他不會(huì)考慮音樂播放器進(jìn)程會(huì)不會(huì)饑餓。
• 所以我們必須保證一些進(jìn)程實(shí)時(shí)盡快的被處理，所以也就有了實(shí)時(shí)優(yōu)先級(jí)的概念，而0~99這些優(yōu)先級(jí)就是為了這一部分而準(zhǔn)備的。

而這個(gè)的原型其實(shí)是task_struct *queue[140]是一個(gè)指針數(shù)組，里面存放是處于同一優(yōu)先級(jí)的進(jìn)程的隊(duì)列。所以就可以根據(jù)優(yōu)先級(jí)插入對(duì)應(yīng)的優(yōu)先級(jí)隊(duì)列中了。

通過上述我們可以得到40個(gè)優(yōu)先級(jí)隊(duì)列，那么拿到CPU運(yùn)行的時(shí)候都是按照著40個(gè)優(yōu)先級(jí)隊(duì)列依次的遍歷進(jìn)行調(diào)度嗎？拿到要遍歷40次嗎，因?yàn)橹?0個(gè)隊(duì)列中大部分情況是不會(huì)每個(gè)都會(huì)有的，所以這必然會(huì)有不必要的操作，也會(huì)影響一點(diǎn)效率。

3.2 處理效率問題

所以為了防止把把40個(gè)隊(duì)列中都進(jìn)行遍歷一次，在運(yùn)行隊(duì)列中的屬性中有一個(gè)屬性int bitmap[5]，這是一個(gè)位圖。所以在linux下其實(shí)時(shí)使用位圖的方式來確定那些優(yōu)先級(jí)里面是由進(jìn)程在排隊(duì)的。

int bitmap[5]有5個(gè)int類型的空間，也就是32 * 5 = 160個(gè)bit位，也就可以表示160個(gè)優(yōu)先級(jí)了。所以bit位的位置就表示哪一個(gè)隊(duì)列，哪一個(gè)優(yōu)先級(jí)，bit位的內(nèi)容就表示隊(duì)列的內(nèi)容。即1就表示有隊(duì)列，0就表示沒有隊(duì)列。

所以我們檢測隊(duì)列中是否有進(jìn)程，就是檢測位圖中的bit位是否位1。

而具體檢測的過程就是先對(duì)int bitmap[5]中這5個(gè)元素通過int整形的方式來進(jìn)行位位操作，一旦與一個(gè)整形進(jìn)行位操作（比如用bitmap[0] & 0xFFFFFFF == 0，如果等于0就說明此時(shí)第一個(gè)整形位中是沒有隊(duì)列的，那么就去和第二個(gè)整形進(jìn)行對(duì)比，一次類推）。而這種算法接近O(1)的算法了。

3.3 活動(dòng)隊(duì)列與過期隊(duì)列

像上述的隊(duì)列中，如果優(yōu)先級(jí)更高的的隊(duì)列中一直有進(jìn)程進(jìn)行插入的話，那么那些處于優(yōu)先級(jí)比較低的進(jìn)程就可能長時(shí)間的得不到CPU的調(diào)度，甚至是可能優(yōu)先級(jí)特別低的進(jìn)程將一直得不到調(diào)度，那么就會(huì)出現(xiàn)我們打開程序會(huì)出現(xiàn)一直打不開的情況，甚至是打都打不開。

所以Linux的設(shè)計(jì)者非常的聰明，他在原理的基礎(chǔ)上（對(duì)應(yīng)紅色的框框）在次創(chuàng)建了一份同樣的結(jié)構(gòu)（對(duì)應(yīng)著藍(lán)色框框）所以說活動(dòng)隊(duì)列和過期隊(duì)列是完全相同的一個(gè)結(jié)構(gòu)，我們其實(shí)可以用一個(gè)結(jié)構(gòu)體進(jìn)行維護(hù)。

struct q
{int nr_active;bitmap[5];task_struct queue[140];
}然后過期隊(duì)列和活動(dòng)隊(duì)列就是使用一下這種結(jié)構(gòu)來表示
struct q array[2]

3.4 如何解決饑餓問題

有了活動(dòng)隊(duì)列和過期隊(duì)列后，就有效的解決了上述的問題。

當(dāng)CPU在執(zhí)行活動(dòng)隊(duì)列中的進(jìn)程的時(shí)候，后來的進(jìn)程無論讓的優(yōu)先級(jí)有多高，他都不會(huì)在添加到后動(dòng)隊(duì)列中取了，而是添加到過期隊(duì)列中去，并且一旦在活動(dòng)隊(duì)列中的進(jìn)程在本才的時(shí)間片結(jié)束后也不會(huì)再次添加到當(dāng)前的活動(dòng)隊(duì)列中去了，而是同樣的添加到過期隊(duì)列中去了。一旦活動(dòng)隊(duì)列中的進(jìn)程都完成了后，這個(gè)時(shí)候我們的過期隊(duì)列就變成了活動(dòng)隊(duì)列，活動(dòng)隊(duì)列就變成了過期隊(duì)列。

3.5 active指針和expired指針

active指針永遠(yuǎn)指向活動(dòng)隊(duì)列，expired指針永遠(yuǎn)指向過期隊(duì)列可是活動(dòng)隊(duì)列上的進(jìn)程會(huì)越來越少，過期隊(duì)列上的進(jìn)程會(huì)越來越多，因?yàn)檫M(jìn)程時(shí)間片到期時(shí)一直都存在的。沒關(guān)系，在合適的時(shí)候，只要能夠交換active指針和expired指針的內(nèi)容，就相當(dāng)于有具有了一批新的活動(dòng)進(jìn)程！

一開始struct q* active = &array[0], struct q* expried= &array[1]。

一旦檢測到活動(dòng)隊(duì)列中中沒有進(jìn)程了，操作系統(tǒng)就會(huì)執(zhí)行一個(gè)操作swap(&active, &expried)，進(jìn)而完成了活動(dòng)隊(duì)列和過期隊(duì)列的交換。