virtual memory(虛擬記憶體)
用途:將輔助記憶體當成虛擬的主記憶體單元
做法:程式與資料先存放在輔助記憶體中,程式執行時再由作業系統自動處理主記憶體單元與輔助記憶體間程式與資料的移動
好處:
程式與資料的大小可不受到主記憶體單元定址空間的限制,解決主記憶體單元容量空間不夠大的問題
可撰寫具有較大邏輯定址空間的程式,同時可讓程式在較小的實際定址空間的主記憶體單元中加以執行
虛擬記憶體的動態位址轉換
採用軟體實作的技術,透過block mapping table(區塊對照表)把virtual address對映到real address,並決定hit或miss
ps:virtual address(虛擬位置)是虛擬記憶體的位置
ps:real/physical address(實際位置)是主記憶體單的位置
virtual address和real address的相對位置完全相同,而相對位置的欄位是依據頁或段的大小
ex:
頁的大小是1kb,則相對位置的欄位為10bit
…………….
virtual memory實作方式
依區塊類別分:
paging(分頁)
segmentation(分段)
paging/segmentation(分頁/分段)
paging:
主記憶體與輔助記憶體間以page為對映單位
ps:主記憶體單元與程式都切割成大小相同的區塊,輔助記憶體的區塊稱為page(頁),主記憶體的區塊稱為page frame(頁框)
透過page mapping table(頁對照表)把virtual address對映到real address
page mapping table格式:[ 進駐位元 | 輔助記憶體位置 | 主記憶的頁編號 ]
virtual address格式:[ 頁的編號 | 相對位置 ]
優點:block的對應,取代,捉取…等記憶體管理單元運作變簡易,適合硬體的製作
缺點:在protection(軟體的保護)與sharing(資料的共用)變得十分困難
會產生internal fragmentation
ex:
設virtual address是23a01180,page大小是1k
則相對位置欄位=10bit,而23a01180轉2進位得到[ 0010,0011,1010,0000,0001,00 | 01,1000,0000 ]=[ 08e804 | 180 ]
因此頁的編號是08e804,相對位置是180
ex:32 pages of 2k bytes each 表示頁的編號欄位為5bit(因為2^5=32),相對位置欄位為11bit(因為2^11=2k)
segmentation:
主記憶體與輔助記憶體間以segment為對映單位
ps:程式切割成大小可能不同的區塊,此區塊為segment
透過segment mapping table(段對照表)把virtual address對映到real address
格式:[ 段的編號 | 相對位置 ]
優點:把protection與sharing變得容易
缺點:記憶體管理單元運作變困難,適合軟體的製作
會產生external fragmentation
paging/segmentation:
程式切割成segment,每個segment在切割成page
主記憶體與輔助記憶體間以page為對映單位
透過segment mapping table和page mapping table把virtual address對映到real address
格式:[ 段的編號 | 頁的編號 | 相對位置 ]
優點:有paging和segmentation的好處
缺點:實作成本高,存取效能差
會產生internal fragmentation
…………………
fragmenation
internal fragmenation(內部碎片):
在程式的最後一個頁的資料可能無法佔滿一個頁框,在一個頁框內部所浪費的空間
external fragmenation(外部碎片):
主記憶體單元在執行過程會進行配置與回收空間,會形成一些很小的空間無法放置任何一個段,即為此空間
虛擬記憶體的動態位址轉換方式
常見有三種做法:
direct mapping(直接對映):效能太差
把block mapping table放在主記憶體中
associative mapping(關聯對映):成本太高
把block mapping table放在關聯記憶體中
combine associative/direct mapping(組合對映)
使用較小的關聯記憶體存放一小部份的block mapping table
ps:此關聯記憶體稱為TLB(translation lookaside buffer,轉換緩衝區)
……………………………………………….
取代演算法的實作
虛擬記憶體的失誤需付出極大的失誤代價,因此取代策略較重要
演算法主要的考量需要盡量降低失誤率
常用演算法有:
LRU(least recently used,最近罕用)
FIFO(first in first out,先進先出)
NRU(not recently used,最近不用)LRU
設有0到2^n-1個block,越大的block表示存取時間越久,需要取代時則選最久的block
可配合存取局部性,讓失誤率減低
hit時,需將小於該block值+1,以及該block本身設為0
miss時,新進入的block設為0,其他所有block都+1
不易製作且成本高
ex:
設有4個,進入順序為32464721,則4,2被hit,hit ratios為2/8
| 3 | 2 | 4 | 6 | 4 | 7 | 2 | 1 | |
| 3 | 3 | 3 | 2 | 6 | 4 | |||
| 2 | 3 | 2 | 2 | 6 | 4 | 7 | ||
| 1 | 3 | 2 | 4 | 6 | 4 | 7 | 2 | |
| 0 | 3 | 2 | 4 | 6 | 4 | 7 | 2 | 1 |
FIFO
設有0到2^n-1個block,越大的block表示進入的時間越早,需要取代時則選最早的block
hit時,不需動作
miss時,將新進的block設為0,並將其他block都+1
成本較低
NRU
每個block會使用reference bit(存取位元)與modify bit(修改位元)
可配合存取局部性,讓失誤率減低,易製作且成本低………………………………………………
page的大小
會影響主記憶的空間使用效率,
較小則internal fragmenation會較少,page mapping table會較大
較大則internal fragmenation會較大,page mapping table會較小
page太大或太小會使失誤率變高
ps:實際設計中,採用pageing或pageing/segmentation的虛擬記憶體,hit rate可達99.99%~99.9999%
設程式大小=s,頁的大小=p,頁對照表中每一個欄位的大小=e,則
內部碎片平均=p/2,程式的頁對照表=s*e/p,所以程式的空間浪費=p/2+s*e/p
要讓空間浪費最小,可將p一階微分並另結果為0得1/2-s*e/p^2=0,所以p=sqrt(2*s*e)
平均存取時間
公式=計算位址時間+hit存取時間+miss存取時間
計算位址時間:透過TLB或是page table將虛擬位址轉換成實際位址所需的時間
公式=ratio of TLB*TLB access time+(1-hit ratio of TLB)*memory access time
hit存取時間:可以在主記憶單元存取到資料所需的時間
公式=(1-page fault rate)*memory access time
miss存取時間:發生page fault進行處理所需的時間
公式=page fault rate*average page-fault service time
ex:
設TLB access time=20ns,memory access time=100ns,average page-fault service time=25ms,hit ratio of TLB=98%,page fault rate=0.0001%
所以計算位址時間=0.98*20ns+0.02*100ns=21.6ns,hit存取時間=99.9999%*100ns=99.9999ns,miss存取時間=0.0001%*25ms=25ns
而平均存取時間=21.6ns+99.9999ns+25ns約=146.6ns