Differences

This shows you the differences between two versions of the page.

--- projects:libcds:bounded_pool [2015/12/10 15:09] – [Bounded object pool] khizmax
+++ projects:libcds:bounded_pool [2015/12/17 23:11] (current) – khizmax
@@ Line 4: / Line 4: @@
 Раз алгоритм lock-free, то и пул тоже должен быть по крайней мере lock-free.
 Пул — это не очередь и не стек, хотя эти структуры данных могут быть пулом. Пул — это класс с двумя интерфейсными функциями:
-- ''T *  get()'' - возвращает любой объект из пула или ''nullptr'', если пул пуст
+  * ''T *  get()'' - возвращает любой объект из пула или ''nullptr'', если пул пуст
-- ''bool put( T * )'' - помещает объект в пул, возвращает ''true'', если успешно (пул не переполнен) или ''false'', если пул полон.
+  * ''bool put( T * )'' - помещает объект в пул, возвращает ''true'', если успешно (пул не переполнен) или ''false'', если пул полон.
 Как правило, конструктор пула заполняет его некими объектами. В этом существенное отличие от классической очереди или стека,
@@ Line 20: / Line 20: @@
 В настоящее время (libcds 2.1.0) в качестве пула в библиотеке используется [[http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue|алгоритм]]
 bounded очереди Дмитрия Вьюкова.
-Он быстр, но имеет один существенный недостаток — иногда не обеспечивает [[https://en.wikipedia.org/wiki/Linearizability|атомарности]]:
+Он быстр, но имеет один существенный недостаток — он не является линеаризуемым:
 при почти полной очереди ''push()'' может быть неудачным, хотя место в очереди ещё есть.
 То есть эта очередь не может стабильно работать в режиме «пул полон».
-**Требуется**: реализовать быстрый алгоритм lock-free/wait-free bounded pool:
+**UPD**: очередь Вьюкова сделана линеаризуемой. По крайней мере, нижеследующий тест на новой реализации успешен.
-<code>
+**Требуется**: найти/придумать и реализовать быстрый алгоритм lock-free/wait-free bounded pool:
+<code c++>
 template <typename T>
 class Pool
@@ Line 41: / Line 43: @@
 };
 </code>
+Методы ''get()'' и ''put()'' не должны распределять памяти.
 **Критерий корректности**: реализация должна успешно пройти такой тест на успешную работу в состоянии «пул почти полон» (псевдокод):
-<code>
+<code c++>
 Pool<void *> pool(256);
 std::atomic<size_t> nGetError(0);
 std::atomic<size_t> nPutError(0);
-void thread()
+void thread_func()
 {
      for ( int i = 1; i <= 1000000; ++i ) {
-          if ( !pool.push( i ))
+          if ( !pool.put( &i ))
                 nPutError.fetch_add(1, std::memory_order_relaxed);
-          void * p = pool.pop();
+          void * p = pool.get();
           if ( p == nullptr )
                 nGetError.fetch_add( 1, std::memory_order_relaxed);