哈工大計算機體系結(jié)構(gòu)Chapter4

計算機系凌緒將詡叉

哈爾濱工業(yè)大學(xué)

移劭計算研究中心

劉宏偉

哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)

2009-7-3學(xué)院1

>主要內(nèi)容

■4.1.存儲體系的形成與性能

■4.2.并行訪問存儲器

■4.3.虛擬存儲器

■4.4.頁式虛擬存儲器

■4.5.高速緩沖存儲器

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院2

4」.存儲體系的形成與性能

■4.LL發(fā)展存儲體系的必要性

■4.1.2.存儲體系的形成與分支

■4.L3.存儲體系的性能參數(shù)

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院3

4.L1發(fā)展存儲體系的必要性

>■存儲器是現(xiàn)代計算機系統(tǒng)的中心

主存儲器

取

寫

取I/O

指

結(jié)

操

令

果數(shù)

作

數(shù)據(jù)

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院4

存儲器的性能

-SM=WIm

■容量W:存儲字長

/：每個存儲體的字?jǐn)?shù)

m:存儲體的個數(shù)

■速度

(1)訪問時間TA：從接到訪存讀申請，到數(shù)據(jù)線

上得到穩(wěn)定的輸出所需的時間。

(2)存儲周期TM：連續(xù)啟動一個存儲體需要的時

間間隔。

(3)頻寬Bm：存儲器可以提供的數(shù)據(jù)傳送速率，

又可分為最大頻寬和實際頻寬

■價格：可用總價格C或每一位的價格c來表示

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院5

計算機系統(tǒng)對存儲器的要求

-容量大，速度高，價格低；

■容量、速度、價格三者之間是相互矛盾的

容量大，延遲大，速度低，總價格高；

速度高，價格高

-目前單一存儲器不能同時滿足容量、速度、價格

方面的要求

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院6

?存儲系統(tǒng)的概念

■兩個或兩個以上速度、容量、價格各不相

同的存儲器用硬件、軟件或硬件與軟件相

結(jié)合的方法連接起來成為一個系統(tǒng)，這個

系統(tǒng)對應(yīng)用程序員透明，并且，從應(yīng)用程

序員看，它是一個存儲器，它的速度接近

于所有存儲器中存儲周期最小的那一個，

容量接近于所有存儲器中容量最大的那

個，價格接近所有存儲器中價格最便宜的

那個。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院7

一個典型的存儲體系

>min(TpT2,...'),用存儲周期表不

S=max(SpS2,...Sn),用MB或GB表示

C=min(CpC2,...Cn),用每位的價格表示

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院8

4.L2存儲體系的形成與分支

■早期的存儲器系統(tǒng)

■虛擬存儲系統(tǒng)

■Cache■主存存儲層次

■多級存儲層次

■當(dāng)今計算機的存儲層次

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院9

(1)早期的存儲器系統(tǒng)

■由主存和輔存兩級構(gòu)成；

■主存與輔存之間并不構(gòu)成完整的整體；

■程序在主、輔之間的調(diào)入調(diào)出完全由程序員

考慮和安排。

這種存儲器系統(tǒng)存在的問題

■增加了程序員的工作量和編程難度；

-降低了程序的運行速度。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院10

(2)虛擬存儲系統(tǒng)

■由輔助的軟硬件自動完成程序在主、輔之間

的調(diào)入調(diào)出；

■從應(yīng)用程序員來看：主、輔構(gòu)成一個完整的

整體；

■存儲系統(tǒng)具有輔存的價格，輔存的容量，主

存的速度。

■程序員可以用整個虛存的地址空間對整個程

序進行統(tǒng)一編址，我們把這種指令的地址碼

稱為虛地址，實際主存地址稱為物理地址。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院11

主存—輔存存儲層次圖TF

主存儲磁盤存

器儲器

t從應(yīng)用程序員看:

速度接近主存儲器的速度，存儲容

量是虛擬地址空間，每位的價格接

近磁盤存儲器

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院12

主存—輔存存儲層次程序的調(diào)入與調(diào)出過程

.將程序空間分成較小的塊或頁

虛地址訪問主存時

■虛地址對應(yīng)單元的內(nèi)容是否裝入主存？

■若在，經(jīng)輔助硬件自動把虛地址轉(zhuǎn)換為主

存實地址

■不在，經(jīng)輔助軟硬件，將相應(yīng)的塊（頁）

調(diào)入主存

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院13

虛擬存儲器無法彌補主存和CPU之間的性能差異

o

00Proc

CPU60%/yr.

00Processor-Memory

PerformanceGap:

(grows50%/year)

M

/

DM/

RAyr

寸

01ZES9Z86017E寸S9Z86o

8888888.886666666.66o

666666668666666666666o

11II1I1I11111I111I11z

iIm￡

,Cache—主存存儲層次

!主■簿層次仍存在的問題

主存與CPU之間的速度差距仍然比較大

■解決方法

■(1)增加CPU中的通用寄存器的數(shù)量(價格、

程序員、編譯程序)

-(2)采用多體交叉并行存取來提高主存的等

效速度(設(shè)備量的增加并不能等比例的提高

主存的速度)

■(3)在主存與CPU之間增加一級速度高、容

量少、價格高的高速緩沖存儲器Cache。借助

于輔助破彳E度Cache與主存病成一個整床。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院15

速度接近Cache的速度，存

儲容量是主存的容量，每位

的價格接近贓存的價格

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院16

多級存儲層次

■整體具有接近

Ml的速度，Mn

CPUJM]/M2JM3」Mn

