操作系統(tǒng)講義第四章存儲器管理

操作系統(tǒng)講義第四章存儲器管理2023/4/29第四章存儲器管理1第1頁，共56頁，2023年，2月20日，星期一主要內(nèi)容4.1存儲器管理的層次結構4.2程序的裝入和鏈接4.3連續(xù)分配方式4.4基本分頁存儲管理方式4.5基本分段存儲管理方式4.6虛擬存儲器的基本概念4.7請求分頁存儲管理方式4.8頁面置換算法4.9請求分段存儲管理方式第2頁，共56頁，2023年，2月20日，星期一存儲器管理概述存儲器是計算機系統(tǒng)的重要組成部分，隨著計算機技術的發(fā)展，系統(tǒng)軟件和應用軟件在種類、功能及其所需存儲空間等方面，都在急劇地膨脹，雖然存儲器的容量也不斷擴大，但是仍不能滿足現(xiàn)在軟件發(fā)展的需要，它仍然是一種緊俏的資源，所以如何有效地管理存儲器，不僅影響到存儲器的利用率，而且還對系統(tǒng)性能有重大的影響。存儲器管理的主要對象：內(nèi)存。第3頁，共56頁，2023年，2月20日，星期一存儲器管理概述有的作業(yè)很大，所要求的內(nèi)存空間超過內(nèi)存總容量，作業(yè)不能全部裝入，致使該作業(yè)無法運行；有大量作業(yè)要求運行，但內(nèi)存不足以容納所有的作業(yè)，只能讓少數(shù)作業(yè)裝入內(nèi)存先運行，而將大量作業(yè)留在外存等待。顯而易見，一種解決辦法就是從物理上增加內(nèi)存的容量，另一種方法就是從邏輯上擴充內(nèi)存的容量，也就是利用虛擬存儲技術解決。如果某存儲器管理方式要求一個作業(yè)全部裝入內(nèi)存才能夠運行，那么就會出現(xiàn)兩種情況：第4頁，共56頁，2023年，2月20日，星期一4.1存儲器管理的層次結構速度非常快，能跟上處理機的速度容量非常大，能容納所有要運行的作業(yè)價格很便宜，不需要花費額外的錢存儲器的理想狀態(tài)：1.多級存儲結構計算機存儲層次至少應具有三級：CPU寄存器，主存，輔存。

注意：存儲層次越往上，存儲介質(zhì)的訪問速度越快，價格也越高，相對存儲容量也越小?？梢苿哟鎯橘|(zhì)磁盤磁盤緩存主存高速緩存寄存器CPU存儲器主存輔存第5頁，共56頁，2023年，2月20日，星期一4.1存儲器管理的層次2.主存儲器和寄存器主存儲器（簡稱內(nèi)存或主存）：計算機的主要部件，用于保存進程運行時的程序和數(shù)據(jù)，可稱為可執(zhí)行存儲器；微機和大中型機：數(shù)十MB到數(shù)GB；嵌入式計算機：數(shù)十KB到幾MB；CPU和外圍設備交換信息的依托；訪問速度遠低于CPU執(zhí)行指令的速度。第6頁，共56頁，2023年，2月20日，星期一4.1存儲器管理的層次2.主存儲器和寄存器寄存器：能夠與CPU協(xié)調(diào)工作的計算機部件；微機和大中型機：數(shù)十到上百個Word；嵌入式計算機：幾個到幾十個Word；訪問速度快；價格十分昂貴；容量很小。第7頁，共56頁，2023年，2月20日，星期一4.1存儲器的層次結構3.高速緩存和磁盤緩存高速緩存：是計算機中的一個重要部件，其容量大于或遠大于寄存器，而比內(nèi)存小兩到三個數(shù)量級左右，從幾十KB到幾MB，訪問速度快于主存儲器；（1）程序執(zhí)行的局部性原理；（2）速度越高價格越貴，計算機系統(tǒng)中經(jīng)常設置兩級或多級高速緩存；（3）緊靠內(nèi)存的一級高速緩存速度最高，容量最小，二級緩存容量稍大，速度也稍低。第8頁，共56頁，2023年，2月20日，星期一4.1存儲器的層次結構3.高速緩存和磁盤緩存磁盤緩存：并不是實際的存儲介質(zhì)，依托于固定磁盤，提供對主存儲器存儲空間的擴充。（1）磁盤的I/O速度遠低于主存的訪問速度；（2）主存也可以看做是輔存的高速緩存；（3）大容量的輔存常常使用磁盤，磁盤數(shù)據(jù)經(jīng)常備份到磁帶或者可移動的磁盤中，以防止硬盤故障時丟失數(shù)據(jù)。第9頁，共56頁，2023年，2月20日，星期一4.2程序的裝入和鏈接一個用戶源程序要變成一個可在內(nèi)存中執(zhí)行的程序都要經(jīng)過以下幾個步驟：編譯：將用戶源代碼編譯成目標代碼；鏈接：將目標模塊及它們所需要的庫函數(shù)鏈接在一起；裝入：將裝入模塊裝入內(nèi)存。庫鏈接程序編譯程序產(chǎn)生的目標模塊裝入模塊裝入程序內(nèi)存第一步第二步第三步第10頁，共56頁，2023年，2月20日，星期一4.2程序的裝入和鏈接絕對裝入方式（AbsoluteLoadingMode）編譯時，知道程序所駐留內(nèi)存的具體位置，編譯程序?qū)a(chǎn)生絕對地址的目標代碼，這個絕對地址可以在編譯或者匯編時給出，也可由程序員賦予。

