第六章主存管理

研究三方面的問(wèn)題：

取（fetch）

放（placement）

替換（replacement）請(qǐng)調(diào)、預(yù)調(diào)連續(xù)、非連續(xù)第六章存儲(chǔ)器管理第六章存儲(chǔ)器管理6.1主存管理功能6.2程序的裝入和鏈接6.3連續(xù)分配主存管理方式6.4覆蓋和對(duì)換技術(shù)6.5分頁(yè)存儲(chǔ)器管理方式6.6分段存儲(chǔ)管理方式6.7段頁(yè)式存儲(chǔ)管理方式主存分配地址轉(zhuǎn)換和重定位存儲(chǔ)保護(hù)和主存共享存儲(chǔ)擴(kuò)充（虛擬存儲(chǔ)技術(shù)）6.1主存管理功能6.2程序的裝入和鏈接

1.程序的裝入絕對(duì)裝入方式靜態(tài)重定位裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式源程序目標(biāo)模塊裝入模塊編譯鏈接裝入內(nèi)存圖示如下：JUMP1424LOAD22241024142422240LOAD1，250036510002500500010000LOAD1,125003651100012500015000絕對(duì)裝入方式靜態(tài)重定位裝入方式JUMP1424LOAD2224102414242224靜態(tài)重定位裝入：在裝入一個(gè)作業(yè)時(shí)，把作業(yè)中的指令地址和數(shù)據(jù)地址全部轉(zhuǎn)換成絕對(duì)地址。這種轉(zhuǎn)換工作是在作業(yè)開(kāi)始前集中完成的，在作業(yè)執(zhí)行過(guò)程中無(wú)需再進(jìn)行地址轉(zhuǎn)換。所以稱(chēng)為“靜態(tài)重定位”。（1）靜態(tài)鏈接2.程序的鏈接

程序的連接方式有三種：靜態(tài)鏈接、裝入時(shí)動(dòng)態(tài)鏈接和運(yùn)行時(shí)鏈接。CallB模塊B模塊C0L-10M-10N-1JSR“L”模塊B模塊C0L-1LL+M-1L+ML+M+N-1鏈接目標(biāo)模塊裝入模塊如：CALLB

JSR”L”需要解決的問(wèn)題：相對(duì)地址的修改；外部調(diào)用符號(hào)的變換（2）裝入時(shí)動(dòng)態(tài)鏈接

目標(biāo)模塊在裝入內(nèi)存的過(guò)程中鏈接，即邊裝入邊鏈接。優(yōu)點(diǎn)：便于修改和更新便于實(shí)現(xiàn)目標(biāo)模塊的共享6.2程序的裝入和鏈接（3）運(yùn)行時(shí)動(dòng)態(tài)鏈接將某些目標(biāo)模塊的鏈接延遲到運(yùn)行該模塊時(shí)才進(jìn)行。即采用部分裝入運(yùn)行方式。優(yōu)點(diǎn)：節(jié)省內(nèi)存空間便于實(shí)現(xiàn)目標(biāo)模塊的共享連續(xù)分配方式是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。分為：?jiǎn)我贿B續(xù)分配、固定分區(qū)分配、動(dòng)態(tài)分區(qū)分配和動(dòng)態(tài)重定位分區(qū)分配四種方式。1.單一（單道）連續(xù)分配方式主存系統(tǒng)區(qū)用戶區(qū)6.3連續(xù)分配主存管理方式內(nèi)存空間安排特點(diǎn)：任一時(shí)刻內(nèi)存只有一道作業(yè)，該作業(yè)連續(xù)存放于內(nèi)存中。只適合單用戶、單任務(wù)環(huán)境。操作系統(tǒng)用戶程序0aa+1n界地址寄存器6.3連續(xù)分配的主存管理方式界地址寄存器主存A>a?cputruefalse地址A終止程序運(yùn)行越界檢查機(jī)構(gòu)：用戶程序每訪問(wèn)一次主存，越界檢查機(jī)構(gòu)將訪問(wèn)的地址與界地址寄存器中的值比較。若越界，則終止其執(zhí)行。（1）分區(qū)劃分方法分區(qū)大小相等分區(qū)大小不相等2.（多道）固定分區(qū)分配管理方式分區(qū)號(hào)大小始地址狀態(tài)11530已分配23065未分配3100125已分配（2）分配方法

