Lab 4: Preemptive Multitasking tags: mit 6.828, os 概述本文是lab4的實驗報告，主要圍繞進程相關概念進行介紹。主要將四個知識點： 1. 開啟多處理器。現代處理器一般都是多核的，這樣每個CPU能同時運行不同進程，實現並行。需要用鎖解決多CPU的 ...

Lab 4: Preemptive Multitasking

tags: mit-6.828, os

概述

本文是lab4的實驗報告，主要圍繞進程相關概念進行介紹。主要將四個知識點：

開啟多處理器。現代處理器一般都是多核的，這樣每個CPU能同時運行不同進程，實現並行。需要用鎖解決多CPU的競爭。
實現進程調度演算法。
實現寫時拷貝fork（進程創建）。
實現進程間通信。

Part A: Multiprocessor Support and Cooperative Multitasking

該部分做三件事：

使JOS支持多CPU
實現系統調用允許普通進程創建新的進程
實現協作式進程調度

Multiprocessor Support

我們將使JOS支持"symmetric multiprocessing" (SMP)，這是一種所有CPU共用系統資源的多處理器模式。在啟動階段這些CPU將被分為兩類：

啟動CPU（BSP）：負責初始化系統，啟動操作系統。
應用CPU（AP）：操作系統啟動後由BSP激活。
哪一個CPU是BSP由硬體和BISO決定，到目前位置所有JOS代碼都運行在BSP上。
在SMP系統中，每個CPU都有一個對應的local APIC（LAPIC），負責傳遞中斷。CPU通過記憶體映射IO(MMIO)訪問它對應的APIC，這樣就能通過訪問記憶體達到訪問設備寄存器的目的。LAPIC從物理地址0xFE000000開始，JOS將通過MMIOBASE虛擬地址訪問該物理地址。

Exercise 1

實現kern/pmap.c中的mmio_map_region()。
解決：可以參照boot_map_region()

void *
mmio_map_region(physaddr_t pa, size_t size)
{
    // Where to start the next region.  Initially, this is the
    // beginning of the MMIO region.  Because this is static, its
    // value will be preserved between calls to mmio_map_region
    // (just like nextfree in boot_alloc).
    static uintptr_t base = MMIOBASE;

    // Reserve size bytes of virtual memory starting at base and
    // map physical pages [pa,pa+size) to virtual addresses
    // [base,base+size).  Since this is device memory and not
    // regular DRAM, you'll have to tell the CPU that it isn't
    // safe to cache access to this memory.  Luckily, the page
    // tables provide bits for this purpose; simply create the
    // mapping with PTE_PCD|PTE_PWT (cache-disable and
    // write-through) in addition to PTE_W.  (If you're interested
    // in more details on this, see section 10.5 of IA32 volume
    // 3A.)
    //
    // Be sure to round size up to a multiple of PGSIZE and to
    // handle if this reservation would overflow MMIOLIM (it's
    // okay to simply panic if this happens).
    //
    // Hint: The staff solution uses boot_map_region.
    //
    // Your code here:
    size = ROUNDUP(pa+size, PGSIZE);
    pa = ROUNDDOWN(pa, PGSIZE);
    size -= pa;
    if (base+size >= MMIOLIM) panic("not enough memory");
    boot_map_region(kern_pgdir, base, size, pa, PTE_PCD|PTE_PWT|PTE_W);
    base += size;
    return (void*) (base - size);
}

Application Processor Bootstrap

在啟動AP之前，BSP需要搜集多處理器的信息，比如總共有多少CPU，它們的LAPIC ID以及LAPIC MMIO地址。mp_init()函數從BIOS中讀取這些信息。具體代碼在mp_init()中，該函數會在進入內核後被i386_init()調用，主要作用就是讀取mp configuration table中保存的CPU信息，初始化cpus數組，ncpu（總共多少可用CPU），bootcpu指針（指向BSP對應的CpuInfo結構）。

真正啟動AP的是在boot_aps()中，該函數遍歷cpus數組，一個接一個啟動所有的AP，當一個AP啟動後會執行kern/mpentry.S中的代碼，然後跳轉到mp_main()中，該函數為當前AP設置GDT，TTS，最後設置cpus數組中當前CPU對應的結構的cpu_status為CPU_STARTED。更多關於SMP的知識可以參考：https://pdos.csail.mit.edu/6.828/2018/readings/ia32/MPspec.pdf和https://wenku.baidu.com/view/615ea3c6aa00b52acfc7ca97.html

Per-CPU State and Initialization

JOS使用struct CpuInfo結構來記錄CPU的信息：

struct CpuInfo {
    uint8_t cpu_id;                 // Local APIC ID; index into cpus[] below
    volatile unsigned cpu_status;   // The status of the CPU
    struct Env *cpu_env;            // The currently-running environment.
    struct Taskstate cpu_ts;        // Used by x86 to find stack for interrupt
};

