第四章存儲(chǔ)管理上-資料下載頁
2024-09-28 12:33本頁面
【導(dǎo)讀】外存管理的基本原理。Windows的高速緩存管理。邏輯地址和物理地址。存儲(chǔ)分配和回收：分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。存儲(chǔ)共享和保護(hù)：。–由應(yīng)用程序控制：覆蓋；–其首地址為0，其余指令中的地址都相對(duì)于首地址來編址。機(jī)器直接尋址的物理地址。它是虛擬存儲(chǔ)的基礎(chǔ)。內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用?？墒褂糜脩魠^(qū)全部空間。最簡單，適用于單用戶、單任務(wù)。造成內(nèi)存浪費(fèi)；程序全部裝入，作系統(tǒng)占用其中一個(gè)分區(qū)。型相同的對(duì)象）。量的中等分區(qū)、少量的大分區(qū)。把內(nèi)存劃分為若干個(gè)固定大小的連續(xù)分區(qū)。若是大于要求，則將該分區(qū)分割。并標(biāo)記為“空閑”。從內(nèi)存低端到高端。
【正文】 現(xiàn)。可用作性能 評(píng)價(jià)的依據(jù) 。 51 2. 最近最久未使用算法 (LRU, Least Recently Used) ? 一個(gè)特殊的棧：把被訪問的頁面移到棧頂，于是棧底 的是最久未使用頁面。 ? 每個(gè)頁面設(shè)立移位寄存器：被訪問時(shí)左邊最高位置 1，定期右移并且最高位補(bǔ) 0，于是 寄存器數(shù)值最小 的是最久未使用頁面。 選擇內(nèi)存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。但由于需要記錄頁面使用時(shí)間的先后關(guān)系，硬件開銷太大。硬件機(jī)構(gòu)如： 52 3. 先進(jìn)先出算法 (FIFO) 選擇 建立最早 的頁面被置換?？梢酝ㄟ^ 鏈表 來表示各頁的建立時(shí)間先后。 性能較差 : 較早調(diào)入的頁往往是經(jīng)常被訪問的頁，這些頁在 FIFO算法下被反復(fù)調(diào)入和調(diào)出。并且可能出現(xiàn)Belady現(xiàn)象。 Belady現(xiàn)象 ：采用 FIFO算法時(shí)，如果對(duì)一個(gè)進(jìn)程 未分配它所要求的全部頁面 ，有時(shí)就會(huì)出現(xiàn)分配的 頁面數(shù)增多 ， 缺頁率反而提高 的異?，F(xiàn)象。 53 Belady現(xiàn)象 進(jìn)程 P有 5頁 , 程序訪問頁的順序?yàn)椋?1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5； 如果在內(nèi)存中分配 3個(gè)頁面，則缺頁情況如下：12次訪問中有缺頁 9次； F I F O 1 2 3 4 1 2 5 1 2 3 4 5頁 0 1 2 3 4 1 2 5 5 5 3 4 4頁 1 1 2 3 4 1 2 2 2 5 3 3頁 2 1 2 3 4 1 1 1 2 5 5缺頁 x x x x x x x √ √ x X √54 如果在內(nèi)存中分配 4個(gè)頁面，則缺頁情況如下：12次訪問中有缺頁 10次； F I F O 1 2 3 4 1 2 5 1 2 3 4 5頁 0 1 2 3 4 4 4 5 1 2 3 4 5頁 1 1 2 3 3 3 4 5 1 2 3 4頁 2 1 2 2 2 3 4 5 1 2 3頁 3 1 1 1 2 3 4 5 1 2缺頁 x x x x √ √ x x x x x x進(jìn)程 P有 5頁 , 程序訪問頁的順序?yàn)椋?1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5； Belady現(xiàn)象 Belady現(xiàn)象的原因 ： FIFO算法的 置換特征 與進(jìn)程 訪問內(nèi)存的動(dòng)態(tài)特征 是 矛盾 的，即被置換的頁面并不是進(jìn)程不會(huì)訪問的。 55 4. 輪轉(zhuǎn)算法 (clock) ? 每頁有一個(gè)使用標(biāo)志位 (use bit)，若該頁被訪問則置user bit=1。 ? 置換時(shí)采用一個(gè)指針，從當(dāng)前指針位置開始按地址先后檢查各頁，尋找 use bit=0的頁面作為被置換頁。 ? 指針經(jīng)過的 user bit=1的頁都修改 user bit=0，最后指針停留在被置換頁的下一個(gè)頁。 也稱 最近未使用算法 (NRU, Not Recently Used)，它是 LRU(最近最久未使用算法 )和 FIFO的折衷。 56 Sta t e of buff er j us t pri or t o a page re pl ac em ent012345678n...Page 9us e = 1Page 19us e = 1Page 1us e = 0Page 45us e = 1Page 191us e = 1Page 556us e = 0Page 13us e = 0Page 67us e = 1Page 33us e = 1Page 222us e = 0next fr am e poi nt erSta t e of buff er j us t af t ert he ne xt page re pl ac em ent012345678n...Page 9us e = 1Page 19us e = 1Page 1us e = 0Page 45us e = 0Page 191us e = 0Page 727us e = 1Page 13us e = 0Page 67us e = 1Page 33us e = 1Page 222us e = 0輪轉(zhuǎn)算法 57 5. 最不常用算法 (LFU, Least Frequently Used) ? 選擇到當(dāng)前時(shí)間為止被 訪問次數(shù)最少 的頁面被置換； ? 每頁設(shè)置訪問計(jì)數(shù)器，每當(dāng)頁面 被訪問時(shí) ，該頁面的 訪問計(jì)數(shù)器加 1； ? 發(fā)生 缺頁中斷時(shí) ，淘汰 計(jì)數(shù)值最小 的頁面，并將所有計(jì)數(shù) 清零 ； 58 6. 頁面緩沖算法 (page buffering) ? 被置換頁面的選擇和處理：用 FIFO算法選擇被置換頁，把被置換的頁面放入兩個(gè)鏈表之一。 – 如果頁面未被修改，就將其歸入到 空閑頁面鏈表 的末尾 – 否則將其歸入到 已修改頁面鏈表 。 它是對(duì) FIFO算法的發(fā)展，通過被置換頁面的緩沖，有機(jī)會(huì)找回剛被置換的頁面； 空閑頁面和已修改頁面，仍停留在內(nèi)存中，如果這些頁面 被再次訪問 ，只需較小開銷，就可以 返還 作為進(jìn)程的內(nèi)存頁。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1