🌎進程的調(diào)度與切換

文章目錄：

進程的調(diào)度與切換

????進程切換

????進程調(diào)度
??????活動狀態(tài)進程隊列
??????位圖判斷
??????過期隊列

????總結(jié)

---

前言：

??在Linux操作系統(tǒng)中，進程的調(diào)度與切換是操作系統(tǒng)核心功能之一，它直接影響著系統(tǒng)的性能和響應速度。那么話不多說，開啟我們今天的話題！

---

🚀進程切換

??CPU中存在眾多寄存器，不同的寄存器有不同的功能，這些寄存器都在CPU中保存著，每一個都能裝一定的數(shù)據(jù)。

??運行隊列控制著PCB排隊執(zhí)行，每執(zhí)行到一個進程的時候，內(nèi)存里的eip指針會逐條追蹤下一條指令。

??我們要知道，所有的保存都是為了恢復，保存在CPU寄存器里的數(shù)據(jù)，是當前進程時間片用完之前所執(zhí)行的進度，而 所有的恢復，都是為了從上次的運行位置繼續(xù)運行。

??并且，CPU內(nèi)的所有臨時數(shù)據(jù)，我們稱之為進程的 硬件上下文！ 硬件上下文，由我們的 進程進行保存，得以保護上下文。

??當進程在進行第二次及第N次調(diào)度進程的時候，進程被放到CPU上開始運行，將曾經(jīng)保存的硬件上下文進行恢復。

??所以進程切換最重要的就是 進程上下文的保存和恢復。

??我們可以看一下內(nèi)核中的一些寄存器：

注意： CPU中的寄存器只有一套，而寄存器保存的數(shù)據(jù)可以有多套。雖然寄存器數(shù)據(jù)放在了共享的CPU設(shè)備內(nèi)，但是 所有的數(shù)據(jù)都是被進程私有的！

---

🚀進程調(diào)度

??活動狀態(tài)進程隊列

??我們上次說過，Linux實現(xiàn)進程調(diào)度的算法，需要考慮 優(yōu)先級，考慮進程饑餓，以及效率。那么CPU是如何實現(xiàn)進程調(diào)度的呢？

??我們來看一下Linux下CPU的運行隊列的各項屬性：

??我們首先看藍色框內(nèi)的內(nèi)容，有一個叫做 queue[140] 的數(shù)組，這里的 queue數(shù)組表示活動狀態(tài)進程的進程隊列。

??其中在queue數(shù)組中，索引0~99號下標我們是不用的，這是因為0-99號下標對應的是 實時進程的優(yōu)先級，實時進程是內(nèi)核里更加重要的進程，放 在前100位由操作系統(tǒng)控制，避免系統(tǒng)搶占的情況。

??所以我們只剩下 100-139 這個范圍可操控，其實這也就和我們優(yōu)先級的可控范圍大小相同，正好對應隊列的四十個空位，而OS通過 某種映射關(guān)系，將可控優(yōu)先級映射到數(shù)組 100-139的下標。

---

??位圖判斷

??我們看藍色框內(nèi)還有一項 bitmap數(shù)組，類型為int，這個數(shù)組用來干嘛呢？只能存儲5個整形變量。

??數(shù)組的名字叫做bitmap已經(jīng)很明顯了，就是位圖，5個整形元素有 32 * 5 = 160 個比特位，比特位的位置，表示哪一個隊列。比特位的內(nèi)容，表示該隊列為不為空。

?比如：0000 … 0000 ，如果最左側(cè)0對應queue[100]的位置，那么如果該比特位為0表示在該下標映射的優(yōu)先級下該隊列為空，否則不為空。

??有人會問：為什么要用位圖？不得不說，這是個愚蠢的問題，遍歷整個隊列的時間開銷要遠大于查找位圖。

??所以，bitmap是用來檢測隊列中是否有進程，檢測對應的比特位是否為1！

??而藍色框內(nèi)還有一個元素：nr_active，在Linux中，nr_active 是運行隊列中用于表示活躍進程數(shù)量的計數(shù)器。nr_active 的值可以告訴內(nèi)核有多少進程正在等待執(zhí)行，從而幫助內(nèi)核進行進程調(diào)度和資源分配。

---

??過期隊列

??在紅色框中的三項屬性與藍色框中的三項屬性完全相同，也就是另外一個隊列，被稱為——過期隊列。

??活躍隊列表示當前CPU正在執(zhí)行的運行隊列，而 正在執(zhí)行的運行隊列（也就是活躍隊列）是不可以增加新的進程的。

??所以操作系統(tǒng)設(shè)置了一個 和活躍隊列相同屬性的過期隊列，當活躍隊列正在執(zhí)行時如果有進程需要添加進運行隊列，那么就會添加至過期隊列當中，也就是說 活躍隊列的進程一直在減少，而過期隊列中的進程一直在增多！

??當活躍隊列的進程執(zhí)行完畢后，就會和過期隊列進行交換，它們交換的方式是通過兩個結(jié)構(gòu)體指針：

??就是 active 和 expired 結(jié)構(gòu)體指針，它們分別指向活躍隊列和過期隊列，而活躍隊列與過期隊列由于屬性完全相同，于是被放在了一個叫做 prio_arry_t[2] 的數(shù)組里，prio_arry_t[0]指向活躍隊列，prio_arry_t[1]指向過期隊列：

struct q{//q是我隨意取的名字int nr_active;int bitmap[5];task_struct queue[140];
}struct q *active;//活躍隊列
struct q *expired;//過期隊列struct q *active = &prio_array_t[0];
struct q *expired = &prio_array_t[1];

??當活躍隊列被CPU執(zhí)行完畢后，我們 只需要交換兩個指針的內(nèi)容即可，這樣僅僅是指向的內(nèi)容變了，活躍隊列變?yōu)檫^期隊列，過期隊列變活躍隊列，并且時間復雜度為 O(1)：

swap(active, expried);//直接交換兩個指針的內(nèi)容

??新增進程在過期隊列里插入，此時正在執(zhí)行的是活躍隊列，所以這個時候在過期隊列里就有時間處理競爭饑餓的問題了。

??這樣，我們競爭饑餓，優(yōu)先級，以及進程效率都解決了。

---

📒??總結(jié)

• ?進程切換最重要的部分就是 進程上下文的保護和恢復。
• ?進程調(diào)度的優(yōu)先級問題由 活躍進程數(shù)組的下標與進程優(yōu)先級形成一種映射關(guān)系 解決。
• ?進程調(diào)度的時間復雜度問題由 位圖和兩個結(jié)構(gòu)體指針 解決，時間復雜度控制在了O(1)。
• ?進程調(diào)度的進程饑餓問題由 活躍隊列和過期隊列 解決。

---

??創(chuàng)作不易，如果這篇文章對你有幫助的話，還望三連支持博主呀~~