操作系統(tǒng)(第2版)孟慶昌牛欣源編著課件第五章存儲(chǔ)管理

第5章存儲(chǔ)管理圖5-1內(nèi)存在計(jì)算機(jī)系統(tǒng)中的地位第5章存儲(chǔ)管理圖5-1內(nèi)存在計(jì)算機(jī)系統(tǒng)中的地位15.1引言5.2分區(qū)法5.5分頁技術(shù)5.6分段技術(shù)5.7段頁式技術(shù)5.8虛擬存儲(chǔ)器5.9請求分頁技術(shù)5.10頁面置換算法本章內(nèi)容提要5.1引言本章內(nèi)容提要25.1引言

內(nèi)存（MainMemory或PrimaryMemory或RealMemory）也稱主存。指CPU能直接存取指令和數(shù)據(jù)的存儲(chǔ)器，統(tǒng)一編址。5.1引言

內(nèi)存（MainMemory或Pri35.1.1用戶程序的執(zhí)行圖5-2用戶程序的機(jī)內(nèi)處理過程5.1.1用戶程序的執(zhí)行圖5-2用戶程序的機(jī)內(nèi)處理過45.1.1用戶程序的主要處理階段1．編輯階段：編輯源代碼。2．編譯階段：源代碼轉(zhuǎn)換為二進(jìn)制指令構(gòu)成的目標(biāo)代碼模塊。3．鏈接階段：將目標(biāo)模塊及所需的庫函數(shù)鏈接形成一個(gè)可執(zhí)行程序。4．裝入階段：將可執(zhí)行程序裝入內(nèi)存某地址空間。5．運(yùn)行階段：從第一條指令開始運(yùn)行程序。

5.1.1用戶程序的主要處理階段1．編輯階段：編輯源代碼5內(nèi)存的使用每個(gè)目標(biāo)模塊指令代碼都以0為基地址順序編址，稱為相對地址或邏輯地址。內(nèi)存中物理存儲(chǔ)單元統(tǒng)一由基地址0開始順序編址，稱為絕對地址或物理地址?？蓤?zhí)行程序各條指令需要進(jìn)行地址轉(zhuǎn)換方能正確執(zhí)行。內(nèi)存的使用每個(gè)目標(biāo)模塊指令代碼都以0為基地址順序編址，稱為相6主存管理功能邏輯地址到物理地址的地址轉(zhuǎn)換內(nèi)存分配和回收存儲(chǔ)保護(hù)內(nèi)存擴(kuò)充(虛擬存儲(chǔ)技術(shù))主存管理功能邏輯地址到物理地址的地址轉(zhuǎn)換75.1.2重定位

程序邏輯地址的范圍為邏輯地址空間?？蓤?zhí)行程序存放的內(nèi)存存儲(chǔ)單元的范圍為物理地址空間。用戶程序和數(shù)據(jù)裝入內(nèi)存時(shí)，需對目標(biāo)程序中的邏輯地址進(jìn)行修改，把邏輯地址轉(zhuǎn)變?yōu)槲锢淼刂返倪^程稱做地址重定位。5.1.2重定位

程序邏輯地址的范圍為邏輯地址空間。8地址映射LoadA12003456。。1200物理地址空間LoadAdata1data13456源程序LoadA200

34560100200編譯連接邏輯地址空間BA=10001000地址映射1200物理地址空間LoadAdata1源程序L91．靜態(tài)重定位目標(biāo)程序裝入內(nèi)存時(shí)，由裝入程序?qū)δ繕?biāo)程序中的指令地址、數(shù)據(jù)地址進(jìn)行修改，完成邏輯地址到物理地址的轉(zhuǎn)換。1．靜態(tài)重定位目標(biāo)程序裝入內(nèi)存時(shí)，由裝入程序?qū)δ繕?biāo)程序中的指10圖5-4靜態(tài)重定位示意圖圖5-4靜態(tài)重定位示意圖11靜態(tài)重定位技術(shù)分析優(yōu)點(diǎn)不需要硬件的支持缺點(diǎn)程序必須占用連續(xù)的內(nèi)存空間程序裝入后不能移動(dòng)位置不支持虛擬存儲(chǔ)及其交換技術(shù)進(jìn)程難以共享程序代碼靜態(tài)重定位技術(shù)分析優(yōu)點(diǎn)122．動(dòng)態(tài)重定位

在每條指令執(zhí)行時(shí)，對所訪問的內(nèi)存進(jìn)行地址重定位。硬件地址轉(zhuǎn)換機(jī)構(gòu)實(shí)現(xiàn)動(dòng)態(tài)重定位。2．動(dòng)態(tài)重定位

在每條指令執(zhí)行時(shí)，對所訪問的內(nèi)存進(jìn)行地址重定13圖5-5動(dòng)態(tài)重定位示意圖圖5-5動(dòng)態(tài)重定位示意圖14動(dòng)態(tài)地址重定位優(yōu)點(diǎn)：程序的內(nèi)存空間動(dòng)態(tài)可變，當(dāng)程序移到另一個(gè)空間時(shí)，修改寄存器BR的值一個(gè)程序不必占用連續(xù)內(nèi)存空間可以部分裝入程序運(yùn)行便于多個(gè)進(jìn)程共享同一個(gè)程序代碼動(dòng)態(tài)地址重定位的代價(jià)：需要硬件的支持。實(shí)現(xiàn)存儲(chǔ)管理的軟件算法較為復(fù)雜。動(dòng)態(tài)地址重定位優(yōu)點(diǎn)：155.2分區(qū)法

支持多道程序運(yùn)行的一種存儲(chǔ)管理方式。把整個(gè)內(nèi)存劃分為若干大小不等的區(qū)域，操作系統(tǒng)占用一個(gè)區(qū)域，其它區(qū)域供用戶進(jìn)程共享，每個(gè)進(jìn)程占用一個(gè)分區(qū)，這種方法稱為分區(qū)存儲(chǔ)管理。分區(qū)的劃分：固定分區(qū)動(dòng)態(tài)分區(qū)5.2分區(qū)法

支持多道程序運(yùn)行的一種存儲(chǔ)管理方式165.2.1固定分區(qū)法

內(nèi)存中分區(qū)個(gè)數(shù)、分區(qū)大小固定，每個(gè)分區(qū)裝入一個(gè)進(jìn)程。1．分區(qū)的大小劃分分區(qū)大小有兩種方式：分區(qū)大小相同分區(qū)大小不同5.2.1固定分區(qū)法

內(nèi)存中分區(qū)個(gè)數(shù)、分區(qū)大小固定，每172．內(nèi)存分配分區(qū)等分方式，進(jìn)程裝入內(nèi)存很簡單。分區(qū)差分方式，有多個(gè)輸入隊(duì)列法和單一輸入隊(duì)列法圖5-6固定分區(qū)內(nèi)存分配2．內(nèi)存分配圖5-6固定分區(qū)內(nèi)存分配185.2.2動(dòng)態(tài)分區(qū)法1．分區(qū)的分配進(jìn)程進(jìn)入內(nèi)存建立分區(qū)，大小適應(yīng)進(jìn)程的需要。這種技術(shù)稱為動(dòng)態(tài)分區(qū)法。2．?dāng)?shù)據(jù)結(jié)構(gòu)（1）空閑分區(qū)表存放（2）空閑分區(qū)鏈存放5.2.2動(dòng)態(tài)分區(qū)法1．分區(qū)的分配19圖5-7MVT的內(nèi)存分配和進(jìn)程調(diào)度情況圖5-7MVT的內(nèi)存分配和進(jìn)程調(diào)度情況203．動(dòng)態(tài)分區(qū)分配算法（1）最先適應(yīng)算法空閑表按內(nèi)存地址順序排列（2）最佳（壞）適應(yīng)算法空閑表按空閑塊大小的增量形式排列（3）循環(huán)適應(yīng)算法最先適應(yīng)算法的變種。從上次找到的可用分區(qū)的下一個(gè)空閑分區(qū)開始查找，順序選擇滿足要求的第一個(gè)空閑分區(qū)。3．動(dòng)態(tài)分區(qū)分配算法（1）最先適應(yīng)算法215.3可重定位分區(qū)分配

5.3.1碎片問題內(nèi)存中尺寸太小、無法利用的小分區(qū)稱做“碎片”。固定分區(qū)法會(huì)產(chǎn)生內(nèi)部碎片。動(dòng)態(tài)分區(qū)會(huì)產(chǎn)生外部碎片.5.3可重定位分區(qū)分配

5.3.1碎片問題22圖5-9分配16KB內(nèi)存塊之前和之后的內(nèi)存配置圖5-9分配16KB內(nèi)存塊之前和之后的內(nèi)存配置235.3.1碎片問題緊縮的時(shí)機(jī)進(jìn)程結(jié)束、釋放所占用的分區(qū)時(shí)（空閑區(qū)有可能相鄰）在分配進(jìn)程的分區(qū)時(shí)（空閑區(qū)有可能不夠）5.3.1碎片問題緊縮的時(shí)機(jī)245.3.2緊縮

移動(dòng)某些已分配區(qū)，使所有進(jìn)程的分區(qū)緊鄰的技術(shù)。圖5-10可重定位分區(qū)的緊縮5.3.2緊縮

移動(dòng)某些已分配區(qū)，使所有進(jìn)程的分區(qū)緊鄰的255.3.3動(dòng)態(tài)重定位的實(shí)現(xiàn)動(dòng)態(tài)重定位經(jīng)常用硬件實(shí)現(xiàn)硬件支持基址寄存器限長寄存器5.3.3動(dòng)態(tài)重定位的實(shí)現(xiàn)動(dòng)態(tài)重定位經(jīng)常用硬件實(shí)現(xiàn)26圖5-11動(dòng)態(tài)重定位的實(shí)現(xiàn)過程圖5-11動(dòng)態(tài)重定位的實(shí)現(xiàn)過程275.3.4可重定位分區(qū)法優(yōu)缺點(diǎn)優(yōu)點(diǎn)可以消除碎片，能夠分配更多的分區(qū)，有助于多道程序設(shè)計(jì)，提高內(nèi)存的利用率。缺點(diǎn)緊縮技術(shù)花費(fèi)CPU時(shí)間當(dāng)進(jìn)程大于整個(gè)空閑區(qū)無法裝入時(shí)，仍要浪費(fèi)一定的內(nèi)存進(jìn)程的存儲(chǔ)區(qū)內(nèi)可能放有從未使用的信息進(jìn)程之間無法對信息共享5.3.4可重定位分區(qū)法優(yōu)缺點(diǎn)優(yōu)點(diǎn)285.4對換技術(shù)

