基本存儲(chǔ)器管理

1、 SUSE 基本內(nèi)存管理基本內(nèi)存管理640K ought to be enough for anybodyBill Gates, 1981susesoftware 內(nèi)存的引入內(nèi)存的引入v計(jì)算機(jī)直接讀取卡片，執(zhí)行指令效率極低，靈活性差v“存儲(chǔ)程序”把要運(yùn)行的程序先“加載”，再自動(dòng)執(zhí)行把程序放到“內(nèi)存”v對(duì)內(nèi)存的要求：大容量、高速度、持久性實(shí)際內(nèi)存是層次結(jié)構(gòu)：Cache: Small amount of fast, expensive memory Main memory: Some medium-speed, medium price memoryDisk storage: Gigabytes

2、of slow, cheap memorycachememorydisktapeMemory hierarchysusesoftware 內(nèi)存管理機(jī)制內(nèi)存管理機(jī)制v現(xiàn)實(shí)的內(nèi)存層次和理想的內(nèi)存有差距，需要一個(gè)有效的內(nèi)存管理機(jī)制v內(nèi)存管理機(jī)制負(fù)責(zé)對(duì)內(nèi)存架構(gòu)進(jìn)行管理，使程序在內(nèi)存架構(gòu)的任何一個(gè)層次上的存放對(duì)用戶來說都是一樣的用戶無須擔(dān)心自己程序的位置，程序的運(yùn)行、計(jì)算輸出結(jié)果是一樣的v通過虛擬內(nèi)存：提供一個(gè)比物理空間大許多的地址空間susesoftware 內(nèi)存管理的目標(biāo)內(nèi)存管理的目標(biāo)v地址保護(hù)進(jìn)程不能隨便訪問另一個(gè)進(jìn)程v地址獨(dú)立程序中的地址和機(jī)器的物理地址無關(guān)如程序中的語句 c = a + b ，

3、大致可以作為3條指令：到a所在的地址取值送入累加器；到b所在地址取值，送入累加器；把累加器結(jié)果寫入變量c所在地址susesoftware 地址地址v如32位的處理器，它的每一條指令是4 個(gè)字節(jié)，以4 個(gè)字節(jié)存儲(chǔ)順序，進(jìn)行順序執(zhí)行，CPU 是順序執(zhí)行的，只要沒發(fā)生什么跳轉(zhuǎn)，它會(huì)順序進(jìn)行執(zhí)行，編譯器會(huì)對(duì)每一條指令分配一個(gè) 編譯地址，這是編譯器分配的，在編譯過程中分配的地址，我們稱之為編譯地址。 susesoftware #includeint main() int a,b,c; a=3; b=4; c=a+b; printf(%d,c); return 0;gcc -S testcr.cLFB0:

4、.cfi_startprocpushq%rbp.cfi_def_cfa_offset 16.cfi_offset 6, -16movq%rsp, %rbp.cfi_def_cfa_register 6subq$16, %rspmovl$3, -12(%rbp)movl$4, -8(%rbp)movl-8(%rbp), %eaxmovl-12(%rbp), %edxaddl%edx, %eaxmovl%eax, -4(%rbp)movl-4(%rbp), %eaxmovl%eax, %esimovl$.LC0, %edimovl$0, %eaxcallprintfmovl$0, %eaxleav

5、esusesoftware 虛擬內(nèi)存虛擬內(nèi)存 Virtual Memoryv物理內(nèi)存容量偏小利用便宜、大容量的磁盤用戶對(duì)內(nèi)存的操作由操作系統(tǒng)負(fù)責(zé)管理, 程序執(zhí)行時(shí)的地址由OS負(fù)責(zé)轉(zhuǎn)換，用戶可以不管。用外存來虛擬內(nèi)存進(jìn)一步，將緩存和磁帶也包括進(jìn)來：速度像緩存那樣快（比內(nèi)存快），容量像磁帶那么大v虛擬一種幻象，真正的內(nèi)存沒有變化但計(jì)算機(jī)里面常常是“空間換時(shí)間”，虛擬內(nèi)存會(huì)比真的內(nèi)存快嗎？有這種兩全其美的事情？susesoftware 操作系統(tǒng)在內(nèi)存中的位置操作系統(tǒng)在內(nèi)存中的位置v操作系統(tǒng)核心常駐內(nèi)存通常占據(jù)的是從0開始的一部分地址空間，用戶程序在高地址如果有ROM，操作系統(tǒng)的部分放在ROM中，部分

