第4章-存儲(chǔ)器管理最終-2012級(jí)用

第四章

存儲(chǔ)器管理4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁存儲(chǔ)管理方式4.4基本分段存儲(chǔ)管理方式4.5虛擬存儲(chǔ)器的基本概念4.6請(qǐng)求分頁存儲(chǔ)管理方式4.7頁面置換算法1用戶程序的主要處理階段連續(xù)分配方式虛擬存儲(chǔ)器的基本特征分頁、分段存儲(chǔ)管理技術(shù)

第四章

存儲(chǔ)器管理2存儲(chǔ)管理的功能內(nèi)存分配——為每個(gè)進(jìn)程分配一定的內(nèi)存空間地址映射——把程序中所用的相對(duì)地址轉(zhuǎn)換成內(nèi)存的物理地址內(nèi)存保護(hù)——檢查地址的合法性，防止越界訪問內(nèi)存擴(kuò)充——解決“求大于供”的問題，采用虛擬存儲(chǔ)技術(shù)3第一節(jié)

存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器管理的功能41、

存儲(chǔ)器的層次結(jié)構(gòu)在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，存儲(chǔ)器是信息管理的來源與歸宿，占據(jù)重要位置。但是，在現(xiàn)有技術(shù)條件下，任何一種存儲(chǔ)裝置，都無法同時(shí)從速度與容量兩方面，滿足用戶的需求。實(shí)際上它們組成了一個(gè)速度由快到慢，容量由小到大的存儲(chǔ)裝置層次。寄存器高速緩存主存儲(chǔ)器磁盤緩存固定磁盤可移動(dòng)存儲(chǔ)介質(zhì)cpu寄存器主存輔存51、

存儲(chǔ)器的層次結(jié)構(gòu)寄存器：

容量最小、速度最快、最貴、易變的高速緩存Cache：少量的、非?？焖?、昂貴、易變的內(nèi)存RAM：若干兆字節(jié)、中等速度、中等價(jià)格、易變的磁盤：數(shù)百兆或數(shù)千兆字節(jié)、低速、價(jià)廉、不易變的內(nèi)存空間一般分為兩部分：系統(tǒng)區(qū)和用戶區(qū)操作系統(tǒng)等系統(tǒng)軟件占用系統(tǒng)區(qū)，用戶區(qū)用來存放用戶程序，存儲(chǔ)管理主要是針對(duì)內(nèi)存用戶區(qū)的管理。62、

存儲(chǔ)器管理的功能地址變換內(nèi)存的分配與回收內(nèi)存的保護(hù)與共享內(nèi)存的擴(kuò)充7第二節(jié)

程序的裝入和鏈接從源程序到程序執(zhí)行基本概念程序的裝入程序的鏈接8第二節(jié)

程序的裝入和鏈接

從用戶的源程序進(jìn)入系統(tǒng)到相應(yīng)程序在機(jī)器上運(yùn)行，所經(jīng)歷的主要處理階段有

，

，

和

。

編譯階段鏈接階段裝入階段運(yùn)行階段91、從源程序到程序執(zhí)行編譯：編譯程序由編譯程序（Compiler）將用戶源代碼編譯成若干個(gè)目標(biāo)模塊。鏈接：鏈接程序由鏈接程序（Linker）將編譯后形成的一組目標(biāo)模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊。裝入：裝入程序*由裝入程序（Loader）將裝入模塊復(fù)制到內(nèi)存中。10庫匯編編譯主子1子2目標(biāo)模塊鏈接程序裝入模塊庫主子1子2裝入程序內(nèi)存庫主子1子2112、基本概念名空間：程序中由自定義的符號(hào)名構(gòu)成的集合。地址空間：程序中用來訪問信息所用地址單元的集合。其中的地址被稱為邏輯地址（相對(duì)地址/程序地址/虛地址）,通常是以0為基址進(jìn)行順序編址。(程序員關(guān)心的問題)存儲(chǔ)空間：物理存儲(chǔ)器中全部物理存儲(chǔ)單元的集合。每個(gè)存儲(chǔ)單元都有它自己的編號(hào)，該編號(hào)被稱為物理地址（絕對(duì)地址/內(nèi)存地址/實(shí)地址）。一個(gè)程序只有從地址空間裝入到存儲(chǔ)空間后才能運(yùn)行。12裝入地址映射BR=1000LoadA,2003456

。

。

。1200內(nèi)存空間LoadA,data1data13456名空間LoadA,20034560100200編譯鏈接地址空間源程序目標(biāo)程序運(yùn)行程序13LOAD1,50012345LOAD1,5001234501005007005000510055005700程序A的地址空間程序A的內(nèi)存空間..................143、程序的裝入裝入就是把鏈接好的裝入模塊裝入“內(nèi)存”。裝入方式絕對(duì)裝入：裝入位置是固定的，由程序員直接編址或由匯編、編譯程序給出地址，即按邏輯地址(=物理地址)裝入內(nèi)存。(只適用于單道系統(tǒng))可重定位裝入：即靜態(tài)重定位動(dòng)態(tài)運(yùn)行時(shí)裝入：即動(dòng)態(tài)重定位15絕對(duì)裝入方式邏輯地址與實(shí)際地址相同要求程序員熟悉內(nèi)存的使用情況通常在程序中采用符號(hào)地址16可重定位裝入方式目標(biāo)模塊從0編址，其它地址相對(duì)于起始地址計(jì)算重定位（地址映射）：由于作業(yè)裝入到與其地址空間不一致的存儲(chǔ)空間所引起的對(duì)地址變換的過程。邏輯地址變換為物理地址。17作業(yè)地址空間內(nèi)存空間裝入365LOAD1,25005000250001000365LOAD1,250015000125001000011000365LOAD1,1250015000125001000011000靜態(tài)重定位18動(dòng)態(tài)運(yùn)行時(shí)裝入方式在程序執(zhí)行時(shí)將相對(duì)地址轉(zhuǎn)換成為絕對(duì)地址允許程序在內(nèi)存中移動(dòng)19VR：邏輯地址寄存器BR：重定位寄存器動(dòng)態(tài)重定位

LoadA,500123455001000

LoadA,50012345作業(yè)地址空間

內(nèi)存空間BR+0100500VR100011001500204、程序的鏈接鏈接：將經(jīng)過編譯或匯編后所得到的一組目標(biāo)模塊及所需的庫函數(shù)裝配成一個(gè)完整的裝入模塊的過程。具體工作：對(duì)相對(duì)地址進(jìn)行修改變換外部調(diào)用符號(hào)鏈接方式：靜態(tài)鏈接：程序執(zhí)行前鏈接裝入時(shí)動(dòng)態(tài)鏈接：便于修改和更新；便于共享。運(yùn)行時(shí)動(dòng)態(tài)鏈接：最小化快速裝入，節(jié)省內(nèi)存。21靜態(tài)鏈接執(zhí)行前將目標(biāo)模塊和他們的庫函數(shù)，連接成一個(gè)完整的裝入模塊。兩個(gè)問題：對(duì)相對(duì)地址修改變換外部調(diào)用符號(hào)22模塊ACallB;Return;0L-1模塊BCallC;Return;0M-1模塊C……Return;0N-1鏈接模塊AJSR“L”;Return;0L-1模塊BJSR“L+M”;Return;LL+M-1模塊C……Return;L+ML+M+N-1裝入模塊目標(biāo)模塊232.裝入時(shí)動(dòng)態(tài)鏈接

鏈接在裝入時(shí)進(jìn)行，即在裝入一個(gè)模塊時(shí)，若發(fā)生一個(gè)外部模塊調(diào)用事件，則由裝入程序去找出相應(yīng)的外部模塊，將它裝入內(nèi)存，并把它鏈接到調(diào)用模塊上去這種鏈接方式的優(yōu)點(diǎn)是便于對(duì)程序模塊進(jìn)行修改和更新，并且可以對(duì)目標(biāo)模塊實(shí)現(xiàn)共享，以提高內(nèi)存和外存的利用率。243.運(yùn)行時(shí)動(dòng)態(tài)鏈接

