Chap61~63文件組織和數(shù)據(jù)存儲(chǔ)

操作系統(tǒng)

第六章文件管理2013Chap6.1~6.3

第六章文件管理

6.1文件6.2文件目錄6.3文件組織與數(shù)據(jù)存儲(chǔ)6.4文件系統(tǒng)其他功能的實(shí)現(xiàn)6.5Linux的文件管理6.6Windows2003文件系統(tǒng)

文件系統(tǒng)概述(1)文件系統(tǒng)是操作系統(tǒng)中負(fù)責(zé)存取和管理信息的模塊，它用統(tǒng)一的方式管理用戶和系統(tǒng)信息的存儲(chǔ)、檢索、更新、共享和保護(hù)，并為用戶提供一整套方便有效的文件使用和操作方法。文件的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。邏輯文件和物理文件。對(duì)于用戶來(lái)說(shuō)，可按需要并遵循文件系統(tǒng)的規(guī)則定義文件信息的邏輯結(jié)構(gòu)，由文件系統(tǒng)提供“按名存取”來(lái)實(shí)現(xiàn)對(duì)文件信息的存儲(chǔ)和檢索；對(duì)于系統(tǒng)來(lái)說(shuō)，必須采用特定數(shù)據(jù)結(jié)構(gòu)和有效算法，實(shí)現(xiàn)文件的邏輯結(jié)構(gòu)到存儲(chǔ)結(jié)構(gòu)的映射，實(shí)現(xiàn)對(duì)文件存儲(chǔ)空間和文件信息的管理，提供多種存取方法。文件系統(tǒng)概述(2)

文件系統(tǒng)面向用戶的功能?

文件的按名存取?

文件目錄建立和維護(hù)?

實(shí)現(xiàn)邏輯文件到物理文件的轉(zhuǎn)換?

文件存儲(chǔ)空間的分配和管理?

提供合適的文件存取方法?

實(shí)現(xiàn)文件的共享、保護(hù)和保密?

提供一組可供用戶使用的文件操作和命令?

提供與設(shè)備管理的統(tǒng)一接口6.1文件

6.1.1文件概念6.1.2文件命名6.1.3文件類(lèi)型6.1.4文件屬性6.1.5文件存取方法6.1.1文件的概念(1)文件是由文件名字標(biāo)識(shí)的一組信息的集合，文件名字是字母或數(shù)字組成的字母數(shù)字串，它的格式和長(zhǎng)度因系統(tǒng)而異。6.1.1文件的概念(1)

還可按文件的邏輯結(jié)構(gòu)或物理結(jié)構(gòu)進(jìn)行分類(lèi)，將在下面討論。在現(xiàn)代操作系統(tǒng)中，不但信息組織成文件，對(duì)設(shè)備的訪問(wèn)也都基于文件進(jìn)行，例如，打印一批數(shù)據(jù)就是向打印機(jī)設(shè)備文件寫(xiě)數(shù)據(jù)，從鍵盤(pán)接收一批數(shù)據(jù)就是從鍵盤(pán)設(shè)備文件讀數(shù)據(jù)。文件的概念(2)

文件系統(tǒng)優(yōu)點(diǎn)

用戶使用方便按名存取文件安全可靠由于用戶通過(guò)文件系統(tǒng)才能實(shí)現(xiàn)對(duì)文件的訪問(wèn)，而系統(tǒng)能提供各種安全、保密和保護(hù)措施，可防止對(duì)文件信息的有意或無(wú)意的破壞或竊用實(shí)現(xiàn)文件共享不同用戶可使用同名或異名的同一個(gè)文件，這樣，節(jié)省文件存儲(chǔ)空間，減少傳輸信息的交換時(shí)間，提高文件空間的利用率6.1.2文件的命名

文件是一個(gè)抽象機(jī)制，提供了把文件保存在磁盤(pán)上，用戶不必了解信息存儲(chǔ)細(xì)節(jié)且便于讀取的方法，這一抽象機(jī)制中最重要的是文件命名。文件名是字母或數(shù)字組成的字母數(shù)字串，它的格式和長(zhǎng)度因系統(tǒng)而異。6.1.2文件的命名

文件名字由：文件名和擴(kuò)展名兩部分組成，前者用于識(shí)別文件，后者用于區(qū)別文件類(lèi)型，中間用“·”分隔開(kāi)來(lái)，它們都是字母或數(shù)字組成的字母數(shù)字串，操作系統(tǒng)還提供通配符“?”和“*”，便于對(duì)一組文件進(jìn)行分類(lèi)或操作。文件名字最長(zhǎng)可為255個(gè)字符。Windows的文件名字不區(qū)分大小寫(xiě)，相反UNIX/Linux卻區(qū)分大小寫(xiě)字母。文件名字可用字符包括字母、數(shù)字及特殊符號(hào)，每個(gè)操作系統(tǒng)對(duì)可用字符作一定限制，像Windows的文件名和擴(kuò)展名不能使用＼、/、<、>、｜和”等字符。6.1.2文件的命名

系統(tǒng)有一些約定擴(kuò)展名，例如：.txt指明純文本文件，.exe表示可執(zhí)行浮動(dòng)二進(jìn)制代碼文件，.bat表示批命令文件，.obj表示編譯或匯編生成的目標(biāo)文件等。.zip壓縮文件.mpeg多媒體視頻文件.lib庫(kù)文件……

6.1.3文件的類(lèi)型按用途分類(lèi)：系統(tǒng)文件、庫(kù)文件和用戶文件按保護(hù)級(jí)別分類(lèi)：只讀文件、讀寫(xiě)文件和不保護(hù)文件按信息流向分類(lèi)：輸入文件、輸出文件和輸入輸出文件按存放時(shí)限分類(lèi)：臨時(shí)文件、永久文件、檔案文件按數(shù)據(jù)類(lèi)型分類(lèi)：源程序文件、目標(biāo)文件和可執(zhí)行文件按設(shè)備類(lèi)型分成：磁盤(pán)文件、磁帶文件、軟盤(pán)文件6.1.3文件的類(lèi)型

