第04章存儲器管理_第1頁
第04章存儲器管理_第2頁
第04章存儲器管理_第3頁
第04章存儲器管理_第4頁
第04章存儲器管理_第5頁
已閱讀5頁,還剩132頁未讀 繼續免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

第四章落儲器管理

第四章存儲器管理

4」存儲器的層次結構

4.2程序的裝入和鏈接

43連續分配方式

4.4基本分頁存儲管理方式

4.5基本分段存儲管理方式

4.6虛擬存儲器的基本概念

4.7請求分頁存儲管理方式

4.8頁面置換算法

4.9請求分段存儲管理方式

k士章商借器管理一q

4.1存儲器的層次結構''

4.1.1多級存儲器結構

?1.存儲器功能

?合理、安全、有效地保存數據

?2.存儲器發展方向

?接口更新

-以硬盤為例:ESDI;IDE/EIDE;ATA;SATA/SATA2;SCSI;

IEEE1394;USB...

>高速性

-以USB為例:USB1.1是12Mbps,USB2.0是480Mbps,USB3.0

理論上是5Gbps...

?存儲密度越來越高,體積越來越小

-1.7Mb/平方英寸;20Mb/平方英寸;1.43Gb/平方英寸;

135Gb/平方英寸;620Gb/平方英寸;1Tb/平方英寸…的不

第四章落儲器管理

--■

容量有望翻倍希捷達到存儲密度新紀錄

2012年03月21日00:00來源:/作者:ChrisR編輯:秋龍評論:一條

[IT168資訊】希捷今日正式宣布,該公司成為第一家在存儲密度上達到1Tbit/平方英寸(1

terabit=ltrillionbit=l萬億bit)這一里程碑的哽盤廠商,新技術的應用使得每平方英寸所記

錄的bit數量甚至超過了銀河系中的天體數量(約20007000億之間)?

希捷所采用的技術名為HAMR,即HeaLAssistedMagneticRecording(熱輔助磁記錄)。作

為目前耍盤采用的P股(PerpendicularMagneticRecording,垂直磁記錄技術的繼任者),

HAMR的理論存儲密度為570Tbit/平方英寸。相比之下,目前的3.5英寸硬盤存儲密度為

620Gbit/平方英寸,2.5硬盤的存儲密度為500Gbit/平方英寸。

HAMR技術可輕松達到PMR技術的存儲密度極限一一1Tbit/平方英寸這一里程碑,比目前硬盤產

品的存儲密度高出55%左右。一旦HAMR得到實際應用,目前3.5英寸硬盤產品的容量可輕松翻倍達

到6TB左右,2.5英寸硬盤的容量更是能提升至2TB。未來HAMR技術成熟后3.5英寸/2.5英寸硬盤的

容量更是可以達到目前服務器水平的30-60TB/10-20ITB。

3

第四章落儲器管理

A容量越來越大,價格越來越低

-以下是近年來關于硬盤價格的趣味數字

□1995年200MB?400MB大于4000元/GB

□1996年1.2GB?2.1GB1500元?2000/GB

□1998年1.2GB?2.1GB200元?250元/GB

□2000年4.3GB--6.4GB40元/GB

□2002年10GB-20GB20元/GB

□2004年40GB-80GB6.97U/GB

□2005年80GB-J60GB4.57U/GB

□2006年80GB-250GB3.8元/GB

□2008年160GB--1TB1.6元/GB

□2009年500GB--2TB0.8元/GB

□2010年500GB入-2TB0.6元/GB

第四章落儲器管理

■■單

圖4-1計算機系統存儲層次示意

第四章落儲器管理

?4.存儲管理功能

A存儲分配與回收

-本章主要內容,討論其算法和數據結構

A地址變換

-可執行文件生成中的鏈接技術;程序裝入時的重定

位技術;進程運行時的地址變換技術和機構(軟件、

硬件)

A存儲共享和保護

-代碼和數據共享;對地址空間的訪問權限(讀、寫、

執行)

A存儲器擴充

-由用戶應用程序控制:覆蓋Overlay

-由OS控制:交換Swapping;請求調入和預調入On

Demand&OnPrefetch么-

w

第四章存儲器管理

4.1.2主存儲器與寄存器

?1.主存儲器

?主存儲器(簡稱內存或主存)是計算機系統中一

個主要部件,用于保存進程運行時的程序和數

據,也稱可執行存儲器,材質以DRAM為主。

由于主存儲器的訪問速度遠低于CPU執行指令

的速度,為緩和這一矛盾,在計算機系統中引

入了寄存器和高速緩存。

W

第四章落儲器管理

?2.寄存器

A寄存器訪問速度最快,完全能與CPU協調工作,

但價格卻十分昂貴,因此容量不可能做得很大。

寄存器的長度一般以字(word)為單位。寄存器

的數目,對于當前的微機系統和大中型機,可

能有幾十個甚至上百個;而嵌入式計算機系統

一般僅有幾個到幾十個。

A寄存器通常用于加速存儲器的訪問速度,如用

寄存器存放操作數,或用作地址寄存器加快地

址轉換速度等。

8

立章啟承器管理

4.1.3高速緩存和磁盤緩存

?1.高速緩存

?高速緩存是現代計算機結構中的一個重要部件,

其容量大于或遠大于寄存器,而比內存約小兩

到三個數量級左右,從幾十KB到幾MB,訪問

速度快于主存儲器。

A根據程序執行的局部性原理(即程序在執行時將

呈現出局部性規律,在一較短的時間內,程序

的執行僅局限于某個部分),將主存中一些經常

訪問的信息存放在高速緩存中,減少訪問主存

儲器的次數,可大幅度提高程序執行速度。

W

上章卷儲器管理:一?

?2.磁盤緩存

?由于目前磁盤的I/O速度遠低于對主存的訪問速

度,因此將頻繁使用的一部分磁盤數據和信息,

暫時存放在磁盤緩存中,可減少訪問磁盤的次

數。

1。

年]上章商儲器管理一?

