計(jì)算機(jī)操作系統(tǒng)-ch6-存儲(chǔ)器管理

第六章器管理本章主要內(nèi)容：一.

器的層次結(jié)構(gòu)二.程序的裝入和三.連續(xù)分配 管理方式單一連續(xù)區(qū)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配四.離散分配的基本分頁(yè)管理方式管理方式分段段頁(yè)式管理管理6.1器的層次結(jié)構(gòu)第六章器管理第六章器管理6.1器的層次結(jié)構(gòu)局部性原理空間局部

性時(shí)間局部

性6.2程序的裝入和在多道程序環(huán)境下，程序要運(yùn)行必須為之創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程的第一件事，就是要將程序和數(shù)據(jù)裝入內(nèi)存。將一個(gè)用戶的源程序變?yōu)橐粋€(gè)可在內(nèi)存中執(zhí)行的程序，通常要經(jīng)過(guò)編譯、、裝入。第六章

器管理第六章

器管理程序的裝入和程序的裝入程序的裝入就是系統(tǒng)調(diào)用裝入程序?qū)⒊绦蜓b入內(nèi)存，可采用三種方式:一、絕對(duì)裝入方式二、可重定位裝入方式(靜態(tài)重定位)三、動(dòng)態(tài)運(yùn)行時(shí)裝入第六章

器管理程序的裝入和程序的裝入一、絕對(duì)裝入方式編譯程序事先已知程序在內(nèi)存中的駐留位置，編譯時(shí)產(chǎn)生絕對(duì)地址的目標(biāo)代碼，絕對(duì)裝入程序按照裝入模塊的絕對(duì)地址將程序和數(shù)據(jù)裝入內(nèi)存。裝入模塊被裝入內(nèi)存后，不需對(duì)程序和數(shù)據(jù)的地址進(jìn)行修改。第六章

器管理程序的裝入和程序的裝入二、可重定位裝入方式(靜態(tài)重定位)在程序裝入時(shí)對(duì)目標(biāo)程序中的指令和數(shù)據(jù)地址的修改過(guò)程稱為重定位。1、編譯程序使目標(biāo)模塊的起始地址從0開(kāi)始。2、程序裝入時(shí)，裝入程序根據(jù)內(nèi)存的使用情況將裝入模塊裝入到內(nèi)存的某個(gè)位置，并對(duì)模塊進(jìn)行重定位。物理地址=有效相對(duì)地址+程序在內(nèi)存中的起始地址。第六章

器管理程序的裝入和程序的裝入三、動(dòng)態(tài)運(yùn)行時(shí)裝入程序執(zhí)行時(shí)進(jìn)行相對(duì)地址→物理地址的轉(zhuǎn)換。(因?yàn)槌绦蛟诨顒?dòng)過(guò)程中，在物理內(nèi)存中的位置會(huì)發(fā)生變化，比如在具有對(duì)換功能的系統(tǒng)中）。CPU內(nèi)存重定位寄存器14000+34614346邏輯地址物理地址內(nèi)存管理單元（MMU)第六章器管理6.2程序的裝入和6.2.2

程序的一、要解決的問(wèn)題將編譯后的目標(biāo)模塊裝配成一個(gè)可執(zhí)行的程序第六章器管理6.2程序的裝入和6.2.2

程序的二、1、靜態(tài)的兩種方式(static

Linking)2、運(yùn)行時(shí)動(dòng)態(tài)

(Run-time

Dynamic

Linking)第六章器管理6.2程序的裝入和6.2.2

程序的二、

的兩種方式1.靜態(tài)：在程序運(yùn)行前，用程序?qū)⒛繕?biāo)模塊鏈接成一個(gè)完整的裝入模塊。靜態(tài)

的任務(wù)：對(duì)相對(duì)地址進(jìn)行修改：變換外部調(diào)用符號(hào)：將每個(gè)模塊中所用的外部調(diào)用符號(hào)，都變換為相對(duì)地址見(jiàn) P139頁(yè)圖6-46.2程序的裝入和6.2.2

程序的靜態(tài)1、的特點(diǎn)：開(kāi)銷大2、程序開(kāi)發(fā)不方便3、程序運(yùn)行快第六章器管理第六章器管理6.2程序的裝入和6.2.2

程序的二、

的兩種方式2、運(yùn)行時(shí)動(dòng)態(tài)基本原理6.2程序的裝入和6.2.2

程序的動(dòng)態(tài)

的特點(diǎn)：1、節(jié)省內(nèi)存和外存空間；2、方便程序開(kāi)發(fā)；3、程序運(yùn)行時(shí)的速度慢了；第六章器管理第六章器管理管理方式6.3連續(xù)分配一、單一連續(xù)分配。二、分區(qū)式分配：1、固定分區(qū)：分區(qū)大小相等分區(qū)大小不等2、動(dòng)態(tài)分區(qū)。第六章器管理連續(xù)分配

