«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) прироста производительности...