第四章存儲管理

在早期的操作系統(tǒng)中，主存分配廣泛采用連續(xù)分配方式。連續(xù)分配方式——為一個用戶程序分配一個連續(xù)的主存空間。4.2連續(xù)存儲空間管理1第六章存儲管理一、單一連續(xù)分配（單個分區(qū)）最簡單的存儲管理方式，用于多道程序設(shè)計技術(shù)之前。內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)由操作系統(tǒng)使用。用戶區(qū)作為一個連續(xù)的分區(qū)分配給一個作業(yè)。評價優(yōu)點：方法簡單，易于實現(xiàn)缺點：1.僅適用于單道程序，只能用于單用戶單任務(wù)的操作系統(tǒng)

2.系統(tǒng)資源利用率低系統(tǒng)區(qū)用戶區(qū)2第六章存儲管理分區(qū)存儲管理是滿足多道程序設(shè)計的最簡單的一種存儲管理方法，它允許多個用戶程序同時存在系統(tǒng)內(nèi)存中，即共享內(nèi)存空間。按分區(qū)劃分方式可分為固定分區(qū)和可變分區(qū)。 3第六章存儲管理二、

固定分區(qū)存儲管理1.基本思想把內(nèi)存的用戶區(qū)預(yù)先劃分成多個分區(qū)，每個分區(qū)大小可以相同，也可以不同。（分區(qū)的劃分由計算機的操作員或者由操作系統(tǒng)給出，并給出主存分配表）

分區(qū)個數(shù)固定，分區(qū)的大小固定。一個分區(qū)中可裝入一個作業(yè)，作業(yè)執(zhí)行過程中不會改變存放區(qū)域。早期的IBM的OS/MFT（具有固定任務(wù)數(shù)的多道程序系統(tǒng)）采用了這種固定分區(qū)的方法。4第六章存儲管理2.主存分配表為了說明各分區(qū)的分配和使用情況，需設(shè)置“主存分配表”，記錄各分區(qū)及其使用情況。主存分配表內(nèi)容：分區(qū)號，分區(qū)的起始地址，長度，占用標志。3.主存空間分配主存存分配程序檢索主存分配表，從中找到還未分配且大小滿足要求的分區(qū)，則將此分區(qū)分配給該作業(yè)。若沒找到滿足條件的分區(qū)，則拒絕為該作業(yè)分配主存。5第六章存儲管理例：某系統(tǒng)的內(nèi)存容量為256K，操作系統(tǒng)占用低地址的20K，其余空間劃分成4個固定大小的分區(qū)。如下圖分區(qū)號起始地址(KB)長度(KB)占用標志1208A22832C36064Ｂ4124132０主存分配表6第六章存儲管理４.固定分區(qū)性能分析在作業(yè)大小和出現(xiàn)頻率均已知的情況下，固定分區(qū)是合適的。在這種情況下分區(qū)的大小選擇與作業(yè)大小相當，這樣內(nèi)存的使用效率較高。但是若作業(yè)的大小和出現(xiàn)的頻率不知道時，勢必造成分區(qū)的大小和作業(yè)的大小相差甚遠，這樣就會造成存儲空間的浪費，從而影響整個系統(tǒng)的效率。

缺點：碎片問題，主存利用率很低。

7第六章存儲管理三、可變分區(qū)存儲管理（動態(tài)分區(qū)）1.基本思想內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運行的過程中建立分區(qū).當作業(yè)裝入主存時，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個分區(qū)給該作業(yè)；否則令該作業(yè)等待.分區(qū)長度不固定,分區(qū)個數(shù)不固定.這種存儲管理的方法克服了固定分區(qū)嚴重浪費主存的問題，提高了主存資源的利用率。ＩＢＭ操作系統(tǒng)ＯＳ／ＭＶＴ采用可變分區(qū)存儲管理。8第六章存儲管理

