組件如何放入自己的項(xiàng)目里？把代碼末兩個(gè)Debug部分刪除，在你的項(xiàng)目里添加下面兩句代碼即可使用死鎖檢測(cè)組件。

init_hook();
start_check();

1. 死鎖的現(xiàn)象以及原理

1.1 復(fù)現(xiàn)最簡(jiǎn)單的死鎖

線程A占有鎖1，線程B占有鎖2；此時(shí)線程A想要獲取鎖2，但是鎖2已經(jīng)被線程B占有， 此時(shí)線程A會(huì)休眠等待線程B釋放鎖2后，再去獲得鎖2。可以看到下面的場(chǎng)景，線程B想要獲取鎖1，結(jié)果線程B也休眠去了。這就導(dǎo)致死鎖，鎖1和鎖2永遠(yuǎn)得不到釋放，因?yàn)榫€程A和線程B都在等待另一個(gè)鎖的釋放。這種僵持的狀態(tài)，就稱為死鎖。

正如下面代碼所示，這樣就引發(fā)了死鎖

void *thread_rountine_1(void *args) {
pthread_t selfid = pthread_self();
printf("thread_routine 1 : %ld n", selfid);
pthread_mutex_lock(&mutex_1);
sleep(1);
pthread_mutex_lock(&mutex_2);
pthread_mutex_unlock(&mutex_2);
pthread_mutex_unlock(&mutex_1);
return (void *) (0);
}
void *thread_rountine_2(void *args) {
pthread_t selfid = pthread_self(); //
printf("thread_routine 2 : %ld n", selfid);
pthread_mutex_lock(&mutex_2);
sleep(1);
pthread_mutex_lock(&mutex_1);
pthread_mutex_unlock(&mutex_1);
pthread_mutex_unlock(&mutex_2);
return (void *) (0);
}

1.2 從死鎖中找出檢測(cè)死鎖的規(guī)律

我們來看看下面這張圖，線程A想要獲取線程B的資源，線程B想要獲取線程C的資源，線程C想要獲取線程D的資源，線程D想要獲取線程A的資源，這其實(shí)就構(gòu)成了一個(gè)有向圖的環(huán)路

來看看前面介紹的最簡(jiǎn)單的死鎖，發(fā)現(xiàn)其本直也是構(gòu)成了一個(gè)有向圖的環(huán)路

來看看非死鎖的場(chǎng)景，只要線程D釋放了mutex4，那么線程C就能獲得鎖，隨后線程C釋放mutex3和4，那么線程B…可以發(fā)現(xiàn)，這個(gè)非死鎖的場(chǎng)景，它是一個(gè)有向圖,但這個(gè)圖沒有構(gòu)成環(huán)路。

過上面三個(gè)場(chǎng)景的分析，我們其實(shí)就可以把死鎖的問題，轉(zhuǎn)換為 有向圖的環(huán)路檢測(cè)。在線程進(jìn)行加鎖前，我們?nèi)ヅ袛嘁幌滤械木€程有沒有構(gòu)成環(huán)路，如果有，則說明現(xiàn)在很有可能會(huì)進(jìn)入死鎖。

2. 檢測(cè)死鎖的前置條件

2.1 有向圖的邊怎么來？

我們現(xiàn)在已經(jīng)知道了死鎖的問題，就轉(zhuǎn)換為 有向圖的環(huán)路檢測(cè)。那么這個(gè)有向圖怎么構(gòu)建？在我們對(duì)mutex1加鎖的時(shí)候，我們?cè)趺粗朗蔷€程A占有mutex1，在對(duì)mutex2加鎖的時(shí)候，怎么知道它已經(jīng)被線程B占有了？我們無(wú)法知道鎖是屬于哪個(gè)線程的。既然連鎖都不知道屬于哪個(gè)線程，哪有如何構(gòu)建出有向圖呢？換言之，我們需要解決：知道當(dāng)前鎖被哪個(gè)線程占用。我們不知道的原因很簡(jiǎn)單，就是mutex和pthread_id沒有一個(gè)對(duì)應(yīng)關(guān)系。

//鎖與線程的信息
struct pair_t {
    unsigned long int th_id;
    enum Type type;