數(shù)據(jù)結(jié)構(gòu)：存儲(chǔ)分塊表MBT（如下表）特點(diǎn)：分區(qū)數(shù)和分區(qū)大小固定。優(yōu)點(diǎn)：簡(jiǎn)單、易實(shí)現(xiàn)。缺點(diǎn)：存在內(nèi)部碎片，主存利用率不高。上下界寄存器和地址檢查機(jī)構(gòu)。當(dāng)作業(yè)被調(diào)度運(yùn)行時(shí)，作業(yè)在內(nèi)存中的上下界地址寄存器限定的地址范圍內(nèi)。每次內(nèi)存訪問(wèn)時(shí)，地址檢查機(jī)構(gòu)作越界檢查。作業(yè)程序是絕對(duì)地址或靜態(tài)重定位裝入。CPU主存下界寄存器上界寄存器><TrueTrue地址AF F程序性中斷（3）地址訪問(wèn)保護(hù)有兩種方式：基址寄存器、長(zhǎng)度寄存器和動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)。當(dāng)作業(yè)被調(diào)度運(yùn)行時(shí)，將作業(yè)所占內(nèi)存基址及長(zhǎng)度送基址、長(zhǎng)度寄存器，每次內(nèi)存訪問(wèn)時(shí)，先看訪問(wèn)地址是否小于長(zhǎng)度，然后+基址進(jìn)行訪存。用戶程序代碼是可動(dòng)態(tài)浮動(dòng)的。CPU主存基地址寄存器長(zhǎng)度寄存器<+True地址AF 程序性中斷所謂程序浮動(dòng)是指程序可以隨機(jī)地從主存的一個(gè)區(qū)域移動(dòng)到另一個(gè)區(qū)域，程序被移動(dòng)后仍不影響它的執(zhí)行。若作業(yè)執(zhí)行時(shí)，被改變的有效區(qū)域依然能正確執(zhí)行，則稱(chēng)程序是可浮動(dòng)的。（4）存儲(chǔ)碎片

OS12k4k3K內(nèi)部碎片OS4k6k12k作業(yè)長(zhǎng)度：5K、8K、12K外部碎片內(nèi)部碎片：存在于一個(gè)存儲(chǔ)分區(qū)內(nèi)，當(dāng)內(nèi)存某存儲(chǔ)區(qū)大于其存放作業(yè)空間而剩下的那部分存儲(chǔ)空間。

外部碎片：通常指一個(gè)暫時(shí)不能使用的存儲(chǔ)分區(qū)。當(dāng)內(nèi)存某存儲(chǔ)分區(qū)容不下要運(yùn)行的作業(yè)時(shí)發(fā)生。3.可變分區(qū)多道管理技術(shù)（1）概念主存事先并未劃分成一個(gè)個(gè)分區(qū)，當(dāng)作業(yè)進(jìn)入主存時(shí)，按作業(yè)的實(shí)際大小建立和分配分區(qū)。（2）特點(diǎn)分區(qū)數(shù)可變分區(qū)大小不固定可能存在大小不等的外部碎片例：假設(shè)任一時(shí)間段內(nèi)，內(nèi)存中每一作業(yè)的運(yùn)行時(shí)間相等。作業(yè)到來(lái)次序所需存儲(chǔ)量運(yùn)行時(shí)間160102100533020470855015OS040256J1J2J3J4J53.可變分區(qū)多道管理技術(shù)（3）數(shù)據(jù)結(jié)構(gòu)常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種：存儲(chǔ)分塊表空閑分區(qū)表或空閑分區(qū)鏈3.可變分區(qū)多道管理技術(shù)分區(qū)號(hào)大小始地址115K30K1040K253K3100K125K………空閑分區(qū)表分區(qū)號(hào)大小始地址514K30K924K65K642K100K………已使用分區(qū)表存儲(chǔ)分塊表（表的維護(hù)較困難，存在表格碎片）已使用分區(qū)表UBT（分區(qū)狀態(tài)為忙）空閑分區(qū)表FBT（分區(qū)狀態(tài)為可用）06K28k8K4k20K28k4k18k頭指針8KB20KB6KB18k已分配未分配空閑分區(qū)鏈（單向鏈）指向下一個(gè)分區(qū)的指針?lè)謪^(qū)大小空閑分區(qū)鏈（雙向鏈）前向指針后向指針N+2N+2N個(gè)可用字節(jié)表示分區(qū)的大小00表示分區(qū)的狀態(tài)1）首次適應(yīng)算法以空閑分區(qū)鏈為例，每次從鏈?zhǔn)组_(kāi)始順序查找，直到找到一個(gè)大小能滿足要求的空閑分區(qū)為止。（一般要求空閑分區(qū)鏈以某種順序鏈接，如地址遞增。）通常有三種分配算法：（4）存儲(chǔ)分配算法缺點(diǎn)：低地址端留下許多很小的、難以利用的空閑分區(qū)。運(yùn)行一段時(shí)間后，使得查找的開(kāi)銷(xiāo)增加。優(yōu)點(diǎn)：內(nèi)存的高地址端保留了較大的空間。首次適應(yīng)算法的內(nèi)存分配過(guò)程從空閑分區(qū)表的開(kāi)始或空閑分區(qū)鏈的鏈?zhǔn)撞檎摇Ｖ每臻e分區(qū)號(hào)F=1空閑分區(qū)表（鏈）檢索完？F.size≥Xk?F.size-Xk≤size?F=F+1

