Linux 的行程管理

相關主題

行程結構

Linux 中的行程 (Process) 被稱為任務 (Task),其資料結構是一個稱為 task_struct 的 C 語言結構,該結構所記錄的欄位相當多,在 Linux 2.6.29.4 版當中光是該結構的宣告就占了 306 行的程式碼,範例 1 顯示了該結構的開頭與結束部分,由此可見要實作一個作業系統是相當不容易的工程。

範例 1 Linux 中的 Task 之結構

行號    Linux 2.6.29.4 版核心原始碼 include/linux/sched.h 檔案
…    …
1115    struct task_struct {
1116    volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
1117    void *stack;
1118    atomic_t usage;
1119    unsigned int flags; /* per process flags, defined below */
1120    unsigned int ptrace;
…    …
1263    /* CPU-specific state of this task */
1264    struct thread_struct thread;
1265    /* filesystem information */
1266    struct fs_struct *fs;
1267    /* open file information */
1268    struct files_struct *files;
1269    /* namespaces */
1270    struct nsproxy *nsproxy;
1271    /* signal handlers */
1272    struct signal_struct *signal;
1273    struct sighand_struct *sighand;
…    …
1417    #ifdef CONFIG_TRACING
1418    /* state flags for use by tracers */
1419    unsigned long trace;
1420    #endif
1421    };
…    …

Linux 的行程結構中包含了一個 thread 欄位 (1264 行),該欄位用來儲存與 CPU 相關的暫存器、分段表等資訊,由於暫存器資訊是與處理器密切相關的,所以每一種 CPU 都會擁有不同的執行緒結構,IA32 (x86) 的thread_struct之程式片段如範例 10.3所示。

範例 2. Linux 中的IA32 (x86) 處理器的Thread 之結構

