# [2022q1](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 9 週測驗題
###### tags: `linux2022`

:::info
目的: 檢驗學員對 **[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)** 的認知
:::

作答表單:
* ==[測驗 `1`](https://docs.google.com/forms/d/e/1FAIpQLSf0qSZqImkfHq6ComFcmMTulKSyVbWSClyQ2lIIMgsyeNfS6Q/viewform)== (Linux 核心設計)
* ==[測驗 `2`](https://docs.google.com/forms/d/e/1FAIpQLSfeaMhMykb8L884svgFToAdQjtiPH2WLoBc_CCjXG2B4AUyew/viewform)== (Linux 核心實作)

### 測驗 `1`

考慮到一個 [lock-free]((https://hackmd.io/@sysprog/concurrency)) 的軟體計時器實作，測試程式如下:

#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](https://gist.github.com/jserv/ee63f467f393153fd865a6b772edc63d)，使用 C11 搭配 GNU extension。

請補完程式碼，使其運作符合預期。作答規範:
* `COND` 為表示式
* `FF1` 和 `FF2` 為表示式

:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 參照 [interval-timer](https://github.com/sn0wvall/interval-timer)，撰寫 lock-based 實作，並提供可適用於 lock-based 和 lock-free timer 實作的測試程式 (含 benchmark)，並解讀實驗結果
:::

---

### 測驗 `2`

考慮到支援多個生產者—多個消費者的 bounded buffer lockfree 實作: [gist](https://gist.github.com/jserv/d2e27c8d9fc3c3e316fd91039633def5) (部分程式碼隱蔽)

程式碼使用 C11 [Atomics](https://en.cppreference.com/w/c/atomic) 和 [Threads](https://en.cppreference.com/w/c/thread) 撰寫，預期執行輸出:

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` 是表示式，依據指定程式碼風格撰寫，以最精簡的形式