c第四章 存儲器管理

第四章存儲器管理4.0存儲器的層次結(jié)構(gòu)4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式4.5虛擬存儲器的基本概念4.6請求分頁存儲管理方式4.8頁面置換算法4.9請求分段存儲管理方式內(nèi)存(MainMemory或PrimaryMemory或RealMemory)也稱主存,是指CPU能直接存取指令和數(shù)據(jù)的存儲器。圖

內(nèi)存在計算機(jī)系統(tǒng)中的地位4.0存儲器的層次結(jié)構(gòu)高速緩存主存儲器（簡稱內(nèi)存或主存）外存儲器（軟盤、硬盤、光盤）磁盤內(nèi)存儲器：存儲管理外存儲器：設(shè)備管理寄存器

磁盤緩存可移動存儲介質(zhì)4.0存儲器的層次結(jié)構(gòu)功能：儲存以二進(jìn)位形式表示的程序和數(shù)據(jù)分類：內(nèi)存儲器/外存儲器內(nèi)存儲器外存儲器(簡稱外存或輔存)存取速度很快較慢存儲容量較小(因單位成本較高)很大(因單位成本較低)性質(zhì)斷電后信息消失斷電后信息保持用途存放已經(jīng)啟動運行的程序和需要立即處理的數(shù)據(jù)長期存放計算機(jī)系統(tǒng)中幾乎所有的信息與CPU關(guān)系CPU所處理的指令及數(shù)據(jù)直接從內(nèi)存中取出程序及相關(guān)數(shù)據(jù)必須先送入內(nèi)存后才能被CPU使用在多道程序環(huán)境下，程序要運行必須為之創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程的第一件事，就是要將程序和數(shù)據(jù)裝入內(nèi)存。如何將一個用戶源程序變?yōu)橐粋€可在內(nèi)存中執(zhí)行的程序，通常要經(jīng)過以下幾步:（1）編譯：由編譯程序（Compiler）將用戶源代碼編譯成若干個目標(biāo)模塊（ObjectModule）；（2）鏈接：由鏈接程序（Linker）將編譯后形成的目標(biāo)模塊以及它們所需要的庫函數(shù)，鏈接在一起，形成一個裝入模塊（LoadModule）；（3）裝入：由裝入程序（Loader）將裝入模塊裝入內(nèi)存。4.1程序的裝入和鏈接4.1程序的裝入和鏈接圖4-1對用戶程序的處理步驟1)靜態(tài)鏈接：在裝入內(nèi)存前鏈接成一個大的裝入模塊module。但需要解決兩個問題，即：

(1)修改相對地址。

(2)變換外部調(diào)用符號。2)裝入時動態(tài)鏈接：邊裝入邊鏈接，即裝入一個模塊時，便去找它的調(diào)用模塊，如有便再裝入，同時修改目標(biāo)模塊中的相對地址。由于分開裝入：便于模塊更新修改；便于模塊的共享。3)運行時動態(tài)鏈接:

將對某些目標(biāo)模塊的鏈接推遲到執(zhí)行時才進(jìn)行。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會被調(diào)入內(nèi)存或被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。4.1.2程序的鏈接圖4-3程序鏈接示意圖4.1.1程序的裝入絕對裝入方式可重定位裝入方式（靜態(tài)重定位）動態(tài)運行時裝入方式（動態(tài)重定位）重要的術(shù)語：

邏輯地址，是目標(biāo)程序中的地址。這種地址一般以0為基地址，順序編址。一個作業(yè)或進(jìn)程的目標(biāo)程序（準(zhǔn)確地說應(yīng)是裝入模塊）的邏輯地址的集合稱為該作業(yè)或進(jìn)程的邏輯地址空間，或稱地址空間或虛擬空間。邏輯地址也稱相對地址或虛擬地址。

物理地址，是物理存貯器的單元地址。物理地址的集合稱為物理地址空間，或稱存儲空間或?qū)嵉刂房臻g。物理地址也稱絕對地址或?qū)嵉刂贰?/p>

