寫在前面：本文參考王道論壇的 操作系統(tǒng)考研復(fù)習(xí)指導(dǎo)單科書

文章目錄

• 第四章 文件管理
• • 4.1 內(nèi)存管理概念
  • • 4.1.1 文件的概念
    • 4.1.2 文件的邏輯結(jié)構(gòu)
    • • 1. 無結(jié)構(gòu)文件（流式文件）
      • 2.有結(jié)構(gòu)文件（記錄式文件）
    • 4.1.3 目錄結(jié)構(gòu)
    • • 1 文件控制塊和索引結(jié)點(diǎn)
      • 2 目錄結(jié)構(gòu)
    • 4.1.4 文件共享
  • 4.2 文件系統(tǒng)實(shí)現(xiàn)
  • • 4.2.1 文件系統(tǒng)層次結(jié)構(gòu)
    • 4.2.2 目錄實(shí)現(xiàn)
    • • 1.線性列表
      • 2. 哈希表
    • 4.2.3 文件實(shí)現(xiàn)
    • • 1.文件分配方式
      • 2. 文件存儲(chǔ)空間管理
  • 4.3 磁盤組織與管理
  • • 4.3.1 磁盤的結(jié)構(gòu)
    • 4.3.2 磁盤調(diào)度算法
    • 4.3.3 磁盤的管理
  • 王道習(xí)題

第四章 文件管理

4.1 內(nèi)存管理概念

4.1.1 文件的概念

4.1.2 文件的邏輯結(jié)構(gòu)

文件的邏輯結(jié)構(gòu)是從用戶觀點(diǎn)出發(fā)看到的文件的組織形式。文件的物理結(jié)構(gòu)（又稱文件的存儲(chǔ)結(jié)構(gòu)）是從實(shí)現(xiàn)觀點(diǎn)出發(fā)看到的文件在外存上的存儲(chǔ)組織形式。 文件的邏輯結(jié)構(gòu)與存儲(chǔ)介質(zhì)特性無關(guān)，但文件的物理結(jié)構(gòu)與存儲(chǔ)介質(zhì)的特性有很大關(guān)系。 文件的邏輯結(jié)構(gòu)實(shí)際上是指在文件的內(nèi)部，數(shù)據(jù)邏輯上是如何組織起來的。

按邏輯結(jié)構(gòu)，文件可分為無結(jié)構(gòu)文件和有結(jié)構(gòu)文件兩種。

1. 無結(jié)構(gòu)文件（流式文件）

無結(jié)構(gòu)文件是最簡(jiǎn)單的文件組織形式。無結(jié)構(gòu)文件將數(shù)據(jù)按照順序組織成記錄并積累、保存，它是有序相關(guān)信息項(xiàng)的集合，以字節(jié)為單位。 由于無結(jié)構(gòu)文件沒有結(jié)構(gòu)，因而對(duì)記錄的訪問只能通過窮舉搜索的方式，因此這種文件對(duì)大多數(shù)應(yīng)用并不適用。但字符流的無結(jié)構(gòu)文件管理簡(jiǎn)單，用戶可以方便地對(duì)其進(jìn)行操作。所以，那些對(duì)基本信息單位操作不多的文件較適合采用字符流的無結(jié)構(gòu)方式，如源程序文件、目標(biāo)代碼文件等。

2.有結(jié)構(gòu)文件（記錄式文件）

有結(jié)構(gòu)文件按記錄的組織形式可以分為如下幾種：

1）順序文件。文件中的記錄一個(gè)接一個(gè)地順序排列，記錄通常是定長的，可以順序存儲(chǔ)或者以鏈表方式存儲(chǔ)，在訪問時(shí)需要順序搜索文件。 順序文件有以下兩種結(jié)構(gòu)：
第一種是串結(jié)構(gòu)，記錄之間的順序與關(guān)鍵字無關(guān)。 通常的辦法是由時(shí)間決定，即按存入時(shí)間的先后排列，最先存入的記錄作為第一條記錄，其次存入的作為第二條記錄，以此類推。

第二種是順序結(jié)構(gòu)，指文件中的所有記錄按照關(guān)鍵字順序排列。

在對(duì)記錄進(jìn)行批量操作，即每次要讀或?qū)懸淮笈涗洉r(shí)，順序文件的效率是所有邏輯文件中最高的；此外，也只有順序文件次啊能存儲(chǔ)在磁帶上， 并能有效工作，但順序文件在查找、修改增加或刪除單條記錄的操作比較困難。

2）索引文件。 索引文件的示意圖。 對(duì)于定長記錄文件（長度為L），要查找第i條記錄，可以直接按照下式計(jì)算得到第i條記錄相對(duì)于第一條記錄的地址：
$$A_i=i\times L$$

然而，對(duì)于可變長記錄文件， 要查找第i條記錄，必須順序查找前i-1條記錄， 從而獲得相應(yīng)記錄的長度L，進(jìn)而按照下式進(jìn)行計(jì)算得到第i條記錄的首址：

$$A_i={\Sigma }_{i=0}^{i?1}{L}_i+i$$

變長記錄文件只能順序查找，系統(tǒng)開銷很大。 為此，可以建立一張索引表以加快檢索速度， 索引表本身是定長記錄的順序文件。在記錄很多或者訪問要求高的文件中， 需要引入索引以提供有效的訪問。

實(shí)際中，通過索引可以成百上千倍地提高訪問速度。

3）索引順序文件。 索引順序文件是順序和索引兩種組織形式的結(jié)合。 索引順序文件將順序文件中的所有記錄分成若干組， 為順序文件建立一張索引表，在索引表中為每組中的第一條記錄建立一個(gè)索引項(xiàng)，其中包含該記錄的關(guān)鍵字值和指向該記錄的指針。

主文件中記錄分組排列，同一個(gè)組中的關(guān)鍵字可以無序，但是組與組之間的關(guān)鍵字必須有序。查找一條記錄時(shí)，首先通過索引表找到其所在的組，然后在該組中使用順序查找，就能很快找到記錄。

對(duì)于含有N條記錄的順序文件， 查找某關(guān)鍵字值的記錄時(shí)，平均查找N/2次。

在索引順序文件中，假設(shè)N條記錄分為$\sqrt{N}$組，索引表中有$\sqrt{N}$個(gè)表項(xiàng)，每組有$\sqrt{N}$個(gè)記錄，在查找某關(guān)鍵字值的記錄時(shí)，先順序查找索引表，需要查找$\frac{\sqrt{N}}{2}$次，然后在主文件中對(duì)應(yīng)的組中循序查找，也需要查找$\frac{\sqrt{N}}{2}$次，總共需要$\sqrt{N}$次。顯然，索引順序文件提高了查找效率，若記錄數(shù)很多，則可采用兩級(jí)或者多級(jí)縮影。

