第4章存儲(chǔ)器管理

4.1存儲(chǔ)管理的功能

4.2程序的裝入和鏈接

4.3連續(xù)分配方式4.4對(duì)換4.5基本分頁(yè)存儲(chǔ)管理方式4.6基本分段存儲(chǔ)管理方式第四章

存儲(chǔ)器管理4.1.1

存儲(chǔ)器的層次結(jié)構(gòu)多級(jí)存儲(chǔ)器結(jié)構(gòu)：寄存器：

容量最小、速度最快高速緩存Cache：

容量遠(yuǎn)大于寄存器，比主存小兩三個(gè)數(shù)量級(jí)內(nèi)存RAM：

cpu直接從主存儲(chǔ)器中取得指令和數(shù)據(jù)

磁盤(pán)：

低速、價(jià)廉、容量最大

4.1.2

存儲(chǔ)器管理的功能一、地址變換二、內(nèi)存分配和回收三、內(nèi)存共享和保護(hù)四、內(nèi)存擴(kuò)充一、地址變換1.邏輯地址和物理地址邏輯地址（相對(duì)地址，虛地址）：用戶的程序經(jīng)過(guò)匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對(duì)地址的形式其首地址為0，其余指令中的地址都相對(duì)于首地址來(lái)編址不能用邏輯地址在內(nèi)存中讀取信息物理地址（絕對(duì)地址，實(shí)地址）：內(nèi)存中存儲(chǔ)單元的地址。物理地址可直接尋址。用高級(jí)語(yǔ)言編程時(shí)，要定義變量、函數(shù)，程序中有函數(shù)調(diào)用，有轉(zhuǎn)向等，都是以它們的名字進(jìn)行的，程序員在一個(gè)“名字空間”駕御自己的程序。通常把程序員用的地址空間為名空間。源程序必須經(jīng)過(guò)編譯才能執(zhí)行。程序?qū)⒈话才懦梢粋€(gè)從地址0開(kāi)始的地址空間。這就成為可以執(zhí)行的目標(biāo)程序，并存入一個(gè)以.exe結(jié)尾的文件中。（編譯程序不知道以后操作系統(tǒng)將把程序裝入何處，只好從0地址開(kāi)始編址。）目標(biāo)程序中指令地址都是相對(duì)0編址的，使用的是相對(duì)地址、邏輯地址?？梢詧?zhí)行并不意味著就能執(zhí)行，還必須由操作系統(tǒng)調(diào)入內(nèi)存才能執(zhí)行。通常把編譯程序形成的從0開(kāi)始編址的地址空間稱為作業(yè)的地址空間。(每個(gè)可執(zhí)行程序都有一個(gè)自己的地址空間。)邏輯地址(地址空間)示意圖2.重定位（地址映射）含義：將用戶程序中的邏輯地址轉(zhuǎn)換為運(yùn)行時(shí)由機(jī)器直接尋址的物理地址稱為地址重定位原因：當(dāng)程序裝入內(nèi)存時(shí),操作系統(tǒng)要為該程序分配一個(gè)合適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致,而CPU執(zhí)行指令時(shí)，是按物理地址進(jìn)行的，所以要進(jìn)行地址轉(zhuǎn)換重定位方式：分為靜態(tài)重定位和動(dòng)態(tài)重定位

因?yàn)槎嗟莱绦蛳到y(tǒng)中，主存將存放多道作業(yè)，而程序員在編寫(xiě)程序時(shí)，不可能了解自己的程序?qū)⒎旁谥鞔嬷泻翁庍\(yùn)行，不可能用絕對(duì)地址來(lái)編寫(xiě)程序。(1)

靜態(tài)地址重定位在裝入一個(gè)作業(yè)時(shí)，把作業(yè)中的指令地址全部轉(zhuǎn)換為絕對(duì)地址（地址轉(zhuǎn)換工作是在作業(yè)執(zhí)行前集中一次完成的）在作業(yè)執(zhí)行過(guò)程中就無(wú)須再進(jìn)行地址轉(zhuǎn)換工作

（2）動(dòng)態(tài)地址重定位在程序執(zhí)行過(guò)程中，在CPU訪問(wèn)內(nèi)存之前,將要訪問(wèn)的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址.動(dòng)態(tài)重定位依靠硬件地址變換機(jī)構(gòu)完成靜態(tài)地址重定位示意圖0100500mova,(500)2345邏輯地址空間裝入程序內(nèi)存空間mova,(1500)2345100011001500靜態(tài)重定位靜態(tài)重定位的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：不需要硬件的支持。

缺點(diǎn)：程序必須占用連續(xù)的內(nèi)存空間；一旦程序裝入后不能移動(dòng)，不易實(shí)現(xiàn)共享。

+

內(nèi)存空間

VR

