Virtual Memory
Ostep Virtual Memory
The Abstraction: Address Space
Multiprogramming and Time sharing
- 為了避免process之間的互相等待,因此從signalprogramming進步到multiprogramming,但在效能提升的同時,如和避免process之間互相干擾成了另一個問題
Address Space
- Address space是process的虛擬記憶體,每個process都具備自己的address space
- process的address space包含運行程序的所有記憶體狀態,比如code必須在記憶體中,因為他們在因為他們在address space裡
- 當程式運行時利用stack保存函數調用訊息,分配空間給局部變量
- 利用heap管理動態分配的以及用戶管理的記憶體
虛擬Memory的目標
- transparency: process感知不到memory被虛擬化的事實,反而認為自己擁有自己的private physical memory
- efficiency: os追求虛擬化盡可能的effiecnt,包括在時間和空間上.在實現高效率虛擬memory時,os不得不依靠硬體
- protection: os應該確保process受到保護不會受到其他process影響,os本身也不會受到任何process影響.當一個prcess執行load,store或指令提取時,不應該用任何方式訪問或影響其他prcess以及os本身的memory
你看到所有地址都不是真的
- 使用C語言打應出來的地址是虛擬地址,並且將由os轉換成物理地址
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
printf("location of code: %p\n", (void *)main);
printf("location of heap: %p\n", (void *)malloc(1));
int x = 3;
printf("location of stack: %p\n", (void *)&x);
}
Mechanisms: Address Translation
- 實現CPU虛擬化時,我們遵循的準則被稱為Limited Direct Execution (LDE)
- LDE原則是os盡量不干擾CPU執行process,只有在關鍵時才及時介入(interposing)來保持對硬體得控制
- 利用基於硬體的地址轉換(hardware-based address translation)又稱address translation 來保證高效靈活的虛擬化
- 使用address translation,硬體對每次memory訪問進行處理都將指令中的victual address轉為十集的physical address來實現受限執行
- 因此每次memory訪問時,硬體都會進行address translation,將應用程式的memory引用重定位到memory實際位置
Example
- 編寫一段C語言程式碼
int main() {
int x;
x = x + 3;
}
- 使用otool來反編譯程式成ASM code
0000000100003f90 ldr w8, [sp, #0xc] # 載入x變量
0000000100003f94 add w8, w8, #0x3 # 將x變量加3
0000000100003f98 str w8, [sp, #0xc] # 將結果存回x變量
使用匯編的角度來看
- 從地址3f90獲得指令
- 執行指令(從地址0xc載入數據)
- 從地址3f94獲得指令
- 執行指令(沒有memory訪問)
- 從地址3f98獲得指令
- 執行指令(將結果存回0xc地址)
使用程式角度
- 他的address space從0開始到16KB結束,所有的memory引用都在這範圍內
- 然後虛擬memory來說,os希望將這些位址放在物理memory的不同地方,不一定從地址0開始,那我們該如何重定向這個process以及對該process保持transparent
- 底下圖片說明process的address space被放入物理memory後可能的樣子,從圖可以看到操作系統第一塊物理memory留給自己,並將上述地址空間重店味道從32KB開始的物理memory地址,剩下的兩塊memory空閒
Dynamic Address Translation
- CPU需要兩個硬體Register分別是base register和bound register(也稱為limit register)
- base register: os決定process在其裡memory中的實際address,並將起始的address記錄在base register中
- bound register: os決定process在其裡memory中的結束address,並將結束的address記錄在bound register中
- 當CPU訪問memory時,會將虛擬地址與base register和bound register進行比較
- 如果虛擬地址小於base register或大於bound register,則會報錯
- 如果虛擬地址在base register和bound register之間,則將虛擬地址加上base register的值來獲得物理地址
- 由上述可以得出一個公式
Bound Register作用
-
bound register是為了確保process不會超過其address space的範圍,如果process試圖訪問超出其address space的memory,則會報錯
-
進而隔離當前process和其他process,確保process之間不會互相干擾
-
process中使用德的memory引用都是virtual address,硬體接下來將vitrual address加上base register的值來獲得physical address
-
底下簡化先前的asm code中指令的位址
- 簡化0000000100003f90成128(數字代替表達,不考慮轉換以及值是否正確)
128 ldr w8, [sp, #0xc] # 載入x變量
流程
- 當PC首先被設置為128後
- 硬體需要獲得這條指令時,先將這個值(128)加上base register的值32KB(32768)來獲得實際的物理位址(32896)
- process從virtual address 15KB的加載,處理器同樣需樣virtual address 15KB加上base register的值32KB(32768)來獲得物理位址(48768)
- 有了物理位址後,處理器可以從物理memory中讀取數據
- 將虛擬地址轉換為物理地址的過程稱為address translation技術ㄓ,而當這種address translation在運行時發生,並且我們甚至可以在process運行後改變其address space,這種技術被稱為dynamic address translation
Dynamic Address Translation要求
- 硬體必須提供base and bound registers,因此每個CPU的Memory Management Unit (MMU)都必須額外擁有這兩個register
- 硬體提供一些privileged指令,只有在kernel模式下指行,其作用為修改base register和bound register的值
- 當用戶嘗試非法訪問memory時(越界訪問),CPU必須能夠產生異常(exception)並安排os的exception handler來處理這個問題
硬體要求 | 解釋 |
---|---|
特權模式 | 需要,以防用戶模式的process執行特權操作 |
base/bound register | 每個CPU需要一對register來支持地址轉換和bound檢查 |
能夠轉換virtual address並檢查是否越界 | 電路完成轉換和檢查bound |
優改base/bound register的特權指令 | 再讓用戶程式運行之前,os必須能夠設定值 |
註冊異常處理的特權指令 | os必須能夠告訴硬體,當異常發生時執行那些程式 |
觸發異常 | 如果process試圖使用特權指令或越界訪聞 |
OS: The New Problem
- 為了支持dynamic address tanslation,硬體支持和操作系統管理結合在一起,實現了一個簡單的虛擬內存系統,因此在關鍵時刻os需要介入,已實現base bound方式的虛擬Memory
- 當process創建時,os必須找到足夠的memory address,而整個操作都會圍繞在Free list上
- 可以把整個物理Memory想像成一組抽屜,標記了空閑或以使用,當new process創建時ㄝos檢索這一個抽屜,為新的address space找到位址,並標記成已被使用
- 當process終止時,os也必須做一些工作,回收他的所有Memory,給其他process使用,當process終止時,os將會把這些Memory放回空閑列表,並根據需要清除相關的數據結構
- 在context switch時,os必須執行一些額外的工作,由於每個CPU都只有一組base and bound register,因此os必須保存和恢復base和bound register
- 當process停止時(即終止運行),os可以改變其地址空間的物理位置
- 要移動process的address space步驟
- os讓process停止運行
- 將address space拷貝到新的位置
- 更新保存的base register(在process結構中)
- 指向新位置
- 當process恢復執行時,其(新)base register就會被恢復,顯然他的指令和數據都在新的Memory位址
- os必須提供exception handler,或要一些function,當process越界訪問Memory時,CPU會觸發異常,os必須要能夠終止這些process
操作系統的要求 | 解釋 |
---|---|
內存管理 | 需要為新process分配Memory |
從終止的process回收Memory | |
一般通過free list來管理Memory | |
base bound 管理 | 必須在context switch時正確設置base和bound register |
異常處理 | 當異常發生時執行的程式,可能的動作是終止犯錯的process |
補充: FreeList
基於時間線展示硬體和os的互動
Boot
OS @boot (kernel mode) | Hardwarre |
---|---|
initialize trap table | |
remember address of... | |
system call handler | |
timer handler | |
illegal mem-access handler | |
illegal instruction handler | |
Run main() | |
Execute return from main | |
start interrupt timer | |
start timer;interrupt after | |
initialize process table | |
initialize free list |
Run
OS @run (kernel mode) | Hardwarre | Program (user mode) |
---|---|---|
To start processA: | ||
1. allocate entry in process table | ||
2. alloc memory for process | ||
3. set base and bound registers | ||
4. return-from-trap (into A) | ||
restore registers of A move to user mode jump to A's(initial) PC | ||
Process A runs Fetch instruction | ||
translate virtual address perform fetch | ||
Execute instruction | ||
if explicit load sotre | ||
1. ensure address is legal | ||
2. translate virtual address | ||
3.perform load and store | ||
Process A runs | ||
Timer interrupt | ||
move to kernel mode | ||
jump to handler | ||
Hnadle timer | ||
1. decide: stop A, run B | ||
2. call switch() routine | ||
3. save register(A) to process-struct(A) (include base and bound registrer) | ||
4. restore register(B) from process-struct(B) (include base and bound registrer) | ||
5. return-from-trap (into B) | ||
restore register of B | ||
move to user mode | ||
jump to B's PC | ||
Process B runs Execute bad load | ||
Load is out-of-bounds | ||
move to kernel mode | ||
jump to trap handler | ||
Handle the trap | ||
decide to kill process B | ||
deallocate B's memory | ||
free B's entry in process table |
目前問題
- 簡單的Dynamic Address translation能夠支持Process transparent但還有問題無法解決
- 重定位process使用了從 到 的物理地址,但由於process的stack和heap並不是很大,導致這塊Memory中大量的空間被浪費
- 這種浪費稱為intrenal fragmentation
internal fragmentation
- 指的是已經分配的Memory單元內部有未使用的空間(即fragmentation).造成了浪費,
- 因為這些fragmentation無法被其他process使用(不足其他process的需求)
- 在我們當前的方式中,即使有足夠的物理Memory容納更多process,但我們目前要求將adress spoace放在固定大小的抽屜,因此出現了internal fragmentation
Segmentation
- 目前的情況都是將所有的process載入到Memory中,並且使用base/bound register來讓os將不同的process進行address translation到不同的physical address,但這樣會發現在stack和heap間存在很大的空閑區塊
Segmentation 范化的base/bound
- 在MMU中引入不只base/bound register,而是給address space內的每個segment一對,一個segment只是address space中的連續定長區域,典型的segment有3個部分
- code
- stack
- heap
- segment讓os將不同的segment放到不同的physical address,從而避免了虛擬address space中未使用但佔用physical memory的問題
segment | base | bound |
---|---|---|
code | 32KB | 2KB |
heap | 34KB | 2KB |
stack | 28KB | 2KB |
-
假設現在引用virtual address為100的地址,MMU將base加上偏移量得到實際的physical address , 然後再檢查該地址是否在bound內(這邊的地址指的不是實際physical address,而是vitrualaddress 的地址) , 發現再bound內部後就發起調用
-
再看到圖1的範例,假設現在要引用的是heap的地址,假設直接將4200加上stack的base 34KB的話會是錯的,因為4200的基底是從4KB(4096)開始,因此應該是 , 然後再檢查該地址是否在bound內,確認在bound內後再將 得到實際的physical address
-
當我們試圖訪問超過bound的address時,就會發生segmentation violation 或是 segmentation fault
怎麼知道調用的是那個Segment
- 由圖中可以知道前兩位代表的是告hardware説調用的是哪一個段(stack,heap,code),剩下的12位則是偏移量
- 因此先使用前兩位找到相對應的segment後再使用偏移量+基底address就可以獲得實際的物理位址
- 現在可以將上述所做轉換成程式碼的形式,也因為偏移量簡化了對bound的判斷,因此只需要檢查偏移量是否小於bound而非大於bound的非法地址
#define SEG_MASK 0x3000
#define SEG_SHIFT 12
#define OFFSET_MASK 0xFFFF
// get top 2 bits of 14-bit
Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
// get offset
Offset = VirtuaalAddress & OFFSET_MASK
if (Offset >= Bounds[Segment])
RaiseException(PROTECETION_FAULT)
else
PhysAddr = Base[Segment] + Offset
Register = AccessMemory(PhysAddr)
- 這邊只使用兩個段是因為,假設使用3個段表示的話,有可能會造成其中一個被浪費,因此有些系統會將heap和stack當成一個段,然後用一bit來做標示
- 在implicit方式中,硬體功過address產生的方式來確定段
- 例如: 如果地址由pc產生,即為指令獲取,則位址在code段, 假設基於stack或base指針則一定在stack段,其他地址在heap段
How about Stack
-
在上圖中可以看到stack被重定位到28KB的地方,但和其他不同的地方在於stack是反向增長的,也就是始於28KB增長到26KB,相對應的虛擬地址也是從16KB到14KB
-
因此硬體需要額外已1bit來區分是否為反相增長(1代表正向,0代表反向) |segment|base|bound|reverse| |-------|----|-----|-------| |code|32KB|2KB|1| |heap|34KB|2KB|1| |stack|28KB|2KB|0|
-
因為反向的緣故,在計算address transtaltion時會有所不同
- 假設現在要訪問的是15KB的虛擬地址,對應到的物理地址為27KB
1, 先將15KB轉換成2進制形式 11 1100 0000 0000,利用前兩位來指定段,並且計算出偏移量為3KB 2. 為了得到正確的偏移量,因此要將現在的偏移量減去最大的段地址(即為bound的上界地址)
- 此時再將偏移量加上base address得到實際的physical address
- 進行bound檢查,確保偏移量的 絕對值 小於sagment的大小
Support Shared
- 為了節省Memory,有時會在address space之間共向segment是有用的行為,因此硬體會需要新增protecetion bit來標示是否能夠對segment進行RW
- 將code segment標示為只讀時,可以讓他被多個process共享但不會破壞process 間的隔離
segment | base | bound | reverse | protect |
---|---|---|---|---|
code | 32KB | 2KB | 1 | Read-Excute |
heap | 34KB | 2KB | 1 | Read-Write |
stack | 28KB | 2KB | 0 | Read-Write |
- 有了protection bit後前面虛擬地址是否越界外,還需要檢查特定的訪問是否允許,如果從事非法訪問hard會拋出異常並且讓os來handle這些error
操作系統支持
- 現在當系統運行時,address space會被不同的segment重定位到physical memory中,相比於之前使用base/bound的方法節省了不少的physical memory
- 具體來說 stack和heap不需要再分配physical memory,讓我們能將更多的address space放入 physical memory
遇到的問題
- os在進行Context switch 時該做些什麼
- 各個segment register中的內容必須保存和恢復,因為每個process都有自己獨立的vritual address space, 因此os必須在process運行前確保被正確設置
- physical address 中充滿了許多free space的小洞,這些洞很難再分配給新的segment或是擴充原有的segment,這類的問題被稱為(external fragmentation)
- 第一種解法是compact physical memory
- os 將所有的process終止後,將數據複製到連續的memory區域中,並且改變他們的segment register內的值,指向新的物理地址,從而獲得足夠大的連續空間
- 但這樣造成的問題是成本很高,因為copy segment是memory intensive(密集),因此會佔用大量的processor(處理器)時間
- 第二種解法是利用 free-space management算法,試圖保留較大的memory區塊來進行分配