Bounded object pool

Довольно часто в lock-free алгоритмах возникает необходимость в пуле некоторого фиксированного объема. Раз алгоритм lock-free, то и пул тоже должен быть по крайней мере lock-free. Пул — это не очередь и не стек, хотя эти структуры данных могут быть пулом. Пул — это класс с двумя интерфейсными функциями:

• T * get() - возвращает любой объект из пула или nullptr, если пул пуст
• bool put( T * ) - помещает объект в пул, возвращает true, если успешно (пул не переполнен) или false, если пул полон.

Как правило, конструктор пула заполняет его некими объектами. В этом существенное отличие от классической очереди или стека, которые создаются пустыми. И вообще, нормальное состояние пула — «пул полон», тогда как для очереди - «очередь пуста».

Пул применяется для хранения некоторых преаллоцированных ресурсов (вспомогательных объектов), которые разделяются между потоками. Например, монитор синхронизации может иметь пул mutex'ов, которые используются в реализации lock-based fine-grained дерева. Эти mutex'ы используются для синхронизации доступа к вершинам дерева при вставке/удалении. Число узлов дерева может быть огромно, создавать для каждого узла свой mutex нерационально (не забудем, что mutex – системный ресурс, число которого может быть ограничено), тогда как число одновременно работающих с деревом потоков невелико, то есть в каждый момент времени нам нужно не 1 млн mutex'ов, а 10 — 20. Здесь может быть использован пул mutex'ов: мы берем из пула mutex, прикрепляем его к узлу дерева, лочим, делаем модификацию поддерева, разлочим и возвращаем mutex в пул.

В настоящее время (libcds 2.1.0) в качестве пула в библиотеке используется алгоритм bounded очереди Дмитрия Вьюкова. Он быстр, но имеет один существенный недостаток — он не является линеаризуемым: при почти полной очереди push() может быть неудачным, хотя место в очереди ещё есть. То есть эта очередь не может стабильно работать в режиме «пул полон».

UPD: очередь Вьюкова сделана линеаризуемой. По крайней мере, нижеследующий тест на новой реализации успешен.

Требуется: найти/придумать и реализовать быстрый алгоритм lock-free/wait-free bounded pool:

template <typename T>
class Pool
{
    size_t capacity_;
public:
    Pool( size_t capacity ): capacity_( capacity ) {}
    T * get(); // return nullptr if pool is empty
    bool put( T * obj );  // return false if pool is full
 
    bool empty() const;
    bool full() const;
    size_t capacity() const { return capacity_; }
};

Методы get() и put() не должны распределять памяти.

Критерий корректности: реализация должна успешно пройти такой тест на успешную работу в состоянии «пул почти полон» (псевдокод):

Pool<void *> pool(256);
std::atomic<size_t> nGetError(0);
std::atomic<size_t> nPutError(0);
 
void thread_func()
{
     for ( int i = 1; i <= 1000000; ++i ) {
          if ( !pool.put( &i ))
                nPutError.fetch_add(1, std::memory_order_relaxed);
          void * p = pool.get();
          if ( p == nullptr )
                nGetError.fetch_add( 1, std::memory_order_relaxed);
     }
}
 
void main()
{
      size_t const thread_count = 16;
 
      size_t const initial_size = pool.capacity() - thread_count;
 
      // initialize pool
      for ( size_t i = 1; i <= initial_size; ++i )
            pool.put(  &initial_size /* put anything */ );
 
      // run working threads
      for ( int i = 0;  I < thread_count; ++i )
          run_thread( thread_func );
      wait_for_all_threads_done();
 
      // no put/get error
      assert( nPutError.load() == 0);
      assert( nGetError.load() == 0 );
}