第一次作業：基於Linux進程模型分析

1.進程與線程 1.0 進程：進程是正在運行的程式的實例（an instance of a computer program that is being executed）。進程是一個具有一定獨立功能的程式關於某個數據集合的一次運行活動。它是操作系統動態執行的基本單元，在傳統的操作系統中，進程既 ...

　　1.進程與線程

1.0 進程：

進程是正在運行的程式的實例（an instance of a computer program that is being executed）。
進程是一個具有一定獨立功能的程式關於某個數據集合的一次運行活動。它是操作系統動態執行的基本單元，在傳統的操作系統中，進程既是基本的分配單元，也是基本的執行單元。

1.1 線程：

線程，有時被稱為輕量級進程(Lightweight Process，LWP），是程式執行流的最小單元。

1.2 進程與線程的關係和區別：

進程是資源的分配和調度的一個獨立單元，而線程是CPU調度的基本單元。
同一個進程中可以包括多個線程，並且線程共用整個進程的資源（寄存器、堆棧、上下文），一個進程至少包括一個線程。
進程在執行過程中擁有獨立的記憶體單元，而多個線程共用記憶體，從而極大地提高了程式的運行效率。
線程是輕兩級的進程，它的創建和銷毀所需要的時間比進程小很多，所有操作系統中的執行功能都是創建線程去完成的。
每個獨立的進程有一個程式運行的入口、順序執行序列和程式的出口。但是線程不能夠獨立執行，必須依存在應用程式中，由應用程式提供多個線程執行控制。
線程有自己的私有屬性TCB，線程id，寄存器、硬體上下文，而進程也有自己的私有屬性進程式控制制塊PCB，這些私有屬性是不被共用的，用來標示一個進程或一個線程的標誌。

　　2.Linux簡介

2.0 定義：

Linux是一套免費使用和自由傳播的類Unix操作系統，是一個基於POSIX和UNIX的多用戶、多任務、支持多線程和多CPU的操作系統。它能運行主要的UNIX工具軟體、應用程式和網路協議。它支持32位和64位硬體。Linux繼承了Unix以網路為核心的設計思想，是一個性能穩定的多用戶網路操作系統。

2.1 特性：

多用戶、多任務：Linux支持多用戶，各個用戶對於自己的文件設備有自己特殊的權利，保證了各用戶之間互不影響。多任務則是現在電腦最主要的一個特點，Linux可以使多個程式同時並獨立地運行。
良好的界面：Linux同時具有字元界面和圖形界面。在字元界面用戶可以通過鍵盤輸入相應的指令來進行操作。它同時也提供了類似Windows圖形界面的X-Window系統，用戶可以使用滑鼠對其進行操作。在X-Window環境中就和在Windows中相似，可以說是一個Linux版的Windows。
支持多種平臺：Linux可以運行在多種硬體平臺上，如具有x86、680x0、SPARC、Alpha等處理器的平臺。此外Linux還是一種嵌入式操作系統，可以運行在掌上電腦、機頂盒或游戲機上。2001年1月份發佈的Linux 2.4版內核已經能夠完全支持Intel 64位晶元架構。同時Linux也支持多處理器技術。多個處理器同時工作，使系統性能大大提高。
文件系統：包含純文本文件（ASCII）、二進位文件（binary）、數據格式的文件（data）。

　　3.Linux系統下進程的組織

3.0 標識符：

每個進程有進程標識符、用戶標識符、組標識符。

功能變數名稱	含義
Pid	進程標識符
Uid、gid	用戶標識符、組標識符
Euid、egid	有效用戶標識符、有效組標識符
Suid、sgid	備份用戶標識符、備份組標識符
Fsuid、fsgid	文件系統用戶標識符、文件系統組標識符

3.1 進程查看：

可以使用ps命令。它能顯示當前運行中進程的相關信息，包括進程的PID。
ps -aux   ##可以看到所有運行的程式與grep連用篩選

ps -a   ##顯示現行終端機下的所有程式（包括其他用戶的程式）

ps -u   ##以用戶為主的排序顯示（username）

ps -x   ##顯示所有程式（包括所有終端機下的）

3.2 進程創建：

fork（）：fork創建一個進程時，子進程只是完全複製父進程的資源，複製出來的子進程有自己的task_struct結構和pid,但卻複製父進程其它所有的資源。
```
 #include <sys/types.h> 
 #include <unistd.h> 

 pid_t fork(void); 
```
正確返回：在父進程中返回子進程的進程號，在子進程中返回0 ；錯誤返回：-1 。
vfolk（）：vfork系統調用不同於fork，用vfork創建的子進程與父進程共用地址空間，也就是說子進程完全運行在父進程的地址空間上，如果這時子進程修改了某個變數，這將影響到父進程。
```
 #include <sys/types.h> 
 #include <unistd.h>

 pid_t vfork(void);
```
正確返回：在父進程中返回子進程的進程號，在子進程中返回0 ；錯誤返回：-1 。
clone（）：fork()是全部複製，vfork()是共用記憶體，而clone() 是則可以將父進程資源有選擇地複製給子進程，而沒有複製的數據結構則通過指針的複製讓子進程共用，具體要複製哪些資源給子進程，由參數列表中的 clone_flags來決定。另外，clone()返回的是子進程的pid。
```
 #include <sched.h> 

 int clone(int (*fn)(void *), void *child_stack, int flags, void *arg); 
```
正確返回：返回所創建進程的PID，函數中的flags標誌用於設置創建子進程時的相關選項；錯誤返回：-１。

3.3 進程終止：

exit（）：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    printf("Using exit\n");
    printf("This is the content in buffer");
    exit(0);
}