重定位：把裝入模塊中指令的邏輯地址以及數(shù)據(jù)的邏輯地址變換成內(nèi)存中物理地址的過程稱為重定位。1.絕對裝入：只能將目標(biāo)模塊裝入指定的內(nèi)存位置缺點：（1）在程序中必須由程序員給出絕對地址?；蛘哒f此時的相對地址和絕對地址一樣；（2）要求程序員對內(nèi)存使用情況非常熟悉。事先知道自己的程序?qū)⒁b在什么地方；（3）只適合于單道程序環(huán)境。例如：某個程序員想在內(nèi)存200處編一個程序：Movax,[204]35h200204Movax,[204]35h裝入程序邏輯地址相對地址內(nèi)存中進(jìn)程絕對地址物理地址….20020402.可重定位的裝入：裝入時將邏輯地址轉(zhuǎn)換為物理地址(重定位)，邏輯地址從0開始。適合于多道程序環(huán)境。地址變換在裝入時一次性完成，以后不變，可看作是靜態(tài)重定位。Movax,[2500]3650100025005000例如:準(zhǔn)備將程序裝入內(nèi)存10000處1000015000Movax,[2500]3651100012500Movax,[12500]365注意：這種裝入后程序不便在內(nèi)存中移動。Why?3.動態(tài)運行時裝入：模塊裝入內(nèi)存后沒有立即重定位，仍然是相對地址；只有當(dāng)CPU執(zhí)行到具有相對地址的代碼時才去重定位，因此是動態(tài)重定位。Movax,[2500]365010002500500010000150001100012500Movax,[2500]3652500相對地址10000重定位寄存器＋12500這種裝入后程序可以內(nèi)存中移動，但需要重定位寄存器的硬件支持。內(nèi)存的分配提綱內(nèi)存分配的總的介紹：連續(xù)分配方式--〉離散分配方式連續(xù)1.單一連續(xù)分配2.固定分區(qū)分配3.動態(tài)分區(qū)分配4.動態(tài)重定位分區(qū)分配離散1.基本分頁存儲管理2.基本分段存儲管理3.段頁式存儲管理對換技術(shù)1.請求分頁存儲管理2.請求分段存儲管理虛擬存儲器4.2連續(xù)分配方式4.2.1單一連續(xù)分配最簡單的一種存儲管理方式將內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用只能用于單用戶、單任務(wù)的操作系統(tǒng)例如：一個容量為256k的內(nèi)存，OS占用32K。操作系統(tǒng)作業(yè)用戶區(qū)0KB32KB96KB256KB-14.2.2固定分區(qū)分配最簡單的多道程序的存儲管理方式主要思想：在單一連續(xù)分配的基礎(chǔ)上，將用戶區(qū)劃分成若干個固定大小的區(qū)，每個區(qū)可以放一個作業(yè)進(jìn)程，多個進(jìn)程并發(fā)。系統(tǒng)一啟動后就已經(jīng)分好了分區(qū)；4.2.2固定分區(qū)分配分區(qū)大小劃分方法：（a）分區(qū)大小相等：缺乏靈活性，當(dāng)程序太小時，內(nèi)存空間浪費；當(dāng)程序太大時，一個分區(qū)又不足以裝入該程序。通常適合于控制多個相同對象的場合。（b）分區(qū)大小不等：將內(nèi)存劃分成含多個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。操作系統(tǒng)用戶區(qū)分區(qū)1分區(qū)2分區(qū)3…操作系統(tǒng)用戶區(qū)分區(qū)5分區(qū)4分區(qū)1分區(qū)2分區(qū)34.2.2固定分區(qū)分配如何分配

（a）分區(qū)使用表：表中包含每個分區(qū)的起始地址、大小、狀態(tài)。

（b）分配方法：在分區(qū)使用表中找出一個能滿足要求的、尚未分配的分區(qū)。將該分區(qū)分給程序、并修改分區(qū)使用表點擊鼠標(biāo)：對1k、9k、33k、121k作業(yè)分配內(nèi)存，并修改分區(qū)狀態(tài)浪費（陰影部分）：7k23k87k211k總浪費：328k操作系統(tǒng)0K20K28K60K180K512k-1分區(qū)1分區(qū)2分區(qū)3分區(qū)4內(nèi)存分區(qū)情況分區(qū)號起始地址大小狀態(tài)1未分配2未分配3未分配4未分配180k20k8k例題：某系統(tǒng)采用固定分區(qū)管理方式，內(nèi)存分區(qū)如圖。現(xiàn)有大小為1k、9k、33k、121k要求進(jìn)入內(nèi)存，畫出他們進(jìn)入內(nèi)存的空間分配情況，說明主存浪費多大。28k60k32k120k332k分區(qū)使用表1k9k33k121k已分配已分配已分配已分配4.2.3動態(tài)分區(qū)分配含義：根據(jù)作業(yè)進(jìn)程的需要，動態(tài)的分配內(nèi)存。系統(tǒng)剛啟動時并不分區(qū)。數(shù)據(jù)結(jié)構(gòu)：用來描述空閑分區(qū)和已分配分區(qū)的情況。常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式：空閑分區(qū)鏈：以鏈表形式記錄每個空閑分區(qū)的情況?？臻e分區(qū)表：以表結(jié)構(gòu)形式記錄每個空閑分區(qū)的情況。例如：操作系統(tǒng)0K20K28K60K180K1k9k33k121k21K37K93K301K空閑分區(qū)表分區(qū)號起始地址大小狀態(tài)1234301k21k7k37k93k23k87k211k空閑空閑空閑空閑4.2.3動態(tài)分區(qū)分配分配算法：（1）首次適應(yīng)算法：從空閑分區(qū)表或分區(qū)鏈（按照地址遞增次序排列）頭上開始查找，找到第一個滿足要求的分區(qū)為止，分配內(nèi)存，余下的部分然仍留在空閑分區(qū)表中。優(yōu)點：傾向于優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū)；保留了高地址部分的空閑分區(qū)。缺點：低地址部分不斷被劃分，留下很多碎片.

例題：例題：已知主存有256k容量，其中os占地端內(nèi)存20k，有下列作業(yè)序列：分析內(nèi)存分配情況和空閑分區(qū)表情況作業(yè)1要求80k；作業(yè)2要求16k；作業(yè)3要求140k