4.2程序的裝入和鏈接''

?在多道程序環境下,要使程序運行,必須先為之

創建進程。而創建進程的第一件事,便是將程序

和數據裝入內存。如何將一個用戶源程序變為一

個可在內存中執行的程序,通常都要經過以下幾

個步驟:首先是要編譯,由編譯程序(Compiler)將

用戶源代碼編譯成若干個目標模塊(Object

Module);其次是鏈接,由鏈接程序(Linker)將編

譯后形成的一組目標模塊,以及它們所需要的庫

函數鏈接在一起,形成一個完整的裝入模塊(Load

Module);最后是裝入,由裝入程序(Loader)將裝

入模塊裝入內存。圖4-2示出了這樣的三步過程。

本節將扼要闡述程序(含數據)的鏈接和裝入過程。

11F

第四章落儲器管理

庫函數

Lib

C

裝入

模塊

.EXE

圖4-2對用戶程序的處理步驟

第回章存儲器管理

4.2.1程序的鏈接

A鏈接:若干目標模塊+庫函數”可裝入模塊

?根據鏈接時間的不同,可把鏈接分成如下三種:

-(1)靜態鏈接。在程序運行之前,先將各目標模塊及

它們所需的庫函數,鏈接成一個完整的裝配模塊,

以后不再拆開。我們把這種事先進行鏈接的方式稱

為靜態鏈接方式。

-(2)裝入時動態鏈接。這是指將用戶源程序編譯后所

得到的一組目標模塊,在裝入內存時,采用邊裝入

邊鏈接的鏈接方式。

-(3)運行時動態鏈接。這是指對某些目標模塊的鏈接,

是在程序執行中需要該(目標)模塊時,才對它進行*

的鏈接。二

13

第四章落儲器管理

?1.靜態鏈接方式(StaticLinking)

A在生成可裝入模塊時(也就是在程序裝入運行前)

完成的鏈接。見圖4-4

?特點:

-一次鏈接,n次運行

-得到完整的可裝入模塊,不可再拆

-不靈活:不管有用與否的模塊都將鏈接到裝入模塊,

同時導致內存利用率較低

-不利于模塊的修改和升級

14

■第四章存儲器管理

0模塊A0模塊A

CALLB;

JSR"L”一

L-1Return;

L-1Return;

L

0模塊B模塊By

CALLC;JSR"L+M”一

M-lReturn;L+M-lReturn;

L+M模塊C-

0模塊C

L+M+N-lReturn;

N-lReturn;

(a)目標模塊(b)裝入模塊

圖4-4程序鏈接示意圖

第四章落儲器管理

?2.裝入時動態鏈接(Load-timeDynamic

Linking)

A用戶源程序經編譯后所得的目標模塊,是在裝

入內存時邊裝入邊鏈接的,即在裝入一個目標

模塊時,若發生一個外部模塊調用事件,將引

起裝入程序去找出相應的外部目標模塊,并將

它裝入內存,還要按照圖4-4所示的方式來修改

目標模塊中的相對地址。

16

W

?3.運行時動態鏈接(Run-timeDynamicLinking)

>裝入時動態鏈接是將所有可能要運行到的模塊都全部

鏈接在一起并裝入內存,顯然這是低效的,因為往往

