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

主存管理7.1主存管理概述51.幾個(gè)概念物理地址(絕對(duì)地址、實(shí)地址)

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

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

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

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

程序地址空間01n-1

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

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

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

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

靜態(tài)地址映射

動(dòng)態(tài)地址映射

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

在程序執(zhí)行期間

進(jìn)行地址映射

進(jìn)行地址映射

需軟件

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

重定位裝入程序

重定位寄存器

需花費(fèi)較多CPU時(shí)間

地址變換快

不靈活

靈活

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

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

——在眾多個(gè)請(qǐng)求者中選擇一個(gè)請(qǐng)求者的原則。放置策略

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

——決定信息裝入主存的時(shí)機(jī)預(yù)調(diào)策略：預(yù)先將信息調(diào)入主存請(qǐng)調(diào)策略：當(dāng)需要信息時(shí)，將信息調(diào)入主存淘汰策略

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

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

20KB上界寄存器

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

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

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

20KB限長寄存器

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

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

32KB

0

256KB1主存20KBos20KB

0

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

14KB20KB

0

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

64KB20KB

0

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

100KB20KB

0

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

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

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

等待隊(duì)列頭指針

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

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

分配標(biāo)志flag

大小size

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

0

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

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

首次匹配(首次適應(yīng)算法)

最佳匹配(最佳適應(yīng)算法)

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

作業(yè)A

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

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

作業(yè)A

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

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

作業(yè)A

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

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

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

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

20KB

030KB100KB

020KB160KB

05KB210KB

046KB

(a)最佳適應(yīng)算法的空閑區(qū)隊(duì)列160KB

05KB100KB

020KB20KB

030KB210KB

046KB

(a)最壞適應(yīng)算法的空閑區(qū)隊(duì)列210KB

046KB20KB

030KB100KB

020KB160KB

05KB

三種放置策略的討論首次適應(yīng)算法

作業(yè)A要求18KB

作業(yè)B要求25KB

作業(yè)C要求30KB

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

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

20KB

030KB100KB

020KB160KB

05KB210KB

046KB

最佳適應(yīng)算法

作業(yè)A要求18KB

作業(yè)B要求25KB

作業(yè)C要求30KB

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

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