當有作業(yè)完成后釋放所占用的存儲區(qū)。在系統(tǒng)運行的過程中，系統(tǒng)中形成多個空閑的不連續(xù)的存儲區(qū)，稱空閑區(qū)。9第六章存儲管理2.實現(xiàn)動態(tài)分區(qū)需要的數(shù)據(jù)結(jié)構(gòu)在動態(tài)分區(qū)存儲管理中，要有相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來登記空閑區(qū)信息，它包括空閑區(qū)的大小和位置。不同系統(tǒng)根據(jù)設(shè)計要求采用不同的結(jié)構(gòu)。常用的有表結(jié)構(gòu)和鏈結(jié)構(gòu)。系統(tǒng)還要設(shè)置了等待分區(qū)隊列，當系統(tǒng)中無空閑區(qū)或無滿足要求的空閑區(qū)時，則把申請者送入等待隊列中，等待別的進程釋放內(nèi)存之后再喚醒隊列中的進程。10第六章存儲管理例:11第六章存儲管理3.分區(qū)分配算法空閑區(qū)表（鏈）中的空閑區(qū)可按一定規(guī)則排列，例如按空閑區(qū)大小的升序（降序）排列；按空閑區(qū)地址升序（降序）組織。根據(jù)空閑區(qū)表（鏈）排列方法不同，對應(yīng)不同的分配算法，常用的可變分區(qū)分配算法有最先適應(yīng)算法，下次適應(yīng)分配算法，最優(yōu)適應(yīng)算法、最壞適應(yīng)算法等。12第六章存儲管理(1)最先適應(yīng)算法空閑區(qū)按地址從小到大的次序排列。分配：當進程申請大小為SIZE的內(nèi)存時，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到容量滿足要求（≥SIZE）的空閑區(qū)為止。從該空閑區(qū)中劃出大小為SIZE的分區(qū)分配給進程，余下的部分仍作為一個空閑區(qū)，但要修改其首址和大小。優(yōu)點：這種算法是盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址部分的大空閑區(qū)，有利于大作業(yè)的裝入。缺點:主存低地址和高地址分區(qū)利用不均衡。在低地址部分,集中了許多非常小的空閑區(qū)(碎片),降低了主存的利用率。13第六章存儲管理（２）下次適應(yīng)分配算法最先適應(yīng)算法的變種?？偸菑目臻e區(qū)上次掃描結(jié)束處順序查找空閑區(qū)表（鏈），直到找到第一個滿足容量要求的空閑區(qū)為止，分割一部分給作業(yè)，剩余部分仍作為空閑區(qū)。14第六章存儲管理(３)最優(yōu)適應(yīng)算法空閑區(qū)按容量遞增的次序排列。分配：當進程申請存儲空間，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到第一個滿足容量要求的空閑區(qū)為止。采用最優(yōu)適應(yīng)算法選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)。15第六章存儲管理優(yōu)點：選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。缺點：空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。隨著時間的推移，系統(tǒng)中的小空閑區(qū)會越來越多，從而造成存儲空間的浪費。16第六章存儲管理(４)最壞適應(yīng)算法要求空閑區(qū)按容量遞減的順序排列。分配：進程申請存儲區(qū)時，檢查空閑區(qū)表（鏈）的第一個空閑區(qū)的大小是否滿足要求，若不滿足則令進程等待；若滿足則從該空閑區(qū)中分配一部分存儲區(qū)給用戶，剩下的部分仍作為空閑區(qū)。為了克服最佳適應(yīng)算法把空閑區(qū)切割得太小的缺點，人們提出了一種最壞適應(yīng)算法，即每次分配時，總是將最大的空閑區(qū)切去一部分分配給請求者，剩余的部分仍是一個較大的空閑區(qū)。避免了空閑區(qū)越分越小的問題。17第六章存儲管理分析:當程序裝入內(nèi)存中最大的空閑區(qū)后，剩下的空閑區(qū)還可能相當大，還能裝下較大的程序。另一方面每次僅作一次查詢工作，查找效率高。18第六章存儲管理例：某時刻系統(tǒng)中有三個空閑區(qū),有一作業(yè)大小25k。大小起始位置30k48k28k138k45k210k首次適應(yīng)算法：最優(yōu)適應(yīng)算法：最壞適應(yīng)算法：19第六章存儲管理4.可變分區(qū)的回收當某個進程釋放某存儲區(qū)時，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中去，否則把釋放區(qū)作為一個空閑區(qū)插入到空閑區(qū)表的適當位置。釋放區(qū)與空閑區(qū)相鄰的四種情況釋放區(qū)與前空閑區(qū)相鄰釋放區(qū)與后空閑區(qū)相鄰釋放區(qū)與前后兩個空閑區(qū)相鄰釋放區(qū)不與任何空閑區(qū)相鄰20第六章存儲管理(a)釋放區(qū)與前空閑區(qū)相鄰：將釋放區(qū)與前空閑區(qū)合并為一個空閑區(qū)。其首址仍為前空閑區(qū)首址，大小為釋放區(qū)大小與空閑區(qū)大小之和。(b)釋放區(qū)與后空閑區(qū)相鄰：則把釋放區(qū)合并到后空閑，首地址為釋放區(qū)首地址，大小為二者大小之和。(c)釋放區(qū)與前后兩個空閑區(qū)相鄰：將這三個區(qū)合為一個空閑區(qū)，其首址為前空閑區(qū)首址，大小為這三個區(qū)大小之和，并取消原后空閑區(qū)表目。(c)釋放區(qū)不與任何空閑區(qū)相鄰：將釋放區(qū)作為一個空閑區(qū)，將其大小和首址插入到空閑區(qū)表的適當位置。21第六章存儲管理可變分區(qū)存儲管理分析優(yōu)點:1.有助于多道程序設(shè)計2.不需過多硬件,僅需界地址寄存器用于存儲保護3.所采用的算法都比較簡單,易于實現(xiàn)缺點:1.碎片問題由于空閑區(qū)的大小與申請內(nèi)存的大小相等的情況是很少的，絕大多數(shù)情況是從一個空閑區(qū)中切去一塊，剩下的部分作為一個空閑區(qū)仍留在空閑區(qū)表中，隨著時間的推移，空閑區(qū)的發(fā)展趨勢是越來越小，直至不能滿足任何用戶要求。這種不能被任何用戶使用的極小的空閑區(qū)稱為碎片。碎片的出現(xiàn)造成了存儲空間的浪費。2.分區(qū)大小受主存容量限制,無法擴充主存容量22第六章存儲管理四、可重定位分區(qū)存儲管理解決碎片問題的一種簡單方法是采用可重定位分區(qū)分配.1.基本思想例:內(nèi)存中現(xiàn)有3個空閑區(qū)，如圖所示，現(xiàn)有一作業(yè)到達，要求獲得30k內(nèi)存空間，沒有分區(qū)滿足容量要求，若想把作業(yè)裝入，可將內(nèi)存中所有作業(yè)進行移動，這樣把原來分散的空閑區(qū)匯集成一個大的空閑區(qū)。操作系統(tǒng)作業(yè)1空閑區(qū)(15k)作業(yè)2空閑區(qū)(15k)作業(yè)3空閑區(qū)(20k)操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)（50k）操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)(20k)作業(yè)423第六章存儲管理

