操作系統(tǒng)原理與實踐教程(第四版) 課件匯 史葦杭 第6-10章 虛擬存儲器 -嵌入式操作系統(tǒng)

6.1虛擬存儲器引入6.2虛擬存儲器的實現(xiàn)方法6.3虛擬存儲器的特征6.4請求分頁存儲管理技術(shù)

6.5頁面置換算法6.6“抖動”與工作集6.7請求分段存儲管理方式第5章虛擬存儲器第6章

虛擬存儲器6.1虛擬存儲器引入前面所介紹的幾種存儲管理方式有一個共同的特點，都要求將一個作業(yè)全部裝入內(nèi)存之后才能運行，于是，就可能出現(xiàn)以下兩種情況：(1)有的作業(yè)很大，其要求的內(nèi)存空間超過了內(nèi)存總?cè)萘?，從而?dǎo)致作業(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無法運行。(2)有多個作業(yè)要求運行，其要求的內(nèi)存空間超過了可用的內(nèi)存空間，只能將少數(shù)作業(yè)裝入內(nèi)存讓它們先運行，而將其它作業(yè)留在外存等待。6.1虛擬存儲器的引入1.傳統(tǒng)存儲管理方式的特征(1)一次性。前面介紹的幾種存儲管理方式有一個共同的特點，都要求將作業(yè)全部裝入內(nèi)存之后才能運行，即作業(yè)在運行前需要一次性地全部裝入內(nèi)存，正是這一特征導(dǎo)致了上述兩種情況的發(fā)生。另外，許多作業(yè)在每次運行時，并非要用到全部程序和數(shù)據(jù)，因此一次性地裝入全部程序和數(shù)據(jù)，對內(nèi)存空間是一種極大的浪費。(2)駐留性。作業(yè)裝入內(nèi)存直到運行結(jié)束，便一直駐留在內(nèi)存中。盡管進程在運行中會因I/O等原因而長期處于阻塞狀態(tài)，或有的程序模塊在運行過一次后就不再需要，但它們都仍將繼續(xù)占用寶貴的內(nèi)存資源。6.1虛擬存儲器的引入2.局部性原理早在1968年，Denning.P就曾指出：程序的執(zhí)行表現(xiàn)出局部性特征，即程序在執(zhí)行過程中的一個時間段內(nèi)，程序的執(zhí)行僅局限于某個部分。相應(yīng)地，它所執(zhí)行的指令地址或操作數(shù)地址也局限于一定的存儲區(qū)域中。(1)程序執(zhí)行時，只有少量分支轉(zhuǎn)移和過程被調(diào)用，在大部分情況下仍是順序執(zhí)行的指令。(2)程序中包含許多循環(huán)結(jié)構(gòu)，由相對較少的指令組成，但是它們將多次執(zhí)行。在循環(huán)過程中，計算被限制在程序中很小的相鄰部分中。(3)程序中過程調(diào)用的深度限制在小范圍內(nèi)，很少出現(xiàn)連續(xù)的過程調(diào)用，大多數(shù)情況下都不超過5。一段時間內(nèi)，指令引用被局限在很少幾個過程中。(4)對于連續(xù)訪問數(shù)組之類的數(shù)據(jù)結(jié)構(gòu)，往往是對存儲區(qū)域中相鄰位置的數(shù)據(jù)進行操作。(5)程序中有些部分是彼此互斥的，不是每次運行時都用到，如出錯處理程序。6.1虛擬存儲器的引入2.局部性原理局限性還表現(xiàn)在下述兩個方面；(1)時間局部性。如果程序中的某條指令正在執(zhí)行，則不久后，該指令可能會再次執(zhí)行。同樣，如果某數(shù)據(jù)被訪問過，則不久后，該數(shù)據(jù)可能會被再次訪問。時間局部性的產(chǎn)生原因是由于在程序中存在著大量的循環(huán)操作。(2)空間局部性。程序在運行過程中，一旦訪問了某個內(nèi)存單元，則在不久后，其鄰近的存儲單元也將可能被訪問，即程序在一段時間內(nèi)所訪問的內(nèi)存地址，可能集中在一定的范圍之內(nèi)?？臻g局部性的產(chǎn)生原因是由于程序的順序執(zhí)行。6.1虛擬存儲器的引入3.虛擬存儲器的概念虛擬存儲器是指在具有層次結(jié)構(gòu)存儲器的計算機系統(tǒng)中，具有請求調(diào)入和交換功能，為用戶提供一個比實際物理內(nèi)存容量大得多的可尋址的一種存儲器系統(tǒng)，它能從邏輯上對內(nèi)存容量進行擴充。其邏輯容量由內(nèi)存容量和外存容量之和決定，其運行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。虛擬存儲器的容量主要受到兩方面的限制：(1)指令中表示地址的字長。一個虛擬存儲器的最大容量是由計算機的地址結(jié)構(gòu)確定的。如：若CPU的有效地址長度為32位，則程序可以尋址的范圍就是0～232-1，即虛存容量為4GB。(2)外存的容量。虛擬存儲器的容量與主存的實際大小沒有直接關(guān)系，而是由主存與輔存的容量之和確定。虛擬存儲技術(shù)是一種性能非常優(yōu)越的存儲器管理技術(shù)，已被廣泛應(yīng)用于大、中、小型機器和微型機中。6.2虛擬存儲器的實現(xiàn)方法虛擬存儲器的實現(xiàn)都必須建立在離散分配的存儲管理方式基礎(chǔ)上。虛擬存儲系統(tǒng)需要具有請求調(diào)頁(段)功能和頁面(分段)置換功能。如果程序執(zhí)行時發(fā)生缺頁或缺段，此時程序就可以利用系統(tǒng)提供的請求調(diào)頁(段)功能，將它們調(diào)入內(nèi)存，以使程序能夠繼續(xù)執(zhí)行下去。如果內(nèi)存已滿，無法裝入新調(diào)入的頁(段)，則必須利用一定的頁(段)置換功能，將內(nèi)存中暫時不用的頁(段)換到外存中，以騰出足夠的空間來存放新調(diào)入的頁(段)，從而保證程序的順利執(zhí)行。虛擬存儲器根據(jù)地址空間結(jié)構(gòu)的不同可以分為分頁虛擬存儲器和分段虛擬存儲器兩類，也可以把兩者結(jié)合起來，構(gòu)成段頁式虛擬存儲器。6.3虛擬存儲器的特征(1)虛擬性。虛擬內(nèi)存不是擴大實際的物理內(nèi)存，而是從邏輯上擴充內(nèi)存的容量。(2)多次性。多次性是指一個作業(yè)可被分成多次調(diào)入內(nèi)存運行。(3)對換性。對換性是指允許在作業(yè)運行過程中進行換進和換出。虛擬性是以多次性和交換性為基礎(chǔ)的，或者說，只有系統(tǒng)允許作業(yè)分多次調(diào)入內(nèi)存，并能將內(nèi)存中暫時不運行的程序和數(shù)據(jù)交換到外存，系統(tǒng)才可能實現(xiàn)虛擬存儲器，而多次性和對換性，又必須建立在離散分配的基礎(chǔ)上。1)進程地址空間分為虛頁實現(xiàn)原理之所以稱虛頁，因為運行時不一定在主存2)運行前裝入部分頁3)運行時訪問的頁面不在內(nèi)存,缺頁中斷,調(diào)入缺頁.4)缺頁中斷,調(diào)入新頁時,若內(nèi)存無空閑塊,則淘汰某頁,把新頁調(diào)入.5)地址變換(重定位):類似簡單分頁系統(tǒng),但頁表要增加4項（增加請求調(diào)頁、頁面置換功能）6.4請求分頁存儲管理方式第6章虛擬存儲器6.4在簡單頁式存儲管理的基礎(chǔ)上，PMT中增加請求調(diào)頁和頁面置換功能。簡單分頁PMT請求頁式進程頁表(PMT)塊號頁號AM外存地址P塊號頁號淘汰此頁寫回外存

M修改位：該頁被寫過否0否,1是,淘汰此頁不寫回外存

A訪問字段：頁面訪問統(tǒng)計,在近期內(nèi)被訪問的次數(shù)，或最近一次訪問到現(xiàn)在的時間間隔.為淘汰算法提供依據(jù)

外存地址:通常是外存物理塊號。

P狀態(tài)位:該頁在主存否0否1在地址變換查表時發(fā)現(xiàn)P=0,硬件缺頁中斷第6章虛擬存儲器6.46.4.1請求分頁中的硬件支持產(chǎn)生缺頁中斷請求調(diào)頁缺頁中斷處理保留CPU現(xiàn)場選擇一頁換出確定缺頁外存地址此頁修改過否？該頁寫回外存缺頁換入內(nèi)存修改頁表NY程序請求訪問一頁CPU查快表訪問頁表頁在內(nèi)存？形成物理地址修改訪問字段和修改位修改快表組織讀缺頁命令啟動I/O開始頁號≧頁表長度？越界中斷頁表項在快表中？YNYN內(nèi)存滿否？NYNY6.4.2請求分頁中的內(nèi)存分配1.最小物理塊數(shù)的確定

