KivApple
Newbie | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Допустим, есть однонаправленный кольцевой связанный список. Его голова хранится в head (описано как Item * volatile), указатель на следующий элемент хранится в Item::next (описано как Item * volatile). С добавлением элементов проблем не возникает, а вот с удалением есть проблема.
Код:
// item - элемент, который мы хотим удалить из списка
while (true) {
Item *prev = head;
if (prev == NULL) break;
while (prev->next != item) { // ***
prev = prev->next;
}
if (__sync_bool_compare_and_swap(&(prev->next), item, item->next)) {
if (__sync_bool_compare_and_swap(&(head), item, item->next)) {
__sync_bool_compare_and_swap(&(head), item, NULL);
}
break;
}
}
|
Запускаю тесты - несколько потоков параллельно пытаются много раз добавлять и удалять элементы из списка (элементы одни и те же и память под них выделена заранее, просто берётся рандомный элемент из набора, который ещё не добавили/уже удалили и с ним делается противоположное действие). В результате иногда имею зависания на цикле, помеченном звёздочкой (когда количество элементов достаточно мало, но больше одного).
Как можно это устранить?
Предполагаю, что проблема возникает, когда функция удаления прерывается другим потоком, который успевает полностью заменить содержимое списка. |
