1两曼、文件和文件系統(tǒng)

文件管理：把所管理的程序和數(shù)據(jù)組織成一系列的文件钠怯，并能進行合理的存儲、使用等操作凭迹。

1 ）基本概念

數(shù)據(jù)項：描述對象某種屬性的字符集罚屋；是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單位。

記錄：一組相關(guān)數(shù)據(jù)項集合嗅绸，描述對象某方面的屬性沿后；

關(guān)鍵字：一個記錄中的一個或幾個數(shù)據(jù)項的集合，用于唯一的標識一個記錄朽砰。

文件：由創(chuàng)建者定義的尖滚、具有文件名的一組相關(guān)元素的集合。

有結(jié)構(gòu)：由相關(guān)記錄組成

無結(jié)構(gòu)：字符流的形式

屬性：類型瞧柔、長度漆弄、物理位置、創(chuàng)建時間

2 ）文件類型

不同的系統(tǒng)對文件的管理方式不同

大多用擴展名標志文件類型造锅，按如下幾種方式分類文件

按用途：系統(tǒng)撼唾、用戶、庫文件

按數(shù)據(jù)形式：源文件哥蔚、目標文件倒谷、可執(zhí)行文件

按存取控制屬性：只執(zhí)行、只讀糙箍、讀寫

按組織和處理方式：普通文件渤愁、目錄文件、特殊（設(shè)備）文件

3）文件系統(tǒng)模型

4）文件操作

操作系統(tǒng)提供哪些文件操作深夯？

u最基本的操作

u創(chuàng)建/刪除文件：分空間抖格，形成FCB及目錄（名，地址）

u讀咕晋、寫：按名檢索目錄雹拄，找到文件地址，開始讀掌呜、寫

u設(shè)置文件讀寫位置滓玖，實現(xiàn)隨機存取（尤其適用于記錄文件）

u還需要：“打開”與“關(guān)閉”：

? 文件讀/寫操作

= 檢索 + 讀/寫质蕉。

p每次讀寫前都要重復(fù)檢索增大開銷势篡。所以為了方便對同一文件的多次讀寫损姜，一次檢索到文件后就在內(nèi)存中記錄其位置，避免重復(fù)檢索殊霞。被記錄下位置的文件就是“打開”文件摧阅；

p不需要再操作文件時，通過“關(guān)閉”這個系統(tǒng)調(diào)用關(guān)閉文件——即從打開文件表上刪除其路徑信息即可绷蹲。

u其他操作：改名棒卷、改所屬用戶、改訪問權(quán)限等屬性的操作祝钢。

2比规、文件的邏輯結(jié)構(gòu)

u文件系統(tǒng)設(shè)計的關(guān)鍵要素：

如何構(gòu)成一個文件，以及如何存儲在外存拦英。

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

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

structure：按用戶觀點如何組織數(shù)據(jù)蜒什；又稱文件組織file organization

p基本要求：檢索速度高、方便修改疤估、降低存儲空間費用（不連續(xù)）

u文件的物理結(jié)構(gòu)：根據(jù)外存上的物理塊的分配機制灾常，記錄文件外存的存儲結(jié)構(gòu)。用戶感知不到的铃拇。

1）文件邏輯結(jié)構(gòu)的類型

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

①定長記錄

②變長記錄

如何組織記錄：

l順序文件钞瀑。系統(tǒng)需按該類型記錄“長度”，通常定長慷荔。

l索引文件雕什。系統(tǒng)需為文件建立索引表。

l索引順序文件显晶。建索引表贷岸，記錄每組記錄的第一個記錄位置。

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

p字節(jié)為單位磷雇，利用讀寫指針依次訪問偿警。

p系統(tǒng)對該類文件不需格式處理。

①順序文件

兩種記錄排列方式

串結(jié)構(gòu)：按記錄形成的時間順序串行排序倦春。記錄順序與關(guān)鍵字無關(guān)户敬；

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

檢索方法：

從頭檢索睁本，順序查找要找的記錄，定長的計算相對快忠怖。

順序結(jié)構(gòu)呢堰，可用折半查找、插值查找凡泣、跳步查找等算法提高效率

具體的尋址過程：

第i條記錄地址（定長） ：

? ? 讀寫指針 + 記錄長度： ptr + i*L

第i條記錄地址（變長） ：

? ? 掃描或讀取前面0~i-1條記錄

第i條記錄地址（變長）

