操作系統(tǒng)原理第5章-存儲管理

第5章存儲管理存儲器是計算機的記憶部件，計算機系統(tǒng)的主要用途是執(zhí)行程序，在執(zhí)行程序時，這些程序及其所訪問的數(shù)據(jù)必須在內(nèi)存里。由于內(nèi)存通常太小不足以永久地容納所有數(shù)據(jù)和程序，因此計算機系統(tǒng)必須提供外存（如硬盤）以擴充內(nèi)存的技術(shù)。內(nèi)存是一個關(guān)鍵性的資源。能否合理而有效地使用它，在很大程度上反映了操作系統(tǒng)的性能，并直接影響整個計算機系統(tǒng)作用的發(fā)揮。5.1.1存儲器的層次三級存儲器結(jié)構(gòu)高速緩存（cache）—內(nèi)存（primarystorage）—外存（secondarystorage）5.1.2存儲管理的功能1.內(nèi)存分配和回收內(nèi)存的利用率與內(nèi)存分配的技術(shù)、方式和策略有直接關(guān)系。2.內(nèi)存保護內(nèi)存保護就是確保多個進程都在各自分配到內(nèi)存區(qū)域內(nèi)操作，互不干擾，防止一個進程破壞其他進程的信息。3.內(nèi)存擴充內(nèi)存“擴充”包含了存儲器利用的提高和擴充兩方面的內(nèi)容。為用戶提供比內(nèi)存物理空間大得多的地址空間。比較典型的內(nèi)存擴充是虛擬存儲器。4.地址映射地址映射就是將進程的邏輯地址變換為內(nèi)存中的物理地址。我們需要實現(xiàn)從邏輯地址到物理地址的變換，即實現(xiàn)從虛地址到實地址的變換。這種變換就是重定位。5.1.3存儲空間與地址空間①邏輯地址邏輯地址就是指令在程序中的地址，源程序經(jīng)編譯（或解釋）后編排的地址。邏輯地址也叫相對地址或虛擬地址。②邏輯地址空間邏輯地址空間就是某程序的邏輯地址的集合，邏輯地址空間可簡稱為地址空間。③物理地址物理地址就是進程中的指令和數(shù)據(jù)在內(nèi)存中的地址，指令和數(shù)據(jù)存放在內(nèi)存中的內(nèi)存單元編號。物理地址也叫絕對地址或?qū)嵉刂?。④物理地址空間物理地址空間是指進程在內(nèi)存中一系列存儲信息的物理單元的集合。物理地址空間也叫存儲空間，存儲空間與地址空間既相互關(guān)聯(lián)，又相互獨立，是內(nèi)存管理的核心概念。5.1.4進程的裝入方式⑴直接裝入方式程序員編程或編譯器編譯時就知道進程將在內(nèi)存中的駐留地址，那么就可以生成絕對代碼。此時進程可以采用直接裝入方式。如MS-DOS的命令文件（.COM）就是在編譯時捆綁成絕對代碼的。⑵重定位裝入方式如果在編譯時編譯器不知道進程將駐留在內(nèi)存何處，那么編譯器就必須生成可重定位代碼。對這種情況，最后綁定會延遲到加載時才進行。此時進程可以采用重定位裝入方式，重定位可分為靜態(tài)重定位和動態(tài)重定位。55.1.5重定位①靜態(tài)重定位裝入程序在裝入進程時，一次性綁定（binding）進程在內(nèi)存中的物理地址，即物理地址＝基址+邏輯地址。優(yōu)點：簡單，無需增加硬件就可以實現(xiàn)。缺點：要求連續(xù)的內(nèi)存存儲空間，程序裝入內(nèi)存后就不可移動，且難以做到程序和數(shù)據(jù)的共享，內(nèi)存的利用率差②動態(tài)重定位進程在裝入內(nèi)存時不進行地址綁定，在指令執(zhí)行期間CPU每次訪問內(nèi)存時進行地址重定位，這種重定位方法需要硬件的支持，系統(tǒng)中需設置一個地址變換機構(gòu)。

