操作系統(tǒng)第七章仍舊重要的文件和磁盤管理YSU課件

測(cè)驗(yàn)：

1、考慮下面的訪問(wèn)串：1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6。假定分配的物理塊有4、5、6三種情況，應(yīng)用下面的頁(yè)面替換算法，計(jì)算各會(huì)出現(xiàn)多少次缺頁(yè)中斷？注意，所給定的頁(yè)塊初始均為空，因此，首次訪問(wèn)一頁(yè)時(shí)就會(huì)發(fā)生缺頁(yè)中斷。

1）LRU2）FIFO3）OPT第七章文件及磁盤管理7.1文件系統(tǒng)基礎(chǔ)7.2文件系統(tǒng)實(shí)現(xiàn)（物理實(shí)現(xiàn)）

7.1文件系統(tǒng)基礎(chǔ)

什么是文件？什么是文件系統(tǒng)？

文件系統(tǒng)主要完成哪些功能？

7.1.1文件的概念

文件是以計(jì)算機(jī)硬盤為載體存儲(chǔ)在計(jì)算機(jī)上的信息集合，文件可以是文本文檔、圖片、程序等。

系統(tǒng)運(yùn)行時(shí)，計(jì)算機(jī)以進(jìn)程為基本單位進(jìn)行資源的調(diào)度和分配；在用戶進(jìn)行的輸入輸出中，則以文件為基本單位。

一、文件的組成

包含一塊存儲(chǔ)空間（其實(shí)是存儲(chǔ)空間中的數(shù)據(jù)）；

包含分類和檢索信息；

包含關(guān)于訪問(wèn)權(quán)限的信息。

例如：圖書館中的書。

一本書相當(dāng)于文件中的數(shù)據(jù)；

不同類別的書需要放在不同的書庫(kù)，再編號(hào)，相當(dāng)于分類索引；

部分昂貴的書目只給VIP讀者使用，相當(dāng)于訪問(wèn)權(quán)限。

二、文件的結(jié)構(gòu)（數(shù)據(jù)項(xiàng)、記錄和文件）

1.數(shù)據(jù)項(xiàng)

在文件系統(tǒng)中，數(shù)據(jù)項(xiàng)是最低級(jí)的數(shù)據(jù)組織形式，可把它分成以下兩種類型：

(1)基本數(shù)據(jù)項(xiàng)，用于描述一個(gè)對(duì)象的某種屬性的一個(gè)值，例如姓名、證件號(hào)碼、日期等。是數(shù)據(jù)中可命名的最小邏輯數(shù)據(jù)單位，即原子數(shù)據(jù)。

(2)組合數(shù)據(jù)項(xiàng)，由多個(gè)基本數(shù)據(jù)項(xiàng)組成。圖7-1文件、記錄和數(shù)據(jù)項(xiàng)之間的層次關(guān)系三、文件的屬性

1、名稱，唯一。

2、標(biāo)識(shí)符，文件系統(tǒng)內(nèi)標(biāo)識(shí)文件的唯一標(biāo)志，一般為數(shù)字。

3、類型，一般由不同的擴(kuò)展名表示。

4、位置。

5、大小。

6、保護(hù)，對(duì)文件進(jìn)行保護(hù)的訪問(wèn)控制信息。

7、時(shí)間、日期和用戶標(biāo)識(shí)，創(chuàng)建、上次修改、上次訪問(wèn)等信息。四、文件的打開(kāi)與關(guān)閉

大部分操作系統(tǒng)要求在文件使用之前就被顯示打開(kāi)。在open調(diào)用完成之后，操作系統(tǒng)對(duì)該文件的任何操作，都不在需要文件名，只需要open調(diào)用返回的指針。close之后，系統(tǒng)回收分配給該文件的內(nèi)存空間等資源，最后釋放文件控制塊。

每個(gè)打開(kāi)的文件都有如下信息：

1）文件指針，這個(gè)指針對(duì)打開(kāi)文件的某個(gè)進(jìn)程來(lái)說(shuō)是唯一的。

2）文件打開(kāi)計(jì)數(shù)，多個(gè)進(jìn)程共用一個(gè)文件時(shí)用。

3）文件磁盤位置，該信息直接存入內(nèi)存，避免每個(gè)文件操作都從磁盤讀取。

4）訪問(wèn)權(quán)限。

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

文件的邏輯結(jié)構(gòu)是從用戶觀點(diǎn)出發(fā)看到的文件組織形式，文件物理結(jié)構(gòu)是從實(shí)際觀點(diǎn)出發(fā),指文件在外存上的存儲(chǔ)組織形式。

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

將數(shù)據(jù)按順序組織成記錄并積累保存，是有序相關(guān)信息項(xiàng)的集合，以字節(jié)（Byte）為單位。訪問(wèn)只能通過(guò)窮舉搜索的方式，對(duì)大多數(shù)應(yīng)用都不適用。但是適合于采用字符流的無(wú)結(jié)構(gòu)方式，如源程序文件、目標(biāo)代碼文件等。

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

(1)順序文件，文件中的記錄一個(gè)接一個(gè)地順序排列，可以是定長(zhǎng)或變長(zhǎng)的，可以順序存儲(chǔ)，或鏈表形式存儲(chǔ)。包括:

串結(jié)構(gòu)：按時(shí)間先后順序。

順序結(jié)構(gòu)：按關(guān)鍵字先后順序。

(2)索引文件，為加快檢索速度，索引表本身是定長(zhǎng)記錄的順序文件。（見(jiàn)下圖）

(3)索引順序文件，上面兩種的結(jié)合。

(4)直接文件或散列文件（HashFile），給定記錄的鍵值或通過(guò)Hash函數(shù)轉(zhuǎn)換的鍵值直接決定記錄的物理地址。圖7-4具有單個(gè)和多個(gè)索引表的索引文件

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

目錄在用戶（應(yīng)用程序）所需要的文件名和文件之間提供一種映射。

(1)實(shí)現(xiàn)“按名存取”。

(2)提高對(duì)目錄的檢索速度。

(3)文件共享。

(4)允許文件重名。1、文件控制塊和索引結(jié)點(diǎn)

1）

文件控制塊FCB(Block)

用來(lái)存放控制文件需要的各種信息的數(shù)據(jù)結(jié)構(gòu)，以實(shí)現(xiàn)“按名存取”。

FCB的有序集合稱為文件目錄，一個(gè)FCB就是一個(gè)文件目錄項(xiàng)。

FCB包含：

文件基本信息；

存取控制信息；

使用信息。索引結(jié)點(diǎn)主要包括以下內(nèi)容：

(1)文件主標(biāo)識(shí)符，即擁有該文件的個(gè)人或小組的標(biāo)識(shí)符；

(2)文件類型，包括正規(guī)文件、目錄文件或特別文件；

(3)文件存取權(quán)限，指各類用戶對(duì)該文件的存取權(quán)限；

(4)文件物理地址，每一個(gè)索引結(jié)點(diǎn)中含有13個(gè)地址項(xiàng)，即iaddr(0)～iaddr(12)，它們以直接或間接方式給出數(shù)據(jù)文件所在盤塊的編號(hào)；

(5)文件長(zhǎng)度，指以字節(jié)為單位的文件長(zhǎng)度；

(6)文件連接計(jì)數(shù)，表明在本文件系統(tǒng)中所有指向該(文件的)文件名的指針計(jì)數(shù)；

(7)文件存取時(shí)間，指出本文件最近被進(jìn)程存取的時(shí)間、最近被修改的時(shí)間及索引結(jié)點(diǎn)最近被修改的時(shí)間。2、

文件目錄結(jié)構(gòu)

需要執(zhí)行的操作：搜索、創(chuàng)建文件、刪除文件、顯示目錄、修改目錄。

1）

單級(jí)文件目錄

這是最簡(jiǎn)單的文件目錄。在整個(gè)文件系統(tǒng)中只建立一張目錄表，每個(gè)文件占一個(gè)目錄項(xiàng)，目錄項(xiàng)中含文件名、文件擴(kuò)展名、文件長(zhǎng)度、文件類型、文件物理地址以及其它文件屬性。此外，為表明每個(gè)目錄項(xiàng)是否空閑，又設(shè)置了一個(gè)狀態(tài)位。單級(jí)文件目錄如圖7-9所示。

2）

兩級(jí)文件目錄