是指能保證進程正常運行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進程分配的物理塊數(shù)少于此值時，進程將無法運行。進程應(yīng)獲得的最小物理塊數(shù)與計算機的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。為進程分配內(nèi)存時，將涉及到三個問題：第一，最小物理塊數(shù)的確定；第二，物理塊的分配策略；第三，物理塊的分配算法。第6章虛擬存儲器6.42.內(nèi)存分配策略

固定分配局部置換為每個進程分配一定數(shù)目的物理塊，整個運行期間都不再改變。

可變分配全局置換

先為系統(tǒng)中的每個進程分配一定數(shù)目的物理塊，而OS自身也保持一定空閑物理塊隊列。當(dāng)某進程發(fā)現(xiàn)缺頁時，由系統(tǒng)從空閑物理塊隊列中取出一個物理塊分配給該進程，并將欲調(diào)入的頁裝入其中。

第6章虛擬存儲器6.46.4.2請求分頁中的內(nèi)存分配2.內(nèi)存分配策略

可變分配局部置換

為每個進程分配一定數(shù)目的物理塊，當(dāng)某進程發(fā)現(xiàn)缺頁時，只允許從該進程在內(nèi)存的頁面中選出一頁換出，這樣就不會影響其它進程的運行。若進程運行過程中頻繁地發(fā)生缺頁中斷，則系統(tǒng)為該進程分配附加的物理塊，直至該進程的缺頁率減少到適當(dāng)程度為止；反之，可適當(dāng)減少分配給該進程的物理塊數(shù)。第6章虛擬存儲器6.46.4.2請求分頁中的內(nèi)存分配并非一個進程分配幾個物理塊就可運行,太少可能造成系統(tǒng)抖動。在采用固定分配策略時，如何將系統(tǒng)中可供分配的所有物理塊分配給各進程?？刹捎靡韵聨追N算法：平均分配:將系統(tǒng)中所有可供分配的物理塊平均分配給各個進程。

內(nèi)存塊平均分給各進程。小進程有利,長進程中斷率高。3.物理塊分配算法第6章虛擬存儲器6.46.4.2請求分頁中的內(nèi)存分配2)根據(jù)進程大小按比例分配:根據(jù)進程的大小按比例分配物理塊。

如果系統(tǒng)中共有n個進程，每個進程的頁面數(shù)為Si，則系統(tǒng)中個進程頁面數(shù)的總和為：3.物理塊分配算法第6章虛擬存儲器6.46.4.2請求分頁中的內(nèi)存分配再假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進程所能分到的物理塊數(shù)bi可由下式計算：3)考慮優(yōu)先權(quán)的分配算法:為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它們分配較多的內(nèi)存空間。

通常將可供分配的所有物理塊分成兩部分：一部分按比例分配給各進程。另一部分則根據(jù)各進程的優(yōu)先權(quán)進行分配，可為高優(yōu)先級進程適當(dāng)?shù)卦黾悠湎鄳?yīng)份額。在重要的實時系統(tǒng)中，則可能是完全按優(yōu)先權(quán)為各進程分配其物理塊。

3.物理塊分配算法第6章虛擬存儲器6.46.4.2請求分頁中的內(nèi)存分配6.4.3頁面調(diào)入策略1）

預(yù)調(diào)頁策略：以預(yù)測為基礎(chǔ)需要調(diào)入某頁時，一次調(diào)入該頁以及相鄰的幾個頁。(通常用于進程首次調(diào)入內(nèi)存,可同時調(diào)入幾頁)優(yōu)點：提高調(diào)頁的I/O效率。缺點：基于預(yù)測，若調(diào)入的頁在以后很少被訪問，則效率低。常用于程序裝入時的調(diào)頁。1.何時調(diào)入頁面第6章虛擬存儲器6.46.4.3頁面調(diào)入策略2）請求調(diào)頁策略：當(dāng)發(fā)生缺頁時，只調(diào)入發(fā)生缺頁時所需的頁面。調(diào)入的頁一定會被訪問。優(yōu)點：容易實現(xiàn)。缺點：對外存I/O次數(shù)多，開銷較大1.何時調(diào)入頁面第6章虛擬存儲器6.46.4.3頁面調(diào)入策略通常對換區(qū)的I/O效率比文件區(qū)的高。關(guān)于調(diào)入頁面的來源，這里有三種做法：1）

從對換區(qū):進程裝入前，將其全部頁面復(fù)制到對換區(qū)，以后總是從對換區(qū)調(diào)入。執(zhí)行時調(diào)入速度快，要求對換區(qū)空間較大。2）

未被修改的頁面從文件區(qū)讀入，而被置換時不需調(diào)出；已被修改的頁面從對換區(qū)調(diào)入,節(jié)省對換區(qū)空間.被修改過的頁面淘汰時送入對換區(qū)2.從何處調(diào)入頁面第6章虛擬存儲器6.46.4.3頁面調(diào)入策略通常對換區(qū)的I/O效率比文件區(qū)的高。關(guān)于調(diào)入頁面的來源，這里有三種做法：2.從何處調(diào)入頁面3）

UNIX方式。未運行過的頁面都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運行過但又被換出的頁面，應(yīng)從對換區(qū)調(diào)入。又由于UNIX系統(tǒng)允許頁面共享，如果某進程所請求的頁面已經(jīng)被其他進程調(diào)入內(nèi)存，此時也無須從對換區(qū)調(diào)入。第6章虛擬存儲器6.46.4.3頁面調(diào)入策略

頁面未在內(nèi)存時（存在位為“0”），程序向CPU發(fā)出一缺頁中斷申請。

轉(zhuǎn)入缺頁中斷處理程序調(diào)入新頁置換

修改快表訪問內(nèi)存數(shù)據(jù)3.頁面調(diào)入過程整個頁面的調(diào)入過程對用戶是透明的。第6章虛擬存儲器6.46.4.3頁面調(diào)入策略

缺頁率：設(shè)一個進程的邏輯空間為n頁，系統(tǒng)為其分配的內(nèi)存物理塊數(shù)為m(m≤n)。

如果在進程的運行過程中，訪問頁面成功（即所訪問的頁面在內(nèi)存中）的次數(shù)為S。訪問頁面失?。此L問的頁面需從外存調(diào)入）的次數(shù)為F。

則總的頁面訪問數(shù)次為A=S+F，那么缺頁率為：4.缺頁率第6章虛擬存儲器6.46.4.3頁面調(diào)入策略

影響缺頁率的因素

頁面大小進程所分配物理塊的數(shù)據(jù)頁面置換算法程序固有特性4.缺頁率第6章虛擬存儲器6.46.4.3頁面調(diào)入策略

事實上，在缺頁中斷處理時，當(dāng)由于空間不足，需要置換部分頁面到外存時，選擇置換頁面還需要考慮到置換的代價。

頁面未修改過，直接放棄。

頁面修改過，必須保存。4.缺頁率第6章虛擬存儲器6.4設(shè)被置換的頁面被修改的概率為β，其缺頁中斷處理時間為ta，被置換頁面沒有被修改的的缺頁中斷時間為tb。則缺頁中斷處理時間的計算公式是：

請求分頁系統(tǒng)的評價優(yōu)點：請求分頁存儲管理具有分頁存儲管理的全部優(yōu)點，特別是它有效地緩解了碎片的問題。提供了大容量的多個虛擬存儲器；作業(yè)地址空間不再受實際存儲容量的限制；更有效地利用主存；有利于運行多道程序；提高了系統(tǒng)效率，方便了用戶，特別是大作業(yè)用戶；第6章虛擬存儲器6.4缺點：要求有相應(yīng)的硬件支持，從而增加了成本，如動態(tài)地址變換、快表、缺頁中斷的產(chǎn)生等都要求有相應(yīng)的硬件支持。缺頁中斷增加了處理機時間的開銷，如頁表的建立與管理、缺頁中斷處理等；頁面淘汰算法如選擇不當(dāng)，有可能產(chǎn)生抖動現(xiàn)象，為防止抖動，會增加系統(tǒng)的復(fù)雜性；雖然減少了碎片，但每個進程的最后一頁內(nèi)總有一部分空間得不到利用；請求分頁系統(tǒng)的評價第6章虛擬存儲器6.4有一臺16位機，可訪問64K空間，給出的地址長度16位內(nèi)存為32K。在具有虛擬存儲功能的系統(tǒng)中，允許進程的地址空間=64K（虛地址空間）64K地址空間不能全部裝入內(nèi)存，部分裝入外存有一個64K的地址空間映象運行時由MMU（MemoryManagementUnit）進行地址變換頁面劃分為4K：64K的虛地址空間可分為0…15（16個頁面）物理空間分為8個塊討論：第6章虛擬存儲器6.4216043XXX5X7XXXX60K-64K…1556K-60K…1452K-56K…1348K-52K…1244K-48K…1140K-44K…1036K-40K…932K-36K…828K-32K…724K-28K…620K-24K…516K-20K…412K-16K…3

8K-12K…24K-8K…10K-4K…0虛地址空間}虛頁28K-32K…724K-28K…620K-24K…516K-20K…412K-16K…38K-12K…24K-8K……10K-4K……0物理地址空間物理塊（虛擬存儲器）第5章虛擬存儲器6.401234567891011121314010100111101000110010111X0X0X01011X01111X0X0X0X015110000000000100001000000000010110頁表VAMA0CPU執(zhí)行

