山東農(nóng)業(yè)大學(xué)計算機(jī)系第6章文件管理

第6章文件管理

□6.1文件和文件系統(tǒng)

文件系統(tǒng)的,□6.2文件的邏輯結(jié)構(gòu),

功能就是提-□6-3外存分配方式-

供高效、快=□6.4目錄管理=

速和方便的5口6.5文件存儲空間的管理

文件存儲和」□6.6文件共享與保護(hù)Z

訪問功能。三□6.7數(shù)據(jù)一致性控制工

「□6.8本章要點(diǎn)與課堂練習(xí)

山東農(nóng)業(yè)上學(xué)計算機(jī)系

2011-6-211

6?1文件和文件系統(tǒng)

6.1.1文件、記錄和數(shù)據(jù)項

6.1.2文件類型和文件系統(tǒng)模型

6.1.3文件操作

山東農(nóng)業(yè)上學(xué)計算機(jī)系2

2011-6-21

6，」文件、記錄和婺據(jù)項

口文件：是指具有文件名的若干相關(guān)

二元素的集合。

□基于文件系統(tǒng)的概念，可以把數(shù)據(jù)

組成分為數(shù)據(jù)項、記錄和文件三級。

編號：01.......i.......

記錄記錄.....記錄........記錄

3

2011-6-21T,讀寫指針

1.數(shù)據(jù)項

□數(shù)據(jù)項是最低的數(shù)據(jù)組織形式。可分為兩

種類型：

1）基本數(shù)據(jù)項。是數(shù)據(jù)組織中可以命名的最

小邏輯數(shù)據(jù)單位，即原子數(shù)據(jù)，又稱為數(shù)

據(jù)元素或字段。其命名往往與其屬性一致。

2）組合數(shù)據(jù)項。由若干個基本數(shù)據(jù)項組成，

簡稱組項。

□基本數(shù)據(jù)項除數(shù)據(jù)名外，還應(yīng)有數(shù)據(jù)類型。

山東農(nóng)業(yè)上學(xué)計算機(jī)系4

2011-6-21

2.記錄

□記錄是一組相關(guān)數(shù)據(jù)項的集合，用于描述一

個對象在某方面的屬性。一個記錄應(yīng)包含哪

些數(shù)據(jù)項，取決于需要描述對象的哪個方面。

□在諸多記錄中，為能唯一的標(biāo)識一個記錄，

必須在一個記錄的各個數(shù)據(jù)項中，確定出一

個或幾個數(shù)據(jù)項，把它們的集合稱為關(guān)鍵字。

也即說關(guān)鍵字是唯一能標(biāo)識一個記錄的數(shù)據(jù)

項。

山東農(nóng)業(yè)上學(xué)計算機(jī)系5

2011-6-21

3.文件

口文件是指由創(chuàng)建者所定義的、具有文件名的

一組相關(guān)元素的集合，可分為有結(jié)構(gòu)文件和

無結(jié)構(gòu)文件兩種。

□有結(jié)構(gòu)文件中文件由若干個記錄構(gòu)成；無結(jié)

構(gòu)文件則被看作是一字符流。

□文件必須要有文件名和屬性。屬性可以包括

文件類型、文件長度、文件的物理位置和文

件的建立時間。

山東農(nóng)業(yè)上學(xué)計算機(jī)系6

2011-6-21

關(guān)于文件屬性_

口文件類型：可以從不同的角度來規(guī)定文件的

類型。如源文件、目標(biāo)文件及可執(zhí)行文件。

□文件長度：指文件的當(dāng)前長度，長度的單位

可以是字節(jié)、字或塊，也可能是最大允許的

長度。

□文件的物理位置：通常是用于指示文件在哪

一個設(shè)備上及在該設(shè)備的哪一個位置的指針。

□文件的存取控制：讀、讀/寫、執(zhí)行

口文件的建立時間、修改時間、訪問時間等。

山東農(nóng)業(yè)上學(xué)計算機(jī)系7

文件、記錄和數(shù)據(jù)賬間的關(guān)系

-文件-

記錄工記錄2記錄n

數(shù)據(jù)項1數(shù)據(jù)項2數(shù)據(jù)項n

)I________)I___

山東農(nóng)業(yè)上學(xué)計算機(jī)系8

2011-6-21

6.1.2文件類型和文件系統(tǒng)模型

件類

文

件

分為

文件

解

展名

擴(kuò)

件系

文

底

最

層

操

行

縱

提

統(tǒng)

供

文件系統(tǒng)模型

山東農(nóng)業(yè)上學(xué)計算機(jī)系9

2011-6-21

文件類型

□按用途分類：系統(tǒng)文件、用戶文件和庫文件。

□按文件中數(shù)據(jù)的形式分類：源文件、目標(biāo)文

件和可執(zhí)行文件。

□按存取控制屬性分類：只執(zhí)行文件、只讀文

件和讀寫文件。

□按文件的邏輯結(jié)構(gòu)分類：有結(jié)構(gòu)文件（記錄

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

□按文件的物理結(jié)構(gòu)分類：順序文件、鏈接文

件、索引文件

山東農(nóng)業(yè)上學(xué)計算機(jī)系10

