第7章操作系統(tǒng) 主存管理

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

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

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

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

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

程序地址空間01n-1

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

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

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

+10000VRBR11靜態(tài)地址映射與動態(tài)地址映射的區(qū)別

靜態(tài)地址映射

動態(tài)地址映射

在作業(yè)裝入過程中

在程序執(zhí)行期間

進行地址映射

進行地址映射

需軟件

需硬件地址變換機構(gòu)

重定位裝入程序

重定位寄存器

需花費較多CPU時間

地址變換快

不靈活

靈活

3.主存分配構(gòu)造分配用的數(shù)據(jù)結(jié)構(gòu)

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

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

——在可用資源中，選擇一個空閑區(qū)的原則。調(diào)入策略

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

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

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

20KB上界寄存器

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

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

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

20KB限長寄存器

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

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

32KB

0

256KB1主存20KBos20KB

0

52KB256KB1主存os作業(yè)1作業(yè)2申請

14KB20KB

0

52KB66KB256KB1主存os作業(yè)1作業(yè)2作業(yè)3申請

64KB20KB

0

52KB66KB130KB256KB1主存os作業(yè)1作業(yè)2作業(yè)3作業(yè)4申請

100KB20KB

0

52KB66KB130KB230KB256KB1主存os作業(yè)1作業(yè)2作業(yè)3作業(yè)4作業(yè)5申請

50KB動態(tài)分區(qū)的分配過程

動態(tài)分區(qū)的回收過程

作業(yè)2

完成作業(yè)4完成20KB

0

52KB66KB130KB230KB256KB1主存作業(yè)1作業(yè)2作業(yè)3作業(yè)4os20KB

0

52KB66KB130KB230KB256KB1主存作業(yè)1作業(yè)3作業(yè)4os20KB

0

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

等待隊列頭指針

空閑區(qū)隊列頭指針

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

分配標志flag

大小size

勾鏈字nextPD22空閑區(qū)隊列結(jié)構(gòu)20KB

0

52KB66KB130KB230KB256KB1主存os作業(yè)1作業(yè)3作業(yè)452KBm-rib

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

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

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

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

作業(yè)A

18KB空閑區(qū)隊列結(jié)構(gòu)空閑區(qū)地址由低到高排序

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

作業(yè)A

18KB空閑區(qū)隊列結(jié)構(gòu)空閑區(qū)大小由小到大排序

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

作業(yè)A

18KB空閑區(qū)隊列結(jié)構(gòu)空閑區(qū)大小由大到小排序

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

三種放置策略的討論首次適應算法、最佳適應算法、最壞適應算法的隊列結(jié)構(gòu)。

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

20KB

030KB100KB

020KB160KB

05KB210KB

046KB

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

05KB100KB

020KB20KB

030KB210KB

046KB

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

046KB20KB

030KB100KB

020KB160KB

05KB

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

作業(yè)A要求18KB

作業(yè)B要求25KB

作業(yè)C要求30KB

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

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

20KB

030KB100KB

020KB160KB

05KB210KB

046KB

最佳適應算法

作業(yè)A要求18KB

作業(yè)B要求25KB

作業(yè)C要求30KB

最佳適應算法對該作業(yè)序列是合適的

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