管理方式單一連續(xù)分配這種方式適用于單用戶，單任務(wù)的OS，它把內(nèi)存OS使用，用戶區(qū)供分為系統(tǒng)區(qū)和用戶區(qū)。系統(tǒng)區(qū)用戶使用。單一連續(xù)分配的OS保護(hù)機(jī)構(gòu)：設(shè)一基址寄存器(存程序在物理內(nèi)存中的最小地址，用于進(jìn)行地址映

射）、和一界限寄存器。如果用戶程序的邏輯地址<界限寄存器中的邏輯地址范圍則是合法地址，否則中斷。第六章器管理6.3

連續(xù)分配

管理方式6.3.2固定分區(qū)分配固定分區(qū)分配將內(nèi)存空間劃分為若干個(gè)固定大小的區(qū)域，在每個(gè)分區(qū)中可以裝入一道作業(yè)。當(dāng)內(nèi)存中劃分成幾個(gè)分區(qū)時(shí)，便允許幾道作業(yè)并發(fā)運(yùn)行；當(dāng)有一個(gè)空閑分區(qū)時(shí)，便可從外存的后備隊(duì)列中選擇一個(gè)適當(dāng)大小的作業(yè)裝入該分區(qū)；當(dāng)該作業(yè)結(jié)束時(shí)，又可從后備隊(duì)列中找出另一個(gè)作業(yè)調(diào)入該分區(qū)。第六章器管理6.3

連續(xù)分配

管理方式6.3.2固定分區(qū)分配一、劃分分區(qū)的方法1、分區(qū)大小相等2、分區(qū)大小不等二、內(nèi)存分配使用一個(gè)記錄內(nèi)存狀況的內(nèi)存分區(qū)使用表來(lái)管理內(nèi)存分配。第六章器管理6.3

連續(xù)分配

管理方式6.3.2固定分區(qū)分配三、固定分區(qū)使用表分區(qū)號(hào)大小（KB)始址（K）狀態(tài)11230已分配23045已分配35075已分配4100125已分配6.3

連續(xù)分配

管理方式6.3.2固定分區(qū)分配四、固定分區(qū)的特點(diǎn)：1、管理簡(jiǎn)單2、內(nèi)存利用率低第六章器管理第六章器管理6.3

連續(xù)分配

管理方式6.3.3動(dòng)態(tài)分區(qū)分配使用固定分區(qū)浪費(fèi)內(nèi)存，故使用動(dòng)態(tài)分區(qū)，根據(jù)進(jìn)程的具體情況分配內(nèi)存。本節(jié)主要內(nèi)容：動(dòng)態(tài)分區(qū)分配使用的數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)分區(qū)分配算法動(dòng)態(tài)分區(qū)的分配和回收操作第六章器管理6.3

連續(xù)分配

管理方式6.3.3動(dòng)態(tài)分區(qū)分配一、動(dòng)態(tài)分區(qū)分配的基本原理第六章器管理6.3

連續(xù)分配

管理方式6.3.3動(dòng)態(tài)分區(qū)分配二、分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)

1、空閑分區(qū)表包含分區(qū)序號(hào)、分區(qū)始址及分區(qū)大小等表目。序號(hào)分區(qū)大?。↘B)分區(qū)始址（K）1123023045第六章

器管理6.3

連續(xù)分配

管理方式6.3.3動(dòng)態(tài)分區(qū)分配二、分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)2、空閑分區(qū)鏈為每個(gè)空閑分區(qū)建立一個(gè)分區(qū)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)包括:向前、向后指針、分區(qū)起始地址及大小。第六章器管理6.3

連續(xù)分配

管理方式6.3.3動(dòng)態(tài)分區(qū)分配三、動(dòng)態(tài)分區(qū)分配算法介紹下面三種動(dòng)態(tài)分區(qū)分配算法：1、首次適應(yīng)算法FF2、循環(huán)首次適應(yīng)算法。3、最佳適應(yīng)算法第六章器管理6.3

連續(xù)分配

管理方式6.3.3動(dòng)態(tài)分區(qū)分配三、動(dòng)態(tài)分區(qū)分配算法1、首次適應(yīng)算法FF在采用空閑分區(qū)鏈作為數(shù)據(jù)結(jié)構(gòu)時(shí)，F(xiàn)F算法要求空閑分區(qū)鏈以地址遞增的次序。在進(jìn)行內(nèi)存分配時(shí)，從鏈?zhǔn)组_(kāi)始順序查找，直至找到一個(gè)能滿足其大小要求的空閑分區(qū)為止。然后，再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑鏈中。首次適應(yīng)算法FF的特點(diǎn)：1、高地址部分大空閑區(qū)較多；2、低地址部分容易留下小分區(qū)；3、查找從低地址開(kāi)始，查找開(kāi)銷較大。第六章器管理6.3

連續(xù)分配

管理方式6.3.3動(dòng)態(tài)分區(qū)分配三、動(dòng)態(tài)分區(qū)分配算法

2、循環(huán)首次適應(yīng)算法該算法是由首次適應(yīng)算法演變而形成的。在為進(jìn)程分配

內(nèi)存空間時(shí)，不再每次從鏈?zhǔn)组_(kāi)始查找，而是從上次找到的

空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找，直至找到第一個(gè)能滿足要求的空閑分區(qū)，并從中劃出一塊與請(qǐng)求的大小相等的內(nèi)存空間分配給作業(yè)。為實(shí)現(xiàn)該算法，應(yīng)設(shè)置一起始查找指針，以指示下一次起始查找的空閑分區(qū)，并采用循環(huán)查找方式。循環(huán)首次適應(yīng)算法的特點(diǎn):

1、空閑區(qū)分布均勻；2、查找開(kāi)銷較??；3、容易使系統(tǒng)缺乏大空閑區(qū)；第六章器管理6.3

連續(xù)分配

管理方式6.3.3動(dòng)態(tài)分區(qū)分配三、動(dòng)態(tài)分區(qū)分配算法3、最佳適應(yīng)算法該算法每次為作業(yè)分配內(nèi)存，總是把既能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免了“大材小用”。為了加速尋找，該算法要求將所有的空閑區(qū)，按其大小以遞增的順序形成一空閑區(qū)。這樣，第一次找到的滿足要求的空閑區(qū)，必然是最優(yōu)的。最佳適應(yīng)算法的特點(diǎn)：1、避免大材小用，提高內(nèi)存利用率；2、容易留下難以利用的小空閑區(qū)。第六章器管理6.3

