【計(jì)算機(jī)操作系統(tǒng)】操作系統(tǒng)--分頁(yè)存儲(chǔ)管理方式

離散分配方式

連續(xù)分配存儲(chǔ)管理方式產(chǎn)生的問(wèn)題：

• 要求連續(xù)的存儲(chǔ)區(qū)
• 碎片問(wèn)題

變連續(xù)分配為離散分配，允許將作業(yè)離散放到多個(gè)不相鄰接的分區(qū)中。

• 分頁(yè)式存儲(chǔ)管理：離散分配的基本單位是頁(yè)
• 分段式存儲(chǔ)管理：離散分配的基本單位是段
• 段頁(yè)式存儲(chǔ)管理：離散分配的基本單位是段、頁(yè)

頁(yè)面和物理塊

空間劃分

• 將1個(gè)用戶進(jìn)程的地址空間（邏輯空間）劃分成若干個(gè)大小相等的區(qū)域，稱為頁(yè)或頁(yè)面，各頁(yè)從 0 開(kāi)始編號(hào)。
• 內(nèi)存空間也分成若干個(gè)與頁(yè)大小相等的區(qū)域，稱為塊（物理塊）或頁(yè)框（frame） ，一樣從 0 開(kāi)始編號(hào)。

內(nèi)存分配

• 在為進(jìn)程分配內(nèi)存時(shí)以塊為單位，將進(jìn)程中若干頁(yè)裝入到多個(gè)不相鄰的塊中，最后1頁(yè)常裝不滿1塊而出現(xiàn)頁(yè)內(nèi)碎片。

地址結(jié)構(gòu)

已知邏輯地址求頁(yè)號(hào)和頁(yè)內(nèi)地址

給定1個(gè)邏輯地址空間中的地址為 A，頁(yè)面的大小為L(zhǎng)，則頁(yè)號(hào) P 和頁(yè)內(nèi)地址 d（從 0 開(kāi)始編號(hào)）可按下式求得：

其中，INT 是整除函數(shù)，mod 是取余函數(shù)。

例：系統(tǒng)的頁(yè)面大小為 1 KB，設(shè) A = 2170 B，則由上式可以求得 P = 2，d = 122。

頁(yè)表

為了便于在內(nèi)存找到進(jìn)程的每一個(gè)頁(yè)面所對(duì)應(yīng)塊，分頁(yè)系統(tǒng)中為每一個(gè)進(jìn)程配置1張頁(yè)表，進(jìn)程邏輯地址空間中的每頁(yè)，在頁(yè)表中都對(duì)應(yīng)有1個(gè)頁(yè)表項(xiàng)。

頁(yè)表寄存在內(nèi)存中，屬于進(jìn)程的現(xiàn)場(chǎng)信息。
用處：1.記錄進(jìn)程的內(nèi)存分配情況 2.實(shí)現(xiàn)進(jìn)程運(yùn)行時(shí)的動(dòng)態(tài)重定位。
訪問(wèn)1個(gè)數(shù)據(jù)需訪問(wèn)內(nèi)存 2 次 (頁(yè)表1次，內(nèi)存1次)。
頁(yè)表的基址及長(zhǎng)度由頁(yè)表寄存器給出。

頁(yè)面大小

若頁(yè)面較小

• 減少頁(yè)內(nèi)碎片和總的內(nèi)存碎片，有益于提高內(nèi)存利用率。
• 每一個(gè)進(jìn)程頁(yè)面數(shù)增多，使頁(yè)表長(zhǎng)度增加，占用內(nèi)存較大。
• 頁(yè)面換進(jìn)換出速度將下降。

若頁(yè)面較大

• 每一個(gè)進(jìn)程頁(yè)面數(shù)減少，頁(yè)表長(zhǎng)度減少，占用內(nèi)存較小。
• 頁(yè)面換進(jìn)換出速度將提高。
• 增加頁(yè)內(nèi)碎片，不利于提高內(nèi)存利用率。

基本分頁(yè)存儲(chǔ)管理方式

在分頁(yè)存儲(chǔ)管理方式中，如果不具有頁(yè)面對(duì)換功能，不支持虛擬存儲(chǔ)器功能，這類存儲(chǔ)管理方式稱為純分頁(yè)或基本分頁(yè)存儲(chǔ)管理方式。

