如果硬件設(shè)備是以數(shù)據(jù)流的方式訪問的囚企，它就是字符設(shè)備（character device）铝侵，但如果是隨機訪問的就是塊設(shè)備（block device）予跌，典型的如硬盤
sector（扇區(qū)）
The smallest addressable unit on a block device is a sector. Sectors come in various powers of two, but 512 bytes is the most common size
塊設(shè)備上最小訪問單元是扇區(qū)（sector）榆纽，一般512字節(jié)大小
雖然最小物理訪問單元是扇區(qū)动遭，但是軟件的最小邏輯訪問單元是塊（block）芬探，它是扇區(qū)大小的2的冪次方倍，一般為512 bytes, 1 kilobyte, and 4 kilobytes厘惦，但不會超過頁大型捣隆（人為限制），那是管理內(nèi)存的最小單位宵蕉。
block（塊）
文件系統(tǒng)都是以塊為單位來操作磁盤的酝静，CPU是不能直接操作磁盤上的數(shù)據(jù)，必須先把它們讀到內(nèi)存中羡玛，那么內(nèi)存中存儲一塊大小的數(shù)據(jù)叫做buffer别智，buffer就是磁盤上一塊大小的數(shù)據(jù)在內(nèi)存中表示，那這個buffer對應(yīng)哪個塊設(shè)備上的哪塊就需要內(nèi)核來管理稼稿，內(nèi)核使用buffer_head這個數(shù)據(jù)結(jié)構(gòu)來描述block和buffer的關(guān)系
struct buffer_head {
unsigned long b_state; /* buffer state flags */
struct buffer_head *b_this_page; /* list of page’s buffers */
struct page *b_page; /* associated page 塊對應(yīng)的物理頁 */
sector_t b_blocknr;/* starting block number */
size_t b_size;/* size of mapping 塊的大小*/
char *b_data;/* pointer to data within the page 塊的地址*/
struct block_device *b_bdev;/* associated block device */
bh_end_io_t *b_end_io;/* I/O completion */
void *b_private;/* reserved for b_end_io */
struct list_head b_assoc_buffers; /* associated mappings */
struct address_space *b_assoc_map; /* associated address space */
atomic_t b_count; /* use count */
};
在2.6之前薄榛，buffer_header在內(nèi)核中得以重用讳窟，它是塊設(shè)備IO的單位和容器,但這個結(jié)構(gòu)有點大，用它來操作數(shù)據(jù)既不簡潔也不簡單敞恋，內(nèi)核更擅長用頁來處理丽啡，這樣既簡單又高效；另一方面buffer_header只能描述單個buffer硬猫，如果要操作大塊數(shù)據(jù)勢必要分成多個buffer_header补箍，導(dǎo)致無謂的開銷。于是在2.5版本就重點開發(fā)了bio結(jié)構(gòu)作為block I/O操作的容器
bio結(jié)構(gòu)
bio數(shù)據(jù)結(jié)構(gòu)以段的形式將buffers組織在一起啸蜜，這些buffers在內(nèi)存中不必是連續(xù)的
struct bio {
...
unsigned short bi_vcnt;/* number of bio_vec */
struct bio_vec *bi_io_vec; /* bio_vec list */
...
}
bio結(jié)構(gòu)體含有bio_vec數(shù)組坑雅，圖上它們指向某個page，但并不表示指向整個page盔性，而是其中一段霞丧，每個 bio_vec 就是這樣一個三元組（page, offset, len）, 哪塊物理頁呢岗，偏移多少字節(jié)冕香、長度多少就定位了一塊buffer
struct bio_vec {
struct page *bv_page;/* pointer to the physical page on which this buffer resides */
unsigned int bv_len;/* the length in bytes of this buffer */
unsigned int bv_offset;/* the byte offset within the page where the buffer resides */
};
bio結(jié)構(gòu)體的優(yōu)點
- 可以輕松表示高內(nèi)存，因為它只處理物理頁而不是指針
- 既能表示普通page I/O也能表示direct I/O（不需要頁緩存）
- 很容易實現(xiàn)scatter-gatter I/O 塊操作
- 相比buffer_header,僅包含I/O 塊操作的最小信息后豫，不會包含與buffer無關(guān)的信息
但bio并不能替代buffer_header,它不能描述buffer的狀態(tài)悉尾，所以需要兩者共存互補。
IO調(diào)度器
一個運行的系統(tǒng)挫酿，每時每刻都會有不同的進程發(fā)起IO請求构眯，這些請求都會放在一個請求隊列中，用 <linux/blkdev.h>中的request_queue結(jié)構(gòu)體表示早龟，隊列中的每個請求用request結(jié)構(gòu)體表示惫霸，它是由多個bio結(jié)構(gòu)體組成。
計算機中的硬盤是為數(shù)不多的機械裝置葱弟，它讀寫數(shù)據(jù)的速度與內(nèi)存相比都是上萬倍的差距壹店，由于是機械裝置，磁頭對扇區(qū)的尋址是計算機中最慢的操作之一芝加，如果對IO請求逐個處理不做全局優(yōu)化硅卢，計算機的性能將顯著降低，比如下面一個請求隊列
- 騎自行車到北京買包中南海
- 騎自行車到上海買包華子
- 騎自行車到北京買一條中南海
- 騎自行車到上海買一條華子
所以IO調(diào)度器的一個重點就是全局考慮隊列的請求藏杖，優(yōu)化尋址時間将塑。
The Linus Elevator
Linux中的最簡單的調(diào)度算法就是電梯調(diào)度算法，主要有四點
- If a request to an adjacent on-disk sector is in the queue, the existing request and the new request merge into a single request.如果IO請求的扇區(qū)和能在隊列中找到毗鄰的蝌麸，合并成一個
- If a request in the queue is sufficiently old, the new request is inserted at the tail of the queue to prevent starvation of the other, older, requests.如果第一步找到的請求存在的時間有點久遠會放棄合并插到隊尾点寥，否則對同一位置的頻繁請求會導(dǎo)致后面的請求無法響應(yīng)
- If a suitable location sector-wise is in the queue, the new request is inserted there. This keeps the queue sorted by physical location on disk.調(diào)度算法會按照請求的扇區(qū)對請求排序，根據(jù)新請求扇區(qū)的位置將其插入到隊列中合適的位置来吩，這樣隊列中請求的扇區(qū)物理位置是有序的敢辩，磁頭像電梯一樣一次只朝一個方向移動處理請求汉柒，避免來回?zé)o序的尋址。
- Finally, if no such suitable insertion point exists, the request is inserted at the tail of the queue.最后如果找不到合適位置就會插在隊尾
The Deadline(截止日期) I/O Scheduler
電梯調(diào)度算法雖然顧全大局责鳍，能極有效的處理磁頭移動碾褂，但仍然沒解決請求餓死的問題，首先說說數(shù)據(jù)的讀或?qū)懙奶卣骼穑瑢嶋H上它們截然不同
進程是不可以直接將數(shù)據(jù)寫到磁盤的正塌，進程只是把寫請求和相關(guān)數(shù)據(jù)等信息提交到內(nèi)核，然后就返回了恤溶，是異步的乓诽，內(nèi)核為了性能也不會立馬將數(shù)據(jù)寫回磁盤，它有一個專門的進程周期性的將緩存的數(shù)據(jù)一起寫回磁盤咒程，所以通常是較大的數(shù)據(jù)流鸠天，這些寫入請求傾向于寫到磁盤相近的地方，很符合電梯調(diào)度算法的胃口帐姻，導(dǎo)致這個算法傾向于滿頭苦寫無法自拔
進程也是不能直接讀取磁盤上的數(shù)據(jù)稠集，它要發(fā)起讀請求，讓內(nèi)核去撈數(shù)據(jù)饥瓷，但它可不會像寫那樣就返回了剥纷，它要等內(nèi)核給它數(shù)據(jù)才會返回，所以讀操作是同步的呢铆，對等待時長很敏感晦鞋。與寫相比，讀的數(shù)據(jù)通常較小而且不連續(xù)棺克，比如目錄下的文件悠垛，有碎片化的特征，更要命的是還不能同時進行娜谊，這個沒返回是不能讀下一個的确买，有依賴關(guān)系。
由于讀寫的這種矛盾因俐，流式寫請求容易讓后面的讀請求在合理的時間內(nèi)得不到處理拇惋，而產(chǎn)生寫?zhàn)I死讀的問題，比如下面一個請求隊列
- 騎自行車到北京大興送貨
- 騎自行車到北京豐臺送貨
- 騎自行車到北京石景山送貨
- 騎自行車到北京海淀買送貨
- 騎自行車到北京朝陽送貨
- 騎自行車到北京東城送貨
- 騎自行車到上海買包華子
Deadline調(diào)度器在電梯調(diào)度器的Sorted queue基礎(chǔ)上添加了兩個先入先出隊列抹剩，并且每個新請求會設(shè)置一個有效期(expiration time), 讀請求是500ms撑帖，寫請求是5s，新請求不僅會正常插入到Sorted queue澳眷，還會添加到另一個隊列的尾部（如：讀請求到Read FIFO queue）胡嘿，調(diào)度器處理請求和以前一樣，從Sorted queue獲取請求钳踊，但如果Read隊列或Write隊列的隊頭請求要到期了就需要優(yōu)先處理衷敌，也就是讀隊列的請求最久500ms左右能被處理勿侯，而寫隊列是5s，本質(zhì)上就是讓讀請求的優(yōu)先級高于寫請求缴罗，從而避免寫?zhàn)I死讀的情況發(fā)生助琐。
Anticipatory(預(yù)料的) I/O Scheduler
Deadline調(diào)度器在性能和延時兩端做了相當好的平衡，但讀請求碎片化面氓、獨立性兵钮、需同步的特性使得磁頭難免不斷的來回移動，付出昂貴的代價舌界。比如正在處理一堆寫請求流掘譬，間歇的來了一波讀請求(進程在一個讀請求結(jié)束后才會發(fā)起下一個讀請求)，如果兩種請求涉及的扇區(qū)較遠呻拌，那么就有大量時間花費在來回移動磁頭上面葱轩。
Anticipatory就是為了解決這個問題，它在Deadline調(diào)度器的基礎(chǔ)上添加了預(yù)判機制藐握，在處理完讀請求后并不著急離開靴拱，而是賭一把等上6ms，看這個時間內(nèi)能不能等到下個讀請求趾娃，如果等到了就立馬處理然后繼續(xù)等待缭嫡，否則承認猜錯了移動磁頭返回原處缔御。為了提高命中率而不是瞎猜抬闷，Anticipatory調(diào)度器會統(tǒng)計每個進程的IO信息來跟蹤它們的行為，從而做出智能預(yù)判耕突。
以上整理自：
Linux kernel Development - Robert Love
I/O Schedulers
