Introduction to Software Transactional Memory and Concurrent Programming

An Introduction to Software Transactional Memory Alessia Milani Labri, Bordeaux

Popularizing Concurrent Programming A multi-core revolution is underway Exploit the power of concurrent computing, by restructuring applications Devise scalable concurrent programs is hard unless good abstractions : Transaction 2

Transaction A transaction is a sequence of operations by a single process on a set of shared data items (transactional objects) that ends Either by committing : all of its updates take effect atomically or by aborting : has no effect (typically restarted) 3

Transactional Memory (TM) To simplify : Just wrap (sequential) code in begin / end transaction TM synchronizes memory accesses so that each transaction seems to execute sequentially and in isolation begin-transaction ------------ ------------- ------------ ------------ ------------ end-transaction 4

Implementing Transactional Memory TM was originally suggested as hardware platform [Herlihy and Moss 1993] HTM is in today hardware platforms, e.g. Intel, IBM, Sun Purely in software : First Software Transactional Memory (STM) only for static transactions [Shavit & Touitou 1995] First dynamic STM [Herlihy, Luchnagco, Moir and Schrer 2003] Hybrid schemes (HyTM) that combine hardware and software [Moir et al. 2006]

Implementing Transactional Memory in Software (STM) Data representation for transactions and data items using base objects begin-transaction read base objects read Algorithms Algorithms for operations on data items, applying primitives to base objects registers, CAS, DCAS write TryCommit end-transaction Asynchronous processes execute these algorithms to execute the operations of the transactions 6

3 levels of abstractions Transaction tryC read write read Operations on data items: E.g., read and write tryCommit / tryAbort Primitives on base objects (registers, CAS ) 7

STM algorithms Main Techniques 8

Back to TM Consistency Serializability: committed transactions appear to execute sequentially begin-Tx Commit read write write read TryC begin-Tx Commit read read write TryC begin-Tx Commit begin-Tx Commit read write write TryC read TryC read write read

Back to TM Consistency Serializability: committed transactions appear to execute sequentially Strict serializability: also preserves the order of non-overlapping transactions [Papadimitriou 1979] serializability strict serializability Opacity: even transactions that later abort are (strictly) serializable [Guerraoui, Kapalka POPL 2008] opacity Much more

Conflicts begin-Tx begin-Tx Commit Commit Read(x)0 Read(x)0 Write(x)1 Write(y)1 p1 p1 begin-Tx Commit begin-Tx Commit Write(x)2 Read(x)0 Write(x)1 Read(y)0 p2 p2 Two concurrent transactions have a conflict if they access the same data item and at least one of these accesses is a Write operation. Two transactions that cannot be serialized have a conflict. (The converse is not true) 11

Design approaches Deferred/Direct updates : operate on local copies of the data items & install changes at commit/ Modify in place, roll back on abort Detect conflicts Commit time Encountering time Resolve a conflict either by aborting one of the conflicting transactions or by waiting/helping it to complete This depends on the progress you want Contention manager 12

Contention Manager Strategies Priority to Oldest? Most work? None Dominates Lots of empirical work but formal work in infancy 13

Progress for TM Lock-free TM Wait-freedom : each non-faulty process completes (successfully) its transaction within a finite number of steps Obstruction-freedom : a process running solo eventually commits its transaction Lock-Based TM Weakly progressive: a transaction aborts only if it has conflicts [Guerraoui, Kapalka POPL 2009] Strongly progressive: at least one of the transactions involved in the conflict commits Multi-version permissive: only writing transaction that conflicts with another writing transaction aborts [Perelman, Fan, Keidar PODC 2010] Read-only transactions always commit

STM algorithms Two Case Studies 15

A lock-based STM : TL2 [Dice et al. DISC 2006] Each data item is associated with a version number TL2 relies on a global versioning clock Transaction keeps Read set: data items & values read Write set: data items & values to be written Deferred update Changes installed at commit Lazy conflict detection Conflicts detected at commit 16

Read-Only Transactions Mem Locks Copy version clock to local read version clock RV 12 32 56 19 100 100 17 Shared Version Clock Private Read Version (RV) 17 17

Read-Only Transactions Mem Locks Copy version clock to local read version clock Each read operation is post- validated checking the lock and version # of the corresponding memory location 12 32 56 19 100 100 17 Shared Version Clock Private Read Version (RV) 18 18 18

Read-Only Transactions Mem Locks Copy version clock to local read version clock Read lock, version #, and memory, check version # less than read clock 12 32 COMMIT if no post-validation fails. Otherwise ABORT as soon as one Read fails 56 19 100 100 17 Shared Version Clock Private Read Version (RV) 19 19 19

Read-Only Transactions Mem Locks 12 32 We have taken a snapshot without keeping an explicit read set! 56 19 100 100 17 Shared Version Clock Private Read Version (RV) 20 20 20