cpunum()總是返回調用它的CPU的ID，巨集thiscpu提供了更加方便的方式獲取當前代碼所在的CPU對應的CpuInfo結構。
每個CPU如下信息是當前CPU私有的：

內核棧：內核代碼中的數組percpu_kstacks[NCPU][KSTKSIZE]為每個CPU都保留了KSTKSIZE大小的內核棧。從內核線性地址空間看CPU 0的棧從KSTACKTOP開始，CPU 1的內核棧將從CPU 0棧後面KSTKGAP位元組處開始，以此類推，參見inc/memlayout.h。
TSS和TSS描述符：每個CPU都需要單獨的TSS和TSS描述符來指定該CPU對應的內核棧。
進程結構指針：每個CPU都會獨立運行一個進程的代碼，所以需要Env指針。
系統寄存器：比如cr3, gdt, ltr這些寄存器都是每個CPU私有的，每個CPU都需要單獨設置。

到目前為止CpuInfo和Env關係可以總結如下： Env和CpuInfo關係

Exercise 3：

修改mem_init_mp()，將內核棧線性地址映射到percpu_kstacks處的物理地址處。
解決：本質上是修改kern_pdir指向的頁目錄和頁表，按照inc/memlayout.h中的結構進行映射即可。

static void
mem_init_mp(void)
{
    // Map per-CPU stacks starting at KSTACKTOP, for up to 'NCPU' CPUs.
    //
    // For CPU i, use the physical memory that 'percpu_kstacks[i]' refers
    // to as its kernel stack. CPU i's kernel stack grows down from virtual
    // address kstacktop_i = KSTACKTOP - i * (KSTKSIZE + KSTKGAP), and is
    // divided into two pieces, just like the single stack you set up in
    // mem_init:
    //     * [kstacktop_i - KSTKSIZE, kstacktop_i)
    //          -- backed by physical memory
    //     * [kstacktop_i - (KSTKSIZE + KSTKGAP), kstacktop_i - KSTKSIZE)
    //          -- not backed; so if the kernel overflows its stack,
    //             it will fault rather than overwrite another CPU's stack.
    //             Known as a "guard page".
    //     Permissions: kernel RW, user NONE
    //
    // LAB 4: Your code here:
    for (int i = 0; i < NCPU; i++) {
        boot_map_region(kern_pgdir, 
            KSTACKTOP - KSTKSIZE - i * (KSTKSIZE + KSTKGAP), 
            KSTKSIZE, 
            PADDR(percpu_kstacks[i]), 
            PTE_W);
    }
}

Locking

目前我們已經有多個CPU同時在執行內核代碼了，我們必須要處理競爭條件。最簡單粗暴的辦法就是使用"big kernel lock"，"big kernel lock"是一個全局鎖，進程從用戶態進入內核後獲取該鎖，退出內核釋放該鎖。這樣就能保證只有一個CPU在執行內核代碼，但缺點也很明顯就是一個CPU在執行內核代碼時，另一個CPU如果也想進入內核，就會處於等待的狀態。
鎖的數據結構在kern/spinlock.h中:

struct spinlock {
    unsigned locked;       // Is the lock held?
};

獲取鎖，釋放鎖的操作在kern/spinlock.c中：

void
spin_lock(struct spinlock *lk)
{
    // The xchg is atomic.
    // It also serializes, so that reads after acquire are not
    // reordered before it. 
    while (xchg(&lk->locked, 1) != 0)           //原理見：https://pdos.csail.mit.edu/6.828/2018/xv6/book-rev11.pdf  chapter 4
        asm volatile ("pause");
}

void
spin_unlock(struct spinlock *lk)
{
    // The xchg instruction is atomic (i.e. uses the "lock" prefix) with
    // respect to any other instruction which references the same memory.
    // x86 CPUs will not reorder loads/stores across locked instructions
    // (vol 3, 8.2.2). Because xchg() is implemented using asm volatile,
    // gcc will not reorder C statements across the xchg.
    xchg(&lk->locked, 0);
}

這是一種"spin-locks"。對於spin_lock()獲取鎖的操作，使用xchg這個原子操作，xchg()封裝了該指令，交換lk->locked和1的值，並將lk-locked原來的值返回。如果lk-locked原來的值不等於0，說明該鎖已經被別的CPU申請了，繼續執行while迴圈吧。對於spin_unlock()釋放鎖的操作，直接將lk->locked置為0，表明我已經用完了，這個鎖可以被別人獲取了。
有了獲取鎖和釋放鎖的函數，我們看下哪些地方需要加鎖，和釋放鎖：

