OS_HW1 四資工三柯名鴻 B10515048

eip 0x7c00
eax 0xaa55
ecx 0x0
ebx 0x0

第0章 Operating system interface

Operating system主要是有效的分配電腦的資源給多個program，且提供比硬體更有用的支援。

xv6是用傳統的kernel，每個process都包含了instructions、data、stack，process會透過system call進入kernel，讓kernel執行完再return，所以process會在user space與kernel space之間來回運行。

第1章 Operating system organization

Operating system必須符合multiplexing、isolation、interaction。

xv6用page tables給每個process獨自的address space，page table則負責將virtual address轉換成physical address。為了定義process的address space，由低到高依序放置"instructions"、“global variable”、“stack”、“heap”。

第5章 Scheduling

運作原理

任何一個OS都可能執行超過電腦處理器數目的process，因此需要規畫適當的時間給處理器。

當process等待設備、I/O完成，或等待child process exit或等待"sleep" system call時，xv6的睡眠和喚醒機制會切換。當process執行user instructions時，xv6會周期性地強制切換。這種multiplexes產生了每個進程都有自己的CPU的錯覺，就像xv6使用memory allocator和hardware page tables來創建每個進程都有自己的內存的假像一樣

程式流程

function	position
cli	x86.h
ltr	x86.h
lcr3	x86.h
outb	x86.h
outsl	x86.h
sti	x86.h
stosb	x86.h
stosl	x86.h
swtch	swtch.S
bread	bio.c
brelse	bio.c
bwrite	bio.c
panic	console.c
fileclose	file.c
bfree	fs.c
readsb	fs.c
iput	fs.c
itrunc	fs.c
iupdate	fs.c
iderw	ide.c
idestart	ide.c
idewait	ide.c
kfree	kalloc.c
begin_op	log.c
commit	log.c
end_op	log.c
install_trans	log.c
log_write	log.c
write_head	log.c
write_log	log.c
pipeclose	pipe.c
piperead	pipe.c
pipewrite	pipe.c
exit	proc.c
kill	proc.c
sched	proc.c
scheduler	proc.c
sleep	proc.c
wakeup	proc.c
wakeup1	proc.c
wait	proc.c
acquiresleep	sleeplock.c
releasesleep	sleeplock.c
acquire	spinlock.c
getcallerpcs	spinlock.c
holding	spinlock.c
pushcli	spinlock.c
popcli	spinlock.c
release	spinlock.c
memmove	string.c
memset	string.c
deallocuvm	vm.c
freevm	vm.c
switchkvm	vm.c
switchuvm	vm.c

代碼解釋

Code: Context switching

User-kernel（system call或interrupt）到舊process的kernel thread，然後context switching到local CPU的scheduler thread，接這context switching到process’s kernel thread，最後返回到user-level process。

xv6使用兩個context switching，scheduler在自己的stack上運行，以簡化清理user processes。

Code: Scheduling

process想要讓出CPU必須要獲得process table的鎖 ptable.lock，並釋放其擁有的其他鎖，修改自己的狀態（proc->state），然後call sched，yield和sleep exit都遵循了這個約定。sched檢查了兩次狀態，這裡的狀態說明了，由於process此時持有鎖，所以CPU應該是在中斷關閉的情況下運行的。最後，sched call swtch把當前context保存在proc->context中然後切換到scheduler context即cpu->scheduler中。swtch返回到scheduler的stack中，就像是scheduler的swtch返回了一樣。scheduler繼續其for迴圈，找到一個process來運行，切換到該process，然後繼續輪轉。

Code: Sleep and wakeup

總體思路是希望sleep將當前process轉化為SLEEPING狀態並call sched 以釋放CPU，而wakeup則尋找一個SLEEPING狀態的process並把它標記為RUNNABLE。

Code: Pipes

實際上在xv6中有兩個使用sleep/wakeup來同步讀者寫者的queues。一個在IDE驅動中：進程將未完成的磁片請求加入queues，然後call sleep。中斷處理常式會使用wakeup告訴進程其磁片請求已經完成了。

Code: Wait, exit, and kill

sleep和wakeup可以在很多需要等待一個可檢查狀態的情況中使用。parent process可以call wait 來等待一個child process退出。wait首先要求獲得ptable.lock，然後查看process table中是否有child process，如果找到了child process，並且沒有一個child process已經退出，那麼就call sleep等待其中一個child process退出，然後不斷迴圈。

exit首先要求獲得ptable.lock然後喚醒當前process的parent process。即使parent process已經是RUNNABLE的了，但在exit call sched 以釋放ptable.lock之前，wait是無法運行其中的迴圈的。所以說只有在child process被標記為ZOMBIE之後，wait才可能找到要退出的child process。在退出並重新呼叫之前，exit會把所有child process交給initproc。最後，exit call sched來讓出CPU。

exit讓一個應用程式可以自我終結；kill則讓一個應用程式可以終結其他進程。在實現kill時有些困難，因為被終結的process可能正在另一個CPU上運行，或正在sleep中並持有kernel資源。為了解決了這難題：它在process table中設置被終結的process的p->killed，如果這個process在睡眠中則喚醒之。如果被終結的進程正在另一個CPU上運行，它則會通過system call或interrupt進入kernel。當它離開kernel時，trap會檢查它的p->killed，如果被設置了，該process就會call exit，終結自己。

資料結構

struct	position
context	proc.h
cpu	proc.h
proc	proc.h
pipe	pipe.h












//(2300-2310)
// Per−CPU state
struct cpu {
    uchar apicid;    // Local APIC ID
    struct context *scheduler;    // swtch() here to enter scheduler
    struct taskstate ts;    // Used by x86 to find stack for interrupt
    struct segdesc gdt[NSEGS];    // x86 global descriptor table
    volatile uint started;    // Has the CPU started?
    int ncli;    // Depth of pushcli nesting.
    int intena;    // Were interrupts enabled before pushcli?
    struct proc *proc;    // The process running on this cpu or null
};








//(2326-2332)
struct context {
    uint edi;
    uint esi;
    uint ebx;
    uint ebp;
    uint eip;
};

















//(2336-2351)
// Per−process state
struct proc {
    uint sz;    // Size of process memory (bytes)
    pde_t* pgdir;    // Page table
    char *kstack;    // Bottom of kernel stack for this process
    enum procstate state;    // Process state
    int pid;    // Process ID
    struct proc *parent;    // Parent process
    struct trapframe *tf;    // Trap frame for current syscall
    struct context *context;    // swtch() here to run process
    void *chan;    // If non−zero, sleeping on chan
    int killed;    // If non−zero, have been killed
    struct file *ofile[NOFILE];    // Open files
    struct inode *cwd;    // Current directory
    char name[16];    // Process name (debugging)
};









//(6762-6769)
struct pipe{
    struct spinlock lock;
    char data[PIPESIZE];
    uint nread; // number of bytes read
    uint nwrite; // number of bytes written
    int readopen; // read fd is still open
    int writeopen; // write fd is still open
};

OS_HW1 四資工三 柯名鴻 B10515048