環(huán)境

ubuntu 20.04 64 系統(tǒng)

正文

在本次實驗將在多個同時運行的用戶程序中實現(xiàn)搶占式多線程(Preemptive Multitasking)。首先解釋一下什么是搶占式多線程：

In computing, preemption is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time. Such changes of the executed task are known as context switches. They are normally carried out by a privileged task or part of the system known as a preemptive scheduler, which has the power to preempt, or interrupt, and later resume, other tasks in the system.
-- wikipedia

第一句話已經(jīng)開宗明義說了什么是搶占式多任務秉版。就是說操作系統(tǒng)會去主動的打斷一個程序的執(zhí)行贤重，不管進程是否合作，并且在將來還會恢復這個任務的執(zhí)行清焕。這個就比較熟悉了并蝗，每個進程都有自己的運行的時間片(time slice)，當時間片結束后秸妥，通過中斷程序（比如收時鐘中斷）來掛起當前在運行的進程滚停，再由調(diào)度算法來決定接下來運行下一個要運行的進程。周而復始粥惧，這樣就能讓cpu一直處于工作狀態(tài)键畴。
下面兩個詞條介紹了介紹了相關內(nèi)容:
Preemptive Multitasking
time-sharing system

在part A，為JOS實現(xiàn)多處理器的功能突雪，實現(xiàn)round-robin調(diào)度起惕，增加最基本的進程管理的系統(tǒng)調(diào)用
在part B，將會實現(xiàn)一個fork（）咏删，它能夠讓用戶進程來通過自我拷貝來創(chuàng)建一個新的進程
在part C, 還會實現(xiàn)一個IPC(inter-process communication), 使得不同的用戶程序能夠相互之間通信惹想。然后還要實現(xiàn)時鐘中斷以及搶占式調(diào)度。

Part A: Multiprocessor Support and Cooperative Multitasking

在本次實驗的第一部分當中督函，首先需要讓JOS能夠在多處理器的電腦上嘀粱，然后實現(xiàn)JOS的一些system calls從而創(chuàng)建新的用戶程序。此外還需要實現(xiàn)cooperative round-robin調(diào)度辰狡，當前進程自愿放棄CPU的時候锋叨，kernel可以從當前進程切換到另外一個進程。在稍后的part C當中搓译，將會實現(xiàn)搶占式調(diào)度悲柱，讓內(nèi)核一段時間后從用戶進程中獲得CPU（即使用戶進程沒有主動放棄CPU）锋喜。
PS：

The term preemptive multitasking is used to distinguish a multitasking operating system, which permits preemption of tasks, from a cooperative multitasking system wherein processes or tasks must be explicitly programmed to yield when they do not need system resources.

這里說明了搶占式都任務和協(xié)作式多任務的區(qū)別些己。

Multiprocessor Suppport

我們將會在JOS中實現(xiàn)“symmetric multiprocessing”(SMP),一個多處理器模型，它意味著所有的CPU都可以訪問系統(tǒng)資源嘿般，比如說內(nèi)存和IO總線段标。盡管所有的CPU在SMP的中所具備的功能都是相同的，在引導的時候這些CPU可以分為兩類：bootstrap processor(BSP)負責初始化系統(tǒng)并且來引導操作系統(tǒng)炉奴；application processors(APs)在操作系統(tǒng)啟動后由BSP來激活逼庞。哪一個處理器作為BSP是由BIOS來指定。目前為止瞻赶，現(xiàn)有的JOS還是運行在BSP之上的（這里的意思就是之前我們做的Lab所實現(xiàn)的代碼都還是在BSP上赛糟，還沒有引入多處理器的功能）派任。
在一個SMP系統(tǒng)當中，每一個CPU都一個accompanying local APIC uint璧南。LAPIC units負責位系統(tǒng)傳遞中斷用的掌逛。LAPIC通過一個標識符來表示它所連接的CPU。在本次lab中司倚，我們將會充分使用一下LAPIC的基本功能(kern/lapic.c)：

• 讀取LAPIC標識符來說明我們當前運行的代碼是在哪個CPU上(see cpunum())
• 從BSP中發(fā)送STARTUP IPI（interprocessor interrupt）到APs來喚醒其他的CPU(see lapic_startup())
• 在part C中豆混，我們要實現(xiàn)一個LAPIC一個內(nèi)置的定時器來出發(fā)時鐘中斷，以此來支持搶占式調(diào)度(see apic_init())

一個處理器訪問它的LAPIC通過 memory-maped I/O(MMIO).在MMIO中动知，有一部分的物理內(nèi)存會被映射為I/O映射皿伺，所以通常的load/stroe指令可以用于訪問這些設備的寄存器（我們操作顯存可以用load/store指令，操作一些其他的硬件可以用in/out指令）盒粮。我們已經(jīng)見識VGA的IO hole(0xA0000-0xC0000,這一部分是直接給顯存使用的)鸵鸥。LAPIC 在物理地址0XFE00_000開始的一個IO hole當中(總共有32MB)，我們不需要完全用到拆讯。JOS的虛擬內(nèi)存留下了4MB的內(nèi)存空間來完成這個事脂男。因為在后面的實驗當中將會介紹更多的MMIO，所以現(xiàn)在需要寫一個簡單的函數(shù)來為這塊區(qū)域分配內(nèi)存种呐。

這上面的內(nèi)容比較難懂宰翅，建議參考MultiProcessor Specification。APIC：advanced programmable interrupt controller爽室。注意他的定語advanced汁讼，所以我們首先需要知道什么是PIC（programmable interrupt controller）。PIC就是用于處理來自外設的一些中斷的（比如說時鐘中斷阔墩，IO設備發(fā)出的中斷）嘿架，PIC能夠對這些中斷設置優(yōu)先級從而使得CPU來執(zhí)行最合適的中斷。PIC是可編程的啸箫，也就是說我們可以寫入代碼來決定它的行為耸彪。比較經(jīng)典的比如說8259A芯片，設計用于intel 8085和intel 8086處理器的.8259A--維基百科忘苛。
APIC可以兼容PIC蝉娜，但是它應該比PIC具有更多的功能（沒去認真了解APIC過，這是我想當然的想法）扎唾。前面說到每一個CPU都有自己的local APIC.如下圖所示:

