新讀者看這里，老讀者直接跳過。

本系列會以一個讀小說的心態(tài)，從開機啟動后的代碼執(zhí)行順序，帶著大家閱讀和賞析 Linux 0.11 全部核心代碼，了解操作系統(tǒng)的技術(shù)細(xì)節(jié)和設(shè)計思想。

你會跟著我一起，看著一個操作系統(tǒng)從啥都沒有開始，一步一步最終實現(xiàn)它復(fù)雜又精巧的設(shè)計，讀完這個系列后希望你能發(fā)出感嘆，原來操作系統(tǒng)源碼就是這破玩意。

書接上回，上回書我們說到了進程調(diào)度的初始化，定義了一個長度為 64 的 task 數(shù)組用于管理全部進程的結(jié)構(gòu)。

之后在 GDT 中預(yù)定義了進程調(diào)度需要用到的 TSS 和 LDT 結(jié)構(gòu)。

之后開啟了定時器，準(zhǔn)備迎接時鐘中斷的到來，進而觸發(fā)進程調(diào)度。

那接下來我們就冷靜下，回到 main 函數(shù)，繼續(xù)看下一個初始化的過程。 那就是緩沖區(qū)初始化 buffer_init，加油，沒剩多少了!

void main(void) {
    ...
    mem_init(main_memory_start,memory_end);
    trap_init();
    blk_dev_init();
    chr_dev_init();
    tty_init();
    time_init();
    sched_init();
    buffer_init(buffer_memory_end);
    hd_init();
    floppy_init();
    sti();
    move_to_user_mode();
    if (!fork()) {
        init();
    }
    for(;;) pause();
}

首先要注意到，這個函數(shù)傳了個參數(shù) buffer_memory_end，這個是在老早之前就設(shè)置好的，就在第12回 | 管理內(nèi)存前先劃分出三個邊界值，回顧下。

想起來了吧?而且我們在 第13回 | 主內(nèi)存初始化 mem_init 中，用 mem_init 設(shè)置好了主內(nèi)存的管理結(jié)構(gòu) mam_map。

再想不起來那就需要把前面的章節(jié)再讀一讀咯，不然后面越來越難。 前面是把主內(nèi)存區(qū)管理起來了，所以今天就是把剩下的緩沖區(qū)部分，也初始化管理起來。目的就是這么單純，我們看代碼。 我們還是采用之前的方式，就假設(shè)內(nèi)存只有 8M，把一些不相干的分支去掉，方便理解。

extern int end;
struct buffer_head * start_buffer = (struct buffer_head *) &end;

void buffer_init(long buffer_end) {
    struct buffer_head * h = start_buffer;
    void * b = (void *) buffer_end;
    while ( (b -= 1024) >= ((void *) (h+1)) ) {
        h->b_dev = 0;
        h->b_dirt = 0;
        h->b_count = 0;
        h->b_lock = 0;
        h->b_uptodate = 0;
        h->b_wait = NULL;
        h->b_next = NULL;
        h->b_prev = NULL;
        h->b_data = (char *) b;
        h->b_prev_free = h-1;
        h->b_next_free = h+1;
        h++;
    }
    h--;
    free_list = start_buffer;
    free_list->b_prev_free = h;
    h->b_next_free = free_list;
    for (int i=0;i<307;i++)
        hash_table[i]=NULL;
}

雖然很長，但其實就造了兩個數(shù)據(jù)結(jié)構(gòu)而已。

不過別急，我們先看這一行代碼。

extern int end;
void buffer_init(long buffer_end) {
    struct buffer_head * start_buffer = (struct buffer_head *) &end;
    ...
}

這里有個外部變量 end，而我們的緩沖區(qū)開始位置start_buffer 就等于這個變量的內(nèi)存地址。

這個外部變量 end 并不是操作系統(tǒng)代碼寫就的，而是由鏈接器 ld 在鏈接整個程序時設(shè)置的一個外部變量，幫我們計算好了整個內(nèi)核代碼的末尾地址。 那在這之前的是內(nèi)核代碼區(qū)域肯定不能用，在這之后的，就給 buffer 用了。所以我們的內(nèi)存分布圖可以更精確一點了。

