Операция может не сохранять новое значение в месте назначения из-за гонки с другим потоком, который изменяет значение в тот же момент, когда вы пытаетесь. Примитив CAS не гарантирует, что запись происходит - только то, что запись происходит, если значение уже соответствует ожидаемому. Примитив не может знать, каково правильное поведение, если значение не соответствует ожидаемому, поэтому в этом случае ничего не происходит - вам нужно исправить проблему, проверив возвращаемое значение, чтобы проверить, сработала ли операция.
Итак, ваш пример:
elem->next = __sync_val_compare_and_swap(&head, head, elem); //always inserts?
не обязательно будет вставлять новый элемент. Если другой поток вставляет элемент в тот же момент, существует условие гонки, которое может привести к тому, что вызов этого потока к __sync_val_compare_and_swap() не обновит head (но ни элемент этого потока, ни элемент другого потока еще не потерян, если вы обрабатываете его правильно) ,
Но есть еще одна проблема с этой строкой кода - даже если head действительно обновился, есть короткий момент времени, когда head указывает на вставленный элемент, но указатель next этого элемента не был обновлен, чтобы указывать на предыдущий заголовок списка. Если другой поток подключается в этот момент и пытается просмотреть список, происходят плохие вещи.
Чтобы правильно обновить список, измените эту строку кода на что-то вроде:
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 из списка, head указывает на B
- делает что-либо с объектом
A1 и освобождает его
- выделяет другой объект,
A2, который находится по тому же адресу, что и A1 был
- добавляет
A2 в список, так что head теперь указывает на A2
Поскольку A1 и A2 имеют одинаковый идентификатор / адрес, это является примером проблемы ABA.
Однако в данном случае это не имеет значения, поскольку поток, добавляющий объект X, не заботится о том, чтобы head указывал на объект, отличный от того, с которого он начинал - все, о чем он заботится, это когда X в очереди:
- список согласован,
- объекты в списке не были потеряны, а
- никаких объектов, кроме
X, не было добавлено в список (по этой теме)