Стандартная имплементация потокобезопасной очереди в GCC

Если тебе linked list - обломайся, он без блокировок не делатся. Причина - при удалении элемента нужна гарантия, что никакой другой поток его не юзает. А так - свой кольцевой список запиливается довольно легко. При условии одного пейсателя и одного читателя обходишься без блокировок. Ну и по желанию добавляешь блокировки на чтение из пустой очереди или запись в полную.

А так - свой кольцевой список запиливается довольно легко.

Мне нужен список, хранимый в виде простого массива. Который может
realloc() для увеличения своего размера, как база данных.

P.S.
А почему при нескольких писателях в кольцевой из атомарных элементов,
нужна блокировка? Для поддержания целостности пары (list, counter)?

Причина - при удалении элемента нужна гарантия, что никакой другой поток его не юзает.

ОК. Попробую обойтись по-возможности без списков на указателях.
Да и медленные они для моей задачи ...

но хотелось бы заюзать что-то стандартное.

почему бы не использовать APR? зачем изобретать очередной лисапед?

APR

как расшифровывается? Гугль думает, что я спросил про April

http://apr.apache.org/

Apache Portable Runtime

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

требуют дополнительного mutex_lock
Доступ из нескольких потоков

Все правильно. Можно, конечно, и без блокировок — но потом пеняй на себя.

Неважно какую структуру данных ты будешь использовать для очереди как таковой: свой велосипед или инструменты, предоставляемые STL, boost, etc. - в любом случае для обеспечения потокобезопасности без блокировки не обойтись. Иначе, при одновременном доступе двух и более потоков к общим для них структурам данных очереди может произойти их (данных) «поломка» - подробности см. в любом мануале по многопоточному программированию.

