VPF::C++0X atomic - Форум программистов

Леопольд

Дата 28.11.2010, 00:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

http://cppjournal.blogspot.com/
Здесь есть статья про lock_free программирование. Для асинхронного удаления элемента используются весьма сложные конструкции. Я вижу решение таким. Довольно просто, и эффективно. Но, может bыть я что-то недопонимаю, и на самом деле здесь bаги?
неbольшой тест LWS

Код

#include <atomic>
#include <memory>

template <typename T>
class stack
{
private:
    struct node
    {
        node * next;
        std::unique_ptr<T> data;

        node(const T& d, node* n = 0)
            :next(n), data(new T(d)) {}

        node() : next(&stack<T>::end), data(std::unique_ptr<T>()) {}

        node(node const&) = delete;
        node & operator=(node const&) = delete;
    };

    std::atomic<node *> m_head;
    std::atomic_uint m_size;
    static node end;

public:
    void push(const T& data)
    {
        node* new_node = new node(data, m_head.load());
        while (!m_head.compare_exchange_weak(
            new_node->next,
            new_node));

        ++m_size;
    }

    std::unique_ptr<T> pop()
    {
        node* old_head=m_head.load();
        while (!m_head.compare_exchange_weak(
            old_head,
            old_head->next));

        if(old_head != &end )
        {
            --m_size;
            auto ret = move(old_head->data);
            delete old_head;
            return move(ret);
        }
        return std::unique_ptr<T>();
    }

    std::size_t size() {return m_size;}

    stack() : m_head(&end), m_size(0) {}
};

template <typename T>
typename stack<T>::node stack<T>::end;

Это сообщение отредактировал(а) Леопольд - 28.11.2010, 01:22

--------------------

вопросов больше чем ответов

Леопольд

Дата 28.11.2010, 01:53 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Вроде bы раbотает, даже если сперва запустить потоки, которые выкидывают элементы из стека...

Код

#include <iostream>
#include <future>

stack<char> s;
enum { elemQuantity = 1000000 };
void push()
{
    for(std::size_t i = 0; i < elemQuantity; ++i)
        s.push(0);
}
void pop()
{
    auto tr = std::async(std::launch::async, push);

    for(std::size_t i = 0; i < elemQuantity; ++i)
        s.pop();

    tr.wait();

}


int main()
{
    auto tr1 = std::async(std::launch::async, pop);
    auto tr2 = std::async(std::launch::async, pop);

    tr1.wait();
    tr2.wait();

    std::cout << "s.size() = " << s.size() << std::endl;

    return 0;
}

http://liveworkspace.org/code/394a8b9144ffe5cb97781cc55598cdb9

Это сообщение отредактировал(а) Леопольд - 28.11.2010, 01:56

--------------------

вопросов больше чем ответов

boostcoder

Дата 28.11.2010, 04:01 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(Леопольд @ 28.11.2010, 00:47

)

http://cppjournal.blogspot.com/
Здесь есть статья про lock_free программирование

там их несколько. о какой именно идет речь?
второе - есть либа relacy. о ней тоже говорится в третьей статье.

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

azesmcar

Дата 28.11.2010, 07:00 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

Леопольд

Ну для начала скажу, что тут есть проблемы не только с очисткой памяти, здесь не предусмотрен pop() на пустом стеке.
Что касается проблемы очистки памяти, опишу ситуацию.
В стеке 10 элементов, 2 потока одновременно выполняют pop().

Код


std::unique_ptr<T> pop()
{
    node* old_head=m_head.load();
    while (!m_head.compare_exchange_weak(old_head, old_head->next));
    if(old_head != &end )
    {
        --m_size;
        auto ret = move(old_head->data);
        delete old_head;
        return move(ret);
    }
    return std::unique_ptr<T>();
}

1 поток выполняет все строчки до 4-ой. Выполняет конструкцию
while (!m_head.compare_exchange_weak(old_head, old_head->next));
compare_exchange_weak возвращает false, т.е. ожидается еще одна итерация и поток передает управеление другому потоку
2 поток входит в pop(), выполняет все действия, удаляет head (так-как old_head != &end), возвращает значение и передает управление 1-ому потоку.
1 поток пытается выполнить еще одну итерацию в цикле while (!m_head.compare_exchange_weak(old_head, old_head->next));
но old_head указывает на удаленную область памяти и old_head->next - обращение к ней, что ведет за собой неопределенное поведение.

