# [2020q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 7 週測驗題
###### tags: `linux2020`

:::info
目的: 檢驗學員對 C 語言流程控制的認知
:::

==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSexCdL_ll_l1kzMwsMit_Wh1lCVFomLhstZvELCn9K4NX3Q0Q/viewform)==

---

### 測驗 `1`

延伸 [C 語言: goto 和流程控制](https://hackmd.io/s/B1e2AUZeM)，考慮以下 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 實作程式碼: (`coroutine.c`)

/*
 * Stackless coroutines.
 * This is an async/await implementation for C based on Duff's device.
 *
 * Features:
 * 1. the async state is caller-saved rather than callee-saved.
 * 2. Subroutines can have persistent state that is not just static state,
 *    because each async subroutine accepts its own struct it uses as a
 *    parameter, and the async state is stored there.
 * 3. Because of the more flexible state, async subroutines can be nested
 *    in tree-like fashion which permits fork/join concurrency patterns.
 */

/* event status */
typedef enum ASYNC_EVT { ASYNC_INIT = 0, ASYNC_DONE = -1 } async;

/* Declare the async state */
#define async_state unsigned int _async_kcont
struct async { async_state; };

/* Mark the start of an async subroutine */
#define async_begin(k)           \
    XXX1                         \
    XXX2

/* Mark the end of a generator thread */
#define async_end          \
    default:               \
        return ASYNC_DONE; \
    }

/* Wait until the condition succeeds */
#define await(cond) await_while(!(cond))

/* Wait while the condition succeeds */
#define await_while(cond) 		\
    case __LINE__:                      \
        if (cond) return __LINE__       \

/* Initialize a new async computation */
#define async_init(state) (state)->_async_kcont = ASYNC_INIT

/* Check if async subroutine is done */
#define async_done(state) (state)->_async_kcont == ASYNC_DONE

/* Resume a running async computation and check for completion */
#define async_call(f, state) \
    (async_done(state) || ASYNC_DONE == ((state)->_async_kcont = (f)(state)))

struct async_sem { unsigned int count; };

/**
 * Initialize a semaphore
 *
 * This macro initializes a semaphore with a value for the
 * counter. Internally, the semaphores use an "unsigned int" to
 * represent the counter, and therefore the "count" argument should be
 * within range of an unsigned int.
 *
 * \param s A pointer to the object representing the semaphore.
 * \param c (unsigned int) The initial count of the semaphore.
 */
#define init_sem(s, c) (s)->count = c

/**
 * Wait for a semaphore
 *
 * This macro carries out the "wait" operation on the semaphore. The
 * wait operation causes the protothread to block while the counter is
 * zero. When the counter reaches a value larger than zero, the
 * protothread will continue.
 *
 * \param s A pointer to the object representing the semaphore.
 */
#define await_sem(s)           \
    do {                       \
        await((s)->count > 0); \
        XXX3;                  \
    } while (0)

/**
 * Signal a semaphore
 *
 * This macro carries out the "signal" operation on the semaphore. The
 * signal operation increments the counter inside the semaphore, which
 * eventually will cause waiting protothreads to continue executing.
 *
 * \param s A pointer to the object representing the semaphore.
 */
#define signal_sem(s) XXX4

/* Use case */

#include <stdio.h>
#include <unistd.h>

#define NUM_ITEMS 32
#define BUFSIZE 8

static int buffer[BUFSIZE];
static int bufptr;

static void add_to_buffer(int item) {
    printf("Item %d added to buffer at place %d\n", item, bufptr);
    buffer[bufptr] = item;
    bufptr = (bufptr + 1) % BUFSIZE;
}
static int get_from_buffer(void) {
    int item = buffer[bufptr];
    printf("Item %d retrieved from buffer at place %d\n", item, bufptr);
    bufptr = (bufptr + 1) % BUFSIZE;
    return item;
}

static int produce_item(void) {
    static int item = 0;
    printf("Item %d produced\n", item);
    return item++;
}

static void consume_item(int item) {
    printf("Item %d consumed\n", item);
}

static struct async_sem full, empty;

static async producer(struct async *pt) {
    static int produced;

    async_begin(pt);
    for (produced = 0; produced < NUM_ITEMS; ++produced) {
        await_sem(&full);

        add_to_buffer(produce_item());

        signal_sem(&empty);
    }
    async_end;
}

