第9講物理內存管理：連續(xù)內存分配

1、第第9 9講講 物理內存管理：物理內存管理：連續(xù)內存分配連續(xù)內存分配授課教師：馬立平授課教師：馬立平聯系方式：聯系方式：Southwest University of Science and Technology內容摘要計算機體系結構/內存層次連續(xù)內存分配計算機體系結構內存層次操作系統的內存管理方式地址空間 & 地址生成伙伴系統I/O設備總線計算機體系結構算術邏輯單元(ALU)寄存器控制邏輯高速緩存存儲管理單元（MMU）Intel 64 and IA-32 Architectures Software Developer ManualsCPU內存內存層次處理器CPUL1緩存L2緩存高速

2、緩存未命中內存缺頁外存(虛擬內存)操作系統硬件(MMU)慢最快快較快訪問速度3.6GHz1.3GHz5ms(查找時間)操作系統的內存管理 邏輯（虛擬）地址空間 物理地址空間MMU抽象邏輯地址空間保護獨立地址空間共享訪問相同內存虛擬化更大的地址空間P1進程Max 操作系統內核 P2進程 P3進程 P4進程0 內存 外存操作系統的內存管理方式操作系統中采用的內存管理方式重定位(relocation)分段(segmentation)分頁(paging)虛擬存儲(virtual memory) 目前多數系統(如 Linux)采用按需頁式虛擬存儲實現高度依賴硬件與計算機存儲架構緊耦合MMU (內存管理單

3、元): 處理CPU存儲訪問請求的硬件內存管理方式操作系統中采用的內存管理方式重定位(relocation)分段(segmentation)分頁(paging)虛擬內存(virtual memory) 目前多數系統(如 Linux)采用按需頁式虛擬內存實現高度依賴硬件與計算機存儲架構緊耦合MMU (內存管理單元): 處理CPU存儲訪問請求的硬件內容摘要計算機體系結構/內存層次連續(xù)內存分配地址空間的定義地址生成地址檢查地址空間 & 地址生成伙伴系統地址空間定義起始地址0，直到 MAXsys物理地址空間 硬件支持的地址空間起始地址0， 直到 MAXprog邏輯地址空間 在CPU運行的進程看到

4、的地址但是地址(address)是從哪里來的?movl %eax, $0 xfffa620e地址(address)是從哪里來的?movl %eax, $0 xfffa620e進程PMAXsys0邏輯地址生成prog P : : foo() : :end PP: :push .inc SP, xjmp _foo :foo: . :push .inc SP, 4jmp 75 : .075編譯匯編鏈接程序加載(重定位) : : :jmp 175 : .1750100函數庫 : : :jmp 1175 : .11001175函數庫1000地址生成時機和限制編譯時假設起始地址已知如果起始地址改變，必須重

5、新編譯加載時如編譯時起始位置未知，編譯器需生成可重定位的代碼(relocatable code) 加載時，生成絕對地址執(zhí)行時執(zhí)行時代碼可移動需地址轉換(映射)硬件支持地址生成過程CPUALU：需要邏輯地址的內存內容MMU：進行邏輯地址和物理地址的轉換CPU控制邏輯：給總線發(fā)送物理地址請求內存發(fā)送物理地址的內容給CPU或接收CPU數據到物理地址建立邏輯地址LA和物理地址PA的映射操作系統物理地址生成總線內存ALU寄存器高速緩存MMU控制器I/O設備movl %eax, $0 xfffa620e地址映射邏輯地址物理地址 CPU地址檢查movl %eax, $0 xfffa620e0MAXsys10

