Lab 4: Preemptive Multitasking tags: mit 6.828, os 概述 本文是lab4的實驗報告,主要圍繞 進程 相關概念進行介紹。主要將四個知識點: 1. 開啟多處理器。現代處理器一般都是多核的,這樣每個CPU能同時運行不同進程,實現並行。需要用鎖解決多CPU的 ...
Lab 4: Preemptive Multitasking
tags: mit-6.828, os
概述
本文是lab4的實驗報告,主要圍繞進程相關概念進行介紹。主要將四個知識點:
- 開啟多處理器。現代處理器一般都是多核的,這樣每個CPU能同時運行不同進程,實現並行。需要用鎖解決多CPU的競爭。
- 實現進程調度演算法。
- 實現寫時拷貝fork(進程創建)。
- 實現進程間通信。
Part A: Multiprocessor Support and Cooperative Multitasking
該部分做三件事:
- 使JOS支持多CPU
- 實現系統調用允許普通進程創建新的進程
- 實現協作式進程調度
Multiprocessor Support
我們將使JOS支持"symmetric multiprocessing" (SMP),這是一種所有CPU共用系統資源的多處理器模式。在啟動階段這些CPU將被分為兩類:
- 啟動CPU(BSP):負責初始化系統,啟動操作系統。
- 應用CPU(AP):操作系統啟動後由BSP激活。
哪一個CPU是BSP由硬體和BISO決定,到目前位置所有JOS代碼都運行在BSP上。
在SMP系統中,每個CPU都有一個對應的local APIC(LAPIC),負責傳遞中斷。CPU通過記憶體映射IO(MMIO)訪問它對應的APIC,這樣就能通過訪問記憶體達到訪問設備寄存器的目的。LAPIC從物理地址0xFE000000開始,JOS將通過MMIOBASE虛擬地址訪問該物理地址。
Exercise 1
實現kern/pmap.c中的mmio_map_region()。
解決:可以參照boot_map_region()
void *
mmio_map_region(physaddr_t pa, size_t size)
{
// Where to start the next region. Initially, this is the
// beginning of the MMIO region. Because this is static, its
// value will be preserved between calls to mmio_map_region
// (just like nextfree in boot_alloc).
static uintptr_t base = MMIOBASE;
// Reserve size bytes of virtual memory starting at base and
// map physical pages [pa,pa+size) to virtual addresses
// [base,base+size). Since this is device memory and not
// regular DRAM, you'll have to tell the CPU that it isn't
// safe to cache access to this memory. Luckily, the page
// tables provide bits for this purpose; simply create the
// mapping with PTE_PCD|PTE_PWT (cache-disable and
// write-through) in addition to PTE_W. (If you're interested
// in more details on this, see section 10.5 of IA32 volume
// 3A.)
//
// Be sure to round size up to a multiple of PGSIZE and to
// handle if this reservation would overflow MMIOLIM (it's
// okay to simply panic if this happens).
//
// Hint: The staff solution uses boot_map_region.
//
// Your code here:
size = ROUNDUP(pa+size, PGSIZE);
pa = ROUNDDOWN(pa, PGSIZE);
size -= pa;
if (base+size >= MMIOLIM) panic("not enough memory");
boot_map_region(kern_pgdir, base, size, pa, PTE_PCD|PTE_PWT|PTE_W);
base += size;
return (void*) (base - size);
}
Application Processor Bootstrap
在啟動AP之前,BSP需要搜集多處理器的信息,比如總共有多少CPU,它們的LAPIC ID以及LAPIC MMIO地址。mp_init()函數從BIOS中讀取這些信息。具體代碼在mp_init()中,該函數會在進入內核後被i386_init()調用,主要作用就是讀取mp configuration table中保存的CPU信息,初始化cpus數組,ncpu(總共多少可用CPU),bootcpu指針(指向BSP對應的CpuInfo結構)。
真正啟動AP的是在boot_aps()中,該函數遍歷cpus數組,一個接一個啟動所有的AP,當一個AP啟動後會執行kern/mpentry.S中的代碼,然後跳轉到mp_main()中,該函數為當前AP設置GDT,TTS,最後設置cpus數組中當前CPU對應的結構的cpu_status為CPU_STARTED。更多關於SMP的知識可以參考:https://pdos.csail.mit.edu/6.828/2018/readings/ia32/MPspec.pdf和https://wenku.baidu.com/view/615ea3c6aa00b52acfc7ca97.html
Per-CPU State and Initialization
JOS使用struct CpuInfo結構來記錄CPU的信息:
struct CpuInfo {
uint8_t cpu_id; // Local APIC ID; index into cpus[] below
volatile unsigned cpu_status; // The status of the CPU
struct Env *cpu_env; // The currently-running environment.
struct Taskstate cpu_ts; // Used by x86 to find stack for interrupt
};
cpunum()總是返回調用它的CPU的ID,巨集thiscpu提供了更加方便的方式獲取當前代碼所在的CPU對應的CpuInfo結構。
每個CPU如下信息是當前CPU私有的:
- 內核棧:內核代碼中的數組
percpu_kstacks[NCPU][KSTKSIZE]
為每個CPU都保留了KSTKSIZE大小的內核棧。從內核線性地址空間看CPU 0的棧從KSTACKTOP開始,CPU 1的內核棧將從CPU 0棧後面KSTKGAP位元組處開始,以此類推,參見inc/memlayout.h。 - TSS和TSS描述符:每個CPU都需要單獨的TSS和TSS描述符來指定該CPU對應的內核棧。
- 進程結構指針:每個CPU都會獨立運行一個進程的代碼,所以需要Env指針。
- 系統寄存器:比如cr3, gdt, ltr這些寄存器都是每個CPU私有的,每個CPU都需要單獨設置。
到目前為止CpuInfo和Env關係可以總結如下:
Exercise 3:
修改mem_init_mp(),將內核棧線性地址映射到percpu_kstacks處的物理地址處。
解決:本質上是修改kern_pdir指向的頁目錄和頁表,按照inc/memlayout.h中的結構進行映射即可。
static void
mem_init_mp(void)
{
// Map per-CPU stacks starting at KSTACKTOP, for up to 'NCPU' CPUs.
//
// For CPU i, use the physical memory that 'percpu_kstacks[i]' refers
// to as its kernel stack. CPU i's kernel stack grows down from virtual
// address kstacktop_i = KSTACKTOP - i * (KSTKSIZE + KSTKGAP), and is
// divided into two pieces, just like the single stack you set up in
// mem_init:
// * [kstacktop_i - KSTKSIZE, kstacktop_i)
// -- backed by physical memory
// * [kstacktop_i - (KSTKSIZE + KSTKGAP), kstacktop_i - KSTKSIZE)
// -- not backed; so if the kernel overflows its stack,
// it will fault rather than overwrite another CPU's stack.
// Known as a "guard page".
// Permissions: kernel RW, user NONE
//
// LAB 4: Your code here:
for (int i = 0; i < NCPU; i++) {
boot_map_region(kern_pgdir,
KSTACKTOP - KSTKSIZE - i * (KSTKSIZE + KSTKGAP),
KSTKSIZE,
PADDR(percpu_kstacks[i]),
PTE_W);
}
}
Locking
目前我們已經有多個CPU同時在執行內核代碼了,我們必須要處理競爭條件。最簡單粗暴的辦法就是使用"big kernel lock","big kernel lock"是一個全局鎖,進程從用戶態進入內核後獲取該鎖,退出內核釋放該鎖。這樣就能保證只有一個CPU在執行內核代碼,但缺點也很明顯就是一個CPU在執行內核代碼時,另一個CPU如果也想進入內核,就會處於等待的狀態。
鎖的數據結構在kern/spinlock.h中:
struct spinlock {
unsigned locked; // Is the lock held?
};
獲取鎖,釋放鎖的操作在kern/spinlock.c中:
void
spin_lock(struct spinlock *lk)
{
// The xchg is atomic.
// It also serializes, so that reads after acquire are not
// reordered before it.
while (xchg(&lk->locked, 1) != 0) //原理見:https://pdos.csail.mit.edu/6.828/2018/xv6/book-rev11.pdf chapter 4
asm volatile ("pause");
}
void
spin_unlock(struct spinlock *lk)
{
// The xchg instruction is atomic (i.e. uses the "lock" prefix) with
// respect to any other instruction which references the same memory.
// x86 CPUs will not reorder loads/stores across locked instructions
// (vol 3, 8.2.2). Because xchg() is implemented using asm volatile,
// gcc will not reorder C statements across the xchg.
xchg(&lk->locked, 0);
}
這是一種"spin-locks"。對於spin_lock()獲取鎖的操作,使用xchg這個原子操作,xchg()封裝了該指令,交換lk->locked和1的值,並將lk-locked原來的值返回。如果lk-locked原來的值不等於0,說明該鎖已經被別的CPU申請了,繼續執行while迴圈吧。對於spin_unlock()釋放鎖的操作,直接將lk->locked置為0,表明我已經用完了,這個鎖可以被別人獲取了。
有了獲取鎖和釋放鎖的函數,我們看下哪些地方需要加鎖,和釋放鎖:
- i386_init()中,BSP喚醒其它AP前需要獲取內核鎖。
- mp_main()中,AP需要在執行sched_yield()前獲取內核鎖。
- trap()中,需要獲取內核鎖,因為這是用戶態進入內核的唯一入口。
- env_run()中,需要釋放內核鎖,因為該函數使用iret指令,從內核返回用戶態。
Exercise 5
在前面提的位置添加加鎖和釋放鎖的代碼。比較簡單就不貼代碼了。
Round-Robin Scheduling
現要JOS內核需要讓CPU能在進程之間切換。目前先實現一個非搶占式的進程調度,需要當前進程主動讓出CPU,其他進程才有機會在當前CPU運行。具體實現如下:
- 實現sched_yield(),該函數選擇一個新的進程運行,從當前正在運行進程對應的Env結構下一個位置開始迴圈搜索envs數組,找到第一個cpu_status為ENV_RUNNABLE的Env結構,然後調用env_run()在當前CPU運行這個新的進程。
- 我們需要實現一個新的系統調用sys_yield(),使得用戶程式能在用戶態通知內核,當前進程希望主動讓出CPU給另一個進程。
Exercise 6
實現sched_yield()函數。
void
sched_yield(void)
{
struct Env *idle;
// Implement simple round-robin scheduling.
//
// Search through 'envs' for an ENV_RUNNABLE environment in
// circular fashion starting just after the env this CPU was
// last running. Switch to the first such environment found.
//
// If no envs are runnable, but the environment previously
// running on this CPU is still ENV_RUNNING, it's okay to
// choose that environment. Make sure curenv is not null before
// dereferencing it.
//
// Never choose an environment that's currently running on
// another CPU (env_status == ENV_RUNNING). If there are
// no runnable environments, simply drop through to the code
// below to halt the cpu.
// LAB 4: Your code here.
int start = 0;
int j;
if (curenv) {
start = ENVX(curenv->env_id) + 1; //從當前Env結構的後一個開始
}
for (int i = 0; i < NENV; i++) { //遍歷所有Env結構
j = (start + i) % NENV;
if (envs[j].env_status == ENV_RUNNABLE) {
env_run(&envs[j]);
}
}
if (curenv && curenv->env_status == ENV_RUNNING) { //這是必須的,假設當前只有一個Env,如果沒有這個判斷,那麼這個CPU將會停機
env_run(curenv);
}
// sched_halt never returns
sched_halt();
}
需要註意:當前CPU在envs數組中找了一圈後沒找到合適的Env去執行,需要重新執行之前運行的進程,否則當前CPU就會進入停機狀態。
System Calls for Environment Creation
儘管現在內核有能力在多進程之前切換,但是僅限於內核創建的用戶進程。目前JOS還沒有提供系統調用,使用戶進程能創建新的進程。
Unix提供fork()系統調用創建新的進程,fork()拷貝父進程的地址空間和寄存器狀態到子進程。父進程從fork()返回的是子進程的進程ID,而子進程從fork()返回的是0。父進程和子進程有獨立的地址空間,任何一方修改了記憶體,不會影響到另一方。
現在需要實現如下系統調用:
- sys_exofork():
創建一個新的進程,用戶地址空間沒有映射,不能運行,寄存器狀態和父環境一致。在父進程中sys_exofork()返回新進程的envid,子進程返回0。 - sys_env_set_status:設置一個特定進程的狀態為ENV_RUNNABLE或ENV_NOT_RUNNABLE。
- sys_page_alloc:為特定進程分配一個物理頁,映射指定線性地址va到該物理頁。
- sys_page_map:拷貝頁表,使指定進程共用當前進程相同的映射關係。本質上是修改特定進程的頁目錄和頁表。
- sys_page_unmap:解除頁映射關係。本質上是修改指定用戶環境的頁目錄和頁表。
Exercise 7:
實現上述所有的系統調用:
sys_exofork(void):
static envid_t
sys_exofork(void)
{
// Create the new environment with env_alloc(), from kern/env.c.
// It should be left as env_alloc created it, except that
// status is set to ENV_NOT_RUNNABLE, and the register set is copied
// from the current environment -- but tweaked so sys_exofork
// will appear to return 0.
// LAB 4: Your code here.
struct Env *e;
int ret = env_alloc(&e, curenv->env_id); //分配一個Env結構
if (ret < 0) {
return ret;
}
e->env_tf = curenv->env_tf; //寄存器狀態和當前進程一致
e->env_status = ENV_NOT_RUNNABLE; //目前還不能運行
e->env_tf.tf_regs.reg_eax = 0; //新的進程從sys_exofork()的返回值應該為0
return e->env_id;
}
sys_env_set_status(envid_t envid, int status):
static int
sys_env_set_status(envid_t envid, int status)
{
// Hint: Use the 'envid2env' function from kern/env.c to translate an
// envid to a struct Env.
// You should set envid2env's third argument to 1, which will
// check whether the current environment has permission to set
// envid's status.
if (status != ENV_NOT_RUNNABLE && status != ENV_RUNNABLE) return -E_INVAL;
struct Env *e;
int ret = envid2env(envid, &e, 1);
if (ret < 0) {
return ret;
}
e->env_status = status;
return 0;
}
sys_page_alloc(envid_t envid, void *va, int perm):
static int
sys_page_alloc(envid_t envid, void *va, int perm)
{
// Hint: This function is a wrapper around page_alloc() and
// page_insert() from kern/pmap.c.
// Most of the new code you write should be to check the
// parameters for correctness.
// If page_insert() fails, remember to free the page you
// allocated!
// LAB 4: Your code here.
struct Env *e; //根據envid找出需要操作的Env結構
int ret = envid2env(envid, &e, 1);
if (ret) return ret; //bad_env
if ((va >= (void*)UTOP) || (ROUNDDOWN(va, PGSIZE) != va)) return -E_INVAL; //一系列判定
int flag = PTE_U | PTE_P;
if ((perm & flag) != flag) return -E_INVAL;
struct PageInfo *pg = page_alloc(1); //分配物理頁
if (!pg) return -E_NO_MEM;
ret = page_insert(e->env_pgdir, pg, va, perm); //建立映射關係
if (ret) {
page_free(pg);
return ret;
}
return 0;
}
sys_page_map(envid_t srcenvid, void srcva,envid_t dstenvid, void dstva, int perm):
static int
sys_page_map(envid_t srcenvid, void *srcva,
envid_t dstenvid, void *dstva, int perm)
{
// Hint: This function is a wrapper around page_lookup() and
// page_insert() from kern/pmap.c.
// Again, most of the new code you write should be to check the
// parameters for correctness.
// Use the third argument to page_lookup() to
// check the current permissions on the page.
// LAB 4: Your code here.
struct Env *se, *de;
int ret = envid2env(srcenvid, &se, 1);
if (ret) return ret; //bad_env
ret = envid2env(dstenvid, &de, 1);
if (ret) return ret; //bad_env
// -E_INVAL if srcva >= UTOP or srcva is not page-aligned,
// or dstva >= UTOP or dstva is not page-aligned.
if (srcva >= (void*)UTOP || dstva >= (void*)UTOP ||
ROUNDDOWN(srcva,PGSIZE) != srcva || ROUNDDOWN(dstva,PGSIZE) != dstva)
return -E_INVAL;
// -E_INVAL is srcva is not mapped in srcenvid's address space.
pte_t *pte;
struct PageInfo *pg = page_lookup(se->env_pgdir, srcva, &pte);
if (!pg) return -E_INVAL;
// -E_INVAL if perm is inappropriate (see sys_page_alloc).
int flag = PTE_U|PTE_P;
if ((perm & flag) != flag) return -E_INVAL;
// -E_INVAL if (perm & PTE_W), but srcva is read-only in srcenvid's
// address space.
if (((*pte&PTE_W) == 0) && (perm&PTE_W)) return -E_INVAL;
// -E_NO_MEM if there's no memory to allocate any necessary page tables.
ret = page_insert(de->env_pgdir, pg, dstva, perm);
return ret;
}
sys_page_unmap(envid_t envid, void *va):
static int
sys_page_unmap(envid_t envid, void *va)
{
// Hint: This function is a wrapper around page_remove().
// LAB 4: Your code here.
struct Env *env;
int ret = envid2env(envid, &env, 1);
if (ret) return ret;
if ((va >= (void*)UTOP) || (ROUNDDOWN(va, PGSIZE) != va)) return -E_INVAL;
page_remove(env->env_pgdir, va);
return 0;
}
Part B: Copy-on-Write Fork
實現fork()有多種方式,一種是將父進程的內容全部拷貝一次,這樣的話父進程和子進程就能做到進程隔離,但是這種方式非常耗時,需要在物理記憶體中複製父進程的內容。
另一種方式叫做寫時拷貝的技術(copy on write),父進程將自己的頁目錄和頁表複製給子進程,這樣父進程和子進程就能訪問相同的內容。只有當一方執行寫操作時,才複製這一物理頁。這樣既能做到地址空間隔離,又能節省了大量的拷貝工作。我畫了個圖來比較這兩種fork方式:
想要實現寫時拷貝的fork()需要先實現用戶級別的缺頁中斷處理函數。
User-level page fault handling
為了實現用戶級別的頁錯誤處理函數,進程需要註冊頁錯誤處理函數,需要實現一個sys_env_set_pgfault_upcall()系統調用提供支持。
Exercise 8:
實現sys_env_set_pgfault_upcall(envid_t envid, void *func)系統調用。該系統調用為指定的用戶環境設置env_pgfault_upcall。缺頁中斷發生時,會執行env_pgfault_upcall指定位置的代碼。當執行env_pgfault_upcall指定位置的代碼時,棧已經轉到異常棧,並且壓入了UTrapframe結構。
static int
sys_env_set_pgfault_upcall(envid_t envid, void *func)
{
// LAB 4: Your code here.
struct Env *env;
int ret;
if ((ret = envid2env(envid, &env, 1)) < 0) {
return ret;
}
env->env_pgfault_upcall = func;
return 0;
}
Normal and Exception Stacks in User Environments
當缺頁中斷發生時,內核會返回用戶模式來處理該中斷。我們需要一個用戶異常棧,來模擬內核異常棧。JOS的用戶異常棧被定義在虛擬地址UXSTACKTOP。
Invoking the User Page Fault Handler
缺頁中斷發生時會進入內核的trap(),然後分配page_fault_handler()來處理缺頁中斷。在該函數中應該做如下幾件事:
- 判斷curenv->env_pgfault_upcall是否設置,如果沒有設置也就沒辦法修複,直接銷毀該進程。
- 修改esp,切換到用戶異常棧。
- 在棧上壓入一個UTrapframe結構。
- 將eip設置為curenv->env_pgfault_upcall,然後回到用戶態執行curenv->env_pgfault_upcall處的代碼。
UTrapframe結構如下:
<-- UXSTACKTOP
trap-time esp
trap-time eflags
trap-time eip
trap-time eax start of struct PushRegs
trap-time ecx
trap-time edx
trap-time ebx
trap-time esp
trap-time ebp
trap-time esi
trap-time edi end of struct PushRegs
tf_err (error code)
fault_va <-- %esp when handler is run
Exercise 9:
按照上面的描述實現page_fault_handler()。
void
page_fault_handler(struct Trapframe *tf)
{
uint32_t fault_va;
// Read processor's CR2 register to find the faulting address
fault_va = rcr2();
// Handle kernel-mode page faults.
// LAB 3: Your code here.
if ((tf->tf_cs & 3) == 0)
panic("page_fault_handler():page fault in kernel mode!\n");
// LAB 4: Your code here.
if (curenv->env_pgfault_upcall) {
uintptr_t stacktop = UXSTACKTOP;
if (UXSTACKTOP - PGSIZE < tf->tf_esp && tf->tf_esp < UXSTACKTOP) {
stacktop = tf->tf_esp;
}
uint32_t size = sizeof(struct UTrapframe) + sizeof(uint32_t);
user_mem_assert(curenv, (void *)stacktop - size, size, PTE_U | PTE_W);
struct UTrapframe *utr = (struct UTrapframe *)(stacktop - size);
utr->utf_fault_va = fault_va;
utr->utf_err = tf->tf_err;
utr->utf_regs = tf->tf_regs;
utr->utf_eip = tf->tf_eip;
utr->utf_eflags = tf->tf_eflags;
utr->utf_esp = tf->tf_esp; //UXSTACKTOP棧上需要保存發生缺頁異常時的%esp和%eip
curenv->env_tf.tf_eip = (uintptr_t)curenv->env_pgfault_upcall;
curenv->env_tf.tf_esp = (uintptr_t)utr;
env_run(curenv); //重新進入用戶態
}
// Destroy the environment that caused the fault.
cprintf("[%08x] user fault va %08x ip %08x\n",
curenv->env_id, fault_va, tf->tf_eip);
print_trapframe(tf);
env_destroy(curenv);
}
User-mode Page Fault Entrypoint
現在需要實現lib/pfentry.S中的_pgfault_upcall函數,該函數會作為系統調用sys_env_set_pgfault_upcall()的參數。
Exercise 10:
實現lib/pfentry.S中的_pgfault_upcall函數。
_pgfault_upcall:
// Call the C page fault handler.
pushl %esp // function argument: pointer to UTF
movl _pgfault_handler, %eax
call *%eax //調用頁處理函數
addl $4, %esp // pop function argument
// LAB 4: Your code here.
// Restore the trap-time registers. After you do this, you
// can no longer modify any general-purpose registers.
// LAB 4: Your code here.
addl $8, %esp //跳過utf_fault_va和utf_err
movl 40(%esp), %eax //保存中斷發生時的esp到eax
movl 32(%esp), %ecx //保存終端發生時的eip到ecx
movl %ecx, -4(%eax) //將中斷發生時的esp值亞入到到原來的棧中
popal
addl $4, %esp //跳過eip
// Restore eflags from the stack. After you do this, you can
// no longer use arithmetic operations or anything else that
// modifies eflags.
// LAB 4: Your code here.
popfl
// Switch back to the adjusted trap-time stack.
// LAB 4: Your code here.
popl %esp
// Return to re-execute the instruction that faulted.
// LAB 4: Your code here.
lea -4(%esp), %esp //因為之前壓入了eip的值但是沒有減esp的值,所以現在需要將esp寄存器中的值減4
ret
Exercise 11:
完成lib/pgfault.c中的set_pgfault_handler()。
void
set_pgfault_handler(void (*handler)(struct UTrapframe *utf))
{
int r;
if (_pgfault_handler == 0) {
// First time through!
// LAB 4: Your code here.
int r = sys_page_alloc(0, (void *)(UXSTACKTOP-PGSIZE), PTE_W | PTE_U | PTE_P); //為當前進程分配異常棧
if (r < 0) {
panic("set_pgfault_handler:sys_page_alloc failed");;
}
sys_env_set_pgfault_upcall(0, _pgfault_upcall); //系統調用,設置進程的env_pgfault_upcall屬性
}
// Save handler pointer for assembly to call.
_pgfault_handler = handler;
}
踩坑:
user_mem_check()中的cprintf()需要去掉,不然faultregs這個測試可能會過不了,坑啊~
缺頁處理小結:
- 引發缺頁中斷,執行內核函數鏈:trap()->trap_dispatch()->page_fault_handler()
- page_fault_handler()切換棧到用戶異常棧,並且壓入UTrapframe結構,然後調用curenv->env_pgfault_upcall(系統調用sys_env_set_pgfault_upcall()設置)處代碼。又重新回到用戶態。
- 進入_pgfault_upcall處的代碼執行,調用_pgfault_handler(庫函數set_pgfault_handler()設置)處的代碼,最後返回到缺頁中斷發生時的那條指令重新執行。
Implementing Copy-on-Write Fork
到目前已經可以實現用戶級別的寫時拷貝fork函數了。fork流程如下:
- 使用set_pgfault_handler()設置缺頁處理函數。
- 調用sys_exofork()系統調用,在內核中創建一個Env結構,複製當前用戶環境寄存器狀態,UTOP以下的頁目錄還沒有建立,新創建的進程還不能直接運行。
- 拷貝父進程的頁表和頁目錄到子進程。對於可寫的頁,將對應的PTE的PTE_COW位設置為1。
- 為子進程設置_pgfault_upcall。
- 將子進程狀態設置為ENV_RUNNABLE。
缺頁處理函數pgfault()流程如下:
- 如果發現錯誤是因為寫造成的(錯誤碼是FEC_WR)並且該頁的PTE_COW是1,則進行執行第2步,否則直接panic。
- 分配一個新的物理頁,並將之前出現錯誤的頁的內容拷貝到新的物理頁,然後重新映射線性地址到新的物理頁。
Exercise 12:
實現lib/fork.c中的fork, duppage and pgfault。
static void
pgfault(struct UTrapframe *utf)
{
void *addr = (void *) utf->utf_fault_va;
uint32_t err = utf->utf_err;
int r;
// Check that the faulting access was (1) a write, and (2) to a
// copy-on-write page. If not, panic.
// Hint:
// Use the read-only page table mappings at uvpt
// (see <inc/memlayout.h>).
// LAB 4: Your code here.
if (!((err & FEC_WR) && (uvpt[PGNUM(addr)] & PTE_COW))) { //只有因為寫操作寫時拷貝的地址這中情況,才可以搶救。否則一律panic
panic("pgfault():not cow");
}
// Allocate a new page, map it at a temporary location (PFTEMP),
// copy the data from the old page to the new page, then move the new
// page to the old page's address.
// Hint:
// You should make three system calls.
// LAB 4: Your code here.
addr = ROUNDDOWN(addr, PGSIZE);
if ((r = sys_page_map(0, addr, 0, PFTEMP, PTE_U|PTE_P)) < 0) //將當前進程PFTEMP也映射到當前進程addr指向的物理頁
panic("sys_page_map: %e", r);
if ((r = sys_page_alloc(0, addr, PTE_P|PTE_U|PTE_W)) < 0) //令當前進程addr指向新分配的物理頁
panic("sys_page_alloc: %e", r);
memmove(addr, PFTEMP, PGSIZE); //將PFTEMP指向的物理頁拷貝到addr指向的物理頁
if ((r = sys_page_unmap(0, PFTEMP)) < 0) //解除當前進程PFTEMP映射
panic("sys_page_unmap: %e", r);
}
static int
duppage(envid_t envid, unsigned pn)
{
int r;
// LAB 4: Your code here.
void *addr = (void*) (pn * PGSIZE);
if (uvpt[pn] & PTE_SHARE) {
sys_page_map(0, addr, envid, addr, PTE_SYSCALL); //對於表示為PTE_SHARE的頁,拷貝映射關係,並且兩個進程都有讀寫許可權
} else if ((uvpt[pn] & PTE_W) || (uvpt[pn] & PTE_COW)) { //對於UTOP以下的可寫的或者寫時拷貝的頁,拷貝映射關係的同時,需要同時標記當前進程和子進程的頁表項為PTE_COW
if ((r = sys_page_map(0, addr, envid, addr, PTE_COW|PTE_U|PTE_P)) < 0)
panic("sys_page_map:%e", r);
if ((r = sys_page_map(0, addr, 0, addr, PTE_COW|PTE_U|PTE_P)) < 0)
panic("sys_page_map:%e", r);
} else {
sys_page_map(0, addr, envid, addr, PTE_U|PTE_P); //對於只讀的頁,只需要拷貝映射關係即可
}
return 0;
}
envid_t
fork(void)
{
// LAB 4: Your code here.
extern void _pgfault_upcall(void);
set_pgfault_handler(pgfault); //設置缺頁處理函數
envid_t envid = sys_exofork(); //系統調用,只是簡單創建一個Env結構,複製當前用戶環境寄存器狀態,UTOP以下的頁目錄還沒有建立
if (envid == 0) { //子進程將走這個邏輯
thisenv = &envs[ENVX(sys_getenvid())];
return 0;
}
if (envid < 0) {
panic("sys_exofork: %e", envid);
}
uint32_t addr;
for (addr = 0; addr < USTACKTOP; addr += PGSIZE) {
if ((uvpd[PDX(addr)] & PTE_P) && (uvpt[PGNUM(addr)] & PTE_P) //為什麼uvpt[pagenumber]能訪問到第pagenumber項頁表條目:https://pdos.csail.mit.edu/6.828/2018/labs/lab4/uvpt.html
&& (uvpt[PGNUM(addr)] & PTE_U)) {
duppage(envid, PGNUM(addr)); //拷貝當前進程映射關係到子進程
}
}
int r;
if ((r = sys_page_alloc(envid, (void *)(UXSTACKTOP-PGSIZE), PTE_P | PTE_W | PTE_U)) < 0) //為子進程分配異常棧
panic("sys_page_alloc: %e", r);
sys_env_set_pgfault_upcall(envid, _pgfault_upcall); //為子進程設置_pgfault_upcall
if ((r = sys_env_set_status(envid, ENV_RUNNABLE)) < 0) //設置子進程為ENV_RUNNABLE狀態
panic("sys_env_set_status: %e", r);
return envid;
}
Part C: Preemptive Multitasking and Inter-Process communication (IPC)
Handling Clock Interrupts
目前程式一旦進入用戶模式,除非發生中斷,否則CPU永遠不會再執行內核代碼。我們需要開啟時鐘中斷,強迫進入內核,然後內核就可以切換另一個進程執行。
lapic_init()和pic_init()設置時鐘中斷控制器產生中斷。需要寫代碼來處理中斷。
Exercise 14:
修改trap_dispatch(),使時鐘中斷發生時,切換到另一個進程執行。
if (tf->tf_trapno == IRQ_OFFSET + IRQ_TIMER) {
lapic_eoi();
sched_yield();
return;
}
Inter-Process communication (IPC)
到目前為止,我們都在做隔離的事情。操作系統另一個重要的內容是允許程式相互交流。
IPC in JOS
我們將要實現sys_ipc_recv()和sys_ipc_try_send()這兩個系統調用,來實現進程間通信。並且實現兩個包裝函數ipc_recv()和 ipc_send()。
JOS中進程間通信的“消息”包含兩部分:
- 一個32位的值。
- 可選的頁映射關係。
Sending and Receiving Messages
sys_ipc_recv()和sys_ipc_try_send()是這麼協作的:
- 當某個進程調用sys_ipc_recv()後,該進程會阻塞(狀態被置為ENV_NOT_RUNNABLE),直到另一個進程向它發送“消息”。當進程調用sys_ipc_recv()傳入dstva參數時,表明當前進程準備接收頁映射。
- 進程可以調用sys_ipc_try_send()向指定的進程發送“消息”,如果目標進程已經調用了sys_ipc_recv(),那麼就發送數據,然後返回0,否則返回-E_IPC_NOT_RECV,表示目標進程不希望接受數據。當傳入srcva參數時,表明發送進程希望和接收進程共用srcva對應的物理頁。如果發送成功了發送進程的srcva和接收進程的dstva將指向相同的物理頁。
Exercise 15
實現sys_ipc_recv()和sys_ipc_try_send()。包裝函數ipc_recv()和 ipc_send()。
static int
sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)
{
// LAB 4: Your code here.
struct Env *rcvenv;
int ret = envid2env(envid, &rcvenv, 0);
if (ret) return ret;
if (!rcvenv->env_ipc_recving) return -E_IPC_NOT_RECV;
if (srcva < (void*)UTOP) {
pte_t *pte;
struct PageInfo *pg = page_lookup(curenv->env_pgdir, srcva, &pte);
//按照註釋的順序進行判定
if (debug) {
cprintf("sys_ipc_try_send():srcva=%08x\n", (uintptr_t)srcva);
}
if (srcva != ROUNDDOWN(srcva, PGSIZE)) { //srcva沒有頁對齊
if (debug) {
cprintf("sys_ipc_try_send():srcva is not page-alligned\n");
}
return -E_INVAL;
}
if ((*pte & perm & 7) != (perm & 7)) { //perm應該是*pte的子集
if (debug) {
cprintf("sys_ipc_try_send():perm is wrong\n");
}
return -E_INVAL;
}
if (!pg) { //srcva還沒有映射到物理頁
if (debug) {
cprintf("sys_ipc_try_send():srcva is not maped\n");
}
return -E_INVAL;
}
if ((perm & PTE_W) && !(*pte & PTE_W)) { //寫許可權
if (debug) {
cprintf("sys_ipc_try_send():*pte do not have PTE_W, but perm have\n");
}
return -E_INVAL;
}
if (rcvenv->env_ipc_dstva < (void*)UTOP) {
ret = page_insert(rcvenv->env_pgdir, pg, rcvenv->env_ipc_dstva, perm); //共用相同的映射關係
if (ret) return ret;
rcvenv->env_ipc_perm = perm;
}
}
rcvenv->env_ipc_recving = 0; //標記接受進程可再次接受信息
rcvenv->env_ipc_from = curenv->env_id;
rcvenv->env_ipc_value = value;
rcvenv->env_status = ENV_RUNNABLE;
rcvenv->env_tf.tf_regs.reg_eax = 0;
return 0;
}
static int
sys_ipc_recv(void *dstva)
{
// LAB 4: Your code here.
if (dstva < (void *)UTOP && dstva != ROUNDDOWN(dstva, PGSIZE)) {
return -E_INVAL;
}
curenv->env_ipc_recving = 1;
curenv->env_status = ENV_NOT_RUNNABLE;
curenv->env_ipc_dstva = dstva;
sys_yield();
return 0;
}
int32_t
ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)
{
// LAB 4: Your code here.
if (pg == NULL) {
pg = (void *)-1;
}
int r = sys_ipc_recv(pg);
if (r < 0) { //系統調用失敗
if (from_env_store) *from_env_store = 0;
if (perm_store) *perm_store = 0;
return r;
}
if (from_env_store)
*from_env_store = thisenv->env_ipc_from;
if (perm_store)
*perm_store = thisenv->env_ipc_perm;
return thisenv->env_ipc_value;
}
void
ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)
{
// LAB 4: Your code here.
if (pg == NULL) {
pg = (void *)-1;
}
int r;
while(1) {
r = sys_ipc_try_send(to_env, val, pg, perm);
if (r == 0) { //發送成功
return;
} else if (r == -E_IPC_NOT_RECV) { //接收進程沒有準備好
sys_yield();
} else { //其它錯誤
panic("ipc_send():%e", r);
}
}
}
IPC原理可以總結為下圖:
總結
本lab還是圍繞進程這個概念來展開的。主要介紹了四部分:
- 支持多處理器。現代處理器一般都是多核的,這樣每個CPU能同時運行不同進程,實現並行。需要用鎖解決多CPU的競爭。 CPU和進程在內核中的數據結構如下圖所示:
- 實現進程調度演算法。 一種是非搶占式式的,另一種是搶占式的,藉助時鐘中斷實現。
- 實現寫時拷貝fork(進程創建)。 原理總結如下:
- 實現進程間通信。原理總結如下:
具體代碼在:https://github.com/gatsbyd/mit_6.828_jos
如有錯誤,歡迎指正(*^_^*):
15313676365