4）直接文件或散列文件（Hash File）。 給定記錄的鍵值或通過散列函數(shù)轉(zhuǎn)換的鍵值直接決定記錄的物理地址。這種映射結(jié)構(gòu)不同于順序文件和索引文件，沒有順序的特性。

散列文件有很高的存取速度，但是會(huì)引起沖突，即不同關(guān)鍵字的散列函數(shù)值相同。

有結(jié)構(gòu)文件邏輯上的組織，是為在文件中查找數(shù)據(jù)服務(wù)的（順序查找、索引查找、索引順序查找和哈希查找）。

4.1.3 目錄結(jié)構(gòu)

與文件管理系統(tǒng)和文件集合相關(guān)聯(lián)的是文件目錄，它包含有關(guān)文件的信息如屬性、位置和所有權(quán)等，這些信息主要由操作系統(tǒng)進(jìn)行管理。

首先我們來看看目錄管理的基本要求：

從用戶的角度看，目錄在用戶（應(yīng)用程序）所需要的文件名和文件之間提供一種映射，所以目錄管理需要實(shí)現(xiàn)“按名存取”；目錄存取的效率直接影響到系統(tǒng)的性能，所以要提高對(duì)目錄的檢索速度；在共享系統(tǒng)中，目錄還需要提供用于控制文件的信息。此外，文件允許重名也是用戶的合理和必然要求，目錄管理通過樹形結(jié)構(gòu)來解決和實(shí)現(xiàn)。

前面介紹了文件內(nèi)部的邏輯結(jié)構(gòu)，下面介紹多個(gè)文件之間在邏輯上是如何組織的，這實(shí)際上是文件“外部”的邏輯結(jié)構(gòu)的問題。

1 文件控制塊和索引結(jié)點(diǎn)

和進(jìn)程管理一樣，為實(shí)現(xiàn)目錄管理，操作系統(tǒng)中引入了文件控制塊這一數(shù)據(jù)結(jié)構(gòu)。

1）文件控制塊。文件控制塊（FCB）是用來存放控制文件需要的各種信息的數(shù)據(jù)結(jié)構(gòu)，以實(shí)現(xiàn)“按名存取”。FCB的有序集合稱為文件目錄，一個(gè)FCB就是一個(gè)文件目錄項(xiàng)。 為了創(chuàng)建一個(gè)新文件，系統(tǒng)將分配一個(gè)FCB并存放在文件目錄中，成為目錄項(xiàng)。

FCB主要包含以下信息：

• 基本信息，比如文件名、文件的物理地址、文件的邏輯結(jié)構(gòu)、文件的物理結(jié)構(gòu)等
• 存取控制信息，比如文件存取權(quán)限等
• 使用信息，比如文件建立時(shí)間、修改時(shí)間

2）索引結(jié)點(diǎn)。在檢索目錄文件的過程中，只用到了文件名，僅當(dāng)找到一個(gè)目錄項(xiàng)（查找文件名與目錄項(xiàng)中文件名匹配）時(shí)，才需要從該目錄項(xiàng)中讀出該文件的物理地址。 也就是說，在檢索目錄時(shí)，文件的其他描述信息不會(huì)用到，也不需要調(diào)入內(nèi)存。因此，有的系統(tǒng)（比如UNIX）采用了文件名和文件描述信息分開的方法，文件描述信息單獨(dú)形成一個(gè)索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱為i結(jié)點(diǎn)，在文件目錄中的每個(gè)目錄項(xiàng)僅由文件名和指向該文件所對(duì)應(yīng)的i結(jié)點(diǎn)的指針構(gòu)成。

一個(gè)FCB的大小是64B，盤塊大小是1KB，因此在每個(gè)盤塊中可以存放16個(gè)FCB（注意，FCB必須連續(xù)存放）。而在UNIX系統(tǒng)中，一個(gè)目錄項(xiàng)僅占16B，其中14B是文件名，2B是 i結(jié)點(diǎn)指針。在1KB的盤塊中可存放64個(gè)目錄項(xiàng)。這樣，就可使查找文件時(shí)的平均啟動(dòng)磁盤次數(shù)減少到原來的1/4，大大節(jié)省了系統(tǒng)開銷。

存放在磁盤上的索引結(jié)點(diǎn)稱為磁盤索引結(jié)點(diǎn)，UNIX中的每個(gè)文件都有一個(gè)唯一的磁盤索引結(jié)點(diǎn)，主要包括以下幾個(gè)方面：

• 文件主標(biāo)識(shí)符，擁有該文件的個(gè)人或小組的標(biāo)識(shí)符
• 文件類型，包括普通文件、目錄文件、特別文件
• 文件存取權(quán)限，各類用戶對(duì)該文件的存取權(quán)限
• 文件物理地址，每個(gè)索引結(jié)點(diǎn)中含有13個(gè)地址項(xiàng)，它們以直接或間接方式給出數(shù)據(jù)文件所在盤塊的編號(hào)
• 文件長度，以字節(jié)為單位
• 文件鏈接計(jì)數(shù)，在本文件系統(tǒng)中所有指向該文件的文件名的指針計(jì)數(shù)
• 文件存取時(shí)間，本文件最近被進(jìn)程存取的時(shí)間、最近被修改的時(shí)間及索引結(jié)點(diǎn)最近被修改的時(shí)間

文件被打開時(shí)，磁盤索引結(jié)點(diǎn)復(fù)制到內(nèi)存的索引結(jié)點(diǎn)中，以便于使用。 在內(nèi)存索引節(jié)點(diǎn)中又增加了以下內(nèi)容：

• 索引結(jié)點(diǎn)編號(hào)，用于標(biāo)識(shí)內(nèi)存索引結(jié)點(diǎn)
• 狀態(tài)，指示i結(jié)點(diǎn)是否上鎖或被修改
• 訪問計(jì)數(shù)，每當(dāng)有一進(jìn)程要訪問此i結(jié)點(diǎn)時(shí)，計(jì)數(shù)加1，訪問結(jié)束減1
• 邏輯設(shè)備號(hào)，文件所屬文件系統(tǒng)的邏輯設(shè)備號(hào)
• 鏈接指針，設(shè)置分別指向空閑鏈表和散列隊(duì)列的指針

2 目錄結(jié)構(gòu)

在目錄這個(gè)層次上所需要執(zhí)行哪些操作呢？

• 搜索。當(dāng)用戶使用一個(gè)文件時(shí)，需要搜索目錄，已找到該文件對(duì)應(yīng)的目錄項(xiàng)
• 創(chuàng)建文件。當(dāng)創(chuàng)建一個(gè)新文件時(shí)，需要在目錄中增加一個(gè)目錄項(xiàng)
• 刪除文件。當(dāng)刪除一個(gè)文件時(shí)，需要在目錄中刪除相應(yīng)的目錄項(xiàng)。
• 顯示目錄。用戶可以請(qǐng)求顯示目錄的內(nèi)容，比如顯示該用戶目錄中的所有文件及其屬性。
• 修改目錄。某些文件屬性保存在目錄中，因而這些屬性的變化需要改變相應(yīng)的目錄項(xiàng)。

