1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,第四章 存儲(chǔ)管理,4.1 概述 一、存儲(chǔ)器的層次：三級(jí)存儲(chǔ)器結(jié)構(gòu),本章主要討論幾種常用的內(nèi)存管理技術(shù)。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,二、用戶程序的處理過程,4.1 概述,絕對(duì)裝入方式：按模塊中的地址，將程序和數(shù)據(jù)裝入到內(nèi)存對(duì)應(yīng)位置。 可重定位方式：在裝入程序時(shí)，根據(jù)當(dāng)時(shí)內(nèi)存的實(shí)際使用情況，重新調(diào)整裝入的內(nèi)存位置，把程序裝入到內(nèi)存的適當(dāng)?shù)胤健?數(shù)學(xué) 模型,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,三、地址重定位（映射）-Relacation 1. 術(shù)語,4.1 概述,名字空間：用戶源程序中由符號(hào)指令，數(shù)據(jù)說明等符號(hào)名字構(gòu)成的空間,經(jīng)匯編或編譯后其目標(biāo)程序占有的地址范圍稱為地址

2、空間；這些地址編號(hào)是相對(duì)于起始地址（0）而定的，稱為邏輯地址或相對(duì)地址。,存儲(chǔ)空間是目標(biāo)程序裝入內(nèi)存后占用的一系列物理單元的集合。 這些物理單元編號(hào)稱為物理地址或絕對(duì)地址。,把程序中的邏輯地址變成內(nèi)存中的物理地址的過程。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,2. 重定位的兩種方式 靜態(tài)重定位:在程序執(zhí)行之前進(jìn)行；由重定位裝配程序根據(jù)將要裝入的內(nèi)存起始位置直接修改模塊中的有關(guān)使用地址的指令。 固定在內(nèi)存的某個(gè)連續(xù)區(qū)域，不能再移動(dòng)。 重定位裝配程序來實(shí)現(xiàn)(一對(duì)界地址寄存器實(shí)現(xiàn)保護(hù)),三、地址重定位（映射）,內(nèi)存中起始地址,內(nèi)存中結(jié)束地址,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,三、地址重定位（映射）,特點(diǎn)：程序執(zhí)

3、行前一次性全部完成。 性能分析： 優(yōu)點(diǎn)-實(shí)現(xiàn)簡(jiǎn)單，不需要硬件機(jī)構(gòu)； 缺點(diǎn)-程序重定位之后就不能再在內(nèi)存中移動(dòng)；要求程序的存儲(chǔ)空間是連續(xù)的，不能放在若干個(gè)不連續(xù)的區(qū)域內(nèi)；各個(gè)用戶進(jìn)程很難共享內(nèi)存中的同一程序副本。,例：假設(shè)已知一段程序的經(jīng)匯編連接后邏輯地址空間如圖所示，采用靜態(tài)地址重定位，上，下界地址寄存器如圖，試給出其存儲(chǔ)空間圖。,與地址有關(guān)的量要做變更 X=x+D,1300,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,(2)動(dòng)態(tài)重定位 時(shí)機(jī)：在程序執(zhí)行過程中進(jìn)行，當(dāng)CPU訪問內(nèi)存指令時(shí)由動(dòng)態(tài)變換機(jī)構(gòu)自動(dòng)進(jìn)行地址轉(zhuǎn)換。 實(shí)現(xiàn)：目標(biāo)模塊不加任何修改而裝入內(nèi)存，由定位寄存器和加法器硬件完成地址轉(zhuǎn)換。,三、地址重

4、定位（映射）,例：假設(shè)已知一段程序的經(jīng)匯編連接后邏輯地址空間如圖所示，采用動(dòng)態(tài)地址重定位，試給出其存儲(chǔ)空間圖。,程序不做任何修改裝入內(nèi)存，在執(zhí)行時(shí)訪問內(nèi)存時(shí)利用重定位寄存器進(jìn)行地址重定位,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,特點(diǎn)：程序執(zhí)行時(shí)動(dòng)態(tài)地完成。 性能分析： 優(yōu)點(diǎn)-程序裝入內(nèi)存之后再搬遷也不會(huì)影響其正確執(zhí)行；每個(gè)目標(biāo)模塊裝入的存儲(chǔ)區(qū)不必順序相鄰，只需要各自對(duì)應(yīng)的定位寄存器即可。-是虛擬存儲(chǔ)器技術(shù)的基礎(chǔ) 缺點(diǎn)-需要硬件支持。,三、地址重定位（映射）,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,四、存儲(chǔ)管理的功能 內(nèi)存的分配與回收； 地址重定位； 內(nèi)存信息的共享與保護(hù)； 內(nèi)存的擴(kuò)充（滿足用戶對(duì)內(nèi)存超容量要求）；

