本文章環境基於 Linux v4.14.259
第一次 trace 整個排程的流程，kernel 真的是個大坑，有很多概念都還不熟，只能整理大概的流程，具體很多 function 的作用都沒辦法很好的說明，希望之後可以多閱讀 source code，把相關的知識慢慢補齊，拼湊成完整的知識。
schedule 要 trace 排程器要先找到 schedule 的入口，定義在 kernel/sched/core.c，函式定義如下
asmlinkage __visible void __sched schedule(void) { struct task_struct *tsk = current; // 避免 deadlock sched_submit_work(tsk); do { // 排程本身無法搶佔，等排程完畢再開啟 preempt_disable(); __schedule(false); // 排程完成，開啟搶佔功能 sched_preempt_enable_no_resched(); } while (need_resched()); // 檢查是不是被設置 TIF_NEED_RESCHED，如果被設置就重新排程 } EXPORT_SYMBOL(schedule); sched_submit_work static inline void sched_submit_work(struct task_struct *tsk) { if (!tsk->state || tsk_is_pi_blocked(tsk)) return; /* * If we are going to sleep and we have plugged IO queued, * make sure to submit it to avoid deadlocks.
本文章環境基於 Linux v4.14.259
因為作業需要在 task_struct 中加入 counter 並且觀察排程器的行為，所以在這邊寫一份筆記來紀錄一下在 linux 中一個 process 建立的時候在哪裡初始化，從 fork() 開始慢慢 trace 下去。
在 Linux 中並沒有明確區分 process 跟 thread, task_struct 可以根據創立條件的不同代表 process 或者 thread。
從實作的角度看可以有以下幾種 system call 建立新的 task_struct:
建立 user process: fork, vfork, clone 建立 kernel thread: kernel_thread, kthread_create 以上這些 API 最後都會呼叫 /kernel/fork.c 中的 _do_fork 來進行 create task_struct 的操作，只是會根據給的參數不同，來決定建立出來的 task_struct 的性質，以上幾個 system call 的差別也可以參考 The difference between fork(), vfork(), exec() and clone()
但是如果看最新幾版的 kernel source code 會發現怎麼樣都沒辦法找到 _do_fork 這個 function 了，仔細找了一下原因，發現在 linux v5.
題目敘述 在小鎮中有 N 個人，其中裡面有一個是 Judge，成為 Judge 要滿足兩個條件
Judge 本身不相信任何人 其他 N-1 個人都相信 Judge 一開始看到這個題目是往圖的方向去思考，後來寫出來的結果不盡理想，最後換個思路直接用一個大小為 N 的 array 來紀錄，如果 A 信任 B 那就 array[B]++, array[A]--，如果 Judge 存在，它就會有 N-1 票，如果在其中支持的任一個人，在支持的過程就會 -1 票，喪失成為法官的條件。
解題紀錄 class Solution { public: int findJudge(int n, vector<vector<int>>& trust) { vector<int> record(n+1, 0); for (int i = 0; i < trust.size(); ++i) { record[trust[i][0]]--; record[trust[i][1]]++; } for (int i = 1; i <= n; ++i) { if (record[i] == n-1) { return i; } } return -1; } };
題目敘述 在一個陣列中找出兩兩相加是 60 的倍數的組合數。
解題紀錄 這個題目如果純粹的硬是把所有的組合都加過一次，一定會 time out，所以基本上要從 O(n) 的作法去嘗試。
假設 x = 57，那相加 3, 63 ... 都可以湊到 60 的倍數，所以我們只要用一個大小 60 的 array 來存 time[i] % 60 的結果就好了，今天 x = 57 的情況我們只要去 array 中查找 array[60 - 57 % 60] = array[3] 就可以獲得在此之前所有曾經出現過可以跟 57 湊成 60 倍數的資料了。
class Solution { public: int numPairsDivisibleBy60(vector<int>& time) { int cnt = 0; int m[60] = {0}; for (int i = 0; i < time.size(); ++i) { cnt += m[time[i]%60 == 0 ?
題目敘述 給一棵二元樹，回傳某個節點與其祖先節點的最大的差(絕對值)。
解題紀錄 DFS 用 DFS 尋訪每個節點，並且順便紀錄到這個節點之前的 max, min value，這樣子最大的差就是 max - min。
class Solution { public: int maxAncestorDiff(TreeNode* root) { return get_max_different(root, root->val, root->val); } int get_max_different(TreeNode *root, int maxv, int minv) { if (!root) return maxv - minv; maxv = max(maxv, root->val); minv = min(minv, root->val); return max(get_max_different(root->left, maxv, minv), get_max_different(root->right, maxv, minv)); } }; #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") static auto _ = [] () {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();
題目敘述 給定一個 perfect binary tree，定義 next 指標，root->next 為空，每個節點的 left child 的 next 為 right child。每個節點 right child 的 next 為該節點 next 的 left child。
用中文有點難表達，直接看圖吧。
解題流程 這題跟很多 tree 的題目一樣，可以用 BFS 或者 DFS 兩種方式去實現。
BFS 用 BFS 的解法，就是在每個 level 找到最左邊的 Node 當作開頭，往右開始每個節點都用 next 指標連結。
class Solution { public: Node* connect(Node* root) { if (!root) return root; queue<Node*> q; q.push(root); while (!q.empty()) { Node *curr; const int qsize = q.size(); for (int i = 0; i < qsize; ++i) { Node *n = q.