操作時(shí)考慮以下幾種目錄結(jié)構(gòu)

1）單級(jí)目錄結(jié)構(gòu)

在整個(gè)文件系統(tǒng)中只建立一張目錄表，每個(gè)文件占一個(gè)目錄項(xiàng)。

實(shí)現(xiàn)了按名存取，到那時(shí)存在查找速度慢，文件不允許重名，不便于文件共享等缺點(diǎn)，而且對(duì)于多用戶的操作系統(tǒng)顯然是不適用的。

2）兩級(jí)目錄結(jié)構(gòu)

將文件目錄分成主文件目錄（Master File Directory，MFD)和用戶文件目錄（User File Directory,UFD）兩級(jí)。

主文件目錄項(xiàng)記錄用戶名及相應(yīng)用戶文件目錄所在的存儲(chǔ)位置。

用戶文件目錄項(xiàng)記錄該用戶文件的FCB信息。

當(dāng)某用戶想要對(duì)其文件進(jìn)行訪問時(shí)，只需要搜索用戶對(duì)應(yīng)的UFD,這既解決了不同用戶文件之間的重名的問題，有一定程度上保證了文件的安全。

但是兩級(jí)目錄結(jié)構(gòu)缺乏靈活性，不能對(duì)文件分類。

3）多級(jí)目錄結(jié)構(gòu)（樹形目錄結(jié)構(gòu)）

用戶要訪問某個(gè)文件時(shí)，用文件的路徑名標(biāo)識(shí)文件，文件路徑名是個(gè)字符串，由從根目錄出發(fā)到所找文件通路上所有目錄名與數(shù)據(jù)文件名用分隔符/ 鏈接而成。 從根目錄出發(fā)的路徑稱為絕對(duì)路徑。當(dāng)層次較多時(shí)，每次從根目錄出發(fā)查詢會(huì)浪費(fèi)時(shí)間，于是加入了當(dāng)前目錄，進(jìn)程對(duì)各文件的訪問都是相對(duì)于當(dāng)前目錄進(jìn)行的。

樹形目錄結(jié)構(gòu)可以方便地對(duì)文件進(jìn)行分類，層次結(jié)構(gòu)清晰，也能有效地進(jìn)行文件的管理和保護(hù)。 但是，在樹形目錄中查找一個(gè)文件時(shí)，需要按照路徑名依次訪問中間結(jié)點(diǎn)，這就增加了磁盤訪問次數(shù)，影響查詢速度。

4）無環(huán)圖目錄結(jié)構(gòu)。樹形目錄結(jié)構(gòu)能便于實(shí)現(xiàn)文件分類，但是不便于實(shí)現(xiàn)文件共享。 為此在樹形目錄結(jié)構(gòu)的基礎(chǔ)上增加了一些指向同一結(jié)點(diǎn)的有向邊，使得整個(gè)目錄成為一個(gè)有向無環(huán)圖。引入無環(huán)圖目錄結(jié)構(gòu)是為了實(shí)現(xiàn)文件共享。

需要為每個(gè)共享節(jié)點(diǎn)設(shè)置一個(gè)共享計(jì)數(shù)器，每當(dāng)圖中增加對(duì)該結(jié)點(diǎn)的共享鏈時(shí)，計(jì)數(shù)器加1；每當(dāng)某用戶提出刪除該結(jié)點(diǎn)時(shí)，計(jì)數(shù)器減1.僅當(dāng)共享計(jì)數(shù)器為0時(shí)，才真正刪除該結(jié)點(diǎn)，否則僅刪除請(qǐng)求用戶的共享鏈。 共享文件（或目錄）不同于文件拷貝（副本）。對(duì)于共享文件，只存在一個(gè)真正的文件，熱河改變都會(huì)為其他用戶所見。

無環(huán)圖結(jié)構(gòu)方便文件的共享，但是使得系統(tǒng)的管理變得更加復(fù)雜。

4.1.4 文件共享

文件共享使得多個(gè)用戶（進(jìn)程）共享同一個(gè)文件，系統(tǒng)中只需要保留該文件的一個(gè)副本。如果系統(tǒng)不能提供貢獻(xiàn)功能，則每個(gè)需要該文件的用戶都要有自己的副本，會(huì)造成對(duì)存儲(chǔ)空間的極大浪費(fèi)。

現(xiàn)代常用的兩種文件共享方法有

1.基于索引結(jié)點(diǎn)的共享方式（硬鏈接）

2利用符號(hào)鏈實(shí)現(xiàn)文件共享（軟鏈接）

4.2 文件系統(tǒng)實(shí)現(xiàn)

在學(xué)習(xí)本節(jié)時(shí)，請(qǐng)讀者思考如下問題：

在目錄中查找某個(gè)文件可以使用什么方法？

文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)有何區(qū)別？單個(gè)文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之間是否存在某些制約關(guān)系？

4.2.1 文件系統(tǒng)層次結(jié)構(gòu)

現(xiàn)代操作系統(tǒng)有多種文件系統(tǒng)類型（如FAT32,NTFS,ext2，ext2，ext4等），因此文件系統(tǒng)的層次結(jié)構(gòu)也不盡相同。下圖是一種合理的層次結(jié)構(gòu)。

1.用戶調(diào)用接口

文件系統(tǒng)為用戶提供與文件及目錄有關(guān)的系統(tǒng)調(diào)用，如新建、打開，讀寫，關(guān)閉，刪除文件，建立、刪除目錄等。 此層由若干程序模塊組成，每個(gè)模塊對(duì)應(yīng)一條系統(tǒng)調(diào)用，用戶發(fā)出系統(tǒng)調(diào)用時(shí)，控制即轉(zhuǎn)入相應(yīng)的模塊。

2 文件目錄系統(tǒng)
文件目錄系統(tǒng)的主要功能是管理文件目錄， 其任務(wù)有管理活躍文件目錄表、管理讀寫狀態(tài)信息表、管理用戶進(jìn)程的打開文件表、管理和組織存儲(chǔ)設(shè)備上的文件目錄結(jié)構(gòu)，調(diào)用下一級(jí)存儲(chǔ)控制模塊。

3 存取控制驗(yàn)證模塊

實(shí)現(xiàn)文件保護(hù)主要由該級(jí)軟件完成，它把用戶的訪問要求與FCB中指示的訪問控制權(quán)限進(jìn)行比較，以確認(rèn)訪問的合法性。