會有些目標模塊根本就不運行。比較典型的例子是作

為錯誤處理用的目標模塊,如果程序在整個運行過程

中都不出現錯誤,則顯然就不會用到該模塊。

>運行時動態鏈接方式是對裝入時鏈接方式的一種改進。

這種鏈接方式是將對某些模塊的鏈接推遲到程序執行

時才進行鏈接,亦即,在程序執行過程中,當發現一

個被調用模塊尚未裝入內存時,才立即由OS去找到該

模塊并將之裝入內存,把它鏈接到調用者模塊上。凡

在本次執行過程中未被用到的目標模塊,都不會被調

入內存和被鏈接到裝入模塊上,這樣不僅可加快程序

的裝入過程,而且可節省大量的內存空間。

17

W

第四章卷儲器

?4.動態鏈接方式的優點

?便于共享

-多個進程可共用一個DLL模塊,節省了內存。

>為部分裝入提供了條件(運行時動態鏈接)

-一個進程可由若干DLL模塊構成,按需裝入。

?便于模塊的修改和升級

-只要被修改模塊的接口不變,則該模塊的修改不會

引發其它模塊的重新編譯。

?改善了程序的可移植性

-可面向不同的應用環境開發同一功能模塊的不同版

本,根據當前的環境載入匹配的模塊版本。.

18"1^01

?5.動態鏈接方式的缺點

A增加了程序執行時的鏈接開銷。(每次運行都需

鏈接)

A模塊數量眾多,增加了模塊的管理開銷。

第四章落儲器管理

4.2.2程序的裝入

?裝入:可裝入模塊(.EXE)”內存進程

?1.絕對裝入方式(AbsoluteLoadingMode)

?在編譯后、裝入前已產生了絕對地址(內存地

址),裝入時不再作地址重定位,即:裝入內

存前的虛擬地址==裝入內存后的物理地址。

A絕對地址的產生:(1)由編譯器完成;(2)

由程序員編程完成。

A優點:裝入過程簡單,無需地址映射。

A缺點:不適于多道程序系統;過于依賴硬件結

構;不易修改、不靈潔。

20

W

第四章存儲器管理

?2.可重定位裝入方式(RelocationLoading

Mode)

A可裝入模塊在被裝入到內存中時,由裝入程序

來完成程序虛擬地址》內存物理地址的變換

21

第四章落儲器管理

0

10000'「如果不進行地址變:

換,那么這條指令

將無法取到正確的

100011000

LOAD1,2500LOAD1,2500U數值“365”,所以

=>\該指令中的地址應

\該重定位為:

250012500

365365\LOAD1,12500>

15000

程序地址空間-

r1

圖4-3裝入內存時的情況物理內存空間

靜態地址重定位:

指令或數據的內存地址MA

=該指令或數據的虛擬地址VA+該程序在內存中的首地址BA

?第四章存儲器管理一一y?

A可重定位裝入的優缺點:

-優點:

口適用于多道程序系統,提高了內存利用率;由于地址映射

規則簡單,故在地址變換過程中無需硬件變換機構的支持。

-缺點:

口任何進程都要求連續的內存空間;必須將全部模塊都裝入

且裝入后不能再移動位置(因為無法實現動態重定位);不

支持虛擬存儲器技術;不易實現共享。

第四章落儲器管理

?3.動態運行時裝入方式(DynamicRun?

timeLoading)

A出于實際情況,程序在運行過程中的內存位置

可能經常要改變,此時就應采用動態運行時裝

入的方式。

A程序裝入內存后并不立即進行地址變換,而是

等到真正要執行時才由硬件地址變換機構來完

成地址變換,從而得到內存物理地址。

24

W

第四章落儲器管理

“基址寄存器BR

外存程序一側存儲器一側主存

動態地址重定位:

指令或數據的內存地址MA

=該指令或數據的虛擬地址VA+重定位基址寄存器BR

25

?第四章存儲器管理一一y?

A動態運行時裝入的優缺點:

-優點

□os可將一個進程的不同部分分散存放在不連續的內存空間;

可移動進程在內存中的位置(由重定位基址寄存器反映移

動情況);提供了實現虛擬存儲器技術的基礎(可實現部分

模塊裝入);有利于實現模塊共享。

-缺點

口動態重定位需要硬件變換機構的支持;實現較復雜。

第四章落儲器管理

4.3連續分配方式

連續分配方式是指一個進程在內存中必須占

用連續的存儲空間。典型的連續分配方式主要有:

單一連續分配、固定分區分配、動態分區分配、

動態重定位分區分配等。

4.3.1單一連續分配

