離散分配式存儲(chǔ)管理

趙剛

【摘 要】該文提出了一種不連續(xù)分配內(nèi)存的方式——分頁(yè)式存儲(chǔ)管理，并且討論了它的基本思想和地址轉(zhuǎn)換，最后提出了該存儲(chǔ)管理的缺點(diǎn)。

【關(guān)鍵詞】分頁(yè)式存儲(chǔ)管理；物理地址；邏輯地址；地址重定位；頁(yè)表；快表

【Abstract】This paper proposes a way to allocate memory discrete - page memory management， and discusses its basic ideas and address translation. Finally， the shortcomings of the storage management.

【Key words】Page memory management；Physical address；Logical address；The relocation；Page table；Fast table

存儲(chǔ)管理是操作系統(tǒng)五大功能之一，是操作系統(tǒng)的重要課題。在存儲(chǔ)管理中，連續(xù)分配方式會(huì)產(chǎn)生許多“碎片”，而這些“碎片”空間很小，無(wú)法容納相關(guān)作業(yè)。通常通過(guò)“緊湊”方法，移動(dòng)程序可以將許多“碎片”拼接成可用的大塊空間，但是通過(guò)“緊湊”方法，移動(dòng)程序增加了系統(tǒng)的開(kāi)銷。如果允許將作業(yè)直接分散地裝入到許多不相鄰、不連續(xù)的分區(qū)中，則無(wú)須再進(jìn)行“緊湊”?；谶@一思想而產(chǎn)生了離散分配方式，分頁(yè)式存儲(chǔ)管理就是其中的一種。

1. 分頁(yè)式存儲(chǔ)管理的基本思想

物理地址是內(nèi)存儲(chǔ)器中的實(shí)際有效地址，邏輯地址用是戶程序中使用的地址，也就是訪內(nèi)指令給出的地址叫邏輯地址。

1.1 分頁(yè)存儲(chǔ)管理允許把一個(gè)作業(yè)存放到若干不相鄰、不連續(xù)的分區(qū)中，這樣既可免去移動(dòng)信息所造成的系統(tǒng)開(kāi)銷，又可盡量減少內(nèi)存產(chǎn)生碎片，其基本思想是：

（1）把物理地址空間分成大小相等的許多分區(qū)，每個(gè)分區(qū)稱為“塊”或“幀”，每個(gè)塊有一個(gè)編號(hào)，從“0”開(kāi)始編號(hào)，塊是存儲(chǔ)分配的單元；

（2）按塊的大小把邏輯地址空間分成許多“頁(yè)”，從“0”開(kāi)始編號(hào)；

（3）邏輯地址形式： 作業(yè)的邏輯地址與一個(gè)數(shù)對(duì)（頁(yè)號(hào)，頁(yè)內(nèi)位移）一一對(duì)應(yīng)；

（4）采用分頁(yè)式存儲(chǔ)管理，作業(yè)一次性全部裝入內(nèi)存，作業(yè)進(jìn)入內(nèi)存時(shí)其連續(xù)的頁(yè)面可以裝入內(nèi)存中不相鄰、不連續(xù)的塊中，只要內(nèi)存有空閑塊，作業(yè)的某一頁(yè)可以放到內(nèi)存任一空閑塊。

1.2 例如：用戶作業(yè)A的大小為3KB，內(nèi)存塊的大小為1KB，當(dāng)作業(yè)提交給系統(tǒng)后被分成了3頁(yè)，如圖1（a）所示，根據(jù)圖1（c）頁(yè)表（頁(yè)與塊的對(duì)應(yīng)關(guān)系），作業(yè)A被裝進(jìn)了內(nèi)存不相鄰、不連續(xù)塊中，如圖1（b）所示。

2. 頁(yè)面的大小

