目錄

文件控制塊---FCB

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

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

記錄文件名及其存放地址、文件的說明和控制信息

文件管理程序結(jié)組于文件控制塊中的信息對(duì)文件施以各種操作

把文件控制塊的有序幾何成為文件目錄退渗。

即一個(gè)文件控制塊就是一個(gè)目錄項(xiàng)移稳，通常一個(gè)文件目錄也被看作是一個(gè)文件，稱為目錄文件会油。

目錄管理

對(duì)文件實(shí)施有效的管理秒裕。必須對(duì)他們加以妥善組織，主要是兩大操作钞啸。

基本信息記錄FCB几蜻、目錄項(xiàng)

方便檢索喇潘、管理

目錄管理要求

實(shí)現(xiàn)安明存取

提高對(duì)目錄的檢索速度

文件共享

允許文件重名。

FCB內(nèi)容

在文件控制塊中梭稚，通常含有以下三類信息颖低。

基本信息類

包括文件名。文件物理位置弧烤，文件邏輯結(jié)構(gòu)忱屑，文件的物理結(jié)構(gòu)。

存取控制信息類

包括文件主的存取權(quán)限暇昂，核準(zhǔn)用戶的存取權(quán)限和一般用戶的存取權(quán)限莺戒。

使用信息類

建立日期和時(shí)間、文件上次修改的日期和時(shí)間

當(dāng)前使用信息：打開該文件的進(jìn)程數(shù)急波、是否唄進(jìn)程鎖住从铲。是否已修改等。

MS-DOS的文件控制塊

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

文件FCB組成的目錄文件存放于磁盤澄暮，需要時(shí)要從磁盤將目錄內(nèi)容調(diào)入內(nèi)存進(jìn)行檢索使用名段。

如果目錄占用5個(gè)盤塊，則至多需啟動(dòng)5次磁盤讀寫泣懊。

索引節(jié)點(diǎn)

引入

文件目錄占大量的盤塊伸辟，需要進(jìn)行的磁盤讀寫開銷越大減少實(shí)際檢索的i洗腦洗量就減少以哦對(duì)那個(gè)磁頭的開銷。提高速度

目錄一般時(shí)按名檢索馍刮。而直接找到正確文件前信夫，只關(guān)心文件名，不需要其他的文件描述信息卡啰。目錄中這部分內(nèi)容的調(diào)入不是必須的

所以將文件名静稻、文件具體信息分開，使文件描述信息單獨(dú)形成一個(gè)索引結(jié)點(diǎn)碎乃。

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

磁盤索引結(jié)點(diǎn)

存放磁盤上的索引節(jié)點(diǎn)。主要包括：文件主標(biāo)識(shí)符惠奸。文件類型梅誓、文件存取權(quán)限、文件物理地址佛南。文件長(zhǎng)度梗掰、文件連接計(jì)數(shù)，文件存取時(shí)間嗅回。

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

文件被打開后及穗。將磁盤索引結(jié)點(diǎn)拷貝到內(nèi)存索引結(jié)點(diǎn)中以便使用，比磁盤索引結(jié)點(diǎn)增加了一下內(nèi)容：索引結(jié)點(diǎn)編號(hào)绵载、狀態(tài)埂陆、訪問計(jì)數(shù)苛白、文件所屬文件系統(tǒng)的邏輯設(shè)備號(hào)、鏈接指針焚虱。

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

目錄結(jié)構(gòu)的組織购裙、關(guān)系到文件系統(tǒng)的存取速度、也關(guān)系到文件的共享性和安全性鹃栽。

組織好文件的目錄躏率。使設(shè)計(jì)好文件系統(tǒng)的重要環(huán)節(jié)。

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

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

整個(gè)文件系統(tǒng)中只建立一張目錄表,每個(gè)文件一個(gè)目錄項(xiàng)民鼓，含有文件相關(guān)信息薇芝。

每建立一個(gè)新文件：

先檢索所有目錄項(xiàng)，保證文件名唯一丰嘉。

獲得一個(gè)空白目錄項(xiàng)夯到。填入相關(guān)信息。修改狀態(tài)位

刪除一個(gè)文件：

找到對(duì)應(yīng)目錄項(xiàng)供嚎』颇铮回收文件所占用空間，刪除目錄項(xiàng)克滴。

優(yōu)點(diǎn)：簡(jiǎn)單逼争、能實(shí)現(xiàn)目錄管理的基本功能-按名存取

缺點(diǎn)：

文件檢索時(shí)需要搜遍整個(gè)目錄文件，范圍大速度滿劝赔，

不允許重名誓焦，名字過多難于記憶，對(duì)于多用戶環(huán)境重名難以避免着帽，

不敗你于實(shí)現(xiàn)文件共享杂伟，一般只適用于單機(jī)環(huán)境

兩級(jí)目錄結(jié)構(gòu)

為每一個(gè)用戶建立一個(gè)單獨(dú)的用戶文件目 錄UFD，UFD由用戶所有文件的文件控制 塊組成仍翰。

系統(tǒng)建立一個(gè)主文件目錄MFD赫粥， MFD中 每個(gè)用戶目錄文件都占有一個(gè)目錄項(xiàng)，其 中包括用戶名和指向UFD的指針予借。

兩級(jí)目錄的特點(diǎn)

基本克服了單級(jí)目錄的缺點(diǎn)越平，并具有以 下優(yōu)點(diǎn)：

提高了檢索目錄的速度。

在不同的目錄中可重名灵迫。

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

不提供子目錄操作，還不方便瀑粥；各用戶 之間被完全隔離的話用戶訪問其他用戶 文件時(shí)挣跋，不方便合作。

