#c #multithreading #containers #atomic #lock-free
Вопрос:
Я прочитал статью «Правильное и эффективное воровство работы для моделей со слабой памятью», в которой авторы приводят этот код:
int take(Deque *q) {
size_t b = load_explicit(amp;q->bottom, relaxed) - 1;
Array *a = load_explicit(amp;q->array, relaxed);
store_explicit(amp;q->bottom, b, relaxed);
thread_fence(seq_cst);
size_t t = load_explicit(amp;q->top, relaxed);
int x;
if (t <= b) {
/* Non-empty queue. */
x = load_explicit(amp;a->buffer[b % a->size], relaxed);
if (t == b) {
/* Single last element in queue. */
if (!compare_exchange_strong_explicit(amp;q->top, amp;t, t 1, seq_cst, relaxed))
/* Failed race. */
x = EMPTY;
store_explicit(amp;q->bottom, b 1, relaxed);
}
} else { /* Empty queue. */
x = EMPTY;
store_explicit(amp;q->bottom, b 1, relaxed);
}
return x;
}
void push(Deque *q, int x) {
size_t b = load_explicit(amp;q->bottom, relaxed);
size_t t = load_explicit(amp;q->top, acquire);
Array *a = load_explicit(amp;q->array, relaxed);
if (b - t > a->size - 1) { /* Full queue. */
resize(q);
a = load_explicit(amp;q->array, relaxed);
}
store_explicit(amp;a->buffer[b % a->size], x, relaxed);
thread_fence(release);
store_explicit(amp;q->bottom, b 1, relaxed);
}
int steal(Deque *q) {
size_t t = load_explicit(amp;q->top, acquire);
thread_fence(seq_cst);
size_t b = load_explicit(amp;q->bottom, acquire);
int x = EMPTY;
if (t < b) {
/* Non-empty queue. */
Array *a = load_explicit(amp;q->array, consume);
x = load_explicit(amp;a->buffer[t % a->size], relaxed);
if (!compare_exchange_strong_explicit(amp;q->top, amp;t, t 1, seq_cst, relaxed))
/* Failed race. */
return ABORT;
}
return x;
}
Как мы видим, при краже они используют seq_cst
забор. Кроме того, они используют этот забор в своей работе. У меня есть два вопроса:
- Зачем нам нужен этот забор в операциях кражи: можете ли вы объяснить какой-нибудь пошаговый пример ситуации, в которой без этого забора в краже мы можем получить неопределенное поведение или состояние гонки?
- Почему мы не можем заменить этот забор в операции взятия, просто выполнив операцию сохранения памяти (или ограждения) (в нижнюю переменную, она же
b
)?