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

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

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

1.程序的裝入可重定位裝入方式（RelocationLoadingMode）多道程序環(huán)境下，編譯程序不可能預(yù)知所編譯的目標(biāo)模塊應(yīng)放在內(nèi)存何處，所以目標(biāo)模塊的起始地址通常從0開(kāi)始，而程序中的其他地址則相對(duì)于起始地址計(jì)算而成。第11頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.2程序的裝入和鏈接

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

2.程序的鏈接靜態(tài)鏈接方式（StaticLinkingMode）(1)對(duì)相對(duì)地址進(jìn)行修改；（2）變換外部調(diào)用符號(hà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頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.2程序的裝入和鏈接

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

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

2.固定分區(qū)分配第15頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.3連續(xù)分配方式

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

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

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

5.哈希算法

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

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

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

6.可重定位分區(qū)分配動(dòng)態(tài)重定位分區(qū)分配算法：類似于動(dòng)態(tài)分區(qū)分配算法，不過(guò)是在算法中增加了緊湊功能，通常在找不到足夠大的空閑分區(qū)來(lái)滿足用戶需求時(shí)進(jìn)行緊湊。請(qǐng)求分配u.size分區(qū)檢索空閑分區(qū)鏈（表）找到大于u.size的可用分區(qū)否？按動(dòng)態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號(hào)及首批空閑分區(qū)總和≥u.size？無(wú)法分配返回緊湊形成連續(xù)空閑區(qū)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)否是是否第25頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.3連續(xù)分配方式

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

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

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

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

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

2.地址變換機(jī)構(gòu)頁(yè)表長(zhǎng)度頁(yè)表首址當(dāng)進(jìn)程要訪問(wèn)某個(gè)邏輯地址中的數(shù)據(jù)時(shí)，分頁(yè)地址變換機(jī)構(gòu)會(huì)自動(dòng)地將有效地址（相對(duì)地址）分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，再以頁(yè)號(hào)為索引去檢索頁(yè)表。頁(yè)表寄存器+頁(yè)內(nèi)地址頁(yè)號(hào)（3）邏輯地址L>1

b

頁(yè)表物理地址塊號(hào)頁(yè)號(hào)0123越界中斷第29頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.4基本分頁(yè)存儲(chǔ)管理方式具有快表的地址變換機(jī)構(gòu)

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

頁(yè)表db物理地址塊號(hào)頁(yè)號(hào)越界中斷輸入寄存器b

快表塊號(hào)頁(yè)號(hào)

第30頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.4基本分頁(yè)存儲(chǔ)管理方式兩級(jí)頁(yè)表

3.兩級(jí)和多級(jí)頁(yè)表P2P1對(duì)于32位的機(jī)器，采用兩級(jí)頁(yè)表結(jié)構(gòu)是合適的；但對(duì)于64位的機(jī)器，可以支持2的64次方（1884744TB）規(guī)模的物理存儲(chǔ)空間，一般可以利用三級(jí)頁(yè)表結(jié)構(gòu)來(lái)實(shí)現(xiàn)。外部頁(yè)號(hào)+

…頁(yè)表db物理地址

…外部頁(yè)表

d外部頁(yè)表寄存器+外部頁(yè)內(nèi)地址頁(yè)內(nèi)地址邏輯地址多級(jí)頁(yè)表第31頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.5基本分段存儲(chǔ)管理方式方便編程通常，用戶把自己的作業(yè)按照邏輯關(guān)系劃分為若干個(gè)段，每個(gè)段都是從0開(kāi)始編址，并且有自己的名字和長(zhǎng)度。

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

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

2.分段系統(tǒng)的基本原理段表長(zhǎng)度段表首址控制寄存器+1002段號(hào)S位移量W>主存越界中斷6K4K8K9200基址段長(zhǎng)1K600500200段號(hào)0123+82928K82928692第34頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.5基本分段存儲(chǔ)管理方式分段和分頁(yè)的主要區(qū)別分段和分頁(yè)都采用離散分配方式，且都要通過(guò)地址映射機(jī)構(gòu)來(lái)實(shí)現(xiàn)地址變換，這是它們的相似之處，但是在概念上兩者完全不同，主要表現(xiàn)在：

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

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

