OSSpinLock 与优先级反转

操作系统里的线程状态

当要处理应用程序时(When an application is to be processed)，它会创建一个线程。
然后，它被分配所需的资源(比如网络)，并进入READY队列。
当线程调度器(类似进程调度器)为线程分配处理器时，它进入RUNNING队列。
处理过程中需要触发一些其他事件时，这是在它的控制之外的(比如另一个要完成的处理)，它从RUNNING队列转换到WAITING队列。
当应用程序具有延迟线程处理的能力时，它可以在需要时延迟线程并使其休眠一段特定的时间。然后线程从RUNNING队列转换到DELAYED队列。

线程延迟的一个例子是闹钟的贪睡。在它第一次响铃并且没有被用户关闭之后，它会在一段特定的时间后再次响铃。在此期间，线程进入睡眠状态。
当线程生成一个I/O请求，并且在它完成之前不能继续移动时，它从RUNNING队列转换到BLOCKED队列。
处理完成后，线程从RUNNING转换到FINISHED。

WAITING和BLOCKED转换之间的区别在于，在WAITING中，线程等待来自另一个线程的信号或等待另一个处理完成，这意味着突发时间是特定的。然而，在BLOCKED状态下，没有指定的时间(它取决于用户何时提供输入)。

The difference between the WAITING and BLOCKED transition is that in WAITING the thread waits for the signal from another thread or waits for another process to be completed, meaning the burst time is specific. While, in BLOCKED state, there is no specified time (it depends on the user when to give an input).

为了成功地执行所有处理事项，处理器需要通过Thread Control Blocks (TCB)维护关于每个线程的信息。

优先级反转

实时操作系统的一个基本要求就是基于优先级的抢占系统。保证优先级高的线程在“第一时间”抢到执行权，是实时系统的第一黄金准则。

但是这种基于优先级抢占的系统，有一个著名的问题需要关注，就是“优先级反转”（Priority Inversion），简单来说，就是有低优先级的线程占据了CPU，妨碍了高优先级线程的执行。“优先级反转”是几乎每一个实时操作系统的噩梦，系统设计上花了很多精力去关注，但依然会出错。

现代最出名的例子，就是1997美国宇航局的火星探路车（Mars Pathfinder）了。

基本情况就是火星探路车在登录火星后的一段时间里无法工作，最后查明是因为优先级反转导致探路车的计算机不断重启。总算最后NASA远程打了个补丁上去，解决了这个问题。这个耗时三年，花了2.6亿美金的项目差点就折在小小的“优先级反转”上了。

所以今天就让我们看看优先级反转是怎样发生的，以及对于QNX这样的基于消息传递的操作系统有什么影响。

什么是“优先级反转”

下面这个时序图就是一个经典的优先级反转

线程A在一个比较低的优先级上工作(Running), 假设是10吧。然后在时间点T1的时候，线程A锁定了一把互斥锁，并开始操作互斥数据。
这时有个高优线级线程C（比如优先级20）在时间点T2被唤醒(Ready)，它也也需要操作互斥数据。当它加锁互斥锁时，因为互斥锁在T1被线程A锁掉了，所以线程C放弃CPU进入阻塞状态(WAITING)，而线程A得以占据CPU，继续执行。
事情到这一步还是正确的，虽然优先级10的A线程看上去抢了优先级20的C线程的时间，但因为程序逻辑，C确实需要退出CPU等完成互斥数据操作后，才能获得CPU。
但是，假设我们有个线程B在优先级15上，在T3时间点上醒了过来(Ready)，因为他比当前执行的线程A优先级高，所以它会立即抢占CPU。而线程A被迫进入READY状态等待。
一直到时间点T4，线程B放弃CPU，这时优先级10的线程A是唯一READY线程，它再次占据CPU继续执行，最后在T5解锁了互斥锁。
在T5，线程A解锁的瞬间，线程C立即获取互斥锁，并在优先级20上等待CPU。因为它比线程A的优先级高，系统立刻调度线程C执行，而线程A再次进入READY状态。