1.程序的裝入可重定位裝入方式（RelocationLoadingMode）多道程序環(huán)境下，編譯程序不可能預知所編譯的目標模塊應放在內(nèi)存何處，所以目標模塊的起始地址通常從0開始，而程序中的其他地址則相對于起始地址計算而成。第11頁，共56頁，2023年，2月20日，星期一4.2程序的裝入和鏈接

1.程序的裝入動態(tài)運行時裝入方式（DynamicRun-timeLoadingMode）裝入程序把裝入模塊裝入內(nèi)存，并不立即把相對地址轉(zhuǎn)換為絕對地址，而是把地址轉(zhuǎn)換推遲到程序真正運行時再執(zhí)行。0LOAD1,2500100025005000365LOAD1,250036510000110001250015000第12頁，共56頁，2023年，2月20日，星期一4.2程序的裝入和鏈接

2.程序的鏈接靜態(tài)鏈接方式（StaticLinkingMode）(1)對相對地址進行修改；（2）變換外部調(diào)用符號模塊ACALLB；Return；0L-1模塊BCALLC；Return；0M-1模塊CReturn；0N-1模塊ACALLB；Return；0L-1模塊BCALLC；Return；L+M-1模塊CReturn；L+M+N-1LL+M第13頁，共56頁，2023年，2月20日，星期一4.2程序的裝入和鏈接

2.程序的鏈接裝入時動態(tài)鏈接方式（Load-timeDynamicLinkingMode）用戶源程序編譯后所得的目標模塊，在裝入內(nèi)存時邊裝入邊鏈接的，這種方式（1）便于修改和更新（2）便于實現(xiàn)對目標模塊的共享。運行時動態(tài)鏈接方式（Run-timeDynamicLinkingMode）許多情況下，應用程序每次要運行的模塊可能不相同，如果把所有模塊都裝入非常低效，所以要在運行過程中動態(tài)裝入所需模塊。第14頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式這是一種最簡單的存儲管理方式，只能用與單用戶單任務的操作系統(tǒng)，內(nèi)存分成系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)提供給OS使用，而用戶區(qū)指除了系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。

1.單一連續(xù)分配這是一種最簡單的可運行多道程序的存儲管理方式，它將內(nèi)存劃為固定大小的區(qū)域，每個分區(qū)裝入一道作業(yè)。

2.固定分區(qū)分配第15頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式

2.固定分區(qū)分配分區(qū)的劃分方法分區(qū)大小相等：所有分區(qū)大小相等，缺點是缺乏靈活性，程序太小時空間浪費，程序太大時無法運行；分區(qū)大小不等：克服了大小相等而缺乏靈活性的缺點，把內(nèi)存分成多個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。內(nèi)存分配：將分區(qū)按照大小進行排隊，并為之建立一張分區(qū)使用表，其各表項包括每個分區(qū)的起始地址、大小以及狀態(tài)。第16頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式

