操作系統(tǒng)第九章文件系統(tǒng)

1、第九章 文件系統(tǒng)9.1 文件系統(tǒng)的概念 文件是具有文件名的且在邏輯上具有完整意義的信息的集合。 文件系統(tǒng)是OS中負(fù)責(zé)管理和存取文件信息的軟件機(jī)構(gòu)，它由管理文件所需的數(shù)據(jù)結(jié)構(gòu)（如文件控制塊、目錄表、存儲(chǔ)分配表）和相應(yīng)的管理軟件，以及訪問文件的一組操作所組成。文件系統(tǒng)的功能：1. 用戶可以對(duì)文件進(jìn)行操作，如：創(chuàng)建、刪除、讀寫文件等；2. 可以共享彼此的文件，如鏈接；3. 提供存取控制，如R、W、X等權(quán)限；4. 實(shí)現(xiàn)輔存空間的自動(dòng)管理；5. 按文件名訪問；6. 提供后備與復(fù)原能力，如回收站；7. 保密功能，如文件口令、文件加密；8. 界面友好。9.2 文件的邏輯組織與存取方法一、文件的邏輯結(jié)構(gòu) 這是

2、從用戶觀點(diǎn)出發(fā)，所觀察到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，它獨(dú)立于物理特性。一、文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)可分為兩種形式：1. 有結(jié)構(gòu)的文件-記錄式文件2. 無結(jié)構(gòu)的文件-流式文件1、流式文件 流式文件是相關(guān)的有序字符的集合。文件的長度即為所含字符數(shù)，如C語言的源程序、寫字板的.TXT文件等。2.記錄式文件 記錄式文件由一組相關(guān)記錄組成。記錄的長度可分為定長和不定長兩類。 定長記錄文件 指文件中所有記錄的長度都是相同的，如數(shù)據(jù)塊中的表文件。 不定長記錄文件 指文件中各記錄的長度不盡相同。二、存取方法1.順序存取：如磁帶文件2.隨機(jī)存?。喝绱疟P文件9.3文件的物理結(jié)構(gòu)文件的物理

3、結(jié)構(gòu) 文件的物理結(jié)構(gòu)是指文件在外存上的存儲(chǔ)組織形式，它與存儲(chǔ)介質(zhì)的存儲(chǔ)特性有關(guān)。存儲(chǔ)介質(zhì)通常劃分為大小相同的物理塊，物理塊是分配和存儲(chǔ)信息的基本單位，如磁盤塊的大小是512B的整數(shù)倍（1KB/塊，4KB/塊），為便于管理，一般也把文件信息劃分為與物理塊大小相等的邏輯塊。例如：當(dāng)磁盤塊大小為512B，某文件長度為1034B，則需要3個(gè)物理塊，第3塊的利用率為10B/512B。當(dāng)磁盤塊大小為1KB/塊時(shí)，則需要2個(gè)物理塊，第2塊的利用率為10B/1024B。常見的文件物理結(jié)構(gòu)有：1. 連續(xù)文件2. 串聯(lián)文件3. 索引文件9.3.1 連續(xù)文件連續(xù)文件它是將文件信息依次存放在外存連續(xù)的物理塊中。例如：

4、某文件A由3個(gè)邏輯塊組成，第一個(gè)邏輯塊對(duì)應(yīng)的物理塊號(hào)為100，則連續(xù)文件的物理結(jié)構(gòu)為：文件目錄文件目錄：A 3 100：r0r1r2 物理塊號(hào)：100 101 102特點(diǎn)：順序存取速度快，但文件存儲(chǔ)要求連續(xù)的存儲(chǔ)空間，會(huì)產(chǎn)生碎片，同時(shí)也不利于文件的動(dòng)態(tài)擴(kuò)充。9.3.2串聯(lián)文件串聯(lián)文件文件存儲(chǔ)的物理塊不必連續(xù)，在每個(gè)物理塊的最后一個(gè)字做為指針，指向下一個(gè)物理塊的位置。例如：某文件B有3個(gè)邏輯塊，分別分配到100,150,57號(hào)物理塊中，串聯(lián)文件的結(jié)構(gòu)為：文件目錄文件目錄：B 3 100：r0150r157r2 物理塊號(hào)：100 150 57特點(diǎn)：沒有外存碎片，動(dòng)態(tài)增刪比較方便。但串聯(lián)文件只能按照