圖5-12對換兩個(gè)進(jìn)程當(dāng)內(nèi)存不足時(shí)，將暫時(shí)不運(yùn)行的進(jìn)程換到外存，將需要馬上運(yùn)行的進(jìn)程調(diào)入內(nèi)存。5.4對換技術(shù)

圖5-12對換兩個(gè)進(jìn)程當(dāng)內(nèi)存不29圖5-13多道程序?qū)Q技術(shù)示例圖5-13多道程序?qū)Q技術(shù)示例305.5分頁技術(shù)

5.5.1分頁存儲(chǔ)管理的基本概念 把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁（page）。從0開始編制頁號(hào)，頁內(nèi)地址從0開始編址。（1）邏輯地址空間——分頁（2）內(nèi)存地址空間——分塊頁（或塊）大小由硬件（系統(tǒng)）確定5.5分頁技術(shù)

5.5.1分頁存儲(chǔ)管理的基本概31（3）邏輯地址表示圖5-14分頁技術(shù)的地址結(jié)構(gòu)邏輯地址為A，頁面大小為L，頁號(hào)p和頁內(nèi)地址d可按下式求得：p=INT[A/L]，d=[A]MODL（3）邏輯地址表示圖5-14分頁技術(shù)的地址結(jié)構(gòu)邏輯地址為32以塊為單位分配內(nèi)存進(jìn)程每個(gè)頁面對應(yīng)一個(gè)內(nèi)存塊一個(gè)進(jìn)程頁面可以裝入物理上不連續(xù)的內(nèi)存塊頁表記錄分配結(jié)果（4）內(nèi)存分配原則以塊為單位分配內(nèi)存（4）內(nèi)存分配原則33（5）頁表——從頁號(hào)到物理塊號(hào)的地址映射圖5-15分頁存儲(chǔ)管理系統(tǒng)（5）頁表——從頁號(hào)到物理塊號(hào)的地址映射圖5-15分頁存34內(nèi)存塊表記錄內(nèi)存使用情況每個(gè)內(nèi)存塊在內(nèi)存塊表中占一項(xiàng)，記錄該塊的狀態(tài)：空閑/分配。（6）內(nèi)存塊表內(nèi)存塊表記錄內(nèi)存使用情況（6）內(nèi)存塊表355.5.2分頁系統(tǒng)中的地址映射圖5-16分頁系統(tǒng)的地址轉(zhuǎn)換機(jī)構(gòu)每個(gè)進(jìn)程平均有半個(gè)頁面的內(nèi)部碎片5.5.2分頁系統(tǒng)中的地址映射圖5-16分頁系統(tǒng)的地36設(shè)進(jìn)程平均大小為s字節(jié)，每個(gè)頁表項(xiàng)占e字節(jié)。每個(gè)進(jìn)程需要的頁數(shù)為s/p每個(gè)進(jìn)程的頁表空間：e*s/p字節(jié)每個(gè)進(jìn)程內(nèi)部碎片平均為p/2頁表和內(nèi)部碎片帶來的總開銷是：e*s/p+p/2令該表達(dá)式的值最小，對p求導(dǎo)，令其等于0，得到方程：-e*s/p2+1/2=0得出最佳頁面尺寸公式，僅考慮上述兩個(gè)因素：5.5.3頁面尺寸p的討論如果s=1MB，e=8B，則最佳頁面尺寸p是4KB設(shè)進(jìn)程平均大小為s字節(jié)，每個(gè)頁表項(xiàng)占e字節(jié)。5.5.3頁375.5.4硬件支持

將頁表保存在內(nèi)存中，由一個(gè)頁表基址寄存器PTBR指向該頁表。整個(gè)系統(tǒng)只有一個(gè)PTBR。內(nèi)存存取速度下降50%！5.5.4硬件支持

將頁表保存在內(nèi)存中，由一個(gè)頁表基址寄38把頁表放在一組快速存儲(chǔ)器中（Cache），加快訪問內(nèi)存的速度?？焖俅鎯?chǔ)器組成的頁表稱為快表，內(nèi)存中的頁表稱為慢表?？毂碛址Q相聯(lián)存儲(chǔ)器（associativememory）

或TLB（Translationlookasidebuffers）轉(zhuǎn)換檢測緩沖區(qū)。把頁表放在一組快速存儲(chǔ)器中（Cache），加快訪問內(nèi)存的速度39快表（或TranslationLookasideBuffer，TLB）快表每項(xiàng)包括鍵號(hào)和值兩部分鍵號(hào)是當(dāng)前進(jìn)程正在使用的某個(gè)頁面號(hào)值是該頁面所對應(yīng)的物理塊號(hào)快表（或TranslationLookasideBuff40快表性能分析示例如果訪問聯(lián)想存儲(chǔ)器的時(shí)間為20ns，訪問內(nèi)存的時(shí)間是100ns，假定訪問聯(lián)想存儲(chǔ)器的命中率分別為0%，50%，80%，90%，98%，下表列出需要的訪問時(shí)間：命中率%平均訪問時(shí)間：T=h*120+（1-h）*2200T=22050T=17080T=14090T=13098T=122快表性能分析示例如果訪問聯(lián)想存儲(chǔ)器的時(shí)間為20ns，訪問內(nèi)存41圖5-17利用快表實(shí)現(xiàn)地址轉(zhuǎn)換圖5-17利用快表實(shí)現(xiàn)地址轉(zhuǎn)換425.5.5保護(hù)方式

（1）利用頁表本身進(jìn)行保護(hù)：保護(hù)頁表基址和頁表長度（2）設(shè)置存取控制位：一個(gè)頁表項(xiàng)，權(quán)限包括：（R/W/RW），出錯(cuò)發(fā)中斷。（3）設(shè)置合法標(biāo)志5.5.5保護(hù)方式

（1）利用頁表本身進(jìn)行保護(hù)：保護(hù)頁表435.5.6頁表的構(gòu)造1．多級(jí)頁表 大邏輯地址空間，頁表項(xiàng)太多。假定： 邏輯地址空間：232～264一個(gè)進(jìn)程的邏輯空間占32位，頁面大小為4kb 最大進(jìn)程可有220（1M）個(gè)邏輯頁 頁表表項(xiàng)達(dá)220個(gè)。

?方案：利用兩級(jí)頁表——給頁表分頁。5.5.6頁表的構(gòu)造1．多級(jí)頁表44圖5-18兩級(jí)頁表地址結(jié)構(gòu)圖5-18兩級(jí)頁表地址結(jié)構(gòu)45圖5-19兩級(jí)頁表結(jié)構(gòu)1023圖5-19兩級(jí)頁表結(jié)構(gòu)102346圖5-20兩級(jí)頁表結(jié)構(gòu)的地址轉(zhuǎn)換圖5-20兩級(jí)頁表結(jié)構(gòu)的地址轉(zhuǎn)換47圖5-21三級(jí)頁表地址結(jié)構(gòu)圖5-21三級(jí)頁表地址結(jié)構(gòu)48三級(jí)頁表結(jié)構(gòu)及其地址映射過程三級(jí)頁表結(jié)構(gòu)及其地址映射過程492．散列頁表HashedPageTable以頁號(hào)作為參數(shù)形成散列值散列表中每一項(xiàng)具有相同散列值，是一個(gè)鏈表。每個(gè)鏈表元素由頁號(hào)、對應(yīng)的內(nèi)存塊號(hào)、指向鏈表中下個(gè)元素的指針組成。2．散列頁表HashedPageTable50圖5-22散列頁表圖5-22散列頁表513．倒置頁表進(jìn)程頁表以邏輯地址的順序排序，虛地址空間較大。倒置頁表按內(nèi)存塊號(hào)排序，每個(gè)內(nèi)存塊占有一個(gè)表項(xiàng)。每個(gè)表項(xiàng)包括存放在該內(nèi)存塊中頁號(hào)和擁有該頁面的進(jìn)程標(biāo)識(shí)符。系統(tǒng)只有一個(gè)頁表。3．倒置頁表進(jìn)程頁表以邏輯地址的順序排序，虛地址空間較大。52圖5-23倒置頁表圖5-23倒置頁表535.5.7頁面共享圖5-24頁面共享可再入代碼（或純碼，在其執(zhí)行過程中本身不做任何修改的代碼，通常由指令和常數(shù)組成）。5.5.7頁面共享圖5-24頁面共享可再入代碼（或純54分頁式管理可實(shí)現(xiàn)頁面共享?xiàng)l件：共享部分是純碼程序共享部分與非共享部分，分頁單獨(dú)存放共享部分的邏輯頁號(hào)、物理頁號(hào)完全相同分頁式管理可實(shí)現(xiàn)頁面共享?xiàng)l件：55分頁技術(shù)總結(jié)優(yōu)點(diǎn)：解決了碎片問題，便于管理缺點(diǎn)：實(shí)現(xiàn)共享有條件不便于動(dòng)態(tài)連接未考慮程序邏輯構(gòu)成分頁技術(shù)總結(jié)優(yōu)點(diǎn)：解決了碎片問題，便于管理56設(shè)頁長為1K，程序地址字長為16位，用戶程序空間和頁表如圖： 設(shè)頁長為1K，程序地址字長為16位，用戶程序空間和頁表如圖：57執(zhí)行指令MOVr1，[2500]，地址轉(zhuǎn)換步驟說明取出程序地址字2500送虛地址寄存器VR由硬件分離頁號(hào)P和頁內(nèi)地址W：頁長為1K，所以頁內(nèi)地址占10位（0~9位），頁號(hào)占6位（10~15位）硬件取出VR寄存器中的高6位即頁號(hào)，低10位即頁內(nèi)地址，得到頁號(hào)P=2，頁內(nèi)位移W=452根據(jù)頁號(hào)P=2，硬件自動(dòng)查該進(jìn)程頁表，找到第2頁對應(yīng)塊號(hào)為7，將塊號(hào)送到內(nèi)存地址寄存器MR的高10位中，將VR中W值452復(fù)制到MR低10位中，形成內(nèi)存地址。系統(tǒng)就以MR中的地址訪問內(nèi)存執(zhí)行指令MOVr1，[2500]，地址轉(zhuǎn)換步驟說明58計(jì)算分頁地址時(shí)要注意： 給出地址字的進(jìn)制 地址的空間長度 頁長 邏輯空間允許的最大頁數(shù)計(jì)算分頁地址時(shí)要注意：595.6分段技術(shù)5.6.1分段存儲(chǔ)管理的基本概念分頁存儲(chǔ)管理存在問題——導(dǎo)致程序在用戶角度的內(nèi)存空間和實(shí)際內(nèi)存空間不同。子程序符號(hào)表主函數(shù)庫函數(shù)堆棧用戶角度的內(nèi)存5.6分段技術(shù)5.6.1分段存儲(chǔ)管理的基本概念60段（segmentation）用戶角度的內(nèi)存管理模式,邏輯地址空間是段的集合當(dāng)用戶程序被編譯時(shí)，編譯程序自動(dòng)構(gòu)建程序的分段，比如：pascal編譯器全局量過程堆?？蓤?zhí)行代碼局部變量段（segmentation）用戶角度的內(nèi)存管理模式,邏輯地611．分段按程序自身的邏輯關(guān)系劃分為若干個(gè)程序段段名段長段號(hào)：段號(hào)從0開始排段內(nèi)地址：從0開始編址，段內(nèi)地址連續(xù)1．分段按程序自身的邏輯關(guān)系劃分為若干個(gè)程序段62圖5-25分段地址空間段號(hào)段長08k15k26k35k圖5-25分段地址空間段號(hào)段長08k15k26k35k632．分段程序的邏輯地址

