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

azesmcar

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

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

Загрузка ...

uploading...

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

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

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

)

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

Завтра пришлю.

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

)

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

Нет, spin-lock - пустая итерация в ожидании, пока другой поток не изменит состояния некой переменной, т.е. это блокировка, mutex работает точно также, просто ожидание не тратит процессорных ресурсов, а compare_exchange ничего не блокирует, он атомарно производит некое действие, никакой другой поток не дожидается его завершения, чтобы продолжить свою работу.

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

mes

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

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

Загрузка ...

любитель

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

Репутация: 144
Всего: 250

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

)

Завтра пришлю.

если в личку, просьба и мне выслать smile

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

http://opendots.net

azesmcar

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

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

Загрузка ...

uploading...

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

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

Цитата(mes @ 28.11.2010, 21:04

)

если в личку, просьба и мне выслать

выложу сюда smile

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

Леопольд

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

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

Загрузка ...

Опытный

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

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

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

)

compare_exchange ничего не блокирует

Я, конечно, имел ввиду в цикле. Если, груbо говоря, 300 процессов bудут постоянно менять переменную, кто-то из них может начать голодать.
Здесь за флажок принимается не какое-то, заранее определённое значение, а смена значения. Если не изменилось, то поменять, но только один процесс сможет это сделать. Остальные, перейдут на следующую итерацию.

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

)

spin-lock - пустая итерация в ожидании, пока другой поток не изменит состояния некой переменной

Т.е., наверное, можно сказать, что это spin lock наоbорот - пустая итерация (а может и не пустая) в ожидании, пока другие, bолее удачливые потоки не перестанут изменять состояние переменной.

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

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

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

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

azesmcar

Дата 29.11.2010, 08:23 (ссылка)

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

Загрузка ...

uploading...

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

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

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

)

Я, конечно, имел ввиду в цикле. Если, груbо говоря, 300 процессов bудут постоянно менять переменную, кто-то из них может начать голодать.

Это не делает из любой итерации блокировку. Эта итерация не блокирует другие потоки, как это делает spin lock, но количество итераций все таки зависит от того, что делают другие потоки, потому эта функция не wait-free.

Статьи
эта статья на русском, не помешает ознакомиться
Что такое модель памяти?
немного википедии
http://en.wikipedia.org/wiki/Non-blocking_algorithm
и далее все на языке Шекспира
Herb Sutter - Lock-Free Code: A False Sense of Security
Andrei Alexandrescu - Lock-Free Data Structures
Andrei Alexandrescu, Maged Michael - Lock-Free Data Structures with Hazard Pointers
Thomas Edward Hart Thesis
Maged Michael - Hazard Pointers
Herb Sutter - A Principle-Based Sequential Memory Model for Microsoft Native Code Platforms
Geoff Langdale - Lock-Free programming
ABA problem

Это сообщение отредактировал(а) azesmcar - 29.11.2010, 08:43

Леопольд

Дата 29.11.2010, 09:25 (ссылка)

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

Загрузка ...

Опытный

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

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

azesmcar, премного благодарен!

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

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

Леопольд

Дата 30.11.2010, 09:57 (ссылка)

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

Загрузка ...

Опытный

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

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

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

)

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

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

)

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

Бывает такой бред пишу... smile

На spin lock'е при вытесняющей (preemptive) многозадачности, очень легко dead lock получить. Когда процесс с более низким приоритетом был прерван сразу после того, как он сделал spin lock. В lock free это невозможная ситуация.

Это сообщение отредактировал(а) Леопольд - 30.11.2010, 09:59

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

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

azesmcar

Дата 30.11.2010, 09:59 (ссылка)

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

Загрузка ...

uploading...

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

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

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

)

На spin lock'е при вытесняющей (preemptive) многозадачности, очень легко dead lock получить

это называется live-lock.

Добавлено через 34 секунды
deadlock не тратит процессорные ресурсы.

Леопольд

Дата 30.11.2010, 10:02 (ссылка)

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

Загрузка ...

Опытный

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

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

azesmcar, ясно, спасибо.

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

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

Леопольд

Дата 30.11.2010, 22:59 (ссылка)

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

Загрузка ...

Опытный

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

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

deleted

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

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

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

Леопольд

Дата 1.12.2010, 10:48 (ссылка)

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

Загрузка ...

Опытный

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

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

Не могу скачать relacy...

Цитата

Страницы, на которую Вы переходите, не существует.

Надеялся она мне поможет понять почему это не работает. Пытаюсь написать вариант с очередью на удаление (end зациклен на себя):

Код

#include <atomic>
#include <memory>

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

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

        node(node * n) :next(n), data(std::shared_ptr<T>()) {}

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

    std::atomic<node *> m_head;
    std::atomic<node *> m_deleted_head;
    std::atomic<std::size_t> m_active_threads;

    static node end;

public:
    stack() : m_head(&end), m_deleted_head(&end), m_active_threads(0) {}

    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));
    }


    std::shared_ptr<T> pop()
    {
        ++m_active_threads;

        node * head = m_head.load();
        while(!m_head.compare_exchange_weak(head, head->next));

        std::shared_ptr<T> ret(head->data);

        if(head == &end)
        {
            --m_active_threads;
            return ret;
        }

        node * deleted_head = m_deleted_head.load();
        //check for solo thread
        if(!--m_active_threads)
        {
            //if m_deleted_head has not been changed then no threads use nodes from the queue
            if(m_deleted_head.compare_exchange_strong(deleted_head, &end))
            {
                head->next = deleted_head;
                while(head != &end)
                {
                    auto next = head->next;
                    delete head;
                    head = next;
                }
            }
        }
        //in other case just push the node to the deleted list
        else
        {
            head->next = m_deleted_head.load();
            while(!m_deleted_head.compare_exchange_weak(head->next, head));
        }

        return ret;
    }
};