5、文件的指針順序訪問，因而查找效率較低。2.文件映照結(jié)構(gòu)（文件分配表文件映照結(jié)構(gòu)（文件分配表FAT）引導(dǎo)塊引導(dǎo)塊文件目錄區(qū)文件目錄區(qū)文件映照表文件映照表（文件分配表）（文件分配表）數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)文件系統(tǒng)結(jié)構(gòu)（磁盤） 系統(tǒng)有文件映照?qǐng)D，圖中每個(gè)表項(xiàng)用來記錄磁盤塊號(hào)（勾鏈字）。 每個(gè)文件的文件目錄項(xiàng)中，用于描述文件物理結(jié)構(gòu)的表項(xiàng)指向文件映照?qǐng)D中的某個(gè)位置，其內(nèi)容為該文件的第一塊的塊號(hào)，其后的各塊在文件映照?qǐng)D中依次勾鏈，文件的最后一塊用尾標(biāo)記表示。例如：文件C占用了第3,6,4,8塊，文件映照?qǐng)D結(jié)構(gòu)為：文件目錄文件目錄：C 4塊 3：文件映照?qǐng)D文件映照?qǐng)D684：磁盤塊號(hào) 012345678：特點(diǎn)：存放鏈

6、指針需要一定的存儲(chǔ)空間，文件映照?qǐng)D一般比較大，不宜保存在主存。在最壞情況下，可能要把整個(gè)文件映照?qǐng)D全部讀入主存，才能找到文件在磁盤中的所有物理塊，所以，把文件所占的磁盤空間盡量靠近是有利的，而不應(yīng)將文件散布在整個(gè)磁盤上（如定期做碎片整理工作）。例：假定1KB/塊，對(duì)于120GB的硬盤，采用FAT32結(jié)構(gòu)（一個(gè)磁盤塊號(hào)32位），求文件映照?qǐng)D的大??？解：磁盤塊數(shù)=120GB/1KB=120M 文件映照?qǐng)D的大小=120MX32bit/8=480MB9.3.4索引文件索引文件為了能隨機(jī)的訪問文件的任何一部分，可以采用索引文件結(jié)構(gòu)。每個(gè)文件文件需建立一個(gè)索引表，索引表中的每個(gè)表項(xiàng)為文件的邏輯塊號(hào)和與之對(duì)

7、應(yīng)的物理塊號(hào)。例如：某文件D分別存放在物理塊23,19,26,29中，該文件的索引結(jié)構(gòu)為：文件目錄文件目錄：D 4 索引表指針：邏輯塊號(hào)邏輯塊號(hào)物理塊號(hào)物理塊號(hào)023119226329R0R1R2R3文件D索引表（磁盤）塊號(hào)19：23：26：29 索引文件在存儲(chǔ)區(qū)占兩個(gè)區(qū)，索引區(qū)和數(shù)據(jù)區(qū)。要訪問索引文件需要兩步操作：1. 查索引表，由邏輯塊號(hào)得物理塊號(hào)；2. 由物理塊號(hào)訪外存獲得所要求的信息。特點(diǎn)：可以進(jìn)行隨機(jī)訪問，易于進(jìn)行文件的增刪。但索引表的使用增加了存儲(chǔ)空間的開銷，文件操作需要兩次訪問外存。例：P263 UNIX System V 的多重索引結(jié)構(gòu)，每個(gè)文件都有自己的磁盤地址表。磁盤塊號(hào)磁