操作系統(tǒng)支持不同類(lèi)型文件：普通文件：源程序文件、數(shù)據(jù)文件、目標(biāo)代碼文件及操作系統(tǒng)文件、庫(kù)文件、實(shí)用程序文件都是普通文件，它們通常存儲(chǔ)在磁盤(pán)上。目錄文件：由文件目錄構(gòu)成的用來(lái)維護(hù)文件系統(tǒng)結(jié)構(gòu)的系統(tǒng)文件，普通文件的查找依賴(lài)于目錄文件，由于它也是由字符信息組成的文件，故可進(jìn)行與普通文件類(lèi)似的如讀、寫(xiě)等種種目錄操作。特別文件：塊設(shè)備文件、字符設(shè)備文件、管道文件。文件的屬性

?文件基本屬性：文件名和擴(kuò)展名、文件屬主ID、文件所屬組ID、文件長(zhǎng)度等

?文件類(lèi)型屬性：如普通文件、目錄文件、系統(tǒng)文件、隱式文件、設(shè)備文件、pipe文件、socket文件等。也可按文件信息分為：ASCII碼文件、二進(jìn)制碼文件等。

?文件保護(hù)屬性：常用的訪問(wèn)方式有可讀、可寫(xiě)、可執(zhí)行、可更新、可刪除等；上鎖標(biāo)志和開(kāi)鎖標(biāo)志；

?文件管理屬性：文件創(chuàng)建時(shí)間、最后訪問(wèn)時(shí)間、最后修改時(shí)間等

?文件控制屬性：邏輯記錄長(zhǎng)、文件當(dāng)前長(zhǎng)、文件最大長(zhǎng)，關(guān)鍵字位置、關(guān)鍵字長(zhǎng)度、信息位置、文件打開(kāi)次數(shù)等

WindowsXPAccess-controlListManagement文件保護(hù)屬性(1)文件保護(hù)屬性用于防止文件被破壞，稱(chēng)為文件保護(hù)。包括兩個(gè)方面：一是防止系統(tǒng)崩潰所造成的文件破壞；二是防止文件主和其他用戶有意或無(wú)意的非法操作所造成的文件不安全性。文件保護(hù)屬性(2)防止系統(tǒng)崩潰造成文件破壞的方法：

?

定時(shí)轉(zhuǎn)儲(chǔ)

?

多副本防止系統(tǒng)崩潰造成文件破壞的方法：

?

訪問(wèn)控制--防止文件主和其他用戶有意或無(wú)意的非法操作所造成的文件不安全性，基本思想是建立三元組：

(用戶、對(duì)象、存取權(quán)限)文件保護(hù)屬性(3)用戶：是指每一個(gè)操作系統(tǒng)使用者的標(biāo)識(shí)。對(duì)象：在操作系統(tǒng)中一般都是文件，因?yàn)?，操作系統(tǒng)把設(shè)備資源也統(tǒng)一到文件層次，如通過(guò)設(shè)備文件使用設(shè)備、通過(guò)socket關(guān)聯(lián)文件使用進(jìn)程通信等，當(dāng)然不排除其他資源。存取權(quán)限：定義了用戶對(duì)文件的訪問(wèn)權(quán)，如：讀、寫(xiě)、刪除、執(zhí)行等等。一個(gè)安全性較高的系統(tǒng)權(quán)限劃分得較多較細(xì)。文件保護(hù)屬性(4)?UNIX/Linux把用戶分為文件主、同組用戶、其他用戶三類(lèi)，?

定義存取權(quán)限可讀r、可寫(xiě)w、可執(zhí)行x，目錄項(xiàng)中的文件屬性共有10位：

-rwxrwxrwx第1位：表示文件是普通文件(-)，還是目錄文件(d)、符號(hào)鏈接文件(l)、設(shè)備文件(b/c)。第2-4位：表示文件主對(duì)文件的存取權(quán)限。第5-7位：表示同組用戶對(duì)文件的存取權(quán)限。第8-10位：表示其他用戶對(duì)文件的存取權(quán)限。如一個(gè)文件的屬性是-rwxr-x--x，表示該文件是普通文件，文件主對(duì)它可讀、可寫(xiě)、可執(zhí)行；同組用戶對(duì)它可讀、可執(zhí)行；其他用戶對(duì)它只可執(zhí)行。文件的存取

存取方法是操作系統(tǒng)為用戶程序提供的使用文件的技術(shù)和手段。由于文件類(lèi)型不同，用戶使用要求不同，因而需要操作系統(tǒng)提供多種存取方法來(lái)滿足用戶要求。存取方法

1順序存取

2

直接存取

3

索引存取文件的存取

1順序存取無(wú)論是無(wú)結(jié)構(gòu)字節(jié)流文件，還是有結(jié)構(gòu)記錄式文件，存取操作都在上次的基礎(chǔ)上進(jìn)行，對(duì)固定長(zhǎng)記錄的順序文件采用隨機(jī)訪問(wèn)，當(dāng)要讀出第i個(gè)記錄時(shí)，其邏輯地址可由記錄長(zhǎng)×i得到。順序存取主要用于磁帶文件，但也適用于磁盤(pán)上的順序文件。對(duì)可變長(zhǎng)記錄的順序文件，每個(gè)記錄的長(zhǎng)度信息存放于記錄的第一個(gè)字段中，它的存取操作分兩步進(jìn)行。讀出時(shí)，根據(jù)讀指針值先讀出一個(gè)物理記錄到緩沖區(qū)，得到記錄長(zhǎng)后，再取出當(dāng)前邏輯記錄；寫(xiě)入時(shí)，先在緩沖區(qū)裝配邏輯記錄和記錄長(zhǎng)，再寫(xiě)入寫(xiě)指針指向的物理記錄。由于順序文件是順序存取的，可采用成組和分解操作來(lái)加快文件的I/O。文件的存取

2直接存取很多應(yīng)用場(chǎng)合要求快速地以任意次序直接讀寫(xiě)某個(gè)記錄為了實(shí)現(xiàn)直接存取，一個(gè)文件可看作由順序編號(hào)的物理塊組成的，這些塊常常劃成等長(zhǎng)，作為定位和存取的最小單位，例如:用戶可請(qǐng)求讀塊22、然后，寫(xiě)塊48，再讀塊9等等，直接存取文件對(duì)讀或?qū)憠K的次序沒(méi)有限制。用戶提供給操作系統(tǒng)的是相對(duì)塊號(hào)，它是相對(duì)于文件開(kāi)始位置的位移量，而絕對(duì)塊號(hào)則由系統(tǒng)換算得到。對(duì)于記錄式文件，要為每個(gè)文件記錄指定關(guān)鍵字，可通過(guò)關(guān)鍵字映射直接檢索和存取文件信息，這也是各類(lèi)應(yīng)用中用得最多的一種直接存取方式文件的存取

