本系列作為?你管這破玩意叫操作系統(tǒng)源碼?的第三大部分，講述了操作系統(tǒng)第一個(gè)進(jìn)程從無(wú)到有的誕生過(guò)程，這一部分你將看到內(nèi)核態(tài)與用戶態(tài)的轉(zhuǎn)換、進(jìn)程調(diào)度的上帝視角、系統(tǒng)調(diào)用的全鏈路、fork 函數(shù)的深度剖析。

不要聽(tīng)到這些陌生的名詞就害怕，跟著我一點(diǎn)一點(diǎn)了解他們的全貌，你會(huì)發(fā)現(xiàn)，這些概念竟然如此活靈活現(xiàn)，如此順其自然且合理地出現(xiàn)在操作系統(tǒng)的啟動(dòng)過(guò)程中。

本篇章作為一個(gè)全新的篇章，需要前置篇章的知識(shí)體系支撐。

第一部分進(jìn)入內(nèi)核前的苦力活

第二部分大戰(zhàn)前期的初始化工作

當(dāng)然，沒(méi)讀過(guò)的也問(wèn)題不大，我都會(huì)在文章里做說(shuō)明，如果你覺(jué)得有困惑，就去我告訴你的相應(yīng)章節(jié)回顧就好了，放寬心。

------- 第三部分目錄?-------

（一）先整體看一下

（二）從內(nèi)核態(tài)到用戶態(tài)

------- 正文開(kāi)始?-------

書(shū)接上回，上回書(shū)咱們說(shuō)到，操作系統(tǒng)通過(guò) move_to_user_mode 方法，通過(guò)偽造一個(gè)中斷和中斷返回，巧妙地從內(nèi)核態(tài)切換到了用戶態(tài)。

void?main(void)?{
????...????
????move_to_user_mode();
????if?(!fork())?{
????????init();
????}
????for(;;)?pause();
}

今天，本來(lái)應(yīng)該再往下講 fork。

但這個(gè)是創(chuàng)建新進(jìn)程的過(guò)程，是一個(gè)很能體現(xiàn)操作系統(tǒng)設(shè)計(jì)的地方。

所以我們先別急著看代碼，我們今天就頭腦風(fēng)暴一下，就是如果讓你來(lái)設(shè)計(jì)整個(gè)進(jìn)程調(diào)度，你會(huì)怎么搞？

別告訴我你先設(shè)計(jì)鎖、設(shè)計(jì) volatile 啥的，這都不是進(jìn)程調(diào)度本身需要關(guān)心的最根本問(wèn)題。

進(jìn)程調(diào)度本質(zhì)是什么？很簡(jiǎn)單，假如有三段代碼被加載到內(nèi)存中。

進(jìn)程調(diào)度就是讓 CPU 一會(huì)去程序 1 的位置處運(yùn)行一段時(shí)間，一會(huì)去程序 2 的位置處運(yùn)行一段時(shí)間。

嗯，就這么簡(jiǎn)單，別反駁我，接著往下看。

整體流程設(shè)計(jì)

如何做到剛剛說(shuō)的，一會(huì)去這運(yùn)行，一會(huì)去那運(yùn)行？

第一種辦法就是，程序 1 的代碼里，每隔幾行就寫(xiě)一段代碼，主動(dòng)放棄自己的執(zhí)行權(quán)，跳轉(zhuǎn)到程序 2 的地方運(yùn)行。然后程序 2 也是如此。

但這種依靠程序自己的辦法肯定不靠譜。

所以第二種辦法就是，由一個(gè)不受任何程序控制的，第三方的不可抗力，每隔一段時(shí)間就中斷一下 CPU 的運(yùn)行，然后跳轉(zhuǎn)到一個(gè)特殊的程序那里，這個(gè)程序通過(guò)某種方式獲取到 CPU 下一個(gè)要運(yùn)行的程序的地址，然后跳轉(zhuǎn)過(guò)去。