4 邏輯文件系統(tǒng)與文件信息緩沖區(qū)

邏輯文件系統(tǒng)與文件信息緩沖區(qū)的主要功能是，根據(jù)文件的邏輯結(jié)構(gòu)將用戶要讀寫的邏輯記錄轉(zhuǎn)換成文件邏輯結(jié)構(gòu)內(nèi)的相應(yīng)塊號(hào)。

5 物理文件系統(tǒng)

主要功能是把邏輯記錄所在的相對(duì)塊號(hào)轉(zhuǎn)換成實(shí)際的物理地址。

6 輔助分配模塊

分配模塊的主要功能是管理輔存空間，即負(fù)責(zé)分配輔存空閑空間和回收輔存空間。

7 設(shè)備管理程序模塊
主要功能是分配設(shè)備、分配設(shè)備讀寫用緩沖區(qū)、磁盤調(diào)度、啟動(dòng)設(shè)備、處理設(shè)備中斷，釋放設(shè)備讀寫緩沖區(qū)，釋放設(shè)備等。

我們可以通過用戶請(qǐng)求訪問某個(gè)文件時(shí)發(fā)生的一系列事情來輔助記憶文件系統(tǒng)的層次結(jié)構(gòu)。

例如，用戶要查看文件F中的內(nèi)容，對(duì)操作系統(tǒng)發(fā)出命令（OS有面向用戶的接口），于是就經(jīng)過了第0級(jí)的用戶調(diào)用接口。

OS得到命令后，需要查找目錄以查找文件F的索引信息，可能是FCB，也可能是索引節(jié)點(diǎn)，經(jīng)過了第1級(jí)文件系統(tǒng)目錄。

通過目錄找到文件FCB后，需要查看文件FCB上的信息，看看這個(gè)用戶有沒有訪問權(quán)限，于是經(jīng)過了存取控制驗(yàn)證模塊。

用戶通過驗(yàn)證后，就真正開始尋址。OS的尋址往往先得到邏輯地址，再得到物理地址，于是在開始尋址時(shí)，OS經(jīng)過邏輯文件系統(tǒng)與文件信息緩沖區(qū)，得到了相應(yīng)文件的內(nèi)容的邏輯地址。

把邏輯地址轉(zhuǎn)換為物理地址， 是在物理文件系統(tǒng)中完成的。

至此為止，尋址完成。 尋址完成后，我們關(guān)心的是找到的這塊空間應(yīng)該如何管理，若要釋放這塊空間，則任務(wù)就交給輔助分配模塊，若要把這塊空間分配給設(shè)備用于I/O，則把任務(wù)交給設(shè)備管理程序模塊。

4.2.2 目錄實(shí)現(xiàn)

在讀文件前，必須先打開文件；打開文件時(shí)，OS利用路徑名找到相應(yīng)目錄項(xiàng)，目錄項(xiàng)中提供了查找文件磁盤塊所需要的信息。 目錄實(shí)現(xiàn)的基本方法有線性列表和哈希表兩種，要注意目錄的實(shí)現(xiàn)就是為了查找，因此線性列表實(shí)現(xiàn)對(duì)應(yīng)線性查找，哈希表的實(shí)現(xiàn)對(duì)應(yīng)散列查找。

1.線性列表

最簡(jiǎn)單的目錄實(shí)現(xiàn)方法是使用存儲(chǔ)文件名和數(shù)據(jù)塊指針的線性表。 創(chuàng)建新文件時(shí)，必須首先搜索目錄表以確定沒有同名的文件存在，然后在目錄表后增加一個(gè)目錄項(xiàng)。 刪除文件則根據(jù)給定的文件名搜索目錄表，接著釋放分配給它的空間。重用目錄項(xiàng)有很多方法： 可以將目錄項(xiàng)標(biāo)記為不再使用，或者將它加到空閑目錄項(xiàng)表上，還可以將目錄表中的最后一個(gè)目錄項(xiàng)復(fù)制到空閑位置，并降低目錄表長度。采用鏈表結(jié)構(gòu)可以減少刪除文件的時(shí)間，其優(yōu)點(diǎn)在于實(shí)現(xiàn)簡(jiǎn)單，不過由于線性表的特殊性，比較費(fèi)時(shí)。

2. 哈希表

哈希表根據(jù)文件名得到一個(gè)值，并返回一個(gè)指向線性列表中元素的指針。 這種方法優(yōu)點(diǎn)是查找非常迅速，插入和刪除也很簡(jiǎn)單，不過需要一些預(yù)備措施來避免沖突。最大的困難是哈希表長度固定以及哈希函數(shù)對(duì)表長的依賴性。

目錄查詢是通過在磁盤上反復(fù)搜索完成的，需要不斷進(jìn)行I/O操作，開銷較大。 所以如前所述， 為了減少I/O操作，把當(dāng)前使用的文件目錄復(fù)制到內(nèi)存，以后要使用該文件的時(shí)候只需要在內(nèi)存中操作，因此降低了磁盤操作次數(shù)，提高了系統(tǒng)速度。

4.2.3 文件實(shí)現(xiàn)

文件的實(shí)現(xiàn)就是研究文件的物理結(jié)構(gòu)，即文件數(shù)據(jù)在物理存儲(chǔ)設(shè)備上是如何分布和組織的。同一個(gè)問題有兩個(gè)方面的回答：一是文件的分配方式，講的是對(duì)磁盤非空閑塊的管理；二是文件存儲(chǔ)空間管理，講的是對(duì)磁盤空閑塊的管理。

1.文件分配方式

文件分配方式對(duì)應(yīng)于文件的物理結(jié)構(gòu)，是指如何為文件分配磁盤塊。常用的磁盤空間分配方法有三種：連續(xù)分配，鏈接分配和索引分配。 有的系統(tǒng)（比如RDOS操作系統(tǒng)）對(duì)三種方法都支持，但更普遍的是一個(gè)系統(tǒng)只支持一種方法。

1）連續(xù)分配

連續(xù)分配方法要求每個(gè)文件在磁盤上占有一組連續(xù)的塊，磁盤地址定義了磁盤上的一個(gè)線性排序。這種排序使得作業(yè)訪問磁盤時(shí)需要的尋道數(shù)和尋道時(shí)間最小。

文件的連續(xù)分配可以用第一塊的磁盤地址和連續(xù)塊的數(shù)量來定義。一個(gè)文件的目錄條目應(yīng)該包括開始?jí)K的地址和該文件所分配區(qū)域的長度。

連續(xù)分配支持順序訪問和直接訪問（即隨機(jī)訪問）。優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單、存取速度快。缺點(diǎn)是文件長度不宜動(dòng)態(tài)增加，因?yàn)橐粋€(gè)文件末尾后的盤塊可能已分配給其他文件，一旦需要增加，就需要大量移動(dòng)盤塊。此外，反復(fù)增刪文件后會(huì)產(chǎn)生外部碎片，且很難確定一個(gè)文件需要的空間大小。

