死锁通常是因为获取锁时形成了环路。 死锁发生前 尽量不要使用共享 例如使用消息通讯,例如Erlang里的变量不变 尽量使用并发组件 例如java.util.concurrent 尽量使用非递归锁(不可重入锁) 例如pthread_mutex_t默认非递归 控制顺序 thread 1: Lock(a), Lock(b) thread 2: Lock(b), Lock(a) 转变为统一的顺序如Lock(a), Lock(b) 运行期警告 把Lock(历史)形成一个graph,看是否存在回路 超时机制 如带有timeout的wait, innodb_lock_wait_timeout等 工具测试 例如Intel inspector, Valgrind-Helgrind(pthread)等 PS. 银行家算法 由Edsger Dijkstra爷爷为设计THE操作系统创建,其使用场景也有些局限性,比如需要知道进程请求资源的可能数量,以及假设进程数量是固定的等,因此基本不具有实用性。 死锁发生后 堆栈查看 pstack(其实就是gdb thread apply all bt) jstack, jconsole ps. CPU100%也可以通过这种方法 检测机制 例如innodb的wait-for graph,形成环路(或者层次太深时也会认为死锁)时,此时会选择Undo量小的事务进行回滚。
Category: 系统
定时器(timer)与时间轮(timewheel)
1 定时器(timer) 1.1 定时器使用场景 通常,定时是系统一个比较常用的事件。定时器要解决的问题是,隔一定时间(short-one)或者每隔一段时间(repeated)触发一个定时事件。 无论是系统还是应用,都会用到定时功能,例如, 系统层面: 屏幕刷新,TCP等 应用层面: 网络库实现的定时功能比如libuv 1.2 应用层定时器 应用层的定时通常有几种方式: 可以在某个循环(比如Windows GetMessage, DispatchMessage后面)判断时间,通常循环里可能会sleep一下,或者有类似poll,wait之类的超时设置; 借助操作系统提供的timer函数(POSIX timer函数或者windows timer消息),或者系统提供的定时任务如crond; 利用poll相关函数,借助timerfd等(linux); 数据结构方面,可以使用链表或者堆。 1.3 系统层定时器 系统定时器有低分辨率定时器,也有高分辨率定时器。 低分辨率定时器一般为毫秒级,典型分辨率为4毫秒。通常采用timer wheel实现。 高分辨率定时器可以达到纳秒级。通常采用红黑树实现。 底层使用时钟硬件(如HPET)提供的时钟中断来提供tick。 2 时间轮(timewheel) timewheel思想十分简单。想象我们的时钟,分辨率为秒,能实现从1秒到43200(12*60*60)秒的定时。然而定时轮并不需要12*60*60大小的数组,只需要用到12+60+60=132个大小的数组。 3 参考 《Professional Linux Kernel Architechure》