бесконечный fifo в java

Я ищу потокобезопасный бесконечный блокирующий fifo, который поддерживается фиксированным буфером, таким как массив. Семантика будет заключаться в том, что несколько потоков чтения и записи могут безопасно получить к нему доступ. Модули записи блокируются, если буфер заполнен, и перезаписывают самый старый элемент. Читатели блокируются, если буфер пуст. Порядок FIFO должен поддерживаться, когда счетчик общего количества добавленных и удаленных элементов один или несколько раз обернулся вокруг размера внутреннего буфера.

Интересно, что обычные места, которые я искал бы для этого (собственные параллельные коллекции Java, коллекции общих ресурсов, гуава), не видят мгновенного ответа на такое «очевидное» требование.


java multithreading concurrency fifo
person simbo1905    schedule 18.02.2013    source источник
comment
Что вы имеете в виду под бесконечным?   -  person Oliver Charlesworth    schedule 18.02.2013
comment
под бесконечным я подразумеваю случайные добавления и случайные удаления до бесконечности, при этом общее количество добавлений и удалений намного превышает размер резервной структуры данных.   -  person simbo1905    schedule 18.02.2013
comment
ммм, ArrayBlockingQueue действительно поддерживает строгий порядок FIFO. Вы пытались включить параметр честного конструктора?   -  person jtahlborn    schedule 18.02.2013
comment
@jtahlborn Дох! :-D спасибо за это. я попробую, когда вернусь в свою IDE. вы можете указать это как ответ, если хотите получить кредит.   -  person simbo1905    schedule 18.02.2013

Ответы (5)


arrow_upward
3
arrow_downward

На самом деле вы описываете ArrayBlockingQueue.

Он потокобезопасен и был разработан именно для этой цели:

  • писатели ждут освобождения места, если очередь заполнена
  • читатели могут ждать до указанного времени ожидания, если необходимо, чтобы элемент стал доступным
person Jean Logeart    schedule 18.02.2013
comment
спасибо за Ваш ответ. Первое, что я попробовал, это ArrayBlockingQueue. модульные тесты начали давать сбой, когда были случайные добавления и случайные удаления с попытками переполнения и пакетными вставками и пакетными удалениями. я хочу, чтобы упорядочение fifo гарантировалось без необходимости внешнего отслеживания порядка или сортировки, если это возможно. - person simbo1905; 18.02.2013
comment
я имею в виду случайное чтение/запись в логическую голову и логический хвост, не случайное в пределах логического порядка fifo. если я всегда хочу, чтобы буфер был заполнен эффективно, тогда семантика циклического буфера кажется чем-то большим, чем необработанный ABQ. - person simbo1905; 18.02.2013
comment
@ simbo1905 - ABQ является циклическим буфером. не понятно какой функционал вы ищете чего не хватает ABQ? - person jtahlborn; 18.02.2013
comment
под случайным я подразумеваю случайные добавления/удаления из логической головы и хвоста коллекции, которая не является физической головой/хвостом линейной коллекции, если вы пытаетесь использовать семантику циклического буфера (это означает, что он всегда заполнен, и вы перезаписываете самое старое значение при вставке новое значение) - person simbo1905; 18.02.2013
comment
@ simbo1905 simbo1905 - вам нужно быть яснее ... может быть, вы могли бы показать пример кода, который не работает с ABQ? - person jtahlborn; 18.02.2013
comment
@jtahlborn согласился. в мою защиту см. этот предшествующий уровень техники, где людям приходилось писать свои собственные stackoverflow.com/questions/7266042/java-ring -buffer я спрашивал сообщество из-за моего удивления необходимостью писать модульные тесты для такого рода «очевидной функциональности» - person simbo1905; 18.02.2013
comment
@ simbo1905 simbo1905 - хорошо, если вам нужна такая функциональность, почему авторы состояния вашего вопроса блокируются, если буфер заполнен? в приведенном вами примере писатель никогда не будет блокировать, он перезапишет самый старый элемент. - person jtahlborn; 18.02.2013
comment
вопрос отредактирован. приносим извинения за отсутствие ясности и спасибо за внимание. - person simbo1905; 18.02.2013
comment
Оказывается, мой сбойный junit, использующий ABQ для проверки разрушителя, не работал, поскольку объекты, переданные очередью, не были неизменными. ArrayBlockingQueue - это ответ. спасибо за настойчивость :-) - person simbo1905; 20.02.2013

arrow_upward
0
arrow_downward

Похоже, вы ищете ArrayBlockingQueue.

person NPE    schedule 18.02.2013
comment
я отредактировал вопрос, чтобы было понятнее, что я ищу что-то, что может быть блокирующим циклическим буфером, в котором писатель перезаписывает самые старые элементы. - person simbo1905; 18.02.2013

arrow_upward
0
arrow_downward

Как насчет java.util.concurrent.ArrayBlockingQueue

person Stanislav Levental    schedule 18.02.2013
comment
спасибо за Ваш ответ. в других ответах, которые предлагают ABQ, я указываю, что я больше ищу круговой буфер, который не является стандартным с ABQ. - person simbo1905; 18.02.2013

arrow_upward
0
arrow_downward

Неясно, ищете ли вы бесконечную очередь блокировки или ограниченную очередь блокировки.

  1. Ограниченная очередь блокировки: java.util.concurrent.ArrayBlockingQueue
  2. Бесконечная очередь блокировки (ограничена только объемом оперативной памяти): java.util.concurrent.LinkedBlockingQueue

Для всех случаев я предлагаю использовать ArrayBlockingQueue.

person max    schedule 18.02.2013
comment
спасибо за Ваш ответ. в других ответах, которые предлагают ABQ, я указываю, что я больше ищу круговой буфер, который не является стандартным с ABQ. - person simbo1905; 18.02.2013
comment
гул я застрял на массиве, так как мне не обязательно нужна сборка мусора для добавления и удаления ссылок. тем не менее, это, вероятно, что-то, что может быть приемлемым, и связанная блокирующая очередь может помочь. попробуем и сообщим вам. - person simbo1905; 18.02.2013

arrow_upward
0
arrow_downward

Для бесконечной очереди вам придется создать свой собственный класс, реализующий интерфейс BlockingQueue, используя делегат очереди (возможно, ArrayBlockingQueue), и когда очередь заполнится, адаптируйте размер, создав новый делегат большего размера. Это должно быть бесконечным до MAX_INT и избежать накладных расходов GC, связанных со связанными очередями (которые должны создавать узлы для каждого вставленного объекта). При необходимости вы также можете уменьшить размер делегата.

person Ralf H    schedule 18.02.2013
comment
как насчет поддержания порядка fifo с большим количеством случайных добавлений и удалений? - person simbo1905; 18.02.2013
comment
Не уверен, что вы имеете в виду здесь. В FIFO (он же список или очередь) не должно быть случайных записей в середине. - person Ralf H; 18.02.2013
comment
извините, я не имел в виду случайный доступ, я имел в виду рандомизированное чтение из головы или хвоста. если вы попытаетесь создать круговой буфер с ArrayBlockingQueue таким образом, чтобы он оставался заполненным, но голова и хвост не находились в позиции 0 или позиции (размер-1), убедитесь, что у вас всегда есть следующее чтение из логического хвоста и следующего чтение из логической головки не так просто, как вызов встроенных методов head/tain для структуры, которые моделируют линейную структуру, а не бесконечный круговой буфер. - person simbo1905; 18.02.2013
comment
да ArrayBlockingQueue можно бесконечно добавлять и бесконечно удалять. - person simbo1905; 20.02.2013