在調(diào)度作業(yè)運(yùn)行時(shí)，必須將它的所有頁(yè)面1次調(diào)入內(nèi)存，但邏輯上連續(xù)的各個(gè)頁(yè)所對(duì)應(yīng)的內(nèi)存塊可以不連續(xù)。

特殊的固定分區(qū) + 離散分配

地址變換機(jī)構(gòu)

地址變換機(jī)構(gòu)

• 將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址。
• 實(shí)現(xiàn)邏輯地址向物理地址的轉(zhuǎn)換（頁(yè)號(hào) ? 塊號(hào)）
• 地址變換借助頁(yè)表來(lái)完成。

地址變換機(jī)構(gòu)種類

• 基本的地址變換機(jī)構(gòu)
• 具有快表的地址變換機(jī)構(gòu)

基本地址變換機(jī)構(gòu)

地址變換借助頁(yè)表來(lái)完成，頁(yè)表駐留內(nèi)存。

為了提高地址變換的速度，系統(tǒng)中設(shè)置1個(gè)頁(yè)表寄存器PTR (Page-Table Register)。

每一個(gè)進(jìn)程對(duì)應(yīng)1頁(yè)表，其信息（如長(zhǎng)度、始址）放在PCB 中，履行時(shí)將其裝入頁(yè)表寄存器。

在單處理機(jī)環(huán)境下，雖然系統(tǒng)中可以運(yùn)行多個(gè)進(jìn)程，但只需1個(gè)頁(yè)表寄存器。

基本地址變換機(jī)構(gòu)

當(dāng)進(jìn)程要訪問(wèn)某個(gè)邏輯地址中的數(shù)據(jù)時(shí)，分頁(yè)地址變換機(jī)構(gòu)會(huì)自動(dòng)地將有效地址（相對(duì)地址）分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部份。

將頁(yè)號(hào)與頁(yè)表長(zhǎng)度進(jìn)行比較，如果頁(yè)號(hào)大于或等于頁(yè)表長(zhǎng)度，則表示本次所訪問(wèn)的地址已超出進(jìn)程的地址空間，產(chǎn)生地址越界中斷。

將頁(yè)表始址與頁(yè)號(hào)和頁(yè)表項(xiàng)長(zhǎng)度的乘積相加，得到該表項(xiàng)在頁(yè)表中的位置，因而可從中得到該頁(yè)的物理塊號(hào)，將之裝入物理地址寄存器中。

將有效地址寄存器中的頁(yè)內(nèi)地址送入物理地址寄存器的塊內(nèi)地址字段中。

• 邏輯地址: 把相對(duì)地址分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部份。
• 越界中斷: 頁(yè)號(hào)與頁(yè)表長(zhǎng)度做比較。
• 頁(yè)表定位：頁(yè)表始址 + 頁(yè)號(hào) × 頁(yè)表項(xiàng)長(zhǎng)度。{查詢頁(yè)表：讀出塊號(hào)。
• 物理地址：塊號(hào) + 塊內(nèi)地址。 （塊內(nèi)地址 = 頁(yè)內(nèi)地址）

地址變換例題

例：若在1分頁(yè)存儲(chǔ)管理系統(tǒng)中，某作業(yè)的頁(yè)表以下表所示，已知頁(yè)面大小為 1024B，試將10進(jìn)制邏輯地址 1011，2148，5012 轉(zhuǎn)化為相應(yīng)的物理地址。

設(shè)頁(yè)號(hào)為 P，頁(yè)內(nèi)位移為 W，邏輯地址為 A，內(nèi)存地址為 M，頁(yè)面大小為 L，則
P = int ( A / L )
W = A mod L
對(duì)邏輯地址 1011
P=int(1011/1024)=0
W=1011 mod 1024=1011
A=1011=(0,1011)
查頁(yè)表第 0 頁(yè)在第 2 塊，所以物理地址為 M=1024*2+1011= 3059。

對(duì)邏輯地址為 2148
P= int (2148/1024)=2
W=2148 mod 1024=100
A=2148=(2,100)
查頁(yè)表第 2 頁(yè)在第 1 塊，所以物理地
址為 M=1024*1+100=1124。
對(duì)邏輯地址 5012
P= int ( 5012/1024)=4
W=5012 mod 1024=916
頁(yè)號(hào)超過(guò)頁(yè)表長(zhǎng)度，該邏輯地址非法。

例：存儲(chǔ)器的用戶空間共有 32 個(gè)頁(yè)面，每頁(yè) 1KB，內(nèi)存16KB。假定某時(shí)刻系統(tǒng)為用戶的第 0、1、2、3 頁(yè)分別分配的物理塊號(hào)為 5、10、4、7，試將邏輯地址 0A5C 和093C 變換為物理地址。

具有快表的地址變換機(jī)構(gòu)

基本的地址變換機(jī)構(gòu)存在的問(wèn)題

• 地址變換速度低（兩次訪問(wèn)內(nèi)存）

具有快表的地址變換機(jī)構(gòu)

• 目的：為提高地址變換速度。
• 快表：又稱為聯(lián)想寄存器、聯(lián)想存儲(chǔ)器 (AssociativeMemory) 、IBM-TLB (Translation Lookaside Buffer)。
• 快表是1種特殊的高速緩沖存儲(chǔ)器（Cache） ，內(nèi)容是頁(yè)表中的1部份或全部?jī)?nèi)容。
• CPU 產(chǎn)生邏輯地址的頁(yè)號(hào)，首先在快表中尋覓，若命中就找出其對(duì)應(yīng)的物理塊；若未命中，再到頁(yè)表中找其對(duì)應(yīng)的物理塊，并將之復(fù)制到快表。若快表中內(nèi)容滿，則按某種算法淘汰某些頁(yè)。