//運行結果：
Using exit
This is the content in buffer

_exit（）：
```
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main()
{
        printf("Using exit\n");
        printf("This is the content in buffer");
        _exit(0);
}
//運行結果：
Using exit
```
exit和_exit函數都是用來終止進程的。當程式執行到exit和_exit時，進程會無條件的停止剩下的所有操作，清除包括PCB在內的各種數據結構，並終止本程式的運行。exit可輸出緩衝區數據，_exit不可輸出緩衝區數據。

abort（）：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    FILE *stream;
    if((stream = fopen("nofilehere", "r")) == NULL)
    {
         perror("Can not open");
         abort();
   }
   else
   {
        fclose(stream);
   }
   return 0;
}

abort()是使異常程式終止，同時發送SIGABRT信號給調用進程。

3.4 進程管理命令

ps： 'ps'是Linux 中最基礎的瀏覽系統中的進程的命令。能列出系統中運行的進程，包括進程號、命令、CPU使用量、記憶體使用量等。
pstree： linux中，每一個進程都是由其父進程創建的。此命令以可視化方式顯示進程，通過顯示進程的樹狀圖來展示進程間關係。
top: ‘top’是一個更加有用的命令，可以監視系統中不同的進程所使用的資源。它提供實時的系統狀態信息。顯示進程的數據包括 PID、進程屬主、優先順序、%CPU、%memory等。可以使用這些顯示指示出資源使用量。
htop: htop與top很類似，但是htop是互動式的文本模式的進程查看器。它通過文字圖形化地顯示每一個進程的CPU和記憶體使用量、swap使用量。使用上下游標鍵選擇進程，F7和F8改變優先順序，F9殺死進程。Htop不是系統預設安裝的，所以需要額外安裝。
nice: 通過nice命令的幫助，用戶可以設置和改變進程的優先順序。提高一個進程的優先順序，內核會分配更多CPU時間片給這個進程。預設情況下，進程以0的優先順序啟動。進程優先順序可以通過top命令顯示的NI（nice value）列查看。
renice: renice命令類似nice命令。使用這個命令可以改變正在運行的進程優先值。註意，用戶只能改變屬於他們自己的進程的優先值。
kill: 這個命令用於發送信號來結束進程。如果一個進程沒有響應殺死命令，這也許就需要強制殺死，使用-9參數來執行。
ulimit: 該命令用於控制系統資源在shell和進程上的分配量。對於系統管理員是最有用的，可以管理重度使用和存在性能問題的系統。限制資源大小可以確保重要進程持續運行，其他進程不會占用過多資源。
w: w 提供當前登錄的用戶及其正在執行的進程的信息。顯示信息頭包含信息，如當前時間、系統運行時長、登錄用戶總數、過去的1，5，15分鐘內的負載均衡數。
pgrep: pgrep的意思是"進程號全局正則匹配輸出"。該命令掃描當前運行進程，然後按照命令匹配條件列出匹配結果到標準輸出。對於通過名字檢索進程號是很有用。
fg , bg：有時，命令需要很長的時間才能執行完成。對於這種情況，我們使用‘bg’命令可以將任務放在後臺執行，而用‘fg’可以調到前臺來使用。
ipcs: ipcs命令報告進程間通信設施狀態。（共用記憶體，信號量和消息隊列）；用-p參數聯合-m、-s或-q使用，可以獲得相關的進程間通信的進程ID。

