系統中能夠 隨機訪問 固定大小數據片的設備被稱為塊設備，這些數據片稱作塊，最常見的塊設備是硬盤。

另一種基本的設備類型是字符設備。字符設備按照字符流的方法被有序訪問，像串口和鍵盤就都屬于字符設備。

如果一個硬件設備是以字符流的方法被訪問的話，那就將它歸于字符設備；反過來，如果一個設備是隨機（無序）訪問的，那么它就屬于塊設備。這兩種類型的設備的根據區別在于是否可以隨機訪問，就是能否在訪問設備時隨意地 從一個位置跳轉到另一個位置。

內核管理塊設備要比管理字符設備細致得多，需要考慮的問題和完成的工作相比字符設備來說要復雜的多。這是因為字符設備僅僅需要控制當前位置一個位置，而塊設備訪問的位置必須能夠在介質的不同區間移動。所以事實上內核不必提供一個專門的子系統來管理字符設備，但是對塊設備的管理卻必須要有一個專門的提供服務子系統。

1 解刨一個塊設備

塊設備最小的可尋址單元是扇區。扇區大小一般是2的整數倍，扇區的大小是設備的物理屬性，扇區是所有塊設備的基本單元，塊設備無法對比扇區還小的單元進行尋址和操作。

塊是文件系統的一種抽象，只能基于塊來訪問文件系統。雖然物理磁盤尋址是按照扇區級進行的，但是內核執行的所有磁盤操作都是按照塊進行的。由于扇區是設備的最小可尋址單元，所以塊不能比扇區還小，只能數倍于扇區的大小，另外內核還要求塊大小是2的整數倍，而且不能超過一個頁的長度。所以，對塊大小的最終要求是，必須是扇區大小的2的整數倍，并且要小于頁面大小。

我們在這總結，扇區：設備的最小尋址單元，有時會被稱作硬扇區或設備塊。塊：文件系統的最小尋址單元，有時會被稱作文件塊或I/O塊。

2 緩沖區和緩沖區頭

當一個塊被調入內存時，它要存儲在一個緩沖區。每個緩沖區與一個塊對應，前面提到過，塊包含一個或多個扇區，但大小不能超過一個頁面，所以一個頁可以容納一個或多個內存中的塊。由于內核在處理數據時需要一些相關的控制信息，所以每一個緩沖區都有一個對應的描述符，該描述符用buffer_head表示，被稱作緩沖區頭，在文件linux/buffer_head.h中定義，它包含了內核操作緩沖區所需要的全部信息。

/** Keep related fields in common cachelines.  The most commonly accessed* field (b_state) goes at the start so the compiler does not generate* indexed addressing for it.*/
struct buffer_head {/* First cache line: */unsigned long b_state;		/* buffer state bitmap (see above) */struct buffer_head *b_this_page;/* circular list of page's buffers */struct page *b_page;		/* the page this bh is mapped to */atomic_t b_count;		/* users using this block */u32 b_size;			/* block size */sector_t b_blocknr;		/* block number */char *b_data;			/* pointer to data block */struct block_device *b_bdev;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 with another mapping */
};

緩沖區頭的目的在于描述磁盤塊和物理內存緩沖區之間的映射關系。這個結構體在內核中只扮演一個角色，說明從緩沖區到塊的映射關系。

在2.6內核以前，緩沖區頭的作用比現在還重要。因為緩沖區頭作為內核的I/O操作單元，不僅僅描述了從磁盤塊到物理內存的映射，而且還是所有塊I/O操作的容器。可是，將緩沖區頭作為I/O操作單元帶來了兩個弊端。

• 首先，緩沖區頭是一個很大且不易控制的數據結構體，而且緩沖區頭對數據的操作既不方便，也不清晰。
• 僅能描述單個緩沖區，當作為所有I/O的容器使用時，緩沖區頭會迫使內核打斷對大塊數據的I/O操作，使其成為對多個buffer_head結構體進行操作。這樣做必然會造成不必要的負擔和空間浪費。

所以2.5開發版內核的主要目標就是為塊I/O操作引入一種新型、靈活并且輕量級的容器，也就是下面要介紹的bio結構體。

3 bio結構體

