操作系統(tǒng)第四章-2016

14存儲器管理

存儲器是計算機(jī)的重要組成部分,存儲器是一種寶貴且緊俏的資源,如何對存儲器有效的管理不但直接影響到存儲器的利用率,還影響到系統(tǒng)的性能.本章討論的主要對象是內(nèi)存。由于對外存的管理與對內(nèi)存的管理相似，只是用途不同，而外存主要用來存放文件，故將在磁盤存儲器管理中介紹。2本章的主要內(nèi)容:存儲器的層次結(jié)構(gòu)；程序的裝入和鏈接；連續(xù)分配存儲管理方式對換分頁存儲管理方式分段存儲管理方式3

4.1存儲器的層次結(jié)構(gòu)

在計算機(jī)執(zhí)行時，幾乎每一條指令都涉及對存儲器的訪問，因此要求對存儲器的訪問速度能跟的上處理機(jī)的運行速度。此外還要求存儲器具有非常大的容量，而且存儲器的價格還應(yīng)很便宜。對于這樣十分嚴(yán)格的三個條件，目前是無法同時滿足的。于是，在現(xiàn)代計算機(jī)系統(tǒng)中都無一例外地采用了多層結(jié)構(gòu)的存儲器系統(tǒng)。44.1.1多層結(jié)構(gòu)的存儲器系統(tǒng)對于通用計算機(jī)而言，存儲層次至少應(yīng)具有三級：最高層為ＣＰＵ寄存器，中間為主存，最底層是輔存。在較高檔的計算機(jī)中，還可以根據(jù)具體的功能細(xì)分為寄存器、高速緩存、主存儲器、磁盤緩存、固定磁盤、可移動存儲介質(zhì)等６層。5計算機(jī)系統(tǒng)存儲層次示意圖如右圖所示：在存儲器層次中，層次越高（越靠近ＣＰＵ），存儲介質(zhì)的訪問速度越快，價格也越高，相對所配置的存儲容量也越小。其中，寄存器、高速緩存、主存儲器和磁盤緩存均屬于操作系統(tǒng)存儲管理的管轄范疇，掉電后，它們中存儲的信息不再存在。而低層的固定磁盤和可移動存儲介質(zhì)則屬于設(shè)備管理的管理范疇，它們存儲的信息將被長期保存。64.1.2主存儲器與寄存器主存儲器和寄存器又被稱為可執(zhí)行存儲器；主存儲器簡稱內(nèi)存或主存，用于保存進(jìn)程運行時的程序和數(shù)據(jù)；寄存器具有與處理機(jī)相同的速度，故對寄存器的訪問速度最快，完全能與ＣＰＵ協(xié)調(diào)工作，但價格十分昂貴，且容量較??；7４.1.3高速緩存和磁盤緩存高速緩存：介于寄存器和存儲器之間的存儲器，主要用于備份主存中較常用的數(shù)據(jù)，以減少處理機(jī)對主存儲器的訪問次數(shù)，大幅度提高程序執(zhí)行速度。高速緩存容量遠(yuǎn)大于寄存器，比內(nèi)存約小兩到三個數(shù)量級左右，訪問速度快于主存儲器。磁盤緩存：暫時存放頻繁使用的一部分磁盤數(shù)據(jù)和信息，以減少訪問磁盤的次數(shù)。與高速緩存不同，磁盤緩存本身不是一種實際存在的存儲器。8

４.２

程序的裝入和鏈接

在多道程序環(huán)境下,程序要運行必須創(chuàng)建進(jìn)程。創(chuàng)建進(jìn)程的第一件事就是將程序和數(shù)據(jù)裝入內(nèi)存。9

如何將一個用戶源程序變成一個可以在內(nèi)存中執(zhí)行的程序？編譯:由編譯程序?qū)⒂脩粼创a譯成若干個目標(biāo)模塊。鏈接:由鏈接程序?qū)⒕幾g后形成的目標(biāo)模塊以及它們所需要的庫函數(shù)鏈接在一起,形成一個裝入模塊。裝入:由裝入程序?qū)⒀b入模塊裝入內(nèi)存。10對用戶程序的處理步驟11前置處理器編譯器優(yōu)化器匯編程序器連接/載入程序程序庫文件目的文件可執(zhí)行文件源文件包含的頭文件匯編語言源文件程序處理步驟

