存儲器管理3.ppt

1、存 儲 器 管 理,虛擬存儲器部分(三),上,下,關(guān)閉,音樂欣賞,課前復(fù)習(xí),上,下,關(guān)閉,音樂欣賞,本講義要點,Belady現(xiàn)象,抖動現(xiàn)象,工作集,上,下,關(guān)閉,音樂欣賞,Belady現(xiàn)象,一.概念引入 一般來講，對于任何一個程序或進(jìn)程，如果在內(nèi)存中給它分配的“頁框”數(shù)越多，那么，系統(tǒng)發(fā)生缺頁的次數(shù)就應(yīng)該越少。這個推論在極限情況下是成立的。因為如果給一個進(jìn)程分配了它所要求的全部頁框，那么系統(tǒng)就不會發(fā)生缺頁現(xiàn)象。但是在使用FIFO置換算法時，在未給進(jìn)程或程序分配足它所要求的全部頁框時，有時會出現(xiàn)分配的頁框（物理頁面）數(shù)越多，系統(tǒng)缺頁次數(shù)反而增加的奇怪現(xiàn)象。我們稱之為Belady現(xiàn)象。,二.舉例說

2、明 設(shè)一個進(jìn)程一共有8頁,且已經(jīng)在內(nèi)存中分配了3個頁框(物理頁面),程序訪問內(nèi)存的順序(訪問串)為7-0-1-2-0-3-0-4-2-3-0-3-2-1-2-0-1。請用FIFO算法作出其置換圖。,分配三個頁框時的情況（缺頁次數(shù)=12）,上,下,關(guān)閉,音樂欣賞,0,0,0,1,1,1,1,4,4,4,4,0,0,0,0,2,3,3,3,3,7,7,7,7,1,0,2,1,2,3,0,3,2,4,0,3,0,2,1,0,7,為該進(jìn)程分配4個頁框（物理頁面）時的置換情況如下：,1,1,2,2,2,2,分配四個頁框時的情況（缺頁次數(shù)=9）,*：這是一個在正常情況下的例子隨著頁框數(shù)的增加，其缺頁次數(shù)也

3、降低了。下面我們介紹一個異常情況時的例子。,Belady現(xiàn)象舉例,上,下,關(guān)閉,音樂欣賞,設(shè)一個進(jìn)程一共有5頁, 程序訪問內(nèi)存的順序(訪問串)為1-2-3-4-1-2-5-1-2-3-4-5。其擁有3個頁框和4個頁框且用FIFO算法置換時的置換情況分別如下：,分配三個頁框時的情況（缺頁次數(shù)=9）,分配四個頁框時的情況（缺頁次數(shù)=10）,為什么,上,下,關(guān)閉,音樂欣賞,FIFO置換算法產(chǎn)生 Belady現(xiàn)象的原因是在于它根本沒有考慮程序執(zhí)行時的動態(tài)特征。,上,下,關(guān)閉,音樂欣賞,工作集,缺頁率與進(jìn)程所分得的頁框數(shù)存在密切關(guān)系。如下圖所示：該圖給出了缺頁率與進(jìn)程分得頁框數(shù) n 之間的關(guān)系曲線。由圖

4、可知，缺頁率隨著頁框數(shù)的減少而單調(diào)遞增，并在所分到的頁框數(shù)較少處出現(xiàn)一個拐點。在拐點下限以左時，每增加一個頁框后都可以明顯的減少缺頁率；而過了拐點，在下限以右時，每增加一個頁框后，對缺頁率的改善不明顯。通常，為進(jìn)程分配的內(nèi)存中的頁框數(shù)應(yīng)取在該曲線的拐點左右，如果內(nèi)存空間較充足，所取的頁框數(shù)目還可以略大些。,缺 頁 率,0,上限,下限,頁框數(shù) n,拐 點,為什么,上,下,關(guān)閉,音樂欣賞,之所以存在這樣的曲線，是因為缺頁率的大小與進(jìn)程運行時的所謂工作集有關(guān)。這是因為，程序在運行時對頁的訪問是不均勻的，即是在某段時間內(nèi)的訪問僅僅局限于有限的若干個頁。如果能夠預(yù)知程序在某段時間內(nèi)要訪問哪些頁，并把它們

5、提前調(diào)入內(nèi)存，將會大大的提高內(nèi)存的命中率，減小缺頁率，從而減少置換工作，提高CPU的利用率。,哪什么又叫“工作集”呢？,上,下,關(guān)閉,音樂欣賞,所謂“工作集”是指， 在某段時間間隔內(nèi)， 進(jìn)程實際要訪問的頁 面的集合。,上,下,關(guān)閉,音樂欣賞,雖然程序只需要少量的幾頁在內(nèi)存中就可以運行，但是為了使程序能有效的運行，較少地產(chǎn)生缺頁，就必須把程序的工作集全部放在內(nèi)存中。然而，我們無法預(yù)知程序在不同的時刻將訪問哪些頁面，因而只能利用程序過去某段時間內(nèi)的行為，作為程序在將來某段時間內(nèi)的近似。,某進(jìn)程在時間 t 的工作集表示為 W(t, )，其中稱為工作集“窗口尺寸”。 正確的選擇工作集窗口的大小，對存儲

6、器 的有效利用和系統(tǒng)吞吐量的提高，都將產(chǎn)生重要的影響。 如果選擇過大以致能將一個進(jìn)程的所有頁都裝入內(nèi)存， 這樣雖不會產(chǎn)生缺頁，但存儲器的利用將不充分，從而失去虛擬存 儲器的意義。但是，如果選擇的過小，為此就不能將進(jìn)程所需的 工作集全部裝入內(nèi)存，而將導(dǎo)致系統(tǒng)頻繁的發(fā)生缺頁中斷，因而 反倒降低了系統(tǒng)的吞吐量。所以工作集應(yīng)選擇適中。,上,下,關(guān)閉,音樂欣賞,抖動現(xiàn)象,一.概念引入 在進(jìn)行頁面置換的時候，當(dāng)一頁或多頁被頻繁的換進(jìn)和換出時，使進(jìn)程的絕大部分的時間都用在這些無謂的換進(jìn)/換出工作上，而系統(tǒng)幾乎不能完成任何有效的工作。這種現(xiàn)象被稱著“抖動”現(xiàn)象，此時的進(jìn)程處于抖動狀態(tài)。,二.抖動的預(yù)防 為了保

7、證系統(tǒng)可靠和提高其吞吐量，就必須防止發(fā)生抖動。其方法很多，但都是通過調(diào)節(jié)多道程序度來實現(xiàn)的。 1.采取足部置換策略 當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁后,僅在自己的內(nèi)存空間范圍內(nèi)置換頁面,同時又不允許其它進(jìn)程獲得新的頁框。這樣，即使有某個進(jìn)程發(fā)生“抖動”，也不會導(dǎo)致其它進(jìn)程發(fā)生抖動，從而使抖動局限于一個較小的范圍內(nèi)。,上,下,關(guān)閉,音樂欣賞,3.L=S準(zhǔn)則 當(dāng)進(jìn)程產(chǎn)生缺頁的平均時間（L）=系統(tǒng)處理進(jìn)程缺頁的平均時間（S）時，此時CPU的利用率最好。 4.掛起若干進(jìn)程 當(dāng)多道程序度偏高是時，為了防止發(fā)生“抖動”，可以將一些進(jìn)程掛起，以便釋放出內(nèi)存空間來滿足將要發(fā)生抖動的進(jìn)程。被掛起的進(jìn)程有以下三種情況： （1）通常都是優(yōu)先權(quán)最低或較低的； （2）當(dāng)內(nèi)存非常擁擠時，也可以掛起一個并不很重要但容量卻很大的進(jìn)程，以便一次性釋放較大的內(nèi)存空間； （3）將具有最多剩余執(zhí)行時間的進(jìn)程掛起。,上,下,關(guān)閉,音樂欣賞,2.在CPU調(diào)度程序中引入工作集算法 調(diào)度程序從外存上調(diào)入一個新作業(yè)到內(nèi)存，來提高多道程序度，從而改善CPU的利用率。在引入工作集算法后，調(diào)