優(yōu)點：內(nèi)存空間的占有量可以改變，容易實現(xiàn)共享。缺點：需硬件支持，成本增加。動態(tài)重定位是一種允許進程在執(zhí)行過程中在內(nèi)存中移動的技術(shù)，必須獲得硬件地址變換機構(gòu)的支持。在多任務操作系統(tǒng)中，多個進程在內(nèi)存中并發(fā)執(zhí)行，進程的創(chuàng)建與撤消，多個進程之間頻繁的上下文切換，其內(nèi)存分配呈現(xiàn)動態(tài)性和隨機性。靜態(tài)重定位僅適應于連續(xù)分配，不能滿足多任務操作系統(tǒng)動態(tài)性和隨機性的要求，因此多任務操作系統(tǒng)存儲管理適合采用離散分配，必須采用動態(tài)重定位。5.2分區(qū)式存儲管理內(nèi)存分配方式可分為連續(xù)分配方式和離散分配方式。分區(qū)式存儲管理是連續(xù)分配方式，為一個進程分配一個連續(xù)的存儲空間。分區(qū)式存儲管理支持多道程序系統(tǒng)和分時系統(tǒng)，但內(nèi)存分配存在不可利用的內(nèi)存空間，即碎片問題。碎片一般可分為內(nèi)碎片和外碎片。5.2.1單一連續(xù)分配單一連續(xù)分配內(nèi)存分配優(yōu)缺點如下：優(yōu)點：實現(xiàn)簡單，不需要復雜的軟、硬件支持。缺點：存在內(nèi)碎片問題。資源利用率低，由于存儲資源利用率低而造成其他資源利用率低。5.2.2固定分區(qū)分配

固定分區(qū)(fixedpartitioning)也叫靜態(tài)分區(qū)，固定分區(qū)存儲管理是實現(xiàn)多道程序設計和分時系統(tǒng)的簡單存儲管理技術(shù)。如圖所示，固定分區(qū)的優(yōu)缺點優(yōu)點：易于實現(xiàn)，開銷小，內(nèi)存分配和回收算法簡單，支持多任務。缺點：存在內(nèi)碎片問題，造成內(nèi)存的浪費。分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的進程數(shù)目。5.2.3動態(tài)分區(qū)動態(tài)分區(qū)分配可謂“量體裁衣”。與固定分區(qū)相比較，動態(tài)分區(qū)的優(yōu)點是沒有內(nèi)碎片。但卻引入了另一種碎片，即外碎片。1．空閑分區(qū)鏈表2．空閑分區(qū)鏈表每個空閑分區(qū)的前后兩個單元，放置空閑分區(qū)的說明信息和指針。如圖所示，系統(tǒng)設立一個鏈首指針Free，指向第一個空閑分區(qū)?？臻e分區(qū)排列需按照一定的規(guī)律（如按大小、按地址），分配進程可以依照空閑分區(qū)鏈表，來查找適合的空閑分區(qū)進行分配。2.動態(tài)分區(qū)的分配算法⑴首次適應算法首次適應算法的空閑鏈是對空閑分區(qū)按照地址從低到高的順序排列起來。為進程選擇分區(qū)時總是按地址從低到高搜索，只要找到可以容納該進程的空閑區(qū)，就把該空閑區(qū)切割出進程大小，分配給該進程，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈首直至鏈尾都不能找到一個能滿足要求的分區(qū)，則此次內(nèi)存分配失敗返回。其缺點是低址部分不斷被劃分，會留下許多難以利用的、很小的空閑分區(qū)（即碎片），而每次查找又都是從低址部分開始，這無疑會增加查找可用空閑分區(qū)鏈時的開銷。⑵循環(huán)首次適應算法循環(huán)首次適應算法的空閑鏈是對空閑分區(qū)按照地址從低到高的順序排列起來（同上）。每次分區(qū)時，總是從上次查找結(jié)束的地方開始，只要找到一個足夠大的空閑區(qū)，就把該空閑區(qū)切割出進程大小，分配給該進程，余下的空閑分區(qū)仍留在空閑鏈中。該算法能使內(nèi)存中的空閑分區(qū)分布得更均勻，從而減少了查找空閑分區(qū)時的開銷，但這樣會缺乏大的空閑分區(qū)。⑶最佳適應算法最佳適應算法的空閑鏈是按空閑區(qū)從小到大順序排列。為進程選擇分區(qū)時總是尋找其大小最接近進程所要求的存儲區(qū)域。所謂“最佳”是指每次為進程分配內(nèi)存時，總是把能滿足要求、又是最小的空閑分區(qū)分配給進程，避免“大材小用”。因為每次分配后所切割下來的剩余部分總是最小的，這樣將加速碎片的形成。⑷最差適應算法最差適應算法的空閑鏈是按空閑區(qū)從大到小順序排列。與最佳適應法相反，它為進程選擇存儲區(qū)時，總是尋找最大的空白區(qū)。最差適應算法可以延緩小空閑區(qū)的形成，但是無法保留大空閑區(qū)。這給以后到達尺寸大的進程分配內(nèi)存空間帶來了困難。內(nèi)存緊縮(compaction)技術(shù)3．動態(tài)分區(qū)內(nèi)存的分配與回收。規(guī)定不再切割尺寸大小為size。從空閑分區(qū)鏈表中找到所需大小的分區(qū)。設進程請求的尺寸大小為u.size，空閑分區(qū)的大小可表示為m.size。若m.size-u.size≤size，說明多余部分太小，可不再切割，將整個分區(qū)分配給進程；內(nèi)存回收情況一：前鄰空閑區(qū)，回收區(qū)與插入點的前一個空閑區(qū)F1相鄰接。此時應將回收區(qū)與插入點的前一分區(qū)合并，不必為回收分區(qū)分配新表項，而只需修改其前一分區(qū)Fl的大小，大小為兩者之和。情況二：前后鄰空閑區(qū)，回收區(qū)同時與插入點的前空閑區(qū)F1和后空閑區(qū)F2兩個空閑區(qū)鄰接。此時將三個分區(qū)合并，使用前空閑區(qū)F1的首址作為新空閑區(qū)的首址，大小為三者之和，取消F2的表項。情況三：后鄰空閑區(qū)，回收分區(qū)與插入點的后一空閑區(qū)F2相鄰接。此時也可將兩分區(qū)合并，形成新的空閑分區(qū)，用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和。情況四：前后不鄰接空閑區(qū)，回收區(qū)不與空閑區(qū)鄰接。這時應為回收區(qū)單獨建立一新表項，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當位置。5.2.4伙伴系統(tǒng)其實現(xiàn)原理如下：一個伙伴系統(tǒng)內(nèi)存的用戶可用空間為2U。進程申請存儲空間時，系統(tǒng)總是為其分配大小為2I的一個空閑分區(qū)。其中S≤I≤U，2S是系統(tǒng)允許的最小分區(qū)尺寸。在實際操作系統(tǒng)中，最小分區(qū)尺寸一般為212。如果進程申請的存儲空間大小為K，且2I-1<K≤2I，則將整個2I大小的分區(qū)分配給該進程；否則，該分區(qū)被分割成兩個大小相等的伙伴分區(qū)，大小為2I-1；再判斷K是否滿足條件：2I-2<K≤2I-1，若滿足條件，則將兩個伙伴中的任何一個分配給該進程。否則，將其中一個伙伴又分成兩個大小相等的伙伴分區(qū)；此過程一直繼續(xù)進行，直到產(chǎn)生的分區(qū)滿足條件I-J≥S并2I-J-1<K≤2I-J，將2I-J大小的分區(qū)分配給該進程；當I-J-1<S時，系統(tǒng)不再分割成兩個大小相等的伙伴分區(qū)，將2S大小的分區(qū)分配給該進程。當進程執(zhí)行完畢，釋放一個尺寸為2I的分區(qū)時，系統(tǒng)用下面的算法回收該分區(qū)。①如果被回收空閑分區(qū)沒有空閑伙伴分區(qū)，那么保留該分區(qū)為一個獨立的空閑分區(qū)，否則執(zhí)行②；②合并回收分區(qū)及其伙伴分區(qū)，從而得到一個尺寸（2I+1）更大的回收空閑分區(qū)，轉(zhuǎn)移到①；

一個伙伴系統(tǒng)內(nèi)存分配與回收的例子

伙伴系統(tǒng)克服了固定分區(qū)和動態(tài)分區(qū)存儲管理技術(shù)的缺陷。但是伙伴系統(tǒng)存在一個問題，即內(nèi)存空間需要不斷地進行分裂和合并，頻繁的伙伴分區(qū)合并操作會浪費很多時間。一種直接的解決方法是延緩合并，不是在伙伴回收時進行合并，而是在必要時才進行伙伴合并。225.2.5整理內(nèi)存碎片5.2.6覆蓋技術(shù)5.2.7交換技術(shù)覆蓋技術(shù)與交換技術(shù)是在多道程序環(huán)境下擴充內(nèi)存的兩種方法。23在現(xiàn)代操作系統(tǒng)中，更多地采用分頁或分段存儲管理技術(shù)，以及虛擬存儲技術(shù)，但伙伴系統(tǒng)在一些操作系統(tǒng)中仍然是一種有效的存儲管理方法。隨著內(nèi)存技術(shù)的發(fā)展，內(nèi)存容量的不斷擴大，伙伴系統(tǒng)作為存儲分配的一種合理有效技術(shù)將得到進一步發(fā)展，比較典型的技術(shù)是Linux系統(tǒng)采用的伙伴堆算法。5.3分頁存儲管理方式分頁存儲管理允許進程的存儲空間是離散的，把進程邏輯地址空間與實際存儲空間分離，增加存儲管理的靈活性。將一個進程分散存儲到許多不連續(xù)的空間，就可以避免內(nèi)存碎片。離散分配方式分為以下三種：分頁存儲管理分段存儲管理段頁式存儲管理5.3.1頁與頁幀在分頁存儲管理方式中，將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁(page)或頁面。每頁從0開始依次編號稱為頁號(pagenumber)。內(nèi)存空間也分成與頁相同大小的若干個存儲塊，稱為頁幀(pageframe)或物理塊。每幀從0開始依次編號稱為幀號或塊號。頁和幀為分頁存儲管理進行分配內(nèi)存的基本單位。進程的最后一頁經(jīng)常裝不滿一塊，而形成不可利用的碎片，稱為頁內(nèi)碎片。通常頁的大小是2的冪，即在512B—8KB之間。隨著內(nèi)存技術(shù)的發(fā)展，容量的不斷增大，頁的大小也應該適度增大為佳。5.3.2分頁存儲管理的實現(xiàn)

1．分頁存儲管理的數(shù)據(jù)結(jié)構(gòu)①頁表：如圖所示，為了便于找到進程的每個頁號對應的內(nèi)存幀號，系統(tǒng)為每個進程建立一張頁面映象表，簡稱頁表。頁表用于完成進程地址空間的邏輯頁號到存儲空間物理幀號的映射。系統(tǒng)為每一個進程建立一個頁表，一個頁號對應一個幀號。頁表的表項也稱為頁描述子，一般包括：頁號、幀號、權(quán)限等。②物理頁幀表：整個系統(tǒng)有一個物理頁幀表，描述物理內(nèi)存空間的分配使用狀況，其數(shù)據(jù)結(jié)構(gòu)可采用位示圖和空閑頁幀鏈表。2．分頁存儲管理的實現(xiàn)分頁存儲管理可謂“見縫插針”，解決了外碎片問題，具體實現(xiàn)技術(shù)如下：①邏輯地址空間分頁，將用戶進程的邏輯地址空間分成若干大小相等的頁。②內(nèi)存存儲空間分幀，將內(nèi)存的用戶區(qū)劃分成與頁大小相同的頁幀。③內(nèi)存分配原則，以頁幀為單位來分配內(nèi)存，將進程若干個邏輯上連續(xù)的頁面裝入若干個離散的頁幀中，由頁表提供進程的頁號到存儲空間幀號的映射。④在分頁存儲管理中，調(diào)度進程運行時，必須將進程的所有頁面一次調(diào)入內(nèi)存，若內(nèi)存中沒有足夠的物理幀，則進程等待。3．分頁存儲管理的地址結(jié)構(gòu)如果邏輯地址空間為2m，頁大小為2n，那么邏輯地址的高m-n位表示頁號p，而低n位表示偏移量d(offset)。如圖4-17所示，邏輯地址結(jié)構(gòu)為頁號p|偏移量d，物理地址結(jié)構(gòu)為幀號f|偏移量d。若給定一個邏輯地址空間中的地址為A，頁的大小為L，則頁號p和偏移量d可按下式求得:p=A/Ld=A%L例如，其系統(tǒng)的頁面大小為1KB，設A=2180，則由上式可以求得p＝2，d＝132。5.3.3分頁存儲管理的地址變換機構(gòu)

頁表寄存器存放CPU正在處理的進程所對應頁表的起始地址和該進程長度（總頁數(shù)）。在分頁存儲管理系統(tǒng)中，其地址變換過程如圖所示，，指令所給出的邏輯地址：頁號p|偏移量d。CPU中的內(nèi)存管理單元(MMU)按頁號通過查找頁表得幀號，形成物理地址：幀號f|偏移量d。CPU每次訪問一個在內(nèi)存中的操作數(shù)，需要兩次訪問內(nèi)存。例如，某分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，每頁4KB。假定某用戶進程一共6頁，已經(jīng)全部換入內(nèi)存，且第0、1、2、3、4、5頁依次存放在內(nèi)存幀的幀號為3、6、9、11、8、12中。設邏輯地址為5A5CH，如圖所示其對應的物理地址求解如下：

該分頁系統(tǒng)的邏輯地址結(jié)構(gòu)為:頁號p（4位）|偏移量d（12位），邏輯地址為5A5CH的頁號p=5，該頁存放在12號內(nèi)存幀中。物理地址結(jié)構(gòu)為：幀號f|偏移量d，求得對應的物理地址為CA5CH。31具有快表的地址變換過程如下：

①CPU給出有效地址后，由地址變換機構(gòu)自動將頁號送入快表，并將此頁號與快表中的所有關(guān)鍵字（頁號）進行比較，而且這種比較是同時進行的。若其中有與此頁號相匹配的關(guān)鍵字，表示要訪問頁描述子在快表中。于是可直接讀出該頁所對應的幀號，則快速形成物理地址。這樣就無需訪問內(nèi)存中的頁表

②如果快表中沒有記錄，即TLB失效，從頁表中查找所需的頁描述子中的幀號，形成物理地址，同時更新快表，把該頁描述子及相鄰的頁描述子寫入快表。

頁號在快表（TLB）中被查找到的百分比稱為命中率（h）。

5.3.4頁表結(jié)構(gòu)

1.多級頁表2.哈希頁表3.反置頁表5.3.5頁的保護和共享的問題5.4分段存儲管理方式5.4.1分段存儲管理方式的引入一個程序由多個程序段和數(shù)據(jù)段組成，程序通過分段劃分為多個模塊，如代碼段、數(shù)據(jù)段、共享段。分段(segment)就是支持這種用戶觀點的內(nèi)存管理方案。每個程序都有由一組段組成。每個段都有名稱和長度。邏輯地址空間是二維的地址空間。邏輯地址由兩個元素組成：段號s|段內(nèi)偏移d。5.4.2分段存儲管理系統(tǒng)的基本原理進程的地址空間被劃分成若干段，每個段定義一個完整邏輯意義的信息，段號從0開始編號。進程加載時，操作系統(tǒng)為所有段分配其所需內(nèi)存，段與段之間不必連續(xù)，物理內(nèi)存的管理采用分區(qū)式存儲管理方法。分段存儲管理具體如下：①邏輯分段段是一組邏輯信息的集合。將一個進程按照其不同的功能，分成若干個相對獨立的段，為每個段命名，并編排段號。②內(nèi)存分配管理方法段為內(nèi)存分配的基本單位，為每段分配連續(xù)的內(nèi)存儲存空間，每段的邏輯地址由0地址開始連續(xù)編址，段與段之間是離散的，物理內(nèi)存的管理采用分區(qū)式存儲管理方法。③段表為了實現(xiàn)分段管理，系統(tǒng)為每個進程建立一個段表，用于描述組成進程地址空間的各個段在內(nèi)存的物理位置，來實現(xiàn)進程的邏輯地址空間到內(nèi)存存儲空間的映射。段表的表項稱為段描述子，一般包括：段號s、段長、段基址(baseaddress)等。5.4.3分段存儲管理地址變換機構(gòu)如圖所示，為了完成進程邏輯地址到物理地址的映射，CPU會查找內(nèi)存中的段表，由段號得到段的基址，加上段內(nèi)偏移，得到實際的物理地址。5.4.4段的共享5.4.5分段與分頁系統(tǒng)的區(qū)別⑴頁幀是信息的物理單位，分頁是系統(tǒng)管理的需要，以解決內(nèi)存的外碎片問題；段是信息的邏輯單位，分段的目的是為了更好地滿足用戶的需要，但分段存儲管理存在外碎片問題。⑵頁的大小是固定的，由系統(tǒng)硬件決定；段的長度是不固定的，大小由用戶決定。⑶分頁系統(tǒng)進程的地址空間是一維的，即該地址空間是單一的線性地址空間，程序員只需利用一個標識符，即可表示一個地址；分段系統(tǒng)進程的地址空間是二維的，程序員在標識一個地址時，既需給出段名，又需給出段內(nèi)偏移。⑷分頁對于用戶是透明，它僅僅用于對內(nèi)存的管理；分段則對用戶是可見的。⑸分段存儲管理可以利用段的共享來實現(xiàn)內(nèi)存共享；分頁存儲管理較難實現(xiàn)內(nèi)存共享。5.4.6段頁式存儲管理分頁管理和分段管理各有所長，將分頁與分段結(jié)合形成段頁式存儲管理技術(shù)。在段頁式系統(tǒng)中，一個進程的地址空間被分成若干段，每段又被分成若干固定大小的頁面。段頁式存儲管理基本原理如下：⑴進程按其邏輯意義分段。⑵段內(nèi)分頁。⑶內(nèi)存實施分頁存儲管理，以頁幀為單位分配內(nèi)存。⑷邏輯地址結(jié)構(gòu)為三元組：<段號s，頁號p，偏移量d〉，V（s|p|d）41段號S段內(nèi)偏移段內(nèi)頁號P偏移量d⑸實現(xiàn)段頁式存儲管理需要兩個重要的數(shù)據(jù)結(jié)構(gòu)，即段表和頁表。①系統(tǒng)為每個進程建立一個段表。其段描述子如下：段號、頁表始址、頁表大小、存取控制、狀態(tài)等。②每個段建立一個頁表。其頁描述子如下：頁號、幀號、訪問位、修改位等。2.段頁式存儲管理地址變換過程如圖所示段頁式存儲管理地址變換過程如下：①從段表寄存器讀取段表始址，找到段表。②段號＋段表始址，得到段描述子地址。③從段描述子讀取頁表始址，頁號＋頁表始址，得到頁描述子地址。④從頁描述子讀取幀號。⑤由幀號f和偏移量拼成物理地址。在段頁式存儲管理中,CPU每次訪問一個在內(nèi)存中的操作數(shù)，需要要三次訪問內(nèi)存，第一次訪問內(nèi)存段表取得頁表始址，第二次訪問頁表取得幀號，形成物理地址，第三次訪問內(nèi)存中的操作數(shù)。段頁式存儲管理地址變換過程

445.5虛擬存儲器CPU執(zhí)行的指令和數(shù)據(jù)必須在物理內(nèi)存中第一種方法是將整個程序放進內(nèi)存中第二種方法是將正在執(zhí)行的部分程序放進內(nèi)存中。覆蓋技術(shù)允許程序部分裝入，但是需要程序員做一些額外的工作。虛擬存儲器（virtualmemory）技術(shù)允許程序部分裝入內(nèi)存，這種方案的一個很大的優(yōu)點就是程序的邏輯地址空間可以比物理內(nèi)存大。而且，虛擬存儲器將內(nèi)存抽象成一個巨大的、統(tǒng)一的存儲空間，將用戶看到的邏輯內(nèi)存與物理內(nèi)存分開，這種技術(shù)允許程序員不受內(nèi)存存儲的限制。5.5.1局部性原理⑴時間局部性，一條指令的一次執(zhí)行和下次執(zhí)行，一個數(shù)據(jù)的一次訪問和下次訪問都集中在一個較短時期內(nèi)。⑵空間局部性，當前執(zhí)行的指令和其鄰近的幾條指令，當前訪問的數(shù)據(jù)和鄰近的數(shù)據(jù)都集中在一個較小區(qū)域內(nèi)。⑶進程中有些部分是彼此互斥的，不是每次運行時都能執(zhí)行到。465.5.2虛擬存儲器的基本原理在進程裝入時，不必將其全部裝入內(nèi)存，而只要將當前需要執(zhí)行的部分頁或段裝入內(nèi)存，就可以讓進程執(zhí)行。在進程執(zhí)行過程中，如果需要執(zhí)行的指令或訪問的數(shù)據(jù)尚未在內(nèi)存(稱為缺頁或缺段)，則由操作系統(tǒng)將相應的頁或段調(diào)入內(nèi)存，然后繼續(xù)執(zhí)行進程。操作系統(tǒng)可以將內(nèi)存中暫時不使用的頁或段調(diào)出，保存在外存上，從而騰出空間存放將要裝入的進程以及將要調(diào)入的頁或段。47所謂虛擬存儲器就是將用戶邏輯內(nèi)存與物理內(nèi)存分離，具有請求調(diào)入功能和置換功能，為用戶提供了一個存儲容量比實際內(nèi)存大得多的存儲器管理系統(tǒng)。5.5.3虛擬存儲器的分類虛擬存儲器技術(shù)一般可以分為三類：⑴請求分頁存儲管理請求分頁存儲管理在分頁存儲管理的基礎上，增加了請求調(diào)頁等功能。與分頁存儲管理不同，請求分頁管理系統(tǒng)只需進程的部分頁面調(diào)入內(nèi)存即可以運行。⑵請求分段存儲管理請求分段存儲管理在分段存儲管理的基礎上，增加了請求調(diào)段或段的動態(tài)鏈接等功能。地址空間中各程序段在運行時并不全部裝入內(nèi)存，而是調(diào)入一個或少數(shù)幾個程序段運行，在運行過程中需要調(diào)用到哪段時，就根據(jù)該段長度在內(nèi)存分配一個連續(xù)的分區(qū)給它使用。若內(nèi)存中沒有足夠大的空閑分區(qū)，則考慮進行段的緊湊或?qū)⒛扯翁蕴鋈?。這種存儲管理技術(shù)稱為請求分段存儲管理。⑶請求段頁式存儲管理。請求段頁式存儲管理是請求分頁和請求分段存儲管理的結(jié)合。請求段頁式存儲管理的內(nèi)存分配單位是幀。邏輯地址是由段號、段內(nèi)頁號、頁內(nèi)偏移地址三部分組成的。在地址變換的過程中會產(chǎn)生缺段中斷和缺頁中斷兩種不同類型的中斷。5.5.4虛擬存儲器的容量一個虛擬存儲器的容量由以下兩個因素決定：⑴虛擬存儲器的容量受CPU的尋址能力的限制，CPU的尋址能力由計算機CPU地址總線結(jié)構(gòu)確定的，它是影響虛擬存儲器最大容量的重要參數(shù)。例如：某計算機CPU的地址總線長度為32位，則CPU可以尋址范圍是0～232-1，即4G。⑵一般來說，虛擬存儲器的容量由內(nèi)存和外存對換區(qū)容量之和所確定；有些虛擬存儲器技術(shù)還要考慮加上進程文件區(qū)的容量。很多教材認為“虛擬存儲器的容量由內(nèi)存和外存之和所確定”，這種說法是不正確的，外存的容量可能很大（如200G），不可能全部作為外存對換區(qū)，同時虛擬存儲器的容量也受CPU的尋址能力的限制。5.5.5虛擬存儲器的特征一次性和駐留性并非是進程運行所必需的條件，虛擬存儲器主要特征如下：①離散性。虛擬存儲器必須建立在離散分配的基礎上，在分頁、分段、段頁式存儲管理的基礎上才能實現(xiàn)虛擬存儲器。②多次性?；诰植啃栽?，虛擬存儲器將一個進程分成多次調(diào)入內(nèi)存，多次性是虛擬存儲器最重要的特征。③對換性。④虛擬性。5.5.6交換區(qū)策略、換入策略和置換策略1.交換區(qū)策略2.頁面換入策略⑴請求換頁(demandpaging)。⑵預換頁(prepaging)。3.置換策略⑴固定分配局部置換(fixedallocation，localreplacement)。⑵可變分配全局置換(variableallocation，globalreplacement)。⑶可變分配局部置換(variableallocation，localreplacement)。525.6請求分頁存儲管理5.6.1請求分頁存儲管理的實現(xiàn)原理①內(nèi)存按分頁管理。虛擬地址結(jié)構(gòu)為：虛頁號p|偏移量d。②根據(jù)局部性原理，進程的部分頁面裝入內(nèi)存即可運行，進程的全部頁面均有機會獲得到內(nèi)存執(zhí)行的機會。③即將要訪問的頁面不在內(nèi)存，由缺頁中斷機構(gòu)就立即產(chǎn)生中斷信號，將缺頁裝入內(nèi)存。缺頁中斷機構(gòu)由硬件和軟件組成。④進程運行需要內(nèi)存頁幀，如果內(nèi)存沒有空閑幀時，由頁面置換算法將一些老頁從內(nèi)存中淘汰出局，為即將被調(diào)入的新頁騰出空位。即老頁與新頁在內(nèi)外存的對換。5.6.2請求分頁存儲管理的實現(xiàn)機制

1．頁描述子的擴充在請求分頁系統(tǒng)中，一般對頁描述子進行如下擴充，除了頁號對應的幀號外，還增加了狀態(tài)位、修改位、訪問字段、存取控制、外存地址等。狀態(tài)位用于指示該頁是否已經(jīng)調(diào)入了內(nèi)存，“1”表示該頁在內(nèi)存中，“0”該頁不在內(nèi)存中。若不在內(nèi)存之中，則產(chǎn)生缺頁中斷。修改位表示該頁調(diào)入內(nèi)存后是否被修改過?！?”表示該頁被修改過，“0”相反。訪問字段用于記錄本頁在一定時間內(nèi)被訪問的次數(shù)，或記錄最近已經(jīng)有多長時間未被訪問。存取控制審定訪問權(quán)限。外存地址用于指出該頁在外存對換區(qū)中的地址，供調(diào)入該頁時使用。頁號幀號狀態(tài)位修改位訪問字段存取控制外存地址2．缺頁中斷機制在請求分頁系統(tǒng)中，CPU硬件一定要提供對缺頁中斷的支持，根據(jù)頁描述子中的狀態(tài)位判斷是否產(chǎn)生缺頁中斷。缺頁中斷是一個比較特殊的中斷，這主要體現(xiàn)在以下兩方面：①在指令的執(zhí)行期間產(chǎn)生和處理缺頁中斷信號。通常的CPU外部中斷是在每條指令執(zhí)行完畢后檢查是否有中斷請求到達。而缺頁中斷是在一條指令的執(zhí)行期間發(fā)現(xiàn)要訪問的指令和數(shù)據(jù)不在內(nèi)存時產(chǎn)生和處理的。②一條指令可以產(chǎn)生多個缺頁中斷。例如，有一條雙操作數(shù)的指令，每個操作數(shù)都不在內(nèi)存中，當這條指令執(zhí)行時，將產(chǎn)生多個中斷。CPU提供的硬件支持還要體現(xiàn)在當從中斷處理進程返回時，能夠正確執(zhí)行產(chǎn)生缺頁中斷的指令。3．請求分頁存儲管理的地址變換流程圖4.6.3頁面置換算法

頁面在內(nèi)外存之間來回替換叫抖動，抖動會引起不必要的額外開銷。1．先進先出算法先進先出算法（FIFO）的基本思想是先進入內(nèi)存的頁面，先被換出，總是先淘汰那些駐留在內(nèi)存時間最長的頁面。理由是：最先進入內(nèi)存的頁面不再被訪問的可能性最大?？梢酝ㄟ^隊列來表示各頁的裝入時間先后。2．最佳置換算算法最佳頁面置換算法(Optimal，OPT)是淘汰永不使用的或是在最長時間內(nèi)不再被訪問的頁面。就是說從內(nèi)存中移出以后不再使用的頁面，如無這樣的頁面，則選擇以后最長時間內(nèi)不需要訪問的頁，這就是最佳置換法。3．最近最久未使用置換算法最近最久未使用置換算法(LeastRecentlyUsed，LRU)的基本思想是根據(jù)局部性原理，如果某一頁被訪問了，那么它很可能馬上又被訪問。反之，如果某一頁很長時間沒有被訪問，那么最近也不太可能會被訪問。其實質(zhì)是，當需要置換一頁時，選擇在最近一段時間最久未使用的頁面予以淘汰。5.頁面緩沖算法頁面緩沖算法(pagebuffering)是對FIFO算法的發(fā)展.通過建立置換頁面的緩沖，從而有機會找回剛被置換的頁面，從而減少系統(tǒng)I/O的開銷。頁面緩沖算法用FIFO算法選擇被置換頁，把被