存儲器管理課件

存儲器管理

存儲器管理是指對存儲器資源的管理。存儲器管理的主要對象是內(nèi)存。存儲管理的內(nèi)容主要包括：存儲器資源的組織（如內(nèi)存的組織方式）；地址變換（邏輯地址與物理地址的對應(yīng)關(guān)系維護(hù)）；虛擬存儲的調(diào)度算法。4.1程序的裝入和鏈接對用戶程序的處理步驟編譯目標(biāo)模塊庫…..鏈接程序裝入模塊裝入程序內(nèi)存源程序4.1.1程序的裝入將一個模塊裝入內(nèi)存時，可采用三種方式：絕對裝入方式可重定位方式動態(tài)運行時裝入方式1.絕對裝入方式

如果事先知道程序?qū)Ⅰv留在內(nèi)存的什么位置，那么編譯或匯編程序?qū)a(chǎn)生絕對地址的目標(biāo)代碼，裝入程序直接將目標(biāo)代碼裝入相應(yīng)的內(nèi)存空間。Load222436522241024優(yōu)點：裝入過程簡單。缺點：過于依賴于硬件結(jié)構(gòu)，只適用于單道程序環(huán)境，不適于多道程序系統(tǒng)。2.可重定位方式

把用戶程序在裝入內(nèi)存時對目標(biāo)程序中指令和數(shù)據(jù)的修改過程稱為重定位。當(dāng)用戶程序被裝入內(nèi)存時，一次性實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換，稱為靜態(tài)重定位。優(yōu)點：無需硬件支持，地址變換由重定位裝配程序完成。缺點：地址變換在裝入時一次性完成，裝入內(nèi)存后不能移動，不利于內(nèi)存空間的有效利用，難于實現(xiàn)程序的共享。LOAD1,2500365LOAD1,12500365100001100012500150005000250010000作業(yè)地址空間內(nèi)存空間邏輯地址物理地址3.動態(tài)運行時裝入方式

裝入模塊裝入內(nèi)存后，不立即把相對地址轉(zhuǎn)換成絕對地址，而是推遲到程序真正要執(zhí)行時才進(jìn)行。優(yōu)點：程序占用的內(nèi)存空間可動態(tài)變化，即允許程序在內(nèi)存中移動；也不必分配連續(xù)的內(nèi)存空間，便于程序的共享。缺點：需要硬件重定位寄存器支持，OS實現(xiàn)較復(fù)雜。4.1.2程序的鏈接

鏈接是指多個目標(biāo)模塊在執(zhí)行時的地址空間分配和相互引用。根據(jù)鏈接時間的不同，把鏈接分為以下三種類型：靜態(tài)鏈接方式裝入時動態(tài)鏈接運行時動態(tài)鏈接1.靜態(tài)鏈接方式

將所有目標(biāo)模塊和所需的庫函數(shù)在裝入前事先鏈接成一個完整的裝入模塊（可執(zhí)行文件），以后不再拆開的鏈接方式。在將幾個目標(biāo)模塊鏈接裝配成一個裝入模塊時，需要解決以下兩個問題：對相對地址進(jìn)行修改；變換外部調(diào)用符號。例：模塊

ACALLB；Return；0L－1模塊

BCALLC；Return；0M－1模塊

CReturn；0N－10模塊

AJSR“L”Return；L－1模塊

BJSR“L＋M”Return；LL＋M－1L＋ML＋M＋N－1模塊

CReturn；(a)目標(biāo)模塊(b)裝入模塊2.裝入時動態(tài)鏈接

一個程序的多個目標(biāo)模塊在裝入內(nèi)存時，邊裝入邊鏈接。

優(yōu)點:便于修改和更新；便于實現(xiàn)對目標(biāo)模塊的共享。3.運行時動態(tài)鏈接

一個程序的多個目標(biāo)模塊在程序執(zhí)行時，根據(jù)需要再動態(tài)裝入和鏈接。

優(yōu)點:

本次執(zhí)行過程中不用的模塊可以不裝入和鏈接。如典型的錯誤處理模塊。

連續(xù)分配是指為一個用戶程序分配一個連續(xù)的內(nèi)存空間。具體分為四種分配方式：單一連續(xù)分配固定分區(qū)分配動態(tài)分區(qū)分配可重定位分區(qū)分配4.2連續(xù)分配方式4.2.1單一連續(xù)分配方式最簡單的一種存儲管理方式，適用于單用戶、單任務(wù)的OS。把內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。優(yōu)點：易于管理。缺點：對要求內(nèi)存空間少的程序，造成內(nèi)存浪費；程序全部裝入，很少使用的程序部分也占用內(nèi)存。4.2.2固定分區(qū)分配方式最簡單的可運行多道程序的存儲管理方式。將內(nèi)存的用戶空間劃分為若干個固定大小的連續(xù)分區(qū)，在每個分區(qū)中只裝入一道作業(yè)。1.劃分分區(qū)的方法：分區(qū)大小相等：只適合于多個相同程序的并發(fā)執(zhí)行（處理多個類型相同的對象）。分區(qū)大小不等：多個小分區(qū)、適量的中等分區(qū)、少量的大分區(qū)。根據(jù)程序的大小，分配當(dāng)前空閑的、適當(dāng)大小的分區(qū)。固定分區(qū)(大小相同)固定分區(qū)(大小不同)例：8M8M8M8M8MOperatingSystem8M12M8M8M6M4M2MOperatingSystem分區(qū)使用表：用于記錄分區(qū)的大小和使用情況，按分區(qū)大小排隊。包括每個分區(qū)的起始地址、大小和狀態(tài)（是否分配）。用戶程序需要裝入時，內(nèi)存分配程序檢索該表，找出一個能滿足要求尚未分配的分區(qū)，分配給該程序，并將其表項中的狀態(tài)置為“已分配”。若未找到大小足夠的分區(qū)，則拒絕為用戶程序分配內(nèi)存。2.內(nèi)存分配例：某系統(tǒng)的內(nèi)存容量為256K，操作系統(tǒng)占用低地址的20K，其余空間劃分成4個固定大小的分區(qū)。OS20K28K60K124K256K-1