3索引存取基于索引文件的索引存取方法，由于文件中的記錄不按它的位置，而按它的記錄名或記錄鍵來(lái)編址，所以，用戶提供記錄名或記錄鍵后，先按名搜索，再查找到所需記錄。采用記錄鍵時(shí)應(yīng)按某種順序存放，例如，按字母先后次序來(lái)排序，對(duì)于這種文件，除可采用按鍵存取外，也可采用順序存取或直接存取的方法，信息塊的地址都可以通過(guò)查找記錄鍵而換算出來(lái)。實(shí)際的系統(tǒng)中，大都采用多級(jí)索引，以加速記錄查找過(guò)程。6.2文件目錄

6.2.1文件控制塊、文件目錄與目錄文件6.2.2層次目錄結(jié)構(gòu)6.2.3目錄的檢索文件系統(tǒng)的分層結(jié)構(gòu)文件管理--實(shí)現(xiàn)文件的邏輯結(jié)構(gòu)，為用戶提供各種文件系統(tǒng)調(diào)用，及文件訪問(wèn)權(quán)限的設(shè)置等工作；目錄管理--負(fù)責(zé)查找文件描述符，進(jìn)而找到需要訪問(wèn)的文件，及進(jìn)行訪問(wèn)權(quán)限檢查等工作；磁盤(pán)主存映射管理--將文件的邏輯地址轉(zhuǎn)換成磁盤(pán)的物理地址，即由邏輯塊號(hào)找到柱面號(hào)、磁頭號(hào)和扇區(qū)號(hào)，具體的數(shù)據(jù)傳輸操作由設(shè)備管理實(shí)現(xiàn)。6.2.1文件目錄與文件目錄項(xiàng)(1)文件系統(tǒng)實(shí)現(xiàn)“按名存取”文件的重要手段是文件目錄文件系統(tǒng)基本功能之一是負(fù)責(zé)文件目錄的建立、維護(hù)和檢索。文件目錄項(xiàng)又稱(chēng)文件控制塊FCB(Block)。有了FCB就可方便地實(shí)現(xiàn)文件的“按名存取”，每當(dāng)創(chuàng)建一個(gè)文件時(shí)，系統(tǒng)就要為它建立一個(gè)FCB，用來(lái)記錄文件的所有屬性信息，存取該文件時(shí)，先找到它的FCB，再找到文件信息盤(pán)塊號(hào)或首塊物理位置就能存取文件信息。文件目錄與文件目錄項(xiàng)(2)

文件目錄項(xiàng)內(nèi)容文件標(biāo)識(shí)和控制信息：文件名、用戶名、文件主存取權(quán)限、授權(quán)者存取權(quán)限、文件口令；文件類(lèi)型等。文件邏輯結(jié)構(gòu)信息：文件的邏輯結(jié)構(gòu)，如記錄類(lèi)型、記錄個(gè)數(shù)、記錄長(zhǎng)度、成組因子數(shù)等。文件物理結(jié)構(gòu)信息:文件所在設(shè)備名，文件物理結(jié)構(gòu)類(lèi)型，記錄存放在輔存的盤(pán)塊號(hào)或文件信息首塊盤(pán)塊號(hào)，也可指出文件索引所在位置等。文件目錄與文件目錄項(xiàng)(2)

文件目錄項(xiàng)內(nèi)容文件使用信息：共享文件的進(jìn)程數(shù)，文件被修改的情況，文件最大長(zhǎng)度和當(dāng)前大小等。文件管理信息:文件建立日期、最近修改日期、最近訪問(wèn)日期、文件保留期限、記帳信息等。

文件目錄為了加快文件的查找，通常把FCB集中起來(lái)進(jìn)行管理，組成文件目錄文件目錄項(xiàng)文件目錄包含許多目錄項(xiàng)，目錄項(xiàng)有兩種，用于描述子目錄和文件FCB，

目錄文件:全部由目錄項(xiàng)構(gòu)成的文件稱(chēng)為目錄文件，與普通文件不同的是，目錄文件永遠(yuǎn)不會(huì)空，它至少包含兩個(gè)目錄項(xiàng)：當(dāng)前目錄項(xiàng)“.”和父目錄項(xiàng)“..”。文件目錄與文件目錄項(xiàng)(3)

文件目錄項(xiàng)內(nèi)容層次目錄結(jié)構(gòu)(1)

Linux和Windows層次目錄結(jié)構(gòu)桌面我的電腦軟盤(pán)本地磁盤(pán)C:本地磁盤(pán)D:user1user2…CD驅(qū)動(dòng)器…網(wǎng)絡(luò)鄰居回收站…桌面我的電腦軟盤(pán)(A:)本地磁盤(pán)(C:)本地磁盤(pán)(D:)user1user2…CD驅(qū)動(dòng)器(E:)…網(wǎng)絡(luò)鄰居回收站…Btestfile.ctty00／devusrlibetchometty01binlibmantmppasswdvarfei1myfile.cgettyfei3fei2fei4fei5層次目錄結(jié)構(gòu)(2)路徑名絕對(duì)路徑名相對(duì)路徑名層次目錄結(jié)構(gòu)(3)

每一級(jí)目錄可以是下一級(jí)目錄的說(shuō)明，也可以是文件的說(shuō)明，形成層次關(guān)系。多級(jí)目錄結(jié)構(gòu)采用樹(shù)型結(jié)構(gòu)，是一棵倒向有根樹(shù)，樹(shù)根是根目錄；從根向下，每個(gè)樹(shù)枝是一個(gè)子目錄；而樹(shù)葉是文件。樹(shù)型多級(jí)目錄優(yōu)點(diǎn):較好地反映現(xiàn)實(shí)世界中具有層次關(guān)系的數(shù)據(jù)集合和確切地反映系統(tǒng)內(nèi)部文件的分支結(jié)構(gòu)；不同文件可重名，只要它們不位于同一末端子目錄中，易于規(guī)定不同層次或子目錄中文件的不同存取權(quán)限，便于文件的保護(hù)、保密和共享等，有利于系統(tǒng)的維護(hù)和查找。層次目錄結(jié)構(gòu)(4)

