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

1、第四章 存儲(chǔ)器管理,4.1 存儲(chǔ)器的層次結(jié)構(gòu)4.2 程序的裝入和鏈接 4.3 連續(xù)分配方式 4.4 基本分頁(yè)存儲(chǔ)管理方式 4.5 基本分段存儲(chǔ)管理方式 4.6 虛擬存儲(chǔ)器的基本概念 4.7 請(qǐng)求分頁(yè)存儲(chǔ)管理方式 4.8 頁(yè)面置換算法 4.9 請(qǐng)求分段存儲(chǔ)管理方式,存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要組成部分，操作系統(tǒng)中的存儲(chǔ)管理是指對(duì)內(nèi)存的管理，它是操作系統(tǒng)的重要功能之一。,充分利用內(nèi)存，為多道程序并發(fā)執(zhí)行提供存

2、儲(chǔ)基礎(chǔ)盡可能方便用戶使用自動(dòng)裝入用戶程序用戶程序中不必考慮硬件細(xì)節(jié)系統(tǒng)能夠解決程序空間比實(shí)際內(nèi)存空間大的問(wèn)題,存儲(chǔ)器管理的目的：,程序的長(zhǎng)度在執(zhí)行時(shí)可以動(dòng)態(tài)伸縮內(nèi)存存取速度快存儲(chǔ)保護(hù)與安全共享與通信及時(shí)了解有關(guān)資源的使用狀況實(shí)現(xiàn)的性能和代價(jià)要合理,內(nèi)存空間的管理、分配與回收內(nèi)存共享--代碼共享，數(shù)據(jù)共享通過(guò)代碼共享節(jié)省內(nèi)存空間，提高內(nèi)存利用率通過(guò)數(shù)據(jù)共享實(shí)現(xiàn)進(jìn)程通信存儲(chǔ)保護(hù)防止地址越界防止操作越權(quán)擴(kuò)充內(nèi)存

3、容量 用戶在編制程序時(shí)，不應(yīng)該受內(nèi)存容量限制，所以要采用一定技術(shù)來(lái)“擴(kuò)充”內(nèi)存的容量，使用戶得到比實(shí)際內(nèi)存容量大的多的內(nèi)存空間，通過(guò)虛擬存儲(chǔ)技術(shù)實(shí)現(xiàn)地址映射（重定位）,存儲(chǔ)器管理的功能：,存儲(chǔ)系統(tǒng)設(shè)計(jì)三個(gè)問(wèn)題： 容量、速度和成本容量：需求無(wú)止境速度：能匹配處理器的速度成本問(wèn)題：成本和其它部件相比應(yīng)在合適范圍之內(nèi),解決方案：采用層次化的存儲(chǔ)體系結(jié)構(gòu)當(dāng)沿著層次下降時(shí)每比特的價(jià)格將下降，容量將增大速度將變

4、慢，處理器的訪問(wèn)頻率也將下降,4.1 存儲(chǔ)器的層次結(jié)構(gòu),4.1.1 多級(jí)存儲(chǔ)器結(jié)構(gòu),容量愈來(lái)愈大訪問(wèn)數(shù)據(jù)的速度愈來(lái)愈慢價(jià)格愈來(lái)愈便宜,,,提高存儲(chǔ)系統(tǒng)效能關(guān)鍵點(diǎn)：程序存儲(chǔ)訪問(wèn)局部性原理程序執(zhí)行時(shí)，有很多的循環(huán)和子程序調(diào)用，一旦進(jìn) 入這樣的程序段，就會(huì)重復(fù)存取相同的指令集合對(duì)數(shù)據(jù)存取也有局部性，在較短的時(shí)間內(nèi)，穩(wěn)定地 保持在一個(gè)存儲(chǔ)器的局部區(qū)域,處理器主要和存儲(chǔ)器 的局部打交道,在經(jīng)過(guò)一段時(shí)間以后，使

5、用的代碼和 數(shù)據(jù)集合會(huì)改變,設(shè)計(jì)多級(jí)存儲(chǔ)的體系結(jié)構(gòu),原則：訪問(wèn)級(jí)別較低存儲(chǔ)器比率小于級(jí)別較高存儲(chǔ) 器比率例：假設(shè)兩級(jí)存儲(chǔ)器：第I級(jí)包含1KB，存取時(shí)間為0.1μs第II級(jí)包含1MB，存取時(shí)間為1μs存取I級(jí)中的內(nèi)容，直接存取存取II級(jí)，首先被轉(zhuǎn)移到I級(jí)，然后再存取假設(shè)確定內(nèi)容所在位置時(shí)間可以忽略若在I級(jí)存儲(chǔ)器中發(fā)現(xiàn)存取對(duì)象的概率是95%，則平均訪問(wèn)時(shí)間為：結(jié)果非常接近I級(jí)存儲(chǔ)的存取時(shí)間,

6、存儲(chǔ)保護(hù)設(shè)施,對(duì)主存中的信息加以嚴(yán)格的保護(hù)，使操作系統(tǒng)及其它程序不被破壞，是其正確運(yùn)行的基本條件之一. 問(wèn)題：多個(gè)程序同時(shí)在同一臺(tái)機(jī)器上運(yùn)行怎樣才能互 不侵犯？,為了保證軟件程序只影響程序的內(nèi)部 硬件可提供如下功能：界地址寄存器（界限寄存器）存儲(chǔ)鍵,1.界地址寄存器（界限寄存器）,在CPU中設(shè)置一對(duì)界限寄存器來(lái)存放該用戶作業(yè)在主存中的下限和上限地址每當(dāng)CPU要訪問(wèn)主存，硬件自動(dòng)將被訪問(wèn)

7、的主存地址與界限寄存器的內(nèi)容進(jìn)行比較，以判斷是否越界如果未越界，則按此地址訪問(wèn)主存，否則將產(chǎn)生程序中斷——越界中斷（存儲(chǔ)保護(hù)中斷）,2.存儲(chǔ)鍵,每個(gè)存儲(chǔ)塊有一個(gè)由二進(jìn)位組成的存儲(chǔ)保護(hù)鍵一用戶作業(yè)被允許進(jìn)入主存，OS分給它一個(gè)唯一的存儲(chǔ)鍵號(hào)并將分配給該作業(yè)各存儲(chǔ)塊存儲(chǔ)鍵也置成同樣鍵號(hào)當(dāng)OS挑選該作業(yè)運(yùn)行時(shí)，OS將它的存儲(chǔ)鍵號(hào)放入程序狀態(tài)字PSW存儲(chǔ)鍵（“鑰匙”）域中每當(dāng)CPU訪問(wèn)主存時(shí)，都將該主存塊的存儲(chǔ)鍵與PSW中的“鑰匙”進(jìn)

8、行比較,,,,……,……,0010,0,7,鑰Key,11,只要鍵匹配，存取均可鍵不匹配，則不可存是否可取要看保護(hù)位,舉例：,? 存A，取A，均可以 (鍵Key匹配)? 存B，取B，均不可以 (鍵不匹配，且取保護(hù))? 存C，不可以 (鍵不匹配)取C，可以，因取保護(hù)位為0，即不保護(hù)取,程序狀態(tài)字,4.1 程序的裝入和鏈接,在多道程序環(huán)境下，要使程序運(yùn)行，必須創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程第一件事就是將程序和數(shù)據(jù)裝入內(nèi)存。

