第3章存儲系統(tǒng)及存儲管理5存儲器管理概述

3.5存儲管理存儲管理的功能地址重定位分區(qū)存儲管理頁式存儲管理虛擬存儲管理存儲器管理存儲器的層次高速緩沖存儲器（cache）內(nèi)存（主存）外存（輔存）主存分為：系統(tǒng)區(qū)用戶區(qū)存儲器管理要管理的區(qū)域存儲器管理的功能思考：要運行你編寫的JAVA語言程序，首先要把你的程序裝入內(nèi)存。如何為程序分配一片存儲空間？內(nèi)存的分配和回收地址變換內(nèi)存共享與保護(hù)虛擬存儲器地址重定位邏輯地址：用戶程序中以“0”開始的地址。物理地址：內(nèi)存中的地址。地址重地位：把邏輯地址轉(zhuǎn)換成物理地址的過程。地址重地位的方式：根據(jù)定位的時機(jī)不同，分為靜態(tài)地址重定位和動態(tài)地址重定位。靜態(tài)地址重定位在作業(yè)裝入內(nèi)存時，進(jìn)行的地址重定位。程序中的地址都是物理地址。優(yōu)點：簡單，無需增加硬件地址轉(zhuǎn)換機(jī)構(gòu)。缺點：一旦裝入，就不能在內(nèi)存中移動位置。用戶無法共享。動態(tài)地址重定位在程序執(zhí)行時進(jìn)行的地址重地位。硬件支持：重定位寄存器（基址寄存器）。程序中的地址是邏輯地址。物理地址=基址寄存器+邏輯地址例：基址寄存器的值為1000，LOADA，500則操作數(shù)的地址為：1500。loada,50023670500邏輯地址空間1000定位寄存器2367物理地址空間+動態(tài)地址重定位優(yōu)點：程序占用的內(nèi)存空間動態(tài)可變。容易實現(xiàn)內(nèi)存共享。缺點：需要硬件支持，增加成本。管理軟件比較復(fù)雜?，F(xiàn)代計算機(jī)中普遍采用動態(tài)重定位的定位方式。主要的內(nèi)存管理技術(shù)單道連續(xù)存儲管理分區(qū)存儲管理固定分區(qū)存儲管理可變分區(qū)存儲管理頁式存儲管理虛擬存儲管理單道連續(xù)存儲管理1、基本原理：內(nèi)存分為兩部分：用戶區(qū)和系統(tǒng)區(qū)。任何時刻，內(nèi)存中最多只有一個用戶作業(yè)。2、內(nèi)存分配算法：用戶請求是否小于用戶區(qū)？分配Y不能運行單道連續(xù)存儲管理3、存儲保護(hù)：保護(hù)系統(tǒng)程序不會遭用戶程序的破壞。措施：設(shè)置一個界限寄存器，存放當(dāng)前可供用戶使用的主存區(qū)域的起始地址。4、多用戶共享（分時系統(tǒng)）

對換（swapping）技術(shù)：讓多個用戶的作業(yè)輪流進(jìn)入主存儲器。

硬件支持：大容量高速輔助存儲器。5、地址重地位方式：靜態(tài)地址重地位。覆蓋技術(shù)如果作業(yè)邏輯地址空間>用戶區(qū)，怎么處理？原理：作業(yè)分段主段始終保留在內(nèi)存（駐留區(qū)）其它段保存在輔存中，輪流進(jìn)入主存誰來分段？用戶把如何分段和覆蓋情況寫成一個“覆蓋描述文件”分區(qū)存儲管理1、基本原理：將內(nèi)存劃分為若干個連續(xù)的存儲區(qū)域（稱為一個分區(qū)），每一個分區(qū)中可以（也只能）裝入一個作業(yè)。2、分區(qū)的種類：根據(jù)分區(qū)的時機(jī)不同，分為：固定分區(qū)和可變分區(qū)兩種。固定分區(qū)存儲管理1、基本原理：在作業(yè)加載內(nèi)存之前，將內(nèi)存劃分為若干個連續(xù)的區(qū)域。一旦劃分好后，主存儲器中的分區(qū)個數(shù)和大小就確定了，不能改變。各個分區(qū)的大小可以不同（長作業(yè)區(qū)和短作業(yè)區(qū)）。2、內(nèi)存分配與回收