?把內存分為系統區和用戶區兩部分,系統區僅提

供給OS使用;用戶區是指除系統區以外的全部內

存空間,提供給用戶使用。

?優點:簡單,易于管理

?缺點:只能用于單用戶單任務OS;內存利用率低,

毫無共享性可言。早已淘汰。

27

W

引入:分區存儲管理原理

①將內存分為一些大小相等或不等的分區

(Partition),每個進程可占用一個分區。

②適于多道程序系統,支持多個進程并發執行。

③出現了碎片問題

I.內碎片:被占用分區的尾部未被利用的空間。

II.外碎片:在兩個被占用分區之間的難以利用的小

空閑分區。

④分區管理的數據結構:分區表或分區鏈表。

⑤內存緊湊(Compaction):將各個已占用分區

向內存某端移動,從而使分散的各個小空閑分

區能相鄰,進而合并為一個稍大的空閑分區。.

28

W

第四章落儲器管理

4.3.2固定分區分配

?1.把內存劃分為若干個固定大小的分區,

分區的總數以及各個分區的大小都是恒定

值。

A各分區大小相等

-不靈活;對于小進程而言,內存利用率低,內碎片

嚴重;對于大進程而言,分區大小可能無法滿足需

要,導致無法裝入。

A各分區大小不等

-小分區、中等分區、大分區。適應性較強,可以有

效提高內存利用率。

29

W

立章啟承器管理

?2.固定分區的內存分配

A為了便于內存分配,通常將分區按大小進行排

隊,并為之建立一張分區使用表,其中各表項

包括每個分區的起始地址、大小及狀態(是否已

分配),見圖4-5(a)所示。

A當有一用戶程序要裝入時,由內存分配程序檢

索該表,從中找出一個能滿足要求的、尚未分

配的分區,將之分配給該程序,然后將該表項

中的狀態置為“已分配”;若未找到大小足夠

的分區,則拒絕為該用戶程序分配內存。存儲

空間分配情況如圖4-5(b)所示。

第四章落儲器管理

操作系統

分區號大小/KB起址/KJB狀態20KB

進程A(8K)

11220已分配32KB

進程B(25K)

23232已分配64KJB

36464已分配進程C(40K)

128KBJ

4128128未分配

(a)分區說明表

256KB

(b)存儲空間分配情況

圖4-5固定分區使用表

第四章落儲器管理

?3.固定分區分配的優缺點

A優點

-由于各分區大小固定,故易于實現,管理開銷小。

?缺點

-內碎片的問題不可避免,較大程序不易裝入,故內

存利用率較低;分區數目固定也限制了進程的并發

度。

第四章落儲器管理

4.3.3動態分區分配

?在動態分區分配方式中,各個分區的大小

會在OS的管理下發生改變,分區總數也會

相應地發生變化。

?1.分區分配中的數據結構

?(1)空閑分區表:記錄所有空閑分區情況的二維

表分區號大小/KB起址/KB狀態

11820未分配

232242未分配

3150502未分配

4128750未分配

33

第四章落儲器管理

?(2)空閑分區

鏈:將所有

的空閑分區

鏈接成一個

雙向鏈,如

圖4-6所示。

「0:未分配

Y

-1:已分配

第四章商儲器管理

?2.分區分配算法

>1)首次適應FF算法(FirstFit)

-空閑分區鏈以地址遞增的次序鏈接。在每次分配時,

都從鏈首開始順序查找,直至找到第一個大小能滿

足要求的空閑分區為止;然后再按照程序的大小,

從該分區中劃出一塊內存空間分配給請求者,余下

的空閑分區仍留在空閑鏈中。若從鏈首直至鏈尾都

不能找到一個能滿足要求的分區,則此次內存分配

失敗,返回。

-特點:簡單;高址內存可保留較大的空閑分區;但

低址內存會產生很多碎片分區;查找開銷大。

35

■第四章存儲器管理

A2)循環首次適應NF算法(NextFit)

-該算法是由首次適應FF算法演變而成的:分配空間

不再是每次都從鏈首開始查找,而是從上次找到的

空閑分區的下一個空閑分區開始查找,如果達到鏈

尾則回到鏈首繼續。

-特點:查找開銷小;空閑分區分布更均勻;但較大

分區難以保留。

>3)最佳適應BF算法(BestFit)

-空閑分區鏈表以容量遞增為序組織,每次分配時從

鏈首查找,將第一個滿足空間要求的分區分配出去。

-特點:最接近按需分配原則;較大的分區容易保留;

但會產生很多難以利用的小碎片分區。

>4)最壞適應WF算法(WorstFit)

