C ++ 11/14/17: блокировка чтения / записи ... без блокировки для читателей?

Question

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

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

Вместо этого было бы несколько операций Atom c (128-битный CAS) для считывателя и мьютекс для писателя. У меня будет две копии структуры данных, одна только для чтения для обычно успешных запросов, и идентичная копия, которая будет обновляться под защитой мьютекса. Как только данные были вставлены в доступную для записи копию, мы делаем ее новой читаемой копией. Затем старая читаемая копия вставляется по очереди, как только все ожидающие чтения читатели закончили ее читать, и писатель вращает число читателей, оставшихся до нуля, затем по очереди изменяет ее и, наконец, освобождает мьютекс.

Или что-то в этом роде.

Что-нибудь в этом роде существует?

Answer 1

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

С точки зрения гарантий прогресса, разница между ними заключается в том, что первый не блокируется для читателей, а второй - без ожидания. Оба блокируют писателей.

Answer 2

Если ваши данные вписываются в 64-битное значение, большинство систем могут дешево и с атомарной считывать / записывать данные, поэтому просто используйте std::atomic<my_struct>.

Для smalli sh и / или нечасто Записанные данные , есть несколько способов сделать читателей действительно доступными только для чтения для общих данных, без необходимости выполнения каких-либо операций atomi c RMW на общем счетчике или чем-то еще. Это позволяет масштабировать на стороне чтения многие потоки, при этом читатели не конкурируют друг с другом (в отличие от 128-битного атоми c, считываемого на x86 с использованием lock cmpxchg16b или с использованием RWlock).

В идеале - просто дополнительный уровень косвенного обращения через указатель atomic<T*> (RCU) или просто дополнительную загрузку + сравнение и ветвление (SeqLock); нет атомов c RMW или барьеры памяти сильнее, чем acq / rel или что-либо еще на стороне чтения.

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

Если ваши данные больше и / или изменяются чаще, одна из стратегий, предложенных в других ответах , требует, чтобы читатель все еще брал RWlock на что-то или атомное увеличение счетчик будет более подходящим. Это не будет идеально масштабироваться, потому что каждому читателю все еще нужно получить эксклюзивное право владения строкой общего кэша, содержащей блокировку или счетчик, чтобы он мог ее изменить, но такого понятия, как бесплатный обед, не существует.

RCU

Похоже, вы на полпути к изобретению RCU (Read Copy Update), где вы обновляете указатель на новую версию.

Но помните, что безблокировочный считыватель может Задержка после загрузки указателя, поэтому у вас есть проблема освобождения. Это сложная часть RCU. В ядре это может быть решено с помощью син c точек, где вы знаете, что нет читателей старше некоторого времени t и, следовательно, можете освободить старые версии. Есть несколько реализаций в пользовательском пространстве. https://en.wikipedia.org/wiki/Read-copy-update и https://lwn.net/Articles/262464/.

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

---

SeqLock

Если ваши данные малы (например, 64-битная временная метка на 32-битной машине ), еще одним хорошим вариантом является SeqLock. Читатели проверяют счетчик последовательности до / после не-атомного c копирования данных в личный буфер. Если счетчики последовательности совпадают, мы знаем, что разрывов не было. (Авторы взаимно исключают каждого с отдельным мьютексом). Реализация счетчика с 64-битными атомами c с 32-битными атомами / как реализовать блокировку секвлока с использованием библиотеки c ++ 11 atomi c .

Это немного хакерства в C ++ для написания чего-то, что может эффективно компилироваться в неатомную копию c, которая может иметь разрыв, потому что это неизбежно является гонкой данных UB. (Если только вы не используете std::atomic<long> с mo_relaxed для каждого блока отдельно, но затем вы отказываете компилятору в использовании movdqu или чего-то другого для копирования 16 байтов одновременно.)

A SeqLock заставляет читателя копировать всю вещь (или, в идеале, просто загружать ее в регистры) при каждом чтении, поэтому она всегда подходит только для небольшой структуры или 128-битного целого или чего-то еще. Но для менее чем 64 байта данных это может быть довольно хорошо, лучше, чем когда читатели используют lock cmpxchg16b для 128-битных данных, если у вас много читателей и нечастые записи.

Хотя это не без блокировки: писатель, который спит во время модификации SeqLock, может получить читателей попробую повторить попытку до бесконечности. Для небольшого SeqLock окно маленькое, и, очевидно, вы хотите, чтобы все данные были готовы до того, как вы выполните первое обновление счетчика последовательности, чтобы минимизировать вероятность прерывания прерывания записи в середине обновления.

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

Answer 3

Оказывается, что двухструктурное решение, о котором я думал, имеет сходство с http://concurrencyfreaks.blogspot.com/2013/12/left-right-concurrency-control.html

