計(jì)算機(jī)操作系統(tǒng)教程-第四版-(張堯?qū)W著)-清華大學(xué)出版社-第5章new存儲管理課件

存儲管理

寄存器、高速緩存區(qū)存儲器cache、主存儲器、外存儲器一、存儲管理概述

1.存儲器類型虛擬地址空間作業(yè)大小，是指作業(yè)中各程序虛擬地址空間大小的總和。2.虛擬地址(VirtualAddress)和物理地址(PhysicalAddress)程序裝入(ProgrammingLoading)重定位(Relocation)靜態(tài)重定位(StaticRelocations)動態(tài)重定位(DynamicRelocation)3.重定位(Relocation)/地址轉(zhuǎn)換系統(tǒng)空間(SystemSpace)和用戶空間(UserSpace)存儲管理目的提高主存儲器的利用率方便用戶對主存儲空間的使用靜態(tài)重定位(StaticRelocations)4.存儲管理的目的存儲空間的分配和回收設(shè)計(jì)合理適的數(shù)據(jù)結(jié)構(gòu)，登記存儲單元的使用情況設(shè)計(jì)分配算法存儲空間回收重定位存儲空間的共享與保護(hù)界限寄存器法保護(hù)鍵法界限寄存器和CPU工作模式虛擬存儲器5.存儲管理的主要功能分區(qū)管理分頁管理分段管理段頁式管理6.存儲管理方法單任務(wù)二、單一連續(xù)區(qū)存儲管理用戶區(qū)分成若干個(gè)長度不等的存儲區(qū)域（分區(qū)），啟動之后長度不變，一個(gè)分區(qū)一道作業(yè)。三、固定分區(qū)存儲管理

1.基本思想（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)分區(qū)說明表(DPT,DescriptivePartition‘sTable)由分區(qū)號、起始地址、分區(qū)長度和狀態(tài)組成2.實(shí)現(xiàn)關(guān)鍵（2）分配和回收（3）重定位和存儲保護(hù)程序大小為xi=1分區(qū)i的長度?y分區(qū)i的狀態(tài)==0?置分區(qū)i的狀態(tài)=1置進(jìn)程PCB中程序位置=i分配完成i=i+1i>分區(qū)數(shù)?x>最大分區(qū)的長度?推遲裝入，等待下次調(diào)度提示：程序超過分區(qū)長度，不能裝入！圖5-6固定分區(qū)的分配流程yyy能夠支持多道程序設(shè)計(jì)并發(fā)執(zhí)行的進(jìn)程數(shù)受分區(qū)個(gè)數(shù)的限制程序大小受分區(qū)長度的限制存在“碎片”3.主要特點(diǎn)減少碎片用戶區(qū)作為空閑區(qū)，根據(jù)程序?qū)嶋H需求量，分配空間，并可回收使用后的空間。

四、可變分區(qū)存儲管理

1.基本思想（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)可用表空閑區(qū)鏈表請求表struct

