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

Леопольд

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

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

Загрузка ...

Опытный

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

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

Цитата(boostcoder @ 1.12.2010, 23:03

)

где? на LWS ?!

Нет конечно, локально.
Уменьшил до 200000, bоюсь к утру LIVELOCK напишет иначе...

Добавлено @ 23:11

Цитата(boostcoder @ 1.12.2010, 23:03

)

Леопольд, скажи, у тебя есть где реально применить сие?

Пока нет. Просто проbую свои силы. Потом хеш-таbлицу хочу написать и распараллелить A* smile

Статью Тиграна прочёл и, неожиданно увлёкся. Кажется мне что в ИИ, bудущее за lock free алгоритмами.

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

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

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

boostcoder

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

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

Загрузка ...

pattern`щик

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

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

установил relacy.
вот тест: http://liveworkspace.org/code/08782ad50b2d...3c7ef1f00810096

Добавлено @ 23:24
только не понимаю что там выводится, и что должно выводится smile

Это сообщение отредактировал(а) boostcoder - 1.12.2010, 23:25

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

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

azesmcar

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

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

Загрузка ...

uploading...

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

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

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

)

relacy не помог...

чем именно он должен был помочь?

Цитата(boostcoder @ 1.12.2010, 23:03

)

Леопольд, скажи, у тебя есть где реально применить сие?

если нужно куда-то применить, советую взглянуть на libcds

Цитата(boostcoder @ 1.12.2010, 23:23

)

установил relacy.

О! Отлично.

Леопольд

Александреску в одной из статей использует такой трюк.
Инкапсулируется некий тип (например map)
Чтение - wait-free безо всяких итераций, просто возвращение объекта.
Запись - создание копии, добавление новой записи и замена внутреннего объекта.
Ну и конечно же опять встает вопрос удаления старой копии.
Это можно построить на шаблоне и применять эту технику для любого типа, но естественно, это эффективно только тогда, когда запись является редким явлением. Упор делается на скорость чтения высокая.

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

Леопольд

Дата 2.12.2010, 06:44 (ссылка)

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

Загрузка ...

Опытный

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

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

Код

10stack_test
iterations: 1000
total time: 1423390
throughput: 0

Что значить throughput в relacy? Почему-то только в ночных тестах равен нулю.

Добавлено @ 06:46

Цитата(azesmcar @ 1.12.2010, 23:32

)

ем именно он должен был помочь?

Где-то, видимо двойной delete. Не могу понять где...
Мне, вроде бы, удалось обойти добавление эелементов обратно в очередь на удаление. Это может сильно поднять производительность.
http://liveworkspace.org/code/8ed457a04766...847bee388deb79b

Цитата

*** glibc detected *** source.cpp.bin: free(): invalid pointer: 0xb3762e38 ***

Добавлено @ 06:49

Цитата(boostcoder @ 1.12.2010, 23:23

)

только не понимаю что там выводится

Поток не успел завершить раbоту до достижения

Код

p.execution_depth_limit = 100000;

Это, как я понял, количество ($) через которые он прошёл.

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

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

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

azesmcar

Дата 2.12.2010, 07:45 (ссылка)

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

Загрузка ...

uploading...

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

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

Цитата(Леопольд @ 2.12.2010, 06:44

)

Это, как я понял, количество ($) через которые он прошёл.

Цитата

Also you can specify 'execution_depth_limit' parameter - used for livelock detection. All executions with trace longer than execution_depth_limit will be treated as livelocked (or non-terminating).

Цитата(Леопольд @ 2.12.2010, 06:44

)

Что значить throughput в relacy? Почему-то в только в ночных тестах равен нулю.

Этого не знаю...

Леопольд

Дата 2.12.2010, 09:16 (ссылка)

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

Загрузка ...

Опытный

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

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

Оно, кстати, иногда работает, хотя нагрузка серьёзная. Два потока "выкидывают" элементы другие два "вставляют", в сумме 2000000 элементов.
http://liveworkspace.org/code/705bf2998c43...9a3bced3e591522
Сперва пытался сделать вариант с возвратом элементов обратно. Но он просто "вешался" под такой нагрузкой.

Может я как-то неправильно тестирую? Не получается воспроизвести...

Код

#include <cstdio>
#include <boost/shared_ptr.hpp>
#include <boost/make_shared.hpp>
#include "relacy/relacy_std.hpp"

template <typename T>
class concurent_stack
{
private:
    struct node
    {
        node * next;
        boost::shared_ptr<T> data;
        node(const T& d, node* n) :next(n), data(boost::make_shared<T>(d)) {}
        node(node* n) :next(n), data(boost::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;

    std::atomic<std::size_t> m_size;
    std::atomic<std::size_t> m_deleted_queue_size;

    static node end;

public:
    concurent_stack() : m_head(&end), m_deleted_head(&end), m_active_threads(0), m_size(0), m_deleted_queue_size(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));
        m_size($).fetch_add(1);
    }
    boost::shared_ptr<T> pop()
    {
        m_active_threads($).fetch_add(1);
        node * head = m_head($).load();
        while(!m_head($).compare_exchange_weak(head, head->next));

        //1.Загружаю указатель на начало очереди на удаление
        node * deleted_head = m_deleted_head($).load();
        //2. умешьшаю счётчик потоков и если он стал равен нулю значит нет потоков, которые работают с тем же m_head
        //3. пытаюсь сделать один strong CAS указателя m_deleted_head и зацикленного на себя указателя &end (признак конца очереди).
        if(m_active_threads($).fetch_sub(1) - 1 == 0 && m_deleted_head($).compare_exchange_strong(deleted_head, &end))
        {
            //Если удалось подменить m_deleted_head с первого раза, значит ни один поток не успел его поменять и список можно спокойно удалять.
            boost::shared_ptr<T> ret;
            if(head == &end)
            {
                head = deleted_head;
            }
            else
            {
                head->data.swap(ret);
                m_size($).fetch_sub(1);

                head->next = deleted_head;
            }
            while(head != &end)
            {
                node * next = head->next;
                if(next != &end) m_deleted_queue_size($).fetch_sub(1);
                delete head;
                head = next;
            }
            return ret;
        }

        if(head != &end)
        {
            //Если не удалось подменить m_deleted_head, то запихнуть удаляемый элемент в очередь на удаление.
            boost::shared_ptr<T> ret;
            head->data.swap(ret);
            m_size($).fetch_sub(1);

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

            m_deleted_queue_size($).fetch_add(1);
            return ret;
        }

        //если стек был пуст
        return boost::shared_ptr<T>();
    }
    ~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;
        }
    }

    std::size_t size()
    {
        return m_size($).load();
    }

    std::size_t del_queue_size()
    {
        return m_deleted_queue_size($).load();
    }
};
template <typename T>
typename concurent_stack<T>::node concurent_stack<T>::end(&concurent_stack<T>::end);




unsigned const thread_count = 32;
unsigned nodes_count = 8;
unsigned non_deleted_queue_total_length = 0;
unsigned non_deleted_queues_quantity = 0;

struct stack_test : rl::test_suite<stack_test, thread_count>
{
    stack_test() {}
    concurent_stack<char> * stack;
    std::size_t non_deleted_nodes;
    // executed in single thread before main thread function
    void before()
    {
        stack = new concurent_stack<char>();
        non_deleted_nodes = 0;
    }
    // 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)
                if(!stack->pop())
                    ++non_deleted_nodes;
        }
    }
    // executed in single thread after main thread function
    void after()
    {
        if(stack->size())
        {
            RL_ASSERT(stack->size() == non_deleted_nodes);
        }
        non_deleted_queue_total_length += stack->del_queue_size();
        ++non_deleted_queues_quantity;
        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);
    std::cout << "average length of non deleted queues = " << (non_deleted_queue_total_length / (double)non_deleted_queues_quantity) << std::endl;
    return 0;
}

Код

10stack_test
iterations: 1000
total time: 5860
throughput: 170

average length of non deleted queues = 26.922

Process returned 0 (0x0)   execution time : 5.877 s

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

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

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

azesmcar

Дата 2.12.2010, 09:34 (ссылка)

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

Загрузка ...

uploading...

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

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

Леопольд

Добавь хоть комментарии и опиши алгоритм.

Леопольд

Дата 2.12.2010, 11:03 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(azesmcar @ 2.12.2010, 09:34

)

Добавь хоть комментарии и опиши алгоритм.

Он похож на тот, который в статье. Основное отличие, работа с очередью удалённых - m_deleted_head:

1. Загружаю m_deleted_head (указатель на начало очереди на удаление)
2. умешьшаю счётчик потоков и если он стал равен нулю (значит нет потоков, которые работают с тем же m_head - указатель на "выкидываемый" элемент).
3. пытаюсь сделать один strong CAS указателя m_deleted_head и зацикленного на себя указателя &end (признак конца очереди).
Рассчёт на то, что если удалось подменить m_deleted_head с первого раза, значит ни один поток не успел его поменять и список можно спокойно удалять.

Если не удалось подменить, то пихаю удаляемый элемент в очередь на удаление.

Ещё, возможно, одно отличие (точно не уверен, может в статье так же). Попытка освободить ненужную занятую память происходит каждый раз, даже если сам стек оказался пустым.

накидал это в виде комментариев в предыдущий пост
http://forum.vingrad.ru/act-ST/f-92/t-3162.../p-2258093.html

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

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

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

Леопольд

Дата 2.12.2010, 12:02 (ссылка)

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

Загрузка ...

Опытный

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

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

Заработало! smile

(поменял 1. и 2. местами и бага "прибил")
8000000 элементов, 4 потока: 2 удаляют, 2 добавляют.
http://liveworkspace.org/code/a1e0bde56b2e...720510a50a6379c

relacy тоже удовлетворён...

Код

#include <cstdio>
#include <boost/shared_ptr.hpp>
#include <boost/make_shared.hpp>
#include "relacy/relacy_std.hpp"

template <typename T>
class concurent_stack
{
private:
    struct node
    {
        node * next;
        boost::shared_ptr<T> data;
        node(const T& d, node* n) :next(n), data(boost::make_shared<T>(d)) {}
        node(node* n) :next(n), data(boost::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;

    //these two are used for testing and quality metrics
    std::atomic<std::size_t> m_size;
    std::atomic<std::size_t> m_deleted_queue_size;

    static node end;

public:
    concurent_stack() : m_head(&end), m_deleted_head(&end), m_active_threads(0), m_size(0), m_deleted_queue_size(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));
        m_size($).fetch_add(1);
    }
    boost::shared_ptr<T> pop()
    {
        m_active_threads($).fetch_add(1);
        node * head = m_head($).load();
        while(!m_head($).compare_exchange_weak(head, head->next));

        //check what no one use the same m_head
        if(m_active_threads($).fetch_sub(1) - 1 == 0)
        {
            node * deleted_head = m_deleted_head($).load();
            //check what no one use any node from the m_deleted_head
            if(m_deleted_head($).compare_exchange_strong(deleted_head, &end) && deleted_head != &end)
            {
                boost::shared_ptr<T> ret;
                if(head == &end)
                {
                    //always try to release the queue of deleted elements
                    //return invalid pointer for the empty stack
                    head = deleted_head;
                }
                else
                {
                    head->data.swap(ret);
                    m_size($).fetch_sub(1);

                    head->next = deleted_head;
                }
                while(head != &end)
                {
                    node * next = head->next;
                    if(next != &end) m_deleted_queue_size($).fetch_sub(1);
                    delete head;
                    head = next;
                }
                return ret;
            }
        }

        if(head != &end)
        {
            //push the deleted element to the queue - m_deleted_head
            boost::shared_ptr<T> ret;
            head->data.swap(ret);
            m_size($).fetch_sub(1);

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

            m_deleted_queue_size($).fetch_add(1);
            return ret;
        }

        //return invalid pointer for the empty stack
        return boost::shared_ptr<T>();
    }

    //this should be called by a sole thread, then no more threads  work with the instance
    ~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;
        }
    }

    //used for testing
    std::size_t size()
    {
        return m_size($).load();
    }
    //used for quality metrics
    std::size_t del_queue_size()
    {
        return m_deleted_queue_size($).load();
    }
};
template <typename T>
typename concurent_stack<T>::node concurent_stack<T>::end(&concurent_stack<T>::end);



//relacy test suite
unsigned const thread_count = 32;
unsigned nodes_count = 8;
unsigned non_deleted_queue_total_length = 0;
unsigned non_deleted_queues_quantity = 0;

struct stack_test : rl::test_suite<stack_test, thread_count>
{
    stack_test() {}
    concurent_stack<char> * stack;
    std::size_t non_deleted_nodes;
    // executed in single thread before main thread function
    void before()
    {
        stack = new concurent_stack<char>();
        non_deleted_nodes = 0;
    }
    // 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)
                if(!stack->pop())
                    ++non_deleted_nodes;
        }
    }
    // executed in single thread after main thread function
    void after()
    {
        if(stack->size())
        {
            RL_ASSERT(stack->size() == non_deleted_nodes);
        }
        non_deleted_queue_total_length += stack->del_queue_size();
        ++non_deleted_queues_quantity;
        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);
    std::cout << "average length of non deleted queues = " << (non_deleted_queue_total_length / (double)non_deleted_queues_quantity) << std::endl;
    return 0;
}

Код

10stack_test
iterations: 1000
total time: 8700
throughput: 114

average length of non deleted queues = 5.4

Process returned 0 (0x0)   execution time : 8.717 s

Да и показатели улучшились.

Если всего 2 потока удаляют то, average length of non deleted queues = 0.09.

P.S. Пожалуй этот вариант уже не так "убог"...
P.S.S А вообще, очень даже ничего! smile

Это сообщение отредактировал(а) Леопольд - 2.12.2010, 15:06

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

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

Леопольд

Дата 2.12.2010, 12:52 (ссылка)

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

Загрузка ...

Опытный

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

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

блин

убогая фигня, опять падает... smile

на одноядерном процессоре, почти сразу.

бага "прибил". Всё чудесно! smile

Если кто-то сможет его "уронить", буду весьма признателен.

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

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

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

azesmcar

Дата 2.12.2010, 16:26 (ссылка)

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

Загрузка ...

uploading...

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

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

Леопольд

Сколько всего изменилось smile

я не успеваю.

Цитата(Леопольд @ 2.12.2010, 12:52

)

бага "прибил"

Мало того, что нашел..так еще и прибил smile

Цитата(Леопольд @ 2.12.2010, 11:03

)

http://forum.vingrad.ru/act-ST/f-92/t-3162.../p-2258093.html

ага, посмотрю.

Цитата(Леопольд @ 2.12.2010, 12:52

)

Если кто-то сможет его "уронить", буду весьма признателен.

Добавь в relacy количество потоков и итераций и оставь на ночь.

Леопольд

Дата 2.12.2010, 19:13 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(azesmcar @ 2.12.2010, 16:26

)

Мало того, что нашел..так еще и прибил

Плохо приbил... smile

Надо передохнуть, уже не сооbражаю ничего...
http://liveworkspace.org/code/1d1704acbdea...fc11a835f900d4e

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

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

azesmcar

Дата 2.12.2010, 20:15 (ссылка)

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

Загрузка ...

uploading...

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

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

Леопольд

Я бы хорошенько пересмотрел этот код. Это и так сложно, а у тебя усложнено еще больше. Комментарии нужны в первую очередь для себя, раздели все на мелкие функции, это заметно облегчит и чтение и понимание того, что происходит. Представить в уме возможные варианты выполнения для нескольких потоков, которые в любой момент могут делать все, что угодно и так сложно, а это еще усложняется кодом. Для начала напиши список, который работает, но с утечками, протестируй, а потом добавляй очистку памяти отдельными функциями. Отдели как нибудь ту часть, которая потенциально может содержать ошибку (т.е. часть очистки памяти) от той, которая протестирована и работает. На данный момент код функции pop слишком большой, чтобы можно было найти в нем ошибку.

Леопольд

Дата 3.12.2010, 08:41 (ссылка)

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

Загрузка ...

Опытный

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

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

azesmcar, пытаюсь рафинировать, потихоньку...

И прихожу к вывод что нельзя использовать обычную связку malloc/free
Запускаю два потока, один добавляет, другой удаляет. Между собой у них только одна атомарная переменная (указатель на голову стека), relacy тесты проходят с опцией (p.search_type = rl::fair_full_search_scheduler_type;) которая всё пространство состояний тестирует. Всё ок.
Но, как только пытаюсь запустить на одноядерной машине (Ubuntu 10.04, g++ 4.5.1):

Цитата

*** glibc detected *** /home/andrey/proj/try_c++0x/bin/Debug/try_c++0x: malloc(): memory corruption (fast): 0x09a0b9a0 ***

Это, видимо, если вызвать malloc до того как free закончит работу.

Сейчас соображу спин лок на выделение памяти и проверю. Google говорит что есть такая штука как lock free malloc

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

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

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

Леопольд

Дата 3.12.2010, 09:46 (ссылка)

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

Загрузка ...

Опытный

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

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

Вот рафинированный код.
LWS relacy

Код

#include <cstdio>
#include <boost/shared_ptr.hpp>
#include <boost/make_shared.hpp>
#include "relacy/relacy_std.hpp"

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

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

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

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

public:
    concurent_stack() : m_head(0), m_deleted_head(0), m_threads_on_lap(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));
    }


    boost::shared_ptr<T> pop()
    {
        boost::shared_ptr<T> ret;

        //begining of the lap (начало "заезда")
        m_threads_on_lap($).fetch_add(1);

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

        if(head)
        {
            ret.swap(head->data);
            head->next = m_deleted_head($).load();
            while(!m_deleted_head($).compare_exchange_weak(head->next, head));
        }
        else
        {
            head = m_deleted_head($).load();
        }

        //1. check this is the last in the lap (кто приехал последний, тот делает "грязную" работу)
        //2. check that no one has changed m_deleted_head since the previous condition (но только если трек сободен)
        //   that means that everithin in the deleted queue can be safely released
        if(m_threads_on_lap($).fetch_sub(1) == 1 && m_deleted_head($).compare_exchange_strong(head, 0))
        {
            while(head)
            {
                node * next = head->next;
                delete head;
                head = next;
            }
        }

        return ret;
    }

    //this method must be called if there is no any thread with reference to the stack instance left
    bool compact()
    {
        node * head = m_deleted_head($).exchange(0);
        bool ret = head;
        while(head)
        {
            node * next = head->next;
            delete head;
            head = next;
        }
        return ret;
    }

    //this method must be called if there is no any thread with reference to the stack instance left
    bool clear()
    {
        node * head = m_head($).exchange(0);
        bool ret = head;
        while(head)
        {
            node * next = head->next;
            delete head;
            head = next;
        }
        return ret;
    }

    //this method must be called if there is no any thread with reference to the stack instance left
    ~concurent_stack()
    {
        clear();
        compact();
    }
};


//relacy test suite
unsigned const thread_count = 3;
unsigned nodes_count = 0;
unsigned non_deleted_queue_total_length = 0;
unsigned non_deleted_queues_quantity = 0;
struct stack_test : rl::test_suite<stack_test, thread_count>
{
    stack_test() {}
    concurent_stack<char> stack;
    std::size_t non_deleted_nodes;
    // executed in single thread before main thread function
    void before()
    {
        non_deleted_nodes = 0;
//        for(std::size_t i = 0; i < nodes_count * thread_count; ++i)
//            stack.push(i);

    }
    // 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)
                if(!stack.pop())
                    ++non_deleted_nodes;
        }
    }
    // executed in single thread after main thread function
    void after()
    {
//        if(stack.size())
//        {
//            RL_ASSERT(stack.size() == non_deleted_nodes);
//        }
//        non_deleted_queue_total_length += stack.del_queue_size();
//        ++non_deleted_queues_quantity;
        stack.clear();
        stack.compact();
    }
    // executed in single thread after every 'visible' action in main threads
    // disallowed to modify any state
    void invariant()
    {
    }
};

void concurent_stack_relacy_test(std::size_t nodes)
{
    nodes_count = nodes;
    rl::test_params p;
    p.execution_depth_limit = 1000000000;
    p.search_type = rl::fair_full_search_scheduler_type;
    rl::simulate<stack_test>(p);
//    std::cout << "average length of non deleted queues = " << (non_deleted_queue_total_length / (double)non_deleted_queues_quantity) << std::endl;
}

Не получается уронить (если не увеличивать количество потоков), видимо на сервере несколько ядер:
http://liveworkspace.org/code/260469bbd4f7...d03e4ad1d4b26e7
на работа одноядерная машина, на ней падает почти сразу.

Это сообщение отредактировал(а) Леопольд - 4.12.2010, 08:24

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

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

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