BR…..動(dòng)態(tài)地址重定位動(dòng)態(tài)地址重定位邏輯地址空間動(dòng)態(tài)地址映射的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：程序占用的內(nèi)存空間是動(dòng)態(tài)可變的，可以把程序從某個(gè)存儲(chǔ)區(qū)移到另一個(gè)區(qū)域一個(gè)程序不一定要求占用一個(gè)連續(xù)的內(nèi)存空間?？梢圆糠值匮b入程序運(yùn)行。便于多個(gè)進(jìn)程共享同一個(gè)程序的代碼。動(dòng)態(tài)地址重定位的代價(jià)：需要硬件的支持。實(shí)現(xiàn)存儲(chǔ)管理的軟件算法較為復(fù)雜。4.1.2存儲(chǔ)管理功能一、地址變換二、內(nèi)存分配和回收三、內(nèi)存共享和保護(hù)四、內(nèi)存擴(kuò)充為了有效合理地利用內(nèi)存，設(shè)計(jì)內(nèi)存的分配和回收方法時(shí)，必須考慮和確定以下幾種策略和數(shù)據(jù)結(jié)構(gòu)：1分配結(jié)構(gòu)：登記內(nèi)存的使用情況2放置策略：確定調(diào)入內(nèi)存的程序和數(shù)據(jù)在內(nèi)存中的位置，即選擇內(nèi)存空閑區(qū)的原則3

交換策略：在需要將某個(gè)程序段和數(shù)據(jù)調(diào)入內(nèi)存時(shí)如果內(nèi)存沒(méi)有足夠的空閑區(qū)，由交換策略來(lái)確定把內(nèi)存中的哪些程序段和數(shù)據(jù)段調(diào)出內(nèi)存，以便騰出足夠的空間。

二、內(nèi)存分配和回收4調(diào)入策略：決定信息裝入內(nèi)存的時(shí)機(jī)，有兩種：在用戶請(qǐng)求時(shí)調(diào)入，稱為請(qǐng)調(diào)；根據(jù)某種算法，確定系統(tǒng)將要使用的信息，并在執(zhí)行前預(yù)先調(diào)入內(nèi)存，稱為預(yù)調(diào)

5回收策略：回收時(shí)機(jī)，以及對(duì)所回收的內(nèi)存空閑區(qū)和已存在的內(nèi)存空閑區(qū)的調(diào)整4.1.2存儲(chǔ)管理功能一、地址變換二、內(nèi)存分配和回收三、內(nèi)存共享和保護(hù)四、內(nèi)存擴(kuò)充三、內(nèi)存共享和保護(hù)內(nèi)存共享是為了更有效利用內(nèi)存內(nèi)存保護(hù)是為了保證在內(nèi)存中的多道程序只能在給定的存儲(chǔ)區(qū)域內(nèi)活動(dòng)并互不產(chǎn)生干擾。包括：防止地址越界防止越權(quán)(對(duì)共享區(qū)有訪問(wèn)權(quán))

最簡(jiǎn)單、最常用的保護(hù)方法是上下界保護(hù)法（1）在CPU中設(shè)置一對(duì)下限寄存器和上限寄存器存放用戶作業(yè)在主存中的下限和上限地址；常用內(nèi)存保護(hù)方法下界寄存器存放程序裝入內(nèi)存后的開(kāi)始地址（首址）上界寄存器存放程序裝入內(nèi)存后的末地址判別式：下界寄存器≤物理地址＜上界寄存器（2）設(shè)置一個(gè)寄存器作為基址寄存器，設(shè)置另一寄存器作為限長(zhǎng)寄存器（指示存儲(chǔ)區(qū)長(zhǎng)度）問(wèn)：訪問(wèn)作業(yè)的邏輯地址分別為2K、10K、20K時(shí)是否會(huì)越界？4.1.2存儲(chǔ)管理功能一、地址變換二、內(nèi)存分配和回收三、內(nèi)存共享和保護(hù)四、內(nèi)存擴(kuò)充四、內(nèi)存擴(kuò)充（虛擬存儲(chǔ)）通過(guò)操作系統(tǒng)利用程序執(zhí)行的局部性，在內(nèi)存和外存之間通過(guò)不斷交換信息，構(gòu)成一個(gè)容量超過(guò)內(nèi)存物理容量的由外存和內(nèi)存共同組成的虛擬存儲(chǔ)器。要實(shí)現(xiàn)內(nèi)存擴(kuò)充，在程序執(zhí)行過(guò)程中，內(nèi)存和外存之間必須經(jīng)常地交換數(shù)據(jù)。最基本的控制數(shù)據(jù)流動(dòng)的方式有：①用戶程序自己控制方式，典型的例子是覆蓋。②操作系統(tǒng)控制方式，又可進(jìn)一步分為：交換方式、請(qǐng)調(diào)方式、預(yù)調(diào)入方式。

與實(shí)際物理存儲(chǔ)器只有一個(gè)（單機(jī)系統(tǒng)中），且被所有進(jìn)程共享不一樣，每個(gè)進(jìn)程都擁有自己的虛擬存儲(chǔ)器，且虛擬存儲(chǔ)器的容量是由計(jì)算機(jī)的地址結(jié)構(gòu)和尋址方式確定的。若CPU給出的有效地址長(zhǎng)度為18位,可以尋址范圍為:0--256k;若地址的長(zhǎng)度為為20位,則尋址范圍為:1024k.庫(kù)匯編編譯主子1子2目標(biāo)模塊鏈接程序裝入模塊庫(kù)主子1子2裝入程序內(nèi)存庫(kù)主子1子24.2

