Атомарные операции над списком
Предположим, у меня есть список, и я хочу использовать test_and_set операция, параметром которой является вычисление некоторого адреса указателя l->a.next->next, Это, я думаю, не будет атомным, и test_and_set будет бесполезным. Есть ли способ рассчитать это значение указателя атомарно, чтобы TAS работал атомарно?
1 ответ
Вы, вероятно, имеете в виду CAS (более полезный).
В целом: да, он часто используется для реализации транзакционных или бесперебойных структур данных,
Сначала обо всем по порядку: давайте отделим вычисления адреса от атомарных операций над адресом, сначала вы получите конкретный адрес, по которому нужно что-то поменять, CAS не волнует, как вы туда попали.
В частности, вы должны сначала позволить каждому из ваших потоков перемещаться по списку, пока они не найдут место, где они хотят заменить следующий указатель, а затем они могут попытаться повторить это с помощью CAS. Это зависит от вашего сценария, должен ли поток повторно просмотреть список для повторной попытки.
Сложная часть на самом деле находится в другом месте кода: где вы освобождаете (или повторно используете) списки-узлы. В общем, вы должны предположить, что вы не можете повторно использовать или освобождать цепочки узлов, которые были отключены от вашего списка никогда. На практике есть эвристики, которые вы можете использовать, но это зависит от вашего варианта использования.