作業(yè)A（6K）作業(yè)B（20K）作業(yè)C（50K）12340K主存作業(yè)A6K作業(yè)B20K作業(yè)C50K作業(yè)隊列分區(qū)說明表分區(qū)號大小(KB)始址(KB)狀態(tài)1820已分配23228已分配36460已分配4132124未分配優(yōu)點：易于實現(xiàn)，開銷小。缺點：內(nèi)碎片造成浪費；分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。4.2.3動態(tài)分區(qū)分配方式動態(tài)創(chuàng)建分區(qū)：在裝入程序時按其初始要求分配，或在其執(zhí)行過程中通過系統(tǒng)調(diào)用進(jìn)行分配或改變分區(qū)大小。優(yōu)點：沒有內(nèi)碎片。缺點：有外碎片；如果大小不是任意的，也可能出現(xiàn)內(nèi)碎片。進(jìn)程A（8K）進(jìn)程D（124K）進(jìn)程B（16K）進(jìn)程C（64K）…OS進(jìn)程A進(jìn)程B進(jìn)程C進(jìn)程DOS進(jìn)程A進(jìn)程B進(jìn)程COS進(jìn)程A進(jìn)程BOS進(jìn)程A1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表：記錄每個空閑分區(qū)的情況，包括分區(qū)序號、分區(qū)始址、分區(qū)大小等?？臻e分區(qū)鏈：在每個空閑分區(qū)的起始部分開辟出一個單元，存放一個鏈表指針和該分區(qū)的大小，在尾部則設(shè)置一后向指針。系統(tǒng)中用一個固定單元作為空閑分區(qū)鏈表的鏈表頭指針，指向第一塊空閑分區(qū)首地址，最后一塊空閑分區(qū)的鏈表指針存放鏈尾標(biāo)志。當(dāng)分區(qū)被分配出去以后，狀態(tài)位由“0”改為“1”，此時前后指針無意義。例：采用雙向鏈的空閑分區(qū)鏈結(jié)構(gòu)2.分區(qū)分配算法首次適應(yīng)算法循環(huán)首次適應(yīng)算法最佳適應(yīng)算法首次適應(yīng)法FF：要求空閑區(qū)按首址遞增的次序組織空閑區(qū)表（隊列）。當(dāng)進(jìn)程申請大小為SIZE的內(nèi)存時，系統(tǒng)從空閑區(qū)表的第一個表目開始查詢，直到首次找到等于或大于SIZE的空閑區(qū)。從該區(qū)中劃出大小為SIZE的分區(qū)分配給進(jìn)程，余下的部分仍作為一個空閑區(qū)留在空閑區(qū)表中，但要修改其首址和大小。優(yōu)點：該算法是盡可能地利用低地址空間，從而保證高地址空間有較大的空閑區(qū)。缺點：低地址部分的不斷劃分，會留下許多難以利用的、很小的空閑分區(qū)，而每次查找都是從低地址部分開始，會增加查找可利用分區(qū)時的開銷。循環(huán)首次適應(yīng)算法：把存儲空間中空白區(qū)構(gòu)成一個循環(huán)鏈，每次為存儲請求查找合適的分區(qū)時，總是從上次查找結(jié)束的地方開始，只要找到一個足夠大的空白區(qū)，就將它劃分后分配出去。優(yōu)點：能使內(nèi)存中的空閑分區(qū)分布均勻，從而減少了查找空閑分區(qū)時的開銷。缺點：使內(nèi)存中缺乏大的分區(qū)。最佳適應(yīng)算法：要求按空閑區(qū)大小從小到大的次序組成空閑區(qū)表（隊列）。當(dāng)進(jìn)程申請一個存儲區(qū)時，系統(tǒng)從表頭開始查找，當(dāng)找到第一個滿足要求的空閑區(qū)時，停止查找，并且這個空閑區(qū)是最佳的空閑區(qū)。所謂最佳即選中的空閑區(qū)是滿足要求的最小空閑區(qū)。優(yōu)點：在系統(tǒng)中若存在一個與申請分區(qū)大小相等的空閑區(qū)，必定會被選中，而首次適應(yīng)法則不一定。若系統(tǒng)中不存在與申請分區(qū)大小相等的空閑區(qū)，則選中的空閑區(qū)是滿足要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。缺點：空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。隨著時間的推移，系統(tǒng)中的小空閑區(qū)會越來越多，從而造成存儲區(qū)的大量浪費。幾點說明：上述三種分配算法各有利弊，到底哪種最好不能一概而論，而應(yīng)針對具體作業(yè)序列來分析。對于某一作業(yè)序列來說，某種算法能將該作業(yè)序列中所有作業(yè)安置完畢，那么我們說該算法對這一作業(yè)序列是合適的。對于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則這一算法對該作業(yè)序列是不合適的。例：