在分頁(yè)存儲(chǔ)管理中的頁(yè)面的大小要適中。頁(yè)面如果太小，雖然可以使內(nèi)存碎片減小，減少了內(nèi)存碎片的總空間，有利于提高內(nèi)存利用率，但也會(huì)使每個(gè)作業(yè)占用較多的頁(yè)面，從而導(dǎo)致作業(yè)的頁(yè)表過(guò)長(zhǎng)，占用大量?jī)?nèi)存，此外，還會(huì)降低頁(yè)面換進(jìn)換出的效率；頁(yè)面如果較大，雖然可以減少頁(yè)表的長(zhǎng)度，提高頁(yè)面換進(jìn)換出的速度，但卻又會(huì)使頁(yè)內(nèi)碎片增大，降低內(nèi)存利用率（分頁(yè)存儲(chǔ)管理的實(shí)現(xiàn)見(jiàn)圖1）。

3. 分頁(yè)式存儲(chǔ)管理的地址轉(zhuǎn)換

3.1 頁(yè)表與快表。

（1）分頁(yè)系統(tǒng)中，將作業(yè)的各個(gè)頁(yè)面離散地存儲(chǔ)在內(nèi)存不連續(xù)的物理塊中，系統(tǒng)應(yīng)能保證進(jìn)程的正確運(yùn)行，即能在內(nèi)存中找到每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊。為此，系統(tǒng)為每個(gè)作業(yè)建立了一張頁(yè)面映像表，簡(jiǎn)稱頁(yè)表。配置了頁(yè)表后，作業(yè)執(zhí)行時(shí)，通過(guò)查找頁(yè)表，找到每頁(yè)在內(nèi)存中的物理塊號(hào)。頁(yè)表的作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。

（2）由于頁(yè)表是存放在內(nèi)存中，CPU在每存取一個(gè)數(shù)據(jù)時(shí)，都要兩次訪問(wèn)內(nèi)存。第一次是訪問(wèn)內(nèi)存中的頁(yè)表，從中找到指定頁(yè)的物理塊號(hào)，再將塊號(hào)與頁(yè)內(nèi)位移拼接，以形成物理地址。第二次訪問(wèn)內(nèi)存時(shí)，才是從第一次所得地址中獲得所需數(shù)據(jù)（或向此地址中寫入數(shù)據(jù)）。因此，采用這種方式將降低CPU訪問(wèn)速度，增加了系統(tǒng)在存儲(chǔ)上的開(kāi)銷。為了提高地址變換速度，可在地址變換機(jī)構(gòu)中增設(shè)一個(gè)具有并行查尋能力的特殊高速緩沖寄存器，又稱為“聯(lián)想寄存器”（Associative Memory），或稱為“快表”，地址變換過(guò)程是：在CPU給出有效地址后，由地址變換機(jī)構(gòu)自動(dòng)地將頁(yè)號(hào)送入高速緩沖寄存器，并將此頁(yè)號(hào)與高速緩存中的所有頁(yè)號(hào)進(jìn)行比較，若其中有與此相匹配的頁(yè)號(hào)，便表示所要訪問(wèn)的頁(yè)表項(xiàng)在快表中。于是，可直接從快表中讀出該頁(yè)所對(duì)應(yīng)的物理塊號(hào)，并送到物理地址寄存器中。如在塊表中未找到對(duì)應(yīng)的頁(yè)表項(xiàng)，則還須再訪問(wèn)內(nèi)存中的頁(yè)表，找到后，把從頁(yè)表項(xiàng)中讀出的物理塊號(hào)送地址寄存器，同時(shí)，再將此頁(yè)表項(xiàng)存入快表的一個(gè)寄存器單元中，重新修改快表。

3.2 地址重定位。

地址重定位指把目標(biāo)程序中的邏輯地址轉(zhuǎn)換成主存空間的物理地址，分頁(yè)式存儲(chǔ)管理采用的是動(dòng)態(tài)重定位，程序在執(zhí)行時(shí)過(guò)程中動(dòng)態(tài)完成地址重定位，需要硬件的支持，地址轉(zhuǎn)換過(guò)程如下：

