атомарная подкачка с CAS (использующий gcc синхронизируют builtins),

Операция может на самом деле не сохранить новое значение в месте назначения из-за гонки с другим потоком, который изменяет значение в тот же момент, когда вы пытаетесь это сделать. Примитив CAS не гарантирует, что запись происходит - только запись происходит, если значение уже соответствует ожидаемому. Примитив не может знать, каково правильное поведение, если значение не соответствует ожидаемому, поэтому в этом случае ничего не происходит - вам нужно решить проблему, проверив возвращаемое значение, чтобы увидеть, сработала ли операция.

Итак, ваш пример:

elem->next = __sync_val_compare_and_swap(&head, head, elem); //always inserts?

не обязательно вставлять новый элемент. Если другой поток вставляет элемент в тот же момент, возникает состояние гонки, которое может привести к тому, что вызов этого потока к __ sync_val_compare_and_swap () не обновит заголовок (но ни этот поток, ни другой поток элемент еще не утерян, если с ним правильно обращаться).

Но есть еще одна проблема с этой строкой кода - даже если head действительно обновлялся, есть короткий момент времени, когда head указывает на вставленный элемент, но этот элемент следующий указатель не обновлен, чтобы указывать на предыдущий заголовок списка. Если в этот момент налетает другой поток и пытается пройти по списку, происходят плохие вещи.

Чтобы правильно обновить список, измените эту строку кода на что-то вроде:

whatever_t* prev_head = NULL;
do {
    elem->next = head;  // set up `elem->head` so the list will still be linked 
                        // correctly the instant the element is inserted
    prev_head = __sync_val_compare_and_swap(&head, elem->next, elem);
} while (prev_head != elem->next);

Или используйте вариант bool , который, на мой взгляд, немного удобнее:

do {
    elem->next = head;  // set up `elem->head` so the list will still be linked 
                        // correctly the instant the element is inserted
} while (!__sync_bool_compare_and_swap(&head, elem->next, elem));

Это некрасиво, и Надеюсь, я правильно понял (легко запутаться в деталях поточно-безопасного кода).Он должен быть заключен в функцию insert_element () (или, что еще лучше, использовать соответствующую библиотеку).

Решение проблемы ABA:

Я не думаю, что проблема ABA имеет отношение к этому коду «добавить элемент в начало списка». Допустим, поток хочет добавить объект X в список, и когда он выполняет elem-> next = head , head имеет значение A1 .

Затем перед выполнением __ sync_val_compare_and_swap () появляется другой набор потоков и:

• удаляет A1 из списка, делая головную точку to B
• делает что-то с объектом A1 и освобождает его
• выделяет другой объект, A2 , который оказывается по тому же адресу, что и A1 было
• добавляет A2 в список, так что head теперь указывает на A2

Поскольку A1 и A2 имеют тот же идентификатор / адрес, это экземпляр проблемы ABA.

Однако в данном случае это не имеет значения, поскольку поток, добавляющий объект X , не заботится о том, что head указывает на другой объект, чем он был в начале - все его заботит то, что когда X поставлен в очередь:

• список согласован,
• ни один объект в списке не был потерян, и
• ни один объект, кроме X ] были добавлены в список (этой веткой)

Нет. Инструкция CAS на x86 берет значение из регистра и сравнивает/записывает его со значением в памяти.

Чтобы атомарно поменять местами две переменные, она должна работать с двумя операндами памяти.

Что касается того, может ли x меняться между &x и x? Да, конечно, может.

Даже без & она может измениться.

Даже в такой функции, как Foo(x, x), вы можете получить два разных значения x, поскольку для вызова функции компилятор должен:

• взять значение x и сохранить его в позиции первого параметра, согласно соглашению о вызове
• взять значение x и сохранить его в позиции второго параметра, согласно соглашению о вызове

между этими двумя операциями другой поток может легко изменить значение x.