3.動態(tài)分區(qū)分配分區(qū)分配中的數(shù)據(jù)結構空閑分區(qū)表；空閑分區(qū)鏈。分區(qū)分配算法首次適應算法：找到第一個大小能滿足要求的空閑空間；循環(huán)首次適應算法：從上次找到的空閑分區(qū)的下一個開始查找，找到一個能滿足要求的空閑分區(qū)；最佳適應算法：找到一個滿足要求、又是最小的空閑分區(qū)分配給作業(yè)；最壞適應算法：挑選一個最大的空閑分區(qū)分割給作業(yè)；快速適應算法：將空閑分區(qū)根據(jù)其容量大小分類，然后根據(jù)進程的長度，尋找到能容納它的最小空閑分區(qū)鏈表，取下第一塊進行分配。第17頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式分區(qū)分配操作1）分配內(nèi)存：系統(tǒng)利用某種分配算法，從空閑分區(qū)鏈（表）中找到所需大小的分區(qū)。從頭開始查表檢索完否？m.size>u.size？m.size-u.size≤size？從該分區(qū)中劃出u.Size大小的分區(qū)將該分區(qū)分配給請求者修改有關數(shù)據(jù)結構返回返回繼續(xù)檢索下一個表項將該分區(qū)從鏈中移出YNNYYN第18頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式分區(qū)分配操作2）回收內(nèi)存：當進程運行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈（表）中找到相應的插入點。a）回收區(qū)與插入點的前一個空閑分區(qū)F1相鄰接，將回收區(qū)與插入點前的分區(qū)合并，不必為回收分區(qū)分配表項，修改前一分區(qū)F1的大小；b）回收區(qū)與插入點的后一空閑分區(qū)F2相鄰接，此時可將兩分區(qū)合并，形成新的空閑分區(qū)，回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和;…F1回收區(qū)………回收區(qū)F2……(a)(b)第19頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式分區(qū)分配操作2）回收內(nèi)存c）回收區(qū)同時與插入點的前、后兩個分區(qū)鄰接，此時將三個分區(qū)合并，使用F1的表項和首址，取消F2表項，大小為三者之和；d）回收區(qū)既不與F1鄰接，又不與F2鄰接，這時應為回收區(qū)單獨建立一新表項，填寫回收區(qū)的首址和大小，并根據(jù)首址插入到空閑鏈中的適當位置；…F1回收區(qū)……回收區(qū)……F2…(c)(d)第20頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式固定分區(qū)方式的不足：限制了活動進程的數(shù)目，當進程大小和空閑分區(qū)大小不匹配時，空間利用率很低。動態(tài)分區(qū)方式的不足：算法復雜，回收空閑分區(qū)時需要進行分區(qū)合并等，系統(tǒng)開銷大?；锇橄到y(tǒng)：上面兩種內(nèi)存方式的一種折衷，伙伴系統(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪，l≤k≤m，其中是分配的最小分區(qū)的大小，表示分配的最大分區(qū)的大小，通常是整個可分配內(nèi)存的大小。

4.伙伴系統(tǒng)伙伴系統(tǒng)的優(yōu)點：算法在回收空閑分區(qū)時，需要對空閑分區(qū)進行合并，所以其時間性能比前面分類搜索算法差，但比順序搜索算法好，而其空間性能則遠優(yōu)于前面所述的分類搜索法，比順序搜索法略差。第21頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式哈希算法就是利用哈?？焖俨檎业膬?yōu)點，以及空閑分區(qū)在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，構造一張以空閑分區(qū)大小為關鍵字的哈希表。

5.哈希算法

6.可重定位分區(qū)分配動態(tài)可重定位：它的引入是為了解決系統(tǒng)中只有若干個小分區(qū)，即使它們?nèi)萘恐痛笥谝b入的程序，但由于這些分區(qū)不相鄰接，無法裝入該程序的情況。第22頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式

