7 Locking

1．很多因锁产生的问题大都在设计层面就可以解决，而且在大多数场合工作良好，比如

（a）使用锁层级避免死锁。

（b）使用死锁检测工具，比如Linux内核lockdep模块[Cor06]。

（c）使用对锁友好的数据结构，比如数组、哈希表、基树，第10章将会讲述这些数据结构。

2．有些锁的问题只在竞争程度很高时才会出现，一般只有不良的设计才会让锁竞争如此激烈。

3．有些锁的问题可以通过其他同步机制配合锁来避免。包括统计计数（第5章）、引用计数（9.1节）、危险指针（9.1.2节）、顺序锁（9.2节）、RCU（9.3节），以及简单的非阻塞数据结构（14.3节）。

4．直到不久之前，几乎所有的共享内存并行程序都是闭源的，所以多数研究者很难知道业界的实践解决方案。

7.1 Staying Alive

7.1.1 Deadlock

从锁指向线程的箭头表示线程持有了该锁，比如，线程B持有锁2和锁4。从线程到锁的箭头表示线程在等待这把锁，比如，线程B等待锁3释放。

在图7.3中，死锁循环是线程B、锁3、线程C、锁4，然后又回到线程B。

从死锁中恢复的办法：

• 杀掉其中一个线程
• 从某个线程中偷走一把锁

下面介绍避免死锁的策略:

7.1.1.1 Locking Hierarchies

按层次使用锁时要为锁编号，严禁不按顺序获取锁。

线程B违反这个层次，因为它在持有锁4时又试图获取锁3，因此导致死锁的发生。

7.1.1.2 Local Locking Hierarchies

小问题：锁的层次本质要求全局性，因此很难应用在库函数上。如果调用了某个库函数的应用程序还没有开始实现，那么倒霉的库函数程序员又怎么才能遵从这个还不存在的应用程序里的锁层次呢？

一种特殊的情况，幸运的是这也是普遍情况，是库函数并不涉及任何调用者的代码。这时，如果库函数持有任何库函数的锁，它绝不会再去获取调用者的锁，这样就避免出现库函数和调用者之间互相持锁的死锁循环。

小问题7.3：这个规则有例外吗？比如即使库函数永远不会调用调用者的代码，但是还是会出现库函数与调用者代码相互持锁的死锁循环。

答案：确实有！这里有几个例子。

1．如果库函数的参数之一是指向库函数将要获取的锁的指针，并且如果库函数在获取调用者的锁的同时还持有自身的锁，那么我们可能有一个涉及调用者和库函数的锁的死锁循环。

2．如果其中一个库函数返回一个指向锁的指针，调用者获取了该锁，如果调用者在持有库的锁的同时获得自身的锁，我们可以再次有一个涉及调用者和库函数的锁的死锁循环。

3．如果其中一个库函数获取锁，然后在返回仍然持有该锁，如果调用者获取了自身的锁，我们又发明了一种产生死锁循环的好办法。

4．如果调用者有一个获取锁的信号处理程序，那么死锁循环就会涉及调用者和库函数的锁。不过在这种情况下，库函数的锁是死锁循环中无辜的旁观者。也就是说，在大多数环境中从信号处理程序内获取锁的想法是个馊主意，它不只是一个坏主意，它也是不受支持的用法。

不过假设某个库函数确实调用了调用者的代码。比如，qsort（）函数调用了调用者提供的比较函数。并发版本的qsort（）通常会使用锁，虽然不大可能，但是如果比较函数复杂并且也使用了锁，那么就有可能出现死锁。这时库函数该如何避免死锁？

出现这种情况时的黄金定律是“在调用未知代码前释放所有的锁”。为了遵守这条定律，qsort（）函数必须在调用比较函数前释放它持有的全部锁。
下面举例说明这条黄金定律:

如图7.4所示，其调用关系如下图所示：

foo() {
    hold lock A
    qsort(cmp_foo)
}

bar() {
    hold lock B
    qsort(cmp_bar)
}

