文件的物理結(jié)構(gòu)及存儲設(shè)備省名師優(yōu)質(zhì)課賽課獲獎?wù)n件市賽課一等獎?wù)n件

8.2.2文件物理結(jié)構(gòu)及存放設(shè)備(3)索引文件 索引文件是由系統(tǒng)為每個文件建立一張索引表，表中標(biāo)明文件邏輯塊號所對應(yīng)物理塊號，索引表本身物理地址由FCB給出。索引表結(jié)構(gòu)：第1頁索引文件這種方法克服了鏈接文件對隨機(jī)存取限制。把全部指針放在一起：索引塊每個文件都有它自己索引塊索引塊第i個條目指向文件第i個塊（隨機(jī)存?。┮粋€索引塊類似于內(nèi)存分配中一個頁表索引文件開銷要比鏈接文件大，尤其假如每個文件只有極少塊時，會造成其余索引塊浪費。第2頁索引分配a.out16目錄項（條目）文件名索引塊000102030405060708091011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859212223445356nil012345678910111213...索引塊(16)第3頁8.2.2文件物理結(jié)構(gòu)及存放設(shè)備 假如索引表很大，超出了一個物理塊，則系統(tǒng)勢必要像處理其它文件一樣，來處理索引表物理存放方式，這么不利于索引表動態(tài)增刪。處理方法是采取多重索引方式，也就是說，當(dāng)索引表所指物理塊超出一塊時，再增加一個次級索引表。這么，在高一級索引表表項里所指向物理塊中并不存放實際文件信息，而是存放一個索引表，在這個次一級索引表中所指向物理塊才是存放文件信息。假如需要，能夠增加到3級以上多級索引。第4頁鏈接索引塊a.out16directoryentryfilenameindexblock00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585939212223445356..........0123456789101112...255indexblock(16)nil57594041nil0123456789101112...255indexblock(39)第5頁多層索引a.out16directoryentryfilenameindexblock00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585926341043nil0123456789101112...255toplevelindexblock(16)......0123456789101112...255......0123456789101112...255......0123456789101112...255......0123456789101112...255secondaryindexblocks第6頁組合鏈接/多層索引TheUnixinodeowner,grouptimestampssizedirectblockssingleindirectdoubleindirecttripleindirectblock(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)............(filenameisnotstoredintheinode)indexblock(UsedinBSDUnix)第7頁8.2.2文件物理結(jié)構(gòu)及存放設(shè)備2.文件存放設(shè)備文件存放設(shè)備分為不可重復(fù)使用和可重復(fù)使用兩類。不可重復(fù)使用文件存放設(shè)備也稱為I/O式字符設(shè)備，如打印紙等?？芍貜?fù)使用文件存放設(shè)備有磁帶、磁盤、光盤等，也稱塊設(shè)備。第8頁8.2.2文件物理結(jié)構(gòu)及存放設(shè)備 兩種經(jīng)典存放設(shè)備特征及存取方法。(1)次序存取設(shè)備 次序存取設(shè)備通常是指那些容量大、價格低存放設(shè)備。(2)直接存取設(shè)備 光盤、磁盤都是一個可直接存取存放設(shè)備(磁盤又分為硬盤和軟盤)。①磁盤 磁盤是一個可直接存取(按地址存取)存放設(shè)備，它把信息統(tǒng)計在盤片上，每個盤片有正反兩面。②只讀型光盤 光盤存放器是利用光學(xué)原理存取信息存放設(shè)備第9頁8.2.2文件物理結(jié)構(gòu)及存放設(shè)備3.文件結(jié)構(gòu)、存放設(shè)備與存取方式 總而言之，文件物理結(jié)構(gòu)，必須適應(yīng)文件存放設(shè)備，而不一樣存放設(shè)備特征，又決定了其上文件存取方式，下面以磁盤和磁帶存放設(shè)備為例，簡明說明3者關(guān)系：①磁盤上文件結(jié)構(gòu)為連續(xù)時，其存取方式普通為次序或隨機(jī)。 當(dāng)文件為連續(xù)方式時，存取方式通常為次序。②磁帶上文件結(jié)構(gòu)為連續(xù)時，其存取方式普通為次序存取。 當(dāng)其上文件為索引文件時，存取方式可為次序、隨機(jī)兩種形式。第10頁8.3文件管理8.3.1文件目錄結(jié)構(gòu)1.文件目錄文件系統(tǒng)為程序和用戶提供了按文件名存取文件機(jī)制，而將文件名轉(zhuǎn)換為存放地址，以及對文件實施控制管理則需經(jīng)過文件目錄來實現(xiàn)。文件目錄管理和文件存放空間管理已成為文件管理主要內(nèi)容。第11頁8.3.1文件目錄結(jié)構(gòu) 一個文件由文件說明和文件體組成。文件說明部分包含文件基本信息、存取控制信息和文件使用信息。①基本信息包含：文件名，用于標(biāo)識一個文件符號名。文件物理位置，標(biāo)明文件內(nèi)容在外存上存放位置。文件結(jié)構(gòu)，指示文件邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。它決定了文件尋址方式。②存取信息包含：各類用戶(包含文件主、核準(zhǔn)用戶、普通用戶等)存取權(quán)限，實現(xiàn)文件共享及保密。③使用信息包含：文件創(chuàng)建、修改日期和時間，以及當(dāng)前使用狀態(tài)信息。第12頁8.3.1文件目錄結(jié)構(gòu)文件系統(tǒng)將這些說明部分全部信息集中起來，以一個數(shù)據(jù)結(jié)構(gòu)形式表示，稱此結(jié)構(gòu)為文件控制塊FCB(FileControlBlock)。文件目錄由文件控制塊組成。文件系統(tǒng)在每個文件建立時都要為它建立一個文件目錄。文件目錄用于文件描述和文件控制，實現(xiàn)按名存取和文件信息共享與保護(hù)，隨文件建立而創(chuàng)建，隨文件刪除而消亡。不一樣操作系統(tǒng)有不一樣文件目錄。第13頁8.3.1文件目錄結(jié)構(gòu)下面以UNIX文件目錄為例加以說明。UNIX系統(tǒng)文件目錄由目錄項和索引節(jié)點兩部分組成（i節(jié)點—加緊文件檢索方法之一）。目錄項占16B，其中14B為文件名，2B為指向文件說明信息索引節(jié)點指針，每個索引節(jié)點占64B，包含文件屬性、文件共享目錄數(shù)、時間、文件存放塊號、文件長度等說明信息。第14頁8.3.1文件目錄結(jié)構(gòu)2.文件目錄結(jié)構(gòu)文件目錄是由文件說明組成，若干個文件目錄組成一個專門目錄文件，目錄文件結(jié)構(gòu)怎樣，關(guān)系到文件存取速度和文件共享及安全特征。文件目錄結(jié)構(gòu)是指專門目錄文件組織形式。慣用目錄結(jié)構(gòu)有單級目錄，二級目錄和多級目錄。第15頁8.3.1文件目錄結(jié)構(gòu)(1)單級目錄 文件系統(tǒng)在每個存放設(shè)備上僅建立一個目錄文件目錄結(jié)構(gòu)，稱為單級目錄(或稱一級目錄)。目錄文件中每一目錄項(或稱一條統(tǒng)計)對應(yīng)一個文件目錄，它包含相正確數(shù)據(jù)項(文件名及擴(kuò)展名、物理地址、說明信息)，如圖所表示。第16頁8.3.1文件目錄結(jié)構(gòu)單級目錄優(yōu)點是結(jié)構(gòu)簡單，經(jīng)過管理其目錄文件，便可實現(xiàn)對文件信息管理。單級目錄特點是：①搜索范圍寬。②不允許文件重名。③不便于文件共享。第17頁8.3.1文件目錄結(jié)構(gòu)(2)二級目錄結(jié)構(gòu) 二級目錄結(jié)構(gòu)將存放在設(shè)備上目錄文件分成兩級：第一級為系統(tǒng)目錄(稱主目錄MFD)，它包含了用戶目錄名和指向該用戶目錄指針；第二級為用戶目錄(稱UFD)，它包含了該用戶全部文件文件目錄，該文件目錄和上述單級目錄一樣，包含了對應(yīng)文件名字，物理地址等。第18頁8.3.1文件目錄結(jié)構(gòu)二級目錄結(jié)構(gòu):