如果規(guī)定每個(gè)文件都只有一個(gè)父目錄，稱(chēng)為純樹(shù)型目錄結(jié)構(gòu)，其缺點(diǎn)是文件共享不是對(duì)稱(chēng)的，父目錄有效擁有該文件，其他被授權(quán)用戶必須經(jīng)過(guò)屬主目錄才能對(duì)該文件進(jìn)行訪問(wèn)。有向無(wú)環(huán)圖目錄盡管它允許文件有多個(gè)父目錄而破壞樹(shù)的特性，但不同用戶可以對(duì)稱(chēng)方式實(shí)現(xiàn)文件共享，即可能屬于不同用戶的多個(gè)目錄，使用不同文件名能訪問(wèn)和共享同一個(gè)文件。有向無(wú)環(huán)圖目錄結(jié)構(gòu)的維護(hù)比純樹(shù)型目錄結(jié)構(gòu)復(fù)雜，由于一個(gè)文件可能有多個(gè)父目錄，需為每個(gè)文件維護(hù)一個(gè)引用計(jì)數(shù)，用來(lái)記錄文件的父目錄個(gè)數(shù)，僅當(dāng)引用計(jì)數(shù)為1時(shí)，刪除操作才移去文件，否則僅僅把相關(guān)記錄從父目錄中刪去。層次目錄結(jié)構(gòu)(5)

Linux支持多父目錄，但其中一個(gè)是主父目錄，它是文件擁有者，且文件被物理存儲(chǔ)在此目錄下，其他次父目錄通過(guò)link方式來(lái)連結(jié)和引用文件，允許任一父目錄刪除共享文件。圖6-1(a)中便示例這種文件共享的情形，文件/home/fei1為myfile.c的主父目錄(圖中實(shí)線表示)，/home/fei2和/home/fei3/fei4均為文件myfile.c的次父目錄(圖中虛線表示)。Windows實(shí)現(xiàn)被稱(chēng)作“快捷方式”的多父目錄連結(jié)，快捷方式是一些指向不同文件夾(子目錄)和菜單之間任意復(fù)制和移動(dòng)的文件及文件夾的指針，刪除快捷方式就是刪除指針。UNIX/Linux特殊目錄項(xiàng)建立方法(1)

文件名inode號(hào)14個(gè)字節(jié)2個(gè)字節(jié)FCB中的文件名和其他管理信息分開(kāi)，其他信息單獨(dú)組成一個(gè)數(shù)據(jù)結(jié)構(gòu)，稱(chēng)為索引節(jié)點(diǎn)inode，該索引節(jié)點(diǎn)的位置由inode號(hào)標(biāo)識(shí)。于是，目錄項(xiàng)中僅剩下14個(gè)字節(jié)的文件名和2個(gè)字節(jié)的inode號(hào)，稱(chēng)為基本目錄項(xiàng)，因此，一個(gè)磁盤(pán)塊可存放幾十個(gè)基本目錄項(xiàng)，系統(tǒng)把由文件目錄項(xiàng)組成的目錄文件和普通文件一樣對(duì)待，均存放在磁盤(pán)中，文件系統(tǒng)中的每個(gè)文件，都有一個(gè)磁盤(pán)inode與之對(duì)應(yīng)，這些inode被集中放在磁盤(pán)上的inode區(qū)。UNIX/Linux特殊目錄項(xiàng)建立方法(1)FCB對(duì)于文件的作用，猶如PCB對(duì)于進(jìn)程的作用，集中這個(gè)文件的所有相關(guān)信息，找到inode，就能獲得該文件的必要信息。每個(gè)磁盤(pán)inode結(jié)構(gòu)使用32或64個(gè)字節(jié)，包含如下信息：文件長(zhǎng)度及在存儲(chǔ)設(shè)備上的物理位置、文件主標(biāo)識(shí)、文件類(lèi)型(普通/目錄/特別/管道文件)、存取權(quán)限、文件鏈接數(shù)(共享數(shù))、文件大小(字節(jié)數(shù))、文件創(chuàng)建、訪問(wèn)和修改時(shí)間，及inode節(jié)點(diǎn)是否空閑，其中有一項(xiàng)addr[40]數(shù)組用于存放文件數(shù)據(jù)或基本目錄項(xiàng)所在的磁盤(pán)塊號(hào)的索引表，每3個(gè)字節(jié)記錄一個(gè)磁盤(pán)塊號(hào)，因此索引表共13項(xiàng)。6.2.3文件目錄的檢索

(a)用戶角度目錄結(jié)構(gòu)usrmyfilxyzhomefei1myfile.cfei3fei2Afei4fei5testfile.cB685．100．．941A270fei1250fei2770fei3270．685．．302myfile.c250．685．．302myfile.c770．685．．345fei4565fei5345．770．．302testfile.c565．770．．824B

不同角度的目錄結(jié)構(gòu)(b)系統(tǒng)角度目錄鏈接6.3文件組織與數(shù)據(jù)存儲(chǔ)6.3.1文件的存儲(chǔ)6.3.2文件的邏輯結(jié)構(gòu)6.3.3文件的物理結(jié)構(gòu)6.3.1文件的存儲(chǔ)

卷是存儲(chǔ)介質(zhì)的物理單位，塊是存儲(chǔ)介質(zhì)上連續(xù)信息所組成的一個(gè)區(qū)域，也叫物理記錄。塊是主存儲(chǔ)器和輔助存儲(chǔ)設(shè)備信息交換的物理單位，每次交換一塊或整數(shù)塊。決定塊的大小要考慮到用戶使用方式、數(shù)據(jù)傳輸效率和存儲(chǔ)設(shè)備類(lèi)型等多種因素。不同類(lèi)型的存儲(chǔ)介質(zhì)，塊的長(zhǎng)短常常各不相同；同一類(lèi)型的存儲(chǔ)介質(zhì)，塊的長(zhǎng)短也可以不同。文件的邏輯結(jié)構(gòu)

1

流式文件和記錄式文件(1)文件組織指文件中信息的配置和構(gòu)造方式，應(yīng)該從文件的邏輯結(jié)構(gòu)和組織及文件的物理結(jié)構(gòu)和組織兩方面考慮。文件的邏輯結(jié)構(gòu)和組織是從用戶觀點(diǎn)出發(fā)，研究用戶概念中的信息組織方式，這是用戶能觀察到，可加以處理的數(shù)據(jù)集合。流式文件和記錄式文件(2)

文件邏輯結(jié)構(gòu)分兩種形式：流式文件，記錄式文件。流式文件指文件內(nèi)的數(shù)據(jù)不再組成記錄，只是依次的一串信息集合，稱(chēng)為字節(jié)流文件。文件常按長(zhǎng)度來(lái)讀取所需信息，也可用插入特殊字符作為分界。記錄式文件包含若干邏輯記錄，邏輯記錄是文件中按信息在邏輯上的獨(dú)立含意劃分的信息單位。記錄式文件域(field)是基本數(shù)據(jù)單元。一個(gè)域包含一個(gè)值。域可以通過(guò)它的長(zhǎng)度和數(shù)據(jù)類(lèi)型(如ascii字符串、二進(jìn)制數(shù)等)來(lái)描述。記錄(record)是一組相關(guān)的域的集合，它可以看做是應(yīng)用程序的一個(gè)單元。文件(file)是一組相似記錄的集合，它被用戶和應(yīng)用程序看做是一個(gè)實(shí)體，并可以通過(guò)名字訪問(wèn)。數(shù)據(jù)庫(kù)(database)是一組相關(guān)的數(shù)據(jù)集合，它的本質(zhì)特征是數(shù)據(jù)元素間存在著明確的關(guān)系，并且可供不同的應(yīng)用程序使用。數(shù)據(jù)庫(kù)可能包含有與一個(gè)組織或項(xiàng)目相關(guān)的所有信息，如一家商店或一項(xiàng)科學(xué)研究。數(shù)據(jù)庫(kù)自身是由一種或多種類(lèi)型的文件組成的。流式文件和記錄式文件(3)

記錄式文件包含若干邏輯記錄，邏輯記錄是文件中按信息在邏輯上的獨(dú)立含意劃分的信息單位。分類(lèi):1)記錄式順序文件：

文件的記錄順序生成和被順序訪問(wèn)，

2)記錄式索引順序文件：這種文件使用索引表，表項(xiàng)包含記錄鍵和索引指針，記錄鍵由應(yīng)用程序確定，而索引指針便指向相應(yīng)記錄。提供的使用記錄式索引順序文件的系統(tǒng)調(diào)用有：getrecord()，參數(shù)包括文件名和記錄鍵，返回一個(gè)指定記錄；putrecord()，參數(shù)包括文件名和記錄鍵，文件系統(tǒng)在選擇的文件位置處寫(xiě)入指定記錄，并建立索引表項(xiàng)。2

成組和分解(1)

邏輯記錄和塊的關(guān)系

邏輯記錄是按信息在邏輯上的獨(dú)立含義劃分的單位，塊是存儲(chǔ)介質(zhì)上連續(xù)信息所組成的區(qū)域。邏輯記錄被存放到文件存儲(chǔ)器的存儲(chǔ)介質(zhì)上時(shí)，可能占用一塊或多塊，也可以一個(gè)物理塊包含多個(gè)邏輯記錄。成組操作:若干邏輯記錄合并成一組，寫(xiě)入一塊。分解操作:當(dāng)存儲(chǔ)介質(zhì)上的一個(gè)物理塊讀進(jìn)系統(tǒng)輸入緩沖區(qū)后，把邏輯記錄從塊中分離出來(lái)的操作。塊因子:每塊中的邏輯記錄的個(gè)數(shù)。成組和分解(2)

記錄成組和分解處理過(guò)程

邏輯記錄1邏輯記錄2邏輯記錄3物理記錄邏輯記錄用戶緩沖區(qū)系統(tǒng)緩沖區(qū)3記錄格式?記錄格式

格式F：定長(zhǎng)記錄格式V：變長(zhǎng)記錄格式S：跨塊記錄定長(zhǎng)記錄固定組塊(fixedblocking)：使用固定長(zhǎng)度的記錄，并且若干條完整的記錄被保存在一個(gè)塊中。在每個(gè)塊的末尾可能會(huì)有一些未使用的空間，稱(chēng)為內(nèi)部碎片。

變長(zhǎng)記錄可變長(zhǎng)度非跨越式組塊(variable-lengthunspannedblocking)：使用可變長(zhǎng)度的記錄，但并不采用跨越的方式。如果下一條記錄比塊中剩余的未使用的空間大，則無(wú)法使用這一部分，因此在大多數(shù)中都會(huì)有未使用的空間。

跨塊記錄可變長(zhǎng)度跨越式組塊(variable-lengthspannedblocking)：使用長(zhǎng)度可變的記錄，并且緊縮到塊中，使得塊中沒(méi)有未使用空間。因此，某些記錄可能會(huì)跨越兩個(gè)塊，通過(guò)一個(gè)指向后繼塊的指針連接。4記錄鍵為了方便記錄式文件的組織和管理，提高文件記錄的查找效率，通常，對(duì)邏輯文件的每個(gè)邏輯記錄至少指定一個(gè)與之對(duì)應(yīng)的基本數(shù)據(jù)項(xiàng)，利用它可與同一文件中的其他邏輯記錄區(qū)別開(kāi)來(lái)，這個(gè)用于標(biāo)識(shí)某個(gè)邏輯記錄的數(shù)據(jù)項(xiàng)，稱(chēng)為記錄鍵，也叫關(guān)鍵字，簡(jiǎn)稱(chēng)鍵。在同一個(gè)文件中，能唯一地標(biāo)識(shí)某個(gè)邏輯記錄的記錄鍵，稱(chēng)為主鍵。4記錄鍵固定長(zhǎng)邏輯記錄存儲(chǔ)時(shí)分兩個(gè)字段，第一字段是記錄鍵，第二字段為記錄信息；變長(zhǎng)邏輯記錄存儲(chǔ)時(shí)分三個(gè)字段，第一字段指明單個(gè)變長(zhǎng)邏輯記錄的記錄鍵和記錄信息的字節(jié)個(gè)數(shù)(也包括第一字段本身的長(zhǎng)度)，第二字段存放記錄鍵，第三字段為記錄信息。采用鍵來(lái)標(biāo)識(shí)的變長(zhǎng)邏輯記錄格式鮮有操作系統(tǒng)來(lái)提供，原因是各種數(shù)據(jù)庫(kù)管理系統(tǒng)中都已經(jīng)實(shí)現(xiàn)這種復(fù)雜的文件組織方式。6.3.3文件的物理結(jié)構(gòu)(1)