作業(yè)1完成；作業(yè)3完成；作業(yè)4要求60k；作業(yè)5要求120k操作系統(tǒng)0k20k256k-1空閑分區(qū)表分區(qū)號起始地址大小120k236k作業(yè)1來到操作系統(tǒng)0k20k256k-1空閑分區(qū)表分區(qū)號起始地址大小1100k156k作業(yè)1100k剛開始時作業(yè)216k作業(yè)3140k分別來到后空閑分區(qū)表分區(qū)號起始地址大小1100k156k操作系統(tǒng)0k20k256k-1作業(yè)1100k作業(yè)2作業(yè)3116k1116k140k0作業(yè)1完成作業(yè)3完成操作系統(tǒng)0k20k256k-1作業(yè)1100k作業(yè)2作業(yè)3116k空閑分區(qū)表分區(qū)號起始地址大小120k80k2116k140k作業(yè)460k作業(yè)5120k（12k?)分別來到180k20k作業(yè)4作業(yè)51236k20kback4.2.3動態(tài)分區(qū)分配分配算法：（2）最佳適應(yīng)算法：每次為作業(yè)分配內(nèi)存時，總是找一個既能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)。特點：為提高程序中查找速度，常常將分配表按照分區(qū)容量按照從小到大排列，查找時只需要從表首按順序查找最合適的。缺點：都在找最合適的分割，常會剩下一些小碎片

例題：例題：已知內(nèi)存分配情況如下圖。要求填寫空閑分區(qū)表，并分配如下作業(yè)序列作業(yè)4大小2k，作業(yè)5大小6k，作業(yè)6大小2k操作系統(tǒng)作業(yè)10k20k256k-110k25k作業(yè)23k35k45k作業(yè)3156k48k100k分區(qū)號起始地址大小空閑分區(qū)表125k10k245k3k3100k156k作業(yè)4247k1k作業(yè)5131k4k作業(yè)6133k2k改進(jìn)：空閑分區(qū)表（按大小排列，便于程序）分區(qū)號起始地址大小225k10k3100k156k145k3k4.2.3動態(tài)分區(qū)分配分配算法：（3）最壞適應(yīng)算法每次分配總是挑選出分配表（鏈）中最大的分區(qū)進(jìn)行分配（4）循環(huán)首次適應(yīng)算法由首次適應(yīng)算法演變而來（5）快速適應(yīng)算法又稱為分類搜索算法，將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表。

看書自行理解4.2.3動態(tài)分區(qū)分配分配內(nèi)存：在系統(tǒng)利用上述的某種分配算法，從空閑分區(qū)表（鏈）中找到所需大小的空閑分區(qū)之后，應(yīng)進(jìn)行內(nèi)存的分配操作，即：

1.計算當(dāng)前空閑分區(qū)的大小m.size和實際請求的分區(qū)大小u.size之差

2.若m.size-u.size<=size（size是實現(xiàn)規(guī)定的不在分割的剩余分區(qū)的大?。?，則將整個空閑分區(qū)分配給請求者。

3.若m.size-u.size>size，則從該空閑分區(qū)中按請求的大小劃分出一塊內(nèi)存空間分配給請求者，并將剩余的部分仍留在空閑分區(qū)表（鏈）中。

4.將分配區(qū)的首地址返回給調(diào)用者。實際地，內(nèi)存分配的操作流程亦可描述為：4.2.3動態(tài)分區(qū)分配回收內(nèi)存：當(dāng)進(jìn)程運行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首地址，從空閑分區(qū)表（鏈）中找到相應(yīng)的插入點，將回收區(qū)插入到空閑分區(qū)表（鏈）中的適當(dāng)位置。此時，可能出現(xiàn)以下四種情況之一：

1.回收區(qū)前連空閑區(qū)

2.回收區(qū)后連空閑區(qū)

3.回收區(qū)前、后連空閑區(qū)

4.回收區(qū)前、后都不連空閑區(qū)例題：操作系統(tǒng)作業(yè)10k20k256k-110k25k作業(yè)23k35k45k作業(yè)3156k48k100k作業(yè)5作業(yè)6作業(yè)458k68k70k分區(qū)號起始地址大小125k10k245k3k3100k156k空閑分區(qū)表作業(yè)3完成、作業(yè)1完成、作業(yè)2完成、作業(yè)5完成作業(yè)3完成10k245k13k作業(yè)1完成5k120k15k作業(yè)2完成10k120k38k作業(yè)5完成2k268k2k4.2.4動態(tài)重定位分區(qū)分配1.動態(tài)重定位的引入思想：在動態(tài)分區(qū)分配的基礎(chǔ)上引入“緊湊”技術(shù)（整理功能）操作系統(tǒng)作業(yè)10k20k256k-110k25k作業(yè)23k35k45k作業(yè)3156k48k100k操作系統(tǒng)作業(yè)10k20k256k-110k25k作業(yè)23k作業(yè)3156k2.動態(tài)重定位的實現(xiàn)動態(tài)重定位分區(qū)分配算法需與在裝入時，采用“動態(tài)運行時裝入”方式，才能保證程序中相對地址的正確性4.2.4動態(tài)重定位分區(qū)分配3.動態(tài)重定位分區(qū)分配算法4.2.4動態(tài)重定位分區(qū)分配動態(tài)重定位分區(qū)分配算法與動態(tài)分區(qū)分配算法基本相同，差別僅在于：在找不到足夠大的空閑分區(qū)來滿足用戶需求時應(yīng)進(jìn)行“緊湊”。其流程可描述為：優(yōu)點:可以消除碎片,能夠分配更多的分區(qū),有助于多道程序設(shè)計,提高內(nèi)存的利用率。缺點:緊湊花費了大量CPU時間;4.2.5對換(Swapping)1.對換的引入（新教材P129）所謂“對換”，是指把內(nèi)存中暫時不能運行的進(jìn)程或者暫時不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對換是提高內(nèi)存利用率的有效措施。對換又分為：（1）整體對換即對換是以整個進(jìn)程為單位的，又稱進(jìn)程對換。

