操作系統(tǒng) 課件 第5、6章 存儲管理、文件系統(tǒng)

第5章存儲管理5.1存儲管理概述5.2分區(qū)管理方案5.3覆蓋與交換技術(shù)5.4虛擬頁面存儲管理方案目錄CONTENTSPART5.1存儲管理概述5.1.1存儲體系

計算機系統(tǒng)中的存儲部件是需要物理實現(xiàn)的，理想存儲部件需要高速、海量和非易失的特性，因此存儲管理需要有機組合各種不同的物理存儲部件，形成其自有的體系結(jié)構(gòu)①最先進的計算機科學(xué)技術(shù)能夠提供的存儲部件的速度，仍然明顯地慢于同級別的處理器的速度②由于成本等方面的原因，任何一種存儲部件都無法在速度與容量兩個方面同時滿足用戶的需求③為解決這些矛盾，采用如圖5-1所示的存儲體系結(jié)構(gòu)云存儲(CloudStorage)外存(SecondaryStorage)內(nèi)存(PrimaryStorage)高速緩存(Cache)寄存器(Register)容量大、速度慢、成本低容量小、速度快、成本高圖5-1存儲體系5.1.1存儲體系①寄存器：處理器中暫存信息的；少量的、非?？焖佟嘿F、通常是MB字節(jié)的數(shù)量級；②內(nèi)存RAM：中等速度、中等價格、內(nèi)容易變的、通常是GB字節(jié)的數(shù)量級；③外存磁盤：低速、價廉、內(nèi)容不易變的，通常是TB字節(jié)的數(shù)量級；④外存部件：還包括光盤、磁帶機等，總?cè)萘靠梢栽龃笾罷B或PB字節(jié)；⑤云存儲：大量外存部件有組織地組合在一起并通過高速網(wǎng)絡(luò)和用戶連接快速存儲設(shè)備和大容量存儲設(shè)備必須構(gòu)成為統(tǒng)一的整體，由操作系統(tǒng)協(xié)調(diào)這些存儲器的使用各種速度和容量的存儲器硬件，在操作系統(tǒng)協(xié)調(diào)之下形成了一種存儲器層次結(jié)構(gòu)，或稱存儲體系云存儲(CloudStorage)外存(SecondaryStorage)內(nèi)存(PrimaryStorage)高速緩存(Cache)寄存器(Register)容量大、速度慢、成本低容量小、速度快、成本高圖5-1存儲體系5.1.2存儲管理的任務(wù)程序需要有一個可以長久存放的外存空間，通常是磁盤程序能夠快速運行必須是處理器能夠直接訪問，因此必須占用一定的內(nèi)存空間外存管理通常通過文件系統(tǒng)來實現(xiàn)內(nèi)存管理是對處理器直接訪問的內(nèi)存空間進行管理，所謂內(nèi)存空間是由存儲單元（字節(jié)或字）組成的一維連續(xù)的地址空間，簡稱內(nèi)存空間，用來存放當前正在運行程序的代碼及數(shù)據(jù)，是程序中指令本身地址所指的、亦即程序計數(shù)器所指的存儲器內(nèi)存空間系統(tǒng)區(qū)存放操作系統(tǒng)常駐內(nèi)存部分，用戶不能占用這部分空間操作系統(tǒng)本身還有一部分可以被用戶使用的公共代碼和數(shù)據(jù)也存放在系統(tǒng)區(qū)用戶區(qū)用于裝入并存放用戶程序和數(shù)據(jù)，這部分的信息隨時都在發(fā)生變化內(nèi)存管理本質(zhì)是管理用戶使用空間以及協(xié)調(diào)用戶調(diào)用操作系統(tǒng)公共代碼和數(shù)據(jù)的使用5.1.2存儲管理的任務(wù)內(nèi)存管理方法內(nèi)存的分配和釋放算法虛擬存儲器的管理控制內(nèi)存和外存之間的數(shù)據(jù)流動方法地址變換技術(shù)內(nèi)存數(shù)據(jù)保護與共享技術(shù)對內(nèi)存進行有效的管理，一般把內(nèi)存分成若干個區(qū)域在最簡單的單道、單用戶系統(tǒng)中，至少也要把它分成兩個區(qū)域：在一個區(qū)域內(nèi)存放系統(tǒng)軟件，如操作系統(tǒng)本身；而另外一個區(qū)域則用于安置用戶程序在多道、多用戶系統(tǒng)中，為了提高系統(tǒng)的利用率，需要將內(nèi)存劃分成更多的區(qū)域，以便支持多道程序5.1.2存儲管理的任務(wù)充分利用內(nèi)存，為多道程序并發(fā)執(zhí)行提供存儲基礎(chǔ)盡可能方便用戶使用系統(tǒng)能夠解決程序空間比實際內(nèi)存空間大的問題程序的長度在執(zhí)行時可以動態(tài)伸縮內(nèi)存存取速度快、效率高保證系統(tǒng)和用戶存儲空間的安全，不發(fā)生非法操作提供資源共享與通信交流通道監(jiān)控關(guān)鍵資源的使用狀況較高的性價比內(nèi)存管理要求滿足以下需求5.1.2存儲管理的任務(wù)I內(nèi)存的分配與回收一個有效的內(nèi)存分配機制，應(yīng)對用戶提出的需求予以快速響應(yīng)，為之分配相應(yīng)的內(nèi)存空間；在用戶程序不再需要它時及時回收，以供其他用戶使用。為此，應(yīng)該具有以下功能記住每個內(nèi)存區(qū)域的狀態(tài)內(nèi)存空間哪些是分配了哪些是空閑的實施分配當用戶提出申請時，按需要進行分配。分配方式有靜態(tài)分配和動態(tài)分配兩種回收接受用戶釋放的區(qū)域在計算機操作系統(tǒng)中，通過引入分配表格（統(tǒng)稱為內(nèi)存分配表）來管理內(nèi)存，通常采用2種組織方式實現(xiàn)上述功能，包括：①位示圖表示法：將內(nèi)存按序劃分為固定大小的區(qū)域，稱為內(nèi)存塊，用一位（Bit）表示一個內(nèi)存塊的狀態(tài)（0表示空閑，稱為空閑塊；1表示占用，稱為已用塊）②鏈表法：將已分配的內(nèi)存空間區(qū)域（一個或多個）首地址和長度組成一條記錄，并將所有已分配的記錄按序組成鏈表，形成已分配內(nèi)存鏈表。將未分配的內(nèi)存空間區(qū)域（一個或多個）首地址和長度組成一條記錄，并將所有分配的記錄按序組成鏈表，形成空閑內(nèi)存鏈表。分配時，操作系統(tǒng)查找空閑鏈表；回收時，操作系統(tǒng)合并未空閑鏈表5.1.2存儲管理的任務(wù)I內(nèi)存的分配與回收動態(tài)分配靜態(tài)分配內(nèi)存空間是在目標程序模塊鏈接后裝入內(nèi)存時確定并分配的，并且在程序運行過程中不允許再申請或在內(nèi)存中“搬家”，即分配工作是在程序運行前一次性完成內(nèi)存空間是在目標模塊裝入時或運行時鏈接并確定分配的，但是在程序運行過程中允許申請附加的內(nèi)存空間或在內(nèi)存中“搬家”，即分配工作可以在程序運行前及運行過程中逐步完成①

動態(tài)分配具有較大的靈活性，在程序運行中需要時，操作系統(tǒng)自動將其調(diào)入內(nèi)存②

程序當前暫不使用的信息可以不進入內(nèi)存，這對提高內(nèi)存的利用率大有好處③

動態(tài)分配反映了程序的動態(tài)性，較之靜態(tài)分配更為合理5.1.2存儲管理的任務(wù)I內(nèi)存共享內(nèi)存共享定義共享內(nèi)容目的指兩個或多個進程共用內(nèi)存中相同區(qū)域，多道程序動態(tài)地共享內(nèi)存，提高內(nèi)存利用率。也能共享內(nèi)存中某個區(qū)域的信息代碼共享和數(shù)據(jù)共享特別是代碼共享要求代碼必須是純代碼（運行中不會改變）通過代碼共享節(jié)省內(nèi)存空間，提高內(nèi)存利用率通過數(shù)據(jù)共享實現(xiàn)進程通信5.1.2存儲管理的任務(wù)I內(nèi)存保護內(nèi)存保護保護內(nèi)容目的保護系統(tǒng)程序區(qū)不被用戶有意或無意的侵犯不允許用戶程序讀寫不屬于自己程序的內(nèi)存空間多個程序共享內(nèi)存提供保障，內(nèi)存中的各道程序，只能訪問它自己的區(qū)域當一道程序發(fā)生錯誤時，不至于影響其他程序的運行在多道程序系統(tǒng)中，內(nèi)存中既有操作系統(tǒng)，又有許多用戶程序。為使系統(tǒng)正常運行，避免內(nèi)存中各程序相互干擾，必須對內(nèi)存中的程序和數(shù)據(jù)進行保護方法地址越界保護：進程在運行時所產(chǎn)生的地址超出其地址空間范圍，則發(fā)生地址越界權(quán)限保護：對多個進程共享的公共區(qū)域，每個進程都有自己的訪問權(quán)限5.1.2存儲管理的任務(wù)I“擴充”內(nèi)存容量擴充內(nèi)存容量目的實現(xiàn)意義用戶在編制程序時，通常不受內(nèi)存容量限制，實際運行時受制于具體的物理計算機平臺。操作系統(tǒng)要采用一定技術(shù)來“擴充”內(nèi)存的容量，使用戶得到比物理內(nèi)存容量大得多的內(nèi)存空間在硬件支持下，軟件、硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來統(tǒng)一使用通過這種方法擴充內(nèi)存，使用戶在編制程序時不受內(nèi)存限制借助虛擬存儲技術(shù)或其他交換技術(shù)，達到在邏輯上擴充內(nèi)存容量5.1.3地址轉(zhuǎn)換

存儲器以字節(jié)（每個字節(jié)為8個二進制位）為編址單位，每個字節(jié)都有一個地址與其對應(yīng)。假定存儲器的容量為n個字節(jié)，其地址編號順序為0，1，2，…，n－1。這些地址稱為內(nèi)存的“絕對地址”，由絕對地址對應(yīng)的內(nèi)存空間稱為“物理地址空間”