loadR1，8196（2004H）CPU給出虛地址8196送VA，分離出P|W：2|4因存在位為1，故2頁在內(nèi)存中，其物理塊號為6塊號6送MA的高四位，W送MA的低12位，形成物理地址：24580（6004H）6004H送地址總線讀取數(shù)據(jù)到寄存器R1。第6章虛擬存儲器6.40缺頁中斷機構(gòu)：在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時，便產(chǎn)生一缺頁中斷，請求OS將所缺之頁調(diào)入內(nèi)存。缺頁中斷同樣需要經(jīng)歷保護CPU環(huán)境、分析中斷原因、轉(zhuǎn)入缺頁中斷處理程序進行處理、恢復(fù)CPU環(huán)境等幾步。但缺頁與一般中斷相比，有著明顯的區(qū)別，主要表現(xiàn)在：（1）在指令執(zhí)行期間產(chǎn)生和處理中斷信號。（2）一條指令在執(zhí)行期間，可能產(chǎn)生多次中斷。如圖所示例子。123466頁面COPYATOBB:A:指令指令COPYATOB本身跨了兩頁，A和B分別各是一個數(shù)據(jù)塊，也都跨了兩頁。該指令的執(zhí)行可能產(chǎn)生6次缺頁中斷。第5章虛擬存儲器6.4產(chǎn)生缺頁中斷請求調(diào)頁缺頁中斷處理保留CPU現(xiàn)場選擇一頁換出確定缺頁外存地址此頁修改過否？該頁寫回外存缺頁換入內(nèi)存修改頁表NY程序請求訪問一頁CPU查快表訪問頁表頁在內(nèi)存？形成物理地址修改訪問字段和修改位修改快表組織讀缺頁命令啟動I/O開始頁號≧頁表長度？越界中斷頁表項在快表中？YNYN內(nèi)存滿否？NYNY6.5頁面置換算法功能：需要調(diào)入頁面時，選擇內(nèi)存中哪個物理頁面被置換。稱為replacementpolicy。目標(biāo)： ①把未來不再使用的調(diào)出 ②短期內(nèi)較少使用的頁面調(diào)出（根據(jù)局部性原理，依據(jù)過去的統(tǒng)計數(shù)據(jù)預(yù)測）頁面鎖定(framelocking)：

必須常駐內(nèi)存的操作系統(tǒng)的關(guān)鍵部分，不允許調(diào)出，頁表項中加上鎖定標(biāo)志位(lockbit)。第6章虛擬存儲器6.5最佳置換算法(OPT,optimal)先進先出頁面置換算法(FIFO)最近最久未使用置換算法(LRU,LeastRecentlyUsed)Clock置換算法(clock)其他置換算法最少使用置換算法 (LFU,LeastFrequentlyUsed)

頁面緩沖算法6.5頁面置換算法第6章虛擬存儲器6.51.最佳置換算法(OPT,optimal)選擇被置換頁面： “未來不再使用的” 或“在最長（未來）時間內(nèi)不再訪問的”這是一種理想情況，實際中是無法預(yù)知的，因而不能實現(xiàn)。可用作某算法性能評價的依據(jù)。Example1:假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1第6章虛擬存儲器6.56.5.1最佳置換算法和先進先出置換算法利用最佳置換算法時的置換圖70120304230321201701770701201201203203243243243203203203201201201201701701√√√√√√缺頁中斷9次，頁面置換6次頁面引用序列為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1√√√第6章虛擬存儲器6.5√√17012.先進先出算法(FIFO)FIFO算法是最早出現(xiàn)的置換算法。該算法總是淘汰最先進入內(nèi)存的頁面，即選擇進入內(nèi)存中駐留時間最長的頁面進行淘汰?？梢园岩粋€進程已調(diào)入內(nèi)存的頁面按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。

該算法性能較差。較早調(diào)入的頁往往是經(jīng)常被訪問的頁，這些頁在FIFO算法下被反復(fù)調(diào)入和調(diào)出，可能產(chǎn)生Belady（貝萊迪）異常。第6章虛擬存儲器6.52.先進先出算法(FIFO)Belady（貝萊迪）異常：在分頁式虛擬存儲器管理中，發(fā)生缺頁時的置換算法采用FIFO（先進先出）算法時，如果對一個進程未分配它所要求的全部頁面，有時就會出現(xiàn)分配的物理塊數(shù)目增多，但缺頁率反而提高的異?，F(xiàn)象。即替換策略不符合隨著物理塊數(shù)量的增大，缺頁率一定減少的規(guī)律。Belady異常的原因：

FIFO算法的置換特征與進程訪問內(nèi)存的動態(tài)特征是矛盾的，即被置換的頁面并不是進程不會訪問的。第6章虛擬存儲器6.5利用FIFO置換算法時的置換圖70120304230321201701770701201201231230430420423023023023013012012012712702√√√√√缺頁中斷16次，頁面置換12次701√√√√√√頁面引用序列為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1√√√√第6章虛擬存儲器6.5√√√√√6.5.2最近最久未使用和最少使用置換算法一個特殊的棧：把被訪問的頁面移到棧頂，于是棧底的是最久未使用頁面。每個頁面設(shè)立移位寄存器：被訪問時左邊最高位置1，周期右移并且最高位補0，于是寄存器數(shù)值最小的是最久未使用頁面。選擇內(nèi)存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。但由于需要記錄頁面使用時間的先后關(guān)系，硬件開銷太大。硬件機構(gòu)如：第6章虛擬存儲器6.51LRU(LeastRecentlyUsed)置換算法的描述利用LRU置換算法時的置換圖70120304230321201701770701201201203203403402432032032032132132102102107107√√√√√缺頁中斷12次，頁面置換9次107√√√√頁面引用序列為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1√√√第6章虛擬存儲器6.5√√√6.6頁面緩沖算法在請求分頁系統(tǒng)中，由于進程在運行時經(jīng)常會發(fā)生頁面換進換出的情況，所以一個十分明顯的事實就是，頁面換進換出所付出的開銷將對系統(tǒng)性能產(chǎn)生重大的影響。在此，我們首先對影響頁面換進換出效率的若干因素進行分析。6.6.1影響頁面換進換出效率的若干因素1.頁面置換算法。2.寫回磁盤的頻率。3.讀入內(nèi)存的頻率。6.6.2頁面緩沖算法PBAPBA算法的主要特點是：①顯著地降低了頁面換進、換出的頻率，使磁盤I/O的操作次數(shù)大為減少，因而減少了頁面換進、換出的開銷；②正是由于換入換出的開銷大幅度減小，才能使其采用一種較簡單的置換策略，如先進先出（FIFO）算法，它不需要特殊硬件的支持，實現(xiàn)起來非常簡單。1.空閑頁面鏈表2.修改頁面鏈表6.7訪問內(nèi)存的有效時間（1）被訪問頁在內(nèi)存中，且其對應(yīng)的頁表項在快表中。顯然，此時不存在缺頁中斷情況，內(nèi)存的有效訪問時間（EAT）分為查找快表的時間（λ）和訪問實際物理地址所需的時間（t）:EAT=λ+t（2）被訪問頁在內(nèi)存中，且其對應(yīng)的頁表項不在快表中。顯然，此時也不存在缺頁中斷情況，但需要兩次訪問內(nèi)存，一次讀取頁表，一次讀取數(shù)據(jù)，另外還需要更新快表。所以，這種情況內(nèi)存的有效訪問時間可分為查找快表的時間、查找頁表的時間、修改快表的時間和訪問實際物理地址的時間：EAT=λ+t+λ+t=2*（λ+t）（3）被訪問頁不在內(nèi)存中。因為被訪問頁不在內(nèi)存中，需要進行缺頁中斷處理，所以這種情況的內(nèi)存的有效訪問時間可分為查找快表的時間、查找頁表的時間、處理缺頁中斷的時間、更新快表的時間和訪問實際物理地址的時間：假設(shè)缺頁中斷處理時間為ε,則EAT=λ+t+ε+λ+t=ε+2*（λ+t）6.8工作集理論和抖動問題從主存中剛剛移走某頁面后，根據(jù)請求馬上又調(diào)入該頁。這種反復(fù)進行入頁和出頁的現(xiàn)象稱為“抖動”，也叫系統(tǒng)顛簸。它會浪費大量的處理機時間，應(yīng)盡可能避免。產(chǎn)生抖動的直接原因是頁面置換算法選取不當(dāng)。第5章虛擬存儲器6.86.8“抖動”與工作集請求分頁系統(tǒng)能有效地減少內(nèi)存碎片，提高處理機的利用率和吞吐量，是目前最常用的一種系統(tǒng)。但如果在系統(tǒng)中運行的進程太多，進程在運行中頻繁地發(fā)生缺頁情況，又會對系統(tǒng)的性能產(chǎn)生很大的影響。6.86.8.1多道程序度與“抖動”第5章虛擬存儲器6.8抖動與工作集1.多道程序度與處理機的利用率100%CPU飽和度利用率0N1NmaxN2N3L/S