8、盤塊號(hào)：磁盤塊號(hào)一次間址二次間址三次間址磁盤地址表addr0addr9addr10addr11addr12datadata直接尋址假設(shè)磁盤塊為1KB，盤塊號(hào)為4B，則直接尋址的文件大小=10 1KB=10KB1KB1KB一次間址0#(4B)：:255#(4B)datadata磁盤塊（1KB)一次間址的文件大小=1KB (1KB/4)=256KB1KB1KB二次間址0#(4B)：:255#(4B)0#(4B)：:255#(4B)0#(4B)：:255#(4B)datadatadatadata：磁盤塊（1KB)磁盤塊（1KB)磁盤塊（1KB)1KB1KB1KB1KB二次間址的文件大小=1KB (1

9、KB/4) (1KB/4)=1GB/16三次間址的文件大小=1KB (1KB/4) (1KB/4) (1KB/4)= 1TB/64可以存儲(chǔ)文件的最大長度=直接尋址一次間址二次間址三次間址思考：如何提高存儲(chǔ)文件的最大長度？系統(tǒng)安裝時(shí)增加磁盤塊的大小，如4KB,8KB或16KB。10.在某系統(tǒng)中，一個(gè)目錄項(xiàng)可以存儲(chǔ)至多13個(gè)磁盤塊地址。前10個(gè)地址指向文件的前10塊，第11個(gè)地址指向一個(gè)一次間址塊，第12個(gè)地址指向一個(gè)二次間址塊，第13個(gè)地址指向一個(gè)三次間址塊。假設(shè)每個(gè)間址塊可以容納256個(gè)磁盤塊地址指針，一個(gè)磁盤塊的大小為1KB，那么一個(gè)文件最多可以達(dá)到多大？解：（102562562+2563）

10、1KB例：在UNIX System V中，如果盤塊的大小為1KB，每個(gè)盤塊號(hào)占4B，那么一個(gè)進(jìn)程要訪問偏移量263168B處的數(shù)據(jù)時(shí)，要經(jīng)過幾次間址？解：邏輯盤塊號(hào)=int(263168/1024)=257塊內(nèi)偏移量=263168 mod 1024 =0 1025710+256只需要經(jīng)過一次間接尋址。9.4文件存儲(chǔ)空間的管理 文件存儲(chǔ)空間的管理實(shí)質(zhì)上是空閑塊的組織與管理問題，它包括空閑塊的組織、分配和回收等幾個(gè)問題。例：某磁盤空間使用情況如下：012345678910111213141516171819202122239.4.1空閑文件目錄（空閑表）思想：外存上一片連續(xù)的空閑區(qū)可以看成是被一個(gè)

11、空閑文件所占用。系統(tǒng)為所有的空閑文件單獨(dú)建立一個(gè)目錄，表目中的內(nèi)容包括第一個(gè)空閑塊的地址和空閑塊的個(gè)數(shù)?？臻e文件目錄空閑文件目錄序號(hào)第一個(gè)空閑塊號(hào)空閑塊個(gè)數(shù)10225231234173523 空閑文件目錄方法適用于連續(xù)文件的分配和回收。 空閑文件目錄的分配和回收與內(nèi)存管理中的分區(qū)存儲(chǔ)管理的空閑塊的分配和回收類似。 缺點(diǎn)：當(dāng)空閑塊較碎時(shí)，會(huì)造成表很大，從而影響文件分配時(shí)查找表的速度；另外還存在碎片問題。9.4.2空閑塊鏈空閑塊鏈思想：把文件存儲(chǔ)設(shè)備上所有的空閑塊鏈接在一起，當(dāng)申請(qǐng)者需要空閑塊時(shí)，分配程序從鏈頭開始摘取所需要的空閑塊，然后調(diào)整鏈?zhǔn)字羔?。?dāng)回收空閑塊時(shí)，把釋放的空閑塊插入鏈中。針。0