　　4.Linux下進程的狀態

4.0 六種狀態：

R (TASK_RUNNING)，可執行狀態。
S (TASK_INTERRUPTIBLE)，可中斷的睡眠狀態。
D (TASK_UNINTERRUPTIBLE)，不可中斷的睡眠狀態。
T (TASK_STOPPED or TASK_TRACED)，暫停狀態或跟蹤狀態。
Z (TASK_DEAD - EXIT_ZOMBIE)，退出狀態，進程成為僵屍進程。
X (TASK_DEAD - EXIT_DEAD)，退出狀態，進程即將被銷毀。

4.1 狀態轉換圖：

　　5.Linux下進程的調度

5.0 簡介：

Linux進程調度採用的是搶占式多任務處理，所以進程之間的掛起和繼續運行無需彼此之間的協作。
Linux在進行進程調度的時候把進程分為兩種：1.普通進程；2.實時進程；實時進程的優先順序永遠比普通進程的優先順序高。

5.1 進程調度策略：

SCHED_OTHER 分時調度策略。
SCHED_FIFO實時調度策略，先到先服務。
SCHED_RR實時調度策略，時間片輪轉。

5.2 進程優先順序：

使用nice值：越大的nice值意味著更低的優先順序。 (-19 ~ 20之間)
實時優先順序：可配置，越高意味著進程優先順序越高。
時間片：Linux中並不是以固定的時間值(如10ms)來分配時間片的，而是將處理器的使用比作為“時間片”劃分給進程。

5.3 O(1)調度演算法：

演算法介紹：在Linux2.6版中，O(1)調度被採用，它是對非實時進程進行調度的一種調度演算法。　
數據結構：在O(1)調度中，要問最重要的數據結構是運行隊列。運行隊列描繪了進程隊列的結構，在內核源碼中用runqueue結構體表示。
```
struct runqueue 
{   unsigned long nr_running; 
    task_t *curr;
    prio_array_t *active,*expired,arrays[2]; 
};
```

優先順序數組:O(1)演算法的另一個核心數據結構即為prio_array結構體。該結構體中有一個用來表示進程動態優先順序的數組queue，它包含了每一種優先順序進程所形成的鏈表。

#define
 MAX_USER_RT_PRIO        100
#define
 MAX_RT_PRIO             MAX_USER_RT_PRIO
#define
 MAX_PRIO                (MAX_RT_PRIO + 40)
typedef struct prio_array
 prio_array_t;
struct prio_array
 {
      unsigned int nr_active;
      unsigned long bitmap[BITMAP_SIZE];
      struct list_head
 queue[MAX_PRIO];
};

