操作系統(tǒng)課件章管理

第六章文件管理6.1概述6.2文件的邏輯結(jié)構(gòu)6.3外存分配方式6.4文件目錄管理6.5文件存儲(chǔ)空間管理6.6文件系統(tǒng)的可靠性和安全性6.7文件系統(tǒng)的數(shù)據(jù)一致性控制6.1概述

所有的計(jì)算機(jī)應(yīng)用程序都要:存儲(chǔ)信息,檢索信息三個(gè)基本要求：能存儲(chǔ)大量信息、長(zhǎng)期保存信息、可共享信息解決方法:

把信息以文件形式存在磁盤或其他介質(zhì)上通過操作系統(tǒng)管理文件：文件的結(jié)構(gòu),命名,存取,使用,保護(hù)和實(shí)現(xiàn)方法用戶觀點(diǎn)(方便)：如何命名,如何訪問,如何共享,如何保護(hù)文件。操作系統(tǒng)觀點(diǎn)(高效)：文件目錄怎樣實(shí)現(xiàn),怎樣管理存儲(chǔ)空間,文件存儲(chǔ)位置,磁盤實(shí)際運(yùn)作方式(與設(shè)備管理的接口)等等6.1.1文件與文件系統(tǒng)計(jì)算機(jī)中用到大量的信息(程序和數(shù)據(jù))資源,平時(shí)總是把它們以文件的形式長(zhǎng)期存放在外存中,需要時(shí)可隨時(shí)調(diào)入內(nèi)存。文件系統(tǒng)就是統(tǒng)一管理這些信息資源的OS軟件,它管理文件的存儲(chǔ)、檢索和更新,提供安全可靠的共享和保護(hù)手段,方便的給用戶使用。1.文件文件是具有文件名的若干(數(shù)目不定)相關(guān)元素的集合,它是文件系統(tǒng)中的最大數(shù)據(jù)單位;可分為有結(jié)構(gòu)文件和無結(jié)構(gòu)文件;有結(jié)構(gòu)文件的元素是記錄,記錄是有意義的數(shù)據(jù)項(xiàng)的集合,無結(jié)構(gòu)文件則是一個(gè)字符流,稱為流式文件。文件名:ASCII碼和漢字組成,支持文件擴(kuò)展名文件屬性:文件類型、文件(當(dāng)前)長(zhǎng)度、文件物理位置、文件建立時(shí)間3.記錄有結(jié)構(gòu)文件中,

一組相關(guān)的數(shù)據(jù)項(xiàng)組成記錄,若干條記錄組成文件,在各記錄中能夠唯一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)集合稱為關(guān)鍵字(key),通常用一個(gè)數(shù)據(jù)項(xiàng)作為關(guān)鍵字。2.數(shù)據(jù)項(xiàng)有結(jié)構(gòu)文件中,數(shù)據(jù)項(xiàng)是最低級(jí)的數(shù)據(jù)組織形式。(1)基本數(shù)據(jù)項(xiàng):用于描述一個(gè)對(duì)象的某種屬性的數(shù)據(jù),是數(shù)據(jù)組織中可以命名的最小邏輯單位,又稱為字段。(2)組合數(shù)據(jù)項(xiàng):由若干個(gè)基本數(shù)據(jù)項(xiàng)組成,簡(jiǎn)稱組項(xiàng)。記錄1記錄2……記錄i……記錄n數(shù)據(jù)項(xiàng)1數(shù)據(jù)項(xiàng)2……數(shù)據(jù)項(xiàng)n文件4.文件系統(tǒng)模型(1)文件系統(tǒng)管理的對(duì)象其屬性(相關(guān)的數(shù)據(jù)結(jié)構(gòu))

文件、目錄、存儲(chǔ)空間。(2)對(duì)對(duì)象操縱和管理的軟件集合讀寫管理、目錄管理、共享和保護(hù)管理、存儲(chǔ)空間管理、地址映射、系統(tǒng)維護(hù)、物理I/O、設(shè)備驅(qū)動(dòng)(3)向用戶提供一個(gè)方便使用的接口命令接口、程序接口文件系統(tǒng)接口對(duì)對(duì)象操縱和管理的軟件集合對(duì)象及其屬性文件系統(tǒng)三層膜型用戶(程序)SurfaceLayoutSpindleSurfaceTracksTrackkSectorsGapsAdaptedfrom:ComputerSystems:AProgrammer’sPerspectivePlatterViewSurface0Surface1Surface2Surface3Surface4Surface5CylinderkSpindlePlatter0Platter1Platter2Adaptedfrom:ComputerSystems:AProgrammer’sPerspectiveDiskinActionSpindleRecordsApplicationsStructuredRecordFilesRecord-StreamTranslationStream-BlockTranslationByteStreamFilesStoragedeviceStream-BlockTranslationb0b1b2bi......5.文件系統(tǒng)的功能(1)統(tǒng)一的存儲(chǔ)空間管理,實(shí)施存儲(chǔ)空間的分配與回收(2)實(shí)現(xiàn)文件的按名存取名字空間映射

存儲(chǔ)空間(邏輯地址轉(zhuǎn)換為物理地址)(3)實(shí)現(xiàn)文件信息的共享,并提供文件的保護(hù)和保密措施(4)對(duì)文件的讀寫管理、目錄管理(5)系統(tǒng)維護(hù)及向用戶提供有關(guān)信息(6)提供與I/O設(shè)備的統(tǒng)一接口(7)向用戶提供方便使用的命令接口和程序接口

(提供對(duì)文件系統(tǒng)和對(duì)文件的操作命令和語句)

文件系統(tǒng)在OS接口中占的比例最大,用戶使用OS的感覺在很大程度上取決于對(duì)文件系統(tǒng)的使用效果.6.1.2文件類型為了提高系統(tǒng)管理文件的效率;提高用戶界面友好性,對(duì)文件進(jìn)行分類。1.按文件性質(zhì)和用途分類系統(tǒng)文件：由系統(tǒng)軟件構(gòu)成的文件用戶文件：由用戶產(chǎn)生的各種文件庫文件：標(biāo)準(zhǔn)子程序及常用的例程構(gòu)成的文件2.按信息保存期限分類臨時(shí)文件；永久文件；檔案文件3.按文件中的數(shù)據(jù)形式分類源文件、目標(biāo)文件、可執(zhí)行文件、數(shù)據(jù)文件4.按文件的存儲(chǔ)控制屬性分類只執(zhí)行文件；只讀文件；讀寫文件。5.按文件的邏輯結(jié)構(gòu)分類流式文件(無結(jié)構(gòu))；記錄式文件(有結(jié)構(gòu))。7.按文件的物理結(jié)構(gòu)分類順序(連續(xù))文件；鏈接文件；索引文件8.UNIX系統(tǒng)將文件分為三類普通文件(regular)

