存儲(chǔ)器管理3.ppt

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

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

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

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

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

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

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