FreeNode{ longstart； //分區(qū)的起始地址

longlength； //分區(qū)的長度

struct

FreeNode*next； //向下指針

}*freePartitionsList； //空閑區(qū)鏈表頭指針2.實(shí)現(xiàn)關(guān)鍵空閑區(qū)鏈表（2）分配動態(tài)分區(qū)存儲空間分配的基本策略最先適應(yīng)法(FF，F(xiàn)irstFit)最佳適應(yīng)法(BF，BestFit)最壞適應(yīng)法(WF，WorstBestFit)程序A、B、C和D，它們的虛擬地址空間大小分別是80K、30K、130K和25K。（3）回收合并判斷在回收一個(gè)分區(qū)時(shí)，系統(tǒng)中空閑區(qū)的個(gè)數(shù)變化情況是：滿足圖5-12(a)類型時(shí)，空閑區(qū)個(gè)數(shù)增加1個(gè)；滿足圖5-12(b)或(c)類型時(shí)空閑區(qū)個(gè)數(shù)不變；而滿足圖5-12(d)類型時(shí)，空閑區(qū)的個(gè)數(shù)反而減少1個(gè)。（4）重定位及存儲保護(hù)動態(tài)重定位界限寄存器法存在外碎片(ExternalFragmentation)，降低了存儲空間的利用率分區(qū)個(gè)數(shù)和每個(gè)分區(qū)的長度都在變化為進(jìn)程的動態(tài)擴(kuò)充存儲空間提供可能需要相鄰空間區(qū)的合并，增加系統(tǒng)的開銷基本分配算法FF、BF和WF，在存儲空間利用率上沒有很大差別3.主要特點(diǎn)（1）存儲空間連續(xù)分配，管理方法容易實(shí)現(xiàn)（2）存在碎片，存儲空間利用率不高(內(nèi)碎片和外碎片的區(qū)別)內(nèi)部碎片：就是已經(jīng)被分配出去（能明確指出屬于哪個(gè)進(jìn)程）卻不能被利用的內(nèi)存空間；外部碎片指的是還沒有被分配出去（不屬于任何進(jìn)程），但由于太小了無法分配給申請內(nèi)存空間的新進(jìn)程的內(nèi)存空閑區(qū)域。從存儲單元的狀態(tài)看，內(nèi)碎片是分配狀態(tài)，外碎片是空閑狀態(tài)從長度看，內(nèi)碎片的長度可能很大，但外碎片的長度往往比較小。（3）程序大小受分區(qū)的限制4.分區(qū)管理總結(jié)對換技術(shù)是由操作系統(tǒng)實(shí)現(xiàn)，程序員或用戶看不到進(jìn)程的調(diào)出/調(diào)入過程對換技術(shù)可以增加并發(fā)執(zhí)行的進(jìn)程數(shù)，或者使得當(dāng)前運(yùn)行的進(jìn)程擁有更多的可用存儲空間5.對換(Swaping)和覆蓋(Overlay)覆蓋技術(shù)(Overlay)是早期操作系統(tǒng)(DOS)采用的一種內(nèi)存邏輯擴(kuò)充技術(shù)程序員：可覆蓋結(jié)構(gòu)設(shè)計(jì)操作系統(tǒng)提供關(guān)于內(nèi)存空間的分配、撤銷和設(shè)置(Setblock)等存儲管理的系統(tǒng)調(diào)用，以及程序裝入或程序裝入并運(yùn)行等的進(jìn)程管理的系統(tǒng)調(diào)用（也稱為EXEC功能）（1）內(nèi)存分塊五、分頁存儲管理

1.基本思想（2）進(jìn)程分頁分頁存儲管理由操作系統(tǒng)和硬件共同實(shí)現(xiàn)由虛擬地址a計(jì)算頁號p和頁內(nèi)地址w的兩種方法：p=a>>k, w=a&p=a/b,w=a%b。（3）非連續(xù)分配分頁存儲管理又分為靜態(tài)分頁和動態(tài)分頁兩種（1）位示圖(bitmap)及其作用假定某內(nèi)存空間共256個(gè)塊，機(jī)器字長為16位，那么，表示內(nèi)存塊使用狀況的位示圖，如圖5-17所示。2.靜態(tài)分頁的實(shí)現(xiàn)關(guān)鍵假定，在位示圖中的一個(gè)位用bitmap[i,j]表示，其中i稱為字號，表示第i行即第i個(gè)字；j稱為位號，表示在第i個(gè)字中的第j位，這里規(guī)定從低位開始計(jì)算。如果位示圖中的第i個(gè)字記為bitmap[i]，那么

bitmap[i,j]=(bitmap[i]>>j)&1位示圖的一個(gè)位bitmap[i,j]表示的塊號為b，可以計(jì)算得到b=字長*i+j相反地，如果已知一個(gè)塊的塊號，那么，這個(gè)塊在位示圖中的位bitmap[i,j]，則有