包含的是用戶信息,一般為ASCII或二進(jìn)制文件目錄文件(directory)

管理文件系統(tǒng)的系統(tǒng)文件特殊文件(specialfile)設(shè)備文件(將外設(shè)看作文件)

字符設(shè)備文件:用于模仿串行I/O設(shè)備,如終端,打印機(jī),網(wǎng)絡(luò)等塊設(shè)備文件:模仿磁盤

為了方便系統(tǒng)和用戶了解文件的類型,常把文件類型作為擴(kuò)展名放在文件名的后面,二者之間用"."隔開。6.1.3文件操作1.文件的"打開"和"關(guān)閉"操作

"打開"(open)文件,是系統(tǒng)將指名文件的屬性(類型,外存物理位置等)從外存拷貝到內(nèi)存打開文件表的一個(gè)表目中,并將該表目的編號(hào)(索引號(hào))返回給用戶。此后,用戶對(duì)文件的操作直接通過索引號(hào)進(jìn)行,避免了對(duì)文件的再次檢索。

"關(guān)閉"(close)操作,將內(nèi)存中的已修改的數(shù)據(jù)寫到外存上,并將對(duì)應(yīng)表目從打開文件表中刪除。2.基本操作創(chuàng)建文件:分配外存空間,建目錄項(xiàng)填入各種屬性刪除文件:將該目錄項(xiàng)置為空項(xiàng),釋放外存空間讀文件寫文件:目錄項(xiàng)中得文件在外存位置,讀寫截?cái)辔募?將文件內(nèi)容置空設(shè)置文件讀寫的位置:設(shè)置文件讀寫指針的位置6.2文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu):從用戶角度看文件的組織形式文件的物理結(jié)構(gòu):文件在外存上的存儲(chǔ)組織形式6.2.1文件的邏輯結(jié)構(gòu)類型

1.有結(jié)構(gòu)文件(記錄文件)

文件是由若干個(gè)記錄組成,每條記錄有其內(nèi)部結(jié)構(gòu)按記錄長(zhǎng)度分:定長(zhǎng)記錄、變長(zhǎng)記錄按記錄間的關(guān)系分:順序、索引、索引順序

2.無結(jié)構(gòu)文件又稱為流式文件,是元素長(zhǎng)度為1的無結(jié)構(gòu)字節(jié)流,如:源程序,可執(zhí)行文件,庫函數(shù),C語言的數(shù)據(jù)文件等。在UNIX系統(tǒng)中所有的文件被看作流式文件。好處：提供很大的靈活性。一條記錄一個(gè)字節(jié)流式文件記錄文件6.2.2順序文件

1.文件的邏輯排序

串結(jié)構(gòu)：各記錄的邏輯順序按存入的時(shí)間排序。有序結(jié)構(gòu)：各記錄的邏輯順序按關(guān)鍵字排序。

2.對(duì)順序文件的讀/寫操作順序文件只能順序讀或順序?qū)?可設(shè)置讀/寫指針Rptr和Wptr,指向下一記錄的邏輯地址。對(duì)定長(zhǎng)記錄:

每當(dāng)讀完一條記錄時(shí)執(zhí)行:Rptr=Rptr+L

每當(dāng)寫完一條記錄時(shí)執(zhí)行:Wptr=Wptr+L

對(duì)變長(zhǎng)記錄:

每當(dāng)讀完一條記錄時(shí)執(zhí)行:Rptr=Rptr+Li

每當(dāng)寫完一條記錄時(shí)執(zhí)行:Wptr=Wptr+Li3.優(yōu)點(diǎn):批量存取效率高,缺點(diǎn):查找增刪低效不方便6.2.3索引文件對(duì)定長(zhǎng)記錄文件,要查找第i個(gè)紀(jì)錄,可直接計(jì)算:Ai=A0+i*L(A0和Ai是第0和第i個(gè)紀(jì)錄的邏輯地址)

對(duì)變長(zhǎng)記錄文件,要查找第i個(gè)紀(jì)錄,則要計(jì)算:

Ai=A0+

i

+ΣLi

(假定每個(gè)紀(jì)錄前用1字節(jié)存儲(chǔ)長(zhǎng)度)

要實(shí)現(xiàn)直接存取文件,對(duì)定長(zhǎng)記錄用公式計(jì)算很方便,但對(duì)變長(zhǎng)記錄卻很困難;為此可建立一張索引表,索引表本身是定長(zhǎng)記錄文件,可直接計(jì)算在索引表上找第i個(gè)紀(jì)錄,按其指針值找到指向的記錄。i-1i=0R0R1...Ri...0L01L1...iLi...索引表邏輯文件

如果要按給定的關(guān)鍵字查找對(duì)應(yīng)的記錄,對(duì)于定長(zhǎng)記錄文件,當(dāng)紀(jì)錄無序時(shí)只能順序查找,效率很低;當(dāng)紀(jì)錄是按的關(guān)鍵字排序時(shí)可直接用折半查找,但插入和刪除效率很低。對(duì)變長(zhǎng)記錄文件,如果沒有索引表只能順序查找,效率很低;

而加了索引表后,

由于索引表是按紀(jì)錄的關(guān)鍵字排序的,檢索時(shí),可用折半查找索引表,按其指針值指向的記錄與給定的關(guān)鍵字比較,查到為止。當(dāng)向索引文件增加新紀(jì)錄時(shí)需要修改索引表。優(yōu)點(diǎn)：檢索數(shù)度塊。缺點(diǎn)：每個(gè)記錄都對(duì)應(yīng)一個(gè)索引項(xiàng),存儲(chǔ)費(fèi)用大。6.2.3索引順序文件對(duì)變長(zhǎng)記錄文件,用索引表存儲(chǔ)費(fèi)用大,結(jié)合索引文件和順序文件的優(yōu)點(diǎn),構(gòu)成索引順序文件;所有記錄邏輯上按關(guān)鍵字有序排列,并將記錄分為若干組,索引表為每組的第一個(gè)記錄建立一個(gè)索引表項(xiàng),檢索時(shí)先根據(jù)索引表鍵值確定該記錄在哪一組,再按該表項(xiàng)指針指向的主文件中的位置順序查找到所要的記錄。如AnFenAnKan...BaoHe...AnFenBaoHe...LanLin...索引表邏輯文件姓名其它屬性鍵邏輯地址

