最近太忙，居然過(guò)了2個(gè)月才更新第十四章。。。。

主要內(nèi)容：

• 塊設(shè)備簡(jiǎn)介
• 內(nèi)核訪問(wèn)塊設(shè)備的方法
• 內(nèi)核I/O調(diào)度程序

1. 塊設(shè)備簡(jiǎn)介

I/O設(shè)備主要有2類(lèi):

• 字符設(shè)備：只能順序讀寫(xiě)設(shè)備中的內(nèi)容，比如 串口設(shè)備，鍵盤(pán)
• 塊設(shè)備：能夠隨機(jī)讀寫(xiě)設(shè)備中的內(nèi)容，比如 硬盤(pán)，U盤(pán)

字符設(shè)備由于只能順序訪問(wèn)，所以應(yīng)用場(chǎng)景也不多，這篇文章主要討論塊設(shè)備。

塊設(shè)備是隨機(jī)訪問(wèn)的，所以塊設(shè)備在不同的應(yīng)用場(chǎng)景中存在很大的優(yōu)化空間。

塊設(shè)備中最重要的一個(gè)概念就是塊設(shè)備的最小尋址單元。

塊設(shè)備的最小尋址單元就是扇區(qū)，扇區(qū)的大小是2的整數(shù)倍，一般是 512字節(jié)。

扇區(qū)是物理上的最小尋址單元，而邏輯上的最小尋址單元是塊。

為了便于文件系統(tǒng)管理，塊的大小一般是扇區(qū)的整數(shù)倍，并且小于等于頁(yè)的大小。

查看扇區(qū)和I/O塊的方法：

[wangyubin@localhost]$ sudo fdisk -l

WARNING: GPT (GUID Partition Table) detected on '/dev/sda'! The util fdisk doesn't support GPT. Use GNU Parted.


Disk /dev/sda: 500.1 GB, 500107862016 bytes, 976773168 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes
Disk identifier: 0x00000000

上面的 Sector size 就是扇區(qū)的值，I/O size就是 塊的值

從上面顯示的結(jié)果，我們發(fā)現(xiàn)有個(gè)奇怪的地方，扇區(qū)的大小有2個(gè)值，邏輯大小是 512字節(jié)，而物理大小卻是 4096字節(jié)。

其實(shí)邏輯大小 512字節(jié)是為了兼容以前的軟件應(yīng)用，而實(shí)際物理大小 4096字節(jié)是由于硬盤(pán)空間越來(lái)越大導(dǎo)致的。

具體的來(lái)龍去脈請(qǐng)參考：4KB扇區(qū)的原因

2. 內(nèi)核訪問(wèn)塊設(shè)備的方法

內(nèi)核通過(guò)文件系統(tǒng)訪問(wèn)塊設(shè)備時(shí)，需要先把塊讀入到內(nèi)存中。所以文件系統(tǒng)為了管理塊設(shè)備，必須管理[塊]和內(nèi)存頁(yè)之間的映射。

內(nèi)核中有2種方法來(lái)管理 [塊] 和內(nèi)存頁(yè)之間的映射。

• 緩沖區(qū)和緩沖區(qū)頭
• bio

2.1 緩沖區(qū)和緩沖區(qū)頭

每個(gè) [塊] 都是一個(gè)緩沖區(qū)，同時(shí)對(duì)每個(gè) [塊] 都定義一個(gè)緩沖區(qū)頭來(lái)描述它。

由于 [塊] 的大小是小于內(nèi)存頁(yè)的大小的，所以每個(gè)內(nèi)存頁(yè)會(huì)包含一個(gè)或者多個(gè) [塊]

緩沖區(qū)頭定義在 <linux/buffer_head.h>: include/linux/buffer_head.h

struct buffer_head {
    unsigned long b_state;            /* 表示緩沖區(qū)狀態(tài) */
    struct buffer_head *b_this_page;/* 當(dāng)前頁(yè)中緩沖區(qū) */
    struct page *b_page;            /* 當(dāng)前緩沖區(qū)所在內(nèi)存頁(yè) */

    sector_t b_blocknr;        /* 起始?jí)K號(hào) */
    size_t b_size;            /* buffer在內(nèi)存中的大小 */
    char *b_data;            /* 塊映射在內(nèi)存頁(yè)中的數(shù)據(jù) */

    struct block_device *b_bdev; /* 關(guān)聯(lián)的塊設(shè)備 */
    bh_end_io_t *b_end_io;        /* I/O完成方法 */
     void *b_private;             /* 保留的 I/O 完成方法 */
    struct list_head b_assoc_buffers;   /* 關(guān)聯(lián)的其他緩沖區(qū) */
    struct address_space *b_assoc_map;    /* 相關(guān)的地址空間 */
    atomic_t b_count;                    /* 引用計(jì)數(shù) */
};

整個(gè) buffer_head 結(jié)構(gòu)體中的字段是減少過(guò)的，以前的內(nèi)核中字段更多。

各個(gè)字段的含義通過(guò)注釋都很明了，只有 b_state 字段比較復(fù)雜，它涵蓋了緩沖區(qū)可能的各種狀態(tài)。

enum bh_state_bits {
    BH_Uptodate,    /* 包含可用數(shù)據(jù) */
    BH_Dirty,    /* 該緩沖區(qū)是臟的(說(shuō)明緩沖的內(nèi)容比磁盤(pán)中的內(nèi)容新，需要回寫(xiě)磁盤(pán)) */
    BH_Lock,    /* 該緩沖區(qū)正在被I/O使用，鎖住以防止并發(fā)訪問(wèn) */
    BH_Req,        /* 該緩沖區(qū)有I/O請(qǐng)求操作 */
    BH_Uptodate_Lock,/* 由內(nèi)存頁(yè)中的第一個(gè)緩沖區(qū)使用，使得該頁(yè)中的其他緩沖區(qū) */

    BH_Mapped,    /* 該緩沖區(qū)是映射到磁盤(pán)塊的可用緩沖區(qū) */
    BH_New,        /* 緩沖區(qū)是通過(guò) get_block() 剛剛映射的，尚且不能訪問(wèn) */
    BH_Async_Read,    /* 該緩沖區(qū)正通過(guò) end_buffer_async_read() 被異步I/O讀操作使用 */
    BH_Async_Write,    /* 該緩沖區(qū)正通過(guò) end_buffer_async_read() 被異步I/O寫(xiě)操作使用 */
    BH_Delay,    /* 緩沖區(qū)還未和磁盤(pán)關(guān)聯(lián) */
    BH_Boundary,    /* 該緩沖區(qū)處于連續(xù)塊區(qū)的邊界，下一個(gè)塊不在連續(xù) */
    BH_Write_EIO,    /* 該緩沖區(qū)在寫(xiě)的時(shí)候遇到 I/O 錯(cuò)誤 */
    BH_Ordered,    /* 順序?qū)?*/
    BH_Eopnotsupp,    /* 該緩沖區(qū)發(fā)生 “不被支持” 錯(cuò)誤 */
    BH_Unwritten,    /* 該緩沖區(qū)在磁盤(pán)上的位置已經(jīng)被申請(qǐng)，但還有實(shí)際寫(xiě)入數(shù)據(jù) */
    BH_Quiet,    /* 該緩沖區(qū)禁止錯(cuò)誤 */

    BH_PrivateStart,/* 不是表示狀態(tài)，分配給其他實(shí)體的私有數(shù)據(jù)區(qū)的第一個(gè)bit */
};

在2.6之前的內(nèi)核中，主要就是通過(guò)緩沖區(qū)頭來(lái)管理 [塊] 和內(nèi)存之間的映射的。

用緩沖區(qū)頭來(lái)管理內(nèi)核的 I/O 操作主要存在以下2個(gè)弊端，所以在2.6開(kāi)始的內(nèi)核中，緩沖區(qū)頭的作用大大降低了。

- 弊端 1

對(duì)內(nèi)核而言，操作內(nèi)存頁(yè)是最為簡(jiǎn)便和高效的，所以如果通過(guò)緩沖區(qū)頭來(lái)操作的話（緩沖區(qū) 即[塊]在內(nèi)存中映射，可能比頁(yè)面要?。?，效率低下。

