多线程专题之线程死锁原因之谜

引子：线程死锁曾是多少程序员的噩梦，每每为此食不甘味，夜不成寐，一句话：苦不堪言。本文从几个场景入手，试图解开产生死锁的原因之谜。

教科书：说的很具体，理解很抽象

　　关于死锁产生的原因《操作系统》中有比较好的说明：

　　（1）因为系统资源不足。

　　（2）进程运行推进的顺序不合适。

　　（3）资源分配不当等。

　　关于死锁出现的必要条件也有比较具体的说明：

　　（1）互斥条件：一个资源每次只能被一个进程使用。

　　（2）请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

　　（3）不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。

　　（4）循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

　　这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，这也为我们实际应用中定位死锁问题，提供了路由。

情景一、不加锁，两线程访问，变量访问示例

　　关于死锁，有锁才能死，如果我们不加锁，自然不会发生死锁，但是如果不加锁，对资源的访问，将会发生什么情况呢。不妨看下面的例子：

　　当两个线程读写相同变量时，线程A读取变量然后给予变量赋予一个新的值，但是写操作需要两个存储器周期。当线程B在这两个存储器周期中间读取这个相同变量时，它就会得到不一致的值。这就是为什么要对多线程资源访问进行加锁，加锁以后的访问顺序就变成了顺序访问，从而可以避免资源的不一致访问。

情景二、不加锁，多线程访问，增量操作示例

　　当两个或多个线程试图在同一时间修改同一个变量时，如果不加锁也会出现数据资源不一致的情况。如下图所示：

　　我们可以看到，增量操作分为三个步骤进行：（1）从内存单元读入寄存器。（2）从寄存器中进行变量值的增加。（3）把新的值写回内存单元。如果两个线程试图同时对统一变量执行增量操作时，结果可能出现不一致。变量可能比原来增加了1，也可能增加了2，具体是1，还是2取决于第二个线程读取变量时获得的值是5还是6。这里面有一个前提就是变量增加的操作不是原子操作，这是因为现代计算机系统中，存储器访问需要多个总线周期，多处理器的总线周期通常在多个处理器上是交叉的，所以无法保证数据时顺序一致的。

情景三、互斥锁，多变量部分锁

　　以上示例已经讲明了我们为何需要线程锁，不加锁将会导致数据资源访问的不一致。可是加锁后，如果存在满足死锁的必要条件，又会产生死锁，我们该怎么办呢？不妨先来看一个示例：

#include <stdlib.h>
#include <pthread.h>

#define NHASH 29
#define HASH(fp) (((unsigned long)fp)%NHASH)

struct foo *fh[NHASH];

pthread_mutex_t hashlock = PTHREAD_MUTEX_INITIALIZER;

struct foo {
    int             f_count;
    pthread_mutex_t f_lock;
    struct foo     *f_next; /* protected by hashlock */
    int             f_id;
    /* ... more stuff here ... */
};

struct foo *
foo_alloc(void) /* allocate the object */
{
    struct foo    *fp;
    int            idx;

    if ((fp = malloc(sizeof(struct foo))) != NULL) {
        fp->f_count = 1;
        if (pthread_mutex_init(&fp->f_lock, NULL) != 0) {
            free(fp);
            return(NULL);
        }
        idx = HASH(fp);
        pthread_mutex_lock(&hashlock);
        fp->f_next = fh[idx];
        fh[idx] = fp->f_next;
        pthread_mutex_lock(&fp->f_lock);
        pthread_mutex_unlock(&hashlock);
        /* ... continue initialization ... */
        pthread_mutex_unlock(&fp->f_lock);
    }
    return(fp);
}
//增加
void
foo_hold(struct foo *fp) /* add a reference to the object */
{
    pthread_mutex_lock(&fp->f_lock);
    fp->f_count++;
    pthread_mutex_unlock(&fp->f_lock);
}
//查找已经对象
struct foo *
foo_find(int id) /* find an existing object */
{
    struct foo    *fp;
    int            idx;

    idx = HASH(fp);
    pthread_mutex_lock(&hashlock);
    for (fp = fh[idx]; fp != NULL; fp = fp->f_next) {
        if (fp->f_id == id) {
            foo_hold(fp);
            break;
        }
    }
    pthread_mutex_unlock(&hashlock);
    return(fp);
}
//减小
void
foo_rele(struct foo *fp) /* release a reference to the object */
{
    struct foo    *tfp;
    int            idx;

    pthread_mutex_lock(&fp->f_lock);
    if (fp->f_count == 1) { /* last reference */
        pthread_mutex_unlock(&fp->f_lock);　　//如果不解锁会怎么样呢？
        pthread_mutex_lock(&hashlock);　　　　//如果顺序发生变化呢？
        pthread_mutex_lock(&fp->f_lock);
        /* need to recheck the condition */
        if (fp->f_count != 1) {
            fp->f_count--;
            pthread_mutex_unlock(&fp->f_lock);
            pthread_mutex_unlock(&hashlock);
            return;
        }
        /* remove from list */
        idx = HASH(fp);
        tfp = fh[idx];
        if (tfp == fp) {
            fh[idx] = fp->f_next;
        } else {
            while (tfp->f_next != fp)
                tfp = tfp->f_next;
            tfp->f_next = fp->f_next;
        }
        pthread_mutex_unlock(&hashlock);
        pthread_mutex_unlock(&fp->f_lock);
        pthread_mutex_destroy(&fp->f_lock);
        free(fp);
    } else {
        fp->f_count--;
        pthread_mutex_unlock(&fp->f_lock);
    }
}