Linux 真實調度算法

下圖是Linux2.6內核中進程隊列的數據結構，也有Linux2.6內核進程O(1)調度算法，可單單看一副圖片，也不知所以然

1. queue[140]

首先就是這個queue[140]，queue它就是個哈希表，優先級就是哈希槽（slot），x-60 + (140 - 40)就是哈希轉換算法

Linux操作系統的優先級其實總共是140個，那之前不是實驗出優先級的范圍是[60, 99]，總共40個嗎？這里為啥是140個呢

因為Linux的優先級有實時優先級和分時優先級，它既是一個實時操作系統，又是一個分時操作系統，而[0, 99]是實時優先級（并不考慮），[100, 139]是分時優先級的范圍，是咱們所要去關注的

x的取值范圍是[60, 99]，將其代入到哈希轉換算法中，得出的取值范圍不就是[100, 139]。那此時就會存在疑問，既然這個實時優先級不考慮，為啥還要將它設計出來呢？

實時優先級適用于實時操作系統，Linux最初確實是作為分時操作系統設計的，主要應用于服務器領域。但它的調度算法之所以要加入實時操作系統特性，最根本的原因在于：任何操作系統開發者都希望擴大用戶群體

雖然Linux在后端服務器領域應用最為廣泛，但這并不意味著它只能用于服務器場景。實際上，Linux同樣適用于工業控制和制造等實時性要求較高的領域。因此，現代操作系統通常都會同時支持分時和實時兩種調度模式

2. bitmap[5] 位圖

bitmap它首先是個位圖，unsigned int bitmap[5]總共有160個比特位（32*5），比特位前140個的位置就逐一對應著queue[140]的slot，比特位中的內容：1/0，1表示該slot指向的進程不為空，0則為空

這里運行隊列咱們只考慮從100開始，上面只是做個形象的展示。進程調度，宏觀上先看優先級，優先級相同的先進先出（FIFO算法），比如圖中2號優先級的第一個進程先調度

比如0000100，優先級為3的進程不為空。為啥位圖的元素個數是5，因為4是128，6是192，只有5是最接近140的

調度器快速地挑選一個進程要分成兩步，第一步就是挑隊列，而挑隊列再也不用去遍歷queue這個指針數組了，直接查看對應的位圖bitmap

第二步：再到隊列中去挑特定的進程→這樣挑選一個進程基本上做到了幾乎為O(1)的時間復雜度，將這個調度算法稱為Linux內核進程調度算法之大O(1)調度算法

3. nr_active

nr_active就表示整個隊列中一共有多少個進程。所以進程調度時先查nr_active→bitmap（確認下標）→queue，找到目標隊列，從目標隊列頭部提取內容，頭部移除（Pop_from），將當前結點的PCB放入到struct task_struct* current指針里，執行切換算法，將current指針指向的進程放到CPU上就能運行了

如果這樣調度的話，假如今天有一個60號進程，它是一個死循環，也有一個99號進程。60進程時間片到了，運行完畢后，切換下去，它未來還要被調度的，所以就將它重新放到了這個隊列（60優先級指向的隊列）的最后面進行排隊

此時你就會發現存在什么樣的問題，CPU在調度時，只有將60優先級隊列中的所有進程全部跑完，才會跑后面優先級隊列的進程，跑完前面所有進程，才會跑99號進程，可是60號進程是個死循環，那99號進程就永遠無法被調度，就會造成進程饑餓問題

4. 活躍進程與過期進程

那為了解決上面進程饑餓問題，就存在著活躍進程與過期進程之分，活躍進程指向藍色框，過期進程指向紅色框，框中內容是相同的

挑選活躍進程中60號進程，它要被CPU調度，等時間片到了之后，它要從CPU上剖離下來，那此時這個進程它不能再放回到active指針所指向的活躍進程中的60號隊列當中，得鏈入到expired指針所指向的過期進程中的60號隊列當中，CPU它調度完成的進程都是要放入到過期進程的對應位置

這樣active queue進程會越來越少，expired queue進程會越來越多。直至active queue中的進程全部為0，即nr_active = 0，最后直接swap(&active, &expired)，交換它兩指向的內容，重新進行調度

上面才算是真正的Linux內核進程調度算法之大O(1)調度算法。這里還要提到的一點就是：當新進程到來時，如果將新進程放到過期進程當中，目前這個進程就處于就緒狀態

很多分時操作系統是支持內核優先級搶占的，比如當前正在運行的是80號進程，新來了一個65號進程，新進程就要給特權，讓它盡快運行，那就只能讓它插隊，那總不能讓它插到過期進程的隊列當中吧，就直接讓它鏈入到活躍進程的65號隊列當中，就開始了優先級的搶占

環境變量

1. 基本概念

• 環境變量（environmentvariables）一般是指在操作系統中用來指定操作系統運行環境的一些參數
• 比如：我們在編寫C/C++代碼的時候，在鏈接的時候，從來不知道我們所鏈接的動態靜態庫在哪里，但是照樣可以鏈接成功，生成可執行程序，原因就是有相關環境變量幫助編譯器進行查找
• 環境變量通常具有某些特殊用途，還有在系統當中通常具有全局特性
• 常見環境變量
  • PATH：指定命令的搜索路徑
  • HOME：指定用戶的主工作目錄(即用戶登陸到Linux系統中時，默認的目錄）
  • SHELL：它的值通常是/bin/bash

2. 命令行參數

main函數有參數嗎？有，argv相當于一張命令行參數表，而argc表示argv指針數組元素的個數

#include<stdio.h>int main(int argc, char* argv[])
{for (int i = 0; i < argc; i++){printf("argv[%d]: %s\n", i, argv[i]);}return 0;
}

再寫一段代碼，來幫助理解程序如何利用argv命令行參數表實現選項功能

int main(int argc, char* argv[])
{if (argc != 2){printf("Usage: %s [-a|-b|-c]\n", argv[0]);return 0;}const char* arg = argv[1];if (strcmp(arg, "-a") == 0)printf("這是功能1\n");else if (strcmp(arg, "-b") == 0)printf("這是功能2\n");else if (strcmp(arg, "-c") == 0)printf("這是功能3\n");else printf("Usage: %s [-a|-b|-c]\n", argv[0]);return 0;
}

3. PATH 環境變量

可是執行我們自己的命令需要帶./，執行系統的命令卻不需要，這是為什么呢？

首先你寫的二進制指令與系統的指令并沒有本質區別，咱們所用的指令本質上在系統里提前預裝的二進制程序，你寫的二進制程序同樣如此，它們兩個并沒有本質區別。 那為啥一個帶路徑，一個不帶路徑呢?

你要知道，要去執行一個程序，那必須先找到它。./code在當前路徑下執行可執行程序， 系統指令卻不需要帶路徑的原因是因為系統中存在環境變量

特別不建議將你自己寫的二進制程序拷貝到/usr/bin目錄下，因為你的二進制文件并沒有經過測試，可能會存在bug，可能會污染系統原本的指令池

那系統憑啥就知道執行命令時就去/usr/bin目錄下去找呢？因為系統中存在環境變量PATH，這個環境變量在系統中默認是存在的，用來標識一串路徑，告訴系統，要去哪些路徑下去找二進制可執行文件（系統中搜索指令的默認搜索路徑）

4. 環境變量具體操作

介紹兩個指令，env：查看系統中所有的環境變量，echo $環境變量名稱：具體查看一個環境變量的內容

對于PATH這個環境變量，執行ls指令時，以冒號作為分隔符，從第一個路徑去找可執行文件，沒找到再依次去后面的路徑找

如果想要去修改一個環境變量的內容，直接環境變量名稱=具體修改內容，比如PATH=/home/xiao，就直接進行路徑覆蓋

如果想要在PATH這個環境變量中去新增一個路徑，可以PATH=$PATH:絕對路徑。那我修改了咋改回來呢？關掉xshell，再重新登錄即可（恢復默認的環境變量）