第4章存儲(chǔ)器管理1-2

1、第四章 存儲(chǔ)器管理,4.1 程序的裝入和鏈接 4.2 連續(xù)分配方式 4.3 基本分頁(yè)存儲(chǔ)管理方式 4.4 基本分段存儲(chǔ)管理方式 4.5 虛擬存儲(chǔ)器的基本概念 4.6 請(qǐng)求分頁(yè)存儲(chǔ)管理方式 4.7 頁(yè)面置換算法 4.8 請(qǐng)求分段存儲(chǔ)管理方式,存儲(chǔ)器管理：指內(nèi)存的管理，外存管理在文件部分講述； 單道程序系統(tǒng)：內(nèi)存被劃分成兩部分：一部分供OS使用，一部分供當(dāng)前正在執(zhí)行的程序使用。多道程序系統(tǒng)：存儲(chǔ)器的用戶

2、部分必須進(jìn)一步地細(xì)分，以適應(yīng)多個(gè)進(jìn)程的要求。細(xì)分的任務(wù)由操作系統(tǒng)動(dòng)態(tài)實(shí)現(xiàn)，這就是存儲(chǔ)器管理。存儲(chǔ)器管理的目的：一是方便用戶使用，二是提高存儲(chǔ)器的利用率。,4.0 基本概念補(bǔ)充,1、存儲(chǔ)器管理功能,主存的分配和回收：系統(tǒng)應(yīng)能記住每個(gè)存儲(chǔ)區(qū)的狀態(tài)；實(shí)施存儲(chǔ)器的分配；回收系統(tǒng)或用戶釋放的存儲(chǔ)區(qū)。提高主存利用率：使多道程序能動(dòng)態(tài)地共享主存，最好能共享主存中的信息。[地址轉(zhuǎn)換或重定位]主存保護(hù)：保證進(jìn)入主存的各道作業(yè)都在自己的存儲(chǔ)空間內(nèi)運(yùn)行

3、，互不干擾。由硬件和軟件配合完成。主存擴(kuò)充：借助于虛擬存儲(chǔ)技術(shù)，為用戶提供比主存空間大的地址空間。,,內(nèi)存的每個(gè)存儲(chǔ)單元都有一個(gè)編號(hào)，這種編號(hào)稱為內(nèi)存地址（或稱為物理地址，絕對(duì)地址）。內(nèi)存地址的集合稱為內(nèi)存空間（或物理地址空間）。例如，我們常說內(nèi)存為：512MB要求用戶用內(nèi)存地址編程是非常困難的，尤其是在多道程序設(shè)計(jì)的環(huán)境中（不知道）。,2、地址映射(地址重定位),用戶編程所用的地址稱為邏輯地址（或程序地址，或虛地址），由邏輯地址

4、組成的空間稱為邏輯地址空間（或程序地址空間）。我們把用戶程序裝入內(nèi)存時(shí)，或在程序執(zhí)行時(shí)，對(duì)有關(guān)指令或數(shù)據(jù)地址的修改稱為從程序地址到內(nèi)存地址的地址映射，或稱為地址重定位。,1100,地址映射的方式,靜態(tài)地址映射：1）程序被裝入內(nèi)存時(shí)由操作系統(tǒng)的連接裝入程序完成程序的邏輯地址到內(nèi)存地址的轉(zhuǎn)換；2）地址轉(zhuǎn)換工作是在程序執(zhí)行前由裝入程序集中一次完成。假定程序裝入內(nèi)存的首地址為BR，程序地址為VR，內(nèi)存地址為MR，則地址映射按下式進(jìn)行

5、：MR=BR+VR,把程序裝入起始地址為1000的內(nèi)存區(qū),…,,,,,,,,,,,,Mov r1,[500],…,1234,…,0,100,500,600,Mov r1,[1500],0,1000,1100,1500,1600,1234,…,…,…,…,,作業(yè)的地址空間,存儲(chǔ)空間,裝入程序,靜態(tài)映射優(yōu)缺點(diǎn),優(yōu)點(diǎn)：不需要硬件的支持，簡(jiǎn)單易實(shí)現(xiàn)，成本低；缺點(diǎn)：程序必須占用連續(xù)的內(nèi)存空間；一旦程序裝入后不能移動(dòng)；主存利用率低；難以做到程序和