這個(gè)每隔一段時(shí)間就中斷 CPU 的不可抗力，就是由定時(shí)器觸發(fā)的時(shí)鐘中斷。

不知道你是否還記得，這個(gè)定時(shí)器和時(shí)鐘中斷，早在?第18回 | 大名鼎鼎的進(jìn)程調(diào)度就是從這里開(kāi)始的?里講的 sched_init 函數(shù)里就搞定了。

而那個(gè)特殊的程序，就是具體的進(jìn)程調(diào)度函數(shù)了。

好了，整個(gè)流程就這樣處理完了，那么應(yīng)該設(shè)計(jì)什么樣的數(shù)據(jù)結(jié)構(gòu)，來(lái)支持這個(gè)流程呢？不妨假設(shè)這個(gè)結(jié)構(gòu)叫 tast_struct。

struct?task_struct?{
?????
}?

換句話說(shuō)，你總得有一個(gè)結(jié)構(gòu)來(lái)記錄各個(gè)進(jìn)程的信息，比如它上一次執(zhí)行到哪里了，要不 CPU 就算決定好了要跳轉(zhuǎn)到你這個(gè)進(jìn)程上運(yùn)行，具體跳到哪一行運(yùn)行，總得有個(gè)地方存吧？

我們一個(gè)個(gè)問(wèn)題拋開(kāi)來(lái)看。

上下文環(huán)境

每個(gè)程序最終的本質(zhì)就是執(zhí)行指令。這個(gè)過(guò)程會(huì)涉及寄存器，內(nèi)存和外設(shè)端口。

內(nèi)存還有可能設(shè)計(jì)成相互錯(cuò)開(kāi)的，互不干擾，比如進(jìn)程 1 你就用 0~1K 的內(nèi)存空間，進(jìn)程 2 就用 1K~2K 的內(nèi)存空間，咱誰(shuí)也別影響誰(shuí)。

雖然有點(diǎn)浪費(fèi)空間，而且對(duì)程序員十分不友好，但起碼還是能實(shí)現(xiàn)的。

不過(guò)寄存器一共就那么點(diǎn)，肯定做不到互不干擾，可能一個(gè)進(jìn)程就把寄存器全用上了，那其他進(jìn)程咋整。

比如程序 1 剛剛往 eax 寫(xiě)入一個(gè)值，準(zhǔn)備用，這時(shí)切換到進(jìn)程 2 了，又往 eax 里寫(xiě)入了一個(gè)值。那么之后再切回進(jìn)程 1 的時(shí)候，就出錯(cuò)了。

所以最穩(wěn)妥的做法就是，每次切換進(jìn)程時(shí)，都把當(dāng)前這些寄存器的值存到一個(gè)地方，以便之后切換回來(lái)的時(shí)候恢復(fù)。

Linux 0.11 就是這樣做的，每個(gè)進(jìn)程的結(jié)構(gòu) task_struct 里面，有一個(gè)叫 tss 的結(jié)構(gòu)，存儲(chǔ)的就是 CPU 這些寄存器的信息。

struct?task_struct?{
????...
????struct?tss_struct?tss;
}

struct?tss_struct?{
????long????back_link;??/*?16?high?bits?zero?*/
????long????esp0;
????long????ss0;????????/*?16?high?bits?zero?*/
????long????esp1;
????long????ss1;????????/*?16?high?bits?zero?*/
????long????esp2;
????long????ss2;????????/*?16?high?bits?zero?*/
????long????cr3;
????long????eip;
????long????eflags;
????long????eax,ecx,edx,ebx;
????long????esp;
????long????ebp;
????long????esi;
????long????edi;
????long????es;?????/*?16?high?bits?zero?*/
????long????cs;?????/*?16?high?bits?zero?*/
????long????ss;?????/*?16?high?bits?zero?*/
????long????ds;?????/*?16?high?bits?zero?*/
????long????fs;?????/*?16?high?bits?zero?*/
????long????gs;?????/*?16?high?bits?zero?*/
????long????ldt;????????/*?16?high?bits?zero?*/
????long????trace_bitmap;???/*?bits:?trace?0,?bitmap?16-31?*/
????struct?i387_struct?i387;
};