程序的裝入和鏈接圖a靜態(tài)鏈接，靜態(tài)裝入圖b動(dòng)態(tài)鏈接，動(dòng)態(tài)裝入引言：存儲(chǔ)器管理方式1連續(xù)分配方式：指為一個(gè)系統(tǒng)或用戶程序分配一個(gè)連續(xù)的空間，主要有：?jiǎn)我贿B續(xù)區(qū)管理方式分區(qū)管理方式：通?？煞譃楣潭ǚ謪^(qū)方式和可變分區(qū)方式2離散分配方式：為了減少因連續(xù)分配所產(chǎn)生的碎片，提高內(nèi)存的利用率產(chǎn)生了離散分配方式，它可將一個(gè)用戶程序離散地分配到內(nèi)存中的多個(gè)不相連接的區(qū)域中。其方式有：分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式段頁(yè)式存儲(chǔ)管理方式虛擬存儲(chǔ)管理方式：為了進(jìn)一步提高內(nèi)存利用率，又形成了一種虛擬存儲(chǔ)管理方式。其方式有：請(qǐng)求分頁(yè)管理方式請(qǐng)求分段管理方式請(qǐng)求段頁(yè)式管理方式4.3連續(xù)分配方式

4.3.1單一連續(xù)分配內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。最簡(jiǎn)單，適用于單用戶、單任務(wù)的OS。優(yōu)點(diǎn)：易于管理。缺點(diǎn)：不能充分利用CPU不能充分利用內(nèi)存（低了內(nèi)存的利用率）不能充分利用外設(shè)實(shí)現(xiàn)思想1、地址轉(zhuǎn)換：靜態(tài)重定位硬件支持：界限寄存器，內(nèi)容為當(dāng)前可供用戶使用的內(nèi)存區(qū)域的起始地址。絕對(duì)地址=邏輯地址+界限寄存器值2、存儲(chǔ)保護(hù)作業(yè)執(zhí)行時(shí)，CPU對(duì)每條指令中的絕對(duì)地址進(jìn)行檢查。若界限地址≤絕對(duì)地址≤內(nèi)存最大地址則可執(zhí)行，否則有地址錯(cuò)誤，形成“地址越界”中斷限定作業(yè)在規(guī)定的內(nèi)存區(qū)內(nèi)執(zhí)行，避免破壞操作系統(tǒng)的信息，達(dá)到“存儲(chǔ)保護(hù)”的目的。3、存儲(chǔ)擴(kuò)充：覆蓋技術(shù)，使一個(gè)大作業(yè)能在小的空間中運(yùn)行固定分區(qū)——把主存分成若干個(gè)固定大小的存儲(chǔ)區(qū)。OS20K28K60K124K256K進(jìn)程A（6K）進(jìn)程B（25K）進(jìn)程C（36K）4.3.2固定分區(qū)分配

分區(qū)說(shuō)明表基本思想把內(nèi)存中可分配的用戶區(qū)預(yù)先劃分成若干個(gè)連續(xù)區(qū)，每個(gè)連續(xù)區(qū)的大小可以相同，也可以不同（等長(zhǎng)或不等長(zhǎng)分區(qū)）。分區(qū)個(gè)數(shù)固定，每個(gè)分區(qū)的大小固定

一個(gè)分區(qū)中裝入一個(gè)作業(yè)，作業(yè)在執(zhí)行過(guò)程中不會(huì)改變存放區(qū)域適用于多道程序設(shè)計(jì)系統(tǒng)固定分區(qū)性能分析在作業(yè)大小和出現(xiàn)頻率均已知的情況下，固定分區(qū)是合適的。在這種情況下分區(qū)的大小選擇與作業(yè)大小相當(dāng)，這樣內(nèi)存的使用效率較高。但是若作業(yè)的大小和出現(xiàn)的頻率不知道時(shí)，勢(shì)必造成分區(qū)的大小和作業(yè)的大小相差甚遠(yuǎn)，這樣就會(huì)造成存儲(chǔ)空間的浪費(fèi)，從而影響整個(gè)系統(tǒng)的效率。返回1、動(dòng)態(tài)分區(qū)原則：存儲(chǔ)空間的劃分是在裝作業(yè)時(shí)進(jìn)行的。從可用的自由存儲(chǔ)空間內(nèi)，劃出一個(gè)大小正好等于作業(yè)大小的存儲(chǔ)區(qū)，并分配給這一作業(yè)。