如果某順序文件的記錄數(shù)為N,則順序檢索平均查找N/2個(gè)記錄。而對(duì)于索引順序文件每組√N(yùn)個(gè)記錄,平均查找√N(yùn)個(gè)記錄;效率大大提高。對(duì)于特大型文件可建立多級(jí)索引表。6.2.4直接文件和哈希文件1.直接文件:根據(jù)給定的記錄鍵值,直接獲得指定記錄的物理地址,這種由給定的記錄鍵值到記錄的物理地址的轉(zhuǎn)換稱為鍵值轉(zhuǎn)換,關(guān)鍵是用什么函數(shù)進(jìn)行轉(zhuǎn)換。2.哈希文件:用哈希函數(shù)(或稱散列函數(shù))進(jìn)行鍵值轉(zhuǎn)換,為了能實(shí)現(xiàn)文件存儲(chǔ)空間的動(dòng)態(tài)分配,通常由哈希函數(shù)求得的不是記錄的地址,而是指向目錄表相應(yīng)表項(xiàng)的指針,表項(xiàng)的內(nèi)容指向相應(yīng)記錄所在的物理塊。如

目錄表Hash(k)鍵值哈希函數(shù)物理塊6.3外存分配方式

文件的物理結(jié)構(gòu)與外存分配方式有關(guān)。常用分配方式有:連續(xù)分配、鏈接分配和索引分配。對(duì)應(yīng)的物理結(jié)構(gòu):連續(xù)結(jié)構(gòu)、鏈接式結(jié)構(gòu)和索引結(jié)構(gòu)6.3.1.連續(xù)分配為每個(gè)文件分配一組連續(xù)的相鄰物理塊,形成的文件結(jié)構(gòu)稱順序文件結(jié)構(gòu),物理文件稱順序文件。這種分配方式保證了記錄的邏輯順序,與占用盤塊的物理順序一致;在目錄項(xiàng)的"文件物理地址"字段中存放該文件的第一個(gè)記錄所在盤塊號(hào)和文件長(zhǎng)度(塊數(shù))。如:目錄filestartlengthf1 02tr 143mail 196…...…2.連續(xù)分配的優(yōu)缺點(diǎn)優(yōu)點(diǎn):順序存取簡(jiǎn)單容易,也支持直接(隨機(jī))存取。順序存取速度快,尋道次數(shù)和尋道時(shí)間最少。也適合隨機(jī)訪問,計(jì)算出盤塊地址直接訪問。缺點(diǎn):易產(chǎn)生外部碎片,降低外存空間的利用率;可利用緊湊法將外部碎片拼接成連續(xù)存儲(chǔ)空間,但緊湊一次需要進(jìn)行大量的磁盤操作花費(fèi)大量的時(shí)間。不利于文件的插入和刪除。必須事先知道文件的大小,對(duì)于動(dòng)態(tài)增長(zhǎng)的文件效果較差。需要估算預(yù)留的連續(xù)外存空間,預(yù)留空間不足將引起大片磁盤空間的移動(dòng),預(yù)留空間太大將使大量的外存空間長(zhǎng)期空閑。6.3.2鏈接分配

將文件存放在多個(gè)離散的盤塊中,同一文件的盤塊鏈接成一個(gè)鏈表,消除外部碎片,顯著的提高了外存空間的利用率,有利于文件插入和刪除,有利于文件的動(dòng)態(tài)擴(kuò)充。1.隱式鏈接在文件目錄的每個(gè)目錄項(xiàng)中,都含有指向鏈接文件第一個(gè)盤塊和最后一個(gè)盤塊的指針,而在每個(gè)盤塊中都含有指向下一個(gè)盤塊的指針,只有508字節(jié)供使用。缺點(diǎn):

只適合順序訪問,隨機(jī)訪問要從頭查找極低效。可靠性差,盤塊的指針出現(xiàn)問題會(huì)導(dǎo)致鏈斷開。更多的尋道次數(shù)和尋道時(shí)間。解決方法:

可將幾個(gè)盤塊組成一個(gè)簇,減少查找指定塊的時(shí)間。Firstblock…Head:417...LengthByte0Byte4095...LengthByte0Byte4095...LengthByte0Byte4095...Block0Block1BlockN-1…LinkedListsEachBlockContainsaHeaderWithNumberofBytesintheBlock-AllowsStorageofVariableLengthBlocksPointertoNextBlockBlocksNeedNotBeContiguousFilesCanExpandandContractConsequently,SeeksCanBeSlow

2.顯式鏈接將鏈接文件各物理塊的指針存放在內(nèi)存的一張鏈接表中,整個(gè)磁盤僅設(shè)一張表稱為文件分配表(FAT),表項(xiàng)的序號(hào)是物理盤塊號(hào),每個(gè)表項(xiàng)中存放鏈接指針(下一盤塊號(hào))。每個(gè)文件的第一個(gè)盤塊號(hào)填入該文件的文件控制塊(FCB)的"物理地址"字段中。記錄的查找過程全部在內(nèi)存中進(jìn)行,檢索速度快、訪問磁盤磁盤次數(shù)少、可靠性高。（MS-DOS的FAT）FCBf1FAT9^4073111^012345678910111213...2FCBf26FAT中每項(xiàng)的大小與磁盤最大容量以及簇的大小有關(guān)471^6.3.3索引分配

鏈接分配存在的問題：要順序查找許多盤塊號(hào),不支持高效的直接存取。

FAT占用較大的內(nèi)存空間。1.單級(jí)索引分配

為每個(gè)文件分配一個(gè)集中存放的索引塊(表),該表實(shí)質(zhì)就是磁盤塊地址數(shù)組,其中第i項(xiàng)存放指向文件的第i塊盤塊號(hào),該文件的目錄項(xiàng)中存儲(chǔ)了指向該索引塊的指針;支持直接存取,如:記錄號(hào)m第i塊盤塊號(hào)012345...91611025-1...索引塊目錄file塊號(hào)

f119fr31….........2.多級(jí)索引分配對(duì)于大文件,當(dāng)分配的盤塊號(hào)已裝滿一個(gè)索引塊時(shí),必須另分配索引塊,各索引塊通過指針連結(jié)起來,文件太大索引塊太多時(shí),檢索索引塊將是低效的,此時(shí)應(yīng)為這些索引塊再建立一級(jí)索引,形成了兩級(jí)索引,必要時(shí)還可建立更多級(jí)的索引分配方式。3.混合索引分配方式

索引分配方式的索引塊花費(fèi)較多空間,小文件索引塊利用率更低。UNIX用混合索引模式避免此缺點(diǎn)。每個(gè)文件的索引結(jié)點(diǎn)含13個(gè)地址項(xiàng)i.addr(0)~i.addr(12),每項(xiàng)2個(gè)字節(jié);前10項(xiàng)存放直接地址(物理塊號(hào)),若文件大于40kB，則用i.addr(10)指向單級(jí)索引塊進(jìn)行一次間接尋址,該塊中最多可放1k個(gè)物理塊號(hào),文件可長(zhǎng)達(dá)4MB;還可用i.addr(11)和i.addr(12)作為二次和三次間接尋址,文件最大長(zhǎng)度分別可達(dá)4GB和4TB。^......^......^......datadata...datadatadata...data^......datadata...datadatadata...datamodeownerstimestampssizeblockcounti.addr(

0)i.addr(

1)…i.addr(

9)i.addr(

10)i.addr(

11)i.addr(

12)...間接地址項(xiàng)混合索引方式直接地址項(xiàng)Datamodeowner…Directblock0Directblock1…Directblock11SingleindirectDoubleindirectTripleindirectinodeDataDataIndexDataDataIndexIndexIndexIndexIndexIndexIndexIndexDataDataDataDataUNIXFilesWith4KBlocks4Kx12=48KForSingleIndirect1000Indices/Block4Kx1000=4MForDoubleIndirect4Kx1,000,000ForTripleIndirect4Kx????????6.3.4