文件系統(tǒng)往往根據(jù)存儲(chǔ)設(shè)備類(lèi)型、存取要求、記錄使用頻度和存儲(chǔ)空間容量等因素提供若干種文件存儲(chǔ)結(jié)構(gòu)，把邏輯文件以不同方式保存到物理存儲(chǔ)設(shè)備的介質(zhì)上。文件的物理結(jié)構(gòu)和組織是指邏輯文件在物理存儲(chǔ)空間中存放方法和組織關(guān)系。文件的存儲(chǔ)結(jié)構(gòu)涉及：塊的劃分、記錄的排列、索引的組織、信息的搜索，其優(yōu)劣直接影響文件系統(tǒng)的性能。第一類(lèi)計(jì)算法。設(shè)計(jì)映射算法，通常用線性計(jì)算法、雜湊法等，通過(guò)對(duì)記錄鍵的計(jì)算轉(zhuǎn)換成對(duì)應(yīng)的物理地址，從而找到所需記錄。直接尋址文件、計(jì)算尋址文件，順序文件均屬此類(lèi)，計(jì)算法的存取效率高，不必增加存儲(chǔ)空間存放附加控制信息，能把分布范圍較廣的鍵均勻地映射到一個(gè)存儲(chǔ)區(qū)域中；

第二類(lèi)指針?lè)?。?gòu)造文件物理結(jié)構(gòu)的方法文件的物理結(jié)構(gòu)(2)

第一類(lèi)計(jì)算法。第二類(lèi)指針?lè)āＴO(shè)置專(zhuān)門(mén)指針，指明相應(yīng)記錄的物理地址或表達(dá)各記錄之間的關(guān)聯(lián)。索引文件、索引順序文件、連接文件等均屬此類(lèi)。優(yōu)點(diǎn)是可將文件信息的邏輯次序與在存儲(chǔ)介質(zhì)上的物理塊排列次序完全分開(kāi)，便于隨機(jī)存取，便于更新，能加快存取速度。但使用指針要耗用較多存儲(chǔ)空間，大型文件的索引查找要耗用較多處理機(jī)時(shí)間，所以，究竟用哪種文件存儲(chǔ)結(jié)構(gòu)，必須根據(jù)應(yīng)用需要、響應(yīng)時(shí)間和存儲(chǔ)空間等多種因素進(jìn)行權(quán)衡折中。構(gòu)造文件物理結(jié)構(gòu)的方法文件的物理結(jié)構(gòu)(2)

1順序文件(連續(xù)文件)文件中邏輯上連續(xù)的信息存放到存儲(chǔ)介質(zhì)的依次相鄰的塊上便形成順序文件。邏輯記錄順序和物理記錄順序完全一致的文件，通常，記錄按出現(xiàn)的次序被讀出或修改。優(yōu)點(diǎn):順序存取記錄時(shí)速度較快，批處理文件，系統(tǒng)文件用得很多。采用磁帶存放順序文件時(shí)，總可以保持快速存取的優(yōu)點(diǎn)。缺點(diǎn):建立文件前需要能預(yù)先確定文件長(zhǎng)度，以便分配存儲(chǔ)空間；修改、插入和增加文件記錄有難度；對(duì)可變長(zhǎng)記錄的處理很困難；磁盤(pán)作連續(xù)分配，會(huì)造成空閑塊的浪費(fèi)。順序文件(連續(xù)文件)順序文件(連續(xù)文件)2連接文件(串聯(lián)文件)(1)

連接文件結(jié)構(gòu)示意圖

文件控制塊……0連接結(jié)構(gòu)的特點(diǎn)是使用連接字(指針)來(lái)表示文件中各個(gè)記錄之間的關(guān)系。文件信息存放在磁盤(pán)的若干個(gè)物理塊中，第一塊文件信息的物理地址由文件FCB給出，而每塊的連接字指出文件的下一個(gè)物理塊位置，通常，連接字內(nèi)容為0時(shí)，表示文件至本塊結(jié)束。

引進(jìn)指向其它數(shù)據(jù)的連接表示是計(jì)算機(jī)程序設(shè)計(jì)的一種重要手段，是表示復(fù)雜數(shù)據(jù)關(guān)系的一種重要方法。連接結(jié)構(gòu)的優(yōu)缺點(diǎn)。連接結(jié)構(gòu)必須將連接字與數(shù)據(jù)信息混合存放，會(huì)破壞數(shù)據(jù)塊的完整性；存取信息須通過(guò)緩沖區(qū)，待獲得連接字后，才能找到下一物理塊地址，因而，僅適宜于順序存取。連接結(jié)構(gòu)恰好克服順序結(jié)構(gòu)不適宜于增、刪、改的缺點(diǎn)，對(duì)某些操作帶來(lái)好處，但其他方面又失去一些性能。連接文件(串聯(lián)文件)(2)一種連接文件建立指針數(shù)組PTRS[n]，每個(gè)PTRS[i]對(duì)應(yīng)一個(gè)磁盤(pán)塊i，如果塊j在文件中跟在塊i之后，那么，元素PTRS[i]=j(即元素PTRS[i]的值為j)。例如，一個(gè)連接文件占用4個(gè)磁盤(pán)塊，文件FCB指出首塊地址，從首塊6開(kāi)始，依次為塊18、塊11和塊13，則有FCB指出6、PTRS[6]=18、PTRS[18]=11、PTRS[11]=13、PTRS[13]=NULL。例子FCB→6

