Try   HackMD

2024q1 Homework1 (lab0)

contributed by < Lccgth >

修正 GitHub 超連結

Reviewed by lintin528

在 list_sort 、 timsort 、 q_sort 的比較中，除了執行時間上的不同可以嘗試使用 perf 來分析 cache 的使用狀況，觀察各個演算法的特性。

開發環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0

$ lscpu
Architecture:                       x86_64
CPU op-mode(s):                     32-bit, 64-bit
Byte Order:                         Little Endian
Address sizes:                      39 bits physical, 48 bits virtual
CPU(s):                             8
On-line CPU(s) list:                0-7
Thread(s) per core:                 1
Core(s) per socket:                 8
Socket(s):                          1
NUMA node(s):                       1
Vendor ID:                          GenuineIntel
CPU family:                         6
Model:                              158
Model name:                         Intel(R) Core(TM) i7-9700KF CPU @ 3.60GH
                                    z
Stepping:                           13
CPU MHz:                            3600.000
CPU max MHz:                        4900.0000
CPU min MHz:                        800.0000
BogoMIPS:                           7200.00
L1d cache:                          256 KiB
L1i cache:                          256 KiB
L2 cache:                           2 MiB
L3 cache:                           12 MiB
NUMA node0 CPU(s):                  0-7

實作佇列操作的程式碼

#include "list.h"

file 的翻譯是「檔案」，而非「文件」(document)

好的，已修正！

我注意到 queue.c 文件 檔案原先未包含 list.h 標頭檔，而 struct list_head 的宣告位於 list.h 中。為了解決這一問題，我在 queue.c 檔案開頭添加包含 list.h 的指令 敘述 (statement)。

q_new()

commit 3b96677

建立一個空的佇列，並且如果記憶體配置失敗就返回 NULL。

先配置記憶體空間給head，並檢查是否成功配置，接著使用函式 INIT_LIST_HEAD()將 head->next 和 head->prev 都指向 head。

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
    return NULL;

INIT_LIST_HEAD(head);

將「目標」和「實作」手法置於本段落前方。

好的，已修正！

q_free()

commit f3a5ab7, commit 33e05ca

釋放所有佇列使用到的記憶體空間。

先檢查佇列（head）是否存在，接著逐一走訪佇列中的節點，紀錄每個節點的 entry，再從佇列中移除此節點、釋放entry。

list_for_each_safe (cur, temp, head) {
    element_t *entry = list_entry(cur, element_t, list);
    list_del(cur);
-   free(entry->value);
-   free(entry);
+   q_release_element(entry);
}
free(head);

q_insert_head()

commit f4608c6

在佇列的開頭處插入一個節點。

先檢查佇列（head）是否存在，和輸入的s字串是否有效。然後為新節點配置記憶體空間，並驗證配置是否成功。接著為字串配置記憶體並進行複製。如果配置失敗，則釋放已配置的節點記憶體。最後將新節點插入到佇列的開頭處。

element_t *element = malloc(sizeof(element_t));
if (!element)
    return false;

element->value = strdup(s);
if (!element->value) {
    free(element);
    return false;
}

list_add(&element->list, head);

q_insert_tail()

commit 7efac73

在佇列的尾部插入一個節點。

與q_insert_head()大致相同，只須將list_add()替換成list_add_tail()。

- list_add(&element->list, head);
+ list_add_tail(&element->list, head);

q_remove_head()

commit 6229a62

移除佇列開頭處的節點。

先檢查佇列（head）是否存在，和是否為空，接著將字串複製到sp中，最後將節點移除