-空閑分區鏈表以容量遞減為序組織,每次分配時從

鏈首查找,將第一個滿足空間要求的分區分配出去。

-特點:小碎片分區的問題得到了有效的解決;但大

分區也不易保留。

A最壞適應算法與前面所述的首次適應、循環首

次適應、最佳適應算法一起,統稱為順序搜索

法。

37

A5)快速適應QF算法(QuickFit)

-該算法又稱為分類搜索法,是將空閑分區根據其容

量大小進行分類,對于每一類具有相同容量的所有

空閑分區,單獨設立一個空閑分區鏈表,這樣,系

統中存在多個空閑分區鏈表,同時在內存中設立一

張管理索引表,該表的每一個表項對應了一種空閑

分區類型,并記錄了該類型空閑分區鏈表表頭的指

針。空閑分區的分類是根據進程常用的空間大小進

行劃分。

-優點:查找效率高;不會對任何分區產生分割,所

以能保留大的分區;也不會產生內存碎片。

-缺點:分區歸還主存的算法復雜,系統開銷較大;

多樣化的鏈表造成管理開銷大。

第四章落儲器管理

?3?分區分配操作

A1)分配內存

-系統應利用某種分配算法,從空閑分區鏈(表)中找

到所需大小的分區。設請求的分區大小為u.size,表

中每個空閑分區的大小可表示為m.size。若m.size-

u.sizeSsize(size是事先規定的不再切割的剩余分區的

大小),說明多余部分太小,可不再切割,將整個分

區分配給請求者;否則(即多余部分超過size),從該

分區中按請求的大小劃分出一塊內存空間分配出去,

余下的部分仍留在空閑分區鏈(表)中。然后,將分

配區的首址返回給調用者。圖4-7示出了分配流程。

39

第四章落儲器管理

圖4-7內存分配流程

第四章落儲器管理

>2)回收內存

-(1)回收區與插入點的前一個空閑分區F1相鄰接,見圖4-8(a)。

此時應將回收區與插入點的前一分區合并,不必為回收分區分

配新表項,而只需修改其前一分區F1的大小。

-(2)回收分區與插入點的后一空閑分區F2相鄰接,見圖4-8(b)。

此時也可將兩分區合并,也不必分配新表項,用回收區的首址

作為新空閑區的首址,大小為兩者之和。

-(3)回收區同時與插入點的前、后兩個分區鄰接,見圖4-8(c)。

此時將三個分區合并,使用Fl的表項,F1的首址不變,F1的

大小為三者之和,刪除F2的表項。

-(4)回收區既不與F1鄰接,又不與F2鄰接,見圖4-8(d)。這時應

為回收區單獨建立一新表項,填寫回收區的首址和大小,并根

據其首址插入到空閑鏈中的適當位置。

41

w

第四章落儲器管理

(a)(b)(d)

第四章落儲器管理

■例:假設最佳適應法

OS(20K)

進程A(8K)

16K空閑區

進程D(50K)

138K空閑區

進程E(16K)

8K空閑區

如果改為首次適應算法?

43

W

■第四章電鰭器管理

4.3.4伙伴系統(自學內容)

?固定分區和動態分區方式都有不足之處。固定分

區方式限制了活動進程的數目,當進程大小與空

閑分區大小不匹配時,內存空間利用率很低。動

態分區方式算法復雜,回收空閑分區時需要進行

分區合并等,系統開銷較大。伙伴系統方式是對

以上兩種內存方式的一種折衷方案。

?伙伴系統規定,無論已分配分區或空閑分區,其

大小均為2的左次塞,左為整數,七任加,其中:21

表示分配的最小分區的大小,2m表示分配的最大

分區的大小,通常2m是整個可分配內存的大小。

44

第四章落儲器管理

?假設系統的可利用空間容量為2m個字,則系統開

始運行時,整個內存區是一個大小為2m的空閑分

區。在系統運行過程中,由于不斷的劃分,可能

會形成若干個不連續的空閑分區,將這些空閑分

區根據分區的大小進行分類,對于每一類具有相

同大小的所有空閑分區,單獨設立一個空閑分區

雙向鏈表。這樣,不同大小的空閑分區形成了

左(OS公⑼個空閑分區鏈表。

45

當需要為進程分配一個長度為〃的存儲空間時,首先計算

一個,.值,使2*〈脛2],然后在空閑分區大小為21的空閑分

區鏈表中查找。若找到,即把該空閑分區分配給進程。否

則,表明長度為2,?的空閑分區已經耗盡,則在分區大小為

2,+1的空閑分區鏈表中尋找。若存在2汁,的一個空閑分區,

