書(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)這完全依賴(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è)值稱(chēng)為優(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)下回分解。

本文轉(zhuǎn)載自微信公眾號(hào)「低并發(fā)編程」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系低并發(fā)編程公眾號(hào)。