第一次作業：關於Linux 2.6.20進程模型和O(1)調度器演算法的分析

1.寫在最前本文基於 Linux Kernel 2.6.20 的源代碼，分析的是本版本linux的進程模型和其O(1) 調度器的基本演算法。源碼瀏覽地址： https://elixir.bootlin.com/linux/v2.6.20/source/kernel 2.關於進程 2.1進程的定義 ...

1.寫在最前

本文基於 Linux Kernel 2.6.20 的源代碼，分析的是本版本linux的進程模型和其O(1) 調度器的基本演算法。
源碼瀏覽地址：
https://elixir.bootlin.com/linux/v2.6.20/source/kernel

2.關於進程

2.1進程的定義

從不同的角度，進程可以有不同的定義，比較經典的定義有：

1）進程是程式的一次執行過程

2）進程是一個程式及其數據在處理器上順序執行時所發生的活動。

3）進程是具有獨立功能的程式在一個數據集合上運行的過程，他是系統進行資源分配和調度的一個獨立單位。

在引入了進程實體的概念後，我們可以把傳統的操作系統中的進程定義為：

“進程是進程實體的運行過程，是系統進行資源分配和調度的一個獨立單位”。

2.2看一眼進程

我們可以使用$ps查詢正在運行的進程，
比如$ps -eo pid,comm,cmd，
下圖為執行結果（部分）:
enter image description here
(-e表示列出全部進程，-o pid,comm,cmd表示我們需要PID，COMMAND，CMD信息)

3.關於進程的組織

linux將進程的列表存放在叫做任務隊列的雙向迴圈鏈表中。
鏈表中的每一項都是類型為task_struct，稱為進程描述符，該結構定義在<linux/sched.h>文件中。
進程描述符中包含一個具體進程的所有信息。
其包含的數據能完整地描述一個正在執行的程式：進程標識符（PID），進程狀態，優先順序等其他所有信息。

3.1進程標識符

pid_t pid;

*來源：https://elixir.bootlin.com/linux/v2.6.20/source/include/linux/sched.h#L855

PID(process IDentity)是一個整數，每一個進程都有一個唯一的PID來代表自己的身份，進程也可以根據PID來識別其他的進程。
在CONFIG_BASE_SMALL配置為0的情況下，PID的取值範圍是0到32767，即系統中的進程數最大為32768個，已可滿足普通用戶的日常使用。

#define PID_MAX_DEFAULT (CONFIG_BASE_SMALL ? 0x1000 : 0x8000)

*來源：https://elixir.bootlin.com/linux/v2.6.20/source/include/linux/threads.h#L27

3.2進程狀態

volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */

*來源：https://elixir.bootlin.com/linux/v2.6.20/source/include/linux/sched.h#L802

state的可能取值有

#define TASK_RUNNING        0
#define TASK_INTERRUPTIBLE  1
#define TASK_UNINTERRUPTIBLE    2
#define TASK_STOPPED        4
#define TASK_TRACED     8
/* in tsk->exit_state */
#define EXIT_ZOMBIE     16
#define EXIT_DEAD       32
/* in tsk->state again */
#define TASK_NONINTERACTIVE 64
#define TASK_DEAD       128

*來源：https://elixir.bootlin.com/linux/v2.6.20/source/include/linux/sched.h#L143

接下來對幾個常用狀態進行簡單的分析。