上面这个时序里，线程B从T3到T4占据CPU运行的行为，就是事实上的优先级反转。一个优先级15的线程B，通过压制优线级10的线程A，而事实上导致高优先级线程C无法正确得到CPU。这段时间是不可控的，因为线程B可以长时间占据CPU（即使轮转时间片到时，线程A和B都处于可执行态，但是因为B的优先级高，它依然可以占据CPU），其结果就是高优先级线程C可能长时间无法得到 CPU。

上面所说的美国宇航局的火星车，就是因为有高优先级的线程被压制，从而在指定时间内无法获得CPU，导致 “看门狗”认为系统出了无法恢复的故障，直接重启了系统。重启后系统再次进入相同状态，导致不断重启，无法正常工作。

为什么忙等会导致低优先级线程拿不到时间片？

现代操作系统在管理普通线程时，通常采用时间片轮转算法(Round Robin，简称 RR)。每个线程会被分配一段时间片(quantum)，通常在 10-100 毫秒左右。当线程用完属于自己的时间片以后，就会被操作系统挂起，放入等待队列中，直到下一次被分配时间片。

优先级反转 vs 自旋锁

优先级反转问题的出现跟自旋锁没有关系
不使用自旋锁时也可能出现优先级反转问题。只要是线程或任务有多个优先级，理论上就可能有反转问题
操作系统在优先级反转发生时通常都会有自动的解决方案，比如提高低优先级线程的优先级等
在使用iOS中的OSSpinLock时

由于这种锁不会记录持有它的线程信息，所有当发生优先级反转时，系统找不到低优先级的线程，可能因此无法通过提高优先级解决优先级反转问题

再加上，高优先级线程使用自旋锁进行轮训等待锁时在一直占用CPU时间片，使得低优先级线程拿到时间片的概率降低

总结

优先级反转问题的出现跟自旋锁没有关系
但一旦出现优先级反转问题，自旋锁会让优先级反转问题不容易解决，甚至造成更严重的线程等待问题

atomic 和 os_unfair_lock

OSSpinLock被废弃后，官方建议使用os_unfair_lock代替；
os_unfair_lock其实是互斥锁（参考资料中有提到）
在老版本中，atomic内部也是用自旋锁实现的，但后续也改成互斥锁了

iOS系统中优先级反转问题是如何解决的？–参考资料中的苹果官方文档有提到

自旋锁的实现原理

自旋锁的目的是为了确保临界区只有一个线程可以访问，它的使用可以用下面这段伪代码来描述:

do {  
    Acquire Lock
        Critical section  // 临界区
    Release Lock
        Reminder section // 不需要锁保护的代码
}

自旋锁的实现思路很简单，理论上来说只要定义一个全局变量，用来表示锁的可用情况即可，伪代码如下:

bool lock = false; // 一开始没有锁上，任何线程都可以申请锁  
do {  
    while(lock); // 如果 lock 为 true 就一直死循环，相当于申请锁
    lock = true; // 挂上锁，这样别的线程就无法获得锁
        Critical section  // 临界区
    lock = false; // 相当于释放锁，这样别的线程可以进入临界区
        Reminder section // 不需要锁保护的代码        
}

这段代码存在一个问题: 如果一开始有多个线程同时执行 while 循环，他们都不会在这里卡住，而是继续执行，这样就无法保证锁的可靠性了。解决思路也很简单，只要确保申请锁的过程是原子操作即可。

原子操作

狭义上的原子操作表示一条不可打断的操作，也就是说线程在执行操作过程中，不会被操作系统挂起，而是一定会执行完。在单处理器环境下，一条汇编指令显然是原子操作，因为中断也要通过指令来实现。

真正的原子操作必须由硬件提供支持

比如 x86 平台上如果在指令前面加上 “LOCK” 前缀，对应的机器码在执行时会把总线锁住，使得其他 CPU不能再执行相同操作，从而从硬件层面确保了操作的原子性。

申请锁的过程，可以用一个原子性操作 test_and_set 来完成，它用伪代码可以这样表示:

bool test_and_set (bool *target) {  
    bool rv = *target; 
    *target = TRUE; 
    return rv;
}


bool lock = false; // 一开始没有锁上，任何线程都可以申请锁  
do {  
    while(test_and_set(&lock); // test_and_set 是一个原子操作
        Critical section  // 临界区
    lock = false; // 相当于释放锁，这样别的线程可以进入临界区
        Reminder section // 不需要锁保护的代码        
}