    unsigned long int lock_id;
    int degress;
};

我們可以做出一個(gè)數(shù)據(jù)結(jié)構(gòu)，在加鎖之前，判斷這個(gè)鎖有沒有被別的線程使用，如果沒有，在加鎖之后我們將這個(gè)鎖與本線程綁定，做一個(gè)pair，然后把這個(gè)pair存起來。比如說線程線程A和mutex1綁定，線程B和mutex2綁定了。當(dāng)線程A再次去嘗試對(duì)mutex2加鎖之前，先判斷mutex2是否名花有主？如果有，那有向圖的邊不就來了嗎？不知道讀者有沒有注意到，這一段話都建立在加鎖之前判斷 鎖 是否名花有主。

有一個(gè)非常簡(jiǎn)單粗暴的方法，在加鎖之前調(diào)用一個(gè)函數(shù)，加鎖之后調(diào)用一個(gè)函數(shù)。讀者可以想一下，本文是要實(shí)現(xiàn)一個(gè)組件，所謂組件，給別人也能用，難道在一個(gè)項(xiàng)目里面，想要檢測(cè)一下死鎖，去把lock上下全部加兩個(gè)函數(shù)？這顯然不符合我們組件的設(shè)想，我們希望不改變別人的代碼，就能實(shí)現(xiàn)檢測(cè)。

lock_before(self_id, (unsigned long int) mutex);
pthread_mutex_lock(&mutex);
lock_after(self_id, (unsigned long int) mutex);

要想實(shí)現(xiàn)上面的需求，我們可以使用hook。

2.2 hook—>dlsym

hook是什么意思？鉤子，簡(jiǎn)單來說，我們使用hook，可以把系統(tǒng)或第三方庫(kù)提供的函數(shù)，替換成我們寫的同名函數(shù)，而第三方庫(kù)的函數(shù)則被我們改名，在我們寫的同名函數(shù)里，可以去調(diào)用第三方庫(kù)原來的函數(shù)。

正如下面代碼所示，系統(tǒng)提供的pthread_mutex_lock被改名為pthread_mutex_lock_f。那么我們就可以使用pthread_mutex_lock來當(dāng)作函數(shù)名稱，如此一來，在別的項(xiàng)目里面，我們通過hook就可以進(jìn)行死鎖檢測(cè)，而不需要去改代碼了。

hook提供了兩個(gè)接口；1. dlsym()是針對(duì)系統(tǒng)的，系統(tǒng)原始的api。2. dlopen()是針對(duì)第三方的庫(kù)。

/* ******* ******************Hook****************** ******* */

typedef int (*pthread_mutex_lock_t)(pthread_mutex_t *mutex);

pthread_mutex_lock_t pthread_mutex_lock_f;

typedef int (*pthread_mutex_unlock_t)(pthread_mutex_t *mutex);

pthread_mutex_unlock_t pthread_mutex_unlock_f;

static int init_hook() {
    pthread_mutex_lock_f = dlsym(RTLD_NEXT, "pthread_mutex_lock");
    pthread_mutex_unlock_f = dlsym(RTLD_NEXT, "pthread_mutex_unlock");
}


int pthread_mutex_lock(pthread_mutex_t *mutex) {
    pthread_t self_id = pthread_self(); //
    lock_before(self_id, (unsigned long int) mutex);
    pthread_mutex_lock_f(mutex);
    lock_after(self_id, (unsigned long int) mutex);
}

在進(jìn)程的虛擬內(nèi)存空間里面，有一塊代碼段 ，上面代碼中，pthread_mutex_lock_f是一個(gè)函數(shù)指針，實(shí)際上，就是把pthread_mutex_lock_f指向代碼段里系統(tǒng)函數(shù)的入口地址 ，以此來實(shí)現(xiàn)偷天換日。

還需要注意一點(diǎn)，這個(gè)#define _GNU_SOURCE要寫在前面，因?yàn)檫@個(gè)就相當(dāng)于一個(gè)開關(guān)，在下面的.h文件里面，有#ifdef _GNU_SOURCE的地方。在gcc編譯的時(shí)候后面加上 -ldl。

#define _GNU_SOURCE
#include < dlfcn.h >

3. 有向圖

3.1 有向圖的數(shù)據(jù)結(jié)構(gòu)

下面來看一下結(jié)構(gòu)體的含義

ertex_list的每一項(xiàng)，都是一個(gè)頂點(diǎn)，后面鏈表里面存的，都是邊的另一個(gè)點(diǎn)。

vlock_list的每一項(xiàng)，存的都是鎖與線程的信息

/* ******* ******************Digraph****************** ******* */

enum Type {
    PROCESS, RESOURCE
};
//鎖與線程的信息
struct pair_t {
    unsigned long int th_id;
    enum Type type;

    unsigned long int lock_id;
    int degress;
};
//頂點(diǎn)
struct vertex_t {
    struct pair_t pair;
    struct vertex_t *next;
};

struct task_graph {
    struct vertex_t vertex_list[MAX];
    int vertex_num;

    struct pair_t lock_list[MAX];
    int lock_num;

    pthread_mutex_t mutex;

    int path[MAX + 1];
    int visited[MAX];
    int k;
    int deadlock;
};

struct task_graph *tg = NULL;


//創(chuàng)建一個(gè)vertex
struct vertex_t *create_vertex(struct pair_t pair) {
    struct vertex_t *tex = (struct vertex_t *) malloc(sizeof(struct vertex_t));

    tex- >pair = pair;
    tex- >next = NULL;
    return tex;
}

//查找vertex在list里面的下標(biāo)
int search_vertex(struct pair_t pair) {
    int i = 0;

    for (i = 0; i < tg- >vertex_num; i++) {
        if (tg- >vertex_list[i].pair.type == pair.type && tg- >vertex_list[i].pair.th_id == pair.th_id) {
            return i;
        }
    }

    return -1;
}

//把vertex添加到vertex_list里面
void add_vertex(struct pair_t pair) {
    if (search_vertex(pair) == -1) {
        tg- >vertex_list[tg- >vertex_num].pair = pair;
        tg- >vertex_list[tg- >vertex_num].next = NULL;
        tg- >vertex_num++;
    }
}

//添加邊,把v添加到u的鏈表里
int add_edge(struct pair_t u, struct pair_t v) {
    add_vertex(u);
    add_vertex(v);

    struct vertex_t *cnt = &(tg- >vertex_list[search_vertex(u)]);

    while (cnt- >next != NULL) {
        cnt = cnt- >next;
    }

    cnt- >next = create_vertex(v);
}

//檢查邊是否存在
int verify_edge(struct pair_t u, struct pair_t v) {
    if (tg- >vertex_num == 0) return 0;

    int idx = search_vertex(u);
    if (idx == -1) {
        return 0;
    }

    struct vertex_t *cnt = &(tg- >vertex_list[idx]);

    while (cnt != NULL) {
        if (cnt- >pair.th_id == v.th_id) {
            return 1;
        }
        cnt = cnt- >next;
    }
    return 0;
}

//刪除邊
int remove_edge(struct pair_t u, struct pair_t v) {

    int idx_u = search_vertex(u);
    int idx_v = search_vertex(v);

    if (idx_u != -1 && idx_v != -1) {

        struct vertex_t *cnt = &tg- >vertex_list[idx_u];
        struct vertex_t *remove;

        while (cnt- >next != NULL) {
            if (cnt- >next- >pair.th_id == v.th_id) {
                remove = cnt- >next;
                cnt- >next = cnt- >next- >next;
                free(remove);
                break;
            }
            cnt = cnt- >next;
        }
    }
}

3.2 dfs判斷環(huán)的方法

現(xiàn)在邊也處理好了，鎖與線程的關(guān)系也處理好了，那么我們?nèi)绾稳ヅ袛嘤袥]有環(huán)呢？我們使用DFS來判斷。

/* ******* ******************check cycle****************** ******* */

//打印
void print_deadlock(void) {
    int i = 0;
    printf("deadlock : ");
    for (i = 0; i < tg- >k - 1; i++) {
        printf("%ld -- > ", tg- >vertex_list[tg- >path[i]].pair.th_id);
    }
    printf("%ldn", tg- >vertex_list[tg- >path[i]].pair.th_id);
}