靜態優先順序和動態優先順序：進程有兩個優先順序,一個是靜態優先順序,一個是動態優先順序.靜態優先順序是用來計算進程運行的時間片長度的,動態優先順序是在調度器進行調度時用到的,調度器每次都選取動態優先順序最高的進程運行. 靜態優先順序的計算:
```
nice值和靜態優先順序之間的關係是：靜態優先順序=100+nice+20
而nice值的範圍是-20～19，所以普通進程的靜態優先順序的範圍是100～139
```
進程運行的時間片長度的計算:
```
靜態優先順序<120，基本時間片=max((140-靜態優先順序)*20, MIN_TIMESLICE)
靜態優先順序>=120，基本時間片=max((140-靜態優先順序)*5, MIN_TIMESLICE)
```
其中MIN_TIMESLICE為系統規定的最小時間片.從該計算公式可以看出,靜態優先順序越高（值越低),進程得到的時間片越長。動態優先順序的計算:
```
動態優先順序=max(100 , min(靜態優先順序 – bonus + 5 , 139))
```
從上面看出,動態優先順序的生成是以靜態優先順序為基礎,再加上相應的懲罰或獎勵(bonus).這個bonus並不是隨機的產生,而是根據進程過去的平均睡眠時間做相應的懲罰或獎勵.交互性強的進程會得到調度程式的獎勵（bonus為正）,而那些一直霸占CPU的進程會得到相應的懲罰（bonus為負）。
調度演算法：Linux2.4版本的內核調度演算法理解起來簡單：在每次進程切換時，內核依次掃描就緒隊列上的每一個進程，計算每個進程的優先順序，再選擇出優先順序最高的進程來運行；儘管這個演算法理解簡單，但是它花費在選擇優先順序最高進程上的時間卻不容忽視。系統中可運行的進程越多，花費的時間就越大，時間複雜度為O(n)。偽代碼如下：
```
for (系統中的每個進程) {
    重新計算時間片;
    重新計算優先順序;
}
```
而2.6內核所採用的O(1)演算法則很好的解決了這個問題，該演算法可以在恆定的時間內為每個進程重新分配好時間片，而且在恆定的時間內可以選取一個最高優先順序的進程，重要的是這兩個過程都與系統中可運行的進程數無關，這也正是該演算法取名為O(1)的緣故。
時間片：O(1)演算法採用過期進程數組和活躍進程數組解決以往調度演算法所帶來的O(n)複雜度問題。過期數組中的進程都已經用完了時間片，而活躍數組的進程還擁有時間片。當一個進程用完自己的時間片後，它就被移動到過期進程數組中，同時這個過期進程在被移動之前就已經計算好了新的時間片。可以看到O(1)調度演算法是採用分散計算時間片的方法，並不像以往演算法中集中為所有可運行進程重新計算時間片。當活躍進程數組中沒有任何進程時，說明此時所有可運行的進程都用完了自己的時間片。那麼此時只需要交換一下兩個數組即可將過期進程切換為活躍進程，進而繼續被調度程式所調度。兩個數組之間的切換其實就是指針之間的交換，因此花費的時間是恆定的。下麵的代碼說明瞭兩個數組之間的交換：
```
struct prop_array *array = rq->active;
if (array->nr_active != 0) {
    rq->active = rq->expired;
    rq->expired = array;
}
```
通過分散計算時間片、交換過期和活躍兩個進程集合的方法可以使得O(1)演算法在恆定的時間內為每個進程重新計算好時間片。

5.4 完全公平調度演算法（CFS）：

演算法簡介：從Linux2.6.23開始，考慮到O(1)調度的一些不足以及公平性方面的缺陷，所以改用完全公平調度（CFS）演算法。

權重：普通進程的優先順序為100～139，並且優先順序是可以通過nice值修改的，nice值的範圍為-20～19。而在CFS調度中，進程的權重與優先順序有關，優先順序越高，權重越大。並且優先順序到權重的轉換有一個經驗公式，經驗公式如下所示：

static const int prio_to_weight[40] = {
     /* -20 */     88761,     71755,     56483,     46273,     36291,
     /* -15 */     29154,     23254,     18705,     14949,     11916,
     /* -10 */      9548,      7620,      6100,      4904,      3906,
     /*  -5 */      3121,      2501,      1991,      1586,      1277,
     /*   0 */      1024,       820,       655,       526,       423,
     /*   5 */       335,       272,       215,       172,       137,
     /*  10 */       110,        87,        70,        56,        45,
     /*  15 */        36,        29,        23,        18,        15,
};548, 7620, 6100, 4904, 3906,

可以看到, nice值越小, 進程的權重越大。

CFS調度器的一個調度周期值是固定的, 由sysctl_sched_latency變數保存.

一個進程在一個調度周期中的運行時間為:

分配給進程的運行時間 = 調度周期 * 進程權重 / 所有進程權重之和

可以看到, 進程的權重越大, 分到的運行時間越多。