6、在RAM中，通常，ROM的地址編碼高于用戶空間的最大地址，這樣I/O操作和訪存就統(tǒng)一了：輸入輸出就和訪存一樣，如某個(gè)寄存器地址是Ra = 0XFFFFA001, 那么往寄存器里寫數(shù)據(jù)，就可以是*Ra = 1; 如果是非內(nèi)存映射的系統(tǒng)，需要特殊的指令進(jìn)行I/O操作 OS in ROM用戶程序 in RAMOS in RAMsusesoftware 最簡單的內(nèi)存管理最簡單的內(nèi)存管理-單道編程下單道編程下v內(nèi)存使用情況是？操作系統(tǒng)占用內(nèi)存空間固定用戶程序?yàn)楹唵危梢詫⒂脩舫绦蚍诺絻?nèi)存一個(gè)固定位置。操作系統(tǒng)跳轉(zhuǎn)到同一個(gè)地方啟動(dòng)程序v用戶程序中的地址靜態(tài)地址翻譯：地址是可先計(jì)算出來，編譯器可以事先知道“

7、物理地址”susesoftware 單道編程內(nèi)存管理的缺點(diǎn)單道編程內(nèi)存管理的缺點(diǎn)v程序要運(yùn)行，需要放入到內(nèi)存空間，若程序大于可用內(nèi)存，無法運(yùn)行v單道程序本身的缺點(diǎn)：浪費(fèi)內(nèi)存v可移植性差不同操作系統(tǒng)可能無法運(yùn)行，為什么？ORG 0030HMOV TMOD,#10HMOV 28H,#01HSETB TR1NEXT:MOV TH1,#3CHMOV TL1,#0B0HMOV P1, 28HAGAI: JBC TF1,SHISJMP AGAISHI: RL 28HSJMP 38HEND單片機(jī)的“絕對(duì)裝入”：susesoftware 多道編程的內(nèi)存管理多道編程的內(nèi)存管理v多進(jìn)程帶來的問題程序是否能加載到固

8、定的地址？程序中語句的物理地址是否能預(yù)先計(jì)算？內(nèi)存是否需要保護(hù)？v程序放在內(nèi)存什么地方？如何知道其地址？邏輯地址-物理地址susesoftware 可重定位裝入可重定位裝入v用戶不可能知道自己程序的位置 由系統(tǒng)裝入程序:根據(jù)內(nèi)存當(dāng)前的情況 重定位：多道環(huán)境下,編譯所得到的目標(biāo)模塊都是以0作為起始地址開始,而實(shí)際放入到內(nèi)存不可能是放在內(nèi)存0的位置上.裝入時(shí)對(duì)目標(biāo)程序中的指令和數(shù)據(jù)的修改過程稱為重定位 靜態(tài)重定位:地址變換在裝入時(shí)一次完成,以后不再改變 如何調(diào)整？相對(duì)地址需要進(jìn)行改變0100025005000LOAD 1, 2500LOAD 1, 1250036536510000110001250

9、015000作業(yè)地址空間作業(yè)地址空間內(nèi)存空間內(nèi)存空間圖：靜態(tài)重定位圖：靜態(tài)重定位susesoftware 靜態(tài)重定位靜態(tài)重定位v它的主要缺點(diǎn)是：（1）程序的存儲(chǔ)空間只能是連續(xù)的一片區(qū)域，而且在重定位之后就不能再移動(dòng)。這不利于內(nèi)存空間的有效使用。（2）各個(gè)用戶進(jìn)程很難共享內(nèi)存中的同一程序的副本（要求程序的存儲(chǔ)空間是連續(xù)的，不能把程序放在若干個(gè)不連續(xù)的區(qū)域內(nèi)）susesoftware 固定分區(qū)固定分區(qū)v 多道編程下的內(nèi)存管理策略：固定分區(qū)，動(dòng)態(tài)分區(qū)v 事先分為若干分區(qū)，分區(qū)大小固定（大小不一致）v 程序到了，2種方式分配到內(nèi)存中：單一隊(duì)列和多隊(duì)列susesoftware 地址翻譯地址翻譯/轉(zhuǎn)換（轉(zhuǎn)