i386_init()中，BSP喚醒其它AP前需要獲取內核鎖。
mp_main()中，AP需要在執行sched_yield()前獲取內核鎖。
trap()中，需要獲取內核鎖，因為這是用戶態進入內核的唯一入口。
env_run()中，需要釋放內核鎖，因為該函數使用iret指令，從內核返回用戶態。

Exercise 5

在前面提的位置添加加鎖和釋放鎖的代碼。比較簡單就不貼代碼了。

Round-Robin Scheduling

現要JOS內核需要讓CPU能在進程之間切換。目前先實現一個非搶占式的進程調度，需要當前進程主動讓出CPU，其他進程才有機會在當前CPU運行。具體實現如下：

實現sched_yield()，該函數選擇一個新的進程運行，從當前正在運行進程對應的Env結構下一個位置開始迴圈搜索envs數組，找到第一個cpu_status為ENV_RUNNABLE的Env結構，然後調用env_run()在當前CPU運行這個新的進程。
我們需要實現一個新的系統調用sys_yield()，使得用戶程式能在用戶態通知內核，當前進程希望主動讓出CPU給另一個進程。

Exercise 6

實現sched_yield()函數。

void
sched_yield(void)
{
    struct Env *idle;

    // Implement simple round-robin scheduling.
    //
    // Search through 'envs' for an ENV_RUNNABLE environment in
    // circular fashion starting just after the env this CPU was
    // last running.  Switch to the first such environment found.
    //
    // If no envs are runnable, but the environment previously
    // running on this CPU is still ENV_RUNNING, it's okay to
    // choose that environment. Make sure curenv is not null before
    // dereferencing it.
    //
    // Never choose an environment that's currently running on
    // another CPU (env_status == ENV_RUNNING). If there are
    // no runnable environments, simply drop through to the code
    // below to halt the cpu.

    // LAB 4: Your code here.
    int start = 0;
    int j;
    if (curenv) {
        start = ENVX(curenv->env_id) + 1;   //從當前Env結構的後一個開始
    }
    for (int i = 0; i < NENV; i++) {        //遍歷所有Env結構
        j = (start + i) % NENV;
        if (envs[j].env_status == ENV_RUNNABLE) {
            env_run(&envs[j]);
        }
    }
    if (curenv && curenv->env_status == ENV_RUNNING) {      //這是必須的，假設當前只有一個Env，如果沒有這個判斷，那麼這個CPU將會停機
        env_run(curenv);
    }
    // sched_halt never returns
    sched_halt();
}

需要註意：當前CPU在envs數組中找了一圈後沒找到合適的Env去執行，需要重新執行之前運行的進程，否則當前CPU就會進入停機狀態。

System Calls for Environment Creation

儘管現在內核有能力在多進程之前切換，但是僅限於內核創建的用戶進程。目前JOS還沒有提供系統調用，使用戶進程能創建新的進程。
Unix提供fork()系統調用創建新的進程，fork()拷貝父進程的地址空間和寄存器狀態到子進程。父進程從fork()返回的是子進程的進程ID，而子進程從fork()返回的是0。父進程和子進程有獨立的地址空間，任何一方修改了記憶體，不會影響到另一方。
現在需要實現如下系統調用：

sys_exofork()：
創建一個新的進程，用戶地址空間沒有映射，不能運行，寄存器狀態和父環境一致。在父進程中sys_exofork()返回新進程的envid，子進程返回0。
sys_env_set_status：設置一個特定進程的狀態為ENV_RUNNABLE或ENV_NOT_RUNNABLE。
sys_page_alloc：為特定進程分配一個物理頁，映射指定線性地址va到該物理頁。
sys_page_map：拷貝頁表，使指定進程共用當前進程相同的映射關係。本質上是修改特定進程的頁目錄和頁表。
sys_page_unmap：解除頁映射關係。本質上是修改指定用戶環境的頁目錄和頁表。

Exercise 7：

實現上述所有的系統調用：
sys_exofork(void)：

static envid_t
sys_exofork(void)
{
    // Create the new environment with env_alloc(), from kern/env.c.
    // It should be left as env_alloc created it, except that
    // status is set to ENV_NOT_RUNNABLE, and the register set is copied
    // from the current environment -- but tweaked so sys_exofork
    // will appear to return 0.

    // LAB 4: Your code here.
    struct Env *e;
    int ret = env_alloc(&e, curenv->env_id);    //分配一個Env結構
    if (ret < 0) {
        return ret;
    }
    e->env_tf = curenv->env_tf;         //寄存器狀態和當前進程一致
    e->env_status = ENV_NOT_RUNNABLE;   //目前還不能運行
    e->env_tf.tf_regs.reg_eax = 0;      //新的進程從sys_exofork()的返回值應該為0
    return e->env_id;
}

sys_env_set_status(envid_t envid, int status):