則把該空閑分區分為相等的兩個分區,這兩個分區稱為一

對伙伴,其中的一個分區用于分配,而把另一個加入分區

大小為2,?的空閑分區鏈表中。若大小為2汁1的空閑分區也不

存在,則需要查找大小為2計2的空閑分區,若找到則對其

進行兩次分割:第一次,將其分割為大小為2計1的兩個分

區,一個用于分配,一個加入到大小為2計1的空閑分區鏈

表中;第二次,將第一次用于分配的空閑區分割為2的兩

個分區,一個用于分配,一個加入到大小為2,?的空閑分區

鏈表中。若仍然找不到,則繼續查找大小為2計3的空閑分

區,幺此類推。由此可見匕,,在最壞的情況下,可能需要對

2〃的空訊分區進行上次分割才能得到所需分區。

46

*

?與一次分配可能要進行多次分割一樣,一次日收

也可能要進行多次合并,如回收大小為2%的生拓

分區時,若事先已存在2%的空閑分區時,則應將

其與伙伴分區合并為大小為2計1的空閑分區,若事

先已存在2計1的空閑分區時,又應繼續與其伙伴分

區合并為大小為2汁2的空閑分區,依此類推。

?在伙伴系統中,其分配和回收的時間性能取決于

查找空閑分區的位置和分割、合并空閑分區所花

費的時間。與前面所述的多種方法相比較,由于

該算法在回收空閑分區時,需要對空閑分區進行

合并,所以其時間性能比前面所述的分類搜索算

法差,但比順序搜嚎算法好,而其空間性能則遠

優于前面所述的分莢獨索法,比順序搜索法略差。

*

47

W

立章啟承器管理

4.3.5哈希算法

?哈希算法就是利用哈希快速查找的優點,

以及空閑分區在可利用空間表中的分布規

律,建立哈希函數,構造一張以空閑分區

大小為關鍵字的哈希表,該表的每一個表

項記錄了一個對應的空閑分區鏈表表頭指

針。

?當進行空閑分區分配時,根據所需空閑分

區大小,通過哈希函數計算,即得到在哈

希表中的位置,從中得到相應的空閑分區

鏈表,實現最佳分配策略。

48

W

第四章落儲器管理

4.3.6可重定位分區分配

?1.動態重定位的引入

?在連續分配方式中,必須把一個系統或用戶程序裝入

一連續的內存空間。如果在系統中只有若干個小的分

區,即使它們容量的總和大于要裝入的程序,但由于

這些分區不相鄰接,也無法把該程序裝入內存。例如,

圖4-9(a)中示出了在內存中現有四個互不鄰接的小分區,

它們的容量分別為10KB、30KB、14KB和26KB,其

總容量是80KB。但如果現在有一程序到達,要求獲得

40KB的內存空間,由于必須為它分配一連續空間,故

此程序無法裝入。這種不能被利用的小分區稱為“零

頭”或“碎片”。

W

第四章落儲器管理

操作系統

用戶程序1

用戶程序3

解決辦法:

用戶程序6

用戶程序9

緊湊:通過移動一些

內存分區,將原本離80KB

散的一些內存小碎片

變得相鄰,進而可以

合并為一個稍大的空

閑分區的技術。

(a)緊湊前(b)緊湊后

現在有4個空閑分區,如果有

一個大小為40KB的程序要求

進入內存,如何處理?圖4-9緊湊的示意

5。忠3

第四章落儲器管理

?2.動態重定位的實現

A經過緊湊后,某些用戶程序在內存中的位置發

生了變化,此時若不對程序和數據的地址加以

修改(變換),則程序必將無法執行。為此,在

每次“緊湊”后,都必須對移動了的程序或數

據進行地址重定位。

?增設“重定位寄存器”,每當系統對內存進行

了“緊湊”而使若干程序從內存的某處移至另

一處時,不需對程序做任何修改,只要實時更

新“重定位寄存器”的值即可。

51*

第四章存儲器管理

基址寄存器BR

(重定位寄存器)

10000

10100

12500

15000

程序

外存程序一側存儲器一側主存

圖4-10動態重定位示意圖

動態地址重定位:

指令或數據的內存地址MA

=該指令或數據的虛擬地址VA+重定位基址寄存器BR52

第四章腐儲器管理

?3.動態重定位分區分配算法

A動態重定位分區分配算法與動態分區分配算法

基本上相同,差別僅在于:在這種分配算法中,

增加了緊湊的功能,通常,在找不到足夠大的

空閑分區來滿足用戶需求時進行緊湊。圖4-11

示出了動態重定位分區分配算法。

.第?章啟承器管理

請求分配、)