9、 一個(gè)用戶源程序要變?yōu)樵趦?nèi)存中可執(zhí)行的程序，通常要進(jìn)行以下處理：（1）編譯：由編譯程序?qū)⒂脩粼闯绦蚓幾g成若干個(gè)目標(biāo)模塊；（2）鏈接：由鏈接程序?qū)⒛繕?biāo)模塊和相應(yīng)的庫(kù)函數(shù)鏈接成裝入模塊；（3）裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存。,1. 絕對(duì)裝入方式,如果在編譯時(shí)，事先知用戶程序在內(nèi)存的駐留位置，則編譯程序在編譯時(shí)就產(chǎn)生絕對(duì)地址的目標(biāo)代碼。裝入程序就直接把裝入模塊中的程序和數(shù)據(jù)裝入到指定的位置，（不需進(jìn)行地址轉(zhuǎn)換）。 程序

10、中所使用的絕對(duì)地址，既可在編譯或匯編時(shí)給出， 也可由程序員直接賦予。 但在由程序員直接給出絕對(duì)地址時(shí)， 不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號(hào)地址，然后在編譯或匯編時(shí)，再將這些符號(hào)地址轉(zhuǎn)換為絕對(duì)地址。,4.2.1 程序的裝入,1.名空間、地址空間和存儲(chǔ)空間,在我們用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫程序時(shí)，總是通過(guò)符號(hào)名來(lái)訪問(wèn)某一單元。我們把程序中由符號(hào)名組成的空

11、間稱為名空間。源程序經(jīng)過(guò)匯編或編譯形成的程序，通常是以0為基址進(jìn)行順序編址，這樣的地址表示形式稱為相對(duì)地址,也叫做邏輯地址或虛地址，把該程序邏輯地址組成的集合叫做程序的邏輯地址空間(簡(jiǎn)稱地址空間)。存儲(chǔ)器中每個(gè)具體存儲(chǔ)單元都有不同的編號(hào)，每個(gè)編號(hào)就是一個(gè)物理地址，整個(gè)程序在內(nèi)存中存儲(chǔ)后所占用的物理地址的集合形成程序的物理地址空間(簡(jiǎn)稱存儲(chǔ)空間)。,2. 重定位（地址映射）裝入方式,名空間、地址空間和存儲(chǔ)空間的關(guān)系,,2.地址映射,邏

12、輯地址是一個(gè)“虛”的概念，處理機(jī)不能直接訪問(wèn)邏輯地址，而物理地址則是“實(shí)”的。因而，操作系統(tǒng)必須提供這樣的功能，把程序執(zhí)行時(shí)要訪問(wèn)的地址空間中的邏輯地址變換成內(nèi)存空間中對(duì)應(yīng)的物理地址。這種把虛地址變換成實(shí)地址的過(guò)程稱作地址映射。若用A表示地址空間，用M表示內(nèi)存空間，則地址映射可表示成：f：Ａ→Ｍ,(1)靜態(tài)映射：當(dāng)用戶程序被裝入內(nèi)存時(shí)，一次性實(shí)現(xiàn)邏 輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換。由重定位 裝入程序完成，它把

13、分配給目標(biāo)程序的內(nèi)存區(qū)的起始 地址B作為基地址，在把該程序裝入指定內(nèi)存區(qū)的同時(shí)， 將程序中的所有邏輯地址翻譯成相對(duì)于基地址B的物理 地址，即ｆ（ａ）＝Ｂ＋ａ,優(yōu)點(diǎn):容易實(shí)現(xiàn)，無(wú)需硬件支持，地址重定位由專門設(shè)計(jì)的 程序來(lái)完成。在早期的操作系統(tǒng)中大多數(shù)都采用這種 方法。缺點(diǎn):程序經(jīng)地址重定位后就不能移動(dòng)了，因而不能重新分 配內(nèi)存，不利于內(nèi)存的有效利用

14、。,0： B=10000 100： LOAD 1，2500 10100： LOAD 1，12500 2500： 365 12500： 365 2600： 12600： 邏輯地址空間

15、 物理地址空間,例如：LOAD 1，2500 這條指令是把相對(duì)地址為2500的存儲(chǔ)單元的內(nèi)容365裝入1號(hào)累加器。而這時(shí)內(nèi)容為365的存儲(chǔ)單元的實(shí)際物理地址為12500（起始地址10000+相對(duì)地址2500），所以LOAD 1，2500 這條指令中的直接地址碼要作相應(yīng)的修改，即改為L(zhǎng)OAD 1，12500。,(2)動(dòng)態(tài)映射：指在程序執(zhí)行過(guò)程中進(jìn)行地址重定位，即在每次訪問(wèn)內(nèi)存單元前才進(jìn)行地址變換。動(dòng)態(tài)重定位可使程序不加任

16、何修改就裝入內(nèi)存，但是它需要硬件—重定位寄存器的支持。對(duì)每一個(gè)有效地址都要加上重定位寄存器中的內(nèi)容，以形成絕對(duì)地址。,優(yōu)點(diǎn):程序在內(nèi)存中的搬移不會(huì)對(duì)程序的正確執(zhí)行造成影響， 使內(nèi)存得以被充分利用。缺點(diǎn):需要附加的硬件支持，實(shí)現(xiàn)存儲(chǔ)管理的軟件算法比較 復(fù)雜。,4.2.2 程序的鏈接,一種事先鏈接方式，即在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫(kù)函數(shù)，鏈接成一個(gè)完整的裝入模塊(執(zhí)行文件)，以后不再拆開(kāi)。實(shí)現(xiàn)靜態(tài)鏈接應(yīng)

17、解決:1）相對(duì)地址的修改2）變換外部調(diào)用符號(hào)存在問(wèn)題：1）不便于對(duì)目標(biāo)模塊 的修改和更新。2）無(wú)法實(shí)現(xiàn)對(duì)目標(biāo)模 塊的共享。,1. 靜態(tài)鏈接方式,指將一組目標(biāo)模塊在裝入內(nèi)存時(shí)，邊裝入邊鏈接的方式。具有便于修改和更新、便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。存在問(wèn)題： 由于程序運(yùn)行所有可能用的目標(biāo)模塊在裝入時(shí)均全部鏈接在一起，所以將會(huì)把一些不會(huì)運(yùn)行的目標(biāo)模塊也鏈接進(jìn)去。如程序中的錯(cuò)誤處理模塊。,2.