抖動6.86.8.1多道程序度與“抖動”第5章虛擬存儲器6.8抖動與工作集1.多道程序度與處理機的利用率100%CPU飽和度利用率0N1NmaxN2N3L/S

抖動在橫軸的開始部分，隨著進程數(shù)目的增加，處理機的利用率急劇增加；到達(dá)N1時，增速明顯減慢；到達(dá)Nmax時，處理機的利用率達(dá)到最大，之后開始緩慢下降；到達(dá)N2時，處理機的利用率下降加快之所以出現(xiàn)利用率趨于0的情況，是因為系統(tǒng)中出現(xiàn)了“抖動”。第5章虛擬存儲器6.8L是缺頁之間的平均時間，S是平均缺頁服務(wù)時間6.8抖動與工作集2.產(chǎn)生“抖動”的原因同時在系統(tǒng)中運行的進程太多，由此分配給每一個進程的物理塊太少，不能滿足進程正常運行的基本要求，致使每個進程在運行時，頻繁地出現(xiàn)缺頁，造成每個進程的大部分時間都用于頁面的換進/換出，而幾乎不能再去做任何有效的工作，從而導(dǎo)致發(fā)生處理機的利用率急劇下降并趨于0的情況。第5章虛擬存儲器6.86.8抖動與工作集6.8.2工作集進程發(fā)生缺頁率的時間間隔與進程所獲得的物理塊數(shù)有關(guān)從圖中可以看出，缺頁率隨著所分配物理塊數(shù)的增加明顯地減少，當(dāng)物理塊數(shù)超過某個數(shù)目時，再為進程增加一個物理塊，對缺頁率的改善已不明顯。已無必要再為它分配更多的物理塊。當(dāng)為某進程所分配的物理塊數(shù)低于某個數(shù)目時，每減少一塊，對缺頁率的影響都變得十分明顯。應(yīng)為進程分配更多的物理塊缺頁率上限下限0n物理塊數(shù)缺頁率與物理塊數(shù)之間的關(guān)系第5章虛擬存儲器6.86.8抖動與工作集6.8.2工作集是指在某段時間間隔Δ里，進程實際所要訪問頁面的集合。24151823241718241817171524172418242424152415241524181524181524181524231815231815242318152424231824231815242318151724231724231817242318151817241817242318172423241817241817241817231824182417182417171824171824171824171817182417182415171517181517182424151724151724151718172415172415172415241724171524171518241718241718241715引用頁面序列窗口大小345第5章虛擬存儲器6.86.8抖動與工作集6.8.3“抖動”的預(yù)防方法1．采取局部置換策略當(dāng)某進程發(fā)生缺頁時，只能在分配給自己的內(nèi)存空間內(nèi)進行置換，不允許從其它進程去獲得新的物理塊，即使“抖動”也不影響其它進程。2．把工作集算法融入到處理機調(diào)度中從外存調(diào)入作業(yè)時，先檢查每個進程在內(nèi)存的駐留頁面是否足夠多。如果已經(jīng)足夠多，新作業(yè)的調(diào)入不會導(dǎo)致缺頁率的增加；反之，如果某些進程的頁面不足，應(yīng)首先為那些缺頁率居高的作業(yè)增加新的物理塊。第5章虛擬存儲器6.86.8抖動與工作集6.8.3“抖動”的預(yù)防方法3.利用“L=S”準(zhǔn)則調(diào)節(jié)缺頁率利用“L=S”準(zhǔn)則調(diào)節(jié)多道程序度，L是缺頁之間的平均時間，S是平均缺頁服務(wù)時間，即用于置換一個頁面所需的時間。L<S，頻繁發(fā)生缺頁；L>S，很少缺頁；L與S接近，磁盤和處理機都可達(dá)到它們的最大利用率。4．選擇暫停的進程掛起某些暫停的進程。第5章虛擬存儲器6.86.9請求分段存儲管理方式在簡單段式存儲管理的基礎(chǔ)上，SMT增加5項:1.請求段表機制1)地址空間分為若干虛段,運行前裝入部分段.2)當(dāng)訪問的段不在內(nèi)存時產(chǎn)生“缺段中斷”,把缺的段調(diào)入內(nèi)存.3)如果內(nèi)存無空閑空間,則置換出暫不用的某個段.很類似虛擬頁式。學(xué)習(xí)中注意二者差異段號段長內(nèi)存首址存取權(quán)限AMP增補位外存始址基本段式SMT增加的表項第5章虛擬存儲器外存始址增補位PMA存取權(quán)限內(nèi)存首址段長段號基本段式SMT增加的表項1)存取權(quán)限:如讀R，寫W，執(zhí)行X2)A訪問字段:段訪問統(tǒng)計,在近期內(nèi)被訪問的次數(shù)， 或近一次訪問到現(xiàn)在的時間間隔.為淘汰算法提供依據(jù)。3)M修改位:該段是否被修改過。4)P存在位(狀態(tài)位):該段在主存否。5)增補位:該段動態(tài)增長過否。6)外存始址:該段外存起始盤塊號。第5章虛擬存儲器

內(nèi)存分配:在虛擬段式管理中是按段對物理內(nèi)存進行分配，可采用動態(tài)分區(qū)算法。2.缺段中斷處理:(參看圖5-12)1)當(dāng)指令給出訪問地址:S|W,地址變換機構(gòu)首先檢查SMT的存在位.2)當(dāng)存在位表示該段不在內(nèi)存,則產(chǎn)生缺段中斷請求：①CPU響應(yīng)中斷,進入中斷處理，把缺的段調(diào)入內(nèi)存,修改SMT和內(nèi)存空閑區(qū)鏈表.②若內(nèi)存無合適空閑區(qū),則拼接或置換某段，形成合適的空閑區(qū)，調(diào)入新段，修改SMT和內(nèi)存空閑鏈表.第5章虛擬存儲器6.9圖5-12缺段中斷處理流程第5章虛擬存儲器6.93.地址變換機構(gòu):(參看圖5-13)訪問S|WW≦段長？N分段越界中斷處理Y符合存取方式？N分段保護中斷處理Y段S在內(nèi)存否？N缺段中斷處理Y修改訪問字段A，如果是寫訪問，則置修改位M=1返回形成物理地址：段始址+W是否出錯？E、R、W查P=1？同于基本段式地址變換機構(gòu)第5章虛擬存儲器6.9

1．共享段表為了實現(xiàn)分段共享，可在系統(tǒng)中配置一張共享段表，所有各共享段都在共享段表中占有一表項。表項中記錄了共享段的段號、段長、內(nèi)存始址、存在位等信息，并記錄了共享此分段的每個進程的情況。共享段表如圖所示。其中各項說明如下。6.9.2分段的共享與保護第5章虛擬存儲器6.9共享進程計數(shù)count。記錄有多少個進程需要共享該分段。存取控制字段。不同進程對該段的存取權(quán)限段號。對于一個共享段，不同的進程可以各用不同的段號去共享該段。

圖5-14共享段表項

第5章虛擬存儲器6.9段名段長內(nèi)存始址狀態(tài)外存始址共享進程計數(shù)進程狀態(tài)進程名進程號段號存取控制權(quán)限……S2301002H1452就緒P1320R阻塞P2561RWN23501A2CH0693就緒P8682X阻塞P9971R阻塞P32003RD4602B00H12002就緒P201334RW阻塞P32002R共享段表示例第5章虛擬存儲器6.9

2．共享段的分配與回收

1)共享段的分配

對第一個請求使用該共享段的進程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，同時將該區(qū)的始址填入請求進程的段表的相應(yīng)項中，還須在共享段表中增加一表項，填寫有關(guān)數(shù)據(jù)，把count置為1；之后，當(dāng)又有其它進程需要調(diào)用該共享段時，由于該共享段已被調(diào)入內(nèi)存，故此時無須再為該段分配內(nèi)存，而只需在調(diào)用進程的段表中增加一表項，填寫該共享段的物理地址；在共享段的段表中，填上調(diào)用進程的進程名、存取控制等，再執(zhí)行count=count+1操作，以表明有兩個進程共享該段。第5章虛擬存儲器6.9分段共享:段名段長內(nèi)存始址狀態(tài)外存始址共享進程計數(shù)count狀態(tài)進程名進程號段號存取控制…外存始址內(nèi)存始址………………外存始址內(nèi)存始址………共享段SMTnSMTm①為Pn共享段分配內(nèi)存②查SMT③SMT建立表項④1⑥為Pm共享段分配內(nèi)存共享段⑦查SMT⑤⑧2⑨共享SMT

2)共享段的回收當(dāng)共享此段的某進程不再需要該段時，應(yīng)將該段釋放，包括撤消在該進程段表中共享段所對應(yīng)的表項，以及執(zhí)行count=count-1操作。若結(jié)果為0，則須由系統(tǒng)回收該共享段的物理內(nèi)存，以及取消在共享段表中該段所對應(yīng)的表項，表明此時已沒有進程使用該段；否則(減1結(jié)果不為0)，只是取消調(diào)用者進程在共享段表中的有關(guān)記錄。第5章虛擬存儲器6.9

3．分段保護在分段系統(tǒng)中，由于每個分段在邏輯上是獨立的，因而比較容易實現(xiàn)信息保護。目前，常采用以下幾種措施來確保信息的安全。