static int
sys_env_set_status(envid_t envid, int status)
{
    // Hint: Use the 'envid2env' function from kern/env.c to translate an
    // envid to a struct Env.
    // You should set envid2env's third argument to 1, which will
    // check whether the current environment has permission to set
    // envid's status.
    if (status != ENV_NOT_RUNNABLE && status != ENV_RUNNABLE) return -E_INVAL;

    struct Env *e;
    int ret = envid2env(envid, &e, 1);
    if (ret < 0) {
        return ret;
    }
    e->env_status = status;
    return 0;
}

sys_page_alloc(envid_t envid, void *va, int perm):

static int
sys_page_alloc(envid_t envid, void *va, int perm)
{
    // Hint: This function is a wrapper around page_alloc() and
    //   page_insert() from kern/pmap.c.
    //   Most of the new code you write should be to check the
    //   parameters for correctness.
    //   If page_insert() fails, remember to free the page you
    //   allocated!

    // LAB 4: Your code here.
    struct Env *e;                                  //根據envid找出需要操作的Env結構
    int ret = envid2env(envid, &e, 1);
    if (ret) return ret;    //bad_env

    if ((va >= (void*)UTOP) || (ROUNDDOWN(va, PGSIZE) != va)) return -E_INVAL;      //一系列判定
    int flag = PTE_U | PTE_P;
    if ((perm & flag) != flag) return -E_INVAL;

    struct PageInfo *pg = page_alloc(1);            //分配物理頁
    if (!pg) return -E_NO_MEM;
    ret = page_insert(e->env_pgdir, pg, va, perm);  //建立映射關係
    if (ret) {
        page_free(pg);
        return ret;
    }

    return 0;
}

sys_page_map(envid_t srcenvid, void srcva,envid_t dstenvid, void dstva, int perm):

static int
sys_page_map(envid_t srcenvid, void *srcva,
         envid_t dstenvid, void *dstva, int perm)
{
    // Hint: This function is a wrapper around page_lookup() and
    //   page_insert() from kern/pmap.c.
    //   Again, most of the new code you write should be to check the
    //   parameters for correctness.
    //   Use the third argument to page_lookup() to
    //   check the current permissions on the page.

    // LAB 4: Your code here.
    struct Env *se, *de;
    int ret = envid2env(srcenvid, &se, 1);
    if (ret) return ret;    //bad_env
    ret = envid2env(dstenvid, &de, 1);
    if (ret) return ret;    //bad_env

    //  -E_INVAL if srcva >= UTOP or srcva is not page-aligned,
    //      or dstva >= UTOP or dstva is not page-aligned.
    if (srcva >= (void*)UTOP || dstva >= (void*)UTOP || 
        ROUNDDOWN(srcva,PGSIZE) != srcva || ROUNDDOWN(dstva,PGSIZE) != dstva) 
        return -E_INVAL;

    //  -E_INVAL is srcva is not mapped in srcenvid's address space.
    pte_t *pte;
    struct PageInfo *pg = page_lookup(se->env_pgdir, srcva, &pte);
    if (!pg) return -E_INVAL;

    //  -E_INVAL if perm is inappropriate (see sys_page_alloc).
    int flag = PTE_U|PTE_P;
    if ((perm & flag) != flag) return -E_INVAL;

    //  -E_INVAL if (perm & PTE_W), but srcva is read-only in srcenvid's
    //      address space.
    if (((*pte&PTE_W) == 0) && (perm&PTE_W)) return -E_INVAL;

    //  -E_NO_MEM if there's no memory to allocate any necessary page tables.
    ret = page_insert(de->env_pgdir, pg, dstva, perm);
    return ret;

}

sys_page_unmap(envid_t envid, void *va):

static int
sys_page_unmap(envid_t envid, void *va)
{
    // Hint: This function is a wrapper around page_remove().

    // LAB 4: Your code here.
    struct Env *env;
    int ret = envid2env(envid, &env, 1);
    if (ret) return ret;

    if ((va >= (void*)UTOP) || (ROUNDDOWN(va, PGSIZE) != va)) return -E_INVAL;
    page_remove(env->env_pgdir, va);
    return 0;
}

Part B: Copy-on-Write Fork

實現fork()有多種方式，一種是將父進程的內容全部拷貝一次，這樣的話父進程和子進程就能做到進程隔離，但是這種方式非常耗時，需要在物理記憶體中複製父進程的內容。
另一種方式叫做寫時拷貝的技術(copy on write)，父進程將自己的頁目錄和頁表複製給子進程，這樣父進程和子進程就能訪問相同的內容。只有當一方執行寫操作時，才複製這一物理頁。這樣既能做到地址空間隔離，又能節省了大量的拷貝工作。我畫了個圖來比較這兩種fork方式：非寫時拷貝vs寫時拷貝fork
想要實現寫時拷貝的fork()需要先實現用戶級別的缺頁中斷處理函數。