邏輯地址：段號(hào)s+段內(nèi)地址d。分段存儲(chǔ)，進(jìn)程邏輯地址空間是二維的。圖5-26分段技術(shù)地址結(jié)構(gòu)2．分段程序的邏輯地址

邏輯地址：段號(hào)s+段內(nèi)地址d。64段號(hào)（8bit）段內(nèi)地址（16bit）0000，00000000，……,00000000，00001111，……,11110000，00010000，……,00000000，00011111，……,1111……，……，1111，11110000，……,00001111，11111111，……,1111段號(hào)（8bit）段內(nèi)地址（16bit）0000，000000653．內(nèi)存分配

內(nèi)存以段為單位分配，每段占用一塊連續(xù)的內(nèi)存分區(qū)。各分區(qū)的大小由對應(yīng)段的大小決定。最大段長（分區(qū)大?。┳疃喽螖?shù)（一個(gè)進(jìn)程擁有最多分區(qū)數(shù)）3．內(nèi)存分配

內(nèi)存以段為單位分配，每段占用一塊連續(xù)的內(nèi)存分區(qū)664．段地址映射段表系統(tǒng)為每個(gè)進(jìn)程建一個(gè)段表。每個(gè)段是段表的一項(xiàng)，段表項(xiàng)中包含段號(hào)、段長和段起始地址。段表基址寄存器系統(tǒng)建立一個(gè)段表地址寄存器（段表首址+段表長度）。4．段地址映射段表67.....40S30N20L10P00K邏輯段號(hào)01234作業(yè)1的地址空間10003200500060008000PKSLN主存k3200p1500l6000n8000s5000段長段地址01234操作系統(tǒng)40S30N20L10P00K邏輯段號(hào)01234作68段號(hào)（8bit）段內(nèi)地址（16bit）0000，00100000，0000，0000，0111該段基址：6000=（1，0111，0111，0000）2基址加段內(nèi)位移量0001，0111，0111，00000000，0000，0000，01110001，0111，0111，0111（得：物理地址）（6007）邏輯地址：第2段，第7個(gè)字節(jié)段號(hào)（8bit）段內(nèi)地址（16bit）0000，00100069圖5-27分段地址轉(zhuǎn)換5.6.2地址轉(zhuǎn)換圖5-27分段地址轉(zhuǎn)換5.6.2地址轉(zhuǎn)換705.6.3段的共享和保護(hù)

1．段的共享在段一級(jí)實(shí)現(xiàn)，共享信息可以設(shè)成一段?？梢灾还蚕聿糠殖绦?。5.6.3段的共享和保護(hù)

1．段的共享71圖5-28分段系統(tǒng)中段的共享圖5-28分段系統(tǒng)中段的共享722．段的保護(hù)

段的保護(hù)措施包括以下三種：①存取控制（R/W/RW）②段表本身可起保護(hù)作用。表項(xiàng)中設(shè)置該段的長度限制段長限制，段表地址寄存器中有段表長度的信息。③保護(hù)環(huán)（進(jìn)程優(yōu)先權(quán)由所在環(huán)決定）2．段的保護(hù)

段的保護(hù)措施包括以下三種：735．分頁和分段的主要區(qū)別

①頁是信息的物理單位。段是信息的邏輯單位。②頁大小由系統(tǒng)確定，段長因段而異。③分頁地址空間是一維的。分段的地址空間是二維的。④分頁系統(tǒng)很難實(shí)現(xiàn)過程和數(shù)據(jù)的分離。分段系統(tǒng)可以。

各段長度不一，難以統(tǒng)一管理。 ——引入段頁式管理5．分頁和分段的主要區(qū)別

①頁是信息的物理單位。段是信息的745.7段頁式技術(shù)

5.7.1段頁式存儲(chǔ)管理的基本原理圖5-29段頁式存儲(chǔ)邏輯地址結(jié)構(gòu)5.7段頁式技術(shù)

5.7.1段頁式存儲(chǔ)管理的基本原理755.7.2段頁式地址轉(zhuǎn)換過程

段號(hào)加段表寄存器中的段表首址該段頁表首址+頁表長度頁表長度比較越界發(fā)中斷，取頁號(hào)加頁表基址對應(yīng)頁號(hào)項(xiàng)，讀出頁表中的物理塊號(hào)物理塊號(hào)與頁內(nèi)地址合成物理地址(如不在內(nèi)存發(fā)缺頁中斷，重新更新頁表)進(jìn)行讀寫。5.7.2段頁式地址轉(zhuǎn)換過程

段號(hào)加段表寄存器中的段表首址76操作系統(tǒng)(第2版)孟慶昌牛欣源編著課件第五章存儲(chǔ)管理775.8虛擬存儲(chǔ)器5.8.1虛擬存儲(chǔ)器的概念進(jìn)程部分裝入內(nèi)存的依據(jù)程序含有不執(zhí)行代碼段程序某些選項(xiàng)和路徑很少使用程序執(zhí)行呈現(xiàn)局部性原理部分調(diào)入內(nèi)存的好處用戶編制程序時(shí)不必考慮內(nèi)存容量的限制在容量有限的內(nèi)存中，可同時(shí)裝入更多的進(jìn)程5.8虛擬存儲(chǔ)器5.8.1虛擬存儲(chǔ)器的概念78虛存下的編程地址空間指令操作數(shù)中地址的二進(jìn)制位數(shù)磁盤中對換區(qū)的大小虛存下的編程地址空間指令操作數(shù)中地址的二進(jìn)制位數(shù)795.8.2虛擬存儲(chǔ)器的特征虛擬擴(kuò)充部分裝入內(nèi)存分配不連續(xù)進(jìn)程執(zhí)行中多次對換5.8.2虛擬存儲(chǔ)器的特征805.9請求分頁技術(shù)5.9.1請求分頁存儲(chǔ)管理的基本思想按照分頁管理提供虛擬存儲(chǔ)器。一個(gè)進(jìn)程的起始頁面在內(nèi)存就可執(zhí)行；繼續(xù)執(zhí)行的頁面不在內(nèi)存，則動(dòng)態(tài)換入內(nèi)存。頁表項(xiàng)增加一個(gè)字段—標(biāo)志位，標(biāo)示進(jìn)程該頁面是否已在內(nèi)存。5.9請求分頁技術(shù)5.9.1請求分頁存儲(chǔ)管理的基本思815.9.2硬件支持及缺頁處理

1．頁表機(jī)制頁表項(xiàng)通常包含下列5種信息：5.9.2硬件支持及缺頁處理

1．頁表機(jī)制82①內(nèi)存塊號(hào)②標(biāo)志位 該位是1，表示該表項(xiàng)有效，該頁在內(nèi)存， 可以使用。 該位是0，表示該表項(xiàng)對應(yīng)的頁面不在內(nèi)存，訪問該頁置缺頁中斷③保護(hù)位（讀寫權(quán)限）④修改位/引用位。記錄該頁的狀態(tài)。⑤禁止緩存位。該位用于禁止該頁被緩存。①內(nèi)存塊號(hào)83XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K虛地址空間物理地址空間}虛頁塊號(hào)虛存頁表XXXX7X5XXX34061260K-64K56K-60K84虛擬存儲(chǔ)的地址映射查詢頁表項(xiàng)及中斷駐留位在內(nèi)存，可訪問，進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換不在內(nèi)存，發(fā)缺頁中斷，調(diào)入所需頁面，進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換按物理地址訪問該頁內(nèi)存。虛擬存儲(chǔ)的地址映射查詢頁表項(xiàng)及中斷駐留位85148400000000000000001111000010110000000000000111100100011101001101011513121110976532100010000000000100110000000000100110在/不在內(nèi)存虛存頁表虛地址8196物理地址24580014840000000000000000111100865.9.3請求分頁技術(shù)的性能

令p表示缺頁中斷的概率（0≤p≤1），簡稱缺頁率，等于缺頁次數(shù)與全部訪問內(nèi)存次數(shù)之比。虛存有效存取時(shí)間表示為： (1-p)×ma+p×缺頁處理時(shí)間5.9.3請求分頁技術(shù)的性能

令p表示缺頁中斷的概率（0872．缺頁中斷機(jī)構(gòu)

圖5-34指令執(zhí)行步驟與缺頁中斷處理過程2．缺頁中斷機(jī)構(gòu)