在多道程序設(shè)計的系統(tǒng)中，內(nèi)存中同時存放了多個用戶程序。操作系統(tǒng)根據(jù)內(nèi)存的使用情況為用戶分配內(nèi)存空間。因此，每個用戶不能預(yù)先知道他的程序?qū)⒈淮娣诺絻?nèi)存的什么位置，用戶程序中就不能使用內(nèi)存的絕對地址。為了方便用戶，每個用戶都可認為自己的程序和數(shù)據(jù)存放在一組“0”地址開始的連續(xù)空間中。用戶程序中使用的地址稱為“邏輯地址”，由邏輯地址對應(yīng)的內(nèi)存空間稱為“邏輯地址空間”5.1.3地址轉(zhuǎn)換I地址重定位地址重定位定義方式邏輯地址轉(zhuǎn)換成絕對地址的工作靜態(tài)重定位動態(tài)重定位

當用戶程序請求執(zhí)行時，內(nèi)存管理要為它分配合適的內(nèi)存空間，該內(nèi)存空間的起始物理（絕對）地址是不固定的，而且起始邏輯地址與分到的起始內(nèi)存空間的物理（絕對）地址經(jīng)常不一致，且后續(xù)也如此。因此，每個邏輯地址在內(nèi)存中也沒有一個固定的物理（絕對）地址與之對應(yīng)

5.1.3地址轉(zhuǎn)換I地址重定位I靜態(tài)重定位

裝入程序前，靜態(tài)重定位把程序中的指令和數(shù)據(jù)的邏輯地址全部轉(zhuǎn)換成絕對地址后再裝入。地址轉(zhuǎn)換工作是在程序開始執(zhí)行前集中完成，所以在程序執(zhí)行過程中就無需再進行地址轉(zhuǎn)換工作圖5-2靜態(tài)重定位

假定用戶程序的邏輯地址空間從“0”到“168”，其中第18號單元處有一條“加法”指令，該指令要求從第066號單元處取出操作數(shù)1234，然后進行加法操作。如果內(nèi)存管理為該程序分配的內(nèi)存區(qū)域是從800號單元開始，那么，邏輯地址第18號單元在內(nèi)存中的對應(yīng)位置是818號單元，第066號單元在內(nèi)存中的對應(yīng)位置應(yīng)該是866號單元。如果不修改上述“加法”指令中的操作數(shù)地址，則處理器執(zhí)行該指令時將從內(nèi)存的066單元中去取操作數(shù)，這顯然是錯誤的，參見圖5-2案例5.1.3地址轉(zhuǎn)換I地址重定位I動態(tài)重定位

裝入程序前，不進行地址轉(zhuǎn)換，而是直接把程序裝入到分配的內(nèi)存區(qū)域中。在程序執(zhí)行過程中，每當執(zhí)行一條指令時都由硬件的地址轉(zhuǎn)換機構(gòu)將程序中的邏輯地址轉(zhuǎn)換成絕對地址

圖5-3指出了動態(tài)重定位的過程。程序裝入到從地址1000開始的內(nèi)存中，從程序起始位于100的地方有一條指令LOAD1,500，意思為將地址500中的數(shù)據(jù)裝入到寄存器1，執(zhí)行時該指令時，需要將該數(shù)據(jù)所在的邏輯地址500與基址寄存器BR（BaseRegister）中的1000相加，得到1500，再去讀取內(nèi)存1500中數(shù)據(jù)并將其放入寄存器1圖5-3動態(tài)重定位案例背景-2：北京大學(xué)圖書館PART5.2分區(qū)管理方案分區(qū)管理分區(qū)管理定義基本思想方式能滿足多道程序運行的最簡單的存儲管理方案把內(nèi)存劃分成若干個連續(xù)區(qū)域，稱為分區(qū)每個分區(qū)裝入一個運行程序固定分區(qū)可變分區(qū)5.2.1固定分區(qū)固定分區(qū)基本思想內(nèi)存分配表

把內(nèi)存劃分成若干個大小固定的分區(qū)，在系統(tǒng)運行期間便不再重新劃分不同程序的存儲要求，各分區(qū)的大小可以不同程序運行時必須提供對內(nèi)存資源的最大申請量是一張分區(qū)說明表，按順序每個分區(qū)在分區(qū)說明表中對應(yīng)一個表項內(nèi)容包括分區(qū)序號、分區(qū)大小、分區(qū)起始地址以及使用狀態(tài)（空閑或占用）

一個程序在運行時，先要根據(jù)其對內(nèi)存的需求量，按一定的分配策略在分區(qū)說明表中查找空閑分區(qū)。若找到能合乎需要的分區(qū)，就將該分區(qū)分配給程序，并將該分區(qū)置為占用狀態(tài)。當程序完成時釋放這塊分區(qū)內(nèi)存，由系統(tǒng)回收，并在分區(qū)說明表中將回收的分區(qū)重新置為空閑狀態(tài)，若有上下鄰空閑分區(qū)，還需要進行合并5.2.1固定分區(qū)圖5-4固定分區(qū)示例在圖5-4中，通過分區(qū)說明表可以看到，區(qū)號為1的分區(qū)大小為8K，起始地址為16K，狀態(tài)為占用，實際是被進程A占用；區(qū)號為2的分區(qū)大小為16K，起始地址為24K，狀態(tài)為空閑；區(qū)號為3的分區(qū)大小為32K，起始地址為40K，狀態(tài)為占用，實際是被進程B占用；如此等等

固定分區(qū)方案都不能充分利用內(nèi)存。因為一個程序的大小，不可能剛好等于某個分區(qū)的大小。所以很難避免內(nèi)存空間的浪費，這種存在于分區(qū)內(nèi)部不可再利用的內(nèi)存空間稱之為內(nèi)碎片

固定分區(qū)方案靈活性差，可接納程序的大小受到了分區(qū)大小的嚴格限制案例5.2.2可變分區(qū)I基本思想可變分區(qū)基本思想1基本思想2系統(tǒng)不預(yù)先劃分固定分區(qū)裝入程序時劃分內(nèi)存分區(qū)，使程序分配的分區(qū)的大小等于該程序的需求量分區(qū)的個數(shù)是可變的、不確定的當有程序要求裝入內(nèi)存運行時，系統(tǒng)從該空閑區(qū)中劃分出一塊與程序大小相同的區(qū)域進行分配當系統(tǒng)運行一段時間后，隨著一系列的內(nèi)存分配和回收。原來的一整塊大空閑區(qū)形成了若干占用區(qū)和空閑區(qū)相間的布局5.2.2可變分區(qū)I基本思想系統(tǒng)為程序D分配一塊內(nèi)存分區(qū)，此時內(nèi)存中剩下了兩塊較小的空閑區(qū)，一塊空閑區(qū)大小為10K,另一塊空閑區(qū)大小為24K。程序E大小為40K，比這兩塊空閑區(qū)大，程序E的需要不能滿足圖5-5可變分區(qū)

某一時刻內(nèi)存空間的布局情況，此時內(nèi)存裝入了A、B、C三個程序，一塊空閑區(qū)大小為10K，另一塊空閑區(qū)大小為94K。此時，又有程序D和程序E請求裝入，程序D大小為70K；表示程序A（大小為16K）和C（大小為30K）已完成，系統(tǒng)回收了它們的占用區(qū)。從程序A回收了16K與原有的10K的空閑區(qū)合并，形成一個26K的空閑區(qū)；從程序C回收了30K，形成一個26K的空閑區(qū)，這樣在內(nèi)存中形成了三塊空閑區(qū)，大小分別是26K、30K和24K，它們的總?cè)萘侩m然遠大于程序E（大小為40K）的需求量，但每塊空閑區(qū)的單獨容量均小于程序E的容量，故系統(tǒng)仍不能為程序E實施分配（a）（b）（c）5.2.2可變分區(qū)I緊縮技術(shù)

內(nèi)存經(jīng)過一段時間的分配回收后，會存在很多很小的空閑塊。它們每一塊都很小，不足以滿足程序分配內(nèi)存的要求，但其總和卻可以滿足程序的分配要求，這些空閑塊很像碎片，這種操作系統(tǒng)知曉的（在內(nèi)存分配鏈表中有記錄），可以分配但區(qū)域很小的空閑空間稱為外碎片。圖5-6內(nèi)存緊縮

解決外碎片問題的辦法是在適當時刻進行碎片整理，通過移動內(nèi)存中的程序，把所有空閑碎片合并成一個連續(xù)的大空閑區(qū)，這種方法稱之為“內(nèi)存緊縮”，又稱為“緊縮技術(shù)”，或“壓縮技術(shù)”5.2.2可變分區(qū)I緊縮技術(shù)

進程E需要40K的空間，在內(nèi)存中，有三塊空閑的外碎片，大小分別是26K、30K和24K，它們的總?cè)萘?0K雖然遠大于進程E（大小為40K）的需求量，但每塊空閑區(qū)的單獨容量均小于進程E的容量，由于普通程序的裝入要求程序的地址空間保持連續(xù)，不得離散，系統(tǒng)仍不能為進程E實施分配，參見圖5-6（a）。采用緊縮技術(shù)之后，在內(nèi)存中的進程B和進程D被移動到內(nèi)存的一端，三塊碎片被拼接為一個大的空閑區(qū)，其容量為80K，參見圖5-6（b）圖5-7緊縮技術(shù)方案的比較圖5-6內(nèi)存緊縮緊縮技術(shù)為進程E的運行創(chuàng)造了條件，進程E被分配了40K空間，還剩下一塊40K的空閑區(qū)5.2.2可變分區(qū)I緊縮技術(shù)緊縮技術(shù)價值注意問題集中分散的空閑區(qū)，提高內(nèi)存的利用率，便于進程動態(tài)擴充內(nèi)存緊縮技術(shù)會增加系統(tǒng)的開銷，也增大了系統(tǒng)運行時間移動是有條件的，不是任何在內(nèi)存中的進程都能隨時移動盡可能減少需要移動的進程數(shù)和信息量5.2.2可變分區(qū)I可變分區(qū)的實現(xiàn)

