Linux操作系統(tǒng)I/O調(diào)度記錄

無情的搬用工

使用緩沖區(qū)來提升性能。

I/O調(diào)度

buffer塊緩沖區(qū)

當一個塊被調(diào)入內(nèi)存的時候，它要存儲在一個緩沖區(qū)中。每個緩沖區(qū)與一個塊對應(yīng)，一個頁面可以容納多個內(nèi)存中的塊。

整體來說，Linux 文件緩沖區(qū)分為page cache和buffer cache，每一個 page cache 包含若干 buffer cache。

具體文件系統(tǒng)則一般只與 buffer cache 交互，它們負責在存儲設(shè)備和 buffer cache 之間交換數(shù)據(jù)，具體的文件系統(tǒng)直接操作的就是disk部分，而具體的怎么被包裝被用戶使用是VFS的責任(VFS將buffer cache包裝成page給用戶)。

image.png

對于具體的Linux文件系統(tǒng)，會以block(磁盤塊)的形式組織文件，為了減少對物理塊設(shè)備的訪問，在文件以塊的形式調(diào)入內(nèi)存后，使用塊高速緩存進行管理。每個緩沖區(qū)由兩部分組成，第一部分稱為緩沖區(qū)首部，用數(shù)據(jù)結(jié)構(gòu)buffer_head表示，第二部分是真正的存儲的數(shù)據(jù)。由于緩沖區(qū)首部不與數(shù)據(jù)區(qū)域相連，數(shù)據(jù)區(qū)域獨立存儲。

具體操作流程
hash表：用于管理包含有效數(shù)據(jù)的buffer，在定位buffer的時候很快捷。

542         #define _hashfn(dev,block)      \
543         ((((dev)<<(bh_hash_shift - 6)) ^ ((dev)<<(bh_hash_shift - 9))) ^ \
544          (((block)<<(bh_hash_shift - 6)) ^ ((block) >> 13) ^ \
545           ((block) << (bh_hash_shift - 12))))
  • 1 當我們在一個具有的文件系統(tǒng)中，當我們需要讀取一塊數(shù)據(jù)的時候，需要調(diào)用bread函數(shù)
1189 struct buffer_head * bread(kdev_t dev, int block, int size)
1190 {
1191         struct buffer_head * bh;
1192 
1193         bh = getblk(dev, block, size);    /* 找到這個buffer */
1194         if (buffer_uptodate(bh))  /* 判斷是否存在有效數(shù)據(jù)，如果存在那么直接返回即可 */
1195                 return bh;
1196         set_bit(BH_Sync, &bh->b_state); /* 如果不存在有效數(shù)據(jù)，將這個buffer設(shè)置成同步狀態(tài) */
1197         ll_rw_block(READ, 1, &bh); /* 如果沒有，那么需要從磁盤中讀取這個block到buffer中，這個是一個底層的讀取操作 */
1198         wait_on_buffer(bh);  /* 等待buffer的鎖打開 */
1199         if (buffer_uptodate(bh)) /* 理論上這個時候應(yīng)該是存在有效數(shù)據(jù)的了，直接返回就可以 */
1200                 return bh;
1201         brelse(bh);
1202         return NULL;
1203 }

第一：通過dev號+block號找到相應(yīng)的buffer，使用函數(shù)getblk

1013 struct buffer_head * getblk(kdev_t dev, int block, int size)
1014 {
1015         for (;;) {
1016                 struct buffer_head * bh;
1017 
1018                 bh = get_hash_table(dev, block, size);   /* 關(guān)鍵函數(shù)，得到hash表中的buffer */
1019                 if (bh) {
1020                         touch_buffer(bh);
1021                         return bh;     /* 返回這個buffer */
1022                 }
1023                 /* 如果沒有找到對應(yīng)的buffer，那么試著去增加一個buffer，就是使用下面的grow_buffers函數(shù) */
1024                 if (!grow_buffers(dev, block, size))
1025                         free_more_memory();
1026         }
1027 }

查找buffer函數(shù)：get_hash_table