2011-6-21

UNIX文件分類

■普通文件

□內(nèi)容可以是程序、數(shù)據(jù)、圖象等，保存在磁

盤塊中

■目錄文件

5□（文件名，文件號）序列，保存在磁盤塊中［

■特殊文件匚

三口設(shè)備z

■設(shè)備作為文件管理

山東農(nóng)業(yè)上學(xué)計算機(jī)系11

2011-6-21

文件系統(tǒng)_

;文件系統(tǒng)是操作系統(tǒng)中負(fù)責(zé)管理和存取文件信息的軟件

機(jī)構(gòu)，它是由管理文件所需的數(shù)據(jù)結(jié)構(gòu)和相應(yīng)的管理軟

件以及訪問文件的一組操作組成。W

二從系統(tǒng)的角度看：文件系統(tǒng)是一個負(fù)責(zé)文件存儲空間管

理的機(jī)構(gòu)。二

二從用戶的角度看：文件系統(tǒng)是用戶在計算機(jī)上存儲信息

、使用信息的接口。

山東農(nóng)業(yè)上學(xué)計算機(jī)系12

2011-6-21

文件系統(tǒng)功能

□用戶角度：實(shí)現(xiàn)“按名存取”

口系統(tǒng)角度：是對文件存儲器的存儲空

二間進(jìn)行組織、分配、負(fù)責(zé)文件的存儲

=并對存入的文件實(shí)施保護(hù)、檢索的一

組軟件的集合。

山東農(nóng)業(yè)上學(xué)計算機(jī)系13

2011-6-21

文件系統(tǒng)

口通用文件系統(tǒng)應(yīng)具有以下功能：

-工）提供用戶對文件操作的命令；二

三2）提供用戶共享文件的機(jī)制；三

=3）管理文件的存儲介質(zhì)；

4）提供文件的存取控制的機(jī)制，保障文件及文件系統(tǒng)

的安全性；

:5）提供文件及文件系統(tǒng)的備份和恢復(fù)功能；二

6）提供對文件的加密和解密功能。

山東農(nóng)業(yè)上學(xué)計算機(jī)系14

2011-6-21

文件系統(tǒng)模型

用戶（程序）

山東農(nóng)業(yè)上學(xué)計算機(jī)系15

2011-6-21

文件系統(tǒng)模型

口對象及其屬性。文件管理系統(tǒng)的對象有：文件、

目錄和磁盤存儲空間。

□操縱和管理軟件。是文件管理的核心部分。實(shí)現(xiàn)

了文件系統(tǒng)的大部分功能——對文件存儲空間的

管理、對文件目錄的管理、文件的地址轉(zhuǎn)換機(jī)制、

對文件讀寫管理以及對文件的共享和保護(hù)。

□文件系統(tǒng)的接口。命令接口（用戶與文件系統(tǒng)）

和程序接口（用戶程序和文件系統(tǒng)）。

山東農(nóng)業(yè)上學(xué)計算機(jī)系16

2011-6-21

6?1?3文件操作

口用戶通過文件系統(tǒng)所提供的系統(tǒng)調(diào)用實(shí)施對

文件的操作。最基本的文件操作有：創(chuàng)建文

件、刪除文件、讀文件、寫文件、截斷文件

和設(shè)置文件的讀/寫位置。

口但對于一個實(shí)際的OS,為了方便用戶使用

文件而提供了更多地對文件的操作，如打開

和關(guān)閉一個文件及改變文件名等操作。

山東農(nóng)業(yè)上學(xué)計算機(jī)系17

2011-6-21

對記錄的操作

工）檢索所有記錄

2）檢索單個記錄

3）插入一個記錄

4）修改一個記錄

5）刪除一個記錄

山東農(nóng)業(yè)上學(xué)計算機(jī)系18

2011-6-21

最基本的文件操作

□創(chuàng)建文件。創(chuàng)建新文件時先分配空間，然后建立記

錄文祥屬性的目臬項。

□刪除文件。找到要刪除文件的目錄項清空，回收存

儲空間。

□讀文件。找到文件目錄項，以確定文件在外存的位

置。用讀指針操作。

□寫文件。先查找目錄項，再利用寫指針操作。

□截斷文件。將無用文件長度置為0,有別于刪除文

件。

□設(shè)置文件的讀/寫位置。用于設(shè)置文件讀/寫指針

的位置，而不是每次都從文件始端讀寫。

山東農(nóng)業(yè)上學(xué)計算機(jī)系19

2011-6-21

文件的“打開”和閉”操作

口所謂“打開”，是指系統(tǒng)將指名文件的屬性從外存

拷貝到內(nèi)存打開文件表的一個表目中，并將該表目

的編號返回給用戶。以后當(dāng)用戶再要求對該文件操

作時，便可利用系統(tǒng)所返回的索引號向系統(tǒng)提出操

作請求。此時可直接利用索引號到打開文件表中查

找，避免了再次檢索。這樣不僅節(jié)省大量檢索開銷

而且顯著提高操作速度。

□當(dāng)用戶不再需要對該文件實(shí)施相應(yīng)的操作時，可利