5、,4.1 概述,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,1。可由CPU調(diào)用執(zhí)行的程序所對(duì)應(yīng)的地址空間為 。 A. 名稱空間B. 虛擬地址空間 C. 相對(duì)地址空間D. 物理地址空間,2。當(dāng)程序經(jīng)過編譯或者匯編以后，形成了一種由機(jī)器指令組成的集合被稱為 。 A. 源程序B. 目標(biāo)程序 C. 可執(zhí)行程序D. 非執(zhí)行程序,3。目標(biāo)程序指令的順序都以0作為一個(gè)參考地址，這些地址被稱為 。 A. 虛擬地址B. 物理地址 C. 絕對(duì)地址D. 重定位地址,4。若調(diào)用指令LOAD A,Data，經(jīng)動(dòng)態(tài)重定位后，其對(duì)應(yīng)指令代碼 。 A. 保持不變B. 會(huì)變化，隨裝入起始地址變化而變化 C. 會(huì)變化，固定在某一存儲(chǔ)區(qū)域D.

6、重定位項(xiàng)等于重定位寄存器內(nèi)容,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,目的：為了滿足多道程序設(shè)計(jì)思想。 方法：將內(nèi)存劃分為若干個(gè)分區(qū)，每個(gè)分區(qū)分配給一個(gè)作業(yè)，用靜態(tài)重定位方式進(jìn)行地址轉(zhuǎn)換，提供必要的保護(hù)手段，保證各作業(yè)互不干擾。在分區(qū)的劃分方式上有固定分區(qū)和可變分區(qū)兩種。,4.2 早期的存儲(chǔ)管理技術(shù) -分區(qū)式分配方式,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,一、固定式分區(qū)（靜態(tài)分區(qū)）,一、固定式分區(qū),(b)分區(qū)說明表,例：已知內(nèi)存分配如圖a所示，此時(shí)分區(qū)說明表如圖b所示，現(xiàn)有后備作業(yè)隊(duì)列如圖c所示，試采用固定分區(qū)法進(jìn)行內(nèi)存分配，并給出相應(yīng)的分區(qū)說明表。,性能：分區(qū)大小固定，分區(qū)表的結(jié)構(gòu)可以是順序表也可以是鏈表；實(shí)

7、現(xiàn)了多個(gè)作業(yè)共享內(nèi)存；分區(qū)的分配和回收算法簡(jiǎn)單；缺點(diǎn)是內(nèi)存利用不充足，有“碎片”，即作業(yè)所需空間和分區(qū)大小不一定恰好相等。,Job A(6k),Job B(25k),Job C(40k),外部碎片剩余165K但不能分配給D,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,4.2 分區(qū)式分配方式,二、可變式分區(qū)（動(dòng)態(tài)分區(qū)） 思想：又稱動(dòng)態(tài)存儲(chǔ)管理，只有當(dāng)作業(yè)調(diào)入內(nèi)存時(shí)，才按作業(yè)大小建立分區(qū)，當(dāng)作業(yè)執(zhí)行完后又釋放此空間。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,2. 分區(qū)的管理與組織方式 采用可變分區(qū)方式管理內(nèi)存儲(chǔ)器時(shí)，內(nèi)存中有兩類性質(zhì)的分區(qū)： 一類是已經(jīng)分配給用戶使用的“已分配區(qū)”， 另一類是可以分配給用戶使用的“空閑區(qū)”