采用可變分區(qū)方式管理時，硬件設(shè)置兩個專用的控制寄存器：基址寄存器和限長寄存器，限長寄存器用來存放程序所占分區(qū)的長度，基址寄存器用來存放程序所占分區(qū)的起始地址圖5-8可變分區(qū)地址轉(zhuǎn)換5.2.2可變分區(qū)I可變分區(qū)的實現(xiàn)必須設(shè)置某種數(shù)據(jù)結(jié)構(gòu)用以記錄內(nèi)存分配的情況，確定某種分配策略并且實施內(nèi)存的分配與回收可以利用前述已分配內(nèi)存鏈表和空閑內(nèi)存鏈表來管理可變分區(qū)圖5-9已分配區(qū)表和空閑區(qū)表

已分配內(nèi)存鏈表也稱為已分配區(qū)表，記錄已裝入的程序在內(nèi)存中占用分區(qū)的起始地址和長度，用標志位指出占用分區(qū)的程序名。另一個是空閑內(nèi)存鏈表，也稱為空閑區(qū)表，記錄內(nèi)存中可供分配的空閑區(qū)的起始地址和長度，用標志位指出該分區(qū)是未分配的空閑區(qū)。由于已占用分區(qū)和空閑區(qū)的個數(shù)不定，因此，兩張表格中都應(yīng)設(shè)置適當?shù)目諜谀浚謩e用以登記新內(nèi)存分配表項，如圖5-9所示案例5.2.2可變分區(qū)I可變分區(qū)的實現(xiàn)當接到內(nèi)存申請時，順序查找空閑區(qū)表，找到第一個滿足申請長度的空閑區(qū)，將其分割并分配當接到內(nèi)存申請時，查找分區(qū)說明表，找到第一個能滿足申請長度的最小空閑區(qū)，將其分割并分配當接到內(nèi)存申請時，查找分區(qū)說明表，找到能滿足申請要求的最大的空閑區(qū)最先適應(yīng)算法最優(yōu)適應(yīng)算法最壞適應(yīng)算法操作系統(tǒng)查找和分配空閑區(qū)的三種分配算法

5.2.2可變分區(qū)I分區(qū)的回收一個歸還區(qū)可能有上鄰空閑區(qū)，也可以有下鄰空閑區(qū)，或既有上鄰又有下鄰空閑區(qū)，或既無上鄰又無下鄰空閑區(qū)。假定進程歸還的分區(qū)起始地址為S，長度為L。一般情況下應(yīng)考慮如下四種可能性程序執(zhí)行結(jié)束后，系統(tǒng)要回收已使用完畢的分區(qū)，將其記錄在空閑區(qū)表中。在收回空間時，應(yīng)首先檢查是否有與歸還區(qū)相鄰的空閑區(qū)，即檢查相鄰的空閑區(qū)表中標志為“未分配”的欄目，以確定是否有相鄰空閑區(qū)，若有，則應(yīng)合并成一個空閑區(qū)登記回收分區(qū)的上鄰分區(qū)是空閑的，需要將兩個空閑區(qū)合并成一個更大的空閑區(qū)，然后修改空閑區(qū)表

回收分區(qū)的下鄰分區(qū)是空閑的，需要將兩個空閑區(qū)合并成一個更大的空閑區(qū)，然后修改空閑區(qū)表回收分區(qū)的上鄰和下鄰分區(qū)都是空閑的，需要將三個空閑區(qū)合并成一個更大的空閑區(qū)，然后修改空閑區(qū)表回收分區(qū)的上鄰和下鄰分區(qū)都不是空閑的，則直接將空閑分區(qū)記錄在空閑區(qū)表中12345.2.2可變分區(qū)I分區(qū)的保護保護方法一：系統(tǒng)設(shè)置界限寄存器，界限寄存器可以是上、下界寄存器或基址、限長寄存器。通常系統(tǒng)設(shè)置一對界限寄存器，用來存放現(xiàn)行進程的內(nèi)存界限。在進程的PCB中保存界限值，當輪到該進程執(zhí)行時，將界限值作為進程現(xiàn)場的一部分恢復(fù)。在進程執(zhí)行過程產(chǎn)生的每一個訪問內(nèi)存的地址，硬件都自動將其與界限寄存器的值進行比較，若發(fā)生地址越界，便產(chǎn)生保護性地址越界中斷，參見圖5-12保護方法二：保護鍵方法，即為每個分區(qū)分配一個保護鍵，相當于一把鎖。同時為每個進程分配一個相應(yīng)的保護鍵，相當于一把鑰匙，存放在程序狀態(tài)字中。每當訪問內(nèi)存時，都要檢查鑰匙和鎖是否匹配，若不匹配，將發(fā)出保護性中斷圖5-12界限寄存器保護5.2.3分區(qū)管理方案的優(yōu)缺點通過分區(qū)管理，內(nèi)存真正成為了共享資源，提高了系統(tǒng)的吞吐量和縮短了周轉(zhuǎn)時間。分區(qū)內(nèi)存管理算法比較簡單，實現(xiàn)起來比較容易，內(nèi)存額外開銷較少，內(nèi)存保護措施簡單內(nèi)存利用率，可變分區(qū)的內(nèi)存利用率比固定分區(qū)高內(nèi)存使用仍不充分，并且存在著較為嚴重的外碎片問題不能實現(xiàn)對內(nèi)存的“擴充”，程序的存儲要求仍然受到物理存儲器實際內(nèi)存容量的限制分區(qū)管理要求運行程序一次全部裝入內(nèi)存之后，才能開始運行優(yōu)點缺點背景-3：西門華表PART5.3覆蓋與交換技術(shù)5.3.1覆蓋技術(shù)覆蓋技術(shù)定義實現(xiàn)方式意義程序的若干程序段，或幾個程序的某些部分共享某一個存儲空間把程序劃分為若干個功能上相對獨立的程序段，按照其自身的邏輯結(jié)構(gòu)使那些不會同時執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域。未執(zhí)行的程序段先保存在磁盤上，當有關(guān)程序段的前一部分執(zhí)行結(jié)束后，把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段打破需要將一個程序的全部信息裝入內(nèi)存后程序才能運行的限制邏輯上擴充了內(nèi)存空間，從而在某種程度上實現(xiàn)了在小容量內(nèi)存上運行較大程序的功能5.3.1覆蓋技術(shù)

假設(shè)進程1的程序正文由A，B，C，D，E，F(xiàn)，等6個程序段組成。它們之間的調(diào)用關(guān)系如圖5-13（a）所示。其中，程序段A只調(diào)用程序段B和C，程序段B只調(diào)用程序段F，而程序段C只調(diào)用D和E。即B不會調(diào)用C，C也不會調(diào)用B。因此，程序段B和程序段C就無須同時在內(nèi)存中?？砂磮D5-13（b）分配程序段的調(diào)入。可見，雖然該程序正文段所需要的內(nèi)存空間是：A（20K）＋B（50K）＋F（30K）＋C（30K）＋D（20K）＋E（40K）＝190K，但是，在采用了覆蓋技術(shù)后，只需要110K內(nèi)存空間就行了圖5-13覆蓋示例

案例5.3.1交換技術(shù)交換技術(shù)定義實現(xiàn)方式意義又稱對換技術(shù)。在分時系統(tǒng)中，用戶的進程需要的內(nèi)存總量比系統(tǒng)中實際內(nèi)存的總量要多，這就需要在磁盤上保存那些在內(nèi)存放不下的進程。在需要運行這些進程時，再將它們裝入內(nèi)存進程從內(nèi)存移到磁盤，并再移回內(nèi)存稱為交換系統(tǒng)可以將那些不在運行中的進程或其一部分調(diào)出內(nèi)存，暫時存放在外存上的一個后備存儲區(qū)中，以騰出內(nèi)存空間給當前需要內(nèi)存空間的進程，后者可能需要從外存換入內(nèi)存，以后再將換出的進程調(diào)入內(nèi)存繼續(xù)執(zhí)行盡可能達到“足夠快地交換進程，以使當CPU調(diào)度程序想重新調(diào)度CPU時，總有進程在內(nèi)存中處于就緒（準備執(zhí)行）狀態(tài)”的理想狀態(tài)，從而提高內(nèi)存利用率5.3.2交換技術(shù)I相關(guān)考慮問題①

換出進程的選擇

在使用交換技術(shù)時，換出進程的選擇是非常重要的問題，如果處理不當，將會造成整個系統(tǒng)效率低下。在分時系統(tǒng)中，一般情況下可以根據(jù)時間片輪轉(zhuǎn)法或基于優(yōu)先數(shù)的調(diào)度算法來選擇要換出的進程。系統(tǒng)在選擇換出進程時，希望換出的進程是短時間內(nèi)不會立刻投入運行的②

交換時機的確定

一般情況下可以在內(nèi)存空間不夠或有不夠的危險時，換出內(nèi)存中的部分進程到外存，以釋放所需內(nèi)存。也可以當系統(tǒng)發(fā)現(xiàn)一個進程長時間不運行時就將該進程換出5.3.2交換技術(shù)I相關(guān)考慮問題③

交換空間的分配圖5-14磁盤交換空間的管理

在一些系統(tǒng)中，當進程在內(nèi)存中時，不再為它分配磁盤空間。當它被換出時，必須為它分配磁盤交換空間，如圖5-14（b）。每次交換，進程都可能被換到磁盤的不同地方，這種管理交換區(qū)的方法與管理內(nèi)存的方法相同。在另外一些系統(tǒng)中，進程一旦創(chuàng)建，就分配給它磁盤上的交換空間，如圖5-14（a）。無論何時進程被換出，它都被換到已經(jīng)為它分配的空間，而不是每次換到不同的空間。當進程結(jié)束時，交換空間被回收。圖5-14說明了上述二種情形5.3.2交換技術(shù)I相關(guān)考慮問題④

換入進程換回內(nèi)存時位置的確定

換出后再換入內(nèi)存的進程，位置是否一定要在換出前的原來位置上。受絕對地址產(chǎn)生時的限制，如果進程中引用的地址都是絕對地址，那么再次被換入內(nèi)存的進程一定要在原來的位置上。如果進程中引用的地址是相對地址，在裝入內(nèi)存可再進行地址重定位，那么再次被換入內(nèi)存的進程就可以不在原來的位置上背景-4：未名湖PART5.4虛擬頁式存儲管理方案5.4.1虛擬存儲技術(shù)虛擬存儲技術(shù)基本思想實現(xiàn)方式本質(zhì)利用大容量的外存來擴充內(nèi)存，產(chǎn)生一個比有限的實際內(nèi)存空間大得多的、邏輯的虛擬內(nèi)存空間，以便能夠有效地支持多道程序系統(tǒng)的實現(xiàn)和大型程序運行的需要，從而增強系統(tǒng)的處理能力由操作系統(tǒng)在硬件支持下把兩級存儲器（內(nèi)存和外存）統(tǒng)一實施管理，達到“擴充”內(nèi)存的目的，呈現(xiàn)給用戶的是一個遠遠大于物理內(nèi)存容量的編程空間。操作系統(tǒng)把程序當前使用的部分保留在物理內(nèi)存，而把其他部分保存在磁盤上，并在需要時在內(nèi)存和磁盤之間動態(tài)交換虛擬存儲器的容量也是有限制的，主要是受地址空間字長和外存容量所限5.4.1虛擬存儲技術(shù)實現(xiàn)虛擬存儲器需要以下的硬件支持硬件支持系統(tǒng)有容量足夠大的外存系統(tǒng)有一定容量的內(nèi)存最主要的是，硬件提供實現(xiàn)虛-實地址映射的機制5.4.1虛擬存儲技術(shù)

當進程開始運行時，先將一部分程序裝入內(nèi)存，另一部分暫時留在外存；當要執(zhí)行的指令不在內(nèi)存時，由系統(tǒng)自動完成將它們從外存調(diào)入內(nèi)存的工作；當沒有足夠的內(nèi)存空間時，系統(tǒng)自動選擇部分內(nèi)存空間，將其中原有的內(nèi)容交換到磁盤上，并釋放這些內(nèi)存空間供其他進程使用虛擬存儲器的工作原理

傳統(tǒng)的交換技術(shù)中，交換到外存上的對象一般都是進程，也就是說交換技術(shù)是以進程為單位進行；而虛擬存儲——如虛擬頁式存儲管理方案——一般是以頁為交換單位與交換技術(shù)原理上的區(qū)別5.4.1虛擬存儲技術(shù)

當進程運行中，內(nèi)外存交換的單元以固定大小的頁進行時，稱為頁式。頁式是面向系統(tǒng)的技術(shù)，而并不考慮程序的結(jié)構(gòu)，軟硬件系統(tǒng)怎么方便就怎么來，因此，程序的代碼、數(shù)據(jù)、堆棧是不加區(qū)別地均以頁的方式進行分塊。為了計算機映射的方便，頁的大小通常是2的冪次方。虛擬頁式存儲技術(shù)的工作原理

當進程運行中，內(nèi)外存交換的單元以程序的結(jié)構(gòu)特征分類進行時，稱為段式。段式是面向用戶的技術(shù)，考慮程序的組織結(jié)構(gòu)，對代碼段、數(shù)據(jù)段、堆棧段等分別處理，便于進行保護和共享。但是，因為段的大小不固定，所以段式結(jié)構(gòu)除了有段號，還需要有段長的變量，這增加了計算機系統(tǒng)的復(fù)雜度。虛擬段式存儲技術(shù)的工作原理5.4.2虛擬頁式存儲管理虛擬頁式存儲管理發(fā)展實現(xiàn)方式首先由英國曼徹斯特大學(xué)提出，并在該校的Atlas計算機上使用。該技術(shù)近年來已廣泛用于微機系統(tǒng)中，支持頁式存儲管理的硬件部件通常稱為“存儲管理部件”（MMU：MemoryManagementUnit）存儲管理部件首先把內(nèi)存分成大小相等的許多塊，把每個塊稱為“物理頁面”或“頁框”，物理頁面是進行內(nèi)存空間分配的物理單位。同時，要求程序中的邏輯地址也進行分頁，頁的大小與物理頁面的大小一致。此時“邏輯地址”可被稱為虛擬地址。這樣，就可把程序信息按頁存放到物理頁面中。于是，頁式存儲器提供編程使用的虛擬地址由兩部分組成：虛擬頁號和頁內(nèi)地址格式5.4.3物理內(nèi)存的分配與回收

頁式存儲管理分配內(nèi)存空間以物理頁面為單位，由于物理頁面的大小是固定的，所以只要在內(nèi)存分配表中具有可以指出哪些物理頁面已經(jīng)分配、哪些物理頁面尚未分配以及當前剩余的空閑物理頁面數(shù)等三種不同的標識即可圖5-15頁式存儲管理的內(nèi)存分配表

簡單的內(nèi)存分配表可以用一張“位示圖”構(gòu)成。假設(shè)內(nèi)存的可分配區(qū)域被分成256個物理頁面，則可用字長為32位的8個字作為“位示圖”。位示圖中的每一位與一個物理頁面對應(yīng)，每一位的值可以是0或1，0表示對應(yīng)的物理頁面為空閑，1表示已占用。在位示圖中再增加一個字節(jié)記錄當前剩余的總空閑物理頁面數(shù)，如圖5-15所示。初始化時系統(tǒng)在位示圖中把操作系統(tǒng)占用物理頁面所對應(yīng)的位置成1，其余位均置0，剩余空閑物理頁面數(shù)為可分配的空閑物理頁面總數(shù)案例5.4.3物理內(nèi)存的分配與回收圖5-15頁式存儲管理的內(nèi)存分配表在進行內(nèi)存分配時，先查看空閑物理頁面數(shù)是否能滿足程序要求。若不能滿足，則不進行分配，程序就不能裝入內(nèi)存；若能滿足，則根據(jù)需求從位示圖中找出一些為0的位，把這些位置成1，并從空閑頁面數(shù)中減去本次分配的頁面數(shù)，然后按照找到的位計算出對應(yīng)的物理頁面號當找到一個為0的位后，根據(jù)它所在的字號、位號，按如下公式就可計算出對應(yīng)的塊號物理頁面號＝字號×字長＋位號把程序裝入到這些物理頁面中，并為該程序建立頁表。當程序執(zhí)行結(jié)束時，則應(yīng)收回它所占用的物理頁面。根據(jù)歸還的物理頁面號計算出該物理頁面在位示圖中對應(yīng)的位置，將占用標志修改成0，再把回收的物理頁面數(shù)加入到空閑物理頁面數(shù)中假定歸還塊的塊號為i，則在位示圖中對應(yīng)的位置為5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁式存儲管理的地址轉(zhuǎn)換為了實現(xiàn)頁式存儲管理，系統(tǒng)要提供一對硬件的頁表控制寄存器頁表始址寄存器頁表長度址寄存器另外：需要高速緩沖存儲器頁表始址寄存器，用于保存正在運行進程的頁表在內(nèi)存的首地址，當進程被調(diào)度程序選中投入運行時，系統(tǒng)將其頁表首地址從進程控制塊中取出送入該寄存器頁表長度寄存器，用于保存正在運行進程的頁表的長度，當進程被選中運行時，系統(tǒng)將它從進程控制塊中取出送入該寄存器

頁表指出該程序虛擬地址中的頁號與所占用的物理頁面號之間的對應(yīng)關(guān)系。頁表的長度由程序擁有的頁面數(shù)而定，故每個程序的頁表長度可能是不同的

頁表又是硬件進行地址轉(zhuǎn)換的依據(jù)，每執(zhí)行一條指令時按虛擬地址中的頁號查頁表。若頁表中無此頁號，則產(chǎn)生一個“地址錯”的程序性中斷事件。若頁表中有此頁號，則可得到對應(yīng)的物理頁面號，按計算公式可轉(zhuǎn)換成訪問的內(nèi)存的物理地址5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁式存儲管理的地址轉(zhuǎn)換需要強調(diào)的是，物理頁面號又稱為頁幀或頁框號根據(jù)二進制乘法運算的性質(zhì)，一個二進制數(shù)乘以2n結(jié)果實際上是將該數(shù)左移n位。所以，實際上是把物理頁面號作為絕對地址的高位地址，而頁內(nèi)地址作為它的低地址部分。地址轉(zhuǎn)換關(guān)系如圖

圖5-16頁式存儲管理的地址轉(zhuǎn)換關(guān)系物理地址的計算公式為：物理地址=物理頁面號×塊長＋頁內(nèi)地址5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁表項●物理頁面號；頁面在內(nèi)存中時所對應(yīng)的物理頁面號●有效位：又稱駐留位、存在位，表示該頁是在內(nèi)存還是在磁盤●訪問位：訪問位表示該頁在內(nèi)存期間是否被訪問過●修改位：修改位表示該頁在內(nèi)存中是否被修改過●保護位：是否能讀/寫其中，訪問位和修改位可以用來決定置換哪個頁面，具體由頁面置換算法決定

在進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據(jù)進程運行的需要，動態(tài)裝入其他頁面；當內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面

在虛擬頁式存儲管理中，頁表項的設(shè)計如下5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁表當系統(tǒng)支持32位的虛擬地址空間時，若頁面大小為4KB，則頁表將包含1M個表項。假設(shè)每個表項由4個字節(jié)組成，那么僅僅是為了存儲頁表就要為每個進程分配4MB的物理地址空間。假設(shè)用戶地址空間為2GB，頁面大小為4KB，則一個進程最多可以有219頁。若用4個字節(jié)表示一頁的物理頁號，則頁表本身就占用2MB，即需要512個頁面存放，我們稱存放頁表的頁面為頁表頁。一般來說，頁表頁可以不連續(xù)存放，因此，需要對頁表頁的地址進行索引。一個簡單的解決辦法就是分級，例如采用兩級頁表，即頁面大小為4KB的32位機器，虛擬地址可被劃分為10位頁目錄、10位頁表和12位的頁內(nèi)偏移圖5-17二級頁表結(jié)構(gòu)