鏈接有兩種形式

隱式鏈接

文件空間信息的目錄項(xiàng) 中沒有鏈接數(shù)據(jù)

◆鏈接信息隱含記錄在盤塊 數(shù)據(jù)中狞换；

◆每個(gè)盤塊拿出若干字節(jié)避咆， 記錄指向下一盤塊號(hào)的指 針舟肉。

◆問題：只能順著盤塊讀取， 可靠性低

顯式鏈接（FAT)

◆記錄盤塊鏈接的 指針顯示地記錄為 一張鏈接表

◆所有已分配的盤 塊號(hào)都記錄在其中牌借， 稱文件分配表

◆為了提高文件系 統(tǒng)訪問速度度气，F(xiàn)AT 一般常駐內(nèi)存

◆屬于一個(gè)文件的盤塊通過鏈接 成為一體，每個(gè)鏈條的首地址作 為文件地址記錄在相應(yīng)文件的 FCB的“物理地址”字段中

計(jì)算

索引分配

鏈接的不足 ?順序檢索的時(shí)間成本：不能支持高效的盤塊直接存取膨报。 要對(duì)一個(gè)文件進(jìn)行直接存取磷籍，仍需在FAT中順序的查找 許多盤塊號(hào)。

鏈接信息的空間成本：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ú)建索引表（物理盤塊索引）比然，記錄所有分 配給它的盤塊號(hào)；

建立文件時(shí)周循，便分配一定的外存空間用于存放文件盤塊 索引表信息强法；

單級(jí)索引分配

◆ 索引形式適合大文件

◆ 中、小型文件湾笛，只需若干鏈接即可饮怯。若用索引 分配方式，用一個(gè)盤塊存放少量索引信息反而 不適用嚎研。

多級(jí)索引

◆若文件較大蓖墅，存放索引表也需要多個(gè) 盤塊（索引盤塊）。

◆索引盤塊亦需要按順序管理起來 ?若索引盤塊數(shù)量較少用指針鏈接的方式即 可临扮；

若索引盤塊較多论矾，需對(duì)索引盤塊也采用索 引方式管理，形成多級(jí)索引杆勇。

多級(jí)索引計(jì)算

混合組織索引

多種索引方式相結(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ù)的盤塊號(hào)； ?

iaddr（10）存放單級(jí)索引的索引盤塊號(hào)关霸；

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

iaddr（11）存放二級(jí)索引的主索引盤塊號(hào)

iaddr（12）存放三級(jí)索引的主索引盤塊號(hào)

存儲(chǔ)空間的管理

空閑表法和空閑鏈表法

空閑表法 ?

常用于連續(xù)分配管理方式

①數(shù)據(jù)結(jié)構(gòu) ?

系統(tǒng)為外存上的所有空閑區(qū)建立 一張空閑表 ?每個(gè)空閑區(qū)對(duì)應(yīng)一個(gè)空閑表項(xiàng) （表項(xiàng)包括序號(hào)杰扫、空閑區(qū)的第一 個(gè)盤塊號(hào)队寇、空閑盤塊數(shù)等。） ?

將所有空閑區(qū)按其起始盤塊號(hào)遞 增的次序排列章姓，如右圖佳遣。

② 存儲(chǔ)空間的分配與回收操作 ? 與內(nèi)存的動(dòng)態(tài)分配類似识埋，同樣可采用首次適 應(yīng)算法、循環(huán)首次適應(yīng)算法等零渐。 ?

回收主要解決對(duì)數(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)成鏈所用基本元素的不同戒财，可 把鏈表分成兩種形式：空閑盤塊鏈 ? 空閑盤區(qū)鏈

空閑盤塊鏈

◆將磁盤上的所有空閑空間热监，以盤塊為單位拉成一 條鏈。

◆因創(chuàng)建文件而請(qǐng)求分配空間時(shí)饮寞，系統(tǒng)從鏈?zhǔn)滓来?摘下適當(dāng)數(shù)目的空閑盤塊分配給用戶孝扛。

◆因刪除文件而釋放存儲(chǔ)空間時(shí)，系統(tǒng)將回收的盤 塊依次插入空閑盤塊鏈的末尾幽崩。

◆優(yōu)點(diǎn)：分配和回收一個(gè)盤塊的過程非常簡(jiǎn)單苦始，但 為一個(gè)文件分配盤塊時(shí)，可能要重復(fù)操作多次

空閑盤區(qū)鏈

◆分配通常采用首次適應(yīng)算法歉铝∮颍回收盤區(qū)時(shí)，將回收 區(qū)與相鄰的空閑盤區(qū)相合并太示。

為提高檢索速度柠贤，可以采用顯式方法，為空閑盤區(qū)建立 一張鏈表放在內(nèi)存中类缤。

◆分配臼勉、回收操作涉及的鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的處理方便

位示圖法——位示圖

利用二進(jìn)制的一位來表示一個(gè)盤塊的使用情況。

值為0表示對(duì)應(yīng)的盤塊空閑餐弱，為1表示已分配宴霸。

有的系 統(tǒng)則相反。

磁盤上的所有盤塊都有一個(gè)二進(jìn)制位與之對(duì)應(yīng)膏蚓，這樣 由所有盤塊所對(duì)應(yīng)的位構(gòu)成一個(gè)集合瓢谢，稱為位示圖。

◆總塊數(shù)=m*n驮瞧∶タ福可用m*n個(gè)位數(shù)來構(gòu)成位示圖，可看成是二維數(shù)組（數(shù)據(jù)結(jié)構(gòu)）。

盤塊的分配與回收

成組鏈接法