template <typename T>
typename stack<T>::node stack<T>::end(&stack<T>::end);

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

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

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

azesmcar

Дата 1.12.2010, 11:06 (ссылка)

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

Загрузка ...

uploading...

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

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

Цитата(Леопольд @ 1.12.2010, 10:48

)

Не могу скачать relacy...

На гугле запретили выкладывать zip файлы.
Качать надо отсюда, добавлю в статью.
http://sites.google.com/site/1024cores/downloads

Леопольд

Дата 1.12.2010, 11:08 (ссылка)

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

Загрузка ...

Опытный

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

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

azesmcar, спасибо!

Так вроде работает, теперь надо с relacy попробовать протестить.

Код


        //check for solo thread
        if(m_active_threads.load() == 1)
        {
            //if m_deleted_head has not been changed theт no threads use nodes from the queue
            if(!--m_active_threads && m_deleted_head.compare_exchange_strong(deleted_head, &end))
            {
                head->next = deleted_head;
                while(head != &end)
                {
                    auto next = head->next;
                    delete head;
                    head = next;
                }
            }
        }

Не, нифига, здесь утечка памяти...

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

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

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

Леопольд

Дата 1.12.2010, 22:57 (ссылка)

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

Загрузка ...

Опытный

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

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

relacy не помог... smile

http://liveworkspace.org/code/8ed457a04766...847bee388deb79b

Код

#include <memory>

#include <cstdio>
#include <relacy/relacy_std.hpp>

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

        node(const T& d, node* n) :next(n), data(std::make_shared<T>(d)) {}
        node(node* n) :next(n), data(std::shared_ptr<T>()) {}

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

    std::atomic<node *> m_head;
    std::atomic<node *> m_deleted_head;
    std::atomic<std::size_t> m_active_threads;

    static node end;

public:
    concurent_stack() : m_head(&end), m_deleted_head(&end), m_active_threads(0) {}

    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));
    }


    std::shared_ptr<T> pop()
    {
        m_active_threads($).fetch_add(1);

        node * head = m_head($).load();
        while(!m_head($).compare_exchange_strong(head, head->next));

        node * deleted_head = m_deleted_head($).load();
        if(m_active_threads($).fetch_sub(1) - 1 == 0 && m_deleted_head($).compare_exchange_strong(deleted_head, &end))
        {
            std::shared_ptr<T> ret;

            if(head == &end)
            {
                head = deleted_head;
            }
            else
            {
                head->data.swap(ret);
                head->next = deleted_head;
            }

            while(head != &end)
            {
                node * next = head->next;
                delete head;
                head = next;
            }

            return ret;
        }

        if(head != &end)
        {
            std::shared_ptr<T> ret;
            head->data.swap(ret);

            head->next = m_deleted_head($).load();
            while(!m_deleted_head($).compare_exchange_weak(head->next, head));

            return ret;
        }

        return head->data;
    }

    ~concurent_stack()
    {
        node * head = m_head($).load();
        while(head != &end)
        {
            node * next = head->next;
            delete head;
            head = next;
        }

        head = m_deleted_head($).load();
        while(head != &end)
        {
            node * next = head->next;
            delete head;
            head = next;
        }
    }
};
template <typename T>
typename concurent_stack<T>::node concurent_stack<T>::end(&concurent_stack<T>::end);



unsigned const thread_count = 4;
unsigned nodes_count = 100000;

struct stack_test : rl::test_suite<stack_test, thread_count>
{
    stack_test() {}

    concurent_stack<char> * stack;

    // executed in single thread before main thread function
    void before()
    {
        stack = new concurent_stack<char>();
    }

    // main thread function
    void thread(unsigned index)
    {
        if(index % 2)
        {
            for(std::size_t i = 0; i < nodes_count; ++i)
                stack->push(i);
        }
        else
        {
            for(std::size_t i = 0; i < nodes_count; ++i)
                stack->pop();
        }
    }

    // executed in single thread after main thread function
    void after()
    {
        delete stack;
    }

    // executed in single thread after every 'visible' action in main threads
    // disallowed to modify any state
    void invariant()
    {
    }
};


#include <boost/lexical_cast.hpp>

int main(int argc, char * argv[])
{
    if(argc > 1)
    {
        nodes_count = boost::lexical_cast<std::size_t>(argv[1]);
    }

    rl::test_params p;
    p.execution_depth_limit = 1000000000;

    rl::simulate<stack_test>(p);

    return 0;
}

запустил на ночь, для 200000 операций push/pop параллельно.

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

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

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

boostcoder

Дата 1.12.2010, 23:03 (ссылка)

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

Загрузка ...

pattern`щик

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

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

Цитата(Леопольд @ 1.12.2010, 22:57

)

запустил на ночь, для 2000000 операций push/pop параллельно

где? на LWS ?! smile

Добавлено через 1 минуту и 24 секунды
и relacy на LWS нет. хотя подумываю установить. карман ведь не тянет smile

Добавлено через 2 минуты и 48 секунд
Леопольд, скажи, у тебя есть где реально применить сие?

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

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

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