文件控制塊—FCB
為了能對一個文件進行正確的存取阁猜，必須為文件設(shè)置用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)，稱之為“文件控制塊”（FCB）
文件與文件控制塊一一對應(yīng)
記錄文件名及其存放地址、文件的說明和控制信息活逆。（是誰审编？在哪里？什么權(quán)次员？）
文件管理程序借助于文件控制塊中的信息對文件施以各種操作败许。
? 把文件控制塊的有序集合稱為文件目錄，即一個文件控制塊就是一個目錄項淑蔚。通常一個文件目錄也被看作是一個文件市殷，稱為目錄文件
目錄管理
u對文件實施有效的管理，必須對它們加以妥善組織刹衫，主要是兩大操作：
1.基本信息記錄(FCB,目錄項)
2.方便檢索醋寝、管理（目錄操作）
目錄管理的要求如下：
實現(xiàn)“按名存取”；（最基本功能）
提高對目錄的檢索速度带迟；
文件共享音羞；
允許文件重名。
1）FCB內(nèi)容
在文件控制塊中仓犬，通常含有以下三類信息嗅绰。
基本信息類
包括文件名，文件物理位置搀继，文件邏輯結(jié)構(gòu)窘面，文件的物理結(jié)構(gòu)。
存取控制信息類
包括文件主的存取權(quán)限叽躯，核準(zhǔn)用戶的存取權(quán)限和一般用戶的存取權(quán)限财边。
使用信息類
建立日期和時間、文件上次修改的日期和時間
當(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)容：文件主標(biāo)識符措拇、文件類型我纪、文件存取權(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)文件共享（因為不能重名，不同用戶使用的共享文件必須不同名字嵌纲，標(biāo)識哪些用戶共享文件也不方便）俘枫，一般只適用單機環(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
對多級目錄進行逐層查找。
1舰褪、文件和文件系統(tǒng)
文件管理：把所管理的程序和數(shù)據(jù)組織成一系列的文件皆疹，并能進行合理的存儲、使用等操作占拍。
1 ）基本概念
數(shù)據(jù)項：描述對象某種屬性的字符集略就；是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單位。
記錄：一組相關(guān)數(shù)據(jù)項集合晃酒，描述對象某方面的屬性表牢；
關(guān)鍵字：一個記錄中的一個或幾個數(shù)據(jù)項的集合，用于唯一的標(biāo)識一個記錄掖疮。
文件：由創(chuàng)建者定義的初茶、具有文件名的一組相關(guān)元素的集合。
有結(jié)構(gòu)：由相關(guān)記錄組成
無結(jié)構(gòu)：字符流的形式
屬性：類型浊闪、長度恼布、物理位置、創(chuàng)建時間
2 ）文件類型
不同的系統(tǒng)對文件的管理方式不同
大多用擴展名標(biāo)志文件類型搁宾，按如下幾種方式分類文件
按用途：系統(tǒng)折汞、用戶、庫文件
按數(shù)據(jù)形式：源文件盖腿、目標(biāo)文件爽待、可執(zhí)行文件
按存取控制屬性：只執(zhí)行损同、只讀、讀寫
按組織和處理方式：普通文件鸟款、目錄文件膏燃、特殊（設(shè)備）文件
3）文件系統(tǒng)模型
4）文件操作
操作系統(tǒng)提供哪些文件操作？
最基本的操作
創(chuàng)建/刪除文件：分空間何什，形成FCB及目錄（名组哩，地址）
讀、寫：按名檢索目錄处渣，找到文件地址伶贰，開始讀、寫
設(shè)置文件讀寫位置罐栈，實現(xiàn)隨機存仁蜓谩（尤其適用于記錄文件）
2、文件的邏輯結(jié)構(gòu)
文件系統(tǒng)設(shè)計的關(guān)鍵要素：
如何構(gòu)成一個文件荠诬，以及如何存儲在外存琅翻。
文件結(jié)構(gòu)：
文件的邏輯結(jié)構(gòu)file logical structure：按用戶觀點如何組織數(shù)據(jù)；又稱文件組織file organization
基本要求：檢索速度高浅妆、方便修改望迎、降低存儲空間費用（不連續(xù)）
文件的物理結(jié)構(gòu)：根據(jù)外存上的物理塊的分配機制障癌，記錄文件外存的存儲結(jié)構(gòu)凌外。用戶感知不到的。
①順序文件
兩種記錄排列方式
串結(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)鍵字標(biāo)識的記錄（例如：數(shù)據(jù)庫、文件系統(tǒng)的基于文件名排序的目錄檢索）
順序文件的優(yōu)缺點：
不方便隨機存取某條記錄奔缠，但適用批量存取的場合掠抬。
適合磁帶等特殊介質(zhì)。
單記錄的查找校哎、修改等交互性差两波；增減不方便（改進辦法：把增刪改的記錄登記在一個事務(wù)文件中瞳步，在某段時間間隔后再與原文件合并更新）。
②索引文件
為了方便單個記錄的隨機存取腰奋，為文件建立一個索引表单起，記錄每項記錄在文件的邏輯地址及記錄長度；該索引表按關(guān)鍵字排序劣坊，馏臭。
索引表內(nèi)容：
索引號、長度讼稚、記錄地址指針
檢索效率
索引表本身即是個按記錄鍵排序的定長順序文件括儒，所以能利用算法提高索引表檢索速度
③索引順序文件
既要方便，又要降低開銷
本方式是最常見的一種邏輯文件形式锐想。
將順序文件的所有記錄分組
還是建立索引表帮寻，但每個表項記錄的是每組第1條記錄的鍵值和地址。
組內(nèi)記錄仍按順序方式檢索和使用赠摇。
檢索一條記錄的過程：
先計算記錄是在第幾組固逗，然后再檢索索引確定組在哪里后，在組內(nèi)順序查找藕帜。
可利用多級索引烫罩，進一步提高檢索效率。
④直接文件
目標(biāo)：有效利用外存空間洽故，提高文件訪問速度
常用三種方式：
連續(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)存
每個文件單獨建索引表（物理盤塊索引），記錄所有分配給它的盤塊號簇宽；
建立文件時勋篓，便分配一定的外存空間用于存放文件盤塊索引表信息；
③混合組織索引（增量式索引組織方式）
多種索引方式相結(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條信息填寫入新回收塊。