8、。 對(duì)分區(qū)的管理，常用的方式有三種：表格法、單鏈表法和雙鏈表法。,二、可變式分區(qū),計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,（1）表格法,二、可變式分區(qū),內(nèi)存分區(qū)的管理表格,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,（2）單鏈表法,二、可變式分區(qū),單鏈表形式分區(qū)管理,在每塊開始與結(jié)束的幾個(gè)字節(jié)中存放有關(guān)本塊狀態(tài)的信息，稱為控制信息區(qū), 如圖a所示。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,二、可變式分區(qū),（3）雙鏈表法,空閑塊鏈表,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,空間分配例題,設(shè)某系統(tǒng)用戶區(qū)大小為5000字節(jié)，地址為1 5000，初始狀態(tài)如下圖a所示，依次分配給5個(gè)作業(yè)P1 P5, 作業(yè)占用區(qū)大小分別為1000，300，600，

9、900，700。 P0 為余下的空閑塊，各占用塊和空閑塊情況如下頁圖b和c所示。,二、可變式分區(qū),注意：空間分配回收時(shí)使用空閑塊鏈表,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,空間回收過程圖（無空閑塊合并發(fā)生）,空間回收過程圖（有空閑塊合并發(fā)生）,當(dāng)P5作業(yè)完成后，回收時(shí)由于其左右鄰居均為空閑塊，因此應(yīng)進(jìn)行合并。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,分配算法： 最先適應(yīng)算法(First-Fit)：空閑表按空閑塊的物理起始地址遞增次序排列，分配時(shí)，從第一塊依次查找，找到第一塊能容納作業(yè)的空閑塊就停止。 最佳適應(yīng)算法(Best-Fit)：空閑表按空閑塊的大小遞增次序排列，分配時(shí)，從第一塊依次查找，找到第一塊能容納作

10、業(yè)的空閑塊就停止。 最差適應(yīng)算法：(Worst-Fit):空閑表按空閑塊的大小遞減次序排列，分配時(shí)，將空閑塊鏈表中第一塊分配給用戶。,二、可變式分區(qū),計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,三、多重式分區(qū) 一個(gè)作業(yè)裝入內(nèi)存中多個(gè)不一定相鄰的分區(qū)。 優(yōu)點(diǎn)：靈活利用內(nèi)存； 缺點(diǎn)：碎片小了，但可能數(shù)量更多。,4.2 分區(qū)式分配方式,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,四、分區(qū)管理的存儲(chǔ)保護(hù) 界地址法：靜態(tài)重定位使用,4.2 分區(qū)式分配方式,一對(duì)基地址、限長寄存器。動(dòng)態(tài)重定位使用。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,4.2 分區(qū)式分配方式,五、可重定位式分區(qū)（緊縮分區(qū)） 1. 實(shí)現(xiàn)：向一個(gè)方向移動(dòng)已分配的作業(yè)，使那些零散

11、的小空閑區(qū)在另一方向連成一片。 2. 問題： 地址項(xiàng)的修改-動(dòng)態(tài)地址重定位；基址限長寄存器保護(hù)； b. 緊縮時(shí)機(jī): 回收時(shí)進(jìn)行-每當(dāng)作業(yè)結(jié)束,釋放所占分區(qū)時(shí); 分配時(shí)進(jìn)行-當(dāng)新作業(yè)到來又沒有能容納的空閑區(qū)分配時(shí); 3. 性能：消除了碎片，提高了內(nèi)存利用率；但花費(fèi)了大量的cpu時(shí)間。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,1.分區(qū)管理要求對(duì)每一個(gè)作業(yè)都分配 內(nèi)存單元。 A. 地址連續(xù)B. 若干地址不連續(xù) C. 若干連續(xù)的幀D. 若干不連續(xù)的幀,2.碎片是指 。 A. 存儲(chǔ)分配完后剩余的空閑區(qū) B. 沒有被使用的存儲(chǔ)區(qū) C. 不能被使用的存儲(chǔ)區(qū) D. 未被使用，而又暫時(shí)不能使用的存儲(chǔ)區(qū),計(jì)算機(jī)軟件技術(shù)基礎(chǔ)