User-level page fault handling

為了實現用戶級別的頁錯誤處理函數，進程需要註冊頁錯誤處理函數，需要實現一個sys_env_set_pgfault_upcall()系統調用提供支持。

Exercise 8：

實現sys_env_set_pgfault_upcall(envid_t envid, void *func)系統調用。該系統調用為指定的用戶環境設置env_pgfault_upcall。缺頁中斷發生時，會執行env_pgfault_upcall指定位置的代碼。當執行env_pgfault_upcall指定位置的代碼時，棧已經轉到異常棧，並且壓入了UTrapframe結構。

static int
sys_env_set_pgfault_upcall(envid_t envid, void *func)
{
    // LAB 4: Your code here.
    struct Env *env;
    int ret;
    if ((ret = envid2env(envid, &env, 1)) < 0) {
        return ret;
    }
    env->env_pgfault_upcall = func;
    return 0;
}

Normal and Exception Stacks in User Environments

當缺頁中斷發生時，內核會返回用戶模式來處理該中斷。我們需要一個用戶異常棧，來模擬內核異常棧。JOS的用戶異常棧被定義在虛擬地址UXSTACKTOP。

Invoking the User Page Fault Handler

缺頁中斷發生時會進入內核的trap()，然後分配page_fault_handler()來處理缺頁中斷。在該函數中應該做如下幾件事：

判斷curenv->env_pgfault_upcall是否設置，如果沒有設置也就沒辦法修複，直接銷毀該進程。
修改esp，切換到用戶異常棧。
在棧上壓入一個UTrapframe結構。
將eip設置為curenv->env_pgfault_upcall，然後回到用戶態執行curenv->env_pgfault_upcall處的代碼。

UTrapframe結構如下：

                    <-- UXSTACKTOP
trap-time esp
trap-time eflags
trap-time eip
trap-time eax       start of struct PushRegs
trap-time ecx
trap-time edx
trap-time ebx
trap-time esp
trap-time ebp
trap-time esi
trap-time edi       end of struct PushRegs
tf_err (error code)
fault_va            <-- %esp when handler is run

Exercise 9:

按照上面的描述實現page_fault_handler()。

void
page_fault_handler(struct Trapframe *tf)
{
    uint32_t fault_va;

    // Read processor's CR2 register to find the faulting address
    fault_va = rcr2();

    // Handle kernel-mode page faults.

    // LAB 3: Your code here.
    if ((tf->tf_cs & 3) == 0)
        panic("page_fault_handler():page fault in kernel mode!\n");

    // LAB 4: Your code here.
    if (curenv->env_pgfault_upcall) {
        uintptr_t stacktop = UXSTACKTOP;
        if (UXSTACKTOP - PGSIZE < tf->tf_esp && tf->tf_esp < UXSTACKTOP) {
            stacktop = tf->tf_esp;
        }
        uint32_t size = sizeof(struct UTrapframe) + sizeof(uint32_t);
        user_mem_assert(curenv, (void *)stacktop - size, size, PTE_U | PTE_W);
        struct UTrapframe *utr = (struct UTrapframe *)(stacktop - size);
        utr->utf_fault_va = fault_va;
        utr->utf_err = tf->tf_err;
        utr->utf_regs = tf->tf_regs;
        utr->utf_eip = tf->tf_eip;
        utr->utf_eflags = tf->tf_eflags;
        utr->utf_esp = tf->tf_esp;              //UXSTACKTOP棧上需要保存發生缺頁異常時的%esp和%eip

        curenv->env_tf.tf_eip = (uintptr_t)curenv->env_pgfault_upcall;
        curenv->env_tf.tf_esp = (uintptr_t)utr;
        env_run(curenv);            //重新進入用戶態
    }

    // Destroy the environment that caused the fault.
    cprintf("[%08x] user fault va %08x ip %08x\n",
        curenv->env_id, fault_va, tf->tf_eip);
    print_trapframe(tf);
    env_destroy(curenv);
}

User-mode Page Fault Entrypoint

現在需要實現lib/pfentry.S中的_pgfault_upcall函數，該函數會作為系統調用sys_env_set_pgfault_upcall()的參數。

Exercise 10：

實現lib/pfentry.S中的_pgfault_upcall函數。

