Open Source & Linux Lab

It's better when it's simple

User Tools

Site Tools


projects:libcds:bounded_pool

This is an old revision of the document!


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() может быть неудачным, хотя место в очереди ещё есть. То есть эта очередь не может стабильно работать в режиме «пул полон».

Требуется: реализовать быстрый алгоритм 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_; }
};

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

Pool<void *> pool(256);
std::atomic<size_t> nGetError(0);
std::atomic<size_t> nPutError(0);

void thread()
{
     for ( int i = 1; i <= 1000000; ++i ) {
          if ( !pool.push( i ))
                nPutError.fetch_add(1, std::memory_order_relaxed);
          void * p = pool.pop();
          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 );
}
projects/libcds/bounded_pool.1449749392.txt.gz · Last modified: 2015/12/10 15:09 by khizmax