1、文件和文件系統(tǒng)
文件管理：把所管理的程序和數(shù)據(jù)組織成一系列的文件，并能進(jìn)行合理的存儲、使用等操作。
1 ）基本概念
????數(shù)據(jù)項(xiàng)：描述對象某種屬性的字符集；是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單位。
????記錄：一組相關(guān)數(shù)據(jù)項(xiàng)集合，描述對象某方面的屬性；
????關(guān)鍵字：一個(gè)記錄中的一個(gè)或幾個(gè)數(shù)據(jù)項(xiàng)的集合，用于唯一的標(biāo)識一個(gè)記錄。
????文件：由創(chuàng)建者定義的、具有文件名的一組相關(guān)元素的集合。
????????有結(jié)構(gòu)：由相關(guān)記錄組成
????????無結(jié)構(gòu)：字符流的形式
????????屬性：類型、長度、物理位置、創(chuàng)建時(shí)間
2 ）文件類型
????不同的系統(tǒng)對文件的管理方式不同，大多用擴(kuò)展名標(biāo)志文件類型，按如下幾種方式分類文件
????????按用途：系統(tǒng)、用戶、庫文件
????????按數(shù)據(jù)形式：源文件、目標(biāo)文件、可執(zhí)行文件
????????按存取控制屬性：只執(zhí)行、只讀、讀寫
????????按組織和處理方式：普通文件、目錄文件、特殊（設(shè)備）文件
3）文件系統(tǒng)模型
4）文件操作
操作系統(tǒng)提供哪些文件操作？
????最基本的操作
????????創(chuàng)建/刪除文件：分空間，形成FCB及目錄（名，地址）
????????讀、寫：按名檢索目錄，找到文件地址，開始讀、寫
????????設(shè)置文件讀寫位置，實(shí)現(xiàn)隨機(jī)存?。ㄓ绕溥m用于記錄文件）
????還需要：“打開”與“關(guān)閉”：文件讀/寫操作 = 檢索 + 讀/寫。
????????每次讀寫前都要重復(fù)檢索增大開銷。所以為了方便對同一文件的多次讀寫，一次檢索到文件后就在內(nèi)存中記錄其位置，避免重復(fù)檢索。被記錄下位置的文件就是“打開”文件；
????????不需要再操作文件時(shí)，通過“關(guān)閉”這個(gè)系統(tǒng)調(diào)用關(guān)閉文件——即從打開文件表上刪除其路徑信息即可。
????其他操作：改名、改所屬用戶、改訪問權(quán)限等屬性的操作。
2、文件的邏輯結(jié)構(gòu)
文件系統(tǒng)設(shè)計(jì)的關(guān)鍵要素：
????如何構(gòu)成一個(gè)文件，以及如何存儲在外存。
文件結(jié)構(gòu)：
????文件的邏輯結(jié)構(gòu)file logical structure：按用戶觀點(diǎn)如何組織數(shù)據(jù)；又稱文件組織file organization
????????基本要求：檢索速度高、方便修改、降低存儲空間費(fèi)用（不連續(xù)）
????文件的物理結(jié)構(gòu)：根據(jù)外存上的物理塊的分配機(jī)制，記錄文件外存的存儲結(jié)構(gòu)。用戶感知不到的。
1）文件邏輯結(jié)構(gòu)的類型
有結(jié)構(gòu)文件（記錄式）
????①定長記錄
????②變長記錄
如何組織記錄：
????順序文件。系統(tǒng)需按該類型記錄“長度”，通常定長。
????索引文件。系統(tǒng)需為文件建立索引表。
????索引順序文件。建索引表，記錄每組記錄的第一個(gè)記錄位置。
無結(jié)構(gòu)文件（字符流式）
????字節(jié)為單位，利用讀寫指針依次訪問。
????系統(tǒng)對該類文件不需格式處理。
①順序文件
兩種記錄排列方式
????串結(jié)構(gòu)：按記錄形成的時(shí)間順序串行排序。記錄順序與關(guān)鍵字無關(guān)；
????順序結(jié)構(gòu)：按關(guān)鍵字排序。
檢索方法：
????從頭檢索，順序查找要找的記錄，定長的計(jì)算相對快。
????順序結(jié)構(gòu)，可用折半查找、插值查找、跳步查找等算法提高效率
具體的尋址過程：
????第i條記錄地址（定長） ：讀寫指針 + 記錄長度： ptr + i*L
????第i條記錄地址（變長） ：掃描或讀取前面0~i-1條記錄
????第i條記錄地址（變長）變長記錄數(shù)據(jù)前用1字節(jié)保存每條記錄長度，順序掃描，但不用把記錄全掃描完
順序結(jié)構(gòu)記錄按關(guān)鍵字排序，可按關(guān)鍵字檢索
????定長：結(jié)合折半查找算法等提高檢索速度
????變長：從第1個(gè)記錄開始順序掃描，直到掃描到要檢索的關(guān)鍵字標(biāo)識的記錄（例如：數(shù)據(jù)庫、文件系統(tǒng)的基于文件名排序的目錄檢索）
順序文件的優(yōu)缺點(diǎn)：
????不方便隨機(jī)存取某條記錄，但適用批量存取的場合。
????適合磁帶等特殊介質(zhì)。
????單記錄的查找、修改等交互性差；增減不方便（改進(jìn)辦法：把增刪改的記錄登記在一個(gè)事務(wù)文件中，在某段時(shí)間間隔后再與原文件合并更新）。
②索引文件
????????為了方便單個(gè)記錄的隨機(jī)存取，為文件建立一個(gè)索引表，記錄每項(xiàng)記錄在文件的邏輯地址及記錄長度；該索引表按關(guān)鍵字排序，。
索引表內(nèi)容：
????索引號、長度、記錄地址指針
檢索效率
????索引表本身即是個(gè)按記錄鍵排序的定長順序文件，所以能利用算法提高索引表檢索速度
折半檢索過程舉例
1.給出用戶關(guān)鍵字
2.檢索索引表(設(shè)有n條記錄,設(shè)一個(gè)索引表項(xiàng)占x字節(jié))，則索引表的x*n/2字節(jié)處記錄著n/2號記錄的地址
3.根據(jù)第2步的地址，讀一條記錄，若記錄中關(guān)鍵字不匹配，再判斷找第n/4還是第n/2+n/4條記錄
一個(gè)索引文件可以有多個(gè)索引表
????????為方便用戶根據(jù)不同記錄屬性檢索記錄，為順序文件建立多個(gè)索引表，每種能成為檢索條件的域都配備一張索引表。
索引文件的優(yōu)缺點(diǎn)
????適用于變長記錄，可提高檢索速度，實(shí)現(xiàn)直接存取
????索引表增加了存儲開銷
③索引順序文件
既要方便，又要降低開銷
本方式是最常見的一種邏輯文件形式。
????將順序文件的所有記錄分組
????還是建立索引表，但每個(gè)表項(xiàng)記錄的是每組第1條記錄的鍵值和地址。
????組內(nèi)記錄仍按順序方式檢索和使用。
檢索一條記錄的過程：
????先計(jì)算記錄是在第幾組，然后再檢索索引確定組在哪里后，在組內(nèi)順序查找。
可利用多級索引，進(jìn)一步提高檢索效率。
④直接文件
給定鍵值（如學(xué)號）不需順序檢索直接得到記錄的物理地址
用戶對文件的操作由操作系統(tǒng)按文件結(jié)構(gòu)分析執(zhí)行
而操作歸根到底要到外存中進(jìn)行實(shí)質(zhì)操作。
3、外存分配方式
目標(biāo)：有效利用外存空間，提高文件訪問速度
常用三種方式：
????1）連續(xù)分配
????????為每一個(gè)文件分配一組相鄰的盤塊。
????????邏輯文件中的記錄順序與存儲器中文件占用盤塊的順序一致。
????????優(yōu)點(diǎn)：順序訪問容易，讀寫速度快
????????缺點(diǎn)：
????????????會產(chǎn)生外存碎片?？删o湊法彌補(bǔ)，但需要額外的空間，和內(nèi)存緊湊相比更花時(shí)間。
????????????創(chuàng)建文件時(shí)要給出文件大??；存儲空間利用率不高，不利于文件的動態(tài)增加和修改；
????????????適用于變化不大順序訪問的文件，在流行的UNIX系統(tǒng)中仍保留了連續(xù)文件結(jié)構(gòu)。如對換區(qū)
????2）鏈接分配（不連續(xù)）
????????可以為每一個(gè)文件分配一組不相鄰的盤塊。
????????設(shè)置鏈接指針，將同屬于一個(gè)文件的多個(gè)離散盤塊鏈接成一個(gè)鏈表，這樣形成的文件稱為鏈接文件。會有鏈接成本。
????????優(yōu)點(diǎn)：
????????????離散分配，消除外部碎片，提高利用率
????????????同時(shí)適用于文件的動態(tài)增長；修改容易
????????鏈接有兩種形式：
? ? ? ? ? ? ①隱式鏈接
? ? ? ? ②顯式鏈接（FAT--file allocationtable）
? ??????????鏈接信息以信息表的形式顯示存放
FAT表的相關(guān)計(jì)算
MS-DOS文件分配結(jié)構(gòu)為例：
一個(gè)1.2M的磁盤，盤塊512B大??；若文件系統(tǒng)采用FAT格式，則FAT表大小如何？
表項(xiàng)個(gè)數(shù) =? 盤塊個(gè)數(shù)
=? 容量 / 盤塊大小 = 1.2 *220 / 29 = 1.2 *211 個(gè)
表項(xiàng)大小，決定于盤塊數(shù)量編號需要的位數(shù)=12 位；
FAT表大小 = 表項(xiàng)個(gè)數(shù) * 表項(xiàng)大小
? = 1.2 *211 * 12 bit
? = 1.2 *211 * 1.5B = 3.6KB
以半字節(jié)（0.5B=4b）為基本單位,表項(xiàng)需12位（1.5B）
FAT 與 NTFS 技術(shù)
早期MS-DOS：12位的FAT12文件系統(tǒng)
Windows95、98：升級到FAT32
Windows NT后：NTFS
? ? 物理磁盤分邏輯卷（分區(qū)），每卷都有一個(gè)單獨(dú)區(qū)域存放自己的文件系統(tǒng)目錄和FAT表。
1.FAT12
? ??表項(xiàng)12位。能支持的硬盤容量僅為8M。
????2^12(個(gè))*512B*4（分區(qū)數(shù)）=2^23B=8M
????磁盤容量不斷增大，可將若干盤塊組為一簇。以簇為單位分配空間
????FAT表記錄簇號，表項(xiàng)數(shù)量減少，一定程度上提高了檢索速度，減少了指針開銷，
????但該改進(jìn)有限，且會形成簇內(nèi)碎片。12位的格式對磁盤容量仍有很大限制
2.FAT16
? ??增加FAT表的項(xiàng)數(shù)，16位可管理的盤容量為2^16*64*512B(一簇含64個(gè)盤塊)=2048M
????若磁盤容量為8G，則每簇大小達(dá)到128K（8G/2^16）,簇內(nèi)碎片最大會到128K。浪費(fèi)嚴(yán)重。
3.FAT32
????簇不能太大，只能繼續(xù)增加表項(xiàng)位數(shù)，以記錄更多數(shù)量
????FAT32規(guī)定每簇4KB(即8個(gè)512B的盤塊），該格式能管理的單個(gè)最大磁盤空間為2^32*4KB=2TB。
????簇大小合適，空間利用率提高；但分配表的擴(kuò)大使運(yùn)行速度相對慢了；可支持長文件名；有最小空間管理限制，卷必須大于512M，單個(gè)文件長度不能大于4G，不能向下兼容。
4.NTF（New technology file system）
? ? ①采用64位磁盤地址，理論上支持2^64字節(jié)的磁盤分區(qū)；
? ? ②支持長文件名；
? ? ③系統(tǒng)糾容錯(cuò)功能
? ? ④提供數(shù)據(jù)一致性、文件加密、壓縮等功能
磁盤組織
????以簇為單位分配回收、但不規(guī)定盤塊大小
????磁盤格式化時(shí)確定卷的簇大小（物理磁盤扇區(qū)的整數(shù)倍），512M以內(nèi)的小磁盤默認(rèn)簇大小為512B，1G的默認(rèn)大小為1KB。。。大多數(shù)情況是4KB
????卷上簇編號為LCN，用戶用到的簇順序編成用戶虛擬簇號VCN，NTFS可進(jìn)行VCN到LCN的映射
文件組織
????以卷為單位，將卷的所有文件信息、目錄信息、可用未分配空間記錄在主控文件表MFT中。
????每個(gè)文件的信息對應(yīng)一行，固定大小1KB，稱為元數(shù)據(jù)
????文件屬性信息、文件數(shù)據(jù)較少時(shí)就直接寫在MFT中；較多超出1KB時(shí)，記錄存放這些信息的簇地址指針。
????兼容性上也有不足
????3）索引分配
????鏈接的不足
????????順序檢索的時(shí)間成本：不能支持高效的盤塊直接存取。要對一個(gè)文件進(jìn)行直接存取，仍需在FAT中順序的查找許多盤塊號。
????????鏈接信息的空間成本：FAT需占用較大的內(nèi)存空間。當(dāng)磁盤容量較大時(shí)，F(xiàn)AT可能要占用數(shù)MB以上的內(nèi)存空間。這是令人難以忍受的
????改進(jìn)：
? ? 系統(tǒng)運(yùn)行時(shí)只涉及部分文件，F(xiàn)AT表無需全部調(diào)入內(nèi)存
????????每個(gè)文件單獨(dú)建索引表（物理盤塊索引），記錄所有分配給它的盤塊號；
????????建立文件時(shí)，便分配一定的外存空間用于存放文件盤塊索引表信息；
????????①單級索引分配
????????索引形式適合大文件
????????中、小型文件，只需若干鏈接即可。若用索引分配方式，用一個(gè)盤塊存放少量索引信息反而不適用。
????????②多級索引
????????????若文件較大，存放索引表也需要多個(gè)盤塊（索引盤塊）。
????????????索引盤塊亦需要按順序管理起來
????????????????若索引盤塊數(shù)量較少用指針鏈接的方式即可；
????????????????若索引盤塊較多，需對索引盤塊也采用索引方式管理，形成多級索引。
多級索引下的文件大小
若兩級索引，盤塊1KB，盤塊號占4字節(jié)
????一個(gè)盤塊可存放的盤塊號數(shù)有多少個(gè)
????????1KB/4B = 210/4 = 28 = 256（個(gè)）
????二級索引下的文件可分配的最大盤塊數(shù)
????????256 * 256 =26×210=64 K（個(gè)）
????文件最大長度為
????????64K（個(gè)）*1KB=64MB
若盤塊大小為4KB，單級索引允許文件最大長度為4MB（4K/4*4KB），二級索引則文件最大可達(dá)4GB（1K*1K*4KB）。
????????③混合組織索引（增量式索引組織方式）
????????多種索引方式相結(jié)合，以UNIX system V的索引結(jié)點(diǎn)為例：
????????一個(gè)索引結(jié)點(diǎn)定義為13個(gè)地址項(xiàng)：iaddr（0）~iaddr（12），總的來說分為兩種：直接地址、間接地址
????????????iaddr（0）~iaddr（9）存放直接地址，即存文件數(shù)據(jù)的盤塊號；
????????????iaddr（10）存放單級索引的索引盤塊號；
????????????剩余的用于文件較大時(shí)存放多級索引數(shù)據(jù)。
????????????????????iaddr（11）存放二級索引的主索引盤塊號
????????????????????iaddr（12）存放三級索引的主索引盤塊號
索引文件在順序訪問或隨機(jī)訪問中都比較靈活，是一種比較 好的文件物理結(jié)構(gòu)，但也是需要一定的用于索引表的空間開銷和檢索文件索引的時(shí)間開銷的。
UNIX系統(tǒng)是使用索引結(jié)構(gòu)成功的例子。
通常一個(gè)系統(tǒng)中僅采用一種方式
采用的磁盤分配方式?jīng)Q定了文件的“物理結(jié)構(gòu)”
????順序結(jié)構(gòu)；鏈接式結(jié)構(gòu)；索引式結(jié)構(gòu)。
????注意與邏輯結(jié)構(gòu)名類似但不是一回事。
4、存儲空間的管理
為實(shí)現(xiàn)存儲空間分配，系統(tǒng)需要：
????記住空閑存儲空間使用情況；為空間設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)；
????提供對存儲空間分配、回收的操作手段。
典型的管理方法：
1）空閑表和空閑鏈表法
????空閑表法
????????常用于連續(xù)分配管理方式
? ??①數(shù)據(jù)結(jié)構(gòu)
????????系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑表
????????每個(gè)空閑區(qū)對應(yīng)一個(gè)空閑表項(xiàng)（表項(xiàng)包括序號、空閑區(qū)的第一個(gè)盤塊號、空閑盤塊數(shù)等。）
????????將所有空閑區(qū)按其起始盤塊號遞增的次序排列，如右圖。
? ??②存儲空間的分配與回收操作
????與內(nèi)存的動態(tài)分配類似，同樣可采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等。
????回收主要解決對數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)修改。
????應(yīng)該說明，雖然很少采用連續(xù)分配方式，然而在外存的管理中，由于它具有較高的分配速度，可減少訪問磁盤的I/O頻率，故它在諸多分配方式中仍占有一席之地。（如實(shí)現(xiàn)虛擬用的部分外存就是連續(xù)分配方式）
????空閑鏈表法
????????將所有空閑盤區(qū)拉成一條空閑鏈。
? ??①數(shù)據(jù)結(jié)構(gòu)：鏈
????????根據(jù)構(gòu)成鏈所用基本元素的不同，可把鏈表分成兩種形式：
????????空閑盤塊鏈
????????????將磁盤上的所有空閑空間，以盤塊為單位拉成一條鏈。
????????????因創(chuàng)建文件而請求分配空間時(shí)，系統(tǒng)從鏈?zhǔn)滓来握逻m當(dāng)數(shù)目的空閑盤塊分配給用戶。
????????????因刪除文件而釋放存儲空間時(shí)，系統(tǒng)將回收的盤塊依次插入空閑盤塊鏈的末尾。
????????????優(yōu)點(diǎn)：分配和回收一個(gè)盤塊的過程非常簡單，但為一個(gè)文件分配盤塊時(shí)，可能要重復(fù)操作多次。
????????空閑盤區(qū)鏈
????????????將所有空閑盤區(qū)拉成一條鏈。每個(gè)盤區(qū)上含有：
????????????指示下一空閑盤區(qū)的指針、本盤區(qū)大小等信息
????????????分配通常采用首次適應(yīng)算法?；厥毡P區(qū)時(shí)，將回收區(qū)與相鄰的空閑盤區(qū)相合并。
????????????????為提高檢索速度，可以采用顯式方法，為空閑盤區(qū)建立一張鏈表放在內(nèi)存中。
????????????分配、回收操作涉及的鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的處理方便
????????空閑盤塊鏈
????????????分配回收簡單。鏈表長，大量分配時(shí)需要操作的指針多
????????空閑盤區(qū)鏈
????????????鏈表長度不定，分配時(shí)操作的指針數(shù)量相對較少，但分配回收操作相對復(fù)雜。
2）位示圖法——位示圖
利用二進(jìn)制的一位來表示一個(gè)盤塊的使用情況。
????值為0表示對應(yīng)的盤塊空閑，為1表示已分配。有的系統(tǒng)則相反。
????磁盤上的所有盤塊都有一個(gè)二進(jìn)制位與之對應(yīng)，這樣由所有盤塊所對應(yīng)的位構(gòu)成一個(gè)集合，稱為位示圖。
總塊數(shù)=m*n?？捎胢*n個(gè)位數(shù)來構(gòu)成位示圖，可看成是二維數(shù)組（數(shù)據(jù)結(jié)構(gòu)）。
盤塊的分配與回收
根據(jù)位示圖進(jìn)行盤塊分配：
1）順序掃描位示圖。找到為0的二進(jìn)制位。
2）將所找到的一個(gè)或一組二進(jìn)制位，轉(zhuǎn)換成與之對應(yīng)的盤塊號。進(jìn)行分配操作。
????????盤塊號計(jì)算公式為：盤塊號 = 列總數(shù)*（i-1）+ j;
????????（注意下標(biāo)i，j從1開始）
3）修改位示圖。
根據(jù)位示圖進(jìn)行盤塊回收：
1）將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。轉(zhuǎn)換公式為：i=(盤塊號-1)div列數(shù)+1；j=(盤塊號-1)mod列數(shù)+1
? ? ? ? ? Div 求商，mod 取余，公式中的i、j都是從1開始的 （如12號盤塊轉(zhuǎn)換后為1，12）
2）修改位示圖。
優(yōu)點(diǎn)：從位示圖中很容易找到一個(gè)或一組相鄰接的空閑盤塊。
但限于容量問題，常用于微型機(jī)和小型機(jī)中。
3）成組鏈接法
大型文件系統(tǒng)，空閑表或空閑鏈表太長不方便管理操作。
UNIX系統(tǒng)中采用成組鏈接法，這是將兩種方法結(jié)合而形成的一種空閑盤塊管理方法。
中心思想：
????所有盤塊按規(guī)定大小劃分為組；
????組間建立鏈接；
????組內(nèi)的盤塊借助一個(gè)系統(tǒng)?？煽焖偬幚恚抑С蛛x散分配回收。
所有空閑盤塊，被分成若干個(gè)組
設(shè)有10000個(gè)盤塊，每100個(gè)分為1組，則分成100個(gè)組。201-7999為文件區(qū)
各組鏈接起來。
成組鏈接法
????鏈表長度上限固定
????組內(nèi)的盤塊借助一個(gè)系統(tǒng)?？煽焖偬幚恚曳峙浠厥毡容^簡單。
????支持離散分配回收。
①空閑盤塊的組織
????空閑盤塊號棧。
????????用來存放當(dāng)前可用的一組空閑盤塊的盤塊號（最多含100個(gè)號）
????????棧中尚有的空閑盤塊號數(shù)N。
????????（N兼具棧頂指針用。棧底為S.free(0)，棧滿時(shí)棧頂?shù)竭_(dá)S.free(99)，N=100，表示有100個(gè)盤塊供使用。
鏈接
????每一組的第一個(gè)盤塊記錄下一組的盤塊號，形成了一條鏈。
????總將鏈的第一組盤塊總數(shù)和所有的盤塊號，記入棧，作為當(dāng)前可供分配的空閑盤塊號。
②空閑盤塊的分配與回收
????分配盤塊時(shí)，須調(diào)用分配過程來完成。
????????先檢查空閑盤塊號棧是否上鎖，如沒有，便從棧頂取出一空閑盤塊號，將與之對應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格。
????????若該盤塊號已是棧底，即S.free(0)，到達(dá)當(dāng)前棧中最后一個(gè)可供分配的盤塊號。
????????讀取該盤塊號所對應(yīng)的盤塊中的信息：即下一組可用的盤塊號入棧。
????????原棧底盤塊分配出去。修改棧中的空閑盤塊數(shù)。
????回收
????????回收盤塊號記入棧頂，空閑數(shù)N加1
????????N達(dá)到100時(shí)，若再回收一塊，則將該100條信息填寫入新回收塊。
文件控制塊—FCB
????????為了能對一個(gè)文件進(jìn)行正確的存取，必須為文件設(shè)置用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)，稱之為“文件控制塊”（FCB）
????????????文件與文件控制塊一一對應(yīng)
????????????記錄文件名及其存放地址、文件的說明和控制信息。（是誰？在哪里？什么權(quán)？）
????????????文件管理程序借助于文件控制塊中的信息對文件施以各種操作。
????????把文件控制塊的有序集合稱為文件目錄，即一個(gè)文件控制塊就是一個(gè)目錄項(xiàng)。通常一個(gè)文件目錄也被看作是一個(gè)文件，稱為目錄文件。
5、目錄管理
????對文件實(shí)施有效的管理，必須對它們加以妥善組織，主要是兩大操作：
????????（1）基本信息記錄(FCB,目錄項(xiàng))
????????（2）方便檢索、管理（目錄操作）
????目錄管理的要求如下：
????????實(shí)現(xiàn)“按名存取”；（最基本功能）
????????提高對目錄的檢索速度；
????????文件共享；
????????允許文件重名。
1）FCB內(nèi)容
????在文件控制塊中，通常含有以下三類信息。
? ? ? ? ①基本信息類
????????????包括文件名，文件物理位置（對于連續(xù)文件：文件起始塊號；對于鏈接文件：指向第一個(gè)物理塊的指針；對于索引文件：索引表地址。），文件邏輯結(jié)構(gòu)，文件的物理結(jié)構(gòu)。
? ? ? ? ②存取控制信息類
????????????包括文件主的存取權(quán)限，核準(zhǔn)用戶的存取權(quán)限和一般用戶的存取權(quán)限。
? ? ? ? ③使用信息類
????????????建立日期和時(shí)間、文件上次修改的日期和時(shí)間
????????????當(dāng)前使用信息：打開該文件的進(jìn)程數(shù)、是否被進(jìn)程鎖住、是否已修改等。
關(guān)于文件檢索的速度：
????????文件FCB組成的“目錄”文件存放于磁盤；需要時(shí)，要從磁盤將目錄內(nèi)容調(diào)入內(nèi)存進(jìn)行檢索和使用。
2）索引結(jié)點(diǎn)
????索引結(jié)點(diǎn)的引入
????????文件目錄占越大量的盤塊，需進(jìn)行的磁盤讀寫開銷越大。減少實(shí)際檢索的信息量就減少移動磁頭的開銷，提高速度；
????????目錄一般是按名檢索。而直到找到正確文件前，只關(guān)心文件名，不需要其它的文件描述信息，目錄中這部分內(nèi)容的調(diào)入不是必須的。
????????所以：將文件名、文件具體信息分開，使文件描述信息單獨(dú)形成一個(gè)索引結(jié)點(diǎn)。
索引結(jié)點(diǎn)由外存到內(nèi)存的過程中有不同的形式：
????磁盤索引結(jié)點(diǎn)
????????存放在磁盤上的索引結(jié)點(diǎn)。主要包括以下內(nèi)容：文件主標(biāo)識符、文件類型、文件存取權(quán)限、文件物理地址、文件長度、文件連接計(jì)數(shù)、文件存取時(shí)間。
????內(nèi)存索引結(jié)點(diǎn)
????????文件被打開后，將磁盤索引結(jié)點(diǎn)拷貝到內(nèi)存索引結(jié)點(diǎn)中以便使用。比磁盤索引結(jié)點(diǎn)增加了以下內(nèi)容：索引結(jié)點(diǎn)編號、狀態(tài)、訪問計(jì)數(shù)、文件所屬文件系統(tǒng)的邏輯設(shè)備號、鏈接指針。
３） 目錄結(jié)構(gòu)
????目錄結(jié)構(gòu)的組織，關(guān)系到文件系統(tǒng)的存取速度，也關(guān)系到文件的共享性和安全性。
????組織好文件的目錄，是設(shè)計(jì)好文件系統(tǒng)的重要環(huán)節(jié)。
????目前常用的目錄結(jié)構(gòu)形式有
????????①單級目錄結(jié)構(gòu)（Single-Level Directory）
????????????最簡單的目錄結(jié)構(gòu)。
????????????整個(gè)文件系統(tǒng)中只建立一張目錄表，每個(gè)文件一個(gè)目錄項(xiàng)，含有文件相關(guān)信息。
????????????每建立一個(gè)新文件：
????????????????先檢索所有的目錄項(xiàng)，保證文件名唯一。
????????????????獲得一空白目錄項(xiàng)，填入相關(guān)信息，修改狀態(tài)位（表明每個(gè)目錄項(xiàng)是否空閑）。
????????????刪除一個(gè)文件：
????????????????找到對應(yīng)目錄項(xiàng)，回收文件所占用空間
????????????????清除目錄項(xiàng)
????????優(yōu)點(diǎn)：簡單、能實(shí)現(xiàn)目錄管理的基本功能——按名存取。
????????缺點(diǎn)：
? ? ? ? ? ? a.文件檢索時(shí)需搜遍整個(gè)目錄文件，范圍大速度慢。
? ? ? ? ? ? b.不允許重名。名字過多難于記憶，對于多用戶環(huán)境重名難以避免。
? ? ? ? ? ? c.不便于實(shí)現(xiàn)文件共享（因?yàn)椴荒苤孛?，不同用戶使用的共享文件必須不同名字，?biāo)識哪些用戶共享文件也不方便），一般只適用單機(jī)環(huán)境。
????????②兩級目錄結(jié)構(gòu)（ Two-Level Directory ）
????????????為每一個(gè)用戶建立一個(gè)單獨(dú)的用戶文件目錄UFD，UFD由用戶所有文件的文件控制塊組成。
????????????系統(tǒng)建立一個(gè)主文件目錄MFD， MFD中每個(gè)用戶目錄文件都占有一個(gè)目錄項(xiàng)，其中包括用戶名和指向UFD的指針。
????????兩級目錄的特點(diǎn)
????????????基本克服了單級目錄的缺點(diǎn)，并具有以下優(yōu)點(diǎn)：
? ? ? ? ? ? ? ? a.提高了檢索目錄的速度。
? ? ? ? ? ? ? ? b.在不同的目錄中可重名。
? ? ? ? ? ? ? ? c.不同用戶還可以使用相同/不同的文件名來訪問系統(tǒng)中的同一個(gè)共享文件。
????????????不提供子目錄操作，還不方便；各用戶之間被完全隔離的話用戶訪問其他用戶文件時(shí)，不方便合作。
????????③多級目錄結(jié)構(gòu)
????????????適用于較大的文件系統(tǒng)管理。又稱為樹狀目錄(tree-like)
????????????在文件數(shù)目較多時(shí)，便于系統(tǒng)和用戶將文件分散管理。
????????????????層次結(jié)構(gòu)更清晰、提供更靈活的權(quán)限管理等
????????????????但目錄級別太多時(shí)也會增加路徑檢索層次，增加磁盤訪問時(shí)間。
相關(guān)名詞：
????目錄結(jié)構(gòu)
????????主目錄稱為根目錄，數(shù)據(jù)文件為樹葉，其它目錄為結(jié)點(diǎn)。多級目錄縮小檢索范圍提高檢索速度和文件系統(tǒng)的性能。
????路徑名
????????從根目錄到任何數(shù)據(jù)文件都只有一條唯一通路。目錄文件名和數(shù)據(jù)文件名依次用“/”連接起來，即構(gòu)成數(shù)據(jù)文件的路徑名。
????當(dāng)前目錄
????????為每個(gè)進(jìn)程設(shè)置一個(gè)“當(dāng)前目錄”，又稱“工作目錄”。
????????從當(dāng)前目錄開始，逐級經(jīng)過中間的目錄文件，最后達(dá)到要訪問的數(shù)據(jù)文件。這一路徑上的目錄和數(shù)據(jù)文件名用“/”連接成路徑名，稱為相對路徑名。
????????從根開始的路徑名稱為絕對路徑名
4）目錄查詢技術(shù)
????用戶要訪問一個(gè)已存文件
????????目錄數(shù)據(jù)調(diào)入內(nèi)存；
????????按名檢索：系統(tǒng)利用提供的文件名對目錄(根據(jù)目錄層次，需要做的檢索次數(shù)也不同)進(jìn)行查詢
????????找該文件控制塊
????????讀FCB或?qū)?yīng)索引結(jié)點(diǎn)；
????????從文件物理地址換算出文件在磁盤上的物理位置；
????????最后通過磁盤驅(qū)動程序，將所需文件讀入內(nèi)存。
????目錄查詢方式：線性檢索法和Hash方法。
線性檢索法
????又稱為順序檢索法。
????單級目錄中
????????用戶提供文件名，順序查找文件目錄。
????樹型目錄中
????????用戶提供路徑名，如/user/ast/mbox
????????對多級目錄進(jìn)行逐層查找。
Hash方法
????曾介紹的Hash文件。
????如果建立了一張Hash索引文件目錄，便可利用Hash方法進(jìn)行查詢
????系統(tǒng)將用戶提供的文件名變換為文件目錄的索引值，再利用該索引值到目錄中去查找，將顯著的提高檢索速度。
????對于使用通配符的文件名系統(tǒng)無法利用Hash法檢索目錄，還是需用線性查找法。
6、文件共享與保護(hù)
1）文件共享
????多個(gè)用戶共享一份文件，只保留文件的一份副本，節(jié)約存儲空間
????共享范圍：單機(jī)系統(tǒng)/多主機(jī)系統(tǒng)/網(wǎng)絡(luò)范圍
????20世紀(jì)六七十年代，出現(xiàn)了若干文件早期共享方法，繞彎路法、連訪法等，逐漸發(fā)展為現(xiàn)代一些共享方式
????????①索引結(jié)點(diǎn)法
????????????基本FCB法：
????????????????名+詳細(xì)信息。
????????????????直接在文件目錄中包含文件的物理地址，該方法實(shí)現(xiàn)的共享不適用文件動態(tài)變化。一個(gè)用戶對文件的修改（如物理塊號增加），對其他用戶不可見，共享文件的FCB信息記錄同步更新困難。
????????????文件名+索引結(jié)點(diǎn)指針。
????????????????一個(gè)用戶修改指針指向地址里的內(nèi)容，指針不變，其他用戶通過指針總能感知索引結(jié)點(diǎn)中的最新內(nèi)容
????????????????索引結(jié)點(diǎn)中增加count計(jì)數(shù)
????????????????主人刪除操作問題：
????????????????????刪，共享用戶訪問錯(cuò)誤；不刪，計(jì)費(fèi)問題。
????????②符號鏈法
????????????創(chuàng)建一個(gè)link類型的文件：“文件名+共享文件路徑”（類似快捷方式）
????????????文件主人刪除文件，共享者只會出現(xiàn)找不到文件錯(cuò)誤。不會發(fā)生共享文件刪除后出現(xiàn)懸空指針的情況。
????????????該方法適用于網(wǎng)絡(luò)文件共享，但根據(jù)路徑檢索共享文件的目標(biāo)位置增加了訪問開銷，link文件獨(dú)占索引結(jié)點(diǎn)也耗費(fèi)一定的空間。
????????????無論哪種共享，鏈接就對應(yīng)一個(gè)文件，如果遍歷復(fù)制整個(gè)目錄內(nèi)的文件，可能會從多條路徑對共享文件進(jìn)行多次訪問
2）磁盤容錯(cuò)（SFT，system fault tolerance）
????防止磁盤故障造成的文件不安全
????SFT I:磁盤表面故障
????????雙目錄、雙文件分配表（空間冗余）
????????寫后讀校驗(yàn)、熱修復(fù)重定向（時(shí)間操作冗余）
????????????寫入磁盤后再讀回內(nèi)存做一致性校驗(yàn)
????????????熱修復(fù)寫過程：從壞道重定向到專區(qū)并記錄
????SFT II：磁盤驅(qū)動器、控制器故障
????????驅(qū)動器故障：磁盤鏡像
????????控制器故障：磁盤雙工——并行控制器，分離搜索加快讀取
????SFT III：高級容錯(cuò)技術(shù)
????????雙機(jī)熱備份
????????雙機(jī)互備份
????????公用磁盤模式
數(shù)據(jù)一致性
????一個(gè)數(shù)據(jù)分別存儲到多個(gè)文件中，典型的如數(shù)據(jù)庫
????保證數(shù)據(jù)一致性：高可靠存儲器（冗余保證穩(wěn)定，磁盤雙工）+ 一致性軟件
????概念
????????事務(wù)：對數(shù)據(jù)各處保存位置訪問、修改使其維持一致性的一次操作。
????????事務(wù)記錄：記錄事務(wù)運(yùn)行時(shí)數(shù)據(jù)項(xiàng)修改全部信息的數(shù)據(jù)結(jié)構(gòu)：事務(wù)名、數(shù)據(jù)項(xiàng)名、舊值、新值。
????????恢復(fù)算法：利用事務(wù)記錄表處理已完成、未完成事務(wù)。
????????檢查點(diǎn)：每隔一段時(shí)間，將內(nèi)存中的事務(wù)記錄表、已修改數(shù)據(jù)、檢查點(diǎn)輸出到穩(wěn)定存儲器，
????并發(fā)控制
????重復(fù)數(shù)據(jù)的一致性
