簡(jiǎn)介

在 lab4 中我們將實(shí)現(xiàn)多個(gè)同時(shí)運(yùn)行的用戶進(jìn)程之間的搶占式多任務(wù)處理。
在 part A 中，我們需要給 JOS 增加多處理器支持。實(shí)現(xiàn)輪詢( round-robin, RR )調(diào)度，并增加基本的用戶程序管理系統(tǒng)調(diào)用( 創(chuàng)建和銷毀進(jìn)程，分配和映射內(nèi)存 )。
在 part B 中，我們需要實(shí)現(xiàn)一個(gè)與 Unix 類似的 fork()，允許一個(gè)用戶進(jìn)程創(chuàng)建自己的拷貝。
在 part C中，我們會(huì)添加對(duì)進(jìn)程間通信 ( IPC ) 的支持，允許不同的用戶進(jìn)程相互通信和同步。還要增加對(duì)硬件時(shí)鐘中斷和搶占的支持。

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

我們首先需要把 JOS 擴(kuò)展到在多處理器系統(tǒng)中運(yùn)行。然后實(shí)現(xiàn)一些新的 JOS 系統(tǒng)調(diào)用來(lái)允許用戶進(jìn)程創(chuàng)建新的進(jìn)程。我們還要實(shí)現(xiàn)協(xié)同輪詢調(diào)度，在當(dāng)前進(jìn)程不使用 CPU 時(shí)允許內(nèi)核切換到另一個(gè)進(jìn)程。

多處理器支持

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

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

處理器通過(guò)映射在內(nèi)存上的 I/O (Memory-Mapped I/O, MMIO) 來(lái)訪問(wèn)它的 LAPIC。在 MMIO 中，物理內(nèi)存的一部分被硬連接到一些 I/O 設(shè)備的寄存器，因此，訪問(wèn)內(nèi)存的 load/store 指令可以被用于訪問(wèn)設(shè)備的寄存器。實(shí)際上，我們?cè)?lab1 中已經(jīng)接觸過(guò)這樣的 IO hole，如0xA0000被用來(lái)寫 VGA 顯示緩沖。LAPIC 開(kāi)始于物理地址 0xFE000000 ( 4GB以下32MB處 )。如果用以前的映射算法（將0xF0000000 映射到 0x00000000，也就是說(shuō)內(nèi)核空間最高只能到物理地址0x0FFFFFFF）顯然太高了。因此，JOS 在 MMIOBASE (即 虛擬地址0xEF800000) 預(yù)留了 4MB 來(lái)映射這類設(shè)備。我們需要寫一個(gè)函數(shù)來(lái)分配這個(gè)空間并在其中映射設(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ù)的一開(kāi)始就調(diào)用了該函數(shù)，將從 lapicaddr 開(kāi)始的 4kB 物理地址映射到虛擬地址，并返回其起始地址。注意到，它是以頁(yè)為單位對(duì)齊的，每次都 map 一個(gè)頁(yè)的大小。

    // 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);

因此實(shí)際就是調(diào)用 boot_map_region 來(lái)建立所需要的映射，需要注意的是，每次需要更改base的值，使得每次都是映射到一個(gè)新的頁(yè)面。

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;
}

引導(dǎo)應(yīng)用處理器

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

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).

實(shí)際上就是標(biāo)記 MPENTRY_PADDR 開(kāi)始的一個(gè)物理頁(yè)為已使用，只需要在 page_init() 中做一個(gè)特例處理即可。唯一需要注意的就是確定這個(gè)特殊頁(yè)在哪個(gè)區(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，可以通過(guò) check_kern_pgdir() 測(cè)試了，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 注釋中的一段話，說(shuō)明了這兩者的區(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

此外，還有個(gè)關(guān)鍵問(wèn)題就是 MPBOOTPHYS 宏的作用。
kern/mpentry.S 是運(yùn)行在 KERNBASE 之上的，與其他的內(nèi)核代碼一樣。也就是說(shuō)，類似于 mpentry_start, mpentry_end, start32 這類地址，都位于 0xf0000000 之上，顯然，實(shí)模式是無(wú)法尋址的。再仔細(xì)看 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);

    ...
}

因此，實(shí)模式下就可以通過(guò) MPBOOTPHYS 宏的轉(zhuǎn)換，運(yùn)行這部分代碼。boot.S 中不需要這個(gè)轉(zhuǎn)換是因?yàn)榇a的本來(lái)就被加載在實(shí)模式可以尋址的地方。

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

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

