Transcript Multiprocessor Synchronization

Software Transactional
Objects
Guy Eddon
Maurice Herlihy
TRAMP 2007
Language/Library support
for Transactions
• Lots of worn on unmanaged languages
– “word-based”
• What about managed languages?
– Objects, GC, bounds checks, structured
exceptions?
– Java™, C#?
• Different concerns
2
Prior STM Work
• Awkward user interface
– Long-lived transactional “wrappers” vs
– Short-lived “versions”
• Programmer conventions
– List element points to wrapper which
points to list ….
– Don’t use short-lived objects beyond
lifetime ….
3
Old-School Atomic Classes
public class List {
public int item;
public TMObject<List> next;
}
Next field is explicit wrapper
4
Old-School Atomic Classes
List next = list.next.OpenRead();
Explicit open
(specify read or write)
5
Old-School Atomic Classes
List next = list.next.OpenRead();
Must discard after transaction,
don’t modify, etc…
6
Old-School Atomic Classes
List wVersion
rVersion == list.next.OpenWrite();
list.next.OpenRead();
List
List rVersion
wVersion == list.next.OpenRead();
list.next.OpenWrite();
List
wVersion.item++;
Read version
Read version
unchanged
changed
7
Library approach
• Intercept field accesses
– SXM (C#)
– DSTM2 (Java™)
• Programmer use factories
– Input is interface
– Synthesize code to intercept field
accesses
Software Transactional Memory
8
Examples
node.Key = 42;
// C# property style
Node.setKey(42);
// Java EJB style
9
Examples
node.Key = 42;
// C# property style
Node.setKey(42);
// Java EJB style
try {
T version = (T) start.get().newVersion;
final Method method = version.getClass().getMethod(methodName, _class);
return new Adapter.Setter<V>() {
public void call(V value) {
try {
ThreadState state = Thread.getLocalState();
…
10
Advantages
• Strong Atomicity
– Detects transactional/non-transactional
race conditions
• Natural programming style
– Almost sequential
– No complex conventions
11
Disadvantages
• Efficiency, efficiency, efficiency
– Even with fast-path optimizations
• Solution
– Use flow analysis to remove
synchronization
– Use MSFT Phoenix compiler
12
Lock-Based Runtime
List
RBTree
SkipList
HashTable
Buffer
SX
M
Li
br
1.
ar
1
y
O
p
Co ts
m
pi
le
r
Co
ns
t
Lo
RW ca
l
Pr
Su
o
bs mo
eq
ue
Pr nt
eO
pe
n
1,400,000
1,200,000
1,000,000
800,000
600,000
400,000
200,000
0
13
Obstruction-Free Run-Time
1,000,000
800,000
600,000
400,000
200,000
RBTree
SkipList
HashTable
Buffer
SX
M
Li
br
1.
ar
1
y
O
p
Co ts
m
pi
le
r
Co
ns
t
Lo
RW ca
l
Pr
Su
o
bs mo
eq
ue
Pr nt
eO
pe
n
0
List
14
Locking vs Obstruction-Free
200,000
150,000
100,000
Ofree
Locking
50,000
0
15
Conclusions
• Managed languages are also important
• Simple flow analysis goes a long way
• Do not rule out non-blocking
algorithms yet
16
Clip Art
17