void print_locklist(void) {
    int i = 0;

    printf("-----------print_locklist----------n");
    for (i = 0; i < tg- >lock_num; i++) {
        printf("threadid : %ld, lockid: %ldn", tg- >lock_list[i].th_id, tg- >lock_list[i].lock_id);
    }
    printf("-----------------------------------n");
}

int DFS(int idx) {
    struct vertex_t *ver = &tg- >vertex_list[idx];
    if (tg- >visited[idx] == 1) {
        tg- >path[tg- >k++] = idx;
        print_deadlock();
        tg- >deadlock = 1;
        return 0;
    }

    tg- >visited[idx] = 1;
    tg- >path[tg- >k++] = idx;

    while (ver- >next != NULL) {
        DFS(search_vertex(ver- >next- >pair));
        tg- >k--;
        ver = ver- >next;
    }

    return 1;
}

//判斷某個(gè)頂點(diǎn)是否成環(huán)
int search_for_cycle(int idx) {
    struct vertex_t *ver = &tg- >vertex_list[idx];
    tg- >visited[idx] = 1;
    tg- >k = 0;
    tg- >path[tg- >k++] = idx;

    while (ver- >next != NULL) {
        int i = 0;
        for (i = 0; i < tg- >vertex_num; i++) {
            if (i == idx) continue;
            tg- >visited[i] = 0;
        }

        for (i = 1; i <= MAX; i++) {
            tg- >path[i] = -1;
        }
        tg- >k = 1;

        DFS(search_vertex(ver- >next- >pair));
        ver = ver- >next;
    }
}

//檢查是否死鎖
void check_dead_lock(void) {
    printf("-----------check deadlock----------n");

    int i;
    tg- >deadlock = 0;
    for (i = 0; i < tg- >vertex_num; i++) {
        if (tg- >deadlock == 1) {
            break;
        }
        //從每個(gè)點(diǎn)都出發(fā)一遍
        search_for_cycle(i);
    }
    if (tg- >deadlock == 0) {
        printf("no deadlockn");
    }

    printf("----------------------------------n");
}

3.3 簡(jiǎn)單測(cè)試一下

可以看到我們的結(jié)果與預(yù)期一致，說明我們的有向圖與判斷環(huán)完成了，那么下面我們就應(yīng)該去寫上鎖前后的函數(shù)了。

/* ******* ******************Debug 2****************** ******* */


int main() {
    tg = (struct task_graph *) malloc(sizeof(struct task_graph));
    tg- >vertex_num = 0;

    struct pair_t v1;
    v1.th_id = 1;
    v1.type = PROCESS;
    add_vertex(v1);

    struct pair_t v2;
    v2.th_id = 2;
    v2.type = PROCESS;
    add_vertex(v2);

    struct pair_t v3;
    v3.th_id = 3;
    v3.type = PROCESS;
    add_vertex(v3);

    struct pair_t v4;
    v4.th_id = 4;
    v4.type = PROCESS;
    add_vertex(v4);


    struct pair_t v5;
    v5.th_id = 5;
    v5.type = PROCESS;
    add_vertex(v5);


    add_edge(v1, v2);
    add_edge(v2, v3);
    add_edge(v3, v4);
    add_edge(v4, v5);
    add_edge(v3, v1);
    add_edge(v5, v1);

    check_dead_lock();
//    search_for_cycle(search_vertex(v1));
}

root@wxf:/tmp/tmp.d4vz2dOyJP# gcc -o deadlock_success deadlock_success.c -lpthread -ldl
root@wxf:/tmp/tmp.d4vz2dOyJP# ./deadlock_success 
-----------check deadlock----------
deadlock : 1 -- > 2 -- > 3 -- > 4 -- > 5 -- > 1
deadlock : 1 -- > 2 -- > 3 -- > 1
----------------------------------
root@wxf:/tmp/tmp.d4vz2dOyJP#

4. 三個(gè)原語(yǔ)操作

現(xiàn)在有向圖和hook都有了，那么我們?nèi)绾伟阉梨i檢測(cè)出來？換言之，我們?cè)趺词褂胮thread_mutex_lock和pthread_mutex_unlock構(gòu)建有向圖？

