27五月2023

第4章存儲器管理

4.1存儲器的層次結(jié)構(gòu)4.2程序的裝入和鏈接4.3連續(xù)分配方式4.4基本分頁存儲管理方式4.5基本分段存儲管理方式4.6虛擬存儲器的基本概念4.7請求分頁存儲管理方式4.8頁面置換算法4.9請求分段存儲管理方式

27五月2023

4.1存儲器的層次結(jié)構(gòu)

寄存器高速緩存主存磁盤緩存磁盤可移動存儲介質(zhì)CPU寄存器主存輔存

圖4-1

計算機系統(tǒng)存儲層次示意4.1.1多級存儲器結(jié)構(gòu)第4章存儲器管理

27五月2023

4.1.2主存儲器與寄存器4.1.3高速緩存和磁盤緩存

主存儲器（簡稱內(nèi)存或主存），用于保存進程運行時的程序和數(shù)據(jù)。CPU與外圍設(shè)備交換的信息一般也依托于主存儲器地址空間。由于主存儲器的訪問速度遠低于CPU執(zhí)行指令的速度，為緩和這一矛盾，引入了寄存器和高速緩存。1.高速緩存2.磁盤緩存

27五月2023

4.2程序的裝入和鏈接圖4-2對用戶程序的處理步驟

第4章存儲器管理

27五月2023

4.2.1程序的裝入1.絕對裝入方式(AbsoluteLoadingMode)

絕對裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。裝入模塊被裝入內(nèi)存后，由于程序中的邏輯地址和實際內(nèi)存地址完全相同，故不需要對程序和數(shù)據(jù)的地址進行修改。

27五月2023

2.可重定位裝入方式(RelocationLoadingMode)圖4-3作業(yè)裝入內(nèi)存時的情況

27五月2023

地址映射LoadA2003456

。。1200物理地址空間LoadAdata1data13456源程序LoadA20034560100200編譯連接邏輯地址空間BA=1000

27五月2023

地址重定位（地址映射）

重定位是指在裝入時對目標程序中指令和數(shù)據(jù)的修改過程。這一過程通常是在裝入時一次完成的，故稱為靜態(tài)重定位。

27五月2023

3.動態(tài)運行時裝入方式(DenamleRun-timeLoading)

動態(tài)運行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進行。因此，裝入內(nèi)存后的所有地址都仍是相對地址。

27五月2023

4.2.2程序的鏈接1.靜態(tài)鏈接方式(StaticLinking)圖4-4程序鏈接示意圖

27五月2023

在將這幾個目標模塊裝配成一個裝入模塊時，須解決以下兩個問題：

(1)對相對地址進行修改。

(2)變換外部調(diào)用符號。

27五月2023

2.裝入時動態(tài)鏈接(LoadtimeDynamicLinking)裝入時動態(tài)鏈接方式有以下優(yōu)點：便于修改和更新。(2)便于實現(xiàn)對目標模塊的共享。

27五月2023

3.運行時動態(tài)鏈接(Run-timeDynamicLinking)

近幾年流行起來的運行時動態(tài)鏈接方式，是對上述在裝入時鏈接方式的一種改進。這種鏈接方式是將對某些模塊的鏈接推遲到執(zhí)行時才鏈接，亦即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。

27五月2023

4.3連續(xù)分配方式4.3.1單一連續(xù)分配

這是最簡單的一種存儲管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。采用這種存儲管理方式時，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。第4章存儲器管理

27五月2023

4.3.2固定分區(qū)分配

固定分區(qū)式分配是將內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域，在每個分區(qū)中只裝入一道作業(yè)。它是一種最簡單的可運行多道程序的存儲管理方式。

27五月2023

1.劃分分區(qū)的方法分區(qū)大小相等，即使所有的內(nèi)存分區(qū)大小相等。缺點：缺乏靈活性，即當(dāng)程序太小時，會造成內(nèi)存空間的浪費。程序太大時，可能無法執(zhí)行。(2)分區(qū)大小不等。含多個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。

27五月2023

2.內(nèi)存分配圖4-5固定分區(qū)使用表

27五月2023

優(yōu)點：易于實現(xiàn)，開銷小。缺點：內(nèi)碎片造成浪費；分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。