訪問(wèn)內(nèi)存的有效時(shí)間

有效訪問(wèn)時(shí)間(Effective Access Time ,EAT) 是指從給定邏輯地址，經(jīng)過(guò)地址變換，到在內(nèi)存中找到對(duì)應(yīng)物理地址單元并取出數(shù)據(jù)所用的總時(shí)間。

基本地址變換機(jī)構(gòu)

具有快表的地址變換機(jī)構(gòu)

例：有1頁(yè)式系統(tǒng)，其頁(yè)表寄存在內(nèi)存中。（1）如果對(duì)內(nèi)存的1次存取需要 100ns，試問(wèn)實(shí)現(xiàn)1次頁(yè)面訪問(wèn)的存取時(shí)間是多少？（2）如果有快表，對(duì)快表的1次存取需要20ns, 平均命中率為 85%，試問(wèn)此時(shí)的存取時(shí)間為多少？

頁(yè)表放內(nèi)存中，則實(shí)現(xiàn)1次頁(yè)面訪問(wèn)需 2 次訪問(wèn)內(nèi)存。
所以實(shí)現(xiàn)1次頁(yè)面訪問(wèn)的存取時(shí)間為：100ns*2=200ns

系統(tǒng)有快表，則實(shí)現(xiàn)1次頁(yè)面訪問(wèn)的存取時(shí)間為：
0.85*(20ns+100ns)+(1-0.85)*(20ns+2*100ns)=135ns

多級(jí)頁(yè)表

若邏輯地址空間很大 (2^32 ∼2^64 ) ，則劃分的頁(yè)比較多，頁(yè)表就很大，占用的存儲(chǔ)空間大（要求連續(xù)） ，實(shí)現(xiàn)較困難。

例如，對(duì) 32 位邏輯地址空間的分頁(yè)系統(tǒng)，如果規(guī)定頁(yè)面大小為 4 KB 即 2^12 B，則在每一個(gè)進(jìn)程頁(yè)表就由高達(dá)2^20 頁(yè)組成。設(shè)每一個(gè)頁(yè)表項(xiàng)占用1個(gè)字節(jié)，每一個(gè)進(jìn)程僅僅頁(yè)表就要占用 1 MB 的內(nèi)存空間。

解決問(wèn)題的方法

• 動(dòng)態(tài)調(diào)入頁(yè)表: 只將當(dāng)前需用的部份頁(yè)表項(xiàng)調(diào)入內(nèi)存，其余的需用時(shí)再調(diào)入。
• 多級(jí)頁(yè)表

兩級(jí)頁(yè)表

將頁(yè)表再進(jìn)行分頁(yè)，離散地將各個(gè)頁(yè)表頁(yè)面寄存在不同的物理塊中，同時(shí)也再建立1張外部頁(yè)表用以記錄頁(yè)表頁(yè)面對(duì)應(yīng)的物理塊號(hào)。