將內(nèi)存中的作業(yè)進行移動,使它們連接在一起,把原來分散的多個小分區(qū)拼接成一個大的空閑區(qū).這個過程稱為”緊湊”或”移動”.

需解決的問題:每次”緊湊”后,程序或數(shù)據(jù)裝入的物理地址變化,采用動態(tài)重定位.24第六章存儲管理2.動態(tài)重定位分區(qū)分配算法與動態(tài)分區(qū)分配算法基本相同,差別在找不到足夠大的空閑分區(qū)時進行”緊湊”.

25第六章存儲管理分區(qū)分配方案評價優(yōu)點:1.實現(xiàn)了主存共享,有助于多道程序設(shè)計,提高了系統(tǒng)資源的利用率;

主存利用率:可重定位分區(qū)分配>動態(tài)分區(qū)分配>固定分區(qū)分配2.與后面所介紹的存儲管理方式相比,實現(xiàn)分區(qū)分配所使用的表格,占用的存儲空間較少,算法也相對簡單;3.實現(xiàn)存儲保護的措施也較簡單。缺點:1.主存仍不能充分利用,除了可重定位分區(qū)法外,都存在碎片問題.2.采用”緊湊”方法,雖解決了碎片問題,但系統(tǒng)開銷太大.3.不能實現(xiàn)對主存的擴充.因此作業(yè)大小受到主存可用空間限制.26第六章存儲管理五、覆蓋技術(shù)與對換技術(shù)1.為什么引入？在多道環(huán)境下擴充內(nèi)存的方法，用以解決在較小的存儲空間中運行較大程序時遇到的矛盾。覆蓋技術(shù)主要用在早期的操作系統(tǒng)中。對換技術(shù)被廣泛用于小型分時系統(tǒng)中，交換技術(shù)的發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn)。27第六章存儲管理2.覆蓋技術(shù)把程序劃分為若干個功能上相對獨立的程序段，按照其自身的邏輯結(jié)構(gòu)將那些不會同時執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域程序段先保存在磁盤上，當有關(guān)程序段的前一部分執(zhí)行結(jié)束，把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段（內(nèi)存“擴大”了）覆蓋：一個作業(yè)的若干程序段，或幾個作業(yè)的某些部分共享某一個存儲空間一般要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)，程序員要向系統(tǒng)指明覆蓋結(jié)構(gòu)，然后由由操作系統(tǒng)完成自動覆蓋28第六章存儲管理A8KE4KF10KC10KB8KD12K作業(yè)X的調(diào)用結(jié)構(gòu)作業(yè)X的常駐區(qū)

A（8K）覆蓋區(qū)0（10K）覆蓋區(qū)1（12K）

BC

D

E

F圖示29第六章存儲管理缺點：對用戶不透明，增加了用戶負擔。

例子：目前這一技術(shù)用于小型系統(tǒng)中的系統(tǒng)程序的內(nèi)存管理上，MS-DOS的啟動過程中，多次使用覆蓋技術(shù)；啟動之后，用戶程序區(qū)TPA的高端部分與COMMAND.COM暫駐模塊也是一種覆蓋結(jié)構(gòu)?，F(xiàn)代操作系統(tǒng)極少使用覆蓋技術(shù)。分析30第六章存儲管理3.對換技術(shù)為平衡系統(tǒng)負載，通過選擇一個進程，把其暫時移出到磁盤，騰出空間給其他進程使用，同時把磁盤中的某個進程再換進主存，讓其投入運行，這種互換稱對換。多用于分時系統(tǒng)中31第六章存儲管理選擇原則（即：將哪個進程換出內(nèi)存？）時間片輪轉(zhuǎn)法或基于優(yōu)先數(shù)的調(diào)度算法，通常把時間片耗盡或優(yōu)先級較低的進程換出，因為短時間內(nèi)它們不會被投入運行。對換時機（即：何時需發(fā)生對換）批處理系統(tǒng)中，當有進程要求動態(tài)擴充主存且得不到滿足時可觸發(fā)對換；分時系統(tǒng)中，對換可與調(diào)度結(jié)合在一起，每個時間片結(jié)束或執(zhí)行I/O操作時實施。

