分頁式存儲管理的分析

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

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

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：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

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

分頁式存儲管理的基本思想

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

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

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

2）按塊的大小把邏輯地址空間分成許多“頁”，從“0”開始編號；

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

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

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

1 頁面的大小

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

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

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

2.1 頁表與快表

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

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

2.2 地址重定位

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

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

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

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

2.3舉例分析

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

表1

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

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

3 分頁式存儲管理的缺點(diǎn)

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

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

參考文獻(xiàn)：

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

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