12、,存儲(chǔ)管理,引入：最早用于分時(shí)系統(tǒng)中提高內(nèi)存利用率的一種內(nèi)存擴(kuò)充技術(shù)。 思想（roll-in roll-out）：除操作系統(tǒng)外，剩余的全部內(nèi)存都分給當(dāng)前正在執(zhí)行的用戶使用，當(dāng)調(diào)度轉(zhuǎn)向下一個(gè)用戶時(shí)，當(dāng)前用戶內(nèi)存區(qū)中的內(nèi)容要寫到外存中，被選中的用戶的信息讀入內(nèi)存。 實(shí)現(xiàn)：由換入和換出兩個(gè)過程構(gòu)成的交換進(jìn)程完成。 核心問題：保證對(duì)換信息量要最少-只要保證當(dāng)前正在執(zhí)行的用戶進(jìn)程在內(nèi)存中完整保存。 技術(shù)支持 一般都有動(dòng)態(tài)重定位機(jī)構(gòu)-因而一個(gè)作業(yè)換入內(nèi)存時(shí)不一定要裝入它被換出前所占據(jù)的區(qū)域中. 需要較多軟件的支持.,4.3 多道程序?qū)Q技術(shù),計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,一、引入目的： 為了解決分區(qū)存儲(chǔ)管

13、理中，當(dāng)某作業(yè)需求空間大于內(nèi)存物理空閑空間時(shí)，該作業(yè)無法運(yùn)行的問題。 二.原理:程序執(zhí)行時(shí)的局部性原理 三、思想： 在一個(gè)程序執(zhí)行過程中，不需要全部裝入內(nèi)存，而把不經(jīng)常被進(jìn)程訪問的程序段和數(shù)據(jù)放在外存中，待需要訪問它們時(shí)再將它們調(diào)入內(nèi)存。（部分裝入內(nèi)存）,4.4 虛擬存儲(chǔ)器的概念,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,三、虛擬存儲(chǔ)器： 是指僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行該作業(yè)的存儲(chǔ)器系統(tǒng)，具有請(qǐng)求調(diào)入和置換功能。,4.4 虛擬存儲(chǔ)器的概念,虛擬存儲(chǔ)管理技術(shù)需要解決的問題： （1）什么時(shí)候把哪部分程序裝入內(nèi)存。 （2）放在內(nèi)存什么位置。 （3）當(dāng)內(nèi)存空間不足時(shí)，把哪部分程序淘汰出內(nèi)存。 常用的虛擬存儲(chǔ)

14、技術(shù)有： 分頁存儲(chǔ)管理、分段存儲(chǔ)管理、段頁存儲(chǔ)管理。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,四、物質(zhì)基礎(chǔ) 二級(jí)存儲(chǔ)器(內(nèi)/外存)-實(shí)現(xiàn)內(nèi)/外存有機(jī)聯(lián)系; 動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)(DAT)-實(shí)現(xiàn)動(dòng)態(tài)定位,實(shí)際上用戶的虛擬地址空間并不可能是無限大，它受到以下兩個(gè)條件制約： 1. 指令中地址長度的限制。 2. 外存儲(chǔ)器容量的限制。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,1. 能夠?qū)崿F(xiàn)對(duì)內(nèi)外存進(jìn)行統(tǒng)一管理，為用戶提供一種宏觀上似乎比實(shí)際內(nèi)存容量大得多的存儲(chǔ)器。 A. 覆蓋技術(shù)B. 交換技術(shù) C. 物理擴(kuò)充D. 虛擬存儲(chǔ)技術(shù),2.若處理器有32位地址，則它的虛擬地址空間為 字節(jié)。 A. 2GBB. 4GB C. 100KBD

15、. 640KB,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,4.5 請(qǐng)求分頁式存儲(chǔ)管理,一、分頁式存儲(chǔ)管理（靜態(tài)分頁）-程序一次裝入內(nèi)存中若干個(gè)不連續(xù)的區(qū)域 1. 分頁管理的基本概念 (1)頁面、頁架（塊） 頁：把每個(gè)作業(yè)的地址空間分成一些大小相等的片，稱為“頁”。 頁架”或者“塊：把內(nèi)存的存儲(chǔ)空間也分成大小與頁相同的片，稱為“頁架”或者“塊”。,(2)頁表與頁表地址寄存器 頁表：系統(tǒng)為每個(gè)作業(yè)建立一個(gè)頁面映像表（PMT），簡(jiǎn)稱“頁表”。頁表中應(yīng)包括：頁號(hào)、頁架號(hào)、狀態(tài)。,作業(yè)各頁的頁號(hào)，每個(gè)作業(yè)頁號(hào)從零開始。,該頁面在內(nèi)存中的頁架號(hào)。,表示該頁是否在內(nèi)存中，用“0”表示該頁不在內(nèi)存，用“1”表示在內(nèi)存中。