628 struct buffer_head * get_hash_table(kdev_t dev, int block, int size)
629 {
630         struct buffer_head *bh, **p = &hash(dev, block);   /* 首先通過hash值得到對應(yīng)的位置，這個函數(shù)h很easy */
631 /* 其實就是 #define hash(dev,block) hash_table[(_hashfn(HASHDEV(dev),block) & bh_hash_mask)]。hashfn函數(shù)上面已經(jīng)說過了，就是通過hash值得到buffer*/
632         read_lock(&hash_table_lock);
633 
634         for (;;) {           /* 下面就是判斷這個得到的buffer數(shù)組中有沒有我們需要的buffer */
635                 bh = *p;
636                 if (!bh)
637                         break;
638                 p = &bh->b_next;
639                 if (bh->b_blocknr != block)
640                         continue;
641                 if (bh->b_size != size)
642                         continue;
643                 if (bh->b_dev != dev)
644                         continue;
645                 get_bh(bh);       /* 如果有那么直接執(zhí)行這個函數(shù)，這個函數(shù)很easy，其實就是增加一個使用計數(shù)器而已： atomic_inc(&(bh)->b_count);*/
646                 break;
647         }
648 
649         read_unlock(&hash_table_lock);
650         return bh;
651 }

如果沒有查找到具體的值則調(diào)用grow_buffers：

2596 /*
2597  * Try to increase the number of buffers available: the size argument
2598  * is used to determine what kind of buffers we want.
2599  */
2600 static int grow_buffers(kdev_t dev, unsigned long block, int size)
2601 {
2602         struct page * page;
2603         struct block_device *bdev;
2604         unsigned long index;
2605         int sizebits;
2606 
2607         /* Size must be multiple of hard sectorsize */
2608         if (size & (get_hardsect_size(dev)-1))
2609                 BUG();
2610         /* Size must be within 512 bytes and PAGE_SIZE */
2611         if (size < 512 || size > PAGE_SIZE)
2612                 BUG();
2613 
2614         sizebits = -1;
2615         do {
2616                 sizebits++;
2617         } while ((size << sizebits) < PAGE_SIZE);
2618 
2619         index = block >> sizebits;
2620         block = index << sizebits;
2621 
2622         bdev = bdget(kdev_t_to_nr(dev));
2623         if (!bdev) {
2624                 printk("No block device for %s\n", kdevname(dev));
2625                 BUG();
2626         }
2627 
2628         /* Create a page with the proper size buffers.. */
2629         page = grow_dev_page(bdev, index, size);
2630 
2631         /* This is "wrong" - talk to Al Viro */
2632         atomic_dec(&bdev->bd_count);
2633         if (!page)
2634                 return 0;
2635 
2636         /* Hash in the buffers on the hash list */
2637         hash_page_buffers(page, dev, block, size);
2638         UnlockPage(page);
2639         page_cache_release(page);
2640 
2641         /* We hashed up this page, so increment buffermem */
2642         atomic_inc(&buffermem_pages);
2643         return 1;
2644 }
2645

當前內(nèi)核的塊I/O操作均使用bio結(jié)構(gòu)體表示。詳細的內(nèi)容不講解，但是這個結(jié)構(gòu)可以用來表示某個I/O操作所需要的塊的位置，而這些塊描述了每個片段在物理頁中實際位置

I/O調(diào)度

把收到的IO請求進行合并以便最大化系統(tǒng)吞吐量。

NOOP算法

NOOP算法的全寫為No Operation。該算法實現(xiàn)了最最簡單的FIFO隊列，所有IO請求大致按照先來后到的順序進行操作。之所以說“大致”，原因是NOOP在FIFO的基礎(chǔ)上還做了相鄰IO請求的合并，并不是完完全全按照先進先出的規(guī)則滿足IO請求。

image.png

NOOP是在Linux2。4或更早的版本的使用的唯一調(diào)度算法。由于該算法比較簡單，減了IO占用CPU中的計算時間最少。不過容易造成IO請求餓死。關(guān)于IO餓死的描述如下：因為寫請求比讀請求更容易。寫請求通過文件系統(tǒng)cache，不需要等一次寫完成，就可以開始下一次寫操作，寫請求通過合并，堆積到I/O隊列中。讀請求需要等到它前面所有的讀操作完成，才能進行下一次讀操作。在讀操作之間有幾毫秒時間，而寫請求在這之間就到來 ，餓死了后面的讀請求 。

CFQ算法

