Differences

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

--- projects:libcds:bounded_pool [2015/12/10 15:33] – khizmax
+++ projects:libcds:bounded_pool [2015/12/17 23:11] (current) – khizmax
@@ 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()'' может быть неудачным, хотя место в очереди ещё есть.
 То есть эта очередь не может стабильно работать в режиме «пул полон».
+**UPD**: очередь Вьюкова сделана линеаризуемой. По крайней мере, нижеследующий тест на новой реализации успешен.
 **Требуется**: найти/придумать и реализовать быстрый алгоритм lock-free/wait-free bounded pool:
-<code>
+<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 ) {