為了克服單級(jí)文件目錄所存在的缺點(diǎn)，可以為每一個(gè)用戶再建立一個(gè)單獨(dú)的用戶文件目錄UFD(User)。這些文件目錄具有相似的結(jié)構(gòu)，它由用戶所有文件的文件控制塊組成。此外，在系統(tǒng)中再建立一個(gè)主文件目錄MFD(Master)；在主文件目錄中，每個(gè)用戶目錄文件都占有一個(gè)目錄項(xiàng)，其目錄項(xiàng)中包括用戶名和指向該用戶目錄文件的指針。圖7-10兩級(jí)文件目錄3）多級(jí)目錄結(jié)構(gòu)（樹(shù)形結(jié)構(gòu)目錄)

在現(xiàn)代OS中，最通用且實(shí)用的文件目錄無(wú)疑是樹(shù)形結(jié)構(gòu)目錄。它可以明顯地提高對(duì)目錄的檢索速度和文件系統(tǒng)的性能。主目錄在這里被稱為根目錄，在每個(gè)文件目錄中，只能有一個(gè)根目錄，每個(gè)文件和每個(gè)目錄都只能有一個(gè)父目錄。把數(shù)據(jù)文件稱為樹(shù)葉，其它的目錄均作為樹(shù)的結(jié)點(diǎn)，或稱為子目錄。圖7-11示出了樹(shù)形結(jié)構(gòu)目錄。

在樹(shù)形結(jié)構(gòu)目錄中，從根目錄到任何數(shù)據(jù)文件都只有一條唯一的通路。在該路徑上，從樹(shù)的根(即主目錄)開(kāi)始，把全部目錄文件名與數(shù)據(jù)文件名依次地用“/”連接起來(lái)，即構(gòu)成該數(shù)據(jù)文件唯一的路徑名。圖7-11多級(jí)目錄結(jié)構(gòu)7.1.4文件共享

文件共享使多個(gè)用戶（進(jìn)程）共享同一份文件，文件共享的范圍已由單機(jī)系統(tǒng)發(fā)展到多機(jī)系統(tǒng)。

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

諸如文件的物理地址及其它的文件屬性等信息，不再是放在目錄項(xiàng)中，而是放在索引結(jié)點(diǎn)中。在文件目錄中只設(shè)置文件名及指向相應(yīng)索引結(jié)點(diǎn)的指針，如圖7-14所示。圖7-14基于索引結(jié)點(diǎn)的共享方式2、利用符號(hào)鏈接實(shí)現(xiàn)文件共享（軟鏈接）

允許一個(gè)文件或子目錄有多個(gè)父目錄，但其中僅有一個(gè)作為主(屬主)父目錄，其它的幾個(gè)父目錄都是通過(guò)符號(hào)鏈接方式與之相鏈接的(簡(jiǎn)稱鏈接父目錄)。圖7-16使用符號(hào)鏈接的目錄層次

7.1.5文件保護(hù)

文件訪問(wèn)類型：

讀；

寫；

執(zhí)行；

添加；

刪除；

列表清單；

重命名、復(fù)制、編輯等。

1、保護(hù)域

（1）訪問(wèn)權(quán)

（2）保護(hù)域

2、訪問(wèn)矩陣

（1）基本的訪問(wèn)矩陣

（2）具有域切換權(quán)的訪問(wèn)矩陣

3、訪問(wèn)矩陣的修改

（1）拷貝權(quán)

（2）所有權(quán)

（3）控制權(quán)

4、訪問(wèn)矩陣的實(shí)現(xiàn)7.2文件系統(tǒng)的實(shí)現(xiàn)

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

1、常見(jiàn)現(xiàn)代OS的文件系統(tǒng)類型

（1）FAT（2）NTFS（3）CDFS（4）exFAT

（5）EXT（6）ZFS（7）JFS（8）UMFS2、層次結(jié)構(gòu)新建、打開(kāi)、讀寫、關(guān)閉等用戶接口文件目錄系統(tǒng)存取控制模塊邏輯文件系統(tǒng)與文件信息緩沖區(qū)物理文件系統(tǒng)輔助分配模塊設(shè)備管理模塊0級(jí)1級(jí)2級(jí)3級(jí)4級(jí)管理文件目錄表、讀寫狀態(tài)信息表等比較用戶訪問(wèn)要求和FCB中指示的訪問(wèn)控制權(quán)限將用戶要讀寫的邏輯記錄轉(zhuǎn)成文件邏輯結(jié)構(gòu)內(nèi)的相應(yīng)塊號(hào)將邏輯記錄所在的相對(duì)塊號(hào)轉(zhuǎn)成實(shí)際的物理地址分配設(shè)備、分配讀寫緩沖區(qū)、磁盤調(diào)度、啟動(dòng)磁盤、處理中斷等二、文件實(shí)現(xiàn)