問題：如何知道哪些分區(qū)已分配；各個分區(qū)的大小和位置？（1）分區(qū)說明表：記錄系統(tǒng)中所有分區(qū)的情況，結(jié)構(gòu)如下：固定分區(qū)存儲管理區(qū)號起始地址長度占用標(biāo)志

其中，“占用標(biāo)志”表示該分區(qū)是已分配還是空閑。（2）分配算法：從分區(qū)說明表中查找一個狀態(tài)是“空閑”、大小滿足作業(yè)要求的分區(qū)，并將狀態(tài)改為“已分配”。（3）回收算法：只需要將分區(qū)說明表中的“狀態(tài)”值改為“空閑”即可。用戶作業(yè)LP=0是否越界？N長度L？分配（狀態(tài)改為“已分配”）YP=P+1狀態(tài)為“空？”YNN無法分配Y固定分區(qū)存儲管理3、地址轉(zhuǎn)換：靜態(tài)重定位的方式。4、存儲保護(hù)：上下界地址法。處理器設(shè)置一對寄存器：上界寄存器和下界寄存器，作業(yè)地址應(yīng)滿足：

下限地址絕對地址上限地址否則，發(fā)生“地址越界”中斷事件。5、存在問題：內(nèi)存利用率很低。6、采用什么措施提高內(nèi)存利用率？提高內(nèi)存利用率的措施（1）按統(tǒng)計規(guī)律劃分分區(qū)。（2）按分區(qū)大小順序排列，低地址部分是較小的分區(qū)，在分區(qū)說明表中按從小到大順序登記。為作業(yè)分配滿足條件的最小的分區(qū)。（3）按作業(yè)對主存儲器的需求量排成多個隊列，每個作業(yè)隊列中的作業(yè)只能依次裝入一個分區(qū)中。可變分區(qū)存儲管理基本原理在作業(yè)要求裝入主存時，根據(jù)作業(yè)的大小從空閑內(nèi)存區(qū)中“切出”一片連續(xù)的區(qū)域．分區(qū)的大小和個數(shù)是不確定的．初始時，系統(tǒng)中只有一個連續(xù)的用戶區(qū)域，隨著作業(yè)的到達(dá)和撤消，用戶區(qū)就被劃分為若干個大小不等的區(qū)域。內(nèi)存OS作業(yè)A作業(yè)B作業(yè)C內(nèi)存分配與回收1、空閑區(qū)的管理（1）空閑分區(qū)表序號起始地址大小狀態(tài)