的容量，每位的

價格接近Mn

1、Mk是Mk+i的緩沖

2、靠近CPU的層次由硬件調(diào)度，遠離CPU的層次由

軟件或軟硬件相結(jié)合的方法調(diào)度

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院17

當(dāng)今計算機中的存儲層次

CPU內(nèi)部

/1

通用寄存器堆第1層

工作速度：Ti<Ti+1

訪

存儲容量：Sj<Si+1問

速

價格：Ci>C度

i+1越

來

越

快

2009-7-3

各種存儲器的主要性能指標(biāo)（僅供參考）

存儲器層次通用寄存器緩沖棧Cache主存儲器磁盤存儲器脫機存儲器

存儲周期<10ns<10ns10-60ns60-300ns10-30ms2-20min

存儲容量<512B<512B8K-2MB32M-1GB1G-1TB5G-10T

價格$C/KB1200803.20.360.010.0001

訪問方式直接譯碼先進先出相聯(lián)訪問隨機訪問塊訪問文件組

材料工藝ECLECLSRAMDRAM磁表面磁、光等

分配管理編譯器分配硬件調(diào)度硬件調(diào)度操作系統(tǒng)系統(tǒng)/用戶系統(tǒng)/用戶

帶寬MB/S400-8000400-1200200-80080-16010-1000.2-0.6

注ECL:EmitterCoupledLogic（發(fā)射極耦合邏輯電路）

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院19

“4.L3存儲體系的性能參數(shù)

■存儲器容量s

■單位容量的平均價格c

■訪問周期T

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院20

』14.1.3存儲體系的性能參數(shù)

■一個由兩個存儲器構(gòu)成的存儲系統(tǒng)

MlM2

(SI,ClfTl)(S2,C2,T2)

S,C,T

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院21

j存儲器容量s

■對存儲系統(tǒng)進行編址的方法

(1)對M2存儲器進行編址，例如Cache存儲

系統(tǒng)

(2)計算機的使用者為存儲系統(tǒng)另外設(shè)計一

個抽象的地址空間，在系統(tǒng)內(nèi)部，再對兩個

存儲器進行分別編址，并且把兩個存儲器的

地址映象到這個抽象的地址空間中，例如虛

擬存儲系統(tǒng)

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院22

■注意，并不是整個磁盤存儲器都作為虛

擬存儲系統(tǒng)使用的，只有在多任務(wù)或多

用戶操作系統(tǒng)中的交換區(qū)或交換文件才

是用來作虛擬存儲系統(tǒng)。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院23

單位容量的平均價格c

?不需單位容量價格公式

C=c.-s.+c^s2

S1+S2

討論

(1)通常情況下，S2?S1,C?C2,因此，存儲系統(tǒng)的

單位容量價格C接近于比較便宜的M2存儲器的單位容量價

格C2。