用“關(guān)閉”此文件，OS將會把該文件從打開文件

表中的表目上刪除。

山東農(nóng)業(yè)上學(xué)計算機(jī)系20

2011-6-21

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

口6?2?工文件邏輯結(jié)構(gòu)的類型

□6.2.2順序文件

□6.2.3索引文件

□6.2.4索引順序文件

□6.2.5直接文件和哈希文件

山東農(nóng)業(yè)上學(xué)計算機(jī)系21

2011-6-21

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

可以用兩種不同的觀點(diǎn)去進(jìn)行研究文件結(jié)構(gòu)=

1.用戶觀點(diǎn)：

是研究用戶“思維”中的抽象文件，或稱邏輯文件，其研

究的側(cè)重點(diǎn)在于為用戶提供一種邏輯結(jié)構(gòu)清晰、使用簡

便的邏輯文件形式。用戶將按照這種形式去存儲、檢索

和加工有關(guān)文件中的信息。

2.實(shí)現(xiàn)觀點(diǎn)：

是研究駐留在設(shè)備“介質(zhì)”中的實(shí)際文件，或稱物理文件

O它研究的側(cè)重點(diǎn)是選擇一些工作性能良好、設(shè)備利用

率高的物理文件形式。系統(tǒng)將按照這種形式同外部設(shè)備

打交道并控制信息的傳輸

山東農(nóng)業(yè)上學(xué)計算機(jī)系22

2011-6-21

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

口通常文件是由一系列的記錄組成的。文件系統(tǒng)設(shè)計

的關(guān)鍵要素，是將這些記錄構(gòu)成一個文件的方法，

以及將一個文件存儲到外存上的方法。事實(shí)上任何

一個文件都存在著以下兩種形式的結(jié)構(gòu)：

1.文件的邏輯結(jié)構(gòu)。從用戶觀點(diǎn)出發(fā)所觀察到的文件

組織形式，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，

它獨(dú)立與文件的物理特性，又稱為文件組織。

2.文件的物理結(jié)構(gòu)。又稱為文件的存儲結(jié)構(gòu)，是指文

件在外存上的存儲組織形式。與存儲介質(zhì)的存儲性

能和采用的外存分配方式有關(guān)。

山東農(nóng)業(yè)上學(xué)計算機(jī)系23

2011-6-21

6?2.工文件邏輯結(jié)物類型

口可以分為兩大類

■有結(jié)構(gòu)文件，是指由一個以上的記錄構(gòu)成的文

件，故又把它稱為記錄式文件。

■無結(jié)構(gòu)文件，這是指由字符流構(gòu)成的文件，故

又稱為是流式文件。

山東農(nóng)業(yè)上學(xué)計算機(jī)系24

2011-6-21

有結(jié)構(gòu)文件

口根據(jù)記錄的長度可分為定長記錄文件和不

定長記錄文件。

1.定長記錄：文件中所有的記錄長度是相同

的。具有相同的數(shù)據(jù)項順序和長度。

2.變長紀(jì)錄：指文件中的各記錄長度不相同。

山東農(nóng)業(yè)上學(xué)計算機(jī)系25

2011-6-21

-----0------0

-m叫

-----m

,ID心｝陽

1

-----2m叫+1

'-----3m

山叫

1%)+抵1+2

■

1------imB

■金叫+1)

叫

?

1R｝叫］

1

高‘叫+1)

?

i——niti■

in*

兄J

(a)固定長度記錄(b)可變長度記錄

山東農(nóng)業(yè)上學(xué)計算機(jī)系26

2011-6-21

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

定長記錄文件的長度=記錄個數(shù)義記錄長度。

變長記錄文件的長度為各記錄長度之和。

例如：學(xué)生登記表文件xsdjb.dbf

姓名學(xué)號籍貫通信地址郵政編碼

李銘925678武昌武昌關(guān)山街125號430074

司馬樂925679北京北京海軍路88號100034

山東農(nóng)業(yè)上學(xué)計算機(jī)系27

2011-6-21

有結(jié)構(gòu)文件

□根據(jù)記錄的組織方式分為下列文件：

1.順序文件。由一系列記錄按某種順序排列

所形成的文件。通常是定長記錄。

2.索引文件。當(dāng)記錄可變長時，通常為之建

立一張索引表，并為每個記錄設(shè)置一個表

項以加快對記錄檢索的速度。

3.索引順序文件。上述兩種方式的結(jié)合。為

文件建立一張索引表，為每一組記錄中的

第一個記錄設(shè)置一個表項。

山東農(nóng)業(yè)上學(xué)計算機(jī)系28

2011-6-21

無結(jié)構(gòu)文件

口如果說大量的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫，是采用有

結(jié)構(gòu)的文件形式的話，則大量的源程序、可

執(zhí)行文件、庫函數(shù)等，所采用的就是無結(jié)構(gòu)

的文件形式，即流式文件。其長度以字節(jié)為

單位。對流式文件的訪問，則是采用讀寫指

針來指出下一個要訪問的字符。

□可以把流式文件看作是記錄文件的一個特例。

山東農(nóng)業(yè)上學(xué)計算機(jī)系29

2011-6-21

