雷華軍++邢益良++裴云

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）11-0008-02

The Analysis of the Paging Storage Management

LEI Hua-jun ， XING Yi-liang，PEI Yun

（Hainan College of Software Technology， Qionghai 571400， China）

Abstract：In this paper ，an approach of discontinuous allocating memory- the paging storage management is proposed， then the basic idea and the address relocation of the paging storage management are discussed， finally the defects of the paging storage management are proposed.

Key words： the paging storage management； physical address；Logical address； Address relocation； page table； quick page table

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

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

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

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

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

2）按塊的大小把邏輯地址空間分成許多“頁(yè)”，從“0”開始編號(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)存任一空閑塊。

例如：用戶作業(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）所示。

1 頁(yè)面的大小

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

圖1 分頁(yè)存儲(chǔ)管理的實(shí)現(xiàn)

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

2.1 頁(yè)表與快表

分頁(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í)，通過查找頁(yè)表，找到每頁(yè)在內(nèi)存中的物理塊號(hào)。頁(yè)表的作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。

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

2.2 地址重定位

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

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)度，表示本次所訪問的地址已超越作業(yè)的地址空間，系統(tǒng)將產(chǎn)生一個(gè)地址越界中斷，如果沒有出現(xiàn)越界錯(cuò)誤，通過查找頁(yè)表，找到頁(yè)號(hào)對(duì)應(yīng)的塊號(hào)；

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

2.3舉例分析

分頁(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。

表1

解：（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。

3 分頁(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è)無法進(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.