CODEWITHSUNDEEP
concurrencyclojure
CHAPa
CHAPa

Reputation: 677

How does commute work?

How really commute works. (commute IDENTITY FUNCTION &values)

the Clojure Documentation says:

Usage: (commute ref fun & args)

Must be called in a transaction. Sets the in-transaction-value of ref to:

(apply fun in-transaction-value-of-ref args) and returns the in-transaction-value of ref.

At the commit point of the transaction, sets the value of ref to be:

(apply fun most-recently-committed-value-of-ref args)

So the commute form is performed in two phases.

is the second phase atomic ?(apply fun most-recently-committed-value-of-ref args)

if not, what happen in this example: 2 Threads ( T1 and T2 ).

Both will increment (commutative function) the same identity.

 IDENTITY: (def i (ref 0 ) 
        (dosync (commute inc i ) )

T1 in the first step of the commute call inc with ref i = 0 ( in transaction value = 1 )

T1 stop

T2 in the first step of the commute call inc with ref i= 0 ( in transaction value = 1 )

T2 stop

T1 in the second step call again inc with the recent commit value i = 0, the inc function return but before update the ref ( i ) T1 stop

T2 in the second step call again inc with the recent commit value i = 0 and update the reference

T1 start again and update the reference with the inc returned value = 1

This is a race condition problem ? how clojure avoid this ? if the second phase be atomic, this will no happen.

Thanks in advance

UPDATE: if i understand correctly the the last phase of the commute operations ( commit point ) is synchronized"LOCK commute fun UNLOCK**" ?

Upvotes: 1

Views: 1322

Answers (1)

michaelee
michaelee

Reputation: 66

The key is to realize that the in-transaction value of the ref (resulting from a commute) may in fact be different from the value that is ultimately written to the ref at the commit point.

In your example, threads T1 and T2 run their transactions simultaneously, with i referring to 0. They both (inc i) via commutes, and therefore both see i=1 during their transactions. When they are ready to commit, however, the function specified in the commute (inc) will be applied to the ref using the most-recently-committed value. So if T1 commits first, i=1, then T2 commits, and i=2. In answer to your question, these commits are indeed atomic, and so no race conditions are possible.

I quote the documentation for commute below:

At the commit point of the transaction, sets the value of ref to be:

(apply fun most-recently-committed-value-of-ref args)

Thus fun should be commutative, or, failing that, you must accept last-one-in-wins behavior.

The "last-one-in-wins" bit warns you that if the function you're applying is not commutative -- matrix multiplication comes to mind -- then in fact a race condition is possible. I.e., the transaction that commits first will have its function applied to the "original" ref value, and the next transaction to commit will have its function applied to the updated state. The function applications are still applied atomically, however.

Upvotes: 5

Related Questions