4.段頁(yè)式存儲(chǔ)管理方式段表始址段表大小段表寄存器主存段號(hào)狀態(tài)頁(yè)表大小頁(yè)表始址0111213041頁(yè)號(hào)狀態(tài)存儲(chǔ)塊#0111213041頁(yè)表操作系統(tǒng)第36頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.5基本分段存儲(chǔ)管理方式地址變換過(guò)程

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

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

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

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

3.虛擬存儲(chǔ)器的實(shí)現(xiàn)方法第40頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式頁(yè)表機(jī)制在請(qǐng)求分頁(yè)系統(tǒng)中所需要的主要數(shù)據(jù)結(jié)構(gòu)是頁(yè)表，其基本作用是將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址。

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

1.請(qǐng)求分頁(yè)中的硬件支持地址變換機(jī)構(gòu)

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

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

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

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

3）可變分配局部置換：為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，當(dāng)缺頁(yè)時(shí)，只允許該進(jìn)程從內(nèi)存的頁(yè)面中選出一頁(yè)換出，這樣不會(huì)影響其他進(jìn)程。第43頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式

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

3.調(diào)頁(yè)策略調(diào)入頁(yè)面的時(shí)機(jī)1）預(yù)調(diào)頁(yè)策略2）請(qǐng)求調(diào)頁(yè)策略第44頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.7請(qǐng)求分頁(yè)存儲(chǔ)管理方式

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

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

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

70

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

70

701201203243203201701缺頁(yè)次數(shù)為9次，缺頁(yè)率:9/20=45%第46頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.8頁(yè)面置換算法

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

70

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

4.其他頁(yè)面置換算法最少使用置換算法和頁(yè)面緩沖算法。第47頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.9請(qǐng)求分段存儲(chǔ)管理方式

1.請(qǐng)求分段中的硬件支持段表機(jī)制請(qǐng)求分段式管理中所需的主要數(shù)據(jù)結(jié)構(gòu)是段表。段表項(xiàng)中，除了段名（號(hào)）、段長(zhǎng)、段在內(nèi)存中的起始地址外，增加了：（1）存取方式：標(biāo)識(shí)本段的存取屬性是只執(zhí)行，只讀，還是允許讀/寫(xiě);（2）訪問(wèn)字段A：用于記錄該段被訪問(wèn)的頻繁程度；（3）修改位M：用于表示該頁(yè)進(jìn)入內(nèi)存后是否被修改過(guò)；（4）存在位P：指示本段是否已調(diào)入內(nèi)存；（5）增補(bǔ)位：用于表示本段在運(yùn)行過(guò)程中是否做過(guò)動(dòng)態(tài)增長(zhǎng)；（6）外存始址：指示本段在外存中的起始地址，即起始盤(pán)塊號(hào)。段名段的基址段長(zhǎng)存取方式訪問(wèn)字段A修改位M存在位P增補(bǔ)位外存始址第48頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.9請(qǐng)求分段存儲(chǔ)管理方式

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

1.請(qǐng)求分段中的硬件支持地址變換機(jī)構(gòu)請(qǐng)求分段系統(tǒng)中的地址變換機(jī)構(gòu)是在分段系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上形成的，地址變幻時(shí)，如果要訪問(wèn)的段不在內(nèi)存，必須先將所缺的段調(diào)入內(nèi)存，并修改段表，然后才能利用段表進(jìn)行地址變換。訪問(wèn)[s][w]w≤段長(zhǎng)？符合存取方式？段S在主存？修改訪問(wèn)字段，如寫(xiě)訪問(wèn)，置修改位=1形成訪問(wèn)主存地址(A)=(主存地址)+(位移量w)返回分段越界中斷處理分段保護(hù)中斷處理缺段中斷處理是否否否是是第50頁(yè)，課件共56頁(yè)，創(chuàng)作于2023年2月4.9請(qǐng)求分段存儲(chǔ)管理方式