多級頁表：大多數(shù)現(xiàn)代計算機系統(tǒng)都支持很大的地址空間，由此帶來的結(jié)果是頁表本身也變得很大大多數(shù)32位的操作系統(tǒng)中采用二級頁表，即由頁表頁和頁目錄一起構(gòu)成進程頁表。圖5-17表示了二級頁表結(jié)構(gòu)。其中，第一級表示頁目錄，保存頁表頁的地址；第二級表示頁表頁，保存物理頁面號案例5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁表散列頁表：當?shù)刂房臻g大于32位時，一種常見的方法是使用以頁號為散列值的散列頁表。其中每個表項都包含一個鏈表，該鏈表中元素的散列值都指向同一個位置。這樣，散列頁表中的每個表項都包含三個字段虛擬頁號所映射的頁框號指向鏈表中下一個元素的指針由虛擬頁號得到散列值查找散列頁表，并將此頁號與鏈表中的第一個元素的字段（a）進行比較。如果匹配，則相應(yīng)的頁框號（字段（b））就可用于形成物理地址。如果不匹配，則沿鏈表依次尋找相匹配的表項將上述方法稍作改變而得到的集群頁表更適用于64位的地址空間。它與雜湊頁表相似，不過其中每個表項代表了多個（例如16個）頁面而不是一個。這樣，一個頁表項就存儲了多個物理頁框的映射信息。對于散布于整個地址空間的不連續(xù)內(nèi)存訪問來說，這種集群頁表非常有效使用的算法5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁表

通常，每個進程都有與之相關(guān)的頁表，進程正在使用的每個頁面在頁表中都有一個表項。進程根據(jù)頁面的虛擬地址對其進行訪問，因此這種表示方法是很自然的。但是這種方法也有其缺點，即每個頁表都含有上百萬個表項，僅僅為了記錄內(nèi)存的使用情況就消耗了大量物理內(nèi)存。

為了解決這個問題，我們可以使用反置頁表。因此，整個系統(tǒng)中只存在一個頁表，并且每個頁框?qū)?yīng)其中一個表項。由于一方面系統(tǒng)中只有一個頁表，而另一方面系統(tǒng)中又存在著多個映射著物理內(nèi)存的地址空間，因此需要在反置頁表中存放地址空間標志符。這樣就保證了一個特定進程的邏輯頁面可以映射到相應(yīng)的物理頁框上。64位的UltraSPARC和PowerPC都是使用反置頁表的實例

盡管這種方法減少了為存放每個頁表所使用的內(nèi)存數(shù)量，但卻增加了內(nèi)存訪問時的查表時間。由于反置頁表是按照物理地址排序的，而在使用時卻是按照虛擬地址查找，因此有可能為了尋找相匹配的表項而遍歷全表反置頁表：每個物理頁框?qū)?yīng)一個表項。每個表項包含與該頁框相對應(yīng)的虛擬頁面地址，以及擁有該頁面進程的信息案例5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁表整個系統(tǒng)中只存在一個頁表，并且每個頁框?qū)?yīng)其中一個表項保證了一個特定進程的邏輯頁面可以映射到相應(yīng)的物理頁框上增加了內(nèi)存訪問時的查表時間。由于反置頁表是按照物理地址排序的，而在使用時卻是按照虛擬地址查找，因此有可能為了尋找相匹配的表項而遍歷全表優(yōu)點缺點反置頁表：每個物理頁框?qū)?yīng)一個表項。每個表項包含與該頁框相對應(yīng)的虛擬頁面地址，以及擁有該頁面進程的信息5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I轉(zhuǎn)換檢測緩沖區(qū)(TLB)提高存取速度，有兩種方法圖5-18帶有TLB的頁式存儲管理地址映射過程一種是在地址映射機制中增加一組高速寄存器保存頁表，這需要大量的硬件開銷，在經(jīng)濟上不可行另一種方法是在地址映射機制中增加一個小容量的聯(lián)想寄存器（相聯(lián)存儲器），它由高速緩沖存儲器組成5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I轉(zhuǎn)換檢測緩沖區(qū)(TLB)TLB內(nèi)容的更新原理如下：

當某一用戶程序需要存取數(shù)據(jù)時，根據(jù)該數(shù)據(jù)所在的邏輯頁號在TLB中找出對應(yīng)的物理頁面號，然后拼接頁內(nèi)地址，以形成物理地址；如果在TLB中沒有相應(yīng)的邏輯頁號，則地址映射仍然通過內(nèi)存中的頁表進行；在得到物理頁面號后需將該頁框號填到TLB的空閑單元中；若TLB中沒有空閑單元，則根據(jù)淘汰算法淘汰某一行，再填入新得到的頁框號

實際上，查找TLB和查找內(nèi)存頁表是并行進行的，一旦發(fā)現(xiàn)TLB中有與所查頁號一致的邏輯頁號就停止查找內(nèi)存頁表，而直接利用TLB中的邏輯頁號

假定訪問內(nèi)存的時間為200毫微秒，訪問高速緩沖存儲器的時間為40毫微秒，高速緩沖存儲器為16個單元時，查TLB的命中率為90％。于是，按虛擬地址轉(zhuǎn)換成絕對地址進行存取的平均訪問時間為（200＋40）×90％＋（200＋200）×10％＝256（毫微秒）不使用TLB需兩次訪問內(nèi)存的時間：200×2＝400毫微秒?？梢娛褂肨LB與不使用TLB相比，訪問時間下降了36％案例5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I缺頁異常處理

當發(fā)生缺頁異常時，操作系統(tǒng)必須在內(nèi)存中尋找一個新的物理頁面（頁框）來進行分配，若沒有空閑的頁框，則選擇一個裝有信息的物理頁面將其信息移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間圖5-19缺頁異常處理流程圖

如果要移走的頁面在內(nèi)存期間已經(jīng)被修改過，就必須把它寫回磁盤以更新該頁在磁盤上的副本。如果該頁沒有被修改過，那么它在磁盤上的副本仍然是有效的，則不需要寫回，調(diào)入的頁面直接覆蓋被淘汰的頁面圖5-19缺頁異常處理流程圖5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I缺頁異常處理①根據(jù)執(zhí)行指令中的邏輯地址查頁表的有效位，判斷該頁是否在內(nèi)存②該頁標志為“0”，形成缺頁異常。保留現(xiàn)場。中斷裝置通過交換PSW讓操作系統(tǒng)的缺頁中斷處理程序占用處理器③操作系統(tǒng)處理缺頁異常，尋找一個空閑的物理頁面④若有空閑頁，則把磁盤上讀出的信息裝入該頁面中⑤修改頁表及內(nèi)存分配表，表示該頁已在內(nèi)存⑥如果內(nèi)存中無空閑頁，則按某種算法選擇一個已在內(nèi)存的頁面，把它暫時調(diào)出內(nèi)存。若在執(zhí)行中該頁面已被修改過，則要把該頁信息重新寫回到磁盤上（否則不必重新寫回磁盤）。當一頁被暫時調(diào)出內(nèi)存后，讓出的內(nèi)存空間用來存放當前需要使用的頁面。頁面被調(diào)出或裝入之后都要對頁表及內(nèi)存分配表作修改⑦恢復(fù)現(xiàn)場，重新執(zhí)行被中斷的指令。當重新執(zhí)行該指令時，由于要訪問的頁面已被裝入內(nèi)存，所以可正常執(zhí)行下去整個缺頁處理過程如下5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁面調(diào)度策略頁面調(diào)度策略調(diào)入策略置頁策略置換策略虛擬存儲器的調(diào)入策略決定了什么時候?qū)⒁粋€頁面由外存調(diào)入內(nèi)存之中當線程產(chǎn)生缺頁時，內(nèi)存管理器還必須確定將調(diào)入的虛擬頁放在物理內(nèi)存的何處。用于確定最佳位置的一組規(guī)則稱為“置頁策略”。選擇頁框應(yīng)使CPU、內(nèi)存和高速緩存不必要的震蕩最小，因此WindowsServer2003需要考慮CPU內(nèi)存高速緩存的大小如果缺頁發(fā)生時物理內(nèi)存已滿，“置換策略”被用于確定哪個物理頁面必須從內(nèi)存中移出為新的頁面騰出空位。在虛擬頁式存儲管理方案中，存在有兩種頁面分配策略，即固定和可變分配策略5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁面調(diào)度策略調(diào)入策略請求調(diào)頁預(yù)調(diào)頁只調(diào)入發(fā)生缺頁時所需的頁面。這種調(diào)入策略實現(xiàn)簡單，但容易產(chǎn)生較多的缺頁異常，造成對外存I/O次數(shù)多，時間開銷過大，容易產(chǎn)生顛簸現(xiàn)象在發(fā)生缺頁需要調(diào)入某頁時，一次調(diào)入該頁以及相鄰的幾個頁。這種策略提高了調(diào)頁的I/O效率，減少了I/O次數(shù)。但由于這是一種基于局部性原理的預(yù)測，若調(diào)入的頁在以后很少被訪問，則造成浪費。這種方式常在程序裝入時使用

虛擬存儲器的調(diào)入策略決定了什么時候?qū)⒁粋€頁面由外存調(diào)入內(nèi)存之中。在虛擬頁式管理中有兩種常用調(diào)入策略5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁面調(diào)度策略置換策略固定分配局部置換

可變分配全局置換

可變分配局部置換

根據(jù)進程的類型，為每一進程分配固定的頁數(shù)的內(nèi)存空間，在整個運行期間都不再改變。采用該策略時，如果進程在運行中出現(xiàn)缺頁，則只能從分配給該進程的頁面中選出一個換出，然后再調(diào)入一頁，以保證分配給該進程的內(nèi)存空間總數(shù)不變采用這種策略時，先為系統(tǒng)中的每一進程分配一定數(shù)量的內(nèi)存空間，操作系統(tǒng)本身也保持一個空閑物理頁面的隊列。當某進程發(fā)生缺頁時，由系統(tǒng)的空閑物理頁面隊列中取出物理頁面分配給該進程。但當空閑物理頁面隊列中的物理頁面用完時，操作系統(tǒng)才從所有內(nèi)存中按規(guī)定的置換算法選擇一頁調(diào)出。該頁可能是系統(tǒng)中任意一個進程的頁同樣基于進程的類型，為每一進程分配一定數(shù)目的內(nèi)存空間。但當某進程發(fā)生缺頁時，只允許從分配給該進程的頁面中選出一頁換出，這樣就不影響其他進程的運行。如果進程在運行的過程中，頻繁的發(fā)生缺頁，則系統(tǒng)再為該進程增加分配若干物理頁面，直到進程的缺頁率降低到適當程度為止