圖5-34指令執(zhí)行步驟與缺頁中斷處理過88進(jìn)程A缺頁處理過程進(jìn)程A遇到缺頁指令，捕俘進(jìn)入操作系統(tǒng)。保存進(jìn)程A的各個(gè)寄存器和進(jìn)程狀態(tài)信息。檢查該頁的訪問合法性，并確定該頁在磁盤上的地址，把該頁從盤上讀到空閑內(nèi)存塊中。在等待盤I/O完成時(shí)，把CPU分給其他進(jìn)程盤I/O完成，發(fā)出盤中斷。保存進(jìn)程B的用戶寄存器和進(jìn)程狀態(tài)。確定該中斷來自磁盤。調(diào)整頁表，標(biāo)明所需頁已放入內(nèi)存。進(jìn)程A就緒，等待分配CPU。調(diào)度進(jìn)程A，則恢復(fù)它的各寄存器、進(jìn)程狀態(tài)和新的頁表，然后重新執(zhí)行前面被中斷的指令。進(jìn)程A缺頁處理過程進(jìn)程A遇到缺頁指令，捕俘進(jìn)入操作系統(tǒng)。89①處理缺頁中斷的時(shí)間②從磁盤調(diào)入該頁的時(shí)間③重新啟動(dòng)該進(jìn)程的時(shí)間處理缺頁中斷花費(fèi)的時(shí)間處理缺頁中斷花費(fèi)的時(shí)間90從磁盤調(diào)入該頁的時(shí)間包括磁盤尋道時(shí)間（即磁頭從當(dāng)前磁道移至指定磁道所用的時(shí)間）旋轉(zhuǎn)延遲時(shí)間（即磁頭從當(dāng)前位置落到指定扇區(qū)開頭所用的時(shí)間）數(shù)據(jù)傳輸時(shí)間從磁盤調(diào)入該頁的時(shí)間包括91有效存取時(shí)間T磁盤旋轉(zhuǎn)延遲時(shí)間約為8ms，尋道時(shí)間約為15ms，傳輸時(shí)間是1ms，全部換頁時(shí)間約25ms。平均缺頁服務(wù)時(shí)間取25ms，內(nèi)存存取時(shí)間取100ns，則T=(1-p)×100+p×25000000=100+24999900×p有效存取時(shí)間T磁盤旋轉(zhuǎn)延遲時(shí)間約為8ms，尋道時(shí)間約為1592有效存取時(shí)間T=110ns時(shí)則有：100+25000000×p=11025000000×p=10p=0.0000004（0.00004%）表明：缺頁率=0.00004%有效內(nèi)存讀寫時(shí)間為110ns有效存取時(shí)間T=110ns時(shí)則有：935.10頁面置換算法

5.10.1頁面置換1．頁面置換過程5.10頁面置換算法

5.10.1頁面置換942．頁面走向用戶程序的存儲(chǔ)訪問的頁號(hào)順序構(gòu)成的序列稱為頁面走向。2．頁面走向95頁面走向示例 對于給定的頁面大小，僅考慮其頁號(hào)，不關(guān)心完整的地址。 如果當(dāng)前對頁面p進(jìn)行了訪問，那么，馬上又對該頁訪問就不會(huì)缺頁。例如程序訪問的地址順序如下：0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105若每頁100個(gè)字節(jié)，則前兩位就是頁號(hào)。頁面走向簡化為：1，4，1，6，1，6，1，6，1，6，1頁面走向示例 對于給定的頁面大小，僅考慮其頁號(hào)，不關(guān)心完整96一般來說，隨著可用塊數(shù)的增加，缺頁數(shù)將減少。圖5-36缺頁量與內(nèi)存塊數(shù)關(guān)系圖一般來說，隨著可用塊數(shù)的增加，缺頁數(shù)將減少。圖5-36缺97常用頁面置換算法請求內(nèi)存管理技術(shù)在實(shí)現(xiàn)缺頁中斷時(shí)需要決定將內(nèi)存中的那些頁面調(diào)出內(nèi)存——稱為頁面淘汰算法(中級(jí)調(diào)度)統(tǒng)一采用下述頁面走向：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1并且假定用戶程序只有三個(gè)內(nèi)存塊可供使用?？疾煸诔绦驁?zhí)行的整個(gè)過程中，一共發(fā)生多少次缺頁中斷。常用頁面置換算法請求內(nèi)存管理技術(shù)在實(shí)現(xiàn)缺頁中斷時(shí)需要決定將內(nèi)985.10.2先進(jìn)先出法（FIFO）先進(jìn)入內(nèi)存的頁，先被換出。圖5-37FIFO頁面置換5.10.2先進(jìn)先出法（FIFO）先進(jìn)入內(nèi)存的頁，先被換99FIFO頁面置換算法優(yōu)點(diǎn)：容易理解、方便程序設(shè)計(jì)。性能并不很好。FIFO頁面置換算法另一個(gè)缺點(diǎn)：存在Belady異?，F(xiàn)象，即缺頁率隨內(nèi)存塊增加而增加。圖5-38關(guān)于一個(gè)頁面走向的FIFO淘汰算法的缺頁曲線FIFO頁面置換算法優(yōu)點(diǎn)：容易理解、方便程序設(shè)計(jì)。性能并不很100 有一虛擬存儲(chǔ)系統(tǒng)，采用先進(jìn)先出的頁面淘汰算法。在內(nèi)存中為每個(gè)進(jìn)程分配3塊。進(jìn)程執(zhí)行時(shí)使用頁號(hào)的順序?yàn)? 432143543215(1) 該進(jìn)程運(yùn)行時(shí)總共出現(xiàn)幾次缺頁。(2) 若每個(gè)進(jìn)程在內(nèi)存有4塊，又將產(chǎn)生幾次缺頁。(3) 如何解釋所出現(xiàn)的現(xiàn)象。

Belady異?，F(xiàn)象示例 有一虛擬存儲(chǔ)系統(tǒng)，采用先進(jìn)先出的頁面淘汰算法。在內(nèi)存中為101FIFO432143543215頁1444111555555頁233344444222頁32223333311xxxxxxx

xx共缺頁中斷9次m=3FIFO4321435102FIFO432143543215頁1444444555511頁233333344445頁32222223333頁4111111222xxxxxx

xxxx共缺頁中斷10次m=4FIFO43214354103m=3時(shí)，缺頁中斷9次m=4時(shí)，缺頁中斷10次FIFO頁面淘汰算法會(huì)產(chǎn)生異?，F(xiàn)象（Belady現(xiàn)象），即：當(dāng)分配給進(jìn)程的物理頁面數(shù)增加時(shí)，缺頁次數(shù)反而增加。m=3時(shí)，缺頁中斷9次1045.10.3最佳置換法（OPT）

最佳置換算法（OptimalReplacement,OPT）所淘汰的頁面應(yīng)在最遠(yuǎn)的將來才被訪問。圖5-39最佳頁面置換OPT算法在實(shí)現(xiàn)上有困難5.10.3最佳置換法（OPT）

最佳置換算法（Opti1055.10.4最近最少使用置換法（LRU）置換在最近一段時(shí)間里最久沒有使用過的頁面圖5-40最近最少使用頁面置換算法5.10.4最近最少使用置換法（LRU）置換在最近一段時(shí)106LRU算法需要實(shí)際硬件的支持。確定最后訪問以來的時(shí)間順序。有以下兩種可行的辦法：①計(jì)數(shù)器。②棧。圖5-41利用棧記錄目前訪問最多的頁面LRU算法需要實(shí)際硬件的支持。確定最后訪問以來的時(shí)間順序。有1075.10.5第二次機(jī)會(huì)置換法（SCR）第二次機(jī)會(huì)置換法（SecondChancePageReplacement,SCR）是對FIFO算法的改進(jìn)。當(dāng)選擇某一頁面置換時(shí)，就檢查最老頁面的引用位：如果是0，就立即淘汰該頁；如果該引用位是1，就給它第二次機(jī)會(huì)，將引用位置0，按當(dāng)前時(shí)間排在隊(duì)尾。5.10.5第二次機(jī)會(huì)置換法（SCR）第二次機(jī)會(huì)置換法（108圖5-42第二次機(jī)會(huì)法示例圖5-42第二次機(jī)會(huì)法示例1095.10.7最少使用置換法（LFU）最不經(jīng)常使用（LFU）置換算法：選擇訪問次數(shù)最少的頁面淘汰。5.10.7最少使用置換法（LFU）最不經(jīng)常使用（LF110(1)頁淘汰算法(2)程序的編制方法(3)分配給進(jìn)程的物理塊數(shù)(4)頁本身的大小影響缺頁次數(shù)的因素(1)頁淘汰算法影響缺頁次數(shù)的因素111程序編制方法示例程序編制方法1：forj=0to127fori=0to127a[i][j]=0;程序編制方法2：fori=0to127forj=0to127a[i][j]=0;內(nèi)存分配1頁，初始時(shí)矩陣數(shù)據(jù)均不在內(nèi)存；頁面大小為128個(gè)整數(shù)；矩陣A128X128按行存放。這兩個(gè)程序執(zhí)行時(shí)分別會(huì)產(chǎn)生多少次缺頁中斷？inta[128][128];程序編制方法示例程序編制方法1：程序編制方法2：內(nèi)存分配1頁112A[0][0]A[0][1]A[0][2]……A[0][127]A[1][0]A[0][1]A[0][2]……A[0][127]………………A[127][0]A[127][1]A[127][2]……A[127][127]A[0][0]A[0][1]A[0][2]……A[0][12113程序A根據(jù)已知條件可知：外循環(huán)加內(nèi)循環(huán)賦值訪問邏輯頁的順序是0、1、2、3、4、5、。。。。。。127頁，正好與缺頁中斷調(diào)入內(nèi)存的頁面順序一致。所以共產(chǎn)生128次缺頁中斷。程序B根據(jù)已知條件可知：每次內(nèi)循環(huán)賦值訪問邏輯頁的順序是0、1、2、3、4、5、。。。。。。127頁，每一次外循環(huán)賦值訪問邏輯頁的順序是0、1、2、3、4、5、。。。。。。127頁，因此，每次賦值都會(huì)產(chǎn)生一次缺頁中斷，將需要的頁面調(diào)入調(diào)入內(nèi)存。所以共產(chǎn)生128*128次缺頁中斷。結(jié)論在虛擬存儲(chǔ)器管理模式下，不同的編程方法會(huì)影響該程序執(zhí)行時(shí)缺頁中斷的次數(shù)，即影響程序執(zhí)行的速度和程序執(zhí)行的效率。程序A1145.11內(nèi)存塊的分配和抖動(dòng)問題5.11.1內(nèi)存塊的分配1．最少內(nèi)存塊數(shù)分給每個(gè)進(jìn)程的最少內(nèi)存塊數(shù)是指保證進(jìn)程正常運(yùn)行所需的最少內(nèi)存塊數(shù)大小由指令集結(jié)構(gòu)決定5.11內(nèi)存塊的分配和抖動(dòng)問題5.11.1內(nèi)存塊的分1152．內(nèi)存塊的分配①固定分配策略分配給進(jìn)程的內(nèi)存塊數(shù)是固定的，且在最初裝入時(shí)（即進(jìn)程創(chuàng)建時(shí)）確定塊數(shù)。②可變分配策略允許分給進(jìn)程的內(nèi)存塊數(shù)隨進(jìn)程的活動(dòng)而改變。2．內(nèi)存塊的分配①固定分配策略分配給進(jìn)程的內(nèi)存塊數(shù)是固定的116頁面置換范圍全局置換——允許一個(gè)進(jìn)程從所有進(jìn)程存儲(chǔ)塊中選取淘汰塊。局部置換——只允許進(jìn)程從分給它的一組內(nèi)存塊中選擇淘汰塊。頁面置換范圍1173．內(nèi)存塊分配算法（1）等分法（2）比例法設(shè)進(jìn)程pi的地址空間大小為si，則總地址空間為S=∑si若可用塊的總數(shù)是m，則分給進(jìn)程pi的塊數(shù)是ai

≈m.si

/S（3）優(yōu)先權(quán)法3．內(nèi)存塊分配算法（1）等分法1185.11.2抖動(dòng)問題系統(tǒng)頁面置換非常頻繁，cpu頻繁執(zhí)行頁面置換調(diào)度程序，用于執(zhí)行進(jìn)程的時(shí)間較少。稱為系統(tǒng)“抖動(dòng)”。1．產(chǎn)生抖動(dòng)的原因圖5-45CPU利用率與多道程序度之間的關(guān)系5.11.2抖動(dòng)問題系統(tǒng)頁面置換非常頻繁，cpu頻繁執(zhí)行1192．防止抖動(dòng)的方法①采用局部置換策略。②利用工作集策略防止抖動(dòng)。③掛起某些進(jìn)程。④采用缺頁頻度法（PageFaultFrequency,PFF）。圖5-46缺頁頻度2．防止抖動(dòng)的方法圖5-46缺頁頻度1203．工作集（1）局部性模型時(shí)間局部——一旦某條指令或數(shù)據(jù)被訪問過，往往很快又被訪問。空間局部——一旦某個(gè)位置被訪問過，它附近的位置也可能很快要用到。（2）工作集模型工作集——一個(gè)進(jìn)程在某一小段時(shí)間內(nèi)訪問頁面的集合。3．工作集（1）局部性模型121圖5-47存儲(chǔ)訪問的局部性圖5-47存儲(chǔ)訪問的局部性122圖5-48工作集模型D就是系統(tǒng)中全部（n個(gè)）進(jìn)程對內(nèi)存塊的總請求量。如果請求值D大于可用內(nèi)存塊的總量m(D＞m)，將出現(xiàn)抖動(dòng)。工作集依賴于程序的行為，并且其大小與的取值有關(guān)。每個(gè)進(jìn)程的工作集大小為WSSi，那么圖5-48工作集模型D就是系統(tǒng)中全部（n個(gè)）進(jìn)程對內(nèi)存1234．工作集頁面置換法淘汰一個(gè)不在工作集中的頁面。4．工作集頁面置換法淘汰一個(gè)不在工作集中的頁面。1245.12請求分段技術(shù)

5.12.1請求分段存儲(chǔ)管理的硬件支持段表項(xiàng)增加一位，表明該段的存在狀態(tài)。增加一些控制位、修改位。5.12請求分段技術(shù)

5.12.1請求分段存儲(chǔ)管理的1255.12.2動(dòng)態(tài)鏈接和鏈接中斷處理

1．動(dòng)態(tài)鏈接僅當(dāng)用到某個(gè)分段時(shí)才對它進(jìn)行鏈接圖5-49直接編址與間接編址5.12.2動(dòng)態(tài)鏈接和鏈接中斷處理

1．動(dòng)態(tài)鏈接圖5-41262．鏈接中斷處理

圖5-50段的動(dòng)態(tài)鏈接2．鏈接中斷處理

圖5-50段的動(dòng)態(tài)鏈接1275.13Linux系統(tǒng)的存儲(chǔ)管理

5.13.1Linux的多級(jí)頁表結(jié)構(gòu)圖5-51Linux進(jìn)程的虛擬存儲(chǔ)空間5.13Linux系統(tǒng)的存儲(chǔ)管理

5.13.1Lin128Linux系統(tǒng)采用三級(jí)頁表的方式

圖5-52三級(jí)頁表地址映射示意圖對于i386來說，CPU只支持兩級(jí)模型。Linux系統(tǒng)采用三級(jí)頁表的方式1295.13.2內(nèi)存頁的分配與釋放

圖5-53空閑內(nèi)存的組織示意圖5.13.2內(nèi)存頁的分配與釋放

圖5-53空閑內(nèi)存的1305.13.3內(nèi)存交換

由內(nèi)核的交換守護(hù)進(jìn)程kswapd完成5.13.3內(nèi)存交換

由內(nèi)核的交換守護(hù)進(jìn)程kswapd完131本章習(xí)題10、某虛擬存儲(chǔ)器的用戶編程空間共32個(gè)頁面，每頁為1KB，內(nèi)存為16KB，假定某時(shí)刻一個(gè)用戶頁表中已調(diào)入內(nèi)存的頁面號(hào)和物理塊號(hào)如表所示，則邏輯地址0A5CH所對應(yīng)的物理地址為

。頁號(hào)物理塊號(hào)051102437本章習(xí)題10、某虛擬存儲(chǔ)器的用戶編程空間共32個(gè)頁面，每頁為13213、已知段表如下：下述邏輯地址的物理地址分別是多少？0,4301,101,111,5003,4004,112段號(hào)基址段長0219600123001429010031327580419529613、已知段表如下：下述邏輯地址的物理地址分別是多少？段號(hào)基133本章作業(yè)1、解釋以下概念：物理地址、邏輯地址、邏輯地址空間、內(nèi)存空間、重定位、碎片、緊縮技術(shù)。2、什么是分頁？什么是分段？3、考慮下述頁面走向：1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6，當(dāng)內(nèi)存塊分別為3和5時(shí)，試問LRU，F(xiàn)IFO，OPT三種置換算法的缺頁次數(shù)各是多少？（注意：所有內(nèi)存塊最初都是空的，凡第一次用到的頁面都都產(chǎn)生一次缺頁）本章作業(yè)1、解釋以下概念：物理地址、邏輯地址、邏輯地址空間、134第5章存儲(chǔ)管理圖5-1內(nèi)存在計(jì)算機(jī)系統(tǒng)中的地位第5章存儲(chǔ)管理圖5-1內(nèi)存在計(jì)算機(jī)系統(tǒng)中的地位1355.1引言5.2分區(qū)法5.5分頁技術(shù)5.6分段技術(shù)5.7段頁式技術(shù)5.8虛擬存儲(chǔ)器5.9請求分頁技術(shù)5.10頁面置換算法本章內(nèi)容提要5.1引言本章內(nèi)容提要1365.1引言

內(nèi)存（MainMemory或PrimaryMemory或RealMemory）也稱主存。指CPU能直接存取指令和數(shù)據(jù)的存儲(chǔ)器，統(tǒng)一編址。5.1引言

內(nèi)存（MainMemory或Pri1375.1.1用戶程序的執(zhí)行圖5-2用戶程序的機(jī)內(nèi)處理過程5.1.1用戶程序的執(zhí)行圖5-2用戶程序的機(jī)內(nèi)處理過1385.1.1用戶程序的主要處理階段1．編輯階段：編輯源代碼。2．編譯階段：源代碼轉(zhuǎn)換為二進(jìn)制指令構(gòu)成的目標(biāo)代碼模塊。3．鏈接階段：將目標(biāo)模塊及所需的庫函數(shù)鏈接形成一個(gè)可執(zhí)行程序。4．裝入階段：將可執(zhí)行程序裝入內(nèi)存某地址空間。5．運(yùn)行階段：從第一條指令開始運(yùn)行程序。

5.1.1用戶程序的主要處理階段1．編輯階段：編輯源代碼139內(nèi)存的使用每個(gè)目標(biāo)模塊指令代碼都以0為基地址順序編址，稱為相對地址或邏輯地址。內(nèi)存中物理存儲(chǔ)單元統(tǒng)一由基地址0開始順序編址，稱為絕對地址或物理地址?？蓤?zhí)行程序各條指令需要進(jìn)行地址轉(zhuǎn)換方能正確執(zhí)行。內(nèi)存的使用每個(gè)目標(biāo)模塊指令代碼都以0為基地址順序編址，稱為相140主存管理功能邏輯地址到物理地址的地址轉(zhuǎn)換內(nèi)存分配和回收存儲(chǔ)保護(hù)內(nèi)存擴(kuò)充(虛擬存儲(chǔ)技術(shù))主存管理功能邏輯地址到物理地址的地址轉(zhuǎn)換1415.1.2重定位

程序邏輯地址的范圍為邏輯地址空間?？蓤?zhí)行程序存放的內(nèi)存存儲(chǔ)單元的范圍為物理地址空間。用戶程序和數(shù)據(jù)裝入內(nèi)存時(shí)，需對目標(biāo)程序中的邏輯地址進(jìn)行修改，把邏輯地址轉(zhuǎn)變?yōu)槲锢淼刂返倪^程稱做地址重定位。5.1.2重定位

程序邏輯地址的范圍為邏輯地址空間。142地址映射LoadA12003456。。1200物理地址空間LoadAdata1data13456源程序LoadA200

34560100200編譯連接邏輯地址空間BA=10001000地址映射1200物理地址空間LoadAdata1源程序L1431．靜態(tài)重定位目標(biāo)程序裝入內(nèi)存時(shí)，由裝入程序?qū)δ繕?biāo)程序中的指令地址、數(shù)據(jù)地址進(jìn)行修改，完成邏輯地址到物理地址的轉(zhuǎn)換。1．靜態(tài)重定位目標(biāo)程序裝入內(nèi)存時(shí)，由裝入程序?qū)δ繕?biāo)程序中的指144圖5-4靜態(tài)重定位示意圖圖5-4靜態(tài)重定位示意圖145靜態(tài)重定位技術(shù)分析優(yōu)點(diǎn)不需要硬件的支持缺點(diǎn)程序必須占用連續(xù)的內(nèi)存空間程序裝入后不能移動(dòng)位置不支持虛擬存儲(chǔ)及其交換技術(shù)進(jìn)程難以共享程序代碼靜態(tài)重定位技術(shù)分析優(yōu)點(diǎn)1462．動(dòng)態(tài)重定位