連續(xù)分配

管理方式6.3.3動(dòng)態(tài)分區(qū)分配四、分區(qū)分配操作1、內(nèi)存分配流程檢索空閑鏈表找足夠大的空閑區(qū)（m.size>=u.size)從m.size中劃出大小為u.size的空間進(jìn)行分配詳細(xì)流程見(jiàn)

p148頁(yè)習(xí)題：當(dāng)前空閑鏈20k:50k80k:100k300k:60k先請(qǐng)求30k空間,再請(qǐng)求50k空間.畫出分別采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法的空閑鏈（size=1k)解答方法參見(jiàn)p145頁(yè)例1。第六章器管理連續(xù)分配

管理方式動(dòng)態(tài)分區(qū)分配四、分區(qū)分配操作2、內(nèi)存回收流程內(nèi)存合并空閑區(qū)當(dāng)前空閑鏈如下：30k:10k

60k:100k

500k:200k請(qǐng)畫出分別回收下列空閑區(qū)之后的空閑鏈：起始地址分區(qū)大小150k5k240k10k350k10k440k20k第六章器管理管理方式6.3連續(xù)分配6.3.4緊湊一、緊湊把多個(gè)分散的小分區(qū)拼接成大分區(qū)的方法，被稱為“拼接”或“緊湊”二、動(dòng)態(tài)重定位物理地址=相對(duì)地址+重定位寄存器中的地址第六章

器管理6.4

多道程序環(huán)境下的對(duì)換“對(duì)換”是指把內(nèi)存中暫不能運(yùn)行的進(jìn)程或暫時(shí)不用的程序和數(shù)據(jù)，換出到外存上，以騰出足夠的內(nèi)存空間，把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)換入內(nèi)存。對(duì)換的方式有兩種：一、整體對(duì)換二、部分對(duì)換第六章

器管理6.4

多道程序環(huán)境下的對(duì)換一、整體對(duì)換如果對(duì)換是以整個(gè)進(jìn)程為單位，便稱之為“整體對(duì)換”或“進(jìn)程”對(duì)換，這種對(duì)換被廣泛地應(yīng)用于分時(shí)系統(tǒng)中，其目的是用以解決內(nèi)存緊張問(wèn)題，并可進(jìn)一步提高內(nèi)存的利用率。第六章

器管理6.4

多道程序環(huán)境下的對(duì)換二、部分對(duì)換如果對(duì)換是以“頁(yè)”或“段”為單位進(jìn)行的，則分別稱之為“頁(yè)面對(duì)換”或“分段對(duì)換”，又統(tǒng)稱為“部分對(duì)換”，這種對(duì)換方法是實(shí)現(xiàn)請(qǐng)求分頁(yè)及請(qǐng)求分段系統(tǒng)的基礎(chǔ)，其目的是為了支持虛擬存貯系統(tǒng)。第六章

器管理6.4

多道程序環(huán)境下的對(duì)換三、對(duì)換空間的管理對(duì)換空間指外存中可以用于存放從內(nèi)存換出進(jìn)程的暫存空間。對(duì)換空間的管理采用與內(nèi)存的動(dòng)態(tài)分區(qū)分配類似的數(shù)據(jù)結(jié)構(gòu)與分配、回收算法。第六章

器管理6.4

多道程序環(huán)境下的對(duì)換四、進(jìn)程的換出與換入進(jìn)程的換出與換入是通過(guò)OS內(nèi)核調(diào)用對(duì)換程序或喚醒對(duì)換進(jìn)程來(lái)實(shí)現(xiàn)的進(jìn)程的換出1、選擇被換出的進(jìn)程選擇低優(yōu)先權(quán)、內(nèi)存駐留時(shí)間較長(zhǎng)的進(jìn)程2、換出過(guò)程對(duì)于共享程序段或數(shù)據(jù)，要先檢查它們當(dāng)前是否被某些其他進(jìn)程需要；對(duì)換前還要申請(qǐng)對(duì)換空間。第六章

器管理進(jìn)程的換入1、檢查PCB中進(jìn)程的狀態(tài)，找出“就緒且換出”態(tài)的進(jìn)程。2、把換出時(shí)間最長(zhǎng)的一個(gè)進(jìn)程作為換入進(jìn)程。3、為換入進(jìn)程申請(qǐng)內(nèi)存空間，若申請(qǐng)成功，則直接換入，若內(nèi)存不夠，則先換出某些進(jìn)程，騰出足夠的空間，再將進(jìn)程換入。第六章器管理6.5

基本分頁(yè)

管理方式連續(xù)分配方式會(huì)形成許多碎片，雖然可通過(guò)緊湊方法將碎片拼接成可用的大塊空間，但須為此付出很大開(kāi)銷。如果允許將一個(gè)進(jìn)程直接離散地分配到許多不相鄰的分區(qū)中，就不必再進(jìn)行“緊湊”。為了支持虛擬內(nèi)存管理,需要引入離散分配方式。根據(jù)離散分配時(shí)所使用的基本單位的不同，離散分配分為以下三種方式：1、分頁(yè)2、分段3、段頁(yè)式管理管理管理第六章器管理管理方式管理的基本方法基本分頁(yè)分頁(yè)一、基本概念1、頁(yè)面：將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁(yè)面或頁(yè)。2、物理塊：將內(nèi)存空間分成與頁(yè)相同大小的若干個(gè)塊，稱為物理塊或頁(yè)框或幀。3、分頁(yè)：在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干頁(yè)分別裝入多個(gè)可以不相鄰接的塊中。4、頁(yè)內(nèi)碎片：進(jìn)程的最后一頁(yè)一般裝不滿一塊，而形成不可利用的碎片，稱為“頁(yè)內(nèi)碎片”。0頁(yè)1頁(yè)邏輯地址空間物理地址空間0塊1塊2002塊200第六章

器管理基本分頁(yè)分頁(yè)二、基本分頁(yè)管理方式管理的基本方法管理方式中的地址結(jié)構(gòu)1、地址結(jié)構(gòu)中包含兩部分：頁(yè)號(hào)P、頁(yè)內(nèi)偏移量W。若用m位表示邏輯地址，頁(yè)大小為2的n次冪，則用低n位表示頁(yè)內(nèi)偏移量w；用高m-n位表示頁(yè)號(hào)P以32位地址為例:可用0~11位表示頁(yè)內(nèi)偏移量n=12(頁(yè)內(nèi)212個(gè)單元=物理塊大小=4K);12-31位(20位)表示頁(yè)號(hào)，共可有220個(gè)頁(yè)面(1M個(gè)頁(yè))這種地址結(jié)構(gòu)可以表示4G的邏輯地址空間。P(m-n)位W(n位)31 12

110計(jì)算關(guān)系：A為邏輯地址，L為頁(yè)面大小，P為頁(yè)號(hào)，W為頁(yè)內(nèi)偏移量.P=INT(A/L)W=mod(A/L)第六章

器管理管理方式管理的基本方法基本分頁(yè)分頁(yè)三、頁(yè)表1、頁(yè)表是系統(tǒng)為進(jìn)程建立的數(shù)據(jù)結(jié)構(gòu)，頁(yè)表的作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址。在進(jìn)程地址空間內(nèi)的所有頁(yè)(0-n)，依次在頁(yè)表中有一頁(yè)表項(xiàng)，其中記錄了相應(yīng)頁(yè)在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)。第六章器管理基本分頁(yè)分頁(yè)管理方式管理的基本方法三、頁(yè)表中還可以包括一些存取控制字段頁(yè)號(hào)塊號(hào)021428……頁(yè)表中還可以包括一些存取控制字段1023102410250頁(yè)1頁(yè)02000201頁(yè)表邏輯地址空間物理地址空間0塊1塊02002塊10231024204720482049Move

eax,(1025)第六章器管理基本分頁(yè)分頁(yè)管理方式管理的基本方法四、地址變換機(jī)構(gòu)為了能將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址，在系統(tǒng)中必須設(shè)

址變換機(jī)構(gòu)，該機(jī)構(gòu)的基本任務(wù)是實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換。(一)、基本的地址變換機(jī)構(gòu)第六章

器管理管理方式管理的基本方法基本分頁(yè)分頁(yè)(二)、地址變換過(guò)程1、進(jìn)程執(zhí)行，PCB塊中頁(yè)表起始地址和頁(yè)表長(zhǎng)度送頁(yè)表寄存器。2、CPU

邏輯單元a。3、由分頁(yè)地址變換機(jī)構(gòu)自動(dòng)將

a

分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分4、由硬件檢索機(jī)構(gòu)搜索頁(yè)表，得到物理塊號(hào)。搜索原理：頁(yè)號(hào)對(duì)應(yīng)的頁(yè)表項(xiàng)地址=頁(yè)表起始地址+頁(yè)表項(xiàng)長(zhǎng)度*頁(yè)號(hào)。(頁(yè)表項(xiàng)中存有物理塊號(hào))。5、物理塊號(hào)和頁(yè)內(nèi)地址送物理地址寄存器。第六章

器管理管理方式管理的基本方法基本分頁(yè)分頁(yè)(三）實(shí)例若頁(yè)的大小為4K，則地址轉(zhuǎn)換機(jī)構(gòu)將邏輯地址0轉(zhuǎn)換成的物理地址為＿＿＿。在一個(gè)頁(yè)式管理系統(tǒng)中，頁(yè)表內(nèi)容如下所示：頁(yè)號(hào)物理塊號(hào)0211263347例題：物理地址的計(jì)算過(guò)程1、計(jì)算頁(yè)號(hào)和頁(yè)內(nèi)偏移p=INT[0/4096]=0w=MOD[0/4096]=02、搜索頁(yè)表，查找0號(hào)頁(yè)面所在的物理塊;結(jié)果為23、計(jì)算物理地址物理地址=塊大小*塊號(hào)+頁(yè)內(nèi)偏移=4096*2+0=8192第六章器管理管理方式基本分頁(yè)分頁(yè)

管理的基本方法（四）、頁(yè)面大小的選擇1、在分頁(yè)系統(tǒng)中頁(yè)面的大小是由機(jī)器的體系結(jié)構(gòu)所決定的,亦即由硬件決定。（如：分頁(yè)單元把低12位邏輯地址解釋為頁(yè)內(nèi)偏移地址，則頁(yè)大小就是4K).2、影響頁(yè)面大小設(shè)計(jì)的因素管理內(nèi)存的開(kāi)銷：（1）頁(yè)面太小，就會(huì)導(dǎo)致進(jìn)程所需頁(yè)面多，頁(yè)表過(guò)長(zhǎng)，占用大量?jī)?nèi)存空間；同時(shí)，降低頁(yè)面換入換出效率。第六章

器管理基本分頁(yè)分頁(yè)管理方式管理的基本方法（四）、頁(yè)面大小的選擇內(nèi)存的利用率頁(yè)面小有利于提高內(nèi)存的利用率，但存(1)所述缺點(diǎn)，頁(yè)面大，可克服(1)的缺點(diǎn)，但頁(yè)內(nèi)碎片大，空間利用率降低。頁(yè)面的大小、頁(yè)面大小是2的冪。、一般頁(yè)面大小在512個(gè)字節(jié)~4K、現(xiàn)在硬件可以支持多種不同的頁(yè)面大小。頁(yè)面大小4k