如果缺頁發(fā)生時物理內(nèi)存已滿，“置換策略”被用于確定哪個物理頁面必須從內(nèi)存中移出為新的頁面騰出空位。在虛擬頁式存儲管理方案中，存在有兩種頁面分配策略，即固定和可變分配策略5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁面置換算法

每次發(fā)生缺頁時，當然可以隨機選擇一個頁面置換。但是如果一個經(jīng)常使用的頁被置換出去，很有可能它很快又要被調(diào)入內(nèi)存，帶來不必要的額外開銷。所以選擇不常使用的頁面會使系統(tǒng)性能好得多

頁面置換算法的優(yōu)劣將會影響虛擬存儲系統(tǒng)的性能，進而影響整個系統(tǒng)的性能。下面將介紹幾個主要的頁面置換算法

如果剛被調(diào)出的頁面又立即要用，因而又要把它裝入，而裝入不久又被選中調(diào)出，調(diào)出不久又被裝入，如此反復(fù)，使調(diào)度非常頻繁。這種現(xiàn)象稱為“抖動”或稱“顛簸”該算法淘汰以后不再需要的，或者在最長時間以后才會用到的頁面。這一算法一般不可能實現(xiàn)，但它可以作為衡量其他頁面淘汰算法優(yōu)劣的一個標準理想頁面置換算法（OPT）5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁面置換算法先進先出頁面置換算法總是選擇最先裝入內(nèi)存的一頁調(diào)出，或者說是把駐留在內(nèi)存中時間最長的一頁調(diào)出先進先出頁面置換算法（FIFO：First-InFirst-Out）實現(xiàn)方案：把裝入內(nèi)存的那些頁面的頁號按進入的先后次序排好隊列，每次總是調(diào)出隊首的頁，當裝入一個新頁后，把新頁的頁號排入隊尾。由操作系統(tǒng)維護一個所有當前在內(nèi)存中的頁面的鏈表，最老的頁面在頭上，最新的頁面在表尾。當發(fā)生缺頁時，淘汰表頭的頁面并把新調(diào)入的頁面加到表尾。在具體實現(xiàn)時，可用指針K指示最早被裝入內(nèi)存的那頁在隊列中的位置，每次總是選擇指針K指示的頁調(diào)出，在裝入一個新頁后，在指針指示的位置上填上新頁頁號，然后指針K加1，指出下一次可調(diào)出的頁5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁面置換算法檢查進入內(nèi)存時間最久頁面的R位，如果是0，那么這個頁面既老又沒有被使用，可以立刻置換掉；如果是1，就將R位清0，并把該頁面放到鏈表的尾端，修改其進入時間，然后繼續(xù)搜索這一算法稱為第二次機會（SecondChance）算法，其基本思想是尋找一個最近的時鐘間隔以來沒有被訪問過的頁面。如果所有的頁面都被訪問過了，該算法就退化為FIFO算法第二次機會頁面置換算法把所有的頁面都保存在一個類似時鐘面的環(huán)形鏈表中，一個表針指向最老的頁面當發(fā)生缺頁時，算法首先檢查表針指向的頁面，如果它的R位是0就置換該頁面，并把新的頁面插入這個位置，然后把表針前移一個位置如果R位是1就清除R位并把表針前移一個位置，重復(fù)這個過程直到找到了一個R位為0的頁面為止。由于這個算法的工作方式，就將它稱為時鐘（clock）算法時鐘頁面置換算法（Clock）5.4.4虛擬頁式存儲地址轉(zhuǎn)換過程I頁面置換算法在缺頁發(fā)生時，首先淘汰掉最長時間未被使用過的頁面。這個策略稱為LRU頁面置換算法實現(xiàn)方案

在頁表中為每一頁增加一個“計時”標志，記錄該頁面自上次被訪問以來所經(jīng)歷的時間，每被訪問一次都應(yīng)從“0”開始重新計時。當要裝入新頁時，檢查頁表中各頁的計時標志，從中選出計時值最大的那一頁調(diào)出（即最近一段時間里最長時間沒有被使用過的頁），并且把各頁的計時標志全置成“0”，重新計時。當再一次產(chǎn)生缺頁異常時，又可找到最近最久未使用過的頁，將其調(diào)出。這種實現(xiàn)方法必須對每一頁的訪問情況時時刻刻地加以記錄和更新，實現(xiàn)起來開銷比較大,但LRU是在效果上最接近OPT的算法最近最少使用頁面置換算法（LRU：LeastRecentlyUsed）5.4.5虛擬頁式存儲管理的優(yōu)點缺點由于它不要求進程的程序段和數(shù)據(jù)在內(nèi)存中連續(xù)存放，從而有效地解決了碎片問題。這既提高了內(nèi)存的利用率，又有利于組織多道程序執(zhí)行存在頁面空間的浪費問題。這是由于各種程序代碼的長度是各不相同的，但頁面的大小是固定的，所以在每個程序的最后一頁內(nèi)總有一部分空間得不到利用，稱為內(nèi)碎片。如果頁面較大，則由此引起的存儲空間的損失仍然較大優(yōu)點缺點5.4.5虛擬存儲管理的性能問題

引入虛擬存儲管理，把內(nèi)存和外存統(tǒng)一管理，其真正目的，是把那些訪問概率非常高的頁放入內(nèi)存，減少內(nèi)外存交換的次數(shù)采用工作集模型，可以解決顛簸問題

在虛存中，頁面可能在內(nèi)存與外存之間頻繁地調(diào)度，有可能出現(xiàn)抖動或顛簸。當系統(tǒng)出現(xiàn)這一現(xiàn)象時，系統(tǒng)用于調(diào)度頁面所需要的時間比進程實際運行所占用的時間還多，系統(tǒng)效率會急劇下降。顛簸是由于缺頁率高而引起的。5.4.5虛擬存儲管理的性能問題

對于給定的進程訪頁序列，從時刻（t-Δ）到時刻t之間所訪問頁面的集合，稱為該進程的工作集。其中，Δ稱為工作集窗口

工作集是隨時間而變化的，如圖5-21所示。工作集大小與窗口尺寸密切相關(guān)由模擬實驗知道，任何程序?qū)?nèi)存都有一個臨界值要求，當分配給進程的物理頁面數(shù)小于這個臨界值時，缺頁率上升；當分配給進程的物理頁面數(shù)大于該臨界值時，再增加物理頁面數(shù)也不能顯著減少缺頁次數(shù)。因此，希望分配給進程的物理頁面數(shù)與當前工作集大小一致感謝大家聆聽THANKSFORTHECAREFULGUIDANCE第6章文件系統(tǒng)學(xué)習目標<71

>1．掌握文件、文件系統(tǒng)的基本概念2．掌握文件控制塊、目錄項、文件目錄及目錄文件的概念3．理解文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及其適用環(huán)境4．掌握目錄檢索、磁盤空間管理、記錄的成組與分解等文

件管理方法5．了解文件和目錄的各種操作6．了解文件共享和文件保護的各種方法6.1文件管理的基本概念6.2文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)6.3文件目錄6.4文件存儲空間管理6.5實現(xiàn)文件系統(tǒng)的表目6.6文件及文件目錄的操作6.7文件系統(tǒng)的性能6.8文件共享、保護目錄CONTENTSPART6.1文件管理的基本概念文件管理的基本概念<74

>文件文件可以被解釋為一組帶標識的、在邏輯上有完整意義的信息項的序列文件系統(tǒng)文件系統(tǒng)是操作系統(tǒng)中統(tǒng)一管理信息資源的一種軟件文件管理的基本概念<75

>文件系統(tǒng)的功能：（1）統(tǒng)一管理文件的存儲空間，實施存儲空間的分配與回收（2）實現(xiàn)文件從名字到外存地址空間的映射即實現(xiàn)文件的按名存取（3）實現(xiàn)文件信息的共享，并提供文件的保護措施（4）向用戶提供一個方便使用的接口（5）系統(tǒng)維護及向用戶提供有關(guān)信息（6）保持文件系統(tǒng)的執(zhí)行效率文件系統(tǒng)在操作系統(tǒng)接口中占的比例最大（7）提供I/O的統(tǒng)一接口文件管理的基本概念<76

>外存儲設(shè)備的特點外存儲設(shè)備通常由驅(qū)動部分和存儲介質(zhì)兩部分組成。存儲介質(zhì)又常被稱為卷，“卷”字來自把存儲介質(zhì)看作“信息容器”的比喻。驅(qū)動器的作用是使計算機能夠?qū)崿F(xiàn)讀寫（及保存、控制、測試）存儲介質(zhì)上的內(nèi)容外存儲設(shè)備的存儲介質(zhì)（1）磁帶（2）磁盤（3）光盤（4）閃存文件管理的基本概念<77

>文件結(jié)構(gòu)、文件存取方式與存儲介質(zhì)文件常用的存取方法有：順序存取和隨機存取等兩種方式選擇哪一種文件的存取方式，既取決于用戶使用文件的方式，也與文件所使用的存儲介質(zhì)有關(guān)（1）順序存取:按從前到后的次序依次訪問文件的各個信息項（2）隨機存取:隨機存取又稱直接存取，即允許用戶按任意的次序、直接存取文件中的任意一個記錄，或者根據(jù)存取命令把讀寫指針移到文件中的指定記錄處讀寫.文件管理的基本概念<78

>為了有效、方便地管理文件，在文件系統(tǒng)中，常常把文件按其性質(zhì)和用途的不同進行分類按文件的用途分類:系統(tǒng)文件、庫函數(shù)文件、用戶文件

按文件的組織形式分類：普通文件、目錄文件、特殊文件文件管理的基本概念<79

>一些常見的文件分類方式按文件的保護方式可劃分為：只讀文件、讀寫文件、可執(zhí)行文件、無保護文件等按信息的流向分類可劃分為：輸入文件、輸出文件和輸入輸出文件等按文件的存放時限可劃分為：臨時文件、永久文件和檔案文件等