1811130PTRS[6]=18、PTRS[18]=11、PTRS[11]=13、PTRS[13]=NULLFCB→63直接文件(哈希文件)(1)

記錄的關(guān)鍵字與其地址間可通過(guò)某種方式建立對(duì)應(yīng)關(guān)系，利用這種關(guān)系實(shí)現(xiàn)存取的文件叫直接文件。hash技術(shù)要建立hash表，hash表是一個(gè)指針數(shù)組，數(shù)組通過(guò)索引訪問(wèn)，找到的指針便指向數(shù)據(jù)記錄。索引是與數(shù)據(jù)記錄有關(guān)的關(guān)鍵字或其變換，直接文件(哈希文件)(2)

步1構(gòu)造轉(zhuǎn)換(hash)函數(shù)

假定有一個(gè)文件系統(tǒng)，采用hash法來(lái)管理FCB，以便加快文件目錄的查找過(guò)程，下面來(lái)討論hash文件的設(shè)計(jì)過(guò)程設(shè)文件名為8個(gè)ASCⅡ字符。構(gòu)造的hash函數(shù)為模2加“⊕”，求已知文件名的ASCⅡ字符值的模2加值作為該文件的FCB所在物理塊在目錄文件中的索引A，那么，

A=(a1⊕a2⊕…⊕a8)直接文件(哈希文件)(3)

步2建立目錄文件(2)

目錄文件采用索引結(jié)構(gòu)，建立文件時(shí)由步1求出文件名的hash值A(chǔ)，凡A值相同的文件的FCB都存放在同一個(gè)物理塊。磁盤(pán)的物理塊號(hào)存放在索引表中的相對(duì)位置應(yīng)等于A值。

直接文件(哈希文件)(4)

步2建立目錄文件(2)目錄文件

A=1026號(hào)物理塊file1文件控制塊file2文件控制塊

01026直接文件(哈希文件)(5)

步3查找文件

根據(jù)給定文件名，由步1算出該文件的FCB所在物理塊號(hào)在索引表中的相對(duì)位置A。根據(jù)A就可找到該FCB所在物理塊號(hào)，把這個(gè)物理塊讀入主存緩沖區(qū)，用文件名逐個(gè)比較，找出要求的FCB。直接文件(哈希文件)(6)

步4溢出處理

物理塊中存放的FCB是有限的，建立目錄文件時(shí)，如果A值相同的文件數(shù)目超過(guò)物理塊能容納數(shù)時(shí)，產(chǎn)生溢出。溢出時(shí)，系統(tǒng)再申請(qǐng)一個(gè)盤(pán)區(qū)，該區(qū)物理塊號(hào)放在A+k的索引表目中，k是質(zhì)數(shù)作為位移常數(shù)。第二塊盤(pán)區(qū)也溢出，則申請(qǐng)第三塊，塊號(hào)放在A+2×k表目中，依此類(lèi)推。查找目錄時(shí)，如第一塊找不到可找A+k表目中的物理塊號(hào)，讀出后繼續(xù)比較，依次類(lèi)推。4索引文件(1)

索引結(jié)構(gòu)是實(shí)現(xiàn)非連續(xù)存儲(chǔ)的另一種方法，適用于數(shù)據(jù)記錄保存有隨機(jī)存取存儲(chǔ)設(shè)備上的文件。使用索引表，每個(gè)表目包含一個(gè)記錄的鍵及其記錄數(shù)據(jù)的存儲(chǔ)地址，這類(lèi)文件稱(chēng)索引文件。

索引文件(2)

…盤(pán)塊號(hào)…文件控制塊(a)無(wú)鍵索引表塊塊塊兩種索引文件結(jié)構(gòu)示意圖…Key1記錄鍵盤(pán)塊號(hào)Key2……KeyN塊塊塊(b)有鍵索引表文件控制塊索引文件(3)