1)越界檢查在段表寄存器中放有段表長度信息；同樣，在段表中也為每個段設(shè)置有段長字段。在進行存儲訪問時，首先將邏輯地址空間的段號與段表長度進行比較，如果段號等于或大于段表長度，將發(fā)出地址越界中斷信號；其次，還要檢查段內(nèi)地址是否等于或大于段長，若大于段長，將產(chǎn)生地址越界中斷信號，從而保證了每個進程只能在自己的地址空間內(nèi)運行。第5章虛擬存儲器6.9

2)存取控制檢查在段表的每個表項中，都設(shè)置了一個“存取控制”字段，用于規(guī)定對該段的訪問方式。通常的訪問方式有：

(1)只讀，即只允許進程對該段中的程序或數(shù)據(jù)進行讀訪問。

(2)只執(zhí)行，即只允許進程調(diào)用該段去執(zhí)行，但不準(zhǔn)讀該段的內(nèi)容，也不允許對該段執(zhí)行寫操作。

(3)讀/寫，即允許進程對該段進行讀/寫訪問。第5章虛擬存儲器6.9第5章虛擬存儲器

3)環(huán)保護機構(gòu)這是一種功能較完善的保護機制。在該機制中規(guī)定：低編號的環(huán)具有高優(yōu)先權(quán)。OS核心處于0環(huán)內(nèi)；某些重要的實用程序和操作系統(tǒng)服務(wù)占居中間環(huán)；而一般的應(yīng)用程序則被安排在外環(huán)上。在環(huán)系統(tǒng)中，程序的訪問和調(diào)用應(yīng)遵循以下規(guī)則：

(1)一個程序可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)。

(2)一個程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)。第5章虛擬存儲器6.9第5章虛擬存儲器圖5-15環(huán)保護機構(gòu)

第5章虛擬存儲器6.9虛擬存儲器是從邏輯上實現(xiàn)對內(nèi)存容量的擴充，讓用戶所感覺到的內(nèi)存容量比實際內(nèi)存容量大得多。所有的虛擬存儲器都是采用分頁請求系統(tǒng)或請求分段系統(tǒng)來實現(xiàn)的。請求分頁式虛擬存儲器系統(tǒng)的性能優(yōu)越，在正常運行情況下，它能有效地減少內(nèi)存碎片，提高處理機的利用率和吞吐率，是目前最常用的一種系統(tǒng)。6.10本章小結(jié)第5章虛擬存儲器在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時，便產(chǎn)生一缺頁中斷，請求OS將所缺之頁調(diào)入內(nèi)存。抖動是在進程運行中出現(xiàn)的嚴(yán)重問題，必須采取相應(yīng)的措施來解決它。在分段基礎(chǔ)上建立的請求分段式虛擬存儲器系統(tǒng)，是以分段為單位進行換入、換出的。6.10本章小結(jié)第5章虛擬儲5器第6章文件管理6.1文件的概念6.2文件目錄6.3文件和目錄操作6.4文件的邏輯結(jié)構(gòu)6.5文件的物理結(jié)構(gòu)6.6文件存儲空間的分配6.7文件存儲空間的管理6.8文件系統(tǒng)6.9文件的共享和保護6.10Linux的文件系統(tǒng)6.1文件的概念文件系統(tǒng)的管理功能，就是通過把計算機保存的程序和數(shù)據(jù)組織成一系列文件的方法來實現(xiàn)的。文件是計算機系統(tǒng)中信息存放的一種組織形式。在現(xiàn)代操作系統(tǒng)中，幾乎都是通過文件系統(tǒng)來組織和管理計算機保存的大量程序和數(shù)據(jù)。6.1.1文件及其分類1.文件的定義文件是計算機系統(tǒng)中信息存放的一種組織形式，是在邏輯上具有完整意義的信息集合，并且有一個名字以供標(biāo)識。構(gòu)成文件的基本單位可以是字符流，也可以是記錄。據(jù)此，文件有兩種有代表性定義：(1)文件是具有標(biāo)識符的相關(guān)字符流的集合。說明文件是由字節(jié)組成，這是一種無結(jié)構(gòu)的文件，稱為流式文件，目前UNIX操作系統(tǒng)，MS-DOS系統(tǒng)均采用這種文件形式。無結(jié)構(gòu)的文件由于采用字符流方式，與源程序、目標(biāo)代碼等在形式上是一致的，因此，該方式適用于源程序、目標(biāo)代碼等文件。(2)文件是具有標(biāo)識符的相關(guān)記錄(一個有意義的信息單位)的集合。文件是由記錄組成，這是一種有結(jié)構(gòu)的文件。記錄是由一組相關(guān)信息項組成。例如每個學(xué)生的檔案表可以視為一個記錄，它包括學(xué)生姓名、出生年月、性別、籍貫等信息項，所有學(xué)生檔案表組成一個學(xué)生文件。記錄式文件主要用于信息管理。6.1.1文件及其分類2.文件的命名文件名由創(chuàng)建者給定，它是由字母或數(shù)字組成的一個字符串，用來標(biāo)識該文件。不同的系統(tǒng)對文件命名有不同的要求。例如，有些系統(tǒng)規(guī)定必須是字母打頭且允許一些其它符號出現(xiàn)在文件名的非打頭部分；有些系統(tǒng)區(qū)分文件名中的大小寫字母，如UNIX和Linux系統(tǒng)；而有些系統(tǒng)則不去區(qū)分文件名中的大小寫，如MS-DOS。名字的長度因系統(tǒng)不同而異。如在有的系統(tǒng)中把名字規(guī)定為8個字符，而在有的系統(tǒng)中規(guī)定可用14個字符。6.1.1文件及其分類2.文件的命名文件名由文件名和擴展名兩部分組成，中間用“.”隔開，如program.c。它們都是由字母或數(shù)字組成的字母數(shù)字串。擴展名也稱文件后綴，利用擴展名可以區(qū)分文件的屬性。擴展名文件類型含義exe,com,bin可執(zhí)行文件可以運行的機器語言程序obj,o目標(biāo)文件編譯過的、尚未鏈接的機器語言程序c,cc,java,pas,asm,a程序源文件用各種語言編寫的源代碼bat,sh批處理文件由命令解釋程序處理的命令txt,doc文本文件文本數(shù)據(jù)、文檔wp,tex,rtf,doc字處理文檔文件各種字處理器格式的文件lib,aso,dll庫文件供程序員使用的例程庫arc,zip,tar存檔文件相關(guān)文件組成一個文件(有時壓縮)進行存檔或存儲ps,pdf,jpg打印或視圖文件用于打印或視圖的ASCⅡ或二進制文件mpeg,mov,rm多媒體文件包含音頻或A/V信息的二進制文件6.1.1文件及其分類3.文件的分類(1)按文件的用途分類系統(tǒng)文件：指由操作系統(tǒng)及其它系統(tǒng)程序和數(shù)據(jù)組成的文件。這種文件不對用戶開放，僅供系統(tǒng)使用，用戶只能通過操作系統(tǒng)提供的系統(tǒng)調(diào)用來使用它們，用戶沒有讀權(quán)限和修改權(quán)限。庫文件：指系統(tǒng)為用戶提供的各種標(biāo)準(zhǔn)函數(shù)、標(biāo)準(zhǔn)過程和實用程序等。用戶只能使用這些文件，而不允許對其進行修改。用戶文件：指由用戶的源代碼、目標(biāo)文件、可執(zhí)行文件或數(shù)據(jù)等所構(gòu)成的文件。這種文件的使用和修改權(quán)均屬于用戶。6.1.1文件及其分類3.文件的分類(2)按文件的操作權(quán)限分類只讀文件：只允許進行讀操作，不能進行寫操作的文件。讀寫文件：允許文件屬主和授權(quán)用戶對其進行讀或?qū)懖僮鞯奈募Ｖ粓?zhí)行文件：該類文件只允許授權(quán)的用戶調(diào)用執(zhí)行，而不允許其修改或讀出文件的內(nèi)容。6.1.1文件及其分類3.文件的分類(3)按文件的性質(zhì)分類普通文件：指一般的用戶文件和系統(tǒng)文件，譬如一般用戶建立的源程序文件、數(shù)據(jù)文件、目標(biāo)代碼文件及操作系統(tǒng)自身代碼文件、庫文件、實用程序文件等都是普通文件。普通文件通常分為ASCII文件和二進制文件，一般存放在外存儲設(shè)備上。目錄文件：由文件目錄項組成，用來管理和實現(xiàn)文件系統(tǒng)功能的系統(tǒng)文件，通過目錄文件可以對其它文件的信息進行檢索。對目錄文件可以進行與普通文件一樣的各種文件操作。特殊文件：指系統(tǒng)中的各類I/O設(shè)備。為了方便統(tǒng)一管理，系統(tǒng)將所有的I/O設(shè)備都視為文件，以文件方式提供給用戶使用。根據(jù)設(shè)備數(shù)據(jù)交換單位的不同，又可將特殊文件分為塊設(shè)備文件和字符設(shè)備文件。前者用于磁盤、光盤等塊設(shè)備的I/O操作，而后者用于終端、打印機等字符設(shè)備的I/O操作。6.1.1文件及其分類3.文件的分類(4)按文件中數(shù)據(jù)的形式分類源文件。指由源程序和數(shù)據(jù)構(gòu)成的文件。通常由終端或輸入設(shè)備輸入的源程序和數(shù)據(jù)所形成的文件都屬于源文件。它通常由ASCII碼或漢字組成。目標(biāo)文件。指把源程序經(jīng)過相應(yīng)語言的編譯程序編譯過，但尚未經(jīng)過鏈接程序鏈接的目標(biāo)代碼所構(gòu)成的文件。它屬于二進制文件。通常，目標(biāo)文件使用的后綴名是“.obj”?？蓤?zhí)行文件。指把編譯后產(chǎn)生的目標(biāo)代碼再經(jīng)過鏈接程序鏈接后所形成的文件。6.1.2文件的屬性為了對文件進行控制和管理，大多數(shù)操作系統(tǒng)都用一組信息來指定文件的類型、操作特性和存取保護等，這組信息稱為文件的屬性。文件的基本屬性：文件的名稱、文件的所有者、文件的授權(quán)者、文件的長度等。文件的類型屬性：如普通文件、目錄文件、系統(tǒng)文件、隱含文件、設(shè)備文件等。也可以按文件信息分為ASCII碼文件、二進制碼文件等。文件的保護屬性：如可讀、可寫、可執(zhí)行、可更新、可刪除等，可改變保護以及檔案屬性。文件的管理屬性：如文件的建立時間、最后存取時間、最后修改時間等。文件的控制屬性：邏輯記錄長、文件的大小、文件的最大長度以及允許的存取方式標(biāo)志、關(guān)鍵字的位置、關(guān)鍵字長度等。所有文件的信息都保存在目錄結(jié)構(gòu)中，而目錄結(jié)構(gòu)保存在外存中。通常，目錄條目包括文件名稱及其唯一標(biāo)識符，而這些標(biāo)識符又定位其它屬性信息。一個文件的屬性信息大概需要1KB。6.2文件目錄文件目錄是一種數(shù)據(jù)結(jié)構(gòu)，用來標(biāo)識文件系統(tǒng)中的文件及其物理地址，供檢索時使用。對文件目錄管理的功能要求如下：(1)實現(xiàn)按名存取。(2)提高對目錄的檢索速度。(3)文件共享。(4)允許文件重名。6.2.1文件控制塊和文件目錄一個文件包括兩部分：文件說明和文件體。文件體是指文件本身的信息，它可以是記錄式文件或字符流文件。文件說明也叫文件控制塊(filecontrolblock，F(xiàn)CB)，它是操作系統(tǒng)為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放管理文件所需的所有有關(guān)信息(文件屬性)，文件控制塊是文件存在的標(biāo)志。6.2.1文件控制塊和文件目錄1.文件控制塊文件控制塊通常包含三類信息:(1)基本信息文件名：用于標(biāo)識一個文件的符號名。在每個系統(tǒng)中，每個文件都必須有唯一的名字，用戶利用該名字進行訪問。文件類型：指明文件屬性是普通文件，還是目錄文件或特殊文件，是系統(tǒng)文件還是用戶文件等。文件物理位置：指文件在外存上的存儲位置，如存放文件的設(shè)備名、文件在外存的起始盤塊號、文件占用的盤塊數(shù)或字節(jié)數(shù)。文件大?。寒?dāng)前文件的大小(以字節(jié)、字或塊為單位)和允許的最大長度。(2)存取控制信息存取控制信息包括：文件屬主的存取權(quán)限、標(biāo)準(zhǔn)用戶的存取權(quán)限以及一般用戶的存取權(quán)限。(3)使用信息時間和日期：反映文件創(chuàng)建和最后修改的日期和時間。最后使用情況：包括文件是否被其它進程鎖住、文件在內(nèi)存中是否已被修改但尚未拷貝到盤上等。這些信息可用于對文件實施保護和監(jiān)控等。使用計數(shù)：表示當(dāng)前有多少個進程正在使用或打開該文件。6.2.1文件控制塊和文件目錄2.文件目錄文件與文件控制塊一一對應(yīng)，文件控制塊的有序集合稱為文件目錄，一個文件控制塊就是一個文件目錄項。為了實現(xiàn)對文件目錄的管理，通常將文件目錄以文件的形式保存在外存上，這個文件就叫目錄文件。