6、數(shù)據(jù)的共享。,動(dòng)態(tài)地址映射（重定位）,動(dòng)態(tài)地址重定位：在程序執(zhí)行的過程中，每次將要訪問的指令或數(shù)據(jù)邏輯地址轉(zhuǎn)換為內(nèi)存地址。動(dòng)態(tài)映射方法：裝入程序把程序和數(shù)據(jù)原樣裝入到已分配的存儲(chǔ)區(qū)中，然后把這個(gè)存儲(chǔ)區(qū)的起始地址送入重定位寄存器中。在程序執(zhí)行時(shí)，再將相對(duì)地址轉(zhuǎn)換成絕對(duì)地址。硬件支持：在動(dòng)態(tài)地址重定位機(jī)構(gòu)中，有一個(gè)基地址寄存器BR和一個(gè)程序地址寄存器VR，一個(gè)內(nèi)存地址寄存器MR。轉(zhuǎn)換過程：MR=BR+VR,把程序裝入起始地址為1000

7、的內(nèi)存區(qū),,…,,,,,…,1234,…,0,100,500,599,作業(yè)的地址空間,,,,,,,,0,1000,1100,1500,1599,1234,…,…,…,…,存儲(chǔ)空間,1000,+,,,,重定位寄存器,邏輯地址VR,,物理地址MR,MOV r1，[50],MOV r1，[50],動(dòng)態(tài)地址映射的過程,程序裝入內(nèi)存后，它所占用的內(nèi)存區(qū)的首地址由系統(tǒng)送入基地址寄存器BR中。在程序執(zhí)行的過程中，若要訪問內(nèi)存，將訪問的邏輯地址送入V

8、R中。 地址轉(zhuǎn)換機(jī)構(gòu)把VR和BR中的內(nèi)容相加，并將結(jié)果送入MR中，作為實(shí)際訪問的地址。,動(dòng)態(tài)重定位優(yōu)缺點(diǎn),優(yōu)點(diǎn)：1）程序占用的內(nèi)存空間是動(dòng)態(tài)可變的，當(dāng)程序從某個(gè)存儲(chǔ)區(qū)移到另一個(gè)區(qū)域時(shí)，只需要修改相應(yīng)的寄存器BR的內(nèi)容即可；2）一個(gè)程序不一定要求占用一個(gè)連續(xù)的內(nèi)存空間，可以部分地裝入程序運(yùn)行；4）便于多個(gè)進(jìn)程共享同一個(gè)程序的代碼。動(dòng)態(tài)地址重定位的代價(jià)：1）需要硬件的支持；2）實(shí)現(xiàn)存儲(chǔ)管理的軟件算法較為復(fù)雜。,4.1存儲(chǔ)器的層次結(jié)構(gòu),4

9、.1.1多級(jí)存儲(chǔ)器結(jié)構(gòu),4.1.2主存儲(chǔ)器和寄存器4.1.3高速緩存和磁盤緩存,4.2 程序的裝入和鏈接,圖 4-1 對(duì)用戶程序的處理步驟,可執(zhí)行程序（文件）,,編譯,鏈接,裝入,二進(jìn)制內(nèi)存映像,,4.1.1 程序的裝入,1. 絕對(duì)裝入方式(Absolute Loading Mode),程序中所使用的絕對(duì)地址，既可在編譯或匯編時(shí)給出， 也可由程序員直接賦予；編譯程序生成的目標(biāo)模塊其邏輯地址與要裝入內(nèi)存的物理地址相同；缺點(diǎn)：?jiǎn)蔚莱?/p>

10、序可用，多道程序環(huán)境不能用。,采用絕對(duì)地址裝入，目前很少使用,2. 可重定位裝入方式(Relocation Loading Mode),圖 4-2 作業(yè)裝入內(nèi)存時(shí)的情況,又稱靜態(tài)重定位：地址變換在裝入時(shí)一次完成，其后不能移動(dòng)。,邏輯地址（相對(duì)地址）,物理地址（絕對(duì)地址）,LOAD 1,12500,3. 動(dòng)態(tài)運(yùn)行時(shí)裝入方式(Denamle Run-time Loading),動(dòng)態(tài)運(yùn)行時(shí)裝方式：裝入內(nèi)存后的所有地址都仍是相對(duì)地址；邏輯地址到