i=b/字長，j=b%字長空閑塊鏈表（2）頁表(PageTable)及其作用每一個(gè)進(jìn)程都有一個(gè)頁表，頁表描述進(jìn)程頁與塊的對應(yīng)關(guān)系頁表的主要作用是重定位和存儲保護(hù)頁表的建立和初始化過程-內(nèi)存分配（3）請求表（4）重定位及存儲保護(hù)重定位過程，其步驟概括如下：1)頁號p和頁內(nèi)地址w2)存儲保護(hù)3)利用頁表得到塊號4)形成物理地址分頁重定位在某靜態(tài)分頁存儲管理中，已知內(nèi)存共的32塊，塊長度為4K，當(dāng)前位示圖如圖5-22所示，進(jìn)程P的虛擬地址空間大小為50000。(1)進(jìn)程P共有幾頁？(2)根據(jù)圖5-22的位示圖，給出進(jìn)程P的頁表。(3)給定進(jìn)程P的虛擬地址：8192(十進(jìn)制)和0x5D8F(十六進(jìn)制)，根據(jù)(2)的頁表，分別計(jì)算對應(yīng)的物理地址。例子（1）進(jìn)程頁數(shù)=（50000+（4K-1））/4K=13（2）參考圖中空閑塊，順序分配給進(jìn)程（3）a.虛擬地址8192轉(zhuǎn)換成物理地址P=8192/4K=2，w=8192%4K=0。P=2對應(yīng)的塊號b=11物理地址11*4K+0=44K解B.虛擬地址0x5D8F0x5D8F=（0101，1101，1000，1111）2P=（0101，1101，1000，1111）2>>12=(00101)=5W=（0101，1101，1000，1111）2&(12個(gè)”1”)=0xD8Fp=5，b=1919*4K+0xD8FCPU每訪問一條指令或一個(gè)數(shù)據(jù)，都要2次訪問內(nèi)存：1)在MMU重定位過程中，根據(jù)頁號查找內(nèi)存中的頁表得到塊號2)CPU根據(jù)重定位得到的物理地址訪問內(nèi)存中的指令或數(shù)據(jù)3.靜態(tài)分頁的特點(diǎn)及效率的改進(jìn)給定一個(gè)時(shí)間段，MMU在訪問頁對應(yīng)的塊時(shí)，如果有m次在快表中得到塊號，有n次在頁表得到塊號，那么，這個(gè)時(shí)間段MMU的快表命中率h=m/（m+n）*100%TLB(TranslationLookasideBuffers)-快表（1）虛擬存儲器要解決的主要技術(shù)有：理論基礎(chǔ)、調(diào)入策略和置換算法（2）理論基礎(chǔ)--程序的局部性原理在程序運(yùn)行過程的一個(gè)較小時(shí)間范圍內(nèi)，只需要一小部分的程序信息，其他部分暫時(shí)不需要；而且在程序的一次執(zhí)行過程，程序的所有指令和數(shù)據(jù)并沒有相同的訪問概率，有一部分指令和數(shù)據(jù)經(jīng)常被訪問，有一部分指令和數(shù)據(jù)很少被訪問，甚至存在部分指令和數(shù)據(jù)根本沒有被訪問。程序的局部性原理又分為時(shí)間局部性和空間局部性4.虛擬存儲器思想（3）調(diào)入策略請求調(diào)入策略預(yù)調(diào)入策略（4）置換算法（1）擴(kuò)充頁表擴(kuò)充頁表的基本結(jié)構(gòu)主要由頁號、塊號、外存地址、中斷位P、訪問位A、修改位M等組成。修改位M的作用？（2）缺頁中斷及其處理（3）頁面調(diào)度操作系統(tǒng)的缺頁中斷處理過程，要為新讀入的頁分配一個(gè)空閑塊，如果內(nèi)存沒有空閑塊，必須按指定的策略，從內(nèi)存中選擇一頁將其信息淘汰，空出的塊分配給新的頁，把這個(gè)過程稱為頁面調(diào)度。

頁面調(diào)度分為局部頁面調(diào)度和全局頁面調(diào)度。（4）置換算法(PageReplacementAlgorithm)，也稱淘汰算法5.請求分頁的實(shí)現(xiàn)關(guān)鍵置換算法的目標(biāo)是，在內(nèi)存中盡可能保留進(jìn)程運(yùn)行過程中經(jīng)常訪問的頁，以減少缺頁中斷的次數(shù)。置換算法一個(gè)進(jìn)程運(yùn)行過程依次訪問的頁號(也稱進(jìn)程的引用序列)是：0、2、3、1、4、1、2、3、5、2、3、1、4、5、0、3、6、9、8、3、6、7、3、6、9、8、7。假定分配該進(jìn)程4個(gè)塊，按局部頁面調(diào)度，采用FIFO置換算法時(shí)，如何計(jì)算缺頁中斷的次數(shù)？依次淘汰的頁號是哪些？1)先進(jìn)先出算法(FIFO)2)最近最久未使用算法(LRU)3)最近最不常用算法(LFU)4)最近未使用算法(NRU)

5)二次機(jī)會算法(SecondChance)二次機(jī)會算法也稱為時(shí)鐘算法(Clock)