從分區(qū)中劃出Xk大小的分區(qū)

修改空閑分區(qū)表和已使用分區(qū)表返回失敗返回noyes

將分區(qū)分配給請(qǐng)求的進(jìn)程yesnoyesnosize為事先規(guī)定不再劃分的剩余分區(qū)的大小。當(dāng)前進(jìn)程申請(qǐng)一Xk大小的內(nèi)存分區(qū)2）循環(huán)首次適應(yīng)算法

設(shè)置查找指針，每次分配內(nèi)存時(shí)，從查找指針開(kāi)始查找空閑分區(qū)表或空閑分區(qū)鏈。優(yōu)點(diǎn)：內(nèi)存的空閑分區(qū)利用均勻（4）存儲(chǔ)分配算法3）最佳適應(yīng)算法

將滿足需求的最小空閑分區(qū)分配給請(qǐng)求內(nèi)存分配的進(jìn)程。（一般要求空閑分區(qū)按由小到大的順序排列）缺點(diǎn)：將在內(nèi)存中留下許多碎片(內(nèi)部碎片)。4）最壞適應(yīng)算法在所有未分配的分區(qū)中挑選最大的，且滿足作業(yè)主存要求的分區(qū)分配給當(dāng)前作業(yè)。（4）存儲(chǔ)分配算法優(yōu)點(diǎn)：能使分配后的剩余分區(qū)足夠大，內(nèi)部碎片減少缺點(diǎn)：運(yùn)行一段時(shí)間后，難以找到用戶程序需要的較大空閑分區(qū)。（5）基本操作主要的操作有：分配內(nèi)存和回收內(nèi)存。

1）分配內(nèi)存選擇一種分配算法將滿足條件的內(nèi)存分區(qū)分配給當(dāng)前申請(qǐng)的進(jìn)程。2）內(nèi)存回收待回收的分區(qū)可能存在的情況有以下四種：回收區(qū)不與任何空閑分區(qū)鄰（如圖（1））回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)相鄰（如圖（2））回收區(qū)與插入點(diǎn)的后一分區(qū)相鄰（如圖（3））回收區(qū)與插入點(diǎn)的前、后兩個(gè)分區(qū)同時(shí)相鄰（如圖（4））F1R作業(yè)作業(yè)R作業(yè)作業(yè)RF2F1RF2圖（1）圖（2）圖（3）圖（4）回收過(guò)程的流程圖：申請(qǐng)回收分區(qū)RSIZE=R的大小LOC=R的始址置R的狀態(tài)為空表目R與F2相鄰？R與F1相鄰？在空閑分區(qū)表中找一空表目該分區(qū)的大小=SIZE始址=LOC狀態(tài)=可用SIZE=SIZE+F2的大小R與F1相鄰？置F2的狀態(tài)為空表目F1的大小=F1的大小+SIZEF2的大小=SIZEF2的始址=LOC返回yesnoyesnonoyes（1）緊湊

