Some STM thoughts, Part I

Last 5 months I have been working on Multiverse and I have gained a lot of new insights:

  1. Concurrency control in an stm is nothing else than saying something about the ordering of transaction execution.
    If there is no shared state, the result of executing transactions will be the same no matter the order, so they are allowed to execute concurrently. If there is shared state, the result of the transactions needs to be the same as one of the 2 possible sequential executions. So concurrency control is creating a partial ordering in the execution of transactions.
  2. Locking essentially leads to an ordering of concurrent executing transactions.
  3. A write-conflict is nothing more than an illegal interleaving of concurrent executing transactions. A write-conflicts happens when an another transaction writes to one or more shared addresses after the current transaction starts and before it commits. A write-conflict would be impossible if transactions execute sequentially.
  4. A deadlock also is nothing more than an illegal interleaving of concurrent executing transactions. Since there is shared state (the locks for example) one transaction needs to execute before the other, or after the other. In both cases a deadlock is impossible because one transaction has finished completely, and releases its locks, before the other begins.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: