Можно ли читать и проверять общую память без мьютексов?

В Linux я использую shmget и shmat для настройки сегмента общей памяти, в который один процесс будет записывать, а один или несколько процессов будут читать. Совместно используемые данные имеют размер несколько мегабайт и при обновлении полностью перезаписываются; он никогда не обновляется частично.

У меня есть сегмент общей памяти, выложенный следующим образом:

    -------------------------
    | t0 | actual data | t1 |
    -------------------------

где t0 и t1 — это копии времени, когда модуль записи начал обновление (с достаточной точностью, чтобы гарантировать, что последующие обновления будут иметь разное время). Модуль записи сначала записывает в t1, затем копирует данные, а затем записывает в t0. Читатель, с другой стороны, считывает t0, затем данные, затем t1. Если считыватель получает одинаковое значение для t0 и t1, он считает данные согласованными и достоверными, если нет, он пытается снова.

Гарантирует ли эта процедура, что если читатель думает, что данные достоверны, то это действительно так?

Нужно ли мне беспокоиться о внеочередном выполнении (OOE)? Если да, то сможет ли читатель, использующий memcpy для получения всего сегмента разделяемой памяти, преодолеть проблемы OOE на стороне читателя? (Это предполагает, что memcpy выполняет копирование линейно и по возрастанию в адресном пространстве. Верно ли это предположение?)


c++ linux shared-memory concurrency locking
person Bribles    schedule 31.03.2010    source источник
comment
Зачем это делать? Мьютексы довольно дешевы. Кроме того, если вы боитесь накладных расходов, вы можете придумать синхронизацию на основе атомарных типов (как вы пытаетесь сделать с t0 и t1).   -  person pajton    schedule 01.04.2010
comment
Почему? Потому что я ленивый и пытался заставить работать самое простое. Также я не хочу, чтобы писатель когда-либо ждал блокировки. У него есть другая обработка, это код, который я изначально не писал, и я не склонен модифицировать его, чтобы он мог ждать, пока читатели закончат чтение. Для меня не важно, чтобы читатели получали непротиворечивые данные всякий раз, когда они читают, просто чтобы они знали, согласуются эти данные или нет.   -  person Bribles    schedule 01.04.2010

Ответы (2)


arrow_upward
2
arrow_downward

Джо Даффи дает точно такой же алгоритм и называет его: "Масштабируемая схема чтения/записи с оптимистичной повторной попыткой".

Это работает.
Вам нужно два поля с порядковыми номерами.

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

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

Какие инструкции необходимы для этого, зависит от архитектуры. Например. на x86/x64 из-за относительно надежных гарантий в этом конкретном случае вообще не нужны барьеры, специфичные для конкретной машины*.

* по-прежнему необходимо убедиться, что компилятор/JIT не возится с загрузками и сохранениями, например. с помощью volatile (который имеет другое значение в Java и C#, чем в ISO C/C++. Однако компиляторы могут различаться. Например, при использовании VC++ 2005 или выше с volatile было бы безопасно делать вышеописанное. См. "Специфический для Microsoft" раздел. быть выполнено с другими компиляторами также на x86/x64.Сгенерированный ассемблерный код должен быть проверен, и нужно убедиться, что доступ к t0 и t1 не устранен или перемещается компилятором.)

Кроме того, если вам когда-нибудь понадобится MFENCE, lock or [TopOfStack],0 может быть лучшим вариантом, в зависимости от ваших потребностей.

person Andras Vass    schedule 01.04.2010
comment
Вы случайно не знаете, есть ли у этой техники название? Кроме того, барьеры памяти необходимы из-за современных конвейерных чрезмерно сложных архитектур, верно? Если бы этот код работал на 8086 или действительно простом микроконтроллере, то не были бы барьеры памяти ненужными? Наконец, если копирование данных выполняется с помощью memcpy, а вызов функции находится между чтением/записью метки времени, не будет ли перемещение мегабайтов данных в сортировке memcpy всегда делать операции с меткой времени последовательными? - person Bribles; 02.04.2010
comment
@Bribles: барьеры необходимы, потому что архитектура реализует более слабую модель согласованности с общей памятью, чем последовательная согласованность. Это как таковое не имеет ничего общего с конвейерной обработкой или OoO, но позволяет нескольким процессорам эффективно обращаться к системе памяти параллельно. См., например. hpl.hp.com/techreports/Compaq-DEC/ WRL-95-7.pdf . На однопроцессорном процессоре барьеры не нужны, потому что весь код выполняется последовательно на одном процессоре. - person janneb; 02.04.2010
comment
@Bribles: Проблема с отметками времени заключается в том, что 1) если производительность имеет значение, получение текущего времени происходит медленнее, чем увеличение счетчика 2) что, если время изменяется в обратном направлении (например, ntpd перемещает часы назад, чтобы компенсировать дрейф часов?). Ну, в Linux 2) по крайней мере можно исправить с помощью clock_gettime(CLOCK_MONOTONIC, ...). - person janneb; 02.04.2010
comment
@janneb: я даже отдаленно не рассматривал возможность использования здесь реального значения часов (даже CLOCK_MONOTONIC просто замедлит работу, не предоставив никакой дополнительной ценности). Я думаю, что недоразумение происходит из-за этого. :S Вы правы, я должен был быть более точным в терминологии в первую очередь. :П - person Andras Vass; 02.04.2010
comment
Вы не можете сказать, что ему не нужны барьеры памяти, и в то же время утверждать, что он работает только с MSVC или Java volatile. Потому что эти системы используют барьеры памяти с их volatile. Так что ДА, вам нужны барьеры памяти. - person Zan Lynx; 28.08.2018

arrow_upward
5
arrow_downward