16、,虛地址空間,實(shí)地址空間,5,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,例：系統(tǒng)選擇頁的大小為1k字節(jié)，則塊的大小也為1K。主存空間如圖所示。,（1）已經(jīng)分配空間給作業(yè)1，2，如圖。,（2）作業(yè)3有3k字節(jié)。其分配空間與相應(yīng)的頁表如圖。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,一、分頁式存儲(chǔ)管理（靜態(tài)分頁）,(3)分頁系統(tǒng)中的地址結(jié)構(gòu) 在分頁系統(tǒng)中，每個(gè)虛擬地址用一個(gè)數(shù)對(duì)（p,d）來表示， 其中p為頁號(hào)。 d是該虛擬地址在頁面號(hào)為p中的相對(duì)地址，稱為頁內(nèi)地址。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,如何將邏輯地址轉(zhuǎn)化為頁號(hào)p與頁內(nèi)位移d？,例1：設(shè)U=552為邏輯地址,頁面大小為P=512，則頁號(hào)p與頁內(nèi)位移d是多少？,例

17、2：設(shè)U=552為邏輯地址,頁面大小為P=512，則頁號(hào)p與頁內(nèi)位移d是多少？,U=(552)10=(1 0 0 0 1 0 1 0 0 0)2,解：P=(512)10=2n=29,n=9,公式：,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,2. 分頁管理的原理 邏輯地址如何轉(zhuǎn)化為物理地址？ 進(jìn)程的邏輯地址(虛地址)=頁號(hào)(P)+頁內(nèi)地址(位移d) 由硬件地址變換機(jī)構(gòu)通過頁表地址寄存器,頁表PMT實(shí)現(xiàn)地址轉(zhuǎn)換。,一、分頁式存儲(chǔ)管理（靜態(tài)分頁）,當(dāng)某作業(yè)被調(diào)度到處理器上運(yùn)行時(shí)，操作系統(tǒng)自動(dòng)將該作業(yè)的頁表的起始地址和長度裝入頁表地址寄存器中,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,例題:假如某系統(tǒng)頁面大小為（512)10

18、字節(jié)，即相當(dāng)于（1000)8字節(jié)，若邏輯地址為（1320)8，其轉(zhuǎn)換為物理地址地址變換過程如圖。,分頁管理的地址轉(zhuǎn)換圖,地址變換機(jī)構(gòu),23285,1320,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,二、請(qǐng)求分頁存儲(chǔ)管理系統(tǒng)（動(dòng)態(tài)分頁） 1.設(shè)計(jì)思想：允許只裝入若干頁（而非全部）的用戶程序和數(shù)據(jù)，便可啟動(dòng)運(yùn)行，以后根據(jù)請(qǐng)求陸續(xù)把即將要運(yùn)行的頁面調(diào)入內(nèi)存。初啟時(shí)，只裝入第一頁。 2.實(shí)現(xiàn)：在分頁系統(tǒng)的基礎(chǔ)上，增加請(qǐng)求調(diào)頁功能和頁面置換功能。 3.技術(shù)措施： 請(qǐng)求分頁的頁表機(jī)制-對(duì)純分頁頁表進(jìn)行擴(kuò)展,4.5 請(qǐng)求分頁式存儲(chǔ)管理,每個(gè)作業(yè)都有存入其JCB中私有頁表； 當(dāng)訪問頁不在內(nèi)存時(shí)，產(chǎn)生缺頁中斷； OS管理一

19、張總的存儲(chǔ)分塊表。,=1,表示該頁修改過,=1,表示最近訪問過,=1,表示該頁在內(nèi)存中,=0,表示該頁不在內(nèi)存中，發(fā)生缺頁中斷,該頁面在外存的地址,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,請(qǐng)求分頁存儲(chǔ)管理技術(shù)例：系統(tǒng)選擇頁的大小為4KB，則塊的大小也為4KB。設(shè)某時(shí)刻系統(tǒng)有3個(gè)作業(yè)，現(xiàn)執(zhí)行作業(yè)2，作業(yè)2的虛擬地址空間如下圖。此時(shí)系統(tǒng)內(nèi)存分配圖如圖a，內(nèi)存存儲(chǔ)分塊表如圖b，作業(yè)表如圖c，各作頁頁表如圖d。,8300=(p,d) =?,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,請(qǐng)求分頁存儲(chǔ)管理技術(shù)圖例,指令Call 8300 經(jīng)動(dòng)態(tài)地址重定位后，實(shí)際執(zhí)行指令為Call（28K108）,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,5.