APIC confuguration

剩下還有一個內(nèi)存就是關于MMIO的咐蚯，在內(nèi)存當中有一塊地址是被用于MMIO的如下圖所示童漩。

memory layout

實現(xiàn)kern/pmap.c中的mmio_map_regin()。查閱代碼kern/lapic.c中的lapic_init來理解它是如何被使用的期奔。你還需要實現(xiàn)下一個Exercise才能測試mmio_map_regin()

mmio_map_region()：
如上面的圖所示侧馅，LAPIC所占據(jù)的物理地址是從0xFEF0_0000開始的1MB內(nèi)存。但是前面說了JOS不需要很大的MMIO呐萌。我們只需要一個4MB的內(nèi)存用于MMIO馁痴。這一道題目要做的就是將虛擬內(nèi)存[MMIOBASE,MMIOBASE+PTSIZE]這塊區(qū)域映射到實際的LAPIC的物理地址去。當我們需要訪問LAPIC的時候肺孤，只需要訪問MMIOBASE這一段內(nèi)存就行罗晕。

    void* ret = (void*)base;
    size = ROUNDUP(size,PGSIZE);
    if( base + size > MMIOLIM) {
        panic("mmio_map_region: size of MMIO overflow");
    }
    boot_map_region(kern_pgdir,base,size,pa,PTE_PCD|PTE_PWT|PTE_W);
    base += size;
    return ret;

Application Processor Bootstrap

在啟動APs之前，BSP應該收集和多處理器系統(tǒng)相關的信息赠堵，比如說有多少個CPU小渊，他們的APIC ID（前面說過，APIC ID用于標識他們是哪個CPU）以及MMIO的地址茫叭。kern/mpconfig.c的mp_init()函數(shù)從MP configuration table（位于BIOS的內(nèi)存范圍內(nèi)）中讀取這些信息酬屉。
kern/init.c中的boot_aps()函數(shù)drives AP bootstrap process. APs最開始的時候是實模式(real mode，回想一下實模式的關鍵點)揍愁，與boot/boot.S中的bootloader和相似呐萨，所以boot_aps()將AP entry code復制到一個在實模式下可用的地址(實模式的地址范圍為0-1MB且并不是所有的內(nèi)存都是可用的，還有IO hole吗垮，見上圖)垛吗。不想bootloader,我們可以控制AP從哪兒開始執(zhí)行代碼凹髓。我們將entry code復制到0x7000(MPENTRY_PADDR)烁登。但是這個地址需要是未使用的(所以不能放到IO hole中)并且還需要page-aligned（為什么需要page-alinged看Multiprocesscor specification section B 4.2，里面有解釋）。
在那之后(設置好APs的entry code之后)饵沧，boot_aps()一個接一個激活APs,設置好CS:IP,從而讓APs可以在此運行代碼(在我們的例子當中就是MPENTRY_PADDR)锨络。在kern/mpentry.S中的entry code和在boot/boot.S中的代碼十分相似。經(jīng)過一些設置后狼牺，為各個AP開啟paging羡儿，還要設置好這個CPU所屬的GDT。然后再調(diào)用mp_main()函數(shù)（在kern/init.c當中）是钥。boot_aps()函數(shù)等待AP發(fā)出一個CPU_STARTED的信號掠归，然后再接下去激活下一個AP。
Exercise 2:

閱讀kern/init.c中的boot_aps()以及mp_main()的代碼悄泥，以及mpentry.S中的匯編代碼虏冻。確保你理解了在引導APs的時候的權限轉換。然后修改你的page_init()函數(shù)弹囚，將MPENTRY_PADDR從free list中移除厨相，這樣才可以安全的復制代碼到這個物理地址。驗證是否通過測試點check_page_free_list().

代碼實現(xiàn):
前面說到我們要將AP的entry code放到MPENTRY_PADDR這個地址處鸥鹉。所以我們要將這塊內(nèi)存不放到free_list去蛮穿。首先我們需要計算entry code占據(jù)了多少的內(nèi)存，是不是超過了一個頁的大小毁渗。此外践磅，在lab1當中，low memory的部分原來都是空閑可用的灸异，現(xiàn)在在這塊內(nèi)存區(qū)域當中加入了entry code音诈，相當于在里面挖了一個洞。

    pages[0].pp_ref = 1;

    // IO hole之前的內(nèi)存都是free的
    //這部分的解釋可以看lab1 Low memory部分
    size_t i ;

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

    //在lab4中绎狭，我們要在內(nèi)存當中留出空間放mpentry.S中的代碼
    //思路细溅，1. 計算mpentry.S的代碼所需要多少內(nèi)存，并且計算的到的數(shù)值還要向上ROUNDUP
    //然后將這些內(nèi)存標記為已被使用
    extern unsigned char mpentry_start[], mpentry_end[];
    int mp_size = mpentry_end - mpentry_start;
    int mp_size_alinged = ROUNDUP(mp_size,PGSIZE);
    for(; i < (MPENTRY_PADDR + mp_size_alinged) / PGSIZE; i++ ) {
        pages[i].pp_ref = 1;
    }
    for (; i < npages_basemem; i++) {
        pages[i].pp_ref = 0;

        //這里設想一下鏈表的頭插法就理解了儡嘶！
        pages[i].pp_link = page_free_list;

        //&pages[i]并不是真正的空閑頁的地址喇聊，這是Pages這個數(shù)組中的元素的地址
        //page2pa這個函數(shù)才是得到真正的地址的。
        page_free_list = &pages[i];
    }

    //IO hole
    for(; i < EXTPHYSMEM/PGSIZE; i++) {
        pages[i].pp_ref = 1;
    }

    //Kernel占據(jù)了從0x0010_0000 - 0x0fff_ffff蹦狂，這一部分是kernel的 
    //所以第一個空閑的頁就緊跟在內(nèi)核之后誓篱，所以 end of IO hole ~ first free page 就是內(nèi)核占據(jù)的內(nèi)存
    ///PADDR是將虛擬地址轉為實際的物理地址
    physaddr_t first_free_addr = PADDR(boot_alloc(0));
    size_t first_free_page = first_free_addr/PGSIZE;

    for(; i < first_free_page; i++) {
        //這部分內(nèi)存被內(nèi)核使用的
        pages[i].pp_ref = 1;
    }

    //內(nèi)核之后的所有內(nèi)存都是free的
    for(; i < npages; i++ ) {
        pages[i].pp_ref = 0;
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }

Question

比較一下kern/mpentry.S以及boot/boot.S中的代碼。牢記kern/mpentry.S是被編譯連接到地址高于KERNBASE的凯楔，MPBOOTSPHYS的目的是什么窜骄？為什么他要在kern/mpentry.S中而不是在boot/boot.S中？換句話說摆屯，如果省略了這個會出現(xiàn)什么問題邻遏？提示：回想一下鏈接地址和加載地址之間的區(qū)別

在我們編譯的時候，我們將鏈接的地址放在了內(nèi)存很高的地方。所以mpentry.S中的編號經(jīng)過編譯后也是很高的地址准验。但是mpentry.S這些代碼是要在實模式中運行的赎线。那么原來鏈接的高地址自然是不能用的。所以要將虛擬地址轉為物理地址糊饱。通過MPBOOTSPHYS這個宏垂寥，就將虛擬地址轉為了在實模式下可用的地址。這樣才可以初始化好entry code從而正常的激活其他處理器另锋。

Per-CPU State and Initialization

當寫一個多處理器的系統(tǒng)的時候滞项，很重要一點就是每一個CPU的狀態(tài)都是私有的，kern/cpu.h中的結構體CpuInfo定義每一個CPU的狀態(tài)夭坪。cpunum() 會返回執(zhí)行這個函數(shù)的CPU的ID蓖扑，這個ID可以用于在數(shù)組cpus中索引對應的CPU。thiscpu這個宏就是當前CPU所屬的CpuInfo結構台舱。

下面是一些關于per-CPU state你需要知道的:

• Per-CPU kernel stack
  因為多個CPU能夠同時trap到內(nèi)核當中律杠，我們需要為每一個CPU都設置他們專屬的內(nèi)核來防止他們之間相互影響。二維數(shù)組percpu_kstacks[NCPU][KSTKSIZE]為每一個CPU都預留了棧的大小竞惋。
• Per-CPU TSS and TSS descriptor:
  每一個CPU的TSS (task state segment)同樣也需要指定每一個CPU的內(nèi)核棧在哪柜去。第i個CPU所屬的TSS粗放在cpus[i].cpu_ts當中，并且與之對應的TSS descriptor在GDT中的位置為gdt[(GD_TSS0 >> 3) + i]拆宛。那個全局的ts（在kern/trap.c當中就不再使用了）
  PS:
  這一點應該很好懂嗓奢。前面我說了每個CPU都有自己的內(nèi)核棧，那么很自然的每個CPU都需要有自己的TSS浑厚。這樣當中斷發(fā)生的時候每個CPU才可以在自己的內(nèi)核棧內(nèi)完成棧切換股耽，原程序的上下文保存的工作（context switch）
• Per-CPU system registers
  所有的寄存器，包括系統(tǒng)寄存器钳幅，對于CPU來說也是私有的物蝙，初始化系統(tǒng)寄存器的指令，比如說lcr3(), lr(),lgdt()等等指令都需要在每一個CPU都運行過敢艰。env_init_percpu()和trap_init_percpu()函數(shù)就是為了這個目的诬乞。

Exercise 3：

修改mem_init_mp()（在kern/pmap.c）中的代碼，初始化好每一個CPU的棧钠导。每一個棧的大小是KSTKSIZE加上SKTKGAP字節(jié)的未映射的棧震嫉。此時的代碼可以通過測試點 check_kern_pgdir()

代碼實現(xiàn):
實現(xiàn)這道題的關鍵點要認真看下mem_init_mp()里面的說明以及memlayout.h中地址空間的分配。注釋里面說到我的們棧分為兩個部分：一個部分是用于普通使用的棧的牡属，另外一部分的棧是用于作為 guard page的票堵。前面說到我們已經(jīng)為各個CPU預留了棧的內(nèi)存，在數(shù)組percpu_kstacks[i]就表示第i個cpu的棧的大小〈ぃ現(xiàn)在我們只需要從KSTKTOP開始逐漸往下為各個CPU的棧地址映射起來即可悴势。

    for(int i = 0; i < NCPU; i++) {
        int kstacktop_i = KSTACKTOP - i * (KSTKSIZE + KSTKGAP);
        boot_map_region(kern_pgdir,
                        kstacktop_i - KSTKSIZE,
                        KSTKSIZE,
                        PADDR(&percpu_kstacks[i]),
                        PTE_P | PTE_W);
    }

Exercise 4:

trap_init_percpu()(在kern/init.c當中)為BSP初始化了TSS以及對應的TSS descriptor窗宇。但是它只能在lab3當中正常使用，現(xiàn)在CPU變多了就不管用了瞳浦。修改代碼讓其對所有CPU都生效。

最開始的時候废士，我陷入了一個誤區(qū)：我一開始以為需要在trap_init_percpu()中使用一個for循環(huán)來初始化叫潦。但是實際上不是的。理解這個代碼怎么寫官硝，首先需要來過一些激活其他的處理器的流程：