qsort(fun *cmp) {
    hold lock C
    *cmp();
}

cmp_foo() {
    hold lock B
    // do cmp things
}

现在假设如下时序，则进入死锁状态：

thread 1                                               |  thread 2
foo                                                    |  
    hold lock A                                        |  bar
    qsort(cmp_foo)                                     |      hold lock B
        hold lock C                                    |      qsort(cmp_bar) 
        cmp_foo();                                     |          try holding lock C
            try holding lock B                         |          // can’t get lock C
            // cannot get lock B ,waiting              |          // waiting!
            // Dead lock now!                          |

图7.5在调用外部未知函数cmp_foo的时候参照黄金定律释放了Lock C，避免了死锁问题。

小问题7.4：但是如果qsort（）在调用比较函数之前释放了所有锁，它怎么保护其他qsort（）线程也可能访问的数据？

答案：通过私有化将要比较的数据元素（如第8章所述）或通过使用延迟处理机制，如引用计数（如第9章所述）。

7.1.1.3 Layered Locking Hierarchies

小问题：如果qsort（）无法在调用比较函数前释放全部的锁，怎么办？

见下面例1的解决办法。

例1

可以使用锁的分级来避免死锁问题，思考图7.4带来的问题，因为在cmp函数中使用了与bar函数相冲突的锁导致了问题，为了改变这一点，我们在cmp函数中使用新的锁D，这样我们就需要把应用层的锁A/B和D放在不同的层级，从而使他们相互隔离，没有产生冲突的机会。

如图7.6所示，在这张图上，我们把全局层次锁分成了三级，第一级是锁A和锁B，第二级是锁C，第三级是锁D。

例2：链表迭代器

这是另一个无法在调用未知代码时释放所有锁的例子。

struct locked_list {
    spinlock_t s;
    struct list_head h;
};
 
/*获取了链表的锁并且返回了第一个元素（假如链表不为空）*/
struct list_head *list_start(struct locked_list *lp)
{
    /* 获取链表的锁 */
    spin_lock(&lp->s);
    return list_next(lp, &lp->h);
}

/* 要么返回指向下一个元素的指针，要么在链表到达末端时返回NULL */
struct list_head *list_next(struct locked_list *lp,
                            struct list_head *np)
{
    struct list_head *ret;

    ret = np->next;
    if (ret == &lp->h) {
        /* 链表达到末端时释放链表的锁 */
        spin_unlock(&lp->s);
        ret = NULL;
    }
    return ret;
}

链表迭代器的一种使用场景如下：

struct list_ints {
    struct list_head n;
    int a;
};

void list_print(struct locked_list *lp)
{
    struct list_head *np;
    struct list_ints *ip;

    np = list_start(lp);
    while (np != NULL) {
        ip = list_entry(np, struct list_ints, n);
        printf("\t%d\n", ip->a);
        np = list_next(lp, np);
    }
}

只要用户代码在处理每个链表元素时，不要再去获取已经被其他调用list_start（）或者list_next（）的代码持有的锁——这会导致死锁——那么锁在用户代码里就可以继续保持隐藏。

我的小问题：自旋锁如何造成死锁？

答案见此所示，说明了自旋锁造成死锁的场景以及现代处理器以及操作系统中如何避免这种情况的出现。

我们在给链接迭代器加锁时通过为锁的层次分级，就可以避免死锁的发生。

这种分级的方法可以扩展成任意多级，但是每增加一级，锁的整体设计就复杂一分。这种复杂性的增长对于某些面向对象的设计来说极不方便，会导致一大堆对象将锁毫无纪律地传来传去。这种面向对象的设计习惯和避免死锁的需要之间的冲突，也是一些程序员们认为并行编程复杂的重要原因。

7.1.1.4 Locking Hierarchies and Pointers to Locks

一般来说设计一个包含着指向锁的指针的API意味着这个设计本身就存在问题。

将内部的锁传递给其他软件组件违反了信息隐藏的美学，而信息隐藏恰恰是一个关键的设计准则。

我的小问题：从这个角度来说，锁的层层封装是否是不合理的？