按文件所使用的介質(zhì)類型分類可劃分為：磁盤文件、磁帶文件、卡片文件和打印文件等上述種種文件系統(tǒng)的分類，其目的是：對不同文件進行管理，提高系統(tǒng)效率；同時，提高文件系統(tǒng)的用戶界面友好性背景-2：北京大學(xué)圖書館PART6.2文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)<81

>文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)設(shè)計文件邏輯結(jié)構(gòu)的原則與文件的邏輯結(jié)構(gòu)相聯(lián)系的是邏輯文件的存取方式，即用戶如何訪問文件在文件系統(tǒng)設(shè)計時，到底選擇何種邏輯結(jié)構(gòu)才能更有利于用戶對文件信息的操作呢？這里，我們列出在一般情況下，設(shè)計文件的邏輯結(jié)構(gòu)時應(yīng)遵循的一些設(shè)計原則：（1）易于操作（2）查找快捷（3）修改方便（4）空間緊湊<82

>文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)文件的邏輯結(jié)構(gòu)就是用戶所看到的文件的組織形式文件邏輯結(jié)構(gòu)是一種經(jīng)過抽象的結(jié)構(gòu)，所描述的是文件中信息的組織形式，與文件在物理介質(zhì)上的具體存儲結(jié)構(gòu)不同。文件劃分成三類邏輯結(jié)構(gòu)：無結(jié)構(gòu)的字符流式文件、定長記錄文件和不定長記錄文件構(gòu)成的記錄樹，如圖所示：邏輯文件的種類<83

>文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)定長記錄文件和不定長記錄文件可以統(tǒng)稱為記錄式文件（1）流式文件流式文件是有序字符的集合（2）記錄式文件記錄式文件是一組有序記錄的集合

文件的物理結(jié)構(gòu)從研究文件管理、設(shè)計文件管理系統(tǒng)的角度來看，必須研究如何在物理存儲器上存儲文件，這是文件系統(tǒng)實現(xiàn)的物理基礎(chǔ)常用的文件物理結(jié)構(gòu)有順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)<84

>文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)順序結(jié)構(gòu)原理順序結(jié)構(gòu)又稱連續(xù)結(jié)構(gòu)，這是一種最簡單的文件物理結(jié)構(gòu)，它把邏輯上連續(xù)的文件信息依次存放在連續(xù)編號的物理塊中。在順序結(jié)構(gòu)中，一個文件的目錄項中只要指出該文件占據(jù)的總塊數(shù)和起始塊號即可順序結(jié)構(gòu)的優(yōu)缺點順序結(jié)構(gòu)的優(yōu)點是，一旦知道了文件在文件存儲設(shè)備上的起始塊號和文件長度，就能很快地進行存取。這是因為從文件的邏輯塊號到物理塊號的變換是非常簡單的。順序結(jié)構(gòu)支持順序存取和隨機存取文件的順序結(jié)構(gòu)<85

>文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)鏈接結(jié)構(gòu)原理文件的鏈接結(jié)構(gòu)的實質(zhì)就是為每個文件構(gòu)造所使用磁盤塊的鏈表文件的鏈接結(jié)構(gòu)<86

>文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)鏈接結(jié)構(gòu)的優(yōu)缺點鏈接結(jié)構(gòu)的優(yōu)點是，存儲碎片問題迎刃而解了，有利于文件動態(tài)擴充，有利于文件插入和刪除，提高了磁盤空間利用率鏈接結(jié)構(gòu)的主要缺點是，存取速度慢，不適于隨機存取文件；磁盤的磁頭移動多，效率相對較低；存在文件的可靠性問題，比如指針出錯，文件也就出錯了；另外，鏈接指針需要占用一定的空間為了提高可靠性，可以采用雙向鏈接，或者在每個物理塊中存儲文件名稱和相對塊號等辦法改進。不過這些辦法只能有限地提高可靠性，并不能從根本解決問題，而且需要耗費更多的空間，典型的鏈接結(jié)構(gòu)是FAT文件系統(tǒng)<87

>文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)FAT文件系統(tǒng)的結(jié)構(gòu)<88

>文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)索引結(jié)構(gòu)原理索引結(jié)構(gòu)的文件把每個物理盤塊的指針字，集中存放在稱為索引表的數(shù)據(jù)結(jié)構(gòu)中的內(nèi)存索引表中。在每個文件相應(yīng)的目錄條目中包括該文件的索引表地址，而索引表中的第i個條目指向文件的第i塊，如圖所示，要讀某個文件的第i塊，只需從該文件索引表的第i個條目中得到該文件塊的地址即可索引文件結(jié)構(gòu)<89

>文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)索引文件結(jié)構(gòu)的優(yōu)缺點索引文件結(jié)構(gòu)保持了鏈接結(jié)構(gòu)的優(yōu)點，又解決了其缺點索引結(jié)構(gòu)文件既適于順序存取，也適用于隨機存取。索引文件可以滿足文件動態(tài)增長的要求，也滿足了文件插入、刪除的要求索引文件還能充分利用外存空間索引結(jié)構(gòu)的缺點是：會引起較多的尋道次數(shù)和尋道時間；索引表本身增加了存儲空間的開銷索引表應(yīng)該多大？應(yīng)該定長還是變長？解決問題的辦法有以下一些種類：①索引表的鏈接模式：一個索引表通常就是一個物理盤塊這樣，讀寫索引表比較簡單對大文件就用多個索引表并將之鏈接在一起②多級索引：這是上述索引表鏈接模式的一種改善變種<90

>文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)UNIX的三級索引結(jié)構(gòu)i節(jié)點的三級索引結(jié)構(gòu)背景-3：西門華表文件目錄PART6.3<92

>文件目錄文件控制塊文件控制塊FCB是系統(tǒng)為管理文件而設(shè)置的一個數(shù)據(jù)結(jié)構(gòu)FCB是文件存在的標志，它記錄了系統(tǒng)管理文件所需要的全部信息FCB通常應(yīng)包括以下內(nèi)容：文件名，文件號，用戶名，文件地址，文件長度，文件類型，文件屬性，共享計數(shù)，文件的建立日期，保存期限，最后修改日期，最后訪問日期，口令，文件邏輯結(jié)構(gòu)，文件物理結(jié)構(gòu)等等<93

>文件目錄文件控制塊中主要的欄目

一級目錄結(jié)構(gòu)<94

>文件目錄文件目錄是實現(xiàn)用戶按名存取文件的一種手段為了能夠方便用戶的檢索和文件的管理，根據(jù)實際的需要，一般把文件目錄設(shè)計成一級（單級）目錄結(jié)構(gòu)、二級目錄結(jié)構(gòu)和多級目錄結(jié)構(gòu)一級目錄結(jié)構(gòu)在系統(tǒng)中設(shè)置一張線性目錄表，表中包括了所有文件的文件控制塊，每個文件控制塊指向一個普通文件，這就是一級目錄結(jié)構(gòu)<95

>文件目錄二級目錄結(jié)構(gòu)為克服一級目錄中文件目錄命名中的可能沖突，并提高對目錄文件的檢索速度，一級目錄被改進擴充成二級目錄二級目錄結(jié)構(gòu)多級目錄結(jié)構(gòu)<96

>文件目錄多級目錄把二級目錄的層次關(guān)系加以推廣，就形成了多級目錄，又稱樹型目錄結(jié)構(gòu)UNIX系統(tǒng)中的一棵目錄樹<97

>文件目錄多級目錄結(jié)構(gòu)的優(yōu)點是便于文件分類，且具有下列特點：（1）層次清楚（2）解決了文件重名問題（3）查找搜索速度快目前大多數(shù)操作系統(tǒng)如UNIX、Linux類、Windows等都采用多級目錄結(jié)構(gòu)。在右圖中給出了UNIX操作系統(tǒng)的一棵目錄樹<98

>文件目錄當前目錄與目錄檢索文件系統(tǒng)向用戶提供了一個當前正在使用的目錄，稱為“當前目錄”，又稱“工作目錄”如果需要，用戶可隨意更改當前目錄用戶在訪問文件時，需要進行目錄檢索，這時用戶給出文件名，系統(tǒng)按名尋找目錄項。有兩種根據(jù)路徑名檢索的方法：一種是全路徑名，另一種是相對路徑<99

>文件目錄目錄項分解法即把目錄項（FCB）分為兩部分，符號目錄項（次部）和基本目錄項（主部）其中，符號目錄項包含文件名以及相應(yīng)的文件號；而基本目錄項包含了除文件名外文件控制塊的其他全部信息目錄項分解法目錄項當用戶建立一個新文件時，與該文件有關(guān)的一些信息與屬性記錄在該文件的文件控制塊內(nèi)。為了便于管理，通常將文件控制塊做成定長數(shù)據(jù)結(jié)構(gòu)的一個記錄，存放在目錄文件中而這樣的每一個記錄稱為目錄項目錄文件多個文件的文件控制塊集中在一起組成了文件的目錄通常，文件目錄以文件的形式保存起來，這個文件就被稱為目錄文件<100

>文件目錄UNIX的文件目錄實現(xiàn)V7文件系統(tǒng)中，UNIX目錄中為每個文件保留了一項，如圖中表示每個目錄項包含了兩個域，文件名（14個字節(jié)）和i節(jié)點的編號（2個字節(jié)）UNIX的目錄項<101

>文件目錄系統(tǒng)讀根目錄并且在根目錄中查找路徑的第一個分量user，以獲取/user目錄的i節(jié)點號由i節(jié)點號來定位i節(jié)點是很直接的，因為每個i節(jié)點在磁盤上都有固定的位置根據(jù)這個i節(jié)點，系統(tǒng)定位/user目錄并在其中查找下一個分量ast一旦找到ast的項，便找到了/user/ast目錄的i節(jié)點依據(jù)這個i節(jié)點，可以定位該目錄并在其中查找mbox然后，這個文件的i節(jié)點被讀入內(nèi)存，并且在文件關(guān)閉之前會一直保留在內(nèi)存中，如圖闡述了查找的過程

查找/usr/ast/mbox的過程<102

>文件目錄FAT文件系統(tǒng)的實現(xiàn)FAT是FileAllocationTable（文件分配表）的縮寫。FAT文件系統(tǒng)總共有三個版本：FAT-12，F(xiàn)AT-16和FAT-32，取決于用多少二進制位表示磁盤塊地址