進(jìn)程A（8K）進(jìn)程D（124K）進(jìn)程B（16K）進(jìn)程C（64K）…OS進(jìn)程A進(jìn)程B進(jìn)程C進(jìn)程DOS進(jìn)程A進(jìn)程B進(jìn)程COS進(jìn)程A進(jìn)程BOS進(jìn)程A4.3.3動(dòng)態(tài)分區(qū)分配OSA（8K）24K空閑區(qū)B（16K）C完成（64K）空閑區(qū)D（124K）OSA（8K）8K空閑區(qū)B（16K）E（50K）D（124K）14K空閑區(qū)F（16K）OSA（8K）8K空閑區(qū)空閑區(qū)16KE（50K）D（124K）空閑合并124+14=138K進(jìn)程E（50K）進(jìn)程F（16K）進(jìn)入內(nèi)存進(jìn)程B（16K）進(jìn)程D（124K）完成

內(nèi)存分配變化過(guò)程2.

動(dòng)態(tài)分區(qū)時(shí)的分配與回收（1）使用的數(shù)據(jù)結(jié)構(gòu)（空閑分區(qū)表）

可用表、自由鏈、請(qǐng)求表（2）常用分區(qū)分配算法

①最先適應(yīng)法：空閑區(qū)按地址順序從小到大登記。依次檢查空閑區(qū)表目，把第一個(gè)找到能容納申請(qǐng)要求的內(nèi)存區(qū)分配給申請(qǐng)者。

②最佳適應(yīng)算法：空閑區(qū)按其大小遞增的順序組成可用表。把找到的第一個(gè)滿足要求的空閑區(qū)分配。

③最壞適應(yīng)算法：按空閑區(qū)按其大小遞減的順序組成空閑區(qū)可用表或自由鏈，每次分配最大的空閑區(qū)。④循環(huán)適應(yīng)算法：每次從上一次查詢停止的位置繼續(xù)向下尋找滿足要求的空閑區(qū)。最先適應(yīng)法(first-fit)：該算法的分配和釋放的時(shí)間性能較好，較大的空閑分區(qū)可以被保留在內(nèi)存高端。但隨著低端分區(qū)不斷劃分而產(chǎn)生較多小分區(qū)，每次分配時(shí)查找時(shí)間開(kāi)銷會(huì)增大。最佳適應(yīng)法(best-fit)：從個(gè)別來(lái)看，外碎片較小，但從整體來(lái)看，會(huì)形成較多外碎片。較大的空閑分區(qū)可以被保留。最壞適應(yīng)法(worst-fit)：基本不留下小空閑分區(qū)，但大作業(yè)的要求往往難以滿足。循環(huán)適應(yīng)法（next-fit）：分區(qū)分布均勻，但會(huì)缺少較大分區(qū)。例：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊(duì)列經(jīng)分析可知：最佳適應(yīng)法對(duì)這個(gè)作業(yè)序列是合適的，而其它兩種對(duì)該作業(yè)序列是不合適的。（3）分區(qū)回收系統(tǒng)回收分區(qū)的主要步驟：1檢查回收分區(qū)是否與空閑區(qū)鄰接，如鄰接則加以合并；2修改說(shuō)明表碎片問(wèn)題由于空閑區(qū)的大小與申請(qǐng)內(nèi)存的大小相等的情況是很少的，絕大多數(shù)情況是從一個(gè)空閑區(qū)中切去一塊，剩下的部分作為一個(gè)空閑區(qū)仍留在空閑區(qū)表中，隨著時(shí)間的推移，空閑區(qū)的發(fā)展趨勢(shì)是越來(lái)越小，直至不能滿足任何用戶要求。這種不能被任何用戶使用的極小的空閑區(qū)稱為碎片。碎片的出現(xiàn)造成了存儲(chǔ)空間的浪費(fèi)。碎片問(wèn)題的解決合并（見(jiàn)分區(qū)回收）移動(dòng)(緊湊)通過(guò)在內(nèi)存移動(dòng)程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域，使分散的空閑區(qū)集中起來(lái)，以容納新的作業(yè)。

緊湊的示意

分區(qū)存儲(chǔ)管理的優(yōu)缺點(diǎn)

l

優(yōu)點(diǎn)：(1)多個(gè)程序共享內(nèi)存，有助于多道程序設(shè)計(jì)。(2)要求的硬件支持少，管理算法簡(jiǎn)單，實(shí)現(xiàn)容易。l

缺點(diǎn)：(1)內(nèi)存利用率仍然不高。存在著嚴(yán)重的碎小空閑區(qū)(碎片)不能利用的問(wèn)題，影響了內(nèi)存的利用率。(2)作業(yè)或進(jìn)程的大小受分區(qū)大小控制，除非配合采用覆蓋和交換技術(shù)。(3)難以實(shí)現(xiàn)各分區(qū)間的信息共享

4.4對(duì)換對(duì)換的引入就是系統(tǒng)根據(jù)需要把主存中暫時(shí)不運(yùn)行的某個(gè)(或某些)作業(yè)部分或全部移到外存，而把外存中的某個(gè)(或某些)作業(yè)移到相應(yīng)的主存區(qū)，并使其投入運(yùn)行。交換技術(shù)是利用外存來(lái)邏輯地?cái)U(kuò)充主存對(duì)換空間的管理對(duì)換區(qū)，空閑分區(qū)表或分區(qū)鏈，采用連續(xù)分配方式，進(jìn)程的換出和換入換出過(guò)程 選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，換出后收回內(nèi)存空間，修改進(jìn)程的PCB相關(guān)信息換入過(guò)程 找出“就緒”狀態(tài)并已經(jīng)換出的進(jìn)程，將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程，將其換入直到已無(wú)可換入的進(jìn)程和無(wú)可換出的進(jìn)程4.5基本分頁(yè)存儲(chǔ)管理方式

4.5.1頁(yè)面與頁(yè)表

1．內(nèi)存空間、進(jìn)程地址空間分頁(yè)

邏輯頁(yè)面（頁(yè)）：將一個(gè)進(jìn)程的地址空間劃分成若干個(gè)大小相等的區(qū)域，稱為邏輯頁(yè)面

物理頁(yè)面（物理塊、頁(yè)框）：將內(nèi)存空間劃分成與頁(yè)相同大小的若干個(gè)物理塊，稱為塊或頁(yè)框。頁(yè)面的大小應(yīng)選擇適中，通常是2的冪，例512B～8KB。

在為進(jìn)程分配內(nèi)存時(shí)，將進(jìn)程中的若干頁(yè)分別裝入多個(gè)不相鄰接的塊中。2．地址結(jié)構(gòu)分頁(yè)地址中的地址結(jié)構(gòu)如下：

它含有兩部分：前一部分為頁(yè)號(hào)P，后一部分為位移量W(或稱為頁(yè)內(nèi)地址)。圖中的地址長(zhǎng)度為32位，其中0～11位為頁(yè)內(nèi)地址，即每頁(yè)的大小為4KB；12～31位為頁(yè)號(hào)，地址空間最多允許有1M頁(yè)。

若給定一個(gè)邏輯地址空間中的地址為A，頁(yè)面大小為L(zhǎng)，則頁(yè)號(hào)P和頁(yè)內(nèi)地址w可按下式求得：

P=int(A/L)

W=A%L其中，int是取整函數(shù)，%是取余運(yùn)算。例：系統(tǒng)頁(yè)面大小為１KB，設(shè)A＝1201B，則P=？,W=？（0,1201）

3．頁(yè)表系統(tǒng)為每個(gè)進(jìn)程建立一張頁(yè)面映射表，簡(jiǎn)稱頁(yè)表。頁(yè)表保存于內(nèi)存。每個(gè)邏輯頁(yè)在頁(yè)表中占一個(gè)表項(xiàng)，記錄該頁(yè)在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)。進(jìn)程在執(zhí)行時(shí)，通過(guò)查找頁(yè)表，就可以找到每頁(yè)所對(duì)應(yīng)的物理塊號(hào)?？梢?jiàn)，頁(yè)表的作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射頁(yè)表的作用

作業(yè)2(0頁(yè))操作系統(tǒng)作業(yè)2(1頁(yè))作業(yè)3(0頁(yè))作業(yè)1(0頁(yè))作業(yè)1(1頁(yè))作業(yè)2(2頁(yè))051601224708作業(yè)1作業(yè)2作業(yè)31KB2KB001KB2KB03KB1KB0邏輯地址空間頁(yè)表物理地址空間頁(yè)號(hào)塊號(hào)1KB2KB3KB4KB5KB6KB7KB8KB9KB10KB分頁(yè)存儲(chǔ)管理基本原理等分主存：把主存劃分成相同大小的存儲(chǔ)塊。用戶邏輯地址空間的分頁(yè)：邏輯地址空間劃分成與物理頁(yè)大小相同的部分。邏輯地址的表示：虛擬地址A=>（p,d）, p--頁(yè)面號(hào)；d--相對(duì)地址（頁(yè)內(nèi)地址） 頁(yè)面大小L，則p=int(A/L)；d=A%L主存分配原則：系統(tǒng)以物理頁(yè)為單位把主存分給作業(yè)或進(jìn)程，并且分給一個(gè)作業(yè)或進(jìn)程的物理頁(yè)不一定是相鄰和連續(xù)的。4.5.2地址變換機(jī)構(gòu)1．基本的地址變換機(jī)構(gòu)

1)基本任務(wù)：利用頁(yè)表把程序中的邏輯地址變換成物理地址。2)硬件支持：在系統(tǒng)中設(shè)置頁(yè)表寄存器，用來(lái)存放頁(yè)表的始址和頁(yè)表的長(zhǎng)度。（其值來(lái)源于進(jìn)程的PCB）3)地址映射過(guò)程：首先系統(tǒng)將頁(yè)號(hào)與頁(yè)表長(zhǎng)度進(jìn)行比較，如果頁(yè)號(hào)大于頁(yè)表寄存器中的頁(yè)表長(zhǎng)度，則訪問(wèn)越界，產(chǎn)生越界中斷。如未出現(xiàn)越界，則根據(jù)頁(yè)表寄存器中的頁(yè)表始址和頁(yè)號(hào)計(jì)算出該頁(yè)在頁(yè)表項(xiàng)中的位置，得到該頁(yè)的物理塊號(hào)。與此同時(shí)，將邏輯地址中的頁(yè)內(nèi)地址與得到的物理塊號(hào)一起形成實(shí)際物理地址分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)

例1：作業(yè)地址空間共有7個(gè)頁(yè)，每頁(yè)的相對(duì)地址為0~1023，1024~2047，2048~3071，…，6144~6150。其對(duì)應(yīng)的主存塊在頁(yè)表中已列出。分別為5，7，9，15，13，10，16共7塊。假定頁(yè)表在主存始址為500。若該程序從第0頁(yè)開(kāi)始運(yùn)行，且現(xiàn)程序計(jì)數(shù)器內(nèi)容為：練習(xí)14.……..109…0硬件動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)工作如下：

1、把該作業(yè)的頁(yè)表始址（500）和頁(yè)表長(zhǎng)度（7）放入控制寄存器中。2、將程序計(jì)數(shù)器內(nèi)容的頁(yè)號(hào)部分（0）與控制寄存器中的頁(yè)表長(zhǎng)度（7）相比較，若頁(yè)號(hào)<頁(yè)表長(zhǎng)度時(shí)轉(zhuǎn)3，否則產(chǎn)生地址越界，終止程序運(yùn)行。

3、按控制寄存器中的頁(yè)表始址找到頁(yè)表，在頁(yè)表中查邏輯頁(yè)對(duì)應(yīng)的物理頁(yè)號(hào)（5）

4、把主存塊號(hào)5與程序計(jì)數(shù)器中的頁(yè)內(nèi)位移相拼接，從而得到該操作所在主存的物理地址：5×1024+100=5220

5、按地址5220訪問(wèn)內(nèi)存，完成指定操作。練習(xí)解答例2：已知某分頁(yè)系統(tǒng)，主存容量為64k，頁(yè)面大小為1k，對(duì)一個(gè)4頁(yè)大的作業(yè)，第0、1、2、3頁(yè)被分配到內(nèi)存的2、4、6、7塊中。求：將十進(jìn)制的邏輯地址1023、2500、4500轉(zhuǎn)換成物理地址。解:(1)1023/1K，得到頁(yè)號(hào)為0，頁(yè)內(nèi)地址1023。又對(duì)應(yīng)的物理塊號(hào)為2，故物理地址為2*1k+1023=3071(2)2500/1K，得到頁(yè)號(hào)為2，頁(yè)內(nèi)地址452。又對(duì)應(yīng)的物理塊號(hào)為6，故物理地址為6*1k+452=6596(3)4500/1K，得到頁(yè)號(hào)為4，頁(yè)內(nèi)地址404。因?yàn)轫?yè)號(hào)不小于頁(yè)表長(zhǎng)度，故產(chǎn)生越界中斷。若頁(yè)的大小為4K，則地址轉(zhuǎn)換機(jī)構(gòu)將邏輯地址0轉(zhuǎn)換成的物理地址為＿＿＿。在一個(gè)頁(yè)式存儲(chǔ)管理系統(tǒng)中，頁(yè)表內(nèi)容如下所示：

復(fù)習(xí)：

2．具有快表的地址變換機(jī)構(gòu)

“兩次訪內(nèi)”問(wèn)題:CPU存取一個(gè)數(shù)據(jù)，需兩次訪問(wèn)內(nèi)存。第1次訪存取物理塊號(hào)、第2次取數(shù)。使計(jì)算機(jī)的處理速度降低近1/2。解決方法：增設(shè)“快表”一組高速緩沖存儲(chǔ)器，稱為“聯(lián)想存儲(chǔ)器”或“快表”，用以存放當(dāng)前訪問(wèn)的那些頁(yè)表項(xiàng)

引入快表的性能分析

引入快表之后的地址變換過(guò)程引入快表的性能分析假定訪問(wèn)主存的時(shí)間為200ns，訪問(wèn)高速緩沖存儲(chǔ)器的時(shí)間為40ns，假設(shè)查快表的命中率為90%。將邏輯地址轉(zhuǎn)換成實(shí)際物理地址進(jìn)行存取的平均訪問(wèn)時(shí)間為：

（200+40）*90%+（200+200）*10%=256（ns）。不使用快表需兩次訪問(wèn)主存的時(shí)間：200*2=400ns。可見(jiàn)使用快表與不使用快表相比，訪問(wèn)時(shí)間下降了36%。引入“快表”后的地址變換過(guò)程

在CPU給出有效地址后，地址變換機(jī)構(gòu)自動(dòng)地將頁(yè)號(hào)送入高速緩存，確定所需要的頁(yè)是否在快表中。若是，則直接讀出該頁(yè)所對(duì)應(yīng)的物理塊號(hào)，送入物理地址寄存器；若在快表中未找到對(duì)應(yīng)的頁(yè)表項(xiàng)，則需再訪問(wèn)內(nèi)存中的頁(yè)表，找到后，把從頁(yè)表中讀出的頁(yè)表項(xiàng)存入快表，以取代一個(gè)舊的頁(yè)表項(xiàng)。具有快表的地址變換機(jī)構(gòu)