6.2.2順序文件

口邏輯記錄的排序一二

文件是記錄的集合。文件中的記錄可以是任

意順序的，因此，它可以按照各種不同的

順序進(jìn)行排列。一般可歸為以下兩種情況：

1-串結(jié)構(gòu)：各記錄之間的順序與關(guān)鍵字無關(guān)。

通常由時間來決定。

2.順序結(jié)構(gòu)：文件中的所有記錄按關(guān)鍵字排

歹U?？梢园搓P(guān)鍵字的長短或英文字母書須

排序。順序結(jié)構(gòu)的檢索效率更高。

山東農(nóng)業(yè)上學(xué)計算機(jī)系30

2011-6-21

6.2.2順序文件

口對順序文件的讀/寫操作

順序文件的記錄可以是定長的，也可以是變

長的。對于定長記錄的順序文件，如果已知

當(dāng)前記錄的邏輯地址，便很容易確定下一個

記錄的邏輯地址。

例如：讀：Rptr=Rptr+L

寫：Wptr=Wptr+L

山東農(nóng)業(yè)上學(xué)計算機(jī)系31

2011-6-21

6.2.2順序文件

口對順序文件的讀/寫操作

對于變長記錄的順序文件，在順序讀或?qū)憰r二

的情況相似，但應(yīng)分別為它們設(shè)置讀或?qū)懼?/p>

針，在每次讀或?qū)懲暌粋€記錄后，須將指針

加上（J是剛操作完的記錄的長度）。

山東農(nóng)業(yè)上學(xué)計算機(jī)系32

2011-6-21

0

⑺定長m錄文件⑶法記錄文件

6.2.2順序文件

口順序文件的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：順序文件的最佳應(yīng)用場合是在對諸記錄進(jìn)行批量存

取時，即每次操作一大批記錄。只有順序文件才能存

儲在磁帶上，并能有效的工作。

缺點(diǎn)：

i.在交互應(yīng)用的場合，如果進(jìn)程需要按關(guān)鍵字操作某個

記錄，順序文件的性能就可能很差。當(dāng)文件較大時更

差（平均查找N/2次）。

2.如想增加或刪除一個記錄都比較困難。

山東農(nóng)業(yè)上學(xué)計算機(jī)系34

2011-6-21

6-2.3索引文件

邏輯文件

山東農(nóng)業(yè)上學(xué)計算機(jī)系35

2011-6-21

索引文件的檢索

口在對索引文件進(jìn)行檢索時，首先是根據(jù)用戶（程序）

提供的關(guān)鍵字，并利用折半查找法去檢索索引表，

從中找出相應(yīng)的表項；再利用該表項中給出的指向

記錄的指針值，去訪問所需的記錄。而每當(dāng)要向索

引文件增加一個新記錄時就需對索引表進(jìn)行修改。

由于索引文件可有較快的檢索速度，故用于要求及

時性較高的場合。

□索引文件的主要問題是除了有主文件外，還需配備

一張索引表，而且每個記錄都要有一個索引項，因

此提高了存儲費(fèi)用。

山東農(nóng)業(yè)上學(xué)計算機(jī)系36

2011-6-21

6.2.4索引順序文件

(indexed-sequentialfile)

姓名其他屬性

鍵1嬰輯地址

AnQiAnQi

BaoRong\

ChenLin\AnKang

BaoRong

山東農(nóng)業(yè)上學(xué)計算機(jī)系37

2011-6-21順序文件

索引順序文件

口在順序文件(主文件mainfile)的基礎(chǔ)上，另

外建立索弓I(index)和溢出文件(oversowfile)。這

樣做的目的是加快順序文件的檢索速度。

□在索引文件中，可將關(guān)鍵字域中的取值劃分

若干個區(qū)間(如A~Z可以劃分為A到Z共26

個區(qū)間)，每個區(qū)間對應(yīng)一個索引項，后者

指向該區(qū)間的開頭記錄。新記錄暫時保存在

溢出文件中，定期歸并入主文件。

山東農(nóng)業(yè)上學(xué)計算機(jī)系38

2011-6-21

索引順序文件

□通過劃分層次，在記錄數(shù)量較大時，比順序

文件大大縮短檢索時間。

□順序文件是N/2（這時可使用折半查找），而

索引順序文件（一級索引）是i/2+N/（2*i）,

其中i為索引長度。

如：有1000,000條記錄的順序文件的平均檢索長度為

500,000,而在添加一個有1000條索引項的索引文件

后，平均檢索長度為1000。

□索引還可以是多級的。

山東農(nóng)業(yè)上學(xué)計算機(jī)系39

2011-6-21

6,2.5直接文件和哈希文件

□直接文件

采用前述幾種文件結(jié)構(gòu)對記錄進(jìn)行存取時，都

須利用給定的記錄鍵值，先對線性表進(jìn)行檢

索，以找到指定記錄的物理地址。然而對直

接文件，則可根據(jù)給定的記錄鍵值，直接獲

得指定記錄的物理地址。換言之，記錄鍵值

本身就決定了記錄的物理地址，組織直接文

件的關(guān)鍵，在于用什么方法進(jìn)行從記錄值到