if (sp) {
    strncpy(sp, entry->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
}

list_del_init(&entry->list);

q_remove_tail()

commit cc82605

移除佇列尾部的節點。

與 q_insert_head() 大致相同，只須將list_first_entry()替換成 list_last_entry()。

- element_t *entry = list_first_entry(head, element_t, list);
+ element_t *entry = list_last_entry(head, element_t, list);

q_size()

commit 88d6c73

計算佇列的大小。

先處理head為空的情況，接著逐一走訪每個節點，由此計算佇列的大小。

list_for_each (li, head)
    len++;

q_delete_mid()

commit 39e784f

刪除佇列裡中間的節點。

先檢查佇列（head）是否存在，和是否為空，接著使用快慢指標找到佇列中間的節點，最後將其刪除

while (fast->next != head && fast->next->next != head) {
    slow = slow->next; 
    fast = fast->next->next; 
}

element_t *entry = list_entry(slow, element_t, list);
list_del(slow);
q_release_element(entry);

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」

了解，已進行修改！

q_delete_dup()

commit b215517

刪除佇列中有重複字串的節點。

逐一走訪每個節點，若目前節點和下一個節點的字串相同，則刪除目前節點，如果不相同的話，利用 dup 標籤檢查此節點的字串有沒有出現過，是否要進行刪除。

list_for_each_safe (node, safe, head) {
    if (safe != head && !strcmp(node_entry->value, safe_entry->value)) {
        dup = true;
        list_del(node);
        q_release_element(node_entry);
    } else if (dup) {
        dup = false;
        list_del(node);
        q_release_element(node_entry);
    }
}

TODO: 撰寫出更精簡的程式碼。

q_swap()

commit 8226559, commit f4c7aab

將每兩個相鄰節點交換。

先檢查佇列（head）是否存在，和是否為空，接著逐一走訪每兩個節點，每進行一組交換就要調整六個指標，分別是 cur->prev 的 next、 cur 與 cur->next 的 prev 和 next、cur->next->next 的 prev。

使用 list_move() 將 cur 移到 cur->next 後方，一樣可達成目標，且程式碼更加精簡。

while (cur != head && cur->next != head) {
-   cur->next = temp->next;
-   temp->next->prev = cur;
-   temp->prev = cur->prev;
-   temp->next = cur;
-   cur->prev->next = temp;
-   cur->prev = temp;
+   list_move(cur, temp);
    cur = cur->next;
}

q_reverse()

commit 4e53342, commit ff94823

反轉佇列中的節點。

先檢查佇列（head）是否存在，和是否為空，接著逐一走訪每個節點，將 prev 和 next 交換。

只需要逐一走訪每個節點，並使用 list_move() 依序將其插入到佇列的開頭處即可。

- do {
-     temp = cur->next;
-     cur->next = cur->prev;
-     cur->prev = temp;
-     cur = temp;
- } while (cur != head);
+ list_for_each_safe (cur, safe, head)
+     list_move(cur, head);

q_reverseK()

commit c954812

將佇列中的節點以 k 個為一組作反轉。

先檢查佇列（head）是否存在、是否為空、size 是否大於 k，接著依照 k 個為一組走訪，將其中的每個節點作反轉。

do {
    do {
        temp = cur->next;
        cur->next = cur->prev;
        cur->prev = temp;
        cur = temp;
    } while (cur != head && count > 0);
    cur->prev->prev = prev;
    prev->next = cur->prev;
    start->next = cur;
    prev = start;
    start = cur;
} while (size > k);

善用 List API，撰寫出更精簡的程式碼

了解，我會依序檢查可以使用哪些 List API。

q_sort()

commit ae7aeba

將佇列中的節點升序/降序排序。

若目前佇列的節點數大於二，則使用快慢指標找到目前佇列的中點，並依照終點將其切為兩條佇列，直到所有佇列的節點數都只剩下一個，再開始依序將兩兩一組佇列進行合併。

while (fast != head && fast->next != head) {
    slow = slow->next;
    fast = fast->next->next;
}

list_cut_position(&left, head, slow);
list_splice_init(head, &right);

if (descend ? strcmp(left_entry->value, right_entry->value) >= 0
            : strcmp(left_entry->value, right_entry->value) <= 0)
    list_move(left->next, cur);
else
    list_move(right->next, cur);
  1. 如果不使用遞迴呼叫，你該如何實作排序程式？
  2. 你如何確保目前的測試已涵蓋排序演算法最差狀況？
  3. 目前的測試如何檢查程式碼是否 stable (sorting)？

q_ascend()

commit 1cb637d, commit b22c3f0, commit 7bc72a1

刪除 移走佇列中滿足條件的節點: 右方存在嚴格小於此節點的節點。

先檢查佇列（head）是否存在，和是否為空，接著反向逐一走訪每個節點，同時紀錄目前所觀察到的最小值，若目前走訪的節點大於最小值，就刪除移走目前節點，反之更新最小值，並紀錄佇列中剩下的節點數。

可以不用建立一個字元陣列紀錄目前的最小值，直接使用指標獲取目前觀察到的最小值。

while (cur != head) {
    if (strcmp(entry->value, min->value) >= 0) {
-       list_del(cur);
-       q_release_element(entry);
+       list_del_init(cur);
    } else {
-       strncpy(min_value, entry->value, MAX_STRING_LENGTH - 1);
-       min_value[MAX_STRING_LENGTH - 1] = '\0';
        min = entry;
    }
}

q_descend()

commit a18d7ff, commit b22c3f0, commit 7bc72a1

刪除 移走佇列中滿足條件的節點: 右方存在嚴格大於此節點的節點。

和 q_ascend() 大致相同，只須將紀錄最小值改成紀錄最大值。

- if (strcmp(entry->value, min->value) >= 0)
+ if (strcmp(entry->value, max->value) <= 0)

q_merge()

commit abee78b

將所有佇列合併成一個升序/降序的佇列。

利用 list_splice_init() 將所有佇列先合併成一個佇列，並且同時紀錄目前佇列的大小，再使用 q_sort() 對其進行排序，最後回傳佇列的大小。

list_for_each_entry (cur, head, chain) {
    list_splice_init(cur->q, tar->q);
    size += cur->size;
}

q_sort(tar->q, descend);

你如何確保目前的測試已涵蓋排序演算法的最差狀況？

研讀論文 〈 Dude, is my code constant time? 〉

oreparaz/dudect

此篇論文介紹了一個量測程式碼的方法 dudect，用以量測其是否能在常數時間 O(1) 內執行完畢。

實驗方法

對執行時間進行洩漏檢測，量測兩種不同輸入類別各自的執行時間，接著統計兩者在時間分佈上是否有差異。

實驗步驟

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

量測執行時間

採用 fix-vs-random 的方法，將第一組輸入設定為固定值，而第二組輸入則會根據每次的量測隨機設定。

後處理

在進行統計分析之前對於每次的量測結果進行後處理，大部分的量測值會集中在較小的執行時間，而有一小部份量測值會出現特別高的執行時間，導致時間分佈出現正偏態，故須要對結果進行取捨。

image

統計測試

使用 Welch 的 t 檢驗測試兩組數據的時間分佈是否相等，若結果顯示不相等，則意味著存在時間洩漏。

Student's t-distribution

是一種機率分佈，用於依照小樣本來估計母體為常態分佈且標準差未知的期望值，由 v 值（自由度）控制其分佈的形狀，當 v 值越低，則出現極端值的概率較高，而 v 值越高，其分佈就越接近常態分佈。

Screenshot from 2024-03-01 18-01-47

修改 lab0-c

我觀察到 oreparaz/dudect 程式碼中的 prepare_percentiles() 函式會根據不同百分位數計算出對應的 percentile，而它們會在 update_statistics() 函式中被用於進行比較，若量測的執行時間小於對應的 percentile，則將其用於統計分析中，大於就排除這些執行時間特別長的量測結果。

目前的 lab0-c 並未進行以上的檢查，會導致將一些執行時間異常的結果也納入統計中，導致程式碼的常數時間檢測會無法通過，當加入上述的檢查後，即可排除異常的結果。

列出論文和程式碼實作的出入之處，並予以討論。

論文與程式碼的主要差異有三，分別為：

cmp(): 比較兩個 64 位整數的大小，用來當作執行 qsort() 時的比較依據。

percentile(): 從一組測量值中找到特定百分位數的值。

prepare_percentiles(): 根據不同的百分位數設定不同的閥值，並透過這些閥值來篩選測量數據，可由此排除執行時間異常的數據。

qtest 新增命令 shuffle

透過 Fisher-Yates shuffle 演算法對佇列進行洗牌。

Fisher-Yates shuffle

步驟

走訪串列得知串列大小並設定 last 為最後一個節點。

從首節點到 last 節點中隨機取一個節點與 last 節點交換。

將 last 往前移一個節點。

重複步驟 2、3 直到 last 為首節點。

![Screenshot from 2024-03-18 12-56-30](https://hackmd.io/_uploads/Byv9YHSCT.png =80%x)

以 Graphviz 重新製圖，並嵌入到 HackMD 筆記中。

示意流程圖

一開始先將 last 設為最後一個節點。







G

Original List


1

1



2

2



1->2





2->1





3

3



2->3





3->2





4

4



3->4





4->3





5(last)

5(last)



4->5(last)





5(last)->4

隨機從首節點到 last 節點取一個和 last 節點交換，並將 last 向前移一個節點，這裡取節點 3 當範例。







G



1

1



2

2



1->2





2->1





5

5



2->5





5->2





4(last)

4(last)



5->4(last)





4(last)->5





3

3



4(last)->3





3->4(last)

重複隨機取節點和 last 交換的步驟，這裡取節點 1 當範例。







G



4

4



2

2



4->2





2->4





5(last)

5(last)



2->5(last)





5(last)->2





1

1



5(last)->1





1->5(last)





3

3



1->3





3->1

重複隨機取節點和 last 交換的步驟，這裡取節點 5 當範例。







G



4

4



2(last)

2(last)



4->2(last)





2(last)->4





5

5



2(last)->5





5->2(last)





1

1



5->1





1->5





3

3



1->3





3->1

重複隨機取節點和 last 交換的步驟，這裡取節點 4 當範例。







G



4(last)

4(last)



2

2



4(last)->2





2->4(last)





5

5



2->5





5->2





1

1



5->1





1->5





3

3



1->3





3->1

當 last 指到首節點時結束，完成節點的洗牌。







G



4

4



2

2



4->2





2->4





5

5



2->5





5->2





1

1



5->1





1->5





3

3



1->3





3->1

實作

commit 65c2bfc

while (last != head && --size) { 
    int index = rand() % size;
    struct list_head *node = head->next, *temp = last->prev;
    while (index--)
        node = node->next;

    list_move(last, node->prev);
    if (node != temp)
        list_move(node, temp);
    last = node->prev;
}

加入到 qtest 中

避免非必要的項目縮排 (即 * , - 或數字)，以清晰、明確，且流暢的漢語書寫。

授課教師在大學教書十餘年，見到不少學生在課堂表現不俗，但在面試場合卻無法清晰地闡述自己的成果和獨到的成就，從而錯過躋身一流資訊科技企業的機會。為此，要求學員書寫開發紀錄，並隨時做好「當主管問起，就能清晰解釋自己的投入狀況」，是強調讓學員「翻身」的本課程在意的事。

濫用條列 (或說 bullet) 來展現，乍看很清爽，但在面試的場合中，就很難用流暢的話語說明。反之，若平日已有這方面的練習，則面試過程中，才可充分展現自己專業之處。

首先在 qtest.c 中加入 do_shuffle() 函式，接著在 console_init() 中加入 shuffle 命令，最後在 qtest 中輸入 help 可看到 shuffle 命令已成功加入。

Commands:
  #           ...          | Display comment
  shuffle                  | Shuffle the order of nodes in the list

驗證

使用 lab0 (D) 提供之驗證程式碼進行驗證。

將初始串列設定為 [1, 2, 3, 4]，並使用 1000000 次 shuffle，將每次執行的結果記錄下來。

四個節點組成的串列共有 24 (4!) 種排列方式，當執行 1000000 次 shuffle，每一種排列方式平均會出現 41666 次。

Expectation:  41666
Observation:  {'1234': 41375, '1243': 41683, '1324': 41545, '1342': 42180, '1423': 41396, '1432': 41561, '2134': 41821, '2143': 41784, '2314': 41315, '2341': 41531, '2413': 41805, '2431': 41480, '3124': 41586, '3142': 41432, '3214': 42248, '3241': 41822, '3412': 41855, '3421': 41530, '4123': 41623, '4132': 41984, '4213': 41449, '4231': 41620, '4312': 41601, '4321': 41774}
chi square sum:  31.861085777372438

Screenshot from 2024-03-18 15-46-41
由數據得知每種排列分式出現的次數都大約在 41666 次左右，符合離散均勻分佈的期望特徵。

引入 lib/list_sort.c 到 lab0-c 專案中

步驟

commit 3893eb1

避免非必要的項目縮排 (即 * , - 或數字)，以清晰、明確，且流暢的漢語書寫。

授課教師在大學教書十餘年，見到不少學生在課堂表現不俗，但在面試場合卻無法清晰地闡述自己的成果和獨到的成就，從而錯過躋身一流資訊科技企業的機會。為此，要求學員書寫開發紀錄，並隨時做好「當主管問起，就能清晰解釋自己的投入狀況」，是強調讓學員「翻身」的本課程在意的事。

濫用條列 (或說 bullet) 來展現，乍看很清爽，但在面試的場合中，就很難用流暢的話語說明。反之，若平日已有這方面的練習，則面試過程中，才可充分展現自己專業之處。

首先將 list_sort.c 和 list_sort.h 加入到 lab0-c 中，接著將 list_sort.o 加入到 MakeFile 的 OBJS 中，然後在 qtest.c 中加入 do_list_sort() 函式，且在 console_init() 中加入 list_sort 命令，最後在 qtest 中輸入 help 可看到 list_sort 命令已成功加入。

Commands:
  #           ...          | Display comment
  list_sort                | Sort queue by linux list sort

和 q_sort 比較

測試用 shell script，可調整佇列大小。

echo -e "new\nit RAND 200000\ntime\nsort\ntime\nfree" | ./qtest

echo -e "new\nit RAND 200000\ntime\nlist_sort\ntime\nfree" | ./qtest

q_sort

佇列大小 Round 1 Round 2 Round 3 Round 4 Round 5 平均
200k 0.128 0.140 0.139 0.133 0.139 0.136
400k 0.307 0.329 0.332 0.317 0.330 0.323
600k 0.493 0.521 0.528 0.511 0.503 0.511
800k 0.693 0.769 0.756 0.733 0.736 0.737
1M 0.903 0.962 0.947 0.955 0.945 0.942

list_sort

佇列大小 Round 1 Round 2 Round 3 Round 4 Round 5 平均
200k 0.116 0.117 0.116 0.119 0.116 0.117
400k 0.266 0.281 0.271 0.263 0.266 0.269
600k 0.433 0.427 0.427 0.424 0.433 0.429
800k 0.602 0.604 0.598 0.632 0.592 0.606
1M 0.756 0.760 0.755 0.761 0.773 0.761

比較圖

image
從資料與圖表可得知目前專案實作的 q_sort 略慢於 list_sort，須通過研讀 list_sort 程式碼得知具體差異為何。

使用 perf 分析

在佇列大小為 200k ，執行 100 次來觀察。

Performance counter stats for './test_q_sort.sh' (100 runs):

         1874,4031      cache-misses              #   43.136 % of all cache refs      ( +-  0.15% )
         4332,7132      cache-references                                              ( +-  0.05% )
       9,7055,4711      instructions              #    0.78  insn per cycle           ( +-  0.01% )
      12,4672,1225      cycles                                                        ( +-  0.11% )

          0.258425 +- 0.000369 seconds time elapsed  ( +-  0.14% )

Performance counter stats for './test_list_sort.sh' (100 runs):

         1756,4224      cache-misses              #   47.197 % of all cache refs      ( +-  0.54% )
         3733,7572      cache-references                                              ( +-  0.05% )
       9,2544,3885      instructions              #    0.78  insn per cycle           ( +-  0.01% )
      11,6991,3859      cycles                                                        ( +-  0.30% )

           0.25129 +- 0.00104 seconds time elapsed  ( +-  0.41% )

cache-misses : 表示程式執行期間無法在快取中找到所需資料而導致的快取未命中次數。
cache-references : 表示程式執行期間對快取的總參考次數。
instructions : 表示程式執行期間執行的指令數量。
cycles : 表示程式執行期間花費的 CPU 週期數。

觀察兩筆資料發現 list_sort 在 cache-misses、cache-references、instructions、cycles 中都小於 q_sort，但在 cache-misses 的比例比 q_sort 要高，須通過研讀比較兩者程式的差異。

研讀 list_sort

merge()

將兩個已經排序好的串列 (a、b) 合併為一個串列，並將合併後的串列返回。

利用 cmp() 比較 a、b 當前節點的大小，若 a 節點小於或等於 b 節點，就通過間接指標將 a 節點接在新串列後方，反之則將 b 節點接在新串列後方，在判斷 a、b 節點大小時若兩者相等則串接 a 節點可以保持 stable 的特性，而使用間接指標可以避免不必要的記憶體空間分配，降低空間複雜度。

此函式只會維護 next 指標，而沒有維護 prev 指標。

merge_final()

當完成所有排序操作後，將最終兩個排序好的串列 (a、b) 合併為一個串列，並將此串列恢復成雙向環狀的鏈結串列。

在研讀此函式時對以下程式碼感到疑惑，為什麼 if 判斷式中要使用 unlikely()，且為什麼要比較 b 和 b 的大小?

do {
    if (unlikely(!++count))
        cmp(priv, b, b);
    b->prev = tail;
    tail = b;
    b = b->next;
} while (b);
為什麼 if 判斷式中要使用 unlikely()

在 linux/compiler.h 中 unlikely 定義如下:

# define unlikely(x)	__builtin_expect(!!(x), 0)

此巨集會先對 x 做兩次 not 運算，因為 x 可能不是 0 或 1 的整數，通過兩次 not 運算後可以將值限制在 0 或 1 之間。

我參照 gcc 13.2 第 6.59 章說明的 __builtin_expect() 後了解此函式的功能為向編譯器提供分支的預測資訊，當 __builtin_expect(x, 0) 時預期 x 的值為 0，而 __builtin_expect(x, 1) 時則預期 x 為 1。

所以 unlikely(!++count) 此判斷式只有在當 count 值增加 1 後變成 0 (溢位) 時成立，這種情況非常罕見，所以這裡才用 unlikely 來提示編譯器此分支不常發生。

但我看到其中預設 __builtin_expect 為真的機率為 90%，不懂為什麼要以此機率當預設值。

For the purposes of branch prediction optimizations, the probability that a __builtin_expect expression is true is controlled by GCC’s builtin-expect-probability parameter, which defaults to 90%.

為什麼要比較 b 和 b 的大小

因為 cmp() 會根據傳入的比較函式不同而改變，因此我查看了 lib/test_list_sort.c 的比較函式，在其中發現比較時會呼叫 check 函式。

首先此函式會先使用 KUNIT_EXPECT_LT_MSG 巨集來檢查 ela 和 ela 的 serial 是否小於 TEST_LIST_LEN，確保他們的大小在特定範圍內。

KUNIT_EXPECT_LT_MSG(test, ela->serial, (unsigned int)TEST_LIST_LEN, "incorrect serial");
KUNIT_EXPECT_LT_MSG(test, elb->serial, (unsigned int)TEST_LIST_LEN, "incorrect serial");

接著使用 KUNIT_EXPECT_PTR_EQ_MSG 巨集來比較 elts 中對應編號的元素是否和 ela 和 elb 匹配。

KUNIT_EXPECT_PTR_EQ_MSG(test, elts[ela->serial], ela, "phantom element");
KUNIT_EXPECT_PTR_EQ_MSG(test, elts[elb->serial], elb, "phantom element");

最後使用 KUNIT_EXPECT_EQ_MSG 巨集來比較 ela 和 elb 的 position1 和 position2 是否和預設值相同，驗證內容沒有被意外修改。

KUNIT_EXPECT_EQ_MSG(test, ela->poison1, TEST_POISON1, "bad poison");
KUNIT_EXPECT_EQ_MSG(test, ela->poison2, TEST_POISON2, "bad poison");
KUNIT_EXPECT_EQ_MSG(test, elb->poison1, TEST_POISON1, "bad poison");
KUNIT_EXPECT_EQ_MSG(test, elb->poison2, TEST_POISON2, "bad poison");

除此之外根據註解的說明，如果要合併的串列非常不平衡 (例如已經排序完畢)，會造成迴圈執行次數較大，此時可以在 cmp() 中定期呼叫 cond_resched()，此函式會根據當前行程已經占用的 CPU 時間和系統中其他行程的狀態判斷是否要讓出 CPU，使其他行程不會產生 starvation。

list_sort()

通過呼叫 merge() 和 merge_final() 對串列進行排序。

其中最不理解的部分為迴圈內判斷是否該進行合併的程式碼。

do {
    /* Find the least-significant clear bit in count */
    for (bits = count; bits & 1; bits >>= 1)
        tail = &(*tail)->prev;
    /* Do the indicated merge */
    if (likely(bits)) {
        struct list_head *a = *tail, *b = a->prev;
        a = merge(priv, cmp, b, a);
        /* Install the merged result in place of the inputs */
        a->prev = b->prev;
        *tail = a;
    }
} while (list);

首先 for 迴圈會通過位元運算來找到 count 最低位的 0，並同時更新 tail 指標，當 count 為 2 的冪加 1 時，就會執行一次合併，這樣是為了確保最多只有兩個子串列在等待合併。

Last changed by 
 
subsidium
0
2
378

Read more

2024q1 Homework5 (assessment)

contributed by < >

Jun 17, 2024
2024q1 Homework4 (quiz3+4)

contributed by < Lccgth >

May 30, 2024
2024q1 Homework6 (intergration)

contributed by < Lccgth >

May 3, 2024
2024q1 Homework2 (quiz1+2)

contributed by < Lccgth >

Mar 20, 2024
Read more from subsidium
Published on HackMD