操作系統中的虛擬內存技術及其實現代碼，操作系統虛擬內存

操作系統中的虛擬內存技術及其實現代碼，操作系統虛擬內存

虛擬內存是現代操作系統普遍使用的一種技術。

虛擬內存的基本思想是，每個進程有用獨立的邏輯地址空間，內存被分為大小相等的多個塊,稱為頁(Page)。每個頁都是一段連續的地址。對於進程來看，邏輯上貌似有很多內存空間，其中一部分對應物理內存上的一塊(稱為頁框 page frame，通常頁和頁框大小相等)，還有一些沒加載在內存中的對應在硬盤上。通過引入進程的邏輯地址，把進程地址空間與實際存儲空間分離，增加存儲管理的靈活性。

地址空間和存儲空間兩個基本概念的定義如下：

地址空間：將源程序經過編譯後得到的目標程序，存在於它所限定的地址范圍內，這個范圍稱為地址空間。地址空間是邏輯地址的集合。

存儲空間：指主存中一系列存儲信息的物理單元的集合，這些單元的編號稱為物理地址存儲空間是物理地址的集合。

由此衍生出的管理方式有三種：
頁式存儲管理、段式存儲管理和段頁式存儲管理。這裡主要介紹頁式存儲。

在頁式系統中進程建立時，操作系統為進程中所有的頁分配頁框。當進程撤銷時收回所有分配給它的頁框。在程序的運行期間，如果允許進程動態地申請空間，操作系統還要為進程申請的空間分配物理頁框。操作系統為了完成這些功能，必須記錄系統內存中實際的頁框使用情況。操作系統還要在進程切換時，正確地切換兩個不同的進程地址空間到物理內存空間的映射。為了理解操作系統如何完成這些需求，我們先理解頁表技術。先看張圖，轉載自51CTO：

頁表中的條目被稱為頁表項（page table entry），一個頁表項負責記錄一段虛擬地址到物理地址的映射關系。

既然頁表是存儲在內存中的，那麼程序每次完成一次內存讀取時都至少會訪問內存兩次，相比於不使用MMU（MMU是Memory Management Unit的縮寫，它代表集成在CPU內部的一個硬件邏輯單元，主要作用是給CPU提供從虛擬地址向物理地址轉換的功能，從硬件上給軟件提供一種內存保護的機制）時的一次內存訪問，效率被大大降低了，如果所使用的內存的性能比較差的話，這種效率的降低將會更明顯。因此，如何在發揮MMU優勢的同時使系統消耗盡量減小，就成為了一個亟待解決的問題。

於是，TLB產生了。TLB是什麼呢？我們叫它轉換旁路緩沖器，它實際上是MMU中臨時存放轉換數據的一組重定位寄存器。既然TLB本質上是一組寄存器，那麼不難理解，相比於訪問內存中的頁表，訪問TLB的速度要快很多。因此如果頁表的內容全部存放於TLB中，就可以解決訪問效率的問題了。

然而，由於制造成本等諸多限制，所有頁表都存儲在TLB中幾乎是不可能的。這樣一來，我們只能通過在有限容量的TLB中存儲一部分最常用的頁表，從而在一定程度上提高MMU的工作效率。

這一方法能夠產生效果的理論依據叫做存儲器訪問的局部性原理。它的意思是說，程序在執行過程中訪問與當前位置臨近的代碼的概率更高一些。因此，從理論上我們可以說，TLB中存儲了當前時間段需要使用的大多數頁表項，所以可以在很大程度上提高MMU的運行效率。

我們這裡所用的是二級頁表的技術，何為二級頁表，即是MMU采用二級查表的方法，即首先由虛擬地址索引出第一張表的某一段內容，然後再根據這段內容搜索第二張表，最後才能確定物理地址。這裡的第一張表，我們叫它一級頁表，第二張表被稱為是二級頁表。采用二級查表法的主要目的是減小頁表自身占據的內存空間，但缺點是進一步降低了內存的尋址效率。

好了，前情介紹完畢，下面上干貨，用哈佛大學開發的用於教學的OS161來實現VM，OS161基於MIP-I hardware。

代碼位於github上：https://github.com/tian-jiang/OS161-VirtualMemory

首先看一段代碼，arch/mips/include/vm.h，物理內存的分配定義在此

/*
 * MIPS-I hardwired memory layout:
 *    0xc0000000 - 0xffffffff   kseg2 (kernel, tlb-mapped)
 *    0xa0000000 - 0xbfffffff   kseg1 (kernel, unmapped, uncached)
 *    0x80000000 - 0x9fffffff   kseg0 (kernel, unmapped, cached)
 *    0x00000000 - 0x7fffffff   kuseg (user, tlb-mapped)
 *
 * (mips32 is a little different)
 */

#define MIPS_KUSEG  0x00000000
#define MIPS_KSEG0  0x80000000
#define MIPS_KSEG1  0xa0000000
#define MIPS_KSEG2  0xc0000000

內存的分配用圖表示如下

這張圖展示了在OS161中物理內存的分配. 

讓我們從頭開始：man.c