連續(xù)分配只適合于長度固定的文件。

2） 鏈接分配

鏈接分配采用離散分配的方式，消除了外部碎片，因此顯著提高了磁盤空間的利用率；又因?yàn)楦鶕?jù)文件的當(dāng)前需求為其分配必需的盤塊，當(dāng)文件動(dòng)態(tài)增長時(shí)，可以動(dòng)態(tài)地再為它分配盤塊，因此無需事先知道文件的大小。此外，對(duì)文件的增刪改也非常方便。 鏈接分配又分為隱式鏈接和顯式鏈接兩種。

隱式鏈接如下圖所示。每個(gè)文件對(duì)應(yīng)一個(gè)磁盤塊的鏈表；磁盤塊分布在磁盤的任何地方，除最后一個(gè)磁盤塊外，每個(gè)盤塊都有指向下一個(gè)盤塊的指針，這些指針對(duì)用戶是透明的。 目錄包括文件 的第一塊的指針和最后一塊的指針。

隱式鏈接分配的缺點(diǎn)是無法直接訪問盤塊，只能通過指針順序訪問文件，且盤塊指針會(huì)消耗一定的存儲(chǔ)空間。隱式鏈接分配的穩(wěn)定性也是一個(gè)問題，系統(tǒng)在運(yùn)行過程中由于軟件或硬件錯(cuò)誤導(dǎo)致鏈表中的指針丟失或者損壞，會(huì)導(dǎo)致文件數(shù)據(jù)的丟失。

顯式鏈接分配方式是指把用于鏈接文件各物理塊的指針，從每個(gè)物理塊的塊末尾中提取出來，顯式地存放在內(nèi)存的一張鏈接表中。該表在整個(gè)磁盤中僅設(shè)置一張，稱為文件分配表（File Allocation Table, FAT）。每個(gè)表項(xiàng)中存放對(duì)應(yīng)塊的下一塊鏈接指針，即下一個(gè)盤塊號(hào)。

FAT表項(xiàng)與全部磁盤塊是一一對(duì)應(yīng)的，并且可以用特殊的數(shù)字-1表示文件的最后一塊，用-2表示這個(gè)磁盤塊是空閑的（當(dāng)然也可以指定-2，-3等等）。因此，文件分配表不僅記錄了文件各塊之間的先后鏈接關(guān)系，同時(shí)還標(biāo)記了空閑的磁盤塊，操作系統(tǒng)也可以通過FAT對(duì)文件存儲(chǔ)空間進(jìn)行管理。

一個(gè)磁盤只會(huì)建立一張F(tuán)AT表，FAT表在系統(tǒng)啟動(dòng)時(shí)就會(huì)被讀入內(nèi)存，并且常駐內(nèi)存，因此查找FAT的過程是在內(nèi)存中進(jìn)行的。

顯式鏈接分配方式的優(yōu)點(diǎn)：
很方便文件拓展，不會(huì)有碎片問題，外存利用率高，并且支持隨機(jī)訪問。相比于隱式鏈接分配，地址轉(zhuǎn)換時(shí)不需要訪問磁盤，因此文件的訪問效率更高。
缺點(diǎn)：文件分配表需要占用一定的存儲(chǔ)空間。

注：鏈接分配默認(rèn)情況下指的是隱式鏈接分配方式。

3）索引分配

鏈接分配方式解決了連續(xù)分配的外部碎片和文件大小管理的問題。但是，鏈接分配不能有效支持隨機(jī)訪問(FAT除外，即顯式鏈接分配除外)。索引分配解決了隨機(jī)訪問這個(gè)問題，它把每個(gè)文件的所有的盤塊號(hào)都集中放在一起構(gòu)成索引表（又稱索引塊），從而索引分配支持隨機(jī)訪問（直接訪問）。存放索引表的磁盤塊稱為索引塊，存放文件數(shù)據(jù)的磁盤塊稱為數(shù)據(jù)塊。

每個(gè)文件都有其索引塊，這是一個(gè)磁盤塊地址的數(shù)組。 索引塊的第i個(gè)條目指向文件的第i個(gè)塊。目錄條目包括索引塊的地址，換句話說，目錄中記錄的是文件的索引塊的塊號(hào)。要讀第i塊，通過索引塊的第i個(gè)條目的指針來查找和讀入所需的塊。索引表建立了邏輯塊號(hào)和物理塊號(hào)的一一映射關(guān)系。

優(yōu)點(diǎn)：索引分配支持直接訪問，且沒有外部碎片問題。文件拓展也很容易實(shí)現(xiàn)（只需要給文件分配一個(gè)空閑塊，并增加一個(gè)索引表項(xiàng)即可）

缺點(diǎn)： 磁盤表要占用一定的存儲(chǔ)空間

如果文件太大，索引表項(xiàng)太多，可以采取以下三種方法解決：
1）鏈接方案

如果索引表太大，一個(gè)索引塊裝不下，那么可以將多個(gè)索引塊鏈接其來存放。

缺點(diǎn)： 若文件很大，索引表很長，就需要將很多個(gè)索引塊鏈接起來。想要找到i號(hào)索引塊，必須先讀入0~i-1號(hào)索引塊，這就導(dǎo)致磁盤I/O操作次數(shù)過多，查找效率低下。

2） 多層索引

建立多層索引（原理類似于多層頁表），使得第一層的索引表項(xiàng)指向第二層的索引塊。還可以根據(jù)文件大小的要求建立第三層、第四層的索引塊

3）混合索引
將多種索引分配方式相結(jié)合的分配方式。例如，系統(tǒng)既采用直接地址，又采用單級(jí)索引分配方式或兩級(jí)索引分配方式。

2. 文件存儲(chǔ)空間管理

1）文件存儲(chǔ)器空間的劃分與初始化。一般來說，一個(gè)文件存儲(chǔ)在一個(gè)文件卷內(nèi)。文件卷可以是物理盤的一部分，也可以是整個(gè)物理盤，支持超大型文件的文件卷也可由多個(gè)物理盤組成，如下圖。

在一個(gè)文件卷中，文件數(shù)據(jù)信息的空間（文件區(qū)）和存放文件控制信息FCB的空間（目錄區(qū)）是分離的。

由于存在很多種類的文件表示和存放格式，所以現(xiàn)代操作系統(tǒng)中一般都有很多不同的文件管理模塊，通過它們可以訪問不同格式的邏輯卷中的文件。 邏輯卷在提供文件服務(wù)前，必須由對(duì)應(yīng)的文件程序進(jìn)行初始化，劃分好目錄區(qū)和文件區(qū)，建立空閑空間管理表格及存放邏輯卷信息的超級(jí)塊。