文件物理結(jié)構(gòu)、存取方式與存儲(chǔ)介質(zhì)的關(guān)系存取方式:順序存取方式,隨機(jī)(直接)存取方式存儲(chǔ)介質(zhì)物理結(jié)構(gòu)存取方式磁帶連續(xù)結(jié)構(gòu)順序存取磁盤連續(xù)鏈接索引順序順序順序隨機(jī)

隨機(jī)

對(duì)比三種分配的優(yōu)缺點(diǎn)連續(xù)分配

優(yōu)點(diǎn):順序存取簡(jiǎn)單高效,尋道距離次數(shù)少,訪問速度快,

也適合隨機(jī)訪問,算出塊地址直接訪問。缺點(diǎn):有外部碎片,外存利用率低,插入和刪除不容易鏈接分配優(yōu)點(diǎn):消除外存碎片,外存利用率高,有利于文件的動(dòng)態(tài)擴(kuò)充,容易插入和刪除,缺點(diǎn):不適合隨機(jī)訪問,可靠性差,尋道次數(shù)多速度慢

顯式鏈接分配可顯著減少尋道次數(shù),提高檢索速度,但FAB占用了較大的內(nèi)存空間索引分配優(yōu)點(diǎn):鏈接分配的全部?jī)?yōu)點(diǎn),還適合隨機(jī)訪問,尋道次數(shù)少,檢索速度快。缺點(diǎn):索引塊費(fèi)較多空間,小文件尤甚,混合索引可避免。課后題:P2196,7,9,106.4文件目錄管理目錄管理的基本要求:實(shí)現(xiàn)"按名存取"提高對(duì)目錄的檢索速度允許文件共享允許文件重名6.4.1文件控制塊和索引結(jié)點(diǎn)1.文件控制塊(FCB):

是操作系統(tǒng)為管理文件而設(shè)置的用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu),存放了為管理文件所需的所有有關(guān)信息。文件和FCB一一對(duì)應(yīng),FCB的有序集稱為文件目錄,一個(gè)FCB就是一個(gè)目錄項(xiàng),為實(shí)現(xiàn)對(duì)文件目錄的管理,通常將文件目錄以文件的形式保存在外存上,這個(gè)文件就叫目錄文件。文件控制塊的內(nèi)容：基本信息:

文件名,擴(kuò)展名,文件主名文件物理地址:存放設(shè)備名,起始盤塊號(hào),文件長(zhǎng)度文件邏輯結(jié)構(gòu):流式或記錄文件,定長(zhǎng)或不定長(zhǎng)文件物理結(jié)構(gòu):順序、鏈接式、索引文件存取控制信息:

文件主、核準(zhǔn)用戶和一般用戶的存取權(quán)限使用信息:

文件的建立日期,最后修改日期,最后訪問日期,當(dāng)前使用信息(共享計(jì)數(shù),是否被鎖住,已被修改是否存盤)文件名擴(kuò)展名屬性備用時(shí)間日期起始?jí)K號(hào)盤塊數(shù)MS-DOS的文件控制塊(32個(gè)字節(jié))2.索引結(jié)點(diǎn)(i結(jié)點(diǎn))

(1)索引結(jié)點(diǎn)的引入當(dāng)目錄中文件很多時(shí),文件目錄要占用大量的盤塊,查找目錄時(shí)需要將這些盤塊逐塊調(diào)入內(nèi)存,將給定的文件名與目錄中的文件名逐一比較;假如一個(gè)FCB為64B,1KB的盤塊只能存16個(gè)FCB,一個(gè)目錄有640個(gè)FCB,需占用40個(gè)盤塊,查找一個(gè)目錄平均要啟動(dòng)磁盤20次。檢索目錄時(shí)只用到了文件名,如果將FCB中的文件名而和描述信息分開存儲(chǔ),就可以增加目錄的每個(gè)盤塊中的文件數(shù),減少訪盤次數(shù),加快檢索速度;UNIX系統(tǒng)中就采用這種方法,將文件描述信息單獨(dú)存放在索引結(jié)點(diǎn)中(簡(jiǎn)稱i結(jié)點(diǎn)),目錄項(xiàng)僅由文件名和指向該文件對(duì)應(yīng)的i結(jié)點(diǎn)的指針構(gòu)成,UNIX的目錄項(xiàng)僅占16B,1KB的盤塊能存64個(gè)目錄項(xiàng)訪盤次數(shù)降到原來的1/4。(2)磁盤索引結(jié)點(diǎn)存放在磁盤上的索引結(jié)點(diǎn),每個(gè)文件有唯一的一個(gè)modeownerstimestampssizeblockcounti.addr(

0)i.addr(

1)…i.addr(

9)i.addr(

10)i.addr(

11)i.addr(

12)文件類型:普通文件、目錄文件特殊文件文件主:所有者和小組標(biāo)識(shí)符時(shí)間標(biāo)記:文件最近被訪問時(shí)間文件最近被修改時(shí)間

i結(jié)點(diǎn)最近被修改時(shí)間文件長(zhǎng)度:字節(jié)長(zhǎng)度連接計(jì)數(shù):指向該文件的指針計(jì)數(shù)直接地址:10項(xiàng)直接盤塊地址間接地址:3種級(jí)別的索引塊地址(3)磁盤索引結(jié)點(diǎn)內(nèi)存索引結(jié)點(diǎn)存放在內(nèi)存上的索引結(jié)點(diǎn),文件打開時(shí)將磁盤索引結(jié)點(diǎn)拷貝到內(nèi)存的索引結(jié)點(diǎn)中,并增加一下幾項(xiàng)當(dāng)前正使用的內(nèi)容。(1)索引結(jié)點(diǎn)編號(hào):用來標(biāo)識(shí)內(nèi)存索引結(jié)點(diǎn)(2)狀態(tài):i結(jié)點(diǎn)是否上鎖或被修改(3)訪問計(jì)數(shù):正在訪問此i結(jié)點(diǎn)的進(jìn)程數(shù)(4)所屬的邏輯設(shè)備號(hào)(5)鏈接指針:指向空閑鏈表和散列隊(duì)列的指針6.4.2目錄結(jié)構(gòu)1.單級(jí)目錄結(jié)構(gòu)為所有文件建立一個(gè)目錄文件(組成一線性表)優(yōu)點(diǎn):