32第六章存儲管理分析與覆蓋技術(shù)相比，交換技術(shù)不要求用戶給出程序段之間的邏輯覆蓋結(jié)構(gòu)；交換發(fā)生在進程或作業(yè)之間，而覆蓋發(fā)生在同一進程或作業(yè)內(nèi)。覆蓋只能覆蓋那些與覆蓋段無關(guān)的程序段。33第六章存儲管理上節(jié)所介紹的連續(xù)分配方式，會出現(xiàn)碎片問題，雖然采用“緊湊”的方法將許多碎片拼接成可用的大塊空間，但須為之付出很大開銷，而無實用價值。如果允許將一個進程直接分散地裝入到許多不相鄰的分區(qū)中，則無須再進行“緊湊”?；谶@一思想而產(chǎn)生了離散分配方式。離散分配方式：給進程分配幾個不連續(xù)的內(nèi)存區(qū)域，并可保證進程的正確執(zhí)行。離散分配方式按分配基本單位不同分為分頁存儲管理和分段存儲管理。34第六章存儲管理4.3分頁存儲管理分頁技術(shù)是由曼徹斯特大學(xué)提出，并于1960年前后在Atlas計算機上實現(xiàn)。這種技術(shù)對操作系統(tǒng)的發(fā)展產(chǎn)生了深遠影響。35第六章存儲管理一、基本原理1.頁面

把一個進程的邏輯地址空間分成若干大小相等的片，每個片稱為頁面或頁

。從0開始編制頁號。 頁面的大小應(yīng)選擇適中，一般頁的大小為2的冪，通常為512B～8KB。2.邏輯地址分頁存儲管理邏輯地址分為兩部分：地址的高位部分為頁號，低位部分為頁內(nèi)位移。頁號頁內(nèi)位移例：邏輯地址32位，頁大小4k，則頁內(nèi)位移占12位，頁號占20位。頁號頁內(nèi)位移31.….1211……..……….036第六章存儲管理3.物理塊（頁框）把主存的物理地址空間分成和頁面大小相等的區(qū)，每個區(qū)稱為物理塊或頁框。從0開始編制塊號。4.物理地址5.分頁存儲管理基本原理

以頁為單位進行分配。當一個進程裝入內(nèi)存時，將進程的多個頁面分別裝入內(nèi)存的多個物理塊中，這些物理塊可以是不相鄰的。塊號塊內(nèi)位移37第六章存儲管理例：頁面大小1k進程2（3k）進程1（1.8k）01012內(nèi)存012

34567...38第六章存儲管理6.頁表進程的各個頁面分散存放在主存不相鄰的物理塊中，系統(tǒng)如何知道頁面和物理塊的對應(yīng)關(guān)系。這就需要系統(tǒng)為每個進程建立一個頁表，用來登記頁號和塊的對應(yīng)關(guān)系和有關(guān)信息。一個進程有多少個頁面，頁表就有多少項。進程的頁表大多駐留在內(nèi)存中，頁表在主存的首地址和長度存放在該進程的進程控制塊。39第六章存儲管理例：頁面大小1k0115進程2（3k）進程1（1.8k）01012內(nèi)存012

34567...進程1頁表頁號塊號頁號塊號進程2頁表03142740第六章存儲管理二、地址轉(zhuǎn)換把程序的邏輯地址轉(zhuǎn)換成內(nèi)存的物理地址。1.分析：程序邏輯地址：內(nèi)存物理地址：頁號頁內(nèi)位移塊號塊內(nèi)位移頁表41第六章存儲管理進程的頁表放在內(nèi)存中，頁表在主存的首地址和頁表長度保存在本進程的PCB中。系統(tǒng)設(shè)置了一個頁表寄存器，當系統(tǒng)調(diào)度一個進程運行前，系統(tǒng)把該進程的頁表首地址和頁表長度送入到該頁表寄存器中，以便地址轉(zhuǎn)換時使用。42第六章存儲管理2.地址轉(zhuǎn)換過程：p’頁表地址越界中斷

L比較P>=L

b+頁號p

頁內(nèi)地址d塊號P’塊內(nèi)地址d物理地址頁表首址寄存器頁表長度寄存器邏輯地址P*表項長度p43第六章存儲管理三、快表和相聯(lián)存儲器在頁式存儲技術(shù)中，我們可看到每次存取數(shù)據(jù)，就要做兩次訪問內(nèi)存的工作，一次是地址轉(zhuǎn)換查頁表時要作一次訪問內(nèi)存的工作，然后是根據(jù)轉(zhuǎn)換后的物理地址訪問內(nèi)存存取數(shù)據(jù)，這樣存取速度降低一倍，將會影響整個系統(tǒng)的使用效率?？梢?，以此高昂代價來換取存儲器空間利用率的提高，是得不償失的。44第六章存儲管理為了提高提高地址變換速度，通常都設(shè)置一個專用的高速存儲器，用來存放頁表的一部分，這種高速存儲器稱為相聯(lián)存儲器（associativememory），存放在相聯(lián)存儲器中的頁表稱快表。相聯(lián)存儲器的存取時間是遠小于主存的，但造價高，故一般都是小容量的，只能存放幾十個頁表項。在采用了快表的系統(tǒng)中，通常采用“雙管齊下“的方針，一方面檢索相聯(lián)存儲器，而同時又檢索內(nèi)存的頁表，在相聯(lián)存儲器中一旦檢索到所要的塊號，便立即停止頁表的檢索，若相聯(lián)存儲器中找不到所要的塊號，就應(yīng)利用主存中頁表查找的到，并將此頁表項填入相聯(lián)存儲器中。根據(jù)程序執(zhí)行局部性的特點，所以快表的命中率可達90%以上。45第六章存儲管理p’頁表地址越界

L比較P>=Lpp’...快表

b+頁號p