1. 在kern/init.c中調(diào)用了boot_aps()函數(shù)
2. boot_aps()函數(shù)矗蕊，為每個AP設置好entry code
3. 然后boot_aps()接著調(diào)用調(diào)用lapic_startap()函數(shù)去發(fā)送STARTUP IPI來激活AP
4. AP激活后兑宇，進入到entry code(mpentry.S)后蜗元，進行必要的設置后，在跳轉到的mp_main()函數(shù)
5. mp_main()函數(shù)中調(diào)用trap_init_percpu()函數(shù)券敌，來設置每一個處理器的它自己的TSS等內(nèi)容

過了一遍上面的流程岖研，我們知道每一個CPU被激活后都要去調(diào)用trap_init_percpu()函數(shù)卿操。我們并不需要在trap_init_percpu()里面加入for循環(huán)。注意在代碼實現(xiàn)的時候孙援，還需要結合注釋來獲得一些提示害淤。

代碼實現(xiàn):
參考原來給的代碼。應該可以理解我的代碼的意思拓售。我們要為每一個CPU設置好他自己的TSS窥摄。 還要設置好GDT。

    thiscpu->cpu_ts.ts_esp0 = KSTACKTOP -  cpunum() * (KSTKSIZE + KSTKGAP);
    thiscpu->cpu_ts.ts_ss0 = GD_KD;
    thiscpu->cpu_ts.ts_iomb= sizeof(struct Taskstate);
    gdt[(GD_TSS0 >> 3) + cpunum()] = SEG16(STS_T32A, 
                                    (uint32_t)(&thiscpu -> cpu_ts),
                                    sizeof(struct Taskstate) -1 ,
                                    0);
    gdt[(GD_TSS0 >> 3) + cpunum()].sd_s = 0;

    // ltr(GD_TSS0 + sizeof(struct Segdesc) * cpunum());
    ltr(((GD_TSS0 >> 3) + cpunum()) << 3);

實驗結果:
完成上面的代碼以后础淤，運行make qemu CPUS=4,然后會看到下面的結果崭放，因為在**mp_init()中最后有一個死循環(huán)所以，代碼不會繼續(xù)執(zhí)行鸽凶。但是我們可以看到此時所有的APs都被喚醒了币砂。不過我圖里面有多個ENV，這是我做了后面的內(nèi)容忘了把代碼注釋掉的結果玻侥，問題不大道伟。:

make qemu CPUS=4

Locking

我們當前的代碼停在了mp_main()（這個函數(shù)里面有個死循環(huán)）。在讓AP更進一步之前使碾，我們首先需要解決多個CPU運行代碼而帶來的race condition問題蜜徽。最簡單的方法就是使用一個大的內(nèi)核鎖(big kernel lock)。所謂大鎖就是當一個進程進入內(nèi)核后就會持有他票摇，當進程返回到用戶態(tài)的時候在釋放鎖(user mode)拘鞋。在這樣的模型之下，多個用戶進程可以在多個CPU上并行運行矢门，但是只有一個用戶進程可以進入到內(nèi)核態(tài)盆色，如果其他進程需要進入到內(nèi)核則需要等待灰蛙。
kern/spinlock.c聲明了一個內(nèi)核鎖，叫做kernel_lock隔躲。他同樣提供了lock_kernel()和unlock_kernel()函數(shù)來獲得鎖以及釋放鎖摩梧。你應該將內(nèi)核鎖應用到下面幾個函數(shù)去。

• 在i386_init(), 在BSP喚醒其他APs之前獲得鎖宣旱。
• 在mp_main()當中,在初始化AP之后獲得鎖仅父，然后調(diào)用sched_yield()來運行進程。
• 在trap()中浑吟，如果trap來自用戶程序笙纤，那么就獲得鎖。對于如何判斷trap是否來自用戶组力，用tf_cs來判斷省容。
  PS：
  如果對于保護模式有過經(jīng)驗對于如何判斷是來自用戶程序還是內(nèi)核，這一點判斷應該十分簡單燎字。我們在trap()函數(shù)中上鎖腥椒，當別的程序也trap到內(nèi)核的時候，若此時已經(jīng)有進程進入了trap候衍，那么新進入trap的進程就要等待了寞酿。**這樣我們就達到了只有一個用戶進程可以進入到內(nèi)核態(tài)的目的。
• 在env_run()當中脱柱，在返回到用戶程序之前釋放鎖伐弹。不要太早也不要太晚釋放鎖。
  Exercie 5:

將lock_kernel()和unlock_kernel()應用到上述代碼榨为。

代碼實現(xiàn):
這個比較簡單惨好。注釋中給我們的提示也比較多了，就不過多講解了随闺。

   //在kern/init.c中
    lock_kernel();
    // Starting non-boot CPUs
    boot_aps();

  //在kern/inic.c中的mp_main()當中
    lock_kernel();
    sched_yield();

//kern/trap.c中的trap()當中
    if ((tf->tf_cs & 3) == 3) {
        // Trapped from user mode.
        // Acquire the big kernel lock before doing any
        // serious kernel work.
        // LAB 4: Your code here.
        lock_kernel();
        assert(curenv);

//kern/env.c中的env_run()當中
    lcr3(PADDR(curenv->env_pgdir));
    unlock_kernel();
    // cprintf("eax:%d\n",curenv->env_tf.tf_regs.reg_eax);
    env_pop_tf(&(curenv->env_tf));

Question:

現(xiàn)在看起來內(nèi)核鎖保證了只有一個CPU可以運行內(nèi)核代碼日川。那我們?yōu)槭裁催€需要對每一個CPU都設置一個棧呢？描述一下當多個CPU共享一個棧的時候會發(fā)生什么矩乐。

對于這個問題龄句，一開始沒有想明白如果使用共享的棧問題會出現(xiàn)在哪里。不過仔細一想散罕，問題會出現(xiàn)在trap,并不是已進入trap就加鎖分歇，回想一下進入trap的過程，我們在_alltraps那里并沒有加鎖欧漱，這里會出現(xiàn)一個問題职抡。前面實驗我們知道,trap(struct Trapframe *tf)，為了取得當前trap的進程误甚，我們在_alltraps中執(zhí)行了push esp指令缚甩。設想一下這樣一個場景谱净，多個CPU都執(zhí)行了_alltraps的代碼，當他們都進入trap以后擅威。那么trap()的參數(shù)tf指向的是同一個tf壕探，另外一個CPU所需要的tf沒了。

