深入分析任務(wù)切換與堆棧 by Liu Wanli

關(guān)鍵字：時間中斷、任務(wù)切換、堆棧、LINUX0.01

引言：

任務(wù)切換與堆棧的關(guān)系怎樣？很多朋友可能不知道她們之間有什么關(guān)系，還有一些朋友可能認為他們之間不會有太大的關(guān)系（文獻4）。而我認為：任務(wù)切換跟堆棧有著密切的關(guān)系！下面是我對它們之間關(guān)系進行的探討，這里的任務(wù)切換我指的是發(fā)生時間中斷時進行強制調(diào)度發(fā)生的任務(wù)切換，所以下面考慮堆棧時我是從中斷開始探討的。當(dāng)然，我在進行這方面分析的時候，也愈感它們的復(fù)雜性，錯誤之處在所難免，望各位朋友多多指正。建議讀者水平：* * *


一、時間中斷。

假設(shè)一個進程在用戶空間執(zhí)行時（這時CPL=3），發(fā)生了時間中斷。這時的中斷處理過程為（文獻1：P438）：
1、根據(jù)中斷向量號找到中斷門描述符；
2、從描述符中分解出選擇子、偏移量、屬性字段并進行相應(yīng)的特權(quán)檢查；
3、根據(jù)描述符類型轉(zhuǎn)入相應(yīng)中斷處理程序中去執(zhí)行。
好象太膚淺了一些？再看看（文獻1：P439圖10.20）：
1、選擇子為空？no繼續(xù)；
2、取得對應(yīng)描述符；（描述符中DPL屬性應(yīng)該為0，文獻3中斷向量初始化部分）
3、存儲段描述符？yes繼續(xù)；
4、非一致代碼段且DPL<CPL且段存在？yes繼續(xù)；根據(jù)假設(shè)CPL=3，DPL=0，所以到5！
5、切換成內(nèi)層堆棧！
如何切換？？因為一個進程有用戶空間堆棧和系統(tǒng)空間（也叫內(nèi)核空間）堆棧，用戶空間堆棧在哪兒我不管，它應(yīng)該是由該進程的任務(wù)狀態(tài)段TSS中SS2指定，SS0指定系統(tǒng)空間堆棧，它和該進程任務(wù)結(jié)構(gòu)task_struct共占一頁空間（見文獻3:sched.c）。所以這里的切換成內(nèi)層堆棧應(yīng)該是將該進程的TSS中SS0的值賦給SS寄存器。
6、使RPL=0；
7、把描述符裝入CS；
8、入口偏移越界？no繼續(xù)；
9、EFLAG、CS、EIP入棧；呵，開始棧的改變了喲！
10、TF=0、NT=0、IF=0；這里考慮的是中斷門。
11、轉(zhuǎn)入處理程序。

別急，先看看現(xiàn)在的堆棧情況：

| 外層EIP |
| 外層CS |
| EFLAG |
| 外層ESP |
| 外層SS |
-----------
這個棧在什么地方呢？這相當(dāng)重要！這是在當(dāng)初切換至內(nèi)層堆棧時進行的，即已經(jīng)到了當(dāng)前進程的系統(tǒng)空間堆棧，也就是跟task_struct共占一頁的那個堆棧。而這里保存的就是該進程在用戶空間的堆棧和代碼信息，以便中斷完成后恢復(fù)進程執(zhí)行。

二、中斷處理程序。
這里指的是時間中斷。（文獻3：system_call.c: timer_interrupt:）

timer_interrupt:
1. push %ds
2. push %es
3. push %fs
4. pushl %edx
5. pushl %ecx
6. pushl %ebx
7. pushl %eax
8. movl $0x10,%eax
9. mov %ax,%ds
10. mov %ax,%es
11. movl $0x17,%eax
12. mov %ax,%fs
13. incl jiffies
14. movb $0x20,%al
15. outb %al,$0x20
16. movl CS(%esp),%eax
17. andl $3,%eax
18. pushl %eax
19. call do_timer
20. andl $4,%esp
21. jmp ret_from_sys_call

1-7行為壓棧操作，這是我們所關(guān)心的！16-18即是將CPL（CPL=CS&3）壓棧，目的是用于do_tiemr(long cpl)函數(shù)。那么在執(zhí)行到do_timer里面時的堆棧怎么樣呢？看看：


|返回地址 |
-----------
| CPL |
| eax |
| ebx |
| ecx |
| edx |
| fs |
| es |
| ds |
-----------
| 外層EIP |
| 外層CS |
| EFLAG |
| 外層ESP |
| 外層SS |
-----------