目前內核中塊I/O操作的基本容器由bio結構體表示，它定義在文件linux/bio.h中，該結構體代表了正在現場的以片斷鏈表形式組織的I/O操作。一個片段是一小塊連續的內存緩存區。這樣的話，就不需要保證單個緩沖區一定要連續。所以通過片段來描述緩沖區，即使一個緩沖區分散在內存的多個位置上，bio結構體也能對內核保證I/O操作的執行。

/** main unit of I/O for the block layer and lower layers (ie drivers and* stacking drivers)*/
struct bio {sector_t		bi_sector;struct bio		*bi_next;	/* request queue link */struct block_device	*bi_bdev;unsigned long		bi_flags;	/* status, command, etc */unsigned long		bi_rw;		/* bottom bits READ/WRITE,* top bits priority*/unsigned short		bi_vcnt;	/* how many bio_vec's */unsigned short		bi_idx;		/* current index into bvl_vec *//* Number of segments in this BIO after* physical address coalescing is performed.*/unsigned short		bi_phys_segments;/* Number of segments after physical and DMA remapping* hardware coalescing is performed.*/unsigned short		bi_hw_segments;unsigned int		bi_size;	/* residual I/O count *//** To keep track of the max hw size, we account for the* sizes of the first and last virtually mergeable segments* in this bio*/unsigned int		bi_hw_front_size;unsigned int		bi_hw_back_size;unsigned int		bi_max_vecs;	/* max bvl_vecs we can hold */struct bio_vec		*bi_io_vec;	/* the actual vec list */bio_end_io_t		*bi_end_io;atomic_t		bi_cnt;		/* pin count */void			*bi_private;bio_destructor_t	*bi_destructor;	/* destructor */
};

使用bio結構體的目的主要是代表正在現場執行的I/O操作，所以該結構體中的主要域都是用來管理相關信息的，其中最重要的幾個域是bi_io_vecs、bi_vcnt和bi_idx。
bi_io_vecs域指向一個bio_vec結構體數組，該結構體鏈表包含一個特定I/O操作所需要使用的所有片段。每個bio_vec結構都是一個形式<page,offset,len>的向量，它描述的是一個特定的片段：片段所在的物理頁、塊在物理頁中的偏移位置、從給定偏移量開始的塊長度。整個bio_io_vec結構體數組表示了一個完整的緩沖區。bio_vec結構體定義在linux/bio.h文件中。

/** was unsigned short, but we might as well be ready for > 64kB I/O pages*/
struct bio_vec {struct page	*bv_page;	/* 指向這個緩沖區所駐留的物理頁 */unsigned int	bv_len; /* 這個緩沖區以字節為單位的大小 */unsigned int	bv_offset;	/* 緩沖區所駐留的頁中以字節為單位的偏移量 */
};

在每個給定的塊I/O操作中，bi_vcnt域用來描述bi_io_vec所指向的bio_vec數組中的向量數目，當塊I/O操作執行完畢后，bi_idx域指向數組的當前bio_vec片段。bi_cnt域記錄bio結構體的使用計數，如果該域值減為0，就應該銷毀該bio結構體，并釋放它所占用的內存。

新老方法對比

緩沖區頭和新的bio結構體之間存在明顯差別，bio結構體代表的是I/O操作，它可以包括內存中的一個或多個頁，另一方面，buffer_head結構體代表一個緩沖區，它描述的是磁盤中的一個塊。因為緩沖區頭關聯的是單獨頁中的單獨磁盤塊，所以它可能會引起不必要的分割，將請求按塊為單位劃分，只能靠以后才能再重新組合，由于bio結構是輕量級的，它描述的塊可以不需要連續存儲區，并且不需要分割I/O操作。

4 請求隊列

塊設備將它們掛起的塊I/O請求保存在請求隊列中，該隊列由reques_queue結構體表示，定義在文件linux/blkdev.h中，包含一個雙向請求鏈表以及相關控制信息。通過內核中像文件系統這樣高層的代碼將請求加入隊列中，請求隊列只要不為空，隊列對應的塊設備驅動程序就會從隊列頭獲取請求，然后將其送入對應的塊設備上去，請求隊列表中的每一項都是一個單獨的請求，由request結構體表示，它定義在文件linux/blkdev.h中，因為一個請求可能要操作多個連續的操作塊，所以每個請求可以由多個bio結構體組成。注意，雖然磁盤上的塊必須連續，但是在內存中這些塊并不一定要連續，每個bio結構體都可以描述多個片段，而每個請求也可以包含多個bio結構體。

