第7章操作系統 主存管理

主存管理7.1主存管理概述51.幾個概念物理地址(絕對地址、實地址)

物理地址是計算機主存單元的真實地址，又稱為絕對地址或實地址。主存空間

物理地址的集合所對應的空間組成了主存空間。邏輯地址(相對地址、虛地址)

用戶的程序地址(指令地址或操作數地址)均為邏輯地址。作業地址空間用戶程序所有的邏輯地址集合對應的空間。6作業地址空間與主存空間主存空間01m-1作業1地址空間01n-1作業i地址空間01k-1

程序局部性原理：一個進程在執行過程中，其大部分程序和數據并不經常被訪問到。在一段時間內，整個程序的執行僅限于程序中的某一部分。虛擬存儲器：計算機系統在處理應用程序時，只裝入部分程序代碼和數據就啟動運行，由操作系統和硬件相互配合完成主存和輔存之間的動態調度，這樣計算機系統好像為用戶提供了一個存儲容量比主存大得多的存儲器，這一個存儲器稱之為虛擬存儲器。實現虛擬存儲器的物質基礎有相當容量的輔存，足以存放應用程序的虛地址空間實現虛擬存儲器的物質基礎有一定容量的主存,存放進入主存的多進程的信息地址變換機構虛擬存儲器的容量：主存與輔存的容量之和確定，還受CPU尋址位數的限制，如32位為4G。2.主存共享方式大小不等的區域分區存儲管理段式存儲管理大小相等的區域頁式存儲管理二者結合段頁式存儲管理3.程序的邏輯組織一維地址結構一個程序是一個連續、線性的地址結構；確定線性地址空間中的指令地址或操作數地址只需要一個信息。

程序地址空間01n-1

二維地址結構一個程序由若干個分段組成，每個分段是一個連續的地址區；確定任一地址空間中的指令地址或操作數地址需要兩個信息，一是該信息所在的分段，另一個是該信息在段內的偏移量。code_addr4KB10代碼分段data_addr3KB10數據分段stack_addr2KB10棧段117.2主存管理功能1.主存管理功能實現邏輯地址到物理主存地址的映射主存分配存儲保護主存擴充

2.地址映射什么是地址映射

將程序地址空間中使用的邏輯地址變換成主存中的物理地址的過程，稱為地址映射。movr1,[500]1230100500599作業地址空間movr1,[500]12301000110015001599256k-1存儲空間地址映射的時機和類別程序編寫或編譯時映射在程序編寫或程序編譯時確定虛、實地址之間的對應關系，結果是一個不能浮動的程序模塊。申請主存的時候，必須明確提出申請的主存的容量和起始地址。靜態映射在作業裝入過程中隨即進行的地址變換方式稱為靜態地址映射。缺點：一個已經開始執行的程序是無法在主存中移動。程序因某種原因被換到輔存后，再調入主存，必須返回原來的位置load1,23053270程序虛擬地址空間內存空間load1,12305327100001100012305無需硬件支持動態映射在程序執行期間，隨著每條指令和數據的訪問自動地連續地進行地址映射，這種地址變換方式稱為動態地址映射特點：裝入時不加任何修改，但在每次訪問內存單元前才進行地址變換。系統中設置重定位寄存器。load1,23053270程序虛擬地址空間內存空間load1,23053271000011000123052305

+10000VRBR11靜態地址映射與動態地址映射的區別

靜態地址映射

動態地址映射

在作業裝入過程中

在程序執行期間

進行地址映射

進行地址映射

需軟件

需硬件地址變換機構

重定位裝入程序

重定位寄存器

需花費較多CPU時間

地址變換快

不靈活

靈活

3.主存分配構造分配用的數據結構

主存資源信息塊：等待隊列；空閑區隊列；主存分配程序制定策略主存分配策略

——在眾多個請求者中選擇一個請求者的原則。放置策略

——在可用資源中，選擇一個空閑區的原則。調入策略

——決定信息裝入主存的時機預調策略：預先將信息調入主存請調策略：當需要信息時，將信息調入主存淘汰策略

——在主存中沒有可用的空閑區(對某一作業而言)時，決定哪些信息從主存中移走，即確定淘汰已占用的內存區的原則。實施主存分配與回收4.存儲保護什么是存儲保護在多用戶環境中，主存儲器按區分配給各用戶程序使用。為了互不影響，必須由硬件(軟件配合)保證各用戶程序只能在給定的存儲區域內活動，這種措施叫做存儲保護。實現方法界地址保護存儲鍵保護界地址保護上下界防護例：作業大小為4KB，主存首址為20KB。

movr1,[500]123020KB256KB1存儲空間24KB下界寄存器

20KB上界寄存器

24KB如何判斷是否越界？若20KB≤D＜24KB

允許訪問；界地址保護基地址、限長防護例：作業大小為4KB，主存首址為20KB。如何設置基址、限長寄存器內容？如何判斷是否越界？若邏輯地址＜4K，允許訪問；否則發生越界中斷

movr1,[500]123020KB256KB1存儲空間24KB基址寄存器

20KB限長寄存器