6.可重定位分區(qū)分配操作系統(tǒng)用戶程序110KB用戶程序330KB用戶程序614KB用戶程序926KB操作系統(tǒng)用戶程序1用戶程序3用戶程序6用戶程序980KB采用的方法：將內(nèi)存中的所有作業(yè)進行移動，使它們?nèi)肯噜徑樱@樣，即可把原來分散的多個小分區(qū)拼接成一個大分區(qū)，這時就可以把作業(yè)裝入該區(qū)。定義：通過移動內(nèi)存中作業(yè)的位置，把原來多個分散的小分區(qū)拼接成一個大分區(qū)的方法，稱為“拼接”或“緊湊”。第23頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式

6.可重定位分區(qū)分配動態(tài)可重定位的實現(xiàn)：作業(yè)裝入內(nèi)存后的所有地址仍然是相對地址，將相對地址轉(zhuǎn)換為物理地址的工作，被推遲到程序指令要真正執(zhí)行時運行。LOAD1,2500365500025001000作業(yè)J250010000相對地址重定位寄存器+LOAD1,250036515000125001010010000主存第24頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式

6.可重定位分區(qū)分配動態(tài)重定位分區(qū)分配算法：類似于動態(tài)分區(qū)分配算法，不過是在算法中增加了緊湊功能，通常在找不到足夠大的空閑分區(qū)來滿足用戶需求時進行緊湊。請求分配u.size分區(qū)檢索空閑分區(qū)鏈（表）找到大于u.size的可用分區(qū)否？按動態(tài)分區(qū)方式進行分配修改有關的數(shù)據(jù)結構返回分區(qū)號及首批空閑分區(qū)總和≥u.size？無法分配返回緊湊形成連續(xù)空閑區(qū)修改有關的數(shù)據(jù)結構否是是否第25頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式

7.對換（Swapping）對換的引入的原因：多道程序環(huán)境下，內(nèi)存中的一些進程因某事件而被阻塞運行，卻占用大量內(nèi)存空間，甚至可能所有進程阻塞而迫使CPU停止下來等待的情況；另一方面，許多作業(yè)在外存上等待，因無內(nèi)存而不能運行。對換的定義：是指把內(nèi)存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)調(diào)出內(nèi)存上，以便騰出足夠的內(nèi)存空間，再把具備運行條件的進程或進程所需的程序和數(shù)據(jù)調(diào)入內(nèi)存。第26頁，共56頁，2023年，2月20日，星期一4.3連續(xù)分配方式

7.對換（Swapping）對換空間的管理：通常把外存分為文件區(qū)和對換區(qū)，其中文件區(qū)用于存放文件，對換區(qū)用于存放從內(nèi)存換出的進程。進程的換出與換入進程的換出：首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，然后啟動磁盤，將進程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上；進程的換入：系統(tǒng)應定時地查看所有進程的狀態(tài)，找出“就緒”狀態(tài)但已經(jīng)換出的進程，將其中換出時間最久的進程作為換入進程，將之換入，直至已無可換入和無可換出進程為止。第27頁，共56頁，2023年，2月20日，星期一4.4基本分頁存儲管理方式頁面

1）頁面和物理塊，適用于批處理系統(tǒng)或者實時性要求不高的系統(tǒng)；

2）頁面大小，能更好地滿足緊迫作業(yè)，適合于嚴格的實時系統(tǒng)或者對性能要求較高的批處理和分時系統(tǒng)中。

1.頁面和頁表地址結構：分頁地址中的地址結構包括兩部分：前一部分是頁號P，后一部分為位移量W（或稱為頁內(nèi)地址）。位移量W頁號P3112110頁表：在分頁系統(tǒng)中，允許各個頁離散地存儲在內(nèi)存不同的物理塊內(nèi)，但系統(tǒng)要保證進程的正確執(zhí)行，所以系統(tǒng)又為每個進程建立了一張頁面映射表。若給定一個邏輯地址空間中的地址為A，頁面的大小為L，則頁號P和頁內(nèi)地址d可按下式求得：第28頁，共56頁，2023年，2月20日，星期一4.4基本分頁存儲管理方式基本的地址變換機構

2.地址變換機構頁表長度頁表首址當進程要訪問某個邏輯地址中的數(shù)據(jù)時，分頁地址變換機構會自動地將有效地址（相對地址）分為頁號和頁內(nèi)地址兩部分，再以頁號為索引去檢索頁表。頁表寄存器+頁內(nèi)地址頁號（3）邏輯地址L>1