• Per-CPU 內(nèi)核棧
  因?yàn)槎?CPU 可能同時(shí)陷入內(nèi)核態(tài)，我們需要給每個(gè)處理器一個(gè)獨(dú)立的內(nèi)核棧。percpu_kstacks[NCPU][KSTKSIZE]
  在 Lab2 中，我們將 BSP 的內(nèi)核棧映射到了 KSTACKTOP 下方。相似地，在 Lab4 中，我們需要把每個(gè) CPU 的內(nèi)核棧都映射到這個(gè)區(qū)域，每個(gè)棧之間留下一個(gè)空頁(yè)作為緩沖區(qū)避免 overflow。CPU 0 ，即 BSP 的棧還是從 KSTACKTOP 開(kāi)始，間隔 KSTACKGAP 的距離就是 CPU 1 的棧，以此類推。

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

• Per-CPU 當(dāng)前環(huán)境指針
  因?yàn)槊總€(gè) CPU 能夠同時(shí)運(yùn)行各自的用戶進(jìn)程，我們重新定義了基于cpus[cpunum()] 的 curenv。

• Per-CPU 系統(tǒng)寄存器
  所有的寄存器，包括系統(tǒng)寄存器，都是 CPU 私有的。因此，初始化這些寄存器的指令，例如 lcr3(), ltr(), lgdt(), lidt() 等，必須在每個(gè) 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().

比較簡(jiǎn)單的一個(gè)練習(xí)，起初只 map 了BSP，這次是 map 所有的 cpu（包括實(shí)際不存在的）。 在 kern/cpu.h 中可以找到對(duì) 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ù)，代碼很簡(jiǎn)單：

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;
    }
}

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

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

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

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

這樣做會(huì)不會(huì)有什么問(wèn)題呢？
實(shí)際上，觀察函數(shù) boot_map_region() 可以看出，其實(shí)新地址覆蓋了舊地址。 而頁(yè)面引用是對(duì)虛擬內(nèi)存來(lái)講的，因此更換物理地址并不需要增加或減少頁(yè)面引用，這種寫法不會(huì)有任何問(wèn)題。當(dāng)然，我們也可以把之前對(duì) BSP 棧的映射直接注釋掉，也能通過(guò)檢查。

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ù)單個(gè)cpu的代碼做改動(dòng)。在 inc/memlayout.h 中可以找到 GD_TSS0 的定義：

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

但是并沒(méi)有其他地方說(shuō)明其他 CPU 的任務(wù)段選擇器在哪。因此最大的難點(diǎn)就是找到這個(gè)值。實(shí)際上，偏移就是 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);

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

鎖

我們現(xiàn)在的代碼在初始化 AP 后就會(huì)開(kāi)始自旋。在進(jìn)一步操作 AP 之前，我們要先處理幾個(gè) CPU 同時(shí)運(yùn)行內(nèi)核代碼的競(jìng)爭(zhēng)情況。最簡(jiǎn)單的方法是用一個(gè)大內(nèi)核鎖 (big kernel lock)。它是一個(gè)全局鎖，在某個(gè)進(jìn)程進(jìn)入內(nèi)核態(tài)時(shí)鎖定，返回用戶態(tài)時(shí)釋放。這種模式下，用戶進(jìn)程可以并發(fā)地在 CPU 上運(yùn)行，但是同一時(shí)間僅有一個(gè)進(jìn)程可以在內(nèi)核態(tài)，其他需要進(jìn)入內(nèi)核態(tài)的進(jìn)程只能等待。
kern/spinlock.h 聲明了一個(gè)大內(nèi)核鎖 kernel_lock。它提供了 lock_kernel() 和 unlock_kernel() 方法用于獲得和釋放鎖。在以下 4 個(gè)地方需要使用到大內(nèi)核鎖：