這里提個(gè)細(xì)節(jié)。

你發(fā)現(xiàn) tss 結(jié)構(gòu)里還有個(gè) cr3 不？它表示 cr3 寄存器里存的值，而 cr3 寄存器是指向頁(yè)目錄表首地址的。

那么指向不同的頁(yè)目錄表，整個(gè)頁(yè)表結(jié)構(gòu)就是完全不同的一套，那么線性地址到物理地址的映射關(guān)系就有能力做到不同。

也就是說(shuō)，在我們剛剛假設(shè)的理想情況下，不同程序用不同的內(nèi)存地址可以做到內(nèi)存互不干擾。

但是有了這個(gè) cr3 字段，就完全可以無(wú)需由各個(gè)進(jìn)程自己保證不和其他進(jìn)程使用的內(nèi)存沖突，因?yàn)橹灰⒉煌挠成潢P(guān)系即可，由操作系統(tǒng)來(lái)建立不同的頁(yè)目錄表并替換 cr3 寄存器即可。

這也可以理解為，保存了內(nèi)存映射的上下文信息。

當(dāng)然 Linux 0.11 并不是通過(guò)替換 cr3 寄存器來(lái)實(shí)現(xiàn)內(nèi)存互不干擾的，它的實(shí)現(xiàn)更為簡(jiǎn)單，這是后話了。

運(yùn)行時(shí)間信息

如何判斷一個(gè)進(jìn)程該讓出 CPU 了，切換到下一個(gè)進(jìn)程呢？

總不能是每次時(shí)鐘中斷時(shí)都切換一次吧？一來(lái)這樣不靈活，二來(lái)這完全依賴時(shí)鐘中斷的頻率，有點(diǎn)危險(xiǎn)。

所以一個(gè)好的辦法就是，給進(jìn)程一個(gè)屬性，叫剩余時(shí)間片，每次時(shí)鐘中斷來(lái)了之后都 -1，如果減到 0 了，就觸發(fā)切換進(jìn)程的操作。

在 Linux 0.11 里，這個(gè)屬性就是 counter。

struct?task_struct?{
????...
????long?counter;
????...
????struct?tss_struct?tss;
}

而他的用法也非常簡(jiǎn)單，就是每次中斷都判斷一下是否到 0 了。

void?do_timer(long?cpl)?{
????...
????//?當(dāng)前線程還有剩余時(shí)間片，直接返回
????if?((--current->counter)>0)?return;
????//?若沒(méi)有剩余時(shí)間片，調(diào)度
????schedule();
}

如果還沒(méi)到 0，就直接返回，相當(dāng)于這次時(shí)鐘中斷什么也沒(méi)做，僅僅是給當(dāng)前進(jìn)程的時(shí)間片屬性做了 -1 操作。

如果已經(jīng)到 0 了，就觸發(fā)進(jìn)程調(diào)度，選擇下一個(gè)進(jìn)程并使 CPU 跳轉(zhuǎn)到那里運(yùn)行。

進(jìn)程調(diào)度的邏輯就是在 schedule 函數(shù)里，怎么調(diào)，我們先不管。

優(yōu)先級(jí)

上面那個(gè) counter 一開(kāi)始的時(shí)候該是多少呢？而且隨著 counter 不斷遞減，減到 0 時(shí)，下一輪回中這個(gè) counter 應(yīng)該賦予什么值呢？

其實(shí)這倆問(wèn)題都是一個(gè)問(wèn)題，就是 counter 的初始化問(wèn)題，也需要有一個(gè)屬性來(lái)記錄這個(gè)值。

