【正文】 外存首址改變位請(qǐng)求頁(yè)式管理中的置換算法置換算法在內(nèi)存中沒(méi)有空閑頁(yè)面時(shí)被調(diào)用。它的目的是選出一個(gè)被淘汰的頁(yè)面。把內(nèi)存和外存統(tǒng)一管理的真正目的是把那些被訪問(wèn)概率非常高的頁(yè)存放在內(nèi)存中。因此，置換算法應(yīng)該置換那些被訪問(wèn)概率最低的頁(yè)，將它們移出內(nèi)存。比較常用的置換算法有：隨機(jī)淘汰算法（在系統(tǒng)設(shè)計(jì)人員無(wú)法確定哪些頁(yè)被訪問(wèn)的概率較低時(shí)，隨機(jī)地選擇某個(gè)用戶的頁(yè)面并將其換出）、輪轉(zhuǎn)法RR（輪轉(zhuǎn)法循回?fù)Q出內(nèi)存可用去內(nèi)一個(gè)可以被換出的頁(yè)，無(wú)論該頁(yè)是剛被換進(jìn)或已換進(jìn)內(nèi)存很長(zhǎng)時(shí)間）和先進(jìn)先出法FIFO（選擇內(nèi)存駐留時(shí)間最長(zhǎng)的一頁(yè)將其淘汰）。最近最久未用頁(yè)面淘汰算法（最近最久未用（LRU）頁(yè)面淘汰算法的著眼點(diǎn)是在要進(jìn)行頁(yè)面淘汰時(shí)，檢查這些淘汰對(duì)象的被訪問(wèn)時(shí)間，總是把最長(zhǎng)時(shí)間未被訪問(wèn)過(guò)的頁(yè)面淘汰出去。這是一種基于程序局部性原理的淘汰算法。也就是說(shuō)，該算法認(rèn)為如果一個(gè)頁(yè)面剛被訪問(wèn)過(guò)，那么不久的將來(lái)被訪問(wèn)的可能性就大；否則被訪問(wèn)的可能性就小。）最近最少用頁(yè)面淘汰算法（最近最少用（LFU）頁(yè)面淘汰算法的著眼點(diǎn)是考慮內(nèi)存塊中頁(yè)面的使用頻率，它認(rèn)為在一段時(shí)間里使用得最多的頁(yè)面，將來(lái)用到的可能性就大。因此，當(dāng)要進(jìn)行頁(yè)面淘汰時(shí)，總是把當(dāng)前使用得最少的頁(yè)面淘汰出去。要實(shí)現(xiàn)LFU頁(yè)面淘汰算法，應(yīng)該為每個(gè)內(nèi)存中的頁(yè)面設(shè)置一個(gè)計(jì)數(shù)器。對(duì)某個(gè)頁(yè)面訪問(wèn)一次，它的計(jì)數(shù)器就加1。經(jīng)過(guò)一個(gè)時(shí)間間隔，把所有計(jì)數(shù)器都清0。產(chǎn)生缺頁(yè)中斷時(shí)，比較每個(gè)頁(yè)面計(jì)數(shù)器的值，把計(jì)數(shù)器取值最小的那個(gè)頁(yè)面淘汰出去。）最優(yōu)頁(yè)面淘汰算法（如果已知一個(gè)作業(yè)的頁(yè)面走向，那么要進(jìn)行頁(yè)面淘汰時(shí)，應(yīng)該把以后不再使用的或在最長(zhǎng)時(shí)間內(nèi)不會(huì)用到的頁(yè)面淘汰出去，這樣所引起的缺頁(yè)中斷次數(shù)肯定最小，這就是所謂的“最優(yōu)（OPT）頁(yè)面淘汰算法”。遺憾的是，OPT的前提是要已知作業(yè)運(yùn)行時(shí)的頁(yè)面走向，這是根本不可能做到的，所以O(shè)PT頁(yè)面淘汰算法沒(méi)有實(shí)用價(jià)值，它只能用來(lái)做為一個(gè)標(biāo)桿（或尺度），與別的淘汰算法進(jìn)行比較。如果在相同頁(yè)面走向的前提下，某個(gè)淘汰算法產(chǎn)生的缺頁(yè)中斷次數(shù)是否接近它。）Belady現(xiàn)象：一般來(lái)說(shuō)，對(duì)于任一作業(yè)或進(jìn)程，如果給它的頁(yè)面數(shù)越接近于它所要求的頁(yè)面數(shù)，則發(fā)生缺頁(yè)的次數(shù)會(huì)越小。但是，使用FIFO算法時(shí)，有時(shí)會(huì)出現(xiàn)分配的頁(yè)面數(shù)增多，缺頁(yè)次數(shù)反而增加的奇怪現(xiàn)象。這種現(xiàn)象稱為Belady現(xiàn)象。存儲(chǔ)保護(hù)頁(yè)式管理可以為內(nèi)存提供兩種方式的保護(hù)。一種是地址越界保護(hù)，另一種是通過(guò)頁(yè)表控制對(duì)內(nèi)存信息的存取操作方式以提供保護(hù)。地址越界保護(hù)可由地址變換機(jī)構(gòu)中的控制寄存器的值——頁(yè)表長(zhǎng)度和所要訪問(wèn)的虛地址相比較來(lái)完成。存取控制保護(hù)的實(shí)現(xiàn)則是在頁(yè)表中增加相應(yīng)的保護(hù)位即可?！镯?yè)式管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)（1）由于它不要求作業(yè)或進(jìn)程的程序段和數(shù)據(jù)在內(nèi)存中連續(xù)存放，從而有效地解決了碎片問(wèn)題；（2）動(dòng)態(tài)頁(yè)式管理提供了內(nèi)存和外存統(tǒng)一管理的虛存實(shí)現(xiàn)方式，使用戶可以利用的存儲(chǔ)空間大大增加。這既提高了主存的利用率，又有利于組織多道程序執(zhí)行。缺點(diǎn)（1）要求有相應(yīng)的硬件支持。例如地址變換機(jī)構(gòu)，缺頁(yè)中斷的產(chǎn)生和選擇淘汰頁(yè)面等都要求有相應(yīng)的硬件支持。這增加了機(jī)器成本。（2）增加了系統(tǒng)開(kāi)銷，例如缺頁(yè)中斷處理。（3）請(qǐng)求調(diào)頁(yè)的算法如選擇不當(dāng)，有可能產(chǎn)生抖動(dòng)現(xiàn)象。（4）雖然消除了碎片，但每個(gè)作業(yè)和進(jìn)程的最后一頁(yè)總有一部分空間得不到利用。如果頁(yè)面較大，則這一部分的損失仍然較大。段式存儲(chǔ)管理的基本思想：把程序按內(nèi)容或過(guò)程（函數(shù)）關(guān)系分成段，每段有自己的名字。一個(gè)用戶作業(yè)或進(jìn)程所包含的段對(duì)應(yīng)于一個(gè)二維線性虛擬空間，也就是一個(gè)二維虛擬存儲(chǔ)器。段式管理程序以段為單位分配內(nèi)存，然后通過(guò)地址映射機(jī)構(gòu)把段式虛擬存儲(chǔ)地址轉(zhuǎn)化為內(nèi)存中的實(shí)際地址。和頁(yè)式管理一樣，段式管理也采用只把那些經(jīng)常訪問(wèn)的段駐留內(nèi)存，而把那些在將來(lái)一段時(shí)間內(nèi)不被訪問(wèn)的段放在外存，待需要時(shí)自動(dòng)調(diào)入內(nèi)存的方法實(shí)現(xiàn)二維虛擬存儲(chǔ)器。 段式與頁(yè)式的比較 段 式 頁(yè) 式 分段由用戶設(shè)計(jì)自己劃分，每段對(duì)應(yīng)的程序模塊，有完整的邏輯意義段面是信息的邏輯單位便于段的共享，執(zhí)行時(shí)按需動(dòng)態(tài)鏈接裝入段長(zhǎng)不等，可動(dòng)態(tài)裝入，有利于新數(shù)據(jù)的增長(zhǎng)二維地址空間：段名、段中地址；段號(hào)、段內(nèi)單元號(hào)管理形式上象頁(yè)式，但概念不同 分頁(yè)用戶看不見(jiàn)，由操作系統(tǒng)為內(nèi)存管理劃分頁(yè)面是信息的物理單位頁(yè)一般不能共享頁(yè)面大小相同，位置不能動(dòng)態(tài)增加一維地址空間往往需要多次缺頁(yè)中斷才能把所需的信息完整地調(diào)入內(nèi)存 段式管理的實(shí)現(xiàn)原理段式管理把一個(gè)進(jìn)程的虛地址空間設(shè)計(jì)成二維結(jié)構(gòu)，即段號(hào)S與段內(nèi)相對(duì)地址W。段號(hào)與段號(hào)之間無(wú)順序關(guān)系，段的長(zhǎng)度是不固定的。每個(gè)段定義一組邏輯上完整的程序或數(shù)據(jù)。例如，一個(gè)進(jìn)程中的程序和數(shù)據(jù)可被劃分為主程序段、子程序段、數(shù)據(jù)段與工作區(qū)段。每個(gè)段是一個(gè)首地址為零、連續(xù)的一維線性空間。段式管理的內(nèi)存分配與釋放段式管理中以段為單位分配內(nèi)存，每段分配一個(gè)連續(xù)的內(nèi)存區(qū)。由于各段長(zhǎng)度不等，所以這些存儲(chǔ)區(qū)的大小不一。而且，同一進(jìn)程所包含的各段之間不要求連續(xù)。段式管理的內(nèi)存分配和釋放是動(dòng)態(tài)進(jìn)行的，與分區(qū)式管理一樣可以采用最先適應(yīng)法、最佳適應(yīng)法、最壞適應(yīng)法等進(jìn)行空閑區(qū)分配。內(nèi)存回收法也同分區(qū)式管理。當(dāng)內(nèi)存中沒(méi)有足夠的空閑區(qū)時(shí)，需要淘汰算法?！锒问焦芾淼牡刂纷儞Q由于段式管理只存放部分信息副本在內(nèi)存，而大部分信息在外存中，這必然引起CPU訪問(wèn)時(shí)發(fā)生所要訪問(wèn)的段不在內(nèi)存現(xiàn)象。那么CPU如何感知到所要訪問(wèn)的段不在內(nèi)存而啟動(dòng)中斷處理程序呢？還有，段式虛擬地址屬于一個(gè)二維的虛擬空間，怎樣變換到一個(gè)一維線性物理地址呢？這些都由段式地址變換機(jī)構(gòu)解決。段式管理程序在進(jìn)行初始內(nèi)存分配之前，首先根據(jù)用戶要求的內(nèi)存大小為一個(gè)作業(yè)或進(jìn)程建立一個(gè)段表，以實(shí)現(xiàn)動(dòng)態(tài)地址變換和缺段中斷處理及存儲(chǔ)保護(hù)等。段式管理的地址變換：一般在內(nèi)存中給出一塊固定的區(qū)域放置段表。當(dāng)某進(jìn)程開(kāi)始執(zhí)行時(shí)，管理程序首先把該進(jìn)程的段表始地址放入段表地址寄存器中。通過(guò)訪問(wèn)段表寄存器，管理程序得到該進(jìn)程的段表始地址從而可開(kāi)始訪問(wèn)段表。然后，由虛擬地址中的段號(hào)s為索引，查段表。若該段在內(nèi)存，則判斷其存取控制方式是否有錯(cuò)。如果存取控制方式正確，則從段表相應(yīng)表目中查出該段在內(nèi)存的起始地址，并將其和段內(nèi)相對(duì)應(yīng)地址w相加，從而得到實(shí)際內(nèi)存地址。若該段不存在，則產(chǎn)生缺段中斷將CPU控制權(quán)交給內(nèi)存分配程序。內(nèi)存分配程序首先檢查空閑區(qū)鏈，以找到足夠長(zhǎng)度的空閑區(qū)來(lái)裝入所需的段。如果內(nèi)存中的可用空閑區(qū)總數(shù)小于所要求的段長(zhǎng)時(shí)，則檢查段表中訪問(wèn)位，以淘汰那些訪問(wèn)概率低的段并將需要段調(diào)入。段的共享與保護(hù)段式存儲(chǔ)管理可以方便地實(shí)現(xiàn)內(nèi)存信息共享和進(jìn)行有效地內(nèi)存保護(hù)。這是因?yàn)槎问前催壿嬕饬x來(lái)劃分的，可以按名訪問(wèn)的緣故。段的共享：在多道環(huán)境下，常常有許多子程序和應(yīng)用程序是被多個(gè)用戶所使用的。特別是在多窗口系統(tǒng)、支持工具等廣泛流行的今天，被共享的程序和數(shù)據(jù)的個(gè)數(shù)和體積都在急劇增加，有時(shí)往往超過(guò)用戶程序長(zhǎng)度的許多倍。內(nèi)存只保留一個(gè)副本，供多個(gè)用戶使用，稱為共享。在多道環(huán)境下，由于進(jìn)程的并發(fā)執(zhí)行，一段程序?yàn)槎鄠€(gè)進(jìn)程共享時(shí)，有可能出現(xiàn)多次同時(shí)重復(fù)執(zhí)行該段程序的情況。這就要求它在執(zhí)行過(guò)程中，該段程序的指令和數(shù)據(jù)不能被修改。共享段進(jìn)行內(nèi)外存交換時(shí)，應(yīng)該設(shè)置一個(gè)共享位。顯然，一個(gè)正在被某進(jìn)程使用或即將被某進(jìn)程使用的共享段是不應(yīng)該調(diào)出內(nèi)存的。段的保護(hù)：（1）地址越界保護(hù)法（2）存取方式控制保護(hù)法★段式管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)提供了內(nèi)外存統(tǒng)一管理的虛存實(shí)現(xiàn)。段長(zhǎng)可根據(jù)需要?jiǎng)討B(tài)增長(zhǎng)。便于對(duì)具有完整邏輯功能的信息段進(jìn)行共享。便于實(shí)現(xiàn)動(dòng)態(tài)鏈接。缺點(diǎn)需要更多的硬件支持。處理碎片比較麻煩。給系統(tǒng)管理帶來(lái)一定的難度和開(kāi)銷。每個(gè)段的長(zhǎng)度受內(nèi)存可用區(qū)大小的限制。選擇不恰當(dāng)?shù)奶蕴惴?，可能?huì)產(chǎn)生抖動(dòng)現(xiàn)象。段頁(yè)式管理的基本思想段式管理為用戶提供了一個(gè)二維的虛地址空間，反映了程序的邏輯結(jié)構(gòu)，有利于段的動(dòng)態(tài)增長(zhǎng)以及共享和內(nèi)存保護(hù)等，這大大方便了用戶。而分頁(yè)管理系統(tǒng)則有效地克服了碎片，提高了存儲(chǔ)器的利用率。從存儲(chǔ)管理的目的來(lái)講，主要是方便用戶的程序設(shè)計(jì)和提高內(nèi)存的利用率。那么把段式管理和頁(yè)式管理結(jié)合起來(lái)讓其互取長(zhǎng)補(bǔ)短不是更好嗎？于是，段頁(yè)式管理方式便被提了出來(lái)。一般僅用于大型機(jī)。段頁(yè)式管理的實(shí)現(xiàn)原理段頁(yè)式管理時(shí)的進(jìn)程的虛擬地址空間中的虛擬地址由三部分組成：即段號(hào)S，頁(yè)號(hào)P和頁(yè)內(nèi)相對(duì)地址D。由于虛擬空間的最小單位是頁(yè)而不是段，從而內(nèi)存可用區(qū)也就被劃分成為若干個(gè)大小相等的頁(yè)面，且每段所擁有的程序和數(shù)據(jù)在內(nèi)存中可以分開(kāi)存放。分段的大小也不再受內(nèi)存可用區(qū)的限制。為了實(shí)現(xiàn)段頁(yè)式管理，系統(tǒng)必須為每個(gè)作業(yè)或進(jìn)程建立一張段表，管理內(nèi)存分配與釋放、缺段處理、存儲(chǔ)保護(hù)和地址變換等。另外，由于一個(gè)段又被劃分成了若干頁(yè)，每個(gè)又必須建立一張頁(yè)表，把段中的虛頁(yè)變換成內(nèi)存中實(shí)際頁(yè)面。顯然，與頁(yè)式管理時(shí)相同，頁(yè)表中也要有實(shí)現(xiàn)缺頁(yè)中斷處理和頁(yè)面保護(hù)等功能的表項(xiàng)。另外，由于在段頁(yè)式管理中，頁(yè)表不再屬于進(jìn)程而屬于段，因此，段表中應(yīng)有頁(yè)表首址和長(zhǎng)度的項(xiàng)?！飫?dòng)態(tài)地址變換過(guò)程在一般使用段頁(yè)式存儲(chǔ)管理的計(jì)算機(jī)系統(tǒng)中，都在內(nèi)存中開(kāi)辟出一塊固定的區(qū)域存放進(jìn)程的段表和頁(yè)表。因此，在段頁(yè)式管理系統(tǒng)中，要對(duì)內(nèi)存中指令或數(shù)據(jù)進(jìn)行一次存取的話，至少需要訪問(wèn)三次以上的內(nèi)存。顯然，CPU的執(zhí)行指令速度大大降低。為了提高地址轉(zhuǎn)換速度，設(shè)置快速聯(lián)想寄存器。它用于存放當(dāng)前最常用的段號(hào)、頁(yè)號(hào)和對(duì)應(yīng)的內(nèi)存頁(yè)面與其它控制用欄目?！锞植啃栽砗投秳?dòng)問(wèn)題程序設(shè)計(jì)常識(shí)告訴我們，一個(gè)作業(yè)往往含有許多循環(huán)和子程序的結(jié)構(gòu)。因此，在作業(yè)運(yùn)行期間，在一小段時(shí)間內(nèi)，訪問(wèn)的地址空間往往只涉及整個(gè)程序的一小部分。在另一小段數(shù)據(jù)內(nèi)，又只涉及另外的一小部分。這種現(xiàn)象稱為局部性特征。反映在頁(yè)面綜跡里，這種特征表現(xiàn)為，在任何一小段時(shí)間里，作業(yè)只集中于訪問(wèn)某幾頁(yè)。所謂工作集，就是一個(gè)作業(yè)在某一小段時(shí)間內(nèi)訪問(wèn)頁(yè)面的集合。如用W(t,△t)表示在(t△t)到t之間所訪問(wèn)的不同的頁(yè)面，那么，這個(gè)W就稱之為作業(yè)在時(shí)間t的工作集。工作集長(zhǎng)度是W (t,△t)中的頁(yè)面數(shù)。工作集長(zhǎng)度越短，局部性越突出。一般來(lái)說(shuō)，一個(gè)作業(yè)的工作集，在運(yùn)行的不同時(shí)刻是不同的，工作集大小亦不相等。而且，工作集大小與△t有關(guān)。 △t大小很難確定，過(guò)小，就不能體現(xiàn)一個(gè)工作集過(guò)渡到另一個(gè)工作集一般是緩慢的這一局部性特征。一個(gè)進(jìn)程執(zhí)行過(guò)程中缺頁(yè)的發(fā)生有兩種可能。一種是并發(fā)進(jìn)程所要求的工作集總和大于內(nèi)存可提供的可用區(qū)。這時(shí)，系統(tǒng)將無(wú)法正常工作，因?yàn)槿狈ψ銐虻目臻g裝入需要的程序和數(shù)據(jù)。另一種可能性是，雖然存儲(chǔ)管理程序?yàn)槊總€(gè)并發(fā)進(jìn)程分配了足夠的工作集，但系統(tǒng)無(wú)法在開(kāi)始執(zhí)行前選擇適當(dāng)?shù)某绦蚝蛿?shù)據(jù)進(jìn)入內(nèi)存。這種情況下，只能依靠執(zhí)行過(guò)程中，當(dāng)CPU發(fā)現(xiàn)所要訪問(wèn)的指令或數(shù)據(jù)不在內(nèi)存時(shí)，由硬件中斷后轉(zhuǎn)入中斷處理程序，將需要的程序和數(shù)據(jù)調(diào)入。系統(tǒng)抖動(dòng)：當(dāng)給進(jìn)程分配的內(nèi)存小于所要求的工作集時(shí)，由于內(nèi)存外存之間交換頻繁，訪問(wèn)外存時(shí)間和輸入輸出處理時(shí)間大大增加，反而造成CPU因等待數(shù)據(jù)空轉(zhuǎn)，使得整個(gè)系統(tǒng)性能大大下降，這就造成了系統(tǒng)抖動(dòng)。解決抖動(dòng)問(wèn)題增加工作集大小；選擇不同的淘汰算法，盡量保持工作集頁(yè)面在內(nèi)存中。實(shí)際上，為了使系統(tǒng)獲得高效率，暫停一個(gè)作業(yè)，當(dāng)其有足夠數(shù)量的頁(yè)面在主存時(shí)才恢復(fù)運(yùn)行；而在調(diào)度一個(gè)新作業(yè)時(shí)，必須有足夠多的空閑存儲(chǔ)塊，才讓其進(jìn)入主存。 1. 若不給自己設(shè)限，則人生中就沒(méi)有限制你發(fā)揮的藩籬。2. 若不是心寬似海，哪有人生風(fēng)平浪靜。在紛雜的塵世里，為自己留下一片純靜的心靈空間，不管是潮起潮落，也不管是陰晴圓缺，你都可以免去浮躁，義無(wú)反顧，勇往直前，輕松自如地走好人生路上的每一步3. 花一些時(shí)間，總會(huì)看清一些事。用一些事情，總會(huì)看清一些人。有時(shí)候覺(jué)得自己像個(gè)神經(jīng)病。既糾結(jié)了自己，又打擾了別人。努力過(guò)后，才知道許多事情，堅(jiān)持堅(jiān)持，就過(guò)來(lái)了。4. 歲月是無(wú)情的，假如你丟給它的是一片空白，它還給你的也是一片空白。歲月是有情的，假如你奉獻(xiàn)給她的是一些色彩，它奉獻(xiàn)給你的也是一些色彩。你必須努力，當(dāng)有一天驀然回首時(shí)，你的回憶里才會(huì)多一些色彩斑斕，少一些蒼白無(wú)力。只有你自己才能把歲月描畫(huà)成一幅難以忘懷的人生畫(huà)卷。學(xué)習(xí)參考