18、 裝入時(shí)動(dòng)態(tài)鏈接方式,在程序運(yùn)行中需要某些目標(biāo)模塊時(shí)，才對(duì)它們進(jìn)行鏈接的方式。具有高效且節(jié)省內(nèi)存空間的優(yōu)點(diǎn)。,3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接方式,單一用戶(連續(xù))分配是一種簡(jiǎn)單的存儲(chǔ)分配方案，主要用于單用戶單任務(wù)操作系統(tǒng)。它的實(shí)現(xiàn)方案如下： (1) 內(nèi)存分配：整個(gè)內(nèi)存劃分為系統(tǒng)區(qū)和用戶區(qū)。系統(tǒng)區(qū) 是操作系統(tǒng)專用區(qū)，不允許用戶程序直接訪問(wèn)，一道 用戶程序獨(dú)占用戶區(qū).,4.3.1 單一用戶存儲(chǔ)管理方案,注意: 我們所

19、涉及的內(nèi)存分配 與回收一般都指用戶區(qū) 的分配與回收。,,進(jìn)程,1,,,OS,,系統(tǒng)區(qū),,用戶區(qū),4.3 連續(xù)分配方式,(3) 內(nèi)存保護(hù)：通過(guò)基址寄存器保證用戶程序不會(huì)從系統(tǒng)區(qū) 開(kāi)始；另外系統(tǒng)需要一個(gè)界限寄存器，里邊存儲(chǔ)程序邏 輯地址范圍，若需要進(jìn)行映射的邏輯地址超過(guò)了界限寄 存器中的值，則產(chǎn)生一個(gè)越界中

20、斷信號(hào)。,(2) 地址映射：物理地址=用戶區(qū)基地址+邏輯地址。,單一連續(xù)分配方案的優(yōu)點(diǎn)是方法簡(jiǎn)單，易于實(shí)現(xiàn)；缺點(diǎn)是它僅適用于單道程序，因而不能使處理機(jī)和內(nèi)存得到充分利用。,例：,一個(gè)容量為256KB的內(nèi)存，操作系統(tǒng)占用32KB，剩下224KB全部分配給用戶作業(yè)，如果一個(gè)作業(yè)僅需64KB，那么就有160KB的存儲(chǔ)空間被浪費(fèi)。,0KB32KB96KB256KB-1,,分配給用戶的空間,4.3.2 固定分區(qū)分配,作業(yè)裝入之前

21、，內(nèi)存就被劃分成若干個(gè)分區(qū)。劃分工作可以由系統(tǒng)管理員完成或由操作系統(tǒng)實(shí)現(xiàn)。一旦劃分完成，在系統(tǒng)運(yùn)行期間不再重新劃分，即分區(qū)的個(gè)數(shù)不可變，分區(qū)的大小不可變，且每個(gè)分區(qū)裝一個(gè)且只能裝一個(gè)作業(yè)?？蓪?nèi)存的用戶區(qū)域劃分成大小相等或不等的分區(qū)。分區(qū)大小相等：只適合于多個(gè)相同程序的并發(fā)執(zhí)行（處理多個(gè)類型相同的對(duì)象）。分區(qū)大小不等：多個(gè)小分區(qū)、適量的中等分區(qū)、少量的大分區(qū)。根據(jù)程序的大小，分配當(dāng)前空閑的、適當(dāng)大小的分區(qū)。系統(tǒng)有一張分區(qū)說(shuō)明

22、表，每個(gè)表目說(shuō)明一個(gè)分區(qū)的大小、起始地址和是否已分配的使用標(biāo)志。,固定分區(qū)示例,例：在某系統(tǒng)中，采用固定分區(qū)分配管理方式，內(nèi)存分區(qū)（單位字節(jié)）情況如圖所示，現(xiàn)有大小為1K、9K、33K、121K的多個(gè)作業(yè)要求進(jìn)入內(nèi)存，試畫出它們進(jìn)入內(nèi)存后的空間分配情況，并說(shuō)明主存浪費(fèi)多大？,分區(qū)說(shuō)明表,（2）分區(qū)說(shuō)明表,(3)主存浪費(fèi)空間=(8-1)+(32-9)+(120-33)+(331-121) =7+23+87+2

23、10=327(k),解：根據(jù)分區(qū)說(shuō)明表，將4個(gè)分區(qū)依次分配給4個(gè)作業(yè)，同時(shí)修改分區(qū)說(shuō)明表，其內(nèi)存分配和分區(qū)說(shuō)明表如下所示：,4.3.3 動(dòng)態(tài)（可變）分區(qū)分配,作業(yè)裝入內(nèi)存時(shí)，從可用的內(nèi)存中劃出一塊連續(xù)的區(qū)域分配給它，且分區(qū)大小正好等于該作業(yè)的大小?？勺兪椒謪^(qū)中分區(qū)的大小和分區(qū)的個(gè)數(shù)都是可變的，而且是根據(jù)作業(yè)的大小和多少動(dòng)態(tài)地劃分。在分配時(shí)，首先找到一個(gè)足夠大的空閑分區(qū)，即這個(gè)空閑區(qū)的大小比作業(yè)要求的要大，系統(tǒng)則將這個(gè)空閑分區(qū)分成兩部

24、分：一部分成為已分配的分區(qū)，剩余的部分仍作為空閑區(qū)。在回收撤除作業(yè)所占領(lǐng)的分區(qū)時(shí)，要檢查回收的分區(qū)是否與前后空閑的分區(qū)相領(lǐng)接，若是，則加以合并，使之成為一個(gè)連續(xù)的大空間。常用的數(shù)據(jù)結(jié)構(gòu)有內(nèi)存分配表（由已分配區(qū)表和空閑區(qū)表組成）和空閑分區(qū)鏈兩種。,,,,,,,,,0K,15K,38K,48K,68K,80K,110K,120K,空閑區(qū)表,已分配區(qū)表,J1,J2,J3,J4,,,,,,,,,0K,15K,38K,48K,68K,80K,

25、110K,120K,空閑區(qū)表,已分配區(qū)表,,85K,,98K,J1,J2,J3,J4,J5,J6,可變分區(qū)示例,2. 分區(qū)分配算法,為了將一個(gè)作業(yè)裝入內(nèi)存，應(yīng)按照一定的分配算法從空閑分區(qū)表（鏈）中選 出一個(gè)滿足作業(yè)需求的分區(qū)分配給作業(yè)，如果這個(gè)空閑分區(qū)的容量比作業(yè)申請(qǐng)的空間要大，則將該分區(qū)一分為二，一部分分配給作業(yè)，剩下的部分仍然留在空閑分區(qū)表（鏈）中，同時(shí)修改空閑分區(qū)表（鏈）中相應(yīng)的信息。目前常用分配算法有：首次適應(yīng)算法循環(huán)首次適

26、應(yīng)算法最佳適應(yīng)算法最壞適應(yīng)算法快速適應(yīng)法,首次適應(yīng)算法（最先適應(yīng)算法）,算法 空閑分區(qū)（鏈）按地址遞增的次序排列。在進(jìn)行內(nèi)存分配時(shí),從空閑分區(qū)表/鏈?zhǔn)组_(kāi)始順序查找,直到找到第一個(gè)滿足其大小要求的空閑分區(qū)為止。然后再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑分區(qū)表（鏈）中。,空閑分區(qū)表,解：按首次適應(yīng)算法， 申請(qǐng)作業(yè)100k，分配3號(hào)分區(qū)，剩下分區(qū)為20k，起始地址160

27、K ； 申請(qǐng)作業(yè)30k，分配1號(hào)分區(qū)，剩下分區(qū)為2k，起始地址50K ； 申請(qǐng)作業(yè)7k，分配2號(hào)分區(qū)，剩下分區(qū)為1k，起始地址59K ； 其內(nèi)存分配圖及分配后空閑分區(qū)表如下：,例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及7K。給出按首次適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。,(2)該算法分配后的空閑分區(qū)表,,,首次適應(yīng)算法的特點(diǎn) 優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū),從

28、而保留了高地址部分的大空閑區(qū)。但由于低地址部分不斷被劃分,致使低地址端留下許多難以利用的很小的空閑分區(qū)(碎片或零頭),而每次查找又都是從低地址部分開(kāi)始,這無(wú)疑增加了查找可用空閑分區(qū)的開(kāi)銷。,循環(huán)首次適應(yīng)算法,算法要求 又稱為下次適應(yīng)算法，由首次適應(yīng)算法演變而來(lái)。在為作業(yè)分配內(nèi)存空間時(shí),不再每次從空閑分區(qū)表/鏈?zhǔn)组_(kāi)始查找,而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找,直到找到第一個(gè)能滿足其大小要求的空閑分區(qū)為止

29、。然后，再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑分區(qū)表/鏈中。,空閑分區(qū)表,解：按循環(huán)首次適應(yīng)算法，申請(qǐng)作業(yè)100k，分配3號(hào)分區(qū)，剩下分區(qū)為20k,起始地址160K； 申請(qǐng)作業(yè)30k，分配4號(hào)分區(qū)，剩下分區(qū)為301k，起始地址210K ；申請(qǐng)作業(yè)7k，分配1號(hào)分區(qū)，剩下分區(qū)為25k，起始地址27K ；其內(nèi)存分配圖及分配后空閑分區(qū)表如下:,例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配

30、申請(qǐng)內(nèi)存空間100K、30K及7K。給出按循環(huán)首次適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。,(2)該算法分配后的空閑分區(qū)表,算法特點(diǎn) 使存儲(chǔ)空間的利用更加均衡，不致使小的空閑區(qū)集中在存儲(chǔ)區(qū)的一端，但這會(huì)導(dǎo)致缺乏大的空閑分區(qū)。,最佳適應(yīng)算法,算法要求： 總是把滿足要求的、又是最小的空閑分區(qū)分給作業(yè)。為了加速尋找，空閑分區(qū)表/鏈按容量大小遞增的次序排列。在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表/鏈的首開(kāi)始順序

31、查找，直到找到第一個(gè)滿足其大小要求的空閑分區(qū)為止。 按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。如果該空閑分區(qū)大于作業(yè)的大小，則與首次適應(yīng)算法相同，將剩余空閑分區(qū)仍留在空閑分區(qū)表/鏈中。,例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及7K。給出按最佳適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。,分配前的空閑分區(qū)表,內(nèi)存分區(qū),解：按最佳適應(yīng)算法，分配前的空

32、閑分區(qū)表如上表。 申請(qǐng)作業(yè)100k，分配3號(hào)分區(qū)，剩下分區(qū)為20k,起始地址160K； 申請(qǐng)作業(yè)30k， 分配2號(hào)分區(qū)，剩下分區(qū)為2k，起始地址50K ； 申請(qǐng)作業(yè)7k， 分配1號(hào)分區(qū)，剩下分區(qū)為1k，起始地址59K ；其內(nèi)存分配圖及分配后空閑分區(qū)表如下：,作業(yè)100K分配后的空閑分區(qū)表,作業(yè)30K分配后的空閑分區(qū)表,作業(yè)7K分配后的空閑分區(qū)表,(2)該算法分配后的空閑分區(qū)表,,,算法特點(diǎn)

33、 若存在與作業(yè)大小一致的空閑分區(qū),則它必然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)，則只劃分比作業(yè)稍大的空閑分區(qū)，,從而保留了大的空閑分區(qū),但空閑區(qū)一般不可能正好和它申請(qǐng)的內(nèi)存空間大小一樣,因而將其分割成兩部分時(shí),往往使剩下的空閑區(qū)非常小,從而在存儲(chǔ)器中留下許多難以利用的小空閑區(qū)（碎片或零頭）。,最壞適應(yīng)算法,算法要求 總是挑選一個(gè)最大的空閑區(qū)分割給作業(yè)使用，空閑分區(qū)表/鏈按容量大小遞減的次序排列。在進(jìn)行內(nèi)存分配時(shí)，從空閑分

34、區(qū)表/鏈的首開(kāi)始順序查找，直到找到第一個(gè)比之大的空閑分區(qū)為止。剩下的空閑仍留在空閑分區(qū)表/鏈中。,空閑分區(qū)表,例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及7K。給出按最壞適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。,作業(yè)100K分配后的空閑分區(qū)表,作業(yè)30K分配后的空閑分區(qū)表,作業(yè)7K分配后的空閑分區(qū)表,解：按最壞適應(yīng)算法，分配前的空閑分區(qū)表如上表。 申請(qǐng)作業(yè)100k，分配1號(hào)分區(qū)，剩下分區(qū)為231k

35、,起始地址280K； 申請(qǐng)作業(yè)30k，分配1號(hào)分區(qū)，剩下分區(qū)為201k，起始地址310K ； 申請(qǐng)作業(yè)7k，分配1號(hào)分區(qū)，剩下分區(qū)為194k，起始地址317K ； 其內(nèi)存分配圖及分配后空閑分區(qū)表如下：,(2)該算法分配后的空閑分區(qū)表,,3,,,,0k 20k 52k 60k180k511k,(1)內(nèi)存分配圖,,,,,,,,20K52K60K280K310K317K,算法

36、特點(diǎn) 總是挑選滿足作業(yè)要求的最大的分區(qū)分配給作業(yè)。這樣使分給作業(yè)后剩下的空閑分區(qū)也較大，可裝下其它作業(yè)。但由于最大的空閑分區(qū)總是因首先分配而劃分，當(dāng)有大作業(yè)到來(lái)時(shí)，其存儲(chǔ)空間的申請(qǐng)往往會(huì)得不到滿足。,快速適應(yīng)算法（分類搜索法）,算法要求 將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，每一類相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立一張管理索引表，每一表項(xiàng)對(duì)應(yīng)了一種空閑分區(qū)類型，并記錄頭指針。進(jìn)程根據(jù)自己的

37、長(zhǎng)度，尋找能容納它的最小空閑區(qū)鏈表，取下第一塊進(jìn)行分配即可。,3. 分區(qū)分配操作_分配內(nèi)存和回收內(nèi)存,（1）分配內(nèi)存 系統(tǒng)利用某種分配算法，從空閑分區(qū)表/鏈中找到所需大小的分區(qū)。分區(qū)的切割： 設(shè)請(qǐng)求的分區(qū)大小為u.size，空閑分區(qū)的大小為m.size,若m.size-u.size?size(size是事先規(guī)定的不再切割的剩余分區(qū)的大小)，說(shuō)明多余部分大小，可不再切割，將整個(gè)分區(qū)分配給請(qǐng)求者；否則，從該分區(qū)中

38、按請(qǐng)求的大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)表/鏈中，然后，將分配區(qū)的首址返回給調(diào)用者。 分配流程圖如下：,（2）回收內(nèi)存,當(dāng)作業(yè)執(zhí)行結(jié)束時(shí)，應(yīng)回收已使用完畢的分區(qū)。系統(tǒng)根據(jù)回收分區(qū)的大小及首地址，在空閑分區(qū)表中檢查是否有鄰接的空閑分區(qū)，如有，則合成為一個(gè)大的空閑分區(qū)，然后修改有關(guān)的分區(qū)狀態(tài)信息?；厥辗謪^(qū)與已有空閑分區(qū)的相鄰情況有以下四種： 1）回收分區(qū)上鄰接一個(gè)空閑分區(qū),合并后首地址為空閑分區(qū)的首地址,大

39、小為二者之和。 2）回收分區(qū)下鄰接一個(gè)空閑分區(qū),合并后首地址為回收分區(qū)的首地址,大小為二者之和。 3）回收分區(qū)上下鄰接空閑分區(qū),合并后首地址為上空閑分區(qū)的首地址,大小為三者之和。 4）回收分區(qū)不鄰接空閑分區(qū)，這時(shí)在空閑分區(qū)表中新建一表項(xiàng)，并填寫分區(qū)大小等信息。,4.3.6 可重定位分區(qū)分配,1. 動(dòng)態(tài)重定位的引入 在分區(qū)存儲(chǔ)管理方式中，必須把作業(yè)裝入到一片連續(xù)的內(nèi)存空

40、間。如果系統(tǒng)中有若干個(gè)小的分區(qū)，其總?cè)萘看笥谝b入的作業(yè)，但由于它們不相鄰接，也將致使作業(yè)不能裝入內(nèi)存。 例 ：如圖所示系統(tǒng)中有四個(gè)小空閑分區(qū)，不相鄰，但總?cè)萘繛?0KB，如果現(xiàn)有一作業(yè)要求分配40KB的內(nèi)存空間，由于系統(tǒng)中所有空閑分區(qū)的容量均小于40KB，故此作業(yè)無(wú)法裝入內(nèi)存。 這種內(nèi)存中無(wú)法被利用的存儲(chǔ)空間稱為“零頭”或“碎片”。根據(jù)碎片出現(xiàn)的情況分為以下兩種：,系統(tǒng)中的碎片,內(nèi)部碎片,外部碎片,內(nèi)部碎片：

41、指分配給作業(yè)的存儲(chǔ)空間中未被利用的部分。如固定分區(qū)中存在的碎片。外部碎片：指系統(tǒng)中無(wú)法利用的小的空閑分區(qū)。 如動(dòng)態(tài)分區(qū)中存在的碎片。,碎片問(wèn)題的解決方法,拼接或緊湊或緊縮技術(shù) 將內(nèi)存中所有作業(yè)移到內(nèi)存一端（作業(yè)在內(nèi)存中的位置發(fā)生了變化，這就必須對(duì)其地址加以修改或變換即稱為重定位），使本來(lái)分散的多個(gè)小空閑分區(qū)連成一個(gè)大的空閑區(qū)。如圖所示。這種通過(guò)移動(dòng)作業(yè)從把多個(gè)分散的小分區(qū)拼接成一個(gè)大分區(qū)的

42、方法稱為拼接或緊湊或緊縮。 拼接時(shí)機(jī)：分區(qū)回收時(shí)；當(dāng)找不到足夠大的空閑分區(qū)且總空閑分區(qū)容量可以滿足作業(yè)要求時(shí)。,,2. 動(dòng)態(tài)重定位的實(shí)現(xiàn),動(dòng)態(tài)重定位可使程序不加任何修改就裝入內(nèi)存，但是它需要硬件—重定位寄存器的支持。對(duì)每一個(gè)有效地址都要加上重定位寄存器中的內(nèi)容，以形成絕對(duì)地址。,動(dòng)態(tài)重定位分區(qū)分配算法流程圖,3. 動(dòng)態(tài)重定位分區(qū)分配算法 在動(dòng)態(tài)分區(qū)分配算法中增加拼接功能，在找不到足夠大的空閑分區(qū)來(lái)滿足

43、作業(yè)要求，而系統(tǒng)中總空閑分區(qū)容量可以滿足作業(yè)要求時(shí)，進(jìn)行拼接。,可重定位分區(qū)分配方式主要特點(diǎn) 可以充分利用存儲(chǔ)區(qū)中的“零頭/碎片”，提高主存的利用率。 但若 “零頭/碎片”過(guò)多，則拼接頻率過(guò)高會(huì)使系統(tǒng)開(kāi)銷加大。,4.3.7 覆蓋技術(shù)與交換技術(shù),1.覆蓋技術(shù),引入：其目標(biāo)是在較小的可用內(nèi)存中運(yùn)行較大的程序。常用于多道程序系統(tǒng)，與分區(qū)存儲(chǔ)管理配合使用。原理：一個(gè)程序的幾個(gè)代碼段或數(shù)據(jù)段，按照時(shí)間先后來(lái)占用公共的內(nèi)存

44、空間。將程序的必要部分（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)存；可選部分（不常用功能）在其他程序模塊中實(shí)現(xiàn)，平時(shí)存放在外存中（覆蓋文件），在需要用到時(shí)才裝入到內(nèi)存；不存在調(diào)用關(guān)系的模塊不必同時(shí)裝入到內(nèi)存，從而可以相互覆蓋。(即不同時(shí)用的模塊可共用一個(gè)分區(qū))缺點(diǎn)：編程時(shí)必須劃分程序模塊和確定程序模塊之間的覆蓋關(guān)系，增加編程復(fù)雜度。從外存裝入覆蓋文件，以時(shí)間延長(zhǎng)來(lái)?yè)Q取空間節(jié)省。,A20K,D20K,E40K,,,,,,,,,,C

45、30K,B50K,F30K,作業(yè)X的調(diào)用結(jié)構(gòu),,,,,,作業(yè)X的常駐區(qū) A（20K）,覆蓋區(qū)0（50K）,覆蓋區(qū)1（40K）,,,,,,,,,,,B,C,D,E,F,注：另一種覆蓋方法：(100K)A(20K)占一個(gè)分區(qū)：20K；B(50K)、D(20K)和E(40K)共用一個(gè)分區(qū)：50K；F(30K)和C(30K)共用一個(gè)分區(qū)：30K；,Total:190K,Total:110K,2. 交換技術(shù),引入：多個(gè)程序并

46、發(fā)執(zhí)行，可以將暫時(shí)不能執(zhí)行的程序送到外存中，從而獲得空閑內(nèi)存空間來(lái)裝入新程序，或讀入保存在外存中而目前到達(dá)就緒狀態(tài)的進(jìn)程。交換單位為整個(gè)進(jìn)程的地址空間。常用于多道程序系統(tǒng)或小型分時(shí)系統(tǒng)中，與分區(qū)存儲(chǔ)管理配合使用。又稱作"對(duì)換"或"滾進(jìn)/滾出(roll-in/roll-out)"；程序暫時(shí)不能執(zhí)行的可能原因：處于阻塞狀態(tài)，低優(yōu)先級(jí)（確保高優(yōu)先級(jí)程序執(zhí)行）；原理：暫停執(zhí)行內(nèi)存中的進(jìn)程，將整個(gè)進(jìn)程的

47、地址空間保存到外存的交換區(qū)中（換出swap out），而將外存中由阻塞變?yōu)榫途w的進(jìn)程的地址空間讀入到內(nèi)存中，并將該進(jìn)程送到就緒隊(duì)列（換入swap in）。,返回,優(yōu)點(diǎn)：增加并發(fā)運(yùn)行的程序數(shù)目，并且給用戶提供適當(dāng)?shù)捻憫?yīng)時(shí)間；編寫程序時(shí)不影響程序結(jié)構(gòu)缺點(diǎn)：對(duì)換入和換出的控制增加處理機(jī)開(kāi)銷；程序整個(gè)地址空間都進(jìn)行傳送，沒(méi)有考慮執(zhí)行過(guò)程中地址訪問(wèn)的統(tǒng)計(jì)特性?？紤]的問(wèn)題：程序換入時(shí)的重定位；減少交換中傳送的信息量，特別是對(duì)大程序；對(duì)外存

48、交換區(qū)空間的管理：如動(dòng)態(tài)分區(qū)方法；,4.4 基本分頁(yè)存儲(chǔ)管理方式,我們把邏輯地址空間劃分為一些相等的片，這些片稱為頁(yè)或頁(yè)面。物理地址空間也被劃分為同樣大小的片，稱為塊。這樣用戶程序進(jìn)入內(nèi)存時(shí)，就可以一頁(yè)對(duì)應(yīng)存入到一個(gè)塊中。對(duì)整個(gè)程序來(lái)說(shuō)，只有可能在最后一塊存在碎片（稱為頁(yè)內(nèi)碎片），而且碎片大小不會(huì)超過(guò)一塊，所以內(nèi)存利用率可以大大提高。用戶程序的邏輯地址:,4.4.1 頁(yè)面與頁(yè)表,頁(yè)面(或塊)的大小由系統(tǒng)硬件地址結(jié)構(gòu)規(guī)定，通常是2

49、的冪，例如512B，1 KB、2 KB等。這樣的規(guī)定可以使地址映射容易實(shí)現(xiàn)。頁(yè)面不能過(guò)大，也不能過(guò)小。過(guò)小會(huì)造成頁(yè)面過(guò)多，增加了系統(tǒng)開(kāi)銷；過(guò)大又會(huì)造成頁(yè)內(nèi)碎片太大，內(nèi)存利用率不高。早期的頁(yè)面大小一般都在512 B～4 KB，隨著計(jì)算機(jī)性能的提高，現(xiàn)在一般在2 KB～8 KB，甚至有的系統(tǒng)支持多種頁(yè)面大小。,例：對(duì)于一個(gè)32位的地址結(jié)構(gòu)，如果頁(yè)面大小為4 KB，則頁(yè)內(nèi)地址由0～11這12位表示，剩余12～31在表示頁(yè)號(hào),（頁(yè)內(nèi)地址）,

50、例：在頁(yè)面大小為4 KB的系統(tǒng)中，若邏輯地址為28024，則 可求得頁(yè)號(hào)為6，頁(yè)內(nèi)偏移量為3448。 而計(jì)算機(jī)內(nèi)部如何得到頁(yè)號(hào)和頁(yè)內(nèi)地址呢？ 28024的二進(jìn)制用32位表示為： (0000 0000 0000 0000 0110 1101 0111 1000)2，因?yàn)轫?yè)面 大小為4 KB，則取低12位為頁(yè)內(nèi)地址，剩余高位是頁(yè)號(hào)。 把這兩部

51、分換算為十進(jìn)制，我們可以驗(yàn)算出通過(guò)上述公 式計(jì)算的結(jié)果的正確性。,系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)頁(yè)表，記錄了進(jìn)程每個(gè)頁(yè)號(hào)及其對(duì)應(yīng)的存儲(chǔ)塊號(hào)。整個(gè)系統(tǒng)一張存儲(chǔ)分塊表，記錄每個(gè)存儲(chǔ)塊及其狀態(tài)（已分配或空閑）。當(dāng)有一個(gè)進(jìn)程進(jìn)入系統(tǒng)時(shí)，為頁(yè)表分配一個(gè)存儲(chǔ)區(qū)，然后搜索存儲(chǔ)分塊表，查看有哪些存儲(chǔ)塊是空閑的，如有空閑的存儲(chǔ)塊，則將存儲(chǔ)塊號(hào)填入頁(yè)表。當(dāng)該進(jìn)程所需的塊數(shù)都分配完后，系統(tǒng)便可按照頁(yè)表的內(nèi)容對(duì)該進(jìn)程進(jìn)行處理。當(dāng)某個(gè)進(jìn)程因?yàn)榻Y(jié)束或

52、者其它一些原因退出系統(tǒng)，則歸還原來(lái)所占用的物理塊。首先修改存儲(chǔ)分塊表，將歸還的物理塊塊號(hào)在表中的狀態(tài)欄改為空閑標(biāo)志，然后釋放該進(jìn)程頁(yè)表所占用的空間。,管理上的考慮,頁(yè)表、存儲(chǔ)分塊表及其關(guān)系,,頁(yè)號(hào),,0,,1,,2,,,塊號(hào),,10,,3,,92,,0號(hào)頁(yè)表,1號(hào)頁(yè)表,,頁(yè)號(hào),,0,,1,,塊號(hào),,9,,53,,,…,,塊號(hào),,0,,…,,狀態(tài),,0,,…,,3,,1,,…,,…,,9,,1,,10,,1,,…,,…,存儲(chǔ)分塊表,,,,

53、,,,由于頁(yè)和塊大小是一致的，每頁(yè)的頁(yè)內(nèi)地址與物理塊的塊內(nèi)單元地址也完全一致，所以在邏輯地址到物理地址的映射中，主要從一個(gè)頁(yè)找到對(duì)應(yīng)的內(nèi)存塊，而這種頁(yè)與塊的對(duì)應(yīng)關(guān)系是頁(yè)表記錄的。每個(gè)進(jìn)程調(diào)度時(shí)，從該進(jìn)程PCB中取得頁(yè)表始址和頁(yè)表長(zhǎng)度（頁(yè)表長(zhǎng)度指頁(yè)表的項(xiàng)數(shù)），裝入到系統(tǒng)中設(shè)置的頁(yè)表寄存器內(nèi)。,4.4.2 地址變換機(jī)構(gòu),1．動(dòng)態(tài)地址映射機(jī)構(gòu),分頁(yè)式地址變換過(guò)程,例：頁(yè)大小為1024 B，給定邏輯地址3795，即得出頁(yè)號(hào)為3，頁(yè)內(nèi)地址為