27五月2023

4.3.3動態(tài)分區(qū)分配

動態(tài)分區(qū)分配是根據(jù)進程的實際需要，動態(tài)為之分配內(nèi)存空間。分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)為實現(xiàn)動態(tài)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用來描述空閑分區(qū)和已分配分區(qū)的情況。通常采用以下兩種形式：

27五月2023

空閑分區(qū)表。

(2)空閑分區(qū)鏈。圖4-6空閑鏈結(jié)構(gòu)

27五月2023

進程A（8K）進程D（124K）進程B（16K）進程C（64K）…OS進程A進程B進程C進程DOS進程A進程B進程COS進程A進程BOS進程A

因為固定分區(qū)主存利用率不高，使用起來不靈活，所以出現(xiàn)了可變分區(qū)的管理技術(shù)。動態(tài)分區(qū)原則：存儲空間的劃分是在裝作業(yè)時進行的。從可用的自由存儲空間內(nèi)，劃出一個大小正好等于作業(yè)大小的存儲區(qū)，并分配給這一作業(yè)。

27五月2023

OSA（8K）24K空閑區(qū)B（16K）C完成64K空閑區(qū)D（124K）OSA（8K）8K空閑區(qū)B（16K）E（50K）D（124K）14K空閑區(qū)F（16K）OSA（8K）8K空閑區(qū)空閑區(qū)16KE（50K）D（124K）空閑合并124+14=138進程E（50K）進程F（16K）進入內(nèi)存進程B（16K）進程D（124K）完成內(nèi)存分配變化過程

27五月2023

2.分區(qū)分配算法(1)首次適應(yīng)算法FF空閑區(qū)鏈：首址遞增排列；申請：按分區(qū)的先后次序，從頭查找，找到符合要求的第一個分區(qū)；優(yōu)點：盡量使用低地址空間，高地址空間保持大的空閑區(qū)域。缺點：隨著低地址分區(qū)不斷劃分而產(chǎn)生較多小分區(qū)（內(nèi)存碎片），每次分配時查找時間開銷會增大。

27五月2023

(2)循環(huán)首次適應(yīng)算法空閑區(qū)鏈：首址遞增排列；申請：從上次分配的分區(qū)起查找（到最后分區(qū)時再回到開頭），找到符合要求的第一個分區(qū)，應(yīng)設(shè)置一個查詢指針。特點：空閑分區(qū)分布均勻；大的空閑分區(qū)不易保留；查找時間開銷會減小。

27五月2023

(3)最佳適應(yīng)算法空閑區(qū)鏈：分區(qū)容量遞增排列；申請：找到符合要求的第一個分區(qū)。特點：碎片較小，但從整體來看，會形成較多的碎片。(4)最壞適應(yīng)算法空閑區(qū)鏈：分區(qū)容量遞減排列；申請：找到符合要求的第一個分區(qū)。特點：大的空閑分區(qū)不易保留。

27五月2023

(5)

快速適應(yīng)算法該算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容量大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表，多個空閑分區(qū)鏈表對應(yīng)一張管理索引表?？臻e分區(qū)的分類根據(jù)進程常用的空間大小進行劃分，如2KB、4KB、8KB等。優(yōu)點：查找效率高，不會對任何分區(qū)進行分割。缺點：分區(qū)歸還主存時算法復(fù)雜，系統(tǒng)開銷較大。存在空間浪費。

27五月2023

動態(tài)分區(qū)分配算法演示

27五月2023

3.分區(qū)分配操作1)分配內(nèi)存圖4-7內(nèi)存分配流程

27五月2023

2)回收內(nèi)存圖4-8內(nèi)存回收情況

27五月2023

作業(yè)：某系統(tǒng)采用動態(tài)分區(qū)分配方式管理內(nèi)存，內(nèi)存空間為640K，高端40K用來存放操作系統(tǒng)。在內(nèi)存分配時，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間。對下列請求序列：作業(yè)1申請130K、作業(yè)2申請60K、 作業(yè)3申請100K、 作業(yè)2釋放60K、作業(yè)4申請200K、作業(yè)3釋放100K、作業(yè)1釋放130K、作業(yè)5申請140K、作業(yè)6申請60K、作業(yè)7申請50K、作業(yè)6釋放60K，請分別畫圖表示出使用首次適應(yīng)算法和最佳適應(yīng)算法進行內(nèi)存分配和回收后內(nèi)存的實際使用情況。

