VPF::Очередь через кольцевой буфер

gpepsi

Дата 3.1.2012, 22:09 (ссылка)

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

Загрузка ...

Шустрый

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

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

Есть ли где готовая реализация ?

bsa

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

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 24
Всего: 196

boost

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

_GRIN_

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

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

Загрузка ...

одинокий падаван

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

Репутация: 6
Всего: 7

gpepsi, если я правильно тебя понял - то так:

Код


#circul_buffer_queue.h
#ifndef CIRCUL_BUFFER_QUEUE_H
#define CIRCUL_BUFFER_QUEUE_H

#include <QQueue>

template<class T>class CCirculBufferQueue : public QQueue<T>
{
private:
    uint m_limit;

public:
    inline CCirculBufferQueue(uint buffer_size) : QQueue<T>(),m_limit(buffer_size) {}

    inline void enqueue(const T &t)
    {
        if(m_limit == QQueue<T>::count())
        {
            QQueue<T>::dequeue(); //remove oldest item
        }
        QQueue<T>::enqueue(t);
    }
};

#endif // CIRCUL_BUFFER_QUEUE_H

Код


#main.cpp

#include "circul_buffer_queue.h"
#include <QDebug>
int main()
{
    CCirculBufferQueue<int>cqueue(5);
    for(int i=1;i<=9;i++)
    {
        cqueue.enqueue(i);
        qDebug() << i << ": " << cqueue.count();
    }
    return 0;
}

лог выполнения

Код

P.S. Решение для кьюта - но в stl можно аналогично релизовать

Это сообщение отредактировал(а) _GRIN_ - 4.1.2012, 21:55

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

Дорогу осилит идущий

gpepsi

Дата 13.1.2012, 21:47 (ссылка)

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

Загрузка ...

Шустрый

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

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

Хочу усложнить задачу - нужна потоко-безопастная очередь...

bsa

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

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 24
Всего: 196

gpepsi, добавь мьютекс и будет тебе безопасная.

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

gpepsi

Дата 14.1.2012, 09:03 (ссылка)

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

Загрузка ...

Шустрый

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

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

bsa, слишком просто

Код


void push (cosnt T& v)
{
    QMutex;
    ...
}
T pop (void)
{
   QMutex;
   ...
}

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

boostcoder

Дата 14.1.2012, 09:26 (ссылка)

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

Загрузка ...

pattern`щик

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

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

http://tim.klingt.org/boost_lockfree/

использую.

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

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

_GRIN_

Дата 15.1.2012, 00:31 (ссылка)

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

Загрузка ...

одинокий падаван

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

Репутация: 6
Всего: 7

Цитата(gpepsi @ 14.1.2012, 07:03

)

Используй QReadWriteLock http://developer.qt.nokia.com/doc/qt-4.8/QReadWriteLock.html

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

Дорогу осилит идущий

boostcoder

Дата 15.1.2012, 01:44 (ссылка)

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

Загрузка ...

pattern`щик

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

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

Цитата(_GRIN_ @ 15.1.2012, 00:31

)

Используй QReadWriteLock

неправильно.
писатель имеет абсолютную "власть" над читателями. по этому, пока писатель не вернул ресурс, читатели курят.

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

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

bsa

Дата 15.1.2012, 17:02 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 24
Всего: 196

Цитата(gpepsi @ 14.1.2012, 10:03

)

bsa, слишком просто

Но судя по коду ты и этого не осилил.

Цитата(gpepsi @ 14.1.2012, 10:03

)

Если у какого писателя после захвата мьютекса произойдет переключение контекста, то все остальные писатели и читатели
будут курить в холостую

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

Это сообщение отредактировал(а) bsa - 15.1.2012, 17:21

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

boostcoder

Дата 15.1.2012, 19:14 (ссылка)

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

Загрузка ...

pattern`щик

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

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

Цитата(bsa @ 15.1.2012, 17:02

)

надо делать так, чтобы захват мьютекса происходил на минимальное время

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

Это сообщение отредактировал(а) boostcoder - 15.1.2012, 19:14

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

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

bsa

Дата 16.1.2012, 12:22 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 24
Всего: 196

boostcoder, другими словами, ты хочешь сказать, что надо менять вообще способ решения задачи, а не пытаться решить ее крутой кольцевой очередью. Я правильно понял?

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

bsa

Дата 16.1.2012, 12:55 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 24
Всего: 196

gpepsi, lock-free программирование структуры данных

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

boostcoder

Дата 16.1.2012, 13:12 (ссылка)

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

Загрузка ...

pattern`щик

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

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

Цитата(bsa @ 16.1.2012, 12:22

)

другими словами, ты хочешь сказать, что надо менять вообще способ решения задачи, а не пытаться решить ее крутой кольцевой очередью. Я правильно понял?

опять же - зависит от задачи.
если задача не критична к производительности - так оставить эту очередь с мьютексом smile

если же наоборот, критична - то три способа(от худшего к лучшему):
1. общая lock-free очередь.
2. на каждый поток по lock-free очереди.
3. новый паттерн disruptor. недавно обсуждали с drug007. посмотри его темы.

Добавлено через 2 минуты и 32 секунды

Цитата(bsa @ 16.1.2012, 12:55

)

gpepsi, lock-free программирование структуры данных

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

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

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

gpepsi

Дата 20.1.2012, 11:46 (ссылка)

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

Загрузка ...

Шустрый

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

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

попробовал набросать

Код


template <class T>
class BoundedQueue {
    Q_DISABLE_COPY(BoundedQueue)

public:
    explicit BoundedQueue(uint size) : m_size(size) {}
    ~BoundedQueue() {}

    bool push(const T& item)
    {
        QWriteLocker locker(&m_lock);
        if (m_queue.size() < m_size)
        {
            m_queue.enqueue(item);
            m_condition.wakeAll();
            return true;
        }
        DebugMessage(__FUNCTION__, "BoundedQueue overflow");
        return false;
    }
    bool pop(T& value, uint msecs)
    {
        QReadLocker locker(&m_lock);
        if (m_condition.wait(&m_lock, msecs))
        {
            Q_ASSERT(!m_queue.isEmpty());
            value = m_queue.dequeue();
            return true;
        }
        return false;
    }

private:
    uint            m_size;
    QQueue<T>        m_queue;
    QReadWriteLock    m_lock;
    QWaitCondition    m_condition;
};

но что-то очередь медленная. Я читаю с нее очень медленно.
Может я сто-то с синхронизацией намутил ?

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| С/С++: Кроссплатформенное программирование, Qt/Gtk+/wxWidgets \| Следующая тема »