磁盤空間的分配方法(電腦磁盤如何分配單元)磁盤直接訪問的特點在文件實現時提供了靈活性。在幾乎每種情況下，很多文件都是存儲在同一個磁盤上的。主要的問題是，如何為這些文件分配空間，以便有效使用磁盤空間和快速訪問文件。磁盤空間分配的主要常用方法有三個：連續分配、鏈接分配和索引分配。每個方法各有優缺點。雖然有些系統對這三種方法都支持。但是更為常見的是，一個系統只對同一文件系統類型的所有文件采用一種方法。連續分配連續分配方法要求，每個文件在磁盤上占有一組連續的塊。磁盤地址為磁盤定義了一個線性排序。有了這個排序，假設只有一個作業正在訪問磁盤，在塊b之后訪問塊b+1通常不需要移動磁頭。當需要磁頭移動（從一個柱面的最后扇區到下一個柱面的第一扇區）時，只需要移動一個磁道。因此，用于訪問連續分配文件的所需尋道數量最小，在確實需要尋道時所需的尋道時間也最小。文件的連續分配可以用首塊的磁盤地址和連續的塊數來定義。如果文件有n塊長并從位置b開始，則該文件將占有塊b，b+1，b+2，…，b+n-1。每個文件的目錄條目包括起始塊的地址和該文件所分配區域的長度，參見下圖磁盤空間的連續分配連續分配文件的訪問非常容易。對于順序訪問，文件系統會記住上次引用的塊的磁盤地址，如需要可讀入下一塊。對于直接訪問一個文件的從塊b開始的第i塊，可以直接訪問塊b+i。因此，連續分配支持順序訪問和直接訪問。不過，連續分配也有一些問題。一個難題是，為新文件找到空間。用于管理空閑空間的系統決定了這個任務如何完成，雖然可以使用任何管理系統，但是有的系統會比其他的要慢。連續分配問題可以作為通用動態存儲分配問題的一個具體應用，即如何從一個空閑塊列表中尋找一個滿足大小為n的空間。從一組空閑塊中尋找一個空閑塊的最為常用的策略是，首次適合和最優適合。模擬結果顯示在時間和空間使用方面，首次適合和最優適合都要比最壞適合更為高效。首次適合和最優適合在空間使用方面不相上下，但是首次適合一般更快。所有這些算法都有外部碎片的問題。隨著文件的分配和刪除，可用磁盤空間被分成許多小片。只要空閑空間分成小片，就會存在外部碎片。當最大連續片不能滿足需求時就有問題；存儲空間分成了許多小片，其中沒有一個足夠大以存儲數據。因磁盤存儲總量和文件平均大小的不同，外部碎片可能是個小問題，但也可能是個大問題。為了防止外部碎片引起的大量磁盤空間的浪費，將整個文件系統復制到另一個磁盤。原來的磁盤完全變成空的，從而創建了一個大的連續空閑空間。然后，通過從這個大的連續空閑空間采用連續分配方法，將這些文件復制回來。這種方案將所有空閑空間有效合并起來，解決了碎片問題。這種合并的代價是時間，而且大硬盤的代價可能特別高。合并這些磁盤空間可能需要數小時，可能每周都需進行。有些系統要求，這個功能線下執行且文件系統要卸載。在這停機期間不能進行正常操作，因此生產系統應盡可能地避免合并。大多數的需要整理碎片的現代系統能夠和正常的系統操作一起在線執行合并，但是性能下降可能很明顯。連續分配的另一個問題是，確定一個文件需要多少空間。當創建一個文件時，需要找到并分配它所需空間的總數。創建者（程序或人員）又如何知道所創建文件的大??？在某些情況下，這種判斷可能相當簡單（例如，復制一個現有文件），一般來說，輸出文件的大小可能難以估計。如果為文件分配的空間太小，則可能會發現文件無法擴展。特別是對于最優適合的分配策略，文件兩側的空間可能已經使用。因此，不能在原地讓文件更大。這時，有兩種可能辦法：終止用戶程序，并給出適當的錯誤消息。這樣，用戶必須分配更多的空間，并再次運行該程序。這些重復的運行可能代價很高。為了防止這些問題，用戶通常會高估所需的磁盤空間，從而造成相當大的空間浪費。找一個更大的空間，將文件內容復制到新空間，并釋放以前的空間。只要空間存在，就可以重復這些動作，不過如此可能耗時。然而，用戶無需獲知究竟發生了什么事情；而系統雖有問題仍繼續運行，只不過會越來越慢。即使文件所需的空間總量事先已知，預先分配仍可能很低效。一個文件在很長時間內增長緩慢（數月或數年），仍必須按它的最終大小來分配足夠空間，即使這個空間很長時間內不用。因此，該文件有一個很大的內部碎片。為了最小化這些缺點，有些操作系統使用連續分配的修正方案。這里，最初分配一塊連續空間。以后，當這個數量不夠時，會添加另一塊連續空間（稱為擴展）。然后，文件塊的位置就記錄為：地址、塊數、下一擴展的首塊的指針。在有些系統上，文件所有者可以設置擴展大小，但是如果所有者不正確，這種設置會導致低效。如果擴展太大，內部碎片可能仍然是個問題；隨著不同大小的擴展的分配和刪除，外部碎片可能也是個問題。鏈接分配鏈接分配解決了連續分配的所有問題。采用鏈接分配，每個文件是磁盤塊的鏈表；磁盤塊可能會散布在磁盤的任何地方。目錄包括文件第一塊和最后一塊的指針。例如，一個有5塊的文件可能從塊9開始，然而是塊16、塊1、塊10，最后是塊25（如下圖）。每塊都有下一塊的一個指針。用戶不能使用這些指針。因此，如果每塊有512字節，并且磁盤地址（指針）需要4字節，則用戶可以使用508字節。磁盤空間的鏈接分配要創建一個新文件，只需在目錄中增加一個新的條目。采用鏈接分配，每個目錄條目都有文件首個磁盤塊的一個指針。這個指針初始化為null，表示一個空的文件。大小字段也設置為0。寫文件導致空閑空間管理系統找到一個空閑塊，這個新塊會被寫入，并鏈接到文件的尾部。讀文件，只需按照塊到塊的指針來讀塊。采用鏈接分配沒有外部碎片，空閑空間列表的任何塊可以用于滿足請求。當創建文件時，并不需要說明文件的大小只，要有可用的空閑塊，文件就可以繼續增長。因此，無需合并磁盤空間。然而，鏈接分配確實有缺點。主要問題是，它只能有效用于順序訪問文件。要找到文件的第i個塊，必須從文件的開始起，跟著指針，找到第i塊。每個指針的訪問都需要一個磁盤讀，有時需要磁盤尋道。因此，鏈接分配不能有效支持文件的直接訪問。另一個缺點是指針所需的空間。如果指針需要使用512字節塊的4字節，則0.78%的磁盤空間會用于指針，而不是其他信息。每個文件需要比原來稍多的空間。這個問題的通常解決方案是，將多個塊組成簇，并按簇而不是按塊來分配。例如，文件系統可以定義一個簇為4塊，在磁盤上僅以簇為單位來操作。這樣，指針所占的磁盤空間的百分比就要小得多。這種方法使得邏輯到物理塊的映射仍然簡單，但提高了磁盤吞吐量（因為需要更少的磁頭移動），并且降低了塊分配和空閑列表管理所需的空間。這種方法的代價增加了內部碎片；如果一個簇而不是塊沒有完全使用，則會浪費更多空間。簇可以改善許多算法的磁盤訪問時間，因此用于大多數操作系統。鏈接分配的另一個問題是可靠性。回想一下，文件是通過散布在磁盤上的指針鏈接起來的，操作系統軟件錯誤或磁盤硬件故障可能導致獲得一個錯誤指針，這個錯誤可能會導致鏈接到空閑空間列表或鏈接到另一個文件。一個不完全的解決方案是，采用雙向鏈表；另一個是，每塊存儲文件名稱和相對塊號。然而，這些方案為每個文件增加了更多額外開銷。鏈接分配的一個重要變種是文件分配表(FAT)的使用。這個簡單而有效的磁盤空間分配方法用于MS-DOS操作系統。每個卷的開頭部分的磁盤用于存儲該表。在該表中，每個磁盤塊都有一個條目，并可按塊號來索引。FAT的使用與鏈表相同。目錄條目包含文件首塊的塊號。通過這個塊號索引的表條目包含文件的下一塊的塊號。這條鏈會繼續下去，直到最后一塊；而最后一塊的表條目的值為文件結束值。未使用的塊用0作為表條目的值來表示。為文件分配一個新塊只要簡單找到第一個值為0的FAT條目，用新塊的地址替換前面文件結束值，用文件結束值替代0。由塊217、618、339組成的文件的FAT結構文件分配表如果不對FAT采用緩存，FAT分配方案可能導致大量的磁頭尋道時間。磁頭必須移到卷的開頭，讀入FAT，找到所需塊的位置，再移到塊本身的位置。在最壞的情況下，每塊都需要移動兩次。優點是改善了隨機訪問時間；因為通過讀入FAT信息，磁頭能找到任何塊的位置。索引分配鏈接分配解決了連續分配的外部碎片和大小聲明的問題。然而，在沒有FAT時，鏈接分配不能支持髙效的直接訪問，因為塊指針與塊一起分散在整個磁盤上，并且必須按序讀取。索引分配通過將所有指針放在一起，即索引塊，解決了這個問題。每個文件都有自己的索引塊，這是一個磁盤塊地址的數組。索引塊的第i個條目指向文件的第i個塊。目錄包含索引塊的地址(下圖)。當查找和讀取第i個塊時，采用第i個索引塊條目的指針。磁盤空間的索引分配當創建文件時，索引塊的所有指針都設為null。當首次寫入第i塊時，先從空閑空間管理器中獲得一塊，再將其地址寫到索引塊的第i個條目。索引分配支持直接訪問，并且沒有外部碎片問題，因為磁盤的任何空閑塊可以滿足更多空間的請求。然而，索引分配確實浪費空間。索引塊指針的開銷通常大于鏈接分配的指針開銷?？紤]一下常見情況，即一個文件只有一塊或兩塊。采用鏈接分配，每塊只浪費一個指針的空間。采用索引分配，即使只有一個或兩個指針是非空的，也必須分配一個完整的索引塊。這一點提出了一個問題：索引塊應為多大？每個文件必須有一個索引塊，因此需要索引塊盡可能小。然而，如果索引塊太小，它不能為大的文件存儲足夠多的指針。因此，必須采取一種機制，以處理這個問題。此目的的機制包括：鏈接方案：一個索引塊通常為一個磁盤塊。因此，它本身能直接讀寫。為了支持大的文件，可以將多個索引塊鏈接起來。例如，一個索引塊可以包括一個含有文件名的頭部和一組頭100個磁盤塊的地址。下一個地址（索引塊的最后一個字）為null（對于小文件），或者另一個索引塊的指針(對于大文件)。多級索引：鏈接表示的一種變種是，通過第一級索引塊指向一組第二級的索引塊，它又指向文件塊。當訪問一塊時，操作系統通過第一級索引查找第二級索引塊，再采用這個塊查找所需的數據塊。這種做法可以持續到第三級或第四級，具體取決于最大文件大小。對于4096字節的塊，可以在索引塊中存入1024個4字節的指針。兩級索引支持1048576個數據塊和4GB的最大文件。組合方案：用于基于UNIX的文件系統，將索引塊的前幾個（如15）指針存在文件的inode中。這些指針的前12個指向直接塊；即它們包含存儲文件數據的塊的地址。因此，小的文件(不超過12塊)不需要單獨的索引塊。如果塊大小為4KB，則不超過48KB的數據可以直接訪問。接下來的3個指針指向間接塊。第一個指向一級間接塊。一級間接塊為索引塊，它包含的不是數據，而是真正包含數據的塊的地址。第二個指向二級間接塊，它包含了一個塊的地址，而這個塊內的地址指向了一些塊，這些塊中又包含了指向真實數據塊的指針。最后一個指針為三級間接塊指針。下圖顯示了一個UNIX的inode。UNIX的inode采用這種方法，一個文件的塊數可以超過許多操作系統所用的4字節的文件指針所能訪問的空間。32位指針只能訪問232字節，或4GB。許多UNIX和Linux現在支持64位的文件指針。這樣的指針允許文件和文件系統為數艾字節。ZFS文件系統支持128位的文件指針。索引分配方案與鏈接分配一樣在性能方面有所欠缺。尤其是，雖然索引塊可以緩存在內存中，但是數據塊可能分布在整個卷上。性能以上討論的分配方法，在存儲效率和數據塊訪問時間上有所不同。當操作系統選擇合適方法來實現時，這兩者都是重要依據。在選擇分配方法之前，需要確定系統是如何使用的。以順序訪問為主的系統和以隨機訪問為主的系統，不應采用相同的方法。對于任何類型的訪問，連續分配只需訪問一次就能獲得磁盤塊。由于可以在內存中容易地保存文件的開始地址，所以可以立即計算第i塊(或下一塊)的磁盤地址，并直接讀取。對于鏈接分配，也可以在內存中保留下一塊的地址，并直接讀取。對于順序訪問，這種方法很好；然而，對于直接訪問，對第i塊的訪問可能需要讀i次磁盤。這個問題表明了，為什么鏈接分配不適用于需要直接訪問的應用程序。因此，有的系統通過使用連續分配支持直接訪問的文件，通過鏈接分配支持順序訪問的文件。對于這些系統，在創建文件時必須聲明使用的訪問類型。用于順序訪問的文件可以鏈接分配，但不能用于直接訪問。用于直接訪問的文件可以連續分配，能支持直接訪問和順序訪問，但是在創建時必須聲明其最大的文件大小。在這種情況下，操作系統必須具有適當的數據結構和算法，來支持兩種分配方法。文件可以從一種類型轉成另一種類型，創建一個所需類型的新文件，將原來文件的內容復制過來，然后可以刪除舊文件，再重新命名新文件。索引分配更為復雜。如果索引塊已在內存，則可以進行直接訪問。然而，在內存中保存索引塊需要相當大的空間。如果沒有這個內存空間，則可能必須先讀取索引塊，再讀取所需的數據塊。對于兩級索引，可能需要讀取兩次索引塊。對于一個極大的文件，訪問文件末尾附近的塊需要首先讀取所有的索引塊，最后才能讀入所需的數據塊。因此，索引分配的性能取決于索引結構、文件大小以及所需塊的位置。有些系統將連續分配和索引分配組合起來：對于小文件(只有3或4塊的)采用連續分配；當文件增大時，自動切換到索引分配。由于大多數文件較小，小文件的連續分配的效率又高，所以平均性能還是相當不錯的。還可以采用許多其他優化方法。鑒于cpu速度和磁盤速度的差距，操作系統采用數千條指令以節省一些磁頭移動，不是不合理的。此外，隨著時間的推移，這種差距會增加，以致于操作系統采用數十萬條指令來優化磁頭移動也是值得的。