6、001500進程P的物理地址空間0MAXprog段基址寄存器邏輯地址段長度寄存器內存異常物理地址指令yesno5001000進程P邏輯地址空間CPU操作系統設置起始(base)和最大(limit)邏輯地址空間+指令內存管理方式操作系統中采用的內存管理方式重定位(relocation)分段(segmentation)分頁(paging)虛擬內存(virtual memory) 目前多數系統(如 Linux)采用按需頁式虛擬內存實現高度依賴硬件與計算機存儲架構緊耦合MMU (內存管理單元): 處理CPU存儲訪問請求的硬件計算機體系結構/內存層次地址空間 & 地址生成連續(xù)內存分配 內存碎片

7、動態(tài)分配 最先匹配 最佳匹配 最差匹配 碎片整理內容摘要伙伴系統進程P2地址空間連續(xù)內存分配和內存碎片連續(xù)內存分配給進程分配一塊不小于指定大小的連續(xù)的物理內存區(qū)域內存碎片空閑內存不能被利用外部碎片分配單元之間的未被使用內存內部碎片 分配單元內部的未被使用內存 取決于分配單元大小是否要取整進程P1地址空間進程P3地址空間MAX0代碼數據堆棧進程P5進程P3進程P6進程P4進程P2進程P1連續(xù)內存分配：動態(tài)分區(qū)分配動態(tài)分區(qū)分配當程序被加載執(zhí)行時，分配一個進程指定大小可變的分區(qū)(塊、內存塊) 分區(qū)的地址是連續(xù)的所有進程的已分配分區(qū)操作系統需要維護的數據結構空閑分區(qū)(Empty-blocks)動態(tài)分區(qū)

8、分配策略最先匹配(First-fit)最佳匹配(Best-fit)最差匹配(Worst-fit)MAX02K bytes500 bytes思路：分配n個字節(jié)，使用第一個可用的空間比n大的空閑塊。 示例：分配400字節(jié)，使用第一個1KB的空閑塊。為空閑塊500 bytes2K bytes最先匹配(First Fit Allocation)策略1K bytes最先匹配(First Fit Allocation)策略分配過程時，搜索一個合適的分區(qū)釋放分區(qū)時，檢查是否可與臨近的空閑分區(qū)合并空閑分區(qū)列表按地址順序排序 原理 & 實現簡單在高地址空間有大塊的空閑分區(qū) 優(yōu)點 缺點外部碎片分配大塊時較

9、慢2K bytes1K bytes500 bytes1K bytes2K bytes最佳匹配(Best Fit Allocation)策略思路：分配n字節(jié)分區(qū)時， 查找并使用不小于n的最小空閑分區(qū)示例：分配400字節(jié)， 使用第3個空閑塊(最小)為空閑塊分配時，查找一個合適的分區(qū) 可避免大的空閑分區(qū)被拆分 可減小外部碎片的大小釋放時，查找并且合并臨近的空閑分區(qū)（如果找到） 相對簡單空閑分區(qū)列表按照大小排序 原理 & 實現最佳匹配(Best Fit Allocation)策略大部分分配的尺寸較小時，效果很好 優(yōu)點 缺點外部碎片釋放分區(qū)較慢容易產生很多無用的小碎片1K bytes最差匹配(W

10、orst Fit Allocation)策略思路：分配n字節(jié)，使用尺寸不小于n的最大空閑分區(qū)示例：分配400字節(jié)，使用第2個空閑塊（最大）500 bytes1K bytes2K bytes為空閑塊最差匹配(Worst Fit Allocation)策略 原理 & 實現空閑分區(qū)列表按由大到小排序分配時，選最大的分區(qū)釋放時，檢查是否可與臨近的空閑分區(qū)合并，進行可能的合并，并調整空閑分區(qū)列表順序避免出現太多的小碎片中等大小的分配較多時，效果最好 優(yōu)點 缺點釋放分區(qū)較慢外部碎片容易破壞大的空閑分區(qū)，因此后續(xù)難以分配大的分區(qū)計算機體系結構/內存層次地址空間 & 地址生成連續(xù)內存分配 內存

