2022q1 第 9 週測驗題

tags: linux2022

目的: 檢驗學員對 並行和多執行緒程式設計 的認知

作答表單:

• 測驗 1 (Linux 核心設計)
• 測驗 2 (Linux 核心實作)

測驗 1

考慮到一個 lock-free 的軟體計時器實作，測試程式如下:

#include <inttypes.h>
#include <stdio.h>                         
#include <stdlib.h>

#include "lf_timer.h"

#define EX_HASHSTR(s) #s
#define EX_STR(s) EX_HASHSTR(s)

#define EXPECT(exp)                                                      \
    do {                                                                 \
        if (!(exp))                                                      \
            fprintf(stderr, "FAILURE @ %s:%u; %s\n", __FILE__, __LINE__, \
                    EX_STR(exp)),                                        \
                abort();                                                 \
    } while (0)
    
static void callback(lf_timer_t tim, lf_tick_t tmo, void *arg)
{
    lf_tick_t tck = lf_timer_tick_get();
    printf("Timer %d expiration %#" PRIx64 " now %#" PRIx64 "\n", tim, tmo,
           tck);
    *(lf_tick_t *) arg = tck;
}   

int main(void)
{
    lf_tick_t exp_a = LF_TIMER_TICK_INVALID;
    lf_timer_t tim_a = lf_timer_alloc(callback, &exp_a);
    EXPECT(tim_a != LF_TIMER_NULL);
    EXPECT(lf_timer_set(tim_a, 1));
    EXPECT(!lf_timer_set(tim_a, 1));

    lf_timer_tick_set(0);
    lf_timer_expire();
    EXPECT(exp_a == LF_TIMER_TICK_INVALID);

    lf_timer_tick_set(1);
    lf_timer_expire();
    EXPECT(exp_a == 1);
    EXPECT(lf_timer_set(tim_a, 2));
    EXPECT(lf_timer_reset(tim_a, 3));

    lf_timer_tick_set(2);
    lf_timer_expire();
    EXPECT(exp_a == 1);
    EXPECT(lf_timer_cancel(tim_a));

    lf_timer_tick_set(3);
    lf_timer_expire();
    EXPECT(exp_a == 1);
    EXPECT(!lf_timer_reset(tim_a, UINT64_C(0xFFFFFFFFFFFFFFFE)));
    EXPECT(lf_timer_set(tim_a, UINT64_C(0xFFFFFFFFFFFFFFFE)));
    EXPECT(lf_timer_reset(tim_a, UINT64_C(0xFFFFFFFFFFFFFFFE)));

    lf_timer_expire();
    EXPECT(exp_a == 1);

    lf_timer_tick_set(UINT64_C(0xFFFFFFFFFFFFFFFE));
    lf_timer_expire();
    EXPECT(exp_a == UINT64_C(0xFFFFFFFFFFFFFFFE));

    lf_timer_free(tim_a);

    printf("timer tests complete\n");
    return 0;
}

預期執行輸出:

Timer 0 expiration 0x1 now 0x1
Timer 0 expiration 0xfffffffffffffffe now 0xfffffffffffffffe
timer tests complete

程式碼可參見 lf_timer，使用 C11 搭配 GNU extension。

請補完程式碼，使其運作符合預期。作答規範:

• COND 為表示式
• FF1 和 FF2 為表示式

延伸問題:

1. 解釋上述程式碼運作原理
2. 參照 interval-timer，撰寫 lock-based 實作，並提供可適用於 lock-based 和 lock-free timer 實作的測試程式 (含 benchmark)，並解讀實驗結果

---

測驗 2

考慮到支援多個生產者—多個消費者的 bounded buffer lockfree 實作: gist (部分程式碼隱蔽)

程式碼使用 C11 Atomics 和 Threads 撰寫，預期執行輸出:

Test: Spsc: null_pointers       : PASS
Test: Spsc: create              : PASS
Test: Spsc: empty               : PASS
Test: Spsc: full                : PASS
Test: Spsc: sums10000           : PASS
Test: Mpsc: null_pointers       : PASS
Test: Mpsc: create              : PASS
Test: Mpsc: empty               : PASS
Test: Mpsc: full                : PASS
Test: Mpsc: sums10000           : PASS
Test: Spmc: null_pointers       : PASS
Test: Spmc: create              : PASS
Test: Spmc: empty               : PASS
Test: Spmc: full                : PASS
Test: Spmc: sums10000           : PASS
Test: Mpmc: null_pointers       : PASS
Test: Mpmc: create              : PASS
Test: Mpmc: empty               : PASS
Test: Mpmc: full                : PASS
Test: Mpmc: sums10000           : PASS

請補完程式碼，使其執行符合預期。作答規範:

• MMM 是表示式，依據指定程式碼風格撰寫，以最精簡的形式