第19頁8.3.1文件目錄結(jié)構(gòu)(3)多級目錄結(jié)構(gòu)采取樹型數(shù)據(jù)結(jié)構(gòu)方法，便形成一個樹型結(jié)構(gòu)目錄。這種文件目錄第一級系統(tǒng)目錄為樹根節(jié)點，定義為根目錄，文件目錄第二級和以下各級目錄均為樹分支節(jié)點(非終節(jié)點)，均定義為子目錄，只有樹葉節(jié)點(終節(jié)點)才為文件。注：樹型目錄每一級既可定義目錄也可定義文件第20頁樹型目錄usrbinetcdevhostsfstabconfbinsbinspooltapetty0tty1tty2rootdateviwhichwhocalendarcronlp第21頁8.3.1文件目錄結(jié)構(gòu)從根目錄經(jīng)各級子目錄抵達(dá)文件通路上全部子目錄名稱為文件存取路徑。文件絕對路徑（從根目錄開始）文件相對路徑（從當(dāng)前目錄開始）在多級目錄結(jié)構(gòu)中，要訪問一個文件必須從根目錄開始，逐層查找各級子目錄，直到文件。無疑這么查找速度較慢。有必要為系統(tǒng)建立一個稱之為“工作目錄”當(dāng)前目錄（加緊文件檢索方法之二），它不一定是根目錄，當(dāng)用戶不另外指定缺省目錄時，系統(tǒng)從該目錄起進(jìn)行查找。不一樣文件系統(tǒng)都能夠設(shè)置這種工作目錄。將多級目錄結(jié)構(gòu)深入推廣，就產(chǎn)生了無環(huán)結(jié)構(gòu)目錄圖狀結(jié)構(gòu)目錄。第22頁8.3.1文件目錄結(jié)構(gòu)3.文件目錄與文件共享 為了有效實現(xiàn)文件共享，文件系統(tǒng)在建立文件目錄過程中，采取了以下兩種方法，使文件只需保留一個副本，到達(dá)多個用戶共享目標(biāo)。(1)繞道法(交叉法) 繞道法查找共享文件方法是每個用戶從各自當(dāng)前目錄開始，向上返回到共享文件所在路徑交叉節(jié)點，然后沿交叉節(jié)點次序向下訪問到共享文件。第23頁8.3.1文件目錄結(jié)構(gòu)繞道法：第24頁鏈接—文件共享另一個方法真正樹型結(jié)構(gòu)目錄僅允許每個文件存在于該結(jié)構(gòu)中一個地方。一個文件或子目錄出現(xiàn)在目錄結(jié)構(gòu)幾個地方經(jīng)常是方便。比如，兩個程序員正在某個相同項目上工作，都希望與項目關(guān)聯(lián)若干文件保留在自己目錄中。共享文件（或目錄）不一樣于文件拷貝。第25頁鏈接在Unix系統(tǒng)中，共享文件能夠經(jīng)過創(chuàng)建鏈接來實現(xiàn)。Unix支持兩種類型鏈接。硬鏈接