在每條指令執(zhí)行時(shí)，對所訪問的內(nèi)存進(jìn)行地址重定位。硬件地址轉(zhuǎn)換機(jī)構(gòu)實(shí)現(xiàn)動(dòng)態(tài)重定位。2．動(dòng)態(tài)重定位

在每條指令執(zhí)行時(shí)，對所訪問的內(nèi)存進(jìn)行地址重定147圖5-5動(dòng)態(tài)重定位示意圖圖5-5動(dòng)態(tài)重定位示意圖148動(dòng)態(tài)地址重定位優(yōu)點(diǎn)：程序的內(nèi)存空間動(dòng)態(tài)可變，當(dāng)程序移到另一個(gè)空間時(shí)，修改寄存器BR的值一個(gè)程序不必占用連續(xù)內(nèi)存空間可以部分裝入程序運(yùn)行便于多個(gè)進(jìn)程共享同一個(gè)程序代碼動(dòng)態(tài)地址重定位的代價(jià)：需要硬件的支持。實(shí)現(xiàn)存儲(chǔ)管理的軟件算法較為復(fù)雜。動(dòng)態(tài)地址重定位優(yōu)點(diǎn)：1495.2分區(qū)法

支持多道程序運(yùn)行的一種存儲(chǔ)管理方式。把整個(gè)內(nèi)存劃分為若干大小不等的區(qū)域，操作系統(tǒng)占用一個(gè)區(qū)域，其它區(qū)域供用戶進(jìn)程共享，每個(gè)進(jìn)程占用一個(gè)分區(qū)，這種方法稱為分區(qū)存儲(chǔ)管理。分區(qū)的劃分：固定分區(qū)動(dòng)態(tài)分區(qū)5.2分區(qū)法

支持多道程序運(yùn)行的一種存儲(chǔ)管理方式1505.2.1固定分區(qū)法

內(nèi)存中分區(qū)個(gè)數(shù)、分區(qū)大小固定，每個(gè)分區(qū)裝入一個(gè)進(jìn)程。1．分區(qū)的大小劃分分區(qū)大小有兩種方式：分區(qū)大小相同分區(qū)大小不同5.2.1固定分區(qū)法

內(nèi)存中分區(qū)個(gè)數(shù)、分區(qū)大小固定，每1512．內(nèi)存分配分區(qū)等分方式，進(jìn)程裝入內(nèi)存很簡單。分區(qū)差分方式，有多個(gè)輸入隊(duì)列法和單一輸入隊(duì)列法圖5-6固定分區(qū)內(nèi)存分配2．內(nèi)存分配圖5-6固定分區(qū)內(nèi)存分配1525.2.2動(dòng)態(tài)分區(qū)法1．分區(qū)的分配進(jìn)程進(jìn)入內(nèi)存建立分區(qū)，大小適應(yīng)進(jìn)程的需要。這種技術(shù)稱為動(dòng)態(tài)分區(qū)法。2．?dāng)?shù)據(jù)結(jié)構(gòu)（1）空閑分區(qū)表存放（2）空閑分區(qū)鏈存放5.2.2動(dòng)態(tài)分區(qū)法1．分區(qū)的分配153圖5-7MVT的內(nèi)存分配和進(jìn)程調(diào)度情況圖5-7MVT的內(nèi)存分配和進(jìn)程調(diào)度情況1543．動(dòng)態(tài)分區(qū)分配算法（1）最先適應(yīng)算法空閑表按內(nèi)存地址順序排列（2）最佳（壞）適應(yīng)算法空閑表按空閑塊大小的增量形式排列（3）循環(huán)適應(yīng)算法最先適應(yīng)算法的變種。從上次找到的可用分區(qū)的下一個(gè)空閑分區(qū)開始查找，順序選擇滿足要求的第一個(gè)空閑分區(qū)。3．動(dòng)態(tài)分區(qū)分配算法（1）最先適應(yīng)算法1555.3可重定位分區(qū)分配

5.3.1碎片問題內(nèi)存中尺寸太小、無法利用的小分區(qū)稱做“碎片”。固定分區(qū)法會(huì)產(chǎn)生內(nèi)部碎片。動(dòng)態(tài)分區(qū)會(huì)產(chǎn)生外部碎片.5.3可重定位分區(qū)分配

5.3.1碎片問題156圖5-9分配16KB內(nèi)存塊之前和之后的內(nèi)存配置圖5-9分配16KB內(nèi)存塊之前和之后的內(nèi)存配置1575.3.1碎片問題緊縮的時(shí)機(jī)進(jìn)程結(jié)束、釋放所占用的分區(qū)時(shí)（空閑區(qū)有可能相鄰）在分配進(jìn)程的分區(qū)時(shí)（空閑區(qū)有可能不夠）5.3.1碎片問題緊縮的時(shí)機(jī)1585.3.2緊縮

移動(dòng)某些已分配區(qū)，使所有進(jìn)程的分區(qū)緊鄰的技術(shù)。圖5-10可重定位分區(qū)的緊縮5.3.2緊縮

移動(dòng)某些已分配區(qū)，使所有進(jìn)程的分區(qū)緊鄰的1595.3.3動(dòng)態(tài)重定位的實(shí)現(xiàn)動(dòng)態(tài)重定位經(jīng)常用硬件實(shí)現(xiàn)硬件支持基址寄存器限長寄存器5.3.3動(dòng)態(tài)重定位的實(shí)現(xiàn)動(dòng)態(tài)重定位經(jīng)常用硬件實(shí)現(xiàn)160圖5-11動(dòng)態(tài)重定位的實(shí)現(xiàn)過程圖5-11動(dòng)態(tài)重定位的實(shí)現(xiàn)過程1615.3.4可重定位分區(qū)法優(yōu)缺點(diǎn)優(yōu)點(diǎn)可以消除碎片，能夠分配更多的分區(qū)，有助于多道程序設(shè)計(jì)，提高內(nèi)存的利用率。缺點(diǎn)緊縮技術(shù)花費(fèi)CPU時(shí)間當(dāng)進(jìn)程大于整個(gè)空閑區(qū)無法裝入時(shí)，仍要浪費(fèi)一定的內(nèi)存進(jìn)程的存儲(chǔ)區(qū)內(nèi)可能放有從未使用的信息進(jìn)程之間無法對信息共享5.3.4可重定位分區(qū)法優(yōu)缺點(diǎn)優(yōu)點(diǎn)1625.4對換技術(shù)

圖5-12對換兩個(gè)進(jìn)程當(dāng)內(nèi)存不足時(shí)，將暫時(shí)不運(yùn)行的進(jìn)程換到外存，將需要馬上運(yùn)行的進(jìn)程調(diào)入內(nèi)存。5.4對換技術(shù)

圖5-12對換兩個(gè)進(jìn)程當(dāng)內(nèi)存不163圖5-13多道程序?qū)Q技術(shù)示例圖5-13多道程序?qū)Q技術(shù)示例1645.5分頁技術(shù)

5.5.1分頁存儲(chǔ)管理的基本概念 把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁（page）。從0開始編制頁號(hào)，頁內(nèi)地址從0開始編址。（1）邏輯地址空間——分頁（2）內(nèi)存地址空間——分塊頁（或塊）大小由硬件（系統(tǒng)）確定5.5分頁技術(shù)

5.5.1分頁存儲(chǔ)管理的基本概165（3）邏輯地址表示圖5-14分頁技術(shù)的地址結(jié)構(gòu)邏輯地址為A，頁面大小為L，頁號(hào)p和頁內(nèi)地址d可按下式求得：p=INT[A/L]，d=[A]MODL（3）邏輯地址表示圖5-14分頁技術(shù)的地址結(jié)構(gòu)邏輯地址為166以塊為單位分配內(nèi)存進(jìn)程每個(gè)頁面對應(yīng)一個(gè)內(nèi)存塊一個(gè)進(jìn)程頁面可以裝入物理上不連續(xù)的內(nèi)存塊頁表記錄分配結(jié)果（4）內(nèi)存分配原則以塊為單位分配內(nèi)存（4）內(nèi)存分配原則167（5）頁表——從頁號(hào)到物理塊號(hào)的地址映射圖5-15分頁存儲(chǔ)管理系統(tǒng)（5）頁表——從頁號(hào)到物理塊號(hào)的地址映射圖5-15分頁存168內(nèi)存塊表記錄內(nèi)存使用情況每個(gè)內(nèi)存塊在內(nèi)存塊表中占一項(xiàng)，記錄該塊的狀態(tài)：空閑/分配。（6）內(nèi)存塊表內(nèi)存塊表記錄內(nèi)存使用情況（6）內(nèi)存塊表1695.5.2分頁系統(tǒng)中的地址映射圖5-16分頁系統(tǒng)的地址轉(zhuǎn)換機(jī)構(gòu)每個(gè)進(jìn)程平均有半個(gè)頁面的內(nèi)部碎片5.5.2分頁系統(tǒng)中的地址映射圖5-16分頁系統(tǒng)的地170設(shè)進(jìn)程平均大小為s字節(jié)，每個(gè)頁表項(xiàng)占e字節(jié)。每個(gè)進(jìn)程需要的頁數(shù)為s/p每個(gè)進(jìn)程的頁表空間：e*s/p字節(jié)每個(gè)進(jìn)程內(nèi)部碎片平均為p/2頁表和內(nèi)部碎片帶來的總開銷是：e*s/p+p/2令該表達(dá)式的值最小，對p求導(dǎo)，令其等于0，得到方程：-e*s/p2+1/2=0得出最佳頁面尺寸公式，僅考慮上述兩個(gè)因素：5.5.3頁面尺寸p的討論如果s=1MB，e=8B，則最佳頁面尺寸p是4KB設(shè)進(jìn)程平均大小為s字節(jié)，每個(gè)頁表項(xiàng)占e字節(jié)。5.5.3頁1715.5.4硬件支持

將頁表保存在內(nèi)存中，由一個(gè)頁表基址寄存器PTBR指向該頁表。整個(gè)系統(tǒng)只有一個(gè)PTBR。內(nèi)存存取速度下降50%！5.5.4硬件支持

