Golang 並行（concurrent）開發 共享資源訪問控制 Mutex 結構 1 2 3 4 type Mutex struct{ state int32 sema uint32 } state紀錄Mutex的四種狀態：主要兩個為Locked:表示是否被鎖定、Waiter:表示blocked中且等待拿鎖的goroutine數量
Method Lock()：加鎖 Unlock()：解鎖
加鎖過程：
去判斷Locked值是否為0，若是0，把Locked set為1，代表拿到鎖 若是1，Waiter的值+1，並且此goroutine blocked 直到 Locked == 0才會被喚醒 解鎖過程：
若沒有其他goroutine blocked，只要把Locked set 為 0，不需要釋放 semaphore 若有其他blocked goroutine，首先先把Locked set 為 0，然後查看到Waiter>0，釋放一個 semaphore，喚醒一個blocked goroutine，被喚醒的goroutine把Locked set 為1 自旋 lock時，如果Locked為1，嘗試lock的goroutine不是馬上進入blocked，而是會持續地(時間很短)探測Locked是否為0，好處是可以避免goroutine的切換
相當於CPU的PAUSE指令，過程中會持續探測Locked（與sleep不同的是不需要將goroutine轉成睡眠狀態） 自旋要滿足 自旋次數夠小，通常設定為4 CPU核心數>1 scheduler 的可運行queue必須為空 也就是CPU不忙的時候啟用自旋
問題： 如果自旋過程中獲得鎖，避免了goroutine切換，那之前被blocked的goroutine很難獲得鎖，造成starving 因此新版的go新增了Mutex – starving欄位
Golang 平行(parallel) 簡介 平行(parallel)與並行(concurrent) 在執行一些需要快速計算的程式時，我們希望盡量使用CPU的多核心特性來將task平行（parallel）化，因此要分解計算任務到多個goroutine中平行運行，再合併各goroutine結果到最終result
並行(concurrent) 是一種程式架構的概念，將程式拆開成多個可以獨立運行的任務，concurrent可能會用到parallel。也就是說，concurrent可以讓很多事情一起做，但是“不一定”要真的在同一個“時間點”做。
Parallelism 注重規劃，將能夠concurrent的程式，分配給不同硬體單元，使其同時執行。 —> 多核心使用
goroutine 多核 在平時直接使用 go func()創建goroutine，並使用top指令觀察，你會發現跟C語言中thread不同的是，go語言只會在某一個核心中呈現busy狀態。
更新：目前新版的go語言的goroutine不需要設置runtime.GOMAXPROCS()會自動幫你判斷能用的核心數 因此在go語言中需要使用runtime.GOMAXPROCS(cpus)來開啟多核心模式，cpus不能超過原本電腦的核心數 在go語言中可以利用runtime.NumCPU()獲取你電腦CPU的核心數
範例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 func sum(seq int, ch chan int) { defer close(ch) sum := 0 for i := 1; i <= 10000000; i++ { sum += i } fmt.
Link List 基本概念 相同結構的東西（用struct)使用指標（pointer)串起來，相同結構的東西稱作NODE 在加入/刪除比array上好操作 有需要的時候才動態的配置空間(malloc / new) 查詢時比array慢 圖示：
靜態配置：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include<stdio.h>#include<stdlib.h> struct node{ int data; struct node *next; }; typedef struct node Node; int main() { Node x, y, z; Node *ptr = &x; x.data = 10; x.
Process Termination _exit() and exit() 有兩種方式可以終止程式：
abnormal - 由訊號觸發，預設是終止程式（可以core dump) normally - 使用_exit()終止程式 1 2 #include<unisted.h>void _exit(int status); status:定義終止狀態，在parent process可以呼叫wait()以取得狀態 結束狀態為 0 ，表示process順利結束。非0表示異常終止 非0狀態沒有固定規則，每個應用程式有自己的規則要參考他們的文件 普遍為SUSv3制訂的：EXIT_SUCCESS(0) EXIT_FAILURE(1) 程式通常不會直接呼叫_exit()，因為會直接終止，通常會呼叫exit()，因為可以在真正呼叫_exit()前執行一些動作
1 2 #include<stdlib.h>void exit(int status); 會進行以下動作：
以反向註冊順序，呼叫exit處理常式 flush stdio的串流緩衝區 使用status 提供的值執行_exit() system call 與在main() 中return 終止程式或執行到main()結尾終止的方式，return n; 等同於 exit(n)
不等價的時候：若在exit的過程中有任何步驟存取main()的區域函數時，從main return會產生不可預期的行為。例如在呼叫setvbuf() 或 setbuf()時使用main()的區域函數時就會發生不等價的情況 行程終止的動作 關閉open file descriptor、directory stream、message catalog descriptor、conversion descriptor 關閉open file descriptor 後，會釋放此形成所有的file lock 解除任何加載的System V共享記憶體段，並將每個區段對應的shm_nattchcounter減去1 解除行程使用mmap()建立的記憶體映射 Exit Handler 在行程終止前執行一些操作，以應用程式的函式庫來說，行程終止前需要清理在生命週期間有用到的函式庫，因此需要exit handler來保證在終止前（結束時）會清理
整數二分 何時使用 有單調性（monotone)的一組數字可以二分，但沒有單調性也可以使用二分法
在何時適用 若可以找到某種性質，在右半邊滿足，左半邊不滿足(在右半邊不滿足，左半邊滿足)，就可以尋找邊界
模板code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 bool check(int x){/*stasify some conditions*/} // [l, r] -> [l, mid] + [mid + 1, r] int bsearch1(int l, int r) { int mid = l + r >> 1; if(check(mid)) r = mid; else l = mid + 1; } // [l, r] -> [l, mid - 1] + [mid, r] int bsearch2(int l, int r) { int mid = l + r + 1 >> 1; if(check(mid)) l = mid; else r = mid - 1; } return l; //also can return r 圖例與解釋 找尋紅色的邊界：check(mid) ：滿足紅色條件
KMP 基本概念 一種用來字符串匹配的算法 一些定義：
s[] 為主字串 ， p[] 是匹配串 ， 即可以理解成p是否是s的子字串 前綴：包含首位字符但不包含末位字符的子字串; 後綴：包含末位字符但不包含首位字符的子字串 部分匹配值 ： 前綴與後綴最長共有長度 next[] 存的是每個下標對應的部分匹配值 核心思考：每次匹配失敗時，把p串往後移動至next對應的值 next的含義與模擬 字串從1開始存，next[i], 是p[1,i]中前綴和後綴相同的最大長度（部分匹配值）， 定義 next[1] = 0 例如：
1 2 3 idx 1 2 3 4 5 6 str a b c a b a next 0 0 0 1 2 1 求next陣列的code
1 2 3 4 5 6 7 // m 為 p 的長度 for(int i = 2, j = 0; i <= m; i++) { while(j && p[i] !