在調(diào)用系統(tǒng)提供的lock以前，我們需要檢測(cè)這個(gè)鎖有沒有被別的線程占用，如果被占用，那么我們就需要往圖里面加一條邊。

如果沒有被占用，那么我們就往里面走。也就是說加鎖完，調(diào)用系統(tǒng)提供的lock之后， 我們需要告訴后面的線程，這個(gè)鎖被我占用了，即添加一項(xiàng)pair，供別人lock之前去檢測(cè)。 如果被占用了，然后鎖被釋放，本線程獲取到了這個(gè)以前被占用的鎖，那么我們lock之后，需要把原來添加的一條邊刪除掉，因?yàn)檫@個(gè)鎖已經(jīng)屬于自己了，并且將鎖對(duì)應(yīng)的pair中的th_id改成自己。

在調(diào)用系統(tǒng)提供的unlock之后，解鎖了一個(gè)鎖之后，我們?nèi)タ纯催€有沒有渴望得到這個(gè)鎖的，如果沒有，則將鎖對(duì)應(yīng)的pair置空，如果有，則不管pair。

注意：下面三個(gè)函數(shù)，我對(duì)三個(gè)函數(shù)都加鎖了，這里是我的偷懶操作，鎖的粒度較大。如果想優(yōu)化，應(yīng)該放到serch函數(shù)里面，我這里懶得去改了。

int pthread_mutex_lock(pthread_mutex_t *mutex) {
    pthread_t self_id = pthread_self(); 

    lock_before(self_id, (unsigned long int) mutex);
    pthread_mutex_lock_f(mutex);
    lock_after(self_id, (unsigned long int) mutex);
}

int pthread_mutex_unlock(pthread_mutex_t *mutex) {
    pthread_t self_id = pthread_self();

    pthread_mutex_unlock_f(mutex);
    unlock_after(self_id, (unsigned long int) mutex);
}

4.1 lock_before

我們現(xiàn)在把加鎖理解為談戀愛確認(rèn)關(guān)系。在確認(rèn)關(guān)系之前，我們要去看一下這個(gè)女生有沒有男朋友，如果她沒有男朋友，妙哉！那么我們就直接確認(rèn)關(guān)系(lock)吧！如果她有男朋友，那現(xiàn)在還不能和她談戀愛，我們先與她曖昧?xí)崦?add_edge)，等著她分手。

void lock_before(unsigned long int thread_id, unsigned long int lock) {
    pthread_mutex_lock_f(&tg- >mutex);

    int idx = search_lock(lock);
//    printf("[lock_before] self_id:%lu lock:%lu lock idx:%d n", thread_id, lock, idx);
    //如果該鎖是第一次則什么都不做
    if (idx != -1) {
        //u是想要加鎖的線程
        struct pair_t u;
        u.th_id = thread_id;
        u.type = PROCESS;
        //把vertex添加到vertex_list里面
        add_vertex(u);
        //v是鎖原來的線程
        struct pair_t v;
        v.th_id = tg- >lock_list[idx].th_id;
        tg- >lock_list[idx].degress++;
        v.type = PROCESS;
        add_vertex(v);

        if (!verify_edge(u, v)) {
            add_edge(u, v); // 把v加入到vertex_list的u的鏈表中
        }
    }

    pthread_mutex_unlock_f(&tg- >mutex);
}

4.2 lock_after

現(xiàn)在我們加鎖完了，也就是談戀愛確認(rèn)關(guān)系了之后，如果我們是她的初戀，那么我們要向全世界宣布(tg->lock_list[empty_lock_idx])：她，是我的女人！如果不是初戀，她被別人宣布過了，那我們就別搞這么浪漫了，把她給我們的備注改成男朋友就好了(tg->lock_list[idx].th_id = thread_id;)，并且我們也不需要曖昧聊天了(remove_edge)，因?yàn)樗呀?jīng)是我們女朋友了。