(2)S2與S1相差不能太大，否則系統(tǒng)要達到較高性能,

調(diào)度起來很困難。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院24

訪問周期T

■命中率：CPU產(chǎn)生的邏輯值能在Mi中訪問到的

概率，一般用模擬實驗的方法可以得到。假設(shè)

選定了一組代表性的程序，執(zhí)行，統(tǒng)計得到對

Mi訪問的次數(shù)為Ni，對M2的訪問次數(shù)為N2,

則命中率定義的表達式如下：

HN、

N、+IN/2

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院25

■整個系統(tǒng)的訪問周期T

T=H-I；+(1—")心

■存儲器的訪問效率

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院26

將(3.1)帶入(3.2)有

1

1

因此：訪問效率與命中率和構(gòu)成存儲系統(tǒng)的

兩級存儲器的速度之比有關(guān)。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院27

m----------------

■使存儲系統(tǒng)的速度與相對比較快的那個存儲

器的速度接近，有兩條途徑：

(1)提高命中率H;

(2)使構(gòu)成存儲系統(tǒng)的兩個存儲器的速度不

能相差太大。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院28

為了討論方便，設(shè)

則有

_________1_______

e―H+(1-H)r

據(jù)此，可得e=/"印的關(guān)系圖如下:

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院29

訪問效率

例1：當(dāng)r=100時,要使e>0.9,H>0.998

例2：在虛擬存儲系統(tǒng)中，兩級存儲器的速度相差比

較懸殊，r>105,如果e=0.9,H約為0.999999。這

個命中率怎么得到呢？

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院30

主要內(nèi)容

■4.1.存儲體系的形成與性能

■4.2.并行訪問存儲器

■4.3.虛擬存儲器

■4.4.頁式虛擬存儲器

■4.5.高速緩沖存儲器

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院31

1B4.2.并行訪問存儲器

-----------------

■單體單字存儲器

-單體多字存儲器

■多體交叉存儲器

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院32

■■單體單字存儲器

■*—---------------------

■特點

每個存儲周期只能訪問一個字?jǐn)?shù)據(jù)寄存器MDR

■主存最大頻寬

Bm=W/TM

存儲體

-主要問題（m字*w位）

存儲器的工作速度與CPU的工作

速度無法配合，存儲器成為計算機系

統(tǒng)的瓶頸。

地址寄存器MAR

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院33

單體多字存儲器

(1)CPU要訪問的字長不變，存儲字長增加n倍

(2)如果存儲器的總?cè)萘坎蛔儯瑒t字?jǐn)?shù)減少為1/n

(3)地址碼被分成了兩部分：存儲器地址和多路選擇

單字長寄存器

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院34

《單體多字存儲器__________

■優(yōu)點

實現(xiàn)起來非常簡單、容易

■缺點

(1)取指令沖突：遇到程序轉(zhuǎn)移，并且轉(zhuǎn)移成功時；

(2)讀操作數(shù)沖突：需要的多個操作數(shù)不一定正好存

放在同一個存儲字中；

(3)寫數(shù)據(jù)沖突：湊齊n個數(shù)才能一起存儲；

■可能的解決沖突方案

采用n套獨立的地址寄存器和n套讀寫控制邏輯

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院35

多體單字交叉訪問存儲器

■多體單字交叉訪問存儲器概述

■高位交叉訪問存儲器

■低位交叉訪問存儲器

■訪問沖突分析

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院36

多體單字交叉訪問存儲器

----------------------------------------------------------------------------------------

■每一個存儲體都有自己獨立的地址寄存器

■每個芯片都有獨立的地址譯碼和讀寫驅(qū)動等外

國電路

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院37

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院38

高位交叉訪問存儲器

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院39

高位交叉訪問存儲器

■主要用來構(gòu)成模塊化的存儲器。

你還記的計算機組成原理中的存儲器擴展嗎?

.組成這個存儲體的存儲器的參數(shù)