頁內(nèi)地址dP’d物理地址頁表地址寄存器頁表長度寄存器邏輯地址46第六章存儲管理硬件能自動分離出頁號和頁內(nèi)地址，但我們只能通過計算才能得到。計算時要注意：(1)邏輯地址以十六進制、八進制、二進制的形式給出將邏輯地址轉(zhuǎn)換成二進制的數(shù)；按頁的大小分離出頁號和頁內(nèi)地址（低位部分是頁內(nèi)地址，高位部分是頁號）；根據(jù)題意產(chǎn)生頁表；將頁內(nèi)地址直接復(fù)制到物理地址的低位部分；以頁號查頁表，得到對應(yīng)頁裝入內(nèi)存的塊號，并將塊號轉(zhuǎn)換成二進制數(shù)填入地址的高位部分，從而形成內(nèi)存物理地址。47第六章存儲管理例1：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、A、5塊，試將邏輯地址0AFEH，1ADDH轉(zhuǎn)換成內(nèi)存地址。邏輯地址1ADDH=0001101011011101頁號P＝3頁內(nèi)地址d＝01011011101物理地址＝0010101011011101＝2ADDH邏輯地址0AFEH=0000101011111110B

2k=211

頁內(nèi)地址占低11位，高位為頁號頁號P＝1頁內(nèi)地址d＝01011111110查頁表知第一頁裝入到內(nèi)存第9塊中，9=1001B物理地址＝0100101011111110＝4AFEH48第六章存儲管理(2)邏輯地址以十進制數(shù)給出按下列公式計算出頁號和頁內(nèi)地址

頁號＝邏輯地址％頁大小頁內(nèi)地址＝邏輯地址mod頁大小根據(jù)題意產(chǎn)生頁表；以頁號查頁表，得到對應(yīng)頁裝入內(nèi)存的塊號內(nèi)存地址＝塊號×頁大小＋頁內(nèi)地址49第六章存儲管理例2：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。邏輯地址7145頁號P＝7145％2048＝3頁內(nèi)地址d＝7145mod2048＝1001查頁表知第3頁裝入內(nèi)存第5塊中物理地址=5*2048+1001=11241邏輯地址3412頁號P＝3412％2048＝1頁內(nèi)地址d＝3412mod2048＝1364查頁表知第1頁裝入內(nèi)存第9塊中物理地址=9*2048+1364=1979650第六章存儲管理位示圖記錄主存物理塊的使用情況四、分頁存儲空間的分配與回收0700111017……空閑塊數(shù)……110主存分配算法：計算一個進程所需要的總塊數(shù)N；查空閑塊數(shù)，看是否還有N個空閑塊，若沒有則令進程等待；如有足夠的空閑塊，則頁表長度設(shè)為N，可填入PCB中；申請頁表區(qū)，把頁表始址填入PCB查位示圖找出N個為“0”的位，計算對應(yīng)的物理塊號，將塊號填入頁表；修改位示圖（相應(yīng)位值占用標志，空閑塊數(shù)-N）；51第六章存儲管理主存回收算法進程執(zhí)行結(jié)束歸還主存時，根據(jù)歸還的物理塊號，計算出對應(yīng)位在位示圖中的位置，將占有標志清“0”，并將歸還的塊數(shù)加入空閑塊數(shù)中。52第六章存儲管理五、兩級頁表和多級頁表當頁表項很多時，僅采用一級頁表需要大片邊續(xù)空間，可將頁表也分頁,由此構(gòu)成二級頁表。具體做法：把整個頁表分成一張張小頁表,每個小頁表每個小頁表稱為頁表頁，大小與物理塊相同，對小頁表順序編號,允許小頁表分散存放在不連續(xù)的物理塊中,為了進行索引查找,應(yīng)該為這些小頁表建一張頁目錄表,其表項指出小頁表所在物理塊號及相關(guān)信息。于是系統(tǒng)要為每個進程建一張頁目錄表,它的每個表項對應(yīng)一個小頁表,而小頁表的每個表項給出了頁面和物理塊的對應(yīng)關(guān)系,頁目錄表是一級頁表,小頁表是二級頁表。53第六章存儲管理邏輯地址結(jié)構(gòu)有三部分組成：頁目錄位移、頁表頁位移和頁內(nèi)位移。塊號頁內(nèi)地址頁目錄位移頁表頁位移頁內(nèi)位移物理塊地址頁表頁地址進程一級頁表進程二級頁表物理地址邏輯地址頁目錄表控制寄存器二級頁表地址轉(zhuǎn)換過程54第六章存儲管理解決頁表頁占用主存空間的問題進程運行涉及頁面的頁表頁應(yīng)放在主存,其他頁表頁使用時再調(diào)入,在頁目錄表中增加特征位,指示對應(yīng)的頁表頁是否已調(diào)入主存,地址轉(zhuǎn)換機構(gòu)根據(jù)邏輯地址中的頁目錄位移,去查頁目錄表對應(yīng)表項,如未調(diào)入,應(yīng)產(chǎn)生一個”缺頁表頁”中斷信號，請求操作系統(tǒng)將頁表頁調(diào)入主存。55第六章存儲管理4.4分段存儲管理

