Приложения одновременных очередей и стеков в .NET 4

Question

.NET 4 включает новые параллельные структуры данных.Коллекции Bag и Dictionary имеют очевидные приложения, но я не вижу никакого применения для структур данных Queue и Stack.Для чего люди их используют?

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

Answer 1

Стеки и очереди невероятно полезны в параллельном программировании, так же как и в последовательном программировании.

Новые классы ConcurrentQueue<T> и ConcurrentStack<T> обеспечивают очень хорошую, поточно-ориентированную реализацию очереди и стека.,Они особенно полезны при работе с многопоточными сценариями производитель / потребитель, так как оба класса являются безблокировочными (хорошими для масштабируемости) и потокобезопасными, а также достаточно производительными.

Кроме того, я хотел бы отметить одинвещь - у вас есть два заблуждения во втором абзаце.Связанные списки не особенно плохи для масштабируемости.Распределение памяти может потребоваться регулярно (хотя есть способы борьбы с этим), но зачастую это меньшая цена, чем другие потенциальные проблемы с точки зрения масштабируемости.(Это действительно зависит от сценария ...) Кроме того, новые классы ConcurrentQueue<T> и ConcurrentStack<T> не основаны на (по крайней мере, традиционном) связанном списке.Это класс без блокировки, который внутренне использует связанный список массивов для хранения элементов, например, std :: deque .

Answer 2

Довольно очевидный сценарий для очереди - один (или более) поток, помещающий рабочие элементы в очередь, и несколько рабочих потоков, извлекающих их для параллельной обработки.

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

Answer 3

В этом недавнем сообщении в блоге, в котором точно описывается вопрос, который вам нужен (проблемы с GC при использовании ConcurrentBag и TPL), предлагаются способы обнаружения и анализа этого в поле (VS2010 Concurrency Visualizer).Использование Server GC предлагается для частичного решения.

http://blogs.msdn.com/b/hshafi/archive/2010/06/17/case-study-parallelism-and-memory-usage-vs2010-tools-to-the-rescue.aspx?wa=wsignin1.0

Answer 4

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

Управление памятью - это проклятие всех структур данных без блокировок: вот хорошая презентация о состоянии дел: http://sysrun.haifa.il.ibm.com/hrl/ISMM2009/program.html#7

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