11、碎片 動態(tài)分配 碎片整理 緊湊（compaction） 分區(qū)對換(swap in/out)內容摘要伙伴系統進程P4進程P3進程P2進程P1碎片整理：緊湊(compaction)MAX0 碎片緊湊通過移動分配給進程的內存分區(qū)，以合并外部碎片碎片緊湊的條件 所有的應用程序可動態(tài)重定位 碎片整理通過調整進程占用的分區(qū)位置來減少或避免分區(qū)碎片需要解決的問題 什么時候移動? 開銷對換等待隊列對換等待就緒隊列等待隊列等待運行就緒P4 P3P2P1碎片整理：分區(qū)對換(Swapping in/out) 通過搶占并回收處于等待狀態(tài)進程的分區(qū)，以 增大可用內存空間 OS外存內存P1P2P3P4碎片整理：分區(qū)對換(

12、Swapping in/out)操作系統內核用戶地址空間進程p1進程p2 換入 換出內存外存 需要解決的問題 交換哪個（些）程序？伙伴系統 伙伴系統的實現 ucore中的伙伴系統計算機體系結構/內存層次地址空間 & 地址生成連續(xù)內存分配內容摘要伙伴系統(Buddy System) 整個可分配的分區(qū)大小2U 需要的分區(qū)大小為2U-1 s 2U 時，把整個塊分配 給該進程；如s 2i1，將大小為2i 的當前空閑分區(qū)劃分成兩個大小為2i1 的空閑分區(qū)重復劃分過程，直到2i-1 s 2i，并把一個空閑分區(qū)分配給該進程伙伴系統的實現 數據結構空閑塊按大小和起始地址組織成二維數組 分配過程由小到大

13、在空閑塊數組中找最小的可用空閑塊如空閑塊過大，對可用空閑塊進行二等分，直到得到合適的可用空閑塊初始狀態(tài)：只有一個大小為2U的空閑塊伙伴系統中的內存分配Request 100K1 Mbyte block1M512K256K128KA=128KRequest 240KA=128K128K512K256KB=256KRequest 64KA=128KB=256K512K128KC=64K64KRequest 256KA=128KC=64K64KB=256K512KD=256K256KRelease BA=128KC=64K64KD=256K256KB=256K256KRelease AC=64K64

14、K256KD=256K256KA=128K128KRequest 75KC=64K64K256KD=256K256KA=128K128KE=128KRelease CC=64K64K256KD=256K256KA=128K128KE=128K128KRelease EC=64K64K256KD=256K256KA=128K128KE=128K128K256K512KRelease D1MC=64K64K256KD=256K256KA=128K128KE=128K128K256K512K512K1MRequest 100KRequest 240KRequest 64KRequest 256KRe

15、lease BRelease ARequest 75KRelease CRelease ERelease D伙伴系統的實現 釋放過程把釋放的塊放入空閑塊數組合并滿足合并條件的空閑塊 合并條件大小相同2i/wiki/Buddy_memory_allocation128K1M512K64K256KC=64K256K64K256KD=256KA=128K地址相鄰低地址空閑塊起始地址為2i1的位數ucore中的物理內存管理struct pmm_manager const char *name;void (*init)(void);void (*init_me

16、mmap)(struct Page *base, size_t n);struct Page *(*alloc_pages)(size_t order);void (*free_pages)(struct Page *base, size_t n);size_t (*nr_free_pages)(void);void (*check)(void);struct pmm_manager const char *name;void (*init)(void);void (*init_memmap)(struct Page *base, size_t n);struct Page *(*alloc_

17、pages)(size_t order);void (*free_pages)(struct Page *base, size_t n);size_t (*nr_free_pages)(void);void (*check)(void);ucore中的伙伴系統實現const struct pmm_manager buddy_pmm_manager = .name = buddy_pmm_manager,.init = buddy_init,.init_memmap = buddy_init_memmap,.alloc_pages = buddy_alloc_pages,.free_pages = buddy_free_pages,.nr_free_pages = buddy_nr_free_pag