為了解決碎片問題，提高內(nèi)存利用率引入了分頁存儲管理。引入分段存儲管理主要是滿足用戶（程序員）編程和使用上的要求。應(yīng)用程序通常是由若干程序段（模塊）組成，例如由主程序段、子程序段、數(shù)據(jù)段等組成，每段具有完整的邏輯意義。在分頁存儲管理中，頁面是信息的物理單位，與源程序不存在邏輯關(guān)系，也就難以實現(xiàn)以段為單位的共享、保護、動態(tài)鏈接等。56第六章存儲管理一、基本原理用戶程序劃分一個用戶程序往往由幾個程序段（主程序、子程序和函數(shù)等）所組成。把程序按自身的邏輯關(guān)系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段段內(nèi)也從0開始編址，段內(nèi)地址是連續(xù)的。(分段是由用戶或編譯器負責(zé)的）邏輯地址（注意：分段地址空間是真正二維的）段號段內(nèi)地址57第六章存儲管理...020k4工作區(qū)段[B]0主程序段[M]......0E40K1子程序段[X]0200K...CALL[X][E].........CALL[Y][F]CALL[A]116......0F50k2子程序段[Y]01165k3數(shù)組段[A]12345...例：58第六章存儲管理內(nèi)存分配以段為單位分配內(nèi)存，每一個段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機分割，需要多少分配多少），但各段之間可以不連續(xù)存放。例：B020kA05kY050kX040kM0200K01234進程.100k320k500k600k800k40k100k20k50k5k內(nèi)存操作系統(tǒng)59第六章存儲管理段表記錄了進程的每個邏輯段在內(nèi)存中的起始地址和段長。每個進程設(shè)置一個段表，進程分為多少段，段表就應(yīng)有幾項。段表放在內(nèi)存，段表在內(nèi)存首地址和段表長度存放在本進程的PCB中。上例：段表段號基址段長012100k320k40K100K50K600K5K800K20K500K3460第六章存儲管理二、地址變換段地址變換由硬件地址變換機構(gòu)完成，系統(tǒng)設(shè)置一對寄存器段表始址寄存器：用于保存正在運行進程的段表的始址段表長度寄存器：用于保存正在運行進程的段表的長度（例如上圖的段表長度為5，它與段長及擴充段表目中的存取控制字一起用于分段管理中的存取保護）61第六章存儲管理

Cl

Cb+段號S段內(nèi)地址d比較b+d段表S>=Cl物理地址段表始址寄存器段表長度寄存器邏輯地址段長l基址b地址越界d>=1分段地址轉(zhuǎn)換及存儲保護機制地址越界比較+段號*表項長度62第六章存儲管理快表同頁地址變換一樣，在段地址變換過程中，也有兩次訪問內(nèi)存的問題。為了加快訪問內(nèi)存的速度也可采用快速存儲器組成快表。

Cl

Cb+段號S段內(nèi)地址d比較比較b

+d段表S>=Cl快表物理地址段表始址寄存器段表長度寄存器邏輯地址Lb...SLb地址越界d>=Ld>=L地址越界比較63第六章存儲管理三、段的共享在分段系統(tǒng)中實現(xiàn)段共享，只需在每個進程的段表中為共享段設(shè)置一個段表項。64第六章存儲管理四、分段和分頁的比較分段是信息的邏輯單位，由源程序的邏輯結(jié)構(gòu)所決定，用戶可見，段長可根據(jù)用戶需要來規(guī)定，段起始地址可從任何主存地址開始。分段方式中，源程序(段號，段內(nèi)位移)經(jīng)連結(jié)裝配后地址仍保持二維結(jié)構(gòu)。分頁是信息的物理單位，與源程序的邏輯結(jié)構(gòu)無關(guān)，用戶不可見，頁長由系統(tǒng)確定，頁面只能以頁大小的整倍數(shù)地址開始。分頁方式中，源程序(頁號，頁內(nèi)位移)經(jīng)連結(jié)裝配后地址變成了一維結(jié)構(gòu)。65第六章存儲管理五、段頁式存儲管理方式分頁系統(tǒng)能解決碎片問題，提高內(nèi)存利用率；分段系統(tǒng)能很好滿足用戶的需求，便于實現(xiàn)段的共享，保護和動態(tài)鏈接。將兩者結(jié)合形成一種新的存儲管理方式。66第六章存儲管理一、段頁式存儲管理基本思想用戶程序劃分 先將用戶程序分成若干個段，再把每個段分成若干個頁。邏輯地址內(nèi)存劃分 按頁式存儲管理方案內(nèi)存分配 以頁為單位進行分配段號段內(nèi)頁號頁內(nèi)位移67第六章存儲管理68第六章存儲管理段表：記錄了每一段的頁表始址和頁表長度頁表：記錄了邏輯頁號與內(nèi)存塊號的對應(yīng)關(guān)系（每一段有一個，一個程序可能有多個頁表）二、地址轉(zhuǎn)換69第六章存儲管理4.5虛擬存儲管理前面介紹的各種存儲管理方式中，在裝入一個作業(yè)時要求將它全部裝入內(nèi)存，才可運行?？赡艹霈F(xiàn)兩種情況：（1）有些作業(yè)所需內(nèi)存空間已超出內(nèi)存總?cè)萘?。?）為提高系統(tǒng)資源效率，內(nèi)存中同時裝入多道作業(yè)，用戶作業(yè)所需空間超出了內(nèi)存空閑空間。如何解決？70第六章存儲管理1968年美國Denning提出程序局部性原理程序局部性原理程序在執(zhí)行時呈現(xiàn)出高度的局部性特征，即在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分；相應(yīng)地，它所訪問的存儲空間也局限于某個區(qū)域。時間局部性一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行,典型原因是程序中的循環(huán)?？臻g局部性若某一存儲單元被訪問，則在不久之后，與該存儲單元相鄰的單元也可能被訪問,典型原因是程序的順利執(zhí)行。71第六章存儲管理基于程序局部性原理，就沒有必要把一個作業(yè)一次性全部裝入內(nèi)存再開始運行。而是僅將當前使用部分裝入主存，其余部分存放在磁盤中，啟動程序運行，進程執(zhí)行過程中，若所訪問的程序和數(shù)據(jù)在主存時可順利執(zhí)行；若不在主存時，由系統(tǒng)自動將這部分信息從磁盤裝入主存（部分裝入），若裝入時沒有足夠空閑物理空間，便把主存中暫時不用的信息移至磁盤（部分替換）。這樣的計算機系統(tǒng)好像為用戶提供了一個存儲容量比實際主存大得多的存儲器，就稱為虛擬存儲器。72第六章存儲管理一、虛擬存儲器概念虛擬存儲器是為了邏輯擴充內(nèi)存，以解決小內(nèi)存無法運行大程序的問題而引入的，是一種以CPU時間和外存空間換取內(nèi)存空間的技術(shù)（是OS中的資源轉(zhuǎn)換技術(shù)），也是迄今為止邏輯擴充內(nèi)存程度最徹底的技術(shù)（遠強于覆蓋和交換技術(shù)）。虛擬存儲器是在1961年由英國曼徹斯特大學(xué)Fotheringham提出，并在該校的atlas機器上實現(xiàn)的一種存儲技術(shù)。從1970年后被廣泛應(yīng)用。73第六章存儲管理1.虛擬存儲器定義在具有層次結(jié)構(gòu)存儲器的計算機系統(tǒng)中，采用自動實現(xiàn)部分裝入和部分替換功能，為用戶提供一個比物理主存容量大得多的，可尋址的一種“主存儲器”。虛擬存儲器的容量受限于計算機的地址結(jié)構(gòu)和可用的磁盤容量，如Intelx的地址線是32位，則程序的可尋址范圍是4G，Windows和Linux都為應(yīng)用程序提供一個4G的邏輯主存。74第六章存儲管理2.虛擬存儲器實現(xiàn)方法