2）文件存儲(chǔ)器空間管理。 文件存儲(chǔ)設(shè)備分成許多大小相同的物理塊，并以塊為單位交換信息，因此，文件存儲(chǔ)設(shè)備的管理實(shí)質(zhì)上是對(duì)空閑塊的組織和管理，它包括空閑塊的組織、分配與回收等問題。

（1）空閑表法

空閑表法屬于連續(xù)分配方式。 它與內(nèi)存的動(dòng)態(tài)分配方式類似，為每個(gè)文件分配一塊連續(xù)的存儲(chǔ)空間。系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑盤塊表，每個(gè)空閑區(qū)對(duì)應(yīng)一個(gè)空閑表項(xiàng)，其中包括表項(xiàng)序號(hào)、該空閑區(qū)的第一個(gè)盤塊號(hào)，該區(qū)的空閑盤塊數(shù)等信息。 再將所有的空閑區(qū)按照起始盤塊號(hào)遞增的次序排列。

空閑盤區(qū)的分配與內(nèi)存的動(dòng)態(tài)分配類似，同樣采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等。例如，在系統(tǒng)為某新建的文件分配空閑盤塊時(shí)，先順序地檢索空閑盤塊表的各表項(xiàng)，直到找到第一個(gè)其大小能滿足要求的空閑區(qū)，再將該盤區(qū)分配給用戶，同時(shí)修改空閑盤塊表。

系統(tǒng)在對(duì)用戶所釋放的存儲(chǔ)空間進(jìn)行回收時(shí)，也采用類似于內(nèi)存回收的方法，即要考慮回收取 是否與空閑表中插入點(diǎn)的前區(qū)和后區(qū)相鄰接，相鄰的話應(yīng)該合并。

（2）空閑鏈表法

將所有空閑盤區(qū)拉成一條空閑鏈，根據(jù)構(gòu)成鏈所用的基本元素不同，可把鏈表分為兩種形式： 空閑盤塊鏈和空閑盤區(qū)鏈。

空閑盤塊鏈將磁盤上的所有空閑空間以盤塊為單位拉成一條鏈。 當(dāng)用戶因?yàn)閯?chuàng)建文件而請(qǐng)求分配存儲(chǔ)空間時(shí)，系統(tǒng)從鏈?zhǔn)组_始，依次摘下適當(dāng)數(shù)目的空閑盤塊分配給用戶。當(dāng)用戶因?yàn)閯h除文件而釋放存儲(chǔ)空間時(shí)，系統(tǒng)將回收的盤塊依次插入空閑盤塊鏈的末尾。這種方法的優(yōu)點(diǎn)是分配和回收一個(gè)盤塊的過程非常簡(jiǎn)單，但在為一個(gè)文件分配盤塊時(shí)可能要重復(fù)多次操作。

空閑盤區(qū)鏈 將磁盤上的所有空閑盤區(qū)（每個(gè)盤區(qū)可包含若干盤塊）拉成一條鏈。再每個(gè)盤區(qū)上除了用于指示下一個(gè)空閑盤區(qū)的指針外，還應(yīng)該有能指明本盤區(qū)大小（盤塊號(hào)）的信息。 分配盤區(qū)的方法與內(nèi)存的動(dòng)態(tài)分區(qū)分配類似，通常采用首次適應(yīng)算法。 回收盤區(qū)時(shí)，注意合并的問題。

（3）位示圖法

位示圖利用二進(jìn)制的一位來表示磁盤中的一個(gè)盤塊的使用情況，磁盤上所有的盤塊都有一個(gè)二進(jìn)制位與之對(duì)應(yīng)。 其值為“0”表示對(duì)應(yīng)的盤塊空閑；其值為1時(shí)表示對(duì)應(yīng)的盤塊已分配。

每個(gè)二進(jìn)制位對(duì)應(yīng)一個(gè)盤塊。

王道書上：（字號(hào)，位號(hào)）或者稱為（行號(hào)，列號(hào)）都是從1開始編號(hào)的。

盤塊的分配：

1）順序掃描位示圖，從中找出一個(gè)或一組為0的二進(jìn)制位。2）將找到的一個(gè)或者一組二進(jìn)制位，轉(zhuǎn)換成與之對(duì)應(yīng)的盤塊號(hào)。若找到的為0 的二進(jìn)制位位于位示圖的第i行，第j列，則其相應(yīng)的盤塊號(hào)按照下式計(jì)算（n代表每行的位數(shù)，也就是字長）
$$b=n(i?1)+j這是從1開始編號(hào)的情況$$

3）修改位示圖，令map[i,j]=1

盤塊的回收:

1）將回收盤塊的盤塊號(hào)轉(zhuǎn)換成位示圖中的行號(hào)和列號(hào)，轉(zhuǎn)換公式為
$$i=(b?1)/(n+1)$$
$$j=(b?1)mod(n+1)$$

2）修改位示圖，令map[i,j]=0

（4）成組鏈接法

空閑表法和空閑鏈表法都不適用于大型文件系統(tǒng)，因?yàn)檫@會(huì)使空閑表或空閑鏈表太大。在UNIX系統(tǒng)中采用的是成組鏈接法，這種方法結(jié)合了空閑表和空閑鏈表兩種方法，克服了表太大的缺點(diǎn)。

文件卷的目錄區(qū)中專門用一個(gè)磁盤塊作為“超級(jí)塊”，當(dāng)系統(tǒng)啟動(dòng)時(shí)需要將超級(jí)塊讀入內(nèi)存。并且要保證內(nèi)存和外存中超級(jí)塊數(shù)據(jù)一致（超級(jí)塊充當(dāng)了鏈表中鏈頭的作用）。
一個(gè)超級(jí)塊記錄下一組空閑盤塊數(shù)和空閑塊號(hào)

大致思想是：一個(gè)超級(jí)塊中記錄下一組空閑塊的數(shù)量和空閑塊號(hào)，對(duì)于下一組空閑塊，選第一個(gè)空閑塊再存儲(chǔ)接下來的空閑塊的數(shù)量和塊號(hào)，依次類推。

4.3 磁盤組織與管理

4.3.1 磁盤的結(jié)構(gòu)

磁盤（Disk）是由表面涂有磁性物質(zhì)的金屬或者塑料構(gòu)成的圓形盤片，通過一個(gè)稱為磁頭的導(dǎo)體線圈從磁盤存取數(shù)據(jù)。在讀/寫操作期間，磁頭固定，磁盤在下面高速旋轉(zhuǎn)。