b

頁表物理地址塊號頁號0123越界中斷第29頁，共56頁，2023年，2月20日，星期一4.4基本分頁存儲管理方式具有快表的地址變換機構

2.地址變換機構頁表長度頁表首址在CPU給出有效地址后，由地址變換機構自動將頁號P送入高速緩沖寄存器，并將此頁號與高速緩存中的所有頁號進行比較，若找到匹配的頁號，就表示要訪問的頁表項在快表中。頁表寄存器+頁內(nèi)地址頁號邏輯地址L>b

頁表db物理地址塊號頁號越界中斷輸入寄存器b

快表塊號頁號

第30頁，共56頁，2023年，2月20日，星期一4.4基本分頁存儲管理方式兩級頁表

3.兩級和多級頁表P2P1對于32位的機器，采用兩級頁表結構是合適的；但對于64位的機器，可以支持2的64次方（1884744TB）規(guī)模的物理存儲空間，一般可以利用三級頁表結構來實現(xiàn)。外部頁號+

…頁表db物理地址

…外部頁表

d外部頁表寄存器+外部頁內(nèi)地址頁內(nèi)地址邏輯地址多級頁表第31頁，共56頁，2023年，2月20日，星期一4.5基本分段存儲管理方式方便編程通常，用戶把自己的作業(yè)按照邏輯關系劃分為若干個段，每個段都是從0開始編址，并且有自己的名字和長度。

1.分段存儲管理方式的引入信息共享在實現(xiàn)對程序和數(shù)據(jù)的共享時，是以信息的邏輯單位為基礎的。分頁系統(tǒng)中的“頁”只是存放信息的物理塊，并無完整的意義，不便于實現(xiàn)共享，而段卻是信息的邏輯單位。信息保護信息保護同樣是對信息的邏輯單位進行保護，因此，分段管理方式能更有效和方便地實現(xiàn)信息保護功能。動態(tài)增長實際應用中，往往有些段，特別是數(shù)據(jù)段，在使用過程中會不斷增長，而事先無法確切地知道數(shù)據(jù)段會增長到多大，這時候其他存儲管理方式無法解決這個問題。動態(tài)鏈接在作業(yè)運行之前，并不把幾個目標程序段鏈接起來，而是在運行過程中需要調(diào)用某段時，才將該段調(diào)入內(nèi)存進行鏈接。第32頁，共56頁，2023年，2月20日，星期一4.5基本分段存儲管理方式分段在這里，作業(yè)的地址空間被劃分為若干個段，每個段定義了一組邏輯信息。例如出程序段MAIN、子程序段X、數(shù)據(jù)段D和棧段S等。

2.分段系統(tǒng)的基本原理段表在分段式存儲管理系統(tǒng)中，為每個分段分配一個連續(xù)的分區(qū)，而進程中的每個段可以離散地移入內(nèi)存中不同的分區(qū)中，像分頁系統(tǒng)一樣，在系統(tǒng)中為每個進程建立一張映射表，稱為“段表”。作業(yè)空間（MAIN）=0030K（X）=1020K（D）=2015K（S）=3010K30K20K15K10K40K80K120K150K段表段號段長基址0123（MAIN）=030K（X）=120K（D）=215K（S）=310K內(nèi)存空間40K80K120K150K第33頁，共56頁，2023年，2月20日，星期一4.5基本分段存儲管理方式分段系統(tǒng)的地址變換過程在系統(tǒng)中設置了段表寄存器，用于存放段表始址和段表長度TL。在進行地址變換時，將邏輯地址中的段號和段表長度TL進行比較。若S>TL，表示段號太大，訪問越界，產(chǎn)生越界中斷信號；若未越界，則根據(jù)段表的始址和該段的段號，計算出該段對應段表項的位置，從中讀出該段在內(nèi)存中的起始地址，進而將該段基址d與段內(nèi)地址相加，得到要訪問的內(nèi)存物理地址。

2.分段系統(tǒng)的基本原理段表長度段表首址控制寄存器+1002段號S位移量W>主存越界中斷6K4K8K9200基址段長1K600500200段號0123+82928K82928692第34頁，共56頁，2023年，2月20日，星期一4.5基本分段存儲管理方式分段和分頁的主要區(qū)別分段和分頁都采用離散分配方式，且都要通過地址映射機構來實現(xiàn)地址變換，這是它們的相似之處，但是在概念上兩者完全不同，主要表現(xiàn)在：