MS-DOS目錄項示意圖:6.2.1文件控制塊和文件目錄3.索引節(jié)點為了減少檢索文件的時間，在有的系統(tǒng)中，如UNIX/Linux系統(tǒng)，采用把文件名和文件描述信息分開的方法，使文件描述信息單獨形成一個定長的數(shù)據(jù)結(jié)構(gòu)，稱為索引節(jié)點，簡稱為i結(jié)點。這樣，在文件目錄中的每個目錄項僅由文件名和指向該文件對應(yīng)的i結(jié)點的指針?biāo)鶚?gòu)成。在UNIX系統(tǒng)中一個目錄僅占16個字節(jié)，其中14個字節(jié)是文件名，2個字節(jié)為i結(jié)點指針。在1KB的盤塊中可保存64個目錄項，這樣，為找到一個文件，可使平均啟動磁盤次數(shù)減少到原來的1/4，大大節(jié)省了系統(tǒng)開銷。Unix系統(tǒng)的文件目錄項示意圖如下。6.2.2文件目錄結(jié)構(gòu)1.單級目錄在整個文件系統(tǒng)中只建立一張目錄表，每個文件占一個目錄項，目錄項中包含文件名、文件擴展名、文件類型、文件長度、文件物理地址以及其它文件屬性。6.2.2文件目錄結(jié)構(gòu)1.單級目錄單級目錄的優(yōu)點是簡單、易于實現(xiàn)，實現(xiàn)了目錄管理的基本功能——按名存取，但卻存在以下一些缺點：(1)查找速度慢。(2)不允許重名。(3)不便于文件的共享。6.2.2文件目錄結(jié)構(gòu)2.兩級目錄為每一個用戶建立一個單獨的用戶文件目錄UFD(UserFileDirectory)。這些文件目錄具有相似的結(jié)構(gòu)，它由用戶所有文件的文件控制塊組成。系統(tǒng)再建立一個主文件目錄MFD(MasterFileDirectory)，在主文件目錄中，每個用戶目錄文件都占有一個目錄項，其目錄項中包括用戶名和指向該用戶目錄文件的指針。6.2.2文件目錄結(jié)構(gòu)2.兩級目錄兩級目錄結(jié)構(gòu)基本克服了單級目錄的缺點，具有以下優(yōu)點：(1)解決文件名沖突。(2)提高目錄檢索速度。(3)不同用戶可使用不同的文件名來訪問系統(tǒng)中的同一個共享文件。兩級目錄仍然存在一些問題。這種結(jié)構(gòu)有效地對用戶加以隔離，這種隔離在各用戶之間完全無關(guān)時是優(yōu)點，但是當(dāng)用戶需要在某個任務(wù)上進行合作，且一用戶又需要訪問其它用戶的文件時，這種隔離就是個缺點，因為有的系統(tǒng)不允許本地用戶文件被其它用戶訪問。6.2.2文件目錄結(jié)構(gòu)3.多級目錄多級目錄結(jié)構(gòu)是一棵倒向的有根樹，樹根是根目錄；從根向下，每一個樹枝是一個子目錄，而樹葉則是文件。樹形目錄有許多優(yōu)點：它較好地反映了現(xiàn)實世界中具有層次關(guān)系的數(shù)據(jù)集合和較確切地反映系統(tǒng)內(nèi)部文件的分支結(jié)構(gòu)，不同的文件可以重名，只要它們不位于同一子目錄中即可，易于規(guī)定不同層次或子樹中文件的不同存取權(quán)限，便于文件的保護、保密和共享等。6.2.2文件目錄結(jié)構(gòu)在樹形目錄結(jié)構(gòu)中，文件的全名包括從根目錄開始到文件為止的所有子目錄路徑。各個子目錄名之間用正斜線“/”或反斜線“\”隔開。子目錄名組成的部分又稱為路徑名。系統(tǒng)內(nèi)的每個文件都有唯一的路徑名，路徑名是從根經(jīng)過所有子目錄再到指定文件的路徑。絕對路徑名從根目錄開始并給出路徑上的目錄名直到指定的文件。相對路徑名則從當(dāng)前目錄開始定義一個路徑。6.2.3目錄的實現(xiàn)1.線性列表目錄文件是由目錄項構(gòu)成的一個線性表，每個目錄項包括文件名和指向數(shù)據(jù)塊的指針。當(dāng)需要創(chuàng)建一個新文件時，系統(tǒng)必須首先搜索目錄文件以確定有沒有同名的文件存在，然后把新文件的目錄項添加到目錄末尾。當(dāng)刪除一個文件時，系統(tǒng)根據(jù)給定的文件名來搜索文件目錄。找到該文件所在目錄項后，釋放分配給該文件的磁盤空間，并將相應(yīng)的目錄項刪除。6.2.3目錄的實現(xiàn)2.哈希表哈希表是實現(xiàn)文件目錄的另一種數(shù)據(jù)結(jié)構(gòu)。采用這種方法時，除了使用線性列表來存放目錄項以外，還使用了哈希表。哈希表將根據(jù)文件名計算出一個哈希值，并返回一個指向線性列表中元素的指針。因此，它大大降低了目錄搜索時間，插入和刪除也很方便，不過需要一些措施來避免沖突(兩個不同的文件名具有相同的哈希值)。哈希表的最大困難在于其大小通常是固定的，而且哈希函數(shù)也依賴于哈希表的大小。6.3文件和目錄操作6.3.1文件操作用戶通過文件系統(tǒng)提供的系統(tǒng)調(diào)用對文件進行操作。1.基本的文件操作(1)創(chuàng)建文件。(2)刪除文件。(3)讀文件。(4)寫文件。(5)文件定位。(6)截短文件。6.3.1文件操作2.文件的“打開”和“關(guān)閉”操作為了避免多次重復(fù)地檢索目錄，大多數(shù)操作系統(tǒng)都引入“打開(open)”這一文件系統(tǒng)調(diào)用，當(dāng)用戶第一次請求對某文件進行操作時，先利用open系統(tǒng)調(diào)用顯式地將該文件打開。操作系統(tǒng)維護一個包含所有打開文件的信息表(打開文件表，openfiletable)。當(dāng)需要進行一個文件操作時，可以通過打開文件表的一個索引來指定文件，而不需要搜索整個文件目錄。當(dāng)文件不再使用時，進程可以關(guān)閉它，操作系統(tǒng)隨即從打開文件表中刪除這一條目。6.3.2目錄操作1.創(chuàng)建目錄創(chuàng)建的新目錄除了目錄項“.”(表示該目錄本身)和“..”(表示父目錄)以外，其內(nèi)容為空。2.刪除目錄刪除目錄時，系統(tǒng)首先進行目錄檢索，在父目錄中找到該目錄的目錄項，然后驗證用戶的操作權(quán)限，如果具有刪除權(quán)限，就執(zhí)行相應(yīng)的刪除操作。在刪除目錄時，不同的系統(tǒng)有不同的限制。有的系統(tǒng)限制只能刪除空目錄，因此，當(dāng)被刪除目錄下有子目錄或文件時，將不能刪除目錄，如MS-DOS就是采用這種目錄刪除方式。而另外有些系統(tǒng)則不管目錄是否為空都可以執(zhí)行刪除操作，如果目錄非空，系統(tǒng)會自動將它下面的文件或子目錄一并刪除。3.檢索目錄檢索目錄是根據(jù)用戶給定的文件路徑名，從高層到底層順序地查找各級文件目錄，尋找指定文件的相關(guān)信息。6.4文件的邏輯結(jié)構(gòu)對于文件組織形式的研究有兩種不同的觀點，即用戶觀點和實現(xiàn)觀點。用戶觀點的目的是研究用戶“思維”中的抽象文件，也稱邏輯文件。研究的側(cè)重點是為用戶提供一種邏輯結(jié)構(gòu)清晰、使用簡便的邏輯文件形式。用戶按照這種形式去存儲和訪問有關(guān)文件中的信息。實現(xiàn)觀點的目的是研究保存在設(shè)備介質(zhì)中的實際文件，也稱物理文件。研究的側(cè)重點是如何選擇工作性能良好、設(shè)備利用率高的物理文件形式。6.4文件的邏輯結(jié)構(gòu)對應(yīng)于用戶觀點的邏輯文件和實現(xiàn)觀點的物理文件，任何一個文件都存在兩種形式的結(jié)構(gòu)：邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。(1)文件的邏輯結(jié)構(gòu)。這是從用戶觀點出發(fā)所觀察到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)及結(jié)構(gòu)，它獨立于文件的物理特性。(2)文件的物理結(jié)構(gòu)。又稱為文件的存儲結(jié)構(gòu)，是指文件在外存上的存儲組織形式。這不僅與存儲介質(zhì)的存儲性能有關(guān)，而且與所采用的外存分配方式有關(guān)。操作系統(tǒng)對文件邏輯結(jié)構(gòu)提出的基本要求包含以下三個方面：高檢索速度。在將大批記錄組成文件時，應(yīng)有利于提高檢索記錄的速度和效率。便于修改。要便于在文件中增加、刪除和修改一個或多個記錄。低存儲費用。減少文件占用的存儲空間，不要求大片的連續(xù)存儲空間。6.4.1文件邏輯結(jié)構(gòu)的類型文件的邏輯結(jié)構(gòu)可分為兩大類：有結(jié)構(gòu)文件和無結(jié)構(gòu)文件。

