2018q1 第 14 週測驗題

測驗 `1`

考慮以下 C 程式，實作多個 producer、單一 consumer 的 queue:

#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

延伸題目: 重現 waitfree-mpsc-queue 實驗，分析 lock 和 waitfree 實作的效能並充分解讀運作機制

2018q1 第 14 週測驗題

測驗 1

測驗 `1`