Round-Robin Scheduling

下一個任務就是在JOS實現(xiàn)進程調(diào)度了郊丛，以Round-Robin的方式李请。Round-Robin調(diào)度簡而言之就是每一個進程都有機會得到CPU，沒有引入優(yōu)先級的概念宾袜。多個進程輪流使用CPU捻艳。
Round-Robin 在JOS按照如下方式實現(xiàn):

• kern/sched.c中的函數(shù)sched_yield()函數(shù)負責選擇下一個需要運行的進程驾窟。找到在當前正在運行的進程之后的狀態(tài)為ENV_RUNNABLE的進程庆猫，然后調(diào)用env_run()來運行新的進程
• sched_yield()不能將同一個進程運行在別的CPU上。通過判斷當前進程的狀態(tài)可以知道他是否運行在某個CPU上绅络。
• 我們實現(xiàn)了一個新的系統(tǒng)調(diào)用月培，sys_yield()，它通過調(diào)用sched_yield()來放棄CPU然后切換到新的進程恩急。

Exercise 6:
在sched_yield()中實現(xiàn)round-robin調(diào)度杉畜，不要忘了在syscall()中加入sys_yield();
確保mp_main()中調(diào)用sched_yield()。
修改kern/init.c中的代碼衷恭，創(chuàng)建三個進程都調(diào)用了user/yield.c程序此叠。
運行make qemu和make qemu CPUS=2來測試結果

代碼實現(xiàn):
結合前面的描述以及sched_yiled()中的代碼注釋。實現(xiàn)這個代碼應該不難随珠。

    struct Env* current_proc = thiscpu->cpu_env; //當前cpu正在運行的進程
    int startid = (current_proc) ? ENVX(current_proc->env_id) : 0; //返回在當前CPU運行的進程ID
    int next_procid;
    for(int i = 1; i < NENV; i++) {
        // 找到當前進城之后第一個狀態(tài)為RUNNABLE的進程
        next_procid = (startid+i) % NENV;
        if(envs[next_procid].env_status == ENV_RUNNABLE) {
            env_run(&envs[next_procid]); //運行新的進程
        }
    }

    //注釋里面說到了灭袁，不能將當前正在運行的進程運行到別的CPU上。如果之前運行在當前CPU的進程仍然在運行
    //且沒有其他可以runnable的進程窗看，那么就繼續(xù)運行原來的進程
    if(envs[startid].env_status == ENV_RUNNING && envs[startid].env_cpunum == cpunum()) {
        env_run(current_proc); //繼續(xù)運行原來的進程
    }

注意,mp_main()的注釋信息告訴我們要把那個死循環(huán)注釋了茸歧。

void
mp_main(void)
{
    // We are in high EIP now, safe to switch to kern_pgdir 
    lcr3(PADDR(kern_pgdir));
    cprintf("SMP: CPU %d starting\n", cpunum());

    lapic_init();
    env_init_percpu();
    trap_init_percpu();
    xchg(&thiscpu->cpu_status, CPU_STARTED); // tell boot_aps() we're up

    // Now that we have finished some basic setup, call sched_yield()
    // to start running processes on this CPU.  But make sure that
    // only one CPU can enter the scheduler at a time!
    //
    // Your code here:
    lock_kernel();
    sched_yield();
    // Remove this after you finish Exercise 6
    // for (;;);
}

最后再加入幾個新的進程，都調(diào)用yield程序显沈。

    // Touch all you want.
    //ENV_CREATE(user_hello, ENV_TYPE_USER);
    // ENV_CREATE(user_primes, ENV_TYPE_USER);
     ENV_CREATE(user_yield, ENV_TYPE_USER);
     ENV_CREATE(user_yield, ENV_TYPE_USER);
     ENV_CREATE(user_yield, ENV_TYPE_USER);

Question:

在實現(xiàn)env_run()當中软瞎，我們使用了lcr3()。在調(diào)用lcr3()之前和之后拉讯，我們都使用參數(shù)傳給env_run()的參數(shù) e涤浇。在更新cr3寄存器之后，MMU中的東西就失效了魔慷。但是參數(shù)e還是有效的芙代。為什么呢？

回答這個問題不難盖彭。還記得之前在xv 6book當中纹烹，它里面提到了任何一個進程的地址空間分為兩部分页滚。一部分稱為用戶程序部分，另外一部分稱為內(nèi)核部分铺呵。內(nèi)核部分在任何一個進程當中都是相同的裹驰，所以就算發(fā)生了切換，但是并沒有改變內(nèi)核地址部分片挂。所以這些參數(shù)還是可用的幻林。

當內(nèi)核從一個進程切換到另外一個進程，必須保證原來進程的寄存器要被保存下來以便于未來恢復這個進程的執(zhí)行音念。 這一切是怎么發(fā)生的?

回答這個問題沪饺，只需要理一下切換進程的過程。（到目前為止闷愤，我們還沒有引入時間片輪轉整葡，只是最簡單的調(diào)度）。

1. 調(diào)用系統(tǒng)調(diào)用sys_yield()使得當前進程主動放棄CPU讥脐。
2. sys_yield()調(diào)用lib/syscall.c中的syscall()進入系統(tǒng)調(diào)用
3. syscall()函數(shù)調(diào)用Int 指令來進入到trap
4. trapentry.S中執(zhí)行到_alltraps將必要的參數(shù)壓入棧后
5. 調(diào)用trap()函數(shù)遭居，然后通過curenv->env_tf = *tf來將內(nèi)核棧當中的用戶程序的寄存器上下文Trapframe賦值給當前進程的env_tf結構。用于恢復將來恢復進程的運行旬渠。
6. trap中調(diào)用trap_dispatch()函數(shù)最終執(zhí)行到kern/syscall.c中的對應的中斷處理函數(shù)俱萍。

