文章目錄

• • • 1 文件的物理結構 （文件分配方式）
    • • 1.1 文件塊、磁盤塊
      • 1.2 文件分配方式——連續分配
      • 1.3 文件分配方式——鏈接分配
      • • • 1.3.1 鏈接分配——隱式鏈接
          • 1.3.2 鏈接分配——顯式鏈接
          • 1.3.3 鏈接分配（總結）
      • 1.4 文件分配方式——索引分配
      • • • 1.4.1 鏈接方案
          • 1.4.2 多層索引
          • 1.4.3 混合索引
          • 1.4.4 索引分配（總結）
      • 1.5 文件分配總結
    • 2 文件存儲空間管理
    • • 2.1 存儲空間的劃分與初始化
      • 2.2 存儲空間管理——空閑表法
      • 2.3 存儲空間管理——空閑鏈表法
      • 2.4 存儲空間管理一一位示圖法
      • 2.5 存儲空間管理一—成組鏈接法
      • 2.6 文件存儲空間管理小結

1 文件的物理結構 （文件分配方式）

1.1 文件塊、磁盤塊

類似于內存分頁，磁盤中的存儲單元也會被分為一個個“塊/磁盤塊/物理塊”。很多操作系統中，磁盤塊的大小與內存塊、頁面的大小相同

在內存管理中，進程的邏輯地址空間被分為一個一個頁面同樣的，在外存管理中，為了方便對文件數據的管理，文件的邏輯地址空間也被分為了一個一個的文件“塊”。 于是文件的邏輯地址也可以表示為（邏輯塊號，塊內地址）的形式。

1.2 文件分配方式——連續分配

連續分配方式要求每個文件在磁盤上占有一組連續的塊。

問題：用戶通過邏輯地址來操作自己的文件，操作系統如何實現從邏輯地址到物理地址的映射？
（邏輯塊號，塊內地址）→（物理塊號，塊內地址）。只需轉換塊號就行，塊內地址保持不變

用戶給出要訪問的邏輯塊號，操作系統找到該文件對應的目錄項（FCB）…

當然，還需要檢查用戶提供的邏輯塊號是否合法（邏輯塊號≥ 長度就不合法）
可以直接算出邏輯塊號對應的物理塊號，物理塊號=起始塊號+邏輯塊號
因此連續分配支持順序訪問和直接訪問（即隨機訪問）

連續分配讀取某個磁盤塊時，需要移動磁頭。訪問的兩個磁盤塊相隔越遠，移動磁頭所需時間就越長。

結論：

連續分配的文件在順序讀/寫時速度最快

物理上采用連續分配的文件不方便拓展。

物理上采用連續分配， 存儲空間利用率低，會產生難以利用的磁盤碎片
可以用緊湊來處理碎片，但是需要耗費很大的時間代價。

連續分配優缺點總結：

優點：支持順序訪問和直接訪問（即隨機訪問）；連續分配的文件在順序訪問時速度最快
缺點：不方便文件拓展；存儲空間利用率低，會產生磁盤碎片

1.3 文件分配方式——鏈接分配

鏈接分配采取離散分配的方式，可以為文件分配離散的磁盤塊。分為隱式鏈接和顯式鏈接兩種。

1.3.1 鏈接分配——隱式鏈接

問題1：隱式鏈接如何實現文件的邏輯塊號到物理塊號的轉變？

用戶給出要訪問的邏輯塊號i，操作系統找到該文件對應的目錄項（FCB）…

從目錄項中找到起始塊號（即0號塊），將0 號邏輯塊讀入內存，由此知道1號邏輯塊存 放的物理塊號，于是讀入1號邏輯塊，再找 到2號邏輯塊的存放位置……以此類推。

因此，讀入i號邏輯塊，總共需要i+1次磁盤 I/O。

結論：采用鏈式分配（隱式鏈接）方式的文件，只支持順序訪問，不支持隨機訪問，查找效率低。另外，指向下一個盤塊的指針也需要耗費少量的存儲空間。

問題2：是否方便拓展文件？

若此時要拓展文件，則可以隨便找一個空閑磁盤塊，掛到文件的磁盤塊鏈尾，并修改文件的FCB

結論：采用隱式鏈接的鏈接分配方式，很方便文件拓展。 另外，所有的空閑磁盤塊都可以被利用，不會有碎片問題， 外存利用率高。

隱式鏈接分配優缺點總結：
隱式鏈接——除文件的最后一個盤塊之外，每個盤塊中都存有指向下一個盤塊的指針。文件目錄 包括文件第一塊的指針和最后一塊的指針。

優點：很方便文件拓展，不會有碎片問題，外存利用率高。
缺點：只支持順序訪問，不支持隨機訪問，查找效率低，指向下一個盤塊的指針也需要耗費少量的存儲空間。