有一作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。分析系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊列。（圖中灰色部分為空閑區(qū)。）①

首次適應(yīng)算法的空閑區(qū)隊列：②

循環(huán)首次適應(yīng)算法的空閑區(qū)隊列：③

最佳適應(yīng)算法的空閑區(qū)隊列：30K20K5K46K^20K100K160K210K鏈?zhǔn)字羔?0K20K5K46K20K100K160K210K鏈?zhǔn)字羔?K20K30K46K^160K100K20K210K鏈?zhǔn)字羔?.分區(qū)的分配在采用分區(qū)存儲管理的系統(tǒng)中，系統(tǒng)初啟后。除操作系統(tǒng)占用一個分區(qū)外，其余存儲區(qū)為一個大的空閑區(qū)。分區(qū)的分配是指利用某種分配算法，找到所需的分區(qū)，按照大小劃分出一塊內(nèi)存空間分配出去，剩余的部分留在空閑分區(qū)鏈中。

從頭開始查表檢索完否？m.size＞u.size?m.size－u.size≤size?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回繼續(xù)檢索下一個表項將該分區(qū)從鏈中移出YNNYYN分配流程圖：

說明： 將一個空閑區(qū)分成二部分有兩種辦法：從空閑區(qū)的上部開始劃出U.SIZE大小的空閑區(qū)給用戶；從空閑區(qū)的底部開始向上劃出U.SIZE大小的空閑區(qū)給用戶。 一般常用第二種辦法，因為這樣劃分時，余下的部分在空閑區(qū)表中的首地址不變，只需要修改一下大小就行了。4.分區(qū)的回收當(dāng)某個進(jìn)程釋放某存儲區(qū)時，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中去，否則把釋放區(qū)作為一個空閑區(qū)插入到空閑區(qū)表的適當(dāng)位置。分區(qū)回收時會有四種情況：4.2.4可重定位分區(qū)分配

不能被利用的小分區(qū)稱為“零頭”或“碎片”。通過移動，把多個分散的小分區(qū)拼接成大分區(qū)的方法被稱為“拼接”或“緊湊”。每次“緊湊”后必須對移動了的程序或數(shù)據(jù)進(jìn)行重新定位。1.動態(tài)重定位的引入操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)作業(yè)4操作系統(tǒng)作業(yè)1空閑區(qū)作業(yè)2空閑區(qū)作業(yè)3空閑區(qū)操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)緊湊前緊湊后2.動態(tài)重定位的實現(xiàn)

需要硬件地址變換機構(gòu)的支持，即重定位寄存器。內(nèi)存地址＝相對地址＋重定位寄存器中的地址。地址變換過程是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問而自動進(jìn)行的。LOAD1,25003650100250050002500相對地址10000重定位寄存器＋LOAD1,250036510000101001250015000作業(yè)J處理機一側(cè)存儲器一側(cè)主存動態(tài)重定位示意圖3.動態(tài)重定位分區(qū)分配算法流程圖：請求分配u.size分區(qū)檢索空閑分區(qū)鏈(表)找到大于u.size的可用區(qū)?按動態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號及首址空閑分區(qū)總和≥u.size?進(jìn)行緊湊形成連續(xù)空閑區(qū)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)否是無法分配返回否是4.2.5對換1.對換的引入對換是指把內(nèi)存中暫時不能運行的進(jìn)程或者暫時不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運行條件的進(jìn)程或者進(jìn)程所需的程序和數(shù)據(jù)，調(diào)入內(nèi)存。通過對換，可利用外存來邏輯地擴充主存。如果對換以整個進(jìn)程為單位，便稱“整體對換”或“進(jìn)程對換”。如果以“頁”或“段”為單位，則分別稱“頁面對換”或“分段對換”，并通稱“部分對換”。2.對換空間的管理

在具有對換功能的OS中，通常把外存分為文件區(qū)和對換區(qū)。文件區(qū)存放文件，常采用離散方式，以提高文件存儲空間的利用率；對換區(qū)存放從內(nèi)存換出的進(jìn)程，常利用連續(xù)分配方式，以提高對換速度。進(jìn)程的換出：選擇處于阻塞狀態(tài)且優(yōu)先級最低的進(jìn)程作為換出進(jìn)程，換出后收回內(nèi)存空間，修改進(jìn)程的PCB相關(guān)信息。進(jìn)程的換入：找出“就緒”狀態(tài)并已經(jīng)換出的進(jìn)程，將其中換出時間最久的進(jìn)程作為換入進(jìn)程，將其換入。直到已無可換入的進(jìn)程和無可換出的進(jìn)程。3.進(jìn)程的換出和換入4.3基本分頁存儲管理方式離散分配方式：為了減少因連續(xù)分配所產(chǎn)生的碎片，提高內(nèi)存的利用率產(chǎn)生了離散分配方式，它可將一個用戶程序離散地分配到內(nèi)存中的多個不相連接的區(qū)域中。其方式有：a.分頁存儲管理方式－離散的基本單位是“頁”；b.分段存儲管理方式－離散的基本單位是“段”；c.段頁式存儲管理方式。

