在本實驗中，你將在多個同時活動的使用者模式環境之間實現搶佔式多工處理。
在 Part A 中，你將在 JOS 中新增對多處理器的支援，以實現迴圈排程。並且新增基本的環境管理方面的系統呼叫（建立和銷毀環境的系統呼叫、以及分配/對映記憶體）。
在 Part B 中，你將要實現一個類 Unix 的 fork()，它將允許一個使用者模式中的環境去建立一個它自已的副本。
最後，在 Part C 中，你將在 JOS 中新增對進程間通訊（IPC）的支援，以允許不同使用者模式環境之間進行顯式通訊和同步。你也將要去新增對硬體時鐘中斷和優先權的支援。
使用 git 去提交你的實驗 3 的原始碼，並獲取課程倉庫的最新版本，然後建立一個名為 lab4 的本地分支，它跟蹤我們的名為 origin/lab4 的遠端 lab4 分支：
athena% cd ~/6.828/lab athena% add git athena% git pull Already up-to-date. athena% git checkout -b lab4 origin/lab4 Branch lab4 set up to track remote branch refs/remotes/origin/lab4. Switched to a new branch "lab4" athena% git merge lab3 Merge made by recursive. ... athena%實驗 4 包含了一些新的原始檔，在開始之前你應該去瀏覽一遍：
kern/cpu.h Kernel-private definitions for multiprocessor supportkern/mpconfig.c Code to read the multiprocessor configuration kern/lapic.c Kernel code driving the local APIC unit in each processorkern/mpentry.S Assembly-language entry code for non-boot CPUskern/spinlock.h Kernel-private definitions for spin locks, including the big kernel lock kern/spinlock.c Kernel code implementing spin lockskern/sched.c Code skeleton of the scheduler that you are about to implement本實驗分為三部分：Part A、Part B 和 Part C。我們計劃為每個部分分配一週的時間。
和以前一樣，你需要完成實驗中出現的、所有常規練習和至少一個挑戰問題。（不是每個部分做一個挑戰問題，是整個實驗做一個挑戰問題即可。）另外，你還要寫出你實現的挑戰問題的詳細描述。如果你實現了多個挑戰問題，你只需寫出其中一個即可，雖然我們的課程歡迎你完成越多的挑戰越好。在動手實驗之前，請將你的挑戰問題的答案寫在一個名為 answers-lab4.txt 的檔案中，並把它放在你的 lab 目錄的根下。
在本實驗的第一部分，將去擴充套件你的 JOS 核心，以便於它能夠在一個多處理器的系統上執行，並且要在 JOS 核心中實現一些新的系統呼叫，以便於它允許使用者級環境建立附加的新環境。你也要去實現協調的迴圈排程，在當前的環境自願放棄 CPU（或退出）時，允許核心將一個環境切換到另一個環境。稍後在 Part C 中，你將要實現搶佔排程，它允許核心在環境佔有 CPU 一段時間後，從這個環境上重新取回對 CPU 的控制，那怕是在那個環境不配合的情況下。
我們繼續去讓 JOS 支援 “對稱多處理器”（SMP），在一個多處理器的模型中，所有 CPU 們都有平等存取系統資源（如記憶體和 I/O 匯流排）的權力。雖然在 SMP 中所有 CPU 們都有相同的功能，但是在引導進程的過程中，它們被分成兩種型別：載入程式處理器（BSP）負責初始化系統和引導作業系統；而在作業系統啟動並正常執行後，應用程式處理器（AP）將被 BSP 啟用。哪個處理器做 BSP 是由硬體和 BIOS 來決定的。到目前為止，你所有的已存在的 JOS 程式碼都是執行在 BSP 上的。
在一個 SMP 系統上，每個 CPU 都伴有一個本地 APIC（LAPIC）單元。這個 LAPIC 單元負責傳遞系統中的中斷。LAPIC 還為它所連線的 CPU 提供一個唯一的識別符號。在本實驗中，我們將使用 LAPIC 單元（它在 kern/lapic.c 中）中的下列基本功能：
cpunum()）。STARTUP，以啟動其它 CPU（檢視 lapic_startap()）。apic_init()）。一個處理器使用記憶體對映的 I/O（MMIO）來存取它的 LAPIC。在 MMIO 中，一部分實體記憶體是寫死到一些 I/O 裝置的暫存器中，因此，存取記憶體時一般可以使用相同的 load/store 指令去存取裝置的暫存器。正如你所看到的，在實體地址 0xA0000 處就是一個 IO 入口（就是我們寫入 VGA 緩衝區的入口）。LAPIC 就在那裡，它從實體地址 0xFE000000 處（4GB 減去 32MB 處）開始，這個地址對於我們在 KERNBASE 處使用直接對映存取來說太高了。JOS 虛擬記憶體對映在 MMIOBASE 處，留下一個 4MB 的空隙，以便於我們有一個地方，能像這樣去對映裝置。由於在後面的實驗中，我們將介紹更多的 MMIO 區域，你將要寫一個簡單的函數，從這個區域中去分配空間，並將裝置的記憶體對映到那裡。
練習 1、實現
kern/pmap.c中的mmio_map_region。去看一下它是如何使用的，從kern/lapic.c中的lapic_init開始看起。在mmio_map_region的測試執行之前，你還要做下一個練習。
在引導應用程式處理器之前，載入程式處理器應該會首先去收集關於多處理器系統的資訊，比如總的 CPU 數、它們的 APIC ID 以及 LAPIC 單元的 MMIO 地址。在 kern/mpconfig.c 中的 mp_init() 函數，通過讀取記憶體中位於 BIOS 區域裡的 MP 設定表來獲得這些資訊。
boot_aps() 函數（在 kern/init.c 中）驅動 AP 的引導過程。AP 們在真實模式中開始，與 boot/boot.S 中啟動引導載入程式非常相似。因此，boot_aps() 將 AP 入口程式碼（kern/mpentry.S）複製到真實模式中的那個可定址記憶體地址上。不像使用引導載入程式那樣，我們可以控制 AP 將從哪裡開始執行程式碼；我們複製入口程式碼到 0x7000（MPENTRY_PADDR）處，但是複製到任何低於 640KB 的、未使用的、頁對齊的實體地址上都是可以執行的。
在那之後，通過傳送 IPI STARTUP 到相關 AP 的 LAPIC 單元，以及一個初始的 CS:IP 地址（AP 將從那兒開始執行它的入口程式碼，在我們的案例中是 MPENTRY_PADDR ），boot_aps() 將一個接一個地啟用 AP。在 kern/mpentry.S 中的入口程式碼非常類似於 boot/boot.S。在一些簡短的設定之後，它啟用分頁，使 AP 進入保護模式，然後呼叫 C 設定程式 mp_main()（它也在 kern/init.c 中）。在繼續喚醒下一個 AP 之前， boot_aps() 將等待這個 AP 去傳遞一個 CPU_STARTED 標誌到它的 struct CpuInfo 中的 cpu_status 欄位中。
練習 2、閱讀
kern/init.c中的boot_aps()和mp_main()，以及在kern/mpentry.S中的組合程式碼。確保你理解了在 AP 引導過程中的控制流轉移。然後修改在kern/pmap.c中的、你自己的page_init()，實現避免在MPENTRY_PADDR處新增頁到空閒列表上，以便於我們能夠在實體地址上安全地複製和執行 AP 載入程式程式碼。你的程式碼應該會通過更新後的check_page_free_list()的測試（但可能會在更新後的check_kern_pgdir()上測試失敗，我們在後面會修復它）。
.
問題 1、比較
kern/mpentry.S和boot/boot.S。記住，那個kern/mpentry.S是編譯和連結後的，執行在KERNBASE上面的，就像核心中的其它程式一樣，宏MPBOOTPHYS的作用是什麼？為什麼它需要在kern/mpentry.S中，而不是在boot/boot.S中？換句話說，如果在kern/mpentry.S中刪掉它，會發生什麼錯誤？ 提示：回顧連結地址和載入地址的區別，我們在實驗 1 中討論過它們。
當寫一個多處理器作業系統時，區分每個 CPU 的狀態是非常重要的，而每個 CPU 的狀態對其它處理器是不公開的，而全域性狀態是整個系統共用的。kern/cpu.h 定義了大部分每個 CPU 的狀態，包括 struct CpuInfo，它儲存了每個 CPU 的變數。cpunum() 總是返回撥用它的那個 CPU 的 ID，它可以被用作是陣列的索引，比如 cpus。或者，宏 thiscpu 是當前 CPU 的 struct CpuInfo 縮略表示。
下面是你應該知道的每個 CPU 的狀態：
每個 CPU 的核心棧
因為核心能夠同時捕獲多個 CPU，因此，我們需要為每個 CPU 準備一個單獨的核心棧，以防止它們執行的程式之間產生相互干擾。陣列 percpu_kstacks[NCPU][KSTKSIZE] 為 NCPU 的核心棧資產保留了空間。
在實驗 2 中，你對映的 bootstack 所參照的實體記憶體，就作為 KSTACKTOP 以下的 BSP 的核心棧。同樣，在本實驗中，你將每個 CPU 的核心棧對映到這個區域，而使用保護頁做為它們之間的緩衝區。CPU 0 的棧將從 KSTACKTOP 處向下增長；CPU 1 的棧將從 CPU 0 的棧底部的 KSTKGAP 位元組處開始，依次類推。在 inc/memlayout.h 中展示了這個對映布局。
每個 CPU 的 TSS 和 TSS 描述符
為了指定每個 CPU 的核心棧在哪裡，也需要有一個每個 CPU 的任務狀態描述符（TSS）。CPU i 的任務狀態描述符是儲存在 cpus[i].cpu_ts 中，而對應的 TSS 描述符是定義在 GDT 條目 gdt[(GD_TSS0 >> 3) + i] 中。在 kern/trap.c 中定義的全域性變數 ts 將不再被使用。
每個 CPU 當前的環境指標
由於每個 CPU 都能同時執行不同的使用者進程，所以我們重新定義了符號 curenv，讓它指向到 cpus[cpunum()].cpu_env（或 thiscpu->cpu_env），它指向到當前 CPU（程式碼正在執行的那個 CPU）上當前正在執行的環境上。
每個 CPU 的系統暫存器
所有的暫存器，包括系統暫存器，都是一個 CPU 私有的。所以，初始化這些暫存器的指令，比如 lcr3()、ltr()、lgdt()、lidt()、等待，必須在每個 CPU 上執行一次。函數 env_init_percpu() 和 trap_init_percpu() 就是為此目的而定義的。
練習 3、修改
mem_init_mp()（在kern/pmap.c中）去對映每個 CPU 的棧從KSTACKTOP處開始，就像在inc/memlayout.h中展示的那樣。每個棧的大小是KSTKSIZE位元組加上未對映的保護頁KSTKGAP的位元組。你的程式碼應該會通過在check_kern_pgdir()中的新的檢查。
.
練習 4、在
trap_init_percpu()（在kern/trap.c檔案中）的程式碼為 BSP 初始化 TSS 和 TSS 描述符。在實驗 3 中它就執行過，但是當它執行在其它的 CPU 上就會出錯。修改這些程式碼以便它能在所有 CPU 上都正常執行。（注意：你的新程式碼應該還不能使用全域性變數ts）
在你完成上述練習後，在 QEMU 中使用 4 個 CPU（使用 make qemu CPUS=4 或 make qemu-nox CPUS=4）來執行 JOS，你應該看到類似下面的輸出：
... Physical memory: 66556K available, base = 640K, extended = 65532K check_page_alloc() succeeded! check_page() succeeded! check_kern_pgdir() succeeded! check_page_installed_pgdir() succeeded! SMP: CPU 0 found 4 CPU(s) enabled interrupts: 1 2 SMP: CPU 1 starting SMP: CPU 2 starting SMP: CPU 3 starting在 mp_main() 中初始化 AP 後我們的程式碼快速執行起來。在你更進一步增強 AP 之前，我們需要首先去處理多個 CPU 同時執行核心程式碼的爭用狀況。達到這一目標的最簡單的方法是使用大核心鎖。大核心鎖是一個單個的全域性鎖，當一個環境進入核心模式時，它將被加鎖，而這個環境返回到使用者模式時它將釋放鎖。在這種模型中，在使用者模式中執行的環境可以同時執行在任何可用的 CPU 上，但是只有一個環境能夠執行在核心模式中；而任何嘗試進入核心模式的其它環境都被強制等待。
kern/spinlock.h 中宣告大核心鎖，即 kernel_lock。它也提供 lock_kernel() 和 unlock_kernel()，快捷地去獲取/釋放鎖。你應該在以下的四個位置應用大核心鎖：
i386_init() 時，在 BSP 喚醒其它 CPU 之前獲取鎖。mp_main() 時，在初始化 AP 之後獲取鎖，然後呼叫 sched_yield() 在這個 AP 上開始執行環境。trap() 時，當從使用者模式中捕獲一個陷阱時獲取鎖。在檢查 tf_cs 的低位位元，以確定一個陷阱是發生在使用者模式還是核心模式時。env_run() 中，在切換到使用者模式之前釋放鎖。不能太早也不能太晚，否則你將可能會產生爭用或死鎖。練習 5、在上面所描述的情況中，通過在合適的位置呼叫
lock_kernel()和unlock_kernel()應用大核心鎖。如果你的鎖定是正確的，如何去測試它？實際上，到目前為止，還無法測試！但是在下一個練習中，你實現了排程之後，就可以測試了。
.
問題 2、看上去使用一個大核心鎖，可以保證在一個時間中只有一個 CPU 能夠執行核心程式碼。為什麼每個 CPU 仍然需要單獨的核心棧？描述一下使用一個共用核心棧出現錯誤的場景，即便是在它使用了大核心鎖保護的情況下。
小挑戰！大核心鎖很簡單，也易於使用。儘管如此，它消除了核心模式的所有並行。大多數現代作業系統使用不同的鎖，一種稱之為細粒度鎖定的方法，去保護它們的共用的棧的不同部分。細粒度鎖能夠大幅提升效能，但是實現起來更困難並且易出錯。如果你有足夠的勇氣，在 JOS 中刪除大核心鎖，去擁抱並行吧！
由你來決定鎖的粒度（一個鎖保護的資料量）。給你一個提示，你可以考慮在 JOS 核心中使用一個自旋鎖去確保你獨占存取這些共用的元件：
- 頁分配器
- 控制台驅動
- 排程器
- 你將在 Part C 中實現的進程間通訊（IPC）的狀態
本實驗中，你的下一個任務是去修改 JOS 核心，以使它能夠在多個環境之間以“迴圈”的方式去交替。JOS 中的迴圈排程工作方式如下：
kern/sched.c 中的 sched_yield() 函數負責去選擇一個新環境來執行。它按順序以迴圈的方式在陣列 envs[] 中進行搜尋，在前一個執行的環境之後開始（或如果之前沒有執行的環境，就從陣列起點開始），選擇狀態為 ENV_RUNNABLE 的第一個環境（檢視 inc/env.h），並呼叫 env_run() 去跳轉到那個環境。sched_yield() 必須做到，同一個時間在兩個 CPU 上絕對不能執行相同的環境。它可以判斷出一個環境正執行在一些 CPU（可能是當前 CPU）上，因為，那個正在執行的環境的狀態將是 ENV_RUNNING。sys_yield()，使用者環境呼叫它去呼叫核心的 sched_yield() 函數，並因此將自願把對 CPU 的控制禪讓給另外的一個環境。練習 6、像上面描述的那樣，在
sched_yield()中實現迴圈排程。不要忘了去修改syscall()以派發sys_yield()。確保在
mp_main中呼叫了sched_yield()。修改
kern/init.c去建立三個（或更多個！）執行程式user/yield.c的環境。執行
make qemu。在它終止之前，你應該會看到像下面這樣，在環境之間來回切換了五次。也可以使用幾個 CPU 來測試：
make qemu CPUS=2。...Hello, I am environment 00001000.Hello, I am environment 00001001.Hello, I am environment 00001002.Back in environment 00001000, iteration 0.Back in environment 00001001, iteration 0.Back in environment 00001002, iteration 0.Back in environment 00001000, iteration 1.Back in environment 00001001, iteration 1.Back in environment 00001002, iteration 1....在程式
yield退出之後，系統中將沒有可執行的環境，排程器應該會呼叫 JOS 核心監視器。如果它什麼也沒有發生，那麼你應該在繼續之前修復你的程式碼。問題 3、在你實現的
env_run()中，你應該會呼叫lcr3()。在呼叫lcr3()的之前和之後，你的程式碼參照（至少它應該會）變數e，它是env_run的引數。在載入%cr3暫存器時，MMU 使用的地址上下文將馬上被改變。但一個虛擬地址（即e）相對一個給定的地址上下文是有意義的 —— 地址上下文指定了實體地址到那個虛擬地址的對映。為什麼指標e在地址切換之前和之後被解除參照？
.
問題 4、無論何時，核心從一個環境切換到另一個環境，它必須要確保舊環境的暫存器內容已經被儲存，以便於它們稍後能夠正確地還原。為什麼？這種事件發生在什麼地方？
.
小挑戰！給核心新增一個小小的排程策略，比如一個固定優先順序的排程器，它將會給每個環境分配一個優先順序，並且在執行中，較高優先順序的環境總是比低優先順序的環境優先被選定。如果你想去冒險一下，嘗試實現一個類 Unix 的、優先順序可調整的排程器，或者甚至是一個彩票排程器或跨步排程器。（可以在 Google 中查詢“彩票排程”和“跨步排程”的相關資料）
寫一個或兩個測試程式，去測試你的排程演算法是否工作正常（即，正確的演算法能夠按正確的次序執行）。如果你實現了本實驗的 Part B 和 Part C 部分的
fork()和 IPC，寫這些測試程式可能會更容易。
.
小挑戰！目前的 JOS 核心還不能應用到使用了 x87 協處理器、MMX 指令集、或流式 SIMD 擴充套件（SSE）的 x86 處理器上。擴充套件資料結構
Env去提供一個能夠儲存處理器的浮點狀態的地方，並且擴充套件上下文切換程式碼，當從一個環境切換到另一個環境時，能夠儲存和還原正確的狀態。FXSAVE和FXRSTOR指令或許對你有幫助，但是需要注意的是，這些指令在舊的 x86 使用者手冊上沒有，因為它是在較新的處理器上引入的。寫一個使用者級的測試程式，讓它使用浮點做一些很酷的事情。
雖然你的核心現在已經有了在多個使用者級環境之間切換的功能，但是由於核心初始化設定的原因，它在執行環境時仍然是受限的。現在，你需要去實現必需的 JOS 系統呼叫，以允許使用者環境去建立和啟動其它的新使用者環境。
Unix 提供了 fork() 系統呼叫作為它的進程建立原語。Unix 的 fork() 通過複製呼叫進程（父進程）的整個地址空間去建立一個新進程（子進程）。從使用者空間中能夠觀察到它們之間的僅有的兩個差別是，它們的進程 ID 和父進程 ID（由 getpid 和 getppid 返回）。在父進程中，fork() 返回子進程 ID，而在子進程中，fork() 返回 0。預設情況下，每個進程得到它自己的私有地址空間，一個進程對記憶體的修改對另一個進程都是不可見的。
為建立一個使用者模式下的新的環境，你將要提供一個不同的、更原始的 JOS 系統呼叫集。使用這些系統呼叫，除了其它型別的環境建立之外，你可以在使用者空間中實現一個完整的類 Unix 的 fork()。你將要為 JOS 編寫的新的系統呼叫如下：
sys_exofork：
這個系統呼叫建立一個新的空白的環境：在它的地址空間的使用者部分什麼都沒有對映，並且它也不能執行。這個新的環境與 sys_exofork 呼叫時建立它的父環境的暫存器狀態完全相同。在父進程中，sys_exofork 將返回新建立進程的 envid_t（如果環境分配失敗的話，返回的是一個負的錯誤程式碼）。在子進程中，它將返回 0。（因為子進程從一開始就被標記為不可執行，在子進程中，sys_exofork 將並不真的返回，直到它的父進程使用 …. 顯式地將子進程標記為可執行之前。）
sys_env_set_status：
設定指定的環境狀態為 ENV_RUNNABLE 或 ENV_NOT_RUNNABLE。這個系統呼叫一般是在，一個新環境的地址空間和暫存器狀態已經完全初始化完成之後，用於去標記一個準備去執行的新環境。
sys_page_alloc：
分配一個實體記憶體頁，並對映它到一個給定的環境地址空間中、給定的一個虛擬地址上。
sys_page_map：
從一個環境的地址空間中複製一個頁對映（不是頁內容！）到另一個環境的地址空間中，保持一個記憶體共用，以便於新的和舊的對映共同指向到同一個實體記憶體頁。
sys_page_unmap：
在一個給定的環境中，取消對映一個給定的已對映的虛擬地址。
上面所有的系統呼叫都接受環境 ID 作為引數，JOS 核心支援一個約定，那就是用值 “0” 來表示“當前環境”。這個約定在 kern/env.c 中的 envid2env() 中實現的。
在我們的 user/dumbfork.c 中的測試程式裡，提供了一個類 Unix 的 fork() 的非常原始的實現。這個測試程式使用了上面的系統呼叫，去建立和執行一個複製了它自己地址空間的子環境。然後，這兩個環境像前面的練習那樣使用 sys_yield 來回切換，父進程在疊代 10 次後退出，而子進程在疊代 20 次後退出。
練習 7、在
kern/syscall.c中實現上面描述的系統呼叫，並確保syscall()能呼叫它們。你將需要使用kern/pmap.c和kern/env.c中的多個函數，尤其是要用到envid2env()。目前，每當你呼叫envid2env()時，在checkperm中傳遞引數 1。你務必要做檢查任何無效的系統呼叫引數，在那個案例中，就返回了-E_INVAL。使用user/dumbfork測試你的 JOS 核心，並在繼續之前確保它執行正常。
.
小挑戰！新增另外的系統呼叫，必須能夠讀取已存在的、所有的、環境的重要狀態，以及設定它們。然後實現一個能夠 fork 出子環境的使用者模式程式，執行它一小會（即，疊代幾次
sys_yield()），然後取得幾張螢幕截圖或子環境的檢查點，然後執行子環境一段時間，然後還原子環境到檢查點時的狀態，然後從這裡繼續開始。這樣，你就可以有效地從一個中間狀態“回放”了子環境的執行。確保子環境與使用者使用sys_cgetc()或readline()執行了一些互動，這樣，那個使用者就能夠檢視和突變它的內部狀態，並且你可以通過給子環境給定一個選擇性遺忘的狀況，來驗證你的檢查點/重新啟動動的有效性，使它“遺忘”了在某些點之前發生的事情。
到此為止，已經完成了本實驗的 Part A 部分；在你執行 make grade 之前確保它通過了所有的 Part A 的測試，並且和以往一樣，使用 make handin 去提交它。如果你想嘗試找出為什麼一些特定的測試是失敗的，可以執行 run ./grade-lab4 -v，它將向你展示核心構建的輸出，和測試失敗時的 QEMU 執行情況。當測試失敗時，這個指令碼將停止執行，然後你可以去檢查 jos.out 的內容，去檢視核心真實的輸出內容。
正如在前面提到過的，Unix 提供 fork() 系統呼叫作為它主要的進程建立原語。fork() 系統呼叫通過複製呼叫進程（父進程）的地址空間來建立一個新進程（子進程）。
xv6 Unix 的 fork() 從父進程的頁上複製所有資料，然後將它分配到子進程的新頁上。從本質上看，它與 dumbfork() 所採取的方法是相同的。複製父進程的地址空間到子進程，是 fork() 操作中代價最高的部分。
但是，一個對 fork() 的呼叫後，經常是緊接著幾乎立即在子進程中有一個到 exec() 的呼叫，它使用一個新程式來替換子進程的記憶體。這是 shell 預設去做的事，在這種情況下，在複製父進程地址空間上花費的時間是非常浪費的，因為在呼叫 exec() 之前，子進程使用的記憶體非常少。
基於這個原因，Unix 的最新版本利用了虛擬記憶體硬體的優勢，允許父進程和子進程去共用對映到它們各自地址空間上的記憶體，直到其中一個進程真實地修改了它們為止。這個技術就是眾所周知的“寫時複製”。為實現這一點，在 fork() 時，核心將複製從父進程到子進程的地址空間的對映，而不是所對映的頁的內容，並且同時設定正在共用中的頁為唯讀。當兩個進程中的其中一個嘗試去寫入到它們共用的頁上時，進程將產生一個頁故障。在這時，Unix 核心才意識到那個頁實際上是“虛擬的”或“寫時複製”的副本，然後它生成一個新的、私有的、那個發生頁故障的進程可寫的、頁的副本。在這種方式中，個人的頁的內容並不進行真實地複製，直到它們真正進行寫入時才進行複製。這種優化使得一個fork() 後在子進程中跟隨一個 exec() 變得代價很低了：子進程在呼叫 exec() 時或許僅需要複製一個頁（它的棧的當前頁）。
在本實驗的下一段中，你將實現一個帶有“寫時複製”的“真正的”類 Unix 的 fork()，來作為一個常規的使用者空間庫。在使用者空間中實現 fork() 和寫時複製有一個好處就是，讓核心始終保持簡單，並且因此更不易出錯。它也讓個別的使用者模式程式在 fork() 上定義了它們自己的語意。一個有略微不同實現的程式（例如，代價昂貴的、總是複製的 dumbfork() 版本，或父子進程真實共用記憶體的後面的那一個），它自己可以很容易提供。
一個使用者級寫時複製 fork() 需要知道關於在防寫頁上的頁故障相關的資訊，因此，這是你首先需要去實現的東西。對使用者級頁故障處理來說，寫時複製僅是眾多可能的用途之一。
它通常是設定一個地址空間，因此在一些動作需要時，那個頁故障將指示去處。例如，主流的 Unix 核心在一個新進程的棧區域中，初始的對映僅是單個頁，並且在後面“按需”分配和對映額外的棧頁，因此，進程的棧消費是逐漸增加的，並因此導致在尚未對映的棧地址上發生頁故障。在每個進程空間的區域上發生一個頁故障時，一個典型的 Unix 核心必須對它的動作保持跟蹤。例如，在棧區域中的一個頁故障，一般情況下將分配和對映新的實體記憶體頁。一個在程式的 BSS 區域中的頁故障，一般情況下將分配一個新頁，然後用 0 填充它並對映它。在一個按需分頁的系統上的一個可執行檔案中，在文字區域中的頁故障將從磁碟上讀取相應的二進位制頁並對映它。
核心跟蹤有大量的資訊，與傳統的 Unix 方法不同，你將決定在每個使用者空間中關於每個頁故障應該做的事。使用者空間中的 bug 危害都較小。這種設計帶來了額外的好處，那就是允許程式設計師在定義它們的記憶體區域時，會有很好的靈活性；對於對映和存取基於磁碟檔案系統上的檔案時，你應該使用後面的使用者級頁故障處理。
為了處理它自己的頁故障，一個使用者環境將需要在 JOS 核心上註冊一個頁故障服務程式入口。使用者環境通過新的 sys_env_set_pgfault_upcall 系統呼叫來註冊它的頁故障入口。我們給結構 Env 增加了一個新的成員 env_pgfault_upcall，讓它去記錄這個資訊。
練習 8、實現
sys_env_set_pgfault_upcall系統呼叫。當查詢目標環境的環境 ID 時，一定要確認啟用了許可權檢查，因為這是一個“危險的”系統呼叫。 “`
在正常執行期間，JOS 中的一個使用者環境執行在正常的使用者棧上：它的 ESP 暫存器開始指向到 USTACKTOP，而它所推播的棧資料將駐留在 USTACKTOP-PGSIZE 和 USTACKTOP-1（含）之間的頁上。但是，當在使用者模式中發生頁故障時，核心將在一個不同的棧上重新啟動使用者環境，執行一個使用者級頁故障指定的服務程式，即使用者異常棧。其它，我們將讓 JOS 核心為使用者環境實現自動的“棧切換”，當從使用者模式轉換到核心模式時，x86 處理器就以大致相同的方式為 JOS 實現了棧切換。
JOS 使用者異常棧也是一個頁的大小，並且它的頂部被定義在虛擬地址 UXSTACKTOP 處，因此使用者異常棧的有效位元組數是從 UXSTACKTOP-PGSIZE 到 UXSTACKTOP-1（含）。儘管執行在異常棧上，使用者頁故障服務程式能夠使用 JOS 的普通系統呼叫去對映新頁或調整對映，以便於去修復最初導致頁故障發生的各種問題。然後使用者級頁故障服務程式通過組合語言 stub 返回到原始棧上的故障程式碼。
每個想去支援使用者級頁故障處理的使用者環境，都需要為它自己的異常棧使用在 Part A 中介紹的 sys_page_alloc() 系統呼叫去分配記憶體。
現在，你需要去修改 kern/trap.c 中的頁故障處理程式碼，以能夠處理接下來在使用者模式中發生的頁故障。我們將故障發生時使用者環境的狀態稱之為捕獲時狀態。
如果這裡沒有註冊頁故障服務程式，JOS 核心將像前面那樣，使用一個訊息來銷毀使用者環境。否則，核心將在異常棧上設定一個陷阱幀，它看起來就像是來自 inc/trap.h 檔案中的一個 struct 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然後，核心安排這個使用者環境重新執行，使用這個棧幀在異常棧上執行頁故障服務程式；你必須搞清楚為什麼發生這種情況。fault_va 是引發頁故障的虛擬地址。
如果在一個異常發生時，使用者環境已經在使用者異常棧上執行，那麼頁故障服務程式自身將會失敗。在這種情況下，你應該在當前的 tf->tf_esp 下，而不是在 UXSTACKTOP 下啟動一個新的棧幀。
去測試 tf->tf_esp 是否已經在使用者異常棧上準備好，可以去檢查它是否在 UXSTACKTOP-PGSIZE 和 UXSTACKTOP-1（含）的範圍內。
練習 9、實現在
kern/trap.c中的page_fault_handler的程式碼，要求派發頁故障到使用者模式故障服務程式上。在寫入到異常棧時，一定要採取適當的預防措施。（如果使用者環境執行時溢位了異常棧，會發生什麼事情？）
接下來，你需要去實現組合程式，它將呼叫 C 頁故障服務程式，並在原始的故障指令處恢復程式執行。這個組合程式是一個故障服務程式，它由核心使用 sys_env_set_pgfault_upcall() 來註冊。
練習 10、實現在
lib/pfentry.S中的_pgfault_upcall程式。最有趣的部分是返回到使用者程式碼中產生頁故障的原始位置。你將要直接返回到那裡，不能通過核心返回。最難的部分是同時切換棧和重新載入 EIP。
最後，你需要去實現使用者級頁故障處理機制的 C 使用者庫。
練習 11、完成
lib/pgfault.c中的set_pgfault_handler()。 ”`
執行 user/faultread（make run-faultread）你應該會看到：
... [00000000] new env 00001000 [00001000] user fault va 00000000 ip 0080003a TRAP frame ... [00001000] free env 00001000執行 user/faultdie 你應該會看到：
... [00000000] new env 00001000 i faulted at va deadbeef, err 6 [00001000] exiting gracefully [00001000] free env 00001000執行 user/faultalloc 你應該會看到：
... [00000000] new env 00001000 fault deadbeef this string was faulted in at deadbeef fault cafebffe fault cafec000 this string was faulted in at cafebffe [00001000] exiting gracefully [00001000] free env 00001000如果你只看到第一個 “this string” 行，意味著你沒有正確地處理遞回頁故障。
執行 user/faultallocbad 你應該會看到：
... [00000000] new env 00001000 [00001000] user_mem_check assertion failure for va deadbeef [00001000] free env 00001000確保你理解了為什麼 user/faultalloc 和 user/faultallocbad 的行為是不一樣的。
小挑戰！擴充套件你的核心，讓它不僅是頁故障，而是在使用者空間中執行的程式碼能夠產生的所有型別的處理器異常，都能夠被重定向到一個使用者模式中的異常服務程式上。寫出使用者模式測試程式，去測試各種各樣的使用者模式例外處理，比如除零錯誤、一般保護故障、以及非法操作碼。
現在，你有個核心功能要去實現，那就是在使用者空間中完整地實現寫時複製 fork()。
我們在 lib/fork.c 中為你的 fork() 提供了一個框架。像 dumbfork()、fork() 應該會建立一個新環境，然後通過掃描父環境的整個地址空間，並在子環境中設定相關的頁對映。重要的差別在於，dumbfork() 複製了頁，而 fork() 開始只是複製了頁對映。fork() 僅當在其中一個環境嘗試去寫入它時才複製每個頁。
fork() 的基本控制流如下：
set_pgfault_handler() 函數，安裝 pgfault() 作為 C 級頁故障服務程式。sys_exofork() 去建立一個子環境。在它的地址空間中，低於 UTOP 位置的、每個可寫入頁、或寫時複製頁上，父環境呼叫 duppage 後，它應該會對映頁寫時複製到子環境的地址空間中，然後在它自己的地址空間中重新對映頁寫時複製。[ 注意：這裡的順序很重要（即，在父環境中標記之前，先在子環境中標記該頁為 COW）！你能明白是為什麼嗎？嘗試去想一個具體的案例，將順序顛倒一下會發生什麼樣的問題。] duppage 把兩個 PTE 都設定了，致使那個頁不可寫入，並且在 “avail” 欄位中通過包含 PTE_COW 來從真正的唯讀頁中區分寫時複製頁。
然而異常棧是不能通過這種方式重對映的。對於異常棧，你需要在子環境中分配一個新頁。因為頁故障服務程式不能做真實的複製，並且頁故障服務程式是執行在異常棧上的，異常棧不能進行寫時複製：那麼誰來複製它呢？
fork() 也需要去處理存在的頁，但不能寫入或寫時複製。
父環境為子環境設定了使用者頁故障入口點，讓它看起來像它自己的一樣。
現在，子環境準備去執行，所以父環境標記它為可執行。
每次其中一個環境寫一個還沒有寫入的寫時複製頁時，它將產生一個頁故障。下面是使用者頁故障服務程式的控制流：
_pgfault_upcall，它呼叫 fork() 的 pgfault() 服務程式。pgfault() 檢測到那個故障是一個寫入（在錯誤程式碼中檢查 FEC_WR），然後將那個頁的 PTE 標記為 PTE_COW。如果不是一個寫入，則崩潰。pgfault() 在一個臨時位置分配一個對映的新頁，並將故障頁的內容複製進去。然後，故障服務程式以讀取/寫入許可權對映新頁到合適的地址，替換舊的唯讀對映。對於上面的幾個操作，使用者級 lib/fork.c 程式碼必須查詢環境的頁表（即，那個頁的 PTE 是否標記為 PET_COW）。為此，核心在 UVPT 位置精確地對映環境的頁表。它使用一個 聰明的對映技巧 去標記它，以使使用者程式碼查詢 PTE 時更容易。lib/entry.S 設定 uvpt 和 uvpd，以便於你能夠在 lib/fork.c 中輕鬆查詢頁表資訊。
練習 12、在
lib/fork.c中實現fork、duppage和pgfault。使用
forktree程式測試你的程式碼。它應該會產生下列的資訊，在資訊中會有 ‘new env'、'free env'、和 'exiting gracefully’ 這樣的字眼。資訊可能不是按如下的順序出現的，並且環境 ID 也可能不一樣。1000: I am '' 1001: I am '0' 2000: I am '00' 2001: I am '000' 1002: I am '1' 3000: I am '11' 3001: I am '10' 4000: I am '100' 1003: I am '01' 5000: I am '010' 4001: I am '011' 2002: I am '110' 1004: I am '001' 1005: I am '111' 1006: I am '101'
.
小挑戰！實現一個名為
sfork()的共用記憶體的fork()。這個版本的sfork()中，父子環境共用所有的記憶體頁（因此，一個環境中對記憶體寫入，就會改變另一個環境資料），除了在棧區域中的頁以外，它應該使用寫時複製來處理這些頁。修改user/forktree.c去使用sfork()而是不常見的fork()。另外，你在 Part C 中實現了 IPC 之後，使用你的sfork()去執行user/pingpongs。你將找到提供全域性指標thisenv功能的一個新方式。
.
小挑戰！你實現的
fork將產生大量的系統呼叫。在 x86 上，使用中斷切換到核心模式將產生較高的代價。增加系統呼叫介面，以便於它能夠一次傳送批次的系統呼叫。然後修改fork去使用這個介面。你的新的
fork有多快？你可以用一個分析來論證，批次提交對你的
fork的效能改變，以它來（粗略地）回答這個問題：使用一個int 0x30指令的代價有多高？在你的fork中執行了多少次int 0x30指令？存取TSS棧切換的代價高嗎？等待 …或者，你可以在真實的硬體上引導你的核心，並且真實地對你的程式碼做基準測試。檢視
RDTSC（讀取時間戳計數器）指令，它的定義在 IA32 手冊中，它計數自上一次處理器重置以來流逝的時鐘週期數。QEMU 並不能真實地模擬這個指令（它能夠計數執行的虛擬指令數量，或使用主機的 TSC，但是這兩種方式都不能反映真實的 CPU 週期數）。
到此為止，Part B 部分結束了。在你執行 make grade 之前，確保你通過了所有的 Part B 部分的測試。和以前一樣，你可以使用 make handin 去提交你的實驗。
在實驗 4 的最後部分，你將修改核心去搶佔不配合的環境，並允許環境之間顯式地傳遞訊息。
執行測試程式 user/spin。這個測試程式 fork 出一個子環境，它控制了 CPU 之後，就永不停歇地運轉起來。無論是父環境還是核心都不能回收對 CPU 的控制。從使用者模式環境中保護系統免受 bug 或惡意程式碼攻擊的角度來看，這顯然不是個理想的狀態，因為任何使用者模式環境都能夠通過簡單的無限迴圈，並永不歸還 CPU 控制權的方式，讓整個系統處於暫停狀態。為了允許核心去搶占一個執行中的環境，從其中奪回對 CPU 的控制權，我們必須去擴充套件 JOS 核心，以支援來自硬體時鐘的外部硬體中斷。
外部中斷（即：裝置中斷）被稱為 IRQ。現在有 16 個可能出現的 IRQ，編號 0 到 15。從 IRQ 號到 IDT 條目的對映是不固定的。在 picirq.c 中的 pic_init 對映 IRQ 0 - 15 到 IDT 條目 IRQ_OFFSET 到 IRQ_OFFSET+15。
在 inc/trap.h 中，IRQ_OFFSET 被定義為十進位制的 32。所以，IDT 條目 32 - 47 對應 IRQ 0 - 15。例如，時鐘中斷是 IRQ 0，所以 IDT[IRQ_OFFSET+0]（即：IDT[32]）包含了核心中時鐘中斷服務程式的地址。這裡選擇 IRQ_OFFSET 是為了處理器異常不會覆蓋裝置中斷，因為它會引起顯而易見的混淆。（事實上，在早期執行 MS-DOS 的 PC 上， IRQ_OFFSET 事實上是 0，它確實導致了硬體中斷服務程式和處理器例外處理之間的混淆！）
在 JOS 中，相比 xv6 Unix 我們做了一個重要的簡化。當處於核心模式時，外部裝置中斷總是被關閉（並且，像 xv6 一樣，當處於使用者空間時，再開啟外部裝置的中斷）。外部中斷由 %eflags 暫存器的 FL_IF 標誌位來控制（檢視 inc/mmu.h）。當這個標誌位被設定時，外部中斷被開啟。雖然這個標誌位可以使用幾種方式來修改，但是為了簡化，我們只通過進程所儲存和恢復的 %eflags 暫存器值，作為我們進入和離開使用者模式的方法。
處於使用者環境中時，你將要確保 FL_IF 標誌被設定，以便於出現一個中斷時，它能夠通過處理器來傳遞，讓你的中斷程式碼來處理。否則，中斷將被遮蔽或忽略，直到中斷被重新開啟後。我們使用引導載入程式的第一個指令去遮蔽中斷，並且到目前為止，還沒有去重新開啟它們。
練習 13、修改
kern/trapentry.S和kern/trap.c去初始化 IDT 中的相關條目，並為 IRQ 0 到 15 提供服務程式。然後修改kern/env.c中的env_alloc()的程式碼，以確保在使用者環境中，中斷總是開啟的。另外，在
sched_halt()中取消註釋sti指令，以便於空閒的 CPU 取消遮蔽中斷。當呼叫一個硬體中斷服務程式時，處理器不會推播一個錯誤程式碼。在這個時候，你可能需要重新閱讀 80386 參考手冊 的 9.2 節，或 IA-32 Intel 架構軟體開發者手冊 卷 3 的 5.8 節。
在完成這個練習後，如果你在你的核心上使用任意的測試程式去持續執行（即：
spin），你應該會看到核心輸出中捕獲的硬體中斷的捕獲幀。雖然在處理器上已經開啟了中斷，但是 JOS 並不能處理它們，因此，你應該會看到在當前執行的使用者環境中每個中斷的錯誤屬性並被銷毀，最終環境會被銷毀並進入到監視器中。
在 user/spin 程式中，子環境首先執行之後，它只是進入一個高速迴圈中，並且核心再無法取得 CPU 控制權。我們需要對硬體程式設計，定期產生時鐘中斷，它將強制將 CPU 控制權返還給核心，在核心中，我們就能夠將控制權切換到另外的使用者環境中。
我們已經為你寫好了對 lapic_init 和 pic_init（來自 init.c 中的 i386_init）的呼叫，它將設定時鐘和中斷控制器去產生中斷。現在，你需要去寫程式碼來處理這些中斷。
練習 14、修改核心的
trap_dispatch()函數，以便於在時鐘中斷發生時，它能夠呼叫sched_yield()去查詢和執行一個另外的環境。現在，你應該能夠用
user/spin去做測試了：父環境應該會 fork 出子環境，sys_yield()到它許多次，但每次切換之後，將重新獲得對 CPU 的控制權，最後殺死子環境後優雅地終止。
這是做回歸測試的好機會。確保你沒有弄壞本實驗的前面部分，確保開啟中斷能夠正常工作（即： forktree）。另外，嘗試使用 make CPUS=2 target 在多個 CPU 上執行它。現在，你應該能夠通過 stresssched 測試。可以執行 make grade 去確認。現在，你的得分應該是 65 分了（總分為 80）。
（嚴格來說，在 JOS 中這是“環境間通訊” 或 “IEC”，但所有人都稱它為 IPC，因此我們使用標準的術語。）
我們一直專注於作業系統的隔離部分，這就產生了一種錯覺，好像每個程式都有一個機器完整地為它服務。一個作業系統的另一個重要服務是，當它們需要時，允許程式之間相互通訊。讓程式與其它程式互動可以讓它的功能更加強大。Unix 的管道模型就是一個權威的範例。
進程間通訊有許多模型。關於哪個模型最好的爭論從來沒有停止過。我們不去參與這種爭論。相反，我們將要實現一個簡單的 IPC 機制，然後嘗試使用它。
你將要去實現另外幾個 JOS 核心的系統呼叫，由它們共同來提供一個簡單的進程間通訊機制。你將要實現兩個系統呼叫，sys_ipc_recv 和 sys_ipc_try_send。然後你將要實現兩個庫去封裝 ipc_recv 和 ipc_send。
使用者環境可以使用 JOS 的 IPC 機制相互之間傳送 “訊息” 到每個其它環境，這些訊息有兩部分組成：一個單個的 32 位值，和可選的一個單個頁對映。允許環境在訊息中傳遞頁對映，提供了一個高效的方式，傳輸比一個僅適合單個的 32 位整數更多的資料，並且也允許環境去輕鬆地設定安排共用記憶體。
一個環境通過呼叫 sys_ipc_recv 去接收訊息。這個系統呼叫將取消對當前環境的排程，並且不會再次去執行它，直到訊息被接收為止。當一個環境正在等待接收一個訊息時，任何其它環境都能夠給它傳送一個訊息 — 而不僅是一個特定的環境，而且不僅是與接收環境有父子關係的環境。換句話說，你在 Part A 中實現的許可權檢查將不會應用到 IPC 上，因為 IPC 系統呼叫是經過慎重設計的，因此可以認為它是“安全的”：一個環境並不能通過給它傳送訊息導致另一個環境發生故障（除非目標環境也存在 Bug）。
嘗試去傳送一個值時，一個環境使用接收者的 ID 和要傳送的值去呼叫 sys_ipc_try_send 來傳送。如果指定的環境正在接收（它呼叫了 sys_ipc_recv，但尚未收到值），那麼這個環境將去傳送訊息並返回 0。否則將返回 -E_IPC_NOT_RECV 來表示目標環境當前不希望來接收值。
在使用者空間中的一個庫函數 ipc_recv 將去呼叫 sys_ipc_recv，然後，在當前環境的 struct Env 中查詢關於接收到的值的相關資訊。
同樣，一個庫函數 ipc_send 將去不停地呼叫 sys_ipc_try_send 來傳送訊息，直到傳送成功為止。
當一個環境使用一個有效的 dstva 引數（低於 UTOP）去呼叫 sys_ipc_recv 時，環境將宣告願意去接收一個頁對映。如果傳送方傳送一個頁，那麼那個頁應該會被對映到接收者地址空間的 dstva 處。如果接收者在 dstva 已經有了一個頁對映，那麼已存在的那個頁對映將被取消對映。
當一個環境使用一個有效的 srcva 引數（低於 UTOP）去呼叫 sys_ipc_try_send 時，意味著傳送方希望使用 perm 許可權去傳送當前對映在 srcva 處的頁給接收方。在 IPC 成功之後，傳送方在它的地址空間中，保留了它最初對映到 srcva 位置的頁。而接收方也獲得了最初由它指定的、在它的地址空間中的 dstva 處的、對映到相同物理頁的對映。最後的結果是，這個頁成為傳送方和接收方共用的頁。
如果傳送方和接收方都沒有表示要轉移這個頁，那麼就不會有頁被轉移。在任何 IPC 之後，核心將在接收方的 Env 結構上設定新的 env_ipc_perm 欄位，以允許接收頁，或者將它設定為 0，表示不再接收。
練習 15、實現
kern/syscall.c中的sys_ipc_recv和sys_ipc_try_send。在實現它們之前一起閱讀它們的注釋資訊，因為它們要一起工作。當你在這些程式中呼叫envid2env時，你應該去設定checkperm的標誌為 0，這意味著允許任何環境去傳送 IPC 訊息到另外的環境，並且核心除了驗證目標 envid 是否有效外，不做特別的許可權檢查。接著實現
lib/ipc.c中的ipc_recv和ipc_send函數。使用
user/pingpong和user/primes函數去測試你的 IPC 機制。user/primes將為每個質數生成一個新環境，直到 JOS 耗盡環境為止。你可能會發現，閱讀user/primes.c非常有趣，你將看到所有的 fork 和 IPC 都是在幕後進行。
.
小挑戰！為什麼
ipc_send要迴圈呼叫？修改系統呼叫介面，讓它不去迴圈。確保你能處理多個環境嘗試同時傳送訊息到一個環境上的情況。
.
小挑戰！質數篩選是在大規模並行程式中傳遞訊息的一個很巧妙的用法。閱讀 C. A. R. Hoare 寫的 《Communicating Sequential Processes》，Communications of the ACM_ 21(8) (August 1978)， 666-667，並去實現矩陣乘法範例。
.
小挑戰！控制訊息傳遞的最令人印象深刻的一個例子是，Doug McIlroy 的冪序列計算器，它在 M. Douglas McIlroy，《Squinting at Power Series》，Software–Practice and Experience， 20(7) (July 1990)，661-683 中做了詳細描述。實現了它的冪序列計算器，並且計算了 sin ( x + x 3) 的冪序列。
.
小挑戰！通過應用 Liedtke 的論文（通過核心設計改善 IPC 效能）中的一些技術、或你可以想到的其它技巧，來讓 JOS 的 IPC 機制更高效。為此，你可以隨意修改核心的系統呼叫 API，只要你的程式碼向後相容我們的評級指令碼就行。
Part C 到此結束了。確保你通過了所有的評級測試，並且不要忘了將你的小挑戰的答案寫入到 answers-lab4.txt 中。
在動手實驗之前， 使用 git status 和 git diff 去檢查你的更改，並且不要忘了去使用 git add answers-lab4.txt 新增你的小挑戰的答案。在你全部完成後，使用 git commit -am 'my solutions to lab 4’ 提交你的更改，然後 make handin 並關注它的動向。