（2）部分對換

頁面對換：對換是以“頁”為單位進(jìn)行的。

分段對換：對換是以“段”為單位進(jìn)行的。圖

對換兩個進(jìn)程4.2.5對換(Swapping)2.對換空間的管理

為了能對對換區(qū)中的空閑盤塊進(jìn)行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以記錄外存的使用情況。其形式與內(nèi)存在動態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個表目中應(yīng)包含兩項，即對換區(qū)的首址及其大小，它們的單位是盤塊號和盤塊數(shù)。3.進(jìn)程的換出與換入

(1)進(jìn)程的換出。每當(dāng)一進(jìn)程由于創(chuàng)建子進(jìn)程而需要更多的內(nèi)存空間，但又無足夠的內(nèi)存空間等情況發(fā)生時，系統(tǒng)應(yīng)將某進(jìn)程換出。其過程是：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進(jìn)程作為換出進(jìn)程，然后啟動磁盤，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。若傳送過程未出現(xiàn)錯誤，便可回收該進(jìn)程所占用的內(nèi)存空間，并對該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改。4.2.5對換(Swapping)

(2)進(jìn)程的換入。系統(tǒng)應(yīng)定時地查看所有進(jìn)程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程，將其中換出時間(換出到磁盤上)最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無可換入的進(jìn)程或無可換出的進(jìn)程為止。4.3基本分頁存儲管理方式為什么會引入離散分配管理？連續(xù)分配管理（單一連續(xù)、固定分區(qū)、可變分區(qū)、可重定位分區(qū)）中的每個進(jìn)程都是連續(xù)的放在內(nèi)存中、要能運行一定要一段連續(xù)的空間。要求嚴(yán)格、浪費空間、產(chǎn)生很多碎片。雖然有“緊湊”、但開銷大。如果允許將一個進(jìn)程直接分散地裝入到許多不相鄰的分區(qū)中，則無需再進(jìn)行“緊湊”?；谶@一思想而產(chǎn)生了離散分配管理方式，包括：

1.分頁存儲管理方式，此時離散分配的基本單位是頁。在分頁存儲管理方式中，又根據(jù)是否具備頁面對換功能，將分頁存儲管理方式分為：（1）基本的分頁存儲管理方式：要求每個作業(yè)全部裝入內(nèi)存后方能運行。

（2）請求分頁存儲管理方式

2.分段存儲管理方式，此時離散分配的基本單位是段。在分段存儲管理方式中，又根據(jù)是否具備分段對換功能，將分段存儲管理方式分為：（1）基本的分段存儲管理方式

（2）請求分段存儲管理方式4.3基本分頁存儲管理方式分頁的思想：把邏輯地址空間（程序）分成若干個大小相等的片－－頁面或頁，并加以編號0頁、1頁、2頁…….把內(nèi)存也分成和頁面大小相等的若干個物理存儲塊－－物理塊，并加以編號0塊、1塊、2塊……為進(jìn)程分配內(nèi)存時，將進(jìn)程的若干個頁裝入多個不相鄰的塊中。當(dāng)一個用戶程序裝入內(nèi)存時,以頁面為單位進(jìn)行分配。頁面的大小是為2n,通常為1KB,2KB,nKB等。由于進(jìn)程的最后一頁經(jīng)常裝不滿一頁，因而形成不可以利用的碎片，稱為“頁內(nèi)碎片”。要注意什么問題？4.3基本分頁存儲管理方式4.3.1頁面與頁表

1.頁面

1)頁面和物理塊分頁存儲管理，是將一個進(jìn)程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各頁加以編號，從0開始，如第0頁、第1頁等。相應(yīng)地，也把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或頁框(frame)，也同樣為它們加以編號，如0＃塊、1＃塊等等。在為進(jìn)程分配內(nèi)存時，以塊為單位將進(jìn)程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內(nèi)碎片”。