虛擬存儲器是建立在離散分配的內(nèi)存管理技術(shù)基礎(chǔ)上的，它主要有以下3種實現(xiàn)方法：請求分頁虛擬存儲管理用戶程序要裝入內(nèi)存時，僅裝入當前使用的頁面，啟動程序運行，在運行的過程中，若發(fā)現(xiàn)要訪問的頁面不在內(nèi)存，則由系統(tǒng)自動裝入所需頁面，若內(nèi)存空間已滿，則根據(jù)某種算法置換某個頁面，以便裝入新的頁面。請求分段虛擬存儲管理用戶程序要裝入內(nèi)存時，首先把當前需要的段裝入主存，啟動程序運行，在運行的過程中，若發(fā)現(xiàn)要訪問的段不在內(nèi)存，則由系統(tǒng)自動裝入所需段，若內(nèi)存空間已滿，則根據(jù)某種算法置換某段，以便裝入新的段。請求段頁式虛擬存儲管理請求分頁+請求分段75第六章存儲管理二、請求分頁虛擬存儲管理請求分頁系統(tǒng)必須解決以下幾個問題：（1）當程序要訪問的某頁不在內(nèi)存時，如何發(fā)現(xiàn)這種缺頁情況？發(fā)現(xiàn)后應(yīng)如何處理？（2）當需要把外存上的某個頁面調(diào)入內(nèi)存時，此時內(nèi)存中沒有空閑物理塊，應(yīng)置換哪些頁面，置換策略，置換算法。76第六章存儲管理1、頁表機制為了實現(xiàn)請求分頁技術(shù)，頁表應(yīng)增加相應(yīng)的內(nèi)容，反映該頁是否在內(nèi)存，在外存的位置，在內(nèi)存的時間的長短等。駐留位：指示該頁是否在內(nèi)存修改位：指示該頁調(diào)入內(nèi)存后是否修改訪問字段：記錄該頁被訪問的次數(shù)，或者最近已有多長時間未被訪問，共選擇換出頁面時參考。外存地址：指示該頁在外存上的地址。頁號物理塊號駐留位修改位訪問字段外存地址77第六章存儲管理2、缺頁中斷處理在地址轉(zhuǎn)換過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，準備將該頁調(diào)入內(nèi)存此時應(yīng)將缺頁的進程掛起（調(diào)頁完成喚醒）78第六章存儲管理指令執(zhí)行和缺頁中斷處理過程啟動一條指令硬件自動將邏輯地址分成頁號和頁內(nèi)地址該頁在內(nèi)存嗎？訪問存儲器完成此指令執(zhí)行下一條指令保護現(xiàn)場有空閑塊嗎？裝入所需頁面修改頁表和主存分配表選擇換出頁面調(diào)整頁表和主存分配表把該頁寫回外存該頁修改過嗎？是是是否否否硬件軟件缺頁中斷恢復(fù)現(xiàn)場79第六章存儲管理缺頁中斷同一般中斷的異同？相同點：保護現(xiàn)場中斷處理恢復(fù)現(xiàn)場不同點：缺頁中斷是在一條指令執(zhí)行期間產(chǎn)生和處理中斷，一般中斷是一條指令完成后CPU檢查是否有中斷；一條指令執(zhí)行時可能產(chǎn)生多次缺頁中斷。如指令可能訪問多個內(nèi)存地址，這些地址在不同的頁中。80第六章存儲管理3.頁面分配策略固定分配進程保持物理塊數(shù)固定不變,稱固定分配;進程創(chuàng)建時,根據(jù)進程類型和程序員的要求決定物理塊數(shù),只要有一個缺頁中斷產(chǎn)生,進程就會有一頁被替換?？勺兎峙溥M程分得的物理塊數(shù)可變,稱可變分配;進程執(zhí)行的某階段缺頁率較高,說明目前局部性較差，系統(tǒng)可多分些物理塊以降低缺頁率，反之說明進程目前的局部性較好,可減少分給進程的物理塊數(shù)。81第六章存儲管理4.頁面替換策略全局替換如果頁面替換算法的作用范圍是整個系統(tǒng)，稱全局頁面替換算法,它可以在運行進程間動態(tài)地分配頁框。局部替換如果頁面替換算法的作用范圍局限于本進程，稱為局部頁面替換算法,它實際上需要為每個進程分配固定的頁框。