PS:
curenv->env_tf = *tf這語句將原來的進程的上下文復制到它自己的env_tf。但是我不理解的是：內(nèi)核中一個envs數(shù)組（定義在env.c當中）來持有所有的進程告丢。為什么在這里看不到以envs[index]->env_tf這種方式來修改進程的寄存器信息枪蘑。沒想通，不過岖免，有一點可以非常明白的是岳颇，在進入中斷后，肯定需要從內(nèi)核棧當中拿到用戶進程的寄存器信息觅捆，然后需要賦值給對應進程的寄存器結構(struct Tramframe)

在_alltraps我們將原來程序的寄存器壓入到了棧當中赦役，就這樣保存了context。sched_yield()調(diào)度完成后栅炒，調(diào)用env_run()跳轉到下一個要執(zhí)行的程序（也可能恢復到原來的進程繼續(xù)執(zhí)行）掂摔。

System Calls For environment Creation

現(xiàn)在你的內(nèi)核可以能夠運行并且能夠在多個用戶進程之間切換了，不過目前仍然還是運行一些內(nèi)核初始化好的進程赢赊。你現(xiàn)在需要實現(xiàn)JOS的一些系統(tǒng)調(diào)用來創(chuàng)建用戶進程并且運行乙漓。
Unix提供了一個fork()這一進程創(chuàng)建原語。Unix fork()拷貝當前整個地址空間的內(nèi)容(父進程)到
新創(chuàng)建的進程當中去（子進程）释移。兩者唯一的區(qū)別就是他們的ID以及他們的父進程ID叭披。在父進程中，fork()返回的是子進程ID玩讳，然而在子進程中fork()返回0涩蜘。默認情況下嚼贡，每一個進程的地址空間都是私有的。
我們需要實現(xiàn)下面的system calls來實現(xiàn)fork():

• sys_exofork():
  這個系統(tǒng)調(diào)用創(chuàng)建了一個新的進程同诫，但是沒有映射地址空間中屬于用戶的那部分粤策，而且此時這個進程還不是可運行的。當調(diào)用sys_exofork()函數(shù)的時候误窖，新創(chuàng)建的進程與父進程有相同的寄存器的值叮盘。在父進程中，sys_exofork()返回新創(chuàng)建進程的ID霹俺。在進程中柔吼，返回0。（因為在最開始的時候子進程被標記為 not runnable丙唧，sys_fork()并不會直接返回知道父進程將子進程標記為可運行的狀態(tài),沒懂沒關系愈魏，看完代碼就懂了）。
• sys_env_status:
  設置指定進程的狀態(tài)為ENV_RUNNABLE或者ENV_RUNNBLE艇棕。這個系統(tǒng)調(diào)用用于將一個進程標記為可運行的蝌戒。
• sys_page_alloc:
  分配一個物理頁串塑，并且將他映射到給出的虛擬地址去沼琉。
• sys_page_map:
  復制當前頁的映射到另外一個進程的地址空間去，這樣一來兩個進程都可以通過相同的虛擬地址訪問相同的物理地址了桩匪。
• sys_page_umap:
  取消所給出的虛擬地址到物理地址的映射打瘪。

上面所有的system calls都接受進程ID作為參數(shù)，JOS認為0表示當前正在運行的進程傻昙。這個是現(xiàn)在envid2nev()中闺骚。
Exercise 7:

實現(xiàn)上面描述的system calls,還要再kern/syscall.c中的syscall()加入他們。你需要很多kern/pmap.c和kern/env.c中的函數(shù)妆档，尤其是envid2env()僻爽。還要記得給envid2env()傳入一個1。最后運行dumbfork程序來判斷有用贾惦。

下面先給出代碼實現(xiàn)胸梆，最后再來分析一下fork() 的整個過程。注意代碼實現(xiàn)結合他給的注釋

sys_exofork():
此函數(shù)并不會真正的讓一個進程直接可以運行须板。他只是分配一個新進程的地址空間碰镜。新分配的進程就是子進程，他有和父進程相同的寄存器的值习瑰，實現(xiàn)這一點只要把當前進程的trapframe復制給子進程就好了绪颖。我們用env_alloc()來創(chuàng)建新的進程,代碼里面有一句child->env_tf.rf_regs.eax=0后面會解釋的。

    struct Env* child;
    int ret_value;
    if((ret_value = env_alloc(&child,curenv->env_id)) < 0) {
        return ret_value ;
    }
    child->env_status = ENV_NOT_RUNNABLE;
    child->env_tf = curenv->env_tf;
    // cprintf("ip:%x\n",curenv->env_tf.tf_eip);
    child->env_tf.tf_regs.reg_eax = 0;
    return child->env_id;

sys_env_set_status():
這個函數(shù)用于設置進程的狀態(tài)甜奄。通過注釋我們知道我要判斷進程是否屬于ENV_RUNNABLE或者ENV_NOT_RUNNABLE狀態(tài)柠横。還要判斷對應envid的進程是否存在窃款。在最后，設置進程的狀態(tài)牍氛。

    int ret_value;
    struct Env* proc;
    if ((ret_value = envid2env(envid,&proc,1)) < 0) {
        return -E_BAD_ENV;
    }
    if(status != ENV_NOT_RUNNABLE && status != ENV_RUNNABLE) {
        return -E_INVAL;
    }
    proc->env_status = status;
    return 0;

sys_page_alloc():
這道題的條件比較多雁乡，乍一看十分嚇人。不過認真看代碼上面的注釋糜俗，可以理解每個條件的意思踱稍。不過多贅述。有一點就是悠抹，當我們判斷perm是否合適的時候珠月，用 &（和運算）就可以。

    if((uintptr_t)va >= UTOP || PGOFF(va)) {
        return -E_INVAL;
    }
    struct Env* env;
    int ret_value;
    if ((ret_value = envid2env(envid,&env,1)) < 0) {
        return -E_BAD_ENV;
    }
    if(!(perm & PTE_SYSCALL)) {
        return -E_INVAL;
    }
    struct PageInfo* new_page = page_alloc(ALLOC_ZERO);
    if(new_page == NULL) {
        return -E_NO_MEM;
    }
    if( (ret_value = page_insert(env->env_pgdir,new_page,va,perm)) < 0) {
        page_free(new_page);
        return ret_value;
    }
    return 0;

sys_page_map():
這個函數(shù)要做的工作是楔敌，將已經(jīng)存在的進程的某一段物理與虛擬地址之間的映射關系復制到新的進程當中去啤挎。所以必然就涉及到頁的查找以及插入。同樣的上面也有一大堆的條件需要我們?nèi)ヅ袛嗦汛铡Ｕ堊屑氶喿x注釋信息庆聘。

    struct Env *src_env,*dst_env;
    int ret_value;
    pte_t*pg_table_entry;
    struct PageInfo* page;
    if( envid2env(srcenvid,&src_env,1) < 0 ||envid2env(dstenvid,&dst_env,1) < 0) {
        return -E_BAD_ENV;
    }
    if((uintptr_t)srcva >= UTOP || PGOFF(srcva) || (uintptr_t)dstva >= UTOP || PGOFF(dstva)) {
        return -E_INVAL;
    }
    if((perm | PTE_SYSCALL) != PTE_SYSCALL) {
        return -E_INVAL;
    }
    page = page_lookup(src_env->env_pgdir,srcva,&pg_table_entry);
    if(page == NULL) {
        return -E_INVAL;
    }
    if(page_insert(dst_env->env_pgdir,page,dstva,perm) < 0) {
        return -E_NO_MEM ;
    }
    return 0;

sys_page_umap():
這個函數(shù)要完成的工作是，就給出的虛擬地址取消映射勺卢。注釋提示我們使用page_remove()伙判。這個也不難，直接給出代碼實現(xiàn).

    struct Env* env;
    if(envid2env(envid,&env,1) < 0) {
        return -E_BAD_ENV;
    }
    if( (uintptr_t)va >= UTOP || PGOFF(va)) {
        return -E_INVAL;
    }
    page_remove(env->env_pgdir,va);
    return 0;

kern/syscall.c中的syscall()：
最后我們要在syscall()中加入對應的case黑忱，這個好懂宴抚。代碼如下：

    case SYS_page_alloc:
        return sys_page_alloc((envid_t)a1, (void * )a2, (int )a3);
    case SYS_page_map:
        return sys_page_map((envid_t) a1, (void *) a2, (envid_t) a3, (void *) a4, (int) a5);
        
    case SYS_page_unmap:
        return sys_page_unmap((envid_t) a1, (void *) a2);

    case SYS_exofork:
        // cprintf("sys_exofork()\n");
        return sys_exofork();

    case SYS_env_set_status:
        return sys_env_set_status((envid_t) a1, (int) a2);

完成上面的代碼后，運行dumbfork甫煞。輸入make run-dumbfork可以得到以下結果（部分）：

上述代碼的一點思考

1. 內(nèi)核是如何做到fork的時候菇曲，父進程返回子進程的ID，子進程返回0抚吠？
   接下來為了講述清楚這個問題可能篇幅非常的長常潮。
   上面這個問題說起來好像一句非常具有迷惑性的話調(diào)用一個fork()兩個返回值。這是網(wǎng)上很多人都這么說的楷力。乍一看好像是這么一回事喊式，不過事實不是這樣的，真正的是原因是兩個返回值分別在子進程和父進程分別返回弥雹。

具體來看看是如何實現(xiàn)的垃帅。曾經(jīng)我一直奇怪，如果子進程和父進程擁有相同的代碼剪勿，那么豈不是無限套娃一直創(chuàng)建進程了贸诚？哈哈，想想就比較搞笑。實際上不是的酱固，我們新創(chuàng)建的進程械念，雖然說在地址空間上擁有和父進程相同的東西。但是它的eip指向的是fork()之后的代碼运悲。比如說以下的代碼:

int main {
  ...
  int pid = fork(); 
  printf("hello world");
  ...
  return 0
}

當我們創(chuàng)建一個子進程后龄减，此時父子進程的eip都是指向printf("hello world"),不過這個只是宏觀上的，具體的匯編代碼稍微和這有些不一樣班眯。所以并不會無限套娃希停。

回到我們的dumbfork中的代碼來解釋。sys_exofork()是一個定義在lib.h中的inline函數(shù)署隘。inline函數(shù)會在編譯的時候直接被替換為對應的代碼宠能。進入到sys_exofork()來看看。

// 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));
    // cprintf("ret:%d\n",ret);
    // cprintf("lib.h sysfork\n");
    return ret;
}

里面是GCC內(nèi)聯(lián)匯編磁餐，雖然說我也不是特別懂內(nèi)聯(lián)匯編违崇。不過我們只需要稍微看看，可以發(fā)現(xiàn)我們調(diào)用int中斷诊霹，把返回值放在了ret這個變量當中羞延。實際上在匯編代碼中，函數(shù)的返回值被放在了eax寄存器當中脾还。
下面是sys_exofork()對應的匯編代碼,這個可以obj/user/dumbfork.asm中得到:

  8000d9:   b8 07 00 00 00          mov    $0x7,%eax
  8000de:   cd 30                   int    $0x30
  8000e0:   89 c3                   mov    %eax,%ebx

調(diào)用int 0x30中斷就是調(diào)用我們創(chuàng)建新進程的中斷伴箩，上面的eax=7表明了我們使用的是SYS_exofork。 此時在父進程的eip就指向0x8000e0了荠呐。接下來就跳轉到了kern/syscall.c中的sys_exefork()中去執(zhí)行了赛蔫。

    struct Env* child;
    int ret_value;
    if((ret_value = env_alloc(&child,curenv->env_id)) < 0) {
        return ret_value ;
    }
    child->env_status = ENV_NOT_RUNNABLE;
    child->env_tf = curenv->env_tf;
    cprintf("ip:%x\n",curenv->env_tf.tf_eip);
    child->env_tf.tf_regs.reg_eax = 0;
    return child->env_id;

