非連續(xù)分配允許一個(gè)程序分散地裝入到不相鄰的內(nèi)存分區(qū)中,根據(jù)分區(qū)的大小是否固定分為分頁(yè)存儲(chǔ)管理方式和分段存儲(chǔ)管理方式。
分頁(yè)存儲(chǔ)管理方式中,又根據(jù)運(yùn)行作業(yè)時(shí)是否要把作業(yè)的所有頁(yè)面都裝入內(nèi)存才能運(yùn)行分為基本分頁(yè)存儲(chǔ)管理方式和請(qǐng)求分頁(yè)存儲(chǔ)管理方式。
1、基本分頁(yè)存儲(chǔ)管理方式
固定分區(qū)會(huì)產(chǎn)生內(nèi)部碎片,動(dòng)態(tài)分區(qū)會(huì)產(chǎn)生外部碎片,這兩種技術(shù)對(duì)內(nèi)存的利用率都比較低。我們希望內(nèi)存的使用能盡量避免碎片的產(chǎn)生。這就引入了分頁(yè)的思想:把主存空間劃分為大小相等且固定的塊,塊相對(duì)較小,作為主存的基本單位。每個(gè)進(jìn)程也以塊為單位進(jìn)行劃分,進(jìn)程在執(zhí)行時(shí),以塊為單位逐個(gè)申請(qǐng)主存中的塊空間。
分頁(yè)的方法從形式上看賣相分區(qū)相等的固定分區(qū)技術(shù),分區(qū)管理不會(huì)產(chǎn)生外部碎片。但它又有本質(zhì)的區(qū)別:塊的大小相對(duì)分區(qū)要小很多,而且進(jìn)程也按照塊進(jìn)行劃分,進(jìn)程運(yùn)行時(shí)按塊申請(qǐng)主存可用空間并執(zhí)行。這樣,進(jìn)程只會(huì)在為最后一個(gè)不完整的塊申請(qǐng)一個(gè)主存塊空間時(shí),才產(chǎn)生主存碎片,所以盡管會(huì)產(chǎn)生內(nèi)部碎片,但是這種碎片相對(duì)進(jìn)程來(lái)說(shuō)也是很小的,每個(gè)進(jìn)程平均產(chǎn)生半個(gè)塊大小的內(nèi)部碎片(也稱頁(yè)內(nèi)碎片)
(1)分頁(yè)存儲(chǔ)的幾個(gè)基本概念
①頁(yè)面和頁(yè)面大小
進(jìn)程中的塊稱為頁(yè)(Page),內(nèi)存中的塊稱為頁(yè)框(Page Frame,或頁(yè)幀)。外存也以同樣的單位進(jìn)行劃分,直接稱為塊(Block)。進(jìn)程在執(zhí)行時(shí)需要申請(qǐng)主存空間,就是要為每個(gè)頁(yè)面分配主存中的可用頁(yè)框,這就產(chǎn)生了頁(yè)和頁(yè)框的一一對(duì)應(yīng)。
為方便地址轉(zhuǎn)換,頁(yè)面大小應(yīng)是2的整數(shù)冪。同時(shí)頁(yè)面大小應(yīng)該適中。如果頁(yè)面太小,會(huì)使進(jìn)程中的頁(yè)面過(guò)多,這樣頁(yè)表就過(guò)長(zhǎng),占用大量?jī)?nèi)存,而且會(huì)增加硬件地址轉(zhuǎn)換的開銷,降低頁(yè)面換入換出的效率;頁(yè)面過(guò)大又會(huì)使頁(yè)內(nèi)碎片增大,降低內(nèi)存的利用率。所以頁(yè)面的大小應(yīng)該適中,考慮到內(nèi)存效率和時(shí)間效率的權(quán)衡。
②地址結(jié)構(gòu)。分頁(yè)存儲(chǔ)管理的邏輯地址結(jié)構(gòu):
地址結(jié)構(gòu)包含兩部分:前一部分為頁(yè)號(hào)P,后一部分為頁(yè)內(nèi)偏移量W。地址長(zhǎng)度為32位,其中0-11位為頁(yè)內(nèi)地址,即每頁(yè)大小為4KB;12-31位為頁(yè)號(hào),地址空間最多允許有2^20頁(yè)。
③頁(yè)表。為了便于在內(nèi)存中找到進(jìn)程的每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊,系統(tǒng)為每個(gè)進(jìn)程建立一張頁(yè)表,記錄頁(yè)面在內(nèi)存中對(duì)應(yīng)的物理號(hào),頁(yè)表 一般存放在內(nèi)存中。
在配置了頁(yè)表后,進(jìn)程執(zhí)行時(shí)通過(guò)查找該表,即可找到每頁(yè)在內(nèi)存中的物理塊號(hào)。可見(jiàn),頁(yè)表的作用是實(shí)現(xiàn)頁(yè)號(hào)到物理塊號(hào)的地址映射。
(2)基本地址的變換機(jī)構(gòu)
地址變換機(jī)構(gòu)的任務(wù)是將邏輯地址轉(zhuǎn)換為內(nèi)存中物理地址,地址變換是借助于頁(yè)表實(shí)現(xiàn)的。
在系統(tǒng)中通常設(shè)置一個(gè)頁(yè)表寄存器(PTR),存放頁(yè)表在內(nèi)存的始址F和頁(yè)表長(zhǎng)度M,進(jìn)程未執(zhí)行時(shí),頁(yè)表的始址和長(zhǎng)度存放在進(jìn)程控制塊中,當(dāng)進(jìn)程執(zhí)行時(shí),才將頁(yè)表始址和長(zhǎng)度存入頁(yè)表寄存器。設(shè)頁(yè)面大小為L(zhǎng),邏輯地址A到物理地址E的變換過(guò)程如下:
①計(jì)算頁(yè)號(hào)P(P=A/L)和頁(yè)內(nèi)偏移量W(w=A%L)
②比較頁(yè)號(hào)P和頁(yè)表長(zhǎng)度M,若P>=M,則產(chǎn)生越界中斷,否則繼續(xù)執(zhí)行。
③頁(yè)表中P對(duì)應(yīng)的頁(yè)表項(xiàng)地址=頁(yè)表起始地址F+頁(yè)號(hào)*頁(yè)表項(xiàng)長(zhǎng)度,取出該頁(yè)表項(xiàng)內(nèi)容b,即為物理塊號(hào)。
④計(jì)算E=b*L+W
以上整個(gè)地址變換過(guò)程均是由硬件自動(dòng)完成的。
假如,頁(yè)面大小L為1K字節(jié),頁(yè)號(hào)2對(duì)應(yīng)的物理塊為b=8,計(jì)算邏輯地址A=2500的物理地址 E的過(guò)程如下
p=2500/1K=2;
w=2500%1K=452;
查找得到頁(yè)號(hào)2對(duì)應(yīng)的物理塊的塊號(hào)為8,E=8*1024+452=8644.
下面討論分頁(yè)管理方式存在的兩個(gè)主要問(wèn)題:
①每次訪存操作都需要進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換,地址轉(zhuǎn)換過(guò)程必須足夠快,否則訪存速度會(huì)降低。
②每個(gè)進(jìn)程引入了頁(yè)表,用于存儲(chǔ)映射機(jī)制,頁(yè)表不能太大,否則內(nèi)存利用率會(huì)降低。
(3)具有快表的地址變換機(jī)構(gòu)
由上面介紹的地址變換過(guò)程可知。若頁(yè)表全部放在內(nèi)存中,則存取一個(gè)數(shù)據(jù)或一條指令至少要訪問(wèn)兩次內(nèi)存
第一次是訪問(wèn)頁(yè)表,確定所存取的數(shù)據(jù)或指令的物理地址
第二次才根據(jù)該地址存取數(shù)據(jù)或指令。
顯然,這種方法比通常執(zhí)行指令的速度慢了一半。
為此,在地址變換機(jī)構(gòu)中增設(shè)了一個(gè)具有并行查找能力的高速緩存存儲(chǔ)器——塊表,又稱為聯(lián)想寄存器(TLB),用來(lái)存放當(dāng)前訪問(wèn)的若干頁(yè)表項(xiàng),以加速地址變換的過(guò)程。于此對(duì)應(yīng),主存中的頁(yè)表也常稱為慢表。
在具有快表的分頁(yè)機(jī)制中,地址的變換過(guò)程:
①CPU給出邏輯地址后,由硬件地址進(jìn)行地址轉(zhuǎn)換并將頁(yè)號(hào)送入高速地址緩沖寄存器,并將此頁(yè)號(hào)與快表中的所有頁(yè)號(hào)進(jìn)行比較。
②如果找到匹配的頁(yè)號(hào), 說(shuō)明所要訪問(wèn)的頁(yè)表項(xiàng)在塊表中,則直接從中取出該頁(yè)所對(duì)應(yīng)的頁(yè)框號(hào),與頁(yè)內(nèi)偏移量拼接成物理地址。這樣存取數(shù)據(jù)僅一次訪存便可實(shí)現(xiàn)。
③如果沒(méi)有找到,則需要訪問(wèn)主存中的頁(yè)表,在讀出頁(yè)表項(xiàng)后,應(yīng)同時(shí)將其存入快表,以便后面可能的再次訪問(wèn)。但若快表已滿,則必須按照一定的算法對(duì)舊的頁(yè)表進(jìn)行替換。
注意:有些處理機(jī)設(shè)計(jì)為塊表和慢表同時(shí)查找,如果在塊表中查找成功則終止慢表的查找。
一般塊表的命中率可以達(dá)到90%以上,這樣,分頁(yè)帶來(lái)的速度損失降低到10%以下。快表的有效性是基于局部性原理。這在后面的虛擬內(nèi)存中將具體討論。
(4)兩級(jí)頁(yè)表
第二個(gè)問(wèn)題:由于引入了分頁(yè)管理,進(jìn)程在執(zhí)行時(shí)不需要將所有頁(yè)調(diào)入內(nèi)存頁(yè)框中,而只要將保存有映射關(guān)系的頁(yè)表調(diào)入內(nèi)存即可。但是我們?nèi)匀恍枰紤]頁(yè)表的大小。以32位邏輯空間,頁(yè)面大小4KB,頁(yè)表項(xiàng)大小4B為例,若要實(shí)現(xiàn)進(jìn)程對(duì)全部邏輯空間的映射,則每個(gè)進(jìn)程需要(2^32/4KB)2^20,約100萬(wàn)個(gè)頁(yè)表項(xiàng)。也就是說(shuō),每個(gè)進(jìn)程僅頁(yè)表這一項(xiàng)就需要4MB主存空間,這顯然是不切合實(shí)際的。
而即便不考慮對(duì)全部邏輯地址空間進(jìn)行映射的情況,一個(gè)邏輯地址空間稍大的進(jìn)程,其頁(yè)表大小也可能是過(guò)大的。
①進(jìn)程舉例(全部放入內(nèi)存)
以一個(gè)40MB的進(jìn)程為例,頁(yè)表項(xiàng)共40KB(40MB/4KB*4B),如果將所有頁(yè)表項(xiàng)內(nèi)容保存在內(nèi)存中,那么需要(40KB/4KB)10個(gè)內(nèi)存頁(yè)框來(lái)把保存整個(gè)頁(yè)表。整個(gè)進(jìn)程大小約為(40MB/4KB)1萬(wàn)個(gè)頁(yè)面,而實(shí)際執(zhí)行時(shí)只需要幾十個(gè)頁(yè)面進(jìn)入內(nèi)存頁(yè)框就可以運(yùn)行,但如果要求10個(gè)頁(yè)面大小的頁(yè)表必須全部進(jìn)入內(nèi)存,這相對(duì)實(shí)際執(zhí)行的幾十個(gè)進(jìn)程頁(yè)面的大小來(lái)說(shuō),肯定是降低了內(nèi)存利用率的;從另一方面來(lái)講,這10頁(yè)的頁(yè)表項(xiàng)也并不需要同時(shí)保存在內(nèi)存中,因?yàn)榇蠖鄶?shù)情況下,映射所需要的頁(yè)表項(xiàng)都在頁(yè)表的同一頁(yè)面中。
解決方案:
為了壓縮頁(yè)表,我們將頁(yè)表映射的思想進(jìn)一步延伸,就可以得到二級(jí)分頁(yè),即使用層次結(jié)構(gòu)的頁(yè)表:將頁(yè)表的10頁(yè)空間也進(jìn)行地址映射,建立上一級(jí)頁(yè)表,用于存儲(chǔ)頁(yè)表的映射關(guān)系。這里對(duì)頁(yè)表的10個(gè)頁(yè)面進(jìn)行映射只需要10個(gè)頁(yè)表項(xiàng),所以上一級(jí)頁(yè)表只需要1頁(yè)就足夠(可以存儲(chǔ)2^10=1024個(gè)頁(yè)表項(xiàng))。在進(jìn)程執(zhí)行時(shí),只需要將1頁(yè)的上一級(jí)頁(yè)表調(diào)入內(nèi)存即可,進(jìn)程的頁(yè)表和進(jìn)程本身的頁(yè)面,可以在后面的執(zhí)行中再調(diào)入內(nèi)存。
②系統(tǒng)舉例(頁(yè)表理論占用最大內(nèi)存)
以上面提到的條件:32位邏輯地址空間、頁(yè)面大小4kB、頁(yè)表項(xiàng)大小4B,以字節(jié)為編址單位,我們就這個(gè)條件來(lái)構(gòu)造一個(gè)合適這個(gè)條件的頁(yè)表結(jié)構(gòu)。頁(yè)面大小為4KB,則頁(yè)內(nèi)偏移址為log2 4K=12位,頁(yè)號(hào)部分為20位,若不采用分級(jí)頁(yè)表,那么光頁(yè)表就要占用2^20*4B/4KB=1024頁(yè)(頁(yè)框),而這大大超過(guò)了許多進(jìn)程自身需要的頁(yè)面,對(duì)于內(nèi)存來(lái)說(shuō)是非常浪費(fèi)資源的,而且查詢頁(yè)表工作也變得十分不便,試想若把這些頁(yè)表放在連續(xù)的空間中,查詢對(duì)應(yīng)的物理頁(yè)號(hào)的時(shí)候可以通過(guò)頁(yè)表首頁(yè)地址+頁(yè)號(hào)*4B的形式得到,而這種方法查詢起來(lái)雖然相對(duì)方便,但是連續(xù)的1024頁(yè)對(duì)于內(nèi)存的要求實(shí)在太高,并且上面說(shuō)到了其中大多數(shù)頁(yè)面都是不會(huì)用到的,所以這種方法并不具有可行性。
解決方案:
如果不把這些頁(yè)表放在連續(xù)的空間中,我們就需要一張索引表來(lái)告訴我們第幾張應(yīng)該去哪找,這就能解決頁(yè)表的查詢問(wèn)題,并且不用把所有的頁(yè)表都調(diào)入內(nèi)存,只有需要它的時(shí)候才調(diào)入(虛擬存儲(chǔ)器思想),這就能解決占用內(nèi)存空間過(guò)大的問(wèn)題。
你也許會(huì)發(fā)現(xiàn)了這個(gè)方案和當(dāng)初引進(jìn)頁(yè)表機(jī)制的方式一模一樣,實(shí)際上就是構(gòu)建一個(gè)頁(yè)表的頁(yè)表,也就是二級(jí)頁(yè)表。為了查詢的方便,頂級(jí)頁(yè)表大小設(shè)立一個(gè)頁(yè)面,那么頂級(jí)頁(yè)表共可以容納4KB/4B=1K個(gè)頁(yè)表項(xiàng),則它占用的地址位數(shù)為log2 1K=10位,而之前計(jì)算過(guò)頁(yè)內(nèi)偏移地址占用了12位,那么32位的邏輯地址空間就剩下10位,正好使得二級(jí)頁(yè)表的大小在一頁(yè)之內(nèi),這樣我們就得到了路基地址空間的格式:
二級(jí)頁(yè)表實(shí)際上就是在原有頁(yè)表結(jié)構(gòu)上再加了一層頁(yè)表
建立多級(jí)頁(yè)表的目的在于建立索引,這樣不用浪費(fèi)主存空間去存儲(chǔ)無(wú)用的頁(yè)表項(xiàng),也不用盲目地順序式查找頁(yè)表項(xiàng),而建立索引的要求是最高一級(jí)頁(yè)表項(xiàng)不超過(guò)一頁(yè)的大小。
-
存儲(chǔ)
+關(guān)注
關(guān)注
13文章
4533瀏覽量
87464 -
操作系統(tǒng)
+關(guān)注
關(guān)注
37文章
7152瀏覽量
125595
發(fā)布評(píng)論請(qǐng)先 登錄
鴻道Intewell操作系統(tǒng):人形機(jī)器人底層操作系統(tǒng)
鴻道Intewell操作系統(tǒng)的Linux實(shí)時(shí)拓展方案

國(guó)產(chǎn)銀河麒麟操作系統(tǒng)V10和星光麒麟V1.0操作系統(tǒng)如何選擇?

deepin操作系統(tǒng)介紹

如何在windows上emulate不同操作系統(tǒng)
什么是虛擬內(nèi)存分頁(yè) Windows系統(tǒng)虛擬內(nèi)存優(yōu)化方法
什么是嵌入式操作系統(tǒng)?
SDRAM同步動(dòng)態(tài)隨機(jī)存儲(chǔ)器的操作說(shuō)明

評(píng)論