1.有結(jié)構(gòu)文件有結(jié)構(gòu)文件又稱記錄式文件，它在邏輯上可以看成是一組連續(xù)記錄的集合，即文件由若干條相關(guān)記錄組成，且對每個記錄編上號碼，依次為記錄1、記錄2、……、記錄n。每個記錄是一組相關(guān)的數(shù)據(jù)集合，用于描述一個對象的某個方面的屬性，如年齡、姓名、職務(wù)、工資等。通常數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫都是采用有結(jié)構(gòu)的文件形式。6.4.1文件邏輯結(jié)構(gòu)的類型有結(jié)構(gòu)文件按照記錄長度是否相同，又可分為定長記錄文件和不定長記錄文件兩種。(1)定長記錄：定長記錄文件中所有記錄的長度相等。定長記錄處理方便，開銷小，被廣泛用于數(shù)據(jù)處理中。(2)變長記錄文件：變長記錄文件中的記錄長度不相等。產(chǎn)生變長記錄的原因，可能是由于一個記錄中所包含的數(shù)據(jù)項數(shù)目并不相同，如書的著作者、論文中的關(guān)鍵詞等；也可能是數(shù)據(jù)項本身的長度不定，例如，病歷記錄中的病因、病史；科技情報記錄中的摘要等。6.4.1文件邏輯結(jié)構(gòu)的類型為了方便用戶使用和系統(tǒng)管理，可采用多種方式來組織這些記錄，形成以下幾種文件：(1)順序文件。由一系列記錄按某種順序排列形成的文件。其中的記錄通常是定長記錄，能用較快的速度查找文件中的記錄。(2)索引文件。主要針對變長記錄的文件，為之建立一張索引表，每個記錄占用一個表項，以加快對記錄檢索的速度。(3)索引順序文件。這是上述兩種文件構(gòu)成方式的組合。6.4.1文件邏輯結(jié)構(gòu)的類型2.無結(jié)構(gòu)的文件無結(jié)構(gòu)文件是由一組相關(guān)信息組成的有序字符流，即流式文件。大量的源程序、可執(zhí)行程序、庫函數(shù)等均采用無結(jié)構(gòu)的文件形式。Windows系統(tǒng)中，所有的文件都被看成是流式文件，即使是有結(jié)構(gòu)文件，也被視為流式文件，系統(tǒng)不對文件進行格式處理。把文件看作字節(jié)流，為操作系統(tǒng)帶來了很大的靈活性。用戶可以根據(jù)需要在自己的文件中加入任何內(nèi)容，而不用操作系統(tǒng)提供任何額外幫助。由于記錄式文件的使用很不方便，尤其是變長記錄文件，另外在文件中還要有說明記錄長度的信息，這就浪費了一部分存儲空間。因此許多現(xiàn)代計算機操作系統(tǒng)，如UNIX操作系統(tǒng)等都取消了記錄式文件。6.4.2順序文件1.文件記錄的排序順序文件是一系列記錄按某種順序排列形成的文件。通常可歸納為以下兩種情況：(1)時間順序結(jié)構(gòu)。各記錄之間的順序與關(guān)鍵字無關(guān)。記錄按存入時間的先后順序排列。(2)關(guān)鍵字順序結(jié)構(gòu)。各記錄按關(guān)鍵字(詞)排列。可以按關(guān)鍵字(詞)的長短從小到大或從大到小排列，或按其英文字母順序排序。對時間順序結(jié)構(gòu)文件，在每次檢索文件時，每次都必須從頭開始，逐個記錄查找，直至找到指定的記錄，或查完所有的記錄為止。對關(guān)鍵字順序結(jié)構(gòu)文件，可采用一些有效的查找算法，如折半查找法、插值查找法、跳步查找法等來提高檢索效率。6.4.2順序文件2.順序文件的讀/寫操作對于定長記錄的順序文件，如果已知當(dāng)前記錄的邏輯地址，可很容易確定下一個記錄的邏輯地址。在讀/寫一個文件時，可設(shè)置一個讀/寫指針Rptr/Wptr，令它指向下一個記錄的首地址，每當(dāng)讀/寫完一個記錄時，便執(zhí)行下式

Rptr/Wptr:=Rptr/Wptr+L

使之指向下一個記錄的首地址，其中的L為記錄長度。對于變長記錄的順序文件，在順序讀/寫時與定長記錄順序文件相似，不同的是在每次讀/寫完一個記錄后，須將讀/寫指針加上Li，Li是剛讀/寫完的記錄的長度。6.4.2順序文件3.順序文件的優(yōu)缺點當(dāng)對記錄文件進行批量存取操作時，即每次要讀寫一大批記錄時，此時，對順序文件的存取效率是所有邏輯文件中最高的。在交互應(yīng)用場合，用戶(程序)需要查找或修改單個記錄，為此系統(tǒng)需要逐個查找諸記錄。這時，順序文件表現(xiàn)出來的性能就可能很差，當(dāng)文件較大時，情況更為嚴(yán)重。例如，一個含有104個記錄的順序文件，如果對它采用順序查找去查找一個指定的記錄，則平均需要查找5