И еще .. пользя от функции size() здесь довольно сомнительная. По сути она возвращает программисту размер, который когда-то точно был размером этого стека, не более. smile

Это сообщение отредактировал(а) azesmcar - 28.11.2010, 07:04

boostcoder

Дата 28.11.2010, 07:03 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(azesmcar @ 28.11.2010, 07:00

)

она возвращает программисту размер, который когда-то точно был размером этого стека, не более.

забавно-то как smile

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

azesmcar

Дата 28.11.2010, 07:50 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

Отвлекся..вернемся к делу

Цитата(Леопольд @ 28.11.2010, 00:47

)

неbольшой тест LWS

http://liveworkspace.org/code/b6e8617b670b...85227a2cb07ea49
всего лишь несколько последовательных запусков и...
вообще непонятен смысл этой статической переменной, в ее роли мог бы выступать 0, и не надо было бы проверять при удалении.

boostcoder

Ну разве что для логирования может сгодиться, другого применения я не вижу smile

Цитата(Леопольд @ 28.11.2010, 01:53

)

Вроде bы раbотает, даже если сперва запустить потоки, которые выкидывают элементы из стека...

Такой тест придется запускать ни один раз, чтобы проверить работоспособность. Лучше использовать

Цитата(boostcoder @ 28.11.2010, 04:01

)

relacy

правда придется немного модифицировать код, но эта жертва, на которую стоит пойти smile

Это сообщение отредактировал(а) azesmcar - 28.11.2010, 07:56

Леопольд

Дата 28.11.2010, 09:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Цитата(azesmcar @ 28.11.2010, 07:00

)

И еще .. пользя от функции size() здесь довольно сомнительная.

Это "для сеbя", надо разоbраться с relacy, а это время.

Цитата(azesmcar @ 28.11.2010, 07:00

)

на удаленную область памяти и old_head->next - обращение к ней, что ведет за собой неопределенное поведение.

Так и знал, что что-то упустил. Спасиbо!

Цитата(azesmcar @ 28.11.2010, 07:00

)

Ну для начала скажу, что тут есть проблемы не только с очисткой памяти, здесь не предусмотрен pop() на пустом стеке. ... вообще непонятен смысл этой статической переменной, в ее роли мог бы выступать 0, и не надо было бы проверять при удалении.

Для этого end и нужна. Она зацикливает конец списка на сеbя.

Это сообщение отредактировал(а) Леопольд - 28.11.2010, 11:50

--------------------

вопросов больше чем ответов

Леопольд

Дата 28.11.2010, 09:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Цитата(boostcoder @ 28.11.2010, 07:03

)

забавно-то как smile

Полегчало?

Лучший спосоb разоbраться - сделать свой, возможно уbогий, вариант.

Это сообщение отредактировал(а) Леопольд - 28.11.2010, 10:23

--------------------

вопросов больше чем ответов

azesmcar

Дата 28.11.2010, 10:05 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

Цитата(Леопольд @ 28.11.2010, 09:37

)

Для этого end и нужна. Она зацикливает конец списка на сеbя.

Да, не заметил

Цитата(Леопольд @ 28.11.2010, 00:47

)

next(&stack<T>::end)

Цитата(Леопольд @ 28.11.2010, 09:37

)

Так и знал, что что-то упустил. Спасиbо!

Пожалуйста.

Леопольд

Дата 28.11.2010, 14:55 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

поbорол при помощи статического указателя (только это уже не lock_free, а wait_free):

Код

#include <cassert>
#include <atomic>
#include <memory>

template <typename T>
class stack
{
private:
    struct node
    {
        node * next;
        std::unique_ptr<T> data;

        node(const T& d, node* n = 0)
            :next(n), data(new T(d)) {}

        node() : next(0), data(std::unique_ptr<T>()) {}

        node(node const&) = delete;
        node & operator=(node const&) = delete;
    };

    std::atomic<node *> m_head;
    static node pend;

public:
    void push(const T& data)
    {
        node* new_node = new node(data, 0);

        node * head = m_head.exchange(&pend);
        while(head == &pend)
        {
            head = m_head.exchange(&pend);
        }
        new_node->next = head;

        m_head.store(new_node);
    }

