Спинлок билета Fair Reader-Writer в C ++ работает медленно

Question

Недавно я реализовал честный тик-спинлок читателя-писателя в C ++. Код довольно прост, и я подумал, что он работает отлично. Я интегрировал спинлок в более крупное приложение и заметил, что в некоторых редких случаях код работает очень медленно, в большинстве случаев он работает очень быстро. Я знаю, что это происходит из-за спин-блокировки, потому что, если я немедленно заменю ее простой спин-блокировкой чтения-записи (несправедливо и без билета), код внезапно просто запускается намного быстрее. Это случилось несколько раз на разных машинах. Я знаю, что такие блокировки могут работать медленно, если вы запускаете их с большим количеством потоков, чем с ядрами, но я запускал их с 16 потоками на машине с 48 ядрами. Я не смог воспроизвести проблему на своем ноутбуке с 4 потоками и 4 ядрами. Вот код:

    inline size_t rndup(size_t v) {

        v--;
        v |= v >> 1;
        v |= v >> 2;
        v |= v >> 4;
        v |= v >> 8;
        v |= v >> 16;
        v |= v >> 32;
        v++;

        return v;
    }    

    class SpinLockRW_MCS {

        public:

            SpinLockRW_MCS(const size_t nb_readers) :   writer(nullptr), lock_pool(nullptr), it_lock_pool(0),
                                                        load_lock_pool(0), mask_it(rndup(2 * nb_readers + 1) - 1),
                                                        padding1{0}, padding2{0}, padding3{0}, padding4{0} {

                if (nb_readers <= std::thread::hardware_concurrency()){

                    lock_pool = new Lock[mask_it + 1];
                    lock_pool[0].is_locked = false;
                }
            }

            ~SpinLockRW_MCS() {

                clear();
            }

            inline void clear() {

                if (lock_pool != nullptr){

                    delete[] lock_pool;
                    lock_pool = nullptr;
                }

                writer = nullptr;

                it_lock_pool = 0;
                load_lock_pool = 0;
            }

            inline void acquire_reader() {

                uint_fast32_t retry = 0;

                const size_t prev_reader_id = it_lock_pool.fetch_add(1) & mask_it;
                const size_t new_reader_id = (prev_reader_id + 1) & mask_it;

                while (lock_pool[prev_reader_id].is_locked){

                    if (++retry > 100) this_thread::yield();
                }

                ++load_lock_pool;

                lock_pool[prev_reader_id].is_locked = true;
                lock_pool[new_reader_id].is_locked = false;
            }

            inline void release_reader() {

                --load_lock_pool;
            }

            inline void acquire_writer() {

                uint_fast32_t retry = 0;

                const size_t prev_reader_id = it_lock_pool.fetch_add(1) & mask_it;
                const size_t new_reader_id = (prev_reader_id + 1) & mask_it;

                while (lock_pool[prev_reader_id].is_locked){

                    if (++retry > 100) this_thread::yield();
                }

                while (load_lock_pool){

                    if (++retry > 100) this_thread::yield();
                }

                lock_pool[prev_reader_id].is_locked = true;

                writer = &lock_pool[new_reader_id];
            }

            inline void release_writer() {

                writer->is_locked = false;
            }

            inline void release_writer_acquire_reader() {

                ++load_lock_pool;

                writer->is_locked = false;
            }

        private:

            struct Lock {

                std::atomic<bool> is_locked;
                const int padding[15];

                Lock() : is_locked(true), padding{0} {}
            };

            Lock* writer;
            const int padding1[14];
            Lock* lock_pool;
            const int padding2[14];
            const size_t mask_it;
            const int padding3[14];
            std::atomic<size_t> it_lock_pool;
            const int padding4[14];
            std::atomic<size_t> load_lock_pool;
    };

Любое предложение будет с благодарностью! Спасибо!

Answer 1

Трудно оценить проблему, не имея более подробной информации, но вот мой выстрел в темноте: я подозреваю, что в вашем сценарии читатели должны очень часто приобретать блокировки (в противном случае вам, вероятно, будет лучше с традиционной блокировкой),Вот ваша проблема:

Любой отдельный поток может лишить всех других ресурсов.

Это верно как для читателей, так и для писателей, хотя в несправедливом алгоритме этообычно верно только для писателей.Проблема в вашей ситуации возникает, когда у вас есть несколько читателей, стоящих в очереди для доступа для чтения.Каждый поток будет ждать, пока предыдущая блокировка станет доступной (while (lock_pool[prev_reader_id].is_locked) ...).Если они могут получить эту блокировку, все в порядке, но вы попадете в беду, как только один поток не сможет ее получить.Все потоки читателей стоят в очереди, чтобы увидеть, как их предшественники переключаются на false.Каждый из них зависит от своего прямого предшественника.

Теперь представьте, что первый читатель не может получить блокировку.Это будет вращаться некоторое время и в конечном итоге yield().Это фактически означает, что ваш поток больше не работает.Операционная система удалила его из очереди планирования, и он не будет работать в течение long времени (остальная часть их временного интервала, что является длинным по сравнению с тем, сколько времени требуется для завершения 100 вращений).Как следствие, полная цепочка ожидающих потоков с большой вероятностью перейдет в yield.

В конце концов флаг, ожидающий первого потока, переключится на false.Но ваш планировщик сейчас в затруднительном положении.Вокруг него куча нитей, но они вращаются только очень короткое время, прежде чем снова начинают приносить доход.Здесь ожидается, что для всех, кроме первой нити в цепочке, если они будут выбраны, они почти наверняка будут обречены на бездействие для еще одного полного временного интервала.Как следствие, если это случается с потоком в начале цепочки ожидающих потоков, вы также осуждаете все другие потоки в цепочке ждать как минимум столько же времени.

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

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

Answer 2

Моя ставка в том, что ваша проблема где-то в следующих строчках:

if (++retry > 100) this_thread::yield();

Я знаю, что именно так вы планируете быть «оптимистичными», какими бы жестко закодированными (произвольными) ни были значения, подобные этим («100» в этомcase), как правило, указывает на недостаток дизайна при работе с этим классом проблем - как вы говорите, вы видите проблему только в другой системе, которая может быть симптомом этого (поскольку при этом значенииработает в вашей системе).Это, в свою очередь, указывает на this_thread::yield() как указание на часть проблемы.