11、物理地址的變換要推遲到程序真正執(zhí)行時(shí)才進(jìn)行；為使地址轉(zhuǎn)換不影響程序執(zhí)行速度，必須使用硬件支持。,4.2.2 程序的鏈接,1. 靜態(tài)鏈接方式(Static Linking),圖 4-3 程序鏈接示意圖,鏈接前，每個(gè)模塊都有各自的相對(duì)起始地址0,鏈接后，每個(gè)模塊使用同一個(gè)相對(duì)起始地址0,名空間,邏輯地址空間,解決：對(duì)相對(duì)地址進(jìn)行修改；變換外部調(diào)用符號(hào),2. 裝入時(shí)動(dòng)態(tài)鏈接(Loadtime Dynamic Linking),基本思想：源

12、程序被編譯生成的目標(biāo)模塊，是在裝入內(nèi)存時(shí)，邊裝入邊連接。裝入程序根據(jù)外部模塊調(diào)用而逐個(gè)裝入和連接。裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)便于修改和更新：各個(gè)模塊的修改極易編譯和連接；便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享：將內(nèi)存中的一個(gè)模塊可以連接到多個(gè)程序中。要運(yùn)行的程序都必須在裝入時(shí)，全部連接調(diào)入內(nèi)存。,3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-time Dynamic Linking),動(dòng)態(tài)鏈接方式：將對(duì)某些模塊的鏈接推遲到執(zhí)行時(shí)才實(shí)施，亦即，在執(zhí)行過程中，

13、當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。特點(diǎn)如下：特點(diǎn)：凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。,,4.3 連續(xù)分配方式,4.2.1 單一連續(xù)分配,特征：最簡(jiǎn)單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中；常把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存

14、的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間， 提供給用戶使用。,4.2.2 固定分區(qū)分配,1. 劃分分區(qū)的方法,分區(qū)大小相等， 即使所有的內(nèi)存分區(qū)大小相等。缺點(diǎn)：缺乏靈活性，大作業(yè)無法運(yùn)行，小作業(yè)浪費(fèi)空間。分區(qū)大小不等，即劃分為小、中、大不等的固定分區(qū)。優(yōu)點(diǎn)：靈活性好。,分配方法：將用戶空間劃分為若干個(gè)固定大小的區(qū)域，在每個(gè)分區(qū)中裝入一道作業(yè)；有幾個(gè)分區(qū)，就有幾道并發(fā)的作業(yè)；有空閑分區(qū)時(shí)，可調(diào)入一適當(dāng)大小的作業(yè)；最簡(jiǎn)單的一種多

15、道程序存儲(chǔ)管理方法。,2. 內(nèi)存分配 ：為了便于內(nèi)存分配，將分區(qū)按照大小排隊(duì)，并建立一個(gè)分區(qū)表。如圖所示。當(dāng)為作業(yè)分配空間時(shí)，分配程序按照此表檢索以合適分區(qū)分配；否則，拒絕分配。缺點(diǎn)：空間浪費(fèi)。,圖 4-4 固定分區(qū)使用表,20K,4.2.3 動(dòng)態(tài)分區(qū)分配,1. 分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu),空閑分區(qū)表。 (2) 空閑分區(qū)鏈。,圖 4-5 空閑鏈結(jié)構(gòu),分配思想：根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)的為進(jìn)程分配（切分）內(nèi)存空間，及需要多大，分配多大。提

16、高內(nèi)存的利用率。,,2. 分區(qū)分配算法,首次適應(yīng)算法FF：空閑分區(qū)按地址遞增成鏈表；每次分配從鏈?zhǔn)滓来尾檎乙豢臻g首次滿足作業(yè)的空閑分區(qū)；再?gòu)脑摲謪^(qū)中切出與作業(yè)等量的空間分之，余者掛到鏈表中；若找不到滿足作業(yè)空間要求的空閑分區(qū)，分配失敗。優(yōu)缺點(diǎn)：低地址部分將產(chǎn)生多個(gè)較小的空閑分區(qū)（碎片），增加分配開銷。,問題：如何從空閑分區(qū)表或鏈表中，選擇一分區(qū)分給作業(yè)，常用的算法如下：,2. 分區(qū)分配算法,循環(huán)首次適應(yīng)算法：該算法是由首次適應(yīng)算