順序結(jié)構(gòu)記錄按關(guān)鍵字排序枉疼，可按關(guān)鍵字檢索

定長：結(jié)合折半查找算法等提高檢索速度

變長：從第1個記錄開始順序掃描皮假，直到掃描到要檢索的關(guān)鍵字標識的記錄（例如：數(shù)據(jù)庫、文件系統(tǒng)的基于文件名排序的目錄檢索）

順序文件的優(yōu)缺點：

不方便隨機存取某條記錄骂维，但適用批量存取的場合惹资。

適合磁帶等特殊介質(zhì)。

單記錄的查找航闺、修改等交互性差褪测；增減不方便（改進辦法：把增刪改的記錄登記在一個事務(wù)文件中，在某段時間間隔后再與原文件合并更新）潦刃。

②索引文件

為了方便單個記錄的隨機存取侮措，為文件建立一個索引表，記錄每項記錄在文件的邏輯地址及記錄長度乖杠；該索引表按關(guān)鍵字排序分扎，。

索引表內(nèi)容：

索引號胧洒、長度畏吓、記錄地址指針

檢索效率

索引表本身即是個按記錄鍵排序的定長順序文件，所以能利用算法提高索引表檢索速度

③索引順序文件

既要方便卫漫，又要降低開銷

本方式是最常見的一種邏輯文件形式庵佣。

將順序文件的所有記錄分組

還是建立索引表，但每個表項記錄的是每組第1條記錄的鍵值和地址汛兜。

組內(nèi)記錄仍按順序方式檢索和使用巴粪。

檢索一條記錄的過程：

先計算記錄是在第幾組，然后再檢索索引確定組在哪里后粥谬，在組內(nèi)順序查找肛根。

可利用多級索引，進一步提高檢索效率漏策。

④直接文件

3派哲、外存分配方式

目標：有效利用外存空間，提高文件訪問速度

常用三種方式：

連續(xù)分配

鏈接分配（不連續(xù)）

索引分配

通常一個系統(tǒng)中僅采用一種方式

采用的磁盤分配方式?jīng)Q定了文件的“物理結(jié)構(gòu)”

順序結(jié)構(gòu)掺喻；鏈接式結(jié)構(gòu)芭届；索引式結(jié)構(gòu)。

注意與邏輯結(jié)構(gòu)名類似但不是一回事感耙。

缺點：

會產(chǎn)生外存碎片褂乍。可緊湊法彌補即硼，但需要額外的空間逃片，和內(nèi)存緊湊相比更花時間。

創(chuàng)建文件時要給出文件大兄凰帧褥实；存儲空間利用率不高呀狼，不利于文件的動態(tài)增加和修改；

適用于變化不大順序訪問的文件损离，在流行的UNIX系統(tǒng)中仍保留了連續(xù)文件結(jié)構(gòu)哥艇。如對換區(qū)

2）鏈接分配

可以為每一個文件分配一組不相鄰的盤塊。

設(shè)置鏈接指針僻澎，將同屬于一個文件的多個離散盤塊鏈接成一個鏈表她奥，這樣形成的文件稱為鏈接文件。會有鏈接成本怎棱。

FAT 與 NTFS 技術(shù)

早期MS-DOS：12位的FAT12文件系統(tǒng)

Windows95哩俭、98：升級到FAT32

Windows NT后：NTFS

? ? 物理磁盤分邏輯卷（分區(qū)），每卷都有一個單獨區(qū)域存放自己的文件系統(tǒng)目錄和FAT表拳恋。

FAT12

表項12位凡资。能支持的硬盤容量僅為8M。

2^12(個)*512B*4（分區(qū)數(shù)）=2^23B=8M

磁盤容量不斷增大谬运，可將若干盤塊組為一簇隙赁。以簇為單位分配空間

FAT表記錄簇號，表項數(shù)量減少梆暖，一定程度上提高了檢索速度伞访，減少了指針開銷，

但該改進有限轰驳，且會形成簇內(nèi)碎片厚掷。12位的格式對磁盤容量仍有很大限制

FAT16

增加FAT表的項數(shù)，16位可管理的盤容量為

2^16*64*512B(一簇含64個盤塊)=2048M

若磁盤容量為8G级解，則每簇大小達到128K（8G/2^16）,簇內(nèi)碎片最大會到128K冒黑。浪費嚴重。

FAT32

簇不能太大勤哗，只能繼續(xù)增加表項位數(shù)抡爹，以記錄更多數(shù)量

FAT32規(guī)定每簇4KB(即8個512B的盤塊），該格式能管理的單個最大磁盤空間為2^32*4KB=2TB芒划。

簇大小合適冬竟，空間利用率提高；但分配表的擴大使運行速度相對慢了民逼；可支持長文件名泵殴；有最小空間管理限制，卷必須大于512M缴挖，單個文件長度不能大于4G袋狞，不能向下兼容。

NTFS

New technology file system

采用64位磁盤地址映屋，理論上支持2^64字節(jié)的磁盤分區(qū)苟鸯；

支持長文件名；

系統(tǒng)糾容錯功能

提供數(shù)據(jù)一致性棚点、文件加密早处、壓縮等功能

磁盤組織

以簇為單位分配回收、但不規(guī)定盤塊大小

磁盤格式化時確定卷的簇大刑蔽觥（物理磁盤扇區(qū)的整數(shù)倍）砌梆，512M以內(nèi)的小磁盤默認簇大小為512B，1G的默認大小為1KB贬循。咸包。。大多數(shù)情況是4KB

卷上簇編號為LCN杖虾，用戶用到的簇順序編成用戶虛擬簇號VCN烂瘫，NTFS可進行VCN到LCN的映射

文件組織

以卷為單位，將卷的所有文件信息奇适、目錄信息坟比、可用未分配空間記錄在主控文件表MFT中。

每個文件的信息對應(yīng)一行嚷往，固定大小1KB葛账，稱為元數(shù)據(jù)

文件屬性信息、文件數(shù)據(jù)較少時就直接寫在MFT中皮仁；較多超出1KB時籍琳，記錄存放這些信息的簇地址指針。

兼容性上也有不足

3）索引分配

鏈接的不足

順序檢索的時間成本：不能支持高效的盤塊直接存取贷祈。要對一個文件進行直接存取巩割，仍需在FAT中順序的查找許多盤塊號。

鏈接信息的空間成本：FAT需占用較大的內(nèi)存空間付燥。當(dāng)磁盤容量較大時储藐，F(xiàn)AT可能要占用數(shù)MB以上的內(nèi)存空間。這是令人難以忍受的

改進：

系統(tǒng)運行時只涉及部分文件莺匠，F(xiàn)AT表無需全部調(diào)入內(nèi)存

每個文件單獨建索引表（物理盤塊索引）挠锥，記錄所有分配給它的盤塊號；

建立文件時勋颖，便分配一定的外存空間用于存放文件盤塊索引表信息嗦嗡；

1 單級

2 多級

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

多種索引方式相結(jié)合，以UNIX system V的索引結(jié)點為例：

一個索引結(jié)點定義為13個地址項：iaddr（0）~iaddr（12）饭玲，總的來說分為兩種：直接地址侥祭、間接地址

iaddr（0）~iaddr（9）存放直接地址，即存文件數(shù)據(jù)的盤塊號；

iaddr（10）存放單級索引的索引盤塊號矮冬；

剩余的用于文件較大時存放多級索引數(shù)據(jù)谈宛。

iaddr（11）存放二級索引的主索引盤塊號

iaddr（12）存放三級索引的主索引盤塊號

3）成組鏈接法

大型文件系統(tǒng)，空閑表或空閑鏈表太長不方便管理操作胎署。

UNIX系統(tǒng)中采用成組鏈接法吆录，這是將兩種方法結(jié)合而形成的一種空閑盤塊管理方法。

中心思想：

所有盤塊按規(guī)定大小劃分為組琼牧；

組間建立鏈接恢筝；

組內(nèi)的盤塊借助一個系統(tǒng)棧可快速處理巨坊，且支持離散分配回收撬槽。

成組鏈接法

鏈表長度上限固定

組內(nèi)的盤塊借助一個系統(tǒng)棧可快速處理趾撵，且分配回收比較簡單侄柔。

支持離散分配回收。

空閑盤塊的組織

空閑盤塊號棧鼓寺。

用來存放當(dāng)前可用的一組空閑盤塊的盤塊號（最多含100個號）

棧中尚有的空閑盤塊號數(shù)N勋拟。

（N兼具棧頂指針用。棧底為S.free(0)妈候，棧滿時棧頂?shù)竭_S.free(99)敢靡，N=100，表示有100個盤塊供使用苦银。

空閑盤塊的分配與回收