(Dm:每個存儲體的容量；

(2)n:構(gòu)成存儲器的存儲體的個數(shù)；

(3)j:每個存儲體的體內(nèi)地址；

(4)k:每個存儲器的各個存儲體的體號。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院40

高位交叉訪問存儲器地址的計算

因此

(1)這個存儲器的地址A的計算公式為:

A=m*k+j

(2)存儲器的體內(nèi)地址4的計算公式為:

Aj=Amodm

J

(3)存儲器的體號4的計算公式為：

L機」

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院41

高位交叉訪問存儲器的優(yōu)缺點

■優(yōu)點

每一個存儲模塊均可以并行工作，具備了并行工作的

條件。

■缺點

由于程序的連續(xù)性和局部性，在程序執(zhí)行過程中被訪

問的指令序列和數(shù)據(jù)絕大多數(shù)都分布在同一個存儲模

塊中，因此，只有一個模塊在不停的忙碌，其它模塊

均空閑。

主要用途：擴大存儲器的容量。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院42

>低位交叉訪問存儲器

■既能增加存儲器的容量又能增加訪存速度

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院43

低位交叉編址地址的計算

.假設(shè)采用低位交叉編址的存儲器的組成參數(shù)與前面

的采用高位交叉訪問方式的存儲器相同，則：

(1)存儲器的地址A的計算公式為：

A=n*j+k

(2)存儲器的體內(nèi)地址4?的計算公式為:

(3)存儲器的體號4的計算公式為：

Ak=Amodn

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院44

■由8個存儲體組成的低位交叉編址方式的存儲器

體

內(nèi)

地

址

(

啦

)

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院45

低位交叉編址n個存儲體分時啟動

存儲體周期〈

o號存儲體

1號存儲體

2號存儲體

nT號存儲體

t

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院46

*Tm為每個存儲體的訪問周期，t為存儲體

的泡動時間間隔：

*應(yīng)用范圍：共享存儲器的多處理機和高速

的單處理機。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院47

低位交叉編址中的訪問沖突

?低位交叉編址增加存儲體的個數(shù)，并不能使

存儲器的速度線性提高，為什么？

例如：有的大型計算機中，采用32個存

儲體低位交叉來構(gòu)成主存儲器，而這個主存

儲器的速度只比單個存儲體的速度提高10倍

左右O

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院48

訪問沖突分析

-1.設(shè)CPU在每個存儲周期能夠取到k個有效

字，k的最大值為n,最小值為1,k是一個隨

機變量。

■2.設(shè)p(k)是k的概率密度函數(shù)。則：B的平均

值為：

B=?p(k)

k=l

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院49

訪問沖突分析

k=l,時p(l)=入

k=2,時p(2)=(L入)入

k=3,時p(3)=(l?入戶*X

同理有k=n?l時，有p(n?l)=(l?入戶2*X

當(dāng)k=n時，無論第n條指令是否轉(zhuǎn)移，k都等于n

因此：p(n)=(l-入產(chǎn)”

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院50

代人表達式

B=21kp(k)

k=i

得至》:

B=l/+2?(1—2)/+…+(〃—1)?(1-2)

經(jīng)化簡得

1-(1-Ay

2

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院51

B

主存頻寬與轉(zhuǎn)移概率分析

.當(dāng)入vO?l時,n的大小對B的改

進

有攀木的髯跑jn的大小對B的影

響

友述常的計算機中，nv8

4.向量計算機中，n的值較大

5?對于最壞情況，用排隊論進行模

擬，得到隨著n的提高，主存的頻

寬近似于n的平方根的關(guān)系得到改

善。

圖4.5m個分體并行存取的占一八八）曲線

6.性能價格比隨n的增大而下降。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院52

主存的頻寬與轉(zhuǎn)移概率和存儲體的個數(shù)之間的關(guān)系

存儲體個數(shù)XX入=0.2入=0.3入=0.4

4嚏即皿2.952.532.18

87.735.704.163.142.46

1614.858.154.863.322.50

3227.509.665.003.332.50

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院53

早期幾臺大型的主存結(jié)構(gòu)

斗

機器型號存儲體個數(shù)存儲體字長存儲周期頻帶寬度

IBM370/1654322000ns8MB/s

CDC660032321000ns128MB/S

CDC67003232275ns465MB/S

CRAY-1166450ns2560MB/S

STAR-100325121280ns1600MB/S

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院54

主要內(nèi)容

■4.1.存儲體系的形成與性能

■4.2.并行訪問存儲器

■43.虛擬存儲器

■4.4.頁式虛擬存儲器

■4.5.高速緩沖存儲器

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院55

4.3.虛擬存儲器

■4.3.1.虛擬存儲器概述

■4.3.2.段式管理

■4.3.3.頁式管理

■434?段頁式管理

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院56

4.3.L虛擬存儲器概述

擬存儲器的組成

A主存儲器和聯(lián)機工作的外部存儲器

■虛擬存儲器中有三種地址

(1)虛擬地址空間：應(yīng)用程序員用來編寫程序

的地址空間，對應(yīng)虛擬地址；

(2)主存地址空間：主存物理空間，對應(yīng)主存

地址；

⑶輔存地址空間：磁盤存儲器的地址空間，

對應(yīng)磁盤存儲器地址。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院57

虛擬存儲器地址的映象與變換

■地址映象：把虛擬地址空間映象到主存地址空

間，即把用戶用虛擬地址編寫的程序，按照某

種規(guī)則裝入到主存中，并建立用戶康地址與主

存實地址之間的對應(yīng)關(guān)系。

■地址變換：程序運行過程中，把多用戶虛擬地

址轉(zhuǎn)換為主存實地址（內(nèi)部地址變換）或磁盤

存儲器地址（外部地址變換）

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院58

[4.3.1.虛擬存儲器地址映象的原理

■程序的定位由系統(tǒng)的定位機構(gòu)來完成，對應(yīng)用

程序員透明。

■地址映象與定位的基本過程

-把程序進行分塊（分程段或頁）；

■建立映象表，指明某段或某頁是否已裝入主存,

如果已裝入主存，指明其在主存的開始位置；

■執(zhí)行程序時，查映象表，如果在主存中，則變

換成實存地址，如果不在主存中，從輔存中調(diào)

入，修改映象表，執(zhí)行時，變換成實地址。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院59

>虛擬存儲器的存儲管理方式

■段式管理

■頁式管理

■段頁式管理

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院60

4.3.虛擬存儲器

■4.3.1.虛擬存儲器概述

■4.3.2.段式管理

■4.3.3.頁式管理

■434?段頁式管理

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院61

4.3.2段式管理

■程序的模塊性

-程序由多個在邏輯上相互獨立的段組成；

■程序在主■輔存之間的調(diào)入調(diào)出以程序段為單

位；

■每一道程序在系統(tǒng)中都有一個段表，段表指

出了該道程序的每一段是否調(diào)入了主存，該

段在主存中的首地址以及該段的長度。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院62

設(shè)某程序的程序空間如下所示，則段表為:

段名

（段號）段地址裝入位段長訪問方式

.:001Ik

1_______________

11

1.______0

i2

1?----------5k13k

13

I.______0

14

1.______Ik12k

15

i.______0

i?60

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院63

J］段表基址寄存器組

存放每程序段表的基地址,如果有N道程序

在主存中，存放這N道程序的段表的基地址的

N個寄存器就構(gòu)成了段表基址寄存器組。

o

1

??????

A7a

??????

N-1

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院64

■多用戶虛地址結(jié)構(gòu)

基號（程序號）段號段內(nèi)位移

A41.5k

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院65

J［分段管理方法的優(yōu)點

十便于大程序分塊編寫

■各段的修改、增刪不會影響其它段的編址

-用戶以段的方式連接而成的程序空間與主存的

實際容量無關(guān)

-多道程序共用已在主存內(nèi)的程序和數(shù)據(jù)

-容易以段為單位實現(xiàn)存儲保護

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院67

實主存管理表

>■占用區(qū)表：起始地址，段長，占用該段的用

戶號，該段進入主存后是否被修改過。

■可用區(qū)表：起始地址，長度。

■可用區(qū)歸并：如果兩個可用區(qū)在地址上相

鄰，則歸并為一個可用區(qū)

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院68

實存可用區(qū)分配算法

-首先分配算法：掃描可用區(qū)表，將要裝入的段

裝入到第一個掃描到的能夠裝入這個段的內(nèi)存

區(qū)域中。速度快，可用區(qū)零頭少。

■最優(yōu)分配法：掃描整個可用區(qū)表，找到一個區(qū)

域分配，使得分配之后段間的可用區(qū)零頭最小。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院69

>最優(yōu)分配法的優(yōu)缺點

?優(yōu)點

能夠留下較大的可用區(qū)，以備容納大的

程序段；

■缺點

會造成大量的可用區(qū)碎片，可能會造成

用“首先分配”算法能夠裝入，但用“最優(yōu)分

配”算法無法裝入的局面。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院70

兩種分配算法舉例

主存

0

0.5k

3k

7.5k

8k

2kF

10k

C

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院71

最優(yōu)分配算法

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院72

兩種分配算法舉例

首先分配法無法裝入F段,而用最優(yōu)分配法可以

主存程序

0"多"勿

0.5k1kD

A

3k

2kE

7.5kB

8k

10k

C

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院73

主存程序主存

IkD

2kE

首先分配算法

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院74

主存程序主存主存

―閃D|

A

首先分配算法最優(yōu)分配算法

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院75

兩種分配算法舉例

用首先分配法可以裝入F段,當(dāng)用最優(yōu)分配法不能

0主存程序

0.5k1kD

3k

2.5kE

7k

8k

2kF

10k

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院76

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院77

>段式管理存在的缺點

■起始地址字段比較長;

■段長字段比較長;

■較大的段間存儲區(qū)域零頭浪費。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院78

4.3.虛擬存儲器

■4.3.1.虛擬存儲器概述

■4.3.2.段式管理

■4.3.3.頁式管理

■434?段頁式管理

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院79

433.頁式管理

主存頁號主存空間D道程序

虛存頁號程序空間

04k

14k

24k

3

4

5

6

7

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院80

頁式存儲的基本原理

.主存空間等分成固定大小的頁；

■程序空間等分成固定大小的頁；

注意:主存的頁與虛存的頁大小相同

頁表：確定了實頁號與虛頁號之間的對

應(yīng)關(guān)系

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院81

事

■虛存地址格式與主存地址格式

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院82

頁式管理的一個實例

主存空間D道程序

主存頁號虛存頁號程序空間

0

4k

A4k

14k

224k

3B

4

5C

虛存頁號主存起點裝入位訪問方式專用位

6

021

7

32k161

271

（可省略）實頁號

D道程序頁表

實頁號頁內(nèi)位移

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院83

頁式管理的地址映象機構(gòu)及其地址變換過程

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院84

段式管理與頁式管理的優(yōu)缺點

■段式管理

(1)每個段都是獨立的；

(2)每個段只包含一種類型的對象，容易實現(xiàn)

保護；

(3)共享的程序或數(shù)據(jù)獨立成段，易于實現(xiàn)多

個用戶、進程對公用段的管理。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院85

>段式管理與頁式管理的優(yōu)缺點

■頁式管理

(1)管理對應(yīng)用程序員來說是透明的;

(2)映象表比較簡單；

(3)內(nèi)存資源浪費少。

但并不具備段式管理具有的優(yōu)點！

是否能將段式管理的優(yōu)點和頁式管理

的優(yōu)點結(jié)合起來呢？

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院86

4.3.虛擬存儲器

■4.3.1.虛擬存儲器概述

■4.3.2.段式管理

■4.3.3.頁式管理

■434?段頁式管理

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院87

V4.3.4段頁式管理

整頁式管理的基本思想

■實存：機械地等分成固定大小的頁

■程序：按照模塊分段，每一段又分成與頁面大

小相同的頁；

-段頁式與純段式的主要差別

段的起點不在是主存的任意位置，而是主存

中頁面的起點。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院88

W-----------------------

■段頁式多用戶虛地址的構(gòu)成

■用戶標(biāo)志U：標(biāo)識用戶或進程

■段號S；

■頁號p;

■頁內(nèi)偏移d。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院89

段頁式管理的定位映像機構(gòu)及其地址變換過程

90

J頁式管理和段頁式管理中存在的問題

**多次查表

(1)段頁式管理中：查找段表和頁表

(2)頁式管理中：當(dāng)頁表的大小超過

一頁時，也需多次查表。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院91

例：設(shè)程序的虛地址長為24位，其中，頁內(nèi)地

址為10位

Nv'（14位）Nr（10位）

則：頁面大小為2%尋址的總頁數(shù)為2q頁

表在一頁中放不下，需要為頁表再建立頁表。

可能需要建立多級頁表。

log^

log2小

哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院

頁表的分級查找舉例

如果頁表中每一項需要Bm個編址單元，且Bm

是2的整數(shù)次賽，即:

N"log2Be

則有：

N1

Nr—N,

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院93

J1頁表的分級查找舉例(續(xù))

例如：N'v=26,Nr=10?Ne=l(Multics),

則頁表的級數(shù)為：

i=[26/(IO-1)^=3

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院94

主要內(nèi)容

■4.1.存儲體系的形成與性能

■4.2.并行訪問存儲器

■4.3.虛擬存儲器

■4.4.頁式虛擬存儲器

■4.5.高速緩沖存儲器

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院95

4.4.頁式虛擬存儲器

>4.4.1.頁式虛擬存儲器地址的映象與變換

>4.4.2.主存頁面替換算法

■4.4.3.頁式虛擬存儲器實現(xiàn)中的問題

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院96

J4.4.1頁式虛擬存儲器地址的映象與變換

■用戶程序指令的地址碼Ni的構(gòu)成

(1)虛頁號N，v,(2)頁內(nèi)地址Nr

■主存地址

(1)實頁號nv,(2)頁內(nèi)地址nr

■虛存與實存的關(guān)系

(1)Nr=nr;(2)N'v>nv

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院97

■多用戶虛地址

(1)用戶號u,(2)虛頁號Nv"(3)頁內(nèi)地

址Nr,因次：虛存空間的總頁數(shù)為：

2〃+N*

如果多用戶虛頁號可以用Nv=Nv」u表示

因此有：

2NV>2%

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院98

虛擬存儲器工作過程中必須要解決的兩個問題

(1)如何把多個用戶的虛存空間壓縮到較小的主

存空間中；

(2)程序執(zhí)行過程中，如何將多用戶虛地址轉(zhuǎn)換

成主存實地址；

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院99

地址的映象和變換

■解決上述問題的方法-地址的映象和變換

■地址的映象：將每個虛存單元按照某種規(guī)

則裝入實后，建立實地址與虛地址之間的

對應(yīng)關(guān)系。對頁式來說，多用戶的虛頁號

對應(yīng)的頁可以裝入到主存的哪些頁位置。

■地址的變換：程序按照指定的映象關(guān)系裝

入主存后，在執(zhí)行時，如何把多用戶虛地

址轉(zhuǎn)換成對應(yīng)的實地址。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院100

虛實地址對應(yīng)關(guān)系及空間壓縮示意圖

一多用戶虛頁號NV—

多用戶虛地

址Ns

實存地址n

2W頁包括

211個用

戶，每個

用戶為2H

頁

2009-7-3101

■頁面爭用或?qū)嶍摏_突

-兩個虛頁請求進入主存同一個頁面位置

■全相聯(lián)映象

■基本思想：每道程序的任何虛頁可以映象裝入

到主存的任何實頁位置。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院102

全相聯(lián)映象示意圖

虛存

頁0

主存1

每

頁面位置。2道程

序

任

1何

虛

頁

可

以

映

像

到

任

何

實

頁

位

2nv-l

置

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院103

頁表法的改進

■裝入位為0的行，用實頁號nv字段存放該虛頁

在輔存中的地址。

■壓縮目錄表，只存放裝入主存的那些虛頁與

實頁的對應(yīng)關(guān)系，稱這種方法為相聯(lián)目錄表

法。

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院104

壓縮目錄表

基號用戶虛頁號頁內(nèi)位移

某用戶虛地

址

2四行

基號+用實頁號其它

戶虛頁號信息

目錄表

（存在相聯(lián)存儲器中）

2009-7-3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院105

全相聯(lián)映射存在的問題

■頁表法：頁表太大，可能需要采用多級頁表，

要查找的表項太多，查找速度慢！

-目錄表法：行數(shù)為主存的頁數(shù)，仍然比較多，

造價較高，查表速度很難快起來。

*因此，一般不直接用目錄表存儲全部虛頁號與