12、1234567891011121314151617181920212223方法一：每個(gè)空閑塊中包含指向下一空閑塊的指針。特點(diǎn)：每申請(qǐng)一塊都要讀出空閑塊并取得指針，申請(qǐng)多次時(shí)需多次讀盤。01234567891011121314151617181920212223磁盤0head方法二：將空閑塊號(hào)組成空閑塊鏈每個(gè)結(jié)點(diǎn)的內(nèi)容包括：當(dāng)前（或下一個(gè)）空閑塊號(hào)和指向下一個(gè)結(jié)點(diǎn)的指針。01234567891011121314151617181920212223head156121314017181923假如一個(gè)盤塊只能訪7個(gè)空閑塊號(hào)，那么插入或刪除1個(gè)結(jié)點(diǎn)就要進(jìn)行“拉鏈”操作。9.4.3位示圖位示圖思想：每個(gè)

13、磁盤塊都對(duì)應(yīng)1bit，“1”已分配，“0”未分配。寫出例題中的位示圖：0011,1001,1111,0001,1000,1110 利用位示圖來進(jìn)行空閑塊分配時(shí)，只需查找圖中的“0”位，并將其置為“1”位。反之，回收時(shí)，只需把相應(yīng)的位由“1”改為“0”即可。根據(jù)位示圖中的位置經(jīng)過簡單的換算就可以得到對(duì)應(yīng)的磁盤塊地址。01234567891011121314151617181920212223例題：一個(gè)位示圖的大小=磁盤容量/磁盤塊大小/8（字節(jié)）例如：對(duì)應(yīng)80GB的磁盤，磁盤塊大小為1KB，則位示圖的大小=80GB/1KB/8=10MB思考：如何減少位示圖的大??？增加磁盤塊的大小。P270 9.

14、8.6 UNIX空閑塊的管理空閑塊的管理成組鏈接法成組鏈接法UNIX的文件系統(tǒng)（文件卷）由四個(gè)部分組成：引導(dǎo)塊引導(dǎo)塊管理塊管理塊索引節(jié)點(diǎn)區(qū)索引節(jié)點(diǎn)區(qū)數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)管理塊(也稱超級(jí)塊)，它記載著文件卷的使用情況： Struct fifsys : int s_nfree; /*直接管理的空閑塊數(shù)*/ int s_free100; /*空閑塊號(hào)棧*/ : 成組鏈接法成組鏈接法思想：從尾向前，空閑塊每100塊一組，最后一組99塊，其余的就是直接管理的盤塊號(hào)和盤塊數(shù)，放入S_free 和S_nfree中。每一組的最后一塊作為索引表，用來登記下一組100塊的盤塊號(hào)和盤塊數(shù)。例如：空閑塊數(shù)為376，最后一組9

15、9塊，第二、三組100塊，最前面一組為77塊。如圖所示：Fifsys(內(nèi)存內(nèi)存)：S_nfree=77S_free0:S_free76S_nfree=100S_free0: （空閑塊號(hào)）S_free99S_nfree=100S_free0: （空閑塊號(hào)）S_free99S_nfree=99S_free0=S_free1: （空閑塊號(hào)）S_free99空閑塊76空閑塊99空閑塊99空閑塊99空閑塊1空閑塊鏈空閑塊表成組鏈接法中：假設(shè)空閑塊數(shù)為N，那么，組數(shù)=int(N/100)+1直接管理的空閑塊數(shù)=(N mod 100)+11、空閑塊的分配空閑塊的分配 S_nfree; If (S_nfree

16、0) S_freeS_nfree指向的盤塊號(hào)出棧； 分配此空閑塊； If (S_nfree=0)If (S_free0= ) 打印出錯(cuò)信息（“無空閑塊可以分配”）； Return(NULL); else 將S_free0指向的空閑塊盤塊索引表和空閑塊數(shù)讀入內(nèi)存的 S_free100 和S_nfree 中，將間接管理變?yōu)橹苯庸芾恚?分配S_free0 指向的盤塊； 2、空閑塊的釋放空閑塊的釋放 if (S_nfree100) S_freeS_nfree+=釋放盤塊號(hào)； Else/*S_free表已滿*/ 將fifsys中的S_nfree=100及S_free 表的內(nèi)容復(fù)制到釋放 的盤塊中； fi