簡(jiǎn)單，易實(shí)現(xiàn)缺點(diǎn):(1)目錄項(xiàng)太多時(shí)查找速度慢平均檢索時(shí)間長(zhǎng)

(2)不允許重名,限制了用戶對(duì)文件的命名

(3)不便于實(shí)現(xiàn)文件共享,只適用于單用戶環(huán)境2.二級(jí)目錄結(jié)構(gòu)為改變一級(jí)目錄文件目錄命名沖突,而改進(jìn),可用不同文件名共享同一文件。目錄分為兩級(jí):一級(jí)稱為主文件目錄MFD,給出用戶名,用戶子目錄所在的物理位置;二級(jí)稱為用戶文件目錄UFD(用戶子目錄),給出該用戶所有文件的FCB。優(yōu)點(diǎn):提高了檢索目錄的速度,解決了文件重名問題和文件共享問題,不同用戶用不同文件名訪問同一文件。缺點(diǎn)：增加了系統(tǒng)空間開銷MFD

用戶名指針ZhangWangLi…...UFD(Z)FCB(fz1)FCB(fz2)FCB(fz3)…...fz1fz2fz3...UFD(W)FCB(fw1)FCB(fw2)…...fw1fw2...UFD(L)FCB(fl1)FCB(fl2)…...fl1fl2...二級(jí)目錄結(jié)構(gòu)3.多級(jí)目錄結(jié)構(gòu)(樹型目錄)目錄結(jié)構(gòu):大型文件系統(tǒng)通常采用三級(jí)或三級(jí)以上的目錄結(jié)構(gòu),構(gòu)成樹型目錄,主目錄稱為根目錄,其它目錄均作為樹的分支結(jié)點(diǎn),文件稱為樹葉。路徑名:

在樹型目錄結(jié)構(gòu),從根目錄到各文件,用經(jīng)歷的全部目錄名和文件名表示唯一的路徑名。當(dāng)前目錄:

可為每個(gè)進(jìn)程設(shè)置一個(gè)"當(dāng)前目錄",進(jìn)程對(duì)文件的訪問都相對(duì)于"當(dāng)前目錄"進(jìn)行。優(yōu)點(diǎn)：層次結(jié)構(gòu)清晰,便于管理和保護(hù),解決重名問題,

文件共享問題,查找速度加快。缺點(diǎn)：增加了系統(tǒng)空間開銷,查找一個(gè)文件按路徑名逐層檢查,

由于每個(gè)文件都放在外存,

級(jí)數(shù)太多時(shí)

訪盤次數(shù)增多影響速度。DEFABCeRSTfACacABabXYZDECSRsrxyzdecUNIX文件系統(tǒng)結(jié)構(gòu)iiiiiiiiiroot目錄binuserdev

bin目錄s1

user目錄LiuLidev目錄

Liu目錄f1t1

Li目錄t1e2

6.4.3目錄查詢技術(shù)1.線性檢索法單級(jí)目錄：用戶給出文件名,按名順序查找目錄項(xiàng)多級(jí)目錄根據(jù)路徑名順序查找各級(jí)目錄：全路徑名：從根開始相對(duì)路徑：從當(dāng)前路徑各級(jí)目錄未查到時(shí)應(yīng)停止查詢,返回"文件未找到",查到則根據(jù)盤塊號(hào)指針讀入下級(jí)目錄繼續(xù)查。2.Hash方法建立一張Hash索引文件目錄,利用Hash函數(shù)直接將文件名轉(zhuǎn)換為索引值直接查找,解決沖突的規(guī)則:(1)該目錄項(xiàng)為空則未找到

(2)文件名(或子目錄名)匹配則找到

(3)該目錄項(xiàng)非空則發(fā)生沖突,將Hash值加一常數(shù)(與目錄長(zhǎng)度互質(zhì))繼續(xù)查找1.外存的特點(diǎn)容量大,斷電后仍可保存信息,速度較慢,成本較低由兩部分組成:驅(qū)動(dòng)部分+存儲(chǔ)介質(zhì)種類很多,外存空間組織與地址與存取方式非常復(fù)雜I/O過程方式非常復(fù)雜2.用戶對(duì)外存的要求讀寫外存數(shù)據(jù),方便、高效、安全(1)讀寫時(shí)不涉及硬件細(xì)節(jié),使用邏輯地址和邏輯操作(2)存取速度盡可能快，容量大且空間利用率高(3)信息安全可靠,防止來自硬件的故障和他人的侵權(quán)(4)可以方便地共享,動(dòng)態(tài)擴(kuò)縮,攜帶拆卸,了解使用情況(5)以盡可能小的代價(jià)完成上述要求6.5文件存儲(chǔ)空間管理1.空閑表法(對(duì)應(yīng)與文件的連續(xù)分配方式)

(1)空閑表:與內(nèi)存動(dòng)態(tài)分區(qū)方式相似,為每個(gè)文件分配連續(xù)的空閑區(qū),建立一張空閑表,每個(gè)空閑區(qū)對(duì)應(yīng)一個(gè)表項(xiàng),存儲(chǔ)該空閑區(qū)的第一個(gè)盤塊號(hào)和空閑塊數(shù)。(2)存儲(chǔ)空間的分配和回收:與內(nèi)存動(dòng)態(tài)分配類似,采用首次適應(yīng)算法,循環(huán)首次適應(yīng)算法等,回收時(shí)要考慮是否與前區(qū)和后區(qū)合并的問題。2.空閑鏈表法空閑塊鏈:把所有空閑塊鏈成空閑塊鏈(對(duì)應(yīng)與文件的鏈接分配方式);還可以簇為單位,鏈成空閑簇鏈?？臻e鏈也可采用顯式鏈接在內(nèi)存建鏈表(MS-DOS)。(2)空閑盤區(qū)鏈:把所有空閑盤區(qū)(每個(gè)空閑區(qū)由連續(xù)的空閑塊組成),以區(qū)為單位鏈成一個(gè)空閑區(qū)鏈,每個(gè)空閑區(qū)含指向下一空閑區(qū)指針和空閑塊數(shù)6.5.1空閑表法和空閑鏈表法1.位示圖:

用一串二進(jìn)制位表示磁盤中所有盤塊的分配使用情況,每個(gè)盤塊對(duì)應(yīng)一位,1表示已分配,0表示空閑。2.

盤塊的分配:順序掃描位示圖,查找為0的位;返回對(duì)應(yīng)盤塊號(hào);位示圖對(duì)應(yīng)位改為13.盤塊的回收:將盤塊號(hào)轉(zhuǎn)換為位示圖位置將對(duì)應(yīng)位置0如：CP/M、Apple-DOS6.5.2.位示圖法