54、723。,① 頁(yè)號(hào)3與頁(yè)表寄存器中的頁(yè)表長(zhǎng)度比較判斷是否越界，如果越界，則轉(zhuǎn)錯(cuò)誤中斷處理，否則轉(zhuǎn)②；② 頁(yè)表中該項(xiàng)在內(nèi)存中的對(duì)應(yīng)地址=頁(yè)表始地址R+頁(yè)號(hào)3×頁(yè)表項(xiàng)長(zhǎng)度i，訪問(wèn)該地址R+3i，得到物理塊號(hào)11；③ 11(頁(yè)號(hào))×1024(頁(yè)大小)+723(頁(yè)內(nèi)地址) = 11987(物理地址)；④ 訪問(wèn)內(nèi)存11987單元，得到需要的數(shù)據(jù)365。,頁(yè)表存放在內(nèi)存中，每條指令都必須兩次訪問(wèn)內(nèi)存儲(chǔ)器，增加了指令執(zhí)行的機(jī)

55、器時(shí)間，影響了計(jì)算機(jī)的速度。一次是訪問(wèn)頁(yè)表，由頁(yè)號(hào)找到對(duì)應(yīng)的物理塊號(hào)；另一次是在物理地址中實(shí)際存取所要的數(shù)據(jù)或指令。為了加快查表速度，在地址映射機(jī)構(gòu)中加入一組高速寄存器(8個(gè)或16個(gè))，構(gòu)成了一個(gè)容量較小的存儲(chǔ)器，稱之為聯(lián)想存儲(chǔ)器（也稱快表）。在聯(lián)想存儲(chǔ)器中，存放正在運(yùn)行進(jìn)程的當(dāng)前最常用的頁(yè)號(hào)和相應(yīng)塊號(hào)，這個(gè)聯(lián)想存儲(chǔ)器具有并行查詢能力，使地址轉(zhuǎn)換時(shí)間大大下降。,2. 快表的引入(聯(lián)想存儲(chǔ)器),引入快表的地址映射,由于對(duì)程序和數(shù)據(jù)

56、的訪問(wèn)往往帶有局限性，所以快表的命中率可以達(dá)到90%左右。,例:假設(shè)檢索聯(lián)想存儲(chǔ)器的時(shí)間為20ns，訪問(wèn)內(nèi)存的時(shí)間 為100ns，訪問(wèn)聯(lián)想存儲(chǔ)器的的命中率為85%，則CPU 存取一個(gè)數(shù)據(jù)的平均時(shí)間為 T=0.85*120+0.15*200=132ns， 如果不引入聯(lián)想存儲(chǔ)器，訪問(wèn)2次主存，將達(dá)200ns。,問(wèn)題 若邏輯地址空間很大，則劃分的頁(yè)就很多，頁(yè)表就很大，其占用的存儲(chǔ)空間（

57、要求連續(xù)）就大，實(shí)現(xiàn)較難。解決問(wèn)題的方法 1、只將當(dāng)前需用的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存，其余的需用時(shí)再調(diào)入。 2、多級(jí)頁(yè)表二級(jí)頁(yè)表 (1)將頁(yè)表再進(jìn)行分頁(yè)，并離散地將各個(gè)頁(yè)表頁(yè)面存放在不同的物理塊中，同時(shí)也再建立一張頁(yè)表（外層頁(yè)表）用以記錄頁(yè)表頁(yè)面對(duì)應(yīng)的物理塊號(hào)。,4.4.3 多級(jí)頁(yè)表,兩級(jí)頁(yè)表結(jié)構(gòu),(2)邏輯地址：(3)地址轉(zhuǎn)換,多級(jí)頁(yè)表 將外層頁(yè)表再進(jìn)行分頁(yè)，也將各

58、外層頁(yè)表頁(yè)面離散地存放在不同的物理塊中，再利用第2級(jí)的外層頁(yè)表來(lái)記錄它們之間的對(duì)應(yīng)的關(guān)系。 邏輯地址：,便于多道程序設(shè)計(jì)，提高了內(nèi)存的利用率，而不必像動(dòng)態(tài)分區(qū)分配那樣執(zhí)行緊湊操作。,分頁(yè)存儲(chǔ)管理的優(yōu)缺點(diǎn),優(yōu)點(diǎn)：,采用動(dòng)態(tài)地址映射會(huì)增加計(jì)算機(jī)成本和降低處理機(jī)的速度。各種表格要占用一定容量的內(nèi)存空間，而且還要花費(fèi)一部分處理機(jī)時(shí)間來(lái)建立和管理這些表格。雖然消除了大量碎片，但每個(gè)作業(yè)的最后一頁(yè)一般都有不能充分利用的空白區(qū)存儲(chǔ)

59、擴(kuò)充問(wèn)題仍未得到解決。當(dāng)沒(méi)有足夠空間能裝下整個(gè)作業(yè)地址空間時(shí)，該作業(yè)還是無(wú)法運(yùn)行。,缺點(diǎn)：,1．把作業(yè)地址空間中使用的邏輯地址變成內(nèi)存中物理地址 稱為（ ）。A. 加載 B. 重定位 C. 物理化 D. 邏輯化,3．在內(nèi)存分配的“最佳適應(yīng)法”中，空閑塊是按（ ）。A.始地址從小到大排序 B.始地址從大到小排序C

60、.塊的大小從小到大排序 D.塊的大小從大到小排序,4．分區(qū)管理和分頁(yè)管理的主要區(qū)別是（ ）。A.分區(qū)管理中的塊比分頁(yè)管理中的頁(yè)要小B.分頁(yè)管理有地址映射而分區(qū)管理沒(méi)有C.分頁(yè)管理有存儲(chǔ)保護(hù)而分區(qū)管理沒(méi)有D.分區(qū)管理要求一道程序存放在連續(xù)的空間內(nèi)而分頁(yè)管理 沒(méi)有這種要求。,2．在可變分區(qū)存儲(chǔ)管理中的緊湊技術(shù)可以( )。A. 集中空閑區(qū)

61、 B. 增加主存容量C. 縮短訪問(wèn)時(shí)間 D. 加速地址轉(zhuǎn)換,B,A,C,D,5．設(shè)內(nèi)存的分配情況如下圖所示。若要申請(qǐng)一塊40K 字節(jié)的內(nèi)存空間，若采用最佳適應(yīng)算法，則所得到 的分區(qū)首址為（ ）。A. 100K B. 190K C. 330K D. 410K

