2022q1 Homework4 (quiz4)

contributed by < Kevin-Shih >

執行環境

lscpu

$ lscpuArchitecture: CPU op-mode(s): Byte Order: Address sizes: CPU(s): On-line CPU(s) list: Thread(s) per core: Core(s) per socket: Socket(s): NUMA node(s): Vendor ID: CPU family: Model: Model name: Stepping: CPU MHz: CPU max MHz: CPU min MHz: BogoMIPS: Virtualization: L1d cache: L1i cache: L2 cache: L3 cache: NUMA node0 CPU(s): >
x86_64
32-bit, 64-bit
Little Endian
39 bits physical, 48 bits virtual
4
0-3
1
4
1
1
GenuineIntel
6
158
Intel® Core™ i5-7300HQ CPU @ 2.50GHz
9
2500.000
3500.0000
800.0000
4999.90
VT-x
128 KiB
128 KiB
1 MiB
6 MiB
0-3

gcc version

$ gcc –version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0

測驗 1

題目
已知輸入必為大於 0 的數值 (即 x > 0)，以下程式碼可計算

⌈ l o g 2 (x) ⌉

，也就是 ceil 和 log2 的組合並轉型為整數:

















int ceil_log2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;                                                                                                                                    
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (EXP1) + 1; // EXP1 = r | shift | x >> 1
}

請補完，使其行為符合預期。

EXP1 為表示式，限制使用 ^, &, |, <<, >> 這幾個運算子，可能會出現常數

運作原理與解題

與第三週測驗 7 的原理十分相近，但加上取 ceil 的功能，回傳值處的 + 1 就是用來處理 ceil 的。同時因為是向上取整的緣故，當 x 正好等於 2 的冪時 log2 已是整數不應 + 1 故透過 x-- 處理，見下方公式。

\begin{aligned} ⌈ l o g 2 (x) ⌉ & = {\begin{cases} i l o g 2 (x), & \forall n \in N, x = 2^{n} \\ i l o g 2 (x) + 1, & \forall n \in N, \forall x \in N^{+}, x \neq 2^{n} \end{cases} \\ = i l o g 2 (x - 1) + 1, \forall x \in N^{+}, x \neq 1 \end{aligned}

忽略 x = 1 此程式碼對於該情形輸出錯誤答案，正解應為 0，但輸出恆大於等於 1 (因 return 時 + 1)

#6 ~ #7 當 x 的 first set 在高位的 16 bits 中， x 會右移 16 bits 並在剩下的 16 bits 繼續找 first set ， r 則設為 16。若不是的話， r 會為 0 不影響後續步驟。 (會變成找低位的 16 bits 中使否有 first set)

#8 ~ #10 則是找在剩下的 16 bits 中 x 的 first set 是否在較高的 8 bits 中，若有 x 會再右移 8 bits 並在剩下的 8 bits 繼續找 first set ， r 則加上 8。

#11 ~ #13, #14 ~ #15 以此類推尋找剩下的 8 bits 及 4 bits。

由於最後 #15 做完的 shift 尚未加到 r 中，因此 EXP1 前半為 r | shift，而剩下的 2 bits 尚未尋找故 EXP1 還要修改為 r | shift | x >> 1，即當 x 的 first set 在 2 bits 中的高位要再加 1 。

改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless

根據 logarithm 的數學定義 “The logarithm of a positive real number x with respect to base b” ，可以看出 log(x) 的定義域為 x > 0 ，因此 x = 0 屬於未定義的情形。

若根據 log, log2 的 manual page，“If x is zero, then a pole error occurs, and the functions return -HUGE_VAL.” ，同樣顯示 x = 0 同樣不在該函數的定義域，應無法以 branchless 實做，而是產生對應的錯誤訊息。

在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有)

在下列的 kernel/sched/fair.c 程式碼片段中有出現類似的形式 1 + ilog2(cpus) ，用於一段更新一些 tunable parameters 的函數，其中一種 policy 採用與 cpu 數量成對數關係的預測方式。

/*
 * Increase the granularity value when there are more CPUs,
 * because with more CPUs the 'effective latency' as visible
 * to users decreases. But the relationship is not linear,
 * so pick a second-best guess by going with the log2 of the
 * number of CPUs.
 *
 * This idea comes from the SD scheduler of Con Kolivas:
 */
