MIT-6.828-JOS-lab4:Preemptive Multitasking

来源:https://www.cnblogs.com/gatsby123/archive/2018/11/08/9930630.html
-Advertisement-
Play Games

Lab 4: Preemptive Multitasking tags: mit 6.828, os 概述 本文是lab4的實驗報告,主要圍繞 進程 相關概念進行介紹。主要將四個知識點: 1. 開啟多處理器。現代處理器一般都是多核的,這樣每個CPU能同時運行不同進程,實現並行。需要用鎖解決多CPU的 ...


Lab 4: Preemptive Multitasking

tags: mit-6.828, os


概述

本文是lab4的實驗報告,主要圍繞進程相關概念進行介紹。主要將四個知識點:

  1. 開啟多處理器。現代處理器一般都是多核的,這樣每個CPU能同時運行不同進程,實現並行。需要用鎖解決多CPU的競爭。
  2. 實現進程調度演算法。
  3. 實現寫時拷貝fork(進程創建)。
  4. 實現進程間通信

Part A: Multiprocessor Support and Cooperative Multitasking

該部分做三件事:

  1. 使JOS支持多CPU
  2. 實現系統調用允許普通進程創建新的進程
  3. 實現協作式進程調度

Multiprocessor Support

我們將使JOS支持"symmetric multiprocessing" (SMP),這是一種所有CPU共用系統資源的多處理器模式。在啟動階段這些CPU將被分為兩類:

  1. 啟動CPU(BSP):負責初始化系統,啟動操作系統。
  2. 應用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.pdfhttps://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私有的:

  1. 內核棧:內核代碼中的數組percpu_kstacks[NCPU][KSTKSIZE]為每個CPU都保留了KSTKSIZE大小的內核棧。從內核線性地址空間看CPU 0的棧從KSTACKTOP開始,CPU 1的內核棧將從CPU 0棧後面KSTKGAP位元組處開始,以此類推,參見inc/memlayout.h。
  2. TSS和TSS描述符:每個CPU都需要單獨的TSS和TSS描述符來指定該CPU對應的內核棧。
  3. 進程結構指針:每個CPU都會獨立運行一個進程的代碼,所以需要Env指針。
  4. 系統寄存器:比如cr3, gdt, ltr這些寄存器都是每個CPU私有的,每個CPU都需要單獨設置。

到目前為止CpuInfo和Env關係可以總結如下:Env和CpuInfo關係

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,表明我已經用完了,這個鎖可以被別人獲取了。
有了獲取鎖和釋放鎖的函數,我們看下哪些地方需要加鎖,和釋放鎖:

  1. i386_init()中,BSP喚醒其它AP前需要獲取內核鎖。
  2. mp_main()中,AP需要在執行sched_yield()前獲取內核鎖。
  3. trap()中,需要獲取內核鎖,因為這是用戶態進入內核的唯一入口。
  4. env_run()中,需要釋放內核鎖,因為該函數使用iret指令,從內核返回用戶態。

Exercise 5

在前面提的位置添加加鎖和釋放鎖的代碼。比較簡單就不貼代碼了。

Round-Robin Scheduling

現要JOS內核需要讓CPU能在進程之間切換。目前先實現一個非搶占式的進程調度,需要當前進程主動讓出CPU,其他進程才有機會在當前CPU運行。具體實現如下:

  1. 實現sched_yield(),該函數選擇一個新的進程運行,從當前正在運行進程對應的Env結構下一個位置開始迴圈搜索envs數組,找到第一個cpu_status為ENV_RUNNABLE的Env結構,然後調用env_run()在當前CPU運行這個新的進程。
  2. 我們需要實現一個新的系統調用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。父進程和子進程有獨立的地址空間,任何一方修改了記憶體,不會影響到另一方。
現在需要實現如下系統調用:

  1. sys_exofork():
    創建一個新的進程,用戶地址空間沒有映射,不能運行,寄存器狀態和父環境一致。在父進程中sys_exofork()返回新進程的envid,子進程返回0。
  2. sys_env_set_status:設置一個特定進程的狀態為ENV_RUNNABLE或ENV_NOT_RUNNABLE。
  3. sys_page_alloc:為特定進程分配一個物理頁,映射指定線性地址va到該物理頁。
  4. sys_page_map:拷貝頁表,使指定進程共用當前進程相同的映射關係。本質上是修改特定進程的頁目錄和頁表。
  5. 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方式:非寫時拷貝vs寫時拷貝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()來處理缺頁中斷。在該函數中應該做如下幾件事:

  1. 判斷curenv->env_pgfault_upcall是否設置,如果沒有設置也就沒辦法修複,直接銷毀該進程。
  2. 修改esp,切換到用戶異常棧。
  3. 在棧上壓入一個UTrapframe結構。
  4. 將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這個測試可能會過不了,坑啊~

缺頁處理小結:

  1. 引發缺頁中斷,執行內核函數鏈:trap()->trap_dispatch()->page_fault_handler()
  2. page_fault_handler()切換棧到用戶異常棧,並且壓入UTrapframe結構,然後調用curenv->env_pgfault_upcall(系統調用sys_env_set_pgfault_upcall()設置)處代碼。又重新回到用戶態。
  3. 進入_pgfault_upcall處的代碼執行,調用_pgfault_handler(庫函數set_pgfault_handler()設置)處的代碼,最後返回到缺頁中斷發生時的那條指令重新執行。
    JOS缺頁異常處理邏輯