通過(guò)移動(dòng)的方法，把內(nèi)存中分散的各個(gè)小的存儲(chǔ)分區(qū)拼湊成大存儲(chǔ)區(qū)的過(guò)程。4.動(dòng)態(tài)重定位的可變分區(qū)分配OS用戶程序A用戶程序B用戶程序C用戶程序DOS用戶程序A用戶程序B用戶程序C用戶程序D緊湊緊湊后需要對(duì)移動(dòng)了的數(shù)據(jù)和程序進(jìn)行重定位。重定位：邏輯地址到物理地址的變換過(guò)程。（1）基本概念物理地址/絕對(duì)地址:指令或數(shù)據(jù)的主存地址。4.動(dòng)態(tài)重定位的可變分區(qū)分配邏輯地址：指目標(biāo)程序所限定地址集合中的地址。邏輯地址是相對(duì)于某個(gè)基準(zhǔn)量（通常為零）編址時(shí)所使用的地址，因此，也稱(chēng)相對(duì)地址。相對(duì)地址空間：是指相對(duì)地址的全體。也稱(chēng)邏輯地址空間或用戶地址空間。0LOAD1，250036510002500500010000LOAD1,125003651100012500015000靜態(tài)重定位：在裝入一個(gè)作業(yè)時(shí)，由裝入鏈接程序在程序執(zhí)行前進(jìn)行的重定位，即把作業(yè)中的指令地址和數(shù)據(jù)地址全部轉(zhuǎn)換成絕對(duì)地址。靜態(tài)重定位是由重定位裝配程序完成，一般不支持程序浮動(dòng)。

4.動(dòng)態(tài)重定位的可變分區(qū)分配動(dòng)態(tài)重定位：在裝入一個(gè)作業(yè)時(shí)，不進(jìn)行地址轉(zhuǎn)換，而是直接把作業(yè)直接裝入到分配的主存區(qū)域中。在作業(yè)指令執(zhí)行時(shí)，由硬件地址轉(zhuǎn)換機(jī)構(gòu)將指令或數(shù)據(jù)的地址轉(zhuǎn)換成絕對(duì)地址。地址變換是在程序執(zhí)行期間，隨著對(duì)每條指令或數(shù)據(jù)的訪問(wèn)而進(jìn)行。動(dòng)態(tài)重定位的特點(diǎn)：動(dòng)態(tài)重定位由硬件機(jī)構(gòu)完成，硬件機(jī)構(gòu)包括重定位寄存器和加法器。在程序執(zhí)行的過(guò)程中進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換。目標(biāo)程序可以在內(nèi)存中移動(dòng)且可以不連續(xù)。0LOAD1，250036510002500500010000LOAD1，12500365110001250015000重定位寄存器100002500+相對(duì)地址（絕對(duì)地址或物理地址）地址空間（相對(duì)地址或邏輯地址）（2）動(dòng)態(tài)重定位的過(guò)程如下：重定位硬件（3）動(dòng)態(tài)重定位分區(qū)分配算法

請(qǐng)求分配u.size分區(qū)檢查空閑分區(qū)表（鏈）找到≥u.size的空閑分區(qū)？按動(dòng)態(tài)分區(qū)方式進(jìn)行分配修改相關(guān)數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號(hào)和始址空閑分區(qū)總和≥u.size？進(jìn)行緊湊修改相關(guān)數(shù)據(jù)結(jié)構(gòu)失敗返回是否是否

