【正文】 分區(qū)的低地址 a裝入到低界限寄存器中 ， 把第 1分區(qū)的高地址 b裝入到高界限寄存器中 。 作業(yè) 1運(yùn)行時(shí) ，硬件會(huì)自動(dòng)檢測(cè)指令中的地址 ， 如果超出 a或 b， 那么就產(chǎn)生出錯(cuò)中斷 ， 從而限定作業(yè) 1只在自己的區(qū)域里運(yùn)行 。 可變分區(qū)存儲(chǔ)管理 可變分區(qū)存儲(chǔ)管理的基本思想 固定分區(qū)存儲(chǔ)管理中的 “ 固定 ” 有兩層含義 ， 一是分區(qū)數(shù)目固定 ， 一是每個(gè)分區(qū)的尺寸固定 。 采用這種內(nèi)存管理技術(shù)時(shí) ， 分配出去的分區(qū)總可能會(huì)有一部分成為內(nèi)部碎片而浪費(fèi)掉 。 究其原因 ， 是因?yàn)檫M(jìn)入分區(qū)的作業(yè)大小 ， 不可能剛好等于該分區(qū)的尺寸 。 那么能否不事先劃分好分區(qū) ， 而是按照進(jìn)入作業(yè)的相對(duì)地址空間的大小來(lái)分配存儲(chǔ) ， 從而避免固定式分區(qū)所產(chǎn)生的存儲(chǔ)浪費(fèi) ， 這實(shí)際上就是可變分區(qū)存儲(chǔ)管理考慮問(wèn)題的出發(fā)點(diǎn) 。 可變分區(qū)存儲(chǔ)管理的基本思想是：在作業(yè)要求裝入內(nèi)存儲(chǔ)器時(shí)，如果當(dāng)時(shí)內(nèi)存儲(chǔ)器中有足夠的存儲(chǔ)空間滿(mǎn)足該作業(yè)的需求，那么就劃分出一個(gè)與作業(yè)相對(duì)地址空間同樣大小的分區(qū)分配給它。 圖 37是可變分區(qū)存儲(chǔ)管理思想的示意圖。圖 37(a)是系統(tǒng)維持的后備作業(yè)隊(duì)列，作業(yè) A需要內(nèi)存 15KB，作業(yè) B需要 20KB，作業(yè) C需要 10KB，等等；圖 37(b)表示系統(tǒng)初啟時(shí)的情形，整個(gè)系統(tǒng)里因?yàn)闆](méi)有作業(yè)運(yùn)行，因此用戶(hù)區(qū)就是一個(gè)空閑分區(qū)；圖 37(c)表示將作業(yè) A裝入內(nèi)存時(shí)，為它劃分了一個(gè)分區(qū)，尺寸為 15KB，此時(shí)的用戶(hù)區(qū)被分為兩個(gè)分區(qū)，一個(gè)是已經(jīng)分配的，一個(gè)是空閑區(qū)；圖 37(d)表示將作業(yè) B裝入內(nèi)存時(shí)，為它劃分了一個(gè)分區(qū)，尺寸為 20KB，此時(shí)的用戶(hù)區(qū)被分為三個(gè)分區(qū)；圖 37(e) 表示將作業(yè) C裝入內(nèi)存時(shí)，為它劃分了一個(gè)分區(qū)，尺寸為 10KB，此時(shí)的用戶(hù)區(qū)被分為四個(gè)分區(qū)。由此可見(jiàn)，可變分區(qū)存儲(chǔ)管理中的“可變”也有兩層含義，一是分區(qū)的數(shù)目隨進(jìn)入作業(yè)的多少可變，一是分區(qū)的邊界劃分隨作業(yè)的需求可變。 由于實(shí)施可變分區(qū)存儲(chǔ)管理時(shí) ， 分區(qū)的劃分是按照進(jìn)入作業(yè)的尺寸進(jìn)行的 ， 因此在這個(gè)分區(qū)里不會(huì)出現(xiàn)內(nèi)部碎片 。 這就是說(shuō) ， 可變分區(qū)存儲(chǔ)管理消滅了內(nèi)部碎片 ， 不會(huì)出現(xiàn)由于內(nèi)部碎片而引起的存儲(chǔ)浪費(fèi)現(xiàn)象 。 但是 ， 為了克服內(nèi)部碎片而提出的可變分區(qū)存儲(chǔ)管理模式 ， 卻引發(fā)了很多新的問(wèn)題 。 只有很好地解決這些問(wèn)題 ， 可變分區(qū)存儲(chǔ)管理才能真正得以實(shí)現(xiàn) 。 下面我們通過(guò)圖 38來(lái)看一下可變分區(qū)存儲(chǔ)管理的工作過(guò)程 ， 歸納出需要解決的一些技術(shù)問(wèn)題 。 假定有作業(yè)請(qǐng)求序列：作業(yè) A需要存儲(chǔ) 16KB，作業(yè) B需要存儲(chǔ) 100KB，作業(yè) C需要存儲(chǔ) 70KB，作業(yè) D需要存儲(chǔ) 75KB，等等。內(nèi)存儲(chǔ)器共 256KB，操作系統(tǒng)占用 20KB，系統(tǒng)最初有空閑區(qū) 236KB，如圖 38(a)所示。下面著重討論 236KB空閑區(qū)的變化。作業(yè) A到達(dá)后，按照它的存儲(chǔ)要求，劃分一個(gè) 16KB大小的分區(qū)分配給它，于是出現(xiàn)兩個(gè)分區(qū)，一個(gè)已經(jīng)分配，一個(gè)為空閑，如圖 38(b)所示。作業(yè) B到達(dá)后，按照它的存儲(chǔ)要求，劃分一個(gè) 100KB大小的分區(qū)分配給它，于是出現(xiàn)三個(gè)分區(qū)，兩個(gè)已經(jīng)分配，一個(gè)為空閑，如圖 38 (c)所示。緊接著為作業(yè) C劃分一個(gè)分區(qū)，從而形成四個(gè)分區(qū)，三個(gè)已經(jīng)分配，一個(gè)空閑，如圖 38(d)所示。 當(dāng)作業(yè) D到達(dá)時(shí)，由于系統(tǒng)內(nèi)只有 50KB的空閑區(qū)，不夠 D的需求，因此作業(yè) D暫時(shí)無(wú)法進(jìn)入。如果這時(shí)作業(yè)B運(yùn)行完畢，釋放它所占用的 100KB存儲(chǔ)量，這時(shí)系統(tǒng)中雖然仍保持為四個(gè)分區(qū)，但有的分區(qū)的性質(zhì)已經(jīng)改變，成為兩個(gè)已分配，兩個(gè)空閑，如圖 38(e)所示。由于作業(yè) B釋放的分區(qū)有 100KB大，可以滿(mǎn)足作業(yè) D的需要，因此系統(tǒng)在 36KB~136KB的空閑區(qū)中劃分出一個(gè)75KB的分區(qū)給作業(yè) D使用。這樣 36KB~136KB分區(qū)被分為兩個(gè)分區(qū)，一個(gè)分配出去（ 36KB~111KB），一個(gè)仍為空閑（ 111KB~136KB），如圖 38 (f)所示。這樣，總共有五個(gè)分區(qū)：三個(gè)已經(jīng)分配，兩個(gè)空閑。 地址的動(dòng)態(tài)重定位 圖 39是對(duì)動(dòng)態(tài)重定位過(guò)程的一個(gè)描述 。 這里仍沿用圖 31的信息 。 現(xiàn)在為了對(duì)圖 39(a)中的用戶(hù)作業(yè) A實(shí)行可變分區(qū)存儲(chǔ)管理 ， 假定按照當(dāng)前內(nèi)存儲(chǔ)器的分配情況 ， 把它原封不動(dòng)地裝入到 22KB~25KB的分區(qū)里面 ?？梢钥吹?， 在其絕對(duì)地址空間里 ， 位于 22KB+3000單元處的指令仍然是 “ call 100”， 未對(duì)它做任何的修改 。如果現(xiàn)在調(diào)度到該作業(yè)運(yùn)行 ， 操作系統(tǒng)就把它所占用的分區(qū)的起始地址 22KB裝入到定位寄存器中 ， 如圖 39(b)所示 。 當(dāng)執(zhí)行到位于單元 22KB+3000中的指令“ call 100”時(shí) ， 硬件的地址變換線路就把該指令中的地址 100取出來(lái) ， 與定位寄存器中的 22KB相加 ， 形成絕對(duì)地址 22628（ =22KB+100） 。 然后就按照這個(gè)地址去執(zhí)行 call指令 。 于是 ， 程序就正確轉(zhuǎn)移到 22628的子程序處去執(zhí)行了 。 空閑區(qū)的合并 在可變分區(qū)存儲(chǔ)管理中實(shí)行地址的動(dòng)態(tài)重定位后 ，用戶(hù)程序就不會(huì)被 “ 釘死 ” 在分配給自己的存儲(chǔ)分區(qū)中 。 必要時(shí) ， 它可以在內(nèi)存中移動(dòng) ， 為空閑區(qū)的合并帶來(lái)了便利 。 內(nèi)存區(qū)域中的一個(gè)分區(qū)被釋放時(shí) ， 與它前后相鄰接的分區(qū)可能會(huì)有四種關(guān)系出現(xiàn) ， 如圖 310所示 。 在圖中 ， 我們做這樣的約定：位于一個(gè)分區(qū)上面的分區(qū) ，稱(chēng)為它的 “ 前鄰接 ” 分區(qū) ， 一個(gè)分區(qū)下面的分區(qū) ， 稱(chēng)為它的 “ 后鄰接 ” 分區(qū) 。 （ 1）圖 310(a)表示釋放區(qū)的前鄰接分區(qū)和后鄰接分區(qū)都是已分配區(qū)，因此沒(méi)有合并的問(wèn)題存在。此時(shí)釋放區(qū)自己形成一個(gè)新的空閑區(qū)，該空閑區(qū)的起始地址就是該釋放區(qū)的起始地址，長(zhǎng)度就是該釋放區(qū)的長(zhǎng)度。 （ 2）圖 310(b)表示釋放區(qū)的前鄰接分區(qū)是一個(gè)空閑區(qū)，后鄰接分區(qū)是一個(gè)已分配區(qū)，因此，釋放區(qū)應(yīng)該和前鄰接的空閑區(qū)合并成為一個(gè)新的空閑區(qū)。這個(gè)新空閑區(qū)的起始地址是原前鄰接空閑區(qū)的起始地址，長(zhǎng)度是這兩個(gè)合并分區(qū)的長(zhǎng)度之和。 （ 3）圖 310(c) 表示釋放區(qū)的前鄰接分區(qū)是一個(gè)分配區(qū)，后鄰接分區(qū)是一個(gè)空閑區(qū)，因此，釋放區(qū)應(yīng)該和后鄰接的空閑區(qū)合并成為一個(gè)新的空閑區(qū)。這個(gè)新空閑區(qū)的起始地址是該釋放區(qū)的起始地址，長(zhǎng)度是這兩個(gè)合并分區(qū)的長(zhǎng)度之和。 （ 4）圖 310(d) 表示釋放區(qū)的前鄰接分區(qū)和后鄰接分區(qū)都是一個(gè)空閑區(qū)，因此，釋放區(qū)應(yīng)該和前、后兩個(gè)鄰接的空閑區(qū)合并成為一個(gè)新的空閑區(qū)。這個(gè)新空閑區(qū)的起始地址是原前鄰接空閑區(qū)的起始地址，長(zhǎng)度是這三個(gè)合并分區(qū)的長(zhǎng)度之和。 空閑分區(qū)的合并 ， 有時(shí)也被稱(chēng)為 “ 存儲(chǔ)緊湊 ” 。何時(shí)進(jìn)行合并 ， 操作系統(tǒng)可以有兩種時(shí)機(jī)的選擇方案：一是調(diào)度到某個(gè)作業(yè)時(shí) ， 當(dāng)時(shí)系統(tǒng)中的每一個(gè)空閑分區(qū)尺寸都比它所需要的存儲(chǔ)量小 ， 但空閑區(qū)的總存儲(chǔ)量卻大于它的存儲(chǔ)請(qǐng)求 ， 于是就進(jìn)行空閑存儲(chǔ)分區(qū)的合并 ， 以便能夠得到一個(gè)大的空閑分區(qū) ， 滿(mǎn)足該作業(yè)的存儲(chǔ)需要；另一是只要有作業(yè)運(yùn)行完畢歸還它所占用的存儲(chǔ)分區(qū) ， 系統(tǒng)就進(jìn)行空閑分區(qū)的合并 。 比較這兩種方案可以看出 ， 前者要花費(fèi)較多的精力去管理空閑區(qū) ， 但空閑區(qū)合并的頻率低 ， 系統(tǒng)在合并上的開(kāi)銷(xiāo)少；后者總是在系統(tǒng)里保持一個(gè)大的空閑分區(qū) ， 因此對(duì)空閑分區(qū)談不上更多的管理 ， 但是空閑區(qū)合并的頻率高 ， 系統(tǒng)在這上面的開(kāi)銷(xiāo)大 。 分區(qū)的管理與組織方式 采用可變分區(qū)方式管理內(nèi)存儲(chǔ)器時(shí) ， 內(nèi)存中有兩類(lèi)性質(zhì)的分區(qū)：一類(lèi)是已經(jīng)分配給用戶(hù)使用的 “ 已分配區(qū) ” ， 另一類(lèi)是可以分配給用戶(hù)使用的 “ 空閑區(qū) ” 。隨著時(shí)間的推移 ， 它們的數(shù)目在不斷地變化著 。 如何知道哪個(gè)分區(qū)是已分配的 ， 哪個(gè)分區(qū)是空閑的 ， 如何知道各個(gè)分區(qū)的尺寸是多少 ， 這就是分區(qū)管理所要解決的問(wèn)題 。 對(duì)分區(qū)的管理 ， 常用的方式有三種：表格法 、 單鏈表法和雙鏈表法 。 下面逐一介紹它們各自的實(shí)現(xiàn)技術(shù) 。 1．表格法 為了記錄內(nèi)存中現(xiàn)有的分區(qū)以及各分區(qū)的類(lèi)型，操作系統(tǒng)設(shè)置兩張表格，一張為“已分配表”，一張為“空閑區(qū)表”，如圖 311(b)和 311 (c)所示。表格中的“序號(hào)”是表目項(xiàng)的順序號(hào)，“起始地址”、“尺寸”和“狀態(tài)”都是該分區(qū)的相應(yīng)屬性。由于系統(tǒng)中分區(qū)的數(shù)目是變化的，因此每張表格中的表目項(xiàng)數(shù)要足夠的多，暫時(shí)不用的表目項(xiàng)的狀態(tài)被設(shè)為“空”。 假定圖 311(a)為當(dāng)前內(nèi)存中的分區(qū)使用情況 ， 那么圖 311(b)記錄了已分配區(qū)的情形 ， 圖 311(c)記錄了空閑區(qū)的情形 。 當(dāng)作業(yè)進(jìn)入而提出存儲(chǔ)需求時(shí) ， 就去查空閑區(qū)表里狀態(tài)為 “ 空閑 ” 的表目項(xiàng) 。 如果該項(xiàng)的尺寸能滿(mǎn)足所求 ， 那么就將它一分為二：分配出去的那一部分在已分配表中找一個(gè)狀態(tài)為 “ 空 ” 的表目項(xiàng)進(jìn)行登記 ， 剩下的部分 （ 如果有的話(huà) ） 仍在空閑區(qū)表中占據(jù)一個(gè)表目項(xiàng) 。 如果有一個(gè)作業(yè)運(yùn)行結(jié)束 ， 則根據(jù)作業(yè)名到已分配表中找到它的表目項(xiàng) ， 將該項(xiàng)的“ 狀態(tài) ” 改為 “ 空 ” ， 隨之在空閑區(qū)表中尋找一個(gè)狀態(tài)為 “ 空 ” 的表目項(xiàng) ， 把釋放分區(qū)的信息填入 ， 并將表目項(xiàng)狀態(tài)改為 “ 空閑 ” 。 當(dāng)然 ， 這時(shí)可能還會(huì)進(jìn)行空閑區(qū)的合并工作 。 2． 單鏈表法 把內(nèi)存儲(chǔ)器中的每個(gè)空閑分區(qū)視為一個(gè)整體 ， 在它的里面開(kāi)辟出兩個(gè)單元 ， 一個(gè)用于存放該分區(qū)的長(zhǎng)度 （ size） ， 一個(gè)用于存放它下一個(gè)空閑分區(qū)的起始地址 （ next） ， 如圖 314(a)所示 。 操作系統(tǒng)開(kāi)辟一個(gè)單元 ， 存放第 1個(gè)空閑分區(qū)的起始地址 ， 這個(gè)單元被稱(chēng)為“ 鏈?zhǔn)字羔?” 。 最后一個(gè)空閑分區(qū)的 next中存放標(biāo)志“ NULL”表明它是最后一個(gè) 。 這樣一來(lái) ， 系統(tǒng)中的所有空閑分區(qū)被連接成為一個(gè)鏈表 。 從鏈?zhǔn)字羔槼霭l(fā) ，順著各個(gè)空閑分區(qū)的 next往下走 ， 就能到達(dá)每一個(gè)空閑分區(qū) 。 圖 314(b)所反映的是圖 311(a)當(dāng)前內(nèi)存儲(chǔ)器中空閑區(qū)的鏈表 。 為了看得更加清楚 ， 有時(shí)也把這些空閑區(qū)抽出來(lái) ， 單獨(dú)畫(huà)出它們形成的鏈表 ， 如圖 314(c)所示 。 用空閑區(qū)鏈表管理空閑區(qū)時(shí) ， 對(duì)于提出的任何一個(gè)請(qǐng)求 ， 都順著空閑區(qū)鏈表首指針開(kāi)始查看一個(gè)一個(gè)空閑區(qū) 。 如果第 1個(gè)分區(qū)不能滿(mǎn)足要求 ， 就通過(guò)它的next找到第 2個(gè)空閑區(qū) 。 如果一個(gè)空閑區(qū)的 next是NULL， 那么就表示系統(tǒng)暫時(shí)無(wú)法滿(mǎn)足該作業(yè)這一次所提出的存儲(chǔ)請(qǐng)求 。 在用這種方式管理存儲(chǔ)器時(shí) ， 無(wú)論分配存儲(chǔ)分區(qū)還是釋放存儲(chǔ)分區(qū) ， 都要涉及到 next（ 指針 ） 的調(diào)整 。 3．雙鏈表法 如前所述，當(dāng)一個(gè)已分配區(qū)被釋放時(shí)，有可能和與它相鄰接的分區(qū)進(jìn)行合并。為了尋找釋放區(qū)前、后的空閑區(qū)，以利于判別它們是否與釋放區(qū)直接鄰接，可以把空閑區(qū)的單鏈表改為雙向鏈表。也就是說(shuō)，在圖 314(a)所表示的每個(gè)空閑分區(qū)中，除了存放下一個(gè)空閑區(qū)起址 next外，還存放它的上一個(gè)空閑區(qū)起址（ prior）的信息，如圖 315(a)所示。這樣，通過(guò)空閑區(qū)的雙向鏈表，就可以方便地由 next找到一個(gè)空閑區(qū)的下一個(gè)空閑區(qū)，也可以由 prior找到一個(gè)空閑區(qū)的上一個(gè)空閑區(qū)。 比如，在把一個(gè)釋放區(qū)鏈入空閑區(qū)雙向鏈表時(shí)，如果通過(guò)它的 prior發(fā)現(xiàn)，在該鏈表中釋放區(qū)的前面一個(gè)空閑區(qū)的起始地址加上長(zhǎng)度，正好等于釋放區(qū)的起始地址，那么說(shuō)明是屬于圖 310(b)的情形，即它前面的空閑區(qū)與它直接相鄰接，應(yīng)該把這個(gè)釋放區(qū)與原來(lái)的空閑區(qū)合并。另外，如果釋放區(qū)起始地址加上長(zhǎng)度正好等于 next所指的下一個(gè)空閑區(qū)的起始地址，那么說(shuō)明是屬于圖 310(c)的情形，即它后面的空閑區(qū)與它直接相鄰接，應(yīng)該把這個(gè)釋放區(qū)與原來(lái)的空閑區(qū)合并。如同單鏈表一樣，在利用雙向鏈表管理存儲(chǔ)空閑分區(qū)時(shí)，無(wú)論分配存儲(chǔ)分區(qū)還是釋放存儲(chǔ)分區(qū)，都要涉及到 next和 prior兩個(gè)指針的調(diào)整。圖 315(b)是圖 311(a)的雙向鏈表形式。 空閑分區(qū)的分配算法 當(dāng)系統(tǒng)中有多個(gè)空閑的存儲(chǔ)分區(qū)能夠滿(mǎn)足作業(yè)提出的存儲(chǔ)請(qǐng)求時(shí) ， 究竟將誰(shuí)分配出去 ， 這屬于分配算法問(wèn)題 。 在可變分區(qū)存儲(chǔ)管理中 ， 常用的分區(qū)分配算法有：最先適應(yīng)算法 、 最佳適應(yīng)算法以及最壞適應(yīng)算法 。 下面分別介紹它們的含義 。 1．最先適應(yīng)算法 實(shí)行這種分配算法時(shí)，總是把最先找到的、滿(mǎn)足存儲(chǔ)需求的那個(gè)空閑分區(qū)作為分配的對(duì)象。這種方案的出發(fā)點(diǎn)是盡量減少查找時(shí)間，它實(shí)現(xiàn)簡(jiǎn)單，但有可能把大的空閑分區(qū)分割成許多小的分區(qū)，因此對(duì)大作業(yè)不利。 2．最佳適應(yīng)算法 實(shí)行這種分配算法時(shí)，總是從當(dāng)前所有空閑區(qū)中找出一個(gè)能夠滿(mǎn)足存儲(chǔ)需求的、最小的空閑分區(qū)作為分配的對(duì)象。這種方案的出發(fā)點(diǎn)是盡可能地不把大的空閑區(qū)分割成為小的分區(qū)，以保證大作業(yè)的需要。該算法實(shí)現(xiàn)起來(lái)比較費(fèi)時(shí)，麻煩。 3．最壞適應(yīng)算法 實(shí)行這種分配算法時(shí)，總是從當(dāng)前所有空閑區(qū)中找出一個(gè)能夠滿(mǎn)足存儲(chǔ)需求的、最大的空閑分區(qū)作為分配的對(duì)象?？梢钥闯觯@種方案的出發(fā)點(diǎn)是照顧中、小作業(yè)的需求。