27五月2023

4.3.4可重定位分區(qū)分配1.動態(tài)重定位的引入圖4-9緊湊的示意

27五月2023

2.動態(tài)重定位的實現(xiàn)圖4-10動態(tài)重定位示意圖

27五月2023

3.動態(tài)重定位分區(qū)分配算法圖4-11動態(tài)分區(qū)分配算法流程圖

27五月2023

4.3.5對換(Swapping)1.對換的引入

在多道程序環(huán)境下，可以將暫時不能執(zhí)行的程序送到外存中，從而獲得空閑內(nèi)存空間來裝入新程序。所謂“對換”，是指把內(nèi)存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對換是提高內(nèi)存利用率的有效措施。

27五月2023

如果對換以整個進程為單位的，稱之為“整體對換”或“進程對換”。而如果對換是以“頁”或“段”為單位進行的，則分別稱之為“頁面對換”或“分段對換”。

優(yōu)點：增加并發(fā)運行的程序數(shù)目，并且給用戶提供適當(dāng)?shù)捻憫?yīng)時間；編寫程序時不影響程序結(jié)構(gòu)。缺點：對換入和換出的控制增加處理機開銷；

27五月2023

2.對換空間的管理

把外存分為文件區(qū)和對換區(qū)。對換區(qū)用來存放從內(nèi)存換出的進程。主要目標是提高進程換入和換出的速度。為了能對對換區(qū)中的空閑盤塊進行管理，在系統(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ù)。

27五月2023

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

27五月2023

(2)進程的換入。系統(tǒng)應(yīng)定時地查看所有進程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進程，將其中換出時間(換出到磁盤上)最久的進程作為換入進程，將之換入，直至已無可換入的進程或無可換出的進程為止。

27五月2023

溫故而知新第4章存儲器管理4.1存儲器的層次結(jié)構(gòu)4.2程序的裝入和鏈接

4.3連續(xù)分配方式

4.4基本分頁存儲管理方式4.5基本分段存儲管理方式4.6虛擬存儲器的基本概念4.7請求分頁存儲管理方式4.8頁面置換算法4.9請求分段存儲管理方式單一連續(xù)分配固定分區(qū)分配動態(tài)分區(qū)分配

27五月2023

溫故而知新第4章存儲器管理4.1存儲器的層次結(jié)構(gòu)4.2程序的裝入和鏈接

4.3連續(xù)分配方式

4.4基本分頁存儲管理方式（重點）4.5基本分段存儲管理方式4.6虛擬存儲器的基本概念（難點）4.7請求分頁存儲管理方式

（重點）4.8頁面置換算法4.9請求分段存儲管理方式

27五月2023

連續(xù)分配方式會形成許多碎片，雖然通過“緊湊”可以拼接，但是必須付出很多開銷。因此產(chǎn)生了離散分配方式，如果離散分配基本單位是頁，則稱為分頁存儲管理方式；如果離散分配基本單位是段，則稱為分段存儲管理方式。4.4基本分頁存儲管理方式

第4章存儲器管理

27五月2023

4.4.1頁面與頁表

1.頁面

1)頁面和物理塊0頁1頁2頁n頁…用戶作業(yè)邏輯地址012n…345內(nèi)存物理地址頁內(nèi)碎片頁或頁面物理塊

27五月2023

2)頁面大小因此，頁面的大小應(yīng)選擇得適中，且頁面大小應(yīng)是2的冪，通常為512B-8KB。頁面太小優(yōu)點：可使內(nèi)存碎片減小，有利于提高內(nèi)存利用率。缺點：會使每個進程占用較多的頁面，從而導(dǎo)致進程的頁表過長，占用大量內(nèi)存。頁面太大優(yōu)點：可減少頁表長度。缺點：頁內(nèi)碎片增大。

27五月2023

2.地址結(jié)構(gòu)

分頁地址中的地址結(jié)構(gòu)如下：

頁號P位移量W311090