\^u.size^E^x

*

檢索空閑分區鏈(表)

廠羌法分曉閑分口

^大于

回口>u.size?^ize的個多

1是

進行緊湊形成按動態分區方式

連續空閑區進行各配

;「

修改有關的數據結構一(返回分區號、

修改有關的數據結構

圖4-11動態分區分配算法流程圖

54

第四章落儲器管理

4.3.7有關分區管理的討論

?1.分區存儲管理的特點

A優點:實現了多個進程對內存的共享,有助于

多道程序系統;提高了資源利用率;要求的硬

件支持少;管理簡單,實現容易。

A缺點:內存利用率仍然不高,小碎片多;進程

大小受分區大小的限制;不能部分裝入,難以

實現各分區間的信息共享;無法實現虛存。

55;要劇球

k上章程儲器管理

?2.關于虛存的實現

>虛存:用戶進程所需內存容量只受內存和外存

容量之和的限制的存儲器技術。單純的分區管

理是無法實現虛存的。

Trw

2)對換Swapping

■換出Swap_out:將內存中阻塞且優先級最低的進程

(程序+數據)換到外存交換區,修改其PCB并回收相

應內存。

■換入Swap_in:將外存交換區中靜止就緒且被換出時

間最久的迸程(程序+數據)換入內存并修改其PCB。

■對換分類:

?進程對換(整體對換)

?部分對換(頁面或分段對換)——真正意義上實現虛存

■對換的三個關鍵操作:換出、換入、對換空間

(pagefile.sys)的管理。

■對換缺點:換入換出開銷大。

57

W

第四章落儲器管理

③關于地址變換和內存保護

■地址變換:不實現緊湊時可采用“靜態可重定位

裝入”方式,實現緊湊時必須采用“運行時動態

可重定位裝入”方式。

■內存保護:

?硬件法:為每個進程設置一對上、下界寄存器,或利用

分區的基址寄存器和限長寄存器。若越界則產生地址保

護中斷并轉錯誤處理。

?軟件法(保護鍵法):為被保護分區設置保護鍵開關字段,

針對不同的進程賦予不同的開關代碼,通過檢查兩者是

否匹配來實現讀、寫保護。

?軟硬結合法。

第四章存儲器管理

4.4基本(靜態)分頁存儲管理方式

4.4.1頁式管理的基本原理

A回顧分區分配法:碎片問題嚴重,內存利用率不高;

由于要求連續存放,導致進程的大小仍受分區大小和

內存可用空間的限制;不利于共享;無法實現虛存。

A引入頁式管理的目的:為了減少碎片,為了實現換入/

換出而采用離散存儲,提高內存利用率。

A分頁存儲管理:將一個進程的邏輯地址空間分成若干

個大小相等而片,稱為頁唳頁,并為各國力嗯緘號,

從0開始,如第0頁、第1頁等。相應地,也把內存空間

分成與頁面相同大小的若干個存儲塊,稱為(物理)塊或

頁框(frame),也同樣為它們加以編號,如0#塊、1#塊

等等。在為進程分配內存時以塊為單位,將進程中的

若干人頁分別裝入到多個可以不相鄰接的物理塊中。

由于進程的最后一頁經串裝不滿一塊而形成了不可利

用的碎片,稱之為“頁山碎片”。

59Kg

第四章落儲器管理

?1.頁面

A一個進程的虛擬空間被劃分為若干個長度相等

的頁面(page),通常幾KB?幾十KB為一頁,故

進程的虛地址(邏輯地址)可由頁號P與頁內地址

W所組成。

頁號P頁內地址W

231090

假設這是某系統的分頁地址結構,則該系

統頁長為2io=lO24B即1KB/頁,一個進程

最長允許有214=16384頁即16384KB

60■工

第四章落儲器管理

A與進程邏輯空間的分頁結構類似,物理內存空

間也被劃分為與頁面相等大小的若干物理塊。

A在為進程分配內存時,將進程的N個頁面(必定

連續)裝入到N個內存物理塊(不一定連續)。即:

連續的N個頁面對應裝入不連續的N個物理塊。

頁管理特點:無外碎片的概念;且內碎片必

定于一個物理塊;實現了非連續(離散)方式

增,為虛存的實現提供了基礎;但管理開銷

?關鍵問題:如何將頁面邏輯地址變換為內存物

理地址?

-頁表+硬件地址變換機構

W

?2?頁表(PageMappingTable)

A由于在分頁系統中,允許將進程的n個連續頁離

散地存儲在內存不連續的n個物理塊中,為此,

系統又為每個進程建立了一張頁面映像表,簡