將對(duì)某些模塊的鏈接推遲到執(zhí)行時(shí)才執(zhí)行，亦即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。25第三節(jié)

連續(xù)分配方式

為用戶程序分配一個(gè)連續(xù)的內(nèi)存空間，曾被廣泛應(yīng)用，且現(xiàn)在仍被采用。單一連續(xù)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配可重定位分區(qū)分配261、單一連續(xù)分配基本思想把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)供OS使用，通常放在低址部分；系統(tǒng)區(qū)以外的全部內(nèi)存空間是用戶區(qū)。在內(nèi)存中僅駐留一道程序，整個(gè)用戶區(qū)為一用戶獨(dú)占。特點(diǎn)方法簡(jiǎn)單，對(duì)硬件要求低，易于實(shí)現(xiàn)；很難實(shí)現(xiàn)共享內(nèi)存和CPU利用率低，只能用于單用戶單任務(wù)OS；實(shí)例CP/M，MS-DOS，嵌入式系統(tǒng)27單一連續(xù)分配DOS內(nèi)存分區(qū)CP/M內(nèi)存分區(qū)系統(tǒng)參數(shù)區(qū)BIOSCCPBDOS系統(tǒng)區(qū)系統(tǒng)區(qū)282、固定分區(qū)分配把內(nèi)存劃分為若干個(gè)固定大小的連續(xù)分區(qū)；最簡(jiǎn)單的一種可運(yùn)行多道程序的存儲(chǔ)管理方式。劃分分區(qū)的方法分區(qū)大小相等：缺乏靈活性，用于控制多個(gè)相同對(duì)象的系統(tǒng)（群控系統(tǒng)）分區(qū)大小不等：多個(gè)較小分區(qū)、適量中等分區(qū)、少量大分區(qū)內(nèi)存分配管理將分區(qū)按大小排隊(duì)建立分區(qū)說明表—分區(qū)號(hào)、起址、大小、狀態(tài)程序裝入時(shí)，由內(nèi)存分配程序檢索分區(qū)說明表，找到符合要求的分區(qū)，并進(jìn)行標(biāo)記。29分區(qū)號(hào)大小(k)起址(k)狀態(tài)11220已分配232已分配364

已分配4128已分配30分區(qū)號(hào)大小(k)起址(k)狀態(tài)11220已分配23232已分配364

已分配4128已分配31分區(qū)號(hào)大小(k)起址(k)狀態(tài)11220已分配23232已分配36464已分配4128已分配32分區(qū)號(hào)大小(k)起址(k)狀態(tài)11220已分配23232已分配36464已分配4128128已分配33分區(qū)號(hào)大小起址狀態(tài)18K512K未使用232K520K未使用332K552K未使用4128K584K未使用5512K712K未使用…………系統(tǒng)區(qū)分區(qū)1分區(qū)4分區(qū)5分區(qū)2分區(qū)3系統(tǒng)區(qū)分區(qū)1分區(qū)4分區(qū)5分區(qū)2分區(qū)3作業(yè)1作業(yè)2作業(yè)3已使用已使用已使用作業(yè)1進(jìn)入，大小30K作業(yè)2進(jìn)入，大小500K作業(yè)3進(jìn)入，大小8K優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開銷小。缺點(diǎn)：內(nèi)碎片造成浪費(fèi)；分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。343、動(dòng)態(tài)分區(qū)分配數(shù)據(jù)結(jié)構(gòu)分區(qū)分配算法分配與回收操作35分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表空閑分區(qū)鏈36空閑分區(qū)表每個(gè)分區(qū)占一個(gè)表目，包含分區(qū)序號(hào)、分區(qū)始址、分區(qū)大小分區(qū)號(hào)大?。↘）起址（K）狀態(tài)16444可用224232可用3空表目4空表目5………37空閑分區(qū)鏈在每一個(gè)分區(qū)的起始部分設(shè)置用于控制分區(qū)的信息、向前指針，在分區(qū)尾部設(shè)置一個(gè)向后指針，形成雙向鏈表。前向指針+2N0

后向指針+2N0

N個(gè)字節(jié)可用空閑鏈表結(jié)構(gòu)38分區(qū)分配算法*FF首次適應(yīng)算法：空閑分區(qū)按起址遞增次序排列，從頭開始直至找到第一個(gè)滿足要求的空閑分區(qū)。特點(diǎn)：內(nèi)存低端會(huì)留下小的空閑區(qū)，高端有大的空閑區(qū)；每次查找從低址開始，會(huì)增加查找開銷。*NF循環(huán)首次適應(yīng)算法(下次適應(yīng))：從上次分配的空閑區(qū)位置之后開始查找(到最后分區(qū)時(shí)再回到開頭)特點(diǎn)：減少查詢次數(shù)，內(nèi)存分配均勻；但缺乏大的空閑分區(qū)。*BF最佳適應(yīng)算法：空閑分區(qū)按大小遞增的次序排列，從頭開始找到第一個(gè)滿足要求的空閑分區(qū)。特點(diǎn)：會(huì)留下大量難以利用的小碎片。39WF最差適應(yīng)算法：空閑分區(qū)按大小遞減的次序排列，最前面的最大的空閑分區(qū)就是找到的分區(qū)。特點(diǎn)：查找速度快，分配后剩下的可用空間比較大；但一段時(shí)間后會(huì)缺乏較大空閑區(qū)。以上四種算法，統(tǒng)稱為順序搜索法。

這些算法各有利弊，到底哪種最好不能一概而論，而應(yīng)針對(duì)具體作業(yè)序列來分析。對(duì)于某一作業(yè)序列來說，某種算法能將該作業(yè)序列中所有作業(yè)安置完畢，那么我們說該算法對(duì)這一作業(yè)序列是合適的。QF快速適應(yīng)算法(分類搜索法)：按進(jìn)程常用空間大小對(duì)空閑分區(qū)進(jìn)行劃分，形成多類分區(qū)鏈表，并設(shè)立一張分區(qū)管理索引表。特點(diǎn)：查找效率高，可滿足大空間需求；但分區(qū)歸還算法復(fù)雜、空間開銷大。40例：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊(duì)列：經(jīng)分析可知：最佳適應(yīng)法對(duì)這個(gè)作業(yè)序列是合適的，而其它兩種對(duì)該作業(yè)序列是不合適的。1、首次適應(yīng)算法2、最佳適應(yīng)法3、最壞適應(yīng)法410K15K38K48K68K80K110K120K空閑區(qū)表已分配區(qū)表始址長度標(biāo)志15K23K未分配48K20K未分配80K30K未分配空空始址長度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ4空空首次適應(yīng)算法FFJ1J2J3J4有個(gè)5K的作業(yè)J5，24K的作業(yè)J6到來：20KJ5104KJ6始址長度標(biāo)志20K18K未分配48K20K未分配104K6K未分配空空始址長度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ415K5KJ580K24KJ642分區(qū)分配操作

1）分配內(nèi)存2）回收內(nèi)存43分配內(nèi)存設(shè)請(qǐng)求的分區(qū)大?。簎.size設(shè)空閑分區(qū)大小：

m.size不可再切割的剩余分區(qū)大?。簊ize如果m.size-u.size≤size將整個(gè)分區(qū)分配給請(qǐng)求者，否則剩余部分留在空閑分區(qū)鏈（表）中。將分區(qū)的首址返回給調(diào)用者44查找空閑分區(qū)鏈表第一項(xiàng)檢索完否？m.size>u.size?m.size-u.size≦size?劃出u.size大小的分區(qū)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回將該分區(qū)從鏈表中移出繼續(xù)檢索下一個(gè)表項(xiàng)YYYNNN內(nèi)存分配流程45回收內(nèi)存

當(dāng)進(jìn)程釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首值，從空閑區(qū)鏈（表）中找到相應(yīng)的插入點(diǎn)，回收區(qū)可能出現(xiàn)四種情況：（1）與插入點(diǎn)的前一個(gè)空閑區(qū)F1相鄰接。（2）與插入點(diǎn)的后一空閑分區(qū)F2相鄰接。（3）同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接。（4）既不與F1鄰接，又不與F2鄰接。46