2.分段系統(tǒng)的基本原理分頁分段目的提高內(nèi)存的利用率更好地滿足用戶需求形式信息的物理單位信息的邏輯單位大小頁的大小固定且由系統(tǒng)決定段的長度不固定，由用戶編寫的程序決定地址空間一維，單一的線性空間二維，包括段名和段內(nèi)地址

3.信息共享分段系統(tǒng)的優(yōu)點：允許多個進程共享一個或多個分段?？芍厝氪a是一種允許多個進程同時訪問的代碼，不允許可重入代碼在執(zhí)行中有任何改變。第35頁，共56頁，2023年，2月20日，星期一4.5基本分段存儲管理方式基本原理：是分段和分頁原理的結合，即先將用戶程序分成若干個段，然后再把每個段分成若干個頁，并為每個段賦予一個段名。

4.段頁式存儲管理方式段表始址段表大小段表寄存器主存段號狀態(tài)頁表大小頁表始址0111213041頁號狀態(tài)存儲塊#0111213041頁表操作系統(tǒng)第36頁，共56頁，2023年，2月20日，星期一4.5基本分段存儲管理方式地址變換過程

4.段頁式存儲管理方式段表長度段表首址段表寄存器+頁號P段號S>段超長頁表始址頁表長度段表0123+頁內(nèi)地址塊內(nèi)地址塊號bb頁表0123第37頁，共56頁，2023年，2月20日，星期一4.6虛擬存儲器的基本概念常規(guī)存儲器管理方式的特征一次性：作業(yè)在運行前要一次性裝入內(nèi)存；駐留性：作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運行結束。

1.虛擬存儲器的引入局部性原理1968年Denning.P指出：程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律，即在較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分；相應地，它所訪問的存儲空間也局限于某個區(qū)域，他提出幾個論點：（1）除了少部分轉(zhuǎn)移和過程調(diào)用指令，程序大多數(shù)情況下是順序執(zhí)行的；（2）過程調(diào)用會讓程序的執(zhí)行由一部分區(qū)域移至另一部分區(qū)域；（3）程序中存在許多循環(huán)結構，雖然由少數(shù)指令構成，但是要多次執(zhí)行；（4）程序中許多對數(shù)據(jù)結構（如數(shù)組）的操作，往往局限于很小的范圍內(nèi)。第38頁，共56頁，2023年，2月20日，星期一4.6虛擬存儲器的基本概念

1.虛擬存儲器的引入局限性表現(xiàn)時間局限性：如果程序中的某條指令一旦執(zhí)行，不久以后該指令可能再次執(zhí)行，數(shù)據(jù)訪問也是類似；空間局限性：一旦程序訪問了某個存儲單元，不久以后，其附近的存儲單元也將被訪問，即程序某一段時間訪問的地址可能集中在一定范圍內(nèi)。虛擬存儲器的定義：是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。

2.虛擬存儲器的特征（1）多次性（2）對換性（3）虛擬性第39頁，共56頁，2023年，2月20日，星期一4.6虛擬存儲器的基本概念虛擬存儲器中，允許將一個作業(yè)分多次調(diào)入內(nèi)存，它的實現(xiàn)毫無例外地建立在離散分配的存儲管理方式的基礎上。（1）請求分頁系統(tǒng)在基本分頁系統(tǒng)的基礎上，增加了請求調(diào)頁功能和頁面置換功能所形成的頁式虛擬存儲系統(tǒng)。硬件支持包括(a)請求分頁的頁表機制(b)缺頁中斷機構(c)地址變換機構；軟件支持：包括用于請求調(diào)頁的軟件和實現(xiàn)頁面置換的軟件。（2）請求分段系統(tǒng)在分段系統(tǒng)的基礎上，增加了請求調(diào)段及分段置換功能后所形成的段式虛擬存儲系統(tǒng)。硬件支持包括(a)請求分段的段表機制(b)缺段中斷機構(c)地址變換機構軟件支持：包括用于請求調(diào)段的軟件和實現(xiàn)段面置換的軟件。

