Angel \”Java\” Lopez on Blog

June 7, 2010

Memory transactions in AjSharp using References

Filed under: .NET, AjSharp, Open Source Projects — ajlopez @ 9:07 am

Last year, I met Clojure, a Lisp dialect compiled to Java. I was coding AjSharpure (see AjLisp Family: Implementing Lisp Interpreters in C#), a Clojure-like interpreter (not compiler), in .NET (if you want a more complete implementation, there is a ClojureCLR, implemented in .NET compiled using DLR, Dynamic Language Runtime).

Clojure has many striking features, specially in persistent structures (“inmutable” list, dictionaries, trees…), concurrency, agents, and more. One feature is STM, software transactional memory. More about these topics in links at end of this post. According to:

http://en.wikipedia.org/wiki/Software_transactional_memory

In computer science, software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. It is an alternative to lock-based synchronization. A transaction in this context is a piece of code that executes a series of reads and writes to shared memory. These reads and writes logically occur at a single instant in time; intermediate states are not visible to other (successful) transactions.

Some weeks ago, I read:

Clojure concurrency Part 4

The article describe the behavior of “ref”, “dosync” and related operations. I wanted to experiment with such features, but in my AjSharp interpreter. So, I wrote a Reference class, and added transaction support to the language.

Now, I can write:

reference = new Reference();
reference <- 1;
result = @reference;

The Reference class is a built-in one, in AjLanguage. Using <- operator is equivalent to ref.SetValue(newvalue). Now, I added the @ operator to get the value, and it is equivalent to ref.GetValue() (Incidentally, GetValue and SetValue are the method of the interface for Channels and Futures, see:

AjSharp: Implementing Futures

Channels and Go Routines in AjSharp (Part 1)

Channels and Go Routines in AjSharp (Part 2)

In those posts, I still wrote <-channel or <-future to GET the value of a channel or future; now, I deprecated such notation, in favor of @channel, @future, that is, in my opinion, more clear).

I decided to make explicit the get/set of a reference, instead of make it transparent. But, what is the purpose? Well, now, I can use the new transaction keyword:

channel1 = new Channel();
end1 = new Channel();
end2 = new Channel();
reference1 = new Reference();
reference2 = new Reference();
reference1 <- 1;
reference2 <- 2;
go transaction 
{ 
  reference1 <- @channel1; 
  result2original = @reference2; 
  end1 <- @reference1; 
}
go transaction 
{ 
  channel1 <- @reference2; 
  reference2 <- @reference2 + 1; 
  result1original = @reference1; 
  end2 <- @reference2; 
}
result1 = @end1; // 2
result2 = @end2; // 3

The two transactions are launched via go command (read the above cited posts about go routines). The first transaction wait for a value from the second one, using the channel in variable channel1. The values in reference1, reference2 in first transactions are the original one, although the second transaction is changing them. That is, a transaction sees an snapshot of its reference values, taken at the beginning of its life. A change of a reference value during a transaction,  is committed at the end of the transaction, and then, it became visible to the rest of of application (but the still running transactions are viewing the snapshot value). If a transaction change a value altered by other concurrent transaction, an exception will be raised.

My implementation is a naive one. I guess I could improve its efficiency. But now, all tests are in green, and it’s good enough for my experiments. Internally, each reference has a current visible value, an updated value (if exists) corresponding only to one or zero transaction, and a list of snapshot value, only to feed still running transaction. A Machine instance (associated by running thread) keeps a list of reference with snapshots, and a list of still running transactions.

My links:

http://delicious.com/ajlopez/clojure

http://delicious.com/ajlopez/clojure+concurrency

http://delicious.com/ajlopez/clojure+tutorial

http://delicious.com/ajlopez/stm

http://delicious.com/ajlopez/clojure+stm

As usual, you can download the code from:

http://code.google.com/p/ajcodekatas/source/browse/

under trunk/AjLanguage.

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

1 Comment »

  1. […] I was experimenting with lightweight implementations of tries, the data structure used to keep storage and calculate hash roots of state of worlds (see Building a blockchain (5)). My idea to parallelize the execution of transactions is to use a trie that support multithreading execution, detecting any conflict of read/write storage btw transactions. If N transactions can be executed without conflicts (ie, a conflict could be two transactions writing the same storage cell), then they could be executed in parallel. The base idea: use ideas from software transactional memory implementations (see Memory Transactions In AjSharp Using References). […]

    Pingback by Scaling Ethereum/RSK (1) | Angel "Java" Lopez on Blog — October 31, 2016 @ 9:48 am


RSS feed for comments on this post. TrackBack URI

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

Blog at WordPress.com.

%d bloggers like this: