四、存儲(chǔ)管理
1.引言
現(xiàn)代計(jì)算機(jī)系統(tǒng)中的存儲(chǔ)系統(tǒng)常是多級(jí)存儲(chǔ)體系，至少有主存（內(nèi)存）和輔存（外存）兩級(jí)。有的系統(tǒng)有更多級(jí)。主存是由系統(tǒng)實(shí)際提供的存儲(chǔ)單元（常指字節(jié)）組成的一個(gè)連續(xù)地址空間，處理器可直接存取。輔存是指軟盤(pán)、硬盤(pán)、光盤(pán)和磁帶等一些外部存儲(chǔ)部件，常用來(lái)存放暫不執(zhí)行的程序和數(shù)據(jù)，處理器不能直接訪問(wèn)，需**啟動(dòng)I/O設(shè)備，才能進(jìn)行內(nèi)存、外存交換。其訪問(wèn)速度慢，但價(jià)格便宜，常用作主存的后援設(shè)備。主存大小由系統(tǒng)硬件決定，是實(shí)實(shí)在在的存儲(chǔ)，它的存儲(chǔ)容量受到實(shí)際存儲(chǔ)單元的限制。虛擬存儲(chǔ)（簡(jiǎn)稱(chēng)虛存）不考慮實(shí)際主存的大小和數(shù)據(jù)存取的實(shí)際地址，只考慮相互有關(guān)的數(shù)據(jù)之間的相對(duì)位置，其容量由計(jì)算機(jī)的地址的位數(shù)決定。系統(tǒng)中主存的使用一般分成兩部分，一部分為系統(tǒng)空間，存放操作系統(tǒng)本身及相關(guān)的系統(tǒng)數(shù)據(jù)，另一部分為用戶(hù)空間，存放用戶(hù)的程序和數(shù)據(jù)。
（1）地址重定位用戶(hù)程序需調(diào)入主存運(yùn)行，即從輔存把用戶(hù)已經(jīng)編譯鏈接的目標(biāo)程序（有時(shí)稱(chēng)為可執(zhí)行程序）裝入主存。由于用戶(hù)作業(yè)的存儲(chǔ)空間是運(yùn)行時(shí)確定的，所以程序中的操作地址都采用相對(duì)地址（邏輯地址）的形式。把相對(duì)地址空間的程序轉(zhuǎn)換成在絕對(duì)地址（物理地址）空間上能夠執(zhí)行的過(guò)程稱(chēng)為地址重定位，也稱(chēng)為地址映射或地址映像。地址重定位有兩種:靜態(tài)重定位和動(dòng)態(tài)重定位。靜態(tài)重定位是指在程序裝入時(shí)完成，一般由軟件實(shí)現(xiàn);動(dòng)態(tài)重定位是指在程序執(zhí)行時(shí)實(shí)現(xiàn)地址轉(zhuǎn)換，它通常由一個(gè)基本地址寄存器和一個(gè)加法器組成的動(dòng)態(tài)重定位機(jī)制實(shí)現(xiàn)。
（2）存儲(chǔ)管理的功能早期的單用戶(hù)操作系統(tǒng)，一次只允許一個(gè)用戶(hù)程序駐留，它擁有用戶(hù)地址空間的全部訪問(wèn)權(quán)限，存儲(chǔ)管理的任務(wù)是存儲(chǔ)空間的分配與回收。在多道程序系統(tǒng)，多個(gè)程序同時(shí)駐留內(nèi)存，如何有效地利用主存，如何讓需要較大運(yùn)行空間的作業(yè)運(yùn)行，如何保護(hù)與共享主存等，都是存儲(chǔ)管理應(yīng)解決的問(wèn)題。存儲(chǔ)管理應(yīng)提高存儲(chǔ)資源的利用效率，又方便用戶(hù)使用，存儲(chǔ)管理的任務(wù)應(yīng)具有如下功能:①分配與回收:主存分配方法有兩種:靜態(tài)分配與和動(dòng)態(tài)分配。靜態(tài)分配是指在目標(biāo)模塊裝入主存時(shí)即取得所需空間，直至完成不再變動(dòng);動(dòng)態(tài)分配則允許進(jìn)程在運(yùn)行過(guò)程中繼續(xù)申請(qǐng)主存空間。采用動(dòng)態(tài)分配方法的系統(tǒng)中，常配合使用合并自由區(qū)的方法，使一個(gè)連續(xù)的空區(qū)盡可能地大。②存儲(chǔ)擴(kuò)充:提供虛擬存儲(chǔ)器，使計(jì)算機(jī)系統(tǒng)似乎有一個(gè)比實(shí)際主存儲(chǔ)器容量大的主存空間。需考慮放置策略。③共享與保護(hù):共享指共享在主存中的程序或數(shù)據(jù)，如多個(gè)用戶(hù)共享編輯程序成編譯程序等。由于多道程序共享主存，每個(gè)程序都應(yīng)有它單獨(dú)的主存區(qū)域，各自運(yùn)行，互不干擾。
2.實(shí)存管理
（1）單一連續(xù)分配在單道程序系統(tǒng)中，主存區(qū)域的用戶(hù)空間全部為一個(gè)作業(yè)或進(jìn)程占用，單一連續(xù)分配方法主要用于早期單道批處理系統(tǒng)以及80年代個(gè)人計(jì)算機(jī)系統(tǒng)，單一連續(xù)分配方法主要采用靜態(tài)分配方法，為降低成本和減少?gòu)?fù)雜度，常不對(duì)主存進(jìn)行保護(hù)，會(huì)引起沖突而使系統(tǒng)癱瘓。
（2）固定分區(qū)分配固定分區(qū)分配法是把主存空間固定地劃分為若干個(gè)大小不等的區(qū)域，劃分的原則由系統(tǒng)決定。系統(tǒng)使用分區(qū)表描述分區(qū)情況。
（3）可變分區(qū)分配可變分區(qū)分配方法是將主存空間按用戶(hù)要求動(dòng)態(tài)地劃分若干個(gè)分區(qū)。這樣就消除了固定分區(qū)分配方法中的小作業(yè)占據(jù)大分區(qū)造成的浪費(fèi)（這種浪費(fèi)稱(chēng)為內(nèi)碎片）。可變分區(qū)分配系統(tǒng)中初始時(shí)只有一個(gè)分區(qū)。隨后，分配程序?qū)⑦@個(gè)區(qū)依次分給作業(yè)或進(jìn)程。繼續(xù)考察連續(xù)分配方案:一個(gè)作業(yè)必須占據(jù)相鄰接的存儲(chǔ)單元。在可變分區(qū)分配系統(tǒng)中，并不作出作業(yè)有多長(zhǎng)的的假定（除了它們不能大于計(jì)算機(jī)內(nèi)可利用主存的尺寸之外。當(dāng)作業(yè)到達(dá)時(shí)，如果調(diào)度機(jī)構(gòu)決定它們開(kāi)始運(yùn)行，它們就能獲得必要的存儲(chǔ)區(qū)，一點(diǎn)浪費(fèi)也沒(méi)有———存儲(chǔ)區(qū)的分區(qū)與作業(yè)的長(zhǎng)度相符。）但是，每種存儲(chǔ)組織方案都包含一定程度的浪費(fèi)。在可變分區(qū)分配系統(tǒng)中，主存中的作業(yè)在開(kāi)始裝入和歸還自由區(qū)之前，主存浪費(fèi)并不明顯，這些自由區(qū)可以被其分作業(yè)使用。即使如此，剩余的自由區(qū)域可能變得很小。因此在可變分區(qū)分配系統(tǒng)中，確實(shí)會(huì)出現(xiàn)存儲(chǔ)器浪費(fèi)，這種現(xiàn)象稱(chēng)為外部碎片。①合并自由區(qū)在可變分區(qū)分配系統(tǒng)中，當(dāng)一個(gè)作業(yè)完成時(shí)，能夠檢測(cè)到被釋放的存儲(chǔ)區(qū)是否與其他自由存儲(chǔ)區(qū)域（自由區(qū)）相鄰接。如果與其他自由存儲(chǔ)區(qū)鄰接，可以在自由存儲(chǔ)區(qū)表記錄上新增加一個(gè)自由區(qū)，或新的自由區(qū)與相鄰接的現(xiàn)存自由區(qū)合并的單一自由區(qū)。合并相鄰接的自由區(qū)以形成單個(gè)更大的自由區(qū)的過(guò)程叫做合并。用合并自由區(qū)的方法，我們重新獲得可能連續(xù)的存儲(chǔ)塊。②存儲(chǔ)拼接即使合并了自由區(qū)，經(jīng)常發(fā)現(xiàn)分布在主存各處的破碎的自由區(qū)在主存中占據(jù)了相當(dāng)數(shù)量的空間。有時(shí)，當(dāng)一個(gè)作業(yè)申請(qǐng)一定數(shù)量的主存，而此時(shí)卻沒(méi)有單個(gè)的自由區(qū)大到足夠裝下這個(gè)作業(yè)，雖然自由區(qū)的總和大于新作業(yè)所要的存儲(chǔ)區(qū)。存儲(chǔ)拼接或存儲(chǔ)緊湊也稱(chēng)碎片收集，移動(dòng)存儲(chǔ)器中所有被占用的區(qū)域到主存的某一端。這樣留下單獨(dú)的大的存儲(chǔ)自由區(qū)，取代在可變分區(qū)多道程序設(shè)計(jì)中常見(jiàn)的許多小自由區(qū)。當(dāng)所有可利用的自由存儲(chǔ)區(qū)連續(xù)時(shí)，一個(gè)正等待著的作業(yè)能夠調(diào)入運(yùn)行，因?yàn)樗拇鎯?chǔ)需求能被拼接形成的單個(gè)自由滿(mǎn)足。③存儲(chǔ)分配算法存儲(chǔ)分配算法用來(lái)決定輸入的程序和數(shù)據(jù)放到主存中的什么地方。
常用3種算法是:
適應(yīng)算法:選擇最小的足夠裝入的可利用的自由區(qū)。對(duì)許多人來(lái)說(shuō)，適應(yīng)看起來(lái)是最直觀的，吸引人的算法。
首次適應(yīng)算法:從主存低地址開(kāi)始選擇第一個(gè)足夠裝入的可利用的自由區(qū)。首次適應(yīng)也具有直觀吸引力，此算法可以快速做出分配決定。
最差適應(yīng)算法:最差適應(yīng)說(shuō)的是，總是將一個(gè)程序放入主存中的自由區(qū)。這種方法吸引人的原因很簡(jiǎn)單:在大自由區(qū)中放入程序后，剩下的自由區(qū)經(jīng)常也很大，于是也能裝下一個(gè)較大的新程序。
（4）交換上述3種方法都把用戶(hù)作業(yè)完全地連續(xù)存放在一個(gè)存儲(chǔ)區(qū)區(qū)域中，為了能在較小的主存空間中運(yùn)行較大的作業(yè)，常采用交換技術(shù)。交換技術(shù)是指將作業(yè)不需要或暫時(shí)不需要的部分（進(jìn)程）移到輔存，讓出主存空間以調(diào)入需要的部分，交換到輔存的部分也可以再次被調(diào)入。實(shí)際上這是有輔存作緩沖，讓用戶(hù)程序在較小的存儲(chǔ)空間中，**不斷地?fù)Q出作業(yè)或進(jìn)程而運(yùn)行較大的作業(yè)。
3.虛存組織
虛擬存儲(chǔ)通常涉及存儲(chǔ)空間大于計(jì)算機(jī)系統(tǒng)主存中可利用存儲(chǔ)空間時(shí)的尋址能力問(wèn)題。虛擬存儲(chǔ)系統(tǒng)的特點(diǎn)是運(yùn)行程序訪問(wèn)的地址不是主存中可以獲得的，即運(yùn)行進(jìn)程訪問(wèn)的地址與主存可用的地址相脫離。運(yùn)行進(jìn)程訪問(wèn)的地址稱(chēng)為虛地址，主存中使用的地址稱(chēng)為實(shí)地址。一個(gè)運(yùn)行進(jìn)程可以訪問(wèn)的虛地址范圍稱(chēng)為進(jìn)程的虛地址空間，相應(yīng)的，可使用的實(shí)地址范圍稱(chēng)為實(shí)地址空間。來(lái)
（1）分段存儲(chǔ)組織可變分區(qū)分配方案中，主存中放置的程序常采用首次適應(yīng)、適應(yīng)或最差適應(yīng)算法實(shí)現(xiàn)，但運(yùn)行的程序需連續(xù)存放在一個(gè)分區(qū)中。一個(gè)作業(yè)是由若干個(gè)具有邏輯意義的段（如主程序、子程序、數(shù)據(jù)段等）組成。分段系統(tǒng)中，允許程序（作業(yè)）占據(jù)主存中若干分離的分區(qū)。每個(gè)分區(qū)存儲(chǔ)一個(gè)程序分段。這樣，每個(gè)作業(yè)需要幾對(duì)界限地址，判定訪問(wèn)地址是否越界也困難了。在分段存儲(chǔ)系統(tǒng)中常常利用存儲(chǔ)保護(hù)健實(shí)現(xiàn)存儲(chǔ)保護(hù)。分段系統(tǒng)中虛擬地址是一個(gè)有序?qū)Γǘ翁?hào)，段內(nèi)位移）。系統(tǒng)為每一個(gè)作業(yè)建立一個(gè)段表，其內(nèi)容包括段號(hào)與主存起始地址的對(duì)應(yīng)關(guān)系、段長(zhǎng)和狀態(tài)等。狀態(tài)指出這個(gè)段是否已調(diào)入主存，即主存起始地址指出這個(gè)段，狀態(tài)也指出這個(gè)段的訪問(wèn)權(quán)限。分段系統(tǒng)的動(dòng)態(tài)地址轉(zhuǎn)換是這樣進(jìn)行的:進(jìn)程運(yùn)行時(shí)，其段表的首地址已在基本地址寄存器中，執(zhí)行的指令訪問(wèn)虛存（s，d）（取指令或取操作數(shù)）時(shí)，首先根據(jù)段號(hào)s查段表，若段已經(jīng)調(diào)入主存，則得到該段的主存起始地址，然后與段內(nèi)相對(duì)地址（段內(nèi)偏移量）相加，得到實(shí)地址。如果該段尚未調(diào)入主存，則產(chǎn)生缺段中斷，以裝入所需要的段。
（2）頁(yè)式存儲(chǔ)組織頁(yè)式存儲(chǔ)組織與存儲(chǔ)組織相似。但是，主存被分劃成若干定長(zhǎng)的頁(yè)，頁(yè)式系統(tǒng)中虛地址是一個(gè)有序?qū)Γ?yè)號(hào)，頁(yè)內(nèi)位移）。系統(tǒng)為每一個(gè)進(jìn)程建立一個(gè)頁(yè)表，其內(nèi)容包括進(jìn)程的邏輯頁(yè)號(hào)與物理頁(yè)號(hào)的對(duì)應(yīng)關(guān)系、狀態(tài)等。頁(yè)式系統(tǒng)的動(dòng)態(tài)地址轉(zhuǎn)換是這樣進(jìn)行的，進(jìn)程運(yùn)行時(shí)，其頁(yè)表的首地址已在系統(tǒng)的動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)中的基本地址寄存器中，執(zhí)行的指令訪問(wèn)虛存地址（p，d）時(shí)，首先根據(jù)頁(yè)號(hào)p查頁(yè)表，由狀態(tài)可知，這個(gè)頁(yè)是否已經(jīng)調(diào)入主存。若已調(diào)入主存，則得到該頁(yè)的主存位置，然后，與頁(yè)內(nèi)相對(duì)位移組合，得到實(shí)地址;如果該頁(yè)尚未調(diào)入主存，則產(chǎn)生缺頁(yè)中斷，以裝入所需的頁(yè)。
（3）段頁(yè)式存儲(chǔ)組織段頁(yè)式存儲(chǔ)組織綜合了段式組織與頁(yè)式組織的特點(diǎn)，主存被分劃成定長(zhǎng)的頁(yè)，段頁(yè)式系統(tǒng)中虛地址形式是（段號(hào)、段內(nèi)頁(yè)號(hào)、頁(yè)內(nèi)位移）。系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)段表，為每個(gè)段建立一個(gè)頁(yè)表。
4.虛存管理
實(shí)存管理中曾討論過(guò)調(diào)入、放置（放入分區(qū)）和交換（swapping）等問(wèn)題，虛擬存儲(chǔ)系統(tǒng)同樣存在這些問(wèn)題。
（1）調(diào)入策略這涉及在什么時(shí)候一頁(yè)或一段要從輔存調(diào)入主存，有兩種算法:直到進(jìn)程訪問(wèn)到某頁(yè)或某段時(shí)，才把這個(gè)頁(yè)或段調(diào)入主存，這稱(chēng)為請(qǐng)求調(diào)入方案;先行調(diào)入方案試圖預(yù)測(cè)進(jìn)程將要訪問(wèn)的是哪些頁(yè)或段，則在訪問(wèn)以前先行調(diào)入這些頁(yè)或段到主存。
（2）放置策略這涉及將調(diào)入的頁(yè)或段放在主存的什么地方，頁(yè)式系統(tǒng)可以放置在任一可利用的實(shí)頁(yè)中，分段系統(tǒng)則類(lèi)似于可變分區(qū)分配系統(tǒng)。
（3）置換策略這涉及到進(jìn)程已用完了該進(jìn)程的可用主存空間時(shí)，選擇淘汰哪些頁(yè)或段，騰出空間放置調(diào)入的頁(yè)或段。在請(qǐng)求頁(yè)式存儲(chǔ)系統(tǒng)中，有若干淘汰算法（置換策略）:①（OPT）算法:選擇不再使用或最遠(yuǎn)的將來(lái)才被使用的頁(yè)，這是理想的算法，但難以實(shí)現(xiàn)，常用于淘汰算法的比較。②隨機(jī)（RAND）算法:隨機(jī)地選擇被淘汰的頁(yè)，開(kāi)銷(xiāo)小，但可能選中立即就要訪問(wèn)的頁(yè)。③先進(jìn)先出（FIFO）算法:選擇在主存駐留時(shí)間最長(zhǎng)的頁(yè)，似乎合理，但可能淘汰立即要使用的頁(yè)。另外，使用FIFO算法時(shí)，在未給予進(jìn)程分配足夠的頁(yè)面數(shù)時(shí)，有時(shí)會(huì)出現(xiàn)給予進(jìn)程的頁(yè)面數(shù)增多，缺頁(yè)次數(shù)反而增加的異?，F(xiàn)象。④最近最少使用（LRU）算法:選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)使用得最少的頁(yè)，這個(gè)算法的主要出發(fā)點(diǎn)是，如果某個(gè)頁(yè)被訪問(wèn)了，則它可能馬上就要被訪問(wèn);反之，如果某個(gè)頁(yè)長(zhǎng)時(shí)間未被訪問(wèn)，則它在最近一段時(shí)間也不會(huì)被訪問(wèn)。存儲(chǔ)管理策略的基礎(chǔ)是局部性原理———進(jìn)程往往會(huì)不均勻地高度局部化地訪問(wèn)主存。局部性表現(xiàn)為時(shí)間局部性和空間局部性?xún)深?lèi):時(shí)間局部性是指最近被訪問(wèn)的存儲(chǔ)位置，很可能不久的將來(lái)還要訪問(wèn)，如循環(huán)、棧等;空間局部性是指存儲(chǔ)訪問(wèn)有成組的傾向:當(dāng)訪問(wèn)某個(gè)位置后，很可能也要訪問(wèn)其附近的位置，如訪問(wèn)數(shù)組，代碼順序執(zhí)行等。存儲(chǔ)訪問(wèn)局部性最有意義的結(jié)果是，只要進(jìn)程所需要的頁(yè)面子集駐留在主存中，進(jìn)程就可以有效地運(yùn)行，根據(jù)局部性訪問(wèn)特性，Denning闡述了程序性能的工作集理論。簡(jiǎn)言之，工作集是進(jìn)程活躍地訪問(wèn)的頁(yè)面的集合。工作集理論指出，為使進(jìn)程有效地運(yùn)行。它的頁(yè)面工作集應(yīng)駐留在主存中。否則，由于進(jìn)程頻繁地從輔存請(qǐng)求頁(yè)面，而出現(xiàn)稱(chēng)為“顛簸”（又稱(chēng)抖動(dòng)）的過(guò)度的頁(yè)面調(diào)度活動(dòng)。此時(shí)，處理頁(yè)面調(diào)度上的時(shí)間超過(guò)了程序的執(zhí)行時(shí)間。顯然，此時(shí)CPU的有效利用率會(huì)急速下降。當(dāng)一個(gè)進(jìn)程陷入顛簸狀態(tài)時(shí)，有的系統(tǒng)將采用全局頁(yè)面調(diào)度方法以試圖消除顛簸現(xiàn)象，即將其他進(jìn)程擁有的主存頁(yè)面調(diào)出主存供這個(gè)進(jìn)程使用