將頁表保存在內(nèi)存中，由一個(gè)頁表基址寄172把頁表放在一組快速存儲(chǔ)器中（Cache），加快訪問內(nèi)存的速度?？焖俅鎯?chǔ)器組成的頁表稱為快表，內(nèi)存中的頁表稱為慢表?？毂碛址Q相聯(lián)存儲(chǔ)器（associativememory）

或TLB（Translationlookasidebuffers）轉(zhuǎn)換檢測緩沖區(qū)。把頁表放在一組快速存儲(chǔ)器中（Cache），加快訪問內(nèi)存的速度173快表（或TranslationLookasideBuffer，TLB）快表每項(xiàng)包括鍵號(hào)和值兩部分鍵號(hào)是當(dāng)前進(jìn)程正在使用的某個(gè)頁面號(hào)值是該頁面所對應(yīng)的物理塊號(hào)快表（或TranslationLookasideBuff174快表性能分析示例如果訪問聯(lián)想存儲(chǔ)器的時(shí)間為20ns，訪問內(nèi)存的時(shí)間是100ns，假定訪問聯(lián)想存儲(chǔ)器的命中率分別為0%，50%，80%，90%，98%，下表列出需要的訪問時(shí)間：命中率%平均訪問時(shí)間：T=h*120+（1-h）*2200T=22050T=17080T=14090T=13098T=122快表性能分析示例如果訪問聯(lián)想存儲(chǔ)器的時(shí)間為20ns，訪問內(nèi)存175圖5-17利用快表實(shí)現(xiàn)地址轉(zhuǎn)換圖5-17利用快表實(shí)現(xiàn)地址轉(zhuǎn)換1765.5.5保護(hù)方式

（1）利用頁表本身進(jìn)行保護(hù)：保護(hù)頁表基址和頁表長度（2）設(shè)置存取控制位：一個(gè)頁表項(xiàng)，權(quán)限包括：（R/W/RW），出錯(cuò)發(fā)中斷。（3）設(shè)置合法標(biāo)志5.5.5保護(hù)方式

（1）利用頁表本身進(jìn)行保護(hù)：保護(hù)頁表1775.5.6頁表的構(gòu)造1．多級(jí)頁表 大邏輯地址空間，頁表項(xiàng)太多。假定： 邏輯地址空間：232～264一個(gè)進(jìn)程的邏輯空間占32位，頁面大小為4kb 最大進(jìn)程可有220（1M）個(gè)邏輯頁 頁表表項(xiàng)達(dá)220個(gè)。

?方案：利用兩級(jí)頁表——給頁表分頁。5.5.6頁表的構(gòu)造1．多級(jí)頁表178圖5-18兩級(jí)頁表地址結(jié)構(gòu)圖5-18兩級(jí)頁表地址結(jié)構(gòu)179圖5-19兩級(jí)頁表結(jié)構(gòu)1023圖5-19兩級(jí)頁表結(jié)構(gòu)1023180圖5-20兩級(jí)頁表結(jié)構(gòu)的地址轉(zhuǎn)換圖5-20兩級(jí)頁表結(jié)構(gòu)的地址轉(zhuǎn)換181圖5-21三級(jí)頁表地址結(jié)構(gòu)圖5-21三級(jí)頁表地址結(jié)構(gòu)182三級(jí)頁表結(jié)構(gòu)及其地址映射過程三級(jí)頁表結(jié)構(gòu)及其地址映射過程1832．散列頁表HashedPageTable以頁號(hào)作為參數(shù)形成散列值散列表中每一項(xiàng)具有相同散列值，是一個(gè)鏈表。每個(gè)鏈表元素由頁號(hào)、對應(yīng)的內(nèi)存塊號(hào)、指向鏈表中下個(gè)元素的指針組成。2．散列頁表HashedPageTable184圖5-22散列頁表圖5-22散列頁表1853．倒置頁表進(jìn)程頁表以邏輯地址的順序排序，虛地址空間較大。倒置頁表按內(nèi)存塊號(hào)排序，每個(gè)內(nèi)存塊占有一個(gè)表項(xiàng)。每個(gè)表項(xiàng)包括存放在該內(nèi)存塊中頁號(hào)和擁有該頁面的進(jìn)程標(biāo)識(shí)符。系統(tǒng)只有一個(gè)頁表。3．倒置頁表進(jìn)程頁表以邏輯地址的順序排序，虛地址空間較大。186圖5-23倒置頁表圖5-23倒置頁表1875.5.7頁面共享圖5-24頁面共享可再入代碼（或純碼，在其執(zhí)行過程中本身不做任何修改的代碼，通常由指令和常數(shù)組成）。5.5.7頁面共享圖5-24頁面共享可再入代碼（或純188分頁式管理可實(shí)現(xiàn)頁面共享?xiàng)l件：共享部分是純碼程序共享部分與非共享部分，分頁單獨(dú)存放共享部分的邏輯頁號(hào)、物理頁號(hào)完全相同分頁式管理可實(shí)現(xiàn)頁面共享?xiàng)l件：189分頁技術(shù)總結(jié)優(yōu)點(diǎn)：解決了碎片問題，便于管理缺點(diǎn)：實(shí)現(xiàn)共享有條件不便于動(dòng)態(tài)連接未考慮程序邏輯構(gòu)成分頁技術(shù)總結(jié)優(yōu)點(diǎn)：解決了碎片問題，便于管理190設(shè)頁長為1K，程序地址字長為16位，用戶程序空間和頁表如圖： 設(shè)頁長為1K，程序地址字長為16位，用戶程序空間和頁表如圖：191執(zhí)行指令MOVr1，[2500]，地址轉(zhuǎn)換步驟說明取出程序地址字2500送虛地址寄存器VR由硬件分離頁號(hào)P和頁內(nèi)地址W：頁長為1K，所以頁內(nèi)地址占10位（0~9位），頁號(hào)占6位（10~15位）硬件取出VR寄存器中的高6位即頁號(hào)，低10位即頁內(nèi)地址，得到頁號(hào)P=2，頁內(nèi)位移W=452根據(jù)頁號(hào)P=2，硬件自動(dòng)查該進(jìn)程頁表，找到第2頁對應(yīng)塊號(hào)為7，將塊號(hào)送到內(nèi)存地址寄存器MR的高10位中，將VR中W值452復(fù)制到MR低10位中，形成內(nèi)存地址。系統(tǒng)就以MR中的地址訪問內(nèi)存執(zhí)行指令MOVr1，[2500]，地址轉(zhuǎn)換步驟說明192計(jì)算分頁地址時(shí)要注意： 給出地址字的進(jìn)制 地址的空間長度 頁長 邏輯空間允許的最大頁數(shù)計(jì)算分頁地址時(shí)要注意：1935.6分段技術(shù)5.6.1分段存儲(chǔ)管理的基本概念分頁存儲(chǔ)管理存在問題——導(dǎo)致程序在用戶角度的內(nèi)存空間和實(shí)際內(nèi)存空間不同。子程序符號(hào)表主函數(shù)庫函數(shù)堆棧用戶角度的內(nèi)存5.6分段技術(shù)5.6.1分段存儲(chǔ)管理的基本概念194段（segmentation）用戶角度的內(nèi)存管理模式,邏輯地址空間是段的集合當(dāng)用戶程序被編譯時(shí)，編譯程序自動(dòng)構(gòu)建程序的分段，比如：pascal編譯器全局量過程堆?？蓤?zhí)行代碼局部變量段（segmentation）用戶角度的內(nèi)存管理模式,邏輯地1951．分段按程序自身的邏輯關(guān)系劃分為若干個(gè)程序段段名段長段號(hào)：段號(hào)從0開始排段內(nèi)地址：從0開始編址，段內(nèi)地址連續(xù)1．分段按程序自身的邏輯關(guān)系劃分為若干個(gè)程序段196圖5-25分段地址空間段號(hào)段長08k15k26k35k圖5-25分段地址空間段號(hào)段長08k15k26k35k1972．分段程序的邏輯地址

邏輯地址：段號(hào)s+段內(nèi)地址d。分段存儲(chǔ)，進(jìn)程邏輯地址空間是二維的。圖5-26分段技術(shù)地址結(jié)構(gòu)2．分段程序的邏輯地址

邏輯地址：段號(hào)s+段內(nèi)地址d。198段號(hào)（8bit）段內(nèi)地址（16bit）0000，00000000，……,00000000，00001111，……,11110000，00010000，……,00000000，00011111，……,1111……，……，1111，11110000，……,00001111，11111111，……,1111段號(hào)（8bit）段內(nèi)地址（16bit）0000，0000001993．內(nèi)存分配

內(nèi)存以段為單位分配，每段占用一塊連續(xù)的內(nèi)存分區(qū)。各分區(qū)的大小由對應(yīng)段的大小決定。最大段長（分區(qū)大?。┳疃喽螖?shù)（一個(gè)進(jìn)程擁有最多分區(qū)數(shù)）3．內(nèi)存分配

內(nèi)存以段為單位分配，每段占用一塊連續(xù)的內(nèi)存分區(qū)2004．段地址映射段表系統(tǒng)為每個(gè)進(jìn)程建一個(gè)段表。每個(gè)段是段表的一項(xiàng)，段表項(xiàng)中包含段號(hào)、段長和段起始地址。段表基址寄存器系統(tǒng)建立一個(gè)段表地址寄存器（段表首址+段表長度）。4．段地址映射段表201.....40S30N20L10P00K邏輯段號(hào)01234作業(yè)1的地址空間10003200500060008000PKSLN主存k3200p1500l6000n8000s5000段長段地址01234操作系統(tǒng)40S30N20L10P00K邏輯段號(hào)01234作202段號(hào)（8bit）段內(nèi)地址（16bit）0000，00100000，0000，0000，0111該段基址：6000=（1，0111，0111，0000）2基址加段內(nèi)位移量0001，0111，0111，00000000，0000，0000，01110001，0111，0111，0111（得：物理地址）（6007）邏輯地址：第2段，第7個(gè)字節(jié)段號(hào)（8bit）段內(nèi)地址（16bit）0000，001000203圖5-27分段地址轉(zhuǎn)換5.6.2地址轉(zhuǎn)換圖5-27分段地址轉(zhuǎn)換5.6.2地址轉(zhuǎn)換2045.6.3段的共享和保護(hù)