_pgfault_upcall:
    // Call the C page fault handler.
    pushl %esp          // function argument: pointer to UTF
    movl _pgfault_handler, %eax
    call *%eax              //調用頁處理函數
    addl $4, %esp           // pop function argument
    
    // LAB 4: Your code here.
    // Restore the trap-time registers.  After you do this, you
    // can no longer modify any general-purpose registers.
    // LAB 4: Your code here.
    addl $8, %esp           //跳過utf_fault_va和utf_err
    movl 40(%esp), %eax     //保存中斷發生時的esp到eax
    movl 32(%esp), %ecx     //保存終端發生時的eip到ecx
    movl %ecx, -4(%eax)     //將中斷發生時的esp值亞入到到原來的棧中
    popal
    addl $4, %esp           //跳過eip

    // Restore eflags from the stack.  After you do this, you can
    // no longer use arithmetic operations or anything else that
    // modifies eflags.
    // LAB 4: Your code here.
    popfl
    // Switch back to the adjusted trap-time stack.
    // LAB 4: Your code here.
    popl %esp
    // Return to re-execute the instruction that faulted.
    // LAB 4: Your code here.
    lea -4(%esp), %esp      //因為之前壓入了eip的值但是沒有減esp的值，所以現在需要將esp寄存器中的值減4
    ret

Exercise 11:

完成lib/pgfault.c中的set_pgfault_handler()。

void
set_pgfault_handler(void (*handler)(struct UTrapframe *utf))
{
    int r;

    if (_pgfault_handler == 0) {
        // First time through!
        // LAB 4: Your code here.
        int r = sys_page_alloc(0, (void *)(UXSTACKTOP-PGSIZE), PTE_W | PTE_U | PTE_P);  //為當前進程分配異常棧
        if (r < 0) {
            panic("set_pgfault_handler:sys_page_alloc failed");;
        }
        sys_env_set_pgfault_upcall(0, _pgfault_upcall);     //系統調用，設置進程的env_pgfault_upcall屬性
    }

    // Save handler pointer for assembly to call.
    _pgfault_handler = handler;
}

踩坑：

user_mem_check()中的cprintf()需要去掉，不然faultregs這個測試可能會過不了，坑啊~

缺頁處理小結：

引發缺頁中斷，執行內核函數鏈：trap()->trap_dispatch()->page_fault_handler()
page_fault_handler()切換棧到用戶異常棧，並且壓入UTrapframe結構，然後調用curenv->env_pgfault_upcall（系統調用sys_env_set_pgfault_upcall()設置）處代碼。又重新回到用戶態。
進入_pgfault_upcall處的代碼執行，調用_pgfault_handler（庫函數set_pgfault_handler()設置）處的代碼，最後返回到缺頁中斷發生時的那條指令重新執行。

Implementing Copy-on-Write Fork

到目前已經可以實現用戶級別的寫時拷貝fork函數了。fork流程如下：

使用set_pgfault_handler()設置缺頁處理函數。
調用sys_exofork()系統調用，在內核中創建一個Env結構，複製當前用戶環境寄存器狀態，UTOP以下的頁目錄還沒有建立，新創建的進程還不能直接運行。
拷貝父進程的頁表和頁目錄到子進程。對於可寫的頁，將對應的PTE的PTE_COW位設置為1。
為子進程設置_pgfault_upcall。
將子進程狀態設置為ENV_RUNNABLE。

缺頁處理函數pgfault()流程如下：

如果發現錯誤是因為寫造成的（錯誤碼是FEC_WR）並且該頁的PTE_COW是1，則進行執行第2步，否則直接panic。
分配一個新的物理頁，並將之前出現錯誤的頁的內容拷貝到新的物理頁，然後重新映射線性地址到新的物理頁。

Exercise 12：

實現lib/fork.c中的fork, duppage and pgfault。

static void
pgfault(struct UTrapframe *utf)
{
    void *addr = (void *) utf->utf_fault_va;
    uint32_t err = utf->utf_err;
    int r;

    // Check that the faulting access was (1) a write, and (2) to a
    // copy-on-write page.  If not, panic.
    // Hint:
    //   Use the read-only page table mappings at uvpt
    //   (see <inc/memlayout.h>).

    // LAB 4: Your code here.
    if (!((err & FEC_WR) && (uvpt[PGNUM(addr)] & PTE_COW))) { //只有因為寫操作寫時拷貝的地址這中情況，才可以搶救。否則一律panic
        panic("pgfault():not cow");
    }


    // Allocate a new page, map it at a temporary location (PFTEMP),
    // copy the data from the old page to the new page, then move the new
    // page to the old page's address.
    // Hint:
    //   You should make three system calls.

    // LAB 4: Your code here.
    addr = ROUNDDOWN(addr, PGSIZE);
    if ((r = sys_page_map(0, addr, 0, PFTEMP, PTE_U|PTE_P)) < 0)        //將當前進程PFTEMP也映射到當前進程addr指向的物理頁
        panic("sys_page_map: %e", r);
    if ((r = sys_page_alloc(0, addr, PTE_P|PTE_U|PTE_W)) < 0)   //令當前進程addr指向新分配的物理頁
        panic("sys_page_alloc: %e", r);
    memmove(addr, PFTEMP, PGSIZE);                              //將PFTEMP指向的物理頁拷貝到addr指向的物理頁
    if ((r = sys_page_unmap(0, PFTEMP)) < 0)                    //解除當前進程PFTEMP映射
        panic("sys_page_unmap: %e", r);
}