82第六章存儲管理固定分配和局部替換策略配合使用進程分得的物理塊數(shù)不變，發(fā)生缺頁中斷，只能從進程的頁面中選頁替換，保證進程的物理塊總數(shù)不變。

策略難點：應(yīng)給每個進程分配多少物理塊?給少了,缺頁中斷率高;給多了,使主存中能同時執(zhí)行的進程數(shù)減少，進而造成處理器和其它設(shè)備空閑。

常用固定分配算法：①平均分配，②按比例分配,③優(yōu)先權(quán)分配。83第六章存儲管理可變分配和全局替換策略配合使用先每個進程分配一定數(shù)目物理塊,os保留若干空閑物理塊,進程發(fā)生缺頁中斷時，從系統(tǒng)空閑塊中選一個給進程,這樣產(chǎn)生缺頁中斷進程的主存空間會逐漸增大,有助于減少系統(tǒng)的缺頁中斷次數(shù)。系統(tǒng)擁有的空閑頁框耗盡時，會從主存中選擇一頁淘汰，該頁可以是主存中任一進程的頁面，這樣又會使那個進程的物理塊數(shù)減少，缺頁中斷率上升。84第六章存儲管理可變分配和局部替換配合使用實現(xiàn)要點:(1)新進程裝入主存時，根據(jù)應(yīng)用類型、程序要求，分配給一定數(shù)目物理塊。(2)產(chǎn)生缺頁中斷時,從該進程頁面中選一個頁面替換。(3)不時重新評價進程的缺頁率，增加或減少分配給進程的物理塊以改善系統(tǒng)性能。85第六章存儲管理5、頁面置換算法

——PageReplacementAlgorithms當要將一頁面并裝入入到全滿的內(nèi)存中時，必須把已在內(nèi)存中的某一頁置換掉。用來選擇置換哪一頁的規(guī)則叫做頁面置換算法。顛簸（抖動）現(xiàn)象在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面所需時間比進程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動。例如，一個每隔幾條指令就發(fā)生一次頁面故障的進程稱為在顛簸（因為一條指令的執(zhí)行只需幾納秒，而每從磁盤上讀入一個頁面則常需幾十毫秒）。系統(tǒng)發(fā)生顛簸的原因頁面置換算法不合理分配給進程的物理頁面數(shù)太少86第六章存儲管理（1）最佳頁面置換換算法（OPT算法）從內(nèi)存中置換出以后永不再使用的頁面；如無這樣的頁面，則選擇以后最長時間內(nèi)不需要訪問的頁。1966年Belady提出的理想算法，但無法實現(xiàn)，因為頁面訪問的順序是很難預(yù)知的。主要用于評價其他置換算法。87第六章存儲管理例：設(shè)某請求分頁系統(tǒng)采用固定分配局部置換策略，一進程的頁面走向為2，3，2，1，5，2，4，5，3，2，5，2，該進程分得3個物理塊，初始為空。OPT

23215245325223315555555522333333222222444444

xxxxx

x

缺頁次數(shù)=6次缺頁率=6/12=50%88第六章存儲管理（2）先進先出頁面置換算法（FIFO算法）置換駐留在內(nèi)存時間最長的頁面，即先進入內(nèi)存的頁面先被置換掉。理由是：最先進入內(nèi)存的頁面不再被訪問的可能性最大。實現(xiàn)簡單：只需把進程在內(nèi)存的頁面按先后次序鏈成1個隊列，并設(shè)置1個替換指針，使它總是指向內(nèi)存中最老的頁面。缺點：效率不高89第六章存儲管理上例：FIFO

23215245325223315244335222315224435231552243

xxxxxxxxx缺頁次數(shù)=9次缺頁率=9/12=75%90第六章存儲管理（3）最近最久未使用頁面置換算法

（LRU算法）選擇在最近一段時間最久未使用的頁面予以置換。根據(jù)程序局部性原理，那些剛被使用過的頁面，可能馬上還要被使用，而在較長時間里未被使用的頁面，可能不會馬上使用到。91第六章存儲管理上例：LRU

23215245325223215