可執(zhí)行程序生成過程:12程序地址:

相對地址(邏輯地址):相對于本可執(zhí)行程序起始地址.由于編譯程序不能預(yù)知編譯的目標(biāo)模塊在內(nèi)存的具體位置,因此目標(biāo)模塊的起始地址通常都是從0開始計算.

絕對地址(物理地址):存放在存儲介質(zhì)上的地址.13４.２.１程序的裝入單個目標(biāo)模塊的裝入過程可采用三種方式：絕對裝入方式可重定位方式動態(tài)運行時的裝入方式14(1)絕對裝入方式:由裝入程序根據(jù)模塊中的地址,將程序和數(shù)據(jù)裝入內(nèi)存。

適合單道程序環(huán)境。符號地址程序JUMPiLOADjDATAijA目標(biāo)模塊絕對地址JUMP1424LOAD222410241424B絕對裝入模塊12004000相對地址JUMP400LOAD1200C相對裝入模塊15(2)可重定位裝入方式:由裝入程序根據(jù)內(nèi)存當(dāng)時的實際使用情況,將裝入模塊裝入到內(nèi)存適當(dāng)?shù)胤?。不允許在內(nèi)存中移位,適用多道程序環(huán)境。定義：把裝入時對目標(biāo)程序中的指令和數(shù)據(jù)地址的修改過程稱為重定位。0100025005000365load1250010000load125001250036515000作業(yè)地址空間內(nèi)存空間16(3)動態(tài)運行時裝入方式

定義：把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址裝換為絕對地址，而是推遲到程序要真正執(zhí)行時才進(jìn)行。地址轉(zhuǎn)換要借助硬件完成才能不影響指令的執(zhí)行速度。174.2.2程序的鏈接功能：將經(jīng)過編譯或匯編后所得到的一組目標(biāo)模塊以及它們所需要的庫函數(shù)裝配成一個完整的裝入模塊。實現(xiàn)：靜態(tài)鏈接；裝入時動態(tài)鏈接：運行時動態(tài)鏈接。18(1)靜態(tài)鏈接

將幾個目標(biāo)模塊鏈接成一個裝入模塊,要運行時直接裝入內(nèi)存。由以下兩步完成:對相對地址修改;變換外部調(diào)用符號。優(yōu)點:簡單19(2)裝入時動態(tài)鏈接:將幾個目標(biāo)模塊邊裝入邊鏈接。若發(fā)生外部調(diào)用,將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊,并將它裝入內(nèi)存。優(yōu)點:便于軟件版本的修改和更新；便于實現(xiàn)目標(biāo)模塊的共享。20(3)運行時動態(tài)鏈接:將幾個目標(biāo)模塊邊運行邊鏈接。若沒有運行的模塊不在鏈接。優(yōu)點:節(jié)約內(nèi)存；程序運行效率更高。問題:運行時實現(xiàn)裝入過程。214.3連續(xù)分配存儲管理方式連續(xù)分配：是指為一個用戶程序分配一個連續(xù)的內(nèi)存空間。連續(xù)分配方式可分為四類：單一連續(xù)分配；固定分區(qū)分配；動態(tài)分區(qū)分配；動態(tài)可重定位分區(qū)分配算法。224.3.1單一連續(xù)分配方式只能用于單用戶，單任務(wù)的操作系統(tǒng)中。內(nèi)存分為兩個區(qū)：（1）系統(tǒng)區(qū):僅提供給操作系統(tǒng)使用，可以停留在內(nèi)存的低址部分，也可以在高址部分。（2）用戶區(qū):指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。23圖4－5：地址映射和地址保護(hù)否CPU<界限存儲器內(nèi)存地址錯重定位寄存器物理地址邏輯地址244.3.2固定分區(qū)分配最早使用的一種可運行多道程序的存儲管理方式。將內(nèi)存空間劃分為若干個固定大小的區(qū)域,稱為分區(qū)。在每個區(qū)域中放入一道作業(yè)。內(nèi)存被劃分成幾個分區(qū),允許放入幾道作業(yè)。當(dāng)有一個分區(qū)空閑時,變可從外存后備隊列中選擇一個適當(dāng)大小的作業(yè)裝入。25(1)劃分分區(qū)的方法：分區(qū)大小相等