static int
duppage(envid_t envid, unsigned pn)
{
    int r;

    // LAB 4: Your code here.
    void *addr = (void*) (pn * PGSIZE);
    if (uvpt[pn] & PTE_SHARE) {
        sys_page_map(0, addr, envid, addr, PTE_SYSCALL);        //對於表示為PTE_SHARE的頁，拷貝映射關係，並且兩個進程都有讀寫許可權
    } else if ((uvpt[pn] & PTE_W) || (uvpt[pn] & PTE_COW)) { //對於UTOP以下的可寫的或者寫時拷貝的頁，拷貝映射關係的同時，需要同時標記當前進程和子進程的頁表項為PTE_COW
        if ((r = sys_page_map(0, addr, envid, addr, PTE_COW|PTE_U|PTE_P)) < 0)
            panic("sys_page_map：%e", r);
        if ((r = sys_page_map(0, addr, 0, addr, PTE_COW|PTE_U|PTE_P)) < 0)
            panic("sys_page_map：%e", r);
    } else {
        sys_page_map(0, addr, envid, addr, PTE_U|PTE_P);    //對於只讀的頁，只需要拷貝映射關係即可
    }
    return 0;
}

envid_t
fork(void)
{
    // LAB 4: Your code here.
    extern void _pgfault_upcall(void);
    set_pgfault_handler(pgfault);   //設置缺頁處理函數
    envid_t envid = sys_exofork();  //系統調用，只是簡單創建一個Env結構，複製當前用戶環境寄存器狀態，UTOP以下的頁目錄還沒有建立
    if (envid == 0) {               //子進程將走這個邏輯
        thisenv = &envs[ENVX(sys_getenvid())];
        return 0;
    }
    if (envid < 0) {
        panic("sys_exofork: %e", envid);
    }

    uint32_t addr;
    for (addr = 0; addr < USTACKTOP; addr += PGSIZE) {
        if ((uvpd[PDX(addr)] & PTE_P) && (uvpt[PGNUM(addr)] & PTE_P) //為什麼uvpt[pagenumber]能訪問到第pagenumber項頁表條目：https://pdos.csail.mit.edu/6.828/2018/labs/lab4/uvpt.html
            && (uvpt[PGNUM(addr)] & PTE_U)) {
            duppage(envid, PGNUM(addr));    //拷貝當前進程映射關係到子進程
        }
    }
    int r;
    if ((r = sys_page_alloc(envid, (void *)(UXSTACKTOP-PGSIZE), PTE_P | PTE_W | PTE_U)) < 0)    //為子進程分配異常棧
        panic("sys_page_alloc: %e", r);
    sys_env_set_pgfault_upcall(envid, _pgfault_upcall);     //為子進程設置_pgfault_upcall

    if ((r = sys_env_set_status(envid, ENV_RUNNABLE)) < 0)  //設置子進程為ENV_RUNNABLE狀態
        panic("sys_env_set_status: %e", r);
    return envid;
}

Part C: Preemptive Multitasking and Inter-Process communication (IPC)

Handling Clock Interrupts

目前程式一旦進入用戶模式，除非發生中斷，否則CPU永遠不會再執行內核代碼。我們需要開啟時鐘中斷，強迫進入內核，然後內核就可以切換另一個進程執行。
lapic_init()和pic_init()設置時鐘中斷控制器產生中斷。需要寫代碼來處理中斷。

Exercise 14：

修改trap_dispatch()，使時鐘中斷發生時，切換到另一個進程執行。

    if (tf->tf_trapno == IRQ_OFFSET + IRQ_TIMER) {
        lapic_eoi();
        sched_yield();
        return;
    }

Inter-Process communication (IPC)

到目前為止，我們都在做隔離的事情。操作系統另一個重要的內容是允許程式相互交流。

IPC in JOS

我們將要實現sys_ipc_recv()和sys_ipc_try_send()這兩個系統調用，來實現進程間通信。並且實現兩個包裝函數ipc_recv()和 ipc_send()。
JOS中進程間通信的“消息”包含兩部分：

一個32位的值。
可選的頁映射關係。

Sending and Receiving Messages

sys_ipc_recv()和sys_ipc_try_send()是這麼協作的：

當某個進程調用sys_ipc_recv()後，該進程會阻塞（狀態被置為ENV_NOT_RUNNABLE），直到另一個進程向它發送“消息”。當進程調用sys_ipc_recv()傳入dstva參數時，表明當前進程準備接收頁映射。
進程可以調用sys_ipc_try_send()向指定的進程發送“消息”，如果目標進程已經調用了sys_ipc_recv()，那麼就發送數據，然後返回0，否則返回-E_IPC_NOT_RECV，表示目標進程不希望接受數據。當傳入srcva參數時，表明發送進程希望和接收進程共用srcva對應的物理頁。如果發送成功了發送進程的srcva和接收進程的dstva將指向相同的物理頁。

