# XV6 A simple, Unix-like Teaching Operating System Chapter 1

---

> [TOC]

---

## Chapter 1 Operating system organization

---

### Kernel organization

讀取資料必須透過 kernel

---

### Process overview


---

- Process是一個抽象的概念，他是 Unix 中的一個隔離單元，即 Process 互相為個體。可以一個 Process 有自己的抽象機器，代表在 Virtual Memory 裡。一個 Process 看上去是一個私有的，其他 Process 無法對他 R/W ，也因為一顆 CPU 同時只能執行一個 Process 的關係讓此 CPU 看上去僅執行此 Process 而已。
- 依照上圖，由於先前說過把 Process 視為一個機器，所以他有分 Kernel 和User。
- 每個 Process 都有自己的 Page Table

---

:::info
[reference][http://fred-zone.blogspot.tw/2011/12/linux-kernel-process.html]

- Process
- Process is a program in execution.
=> 程式執行檔的 binary code + 記錄資料的記憶體

- Process 分成內外兩個角度來探討：
1. 從 Process 內部，程式執行的觀點
2. 從 Process 外部，也就是作業系統的觀點

- 程式執行的觀點：
- Process 就是一般的程式碼被放到記憶體執行。一支程式擁有著數個 segments（區段），並仰賴著這些 segment 來持續運作。大致上來說，每個 segment 有不同的用途：
- Code Segment - 存放主要程式
- Data Segment - 存放已被初始化並賦予值的全域變數
- BSS Segment - 紀錄尚未被賦予值的全域變數
- Stack Segment(Stack/Heap) - 紀錄 Process 在執行時動態註冊的變數包括 function 中的 local variable

- 作業系統的觀點
- 作業系統有記憶體管理機制，其建立虛擬記憶體空間，將程式對映進去該空間後，開始執行。作業系統管理著 Process 所擁有的 Segments，為每個 Segment 都配置了『虛擬記憶體區域(VMA, Virtual Memory Area)』。
:::

---

:::warning
- 使用虛擬記憶體之優點
1. 程式不再受到實際記憶體可用空間限制，記憶體可用空間變大。
2. 有更多程式能同時運用記憶體，增加了CPU 使用率。
3. 載入程式或置換程式所須 I/O 次數減少，速度加快。
:::

---

## 20170712 Meeting
- 之後先報
- Open RISK 1200
- WISHBONE
- 再回來報 XV-6

---

### Process Code

- Code: The First Address Space
- 說明 xv6 如何為 Kernel 製造第一個 Process
1. 開機
2. 初始化自己
3. 從硬碟讀取 Boot Loader 到記憶體並執行(Appendix B 有說明細節)
4. Boot Loader 會把 xv6 Kernel 讀到 **實體記憶體** 0x100000。
:::warning
此時 Page Hardware 不啟用，因此 Kernel 不算完全啟動，同時記憶體位置是直接映射到實體位址的。
:::
5. 為了允許內核的其餘部分運行，設置一個 Page Table，將從 0x80000000 開始的虛擬地址（稱為 KERNBASE） 映射到從 0x0 開始的物理地址。設置兩個虛擬地址映射到相同物理內存是 Page Table 的常用的用法。
6. Enabled Paging Hardware
7. 讓 Kernel 在高位址上面跑
1. 將 %esp 指向高位址的 Stack 記憶體
2. Jump 位於高位址的 Main

---

- Code: Creating The First Process
1. 調用 Userinit 建立第一個 Process (只有第一個會調用)

    // Set up first user process.
    void
    userinit(void)
    {
        struct proc *p;
        extern uchar _binary_initcode_start[], _binary_initcode_size[];

        p = allocproc();
        initproc = p;

        // Initialize memory from initcode.S
        p->sz = PAGE;
        p->mem = kalloc(p->sz);
        memmove(p->mem, _binary_initcode_start, (int)_binary_initcode_size);

        memset(p->tf, 0, sizeof(*p->tf));
        p->tf->cs = (SEG_UCODE << 3) | DPL_USER;
        p->tf->ds = (SEG_UDATA << 3) | DPL_USER;
        p->tf->es = p->tf->ds;
        p->tf->ss = p->tf->ds;
        p->tf->eflags = FL_IF;
        p->tf->esp = p->sz;
        p->tf->eip = 0;  // beginning of initcode.S

        safestrcpy(p->name, "initcode", sizeof(p->name));
        p->cwd = namei("/");

        p->state = RUNNABLE;
    }

2. Userinit 調用 Allocproc (每個都會掉用)
3. Allocproc 在 Process Table 中分配一個 Slot (Struct Proc) 並初始化 Process 與 Kernel Thread 有關的
4. Allocproc 掃描 Proc Table 找到 p->state 是 **UNUSED** 並把它標記為 **EMBRYO** 且給他一個 Pid 代表有人用
5. Allocproc 嘗試請求分配一個 Kernel Stack ，若失敗則把前面 p->state 復原 **UNUSED**

    // File:proc.c
    // Look in the process table for an UNUSED proc.
    // If found, change state to EMBRYO and return it.
    // Otherwise return 0.
    static struct proc*
    allocproc(void)
    {
        struct proc *p;

        acquire(&ptable.lock);
        for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
            if(p->state == UNUSED){
                p->state = EMBRYO;
                p->pid = nextpid++;
                goto found;
            }
        }
        release(&ptable.lock);
        return 0;

        found:
        release(&ptable.lock);

        // Allocate kernel stack if necessary.
        if((p->kstack = kalloc(KSTACKSIZE)) == 0){
            p->state = UNUSED;
            return 0;
        }
        p->tf = (struct trapframe*)(p->kstack + KSTACKSIZE) - 1;

        // Set up new context to start executing at forkret (see below).
        p->context = (struct context *)p->tf - 1;
        memset(p->context, 0, sizeof(*p->context));
        p->context->eip = (uint)forkret;
        return p;
    }

    // File:proc.c
    // A fork child's very first scheduling by scheduler()
    // will swtch here.  "Return" to user space.
    void
    forkret(void)
    {
        // Still holding ptable.lock from scheduler.
        release(&ptable.lock);

        // Jump into assembly, never to return.
        forkret1(cp->tf);
    }


