Transcript Software Transactional Memory Should Not Be Obstruction Free

Paper: Robert Ennals
Presenter: Emerson Murphy-Hill
Slide 1 (of 21)
MULTIVIEW
Software Transactional Memory
Should Not Be Obstruction Free
• Hardware and software transactions
• No performance data
• STM striving to be obstruction-free:
MULTIVIEW
What We’ve Seen Thus Far…
– A process will make progress in a finite number of
steps in the absence of contention
– The weakest progress guarantee
– Introduces the possibility of livelock, which can be
addressed through contention management (helping /
stealing)
• The message: the weaker the progress guarantee,
the simpler the implementation…
Slide 2 (of 21)
MULTIVIEW
The Gist of this Paper:
• Obstruction-freedom is an unnecessary
guarantee for transactional memory
• Obstruction-freedom makes
implementation difficult
• Without obstruction-freedom, performance
is fine
Slide 3 (of 21)
• In real programs, concurrency is implemented
with threads
• Threads are used for convenience:
– No performance advantage for single-core machines
– Convenience allows one thread to proceed while
another blocks
– For instance, GUI and compute threads
– Only locks needed; that’s fine for single-core
– Different priority locks may be needed to ensure low
priority threads don’t block high priority threads
Slide 4 (of 21)
MULTIVIEW
Threads
• Threading for performance:
– In the presence of multi-cores, multi-threads
are good!
• We expect locks in threaded code
converted to transactions automatically
• The key: since the original, locked code
could block a process, it’s acceptable for
the new STM code to block as well
Slide 5 (of 21)
MULTIVIEW
Threads (continued)
Slide 6 (of 21)
MULTIVIEW
Obstruction Freedom is
Unnecessary
• Straw-man or Herlihy: long-running/nonterminating transactions can cause other
transactions to block without obstructionfreedom
• Wrong! This happens anyway:
MULTIVIEW
Long Running Transactions Block
Others
– Suppose we have a read to an object, a yearlong compute, then a write to the same object
– All STM implementations can only block other
transactions
Slide 7 (of 21)
MULTIVIEW
Context Switching
• Straw-man or Herlihy: the system grinds to a halt
when the OS switches tasks
• Wrong! Here’s why:
– The task will be switched back in again
– In a good implementation, this will be rare, because
the number of tasks should equal the number of
processors
– There should be no blocking in transactions anyway:
• It wasn’t allowed in the original locked implementation
• Transaction-aware operating systems can prevent it
Slide 8 (of 21)
• Straw-man or Herlihy: On software or
hardware failure, system grinds to halt
• Wrong!
MULTIVIEW
Independent Failure
– Software or hardware failure broke the lockbased implementation, so it’s fine
– Hardware failure is rare in multi-cores anyway
Slide 9 (of 21)
Slide 10 (of 21)
MULTIVIEW
Obstruction Freedom makes
Implementation Difficult
• STM usually requires several memory accesses before an object can
be accessed
• What if one process wants to access an object owned by swappedout process?
– Wait, but that’s not obstruction-free
– Go ahead, but that’s not safe
– Could abort the blocked process and wait for acknowledgement, but
that’s not obstruction-free either (also, might live-lock)
• So: STM cannot store object data in-place
Slide 11 (of 21)
MULTIVIEW
Cache-locality
MULTIVIEW
Excessive Active Transactions
• If there are N transactions on N processors,
what happens if we want to add another
transaction?
• Obstruction-free implementations can’t
wait for other transactions to complete, so
memory contention must increase
Slide 12 (of 21)
Slide 13 (of 21)
MULTIVIEW
Life without ObstructionFreedom…
• Revocable Two Phase Locking for Writes
MULTIVIEW
The Basic Idea
– A transaction locks all objects it intends to write
– Locks are released when transaction is complete
– On deadlock, one transaction aborts and rolls back it’s
writes
• Optimistic Concurrency Control for Reads
– Objects log the version number they read
– Version numbers must match end-of-transaction
version numbers on commit
Slide 14 (of 21)
Slide 15 (of 21)
MULTIVIEW
Memory Layout
• To write to an object:
– If the object’s handle is a version number
• CAS handle to point to new write descriptor
• Make private working copy
– If the object’s handle is a write descriptor, wait
MULTIVIEW
Reading and Writing
• Until it is a version number
• Or a timeout has been reached, then request other process to
abort
– On deadlock, system aborts one transaction
• To read from an object
– Wait for handle to become a version
– Log the version
Slide 16 (of 21)
MULTIVIEW
Committing
• Make sure all read objects still have same
version
• Write working copy to original object
• Set object’s descriptor to a new version
• The runtime must periodically check for
invalid transactions (transactions that are in
infinite loops because they’ve seen
inconsistent data)
Slide 17 (of 21)
Slide 18 (of 21)
MULTIVIEW
Performance
Slide 19 (of 21)
MULTIVIEW
Performance (continued)
Slide 20 (of 21)
MULTIVIEW
Performance (continued)
• Obstruction freedom is not important to
software transactional memory systems
• Obstruction freedom makes
implementations:
– Inefficient
– Complicated
• So do away with it!
Slide 21 (of 21)
MULTIVIEW
Conclusion