非連續(xù)空間存放方式

我們已經(jīng)對(duì)連續(xù)分配的方式有了一定的了解，并且也清楚了它存在的問題和局限性。為了解決這些問題，非連續(xù)存放的方式應(yīng)運(yùn)而生。非連續(xù)空間存儲(chǔ)大致可以分為兩種形式：鏈表形式和索引形式。

鏈?zhǔn)椒峙?/h2>

鏈?zhǔn)椒峙涫且环N離散分配的方式，用于為文件分配非連續(xù)的磁盤塊。它有兩種分配方式：顯示鏈接和隱式鏈接。

隱式鏈接

隱式鏈表分配與我們已知的Java鏈表知識(shí)基本是一致的，都需要存儲(chǔ)下一個(gè)節(jié)點(diǎn)的指針。但為什么稱之為隱式鏈接呢？因?yàn)槲覀儾恢烂總€(gè)節(jié)點(diǎn)的指針是什么，只有通過遍歷的方式從頭節(jié)點(diǎn)開始逐步獲取下一個(gè)節(jié)點(diǎn)的指針。每次操作都是相同的，指針并沒有存儲(chǔ)起來。在隱式鏈接分配中，目錄項(xiàng)只存儲(chǔ)了頭節(jié)點(diǎn)（磁盤塊）指針和尾節(jié)點(diǎn)（磁盤塊）指針。當(dāng)需要分配新的磁盤塊時(shí)，我們使用最后一個(gè)磁盤塊中的指針指向新的磁盤塊，并將新的磁盤塊標(biāo)記為最后一個(gè)磁盤塊。

現(xiàn)在讓我們考慮一個(gè)問題：使用隱式鏈接如何將邏輯塊號(hào)轉(zhuǎn)換為物理塊號(hào)？我們可以將其類比為Java中的鏈表如何找到相應(yīng)的元素。

當(dāng)用戶提供要訪問的邏輯塊號(hào) i 時(shí)，操作系統(tǒng)需要找到所需訪問文件的文件控制塊（FCB）。從FCB中我們可以得知文件的起始?jí)K號(hào)，然后將邏輯塊號(hào) 0 的數(shù)據(jù)讀入內(nèi)存，通過這個(gè)可以知道邏輯塊號(hào) 1 的物理塊號(hào)，然后再讀入邏輯塊號(hào) 1 的數(shù)據(jù)進(jìn)入內(nèi)存，如此類推，最終可以找到用戶所需訪問的邏輯塊號(hào) i。因此，訪問邏輯塊號(hào) i 需要進(jìn)行 i + 1 次磁盤 I/O 操作。隱式鏈接分配就像Java中的鏈表一樣只能按順序訪問，不支持隨機(jī)訪問，因此查找效率較低。

現(xiàn)在讓我們考慮另一個(gè)問題：使用隱式鏈接是否方便文件擴(kuò)展？我們可以將其類比為Java中的鏈表是否方便進(jìn)行擴(kuò)容呢？

我們知道，目錄項(xiàng)中存儲(chǔ)了結(jié)束塊號(hào)的物理地址。因此，如果要擴(kuò)展文件，我們只需要將新分配的磁盤塊掛載到結(jié)束塊號(hào)的后面。我們修改結(jié)束塊號(hào)的指針指向新分配的磁盤塊，并更新目錄項(xiàng)。隱式鏈接分配類似于Java中的鏈表，很方便進(jìn)行文件擴(kuò)展。所有的空閑磁盤塊都可以被利用，沒有碎片問題，存儲(chǔ)利用率較高。

顯式鏈接

有隱式連接那么就有顯式鏈接，隱式鏈接我們說了沒有存儲(chǔ)各個(gè)節(jié)點(diǎn)指針?biāo)悦看味夹枰匦聫念^結(jié)點(diǎn)來獲取下一指針節(jié)點(diǎn)，那么顯示鏈接是把用于鏈接各個(gè)物理塊的指針顯式地存放在一張表中，該表稱為文件分配表（FAT，F(xiàn)ile Allocation Table）。

由于查找記錄的過程是在內(nèi)存中進(jìn)行的，從而顯著提高了檢索速度并減少了訪問磁盤的次數(shù)。但也正是整個(gè)表都存放在內(nèi)存中的關(guān)系，它的主要的缺點(diǎn)是不適用于大磁盤。

舉個(gè)例子，假設(shè)有一個(gè)擁有200GB空間和1KB塊大小的磁盤。根據(jù)顯式鏈接的方式，需要在文件分配表中存儲(chǔ)2億項(xiàng)，每一項(xiàng)對(duì)應(yīng)磁盤上的一個(gè)塊。如果每一項(xiàng)需要4個(gè)字節(jié)的存儲(chǔ)空間，那么文件分配表將占用800MB的內(nèi)存。顯然，對(duì)于大磁盤而言，這種方式并不適合。

索引分配

理解索引分配之前，可以先想一下MySQL中的索引結(jié)構(gòu)，這樣可以更好的理解索引分配的原理。

鏈表的方式解決了連續(xù)分配的磁盤碎片和文件動(dòng)態(tài)擴(kuò)展的問題，但是不能有效支持直接訪問（FAT除外）。為了解決這個(gè)問題，可以采用索引的方式。