17、法演變而成的，區(qū)別僅是從上次已分配分區(qū)的下一個(gè)分區(qū)依次查找首次滿足作業(yè)的空閑分區(qū)，并從中劃分出作業(yè)需要的分區(qū)。實(shí)現(xiàn)方法：起始循環(huán)指針+循環(huán)空閑分區(qū)鏈表最佳適應(yīng)算法：空閑鏈表依照空間大小排列，每次從鏈?zhǔn)诪樽鳂I(yè)找一個(gè)大小最合適的分區(qū)分配。缺點(diǎn)：最佳適應(yīng)必將產(chǎn)生最小的空閑碎片。,3. 分區(qū)分配操作,分配內(nèi)存操作 分配操作如左圖所示,回收內(nèi)存操作 回收的分區(qū)有4種情況：與前、后、前后空分區(qū)相鄰，如下圖所示。,圖 4-7 內(nèi)存

18、回收時(shí)的情況,當(dāng)回收分區(qū)與前后空閑分區(qū)均不相鄰時(shí)，為回收分區(qū)建立一個(gè)空閑分區(qū)結(jié)點(diǎn)，并插入鏈表適當(dāng)位置。,,,,,,回收分區(qū),……,……,4.2.4 可重定位分區(qū)分配,1. 動(dòng)態(tài)重定位的引入：動(dòng)態(tài)回收碎片，將小而不可用的空閑分區(qū)拼接成較大的一個(gè)空閑分區(qū)。移動(dòng)作業(yè)分區(qū)，必然要重定位。,圖 4-8 緊湊的示意,2.動(dòng)態(tài)重定位的實(shí)現(xiàn)：作業(yè)在內(nèi)存中仍保持邏輯地址，在執(zhí)行時(shí)再實(shí)施重定位。具體過程如下圖。,圖 4-9 動(dòng)態(tài)重定位示意圖,3. 動(dòng)

19、態(tài)重定位分區(qū)分配算法：在動(dòng)態(tài)分區(qū)算法增加了回收碎片的功能。,圖 4-10 動(dòng)態(tài)分區(qū)分配算法流程圖,作業(yè)4-1,P159 ： 4、5、6,4.2.5 對(duì)換(Swapping),1. 對(duì)換的引入,對(duì)換定義：對(duì)換是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)調(diào)入內(nèi)存。對(duì)換目的：提高內(nèi)存的利用率。進(jìn)程對(duì)換：如果對(duì)換是以整個(gè)進(jìn)程為單位進(jìn)行的，則稱

20、為進(jìn)程對(duì)換或整體對(duì)換；頁(yè)面對(duì)換：如果對(duì)換是以頁(yè)或段為單位進(jìn)行的，稱為頁(yè)面對(duì)換或分段對(duì)換，統(tǒng)稱部分對(duì)換。在實(shí)現(xiàn)虛擬存儲(chǔ)系統(tǒng)時(shí)候，依靠頁(yè)面或分段對(duì)換。,2. 對(duì)換空間的管理,實(shí)現(xiàn)進(jìn)程對(duì)換系統(tǒng)必須具備三個(gè)功能：對(duì)換空間管理、進(jìn)程的換出和進(jìn)程的換入。首先研究對(duì)換空間管理：將外存磁盤空間劃分為文件區(qū)和對(duì)換區(qū)：文件區(qū)用于存放文件，管理以提高存儲(chǔ)空間的利用率為目的；后者用于存儲(chǔ)對(duì)換的進(jìn)程，故應(yīng)以提高對(duì)換速度為目標(biāo)。對(duì)換區(qū)空間管理：建立對(duì)換區(qū)空

21、閑空間分區(qū)表（鏈）數(shù)據(jù)結(jié)構(gòu)。其形式與內(nèi)存動(dòng)態(tài)分區(qū)分配方式中的空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個(gè)表項(xiàng)中應(yīng)包含兩項(xiàng)，對(duì)換區(qū)的首址及其大小，它們的單位是盤塊號(hào)和盤塊數(shù)。,2. 對(duì)換空間的管理,對(duì)換區(qū)分配：采用連續(xù)分配，雷同內(nèi)存動(dòng)態(tài)分區(qū)方式的分配算法：可用首次適應(yīng)算法，循環(huán)首次適應(yīng)算法或最佳適應(yīng)算法。對(duì)換區(qū)回收：也與內(nèi)存動(dòng)態(tài)分區(qū)回收算法雷同，要考慮回收區(qū)與前后地址相鄰（磁盤塊號(hào)）分區(qū)的合并。,3. 進(jìn)程的換出與換入,進(jìn)程的換出：

