?

??樊梓慕：個(gè)人主頁(yè)

???個(gè)人專欄：《C語(yǔ)言》《數(shù)據(jù)結(jié)構(gòu)》《藍(lán)橋杯試題》《LeetCode刷題筆記》《實(shí)訓(xùn)項(xiàng)目》《C++》《Linux》

??每一個(gè)不曾起舞的日子，都是對(duì)生命的辜負(fù)

目錄

前言

1.進(jìn)程切換

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

2.1Linux系統(tǒng)的進(jìn)程調(diào)度算法如何實(shí)現(xiàn)兼顧進(jìn)程優(yōu)先級(jí)的設(shè)計(jì)

2.2Linux系統(tǒng)的進(jìn)程調(diào)度算法如何實(shí)現(xiàn)兼顧效率的設(shè)計(jì)

2.3nr_active

2.4Linux系統(tǒng)的進(jìn)程調(diào)度算法如何實(shí)現(xiàn)兼顧進(jìn)程饑餓的設(shè)計(jì)

2.4.1理論上講解

2.4.2如何實(shí)現(xiàn)的？

前言

上篇文章我們最后提到了進(jìn)程的并發(fā)：多個(gè)進(jìn)程在一個(gè)CPU下采用進(jìn)程切換的方式，在一段時(shí)間之內(nèi)，讓多個(gè)進(jìn)程都得以推進(jìn)，稱之為并發(fā)。

那么Linux是如何完成進(jìn)程的調(diào)度與切換的呢？

本篇文章博主會(huì)與大家共同學(xué)習(xí)Linux下進(jìn)程的調(diào)度與切換。

?歡迎大家??收藏??以便未來(lái)做題時(shí)可以快速找到思路，巧妙的方法可以事半功倍。?

=========================================================================文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-762130.html

GITEE相關(guān)代碼：??fanfei_c的倉(cāng)庫(kù)??

=========================================================================

1.進(jìn)程切換

我們知道一個(gè)CPU在同一時(shí)間只能運(yùn)行一個(gè)進(jìn)程，而并發(fā)實(shí)際上就是利用時(shí)間片，讓每個(gè)進(jìn)程在CPU上只能運(yùn)行一個(gè)時(shí)間片的時(shí)間，然后就被切換到另一個(gè)進(jìn)程，所以我們計(jì)算機(jī)雖然看起來(lái)似乎是非常流暢的運(yùn)行每個(gè)進(jìn)程，而實(shí)際上則是一卡一卡的運(yùn)行的，只不過(guò)這個(gè)時(shí)間非常短，我們感覺(jué)不到罷了。

那進(jìn)程首次調(diào)度完成被切換走，當(dāng)CPU二次調(diào)度該進(jìn)程時(shí)，是如何記得上次執(zhí)行到哪里了呢？

CPU中存在有大量的寄存器，進(jìn)程運(yùn)行產(chǎn)生的臨時(shí)數(shù)據(jù)都被保存在這些寄存器中，這些臨時(shí)數(shù)據(jù)被稱為進(jìn)程的硬件上下文，當(dāng)時(shí)間片消耗完的時(shí)候，進(jìn)程會(huì)保存這些上下文，現(xiàn)階段大家可以理解為保存到PCB中，當(dāng)進(jìn)程被二次調(diào)度時(shí)，進(jìn)程會(huì)將曾經(jīng)保存的硬件上下文進(jìn)行恢復(fù)（將之前保存的硬件上下文覆蓋到CPU的寄存器中）。

• 雖然CPU中的寄存器只有一套，但是寄存器內(nèi)部保存的數(shù)據(jù)可以有多套。
• CPU是被所有進(jìn)程共享的，但內(nèi)部的數(shù)據(jù)卻是進(jìn)程私有的。

大家可以理解為：在任意一個(gè)時(shí)刻，CPU中的數(shù)據(jù)只屬于一個(gè)進(jìn)程。

所以看起來(lái)，我們用的是同一個(gè)設(shè)備，但實(shí)際上進(jìn)程之間是具有獨(dú)立性的。

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

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

上篇文章我們講到了優(yōu)先級(jí)的概念，那Linux是如何在兼顧進(jìn)程優(yōu)先級(jí)、饑餓、效率來(lái)實(shí)現(xiàn)進(jìn)程調(diào)度的算法呢？

