# Programming Project - Nachos
:::info
先預定周日(5.14)晚上19:00合併和討論第二部分
前三:Verna 後三:Jessica
:::
# Part 1. trace code
## I. New→Ready
1)  userprog/userkernel.cc UserProgKernel::InitializeAllThreads()
execfileNum 是Total threads number, 在 InitializeAllThreads() 中藉由呼叫InitializeOneThread(), 依序初始化 a thread , 總共會有 execfileNum 條threads

2)  userprog/userkernel.cc UserProgKernel:: InitializeOneThread(char*)
Kernel 會幫忙 create a new thread, 首先，給予 threadName 和 threadID 產生一條 new thread 後，再 fork，使 thread 第一次進入到 Running state時 ， 該 thread 的file 可以被載入與執行。


3)  threads/thread.cc Thread::Fork(VoidFunctionPtr, void*) 

Fork(,) 主要是用來讓2個threads(分別是 caller & callee) 以concurrently 的方式運行。
首先，會先配置一個 stack ，對於 stack 做初始化，透過call SWITCH(,) ， 使得callee 可以 run a procedure ，藉此讓他可以與caller 並行，最後再將 thread 放入ready queue 中，等待進入running state。

4)  threads/thread.cc Thread::StackAllocate(VoidFunctionPtr, void*)
StackAllocate(,) 的目的是：配置一塊連續的記憶體空間，讓 thread 可以存放 local variables 。
thread execution stack 中的 first frame 是ThreadRoot，其中藉由這個 ThreadRoot 的starting address 讓我們在呼叫 SWITCH() 時，可以switch 到這個 thread。

5)  threads/scheduler.cc Scheduler::ReadyToRun(Thread*)
ReadyToRun(Thread*) 的用途在於：把 thread 放入 readyList 中，等待被 scheduling 在 CPU 上。
thread會被放到readyList當中，並且thread的status會被設為READY。

## II. Ready→Running
1)  threads/scheduler.cc Scheduler::FindNextToRun()
FindNextToRun() 目的是：找出下一個要執行的 thread 。
起初會確定 kernal 的 interrupt 已被開啟，若有 ready thread 在 readyList 中，則會將該 thread 從 readyList 中移出，接著 return 該 thread ，反之，則 return null 。


2)  threads/scheduler.cc Scheduler::Run(Thread*, bool)
Run(,) 的目的為：把 CPU 分派給剛才被選出來的 next thread ，儲存 oldThread 的狀態，載入 new thread 並且 switch 向他。
變數 oldThread 指向現在正執行的 thread ，當我們將要執行 nextThread 且不再執行這個 oldThread 時（也就是 oldThread finished）， 將他標記為要是刪除的那一個。


3)  threads/switch.s SWITCH(Thread*, Thread*)
SWITCH(Thread*, Thread*) 目的: 先把 %eax (register) 的內容 ''暫存在一個 data section (_eax_save)，然後把 %eax register 先拿來存指向 t1 的位址 (t1 stack 的起始位址)，接著一系列將 cpu registers ( %ebx, %ecx ,..., % )的''內容''存回 t1 的 stack。剩下最後一個位置 (4(%eax)) 還沒存到本來該存的內容(暫存在 _eax_save) 將其存回去

4)  machine/mipssim.cc Machine::Run() 

Run() 用來模擬當程式啟動 ， kernel 呼叫執行 user-level program 在 Nachos 上的情況。
kernel->interrupt->setStatus(UserMode) 將machine的status (有三種狀態 idea, kernel, user ) 設定為user 。


Run() 內的無窮迴圈 for(;;) ，每一回都會呼叫以下 function :
Machine::OneInstruction(Instruction *instr) 用來執行一個來自user-level 的 decoded instruction，若過程中有任何 exception 或 interrupt，就會調用 exception handler，return 回 Run() ，因為 OneInstruction() 在無窮 loop 中，萬一任何 state 改變，我們仍可以再次重新開始執行一個 instruction。
kernel->interrupt->OneTick()：增加 stats->totalTicks , stats->systemTicks 跟 stats->userTicks ，接著確認是否有任何 pending 的 instruction 現在需要被執行了。(以下將於 III. Running→Ready 2) machine/interrupt.cc Interrupt::OneTick() 接續詳述)

## III. Running→Ready
1)  machine/mipssim.cc Machine::Run() 

同上 II. Ready→Running  4)machine/mipssim.cc Machine::Run()
2)  machine/interrupt.cc Interrupt::OneTick()
接續詳述 II. Ready→Running 4)machine/mipssim.cc Machine::Run()

增加 stats->totalTicks , stats->systemTicks 跟 stats->userTicks ，接著確認是否有任何 pending 的 instruction 現在需要被執行了，


首先將 interrupts disable，然後到 machine/interrupt.cc 的 CheckIfDue() 看:

有沒有任何 interrupts 要執行了。傳入的參數 advanceClock: 若為 true ，代表ready queue 為空，跳到下一個pending interrupt 發生的時間點。判斷最新要執行的 Interrupt event 的 when 有無 > totalTicks，若大於，且判斷 advanceClock 為 false，則 return 回 false ，不做任何事 ; 若 when 小於等於 totalTicks，則要執行這個 interrupt ，所以將此 interrupt 從 list 中取出，呼叫 next->callOnInterrupt->CallBack() 來呼叫 interrupt handler。

回到 OneTick() ，if (yieldOnReturn) 判斷是否要context switch，若為 true ，則讓現在的 thread 做 Yield() 操作。