分配盤塊時啸胧，須調(diào)用分配過程來完成。

先檢查空閑盤塊號棧是否上鎖幔虏，如沒有纺念，便從棧頂取出一空閑盤塊號，將與之對應(yīng)的盤塊分配給用戶想括，然后將棧頂指針下移一格陷谱。

若該盤塊號已是棧底，即S.free(0)瑟蜈，到達當(dāng)前棧中最后一個可供分配的盤塊號烟逊。

讀取該盤塊號所對應(yīng)的盤塊中的信息：即下一組可用的盤塊號入棧。

原棧底盤塊分配出去铺根。修改棧中的空閑盤塊數(shù)宪躯。

回收

回收盤塊號記入棧頂，空閑數(shù)N加1

N達到100時位迂，若再回收一塊访雪，則將該100條信息填寫入新回收塊详瑞。

文件控制塊—FCB

u為了能對一個文件進行正確的存取，必須為文件設(shè)置用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)臣缀，稱之為“文件控制塊”（FCB）

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

p記錄文件名及其存放地址坝橡、文件的說明和控制信息。（是誰肝陪？在哪里驳庭？什么權(quán)刑顺？）

p文件管理程序借助于文件控制塊中的信息對文件施以各種操作氯窍。

? 把文件控制塊的有序集合稱為文件目錄，即一個文件控制塊就是一個目錄項蹲堂。通常一個文件目錄也被看作是一個文件狼讨，稱為目錄文件

5、目錄管理

u對文件實施有效的管理柒竞，必須對它們加以妥善組織政供，主要是兩大操作：

1.基本信息記錄(FCB,目錄項)

2.方便檢索、管理（目錄操作）

u目錄管理的要求如下：

o實現(xiàn)“按名存取”朽基；（最基本功能）

o提高對目錄的檢索速度布隔；

o文件共享；

o允許文件重名稼虎。

1）FCB內(nèi)容

u在文件控制塊中衅檀，通常含有以下三類信息。

1.基本信息類

o包括文件名霎俩，文件物理位置哀军，文件邏輯結(jié)構(gòu)，文件的物理結(jié)構(gòu)打却。

2.存取控制信息類

o包括文件主的存取權(quán)限杉适，核準用戶的存取權(quán)限和一般用戶的存取權(quán)限。

3.使用信息類

o建立日期和時間柳击、文件上次修改的日期和時間

o當(dāng)前使用信息：打開該文件的進程數(shù)猿推、是否被進程鎖住、是否已修改等捌肴。

關(guān)于文件檢索的速度：

文件FCB組成的“目錄”文件存放于磁盤蹬叭；需要時，要從磁盤將目錄內(nèi)容調(diào)入內(nèi)存進行檢索和使用哭靖。

如果目錄占用5個盤塊具垫，則至多需啟動5次磁頭讀寫，如何提高檢索速度试幽？

2）索引結(jié)點

索引結(jié)點的引入

文件目錄占越大量的盤塊筝蚕，需進行的磁盤讀寫開銷越大卦碾。減少實際檢索的信息量就減少移動磁頭的開銷，提高速度起宽；

目錄一般是按名檢索洲胖。而直到找到正確文件前，只關(guān)心文件名坯沪，不需要其它的文件描述信息绿映，目錄中這部分內(nèi)容的調(diào)入不是必須的。

所以：將文件名腐晾、文件具體信息分開叉弦，使文件描述信息單獨形成一個索引結(jié)點。

索引結(jié)點由外存到內(nèi)存的過程中有不同的形式：

磁盤索引結(jié)點

存放在磁盤上的索引結(jié)點藻糖。主要包括以下內(nèi)容：文件主標識符淹冰、文件類型、文件存取權(quán)限巨柒、文件物理地址樱拴、文件長度、文件連接計數(shù)洋满、文件存取時間晶乔。

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

文件被打開后，將磁盤索引結(jié)點拷貝到內(nèi)存索引結(jié)點中以便使用牺勾。比磁盤索引結(jié)點增加了以下內(nèi)容：索引結(jié)點編號正罢、狀態(tài)、訪問計數(shù)禽最、文件所屬文件系統(tǒng)的邏輯設(shè)備號腺怯、鏈接指針。

３） 目錄結(jié)構(gòu)

目錄結(jié)構(gòu)的組織川无，關(guān)系到文件系統(tǒng)的存取速度呛占，也關(guān)系到文件的共享性和安全性。