Implementing Copy-on-Write Fork

到目前已經可以實現用戶級別的寫時拷貝fork函數了。fork流程如下:

  1. 使用set_pgfault_handler()設置缺頁處理函數。
  2. 調用sys_exofork()系統調用,在內核中創建一個Env結構,複製當前用戶環境寄存器狀態,UTOP以下的頁目錄還沒有建立,新創建的進程還不能直接運行。
  3. 拷貝父進程的頁表和頁目錄到子進程。對於可寫的頁,將對應的PTE的PTE_COW位設置為1。
  4. 為子進程設置_pgfault_upcall。
  5. 將子進程狀態設置為ENV_RUNNABLE。

缺頁處理函數pgfault()流程如下:

  1. 如果發現錯誤是因為寫造成的(錯誤碼是FEC_WR)並且該頁的PTE_COW是1,則進行執行第2步,否則直接panic。
  2. 分配一個新的物理頁,並將之前出現錯誤的頁的內容拷貝到新的物理頁,然後重新映射線性地址到新的物理頁。

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中進程間通信的“消息”包含兩部分:

  1. 一個32位的值。
  2. 可選的頁映射關係。

Sending and Receiving Messages

sys_ipc_recv()和sys_ipc_try_send()是這麼協作的:

  1. 當某個進程調用sys_ipc_recv()後,該進程會阻塞(狀態被置為ENV_NOT_RUNNABLE),直到另一個進程向它發送“消息”。當進程調用sys_ipc_recv()傳入dstva參數時,表明當前進程準備接收頁映射。
  2. 進程可以調用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原理可以總結為下圖:
JOS IPC原理

總結

本lab還是圍繞進程這個概念來展開的。主要介紹了四部分:

  1. 支持多處理器。現代處理器一般都是多核的,這樣每個CPU能同時運行不同進程,實現並行。需要用鎖解決多CPU的競爭。 CPU和進程在內核中的數據結構如下圖所示:Env和CpuInfo關係
  2. 實現進程調度演算法。 一種是非搶占式式的,另一種是搶占式的,藉助時鐘中斷實現。
  3. 實現寫時拷貝fork(進程創建)。 原理總結如下:非寫時拷貝vs寫時拷貝fork
  4. 實現進程間通信。原理總結如下:JOS IPC原理

具體代碼在:https://github.com/gatsbyd/mit_6.828_jos

如有錯誤,歡迎指正(*^_^*):
15313676365


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 一、CLR 線程池基礎 一般來說如果電腦的 CPU 利用率沒有 100% ,那麼說明很多進程的部分線程沒有運行。可能在等待 文件/網路/資料庫等設備讀取或者寫入數據,又可能是等待按鍵、滑鼠移動等事件。 執行 I/O 限制的操作時,操作系統通過設備驅動程式通知硬體幹活,而 CPU 處於一種空閑狀態。 ...
  • head 與 tail 就像它的名字一樣的淺顯易懂,它是用來顯示開頭或結尾某個數量的文字區塊,head 用來顯示檔案的開頭至標準輸出中,而 tail 想當然爾就是看檔案的結尾。 一.命令格式: head [參數]... [文件]... 二.命令功能: head 用來顯示檔案的開頭至標準輸出中,預設h ...
  • e2image e2Image程式將位於設備上的ext2、ext3或ext4文件系統元數據保存到由圖像文件指定的文件中。通過對這些程式使用-i選項,image文件可以由dupe2fs和調試器來檢查。這可以幫助專家恢復嚴重損壞的文件系統。 如果image文件是”-“,那麼e2image的輸出將被髮送到 ...
  • rar解壓 ...
  • Linux 提供了許多用於文件搜索的命令,這些命令都很強大,但是也有一些不同之處,這裡分別介紹一下。 一、find 命令 find 是最常見和最強大的一個文件搜索命令。使用 find 命令可以在指定目錄中搜索指定的文件。語法如下: 其中,目錄是 find 命令將要去搜索的目錄,包括該目錄及其子目錄, ...
  • 特殊變數     在Shell中的特殊變數主要分別兩種 位置參數變數 、 狀態變數 兩種。 位置參數變數     Shell中的位置參數變數主要是指\$0、\$1、\$ 等,主要用於從命令行、函數或腳本執行等地方傳遞參數。詳細說明如下所示: \$0 :獲取當前 ...
  • ssh keygen 作用就是驗證主機和用戶公鑰加密 值得註意的是passphrase選項詢問 是對自身密鑰的保護,因為在ssh通信前,密鑰是不受保護的,如果填來的話通常會使用aes256 cbc的對稱加密方法對口令加密,當然也可以不填 支持的非對稱加密演算法 命令具體選項 ...
  • 1. linux優先順序的表示 1.1 優先順序的內核表示 linux優先順序概述 在用戶空間通過nice命令設置進程的靜態優先順序, 這在內部會調用nice系統調用, 進程的nice值在 20~+19之間. 值越低優先順序越高. setpriority系統調用也可以用來設置進程的優先順序. 它不僅能夠修改單個 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...