Efficient STM(2005)

Intel的人在2005年作的一个STM，非常注重实用的效率。他们重点就是在Cache上提高效率。
Effecient Software Transactional Memory(2005)
    这篇文章提出了一个新的基于对象的STM设计。这个设计主要为了通过最小化cache冲突
    和主存带宽需求来做到最大化性能。与之前的设计相比，有以下四点差异。
    1. 对象的版本信息是内联地存储的。这避免了在找一个对象的当前数据的时候访问额
    外的cache line。
    2. Bookkeeping信息总是创建它的transaction的私有信息。这样，允许这些信息
    始终存在于那个trasn对应的处理器的cache line中。
    3. Bookkeeping信息的空间是顺序分配的，并且在对应的trans结束后立刻释放回收，
    这使得这些空间小而且局部性更好（不需要使用GC或是引用计数）。
    4. 本文的STM不保证在OS挂起某个trans的执行的时候，其它的trans可以前进。
    上面的第四个属性允许一个被挂起的trans阻挡当前trans的执行。但是，这篇文章有一
    句话很好“我们追求的是实现的高效性，而不是理论的完美性”(我觉得今天的计算机技
    术就是以这个为准则发展的)。文章做了两个前提假设。一，OS的调度不会造成某个
    trans的饥饿；二，trans之间可以相互发送信号。从实践来看，这两个假设是很合理的
    。当某个trans发现自己被别的trans阻挡的时候，它会向对方发送信号，请求对方
    abort。如果对方目前被挂起，则对方再次被唤醒的时候，会处理这个信号。只有对方
    被OS一直挂起，才会导致这个trans被永久的阻塞。根据假设，这是不会存在的。
    这篇文章的STM在基本的并发控制机制上类似于DSTM。但是，有两个特色：
    1. 使用可撤销的二阶段锁来管理写。
        当一个trans t想要写一个object o时，它必须首先获得o上的一个互斥锁。t会
        一直持有这个锁，直到它最终提交或是被强迫abort。如果t想写的object被另一个
        trans s锁住，t可以等待s的结束，也可以使s abort，偷过来那个object。
        这里，可撤销的锁并不会导致死锁，可以用于细粒度的锁，而传统的不可撤销的
        锁用于细粒度的锁时，有些不现实。
    2. 使用乐观的并发控制处理读。
        无论何时一个trans t读一个object，它记录下当前读到的object的版本。当t提交
        的时候，检查这些读的object的版本是否变化。这里，和read－lock不同的是，
        乐观的并发控制并不会导致多个读者的cache冲突。
    通过ContentionManager，该系统可以保证没有deadlock以及livelock，并且一个高优
    先级的trans不会永久地被一个低优先级的trans阻塞。但是，该系统并不能保证
    lock-free。一个不终止的高优先级的trans可能阻塞所有其它的trans。
    Performance Evaluation 部分评测了这个系统的性能。该系统的性能远高于DSTM和
    FSTM。即使在trans数目远大于处理器数目的时候，该系统的性能仍然超过FSTM。
    比较遗憾的是，该系统并不能保证lock－freedom。

    下面，简要说明一下系统的实现：
    存储布局：
    1. 存储空间分为Public Memory(所有trans可以访问，只包含Object和气handle)；
        Private Memory(每一个trans独立拥有，只有自己能访问，用于存储Bookkeep
        信息，包括writeDesc和readDesc)；Semi-private Memory(每一个trans独立拥有
        ，用于记录transDesc，其中包含一些调度信息，writeDesc指针，readDesc指针
        等，只有在发现冲突的时候才使用)。所有的私有数据都在线程栈上分配。
        writeDesc中包含object的最近版本号，object的指针，以及一份数据的工作拷贝
        readDesc中包含object的最近版本号，object的指针。
    2. Object和它的handle是连续存储的。handle可能包含当前object的版本号（奇数）
        也可能包含当前拥有该Object的trans的writeDesc指针，将该指针的若干低位屏蔽
        掉就得到了transDesc的指针。
    3. 写操作的伪代码(trans t写object o)
%{
get_write_pointer(t,o){
    h = o->handle;
    if(is_locked(h) && handle_owner(h) == t){
        return &(((writedesc*)h)->data);
    }else{
        writedesc = new write_descriptor;
        v = wait_for_object(o,writedesc);
        writedesc->last_version = v;
        writedesc->object_pointer = o;
        writedesc->data = o->data;
        return &(writedesc->data);
    }
}
wait_for_object(o,writedesc){
    while (true) {
        h = o->handle;
        if(is_unlocked(h)){
            if(writedesc != NULL)
                compare_and_swap(&(o->handle),h,writedesc);
            wakeup_any_in_wakeup_list();
            return h;
        }else{
            s = get_handle_owner(h);
            switch(ask_contention_manager_what_to_do(this,s)){
                case KILL_THEM:
                     send_abort_signal(s);
                     wait_for_ack_signal(s);
                     add_to_wakeup_list(s);
                     break;
                case WAIT_UNTIL_FINISHED:
                     wait_until_finished();
                     break;
                case WAIT_A_LITTLE:
                     sleep_briefly();
                     break;
            }
        }
    }
}
when_receive_abort_signal(sender,receiver){
    abort(receiver);
    send_ack_signal(sender);
    wait_for_wakeup_signal();
    restart_from_the_beginning(receiver);
}
}%
    t需要锁住o并生成一个o的数据的工作拷贝。先检查o的handle，看o是否被锁。如果o
    已经被自己锁住，那么返回自己私有空间中的工作拷贝。否则，t必须锁住o，并生成
    新的工作拷贝。这个模式是所谓的eager acquire
    如果o目前没有被锁，那么t用cas锁住它(将handle写为指向writeDesc的指针)，并初始
    化writeDesc。如果o当前被别的trans s锁住，t询问CM如何处理，CM可能告诉t abort
    对方，等待对方结束或等待一段时间后重试。如果t受到第一个情况，它向s发送信号
    abort。当收到了回应信号，t再次尝试获得o的锁。

    4. 读的伪代码
%{
get_read_pointer(t,o){
    h = o->handle;
    if(handle_owner(h) == t){
        return &(((writedesc*)(h->handle))->data);
    }else{
        readdesc = new read_descriptor;
        v = wait_for_object(o,NULL);
        readdesc->version_seen = v;
        readdesc->object_pointer = o;
        return &o->data;
    }
}
}%

    5. 提交和aborte的伪代码
%{
 commit(t){
    for each read descriptor r{
        if(r->object_pointer->handle != r->version_seen){
            abort(t);
            restart_from_the_beginning(t);
        }
    }
    block_abort_signal();
    for each write descriptor w{
        w->object_pointer->data = w->data;
        w->object_pointer->handle = next_version(w->last_version);
    }
    free_all_read_and_write_descriptors(t);
    unblock_abort_signal();
}
abort(t){
    for each write descriptor w{
        w->object_pointer->handle = w->last_version;
    }
    free_all_read_and_write_descriptors(t);
}
}%