目錄
文件控制塊---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))。
盤塊的分配與回收
成組鏈接法