LINUX.ORG.RU

LockFree очередь сообщений в shared memory - какие хорошие реализации?


1

4

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

  • retcode_t push(void* data, int size);
  • retcode_t pop(void* data, int max_size, int* size);

При том это все рабоатет на уровне сообщения. Т.е. если вставили тру кусочка по 100, 200, и 300 то и выберем 100, 200, 300 а не 600 одним куском.

Хотелось бы это сделать без блокировок. Писателей/читателей от 4 до 50

★★★
Ответ на: комментарий от ckotinko

Все равно не выглядит работающим и ПРОВЕРЕННЫМ решением. При одновременной работе нескольких потоков все будет ломаться. Проверьте как все будет работать если один поток отстает об другого на одну строчку

vromanov ★★★
() автор топика
Ответ на: комментарий от vromanov

это решение не для чтения во много потоков. его можно приспособить добавив feedback от работающих потоков - кто готов забрать задачу. это проще сделать(через lock btc [bitmask])

в принципе возможно реализовать атомарное чтение через cmpxchg8b/cmpxchg16b но.

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

ckotinko ☆☆☆
()
Ответ на: комментарий от ckotinko

Угу. Спасибо, но нам все-таки нужно несколько другое. Будем сами лабать... Т.е. нам еще к этому нужен и циклический буффер. Да и много читателей нужно, чтобы вычитывать по одному сообщению.

vromanov ★★★
() автор топика
Ответ на: комментарий от ckotinko

Года три назад тут с ассемблером пролетало решение. Много писателей, один читатель. На практике потом использовал для захвата 20-гигабитного потока, с моментальным буферированием и отложенной записью на диск, когда взодхнуть можно было. Потом ещё какую-то фигню для эзернета переделывали, там с двух 10-гигабитных портов данные снимали и тоже на диск писали.

mv ★★★★★
()
Ответ на: комментарий от vromanov

Ваше хамство просто убивает. Вы что думаете тут идиоты сидят? Ваши фразы КАСПОМ кабе демонстрируют что вы просто тупой.

Проверьте как все будет работать...

Тебе надо ты и проверяй. Вам уже предложили несколько решений. С вашей стороны ПРОВЕРЬ ТО И СЕ просто козлизм.

Спасибо за внимание.

anonymous
()

Тред не читал.

Для shared memory совсем без блокировок нельзя. Я в свое время делал какую-то похожую структуру данных, внутри которой хранил «ссылки»(смещения) на «сегменты», а потом просто обменивал значения этих ссылки и делал лок только на время такого обмена. Не думаю, что вам не хватит этого. Использовал кажется System V IPC, но для posix не должно сильно отличаться.

anonymous
()
Ответ на: комментарий от vromanov

Ок, но я вас сразу предупреждаю, что вот то, что я написал - есть предел возможностей при использовании c++11 и чтоб было переносимо. Более того, это предел возможностей без использования лютого ассемблера. то есть очередь где много чтецов - уже на ассемблере. но futex на неё уже с трудом вешается

ckotinko ☆☆☆
()
Последнее исправление: ckotinko (всего исправлений: 1)
Ответ на: комментарий от ckotinko

Эм. Так ТС нужна shared memory или нет?

anonymous
()
Ответ на: комментарий от anonymous

Забрать из очереди в shared memory без блокировки не получится.

А чем в данном случае шаред от нешаред отличается?

mv ★★★★★
()
Ответ на: комментарий от mv

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

vromanov ★★★
() автор топика
Ответ на: комментарий от anonymous

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

vromanov ★★★
() автор топика
Ответ на: комментарий от mv

Тем, что у вас нет атомарных операций для изменения данных в shared memory. По крайней мере API для shared memory таких гарантий не дает.

anonymous
()
Ответ на: комментарий от vromanov

Верно. Но хотелось бы иметь какие-то более понятные, документированые, гарантии распространения видимости. как volatile например

vertexua ★★★★★
()
Последнее исправление: vertexua (всего исправлений: 1)
Ответ на: комментарий от vromanov

Так для разных процессов shared memory будет мапиться на разные адреса. Хотя для большинства реализаций скорее всего все будет ок, API для shared memory гарантий не дает. Если я ошибаюсь - дайте ссылку на доку.

anonymous
()
Ответ на: комментарий от anonymous

Чем мешают разные адреса? Использовать смещения. Мы уже очень активно используем shared memory. У нас в ней куча всяких объектов лежит: очереди, статистические счетчики, база данных, всякие хранилища машины состояний, пул буферов, фильтры для логирования и трасировки итд.

vromanov ★★★
() автор топика
Ответ на: комментарий от vromanov

Пусть себе лежат. Доступ к ним из разных процессов требует синхронизации. Покажите мне доку, из которой будет следовать, что cas успешно будет работать в случае данных в shared memory.

anonymous
()
Ответ на: комментарий от anonymous

Покажите мне доку, где написано что shared memory отличается от обычной памяти, настолько что там не будет работать CAS. Также подумайте, где находятся семафоры и другие IPC объекты.

vromanov ★★★
() автор топика
Ответ на: комментарий от anonymous

Скорее всего будет все хорошо. Дело в том что cas работает хорошо для разных потоков. В linux потоки и процессы - одно и то же, оба порождаются низкоуровневым вызовом clone(), но с разными опциями. Грубо говоря поток - процесс, который полностью разделяет память с родителем. Тут грешить можно только на разные опции clone() и это можно исследовать

vertexua ★★★★★
()
Ответ на: комментарий от anonymous

Читайте про виртуальное адресное пространство.

Но ведь разделяемая память скорее имеет отношение к отображению файлов в память, а это уже делает не процессор, а ядро. Так что у меня остается вопрос, кто и как гарантирует мне атомарность операций над shared memory

anonymous
()
Ответ на: комментарий от vertexua

Да, но тут-то речь о механизме разделяемой памяти, а не об общей памяти между потомком и родителем.

anonymous
()
Ответ на: комментарий от anonymous

Память с ядром всегда связана. Например страница будет выгружена в своп. Что означает что для процессора она обозначена будет только для чтения. Ошибка при записи будет поймана ядром и страница будет считана с диска. Тут процессор дружит с ядром.

vertexua ★★★★★
()
Ответ на: комментарий от vertexua

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

anonymous
()
Ответ на: комментарий от vertexua

Да все нормально работает. Даже без clone - т.е. процессы могут быть совсем разными, а не результатами fork. В cmpxchg(x86) могут передаваться разные адреса, но ссылаются они при этом на один и тот-же физический адрес памяти. Смотрите, например, реализацию именованых семафоров в NPTL.

vromanov ★★★
() автор топика
Ответ на: комментарий от vromanov

В cmpxchg(x86) могут передаваться разные адреса, но ссылаются они при этом на один и тот-же физический адрес памяти.

Так будет дока, где API для shared memory гарантирует это?

anonymous
()
Ответ на: комментарий от vromanov

Какие очевидные вещи, если возможна реализация, которая будет удволетворять спецификации и при этом нарушать ваше предположение.

У нас например, софт верифицируется, потому скорее всего такой хак зарубят...

anonymous
()
Ответ на: комментарий от anonymous

Она использует атомарные операции с shared memory. Например, именованные семафоры создают файлик в /dev/shm и указатель на семафор, на самом деле указывает на shared memory.

vromanov ★★★
() автор топика
Ответ на: комментарий от anonymous

Тем, что у вас нет атомарных операций для изменения данных в shared memory. По крайней мере API для shared memory таких гарантий не дает.

Какие такие специальные атомарные операции для shared memory?

mv ★★★★★
()
Ответ на: комментарий от vromanov

Это тоже реализация(поменяется что-то в ядрышке, поменяют и они). И только в linux. И напоминаю, я не спорю с тем, что это работает. Я пытаюсь понять, кто и как это гарантирует.

anonymous
()
Ответ на: комментарий от anonymous

Так будет дока, где API для shared memory гарантирует это?

«Intel® 64 and IA-32 Architectures, Software Developer's Manual, Combined Volumes: 1, 2A, 2B, 3A and 3B»

mv ★★★★★
()
Ответ на: комментарий от mv

Так вот их и нет. А вопрос заключается в том, гарантируется ли API для shared memory, что разные адреса для shared memory в процессах будут мапиться на один и тот же физический адрес?

anonymous
()
Ответ на: комментарий от anonymous

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

Да у вас, мой друг, серьёзная дыра в образовании! К вышеотмеченному талмуду могу дополнительно порекомендовать What every programmer should know about memory и какой-нибудь букварь по организации компьютеров.

mv ★★★★★
()
Ответ на: комментарий от anonymous

Так вот их и нет. А вопрос заключается в том, гарантируется ли API для shared memory, что разные адреса для shared memory в процессах будут мапиться на один и тот же физический адрес?

Ну, во-первых, само название shared неиллюзорно намекает, что память - она одна и та же для всех, кто ей пользуется. Вы тут пытаетесь протолкнуть что-то типа replicated memory, но в топике разговор идёт именно про shared. Т.е. одинаковый набор физических страниц, отображённых в нескольких виртуальных адрессных пространствах.

mv ★★★★★
()
Ответ на: комментарий от mv

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

anonymous
()
Ответ на: комментарий от anonymous

Можно и в байте сделать 13 бит. Значит, внесем такую систему в список неподдерживаемых. У меня нет задачи обеспечить 100% портабельность кода. Меня устроит даже конкретная версия линукса на конкретном оборудовании.

vromanov ★★★
() автор топика
Ответ на: комментарий от vromanov

Я не пытаюсь вас отговаривать, если что. Я просто пытался выяснить то, что меня интересует=)

anonymous
()
Ответ на: комментарий от mv

решение тут возможно только одно, в силу ограничений x86.

ckotinko ☆☆☆
()
Ответ на: комментарий от vertexua

это всего лишь память. всего-то навсего - страницы памяти, отмапленные в адресное пространство. неужели писание программ на жабе делает эти очевидные вещи непонятными?

ckotinko ☆☆☆
()
Ответ на: комментарий от anonymous

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

Здравый смысл.

mv ★★★★★
()
Ответ на: комментарий от ckotinko

Упорыш, о кешах процессора слышал? Так вот если у тебя переменная с многих потоков без синхронизации, то volatile не помешало бы. А куда ты volatile лепить будешь в shared памяти? Вот это и обсуждаем, надо лепить, не надо лепить, когда и как.

vertexua ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.