按裝入內(nèi)存的時(shí)間排列，得到內(nèi)存的頁FIFO序列，再按訪問位A和修改位M，內(nèi)存的頁分為如下4類：①A=0，M=0。淘汰這類頁可以減小I/O操作開銷，是置換算法的首選頁；②A=0，M=1。淘汰這類頁需要額外的寫I/O操作，但可以減少抖動現(xiàn)象；③A=1，M=0。淘汰這類頁可以減小I/O操作開銷，但可能產(chǎn)生抖動現(xiàn)象；④A=1，M=1。這類頁是在算法執(zhí)行的最后，不得已的選擇。改進(jìn)型二次機(jī)會算法思想如下：檢查步驟：(1)查找①類頁的，如果找到則淘汰，算法完成；(2)查找②類頁的，如果找到則淘汰，算法完成；在查找過程，置A=0.(3)返回(1)，進(jìn)行第二遍查找，因?yàn)榇藭r(shí)所有頁的A=0，所以，在第二遍查找時(shí)，最壞情況在(2)中必可找到淘汰的頁。設(shè)置剩余空閑塊數(shù)量不足內(nèi)存總塊數(shù)的1/4和1/8兩個(gè)界限。另外，再設(shè)置一個(gè)頁緩沖區(qū)(PageBuffer)，頁緩沖區(qū)用于保存2個(gè)頁緩沖鏈表：

未修改頁鏈表(M0鏈表)和

修改頁鏈表(M1鏈表)在重定位發(fā)現(xiàn)訪問頁的中斷位P=0時(shí)，則先在頁緩沖區(qū)中M0和M1鏈表中查找，如果存在匹配的，則將其移出，并修改頁表相關(guān)信息，如置p=1等，因?yàn)镸0和M1鏈表中的頁還沒有被淘汰，所以不需要讀I/O操作，可以直接從內(nèi)存中得頁的信息。如果在頁緩沖區(qū)中M0和M1鏈表不存在與當(dāng)前要訪問的頁，則產(chǎn)生缺頁中斷。6)頁緩沖算法(PageBuffer)在為新讀入的頁分配內(nèi)存時(shí)，如果沒有空閑塊，則可以從頁緩沖區(qū)中的M0鏈表中移出一個(gè)頁，將其對應(yīng)的塊分配給新的頁；如果M0鏈表為空，則從M1鏈表中移出一個(gè)頁淘汰，分配之前執(zhí)行一個(gè)寫I/O操作，或者一次性地把M1鏈表的所有頁寫入磁盤，全部淘汰，回收作為空閑區(qū)。在產(chǎn)生缺頁中斷為新讀入的頁分配內(nèi)存塊時(shí)，如果剩余空閑塊數(shù)量低于第1界限，比如不足內(nèi)存總塊數(shù)的1/4，則設(shè)置所有內(nèi)存頁的訪問位A=0；如果剩余空閑塊數(shù)量低于第2界限，比如不足內(nèi)存總塊數(shù)的1/8，將內(nèi)存中訪問位A=0的頁淘汰進(jìn)入頁緩沖區(qū)。具體作法是：置這些頁的中斷位P=0，再根據(jù)修改位M，把其中M=0的頁加入頁緩沖區(qū)的M0鏈表，把M=1的頁加入M1修改頁鏈表，這里，只須把能夠標(biāo)識頁的歸屬的進(jìn)程號和頁號等信息加入鏈表中，這些頁并沒有被淘汰。指系統(tǒng)設(shè)置一個(gè)跟蹤程序，檢查每一個(gè)進(jìn)程的工作集，只有在一個(gè)進(jìn)程的工作集在內(nèi)存后，才允許它運(yùn)行。工作集模型可以用于內(nèi)存的分配，假定系統(tǒng)有n個(gè)進(jìn)程，當(dāng)前第i個(gè)進(jìn)程的工作集頁數(shù)為wsi，那么，n個(gè)進(jìn)程需要的內(nèi)存塊數(shù)。D=wsi工作集模型(WorkingSetModel)當(dāng)D大于內(nèi)存塊總數(shù)時(shí)，采用對換技術(shù)，選擇一些進(jìn)程從內(nèi)存調(diào)出到交換區(qū)，以保證內(nèi)存中剩余進(jìn)程的工作集都可以裝入內(nèi)存，這樣可以減少頻繁的缺頁中斷可能產(chǎn)生的抖動現(xiàn)象。缺頁率

如果一個(gè)進(jìn)程的引用序列是p1、p2、…、pn-1、pn，它在執(zhí)行過程中，產(chǎn)生缺頁中斷的次數(shù)為m，那么，該進(jìn)程執(zhí)行這個(gè)引用序列的缺頁率定義為：f=m/n*100%對于一個(gè)進(jìn)程，分配的內(nèi)存塊數(shù)越多，它在運(yùn)行過程產(chǎn)生的缺頁率越小。但是，對于FIFO置換算法，存在個(gè)別進(jìn)程，分配給內(nèi)存塊數(shù)增加，缺頁率反而也增加，這種的反?，F(xiàn)象