Protecting Shared Data Structure Sample Clauses

Protecting Shared Data Structure. ‌ There are two groups of methods to protect a shared data structure, lock-based meth- ods and lock-free methods. Lock-based Methods use mutexes and locks to create synchronization and pro- tect the shared data. The first obvious design used one mutex to protect the entire search tree, but later ones used more than one mutex to protect smaller parts of the search tree and allow a greater level of concurrency in accesses to the search tree [CWvdH08a]. Locks are notoriously bad for parallel performance, because other threads have to wait until the lock is released, and locks are often a bottleneck when many threads try to acquire the same lock. If we can write a search tree data structure that is safe for concurrent accesses without locks, there is the potential for maximum concurrency. Definition 5.2 (Lock-based) A data structure is lock-based when it uses mutexes and locks to create synchronization to protect the shared data. Lock-free Methods use a lock-free data structure. Such a data structure often uses the compare/exchange operation to make progress in an algorithm, rather than pro- tecting a part that makes progress. For example, when modifying a shared variable, an approach using locks would first acquire the lock, then modify the variable, and finally release the lock. A lock-free approach would use compare/exchange to modify the variable directly. This requires only one memory operation rather than three, but designing a lock-free data structure is hard and needs extreme care. Definition 5.3 (Lock-free) A data structure is lock-free when more than one thread must be able to access it concurrently.