static async consumer(struct async *pt) {
    static int consumed;

    async_begin(pt);
    for (consumed = 0; consumed < NUM_ITEMS; ++consumed) {
        await_sem(&empty);
        consume_item(get_from_buffer());
        signal_sem(&full);
    }
    async_end;
}

static async driver_thread(struct async *pt) {
    static struct async cr_producer, cr_consumer;

    async_begin(pt);

    init_sem(&empty, 0);
    init_sem(&full, BUFSIZE);

    async_init(&cr_producer);
    async_init(&cr_consumer);

    await(producer(&cr_producer) & consumer(&cr_consumer));

    async_end;
}

int main(void) {
    struct async driver_pt;
    async_init(&driver_pt);

    while (!async_call(driver_thread, &driver_pt)) {
        usleep(10); /* why? */
    }
    return 0;
}

這段程式碼是經典的[生產者——消費者問題](https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem)，預期執行輸出為:

Item 0 produced
Item 0 added to buffer at place 0
Item 1 produced
Item 1 added to buffer at place 1
Item 2 produced
Item 2 added to buffer at place 2
Item 3 produced
Item 3 added to buffer at place 3
Item 4 produced
Item 4 added to buffer at place 4
Item 5 produced
Item 5 added to buffer at place 5
Item 6 produced
Item 6 added to buffer at place 6
Item 7 produced
Item 7 added to buffer at place 7
Item 0 retrieved from buffer at place 0
Item 0 consumed
Item 1 retrieved from buffer at place 1
Item 1 consumed
Item 2 retrieved from buffer at place 2
Item 2 consumed
Item 3 retrieved from buffer at place 3
Item 3 consumed
Item 4 retrieved from buffer at place 4
Item 4 consumed
Item 5 retrieved from buffer at place 5
Item 5 consumed
Item 6 retrieved from buffer at place 6
Item 6 consumed
Item 7 retrieved from buffer at place 7
Item 7 consumed

巨集展開後的程式碼:

int main(void) {
    struct async driver_pt;
    driver_pt._async_kcont = ASYNC_INIT;

    while (1) {
        if (driver_pt._async_kcont != ASYNC_DONE){
            driver_pt._async_kcont = driver_thread(&driver_pt);
            if (ASYNC_DONE == driver_pt._async_kcont) break;
        }
        else {
            break;
        }
        usleep(10);
    }
    return 0;
}

`async_call` 其實是一行條件運算式。由於 C 語言中，`||` 運算子會先執行左邊的 expression，若結果為 `false`，才執行右邊的 expression （若為 `true` 就不執行），又這個 `while` 迴圈只在 `async_call` 回傳 `0` (也就是 `||` 的兩個expression 都回傳 `0`）的情況下才會繼續執行，拆解完後可清楚知道這個 `while` 迴圈做了什麼：
* 首先檢查欲呼叫的函式是否已執行完畢，若是，直接跳出迴圈;
* 如果不是的話，則執行這個函式，並更新其狀態;
* 如果更新後發現函式已執行完畢，也跳出迴圈;
* 否則暫停 10 毫秒，然後重新執行上述步驟;

請補完程式碼

==作答區==

XXX1 = ?
* `(a)` `switch (k) {`
* `(b)` `switch ((k)->count) {`
* `(c)` `if (k) {`
* `(d)` `if ((k)->count) {`
* `(e)` `switch ((k)->_async_kcont) {`
* `(f)` `if ((k)->_async_kcont) {`

XXX2 = ?
* `(a)` `case 0:`
* `(b)` `/* empty */`

XXX3 = ?
* `(a)` `(s)->count++`
* `(b)` `(--s)->count`
* `(c)` `--(s)->count`

XXX4 = ?
* `(a)` `(s++)->count`
* `(b)` `(++s)->count`
* `(c)` `--(s)->count`
* `(d)` `++(s)->count`

:::success
延伸問題:
1. 解釋上述程式運作原理，特別是和 [Duff's device](https://en.wikipedia.org/wiki/Duff%27s_device) 的關聯;
2. 整合 timeout 機制，允許 callback function 在指定的時間執行，如 [TimerCallback callback function](https://docs.microsoft.com/en-us/previous-versions/windows/desktop/legacy/ms686790(v=vs.85))
:::

---