实时系统(RTOS)上用过mimalloc,看了一些mimalloc代码,还调试过一些相关的bug,说点感受:
mimalloc用原子操作而不是锁来做关键数据的保护,原子操作的开销比锁要小很多,所以性能会好很多。在X86上,一个原子操作最糟糕的情况也就是100个cycle左右(SMP),优化的足够好的话30个cycle就可以搞定,而如果使用操作系统自带的锁操作,涉及到函数调用以后开销至少是几百上千cycle。所以精心设计的原子操作性能会比用锁实现的库要快很多倍。
但原子操作也有一个很大的问题:死锁,尤其是在RTOS上,非RT的系统里,不同优先级的任务都可能会得到调度,但RTOS里,调度器会优先调度高优先级的任务,而原子操作本身不具备检测优先级翻转的机制,一旦某个低优先级任务持有了原子操作的某些数值(可以理解为锁),那么高优先级任务可能会被阻塞,并有可能死锁。
性能和实时性在某些场景中是会有冲突的,为了实时性有时候需要牺牲一部分性能。比如mimalloc这个库,如果要考虑到RTOS中的死锁问题,那么就可能需要增加一些延迟、把原子操作改成锁,通过牺牲性能来换取RTOS中的实时性调度。
有人可能不理解为什么在RTOS里会死锁,我还是拿代码来描述一下(顺便说一句,这个问题,正好就是我前一段debug时候遇到的),版本是1.6.7:
任务A正在free内存,调用栈:
mi_free -> mi_free_generic -> _mi_free_block -> _mi_free_block_mt
在函数_mi_free_block_mt中会有一个原子操作:
tfreex = mi_tf_set_delayed(tfree,MI_DELAYED_FREEING);
代码链接:https://github.com/microsoft/mimalloc/blob/master/src/alloc.c#L367
do { use_delayed = (mi_tf_delayed(tfree) == MI_USE_DELAYED_FREE); if (mi_unlikely(use_delayed)) { // unlikely: this only happens on the first concurrent free in a page that is in the full list tfreex = mi_tf_set_delayed(tfree,MI_DELAYED_FREEING); } else { // usual: directly add to page thread_free list mi_block_set_next(page, block, mi_tf_block(tfree)); tfreex = mi_tf_set_block(tfree,block); } } while (!mi_atomic_cas_weak_release(&page->xthread_free, &tfree, tfreex));
此时如果一个高优先级任务B触发并调度,在RTOS中,高优先级任务持续运行的情况下,低优先级任务A是不会被调度的。
B的调用栈:
_mi_heap_malloc_zero -> _mi_malloc_generic -> mi_heap_delayed_free -> _mi_free_delayed_block -> _mi_page_use_delayed_free
注意_mi_page_use_delayed_free这里有一个do while的循环,这个循环的核心操作就是等待tfree不等于MI_DELAYED_FREEING,非RTOS里,这么做没问题。
代码链接:https://github.com/microsoft/mimalloc/blob/master/src/page.c#L128
void _mi_page_use_delayed_free(mi_page_t* page, mi_delayed_t delay, bool override_never) { mi_thread_free_t tfreex; mi_delayed_t old_delay; mi_thread_free_t tfree; do { tfree = mi_atomic_load_acquire(&page->xthread_free); // note: must acquire as we can break/repeat this loop and not do a CAS; tfreex = mi_tf_set_delayed(tfree, delay); old_delay = mi_tf_delayed(tfree); if (mi_unlikely(old_delay == MI_DELAYED_FREEING)) { mi_atomic_yield(); // delay until outstanding MI_DELAYED_FREEING are done. // tfree = mi_tf_set_delayed(tfree, MI_NO_DELAYED_FREE); // will cause CAS to busy fail } else if (delay == old_delay) { break; // avoid atomic operation if already equal } else if (!override_never && old_delay == MI_NEVER_DELAYED_FREE) { break; // leave never-delayed flag set } } while ((old_delay == MI_DELAYED_FREEING) || !mi_atomic_cas_weak_release(&page->xthread_free, &tfree, tfreex)); }
问题出在RTOS上,在RTOS里,任务B会一直卡在_mi_page_use_delayed_free函数的while循环里,而任务A又因为得不到调度,没办法把_mi_free_block_mt跑完,这就意味着tfree的值一直无法改变。
然后就死锁了,实际上CPU此时一直在任务B里忙着跑while循环,然而无济于事。非RTOS里,即使任务B比任务A优先级高,任务A仍然有一定机会可以跑,但到了RTOS里,任务A没有任何机会。
所以回到我前面的结论,mimalloc的有些代码没有考虑RTOS的使用场景。
注:核心问题是RTOS里delay并不一定能真的触发低优先级调度,很多时候只会造成reschedule,当然,也可以用类似sleep的方法,但这样有可能会造成恶劣的性能影响。
原子操作很快,比锁快,但无法检测优先级翻转。
有人会说操作系统的锁的实现就是用原子操作,这种说法是对的,锁的操作是要使用原子操作,但并不代表锁的操作只用到了原子操作。一个典型的操作系统级别的锁,在SMP的环境里,首先要判断当前的状态(是否在中断上下文),然后发起一个多核的锁的广播,这里会有多个CAS的原子操作,因为多个核心上可能有多个任务同时发起锁的请求。通过精心设计的CAS可以让某个核最终获得所有的核心(具体去看RTOS代码吧),这样所有核心的状态一致了,再用一个原子操作去调整锁的状态,同时检查其他核心上的任务优先级,以及锁本身的优先级等待,把任务重新排队,一切就绪以后,才释放多核的锁。
而对于普通的原子操作,硬件上只有一条CAS指令。
锁要比原子操作复杂的多,但也能监测并解决更多的问题(比如优先级翻转等)。