Data Structures useful in multi-threaded programming [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 9 years ago.

Improve this question

Besides the well known data Structure which can be used in Multi-Threaded programs such as Concurrent Stack, Concurrent Queue, Concurrent List, Concurrent Hashing. Are there any other lesser know but useful Data Structures which can be used in parallel/Multi-Threaded programming.

Even if they are some different versions of above listed data structures with some optimization, then kindly do share.

Please do include some references.

Edit: Will keep listing what I find

1) ConcurrentCuckooHashing (Optimized version of ConcurrentHashing)

2) ConcurrentSkipList

Answer 1

I will try to answer with examples from JDK, if you do not mind:

Lists:

• CopyOnWriteArrayList is a list that achieves thread-safe usage by recreating backing array each time the list is modified;
• Lists returned by Collections.synchronizedList() are thread-safe as they include exclusive locking for most operations (iteration over is an exception);
• ArrayBlockingQueue. Queue that has a fixed size and blocks when there's nothing to pull out or no space to push in;
• ConcurrentLinkedQueue is a lock-free queue based on Michael-Scott algorithm;
• Concurrent stack, based on Treiber algorithm. Surprisingly, I didn't find that in JDK;

Sets:

• Sets, returned by factory Collections.newSetFromMap() with a backing ConcurrentHashMap. With these sets you can be sure that its iterators is not prone to ConcurrentModificationException, and they use a striping technique for locking it - locking all set is not neccesary to perform some operations. For example, when you want to add element, only the part of the set determined by element hashCode() will be locked;
• ConcurrentSkipListSet. The thread-safe set based on a Skip List data structure;
• Sets, returned by Collections.synchronizedSet(). All points written about similar lists are applicable here.

Maps:

• ConcurrentHashMap which I already mentioned and explained. Striping is based on item keys;
• ConcurrentSkipListMap. Thread-safe map, based on skip list;
• Maps, returned by Collections.synchronizedMap(). All points written about similar lists and maps are applicable here.

These were more or less standard data structures intended for multithreaded usage, which should be enough for most practical tasks. I also found some links you may find useful:

• Wait-free red-black tree;
• A huge article about concurrent data structures in general;
• Concurrent structures and synchronization primitives used in .NET;
• Articles about transactional memory - not really a data structure, but since your request serves academic purposes, worth reading;
• One more article about transactional memory - Easy to read, but it is in Russian language. If you can read it, definetely worth reading;