Software Transactional Memory for Dynamic-Sized Da

阅读笔记
    This paper proposed a novle STM implementation. This STM support dynamic
    sized data structures. And the implementation is obstruction-free. This lead
    to a more efficient implementation. Authors also demo this STM with a
    red-black tree. This is the first dynamic STM. This STM supports
    transactions and transactional objects created dynamically, and transactions
    may determine the sequence of objects accessed based on the values observed
    earlier in the same transaction.
    1. Obstruction-freedom does not rule out livelock, unlike lock-freedom.
    Interfering concurrent threads may repeatedly prevent one another from
    making progress. But its simplicity admits a more effecient implementation,
    which is more effecient under the situation that the synchronization
    conflicts among concurrent threads is rare. Of course, other policy is used
    to ensuring the progress of system.
    2. TMObject is used as an container of regular objects. One may create a
    transactional object any time which is not part of a transaction.
    3. All successfully commited transactions is linearizable: they appear to
    execute in a one-at-a-time order.
    4. Transactions that eventually aborted has consistency problem. A
    transaction may see some inconsistency state among the objects it opened,
    This may cause some unexpected side effects. DSTM addresses this problem by
    validating a transaction whenever it opens a transaction objects. Validation
    consists of checking synchronization conflicts, that is, whether any
    transactional object opened by the transaction has since been opened in a
    conflicting mode by another transaction(Why not delay this testing to
    "opened in a conflicting mode and commit successfully" by another
    transaction).
    5. There is a example of Integer Set 's implemetation using DSTM in section
       2.
    6. To reduce the conflictings, DSTM provide two utils: one is open with
    status, a number of READ open don't conflict with each other; the other is
    release(), this must be carefully used, because it can cause the
    linearizability broken(Do not use this kinds of things, I think).
    7. Implementations
        a. Data structures
            For each TMObject
            a start pointer to a Locator
            a Locator contains:
                transaction: point to the transaction that most recently opened
                the TMObject in WRITE mode
                oldObject: point to an old object version
                newObject: point to a new object version
        b. The current version of the object is determined by the status of the
        transaction that most recently opened the TMObject in WRITE mode. If the
        transaction committed successfully, the newObject is current version; if
        the transaction aborted or active, the oldObject is current version. So
        that, if several TMObjects have most recently been opened in WRITE mode
        by the same active transaction, then changing the status field of that
        transaction from ACTIVE to COMMITED atomatically change the current
        version of the objects to its new version.
        c. Open a TMObject in WRITE mode
            (1). allocate a new Locator
            (2). If the target TMObject has a transaction in ACTIVE, aborted
            it(by change its status using cas) or let it complete according to
            contention manager.
            (3). set the Locator's oldObject point to the TMObject's current
            version
            (4). set the Locator's newObject point to a copy of oldObject
            (5). change TMObject's start point to the new Locator using cas.
            (6). if failed, retry.
        d. Open a TMObject in READ mode
            (1). same as (2) in c
            (2). add pair(o,v) to a thread-local table(o is the TMObject, and v
            is its current version), if this pair is already exists, increasing
            its counter.
        e. release a TMObject
            (1). decrease the counter, if the counter == 0, remove from the
            table
        f. validate a transaction
            after open has determined which version of an object to return, and
            before it actually returns that version:
            (1). for each pair (o,v) in the calling thread's table, verify that
            v is still the current version of o
            (2). check that the status field of the current transaction is
            ACITIVE
        g. Commit
            (1). validate entries in the table as (1) in f;
            (2). calling cas to attempt changing the status from ACTIVE to
            COMMITED
    8. Costs
        Without conflicts:
        Open W objects for writing is O(W);
        Open R objects for read and W for write, the validating cost is
        O((R+W)*R), a little bit inefficient.
        if there are conflicts...
    9. Contention manager is used to ensuring progress of the system.
    Obstruct-free distinct between the obstruct-free mechanism that ensure
    correctness and mechanism that ensure progress.
    10. Each thread has its own contention manager instance. Informally, any
    active transaction thar asks sufficiently many times must eventually get
    permission to abort a conflicting transaction(this ensure the correctness of
    the contention manager, but not ensure the progress of system.).
    10. In paper's implementation, defined a ContentionManager interface, so the
    programmer can implementation specific managers. This interface has two
    kinds of functions: notifications and feedbacks. notifications
    like(commitTransactionSuccess) is invoked every time a transaction has been
    commited; feedback functions is called by DSTM to determine what action to
    do, like(shouldAbort) is called with the conflicting thread's instance of
    contention manager as argument every time a conflicting is detected, this
    contention manager should decide return true or false.
    11. Note: There, in the contention manager, is a problem of scheduling
    12. In the author's words "One shortcoming is that there is no way for a
    transaction to detect that another transaction has opened an object in READ
    mode", if we can do this, there's no need to "validate a transaction", also
    have more chances to reduce contentions. In another aspect, this would
    increase the over head of openning an object.