基本分頁存儲管理方式：

在分頁存儲管理方式中，如果不具備頁面對換功能，就是基本分頁存儲管理方式，即不支持虛擬存儲器的功能。頁面

頁（頁面）－把每個作業(yè)(進(jìn)程)邏輯地址空間劃分成若干大小相等的片。

物理塊－把內(nèi)存空間劃分成與頁相同的片。分頁式存儲器的邏輯地址結(jié)構(gòu)分頁地址中的地址結(jié)構(gòu)確定了主存儲器的分頁大小,也決定了頁面大小。

頁號P頁內(nèi)地址(偏移量)31 1211 0總頁數(shù)：220＝1M(頁)；每頁大小為：212＝4KB3.頁表系統(tǒng)為每個進(jìn)程建立一張頁面映象表，即頁表。頁表的長度和首地址存放在該進(jìn)程的進(jìn)程控制塊（PCB）中。頁表的作用是實現(xiàn)從頁號到物理塊號的地址映射。頁表由頁號和塊號組成，指出邏輯地址中頁號與主存中物理塊號的對應(yīng)關(guān)系。頁號作業(yè)地址空間的頁序號。塊號內(nèi)存空間的頁面序號。邏輯上相鄰的頁，物理上不一定相鄰。頁號塊號021326頁表的作用用戶程序0頁1頁2頁3頁4頁5頁…n頁頁表頁號塊號02132638495……內(nèi)存空間012345678910注意：頁大小的選擇太大：浪費；太?。喉摫磉^長；頁的大小是2K

，通常為512B-5KB。例：如圖，作業(yè)1有2頁分別裝入內(nèi)存的第5、6塊；作業(yè)2有3頁裝入內(nèi)存的第2、4、7塊；作業(yè)3有1頁裝入內(nèi)存的第8塊。4.3.2地址變換機構(gòu)基本任務(wù)：邏輯地址

物理地址。由于頁面和物理塊大小相同，他們的地址是一一對應(yīng)的，無需變換。所以地址變換實際上只是將邏輯地址中的頁號，轉(zhuǎn)換為內(nèi)存中的物理塊號，這一任務(wù)是由頁表來完成的。

即：頁號

頁表

存儲塊號b，與頁內(nèi)地址w合成，形成物理地址。1.基本的地址變換機構(gòu)頁表長度（5）頁表始址頁內(nèi)地址w頁號（3）wbb01234頁表寄存器

邏輯地址頁表物理地址塊號頁號＋>越界中斷例：在采用頁式存儲管理的系統(tǒng)中，某作業(yè)J的邏輯地址空間為4頁（每頁2048字節(jié)），且已知該作業(yè)的頁面映像表（即頁表）如右圖，試借助地址變換圖（要求畫出地址變換圖）求出有效邏輯地址4865所對應(yīng)的物理地址。

頁號塊號02142638頁表長度頁表始址頁內(nèi)地址頁號7696頁表寄存器邏輯地址頁表物理地址＋頁號塊號021426384865=2*2048+7697692物理地址：6*2048+769=130572.具有快表的地址變換機構(gòu)在前述的頁地址變換過程中有一個嚴(yán)重的問題，那就是每一次對內(nèi)存的訪問都要訪問頁表，頁表是放在內(nèi)存中的，也就是說每一次訪問內(nèi)存的指令至少要訪問兩次內(nèi)存，運行速度要下降一半。若不解決這一問題是不能令人忍受的。為了提高存取速度，通常設(shè)置一個具有并行查詢能力的特殊高速緩沖寄存器，存放當(dāng)前作業(yè)的最常用的頁號及對應(yīng)塊號。我們把存放在高速緩沖寄存器中的頁表叫快表，把存放在內(nèi)存中的頁表稱為慢表。快表又叫聯(lián)想寄存器。需要說明的是：快表的地址轉(zhuǎn)換是非常快的，因為它是將頁號與快表中的各行同時比較，從而大大減少了地址變換時間，基本上克服了兩次訪問主存的缺點。頁表長度（5）頁表始址頁內(nèi)地址w頁號（3）wbb01234頁表寄存器邏輯地址寄存器頁表塊號頁號＋>b輸入寄存器塊號頁號快表具有快表的地址變換機構(gòu)越界中斷4.3.3兩級頁表和多級頁表當(dāng)頁表項很多時，僅采用一級頁表需要大片連續(xù)空間，可將頁表也分頁，并對頁表所占的空間進(jìn)行索引形成外層頁表。由此構(gòu)成兩級頁表。更進(jìn)一步可形成多級頁表。

1.兩級頁表外層頁表有210個頁表項；最多允許有210個頁表分頁；頁面大小為：212＝4KB。邏輯地址結(jié)構(gòu)可描述如下：101110780121742n第0頁頁表146…012…1023第1頁頁表11411501…1023外部頁表01234567……1141151468第n頁頁表1468012…1023內(nèi)存空間兩級頁表結(jié)構(gòu)具有兩級頁表的地址變換機構(gòu)外部頁號P1P2外部頁內(nèi)地址頁內(nèi)地址d邏輯地址＋外部頁表寄存器外部頁表＋db頁表頁表物理地址……兩級頁表地址變換需三次訪問內(nèi)存：一次訪問頁目錄、一次訪問頁表頁、一次訪問指令或數(shù)據(jù)，訪問時間加了兩倍?？稍鲈O(shè)快表，提高訪問速度。4.4基本分段存儲管理方式

分頁存儲管理方式中用戶的程序地址空間是一維線性的，這對用戶特別是程序設(shè)計極不方便，用戶看待程序是以自然段為單位的，如：主程序段、子程序段、數(shù)據(jù)段等……。因此人們提出了段式存儲管理方式。

將程序的地址空間按內(nèi)容或過程（函數(shù)）關(guān)系劃分為若干個段，每段有自己的名字。以段為單位分配內(nèi)存，然后通過地址重定位機構(gòu)把段式虛擬地址轉(zhuǎn)換為實際的內(nèi)存物理地址?；舅枷耄褐饕菫榱藵M足用戶和程序員的下述需要：方便編程分段共享分段保護(hù)動態(tài)鏈接動態(tài)保護(hù)動態(tài)增長4.4.1分段存儲管理方式的引入1.分段每個段定義了一組邏輯信息。如：主程序段、子程序段、數(shù)據(jù)段等。用段號代替段名。兩維邏輯地址：段號＋段內(nèi)地址。地址結(jié)構(gòu)： 段號S+段內(nèi)地址W4.4.2分段系統(tǒng)的基本原理段號S段內(nèi)地址d3116150(一個作業(yè)最多216=64K個段，每段最大長度216=64KB)每個進(jìn)程一張表，用以實現(xiàn)地址變換，程序的每一個段在段表中占用一個表目。包括：段的長度、段的首址(基址)信息。2.段表段號012段首址段長度58K20K100K110K260K140K作業(yè)空間(MAIN)＝0030K(X)＝1020K(D)＝2015K(S)＝3010K30K20K15K10K40K80K120K150K段長基址段號(MAIN)＝030K(X)＝120K(D)＝215K(S)＝310K040K80K120K150K段表內(nèi)存空間0123利用段表實現(xiàn)地址映射3.地址變換機構(gòu)控制寄存器段表始址段表長度＞2100＋段號S越界1K段長600段號01236K4K5002008K9200基址位移量W＋82928K82928692主存物理地址有效地址地址變換需兩次訪問內(nèi)存，訪問時間加了一倍?？稍鲈O(shè)快表，提高訪問速度。例：有一段表如右圖所示，試分別求邏輯地址（2，88）和邏輯地址（4，100）所對應(yīng)的物理地址。段號基地址段長021960012300142901003132758041952964.分段與分頁技術(shù)的比較相似：二者在內(nèi)存中都不是整體連續(xù)的，都要通過地址映射機構(gòu)將邏輯地址映射到物理內(nèi)存中。不同：

“頁”是信息的“物理”單位，大小固定。“段”是信息的邏輯單位，即它是一組有意義的信息，其長度不定。頁的大小是由系統(tǒng)固定的，在一個系統(tǒng)中所有頁的大小是一樣的，只能有一種大??；段的長度因段而異，取決于用戶所編寫的程序分頁的作業(yè)的地址空間是單一的線性地址空間，分段作業(yè)的地址空間是二維的。4.4.3信息共享

分段系統(tǒng)的一個突出優(yōu)點是易于實現(xiàn)段的共享，即允許若干個進(jìn)程共享一個或多個分段，且對共享段的保護(hù)也簡單易行。分頁系統(tǒng)雖然也能實現(xiàn)程序和數(shù)據(jù)的共享，但遠(yuǎn)不如分段系統(tǒng)方便。

例：40個用戶共享一文本編輯程序。該程序有160KB的代碼和40KB的數(shù)據(jù)區(qū)。其中，160KB的代碼為可重入代碼（即允許多個進(jìn)程同時訪問的代碼，但不允許任何進(jìn)程對它進(jìn)行修改。）分頁系統(tǒng)中共享editor的示意圖（設(shè)頁面大小為4KB）分段系統(tǒng)中共享editor的示意圖4.4.4段頁式存儲管理方式

引入：

分頁和分段管理方式各有其優(yōu)缺點，分頁系統(tǒng)能有效提高內(nèi)存的利用率，而分段則能更好地滿足用戶的需要，因此可以將兩者結(jié)合成一種新的存儲管理方式系統(tǒng)稱為“段頁式系統(tǒng)”。1.基本原理一個程序首先被分成若干程序段，每一段賦予不同的分段標(biāo)識符，然后，對每一分段又分成若干個固定大小的頁面。地址結(jié)構(gòu)：分三部分（如圖所示）

作業(yè)地址空間和地址結(jié)構(gòu)04K8K12K15K16K子程序段04K8K數(shù)據(jù)段04K8K10K12K(a)段號(S)段內(nèi)頁號(P)頁內(nèi)地址(W)(b)主程序段2.地址映射段表：記錄了每一段的頁表始址和頁表長度。頁表：記錄了邏輯頁號與內(nèi)存塊號的對應(yīng)關(guān)系（每一段有一個，一個程序可能有多個頁表）。內(nèi)存分配管理：同頁式管理。如圖所示：利用段表和頁表實現(xiàn)地址映射段號狀態(tài)頁表大小頁表始址0111213041頁號狀態(tài)存儲塊#0111213041操作系統(tǒng)主存頁表段表段表大小段表始址段表寄存器3.地址變換過程段表寄存器段表始址段表長度＞段號S頁號P＋段超長段表0123＋頁內(nèi)地址頁表0123b塊號

b塊內(nèi)地址頁表始址頁表長度地址變換需三次訪問內(nèi)存：一次訪問段表、一次訪問頁表、一次訪問指令或數(shù)據(jù)，訪問時間加了兩倍?？稍鲈O(shè)快表，提高訪問速度。4.5虛擬存儲器的基本概念基本思想：

通過軟硬件結(jié)合的方法，利用大容量的外存空間來邏輯擴充內(nèi)存，使得產(chǎn)生一種不受實際內(nèi)存容量大小限制的邏輯的虛擬存儲器。1.常規(guī)存儲器管理方式的特征一次性駐留性

4.5.1虛擬存儲器的引入2.局部性原理

指程序在執(zhí)行過程中的一個較短時期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。具體表現(xiàn)在以下幾方面：程序在執(zhí)行時，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)移和過程調(diào)用指令。過程調(diào)用的嵌套深度一般不超過5，因此執(zhí)行的范圍不超過這組嵌套的過程。程序中存在相當(dāng)多的循環(huán)結(jié)構(gòu)，它們由少量指令組成，而被多次執(zhí)行。程序中存在相當(dāng)多對一定數(shù)據(jù)結(jié)構(gòu)的操作，如數(shù)組操作，往往局限在較小范圍內(nèi)。還可以表現(xiàn)為：時間局部性，即一條指令的一次執(zhí)行和下次執(zhí)行，一個數(shù)據(jù)的一次訪問和下次訪問都集中在一個較短時期內(nèi)；空間局部性，即當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問的數(shù)據(jù)和鄰近的數(shù)據(jù)都集中在一個較小區(qū)域內(nèi)。

基于程序局部性原理，就沒有必要把一個作業(yè)一次性全部裝入內(nèi)存再開始運行。而是可以把程序當(dāng)前執(zhí)行所涉及的信息放入內(nèi)存中，其余部分可根據(jù)需要臨時調(diào)入。3.虛擬存儲器的定義

是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。4.5.2虛擬存儲器的實現(xiàn)方法1.分頁請求系統(tǒng)在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁面置換功能所形成的頁式虛擬存儲系統(tǒng)。2.請求分段系統(tǒng)在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段功能、分段置換功能所形成的段式虛擬存儲系統(tǒng)。4.5.3虛擬存儲器的特征多次性（虛擬存儲器最重要的特征） 指一個作業(yè)被分成多次調(diào)入內(nèi)存運行。對換性指允許在作業(yè)的運行過程中進(jìn)行換進(jìn)、換出。虛擬性（實現(xiàn)虛擬存儲器的主要目的）指能夠從邏輯上擴充內(nèi)存容量。

三個特征中，虛擬性以多次性、對換性為基礎(chǔ)，而多次性、對換性必須建立在離散分配的基礎(chǔ)上。4.6請求分頁存儲管理方式

是指在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁面置換功能所形成的頁式虛擬存儲系統(tǒng)。頁表項：頁號、物理塊號、狀態(tài)位、訪問位、修改位、外存地址。

狀態(tài)位：表示該頁是在內(nèi)存還是在外存；訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定）；修改位：查看此頁是否在內(nèi)存中被修改過；外存地址：用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入該頁時參考。頁號物理塊號狀態(tài)位外存地址訪問位修改位4.6.1請求分頁中的硬件支持1.頁表機制2.缺頁中斷機構(gòu)在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，準(zhǔn)備將該頁調(diào)入內(nèi)存。此時應(yīng)將缺頁的進(jìn)程掛起（調(diào)頁完成后喚醒）。如果內(nèi)存中有空閑塊，則分配一個塊，將要調(diào)入的頁裝入該塊，并修改頁表中相應(yīng)頁表項目的狀態(tài)位及相應(yīng)的物理塊號。若此時內(nèi)存中沒有空閑塊，則要淘汰某頁（若被淘汰頁在內(nèi)存期間被修改過，則要將其寫回外存）。缺頁中斷與一般中斷的比較：相同點：缺頁中斷同一般中斷都是中斷，都需要保護(hù)現(xiàn)場、中斷處理、恢復(fù)現(xiàn)場。不同點：一般中斷是一條指令完成后中斷，缺頁中斷是一條指令執(zhí)行時中斷；一條指令執(zhí)行時可能產(chǎn)生多個缺頁中斷。例如一條指令可能訪問多個內(nèi)存地址，這些地址在不同的頁中。將產(chǎn)生6次缺頁中斷例：COPYATOB頁面B：A：654321指令copyATOB3.地址變換機構(gòu)兩種內(nèi)存分配策略：固定分配和可變分配。兩種置換策略：全局置換和局部置換。經(jīng)過組合，得出三種適用的策略：固定分配局部置換可變分配全局置換可變分配局部置換4.6.2內(nèi)存分配策略和分配算法1.物理塊的分配策略2.物理塊分配算法平均分配算法按比例分配算法考慮優(yōu)先權(quán)的分配算法請求調(diào)頁(demandpaging)：只調(diào)入發(fā)生缺頁時所需的頁面。

優(yōu)點：容易實現(xiàn)；

缺點：對外存I/O次數(shù)多，開銷較大。預(yù)調(diào)頁(prepaging)：在發(fā)生缺頁需要調(diào)入某頁時，一次調(diào)入該頁以及相鄰的幾個頁。

優(yōu)點：提高調(diào)頁的I/O效率；

缺點：基于預(yù)測，若調(diào)入的頁在以后很少被訪問，則效率低。常用于程序裝入時的調(diào)頁。4.6.3調(diào)頁策略1.何時調(diào)入頁面（有兩種常用策略）2.調(diào)入頁面的來源進(jìn)程裝入時，將其全部頁面復(fù)制到對換區(qū)，以后總是從對換區(qū)調(diào)入。執(zhí)行時調(diào)入速度快，要求對換區(qū)空間較大。凡是未被修改的頁面，都直接從文件區(qū)讀入，而被置換時不需調(diào)出；已被修改的頁面，被置換時需調(diào)出到對換區(qū)，以后從對換區(qū)調(diào)入。節(jié)省對換區(qū)空間，用于缺少足夠的對換區(qū)的系統(tǒng)。

將外存劃分為兩部分：文件區(qū)、對換區(qū)。通常對外存對換區(qū)的I/O效率比文件區(qū)的高。關(guān)于調(diào)入頁面的來源，這里有兩種做法：4.7頁面置換算法

把選擇換出頁面的算法稱為頁面置換算法。應(yīng)該把那些以后不再會訪問的頁面換出，或者把那些停留較長時間而不會再訪問的頁面調(diào)出，最終的目的是達(dá)到一個較低的頁面更換頻率。幾種常用置換算法：最佳置換算法(OPT,Optimal)先進(jìn)先出置換算法(FIFO)最近最久未使用置換算法(LRU,LeastRecentlyUsed)Clock置換算法最少使用置換算法(LFU,LeastFrequentlyUsed)頁面緩沖算法(PBA,PageBufferingAlgorithm)Belady于1966年提出的一種理論上的算法。選擇“未來不再使用的”或“在最長時間內(nèi)不再被訪問的”頁面被置換。通?？梢垣@得最低的缺頁率。這是一種理想情況，是實際執(zhí)行中無法預(yù)知的，因而不能實現(xiàn)。可用作性能評價的依據(jù)。1.最佳(Optimal)置換算法4.7.1最佳置換算法和先進(jìn)先出置換算法

假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

。70770170122010320304243230321201201770101203利用最佳頁面置換算法時的置換圖：例：共發(fā)生6次頁面置換▲▲▲▲▲▲2.先進(jìn)先出(FIFO)頁面置換算法基本思想：總是先淘汰那些駐留在內(nèi)存時間最長的頁面，即先進(jìn)入內(nèi)存的頁面先被置換掉。理由是：最先進(jìn)入內(nèi)存的頁面不再被訪問的可能性最大。引入指針將進(jìn)入內(nèi)存的頁面按時間的先后次序鏈成隊列，新進(jìn)入的頁面從隊尾入隊，淘汰總是從隊列頭進(jìn)行。707701701220103231044302303210132017702012304204230230127127011例：（同前例）利用FIFO置換算法時的置換圖：共發(fā)生12次頁面置換▲▲▲▲▲▲▲▲▲▲▲▲Belady現(xiàn)象:Belady現(xiàn)象：采用FIFO算法時，如果對一個進(jìn)程未分配它所要求的全部頁面，有時就會出現(xiàn)分配的頁面數(shù)增多，缺頁率反而提高的異?，F(xiàn)象。描述：一個進(jìn)程P要訪問M個頁，OS分配N個內(nèi)存頁面給進(jìn)程P；對一個訪問序列S，發(fā)生缺頁次數(shù)為PE(S,N)。當(dāng)N增大時，PE(S,N)時而增大，時而減小。原因：FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動態(tài)特征是矛盾的，即被置換的頁面并不是進(jìn)程不會訪問的。Belady現(xiàn)象的例子：進(jìn)程P有5頁程序。訪問頁的順序為：1,2,3,4,1,2,5,1,2,3,4,5。(1)