---

- Code: Running The First Process
- 在 Call "Userinit" , "Mpmain" 之後，為了讓他跑起來要去呼叫 "Scheduler"。
1. 利用指令啟動此 Processor 的 Interrupts
2. 利用 For Loop 尋找即將起動的 Process
( 這時因為只有一個 Process 所以只會找到剛剛新建的那個 )
3. 利用 Switchuvm 告訴硬件開始使用目標 Process 的 Page Table
4. 將 Process p->state 改成 RUNNABLE
5. 呼叫 "Swtch" 做 Context Switch

- 主程式

        // File:proc.c
        // PAGEBREAK: 42
        // Per-CPU process scheduler.
        // Each CPU calls scheduler() after setting itself up.
        // Scheduler never returns.  It loops, doing:
        //  - choose a process to run
        //  - swtch to start running that process
        //  - eventually that process transfers control
        //      via swtch back to the scheduler.
        void
        scheduler(void)
        {
            struct proc *p;

            for(;;){
                // Enable interrupts on this processor, in lieu of saving intena.
                sti();

                // Loop over process table looking for process to run.
                acquire(&ptable.lock);
                for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
                    if(p->state != RUNNABLE)
                        continue;

                    // Switch to chosen process.  It is the process's job
                    // to release ptable.lock and then reacquire it
                    // before jumping back to us.
                    cp = p;
                    usegment();
                    p->state = RUNNING;
                    swtch(&c->context, &p->context);

                    // Process is done running for now.
                    // It should have changed its p->state before coming back.
                    cp = 0;
                    usegment();
                }
                release(&ptable.lock);

            }
        }

- Usegment()

        // File:proc.c
        // Set up CPU's segment descriptors and task state for the current process.
        // If cp==0, set up for "idle" state for when scheduler() is running.
        void
        usegment(void)
        {
            pushcli();
            c->ts.ss0 = SEG_KDATA << 3;
            if(cp)
                c->ts.esp0 = (uint)(cp->kstack + KSTACKSIZE);
            else
                c->ts.esp0 = 0xffffffff;

            if(cp){
                c->gdt[SEG_UCODE] = SEG(STA_X|STA_R, (uint)cp->mem, cp->sz-1, DPL_USER);
                c->gdt[SEG_UDATA] = SEG(STA_W, (uint)cp->mem, cp->sz-1, DPL_USER);
            } else {
                c->gdt[SEG_UCODE] = SEG_NULL;
                c->gdt[SEG_UDATA] = SEG_NULL;
            }
            c->gdt[SEG_TSS] = SEG16(STS_T32A, (uint)&c->ts, sizeof(c->ts)-1, 0);
            c->gdt[SEG_TSS].s = 0;

            lgdt(c->gdt, sizeof(c->gdt));
            ltr(SEG_TSS << 3);
            popcli();
        }

- Swtch()

        # File:swtch.S
        #   void swtch(struct context **old, struct context **new);
        #  
        # Save current register context in old
        # and then load register context from new.

        .globl swtch
        swtch:
          movl 4(%esp), %eax
          movl 8(%esp), %edx

          # Save old callee-save registers
          pushl %ebp
          pushl %ebx
          pushl %esi
          pushl %edi

          # Switch stacks
          movl %esp, (%eax)
          movl (%edx), %esp

          # Load new callee-save registers
          popl %edi
          popl %esi
          popl %ebx
          popl %ebp
          ret

---

- The first system call: exec
- 第二章後面

---

### Real world
- 大多數操作系統都採用 Process 概念，大多數 Process 看起來與 xv6 相似。 一個真正的操作系統將會找到具有明確的 Free Proc 結構還有 Free List，而不是在 allocproc 中的線性時間搜索; 為了簡單起見，xv6使用線性掃描（許多的第一個）。
- xv6 的地址空間佈局存在不能使用超過 2GB 物理 RAM 的缺陷。 可以解決這個問題，但最好的方案是切換到64位地址的機器。