正在運(yùn)行的進(jìn)程，必須把外部頁(yè)表調(diào)入內(nèi)存，而動(dòng)態(tài)調(diào)入內(nèi)部頁(yè)表。只將當(dāng)前所需的1些內(nèi)層頁(yè)表裝入內(nèi)存，其余部份根據(jù)需要再陸續(xù)調(diào)入。

將外層頁(yè)表再進(jìn)行分頁(yè)，也將各外層頁(yè)表頁(yè)面離散地寄存在不同的物理塊中，再利用第 2 級(jí)的外層頁(yè)表來(lái)記錄它們之間的對(duì)應(yīng)的關(guān)系。

反置頁(yè)表

解決問(wèn)題的方法

• 動(dòng)態(tài)調(diào)入頁(yè)表
• 多級(jí)頁(yè)表
• 反置頁(yè)表（Inverted page tables ）

1般頁(yè)表的表項(xiàng)是按頁(yè)號(hào)進(jìn)行排序，頁(yè)表項(xiàng)中的內(nèi)容是物理塊號(hào)。

反置頁(yè)表是為每個(gè)物理塊設(shè)置1個(gè)頁(yè)表項(xiàng)并按物理塊號(hào)排序，其中的內(nèi)容是頁(yè)號(hào) P 及隸屬進(jìn)程標(biāo)志符 pid。

利用反置頁(yè)表進(jìn)行地址變換

• 用進(jìn)程標(biāo)志符和頁(yè)號(hào)去檢索反置頁(yè)表。
• 如果檢索完全個(gè)頁(yè)表未找到與之匹配的頁(yè)表項(xiàng)，表明此頁(yè)此時(shí)還沒(méi)有調(diào)入內(nèi)存，對(duì)具有要求調(diào)頁(yè)功能的存儲(chǔ)器系統(tǒng)產(chǎn)生要求調(diào)頁(yè)中斷，若無(wú)此功能則表示地址出錯(cuò)。
• 如果檢索到與之匹配的表項(xiàng)，則表項(xiàng)的序號(hào) i 便是該頁(yè)的物理塊號(hào)，將該塊號(hào)與頁(yè)內(nèi)地址1起構(gòu)成物理地址。

• 反置頁(yè)表可以有效地減少頁(yè)表占用的內(nèi)存，但反置頁(yè)表中只包括已調(diào)入內(nèi)存的頁(yè)面，未包括那些未調(diào)入內(nèi)存的各個(gè)進(jìn)程的頁(yè)面，因此必須為每一個(gè)進(jìn)程建立1個(gè)外部頁(yè)表 (External Page Table)。發(fā)現(xiàn)頁(yè)面不在內(nèi)存時(shí)才訪問(wèn)外部頁(yè)表。
• 外部頁(yè)表寄存各頁(yè)在外存中的物理位置。通過(guò)外部頁(yè)表可將所需要的頁(yè)面調(diào)入內(nèi)存。
• 反置頁(yè)表中是為每個(gè)物理塊設(shè)置1個(gè)頁(yè)表項(xiàng)，通常頁(yè)表項(xiàng)的數(shù)目也很大，通常又利用 Hash 表來(lái)檢索。

頁(yè)的同享與保護(hù)

頁(yè)的同享：各進(jìn)程把需要同享的數(shù)據(jù)/程序的相應(yīng)頁(yè)指向相同物理塊。

頁(yè)的保護(hù)

頁(yè)式存儲(chǔ)管理系統(tǒng)提供了兩種方式：

• 地址越界保護(hù)
• 在頁(yè)表中設(shè)置保護(hù)位（定義操作權(quán)限：只讀，讀寫，履行等）

同享帶來(lái)的問(wèn)題

若同享數(shù)據(jù)與不同享數(shù)據(jù)劃在同1塊中，則：

• 有些不同享的數(shù)據(jù)也被同享，不容易保密。
• 計(jì)算同享數(shù)據(jù)的頁(yè)內(nèi)位移較困難。

實(shí)現(xiàn)數(shù)據(jù)同享的最好方法：分段存儲(chǔ)管理。

轉(zhuǎn)載自：楊森源

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)