Stanford CS149 I Parallel Computing I 2023 I Lecture 16 - Transactional Memory 1

Synchronization Challenges

• Modern systems use load linked and store conditional memory operations, managed by the coherence system, to implement atomic load and store for synchronization primitives. (1m30s)
• Programming with synchronization primitives, even at higher levels of abstraction like locks and barriers, remains challenging due to the difficulty of developing lock-free data structures and the potential for deadlock. (1m57s)

Transactions as a Solution

• Transactions offer a potential solution to the challenges of synchronization by providing a higher level of abstraction and potentially improving performance. (2m36s)
• Transactional memory, inspired by database transactions, provides atomicity, isolation, and serializability, but not durability. (12m21s)

Atomic Construct

• To prevent synchronization issues when multiple threads access shared data, the atomic construct can be used to ensure a sequence of statements are executed atomically. (7m35s)
• The atomic construct is a declarative abstraction, meaning the programmer specifies the desired outcome (atomic execution) without specifying the implementation details (e.g., using locks). (8m32s)

Transactional Consistency

• Transactional consistency, similar to sequential consistency, involves a bulk operation of memory references. (14m14s)
• Transactions can provide an easy-to-use programming model coupled with high performance because they offer the performance benefit of fine-grain concurrency. (26m11s)

Thread-Safe Data Structures

• Java's synchronized HashMap, while thread-safe, can have performance limitations due to its single lock for the entire data structure. (16m55s)
• Fine-grained locking, such as using a lock per bucket in a HashMap, can improve concurrency and performance but introduces implementation complexity and overhead. (18m28s)

Transactional Programming

• Transactions will only be serialized when there are conflicts between the read and write states of two transactions. (26m32s)
• To make a doubly linked list's pushLeft method thread-safe using transactions, make all the operations on the variables associated with the list atomic. (27m53s)
• Transactions offer a straightforward approach to programming and provide advantages in handling failures. (28m23s)
• Transactions simplify failure recovery by reverting the system to its initial state if an abort occurs, eliminating the need for manual cleanup or lock release. (28m54s)
• While locks can lead to deadlocks, especially in scenarios like nested synchronized blocks, transactions offer a solution by serializing conflicting operations and enabling concurrency when there are no conflicts. (30m38s)

Transactional Memory and Concurrency

• Transactional memory allows for concurrency if there are no conflicts. (35m53s)
• Atomic atomicity requires all code within the atomic block to execute at once in relation to other threads. (41m37s)
• Replacing a synchronized block with an atomic block may not always work, especially if the code relies on the order of execution between threads. (41m2s)

Transactional Memory Implementation

• Transactional memory implementations must provide atomicity, isolation, and serializability while maximizing concurrency. (44m16s)
• Two key aspects of transactional memory implementation are data versioning (managing committed and uncommitted state) and transaction conflict detection. (45m21s)

Data Versioning

• Eager versioning updates memory (or cache) as soon as possible and relies on an undo log to revert changes if the transaction aborts. (46m20s)
• Eager versioning updates memory directly and maintains an undo log, resulting in faster commits but slower aborts. (53m54s)
• Lazy versioning utilizes a write buffer, potentially requiring checks in multiple places. It offers faster aborts but slower commits. (54m31s)

Conflict Detection

• Conflict detection is crucial in transactional memory, with pessimistic detection aiming to identify conflicts early and optimistic detection deferring conflict checks until the transaction's end. (56m22s)
• Transaction zero's read set includes 'a' and its write set includes 'c', while transaction one's write set includes 'b'. There is no conflict, so both transactions commit. (1h0m20s)
• If transaction zero writes to 'a' and transaction one reads 'a', there is a conflict. Transaction one could be stalled to avoid discarding its work, waiting for transaction zero to complete. (1h1m53s)
• If transaction zero reads 'a' and then transaction one writes to 'a', transaction zero aborts and restarts. This demonstrates the "writer wins" policy in aggressive contention management. (1h6m29s)

Pessimistic Transactional Memory

• Pessimistic transactional memory checks for conflicts before a read operation. If a conflict is detected, the transaction stalls until the conflict is resolved. (1h8m11s)
• A live lock situation occurs when two or more transactions repeatedly abort and restart due to conflicting operations, preventing any progress. The system needs to detect and resolve such situations. (1h10m16s)

Optimistic Transactional Memory

• Optimistic transactional memory assumes no conflicts and only performs conflict detection during the commit phase. If a conflict is detected during commit, the transaction is aborted and restarted. (1h12m27s)
• When a transaction commits, it updates the memory state, and there are no conflicts with other existing writes due to serialization. The read of variable 'a' occurs before the write of 'a' in the serialized order, so transaction zero does not see updates from transaction one. (1h16m58s)
• If the read set of T1 and T0 are both 'a' and the write set of T0 and T1 are both 'a', T0 should restart due to a conflict with the committing transaction. Optimistic detection allows for forward progress in this scenario. (1h17m40s)
• Eager versioning and optimistic detection do not work well together. (1h19m12s)
• In case 3, there is no conflict because the write set is empty. The right set of the committing transaction is compared against the read sets of other transactions. (1h19m48s)