缺點：缺乏靈活性

為什么還用？對于利用一臺計算機(jī)去控制多個相同對象的場合而言，該劃分方式比較方便和實用。分區(qū)大小不等:

較小的分區(qū)、中等分區(qū)、大分區(qū).26(2)內(nèi)存分配:

將分區(qū)根據(jù)大小進(jìn)行排隊,并建立一張分區(qū)使用表。

分區(qū)使用表中,各表項包含每個分區(qū)的起始地址、大小、狀態(tài)（是否已分配）。27圖5－6固定分區(qū)使用表（a）分區(qū)說明表（b）存儲空間分配情況分區(qū)號大?。ǎ耍拢┢鹬罚ǎ耍顟B(tài)１１２２０已分配２３２３２已分配３６４６４未分配４１２８１２８已分配空間操作系統(tǒng)２４ＫＢ作業(yè)Ａ３２ＫＢ作業(yè)Ｂ６４ＫＢ作業(yè)Ｃ１２８ＫＢ．．．．．．２５６ＫＢ28固定分區(qū)分配是最簡單的多道程序的存儲管理方式.用于60年代的IBM-360的MFT操作系統(tǒng).每個分區(qū)大小固定,造成浪費,較少使用.有些控制系統(tǒng)今天仍然使用該方式.294.3.3動態(tài)分區(qū)分配動態(tài)的分區(qū)分配：根據(jù)進(jìn)程的實際需要，動態(tài)的為之分配連續(xù)的內(nèi)存空間。必須解決的三個問題:(1)分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)；

（2)分區(qū)分配的算法；

（3)分區(qū)的分配和回收操作。30(1)動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)

空閑分區(qū)表：用于為內(nèi)存中每個未分配出去的分區(qū)設(shè)置一個表項．分區(qū)大小分區(qū)號分區(qū)大?。ǎ耍拢┓謪^(qū)始址（Ｋ）狀態(tài)１５０８５空閑２３２１５５空閑３７０２７５空閑４６０５３２空閑５．．．．．．．．．310

0N＋2N+2向后指針前向指針空閑分區(qū)鏈：在每個分區(qū)的起始部分設(shè)置一些用于控制分區(qū)分配的信息,以及鏈接分區(qū)的前項指針;并在分區(qū)尾部設(shè)置一后向指針.通過前后向指針將分去鏈接成一個雙向鏈.32(2)動態(tài)分區(qū)分配算法:

從空閑分區(qū)鏈中尋找分區(qū)的算法33(3)分區(qū)分配操作:分配內(nèi)存回收內(nèi)存34m.size-u.size≤size?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回將該分區(qū)從鏈中移出m.size>u.size?繼續(xù)檢索下一個表項從頭開始查表檢索完否？返回

分配內(nèi)存NNN35

F1回收區(qū)回收區(qū)F2回收區(qū)F1F2

回收內(nèi)存:回收區(qū)與插入點的前一個分區(qū)鄰接F1;

回收區(qū)與插入點的后一個分區(qū)鄰接F2;

回收區(qū)與插入點的前后分區(qū)鄰接F1,F2;

回收區(qū)既不與F1鄰接又不與F2鄰接;364.3.4基于順序搜索的動態(tài)分區(qū)分配算法基于順序搜索的動態(tài)分區(qū)分配算法有如下四種：首次適應(yīng)算法循環(huán)首次適應(yīng)算法最佳適應(yīng)算法最壞適應(yīng)算法37首次適應(yīng)算法FF:空閑分區(qū)鏈以地址遞增的次序鏈接。每次分配時從鏈?zhǔn)组_始順序查找,直到找到一個能滿足大小要求的空閑分區(qū)為止。按照作業(yè)的大小,從該分區(qū)中劃分出一塊內(nèi)存空間分配給請求者。余下的空閑分區(qū)仍留在空閑鏈中。特點:優(yōu)先利用內(nèi)存低址部分,為大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。留下了很多難以利用的很小的空間。38

循環(huán)首次適應(yīng)算法:

