contributed by < yanjiew1 > 作業說明 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64

contributed by < yanjiew1 > 測驗1 mpool 為 memory pool 實作。 pool_init 是用來初始化 mpool 系統，透過它告訴 mpool 使用哪塊空間作為 memory pool 使用 ，空間大小有多少。 mpool 實作了類似 C 語言標準函式庫提供的記憶體配置器函式，分別為 pool_malloc 、 pool_calloc 、 pool_realloc 、 pool_free 。功能與 C 語言的記憶體置器很像，差別在於 mpool 是從一個設定好的一塊 memory pool 來配置空間。 程式碼運作原理

contributed by <yanjiew1> 想問老師的問題 :::info Fence 和 Barrier 的不同？ ::: :::info Userspace RCU 實作有 rcu-qsbr 、 rcu-signal 和 rcu-generic 。想詢問 Linux Kernel 比較接近哪一種實作方式？ :::

contributed by < yanjiew1 > 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual

contributed by < yanjiew1 > GitHub 題目連結 實驗環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu

contributed by < yanjiew1 > GitHub 開發與實驗環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64

contributed by < yanjiew1 > 實驗環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual

contributed by < yanjiew1 > GitHub 名詞定義 Runs：為在 Mergesort 和 Timsort 中已經排序好的子序列。 Natural Run： Natural Run 就是在未排序的序列中，裡面已經排序好的子序列。例如： [10, 20, 30, 25, 27, 31, 34] ，就可以形成 2 個 Natural Runs ：[10, 20, 30] 和 [25, 27, 31, 34] 。 合併樹：把 Timsort 和 Mergesort 合併的行為表示成一棵二元樹。此二元樹的葉節點，在 Mergesort 為個別元素，而在 Timsort 為 Natural Runs 。而內部節點代表其二個子節點的合併產生的 Run。 比較次數估算： 把所有合併樹中的內部節點代表之 Run 元素個數加總，即可估算比較次數。

contributed by <yanjiew1> 我打算做的貢獻 就在閱讀 list_sort.c 的原始碼過程中，發現 list_sort.c 內的 merge ，搭配你所不知道的 C 語言: linked list 和非連續記憶體的技巧，透過 indirect pointer 的方式減少 if 敘述，故很快的就就做了相關的修改，如下： diff --git a/lib/list_sort.c b/lib/list_sort.c index 0fb59e92ca2d..9d12e50088ab 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -16,28 +16,15 @@ __attribute__((nonnull(2,3,4)))

contributed by < yanjiew1 > GitHub 實驗環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64

contributed by < yanjiew1 > GitHub 連結: https://github.com/yanjiew1/linux23q1-quiz1 開發與實驗環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64

這篇文章是繼閱讀 Linux 核心的紅黑樹後，想補完這篇文章的不足並嘗試用 C 來實作紅黑樹。寫完後會貢獻回原本的文章。 在 Linux 核心的紅黑樹介紹了左傾紅黑樹，但是 Eddie Kohler 教授卻提出左傾紅黑樹是不好的，故在撰寫這篇文章時，會針對傳統紅黑樹和左傾紅黑樹建構測試程式，並且包含 top-down 和 bottom-up 的方式均實測，來看看效能如何。 紅黑樹簡介 紅黑樹是一種能自己保持平衡的二元搜尋樹。其需保持以下特性： 每一個節點不是紅色就是黑色 從根節點到每一個終端節點 (leaf) 的路徑上，所經過的黑色節點數一樣多 紅色節點的子點必為黑色節點

contributed by < yanjiew1 > 作業說明 實驗環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64