磁盤盤面上的數(shù)據(jù)存儲(chǔ)在一組同心圓中，稱為磁道。 每個(gè)磁道與磁頭一樣寬，一個(gè)盤面上由上千個(gè)磁道。磁道又劃分為幾百個(gè)扇區(qū)，每個(gè)扇區(qū)固定存儲(chǔ)大小（通常是512B），一個(gè)扇區(qū)稱為一個(gè)盤塊。相鄰磁道即相鄰扇區(qū)之間通過一定的間隙分隔開，以避免精度錯(cuò)誤。 注意，由于扇區(qū)按照固定圓心角度劃分，所以密度從最外道逐漸向最內(nèi)道增加的，磁盤的存儲(chǔ)能力受限于最內(nèi)道的最大記錄密度。

磁盤安裝在一個(gè)磁盤驅(qū)動(dòng)器中，它有磁頭臂、用于旋轉(zhuǎn)磁盤的主軸和用于數(shù)據(jù)輸入/輸出的電子設(shè)備組成。

扇區(qū)是磁盤可尋址的最小存儲(chǔ)單位，磁盤地址用“柱面號(hào)·盤面號(hào)·扇區(qū)號(hào)”表示。

用戶訪問文件，需要操作系統(tǒng)的服務(wù)，文件實(shí)際上存儲(chǔ)在磁盤中，操作系統(tǒng)接收到用戶的命令后，經(jīng)過一系列的檢驗(yàn)訪問權(quán)限和尋址過程后，最終都會(huì)到達(dá)磁盤，控制磁盤把相應(yīng)的數(shù)據(jù)信息讀出或修改。 當(dāng)有多個(gè)請(qǐng)求同時(shí)到達(dá)時(shí)，操作系統(tǒng)就要決定先為哪個(gè)請(qǐng)求服務(wù)，這就是磁盤調(diào)度算法要解決的問題。

4.3.2 磁盤調(diào)度算法

一次磁盤讀寫操作的時(shí)間由尋道時(shí)間、延遲時(shí)間和傳輸時(shí)間決定的。

1）尋道時(shí)間Ts。 活動(dòng)頭磁盤在讀寫信息前，將磁頭移動(dòng)到指定磁道所需要的時(shí)間。這個(gè)時(shí)間除跨越n條磁道的時(shí)間外，還包括啟動(dòng)磁臂的時(shí)間s
$$T_s=m\times n+s$$

式中，m是與磁盤驅(qū)動(dòng)器速度有關(guān)的常數(shù)，約為0.2ms，磁臂的啟動(dòng)時(shí)間約為2ms。

2）延遲時(shí)間Tr。 磁頭定位到某一磁道的扇區(qū)（塊號(hào)）所需要的時(shí)間，設(shè)磁盤的旋轉(zhuǎn)速度為r，則
$$T_r=\frac{1}{2r}$$

對(duì)于硬盤，典型的旋轉(zhuǎn)速度是5400轉(zhuǎn)/分，相當(dāng)于一周11.1ms，則Tr=5.55ms；對(duì)于軟盤，其旋轉(zhuǎn)速度為300~600轉(zhuǎn)/分，則Tr為50 ~100 ms

3）傳輸時(shí)間Tt。 從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時(shí)間，這個(gè)時(shí)間取決于每次所讀寫的字節(jié)數(shù)b和磁盤的旋轉(zhuǎn)速度：
$$T_t=\frac{b}{rN}$$

式中，r是磁盤每秒的轉(zhuǎn)數(shù)，N是一個(gè)磁道上的字節(jié)數(shù)。

在磁盤存取時(shí)間的計(jì)算中，尋道時(shí)間和磁盤調(diào)度算法相關(guān)，下面將介紹幾種算法；而延遲時(shí)間和傳輸時(shí)間都和磁盤旋轉(zhuǎn)速度相關(guān)，且為線性相關(guān)，所以在硬件上，轉(zhuǎn)速是磁盤性能一個(gè)非常重要的參數(shù)。

總平均存儲(chǔ)時(shí)間Ta可以表示為：
$$T_a=T_s+\frac{1}{2r}+\frac{b}{rN}$$

在實(shí)際的磁盤I/O操作中，存取時(shí)間與磁盤調(diào)度算法密切相關(guān)。調(diào)度算法直接決定尋道時(shí)間，從而決定總的存取時(shí)間。

目前常用的磁盤調(diào)度算法有以下幾種
1）先來先服務(wù)(First Come First Served,FCFS)算法
FCFS算法根據(jù)進(jìn)程請(qǐng)求訪問磁盤的先后順序進(jìn)行調(diào)度，這是一種最簡(jiǎn)單的調(diào)度算法，如下圖。該算法的優(yōu)點(diǎn)是具有公平性。若只有少量的進(jìn)程需要訪問，且大部分請(qǐng)求都是訪問簇聚的文件扇區(qū)，則有望達(dá)到較好的性能；缺點(diǎn)是，如果大量的進(jìn)程競(jìng)爭(zhēng)使用磁盤，并且請(qǐng)求訪問的磁道很分散，則性能很差。

2）最短尋找時(shí)間優(yōu)先(Shortest Seek Time First,SSTF)算法

SSTF算法選擇調(diào)度處理的磁道是與當(dāng)前磁頭所在磁道距離最近的磁道，以便使每次的尋道時(shí)間最短。 當(dāng)然，總是選擇最小尋找時(shí)間并不能保證平均尋道時(shí)間最小，但能提供比FCFS算法更好的性能。 這種算法會(huì)產(chǎn)生“饑餓”現(xiàn)象。

如果某時(shí)刻磁頭正在18號(hào)磁道，而在18號(hào)磁道附近頻繁地增加新的請(qǐng)求，則SSTF算法使得磁頭長時(shí)間在18號(hào)磁道附近工作，將使遠(yuǎn)處的磁道的訪問被無限期地延遲，即被“餓死”。

3）掃描（SCAN）算法(又稱為電梯調(diào)度算法)

SCAN算法在磁頭當(dāng)前移動(dòng)方向上選擇與當(dāng)前磁頭所在磁道距離最近的請(qǐng)求作為下一次服務(wù)的對(duì)象，實(shí)際上就是在最短尋找時(shí)間優(yōu)先算法的基礎(chǔ)上規(guī)定了磁頭運(yùn)動(dòng)的方向。由于磁頭移動(dòng)規(guī)律與電梯運(yùn)行相似，因此又稱電梯調(diào)度算法。 SCAN算法對(duì)最近掃描過的區(qū)域不公平，因此它在訪問局部性方面不如FCFS 和SSTF 算法好。

4）循環(huán)掃描（Circular SCAN ，C-SCAN）算法

在掃描算法的基礎(chǔ)上規(guī)定磁頭單向移動(dòng)來提供服務(wù)，回返時(shí)直接快速移動(dòng)至起始端而不服務(wù)任何請(qǐng)求。 由于SCAN算法偏向于處理那些接近最里或最外的磁道的訪問請(qǐng)求，所以使用改進(jìn)型的C-SCAN算法來避免這個(gè)問題。