10、換（translation）的方法：重點(diǎn)）的方法：重點(diǎn)v多道編程環(huán)境下，程序加載到內(nèi)存的地址是不固定的，程序的物理地址需要進(jìn)行翻譯：程序整個(gè)一起加載到某個(gè)內(nèi)存塊，所以：物理地址 = 邏輯地址 + 程序所在區(qū)域的起始地址v保護(hù)：程序不能超出自己所在的內(nèi)存塊合法地址：內(nèi)存塊起始地址起始地址+程序長度即：基址，極限(邊界bound)susesoftware 基址和極限基址和極限v 進(jìn)程不管物理地址，對(duì)每個(gè)程序而言，它仿佛獨(dú)占了一個(gè)內(nèi)存空間從0極限的計(jì)算機(jī)Physical memory0basebase + boundphysical memory sizevirtual memory0boundsu

11、sesoftware 動(dòng)態(tài)地址翻譯的優(yōu)點(diǎn)動(dòng)態(tài)地址翻譯的優(yōu)點(diǎn)v1、靈活不依賴于編譯器的靜態(tài)地址翻譯，在任何操作系統(tǒng)中可用v2、保護(hù)：可以使用2個(gè)寄存器就做到地址保護(hù)v3、虛擬內(nèi)存得以實(shí)現(xiàn)一個(gè)程序可以用的內(nèi)存空間不變所有程序的內(nèi)存空間之和可以大于物理內(nèi)存把整個(gè)進(jìn)程放到磁盤上新進(jìn)程調(diào)入內(nèi)存susesoftware 基址基址+極限的問題極限的問題v能不能共享代碼段？data (P2)data (P1)codePhysical memorydata (P1)codedata (P2)codevirtual memoryvirtual memoryvirtual address(process 1)vir

12、tual address(process 2)基于保護(hù)(base+bound)，會(huì)破壞進(jìn)程地址獨(dú)立不方便實(shí)現(xiàn)共享susesoftware 非固定分區(qū)非固定分區(qū)v固定分區(qū)簡單，缺點(diǎn)也很明顯程序大小和分區(qū)大小不容易匹配大程序可能無法放入無法應(yīng)對(duì)程序運(yùn)行期間的動(dòng)態(tài)生長v非固定分區(qū)除了OS的部分，其余部分作為以整體來依次的“劃分”如果依次“疊羅漢”式挨著分配，也會(huì)導(dǎo)致無法增長分配時(shí)預(yù)留一塊空閑供程序增長使用susesoftware 程序的增長程序的增長v 程序的代碼段固定，數(shù)據(jù)和堆棧增長數(shù)據(jù)如new，棧如局部變量數(shù)據(jù)和棧往一個(gè)方向增長，導(dǎo)致可能某個(gè)先到頂，另一個(gè)也無法前進(jìn)數(shù)據(jù)和棧反向增長susesof

13、tware 交換：交換：swappingv非固定分區(qū)，考慮到程序可能增長，預(yù)留空間，但不能從根本解決問題交換：將程序倒出到硬盤，在加載到內(nèi)存的過程操作系統(tǒng)BA操作系統(tǒng)BAC操作系統(tǒng)BC操作系統(tǒng)BCD操作系統(tǒng)DC操作系統(tǒng)A操作系統(tǒng)ADCA增長，已無法容納換出空間足夠，換入susesoftware 外部碎片外部碎片v隨著進(jìn)程的推進(jìn)，可能會(huì)留下很多無法使用的微小內(nèi)存空間-外部碎片v可以使用交換進(jìn)行整合susesoftware 重疊重疊 overlayv當(dāng)一個(gè)程序超過了物理內(nèi)存大小，還能用“交換”等方式來讓它執(zhí)行么？v將程序按功能分為若干單元：一個(gè)單元執(zhí)行完以后再執(zhí)行下一個(gè)單元。而一旦執(zhí)行到下一個(gè)單元

14、，就不會(huì)再執(zhí)行前面的單元。v這樣可以把后面的程序單元覆蓋到當(dāng)前程序單元之上，可以重復(fù)使用一些內(nèi)存哪些單元可以被覆蓋？哪些不再執(zhí)行？操作系統(tǒng)不知道，只有程序員清楚。操作系統(tǒng)無法進(jìn)行重疊，需要程序員來做這個(gè)事情susesoftware 小結(jié)：程序的小結(jié)：程序的“裝入裝入”-把程序放入到內(nèi)存把程序放入到內(nèi)存v絕對(duì)裝入：單道系統(tǒng)中，編譯器產(chǎn)生物理地址v靜態(tài)重定位：編譯器產(chǎn)生0開始的邏輯地址，裝入時(shí)由地址重定位機(jī)構(gòu)修改程序中的地址裝入內(nèi)存缺點(diǎn)：程序中地址已經(jīng)修改，裝入后不能移動(dòng)，而某些時(shí)候需要在內(nèi)存中移動(dòng)程序優(yōu)點(diǎn)：效率高，CPU直接取指執(zhí)行v動(dòng)態(tài)重定位地址空間中的代碼在裝入過程中不發(fā)生變化不發(fā)生變化，程

15、序執(zhí)行期間，每次訪問內(nèi)存之前進(jìn)行重定位。這種變換是靠硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)的。通常采用一個(gè)重定位寄存器（若沒有硬件，CPU每次要計(jì)算地址，效率太低），其中放有當(dāng)前正在執(zhí)行的程序在內(nèi)存空間中的起始地址susesoftware （b）采用動(dòng)態(tài)重定位時(shí)內(nèi)存）采用動(dòng)態(tài)重定位時(shí)內(nèi)存空間及地址重定位示意圖空間及地址重定位示意圖 （a）采用靜態(tài)重定）采用靜態(tài)重定 位后的內(nèi)存空間位后的內(nèi)存空間 因?yàn)槊繄?zhí)行一條指令都需要重定位，為提高效率，使用硬件寄存器susesoftware 邏輯地址與物理地址邏輯地址與物理地址vCPU所發(fā)出的地址通常為邏輯地址,而內(nèi)存單元看到的地址(內(nèi)存地址寄存器中的地址)為物理地址(Phy

16、sical Address)v編譯和裝入時(shí)生成的物理和邏輯地址相同,但執(zhí)行時(shí)不同的”捆綁”方案導(dǎo)致不同的邏輯地址和物理地址, 通常稱邏輯地址為”虛擬地址”v虛擬地址到物理地址的映射是由MMU硬件設(shè)備來完成的,簡單的MMU就是一個(gè)重定位寄存器v用戶程序永遠(yuǎn)看不到真正的物理地址.如程序中使用一個(gè)指向位置123的指針, 那么對(duì)它的使用都是123這個(gè)數(shù). 當(dāng)對(duì)這個(gè)內(nèi)存地址操作時(shí)才轉(zhuǎn)換為物理地址susesoftware 空閑內(nèi)存管理空閑內(nèi)存管理v用1、0表示內(nèi)存塊的使用情況簡單、直觀v用鏈表表示分配情況P：表示使用，開始和長度；H：表示空閑susesoftware 位圖表示和鏈表表示的比較位圖表示和鏈表

17、表示的比較v表項(xiàng)（占用空間）：當(dāng)程序數(shù)量少時(shí)，鏈表表項(xiàng)少位圖的空間成本是固定的v可靠性：位圖：無；鏈表：有v時(shí)間成本位圖：簡單鏈表：對(duì)表項(xiàng)進(jìn)行合并操作v其他：查找時(shí)間等susesoftware 小結(jié)：基本內(nèi)存管理小結(jié)：基本內(nèi)存管理v固定加載地址的內(nèi)存管理單道系統(tǒng)，程序物理地址v固定分區(qū)的內(nèi)存管理內(nèi)存劃分為固定分區(qū)，程序裝入某分區(qū)v非固定分區(qū)的內(nèi)存管理即來即分v交換內(nèi)存管理內(nèi)存和外設(shè)之間換入換出v核心概念虛擬地址：基址+極限物理地址：內(nèi)存中真實(shí)地址susesoftware susesoftware 動(dòng)態(tài)分區(qū)分配算法動(dòng)態(tài)分區(qū)分配算法v新作業(yè)裝入內(nèi)存,從空閑分區(qū)表或空閑分區(qū)鏈中選一塊分區(qū)分配給作業(yè)v1首次適應(yīng)算法FF。 分區(qū)按低址高址鏈接, 從鏈?zhǔn)组_始查找, 找到的第一個(gè)分區(qū)中劃出一塊分給作業(yè), 余下的仍留在空閑鏈中 特點(diǎn)：低址內(nèi)存使用頻繁, 有內(nèi)存碎片, 高地址保留大空閑區(qū), 增加查找時(shí)間susesoftware 動(dòng)態(tài)分區(qū)動(dòng)態(tài)分區(qū) 2循環(huán)首次適應(yīng)