《Linux核心設計與實作》CHAPTER4閱讀梳理

【學習時間：3hours】

【學習内容：多任務；程序排程政策；Linux中程序排程的關鍵問題；搶占】

個人思考部分見【】标出的部分

一、多任務

1.非搶占式多任務

程序會一直執行直到自己主動停止運作（這一步驟稱為讓步）

2.搶占式多任務

Linux/Unix使用的是搶占式的方式；強制的挂起程序的動作就叫做搶占。程序在被搶占之前能夠運作的時間是預先設定好的（也就是程序的時間片）

二、與政策相關的概念

1.程序的消耗類型

1. I/O消耗型程序
   • 程序的大部分時間用來送出I/O請求或者等待I/O請求
   • 多數使用者圖形界面（GUI）都屬于I/O密集型
2. 處理器耗費型
   • 時間大多數用在執行代碼上
   • 例如MATLAB
   • 往往要延長運作時間并降低排程頻率

2.程序優先級

1. 基于優先級的排程：優先極高的程序先運作；相同優先級的程序按照輪轉方式進行排程；
2. 優先級分為兩類
   • nice值（從-20——+19）：預設值為0；數值越大意味着優先級越低；可以通過 ps-el檢視系統程序清單并找到NI标記列對應的優先級
   • 實時優先級（從0——99）：越高的實時優先級級數意味着程序優先級越高
   • 二者互不互動
3. 時間片
   • 時間片表示程序在被搶占之前所能夠持續運作的時間；排程政策必須确定一個預設的時間片；
   • Linux的CFS排程器并沒有直接劃分時間片到程序，而是将處理器的使用比例劃分給了程序。也就是說，其搶占時機取決于新的可執行程式消耗了多少處理器使用比，如果消耗的使用比比目前程序小，則新程序立即投入運作搶占目前程序。

三、Linux排程算法

1.排程器類

1. Linux排程器是以子產品方式提供的（也就是排程器類），目的是允許不同類型的程序可以有針對性地選擇排程算法
2. 排程器類允許多種不同的可動态添加的排程算法并存，排程屬于自己範疇的程序；
3. 排程器代碼會按照優先級順序周遊排程類，擁有一個可執行程序的最高優先級的排程器類勝出，去選擇下面要執行的那一個程式；

2.Unix中系統排程問題

1. 将nice值映射到時間片的話，就必須将nice值對應到處理器的絕對時間；這樣會導緻程序切換無法最優進行；
2. 如果使用相對nice值，所帶來的效果将會極大取決于其nice的初始值；
3. 如果執行nice值到時間片的映射，時間片極大受制于定時器。

3.公平排程

1. CFS基于一個簡單的理念：程序排程的效果應當如同系統具備一個理想中的完美任務處理器。CFS的做法如下：
   • 允許每個程序運作一段時間、循環輪轉、選擇運作最少的程序作為下一個運作程序；
   • nice值作為程序獲得的處理器運作比的權重（而不是完全由nice決定時間片）；
   • 每個程序都按照其權重在全部的可運作程序中所占的比例對應的“時間片”來運作

【所謂“魚與熊掌不可得兼”即如此——越小的排程周期就會表現出越好的互動性，也更接近于“同時完成多任務”這一孜孜追求的目标；然而系統必須承受更高的切換代價和更差的系統吞吐量——甚至将絕大多數精力耗費在這種來回倒騰上】

四、Linux排程的實作

1.時間記賬

• 所有的排程器都必須對程序的運作時間做記賬；
• CFS使用排程器實體結構來追蹤運作記賬

2.虛拟實時

• vrntime變量【也就是在上面所說的實體結構中】存放虛拟運作時間。虛拟時間以ns為機關，和節拍定時器無關；
• update_curr()函數實作了記賬功能；計算了目前程序的執行時間并将其存放在data_exec中；然後将運作時間傳遞給了_update_curr()，由後者再根據目前可運作程序總數對運作時間進行計算，最終确定上述的權重值與目前運作程序的vrntime。

• 

3.程序選擇

1. CFS算法核心：選擇具有最小vrntime的任務
2. 具體做法：利用紅黑樹rbtree（以節點形式存儲資料的二叉樹）
3. 舉例：
   • 選擇下一個任務：從根節點中序周遊二叉樹，一直到葉子節點（也就是vrntime最小的程序）；
   • 向樹中加入程序：在程序變為可執行狀态或者通過fork()調用第一次建立程序；
   • 從樹中删除程序：發生在程序阻塞或者終止的時候

【由此我們可以看到，二叉樹中存儲的全部是可執行程序】

4.程序排程入口

1. 程序排程的主要入口點是函數schedule()，定義在kernel/sched.c中；這正是内和其他部分用于排程程序排程器的入口
2. 這一函數最重要的工作就是調用pick_next_state()，依次檢查每一個排程類，并從最高優先級的排程類中，選擇最高優先級程序

5.睡眠和喚醒

1. 程序休眠一定是為了等待一些事件
   • 程序把自己标記成休眠狀态，從可執行紅黑樹中移除；
   • 放入等待隊列——由等待某些時間發生的程序組成的連結清單，核心用wake_queue_head_t來代表等待隊列

   • 

2. 喚醒操作由函數wake_up()進行
   • 它會調用函數try_to _wake_up()将程序設定為TASK_RUNNING狀态，調用enqueue_task()将程序放入紅黑樹中
   • 當然，也存在虛假喚醒程序的狀态

五、搶占和上下文切換

1.上下文切換由定義在kernel/sched.c中的context_switch()函數負責，每當一個新的程序被選出來準備運作的時候，schedule()就會調用該函數：

• 調用switch_mm()，負責把虛拟記憶體從上一個程序映射切換到新的程序中；
• 調用switch_to()，負責從上一個程序的處理器狀态切換到新程序的處理器狀态

2.Linux系統支援核心搶占

1. 隻要沒有鎖，核心就可以程序搶占；
2. 為了支援搶占，每個程序的thread_info都加入了preempt_count計數器（初值為0，每當使用鎖的時候就加1，釋放鎖的時候數值減1），當數值為0的時候，核心就可以搶占
3. 核心搶占發生在：
   • 中斷處理程式正在執行且傳回核心空間之前；
   • 核心代碼再一次具有可搶占性的時候；
   • 核心中的任務顯式地調用schedule函數

總結

我們一路從最基本的堆棧變化研究到程序的建立和執行；那麼到了現在則水到渠成地開始關注如何協調許多個不同的程序方面（較好的排程政策也是現代處理系統的優勢之一）