Для очередей в чистом C обычно используют <sys/queue.h>. Она не-POSIX, но Linux/*BSD есть. В крайнем случае можно таскать с собой, это небольшая header-only библиотека.

Мутексы на запись, как уже написали, нужны в любом случае.

Из-за одних только очередей использовать APR - как-то избыточно, мне кажется

Из-за одних только очередей использовать APR - как-то избыточно, мне кажется

Скорее всего там, где нужны очереди, также понадабятся потом мутексы, сокеты, работа с фаилами, треды и остальной набор утилит для реализации _работающей_ проги. APR также кроссплатформенен.

А смысл тащить библиотечищу, да еще апачевскую, туда, где можно обойтись элементарными queue, pthreads и прочими стандартными средствами?

А смысл тащить библиотечищу, да еще апачевскую, туда, где можно обойтись элементарными queue, pthreads и прочими стандартными средствами?

А если мне надо не велосипедом заниматься, а над задачей работать? А если мне надо на нескольких платформах запускать?

А если мне надо не велосипедом заниматься, а над задачей работать?

«Велосипед» будет быстрей, нежели разбираться хрен знает в чем.

А если мне надо на нескольких платформах запускать?

Ну, тогда придется всякую хрень использовать. Да.

библиотечищу

lrwxrwxrwx 1 user user 13 Oct 8 14:36 libapr-1.so -> libapr-1.so.0*
lrwxrwxrwx 1 user user 17 Oct 8 14:36 libapr-1.so.0 -> libapr-1.so.0.4.5*
-rwxr-xr-x 1 user user 162948 Oct 8 14:36 libapr-1.so.0.4.5*
lrwxrwxrwx 1 user user 17 Oct 8 14:36 libaprutil-1.so -> libaprutil-1.so.0*
lrwxrwxrwx 1 user user 22 Oct 8 14:36 libaprutil-1.so.0 -> libaprutil-1.so.0.3.12*
-rwxr-xr-x 1 user user 115976 Oct 8 14:36 libaprutil-1.so.0.3.12*
lrwxrwxrwx 1 user user 13 Oct 8 14:36 libexpat.so -> libexpat.so.0*
lrwxrwxrwx 1 user user 17 Oct 8 14:36 libexpat.so.0 -> libexpat.so.0.5.0*
-rwxr-xr-x 1 user user 118944 Oct 8 14:36 libexpat.so.0.5.0*


А можно вообще в статику компильнуть.

И какого размера там мануал?

нежели разбираться хрен знает в чем.

это ты так об APR?

И какого размера там мануал?

мануала нет. Есть туториалы в ваших инетах. Есть доксигеновская документация, но очень подробная. А API APR очень простой, достаточно только освоить правильную работу с пулами.

Сдается мне, этот ваш APR — очередной набор костылей и подпорок.

Сдается мне, этот ваш APR — очередной набор костылей и подпорок.

то есть самый популярный вебсервер, subversion и куча других проектов работают на костылях. Черт, а народ то и не знает! ;-)

Для очередей в чистом C обычно используют <sys/queue.h>, http://linux.die.net/man/3/queue

это то, что доктор прописал

спасибо

А почему при нескольких писателях в кольцевой из атомарных элементов, нужна блокировка? Для поддержания целостности пары (list, counter)?

Есть письменное подтверждение атомарности?

не понял. ты спрашиваешь меня спецификации на компилятор от Intel или GNU? или спецификации на процессоры?

А почему при нескольких писателях в кольцевой из атомарных элементов, нужна блокировка?

Атомарных элементов (по крайней мере, в С) не бывает, бывают атомарные операции. В С++ можно сделать класс и перегрузить для него всю арифметику с помощью атомарных операций, но производительность такого списка может быть неудовлетворительной.

Вообще говоря, для многих структур есть варианты lock-free, в т.ч. и для очередей. Но с ними все немного сложнее, конечно.

См., например: http://www.1024cores.net/ Или просто google: lock free

Атомарных элементов (по крайней мере, в С) не бывает, бывают атомарные операции.

Здесь точных терминов не знаю. Рассуждал по-аналогии с определением: Язык = Алфавит + Грамматика.

Точно, как выше уже упомянли: оказывается, существуют атомарные операции даже для double:

store, load, exchange and compare_exchange_{weak,strong}.

Кстати, можешь пригласить niXman'а: он тут обитает.

По сути, получается, что вместо

double var;
mutex var_mutex;

double get_var(void) {
    double tmp;
    mutex_lock(&var_mutex);
    tmp = var;
    mutex_unlock(&var_mutex);
}

set_var(double tmp) {
    mutex_lock(&var_mutex);
    var = tmp;
    mutex_unlock(&var_mutex);
}

void* thread_func(void)
{
    double d;
    for (...) {
        d = get_var();
        //....
        set_var(d);
    }
}

Выше потерялся return:

double get_var(void) {
    double tmp;
    mutex_lock(&var_mutex);
    tmp = var;
    mutex_unlock(&var_mutex);
    return tmp;
}

не понимаю - зачем такое извращение с double? разве операция get/set (=) в Си не атомарна над ним?

Нет никаких «get/set» в Си, есть запись по адресу в памяти. А уж будет он атомарным или нет, зависит от архитектуры.

Но всё равно в каждом потоке манипулировать значением var нужно по-прежнему посредством временной переменной d.

Зато как сильно повышается скорость выполнения! У меня из-за этих блокировок видеокарточка считала кое-что так же медленно, как CPU. А все потому, что старенькая она у меня — не умеет атомарные операции.

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

Например, не-атомарный может быть в случае software-эмуляции операций с float'ами?

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

Мне нужен список, хранимый в виде простого массива. Который может

realloc() для увеличения своего размера, как база данных.

И на realloc у тебя будет блокировка всей очереди. Может все-таки выйдет не увеличивать очередь?

А почему при нескольких писателях в кольцевой из атомарных элементов,

нужна блокировка?

Я уже не помню. Или не нужна, но нужно особо плясать с бубном. Суть в том, что тебе нужно: 1. предварительно выделить место под след. элемент (чтобы параллельный пейсатель не начал туда же писать), 2. записать значение элемента очереди, 3. пометить элемент как уже записанный (т.е. подвинуть указатель на последний записанный). А теперь представь расклад: поток №1 делает 1,2, потом поток №2 делает 1,2, и 3. Что делать в 3? ведь между элементом потока №2 и концом списка есть элемент потока №1, в который тот еще возможно не закончил писать? Поток №2 таким образом не может сделать 3, потому что 3 еще не сделал поток №1. В свое время я на этом остановился и не выдумывая, что делать дальше, тупо добавил мьютекс на влю запись.

А вообще, если у тебя много писателей, то тупо сделай много очередей (по одной на писателя). Дальше, если читатель один - пусть перебирает все очереди. Если много, то без блокировки на чтении можно обойтись - читатель 1. запоминает позицию чтения, 2. читает, 3. атомарно проверяет, не изменилась ли позиция чтения и подвигает еще (atomic compare/exchange) Если не вышло (позиция изменилась) - назад к 1.

Apache Portable Runtime

И где там очереди?

что-то типа буста для Си

Бггг.

И где там очереди?

http://apr.apache.org/docs/apr/trunk/group___a_p_r___util___f_i_f_o.html

Спасибо.

Я правильно понял, что STL'ные queue требуют дополнительного mutex_lock для цикла чтения-записи в очередь?

struct LockableI {
    virtual void lock() = 0;
    virtual void unlock() = 0;
    virtual ~LockableI() {}
};

class Using {
    LockableI *x;
  public:
    Using(LockableI *x) : x(x) { x->lock(); }
    ~Using() { x->unlock(); }
};

class Using2 {
    LockableI *x, *y;
  public:
    Using2(LockableI *x, LockableI *y) : x(x), y(y) {
        x < y ? (x->lock(), y->lock()) : (y->lock(), x->lock()); }
    ~Using2() { x < y ? (y->unlock(), x->unlock()) : (x->unlock(), y->unlock()); }
};

class SingleLock : public LockableI {
    pthread_mutex_t mutex;
  public:
    SingleLock() : mutex(PTHREAD_MUTEX_INITIALIZER) {}
    void lock() { pthread_mutex_lock(&mutex); }
    void unlock() { pthread_mutex_unlock(&mutex); }
};

template <typename T>
struct queueTS : public std::queue<T>, public SingleLock {
    // ...
};

и использовать так:

    queueTS<int> mbox1, mbox2;

    // ...

    {
        Using _(&mbox1);

        // sequential work with mbox1...
    }

    // ...

    {
        Using2 _(&mbox1, &mbox2);

        // mbox1 <-> mbox2 transfer...
    }

Если связных объекта три - X, Y, Z, - то Using2 уже не поможет - если сделать Using2(X, Y) и где-то ещё Using2(Y, Z), первый может захватить X, второй - Y. Но если сделать Using3 соблюдая тот же lock ordering, то Using3(X, Y, Z) захватится минимальный по адресу указатель и все остальные Using3 от комбинаций X, Y, Z будут ждать (так как будут пытаться сначала захватить тот же минимальный по адресу объект). То есть, если есть n связных объектов они должны блокироваться все вместе с помощью UsingN и никак иначе, иначе они должны быть не связаны, а независимы.