如果在內(nèi)存中分配3個頁面，則缺頁情況如下：12次訪問中有缺頁9次；FIFO123412512345頁0123412555344頁112341222533頁21234111255缺頁xxxxxxx√√x√x(2)

如果在內(nèi)存中分配4個頁面，則缺頁情況如下：12次訪問中有缺頁10次；FIFO123412512345頁0123444512345頁112333451234頁21222345123頁3111234512缺頁xxxx√√xxxxxx選擇內(nèi)存中最近一段時間里較久未被訪問的頁面予以淘汰。性能接近最佳置換算法。根據(jù)程序局部性原理，那些剛被使用過的頁面，可能馬上還要被使用，而在較長時間里未被使用的頁面，可能不會馬上使用到。由于需要記錄頁面使用時間的先后關(guān)系，硬件開銷太大。4.7.2最近最久未使用(LRU)置換算法1.LRU置換算法的描述70770170122010320304403230321132201710701402432032102例：（同前例）利用LRU頁面置換算法時的置換圖：共發(fā)生9次頁面置換▲▲▲▲▲▲▲▲▲1)

寄存器為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為:R=Rn-1Rn-2Rn-3…R2R1R0

2.LRU置換算法的硬件支持

當(dāng)頁面被訪問時，對應(yīng)的寄存器的最左邊位置1；每隔時間t，將r寄存器右移一位；發(fā)生缺頁中斷時，找最小數(shù)值的r寄存器對應(yīng)的頁面淘汰。

某進(jìn)程具有8個頁面時的LRU訪問情況2)

棧用棧保存當(dāng)前使用頁面時棧的變化情況4474707407047170410174010741210742120741210742621076

用棧來保存當(dāng)前使用的各個頁面的頁面號，當(dāng)進(jìn)程訪問某頁面時，將該頁面的頁面號從棧中移出，壓入棧頂。因此棧頂始終是最新被訪問頁面的編號。

每頁有一個使用訪問位，將內(nèi)存中的所有頁面通過鏈接指針鏈接成一個循環(huán)隊列。若該頁被訪問則置訪問位=1。4.7.3Clock置換算法

也稱最近未使用算法(NRU,NotRecentlyUsed)，是一種最為流行、低開銷的LRU(最近最久未使用算法)近似算法。1.簡單的Clock置換算法

簡單Clock置換算法的流程和示例入口

查尋指針前進(jìn)一步，指向下一個表目頁面訪問位＝0?選擇該頁面淘汰是返回置頁面訪問位＝0否替換指針塊號頁號訪問位指針01240342156507112.改進(jìn)型Clock置換算法

首選置換頁面：既是未使用過的頁面；又是未修改的頁面。由訪問位A和修改位M可以組合成下面四種類型的頁面：

1類(A=0,M=0)：表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。

2類(A=0,M=1)：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。

3類(A=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。

4類(A=1,M=1)：最近已被訪問且被修改，該頁可能再被訪問。具體執(zhí)行過程分成以下三步：(1)

從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊列，尋找A=0且M=0的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位A。(2)

如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。(3)

如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復(fù)0。然后重復(fù)第一步，如果仍失敗，必要時再重復(fù)第二步，此時就一定能找到被淘汰的頁。選擇到當(dāng)前時間為止被訪問次數(shù)最少的頁面被置換。為內(nèi)存中每頁設(shè)置一個移位寄存器，每次訪問某頁時將該移位寄存器最高位置1，每隔一定時間右移一次。使用最少的頁面即為∑Ri最小的頁。（頁面訪問圖同LRU置換算法）會出現(xiàn)的問題：不能真正反映頁面的使用情況。4.7.4其它置換算法1.最少使用(LFU)置換算法2.頁面緩沖算法(PBA)它是對FIFO算法的發(fā)展，通過被置換頁面的緩沖，有機會找回剛被置換的頁面；被置換頁面的選擇和處理：用FIFO算法選擇被置換頁，把被置換的頁面放入兩個鏈表之一：如果頁面未被修改，就將其歸入到空閑頁面鏈表的末尾；否則將其歸入到已修改頁面鏈表。需要調(diào)入新的物理頁面時，將新頁面內(nèi)容讀入到空閑頁面鏈表的第一項所指的頁面，然后將第一項刪除?？臻e頁面和已修改頁面，仍停留在內(nèi)存中一段時間，如果這些頁面被再次訪問，只需較小開銷，而被訪問的頁面可以返還作為進(jìn)程的內(nèi)存頁。當(dāng)已修改頁面達(dá)到一定數(shù)目后，再將它們一起調(diào)出到外存，然后將它們歸入空閑頁面鏈表，這樣能大大減少I/O操作的次數(shù)。缺頁率的計算：缺頁率=缺頁次數(shù)/訪問串的訪問次數(shù)思考題：

某程序在內(nèi)存中分配3塊內(nèi)存，初始為空，訪問頁的走向為2，3，2，1，5，2，4，5，3，2，5，2，用FIFO和LRU算法分別計算缺頁次數(shù)和缺頁率。FIFO232152453252頁1233152443352頁222315224435頁3231552243xx

xxxx

x

xx共缺頁中斷9次，缺頁率：9/