void lock_after(unsigned long int thread_id, unsigned long int lock) {
    pthread_mutex_lock_f(&tg- >mutex);

    int idx = search_lock(lock);
//    printf("[lock_after ] self_id:%lu lock:%lu ", thread_id, lock);

    if (idx == -1) {  // 第一次加鎖,找一個(gè)空位lock_list，設(shè)置th_id和lock
        int empty_lock_idx = search_empty_lock(lock);
        tg- >lock_list[empty_lock_idx].th_id = thread_id;
        tg- >lock_list[empty_lock_idx].lock_id = lock;
//        printf("分配lock_list位置 idx:%d n", empty_lock_idx);
        if (empty_lock_idx >= tg- >lock_num) {
            inc(&tg- >lock_num, 1);
        }
    }
    else {
        //u是想要加鎖的線程
        struct pair_t u;
        u.th_id = thread_id;
        u.type = PROCESS;
        //v是鎖原來的線程
        struct pair_t v;
        v.th_id = tg- >lock_list[idx].th_id;
        tg- >lock_list[idx].degress--;
        v.type = PROCESS;
        //刪除邊
        if (verify_edge(u, v)) {
            remove_edge(u, v);
        }
        //設(shè)為本線程
        tg- >lock_list[idx].th_id = thread_id;

//        printf("獲得 lock idx:%d n", idx);
    }

    pthread_mutex_unlock_f(&tg- >mutex);
}

4.3 unlock_after

unlock就相當(dāng)于分手，如果她沒有備胎，那么她就恢復(fù)單身(pair置空)，如果她有備胎，那就隨她吧~

void unlock_after(unsigned long int thread_id, unsigned long int lock) {
    pthread_mutex_lock_f(&tg- >mutex);

    int idx = search_lock(lock);
    //如果入度為0，說明沒有別的線程指向該鎖，則把這個(gè)idx位置置空
    if (tg- >lock_list[idx].degress == 0) {
        tg- >lock_list[idx].th_id = 0;
        tg- >lock_list[idx].lock_id = 0;
    }

    pthread_mutex_unlock_f(&tg- >mutex);
}

5. 死鎖檢測(cè)線程的測(cè)試

下面我們來測(cè)試這個(gè)場(chǎng)景。完整代碼在目錄前言中。

/* ******* ******************Debug 1****************** ******* */
pthread_mutex_t mutex_1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_3 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_4 = PTHREAD_MUTEX_INITIALIZER;

void *thread_rountine_1(void *args) {
    pthread_t selfid = pthread_self(); //

    printf("thread_routine 1 : %ld n", selfid);

    pthread_mutex_lock(&mutex_1);
    sleep(1);
    pthread_mutex_lock(&mutex_2);

    pthread_mutex_unlock(&mutex_2);
    pthread_mutex_unlock(&mutex_1);

    return (void *) (0);
}

void *thread_rountine_2(void *args) {
    pthread_t selfid = pthread_self(); //

    printf("thread_routine 2 : %ld n", selfid);

    pthread_mutex_lock(&mutex_2);
    sleep(1);
    pthread_mutex_lock(&mutex_3);

    pthread_mutex_unlock(&mutex_3);
    pthread_mutex_unlock(&mutex_2);

    return (void *) (0);
}

void *thread_rountine_3(void *args) {
    pthread_t selfid = pthread_self(); //

    printf("thread_routine 3 : %ld n", selfid);

    pthread_mutex_lock(&mutex_3);
    sleep(1);
    pthread_mutex_lock(&mutex_4);

    pthread_mutex_unlock(&mutex_4);
    pthread_mutex_unlock(&mutex_3);

    return (void *) (0);
}

void *thread_rountine_4(void *args) {
    pthread_t selfid = pthread_self(); //

    printf("thread_routine 4 : %ld n", selfid);

    pthread_mutex_lock(&mutex_4);
    sleep(1);
    pthread_mutex_lock(&mutex_1);

    pthread_mutex_unlock(&mutex_1);
    pthread_mutex_unlock(&mutex_4);

    return (void *) (0);
}


int main() {
    init_hook();
    start_check();

    printf("start_checkn");

    pthread_t tid1, tid2, tid3, tid4;
    pthread_create(&tid1, NULL, thread_rountine_1, NULL);
    pthread_create(&tid2, NULL, thread_rountine_2, NULL);
    pthread_create(&tid3, NULL, thread_rountine_3, NULL);
    pthread_create(&tid4, NULL, thread_rountine_4, NULL);

    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
    pthread_join(tid3, NULL);
    pthread_join(tid4, NULL);

    return 0;
}