Вот конкретная c структура данных и псевдокод, которые я имел в виду.

У нас есть две копии некоторой произвольной структуры данных, называемой MyMap, и два указателя из группы из трех указателей указывают на эти два. Первоначально на один указывает achReadOnly [0] .pmap, а на другой - pmapMutable.

Краткое примечание к achReadOnly: у него нормальное состояние и два временных состояния. Нормальное состояние будет (WLOG для ячейки 0/1):

achReadOnly = { { pointer to one data structure, number of current readers },
                { nullptr, 0 } }
pmapMutable = pointer to the other data structure

Когда мы закончили мутировать «другой», мы сохраняем его в неиспользуемом слоте массива, так как он следующий Поколение только для чтения, и читатели могут начать доступ к нему.

achReadOnly = { { pointer to one data structure, number of old readers },
                { pointer to the other data structure, number of new readers } }
pmapMutable = pointer to the other data structure

Писатель затем очищает указатель на «один», предыдущее поколение только для чтения, вынуждая читателей к go следующему Поколение одно. Мы перемещаем это в pmapMutable.

achReadOnly = { { nullptr, number of old readers },
                { pointer to the other data structure, number of new readers } }
pmapMutable = pointer to the one data structure

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

struct CountedHandle {
    MyMap*   pmap;
    int      iReaders;
};

// Data Structure:
atomic<CountedHandle> achReadOnly[2];
MyMap* pmapMutable;
mutex_t muxMutable;

data Read( key ) {
    int iWhich = 0;
    CountedHandle chNow, chUpdate;

    // Spin if necessary to update the reader counter on a pmap, and/or
    // to find a pmap (as the pointer will be overwritten with nullptr once
    // a writer has finished updating the mutable copy and made it the next-
    // generation read-only in the other slot of achReadOnly[].

    do {
        chNow = achReadOnly[ iWhich ];
        if ( !chNow .pmap ) {
            iWhich = 1 - iWhich;
            continue;
        }
        chUpdate = chNow;
        chNow.iReaders++;
    } while ( CAS( ach[ iWhich ], chNow, chUpdate ) fails );

    // Now we've found a map, AND registered ourselves as a reader of it atomicly.
    // Importantly, it is impossible any reader has this pointer but isn't
    // represented in that count.

    if ( data = chnow.pmap->Find( key ) ) {
        // Deregister ourselves as a reader.
        do {
            chNow = achReadOnly[ iWhich ];
            chUpdate = chNow;
            chNow.iReaders--;
        } while ( CAS( ach[ iWhich ], chNow, chUpdate ) fails );

        return data;
    }

    // OK, we have to add it to the structure.

    lock muxMutable;
    figure out data for this key
    pmapMutable->Add( key, data );

    // It's now the next-generation read-only.  Put it where readers can find it.
    achReadOnly[ 1 - iWhich ].pmap = pmapMutable;

    // Prev-generation readonly is our Mutable now, though we can't change it
    // until the readers are gone.
    pmapMutable = achReadOnly[ iWhich ].pmap;

    // Force readers to look for the next-generation readonly.
    achReadOnly[ iWhich ].pmap = nullptr;

    // Spin until all readers finish with previous-generation readonly.
    // Remember we added ourselves as reader so wait for 1, not 0.

    while ( achReadOnly[ iWhich ].iReaders > 1 }
        ;

    // Remove our reader count.
    achReadOnly[ iWhich ].iReaders = 0;

    // No more readers for previous-generation readonly, so we can now write to it.
    pmapMutable->Add( key, data );

    unlock muxMutable;

    return data;

}

Answer 4

Решение, которое мне пришло:

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

Если вы НЕ найдете свои данные, вы получите мьютекс для мастер-копии.

Это может иметь много новых вставки в него из других потоков (возможно, включая необходимые данные!). Проверьте, есть ли в нем ваши данные, а если нет, вставьте.

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

Читатели могут читать весь день параллельно, даже когда происходят обновления, без блокировок . Блокировка необходима только при записи (или иногда при догонении). Этот общий подход будет работать для широкого спектра базовых структур данных. QED

---

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

Однако данные, найденные индексом Если это только для чтения, нужно иметь только одну копию, на которую ссылаются многие индексы. (К счастью, это мой случай.)

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

Наконец, «скопировать все последние обновления» было бы полезно, если бы все новые данные, добавленные в структуру, были, скажем, помещены в конец вектора, заданного таким образом скажем, у вас есть 4000 записей в вашей локальной копии, в главной копии 4020, вы можете с помощью нескольких машинных циклов найти 20 объектов, которые нужно добавить. (К счастью, это мой случай.)