B10532008 黃信恩 HW1
項目一
暫存器eax為 0xaa55
暫存器ecx為 0x0
暫存器edx為 0x80
暫存器ebx為 0x0
stack中最頂端的值(esp)往下分別為
0xf000d242 0x00000000 0x00006f6a 0x00000000 0x0000916e 0x00009135 0x00000000 0x00000000 0x00006c65 0x00007c00 0x00000080 0x000f1ede 0x000f3e37 0x00000000 0x00007c00 0x00000001 0x00000000 0x00000000 0x00000000 0x00000000 0x00800000 0x00000000 0xaa550000 0x7c000000
項目二 零、一章報告
kernel
xv6作業系統使用了傳統的kernel概念，kernel可以提供服務給其他執行中的程式，而每一個執行中的程式被叫做process，包含指令、data和stack。
而process透過system call來使用kernel，整個process就在kernel和user space之間執行。
kernel使用了CPU的硬體保護來確保每個user space中的程式只會使用到自己的memory，當程式呼叫system call的時候，kernel將會執行預定的功能。
shell是user program，他接收用戶的輸入並執行，xv6 shell是一個簡單的Unix shell實作。
process
xv6 process由user-space memory和private的kernel process組成，xv6有time-share特性，他可以在CPU中切換執行的程式，xv6會保存沒有在執行的程式的CPU暫存器。
一個process可以用fork()這個system call來創建他的子process，而子process的memory內容和父process相同，fork指令在父process會返回子process的pid，而子process返回0。
如果呼叫system call exit()會停止程式的執行，並釋放資源，wait()指令會讓父process回到上一個子process，直到有子process進行exit()。
exec這個system-call會從檔案系統中讀取檔案來取代目前的process的memory。
file descriptor and pipe
file descriptor是一個小整數，代表一個process可以讀寫的kernel物件，xv6的kernel利用file descriptor來當作每個process的table，0是標準輸入，1是標準輸出，2是error。
system call read 和 write 是從file descriptor指的位置讀或寫數個bytes，用法為read/write (fd,buf,n)，fd為file descriptor，buf為存取位置，n為n個byte。
system call close會釋放一個file descriptor，使他接下來可以被open,pipe或dup重複使用。
file descriptor和fork的使用讓I/O重新導向能夠簡單實作。
pipe是一個kernel的小buffer，利用成對的file descriptor來讓process可以用一個讀取，另一個寫入，pipe提供了一種processe的互動方式。
file system
xv6的file system提供文件目錄，他是一個樹狀的結構，根節點是一個特別的目錄root，路徑/a/b/c代表c在b中，b在a中，而a在root之中。不以/開始的目錄是相對目錄，是目前process的目錄，可以使用system call chdir來改變。
mknod指令可以創建一個沒有內容的文件，這個的兩個參數使文件包含major和minor device numbers，用來讓kernel辨識一個唯一的kernel device。
fstat指令會接收一個 struct stat，他包含一個文件的 type,dev,ino,nlink,size，使用link指令可以使一個檔案可以有多個名字，但inode是唯一的，system call unlink可以將一個文件名移除，而一個文件的空間只有在nlink和沒有file descriptors refer他時才會被清空。
isolation
如果程式能利用library來使用硬體資源，當然執行效能會很好，但其壞處就是若超過一個程式要執行，其他的程式就必須要停止他們的process，這樣的合作time-sharing機制只有在程式互相信賴且沒有錯誤時才會是理想的，但是現實是很難發生的，所以isolation的方式才是比較合理的方式，若達到strong isolation，也可以避免程式直接使用重要的硬體資源，其方法就是利用作業系統的system call 介面來管理，像在xv6中的檔案管理就是使用open,read等等指令來管理。
很多作業系統使用的是Monolithic kernel，這種方式的作業系統會有完全的硬體掌控能力，而缺是作業系統中各部分的介面可能過於複雜，因此作業系統的開發者可能會犯錯造成kernel出錯，整個電腦就需要重新啟動，為了降低這種風險，OS設計者會最小化在kernel mode中的程式數量，讓大部分的程式在user space中執行，這種方式稱作microkernel，也是xv6所使用的方式。
process是一個在xv6的isolation方式下的單位，他使的每個程式都像有自己的空間和自己的一個CPU，每一個process都有自己的map，當kernel要執行時就會使用這個map來知道真實的address，xv6使用struct proc來記錄process的狀態，其中包含了state表示狀態和pgdir來表示p table。
項目三 第五章 Scheduling 報告
在xv6中的scheduler方法其實就是讓每個process輪流執行，叫做輪轉法(round robin)。
當process數量多於處理器數量時，我們就需要讓每個process認為自己獨佔處理器，然後使用multiplexing的方法來模擬出多個處理器。
context switching
xv6在進行切換兩個user space的process時，會利用system call或interrupt來進入kernel，然後切換到CPU的scheduler，進入新process的kernel，才會再回到user-level的process，流程如下圖：
kernel的切換程式 流程如下
yield->sched->swtch
//process會呼叫yield函數 其中的sched函數再呼叫swtch函數
//而swtch函數如下
void swtch(struct context **old, struct context *new);
swtch的功能是負責保存kernel中的暫存器，並且載入新的process的暫存器值。
scheduling
為了防止多個CPU處理同一個process，xv6會在執行過程中持有著鎖，在scheduling中指的是ptable.lock，在將呼叫swtch函式時，呼叫者必須持有著鎖，才能確保process是正確的被單一執行。
kernel thread只會在sched中放棄處理器，然後回到scheduler的相同位置，而進入處理器也是經由scheduler呼叫sched，不斷循環執行，以下程式碼節錄：
//第2781行
swtch(&(c−>scheduler), p−>context);
//以及2822行
swtch(&p−>context, mycpu()−>scheduler);
這樣在兩個threads中切換的方式又叫做 coroutines。
void
scheduler(void)
{
struct proc *p;
struct cpu *c = mycpu();
c−>proc = 0;
for(;;){
sti();
acquire(&ptable.lock);
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
if(p−>state != RUNNABLE)
continue;
c−>proc = p;
switchuvm(p);
p−>state = RUNNING;
swtch(&(c−>scheduler), p−>context);
switchkvm();
c−>proc = 0;
}
release(&ptable.lock);
}
}
scheduler會不斷的尋找 p->state == RUNNABLE的process，當他找到了這樣的process，他會更改目前執行的c−>proc為找到的process，用switch切換到process的p table，標記他為RUNNING，最後用swtch切換到process中，值得注意的是，scheduler都持有著鎖，因為他將要進行state變化。
scheduler使用到的資料結構如下
struct proc {
uint sz;
pde_t* pgdir; // Page table
char *kstack;
enum procstate state; // state = RUNNABEL or RUNNING or SLEEPING or ZOMBIE
int pid; // Process ID
struct proc *parent; // Parent process
struct trapframe *tf;
struct context *context; // swtch() here to run process
void *chan;
int killed;
struct file *ofile[NOFILE];
struct inode *cwd;
char name[16];
};
struct {
struct spinlock lock; //持有的lock
struct proc proc[NPROC];
} ptable;
struct cpu {
uchar apicid; // Local APIC ID
struct context *scheduler; // swtch() here to enter scheduler
struct taskstate ts;
struct segdesc gdt[NSEGS]; // descriptor table
volatile uint started;
int ncli;
int intena; // 是否可以 interrupts
struct proc *proc; // running process
};
mycpu(); //將回傳apicid
Sleep and wakeup
sleep 和 wakeup是process互動的方法，sleep可以使一個process暫時休眠，等待事件發生，而當這個事件發生時，就利用wakeup把process喚醒。
在CPU執行過程中，CPU受到中斷但是還沒有把process進入sleep，而wakeup就被呼叫，導致process再也收不到這個事件無法被wakeup，這樣的問題被稱作deadlocked，將鎖當作參數傳入sleep能夠有效解決這樣的問題，可以確保不會在sleep前遭到中斷，並且在sleep最後也可以釋放鎖。
以下為xv6的sleep
sleep(void *chan, struct spinlock *lk)
{
struct proc *p = myproc();
if(p == 0)
panic("sleep");
if(lk == 0)
panic("sleep without lk");
if(lk != &ptable.lock){
acquire(&ptable.lock);
release(lk);
}
// Go to sleep.
p−>chan = chan;
p−>state = SLEEPING;
sched();
p−>chan = 0;
if(lk != &ptable.lock){
release(&ptable.lock);
acquire(lk);
}
}
sleep會先確認process存在且sleep持有鎖(lk)，接著還要有ptable.lock，在確保安全之後，sleep就可以先釋放lk，最後使用sched函式就可以完成sleep。
接下來是xv6的wake up
static void
wakeup1(void *chan)
{
struct proc *p;
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
if(p−>state == SLEEPING && p−>chan == chan)
p−>state = RUNNABLE;
}
void
wakeup(void *chan)
{
acquire(&ptable.lock);
wakeup1(chan);
release(&ptable.lock);
}
wakeup先獲得鎖之後，會再呼叫實際運作的wakeup1來喚醒chan上的所有process，透過將對應的chan上所有process的state改成RUNNABLE來讓他們可以再被scheduler來呼叫。
pipe
pipe是其中一個會使用到sleep/wakeup來讀取和寫入的xv6例子，pipe使用的資料結構如下：
//in pipe.c line 12
struct pipe {
struct spinlock lock; //lock
char data[PIPESIZE]; //data
uint nread; // number of bytes read
uint nwrite; // number of bytes written
int writeopen; // write fd is still open
};
假設讀寫 piperead 和 pipewrite分別在兩個CPU上運行，pipewrite先請求獲得pipe的鎖，而piperead也請求獲得管道的鎖，pipewrite會成功執行，而piperead則會停在請求鎖的部分，在pipewrite寫入過程中如果發生寫滿，那他就會呼叫wakeup，讓在sleep的讀取者醒來，而在pipewrite進入sleep時也會釋放pipe的鎖。
piperead現在可以獲得鎖了，然後發現 p->nread != p->nwrite，代表pipe中是有資料的，所以他開始讀取，因為 nwrite == nread + PIPESIZE，現在nread變多了，所以nwrite也跟著可以繼續寫入了，所以piperead會呼叫wakeup，讓寫入者醒來，自己進入sleep並釋放鎖。
pipe利用分開的read和write，充分利用了sleep和wakeup來使的系統更有效率。
wait,exit,kill
在xv6中，一個子process如果要退出，他並不是直接消失，而是會將state變成ZOMBIE，直到父process呼叫wait才能發現子process可以結束了，父process的責任也是去清理子process的空間以及struct proc以便再利用，而如果父process在子process前退出，init process會代替父process來做好其他的清理工作。
wait指令開始會先請求獲得ptable.lock，接下來透過ptable來找是否有退出的子process，如果沒有，就用sleep等待有退出的子process。
exit指令也會先取得ptable.lock，然後wakeup這個process的父process，因為自己在完成動作前仍然有著鎖，所以喚醒父process是安全的，子process在執行exit時就會將大部分的清理工作完成，但是自己的p->kstack p->pgdir是在exit時必須用到的，所以只能在結束後喚醒正在wait的父process來清理。
kill指令讓一個process可以終結其他process，而他的方法就是設置要終結的process的 p->killed，如果這個process正在sleep的狀態就將他喚醒，而當這個process發現自己的p->killed被設置了，就會使用exit指令來終結自己。