Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
KivApple
0 / 0 / 0
Регистрация: 04.01.2016
Сообщений: 2
1

Lock-free добавление и удаление в односвязный кольцевой список

06.01.2016, 03:42. Просмотров 298. Ответов 0
Метки нет (Все метки)

Я реализовал lock-free добавление и удаление в односвязный кольцевой список:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#define CAS(var, oldValue, newValue) __sync_bool_compare_and_swap(&(var), oldValue, newValue)
 
typedef struct Item Item;
struct Item {
    Item * volatile next;
    ...
};
 
Item * volatile head = NULL;
 
void addToList(Item *item) {
    while (true) {
        item->next = listHead;
        if (item->next == NULL) {
            item->next = item;
            if (CAS(listHead, NULL, item)) {
                break;
            }
        } else {
            if (CAS(listHead, item->next, item)) {
                break;
            }
        }
    }
}
 
void removeFromList(Item *item) {
    while (true) {
        Item *prev = listHead;
        while (prev->next != item) {
            prev = prev->next;
        }
        if (CAS(prev->next, item, item->next)) {
                if (CAS(head, item, item->next)) {
                    CAS(head, item, NULL);
                }
                break;
            }
        }
    }
}
Я не уверен, что этот код полностью thread-safe. Особенно беспокоит функция удаления (цикл поиска prev). Помогите разобраться, пожалуйста.
P.S.: Вопрос освобождения памяти после удаления элемента меня сейчас не интересует. У меня есть возможность убедиться, что элемент больше никто не попытается добавить в список перед его уничтожением.

Добавлено через 10 часов 56 минут
Произвёл некоторую модернизацию кода. Сейчас ситуация такова. Добавление элемента полностью lock-free. Удаление - нет. Если использовать mutex (только один поток может вызвать в один момент времени удаление элемента, при этом другие потоки могут в этот момент добавлять элементы как угодно), то всё отлично работает. Если попытаться использовать и удаление lock free, то программа падает на assert(head != item) в функции добавления (что по сути означает нарушение целостности данных - голова списка указывает на элемент, которого в списке не должно быть ещё). Обратное действие (mutex для добавления и lock-free удаление) проблему не убирает.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#define CAS(var, oldValue, newValue) __sync_bool_compare_and_swap(&(var), oldValue, newValue)
 
typedef struct ListItem;
struct ListItem {
    ListItem * volatile next;
    bool locked;
    bool removed;
};
 
typedef struct List {
    ListItem * volatile head;
    ListItem * volatile current;
} List;
 
List list;
 
void insertListItem(ListItem *item) {
    if (!CAS(item->locked, false, true)) return;
    if (item->removed == true) {
        item->removed = false;
        while (true) {
            ListItem *head = list.head;
            assert(item != head); // Во время многопоточных тестов иногда срабатывает этот assert, без него получался циклический список и зависала функция удаления.
            item->next = head;
            if (CAS(list.head, item->next, item)) {
                break;
            }
        }
    }
    item->locked = false;
}
 
void removeFromList(ListItem *item) {
    if (!CAS(item->locked, false, true)) return;
    if (item->removed == false) {
        while (true) {
            ListItem *prev = (ListItem*)(&(list.head)); // next - первое поле структуры ListItem, так что мы имеем право так сделать.
            while (prev->next != item) {
                prev = prev->next;
            }
            if (CAS(prev->next, item, item->next)) {
                break;
            }
        }
        item->removed = true;
    }
    item->locked = false;
}
Как исправить функцию удаления, чтобы она стала тоже lock-free?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.01.2016, 03:42
Ответы с готовыми решениями:

Из введенных слов создать односвязный кольцевой список
Доброй ночи Задача звучит так: Из введенных слов создать односвязный кольцевой список. Далее,...

Создать кольцевой односвязный список, элементы которого будут вводиться с клавиатуры
Нужно сделать кольцевой односвязный список, элементы которого будут вводиться с клавиатуры. Я...

Двусвязный кольцевой список. Удаление по критерию
И снова здравствуйте! Нашла тут удаление для односвязного кольцевого. А у меня двусвязный...

Односвязный список: удаление элементов,заканчивающихся на 5
Есть вот такая задача: Создать список из случайных целых чисел и удалить элементы, заканчивающиеся...

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

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.01.2016, 03:42

Вывести на экран в символическом виде состояние NUM LOCK, CAPS LOCK и SCROLL LOCK
Помогите решить задачку на турбо си Выводить на экран в символическом виде состояние NUM LOCK,...

Односвязный список. Добавление и удаление в строку
Здравствуйте, есть задача. Дана строка, если в ней встречается '*', то нужно удвоить ее, если...

Создать односвязный список типа стек, произвести удаление и добавление элемента
Создать односвязный список типа стек. Заменить последний элемент на другой вводимый с ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru