Linked Lists: Locking, Lock-
         Free, and Beyond … 
           Companion slides for 
         The Art of Multiprocessor 
             Programming 
        by Maurice Herlihy & Nir Shavit 
                       Last Lecture: Spin-Locks 
                            .                            CS 
                            .                                          Resets lock  
                            .                   spin   critical        upon exit 
                                                lock    section 
                                         Art of Multiprocessor Programming                     2 
                         Today: Concurrent Objects 
                  •  Adding threads should not lower 
                      throughput 
                        –  Contention effects 
                        –  Mostly fixed by Queue locks 
                  •  Should increase throughput 
                        –  Not possible if inherently sequential 
                        –  Surprising things are parallelizable 
                                             Art of Multiprocessor Programming                           3 
                        Coarse-Grained 
                        Synchronization 
           •  Each method locks the object 
              –  Avoid contention using queue locks  
              –  Easy to reason about 
                 •  In simple cases 
              –  Standard Java model 
                 •  Synchronized blocks and methods 
           •  So, are we done?  
                           Art of Multiprocessor Programming  4