目录1.代码演示死锁2.死锁的定义3.形象理解死锁4.产生死锁的四个必要条件解释头尾相接的循环等待资源注意是必要条件!5.解决死锁的方法破坏互斥条件破坏请求与保持条件破坏不剥夺条件破坏循环等待条件避免死锁的方法6.避免死锁算法死锁检测算法银行家算法4.结论5.补充: 线程不能自己等自己,否则死锁man手册说明glibc-2.43源码说明1.代码演示死锁以OS74.【Linux】线程互斥(2) 加锁、解锁、“原子的“含义文章的代码为例子,稍作修改:在get_tickets中调用两次pthread_mutex_lock(lock)函数#include pthread.h #include unistd.h #include stdio.h #include string #include iostream #define NUM 5 int tickets1000;//全局变量 class thread_data { public: thread_data(std::string* thread_name,pthread_mutex_t* lock) :_thread_name(thread_name) ,_lock(lock) {} std::string* _thread_name; pthread_mutex_t* _lock; }; void* get_tickets(void* args) { thread_data* tmpstatic_castthread_data*(args); pthread_mutex_t* locktmp-_lock; std::string* thread_nametmp-_thread_name; for (;;) { pthread_mutex_lock(lock); pthread_mutex_lock(lock); if (tickets0) { usleep(1000); tickets--; std::cout*thread_name : 完成抢票剩余tickets张票std::endl; } else { pthread_mutex_unlock(lock); break; } pthread_mutex_unlock(lock); usleep(10); } //模拟抢票需要花时间 return nullptr; } int main() { pthread_t tid_arr[NUM]; pthread_mutex_t lock; pthread_mutex_init(lock,nullptr); for (int i0;iNUM;i) { std::string* thread_namenew std::string(threadstd::to_string(i)); thread_data* argsnew thread_data(thread_name,lock); pthread_create(tid_arr[i],nullptr,get_tickets,args); } for (int i0;iNUM;i) { pthread_join(tid_arr[i],nullptr); } pthread_mutex_destroy(lock); return 0; }运行结果: 卡住了原因: 只有一把锁,但是申请两次,那么所有线程都卡住了2.死锁的定义例如两个线程都持有锁,但它们都想申请对方的锁 → 我等你,你等我,那么两个线程都处于永久等待的状态,即死锁当然一个进程只有一个线程也能出现死锁,比如只有一个锁,但是该线程申请多次锁,导致死锁死锁(deadlock)是指在一组进程中的各个线程均占有不会释放的资源,但因互相申请被其他进程所站用不会释放的资源而处于的一种永久等待状态3.形象理解死锁根据死锁的定义,可以这样形象理解死锁:面试官什么是死锁面试者你给我 offer 我就告诉你面试官你说了我就给你 offer周而复始4.产生死锁的四个必要条件这四个必要条件在各个大厂的面试题都考过:2026字节后端(感谢快来一起摸鱼牛友分享面试题!)2026字节测试开发实习一面(感谢不上岸不改名58牛友分享面试题!)必要条件的含义: 只要产生死锁,一定能推出以下四个条件1.互斥条件(前提): 一个资源每次只能被一个执行流使用2.请求与保持条件(原则): 一个执行流因请求资源而阻塞时,对已获得的资源保持不放3.不剥夺条件(原则): 一个执行流已获得的资源,在未使用完之前,不能被强行剥夺4.循环等待条件(★★★): 若干执行流之间形成一种头尾相接的循环等待资源的关系解释头尾相接的循环等待资源A等待B的资源,B等待C的资源,C等待D的资源,......,N等待A的资源,也就形成了环路(头尾相接)注意是必要条件!产生死锁 → 存在环路但是产生死锁存在环路Bilibili三面面经:可以出现有环但是无死锁的情况当每种资源类型只有一个实例时死锁一定发生如果资源类型有多个实例系统也可能通过资源的动态分配来避免死锁参考资料: https://zhuanlan.zhihu.com/p/712769314我进一步解释:有环有死锁:两个环,都是死锁有环无死锁:虽然有环(R1和R2形成循环等待关系),但是R1可以通过申请P2来避免循环等待死锁不是环导致的,而是形成环路在环路上等待(申请失败就会等待)的问题(两个条件必须同时满足,这个要强调!)导致的,很显然图中R1除了申请P3资源,还能申请另一个P2资源,这样就有效的规避了环路等待的这个条件结论: 有环不一定有死锁,死锁不是环导致的,而是形成环路在环路上等待的问题导致的5.解决死锁的方法产生死锁 → 四个条件同时满足的逆否命题是四个条件不同时满足 → 不产生死锁,也就是说:破坏一个条件就一定不可能有死锁破坏互斥条件代码要重写,难度大,一般不可能破坏请求与保持条件一个执行流因请求资源而阻塞时,释放已获得的资源破坏不剥夺条件抢别人的锁,换句话说,就是释放对方的锁破坏循环等待条件举例,原来有锁1,锁2,现在线程1先申请锁1再申请锁2,线程2先申请锁2再申请锁1,如下图的交叉申请:交叉申请容易导致死锁,让两个线程按顺序申请:线程1和线程2同时申请同一把锁,如下图:得出避免死锁的其中一种方法: 加锁顺序一致避免死锁的方法破坏死锁的四个必要条件加锁顺序一致避免锁未释放的场景资源一次性分配6.避免死锁算法死锁检测算法根据循环等待条件,死锁检测可以利用图算法,检测有向图是否有环银行家算法银行家算法Bankers Algorithm4.结论如果将对临界资源的访问加上锁,则这个函数是线程安全的,但如果这个函数被重入,若锁还未释放则会产生死锁5.补充: 线程不能自己等自己,否则死锁之前在OS72.【Linux】__thread、分离线程中讲过线程不能自己等待自己,否则发生死锁,本文来解释#include pthread.h #include sys/types.h #include unistd.h #include iostream #include cstring void *thread_routine(void*) { return nullptr; } int main() { pthread_t tid; pthread_create(tid, nullptr,thread_routine, nullptr); sleep(1); int ret; if (retpthread_join(pthread_self(),nullptr)) { std::cout主线程等待失败: strerror(ret)std::endl; } return 0; }运行结果: 死锁解释: 线程正在运行,未退出,但线程使用pthread_join等待自己退出,会死锁,类似鸡生蛋、蛋生鸡的问题man手册说明手册里面提到了线程自己等待自己会死锁man pthread_joinor thread specifies the calling thread.这里the calling thread的calling为主动形式,翻译为调用线程,线程指定调用线程,就是线程指定自己glibc-2.43源码说明pthread_join在glibc-2.43中等同于___pthread_join,定义在/nptl/pthread_join.c中int ___pthread_join (pthread_t threadid, void **thread_return) { return __pthread_clockjoin_ex (threadid, thread_return, 0 /* Ignored */, NULL, true); } versioned_symbol (libc, ___pthread_join, pthread_join, GLIBC_2_34);__pthread_clockjoin_ex函数定义在/nptl/pthread_join_common.c中,做了线程等待自己的判断:int __pthread_clockjoin_ex (pthread_t threadid, void **thread_return, clockid_t clockid, const struct __timespec64 *abstime, bool cancel) { if (cancel) __pthread_testcancel (); struct pthread *pd (struct pthread *) threadid; /* Make sure the clock and time specified are valid. */ if (abstime __glibc_unlikely (!futex_abstimed_supported_clockid (clockid) || ! valid_nanoseconds (abstime-tv_nsec))) return EINVAL; LIBC_PROBE (pthread_join, 1, threadid); int result 0; unsigned int state; while ((state atomic_load_acquire (pd-joinstate)) ! THREAD_STATE_EXITED) { struct pthread *self THREAD_SELF; if (pd self !cancel_enabled_and_canceled (self-cancelhandling)) return EDEADLK; /* POSIX states calling pthread_join on a non joinable thread is undefined. However, if PD is still in the cache we can warn the caller. */ if (state THREAD_STATE_DETACHED) return EINVAL; /* pthread_join is a cancellation entrypoint and we use the same rationale for pthread_timedjoin_np. The kernel notifies a process which uses CLONE_CHILD_CLEARTID via a memory zeroing and futex wake-up when the process terminates. The futex operation is not private. */ int ret cancel ? __futex_abstimed_wait_cancelable64 (pd-joinstate, state, clockid, abstime, LLL_SHARED) : __futex_abstimed_wait64 (pd-joinstate, state, clockid, abstime, LLL_SHARED); if (ret ETIMEDOUT || ret EOVERFLOW) { result ret; break; } } void *pd_result pd-result; if (__glibc_likely (result 0)) { if (thread_return ! NULL) *thread_return pd_result; /* Free the TCB. */ __nptl_free_tcb (pd); } LIBC_PROBE (pthread_join_ret, 3, threadid, result, pd_result); return result; }注意while循环中的EDEADLK:if (pd self !cancel_enabled_and_canceled (self-cancelhandling)) return EDEADLK;结论: pthread_join(pthread_self(),ptr),线程自己等待自己,自己又不退出,pthread_join会主动判断这个情况,直接错误返回,否则会导致死锁
OS75.【Linux】线程互斥(4) 死锁
目录1.代码演示死锁2.死锁的定义3.形象理解死锁4.产生死锁的四个必要条件解释头尾相接的循环等待资源注意是必要条件!5.解决死锁的方法破坏互斥条件破坏请求与保持条件破坏不剥夺条件破坏循环等待条件避免死锁的方法6.避免死锁算法死锁检测算法银行家算法4.结论5.补充: 线程不能自己等自己,否则死锁man手册说明glibc-2.43源码说明1.代码演示死锁以OS74.【Linux】线程互斥(2) 加锁、解锁、“原子的“含义文章的代码为例子,稍作修改:在get_tickets中调用两次pthread_mutex_lock(lock)函数#include pthread.h #include unistd.h #include stdio.h #include string #include iostream #define NUM 5 int tickets1000;//全局变量 class thread_data { public: thread_data(std::string* thread_name,pthread_mutex_t* lock) :_thread_name(thread_name) ,_lock(lock) {} std::string* _thread_name; pthread_mutex_t* _lock; }; void* get_tickets(void* args) { thread_data* tmpstatic_castthread_data*(args); pthread_mutex_t* locktmp-_lock; std::string* thread_nametmp-_thread_name; for (;;) { pthread_mutex_lock(lock); pthread_mutex_lock(lock); if (tickets0) { usleep(1000); tickets--; std::cout*thread_name : 完成抢票剩余tickets张票std::endl; } else { pthread_mutex_unlock(lock); break; } pthread_mutex_unlock(lock); usleep(10); } //模拟抢票需要花时间 return nullptr; } int main() { pthread_t tid_arr[NUM]; pthread_mutex_t lock; pthread_mutex_init(lock,nullptr); for (int i0;iNUM;i) { std::string* thread_namenew std::string(threadstd::to_string(i)); thread_data* argsnew thread_data(thread_name,lock); pthread_create(tid_arr[i],nullptr,get_tickets,args); } for (int i0;iNUM;i) { pthread_join(tid_arr[i],nullptr); } pthread_mutex_destroy(lock); return 0; }运行结果: 卡住了原因: 只有一把锁,但是申请两次,那么所有线程都卡住了2.死锁的定义例如两个线程都持有锁,但它们都想申请对方的锁 → 我等你,你等我,那么两个线程都处于永久等待的状态,即死锁当然一个进程只有一个线程也能出现死锁,比如只有一个锁,但是该线程申请多次锁,导致死锁死锁(deadlock)是指在一组进程中的各个线程均占有不会释放的资源,但因互相申请被其他进程所站用不会释放的资源而处于的一种永久等待状态3.形象理解死锁根据死锁的定义,可以这样形象理解死锁:面试官什么是死锁面试者你给我 offer 我就告诉你面试官你说了我就给你 offer周而复始4.产生死锁的四个必要条件这四个必要条件在各个大厂的面试题都考过:2026字节后端(感谢快来一起摸鱼牛友分享面试题!)2026字节测试开发实习一面(感谢不上岸不改名58牛友分享面试题!)必要条件的含义: 只要产生死锁,一定能推出以下四个条件1.互斥条件(前提): 一个资源每次只能被一个执行流使用2.请求与保持条件(原则): 一个执行流因请求资源而阻塞时,对已获得的资源保持不放3.不剥夺条件(原则): 一个执行流已获得的资源,在未使用完之前,不能被强行剥夺4.循环等待条件(★★★): 若干执行流之间形成一种头尾相接的循环等待资源的关系解释头尾相接的循环等待资源A等待B的资源,B等待C的资源,C等待D的资源,......,N等待A的资源,也就形成了环路(头尾相接)注意是必要条件!产生死锁 → 存在环路但是产生死锁存在环路Bilibili三面面经:可以出现有环但是无死锁的情况当每种资源类型只有一个实例时死锁一定发生如果资源类型有多个实例系统也可能通过资源的动态分配来避免死锁参考资料: https://zhuanlan.zhihu.com/p/712769314我进一步解释:有环有死锁:两个环,都是死锁有环无死锁:虽然有环(R1和R2形成循环等待关系),但是R1可以通过申请P2来避免循环等待死锁不是环导致的,而是形成环路在环路上等待(申请失败就会等待)的问题(两个条件必须同时满足,这个要强调!)导致的,很显然图中R1除了申请P3资源,还能申请另一个P2资源,这样就有效的规避了环路等待的这个条件结论: 有环不一定有死锁,死锁不是环导致的,而是形成环路在环路上等待的问题导致的5.解决死锁的方法产生死锁 → 四个条件同时满足的逆否命题是四个条件不同时满足 → 不产生死锁,也就是说:破坏一个条件就一定不可能有死锁破坏互斥条件代码要重写,难度大,一般不可能破坏请求与保持条件一个执行流因请求资源而阻塞时,释放已获得的资源破坏不剥夺条件抢别人的锁,换句话说,就是释放对方的锁破坏循环等待条件举例,原来有锁1,锁2,现在线程1先申请锁1再申请锁2,线程2先申请锁2再申请锁1,如下图的交叉申请:交叉申请容易导致死锁,让两个线程按顺序申请:线程1和线程2同时申请同一把锁,如下图:得出避免死锁的其中一种方法: 加锁顺序一致避免死锁的方法破坏死锁的四个必要条件加锁顺序一致避免锁未释放的场景资源一次性分配6.避免死锁算法死锁检测算法根据循环等待条件,死锁检测可以利用图算法,检测有向图是否有环银行家算法银行家算法Bankers Algorithm4.结论如果将对临界资源的访问加上锁,则这个函数是线程安全的,但如果这个函数被重入,若锁还未释放则会产生死锁5.补充: 线程不能自己等自己,否则死锁之前在OS72.【Linux】__thread、分离线程中讲过线程不能自己等待自己,否则发生死锁,本文来解释#include pthread.h #include sys/types.h #include unistd.h #include iostream #include cstring void *thread_routine(void*) { return nullptr; } int main() { pthread_t tid; pthread_create(tid, nullptr,thread_routine, nullptr); sleep(1); int ret; if (retpthread_join(pthread_self(),nullptr)) { std::cout主线程等待失败: strerror(ret)std::endl; } return 0; }运行结果: 死锁解释: 线程正在运行,未退出,但线程使用pthread_join等待自己退出,会死锁,类似鸡生蛋、蛋生鸡的问题man手册说明手册里面提到了线程自己等待自己会死锁man pthread_joinor thread specifies the calling thread.这里the calling thread的calling为主动形式,翻译为调用线程,线程指定调用线程,就是线程指定自己glibc-2.43源码说明pthread_join在glibc-2.43中等同于___pthread_join,定义在/nptl/pthread_join.c中int ___pthread_join (pthread_t threadid, void **thread_return) { return __pthread_clockjoin_ex (threadid, thread_return, 0 /* Ignored */, NULL, true); } versioned_symbol (libc, ___pthread_join, pthread_join, GLIBC_2_34);__pthread_clockjoin_ex函数定义在/nptl/pthread_join_common.c中,做了线程等待自己的判断:int __pthread_clockjoin_ex (pthread_t threadid, void **thread_return, clockid_t clockid, const struct __timespec64 *abstime, bool cancel) { if (cancel) __pthread_testcancel (); struct pthread *pd (struct pthread *) threadid; /* Make sure the clock and time specified are valid. */ if (abstime __glibc_unlikely (!futex_abstimed_supported_clockid (clockid) || ! valid_nanoseconds (abstime-tv_nsec))) return EINVAL; LIBC_PROBE (pthread_join, 1, threadid); int result 0; unsigned int state; while ((state atomic_load_acquire (pd-joinstate)) ! THREAD_STATE_EXITED) { struct pthread *self THREAD_SELF; if (pd self !cancel_enabled_and_canceled (self-cancelhandling)) return EDEADLK; /* POSIX states calling pthread_join on a non joinable thread is undefined. However, if PD is still in the cache we can warn the caller. */ if (state THREAD_STATE_DETACHED) return EINVAL; /* pthread_join is a cancellation entrypoint and we use the same rationale for pthread_timedjoin_np. The kernel notifies a process which uses CLONE_CHILD_CLEARTID via a memory zeroing and futex wake-up when the process terminates. The futex operation is not private. */ int ret cancel ? __futex_abstimed_wait_cancelable64 (pd-joinstate, state, clockid, abstime, LLL_SHARED) : __futex_abstimed_wait64 (pd-joinstate, state, clockid, abstime, LLL_SHARED); if (ret ETIMEDOUT || ret EOVERFLOW) { result ret; break; } } void *pd_result pd-result; if (__glibc_likely (result 0)) { if (thread_return ! NULL) *thread_return pd_result; /* Free the TCB. */ __nptl_free_tcb (pd); } LIBC_PROBE (pthread_join_ret, 3, threadid, result, pd_result); return result; }注意while循环中的EDEADLK:if (pd self !cancel_enabled_and_canceled (self-cancelhandling)) return EDEADLK;结论: pthread_join(pthread_self(),ptr),线程自己等待自己,自己又不退出,pthread_join会主动判断这个情况,直接错误返回,否则会导致死锁