16K

2M

4M

8M

16M等等第六章器管理管理方式6.5基本分頁(yè)6.5.2

快表一、

快表快表（轉(zhuǎn)換后援緩沖TLB-TranslationLookasideBuffer）,是為了提高CPU訪存速度而采用的緩存，用來(lái)存放最近被 過(guò)的頁(yè)表項(xiàng)。第六章器管理管理方式6.5基本分頁(yè)6.5.2

快表二、快表的引入CPU存取一個(gè)數(shù)據(jù)，需兩次

內(nèi)存。第1次訪存取物理塊號(hào)、第2次取數(shù)。使計(jì)算機(jī)的處理速度降低近1/2。為了提高訪存速度，引

想

器，存放最近使用過(guò)的頁(yè)表項(xiàng)。第六章器管理6.5

基本分頁(yè)

管理方式6.5.2地址變換機(jī)構(gòu)三、引入TLB之后的地址變換過(guò)程TLB引入之后的地址變換過(guò)程第六章器管理6.5

基本分頁(yè)

管理方式6.5.2地址變換機(jī)構(gòu)四、引入TLB的性能分析TLB的速度為20ns,時(shí)間。若cpu

內(nèi)存的速度為120ns,試比較有TLB和無(wú)TLB系統(tǒng)的有效假

定TLB

中率為90%1、有TLB系統(tǒng)的有效 時(shí)間=（120+120+20）*10%+（120+20）*90%=152ns2、無(wú)TLB系統(tǒng)的有效 時(shí)間=120+120=240ns第六章器管理6.5基本分頁(yè)管理方式6.5.3

兩級(jí)和多級(jí)頁(yè)表對(duì)于很大的邏輯地址空間，使用分頁(yè)，需要很大的連續(xù)空間來(lái)存放頁(yè)表，為了實(shí)現(xiàn)頁(yè)表的離散存放，引入了兩級(jí)或多級(jí)頁(yè)表，其好處是：1、對(duì)頁(yè)表所需的內(nèi)存空間，采用離散分配方式,來(lái)解決難以找到一塊連續(xù)的大內(nèi)存空間以及頁(yè)表的離散存放的問(wèn)題。2、只將當(dāng)前需要的頁(yè)表調(diào)入內(nèi)存，其余的頁(yè)表駐留在磁盤上。第六章器管理6.5

基本分頁(yè)

管理方式6.5.3

兩級(jí)和多級(jí)頁(yè)表一、兩級(jí)頁(yè)表的實(shí)現(xiàn)方法將頁(yè)表再進(jìn)行分頁(yè)，使每個(gè)頁(yè)面的大小與內(nèi)存物理塊的大小相同，并為它們。將這些頁(yè)表頁(yè)面分別放入不同的，不一定相鄰的物理塊中，為離散分配的頁(yè)表再建立一張頁(yè)表，稱為外層頁(yè)表，在外層頁(yè)表中的每個(gè)表項(xiàng)中記錄了頁(yè)表頁(yè)面的物理塊號(hào)。第六章器管理6.5

基本分頁(yè)

管理方式6.5.3

兩級(jí)和多級(jí)頁(yè)表二、兩級(jí)頁(yè)表的尋址外層頁(yè)號(hào)外層頁(yè)內(nèi)地址頁(yè)內(nèi)地址P1P2d兩級(jí)頁(yè)表的邏輯地址結(jié)構(gòu)1、對(duì)于給定的邏輯地址A,由外部頁(yè)號(hào)p1，從外層頁(yè)表中找到頁(yè)表分頁(yè)所在的物理塊號(hào)。2、由外層頁(yè)內(nèi)地址p2，從分頁(yè)頁(yè)表中找到進(jìn)程頁(yè)所在的物理塊號(hào)。3、由A所在的進(jìn)程頁(yè)的物理塊號(hào)+頁(yè)內(nèi)地址得到A的物理地址。6.5

基本分頁(yè)

管理方式6.5.3

兩級(jí)和多級(jí)頁(yè)表如何根據(jù)邏輯地址得到p1,p2,w?1、32位線性邏輯地址的最高10位被硬件解釋為p1,中間10位被硬件解釋為p2，低12位解釋為頁(yè)內(nèi)偏移；2、若邏輯地址為A，頁(yè)大小為L(zhǎng),頁(yè)表長(zhǎng)度為N(每個(gè)頁(yè)表中存放的頁(yè)表項(xiàng)數(shù)）P1=INT[INT[A/L]/N]P2=mod[INT[A/L]/N]W=mod[A/L]第六章器管理第六章

器管理6.5

基本分頁(yè)

管理方式6.5.3

兩級(jí)和多級(jí)頁(yè)表三、減少頁(yè)表占用內(nèi)存的方法將當(dāng)前所需要的頁(yè)表和外層頁(yè)表放在內(nèi)存中，其余頁(yè)表放在外存，當(dāng)所需頁(yè)表不在內(nèi)存時(shí)，產(chǎn)生一中斷，將請(qǐng)求的頁(yè)表調(diào)入內(nèi)存。四、多級(jí)頁(yè)表結(jié)構(gòu)對(duì)于64位的機(jī)器，使用二級(jí)頁(yè)表，仍存在連續(xù)占用大量?jī)?nèi)存的問(wèn)題，可以采用多級(jí)頁(yè)表結(jié)構(gòu)，將外層頁(yè)表再分若干頁(yè)。第六章