4.5.3兩級(jí)和多級(jí)頁(yè)表解決大頁(yè)表占用大的連續(xù)存儲(chǔ)空間的問(wèn)題CPU具有32位地址時(shí),使用232邏輯地址空間的分頁(yè)系統(tǒng),規(guī)定頁(yè)面4KB時(shí),每個(gè)進(jìn)程頁(yè)表的表項(xiàng)有1M個(gè),若表項(xiàng)占用4個(gè)字節(jié),則每個(gè)進(jìn)程需要占用4MB連續(xù)內(nèi)存空間存放頁(yè)表多級(jí)頁(yè)表概念：頁(yè)表也進(jìn)行分頁(yè)，內(nèi)存僅存放當(dāng)前使用的頁(yè)表,暫時(shí)不用部分放在磁盤(pán)上,待用到時(shí)再調(diào)入具體做法：把整個(gè)頁(yè)表進(jìn)行分頁(yè),分成一張張小頁(yè)表(稱為頁(yè)表頁(yè)),小頁(yè)表的大小與頁(yè)框相同，為進(jìn)行索引查找,應(yīng)該為這些小頁(yè)表建一張頁(yè)目錄表基本分頁(yè)存儲(chǔ)管理 為離散分配的頁(yè)表再建一張頁(yè)表，稱為：外層頁(yè)表或頁(yè)目錄表外層頁(yè)表頁(yè)表增設(shè)外層頁(yè)表寄存器，存放外層頁(yè)表的始址外層頁(yè)號(hào) 外層頁(yè)內(nèi)地址 頁(yè)內(nèi)地址31222112110兩級(jí)頁(yè)表結(jié)構(gòu)

兩級(jí)頁(yè)表的地址變換機(jī)構(gòu) 二級(jí)頁(yè)表地址變換需三次訪問(wèn)主存：一次訪問(wèn)頁(yè)目錄、一次訪問(wèn)頁(yè)表頁(yè)、一次訪問(wèn)指令或數(shù)據(jù)，訪問(wèn)時(shí)間加了兩倍外層頁(yè)號(hào) 外層頁(yè)內(nèi)地址 頁(yè)內(nèi)地址外部頁(yè)表寄存器＋＋外部頁(yè)表 頁(yè)表 物理地址2．多級(jí)頁(yè)表對(duì)于32位的機(jī)器，采用兩級(jí)頁(yè)表結(jié)構(gòu)是合適的；但對(duì)于64位的機(jī)器，采用兩級(jí)頁(yè)表是否仍可適用的問(wèn)題，須做以下簡(jiǎn)單分析。如果頁(yè)面大小仍采用4KB即212B，那么還剩下52位，假定仍按物理塊的大小(212位)來(lái)劃分頁(yè)表，則將余下的42位用于外層頁(yè)號(hào)。此時(shí)在外層頁(yè)表中可能有4096G個(gè)頁(yè)表項(xiàng)，要占用16384GB的連續(xù)內(nèi)存空間。這樣的結(jié)果顯然是不能令人接受的，因此必須采用多級(jí)頁(yè)表，將外層頁(yè)表再進(jìn)行分頁(yè)，也就是將各分頁(yè)離散地裝入到不相鄰接的物理塊中，再利用第2級(jí)的外層頁(yè)表來(lái)映射它們之間的關(guān)系。

4.5基本分頁(yè)存儲(chǔ)管理方式4.5.4反置頁(yè)表一、反置頁(yè)表

用反置頁(yè)表，為每一個(gè)物理頁(yè)設(shè)一個(gè)表項(xiàng)，表項(xiàng)中放進(jìn)程號(hào)和頁(yè)號(hào)，系統(tǒng)只維護(hù)一張反置頁(yè)表。由于物理存儲(chǔ)空間小于邏輯存儲(chǔ)空間，所以使用反置頁(yè)表減少了頁(yè)表占用的內(nèi)存空間。二、反置頁(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)偏移地址

基本分頁(yè)的特點(diǎn)優(yōu)點(diǎn)：存在頁(yè)內(nèi)碎片，但碎片相對(duì)較小，內(nèi)存利用率較高實(shí)現(xiàn)了離散分配，消除了程序浮動(dòng)；缺點(diǎn)：需要專門(mén)的硬件支持，尤其“快表”；內(nèi)存訪問(wèn)的效率下降。頁(yè)式：按內(nèi)存物理頁(yè)大小將進(jìn)程空間分頁(yè)（用戶不可見(jiàn)），內(nèi)存空間等長(zhǎng)段式:

按程序邏輯結(jié)構(gòu)將進(jìn)程空間分段（用戶可見(jiàn)），內(nèi)存空間不等長(zhǎng)4.6基本分段存儲(chǔ)管理方式基本分段管理思想的引入基本原理地址變換分段與分頁(yè)的主要區(qū)別段頁(yè)式存儲(chǔ)管理方式4.6基本分段存儲(chǔ)管理方式