F1

回收區(qū)

F1回收區(qū)與插入點(diǎn)的前一個(gè)空閑區(qū)F1相鄰接

47

回收區(qū)F2

回收區(qū)回收區(qū)與插入點(diǎn)的后一空閑分區(qū)F2相鄰接48F1

回收區(qū)F2F1回收區(qū)同時(shí)與插入點(diǎn)的前后兩個(gè)分區(qū)鄰接494、可重定位分區(qū)分配動(dòng)態(tài)重定位的引入隨著系統(tǒng)接收的作業(yè)的增加，內(nèi)存中連續(xù)的大塊分區(qū)不復(fù)存在，產(chǎn)生了大量的“碎片”。新的作業(yè)無法裝入到每個(gè)“碎片”小分區(qū)上運(yùn)行，但所有碎片的空間總和可能大于需求。通過“拼接”或“緊湊”來實(shí)現(xiàn)程序的浮動(dòng)（動(dòng)態(tài)重定位）。50OS區(qū)Job2Job4Job3Job1Job5Job6Job7“零頭”碎片OS區(qū)Job2Job4Job3Job1Job5Job6Job7OS區(qū)Job2Job4Job3Job1Job5Job6Job7514.2.4可重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入圖4-8緊湊的示意☆分配一個(gè)連續(xù)的內(nèi)存空間“緊湊”52動(dòng)態(tài)重定位的引入操作系統(tǒng)用戶程序110KB用戶程序330KB用戶程序614KB用戶程序926KB碎片：內(nèi)存中不能被利用的小分區(qū)稱為“零頭”或“碎片”。

53動(dòng)態(tài)重定位的引入操作系統(tǒng)用戶程序1用戶程序3用戶程序6用戶程序980KB分散的小分區(qū)拼接成一個(gè)大分區(qū)的方法，稱為“拼接”或“緊湊”。54動(dòng)態(tài)重定位的實(shí)現(xiàn)地址變換過程是在程序執(zhí)行期間，隨著對(duì)每條指令或數(shù)據(jù)的訪問自動(dòng)進(jìn)行的，故稱為動(dòng)態(tài)重定位增設(shè)硬件機(jī)構(gòu)：重定位寄存器。55動(dòng)態(tài)重定位的實(shí)現(xiàn)處理機(jī)一側(cè)存儲(chǔ)器一側(cè)作業(yè)J內(nèi)存365LOAD1,2500500025001000365LOAD1,2500150001250010000110002500相對(duì)地址10000重定位寄存器000056動(dòng)態(tài)重定位分區(qū)分配算法增加了緊湊功能設(shè)請(qǐng)求的分區(qū)大?。簎.size設(shè)空閑分區(qū)大小：

m.size不可再切割的剩余分區(qū)大?。簊ize可重定位分區(qū)分配算法動(dòng)態(tài)分區(qū)+緊湊技術(shù)，與動(dòng)態(tài)分區(qū)分配算法基本相同，但增加了緊湊功能。57動(dòng)態(tài)重定位分區(qū)分配算法流程查找空閑分區(qū)鏈表第一項(xiàng)找到大于u.size的可用分區(qū)？按動(dòng)態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號(hào)及首址進(jìn)行緊湊形成連續(xù)空閑區(qū)YYNN請(qǐng)求分配u.size分區(qū)空閑分區(qū)總和≥u.size？修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)無法分配返回58優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)：消除了“碎片”，提高了內(nèi)存利用率，同時(shí)提高了系統(tǒng)效率。缺點(diǎn)：需要?jiǎng)討B(tài)重定位“硬件”機(jī)構(gòu)支持，增加了系統(tǒng)成本，并輕度降低了程序執(zhí)行速度，“緊湊”處理增加了系統(tǒng)開銷。動(dòng)態(tài)重定位分區(qū)分配算法595、覆蓋技術(shù)覆蓋技術(shù)是作業(yè)之間或作業(yè)內(nèi)部的若干個(gè)程序段共享主存的技術(shù)。主程序子程序A子程序B子E子C子D子F調(diào)用子G調(diào)用調(diào)用2k3k4k1k4k4k4k3k子H3k調(diào)用主程序2k子程序A(B)4kC(D/E/F/G)4kH3k覆蓋段覆蓋段程序大?。?8K內(nèi)存空間只需13K60簡(jiǎn)單覆蓋應(yīng)用示意圖輸入模塊正常輸出計(jì)算模塊數(shù)據(jù)錯(cuò)誤結(jié)束退出結(jié)果異常分析與報(bào)告輸入模塊計(jì)算模塊結(jié)束退出正常輸出數(shù)據(jù)錯(cuò)誤結(jié)果異常分析與報(bào)告61對(duì)換的引入對(duì)換：指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或暫時(shí)不用的程序和數(shù)據(jù)調(diào)出到外存，以騰出空間供具備運(yùn)行條件的進(jìn)程或其程序數(shù)據(jù)調(diào)入內(nèi)存投入運(yùn)行。（中級(jí)調(diào)度）目的：用于解決內(nèi)存不足的問題；對(duì)換分類（1）整體對(duì)換：以整個(gè)進(jìn)程為單位，又稱進(jìn)程對(duì)換（2）部分對(duì)換：頁面對(duì)換，以“頁”為單位；分段對(duì)換,以“段”為單位進(jìn)程對(duì)換實(shí)現(xiàn)的功能對(duì)換空間的管理進(jìn)程換入過程進(jìn)程換出過程6、對(duì)換技術(shù)（Swapping）62文件區(qū)對(duì)換區(qū)外存對(duì)換空間的管理為提高空間利用率采用離散分配方式為提高對(duì)換速度采用連續(xù)分配方式63進(jìn)程換出過程選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對(duì)換區(qū)上若傳送過程未出現(xiàn)錯(cuò)誤，便可回收該進(jìn)程所占用的內(nèi)存空間，并修改該進(jìn)程的PCB64進(jìn)程換入過程定時(shí)查看進(jìn)程狀態(tài)將處于“就緒”態(tài)的換出時(shí)間最久的進(jìn)程換入內(nèi)存直至已無可換入的進(jìn)程或無可換出的進(jìn)程為止。65離散分配方式基本思想：將一個(gè)進(jìn)程分散的裝入不相鄰的分區(qū)中。離散分配的基本單位是頁，則稱為分頁存儲(chǔ)管理方式；如果離散分配的基本單位是段，則稱為分段存儲(chǔ)管理方式。66第四節(jié)

基本分頁存儲(chǔ)管理方式連續(xù)分配方式的不足，促使人們產(chǎn)生了離散分配的管理思想。從而引入了“分頁”分配管理的管理方式。分為：基本分頁（純分頁）和支持虛存管理的請(qǐng)求分頁管理?；痉猪摯鎯?chǔ)管理方式不具備頁面對(duì)換功能又稱純分頁存儲(chǔ)管理方式不支持虛擬存儲(chǔ)器功能67分頁存儲(chǔ)管理將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁面或頁，并為各頁編號(hào)，從0開始，如第0頁、第1頁等。把內(nèi)存空間分成與頁面相同大小的若干個(gè)存儲(chǔ)塊，稱為塊或頁框，也加以編號(hào)，如0#、1#塊等。以塊為單位將進(jìn)程中的若干個(gè)頁分別裝入到多個(gè)可以不相臨接的物理塊中68頁內(nèi)碎片由于進(jìn)程的最后一頁經(jīng)常不滿一塊而形成不可利用的碎片，稱之為“頁內(nèi)碎片”。69頁面大小通常1KB-8KB頁面太?。喉搩?nèi)碎片小，提高內(nèi)存利用率，但頁表過長，占內(nèi)存；降低對(duì)換效率。頁面太大：提高了對(duì)換速度。但頁內(nèi)碎片大，降低了內(nèi)存利用率。701、頁面與頁表01234567891110內(nèi)存第0頁第1頁第2頁第3頁第4頁第5頁第6頁用戶作業(yè)02K-1第2頁（頁長2K）02K-14號(hào)頁架（頁長2K）實(shí)現(xiàn)原理：1．等分主存：每份稱為物理塊/頁框/頁架，編號(hào)：01234……2.劃分地址空間：以塊長為尺度將作業(yè)的地址空間從低地址端開始劃分成片每片稱為頁/頁面，編號(hào)：01234……