在FF算法的基礎(chǔ)上,不在每次從鏈?zhǔn)组_始查找,而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找,直到找到一個能滿足大小要求的空閑分區(qū)為止.按照作業(yè)的大小,從該分區(qū)中劃分出一塊內(nèi)存空間分配給請求者。實現(xiàn)方法:設(shè)置一起始查詢指針指示下一次起始查詢的空閑分區(qū),并采用循環(huán)查找方式。

特點:使空閑分區(qū)分布均勻；

減少查找空閑分區(qū)開銷；

缺乏大的空閑分區(qū)。39

最佳適應(yīng)算法:

將所有的空閑區(qū)按其大小遞增的順序形成一空閑區(qū)鏈。這樣第一次找到的空閑區(qū)必然是最優(yōu)的。

特點:找到的空閑區(qū)既是滿足要求又是最小的。

每次分配割下的剩余部分總是最小,這些小的空間難以利用。

40

最壞適應(yīng)算法:

在掃描整個空閑分區(qū)表或鏈表時，總是挑選一個最大的空閑分區(qū)，從中分割一部分存儲空間給作業(yè)使用，以至于存儲器中缺乏大的空閑分區(qū)。特點:可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的可能性最小，對中、小作業(yè)有利。查找效率高

414.3.5基于索引搜索的動態(tài)分區(qū)分配算法目前常用的基于索引搜索的動態(tài)分區(qū)分配算法包括：快速適應(yīng)算法伙伴系統(tǒng)哈希算法42快速適應(yīng)算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表，這樣系統(tǒng)中存在多個空閑分區(qū)鏈表。執(zhí)行步驟：根據(jù)進(jìn)程的長度，從索引表中去尋找到能容納它的最小空閑區(qū)鏈表；從鏈表中取下第一塊進(jìn)行分配。優(yōu)點：查找效率高缺點：系統(tǒng)開銷大；為進(jìn)程所分配的分區(qū)中，存在一定浪費。43伙伴系統(tǒng)

優(yōu)缺點：回收空閑分區(qū)時，需要對空閑分區(qū)進(jìn)行合并，所以其時間性能比快速適應(yīng)算法差，但由于它采用索引搜索算法，比順序搜索算法好?？臻g性能優(yōu)于快速適應(yīng)算法，比順序搜索法略差。44哈希算法哈希算法利用哈?？焖俨檎业膬?yōu)點，以及空閑分區(qū)在可利用空閑區(qū)表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，該表的每一個表項紀(jì)錄了一個對應(yīng)的空閑分區(qū)鏈表表頭指針。當(dāng)進(jìn)行空閑分區(qū)分配時，根據(jù)所需空閑分區(qū)大小，通過哈希函數(shù)計算，即得到在哈希表中的位置，從中得到相應(yīng)的空閑分區(qū)鏈表，實現(xiàn)最佳分配策略。454.3.6動態(tài)重定位分區(qū)分配(1)緊湊:

零頭(碎片):作業(yè)之間(主存中)不能充分利用的存儲碎塊。

緊湊:將內(nèi)存中的所有作業(yè)進(jìn)行移動，使它們相鄰接.原來分散的多個小分區(qū)拼結(jié)成一個大分區(qū)。46

操作系統(tǒng)

用戶程序1

10KB

用戶程序3

30KB

用戶程序6

14KB

用戶程序9

26KB

操作系統(tǒng)

用戶程序1

用戶程序3

用戶程序6

用戶程序9

80KB緊湊前

緊湊后47(2)動態(tài)重定位:

用RR(重定位寄存器):硬件完成.

程序執(zhí)行時真正訪問的內(nèi)存地址是相對地址與重定位寄存器中的地址相加而形成的.

動態(tài)重定位:

地址變換過程是在程序執(zhí)行期間,隨著對每條指令和數(shù)據(jù)的訪問而自動進(jìn)行的,這就是動態(tài)重定位.48250010000LOAD1,2500365LOAD1,2500365010025005000作業(yè)j相對地址重定位寄存器10000101001250015000主存處理機(jī)一側(cè)存儲器一側(cè)動態(tài)重定位示意圖49(3)動態(tài)重定位分區(qū)分配算法