• 在 i386_init()，BSP 喚醒其他 CPU 之前獲得內(nèi)核鎖
• 在 mp_main()，初始化 AP 之后獲得內(nèi)核鎖，之后調(diào)用 sched_yield() 在 AP 上運(yùn)行進(jìn)程。
• 在 trap()，當(dāng)從用戶態(tài)陷入內(nèi)核態(tài)時(shí)獲得內(nèi)核鎖，通過(guò)檢查 tf_Cs 的低 2bit 來(lái)確定該 trap 是由用戶進(jìn)程還是內(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.

實(shí)現(xiàn)比較簡(jiǎn)單，不用細(xì)講。
關(guān)鍵要理解兩點(diǎn)：

• 大內(nèi)核鎖的實(shí)現(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. 
    // 關(guān)鍵代碼，體現(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ù)的實(shí)現(xiàn)，使用它而不是用簡(jiǎn)單的 if + 賦值 是因?yàn)樗且粋€(gè)原子性的操作。

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)匯編，語(yǔ)法在 Lab3 中已經(jīng)講解過(guò)。lock 確保了操作的原子性，其意義是將 addr 存儲(chǔ)的值與 newval 交換，并返回 addr 中原本的值。于是，如果最初 locked = 0，即未加鎖，就能跳出這個(gè) while循環(huán)。否則就會(huì)利用 pause 命令自旋等待。這就確保了當(dāng)一個(gè) CPU 獲得了 BKL，其他 CPU 如果也要獲得就只能自旋等待。

• 為什么要在這幾處加大內(nèi)核鎖
  為了避免多個(gè) CPU 同時(shí)運(yùn)行內(nèi)核代碼，這基本是廢話。從根本上來(lái)講，其設(shè)計(jì)的初衷就是保證獨(dú)立性。由于分頁(yè)機(jī)制的存在，內(nèi)核以及每個(gè)用戶進(jìn)程都有自己的獨(dú)立空間。而多進(jìn)程并發(fā)的時(shí)候，如果兩個(gè)進(jìn)程同時(shí)陷入內(nèi)核態(tài)，就無(wú)法保證獨(dú)立性了。例如內(nèi)核中有某個(gè)全局變量 A，cpu1 讓 A=1， 而后 cpu2 卻讓 A=2，顯然會(huì)互相影響。最初 Linux 設(shè)計(jì)者為了使系統(tǒng)盡快支持 SMP，直接在內(nèi)核入口放了一把大鎖，保證其獨(dú)立性。參見(jiàn)這篇非常好的文章 大內(nèi)核鎖將何去何從
  其流程大致為：
  BPS 啟動(dòng) AP 前，獲取內(nèi)核鎖，所以 AP 會(huì)在 mp_main 執(zhí)行調(diào)度之前阻塞，在啟動(dòng)完 AP 后，BPS 執(zhí)行調(diào)度，運(yùn)行第一個(gè)進(jìn)程，env_run() 函數(shù)中會(huì)釋放內(nèi)核鎖，這樣一來(lái)，其中一個(gè) AP 就可以開(kāi)始執(zhí)行調(diào)度，運(yùn)行其他進(jìn)程。

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

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

輪詢調(diào)度

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

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

• sched_yield()不能同時(shí)在兩個(gè)CPU上運(yùn)行同一個(gè)進(jìn)程。如果一個(gè)進(jìn)程已經(jīng)在某個(gè) CPU 上運(yùn)行，其狀態(tài)會(huì)變?yōu)?ENV_RUNNING。

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

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.

注意以下幾個(gè)問(wèn)題：