62、,C,一個(gè)用戶作業(yè)的程序按其邏輯結(jié)構(gòu)可劃分為若干段，例如主程序段、子程序段、數(shù)據(jù)段、堆棧段等。這些段中的每一段在邏輯上都是完整的，因此每一段都是一組邏輯信息，有自己的名字，且都有一段連續(xù)的地址空間。在分段式存儲(chǔ)管理中，段名用段號(hào)代替，段地址從0開(kāi)始編址，因?yàn)楦鞫蔚倪壿嬓畔?nèi)容不同，所以段長(zhǎng)度不同。這樣用段號(hào)和段內(nèi)地址構(gòu)成用戶程序的邏輯地址。當(dāng)一個(gè)用戶程序裝入內(nèi)存時(shí)，系統(tǒng)為每個(gè)段分配一個(gè)連續(xù)的內(nèi)存區(qū)域，而各個(gè)段之間可以離散存放。,4

63、.5.2 分段系統(tǒng)的基本原理,4.5 基本分段存儲(chǔ)管理方式,地址映射機(jī)構(gòu),段 表,分段式地址變換過(guò)程,例：給定邏輯地址中段號(hào)為3，段內(nèi)地址為723,分頁(yè)和分段的主要區(qū)別,分頁(yè)是出于系統(tǒng)管理的需要，分段是出于用戶應(yīng)用的需要。一條指令或一個(gè)操作數(shù)可能會(huì)跨越兩個(gè)頁(yè)的分界處，而不會(huì)跨越兩個(gè)段的分界處。頁(yè)大小是系統(tǒng)固定的，而段大小則通常不固定。邏輯地址表示：分頁(yè)是一維的，各個(gè)模塊在鏈接時(shí)必須組織成同一個(gè)地址空間；分段是二維的，各個(gè)

64、模塊在鏈接時(shí)可以每個(gè)段組織成一個(gè)地址空間。通常段比頁(yè)大，因而段表比頁(yè)表短，可以縮短查找時(shí)間，提高訪問(wèn)速度。,返回,4.5.3 信息共享,分頁(yè)系統(tǒng)中共享editor的示意圖,例:一個(gè)多用戶系統(tǒng)可同時(shí)容納40個(gè)用戶，都執(zhí)行一個(gè)文本編輯程序（160KB代碼和40KB數(shù)據(jù)區(qū)），代碼是可重入的假定頁(yè)面大小為4KB。,分段系統(tǒng)中共享editor的示意圖,,方便了用戶編程。多個(gè)邏輯段形成作業(yè)這種組織方式，使用戶可以清晰地設(shè)計(jì)和了解程序的結(jié)構(gòu)。便

65、于實(shí)現(xiàn)程序和數(shù)據(jù)的共享與保護(hù)。程序的動(dòng)態(tài)鏈接實(shí)現(xiàn)方便。通常一個(gè)源程序經(jīng)過(guò)編譯后所形成的若干個(gè)目標(biāo)程序，還需再經(jīng)過(guò)鏈接，形成可執(zhí)行代碼后才能運(yùn)行，這種在裝入時(shí)進(jìn)行的鏈接稱為靜態(tài)鏈接。動(dòng)態(tài)鏈接是指在作業(yè)運(yùn)行之前，并不把幾個(gè)目標(biāo)程序段都鏈接起來(lái)，而是先將主程序?qū)?yīng)的目標(biāo)程序裝入內(nèi)存并啟動(dòng)運(yùn)行，當(dāng)運(yùn)行過(guò)程中又需要調(diào)用某段時(shí)，再將該段（目標(biāo)程序）調(diào)入內(nèi)存并鏈接起來(lái)。所以，動(dòng)態(tài)鏈接是以段為基礎(chǔ)的。應(yīng)用中會(huì)發(fā)生數(shù)據(jù)動(dòng)態(tài)增長(zhǎng)的情況，而且這種增長(zhǎng)是無(wú)

66、法預(yù)知的，采用分段管理可以很好地解決這個(gè)問(wèn)題。,分段存儲(chǔ)管理的優(yōu)缺點(diǎn),優(yōu)點(diǎn)：,缺點(diǎn)：,有碎片問(wèn)題。,4.5.4 段頁(yè)式存儲(chǔ)管理方式,在段頁(yè)式存儲(chǔ)管理系統(tǒng)中，處理機(jī)給出的有效地址被劃分為三部分：段號(hào)、段內(nèi)頁(yè)號(hào)和頁(yè)內(nèi)地址。段頁(yè)式存儲(chǔ)管理中，記錄邏輯地址到物理地址的映射表包括段表和頁(yè)表。它們的結(jié)構(gòu)和映射功能如圖所示。,,例:給定某個(gè)邏輯地址中，段號(hào)為2，段內(nèi)地址為6015，若系統(tǒng)規(guī)定塊大小為1 KB，則采用段頁(yè)式管理，該邏輯地址表示：段號(hào)

67、為2，段內(nèi)頁(yè)號(hào)為5，頁(yè)內(nèi)地址為895。其地址變換過(guò)程如圖所示。,① 段號(hào)2與段表寄存器中存放的段表長(zhǎng)度比較以判斷是否越界，如果越界，則轉(zhuǎn)錯(cuò)誤中斷處理，否則轉(zhuǎn)②； ② 段表始地址+段號(hào)×段表項(xiàng)長(zhǎng)度，就得到屬于該段的頁(yè)表始地址和頁(yè)表長(zhǎng)度； ③ 頁(yè)號(hào)與頁(yè)表長(zhǎng)度進(jìn)行越界檢查，頁(yè)表始地址+頁(yè)號(hào)×頁(yè)表項(xiàng)長(zhǎng)度，就得到內(nèi)存頁(yè)表中記錄的該頁(yè)對(duì)應(yīng)的物理塊號(hào)16； ④ 16(塊號(hào))

68、15;1024(塊大小)+895(頁(yè)內(nèi)地址)=17279(一個(gè)物理地址號(hào))； ⑤ 訪問(wèn)內(nèi)存17 279單元，得到需要的數(shù)據(jù)365。,采用段頁(yè)式存儲(chǔ)管理，從邏輯地址到物理地址的變換過(guò)程中要三次訪問(wèn)內(nèi)存，一次是訪問(wèn)段表，一次是訪問(wèn)頁(yè)表，再一次是訪問(wèn)內(nèi)存物理地址。這就是說(shuō)，當(dāng)訪問(wèn)內(nèi)存中的一條指令或數(shù)據(jù)時(shí)，至少要訪問(wèn)內(nèi)存三次，這將使程序的執(zhí)行速度大大降低。為此，可以像在分頁(yè)存儲(chǔ)管理中那樣，使用聯(lián)想存儲(chǔ)器的方法來(lái)加快查表速度。,

69、4.6 虛擬存儲(chǔ)器的基本概念,常規(guī)存儲(chǔ)管理方式的共同點(diǎn)： 要求一個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行。問(wèn)題： (1)有的作業(yè)很大,所需內(nèi)存空間大于內(nèi)存總?cè)萘?使作業(yè)無(wú)法運(yùn)行。 (2)有大量作業(yè)要求運(yùn)行，但內(nèi)存容量不足以容納下所有作業(yè)，只能讓一部分先運(yùn)行，其它在外存等待。解決方法 （1）增加內(nèi)存容量。 （2）從邏輯上擴(kuò)充內(nèi)存容量 ----覆蓋 ----對(duì)換