4.6.1分段存儲(chǔ)管理方式的引入1)方便編程通常，用戶把自己的作業(yè)按照邏輯關(guān)系劃分為若干個(gè)段，每個(gè)段都是從0開(kāi)始編址，并有自己的名字和長(zhǎng)度。因此，希望要訪問(wèn)的邏輯地址是由段名(段號(hào))和段內(nèi)偏移量(段內(nèi)地址)決定的。例如，下述的兩條指令便是使用段名和段內(nèi)地址：LOADl，[A]|〈D〉；STORE1，[B]|〈C〉；其中，前一條指令的含義是將分段A中D單元內(nèi)的值讀入寄存器1；后一條指令的含義是將寄存器1的內(nèi)容存入B分段的C單元中。

2)信息共享:共享的實(shí)現(xiàn)以是信息的邏輯單位為基礎(chǔ)

3)信息保護(hù)4)動(dòng)態(tài)增長(zhǎng)5)動(dòng)態(tài)鏈接4.6.2分段系統(tǒng)的基本原理1.分段

一個(gè)用戶程序可劃分為若干段（如一個(gè)主程序、一個(gè)或幾個(gè)子程序、數(shù)據(jù)段等），每個(gè)段在邏輯上是完整的（是一個(gè)獨(dú)立的功能模塊），都有自己的名字，且都有一段連續(xù)的地址空間。地址組成：段號(hào)段內(nèi)地址3116150例：01kCALL[X]|<Y>LOADL,[A]|6STOREL,[B]|<C>分段MAIN(主程)Y:

0640分段X（子程）6：

分段A（數(shù)組）05000300分段B2．段表

在系統(tǒng)中為每個(gè)進(jìn)程建立一張段映射表，簡(jiǎn)稱為“段表”。進(jìn)程在執(zhí)行中，通過(guò)查段表來(lái)找到每個(gè)段所對(duì)應(yīng)的內(nèi)存區(qū)。可見(jiàn)，段表實(shí)現(xiàn)了從邏輯段到物理內(nèi)存區(qū)的映射。(1)段長(zhǎng)(或稱段的容量)。該段的長(zhǎng)度，即其字節(jié)數(shù)，在虛存和實(shí)存中段長(zhǎng)是一樣的。(2)主存起始地址。該段裝入主存內(nèi)的起始地址。(3)存取控制權(quán)限。為了實(shí)現(xiàn)段的保護(hù)，規(guī)定各段的存取權(quán)限。例如，執(zhí)行E：執(zhí)行一個(gè)程序或子程序，不允許讀或?qū)?；讀R：允許讀，不允許寫(xiě)或執(zhí)行；寫(xiě)W：允許寫(xiě)，不允許讀或執(zhí)行。除此之外，還可以是上述三種權(quán)限的組合，當(dāng)存取要求違反了段的存取權(quán)限，則發(fā)生保護(hù)中斷。利用段表實(shí)現(xiàn)地址映射

(main)=030k(x)=120k(D)=215k040k80k120k

3．地址變換機(jī)構(gòu)

段表寄存器:用于存放段表始址和段表長(zhǎng)度。

越界訪問(wèn)控制:邏輯地址的段號(hào)與段表長(zhǎng)度比較；段內(nèi)地址與段表中保存的段長(zhǎng)比較。

分段系統(tǒng)的地址變換過(guò)程

段表始址段表長(zhǎng)度（4）段表寄存器≤153705物理地址段號(hào)3105邏輯地址越界中斷段表基址段長(zhǎng)150K35K500K9K300K20K100K42K3210段號(hào)內(nèi)存150*1024=153600153600+105=153705練習(xí)：對(duì)于如下所示的段表，請(qǐng)將邏輯地址（0，137），（1，4000），（2，3600），（5，230）轉(zhuǎn)換成物理地址。解:(1)段號(hào)0<段表長(zhǎng)，且137<段長(zhǎng)10k，故段號(hào)、段內(nèi)地址全部合法。得物理地址為50k+137=51337解:(2)段號(hào)1<段表長(zhǎng)，段號(hào)合法。4000>段長(zhǎng)3k，因此產(chǎn)生越界中斷。解:(3)段號(hào)2<段表長(zhǎng)，且3600<段長(zhǎng)5k，故段號(hào)、段內(nèi)地址全部合法。得物理地址為70k+3600=75280解:(4)段號(hào)5＝段表長(zhǎng)，故段號(hào)不合法。產(chǎn)生越界中斷。

4．分頁(yè)和分段的主要區(qū)別由上所述不難看出，分頁(yè)和分段系統(tǒng)有許多相似之處。比如，兩者都采用離散分配方式，且都要通過(guò)地址映射機(jī)構(gòu)來(lái)實(shí)現(xiàn)地址變換。但在概念上兩者完全不同，主要表現(xiàn)在下述三個(gè)方面。(1)頁(yè)是信息的物理單位，分頁(yè)是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率?；蛘哒f(shuō)，分頁(yè)僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，它含有一組其意義相對(duì)完整的信息。分段的目的是為了能更好地滿足用戶的需要。(2)頁(yè)的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，是由機(jī)器硬件實(shí)現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁(yè)面；而段的長(zhǎng)度卻不固定，決定于用戶所編寫(xiě)的程序，通常由編譯程序在對(duì)源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來(lái)劃分。(3)分頁(yè)的