4第四章存儲器管理

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

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

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

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

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

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

7、的主存地址與界限寄存器的內(nèi)容進(jìn)行比較，以判斷是否越界如果未越界，則按此地址訪問主存，否則將產(chǎn)生程序中斷——越界中斷（存儲保護(hù)中斷）,2.存儲鍵,每個存儲塊有一個由二進(jìn)位組成的存儲保護(hù)鍵一用戶作業(yè)被允許進(jìn)入主存，OS分給它一個唯一的存儲鍵號并將分配給該作業(yè)各存儲塊存儲鍵也置成同樣鍵號當(dāng)OS挑選該作業(yè)運(yùn)行時，OS將它的存儲鍵號放入程序狀態(tài)字PSW存儲鍵（“鑰匙”）域中每當(dāng)CPU訪問主存時，都將該主存塊的存儲鍵與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、 一個用戶源程序要變?yōu)樵趦?nèi)存中可執(zhí)行的程序，通常要進(jìn)行以下處理：（1）編譯：由編譯程序?qū)⒂脩粼闯绦蚓幾g成若干個目標(biāo)模塊；（2）鏈接：由鏈接程序?qū)⒛繕?biāo)模塊和相應(yīng)的庫函數(shù)鏈接成裝入模塊；（3）裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存。,1. 絕對裝入方式,如果在編譯時，事先知用戶程序在內(nèi)存的駐留位置，則編譯程序在編譯時就產(chǎn)生絕對地址的目標(biāo)代碼。裝入程序就直接把裝入模塊中的程序和數(shù)據(jù)裝入到指定的位置，（不需進(jìn)行地址轉(zhuǎn)換）。 程序

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

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

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

13、分配給目標(biāo)程序的內(nèi)存區(qū)的起始 地址B作為基地址，在把該程序裝入指定內(nèi)存區(qū)的同時， 將程序中的所有邏輯地址翻譯成相對于基地址B的物理 地址，即ｆ（ａ）＝Ｂ＋ａ,優(yōu)點(diǎn):容易實(shí)現(xiàn)，無需硬件支持，地址重定位由專門設(shè)計(jì)的 程序來完成。在早期的操作系統(tǒng)中大多數(shù)都采用這種 方法。缺點(diǎn):程序經(jī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 這條指令是把相對地址為2500的存儲單元的內(nèi)容365裝入1號累加器。而這時內(nèi)容為365的存儲單元的實(shí)際物理地址為12500（起始地址10000+相對地址2500），所以LOAD 1，2500 這條指令中的直接地址碼要作相應(yīng)的修改，即改為LOAD 1，12500。,(2)動態(tài)映射：指在程序執(zhí)行過程中進(jìn)行地址重定位，即在每次訪問內(nèi)存單元前才進(jìn)行地址變換。動態(tài)重定位可使程序不加任

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

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

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

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

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

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

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

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

24、分：一部分成為已分配的分區(qū)，剩余的部分仍作為空閑區(qū)。在回收撤除作業(yè)所占領(lǐng)的分區(qū)時，要檢查回收的分區(qū)是否與前后空閑的分區(qū)相領(lǐng)接，若是，則加以合并，使之成為一個連續(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ū)分配算法,為了將一個作業(yè)裝入內(nèi)存，應(yīng)按照一定的分配算法從空閑分區(qū)表（鏈）中選 出一個滿足作業(yè)需求的分區(qū)分配給作業(yè)，如果這個空閑分區(qū)的容量比作業(yè)申請的空間要大，則將該分區(qū)一分為二，一部分分配給作業(yè)，剩下的部分仍然留在空閑分區(qū)表（鏈）中，同時修改空閑分區(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)存分配時,從空閑分區(qū)表/鏈?zhǔn)组_始順序查找,直到找到第一個滿足其大小要求的空閑分區(qū)為止。然后再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑分區(qū)表（鏈）中。,空閑分區(qū)表,解：按首次適應(yīng)算法， 申請作業(yè)100k，分配3號分區(qū)，剩下分區(qū)為20k，起始地址160

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

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

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

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

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

32、閑分區(qū)表如上表。 申請作業(yè)100k，分配3號分區(qū)，剩下分區(qū)為20k,起始地址160K； 申請作業(yè)30k， 分配2號分區(qū)，剩下分區(qū)為2k，起始地址50K ； 申請作業(yè)7k， 分配1號分區(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ū)一般不可能正好和它申請的內(nèi)存空間大小一樣,因而將其分割成兩部分時,往往使剩下的空閑區(qū)非常小,從而在存儲器中留下許多難以利用的小空閑區(qū)（碎片或零頭）。,最壞適應(yīng)算法,算法要求 總是挑選一個最大的空閑區(qū)分割給作業(yè)使用，空閑分區(qū)表/鏈按容量大小遞減的次序排列。在進(jìn)行內(nèi)存分配時，從空閑分

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

35、,起始地址280K； 申請作業(yè)30k，分配1號分區(qū)，剩下分區(qū)為201k，起始地址310K ； 申請作業(yè)7k，分配1號分區(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è)到來時，其存儲空間的申請往往會得不到滿足。,快速適應(yīng)算法（分類搜索法）,算法要求 將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，每一類相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個空閑分區(qū)鏈表，同時在內(nèi)存中設(shè)立一張管理索引表，每一表項(xiàng)對應(yīng)了一種空閑分區(qū)類型，并記錄頭指針。進(jìn)程根據(jù)自己的

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

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

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

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

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

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

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

44、空間。將程序的必要部分（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)存；可選部分（不常用功能）在其他程序模塊中實(shí)現(xiàn)，平時存放在外存中（覆蓋文件），在需要用到時才裝入到內(nèi)存；不存在調(diào)用關(guān)系的模塊不必同時裝入到內(nèi)存，從而可以相互覆蓋。(即不同時用的模塊可共用一個分區(qū))缺點(diǎn)：編程時必須劃分程序模塊和確定程序模塊之間的覆蓋關(guān)系，增加編程復(fù)雜度。從外存裝入覆蓋文件，以時間延長來換取空間節(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)占一個分區(qū)：20K；B(50K)、D(20K)和E(40K)共用一個分區(qū)：50K；F(30K)和C(30K)共用一個分區(qū)：30K；,Total:190K,Total:110K,2. 交換技術(shù),引入：多個程序并

46、發(fā)執(zhí)行，可以將暫時不能執(zhí)行的程序送到外存中，從而獲得空閑內(nèi)存空間來裝入新程序，或讀入保存在外存中而目前到達(dá)就緒狀態(tài)的進(jìn)程。交換單位為整個進(jìn)程的地址空間。常用于多道程序系統(tǒng)或小型分時系統(tǒng)中，與分區(qū)存儲管理配合使用。又稱作"對換"或"滾進(jìn)/滾出(roll-in/roll-out)"；程序暫時不能執(zhí)行的可能原因：處于阻塞狀態(tài)，低優(yōu)先級（確保高優(yōu)先級程序執(zhí)行）；原理：暫停執(zhí)行內(nèi)存中的進(jìn)程，將整個進(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)時間；編寫程序時不影響程序結(jié)構(gòu)缺點(diǎn)：對換入和換出的控制增加處理機(jī)開銷；程序整個地址空間都進(jìn)行傳送，沒有考慮執(zhí)行過程中地址訪問的統(tǒng)計(jì)特性。考慮的問題：程序換入時的重定位；減少交換中傳送的信息量，特別是對大程序；對外存

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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