6.4覆蓋和對(duì)換技術(shù)因內(nèi)存空間小于作業(yè)的程序空間而引入覆蓋。將主存的用戶空間劃分成一個(gè)固定區(qū)和多個(gè)覆蓋區(qū)。主程序放固定區(qū)依次調(diào)用的子程序則放在同一個(gè)覆蓋區(qū)操作系統(tǒng)提供覆蓋系統(tǒng)調(diào)用函數(shù)，在轉(zhuǎn)子程序前調(diào)用1.覆蓋技術(shù)覆蓋（overlap）A(4k)E(10k)D(6k)C(4k)B(6k)F(8k)操作系統(tǒng)固定區(qū)(4k)覆蓋區(qū)(6k)覆蓋區(qū)(10k)覆蓋技術(shù)是早期擴(kuò)大內(nèi)存容量的一種技術(shù)，并在單道連續(xù)存儲(chǔ)管理中使用。覆蓋順序和結(jié)構(gòu)由程序員規(guī)定?；舅枷耄簩⑻幱诘却隣顟B(tài)(等I/O)的進(jìn)程或暫時(shí)不用的程序或數(shù)據(jù)從主存換出到輔存的對(duì)換區(qū)，把將要執(zhí)行的進(jìn)程移入主存。2.對(duì)換（交換）技術(shù)為了支持交換，必須在系統(tǒng)空間設(shè)立I/O緩沖區(qū)。6.4覆蓋和對(duì)換技術(shù)2.對(duì)換技術(shù)（1）對(duì)換的形式進(jìn)程對(duì)換：即整體對(duì)換，以進(jìn)程為對(duì)換單位，目標(biāo)是提高主存的利用率。部分對(duì)換：包括頁(yè)面對(duì)換和分段對(duì)換，目的是支持虛擬存儲(chǔ)器系統(tǒng)。文件區(qū)：管理的目標(biāo)是提高文件存儲(chǔ)空間的利用率。對(duì)換區(qū)：采用動(dòng)態(tài)分區(qū)分配的管理方式，目的是提高交換速度。外存（2）對(duì)換空間的管理1）目標(biāo)：提高換進(jìn)、換出的速度。2）數(shù)據(jù)結(jié)構(gòu)：對(duì)換區(qū)的空閑分區(qū)表（或鏈），每個(gè)表項(xiàng)應(yīng)包括分區(qū)的首址和大小。（即開(kāi)始盤(pán)塊號(hào)和盤(pán)塊數(shù)）3）對(duì)換區(qū)的分配和回收對(duì)換區(qū)的分配一般采用連續(xù)分配方式，與動(dòng)態(tài)分區(qū)的內(nèi)存分配與回收基本相同。2.對(duì)換技術(shù)（3）進(jìn)程的換進(jìn)與換出1）進(jìn)程的換進(jìn)從交換區(qū)中尋找處于“就緒”狀態(tài)且換出時(shí)間最長(zhǎng)的進(jìn)程換進(jìn)。申請(qǐng)內(nèi)存空間執(zhí)行換入操作成功2.對(duì)換技術(shù)2）進(jìn)程的換出選擇處于阻塞或掛起狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程換出。（注：正在被共享的程序段或數(shù)據(jù)不能換出）申請(qǐng)對(duì)換區(qū)空間執(zhí)行換出操作成功2.對(duì)換技術(shù)注意：對(duì)換技術(shù)沒(méi)有從邏輯上擴(kuò)充主存空間給用戶使用（即不提供虛擬地址空間）??！6.5基本分頁(yè)存儲(chǔ)管理方式（不支持頁(yè)面對(duì)換功能）1.基本概念頁(yè)：將進(jìn)程的邏輯地址空間分成若干大小相等的片，這樣的片稱(chēng)為頁(yè)面，頁(yè)面從0開(kāi)始連續(xù)編號(hào)，如0，1，2，……物理塊：將內(nèi)存地址空間分成與頁(yè)面大小相同的存儲(chǔ)塊，稱(chēng)之為物理塊或頁(yè)框，物理塊或頁(yè)框也從0開(kāi)始連續(xù)編號(hào)，也稱(chēng)頁(yè)幀。有效地址：也稱(chēng)“虛擬地址”或“相對(duì)地址”，有效地址用一數(shù)對(duì)(p,d)表示，結(jié)構(gòu)如下：回收：當(dāng)進(jìn)程結(jié)束時(shí)，系統(tǒng)回收它的所有物理頁(yè)幀入空閑隊(duì)列。分配：初始時(shí)，所有頁(yè)幀都在空閑隊(duì)列中，當(dāng)用戶進(jìn)程被創(chuàng)建時(shí)，系統(tǒng)按需要量從空閑隊(duì)列獲得相應(yīng)數(shù)量的頁(yè)幀。2.動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)

因分頁(yè)存儲(chǔ)器管理方式中邏輯地址與物理地址之間失去自然聯(lián)系，故要通過(guò)頁(yè)表，并由硬件動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)將邏輯地址映射成物理地址才能正確訪存。6.5基本分頁(yè)存儲(chǔ)管理方式（不支持頁(yè)面對(duì)換功能）頁(yè)表：放在系統(tǒng)空間的頁(yè)表區(qū)，存儲(chǔ)邏輯頁(yè)與物理頁(yè)幀之間的對(duì)應(yīng)關(guān)系。PCB表中有一指針指向頁(yè)表，即每一進(jìn)程擁有一張頁(yè)表。18530498765432103210邏輯空間物理空間頁(yè)表頁(yè)號(hào)有效地址結(jié)構(gòu)：6.5基本分頁(yè)存儲(chǔ)管理方式