而且每個(gè) [塊] 對(duì)應(yīng)一個(gè)緩沖區(qū)頭的話，導(dǎo)致內(nèi)存的利用率降低（緩沖區(qū)頭包含的字段非常多）

- 弊端 2

每個(gè)緩沖區(qū)頭只能表示一個(gè) [塊]，所以內(nèi)核在處理大數(shù)據(jù)時(shí)，會(huì)分解為對(duì)一個(gè)個(gè)小的 [塊] 的操作，造成不必要的負(fù)擔(dān)和空間浪費(fèi)。

2.2 bio

bio結(jié)構(gòu)體的出現(xiàn)就是為了改善上面緩沖區(qū)頭的2個(gè)弊端，它表示了一次 I/O 操作所涉及到的所有內(nèi)存頁(yè)。

/*
 * I/O 操作的主要單元，針對(duì) I/O塊和更低級(jí)的層 (ie drivers and
 * stacking drivers)
 */
struct bio {
    sector_t        bi_sector;    /* 磁盤(pán)上相關(guān)扇區(qū) */
    struct bio        *bi_next;    /* 請(qǐng)求列表 */
    struct block_device    *bi_bdev; /* 相關(guān)的塊設(shè)備 */
    unsigned long        bi_flags;    /* 狀態(tài)和命令標(biāo)志 */
    unsigned long        bi_rw;        /* 讀還是寫(xiě) */

    unsigned short        bi_vcnt;    /* bio_vecs的數(shù)目 */
    unsigned short        bi_idx;        /* bio_io_vect的當(dāng)前索引 */

    /* Number of segments in this BIO after
     * physical address coalescing is performed.
     * 結(jié)合后的片段數(shù)目
     */
    unsigned int        bi_phys_segments;

    unsigned int        bi_size;    /* 剩余 I/O 計(jì)數(shù) */

    /*
     * To keep track of the max segment size, we account for the
     * sizes of the first and last mergeable segments in this bio.
     * 第一個(gè)和最后一個(gè)可合并的段的大小
     */
    unsigned int        bi_seg_front_size;
    unsigned int        bi_seg_back_size;

    unsigned int        bi_max_vecs;    /* bio_vecs數(shù)目上限 */
    unsigned int        bi_comp_cpu;    /* 結(jié)束CPU */

    atomic_t        bi_cnt;        /* 使用計(jì)數(shù) */
    struct bio_vec        *bi_io_vec;    /* bio_vec 鏈表 */
    bio_end_io_t        *bi_end_io; /* I/O 完成方法 */
    void            *bi_private;    /* bio結(jié)構(gòu)體創(chuàng)建者的私有方法 */
#if defined(CONFIG_BLK_DEV_INTEGRITY)
    struct bio_integrity_payload *bi_integrity;  /* data integrity */
#endif
    bio_destructor_t    *bi_destructor;    /* bio撤銷(xiāo)方法 */
    /*
     * We can inline a number of vecs at the end of the bio, to avoid
     * double allocations for a small number of bio_vecs. This member
     * MUST obviously be kept at the very end of the bio.
     * 內(nèi)嵌在結(jié)構(gòu)體末尾的 bio 向量，主要為了防止出現(xiàn)二次申請(qǐng)少量的 bio_vecs
     */
    struct bio_vec        bi_inline_vecs[0];
};

幾個(gè)重要字段說(shuō)明：

• bio 結(jié)構(gòu)體表示正在執(zhí)行的 I/O 操作相關(guān)的信息。
• bio_io_vec 鏈表表示當(dāng)前 I/O 操作涉及到的內(nèi)存頁(yè)
• bio_vec 結(jié)構(gòu)體表示 I/O 操作使用的片段
• bi_vcnt bi_io_vec鏈表中bi_vec的個(gè)數(shù)
• bi_idx 當(dāng)前的 bi_vec片段，通過(guò) bi_vcnt（總數(shù)）和 bi_idx（當(dāng)前數(shù)），就可以跟蹤當(dāng)前 I/O 操作的進(jìn)度

bio_vec 結(jié)構(gòu)體很簡(jiǎn)單，定義如下：

