NZTM:Non-blocking Zero Indirection TM

这篇文章是2007年的，Sun的人写的。Sun在Transactional Memory方面的研究似乎很厉害，经常看到他们的文章。这篇文章介绍的TM仍然是HyTM，但是，我觉得他们的NZSTM的实现比较有意思。可是，就文章中的性能评测来看，NZSTM的性能是很差的。文章解释说这是由于还没有进行调优。下面仔细说明了NZSTM是怎么回事。
This interface presented is similar to DSTM.
Transaction and NZObject datastructures ref the graph in original paper.
1. One difference with DSTM is when a trans detects a confliction with another,
    it can wait, or it can "request" the second to abort its self instead of
    just aborting the second. This is done using the AbortNowPlease flag.

AbortNowPlease flag:
    If an active trans observes that its AbortNowPlease flag is set, it will
    change its status to Aborted.
    If an trans request another to abort, it wait until that one's status
    becomes Aborted, then it can safely open the object.

data field of a NZObject
    Normally contains the current version of the wrapped object.
    If a trans T wants to modify the data, T must get exclusive ownership by
    placing a pointer to T in the WriterTXN field. Before modefying, T must also
    invoke clone to make a copy of the data, put the pointer to the copy in
    OldData field. This copy is needed in case T aborts.
    (This copy can stored just after the data field, add another field to
    indicate which is the current version, to improve locality. DSTM2)

Visible Reader
    NZSTM using visible reader, when a reader open an object for reading, it
    insert a pointer to itself in the ReaderList. (This can eliminate the
    Validating process, but add a little overhead in openning the object for
    reading and a non-trivil overhead in openning the object for writing)

Openning For Write
    A trans T want to open an NZObject to write.
    If T finds that the WriterTXN field has a pointer points to itself, T has
    previously opened the object for write, so just return the data.
    Otherwise, T must ensure there are no conflicts with other trans.
    Deal with writing conflict:
    If WriterTXN is NULL or points to a trans with status Commited or Aborted,
    there are no write conflicts. T put its pointer in WriterTXN using a CAS.
    If WriterTXN points to an Active trans T', then T asks the CM, wait or
    request T' to abort.(This request canbe implemented with a signal) After T'
    has aborted itself, T can get WriterTXN pointing to itself.
    Deal with reading conflict:
    T traversal the ReaderList looking for active trans. For each one it found,
    except itself, T asks CM, wait or request that trans to abort as above.
    If T is in ReaderList, it upgrade itself from reading to writing, delete the
    entry in ReaderList.
    After all conflits are resolved:
    If the object is owned by an Aborted trans just before T get it, T need to
    restore the backup copy(OldData), otherwise T create a new one. Finally, T
    can access the data.

Openning for Read
    A trans T want to open an NZObject to read.
    If T already own the object for writing, just return the data.
    Otherwise, T check writing conflicts and resovle it as above.Then do the
    following:
    1. T temporarily get exclusive ownship of the object by swapping the
    WriterTXN to point to itself.(to avoid a trans openning this obj for
    writting, and does not find that T insert itself into ReaderList. This
    operation may have bad effect ???)
    2. Add T to ReaderList(There must be no entry in ReaderList this time).
    3. Check whether the previous Writer trans was aborted, if so, restores the
    backup copy and store NULL to the OldData field.
    4. Release the ownership by swapping WriterTXN to NULL
    5. Return data

Make it non-blocking
    1. Reason for blocking. Trans T request T' to abort must wait T' 's response
    by seeing that T' 's status is Aborted. Otherwise, while T access the data,
    there may still be some stores from T', that would be problem.
    2. Using short HTM can easy make this non-blocking. Every store is an HTM.
    This HTM first check that AbortNowPlease is not set, the perform the store.
    3. Using softwre make it non-blocking
    When an trans is requested to abort and it does not respond, we using a
    DSTM-like approach. Use WriterTXN as the Start pointer.
    When T request the current owner T' of a object to abort, and T' does not
    respond:
    a. T create a DSTM locator. Locator's Transaction field points to T, Old
    field points to the backup copy created by T'(or just data field if this
    copy does not exists), New field points to a new copy of Old's backup copy.
    This Locator has an additional field AbortedTXN, points to T'.
    b. Using CAS to swap the NZObject's WriterTXN to points to the Locator.
    c. Thus treate an NZObject as an DSTM object( And each new Locator must have
    the AbortedTXN field set to same as the replaced Locator).
    If the unresponsive trans T' finally abort itself, we need to restore the
    STM like object to normal NZObject, using a transaction RT:
    a. RT open the object for writing as DSTM, except tha it stores a pointer to
    its own in the AbortedTXN field of the new Locator.
    b. RT store pointer to current object value(in Old field) into OldData field
    c. RT using a CAS to swap WriterTXN to point itself, if success, RT copy
    OldData back to the data field and process normally, if failed, RT just
    abort itself.