稱頁表。在進程地址空間內的所有頁(0?n),依

次在頁表中有一頁表項,其中記錄了M應頁在

內存中對應的物理塊號,見圖4-12的中間部分。

在配置了頁表后,進程執行時,通過查找該表,

即可找到每頁在內存中的物理塊號。可見,頁

表的作用是實現小頁號到其理塊號的投址映射。

~物理塊號

W

細章啟承器管理

說明:

?頁表負責記錄遂聘

頁面與內存物理塊

的對應關系

?每個進程都有自己

的一張頁表

?頁表的長度由進程

大小和頁面大小共

同決定:比如一進

程為4765B,若頁

面大小為1KB/頁,

則該進程包含5頁

(第0頁?第4頁),即

該戰程的頁表包含

5個表項

63

W

思考幾個問題

①頁面大小一般為2n字節,但具體n有多大?過小怎

樣?過大怎樣?

■過小:則頁表過長,換入/換出效率低,使用和維護的開

銷大。

■過長:頁內碎片大。

②已知邏輯地址和頁面大小,如何計算頁號及頁內

地址?

■頁號=邏輯地址/頁面大小(整除運算)

■頁內地址=邏輯地址%頁面大小(求余運算)

■例:已知頁面大小為1KB/頁,現有一數據的邏輯地址為

2148,問:該數據在哪頁的哪個位置?

?頁號=2148/1024=2,頁內地址=2148%1024=一,

100,即:該數據在該進程的第2頁的相對地址100處名人

64

w

3.靜態頁式管理(基本頁式管理)

>必須將一個進程的所有頁面全部裝入到內存物理塊,

無法實現虛存。

4.動態頁式管理

>允/您二個進程的一部分頁面裝入到內存物理塊。

>采用“請求調頁”或二禪調頁”技術實現了內外存存

儲器的統一管理即對換技術。

>內存中只存放那些經常被執行或將要被執行的頁面,

而不常被執行或近期內不會執行的頁面則存放在外存,

待需要時再按請求式調入。

5.分頁管理的重點

①邏輯地址》物理疝址的地址變換(頁表+硬件地址變

換機構).

②頁面的動態置換技術

65;

第四章落儲器管理

4.4.2地址變換機構

?1.基本的地址變換機構

?地址映射:連續的N個頁面對應于不連續的N個物理塊

-邏輯頁號”物理塊號:查頁表

-頁內地址9塊內地址:兩者相等

?從成本和容量上來考慮,采用寄存器來存儲頁表是不

現實的。因此,頁表大多駐留在內存中,而在系統中

只設置一個頁表寄存器PTR(TableRegister),在其

中存放該進程的頁表在內存的始址和頁表的長度。平

時,進程未執行時,頁表的始址和頁表長度存放在本

進程的PCB中。當調度程序調度到某進程時,才將這

兩個數據裝入頁表寄存器中。因此,在單處理機環境

下,雖然系統中可以運行多個進程,但只需一個頁表

寄存器。

66

W

A地址變換算法

-當某進程被調度執行時,將其PCB中記錄的頁表始

址S和頁表長度L取出來放到“頁表寄存器”中;同

時,分頁地址變換機構會自動將邏輯地址劃分為頁

號P和頁內地址W,然后用頁號P與頁表長度L比較:

若PNL則越界中斷,否則合法,再以頁號P去檢索頁

表,查得該頁P對應的物理塊號,進而算得該塊在內

存的起始地址B,最后B與頁內地址W(即塊內地址)

相加就得到了要訪問的物理地址。這樣便完成了從

邏輯地址到物理地址的變換。圖4-13示出了分頁系

統的地址變換機構。

67

W

第四章落儲器管理

越界中斷

圖4-13分頁系統的地址變換機構

68

第四章存儲器管理

1。

■例:已知頁面長度為1KB/頁,某進程的頁表如圖所

示。現有邏輯地址為100的一條指令LOADR19

[2500]o問:

?試說明該指令的取指過程?

?試說明該指令的取數過程?

頁號塊號

02

13

28

第四章落儲器管理

越界中斷

頁表寄存器邏輯地址100

頁表始址頁表長度3<頁號0頁內地址100

+

頁號物理地址

-0A塊號2塊內地址100

1

2

該指令的物理地址為2148

頁表

邏輯地址為100的指令的取指過程:

?頁號=近科地址/頁長=100/1024=0

?頁內地址=邏輯地址%頁長=100%1024=100

?物理地址=物理塊號*塊長十境內地址=2*1024+100=214870

邏輯地址為100的指令的取教過程(該教的邏輯地址為2500):

?頁號=近科地址/頁長

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論