Паттерн очереди

Что то я не понял до конца задачи... хоцца независимого чтения/записи? Ну так выдергивай из очереди элемент при удалении, оттпуская блокировку а потом уже передавай элемет тому кто его обрабатывате при удалении... при добавлении то же самое.

Как раз в этом случае независимо не получится :) Очередь должна быть залочена целиком, пока элемент не будет удален, а все ссылки в списке не обновлены. Читать из очереди без mutex тоже не безопасно, т.к. есть вероятность попасть на битую ссылку.

Интересуют уже существующие идеи реализации, а то велосипед не нужен :)

При твоих условиях: если больше 2 элементов в очереди, то блокировка не нужна. Блокируй только если 2, 1 или 0 элементов.

Во как народ мучается, лишь бы не делать нормальную многопроцессную систему с очередями в виде FIFO-файлов :-)

>если больше 2 элементов в очереди, то блокировка не нужна.
почему это?

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

Для простоты эксперимента - если взять простой список:

list<int> l;

void* writer ()
{
int i = 0;
while(1) {
l.push_back(i);
}
return 0;
}

void* reader ()
{
while(1) {
printf("%d\n", l.front());
l.pop_front();
}
}

Грохается только так (SEGFAULT).

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

Например, конец очереди отмечается NULL'ем.

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

Разумеется, если ты САМ станешь наворачивать логику, типа, введешь переменную "длина" и станешь ее менять и из читателя, и из писателя, то все на уши встанет (если только ты не задействуешь атомарные операции) -- ну дык, сам логику накрутил. Алгоритм же такого не требует.

С более сложной топологией, особенно если есть петли, все сложнее.

епрст... добавить/удалить элемент из очереди - это ж децил тактов. Ес-но на время этих операций очередь нуно лочить, и не стоит надеяться на атомарность операций - даже i++ если верить литературе могет быть не атомарной.

но вот обрабатывать элементы (создавать перед добавлением и анализировать после удаления) моно и не под блокировкой - поскоку на этот момент элемент никто чужой не видит. С-но я это и имел ввиду...

AIv (07.02.2005 20:32:42):

> епрст... добавить/удалить элемент из очереди - это ж децил тактов. Ес-но на время этих операций очередь нуно лочить,

Еще раз.

Если это FIFO, то ее НЕ НУЖНО лочить, поскольку операцию добавления легко сделать атомарной, а удалять можно вообще как взбрендит.

Пример:

В голове сидит пустая ячейка, на нее указывает указатель Г. Хвост -- указатель Х -- указывает на того, кто первым пришел.

Читатель: если Х == Г, то пусто. Иначе возвращает инфу из Х, а Х = Х->next.

Писатель: заполняет поля ячейки, на которую указывает Г, создает новую пустую ячейку Н, делает Г->next = Н, после чего (вот оно, атомарное добавление новой ячейки!) Г = Н

> ...даже i++ если верить литературе могет быть не атомарной.

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

Die-Hard, а как атомарно удалять после чтения для FIFO?

Покажи на струтуре:

struct Element {
  int value;
  Element* next;
};

struct Queue {
  Element* first;
  Element* last;
};

> ...а как атомарно удалять после чтения для FIFO?

Никак!

Встречный вопрос -- а зачем его удалять АТОМАРНО, если никто, кроме читателя, в этот конец не лезет?

Очередь ограничена по длине и элемент после чтения должен быть удален,
чтобы не мусорить память.

Можно не атомарно, а безопасно :)

> Очередь ограничена по длине и элемент после чтения должен быть удален,...

Дык, и удаляй, кто ж мешает! Зачем тебе его АТОМАРНО удалять? Запоминай ptr= first, перелинковывай first=first->next и грохай все, что в ptr вместе с ним.