你看，之前的疑惑解決了吧?很好理解嘛，內(nèi)核程序和緩沖區(qū)的劃分，肯定有個分界線，這個分界線就是 end 變量的值。

這個值定多少合適呢?

像主內(nèi)存和緩沖區(qū)的分界線，就直接代碼里寫死了，就是上圖中的 2M。

可是內(nèi)核程序占多大內(nèi)存在寫的時候完全不知道，就算知道了如果改動一點代碼也會變化，所以就由程序編譯鏈接時由鏈接器程序幫我們把這個內(nèi)核代碼末端的地址計算出來，作為一個外部變量 end 我們拿來即用，就方便多了。

好，回過頭我們再看看，整段代碼創(chuàng)造了哪兩個管理結(jié)構(gòu)? 我們先看這段結(jié)構(gòu)。

void buffer_init(long buffer_end) {
    struct buffer_head * h = start_buffer;
    void * b = (void *) buffer_end;
    while ( (b -= 1024) >= ((void *) (h+1)) ) {
        ...
        h->b_data = (char *) b;
        h->b_prev_free = h-1;
        h->b_next_free = h+1;
        h++;
    }
    ...
}

就倆變量。

一個是 buffer_head 結(jié)構(gòu)的 h，代表緩沖頭，其指針值是 start_buffer，剛剛我們計算過了，就是圖中的內(nèi)核代碼末端地址 end，也就是緩沖區(qū)開頭。 一個是 b，代表緩沖塊，指針值是 buffer_end，也就是圖中的 2M，就是緩沖區(qū)結(jié)尾。 緩沖區(qū)結(jié)尾的 b 每次循環(huán) -1024，也就是一頁的值，緩沖區(qū)結(jié)尾的 h 每次循環(huán) +1(一個 buffer_head 大小的內(nèi)存)，直到碰一塊為止。

可以看到，其實這個 b 就代表緩沖塊，h 代表緩沖頭，一個從上往下，一個從下往上。 而且這個過程中，h 被附上了屬性值，其中比較關(guān)鍵的是這個 buffer 所表示的數(shù)據(jù)部分 b_data，也就是指向了上面的緩沖塊 b。

還有這個 buffer 的前后空閑 buffer 的指針b_prev_free 和 b_next_free。

那畫成圖就是如下這樣。

當(dāng)緩沖頭 h 的所有 next 和 prev 指針都指向彼此時，就構(gòu)成了一個雙向鏈表。繼續(xù)看。

void buffer_init(long buffer_end) {
    ...
    free_list = start_buffer;
    free_list->b_prev_free = h;
    h->b_next_free = free_list;
    ...
}

這三行代碼，結(jié)合剛剛的雙向鏈表 h，我畫出圖，你就懂了。

看，free_list 指向了緩沖頭雙向鏈表的第一個結(jié)構(gòu)，然后就可以順著這個結(jié)構(gòu)，從雙向鏈表中遍歷到任何一個緩沖頭結(jié)構(gòu)了，而通過緩沖頭又可以找到這個緩沖頭對應(yīng)的緩沖塊。 簡單說，緩沖頭就是具體緩沖塊的管理結(jié)構(gòu)，而 free_list 開頭的雙向鏈表又是緩沖頭的管理結(jié)構(gòu)，整個管理體系就這樣建立起來了。

現(xiàn)在，從 free_list 開始遍歷，就可以找到這里的所有內(nèi)容了。

不過，還有最后一個事，能幫助更好管理，往下看。

void buffer_init(long buffer_end) {
    ...
    for (i=0;i<307;i++)
        hash_table[i]=NULL;
}

一個 307 大小的 hash_table 數(shù)組，這是干嘛的呢?

其實今天的這個代碼在 buffer.c 中，而 buffer.c 是在 fs 包下的，也就是文件系統(tǒng)包下的。所以它今后是為文件系統(tǒng)而服務(wù)，具體是內(nèi)核程序如果需要訪問塊設(shè)備中的數(shù)據(jù)，就都需要經(jīng)過緩沖區(qū)來間接地操作。 也就是說，讀取塊設(shè)備的數(shù)據(jù)(硬盤中的數(shù)據(jù))，需要先讀到緩沖區(qū)中，如果緩沖區(qū)已有了，就不用從塊設(shè)備讀取了，直接取走。 那怎么知道緩沖區(qū)已經(jīng)有了要讀取的塊設(shè)備中的數(shù)據(jù)呢?從雙向鏈表從頭遍歷當(dāng)然可以，但是這效率可太低了。所以需要一個 hashmap 的結(jié)構(gòu)方便快速查找，這就是 hash_table 這個數(shù)組的作用。 現(xiàn)在只是初始化這個 hash_table，還并沒有哪個地方用到了它，所以我就先簡單劇透下。

之后當(dāng)要讀取某個塊設(shè)備上的數(shù)據(jù)時，首先要搜索相應(yīng)的緩沖塊，是下面這個函數(shù)。

#define _hashfn(dev,block) (((unsigned)(dev^block))%307)
#define hash(dev,block) hash_table[_hashfn(dev,block)]

// 搜索合適的緩沖塊 
struct buffer_head * getblk(int dev,int block) {
    ...
    struct buffer_head bh = get_hash_table(dev,block)；
    ...
}

struct buffer_head * get_hash_table(int dev, int block) {
    ...    
    find_buffer(dev,block);
    ...
}

static struct buffer_head * find_buffer(int dev, int block) { 
    ...     
    hash(dev,block);
    ...
}

一路跟下來發(fā)現(xiàn)，就是通過

dev^block % 307

即

(設(shè)備號^邏輯塊號) Mod 307

找到在 hash_table 里的索引下標(biāo)，接下來就和 Java 里的 HashMap 類似，如果哈希沖突就形成鏈表，畫成圖就是這樣。

哈希表 + 雙向鏈表，如果刷算法題多了，很容易想到這可以實現(xiàn) LRU 算法，沒錯，之后的緩沖區(qū)使用和棄用，正是這個算法發(fā)揮了作用。

也就是之后在講通過文件系統(tǒng)來讀取硬盤文件時，都需要使用和棄用這個緩沖區(qū)里的內(nèi)容，緩沖區(qū)即是用戶進程的內(nèi)存和硬盤之間的橋梁。

好了好了，再多說幾句就把文件系統(tǒng)里讀操作講出來了，壓力太大，本章還是主要就了解這個緩沖區(qū)的管理工作是如何初始化的，為后面做鋪墊。

回過頭來看看我們目前的進度吧!

void main(void) {
    ...
    mem_init(main_memory_start,memory_end);
    trap_init();
    blk_dev_init();
    chr_dev_init();
    tty_init();
    time_init();
    sched_init();
    buffer_init(buffer_memory_end);
    hd_init();
    floppy_init();
    
    sti();
    move_to_user_mode();
    if (!fork()) {init();}
    for(;;) pause();
}

整個初始化的部分，就差 hd_init 和 floppy_init這兩個塊設(shè)備的初始化還沒講了。

而且幸運的是，floppy_init 是軟盤初始化，現(xiàn)在軟盤幾乎都被淘汰了，計算機中也沒有軟盤驅(qū)動器了，所以這個我們完全可以不看，那就剩下一個hd_init 硬盤初始化了，非常簡單! 還記得小時候我特別喜歡收集軟盤，里面分門別類存上我做的 Flash 動畫，然后在軟盤上的那個紙標(biāo)簽上寫上文字，表示軟盤存了什么，想想看還是回憶呢。

扯遠(yuǎn)了。 之前的各種初始化工作所建立的數(shù)據(jù)結(jié)構(gòu)，會在后面各個模塊發(fā)揮最最核心的作用，任何操作系統(tǒng)的管理都離不開這些初始化工作所建立的數(shù)據(jù)結(jié)構(gòu)，所以一定要把這些根基搭建好，別急別慌。 等初始化工作全部完成，我會專門用一回給大家梳理一下，大家就盡可能把初始化這一大部分的數(shù)據(jù)結(jié)構(gòu)記在心里吧!