第四章存儲(chǔ)管理

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

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

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

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

缺點(diǎn)：碎片問(wèn)題，主存利用率很低。

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

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

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

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

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

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

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

BC

D

E

F圖示29第六章存儲(chǔ)管理缺點(diǎn)：對(duì)用戶不透明，增加了用戶負(fù)擔(dān)。

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

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

把一個(gè)進(jìn)程的邏輯地址空間分成若干大小相等的片，每個(gè)片稱為頁(yè)面或頁(yè)

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

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

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

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

L比較P>=L

b+頁(yè)號(hào)p

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

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

b+頁(yè)號(hào)p

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

2k=211

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

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

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

Cl

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

Cl

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

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

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

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

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

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

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

23215245325223315555555522333333222222444444

xxxxx

x

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

23215245325223315244335222315224435231552243

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

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

23215245325223215