上面的返回地址當(dāng)然就是調(diào)用do_timer后的那條語句，即20行的andl $4,%esp語句。那么是不是do_timer函數(shù)執(zhí)行完就返回到這兒呢，也是，當(dāng)然要復(fù)雜得多，因為在do_timer()函數(shù)中調(diào)用了schedule()并且發(fā)生了任務(wù)切換！哎，好麻煩，也不知道什么時候才能返回到這兒來呢，還是一步一步來看吧。

三、do_timer()（文獻3：sched.c: do_timer()）

void do_timer(long cpl)
{
...
if ((--current->counter)>0) return;
current->counter=0;
if(!cpl)return;
schedule();
}

省略號為無關(guān)緊要的兩條語句，進行進程的計時。如果時間片沒有用完(counter>0)或CPL為0，不發(fā)生調(diào)度直接返回，當(dāng)然這里也不是就直接返回到以前執(zhí)行的進程空間，而是返回到do_timer()中，注意開始的返回地址，然后再通過iret指令從中斷處理返回到進程中去。當(dāng)然，根據(jù)我們的假設(shè)，這兒CPL應(yīng)該為3，因為是在用戶空間發(fā)生中斷的。我們要從最復(fù)雜的情況來討論這個問題。好了，就讓我們進入到中心點吧，請進schedule()。

四、schedule()。 （文獻3：sched.c: schedule()）

void schedule(void )
{
int next;
...
switch_to(next);
}

呵，這里我又省略了幾句代碼，它執(zhí)行的是調(diào)度算法，即從所有狀態(tài)為‘運行’的進程中找出下一個要執(zhí)行的進程，然后將編號賦給next。進行切換！

switch_to()是一個宏，它在（文獻3： sched.h）中定義：

#define switch_to(n) { \
struct (long a,b;} __tmp; \
__asm__("cmpl %%ecx,current \n\t" \
"je 1f\n\t" \
"xchgl %%ecx, current\n\t" \
"movw %%dx, %1\n\t" \
"ljmp *%0\n\t" \
"cmpl %%ecx, %2\n\t" \
"jne 1f\n\t" \
"clts\n" \
"1:" \
::"m" (*&__tmp.a), "m" (*&__tmp.b), \
"m" (last_task_used_math),"d" _TSS(n), "c" ((long) task[n])); \
}

這是任務(wù)切換的關(guān)鍵代碼，原理是直接通過TSS來進行任務(wù)的切換（文獻1：P420）。那我就將這段關(guān)鍵代碼逐行解說一下吧。cmpl %%ecx, current，比較任務(wù)n是不是當(dāng)前進程，如果是當(dāng)然就不用切換了，直接結(jié)束schedule()。xchgl %%ecx,current，current指針指向任務(wù)n的任務(wù)結(jié)構(gòu)，ecx寄存器保存當(dāng)前進程的任務(wù)結(jié)構(gòu)指針。movw %%dx, %1， 使__tmp.b=‘GDT中第n個任務(wù)的TSS選擇子’，注意_TSS(n)是求選擇子的宏！ljmp *%0，這句代碼就是真正的任務(wù)切換羅， AT&T語法的ljmp相當(dāng)于INTEL的jmp far SECTION:OFFSET指令格式，它的絕對地址前加*號。這里引用（文獻1：P420）一段話：當(dāng)段間轉(zhuǎn)移指令JMP所含指針的選擇子指示一個可用任務(wù)狀態(tài)段TSS描述符時，正常情況下就發(fā)生從當(dāng)前任務(wù)到由該可用任務(wù)的切換。目標任務(wù)的入口點由目標任務(wù)TSS內(nèi)的CS和EIP字段所規(guī)定的指針確定，這樣的JMP指令內(nèi)的偏移被丟棄。再具體的任務(wù)切換你也許得翻翻（文獻1：P421），這里我只講有關(guān)堆棧的處理，那就是把寄存器現(xiàn)場保存到當(dāng)前任務(wù)的TSS。把通用寄存器、段寄存器、EIP及EFLAGS的當(dāng)前值保存到當(dāng)前的TSS中。保存的EIP的值是返回地址，指向引起任務(wù)切換指令的下一條指令；恢復(fù)目標任務(wù)的寄存器現(xiàn)場，根據(jù)保存在TSS中的內(nèi)容恢復(fù)各通用寄存器、段寄存器、EFLAG、EIP。好了，基本概念就引用這么多，那么，剛才提到的進程馬上要被切換出去了，它保存TSS中EIP是什么呢？顯然，根據(jù)剛才的分析應(yīng)該是cmpl %%ecx, %2這條指令。這意味著什么呢？這就是說，如果下次這個任務(wù)要被切換成運行狀態(tài)時，它將從cmpl %%ecx, %2這條指令開始執(zhí)行！那么，由彼任務(wù)推到此任務(wù)，也就是說我們切換至任務(wù)next時，它也是從這條指令開始執(zhí)行的！于是我們進入到任務(wù)next的堆?？臻g，并開始執(zhí)行，但由于任務(wù)next和當(dāng)前的任務(wù)有著相同的堆棧路徑（這和LINUX中的內(nèi)核控制路徑是不是一回事呢？），所以我們還是引用當(dāng)前的堆棧來繼續(xù)分析。
哦，有點糊涂了，好象是。休息一下，再參考一下（文獻2：上冊P373）。專家也是這樣說的;)
要不，我們這么理解，剛才被中斷的進程發(fā)生了強制調(diào)度，且也發(fā)生了任務(wù)切換，只不過是切換到它自己，實際上不是喲。好吧，JMP成功，開始執(zhí)行。

