Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Thread-safe double linked list

399
26 августа 2016 года
KIV
432 / / 20.01.2009
Написал вот такую реализацию двунаправленного связанного списка на C++:
Код:
class List;

class ListItem {
    public:
        constexpr ListItem(): m_next(nullptr), m_prev(nullptr), m_list(nullptr) {
        }
       
        ~ListItem() {
            assert(m_list == nullptr);
        }
       
        bool remove();
       
        ListItem* next() const {
            return m_next;
        }
       
        List* list() const {
            return m_list;
        }
       
        bool inList() const {
            return list() != nullptr;
        }
       
        bool inList(List* l) const {
            return list() == l;
        }
       
    private:
        friend class List;
       
        ListItem* m_next;
       
        ListItem* m_prev;
       
        List* m_list;
       
};

class List {
    public:
        constexpr List(): m_head(nullptr), m_tail(nullptr), m_count(0) {
        }
       
        ~List() {
            assert(m_count == 0);
        }
       
        bool insertAfter(ListItem* item, ListItem* after);
       
        bool insertBefore(ListItem* item, ListItem* before);
       
        bool insertHead(ListItem* item) {
            return insertBefore(item, nullptr);
        }
       
        bool insertTail(ListItem* item) {
            return insertAfter(item, nullptr);
        }
       
        bool remove(ListItem* item) {
            if (item->m_list == this) {
                return item->remove();
            }
            return false;
        }
       
        ListItem* removeHead() {
            ListItem* item = m_head;
            if (item) {
                item->remove();
            }
            return item;
        }
       
        ListItem* removeTail() {
            ListItem* item = m_tail;
            if (item) {
                bool retval = item->remove();
                assert(retval);
            }
            return item;
        }
       
        ListItem* head() const {
            return m_head;
        }
       
        ListItem* tail() const {
            return m_tail;
        }
       
        unsigned int count() const {
            return m_count;
        }
       
        bool empty() const {
            return count() == 0;
        }
       
    private:
        friend class ListItem;
       
        ListItem* m_head;
       
        ListItem* m_tail;
       
        unsigned int m_count;
       
};

inline bool List::insertAfter(ListItem* item, ListItem* after) {
    assert(item != nullptr);
    if (after && (after->m_list != this)) {
        return false;
    }
    if (after) {
        item->m_prev = after;
        item->m_next = after->m_next;
        after->m_next = item;
        if (item->m_next) {
            item->m_next->m_prev = item;
        } else {
            m_tail = item;
        }
    } else {
        item->m_next = nullptr;
        item->m_prev = m_tail;
        if (item->m_prev) {
            item->m_prev->m_next = item;
        } else {
            m_head = item;
        }
        m_tail = item;
    }
    item->m_list = this;
    m_count++;
    return true;
}

inline bool List::insertBefore(ListItem* item, ListItem* before) {
    assert(item != nullptr);
    if (before && (before->m_list != this)) {
        return false;
    }
    if (before) {
        item->m_next = before;
        item->m_prev = before->m_prev;
        before->m_prev = item;
        if (item->m_prev) {
            item->m_prev->m_next = item;
        } else {
            m_head = item;
        }
    } else {
        item->m_prev = nullptr;
        item->m_next = m_head;
        if (item->m_next) {
            item->m_next->m_prev = item;
        } else {
            m_tail = item;
        }
        m_head = item;
    }
    item->m_list = this;
    m_count++;
    return true;
}

inline bool ListItem::remove() {
    List* list = m_list;
    if (list == nullptr) {
        return false;
    }
    if (m_next) {
        m_next->m_prev = m_prev;
    } else {
        list->m_tail = m_prev;
    }
    if (m_prev) {
        m_prev->m_next = m_next;
    } else {
        list->m_head = m_next;
    }
    list->m_count--;
    m_list = nullptr;
    return true;
}
Любую работу со списком произвожу только через публичные методы этих классов, любые операции добавления/удаления - перед вызовом метода захватываю pthread mutex, после вызова метода отпускаю его.

В итоге при многопоточной работе срабатывает assert(retval) в методе removeTail (при этом у списка m_count равен 1, m_head и m_tail указывают на этот элемент, а у самого элемента m_next и m_prev обнулены). То есть получается, что в списке оказывается элемент, у которого m_list == nullptr, хотя такого быть не должно, потому что обе функции добавления элемента присваивают ему правильное значение.

Что происходит? У меня ошибка в реализации алгоритма связанного списка (в однопоточных тестах вроде всё нормально)? Или для корректной работы недостаточного просто захватывать mutex?

Если что, любая модификация списка (вызовы insert и remove) происходят подобным образом:

 
Код:
pthread_mutex_lock(&my_mutex);
...
какие-то действия со списком ...
...
pthread_mutex_unlock(&my_mutex);
1
26 августа 2016 года
kot_
7.3K / / 20.01.2000
Для потокобезопасности необходимо сами модификаторы сделать атомарными. У вас этого нет, или я смотрел не внимательно.
Возможно поможет эта тема - http://stackoverflow.com/questions/11640681/thread...
399
26 августа 2016 года
KIV
432 / / 20.01.2009
Можно поконкретнее про атомарность операций? Списки используются в более сложных структурах данных, которые уже захватывают mutex. Я абсолютно уверен, что никто не вызывает функции добавления и удаления не схватив mutex. По ссылке я в основном увидел стилистические советы вроде создания специального объекта для захвата mutex (чтобы реализовать RAII). У меня все это есть, я просто не стал загромождать сообщение лишним кодом.

Или вы имеете ввиду, что я должен обернуть все поля этих классов в std::atomic?
1
27 августа 2016 года
kot_
7.3K / / 20.01.2000
Разумнее выполнять захват мьютекса (либо критические секции - не важно) выполнять в методе - именно это гарантирует потокобезопасность. Под атомарностью я понимаю гарантированное выполнение конкретного кода одним и только одним процессом от начала и до конца. Использовать ли для этго std::atomic - на ваше усмотрение
327
27 августа 2016 года
UserNet2008
748 / / 03.04.2010
mutex без контроля вторичново захвата в том же потоке
думаю надо смотреть в сторону
recursive_mutex
412
28 августа 2016 года
grgdvo
323 / / 04.07.2007
если операции атомарные, то вторичного захвата не должно быть по сути.
скорее всего ошибка где-то в других структурах данных, которые неверно испольуют List в многопоточном режиме.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог