【文章內(nèi)容簡介】 該算法，應(yīng)設(shè)置起始查尋指針，以指示下一次起始的查尋的空閑區(qū)，并采用循 環(huán)查找方式，即如果最后一個 (鏈尾 )空閑區(qū)的大小仍然 能滿足要求，應(yīng)返回到第一個空 閑區(qū)，比較其大小是否滿足要求， 找到后應(yīng)立即調(diào)整起始查尋指針。這種算法能使內(nèi)存的 空閑區(qū)分布地更均勻，減少了查找空閑區(qū)的開銷，但這會缺乏大的空閑區(qū)。 (3) 最佳適應(yīng)算法。采用這種算法要求可用分區(qū)表或自由鏈表按照空閑區(qū)從小到大的 次序排列。當(dāng)用戶作業(yè)申請一個空閑區(qū)時，存儲器管理程序就從可用分區(qū)表或自由鏈表的 頭部開始查找，當(dāng)找到第一個滿足條件的空閑區(qū)時，停止查找，進行存儲區(qū)的分配。 采用這種算法的優(yōu)點是從空閑區(qū)中挑選一個能滿足作業(yè)要求的最小分區(qū)，避免了 大 材小用 。孤立地看，最佳適應(yīng)算法似乎是最佳的，事實上這種算法也存在缺 點，那就是 由于空閑區(qū)通常 可能正好和作業(yè)所要求的大小相等，因而要將其分割成兩部分，這往往 使剩下的空閑區(qū)非常小而成為 碎片 ，以至幾乎無法使用。隨著系統(tǒng)的運行，這種小空 閑區(qū)也逐步增多，造成了內(nèi)存空間的浪費。故有些系統(tǒng)往往還采用與之相反的分配算法， 即最壞適應(yīng)法。 ?82 第 4 章 存儲器管理 ?83 (4) 最壞適應(yīng)法是把一個作業(yè)分配到內(nèi)存中最大的空閑區(qū)中。采用這種算法要求可用 分區(qū)表或自由鏈表按照空閑區(qū)從大到小的次序排列。當(dāng)用戶進程申請一個空閑區(qū)時，存儲 管理系統(tǒng)分析可用分區(qū)表或自由鏈表中的第一個空閑區(qū)是否滿足用戶的作業(yè)要求，若滿足 要求，則將第一個空閑區(qū)分配給它，否則分配失敗。 這種算法看起來是最差的算法，因為它總是將最大的空閑區(qū)來滿足用戶的要求。但是 經(jīng)過分析后發(fā)現(xiàn)，最壞 適應(yīng)算法也具有實用價值。其原因是：在大空閑區(qū)中裝入作業(yè)后， 剩下的空閑區(qū)往往也很大而 至于是 碎片 ，于是也能滿足以后較大的作業(yè)要求。該算 法對中、小作業(yè)的運行是很有利的。 以上介紹的是有關(guān)動態(tài)分區(qū)的分配問題，對應(yīng)分配的問題就是回收與合并問題。 當(dāng)用戶作業(yè)和進程執(zhí)行結(jié)束時，存儲管理程序要回收使用完畢的空閑區(qū)，并將其插入 到空閑區(qū)可用表或自由鏈表中。在回收的過程中，需要對回收的空閑區(qū)進行合并。因為如 果 對空閑區(qū)進行合并，則會由于每個作業(yè)或進程所要求的內(nèi)存長度 一樣而形成大量分 散的較小的空閑區(qū)，從而造成大量內(nèi)存的浪費。所以需要對小的空閑區(qū)要盡可能多地進行 合并，以便形成能夠滿足作業(yè)需求的大的空閑區(qū)。將一個被釋放的空閑區(qū)插入空閑區(qū)可用 分區(qū)表或自由鏈表中時，會出現(xiàn) 4 種合并情況。 (1) 釋放區(qū)與上下兩個空閑區(qū)相鄰。在這種情況下，將 3 個空閑區(qū)合并為一個空閑區(qū)。 新空閑區(qū)起始地址為上空閑區(qū)的起始地址，大小為 3 個空閑區(qū)之和。同時，修改可用分區(qū) 表或自由鏈中的表項目。 (2) 釋放區(qū)與上空閑區(qū)相鄰。在這種情況下，將釋放區(qū)與上空閑區(qū)合并為一個空閑區(qū)， 其起始地 址為上空閑區(qū)的起始地址，大小為釋放區(qū)和上空閑區(qū)之和。同時，修改可用分區(qū) 表或自由鏈表中的表項目。 (3) 釋放區(qū)與下空閑區(qū)相鄰。在這種情況下，將釋放區(qū)與下空閑區(qū)合并為一個空閑區(qū)， 其起始地址為釋放區(qū)的起始地址，大小為釋放區(qū)和下空閑區(qū)之和。同時，修改可用分區(qū)表 或自由鏈表中的表項目。 (4) 釋放區(qū)與上下兩個空閑區(qū)都 相鄰。在這種情況下，釋放區(qū)作為一個新的空閑可 用區(qū)插入到可用分區(qū)表或自由鏈中。 3. 動態(tài)分區(qū)地址轉(zhuǎn)換 靜態(tài)重定位和動態(tài)重定位技術(shù)，都可以用完成分區(qū)內(nèi)存管理的地址轉(zhuǎn)換 ，但是由于動 態(tài)分區(qū)時，分區(qū)的大小 固定，有時因系統(tǒng)內(nèi)存中有過多的小的空閑區(qū)，操作系統(tǒng)會整理 內(nèi)存空間，將小的空閑區(qū)合并而移動內(nèi)存中的程序和數(shù)據(jù)。因此，對動態(tài)分區(qū)方式應(yīng)采用 動態(tài)重定位裝入作業(yè)，當(dāng)作業(yè)執(zhí)行時由硬件地址轉(zhuǎn)換機構(gòu)完成地址轉(zhuǎn)換。 4. 分區(qū)的共享和保護 在分區(qū)管理方式中，如果每個作業(yè)只能占用一個分區(qū)，那么就 允許各道作業(yè)存在公 共的共享區(qū)域。這樣，當(dāng)幾道作業(yè)都要使用某個例行程序時就只好在各自的存儲區(qū)域內(nèi)各 放一套了，這種方式顯然降低了內(nèi)存的使用效率。所以有些計算機系統(tǒng)提 供了多對基址 / 限長寄存器，允許一個作業(yè)占用多個分區(qū)。系統(tǒng)可以規(guī)定某對基址 /限長寄存器限定的區(qū)域 是共享的，用來存放共享的程序和常數(shù)。對共享區(qū)的信息也必須規(guī)定只能執(zhí)行或讀出，而 能寫入，若某作業(yè)要想往該共享區(qū)域?qū)懭胄畔r，則將遭到系統(tǒng)的拒絕，并產(chǎn)生保護中 ?83 ?84 計算機操作系統(tǒng)原理教程與實訓(xùn) 斷。因此，幾道作業(yè)共享的例行程序或數(shù)據(jù)就可存放在一個共享的分區(qū)中，只要讓各道作 業(yè)的共享存儲區(qū)域部分有相同的基址 /限長址，就可實現(xiàn)分區(qū)共享。 分區(qū)管理下采用的保護機制通常有上下界寄存器法、基址寄存器法和保護鍵法，這些 方法在前面已介紹，這里 作贅述。 5. 分區(qū)存儲管理的優(yōu)缺點 優(yōu)點主要有如下幾點。 (1) 實現(xiàn)了多道程序設(shè)計，從而提高了系統(tǒng)資源的利用率。 (2) 系統(tǒng)要求的硬件支 少，管理簡單，實現(xiàn)容易。 缺點主要如下。 (1) 必須給作業(yè)分配一組連續(xù)的內(nèi)存區(qū)域。 (2) 碎片 問題嚴重，內(nèi)存仍 能得到充分利用。 (3) 內(nèi)存的擴充只能采用覆蓋與交換技術(shù)，無法真正實現(xiàn)虛擬存儲。 頁式存儲管理 盡管分區(qū)管理從實現(xiàn)方法來看比較簡單，但由于該管理方式要求作業(yè)占用內(nèi)存的一組 連續(xù)的存儲單元，這樣會導(dǎo)致整個計算機存儲系統(tǒng)出現(xiàn)系列問題。首先，當(dāng)連續(xù)空閑區(qū) 能滿足進程的要求時，即使系統(tǒng)中所有空閑區(qū)之和大于進程對內(nèi)存的要求，也仍然 能裝 入進程；其次，在動態(tài)分區(qū)的存儲空間中，常常由于存在著一些 足以裝入任何作業(yè)的小 的分區(qū)而浪費掉部分存儲資源，這就是所謂的存儲器的 碎片 問題。盡管采用一些技術(shù) 可以解決這個問題，但要為移動大量信息花去 少處理機時間，代價較高。如果我們能取 消作業(yè)對其存儲區(qū)域的連續(xù)性要求，必然會進一步提高內(nèi)存空間的利用率，又無需為移動 信息付出代價?；谶@一指導(dǎo)思想，產(chǎn)生了離散存儲管理方式。如果離散分配的基本單位 是頁，則稱為分頁式存儲管理；如果離散分配的基本單位是段，則稱為分段存儲管理 方式。 頁式管理的基本原理 頁式存儲管理取消了存儲分配的連續(xù)性，它能夠?qū)⒂脩暨M程分配到 連續(xù)的存儲單元 中連續(xù)執(zhí)行。 頁式存儲管理系統(tǒng)中，在系統(tǒng)初始化時把每個作業(yè)的地址空間分成一些大小相等的塊， 稱之為頁 (Page)。所有的頁從 0開始依次有一個頁號。頁的大小通常在 1KB～ 4KB 范圍 內(nèi)，但是，頁的大小總是 2 的整數(shù)次冪。經(jīng)過頁的劃分之后，進程的虛擬地址變?yōu)轫撎? P 與頁內(nèi)位移量即頁內(nèi)地址 W 所組成。如圖 中的地址長度為 24 位，其中 0～ 9 位 為頁內(nèi)地 址，從這個地址結(jié)構(gòu)可以知道，頁面的大小為 1024 字節(jié) (1K)，其地址空間最多可有 16K 頁。 23 ? ? 10 9 ? ? 2 1 0 頁號 P 圖 頁內(nèi)地址 W 分頁系統(tǒng)的地址結(jié)構(gòu) ?84 第 4 章 存儲器管理 ?85 除了把作業(yè)或進程的虛擬空間劃分為大小相等的頁之外，頁式管理還把內(nèi)存空間以與 頁相等的大小劃分為若干個物理塊，這些物理塊稱為頁面 (Page Frame)或頁楨、頁框。每個 頁面也從 0開始依次編址。這些塊為系統(tǒng)中的任一進程所共享 (除去操作系統(tǒng)區(qū)外 )。分 頁管理時，系統(tǒng)以頁為單位為用戶進程分配頁面，每個頁面之間可以 再連續(xù)，從而取消 了存儲分配的連續(xù)性。 與分區(qū)管理相比，頁式管理 方式的優(yōu)越性主要體現(xiàn)在以下兩個方面。 (1) 實現(xiàn)了連續(xù)存儲到非連續(xù)存儲的飛躍，為實現(xiàn)虛擬存儲打下了基礎(chǔ)。 (2) 解決了內(nèi)存中的 碎片 問題，因為從分配思想上看已 存在 可利用空閑的頁 面，盡管每個進程的最后一頁 一定占滿整個頁面。這部分未占滿頁面的存儲區(qū)域稱為 頁內(nèi)碎片 ，任意一個 頁內(nèi)碎片 都 會大于整個頁面的大小，從而提高了內(nèi)存的利 用率。 分頁存儲管理根據(jù)作業(yè)裝入內(nèi)存的時機 同，一般分為靜態(tài)頁式管理和動態(tài)頁式管理。 下面將具體介紹這些存儲管理方法。 靜態(tài)頁式管理 靜態(tài)頁式管理是指用戶作業(yè)在開始執(zhí)行以前，將該作業(yè)的程序和數(shù)據(jù)全部裝入到內(nèi)存 的各個頁面中，如果當(dāng)時頁面 (頁框、頁楨 )數(shù) 足，則該作業(yè)必須等待，系統(tǒng)再調(diào)度另外 的作業(yè)。 1. 頁式管理中所用的數(shù)據(jù)結(jié)構(gòu) 1) 頁表 頁表占用內(nèi)存的一塊固定的存儲區(qū)，它是在作業(yè)裝入內(nèi)存并創(chuàng)建其相應(yīng)進程時，由操 作系統(tǒng)根據(jù)內(nèi)存的分配情況建立的。頁表中需要兩個信息，一個是頁號，另一個是頁面號， 記錄著該進程的每個頁分配到內(nèi)存的哪些頁面中。顯然，每個進程至少擁有一張頁表， 這 個頁表記錄了進程的虛擬地址和內(nèi)存地址的映射關(guān)系。 2) 請求表 請求表就是用來確定作業(yè)或進程的虛擬地址空間的各頁表在內(nèi)存中的實際對應(yīng)位置。 當(dāng)系統(tǒng)有多個作業(yè)或進程時，系統(tǒng)必須知道每個作業(yè)或進程的頁表起始地址和長度，才能 進行內(nèi)存分配和地址變換。整個系統(tǒng)設(shè)置一張請求表，請求表的內(nèi)容包括：進程號、請求 頁面數(shù)、頁表始址、頁表長度和狀態(tài)等，如表 42 所示。 3) 存儲頁面表 為了描述內(nèi)存空間的分配情況，系統(tǒng)設(shè)置一張存儲頁面表。存儲頁面表指出了內(nèi)存各 頁面是否已被分配，以及未被分配的頁 面總數(shù)。存儲頁面表的形式有兩種：一種是在內(nèi)存 中劃分出一個固定的區(qū)域，該區(qū)域中每個單元的每個位表示一個頁面的使用狀態(tài)，若該位 為 1，代表所對應(yīng)的頁面已分配，若該位為 0，代表所對應(yīng)的頁面空閑。這種存儲頁面表稱 為位示圖，如圖 所示。 ?85 ?86 計算機操作系統(tǒng)原理教程與實訓(xùn) 表 4 2 請求表 進 程 號 請求頁面數(shù) 1 2 3 ? 20 30 21 ? 頁 表 始 址 1 024 1 044 頁 表 長 度 20 30 ? ? 狀 已分配 已分配 未分配 ? 態(tài) 0 0 0 1 2 1 0 0 3 1 1 0 4 0 1 1 0 1 1 ? ? ? ? ? ? ? ? 27 1 0 1 28 1 1 1 29 0 1 0 30 1 1 1 31 1 0 0 圖 位示圖 位示圖要占用一部分內(nèi)存空間，一個劃分為 2 048 個頁面的主存，如內(nèi)存單元長度為 32 位，則位示圖就占據(jù) 2 048/32=64 個內(nèi)存單元。 存儲頁面表的另一種形式是采用空閑頁面鏈的方法。在空閑頁面鏈中，隊首頁面的第 一單元和第二單元分別存放空閑頁面的總數(shù)和指向下一個空閑頁面的指針，其他頁面的第 一單元則分別存放指向下一個空閑頁面的指針?？臻e頁面鏈的方法由于使用了空閑頁面本 身的存儲單元來存放空閑頁面鏈的指針，因此 占 據(jù)額外的主存空間，是一種較為經(jīng)濟的 存儲頁面表的組織法。 2. 靜態(tài)頁式管理中的分配與回收 靜態(tài)頁式管理的分配和回收非常方便。作業(yè)或進程分配頁面時，首先從請求表中查出 作業(yè)或進程所要求的頁面數(shù)。然后，由存儲頁面表檢查是否有足夠的空閑頁面，若沒有， 則本次無法分配。如果有，則分配并設(shè)置頁表，并填寫請求表中的相應(yīng)表項 (頁表始址、 頁表長度和狀態(tài) )，同時修改存儲頁面表將分配出去的頁面對應(yīng)的狀態(tài)設(shè)置為分配狀態(tài)。 頁面的回收算法也較為簡單，當(dāng)進程執(zhí)行完畢時，根據(jù)進程頁表中登記的頁面號，將 這些頁 面插入到存儲頁面表中，使之成為空閑頁面。最后，拆除該進程所對應(yīng)的頁表即可。 3. 頁式管理中的地址變換 靜態(tài)頁式管理的另一個關(guān)鍵問題是地址變換。地址變換機構(gòu)的基本任務(wù)，是利用頁表， 把用戶程序中的邏輯地址變換為內(nèi)存的物理地址。由于頁內(nèi)地址和物理地址是一一對應(yīng) 的， 需進行變換，因此，地址變換機構(gòu)的任務(wù)，實際上是將頁號變換為頁面號。頁式管 理中的地址變換過程全部由硬件地址變換機構(gòu)自動完成，采用的是動態(tài)重定位技術(shù)。 由于頁表駐留在內(nèi)存的某個固定區(qū)域中，而取數(shù)據(jù)或指令又必須經(jīng)過頁表變換才能 得 到實際的物理地址。因此，頁式管理中取一個數(shù)據(jù)或指令至少要訪問內(nèi)存兩次以上。一次 訪問頁表以確定所取數(shù)據(jù)或指令的物理地址，另一次是根據(jù)地址取數(shù)據(jù)或指令。這比通常 執(zhí)行指令的速度下降了一半。解決這