5 I/O調度程序

如果簡單地以內核產生請求的次序直接將請求發向塊設備的話，性能肯定讓人難以接受。磁盤尋址是整個計算機中最慢的操作之一，所以盡量縮短尋址時間無疑是提供系統性能的關鍵。

為了優化尋址操作，內核既不會簡單地按請求接受次序，也不會立即將其提交給磁盤。相反，它會在提交前，先執行名為合并與排序的預操作，這種操作可以極大地提高系統的整體性能。在內核中負責提交I/O請求的子系統被稱為I/O調度程序。

I/O調度程序將磁盤I/O資源分配給系統中所有掛起的塊I/O請求，具體來說，這種資源分配是通過將請求隊列中掛起的請求合并和排序來完成的。注意不要將I/O調度程序和進程調度程序混淆。進程調度程序的作用是將處理器資源分配給系統中的運行進程。進程調度程序和I/O調度程序都是將一個資源虛擬給多個對象，對進程調度程序來說，處理器被虛擬并被系統中的運行進程共享。I/O調度程序虛擬塊設備給多個磁盤請求，以便降低磁盤尋址時間。

I/O調度程序的工作

I/O調度程序的工作是管理塊設備的請求隊列。它決定隊列中的請求排序順序以及在什么時刻派發請求到塊設備。這樣做有利于減少磁盤尋址時間。

I/O調度程序通過兩種方法減少磁盤尋址時間：合并與排序。合并指將兩個或多個請求結合成一個新請求。比如系統文件提交請求到請求隊列，如果這是請求隊列已經存在一個請求，并且它訪問的磁盤扇區和當前請求訪問的磁盤扇區相鄰，那么這兩個請求就可以合并為一個對單個和多個相鄰磁盤扇區操作的新請求。通過合并請求，I/O調度程序就可以將多次請求的開銷壓縮成一次請求的開銷，請求合并和只需要傳遞給磁盤一條尋址命令，就可以訪問到請求合并前必須多次尋址才能訪問完的磁盤區域了，因此合并請求能減少系統開銷和磁盤尋址次數。

注意，相鄰的磁盤才可以合并，如果請求隊列中沒有與當前請求磁盤扇區相鄰，就不能合并，會將其插入請求隊列的尾部。I/O調度程序將整個請求隊列按扇區增長方向有序排序，使所有請求按硬盤扇區的排序順序有序排列的目的不僅是為了縮短單獨一次請求的尋址時間，更重要的是，通過保持磁盤頭以直線方向移動，縮短了所有請求的磁盤尋址時間。該排序算法類似于電梯調度，電梯不能隨意的從一層跳到另一層，它應該向一個方向移動，當抵達同一方向上的最后一層后，再掉頭向另一個方向移動。處于這種相似性，所以I/O調度程序被稱為電梯調度。

Linus電梯

在2.4內核中，Linus電梯是默認的I/O調度程序。雖然后來在2.6內核中它被另外兩種調度程序取替了，但是由于這個電梯算法比后來的調度程序簡單，而且它們執行的許多功能類似，所以仍然值得討論一下。

Linus電梯能執行合并與排序預處理。當有新的請求加入隊列時，它首先會檢查其他每一個掛起的請求是否可以和新請求合并（請求的扇區是否相鄰）。如果合并嘗試失敗，那么就需要尋找可能的插入點（新請求在隊列中的位置必須符合請求以扇區方向有序排序的原則）。如果找到，請求將被插入到該點，如果沒有合適的位置，那么新請求就被加入到隊列尾部。另外，如果發現隊列中有駐留時間過長的請求，那么新請求也將被加入到隊列尾部，即使插入后還要排序。這樣做是為了避免由于訪問相近磁盤位置的請求太多，從而造成訪問磁盤其他位置的請求難以得到執行機會這一問題。不幸的事，這種方案并不很有效，因為它僅僅是在經過一段時間后停止插入，并非是給等待了一段時間的請求提供實質性服務，這改善了等待時間但最終還是會導致請求饑餓現象的發生。