狀態	描述
TASK_RUNNING	進程正在執行或者進程正在準備執行。
TASK_INTERRUPTIBLE	進程由於等待某些條件處於阻塞（掛起的狀態），一旦等待的條件成立，便會從該狀態變成TASK_RUNNING。這些條件主要包括：硬中斷、資源、某些信號等等。
TASK_UNINTERRUPTIBLE	與TASK_INTERRUPTIBLE類似。但我們傳遞任何信號都無法喚醒它，只有當它所等待的資源可用時，它才被喚醒。
TASK_STOPPED	進程停止執行。當進程接收到SIGSTOP、SIGTTIN、SIGTSTP或者SIGTTOU信號等之後就會進入該狀態。
TASK_TRACED	進程被debugger等進程監視。進程執行被調試程式所停止，當一個進程被另外的進程所監視，每一個信號都會讓進城進入該狀態。
EXIT_ZOMBIE	進程的執行被終止，但其父進程還未使用`wait()`等系統調用來獲取它的終止信息，此時進程成為僵屍進程。
EXIT_DEAD	進程被“殺死”，也就是進程的最終狀態。

而進程狀態之間的轉換，大致如下圖。
enter image description here

3.3優先順序

int prio, static_prio, normal_prio;

*來源：https://elixir.bootlin.com/linux/v2.6.20/source/include/linux/sched.h#L815

簡單分析
欄位|描述
---|---
prio|保存動態優先順序
static_prio|保存靜態優先順序
normal_prio|它的值取決於優先策略和靜態優先順序

4.關於O(1)調度演算法

4.1 調度器與進程

調度器：
通常來說，操作系統是應用程式和可用資源之間的媒介。

典型的資源有記憶體和物理設備。

CPU也可以認為是一個資源，調度器可以臨時分配一個任務在上面執行（單位是時間片）。調度器使得我們同時執行多個程式成為可能，因此可以與具有各種需求的用戶共用CPU。所以，如何高效地分配CPU時間片，是調度器的重要目標。

活動進程和過期進程:
調度器為每一個CPU維護了兩個進程隊列數組：active數組和expire數組。

active進程: 那些還沒有用完時間片的進程
expire進程: 那些已經用完時間片的進程

調度程式的工作就是在活動進程集合中選取一個最佳優先順序的進程,如果該進程時間片恰好用完,就將該進程放入過期進程集合中.

4.2 滿足O(1)的數據結構？

通過在數據結構課上的知識，大多數演算法的時間複雜度在O(log N) 基本上就是最好的結果，那麼2.6 的 O(1) 調度演算法是怎麼做到的？

在回答這個問題之前，我們先回顧一下數據結構的四種基本操作以及其時間複雜度：

access：隨機訪問。array 是唯一滿足 O(1) 隨機訪問的數據結構。
search：搜索。hash table 是 O(1) 時間複雜度的，但最壞情況下是 O(N) 的。大部分 tree（b-tree / red-black tree）平均情況和最壞情況都是 O(log N)。
insert/deletion：插入和刪除。linked list，stack，queue 在平均和最壞情況下都是 O(1)。

綜上，若想達成 O(1) scheduler 的目標，操作只能包含純粹的 access，insert 和 deletion，不能有 search。

此外，對於 scheduler，我們應該儘量要選擇平均情況和最壞情況表現一致的演算法。如果平均情況是 O(1)，最壞情況是 O(n)，那麼這個 scheduler 會給系統帶來很大的不確定性

所以我們的選擇並不多。
對於access 只能用 array，
對於insert / deletion 只能用 linked list / queue / stack。

4.3 演算法思路

我們先看一張大神給出的正確答案。
enter image description here

在linux中一共有140 種不同的優先順序，所以我們就用長度為 140 的 array 去記錄優先順序。在每個優先順序下使用 FIFO queue 來管理該優先順序下的所有 process。新來的插到隊尾，先進先出。此時，insert / deletion 都是 O(1)。
但，應該如何找到當前最高優先順序下的process？若從優先順序 0 開始遍歷，演算法顯然不是O(1)。在 2.6 scheduler 里採用 bitarray，為每種優先順序分配一個 bit，若該優先順序隊列下有 process，那麼對相應的 bit 染色，置為 1，否則置為 0。

現在，問題簡化成尋找一個 bitarray 中最高位是 1 的 bit（left-most bit）。

4.4 重要數據結構

struct runqueue（運行隊列）：每個cpu都有一個運行隊列