實(shí)際上操作系統(tǒng)想要實(shí)現(xiàn)一個(gè)進(jìn)程調(diào)度算法并不容易，而Linux對(duì)于進(jìn)程調(diào)度的算法設(shè)計(jì)非常優(yōu)秀，我們一起來(lái)學(xué)習(xí)一下吧：

之前我們學(xué)習(xí)進(jìn)程狀態(tài)時(shí)，有關(guān)進(jìn)程排隊(duì)中CPU運(yùn)行隊(duì)列有過(guò)這樣一張圖：

今天我們來(lái)細(xì)化一下運(yùn)行隊(duì)列中的成員：

這是Linux系統(tǒng)下對(duì)運(yùn)行隊(duì)列的設(shè)計(jì)。

不考慮其他成員，我們只看圈出來(lái)的兩個(gè)部分：

藍(lán)色部分為活動(dòng)隊(duì)列，紅色部分為過(guò)期隊(duì)列，他們兩個(gè)你可以認(rèn)為是完全相同的兩個(gè)結(jié)構(gòu)。

2.1Linux系統(tǒng)的進(jìn)程調(diào)度算法如何實(shí)現(xiàn)兼顧進(jìn)程優(yōu)先級(jí)的設(shè)計(jì)

該數(shù)組中一個(gè)元素就是一個(gè)進(jìn)程隊(duì)列，相同優(yōu)先級(jí)的進(jìn)程按照FIFO（先進(jìn)先出）規(guī)則進(jìn)行排隊(duì)調(diào)度，所以，數(shù)組下標(biāo)就是優(yōu)先級(jí)！

但我們之前學(xué)習(xí)優(yōu)先級(jí)時(shí)不是說(shuō)進(jìn)程優(yōu)先級(jí)范圍為[60,99]么，一共40個(gè)優(yōu)先級(jí)，為什么這里有140個(gè)優(yōu)先級(jí)呢？

首先這里我們只考慮100~139，這部分被稱為普通優(yōu)先級(jí)，100就對(duì)應(yīng)著60，139就對(duì)應(yīng)著99，而剩下0~99的部分為實(shí)時(shí)優(yōu)先級(jí)。