在這里我們創(chuàng)建了子進程砂客，然后復制父進程的寄存器給他泥张，所以子進程的eip也是指向0x8000e0。關鍵的一句就是child->env_tf.tf_regs.reg_eax = 0;我們修改了trapframe中的eax,我們知道eax是和返回值有關的鞠值。有一點疑問就是我們?nèi)绾卫闷饋磉@個返回值媚创？暫且先不管，到這里return 的代碼就return 返回到父進程去了彤恶。網(wǎng)上有些人說的钞钙，子進程也執(zhí)行了fork()，注意這個說法是錯的声离。只有父進程執(zhí)行了fork()芒炼。
為了驗證一下這個結果，我們在kern/syscall.c中的syscall()的SYS_exofork對應的case加入一個cprintf术徊，以及在kern/syscall.c中的sys_exorfork()中加入cpintf()本刽。輸出結果如下(這是部分輸出結果):

[00000000] new env 00001000
sys_exofork()
syscall.c:enter sys_exofork 
[00001000] new env 00001001
ip:8000e0

可以看到，確實中斷也只調(diào)用了一次，而且sys_exfork()也確確實實就執(zhí)行了一次子寓。接踵而來的問題就是既然就執(zhí)行了一次那么是如何做到兩個不同的返回值的呢暗挑？

還記得前面說到了，子進程被創(chuàng)建后就停在了0x0x8000e0,這句語句對應的eax存放的是返回值斜友。所以我們只有在這句語句之前修改eax的值炸裆，那么代碼中得到的返回值就被修改了。問題是如何修改返回值鲜屏？答案很簡單烹看，前面我們設置了child的eax=0，那么只要在子進程一被調(diào)度算法調(diào)度洛史，輪到他執(zhí)行的時候听系，由于popal指令，會恢復trapframe中到對應的寄存器去虹菲，于是輪到他執(zhí)行的時候eax就被修改為0了靠胜。
我們在dumfork()的sys_exofork()后面加上一句打印進程ID的語句如下：

    envid = sys_exofork();
    cprintf("id:%d\n",envid);

運行后得到結果:

[00000000] new env 00001000
[00001000] new env 00001001
id:4097
0: I am the parent! id:4097
id:0

可以看到子進程ID為4097返回到了父進程，子進程中返回了0毕源±四可以說我們的fork是正確的。有一點不解的是霎褐，為什么中間先打印一句0: I am the parent! id:4097址愿，而且為什么子進程打印ID的語句會在它之后？冻璃。 注意响谓，還記得我們新創(chuàng)建的進程并不是一開始就可以運行的，要到后面語句:

    if ((r = sys_env_set_status(envid, ENV_RUNNABLE)) < 0)
        panic("sys_env_set_status: %e", r);

設置為Runnable后才可以執(zhí)行省艳。此時我們沒有引入時間片輪轉娘纷，所以只有當進程主動放棄CPU的時候才可以調(diào)度別的進程。

void
umain(int argc, char **argv)
{
    envid_t who;
    int i;

    // fork a child process
    who = dumbfork();

    // print a message and yield to the other a few times
    for (i = 0; i < (who ? 10 : 20); i++) {
        cprintf("%d: I am the %s! id:%d\n", i, who ? "parent" : "child",who);
        sys_yield();
    }
}

到這里跋炕，for循環(huán)中首先打印出parent赖晶，然后父進程就放棄了CPU。接著關鍵點到了辐烂，調(diào)度程序發(fā)現(xiàn)子進程可以運行遏插，就調(diào)度子進程去獲取執(zhí)行纠修，然后在envv_run中恢復了子進程的各個寄存器的值了牛。子進程開始運行此時eax寄存器已被修改，所以返回值變?yōu)榱?敬锐，然后開始執(zhí)行0x0x8000e0的代碼，終于它來到它自己的printf(),輸出了id:0梳星。
所以比較關鍵的就是韵吨，子進程的返回值不是和父進程同時返回的漏峰。父進程先執(zhí)行得到了自己的返回值童擎，然后調(diào)度算法使得子進程運行芯砸，子進程中再得到返回值包帚，只不過這個返回值已經(jīng)被修改過了谋梭。

2. 我們fork()后，為什么新創(chuàng)建的進程就直接到了envs數(shù)組當中去了？
   這個疑問最先來自于：我們好像沒有顯示的通過envs[i]的方式來將新創(chuàng)建的進程加入到envs數(shù)組當中去吼鱼∷霭回顧一下創(chuàng)建進程的流程就可以明白這個問題眶蕉。
   首先在kern/env.c中，初始化了所有的envs,并且將它們用一個鏈表串起來饭入，env_free_list是鏈表頭:

然后我們在創(chuàng)建的時候嵌器，就更新鏈表。因為鏈表的作用是將所有空閑的進程slot串起來谐丢。所以更新了鏈表相當于就是往envs這個數(shù)組中加入數(shù)據(jù)了爽航。
下面是env_alloc()中的代碼，更新了鏈表庇谆。

一點思考

不得不說國內(nèi)的操作系統(tǒng)課太不夠意思了岳掐。學校開的不夠實踐性。就以進程來說饭耳，上課說進程有多個狀態(tài)串述，比如說ready,dead，running寞肖。當切換進程的時候纲酗，將CPU的控制權還給內(nèi)核，內(nèi)核來調(diào)度程序新蟆。當時就在想內(nèi)核也是進程觅赊，既然說調(diào)度程序是內(nèi)核代碼，內(nèi)核又是一個進程琼稻，感覺很奇怪吮螺，難道調(diào)度程序也要調(diào)度內(nèi)核嗎？
經(jīng)過本次partA的實踐帕翻，可以了解到內(nèi)核并不是嚴格意義上的進程鸠补，它沒有那些running，block什么的狀態(tài)嘀掸。