采用SCAN算法和C-SCAN算法時(shí)，磁頭總是嚴(yán)格地遵循從盤面的一端到另一端，顯然，在實(shí)際使用時(shí)還可以改進(jìn)，即磁頭移動(dòng)只需要到達(dá)最遠(yuǎn)端的一個(gè)請(qǐng)求即可返回，不需要到達(dá)磁盤端點(diǎn)。 這種形式的SCAN算法和C-SCAN算法稱為LOOK調(diào)度和C-LOOK調(diào)度，因?yàn)樗鼈冊(cè)诔粋€(gè)給定方向移動(dòng)前會(huì)查看是否有請(qǐng)求。

注意，如沒有特殊說明，也可以默認(rèn)SCAN算法和C-SCAN算法為LOOK算法和C-LOOK調(diào)度。

對(duì)比以上幾種磁盤調(diào)度算法，FCFS算法太過簡(jiǎn)單，性能較差，僅僅在請(qǐng)求隊(duì)列長度接近于1時(shí)才較為理想；SSTF算法較為通用和自然；SCAN算法和C-SCAN算法在磁盤負(fù)載較大時(shí)比較占優(yōu)勢(shì)。

除減少尋道時(shí)間以外，減少延遲時(shí)間也是提高磁盤傳輸效率的重要因素，可以對(duì)盤面扇區(qū)進(jìn)行交替編號(hào)，對(duì)磁盤片組中的不同盤面錯(cuò)位命名。假設(shè)每個(gè)盤面有8個(gè)扇區(qū)，磁盤片組共8個(gè)盤面，可以采用下圖所示的編號(hào)。

磁盤是連續(xù)自轉(zhuǎn)設(shè)備，磁頭讀/寫一個(gè)物理塊后，需要經(jīng)過短暫的處理時(shí)間才能讀/寫下一塊。假設(shè)邏輯記錄數(shù)據(jù)連續(xù)存放在磁盤空間中，若在盤面上按扇區(qū)交替編號(hào)連續(xù)存放，則連續(xù)讀/寫多條記錄時(shí)能較少磁頭的延遲時(shí)間；同柱面不同盤面的扇區(qū)若能錯(cuò)位編號(hào)，連續(xù)讀/寫相鄰兩個(gè)盤面的邏輯記錄時(shí)也能減少磁頭延遲時(shí)間。

4.3.3 磁盤的管理

1 . 磁盤初始化
一個(gè)新的磁盤只是一個(gè)含有磁性記錄材料的空白盤。在磁盤能存儲(chǔ)數(shù)據(jù)之前，它必須分成扇區(qū)以便磁盤控制器能進(jìn)行讀和寫操作，這個(gè)過程稱為低級(jí)格式化（物理分區(qū)）。低級(jí)格式化為磁盤的每個(gè)扇區(qū)采用特別的數(shù)據(jù)結(jié)構(gòu)。每個(gè)扇區(qū)的數(shù)據(jù)結(jié)構(gòu)通常由頭、數(shù)據(jù)區(qū)域（通常為512B大小）和尾部組成。頭部和尾部包含了一些磁盤控制器所使用的信息。

為使用磁盤存儲(chǔ)文件，操作系統(tǒng)還需要將自己的數(shù)據(jù)結(jié)構(gòu)記錄在磁盤上：
第一步將磁盤分為由一個(gè)或多個(gè)柱面組成的分區(qū)（即熟悉的C盤和D盤等形式的分區(qū)）；

第二步對(duì)物理分區(qū)進(jìn)行邏輯格式化（創(chuàng)建文件系統(tǒng)），操作系統(tǒng)將初始的文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)到磁盤上，這些數(shù)據(jù)結(jié)構(gòu)包括空閑和已分配的空間以及一個(gè)初始為空的目錄。

2 . 引導(dǎo)塊

計(jì)算機(jī)啟動(dòng)時(shí)需要運(yùn)行一個(gè)初始化程序（自舉程序），它初始化CPU、寄存器、設(shè)備控制器和內(nèi)存等，接著啟動(dòng)操作系統(tǒng)。 為此，該自舉程序應(yīng)該找到磁盤上的操作系統(tǒng)內(nèi)核，裝入內(nèi)存，并轉(zhuǎn)到起始地址，從而開始操作系統(tǒng)的運(yùn)行。

自舉程序通常保存在ROM中，為了避免改變自舉代碼而需要改變ROM硬件的問題，因此只在ROM中保留很小的自舉裝入程序，將完整功能的自舉程序保存在磁盤的啟動(dòng)塊上，啟動(dòng)塊（也叫引導(dǎo)塊）位于磁盤的固定位。擁有啟動(dòng)分區(qū)的磁盤稱為啟動(dòng)磁盤或系統(tǒng)磁盤。

3 . 壞塊

由于磁盤有移動(dòng)部件且容錯(cuò)能力弱，因此容易導(dǎo)致一個(gè)或多個(gè)扇區(qū)損壞。部分磁盤甚至在出廠時(shí)就有壞扇區(qū)。根據(jù)所使用的磁盤和控制器，對(duì)這些塊有多種處理方式。

對(duì)于簡(jiǎn)單磁盤，比如電子集成驅(qū)動(dòng)器（IDE），壞扇區(qū)可手工處理，比如MS-DOS的Format命令執(zhí)行邏輯格式化（創(chuàng)建文件系統(tǒng)）時(shí)便會(huì)掃描磁盤以檢查壞扇區(qū)。壞扇區(qū)在FAT表中會(huì)標(biāo)明，因此程序不會(huì)使用。

對(duì)于復(fù)雜的磁盤，比如小型計(jì)算機(jī)系統(tǒng)接口(SCSI)，其控制器維護(hù)一個(gè)磁盤壞塊鏈表。該鏈表在出廠前進(jìn)行低級(jí)格式化時(shí)已經(jīng)初始化，并在磁盤的整個(gè)使用過程中不斷更新。低級(jí)格式化將一些塊保留作為備用，對(duì)操作系統(tǒng)透明。 控制器可以用備用塊來邏輯地代替壞塊，這種方案稱為扇區(qū)備用。

對(duì)壞塊的處理實(shí)際上就是利用某種機(jī)制，使得系統(tǒng)不去使用壞塊。壞塊屬于硬件故障，操作系統(tǒng)是不能修復(fù)壞塊的。

王道習(xí)題

答案：B 磁帶只能順序訪問；光盤、U盤，磁盤都可以隨機(jī)訪問。

答案：D尋道時(shí)間影響速度最大

答案：A

總結(jié)

以上是生活随笔為你收集整理的操作系统第四章-文件管理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。