static unsigned int get_update_sysctl_factor(void)
{
	unsigned int cpus = min_t(unsigned int, num_online_cpus(), 8);
	unsigned int factor;

	switch (sysctl_sched_tunable_scaling) {
	case SCHED_TUNABLESCALING_NONE:
		factor = 1;
		break;
	case SCHED_TUNABLESCALING_LINEAR:
		factor = cpus;
		break;
	case SCHED_TUNABLESCALING_LOG:
	default:
		factor = 1 + ilog2(cpus);
		break;
	}

	return factor;
}

測驗 2

題目
改寫第 3 週測驗題的測驗 11 裡頭的 fls 函式 (fls 意謂 “find last set”)，使其得以計算 Find first set:

#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)

#include <stddef.h>

static inline size_t ffs(unsigned long x)
{
    if (x == 0)
        return 0;

    size_t o = 1;
    unsigned long t = ~0UL;
    size_t shift = BITS_PER_LONG;

    shift >>= 1;
    t >>= shift;

    while (shift) {
        if ((EXP2) == 0) { // EXP2 = x & t
            x >>= shift;
            EXP3; // EXP3 = o += shift
        }

        shift >>= 1;
        t >>= shift;
    }

    return o;
}

請補完，使其行為符合預期。

EXP2 和 EXP3 限制使用 ^, &, |, <<=, >>=, +=, -= 這幾個運算子，可能會出現常數

運作原理與解題

後續的程式碼負責處理 x >= 1 的情形，ffs 至少為 1，因此回傳值 o 先初始化為 1，shift 則設為 BITS_PER_LONG / 2 並將 t 右移 shift 得到低位半邊全為 1 的 unsigned long，用於後續找尋 ffs 在高位的半邊或低位的半邊。

透過 BITS_PER_LONG 可以克服 LP64, LLP64 等 unsigned long 長度不同的問題。

if 的部分，t 作為 mask 用於判斷 ffs 是否位於低位的半邊(f 在低位半邊全為 1，高位半邊全為 0)，若是不在低位半邊，則 x 向左移 x 長度的一半(即 shift)並將 o 加上 shift。因此 EXP2 = x & t， EXP3 = o += shift。

而不論 if condition 是否成立，shift 都會除 2，而 t 右移一半的長度，以繼續搜尋 x 剩下的半邊直到 shift 歸零。

迴避 while, for, goto 等關鍵字以改寫出功能等價的實作

#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)

#include <stddef.h>

static inline size_t myffs(unsigned long x)
{
    if (x == 0)
        return 0;

    size_t ret = 1;
    unsigned long t = ~0UL;
    size_t shift = BITS_PER_LONG >> 1, m;

    t >>= shift;
    m = ((x & t) == 0) * shift;
    x >>= m;
    ret += m;
    shift >>= 1;

    t >>= shift;
    m = ((x & t) == 0) * shift;
    x >>= m;
    ret += m;
    shift >>= 1;

    t >>= shift;
    m = ((x & t) == 0) * shift;
    x >>= m;
    ret += m;
    shift >>= 1;

    t >>= shift;
    m = ((x & t) == 0) * shift;
    x >>= m;
    ret += m;
    shift >>= 1;

    t >>= shift;
    m = ((x & t) == 0) * shift;
    x >>= m;
    ret += m;
    shift >>= 1;

    /**
     * For LP64 shift = 1, check if ffs at higherend
     * of last two bits then `ret` += 1.
     * for LLP64 shift = 0, ignore this line
     */ 
    ret += ((x & 1) == 0) & shift;
    return ret;
}

透過將 while loop 展開並針對 LP64, LLP64 的不同改寫了最後一行，當 BITS_PER_LONG 為 32 執行到最後一行時 shift = 0 ，透過與 shift 作 AND 運算避免勿加多餘的數；而對於 BITS_PER_LONG 為 64 者則透過該行檢驗 ffs 在剩餘的 2 bits 中的高位或低位並加上對應的數值 0 或 1。

另外在中間的部份加入新的變數 m 方便拿掉 if 進可能減少 branch 次數，實現方式類似測驗 1 ，但為了同時適用 LP64, LLP64 做了一些修改。

m = ((x & t) == 0) * shift 類似 r = (x > 0xFFFF) << 4

測試 myffs
加入下方 main function 方便測試是否正確

int main(int argc, char **argv){
    printf("ffs = %ld\n", myffs(atol(argv[1])));
    return 0;
}

編譯後執行結果

$ gcc -o q2 q2.c
$ ./q2 2
ffs = 2
$ ./q2 1
ffs = 1
$ ./q2 64
ffs = 7
$ ./q2 258
ffs = 2

// 5120 = 0b1010000000000
$ ./q2 5120
ffs = 11

正確！

在 Linux 核心原始程式碼的 include/asm-generic/bitops 目錄找出相關程式碼，並探討應用案例

在 include/asm-generic/bitops/__ffs.h 中有相近的實做。

相關的應用在很多地方都有出現

音效相關
- sound/soc/codecs/rt1011.c
- sound/soc/codecs/rt1019.c
- sound/soc/codecs/tas2562.c
- 各種型號的 codec 中很多…
網路相關
- drivers/net/wireless/realtek/rtw88/coex.c
- drivers/net/wireless/realtek/rtw88/tx.c
- drivers/net/ethernet/chelsio/cxgb4/sge.c
- drivers/net/ethernet/sfc/falcon/falcon.c
- 各種有線 / 無線網路相關 drvier …
GPU drm 相關

測驗 3

題目
考慮以下改寫自 Linux 核心的程式碼:

struct foo_consumer {
    int (*handler)(struct foo_consumer *self, void *);
    struct foo_consumer *next;
};

struct foo {
    struct foo_consumer *consumers;
    unsigned long flags;
};

#include <stdbool.h>

/*
 * For foo @foo, delete the consumer @fc.
 * Return true if the @fc is deleted sfccessfully
 * or return false.
 */
static bool consumer_del(struct foo *foo, struct foo_consumer *fc)
{
    struct foo_consumer **con;
    bool ret = false;

    for (con = &foo->consumers; *con; EXP4) { // EXP4 = `con = &(*con)->next`
        if (*con == fc) {
            *con = EXP5; // EXP5 = fc->next
            ret = true;
            break;
        }
    }

    return ret;
}

請補完，使 consumer_del 行為符合註解規範。

EXP4 和 EXP5 都包含指標操作 (如 ->)

運作原理與解題

for loop 會依序走訪 foo->consumers 中所有的 foo_consumer，因此作為迴圈變數的 indirect pointer con 應該每次都指向儲存下一個 foo_consumer 指標的位置，因此 EXP4 = con = &(*con)->next。

而 EXP5 所在的 if 敘述中是將符合的 foo_consumer 從 linked list 中移除並將 ret 設為 true 表示正確移除，因此要將 *con 也就是前一個 fc 的 next 設為 fc->next 來跳過要刪除的 fc。因此 EXP5 = fc->next。

TODO

在 Linux 核心原始程式碼相似技巧的程式碼 (例如 uprobe)，並探討應用案例

區分 foo 和 foo_consumer 的好處

將 foo 作為容器， foo_consumer 作為內容物，明確區分兩者的功能有助於管理及使用，foo 作為容器包含了 foo_consumer 這一系列內容物的起始位置及一組 flags 標注內含的所有 foo_consumer 的狀態；foo_consumer 作為內容物以 linked list 的方式串起一系列的 foo_consumer ，當需要走訪節點時就不需要上到 foo 的層級，以 foo_consumer 作為 entry 走訪即可得到個節點的資料。

測驗 4

題目
以下嘗試用 lab0 提及的 setjmp 和 longjmp，用以實作〈你所不知道的 C 語言: goto 和流程控制篇〉闡述的 coroutine，參考的程式執行輸出如下:

Task 0: n = 3
Task 1: n = 3
Task 0: resume
Task 1: resume
Task 0: resume
Task 0: complete
Task 1: resume
Task 1: complete

n = 3 似乎應該各印出 3 次 resume 才對

原始程式碼 (檔名 jmp.c)

#include <setjmp.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

struct task {
    jmp_buf env;
    struct list_head list;
};

static LIST_HEAD(tasklist);
static void (**tasks)(void *);
static int ntasks;
static jmp_buf sched;

static void task_add(struct list_head *tasklist, jmp_buf env)
{
    struct task *t = malloc(sizeof(*t));
    memcpy(t->env, env, sizeof(jmp_buf));
    INIT_LIST_HEAD(&t->list);
    list_add_tail(&t->list, tasklist);
}

static void task_switch(struct list_head *tasklist)
{
    jmp_buf env;

    if (!list_empty(tasklist)) {
        struct task *t = list_first_entry(tasklist, struct task, list);
        EXP6;    // EXP6 = list_del(&t->list)
        memcpy(env, t->env, sizeof(jmp_buf));
        free(t);
        longjmp(env, 1);
    }
}