struct bio_vec {
    struct page    *bv_page;       /* 對(duì)應(yīng)的物理頁(yè) */
    unsigned int    bv_len;     /* 緩沖區(qū)大小 */
    unsigned int    bv_offset;  /* 緩沖區(qū)開(kāi)始的位置 */
};

每個(gè) bio_vec 都是對(duì)應(yīng)一個(gè)頁(yè)面，從而保證內(nèi)核能夠方便高效的完成 I/O 操作

2.3 2種方法的對(duì)比

緩沖區(qū)頭和bio并不是相互矛盾的，bio只是緩沖區(qū)頭的一種改善，將以前緩沖區(qū)頭完成的一部分工作移到bio中來(lái)完成。

bio中對(duì)應(yīng)的是內(nèi)存中的一個(gè)個(gè)頁(yè)，而緩沖區(qū)頭對(duì)應(yīng)的是磁盤(pán)中的一個(gè)塊。

對(duì)內(nèi)核來(lái)說(shuō)，配合使用bio和緩沖區(qū)頭 比 只使用緩沖區(qū)頭更加的方便高效。

bio相當(dāng)于在緩沖區(qū)上又封裝了一層，使得內(nèi)核在 I/O操作時(shí)只要針對(duì)一個(gè)或多個(gè)內(nèi)存頁(yè)即可，不用再去管理磁盤(pán)塊的部分。

使用bio結(jié)構(gòu)體還有以下好處：

• bio結(jié)構(gòu)體很容易處理高端內(nèi)存，因?yàn)樗幚淼氖莾?nèi)存頁(yè)而不是直接指針
• bio結(jié)構(gòu)體既可以代表普通頁(yè)I/O，也可以代表直接I/O
• bio結(jié)構(gòu)體便于執(zhí)行分散-集中（矢量化的）塊I/O操作，操作中的數(shù)據(jù)可以取自多個(gè)物理頁(yè)面

3. 內(nèi)核I/O調(diào)度程序

緩沖區(qū)頭和bio都是內(nèi)核處理一個(gè)具體I/O操作時(shí)涉及的概念。

但是內(nèi)核除了要完成I/O操作以外，還要調(diào)度好所有I/O操作請(qǐng)求，盡量確保每個(gè)請(qǐng)求能有個(gè)合理的響應(yīng)時(shí)間。

下面就是目前內(nèi)核中已有的一些 I/O 調(diào)度算法。

3.1 linus電梯

為了保證磁盤(pán)尋址的效率，一般會(huì)盡量讓磁頭向一個(gè)方向移動(dòng)，等到頭了再反過(guò)來(lái)移動(dòng)，這樣可以縮短所有請(qǐng)求的磁盤(pán)尋址總時(shí)間。

磁頭的移動(dòng)有點(diǎn)類(lèi)似于電梯，所有這個(gè) I/O 調(diào)度算法也叫電梯調(diào)度。

linux中的第一個(gè)電梯調(diào)度算法就是 linus本人所寫(xiě)的，所有也叫做 linus 電梯。

linus電梯調(diào)度主要是對(duì)I/O請(qǐng)求進(jìn)行合并和排序。

當(dāng)一個(gè)新請(qǐng)求加入I/O請(qǐng)求隊(duì)列時(shí)，可能會(huì)發(fā)生以下4種操作:

1. 如果隊(duì)列中已存在一個(gè)對(duì)相鄰磁盤(pán)扇區(qū)操作的請(qǐng)求，那么新請(qǐng)求將和這個(gè)已存在的請(qǐng)求合并成一個(gè)請(qǐng)求
2. 如果隊(duì)列中存在一個(gè)駐留時(shí)間過(guò)長(zhǎng)的請(qǐng)求，那么新請(qǐng)求之間查到隊(duì)列尾部，防止舊的請(qǐng)求發(fā)生饑餓
3. 如果隊(duì)列中已扇區(qū)方向?yàn)樾虼嬖诤线m的插入位置，那么新請(qǐng)求將被插入該位置，保證隊(duì)列中的請(qǐng)求是以被訪問(wèn)磁盤(pán)物理位置為序進(jìn)行排列的
4. 如果隊(duì)列中不存在合適的請(qǐng)求插入位置，請(qǐng)求將被插入到隊(duì)列尾部

