«Lock-free, or not lock-free, that is the question» или «Здоровый сон хуже горькой редьки»

    На написание данной статьи меня подвигли комментарии к статье "Как правильно и неправильно спать".


    Речь в данной статье пойдёт о разработке многопоточных приложений, применимости lock-free к некоторым кейсам возникшим в процессе работы над LAppS, о функции nanosleep и насилии над планировщиком задач.


    NB: Всё обсуждаемое касается разработки на C++ под Linux, но может быть применимо ко всем POSIX.1-2008 совместимым системaм (с оглядкой на конкретную реализацию).

    Вобщем всё довольно сумбурно, надеюсь ход мысли в изложении будет понятен. Если интересно то прошу под кат.


    Событийно- ориентированное ПО всегда чего-то ждёт. Будь то GUI или сетевой сервер, они ждут каких-либо событий: поступления ввода с клавиатуры, события мыши, поступление пакета данных по сети. Но всякое ПО ждёт по разному. Lock-free системы вообще не должны ждать. По крайней мере использование lock-free алгоритмов, должно происходить там где ждать не нужно, и даже вредно. Но ведь мы говорим о конкурентных (много-поточных) системах, и как ни странно lock-free алгоритмы тоже ждут. Да они не блокируют исполнение параллельных потоков, но сами при этом ждут возможности сделать что-либо без блокировки.


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


    Поведение мьютекса в случае конкурентного lock() также как и sem_wait() в Linux, помещает ожидающий поток в конец очереди планировщика задач, и когда она оказывается в топ-е, проверка повторяется и без возврата в userland, поток помещается опять в очередь, если ожидаемое событие ещё не произошло. Это очень важный момент.


    И я решил проверить, могу-ли я отказаться от std::mutex и POSIX-семафоров, эмулируя их с помощью std::atomic, перенеся нагрузку по большей части в userland. На самом деле не удалось, но обо всём по порядку.


    Во первых у меня есть несколько секций в которых эти эксперименты могли-бы оказаться полезными:


    • блокировки в LibreSSL (case 1);
    • блокировки при передаче payload полученных пакетов, в приложения Lua (case 2);
    • Ожидание событий о поступлении payload готовых для обработки приложениями Lua (case 3).

    Начнём с "неблокирующих-блокировок". Давайте напишем свой мьютекс с использованием атомиков, как это показано в некоторых выступлениях Х. Саттера (оригинального кода нет, поэтому по памяти и поэтому код на 100% с оригиналом не совпадает, да и у Саттера этот код относился к прогрессу C++20, поэтому есть отличия). И несмотря на простоту этого кода, в нём есть подводные камни.


    #include <atomic>
    #include <pthread.h>
    
    namespace test
    {
        class mutex
        {
        private:
          std::atomic<pthread_t> mLock;
        public:
          explicit mutex():mLock{0}
          {
          }
          mutex(const mutex&)=delete;
          mutex(mutex&)=delete;
    
          void lock()
          {
            pthread_t locked_by=0; // в C++20 эта переменная будет не нужна, т.к. compare_exchange_strong сможет работать со значениями вместо референса в первом аргументе
            while(!mLock.compare_exchange_strong(locked_by,pthread_self()))
            {
              locked_by=0; // это тоже будет не нужно
            }
          }
    
          void unlock()
          {
            pthread_t current=pthread_self();
    
            if(!mLock.compare_exchange_strong(current,0))
            {
              throw std::system_error(EACCES, std::system_category(), "An attempt to unlock the mutex owned by other thread");
            }
          }
    
          const bool try_lock()
          {
            pthread_t unused=0;
            return mLock.compare_exchange_strong(unused,pthread_self());
          }
        };
    }

    В отличии от std::mutex::unlock(), поведение test::mutex:unlock() при попытке разблокировать из другого потока, — детерминированное. Будет выброшено исключение. Это хорошо, хоть и не соответствует поведению стандарта. А что в этом классе плохо? Плохо то, что метод test::mutex:lock() будет безбожно жрать ресурсы ЦП в выделенных потоку квотах времени, в попытках завладеть мьютексом, которым уже владеет другой поток. Т.е. цикл в test::mutex:lock() приведёт к бесполезной трате ресурсов ЦП. Каковы наши варианты выхода из этой ситуации?


    Мы можем воспользоваться sched_yield() (как предлагается в одном из коментариев к вышеупомянутой статье). Так-ли это просто? Во первых для того что-бы использовать sched_yield() необходимо что-бы потоки исполнения использовали политики SCHED_RR, SCHED_FIFO, для своей приоритезации в планировщике задач. В противном случае вызов sched_yield() будет бесполезной тратой ресурсов ЦП. Во вторых, очень частый вызов sched_yield() всё равно повышает расход ресурсов ЦП. Более того, использование real-time политик в вашем приложении, и при условии, что в системе нет других real-time приложений, ограничит очередь планировщика с выбранной политикой только вашими потоками. Казалось-бы, — это хорошо! Нет не хорошо. Вся система станет менее отзывчива, т.к. занята задачей с приоритетом. CFQ окажется в загоне. А ведь в приложении есть и другие потоки, и очень часто возникает ситуация, когда захвативший мьютекс поток, ставится в конец очереди (истекла квота), а поток который ждёт освобождения мьютекса прямо перед ним. В моих экспериментах (case 2) этот метод дал примерно те-же результаты (на 3.8% хуже), что и std::mutex, но система при этом менее отзывчива и расход ресурсов ЦП повышается на 5%-7%.


    Можно попытаться изменить test::mutex::lock() так (тоже плохо):


    void lock()
    {
      pthread_t locked_by=0;
      while(!mLock.compare_exchange_strong(locked_by,pthread_self()))
      {
         static thread_local const struct timespec pause{0,4}; // - можно поиграть с длительностью сна
    
         nanosleep(&pause,nullptr);
         locked_by=0; 
      }
    }

    Тут можно экспериментировать с длительностью сна в наносекундах, 4нс задержки оказались оптимальными для моего ЦП и падение производительности относительно std::mutex в том-же case 2, составило 1.2%. Не факт что nanosleep спал 4нс. На самом деле или больше (в общем случае) или меньше (если прерывался). Падение (!) потребления ресурсов ЦП составило 12%-20%. Т.е. это был такой здоровый сон.


    В OpenSSL и LibreSSL есть две функции устанавливающие коллбэки для блокирования при использовании этих библиотек в многопоточной среде. Выглядит это так:


    // Сам callback
    void openssl_crypt_locking_function_callback(int mode, int n, const char* file, const int line)
    {
      static std::vector<std::mutex> locks(CRYPTO_num_locks());
      if(n>=static_cast<int>(locks.size()))
      {
        abort();
      }
    
      if(mode & CRYPTO_LOCK)
        locks[n].lock();
      else
        locks[n].unlock();
    }
    
    //  назначение callback-a
    CRYPTO_set_locking_callback(openssl_crypt_locking_function_callback);
    
    // определение id
    CRYPTO_set_id_callback(pthread_self);

    А теперь самое страшное, использование вышеприведённого мьютекса test::mutex в LibreSSL снижает производительность LAppS почти в 2 раза. Причём независимо от варианта (пустой цикл ожидания, sched_yield(), nanosleep()).


    Вобщем case 2 и case 1 вычёркиваем, и остаёмся с std::mutex.


    Перейдём к семафорам. Есть множество примеров того как реализовать семафоры с помощью std::condition_variable. Все они используют std::mutex в том числе. И такие симуляторы семафоров медленнее (по моим тестам), чем системные POSIX семафоры.


    Поэтому сделаем семафор на атомиках:


        class semaphore
        {
         private:
          std::atomic<bool> mayRun;
          mutable std::atomic<int64_t> counter;
    
         public:
    
          explicit semaphore() : mayRun{true},counter{0}
          {
          }
    
          semaphore(const semaphore&)=delete;
          semaphore(semaphore&)=delete;
    
          const bool post() const
          {
            ++counter;
            return mayRun.load();
          }
    
          const bool try_wait()
          {
            if(mayRun.load())
            {
              if(counter.fetch_sub(1)>0)
                return true;
              else 
              {
                ++counter;
                return false;
              }
            }else{
              throw std::system_error(ENOENT,std::system_category(),"Semaphore is destroyed");
            }
          }
    
          void wait()
          {
            while(!try_wait())
            {
              static thread_local const struct timespec pause{0,4};
              nanosleep(&pause,nullptr);
            }
          }
    
          void destroy()
          {
            mayRun.store(false);
          }
    
          const int64_t decrimentOn(const size_t value)
          {
            if(mayRun.load())
            {
              return counter.fetch_sub(value);
            }else{
              throw std::system_error(ENOENT,std::system_category(),"Semaphore is destroyed");
            }
          }
    
          ~semaphore()
          {
            destroy();
          }
        };

    О, этот семафор оказывается многократно более быстрым чем системный семафор. Результат отдельного тестирования этого семафора с одним провайдером и 20 консамерами:


    OS semaphores test. Started 20 threads waiting on a semaphore
    Thread(OS): wakes: 500321
    Thread(OS): wakes: 500473
    Thread(OS): wakes: 501504
    Thread(OS): wakes: 502337
    Thread(OS): wakes: 498324
    Thread(OS): wakes: 502755
    Thread(OS): wakes: 500212
    Thread(OS): wakes: 498579
    Thread(OS): wakes: 499504
    Thread(OS): wakes: 500228
    Thread(OS): wakes: 499696
    Thread(OS): wakes: 501978
    Thread(OS): wakes: 498617
    Thread(OS): wakes: 502238
    Thread(OS): wakes: 497797
    Thread(OS): wakes: 498089
    Thread(OS): wakes: 499292
    Thread(OS): wakes: 498011
    Thread(OS): wakes: 498749
    Thread(OS): wakes: 501296
    OS semaphores test. 10000000 of posts for 20 waiting threads have taken 9924 milliseconds
    OS semaphores test. Post latency: 0.9924ns
    
    =======================================
    
    AtomicEmu semaphores test. Started 20 threads waiting on a semaphore
    Thread(EmuAtomic) wakes: 492748
    Thread(EmuAtomic) wakes: 546860
    Thread(EmuAtomic) wakes: 479375
    Thread(EmuAtomic) wakes: 534676
    Thread(EmuAtomic) wakes: 501014
    Thread(EmuAtomic) wakes: 528220
    Thread(EmuAtomic) wakes: 496783
    Thread(EmuAtomic) wakes: 467563
    Thread(EmuAtomic) wakes: 608086
    Thread(EmuAtomic) wakes: 489825
    Thread(EmuAtomic) wakes: 479799
    Thread(EmuAtomic) wakes: 539634
    Thread(EmuAtomic) wakes: 479559
    Thread(EmuAtomic) wakes: 495377
    Thread(EmuAtomic) wakes: 454759
    Thread(EmuAtomic) wakes: 482375
    Thread(EmuAtomic) wakes: 512442
    Thread(EmuAtomic) wakes: 453303
    Thread(EmuAtomic) wakes: 480227
    Thread(EmuAtomic) wakes: 477375
    AtomicEmu semaphores test. 10000000 of posts for 20 waiting threads have taken 341 milliseconds
    AtomicEmu semaphores test. Post latency: 0.0341ns
    

    T.e. этот семафор с почти бесплатным post(), который в 29 раз быстрее системного, ещё и очень быстр в пробуждении ждущих его потоков: 29325 пробуждений¹ в милисeкунду, против 1007 пробуждений в милисeкунду у системного. У него детерминированное поведение при разрушенном семафоре или разрушаемом семафоре. И естественно segfault при попытке использовать уже уничтоженный.


    (¹) На самом деле столько раз в милисeкунду поток не может быть отложен и пробужен планировщиком. Т.к. post() не блокирующий, при данном синтетическом тесте, wait() очень часто оказывается в ситуации когда и спать не нужно. При этом как минимум 7-мь потоков параллельно читают значение семафора.


    Но использование его в case 3 в LAppS приводит к потерям производительности независимо от времени сна. Он слишком часто просыпается для проверки, а события в LAppS поступают гораздо медленнее (латентность сети, латентность клиентской части генерирующей нагрузку, и т.д.). А проверять реже, — значит также потерять в производительности.


    Более того использование сна в подобных случаях и подобным образом совсем вредно, т.к. на другом железе результаты могут оказаться совсем другими (как и в случае ассемблерной инструкции pause), и для каждой модели ЦПУ ещё и придётся подбирать время задержки.


    Преимущество системных мьютекса и семафора, в том что поток исполнения не просыпается до тех пор пока событие (разблокировка мьютекса или инкремент семафора) не произойдёт. Лишние циклы ЦП не тратятся, — профит.


    Вобщем, всё от это лукавого, отключение iptables на моей системе даёт от 12% (с TLS) до 30% (без TLS) прироста производительности...

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 42

      0
      Позанудствуем чуток…

      Как говорится в священном писании:

      Issue 6

      IEEE Std 1003.1-2001/Cor 2-2004, item XBD/TC2/D6/26 is applied, adding pthread_t to the list of types that are not required to be arithmetic types, thus allowing pthread_t to be defined as a structure.

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

      class mutex
          {
          private:
            std::atomic<pthread_t> mLock;
          public:
            explicit mutex():mLock{0}
            {
            }
      


      Да и вообще в общем случае завернуть её в атомик не получится по той же самой причине.
        –1
        Во первых не у меня, а у Саттера на одном из слайдов (сейчас даже не вспомню в каком из видео о прогрессе в работе над C++20 он этот код показывал).

        Во вторых если мы говорим о Linux в первую очередь, то pthread_t это unsigned long int.

        В третьих, сомневаюсь, что этот элемент (XBD/TC2/D6/26), в какой-либо распространнённой ОС применяется. Я-бы предположил, что в целях совместимости pthread_t в большинстве систем останется арифметическим, либо может быть имплементирован как указатель на структуру (что оставлят его арифметическим).

        Но это не отменяет вашей правоты, и для каждой ОС нужно будет убедиться, что pthread_t арифметический.
          +2
          > Во первых не у меня, а у Саттера на одном из слайдов

          Нет, ну если у самого Саттера то конечно да. Это весомый аргумент.

          > Во вторых если мы говорим о Linux в первую очередь, то pthread_t это unsigned long int.

          Как там было выше…

          ========
          NB: Всё обсуждаемое касается разработки на C++ под Linux, но может быть применимо ко всем POSIX.1-2008 совместимым системaм (с оглядкой на конкретную реализацию).
          ========

          Все-так скорее «Все обсуждаемое применимо сугубо для Linux и не применимо к остальным POSIX совместимым платформам» т.к. вы делаете фундаментальные допущения, которые верны и то с оговорками только для Linux.

          > В третьих, сомневаюсь, что этот элемент (XBD/TC2/D6/26), в какой-либо распространнённой ОС применяется. Я-бы предположил, что в целях совместимости pthread_t в большинстве систем останется арифметическим, либо может быть имплементирован как указатель на структуру (что оставлят его арифметическим).

          Неверное предположение. Первое, что приходит в голову — *BSD. Второе — почти уверен что QNX. Третье — скорее всего остальные *NIX. Сугубо для проформы:

          github.com/freebsd/freebsd/blob/master/sys/sys/_pthreadtypes.h

          Просто потому, что pthread_t нигде не используется по значению. Мы всегда оперируем указателем на этот тип. Детали реализации по-определению скрыты от пользователя и он не должен делать каких-либо предположений на этот счет. Как следствие, гораздо удобнее объявить его как прозрачную структуру чтобы упростить себе жизнь внутри реализации.
            0
            Впрочем, если pthread_t сам по себе — это указатель на структуру, код выше вполне валиден т.к. арифметических операций над ним не производится но лишь присваивание или сравнение на равенство. Хотя выглядит все равно подозрительно.
              0

              Вот сразу из вашей-же ссылки на исходники BSD:


              typedef struct  pthread         *pthread_t

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


              Если конечно очень хочется занудствовать, то найдите ссылки на исходники с ОС, где pthread_t не указатель или интегральный тип.

                0
                А, вспомнил, что мне показалось таким неправильным в попытке запихнуть pthread_t куда-либо включая атомик. Даже если вы не проводите над ними арифметических операций, даже сравнивать два потока нужно не абы как но через pthread_equal()

                pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_equal.html#

                Все остальное UB. Как эксперимент на попробовать здесь и сейчас — согласен, забавно. Но как тенденция — навряд ли.

                PS: Если уж мы говорим за «на Linux» то он, родимый, по этому поводу в своем мане говорит, что:

                NOTES
                The pthread_equal() function is necessary because thread IDs should be considered opaque: there is no portable way for applications to directly compare two pthread_t values.
                  0
                  Основная проблема с UB, это то что Thread ID может быть инвалидным, именно тогда UB. pthread_self() всегда гарантируемо и предсказуемо вернёт одно и тот-же значение для того-же самого потока. Даже если pthread_t это указатель на структуру, то pthread_self() всегда вернёт один и тот-же адрес. unlock() может подвиснуть если заблокировавший мьютекс поток умер, не разблокировав его. Но тут уже неважно кто сравнивает значения pthread_t.

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

                  Хотя, как я уже заметил в самой статье, — эти костыли просто плохо, предоставляемое системной лучше.
        • UFO just landed and posted this here
            0
            Системный семафор построен на спинлоках или на обычных мьютексах

            ./kernel/locking/rwsem-spinlock.c


            Но в glibc (см. sem_waitcommon.c) используются как атомарные операции (попытка получить без блокировки: __new_sem_wait_fast (struct new_sem sem, int definitive_result)), так и атомарные + ожидание по времени (__new_sem_wait_slow (struct new_sem sem, const struct timespec *abstime)) в do_futex_wait (sem, abstime).


            Вообще семафор имеет среди прочего интерфейс sem_timedwait, что намекает на необходимость использования ожидания по времени в том числе.


            Так вот вот это ожидание с квотой времени, которое не поднимается до уровня userland очень классно экономит ресурсы. Т.к. с каждым nanosleep в userland мы проваливаемся до ядра там наш поток перепланируют, потом мы просыпаемся, потом понимаем что нужно ждать ещё и опять спим. Вобщем это результат с lock-free, вполне нормально объясняет.


            Вот так ...


            Алгоритм тестов простой, запускается N потоков, каждый из этих потоков ожидает на одном и том-же семафоре, в случае срабатывания семафора, инкрементирует аттрибут wake для данного потока. В деструкторе печать значения wake.
            В основном потоке, после старта N-ждущих, получаем срез времени (старт), запускаем sem_post() на М итераций, получаем срез времени (стоп), принудительно останавливаем все потоки (получая печать результатов wakes на экран), и выводим результат стоп-старт в милисeкундах для M итераций sem_post().


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

            +1
            битая ссылка на LAppS (ithub вместо github)
              0

              Lock-free mutex невозможен, ведь задача мьютекса — блокировать. Для того, чтобы алгоритм назывался Lock-free, недостаточно добавить в него спинлок на атомике! Должно выполняться еще одно условие: любой провал спинлока означает, что другой поток успешно продвинулся.


              Более слабое условие звучит так: если системный планировщик почему-то решит, что только один поток достоин получать процессорное время, то этому самому потоку ничего не должно помешать. Разумеется, в ситуации с мьютексом не выполняется даже это.


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

                0
                Я с вами полностью согласен. Более того в приведённом семафоре (в отличии от мьютекса), это условие выполняется. Там как минимум 7-мь потоков параллельно в состоянии получить значение семафора(т.к. post() многократно быстрее). Однако, в событийно ориентированной системе, ждать приходится. Применимость чистого lock-free для моих кейсов вообще сомнительная и это просто эксперименты.
                  0
                  Нет, для семафора оно тоже в общем виде не выполняется. Потому что у него тоже есть достижимое состояние когда вызов lock будет ждать прихода другого потока неопределенно долго (а если оно недостижимо — то этот семафор нафиг не нужен).

                  И чтобы не жечь под нагрузкой процессор впустую — надо бы вместо nanosleep откатываться на обычное решение с mutex и condition variable.
                    0
                    А вы статью не внимательно читали. nanosleep, как-раз и не зжёт процессор. А семафоры в LAppS используются что-бы ждать событий. Из за латентности сетевого стека, кол-во операций post() в реальной системе (а не в синтезе), всегда медленнее операций чтения.

                    И не нужен mutex с condition_variable, т.к. они ни чем не лучше POSIX семафоров. А вышеприведённая имплементация не хуже mutex с condition_variable. По крайней мере на моих тестах.
                      0
                      А вы статью не внимательно читали. nanosleep, как-раз и не зжёт процессор.

                      Но все равно процессорное время тратится впустую.


                      А вышеприведённая имплементация не хуже mutex с condition_variable. По крайней мере на моих тестах.

                      Ну нет, вышеприведенная реализация — как раз хуже чем mutex с condition_variable. По крайней мере, в ситуации когда все потоки сделали wait, и никто не делает post (чему эта ситуация соответствует — высокой нагрузке или простою — зависит от того как семафор используется). Возможно, этой ситуации просто нет в ваших тестах.

                        0

                        int nanosleep(const struct timespec rqtp, struct timespec rmtp);


                        Но все равно процессорное время тратится впустую.

                        Нет, оно отдаётся другим потокам.


                        man nanosleep(3)


                        int nanosleep(const struct timespec *rqtp, struct timespec *rmtp); 

                        Description
                        The nanosleep() function shall cause the current thread to be suspended from execution until either the time interval specified by the rqtp argument has elapsed or a signal is delivered to the calling thread, and its action is to invoke a signal-catching function or to terminate the process.

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

                          0

                          В пустую тратится не то время про которое вы подумали, а время в течении которого переключаются контексты плюс время на проверку условия цикла.

                            0

                            Да. Об этом я и в статье написал. По моему с condition_variable будет экономнее только если использовать notify_one(), a если notify_all(), то даже хуже. ведь там и на блокировке мьютекса контекст переключается и на вызов к wait() и на notify. Вообще нужно считать и тестировать. Потестирую сейчас пожалуй. И сообщу.


                            Протестировал. Если вас устроит такая поделка на condition_variable вместо семафора:


                            class SemEmuCond
                            {
                            private:
                              std::mutex              mMutex;
                              std::condition_variable mCond;
                              size_t counter;
                            public:
                              SemEmuCond():mMutex(),mCond(),counter(0){}
                            
                              void post()
                              {
                                std::unique_lock<std::mutex> lk(mMutex);
                                mCond.wait(lk,[this]{++counter; return true;});
                                mCond.notify_all();
                              }
                            
                              void wait()
                              {
                                while(1)
                                {
                                   std::unique_lock<std::mutex> lk(mMutex);
                                   mCond.wait(lk);
                                   if(counter>0)
                                   {
                                     --counter;
                                     break;
                                   }
                                }
                              }
                            };

                            То результаты печальные:


                            1. терминация потока ожидающего на подобном семафоре приводит к UB.
                            2. производительность:

                            Started 4 EmuCond threads waiting on a semaphore
                            CondEmu semaphores test. 10000000 of posts for 4 waiting threads have taken 5349 miliseconds
                            CondEmu semaphores test. Post latency: 0.5349ns

                            По потокам проблема, см п. 1


                            20 threads:


                            CondEmu semaphores test. 10000000 of posts for 20 waiting threads have taken 12529 miliseconds
                            CondEmu semaphores test. Post latency: 1.2529ns
                            Thread(EmuCond) wakes: 353156
                            terminate called without an active exception
                            Аварийный останов

                            т.е. хуже.

                              0
                              Э… зачем вы делаете mCond.wait в post? Почему не notify_one? Зачем вы делаете mCond.wait в wait безусловно? Наконец, куда делись ваши атомики? Я же предлагал использовать это решение вместо nanosleep, а не вместо всего вашего алгоритма…
                                0
                                Вы правы в post() совершенно не нужно делать: mCond.wait(lk,[this]{++counter; return true;});
                                Там как-бы итак мьютекс эксклюзивно локируется. Заменил на ++counter;

                                Результат:

                                Started 20 EmuCond threads waiting on a semaphore
                                CondEmu semaphores test. 10000000 of posts for 20 waiting threads have taken 12106 miliseconds
                                CondEmu semaphores test. Post latency: 1.2106ns

                                Т.е. выигрышь 5% относительно предыдущего.

                                notify_one() — плохо, т.к. будить будет последовательно, а если post() быстрее потребления и аппаратных потоков в системе например 4-е, то при пробуждении 3 консамера должны суметь декрементировать семафор практически одновременно.

                                Как подтверждение результат с notify_one():

                                Started 20 EmuCond threads waiting on a semaphore
                                CondEmu semaphores test. 10000000 of posts for 20 waiting threads have taken 22821 miliseconds
                                CondEmu semaphores test. Post latency: 2.2821ns

                                > Наконец, куда делись ваши атомики? Я же предлагал использовать это решение вместо nanosleep

                                Вы хотите использовать только нотификацию condition_variable для ожидания события? Дошло. Тоже вариант сейчас посмотрим.

                                Фигня получилась. Тут тебе и мьютекс, тут тебе и атомики тут и кондишн-вар, я пока делал понял, что фигня будет. Как результат:

                                … 10000000 of posts for 20 waiting threads have taken 12704 milisecond
                                Post latency: 1.2704ns

                                Т.е это вообще не вариант, а учитывая что потоки произвольно теперь убивать нельзя пока они на кондиш-не ждут, то вообще но-гоу.
                                  0
                                  То есть с атомиками получилось столько же, сколько и без них, и это все — медленнее чем с нанослипом? А вы точно атомики снаружи мьютекса менали? :-)
                                    0
                                    Да точно. На самом деле всё ещё проще. Попробуйте сами. Это-же элементарно.
                    0
                    По поводу же применимости lock-free для ваших кейсов — тут все просто. В первом кейсе lock-free должны были применять авторы LibreSSL, а не вы.

                    Во втором и третьем кейсах, я так понимаю, вся lua-часть выполняется в один поток, и где-то крутится цикл ожидания событий? В таком случае lock-free невозможен, опять-таки, исходя из задачи.
                      0
                      Во втором и третьем кейсах, я так понимаю, вся lua-часть выполняется в один поток, и где-то крутится цикл ожидания событий? В таком случае lock-free невозможен, опять-таки, исходя из задачи.


                      Нет не верно. Потоков Lua может быть столько сколько инстансов каждого сервера выполняется. Поступление событий по сети (в моих условиях), заведомо медленнее чем их обработка в потоках lua (парадокс, но на echo тестах это так). И простое отключение iptables производительность сервера увеличивает на 30%… вот как…
                        0

                        Ну значит, у вас несколько потоков крутится в цикле ожидания события? Это ничего не меняет...

                    0
                    Вы сейчас что-то странное сказали.

                    «Любой провал спинлока означает, что другой поток успешно продвинулся» — точнее, другой поток получил лок. Это deadlock freedom, самое слабое условие алгоритмов с блокировками.

                    «если системный планировщик почему-то решит, что только один поток достоин получать процессорное время, то этому самому потоку ничего не должно помешать» — это obstruction freedom, самое слабое условие lock-free алгоритмов. Это условие, кстати, сильнее deadlock freedom.

                    Сведение мьютекса исключительно к спин-локам в теории проблем не вызывает, т.к. спин-лок — одна из возможных реализаций мьютекса. Редко когда эффективная, это да.

                    А собственно смысл lock-free не в том, что мы никогда не ждём. Он в том, что в алгоритме не должно быть критических секций. То есть мьютексов/спинлоков не должно быть в принципе.
                      0
                      «Любой провал спинлока означает, что другой поток успешно продвинулся» — точнее, другой поток получил лок. Это deadlock freedom, самое слабое условие алгоритмов с блокировками.

                      Нет, deadlock freedom требует чтобы хоть какой-нибудь поток в конечном счете (Whatever the time T… then there is a time T' > T at which ...) успешно получил лок. А я писал о том, что происходит за одну итерацию, это и есть требование lock freedom.


                      Сведение мьютекса исключительно к спин-локам в теории проблем не вызывает, т.к. спин-лок — одна из возможных реализаций мьютекса/

                      Сведение мьютекса исключительно к спин-локам проблем, может быть, и не вызывает — но не позволяет мьютексу называться lock-free.

                        0
                        А, то есть вы хотели lock freedom описать. Только тогда стоит написать «провал операции» как более абстрактное, или вообще «хотя бы один поток выполнит операцию при любых действиях других потоков» — в вашем определении забыт случай с 1 потоком :-)

                        Касательно спинлоков — они тоже не lock-free. Вообще lock-free — это когда как минимум нет блокировок, т.е. ни мьютексов, ни спинлоков, ни семафоров.
                          0

                          Когда операция — это получение блокировки через спинлок, провал операции — это провал спинлока.


                          Касательно спинлоков — они тоже не lock-free. Вообще lock-free — это когда как минимум нет блокировок, т.е. ни мьютексов, ни спинлоков, ни семафоров.

                          Ну так я именно это и написал же. С чем вы спорите?

                            0
                            Наверное, с неудачной формулировкой.
                            Должно выполняться еще одно условие

                            Как бы подразумевается, что как-то это условие сделать, и мьютекс становится lock-free. Хотя на самом деле единственный способ получить lock-free это выкинуть все мьютексы вообще.
                            вся затея со сведением мьютекса исключительно к спин-локам обречена на провал

                            Лучше было бы «вся затея с получением lock-free мьютекса», потому что сводить мьютекс к его реализации на спин-локах нам ничто не мешает, а заменять первые на вторые может даже оказаться полезно.
                              0

                              Так все правильно же. Достаточно выполнить невыполнимое условие — и мьютекс станет lock-free :-)

                    0
                    Если занудствовать дальше, то у автора получился «не честный» семафор, так как «настоящий» семафор должен гарантировать равный шанс для каждого ждущего потока при доступе к ресурсу, а тут уже простым счетчиком не ограничишься. Придется городить lock-free список ждущих потоков и т.д. Глядишь и скорость выровнится, по сравнению со стандартным семафором. А так — да, срезать углы можно, но надо понимать за счет чего.
                      0
                      Неверно. Если счётчик больше числа потоков консамеров, то выполнится параллельно столько потоков сколько система поддерживает (на самом деле каждый из них попытается выполнить атомарный декремент одного и того-же значения, что их всё равно выстроит в очередь). Более того посмотрите на код glibc там так-же при невозможности декрементировать счётчик поток уводится в сон (см комментарии выше), и также используются атомарные операции декремента. Вобщем этот семафор ничем не хуже системного, ровно с теми-же шансами на выполнение. Но суть статьи не в этом, а в том, что всё это от лукавого.
                        0
                        Я представляю как работает семафор и, не много, не об этом. Представьте что счетчик ресурсов исчерпан (нуль) и в этот момент еще 10 потоков пытаются захватить ресурс. Ясно что все они буду ждать пока ресурс не появится. Вопрос в том, какие потоки, из уже ожидающих, пробудятся в случае когда ресурсы семафора снова станут доступны. Хорошая реализация семафора должна пробуждать потоки гарантируя, в среднем, каждому ожидающему потоку равную возможность получить ресурс.
                          0
                          Вопрос в том, какие потоки, из уже ожидающих, пробудятся в случае когда ресурсы семафора снова станут доступны


                          А тут также как и в системной реализации, какой поток CFQ пробудит первым, тот и получит преимущество, а в среднем шансы у них действительно равные. POSIX многоядерности OS не специфицирует кстати, поэтому параллельного пробуждения планировщиком также не существует и кто-то становится «первым среди равных».
                          0
                          Не совсем с теми же.
                          На системном семафоре у всех потоков 500000 +- 3000 сообщений. Практически поровну.
                          На вашем есть «удачливый» поток с 600000 сообщениями, и пара «неудачников» с 450000 — разница на треть.
                            0
                            А тут как раз просто. Этот фокус элементарен, в этом тесте (см пояснения выше), некоторые потоки довольно долго вообще в сон не уходят, т.к. post() многократно быстрее чем wait(). Ведь 20 потоков ждут, каки-е то спят, а какие-то молотят, так вот преимущество у тех потоков, у которых квота процессорного времени не истекла, но вы их посчитайте, — 7 потоков с изначальным преимуществом (Core i7).
                        0
                        А можно ссылку на код с тестами?
                          0

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

                          0

                          А вы не думали использовать wait-free алгоритмы? Например, передачу сообщений между потоками можно делать через циклический буфер с двумя указателями. Каждый перемещает свой указатель, не ожидая других. Чтение чужого указателя и перемещение своего разделяем барьерами памяти — это гарантирует, что один другой не обгонит. Если надо надо слать многим потокам или принимать из разных мест — создаём по такому буферу на каждую пару и шлём через раунд-робин. Если хотим записать, а все буферы переполнены — либо подвисаем в ожидании, либо делаем что-то ещё. И наоборот, если хотим получить, а буферы пусты, то либо подвисаем, либо делаем что-то ещё. Вот тут я описываю использование горутин и каналов реализованных по этим принципам. А тут можно глянуть исходники.

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

                          Only users with full accounts can post comments. Log in, please.