對某特定機器，其地址結(jié)構(gòu)是一定的。若給定一個邏輯地址空間中的地址為A，頁面的大小為L，則頁號P和頁內(nèi)地址d可按下式求得：

27五月2023

2.地址結(jié)構(gòu)

0頁1頁2頁n頁…用戶作業(yè)邏輯地址假設(shè)一邏輯地址空間，頁面大小為1K，則邏輯地址1000,2500分別在幾號頁？頁內(nèi)地址是多少？0102420483072…1000/1024=0……10002500/1024=2……452

27五月2023

3.頁表

圖4-12頁表的作用

15

27五月2023

頁表（邏輯地址與物理地址的對應(yīng)）

27五月2023

4.4.2地址變換機構(gòu)

1.基本的地址變換機構(gòu)

圖4-13分頁系統(tǒng)的地址變換機構(gòu)

27五月2023

地址變換過程演示

27五月2023

由于頁表存儲在內(nèi)存中，CPU每存取一個數(shù)據(jù)，都要兩次訪問內(nèi)存。第一次是訪問內(nèi)存中的頁表，從中找到指定的物理塊號；第二次訪問內(nèi)存才是從具體的物理地址獲得所需數(shù)據(jù)。地址變換效率分析解決方案增設(shè)快表

27五月2023

2.具有快表的地址變換機構(gòu)圖4-14具有快表的地址變換機構(gòu)

27五月2023

命中率：是指頁號在快表中被查找到的百分比，記為p。則有效訪問時間：

在快表的訪問時間×p＋不在快表訪問時間×（1-p）快表的意義：提高地址變換速度快表的位置：高速緩沖寄存器（聯(lián)想寄存器）說明：由于成本關(guān)系，快表不可能做得很大，通常只存放16~512個頁表項，這對于中、小型作業(yè)來說，已有可能把全部頁表項放在快表中，從快表中能找到所需頁表項的機率可達90%以上。

27五月2023

4.4.3兩級和多級頁表

現(xiàn)代的大多數(shù)計算機系統(tǒng)，都支持非常大的邏輯地址空間(232-264)。在這樣的環(huán)境下，頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。例如：又因為每個頁表項占用一個字節(jié)，故每個進程僅僅其頁表就要占用1MB的內(nèi)存空間，而且還要求是連續(xù)的。頁號P位移量W3112110

27五月2023

1.兩級頁表(Two-LevelPageTable)

邏輯地址結(jié)構(gòu)可描述如下：

27五月2023

圖4-15兩級頁表結(jié)構(gòu)

27五月2023

圖4-16具有兩級頁表的地址變換機構(gòu)

27五月2023

2.多級頁表

對于32位的機器，采用兩級頁表結(jié)構(gòu)是合適的；但對于64位的機器，如果頁面大小仍采用4KB即212B，那么還剩下52位，假定仍按物理塊的大小(212位)來劃分頁表，則將余下的42位用于外層頁號。此時在外層頁表中可能有4096G個頁表項，要占用16384GB的連續(xù)內(nèi)存空間。必須采用多級頁表，將外層頁表再進行分頁，也是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關(guān)系。

27五月2023

4.5基本分段存儲管理方式

引入分頁存儲管理方式，主要是為了提高內(nèi)存的利用率。而引入分段存儲管理方式，主要是為了滿足用戶在編程和使用上的多方面的要求。第4章存儲器管理

27五月2023

4.5.1分段存儲管理方式的引入

引入分段存儲管理方式，主要是為了滿足用戶和程序員的下述一系列需要：

1)方便編程

2)信息共享

3)信息保護

4)動態(tài)增長

5)動態(tài)鏈接

27五月2023

4.5.2分段系統(tǒng)的基本原理

1.分段

按程序自身的邏輯關(guān)系把作業(yè)的地址空間劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段也從0開始編址，段內(nèi)地址是連續(xù)的。

27五月2023

分段地址中的地址具有如下結(jié)構(gòu)（二維的）：

段號段內(nèi)地址3116150

27五月2023

2.段表

進程中每個分段分配一個連續(xù)的內(nèi)存空間（分區(qū)），各個段可以離散地存放在內(nèi)存中不同的分區(qū)。因此系統(tǒng)給每個進程建立一張映射表，簡稱“段表”。段表是用于實現(xiàn)從邏輯段到物理內(nèi)存分區(qū)的映射。