22、每當(dāng)創(chuàng)建一新進(jìn)程而又無足夠的內(nèi)存空間時(shí)，系統(tǒng)應(yīng)將某進(jìn)程換出。 換出過程：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，并將該進(jìn)程的程序和數(shù)據(jù)安全傳送到磁盤的對(duì)換區(qū)上；然后回收該進(jìn)程所占用的內(nèi)存空間，并對(duì)該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改（改什么？）。 進(jìn)程的換入：系統(tǒng)定時(shí)找出“靜止就緒”狀態(tài)的進(jìn)程，并將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程換入，直至已無可換入的進(jìn)程,4.3 基本分頁(yè)存儲(chǔ)管理方式,問題：由于為進(jìn)程連續(xù)分配內(nèi)存空間

23、，將產(chǎn)生大量碎片；為了利用碎片必須將其合并，又需要系統(tǒng)開銷。能否給進(jìn)程離散（不連續(xù)）地分配內(nèi)存空間，解決這些問題？離散分配：當(dāng)前使用最多的內(nèi)存分配方式是分頁(yè)管理方式和分段管理方式；分頁(yè)是頁(yè)面為單位進(jìn)行內(nèi)存分配，分段方式是以段為單位進(jìn)行內(nèi)存分配?；痉猪?yè)（段）存儲(chǔ)管理方式：如果分頁(yè)或分段存儲(chǔ)管理方式中不具備頁(yè)面或分段對(duì)換功能，將其稱之為基本分頁(yè)或基本分段存儲(chǔ)管理方式。,4.3.1 頁(yè)面與頁(yè)表,1. 頁(yè)面與物理塊頁(yè)面：將一個(gè)進(jìn)程的邏

24、輯地址空間分成若干個(gè)大小相等的片，稱為頁(yè)面或頁(yè)，并為各頁(yè)順序編號(hào)為0、1、2、…、n。物理塊：把內(nèi)存空間分成與頁(yè)面相同大小的若干個(gè)存儲(chǔ)塊，稱為(物理)塊或頁(yè)框(frame)， 也同樣為它們加以編號(hào)，如0＃塊、1＃塊等等。內(nèi)存分配原理：在為進(jìn)程分配內(nèi)存時(shí)，以頁(yè)面為單位給進(jìn)程離散分配與頁(yè)面數(shù)等量的物理塊，并分別裝入到相應(yīng)的物理塊中（全部轉(zhuǎn)入） 頁(yè)內(nèi)碎片：由于進(jìn)程的最后一頁(yè)經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁(yè)內(nèi)碎片”。,舉例

25、：如左圖所示，按照基本分頁(yè)存儲(chǔ)管理方式為進(jìn)程分配內(nèi)存空間。設(shè)頁(yè)面大小為1KB,,頁(yè)面大小設(shè)定：在分頁(yè)系統(tǒng)中的頁(yè)面其大小應(yīng)適中，且頁(yè)面大小應(yīng)是2的冪，通常為512 B~8 KB。 頁(yè)面大小利弊：若頁(yè)面太小，內(nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間，提高內(nèi)存利用率；但另一方面也會(huì)使每個(gè)進(jìn)程占用較多的頁(yè)面，從而導(dǎo)致進(jìn)程的頁(yè)表過長(zhǎng)，占用大量?jī)?nèi)存等；若頁(yè)面較大，可以減少頁(yè)表的長(zhǎng)度，節(jié)省內(nèi)存，但卻又會(huì)使頁(yè)內(nèi)碎片增大。,2、邏輯地址結(jié)構(gòu),最大頁(yè)面

26、數(shù)： 220=1M個(gè)頁(yè)面大?。?212=4KB邏輯空間： 0~232-1一維的，并針對(duì)程序員,,邏輯地址空間中的地址為A，頁(yè)面大小為L(zhǎng)，則有：,P=INT[A/L],,d=[A] MOD L,,例：A=2170B，L=1KB時(shí)，則有P=2，d=122,3、頁(yè)表分頁(yè)存儲(chǔ)管理方式按照進(jìn)程頁(yè)面的多少，為進(jìn)程離散分配相同數(shù)量的物理塊，為了記錄每一頁(yè)所分配的物理塊，必須為每個(gè)進(jìn)程建立一個(gè)頁(yè)表每個(gè)進(jìn)程一個(gè)頁(yè)表，每個(gè)頁(yè)面一個(gè)表項(xiàng)