2)頁面大小在分頁系統(tǒng)中的頁面其大小應(yīng)適中。頁面若太小，一方面雖然可使內(nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間，有利于提高內(nèi)存利用率，但另一方面也會使每個進(jìn)程占用較多的頁面，從而導(dǎo)致進(jìn)程的頁表過長，占用大量內(nèi)存；此外，還會降低頁面換進(jìn)換出的效率。然而，如果選擇的頁面較大，雖然可以減少頁表的長度，提高頁面換進(jìn)換出的速度，但卻又會使頁內(nèi)碎片增大。因此，頁面的大小應(yīng)選擇得適中，且頁面大小應(yīng)是2的冪，通常為512B~8KB。4.3.1頁面與頁表2.地址結(jié)構(gòu)分頁地址中的地址結(jié)構(gòu)如下：頁號P位移量（或頁內(nèi)地址）d31121104.3.1頁面與頁表（a）若頁內(nèi)偏移d占12位，表示頁面大小為4kB（b）若頁號P占20位、表示頁面的數(shù)目為1M頁2.地址結(jié)構(gòu)4.3.1頁面與頁表例:某系統(tǒng)頁面大小為1k，已知地址為A=2170Byte（十進(jìn)制）、問頁號p是多少？頁內(nèi)地址d是多少？A=2170=第0頁（1024）＋第1頁(1024）+第2頁(頁內(nèi)122)頁號：P=2頁內(nèi)地址:d=122對某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個邏輯地址空間中的地址為A，頁面的大小為L，則頁號P和頁內(nèi)地址d可按下式求得：2170除以1024＝2….122 例:某系統(tǒng)頁面大小為1k，已知地址為A=4EA5h（16進(jìn)制），問頁號p是多少？頁內(nèi)地址d是多少？方法一：將A=4EA5h轉(zhuǎn)化為十進(jìn)制，利用上例中的方法求解：

A=4EA5h=2013320133/1024=19…….677方法二：由于地址系統(tǒng)是：

本題中頁面大小為1k=1024是需要10位頁內(nèi)偏移位數(shù)0頁號位數(shù)P910位將A=4EA5h轉(zhuǎn)變?yōu)槎M(jìn)制是:0100111010100101頁號：P=010011=19頁內(nèi)偏移地址：d=1010100101=6773.頁表頁表的作用是實現(xiàn)從頁號到物理塊號的地址映射。4.3.1頁面與頁表用戶程序0頁1頁2頁4k4k4k0塊1塊2塊….3塊19塊20塊….物理內(nèi)存3頁4k頁表頁號塊號0113219304.3.2地址變換機(jī)構(gòu)00頁1頁…Movax,3…102047204820492170前面的例子：某系統(tǒng)頁面大小為1k，共有3頁、分別放于內(nèi)存的1、19、3物理塊中。已知邏輯地址為A=2170Byte，問物理塊中的地址是多少？1220塊1塊2塊….3塊19塊20塊….Movax,33x1k+122=3194實際的物理地址變換機(jī)構(gòu)，見下一頁4.3.2地址變換機(jī)構(gòu)頁號塊號0111923a頁表始址頁表長度頁表寄存器頁號頁內(nèi)偏址邏輯地址A=21702122a3>+越界Na+23122物理地址＝31941.基本的地址變換機(jī)構(gòu)例：在一個分頁存儲管理系統(tǒng)中、某個作業(yè)的頁表如下。已知頁面大小為1024字節(jié)。試將邏輯地址1011、2148、3000、4000、5012轉(zhuǎn)化為相應(yīng)的物理地址頁號塊號02132136答：1011－>30592148－>11243000－>19764000－>70725012－>越界非法2.具有快表的地址變換機(jī)構(gòu)4.3.2地址變換機(jī)構(gòu)在基本的地址變換機(jī)構(gòu)中，頁表是放在內(nèi)存中的。此時，CPU存取一個數(shù)據(jù)，需要訪問內(nèi)存2次。

第1次，訪問內(nèi)存中的頁表，找出邏輯地址對應(yīng)的物理地址；第2次，訪問內(nèi)存物理地址處的數(shù)據(jù)。為了提高地址變換速度，可在地址變換機(jī)構(gòu)中增設(shè)一個具有并行查詢能力的特殊高速緩沖寄存器，又稱“快表”，用以存放當(dāng)前訪問的那些頁表項。此時的變換過程可描述為：頁號塊號0111923a頁表始址頁表長度頁表寄存器頁號頁內(nèi)偏址邏輯地址A=21702122a3>+越界Na+23122物理地址＝3194頁號塊號頁表快表2.具有快表的地址變換機(jī)構(gòu)4.3.2地址變換機(jī)構(gòu)2.具有快表的地址變換機(jī)構(gòu)4.3.2地址變換機(jī)構(gòu)例：某頁式系統(tǒng)，頁表存在內(nèi)存中（1）如果對主存一次存取要1.5微秒、存取一個數(shù)據(jù)需要多少時間（2）如果系統(tǒng)有快表，平均命中率為85%，對快表的查找時間忽略為0，問此時存取一個數(shù)據(jù)要多少時間？答（1）2次訪問內(nèi)存2x1.5=3微秒（2）85%命中，只要訪問一次內(nèi)存，直接取得數(shù)據(jù)0.85x1.515％不能命中，要先訪問內(nèi)存快表得物理地址、在訪問內(nèi)存數(shù)據(jù)，共訪問2次3微秒。0.15x3

需要時間：0.85x1.5+0.15x3=1.725微秒4.3.3兩級和多級頁表現(xiàn)代的大多數(shù)計算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下，頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。在某些情況下，是不現(xiàn)實的?？梢圆捎眠@樣兩個方法來解決這一問題：①采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題；②只將當(dāng)前需要的部分頁表項調(diào)入內(nèi)存，其余的頁表項仍駐留在磁盤上，需要時再調(diào)入。1.兩級頁表(Two-LevelPageTable)邏輯地址結(jié)構(gòu)可描述如下：圖4-14兩級頁表結(jié)構(gòu)圖4-15具有兩級頁表的地址變換機(jī)構(gòu)

2.多級頁表對于32位的機(jī)器，采用兩級頁表結(jié)構(gòu)是合適的；但對于64位的機(jī)器，如果頁面大小仍采用4KB即212B，那么還剩下52位，假定仍按物理塊的大小(212位)來劃分頁表，則將余下的42位用于外層頁號。此時在外層頁表中可能有4096G個頁表項，要占用16384GB的連續(xù)內(nèi)存空間。必須采用多級頁表，將外層頁表再進(jìn)行分頁，也是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關(guān)系。對于64位的計算機(jī)，如果要求它能支持2６４(=1844744TB)規(guī)模的物理存儲空間，則即使是采用三級頁表結(jié)構(gòu)也是難以辦到的；而在當(dāng)前的實際應(yīng)用中也無此必要。4.4基本分段存儲管理方式4.4.1分段存儲管理方式的引入引入分段存儲管理方式，主要是為了滿足用戶和程序員的下述一系列需要（新教材P135）：

1)方便編程