27五月2023

圖4-17利用段表實現(xiàn)地址映射

27五月2023

圖4-18分段系統(tǒng)的地址變換過程

3.地址變換機構(gòu)

27五月2023

要訪問一個數(shù)據(jù)，需兩次訪問內(nèi)存。同樣也可以增設(shè)一個聯(lián)想存儲器（快表）。一般情況下段比頁大，因而段表項的數(shù)目比頁表項的數(shù)目少，其所需的聯(lián)想存儲器也比較小。地址變換效率分析

27五月2023

4.分頁和分段的主要區(qū)別

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

27五月2023

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

(3)分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個記憶符，即可表示一個地址；而分段的作業(yè)地址空間則是二維的，程序員在標識一個地址時，既需給出段名，又需給出段內(nèi)地址。

27五月2023

4.5.3信息共享

圖4-19分頁系統(tǒng)中共享editor的示意圖

27五月2023

圖4-20分段系統(tǒng)中共享editor的示意圖

可重入代碼又稱為“純代碼”，是一種允許被多個進程同時訪問的代碼，進程必須配局部數(shù)據(jù)區(qū)。

27五月2023

4.5.4段頁式存儲管理方式

1.基本原理

將用戶程序劃分若干個段，然后再把每個段分成若干頁，并為每一段賦一個段名。

27五月2023

圖4-21作業(yè)地址空間和地址結(jié)構(gòu)

頁

27五月2023

圖4-22利用段表和頁表實現(xiàn)地址映射

段號（S）段內(nèi)頁號（P）頁內(nèi)地址（W）

27五月2023

2.地址變換過程

圖4-23段頁式系統(tǒng)中的地址變換機構(gòu)

27五月2023

要訪問一個數(shù)據(jù)，需三次訪問內(nèi)存。同樣也可以增設(shè)一個聯(lián)想寄存器（快表），存放段號和頁號。

地址變換效率分析

27五月2023

4.6虛擬存儲器的基本概念

兩種情況：

(1)有的作業(yè)很大，其所要求的內(nèi)存空間超過了內(nèi)存總?cè)萘?，作業(yè)不能全部被裝入內(nèi)存，導(dǎo)致該作業(yè)無法運行。

(2)有大量作業(yè)要求運行，但是由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)的作業(yè)裝入內(nèi)存讓它們先運行，而將其它大量的作業(yè)留在外存上等待。第4章存儲器管理

27五月2023

4.6.1虛擬存儲器的引入1.常規(guī)存儲器管理方式的特征

一次性。

(2)駐留性。

27五月2023

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ù)組進行操作，它們往往都局限于很小的范圍內(nèi)。

27五月2023

局部性又表現(xiàn)在下述兩個方面：

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

(2)空間局部性。一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問，即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是程序的順序執(zhí)行。

27五月2023

3.虛擬存儲器定義

所謂虛擬存儲器，是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存?？梢?，虛擬存儲技術(shù)是一種性能非常優(yōu)越的存儲器管理技術(shù)，故被廣泛地應(yīng)用于大、中、小型機器和微型機中。

27五月2023

4.6.2虛擬存儲器的實現(xiàn)方法

1.分頁請求系統(tǒng)（以頁面為單位）硬件支持。

①請求分頁的頁表機制，它是在純分頁的頁表機制上增加若干項而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)；②缺頁中斷機構(gòu)，即每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存；③地址變換機構(gòu)，它同樣是在純分頁地址變換機構(gòu)的基礎(chǔ)上發(fā)展形成的。(2)實現(xiàn)請求分頁的軟件（調(diào)頁算法和置換算法）。

27五月2023

4.6.3虛擬存儲器的特征

多次性多次性是指一個作業(yè)被分多次調(diào)入內(nèi)存。多次性是虛擬存儲器最重要的特征。2.對換性對換性是指允許在作業(yè)的運行過程中換進、換出。換進和換出能夠有效提高內(nèi)存利用率。3.虛擬性虛擬性是指能夠從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠遠大于實際容量。虛擬性是以多次性和對換性為基礎(chǔ)的。

27五月2023

4.7請求分頁存儲管理方式