物理地址的轉(zhuǎn)換。

山東農(nóng)業(yè)上學(xué)計算機(jī)系40

2011-6-21

6?2?5直接文件和哈產(chǎn)文件

口哈希（Hash）文件

這是目前應(yīng)用最為廣泛的一種直接文件。它

利用Hash函數(shù)（或稱為散列函數(shù)），可將

記錄鍵值轉(zhuǎn)換為相應(yīng)記錄的地址。但為了能

實(shí)現(xiàn)文件存儲空間的動態(tài)分配，通常由

Hash函數(shù)所求得的并非是相應(yīng)記錄的地址,

而是指向一目錄表相應(yīng)表目的指針，該表目

網(wǎng)內(nèi)容指向相應(yīng)記錄所在的物理塊，如下圖

ZjSO

山東農(nóng)業(yè)上學(xué)計算機(jī)系41

2011-6-21

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

口若令K為記錄鍵值，用目錄表

A作為通過Hash函數(shù)------

轉(zhuǎn)換所形成的該記錄------

在目錄表中對應(yīng)表目Hash函數(shù)一?

的位置，則有關(guān)系------

A=H(K)O通常把----<.—

Hash函數(shù)作為標(biāo)準(zhǔn)函鍵值

數(shù)存于系統(tǒng)中，供存

取文件時調(diào)用。

山東農(nóng)業(yè)上學(xué)計算機(jī)系42

2011-6-21

文件的物理結(jié)構(gòu)

文件的物理結(jié)構(gòu)指文件在存儲介質(zhì)上的存儲方式。

三種基本結(jié)構(gòu)：

工.連續(xù)文件結(jié)構(gòu)匚

2.鏈接文件結(jié)構(gòu)；

3.索引文件結(jié)構(gòu)

山東農(nóng)業(yè)上學(xué)計算機(jī)系43

2011-6-21

6.3外存分配方式

文件的物理結(jié)構(gòu)和外存分配方法有關(guān)。在

采用不同的分配方式時將形成不同的文件

物理結(jié)構(gòu)。

連續(xù)分配方式-順序式結(jié)構(gòu)

鏈接分配方式一鏈接式結(jié)構(gòu)

索引分配方式-索引式結(jié)構(gòu)

山東農(nóng)業(yè)上學(xué)計算機(jī)系44

2011-6-21

6.3外存分配方式

6.3.1連續(xù)分配

6.3.2鏈接分配

6.3.3索引分配

山東農(nóng)業(yè)上學(xué)計算機(jī)系45

2011-6-21

6.3.1連續(xù)分配

directory

filestartlength

count02

o口1口2口3口

tr143

mail196

4口5口6口7口list284

f62

8口9口1O口11口

tr

12口13口〔4口15口

16口"口[8口19口

mail

2O||21□22||23||

24口25口26口27□

list

28□29口30[~~131□

山東農(nóng)業(yè)上學(xué)計算機(jī)系46

20II-6-21

連續(xù)分配：一個文件占有若干連續(xù)的磁盤塊。

磁盤空間

優(yōu)點(diǎn)：速度快，節(jié)省空間。

缺點(diǎn)：長度變化困難。

塊18

塊19

首塊=18

塊數(shù)=5塊20

塊21

塊22

FCB

山東農(nóng)業(yè)上學(xué)計算機(jī)系

2011-6-21

6.3.1連續(xù)分配

C[連續(xù)文件

二不蓮線文件是由一組分配在窿盤連續(xù)區(qū)域的物理塊組成的,

E

物理塊

匚

102103104105106

C

C

文件說明信息/

aa??■100優(yōu)點(diǎn)：結(jié)構(gòu)簡單，實(shí)現(xiàn)容易.

缺點(diǎn)：不利于文件動態(tài)擴(kuò)充；

bb???104

■■■空間利用不充分；創(chuàng)建文件時

要求給出文件大小，用戶不方

便.

6.3?2鏈接分配

口采用鏈接分配方式時，可通過在每個盤塊

上的鏈接指針，將同屬于一個文件的多個

離散的盤塊鏈接成一個鏈表，把這樣形成

的文件稱為鏈接文件。

□鏈接方式又可分為隱式鏈接和顯式鏈接兩

種形式。

山東農(nóng)業(yè)上學(xué)計算機(jī)系49

2011-6-21

隱式鏈接

每個文件是一個磁盤塊的鏈接列表:

塊可以分散在磁盤各處。

山東農(nóng)業(yè)上學(xué)計算機(jī)系50

2011-6-21

山東農(nóng)業(yè)上學(xué)計算機(jī)系51

2011-6-21

隱式鏈接

directory

filestartend

925

。口2口3口jeep

4口7口

8口11口

1215口

16F~I17|I18||19||

201|2122口23口

24||2526口27口

281|291|30||31□

52

20II-6-21山東農(nóng)業(yè)上學(xué)必算機(jī)系

隱式鏈接

評價：_

L存儲空間利用率高；

2.文件創(chuàng)建時用戶不必指出文件的大??；二

3.文件動態(tài)擴(kuò)充和修改容易。

4.順序存取效率高，隨機(jī)存取效率太低，如果訪

問文件的最后的內(nèi)容，實(shí)際上是要訪問整個文

件。

山東農(nóng)業(yè)上學(xué)計算機(jī)系53

2011-6-21

顯式鏈接

?為了克服隱式鏈接文件的存取效率太低

的問題，人們提出顯式鏈接的技術(shù),即

把串聯(lián)文件中的鏈接字集中在一結(jié)構(gòu)中,

二這樣既保持了鏈接文件的優(yōu)點(diǎn)，也克服

DOS、WINDOWS系統(tǒng)就采用了

這樣結(jié)構(gòu)。

山東農(nóng)業(yè)上學(xué)計算機(jī)系54

2011-6-21

顯式鏈接

FAT：文件分配表，磁盤

格式化后建立，從磁盤的

第二個扇區(qū)開始，有兩個

相同的FAT。

磁盤的類型：

FDF,雙面，F(xiàn)CH,單面

（9扇區(qū)/磁道）

F8H,硬盤

000H：空閑簇

FFFH：文件的結(jié)尾簇

XXXH：文件的下一簇

家亞上學(xué)計算機(jī)系55

2011-6-21

鏈?zhǔn)椒峙涞膬?yōu)點(diǎn)