linus電梯調(diào)度程序在2.6版的內(nèi)核中被其他調(diào)度程序所取代了。

3.2 最終期限I/O調(diào)度

linus電梯調(diào)度主要考慮了系統(tǒng)的全局吞吐量，對(duì)于個(gè)別的I/O請(qǐng)求，還是有可能造成饑餓現(xiàn)象。

而且讀寫(xiě)請(qǐng)求的響應(yīng)時(shí)間要求也是不一樣的，一般來(lái)說(shuō)，寫(xiě)請(qǐng)求的響應(yīng)時(shí)間要求不高，寫(xiě)請(qǐng)求可以和提交它的應(yīng)用程序異步執(zhí)行，

但是讀請(qǐng)求一般和提交它的應(yīng)用程序時(shí)同步執(zhí)行，應(yīng)用程序等獲取到讀的數(shù)據(jù)后才會(huì)接著往下執(zhí)行。

因此在 linus 電梯調(diào)度程序中，還可能造成 寫(xiě)-饑餓-讀（wirtes-starving-reads）這種特殊問(wèn)題。

為了盡量公平的對(duì)待所有請(qǐng)求，同時(shí)盡量保證讀請(qǐng)求的響應(yīng)時(shí)間，提出了最終期限I/O調(diào)度算法。

最終期限I/O調(diào)度 算法給每個(gè)請(qǐng)求設(shè)置了超時(shí)時(shí)間，默認(rèn)情況下，讀請(qǐng)求的超時(shí)時(shí)間500ms，寫(xiě)請(qǐng)求的超時(shí)時(shí)間是5s

但一個(gè)新請(qǐng)求加入到I/O請(qǐng)求隊(duì)列時(shí)，最終期限I/O調(diào)度和linus電梯調(diào)度相比，多出了以下操作:

1. 新請(qǐng)求加入到 排序隊(duì)列(order-FIFO)，加入的方法類(lèi)似 linus電梯新請(qǐng)求加入的方法
2. 根據(jù)新請(qǐng)求的類(lèi)型，將其加入 讀隊(duì)列(read-FIFO) 或者寫(xiě)隊(duì)列(wirte-FIFO) 的尾部（讀寫(xiě)隊(duì)列是按加入時(shí)間排序的，所以新請(qǐng)求都是加到尾部）
3. 調(diào)度程序首先判斷 讀，寫(xiě)隊(duì)列頭的請(qǐng)求是否超時(shí)，如果超時(shí)，從讀，寫(xiě)隊(duì)列頭取出請(qǐng)求，加入到派發(fā)隊(duì)列(dispatch-FIFO)
4. 如果沒(méi)有超時(shí)請(qǐng)求，從 排序隊(duì)列(order-FIFO)頭取出一個(gè)請(qǐng)求加入到 派發(fā)隊(duì)列(dispatch-FIFO)
5. 派發(fā)隊(duì)列(dispatch-FIFO)按順序?qū)⒄?qǐng)求提交到磁盤(pán)驅(qū)動(dòng)，完成I/O操作

最終期限I/O調(diào)度 算法也不能?chē)?yán)格保證響應(yīng)時(shí)間，但是它可以保證不會(huì)發(fā)生請(qǐng)求在明顯超時(shí)的情況下仍得不到執(zhí)行。

最終期限I/O調(diào)度 的實(shí)現(xiàn)參見(jiàn): block/deadline-iosched.c

3.3 預(yù)測(cè)I/O調(diào)度

最終期限I/O調(diào)度算法優(yōu)先考慮讀請(qǐng)求的響應(yīng)時(shí)間，但系統(tǒng)處于寫(xiě)操作繁重的狀態(tài)時(shí)，會(huì)大大降低系統(tǒng)的吞吐量。

因?yàn)樽x請(qǐng)求的超時(shí)時(shí)間比較短，所以每次有讀請(qǐng)求時(shí)，都會(huì)打斷寫(xiě)請(qǐng)求，讓磁盤(pán)尋址到讀的位置，完成讀操作后再回來(lái)繼續(xù)寫(xiě)。

這種做法保證讀請(qǐng)求的響應(yīng)速度，卻損害了系統(tǒng)的全局吞吐量（磁頭先去讀再回來(lái)寫(xiě)，發(fā)生了2次尋址操作）

