Настольный теннис без блокировки в C11

Question

Я очень новичок в параллелизме в C и пытаюсь научиться понимать, как это работает.

Я хотел написать соответствующую реализацию пинг-понга без блокировки, т.е. один поток печатает пинг , после этого другой поток печатает понг и делает его блокирующим.свободно.Вот моя попытка сделать это:

#if ATOMIC_INT_LOCK_FREE != 2
    #error atomic int should be always lock-free
#else
    static _Atomic int flag;
#endif

static void *ping(void *ignored){
    while(1){
        int val = atomic_load_explicit(&flag, memory_order_acquire);
        if(val){
            printf("ping\n");
            atomic_store_explicit(&flag, !val, memory_order_release);
        }
    }
    return NULL;
}
static void *pong(void *ignored){
    while(1){
        int val = atomic_load_explicit(&flag, memory_order_acquire);
        if(!val){
            printf("pong\n");
            atomic_store_explicit(&flag, !val, memory_order_release);
        }
    }
    return NULL;
}

int main(int args, const char *argv[]){
    pthread_t pthread_ping;
    pthread_create(&pthread_ping, NULL, &ping, NULL);

    pthread_t pthread_pong;
    pthread_create(&pthread_pong, NULL, &pong, NULL);
}

Я проверял это несколько раз, и это работало, но есть вещи, которые кажутся странными:

1. Это либо блокировка -свободен или не компилируется

Поскольку Стандарт определяет свойство без блокировки равным 2, чтобы все операции с атомарным типом всегда были без блокировки.В частности, я проверил код компиляции, и он выглядит как

sub    $0x8,%rsp
nopl   0x0(%rax)
mov    0x20104e(%rip),%eax        # 0x20202c <flag>
test   %eax,%eax
je     0xfd8 <ping+8>
lea    0xd0(%rip),%rdi        # 0x10b9
callq  0xbc0 <puts@plt>
movl   $0x0,0x201034(%rip)        # 0x20202c <flag>
jmp    0xfd8 <ping+8>

Это выглядит нормально, и нам даже не нужно какое-то ограждение, поскольку Процессор Intel s не позволяет магазинам бытьпереупорядочено с более ранними нагрузками.Такие предположения работают только в том случае, если мы знаем аппаратную модель памяти, которая не является переносимой

Использование stdatomics с pthreads

Я застрял с glibc 2.27, где threads.h еще не реализовано.Вопрос в том, строго ли это сделать?В любом случае это странно, если у нас есть атомы, но нет потоков.Каково тогда правильное использование stdatomic s в многопоточном приложении?

Answer 1

Термин «без блокировки» имеет два значения:

1. значение для компьютерной науки: застревание одного потока не может препятствовать другим. Эту задачу невозможно сделать без блокировки, вам нужно потоков, чтобы ждать друг друга .(https://en.wikipedia.org/wiki/Non-blocking_algorithm)

2. с использованием атомной блокировки без блокировки. Вы в основном создаете свой собственный механизм для создания потокового блока, ожидая в неприятном цикле вращения без отступления, чтобы в конечном итоге освободить процессор.

Каждая отдельная стандартная операция загрузки и хранения отдельно не блокируется, но вы используете их для создания своего рода двухпотоковой блокировки.

---

Вашпопытка выглядит корректной для меня. Я не вижу, как поток может «пропустить» обновление, потому что другой поток не напишет другой, пока не завершится этот. И я не вижу пути для обоих потоковбыть в их критических секциях сразу.

Более интересный тест будет использовать разблокированные операции stdio, такие как
fputs_unlocked("ping\n", stdio);, чтобы использовать (и зависеть) тот факт, чтовы уже гарантировали взаимное исключение между потоками. См. unlocked_stdio (3) .

И тестирование с выводом, перенаправленным в файл, поэтому stdio полностью буферизуется, а не буферизируется строкой. (Aсистемавызов как write() в любом случае полностью сериализуется, например atomic_thread_fence(mo_seq_cst).)

---

Он либо без блокировки, либо не компилируется

Хорошо, почемутот странный?Вы решили сделать это.Это необязательно;алгоритм по-прежнему будет работать на реализациях C без постоянной блокировки atomic_int.

atomic_bool может быть лучшим выбором, будучи свободным от блокировки на большем количестве платформ, включая 8-битныеплатформы, где int принимает 2 регистра (потому что он должен быть не менее 16-битным).Реализации могут свободно делать atomic_bool 4-байтовым типом на платформах, где это более эффективно, но IDK, если таковые вообще есть.(На некоторых платформах, отличных от x86, загрузка / хранение байтов обходится дополнительным циклом задержки чтения / записи в кэш. Здесь это пренебрежимо мало, потому что вы всегда имеете дело с пропуском кеша между ядрами.)

ВыЯ думаю, atomic_flag будет правильным выбором для этого, но он обеспечивает только тестирование и настройку и очистку, как операции RMW. Не обычная загрузка или сохранение.

Такие предположения работают только в том случае, если мы знаем аппаратную модель памяти, которая не является переносной

Да, но этоas-code gen без препятствий генерируется только при компиляции для x86 .Компиляторы могут и должны применять правило as-if для создания asm, который выполняется на цели компиляции , как если бы источник C работал на абстрактной машине C.

---

Использование stdatomics с pthreads

Гарантирует ли стандарт ISO C, что поведение атома должно быть четко определено со всеми реализациями потоков (такими как pthreads, более ранние LinuxThreads и т. Д ...)

НетISO C ничего не говорит о таких расширениях языка, как POSIX.

В сноске (не нормативной) говорится, что атомы без блокировки должны быть безадресными, чтобы они работали между различными процессами, получающими доступта же общая память.(Или, может быть, эта сноска есть только в ISO C ++, я не пошел и не перепроверил).

Это единственный случай, когда я могу подумать, что ISO C или C ++ пытается предписывать поведение для расширений.

Но стандарт POSIX , мы надеемся, что-то говорит о stdatomic!Вот где вы должны смотреть;он расширяет ISO C, а не наоборот, поэтому стандарт pthreads должен указывать, что его потоки работают как C11 thread.h, а атомика работает.

На практике, конечно, stdatomicна 100% подходит для любой реализации потоков, где все потоки используют одно и то же виртуальное адресное пространство. Это включает в себя такие вещи без блокировки, как _Atomic my_large_struct foo;.