1．段的共享在段一級(jí)實(shí)現(xiàn)，共享信息可以設(shè)成一段。可以只共享部分程序。5.6.3段的共享和保護(hù)

1．段的共享205圖5-28分段系統(tǒng)中段的共享圖5-28分段系統(tǒng)中段的共享2062．段的保護(hù)

段的保護(hù)措施包括以下三種：①存取控制（R/W/RW）②段表本身可起保護(hù)作用。表項(xiàng)中設(shè)置該段的長度限制段長限制，段表地址寄存器中有段表長度的信息。③保護(hù)環(huán)（進(jìn)程優(yōu)先權(quán)由所在環(huán)決定）2．段的保護(hù)

段的保護(hù)措施包括以下三種：2075．分頁和分段的主要區(qū)別

①頁是信息的物理單位。段是信息的邏輯單位。②頁大小由系統(tǒng)確定，段長因段而異。③分頁地址空間是一維的。分段的地址空間是二維的。④分頁系統(tǒng)很難實(shí)現(xiàn)過程和數(shù)據(jù)的分離。分段系統(tǒng)可以。

各段長度不一，難以統(tǒng)一管理。 ——引入段頁式管理5．分頁和分段的主要區(qū)別

①頁是信息的物理單位。段是信息的2085.7段頁式技術(shù)

5.7.1段頁式存儲(chǔ)管理的基本原理圖5-29段頁式存儲(chǔ)邏輯地址結(jié)構(gòu)5.7段頁式技術(shù)

5.7.1段頁式存儲(chǔ)管理的基本原理2095.7.2段頁式地址轉(zhuǎn)換過程

段號(hào)加段表寄存器中的段表首址該段頁表首址+頁表長度頁表長度比較越界發(fā)中斷，取頁號(hào)加頁表基址對應(yīng)頁號(hào)項(xiàng)，讀出頁表中的物理塊號(hào)物理塊號(hào)與頁內(nèi)地址合成物理地址(如不在內(nèi)存發(fā)缺頁中斷，重新更新頁表)進(jìn)行讀寫。5.7.2段頁式地址轉(zhuǎn)換過程

段號(hào)加段表寄存器中的段表首址210操作系統(tǒng)(第2版)孟慶昌牛欣源編著課件第五章存儲(chǔ)管理2115.8虛擬存儲(chǔ)器5.8.1虛擬存儲(chǔ)器的概念進(jìn)程部分裝入內(nèi)存的依據(jù)程序含有不執(zhí)行代碼段程序某些選項(xiàng)和路徑很少使用程序執(zhí)行呈現(xiàn)局部性原理部分調(diào)入內(nèi)存的好處用戶編制程序時(shí)不必考慮內(nèi)存容量的限制在容量有限的內(nèi)存中，可同時(shí)裝入更多的進(jìn)程5.8虛擬存儲(chǔ)器5.8.1虛擬存儲(chǔ)器的概念212虛存下的編程地址空間指令操作數(shù)中地址的二進(jìn)制位數(shù)磁盤中對換區(qū)的大小虛存下的編程地址空間指令操作數(shù)中地址的二進(jìn)制位數(shù)2135.8.2虛擬存儲(chǔ)器的特征虛擬擴(kuò)充部分裝入內(nèi)存分配不連續(xù)進(jìn)程執(zhí)行中多次對換5.8.2虛擬存儲(chǔ)器的特征2145.9請求分頁技術(shù)5.9.1請求分頁存儲(chǔ)管理的基本思想按照分頁管理提供虛擬存儲(chǔ)器。一個(gè)進(jìn)程的起始頁面在內(nèi)存就可執(zhí)行；繼續(xù)執(zhí)行的頁面不在內(nèi)存，則動(dòng)態(tài)換入內(nèi)存。頁表項(xiàng)增加一個(gè)字段—標(biāo)志位，標(biāo)示進(jìn)程該頁面是否已在內(nèi)存。5.9請求分頁技術(shù)5.9.1請求分頁存儲(chǔ)管理的基本思2155.9.2硬件支持及缺頁處理

1．頁表機(jī)制頁表項(xiàng)通常包含下列5種信息：5.9.2硬件支持及缺頁處理

1．頁表機(jī)制216①內(nèi)存塊號(hào)②標(biāo)志位 該位是1，表示該表項(xiàng)有效，該頁在內(nèi)存， 可以使用。 該位是0，表示該表項(xiàng)對應(yīng)的頁面不在內(nèi)存，訪問該頁置缺頁中斷③保護(hù)位（讀寫權(quán)限）④修改位/引用位。記錄該頁的狀態(tài)。⑤禁止緩存位。該位用于禁止該頁被緩存。①內(nèi)存塊號(hào)217XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K虛地址空間物理地址空間}虛頁塊號(hào)虛存頁表XXXX7X5XXX34061260K-64K56K-60K218虛擬存儲(chǔ)的地址映射查詢頁表項(xiàng)及中斷駐留位在內(nèi)存，可訪問，進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換不在內(nèi)存，發(fā)缺頁中斷，調(diào)入所需頁面，進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換按物理地址訪問該頁內(nèi)存。虛擬存儲(chǔ)的地址映射查詢頁表項(xiàng)及中斷駐留位219148400000000000000001111000010110000000000000111100100011101001101011513121110976532100010000000000100110000000000100110在/不在內(nèi)存虛存頁表虛地址8196物理地址245800148400000000000000001111002205.9.3請求分頁技術(shù)的性能

令p表示缺頁中斷的概率（0≤p≤1），簡稱缺頁率，等于缺頁次數(shù)與全部訪問內(nèi)存次數(shù)之比。虛存有效存取時(shí)間表示為： (1-p)×ma+p×缺頁處理時(shí)間5.9.3請求分頁技術(shù)的性能

令p表示缺頁中斷的概率（02212．缺頁中斷機(jī)構(gòu)

圖5-34指令執(zhí)行步驟與缺頁中斷處理過程2．缺頁中斷機(jī)構(gòu)

圖5-34指令執(zhí)行步驟與缺頁中斷處理過222進(jìn)程A缺頁處理過程進(jìn)程A遇到缺頁指令，捕俘進(jìn)入操作系統(tǒng)。保存進(jìn)程A的各個(gè)寄存器和進(jìn)程狀態(tài)信息。檢查該頁的訪問合法性，并確定該頁在磁盤上的地址，把該頁從盤上讀到空閑內(nèi)存塊中。在等待盤I/O完成時(shí)，把CPU分給其他進(jìn)程盤I/O完成，發(fā)出盤中斷。保存進(jìn)程B的用戶寄存器和進(jìn)程狀態(tài)。確定該中斷來自磁盤。調(diào)整頁表，標(biāo)明所需頁已放入內(nèi)存。進(jìn)程A就緒，等待分配CPU。調(diào)度進(jìn)程A，則恢復(fù)它的各寄存器、進(jìn)程狀態(tài)和新的頁表，然后重新執(zhí)行前面被中斷的指令。進(jìn)程A缺頁處理過程進(jìn)程A遇到缺頁指令，捕俘進(jìn)入操作系統(tǒng)。223①處理缺頁中斷的時(shí)間②從磁盤調(diào)入該頁的時(shí)間③重新啟動(dòng)該進(jìn)程的時(shí)間處理缺頁中斷花費(fèi)的時(shí)間處理缺頁中斷花費(fèi)的時(shí)間224從磁盤調(diào)入該頁的時(shí)間包括磁盤尋道時(shí)間（即磁頭從當(dāng)前磁道移至指定磁道所用的時(shí)間）旋轉(zhuǎn)延遲時(shí)間（即磁頭從當(dāng)前位置落到指定扇區(qū)開頭所用的時(shí)間）數(shù)據(jù)傳輸時(shí)間從磁盤調(diào)入該頁的時(shí)間包括225有效存取時(shí)間T磁盤旋轉(zhuǎn)延遲時(shí)間約為8ms，尋道時(shí)間約為15ms，傳輸時(shí)間是1ms，全部換頁時(shí)間約25ms。平均缺頁服務(wù)時(shí)間取25ms，內(nèi)存存取時(shí)間取100ns，則T=(1-p)×100+p×25000000=100+24999900×p有效存取時(shí)間T磁盤旋轉(zhuǎn)延遲時(shí)間約為8ms，尋道時(shí)間約為15226有效存取時(shí)間T=110ns時(shí)則有：100+25000000×p=11025000000×p=10p=0.0000004（0.00004%）表明：缺頁率=0.00004%有效內(nèi)存讀寫時(shí)間為110ns有效存取時(shí)間T=110ns時(shí)則有：2275.10頁面置換算法

5.10.1頁面置換1．頁面置換過程5.10頁面置換算法

5.10.1頁面置換2282．頁面走向用戶程序的存儲(chǔ)訪問的頁號(hào)順序構(gòu)成的序列稱為頁面走向。2．頁面走向229頁面走向示例 對于給定的頁面大小，僅考慮其頁號(hào)，不關(guān)心完整的地址。 如果當(dāng)前對頁面p進(jìn)行了訪問，那么，馬上又對該頁訪問就不會(huì)缺頁。例如程序訪問的地址順序如下：0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105若每頁100個(gè)字節(jié)，則前兩位就是頁號(hào)。頁面走向簡化為：1，4，1，6，1，6，1，6，1，6，1頁面走向示例 對于給定的頁面大小，僅考慮其頁號(hào)，不關(guān)心完整230一般來說，隨著可用塊數(shù)的增加，缺頁數(shù)將減少。圖5-36缺頁量與內(nèi)存塊數(shù)關(guān)系圖一般來說，隨著可用塊數(shù)的增加，缺頁數(shù)將減少。圖5-36缺231常用頁面置換算法請求內(nèi)存管理技術(shù)在實(shí)現(xiàn)缺頁中斷時(shí)需要決定將內(nèi)存中的那些頁面調(diào)出內(nèi)存——稱為頁面淘汰算法(中級(jí)調(diào)度)統(tǒng)一采用下述頁面走向：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1并且假定用戶程序只有三個(gè)內(nèi)存塊可供使用?？疾煸诔绦驁?zhí)行的整個(gè)過程中，一共發(fā)生多少次缺頁中斷。常用頁面置換算法請求內(nèi)存管理技術(shù)在實(shí)現(xiàn)缺頁中斷時(shí)需要決定將內(nèi)2325.10.2先進(jìn)先出法（FIFO）先進(jìn)入內(nèi)存的頁，先被換出。