空閑表和空閑鏈表不適用于大型文件系統(tǒng)(表太長(zhǎng)),UNIX系統(tǒng)將這兩種方法相結(jié)合,將空閑盤塊分成組,每組第一塊存一個(gè)空閑表成組鏈接起來,兼二者之優(yōu)點(diǎn)克服了它們的缺點(diǎn)?！?..6.5.3.成組鏈接法1.空閑塊的組織:

(1)

空閑盤塊號(hào)棧:此棧存儲(chǔ)當(dāng)前正在分配的一組空閑盤塊號(hào)及本組尚有的空閑塊總數(shù)N,N兼作棧頂指針。如:N=100,S.free(0)—S.free(99)存儲(chǔ)當(dāng)前組空閑盤塊號(hào)

(2)

每組的第一塊存儲(chǔ)下一組空閑盤塊號(hào)棧形成鏈。

(3)最末組的空閑盤塊號(hào)棧存放在前一組的第一空閑塊中,其中的S.free(0)存放結(jié)束標(biāo)志。100300299…201NS.free(0)S.free(1)…S.free(99)100400399…301...990999…901............2.空閑塊的分配和回收:

利用空閑盤塊號(hào)棧。(1)分配:

N=N-1;if(N>0)分配S.free(N);else{m=S.free(N);讀入S.free(N);分配m;}(2)回收:if(N=100){寫入回收塊;N=0}S.free(N)=回收塊號(hào);N=N+1;100300299…201NS.free(0)S.free(1)…S.free(99)100400399…301...990999…901............課后題:P21912,15,18,19為什么？黑客技術(shù)

病毒技術(shù)惡意代碼黑客大聚會(huì)現(xiàn)代入侵攻擊技術(shù)攻擊經(jīng)驗(yàn)切磋現(xiàn)代入侵攻擊技術(shù)入侵知識(shí)交流現(xiàn)代入侵攻擊技術(shù)新一代主動(dòng)式惡意代碼2002惡意代碼對(duì)全球經(jīng)濟(jì)的影響($U.S.Billions)Source:ComputerEconomics01.02.02Nimda$635MCodeRed(s)$2.62BSirCam$1.15BJuly1901:05:002001攻擊速度

July1920:15:002001攻擊速度

MaliciousCodeMalware=

特洛伊木馬的由來大約在公元前12世紀(jì)，希臘向特洛伊城宣戰(zhàn)。這是因?yàn)樘芈逡镣踝咏俪至薙parta國(guó)王Menelaus的妻子Helen（據(jù)說是當(dāng)時(shí)最美的女子）。戰(zhàn)爭(zhēng)持續(xù)了10年，特洛伊城十分堅(jiān)固，希臘軍隊(duì)無法取得勝利。

最終，希臘軍隊(duì)撤退，在特洛伊城外留下很多巨大的木馬，里面藏有希臘最好的戰(zhàn)士。特洛伊城的人民看到這些木馬，以為是希臘軍隊(duì)留給他們的禮物，就將這些木馬弄進(jìn)城。到了夜晚，藏在木馬中的希臘士兵在Odysseus的帶領(lǐng)下打開特洛伊城的城門，讓希臘軍隊(duì)進(jìn)入，然后奪下特洛伊城。據(jù)說“小心希臘人的禮物”這一諺語就是出自這個(gè)故事。在計(jì)算機(jī)領(lǐng)域，特洛伊木馬是一段吸引人的程序，因?yàn)樗鼈兛蓤?zhí)行某些秘密任務(wù)。****惡意代碼紅蟲：多達(dá)225,000站點(diǎn)數(shù)小時(shí)內(nèi)攻破。惡意代碼Dakfjdjfdsafkdafldjdkjajfdlkiefjdksjalfdksajdlsakfdsalkfdkslafjdksafljddfksajfdjskajfdsjafdjsakjfdksjafkdjlsafjldksjafowjfejwaijiojkajfdkajdsajfdjsajfdjasfjdjsalfjlsdk惡意代碼

新一代主動(dòng)式惡意代碼極短時(shí)間內(nèi)（Flashworms---30s），利用優(yōu)化掃描的方法，感染近十萬個(gè)有漏洞的系統(tǒng),可以確定并記錄是否被擊中（4-5分鐘，感染近百萬臺(tái)系統(tǒng)）。掃描探測(cè)

傳遞復(fù)制被感染的機(jī)器

有漏洞的機(jī)器惡意代碼massrooter大型推土機(jī)廣發(fā)自動(dòng)攻擊程序Teso組織，面向wuftp2.6~2.7在幾十秒內(nèi)被侵入和控制

6.6文件共享與文件保護(hù)

一個(gè)文件(或子目錄)可以被多個(gè)用戶(進(jìn)程)共享使用;這樣可以節(jié)省時(shí)間和存儲(chǔ)空間,減少了用戶工作量。早期的文件共享方式有繞彎路法、連訪法和基本文件目錄法;當(dāng)前常用兩種文件共享方法,它們是：基于索引結(jié)點(diǎn)的共享方式利用符號(hào)鏈實(shí)現(xiàn)文件共享6.6.1基于索引結(jié)點(diǎn)的共享方式將共享文件或子目錄鏈接到多個(gè)用戶的目錄表中,此時(shí)目錄的結(jié)構(gòu)已不再是樹型結(jié)構(gòu)而是一個(gè)有向非循環(huán)圖。如果文件的描述信息直接存儲(chǔ)在用戶的目錄表中,當(dāng)某個(gè)用戶對(duì)文件修改時(shí)這些描述信息的內(nèi)容也可能發(fā)生變化,此時(shí)該文件的其它共享者目錄的對(duì)應(yīng)信息并未隨之改變,引起共享錯(cuò)誤。用索引結(jié)點(diǎn)可避免。UFD(W)

file1……UFD(Z)

file2…………count=2W/file1Z/file2索引結(jié)點(diǎn)

為了解決這一問題可以將目錄表中文件的描述信息存儲(chǔ)在索引結(jié)點(diǎn)中,而僅將文件名和指向索引結(jié)點(diǎn)的指針存放在目錄表中。索引結(jié)點(diǎn)中的count用作共享計(jì)數(shù)(鏈接計(jì)數(shù))。DEFABC

IJK

LN

GH

B/I

A/D/NB/KC/G

圖中表示有向非循環(huán)圖的目錄結(jié)構(gòu)，圓圈表示索引結(jié)點(diǎn)和文件本身。

UFD(C)