邏輯地址=p(頁(yè)號(hào))*頁(yè)面大小+d(頁(yè)內(nèi)位移)

物理地址=f(頁(yè)幀號(hào)))*頁(yè)面大小+d(同上)p=線性邏輯地址/頁(yè)面大??；

d=線性邏輯地址-p*頁(yè)面大小。例如：頁(yè)面的大小為1KB，求邏輯地址4101的頁(yè)號(hào)和頁(yè)內(nèi)位移。15141312111098665432100001000000000101得到頁(yè)號(hào)p=4，頁(yè)內(nèi)位移d=56.5基本分頁(yè)存儲(chǔ)管理方式為了減少頁(yè)號(hào)和頁(yè)內(nèi)位移的計(jì)算時(shí)間，一般規(guī)定頁(yè)面的大小為2的冪（與機(jī)器內(nèi)部的二進(jìn)制數(shù)的表示一致），且頁(yè)長(zhǎng)在29~212之間，這樣可以根據(jù)頁(yè)面的長(zhǎng)度方便地計(jì)算出頁(yè)號(hào)和頁(yè)內(nèi)位移（獲取p和d的除、乘法通過(guò)移位就能實(shí)現(xiàn)）。頁(yè)號(hào)和頁(yè)內(nèi)位移在機(jī)器指令的地址中各占幾位取決于頁(yè)的大小。頁(yè)號(hào)和頁(yè)內(nèi)位移的分割由硬件完成。（1）基本地址變換機(jī)構(gòu)3.地址變換頁(yè)表始址頁(yè)表長(zhǎng)度p（3）d88d≤越界中斷有效地址物理地址+0123頁(yè)表寄存器頁(yè)表頁(yè)表寄存器PTR：存放頁(yè)表在內(nèi)存的首地址和頁(yè)表的長(zhǎng)度。頁(yè)表一般常駐內(nèi)存問(wèn)題：CPU在這樣的地址變換機(jī)構(gòu)存取一個(gè)數(shù)據(jù)時(shí)，需要訪問(wèn)內(nèi)存幾次？快表：由一組高速緩沖寄存器組成，用來(lái)存放當(dāng)前訪問(wèn)過(guò)的頁(yè)表項(xiàng)，以減少地址轉(zhuǎn)換過(guò)程中的時(shí)間花費(fèi)。快表的表目結(jié)構(gòu)：系統(tǒng)中快表的表目一般有64~256個(gè)，快表的訪問(wèn)速度比普通主存要高出一個(gè)數(shù)量級(jí)，以并行的方式查找快表中的各表目。

（2）帶有快表的地址變換機(jī)構(gòu)頁(yè)號(hào)物理塊號(hào)進(jìn)程號(hào)訪問(wèn)權(quán)限如何用快表實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換？帶有快表的地址轉(zhuǎn)換過(guò)程(聯(lián)想存儲(chǔ)器可以看成是頁(yè)表的cache)PdN k-1 0fdn k-1 0P2f2P1f1......Pf......Pmfmf頁(yè)表始地+頁(yè)表聯(lián)想存儲(chǔ)器帶有快表的地址變換過(guò)程如下：CPU給出有效地址P是否在快表？讀出物理塊號(hào)查找頁(yè)表將新頁(yè)號(hào)寫(xiě)入快表（若快表已滿需要進(jìn)行置換）Pd讀出物理塊號(hào)P是否越界？否是否越界中斷是物理寄存器在進(jìn)程被調(diào)度占用cpu時(shí)，將進(jìn)程頁(yè)表始址裝入頁(yè)表地址寄存器。命中率：選用8-12項(xiàng)組成的聯(lián)想存儲(chǔ)器，并采用適當(dāng)?shù)奶鎿Q策略，在聯(lián)想存儲(chǔ)器中匹配成功的可能性可達(dá)80-90%。等效訪問(wèn)時(shí)間：設(shè)訪存時(shí)間為750ns，搜索聯(lián)想存儲(chǔ)器的時(shí)間為50ns，命中率為80%，則（這里假設(shè)先查聯(lián)想存儲(chǔ)器再查頁(yè)表）：

80%*（750+50）+20%*（750+50+750）

=950ns（2）帶有快表的地址變換機(jī)構(gòu)4.可用空間管理可用bitmap數(shù)組或空閑頁(yè)幀鏈來(lái)管理可用頁(yè)幀。6.5基本分頁(yè)存儲(chǔ)管理方式5.共享與保護(hù)