與動態(tài)分區(qū)分配算法基本相同，差別僅在于：在這種分配算法中，增加了緊湊的功能。當(dāng)該算法不能找到一個足夠大的空閑分區(qū)以滿足用戶需求時，如果所有小的空閑分區(qū)的容量總和大于用戶的要求，這是便須對內(nèi)存進(jìn)行“緊湊”，將經(jīng)緊湊后多得到的大空閑分區(qū)分配給用戶。如果所有小空閑分區(qū)的容量總和仍小于用戶的需求，則返回分配失敗信息。50(3)動態(tài)分區(qū)分配算法流程:

無法分配返回空閑分區(qū)總和>u.xize進(jìn)行緊湊形成連續(xù)空閑區(qū)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)請求分配u.xize分區(qū)檢索空閑分區(qū)鏈

找到大于u.xize的可用區(qū)否？按動態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號及首址否否是是51IBM-PC微機(jī)中的存儲管理方式(1)段存儲器和作業(yè)的分段:

采用多重定位的存儲器管理方式.

設(shè)置四個段寄存器:

代碼段寄存器CS

數(shù)據(jù)段寄存器DS

棧段寄存器SS

附加段寄存器ES.52程序分為四個段:

代碼段,數(shù)據(jù)段,棧段,附加段.

這幾個段的地址空間可以鄰接也可以分開;也可部分或全部重疊.

一個作業(yè)的最大地址空間可為256KB.每一個段可以存放在內(nèi)存用戶區(qū)的任何位置.IBM-PC機(jī)的最大尋址范圍為1MB,20位地址.而每段地址位16位,剩余4位(低4位全為0).因此把高16位的內(nèi)容放入段寄存器中.53(2)形成訪問內(nèi)存物理地址:

段寄存器內(nèi)容左移4位再與16位的地址偏移量相加就是20位的物理地址.(3)多重定位的實現(xiàn):

由于有四個段寄存器，可以實現(xiàn)四重分區(qū)。一個用戶程序分為四段，每段可以放在用戶區(qū)的任何位置，也允許在內(nèi)存中移動。544.4對換也稱為交換(Swaping)技術(shù)。最早用在麻省理工學(xué)院的兼容分時系統(tǒng)CTSS中.該系統(tǒng)是單用戶系統(tǒng),在內(nèi)存中只留一道用戶作業(yè),其它作業(yè)都駐留在外存后備隊列,每次只調(diào)入一個作業(yè)進(jìn)入內(nèi)存運行,此作業(yè)的時間片用完后調(diào)至外存。再從外存后備隊列再調(diào)入下一個作業(yè)進(jìn)入內(nèi)存。這樣,解決了內(nèi)存的不足,增加了作業(yè)的多道度。這種早期的交換技術(shù)由于CPU空閑時間太長今天已經(jīng)不用。

554.4.1多道程序環(huán)境下的兌換技術(shù)對換概念:

將主存中暫時不能運行的進(jìn)程（程序，數(shù)據(jù)）調(diào)到外存，騰出主存空間把外存的進(jìn)程（程序，數(shù)據(jù)）調(diào)入主存投入運行。對換類型：如果對換以整個進(jìn)程為單位,則稱為“整體對換”或“進(jìn)程對換”,在分時系統(tǒng)中應(yīng)用最多。如果對換以頁或段為單位,則稱為“頁面對換”或“分段對換”,也稱為“部分對換”。564.4.2對換空間的管理1.對換空間管理的主要目標(biāo)1）對文件區(qū)管理的主要目標(biāo)主要目標(biāo)是提高文件存儲空間的利用率，然后才是提高對文件的訪問速度。2）對對換空間管理的主要目標(biāo)主要目標(biāo)是提高進(jìn)程換入和換出的速度，然后才是提高文件存儲空間的利用率。574.4.2對換空間的管理2.對換區(qū)空閑盤塊管理中的數(shù)據(jù)結(jié)構(gòu)

使用空閑分區(qū)表或空閑分區(qū)鏈，在空閑分區(qū)表的每個表目中，應(yīng)包含：對換區(qū)的首址及其大小，分別用盤塊號和盤塊數(shù)表示。584.4.2對換空間的管理

594.4.3

進(jìn)程的換出與換入(1)進(jìn)程的換出:選出被換出的進(jìn)程:

狀態(tài):阻塞或睡眠；