口離散分配方式

□消除了外部碎片

□提高了外存空間利用率

□便于文件動態(tài)增長

□方便文件的增、冊h改

山東農(nóng)業(yè)上學(xué)計算機(jī)系56

2011-6-21

鏈?zhǔn)椒峙涞娜秉c(diǎn)

口鏈接分配方式雖然解決了連續(xù)分配方式所

存在的問題，但又出現(xiàn)了另外兩個問題：

口不能支持高效的直接存取。要對一個文件

進(jìn)行直接存取，需首先在FAT中順序的查

找許多盤塊號。

口FAT需占用較大的內(nèi)存空間。當(dāng)磁盤容量

較大時，F(xiàn)AT可能要占用數(shù)MB以上的內(nèi)存

空間。這是令人難以忍受的。

山東農(nóng)業(yè)上學(xué)計算機(jī)系57

2011-6-21

索引分配

單

級

索

引

方

式

28口29口30口31口

山東農(nóng)業(yè)上學(xué)計算機(jī)系58

2011-6-21

索引分配方式示意圖

口索引文件結(jié)構(gòu)三文件說明皆息

這種文件的數(shù)據(jù)結(jié)構(gòu)是

文件的索引表，每個文

件有一個索引表，表中

每個表目包括：邏輯塊

號，物理塊號。

口索引表位置：文件目錄

中，文件的開頭等。

口索引表大?。汗潭ù笮?

非固定大小。

山東農(nóng)業(yè)上學(xué)計算機(jī)系59

2011-6-21

索引分配方式的問題

□每個文件一個索弓I塊

□不利于小文件（常采用鏈?zhǔn)剑?/p>

山東農(nóng)業(yè)上學(xué)計算機(jī)系60

2011-6-21

多級索引方式

outer-index

夕卜部索弓I

indextable

索引表文件

山東農(nóng)業(yè)上學(xué)計算機(jī)系61

2011-6-21

多級索引方式

?UNIX系統(tǒng)采用多級間接索引結(jié)構(gòu)

?小型文件采用直接索引

?大型文件采用間接索引

山東農(nóng)業(yè)上學(xué)計算機(jī)系62

2011-6-21

工給點(diǎn)文件數(shù):據(jù)塊

addr[fl]

addi[1]

J一次索引塊

二次索引塊

addr[s]

addr[10]

iddr[11]

二次索引塊

4ddr[12]

■

三次索引抉

UNIX文件系統(tǒng)的多級間接嗦引結(jié)構(gòu)

3888物理燒

空56物厚塊

刁83------］紅2物理城

4$￥q206—

3972——

2456

89斐81物理塊

7656|43叫—

-——

文件I節(jié)點(diǎn)■

混合分配方式

口直接地址

□一次間接地址

□多次間接地址

山東農(nóng)業(yè)上學(xué)計算機(jī)系65

2011-6-21

聯(lián)合策略：UNIX（每個塊4K字節(jié)）

mode

owners(2)

timestamps(3)

sizeblock

count

directblocks

singleindirect

doubleindirect

tripleindirect"1data

*

Jdata

山東農(nóng)業(yè)上學(xué)計算機(jī)系66

2011-6-21

文件類型與文件存儲器、存取方法

的關(guān)系

存取磁舟磁帶

設(shè)備

—

文件連續(xù)串聯(lián)索引Hssh連續(xù)

類型文件文件文件文件文件

文件固定固定、固定、固定、固定

長度可變可變可變

存

取直接、順序直接、直接、順序

方法

順序順序順序

山東農(nóng)業(yè)上學(xué)計算機(jī)系

2011-6-21

文件物理結(jié)構(gòu)的比較

連續(xù)文件

優(yōu)點(diǎn)：

不冠要額外的空間開銷；

在文件目錄中指出文件的大小和首塊的塊號;

適應(yīng)于順序存取。

缺點(diǎn)：

動袤地增長和縮小系統(tǒng)開銷很大；，