1     /* Early initialization. */
2     ram_bootstrap();
3         .......
4 
5     /* Late phase of initialization. */
6     vm_bootstrap();
7         ........

在操作系統啟動的時候，調用raw_bootstrap()以及vm_bootstrap()來啟動vm管理模塊。那麼這兩個函數是在哪裡定義和使用的呢，我們接著看下面的代碼。

include/vm.h和arch/mips/include/vm.h

    /* Initialization function */
void vm_bootstrap(void);

/*
 * Interface to the low-level module that looks after the amount of
 * physical memory we have.
 *
 * ram_getsize returns the lowest valid physical address, and one past
 * the highest valid physical address. (Both are page-aligned.) This
 * is the memory that is available for use during operation, and
 * excludes the memory the kernel is loaded into and memory that is
 * grabbed in the very early stages of bootup.
 *
 * ram_stealmem can be used before ram_getsize is called to allocate
 * memory that cannot be freed later. This is intended for use early
 * in bootup before VM initialization is complete.
 */

void ram_bootstrap(void);
paddr_t ram_stealmem(unsigned long npages);
void ram_getsize(paddr_t *lo, paddr_t *hi);

這兩個function是定義在這裡的，那麼這兩個function又是干什麼事情的呢

vaddr_t firstfree;   /* first free virtual address; set by start.S */

static paddr_t firstpaddr;  /* address of first free physical page */
static paddr_t lastpaddr;   /* one past end of last free physical page */

/*
 * Called very early in system boot to figure out how much physical
 * RAM is available.
 */
void
ram_bootstrap(void)
{
    size_t ramsize;
    
    /* Get size of RAM. */
    ramsize = mainbus_ramsize();

    /*
     * This is the same as the last physical address, as long as
     * we have less than 508 megabytes of memory. If we had more,
     * various annoying properties of the MIPS architecture would
     * force the RAM to be discontiguous. This is not a case we 
     * are going to worry about.
     */
    if (ramsize > 508*1024*1024) {
        ramsize = 508*1024*1024;
    }

    lastpaddr = ramsize;

    /* 
     * Get first free virtual address from where start.S saved it.
     * Convert to physical address.
     */
    firstpaddr = firstfree - MIPS_KSEG0;

    kprintf("%uk physical memory available\n", 
        (lastpaddr-firstpaddr)/1024);
}

/*
 * Initialise the frame table
 */
void
vm_bootstrap(void)
{
    frametable_bootstrap();
}

/*
 * Make variables static to prevent it from other file's accessing
 */
static struct frame_table_entry *frame_table;
static paddr_t frametop, freeframe;

/*
 * initialise frame table
 */
void
frametable_bootstrap(void)
{
    struct frame_table_entry *p;
    paddr_t firsta, lasta, paddr;
    unsigned long framenum, entry_num, frame_table_size, i;
    
    // get the useable range of physical memory
    ram_getsize(&firsta, &lasta);
    KASSERT((firsta & PAGE_FRAME) == firsta);
    KASSERT((lasta & PAGE_FRAME) == lasta);
    
    framenum = (lasta - firsta) / PAGE_SIZE;
    
    // calculate the size of the whole framemap
    frame_table_size = framenum * sizeof(struct frame_table_entry);
    frame_table_size = ROUNDUP(frame_table_size, PAGE_SIZE);
    entry_num = frame_table_size / PAGE_SIZE;
    KASSERT((frame_table_size & PAGE_FRAME) == frame_table_size);
    
    frametop = firsta;
    freeframe = firsta + frame_table_size;
    
    if (freeframe >= lasta) {
        // This is impossible for most of the time
        panic("vm: framemap consume physical memory?\n");
    }
    
    // keep the frame state in the top of the useable range of physical memory
    // the free frame page address started from the end of the frame map
    frame_table = (struct frame_table_entry *) PADDR_TO_KVADDR(firsta);
    
    // Initialise the frame list, each entry corrsponding to a frame,
    // and each entry stores the address of the next free frame.
    // If the next frame address of this entry equals zero, means this current frame is allocated
    p = frame_table;
    for (i = 0; i < framenum-1; i++) {
        if (i < entry_num) {
            p->next_freeframe = 0;
            p += 1;
            continue;
        }
        paddr = frametop + (i+1) * PAGE_SIZE;
        p->next_freeframe = paddr;
        p += 1;
    }
}

struct frame_table_entry {
    // address of next free frame
    size_t          next_freeframe;
};

raw_bootstrap是系統初始化時用來查看有多少物理內存可以使用的。而vm_bootstrap只是簡單的調用了frametable_bootstrap()，而frametable_bootstrap()則是將能用的物理內存分頁，每頁大小為4K，然後保存一個記錄空白頁的linked list在內存中，從free的內存的頂部開始存放，但是在存放之前，先要算出需要多少空間來存放這個frame table。所以代碼的前段在計算frame table的大小，後面則是初始化frame table這個linked list。因為初始化的時候都是空的，所以直接指向下一個page的地址即可。

操作系統的vm初始化到此完畢。那vm是怎麼使用的呢，請看下面