基本存儲器管理

1、 SUSE 基本內(nèi)存管理基本內(nèi)存管理640K ought to be enough for anybodyBill Gates, 1981susesoftware 內(nèi)存的引入內(nèi)存的引入v計算機直接讀取卡片，執(zhí)行指令效率極低，靈活性差v“存儲程序”把要運行的程序先“加載”，再自動執(zhí)行把程序放到“內(nèi)存”v對內(nèi)存的要求：大容量、高速度、持久性實際內(nèi)存是層次結(jié)構：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)存管理機制內(nèi)存管理機制v現(xiàn)實的內(nèi)存層次和理想的內(nèi)存有差距，需要一個有效的內(nèi)存管理機制v內(nèi)存管理機制負責對內(nèi)存架構進行管理，使程序在內(nèi)存架構的任何一個層次上的存放對用戶來說都是一樣的用戶無須擔心自己程序的位置，程序的運行、計算輸出結(jié)果是一樣的v通過虛擬內(nèi)存：提供一個比物理空間大許多的地址空間susesoftware 內(nèi)存管理的目標內(nèi)存管理的目標v地址保護進程不能隨便訪問另一個進程v地址獨立程序中的地址和機器的物理地址無關如程序中的語句 c = a + b ，

3、大致可以作為3條指令：到a所在的地址取值送入累加器；到b所在地址取值，送入累加器；把累加器結(jié)果寫入變量c所在地址susesoftware 地址地址v如32位的處理器，它的每一條指令是4 個字節(jié)，以4 個字節(jié)存儲順序，進行順序執(zhí)行，CPU 是順序執(zhí)行的，只要沒發(fā)生什么跳轉(zhuǎn)，它會順序進行執(zhí)行，編譯器會對每一條指令分配一個 編譯地址，這是編譯器分配的，在編譯過程中分配的地址，我們稱之為編譯地址。 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)存容量偏小利用便宜、大容量的磁盤用戶對內(nèi)存的操作由操作系統(tǒng)負責管理, 程序執(zhí)行時的地址由OS負責轉(zhuǎn)換，用戶可以不管。用外存來虛擬內(nèi)存進一步，將緩存和磁帶也包括進來：速度像緩存那樣快（比內(nèi)存快），容量像磁帶那么大v虛擬一種幻象，真正的內(nèi)存沒有變化但計算機里面常常是“空間換時間”，虛擬內(nèi)存會比真的內(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)一了：輸入輸出就和訪存一樣，如某個寄存器地址是Ra = 0XFFFFA001, 那么往寄存器里寫數(shù)據(jù)，就可以是*Ra = 1; 如果是非內(nèi)存映射的系統(tǒng)，需要特殊的指令進行I/O操作 OS in ROM用戶程序 in RAMOS in RAMsusesoftware 最簡單的內(nèi)存管理最簡單的內(nèi)存管理-單道編程下單道編程下v內(nèi)存使用情況是？操作系統(tǒng)占用內(nèi)存空間固定用戶程序為簡單，可以將用戶程序放到內(nèi)存一個固定位置。操作系統(tǒng)跳轉(zhuǎn)到同一個地方啟動程序v用戶程序中的地址靜態(tài)地址翻譯：地址是可先計算出來，編譯器可以事先知道“

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

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

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

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

11、sesoftware 動態(tài)地址翻譯的優(yōu)點動態(tài)地址翻譯的優(yōu)點v1、靈活不依賴于編譯器的靜態(tài)地址翻譯，在任何操作系統(tǒng)中可用v2、保護：可以使用2個寄存器就做到地址保護v3、虛擬內(nèi)存得以實現(xiàn)一個程序可以用的內(nèi)存空間不變所有程序的內(nèi)存空間之和可以大于物理內(nèi)存把整個進程放到磁盤上新進程調(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)基于保護(base+bound)，會破壞進程地址獨立不方便實現(xiàn)共享susesoftware 非固定分區(qū)非固定分區(qū)v固定分區(qū)簡單，缺點也很明顯程序大小和分區(qū)大小不容易匹配大程序可能無法放入無法應對程序運行期間的動態(tài)生長v非固定分區(qū)除了OS的部分，其余部分作為以整體來依次的“劃分”如果依次“疊羅漢”式挨著分配，也會導致無法增長分配時預留一塊空閑供程序增長使用susesoftware 程序的增長程序的增長v 程序的代碼段固定，數(shù)據(jù)和堆棧增長數(shù)據(jù)如new，棧如局部變量數(shù)據(jù)和棧往一個方向增長，導致可能某個先到頂，另一個也無法前進數(shù)據(jù)和棧反向增長susesof

13、tware 交換：交換：swappingv非固定分區(qū)，考慮到程序可能增長，預留空間，但不能從根本解決問題交換：將程序倒出到硬盤，在加載到內(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隨著進程的推進，可能會留下很多無法使用的微小內(nèi)存空間-外部碎片v可以使用交換進行整合susesoftware 重疊重疊 overlayv當一個程序超過了物理內(nèi)存大小，還能用“交換”等方式來讓它執(zhí)行么？v將程序按功能分為若干單元：一個單元執(zhí)行完以后再執(zhí)行下一個單元。而一旦執(zhí)行到下一個單元

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

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

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

17、表示的比較v表項（占用空間）：當程序數(shù)量少時，鏈表表項少位圖的空間成本是固定的v可靠性：位圖：無；鏈表：有v時間成本位圖：簡單鏈表：對表項進行合并操作v其他：查找時間等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)存和外設之間換入換出v核心概念虛擬地址：基址+極限物理地址：內(nèi)存中真實地址susesoftware susesoftware 動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法v新作業(yè)裝入內(nèi)存,從空閑分區(qū)表或空閑分區(qū)鏈中選一塊分區(qū)分配給作業(yè)v1首次適應算法FF。 分區(qū)按低址高址鏈接, 從鏈首開始查找, 找到的第一個分區(qū)中劃出一塊分給作業(yè), 余下的仍留在空閑鏈中 特點：低址內(nèi)存使用頻繁, 有內(nèi)存碎片, 高地址保留大空閑區(qū), 增加查找時間susesoftware 動態(tài)分區(qū)動態(tài)分區(qū) 2循環(huán)首次適應