通過(guò)頁(yè)表可以使幾個(gè)邏輯空間指向同一個(gè)物理空間，實(shí)現(xiàn)程序共享。

例：EDIT1EDIT2EDIT3DATA1EDIT1EDIT2EDIT3DATA2EDIT1EDIT2EDIT3DATA3OSDATA1EDIT101234567891011EDIT2EDIT3DATA2DATA3P1 P2 P33461346734610頁(yè)表存儲(chǔ)保護(hù)越界保護(hù)：設(shè)置頁(yè)表長(zhǎng)度寄存器，查頁(yè)表前，先檢查頁(yè)號(hào)是否越界。操作訪問(wèn)保護(hù)：在每個(gè)頁(yè)表項(xiàng)中增設(shè)一存儲(chǔ)保護(hù)域，用于說(shuō)明對(duì)該頁(yè)的訪問(wèn)權(quán)限，每一個(gè)對(duì)該頁(yè)存儲(chǔ)的訪問(wèn)都首先要比照是否滿足該頁(yè)訪問(wèn)權(quán)限的說(shuō)明，滿足則訪問(wèn)，否則報(bào)錯(cuò)。例：設(shè)為每一頁(yè)表項(xiàng)增加三位，R位表示讀權(quán)限，W位表示寫(xiě)權(quán)限，E位表示執(zhí)行權(quán)限。

R W E 0 0 0不可進(jìn)行任何操作

0 0 1可以執(zhí)行,不可以讀寫(xiě)

0 1 0只可以寫(xiě)

假設(shè)：有一個(gè)32位的分頁(yè)存儲(chǔ)器管理系統(tǒng)，頁(yè)面的大小規(guī)定為1KB，每個(gè)頁(yè)表項(xiàng)占4個(gè)字節(jié)，求頁(yè)表所占的最大內(nèi)存空間？6.兩級(jí)頁(yè)表32位計(jì)算機(jī)系統(tǒng)的邏輯地址空間應(yīng)是232，頁(yè)表長(zhǎng)度為：232/210=222，則頁(yè)表所占的內(nèi)存空間就是222×22=224個(gè)字節(jié)，即16MB。4.兩級(jí)頁(yè)表（1）原理：將頁(yè)表分成與內(nèi)存物理塊大小相等的頁(yè)，在內(nèi)存中采用離散方式存放；只把當(dāng)前使用的那部分頁(yè)表項(xiàng)調(diào)入內(nèi)存。（2）兩級(jí)頁(yè)表的邏輯結(jié)構(gòu)外層頁(yè)表：將頁(yè)表進(jìn)行分頁(yè)，并為其建立一張頁(yè)表。每個(gè)頁(yè)表分頁(yè)在外層頁(yè)表中占一表項(xiàng)，表項(xiàng)的內(nèi)容為頁(yè)表頁(yè)在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)。01…114115…10241025…

…………………01234...114…102410111068012…n第0號(hào)第n號(hào)第1號(hào)外層頁(yè)表（頁(yè)目錄）頁(yè)表01…頁(yè)表分頁(yè)外層頁(yè)號(hào)外層頁(yè)內(nèi)地址頁(yè)內(nèi)地址

（3）兩級(jí)頁(yè)表的地址變換1）邏輯地址結(jié)構(gòu)2）地址變換過(guò)程外層頁(yè)號(hào)P1外層頁(yè)內(nèi)地址P2頁(yè)內(nèi)地址d外部頁(yè)表寄存器外層頁(yè)表頁(yè)表項(xiàng)塊號(hào)