3.分配原則：主存以塊為單位，作業(yè)以頁為單位１頁→１塊分給一個(gè)作業(yè)的若干塊不要求鄰接

711、頁面與頁表頁面頁面和物理塊（頁框/架）：順序編號(hào)，頁內(nèi)碎片頁面大?。?nBytes一般在：1K~8K地址結(jié)構(gòu)

邏輯地址 物理地址頁內(nèi)地址d物理塊號(hào)P

位移量W頁號(hào)P例如：位移量（頁內(nèi)地址）W頁號(hào)P3112110每頁大小：212=4KB地址空間中最多有：220=1M頁721、頁面與頁表例如：位移量W頁號(hào)P151090計(jì)算一共劃分了多少頁，每一頁有多大？每頁大小：210=1KB地址空間中最多有：26=64頁73已知：邏輯地址空間中的地址A，頁面大小L頁號(hào)P和頁內(nèi)地址d的計(jì)算公式P＝INT[A/L]INT：整除函數(shù)d＝[A]MODLMOD：取余函數(shù)例如：某系統(tǒng)的頁面大小為1KB，地址A=2170B，則求得P=2，d=1221、頁面與頁表74頁表——頁面映像表定義：為便于在內(nèi)存中找到進(jìn)程的每個(gè)頁面所對(duì)應(yīng)的物理塊，系統(tǒng)為每個(gè)進(jìn)程建立一張頁面映像表，簡(jiǎn)稱頁表，記錄頁面在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)。數(shù)據(jù)結(jié)構(gòu)：頁號(hào)、塊號(hào)、存取控制項(xiàng)頁表的作用：實(shí)現(xiàn)從頁號(hào)到物理塊號(hào)的地址映射。1、頁面與頁表7523579…11104內(nèi)存第0頁第1頁第2頁第3頁第4頁第5頁第6頁012356789101112用戶作業(yè)第0頁第1頁第2頁第3頁第4頁第5頁第6頁…第n頁塊號(hào)頁號(hào)1051169453327120頁表……頁表的作用問題：分頁存儲(chǔ)管理方式要想從內(nèi)存讀取一個(gè)信息，需要訪問幾次內(nèi)存？兩次。76表項(xiàng)中常設(shè)有存取控制字段一位：允許讀/寫只讀兩位：

允許讀/寫只讀只執(zhí)行77

例題:在一分頁存儲(chǔ)管理系統(tǒng)中，邏輯地址長度為16位，頁面大小為4096字節(jié)，現(xiàn)有一個(gè)邏輯地址為2F6AH，且第0、1、2頁依次放在物理塊號(hào)10、12、14中，問相應(yīng)的物理地址是多少？解答：因邏輯地址長度為16位，頁面大小4096字節(jié)，所以，前面的4位表示頁號(hào)。2F6AH的二進(jìn)制表示：0010

1111

0110

1010可知頁號(hào)為2，故放在14號(hào)物理塊中十六進(jìn)制表示為：EF6AH78某存儲(chǔ)器中的用戶空間共有32個(gè)頁面，每頁1KB，主存32KB。假定某時(shí)刻系統(tǒng)為用戶的笫0、1、2、3頁分別分配物理塊為5、10、4、7，地址0A6F對(duì)應(yīng)的物理地址為多少?

解：0A6F對(duì)應(yīng)的二進(jìn)數(shù)16位為：0000101001101111（1分），可見是第2個(gè)頁，其對(duì)應(yīng)的物理塊號(hào)為4（2分）。故物理地址為：0001001001101111，即126F792、地址變換機(jī)構(gòu)基本的地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)的任務(wù)：實(shí)現(xiàn)地址映射，即從邏輯地址到物理地址的變換過程。實(shí)際上是將邏輯地址中的頁號(hào)轉(zhuǎn)換為內(nèi)存中的物理塊號(hào)。地址變換任務(wù)是借助于頁表來完成的，頁表存放在內(nèi)存系統(tǒng)區(qū)的一個(gè)連續(xù)空間中；系統(tǒng)中只設(shè)置一個(gè)頁表寄存器PTR，存放頁表在內(nèi)存的始址和頁表的長度(即頁數(shù))。進(jìn)程未執(zhí)行時(shí)，頁表的始址和頁表長度存放在本進(jìn)程PCB中，當(dāng)調(diào)度到進(jìn)程時(shí)裝入頁表寄存器中。地址映射過程：自動(dòng)的將邏輯地址分為頁號(hào)和頁內(nèi)地址根據(jù)頁號(hào)查詢頁表：頁表首地址+頁號(hào)*表項(xiàng)長度80頁表始址頁表長度頁表寄存器≤頁表塊號(hào)頁號(hào)53327120物理地址頁號(hào)(3)頁內(nèi)地址邏輯地址越界中斷找到該頁對(duì)應(yīng)的物理塊號(hào)，裝入物理地址寄存器將頁內(nèi)地址送入物理地址寄存器。81例1：已知某分頁系統(tǒng)，主存容量為64k，頁面大小為1k，對(duì)一個(gè)4頁大的作業(yè)，第0、1、2、3頁被分配到內(nèi)存的2、4、6、7塊中。求：將十進(jìn)制的邏輯地址1023、2500、4500轉(zhuǎn)換成物理地址。解:(1)1023/1K，得到頁號(hào)為0，頁內(nèi)地址1023。又對(duì)應(yīng)的物理塊號(hào)為2，故物理地址為2*1k+1023=3071(2)2500/1K，得到頁號(hào)為2，頁內(nèi)地址452。又對(duì)應(yīng)的物理塊號(hào)為6，故物理地址為6*1k+452=6596(3)4500/1K，得到頁號(hào)為4，頁內(nèi)地址404。因?yàn)轫撎?hào)不小于頁表長度，故產(chǎn)生越界中斷。82快表引入原因cpu存取一個(gè)數(shù)據(jù)時(shí)要兩次訪問內(nèi)存第一次是訪問頁表，找到指定頁的物理塊號(hào)，再將塊號(hào)與頁內(nèi)偏移量w拼接形成物理地址。第二次訪問內(nèi)存是從所得地址中獲得所需數(shù)據(jù)（或向此地址中寫入數(shù)據(jù)）cpu的工作效率大約減少一半83為提高地址變換速度增設(shè)一個(gè)具有并行查詢能力的高速緩沖寄存器，稱為“聯(lián)想寄存器”或“快表”，用于存放當(dāng)前訪問的頁表項(xiàng)。84地址變換過程cpu給出有效地址，由地址變換機(jī)構(gòu)自動(dòng)地將頁號(hào)p送入高速緩沖存儲(chǔ)器，并將此頁號(hào)與高速緩存中的所有頁號(hào)進(jìn)行比較，若有與此相匹配的頁號(hào)，則表示所要訪問的頁表項(xiàng)在快表中。于是，可直接讀出該頁所對(duì)應(yīng)的物理塊號(hào)，并送物理地址寄存器中。如在快表中未找列對(duì)應(yīng)的頁表項(xiàng)，還須再訪問內(nèi)存中的頁表，找到后，把從頁表項(xiàng)中讀出的物理塊號(hào)送地址寄存器；同時(shí)，還將此頁表項(xiàng)存入快表中的一個(gè)寄存器單元中，亦即重新修改快表、但如果聯(lián)想存儲(chǔ)器巳滿，則os必須找到一個(gè)老的且已被認(rèn)為不再需要的頁表項(xiàng)將它換出。局部性原理85頁表始址頁表長度頁表寄存器≤頁表塊號(hào)頁號(hào)5332712031250物理地址21250邏輯地址越界中斷快表塊號(hào)頁號(hào)2051145320輸入寄存器具有快表的地址變換機(jī)構(gòu)86頁表始址頁表長度頁表寄存器≤頁表塊號(hào)頁號(hào)5332712071250物理地址11250邏輯地址越界中斷快表塊號(hào)頁號(hào)2051145320輸入寄存器具有快表的地址變換機(jī)構(gòu)87快表通常只存放16~512個(gè)頁表項(xiàng)對(duì)于中、小型作業(yè)來說，已有可能把全部頁表項(xiàng)放在快表中大型作業(yè)只能將其一部分頁表項(xiàng)放入其中從快表能找到所需頁表項(xiàng)的命中率可達(dá)90%88例：檢索聯(lián)想寄存器的時(shí)間為20ns，訪問內(nèi)存的時(shí)間為100ns。如果能在聯(lián)想存儲(chǔ)器中檢索出頁號(hào)，則cpu存取數(shù)據(jù)共需要