• 如何找到目前正在運(yùn)行的進(jìn)程在 envs[] 中的序號(hào)？
  在 kern/env.h 中，可以找到指向 struct Env的指針 curenv，表示當(dāng)前正在運(yùn)行的進(jìn)程。但是需要注意，不能直接由 curenv->env_id得到其序號(hào)。在 inc/env.h 中有一個(gè)宏可以完成這個(gè)轉(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 中實(shí)現(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 中運(yùn)行的用戶進(jìn)程改為以下：

// 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);
...

運(yùn)行 make qemu CPUS=2 可以看到三個(gè)進(jìn)程通過(guò)調(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> 

記錄一下自己遇到的問(wèn)題：
這個(gè) exercise 出現(xiàn)了 triple fault 報(bào)錯(cuò)，查了很久原因。由于是triple fault 肯定是 trap 過(guò)程中的錯(cuò)誤，仔細(xì)檢查發(fā)現(xiàn)是自己的 exercise4 的做法出現(xiàn)了問(wèn)題，一個(gè)非常二的錯(cuò)誤。

// 錯(cuò)誤版本，顯然沒(méi)有更改 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?

大意是問(wèn)為什么通過(guò) lcr3() 切換了頁(yè)目錄，還能照常對(duì) e 解引用?；叵朐?lab3 中，曾經(jīng)寫過(guò)的函數(shù) env_setup_vm()。它直接以內(nèi)核的頁(yè)目錄作為模版稍做修改。因此兩個(gè)頁(yè)目錄的 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?

在進(jìn)程陷入內(nèi)核時(shí)，會(huì)保存當(dāng)前的運(yùn)行信息，這些信息都保存在內(nèi)核棧上。而當(dāng)從內(nèi)核態(tài)回到用戶態(tài)時(shí)，會(huì)恢復(fù)之前保存的運(yùn)行信息。
具體到 JOS 代碼中，保存發(fā)生在 kern/trapentry.S，恢復(fù)發(fā)生在 kern/env.c?？梢詫?duì)比兩者的代碼。
保存：

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

_alltraps:
pushl %ds    // 保存當(dāng)前段寄存器
pushl %es
pushal    // 保存其他寄存器

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

恢復(fù)：

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"    // 恢復(fù)棧頂指針
        "\tpopal\n"    // 恢復(fù)其他寄存器
        "\tpopl %%es\n"    // 恢復(fù)段寄存器
        "\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)建進(jìn)程

現(xiàn)在我們的內(nèi)核已經(jīng)可以運(yùn)行多個(gè)進(jìn)程，并在其中切換了。不過(guò)，現(xiàn)在它仍然只能運(yùn)行內(nèi)核最初設(shè)定好的程序 (kern/init.c) 。現(xiàn)在我們即將實(shí)現(xiàn)一個(gè)新的系統(tǒng)調(diào)用，它允許進(jìn)程創(chuàng)建并開(kāi)始新的進(jìn)程。
Unix 提供了 fork() 這個(gè)原始的系統(tǒng)調(diào)用來(lái)創(chuàng)建進(jìn)程。fork()將會(huì)拷貝父進(jìn)程的整個(gè)地址空間來(lái)創(chuàng)建子進(jìn)程。在用戶空間里，父子進(jìn)程之間的唯一區(qū)別就是它們的進(jìn)程 ID。fork()在父進(jìn)程中返回其子進(jìn)程的進(jìn)程 ID，而在子進(jìn)程中返回 0。父子進(jìn)程之間是完全獨(dú)立的，任意一方修改內(nèi)存，另一方都不會(huì)受到影響。
我們將為 JOS 實(shí)現(xiàn)一個(gè)更原始的系統(tǒng)調(diào)用來(lái)創(chuàng)建新的進(jìn)程。涉及到的系統(tǒng)調(diào)用如下：

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

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.

一個(gè)比較冗長(zhǎng)的練習(xí)。重點(diǎn)應(yīng)該放在閱讀 user/dumbfork.c 上，以便理解各個(gè)系統(tǒng)調(diào)用的作用。
在 user/dumbfork.c 中，核心是 duppage() 函數(shù)。它利用 sys_page_alloc() 為子進(jìn)程分配空閑物理頁(yè)，再使用sys_page_map() 將該新物理頁(yè)映射到內(nèi)核 (內(nèi)核的 env_id = 0) 的交換區(qū) UTEMP，方便在內(nèi)核態(tài)進(jìn)行 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ù)主要是分配了一個(gè)新的進(jìn)程，但是沒(méi)有做內(nèi)存復(fù)制等處理。唯一值得注意的就是如何使子進(jìn)程返回0。
sys_exofork()是一個(gè)非常特殊的系統(tǒng)調(diào)用，它的定義與實(shí)現(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 寄存器的值。那么，它到底是什么時(shí)候返回？這就涉及到對(duì)整個(gè) 進(jìn)程->內(nèi)核->進(jìn)程 的過(guò)程的理解。

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ù)中，子進(jìn)程復(fù)制了父進(jìn)程的 trapframe，此后把 trapframe 中的 eax 的值設(shè)為了0。最后，返回了子進(jìn)程的 id。注意，根據(jù) kern/trap.c 中的 trap_dispatch() 函數(shù)，這個(gè)返回值僅僅是存放在了父進(jìn)程的 trapframe 中，還沒(méi)有返回。而是在返回用戶態(tài)的時(shí)候，即在 env_run() 中調(diào)用 env_pop_tf() 時(shí)，才把 trapframe 中的值賦值給各個(gè)寄存器。這時(shí)候 lib/syscall.c 中的函數(shù) syscall() 才獲得真正的返回值。因此，在這里對(duì)子進(jìn)程 trapframe 的修改，可以使得子進(jìn)程返回0。

sys_page_alloc() 函數(shù)
在進(jìn)程 envid 的目標(biāo)地址 va 分配一個(gè)權(quán)限為 perm 的頁(yè)面。

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ù)
簡(jiǎn)單來(lái)說(shuō)，就是建立跨進(jìn)程的映射。

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ù)
設(shè)置狀態(tài)，在子進(jìn)程內(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é)束。