IntroductionProblem FormulationThin LocksImplementationLocking AlgorithmsEvaluationBenchmarksConclusionsQuestionsIntroduction Thin Locks Evaluation QuestionsThin Locks: Featherweight Synchronization forJavaD. Bacon1R. Konuru1C. Murthy1M. Serrano1Presented by: Calvin Hubble21IBM T.J. Watson Research Center2Department of Computer Scie nceUniversity of CA, San Diego16th November 2005David F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsOutlineIntroductionProblem FormulationThin LocksImplementationLocking AlgorithmsEvaluationBenchmarksConclusionsQuestionsDavid F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsOutlineIntroductionProblem FormulationThin LocksImplementationLocking AlgorithmsEvaluationBenchmarksConclusionsQuestionsDavid F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsProblem FormulationIntroductionIJava synchronization is a double-edged wordIJava has threads and synchronized metho dsISynchronization is “dog slow”IStuck with a tradeoffIBad Performance, Safe CodeIGood performance, bug-prone codeICan we modify Java to be faster yet still thread-safe to theeveryday programmer?David F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsProblem FormulationProblemIBecause Java is an explicitly multi-threaded language,general-purposes libraries are thread-safeINon-trivial public methods of standard utility classes likeVector or Hashtable are synchronizedIExample: Library call to set a bit in a bit vector:I50 instructions to lock and unlock the objectI10 instructions metho d call overheadI5 instructions to actually set the bitILocking overhead frequently 25 − 50%IEven in single-threaded applications!!David F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsProblem FormulationLocking Scenarios by Frequency1. Locking an unlocked object2. Locking an object already locked by current thread a smallnumber of times (shallow nested lo cking)3. Locking an object already locked by the current thread manytimes (deeply nested locking)4. Being the first to queue on a locked object5. Trying to lock an object with a queueMeasurements: median of 80% of all lock operations are onunlocked objects, and nesting is very shallow.David F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsProblem FormulationLocking FrequencyDavid F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsProblem FormulationGoalGoal: a locking algorithm with very low overhead forsingle-threaded programs, but with excellent performance in thepresence of multithreading and contention.David F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsOutlineIntroductionProblem FormulationThin LocksImplementationLocking AlgorithmsEvaluationBenchmarksConclusionsQuestionsDavid F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsImplementationThin LocksIAssume pre-existing heavy-weight locking systemI“Fat Locks”IThin Locks - a lightweight system for 2 most common cases1. Object is unlocked2. Shallow nested lockingILocks are defaulted to t hin and inflated if neededIOnce a lock is inflated, it can never be defaultedDavid F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsImplementationNew Lock StructureIReserve 24 bits in the header ofeach object for a thin lockI“Obtained 24 free bits usingvarious encoding techniquesfor the other values typicallystored in the header”IFirst bit: Monitor shape lockI0 - denotes lock is “thin”I1 - denotes lock is “fat”David F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsImplementationWhen Lock is ThinILock StructureIMonitor Shape bit - 0INext 15 bits - Thread IdentifierILast 8 bits - Nested lock count (+1)IMaximum of 255 nested locksDavid F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsImplementationWhen Lock is FatILock StructureIMonitor Shape bit - 1INext 23 bits - index of fat lockDavid F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsLocking AlgorithmsAssumptionsIHardware supportIUsed compare-and-swapICMP&SWP(addr, old, new) - If contents of addr == oldvalue, store new value and return true, otherwise return falseIkey invariant: The lock field is never modified by any threadexcept the current “owner”.David F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsLocking AlgorithmsLocking without ContentionIInitially - lock field is 0, thread A wis hes to lock.IAlgorithm:Icompare-and-swap lock wordI“Old” value: High 24-bits masked to 0I“New” value: monitor shape 0, thread index A, count 0IIf succeeds, object was not locked by another thread and wenow own lockDavid F. Bacon, Ravi Konuru, Chet Murthy, Mauricio Serrano University of CA, San DiegoThin Locks: Featherweight Synchronization for JavaIntroduction Thin Locks Evaluation QuestionsLocking AlgorithmsUnlocking without Contention (no nesting)IAlgorithmIConstruct “old” value: monitor shape 0, thread index A, count0IRead lock word