索引的實(shí)現(xiàn)是為每個(gè)文件創(chuàng)建一個(gè)「索引數(shù)據(jù)塊」，里面存放的是指向文件數(shù)據(jù)塊的指針列表，類似于書的目錄。通過查閱索引數(shù)據(jù)塊，可以快速找到對(duì)應(yīng)的數(shù)據(jù)塊。

此外，文件頭還需要包含指向「索引數(shù)據(jù)塊」的指針。這樣可以通過文件頭知道索引數(shù)據(jù)塊的位置，然后通過索引數(shù)據(jù)塊里的索引信息找到對(duì)應(yīng)的數(shù)據(jù)塊。

當(dāng)創(chuàng)建文件時(shí)，索引塊的所有指針都被設(shè)置為空。當(dāng)首次寫入第 i 塊時(shí)，從空閑空間中獲取一個(gè)塊，并將其地址寫入索引塊的第 i 個(gè)條目。這樣，通過文件頭中的指向索引數(shù)據(jù)塊的指針，可以知道索引數(shù)據(jù)塊的位置，并通過索引數(shù)據(jù)塊中的索引信息找到對(duì)應(yīng)的數(shù)據(jù)塊。

索引分配的優(yōu)點(diǎn)包括：

• 創(chuàng)建、增大和縮小文件都很方便；
• 沒有碎片問題；
• 支持順序讀寫和隨機(jī)讀寫。

然而，索引分配也有一些缺點(diǎn)。由于索引數(shù)據(jù)也需要存放在磁盤塊中，如果文件很小，實(shí)際上只需要一個(gè)塊就可以存放，但仍需要額外分配一個(gè)塊來存放索引數(shù)據(jù)，這會(huì)帶來額外的開銷。

如果文件很大，以至于一個(gè)索引數(shù)據(jù)塊無法容納全部的索引信息，我們可以采用組合的方式來處理大文件的存儲(chǔ)。

組合方式是鏈表 + 索引，也被稱為「鏈?zhǔn)剿饕龎K」。在這種實(shí)現(xiàn)方式中，索引數(shù)據(jù)塊中會(huì)預(yù)留一個(gè)指針，用于存放下一個(gè)索引數(shù)據(jù)塊的地址。當(dāng)一個(gè)索引數(shù)據(jù)塊的索引信息用完時(shí)，可以通過該指針找到下一個(gè)索引數(shù)據(jù)塊的信息。然而，這種方式也會(huì)面臨鏈表方式的問題，即如果某個(gè)指針損壞了，后續(xù)的數(shù)據(jù)將無法讀取。

為了解決這個(gè)問題，可以采用多級(jí)索引的方式。多級(jí)索引將一個(gè)大文件的索引信息分散到多個(gè)索引數(shù)據(jù)塊中，以減輕單個(gè)索引數(shù)據(jù)塊的負(fù)擔(dān)。類似于MySQL的B+樹索引結(jié)構(gòu)，多級(jí)索引也在非葉子節(jié)點(diǎn)存儲(chǔ)了索引數(shù)據(jù)，而索引指針指向葉子節(jié)點(diǎn)的數(shù)據(jù)。盡管存在一些不同，但它們的邏輯是相似的。

總結(jié)

非連續(xù)空間存放方式是為了解決連續(xù)分配方式的問題和局限性而提出的。其中，鏈?zhǔn)椒峙浞绞桨[式鏈接和顯式鏈接兩種形式。隱式鏈接通過存儲(chǔ)頭節(jié)點(diǎn)和尾節(jié)點(diǎn)指針的方式實(shí)現(xiàn)文件的非連續(xù)分配，但查找效率較低且不支持隨機(jī)訪問，但方便文件擴(kuò)展且沒有碎片問題。顯式鏈接通過文件分配表存儲(chǔ)物理塊的指針，提高了檢索速度但不適用于大磁盤。

索引分配方式則通過為每個(gè)文件創(chuàng)建索引數(shù)據(jù)塊，并在文件頭和索引數(shù)據(jù)塊中存儲(chǔ)指針信息，實(shí)現(xiàn)了文件的非連續(xù)分配和直接訪問。索引分配的優(yōu)點(diǎn)包括方便創(chuàng)建、擴(kuò)展和縮小文件，沒有碎片問題，支持順序和隨機(jī)讀寫。然而，索引分配也存在一些缺點(diǎn)，如對(duì)小文件的額外開銷。

為了解決大文件存儲(chǔ)問題，可以采用鏈?zhǔn)剿饕龎K和多級(jí)索引的組合方式。鏈?zhǔn)剿饕龎K通過指針連接多個(gè)索引數(shù)據(jù)塊，但可能面臨指針損壞導(dǎo)致數(shù)據(jù)無法讀取的問題。多級(jí)索引將大文件的索引信息分散到多個(gè)索引數(shù)據(jù)塊中，提高了文件系統(tǒng)的性能和可靠性。通過這些優(yōu)化，可以更好地處理大文件存儲(chǔ)，并提高文件系統(tǒng)的效率。文章來源地址http://www.zghlxwxcb.cn/news/detail-695059.html

到了這里，關(guān)于操作系統(tǒng)中文件系統(tǒng)的實(shí)現(xiàn)和分配方式探析（下）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！