【文章內(nèi)容簡(jiǎn)介】 分頁式存儲(chǔ)管理 分頁式存儲(chǔ)管理的基本思想 如上所述 ， 可變分區(qū)存儲(chǔ)管理按照作業(yè)對(duì)存儲(chǔ)的需求量進(jìn)行分區(qū)的劃分 ， 因此它不出現(xiàn)內(nèi)部碎片 。 但由此會(huì)招致某些分區(qū)過小而無法滿足作業(yè)存儲(chǔ)請(qǐng)求的情形 ， 從而產(chǎn)生外部碎片 。 在那里 ， 解決外部碎片的辦法是通過移動(dòng)作業(yè)對(duì)空閑分區(qū)進(jìn)行合并 。 這不僅不方便 ， 還增加了系統(tǒng)的開銷 。 之所以要移動(dòng)內(nèi)存中的作業(yè)，主要是因?yàn)樵诖酥?，用戶作業(yè)必須被裝入一個(gè)連續(xù)的存儲(chǔ)區(qū)域，才能正確運(yùn)行。不移動(dòng)，就不能獲得大的空閑分區(qū)，就不能有一個(gè)大的連續(xù)分區(qū)分配給用戶作業(yè)使用。如果可以把用戶作業(yè)分散裝入到幾個(gè)不連續(xù)的分區(qū)里，仍然能保證它得到正確的運(yùn)行，那么就無須去移動(dòng)內(nèi)存中的作業(yè)了。分頁式存儲(chǔ)管理正是打破了這種“連續(xù)”的禁錮，把對(duì)存儲(chǔ)器的管理大大向前推進(jìn)了一步。 分頁式存儲(chǔ)管理是將固定式分區(qū)方法與動(dòng)態(tài)重定位技術(shù)結(jié)合在一起提出的一種存儲(chǔ)管理方案，它需要硬件的支持。其基本思想是：首先把整個(gè)內(nèi)存儲(chǔ)器劃分成大小相等的許多分區(qū)，每個(gè)分區(qū)稱為“塊”（這表明它具有固定分區(qū)的管理思想，只是這里的分區(qū)是定長(zhǎng)罷了）。比如把內(nèi)存儲(chǔ)器劃殖 n個(gè)分區(qū)，編號(hào)為0,1,2,…, n1。例如，在圖 317(a)中，內(nèi)存儲(chǔ)器總的容量為 256KB，操作系統(tǒng)要求 20KB。若塊的尺寸為 4KB，則共有 64塊，操作系統(tǒng)占用前 5塊，其他分配給用戶使用。在分頁式存儲(chǔ)管理中，塊是存儲(chǔ)分配的單位。 其次 ， 用戶作業(yè)仍然相對(duì)于 “ 0”進(jìn)行編址 ， 形成一個(gè)連續(xù)的相對(duì)地址空間 。 操作系統(tǒng)接受用戶的相對(duì)地址空間 ， 然后按照內(nèi)存塊的尺寸對(duì)該空間進(jìn)行劃分 。用戶程序相對(duì)地址空間中的每一個(gè)分區(qū)被稱為 “ 頁 ” ，編號(hào)從 0開始 ， 第 0頁 、 第 1頁 、 第 2頁 、 …… 。 比如 ，圖 317(b)中 ， 作業(yè) A的相對(duì)地址空間大小為 11KB。 按照 4KB來劃分 ， 它有 2頁多不到 3頁大小 ， 但把它作為 3頁來對(duì)待 ， 編號(hào)為第 0頁 、 第 1頁和第 2頁 。 這樣一來，用戶相對(duì)地址空間中的每一個(gè)相對(duì)地址，都可以用“頁號(hào)，頁內(nèi)位移”來表示。并且不難看出，數(shù)對(duì)（頁號(hào)，頁內(nèi)位移）與相對(duì)地址是一一對(duì)應(yīng)的。比如說，圖 317(b)中，相對(duì)地址 5188與數(shù)對(duì)（ 1，1092）相對(duì)應(yīng)，其中“ 1”是相對(duì)地址所在頁的頁號(hào)，而“ 1092”則是相對(duì)地址與所在頁起始位置（ 4KB=4096）之間的位移。又比如，相對(duì)地址 9200與數(shù)對(duì)（ 2， 108）相對(duì)應(yīng)，“ 2” 是相對(duì)地址所在頁的頁號(hào)，“ 108” 是相對(duì)地址與所在頁起始位置（ 8KB=8192）之間的位移。 有了這些準(zhǔn)備，如果能夠解決作業(yè)原封不動(dòng)地進(jìn)入不連續(xù)存儲(chǔ)塊后也能正常運(yùn)行的問題，那么分配存儲(chǔ)塊是很容易的事情，因?yàn)橹灰獌?nèi)存中有足夠多的空閑塊，那么作業(yè)中的某一頁進(jìn)入哪一塊都是可以的。比如圖 317(a)中，就把作業(yè) A裝入到了第 8塊、第 11塊和第 6塊這樣的三個(gè)不連續(xù)的存儲(chǔ)塊中。 下面以圖例來說明如何確保原封不動(dòng)地進(jìn)入不連續(xù)存儲(chǔ)塊后的作業(yè)能夠正常的運(yùn)行。假定塊的尺寸為1KB，作業(yè) A的相對(duì)地址空間為 3KB大小，在相對(duì)地址100處有一條調(diào)用子程序的指令 call，子程序的入口地址為 3000（當(dāng)然是相對(duì)地址）。作業(yè) A進(jìn)入系統(tǒng)后被劃分成 3頁，如圖 318(a)所示。現(xiàn)在把第 0、 2頁依次裝入到內(nèi)存儲(chǔ)器的第 7三個(gè)不連續(xù)的塊中，如圖 318(b)所示。 為了確保原封不動(dòng)放在不連續(xù)塊中的用戶作業(yè) A能夠正常運(yùn)行 ， 可以采用如下方法 。 （ 1） 記錄作業(yè) A的頁 、 塊對(duì)應(yīng)關(guān)系 ， 如圖 318(c)所示 ， 它表示作業(yè) A的第 0頁放在內(nèi)存中的第 4塊 ， 第 1頁放在內(nèi)存中的第 9塊 ， 第 2頁放在內(nèi)存中的第 7塊 。 （ 2） 當(dāng)運(yùn)行到指令 “ call 3000”時(shí) ， 把它里面的相對(duì)地址 3000轉(zhuǎn)換成數(shù)對(duì)： (2， 952)， 表示該地址在作業(yè)相對(duì)地址空間里位于第 2頁 ， 距該頁起始位置的位移是952。 具體的計(jì)算公式是： 頁號(hào) =相對(duì)地址 /塊尺寸 （ 注：這里的 “ /”運(yùn)算符表示整除 ） ； 頁內(nèi)位移 =相對(duì)地址 %快尺寸 （ 注：這里的 “ %”運(yùn)算符表示求余 ） 。 （ 3）用數(shù)對(duì)中的“頁號(hào)”去查作業(yè) A的頁、塊對(duì)應(yīng)關(guān)系表（如圖 318(c)所示），得知相對(duì)地址空間中的第 2頁內(nèi)容，現(xiàn)在是在內(nèi)存的第 7塊中。 （ 4）把內(nèi)存第 7塊的起始地址與頁內(nèi)位移相加，就得到了相對(duì)地址 3000現(xiàn)在的絕對(duì)地址，即7KB+952=8120。 至此，系統(tǒng)就去做指令“ call 8120”，從而得到了正確地執(zhí)行。 從以上的講述可以看到，在分頁式存儲(chǔ)管理中，用戶程序是原封不動(dòng)地進(jìn)入各個(gè)內(nèi)存塊的。指令中相對(duì)地址的重定位工作，是在指令執(zhí)行時(shí)進(jìn)行，因此屬于動(dòng)態(tài)重定位，并且由如下的一些內(nèi)容一起來實(shí)現(xiàn)地址的動(dòng)態(tài)重定位： （ 1）將相對(duì)地址轉(zhuǎn)換成數(shù)對(duì)（頁號(hào)，頁內(nèi)位移）； （ 2）建立一張作業(yè)的頁與塊對(duì)應(yīng)表； （ 3）按頁號(hào)去查頁、塊對(duì)應(yīng)表； （ 4）由塊的起始地址與頁內(nèi)位移形成絕對(duì)地址。 分頁式存儲(chǔ)管理的地址轉(zhuǎn)換 1． 地址結(jié)構(gòu)與數(shù)對(duì) (頁號(hào) ， 頁內(nèi)位移 )的形成 如上所述 ， 在分頁式存儲(chǔ)管理的地址變換中 ， 首先遇到的是系統(tǒng)要把指令中的相對(duì)地址轉(zhuǎn)換成它所對(duì)應(yīng)的數(shù)對(duì) ， 并且也給出了進(jìn)行這種變換時(shí)使用的計(jì)算公式 。 但是 ， 如果每次地址變換都要做這種映射計(jì)算 ，不僅費(fèi)時(shí) ， 而且麻煩 。 如果把塊（或頁）的尺寸限定只能是 2的方冪，那么利用計(jì)算機(jī)系統(tǒng)設(shè)定的地址結(jié)構(gòu)，就很容易得到一個(gè)相對(duì)地址所對(duì)應(yīng)的數(shù)對(duì)，根本不用進(jìn)行上面的復(fù)雜計(jì)算。 例如，某系統(tǒng)的地址結(jié)構(gòu)長(zhǎng)為 16個(gè)二進(jìn)制位，如圖 319(a)所示。它表示該地址空間有 64KB（ 2的 16次方）大，即 0~65535?，F(xiàn)在圖 319(a)中是相對(duì)地址 3000的二進(jìn)制表示。我們假定系統(tǒng)的塊尺寸為 1KB=1024字節(jié)。 按照前面給出的公式，算出 3000對(duì)應(yīng)的數(shù)對(duì)是“ 2，952”。其實(shí)分析一下就可以知道，現(xiàn)在一頁的尺寸為1KB，表明每一頁中有 1024個(gè)字節(jié)，它需要用 10個(gè)二進(jìn)制位來表示。因此，我們?cè)诘?10個(gè)二進(jìn)制位處畫一條粗的豎線，如圖 319(b)所示。這樣，第 0位到第 9位這 10個(gè)二進(jìn)制位就可以表示一頁中 0~1023這 1024個(gè)字節(jié)。如果超過 1024個(gè)字節(jié)，就往前進(jìn)位。于是，前面的第 10位到第 15位就表示第幾頁。根據(jù)這個(gè)分析，圖319(b)中高 6位的二進(jìn)制數(shù)值是 2，正是 3000對(duì)應(yīng)的頁號(hào)，低 10位的二進(jìn)制數(shù)值是 952，正是 3000對(duì)應(yīng)的頁內(nèi)位移。 假定現(xiàn)在把一頁的尺寸設(shè)置為 256個(gè)字節(jié)。為了說明相對(duì)地址 3000應(yīng)該與哪個(gè)數(shù)對(duì)相對(duì)應(yīng)，在圖 319(a)的基礎(chǔ)上，在第 7位和第 8位之間畫一條粗的豎線，如圖 319(c)所示。之所以這樣做，是因?yàn)?2的 8次方等于256。計(jì)算高 8位（ 8~15）相應(yīng)的二進(jìn)制數(shù)值是 11；計(jì)算低 8位（ 0~7）相應(yīng)的二進(jìn)制數(shù)值是 184。因此，當(dāng)每頁長(zhǎng)度為 256個(gè)字節(jié)時(shí)，相對(duì)地址 3000應(yīng)該在第 11頁的第 184處。 2． 頁表與快表 在分頁式存儲(chǔ)管理中 ， 系統(tǒng)按照內(nèi)存塊的尺寸 ，把每一個(gè)用戶作業(yè)的相對(duì)地址空間劃分成若干頁 ， 然后把這些頁裝入到內(nèi)存的空閑塊中投入運(yùn)行 。 系統(tǒng)為了知道一個(gè)作業(yè)的某一頁存放在內(nèi)存中的哪一塊中 ，就需要建立起它的頁 、 塊對(duì)應(yīng)關(guān)系表 。 在操作系統(tǒng)中 ，把這張表稱為 “ 頁表 ” 。 因此 ， 在分頁式存儲(chǔ)管理中 ，每一個(gè)作業(yè)都有自己的頁表 。 用戶作業(yè)相對(duì)地址空間劃分成多少頁 ， 其頁表就有多少個(gè)表項(xiàng) ， 表項(xiàng)按頁號(hào)順序排列 。 頁表的構(gòu)成是應(yīng)該考慮的問題。一種方法是利用內(nèi)存儲(chǔ)器。這時(shí)，只需要硬件設(shè)置一個(gè)專用寄存器：“頁表控制寄存器”。每當(dāng)進(jìn)程調(diào)度時(shí)，把調(diào)度到作業(yè)的頁表起始地址和頁表長(zhǎng)度（即頁表表項(xiàng)的數(shù)目）放入寄存器中，就能達(dá)到映射不同作業(yè)地址的目的。圖 320給出了地址轉(zhuǎn)換過程：先把 CPU指令中的相對(duì)地址分解成數(shù)對(duì)（頁號(hào)，頁內(nèi)位移），接著由頁號(hào)與頁表起始地址得到該頁號(hào)在頁表中對(duì)應(yīng)的表目，從而查到相應(yīng)的塊號(hào)，再由塊號(hào)與頁內(nèi)位移拼出絕對(duì)地址。此時(shí)才去執(zhí)行所需要的指令。頁表控制寄存器中的“長(zhǎng)度”起到存儲(chǔ)保護(hù)的作用，每一個(gè)相對(duì)地址中的頁號(hào)都不能大于該長(zhǎng)度，否則出錯(cuò)。 由于頁表存放在內(nèi)存 ， 因此不僅增加了系統(tǒng)在存儲(chǔ)上的花銷 ， 更為重要的還是降低了 CPU的訪問速度 。這是因?yàn)槊看螌?duì)某一地址的訪問 ， 首先要訪問內(nèi)存中的頁表 ， 形成絕對(duì)地址后 ， 才能進(jìn)行所需要的真正訪問 。 也就是說 ， 以前只須一次訪問就能實(shí)現(xiàn)的操作 ，現(xiàn)在要兩次訪問內(nèi)存儲(chǔ)器才能實(shí)現(xiàn) 。 為了提高地址的轉(zhuǎn)換速度 ， 另一種實(shí)現(xiàn)頁表的方法是用一組快速的硬件寄存器構(gòu)成公用的頁表 。 調(diào)度到誰時(shí) ， 就把誰在內(nèi)存的頁表內(nèi)容裝入該組寄存器中 。這組硬件寄存器是這樣工作的：硬件把頁號(hào)與寄存器組中所有的表項(xiàng)同時(shí)并行比較 ， 立即輸出與該頁號(hào)匹配的塊號(hào) 。 如圖 321所示 。 這種做法無須訪問內(nèi)存 ，并且通過并行匹配直接完成地址的變換 ， 因此速度是極快的 。 由于快速寄存器價(jià)格昂貴 ， 因此完全由它來組成頁表的方案是不可取的 。 比如 ， 當(dāng)?shù)刂方Y(jié)構(gòu)為 32個(gè)二進(jìn)制位 、 塊尺寸定為 4KB時(shí) ， 地址空間最多可以有 100萬個(gè)頁面 。 由于一個(gè)頁面在頁表中要有一個(gè)表目項(xiàng) ，于是要有 100萬個(gè)快速寄存器組構(gòu)成頁表 ， 實(shí)在無法想象 。 考慮到大多數(shù)程序在一次調(diào)度運(yùn)行時(shí) ， 傾向于在少數(shù)頁面中進(jìn)行頻繁的訪問 （ 這被稱為程序的 “ 局部性 ” 原理 ） ， 因此實(shí)際系統(tǒng)中的做法是采用內(nèi)存頁表與快速寄存器組相結(jié)合的解決方案 ， 并且利用程序的局部性原理 ， 只用極少數(shù)幾個(gè) （ 一般是 8~16個(gè) ） 快速寄存器來構(gòu)成快速寄存器組 ， 這時(shí)把快速寄存器組單獨(dú)起名為： “ 相聯(lián)寄存器 ” ， 或簡(jiǎn)稱 “ 快表 ” 。 這時(shí)分頁式存儲(chǔ)管理的地址轉(zhuǎn)換過程如圖 322所示 。 通過查快表就能實(shí)現(xiàn)內(nèi)存訪問的成功率為 “ 命中率 ” ， 可見 ， 命中率越高 ， 性能就越好 。 表 32給出了平均命中率與相聯(lián)寄存器個(gè)數(shù)的關(guān)系 。 從表中可以看出 ， 設(shè)置快表 ， 確實(shí)能夠達(dá)到提高地址轉(zhuǎn)換速度的目的 。 內(nèi)存塊的分配與回收 分頁式存儲(chǔ)管理是以塊為單位進(jìn)行存儲(chǔ)分配的 ，并且每塊的尺寸相同 。 因此 ， 在有存儲(chǔ)請(qǐng)求時(shí) ， 只要系統(tǒng)中有足夠的空閑塊存在 ， 就可以進(jìn)行存儲(chǔ)分配 ，把誰分配出去都一樣 ， 沒有好壞之分 。 為了記住內(nèi)存塊誰是已分配的 ， 誰是空閑的 ， 可以采用 “ 存儲(chǔ)分塊表 ” 、 “ 位圖 ” 以及 “ 單鏈表 ” 等管理方法 。 所謂“存儲(chǔ)分塊表”，就是操作系統(tǒng)維持一張表格，它的一個(gè)表項(xiàng)與內(nèi)存中的一塊相對(duì)應(yīng)，用來記錄該塊的使用情況。比如，圖 323(a)表示內(nèi)存總的容量是 64KB，每塊 4KB，于是被劃分成 16塊。這樣，相應(yīng)的存儲(chǔ)分塊表也有 16個(gè)表項(xiàng)，它恰好記錄了每一塊當(dāng)前的使用情況，如圖 323(b)所示。當(dāng)有存儲(chǔ)請(qǐng)求時(shí)，就查存儲(chǔ)分塊表。只要表中“空閑塊總數(shù)”記錄的數(shù)目大于請(qǐng)求的存儲(chǔ)量，就可以進(jìn)行分配，同時(shí)把表中分配出去的塊的狀態(tài)改為“已分配”。當(dāng)作業(yè)完成歸還存儲(chǔ)塊時(shí)，就把表中相應(yīng)塊的狀態(tài)改為“空閑”。 當(dāng)內(nèi)存儲(chǔ)器很大時(shí) ， 存儲(chǔ)分塊表也就會(huì)很大 ， 要花費(fèi)掉相當(dāng)多的存儲(chǔ)量 ， 于是出現(xiàn)了用位圖記錄每一塊狀態(tài)的方法 。 所謂 “ 位圖 ” ， 即是用二進(jìn)制位與內(nèi)存塊的使用狀態(tài)建立起關(guān)系 ， 該位為 “ 0”， 表示對(duì)應(yīng)的塊空閑；該位為 “ 1”， 表示對(duì)應(yīng)的塊已分配 。 這些二進(jìn)制位的整體 ， 就稱為 “ 位圖 ” 。 比如圖 323(c)就是由 3個(gè)字節(jié)組成的位圖 ， 前兩個(gè)字節(jié)是真正的位圖 （ 共 16個(gè)二進(jìn)制位 ） ， 第三個(gè)字節(jié)用來記錄當(dāng)前的空閑塊數(shù) 。 進(jìn)行塊分配時(shí)，首先查看當(dāng)前空閑塊數(shù)能否滿足作業(yè)提出的存儲(chǔ)需求。若不能滿足，則該作業(yè)不能裝入內(nèi)存。在滿足時(shí)，一方面根據(jù)需求的塊數(shù)，在位圖中找出一個(gè)個(gè)當(dāng)前取值為“ 0”的位，把它們改為取值“ 1”，修改“空閑塊總數(shù)”。這樣，就把原來空閑的塊分配出去了；另一方面，按照所找到的位的位號(hào)以及字節(jié)號(hào)，可以按下面的公式計(jì)算出該位所對(duì)應(yīng)的塊號(hào)（注：下面給出的不是通用公式）： 塊號(hào) =字節(jié)號(hào) 8+位號(hào) 把作業(yè)相對(duì)地址空間里的頁面裝入這些塊，并在頁表里記錄頁號(hào)與塊號(hào)的這些對(duì)應(yīng)關(guān)系，形成作業(yè)的頁表。 在作業(yè)完成運(yùn)行歸還存儲(chǔ)區(qū)時(shí)，可以按照下面的公式，根據(jù)歸還的塊號(hào)計(jì)算出該塊在位圖中對(duì)應(yīng)的是哪個(gè)字節(jié)的哪一位，把該位置成“ 0”，實(shí)現(xiàn)塊的回收。 字節(jié)號(hào) =塊號(hào) /8； 位號(hào) =塊號(hào) %8 （注：這里的“ /”運(yùn)算符表示整除；這里的“ %”運(yùn)算符表示求余）。 如同可變分區(qū)方式管理內(nèi)存儲(chǔ)器時(shí)采用的單鏈表法一樣，在這里也可以把空閑塊鏈接成