27、；表項(xiàng)：頁(yè)號(hào)：0、1、2、…、n；塊號(hào)：離散分配形成；存取控制：讀寫控制,頁(yè)表示意圖,圖 4-11 頁(yè)表的作用,基本分頁(yè)系統(tǒng)多進(jìn)程內(nèi)存分配示意圖,4.3.2 地址變換機(jī)構(gòu),基本的地址變換機(jī)構(gòu) ：實(shí)現(xiàn)邏輯地址向物理地址的轉(zhuǎn)換。由于頁(yè)內(nèi)地址與塊內(nèi)地址一一對(duì)應(yīng)，所以地址轉(zhuǎn)換關(guān)鍵是將邏輯地址中的頁(yè)號(hào)轉(zhuǎn)換為內(nèi)存中的物理塊號(hào)。轉(zhuǎn)換機(jī)構(gòu)設(shè)施：頁(yè)表寄存器：存放進(jìn)程頁(yè)表在內(nèi)存中的起地址和頁(yè)表長(zhǎng)度（進(jìn)程不執(zhí)行時(shí)放在PCB中，執(zhí)行時(shí)調(diào)入寄存器中）；物理地

28、址寄存器：存放轉(zhuǎn)換后的物理地址（內(nèi)存地址）；查找表項(xiàng)：表項(xiàng)地址=頁(yè)表起始地址+頁(yè)號(hào)*表項(xiàng)長(zhǎng)度；地址轉(zhuǎn)換過程如下圖。,圖 4-12 分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu),[例] 說明運(yùn)行進(jìn)程的地址變換過程。 如下圖所示，進(jìn)程程序地址空間共有7個(gè)頁(yè)，每頁(yè)的大小為1024。其對(duì)應(yīng)的主存塊在頁(yè)表中已列出。假定頁(yè)表在主存始址為500。若該程序從第0頁(yè)開始運(yùn)行，且現(xiàn)程序計(jì)數(shù)器內(nèi)容為：,,,0,100,程序計(jì)數(shù)器：,邏輯地址,例：有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，

29、有一作業(yè)大小是8KB，頁(yè)大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。,虛地址 7145P＝7145 ％ 2048 ＝3W＝7145 mod 2048 ＝1001MR=5*2048+1001=11241虛地址7145的內(nèi)存地址是：11241,虛地址 3412P＝3412 ％ 2048 ＝1W＝3412 mod 2048 ＝1364MR=9*2048+1364=19796

30、虛地址3412的內(nèi)存地址是：19796,2、具有快表的地址變換機(jī)構(gòu)問題：兩次訪問內(nèi)存(頁(yè)表，數(shù)據(jù))，運(yùn)行速度下降一半；解決方法：聯(lián)想存儲(chǔ)器，快表，存放當(dāng)前訪問的頁(yè)表項(xiàng)；思路：將已訪問的頁(yè)號(hào)的頁(yè)表項(xiàng)放入快表，方便下次訪問，提高訪問速度，爭(zhēng)取一次訪問內(nèi)存；聯(lián)想存儲(chǔ)器：通常只要設(shè)定8～16個(gè)寄存器作為聯(lián)想存儲(chǔ)器，即可使程序執(zhí)行速度大大提高。,具有快表的地址變換過程示意圖,圖 4-13 具有快表的地址變換機(jī)構(gòu),4.3.3 兩級(jí)和多級(jí)

31、頁(yè)表,問題：現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下，頁(yè)表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。例如，對(duì)于一個(gè)具有32位邏輯地址空間的分頁(yè)系統(tǒng)，規(guī)定頁(yè)面大小為4 KB即212 B，則在每個(gè)進(jìn)程頁(yè)表中的頁(yè)表項(xiàng)可達(dá)1兆個(gè)之多，而且還要求是連續(xù)的。解決辦法：① 采用離散分配方式存放頁(yè)表；② 使用對(duì)換方式調(diào)入、調(diào)出頁(yè)表。,1. 兩級(jí)頁(yè)表(Two-Level Page Table),邏輯地址結(jié)構(gòu)可描述

