优先级反转那些事儿

,最近在线上遇到了一些​​[HMDConfigManager remoteConfigWithAppID:]​​卡死,观察了下主线程堆栈，用到的锁是读写锁：,,随后又去翻了下持有着锁的子线程，有各种各样的情况，且基本都处于正常的执行状态，例如有的处于打开文件状态，有的处于​​read​​状态，有的正在执行​​NSUserDefaults​​的方法···,,,通过观察发现，出问题的线程都有​​QOS:BACKGROUND​​标记。整体看起来持有锁的子线程仍然在执行，只是留给主线程的时间不够了。为什么这些子线程在持有锁的情况下，需要执行这么久，直到主线程的 8s 卡死？一种情况就是真的如此耗时，另一种则是出现了优先级反转。,这个案例里，持有读写锁且优先级低的线程迟迟得不到调度（又或者得到调度的时候又被抢占了，或者得到调度的时候时间已然不够了）而具有高优先级的线程由于拿不到读写锁，一直被阻塞，所以互相死锁。​​iOS8​​之后引入了​​QualityOfService​​的概念，类似于线程的优先级，设置不同的​​QualityOfService​​的值后系统会分配不同的​​CPU​​时间、网络资源和硬盘资源等，因此我们可以通过这个设置队列的优先级。,在 Threading Programming Guide 文档中，苹果给出了提示：,苹果的建议是不要随意修改线程的优先级，尤其是这些高低优先级线程之间存在临界资源竞争的情况。所以删除相关优先级设置代码即可解决问题。,在 pthread_rwlock_rdlock(3pthread) 发现了如下提示：,尽管针对的是实时系统，但是还是有一些启示和帮助。按照提示，对有问题的代码进行了修改：在线程通过 ​​pthread_rwlock_wrlock​​ 拿到 ​​_rwlock​​ 的时候，临时提升其优先级，在释放 ​​_rwlock​​ 之后，恢复其原先的优先级。,为了验证上述的手动调整线程优先级是否有一定的效果，这里通过​​demo​​进行本地实验：定义了​​2000​​个​​operation​​（目的是为了​​CPU​​繁忙），优先级设置​​NSQualityOfServiceUserInitiated​​，且对其中可以被​​100​​整除的​​operation​​的优先级调整为​​NSQualityOfServiceBackground​​，在每个​​operation​​执行相同的耗时任务，然后对这被选中的​​10​​个​​operation​​进行耗时统计。,统计信息如下表所示：,,可以看到：,通过​​Demo​​可以发现，通过手动调整其优先级，低优先级任务的整体耗时得到大幅度的降低，这样在持有锁的情况下，可以减少对主线程的阻塞时间。​,,该问题的验证过程分为​​2​​个阶段：,所以相对来说，线上的提升相对有限。,那么是否所有锁都需要像上文一样，手动提升持有锁的线程优先级？系统是否会自动调整线程的优先级？如果有这样的机制，是否可以覆盖所有的锁？要理解这些问题，需要深刻认识优先级反转。,优先级反转，是指某同步资源被较低优先级的进程/线程所拥有，较高优先级的进程/线程竞争该同步资源未获得该资源，而使得较高优先级进程/线程反而推迟被调度执行的现象。根据阻塞类型的不同，优先级反转又被分为​​Bounded priority inversion​​和​​Unbounded priority inversion​​。,这里借助 Introduction to RTOS - Solution to Part 11 的图进行示意。,如图所示，高优先级任务（​​Task H​​）被持有锁的低优先级任务（​​Task L​​)阻塞，由于阻塞的时间取决于低优先级任务在临界区的时间（持有锁的时间），所以被称为​​bounded priority inversion​​。只要​​Task L​​一直持有锁，​​Task H​​就会一直被阻塞，低优先级的任务运行在高优先级任务的前面，优先级被反转。,,在​​Task L​​持有锁的情况下，如果有一个中间优先级的任务（​​Task M​​）打断了​​Task L​​，前面的​​bounded​​就会变为​​unbounded​​，因为​​Task M​​只要抢占了​​Task L​​的​​CPU​​，就可能会阻塞​​Task H​​任意多的时间（​​Task M​​可能不止​​1​​个）。,,目前解决​​Unbounded priority inversion​​有​​2​​种方法：一种被称作优先权极限（​​priority ceiling protocol​​），另一种被称作优先级继承（​​priority inheritance​​）。,在优先权极限方案中，系统把每一个临界资源与 1 个极限优先权相关联。当1个任务进入临界区时，系统便把这个极限优先权传递给这个任务，使得这个任务的优先权最高；当这个任务退出临界区后，系统立即把它的优先权恢复正常，从而保证系统不会出现优先权反转的情况。该极限优先权的值是由所有需要该临界资源的任务的最大优先级来决定的。,如图所示，锁的极限优先权是 3。当​​Task L​​持有锁的时候，它的优先级将会被提升到3，和​​Task H​​一样的优先级。这样就可以阻止​​Task M​​(优先级是2）的运行，直到​​Task L​​和​​Task H​​不再需要该锁。,,在优先级继承方案中，大致原理是：高优先级任务在尝试获取锁的时候，如果该锁正好被低优先级任务持有，此时会临时把高优先级线程的优先级转移给拥有锁的低优先级线程，使低优先级线程能更快的执行并释放同步资源，释放同步资源后再恢复其原来的优先级。,,可以通过以下几种发生来避免或者转移​​Bounded priority inversion​​：,iOS 系统主要使用以下两种机制来在不同线程（或 ​​queue​​）间传递 ​​QoS​​：,系统的 QoS 传递规则比较复杂，主要参考以下信息：,调度程序会根据这些信息决定 ​​block​​ 以什么优先级运行。,如果当前线程因等待某线程（线程 1）上正在进行的操作（如 ​​block1​​）而受阻，而系统知道 ​​block1​​ 所在的目标线程（​​owner​​），系统会通过提高相关线程的优先级来解决优先级反转的问题。反之如果系统不知道 ​​block1​​ 所在目标线程，则无法知道应该提高谁的优先级，也就无法解决反转问题；,记录了持有者信息（​​owner​​）的系统 API 如下：,使用以上这些 ​​API​​ 能够在发生优先级反转时使系统启用优先级反转避免机制。,接下来对前文提到的各种「基础系统​​API​​」进行验证,​​pthread mutex​​的数据结构​​pthread_mutex_s​​其中有一个​​m_tid​​字段，专门来记录持有该锁的线程​​Id​​。,代码来验证一下：线程优先级是否会被提升？,先在子线程上锁并休眠，然后主线程请求该锁。,可以看到，低优先级子线程先持有锁，当时的优先级为​​4​​，而该锁被主线程请求的时候，子线程的优先级被提升为​​47​​,​​os_unfair_lock​​用来替换​​OSSpinLock​​，解决优先级反转问题。等待​​os_unfair_lock​​锁的线程会处于休眠状态，从用户态切换到内核态，而并非忙等。​​os_unfair_lock​​将线程​​ID​​保存到了锁的内部，锁的等待者会把自己的优先级让出来，从而避免优先级反转。验证一下：,结果和​​pthread mutex​​一致。,在 pthread_rwlock_init 有如下提示：,大意是内核不感知读写锁，无法提升低优先级线程的优先级，从而无法避免优先级反转。通过查询定义发现：​​pthread_rwlock_s​​包含了字段​​rw_tid​​，专门来记录持有写锁的线程，这不由令人好奇：为什么​​pthread_rwlock_s​​有​​owner​​信息却仍然无法避免优先级反转？,https://news.ycombinator.com/item?id=21751269 链接中提到：,大意是：​​XNU​​使用 ​​​turnstiles​​​ 内核机制进行优先级继承，这种机制被应用在 ​​pthread mutex​​ 和 ​​os_unfair_lock​​ 上。,顺藤摸瓜，在​​ksyn_wait​​方法中找到了​​_kwq_use_turnstile​​的调用，其中的注释对读写锁解释的比较委婉，添加了 ​​at least sometimes​​,再去查看​​_kwq_use_turnstile​​的定义，代码还是很诚实的，只有在​​KSYN_WQTYPE_MTX​​才会启用​​turnstile​​进行优先级反转保护，而读写锁的类型为​​KSYN_WQTYPE_RWLOCK​​，这说明读写锁不会使用​​_kwq_use_turnstile​​，所以无法避免优先级反转。,另外在​​_pthread_find_owner​​也可以看到，读写锁的​​owner​​是​​0​​,把锁更换为读写锁，验证一下前面的理论是否正确：,可以看到读写锁不会发生优先级提升。,这个​​API​​都比较熟悉了，这里直接验证：,​​_queue​​是一个低优先级队列（​​QOS_CLASS_BACKGROUND​​），可以看到​​dispatch_sync​​调用压入队列的任务，以及在这之前​​dispatch_async​​压入的任务，都被提升到较高的优先级​​47​​（和主线程一致），而最后一个​​dispatch_async​​的任务则以优先级​​4​​来执行。,​​_queue​​是一个低优先级队列（​​QOS_CLASS_BACKGROUND​​），当在当前主线程使用​​dispatch_wait​​进行等待时，输出如下，低优先级的任务被提升到优先级​​47​​,而如果将​​dispatch_wait(block, DISPATCH_TIME_FOREVER)​​注释掉之后，输出如下：,之前对​​dispatch_semaphore​​的认知非常浅薄，经常把二值信号量和互斥锁划等号。但是通过调研后发现：​​dispatch_semaphore​​ 没有 ​​QoS​​ 的概念，没有记录当前持有信号量的线程（​​owner​​），所以有高优先级的线程在等待锁时，内核无法知道该提高哪个线程的调试优先级（​​QoS​​）。如果锁持有者优先级比其他线程低，高优先级的等待线程将一直等待。Mutexvs Semaphore: What’s the Difference? 一文详细比对了​​Mutex​​和​​Semaphore​​之间的区别。,这些是一些警示，可以看到​​dispatch_semaphore​​十分危险，使用需要特别小心。,这里通过苹果官方提供的demo进行解释：,值得一提的是，​​Clang​​专门针对这种情况进行了静态检测：https://github.com/llvm-mirror/clang/blob/master/lib/StaticAnalyzer/Checkers/GCDAntipatternChecker.cpp,如果想使用该功能，只需要打开​​xcode​​设置即可：,​​dispatch_semaphore​​给笔者的印象非常深刻，之前写过一段这样的代码：使用信号量在主线程同步等待相机授权结果。,上线后长期占据卡死​​top1​​，当时百思不得其解，在深入了解到信号量无法避免优先级反转后，终于豁然开朗，一扫之前心中的阴霾。,,这类问题一般通过​​2​​种方式来解决：,前文提到​​XNU​​使用​​turnstile​​进行优先级继承，这里对​​turnstile​​机制进行简单的描述和理解。在​​XNU​​内核中，存在着大量的同步对象（例如​​lck_mtx_t​​），为了解决优先级反转的问题，每个同步对象都必须对应一个分离的数据结构来维护大量的信息，例如阻塞在这个同步对象上的线程队列。可以想象一下，如果每个同步对象都要分配一个这样的数据结构，将造成极大的内存浪费。,为了解决这个问题，​​XNU​​采用了​​turnstile​​机制，一种空间利用率很高的解决方案。该方案的提出依据是同一个线程在同一时刻不能同时阻塞于多个同步对象上。这一事实允许所有同步对象只需要保留一个指向​​turnstile​​的指针，且在需要的时候去分配一个​​turnstile​​即可，而​​turnstile​​则包含了操作一个同步对象需要的所有信息，例如阻塞线程的队列、拥有这个同步对象的线程指针。​​turnstile​​是从池中动态分配的，这个池的大小会随着系统中已分配的线程数目增加而增加，所以​​turnstile​​总数将始终低于或等于线程数，这也决定了​​turnstile​​的数目是可控的。​​turnstile​​由阻塞在该同步对象上的第一个线程负责分配，当没有更多线程阻塞在该同步对象上，​​turnstile​​会被释放，回收到池中。,​​turnstile​​的数据结构如下：,在验证环节有一些优先级数值，这里借助「Mac OS® X and iOS Internals」解释一下：实验中涉及到的优先级数值都是相对于​​Mach​​层而言的，且都是用户线程数值。,,本文主要阐述了优先级反转的一些概念和解决思路，并结合​​iOS​​平台的几种锁进行了详细的调研。通过深入的理解，可以去规避一些不必要的优先级反转，从而进一步避免卡死异常。字节跳动 ​​APM​​团队也针对线程的优先级做了监控处理，进而达到发现和预防优先级反转的目的。