往宏觀想一下，這個(gè)值越大，那么 counter 就越大，那么每次輪到這個(gè)進(jìn)程時(shí)，它在 CPU 中運(yùn)行的時(shí)間就越長(zhǎng)，也就是這個(gè)進(jìn)程比其他進(jìn)程得到了更多 CPU 運(yùn)行的時(shí)間。

那我們可以把這個(gè)值稱為優(yōu)先級(jí)，是不是很形象。

struct?task_struct?{
????...
????long?counter;
????long?priority;
????...
????struct?tss_struct?tss;
}

每次一個(gè)進(jìn)程初始化時(shí)，都把 counter 賦值為這個(gè) priority，而且當(dāng) counter 減為 0 時(shí)，下一次分配時(shí)間片，也賦值為這個(gè)。

其實(shí)叫啥都行，反正就是這么用的，就叫優(yōu)先級(jí)吧。

進(jìn)程狀態(tài)

其實(shí)我們有了上面那三個(gè)信息，就已經(jīng)可以完成進(jìn)程的調(diào)度了。

甚至如果你的操作系統(tǒng)讓所有進(jìn)程都得到同樣的運(yùn)行時(shí)間，連 counter 和 priority 都不用記錄，就操作系統(tǒng)自己定一個(gè)固定值一直遞減，減到 0 了就隨機(jī)切一個(gè)新進(jìn)程。

這樣就僅僅維護(hù)好寄存器的上下文信息 tss 就好了。

但我們總要不斷優(yōu)化以適應(yīng)不同場(chǎng)景的用戶需求的，那我們?cè)賰?yōu)化一個(gè)細(xì)節(jié)。

很簡(jiǎn)單的一個(gè)場(chǎng)景，一個(gè)進(jìn)程中有一個(gè)讀取硬盤(pán)的操作，發(fā)起讀請(qǐng)求后，要等好久才能得到硬盤(pán)的中斷信號(hào)。

那這個(gè)時(shí)間其實(shí)該進(jìn)程再占用著 CPU 也沒(méi)用，此時(shí)就可以選擇主動(dòng)放棄 CPU 執(zhí)行權(quán)，然后再把自己的狀態(tài)標(biāo)記為等待中。

意思是告訴進(jìn)程調(diào)度的代碼，先別調(diào)度我，因?yàn)槲疫€在等硬盤(pán)的中斷，現(xiàn)在輪到我了也沒(méi)用，把機(jī)會(huì)給別人吧。

那這個(gè)狀態(tài)可以記錄一個(gè)屬性了，叫 state，記錄了此時(shí)進(jìn)程的狀態(tài)。

struct?task_struct?{
????long?state;
????long?counter;
????long?priority;
????...
????struct?tss_struct?tss;
}

而這個(gè)進(jìn)程的狀態(tài)在 Linux 0.11 里有這么五種。

#define?TASK_RUNNING??????????0
#define?TASK_INTERRUPTIBLE????1
#define?TASK_UNINTERRUPTIBLE??2
#define?TASK_ZOMBIE???????????3
#define?TASK_STOPPED??????????4

好了，目前我們這幾個(gè)字段，就已經(jīng)可以完成簡(jiǎn)單的進(jìn)程調(diào)度任務(wù)了。

有表示狀態(tài)的 state，表示剩余時(shí)間片的 counter，表示優(yōu)先級(jí)的 priority，和表示上下文信息的 tss。

其他字段我們需要用到的時(shí)候再說(shuō)，今天只是頭腦風(fēng)暴一下進(jìn)程調(diào)度設(shè)計(jì)的思路。

我們看一下 Linux 0.11 中進(jìn)程結(jié)構(gòu)的全部，心里先有個(gè)數(shù)，具體干嘛的先別管，就記住我們剛剛頭腦風(fēng)暴的那四個(gè)字段就行了。