小问题7.5：请列举出一个例子，说明将指向锁的指针传给另一个函数的合理性。

例子1：Locking primitives
例子2：比如说有个函数要返回某个对象，而在对象成功返回之前必须持有调用者提供的锁。
例子3：POSIX的pthread_cond_wait（）函数，要传递一个指向pthread_mutex_t的指针来防止错过唤醒而导致的挂起。

7.1.1.5 Conditional Locking

spin_lock(&lock2);
layer_2_processing(pkt);
nextlayer = layer_1(pkt);
//报文在协议栈中从下往上发送时，这里的获取锁操作将导致死锁。
spin_lock(&nextlayer->lock1); 
layer_1_processing(pkt);
spin_unlock(&lock2);
spin_unlock(&nextlayer->lock1);

在这个例子中，当报文在协议栈中从上往下发送时，必须逆序获取下一层的锁。而报文在协议栈中从下往上发送时，是按顺序获取锁，图中第4行的获取锁操作将导致死锁。

我的小问题：这里是如何导致死锁的？

答案: 从下面的解决方案来看，是spin_lock(&nextlayer->lock1)这个操作的失败导致了死锁。

spin_lock(&nextlayer->lock1)失败的原因是nextlayer->lock1在从下往上发送时已经被layer_1持有了，所以这里会失败进入自旋等待，而此时layer_1也尝试获取layer_2的锁，所以造成了死锁。

此时获取自旋锁的正确的顺序应该是先获取layer_1的锁在获取layer_2的锁。

而在这个引发死锁的场景下，先获取了layer_2的锁之后再去获取已经被layer_1抢占了的lock1(比如说这个锁可能被layer_1的某个中断处理程序中先获取了)，导致失败。

我的小问题：通常情况下,自旋锁如何造成死锁？在内核中遇到此类的问题该如何定位？

一次spinlock死锁故障的定位
单CPU自旋锁导致死锁的问题.

在本例中避免死锁的办法是先强加一套锁的层次，但在必要时又可以有条件地乱序获取锁，如下代码所示，与上面无条件的获取层1的锁不同，第5行用spin_trylock有条件地获取锁。该原语在锁可用时立即获取锁，在锁不可用时不获取锁，返回0。如下所示：

retry:
spin_lock(&lock2);
layer_2_processing(pkt);
nextlayer = layer_1(pkt);
if (!spin_trylock(&nextlayer->lock1)) {
    spin_unlock(&lock2);
    spin_lock(&nextlayer->lock1);
    spin_lock(&lock2);
    if (layer_1(pkt) != nextlayer) {
        spin_unlock(&nextlayer->lock1);
        spin_unlock(&lock2);
        goto retry;
    }
}
layer_1_processing(pkt);
spin_unlock(&lock2);
spin_unlock(&nextlayer->lock1);