4.7.1請求分頁中的硬件支持

1.頁表機制

頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址第4章存儲器管理

27五月2023

2.缺頁中斷機構(gòu)

圖4-24涉及6次缺頁中斷的指令

27五月2023

3.地址變換機構(gòu)

圖4-25請求分頁中的地址變換過程

27五月2023

4.7.2內(nèi)存分配策略和分配算法

1.最小物理塊數(shù)的確定

最小物理塊數(shù)是指能保證進程正常運行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進程分配的物理塊數(shù)少于此值時，進程將無法運行。進程應(yīng)獲得的最少物理塊數(shù)與計算機的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。對于某些簡單的機器，若是單地址指令且采用直接尋址方式，則所需的最少物理塊數(shù)為2。其中，一塊是用于存放指令的頁面，另一塊則是用于存放數(shù)據(jù)的頁面。如果該機器允許間接尋址時，則至少要求有三個物理塊。對于某些功能較強的機器，其指令長度可能是兩個或多于兩個字節(jié)，因而其指令本身有可能跨兩個頁面，且源地址和目標地址所涉及的區(qū)域也都可能跨兩個頁面。

27五月2023

2.物理塊的分配策略

在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進行置換時，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。

1)固定分配局部置換

2)可變分配全局置換

3)可變分配局部置換

27五月2023

3.物理塊分配算法

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

27五月2023

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

27五月2023

3)考慮優(yōu)先權(quán)的分配算法在實際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據(jù)各進程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進程。在有的系統(tǒng)中，如重要的實時控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)來為各進程分配其物理塊的。

27五月2023

4.7.3調(diào)頁策略1.何時調(diào)入頁面

預(yù)調(diào)頁策略2)請求調(diào)頁策略

27五月2023

2.從何處調(diào)入頁面

在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)。由于對換區(qū)是采用連續(xù)分配方式，而文件區(qū)是采用離散分配方式，故對換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁請求時，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況：

(1)系統(tǒng)擁有足夠的對換區(qū)空間，這時可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。為此，在進程運行前，便須將與該進程有關(guān)的文件，從文件區(qū)拷貝到對換區(qū)。

27五月2023

(2)系統(tǒng)缺少足夠的對換區(qū)空間，這時凡是不會被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時，由于它們未被修改而不必再將它們換出，以后再調(diào)入時，仍從文件區(qū)直接調(diào)入。但對于那些可能被修改的部分，在將它們換出時，便須調(diào)到對換區(qū)，以后需要時，再從對換區(qū)調(diào)入。

(3)UNIX方式。由于與進程有關(guān)的文件都放在文件區(qū)，故凡是未運行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運行過但又被換出的頁面，由于是被放在對換區(qū)，因此在下次調(diào)入時，應(yīng)從對換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁面共享，因此，某進程所請求的頁面有可能已被其它進程調(diào)入內(nèi)存，此時也就無須再從對換區(qū)調(diào)入。

27五月2023

3.頁面調(diào)入過程每當(dāng)程序所要訪問的頁面未在內(nèi)存時，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后，如果此時內(nèi)存能容納新頁，則啟動磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁準備換出；如果該頁未被修改過，可不必將該頁寫回磁盤；但如果此頁已被修改，則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存，并修改頁表中的相應(yīng)表項，置其存在位為“1”，并將此頁表項寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。

27五月2023

4.8頁面置換算法

頁面置換算法是選擇換出頁面的算法。置換算法的好壞，將直接影響到系統(tǒng)的性能。第4章存儲器管理

27五月2023

4.8.1最佳置換算法和先進先出置換算法

1.最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。

27五月2023

假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

進程運行時，先將7，0，1三個頁面裝入內(nèi)存。以后，當(dāng)進程要訪問頁面2時，將會產(chǎn)生缺頁中斷。此時OS根據(jù)最佳置換算法，將選擇頁面7予以淘汰。

圖4-26利用最佳頁面置換算法時的置換圖

023

27五月2023

2.先進先出(FIFO)頁面置換算法圖4-27利用FIFO置換算法時的置換圖701

27五月2023

4.8.2最近最久未使用(LRU)置換算法

1.LRU(LeastRecentlyUsed)置換算法的描述