Example Execution: Read Only Trans Mem Locks Shared Version Clock 100 1. RV Shared Version Clock 2. On Read: read lock, read mem, read lock: check unlocked, unchanged, and v# <= RV 3. Commit. 87 0 87 0 87 0 87 0 34 0 34 0 34 0 34 0 88 0 88 0 V# 0 99 0 99 0 99 0 V# 0 99 0 44 0 44 0 Reads form a snapshot of memory. No read set! V# 0 50 0 50 0 50 0 V# 0 50 0 100 RV

Writing Transactions Mem Locks Copy version clock to local read version clock RV 12 32 56 19 100 100 17 Shared Version Clock Private Read Version (RV) 22 22 22

Writing Transactions Mem Locks Copy version clock to local read version clock On read/write, check: Unlocked & version # < RV Add to R/W set 12 32 56 19 100 100 17 Shared Version Clock Private Read Version (RV) 23 23 23

On Commit Mem Locks Acquire write locks 12 32 56 19 100 100 17 Private Read Version (RV) Shared Version Clock 24 24

On Commit Mem Locks Acquire write locks Increment Version Clock 12 32 56 19 100 100 101 17 Private Read Version (RV) Shared Version Clock Art of Multiprocessor Programming 25 25 25

On Commit Mem Locks Acquire write locks Increment Version Clock Check version numbers RV 12 32 56 19 100 100 101 17 Private Read Version (RV) Shared Version Clock Art of Multiprocessor Programming 26 26 26

On Commit Mem Locks Acquire write locks Increment Version Clock Check version numbers RV Update memory 12 x 32 56 19 100 100 101 y 17 Private Read Version (RV) Shared Version Clock 27 27 27

On Commit Mem Locks Acquire write locks Increment Version Clock Check version numbers RV Update memory Update write version #s 12 x 32 101 56 19 100 100 101 y 17 101 Private Read Version (RV) Shared Version Clock 28 28 28

Example: Writing Transaction Shared Version Clock Mem Locks 100 100 120 121 87 0 1. RV Shared Version Clock 2. On Read/Write: check unlocked and v# <= RV then add to Read/Write-Set 3. Acquire Locks 4. WV = F&I(VClock) 5. Validate each v# <= RV 6. Release locks with v# WV 87 0 87 0 87 0 87 0 X 121 0 X 34 0 34 0 34 0 34 1 121 0 88 0 88 0 Y V# 0 121 0 99 0 99 0 99 0 99 1 121 0 Y 44 0 44 0 V# 0 50 0 V# 0 50 0 50 0 50 0 50 0 Commit RV 100 29

A lock-free STM : Dynamic Software Transactional Memory Proposed in [Herlihy et al. DISC 2003] Opacity & obstruction freedom Transaction keeps Read set: data items & values read Direct update Changes installed when the corresponding Write is executed Eager conflict detection Conflicts detected at encountering time 30

DSTM : transaction and transactional object representation A transaction has a status field that is initialized to be ACTIVE, and it is later COMMITED or ABORTED using a CAS primitive a readlist to store the data items read together with the values read Status of the transaction that most recently accessed the object to write it Each transactional object has the following structure status transaction new object old object start Data TMObject Locator Data

Current object version The current object version is determined by the status of the transaction that most recently accessed the object to WRITE : committed: the new object is the current aborted: the old object is the current active: the old object is the current, and the new is tentative The actual version only changes when a commit is successful

Write operation : example Transaction A tries to write object o. Let B be the transaction that most recently accessed o to WRITE it committed transaction new object old object Data start o Data B s Locator copy Use CAS in order to replace locator If CAS fails, A restarts from the beginning 4 transaction new object old object active Data A s Locator A creates a new Locator A sets old object to the previous new A copies the previous new object, and sets new 1 3 2

Which is the current version of the object if B is active? A and B are conflicting transactions, that run at the same time Use Contention Manager to decide which should continue and which should abort If B needs to abort, try to change its status to aborted (using CAS)

Read operation To read object o by a transaction A Fetch the current version v just as before Add the pair (o, v) to the read set of A

Validating a transaction Before returning the value either read or written, check consistency For each pair (o,v) in the read set, verify that v is still the most recently committed version of the transactional object o. Check that the status of the transaction is still ACTIVE

Committing a transaction The commit needs to do the following: 1. Validate the transaction 2. Change the transaction s status from active to committed (using CAS)

Thats it? You are here Multiversioning Elastic Txs Irrevocable transactions Privatization Distributed STM Nested transactions Lower bounds

More references and credits Many of these slides are (largely inspired) from The slides of The Art of Multiprocessor Programming by Maurice Herlihy and Nir Shavit A PODC 2010 talk by Hagit Attiya Teaching slides by Danny Hendler Other reference : Transactional Memory,Foundations, Algorithms, Tools, and Applications. COST Action Euro-TM IC1001. Lecture Notes in Computer Science, Springer 2014.