4KB保護鍵法：軟件和硬件結合的方法。為每一個被保護存儲塊分配一個單獨的保護鍵。對不同進程賦予不同的開關代碼，保護鍵可設置成對RW同時進行保護或只對R、W進行單獨保護的。7.3分區存儲管理及存在的問題分區管理基本原理分區：由系統操作員或操作系統把內存空間分成若干個大小不等的區域，稱為分區。基本原理：給每個內存中的作業劃分一塊適當大小的存儲區，以連續存儲各作業的程序和數據。要求：一個分區只裝一個作業。1.固定分區法分區事先已經劃分好，分區大小不能改變。數據結構分區說明表：內存的分配釋放、存儲保護以及地址變換等都通過分區說明表進行。分區號分區長度起始地址狀態OS(8K)用戶分區1(16K)用戶分區2(16K)用戶分區3(32K)分區號起始地址長度狀態18K16K0224K16K0340K32K分區說明表Job1(20K)0Job1084024缺點：各分配分區可能造成碎片（零頭）；程序大小受分區空間大小的限制。2.動態分區分配什么是動態分區分配

在處理作業的過程中，建立分區，依用戶請求的大小分配分區。作業1申請

32KB

0

256KB1主存20KBos20KB

0

52KB256KB1主存os作業1作業2申請

14KB20KB

0

52KB66KB256KB1主存os作業1作業2作業3申請

64KB20KB

0

52KB66KB130KB256KB1主存os作業1作業2作業3作業4申請

100KB20KB

0

52KB66KB130KB230KB256KB1主存os作業1作業2作業3作業4作業5申請

50KB動態分區的分配過程

動態分區的回收過程

作業2

完成作業4完成20KB

0

52KB66KB130KB230KB256KB1主存作業1作業2作業3作業4os20KB

0

52KB66KB130KB230KB256KB1主存作業1作業3作業4os20KB

0

52KB66KB130KB230KB256KB1主存os作業1作業3分區的分配與回收分區分配思路依申請者所要求的主存區的大小，分區分配程序在自由主存隊列中找一個滿足用戶需要的空閑塊；若找到了所需的空閑區，有兩種情況空閑區與要求的大小相等，將該空閑區分配并從隊列中摘除；空閑區大于所要求的的大小，將空閑區分為兩部分：一部分成為已分配區，建立已分配區的描述器；剩下部分仍為空閑區。返回所分配區域的首址；否則，告之不能滿足要求。分區回收思路檢查釋放分區(即為回收分區)在主存中的鄰接情況；若上、下鄰接空閑區，則合并，成為一個連續的空閑區；若回收分區不與任何空閑區相鄰接，建立一個新的空閑區，并加入到空閑區隊列中。上空閑區下空閑區上空閑區下空閑區2.動態分區分配分區分配結構主存資源信息塊(M_RIB)分區描述器(PD)

等待隊列頭指針

空閑區隊列頭指針

主存分配程序入口地址M_RIBflag：為0——空閑區為1——已分配區size：分區大小next：空閑區——自由主存隊列中的勾鏈字已分配區——此項為零。

分配標志flag

大小size

勾鏈字nextPD22空閑區隊列結構20KB

0

52KB66KB130KB230KB256KB1主存os作業1作業3作業452KBm-rib

空閑區隊列230KB014KB026KB253.放置策略什么是放置策略選擇空閑區的策略，稱為放置策略。常用的放置策略——

首次匹配(首次適應算法)

最佳匹配(最佳適應算法)

最壞匹配(最壞適應算法)首次適應算法首次適應算法是將輸入的作業放置到主存里第一個足夠裝入它的地址最低的空閑區中。

作業A

18KB空閑區隊列結構空閑區地址由低到高排序

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os特點：優先利用內存低地址部分的空閑區。優點：保留了高地址部分的大空閑區。缺點：低地址端留下許多難以利用的很小空閑分區（碎片）；增加查找可用空閑分區開銷。最佳適應算法最佳適應算法是將輸入的作業放置到主存中與它所需大小最接近的空閑區中。

作業A

18KB空閑區隊列結構空閑區大小由小到大排序

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os特點：優先利用了大小與程序要求最接近的空閑區。優點：保留了大空閑區。缺點：剩下的空閑區很小，且數量較多。最壞適應算法最壞適應算法是將輸入的作業放置到主存中與它所需大小差距最大的空閑區中。

作業A

18KB空閑區隊列結構空閑區大小由大到小排序

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os特點：總是挑選出最大的分區分配給程序。優點：分配給程序后剩下的空閑區較大，可能能裝下其它作業。缺點：最大空閑區總是首先被分配而進行劃分，難于滿足大作業的要求。三種放置策略的討論作業A要求18KB；作業B要求25KB；作業C要求30KB。用首次適應算法、最佳適應算法、最壞適應算法來處理該作業序列，看哪種算法合適。

三種放置策略的討論首次適應算法、最佳適應算法、最壞適應算法的隊列結構。

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os(a)首次適應算法的空閑區隊列

20KB

030KB100KB

020KB160KB

05KB210KB

046KB

(a)最佳適應算法的空閑區隊列160KB

05KB100KB

020KB20KB

030KB210KB

046KB

(a)最壞適應算法的空閑區隊列210KB

046KB20KB

030KB100KB

020KB160KB

05KB

三種放置策略的討論首次適應算法

作業A要求18KB

作業B要求25KB

作業C要求30KB

首次適應算法對該作業序列是不合適的

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os(a)首次適應算法的空閑區隊列

20KB

030KB100KB

020KB160KB

05KB210KB

046KB

最佳適應算法

作業A要求18KB

作業B要求25KB

作業C要求30KB

最佳適應算法對該作業序列是合適的

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1