2)信息共享

3)信息保護(hù)

4)動態(tài)增長

5)動態(tài)鏈接4.4.2分段系統(tǒng)的基本原理1.分段分段地址中的地址具有如下結(jié)構(gòu)：段號段內(nèi)地址3116150圖4-16利用段表實現(xiàn)地址映射2.段表圖4-17分段系統(tǒng)的地址變換過程3.地址變換機(jī)構(gòu)4.分頁和分段的主要區(qū)別

(1)頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率?；蛘哒f，分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好地滿足用戶的需要。

(2)頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，是由機(jī)器硬件實現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁面；而段的長度卻不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序進(jìn)行編譯時，根據(jù)信息的性質(zhì)來劃分。

(3)分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個記憶符，即可表示一個地址；而分段的作業(yè)地址空間則是二維的，程序員在標(biāo)識一個地址時，既需給出段名，又需給出段內(nèi)地址。4.4.3信息共享(新教材P139)圖4-18分頁系統(tǒng)中共享editor的示意圖圖4-19分段系統(tǒng)中共享editor的示意圖4.4.4段頁式存儲管理方式1.基本原理圖4-20作業(yè)地址空間和地址結(jié)構(gòu)圖4-21利用段表和頁表實現(xiàn)地址映射2.地址變換過程圖4-22段頁式系統(tǒng)中的地址變換機(jī)構(gòu)4.5虛擬存儲器的基本概念4.5.1虛擬存儲器的引入1.常規(guī)存儲器管理方式的特征（新教材P142）一次性，即作業(yè)在運行前需一次性全部裝入內(nèi)存。(2)駐留性，即作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運行結(jié)束。思考這樣兩種情形：(1)有的作業(yè)很大甚至超過了內(nèi)存總?cè)萘浚?2)有大量的作業(yè)要求運行，但內(nèi)存容量不足以容納所有這些作業(yè)。2.局部性原理早在1968年，

Denning.P就曾指出：

(1)程序執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的。

(2)過程調(diào)用將會使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都不超過5。

(3)程序中存在許多循環(huán)結(jié)構(gòu)，這些雖然只由少數(shù)指令構(gòu)成，但是它們將多次執(zhí)行。

(4)程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，如對數(shù)組進(jìn)行操作，它們往往都局限于很小的范圍內(nèi)。局限性又表現(xiàn)在下述兩個方面：

(1)時間局限性。如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過，則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時間局限性的典型原因，是由于在程序中存在著大量的循環(huán)操作。

(2)空間局限性。一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問，即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是程序的順序執(zhí)行。3.虛擬存儲器定義正是由于程序在執(zhí)行時具有局部性規(guī)律，因此應(yīng)用程序在執(zhí)行之前，沒有必要全部一次性裝入內(nèi)存，僅須將那些當(dāng)前要運行的少數(shù)頁面或段先裝入內(nèi)存便可運行，其余部分留在磁盤上。程序在運行時，如果它所要訪問的頁(段)已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去；如果尚未調(diào)入內(nèi)存(缺頁或缺段)，此時程序應(yīng)利用OS提供的請求調(diào)頁(段)功能，將它們調(diào)入內(nèi)存，以使程序能繼續(xù)執(zhí)行下去；如果此時內(nèi)存已滿，無法再裝入新的頁(段)，則還需利用頁(段)的置換功能，將內(nèi)存中暫時不用的頁(段)調(diào)至磁盤上，騰出足夠的內(nèi)存空間后，再將要訪問的頁(段)調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。3.虛擬存儲器定義所謂虛擬存儲器，是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存?？梢姡摂M存儲技術(shù)是一種性能非常優(yōu)越的存儲器管理技術(shù)，故被廣泛地應(yīng)用于大、中、小型機(jī)器和微型機(jī)中。