行號    Linux 2.6.29.4 版核心原始碼 arch/x86/include/asm/processor.h 檔案
…    …
391    struct thread_struct {
392    /* Cached TLS descriptors: */
393    struct desc_struct tls_array[GDT_ENTRY_TLS_ENTRIES];
394    unsigned long sp0;
395    unsigned long sp;
…    …

行程狀態

Linux 行程的狀態有 Running, Interruptible, Uninterruptible, Zombie, Stopped 等五種,但後來又增加了 Traced, EXIT_DEAD, TASK_DEAD, TASK_WAKEKILL 等四種,形成了九種狀態 (2.6.29.4 版),如範例 10.4所示。

範例 3. Linux 中的行程狀態

行號    Linux 2.6.29.4 版核心原始碼 include/linux/sched.h 檔案
…    …
174    #define TASK_RUNNING 0
175    #define TASK_INTERRUPTIBLE 1
176    #define TASK_UNINTERRUPTIBLE 2
177    #define __TASK_STOPPED 4
178    #define __TASK_TRACED 8
179    /* in tsk->exit_state */
180    #define EXIT_ZOMBIE 16
181    #define EXIT_DEAD 32
182    /* in tsk->state again */
183    #define TASK_DEAD 64
184    #define TASK_WAKEKILL 128
…    …

行程切換

行程切換 (內文切換) 是與處理器密切相關的程式碼,每個處理器的實作方式均有相當大的差異,但基本原理都是將上一個行程 (prev, 以下稱為舊行程) 的暫存器保存後,再將程式計數器設定給下一個行程 (next, 以下稱為新行程)。在 IA32 (x86) 的處理器中,Linux 的行程切換程式碼 如範例 4 所示,該行程切換函數 switch_to(prev, next, last) 是一個內嵌於 C 語言的組合語言巨集,採用 GNU 的內嵌組合語言語法 。

首先,switch_to 最外層是一個 do { … } while (0) 的迴圈,這個語法很奇怪,因為該迴圈根本永遠都只會執行一次,那又為何要用迴圈呢?這純粹只是為了要把中間的組合語言用區塊結構 {…} 包起來而已,但卻很容易誤導讀者,以為那是一個無窮迴圈 。

範例 4. Linux在 IA32 (x86) 處理器上的行程切換程式碼

行號 Linux 2.6.29.4 檔案 arch/x86/include/asm/system.h
…    …
30    #define switch_to(prev, next, last) \
31    do {\
32    /* \
33     * Context-switching clobbers all registers, so we clobber\
34     * them explicitly, via unused output variables.\
35     * (EAX and EBP is not listed because EBP is saved/restored \
36     * explicitly for wchan access and EAX is the return value of \
37     * __switch_to()) \
38     */ \
39    unsigned long ebx, ecx, edx, esi, edi; \
40    \
41    asm volatile("pushfl\n\t" /* save flags */ \
42    "pushl %%ebp\n\t" /* save EBP */ \
43    "movl %%esp,%[prev_sp]\n\t"/* save ESP */ \
44    "movl %[next_sp],%%esp\n\t"/* restore ESP */ \
45    "movl $1f,%[prev_ip]\n\t" /* save EIP */ \
46    "pushl %[next_ip]\n\t" /* restore EIP */ \
47    "jmp __switch_to\n" /* regparm call */ \
48    "1:\t" \
49    "popl %%ebp\n\t" /* restore EBP */ \
50    "popfl\n" /* restore flags */ \
51    \
52    /* output parameters */ \
53    [prev_sp] "=m" (prev->thread.sp), \
54    [prev_ip] "=m" (prev->thread.ip), \
55    "=a" (last), \
56    \
57    /* clobbered output registers: */ \
58    "=b" (ebx), "=c" (ecx), "=d" (edx), \
59    "=S" (esi), "=D" (edi) \
60    \
61    /* input parameters: */ \
62    : [next_sp]  "m" (next->thread.sp), \
63     [next_ip]  "m" (next->thread.ip), \
64    \
65    /* regparm parameters for __switch_to(): */ \
66    [prev]     "a" (prev), \
67    [next]     "d" (next) \
68    \
69    : /* reloaded segment registers */ \
70    "memory"); \
71    } while (0)
…    …

第41行開始才是行程切換的動作,指令pushfl 用來儲存旗標暫存器到堆疊中,pushl %%ebp 用來儲存框架暫存器 (ebp) 到堆疊中,movl %%esp, %[prev_sp] 則用來儲存舊行程的堆疊暫存器 (esp) 到 (prev->thread.sp) 欄位中,而 pushl %[next_sp], %%esp 則是將新行程的堆疊暫存器 (next->thread.sp) 取出後,放到CPU的esp暫存器中,於是建構好新行程的堆疊環境。接著,第45行的movl $1f, %[prev_ip] 將標記 1 的位址放入舊行程的 prev->thread.ip 欄位中。接著46行用指令pushl %[next_ip] 將新行程的程式計數器 next->thread.ip 推入堆疊中,然後利用指令jmp __switch_to跳入C語言的 switch_to() 函數 中,當該函數的返回指令被執行時,將會發生一個奇妙的結果。

由於 switch_to() 函數是一個C語言函數,原本應該被其他C語言函數呼叫的,呼叫前原本上層函數會先將下一個指令的位址存入堆疊中,然後才進行呼叫。C語言函數在返回前會從堆疊中取出返回點,以返回上一層函數繼續執行 。雖然我們是利用組合語言指令 jmp __switch_to 跳入該函數的,但C語言的編譯器仍然會以同樣的方式編譯,於是返回時仍然會從堆疊中取出 pushl %[next_ip] 指令所推入的位址,因而在 switch_to() 函數返回時,就會將程式計數器設為 next->thread.ip,於是透過函數返回的過程,間接的完成了行程切換的動作。

既然新行程已經在 switch_to() 函數返回時就開始執行了,那麼內文切換的動作不就已經完成了嗎?既然如此為何又需要第 49-50 兩行的程式呢?我們必須進一步回答這個問題。

第45行之所以將標記1放入prev->thread.ip中,是為了讓舊行程在下次被喚醒時,可以回到標記 1 的位置。當下次舊行程被喚醒後,就會從標記 1 的位址開始執行,舊行程可以利用第49-50行的popl %%ebp; popfl 兩個指令,恢復其 ebp (框架指標) 與旗標暫存器,然後再度透過 switch_to(),切換回舊行程 (只不過這次舊行程變成了函數switch_to(prev, next, last) 中的 next 角色,不再是『舊行程』了。

或許我們可以說 switch_to() 函數其實並不負責切換行程,因為該函數會將處理器中各種需要保存的值存入舊行程 prev 的 task_struct 結構中,以便下次 prev 行程被喚醒前可以回存這些暫存器值,其實並沒有切換或執行新行程的功能,但因為 jmp __switch_to 指令前的 pushl %[next_ip] 指令,導致該函數在返回時順便做了行程切換的動作,這種隱含性是作業系統設計時一種相當弔詭的技巧,也是學習 Linux 時對程式人員最大的挑戰之一。

排程

解說完行程切換的原理後,我們就可以來看看排程系統了。Linux 採用的排程機制較為複雜,該排程式建構在一個稱為 goodness 的行程 (或執行緒) 評估值上,goodness 是一個從 0 到 1999 之間的整數。一般執行緒的 goodness 小於 1000,但即時執行緒的 goodness 則會從 1000 開始,因此保證了任何即時執行緒的 goodness 都會高於一般執行緒。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>

int spawn(char *prog, char **arg_list) {    // Spawn為生育的意思
  pid_t child;    
  child = fork();     // 用fork()函數分枝出子行程
  if (child != 0) {     // 如果不成功
    return child;     //   傳回失敗的行程代碼
  } else {     // 否則
    execvp(prog, arg_list);     //   將 prog 參數所指定的
    fprintf(stderr, "spawn error\n");     // 程式載入到子行程中
    return -1;
  }
}

int main() {     // 主程式開始
  char *arg_list[] = { "ls", "-l", "/etc", NULL };    // ls -l /etc
  spawn("ls", arg_list);     // 開始分支
  printf("The end of program.\n");     // 印出主程式結束訊息
  return 0;
}

執行過程與結果

$ gcc fork.c -o fork

$ ./fork
The end of program.

$ total 94
-rwxr-x---  1 ccc Users  2810 Jun 13  2008 DIR_COLORS
drwxrwx---+ 2 ccc Users     0 Oct  7  2008 alternatives
-rwxr-x---  1 ccc Users    28 Jun 13  2008 bash.bashrc
drwxrwx---+ 4 ccc Users     0 Oct  7  2008 defaults
-rw-rw-rw-  1 ccc Users   716 Oct  7  2008 group
….

執行緒

POSIX標準中支援的執行緒函式庫稱為 pthread,我們可以透過 pthread 結構與 pthread_create() 函數執行某個函數指標,以建立新的執行緒。範例 6 顯示了一個利用 pthread 建立兩個執行緒,分別不斷印出 George 與 Mary 的程式。該程式中總共有三個執行主體,第一個是 print_george()、第二個是 print_mary()、第三個是主程式本身。由於每隔 1 秒印一次 George ,但每隔 0.5 秒就印一次 Mary,因此執行結果會以 George, Mary, George, George,Mary 的形式印出。

範例 6 利用pthread 函式庫建立執行緒的範例

#include <pthread.h>     // 引用 pthread 函式庫
#include <stdio.h>    

void *print_george(void *argu) {    // 每隔一秒鐘印出一次 George 的函數
  while (1) {    
    printf("George\n");    
    sleep(1);    
  }    
  return NULL;    
}    

void *print_mary(void *argu) {     // 每隔一秒鐘印出一次 Mary 的函數
  while (1) {    
    printf("Mary\n");    
    sleep(2);    
  }    
  return NULL;    
}    

int main() {     // 主程式開始
  pthread_t thread1, thread2;     // 宣告兩個執行緒
  pthread_create(&thread1, NULL, &print_george, NULL);    // 執行緒 print_george
  pthread_create(&thread2, NULL, &print_mary, NULL);    // 執行緒 print_mary
  while (1) {     // 主程式每隔一秒鐘
    printf("----------------\n");    // 就印出分隔行
    sleep(1);     // 停止一秒鐘
  }    
  return 0;    
}

執行過程與結果

$ gcc thread.c -o thread

$ ./thread
George
Mary
-------------------------
George
-------------------------
George
Mary
-------------------------
George
-------------------------
…
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License