器管理管理方式6.5基本分頁(yè)6.5.4反置頁(yè)表一、反置頁(yè)表用反置頁(yè)表，為每一個(gè)物理塊設(shè)一個(gè)表項(xiàng)，表項(xiàng)中放進(jìn)程號(hào)和頁(yè)號(hào)，系統(tǒng)只一張反置頁(yè)表。由于物理空間小于邏輯空間，所以使用反置頁(yè)表減少了頁(yè)表占用的內(nèi)存空間。第六章器管理管理方式6.5基本分頁(yè)6.5.4反置頁(yè)表二、反置頁(yè)表的尋址邏輯地址=進(jìn)程號(hào)+頁(yè)號(hào)+頁(yè)內(nèi)偏移地址尋址過(guò)程：根據(jù)進(jìn)程號(hào)和頁(yè)號(hào)找到物理塊號(hào)物理地址=物理塊首址+頁(yè)內(nèi)偏移地址進(jìn)程號(hào)頁(yè)號(hào)物理塊號(hào)………第六章器管理分段

管理分段機(jī)制的引入引入分段

管理的好處：1、

方便編程2、

分段共享3、

分段保護(hù)4、

動(dòng)態(tài)5、

動(dòng)態(tài)增長(zhǎng)第六章器管理6.6

分段

管理6.6.2分段系統(tǒng)的基本原理一、分段作業(yè)的地址空間被劃分成若干個(gè)段，每個(gè)段定義了一組邏輯信息，每個(gè)段的大小由相應(yīng)的邏輯信息組的長(zhǎng)度確定，段的大小不一樣,每段的邏輯地址從0開(kāi)始。第六章器管理6.6

分段

管理6.6.2分段系統(tǒng)的基本原理二、分段的邏輯地址結(jié)構(gòu)段號(hào)段的邏輯地址段內(nèi)偏移地址第六章器管理6.6分段

管理6.6.2分段系統(tǒng)的基本原理三、段表1、系統(tǒng)為每個(gè)段分配

續(xù)區(qū)，各個(gè)段可以離散地放入內(nèi)存不同的分區(qū)。2、系統(tǒng)為每個(gè)進(jìn)程建立一張段

表，段 表的每—個(gè)表項(xiàng)記錄信息；段號(hào)、段長(zhǎng)、該段的基址。第六章器管理6.6

分段

管理6.6.2分段系統(tǒng)的基本原理三、段表段號(hào)段長(zhǎng)基址030k40k120k80k215k120k(main)=030k(x)=120k(D)=215k040k80k120k段表始址段表長(zhǎng)度>01k

6k16004k2500

8k++82928k82928692段號(hào) 段長(zhǎng) 基址2100越界段號(hào)位移量w四、分段系統(tǒng)的地址變換機(jī)構(gòu)第六章器管理6.6

分段

管理6.6.2分段系統(tǒng)的基本原理五、分頁(yè)和分段的主要區(qū)別1、頁(yè)是按物理單位劃分的,段是按邏輯單位劃分的。2、頁(yè)的大小是固定的，段的大小不固定，決定于用戶編寫的程序和編譯器。3、分頁(yè)的地址空間是一維的，分段的地址空間是二維的。第六章器管理6.6

分段

管理6.6.2分段系統(tǒng)的基本原理六、信息共享多個(gè)進(jìn)程可能共享程序和數(shù)據(jù)，基本分段管管理方式下共享的實(shí)現(xiàn)是不同理方式與基本分頁(yè)的。（一）、分頁(yè)共享每個(gè)進(jìn)程為共享的程序和數(shù)據(jù)設(shè)頁(yè)表項(xiàng)，不同進(jìn)程共享頁(yè)的頁(yè)表項(xiàng)指向相同的物理塊，共享程序和數(shù)據(jù)在內(nèi)存中只留一個(gè)副本。（二）、分段共享每個(gè)進(jìn)程中，為每個(gè)共享段設(shè)一段表項(xiàng)，段表中共享段的物理地址相同。第六章器管理6.6分段管理6.6.3段頁(yè)式為了使管理方式系統(tǒng)既具有分段系統(tǒng)便

現(xiàn)、分段可共享、易于保護(hù)、可動(dòng)態(tài)等一系列優(yōu)點(diǎn)；又能象分頁(yè)系統(tǒng)那樣很好地解決內(nèi)存的外部碎片問(wèn)題，以及為各個(gè)分段可離散地分配內(nèi)存等問(wèn)題，引入了“段頁(yè)式系統(tǒng)”。第六章器管理6.6分段

管理6.6.3段頁(yè)式

管理方式一、基本原理將用戶進(jìn)程空間先劃分成若干個(gè)段，每個(gè)段劃分成若干個(gè)頁(yè)，每個(gè)進(jìn)程有一個(gè)段表，每個(gè)段都有一個(gè)頁(yè)表。地址結(jié)構(gòu)由段號(hào)、段內(nèi)頁(yè)號(hào)和頁(yè)內(nèi)地址三部分組成。每一段表項(xiàng)存放某個(gè)段的頁(yè)表始址和頁(yè)表長(zhǎng)度。段頁(yè)式第六章器管理管理方式6.6分段

管理6.6.3段頁(yè)式二、地址變換過(guò)程1、利用段號(hào)，找到某段的段表項(xiàng)，得到該段頁(yè)表的首地址。2、利用段內(nèi)頁(yè)號(hào)和由1得到的頁(yè)表始址得到頁(yè)表項(xiàng)。3、由頁(yè)表項(xiàng)得到頁(yè)所在的物理塊號(hào)。4、物理塊號(hào)與頁(yè)內(nèi)地址得到某邏輯地址的物理地址。段頁(yè)式地程6.7

80X86常規(guī)內(nèi)存尋址6.7.1內(nèi)存地址1、邏輯地址：邏輯地址（logical

address）包含在機(jī)器語(yǔ)言指令中用來(lái)指定一個(gè)操作數(shù)或一

