CIS4307: Transactional Memory

  • Lock-based code does not compose: Consider two protected bounded buffers queue1 and queue2. Multiple processes will put into queue1 and multiple processes will get from queue2. In between queue1 and queue2 are processes that get from queue1 and put in queue2. We want that this action of getting and putting be atomic. Thas is, two intermediaries doing the pair get-put will not have their actions interleaved and their pairs will be executed in the order of their gets.
    Using protected bounded buffers to achieve this behavior we would have to throw away the standard lock+condition implementation of protected bounded buffers and come out with one that also satisfies the new requirement.
    Another example would be: supposes that we store in a hashtable pairs [accountId, balance] and we protect the individual pairs so that updates are atomic. Then if we want to have atomic transfers of values between two pairs we will have to make a completely new implementation.

    To facilitate the development of concurrent programs on Multi Core Chips (MCC) and on Shared Memory Systems (SMS) it has been proposed the concept of Transactional Memory, inspired by the concept of Transactions in use with data base systems. The idea is to be able to group a number of read/write memory operations and execute them atomically, either they are successfully carried out even in the presence of concurrent operations, or they fail and are retried. Implementations have been suggested fully in hardware, fully in sofware, and with a mix of hardware and software. We will discuss the software approach. In the following I repeat essentially word per word a presentation made by Simon Peyton Jones of Microsoft. The constructs introduced below are present in STM Haskell: http://haskell.org/ghc which can be downloaded and experimented with.

    The Atomic Statement

    atomic { .. CODE ...}
    A possible implementation goes as follows: at the beginning of the atomic code an empty log is created. All write actions of the code are reported in log[name of variable and new value], not done in memory. All read actions actions are first done on the log, and if not there then in memory, in which case the name of the variable and its value are recorded in the log. If the actions aborts, the log is cleared and the action restarted. If the action succeeds then a global lock, or an individual lock on all the variables in the log, linearly ordered, is established. The values of the read variables in the log are compared to their values in memory. If different the action aborts, the log is cleared, and the action restarted. If the same, the action commits, the writes are carried out on memory, the log is deleted, and the locks released.

    This construct, in addition to Atomicity, has another important property: Isolation, that is, the intermediate values of the variables appearing in the CODE are not visible to concurrent programs. Viceversa, the CODE does not see changes which may be made to those variables by concurrent programs. This is achieved thanks to the type system of Haskell [mystery] which also prevents the inclusion of operations with side effects such as printing, or activating an effector.

    The Retry Statement

    atomic {if n_items== 0 then retry
		else ...remove from queue... }
    The retry statement follows a boolean expression (in this case n_items == 0), then the run time will let the statement sleep until some of the variables in the expression are changed, at which time the atomic statement is retried.

    Composition

    atomic {x = queue1.getItem(); queue2.putItem( x ) }

    Choice

    atomic {x = queue1.getItem()
	;choose
		queue2.putItem(x)
	orElse
		queue3.putItem(x) }

    Choice composes too

    atomic {x = queue1.getItem()
	; choose
		queue2.putItem(x)
	orElse
		queue3.putItem(x) }