многопоточный связанный список в C ++ - PullRequest
2 голосов
/ 02 июля 2011

Сначала небольшое объяснение того, что я пытаюсь сделать:

Я планирую написать программу с потоком сокетов, реализованным с использованием библиотеки boost :: asio, которая передает данные в анализатор, реализованный с использованием boost:дух :: ци.Анализатор примет пакеты и заполнит объект пакета, а затем добавит этот объект в конец связанного списка объектов пакета.Процессор пакетов прочитает первый объект в списке и выполнит его обработку, а затем перейдет к следующему элементу и удалит первый.

Я решил использовать связанный список, потому что если я использовал std :: queueЯ должен был бы заблокировать весь контейнер каждый раз, когда поток добавил пакет или процессор удалил один, что заставило бы два потока работать более или менее последовательно, чего я хотел бы избежать.Плюс класс очереди имеет тенденцию копировать все объекты, в то время как идея связанного списка имеет преимущество в том, что объект создается один раз, а затем просто указывает на него.Чтобы избежать сериализации всего этого бизнеса, я намереваюсь поместить boost: mutex-мьютексы в каждый узел и заблокировать их оттуда.Идея состоит в том, чтобы поток сокетов создал список и немедленно заблокировал первый узел, заполнил узел из анализатора, создал следующий узел и заблокировал его, затем разблокировал первый узел и перешел к следующему узлу для выполнения работы.Таким образом, в конце никогда не будет зависшего разблокированного узла, к которому процессор пакетов может перейти и удалить под носом потоков сокетов.Пакетный процессор проверит первый узел и попытается заблокировать его, если он заблокирует его, он выполнит его обработку, а затем разблокирует, получит следующий узел и затем удалит первый узел.Таким образом, сериализация ограничена теми временами, когда процессор пакетов догоняет класс потока сокетов.

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

Заранее спасибо!

Ответы [ 5 ]

1 голос
/ 02 июля 2011

Проверьте эту статью, она о нескольких потребителях, но все еще блестящая:

Измерение параллельной производительности: оптимизация параллельной очереди

0 голосов
/ 02 июля 2011

Хм .. почему такое сложное решение общей проблемы? Существует множество классов очереди «производитель-потребитель» - выберите работающий тип ссылки / указателя / типа int (т.е. без копирования данных).

Получайте байты из вашего потока, пока вы не соберете «объект пакета» в соответствии с вашим протоколом. Поместите объект пакета ссылка в очередь и немедленно добавьте еще один () для следующего пакета. Процессор пакетов потребляет объекты пакетов из очереди.

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

Попытка оперировать объектами, которые уже находятся в очереди (или связанном с очередями списке), для меня звучит как кошмар (и другие авторы, похоже, согласны). Есть ли еще какая-то причина, почему вам нужно это сделать?

Rgds, Martin

0 голосов
/ 02 июля 2011

Эта реализация кричит мне три вещи:

  • Слишком легко получить тупик, потому что вставка и удаление должны будут блокировать несколько мьютексов одновременно, и вы не можете сделать это одновременно. Ну, вы можете, но вам нужно будет разместить мьютексы вокруг ваших мьютексов.
  • Слишком легко получить коррупцию. Проблемы, которые приводят к тупику, также могут привести к коррупции.
  • И медленно, медленно, медленно. Подумайте о своем бедном списке ходок. Каждый шаг включает в себя разблокировку, блокировку, другую разблокировку и другую блокировку. придется быть очень осторожным в шаге, и это будет дорого. Блокировка и разблокировка каждого элемента, и делать это в правильном порядке? Уч.

Это похоже на случай преждевременной оптимизации и преждевременной пессимизации, работающих параллельно. Что привело эту архитектуру?

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

0 голосов
/ 02 июля 2011

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

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

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

Не забудьте иметь условие завершения (например, нулевой указатель в поле next), чтобы источник мог подать сигналПотребитель, которому больше нечего обрабатывать.

0 голосов
/ 02 июля 2011

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

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

...