優(yōu)先級最低；

在內(nèi)存中的駐留時間。換出過程:非共享的程序或數(shù)據(jù)直接換出；共享的程序或數(shù)據(jù)換出前必須判斷引用計數(shù)減1后是否為0,不為0,則不能換出；可以換出時，在申請對換空間成功后換出，同時釋放內(nèi)存。60(2)進(jìn)程的換入:當(dāng)對換進(jìn)程或程序去執(zhí)行對換操作時，便檢查PCB集合中所有進(jìn)程的狀態(tài)。從中找出“就緒且換出”狀態(tài)的進(jìn)程。當(dāng)存在多個這樣的進(jìn)程時，首先把其中換出時間（必須大于規(guī)定時間）最久的進(jìn)程作為換入進(jìn)程.根據(jù)進(jìn)程大小為其申請內(nèi)存。成功，直接將進(jìn)程換入。失敗，先將內(nèi)存中某些進(jìn)程換出，再換入該進(jìn)程。614.5

分頁存儲管理方式離散分配內(nèi)存方式:

克服連續(xù)分配方式會產(chǎn)生碎片；

避免緊湊開銷太大。離散分配內(nèi)存分為三種方式分頁存儲管理分段存儲管理段頁式存儲管理624.5.1分頁存儲管理的基本方法(1)頁面和物理塊頁面：在分頁存儲管理方式中將一個進(jìn)程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁。物理塊：內(nèi)存空間也分成和頁相同大小的若干個存儲塊，稱為物理塊或頁框。頁內(nèi)碎片:最后一頁裝不滿時形成。頁面大小：適中的頁面大小為2的冪，通常為1KB~8KB。634.5.1分頁存儲管理的基本方法(2)地址結(jié)構(gòu)頁號P(1MB)位移量W(4KB)3112110它含有兩部分。前一部分為頁號P，后一部分為位移量W，即頁內(nèi)地址。對某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個邏輯空間中的地址為A,頁面大小為L，則頁號P和頁內(nèi)地址d可按下式求得：

P=INT[A/L]，

d=[A]MODL640頁1頁2頁3頁4頁5頁…N頁02132638495…

…(3)頁表:實現(xiàn)從頁號到物理塊號的映射。頁號塊號內(nèi)存0123456789用戶程序頁表的作用654.5.2地址變換機(jī)構(gòu)

基本任務(wù)：實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，即將邏輯地址中的頁號轉(zhuǎn)換為內(nèi)存中的物理塊號?；镜牡刂纷儞Q機(jī)構(gòu)。具有塊表的地址變換機(jī)構(gòu)。66(1)基本的地址變換機(jī)構(gòu):

頁表寄存器:由于頁表大多數(shù)駐留在內(nèi)存中,在內(nèi)存中設(shè)置一個頁表寄存器存放頁表在內(nèi)存中的始址和長度。在單處理機(jī)環(huán)境下只需一個頁表寄存器。分頁地址變換機(jī)構(gòu):將邏輯地址分為頁號與頁內(nèi)地址；比較頁號與頁表長度:大于,越界；否則:頁表始址+頁號*頁表項長度=在頁表中的位置；在頁表中的位置中得到該頁的物理塊號；物理塊的始址+頁內(nèi)偏移=物理地址。67頁表始址頁表長度頁號3頁內(nèi)地址1b越界中斷頁號塊號0123頁表物理地址頁表寄存器邏輯地址基本的地址變換機(jī)構(gòu):68(2)具有快表的地址變換機(jī)構(gòu):

由于頁表大多數(shù)在內(nèi)存中,CPU存取一個數(shù)據(jù)要兩次訪問內(nèi)存,使計算機(jī)的處理速度降低1/2,代價高。

在地址變換機(jī)構(gòu)中增加一個具有并行查詢能力的特殊高速緩沖存儲器,稱為“聯(lián)想寄存器”或“快表”，用來存放當(dāng)前訪問的表項。地址變換機(jī)構(gòu):

自動將頁號P送入高速緩沖存儲器中,并將該頁號與緩沖存儲器中的頁號比較,若有,則頁表項在快表中,直接得到物理塊號;若無則在內(nèi)存中,再訪問內(nèi)存。

