# 2018q1 第 14 週測驗題
### 測驗 `1`
考慮以下 C 程式,實作多個 producer、單一 consumer 的 queue:
```C
#include <stdatomic.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <sys/types.h>
struct conq {
_Atomic size_t count, head;
size_t tail, max;
void *_Atomic *buffer;
int flags;
};
/* multi-producer, single consumer queue */
struct conq *conq_create(struct conq *n, size_t capacity) {
if (!n) {
n = calloc(1, sizeof(*n));
n->flags |= 1;
} else n->flags = 0;
n->count = ATOMIC_VAR_INIT(0); n->head = ATOMIC_VAR_INIT(0);
n->tail = 0; n->max = capacity;
n->buffer = calloc(capacity, sizeof(void *));
atomic_thread_fence(memory_order_release);
return n;
}
void conq_destroy(struct conq *q) {
free(q->buffer);
if (q->flags & 1)
free(q);
}
/* enqueue an item into the queue. Safe to call from multiple threads */
bool conq_enqueue(struct conq *q, void *obj) {
size_t count =
atomic_fetch_add_explicit(&q->count, 1, memory_order_acquire);
if (count >= q->max) {
/* back off, queue is full */
atomic_fetch_sub_explicit(&q->count, 1, memory_order_release);
return false;
}
/* increment the head, which gives us 'exclusive' access to that element */
size_t head = atomic_fetch_add_explicit(&q->head, 1, memory_order_acquire);
atomic_exchange_explicit(&q->buffer[TT1 % TT2], obj,
memory_order_release);
return true;
}
/* dequeue an item from the queue and return it */
void *conq_dequeue(struct conq *q) {
void *ret = atomic_exchange_explicit(&q->buffer[SS], NULL,
memory_order_acquire);
if (!ret) return NULL;
if (++q->tail >= q->max)
q->tail = 0;
atomic_fetch_sub_explicit(&q->count, 1, memory_order_release);
return ret;
}
size_t conq_count(struct conq *q) {
return atomic_load_explicit(&q->count, memory_order_relaxed);
}
size_t conq_capacity(struct conq *q) { return q->max; }
```
請補完以上程式碼。
==作答區==
TT1 = ?
* `(a)` count
* `(b)` head
* `(c)` q->max
* `(d)` q->head
* `(e)` q->flags
*
TT2 = ?
* `(a)` count
* `(b)` head
* `(c)` q->max
* `(d)` q->head
* `(e)` q->flags
*
SS = ?
* `(a)` q->tail
* `(b)` q->head
* `(c)` q->max
* `(d)` q->flags
:::info
延伸題目: 重現 [waitfree-mpsc-queue](https://github.com/dbittman/waitfree-mpsc-queue) 實驗,分析 lock 和 waitfree 實作的效能並充分解讀運作機制
:::