From: d@d.d   
      
   Hello,   
      
      
   Lock Versus Lock-Free   
      
      
   The class of problems that can be solved by lock-free approaches is limited.   
      
   Furthermore, lock-free approaches can require restructuring a problem.   
   As soon as multiple shared data-structures are modified   
   simultaneously,the only practical approach is to use a lock.   
      
   All lock-free dynamic-size data-structures using such CAA   
   (Compare-and-assign) require some form of garbage collector to lazily   
   delete storage when it is no longer referenced. In languages with   
   garbage collection, this capability comes for free (at the cost of   
   garbage collection). For languages without garbage collection, the code   
   is complex and error prone in comparison with locks, requiring   
   epoch-based reclamation, read-copy-update (RCU), or hazard pointers.   
      
   While better performance is claimed for lock-free data-structures, there   
   is no long-term evidence to support this claim. Many high-performance   
   locking situations, e.g., operating system kernels and databases,   
   continue to use locking in various forms, even though there are a broad   
   class of lock-free data-structure readily available.   
      
   While lock-free data-structures cannot have deadlock, there is seldom   
   deadlock using locks for the simple class of problems solvable using   
   lock-free approaches. For example, protecting basic data-structure   
   operations with locks is usually very straightforward. Normally deadlock   
   occurs when accessing multiple resources simultaneously, which is not a   
   class of problems   
   dealt with by lock-free approaches. Furthermore, disciplined lock usage,   
   such as ranking locks to avoid deadlock, works well in practice and   
   is not onerous for the programmer.Finally, some static analysis tools   
   are helpful for detecting deadlock scenarios.   
      
   Lock-free approaches have thread-kill tolerance, meaning no thread owns   
   a lock, so any thread can terminate at an arbitrary point without   
   leaving a lock in the closed state. However, within an application,   
   thread kill is an unusual operation and thread failure means an   
   unrecoverable error or major reset.   
      
   A lock-free approach always allows progress of other threads, whereas   
   locks can cause delays if the lock owner is preempted. However,this   
   issue is a foundational aspect of preemptive concurrency. And there are   
   ways to mitigate this issue for locks using scheduler-activation   
   techniques. However, lock-free is not immune to delays. If a page is   
   evicted containing part of the lock-based or lockfree data, there is a   
   delay. Hence, lock free is no better than lock based if the page   
   fault occurs on frequently accessed shared data. Given the increasing   
   number of processors and large amount of memory on modern computers,   
   neither of these delays should occur often.   
      
   Lock-free approaches are reentrant, and hence, can be used in signal   
   handlers, which are implicitly concurrent. Locking approaches cannot   
   deal with this issue. Lock-free approaches are claimed not to have   
   priority inversion. However, inversion can occur because of the spinning   
   required with atomic instructions, like CAA, as the hardware does not   
   provide a bound for spinning threads. Hence, a low-priority thread can   
   barge head of a high-priority thread because the low-priority thread   
   just happens to win the race at the CAA instruction. Essentially,   
   priority inversion is a foundational aspect of preemptive concurrency   
   and can only be mitigated.   
      
   The conclusion is that for unmanaged programming language (i.e., no   
   garbage collection), using classical locks is simple, efficient,   
   general, and causes issues only when the problem scales to multiple   
   locks. For managed programming-languages, lock-free data-structures are   
   easier to implement, but only handle a specific set of problems, and the   
   programmer must accept other idiosyncrasies, like pauses in   
   execution for garbage collection.   
      
      
      
   Thank you,   
   Amine Moulay Ramdane.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)