5.1計(jì)算機(jī)體系結(jié)構(gòu)和內(nèi)存層次
計(jì)算機(jī)體系結(jié)構(gòu)
內(nèi)存層次
操作系統(tǒng)的內(nèi)存管理
存儲(chǔ)管理要達(dá)到效果是抽象，把線性的物理地址編號(hào)轉(zhuǎn)變成抽象的邏輯地址空間
■抽象
邏輯地址空間
■保護(hù)（每一個(gè)進(jìn)程只能訪問自己的空間）
獨(dú)立地址空間
■共享（內(nèi)核部分的內(nèi)存是共享的）
訪問相同內(nèi)存
■虛擬化（比實(shí)際內(nèi)存大）
更大的地址空間
操作系統(tǒng)的內(nèi)存管理方式
■操作系統(tǒng)中采用的內(nèi)存管理方式
重定位(relocation)
分段(segmentation)（不連續(xù)，把代碼 數(shù)據(jù)和堆棧分成三塊)
分頁(paging)(分成基本的單位)
虛擬存儲(chǔ)(virtual memory)(· 目前多數(shù)系統(tǒng)(如Linux)采用按需頁式虛擬存儲(chǔ))
■實(shí)現(xiàn)高度依賴硬件
與計(jì)算機(jī)存儲(chǔ)架構(gòu)緊耦合
MMU (內(nèi)存管理單元):處理CPU存儲(chǔ)訪問請(qǐng)求的硬件
5.2地址空間和地址生成
地址空間定義
■物理地址空間— 硬件支持的地址空間
起始地址0，直到MAXsys
■邏輯地址空間— 在CPU運(yùn)行的進(jìn)程看到的地址
起始地址0， 直到MAXprog
邏輯地址生成
地址生成時(shí)機(jī)和限制
■編譯時(shí)（例：功能手機(jī)）
假設(shè)起始地址已知
如果起始地址改變，必須重新編譯
■加載時(shí)（例：智能手機(jī)）
如編譯時(shí)起始位置未知，編譯器需生成可重定位的代碼(relocatable code)
加載時(shí)，生成絕對(duì)地址
■執(zhí)行時(shí)
執(zhí)行時(shí)代碼可移動(dòng)
需地址轉(zhuǎn)換(映射)硬件支持
注：前面兩種情況的，不但要求在地址空間是連續(xù)的，同時(shí)運(yùn)行起來之后不能在改變他的地址，從靈活性的角度來說執(zhí)行時(shí)生成地址是最好的，但是前面兩種簡(jiǎn)單
地址生成過程
■CPU（生成邏輯地址）
ALU：需要邏輯地址的內(nèi)存內(nèi)容
MMU：進(jìn)行邏輯地址和物理地址的轉(zhuǎn)換
CPU控制邏輯：給總線發(fā)送物理地址請(qǐng)求
■內(nèi)存
發(fā)送物理地址的內(nèi)容給CPU
或接收CPU數(shù)據(jù)到物理地址
■操作系統(tǒng)
建立邏輯地址LA和物理地址PA的映射
地址檢查
5.3連續(xù)內(nèi)存分配
連續(xù)內(nèi)存分配和內(nèi)存碎片
■連續(xù)內(nèi)存分配
給進(jìn)程分配一塊不小于指定大小的連續(xù)的物理內(nèi)存區(qū)域
■內(nèi)存碎片
空閑內(nèi)存不能被利用
外部碎片（始終是個(gè)問題）
分配單元之間的未被使用內(nèi)存
■內(nèi)部碎片
分配單元內(nèi)部的未被使用內(nèi)存
取決于分配單元大小是否要取整
例，要分配510字節(jié)，因?yàn)橐≌?，分?12,2個(gè)字節(jié)就是內(nèi)存碎片
連續(xù)內(nèi)存分配：動(dòng)態(tài)分區(qū)分配
■動(dòng)態(tài)分區(qū)分配
當(dāng)程序被加載執(zhí)行時(shí)，分配一個(gè)進(jìn)程指定大小可變的分區(qū)(塊、內(nèi)存塊)
分區(qū)的地址是連續(xù)的
■操作系統(tǒng)需要維護(hù)的數(shù)據(jù)結(jié)構(gòu)
所有進(jìn)程的已分配分區(qū)
空閑分區(qū)(Empty-blocks)
■動(dòng)態(tài)分區(qū)分配策略
最先匹配(First-fit)碰到哪一個(gè)就是那個(gè)
最佳匹配(Best-fit)找一個(gè)要求大的最少的那個(gè)
最差匹配(Worst-fit)每次用的時(shí)候用的是最大的
最先匹配(First Fit Allocation)策略
思路：
分配n個(gè)字節(jié)，使用第一個(gè)可用的空間比n大的空閑塊。
示例：
分配400字節(jié)，使用第一個(gè)1KB的空閑塊。
■ 原理&實(shí)現(xiàn)
空閑分區(qū)列表按地址順序排序
分配過程時(shí)，搜索一個(gè)合適的分區(qū)
釋放分區(qū)時(shí)，檢查是否可與臨近的空閑分區(qū)合并
■ 優(yōu)點(diǎn)
簡(jiǎn)單
在高地址空間有大塊的空閑分區(qū)
■ 缺點(diǎn)
外部碎片
分配大塊時(shí)較慢
最佳匹配(Best Fit Allocation)策略
思路：
分配n字節(jié)分區(qū)時(shí)， 查找并使用不小于n的最小空閑分區(qū)
示例：
分配400字節(jié)， 使用第3個(gè)空閑塊(最小)
■ 原理&實(shí)現(xiàn)
空閑分區(qū)列表按照大小排序
分配時(shí)，查找一個(gè)合適的分區(qū)
釋放時(shí)，查找并且合并臨近的空閑分區(qū)（如果找到）
■ 優(yōu)點(diǎn)
簡(jiǎn)單
大部分分配的尺寸較小時(shí)，效果很好
· 可避免大的空閑分區(qū)被拆分
· 可減小外部碎片的大小
· 相對(duì)簡(jiǎn)單
■ 缺點(diǎn)
外部碎片
釋放分區(qū)較慢
容易產(chǎn)生很多無用的小碎片
最差匹配(Worst Fit Allocation)策略
思路：
分配n字節(jié)，使用尺寸不小于n的最大空閑分區(qū)
示例：
分配400字節(jié)，使用第2個(gè)空閑塊（最大）
■ 原理&實(shí)現(xiàn)
空閑分區(qū)列表按照大小排序
分配時(shí)，選最大的分區(qū)
釋放時(shí)，檢查是否可與臨近的空閑分區(qū)合并，進(jìn)行可能的合并，并調(diào)整空閑分區(qū)列表順序
■ 優(yōu)點(diǎn)
簡(jiǎn)單
中等大小的分配較多時(shí)，效果最好
避免出現(xiàn)太多的小碎片
■ 缺點(diǎn)
外部碎片
釋放分區(qū)較慢
容易破壞大的空閑分區(qū)，因此后續(xù)難以分配大的分區(qū)
5.4碎片整理
碎片整理：緊湊(compaction)
■ 碎片整理
通過調(diào)整進(jìn)程占用的分區(qū)位置來減少或避免分區(qū)碎片
■ 碎片緊湊
通過移動(dòng)分配給進(jìn)程的內(nèi)存分區(qū)，以合并外部碎片
碎片緊湊的條件
· 所有的應(yīng)用程序可動(dòng)態(tài)重定位
需要解決的問題
· 什么時(shí)候移動(dòng)?處于等待狀態(tài)進(jìn)程
· 開銷
碎片整理：分區(qū)對(duì)換(Swapping in/out)
通過搶占并回收處于等待狀態(tài)進(jìn)程的分區(qū)，以增大可用內(nèi)存空間
內(nèi)存不夠時(shí)，有新的進(jìn)程產(chǎn)生，就把處于等待狀態(tài)的進(jìn)程放到外存中，這樣可以使更多的進(jìn)程在系統(tǒng)里交替運(yùn)行。
5.5伙伴系統(tǒng)
比較好地折中了分配和回收過程當(dāng)中這種合并和分配塊的位置、碎片的問題
伙伴系統(tǒng)(Buddy System)
■ 整個(gè)可分配的分區(qū)大小2U（就直接劃一半與你要求分配的大小做比較）
■ 需要的分區(qū)大小為2U-1 < s≤2U時(shí)，把整個(gè)塊分配給該進(jìn)程；
如s≤2i－1，將大小為2i的當(dāng)前空閑分區(qū)劃分成兩個(gè)大小為2i－1的空閑分區(qū)
重復(fù)劃分過程，直到2i-1 < s≤2i，并把一個(gè)空閑分區(qū)分配給該進(jìn)程
伙伴系統(tǒng)的實(shí)現(xiàn)
■ 數(shù)據(jù)結(jié)構(gòu)
空閑塊按大小和起始地址組織成二維數(shù)組
初始狀態(tài)：只有一個(gè)大小為2U的空閑塊
■ 分配過程（分配的塊大小是比要求的大，比其兩倍?。?/p>
由小到大在空閑塊數(shù)組中找最小的可用空閑塊
如空閑塊過大，對(duì)可用空閑塊進(jìn)行二等分，直到得到合適的可用空閑塊
■ 釋放過程
把釋放的塊放入空閑塊數(shù)組
合并滿足合并條件的空閑塊
■ 合并條件
大小相同2i
地址相鄰
低地址空閑塊起始地址為2i＋1的位數(shù)
伙伴系統(tǒng)中的內(nèi)存分配