，如果不能在聯(lián)想存儲(chǔ)器中找到該頁號(hào)，則總共需要

。再假定訪問聯(lián)想存儲(chǔ)器的命中率分別為0%，50%，80%，90%，98%，計(jì)算有效訪問時(shí)間。有效訪問時(shí)間：T命中率：hT=h*t1+（1-h）*t289命中率%T=h*t1+（1-h）*t202205017080140901309812290例如：有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4KB，即212B,則在每個(gè)進(jìn)程頁表中頁表項(xiàng)可達(dá)1兆（220）個(gè)之多。又因?yàn)槊總€(gè)頁表項(xiàng)占用4個(gè)字節(jié)，故每個(gè)進(jìn)程僅僅其頁表就要占用4MB的內(nèi)存空間，而且還要求是連續(xù)的。解決方法：（1）用離散分配方式解決難以找到連續(xù)的大內(nèi)存空間的問題。（2）只將當(dāng)前需要的部分頁表項(xiàng)調(diào)入內(nèi)存，其余的頁表項(xiàng)仍駐留在磁盤上，需要時(shí)再調(diào)入。91兩級(jí)頁表

為離散分配的頁表再建立的一張頁表，稱為外層頁表，在每個(gè)頁表項(xiàng)中記錄了頁表頁面的物理塊號(hào)。923、兩級(jí)和多級(jí)頁表兩級(jí)頁表解決大頁表占用大的連續(xù)存儲(chǔ)空間的問題；將在內(nèi)存中離散分配的頁表再建立一張頁表，稱為外層頁表。邏輯地址： 外層頁號(hào)+外層頁內(nèi)地址+頁內(nèi)地址增設(shè)外層頁表寄存器，存放外層頁表的始址10位10位12位933、兩級(jí)和多級(jí)頁表以32位邏輯地址空間為例當(dāng)頁面大小為4KB時(shí)（12位），若采用一級(jí)頁表結(jié)構(gòu)，應(yīng)具有20位的頁號(hào)，即頁表項(xiàng)應(yīng)有1M個(gè)；用兩級(jí)頁表時(shí)，再對(duì)頁表進(jìn)行分頁，使每頁中包含210個(gè)頁表項(xiàng)，最多允許有210個(gè)頁表分頁，即外層頁表中的外層頁內(nèi)地址P2為10位，外層頁號(hào)P1也為10位。94邏輯地址結(jié)構(gòu)外層頁號(hào)外層頁內(nèi)地址頁內(nèi)地址3122211211095963、兩級(jí)和多級(jí)頁表外部頁表塊號(hào)頁號(hào)321078110110頁表分頁11223120211130……01231121131011……97外部頁表外部頁表寄存器物理地址外部頁號(hào)P1外部頁內(nèi)地址P2邏輯地址頁內(nèi)地址d…………頁表具有兩級(jí)頁表的地址變換機(jī)構(gòu)984、基本分頁的特點(diǎn)優(yōu)點(diǎn)：存在頁內(nèi)碎片，但碎片相對(duì)較小，內(nèi)存利用率較高實(shí)現(xiàn)了離散分配，消除了程序浮動(dòng)；缺點(diǎn)：需要專門的硬件支持，尤其“快表”；內(nèi)存訪問的效率下降。99第五節(jié)

基本分段存儲(chǔ)管理方式基本分段管理思想的引入基本原理地址變換分段與分頁的主要區(qū)別段頁式存儲(chǔ)管理方式1001、分段管理思想的引入分段存儲(chǔ)管理方式主要是為了滿足用戶和程序員的下述需要：方便編程：LOAD1,[A]|<D>;信息共享：共享的實(shí)現(xiàn)以是信息的邏輯單位為基礎(chǔ)信息保護(hù)：同樣是對(duì)邏輯單位進(jìn)行保護(hù)動(dòng)態(tài)增長：如數(shù)據(jù)段動(dòng)態(tài)鏈接：運(yùn)行時(shí)調(diào)入內(nèi)存并鏈接101在分段存儲(chǔ)管理方式中，作業(yè)的地址空間被劃分為若干個(gè)段，每個(gè)段定義一組邏輯信息。每個(gè)段都從0開始編址，采用一段連續(xù)的地址空間。段的長度由相應(yīng)的邏輯信息組的長度決定，因而段長不等整個(gè)作業(yè)的地址空間分成多個(gè)段，是二維的。2、基本原理102分段地址中的地址具有如下結(jié)構(gòu)：

段號(hào)段內(nèi)地址31

16150允許一個(gè)作業(yè)最多有64K個(gè)段每個(gè)段的最大長度為64K103系統(tǒng)為每一個(gè)進(jìn)程建立一張段映射表，簡(jiǎn)稱段表。用于實(shí)現(xiàn)從邏輯段到物理內(nèi)存的映射。（段表的定義及作用）段表1042、基本原理分段作業(yè)（邏輯地址）空間分段，每個(gè)段都有名字：主程序段、子程序段、數(shù)據(jù)段、棧段等邏輯地址：二維地址（段號(hào)，段內(nèi)地址）每個(gè)段裝入內(nèi)存中的一個(gè)連續(xù)的內(nèi)存空間段表段號(hào)、段基址、段長度等每個(gè)段在段表中占一個(gè)表項(xiàng)段表寄存器：存放段表的起址和長度利用段表實(shí)現(xiàn)地址映射1052、基本原理內(nèi)存第0段第1段第2段第3段用戶作業(yè)段表基址段長150K35K500K9K300K20K100K42K3210段號(hào)第0段第1段第2段第3段1063、地址變換及變換機(jī)構(gòu)基本分段管理的地址變換與基本分頁管理的變換機(jī)構(gòu)和過程類似段表寄存器存放段表的起始地址和段表長度越界訪問控制邏輯地址的段號(hào)與段表長度比較；段內(nèi)地址與段表中保存的段長比較。107段表始址段表長度（4）段表寄存器≤8292物理地址段號(hào)2100邏輯地址越界中斷段表基址段長92002008K5004K6006K1K3210段號(hào)內(nèi)存108例2：對(duì)于如下所示的段表，請(qǐng)將邏輯地址（0，137），（1，4000），（2，3600），（5，230）轉(zhuǎn)換成物理地址。解:(1)段號(hào)0<段表長，且137<段長10k，故段號(hào)、段內(nèi)地址全部合法。得物理地址為50k+137=51337段號(hào)內(nèi)存始址段長050k10k160k3k270k5k3120k8k4150k4k解:(2)段號(hào)1<段表長，段號(hào)合法。4000>段長3k，因此產(chǎn)生越界中斷。解:(3)段號(hào)2<段表長，且3600<段長5k，故段號(hào)、段內(nèi)地址全部合法。得物理地址為70k+3600=75280解:(4)段號(hào)5＝段表長，故段號(hào)不合法。產(chǎn)生越界中斷。1094、分段與分頁的主要區(qū)別（重點(diǎn)）頁是信息的物理單位，分頁是為了滿足系統(tǒng)管理的需要；段是信息的邏輯單位，分段是為了滿足用戶的需要；頁的大小固定且由系統(tǒng)決定，段的長度不固定，決定于用戶所編寫的程序，通常由編譯程序在對(duì)源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來劃分。分頁系統(tǒng)中的邏輯地址空間是一維的，程序員只需利用一個(gè)記憶符，即可表示一個(gè)地址；分段系統(tǒng)中的是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，既需給出段名，又需給出段內(nèi)地址。110內(nèi)存頁表editor1data1進(jìn)程1data1進(jìn)程2editor2…editor40editor1editor2…editor40…data10…data102122…6061…702122…6071…80editor1data1data1editor2…editor40…data10…data10021226061707180可重入代碼(純代碼)：允許多個(gè)進(jìn)程同時(shí)訪問但不允許修改的代碼（程序的編譯器）111內(nèi)存段表基址段長240K40K80K160K10段號(hào)editorJob1數(shù)據(jù)進(jìn)程1editorJob2數(shù)據(jù)進(jìn)程2基址段長380K40K80K160K10段號(hào)editorJob1數(shù)據(jù)Job2數(shù)據(jù)112段號(hào)S段內(nèi)頁號(hào)P頁內(nèi)地址W5、段頁式存儲(chǔ)管理方式基本思想結(jié)合分頁和分段技術(shù)；分頁：有效提高內(nèi)存利用率分段：很好的滿足用戶需求原理對(duì)內(nèi)存進(jìn)行分頁（物理塊/頁架）；對(duì)用戶作業(yè)先分段，各段再分頁。地址結(jié)構(gòu)與地址變換段號(hào)、段內(nèi)頁號(hào)、頁內(nèi)地址三部分段表和頁表113段頁式存儲(chǔ)管理方式