owner=Ccount=1鏈接前UFD(B)UFD(C)owner=Ccount=2鏈接后UFD(B)owner=Ccount=1所有者刪除后問題：刪除文件時(shí)怎樣考慮？當(dāng)文件主刪除文件時(shí)可能會(huì)發(fā)生指針懸空。6.6.2利用符號(hào)鏈(SymbolicLink)實(shí)現(xiàn)文件共享要使用戶B能共享用戶C的文件F,系統(tǒng)建立一個(gè)類型為L(zhǎng)INK的新文件,如起名為G(或仍為F),放在B的目錄中,該文件只包含被共享文件F的路徑名。此法稱為符號(hào)鏈接(SymbolicLinking),當(dāng)B要訪問G文件時(shí),被OS截獲,OS根據(jù)G的LINK類型確定它是符號(hào)鏈,再按此符號(hào)鏈找到共享文件F。當(dāng)文件主C刪除文件F后,若B試圖通過文件G符號(hào)鏈訪問F,則只會(huì)因找不到文件訪問失敗,不會(huì)發(fā)生指針懸空。

問題:

訪問時(shí)系統(tǒng)要按符號(hào)鏈逐個(gè)分量查找目錄,多次讀盤,系統(tǒng)開銷甚大。

優(yōu)勢(shì):

可在網(wǎng)絡(luò)環(huán)境下用,符號(hào)鏈可存網(wǎng)址和路徑

兩種方法的共同問題是遍歷文件系統(tǒng)并拷貝到磁帶上,對(duì)將多次編歷到共享文件,產(chǎn)生多個(gè)拷貝。6.6.3文件系統(tǒng)的安全性1.安全性確保的用戶不能存取某些文件。涉及到技術(shù)、管理、法律、道德和政治等問題安全性的兩個(gè)重要方面：(1)數(shù)據(jù)丟失:災(zāi)難、硬件或軟件故障、人的失誤可通過磁盤容錯(cuò)技術(shù)和備份(存放在另一處)來解決(2)入侵者積極的或消極的非技術(shù)人員的偶然窺視入侵者的窺視明確的偷竊企圖商業(yè)或軍事間諜活動(dòng)設(shè)計(jì)安全時(shí)要考慮是那一類入侵者2.防止OS的安全缺陷UNIX、TENEX、OS/360、Windows等都存在Logicbomb(邏輯炸彈),Morris(蠕蟲)利用安全缺陷(1)一般性的安全攻擊請(qǐng)求內(nèi)存頁、磁盤空間和磁帶并讀取其內(nèi)容嘗試非法的系統(tǒng)調(diào)用(非法參數(shù)、不合適的參數(shù))

在登錄過程中鍵入DEL,BREAK

寫一段程序欺騙用戶……

病毒(2)安全性的設(shè)計(jì)原則系統(tǒng)設(shè)計(jì)必須公開缺省屬性應(yīng)該不可訪問檢查當(dāng)前權(quán)限給每個(gè)進(jìn)程賦予一個(gè)最小的可能權(quán)限保護(hù)機(jī)制應(yīng)簡(jiǎn)單一致，嵌入到系統(tǒng)底層3.文件的保護(hù)機(jī)制(1)文件保護(hù)用于提供安全性的特定的操作系統(tǒng)機(jī)制。

(有權(quán)限的用戶,應(yīng)讓其進(jìn)行相應(yīng)操作,否則,應(yīng)禁止)

實(shí)現(xiàn)：用戶驗(yàn)證、存取控制(2)用戶驗(yàn)證用戶登錄,檢驗(yàn)其身份(1)口令(2)物理鑒定磁卡，指紋，簽名分析，手指長(zhǎng)度分析(3)對(duì)策(3)存取控制審查用戶的權(quán)限審查本次操作的合法性存取控制矩陣

用戶文件

A B C

User1 rw r w User2 e

文件的二級(jí)存取控制第一級(jí)：對(duì)訪問者的識(shí)別用戶分類：文件主(owner)

同組用戶(group)、其它用戶(other)第二級(jí)：對(duì)操作權(quán)限的識(shí)別操作分類：讀操作(r)、寫操作(w)

執(zhí)行操作(x)、不能執(zhí)行任何操作(-)6.6.4磁盤容錯(cuò)技術(shù)通過設(shè)置冗余的磁盤驅(qū)動(dòng)器、磁盤控制器等部件,來提高可靠性的技術(shù)。1.第一級(jí)磁盤容錯(cuò)技術(shù)SFT-1

因磁盤表面缺陷造成的數(shù)據(jù)破壞或丟失,包括雙份目錄、雙份文件分配表和寫后讀校驗(yàn)等措施(1)雙份目錄和雙份文件分配表(2)熱修復(fù)重定向和寫后讀校驗(yàn)熱修復(fù)重定向:將磁盤的2~3%作為熱修復(fù)重定向區(qū)寫后讀校驗(yàn):寫盤后立即讀并于原數(shù)據(jù)校驗(yàn)2.第二級(jí)磁盤容錯(cuò)技術(shù)SFT-2(1)磁盤鏡像兩個(gè)磁盤驅(qū)動(dòng)器互為備份(2)磁盤雙工通道、磁盤控制器和磁盤驅(qū)動(dòng)都為雙份主機(jī)磁盤控制器通道主機(jī)磁盤控制器磁盤控制器通道通道數(shù)據(jù)0數(shù)據(jù)1的備份CPU磁盤0數(shù)據(jù)1數(shù)據(jù)0的備份磁盤1塊交錯(cuò)備份6.7文件系統(tǒng)的數(shù)據(jù)一致性控制同一數(shù)據(jù)存放在不同的文件中,對(duì)它修改時(shí)應(yīng)對(duì)不同的文件都統(tǒng)一修改,才能保證數(shù)據(jù)的一致性。修改時(shí)數(shù)據(jù)的流向是,磁盤塊→內(nèi)存→寫回磁盤塊。若在寫回之前,系統(tǒng)崩潰,則文件系統(tǒng)數(shù)據(jù)出現(xiàn)不一致。系統(tǒng)應(yīng)配置保證數(shù)據(jù)一致性的軟件和相應(yīng)的硬件，硬件采取冗余技術(shù)配置一個(gè)高度可靠的存儲(chǔ)系統(tǒng),稱為穩(wěn)定存儲(chǔ)器;目前廣泛采用磁盤雙工方式來實(shí)現(xiàn)穩(wěn)定存儲(chǔ)器。設(shè)計(jì)保證數(shù)據(jù)一致性的實(shí)用程序,當(dāng)系統(tǒng)再次啟動(dòng)時(shí),運(yùn)行該程序,檢查磁盤塊和目錄系統(tǒng)。6.7.1事務(wù)1.事務(wù)的定義事務(wù)是用于訪問和修改數(shù)據(jù)的一個(gè)程序單位,由一系列相關(guān)的讀寫操作組成;被訪問的數(shù)據(jù)可以分散在不同位置,只有一系列讀寫操作全部完成才能以托付操作(CommitOperation)終止操作;而只要有一個(gè)操作失敗就執(zhí)行夭折操作(AbortOperation)。為了保證數(shù)據(jù)的一致性,對(duì)于夭折事務(wù)所操作過的數(shù)據(jù)必須恢復(fù)原來的狀態(tài),使該事務(wù)退回(rolledback),保證一個(gè)事務(wù)對(duì)一批數(shù)據(jù)修改操作,要么全部完成要么一個(gè)也不修改,這種特性稱事務(wù)的原子性。2.事務(wù)記錄(TransactionRecord)