五、轉(zhuǎn)折點，從schedule()返回。

cmpl %%ecx, %2；jne 1f; clts;1: 這幾句是與協(xié)處理器有關(guān)，還有TS標志，我們就直接到1：吧，開始從schedule()返回，注意switch_to()是宏，它在schedule()末端。返回到哪兒去了呢？跟蹤一下，看看上面的堆棧示意圖，返回地址就是調(diào)用do_timer后的那條語句，
addl $4, %esp
jmp ret_from_sys_call
這兒esp加4就是把堆棧中的CPL去掉，因為我們不用了，跳轉(zhuǎn)到ret_from_sys_call。哦，剩下的處理與系統(tǒng)調(diào)用返回共用代碼。

六、ret_from_sys_call （文獻3，kernel/system_call.s）
先看看我們的焦點，堆棧怎么樣了呢？

| eax |
| ebx |
| ecx |
| edx |
| fs |
| es |
| ds |
-----------
| 外層EIP |
| 外層CS |
| EFLAG |
| 外層ESP |
| 外層SS |
-----------

ret_from_sys_call:
movel current, %eax
cmpl task, %eax
je 3f
movl CS(%esp), %ebx
testl $3, %ebx
je 3f
cmpw $0x17, OLDSS(%esp)
jne 3f
2:
....
3:
popl %eax
popl %ebx
popl %ecx
popl %edx
pop %fs
pop %es
pop %ds
iret

2標號處我省略了一些有關(guān)信號及其它一些處理。讓我們分析一下，如果當(dāng)前任務(wù)是0號進程，或是任務(wù)先前的CPL為3（即用戶態(tài)），或是任務(wù)先前的堆棧段為LDT中指定的堆棧，JMP到3標號處。由先前的假設(shè)可知，此任務(wù)的CPL為3，那就跳吧。把eax, ebc, ecx, edx, fs, es, ds寄存器從堆棧中恢復(fù)出來。
現(xiàn)在堆棧如下：

| 外層EIP |
| 外層CS |
| EFLAG |
| 外層ESP |
| 外層SS |
-----------
記得我們還有最后一條語句喲，iret。這條指令大家想必已經(jīng)很熟悉了，它恢復(fù)EIP、CS、EFLAG、ESP、SS。記得不，這是不是已經(jīng)恢復(fù)到了最初的時間中斷時進程被中斷的那一刻？恭喜！你終于可以繼續(xù)做你需要做的事情了！小心，還有下一個時間中斷，哦，你不怕？因為它不會影響你的連貫性。

結(jié)束語：
我們走過了一段艱辛的歷程，但我們走的是一段近乎直線的路徑，并沒有分析到其它各個方面的情況。不過我相信，通過這段路程，會讓我們對于任務(wù)切換機制有一個更深入的認識。希望對大家有所幫助，這也是我寫出來與大家分享的緣故。

參考文獻：
1、80X86匯編語言程序設(shè)計教程 楊季文編著 清華大學(xué)出版社
2、LINUX內(nèi)核源代碼情景分析 毛德操 胡希明著 浙江大學(xué)出版社
3、LINUX0.01源代碼
4、http://www.linuxforum.net/ LINUX內(nèi)核分析-->精華篇-->進程調(diào)度