69頁表始址頁表長度頁號頁內(nèi)地址bbd+>輸入寄存器頁表寄存器邏輯地址物理地址越界中斷頁號塊號頁表頁號塊號快表具有快表的地址變換機(jī)構(gòu)70

由于高速緩存的成本很高,不可能做很大,通常存放16~512個頁表項。Molorola68030處理器有22個；Intel80486處理器有32個；

中、小型作業(yè)可能把全部頁表項放入快表中,大型作業(yè)只能放入一部分。71命中率(%)有效訪問時間T=h*t1+(1-h)ts(ns)050809098T=0*120+1*220=220T=0.5*120+0.5*220=170T=0.8*120+0.2*220=140T=0.9*120+0.1*220=130T=0.98*120+0.02*220=122

通常,聯(lián)想寄存器的命中率為80%~90%,有效訪問時間只比單周期增加了30%~40%,如果不引入則訪問時間延長一倍.4.5.3訪問內(nèi)存的有效時間724.5.4兩級和多級頁表

現(xiàn)代的大多數(shù)計算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間，頁表應(yīng)非常大。

如:32位地址空間,頁面大小為12位(4KB)時,則頁數(shù)為1M,即頁表項為1M.如果一個頁表項占用4個字節(jié),故每個進(jìn)程只是頁表就要占用4MB的內(nèi)存空間,并且這些內(nèi)存空間還必須是連續(xù)的。

對于內(nèi)存來說,要有大的連續(xù)空間用于頁表不現(xiàn)實。73通過兩個方面來解決這一問題：對頁表所需的內(nèi)存空間，采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間問題.只將當(dāng)前需要的部分頁表調(diào)入內(nèi)存,其余的頁表仍然駐留在磁盤上,只有需要時再調(diào)入內(nèi)存。74(1)兩級頁表:

為了避免頁表需要大的連續(xù)內(nèi)存空間,利用將頁表進(jìn)行分頁的辦法。頁表的頁面大小等于內(nèi)存物理塊的大??；對頁表的頁面進(jìn)行編號；為分散的頁表再建立一張頁表,稱為外層頁表；在外層頁表中記錄有頁表頁面號與頁表所在物理塊的首址。75例:32位物理地址空間.頁面大小為4KB,一個頁表項長度為1個字節(jié)。如果連續(xù)頁表則需要1MB的連續(xù)空間.

現(xiàn)在用兩級頁表:

對1MB的頁表進(jìn)行分頁,每頁4KB,則需250頁；

外層頁表則需要250項,如果一項為4個字節(jié),外層頁表需占用1KB的內(nèi)存空間。

在外層頁表中有頁表的頁面號與頁面所在物理塊號映射。

只要知道進(jìn)程某頁在頁表中的頁面,則可從外層頁面上查到頁表頁面所在的物理塊首址,在該物理塊中相應(yīng)行得到進(jìn)程的該頁所在物理塊號。76101110781742146…第一頁頁表114115…第n頁頁表1468…………012外部頁表第0頁頁表內(nèi)存空間0123456711411514680121023012102301210231011107877兩級頁表的地址變換:

在原來的地址變換機(jī)構(gòu)中增加一個外層頁表寄存器,用于存放外層頁表的始址;

并利用邏輯地址中的外層頁號,作為外層頁表的索引,從中找到指定頁表分頁的首址;

從頁表分頁中得到所找頁在頁表中的項;

項中的內(nèi)容得到物理塊號.78具有兩級頁表的地址變換機(jī)構(gòu):p1p2p3外部頁號外部頁內(nèi)地址頁內(nèi)地址邏輯地址外部頁表寄存器外部頁表頁表db物理地址79(2)多級頁表結(jié)構(gòu):

對于32位,從前面可見兩級頁表可以解決.

對于64位機(jī)器，必須采用多級頁表，將16GB的外層頁表再進(jìn)行分頁，也是將各個分頁離散地分配到不鄰接的物理塊中，再利用第二級的外層頁表來映射它們之間的關(guān)系。

SUN公司的SPARC處理器支持三級頁表結(jié)構(gòu)，

Motorola的68030處理器，則支持四級頁表結(jié)構(gòu)。804.5.5反置頁表

在分頁系統(tǒng)中為