4.5.2虛擬存儲器的實現(xiàn)方法1.分頁請求系統(tǒng)硬件支持。①請求分頁的頁表機(jī)制，它是在純分頁的頁表機(jī)制上增加若干項而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)；②缺頁中斷機(jī)構(gòu)，即每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存；③地址變換機(jī)構(gòu)，它同樣是在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的。(2)實現(xiàn)請求分頁的軟件。包括用于實現(xiàn)請求調(diào)頁的軟件和實現(xiàn)頁面置換的軟件。4.5.2虛擬存儲器的實現(xiàn)方法2.分段請求系統(tǒng)硬件支持。①請求分段的段表機(jī)制；②缺段中斷機(jī)構(gòu)；③地址變換機(jī)構(gòu)。(2)實現(xiàn)請求分段的軟件。4.5.3虛擬存儲器管理方式的特征(新教材P144)多次性即一個作業(yè)被分成多次調(diào)入內(nèi)存運行。對換性即允許在作業(yè)的運行過程中進(jìn)行換進(jìn)換出。虛擬性即能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實際內(nèi)存容量。這是虛擬存儲器所表現(xiàn)出來的最重要的特征，也是實現(xiàn)虛擬存儲器的最重要的目標(biāo)。4.6請求分頁存儲管理方式4.6.1請求分頁中的硬件支持1.頁表機(jī)制頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址用于指示該頁是否已經(jīng)調(diào)入內(nèi)存用于記錄該頁在一段時間內(nèi)被訪問的次數(shù)，或者記錄該頁最近已有多長時間未被訪問表示該頁在調(diào)入內(nèi)存后是否被修改過，若已被修改，則在置換該頁是，必須將該頁重寫到外存上。用于指出該頁在外存上的地址2.缺頁中斷機(jī)構(gòu)圖4-23涉及6次缺頁中斷的指令與一般中斷相比，缺頁中斷有著明顯的不同，主要表現(xiàn)在以下兩個方面：(1)通常，CPU是在一條指令執(zhí)行完后，才檢查是否有中斷請求到達(dá)。若有，便去響應(yīng)；否則，繼續(xù)執(zhí)行下一條指令。然而，缺頁中斷則是在指令執(zhí)行期間，發(fā)現(xiàn)所要訪問的指令或數(shù)據(jù)不在內(nèi)存時所產(chǎn)生和處理的。(2)一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。如右圖所示。3.地址變換機(jī)構(gòu)圖4-24請求分頁中的地址變換過程4.6.2內(nèi)存分配策略和分配算法在為進(jìn)程分配內(nèi)存時，將涉及到三個問題：最小物理塊數(shù)問題物理塊的分配策略物理塊分配算法4.6.2內(nèi)存分配策略和分配算法1.最小物理塊數(shù)的確定這里所說的最小物理塊數(shù)，是指能保證進(jìn)程正常運行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時，進(jìn)程將無法運行。進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。2.物理塊的分配策略在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。

先為每個進(jìn)程分配一定數(shù)目的物理塊，而OS自身也保持一個空閑物理塊隊列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁時，由系統(tǒng)從物理空閑塊中取出一個物理塊分配給該進(jìn)程，并將欲調(diào)入的頁裝入其中。僅當(dāng)空閑物理塊隊列中的物理塊用完時，OS才從內(nèi)存中選擇一頁調(diào)出，該頁可能是系統(tǒng)中任意進(jìn)程的某一頁。為每個進(jìn)程分配一定數(shù)目的物理塊，且在整個運行期間都不再改變。若進(jìn)程在運行中發(fā)現(xiàn)缺頁，則只能從該進(jìn)程在內(nèi)存中的n個頁面中選出一頁換出，然后再調(diào)入一頁，從而保證該進(jìn)程在所占內(nèi)存空間不變。為每個進(jìn)程分配一定數(shù)目的物理塊，但當(dāng)發(fā)現(xiàn)某進(jìn)程缺頁時，只允許從該進(jìn)程在內(nèi)存的n個頁面中選出一頁換出。但如果該進(jìn)程在運行中頻繁地發(fā)生缺頁中斷，則系統(tǒng)須再為該進(jìn)程分配若干附加的物理塊，直至該進(jìn)程的缺頁率減少到適當(dāng)程度為止；反之，若某進(jìn)程在運行過程中的缺頁率特別低，則可適當(dāng)就減少分配給它的物理塊數(shù)。1)固定分配局部置換：2)可變分配全局置換：3)可變分配局部置換：3.物理塊分配算法在采用固定分配策略時，如何將系統(tǒng)中可供分配的所有物理塊分配給各個進(jìn)程，可采用以下幾種算法：

1)平均分配算法這是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個進(jìn)程。例如，當(dāng)系統(tǒng)中有100個物理塊，有5個進(jìn)程在運行時，每個進(jìn)程可分得20個物理塊。這種方式貌似公平，但實際上是不公平的，因為它未考慮到各進(jìn)程本身的大小。如有一個進(jìn)程其大小為200頁，只分配給它20個塊，這樣，它必然會有很高的缺頁率；而另一個進(jìn)程只有10頁，卻有10個物理塊閑置未用。

