## Schedule

xv6 一個process只有一個thread，所以thread切換時，需要透過interrupt進入kernel，才能完成thread的切換。

也能理解一個process兩個thread，一個thread是在user mode運行，另一個thread是kernel mode，兩者不會同時執行。

**thread 實現的是 concurrancy，多核才能實現 parallelism。**

當計時器達到設定值時，會強制進入中斷，中段位置在trap中的yield()，yield 會呼叫 thread schedule來切換thread ，避免CPU密集型時，其中一個thread不願意將鎖放掉，導致佔據過多時間，這裡又被稱為Pre-emptive schedule 搶占行調度。

自願放出鎖的調度，則稱為vuluntary schedule。

**thread的三個state:**
running : 當前在cpu運行的thread (cpu的寄存器存在cpu當中)
runnable : 沒再cpu運行的thread，且沒在等待i/o。(須將寄存器狀態保存下來)
sleeping : 在等待i/o的thread。

**切換thread流程(context 上下文切換):**
thread的user mode寄存器存在trampframe，接著跳轉到kernel mode 並通過 swich()，將kernel的寄存器存到context()，並呼叫thread scheduler()，而thread scheduler()會將修改上一個thread的狀態變成 runnable 或是 sleeping，並再次調用swich()，通過排序，跳轉到下一個thread的kernel mode **(透過context 儲存的 ra 寄存器 跳到 那個thread 上次透過schedule呼叫 swtch function的地方，ra寄存器執行，swtch function return後繼續運行)**，並通過interrupt 和 trampframe跳轉回 thread的user mode。

每個thread的context存在p->context，**而thread scheduler()的context存在cpu->context裡面。**

context只保存個14寄存器是因為他們是callee寄存器，需要由被調用的函數自行保存，否則會消失，而caller寄存器在函數呼叫時，已經儲存在stack當中了。

切換進程時，須關閉中斷。

創建process時，會用 forkret，來讓每個process保持在 swtch 可以 return 的狀態。

## lab multitthread
**lab 1** 是在user mode 實現一個 thread 的功能。

首先是 int main ()，先出初始化thread， 然後使用func funca funcb 透過create 創建三個thread，在使用schedule開始執行thread。
thread的結構體，context是自己加的，用來保存callee regisiter。

func a 跟 b c 長的差不多，就是print a start，並將starated至1，如果b 和C 還沒置1，就跳轉下一個thread，之後每一個迴圈跳下一個thread。

thread_create()


初始化每個thread的 stack 和 context，context的ra 初始化為每個func，這樣一開始schedule會從func開始執行，stack初始化為stack頂端(上到下)。

最後修改schedule函數即可

thread_switch makefile通過 thread_switch在uthread的text自段從彙編鏈接而來的，

如下所示

**lab2**
第二個實驗就是加鎖，避免不同thread導致race condition，因為hash table 是用linklist 來接下一個 link，可能兩個thread同時對該指標進行操作，導致其中一個指標儲存的key被覆蓋。

**lab3**
類似wakeup，其他thread sleep ，等待最後一個 wakeup。同樣需要加鎖，而pthread_cond_wait，會在睡眠時放開鎖，醒來後會等待鎖。

## Coordination (Sleep and Wake up)

阻塞機制:thread->sleep，就是CPU不會切換到該thread。

非阻塞機制:thread->runable，等待時I/O可以切換該thread，但需要polling i/o是否完成。

sleep是拿來實現阻塞的一種機制。
sleep需要傳遞鎖，會在sleep後釋放，並且在wakeup後重新獲取。

如果鎖不是在sleep內部執行，可能會發生lost wakeup，也就是Sleep之前進中斷，跳轉到wakeup函數，讓sleep函數等不到wake up。

**wake up的實現**
遍歷每個process，**需獲取該process的lock**，直到條件相符，並使thread 的 state變成可執行(需要鎖)。

**sleep的實現**
在釋放傳遞的lock之前，會先獲取當前process的lock，避免當前process還未sleep之前，就已經wakeup，並配合schedule()，實現context。

可以多的sleep共用同一個管道，等待單一process去wake up。

semaphone(信號量)則是用count的方式，而不用獲取鎖。

**process的終止**

xv6有兩種方式終止process，分別是exit 和 kill。

**exit:**
因為precess只能消滅文件系統和狀態等關係，但無法清空自己的stack等訊息，所以通常由父進程消滅，使用exit之後，state會變成zombie，並清除文件系統，此時父進程會使用wait(sleep)，等待子進程的exit的(wakeup)，wait會將狀態為zombie的子進程清除。

exit之後，如果當前process還有子進程，會把子進程的parent掛載到最初的process，由process清理這些子進程，避免出現zombie process。

**kill(溫和的)**
kill則是會等到process安全執行完之後，才會exit。

**note:** 所以linux的kill可以理解成`SIGKILL`會直接執行exit，溫和的`SIGTERM`則會等process執行完才exit。

**note:** 在linux中，要殺死process必需要創建和kill的id一樣，否則沒有權限。

**note:** init process 是無法exit的，否則系統會crash。

**ex:selct epolling poll 差別?**

## lab: locks
**第一個lab**是kalloc() 和 kfree()的修改，因為原先的kalloc()和kfree()只有一組鎖，當其中一個thread使用鎖時，其他CPU是不能使用的，所以需要修改kmem結構體裡的鎖。

kalloc 和 kfree 是將物理記憶體抽象，物理記憶體以頁為單位，每個kfreelist 是以linklist 的方式記錄空白的物理記憶體page。

首先修改kmem結構體，讓每組cpu有各自的 freelist，`NCPU`是CPU最大值。

至於freelist的初始化，我猜在qemu初始化時，就會透過每個CPU去並行分配freelist。

初始化鎖
name 沒初始化也沒關系，只是命名

修改kfree()，push_off() ~ pop_off ，是中斷關閉，如果獲得CPU這組鎖的當下，thread切換，將會導致這組freelist接到別組CPU的freelist，會導致freelist分布不均。

剩下操作就是獲取鎖，然後分配頁表給freelist。

kalloc() 和 kasteal()，當該組cpu的freelist不足時，需要去偷別組CPU的freelist，使用kasteal函數去獲取別組CPU的freelist，剩下操作跟kfree()差不多。

katreal 這裡使用round-robin演算法，也就是往右邊CPU去偷，不能一左一右，會造成deadlock。



**lab: buffer cache**
xv6的cache 鎖只有一個，當不同thread需訪問cache，需要等待鎖，為解決上面問題，修改buffer結構，原本的buffer是用雙向linklist來查找文件對應block是否在cache中，但這樣訪問太慢了，因此優化成hash提高訪問速度。

概念類似這樣:

將原先的cache透過block代號hash分成十三個部分(blocknum%13)，降低鎖等待時間，因為cache有需多共用部分，不能像kalloc一樣每個CPU各一個。

當遇到碰撞情形，因此將每個hash又各連五個buf array。
結構體如下:
extern uint ticks，是用來使用LRU Cache的時間，從trap的硬件中斷而來。

Hash function: 單純的質數除法，質數能設更大，避免碰撞和鎖等待機率。


初始化buffer: 因為不再是雙向linklist，而是單純的array，所以只需要初始化每個hash和底下對應array的lock。

接著是bget函數，通過dev和blockno來獲取資料是否存在cache當中，，以下是有cache的情況，並讓對應鎖進入睡眠，等待文件來使用。

沒有時使用如下，使用LRU算法，將hash[key]中，最長時間沒使用的替換掉，

bread 和 bwrite 就不用修改

brelease 則可以釋放睡眠中的鎖

上面實驗重點在LRU CACHE的設計，通過HASH降低查找時間，並使用ticket來記錄時間，而無需使用雙向linklist。