文件創(chuàng)建時要求用戶提供文件的大小；

存儲空間浪費(fèi)較大。

山東農(nóng)業(yè)上學(xué)計算機(jī)系68

2011-6-21

文件物理結(jié)構(gòu)的比較

串聯(lián)文件

優(yōu)點(diǎn)：

空間利用率高；

便于動態(tài)增長；

適應(yīng)于順序訪問的文件。

缺點(diǎn)：

不便于隨即訪問。

山東農(nóng)業(yè)上學(xué)計算機(jī)系69

2011-6-21

士件物理結(jié)構(gòu)的比較3

索引文彳牛

優(yōu)點(diǎn)：二

既適應(yīng)于順序訪問，也適應(yīng)于隨機(jī)訪問。=

UNIX系統(tǒng)是使用索引結(jié)構(gòu)成功的例子。二

缺點(diǎn)：

需要用于索引表的空間開銷和文件索引的時

間開銷。

山東農(nóng)業(yè)上學(xué)計算機(jī)系70

2011-6-21

6.4目錄管理

?:?目錄是由文件說明索引組成的用于文件檢索

的特殊文件。

?:?文件目錄的內(nèi)容主要是文件訪問的控制信息

（不包括文件內(nèi)容）。

?:?它是一張記錄所有文件名及其存放地址、文

件的說明和控制信息的表格。

?:?每個文件有一個文件的目錄項。

山東農(nóng)業(yè)上學(xué)計算機(jī)系71

2011-6-21

文件目錄項:

文件目錄項是文件屬性信息(properties),

其中的一部分是用戶可獲取的。

1.文件名4.存取控制信息

2.文件的大小，單位：字節(jié)文件主和其它用戶對該文件的訪

3.文件在物理存儲介質(zhì)中的位置。問權(quán)限。

取決于文件的物理結(jié)構(gòu)。5.管理信息

對于連續(xù)文件：文件起始塊號(包含文件創(chuàng)建的日期和時間，最

即文件的第一個物理塊塊號)；近修改該文件的日期和時間等。

對于串聯(lián)文件：指向第一個物理6.文件的類型

塊的指針；

對于索引文件：索引表。

山東農(nóng)業(yè)上學(xué)計算機(jī)系72

2011-6-21

文件目錄項:

L基本信息

□文件名：字符串，通常在不同系統(tǒng)中允許不同的

最大長度。可以修改。有些系統(tǒng)允許同一個文件

有多個別名（alias，；

口文件類型：可有多種不同的劃分方法，如：

■有無結(jié)構(gòu)（記錄文件，流式文件）

■內(nèi)容（二進(jìn)制，文本）

■用途（源代碼，目標(biāo)代碼，可執(zhí)行文件，數(shù)據(jù)）

■屬性attribute（如系統(tǒng),隱含等）

■文件組織（如順序，索引等）

2011-6-21山東農(nóng)業(yè)大售計嘉機(jī)系TT-

文件目錄項:

2.地址信息

口存放位置：包括哪個設(shè)備或文件卷

volume.以及客個存儲及位置；

口文件長度（當(dāng)前和上限）：以字節(jié)、字或

存儲塊為單位?？梢酝ㄟ^寫入或創(chuàng)建、打

開、關(guān)閉等操作而變化。

山東農(nóng)業(yè)上學(xué)計算機(jī)系74

2011-6-21

文件目錄項:

3.訪問控制信息

□文件所有者（屬主）：通常是創(chuàng)建文件

的用戶，或者改變已有文件的屬主；

□訪問權(quán)限（控制各用戶可使用的訪問方

式）：如讀、寫、執(zhí)行、刪除等；

山東農(nóng)業(yè)上學(xué)計算機(jī)系75

2011-6-21

文件目錄項:

4.使用信息

□創(chuàng)建時間

□最后一次讀訪問的時間和用戶

□最后一次寫訪問的時間和用戶

山東農(nóng)業(yè)上學(xué)計算機(jī)系76

2011-6-21

目錄管理的要求

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

2.提高對目錄的檢索速度。

3.文件共享。

4,允許文件重名。

山東農(nóng)業(yè)上學(xué)計算機(jī)系77

2011-6-21

6?4目錄管理

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

□6.4.2目錄結(jié)構(gòu)

□6.4.3目錄查詢技術(shù)

山東農(nóng)業(yè)上學(xué)計算機(jī)系78

2011-6-21

6?4.1文件控制塊和夢引結(jié)點(diǎn)

口“文件控制塊（FCB）”

□文件與文件控制塊一一對應(yīng)

口文件目錄：文件控制塊的有序集合

□目錄文件

山東農(nóng)業(yè)上學(xué)計算機(jī)系79

2011-6-21

文件控制塊

1.基本信息類。包括文件名，文件物理位置，

文件邏輯結(jié)構(gòu)，文件的物理結(jié)構(gòu)。

2.存取控制信息類。包括文件主的存取權(quán)限，

核準(zhǔn)用戶的存取權(quán)限和一般用戶的存取權(quán)限。

3,使用信息類。包括文件的建立日期和時間、

文件上次修改的日期和時間及當(dāng)前使用信息。

