Transactional Locking II

这篇文章是2006年的一篇文章，是"What makes transaction faster"那篇文章的后继版本
。这篇文章在前一篇提出的TL的基础上提出了TL2的方法。这篇文章主要改进的地方是，
避免了在Transaction执行过程中可能会有的短时间的在不一致（不安全）的数据上的执行
。它为引入了一个全局量，类似一个逻辑时钟。用这个时钟记录每一个Write
Transaction提交的时间和每一个location最后一次被写的时间。一个关键的问题就是，怎
么实现这个全局量。如果只是用一个共享变量，会有额外的冲突，更严重的是会有cache一
致性的问题，后者会严重影响性能。其实，在TL中，最重要的是那个read set的构建代价
太大，怎么减少这些代价？事实上，当数据结构较小的时候，TL的性能比TL2更好，而当数
据结构很大的时候，TL2的优势就显示出来了。

Transactional Locking II
TL2 uses commit mode of TL. There is a shared global-version variable per
transaction system implementation(per application or per datastructure). Each
transaction has a local read set(containing the lock addresses associated with
variables it read) and a local write set (containing the addresses, the values
it write).

Writing Transactions (transactions that writes the shared memory)
1. Sample the global version-clock. Load it into a thread local variable called
    read version number(rv).
2. Run through a speculative execution.
    Load:
    a. Check to see if the load address appears in its write set. If so, return
    the value. Do not execute step (d).
    b. load the variable, load the lock, check the lock is free, and version in
    it is <= rv
    c. Added an entry in local read set.
    Store:
    store each (address, value) pair in the local write-set
3. Commit
    a. Lock the write set just like TL.
    b. Increament and fetch global version clock atomically. Recording the
    current value of global version in a local variable write version number(wv)
    .
    c. Validate the read set
        if rv+1 == wv return true
        Checking every location in the read set that the version number
        associated with the versioned-write-lock is <= rv
    d. write each location in write set back to variable, release the locks and
        set the version to wv(use a store).

Low-Cost Read-Only transaction(Transactions not modifying the shared data)
    1. Sample the global-version-clock, load it to a local variable rv.
    2. After each load, check that the associated lock is free and version is
    <= rv, otherwise abort.

Problem: How does the paper implements the low contention global version clock?

To make TL or TL2 can use hardware transactions, we only need let the HTM
checking that every location it read or write has a free lock, and every write
location's lock is increamanted.