條指令的地址。這種尋址方式在80x86著名的分段結(jié)構(gòu)中表現(xiàn)得尤為具體，它促使MS-DOS

或Windows程序

員把程序分成若干段。每一個(gè)邏輯地址都由一個(gè)段(segment)和偏移量（offset或displacement）組成，偏移量指明了從段開(kāi)始的地方到實(shí)際地址之間的距離。6.7

80X86常規(guī)內(nèi)存尋址2、線性地址（linear

address）(也稱虛擬地址virtual

address)是一個(gè)32位無(wú)符號(hào)整數(shù)，可以用來(lái)表示高達(dá)4GB的地址，也就是，高達(dá)4

294

967

296個(gè)器單元。線性地址通常用16進(jìn)制數(shù)字表示，值的范圍從0x00000000

到0xffffffff。6.7

80X86常規(guī)內(nèi)存尋址3、物理地址（physical

address）用于

器

級(jí)處理器的地址引腳發(fā)送到器單元尋址。它們與從微器總線上的電信號(hào)相對(duì)應(yīng)。物理地址由32位或36位無(wú)符號(hào)整數(shù)表示。6.7

80X86常規(guī)內(nèi)存尋址6.7.2硬件中的分段1、段選擇符和段寄存器段選擇符(segment

selector

）：是一個(gè)16位長(zhǎng)的段標(biāo)識(shí)符。段寄存器：用來(lái)存放段選擇符。13位描述符索引index1位TI2位RPL段選擇符6.7

80X86常規(guī)內(nèi)存尋址段選擇符字段字段名index描述指定了放在GDT或LDT中的相應(yīng)段描述符的。TI（(Table

Indicator)標(biāo)志指明段描述符是在GDT中（TI=0）或在LDT（TI=1）。TIRPL

請(qǐng)求者

級(jí)：當(dāng)相應(yīng)的段選擇符裝入到cs寄存器中時(shí)指示出CPU當(dāng)前的 級(jí)；6.7

80X86常規(guī)內(nèi)存尋址6.7.2硬件中的分段2、段描述符每個(gè)段都由一個(gè)8字節(jié)的段描述符(SegmentDescriptor)來(lái)描述段的特征。段描述符放在全局描述符表（Global

Descriptor

Table,GDT）或局部描述符表（Local

Descriptor

Table

，LDT）中。GDT的線性基址存放在gdtr寄存器中，當(dāng)前正被使用的LDT線性基址放在ldtr處理器寄存器中。段描述符字段Limit字段名 描述Base

包含段的起始地址G

粒度標(biāo)志G。如果該位清為0，段大小以字節(jié)為單位，否則以4096字節(jié)的倍數(shù)計(jì)。20位的Limit字段，指定了以字節(jié)為單位的段長(zhǎng)度。如果G被置為0，則一個(gè)非空段 的大小在1個(gè)字節(jié)到1MB之間變化；否則，將在4KB到4GB之間變化。系統(tǒng)標(biāo)志S，如果它被清0，則這是一個(gè)系統(tǒng)段， 內(nèi)核數(shù)據(jù)結(jié)構(gòu)，否則它是一S個(gè)普通的代碼段或數(shù)據(jù)段。4位Type字段，描述了段的類型特征和它的存取權(quán)限。TypeDPL描述符 級(jí)字段：用于限制對(duì)這個(gè)段的存取。它表示為這個(gè)段而要求的CPU最小的優(yōu)先級(jí)。因此，DPL設(shè)為0的段只能當(dāng)CPL為0時(shí)（即在內(nèi)核態(tài)）才是可 的，而DPL設(shè)為3的段對(duì)任何CPL值都是可 的。Segment-Present標(biāo)志：等于0表示段當(dāng)前不在主存中。Linux總是把這個(gè)標(biāo)志（47位）設(shè)為1，因?yàn)樗鼜膩?lái)不把整個(gè)段交換到磁盤上去。PD或B

稱為D或B的標(biāo)志，取決于是代碼段還是數(shù)據(jù)段。D或B的含義在兩種情況下稍微有所區(qū)別，但是如果段偏移量的地址是32位長(zhǎng)，就基本上把它置為1，如果這個(gè)偏移量是16位長(zhǎng)，它被清0

。AVL標(biāo)志可以由操作系統(tǒng)使用，但是被Linux忽略。6.7

80X86常規(guī)內(nèi)存尋址6.7.2硬件中的分段3、快速

段描述符為了加速邏輯地址到線性地址的轉(zhuǎn)換，80x86處理器提供一種附加的非編程的寄存器,供6個(gè)可編程的段寄存器使用。每一個(gè)非編程的寄存器含有8個(gè)字節(jié)的段描述符，由相應(yīng)的段寄存器中的段選擇符來(lái)指定。每當(dāng)一個(gè)段選擇符被裝入段寄存器時(shí)，相應(yīng)的段描述符就由內(nèi)存裝入到對(duì)應(yīng)的非編程CPU寄存器。從那時(shí)起，針對(duì)那個(gè)段的邏輯地址轉(zhuǎn)換就可以不 主存中的GDT或LDT，處理器只需直接 存放段描述符的CPU寄存器即可

。6.7

80X86常規(guī)內(nèi)存尋址6.7.2硬件中的分段4、由段選擇符獲得一個(gè)段描述符由于一個(gè)段描述符是8字節(jié)長(zhǎng)，它在GDT或LDT內(nèi)的相對(duì)地址是由段選擇符的最高13位的值乘以8得到的。例如：如果GDT在0x00020000（這個(gè)值保存在