3)  threads/thread.cc Thread::Yield() 

Yield() 功用為：讓其他正在 run 的 thread 放棄 CPU，並且將該 thread 放到 ready list，之後便可以再次被 scheduled。
過程為，先將原本的 thread 在被 SWITCH之前，先執行R eadyToRun(this)，也就是放到scheduler後，再把 next thread (接著要執行的 thread) 轉變為 running state，隨後 context switch。

4)  threads/scheduler.cc Scheduler::FindNextToRun() 

FindNextToRun() 目的為：return 下一個被scheduled 到 CPU 的 thread。
若 readyList 是空的，就會 return null。 （同上II. Ready→Running 1)  threads/scheduler.cc Scheduler::FindNextToRun() ）

5)  threads/scheduler.cc Scheduler::ReadyToRun(Thread*)
ReadyToRun(Thread*) 目的是：標記一個 thread 是 ready 的狀態，將它放入 readyList 中，等待被 scheduled 到 CPU 上執行。
需要確認 interrupt 已經 disable ，然後把被傳進來的 thread （被 switch out的）的 status 設回 READY，放回 readyList 的尾端

6)  threads/scheduler.cc Scheduler::Run(Thread*, bool) 
回到Yield() 中呼叫的 kernel -> scheduler -> Run(nextThread, FALSE);
bool finishing ＝FALSE 表示原本的 thread 還沒結束，不刪掉， 若原本的 thread 是一個 user program (其 addrspace 不是 null)要將其原本的 userspace 狀態存起來(存進 user registers)，檢查 oldthread 的 stack 有沒有 overflow，將 kernel->currentThread 設為 nextThread，nextthread 的 status 設成 Running，下一步，呼叫 assembly code SWITCH(oldThread, nextThread) ;
CheckToBeDestroyed() : 確認並且刪除前一個run的thread 是否已經結束，需要刪掉。最後，如果 oldthread 有address space ，則 restore 他的content 。

## IV.Running→Waiting
1. userprog/exception.cc ExceptionHandler(ExceptionType) case SC_PrintInt
在syscal.h定義各system call的編碼，其中
#define SC_PrintInt 11
若system call進入exception所表示的編碼為11，則執行case SC_PrintInt。
2. userprog/synchconsole.cc SynchConsoleOutput::PutInt()
synchconsole.h為解決同步問題的函式，SynchConsoleOutput::PutInt(int value)則是輸出同步結果。
當要使用被lock的thread時(lock->Acquire())，會增加PutChar(str[index])的index值，輸出字串後， lock->Release()，即會釋放該thread 。
3. machine/console.cc ConsoleOutput::PutChar(char)
synchConsoleOut->PutChar()會呼叫ConsoleOutput::PutChar(char ch)執行將char寫入到output，安排未來可能會發生的中斷。
4. threads/synch.cc Semaphore::P()
解決threads的同步問題。號誌的value>0則value遞減，檢查value值和遞減不可中斷。當value==0時，行程會被擋住，thread無法執行。
5. threads/synchlist.cc SynchList<T>::Append(T)
增加一個”項目”到清單的末端。喚醒隨意一個等待被追加的元素。用Acquire()把lock的使用權給現在的thread，再把傳來的item放在list的最後，再用Signal()把等待中的thread叫醒，最後將lock釋放。
6. threads/thread.cc Thread::Sleep(bool)
將會放掉CPU。當前thread的行程完成或在等待同步變數，弱是因為等待同步變數，一些其他thread將會喚醒此thread，使它重新回到ready queue中，即可被重新調用。
7. threads/scheduler.cc Scheduler::FindNextToRun()
從ready queue中選擇一個thread被執行。若ready queue為空，則return null。
8. threads/scheduler.cc Scheduler::Run(Thread*, bool)
thread尚未執行完成時要切換到另一個thread執行，需要保存原本thread當下狀態，並載入下一個要執行的thread狀態。
## V. Waiting→Ready
1. threads/synch.cc Semaphore::V()
用以增加信號值，執行V()，訊號標S的值會被增加。結束離開臨界區段的行程，將會執行V()。當訊號標S不為負值時，先前被擋住的其他行程，將可獲准進入臨界區段。
2. threads/scheduler.cc Scheduler::ReadyToRun(Thread*)
用於初始化程序，將不在running state的thread標記為ready並放入ready queue中，以便調度到CPU上。
## VI. Running→Terminated (Note: start from the Exit system call is called)
1. userprog/exception.cc ExceptionHandler(ExceptionType) case SC_Exit
ExceptionHandler用以定義並處理Exception。用以定義並處理Exception。SC_Exit將會強制應用程序退出。
2. threads/thread.cc Thread::Finish()
thread已經執行完畢，當forked程序結束時被呼叫，呼叫Sleep()使thread 變為blocked狀態。
3. threads/thread.cc Thread::Sleep(bool)
為一個布林函式。用以放開CPU的控制，但thread現在是blocked。除非它被明確地放回ready queue不然不會再次執行。
4. threads/scheduler.cc Scheduler::FindNextToRun()
從ready queue中選擇一個thread被執行。若ready queue為空，則return null。
由於程式已經要進入結束，將不會有下一個被選擇執行的thread。
5. threads/scheduler.cc Scheduler::Run(Thread*, bool)
將CPU交給下一個要切換的thread，並保存目前thread狀態。
若舊thread的程序已完成，則刪除。