struct?task_struct?{
/*?these?are?hardcoded?-?don't?touch?*/
????long?state;?/*?-1?unrunnable,?0?runnable,?>0?stopped?*/
????long?counter;
????long?priority;
????long?signal;
????struct?sigaction?sigaction[32];
????long?blocked;???/*?bitmap?of?masked?signals?*/
/*?various?fields?*/
????int?exit_code;
????unsigned?long?start_code,end_code,end_data,brk,start_stack;
????long?pid,father,pgrp,session,leader;
????unsigned?short?uid,euid,suid;
????unsigned?short?gid,egid,sgid;
????long?alarm;
????long?utime,stime,cutime,cstime,start_time;
????unsigned?short?used_math;
/*?file?system?info?*/
????int?tty;????????/*?-1?if?no?tty,?so?it?must?be?signed?*/
????unsigned?short?umask;
????struct?m_inode?*?pwd;
????struct?m_inode?*?root;
????struct?m_inode?*?executable;
????unsigned?long?close_on_exec;
????struct?file?*?filp[NR_OPEN];
/*?ldt?for?this?task?0?-?zero?1?-?cs?2?-?ds&ss?*/
????struct?desc_struct?ldt[3];
/*?tss?for?this?task?*/
????struct?tss_struct?tss;
};

看吧，其實(shí)也沒(méi)多少咯～

好了，今天我們完全由自己從零到有設(shè)計(jì)出了進(jìn)程調(diào)度的大體流程，以及它需要的數(shù)據(jù)結(jié)構(gòu)。

我們知道了進(jìn)程調(diào)度的開(kāi)始，要從一次定時(shí)器滴答來(lái)觸發(fā)，通過(guò)時(shí)鐘中斷處理函數(shù)走到進(jìn)程調(diào)度函數(shù)，然后去進(jìn)程的結(jié)構(gòu) task_struct 中取出所需的數(shù)據(jù)，進(jìn)行策略計(jì)算，并挑選出下一個(gè)可以得到 CPU 運(yùn)行的進(jìn)程，跳轉(zhuǎn)過(guò)去。

那么下一講，我們從一次時(shí)鐘中斷出發(fā)，看看一次 Linux 0.11 的進(jìn)程調(diào)度的全過(guò)程。有了這兩回做鋪墊，之后再看主流程中的 fork 代碼，將會(huì)非常清晰！

欲知后事如何，且聽(tīng)下回分解。

------- 關(guān)于本系列的完整內(nèi)容?-------

本系列的開(kāi)篇詞看這

閃客新系列！你管這破玩意叫操作系統(tǒng)源碼

本系列的擴(kuò)展資料看這（也可點(diǎn)擊閱讀原文），這里有很多有趣的資料、答疑、互動(dòng)參與項(xiàng)目，持續(xù)更新中，希望有你的參與。

https://github.com/sunym1993/flash-linux0.11-talk

本系列全局視角

最后，祝大家都能追更到系列結(jié)束，只要你敢持續(xù)追更，并且把每一回的內(nèi)容搞懂，我就敢讓你在系列結(jié)束后說(shuō)一句，我對(duì) Linux 0.11 很熟悉。

公眾號(hào)更新系列文章不易，閱讀量越來(lái)越低，希望大家多多傳播，不方便的話點(diǎn)個(gè)小小的在看我也會(huì)很開(kāi)心，我相信星火燎原的力量，謝謝大家咯。

另外，本系列完全免費(fèi)，希望大家能多多傳播給同樣喜歡的人，同時(shí)給我的 GitHub 項(xiàng)目點(diǎn)個(gè) star，就在閱讀原文處，這些就足夠讓我堅(jiān)持寫(xiě)下去了！我們下回見(jiàn)。

一個(gè)新進(jìn)程的誕生（三）如果讓你來(lái)設(shè)計(jì)進(jìn)程調(diào)度

整體流程設(shè)計(jì)

上下文環(huán)境

運(yùn)行時(shí)間信息

優(yōu)先級(jí)

進(jìn)程狀態(tài)