作業系統設計/檔案系統/分配
分配背後的主要思想是有效地利用檔案空間並快速訪問檔案。有三種類型的分配
- 連續分配
- 連結分配
- 索引分配
除了在磁碟驅動器上儲存實際的檔案資料外，檔案系統還儲存有關檔案的元資料：每個檔案的檔名，上次編輯時間，它在磁碟上的確切位置以及磁碟的哪些部分是“空閒的”。空閒區域當前未被檔案資料或元資料使用，因此可用於儲存新檔案。（儲存這些元資料的區域通常稱為“inode”、“塊”、“檔案分配表”等。）
為了跟蹤空閒空間，檔案系統維護一個空閒空間列表，該列表跟蹤所有空閒的磁碟塊。要建立檔案，需要為檔案預留所需空間，並將相應空間從與每個空間連結的空閒列表中刪除。
連續分配方法要求每個檔案佔用磁碟上的一組連續地址。磁碟地址定義了磁碟上的線性排序。當檔案必須儲存在磁碟上時，系統會搜尋與檔案大小要求一致的連續塊集，即系統會等待直到找到所需數量的記憶體塊按順序排列。當有可用空間時，系統將檔案儲存在磁碟上並在目錄中進行條目。
連續分配檔案的目錄條目包含
- 起始塊地址
- 分配塊的長度
透過這種排序，在塊 b 後訪問塊 b+1 通常不需要任何磁頭移動。檔案的連續分配由磁碟地址和第一個塊的長度定義。如果檔案有 n 個塊長，並且從位置 b 開始，那麼它將佔用塊 b、b+1、b+2、…、b+n-1。每個檔案的目錄條目指示起始塊的地址和為該檔案分配的區域的長度。
在連結分配中，每個檔案都是磁碟塊的連結列表。目錄包含指向檔案第一個（以及可選的最後一個）塊的指標。例如，一個從塊 4 開始的 5 塊檔案，可能會在塊 7 處繼續，然後是塊 16、塊 10，最後是塊 27。每個塊包含指向下一個塊的指標，最後一個塊包含一個 NIL 指標。值 -1 可用於 NIL 以將其與塊 0 區分開。
透過連結分配，每個目錄條目都包含指向檔案第一個磁碟塊的指標。該指標初始化為 nil（列表結束指標值）以表示空檔案。對檔案寫入會刪除第一個空閒塊並寫入該塊。然後將這個新塊連結到檔案的末尾。要讀取檔案，只需從塊到塊地跟蹤指標即可。
連結分配沒有外部碎片。任何空閒塊都可以用來滿足請求。請注意，在建立檔案時也不需要宣告檔案的大小。只要有空閒塊，檔案就可以繼續增長。但是，連結分配確實有缺點。主要問題是它效率低下以支援直接訪問；它只對順序訪問檔案有效。要找到 檔案的塊，它必須從該檔案的開頭開始，並跟蹤指標，直到到達 塊。請注意，每次訪問指標都需要磁碟讀取。
連結分配不支援檔案的隨機訪問，因為每個塊只能從前一個找到。索引分配透過將所有指標集中到索引塊中來解決此問題。一個磁碟塊僅用於儲存檔案的 DBA（磁碟塊地址）。
每個檔案都與其自己的索引節點關聯。如果檔案很大，那麼一個磁碟塊可能不足以容納該檔案的所有相關 DBA。如果檔案很小，那麼一些磁碟塊空間會被浪費，因為 DBA 較少，一個磁碟塊仍然可以容納更多 DBA。
該方法解決了碎片問題，因為塊可以儲存在任何位置。