17、fsys中的S_nfree=1； S_free0 =釋放盤塊號(hào)； 有一個(gè)磁盤組共有10個(gè)記錄面，每個(gè)記錄面上有100個(gè)磁道，每個(gè)磁道上有16個(gè)扇區(qū)。假定分配以扇區(qū)為單位，若使用位示圖管理磁盤空間，問位示圖需要占用多少空間？若空閑文件目錄的每個(gè)表目占用5B，問什么時(shí)候空閑文件目錄大于位示圖？解：位示圖的大小=10100161位=2000B當(dāng)空閑文件目錄中的表目數(shù)2000B/5B=400時(shí)，空閑文件目錄大于位示圖。 9.5文件目錄9.5.1文件目錄及其內(nèi)容1.文件目錄是一張記錄所有文件的名字及其存放地址的目錄表，表中還應(yīng)包括文件的說明和控制方面的信息。文件控制塊（FCB）的有序集合即為文件目錄。例

18、1：MSDOS的FCB內(nèi)容：MSDOS的文件系統(tǒng)（文件卷）由四個(gè)部分組成：引導(dǎo)塊引導(dǎo)塊FAT表表文件目錄區(qū)文件目錄區(qū)數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)文件目錄區(qū)文件目錄區(qū)FCB1：FCBn每個(gè)FCB占32B:文件名文件名擴(kuò)展名擴(kuò)展名屬性屬性保留保留時(shí)間時(shí)間日期日期第一塊第一塊塊號(hào)塊號(hào)長度長度指向FAT表 8B 3B 1B 10B 2B 2B 2B 4B 例2：UNIX的FCB內(nèi)容（索引節(jié)點(diǎn)或i節(jié)點(diǎn)）P260文件所有者標(biāo)識(shí)i_uid, i_gid文件類型i_type文件存取權(quán)限i_mode文件鏈接計(jì)數(shù)i_link文件存取時(shí)間i_time文件長度i_size磁盤地址索引表i_addr13i_uid ,i_gidi_ui

19、d ：文件的所有者號(hào)i_gig：文件所屬組號(hào)i_uidi_gidi_type文件的類型：d 目錄文件- 普通文件（正規(guī)文件） b塊設(shè)備文件 c字符設(shè)備文件 p管道文件文件類型文件類型i_mode系統(tǒng)按用戶、用戶組、其它用戶三類對(duì)文件進(jìn)行保護(hù)，每類都具有R、W、X的存取權(quán)，并且 可以用chmod命令進(jìn)行設(shè)置。默認(rèn)權(quán)限：普通文件：664可執(zhí)行文件：775存取權(quán)限改變文件的存取權(quán)限：i_link初值為1，同一文件系統(tǒng)中每建立一個(gè)硬鏈接，i_link+1;刪除一個(gè)文件時(shí)，i_link減1，當(dāng)i_link=0時(shí)，才能真正刪除該文件。圖1所示鏈接文件和被鏈接的文件具有相同的i節(jié)點(diǎn)號(hào)。圖2所示圖1圖2文件鏈