為了實(shí)現(xiàn)事務(wù)的原子修改,用事務(wù)記錄這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn),它被存放在穩(wěn)定存儲(chǔ)器中,用來存儲(chǔ)事務(wù)運(yùn)行時(shí)數(shù)據(jù)項(xiàng)修改的全部信息,故又稱為運(yùn)行記錄(Log),該記錄包括下列字段:

事務(wù)名、數(shù)據(jù)項(xiàng)名、舊值、新值3.恢復(fù)算法

如果系統(tǒng)發(fā)生故障,應(yīng)對(duì)以前的事務(wù)進(jìn)行清理,通過查找事務(wù)記錄表做如下操作：(1)如果在Log表中只有(Ti開始)記錄無(Ti托付)記錄則調(diào)用undo(Ti)把所有被Ti修改過的數(shù)據(jù)恢復(fù)為原值。(2)如果在Log表中既有(Ti開始)記錄又有(Ti托付)記錄則調(diào)用redo(Ti)把已被Ti修改過的數(shù)據(jù)設(shè)置為新值。6.7.2檢查點(diǎn)(CheckPoints)1.檢查點(diǎn)的作用使對(duì)為了對(duì)事務(wù)記錄的清理工作經(jīng)常化,設(shè)置檢查點(diǎn)記錄;每隔一定的時(shí)間做一次清理:將內(nèi)存中的當(dāng)前事務(wù)記錄表的所有記錄,和所有已修改的數(shù)據(jù),輸出到穩(wěn)定存儲(chǔ)器中;再將檢查點(diǎn)記錄輸出到穩(wěn)定存儲(chǔ)器中;每當(dāng)出現(xiàn)一個(gè)檢查點(diǎn)記錄便執(zhí)行恢復(fù)操作。2.新的恢復(fù)算法發(fā)生故障后,恢復(fù)算法只需對(duì)最后一個(gè)檢查點(diǎn)之后的事務(wù)記錄進(jìn)行處理。即從最后一個(gè)檢查點(diǎn)之后的第一個(gè)事務(wù)記錄開始,對(duì)所有的事務(wù)Tk,在Log表中出現(xiàn)(Tk托付)記錄則執(zhí)行redo(Tk),

未出現(xiàn)(Tk托付)記錄則執(zhí)行undo(Tk)。6.7.3并發(fā)控制

由于事務(wù)具有的原子性,使得一個(gè)事務(wù)執(zhí)行完后才允許另一事務(wù)執(zhí)行,即事務(wù)對(duì)數(shù)據(jù)項(xiàng)的修改是互斥的,事務(wù)的這種特性稱為順序性,將實(shí)現(xiàn)順序性的技術(shù)稱為并發(fā)控制?？梢杂没コ庑盘?hào)量來保證事務(wù)處理的順序性,但用的最廣的是“鎖”。1.利用互斥鎖實(shí)現(xiàn)順序性設(shè)置一種用于實(shí)現(xiàn)互斥的鎖,簡(jiǎn)稱互斥鎖,為每一個(gè)共享對(duì)象設(shè)一把互斥鎖,如果事務(wù)Ti需要對(duì)一批對(duì)象進(jìn)行訪問,則為了保證事務(wù)操作的原子性,應(yīng)先獲得這批對(duì)象的互斥鎖,將他們?nèi)挎i住,如果成功便可以對(duì)這批對(duì)象執(zhí)行讀寫操作,然后全部開鎖,若某對(duì)象已被其它事務(wù)鎖住,則Ti要將已鎖住的對(duì)象全部開鎖。2.利用互斥鎖和共享鎖實(shí)現(xiàn)順序性對(duì)于共享文件,寫只能互斥進(jìn)行,但讀操作卻允許多個(gè)事務(wù)同時(shí)去讀,顯然用互斥鎖不能實(shí)現(xiàn)同時(shí)讀,為此引入另一種鎖共享鎖?；コ怄i僅允許一個(gè)事務(wù)對(duì)相應(yīng)的對(duì)象執(zhí)行讀或?qū)?共享鎖則允許多個(gè)事務(wù)對(duì)相應(yīng)的對(duì)象執(zhí)行讀操作,同時(shí)不允許任何一個(gè)事務(wù)對(duì)相應(yīng)的對(duì)象執(zhí)行寫操作。如果事務(wù)Ti需要對(duì)Q對(duì)象執(zhí)行讀操作,則只需獲得Q的共享鎖。如果事務(wù)Ti需要對(duì)Q對(duì)象執(zhí)行寫操作,則需獲得Q的互斥鎖和共享鎖。類似于讀者寫者問題。6.7.4重復(fù)數(shù)據(jù)的一致性問題1.重復(fù)文件的一致性以UNIX類型的文件系統(tǒng)為例,通常文件一個(gè)文件的目錄項(xiàng)由一個(gè)文件名和一個(gè)索引結(jié)點(diǎn)號(hào)組成;當(dāng)有重復(fù)文件時(shí),一個(gè)文件的目錄項(xiàng)由一個(gè)文件名和若干個(gè)索引結(jié)點(diǎn)號(hào)組成。保證重復(fù)文件的一致性用兩種方法：(1)當(dāng)一個(gè)文件被修改后,可查目錄,從各i結(jié)點(diǎn)找到各拷貝的物理位置,對(duì)這些拷貝做同樣修改。(2)為新修改的文件建立幾個(gè)新拷貝取代原來的拷貝。文件名i結(jié)點(diǎn)f117f222…...文件名i結(jié)點(diǎn)

f1171940f2227291……2.盤塊號(hào)一致性的檢查兩張表，每塊對(duì)應(yīng)一個(gè)表中的計(jì)數(shù)器，初值為0表一：記錄了每塊在空閑塊表中出現(xiàn)的次數(shù)表二：記錄了每塊在文件中出現(xiàn)的次數(shù)012345678910111213141511010111100

1110000101000011

00111空閑塊計(jì)數(shù)數(shù)據(jù)塊計(jì)數(shù)正常情況012345678910111213141511010111100

1110000001000011

00011空閑塊計(jì)數(shù)數(shù)據(jù)塊計(jì)數(shù)丟失盤塊012345678910111213141511012111100

1110000100000011

00011空閑塊計(jì)數(shù)數(shù)據(jù)塊計(jì)數(shù)空閑塊號(hào)重復(fù)012345678910111213141511011011100

111000010