（1）作業(yè)的邏輯地址轉(zhuǎn)換成頁(yè)號(hào)，頁(yè)內(nèi)位移兩部分，頁(yè)號(hào)=邏輯地址/塊尺寸，頁(yè)內(nèi)位移=邏輯地址%塊尺寸（“/”是整除運(yùn)算符，“%”是求余運(yùn)算符）；

（2）以頁(yè)號(hào)為索引去檢索頁(yè)表，在執(zhí)行檢索之前，先將頁(yè)號(hào)與頁(yè)表長(zhǎng)度進(jìn)行比較，如果頁(yè)號(hào)大于或等于頁(yè)表長(zhǎng)度，表示本次所訪問(wèn)的地址已超越作業(yè)的地址空間，系統(tǒng)將產(chǎn)生一個(gè)地址越界中斷，如果沒(méi)有出現(xiàn)越界錯(cuò)誤，通過(guò)查找頁(yè)表，找到頁(yè)號(hào)對(duì)應(yīng)的塊號(hào)；

（3）塊號(hào)*塊尺寸+頁(yè)內(nèi)位移得到物理地址，這樣完成從邏輯地址到物理地址的變換。

3.3 舉例分析。

3.3.1 分頁(yè)系統(tǒng)中內(nèi)存被劃分成4塊，每塊4KB，某作業(yè)的邏輯地址空間共劃分成4個(gè)頁(yè)面，當(dāng)前頁(yè)與塊對(duì)應(yīng)關(guān)系表（頁(yè)表）如表1所示，試求出對(duì)應(yīng)于下列邏輯地址的物理地址：（a）4100（b）8300。（見(jiàn)表1）

3.3.2 解：（a）邏輯地址4100對(duì)應(yīng)的頁(yè)號(hào)是：4100/4096=1 ，對(duì)應(yīng)的頁(yè)內(nèi)位移是：4100%4096=4，用1去查頁(yè)表，知道第1頁(yè)現(xiàn)在存放在內(nèi)存的第1塊，第1塊的起始地址為4096（4KB），因此，邏輯地址4100所對(duì)應(yīng)的物理地址是：4096+4=4100；

（b）虛擬地址8300對(duì)應(yīng)的頁(yè)號(hào)是：8300/4096=2，對(duì)應(yīng)的頁(yè)內(nèi)位移是：8300%4096=108，用2去查頁(yè)表，知道第2頁(yè)現(xiàn)在存放在內(nèi)存的第6塊，第6塊的起始地址為6×4K=24576，因此，邏輯地址8300所對(duì)應(yīng)的物理地址是24576+108=24684。

4. 分頁(yè)式存儲(chǔ)管理的缺點(diǎn)

（1）分頁(yè)式存儲(chǔ)管理中，作業(yè)的最后一頁(yè)大小可能與內(nèi)存塊大小不吻合，會(huì)產(chǎn)生內(nèi)部碎片，浪費(fèi)內(nèi)存空間；

（2）分頁(yè)式存儲(chǔ)管理中，作業(yè)需要一次性全部裝入內(nèi)存，當(dāng)作業(yè)尺寸大于內(nèi)存剩余空間時(shí)，作業(yè)無(wú)法進(jìn)入內(nèi)存運(yùn)行，因此，分頁(yè)式存儲(chǔ)管理不具備虛擬存儲(chǔ)技術(shù)。

參考文獻(xiàn)

[1] 宗大華， 宗濤， 陳吉人. 操作系統(tǒng)[M].3版.北京： 人民郵電出版社， 2011： 57～66.

[2] 張堯?qū)W， 史美林.計(jì)算機(jī)操作系統(tǒng)教程[M]. 北京： 清華大學(xué)出版社， 1993.

[文章編號(hào)]1619-2737（2015）07-29-027