103個記錄。如果是可變長記錄的順序文件，則為查找一個記錄所需付出的開銷將更大。順序文件的另一個缺點是，增加或刪除一個記錄比較困難。6.4.3索引文件在變長記錄文件中引入索引表，即為變長記錄文件建立一張索引表，對主文件中的每個記錄，在索引表中建立一個對應(yīng)的表項，記錄該文件記錄的長度L及指向該記錄的指針(該記錄在邏輯地址空間的首址)。由于索引表是按記錄鍵排序的，因此，索引表本身是一個定長記錄的順序文件，從而可以方便地實現(xiàn)直接存取。在對索引文件進行檢索時，首先根據(jù)用戶(程序)提供的關(guān)鍵字，并利用折半查找法去檢索索引表，從中找到對應(yīng)的表項，再利用該表項中給出的指向記錄的指針值，去訪問所需的記錄。6.4.4索引順序文件索引順序文件是順序文件和索引文件相結(jié)合的產(chǎn)物，是最常見的一種邏輯文件形式。它將順序文件中的所有記錄分為若干個組，為順序文件建立一張索引表，在索引表中為每組中的第一個記錄建立一個索引項，其中含有該記錄的鍵值和指向該記錄的指針。在對索引順序文件進行檢索時，首先利用用戶(程序)提供的關(guān)鍵字以及某種查找算法去檢索索引表，找到該記錄所在記錄組中第一個記錄的表項，從中得到該記錄組第一個記錄在主文件中的位置；然后，再利用順序查找法去查找主文件，從中找到所要訪問的記錄。如果在一個順序文件中包含的記錄數(shù)為N，則為檢索到具有指定關(guān)鍵字的記錄，平均須查找N/2個記錄；但對于索引順序文件，則為能檢索到具有指定關(guān)鍵字的記錄，平均只要查找個記錄數(shù)。6.5文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)指文件在外存上的存儲組織形式，表示一個文件在外存上的安置、鏈接和編目的方法。它和文件的邏輯結(jié)構(gòu)以及外存設(shè)備的特性等都有密切的關(guān)系。因此，在確定一個文件的物理結(jié)構(gòu)時，必須考慮文件的大小、記錄是否定長、訪問的頻繁程度和存取方法等。磁盤的結(jié)構(gòu)允許文件管理系統(tǒng)按三種不同的方式組織文件：連續(xù)文件、鏈接文件、隨機文件。6.5.1連續(xù)文件連續(xù)文件結(jié)構(gòu)是由一組分配在磁盤連續(xù)區(qū)域的物理塊組成的。文件中的每一個記錄有一個序號，序號為i+1的記錄，其物理位置一定緊跟在i號記錄之后。連續(xù)文件結(jié)構(gòu)的優(yōu)點有：(1)存取簡單。若給定記錄號為r，記錄長度為l，物理塊大小為size，則相對塊號計算為：(2)存取速度較快。如果文件中第n個記錄剛被存取過，而下一個要存取的是第n+1個記錄，則這個存取操作會很快完成。

6.5.1連續(xù)文件連續(xù)文件結(jié)構(gòu)的缺點是：如果是直接存取設(shè)備(或稱多路存儲設(shè)備，如磁盤)，在多道程序情況下，由于其他用戶可能驅(qū)使磁頭移向其它柱面，因而就會降低連續(xù)文件的優(yōu)越性。連續(xù)文件結(jié)構(gòu)對于變化少、可以作為一個整體處理的大量數(shù)據(jù)段較為方便，而對那些變化頻繁的少量記錄不宜采用。對于連續(xù)文件結(jié)構(gòu)來說，其文件長度一經(jīng)固定便不易改變，因而不利于文件的增長和擴充。6.5.2鏈接文件鏈接文件結(jié)構(gòu)是按順序由串聯(lián)的塊組成的，即文件的信息按存儲介質(zhì)的物理特性存于若干塊中，一塊中可包含一個邏輯記錄或多個邏輯記錄，或者一個邏輯記錄占有多個物理塊。每個物理塊的最末一個字(或第一個字)作為鏈接字，它指向后繼塊的物理地址。文件的最后一塊的鏈接字為結(jié)束標(biāo)記(例如“

”)，它表示文件至本塊結(jié)束。6.5.2鏈接文件鏈接文件采用的是一種非連續(xù)的存儲結(jié)構(gòu)，文件的邏輯記錄可以存放到不連續(xù)的物理塊中，能較好地利用外存空間。另外，還易于對文件進行擴充，即只要修改鏈接字就可以將記錄插入到文件中間或從文件中刪除若干記錄。對于鏈接文件而言，為了找到一個記錄，文件必須從文件頭開始一塊一塊查找，直到所需的記錄被找到。鏈接文件可以是單鏈結(jié)構(gòu)，也可以是雙鏈結(jié)構(gòu)。在雙鏈結(jié)構(gòu)中，在每個相應(yīng)的物理塊中增加一個后向指針，令它指向上一個記錄所在的物理塊，鏈接文件能反向順序存取。鏈接文件雖比較易于修改，但由于存放鏈指針，所以需要消耗一定的存儲空間。鏈接文件只適用于順序存取方式，不適用于直接存取方式。6.5.3隨機文件隨機文件結(jié)構(gòu)是實現(xiàn)非連續(xù)分配的另一種方式。在隨機文件結(jié)構(gòu)中，文件的數(shù)據(jù)記錄存放在直接存取型存儲設(shè)備上，數(shù)據(jù)記錄的關(guān)鍵字和其地址之間建立某種對應(yīng)關(guān)系，并利用這種關(guān)系進行存取。通常有三種形式的隨機文件結(jié)構(gòu)：直接地址結(jié)構(gòu)、索引結(jié)構(gòu)和散列結(jié)構(gòu)。1.直接地址結(jié)構(gòu)如果知道某個記錄的地址時，可直接使用這個地址進行存取。這就意味著，用戶必須知道每個記錄的具體地址，這是很不方便的。因此，直接地址結(jié)構(gòu)并不常用。當(dāng)然直接地址結(jié)構(gòu)的存取效率最高，因為不需要進行任何“查找”。6.5.3隨機文件2.索引結(jié)構(gòu)索引結(jié)構(gòu)將邏輯文件順序地劃分成長度與物理存儲塊長度相同的邏輯塊，然后為每個文件分別建立邏輯塊號與物理塊號的映射表。這張表稱為該文件的索引表。用這種方法構(gòu)造的文件稱為索引文件。索引文件的索引項按文件邏輯塊號順序排列。6.5.3隨機文件索引文件在存儲區(qū)中占兩個區(qū)：索引區(qū)和數(shù)據(jù)區(qū)。索引區(qū)存放索引表。數(shù)據(jù)區(qū)存放數(shù)據(jù)文件本身。訪問索引文件需要兩步操作。第一步是查文件索引，由邏輯塊號查得物理塊號；第二步是由此物理塊號獲得所要求的信息。因此，需要兩次訪問文件存儲器。如果文件索引表已經(jīng)預(yù)先調(diào)入主存，則只需訪問一次。索引文件的優(yōu)點是可以直接訪問任意記錄，而且便于文件的增刪。當(dāng)增加或刪除記錄時，需要對索引表及時加以修改。由于每次存取都涉及到索引表的查找，因此，所采用的查找策略對文件系統(tǒng)的效率有很大的影響。通常采用的查找策略有兩種：二分查找和順序查找。6.5.3隨機文件3.散列結(jié)構(gòu)在散列結(jié)構(gòu)中，文件中記錄的關(guān)鍵字經(jīng)過散列計算處理，轉(zhuǎn)換成相應(yīng)的物理塊地址，并進行訪問，利用這種散列關(guān)系實現(xiàn)記錄存取的文件叫做散列文件。由于通常地址的總數(shù)比可能的關(guān)鍵字的值的總數(shù)要小得多，即不會是一對一的關(guān)系，因此不同的關(guān)鍵字在散列計算之后，可能會得出相同的地址，稱為“沖突”。一種散列算法是否成功的一個重要標(biāo)志，是看其將不同的關(guān)鍵字映射到同一地址的幾率有多大，如果幾率越小，則該散列算法的性能就越好。即“沖突”產(chǎn)生的幾率越小越好。散列算法的基本思想是根據(jù)關(guān)鍵字來計算相應(yīng)記錄的地址，所以必須解決好如下兩個問題：(1)尋找一個散列函數(shù)h(k)實現(xiàn)關(guān)鍵字到地址的轉(zhuǎn)換。(2)確定解決沖突的方法。6.5.4文件物理結(jié)構(gòu)比較連續(xù)文件的優(yōu)點是不需要額外的空間開銷，只要在目錄中指出起始塊號和文件長度，就可以對文件進行訪問，且一次可以讀出整個文件。對于固定不變且要長期使用的文件(比如系統(tǒng)文件)，這是一種較為節(jié)省的方法。其缺點是：(1)不能