Exercise 15

實現sys_ipc_recv()和sys_ipc_try_send()。包裝函數ipc_recv()和 ipc_send()。

static int
sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)
{
    // LAB 4: Your code here.
    struct Env *rcvenv;
    int ret = envid2env(envid, &rcvenv, 0);
    if (ret) return ret;
    if (!rcvenv->env_ipc_recving) return -E_IPC_NOT_RECV;

    if (srcva < (void*)UTOP) {
        pte_t *pte;
        struct PageInfo *pg = page_lookup(curenv->env_pgdir, srcva, &pte);

        //按照註釋的順序進行判定
        if (debug) {
            cprintf("sys_ipc_try_send():srcva=%08x\n", (uintptr_t)srcva);
        }
        if (srcva != ROUNDDOWN(srcva, PGSIZE)) {        //srcva沒有頁對齊
            if (debug) {
                cprintf("sys_ipc_try_send():srcva is not page-alligned\n");
            }
            return -E_INVAL;
        }
        if ((*pte & perm & 7) != (perm & 7)) {  //perm應該是*pte的子集
            if (debug) {
                cprintf("sys_ipc_try_send():perm is wrong\n");
            }
            return -E_INVAL;
        }
        if (!pg) {          //srcva還沒有映射到物理頁
            if (debug) {
                cprintf("sys_ipc_try_send():srcva is not maped\n");
            }
            return -E_INVAL;
        }
        if ((perm & PTE_W) && !(*pte & PTE_W)) {    //寫許可權
            if (debug) {
                cprintf("sys_ipc_try_send():*pte do not have PTE_W, but perm have\n");
            }
            return -E_INVAL;
        }       
        
        if (rcvenv->env_ipc_dstva < (void*)UTOP) {
            ret = page_insert(rcvenv->env_pgdir, pg, rcvenv->env_ipc_dstva, perm); //共用相同的映射關係
            if (ret) return ret;
            rcvenv->env_ipc_perm = perm;
        }
    }
    rcvenv->env_ipc_recving = 0;                    //標記接受進程可再次接受信息
    rcvenv->env_ipc_from = curenv->env_id;
    rcvenv->env_ipc_value = value; 
    rcvenv->env_status = ENV_RUNNABLE;
    rcvenv->env_tf.tf_regs.reg_eax = 0;
    return 0;
}

static int
sys_ipc_recv(void *dstva)
{
    // LAB 4: Your code here.
    if (dstva < (void *)UTOP && dstva != ROUNDDOWN(dstva, PGSIZE)) {
        return -E_INVAL;
    }
    curenv->env_ipc_recving = 1;
    curenv->env_status = ENV_NOT_RUNNABLE;
    curenv->env_ipc_dstva = dstva;
    sys_yield();
    return 0;
}

int32_t
ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)
{
    // LAB 4: Your code here.
    if (pg == NULL) {
        pg = (void *)-1;
    }
    int r = sys_ipc_recv(pg);
    if (r < 0) {                //系統調用失敗
        if (from_env_store) *from_env_store = 0;
        if (perm_store) *perm_store = 0;
        return r;
    }
    if (from_env_store)
        *from_env_store = thisenv->env_ipc_from;
    if (perm_store)
        *perm_store = thisenv->env_ipc_perm;
    return thisenv->env_ipc_value;
}

void
ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)
{
    // LAB 4: Your code here.
    if (pg == NULL) {
        pg = (void *)-1;
    }
    int r;
    while(1) {
        r = sys_ipc_try_send(to_env, val, pg, perm);
        if (r == 0) {       //發送成功
            return;
        } else if (r == -E_IPC_NOT_RECV) {  //接收進程沒有準備好
            sys_yield();
        } else {            //其它錯誤
            panic("ipc_send():%e", r);
        }
    }
}

IPC原理可以總結為下圖：
JOS IPC原理

總結

本lab還是圍繞進程這個概念來展開的。主要介紹了四部分：

支持多處理器。現代處理器一般都是多核的，這樣每個CPU能同時運行不同進程，實現並行。需要用鎖解決多CPU的競爭。 CPU和進程在內核中的數據結構如下圖所示：
實現進程調度演算法。一種是非搶占式式的，另一種是搶占式的，藉助時鐘中斷實現。
實現寫時拷貝fork（進程創建）。原理總結如下：
實現進程間通信。原理總結如下：

具體代碼在：https://github.com/gatsbyd/mit_6.828_jos

如有錯誤，歡迎指正(*^_^*)：
15313676365

MIT-6.828-JOS-lab4:Preemptive Multitasking