是復(fù)制指向相同存放區(qū)目錄條目軟鏈接（符號鏈接）是別名或其它文件或目錄指針。

(=>在MSWindows中快捷方式)第26頁鏈接usrbinetcvarbinsbinspoolrootdateviwhichwhocalendarcronlpadmmailspool第27頁硬鏈接file1file2file3file4file5file6file7directoryafile-8file1file9file10file11file12file13directorybdisk第28頁軟鏈接file1file2file3file4file5file6file7directoryafile-8file1file9file10file11file12file13directorybdisk第29頁鏈接問題鏈接可能引入一致性問題。對于硬鏈接當(dāng)文件被刪除時會發(fā)生什么？對Unix系統(tǒng)，每個文件有鏈接計數(shù)。當(dāng)指向一個文件新鏈接建立時，該鏈接計數(shù)增加。當(dāng)一個文件被從目錄中刪除時，該鏈接計數(shù)降低。假如鏈接計數(shù)是0，該文件所占據(jù)空間被釋放。第30頁鏈接問題對于軟鏈接假如原來文件被刪除，那么全部軟鏈接被留下懸空。這就像發(fā)生在MSWindows快捷方式第31頁8.3.1文件目錄結(jié)構(gòu)(2)基本文件目錄表法*為了有效實現(xiàn)系統(tǒng)文件共享，文件系統(tǒng)需建立一基本文件目錄BFD，它包含了文件結(jié)構(gòu)、物理塊號、存取控制和管理信息。另外，需增加符號文件目錄表SFD，包含用戶給定符號名和系統(tǒng)文件賦予文件說明信息內(nèi)部標(biāo)識符。主目錄(MFD)統(tǒng)計了文件名和系統(tǒng)給定惟一標(biāo)識。第32頁8.3.1文件目錄結(jié)構(gòu)文件目錄表：第33頁8.3.1文件目錄結(jié)構(gòu) 在實現(xiàn)文件共享時，能夠有以下兩種模式：①不一樣時使用同一文件。②同時使用同一文件。當(dāng)全部進(jìn)程都不修改文件時，情況比較簡單；假如一些進(jìn)程要求對文件修改，那么就必需加以控制，不然數(shù)據(jù)一致性就得不到確保?？刂品椒ㄓ袃煞N：一個是不允許讀者與寫者，或者寫者與寫者同時打開文件，但這會降低文件并發(fā)性，并可能造成死鎖；另一個是允許其同時打開文件，由OS為用戶提供對應(yīng)互斥伎倆，文件使用者借用這種伎倆確保對文件同時共享不發(fā)生沖突。第34頁8.3.2文件目錄管理如上所述，文件目錄是以目錄文件形式存放，當(dāng)存取一個文件時，往往需要訪問多級文件目錄，假如對每一級目錄訪問都需要到文件存放設(shè)備上去搜索，勢必占用過多CPU時間，若在系統(tǒng)開啟時，把全部目錄文件讀入內(nèi)存，由系統(tǒng)直接在內(nèi)存實施對各級目錄搜索則即使提升了訪問速度，但需要內(nèi)存容量太大。普通來說，系統(tǒng)只把當(dāng)前正在使用那些文件目錄表（打開文件表—加緊文件檢索方法之三）復(fù)制到內(nèi)存中，為此，系統(tǒng)提供兩種特殊操作：其一是把相關(guān)目錄文件復(fù)制到內(nèi)存指定區(qū)，通常稱為打開文件(Open)；其二是提供用戶不再訪問相關(guān)文件目錄文件刪除操作，通常稱為關(guān)閉文件(Close)。第35頁8.4文件存放空間分配與管理由文件存放結(jié)構(gòu)可知，文件信息交換都是以塊為單位進(jìn)行。所以，將文件存放設(shè)備稱為塊設(shè)備，這里介紹存放空間管理實際上是對文件塊空間而言，詳細(xì)說是指空閑塊組織與回收。普通來說，空閑塊空間分配經(jīng)常有兩種方式：一個靜態(tài)分配；另一個是動態(tài)分配。另外在分配區(qū)域上，能夠?qū)⒁粋€文件分配在一個完整分區(qū)中（以塊或簇為單位），常使用包含文件名、起始地址、長度文件分配表FAT等。第36頁8.4.1文件存放空間分配 文件空間分配常采?。哼B續(xù)分配、索引分配、鏈接分配3種方法。1.連續(xù)分配 連續(xù)分配方式是將文件存放在輔存連續(xù)存放區(qū)中。