3.虛擬存儲器的實現(xiàn)方法第40頁，共56頁，2023年，2月20日，星期一4.7請求分頁存儲管理方式頁表機制在請求分頁系統(tǒng)中所需要的主要數(shù)據(jù)結構是頁表，其基本作用是將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址。

1.請求分頁中的硬件支持缺頁中斷機構當所要訪問的頁面不在內(nèi)存時，便產(chǎn)生一缺頁中斷，請求OS將所缺之頁調(diào)入內(nèi)存，它和一般中斷的區(qū)別主要表現(xiàn)在：（1）在指令執(zhí)行期間產(chǎn)生和處理中斷信號；（2）一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。（1）狀態(tài)位P：標識本段的存取屬性是只執(zhí)行，只讀，還是允許讀/寫;（2）訪問字段A：用于記錄該段被訪問的頻繁程度；（3）修改位M：用于表示該頁進入內(nèi)存后是否被修改過；（4）外存始址：指示本段在外存中的起始地址，即起始盤塊號。頁號物理塊號訪問字段A修改位M狀態(tài)位P外存始址第41頁，共56頁，2023年，2月20日，星期一4.7請求分頁存儲管理方式

1.請求分頁中的硬件支持地址變換機構

開始頁號>頁表長度？CPU檢索快表否是訪問頁表頁表項在快表中？頁在內(nèi)存？修改快表修改訪問位和修改位形成物理地址地址變換結束保留CPU現(xiàn)場從外存中找到缺頁內(nèi)存滿否？選擇一頁換出該頁被修改否？將該頁寫回內(nèi)存OS命令CPU從外存讀缺頁啟動I/O硬件將一頁從外存換入內(nèi)存修改頁表越界中斷否是否是是否是產(chǎn)生缺頁中斷請求調(diào)頁程序請求訪問一頁第42頁，共56頁，2023年，2月20日，星期一4.7請求分頁存儲管理方式

2.內(nèi)存分配策略和分配算法最小物理塊數(shù)的確定最小物理塊數(shù)是只能保證進程正常運行所需的最小物理塊數(shù)，當系統(tǒng)為進程分配的物理塊數(shù)少于此值時，進程將無法運行。物理塊的分配策略

1）固定分配局部置換：為每個進程分配一定數(shù)目的物理塊，在整個運行期間不再改變；

2）可變分配全局置換：為每個進程分配一定數(shù)目的物理塊，OS自身也保持一個空閑物理塊隊列，用于分配給缺頁進程；

3）可變分配局部置換：為每個進程分配一定數(shù)目的物理塊，當缺頁時，只允許該進程從內(nèi)存的頁面中選出一頁換出，這樣不會影響其他進程。第43頁，共56頁，2023年，2月20日，星期一4.7請求分頁存儲管理方式

2.內(nèi)存分配策略和分配算法物理塊的分配算法1）平均分配法：將系統(tǒng)中所有可供分配的物理塊平均分配給各個進程；2）按比例分配法：按照進程的大小按比例分配物理塊；3）考慮優(yōu)先級的分配法：通常把內(nèi)存中可供分配的物理塊分成兩部分，一部分按比例分配給各進程，另一部分則根據(jù)各進程的優(yōu)先級，適當增加其份額，分配給各進程。

3.調(diào)頁策略調(diào)入頁面的時機1）預調(diào)頁策略2）請求調(diào)頁策略第44頁，共56頁，2023年，2月20日，星期一4.7請求分頁存儲管理方式

3.調(diào)頁策略確定從何處調(diào)入頁面請求分頁系統(tǒng)中的外存分成兩部分：文件區(qū)（用于存放文件）和對換區(qū)（用戶存放對換頁面），缺頁請求調(diào)頁時分下列三種情況：1）系統(tǒng)擁有足夠的兌換空間，此時可全部從兌換區(qū)調(diào)入所需頁面；2）系統(tǒng)缺少足夠的對換區(qū)空間，此時不會被修改的文件從文件區(qū)調(diào)入；3）UNIX方式：凡是未運行過的頁面都應從文件區(qū)調(diào)入，曾經(jīng)運行過的頁面都從對換區(qū)調(diào)入。頁面調(diào)入過程當程序要訪問的頁面未在內(nèi)存時，便向CPU發(fā)出缺頁中斷，中斷處理程序會保留CPU環(huán)境，分析中斷原因并轉(zhuǎn)入中斷處理程序，在外村中找到缺頁的物理塊，如果內(nèi)存能容納，則將之調(diào)入，否則根據(jù)算法選擇一頁換出，并修改相應的數(shù)據(jù)結構。第45頁，共56頁，2023年，2月20日，星期一4.8頁面置換算法

