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)隨機存?。ㄓ绕溥m用于記錄文件）

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

? 文件讀/寫操作

= 檢索 + 讀/寫。

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

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)生外存碎片?？删o湊法彌補，但需要額外的空間，和內(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ī)定盤塊大小

磁盤格式化時確定卷的簇大?。ㄎ锢泶疟P扇區(qū)的整數(shù)倍），512M以內(nèi)的小磁盤默認簇大小為512B，1G的默認大小為1KB。。。大多數(shù)情況是4KB

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

文件組織

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

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

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

兼容性上也有不足

3）索引分配

鏈接的不足

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

鏈接信息的空間成本：FAT需占用較大的內(nèi)存空間。當磁盤容量較大時，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)?？煽焖偬幚恚抑С蛛x散分配回收。

成組鏈接法

鏈表長度上限固定

組內(nèi)的盤塊借助一個系統(tǒng)?？煽焖偬幚恚曳峙浠厥毡容^簡單。

支持離散分配回收。

空閑盤塊的組織

空閑盤塊號棧。

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

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

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

空閑盤塊的分配與回收

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

先檢查空閑盤塊號棧是否上鎖，如沒有，便從棧頂取出一空閑盤塊號，將與之對應的盤塊分配給用戶，然后將棧頂指針下移一格。

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

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

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

回收

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

N達到100時，若再回收一塊，則將該100條信息填寫入新回收塊。

文件控制塊—FCB

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

p文件與文件控制塊一一對應

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當前使用信息：打開該文件的進程數(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ō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ù)文件的路徑名。

當前目錄

為每個進程設(shè)置一個“當前目錄”，又稱“工作目錄”。

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

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

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

用戶要訪問一個已存文件

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

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

找該文件控制塊

讀FCB或?qū)饕Y(jié)點；

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

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

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

線性檢索法

又稱為順序檢索法。

單級目錄中

用戶提供文件名，順序查找文件目錄。

樹型目錄中

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

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