該算法的特點是按照IO請求的地址進行排序，而不是按照先來后到的順序來進行響應(yīng)。CFQ為每個進程/線程，單獨創(chuàng)建一個隊列來管理該進程所產(chǎn)生的請求，也就是說每個進程一個隊列，各隊列之間的調(diào)度使用時間片來調(diào)度，以此來保證每個進程都能被很好的分配到I/O帶寬。

image.png

在傳統(tǒng)的SAS盤上，磁盤尋道花去了絕大多數(shù)的IO響應(yīng)時間。CFQ的出發(fā)點是對IO地址進行排序，以盡量少的磁盤旋轉(zhuǎn)次數(shù)來滿足盡可能多的IO請求。在CFQ算法下，SAS盤的吞吐量大大提高了。但是相比于NOOP的缺點是，先來的IO請求并不一定能被滿足，也可能會出現(xiàn)餓死的情況。

DEADLINE算法

最終期限算法（DEADLINE）在CFQ的基礎(chǔ)上，解決了IO請求餓死的極端情況。除了CFQ本身具有的IO排序隊列之外，DEADLINE額外分別為讀IO和寫IO提供了FIFO隊列。讀FIFO隊列的最大等待時間為500ms，寫FIFO隊列的最大等待時間為5s。FIFO隊列內(nèi)的IO請求優(yōu)先級要比CFQ隊列中的高，而讀FIFO隊列的優(yōu)先級又比寫FIFO隊列的優(yōu)先級高。優(yōu)先級可以表示如下：

FIFO(Read) > FIFO(Write) > CFQ

Deadline確保了在一個截止時間內(nèi)服務(wù)請求，這個截止時間是可調(diào)整的，而默認讀期限短于寫期限。這樣就防止了寫操作因為不能被讀取而餓死的現(xiàn)象。

預(yù)先算法

為了滿足隨機IO和順序IO混合的場景，Linux還支持ANTICIPATORY調(diào)度算法。ANTICIPATORY的在DEADLINE的基礎(chǔ)上，為每個讀IO都設(shè)置了6ms的等待時間窗口。如果在這6ms內(nèi)OS收到了相鄰位置的讀IO請求，就可以立即滿足。

本質(zhì)上與Deadline一樣，但在最后一次讀操作后，要等待6ms，才能繼續(xù)進行對其它I/O請求進行調(diào)度。可以從應(yīng)用程序中預(yù)訂一個新的讀請求，改進讀操作的執(zhí)行，但以一些寫操作為代價。它會在每個6ms中插入新的I/O操作，而會將一些小寫入流合并成一個大寫入流，用寫入延時換取最大的寫入吞吐量。AS適合于寫入較多的環(huán)境，比如文件服務(wù)器，但對對數(shù)據(jù)庫環(huán)境表現(xiàn)很差。

避免了許多向后再向前的問題，所以6ms能換來很多優(yōu)勢還是很好的，如果不幸6ms內(nèi)沒有預(yù)期的操作，那么也就只是損失6ms而已。

SSD的erase-before-write

SSD的寫操作比較特殊，SSD的最小寫入單元為4KB，稱為頁(page)，當寫入空白位置時可以按照4KB的單位寫入，但是如果需要改寫某個單元時，則需要一個額外的擦除(erase)動作，如果向一個空白的page寫入信息時，可以直接寫入而無需擦除，但是如果需要改寫某個存儲單元(page)的數(shù)據(jù)，必須首先將整個block讀入緩存，然后修改數(shù)據(jù)，并擦除整個block的數(shù)據(jù)，最后將整個block寫入，很顯然，SSD改寫數(shù)據(jù)的代價很高，SSD的這個特性，我們稱之為erase-before-write。

SSD的erase-before-write

SSD的寫操作比較特殊，SSD的最小寫入單元為4KB，稱為頁(page)，當寫入空白位置時可以按照4KB的單位寫入，但是如果需要改寫某個單元時，則需要一個額外的擦除(erase)動作，如果向一個空白的page寫入信息時，可以直接寫入而無需擦除，但是如果需要改寫某個存儲單元(page)的數(shù)據(jù)，必須首先將整個block讀入緩存，然后修改數(shù)據(jù)，并擦除整個block的數(shù)據(jù)，最后將整個block寫入，很顯然，SSD改寫數(shù)據(jù)的代價很高，SSD的這個特性，我們稱之為erase-before-write。

參考鏈接

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容