32、如下：頁(yè)面大小為4K（12位），每頁(yè)包含1024個(gè)頁(yè)表項(xiàng)（P2，占10位）；總共有1024個(gè)分頁(yè)（P1，占10位））,圖 4-14 兩級(jí)頁(yè)表結(jié)構(gòu),圖 4-15 具有兩級(jí)頁(yè)表的地址變換機(jī)構(gòu),二級(jí)頁(yè)表地址轉(zhuǎn)換過程示意圖,2. 多級(jí)頁(yè)表 對(duì)于32位的機(jī)器，采用兩級(jí)頁(yè)表結(jié)構(gòu)是合適的；但對(duì)于64位的機(jī)器，如果頁(yè)面大小仍采用4 KB即212 B，那么還剩下52位， 假定仍按物理塊的大小(212位)來劃分頁(yè)表，則將余下的42位用于外層頁(yè)

33、號(hào)。此時(shí)在外層頁(yè)表中可能有4096 G個(gè)頁(yè)表項(xiàng)， 要占用16384 GB的連續(xù)內(nèi)存空間。 必須采用多級(jí)頁(yè)表，將外層頁(yè)表再進(jìn)行分頁(yè)，也是將各分頁(yè)離散地裝入到不相鄰接的物理塊中，再利用第2級(jí)的外層頁(yè)表來映射它們之間的關(guān)系。 對(duì)于64位的計(jì)算機(jī)，如果要求它能支持2６４(=1844744 TB)規(guī)模的物理存儲(chǔ)空間，則即使是采用三級(jí)頁(yè)表結(jié)構(gòu)也是難以辦到的；而在當(dāng)前的實(shí)際應(yīng)用中也無此必要。,,例題一一個(gè)由8個(gè)頁(yè)面，每頁(yè)有1024個(gè)

34、字節(jié)組成的邏輯空間，把它裝入有32個(gè)物理塊的存儲(chǔ)器中，問：(1)邏輯地址需要多少位二進(jìn)制來表示？(2)絕對(duì)地址需要多少位二進(jìn)制來表示？,解：頁(yè)面數(shù)：8=23 塊數(shù)：32= 25 頁(yè)面長(zhǎng)度：1024=210,頁(yè)面長(zhǎng)度決定了頁(yè)內(nèi)地址的長(zhǎng)度0~9，10位；頁(yè)面數(shù)決定了頁(yè)號(hào)的地址長(zhǎng)度0~2，3位；塊數(shù)決定了塊號(hào)的地址程度0~4，5位；塊內(nèi)地址與頁(yè)內(nèi)地址的長(zhǎng)度相等；故： 邏輯地址需要用13位來表示；

35、 絕對(duì)地址需要用15位來表示；,習(xí)題二：設(shè)有一分頁(yè)管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁(yè)，每頁(yè)2048字節(jié)，內(nèi)存總共有8個(gè)存儲(chǔ)塊，試問邏輯地址至少應(yīng)為多少位？物理地址至少應(yīng)為多少位？?jī)?nèi)存空間共有多大？,答案：邏輯地址至少15位；物理地址至少14位；內(nèi)存空間共有8*2048=214,習(xí)題三：現(xiàn)有一分頁(yè)管理系統(tǒng)，其頁(yè)表存放在內(nèi)存中。若對(duì)內(nèi)存的一次存取需要1.5ms，試問實(shí)現(xiàn)一次頁(yè)面訪問的存取時(shí)間是多少？現(xiàn)有一個(gè)

36、加有快表的系統(tǒng)，快表的平均命中率為80%，當(dāng)頁(yè)表項(xiàng)在快表中時(shí)，其查找時(shí)間忽略為0，試問此時(shí)的存取時(shí)間是多少？若快表的平均命中率為90%時(shí)，存取時(shí)間又為多少呢？,解：若頁(yè)表存在內(nèi)存，則一個(gè)頁(yè)面訪問需要訪問內(nèi)存2次，已知一次存取時(shí)間為1.5ms，則一次頁(yè)面訪問的存取時(shí)間為3ms.若系統(tǒng)中有快表，則兩種情況：需要訪問的頁(yè)面在快表中：訪問內(nèi)存1次；需要訪問的頁(yè)面不在快表中：訪問內(nèi)存2次；若快表的命中率為80%則：訪問時(shí)間：