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