1.3.2 鏈接分配——顯式鏈接

顯式鏈接把用于鏈接文件各物理塊的指針顯式地存放在一張表中。即文件分配表（FAT，File Allocation Table）

假設某個新創建的文件“aaa”依 次存放在磁盤塊2→5→0→1
假設某個新創建的文件“bbb”依 次存放在磁盤塊4→23→3
則FAT表如下：

注意：一個磁盤僅設置一張FAT。 開機時，將FAT讀入內存，并常駐內存。FAT 的各個表項在物理上連續存儲，且每一個表項長度相同，因此“物理塊號”字段可以是隱含的。

問題1：如何實現文件的邏輯塊號到物理塊號的轉變？

用戶給出要訪問的邏輯塊號i，操作系統找到該文件對應的目錄項 （FCB）…

從目錄項中找到起始塊號，若i>0，則查詢內存中的文件分配表FAT， 往后找到i號邏輯塊對應的物理塊號。邏輯塊號轉換成物理塊號的過程不需要讀磁盤操作。

結論：采用鏈式分配（顯式鏈接）方式的文件，支持順序訪問，也支持隨機訪問（想訪問i號邏輯塊時，并不需要依次訪問之前的0~i-1號邏輯塊），由于塊號轉換的過程不需要訪問磁盤，因此相比于隱式鏈接來說，訪問速度快很多。
顯然，顯式鏈接也不會產生外部碎片，也可以很方便地對文件進行拓展。

1.3.3 鏈接分配（總結）

隱式鏈接——除文件的最后一個盤塊之外，每個盤塊中都存有指向下一個盤塊的指針。文件目錄包括文件第一塊的指針和最后一塊的指針。
優點：很方便文件拓展，不會有碎片問題，外存利用率高。
缺點：只支持順序訪問，不支持隨機訪問，查找效率低，指向下一個盤塊的指針也需要耗費少量的存儲空間。

顯式鏈接——把用于鏈接文件各物理塊的指針顯式地存放在一張表中，即 文件分配表（FAT，File AllocationTable）。一個磁盤只會建立一張文件分配表。開機時文件分配表放入內存，并常駐內存。
優點：很方便文件拓展，不會有碎片問題，外存利用率高，并且支持隨機訪問。相比于隱式鏈接來說，地址轉換時不需要訪問磁盤，因此文件的訪問效率更高。
缺點：文件分配表的需要占用一定的存儲空間。

考試題目中遇到未指明隱式/顯式的“鏈接 分配”，默認指的是隱式鏈接的鏈接分配

1.4 文件分配方式——索引分配

索引分配允許文件離散地分配在各個磁盤塊中，系統會為每個文件建立一張索引表，索引表中記錄了文件的各個邏輯塊對應的物理塊（索引表的功能類似于內存管理中的頁表——建立邏輯頁面到物理頁之間的映射關系）。索引表存放的磁盤塊稱為索引塊。文件數據存放的磁盤塊稱為數據塊。

假設某個新創建的文件“aaa”的數 據依次存放在磁盤塊2→5→13→9。 7號磁盤塊作為“aaa”的索引塊， 索引塊中保存了索引表的內容。

注：在顯式鏈接的鏈式分配方式中，文件分配表FAT 是一個磁盤對應一張。而索引分配方式中，索引表是一個文件對應一張。

可以用固定的長度表示物理塊號（如： 假設磁盤總容量為1TB=2⁴⁰B，磁盤塊大小為1KB，則共有2³⁰個磁盤塊，則可用4B表示磁盤塊號），因此，索引表中的“邏輯塊號”可以是隱含的。

問題：索引分配如何實現文件的邏輯塊號到物理塊號的轉換？

用戶給出要訪問的邏輯塊號i，操作系統找到該文件對應的目錄項（FCB）…

從目錄項中可知索引表存放位置，將索引表從外存讀入內存，并查找索引表即可只i號邏輯塊在外存中的存放位置。

可見，索引分配方式可以支持隨機訪問。 文件拓展也很容易實現（只需要給文件分配 一個空閑塊，并增加一個索引表項即可） 但是索引表需要占用一定的存儲空間

若每個磁盤塊1KB，一個索引表項4B，則一個磁盤塊只能存放1024/4=256個索引項

如果一個文件的大小超過了256 塊，也就意味著這個文件對應的索引表超過了256個索引項，那么一個磁盤塊是裝不下文件的整張索引表的，如何解決這個問題？
解決方案：①鏈接方案 ②多層索引 ③混合索引

1.4.1 鏈接方案

鏈接方案：如果索引表太大，一個索引塊裝不下，那么可以將多個索引塊鏈接起來存放