1.先進先出（FIFO）頁面置換算法最早出現(xiàn)的置換算法，總是淘汰最先進入內(nèi)存的頁面。

2.最佳（Optimal）頁面置換算法1966年由Belady提出的，選擇的被淘汰的頁面都是以后永不使用或者在最長（未來）時間內(nèi)。701203042303212017012312304304204230230130127127027017

70

701201缺頁次數(shù)為15次，缺頁率:15/20=75%701203042303212017017

70

701201203243203201701缺頁次數(shù)為9次，缺頁率:9/20=45%第46頁，共56頁，2023年，2月20日，星期一4.8頁面置換算法

3.最近最久未使用（LRU）頁面置換算法地址變換機構LRU算法選擇最近最久未使用的頁面予以淘汰。LRU的硬件支持1）寄存器：為了記錄某個進程在內(nèi)存中各頁的使用情況，需要為每個內(nèi)存中的頁面設置一個寄存器。2）棧：每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。203403402432032132102107701203042303212017017

70

701201缺頁次數(shù)為12次，缺頁率:12/20=60%

4.其他頁面置換算法最少使用置換算法和頁面緩沖算法。第47頁，共56頁，2023年，2月20日，星期一4.9請求分段存儲管理方式

1.請求分段中的硬件支持段表機制請求分段式管理中所需的主要數(shù)據(jù)結構是段表。段表項中，除了段名（號）、段長、段在內(nèi)存中的起始地址外，增加了：（1）存取方式：標識本段的存取屬性是只執(zhí)行，只讀，還是允許讀/寫;（2）訪問字段A：用于記錄該段被訪問的頻繁程度；（3）修改位M：用于表示該頁進入內(nèi)存后是否被修改過；（4）存在位P：指示本段是否已調(diào)入內(nèi)存；（5）增補位：用于表示本段在運行過程中是否做過動態(tài)增長；（6）外存始址：指示本段在外存中的起始地址，即起始盤塊號。段名段的基址段長存取方式訪問字段A修改位M存在位P增補位外存始址第48頁，共56頁，2023年，2月20日，星期一4.9請求分段存儲管理方式

1.請求分段中的硬件支持缺段中斷機構在請求分段系統(tǒng)中，當發(fā)現(xiàn)運行進程所要訪問的段尚未調(diào)入內(nèi)存時，便由缺段中斷機構產(chǎn)生缺段中斷信號，進入OS后由缺段中斷處理程序?qū)⑺璧亩握{(diào)入內(nèi)存。虛段S不在內(nèi)存內(nèi)存中有合適的空閑區(qū)嗎？修改段表及內(nèi)存空區(qū)鏈喚醒請求進程返回阻塞請求進程淘汰一個或幾個實段，以形成一個合適空區(qū)空區(qū)拼接，以形成一個合適的空區(qū)是否否是空區(qū)容量總和能滿足要求？從外存讀入段S第49頁，共56頁，2023年，2月20日，星期一4.9請求分段存儲管理方式

1.請求分段中的硬件支持地址變換機構請求分段系統(tǒng)中的地址變換機構是在分段系統(tǒng)地址變換機構的基礎上形成的，地址變幻時，如果要訪問的段不在內(nèi)存，必須先將所缺的段調(diào)入內(nèi)存，并修改段表，然后才能利用段表進行地址變換。訪問[s][w]w≤段長？符合存取方式？段S在主存？修改訪問字段，如寫訪問，置修改位=1形成訪問主存地址(A)=(主存地址)+(位移量w)返回分段越界中斷處理分段保護中斷處理缺段中斷處理是否否否是是第50頁，共56頁，2023年，2月20日，星期一4.9請求分段存儲管理方式