d++外部頁(yè)表的始址物理寄存器P2P1例1：若在一個(gè)兩級(jí)頁(yè)表的存儲(chǔ)器管理系統(tǒng)中，某指令對(duì)應(yīng)的有效地值為（1，10，253），頁(yè)面大小為1K,根據(jù)下表求該指令的物理地址。6113…2081號(hào)頁(yè)表分頁(yè)…11211205…1106…10第1205號(hào)物理塊第208號(hào)物理塊10511…AbdcIntx=20;dfgAsfsdagdhhgj253物理塊號(hào)為208，塊內(nèi)位移為253物理地址=1024×208+253例2：已知某系統(tǒng)的頁(yè)面大小為4KB，每個(gè)頁(yè)表項(xiàng)大小占4B，現(xiàn)采用多層分頁(yè)策略映射64位有效地址空間。請(qǐng)問(wèn)：若限定最高層頁(yè)表的大小占1頁(yè)，應(yīng)采用幾層分頁(yè)策略？6層4.5分段存儲(chǔ)管理方式1.為什么要引入分段存儲(chǔ)管理方式分段共享和保護(hù)動(dòng)態(tài)鏈接動(dòng)態(tài)增長(zhǎng)方便編程2.分段管理的基本原理將進(jìn)程的地址空間劃分為若干個(gè)邏輯段，段的長(zhǎng)度由邏輯信息本身的長(zhǎng)度決定。每一段占一個(gè)連續(xù)內(nèi)存分區(qū)。分段在編譯時(shí)由編譯程序完成。

3.分段管理的邏輯地址結(jié)構(gòu)

段號(hào)段內(nèi)位移

例：…CALL[X]|<Y>…LOAD1,[A]|6STORE1,[B]|C…分段MAIN…Y………C…分段X（子程序）分段A

（數(shù)據(jù)）分段B（工作區(qū)）15163104.分段管理的地址變換和數(shù)據(jù)結(jié)構(gòu)

（1）段表

系統(tǒng)為每個(gè)進(jìn)程建立一張段映射表，稱(chēng)為段表。段長(zhǎng)基地址30K40K20K80K15K120K……012…段號(hào)段表30K20K40K80K

15K120K內(nèi)存段表放于系統(tǒng)空間，進(jìn)程PCB表中存有段表始地址、段表長(zhǎng)度。+（2）分段管理的地址變換機(jī)構(gòu)段長(zhǎng)基地址30K40K20K80K15K4K……

段號(hào)2段內(nèi)位移量100段表始址段表長(zhǎng)度012…段號(hào)+物理地址（4196）段表寄存器邏輯地址≤越界5.分頁(yè)與分段的比較頁(yè)是信息的物理單位；而段是信息的邏輯單位頁(yè)的大小固定；而段的大小是由它代表的邏輯信息來(lái)決定分頁(yè)管理的地址空間是一維的，而分段管理的地址空間是二維的4.5分段存儲(chǔ)管理方式6.分段管理的共享和保護(hù)（1）段的共享

對(duì)于那些被多個(gè)程序共享的段，在內(nèi)存中只保留一個(gè)副本。副本采用可重入代碼。

4.5分段存儲(chǔ)管理方式可重入代碼：又稱(chēng)“純代碼”，是一種允許多個(gè)進(jìn)程同時(shí)訪問(wèn)的代碼?？芍厝氪a在被訪問(wèn)過(guò)程中不允許任何進(jìn)程對(duì)其進(jìn)行修改。段1段表1段2段n段1段2段n段表2……………內(nèi)存進(jìn)程1地址空間進(jìn)程2地址空間共享段共享段分段共享的示意如下圖：（2）段的保護(hù)段式管理的保護(hù)方式主要有兩種：地址越界保護(hù)（上、下界寄存器或基址+限長(zhǎng)寄存器）存儲(chǔ)保護(hù)鍵法（每個(gè)存儲(chǔ)塊分配一個(gè)單獨(dú)的保護(hù)鍵，每個(gè)進(jìn)入系統(tǒng)的作業(yè)也賦予一保護(hù)鍵，相當(dāng)于鑰匙。）存取控制4.5分段存儲(chǔ)管理方式4.6段頁(yè)式存儲(chǔ)管理方式1.基本原理首先，將用戶程序中所包含的具有獨(dú)立邏輯功能的程序或數(shù)據(jù)分成若干個(gè)段，并擁有各自的段號(hào)。然后再將每個(gè)段劃分成若干個(gè)頁(yè)，最后不足一頁(yè)的部分也占一頁(yè)。2.數(shù)據(jù)結(jié)構(gòu)（1）段表（2）段頁(yè)表（3）段表寄存器三者的關(guān)系如下圖：

段表長(zhǎng)度段表始址段號(hào)狀態(tài)頁(yè)表長(zhǎng)度頁(yè)表始址01510241062056頁(yè)號(hào)狀態(tài)塊號(hào)0……頁(yè)號(hào)狀態(tài)塊號(hào)0…………………內(nèi)存段表0號(hào)段頁(yè)表1號(hào)段頁(yè)表段表寄存器4.6段頁(yè)式