static void task_join(struct list_head *tasklist)
{
    jmp_buf env;

    while (!list_empty(tasklist)) {
        struct task *t = list_first_entry(tasklist, struct task, list);
        EXP7;    // EXP7 = list_del(&t->list)
        memcpy(env, t->env, sizeof(jmp_buf));
        free(t);
        longjmp(env, 1);
    }
}

void schedule(void)
{
    static int i;

    srand(0xCAFEBABE ^ (uintptr_t) &schedule); /* Thanks to ASLR */

    setjmp(sched);

    while (ntasks-- > 0) {
        int n = rand() % 5;
        tasks[i++](&n);
        printf("Never reached\n");
    }

    task_join(&tasklist);
}

/* A task yields control n times */

void task0(void *arg)
{
    jmp_buf env;
    static int n;
    n = *(int *) arg;

    printf("Task 0: n = %d\n", n);

    if (setjmp(env) == 0) {
        task_add(&tasklist, env);
        EXP8;    // EXP8 = longjmp(sched, 1)
    }

    for (int i = 0; i < n; i++) {
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 0: resume\n");
    }

    printf("Task 0: complete\n");
    longjmp(sched, 1);
}

void task1(void *arg)
{
    jmp_buf env;
    static int n;
    n = *(int *) arg;

    printf("Task 1: n = %d\n", n);

    if (setjmp(env) == 0) {
        task_add(&tasklist, env);
        EXP9;    // EXP9 = longjmp(sched, 1)
    }

    for (int i = 0; i < n; i++) {
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 1: resume\n");
    }

    printf("Task 1: complete\n");
    longjmp(sched, 1);
}

#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
int main(void)
{
    void (*registered_task[])(void *) = {task0, task1};
    tasks = registered_task;
    ntasks = ARRAY_SIZE(registered_task);

    schedule();

    return 0;
}

請補完，使行為符合註解規範。

EXP6 和 EXP7 都包含 List API 的使用
EXP8 和 EXP9 應有函式呼叫

運作原理與解題

執行這個程式時，registered_task 是包含 task0, task1 兩個 function designator 的陣列，ntask 表示 registered_task 中包含的 function designator 數量。接著 main 會呼叫 schedule()。

根據 C99 [ 6.5.3.2-4 ] 所述：
The unary * operator denotes indirection. If the operand points to a function, the result is a function designator
因此 (*registered_task[]) 是 function designator 的陣列
又根據 C99 [ 6.3.2.1 ]：
A function designator is an expression that has function type. Except when it is the operand of the sizeof operator) or the unary & operator, a function designator with type ‘‘function returning type’’ is converted to an expression that has type ‘‘pointer to function returning type’’.
tasks 是 pointer to pointer to function returning type 而 registered_task 也是 pointer to pointer to function returning type 因此可以直接 assign。

schedule()

void schedule(void)
{
    static int i;

    srand(0xCAFEBABE ^ (uintptr_t) &schedule); /* Thanks to ASLR */

    setjmp(sched);

    while (ntasks-- > 0) {
        int n = rand() % 5;
        tasks[i++](&n);
        printf("Never reached\n");
    }

    task_join(&tasklist);
}

先設好 jump_buf 以便跳回來，接著while loop 中依序呼叫 tasks 中的 function pointer 將 task0, task1 都初始化後(見下段)，呼叫 task_join() 以便執行 task0, task1 的內容。

task0(), task1()
task0 的 code 為例：

/* A task yields control n times */

void task0(void *arg)
{
    jmp_buf env;
    static int n;
    n = *(int *) arg;

    printf("Task 0: n = %d\n", n);

    if (setjmp(env) == 0) {
        task_add(&tasklist, env);
        EXP8;    // EXP8 = longjmp(sched, 1)
    }

    for (int i = 0; i < n; i++) {
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 0: resume\n");
    }

    printf("Task 0: complete\n");
    longjmp(sched, 1);
}

呼叫後會設置 jump_buf 後會將該 task 加入 task_list 並以 longjmp 跳回先前的 schedule() 紀錄的位置，因此 EXP8, EXP9 = longjmp(sched, 1)。後續跳回來時 setjmp 的回傳值會是由 longjmp 所指定的值，這次程式碼中均是 1，因不等於 0 故會繼續執行後續的 for loop。