總而言之，當一個請求加入大隊列時，有可能發生四種操作，它們依次是：

• 如果隊列中已存在一個相鄰磁盤扇區操作，那么新請求將和這個已經存在的請求合并成一個請求。
• 如果隊列中存在一個駐留時間過長的請求，那么新請求將被插入到隊列尾部，以防止舊的其他請求發生饑餓
• 如果隊列中以扇區方向為序存在合適的插入位置，那么新的請求將被插入到該位置，保證隊列中的請求是以被訪問磁盤物理位置為序進行排序的
• 如果隊列中不存在合適的請求插入位置，請求將被插入隊列尾部

最終期限I/O調度程序

最終期限I/O調度程序是為了解決Linus電梯所帶來的饑餓問題而提出來的。出于減少磁盤尋址時間的考慮，對某個磁盤區域上的繁重操作，無疑會使得磁盤其他位置上的操作請求得不到運行機會。

如下圖，在最后期限I/O調度程序中，每個請求都有一個超時時間。默認情況下，讀請求的超時時間是500毫秒，寫請求的超時時間是5秒。最后期限I/O調度請求類似于Linus電梯，也以磁盤物理位置為次序維護請求隊列這個隊列被稱為排序隊列。當一個新請求遞交給排序隊列時，最后期限I/O調度程序類似于Linus電梯，合并插入請求，但是最后期限I/O調度程序同時也會以請求類型為依據將它們插入到額外隊列中。讀請求按次序被插入到特定的讀FIFO隊列中，寫請求被插入到特定的寫FIFO隊列中。雖然普通隊列以磁盤扇區為序進行排序，但是這些隊列（寫請求、讀請求）是以FIFO組織的。

對于普通操作來說，最后期限I/O調度程序將請求從排序隊列的頭部取下，再推入到派發隊列中，派發隊然后將請求提交給磁盤驅動，從而保證了最小化的請求尋址。如果在寫FIFO隊列頭，或是在讀FIFO隊列頭的請求超時，那么最后期限I/O調度程序便從FIFO隊列中提取請求進行服務，依靠這種方法，最后期限I/O調度程序試圖保證不會發生有請求在明顯超期的情況下仍不能得到服務的現象。

最后期限I/O調度程序的實現在文件drivers/block/deadline-iosche.c中。

預測I/O調度程序

預測I/O調度程序在最終期限調度程序的基礎上，增加了一個空閑時間，也就說當請求提交后，不會立即返回處理其他請求，而是可以空閑幾個ms，等待磁盤相鄰位置的請求。對于應用程序來說，這是一個提交請求的機會，任何相鄰磁盤位置操作請求都會得到立即處理。在等待時間結束后，預測IO處理程序返回原來位置基礎執行以前剩下的請求。如果一個相鄰磁盤位置的請求在空閑時刻到來，那么它就會立刻得到執行，從而減小了二次尋址。

完全公正的排隊I/O調度程序

該方法是為了專有工作負荷設計的，在實際中也為多掙工作負荷提供了較好的性能。該方法是將I/O請求根據引起該請求的進程來組織的，比如進程foo發起的請求放進foo隊列，bar進程發起的請求放入bar隊列。然后，以時間輪片一次從每個隊列中選取請求。

空操作的I/O調度程序

所謂空操作是指，該調度方法僅僅進行請求的合并，而不進行其他操作。這主要針對閃存這一類的塊設備，這類設備是正在的隨機存儲，沒有必要按序訪問。

I/O調度程序的選擇

在2.6內核中，有以上四種不同的I/O調度程序，每一種I/O調度程序都可以被啟用，并內置在內核中，作為默認，塊設備使用預測I/O調度程序，在啟動時，可以通過命令行選項elevator = foo來覆蓋默認，這里foo是一個有效而激活I/O調度程序。如下表：

內核命令行選項elevator=cfq會啟用完全公正的I/O調度程序給所有的塊設備。