20、 硬件支持 動(dòng)態(tài)地址映射機(jī)構(gòu)-利用頁表將虛地址轉(zhuǎn)換物理地址； 頁表實(shí)現(xiàn)形式： 用專用內(nèi)存區(qū)實(shí)現(xiàn)： 用一組專用寄存器實(shí)現(xiàn): 用一個(gè)高速聯(lián)想寄存器保存頁表-快表實(shí)現(xiàn)：,二、請(qǐng)求分頁存儲(chǔ)管理系統(tǒng),缺頁中斷響應(yīng)機(jī)構(gòu),計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,利用快表實(shí)現(xiàn)地址轉(zhuǎn)換一,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,頁表、快表地址轉(zhuǎn)換機(jī)構(gòu),計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,工作區(qū)入內(nèi)存 填寫頁表各項(xiàng),進(jìn)程調(diào)度該進(jìn)程,啟動(dòng)待執(zhí)行指令,計(jì)算頁號(hào)與頁內(nèi) 相對(duì)地址,該頁在 內(nèi)存嗎？,地址變換,訪內(nèi)存執(zhí)行 完成該指令,執(zhí)行下一 條指令,是,硬件完成,否,保護(hù)當(dāng)前進(jìn)程現(xiàn)場(chǎng),有空閑塊嗎？,選擇一 頁淘汰,該頁修改 過嗎？,把該頁寫 回外

21、存,調(diào)入所需頁,調(diào)整頁表及 空閑塊表,恢復(fù)被中斷 進(jìn)程現(xiàn)場(chǎng),是,否,是,否,狀態(tài)位,引用位,改變位,否,請(qǐng)求分頁系統(tǒng)程序執(zhí)行過程,缺頁中斷,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,缺頁中斷處理過程,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,6.請(qǐng)求分頁系統(tǒng)的性能： 有效存取時(shí)間：t=（1-P）ma+P缺頁處理時(shí)間 其中，P-缺頁中斷概率；ma-內(nèi)存存取時(shí)間。 有快表時(shí)，存取時(shí)間短。速度與命中率相關(guān)。 無快表時(shí)，執(zhí)行速度降低。（二次訪問內(nèi)存）,4.5 請(qǐng)求分頁式存儲(chǔ)管理,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,三、頁面淘汰算法（置換） 頁面淘汰：由于分頁管理中分配給每道程序的頁架數(shù)有限，因此內(nèi)存中的頁面要隨時(shí)進(jìn)行更換，稱為頁面

22、淘汰。,4.5 請(qǐng)求分頁式存儲(chǔ)管理,頁面淘汰算法評(píng)價(jià)準(zhǔn)則：在特定存儲(chǔ)訪問序列上運(yùn)行頁面淘汰算法，用其缺頁率來衡量。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,四、頁面淘汰算法,頁面走向：評(píng)價(jià)時(shí)用于量化缺頁率的存儲(chǔ)訪問序列。 （人工獲得）隨機(jī)產(chǎn)生；實(shí)際跟蹤記錄地址,量化： 對(duì)于給定的頁面(大小確定), 只關(guān)心頁號(hào), 不關(guān)心完整地址; 如果對(duì)P頁進(jìn)行了訪問,隨后立即對(duì)P頁的訪問不會(huì)缺頁;,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,3. 幾種常用頁面淘汰算法 （1）先進(jìn)先出法（FIFOFirst Input First Output）： 算法思想：認(rèn)為最先進(jìn)入內(nèi)存的頁面，不再被使用的可能性最大，所以最先進(jìn)入內(nèi)存的頁面，最先

23、被調(diào)出內(nèi)存。,四、頁面淘汰算法,例：設(shè)有一用戶程序共分為6頁，頁面大小為100,設(shè)執(zhí)行時(shí)訪問虛擬地址依次為450,440,320,330,210,150,453,350,355,550,456,330,299,199,500. 分配給該程序的內(nèi)存塊數(shù)M為3，內(nèi)存存儲(chǔ)地址從0開始分配. (1)給出頁面走向P (2)采用FIFO淘汰算法，給出其頁面淘汰過程 (3)求缺頁率。,4,+,+,+,+,+,+,+,+,+,注意:如果對(duì)P頁進(jìn)行了訪問,隨后立即對(duì)P頁的訪問不會(huì)缺頁;,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,四、頁面淘汰算法,例：設(shè)有一用戶程序共分為6頁， 頁面走向P為1，2，3，4，1，2，5，1，2