既具有分段系統(tǒng)的便于實(shí)現(xiàn)、分段可共享、易于保護(hù)、可動(dòng)態(tài)鏈接等優(yōu)點(diǎn)又能像分頁系統(tǒng)那樣解決內(nèi)存的外部碎片問題，以及可為各個(gè)分段離散地分配內(nèi)存等問題。114段頁式存儲(chǔ)管理基本原理

分段和分頁原理結(jié)合先將用戶分成若干個(gè)段再把每個(gè)段分成若干個(gè)頁，并為每一個(gè)段賦予一個(gè)段名。

115作業(yè)地址空間116段頁式地址結(jié)構(gòu)117主程序段數(shù)據(jù)段子程序段118……段表始址段表長度段表13021110頁表始址頁表長度狀態(tài)段號(hào)段表寄存器頁表03121110存儲(chǔ)塊號(hào)狀態(tài)頁號(hào)頁表1110存儲(chǔ)塊號(hào)狀態(tài)頁號(hào)119段表始址段表長度段表寄存器邏輯地址頁號(hào)P頁內(nèi)地址段號(hào)S≤段表塊號(hào)b塊內(nèi)地址物理地址越界中斷頁表xxxx2xxxx1xxxx0頁表始址段號(hào)2b10存儲(chǔ)塊號(hào)頁號(hào)120三次訪問內(nèi)存第一次訪問段表，從中取得頁表始值；第二次訪問頁表，從中取出該頁所在的物理塊號(hào)，并將該塊號(hào)與頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址；第三次真正訪問指令或數(shù)據(jù)。121段頁式存儲(chǔ)管理的優(yōu)缺點(diǎn)同時(shí)具備分段和分頁管理的優(yōu)點(diǎn)：分散存儲(chǔ)，內(nèi)存利用率較高；便于代碼或數(shù)據(jù)共享，支持動(dòng)態(tài)鏈接等。訪問效率下降：一次訪問轉(zhuǎn)換成了三次訪問。122第六節(jié)

虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的引入虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的特征1231、虛擬存儲(chǔ)器的引入內(nèi)存空間的限制情況一：內(nèi)存空間裝不下的大作業(yè)無法運(yùn)行情況二：作業(yè)量大時(shí)，無法允許更多的作業(yè)并發(fā)常規(guī)存儲(chǔ)器管理方式的特點(diǎn)：一次性、駐留性虛擬存儲(chǔ)器物理上不存在，利用海量外存進(jìn)行內(nèi)存“空間”擴(kuò)展。允許作業(yè)部分裝入，需要時(shí)再臨時(shí)裝入所需的部分。直到作業(yè)退出，某些部分也有可能沒被裝入過。*基于局部性原理—程序在執(zhí)行時(shí)將呈現(xiàn)局部性規(guī)律，即在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分，它所訪問的存儲(chǔ)空間也局限于某個(gè)區(qū)域。124局部性原理幾個(gè)論點(diǎn)程序多數(shù)情況是順序執(zhí)行的過程調(diào)用會(huì)使程序的執(zhí)行由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但過程調(diào)用的深度大多不超過5。程序?qū)?huì)在一段時(shí)間內(nèi)都局限在這些過程的范圍內(nèi)運(yùn)行。循環(huán)結(jié)構(gòu)雖只由少數(shù)指令構(gòu)成，但是他們將多次執(zhí)行程序包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理。125局部性表現(xiàn)時(shí)間局限性。某指令一旦執(zhí)行，則不久后該指令可能再次執(zhí)行；某數(shù)據(jù)被訪問過，則不久后該數(shù)據(jù)可能再次被訪問?？臻g局限性。程序在一段時(shí)間內(nèi)訪問的地址，可能集中在一定的范圍之內(nèi)，其典型的情況便是程序的順序執(zhí)行。126虛擬存儲(chǔ)器定義：虛擬存儲(chǔ)器是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。其邏輯容量由內(nèi)存和外存之和所決定，其運(yùn)行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。1272、虛擬存儲(chǔ)器的實(shí)現(xiàn)方法必須建立在離散分配的內(nèi)存管理技術(shù)基礎(chǔ)上。分頁請(qǐng)求系統(tǒng)在分頁系統(tǒng)的基礎(chǔ)上、增加了請(qǐng)求調(diào)頁功能、頁面置換功能所形成的頁式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入若干頁（而非全部程序）的用戶程序和數(shù)據(jù)，便可啟動(dòng)運(yùn)行。再通過調(diào)頁功能及頁面置換功能，陸續(xù)地把即將要運(yùn)行的頁面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁面換出到外存上、置換時(shí)以頁面為單位1282、虛擬存儲(chǔ)器的實(shí)現(xiàn)方法基本分頁系統(tǒng)+請(qǐng)求調(diào)頁功能+頁面置換功能＝頁式虛擬存儲(chǔ)系統(tǒng)硬件支持：請(qǐng)求分頁的頁表機(jī)制、缺頁中斷機(jī)構(gòu)、動(dòng)態(tài)地址變換機(jī)構(gòu)。軟件支持：請(qǐng)求分頁、頁面置換1292、虛擬存儲(chǔ)器的實(shí)現(xiàn)方法例：某虛擬存儲(chǔ)器的用戶編程空間共32個(gè)頁面，每頁為1KB，內(nèi)存16KB。假定某時(shí)刻一用戶頁表中已調(diào)入內(nèi)存的頁面的頁號(hào)和物理塊號(hào)的對(duì)照表如下：頁號(hào)物理塊號(hào)031721138則邏輯地址0A5C(H)所對(duì)應(yīng)的物理地址是什么？130請(qǐng)求分段系統(tǒng)基本分段系統(tǒng)+請(qǐng)求調(diào)段功能+分段置換功能＝段式虛擬存儲(chǔ)系統(tǒng)硬件支持：請(qǐng)求分段的段表機(jī)制、缺段中斷機(jī)構(gòu)、動(dòng)態(tài)地址變換機(jī)構(gòu)。軟件支持：請(qǐng)求分段、段的置換1313、虛擬存儲(chǔ)器的特征離散性——最基本在內(nèi)存分配時(shí)采用離散分配方式；多次性一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行；對(duì)換性允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)、換出；虛擬性——最重要能從邏輯上擴(kuò)充內(nèi)存容量，使用戶“看到”的內(nèi)存容量遠(yuǎn)大于實(shí)際大小。（總?cè)萘坎怀^物理內(nèi)存和外存交換區(qū)容量之和）該特征是以上兩個(gè)特征為基礎(chǔ)的。132第七節(jié)