下圖說明了FAT文件系統(tǒng)是如何組織一個卷的文件分配表位于卷的開頭，為了防止文件系統(tǒng)遭到破壞，F(xiàn)AT文件系統(tǒng)保存了兩個文件分配表，這樣當其中一個遭到破壞時可以保護卷此外，文件分配表和根目錄必須存放在磁盤上一個固定的位置，這樣才可以正確地找到啟動系統(tǒng)所需要的文件FAT卷的結(jié)構(gòu)<103

>文件目錄引導(dǎo)扇區(qū)引導(dǎo)扇區(qū)（BootSector）包含用于描述卷的各種信息，利用這些信息才可以訪問文件系統(tǒng)在基于X86的計算機上，主引導(dǎo)記錄（MasterBootRecord）使用系統(tǒng)分區(qū)上的引導(dǎo)扇區(qū)來加載操作系統(tǒng)的核心文件文件分配表文件分配表包含關(guān)于卷上每個簇的如下類型的信息，括號中是FAT16的樣值：未使用（0x0000，被文件所使用的簇，壞簇（0xFFF7），文件中的最后一簇（0xFFF8-0xFFFF）在FAT目錄結(jié)構(gòu)中，每個文件都給出了它在卷上的起始簇號起始簇號是文件所使用的第一個簇的地址，每個簇都包含一個指針，指向文件中的下一簇，或者包含一個指示符(0xFFFF)，表明該簇是文件的結(jié)尾這些鏈接以及文件結(jié)尾指示符如圖所示。

文件分配表的例子<104

>文件目錄根目錄在FAT16文件系統(tǒng)中，位于根目錄下的每個文件和子目錄在根目錄區(qū)中都包含一個目錄項。根目錄與其他目錄之間的唯一區(qū)別是，根目錄位于磁盤上一個特殊的位置并且具有固定的大小，每個目錄項的大小為32字節(jié)，其內(nèi)容包括：文件名、擴展名、屬性字節(jié)、最后一次修改時間和日期、文件長度、第一簇的編號等背景-4：未名湖PART6.4文件存儲空間管理<106

>文件存儲空間管理磁盤空間的分配回收算法在設(shè)計空閑空間登記表的數(shù)據(jù)結(jié)構(gòu)時，一般有四種不同的方案可以考慮1.位示圖位示圖法的基本思想是，利用一串二進制位（bit）的值來反映磁盤空間的分配使用情況在位示圖中，每一個磁盤中物理塊用一個二進制位對應(yīng)，如果某個物理塊為空閑，則相應(yīng)的二進制位為0；如果該物理塊已分配了，則相應(yīng)的二進位為1，如圖所示圖位示圖<107

>文件存儲空間管理位示圖對空間分配情況的描述能力強，一個二進位就描述一個物理塊的狀態(tài)。另外，位示圖占用空間較小，因此可以復(fù)制到內(nèi)存，使查找既方便又快速位示圖適用于各種文件物理結(jié)構(gòu)的文件系統(tǒng)使用位示圖能夠簡單有效地在盤上找到n個連續(xù)的空閑塊，很多計算機提供了位操作指令，使位示圖的查找能夠高效進行例如，Intelx86微處理器系列就有這樣的指令：返回指定寄存器的所有位中值為1的第一位空閑塊表<108

>文件存儲空間管理空閑塊表空閑塊表是專門為空閑塊建立的一張表，該表記錄外存儲器全部空閑的物理塊：包括每個空閑塊的第一個空閑物理塊號和和該空閑塊中空閑物理塊的個數(shù)。如圖所示，空閑塊表方式特別適合于文件物理結(jié)構(gòu)為順序結(jié)構(gòu)的文件系統(tǒng)<109

>文件存儲空間管理空閑塊鏈表將外存儲器中所有的空閑物理塊連成一個鏈表，用一個空閑塊首指針指向第一個空閑塊，隨后的每個空閑塊中都含有指向下一個空閑塊的指針，最后一塊的指針為空，表示鏈尾，這樣就構(gòu)成了一個空閑塊鏈表，如圖所示空閑塊鏈表<110

>文件存儲空間管理UNIX系統(tǒng)的空閑塊成組鏈接法

空閑塊成組鏈接表<111

>文件存儲空間管理假設(shè)初始化時系統(tǒng)已把專用塊讀入主存儲器L單元開始的區(qū)域中，分配和回收的算法如下：（1）分配一個空閑塊查L單元內(nèi)容（空閑塊數(shù)）：查L單元內(nèi)容（空閑塊數(shù)）：當空閑塊數(shù)>1，i:＝L＋空閑塊數(shù)；從i單元得到一空閑塊號；把該塊分配給申請者；空閑塊數(shù)減1當空閑塊數(shù)＝1，取出L＋1單元內(nèi)容（一組的第一塊塊號或0）；<112

>文件存儲空間管理（2）歸還一塊查L單元的空閑塊數(shù)；當空閑塊數(shù)<100，空閑塊數(shù)加1；j:＝L＋空閑塊數(shù)；歸還塊號填入j單元當空閑塊數(shù)＝100，把主存中登記的信息寫入歸還塊中；把歸還塊號填入L＋1單元；將L單元置成1背景-5：翻尾石魚PART6.5實現(xiàn)文件系統(tǒng)的表目<114

>實現(xiàn)文件系統(tǒng)的表目系統(tǒng)打開文件表系統(tǒng)打開文件表專門用于保存已打開文件的文件控制塊，通常放在內(nèi)存除了保存已打開文件的文件控制塊之外，在該表格中還保存了共享計數(shù)、修改標志等信息，如下圖所示。其中，由于允許多個進程同時打開同一個文件，所以共享計數(shù)標出有幾個進程打開同一個文件；修改標志是指文件控制塊或i節(jié)點的內(nèi)容是否被修改過，如果修改過，則關(guān)閉文件時要將文件控制塊寫回磁盤系統(tǒng)打開文件表<115

>實現(xiàn)文件系統(tǒng)的表目用戶打開文件表每個進程都有一個“用戶打開文件表”以UNIX為例，該表的內(nèi)容有文件描述符、打開方式、讀寫指針、系統(tǒng)打開文件表入口等等另外在進程的進程控制塊PCB中，還記錄了“用戶打開文件表”的位置用戶打開文件表<116

>實現(xiàn)文件系統(tǒng)的表目在系統(tǒng)打開文件表和用戶打開文件表之間存在一種關(guān)系實際上，用戶打開文件表指向了系統(tǒng)打開文件表如果多個進程共享同一個文件，則一定有多個用戶打開文件表目對應(yīng)著系統(tǒng)打開文件表的同一入口

打開文件表之間關(guān)系背景-1：北京大學(xué)西門PART6.6文件及文件目錄的操作<118

>文件及文件目錄的操作典型的文件操作1.建立文件用戶首先調(diào)用文件系統(tǒng)的“建立文件”操作，在請求調(diào)用該操作時，提供所要創(chuàng)建的文件的文件名及若干參數(shù)：用戶名、文件名、存取方式、存儲設(shè)備類型、記錄格式、記錄長度，等等系統(tǒng)依據(jù)用戶提供的文件名及若干參數(shù)，為這一新創(chuàng)建的文件分配一個文件控制塊，填寫文件控制塊中的有關(guān)項建立文件的實質(zhì)是建立文件的文件控制塊FCB，并建立必要的存儲空間，分配空的FCB從而建立起系統(tǒng)與文件的聯(lián)系建立文件系統(tǒng)調(diào)用的一般格式為：create（文件名，訪問權(quán)限，（最大長度））建立文件的具體步驟如下：（1）檢查參數(shù)的合法性；（2）檢查同一目錄下有無重名文件；（3）在目錄中有無空閑位置；

（4）填寫目錄項內(nèi)容；（5）返回<119

>文件及文件目錄的操作2.打開文件打開文件，是使用文件的第一步，任何一個文件使用前都要先打開，即把文件控制塊FCB送到內(nèi)存打開文件系統(tǒng)調(diào)用的一般格式為：fd=open（文件路徑名，打開方式）打開文件時，系統(tǒng)主要完成以下工作：（1）根據(jù)文件路徑名查目錄，找到FCB主部（2）根據(jù)打開方式、共享說明和用戶身份檢查訪問合法性（3）根據(jù)文件號查系統(tǒng)打開文件表，看文件是否已被打開（4）在用戶打開文件表中取一空表項，填寫打開方式等，并指向系統(tǒng)打開文件表對應(yīng)表項3.讀文件讀文件系統(tǒng)調(diào)用的一般格式為：read（文件名，（文件內(nèi)位置），要讀的長度，內(nèi)存目的地址），讀寫方式可為讀、寫和既讀又寫等<120

>文件及文件目錄的操作讀文件時，系統(tǒng)主要完成以下工作：（1）檢查長度是否為正整數(shù)（2）根據(jù)文件名查找目錄，確定該文件在目錄中的位置（3）根據(jù)隱含參數(shù)中的文件主和目錄中該文件的存儲權(quán)限數(shù)據(jù)，檢查是否有權(quán)讀：（4）由文件內(nèi)位置與要讀的長度計算最末位置，將其與目錄中的文件長度比較，超過否？（5）根據(jù)參數(shù)中的位置、長度和目錄中的映射信息，確定物理塊號、需要讀出的塊數(shù)等讀盤參數(shù)（6）根據(jù)下一塊號讀塊至內(nèi)存緩沖區(qū)（7）取出要讀的內(nèi)容，也許要進行成組的分解，將取出的內(nèi)容送至參數(shù)中的內(nèi)存目的地址（8）根據(jù)塊內(nèi)長度或起始塊號+塊數(shù)，確定還讀下一塊嗎？同時確定下一塊塊（9）正常返回（10）錯誤返回，返回相應(yīng)錯誤號<121

>文件及文件目錄的操作4.寫文件寫文件系統(tǒng)調(diào)用的一般格式為：write（文件名，記錄鍵，內(nèi)存位置）把內(nèi)存中指定單元的數(shù)據(jù)作為指定的一個記錄寫入指定文件中，系統(tǒng)還將為其分配物理塊，以便把記錄信息寫到外存上5.關(guān)閉文件若文件