void longjmp(jmp_buf env, int val);
After longjmp() is completed, program execution continues as if
the corresponding invocation of setjmp() had just returned the
value specified by val. The longjmp() function shall not cause
setjmp() to return 0; if val is 0, setjmp() shall return 1.
–longjmp manual

for loop 中會執行 @arg 所指定的次數，每次都會先 setjmp 後將 task 加入 tasklist 並呼叫 task_switch 切換到下個 task ，跳回來時會印出 resume。跳出 for loop 後則會印出 complete 並跳回 schedule()。

task_join

static void task_join(struct list_head *tasklist)
{
    jmp_buf env;

    while (!list_empty(tasklist)) {
        struct task *t = list_first_entry(tasklist, struct task, list);
        EXP7;    // EXP7 = list_del(&t->list)
        memcpy(env, t->env, sizeof(jmp_buf));
        free(t);
        longjmp(env, 1);
    }
}

簡單來說跳到 tasklist 第一個 entry 對應的位置繼續執行，並刪除第一個 entry。由 schedule() 呼叫。

當 tasklist 不為空的時候，取出第一個 entry 將其從 linked list 中移除，並將該 entry 所儲存的 jump_buf 複製到 env 後，釋放該 entry 所佔的記憶體空間，最後 longjmp 跳到 env 對應位置。因此 EXP7 = list_del(&t->list)。

task_add

static void task_add(struct list_head *tasklist, jmp_buf env)
{
    struct task *t = malloc(sizeof(*t));
    memcpy(t->env, env, sizeof(jmp_buf));
    INIT_LIST_HEAD(&t->list);
    list_add_tail(&t->list, tasklist);
}

將 setjmp 所設定的 jump_buf 複製到一個新的 entry 中並將該 entry 排入 tasklist 中的末端。

task_switch
與 task_join 所做的事完全相同，但由 task0(), task1() 呼叫。因此 EXP6 = list_del(&t->list)。

TODO

對比 concurrent-programs 裡頭的 coroutine 程式碼，如 tinync 和 preempt_sched，嘗試引入 UNIX Signal 來做到 preemptive scheduling
對比〈A brief history of the Linux Kernel’s process scheduler: The very first scheduler, v0.01〉，解說早期 Linux 核心 CPU 排程器的行為，並利用上述程式碼來模擬

上述 coroutine 實作的限制

因為 setjmp, longjmp 只恢復了包含 stack pointer, program counter 等暫存器的值，而區域變數 i 等 stack 內的 automatic variables 則沒有被保存及復原。

The setjmp() function saves various information about the calling environment (typically, the stack pointer, the instruction pointer, possibly the values of other registers and the signal mask) in the buffer env for later use by longjmp(). In this case, setjmp() returns 0.
–man setjmp

以及
The compiler may optimize variables into registers, and longjmp() may restore the values of other registers in addition to the stack pointer and program counter. Consequently, the values of automatic variables are unspeci-fied after a call to longjmp() if they meet all the following criteria:

they are local to the function that made the corresponding setjmp() call

their values are changed between the calls to setjmp() and longjmp()

they are not declared as volatile.
–man setjmp

因此若將題目中的程式實際執行後會出現下列情形 (為方便比較 n 設為 3)

$ gcc -g -o q4 q4.c 
$ ./q4
Task 0: n = 3
Task 1: n = 3
Task 0: before longjmp i = 0
Task 1: before longjmp i = 0
Task 0: after longjmp i = 0
Task 0: resume
Task 0: before longjmp i = 1
Task 1: after longjmp i = 1
Task 1: resume
Task 1: before longjmp i = 2
Task 0: after longjmp i = 2
Task 0: resume
Task 0: complete
Task 1: after longjmp i = 21881
Task 1: resume
Task 1: complete

不難看出兩個 task 間的 i 會互相影響，進而導致錯誤的結果。

而將 i 改為 static local variable 則會讓 i 從原先自動分配在 call stack 上改為分配在程式的 data segment 上，從而避免 call stack 沒有完整復原導致的錯誤。

修改後程式碼如下

void task0(void *arg)
{
    jmp_buf env;
    static int n;
    n = *(int *) arg;

    printf("Task 0: n = %d\n", n);

    if (setjmp(env) == 0) {
        task_add(&tasklist, env);
        longjmp(sched, 1);    // EXP8 = longjmp(sched, 1)
    }
    static int i;
    for (i = 0; i < n; i++) {
        printf("Task 0: before jmp i = %d\n", i);
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 0: after jmp i = %d\n", i);
        printf("Task 0: resume\n");
    }

    printf("Task 0: complete\n");
    longjmp(sched, 1);
}

執行結果

$ gcc -g -o q4 q4.c 
$ ./q4
Task 0: n = 3
Task 1: n = 3
Task 0: before jmp i = 0
Task 1: before jmp i = 0
Task 0: after jmp i = 0
Task 0: resume                //task 0 resume 1 
Task 0: before jmp i = 1
Task 1: after jmp i = 0
Task 1: resume                //task 1 resume 1 
Task 1: before jmp i = 1
Task 0: after jmp i = 1
Task 0: resume                //task 0 resume 2 
Task 0: before jmp i = 2
Task 1: after jmp i = 1
Task 1: resume                //task 1 resume 2 
Task 1: before jmp i = 2
Task 0: after jmp i = 2
Task 0: resume                //task 0 resume 3 
Task 0: complete
Task 1: after jmp i = 2
Task 1: resume                //task 1 resume 3 
Task 1: complete

正確!

先前 setjmp, longjmp 的 man page 提到會保存及回復 values of other registers ，因此測試一下若是以 inline asm 的方式挪用 ebx 存放變數 i ，是否可以得到相同結果。

EBX — Pointer to data in the DS segment
– Intel® 64 and IA-32 Architectures Software Developer's Manual Vol. 1 Chapter 3.4.1 (Page 3-12)

void task0(void *arg)
{
    jmp_buf env;
    static int n;
    n = *(int *) arg;

    printf("Task 0: n = %d\n", n);

    if (setjmp(env) == 0) {
        task_add(&tasklist, env);
        longjmp(sched, 1);    // EXP8 = longjmp(sched, 1)
    }
    register int i asm("ebx");
    for (i = 0; i < n; i++) {
        printf("Task 0: before jmp i = %d\n", i);
        if (setjmp(env) == 0) {
            task_add(&tasklist, env);
            task_switch(&tasklist);
        }
        printf("Task 0: after jmp i = %d\n", i);
        printf("Task 0: resume\n");
    }

    printf("Task 0: complete\n");
    longjmp(sched, 1);
}

編譯並執行

$ gcc -g -o q4 q4.c 
$ ./q4
Task 0: n = 3
Task 1: n = 3
Task 0: before jmp i = 0
Task 1: before jmp i = 0
Task 0: after jmp i = 0
Task 0: resume                //task 0 resume 1 
Task 0: before jmp i = 1
Task 1: after jmp i = 0
Task 1: resume                //task 1 resume 1 
Task 1: before jmp i = 1
Task 0: after jmp i = 1
Task 0: resume                //task 0 resume 2 
Task 0: before jmp i = 2
Task 1: after jmp i = 1
Task 1: resume                //task 1 resume 2 
Task 1: before jmp i = 2
Task 0: after jmp i = 2
Task 0: resume                //task 0 resume 3 
Task 0: complete
Task 1: after jmp i = 2
Task 1: resume                //task 1 resume 3 
Task 1: complete

在我的環境中是可以得到相同結果的。

Jim Huang

2022/03/29 10:03:47

其中一種 policy 採用與 cpu 數量成對數關係的預測方式。

TODO: 搭配 Linux CPU 排程器書籍提到的 sysctl_sched_min_granularity 來探討 (Edited)

2022/04/15 02:58:31

如果增加 -O2 編譯選項，則這個作法會使執行結果不如預期 (Edited)

2022/04/15 03:04:43

TODO: 對照 -O2 的組合語言輸出 (Edited)

2022/04/15 03:05:16

compiler barrier # (Edited)

2022q1 Homework4 (quiz4)

測驗 1

運作原理與解題

改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless

在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例 (提示: 在 Linux 核心排程器就有)

測驗 2

運作原理與解題

迴避 while, for, goto 等關鍵字以改寫出功能等價的實作

在 Linux 核心原始程式碼的 include/asm-generic/bitops 目錄找出相關程式碼，並探討應用案例

測驗 3

運作原理與解題

區分 foo 和 foo_consumer 的好處

測驗 4

運作原理與解題

上述 coroutine 實作的限制

Read more

2022q1 Homework1 (lab0)

2022q1 Homework5 (quiz6)

2022q1 Homework5 (quiz8)

2022q1 Homework5 (quiz5)