請(qǐng)求分頁存儲(chǔ)管理方式請(qǐng)求分頁中的硬件支持內(nèi)存分配策略和分配算法請(qǐng)求分頁策略1331、請(qǐng)求分頁中的硬件支持頁表機(jī)制用于地址轉(zhuǎn)換；增加頁表項(xiàng)：頁號(hào)物理塊號(hào)狀態(tài)位P訪問字段A修改位M外存地址狀態(tài)位P：用于指示該頁是否已調(diào)入內(nèi)存訪問字段A：記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)修改位M：該頁在調(diào)入內(nèi)存后是否被修改過外存地址：指示該頁在外存上的地址134缺頁中斷機(jī)構(gòu)請(qǐng)求分頁系統(tǒng)中每當(dāng)所要訪問的頁不在內(nèi)存時(shí)，便引發(fā)一次缺頁中斷、請(qǐng)求將所缺之頁調(diào)入內(nèi)存。缺頁中斷與其他中斷的不同：在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁中斷654321A:B:CopyAtoB指令135第八節(jié)

頁面置換算法*最佳置換算法（OPT）*先進(jìn)先出（FIFO）*最近最久未使用置換算法（LRU）Clock置換算法（NRU）最少使用置換算法（LFU）頁面緩沖置換算法（PBA）當(dāng)內(nèi)存中沒有可以利用的頁架時(shí)，根據(jù)一定的策略從內(nèi)存中選擇一個(gè)頁面，把它置換到外存，稱為頁面置換算法。1361、最佳置換算法（OPT）

由Belady于1966年提出的一種理論上的算法，所淘汰的頁面，將是永不使用的或是在最長時(shí)間內(nèi)不被訪問的頁面（向?qū)砜矗?/p>

例如，假定系統(tǒng)為某進(jìn)程分配3個(gè)物理塊，并考慮有以下頁面引用串，需要注意的是：在某進(jìn)程中，(有些頁面經(jīng)常被訪問，如全局變量，常用函數(shù)，某些例程等)引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1137引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用率70770170122010320304243230321201201770101頁框(物理塊）203采用最佳置換算法，共發(fā)生9次缺頁，缺頁率9/20=45%。1、最佳置換算法（OPT）1381、最佳置換算法（OPT）特點(diǎn)：理論上，性能最佳；實(shí)際上，無法實(shí)現(xiàn)；通常用該算法來評(píng)價(jià)其他算法的優(yōu)劣。1392、先進(jìn)先出（FIFO）基本思想：

FIFO置換算法的思想是：當(dāng)發(fā)生頁面置換時(shí)，總是選擇在內(nèi)存駐留時(shí)間最久的頁面予以淘汰。對(duì)于上例，利用FIFO置換算法時(shí)，當(dāng)訪問2號(hào)頁面時(shí)，由于7號(hào)頁面駐留時(shí)間最長，故將7號(hào)頁面置換出去，同理，對(duì)其它頁面置換情況參照如下表所示。140引用率70770170122010323104430230321013201770201頁框2304204230230127127011從表上可以看出，采用FIFO置換算法，共發(fā)生15次缺頁，缺頁率為15/20=75%，2、先進(jìn)先出（FIFO）1412、先進(jìn)先出（FIFO）特點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單與進(jìn)程實(shí)際的運(yùn)行不相適應(yīng)142先進(jìn)先出算法雖然簡(jiǎn)單，但從數(shù)據(jù)分析可以看出該算法效果不夠理想，由于程序執(zhí)行具有局部性原理，所以該算法不能保證經(jīng)常被訪問的頁面不被淘汰。同時(shí)，在FIFO置換算法中，隨著分配給進(jìn)程的物理塊增多，反而缺頁率增大了，這種現(xiàn)象稱為Belady異常。只有FIFO置換算法有這種奇怪現(xiàn)象，其它算法沒有。下面來看一個(gè)例子，設(shè)某進(jìn)程的頁面引用串如下：1，2，3，4，1，2，5，1，2，3，4，5當(dāng)該進(jìn)程分得3、4物理塊時(shí)，其缺頁次數(shù)分別是9，10。(具體分析)2、先進(jìn)先出（FIFO）1433、最近最久未使用置換算法（LRU）基本思想：

根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策。由于無法預(yù)測(cè)各頁面將來的使用情況，只能利用“最近的過去”作為“最近將來”的近似，選擇最近最久未使用的頁面予以淘汰。特點(diǎn)：性能較好實(shí)現(xiàn)復(fù)雜，需要硬件支持（每頁配置一個(gè)寄存器、棧），增加系統(tǒng)負(fù)擔(dān)。144引用率70770170122010320304403230321132201710701頁框402432032102從上可以看出，采用LRU算法時(shí)，系統(tǒng)缺頁12次，缺頁率為12/20=60%3、最近最久未使用置換算法（LRU）1453、最近最久未使用置換算法（LRU）算法實(shí)現(xiàn)：

該算法賦予每個(gè)頁面一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間T,當(dāng)須淘汰一個(gè)頁面時(shí)，選擇現(xiàn)有頁面中其T值最大的，即最近最久未使用的頁面予以淘汰。146LRU置換算法的硬件支持：1）寄存器為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，表示為：R＝Rn-1Rn-2…R1R0當(dāng)進(jìn)程訪問此物理塊時(shí)，將Rn-1位置1。定時(shí)信號(hào)每隔一定時(shí)間將寄存器右移一位,并將最高位補(bǔ)0。具有最小數(shù)值的寄存器所對(duì)應(yīng)的頁面就是最近最久未使用的頁面。147101101108111000007110101006011010115110101104001000003001101012010010101R0R1R2R3R4R5R6R7R實(shí)頁某進(jìn)程具有8個(gè)頁面時(shí)的LRU訪問情況1482）棧利用棧來保存當(dāng)前使用的各個(gè)頁面的頁面號(hào)。當(dāng)進(jìn)程訪問此頁面時(shí)，將該頁面的頁面號(hào)從棧中移出，壓入棧頂。因此棧頂是最新被訪問頁面的編號(hào)，棧底是最近最久未使用頁面的頁面號(hào)。例如：現(xiàn)有一進(jìn)程所訪問的頁面號(hào)序列如下：4，7，0，7，1，0，1，2，1，2，6棧的變換情況為：4740741704017410742107412074210746210747067170401212149例1：在一個(gè)請(qǐng)求分頁系統(tǒng)中，假定系統(tǒng)分給一個(gè)作業(yè)的物理塊數(shù)為3，并且此作業(yè)的頁面走向?yàn)?，3，2，1，5，2，4，5，3，2，5，2。用FIFO、LRU、OPT計(jì)算缺頁次數(shù)和缺頁率。分析：如果所訪問的頁還沒有裝入內(nèi)存，將發(fā)生一次缺頁中斷。訪問過程中發(fā)生缺頁中斷的次數(shù)就是缺頁次數(shù)。缺頁次數(shù)除以總的訪問次數(shù)，就是缺頁率。150缺頁中斷32+253+453423+423425+425+125+135+13232+32+21252354251232頁面走向使用FIFO算法:缺頁次數(shù)：9，缺頁率：9/12；頁面置換6次駐留內(nèi)存最久的頁面——黃色標(biāo)志151缺頁中斷32253253+253+453452+452152+152+13232+32+21252354251232頁面走向使用LRU算法：長時(shí)間沒有訪問的頁面——黃色標(biāo)志剛剛訪問過的頁面——綠色標(biāo)志缺頁次數(shù)：7，缺頁率：7/12；頁面置換4次152缺頁中斷32532532+532534534+534532+532+13232+32+21352354251232頁面走向使用OPT算法：將來再也不用或最長時(shí)間不用的頁面——黃色標(biāo)志缺頁次數(shù)：6，缺頁率：6/12，頁面置換3次LRU最接近OPT，表明LRU優(yōu)于FIFO。153例2：在一個(gè)請(qǐng)求分頁系統(tǒng)中，假如一個(gè)作業(yè)的頁面走向?yàn)?，2，3，4，1，2，5，1，2，3，4，5,當(dāng)分給該作業(yè)的物理塊數(shù)M分別為3和4時(shí)，請(qǐng)用FIFO計(jì)算缺頁次數(shù)和缺頁率，并比較所得的結(jié)果。154缺頁中斷32435+435+235215215+215+214+314+324+321+21+11543215214321頁面走向使用FIFO算法——物理塊數(shù)為3:缺頁次數(shù)：9，缺頁率：9/12155使用FIFO算法——物理塊數(shù)為4:缺頁次數(shù)：10，缺頁率：10/12這種異?，F(xiàn)象稱為Belady現(xiàn)象。缺頁中斷432+3254+3214+3215+4215+4315+432543214321+4321+321+21+11543215214321頁面走向1564、最少使用置換算法（LFU）(不講)選擇在最近時(shí)期使用最少的頁面淘汰。（頻率）為每個(gè)頁面配一個(gè)計(jì)數(shù)器。需為在內(nèi)存中的每個(gè)頁面設(shè)置一個(gè)移位寄存器，用來記錄該頁面被訪問的頻率。每次訪問某頁時(shí)，便將該移位寄存器的最高位置1，此后每隔一定時(shí)間自動(dòng)右移一位。最近一段時(shí)間最少使用的頁面是∑Ri最小的頁。157101101108111000007110101006011010115110101104001000003001101012010010101R0R1R2R3R4R5R6R7R實(shí)頁158第九節(jié)