索引順序文件索引順序文件是順序文件的擴(kuò)展，各記錄本身在介質(zhì)上也順序排列，有直接處理和修改記錄的能力。索引順序文件能象順序文件一樣進(jìn)行快速順序處理，既允許按物理存放次序(記錄出現(xiàn)的次序）；也允許按邏輯順序(由記錄主鍵決定的次序）進(jìn)行處理。二級(jí)索引。二級(jí)索引表的表項(xiàng)列出一級(jí)索引表每一塊最后一個(gè)索引項(xiàng)的鍵值及該索引表區(qū)的地址，若干個(gè)記錄的索引本身也是一種記錄。查找時(shí)先查看二級(jí)索引表找到某鍵所在的索引表區(qū)地址，再搜索一級(jí)索引表找出數(shù)據(jù)記錄。三級(jí)索引。順序文件vs索引文件例子:考慮一個(gè)包含100萬(wàn)記錄的順序文件，為查找某一特定的關(guān)鍵域值，平均需要訪問(wèn)50萬(wàn)次記錄?，F(xiàn)在假設(shè)創(chuàng)建一個(gè)包含了1000項(xiàng)的索引，索引中的關(guān)鍵域或多或少均勻分布在文件中，為找到這條記錄，平均只需要在索引文件中進(jìn)行500次訪問(wèn)，接著在主文件中進(jìn)行500次訪問(wèn)。搜索的開(kāi)銷(xiāo)從500000減少到1000。

順序文件vs索引文件例子:為提供更有效的訪問(wèn)，可以使用多級(jí)索引。最低一級(jí)的索引文件看做是順序文件，然后為該文件創(chuàng)建高一級(jí)的索引文件。再次考慮一個(gè)包含100萬(wàn)條記錄的文件，首先構(gòu)造具有10000項(xiàng)的低級(jí)索引，然后為這個(gè)低級(jí)索引構(gòu)造100項(xiàng)的高級(jí)索引。搜索過(guò)程從高級(jí)索引開(kāi)始，找到指向低級(jí)索引的一項(xiàng)(平均長(zhǎng)度=50次訪問(wèn))。接著搜索這個(gè)索引，找到指向主文件的一項(xiàng)(平均長(zhǎng)度=50次訪問(wèn))。然后搜索主文件(平均長(zhǎng)度=50次訪問(wèn))。因此，平均搜索長(zhǎng)度從500000減少到1000，最后減少到150。SecondaryStorageManagement在二級(jí)存儲(chǔ)中，一個(gè)文件是由許多塊組成的。操作系統(tǒng)或文件管理系統(tǒng)負(fù)責(zé)給文件分配塊。這引發(fā)了兩個(gè)管理問(wèn)題。首先，二級(jí)存儲(chǔ)中的空間必須分配給文件；其次，必須知道哪些空間可以用來(lái)分配。這兩個(gè)問(wèn)題是相關(guān)的，即文件分配采用的方法可能會(huì)影響空閑空間管理的方法。此外，文件結(jié)構(gòu)和分配策略之間也是互相影響的。

SecondaryStorageManagement文件分配涉及到以下幾個(gè)問(wèn)題：當(dāng)創(chuàng)建一個(gè)新文件時(shí)，是否一次性地給它分配所需要的最大空間?給文件分配的空間是一個(gè)或多個(gè)連續(xù)的單元，這些單元稱(chēng)為分區(qū)。一個(gè)分區(qū)的大小可以從一塊到整個(gè)文件。在分配文件時(shí)，分區(qū)的大小應(yīng)該是多少?為跟蹤分配給文件的分區(qū)，應(yīng)該使用哪種數(shù)據(jù)結(jié)構(gòu)或表?在DOS或其他系統(tǒng)中，這種表通稱(chēng)為文件分配表(table,FAT)。

Preallocation預(yù)分配策略要求在發(fā)出創(chuàng)建文件的請(qǐng)求時(shí)聲明該文件的最大大小。在許多情況下，如程序編譯、產(chǎn)生摘要數(shù)據(jù)文件或通過(guò)通信網(wǎng)絡(luò)從另一個(gè)系統(tǒng)中傳送文件時(shí)，都可以很可靠地估計(jì)這個(gè)值。但是對(duì)許多應(yīng)用程序，如果不能可靠地估計(jì)文件可能的最大大小，就很難實(shí)現(xiàn)這種策略。在這種情況下，用戶和應(yīng)用程序都會(huì)多估計(jì)一些文件的大小，以避免分配的空間不夠用。從二級(jí)存儲(chǔ)分配的角度看，這顯然是非常浪費(fèi)的。因此，使用動(dòng)態(tài)分配要好一些，動(dòng)態(tài)分配只有需要時(shí)才給文件分配空間。

文件分配分配給文件的分區(qū)大小。一種極端情況是，分配一個(gè)足夠大的分區(qū)，可以保存整個(gè)文件；另一種極端情況是磁盤(pán)空間一次只分配一塊。因此，在選擇一個(gè)分區(qū)的大小時(shí)，需要折中考慮單個(gè)文件的效率和整個(gè)系統(tǒng)的效率。[WIED87]給出了需要折中考慮的四項(xiàng)內(nèi)容：鄰近空間可以提高性能，特別是對(duì)于Retrieve_next操作，以及面向事務(wù)的操作系統(tǒng)中運(yùn)行的事務(wù)。數(shù)目較多的小分區(qū)會(huì)增加用于管理分配信息的表的大小。使用固定大小的分區(qū)(例如塊)可以簡(jiǎn)化空間的再分配。使用可變大小的分區(qū)或者固定大小的小分區(qū)可以減少由于超額分配而產(chǎn)生的未使用存儲(chǔ)空間的浪費(fèi)。

文件分配當(dāng)然，這幾項(xiàng)內(nèi)容是互相影響的，必須一起考慮。其結(jié)果是可以有兩種選擇?？勺兊拇筮B續(xù)分區(qū)：可以提供較好的性能。大小可變避免了浪費(fèi)，并且使文件分配表比較小，但是這又導(dǎo)致空間很難再次利用。塊：小的固定分區(qū)提供了更大的靈活性，但是為了分配，它們可能需要較大的表或更復(fù)雜的結(jié)構(gòu)。鄰近性不再是主要目標(biāo)，而是根據(jù)需要來(lái)分配塊。每一種選擇都適用于預(yù)分配和動(dòng)態(tài)分配。對(duì)于可變大的大連續(xù)分區(qū)，一個(gè)文件被預(yù)分配給一組連續(xù)的塊，這就消除了對(duì)文件分配表的需求，它所需要的僅僅是指向第一塊的指針和分配的塊數(shù)目。對(duì)于塊，一次性地分配所有分配所需要的所有塊，這意味著該文件的文件分配表間保持固定大小。

策略對(duì)于可變大小的分區(qū)，我們需要考慮空閑空間的碎片問(wèn)題。這個(gè)問(wèn)題在第7章討論主存的劃分時(shí)已經(jīng)討論過(guò)。一些可能的選擇策略如下：首次適配：從空閑塊列表中選擇第一個(gè)未被使用且大小足夠的連續(xù)的塊組。最佳適配：選擇大小足夠的未使用過(guò)的塊中最小的一個(gè)。最近適配：選擇與前面分配給該文件的組塊最為鄰近的組，其目的是為了提高局部性。

ContiguousAllocation連續(xù)分配是指在創(chuàng)建文件時(shí)，給文件分配一組連續(xù)的塊。這是一種使用大小可變分區(qū)的預(yù)分配方案。在文件分配表中每個(gè)文件只需要一個(gè)表項(xiàng)，用于說(shuō)明起始?jí)K和文件的長(zhǎng)度。從單個(gè)順序文件的角度看，連續(xù)分配是最好的。對(duì)于順序處理，可以同時(shí)讀入多個(gè)塊，從而提高了I/O性能。同時(shí)，檢索一個(gè)塊也是非常容易的。例如，如果一個(gè)文件從塊b開(kāi)始，需要文件的第i塊，則這一塊在二級(jí)存儲(chǔ)中的塊位置為b+i-1。連續(xù)分配也存在一些問(wèn)題。首先，會(huì)出現(xiàn)外部碎片，使得很難找到空間大小足夠的連續(xù)塊。因此，它時(shí)常需要執(zhí)行緊縮算法來(lái)釋放磁盤(pán)中的額外空間，如圖12.8所示。其次，因?yàn)槭穷A(yù)分配，它需要在創(chuàng)建文件時(shí)聲明文件的大小。

圖12.7連續(xù)文件分配圖12.8連續(xù)文件分配(緊縮