研究文件的物理結(jié)構(gòu)，即文件數(shù)據(jù)在物理存儲(chǔ)設(shè)備上是如何分布及組織的。

1、文件分配方式

（1）連續(xù)分配方式

要求為每一個(gè)文件分配一組相鄰接的盤塊。見(jiàn)251頁(yè)圖8-1

優(yōu)點(diǎn)：訪問(wèn)容易，訪問(wèn)快

缺點(diǎn)：外部碎片多；事先要知道文件長(zhǎng)度；

插入、刪除記錄不方便；

很難支持動(dòng)態(tài)增長(zhǎng)問(wèn)題。（2）鏈接組織方式

1）隱式鏈接

每個(gè)目錄項(xiàng)中都含有指向鏈接文件第一個(gè)盤塊和最后一個(gè)盤塊的指針。每個(gè)盤塊都記錄下一個(gè)盤塊。

優(yōu)點(diǎn)：離散，消除外部碎片

缺點(diǎn)：只適合順序訪問(wèn)，對(duì)隨機(jī)訪問(wèn)效率低。

2）顯示鏈接*教材253頁(yè)

把用于鏈接文件各物理塊的指針顯示存放在內(nèi)存的一張鏈接表中。

表中存儲(chǔ)所有物理塊及該塊指向同文件中下一塊的指針。

文件控制塊FCB中存文件首的塊號(hào)。

該表稱為文件分配表FAT（Table）（3）索引組織方式

鏈接組織方式缺點(diǎn)：

不支持高效的直接存?。?/p>

FAT本身需占用較大內(nèi)存。

索引方式：

1）單級(jí)索引方式教材257頁(yè)

為每個(gè)文件分配一個(gè)索引塊（表），把分配給該文件的所有盤塊號(hào)都記錄在索引塊號(hào)中。建立文件時(shí)，只須在為之建立的目錄項(xiàng)中填上指向該索引塊的指針。

2）多級(jí)索引組織方式教材258頁(yè)

3）增量式索引組織方式（混合組織方式）

a）對(duì)小文件，盤塊地址最好直接放入FCB中，即直接尋址；

b）對(duì)中型文件，采用單級(jí)索引，即一次間址；

c）大型、特大型文件，采用二級(jí)、三級(jí)索引，即二次、三次間址。

UNIX采用該方式。

（4）補(bǔ)充：顯示鏈接組織方式

1)FAT技術(shù)

每個(gè)邏輯磁盤是一個(gè)卷，每個(gè)卷專門劃出一個(gè)單獨(dú)區(qū)域來(lái)存放自己的目錄和FAT表。

a）FAT12

12位表項(xiàng)212個(gè)表項(xiàng)一塊512字節(jié)512*212=2MB

如果四個(gè)邏輯分區(qū)，最大支持8MB。

b）引入簇

簇（cluster）：相鄰的一組扇區(qū)，一般2n個(gè)塊

設(shè)一簇8塊時(shí)，最大支持8*8=64MB

c）FAT16

16位表項(xiàng)216個(gè)表項(xiàng)1簇128K時(shí)

216

*128K=8G浪費(fèi)仍舊很大。d）FAT32

FAT32比FAT16存儲(chǔ)利用率提高15%

缺點(diǎn)：FAT32不支持小于512M的分區(qū)；

單個(gè)文件長(zhǎng)度不能大于4G；

不能向下兼容。

2）NTFS

a）使用64位磁盤地址

b）支持長(zhǎng)文件名

c）一定容錯(cuò)能力

d）數(shù)據(jù)一致性保證

e）提供文件加密、文件壓縮功能

以簇為分配、回收單位2、文件存儲(chǔ)空間管理

（1）空閑表法

（2）空閑鏈表法

（3）位示圖法

（4）成組鏈接法練習(xí)：

1、設(shè)當(dāng)前工作目錄的主要目的是（C）。（2010聯(lián)考真題）

A、節(jié)省外存空間B、節(jié)省內(nèi)存空間C、加快文件的檢索速度

D、加快文件的讀/寫速度

2、文件系統(tǒng)中，文件訪問(wèn)控制信息存儲(chǔ)的合理位置是（A）。（2009聯(lián)考真題）