如果if (!spin_trylock(&nextlayer->lock1)获取成功，处理流程同以上的代码。

如果获取失败，第6行释放锁，第7行和第8行用正确的顺序获取锁。

系统中可能有多块网络设备（比如 Ethernet 和WiFi），这样layer_1函数必须进行路由选择。这种选择随时都可能改变，特别是系统可移动时。所以第9行必须重新检查路由选择，如果发生改变，必须释放锁重新来过。

7.1.1.6 Acquire Needed Locks First

条件锁有一个重要的特例，在执行真正的处理工作之前，已经拿到了所有必需的锁。
在这种情况下，处理不需要是幂等的（idempotent）：如果这时不能在不释放锁的情况下拿到某把锁，那么释放所有持有的锁，重新获取。只有在持有所有必需的锁以后才开始处理工作。

7.1.1.7 Single-Lock-at-a-Time Designs

如果有一个可以完美分割的问题，每个分片拥有一把锁。然后处理任何特定分片的线程只需获得对应这个分片的锁。

7.1.1.8 Signal/Interrupt Handlers

The trick is to block signals (or disable interrupts, as the case may be) when acquiring any lock that might be acquired within an interrupt handler. Furthermore, if holding such a lock, it is illegal to attempt to acquire any lock that is ever acquired outside of a signal handler without blocking signals.

其中的诀窍是在任何可能中断处理函数里获取锁的时候阻塞信号（或者屏蔽中断）。不仅如此，如果已经获取了锁，那么在不阻塞信号的情况下，尝试去获取任何可能在中断处理函数之外被持有的锁，这种操作都是非法操作。

小问题7.10：如果锁A在信号处理函数之外被持有，锁B在信号处理函数之内被持有，为什么在不阻塞信号并且持有锁B的情况下去获取锁A是非法的？

答案：因为这会导致死锁。假定锁A在信号处理函数之外被持有，并且在持有时没有阻塞该信号，那么有可能在持有锁时处理该信号。相应的信号处理函数可能再去获取锁B，从而同时持有锁A和锁B。因此，如果我们还想在持有锁B的同时获取锁A，将有一个死锁循环等着我们。

因此，在不阻塞信号的情况下，如已经持有了从信号处理函数内获取的锁，从信号处理程序外部获取另一把锁是非法的。

小问题7.11：在信号处理函数里怎样才能合法地阻塞信号？

答案：最简单和最快速的方法之一是在设置信号时将sa_mask字段传递给sigaction（）的struct sigaction。

7.1.2 Livelock and Starvation

虽然条件锁是一种有效避免死锁机制，但是有可能被滥用。

void thread1(void)
{
retry:
    spin_lock(&lock1);
    do_one_thing();
    if (!spin_trylock(&lock2)) {
        spin_unlock(&lock1);
        goto retry;
    }
    do_another_thing();
    spin_unlock(&lock2);
    spin_unlock(&lock1);
}

void thread2(void)
{
retry:
    spin_lock(&lock2);
    do_a_third_thing();
    if (!spin_trylock(&lock1)) {
        spin_unlock(&lock2);
        goto retry;
    }
    do_a_fourth_thing();
    spin_unlock(&lock1);
    spin_unlock(&lock2);
}

1．第4行线程1获取lock1，然后调用do_one_thing（）。

2．第18行线程2获取lock2，然后调用do_a_third_thing（）。

3．线程1在第6行试图获取lock2，由于线程2已经持有而失败。

4．线程2在第20行试图获取lock1，由于线程1已经持有而失败。

5．线程1在第7行释放lock1，然后跳转到第3行的retry。

6．线程2在第21行释放lock2，然后跳转到第17行的retry。

7．上述过程不断重复，活锁华丽登场。

解决办法： 活锁和饥饿都属于事务内存软件实现中的严重问题，所以现在引入了竞争管理器这样的概念来封装这些问题。以锁为例，通常简单的指数级后退就能解决活锁和饥饿。

指数级后退是指在每次重试之前增加按指数级增长的延迟，如下所示:

void thread1(void)
{
    unsigned int wait = 1;
    retry:
    spin_lock(&lock1);
    do_one_thing();
    if (!spin_trylock(&lock2)) {
        spin_unlock(&lock1);
        sleep(wait);
        wait = wait << 1;
        goto retry;
    }
    do_another_thing();
    spin_unlock(&lock2);
    spin_unlock(&lock1);
}

void thread2(void)
{
    unsigned int wait = 1;
    retry:
    spin_lock(&lock2);
    do_a_third_thing();
    if (!spin_trylock(&lock1)) {
        spin_unlock(&lock2);
        sleep(wait);
        wait = wait << 1;
        goto retry;
    }
    do_a_fourth_thing();
    spin_unlock(&lock1);
    spin_unlock(&lock2);
}

1．第4行线程1获取lock1，然后调用do_one_thing（）。

2．第18行线程2获取lock2，然后调用do_a_third_thing（）。

3．线程1在第6行试图获取lock2，由于线程2已经持有而失败。

4．线程2在第20行试图获取lock1，由于线程1已经持有而失败。

5．线程1在第7行释放lock1，睡眠wait秒，然后跳转到第3行的retry。

6．线程2在第21行释放lock2，睡眠wait秒，然后跳转到第17行的retry。

7．上述过程不断重复，睡眠的时间不甚精确，thread1就可能在thread2睡眠的情况下醒来获取到它的锁。

7.1.3 Unfairness

锁容易被同一个numa内的CPU们轮奸。

7.1.4 Inefficiency

Locks are implemented using atomic instructions and memory barriers, and often involve cache misses.

锁是由原子操作和内存屏障实现，并且常常带来高速缓存未命中。开销比较大。

不过一旦持有了锁，持有者可以不受干扰地访问被锁保护的代码。获取锁可能代价高昂，但是一旦持有，特别是对较大的临界区来说，CPU的高速缓存反而是高效的性能加速器。

小问题7.17：锁的持有者怎么样才会受到干扰？

答案：如果受锁保护的数据与锁本身处于同一高速缓存行中，那么其他CPU获取锁的尝试将导致持有锁的CPU产生昂贵的高速缓存未命中。这是伪共享的一种特殊情况，如果由不同锁保护的一对变量共享高速缓存行，也会出现这种情况。相反，如果锁和与它保护的数据处于不同的高速缓存行中，则持有锁的CPU通常只会在第一次访问给定的变量时遇到缓存未命中。

当然，将锁和数据放入单独的缓存行也有缺点，代码将产生两次高速缓存未命中，而不是在无竞争时的一次高速缓存未命中。

7.2 Types of Locks

7.2.1 Exclusive Locks

互斥锁正如其名，一次只能有一个线程持有该锁。持锁者对受锁保护的代码享有排他性的访问权。

小问题7.18：如果获取互斥锁后马上释放，也就是说，临界区是空的，这种做法有意义吗

互斥锁的语义有两个组成部分： （1）大家比较熟悉的数据保护语义 （2）消息语义，释放给定的锁将通知等待获取那个锁的线程。

空临界区的做法使用了消息传递的语义，而非数据保护语义。

7.2.2 Reader-Writer Locks

读/写锁和互斥锁允许的规则不大相同：互斥锁只允许一个持有者，读/写锁允许任意多个持有者持有读锁（但只能有一个持有写锁）。

实现方式一：

经典的读/写锁实现使用一组只能以原子操作方式修改的计数和标志。

这种实现和互斥锁一样，对于很小的临界区来说开销太大，获取和释放锁的开销比一条简单指令的开销高两个数量级。然，如果临界区足够长，获取和释放锁的开销与之相比就可以忽略不计了。如下图所示为原子操作的开销。

实现锁的开销和临界区中获得的收益需要权衡考虑。

实现方式二：

另一个设计读/写锁的方法是使用每线程的互斥锁，这种读/写锁对读者非常有利。线程在读的时候只要获取本线程的锁即可，而在写的时候需要获取所有线程的锁。在没有写者的情况下，每个读锁的开销只相当于一条原子操作和一个内存屏障的开销之和，并且不会有高速缓存未命中，这点对于锁来说非常不错。不过，写锁的开销包括高速缓存未命中，再加上原子操作和内存屏障的开销之和——再乘以线程的个数。

简单地说，读/写锁在有些场景非常有用，但各种实现方式都有各自的缺点。读/写锁的正统用法是用于非常长的只读临界区，临界区耗时几百微秒或者毫秒以上最好。

7.2.3 Beyond Reader-Writer Locks

锁可能的允许规则有很多，VAX/VMS分布式锁管理器就是其中一个例子，如表7.1所示。空白格表示兼容，包含X的格表示不兼容。

• null If a thread is not holding a lock, it should not prevent any other thread from acquiring that lock.
• concurrent-read The concurrent-read mode might be used to accumulate approximate statistics on a data structure, while permitting updates to proceed concurrently.
• concurrent write The concurrent-write mode might be used to update approximate statistics, while still permitting reads and concurrent updates to proceed concurrently.

可见concurrent-read和concurrent write常用于非精确计数场景，可见5.2中的相关内容。

• protected read The protected-read mode might be used to obtain a consistent snapshot of the data structure, while permitting reads but not updates to proceed concurrently.
• protected write The protected-write mode might be used to carry out updates to a data structure that could interfere with protected readers but which could be tolerated by concurrent readers.
• exclusive The exclusive mode is used when it is necessary to exclude all other accesses.

It is interesting to note that exclusive locks and reader-writer locks can be emulated by the VAX/VMS DLM. Exclusive locks would use only the null and exclusive modes, while reader-writer locks might use the null, protected-read, and protected-write modes.

Quick Quiz 7.19: Is there any other way for the VAX/VMS DLM to emulate a reader-writer lock?

Answer: There are in fact several. One way would be to use the null, protected-read, and exclusive modes. Another way would be to use the null, protected-read, and concurrent-write modes. A third way would be to use the null, concurrent-read, and exclusive modes.

相对于VAX/VMS分布式锁管理器的6个状态，有些数据库中使用的锁甚至可以有30个以上的状态。

7.2.4 Scoped Locking

在面向对象编程领域，可以使用凭借构造函数和析构函数去获取和释放锁。

Another approach is to use the object-oriented “resource allocation is initialization” (RAII) pattern.

好处是方便使用，坏处是让锁的很多有用的用法变得不再可能，破坏了锁的灵活性。

内核中RCU的例子：

其算法如下所示：

void force_quiescent_state(struct rcu_node *rnp_leaf)
{
    int ret;
    struct rcu_node *rnp = rnp_leaf;
    struct rcu_node *rnp_old = NULL;
    for (; rnp != NULL; rnp = rnp->parent) {
        ret = (ACCESS_ONCE(gp_flags)) ||
        !raw_spin_trylock(&rnp->fqslock);
        if (rnp_old != NULL)
        raw_spin_unlock(&rnp_old->fqslock);
        if (ret)
        return;
        rnp_old = rnp;
    }
    if (!ACCESS_ONCE(gp_flags)) {
        ACCESS_ONCE(gp_flags) = 1;
        do_force_quiescent_state();
        ACCESS_ONCE(gp_flags) = 0;
    }
    raw_spin_unlock(&rnp_old->fqslock);
}

此函数说明了层次锁的常见模式。
就像之前提到的交互器封装，这个模式很难使用RAII式加锁法实现，因此在可预见的未来我们仍然需要加锁和解锁原语。

7.3 Locking Implementation Issues

7.3.1 Sample Exclusive-Locking Implementation Based on Atomic Exchange

typedef int xchglock_t;
#define DEFINE_XCHG_LOCK(n) xchglock_t n = 0

void xchg_lock(xchglock_t *xp)
{
    while (xchg(xp, 1) == 1) {
        while (*xp == 1)
        continue;
    }
}

void xchg_unlock(xchglock_t *xp)
{
    (void)xchg(xp, 0);
}

小问题7.23：为什么需要图7.16中第7、8行的内循环呢？为什么不是简单地重复做第6行的原子交换操作？

答案：假设锁已被一个线程持有，并且有其他几个线程尝试获取该锁。在这种情况下，如果这些线程都循环地使用原子交换操作，它们会让包含锁的高速缓存行在它们之间“乒乓”，使得芯片互联模块不堪重负。相反，如果这些线程在第7、8行上的内循环中自旋，它们将只在自己的高速缓存中自旋，对互连模块几乎没有影响。

小问题7.24：为什么不简单地在图7.16第14行的加锁语句中，将变量赋值为0？

答案：这也是一个合法的实现，但只有当这个赋值操作之前有一个内存屏障并使用ACCESS_ONCE（）时才可行。若使用xchg（）操作就不需要内存屏障，因为此操作将返回一个值，这意味着它是一个完整的内存屏障。

我的小问题：x86的xchg指令是否自带内存屏障？

从以上的7.24小问题的答案来看是的。

评价：
在锁竞争不激烈时性能好，并且具有内存占用小的优点。它避免了给不能使用它的线程提供锁，但可能会导致锁分配不公平或者甚至在锁竞争激烈时出现饥饿现象。

7.3.2 Other Exclusive-Locking Implementations

ticket lock是内核中实现的一种锁，通过先入先出的处理准则，可以解决上述CAS的实现方式带来的不公平问题，但是可能将锁授予给当前无法使用它的线程，并且仍然存在竞争激烈时的性能问题——原因是释放锁的线程必须更新对应的内存地址。在高度竞争时，每个尝试获取锁的线程将拥有高速缓存行的只读副本，因此锁的持有者将需要使所有此类副本无效，然后才能更新内存地址来释放锁。通常，CPU和线程越多，在高度竞争条件下释放锁时所产生的开销就越大。

queued-lock实现方式可以大大减少了在高度锁竞争时交换锁的开销，但是也增加了其在低度竞争时的开销。

因此，Beng-Hong Lim和AnantAgarwal将简单的test-and-set锁与queued-lock相结合，在低度竞争时使test-and-set锁，在高度竞争时切换到queued-lock，因此得以在低度竞争时获得低开销，并在高度竞争时获得公平和高吞吐量。Browning等人采取了类似的方法，但避免了单独标志的使用，这样test-and-set锁的快速路径可以使用test-and-set实现所使用的代码。这种方法已经用于生产环境。

在高度锁竞争中出现的另一个问题是当锁的持有者受到延迟，特别是当延迟的原因是抢占时，这可能导致优先级反转。

解决方法是优先级继承或在持有锁时防止抢占。在防止持有锁的线程被抢占的方面，Linux中则使用了futexes机制实现这个功能。

有趣的是，在锁的实现中原子指令并不是不可或缺的部分。 以下是一些不采用原子指令实现锁的例子：

A new solution of Dijkstra’s concurrent programming problem
Solution of a Problem in Concurrent Programming Control

在Herlihy和Shavit的教科书中可以找到一种锁的漂亮实现，只使用简单的加载和存储。

The Art of Multiprocessor Programming

提到这点的目的是，虽然这个实现没有什么实际应用，但是详细的研究这个实现将非常具有娱乐性和启发性。

随着越来越多的人熟悉并行硬件并且并行化越来越多的代码，我们可以期望出现更多的专用加解锁原语。不过，你应该仔细考虑这个重要的安全提示，只要可能，尽量使用标准同步原语。标准同步原语与自己开发的原语相比，最大的优点是标准原语通常不太容易出BUG。

Gamsa等人描述了一种基于令牌的机制，其中令牌在CPU之间循环。当令牌到达给定的CPU时，它可以排他性地访问由该令牌保护的任何内容。详细的论文如下所示：

Tornado: Maximizing Locality and Concurrency in a Shared Memory Multiprocessor Operating System

7.4 Lock-Based Existence Guarantees

并行编程的一个关键挑战是提供存在保证，使得在整个访问尝试的过程中，可以在保证该对象存在的前提下访问给定对象。在某些情况下，存在保证是隐含的。

1．基本模块中的全局变量和静态局部变量在应用程序正在运行时存在。

2．加载模块中的全局变量和静态局部变量在该模块保持加载时存在。

3．只要至少其中一个函数还在被使用，模块将保持加载状态。

4．给定的函数实例的堆栈变量，在该实例返回前一直存在。

5．如果你正在某个函数中执行，或者正在被这个函数调用（直接或间接），那么这个函数一定有一个活动实例。

虽然这些隐式存在保证非常直白，但是涉及隐含存在保证的故障可是真的发生过。

小问题7.27：依赖隐式存在保证怎样才会导致故障？

答案：这里有一些因使用隐式存在保证不当而导致的错误。

1．程序将全局变量的地址写入文件，然后后续相同程序的更大实例读取该地址并尝试解引用。这可能因为每个进程的地址空间随机化而失败，更不用说程序重新编译了。

2．模块可以将其中一个变量的地址记录在位于其他模块的指针中，然后尝试在模块被卸载之后对指针解引用dereference(*)。

3．函数可以将它的一个堆栈变量的地址记录到全局指针中，其他函数可能会在该函数返回之后尝试解引用。

如果给定结构只能在持有一个给定的锁时被释放，那么持有锁就保证那个结构的存在。

一种保证锁存在的简单方式是把锁放在一个全局变量里，但全局锁具有可扩展性受限的缺点。有种可以让可扩展性随着数据结构的大小增加而改进的方法，是在每个元素中放置锁的结构。不幸的是，把锁放在一个数据元素中以保护这个数据元素本身的做法会导致微妙的竞态条件，如下所示：

int delete(int key)
{
    int b;
    struct element *p;

    b = hashfunction(key);
    p = hashtable[b];
    if (p == NULL || p->key != key)
        return 0;
    spin_lock(&p->lock);
    hashtable[b] = NULL;
    spin_unlock(&p->lock);
    kfree(p);
    return 1;
}

解决本例问题的办法是使用一个全局锁的哈希集合，使得每个哈希桶有自己的锁，如下所示：

int delete(int key)
{
    int b;
    struct element *p;
    spinlock_t *sp;

    b = hashfunction(key);
    sp = &locktable[b];
    spin_lock(sp);
    p = hashtable[b];
    if (p == NULL || p->key != key) {
        spin_unlock(sp);
        return 0;
    }
    hashtable[b] = NULL;
    spin_unlock(sp);
    kfree(p);
    return 1;
}

我的小问题：这个例子看不太懂哟~

7.5 Locking: Hero or Villain?

那些写应用程序的家伙很喜欢锁，那些编写并行库的同行不那么开心，那些并行化现有顺序库的人非常不爽。

7.5.1 Locking For Applications: Hero!

当编写整个应用程序（或整个内核）时，开发人员可以完全控制设计，包括同步设计。假设设计良好地使用分割原则，如第6章所述，锁可以是非常有效的同步机制，锁在生产环境级别的高质量并行软件中大量使用已经说明了一切。

然而，尽管通常其大部分同步设计是基于锁，这些软件也几乎总是还利用了其他一些同步机制，包括特殊计数算法（第5章）、数据所有权（第8章）、引用计数（9.1节）、顺序锁（9.2节）和RCU（9.3节）。此外，业界也使用死锁检测工具[The kernel lock validator]、获取/释放锁平衡工具[Finding kernel problems automatically]、高速缓存未命中分析[valgrind]和基于计数器的性能分析[perf，Oprofile]等等。

通过仔细设计、使用良好的同步机制和良好的工具，锁在应用程序和内核领域工作的相当不错。

7.5.2 Locking For Parallel Libraries: Just Another Tool

如例子7.1.1.2中所示，库函数调用引入的死锁问题值得关注。 会引入死锁问题的几种情况：

• 函数调用应用程序代码
• 与信号处理程序的交互，例如库函数接收的信号触发了应用程序的信号处理函数的调用。
• 父进程和子进程之间的库函数调用

可以使用以下策略来避免死锁问题。

1. Don’t use either callbacks or signals.

不要使用回调或信号。

1. Don’t acquire locks from within callbacks or signal handlers.

不要从回调或信号处理函数中获取锁。

1. Let the caller control synchronization.

让调用者控制同步。

1. Parameterize the library API to delegate locking to caller.

将库API参数化，以便让调用者处理锁。

1. Explicitly avoid callback deadlocks.

显式地避免回调死锁。

1. Explicitly avoid signal-handler deadlocks.

显式地避免信号处理程序死锁。

7.5.3 Locking For Parallelizing Sequential Libraries: Villain!

随着到处可见的低成本多核系统的出现，常见的任务往往是并行化现有的库，这些库的设计仅考虑了单线程使用的情况。从并行编程的角度看，这种对于并行性的全面忽视可能导致库函数API的严重缺陷。比如：

1. Implicit prohibition of partitioning.

隐式的禁止分割。

1. Callback functions requiring locking.

需要锁的回调函数。

1. Object-oriented spaghetti code.

面向对象的意大利面条式代码。