24、，3，4，5， 分配給該程序的內(nèi)存塊數(shù)M為3， 采用FIFO淘汰算法，其頁面淘汰過程如下，并求缺頁率。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,四、頁面淘汰算法,例：設(shè)有一用戶程序共分為6頁， 頁面走向P為1，2，3，4，1，2，5，1，2，3，4，5， 分配給該程序的內(nèi)存塊數(shù)M為4， 采用FIFO淘汰算法，其頁面淘汰過程如下，并求缺頁率。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,性能分析： 這一算法適用于按線性順序訪問地址的程序，否則效率不高。 算法簡(jiǎn)單, 但性能較差(實(shí)驗(yàn)證明),表現(xiàn)為: 內(nèi)存利用率不高。 存在異?，F(xiàn)象。,（1）先進(jìn)先出法,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,四、頁面淘汰算法,(2)最優(yōu)淘汰法(OP

25、T Optimal Replacement) 思想：淘汰將在最長的時(shí)間后才要訪問的頁面。 實(shí)現(xiàn)：非常困難，因?yàn)樾枰櫢黜撁娣娇深A(yù)測(cè)未來?！翱磳怼?OPT頁面淘汰過程,4,例：設(shè)有一用戶程序共分為6頁， 頁面走向P為4，3，2，1，4，3，5，4，3，2，1，5， 分配給該程序的內(nèi)存塊數(shù)M為3， 采用OPT淘汰算法，其頁面淘汰過程如下，并求缺頁率。,性能分析： a. 最優(yōu)算法,目的在于減少頁面交換次數(shù),節(jié)約處理機(jī)時(shí)間； b. 缺頁率,f=7/12=58%,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,(3)最久未使用法(LRU Least Recently Used) 思想：基于“過去一段時(shí)間里不曾被訪問過

26、的頁，在最近的將來可能也不再會(huì)被訪問”假設(shè)。淘汰一頁時(shí)，選取在最近一段時(shí)間內(nèi)最久未使用過的頁面予以淘汰。,四、頁面淘汰算法,常采用近似算法： 最不頻繁使用法(LRU)-把最不常用的頁面先淘汰。 b. 最近沒有使用法(NUR)-把最近沒有使用過的頁面淘汰。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,性能分析: 近似算法是較為實(shí)用的算法，效果較好，實(shí)現(xiàn)不難,(3)最久未使用法,例：設(shè)有一用戶程序共分為6頁， 頁面走向P為4，3，2，1，4，3，5，4，3，2，1，5， 分配給該程序的內(nèi)存塊數(shù)M為3， 采用LRT淘汰算法，其頁面淘汰過程如下，并求缺頁率。,缺頁率f=10/12=83%,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管

27、理,(4) 第二次機(jī)會(huì)算法(SCR)-FIFO的改進(jìn) 思想：保護(hù)經(jīng)常被訪問的“老頁”不被淘汰。 實(shí)現(xiàn)：每頁被訪問時(shí)，置訪問位“1”，需要淘汰一頁時(shí)，依FIFO順序檢查各頁的訪問位，為“0”者，淘汰；為“1”者，給予第二次機(jī)會(huì)，同時(shí)，清0。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,用循環(huán)鏈表表示的第二次機(jī)會(huì)算法,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,四、物理塊分配算法-內(nèi)存空閑塊分配 最少塊數(shù)原則-不允許一條指令在執(zhí)行過程中缺頁 最少塊數(shù)必須保證訪問指令執(zhí)行期間不缺頁。 結(jié)論: 每個(gè)進(jìn)程的最少塊數(shù)由指令集結(jié)構(gòu)決定; 每個(gè)進(jìn)程的最多塊數(shù)由可用內(nèi)存的總量決定。 2. 全局分配與局部分配 允許缺頁時(shí)在全體進(jìn)程中選擇淘汰