gdtr寄存器中），且由段選擇符所指定的索引號(hào)為2，那么相應(yīng)的段描述符地址是0x00020000+(2

×8),或0x00020010。(注意:這個(gè)計(jì)算得到的地址是一個(gè)段描述符的線性地址,不是物理地址,線性地址經(jīng)過(guò)分頁(yè)單元的轉(zhuǎn)換可以得到物理地址)6.7

80X86常規(guī)內(nèi)存尋址6.7.2硬件中的分段5、分段單元如何把邏輯地址轉(zhuǎn)化為線性地址？先檢查段選擇符的TI字段，以決定段描述符保存在哪一個(gè)描述符表中。TI字段指明描述符是在GDT中（在這種情況下，分段單元從gdtr寄存器中得到GDT的線性

址）還是在激活的LDT中（在這種情況下，分段單元從ldtr寄存器中得到

LDT的線性 址）。從段選擇符的index字段計(jì)算段描述符的地址，index字段的值乘以8（一個(gè)段描述符的大?。?，這個(gè)結(jié)果與gdtr或ldtr寄存器中的內(nèi)容相加。把邏輯地址的偏移量與段描述符Base字段的值相加就得到了線性地址。(這個(gè)線性地址由分頁(yè)單元轉(zhuǎn)換得到物理地址）6.7

80X86常規(guī)內(nèi)存尋址6.7.3

Linux中的分段運(yùn)行在用戶態(tài)的所有Linux進(jìn)程都使用一對(duì)相同的段來(lái)對(duì)指令和數(shù)據(jù)尋址。這兩個(gè)段就是所謂的用戶代碼段和用戶數(shù)據(jù)段。類似地，運(yùn)行在內(nèi)核態(tài)的所有

Linux進(jìn)程都使用一對(duì)相同的段對(duì)指令和數(shù)據(jù)尋址：它們分別叫做內(nèi)核代碼段和內(nèi)核數(shù)據(jù)段。6.7

80X86常規(guī)內(nèi)存尋址6.7.3

Linux中的分段1、四個(gè)主要的Linux段的段描述符字段的值段BaseGLimitSTypeDPLD/BP用戶代碼段0x0000000010xfffff11311用戶數(shù)據(jù)段0x0000000010xfffff12311內(nèi)核代碼段0x0000000010xfffff110011內(nèi)核數(shù)據(jù)段0x0000000010xfffff120116.7

80X86常規(guī)內(nèi)存尋址6.7.3

Linux中的分段

2、Linux分段的特點(diǎn)：上述四個(gè)段相應(yīng)的段描述符由宏_

_USER_CS，__USER_DS，_

_KERNEL_CS，和_

_KERNEL_DS分別指定。例如，為了對(duì)內(nèi)核代碼段尋址，內(nèi)核只需要把這個(gè)宏產(chǎn)生的值裝進(jìn)cs段寄存器即可。與段相關(guān)的線性地址從0開(kāi)始，達(dá)到4G-1的尋址限長(zhǎng)。這就意味著在用戶態(tài)和內(nèi)核態(tài)下的所有程序可以使用相同的邏輯地址。所有段都從0x00000000開(kāi)始，這可以得出另一個(gè)重要結(jié)論，那就是在Linux下邏輯地址與線性地址是一致的，即邏輯地址的偏移量字段的值與相應(yīng)的線性地址的值總是一致的。6.7

80X86常規(guī)內(nèi)存尋址6.7.3

Linux中的分段3、Linux的全局描述符表在單處理器系統(tǒng)中只有一個(gè)GDT，而在多處理器系統(tǒng)中每個(gè)CPU對(duì)應(yīng)一個(gè)GDT。每個(gè)GDT包含18個(gè)段描述符和14個(gè)空的，未使用的，或保留的項(xiàng)。每一個(gè)

GDT中包含的18個(gè)段描述符指向下列的段：每一個(gè)GDT中包含的18個(gè)段描述符指向下列的段：用戶和內(nèi)核態(tài)下的代碼和數(shù)據(jù)段共四個(gè)任務(wù)狀態(tài)段（TSS），每個(gè)處理器有一個(gè)一個(gè)包括缺省局部描述符表的段三個(gè)局部線程

段與高級(jí)電源管理（AMP）相關(guān)的三個(gè)段與支持即插即用功能的BIOS服務(wù)程序相關(guān)的5個(gè)段被內(nèi)核用來(lái)處理“雙重錯(cuò)誤”（處理一個(gè)異常時(shí)可能會(huì)另一個(gè)異常。在這種情況下產(chǎn)生雙重錯(cuò)誤）異常的特殊TSS段6.7

80X86常規(guī)內(nèi)存尋址6.7.4

硬件中的分頁(yè)1、常規(guī)分頁(yè)從80386起，In處理器的分頁(yè)單元處理4KB的頁(yè)。32位的線性地址被分成3個(gè)字段：（Directory）最高10位中間10位最低12位頁(yè)表（Table）偏移量（Offset）6.7

80X86常規(guī)內(nèi)存尋址6.7.4

硬件中的分頁(yè)三個(gè)字段的含義正在使用的頁(yè)的物理地址存放在控制寄存器CR3中。線性地址內(nèi)的Directory字段(相當(dāng)于二級(jí)頁(yè)表中的p1)決定頁(yè) 中的 項(xiàng)，而 項(xiàng)指向適當(dāng)?shù)捻?yè)表。地址的Table字段(相當(dāng)于二級(jí)頁(yè)表中的p2)依次又決定頁(yè)表中的表項(xiàng)，而表項(xiàng)含有頁(yè)所在頁(yè)框的物理地址。Offset字段決定頁(yè)框內(nèi)的相對(duì)位置（見(jiàn)圖2-7）。由于它是一個(gè)12位