圖4-28LRU頁面置換算法

27五月2023

2.LRU置換算法的硬件支持

1)寄存器為了記錄某進程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為

R=Rn-1Rn-2Rn-3…R2R1R0

27五月2023

圖4-29某進程具有8個頁面時的LRU訪問情況

27五月2023

2)棧

圖4-30用棧保存當(dāng)前使用頁面時棧的變化情況

27五月2023

4.8.3Clock置換算法

1.簡單的Clock置換算法

圖4-31簡單Clock置換算法的流程和示例

27五月2023

2.改進型Clock置換算法

由訪問位A和修改位M可以組合成下面四種類型的頁面：

1類(A=0,M=0)：表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。

2類(A=0,M=1)：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。

3類(A=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。

4類(A=1,M=1):最近已被訪問且被修改，該頁可能再被訪問。

27五月2023

其執(zhí)行過程可分成以下三步：

(1)從指針所指示的當(dāng)前位置開始，掃描循環(huán)隊列，尋找A=0且M=0的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位A。

(2)如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。

(3)如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復(fù)0。然后重復(fù)第一步，如果仍失敗，必要時再重復(fù)第二步，此時就一定能找到被淘汰的頁。

27五月2023

4.8.4其它置換算法

最少使用(LFU：LeastFrequentlyUsed)置換算法2.頁面緩沖算法(PBA：PageBufferingAlgorithm)

27五月2023

4.9請求分段存儲管理方式

4.9.1請求分段中的硬件支持

1.段表機制段名段長段的基址存取方式訪問字段A修改位M存在位P增補位外存始址第4章存儲器管理

27五月2023

在段表項中，除了段名(號)、段長、段在內(nèi)存中的起始地址外，還增加了以下諸項：(1)存取方式。(2)訪問字段A。(3)修改位M。(4)存在位P。(5)增補位。(6)外存始址。

27五月2023

2.缺段中斷機構(gòu)

圖4-32

請求分段系統(tǒng)中的中斷處理過程

27五月2023

3.地址變換機構(gòu)

圖4-33請求分段系統(tǒng)的地址變換過程

27五月2023

4.9.2分段的共享與保護

1.共享段表

圖4-34共享段表項

27五月2023

(1)共享進程計數(shù)count(2)存取控制字段(3)段號

27五月2023

2.共享段的分配與回收

1)共享段的分配在為共享段分配內(nèi)存時，對第一個請求使用該共享段的進程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，同時將該區(qū)的始址填入請求進程的段表的相應(yīng)項中，還須在共享段表中增加一表項，填寫有關(guān)數(shù)據(jù)，把count置為1；之后，當(dāng)又有其它進程需要調(diào)用該共享段時，由于該共享段已被調(diào)入內(nèi)存，故此時無須再為該段分配內(nèi)存，而只需在調(diào)用進程的段表中，增加一表項，填寫該共享段的物理地址；在共享段的段表中，填上調(diào)用進程的進程名、存取控制等，再執(zhí)行count:=count+1操作，以表明有兩個進程共享該段。

27五月2023

2)共享段的回收當(dāng)共享此段的某進程不再需要該段時，應(yīng)將該段釋放，包括撤在該進程段表中共享段所對應(yīng)的表項，以及執(zhí)行count:=count-1操作。若結(jié)果為0，則須由系統(tǒng)回收該共享段的物理內(nèi)存，以及取消在共享段表中該段所對應(yīng)的表項，表明此時已沒有進程使用該段；否則(減1結(jié)果不為0)，則只是取消調(diào)用者進程在共享段表中的有關(guān)記錄。

27五月2023

3.分段保護

越界檢查2)存取控制檢查只讀

(2)只執(zhí)行

(3)讀/寫3)環(huán)保護機構(gòu)一個程序可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)。一個程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)。

27五月2023

圖4-35環(huán)保護機構(gòu)

27五月2023

練習(xí)題在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小為4096字節(jié)，且第0、1、2頁依次放在物理塊5、10、11中，則邏輯地址為5000，2F6AH，相應(yīng)的物理地址為多少？解：本頁式系統(tǒng)的邏輯地址結(jié)構(gòu)為：邏輯地址2F6AH的二進制表示為：0010111101101010