# Lab7 Multithreading 紀錄 ## Uthread: switching between threads ### `user/uthread.c`: 1. 定義 `context`: ```C struct context { uint64 ra; uint64 sp; // callee-saved uint64 s0; uint64 s1; uint64 s2; uint64 s3; uint64 s4; uint64 s5; uint64 s6; uint64 s7; uint64 s8; uint64 s9; uint64 s10; uint64 s11; }; ``` 2. 把 `context` 加進 `struct thread` ```C struct thread { char stack[STACK_SIZE]; int state; struct context context; // add context to thread }; ``` 3. 實做 `thread_create()` ```C void thread_create(void (*func)()) { struct thread *t; for (t = all_thread; t < all_thread + MAX_THREAD; t++) { if (t->state == FREE) break; } t->state = RUNNABLE; // YOUR CODE HERE t->context.ra = (uint64) *func; // return 到 func t->context.sp = (uint64) (t->stack + STACK_SIZE - 1); // 記得 stack 是往下長的 } ``` 4. `thread_schedule()` ```C void thread_schedule(void) { struct thread *t, *next_thread; /* Find another runnable thread. */ /* ... */ if (current_thread != next_thread) { /* switch threads? */ next_thread->state = RUNNING; t = current_thread; current_thread = next_thread; /* YOUR CODE HERE * Invoke thread_switch to switch from t to next_thread: * thread_switch(??, ??); */ thread_switch((uint64) &t->context, (uint64) &next_thread->context); // 在這裡 switch! } else next_thread = 0; } ``` 為什麼只需要儲存 callee-saved? 因為在呼叫 `yield()` 之前與之後 compiler 就早就已經處理好 caller-saved 的還原問題了 在 timer interrupt 的時候，OS 會把 caller-saved 和 callee-saved register 都儲存下來了 (`trampoline.S` 在做的事情) callee-saved: * 以 caller 的角度而言 * 不管我呼叫到了多少的 funcfion，這些 register 都不應該會被改變 * 以 callee 的角度而言 * 如果我需要使用 callee-saved regisger，那麼我一定要把值還給 caller 再 return caller-saved: * 以 caller 的角度而言 * 在呼叫別的 function 之前，我一定要自己把 caller-saved register 紀錄下來才行 * 以 callee 的角度而言 * 我可以隨意的使用 caller-saved register，因為我知道 caller 會自己 value 的還原處理好 ### `user/uthread_switch.S`: 這裡直接照抄 `kernel/swtch.S` 就好: ```asm .text /* * save the old thread's registers, * restore the new thread's registers. */ .globl thread_switch thread_switch: /* YOUR CODE HERE */ sd ra, 0(a0) sd sp, 8(a0) sd s0, 16(a0) sd s1, 24(a0) sd s2, 32(a0) sd s3, 40(a0) sd s4, 48(a0) sd s5, 56(a0) sd s6, 64(a0) sd s7, 72(a0) sd s8, 80(a0) sd s9, 88(a0) sd s10, 96(a0) sd s11, 104(a0) ld ra, 0(a1) ld sp, 8(a1) ld s0, 16(a1) ld s1, 24(a1) ld s2, 32(a1) ld s3, 40(a1) ld s4, 48(a1) ld s5, 56(a1) ld s6, 64(a1) ld s7, 72(a1) ld s8, 80(a1) ld s9, 88(a1) ld s10, 96(a1) ld s11, 104(a1) ret /* return to ra */ ``` ## using thread 使用 `table_locks` 解決 ```C struct entry { int key; int value; struct entry *next; }; struct entry *table[NBUCKET]; pthread_mutex_t table_locks[NBUCKET]; int keys[NKEYS]; int nthread = 1; ``` 在 `main()` 中初始化 ```C int main(int argc, char *argv[]) { // ... if (argc < 2) { fprintf(stderr, "Usage: %s nthreads\n", argv[0]); exit(-1); } for (int i = 0; i < NBUCKET; i++) pthread_mutex_init(&table_locks[i], NULL); // ... } ``` 在使用到 `table[i]` 的前後使用 `pthread_mutex_lock()` 以及 `pthread_mutex_unlock()` ```C static void put(int key, int value) { int i = key % NBUCKET; pthread_mutex_lock(&table_locks[i]); // lock!!!!! struct entry *e = 0; for (e = table[i]; e != 0; e = e->next) { if (e->key == key) break; } if(e){ e->value = value; } else { insert(key, value, &table[i], table[i]); } pthread_mutex_unlock(&table_locks[i]); // unlock!!! } ``` ## Barrier 這個 assignment 的目地是要實做出 `barrier()` 可以使用以下兩個 function: ``` pthread_cond_wait(&cond, &mutex); // broadcast 到 cond 時，才會 release mutex pthread_cond_broadcast(&cond); // 去通知那些 wait cond 的 function ``` ### 為什麼 `pthread_cond_wait()` 需要搭配一個 `mutex` ? 以 `barrier()` 為例, 請觀察 `bstate.barrier_mutex`， 有很多 thread 會想要取得 `mutex` 所以在 `wait()` 時先把 `mutex` 還回去(其他 thead 拿的到) 而，從 `wait()` return 回來時必須要重新拿到 `mutex` 才行 因為還有可能會針對 `bstate` 進行修改 ### 資料結構解釋 ```C static int nthread = 1; // 總共有多少個 thread struct barrier { // pthread_cond_wait() 需要有 cond 以及 mutex 作為參數 pthread_mutex_t barrier_mutex; // 必須拿到 mutex 針對 bstate 做動作 pthread_cond_t barrier_cond; int nthread; // 有多少 thread 到達了 barrier int round; // 總共有 20000 回合的 barrier } bstate; // round 用來紀錄現在進行到了第幾回合 ``` `barrier()`: ```C static void barrier() { // YOUR CODE HERE // // Block until all threads have called barrier() and // then increment bstate.round. // pthread_mutex_lock(&bstate.barrier_mutex); bstate.nthread++; if (bstate.nthread < nthread) { pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex); } else { bstate.round++; bstate.nthread = 0; pthread_cond_broadcast(&bstate.barrier_cond); } pthread_mutex_unlock(&bstate.barrier_mutex); } ``` ## 參考資料 * https://pdos.csail.mit.edu/6.S081/2022/schedule.htm://pdos.csail.mit.edu/6.S081/2022/schedule.html * https://pdos.csail.mit.edu/6.S081/2022/labs/thread.html * https://ttzytt.com/2022/08/xv6_lab7_record/