組織好文件的目錄懦趋，是設(shè)計好文件系統(tǒng)的重要環(huán)節(jié)晾虑。

目前常用的目錄結(jié)構(gòu)形式有

單級目錄

兩級目錄

多級目錄

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

最簡單的目錄結(jié)構(gòu)。

整個文件系統(tǒng)中只建立一張目錄表仅叫，每個文件一個目錄項帜篇，含有文件相關(guān)信息。

每建立一個新文件：

先檢索所有的目錄項诫咱，保證文件名唯一笙隙。

獲得一空白目錄項，填入相關(guān)信息坎缭，修改狀態(tài)位（表明每個目錄項是否空閑）竟痰。

刪除一個文件：

找到對應(yīng)目錄項签钩，回收文件所占用空間

清除目錄項

優(yōu)點：簡單、能實現(xiàn)目錄管理的基本功能——按名存取坏快。

缺點：

文件檢索時需搜遍整個目錄文件铅檩，范圍大速度慢。

不允許重名莽鸿。名字過多難于記憶昧旨，對于多用戶環(huán)境重名難以避免。

不便于實現(xiàn)文件共享（因為不能重名祥得，不同用戶使用的共享文件必須不同名字兔沃，標識哪些用戶共享文件也不方便），一般只適用單機環(huán)境啃沪。

②兩級目錄結(jié)構(gòu)（ Two-Level Directory ）

為每一個用戶建立一個單獨的用戶文件目錄UFD粘拾，UFD由用戶所有文件的文件控制塊組成窄锅。

系統(tǒng)建立一個主文件目錄MFD创千， MFD中每個用戶目錄文件都占有一個目錄項，其中包括用戶名和指向UFD的指針入偷。

基本克服了單級目錄的缺點追驴，并具有以下優(yōu)點：

提高了檢索目錄的速度。

在不同的目錄中可重名疏之。

不同用戶還可以使用相同/不同的文件名來訪問系統(tǒng)中的同一個共享文件殿雪。

不提供子目錄操作，還不方便锋爪；各用戶之間被完全隔離的話用戶訪問其他用戶文件時丙曙，不方便合作。

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

適用于較大的文件系統(tǒng)管理其骄。又稱為樹狀目錄(tree-like)

在文件數(shù)目較多時亏镰，便于系統(tǒng)和用戶將文件分散管理。

層次結(jié)構(gòu)更清晰拯爽、提供更靈活的權(quán)限管理等

但目錄級別太多時也會增加路徑檢索層次索抓，增加磁盤訪問時間。

相關(guān)名詞：

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

主目錄稱為根目錄毯炮，數(shù)據(jù)文件為樹葉逼肯，其它目錄為結(jié)點。多級目錄縮小檢索范圍提高檢索速度和文件系統(tǒng)的性能桃煎。

路徑名

從根目錄到任何數(shù)據(jù)文件都只有一條唯一通路篮幢。目錄文件名和數(shù)據(jù)文件名依次用“/”連接起來，即構(gòu)成數(shù)據(jù)文件的路徑名为迈。

當(dāng)前目錄

為每個進程設(shè)置一個“當(dāng)前目錄”三椿，又稱“工作目錄”奈揍。

從當(dāng)前目錄開始，逐級經(jīng)過中間的目錄文件赋续，最后達到要訪問的數(shù)據(jù)文件男翰。這一路徑上的目錄和數(shù)據(jù)文件名用“/”連接成路徑名，稱為相對路徑名纽乱。

從根開始的路徑名稱為絕對路徑名

4）目錄查詢技術(shù)

用戶要訪問一個已存文件

目錄數(shù)據(jù)調(diào)入內(nèi)存蛾绎；

按名檢索：系統(tǒng)利用提供的文件名對目錄(根據(jù)目錄層次，需要做的檢索次數(shù)也不同)進行查詢

找該文件控制塊

讀FCB或?qū)?yīng)索引結(jié)點鸦列；

從文件物理地址換算出文件在磁盤上的物理位置租冠；

最后通過磁盤驅(qū)動程序，將所需文件讀入內(nèi)存薯嗤。

目錄查詢方式：線性檢索法和Hash方法顽爹。

線性檢索法

又稱為順序檢索法。

單級目錄中

用戶提供文件名骆姐，順序查找文件目錄镜粤。

樹型目錄中

用戶提供路徑名，如/user/ast/mbox

對多級目錄進行逐層查找玻褪。