2)按比例分配算法這是根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個進(jìn)程，每個進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為：又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進(jìn)程所能分到的物理塊數(shù)為bi，將有：bi應(yīng)該取整，它必須大于最小物理塊數(shù)。

3)考慮優(yōu)先權(quán)的分配算法在實際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。在有的系統(tǒng)中，如重要的實時控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)來為各進(jìn)程分配其物理塊的。頁面調(diào)入策略涉及到三個問題：調(diào)入頁面的時機(jī)從何處調(diào)入頁面頁面調(diào)入的過程4.6.3調(diào)頁策略4.6.3調(diào)頁策略1.何時調(diào)入頁面預(yù)調(diào)頁策略即將那些預(yù)計在不久之后便會訪問的頁面預(yù)先調(diào)入內(nèi)存。但遺憾的是，目前預(yù)調(diào)頁的成功率較低，僅約50%。2)請求調(diào)頁策略根據(jù)請求調(diào)入頁面，此時調(diào)入的頁面肯定是會被訪問的，但這種策略每次僅調(diào)入一頁，故系統(tǒng)開銷相對較大。2.從何處調(diào)入頁面在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)。通常，由于對換區(qū)是采用連續(xù)分配方式，而文件是采用離散分配方式，故對換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁請求時，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況：(1)若系統(tǒng)擁有足夠的對換區(qū)空間，能使得在進(jìn)程運行前，保證與該進(jìn)程有關(guān)的文件，都已從文件區(qū)拷貝到對換區(qū)。這時，若發(fā)生缺頁中斷，則可全部從對換區(qū)調(diào)入所需頁面。(2)系統(tǒng)缺少足夠的對換區(qū)空間，即運行中的進(jìn)程僅是部分頁面拷貝到了對換區(qū)。這時，若發(fā)生缺頁中斷，則分以下兩種情形：凡是不會被修改的頁面，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時，由于它們未被修改而不必再將它們換出（直接覆蓋就行），以后再調(diào)入時，仍從文件區(qū)直接調(diào)入。對于那些可能被修改的頁面，若已經(jīng)拷貝到對換區(qū)，則從對換區(qū)調(diào)入，否則從文件區(qū)調(diào)入。但在將它們換出時，便須調(diào)出到對換區(qū)，以后需要時，再從對換區(qū)調(diào)入。(3)UNIX方式。此時，與進(jìn)程有關(guān)的頁面都放在文件區(qū)，故凡是未運行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運行過但又被換出的頁面，由于是被放在對換區(qū)，因此在下次調(diào)入時，應(yīng)從對換區(qū)調(diào)入。3.頁面調(diào)入過程每當(dāng)程序所要訪問的頁面未在內(nèi)存時，便向CPU發(fā)出一缺頁中斷：(1)中斷處理程序首先保留CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁中斷處理程序。(2)該程序通過查找頁表，得到該頁在外存的物理塊后，

(a)如果此時內(nèi)存能容納新頁，則啟動磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。

(b)如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出。如果該頁未被修改過，可不必將該頁寫回磁盤；如果此頁已被修改，則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存，并修改頁表中的相應(yīng)表項，置其存在位為“1”，并將此頁表項寫入快表中。(3)在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。4.8頁面置換算法4.8.1最佳置換算法和先進(jìn)先出置換算法

1.最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用順序：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

進(jìn)程運行時，先將7，0，1三個頁面裝入內(nèi)存。以后，當(dāng)進(jìn)程要訪問頁面2時，將會產(chǎn)生缺頁中斷。此時OS根據(jù)最佳置換算法，將選擇頁面7予以淘汰。圖4-25利用最佳頁面置換算法時的置換圖引用順序70770170122010320304243230321201201770101頁框(物理塊）2032.先進(jìn)先出(FIFO)頁面置換算法圖4-26利用FIFO置換算法時的置換圖引用順序70770170122010323104430230321013201770201頁框23042042302301271270114.8.2最近最久未使用(LRU)置換算法1.LRU(LeastRecentlyUsed)置換算法的描述圖4-27LRU頁面置換算法引用順序70770170122010320304403230321132201710701頁框4024320321022.LRU置換算法的硬件支持

LRU置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個進(jìn)程在內(nèi)存中各個頁面各有多少時間未被進(jìn)程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有兩類硬件之一的支持：寄存器或棧。2.LRU置換算法的硬件支持

1)寄存器為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為R=Rn-1Rn-2Rn-3…R2R1R0

當(dāng)某頁面首次進(jìn)入內(nèi)存時，相應(yīng)寄存器的各位置為1。此時，定時信號將每隔一定時間將寄存器右移一位。注意，當(dāng)進(jìn)程訪問該頁面時，則將相應(yīng)寄存器的Rn-1位置為1。那么具有最小數(shù)值的寄存器所對應(yīng)的頁面，就是最近最久未使用的頁面。圖4-28某進(jìn)程具有8個頁面時的LRU訪問情況2)棧也可利用一個特殊的棧來保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進(jìn)程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的頁面號，而棧底則是最近最久未是頁面的頁面號。圖4-29用棧保存當(dāng)前使用頁面時棧的變化情況44747074070471704101740107