    std::unique_ptr<T> pop()
    {
        node * head = m_head.exchange(&pend);
        while(head == &pend)
        {
            head = m_head.exchange(&pend);
        }
        if(head)
        {
            m_head.store(head->next);
            auto ret = move(head->data);
            delete head;
            return move(ret);
        }
        m_head.store(0);
        return std::unique_ptr<T>();
    }
    stack() : m_head(0) {}
};
template <typename T>
typename stack<T>::node stack<T>::pend;

Недостаток, много раbоты в холостую (spin lock). Достоинство, простота реализации. Теперь пора вторую статью читать. smile

Рельна ли ситуация, когда поток подменил указатель и внезапно умер, не завершив раbоту? Если да, то bудет deadlock.

Это сообщение отредактировал(а) Леопольд - 28.11.2010, 23:00

--------------------

вопросов больше чем ответов

azesmcar

Дата 28.11.2010, 16:31 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

А в чем замысел? Почему compare_exchange заменен на if и exchange?
Вообще комментарии бы не помешали, не знаю будет работать или нет, детально не смотрел, но насколько я понял

Цитата(Леопольд @ 28.11.2010, 14:55

)

много раbоты в холостую.

и эта работа в холостую по сути лишает преимущества перед блокировками.

Цитата(Леопольд @ 28.11.2010, 14:55

)

Если да, то bудет deadlock.

дедлока тут по определению быть не может. Дедлок может возникнуть только при блокировании, а тут нет блокирования.

Это сообщение отредактировал(а) azesmcar - 30.11.2010, 10:49

Леопольд

Дата 28.11.2010, 17:14 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Цитата(azesmcar @ 28.11.2010, 16:31

)

А в чем замысел? Почему compare_exchange заменен на if и exchange?

Когда смотришь с уровня новичка, всё выглядит весьма запутанно. Пытаюсь распутать. Здесь получился spin lock.
compare_exchange сложнее читать, он неинтуитивно записывает новое значение атомарной переменной по ссылке в первый аргумент.

Это сообщение отредактировал(а) Леопольд - 28.11.2010, 17:37

--------------------

вопросов больше чем ответов

azesmcar

Дата 28.11.2010, 17:20 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

Цитата(Леопольд @ 28.11.2010, 17:14

)

Здесь получился spin lock.

spin lock - тоже lock, но в user-mode и никак не может быть wait-free.
wait-free функция означает, что любой поток, начавший выполнять эту функцию закончит выполнение за N-ое количество шагов, и N никак не зависит от других потоков.

Цитата(Леопольд @ 28.11.2010, 17:14

)

Когда смотришь с уровня новичка, всё выглядит весьма запутанно. Пытаюсь распутать.

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

Это сообщение отредактировал(а) azesmcar - 28.11.2010, 17:22

Леопольд

Дата 28.11.2010, 17:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Цитата(azesmcar @ 28.11.2010, 16:31

)

и эта работа в холостую по сути лишает преимущества перед блокировками.

Вроде как не совсем. Нет переключения контекста, но тоже есть куча минусов.

Цитата(azesmcar @ 28.11.2010, 17:20

)

могу подкинуть литературу, но только на английском.

Не откажусь от ссылок на признанных авторов в данной теме. Спасиbо! Английский даже лучше, иногда перевод тяжелее понять.

Добавлено @ 17:35

Цитата(azesmcar @ 28.11.2010, 17:20

)

и никак не может быть wait-free.

Цитата

Терминология
Lock-free – lock-free считается та процедура, для которой гарантируется прогресс как минимум одного потока, выполняющего эту процедуру. Другие потоки могут ждать, но один поток минимум должен прогрессировать.

Wait-free – операция называется wait-free в том случае, если она завершается за определенное количество шагов, не зависящих от состояние и действий других потоков.

Действительно, показалось что по смыслу подходит, только перепутал одно с другим...

Это сообщение отредактировал(а) Леопольд - 28.11.2010, 18:07

--------------------

вопросов больше чем ответов

Леопольд

Дата 28.11.2010, 18:24 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Цитата(azesmcar @ 28.11.2010, 17:20

)

spin lock - тоже lock

Получается, что compare_exchange тот же spin lock.

--------------------

вопросов больше чем ответов

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »