Concurrency and Software Transactional Memories

Download Report

Transcript Concurrency and Software Transactional Memories 

Concurrency and Software
Transactional Memories
Satnam Singh, Microsoft
Faculty Summit 2005
Concurrency and Parallelism
 Software
engineering.
 Multi-core.
 Future computing architectures.
 Reconfigurable
computing.
 Message passing multi-processor
systems.
 Alternative computing devices.
Concurrent Programming
Threads: C++, Java, C#
 Rendezvous: Ada.
 Synchronous: Esterel, Lustre.
 Join patterns: Jocaml, C-Omega.
 Implicit parallelism: functional
languages.
 Hardware: VHDL, Verilog.

Reconfigurable Systems
Code/Circuit Generation
VHDL, Verilog -> hardware implementation
Esterel design
void uart_device_driver ()
{
.....
}
uart.c
C -> software implementation
Hardware/Software
Fighting back

Formal analysis techniques:
contract checking
 behavioral types
 deadlock avoidance

Language level support for
concurreny.
 Lock free programming:

Lock-free data structures
 Software transactional memories

Transactional Memory
atomic
A.withdraw(3)
B.deposit(3)
end




IDEA
!
Herlihy/Moss ISCA 1993
Steal ideas from the database community.
atomic does what it says on the tin.
Directly supports what the programmer is
trying to do: an atomic transaction against
memory.
“Write the simple sequential code, and
wrap atomic around it”.
How does it work?
atomic
<body>





Optimistic
concurrency
Execute <body> without taking any locks.
Each read and write in <body> is logged
to a thread-local transaction log.
Writes go to the log only, not to memory.
At the end, the transaction tries to
commit to memory.
Commit may fail; then transaction is re-run
Transactional Memory
No races: no locks, so you can’t
forget to take one
 No lock-induced deadlock,
because no locks
 Error recovery trivial: an exception
inside atomic aborts the transaction
 Simple code is scalable.
 Implementation in Haskell:


orElse combinator
Summary

Question reliance on asynchronous
concurrent programming languages:
digital design
 synchronous reactive systems

Prepare for alternative computing
architectures.
 Formal analysis.
 Software Transactional Memories.
