存儲管理

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

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

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

四、可變分區存儲管理

1.基本思想（1）數據結構設計可用表空閑區鏈表請求表struct

FreeNode{ longstart； //分區的起始地址

longlength； //分區的長度

struct

FreeNode*next； //向下指針

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

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

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

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

頁面調度分為局部頁面調度和全局頁面調度。（4）置換算法(PageReplacementAlgorithm)，也稱淘汰算法5.請求分頁的實現關鍵置換算法的目標是，在內存中盡可能保留進程運行過程中經常訪問的頁，以減少缺頁中斷的次數。置換算法一個進程運行過程依次訪問的頁號(也稱進程的引用序列)是：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。假定分配該進程4個塊，按局部頁面調度，采用FIFO置換算法時，如何計算缺頁中斷的次數？依次淘汰的頁號是哪些？1)先進先出算法(FIFO)2)最近最久未使用算法(LRU)3)最近最不常用算法(LFU)4)最近未使用算法(NRU)

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

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

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

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

如果一個進程的引用序列是p1、p2、…、pn-1、pn，它在執行過程中，產生缺頁中斷的次數為m，那么，該進程執行這個引用序列的缺頁率定義為：f=m/n*100%對于一個進程，分配的內存塊數越多，它在運行過程產生的缺頁率越小。但是，對于FIFO置換算法，存在個別進程，分配給內存塊數增加，缺頁率反而也增加，這種的反常現象