假設磁盤塊大小為1KB，一個索引表項占4B，則一個磁盤塊只能存放1024/4=256個索引項。
若一個文件大小為256X256KB= 65,536KB=64MB 該文件共有256X256個塊，也就對應 256X256個索引項，也就需要256個索引塊來存儲，這些索引塊用鏈接方案連起來。 若想要訪問文件的最后一個邏輯塊， 就必須找到最后一個索引塊（第256 個索引塊），而各個索引塊之間是用指針鏈接起來的，因此必須先順序地讀入前255個索引塊。
這顯然是很低效的。如何解決呢？

1.4.2 多層索引

多層索引：建立多層索引（原理類似于多級頁表）。使第一層索引塊指向第二層的索引塊。還可根據 文件大小的要求再建立第三層、第四層索引塊。

假設磁盤塊大小為1KB，一個索引表項占4B，則一個磁盤塊只能存放256個索引項。
若某文件采用兩層索引，則該文件的最大長度可以到256X256X1KB=65,536KB=64MB
最大長度：第一級索引表最多有256個索引項，也就是會指向256個第二季索引表，而第二級索引表最多也是256個索引項，每個索引項分別指向一個數據塊，數據塊大小1KB，則采用兩層索引，文件最大256X256X1KB=65,536KB=64MB

可根據邏輯塊號算出應該查找索引表中的哪個表項。 如：要訪問1026號邏輯塊，則 1026/256=4，1026%256=2
1026/256=4說明1026號邏輯塊對應的索引項是4號二級索引表中存放的
1026%256=2 則需要查詢4號索引表中的2號表項

因此可以先將一級索引表調入內存，查詢4號表項， 將其對應的二級索引表調入內存，再查詢二級索引表的2號表項即可知道1026號邏輯塊存放的磁盤塊號了。 訪問目標數據塊，需要3次磁盤I/O。第一次讀入一級索引表，第二次讀入二級索引表，第三次讀入最終要訪問的數據塊。

若采用三層索引，則文件的最大長度為256X256X256X1KB=16GB
類似的，訪問目標數據塊，需要4次磁盤I/O

重要結論：若采用多層索引，則各層索引表大小不能超過一個磁盤塊

采用K層索引結構，且頂級索引表未調入內存，則訪問一個數據塊只需要K+1次讀磁盤操作

1.4.3 混合索引

混合索引：多種索引分配方式的結合。例如，一個文件的頂級索引表中，既包含直接地址索引（直接 指向數據塊），又包含一級間接索引（指向單層索引表）、還包含兩級間接索引（指向兩層索引表） 。

由上可見：
若頂級索引表還沒讀入內存
訪問0~7號邏輯塊：兩次讀磁盤
訪問8~263：三次讀磁盤盤次數。
訪問264~65799：因次讀磁盤
對于小文件，只需較少的讀磁盤次數就可以訪問目標數據塊（一般計算機中小文件更多）
這種結構索引支持的最大文件長度為8+256+65536=65800KB→常考混合索引的最大文件長度

1.4.4 索引分配（總結）

索引分配允許文件離散地分配在各個磁盤塊中，系統會為每個文件建立一張索引表，索引表中記錄了文件的各個邏輯塊對應的物理塊（索引表的功能類似于內存管理中的頁表——建立邏輯頁面到物理頁之間的映射關系） 。

索引表存放的磁盤塊稱為索引塊。文件數據存放的磁盤塊稱為數據塊。 若文件太大，索引表項太多，可以采取以下三種方法解決：

鏈接方案：如果索引表太大，一個索引塊裝不下，那么可以將多個索引塊鏈接起來存放。
缺點：若文件很大，索引表很長，就需要將很多個索引塊鏈接起來。想要找到i號索引塊，必須先依次讀入0~i-1 號索引塊，這就導致磁盤I/O次數過多，查找效率低下。

多層索引：建立多層索引（原理類似于多級頁表）。使第一層索引塊指向第二層的索引塊。還可根據文件大小的要求再建立第三層、第四層索引塊。采用K層索引結構，且頂級索引表未調入內存，則訪問 一個數據塊只需要K+1次讀磁盤操作。
缺點：即使是小文件，訪問一個數據塊依然需要K+1次讀磁盤。

混合索引：多種索引分配方式的結合。例如，一個文件的頂級索引表中，既包含直接地址索引（直接指向數據塊），又包含一級間接索引（指向單層索引表）、還包含兩級間接索引（指向兩層索引表） 。
優點：對于小文件來說，訪問一個數據塊所需的讀磁盤次數更少。

超級超級超級重要考點：

要會根據多層索引、混合索引的結構計算出文件的最大長度（Key：各級索引表最大不能超過一個塊）；