Современное оборудование на самом деле совсем не последовательное. Таким образом, это не гарантирует работу, если вы не выполняете барьеры памяти в соответствующих местах. Барьеры необходимы, потому что архитектура реализует более слабую модель согласованности с общей памятью, чем последовательная согласованность. Это как таковое не имеет ничего общего с конвейерной обработкой или OoO, но позволяет нескольким процессорам эффективно обращаться к системе памяти параллельно. См., например. Модели согласованности с общей памятью: руководство. На однопроцессорном процессоре барьеры не нужны, потому что весь код выполняется последовательно на одном процессоре.

Кроме того, нет необходимости иметь два поля времени, счетчик последовательности, вероятно, является лучшим выбором, поскольку нет необходимости беспокоиться о том, что два обновления настолько близки, что они получают одну и ту же отметку времени, а обновление счетчика происходит намного быстрее, чем получение Текущее время. Кроме того, нет никаких шансов, что часы переместятся назад во времени, что может произойти, например, когда ntpd подстраивается под дрейф часов. Хотя эту последнюю проблему можно решить в Linux с помощью clock_gettime(CLOCK_MONOTONIC, ...). Другое преимущество использования счетчиков последовательности вместо меток времени заключается в том, что вам нужен только один счетчик последовательности. Модуль записи увеличивает счетчик как перед записью данных, так и после завершения записи. Затем считыватель считывает порядковый номер, проверяет, является ли он четным, и если да, то считывает данные и, наконец, снова считывает порядковый номер и сравнивает его с первым порядковым номером. Если порядковый номер нечетный, это означает, что идет запись, и нет необходимости читать данные.

Ядро Linux использует блокирующий примитив, называемый seqlocks, который делает что-то подобное вышеописанному. Если вы не боитесь «загрязнения GPL», вы можете найти реализацию в Google; Таким образом, это тривиально, но фокус в том, чтобы правильно установить барьеры.

person janneb    schedule 01.04.2010
comment
Если предположить, что я использовал соответствующие инструкции по сборке [SLM]FENCE до и/или после операций чтения и записи, разве мне не понадобятся 2 копии счетчика последовательностей (seqc)? Если бы у меня был только один, писатель мог бы начать с установки seqc, начать запись данных, затем ОС переключает процессы, и запускается читатель, читает seqc и большую часть данных (некоторые обновлены, некоторые нет), а затем переключается обратно на писатель, который заканчивает, спиной к читателю, который заканчивает. Читатель получает один и тот же seqc оба раза, но все равно получает неверные данные. - person Bribles; 02.04.2010
comment
См. ссылку в Википедии; модуль записи увеличивает seqc перед запуском обновления и после его завершения. Затем читатель проверяет, является ли seqc четным или нечетным, в дополнение к сравнению seqc до и после чтения. - person janneb; 02.04.2010
comment
@andras: Действительно, именно поэтому я написал ... подсчет последовательности, вероятно, лучший выбор, поскольку не нужно беспокоиться о том, что два обновления настолько близки, что они получают одинаковую отметку времени ... - person janneb; 02.04.2010
comment
@janneb: Кажется, я полностью пропустил предложение между более быстрыми, чем ... и Эта последняя проблема - что, конечно, делает последнюю проблему означающей что-то совершенно другое. Извини, моя ошибка. :П - person Andras Vass; 02.04.2010
comment
@janneb: На наиболее распространенном настольном оборудовании (x86/x64) модель памяти на самом деле достаточно сильна, чтобы поддерживать это без явных ограничений. Прелесть подхода OP с двумя полями заключается в том, что вам не нужны никакие барьеры на x86/x64. Если компилятор не переупорядочивает/оптимизирует доступ к памяти, это будет работать OOTB на x86/x64. Ссылки: 1. bluebytesoftware.com/blog/2009/06/05/ 2. blogs.msdn.com/kangsu/archive/2007/07/16/ - person Andras Vass; 07.04.2010
comment
@andras: В ссылках используется volatile в C# и VC++, которые, как вы упомянули в своем ответе, имеют другую семантику в C# и VC++, чем в ISO C++ и GCC. Я считаю, что Java имеет семантику volatile, аналогичную C# и VC++, и, кажется, использует XCHG или MFENCE для хранения volatile. Однако вы правы в том, что x86 обеспечивает довольно сильную модель. Я не уверен на 100%, но я думаю, что вы правы, что этот конкретный алгоритм не нуждается в каких-либо заборах на x86, поскольку архитектура гарантирует порядок хранения (хранилища от процессора всегда видны в порядке программы другими процами). - person janneb; 08.04.2010
comment
@janneb: Даже в мире Java, с точки зрения volatile, LOCK:ADD [TopOfStack],0 может понадобиться только в том случае, если за энергозависимым хранилищем следует энергозависимое чтение. Другие барьеры не используются в поваренной книге JSR-133. Цитата: ... StoreLoad строго необходим только для отделения хранилищ от последующих загрузок тех же местоположений, которые были сохранены до барьера. Поведение, которое вы видите, может быть объяснено тем, что JIT придерживается консервативной стратегии, предложенной Дагом Ли. Возможно, ваш JIT создает забор для всех энергозависимых хранилищ. Однако в этом нет необходимости. - person Andras Vass; 08.04.2010
comment
@janneb: ... и в этом конкретном случае они действительно не нужны для x86/x64. (Забыл добавить ссылку на поваренную книгу — не то чтобы ее было так сложно найти в гугле — но вот она: gee.cs.oswego.edu/dl/jmm/cookbook.html ) - person Andras Vass; 08.04.2010
comment
@janneb: Единственное, что необходимо здесь, это убедиться, что компилятор генерирует самый простой - и, казалось бы, неэффективный - машинный код, который можно ожидать, и не выполняет хитрых оптимизаций. - person Andras Vass; 08.04.2010