預(yù)測(cè)I/O調(diào)度算法是為了解決上述問(wèn)題而提出的，它是基于最終期限I/O調(diào)度算法的。

但有一個(gè)新請(qǐng)求加入到I/O請(qǐng)求隊(duì)列時(shí)，預(yù)測(cè)I/O調(diào)度與最終期限I/O調(diào)度相比，多了以下操作:

1. 新的讀請(qǐng)求提交后，并不立即進(jìn)行請(qǐng)求處理，而是有意等待片刻(默認(rèn)是6ms)
2. 等待期間如果有其他對(duì)磁盤(pán)相鄰位置進(jìn)行讀操作的讀請(qǐng)求加入，會(huì)立刻處理這些讀請(qǐng)求
3. 等待期間如果沒(méi)有其他讀請(qǐng)求加入，那么等待時(shí)間相當(dāng)于浪費(fèi)掉
4. 等待時(shí)間結(jié)束后，繼續(xù)執(zhí)行以前剩下的請(qǐng)求

預(yù)測(cè)I/O調(diào)度算法中最重要的是保證等待期間不要浪費(fèi)，也就是提高預(yù)測(cè)的準(zhǔn)確性，

目前這種預(yù)測(cè)是依靠一系列的啟發(fā)和統(tǒng)計(jì)工作，預(yù)測(cè)I/O調(diào)度程序會(huì)跟蹤并統(tǒng)計(jì)每個(gè)應(yīng)用程序的I/O操作習(xí)慣，以便正確預(yù)測(cè)應(yīng)用程序的讀寫(xiě)行為。

如果預(yù)測(cè)的準(zhǔn)確率足夠高，那么預(yù)測(cè)I/O調(diào)度和最終期限I/O調(diào)度相比，既能提高讀請(qǐng)求的響應(yīng)時(shí)間，又能提高系統(tǒng)吞吐量。

預(yù)測(cè)I/O調(diào)度的實(shí)現(xiàn)參見(jiàn): block/as-iosched.c

注:預(yù)測(cè)I/O調(diào)度是linux內(nèi)核中缺省的調(diào)度程序。

3.4 完全公正的排隊(duì)I/O調(diào)度

完全公正的排隊(duì)(Complete Fair Queuing, CFQ)I/O調(diào)度 是為專(zhuān)有工作負(fù)荷設(shè)計(jì)的，它和之前提到的I/O調(diào)度有根本的不同。

CFQ I/O調(diào)度 算法中，每個(gè)進(jìn)程都有自己的I/O隊(duì)列，

CFQ I/O調(diào)度程序以時(shí)間片輪轉(zhuǎn)調(diào)度隊(duì)列，從每個(gè)隊(duì)列中選取一定的請(qǐng)求數(shù)(默認(rèn)4個(gè))，然后進(jìn)行下一輪調(diào)度。

CFQ I/O調(diào)度在進(jìn)程級(jí)提供了公平，它的實(shí)現(xiàn)位于: block/cfq-iosched.c

3.5 空操作的I/O調(diào)度

空操作(noop)I/O調(diào)度幾乎不做什么事情，這也是它這樣命名的原因。

空操作I/O調(diào)度只做一件事情，當(dāng)有新的請(qǐng)求到來(lái)時(shí)，把它與任一相鄰的請(qǐng)求合并。

空操作I/O調(diào)度主要用于閃存卡之類(lèi)的塊設(shè)備，這類(lèi)設(shè)備沒(méi)有磁頭，沒(méi)有尋址的負(fù)擔(dān)。

空操作I/O調(diào)度的實(shí)現(xiàn)位于: block/noop-iosched.c

3.6 I/O調(diào)度程序的選擇

2.6內(nèi)核中內(nèi)置了上面4種I/O調(diào)度，可以在啟動(dòng)時(shí)通過(guò)命令行選項(xiàng) elevator=xxx 來(lái)啟用任何一種。

elevator選項(xiàng)參數(shù)如下:

如果啟動(dòng)預(yù)測(cè)I/O調(diào)度，啟動(dòng)的命令行參數(shù)中加上 elevator=as