TimHarris TimHarris

Niner since 2006


  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    ebdrup wrote:
    my intuition says it should work if I do all looking up and updating of the _typeInts inside an atomic block.
    But suppose the ContainsKey is run and another thread interrupts before the int[] is calculated. The other thread runs the same atomic operation to completion, would the first atomic opration retry because some state it read was updated or would it throw an exception when trying to insert a duplicate key?

    Hi -- yes, if the second thread's atomic block commits while the first thread's one is still running then the runtime system will detect the conflict, roll back the first thread's attempt, and then re-execute it (when it will see the update that the second thread has made). 


  • Programming in the Age of Concurrency: Software ​Transaction​al Memory

    Hi, great questions --

    staceyw wrote:
    1) I missed a fundamental idea I think.  It sound as if the last writer wins.  So if I have an atomic block, I can make changes to state.  But another thread can write to the state and commit, but the first atomic block will then rollback.  What did I miss?

    You're right, this is what the implementation in Haskell will do.  But there's actually a lot of flexibility for the implementation to do other things -- maybe to guarantee some kind of fairness between threads so that the atomic blocks of one thread don't keep on getting rolled back by the atomic blocks of another, or to hold off the execution of one thread's atomic block because it's really likely to conflict with another (if conflicts are really likely then its best to run the atomic blocks sequentially rather than in parallel).

    I think this is one of the nice things about atomic blocks -- the abstraction provided to the programmer is "all this happens atomically", but the implementation can do smarter things to reduce the wasted work caused by atomic blocks being rolled back. 

    If you want to read more about this aspect of transactional memory, then Michael Scott's group at U Rochester has done a lot of nice work in the area.

    staceyw wrote:
    2) Charles, you had a good question that don't think was fully answered in the vid.  Doing async in the block.

          // Do some stuff
               delegate(int i)
                    // Do some stuff in callback.

    We do some stuff and then kick off an async operation.  But then we exit the atomic block right away because the async operation does not block.  So the callback is not executed in atomic anymore.  And worse yet,  the code appears as if it is still executed in the block.  What I am missing?  Or was the answer just to never do this?

    That's a difficult question!  As you say, one answer could be that this should never be done -- in Haskell we have a very clear separation between things that can be done in atomic blocks (like updates to shared memory), and things that can't (like creating new threads). 

    Another answer could be that the BeginXXX action kicks off the async operation as normal when the atomic block commits, but that the delegate runs in its own transaction when its called.  

    A third option is that the async actions are kicked off when the atomic block commits, and the delegates then just run normally.  This option fits in with one of the ways that we've sometimes explained the semantics of atomic blocks: think of "atomic" as causing the thread entering the block to suspend all of the others in the system and then run in isolation, resuming the other threads when it reaches the end of the block.

    As I said though, it's a difficult question; maybe there are better options than these three!

    staceyw wrote:
    3)  How does long running I/O and DB transactions play with this.  So in a normal app, I would need both to be atomic.  I need the in-memory objects to be atomic and the DB to be atomic in a single transaction.  How does this work?

    Another great topic Smiley.  At the moment we're looking at adding features to the Haskell implementation to do this kind of thing.  Basically it involves doing a two-phase commit that involves the transactional memory and the database -- that means getting the transactional memory and database to both vote that their part of the transaction is OK to commit, and then only doing the commit once both have voted OK.  It adds some complexity to the implementation -- after the transactional memory has voted OK then it can't go back on its decision and abort.  I did actually look at this kind of technique in an earlier system using transactional memory -- there's a bit about it in a paper "Exceptions and side effects in atomic blocks" linked from my page https://research.microsoft.com/~tharris.

    The thing that's really important to remember for atomic blocks, though, is that it must make sense for the block's contents to occur as a single atomic action.  For instance, atomic blocks that just perform input or just perform output are OK (e.g. we can buffer up the output until the block commits), but an atomic block that writes something on the screen, waits for a user's interaction, and then continues isn't OK -- that's really two separate actions (one before the user's input, and one after the user's input), rather than a single atomic action.