Transparent support for wait-free transactions

随手的笔记，有兴趣可以看看
    This paper concerns software support for non-blocking transactions in shared
    memory mutiprocessors. This implementation supports dynamic transactions.
    The key is using a lock-free(but not wait-free) multi-word compare and swap
    operation.
    1. This implementation is based on a "conditional wait-free" MWCAS
    operation. The wait-free MWCAS is costly in memory and less effecient, and
    the lock-free(not wait-free) ones are not guarantee termination. The
    conditional wait-free is a lock-free implementation and allows comunicating
    with external helpping mechanism. This allows to using a high level helping
    mechanism to guarantee termination.
    2. One word compare and swap operation.
    3. The implementation of Multi-word compare and swap operation in this paper
    is similar to STM with a few optimizations specific to MWCAS.
%{
/* conditionally wait-free MWCAS operation implementation*/
/* hard to understand...*/
type valtype /*any type that fits into one machine word;*/
lock_type=record
        owner:-1..N-1
        index:0..W-1
        end
par_type=record
        nw:1..W
        addr:array[0..W-1] of 0..M-1
        old,new:array[0..W-1] of valtype
        end
stat_type=record
        stat:{init,lock,modify,unlock}
        flag:{succ,fail,retry,none}
        end
/* shared variables    */   
LOCK:array[0..M-1] of lock_type init (-1,0)
STAT:array[0..N-1] of stat_type init (init,succ)
MEM:array[0..M-1] of valtype
PAR:array[0..N-1] of par_type
}%
   Note: Lock-free means that a thread cannot lock up, every step it takes
   brings progress to system(even a process crashes or held up, the rest of the
   system still carry on). Wait-free means that a thread can finish an
   operation in a finite number of steps, regardless of the actions of other
   threads. Obstruction-free is the weakest one, it only demands that any
   partially-completed operation can be aborted and the changes made roll back.
   Observe from outside is that, at any point, a single thread executed in
   isolation(i.e. with all maybe obstructing threads suspended) for a bounded
   number of steps will complete its operation.
   4. An easy example of tm used in FIFO queue.
   5. I think this paper presented the "real" stm concept.
%{
/* lock-free transaction implementation explaned detailedly in paper*/
/* types */
type
wordtype=record
    ver: integer
    blk: 0..B-1+N*T
    pid: 0..N /* added for wait-free*/
    end
blktype=array [0..S-1] of valtype
nodeptr=pointer to nodetype
nodetype=record
    left, right: nodeptr
    blk: 0..B-1
    old, new: wordtype
    dirty: bool
    end
vertype=record /*added for wait-free*/
    ver: integer
    active: boolean
    end
anctype=record /* added for wait-free*/
    tran: trantype
    pars: partype
    end
/*shared data structures*/
BLK array[0..B-1+N*T] of blktype
/*0..B-1+2N for wait-free, 0..B-1 are treated as wordtype, B..B+N-1 as
 * valtype,B+N..B+2N-1 as vertype*/
BANK array[0..B-1] of wordtype
/*initially, BANK[n]=(0, n+N*T) && BLK[n+N*T] is nth block of initial value*/
/*private variables*/
copy, oldlst:array[0..T-1] of 0..B-1+N*T
i,cnt, dcnt: 0..T
blk:0..B-1
v:valtype
ret: valtype
view, ptr:nodeptr
/*initially copy[n]=p*T+n view==nil*/
/*following shared data are added for wait-free*/
ANC: array[0..N-1] of anctype
HELP: array[0..N-1, 0..N-1] of vertype
}%
    5. Wait-free implementation.
        Similar to lock-free one, except for a few changes.
        a. Add two words to MWCAS operation, the first records transaction
        return values, the second indicate that this transaction has been
        compeleted, donot re-execute it.
        b. Add an announce array to records transactions executed by processes,
        so other can help it finish this transaction.
        c. Introduce a HELP array, through which processes "request help" in
        order to ensure that their transactions eventually complete.
    6. MWCAS has limited some concurrency. See the last paragraph in paper.