要能自己分析訪問某個數據塊所需要的讀磁盤次數（Key：FCB中會存有指向頂級索引塊的指針，因此可以根據FCB讀入頂級索引塊。每次讀入下一級的索引塊都需要一次讀磁 盤操作。另外，要注意題目條件——頂級索引塊是否已調入內存）

1.5 文件分配總結

2 文件存儲空間管理

2.1 存儲空間的劃分與初始化

安裝Windows操作系統的時候，一個必經步驟是為磁盤分區（C盤、D盤、E盤等）

存儲空間的劃分：將物理磁盤劃分為一個個文件卷（邏輯卷、邏輯盤）

2.2 存儲空間管理——空閑表法

適用于“連續分配方式”

某時刻磁盤使用如下：

對應的空閑表：

第一個空閑盤塊號空閑盤塊數

0	2
5	1
10	5
18	3
23	1

空閑分區表

如何分配磁盤塊：

與內存管理中的動態分區分配很類似，為一個文件分配連續的存儲空間。同樣可采用首次適應、最佳適應、最壞適應等算法來決定要為文件分配哪個區間。

如何回收磁盤塊：

與內存管理中的動態分區分配很類似，當回收某個存儲區時需要有四種情況:
（1）回收區的前后都沒有相鄰空閑區；
（2）回收區的前后都是空閑區；
（3）回收區前面是空閑區；
（4）回收區后面是空閑區。
總之，回收時需要注意表項的合并問題。

2.3 存儲空間管理——空閑鏈表法

空閑盤塊鏈：

操作系統保存著鏈頭、鏈尾指針。
如何分配：若某文件申請K個盤塊，則從鏈頭開始依次摘下K個盤塊分配，并修改空閑鏈的鏈頭指針。
如何回收：回收的盤塊依次掛到鏈尾，并修改空閑鏈的鏈尾指針。

特點：適用于離散分配的物理結構。為文件分配多個盤塊時可能要重復多次操作

空閑盤區鏈：

操作系統保存著鏈頭、鏈尾指針。
如何分配：若某文件申請K個盤塊，則可以采用首次適應、最佳適應等算法，從鏈頭開始檢索，按照算法規則找到一個大小符合要求的空閑盤區，分配給文件。若沒有合適的連續空閑塊，也可以將不同盤區的盤塊同時分配給一個文件，注意分配后可能要修改相應的鏈指針、盤區大小等數據。
如何回收：若回收區和某個空閑盤區相鄰，則需要將回收區合并到空閑盤區中。若回收區沒有和任何空閑區相鄰，將回收區作為單獨的一個空閑盤區掛到鏈尾。

特點：離散分配、連續分配都適用。為一個文件分配多個盤塊時效率更高

2.4 存儲空間管理一一位示圖法

位示圖：每個二進制位對應一個盤塊。

某時刻磁盤利用情況如下：

對應的位示圖：

在本例中，“0”代表盤塊空閑，“1”代表盤塊已分配。位示圖一般用連續的“字”來表示，如本例中一個字的字長是16位，字中的每一位對應一個盤塊。因此可以用（字號，位號）對應一個盤塊號。當然有的題目中也描述為（行號，列號）

重點重點：要能自己推出盤塊號與（字號位號）相互轉換的公式。
注意題目條件：盤塊號、字號、位號到底是從0開始還是從1開始
如本例中盤塊號、字號、位號從0開始，若n表示字長，則.
（字號，位號）=（i，j）的二進制位對應的盤塊號b=ni+j

本例中：
（0,1）→b=16X0+1
（1,10）→b=16X1+10
b號盤塊對應的字號i=b/n，位號j=b%n
b=13→i=13/16=0,j=13%16=13

如何分配：若文件需要K個塊，
①順序掃描位示圖，找到K個相鄰或不相鄰的“0”；
②根據字號、位號算出對應的盤塊號，將相應盤塊分配給文件；
③將相應位設置為“1”。
如何回收：①根據回收的盤塊號計算出對應的字號、位號；②將相應二進制位設為“0”

特點：連續分配、離散分配都適用

2.5 存儲空間管理一—成組鏈接法

空閑表法、空閑鏈表法不適用于大型文件系統，因為空閑表或空閑鏈表可能過大。UNIX系統中采用了成組鏈接法對磁盤空閑塊進行管理。
文件卷的目錄區中專門用一個磁盤塊作為“超級塊”，當系統啟動時需要將超級塊讀入內存。并且要保證內存與外存中的“超級塊”數據一致。

2.6 文件存儲空間管理小結

總結

以上是生活随笔為你收集整理的15 操作系统第四章 文件管理 文件的物理结构 文件存储空间管理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。