第37頁8.4.1文件存放空間分配2.索引分配索引分配方法主要是利用文件分配表FAT給每個文件分配一個指出該文件索引表所在物理塊號表目，索引表所在索引塊與存放文件文件塊是分離。文件索引每個表目標(biāo)設(shè)置有兩種情況：一個是直接給出索引文件各物理塊；另一個是設(shè)置文件起始塊和長度，這有利于連續(xù)分配，也有利于節(jié)約索引表空間、提升效率，如圖所表示。第38頁8.4.1文件存放空間分配第39頁8.4.1文件存放空間分配3.鏈接分配鏈接分配文件空間方法是一個離散分配方式，適合用于文件長度需動態(tài)增減，或用戶對其文件應(yīng)用不十分明確情況，普通分配非連續(xù)輔存空間。采取鏈接表方法鏈接存放空間，鏈接空間大小大多以區(qū)或段為單位。第40頁8.4.1文件存放空間分配(1)以扇區(qū)為鏈接單位 這是給需動態(tài)改變文件分配若干磁盤扇區(qū)，這些扇區(qū)在磁盤上能夠不連續(xù)，而分配給同一文件各扇區(qū)按其上文件邏輯統(tǒng)計次序用鏈指針鏈接起來。(2)以區(qū)段(或簇)為單位分配 這不是以扇區(qū)為單位進(jìn)行分配，而是以區(qū)段(或稱簇)為單位進(jìn)行分配。第41頁8.4.2磁盤空間管理 文件磁盤存放空間管理包含磁盤空間塊分配和回收。1.盤塊盤塊是操作系統(tǒng)傳輸數(shù)據(jù)基本單位，盤塊大，I/O操作傳輸數(shù)據(jù)量多，傳輸性能好，但也會造成盤空間浪費。既要提升傳輸率，又要降低盤空間浪費，是文件系統(tǒng)追求目標(biāo)，盤塊是主要原因之一。第42頁8.4.2磁盤空間管理(1)邏輯塊 邏輯磁盤是文件系統(tǒng)中一個抽象存放概念。系統(tǒng)將邏輯磁盤視為一些有固定大小可隨機(jī)存取邏輯塊線性序列。磁盤驅(qū)動程序?qū)⑦壿媺K映射到物理介質(zhì)上。普通情況下，一個物理磁盤被分成物理上連續(xù)幾個分區(qū)，每個分區(qū)就是一個邏輯磁盤，又稱磁盤分區(qū)。 通常所說磁盤分區(qū)就是將每一個分區(qū)定義為一個盤，此盤就是一個邏輯磁盤。(2)盤區(qū) 磁盤分區(qū)是將磁盤上一組連續(xù)柱面空間組成一體，定義為一個盤區(qū)。其上可有一個獨立文件系統(tǒng)。不一樣類文件系統(tǒng)可占有不一樣盤，各自定義自己盤塊大小。第43頁8.4.2磁盤空間管理2.磁盤塊大小①磁盤塊大小。能夠了解為磁盤分配單位，它要求了文件系統(tǒng)分配粒度和磁盤I/O粒度，盤塊大，有利于增加系統(tǒng)性能，不一樣文件系統(tǒng)塊大小也不一樣，F(xiàn)FS（FreeBSD快速文件系統(tǒng)）可大于等于4KB，NTFS（NT內(nèi)核文件系統(tǒng)，簇大小并不依賴于磁盤或分區(qū)大?。┛纱蟮?4KB，F(xiàn)AT32簇大小可到達(dá)32KB。②片斷：是盤塊組成單位。第44頁8.4.2磁盤空間管理3.盤塊管理 盤塊管理慣用盤圖，鏈表和i節(jié)點等伎倆，因文件系統(tǒng)而異。(1)盤圖法 盤圖也稱字位映像圖，是一個慣用方法，它用位(bit)值0、1來表示磁盤上對應(yīng)物理塊是否被分配，bit值為1表示對應(yīng)物理塊被分配，為0表示對應(yīng)物理塊為空閑。 對應(yīng)一串連續(xù)bit值，按字節(jié)組成一張表，此表能夠把一個完整磁盤使用情況記載下來。第45頁盤圖法分配時：b（塊號）=n（字長）*i（行號）+j（列號）回收時：i（行號）=b（塊號）divn（字長） j（列號）=b（塊號）modn（字長）n位m字0123456701100011110101111121100001134567第46頁8.4.2磁盤空間管理(2)鏈接法①鏈接索引塊。 這是一個慣用方法，它首先是選擇若干空閑物理塊建立索引表塊，假設(shè)這么塊大小為1KB，能夠設(shè)512個表目，每個表目占用16位，以此表示一個空閑物理塊塊號，則每個表目對應(yīng)一個空閑物理塊。 而后將這些含有空閑塊號索引塊之間用鏈接方式鏈接起來，即每個索引塊第0個表目作為鏈表指針，指向下一個索引塊，或鏈尾標(biāo)志。第47頁8.4.2磁盤空間管理鏈接索引塊：第48頁8.4.2磁盤空間管理②分配與回收空閑塊。 為了操作方便，通常將索引鏈表中鏈頭指針?biāo)赶蛩饕龎K表目中留出空項(其它索引塊表目項全填滿)，當(dāng)文件系統(tǒng)分配盤空間時從鏈表頭索引塊塊尾開始，直到該索引塊第0個表目，假如該索引塊僅剩下第0個表目，則將該表目標(biāo)內(nèi)容讀到特定塊鏈頭指針中，然后將原鏈頭指針指向索引塊T，分給請求分配空閑塊文件。 空閑塊回收則相反，僅將釋放空閑塊塊號加到鏈頭指針指出索引表塊尾部表目中即可。第49頁8.4.2磁盤空間管理—Unix系統(tǒng)示例在Unix操作系統(tǒng)中，把磁盤存放空間空閑塊成組連接。每100個空閑塊為一組，每一組第一個空閑塊中登記下一組空閑塊磁盤物理塊號和空閑塊總數(shù)，最終不足100塊那部分磁盤物理塊及塊數(shù)記入專用塊（超級塊）中。第50頁Unix系統(tǒng)示例

假定共有空閑塊438塊，編號從12到449?？臻e塊數(shù)395049…12…空閑塊數(shù)100150149…5251空閑塊數(shù)100250249…152151空閑塊數(shù)100350349…252251空閑塊數(shù)1000449…352351專用塊50#150#250#