虛擬運行時間：為了實現公平，開發者將虛擬運行時間引入到CFS調度中來取代優先順序對於選擇進程運行的決定地位，在內核源碼中用vruntime欄位來表示虛擬運行時間。並且在CFS中主要有兩個要素可以決定進程的虛擬運行時間，它們分別是進程的權重和進程實際運行的時間。調度器總是調度虛擬運行時間最小的進程，並且在每一次時鐘中斷到來時，內核都要重新計算當前進程的虛擬運行時間，計算公式如下：
```
vruntime = 進程在一個調度周期內的實際運行時間 * NICE_0_LOAD / 進程權重
         = (調度周期 * 進程權重 / 所有進程總權重) * NICE_0_LOAD / 進程權重 
         = 調度周期 * NICE_0_LOAD / 所有進程總權重 
```
NICE_0_LOAD = 1024, 表示nice值為0的進程權重。

由上述公式可以看出正在運行的進程的虛擬運行時間隨著運行時間的增長而增長，當它的虛擬運行時間不是可運行態進程中的最小值時它就會被其它可運行態進程搶占，而且能夠看出虛擬運行時間與當前進程運行的時間、當前進程的權重的關係是：虛擬運行時間與當前進程運行的時間成正比，與當前進程的權重成反比。
由此可見，當一個進程的優先順序越高，運行的時間越少時，這個進程的虛擬運行時間就越小，此進程就越應該被調度執行。
紅黑樹：相比於O(1)調度，CFS調度沒有用運行隊列來維護可運行態進程，而是用紅黑樹來組織普通進程。紅黑樹本質上是一顆二叉查找樹，它具有以下5個特點：
（1）每個葉結點都是空結點，並且它們是黑色的；
（2）根結點是黑色的；
（3）紅色結點的子結點必定是黑色的；
（4）對於任意結點而言，其到葉節點的每條路徑上的黑色結點的數目都相同；
（5）每個結點不是黑色就是紅色。
這些特點決定了紅黑樹是自平衡的，雖然紅黑樹沒有達到恆定O(1)的時間複雜度但是它最差的時間複雜度也為O(logn)，這就決定了它可以在插入和刪除等操作上表現得非常高效。
CFS使用的紅黑樹是以時間為順序的，它的結點由調度實體來描述，關於調度實體的概念將在下一節組調度中介紹，而進程的虛擬運行時間和權重也存放在這個結構中，下圖描繪了CFS中紅黑樹的結構。

　　　　內核通過紅黑樹來對虛擬運行時間進行排序，紅黑樹的最左側結點的虛擬運行時間最少，所以該結點所表示的進程將是下一個要被調度的進程。

組調度：Linux系統中不僅有進程而且也有進程組，所以在CFS中支持對進程組的調度，即CFS組調度。因為組中進程的task_struct不能完成對所屬進程組的調度，所以為瞭解決這個問題，CFS引入了調度實體，也就是一個調度單位的概念，在內核源碼中用sched_entity欄位表示。進程和進程組的與調度相關的信息都被保存在調度實體中，比如虛擬運行時間和權重。當內核關閉組調度的使用時，調度實體就等同於進程。 CFS引入組調度是為了將以進程為單位的調度擴展到以用戶為單位的調度，即將進程的歸屬按用戶劃分，每個用戶擁有一個進程組，組中有一些進程。當進行組調度時，先選擇用戶，然後才選擇用戶所擁有進程組中的某一個進程。這樣的話每個用戶的進程組被調度的機率相同，用戶享有相同比例的CPU時間，防止了當A用戶的進程的權重遠高於B用戶的進程的權重時，B用戶的進程只能等A用戶的進程全部運行完了之後才能運行的情況，這樣體現了用戶間的公平性。

　　6.淺談Linux進程模型

進程作為操作系統重要的核心之一，其發展形成經過了上萬名高級程式員之手，千萬級別的代碼量，可見其工程的浩大。在不斷地改革創新之後，進程模型漸臻完美，然而仍存在不足，例如：程式併發執行時付出了巨大的時空開銷，每個進程在進行切換時身上帶了過多的“累贅”導致系統效率降低，故而引入了線程。
進程模型建立在大量的數據結構基礎上，不斷地翻陳出新，如由早期的Linux 2.1版本的O(n)調度器到 Linux 2.6版本的O(1)調度器再到CFS調度器。
進程模型作為人類的高智慧集中產物，基於人類科學，在硬體的基礎上實現軟體層面的諸多功能，其深奧的原理仍有待我們進一步學習探究。

　 7.參考鏈接