20、接數(shù)文件存取時(shí)間：i_time包括：i_atime:：最后一次訪問時(shí)間i_mtime：最后一次修改時(shí)間i_ctime：創(chuàng)建時(shí)間文件長度：i_size磁盤地址索引表：i_addr13文件大小文件最后一次修改時(shí)間9.5.2一級(jí)文件目錄 為了實(shí)現(xiàn)“按名存取”的功能，在整個(gè)文件系統(tǒng)中只建立一張目錄表，每個(gè)文件占一項(xiàng)表目，主要由文件名和文件說明信息組成。 一級(jí)目錄結(jié)構(gòu)易于實(shí)現(xiàn)，管理簡單；但當(dāng)系統(tǒng)中文件數(shù)增多時(shí)，查找時(shí)間較長，且易于發(fā)生重名問題。9.5.3二級(jí)文件目錄 將文件目錄分成主文件目錄和用戶文件目錄二級(jí)。1、主文件目錄（MFD）：記錄用戶名及相應(yīng) 用戶目錄所在的儲(chǔ)存位置。2、用戶文件目錄（UFD）

21、登記該用戶的文件 控制塊的信息。例如：wanggaofile1file4file1file2主文件目錄MFDWang的文件目錄UFD gao的文件目錄UFDdatadatadatadata 二級(jí)目錄可以解決重名問題，并可獲得較高的查找速度；但二級(jí)目錄缺乏靈活性，無法反映真實(shí)世界復(fù)雜的文件結(jié)構(gòu)形式。如：一個(gè)用戶不能定義同名文件。9.5.4 多級(jí)文件目錄 也稱樹形目錄結(jié)構(gòu)。在多級(jí)目錄結(jié)構(gòu)中，第一級(jí)目錄稱為根目錄，目錄樹中非葉節(jié)點(diǎn)稱為子目錄，葉節(jié)點(diǎn)為文件。 在多級(jí)目錄中，用戶要訪問某個(gè)文件時(shí)，需要指出訪問路徑。從根目錄出發(fā)的路徑稱為絕對(duì)路徑。從當(dāng)前目錄出發(fā)的路徑稱為相對(duì)路徑。 當(dāng)采用多級(jí)目錄組織后，

22、不同用戶可以給不同文件起相同的名字?？梢园晌募M織的有條有理，非常便于管理 9.5.4 多級(jí)文件目錄 文件目錄的查詢方法：1、線性檢索算法2、哈希檢索算法：即目錄信息存放在一個(gè)哈希表中（沖突）。3、Windows 2000 采用B+樹儲(chǔ)存目錄信息，可以使磁盤訪問次數(shù)減少到最小。9.6共享與安全一、文件共享 是指某一個(gè)或某一部分文件可以讓事先規(guī)定的某些用戶共同使用。例如：基于索引節(jié)點(diǎn)的文件共享二、文件的安全（文件保護(hù)機(jī)制）1.設(shè)置文件的存取權(quán)限2.口令3.加密技術(shù)9.7文件操作與文件備份9.7.1 文件操作文件系統(tǒng)提供一組使用文件的系統(tǒng)調(diào)用。例如：打開文件：打開文件：把該文件的有關(guān)目錄表復(fù)制到主存中約定的區(qū)域，建立用戶和這個(gè)文件的聯(lián)系。關(guān)閉文件：關(guān)閉文件：系統(tǒng)將其在主存中相應(yīng)的目錄表刪去，切斷用戶與該文件的聯(lián)系；若在文件打開期間，該文件做過某種修改，則應(yīng)將其寫回輔存。9.7.2 文件的備份 為了能在軟、硬件失效的意外情況下恢復(fù)文件，保證數(shù)據(jù)的連續(xù)可用性，文件系統(tǒng)應(yīng)當(dāng)提供適當(dāng)?shù)臋C(jī)構(gòu)，以便復(fù)制備份。 建立文件拷貝的基本方法有兩種：一、周期性轉(zhuǎn)儲(chǔ)（全量轉(zhuǎn)儲(chǔ)）二、增量轉(zhuǎn)儲(chǔ)一、周期性轉(zhuǎn)儲(chǔ)（全量轉(zhuǎn)儲(chǔ)） 按固定的時(shí)間周期把外存中所有的