28、者(可變分配) 缺頁時(shí)只在自己駐內(nèi)頁中選擇淘汰者(固定分配),4.5 請(qǐng)求分頁式存儲(chǔ)管理,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,3. 分配算法 等分法: 總塊數(shù)m /總進(jìn)程數(shù)n 性能-一視同仁，但有的剩余；有的不夠。 按需比例法： si/s*m 其中:si-進(jìn)程pi地址空間大小; s=si(i=1n) m-內(nèi)存總塊數(shù) 4. 抖動(dòng)問題: 剛被淘汰出去的頁面,很快又要訪問,又調(diào)回內(nèi)存, 如此反復(fù)。由于淘汰算法不當(dāng)產(chǎn)生.,五、物理塊分配算法,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,五、請(qǐng)求時(shí)分頁存儲(chǔ)管理系統(tǒng)的性能 優(yōu)點(diǎn)： 1. 提供大容量的多個(gè)虛擬存儲(chǔ)器 2. 提高了內(nèi)存利用率; 3. 作業(yè)地址空間不受內(nèi)存限制，有利

29、于組織多道程序執(zhí)行; 4. 不要求作業(yè)在內(nèi)存中連續(xù)存放，有效解決碎片問題; 缺點(diǎn)： 1. 要求相應(yīng)的硬件支持; 2. 增加系統(tǒng)開銷; 3. 算法選擇不當(dāng),會(huì)產(chǎn)生抖動(dòng).,4.5 請(qǐng)求分頁式存儲(chǔ)管理,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,1.頁式存儲(chǔ)管理中，頁表的大小由 決定。 A. 作業(yè)所占頁的多少B. 操作系統(tǒng) C. 計(jì)算機(jī)編址范圍D. 系統(tǒng)統(tǒng)一指定,2.一進(jìn)程剛獲得三個(gè)存儲(chǔ)塊的使用權(quán)，若該進(jìn)程訪問頁面的次序是1,3,2,1,2,1,5,1,2,3，當(dāng)采用先進(jìn)先出調(diào)度算法時(shí)，發(fā)生缺頁的次數(shù)是 次。 A. 4B. 5 C. 6D. 7,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,4.6 段式存儲(chǔ)管理,一、分段的基本思

30、想 引入：為了滿足用戶（程序員）在編程和使用上多方面的要求。 2. 分段：(用戶編程時(shí)決定)把程序按內(nèi)容或過程（函數(shù)）關(guān)系劃分 成若干個(gè)段，每段定義一組邏輯上完整的程序和數(shù)據(jù)，且每段有自己的名字和長度。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,4.6 段式存儲(chǔ)管理,3. 分段管理的基本概念 （1）段 一個(gè)程序由若干個(gè)程序模塊組成，可以按模塊來分配存儲(chǔ)空間。分段管理把每個(gè)模塊的地址空間稱為“段”。每個(gè)段規(guī)定一個(gè)段號(hào)，每個(gè)段的地址空間都從“0”地址開始。 （2）分段管理中的地址結(jié)構(gòu) 在分段情況下，每一個(gè)虛擬地址需要用兩部分來描述，如下圖。,！在分頁存儲(chǔ)管理中，一個(gè)虛擬地址可以分解為頁號(hào)和頁內(nèi)地址。二者是否相

31、同？,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,段式虛地址空間-二維 程序地址=段名(s)+段內(nèi)位移(w相對(duì)于每段起始) 注意:與頁式虛地址(一維)的區(qū)別: 段名(號(hào))之間無順序關(guān)系;頁號(hào)之間是連續(xù)的。 段的長度是不固定的.(與完整的邏輯信息有關(guān))。頁長度固定，一般一頁中的信息不是完整的邏輯信息單位。,！在分頁存儲(chǔ)管理中，一個(gè)虛擬地址可以分解為頁號(hào)和頁內(nèi)地址。二者是否相同？,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),存儲(chǔ)管理,段表、段地址寄存器 系統(tǒng)為每個(gè)作業(yè)建立一個(gè)段映象表（SMT），簡(jiǎn)稱段表，段表中包括：段號(hào)、段的長度、段在主存中的起始地址、段的狀態(tài)以及存取權(quán)限等。 同時(shí)系統(tǒng)設(shè)立一個(gè)段表地址寄存器，指出當(dāng)前運(yùn)行作業(yè)的段表在主存中的起始地址b以及段表長度L。,4.