請(qǐng)求分段存儲(chǔ)管理方式請(qǐng)求分段中的硬件支持請(qǐng)求分段中的分段共享請(qǐng)求分段中的分段保護(hù)以基本分段內(nèi)存管理為基礎(chǔ)，程序運(yùn)行前，只需先調(diào)入部分分段，便啟動(dòng)執(zhí)行。其它分段在需要時(shí)，通過缺段中斷處理程序臨時(shí)調(diào)入。1591、請(qǐng)求分段中的硬件支持段表機(jī)制段名(號(hào))段長段的基址存取方式訪問字段A修改位M存在位P增補(bǔ)位外存始址(1)存取方式：存取屬性為只執(zhí)行、只讀或允許讀/寫(2)訪問字段A：記錄該段被訪問的頻繁程度(3)修改位M：該段在進(jìn)入內(nèi)存后是否被修改過(4)存在位P：指示本段是否已調(diào)入內(nèi)存(5)增補(bǔ)位：表示本段在運(yùn)行過程中，是否做過動(dòng)態(tài)增長(6)外存始址：本段在外存中的起始地址，即起始盤塊號(hào)160缺段中斷機(jī)構(gòu)以信息分段為單位操作。由于分段不定長，處理時(shí)較缺頁中斷復(fù)雜。虛段S不在內(nèi)存返回阻塞請(qǐng)求進(jìn)程內(nèi)存中有合適的空閑區(qū)嗎？從外存讀入段S修改段表及內(nèi)存空閑區(qū)鏈喚醒請(qǐng)求進(jìn)程空區(qū)容量總和能否滿足？否空區(qū)拼接，以形成一個(gè)合適的空區(qū)淘汰一個(gè)或幾個(gè)實(shí)段以形成一個(gè)合適空區(qū)是否是161地址變換機(jī)構(gòu)在基本分段系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上形成，增加了分段不在內(nèi)存時(shí)的缺段中斷請(qǐng)求。訪問[S][W]返回W≤段長？修改訪問字段，如寫訪問，置修改位=1形成訪問主存地址(A)=(主存始址)+(位移量W)是符合存取方式？段S在主存？分段越界中斷處理分段保護(hù)中斷處理缺段中斷處理是是否否否1622、分段共享共享段表段名段長內(nèi)存始址狀態(tài)外存始址共享進(jìn)程計(jì)數(shù)count狀態(tài)進(jìn)程名進(jìn)程號(hào)段號(hào)存取控制…………共享進(jìn)程計(jì)數(shù)count：記錄要共享該段的進(jìn)程數(shù)目存取控制字段：對(duì)一共享段，給不同進(jìn)程不同權(quán)限段號(hào)：不同進(jìn)程可以各用不同段號(hào)去共享某共享段163共享段的分配對(duì)第一個(gè)請(qǐng)求使用該共享段的進(jìn)程，由系統(tǒng)為該共享段分配一物理區(qū)，在把共享段調(diào)入該區(qū)。同時(shí)將該區(qū)的始址填入該進(jìn)程的段表中。在共享段表中增加一表項(xiàng)，置count=1其他進(jìn)程要調(diào)用該共享段時(shí)，在進(jìn)程的段表中增加一表項(xiàng)，填入該共享段的物理地址；在共享段的段表中，填上調(diào)用進(jìn)程的進(jìn)程名、存取控制等，再執(zhí)行count=count+1共享段的回收當(dāng)進(jìn)程不再需要共享段時(shí)，先釋放，撤消共享段的表項(xiàng)，執(zhí)行count=count-1僅當(dāng)count=0時(shí)，由系統(tǒng)回收共享段的物理內(nèi)存。1643、分段保護(hù)越界檢查段表寄存器：段表始址、段表長度比較：段號(hào)—段表長度、段長—段內(nèi)地址存取控制檢查存取控制字段只讀、只執(zhí)行、讀/寫環(huán)保護(hù)機(jī)構(gòu)環(huán)的設(shè)置：0-OS;1-實(shí)用程序和OS服務(wù)；2-應(yīng)用程序優(yōu)先級(jí)：低編號(hào)的環(huán)具有高優(yōu)先權(quán)。程序可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)；程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)。165小結(jié)一.存儲(chǔ)器的裝入和鏈接1重定位的概念、裝入方式；2鏈接方式二.連續(xù)分區(qū)分配1各連續(xù)分配方式的實(shí)現(xiàn)思想；2動(dòng)態(tài)分區(qū)分配的常用算法；3覆蓋和對(duì)換技術(shù)的概念和引入目的三.離散分區(qū)分配

1基本分頁/分段/段頁式管理的原理、地址映射過程；2引入快表的地址映射過程；3分頁和分段的區(qū)別166小結(jié)四.虛擬存儲(chǔ)管理1虛擬存儲(chǔ)器的定義和特點(diǎn)；2請(qǐng)求分頁/分段管理的原理、硬件支持；3頁面置換算法167小結(jié)本章重點(diǎn)：動(dòng)態(tài)分區(qū)分配算法；地址變換頁面置換算法；基本分頁/分段、請(qǐng)求分頁/分段管理的原理和地址映射機(jī)構(gòu)168補(bǔ)充有一頁式系統(tǒng)，其頁表存放在主存中。如果對(duì)主存的一次存取需要1.5微秒，試問實(shí)現(xiàn)一次頁面訪問的存取時(shí)間是多少？如果系統(tǒng)加有快表，平均命中率為85%，當(dāng)頁表項(xiàng)在快表中時(shí)，其查找時(shí)間忽略為0，試問此時(shí)的存取時(shí)間為多少？解：(1)由于頁表存放在主存，因此CPU必須兩次訪問主存才能獲得所需數(shù)據(jù)，所以實(shí)現(xiàn)一次頁面訪問的存取時(shí)間是：

1.5×2=3微秒

(2)在系統(tǒng)增加了快表后，在快表中找到頁表項(xiàng)的概率為85%，所以實(shí)現(xiàn)一次頁面的訪問的存取時(shí)間是0.85×1.5+(1-0.85)×2×1.5=1.725微秒1691．在虛擬存儲(chǔ)系統(tǒng)中，若進(jìn)程在內(nèi)存中占3塊(開始時(shí)為空)，采用先進(jìn)先出頁面淘汰算法，當(dāng)執(zhí)行訪問頁號(hào)序列為1、2、3、4、1、2、5、1、2、3、4、5、6時(shí)，將產(chǎn)生

次缺頁中斷。A．7B．8C．9D．102．系統(tǒng)“抖動(dòng)”現(xiàn)象的發(fā)生是由

引起的。A．置換算法選擇不當(dāng)B．交換