山東農(nóng)業(yè)上學(xué)計算機(jī)系80

2011-6-21

MS-DOS的文件控制塊

文擴(kuò)屬備時日第盤

件展塊L-h

名名性用間期塊數(shù)

號

山東農(nóng)業(yè)上學(xué)計算機(jī)系81

2011-6-21

索引結(jié)點(diǎn)

□索引結(jié)點(diǎn)的引入■便于快速檢索文件目錄!

文件名索引結(jié)點(diǎn)編號

文件名1nl

文件名2-n2

■■

■■

■■

UNIX的文件目錄

山東農(nóng)業(yè)上學(xué)計算機(jī)系82

2011-6-21

磁盤索引結(jié)點(diǎn)

口這是存放在磁盤上的索引結(jié)點(diǎn)。每個文件有唯一的

一個磁盤索引結(jié)點(diǎn)，主要包括以下內(nèi)容：

1.文件主標(biāo)識符。

2.文件類型。

3.文件存取權(quán)限。

4.文件物理地址。

5.文件長度。

6.文件連接計數(shù)。

7.文件存取時間。

山東農(nóng)業(yè)上學(xué)計算機(jī)系83

2011-6-21

內(nèi)存索引結(jié)點(diǎn)_____________

口這是放在內(nèi)存中的索引結(jié)點(diǎn)。當(dāng)文件被打開后,

將磁盤索引結(jié)點(diǎn)拷貝到內(nèi)存索引結(jié)點(diǎn)中。比磁

盤索引結(jié)點(diǎn)又增加了以下內(nèi)容：

!■索引結(jié)點(diǎn)編號。

2.狀態(tài)。

3.訪問計數(shù)。

4.文件所屬文件系統(tǒng)的邏輯設(shè)備號。

5.鏈接指針。

山東農(nóng)業(yè)上學(xué)計算機(jī)系84

2011-6-21

6,4-2目錄結(jié)構(gòu)

□單級目錄

□兩級目錄

□多級目錄

山東農(nóng)業(yè)上學(xué)計算機(jī)系85

2011-6-21

單級目錄結(jié)構(gòu)（Single-LevelDirectory）

directorycatboatestdatamailconthexrecords

□Namingproblem（命名問題）

□Groupingproblem（分組）

山東農(nóng)業(yè)上學(xué)計算機(jī)系86

2011-6-21

單級目錄示意圖

文件名［物理地址文件說明-狀態(tài)位［

V/十^1rJL

文件名21

—

山東農(nóng)業(yè)上學(xué)計算機(jī)系87

2011-6-21

單級目錄特點(diǎn)

口優(yōu)點(diǎn)：簡單且能實(shí)現(xiàn)目錄管理的基本功能。

□缺點(diǎn)：

1.查找速度慢。

2.限制了用戶對文件的命名。

3.不便于實(shí)現(xiàn)文件共享。

山東農(nóng)業(yè)上學(xué)計算機(jī)系88

2011-6-21

兩級目錄結(jié)構(gòu)Two-LevelDirectory)

MFD

-WFI-子目錄指針

user"11

user2j

*

■

兩級目錄結(jié)構(gòu)(Two?LevelDirectory)

山東農(nóng)業(yè)上學(xué)計算機(jī)系90

2011-6-21

兩級目錄的特點(diǎn)

口基本克服了單級目錄的缺點(diǎn)，并具有以下

優(yōu)點(diǎn)：

工■提高了檢索目錄的速度。

2.在不同的目錄中可以有相同的文件名。

3.不同用戶還可以使用不同的文件名來訪問系統(tǒng)

中的同一個共享文件。

□存在的問題是各用戶之間被完全隔離了，

無法進(jìn)行合作。

山東農(nóng)業(yè)上學(xué)計算機(jī)系91

2011-6-21

Tree-StructuredDirectories

（樹型目錄/多級目錄結(jié)構(gòu)）

多級目錄結(jié)構(gòu)

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

□路徑名

□當(dāng)前目錄

山東農(nóng)業(yè)上學(xué)計算機(jī)系93

2011-6-21

6?4?3目錄查詢技術(shù)

口線性檢索法

□Hash方法。

山東農(nóng)業(yè)上學(xué)計算機(jī)系94

2011-6-21

線性檢索法

根目錄結(jié)點(diǎn)6是132號盤塊是結(jié)點(diǎn)26是496號盤塊是

/usr的目錄/usr/ast的目錄/usr/ast的目錄

6■26■

1??6??

19dick64grants

30erik92books

51jim60IDbox

26a3t81minik

1

45bal17src

usr字段

查找/usr/ast/mbox的步驟

山東農(nóng)業(yè)上學(xué)計算機(jī)系95

2011-6-21

Hash法

□因用Hash方法可能會產(chǎn)生沖突，檢索的三

種情況如下：

1.如果目錄表中相應(yīng)的目錄項是空的，則表

示系統(tǒng)無指定文件。

2.如果目錄項中的文件名于指定文件名匹配，

則表示找到指定文件。

3.如果目錄項中的文件名于指定文件名不匹

配，則表示發(fā)生了“沖突”，需用解決