struct rq {
    spinlock_t lock;
    unsigned long nr_running;
    unsigned long raw_weighted_load;
    unsigned long cpu_load[3];
    unsigned long long nr_switches;
    unsigned long nr_uninterruptible;
    unsigned long expired_timestamp;
    /* Cached timestamp set by update_cpu_clock() */
    unsigned long long most_recent_timestamp;
    struct task_struct *curr, *idle;
    unsigned long next_balance;
    struct mm_struct *prev_mm;
    struct prio_array *active, *expired, arrays[2];
    int best_expired_prio;
    atomic_t nr_iowait;
    ...
    }

*來源：https://elixir.bootlin.com/linux/v2.6.20/source/kernel/sched.c#L205
其中最最重要的部分便是prio_array。
prio_array（優先順序數組）
O(1)演算法的核心數據結構即為prio_array結構體。

struct prio_array {
    unsigned int nr_active;
    DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */
    struct list_head queue[MAX_PRIO];
};

*來源：https://elixir.bootlin.com/linux/v2.6.20/source/kernel/sched.c#L192

其中

bitmap：優先順序點陣圖，它使用一個位（bit）來代表一個優先順序。
queue：表示進程動態優先順序的數組，它包含了每一種優先順序進程所形成的鏈表。

4.5 O(1)調度演算法的實現

schedule()是實現進程調度的主要函數，並且負責完成進程切換工作，其用於確定最高優先順序進程的代碼非常快捷高效。它在kernel/sched.c中的定義如下

asmlinkage void __sched schedule(void)
{
    struct task_struct *prev, *next;
    struct prio_array *array;
    struct list_head *queue;
    unsigned long long now;
    unsigned long run_time;
    int cpu, idx, new_prio;
    long *switch_count;
    struct rq *rq;
    ...
}

*來源:https://elixir.bootlin.com/linux/v2.6.20/source/kernel/sched.c#L3412
其中，選擇候選進程的關鍵代碼為：

    idx = sched_find_first_bit(array->bitmap);
    queue = array->queue + idx;
    next = list_entry(queue->next, struct task_struct, run_list);

*來源:https://elixir.bootlin.com/linux/v2.6.20/source/kernel/sched.c#L3509

例如：在queue[i]中，存放的計時優先順序為i的進程隊列的鏈表頭。而bitmap是用來作為進程隊列queue的索引點陣圖。
bitmap的每一位都與queue[i]對應。當queue[i]的進程隊列不為空時，bitmap的對應位就為1，否則為0。
現在只需要使用彙編指令按照進程優先順序從高到底的方向找到第一個為1的位置idx，idx就是當前運行隊列中最高的優先順序數（函數sched_find_first_bit()便是用來完成這一功能）。
那麼，queue[idx]->next便是我們要找的候選進程。
當active數組中的所有進程都被移到expire數組中後，調度器交換active數組和expire數組。
當進程被移入expire數組時，調度器會重置其時間片，因此新的active數組又恢復了初始情況，而expire數組為空，從而開始新的一輪調度。

4.6 更多細節

除了選取最高優先順序進程外，O(1)演算法還有其他許多的細節，比如進程動態優先順序的計算，調度與搶占時機，由於個人水平原因，無法一一闡述。

5.感受與總結

通過查閱資料我得知在linux2.4版本時，2.4的O(n)scheduler早已被詬病已久。
而在劃時代的2.6版本中 O(1)scheduler的出現想必一定讓當時的開發者興奮不已。雖然如今的linux所使用的是更加強調公平性的 CFS（Completely Fair Scheduler），但它依舊用簡單的演算法和獨特的設計取得了自己的地位並且影響更多的開發者。無論任何調度器演算法都還無法滿足所有應用的需要，CFS也有一些負面的測試報告。相信隨著Linux的不斷發展，更多開發者的不懈努力，還會出現更好的調度演算法。