目的: 檢驗學員對 C 語言流程控制的認知
1
延伸 C 語言: goto 和流程控制,考慮以下 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;
}
這段程式碼是經典的生產者——消費者問題,預期執行輸出為:
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
請補完程式碼
作答區
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
延伸問題:
解說錄影: Part 1 / Part 2 / Part 3 / Part 4 / Part 5/ Part 6 / Part 7
May 30, 2025許多文件、程式碼和技術討論會看到 lock-free 和 lockless 字眼,例如 DPDK Programmer’s Guide 就在一份文件中存在上述二個術語。二者的差異是什麼呢?
May 30, 2025「Linux 核心設計」課程期末專題清單
May 27, 20255.16.6
May 27, 2025or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up