【正文】 詞 )排列 。 21 2. 對(duì)順序文件 (Sequential File)的讀 / R0R1R2R3?Ri?LLLLLL2L3L4LL(i ＋ 1 ) LR p t r( a ) 定長(zhǎng)記 錄文件L0R0L1R1?Ri?W p t r( b ) 變 長(zhǎng)記錄 文件Li0 0L0L0＋ 1L1L0＋ L1＋ 2Li∑ ( Lk＋ 1)i － 1k ＝ 0∑ ( Lk＋ 1)ik ＝ 0圖 63 定長(zhǎng)和變長(zhǎng)記錄文件 22 3. 順序文件的最佳應(yīng)用場(chǎng)合 ， 是在對(duì)諸記錄進(jìn)行批量存取時(shí) ， 即每次要讀或?qū)懸淮笈涗?。 在交互應(yīng)用的場(chǎng)合 ， 如果用戶 (程序 )要求查找或修改單個(gè)記錄 ， 為此系統(tǒng)便要去逐個(gè)地查找諸記錄 。 例如 ， 有一個(gè)含有 104個(gè)記錄的順序文件 ， 如果對(duì)它采用順序查找法去查找一個(gè)指定的記錄 ， 則平均需要查找 5 103個(gè)記錄； 如果是可變長(zhǎng)記錄的順序文件 ， 則為查找一個(gè)記錄所需付出的開銷將更大 ， 這就限制了順序文件的長(zhǎng)度 。 為了解決這一問(wèn)題 ， 可以為順序文件配置一個(gè)運(yùn)行記錄文件 (Log File)或稱為事務(wù)文件(Transaction File)， 把試圖增加 、 刪除或修改的信息記錄于其中 ， 規(guī)定每隔一定時(shí)間 ， 例如 4小時(shí) ， 將運(yùn)行記錄文件與原來(lái)的主文件加以合并 ， 產(chǎn)生一個(gè)按關(guān)鍵字排序的新文件 。為此，須順序地查找每個(gè)記錄，從中獲得相應(yīng)記錄的長(zhǎng)度 Li，然后才能按下式計(jì)算出第 i個(gè)記錄的首址。 換言之 ， 記錄鍵值本身就決定了記錄的物理地址 。 組織直接文件的關(guān)鍵 ， 在于用什么方法進(jìn)行從記錄值到物理地址的轉(zhuǎn)換 。 (2) 順序訪問(wèn)速度快。 (2) 必須事先知道文件的長(zhǎng)度。 要對(duì)一個(gè)較大的文件進(jìn)行直接存取 ， 須首先在 FAT中順序地查找許多盤塊號(hào) 。 圖 611 索引分配方式 1 2305 6 7491011813 14 151217 181916212223202526272429 303128c o u n tf i l e 塊 序 號(hào)j e e p 19目錄91611025－ 1－ 1－ 1192. 多級(jí)索引分配 012……………1 0 51 0 62 5 43 5 63 5 79 8 51 0 51 0 62 5 47 4 03 5 63 5 7…1 1 2 59 8 53 6 07 4 0…1 1 2 5…主索引3 6 0第二級(jí) 索引磁盤空 間圖 612 兩級(jí)索引分配 圖 613 混合索引方式 m o d eo w n e r s ( 2 )t i m e s t a m p s ( 3 )s i z eb l o c k c o u n ti . a d d r ( 0 )i . a d d r ( 1 )d i r e c t b l o c k ss i n g l e i n d i r e c td o u b l e i n d i r e c tt r i p l e i n d i r e c td a t ad a t ad a t ad a t a……d a t ad a t a………d a t ad a t ad a t ad a t a38 (1) 直接地址 。 換言之 ， 在這里的每項(xiàng)中所存放的是該文件數(shù)據(jù)的盤塊的盤塊號(hào) 。 39 (2) 一次間接地址 。 為此 ， 可再利用索引結(jié)點(diǎn)中的地址項(xiàng) iaddr(10)來(lái)提供一次間接地址 。圖中的一次間址塊也就是索引塊 ， 系統(tǒng)將分配給文件的多個(gè)盤塊號(hào)記入其中 。 40 (3) 多次間接地址 。 這時(shí) ， 用地址項(xiàng) iaddr(11)提供二次間接地址 。 系統(tǒng)此時(shí)是在二次間址塊中記入所有一次間址塊的盤號(hào) 。 同理 ， 地址項(xiàng) iaddr(12)作為三次間接地址 ， 其所允許的文件最大長(zhǎng)度可達(dá) 4 TB。 (2) 提高對(duì)目錄的檢索速度。 (4) 允許文件重名。 (2) 狀態(tài)。 每當(dāng)有一進(jìn)程要訪問(wèn)此 i結(jié)點(diǎn)時(shí)， 將該訪問(wèn)計(jì)數(shù)加 1， 訪問(wèn)完再減 1 (4) (5) 鏈接指針。 46 目錄結(jié)構(gòu) 1. 單級(jí)目錄結(jié)構(gòu) 文件名 物理地址 文件說(shuō)明 狀態(tài)位 文件名 1 文件名 2 … 圖 616 單級(jí)目錄 47 單級(jí)目錄的優(yōu)點(diǎn)是簡(jiǎn)單且能實(shí)現(xiàn)目錄管理的基本功能 ——按名存取 ， (1) 查找速度慢 (2) 不允許重名 (3) 不便于實(shí)現(xiàn)文件共享 48 2. 兩級(jí)目錄 圖 617 兩級(jí)目錄結(jié)構(gòu) 用戶名W a n gZ h a n gG a o指向子 目錄指針W a n g 用 戶 目 錄A l p h aT e s tA l p h aT e s tR e p o r tT e s tZ h a n g 用 戶 目 錄R e p o r tT e s tG a o 用 戶 目 錄B e t aD e v i c eM i s xB e t aD e v i c eM i s x49 (1) 提高了檢索目錄的速度 (2) 在不同的用戶目錄中， 可以使用相同的文件名。 在樹形目錄結(jié)構(gòu)中 ， 從根目錄到任何數(shù)據(jù)文件 ， 都只有一條惟一的通路 。 系統(tǒng)中的每一個(gè)文件都有惟一的路徑名 。 52 (3) 當(dāng)前目錄 (Current Directory)。 這是相當(dāng)麻煩的事 ， 同時(shí)由于一個(gè)進(jìn)程運(yùn)行時(shí)所訪問(wèn)的文件 ， 大多僅局限于某個(gè)范圍 ， 因而非常不便 。 進(jìn)程對(duì)各文件的訪問(wèn)都相對(duì)于 “ 當(dāng)前目錄 ” 而進(jìn)行 。 把這一路徑上的全部目錄文件名與數(shù)據(jù)文件名用 “ /”連接形成路徑名 ， 如用戶 B的當(dāng)前目錄是 F， 則此時(shí)文件 J的相對(duì)路徑名僅是 J本身 。 53 4. 增加和刪除目錄 (1) 不刪除非空目錄 。 如果目錄中還包含有子目錄 ， 還必須采取遞歸調(diào)用方式來(lái)將其刪除 ， 在 MSDOS中就是采用這種刪除方式 。 當(dāng)要?jiǎng)h除一目錄時(shí) ， 如果在該目錄中還包含有文件 ， 則目錄中的所有文件和子目錄也同時(shí)被刪除 。 (2) 如果目錄項(xiàng)中的文件名與指定文件名相匹配 ， 則表示該目錄項(xiàng)正是所要尋找的文件所對(duì)應(yīng)的目錄項(xiàng) ， 故而可從中找到該文件所在的物理地址 。 56 空閑表法和空閑鏈表法 1. 空閑表法 圖 620 空閑盤塊表 序號(hào) 第一空閑盤塊號(hào) 空閑盤塊數(shù) 1 2 4 2 9 3 3 15 5 4 — — 文件存儲(chǔ)空間的管理 57 (2) 存儲(chǔ)空間的分配與回收 。 例如 ， 在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時(shí) ， 先順序地檢索空閑表的各表項(xiàng) ， 直至找到第一個(gè)其大小能滿足要求的空閑區(qū) ， 再將該盤區(qū)分配給用戶 (進(jìn)程 )， 同時(shí)修改空閑表 。 58 2. 空閑鏈表法 (1) 空閑盤塊鏈。 (2) 將所找到的一個(gè)或一組二進(jìn)制位， 轉(zhuǎn)換成與之相應(yīng)的盤塊號(hào)。 (3) 修改位示圖， 令 map［ i,j］ =1。 i=(b1)DIV n+1 j=(b1)MOD n+1 (2) 修改位示圖。 62 成組鏈接法 1. 1 0 04 0 03 9 93 0 13 0 01 0 03 0 02 9 9…2 0 22 0 12 9 9…1 0 04 0 03 9 9…2 0 1 3 0 1………9907 9 9 97 9 0 17 9 0 07 8 9 9…7 8 0 17 9 9 9…7 9 0 1空 閑 盤 塊 號(hào)棧S . f r e e019899圖 622 空閑盤塊的成組鏈接法 63 2. 當(dāng)系統(tǒng)要為用戶分配文件所需的盤塊時(shí) ， 須調(diào)用盤塊分配過(guò)程來(lái)完成 。 若該盤塊號(hào)已是棧底 ， 即 (0)， 這是當(dāng)前棧中最后一個(gè)可分配的盤塊號(hào) 。 然后 ， 再分配一相應(yīng)的緩沖區(qū) (作為該盤塊的緩沖區(qū) )。 64 在系統(tǒng)回收空閑盤塊時(shí) ， 須調(diào)用盤塊回收過(guò)程進(jìn)行回收 。 當(dāng)棧中空閑盤塊號(hào)數(shù)目已達(dá)100時(shí) ， 表示棧已滿 ， 便將現(xiàn)有棧中的 100個(gè)盤塊號(hào) ， 記入新回收的盤塊中 ， 再將其盤塊號(hào)作為新棧底 。一個(gè)分區(qū)的參數(shù)包括： 磁盤參數(shù) （如每道扇區(qū)數(shù)和磁頭數(shù)）， 分區(qū)的起始和結(jié)束柱面 等。在同一個(gè)文件卷中 使用同一份管理數(shù)據(jù) 進(jìn)行文件 分配和外存空閑空間管理 ，而在不同的文件卷中使用相互獨(dú)立的管理數(shù)據(jù)。 – 通常一個(gè) 文件卷只能存放在一個(gè)物理外設(shè)上 （并不絕對(duì)），如一個(gè)磁盤分區(qū)或一盤磁帶。 – 通常，進(jìn)行格式化操作使得一個(gè)文件卷上 原有的文件都被刪除 ?？梢匀菁{長(zhǎng)度大于磁盤分區(qū)容量的文件。 67 ? 磁盤交叉存儲(chǔ) (disk interleaving)： 將一個(gè)文件卷的存儲(chǔ)塊依次分散在多個(gè)磁盤上 。 – 優(yōu)點(diǎn)： 提高 I/O效率 。關(guān)鍵： 磁盤訪問(wèn)時(shí)間大部分由旋轉(zhuǎn)等待時(shí)間組成 。 – 類似例子：在虛擬存儲(chǔ)器中建立 多個(gè)交換區(qū) ，分散在多個(gè)磁盤上 68 D i sk 0D i sk 1D i sk 2D i sk 3C y cl i ng W ai tD at a T r ans f ertR eques t C om pl et e多個(gè)磁盤上的交換區(qū)訪問(wèn) 69 AABB B BB CCCCC根目錄? C CC圖 623 包含有共享文件的文件系統(tǒng) 文件共享與文件保護(hù) 圖 624 基于索引結(jié)點(diǎn)的共享方式 W a n g 用戶文 件目錄T e s t rL e e 用戶文 件目錄T e s t rc o u n t ＝ 2文件物 理地址索引結(jié) 點(diǎn)T e s t圖 625 進(jìn)程 B鏈接前后的情況 C 的目錄o w n e r ＝ cc o u