A、文件控制塊B、文件分配表C、用戶口令卡D、系統(tǒng)注冊(cè)表

3、若一個(gè)用戶進(jìn)程通過(guò)read系統(tǒng)調(diào)用讀取一個(gè)磁盤文件中的數(shù)據(jù)，則下列關(guān)于此過(guò)程的敘述中，正確的是（A）。（2012聯(lián)考真題）

I若該文件的數(shù)據(jù)不在內(nèi)存，則該進(jìn)程進(jìn)入睡眠等待狀態(tài)。

II請(qǐng)求read系統(tǒng)調(diào)用會(huì)導(dǎo)致CPU從用戶態(tài)切換到核心態(tài)

IIIread系統(tǒng)調(diào)用的參數(shù)應(yīng)包含文件的名稱

A、僅I、IIB僅I、IIIC、僅II、IIID、I、II和III4、用戶在刪除某文件的過(guò)程中，操作系統(tǒng)不可能執(zhí)行的操作是（A）。（2013年聯(lián)考真題）

A、刪除此文件所在的目錄B、刪除與此文件關(guān)聯(lián)的目錄項(xiàng)

C、刪除與此文件對(duì)應(yīng)的文件控制塊D、釋放與此文件關(guān)聯(lián)的內(nèi)存緩沖區(qū)

5、設(shè)文件F1的當(dāng)前引用計(jì)數(shù)值為1，先建立文件F1的符號(hào)鏈接（軟鏈接）文件F2，再建立文件F1的硬鏈接文件F3，然后刪除文件F1。此時(shí)，文件F2和文件F3的引用計(jì)數(shù)值分別是（B）。（2009聯(lián)考真題）

A、0、1B、1、1C、1、2D、2、1

6、在一個(gè)文件被用戶進(jìn)程首次打開(kāi)的過(guò)程中，操作系統(tǒng)需做的是（B）。（2014年聯(lián)考真題）

A、將文件內(nèi)容讀到內(nèi)存中B、將文件控制塊讀到內(nèi)存中

C、修改文件控制塊中的讀寫權(quán)限D(zhuǎn)、將文件的數(shù)據(jù)緩沖區(qū)首指針?lè)祷亟o用戶進(jìn)程

7、下列文件物理結(jié)構(gòu)中，適合隨機(jī)訪問(wèn)且易于文件擴(kuò)展的是（B）。（2009聯(lián)考真題）

A、連續(xù)結(jié)構(gòu)B、索引結(jié)構(gòu)

C、鏈?zhǔn)浇Y(jié)構(gòu)且磁盤快定長(zhǎng)D、鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊變長(zhǎng)

8、設(shè)文件索引結(jié)點(diǎn)中有7個(gè)地址項(xiàng)，其中4個(gè)地址項(xiàng)是直接地址索引，2個(gè)地址項(xiàng)是一級(jí)間接地址索引，1個(gè)地址項(xiàng)是二級(jí)間接地址索引，每個(gè)地址項(xiàng)大小為4B，若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256B，則可表示的單個(gè)文件最大長(zhǎng)度是（C）。（2010聯(lián)考真題）

A、33KBB、519KBC、1057KBD、16516KB

9、為支持CD-ROM中視頻文件的快速隨機(jī)播放，播放性能最好的文件數(shù)據(jù)塊組織方式是（A）。（2013聯(lián)考真題）

A、連續(xù)結(jié)構(gòu)B、鏈?zhǔn)浇Y(jié)構(gòu)C、直接索引結(jié)構(gòu)D、多級(jí)索引結(jié)構(gòu)10、若某文件系統(tǒng)索引節(jié)點(diǎn)（inode）中有直接地址項(xiàng)和間接地址項(xiàng)，則下列選項(xiàng)中，與單個(gè)文件長(zhǎng)度無(wú)關(guān)的因素是（A）。（2013聯(lián)考真題）

A、索引節(jié)點(diǎn)的總數(shù)B、間接地址索引的級(jí)數(shù)

C、地址項(xiàng)的個(gè)數(shù)D、文件塊的大小

強(qiáng)化練習(xí)：

1、（2011聯(lián)考真題）某文件系統(tǒng)為一級(jí)目錄結(jié)構(gòu)，文件的數(shù)據(jù)一次性寫入磁盤，已寫入的文件不可修改，但可多次創(chuàng)建新文件。請(qǐng)回答如下問(wèn)題：