簡介

在 lab4 中我們將實現(xiàn)多個同時運行的用戶進程之間的搶占式多任務處理灼卢。
在 part A 中兑牡，我們需要給 JOS 增加多處理器支持练对。實現(xiàn)輪詢( round-robin, RR )調(diào)度遍蟋，并增加基本的用戶程序管理系統(tǒng)調(diào)用( 創(chuàng)建和銷毀進程，分配和映射內(nèi)存 )螟凭。
在 part B 中虚青，我們需要實現(xiàn)一個與 Unix 類似的 fork()，允許一個用戶進程創(chuàng)建自己的拷貝螺男。
在 part C中棒厘，我們會添加對進程間通信 ( IPC ) 的支持纵穿，允許不同的用戶進程相互通信和同步。還要增加對硬件時鐘中斷和搶占的支持奢人。

Part A: 多處理器支持及協(xié)同多任務處理

我們首先需要把 JOS 擴展到在多處理器系統(tǒng)中運行谓媒。然后實現(xiàn)一些新的 JOS 系統(tǒng)調(diào)用來允許用戶進程創(chuàng)建新的進程。我們還要實現(xiàn)協(xié)同輪詢調(diào)度何乎，在當前進程不使用 CPU 時允許內(nèi)核切換到另一個進程句惯。

多處理器支持