??什么是實(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(shuí)的優(yōu)先級(jí)高就僅服務(wù)誰(shuí)，所有用戶的優(yōu)先級(jí)都差不太多，不會(huì)出現(xiàn)誰(shuí)的優(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ì)考慮音樂(lè)播放器進(jìn)程會(huì)不會(huì)饑餓。
• 所以我們必須保證一些進(jìn)程實(shí)時(shí)盡快的被處理，所以也就有了實(shí)時(shí)優(yōu)先級(jí)的概念，而0~99這些優(yōu)先級(jí)就是為了這一部分而準(zhǔn)備的。

?所以我們運(yùn)行隊(duì)列中queue[140]的構(gòu)成大概為這樣子：

之前我們以為運(yùn)行隊(duì)列就是一個(gè)隊(duì)列，但實(shí)際上操作系統(tǒng)要給我們維護(hù)40個(gè)隊(duì)列，每個(gè)隊(duì)列都代表著不同的優(yōu)先級(jí)。

2.2Linux系統(tǒng)的進(jìn)程調(diào)度算法如何實(shí)現(xiàn)兼顧效率的設(shè)計(jì)

每次CPU運(yùn)行進(jìn)程，難道都要從開(kāi)始向上遍歷找不為空的隊(duì)列么，那也太麻煩了。

所以就有了bitmap[5]這個(gè)成員，該成員是int類型的數(shù)組，int類型占32個(gè)bit，所以5個(gè)int就是160個(gè)bit，而queue為140，多出來(lái)的20我們不管，那是不是檢測(cè)哪個(gè)優(yōu)先級(jí)隊(duì)列中有進(jìn)程就能夠轉(zhuǎn)化乘檢測(cè)對(duì)應(yīng)的比特位是否為1了呢??？

位操作的速度可比遍歷快多了。

比如：如果數(shù)組中某個(gè)元素為0，則證明該32個(gè)比特位都為0，也就證明該32個(gè)隊(duì)列都為空，如果某個(gè)元素不為0，那該問(wèn)題就轉(zhuǎn)化為了如何從一個(gè)整形中提取出最低位的不為0的比特位。

所以該算法在系統(tǒng)中查找一個(gè)最合適調(diào)度的進(jìn)程的時(shí)間復(fù)雜度是一個(gè)常數(shù)，不會(huì)隨著進(jìn)程的增多而導(dǎo)致時(shí)間成本增加，被稱為O(1)調(diào)度算法。

2.3nr_active

表示該運(yùn)行隊(duì)列共有多少個(gè)活躍進(jìn)程。

2.4Linux系統(tǒng)的進(jìn)程調(diào)度算法如何實(shí)現(xiàn)兼顧進(jìn)程饑餓的設(shè)計(jì)

假設(shè)在運(yùn)行隊(duì)列里存在有很多優(yōu)先級(jí)為139的進(jìn)程等待執(zhí)行，但此時(shí)不斷產(chǎn)生更高優(yōu)先級(jí)的進(jìn)程，也就導(dǎo)致優(yōu)先級(jí)為139的進(jìn)程進(jìn)程饑餓的問(wèn)題了。

2.4.1理論上講解

那Linux系統(tǒng)是如何處理進(jìn)程饑餓的呢？

Linux系統(tǒng)搞了兩個(gè)一摸一樣的結(jié)構(gòu)就是為了處理進(jìn)程饑餓。

一個(gè)稱之為活躍隊(duì)列，一個(gè)稱之為過(guò)期隊(duì)列。

CPU只會(huì)執(zhí)行活躍隊(duì)列中的進(jìn)程，而新產(chǎn)生的進(jìn)程會(huì)被操作系統(tǒng)添加到過(guò)期隊(duì)列，不論這個(gè)新進(jìn)程的優(yōu)先級(jí)高低，等活躍隊(duì)列中的進(jìn)程都被執(zhí)行完成了后，此時(shí)過(guò)期隊(duì)列搖身一變成為活躍隊(duì)列，而活躍隊(duì)列變?yōu)檫^(guò)期隊(duì)列，周而復(fù)始，也就解決了進(jìn)程饑餓的問(wèn)題。

注意：如果某個(gè)處在活躍隊(duì)列中的進(jìn)程的時(shí)間片消耗完，該進(jìn)程就會(huì)從活躍隊(duì)列中剝離，然后被添加到過(guò)期隊(duì)列。

2.4.2如何實(shí)現(xiàn)的？

我們將藍(lán)色框與紅色框定義為兩個(gè)結(jié)構(gòu)體：

struct q//這兩個(gè)結(jié)構(gòu)體相同，這里就寫(xiě)一個(gè)大家理解就行
{
    int nr_active;
    int bitmap[5];
    task_struct queue[140];
}

再定義一個(gè)數(shù)組struct q array[2];

該數(shù)組用來(lái)存放這兩個(gè)結(jié)構(gòu)體。

再定義兩個(gè)成員*active與*expired：

這兩個(gè)指針?lè)謩e指向數(shù)組中的內(nèi)容，即：

struct q *active=&array[0];
struct q *expired=&array[1];

?每當(dāng)活躍隊(duì)列為空時(shí)，就會(huì)交換這兩個(gè)指針變量的內(nèi)容，使之指向?qū)Ψ皆瓉?lái)指向的內(nèi)容，這也就完成了活躍隊(duì)列變?yōu)檫^(guò)期隊(duì)列，過(guò)期隊(duì)列變?yōu)榛钴S隊(duì)列的操作：

swap(&active,&expired);

所以Linux系統(tǒng)對(duì)于進(jìn)程調(diào)度的設(shè)計(jì)是不是非常巧妙呢??？?

=========================================================================

如果你對(duì)該系列文章有興趣的話，歡迎持續(xù)關(guān)注博主動(dòng)態(tài)，博主會(huì)持續(xù)輸出優(yōu)質(zhì)內(nèi)容

??博主很需要大家的支持，你的支持是我創(chuàng)作的不竭動(dòng)力??

??~ 點(diǎn)贊收藏＋關(guān)注 ~??

=========================================================================

到了這里，關(guān)于【Linux】進(jìn)程周邊004之進(jìn)程的調(diào)度與切換（領(lǐng)略Linux系統(tǒng)進(jìn)程調(diào)度算法的神奇）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！