注意：這里的狀態(tài)是指該表目的狀態(tài)，其值表示該表目是空閑還是已使用。（2）空閑分區(qū)鏈空閑區(qū)大小；下一空閑區(qū)起始地址……分配算法（1）1、最先適配算法：空閑分區(qū)表按地址從小到大排列，從第一個開始，找到第一個滿足條件的分區(qū)，根據(jù)作業(yè)的大小切出一片連續(xù)的區(qū)域。作業(yè)請求LP=1是否越界？Y不能分配狀態(tài)為空閑？NP=P+1長度≥LNY長度=L狀態(tài)置為“空表目”YN起始地址=起始地址+L長度=長度-L分配算法（2）2、最優(yōu)適配算法原理：將空閑區(qū)按大小從小到大排列，將滿足需求的最小的空閑區(qū)分配給作業(yè)。基于：為了更好地滿足大作業(yè)的需求。但是：這樣切下的空閑區(qū)容易變成“碎片”。算法流程與最先適配法相同。分配算法（3）3、最壞適配算法從滿足需求的最大的空閑區(qū)中為作業(yè)分配空間?？臻e分區(qū)表按大小從大到小排列?；冢呵型旰蟮目臻e區(qū)仍能滿足某個作業(yè)的需求，減少碎片的數(shù)量。但對大作業(yè)不利。其流程為：用戶作業(yè)請求Ｌ取分區(qū)表的第一個表項長度≥ＬＹ起始地址＝起始地址＋Ｌ長度＝長度－Ｌ長度＝ＬＮＹ狀態(tài)置空表目不能分配N回收算法１、待回收區(qū)：其起始地址為Ａ，長度為Ｌ。２、上空閑區(qū)和下空閑區(qū)３、可能的四種情況：（１）上下都不空。（２）上空，下不空。（３）下空，上不空。（４）上下都為空。待回收區(qū)作業(yè)區(qū)作業(yè)區(qū)上下都不空待回收區(qū)作業(yè)區(qū)上空下不空在空閑分區(qū)表中找一個空表目，將其內(nèi)容填入。上空閑區(qū)：大?。酱笮。檀厥諈^(qū)作業(yè)區(qū)待回收區(qū)下空上不空下空閑區(qū)：起始地址=A大小=大小+L上下都為空上空閑區(qū)：長度=長度+L+下空閑區(qū)起址不變。注意如何判斷待回收區(qū)是否與空閑區(qū)相連？地址+長度=下一空閑區(qū)首地址空閑區(qū)的管理：為了便于空閑區(qū)的合并，采用鏈接結(jié)構(gòu)。按地址從小到大排序。第一塊和最后一塊的情況。可變分區(qū)存在的問題及解決辦法碎片問題：一些很小的內(nèi)存區(qū)域。移動技術(shù)將離散的碎片集合在一起。不是任何時候都可以移動。移動技術(shù)需要很大的系統(tǒng)開銷。保護(hù)問題界地址法：基址和長度寄存器。上機(jī)題目1、編寫可變分區(qū)存儲管理算法（最先適配法）2、編寫可變分區(qū)的內(nèi)存回收算法。分區(qū)存儲管理的缺點“碎片”問題原因：作業(yè)要求連續(xù)的存儲空間。解決辦法：允許作業(yè)占據(jù)不連續(xù)的空間。頁式存儲管理基本原理內(nèi)存分配地址變換內(nèi)存保護(hù)和內(nèi)存共享虛擬存儲器基本原理“等分”內(nèi)存。把內(nèi)存劃分為大小相同的“塊”。把用戶作業(yè)空間劃分為大小相同的“頁”。頁和塊的大小相同。在把作業(yè)加載到內(nèi)存時，頁和頁之間不再連續(xù)。但頁內(nèi)連續(xù)。也不必把所有的頁都一次性加載內(nèi)存，只需要加載那些馬上要用到的頁。其余的頁在需要時再加載。地址變換邏輯地址：頁號+頁內(nèi)地址如何轉(zhuǎn)變?yōu)閮?nèi)存物理地址？考慮：物理地址=塊號*塊長度+塊內(nèi)地址塊長度一定，塊內(nèi)地地址與頁內(nèi)地址相同。問題變?yōu)椋喝绾胃鶕?jù)頁號得到塊號？頁表：頁號頁內(nèi)地址頁表地址變換過程1、根據(jù)頁號查頁表，得到塊號。2、根據(jù)塊號和頁內(nèi)地址計算物理地址。3、例題：例題：在分頁存儲管理系統(tǒng)中，用戶編程空間共32個頁，每頁大小為1024B，內(nèi)存為16KB。假定某一時刻用戶頁表如下，若邏輯地址為035E（H），求其所對應(yīng)的物理地址。頁號物理塊號 0 5 1 10 2 3 3 7分析：（1）根據(jù)題意，頁內(nèi)地址為10位，頁號為5位。210=1024，25=32（2）根據(jù)給定的邏輯地址得到頁號和頁內(nèi)地址。035E（H）=（0000001101011110）2從左邊數(shù)10位為頁內(nèi)地址，剩余為頁號。頁號為0。（3）根據(jù)頁號查頁表，得到塊號為5。（4）將塊號與塊內(nèi)地址組合為物理地址：01011101011110=175E（H） 頁表的實現(xiàn)—快表從上述地址變換過程可以看出：CPU每取一條指令或數(shù)據(jù)，都必須經(jīng)過頁表。因此，頁表的每一個表項都是一個動態(tài)重定位機(jī)構(gòu)。如何實現(xiàn)頁表，將影響系統(tǒng)的效率。方式：硬件實現(xiàn)：用寄存器組。但代價太高，特別是內(nèi)存很大時，是不可能的。軟件實現(xiàn)：將頁表放在內(nèi)存中。每取一條指令，要兩次訪問內(nèi)存?？毂碥浻布Y(jié)合：將頁表中使用最頻繁的表項（頁表的的一個子集）放在cache中。稱為“快表”。cache也稱為“聯(lián)想寄存器”，它不是根據(jù)地址而是根據(jù)所存信息的全部特征或部分特征進(jìn)行存取。在這里為頁號。若要訪問的頁在cache中，則只需一次訪問內(nèi)存。若不在，則到內(nèi)存中去找，同時把新的頁表表項寫入cache。例題：對于利用快表且頁表存于內(nèi)存的分頁系統(tǒng)，假定CPU的一次訪問內(nèi)存時間為1μs，訪問快表時間忽略不計。如果85%的地址映射可直接通過快表完成，那么進(jìn)程完成一次內(nèi)存讀寫的平均有效時間是多少？分析：（1）若直接通過快表完成，則只需一次訪問內(nèi)存。（2）若不能，則需要兩次訪問內(nèi)存。（3）平均時間=1*85%+2*15%內(nèi)存分配用戶需求：需要多少塊？內(nèi)存空閑塊的管理：位示圖。位示圖：在內(nèi)存中劃出一片區(qū)域，用一位代表一個塊，該位的值表示所代表的塊的狀態(tài)：0：空閑；1：已分配。內(nèi)存分配塊號與字號、字長的關(guān)系：系統(tǒng)的字長一定，內(nèi)存塊從0開始編號，則有：塊號=字號*字長+位號字號=[塊號/字長]（取整的意思）位號=塊號MOD字長用戶作業(yè)請求：塊數(shù)B掃描位示圖，查找為0的位空閑塊數(shù)BN無法分配計算塊號建立頁表例題（1）一個32位計算機(jī)系統(tǒng)有主存128M和輔助存儲器10G，這個系統(tǒng)的虛擬空間是多少？（2）頁式虛擬存儲管理采用位示圖技術(shù)，設(shè)主存有16384塊，采用32位的512個字作為位示圖。若塊號、字號和位號（從高位到低位）分別從1、0、0開始。試計算：5998塊對應(yīng)的字號和位號；198字的20位對應(yīng)于哪一塊？頁式系統(tǒng)的內(nèi)存保護(hù)和共享保護(hù)：在頁表上添加一個保護(hù)位。在做地址變換時，檢查對頁面的訪問是否合法。共享：根據(jù)地址轉(zhuǎn)換過程可知：如果在不同用戶的頁表中填上相同的頁表表項（塊號），就能夠訪問相同的內(nèi)存空間。塊號保護(hù)位5R12WR555用戶1用戶2用戶355虛擬存儲技術(shù)基本原理實現(xiàn)過程頁面替換頁式虛擬存儲技術(shù)虛擬存儲器：內(nèi)存擴(kuò)充技術(shù)，為用戶提供一個比實際內(nèi)存大得多的內(nèi)存空間。虛擬存儲的理論依據(jù):局部性原理。頁式虛擬的基本原理：加載作業(yè)時，只加載那些最活躍的頁，其余的頁需要時再加載?！罢埱笳{(diào)頁技術(shù)”和“預(yù)調(diào)頁技術(shù)”。實現(xiàn)虛擬的三個三個條件程序中的哪些頁已經(jīng)加載內(nèi)存。當(dāng)要訪問的頁不在內(nèi)存時，如何將其調(diào)入內(nèi)存？若此時內(nèi)存空間已滿，如何選擇換出的頁？一、如何知道哪些已在內(nèi)存在頁表中添加一個標(biāo)志位（中斷位），標(biāo)志該頁是否已在內(nèi)存：0：不在1：在內(nèi)存塊號保護(hù)位標(biāo)志位二、當(dāng)要訪問的頁不在內(nèi)存時發(fā)生“缺頁中斷”。缺頁中斷的處理過程：保存現(xiàn)場在內(nèi)存中找到一個空閑塊。從磁盤上找到要調(diào)入的頁。讀磁盤到內(nèi)存。恢復(fù)現(xiàn)場。重新調(diào)度運行。三、在調(diào)入內(nèi)存時，若內(nèi)存已滿進(jìn)行“頁面替換”：從內(nèi)存中選擇一個頁調(diào)出內(nèi)存，為新調(diào)入的頁讓出空間。問題：選擇哪一個頁換出？如果替換的不合適，則發(fā)生“抖動”或“顛簸”現(xiàn)象：頁在內(nèi)外存之間頻繁地調(diào)入調(diào)出，系統(tǒng)開銷很大。換出換入頁面替換算法先進(jìn)先出法（FIFO）：將最先調(diào)入內(nèi)存的頁調(diào)出內(nèi)存。最近最少使用算法（LRU：leastrecentlyused）。將最近一段時間內(nèi)沒有用過的頁調(diào)出內(nèi)存。頁面替換算法最近最少使用算法（LFU）：最近一段時間內(nèi)使用次數(shù)最少的頁調(diào)出內(nèi)存。為每一個在內(nèi)存的頁設(shè)置一個計數(shù)器，選擇計數(shù)器中的值最小的調(diào)出。最優(yōu)算法（OPT）：把將來一段時間內(nèi)被使用的可能性最小的頁調(diào)出內(nèi)存。利用預(yù)測方法先來預(yù)測將來的使用情況。注意：LRU、LFU之間的區(qū)別。例題：有一個分頁式虛擬存儲管理系統(tǒng)，每個進(jìn)程在內(nèi)存有3頁數(shù)據(jù)區(qū)、1頁程序區(qū)，剛開始時數(shù)據(jù)區(qū)為空?，F(xiàn)有一個進(jìn)程有以下訪問序列：1，5，4，1，2，3，2，1，5，4，2，4，3，5，1若系統(tǒng)采用：（1）最近最少使用（LRU）淘汰算法（2）先進(jìn)先出（FIFO）淘汰算法請計算缺頁次數(shù)和發(fā)生缺頁中斷后的淘汰頁號。分析：（1）采用FIFO方法：將內(nèi)存中的頁按進(jìn)入的先后次序排隊，后來的加入隊尾，先來的先出去。（1）FIFO算法訪問隊列：154123215424351

154423315422351內(nèi)存155422315442351154423155423缺頁中斷頁面替換154231543答案：缺頁中斷的次數(shù)為12次，頁面替換的次序是：154231543。（2）LRU算法：訪問隊列：154123215424351

154423335422351內(nèi)存155122215442351141112155443缺頁中斷頁面替換54321524答案：缺頁中斷的次數(shù)為11次，頁面替換的次序是：5432152441.某系統(tǒng)采用頁式存儲管理，運行一個共有九頁的作業(yè)，依次訪問的頁面的次序為123782141231526393526，若前五頁已裝入主存且維持五個頁在主存工作，試問分別用FIFO和LRU調(diào)度算法時，完成該作業(yè)會產(chǎn)生的缺頁中斷次數(shù)和淘汰頁面的次序?答案：（1）FIFO：中斷次數(shù)為7次，淘汰頁面的次序為1237851（2）LRU：中斷次數(shù)為5次，淘汰頁面的次序為37841綜合應(yīng)用題

FIFO算法12378214

1231526393526缺頁替換888888412335566999997777777841223355666663333333784112233555552222222378441122333331111111237884511222221237851

√√√√√√√LRU算法123782141231526393526缺頁替換8888884443355669999977777771112211223333333333332221133556666622222228884422112222211111117778844335555537841

√√√√√工作集模型虛擬存儲技術(shù)的理論基礎(chǔ)。局部性原理：進(jìn)程往往會不均勻地高度局部化地訪問內(nèi)存。

時間局部性：剛剛被訪問的頁，很可能在不久的將來還要訪問。例如：循環(huán)；子程序；棧；用戶記數(shù)和總計的變量等。

空間局部性：某個頁面被訪問，很可能它相臨的頁也要被訪問。例如：數(shù)組遍歷；代碼程序的執(zhí)行；等等。工作集：進(jìn)程活躍地訪問的頁面的集合。工作集模型（續(xù)）工作集存儲管理策略力求把活躍程序的工作集保存在內(nèi)存中。從上圖可以看出：僅當(dāng)一個進(jìn)程的全部工作集都在內(nèi)存時才能運行該作業(yè)。hW(h)h0頁式存儲管理的缺陷從理論上講，不同用戶共享程序段或數(shù)據(jù)很簡單，只需在不同用戶的頁表中填上相同的塊號，經(jīng)地址變換后，一定能訪問相同的內(nèi)存空間。但是，由于頁的劃分是由系統(tǒng)自動進(jìn)行的，很可能用戶要共享的頁分布在不同的頁中，給共享和保護(hù)造成了麻煩。多級頁表原理：程序執(zhí)行的局部性。沒有必要把整個頁表都存放在內(nèi)存中。頁內(nèi)地址頁號II頁號IWindows2000采用的二級頁表見教材P109圖4-244.8UNIX系統(tǒng)的虛擬存儲管理UNIX的虛擬地址三個區(qū)段：系統(tǒng)區(qū)段、程序區(qū)段、控制區(qū)段系統(tǒng)區(qū)段：常駐內(nèi)存控制區(qū)段：用戶棧、核心棧、user區(qū)P110圖4-25UNIX虛擬地址結(jié)構(gòu)UNIX的頁表結(jié)