Differences

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

--- projects:libcds:tasks [2017/02/25 13:50] – kel
+++ projects:libcds:tasks [2017/09/20 00:59] – Убран алгоритм по причине уже его реализованности kel
@@ Line 44: / Line 44: @@
 Реализовать описанный в статье алгоритм bounded deque. SMR здесь не требуется, так как deque основана на массиве.
-==== [2014] Dodds,Haas,Kirsch Fast Concurrent Data-Structures Through Explicit Timestamping.pdf ====
-//Сложность://4\\
-Перспективный алгоритм построения lock-free стека, очереди, deque. Должен обеспечивать очень хорошую производительность для push-операций, так как push производится в локальный для потока storage. Псевдокод основан на tagged pointers, требуется применить какой-либо другой SMR – Hazard Pointers, reference counting.
 ==== [2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf ====
@@ Line 109: / Line 103: @@
 В libcds уже есть HP- и RCU-based реализации (без helping'а), требуется сделать append-only версию (без GC – cds::gc::nogc), то есть версию без возможности удаления элементов. Попробовать реализовать helping (будет хорошо, если helping будет включаться отдельным флагом в traits).
-==== [2010] Bronson,Casper,Chafi,Olukotun A Practical Concurrent Binary Search Tree.pdf ====
-//Сложность://7\\
-Реализация конкурентного AVL-tree, новый метод optimistic hand-over-hand locking. Проанализировать, какой SMR подходит (HP, RCU, оба), либо же алгоритм не требует никакой SMR схемы.
 ==== [2011] Brown,Helga Non-blocking k-ary Search Trees.pdf ====
@@ Line 137: / Line 125: @@
 Реализация конкурентного trie. No comments.
-===== Реализованные =====
+===== Требующие доработки =====
+==== A.Williams “C++ Concurrency in Action” - lock-free очередь на shared_ptr ====
+> //Сложность://2
+> [[https://github.com/khizmax/libcds/pull/72|Pull request]]
+Алгоритм и его подробный анализ есть в книге. Требуется создать очередь на C++11. Оценить, можно ли создать intrusive-версию.
 ==== A.Williams “C++ Concurrency in Action” - lock-free стек на shared_ptr ====
 > //Сложность://1+
-> [[https://github.com/khizmax/libcds/pull/54|Pull request]]
+> [[https://github.com/khizmax/libcds/pull/73|Pull request]]
 Алгоритм и его подробный анализ есть в книге. Требуется создать стек на C++11, используя оба алгоритма, описанных в книге: на shared_ptr и split reference counting. Оценить, можно ли создать intrusive-версию.
-==== A.Williams “C++ Concurrency in Action” - lock-free очередь на shared_ptr ====
+==== [2014] Dodds,Haas,Kirsch Fast Concurrent Data-Structures Through Explicit Timestamping.pdf ====
-> //Сложность://2
+> //Сложность://4\\
-> [[https://github.com/khizmax/libcds/pull/72|Pull request]]
+> [[https://github.com/khizmax/libcds/pull/55|Pull request]]
+Перспективный алгоритм построения lock-free стека, очереди, deque. Должен обеспечивать очень хорошую производительность для push-операций, так как push производится в локальный для потока storage. Псевдокод основан на tagged pointers, требуется применить какой-либо другой SMR – Hazard Pointers, reference counting.
+===== Реализованные =====
-Алгоритм и его подробный анализ есть в книге. Требуется создать очередь на C++11. Оценить, можно ли создать intrusive-версию.