我們即將使 JOS 能夠支持“對稱多處理” (Symmetric MultiProcessing, SMP)。這種模式使所有 CPU 能對等地訪問內(nèi)存、I/O 總線等系統(tǒng)資源。雖然 CPU 在 SMP 下以同樣的方式工b作摔踱，在啟動過程中他們可以被分為兩個類型：引導處理器(BootStrap Processor, BSP) 負責初始化系統(tǒng)以及啟動操作系統(tǒng)谨履；應用處理器( Application Processors, AP ) 在操作系統(tǒng)拉起并運行后由 BSP 激活。哪個 CPU 作為 BSP 由硬件和 BIOS 決定孵班。也就是說目前我們所有的 JOS 代碼都運行在 BSP 上。
在 SMP 系統(tǒng)中，每個 CPU 都有一個附屬的 LAPIC 單元邓厕。LAPIC 單元用于傳遞中斷，并給它所屬的 CPU 一個唯一的 ID扁瓢。在 lab4 中详恼，我們將會用到 LAPIC 單元的以下基本功能 ( 見`kern/lapic.c1 )：

• 讀取 APIC ID 來判斷我們的代碼運行在哪個 CPU 之上。
• 從 BSP 發(fā)送STARTUP 跨處理器中斷 (InterProcessor Interrupt, IPI) 來啟動 AP引几。
• 在 part C 中昧互，我們?yōu)?LAPIC 的內(nèi)置計時器編程來觸發(fā)時鐘中斷以支持搶占式多任務處理。

處理器通過映射在內(nèi)存上的 I/O (Memory-Mapped I/O, MMIO) 來訪問它的 LAPIC伟桅。在 MMIO 中敞掘，物理內(nèi)存的一部分被硬連接到一些 I/O 設備的寄存器，因此楣铁，訪問內(nèi)存的 load/store 指令可以被用于訪問設備的寄存器玖雁。實際上，我們在 lab1 中已經(jīng)接觸過這樣的 IO hole盖腕，如0xA0000被用來寫 VGA 顯示緩沖赫冬。LAPIC 開始于物理地址 0xFE000000 ( 4GB以下32MB處 )。如果用以前的映射算法（將0xF0000000 映射到 0x00000000溃列，也就是說內(nèi)核空間最高只能到物理地址0x0FFFFFFF）顯然太高了劲厌。因此，JOS 在 MMIOBASE (即 虛擬地址0xEF800000) 預留了 4MB 來映射這類設備听隐。我們需要寫一個函數(shù)來分配這個空間并在其中映射設備內(nèi)存补鼻。

Exercise 1.
Implement mmio_map_region in kern/pmap.c. To see how this is used, look at the beginning of lapic_init in kern/lapic.c. You'll have to do the next exercise, too, before the tests for mmio_map_region will run.

lapic_init()函數(shù)的一開始就調(diào)用了該函數(shù)，將從 lapicaddr 開始的 4kB 物理地址映射到虛擬地址，并返回其起始地址风范。注意到咨跌，它是以頁為單位對齊的，每次都 map 一個頁的大小硼婿。

    // lapicaddr is the physical address of the LAPIC's 4K MMIO
    // region.  Map it in to virtual memory so we can access it.
    lapic = mmio_map_region(lapicaddr, 4096);

因此實際就是調(diào)用 boot_map_region 來建立所需要的映射虑润，需要注意的是，每次需要更改base的值加酵，使得每次都是映射到一個新的頁面拳喻。

void *
mmio_map_region(physaddr_t pa, size_t size)
{
    static uintptr_t base = MMIOBASE;

    size_t rounded_size = ROUNDUP(size, PGSIZE);

    if (base + rounded_size > MMIOLIM) panic("overflow MMIOLIM");
    boot_map_region(kern_pgdir, base, rounded_size, pa, PTE_W|PTE_PCD|PTE_PWT);
    uintptr_t res_region_base = base;   
    base += rounded_size;       
    return (void *)res_region_base;
}

引導應用處理器

在啟動 APs 之前，BSP 需要先搜集多處理器系統(tǒng)的信息猪腕，例如 CPU 的總數(shù)冗澈，CPU 各自的 APIC ID，LAPIC 單元的 MMIO 地址陋葡。kern/mpconfig.c 中的 mp_init() 函數(shù)通過閱讀 BIOS 區(qū)域內(nèi)存中的 MP 配置表來獲取這些信息亚亲。
boot_aps() 函數(shù)驅(qū)動了 AP 的引導。APs 從實模式開始腐缤，如同 boot/boot.S 中 bootloader 的啟動過程捌归。因此 boot_aps() 將 AP 的入口代碼 (kern/mpentry.S) 拷貝到實模式可以尋址的內(nèi)存區(qū)域 (0x7000, MPENTRY_PADDR)。
此后岭粤，boot_aps() 通過發(fā)送 STARTUP 這個跨處理器中斷到各 LAPIC 單元的方式惜索，逐個激活 APs。激活方式為：初始化 AP 的 CS:IP 值使其從入口代碼執(zhí)行剃浇。通過一些簡單的設置巾兆，AP 開啟分頁進入保護模式，然后調(diào)用 C 語言編寫的 mp_main()虎囚。boot_aps() 等待 AP 發(fā)送 CPU_STARTED 信號角塑，然后再喚醒下一個。

Exercise 2.
Read boot_aps() and mp_main() in kern/init.c, and the assembly code in kern/mpentry.S. Make sure you understand the control flow transfer during the bootstrap of APs. Then modify your implementation of page_init() in kern/pmap.c to avoid adding the page at MPENTRY_PADDR to the free list, so that we can safely copy and run AP bootstrap code at that physical address. Your code should pass the updated check_page_free_list() test (but might fail the updated check_kern_pgdir() test, which we will fix soon).

實際上就是標記 MPENTRY_PADDR 開始的一個物理頁為已使用淘讥，只需要在 page_init() 中做一個特例處理即可圃伶。唯一需要注意的就是確定這個特殊頁在哪個區(qū)間內(nèi)。

...
size_t mp_page = MPENTRY_PADDR/PGSIZE;
for (i = 1; i < npages_basemem; i++) {
    if (i == mp_page) {
        pages[i].pp_ref = 1;
        continue;
    }
    pages[i].pp_ref = 0;
    pages[i].pp_link = page_free_list;
    page_free_list = &pages[i];
}
...

現(xiàn)在執(zhí)行 make qemu蒲列，可以通過 check_kern_pgdir() 測試了窒朋，Exercise 1, 2 完成。

Question 1.
Compare kern/mpentry.S side by side with boot/boot.S. Bearing in mind that kern/mpentry.S is compiled and linked to run above KERNBASE just like everything else in the kernel, what is the purpose of macro MPBOOTPHYS? Why is it necessary in kern/mpentry.S but not in boot/boot.S? In other words, what could go wrong if it were omitted in kern/mpentry.S?
Hint: recall the differences between the link address and the load address that we have discussed in Lab 1.

注意 kern/mpentry.S 注釋中的一段話嫉嘀，說明了這兩者的區(qū)別炼邀。

# This code is similar to boot/boot.S except that
#    - it does not need to enable A20
#    - it uses MPBOOTPHYS to calculate absolute addresses of its
#      symbols, rather than relying on the linker to fill them

此外魄揉，還有個關鍵問題就是 MPBOOTPHYS 宏的作用剪侮。
kern/mpentry.S 是運行在 KERNBASE 之上的，與其他的內(nèi)核代碼一樣。也就是說瓣俯，類似于 mpentry_start, mpentry_end, start32 這類地址杰标，都位于 0xf0000000 之上，顯然彩匕，實模式是無法尋址的腔剂。再仔細看 MPBOOTPHYS 的定義：

#define MPBOOTPHYS(s) ((s) - mpentry_start + MPENTRY_PADDR)

其意義可以表示為，從 mpentry_start 到 MPENTRY_PADDR 建立映射驼仪，將 mpentry_start + offset 地址轉(zhuǎn)為 MPENTRY_PADDR + offset 地址掸犬。查看kern/init.c，發(fā)現(xiàn)已經(jīng)完成了這部分地址的內(nèi)容拷貝绪爸。

static void
boot_aps(void)
{
    extern unsigned char mpentry_start[], mpentry_end[];
    void *code;
    struct CpuInfo *c;

    // Write entry code to unused memory at MPENTRY_PADDR
    code = KADDR(MPENTRY_PADDR);
    memmove(code, mpentry_start, mpentry_end - mpentry_start);

    ...
}

因此湾碎，實模式下就可以通過 MPBOOTPHYS 宏的轉(zhuǎn)換，運行這部分代碼奠货。boot.S 中不需要這個轉(zhuǎn)換是因為代碼的本來就被加載在實模式可以尋址的地方介褥。

CPU 狀態(tài)和初始化

當寫一個多處理器操作系統(tǒng)時，分清 CPU 的私有狀態(tài) ( per-CPU state) 及全局狀態(tài) (global state) 非常關鍵递惋。 kern/cpu.h 定義了大部分的 per-CPU 狀態(tài)柔滔。
我們需要注意的 per-CPU 狀態(tài)有：

• Per-CPU 內(nèi)核棧
  因為多 CPU 可能同時陷入內(nèi)核態(tài)，我們需要給每個處理器一個獨立的內(nèi)核棧萍虽。percpu_kstacks[NCPU][KSTKSIZE]
  在 Lab2 中睛廊，我們將 BSP 的內(nèi)核棧映射到了 KSTACKTOP 下方。相似地杉编，在 Lab4 中喉前，我們需要把每個 CPU 的內(nèi)核棧都映射到這個區(qū)域，每個棧之間留下一個空頁作為緩沖區(qū)避免 overflow王财。CPU 0 卵迂，即 BSP 的棧還是從 KSTACKTOP 開始，間隔 KSTACKGAP 的距離就是 CPU 1 的棧绒净，以此類推见咒。

• Per-CPU TSS 以及 TSS 描述符
  為了指明每個 CPU 的內(nèi)核棧位置，需要任務狀態(tài)段 (Task State Segment, TSS)挂疆，其功能在 Lab3 中已經(jīng)詳細講過改览。

• Per-CPU 當前環(huán)境指針
  因為每個 CPU 能夠同時運行各自的用戶進程，我們重新定義了基于cpus[cpunum()] 的 curenv缤言。

• Per-CPU 系統(tǒng)寄存器
  所有的寄存器宝当，包括系統(tǒng)寄存器，都是 CPU 私有的胆萧。因此庆揩，初始化這些寄存器的指令俐东，例如 lcr3(), ltr(), lgdt(), lidt() 等，必須在每個 CPU 都執(zhí)行一次订晌。

Exercise 3.
Modify mem_init_mp() (in kern/pmap.c) to map per-CPU stacks starting at KSTACKTOP, as shown in inc/memlayout.h. The size of each stack is KSTKSIZE bytes plus KSTKGAP bytes of unmapped guard pages. Your code should pass the new check in check_kern_pgdir().

比較簡單的一個練習虏辫，起初只 map 了BSP，這次是 map 所有的 cpu（包括實際不存在的）锈拨。 在 kern/cpu.h 中可以找到對 NCPU 以及全局變量percpu_kstacks的聲明砌庄。

// Maximum number of CPUs
#define NCPU  8
...
// Per-CPU kernel stacks
extern unsigned char percpu_kstacks[NCPU][KSTKSIZE];

percpu_kstacks的定義在 kern/mpconfig.c 中可以找到：

// Per-CPU kernel stacks
unsigned char percpu_kstacks[NCPU][KSTKSIZE]
__attribute__ ((aligned(PGSIZE)));

此后就是修改 kern/pmap.c 中的函數(shù)，代碼很簡單：

static void
mem_init_mp(void)
{
    uintptr_t start_addr = KSTACKTOP - KSTKSIZE;    
    for (size_t i=0; i<NCPU; i++) {
        boot_map_region(kern_pgdir, (uintptr_t) start_addr, KSTKSIZE, PADDR(percpu_kstacks[i]), PTE_W | PTE_P);
        start_addr -= KSTKSIZE + KSTKGAP;
    }
}

但是有個違和感很強的地方奕枢，之前已經(jīng)把 BSP娄昆，也就是 cpu 0 的內(nèi)核棧映射到了bootstack對應的物理地址：

boot_map_region(kern_pgdir, (uintptr_t) (KSTACKTOP-KSTKSIZE), KSTKSIZE, PADDR(bootstack), PTE_W | PTE_P);

然而這里又映射到了另一片物理地址，具體可以打印出來觀察：

BSP: map 0xefff8000 to physical address 0x115000
...
cpu 0: map 0xefff8000 to physical address 0x22c000

這樣做會不會有什么問題呢缝彬？
實際上稿黄，觀察函數(shù) boot_map_region() 可以看出，其實新地址覆蓋了舊地址跌造。 而頁面引用是對虛擬內(nèi)存來講的杆怕，因此更換物理地址并不需要增加或減少頁面引用，這種寫法不會有任何問題壳贪。當然陵珍，我們也可以把之前對 BSP 棧的映射直接注釋掉，也能通過檢查违施。

Exercise 4.
The code in trap_init_percpu() (kern/trap.c) initializes the TSS and TSS descriptor for the BSP. It worked in Lab 3, but is incorrect when running on other CPUs. Change the code so that it can work on all CPUs. (Note: your new code should not use the global ts variable any more.)

先注釋掉 ts互纯，再根據(jù)單個cpu的代碼做改動。在 inc/memlayout.h 中可以找到 GD_TSS0 的定義：

#define GD_TSS0   0x28     // Task segment selector for CPU 0

但是并沒有其他地方說明其他 CPU 的任務段選擇器在哪磕蒲。因此最大的難點就是找到這個值留潦。實際上，偏移就是 cpu_id << 3辣往。

// static struct Taskstate ts;
...
    struct Taskstate* this_ts = &thiscpu->cpu_ts;

    // Setup a TSS so that we get the right stack
    // when we trap to the kernel.
    this_ts->ts_esp0 = KSTACKTOP - thiscpu->cpu_id*(KSTKSIZE + KSTKGAP);
    this_ts->ts_ss0 = GD_KD;
    this_ts->ts_iomb = sizeof(struct Taskstate);

    // Initialize the TSS slot of the gdt.
    gdt[(GD_TSS0 >> 3) + thiscpu->cpu_id] = SEG16(STS_T32A, (uint32_t) (this_ts),
                    sizeof(struct Taskstate) - 1, 0);
    gdt[(GD_TSS0 >> 3) + thiscpu->cpu_id].sd_s = 0;

    // Load the TSS selector (like other segment selectors, the
    // bottom three bits are special; we leave them 0)
    ltr(GD_TSS0 + (thiscpu->cpu_id << 3));

    // Load the IDT
    lidt(&idt_pd);

運行 make qemu CPUS=4 成功（雖然我只有2核兔院，似乎初始化的 cpu 個數(shù)完全靠用戶指定）。

鎖

我們現(xiàn)在的代碼在初始化 AP 后就會開始自旋站削。在進一步操作 AP 之前坊萝，我們要先處理幾個 CPU 同時運行內(nèi)核代碼的競爭情況。最簡單的方法是用一個大內(nèi)核鎖 (big kernel lock)许起。它是一個全局鎖十偶，在某個進程進入內(nèi)核態(tài)時鎖定，返回用戶態(tài)時釋放园细。這種模式下惦积，用戶進程可以并發(fā)地在 CPU 上運行，但是同一時間僅有一個進程可以在內(nèi)核態(tài)猛频，其他需要進入內(nèi)核態(tài)的進程只能等待狮崩。
kern/spinlock.h 聲明了一個大內(nèi)核鎖 kernel_lock蛛勉。它提供了 lock_kernel() 和 unlock_kernel() 方法用于獲得和釋放鎖。在以下 4 個地方需要使用到大內(nèi)核鎖：

• 在 i386_init()厉亏，BSP 喚醒其他 CPU 之前獲得內(nèi)核鎖
• 在 mp_main()董习，初始化 AP 之后獲得內(nèi)核鎖烈和，之后調(diào)用 sched_yield() 在 AP 上運行進程爱只。
• 在 trap()，當從用戶態(tài)陷入內(nèi)核態(tài)時獲得內(nèi)核鎖招刹，通過檢查 tf_Cs 的低 2bit 來確定該 trap 是由用戶進程還是內(nèi)核觸發(fā)恬试。
• 在 env_run()，在切換回用戶模式前釋放內(nèi)核鎖疯暑。

Exercise 5.
Apply the big kernel lock as described above, by calling lock_kernel() and unlock_kernel() at the proper locations.

實現(xiàn)比較簡單训柴，不用細講。
關鍵要理解兩點：

• 大內(nèi)核鎖的實現(xiàn)

void
spin_lock(struct spinlock *lk)
{
#ifdef DEBUG_SPINLOCK
    if (holding(lk))
        panic("CPU %d cannot acquire %s: already holding", cpunum(), lk->name);
#endif

    // The xchg is atomic.
    // It also serializes, so that reads after acquire are not
    // reordered before it. 
    // 關鍵代碼妇拯，體現(xiàn)了循環(huán)等待的思想
    while (xchg(&lk->locked, 1) != 0)
        asm volatile ("pause");

    // Record info about lock acquisition for debugging.
#ifdef DEBUG_SPINLOCK
    lk->cpu = thiscpu;
    get_caller_pcs(lk->pcs);
#endif
}

其中幻馁，在 inc/x86.h 中可以找到 xchg() 函數(shù)的實現(xiàn)，使用它而不是用簡單的 if + 賦值 是因為它是一個原子性的操作越锈。

static inline uint32_t
xchg(volatile uint32_t *addr, uint32_t newval)
{
    uint32_t result;

    // The + in "+m" denotes a read-modify-write operand.
    asm volatile("lock; xchgl %0, %1"
             : "+m" (*addr), "=a" (result)  // 輸出
             : "1" (newval)             //  輸入
             : "cc");
    return result;
}

這是一段內(nèi)聯(lián)匯編仗嗦，語法在 Lab3 中已經(jīng)講解過。lock 確保了操作的原子性甘凭，其意義是將 addr 存儲的值與 newval 交換稀拐，并返回 addr 中原本的值。于是丹弱，如果最初 locked = 0德撬，即未加鎖，就能跳出這個 while循環(huán)躲胳。否則就會利用 pause 命令自旋等待蜓洪。這就確保了當一個 CPU 獲得了 BKL，其他 CPU 如果也要獲得就只能自旋等待坯苹。

• 為什么要在這幾處加大內(nèi)核鎖
  為了避免多個 CPU 同時運行內(nèi)核代碼蝠咆，這基本是廢話。從根本上來講北滥，其設計的初衷就是保證獨立性刚操。由于分頁機制的存在，內(nèi)核以及每個用戶進程都有自己的獨立空間再芋。而多進程并發(fā)的時候菊霜，如果兩個進程同時陷入內(nèi)核態(tài)，就無法保證獨立性了济赎。例如內(nèi)核中有某個全局變量 A鉴逞，cpu1 讓 A=1记某， 而后 cpu2 卻讓 A=2，顯然會互相影響构捡。最初 Linux 設計者為了使系統(tǒng)盡快支持 SMP液南，直接在內(nèi)核入口放了一把大鎖，保證其獨立性勾徽。參見這篇非常好的文章 大內(nèi)核鎖將何去何從
  其流程大致為：
  BPS 啟動 AP 前滑凉，獲取內(nèi)核鎖，所以 AP 會在 mp_main 執(zhí)行調(diào)度之前阻塞喘帚，在啟動完 AP 后畅姊，BPS 執(zhí)行調(diào)度，運行第一個進程吹由，env_run() 函數(shù)中會釋放內(nèi)核鎖若未，這樣一來，其中一個 AP 就可以開始執(zhí)行調(diào)度倾鲫，運行其他進程粗合。

Question 2.
It seems that using the big kernel lock guarantees that only one CPU can run the kernel code at a time. Why do we still need separate kernel stacks for each CPU? Describe a scenario in which using a shared kernel stack will go wrong, even with the protection of the big kernel lock

例如，在某進程即將陷入內(nèi)核態(tài)的時候（尚未獲得鎖）乌昔，其實在 trap() 函數(shù)之前已經(jīng)在 trapentry.S 中對內(nèi)核棧進行了操作隙疚，壓入了寄存器信息。如果共用一個內(nèi)核棧玫荣，那顯然會導致信息錯誤甚淡。

輪詢調(diào)度

下一個任務是讓 JOS 內(nèi)核能夠以輪詢方式在多個任務之間切換。其原理如下：

• kern/sched.c 中的 sched_yield() 函數(shù)用來選擇一個新的進程運行捅厂。它將從上一個運行的進程開始贯卦，按順序循環(huán)搜索 envs[] 數(shù)組，選取第一個狀態(tài)為 ENV_RUNNABLE 的進程執(zhí)行焙贷。

• sched_yield()不能同時在兩個CPU上運行同一個進程撵割。如果一個進程已經(jīng)在某個 CPU 上運行，其狀態(tài)會變?yōu)?ENV_RUNNING辙芍。

• 程序中已經(jīng)實現(xiàn)了一個新的系統(tǒng)調(diào)用 sys_yield()啡彬，進程可以用它來喚起內(nèi)核的 sched_yield() 函數(shù)，從而將 CPU 資源移交給一個其他的進程故硅。

Exercise 6.
Implement round-robin scheduling in sched_yield() as described above. Don't forget to modify syscall() to dispatch sys_yield().
Make sure to invoke sched_yield() in mp_main.
Modify kern/init.c to create three (or more!) environments that all run the program user/yield.c.

注意以下幾個問題：

• 如何找到目前正在運行的進程在 envs[] 中的序號庶灿？
  在 kern/env.h 中，可以找到指向 struct Env的指針 curenv吃衅，表示當前正在運行的進程往踢。但是需要注意，不能直接由 curenv->env_id得到其序號徘层。在 inc/env.h 中有一個宏可以完成這個轉(zhuǎn)換峻呕。

// The environment index ENVX(eid) equals the environment's offset in the 'envs[]' array.
#define ENVX(envid)     ((envid) & (NENV - 1))

• 查看 kern/env.c 可以發(fā)現(xiàn) curenv 可能為 NULL利职。因此要注意特例。

在 kern/sched.c 中實現(xiàn)輪詢調(diào)度瘦癌。

void
sched_yield(void)
{
    struct Env *idle;

    // LAB 4: Your code here.
    idle = curenv;
    size_t idx = idle!=NULL ? ENVX(idle->env_id):-1;
    for (size_t i=0; i<NENV; i++) {
        idx = (idx+1 == NENV) ? 0:idx+1;
        if (envs[idx].env_status == ENV_RUNNABLE) {
            env_run(&envs[idx]);
            return;
        }
    }
    if (idle && idle->env_status == ENV_RUNNING) {
        env_run(idle);
        return;
    }
    // sched_halt never returns
    sched_halt();
}

在 kern/syscall.c 中添加新的系統(tǒng)調(diào)用猪贪。

// syscall()
...
    case SYS_yield:
        sys_yield();
        break;
...

將 kern/init.c 中運行的用戶進程改為以下：

// i386_init()
...
#if defined(TEST)
    // Don't touch -- used by grading script!
    ENV_CREATE(TEST, ENV_TYPE_USER);
#else
    // Touch all you want.
    ENV_CREATE(user_primes, ENV_TYPE_USER);
#endif // TEST*
    ENV_CREATE(user_yield, ENV_TYPE_USER);
    ENV_CREATE(user_yield, ENV_TYPE_USER);
    ENV_CREATE(user_yield, ENV_TYPE_USER);
...

運行 make qemu CPUS=2 可以看到三個進程通過調(diào)用 sys_yield 切換了5次。

Hello, I am environment 00001000.
Hello, I am environment 00001001.
Back in environment 00001000, iteration 0.
Hello, I am environment 00001002.
Back in environment 00001001, iteration 0.
Back in environment 00001000, iteration 1.
Back in environment 00001002, iteration 0.
Back in environment 00001001, iteration 1.
Back in environment 00001000, iteration 2.
Back in environment 00001002, iteration 1.
Back in environment 00001001, iteration 2.
Back in environment 00001000, iteration 3.
Back in environment 00001002, iteration 2.
Back in environment 00001001, iteration 3.
Back in environment 00001000, iteration 4.
Back in environment 00001002, iteration 3.
All done in environment 00001000.
[00001000] exiting gracefully
[00001000] free env 00001000
Back in environment 00001001, iteration 4.
Back in environment 00001002, iteration 4.
All done in environment 00001001.
All done in environment 00001002.
[00001001] exiting gracefully
[00001001] free env 00001001
[00001002] exiting gracefully
[00001002] free env 00001002
No runnable environments in the system!
Welcome to the JOS kernel monitor!
Type 'help' for a list of commands.
K> 

記錄一下自己遇到的問題：
這個 exercise 出現(xiàn)了 triple fault 報錯讯私，查了很久原因热押。由于是triple fault 肯定是 trap 過程中的錯誤，仔細檢查發(fā)現(xiàn)是自己的 exercise4 的做法出現(xiàn)了問題妄帘，一個非常二的錯誤楞黄。

// 錯誤版本池凄，顯然沒有更改 thiscpu 中的值
    struct Taskstate this_ts = thiscpu->cpu_ts;
// 正確版本
    struct Taskstate* this_ts = &thiscpu->cpu_ts;

Question 3.
In your implementation of env_run() you should have called lcr3(). Before and after the call to lcr3(), your code makes references (at least it should) to the variable e, the argument to env_run. Upon loading the %cr3 register, the addressing context used by the MMU is instantly changed. But a virtual address (namely e) has meaning relative to a given address context--the address context specifies the physical address to which the virtual address maps. Why can the pointer e be dereferenced both before and after the addressing switch?

大意是問為什么通過 lcr3() 切換了頁目錄抡驼，還能照常對 e 解引用≈茁兀回想在 lab3 中致盟，曾經(jīng)寫過的函數(shù) env_setup_vm()。它直接以內(nèi)核的頁目錄作為模版稍做修改尤慰。因此兩個頁目錄的 e 地址映射到同一物理地址馏锡。

static int
env_setup_vm(struct Env *e)
{
    int i;
    struct PageInfo *p = NULL;

    // Allocate a page for the page directory
    if (!(p = page_alloc(ALLOC_ZERO)))
        return -E_NO_MEM;

    // LAB 3: Your code here.
    e->env_pgdir = page2kva(p);
    memcpy(e->env_pgdir, kern_pgdir, PGSIZE); // use kern_pgdir as template 
    p->pp_ref++;
    // UVPT maps the env's own page table read-only.
    // Permissions: kernel R, user R
    e->env_pgdir[PDX(UVPT)] = PADDR(e->env_pgdir) | PTE_P | PTE_U;

    return 0;
}

Question 4.
Whenever the kernel switches from one environment to another, it must ensure the old environment's registers are saved so they can be restored properly later. Why? Where does this happen?

在進程陷入內(nèi)核時，會保存當前的運行信息伟端，這些信息都保存在內(nèi)核棧上杯道。而當從內(nèi)核態(tài)回到用戶態(tài)時，會恢復之前保存的運行信息责蝠。
具體到 JOS 代碼中党巾，保存發(fā)生在 kern/trapentry.S，恢復發(fā)生在 kern/env.c霜医〕莘鳎可以對比兩者的代碼。
保存：

#define TRAPHANDLER_NOEC(name, num)
    .globl name;                            
    .type name, @function;                      
    .align 2;                           
    name:                               
    pushl $0;                           
    pushl $(num);                           
    jmp _alltraps
...

_alltraps:
pushl %ds    // 保存當前段寄存器
pushl %es
pushal    // 保存其他寄存器

movw $GD_KD, %ax
movw %ax, %ds
movw %ax, %es
pushl %esp    //  保存當前棧頂指針
call trap

恢復：

void
env_pop_tf(struct Trapframe *tf)
{
    // Record the CPU we are running on for user-space debugging
    curenv->env_cpunum = cpunum();

    asm volatile(
        "\tmovl %0,%%esp\n"    // 恢復棧頂指針
        "\tpopal\n"    // 恢復其他寄存器
        "\tpopl %%es\n"    // 恢復段寄存器
        "\tpopl %%ds\n"
        "\taddl $0x8,%%esp\n" /* skip tf_trapno and tf_errcode */
        "\tiret\n"
        : : "g" (tf) : "memory");
    panic("iret failed");  /* mostly to placate the compiler */
}

系統(tǒng)調(diào)用：創(chuàng)建進程

現(xiàn)在我們的內(nèi)核已經(jīng)可以運行多個進程肴敛，并在其中切換了署海。不過，現(xiàn)在它仍然只能運行內(nèi)核最初設定好的程序 (kern/init.c) ∫侥校現(xiàn)在我們即將實現(xiàn)一個新的系統(tǒng)調(diào)用砸狞，它允許進程創(chuàng)建并開始新的進程。
Unix 提供了 fork() 這個原始的系統(tǒng)調(diào)用來創(chuàng)建進程镀梭。fork()將會拷貝父進程的整個地址空間來創(chuàng)建子進程刀森。在用戶空間里，父子進程之間的唯一區(qū)別就是它們的進程 ID丰辣。fork()在父進程中返回其子進程的進程 ID撒强，而在子進程中返回 0禽捆。父子進程之間是完全獨立的，任意一方修改內(nèi)存飘哨，另一方都不會受到影響胚想。
我們將為 JOS 實現(xiàn)一個更原始的系統(tǒng)調(diào)用來創(chuàng)建新的進程。涉及到的系統(tǒng)調(diào)用如下：

• sys_exofork:
  這個系統(tǒng)調(diào)用將會創(chuàng)建一個空白進程：在其用戶空間中沒有映射任何物理內(nèi)存芽隆，并且它是不可運行的浊服。剛開始時，它擁有和父進程相同的寄存器狀態(tài)胚吁。sys_exofork 將會在父進程返回其子進程的envid_t牙躺，子進程返回 0（當然，由于子進程還無法運行腕扶，也無法返回值孽拷，直到運行：）
• sys_env_set_status:
  設置指定進程的狀態(tài)。這個系統(tǒng)調(diào)用通常用于在新進程的地址空間和寄存器初始化完成后脓恕，將其標記為可運行。
• sys_page_alloc:
  分配一個物理頁并將其映射到指定進程的指定虛擬地址上。
• sys_page_map:
  從一個進程中拷貝一個頁面映射（而非物理頁的內(nèi)容）到另一個。即共享內(nèi)存。
• sys_page_unmap:
  刪除到指定進程的指定虛擬地址的映射。

Exercise 7.
Implement the system calls described above in kern/syscall.c. You will need to use various functions in kern/pmap.c and kern/env.c, particularly envid2env(). For now, whenever you call envid2env(), pass 1 in the checkperm parameter. Be sure you check for any invalid system call arguments, returning -E_INVAL in that case. Test your JOS kernel with user/dumbfork and make sure it works before proceeding.

一個比較冗長的練習金麸。重點應該放在閱讀 user/dumbfork.c 上桨醋，以便理解各個系統(tǒng)調(diào)用的作用。
在 user/dumbfork.c 中，核心是 duppage() 函數(shù)。它利用 sys_page_alloc() 為子進程分配空閑物理頁，再使用sys_page_map() 將該新物理頁映射到內(nèi)核 (內(nèi)核的 env_id = 0) 的交換區(qū) UTEMP耻矮，方便在內(nèi)核態(tài)進行 memmove 拷貝操作倡缠。在拷貝結(jié)束后，利用 sys_page_unmap() 將交換區(qū)的映射刪除。

void
duppage(envid_t dstenv, void *addr)
{
    int r;

    // This is NOT what you should do in your fork.
    if ((r = sys_page_alloc(dstenv, addr, PTE_P|PTE_U|PTE_W)) < 0)
        panic("sys_page_alloc: %e", r);
    if ((r = sys_page_map(dstenv, addr, 0, UTEMP, PTE_P|PTE_U|PTE_W)) < 0)
        panic("sys_page_map: %e", r);
    memmove(UTEMP, addr, PGSIZE);
    if ((r = sys_page_unmap(0, UTEMP)) < 0)
        panic("sys_page_unmap: %e", r);
}

sys_exofork() 函數(shù)

該函數(shù)主要是分配了一個新的進程，但是沒有做內(nèi)存復制等處理衔蹲。唯一值得注意的就是如何使子進程返回0。
sys_exofork()是一個非常特殊的系統(tǒng)調(diào)用，它的定義與實現(xiàn)在 inc/lib.h 中，而不是 lib/syscall.c 中垢夹。并且而晒，它必須是 inline 的迅耘。

// This must be inlined.  Exercise for reader: why?
static inline envid_t __attribute__((always_inline))
sys_exofork(void)
{
    envid_t ret;
    asm volatile("int %2"
             : "=a" (ret)
             : "a" (SYS_exofork), "i" (T_SYSCALL));
    return ret;
}

可以看出，它的返回值是 %eax 寄存器的值。那么彰触，它到底是什么時候返回分蓖？這就涉及到對整個 進程->內(nèi)核->進程 的過程的理解尔艇。

static envid_t
sys_exofork(void)
{
    // LAB 4: Your code here.
    // panic("sys_exofork not implemented");
    struct Env *e;
    int r = env_alloc(&e, curenv->env_id);
    if (r < 0) return r;
    e->env_status = ENV_NOT_RUNNABLE;
    e->env_tf = curenv->env_tf;
    e->env_tf.tf_regs.reg_eax = 0;
    return e->env_id;
}

在該函數(shù)中，子進程復制了父進程的 trapframe么鹤，此后把 trapframe 中的 eax 的值設為了0终娃。最后，返回了子進程的 id蒸甜。注意棠耕，根據(jù) kern/trap.c 中的 trap_dispatch() 函數(shù)，這個返回值僅僅是存放在了父進程的 trapframe 中柠新，還沒有返回窍荧。而是在返回用戶態(tài)的時候，即在 env_run() 中調(diào)用 env_pop_tf() 時恨憎，才把 trapframe 中的值賦值給各個寄存器蕊退。這時候 lib/syscall.c 中的函數(shù) syscall() 才獲得真正的返回值。因此憔恳，在這里對子進程 trapframe 的修改瓤荔，可以使得子進程返回0。

sys_page_alloc() 函數(shù)
在進程 envid 的目標地址 va 分配一個權限為 perm 的頁面钥组。

static int
sys_page_alloc(envid_t envid, void *va, int perm)
{
    // LAB 4: Your code here.
    // panic("sys_page_alloc not implemented");
    if ((~perm & (PTE_U|PTE_P)) != 0) return -E_INVAL;
    if ((perm & (~(PTE_U|PTE_P|PTE_AVAIL|PTE_W))) != 0) return -E_INVAL;
    if ((uintptr_t)va >= UTOP || PGOFF(va) != 0) return -E_INVAL; 
    
    struct PageInfo *pginfo = page_alloc(ALLOC_ZERO);
    if (!pginfo) return -E_NO_MEM;
    struct Env *e;
    int r = envid2env(envid, &e, 1);
    if (r < 0) return -E_BAD_ENV;
    r = page_insert(e->env_pgdir, pginfo, va, perm);
    if (r < 0) {
        page_free(pginfo);
        return -E_NO_MEM;
    }
    return 0;
}

sys_page_map() 函數(shù)
簡單來說输硝，就是建立跨進程的映射。

static int
sys_page_map(envid_t srcenvid, void *srcva,
         envid_t dstenvid, void *dstva, int perm)
{
    // LAB 4: Your code here.
    // panic("sys_page_map not implemented");

    if ((uintptr_t)srcva >= UTOP || PGOFF(srcva) != 0) return -E_INVAL;
    if ((uintptr_t)dstva >= UTOP || PGOFF(dstva) != 0) return -E_INVAL;
    if ((perm & PTE_U) == 0 || (perm & PTE_P) == 0 || (perm & ~PTE_SYSCALL) != 0) return -E_INVAL;
    struct Env *src_e, *dst_e;
    if (envid2env(srcenvid, &src_e, 1)<0 || envid2env(dstenvid, &dst_e, 1)<0) return -E_BAD_ENV;
    pte_t *src_ptab;    
    struct PageInfo *pp = page_lookup(src_e->env_pgdir, srcva, &src_ptab);
    if ((*src_ptab & PTE_W) == 0 && (perm & PTE_W) == 1) return -E_INVAL;
    if (page_insert(dst_e->env_pgdir, pp, dstva, perm) < 0) return -E_NO_MEM;
    return 0;
}

sys_page_unmap() 函數(shù)
取消映射者铜。

static int
sys_page_unmap(envid_t envid, void *va)
{
    // LAB 4: Your code here.
    // panic("sys_page_unmap not implemented");
    if ((uintptr_t)va >= UTOP || PGOFF(va) != 0) return -E_INVAL;
    struct Env *e;
    if (envid2env(envid, &e, 1) < 0) return -E_BAD_ENV;
    page_remove(e->env_pgdir, va);
    return 0;
}

sys_env_set_status() 函數(shù)
設置狀態(tài)腔丧，在子進程內(nèi)存 map 結(jié)束后再使用。

static int
sys_env_set_status(envid_t envid, int status)
{
    // LAB 4: Your code here.
    // panic("sys_env_set_status not implemented");
    
    if (status != ENV_RUNNABLE && status != ENV_NOT_RUNNABLE) return -E_INVAL;  
    struct Env *e;
    if (envid2env(envid, &e, 1) < 0) return -E_BAD_ENV;
    e->env_status = status;
    return 0;
}

最后作烟，不要忘記在 kern/syscall.c 中添加新的系統(tǒng)調(diào)用類型，注意參數(shù)的處理砾医。

...
    case SYS_exofork:
        retVal = (int32_t)sys_exofork();
        break;
    case SYS_env_set_status:
        retVal = sys_env_set_status(a1, a2);
        break;
    case SYS_page_alloc:
        retVal = sys_page_alloc(a1,(void *)a2, (int)a3);
        break;
    case SYS_page_map:
        retVal = sys_page_map(a1, (void *)a2, a3, (void*)a4, (int)a5);
        break;
    case SYS_page_unmap:
        retVal = sys_page_unmap(a1, (void *)a2);
        break;
...

make grade 成功拿撩。至此，part A 結(jié)束如蚜。