STM
Software Transactional Memory
STM is a concurrency control mechanism that simplifies the process of writing concurrent programs. It allows for the execution of blocks of code (transactions) that can operate on shared memory that ensures consistency and avoids common concurrency problems such as deadlocks and race conditions.
In STM, code blocks are executed as transactions. A transaction is a sequence of read and write operations on shared memory that appears to execute atomically (indivisibly) from the perspective of other transactions. This means either all operations in the transaction are committed, or none are, if it is aborted.
Key Concepts of STM
Optimistic Concurrency Control: STM typically uses optimistic concurrency control. Transactions proceed without locking resources, assuming that conflicts are rare.
Isolation: STM ensures that the intermediate states of a transaction are not visible to other transactions.
Atomicity: STM guarantees that transactions are atomic, meaning that they either complete entirely or have no effect at all.
Consistency: STM ensures that each transaction takes the shared memory from one consistent state to another. This consistency is maintained by checking for conflicts and aborting and retrying transactions as necessary.
Implications
STM was initially designed to achieve serializability. However, serializability in STM doesn't necessarily result in a unique execution order, which is perfectly acceptable in conventional systems. This, however, is an inherent issue for blockchain systems. To achieve consensus, all nodes must arrive at the same state. STM does not ensure this because executing transactions in different orders can result in varying final states.
To solve this problem, there are two solutions:
Predefined execution order.
Conflict Avoidance.
A Predefined Order
When transactions must follow a strict predefined order, conflicts are more likely because STM reduces the flexibility of execution from any serializable order to a single specific order. Because there is no easy way to enforce a predefined order without introducing significant complexity and overhead. As a result, threads rely on a try-and-fail approach, repeatedly attempting to execute in the correct order until they succeed. This significantly increases the likelihood of conflicts and re-executions.
Conflict Avoidance
Among the various conflict avoidance measures, execution scheduling is indeed an effective strategy in STM (Software Transactional Memory) systems
Execution scheduling in Software Transactional Memory (STM) refers to the process of determining the order in which transactions are executed to minimize conflicts and ensure consistency. In STM, multiple transactions may attempt to access and modify shared data concurrently. Execution scheduling aims to manage these transactions in a way that avoids conflicts, maximizes parallelism, and maintains system performance and correctness.
Last updated